CS438 08 Bridges

Bridges and LAN Switches: 

Bridges and LAN Switches

Ethernet Backoff revisited: 

Ethernet Backoff revisited After N collisions, pick a number k between 0 and 2N-1 Wait for k*51.2 us Send frame if no one has started using the channel

Repeated Collisions: 

Repeated Collisions Suppose A, B, and C each have a frame 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 to send again Collision again Increase collision counter

Capture Effect: 

Capture 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!

Bridges: Building Extended LAN’s: 

Bridges: Building Extended LAN’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 bridges

Bridges: 

Bridges 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 an extended LAN

Bridges vs. Switches: 

Bridges 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 ports

Uses and Limitations of Bridges: 

Uses and Limitations of Bridges 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 formats

Bridges with Loops: 

Bridges with Loops Problem If there is a loop in the extended LAN, a packet could circulate forever Side question: Are loops good or bad? Solution Select which bridges should actively forward Create a spanning tree to eliminate unnecessary edges Adds robustness Complicates learning/forwarding

Example Extended LAN with LOOPS: 

Example Extended LAN with LOOPS B9 B4 B B7 B1 B5 B2 A K J I H G F E D C B

Spanning Tree Algorithm: 

Spanning 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 bridges

Defining a Spanning Tree: 

Defining 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 the lowest ID to break ties) is the designated bridge for a LAN The corresponding port is the designated port Bridges with no designated ports and ports that are neither a root port nor a designated port are not part of the tree.

Spanning Tree Algorithm: 

Spanning Tree Algorithm B9 B4 B B7 B1 B5 B2 B1 A K J I H G F E D C B Root D – designated port R – root port

Using a Spanning Tree: Forwarding: 

Using a Spanning Tree: Forwarding Forwarding Each bridge forwards frames over each LAN for which it is the designated bridge or connected by a root port

Finding the Tree by a distributed Algorithm: 

Finding the Tree by a distributed Algorithm Bridges run a distributed spanning tree algorithm Select when bridges should actively forward frames Developed by Radia Perlman at DEC Now IEEE 802.1 specification

Distributed Spanning Tree Algorithm: 

Distributed Spanning Tree Algorithm Bridges exchange configuration messages (Y,d,X) Y = root node d = distance to root node X = originating node Each bridge records current best configuration message for each port Initially, each bridge believes it is the root When a bridge discovers it is not the root, stop generating messages

Distributed Spanning Tree Algorithm: 

Distributed Spanning Tree Algorithm 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 algorithm

Spanning Tree Algorithm: 

Spanning Tree Algorithm B9 B4 B6 B7 B1 B5 B2 A K J I H G F E D C B (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)

Bridges: Limitations: 

Bridges: Limitations Does not scale Spanning tree algorithm scales linearly Broadcast does not scale Virtual LANs (VLAN) An extended LAN that is partitioned into several networks Each network appears separate Limits effect of broadcast Simple to change virtual topology

Bridges: Limitations: 

Bridges: 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!

Switch: 

Switch Link layer device stores and forwards Ethernet frames examines frame header and selectively forwards frame 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 configured

Forwarding: 

Forwarding How do determine onto which LAN segment to forward frame? Looks like a routing problem... 1 2 3

Self learning: 

Self learning A switch has a switch table entry in switch table: (MAC Address, Interface, Time Stamp) stale entries in table dropped (TTL can be 60 min) switch learns which hosts can be reached through which interfaces when frame received, switch “learns” location of sender: incoming LAN segment records sender/location pair in switch table

Filtering/Forwarding: 

forward on all but the interface on which the frame arrived Filtering/Forwarding When switch receives a frame: index switch table using MAC dest address if entry found for destination then { if dest on segment from which frame arrived then drop the frame else forward the frame on interface indicated } else flood

Switch example: 

Switch example Suppose C sends frame to D Switch receives frame from from C notes in bridge table that C is on interface 1 because D is not in table, switch forwards frame into interfaces 2 and 3 frame received by D hub hub hub switch A B C D E F G H I address interface A B E G 1 1 2 3 1 2 3

Switch example: 

Switch example Suppose D replies back with frame to C. Switch receives frame from from D notes in bridge table that D is on interface 2 because C is in table, switch forwards frame only to interface 1 frame received by C hub hub hub switch A B C D E F G H I address interface A B E G C 1 1 2 3 1

Switch: traffic isolation: 

Switch: traffic isolation switch installation breaks subnet into LAN segments switch filters packets: same-LAN-segment frames not usually forwarded onto other LAN segments segments become separate collision domains collision domain collision domain collision domain

Switches: dedicated access: 

Switches: dedicated access Switch with many interfaces Hosts have direct connection to switch No collisions; full duplex Switching: A-to-A’ and B-to-B’ simultaneously, no collisions switch A A’ B B’ C C’

More on Switches: 

More on Switches cut-through switching: frame forwarded from input to output port without first collecting entire frame slight reduction in latency combinations of shared/dedicated, 10/100/1000 Mbps interfaces

Institutional network: 

Institutional network hub hub hub switch to external network router IP subnet mail server web server

Switches vs. Routers: 

Switches vs. Routers both store-and-forward devices routers: network layer devices (examine network layer headers) switches are link layer devices routers maintain routing tables, implement routing algorithms switches maintain switch tables, implement filtering, learning algorithms

Summary comparison: 

Summary comparison