lecture18

Bridges and Extended LANs: 

Bridges and Extended LANs

Overview: 

Overview LANs have physical limitations (e.g., 2500m Ethernet) Connect two or more LANs with a bridge accept and forward strategy level 2 connection (does not add packet header) Collection of LANs connected by bridges called an exteneded LAN

Problems: 

Problems Heterogeneity Different Host types Different protocols Different hardware medium (FDDI, Ethernet) Scale Internet has doubled in size each year for the last 20 years

Bridges vs Switches: 

Bridges vs Switches A Bridge is a link-level node that forwards frames Connect two or more multi-access networks A Switch is a multi-input, multi-output device, which transfers packets from an input to one or more outputs. So, a Bridge meets the definition of a switch, but some switches aren't link-level nodes and don’t use spanning tree and aren’t bridges

Slide5: 

Seven Layer Model Application Presentation Session Transport Network Data Link Physical Routing address framing errors electrical signals Bridge (Uses spanning tree to learn routing information Some Switches add network header for routing information)

Performance: 

Performance Switches can be built from a general-purpose workstations; will consider special-purpose hardware later.

Performance: 

Performance Aggregate bandwidth 1/2 of the I/O bus bandwidth capacity is shared among all hosts connected to switch example: 800Mbps bus can support 8 T3 ports Packets-per-second must be able to switch small packets 15,000 packets-per-second is an achievable number 66μsec/packet 50ns memory = 128 memory accesses example: 64-byte packets implies 7.69Mbps

Learning Bridges: 

Do not forward when unnecessary Maintain forwarding table Learn table entries based on source address Table is an optimization; need not be complete Always forward broadcast frames Learning Bridges Host A B C X Y Z Port 1 1 1 2 2 2

Algorithm: 

Algorithm If the address is in the tables then Forward the packet onto the necessary port. If the address is not in the tables, then Forward the packet onto every port except for the port that the packet was received on, just to make sure the destination gets the message. Add an entry in your internal tables linking the Source Address of the packet to whatever port the packet was received from.

Bridging Functionality: 

Bridging Functionality

Bridging Loops: 

Bridging Loops

Spanning Tree Algorithm: 

Spanning Tree Algorithm Extended LANs sometimes have loops

Example: 

Example B1 B4 B6 G H I J 0 1 3 4 6 7 8

Spanning Tree: 

Spanning Tree Bridges run a distributed spanning tree algorithm Select which bridges actively forward frames Developed by Radia Perlman at DEC Now IEEE 802.1 specification

Algorithm Overview: 

Algorithm Overview Each bridge has a unique id (e.g., B1, B2, B3) Select bridge with smallest id as root Select bridge on each LAN that is closest to the root as that LAN's designated bridge (use id to break ties) Each bridge forwards frames over each LAN for which it is the designated bridge

Example: 

Example

Algorithm Detail: 

Algorithm Detail Bridges exchange configuration messages id for bridge sending the message id for what the sending bridge believes to be root bridge distance (hops) from sending bridge to root bridge Each bridge records current best configuration message for each port Initially, each bridge believes it is the root When learn not root, stop generating configuration message in steady state, only root generates configuration messages

Continued...: 

Continued... When learn not designated bridge, stop forwarding configuration messages in steady state, only designated bridges forward configuration messages Root bridge continues to send configuration messages periodically If any given bridge does not receive configuration message after a period of time, starts generating configuration messages claiming to be to be the root

Example: 

Example B1 B2 B3 B5 B7 B4 B6 A B C D E F G H I J K (3,3,0) (3,3,0) (2,2,0) (2,2,0) (6,6,0) (6,6,0) (4,4,0) (4,4,0) (4,4,0) (1,1,0) (1,1,0) (1,1,0) (1,1,0) (5,5,0) (5,5,0) (5,5,0) (7,7,0) (7,7,0) (7,7,0)

Example: 

Example B1 B2 B3 B5 B7 B4 B6 A B C D E F G H I J K (3,2,1) (2,1,1) (6,1,1) (4,1,1) (4,1,1) (1,1,0) (1,1,0) (1,1,0) (1,1,0) (5,1,1) (5,1,1) (7,1,1) (7,1,1)

Example: 

Example B1 B2 B3 B5 B7 B4 B6 A B C D E F G H I J K (2,1,1) (4,1,1) (4,1,1) (1,1,0) (1,1,0) (1,1,0) (1,1,0) (5,1,1) (5,1,1) (7,1,1)

What about this one?: 

What about this one? B5 B2 B3 B1 B7 B4 B6 A B C D E F G H I J K

Broadcast and Multicast: 

Broadcast and Multicast Forward all broadcast/multicast frames (current practice) Learn when no group members downstream Accomplished by having each member of group G send a frame to bridge multicast address with G in source field

Limitations of Bridges: 

Limitations of Bridges Do not scale spanning tree algorithm does not scale broadcast does not scale Do not accommodate heterogeneity Since don’t have own header, can’t join dissimilar networks, address formats Caution: beware of transparency Congestion can cause dropped frames Additional delay frame reordering