Page 1Peter A. Steenkiste, SCS, CMU1Lecture 7Datalink – Bridging and SwitchingPeter SteenkisteDepartments of Computer Science andElectrical and Computer EngineeringCarnegie Mellon University15-441 Networking, Spring 2006http://www.cs.cmu.edu/~prs/15-441Peter A. Steenkiste, SCS, CMU2Datalink Layer Architectures● Multiple access networks.» Contention-based» Taking turns» Partitioning● Switched networks.» Switch design» Finding a pathPage 2Peter A. Steenkiste, SCS, CMU3Today’s Lecture● Bridges.● Spanning tree protocol.● Switching.● Connectivity to the home.Peter A. Steenkiste, SCS, CMU4Internetworking● There are many different devices for interconnecting networks.EthernetRouterEthernetEthernetToken-ringBridgeRepeaterATMPage 3Peter A. Steenkiste, SCS, CMU53333776655776655776655776655776655776655776655776655Internetworking Options4433221144332211114433221144332211221111443322114433221133repeater bridge(e.g. 802 MAC)routerphysicaldata linknetwork44332211443322112222gateway. . .222211111111Peter A. Steenkiste, SCS, CMU6Repeaters ● Used to interconnect multiple Ethernet segments● Merely extends the baseband cable● Amplifies all signals including collisions RepeaterPage 4Peter A. Steenkiste, SCS, CMU7Building Larger LANs:Bridges● Bridges connect multiple IEEE 802 LANs at layer 2.» Only forward packets to the right port» Reduce collision domain compared with single LAN●In contrast, repeaters rebroadcast packets.host host host host hosthost host host host hosthosthostBridgePeter A. Steenkiste, SCS, CMU8Transparent Bridges● Design goals:» “Plug and play” capability» Self-configuring without hardware or software changes» Bridge do not impact the operation of the individual LANs●Three parts to making bridges transparent:1) Forwarding of frames2) Learning of addresses3) Spanning tree algorithmPage 5Peter A. Steenkiste, SCS, CMU9The Forwarding Database● Each switch maintains a forwarding database:<MAC address, port, age>MAC address: host or group addressPort: port number on the bridgeAge: age of the entry● Meaning: A machine with MAC address lies in the direction of number port of the bridge● For every packet, the bridge “looks up” the entry for the packets destination MAC address and forwards the packet on that port.» Other packets are broadcasted – why?Peter A. Steenkiste, SCS, CMU10●Assume a frame arrives on port x.Frame ForwardingBridge 2Port A Port CPort xPort BSearch if MAC address of destination is listed for ports A, B, or C.Forward the frame on theappropriate portFlood the frame, i.e., send the frame on all ports except port x.Found?Notfound ?Page 6Peter A. Steenkiste, SCS, CMU11●In principle, the forwarding database could be set statically (=static routing)● In the 802.1 bridge, the process is made automatic with a simple heuristic:The source field of a frame that arrives on a port tells which hosts are reachable from this port.Address LearningBridge 2Port A Port CPort xPort BLAN 3host nPeter A. Steenkiste, SCS, CMU12Algorithm:● For each frame received, the source stores the source field in the forwarding database together with the port where the frame was received.● All entries are deleted after some time.Address Learning 2Bridge 2Port A Port CPort xPort BLAN 3host nPage 7Peter A. Steenkiste, SCS, CMU13ExampleBridge 2Port1LAN 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?Bridge X Bridge YPeter A. Steenkiste, SCS, CMU14Address Lookup● Address is a 48 bit IEEE MAC address.● Next hop: output port for packet.● Timer is used to flush old entries (15 second default)● Size of the table is equal to the number of hosts.Bridge8711C98900AA2Address Next HopA21032C9A591199A323C908422301B2369011C269551900119038:15Info8:368:018:168:11132Page 8Peter A. Steenkiste, SCS, CMU15Spanning Tree Bridges● More complex topologies can provide redundancy.» But can also create loops.● What is the problem with loops?» Bridges will create duplicate copies of the packets» Even worse: packets to unknown destinations will create continuous floods!host host host host hosthost host host hosthosthostBridge BridgehostPeter A. Steenkiste, SCS, CMU16●A solution to the loop problem is to embed a tree into the topology ● IEEE 802.1 has an algorithm that builds and maintains a spanning tree in a dynamic environment.● Want distributed, fully automated protocol.» Bridges exchange messages to configure the bridge » Configuration BPDUs: Configuration Bridge Protocol Data UnitsSolution: Spanning TreesPage 9Peter A. Steenkiste, SCS, CMU17Spanning Tree Example● Root of the spanning tree is the bridge with the lowest identifier.» All ports are part of tree● Each bridge finds shortest path to the root.» Remembers port that is on the shortest path» Used to forward packets● Select for each LAN the designated bridge that has the shortest path to the root.» Identifier as tie-breaker» Responsible for that LANB3B7B5B2B1B4B6121111Peter A. Steenkiste, SCS, CMU18Spanning Tree ProtocolOverviewEmbed a tree that provides a single unique path to each destination:1) Elect a single bridge as a root bridge2) Each bridge calculates the distance of the shortest path to the root bridge3) Each LAN identifies a designated bridge, the bridge closest to the root. It will forward packets to the root.4) Each bridge determines a root port, which will be used to send packets to the root5) Select the ports that form the spanning treePage 10Peter A. Steenkiste, SCS, CMU19Concepts● Each bridge has a unique identifier:Bridge ID = <MAC address + priority level>Note that a bridge has several MAC addresses (one for each port), but only one ID● Each port within a bridge has a unique identifier (port ID).● Root Bridge: The bridge with the lowest identifier is the root of the spanning tree.● Path Cost: Cost of the least cost path to the root from the port of a transmitting bridge; Assume it is measured in #Hops to the root.Peter A. Steenkiste, SCS, CMU20More Concepts● Root Port: Each bridge has a root port which identifies the next hop from a bridge to the root.● Designated Bridge, Designated Port: Single bridge on a LAN that provides the minimal cost path to the root for this LAN:- if two bridges have the same cost, select the one with highest priority- if the min-cost bridge has two or more ports on the LAN, select the port with the lowest
View Full Document
Unlocking...