CS438 08 Bridges

67 %
33 %
Information about CS438 08 Bridges

Published on December 28, 2007

Author: WoodRock

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

bYTEBoss CareCostReport7-08

Multi-Yr. Inventory. Current Yr. Inventory. Fee for Service Contracts Only. III. S&S & IV. Indirect(pg.5-6). II. PS-Benefits (pg.4) . II. PS-Salaries (pg.3).
Read more

bYTEBoss Review2

bYTEBoss Online document ... (0.08 $ 1,000)/$1,027 = 7.79 ... oferta-byczkowscy-jesieÅ -20132 secure-email-ppt coral_reef_egypt CS438-08.Bridges Igrejas ...
Read more

Ppt Lan-s-slides | Powerpoint Presentations and Slides ...

LAN switching and Bridges - University of Virginia PPT. Presentation Summary : LAN switching and Bridges Relates to Lab 6. Covers interconnection devices ...
Read more

Ethernet - Ace Recommendation Platform

Ace your next Ethernet test with these study tools from Learning Ace!
Read more


Advertising Programmes Business Solutions +Google About Google Google.com © 2015 - Privacy - Terms. Search; Images; Maps; Play; YouTube; News; Gmail ...
Read more

Ppt Provider-protocol | Powerpoint Presentations and ...

View and Download PowerPoint Presentations on PROVIDER PROTOCOL PPT. Find PowerPoint Presentations and Slides using the power of XPowerPoint.com, find free ...
Read more


... Hits BEGIN_BROWSER 80 firefox1.5.0.13 22 msie6.0 46899 webcapture 13 msie5.23 1 netscape4.08 3 firefox1.5.0 ... 1 porous 2 bridge 1 refrigerated ...
Read more

Network Programming - Ace Recommendation Platform

CS438-04.MoreSockets More Network Programming ; CS438-04.MoreSockets.1up More Network Programming ; s39 Network Programming in Java ; l7-networking-intro
Read more