Bridges and LAN SwitchesEthernet Backoff revisitedRepeated CollisionsCapture EffectBridges: Building Extended LAN’sBridgesBridges vs. SwitchesUses and Limitations of BridgesBridges with LoopsExample Extended LAN with LOOPSSpanning Tree AlgorithmDefining a Spanning TreeSlide 13Using a Spanning Tree: ForwardingFinding the Tree by a distributed AlgorithmDistributed Spanning Tree AlgorithmSlide 18Slide 19Bridges: LimitationsSlide 21SwitchForwardingSelf learningFiltering/ForwardingSwitch exampleSlide 27Switch: traffic isolationSwitches: dedicated accessMore on SwitchesInstitutional networkSwitches vs. RoutersSummary comparison01/14/19 CS/ECE 438 - UIUC, Fall 2006 1Bridges and LAN Switches01/14/19 CS/ECE 438 - UIUC, Fall 2006 2Ethernet Backoff revisitedAfter N collisions, pick a number k between 0 and 2N-1Wait for k*51.2 usSend frame if no one has started using the channel01/14/19 CS/ECE 438 - UIUC, Fall 2006 3Repeated CollisionsSuppose A, B, and C each have a frame to send, causing a collisionA picks k=0, B and C pick k=1A wins, sends frameAfter A is done, B and C both try to send againCollision againIncrease collision counter01/14/19 CS/ECE 438 - UIUC, Fall 2006 4Capture EffectA and B collideA picks 0, B picks 1A wins, transmits frameSuppose A has another frame to sendA and B collide againA’s collision counter is 1, pick k from 0,1B’s collision counter is 2, pick k from 0,1,2,3A is likely to win againAnd keep winning!01/14/19 CS/ECE 438 - UIUC, Fall 2006 5Bridges: Building Extended LAN’sTraditional LANShared medium (e.g., Ethernet)Cheap, easy to administerSupports broadcast trafficProblemScale LAN conceptLarger geographic area (> O(1 km))More hosts (> O(100))But retain LAN-like functionalitySolutionbridges01/14/19 CS/ECE 438 - UIUC, Fall 2006 6BridgesProblemLANs have physical limitationsEthernet – 1500mSolutionConnect two or more LANs with a bridgeAccept and forwardLevel 2 connection (no extra packet header)A collection of LANs connected by bridges is called an extended LAN01/14/19 CS/ECE 438 - UIUC, Fall 2006 7Bridges vs. SwitchesSwitch Receive frame on input portTranslate address to output portForward frameBridge Connect shared mediaAll ports bidirectionalRepeat subset of trafficReceive frame on one portSend on all other ports01/14/19 CS/ECE 438 - UIUC, Fall 2006 8Uses and Limitations of BridgesBridgesextend LAN conceptLimited scalability to O(1,000) hostsnot to global networksNot heterogeneoussome use of address, butno translation between frame formats01/14/19 CS/ECE 438 - UIUC, Fall 2006 9Bridges with LoopsProblemIf there is a loop in the extended LAN, a packet could circulate foreverSide question: Are loops good or bad?SolutionSelect which bridges should actively forwardCreate a spanning tree to eliminate unnecessary edgesAdds robustnessComplicates learning/forwarding01/14/19 CS/ECE 438 - UIUC, Fall 2006 10Example Extended LAN with LOOPSB9B4BB7B1B5B2AKJIHGFEDCB01/14/19 CS/ECE 438 - UIUC, Fall 2006 11Spanning Tree AlgorithmView extended LAN as bipartite graphLAN’s are graph nodesBridges are also graph nodesPorts are edges connecting LAN’s to bridgesSpanning tree requiredConnect all LAN’sCan leave out bridges01/14/19 CS/ECE 438 - UIUC, Fall 2006 12Defining a Spanning TreeBasic RulesBridge with the lowest ID is the rootFor a given bridgeA port in the direction of the root bridge is the root portFor a given LANThe bridge closest to the root (or the bridge with the lowest ID to break ties) is the designated bridge for a LANThe corresponding port is the designated portBridges with no designated ports and ports that are neither a root port nor a designated port are not part of the tree.01/14/19 CS/ECE 438 - UIUC, Fall 2006 13Spanning Tree AlgorithmB9B4BB7B1B5B2B1DDDDDAKJIHGFEDCBRRRRRDDDDDDRootD – designated port R – root port01/14/19 CS/ECE 438 - UIUC, Fall 2006 14Using a Spanning Tree: ForwardingForwardingEach bridge forwards frames over each LAN for which it is the designated bridge or connected by a root portB4B7B1B5B2B1AKJIHGFEDCB01/14/19 CS/ECE 438 - UIUC, Fall 2006 16Finding the Tree by a distributed AlgorithmBridges run a distributed spanning tree algorithmSelect when bridges should actively forward framesDeveloped by Radia Perlman at DECNow IEEE 802.1 specification01/14/19 CS/ECE 438 - UIUC, Fall 2006 17Distributed Spanning Tree AlgorithmBridges exchange configuration messages(Y,d,X)Y = root noded = distance to root nodeX = originating nodeEach bridge records current best configuration message for each portInitially, each bridge believes it is the rootWhen a bridge discovers it is not the root, stop generating messages01/14/19 CS/ECE 438 - UIUC, Fall 2006 18Distributed Spanning Tree AlgorithmBridges forward configuration messagesOutward from root bridgei.e., on all designated portsBridge assumes It is designated bridge for a LANUntil it learns otherwiseSteady Stateroot periodically send configuration messagesA timeout is used to restart the algorithm01/14/19 CS/ECE 438 - UIUC, Fall 2006 19Spanning Tree AlgorithmExample at bridge B31. B3 receives (B2, 0, B2)2. Since 2 < 3, B3 accepts B2 as root3. B3 adds one to the distance advertised by B2 and sends (B2, 1, B3)4. B2 accepts B1 as root and sends (B1, 1, B2)5. B5 accepts B1 as root and sends (B1, 1, B5)6. B3 accepts B1 as root and stops forwardingB4B7B1B5B2B1AKJIHGFEDCB01/14/19 CS/ECE 438 - UIUC, Fall 2006 20Bridges: LimitationsDoes not scaleSpanning tree algorithm scales linearlyBroadcast does not scaleVirtual LANs (VLAN)An extended LAN that is partitioned into several networksEach network appears separateLimits effect of broadcastSimple to change virtual topology01/14/19 CS/ECE 438 - UIUC, Fall 2006 21Bridges: LimitationsDoes not accommodate heterogeneityNetworks must have the same address formate.g. Ethernet-to-EthernetCautionBeware of transparencyMay break assumptions of the point-to-point protocolsFrames may get droppedVariable latencyReordering Bridges happen!01/14/19 CS/ECE 438 - UIUC, Fall 2006 22SwitchLink layer devicestores and forwards Ethernet framesexamines frame header and selectively forwards frame based on MAC dest addresswhen
View Full Document
Unlocking...