1-1©2005 Raj JainCSE473sWashington University in St. LouisHighHigh--Speed LANsSpeed LANsPart III: Part III: LLC and BridgingLLC and BridgingRaj Jain Washington UniversitySaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse473-05/1-2©2005 Raj JainCSE473sWashington University in St. LouisOverviewOverviewq Logical Link Controlq Bridgesq Path determination: Spanning treeq Layer 2 switchesq Layer 3 switches1-3©2005 Raj JainCSE473sWashington University in St. LouisLogical Link ControlLogical Link Controlq IEEE 802 Datalink:802.3CSMA?CD802.4Token Bus802.5Token RingMediaAccessLogical Link Controlq Logical Link Control Functions:q Upper layer Protocol multiplexingq Flow control (Windows)q Error Control (Retransmissions)q Several different types of LLC’s: Type 1, 2, 3, …q Based on HDLC1-4©2005 Raj JainCSE473sWashington University in St. LouisProtocol MultiplexingProtocol Multiplexingq Ethernetq IEEE 802.3Dest.AddressSourceAddressType66 2Size in bytesDest.AddressSourceAddressLengthInfo66 2IP IPX AppleTalkLLCIP IPX AppleTalkCRCCRC44PadLengthInfo1-5©2005 Raj JainCSE473sWashington University in St. LouisLLC TypesLLC Typesq Type 1: Unacknowledged connectionless (on 802.3)No flow or error control. Provides protocol multiplexing.q Type 2: Acknowledged connection oriented (on 802.5)Provides flow control, error control. Uses SABME (Set asynchronous balanced mode), UA (unnumbered ack), DM (disconneced mode), DISC (disconnect)q Type 3: Acknowledged connectionlessUses one-bit sequence numberAC command PDUs acked by AC response PDUs1-6©2005 Raj JainCSE473sWashington University in St. LouisLLC HeaderLLC Headerq Multiple network layer protocols can share a datalinkq Each protocol is identified by a “service access point (SAP)”q First bit of DSAP indicates Individual/Groupq First bit of SSAP indicateds command/responseq Eight-bit SAP ⇒ Only 256 standard values possibleq Even IP couldn’t get a standard SAP. Use Subnetwork Access Protocol SAP (SNAP SAP)ControlDSAP SSAP Info8b 8b 8b Size in bits1-7©2005 Raj JainCSE473sWashington University in St. LouisSNAP SAPSNAP SAPAA AA 03q SubNetwork Access Protocol Service Access Pointq When DSAP=AA, SSAP=AA, Control=UI,protocol ID field is used for multiplexingDSAP SSAP ControlProtocol ID Info40 bitsq Protocol ID is 40 bit long. The first 24 bits are Organizationally Unique Identifiers (OUI). OUI of 0 is used. The Ethernet type values are used in the last 16 bits.Protocol ID = 00-00-00-xx-xx1-8©2005 Raj JainCSE473sWashington University in St. LouisBridgesBridges1-9©2005 Raj JainCSE473sWashington University in St. LouisBridge: FunctionsBridge: Functionsq Monitor all frames on LAN Aq Pickup frames that are for stations on the other sideq Retransmit the frames on the other sideq Knows or learns about stations are on various sidesq Makes no modification to content of the frames.May change headers.q Provides storage for frames to be forwardedq Improves reliability (less nodes per LAN)q Improves performance (more bandwidth per node)q Security (Keeps different traffic from entering a LAN)q May provide flow and congestion control1-10©2005 Raj JainCSE473sWashington University in St. LouisInterconnection DevicesInterconnection Devicesq Repeater: PHY device that restores data and collision signalsq Hub: Multiport repeater + fault detection, notification and signal broadcastq Bridge: Datalink layer device connecting two or more collision domains (Switch = Multi-port Bridge)q Router: Network layer device (does not propagate MAC multicasts)H HBH HRouterExtended LAN=Broadcast domainLAN=CollisionDomain1-11©2005 Raj JainCSE473sWashington University in St. LouisBridge Protocol ArchitectureBridge Protocol Architecture1-12©2005 Raj JainCSE473sWashington University in St. LouisPath Determination: Spanning TreePath Determination: Spanning TreeLAN ALAN B LAN CLAN D LAN E LAN GLAN FB101B102B103B104B105B106SSSSSSSNodes = LANsEdges = BridgesBAF GD ECB101 B102B106B105B104B1031-13©2005 Raj JainCSE473sWashington University in St. LouisSpanning Tree (Cont)Spanning Tree (Cont)LAN ALAN B LAN CLAN D LAN E LAN GLAN FBr101B102Br103B104B105B106StStStSSSSB107BAF GD ECB101 B102B106B105B104B103B1071-14©2005 Raj JainCSE473sWashington University in St. LouisSpanning Tree: TerminologySpanning Tree: Terminologyq Bridge Identifier: MAC address plus a priority levelq Port identifier: For each port of a bridgeq Path cost: Cost transmitting through a portq Root Bridge: The bridge with the lowest identifierq Root port: Port with minimum cost to the root bridgeq Root path cost: Cost of the path to the root bridgeq Designated bridge: One per LAN. Provides minimum cost path from the LAN to the root bridge.q Designated Port: Connects designated bridge to LAN1-15©2005 Raj JainCSE473sWashington University in St. LouisSpanning Tree AlgorithmSpanning Tree Algorithmq All bridges multicast to “All bridges”q My IDq Root IDq My cost to rootq The bridges update their info using Dijkstra’salgorithm and rebroadcastq Initially all bridges are roots but eventually converge to one root as they find out the lowest Bridge ID.q On each LAN, the bridge with minimum cost to the root becomes the Designated bridgeq All ports of all non-designated bridges are blocked.1-16©2005 Raj JainCSE473sWashington University in St. LouisSpanning Tree ExampleSpanning Tree ExampleLAN2LAN5LAN1LAN3 LAN4Bridge 4C=5C=5Bridge 5C=5C=5Bridge 2C=10C=5Bridge 3C=10C=10Bridge 1C=10C=10C=53 41521020205510101-17©2005 Raj JainCSE473sWashington University in St. LouisSpanning Tree ExampleSpanning Tree ExampleLAN2LAN5LAN1LAN3 LAN4Bridge 4C=5C=5Bridge 5C=5C=5Bridge 2C=10C=5Bridge 3C=10C=10Bridge 1C=10C=10C=53 41521020205510101-18©2005 Raj JainCSE473sWashington University in St. LouisLayer 2 SwitchesLayer 2 Switchesq Switches = Multi-port bridges with packet forwarding in hardwareq Store-and-forward switchq Accepts complete frame on input lineq Buffers it briefly, q Then routes it to appropriate output lineq Delay between sender and receiverq Cut-through switchq Switch begins repeating frame onto output line as soon as itrecognizes destination addressq Highest possible throughput q Risk of propagating bad frames: Switch unable to check CRC prior to retransmission1-19©2005 Raj JainCSE473sWashington University in St. LouisProblems with Switched NetworksProblems with Switched Networksq Broadcast Storms:q Broadcast frames are forwarded by bridges on all other portsq In large