Ethernet switches and IP routersTransparent BridgesFrame ForwardingFrame Forwarding 2Forwarding conditionsAddress LearningAddress Learning 2ExampleForwarding MAC frames and learningInternet Address ClassesIP AddressesRoutingIP ForwardingSlide 14Forwarding Functions at HostForwarding Functions at RouterNeed for RoutingDanger of LoopsSpanning TreesConcept - Bridge IDConcept - Root bridge of a networkConcept - For each bridgeConcept - For each LANConcept - Designated bridge/portSteps of Spanning Tree AlgorithmWhat we just didHow do the bridges determine the spanning tree?Short form notation for BPDUsOrdering of MessagesDetermine the Root BridgeCalculate the Root Path Cost Determine the Root PortDetermine if the bridge is the designated bridge for any of the LANs connected to its portsSelecting the Ports for the Spanning TreeBuilding the Spanning TreeAdapting to ChangesExample 1Example 2 (Practice - Solution in Exercises)Network Example (Practice - Solution in Exercises)Interesting casesSlide 40Another caseSlide 42PriorityM. Veeraraghavan (originals by J. Liebeherr)1Ethernet switches and IP routers•Ethernet MAC address: Flat 6-byte addresses–Full address match for forwarding –If there is no match, forward on all interfaces as determined by state (set by spanning tree algorithm)•IP address: Hierarchical 4-byte addresses–Longest prefix matchM. Veeraraghavan (originals by J. Liebeherr)2Transparent Bridges•Three aspects of bridge operation:(1) Forwarding of Frames(2) Learning of Addresses(3) Spanning Tree AlgorithmM. Veeraraghavan (originals by J. Liebeherr)3Frame Forwarding•Each bridge maintains a filtering database with entries< MAC address, port, age> MAC address: host name or group addressport: port number of bridgeage: aging time of entrywith interpretation: •a machine with MAC address lies in direction of the port number from the bridge. The entry is age time units old.M. Veeraraghavan (originals by J. Liebeherr)4•Assume a MAC frame arrives on port x.Frame Forwarding 2Bridge 2Port A Port CPort xPort BSearch if MAC address of destination is listed for ports A, B, or C.Flood the frame, i.e., send the frame on all ports except port x if portstates allow it.Found?Notfound ?Forward frame on corresponding port if different from the port on which the frame arrived and the port state allows itM. Veeraraghavan (originals by J. Liebeherr)5Forwarding conditions•Forward a MAC frame if and only if–The receiving port is in a forwarding state (will learn the meaning of this term in the routing lecture)–The transmitting port is in a forwarding state–Either the filtering database indicates the port number for the destination MAC address or no such entry is present (in which case all ports are eligible transmission ports) –Do not transmit on port on which frame was received–The maximum service data unit size supported by the LAN to which the transmitting port is connected is not exceeded.M. Veeraraghavan (originals by J. Liebeherr)6•In principle, the filtering database could be set statically (=static routing)•In the 802.1 bridge, the process is made automatic with a simple heuristic: The source address field of a frame that arrives on a port is used by the bridge to update its filtering database, which indicates the port through which each host is reachable. Address LearningBridge 2Port A Port CPort xPort BLAN 3host nM. Veeraraghavan (originals by J. Liebeherr)7Algorithm: •For each frame received, the bridge stores the source address field in the filtering database together with the port on which the frame was received.•All entries are deleted after some time (default is 300 seconds).Address Learning 2Bridge 2Port A Port CPort xPort BLAN 3host nM. Veeraraghavan (originals by J. Liebeherr)8ExampleBridge 1Port1LAN 1ALAN 2CB DLAN 3E FPort2Bridge 2Port1Port2•Consider the following packets: <Src=A, Dest=F>, <Src=C, Dest=A>, <Src=E, Dest=C>•What have the bridges learned?M. Veeraraghavan (originals by J. Liebeherr)9Forwarding MAC frames and learning•Relaying of MAC frames and observation of trafficFramereceptionFrametransmissionFiltering databasePort stateinformationPort stateinformationFrameforw ardingLearningprocessLearning process writes Filtering DBFrame forwarding reads Filtering DBM. Veeraraghavan (originals by J. Liebeherr)10Internet Address Classes•IP distinguishes 5 classes of addresses. 1Class A1 1 1 00network id7 bitshost24 bitsClass B1network id14 bitshost16 bits0Class C1network id21 bits01host8 bitsClass D1 multicast group id28 bits01 1Class E(reserved for future use)27 bitsM. Veeraraghavan (originals by J. Liebeherr)11IP Addresses•The end points of each range are not allowed because all zeros and all ones are disallowed for netid, subnetid and hostid (see pg. 42 of text and RFC791).Class From ToA0.0.0.0 127.255.255.255B128.0.0.0 191.255.255.255C192.0.0.0 223.255.255.255D224.0.0.0 239.255.255.255E240.0.0.0 247.255.255.255M. Veeraraghavan (originals by J. Liebeherr)12Routing•There are two parts to the routing problem: 1. How to pass a packet from an input interface to the output interface of a router (“packet forwar- ding”) ? 2. How to create routing tables? •In this lecture, we only discuss the packet forwarding part. The other function is discussed in the routing protocols lecture.M. Veeraraghavan (originals by J. Liebeherr)13•A packet is typically forwarded to a large number of routers before reaching the destination host. •IP forwarding is done on a hop-by-hop basis, i.e., no one knows the complete route. The goal of forwarding is to bring the IP datagram closer to the destination.IP ForwardingM. Veeraraghavan (originals by J. Liebeherr)14IP Forwarding•IP forwarding is performed by both hosts and routers.•The difference between IP forwarding in a host and in a router is that a host’s IP module does not forward packets received on an interface to another interface (if it does then it is behaving as a router). In a host, IP forwarding is from the higher layers to an interface or vice versa•Both routers and hosts have a routing table. Routing table entries look like this and is looked up for each datagram:M. Veeraraghavan (originals by J. Liebeherr)15Forwarding Functions at Host•Forwarding an IP datagram at a host:DestIP = destination IP addressIf (destination is on the same network as host)Deliver datagram to destination directly;else Send datagram to default router;•Reception of an IP datagram at a