WIXLIB

LAN switching and BridgesCS491G: Computer Networking LabV. ArunSlides adapted from Liebeherr and El Zarki, and Kurose and Ross1

Outline Interconnection devicesBridges/LAN switches vs. RoutersLearning BridgesTransparent bridges2

Introduction Several different devices for interconnecting erX.25NetworkTokenringGateway3

Ethernet Hub Connects hosts to Ethernet LAN and connects multiple Ethernet LANsCollisions are 802.3 MACHubHub802.3 MAC4

Bridges/LAN switches A bridge or LAN switch is a device that interconnects two or more LocalArea Networks (LANs) and forwards packets between these networks. Bridges/LAN switches operate at the Data Link Layer (Layer 2)TokenringBridgeIPLLC802.3 MACIPBridgeLLCLAN802.3 MACLLC802.5 MACLAN802.5 MAC5

Terminology: Bridge, LAN switch, Ethernet switchThere are different terms to refer to a data-link layer interconnection device: The term bridge was coined in the early 1980s. Today, the terms LAN switch or (in the context of Ethernet) Ethernetswitch are used.Convention: We will use the three terms interchangeably.6

Ethernet Hubs vs. Ethernet Switches An Ethernet switch is a packet switch for Ethernet frames Buffering of frames prevents collisions. Each port is isolated and builds its own collision domainAn Ethernet Hub does not perform buffering: Collisions occur if two frames arrive at the same SMA/CDOutputBuffers7

Dual Speed Ethernet hub Dual-speed hubsoperate at 10 Mbps and100 Mbps per second Conceptually thesehubs operate like twoEthernet hubsseparated by a bridge100 Mbps100 Mbps100 Mbps100 Mbps10 Mbps10 Mbps10 Mbps10 MbpsDual-SpeedEthernet Hub8

Routers Routers operate at the Network Layer (Layer 3) Interconnect IP networksIP networkIP networkIP CPTCPIPNetworkAccessHostIPIP protocolDataLinkNetworkAccessIPIP protocolNetworkAccessRouterDataLinkNetworkAccessIP Host9

Gateways The term “Gateway” is used with different meanings indifferent contexts “Gateway” is a generic term for routers (Level 3) “Gateway” is also used for a device that interconnectsdifferent Layer 3 networks and which performs translation ofprotocols (“Multi-protocol router”)SNANetworkX.25NetworkIP NetworkHostGatewayHostGateway10

Bridges versus Routers An enterprise network (e.g., university) with a large number oflocal area networks (LANs) can use routers or bridges––––1980s: LANs interconnection via bridgesLate 1980s and early 1990s: increasingly use of routersSince mid1990s: LAN switches replace most routersLate 2000s: Switches and SDN11

A Routed Enterprise NetworkRouterInternetHubFDDIFDDI12

A Switched Enterprise NetworkInternetRouterBridge/Switch13

Interconnecting networks:Bridges versus RoutersRouters Each host’s IP address must beconfigured Bridges/LAN switches MAC addresses of hosts arehardwiredIf network is reconfigured, IPaddresses may need to bereassigned No network configuration needed Routing done via RIP or OSPF Each router manipulates packetheader (e.g., reduces TTL field)Routing done by– learning bridge algorithm– spanning tree algorithmBridges do not manipulate frames 14

BridgesOverall design goal: Complete transparency“Plug-and-play”Self-configuring without hardware or software changesBridges should not impact operation of existing LANsThree parts to understanding bridges:(1) Forwarding of Frames(2) Learning of Addresses(3) Spanning Tree Algorithm15

(1) Frame Forwarding Each bridge maintains a MAC forwarding tableForwarding table plays the same role as the routing table of an IP routerEntries have the form ( MAC address, port, age), whereMAC address:port:age:host name or group addressport number of bridgeaging time of entry (in seconds)with interpretation:a machine with MAC address lies in direction of the port numberfrom the bridge. The entry is age time units old.MAC forwarding tableMAC 102016

(1) Frame Forwarding Assume a MAC frame arrives on port x.Port xIs MAC address ofdestination in forwardingtable for ports A, B, or C ?Found?Forward the frame on theappropriate portBridge 2Port APort CPort BNotfound ?Flood the frame,i.e.,send the frame on allports except port x.17

(2) Address Learning (Learning Bridges) Routing entries set automatically with a simple heuristic:Source field of a frame that arrives on a port tellswhich hosts are reachable from this port.Src x, Dest ySrc x, Dest ySrc x,Src y, Dest yDest xPort 1Port 2Port 3Port 4x is at Port 3y is at Port 4Port 5Port 6Src x,Src y, Dest yDest xSrc x, Dest ySrc x, Dest y18

(2) Address Learning (Learning Bridges)Learning Algorithm: For each frame received, the source stores the sourcefield in the forwarding database together with the portwhere the frame was received. All entries are deleted after some time (default is 15seconds).Src y, Dest xPort 1Port 2Src y, Dest xPort 3Port 4x is at Port 3y is at Port 4Port 5Port 619

Example Consider the following packets:(Src A, Dest F), (Src C, Dest A), (Src E, Dest C) What have the bridges learned?BridgeBridge 12Port1Bridge 2Port2LAN 1ABPort2Port1LAN 2CLAN 3DEF20

Need for a forwarding between networks What do bridges do ifsome LANs arereachable only inmultiple hops ?What do bridges do if thepath between two LANsis not unique ?LAN 2dBridge 4Bridge 3Bridge 1LAN 5Bridge 5LAN 1Bridge 2LAN 3LAN 421

Problems with network of bridges Consider the two LANs that are connectedby two bridges.LAN 2 Assume host n is transmitting aframe F with unknown destination.What is happening?FF Bridges A and B flood the frameBridge BBridge Ato LAN 2.FF Bridge B sees F on LAN 2 (withunknown destination), and copiesLAN 1the frame back to LAN 1 Bridge A does the same.F Duplication causes “broadcast storm”Where’s the problem? What’s thehost nsolution ?22

Transparent Bridges Three principal approaches can be found:– Fixed Routing– Source Routing– Spanning Tree Routing (IEEE 802.1d) We only discuss the last one Bridges that execute the spanning tree algorithm are calledtransparent bridges23

Spanning Tree Protocol (IEEE 802.1d) Spanning Tree Protocol (SPT) is asolution to prevent loops whenforwarding frames between LANs– Standardized as IEEE 802.1dLAN 2dBridge 4Bridge 3 SPT organizes bridges and LANs asspanning tree in a dynamicenvironment– Frames are forwarded only alongthe branches of the spanning tree– Trees don’t have loopsBridge 1LAN 5Bridge 5LAN 1Bridges exchange messages toconfigure the bridge (Bridge ProtocolData Unit or BPDUs) to build tree.Bridge 2LAN 3LAN 424

Configuration BPDUsDestinationMAC addressSource MACaddressmessage typeSet to 0lowest bit is "topology change bit (TC bit)flagsCostbridge IDport IDID of rootCost of the path from thebridge sending thismessageID of bridge sending this messagemessage ageID of port from whichmessage is sentmaximum ageTime betweenBPDUs from the root(default: 1sec)Set to 0versionroot IDConfigurationMessageSet to 0protocol identifierhello timeforward delayTime betweenrecalculations of thespanning tree(default: 15 secs)time since root sent amessage onwhich this message is based25

What do the BPDUs do?With the help of the BPDUs, bridges can: Elect a single bridge as the root bridge. Calculate the distance of the shortest path to the root bridge Each LAN can determine a designated bridge, which is thebridge closest to the root. The designated bridge will forwardpackets towards the root bridge. Each bridge can determine a root port, the port that gives thebest path to the root. Select ports to be included in the spanning tree.26

Concepts Each bridge as a unique identifier:Bridge IDBridge ID Priority :2 bytesBridge MAC address: 6 bytes– Priority is configured– Bridge MAC address is lowest MAC addresses of all ports Each port of a bridge has a unique identifier (port ID). Root Bridge: The bridge with the lowest identifier is the rootof the spanning tree. Root Port:Each bridge has a root port which identifies thenext hop from a bridge to the root.27

Concepts Root Path Cost: For each bridge, the cost of the min-costpath to the root. Designated Bridge, Designated Port: Single bridge on aLAN that provides the minimal cost path to theroot for this LAN:- if two bridges have the same cost, selectone with highest priority- if min-cost bridge has two or more portson the LAN, select port with lowest ID Note: We assume that “cost” of a path is the number of “hops”.28

Steps of Spanning Tree Algorithm Each bridge is sending out BPDUs that contain the followinginformation:root ID cost bridge ID port IDroot bridge (what the sender thinks it is)root path cost for sending bridgeIdentifies sending bridgeIdentifies the sending port Transmission of BPDUs results in the distributed computationof a spanning tree Convergence of the algorithm is very quick29

Ordering of Messages We define an ordering of BPDU messagesID R1 C1 ID B1 ID P1M1ID R2 C2 ID B2 ID P2M2We say M1 advertises a better path than M2 (“M1 M2”) if(R1 R2),Or (R1 R2) and (C1 C2),Or (R1 R2) and (C1 C2) and (B1 B2),Or (R1 R2) and (C1 C2) and (B1 B2) and (P1 P2)30

Initializing the Spanning Tree Protocol Initially, all bridges assume they are the root bridge. Each bridge B sends BPDUs of this form on its LANs fromeach port P:B0BP Each bridge looks at the BPDUs received on all its ports andits own transmitted BPDUs. Root bridge updated to the smallest received root ID that hasbeen received so far31

Operations of Spanning Tree Protocol Each bridge B looks on all its ports for BPDUs that are better than itsown BPDUs Suppose a bridge with BPDU:M1R1 C1 B1 P1receives a “better” BPDU:M2R2 C2 B2 P2Then it will update the BPDU to:R2 C2 1 B1 P1 However, the new BPDU is not necessarily sent outOn each bridge, the port where the “best BPDU” (via relation “ “) wasreceived is the root port of the bridge.32

When to send a BPDU Say, B has generated a BPDU for each port xR CostBxB will send this BPDU on port x only if itsBPDU is better (via relation “ “) than anyBPDU that B received from port x.Port xBridge BPort APort CPort B In this case, B also assumes that itis the designated bridge for theLAN to which the port connects And port x is the designated port of that LAN33

Selecting the Ports for the Spanning Tree Each bridges makes a local decision which of its ports arepart of the spanning tree Now B can decide which ports are in the spanning tree: B’s root port is part of the spanning tree All designated ports are part of the spanning tree All other ports are not part of the spanning tree B’s ports that are in the spanning tree will forward packets( forwarding state) B’s ports that are not in the spanning tree will not forwardpackets ( blocking state)34

Building the Spanning Tree Consider the network on the right.Assume that the bridges havecalculated the designated ports(D) and the root ports (R) asindicated.LAN 2dDBridgeBridgeDRRLAN 5BridgeR BridgeWhat is the spanning tree?– On each LAN, connect R portsto the D ports on this LANDLAN 1RDLAN 3BridgeDLAN 435

Example Assume that all bridges send out their BPDU’s once per second, and assume thatall bridges send their BPDUs at the same timeAssume that all bridges are turned on simultaneously at time T 0 sec.Bridge ID 5Bridge ID 7LANLANport Cport Aport Cport ALANport Bport Bport Bport ABridgeID 3port BLANport ABridgeID 1port ALANport CBridge ID2port Bport BLANport Aport Cport DBridge ID 6LAN36

Example: BPDU’s sent by the bridgesT 0secBridge 1Bridge 2Bridge 3Bridge 5Bridge 6Bridge 6,0,6,port)(7,0,7,port)sent on ports:A,BportsA,Bports D(1,1,7,port)noneT 1secT 2sec In the table (1,0,1,port) means that the BPDU is (1,0,1,A) if the BPDU is sent on port Aand (1,0,1,B) if it is sent on port B. At T 1, Bridge 7 receives two BPDUs from Bridge 1: (1,0,1,A) and (1,0,1,B). We assumethat A is numerically smaller than B. If not, then the root port of Bridge 7 changes.37