110/3/07 CS/ECE 438 - UIUC, Fall 2007 1Bridges and LAN Switches10/3/07 CS/ECE 438 - UIUC, Fall 2007 2Ethernet Backoff revisited After N collisions, pick a number kbetween 0 and 2N-1 Wait for k*51.2 us Send frame if no one has started usingthe channel10/3/07 CS/ECE 438 - UIUC, Fall 2007 3Repeated Collisions Suppose A, B, and C each have aframe to send, causing a collision A picks k=0, B and C pick k=1 A wins, sends frame After A is done, B and C both try tosend again Collision again Increase collision counter10/3/07 CS/ECE 438 - UIUC, Fall 2007 4Capture Effect A and B collide A picks 0, B picks 1 A wins, transmits frame Suppose A has another frame to send A and B collide again A’s collision counter is 1, pick k from 0,1 B’s collision counter is 2, pick k from 0,1,2,3 A is likely to win again And keep winning!10/3/07 CS/ECE 438 - UIUC, Fall 2007 5Bridges: Building ExtendedLAN’s Traditional LAN Shared medium (e.g., Ethernet) Cheap, easy to administer Supports broadcast traffic Problem Scale LAN concept Larger geographic area (> O(1 km)) More hosts (> O(100)) But retain LAN-like functionality Solution bridges10/3/07 CS/ECE 438 - UIUC, Fall 2007 6Bridges Problem LANs have physical limitations Ethernet – 1500m Solution Connect two or more LANs with a bridge Accept and forward Level 2 connection (no extra packet header) A collection of LANs connected by bridges is called anextended LAN210/3/07 CS/ECE 438 - UIUC, Fall 2007 7Bridges vs. Switches Switch Receive frame on input port Translate address to output port Forward frame Bridge Connect shared media All ports bidirectional Repeat subset of traffic Receive frame on one port Send on all other ports10/3/07 CS/ECE 438 - UIUC, Fall 2007 8Uses and Limitations ofBridges Bridges extend LAN concept Limited scalability to O(1,000) hosts not to global networks Not heterogeneous some use of address, but no translation between frame formats10/3/07 CS/ECE 438 - UIUC, Fall 2007 9Bridges with Loops Problem If there is a loop in the extended LAN, a packetcould circulate forever Side question: Are loops good or bad? Solution Select which bridges should actively forward Create a spanning tree to eliminate unnecessaryedges Adds robustness Complicates learning/forwarding10/3/07 CS/ECE 438 - UIUC, Fall 2007 10Example Extended LAN withLOOPSB9B4BB7B1B5B2AKJIHGFEDCB10/3/07 CS/ECE 438 - UIUC, Fall 2007 11Spanning Tree Algorithm View extended LAN as bipartite graph LAN’s are graph nodes Bridges are also graph nodes Ports are edges connecting LAN’s to bridges Spanning tree required Connect all LAN’s Can leave out bridges10/3/07 CS/ECE 438 - UIUC, Fall 2007 12Defining a Spanning Tree Basic Rules Bridge with the lowest ID is the root For a given bridge A port in the direction of the root bridge is the root port For a given LAN The bridge closest to the root (or the bridge with thelowest ID to break ties) is the designated bridge for aLAN The corresponding port is the designated port Bridges with no designated ports and ports that areneither a root port nor a designated port are notpart of the tree.310/3/07 CS/ECE 438 - UIUC, Fall 2007 13Spanning Tree AlgorithmB9B4BB7B1B5B2B1DDDDDAKJIHGFEDCBRRRRRDDDDDDRootD –designatedportR –root port10/3/07 CS/ECE 438 - UIUC, Fall 2007 14Using a Spanning Tree:Forwarding Forwarding Each bridgeforwards framesover each LAN forwhich it is thedesignated bridge orconnected by a rootportB4B7B1B5B2B1AKJIHGFEDCB10/3/07 CS/ECE 438 - UIUC, Fall 2007 15Finding the Tree by adistributed Algorithm Bridges run a distributed spanning treealgorithm Select when bridges should activelyforward frames Developed by Radia Perlman at DEC Now IEEE 802.1 specification10/3/07 CS/ECE 438 - UIUC, Fall 2007 16Distributed Spanning TreeAlgorithm Bridges exchange configuration messages (Y,d,X) Y = root node d = distance to root node X = originating node Each bridge records current bestconfiguration message for each port Initially, each bridge believes it is the root When a bridge discovers it is not the root,stop generating messages10/3/07 CS/ECE 438 - UIUC, Fall 2007 17Distributed Spanning TreeAlgorithm Bridges forward configuration messages Outward from root bridge i.e., on all designated ports Bridge assumes It is designated bridge for a LAN Until it learns otherwise Steady State root periodically send configuration messages A timeout is used to restart the algorithm10/3/07 CS/ECE 438 - UIUC, Fall 2007 18Spanning Tree AlgorithmB9B4B6B7B1B5B2AKJIHGFEDCB(1,0,1)(4,0,4)(6,0,6)(2,0,2)(9,0,9)(5,0,5)(7,0,7)(2,1,1)(9,1,2)(5,1,1)(7,1,1)(4,1,1)(9,2,1)(6,1,1)410/3/07 CS/ECE 438 - UIUC, Fall 2007 19Bridges: Limitations Does not scale Spanning tree algorithm scales linearly Broadcast does not scale Virtual LANs (VLAN) An extended LAN that is partitioned into severalnetworks Each network appears separate Limits effect of broadcast Simple to change virtual topology10/3/07 CS/ECE 438 - UIUC, Fall 2007 20Bridges: Limitations Does not accommodate heterogeneity Networks must have the same address format e.g. Ethernet-to-Ethernet Caution Beware of transparency May break assumptions of the point-to-point protocols Frames may get dropped Variable latency Reordering Bridges happen!10/3/07 CS/ECE 438 - UIUC, Fall 2007 21Switch Link layer device stores and forwards Ethernet frames examines frame header and selectively forwardsframe based on MAC dest address when frame is to be forwarded on segment,uses CSMA/CD to access segment transparent hosts are unaware of presence of switches plug-and-play, self-learning switches do not need to be configured10/3/07 CS/ECE 438 - UIUC, Fall 2007 22Forwarding• How do determine onto which LAN segment toforward frame?• Looks like a routing problem...hubhubhubswitch12310/3/07 CS/ECE 438 - UIUC, Fall 2007 23Self learning A switch has a switch table entry in switch table: (MAC Address, Interface, Time Stamp) stale entries in table dropped (TTL can be 60min) switch learns which hosts can be reachedthrough which interfaces when frame received, switch “learns” location ofsender: incoming LAN segment records sender/location pair in
View Full Document
Unlocking...