CS438 08 Bridges

Information about CS438 08 Bridges

Published on December 28, 2007

Author: WoodRock

Source: authorstream.com

Content

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

Related presentations


Other presentations created by WoodRock

VoIP endfassung
18. 06. 2007
0 views

VoIP endfassung

Lone Wolf Presentation
22. 04. 2008
0 views

Lone Wolf Presentation

Guersenfinal
17. 04. 2008
0 views

Guersenfinal

10 bridge
16. 04. 2008
0 views

10 bridge

Reveiwfinal spring
14. 04. 2008
0 views

Reveiwfinal spring

ch03 edit
13. 04. 2008
0 views

ch03 edit

Howcroft CME
10. 04. 2008
0 views

Howcroft CME

ARPA07distribute
09. 04. 2008
0 views

ARPA07distribute

PowerPoint Presentation 2007
07. 04. 2008
0 views

PowerPoint Presentation 2007

Central Asia short
30. 03. 2008
0 views

Central Asia short

APALSAGeneralMeeting
27. 03. 2008
0 views

APALSAGeneralMeeting

elements compounds mixtures
04. 01. 2008
0 views

elements compounds mixtures

Moodle for english teachers
27. 06. 2007
0 views

Moodle for english teachers

YagerDOE2005
17. 09. 2007
0 views

YagerDOE2005

JESSICA2 HKJU Dec 18 2002
17. 09. 2007
0 views

JESSICA2 HKJU Dec 18 2002

wipo smes del 07 www 76775
24. 09. 2007
0 views

wipo smes del 07 www 76775

LDAP Integration
24. 09. 2007
0 views

LDAP Integration

SAR presentation Final
24. 09. 2007
0 views

SAR presentation Final

Politics ml Z
02. 10. 2007
0 views

Politics ml Z

sparkles
04. 10. 2007
0 views

sparkles

Extreme Makeover
17. 09. 2007
0 views

Extreme Makeover

current status ebxml cppa tc
29. 10. 2007
0 views

current status ebxml cppa tc

ast201 2007 lect11
28. 11. 2007
0 views

ast201 2007 lect11

judicial
28. 08. 2007
0 views

judicial

Laptop Security
28. 08. 2007
0 views

Laptop Security

hammer fatriv
28. 08. 2007
0 views

hammer fatriv

Air Monitoring
23. 10. 2007
0 views

Air Monitoring

CONFINED
07. 11. 2007
0 views

CONFINED

Kansas GRB 5
15. 11. 2007
0 views

Kansas GRB 5

ATS
16. 11. 2007
0 views

ATS

Lecture 4 Bioterrorism Dunne
17. 11. 2007
0 views

Lecture 4 Bioterrorism Dunne

wieser sybase
20. 11. 2007
0 views

wieser sybase

rushdie
21. 11. 2007
0 views

rushdie

Napoleon I
26. 11. 2007
0 views

Napoleon I

SonnetOL
11. 08. 2007
0 views

SonnetOL

Steve Lafferty optimized
11. 08. 2007
0 views

Steve Lafferty optimized

Tibetian test 2
11. 08. 2007
0 views

Tibetian test 2

Plumbing an Information Space
02. 01. 2008
0 views

Plumbing an Information Space

Tree of Life 3 11 03
11. 08. 2007
0 views

Tree of Life 3 11 03

savas dangerous offenders
11. 08. 2007
0 views

savas dangerous offenders

Memory Revisited
12. 10. 2007
0 views

Memory Revisited

Dermatology Revision
05. 01. 2008
0 views

Dermatology Revision

FROM THE DISCOVERY OF HELIX
16. 10. 2007
0 views

FROM THE DISCOVERY OF HELIX

504d AACR poster 2005 cfg
30. 10. 2007
0 views

504d AACR poster 2005 cfg

Zeeberg
17. 09. 2007
0 views

Zeeberg

sweep
11. 08. 2007
0 views

sweep

Industrialization Ideology
26. 10. 2007
0 views

Industrialization Ideology

sa advocacy
24. 09. 2007
0 views

sa advocacy

CausalArguments
26. 11. 2007
0 views

CausalArguments

JostDeutschAwards
07. 01. 2008
0 views

JostDeutschAwards

Class24ImlicatureExp
19. 02. 2008
0 views

Class24ImlicatureExp

Lars Nord Presentation at HA2005
08. 10. 2007
0 views

Lars Nord Presentation at HA2005

ConEvals
27. 02. 2008
0 views

ConEvals

moodle themes
27. 06. 2007
0 views

moodle themes

Moodle lokalp
27. 06. 2007
0 views

Moodle lokalp

Moodle na UE final
27. 06. 2007
0 views

Moodle na UE final

SIRESENAC06
06. 03. 2008
0 views

SIRESENAC06

Seance 4 Alissa fr
24. 10. 2007
0 views

Seance 4 Alissa fr

SKita gesture
11. 08. 2007
0 views

SKita gesture

8 lessons learnt from nms
18. 03. 2008
0 views

8 lessons learnt from nms

WORKING IN THE EU INSTITUTIONS
20. 03. 2008
0 views

WORKING IN THE EU INSTITUTIONS

semantic web applications
25. 03. 2008
0 views

semantic web applications

FutureofNews
05. 10. 2007
0 views

FutureofNews

sxu 1 05 06
11. 08. 2007
0 views

sxu 1 05 06

canarias
23. 10. 2007
0 views

canarias

Reintegration ProgramFinal
28. 12. 2007
0 views

Reintegration ProgramFinal

G Abaee
22. 11. 2007
0 views

G Abaee

tromsoe
11. 08. 2007
0 views

tromsoe

glazerbusan
12. 10. 2007
0 views

glazerbusan

Stockholm Tutorial June 2001
12. 03. 2008
0 views

Stockholm Tutorial June 2001

TF Rschede
18. 06. 2007
0 views

TF Rschede

telwisa 5
18. 06. 2007
0 views

telwisa 5

Teitler Framework
18. 06. 2007
0 views

Teitler Framework

STRUMENTI tris DI ATTUAZIONE
18. 06. 2007
0 views

STRUMENTI tris DI ATTUAZIONE

strategic plan
18. 06. 2007
0 views

strategic plan

STEROIDS
18. 06. 2007
0 views

STEROIDS

Slide musso taranto
18. 06. 2007
0 views

Slide musso taranto

V 005 Gierke
18. 06. 2007
0 views

V 005 Gierke

Vorlesung BGB AT 1
18. 06. 2007
0 views

Vorlesung BGB AT 1

violenza
18. 06. 2007
0 views

violenza

Varma
18. 06. 2007
0 views

Varma

usenix
18. 06. 2007
0 views

usenix

unter Mitglieder wenn das geht
18. 06. 2007
0 views

unter Mitglieder wenn das geht

Unterrichtsbeobachtu ng
18. 06. 2007
0 views

Unterrichtsbeobachtu ng

Traechtigkeit
18. 06. 2007
0 views

Traechtigkeit

todoslossantosanual
02. 11. 2007
0 views

todoslossantosanual

vortrag we mu 220602
18. 06. 2007
0 views

vortrag we mu 220602

SOR Legal Updates 2006 141962 7
11. 08. 2007
0 views

SOR Legal Updates 2006 141962 7

Bigwood 1
13. 03. 2008
0 views

Bigwood 1

lrec metadata
14. 11. 2007
0 views

lrec metadata

termininfo D2D Konferenz2006
18. 06. 2007
0 views

termininfo D2D Konferenz2006

3320 l09
17. 09. 2007
0 views

3320 l09

typologie
18. 06. 2007
0 views

typologie

antalya
03. 09. 2007
0 views

antalya

sermonpp thy will be done
11. 08. 2007
0 views

sermonpp thy will be done

gabriel
24. 09. 2007
0 views

gabriel

tack2
24. 09. 2007
0 views

tack2

VORTRAG BW
18. 06. 2007
0 views

VORTRAG BW

The Perils of Childhood Obesity
11. 08. 2007
0 views

The Perils of Childhood Obesity

GT TurkeyCountryPresent ation
23. 10. 2007
0 views

GT TurkeyCountryPresent ation

Open Everything 3 9
01. 10. 2007
0 views

Open Everything 3 9

arnaud
28. 09. 2007
0 views

arnaud

file1180026507
22. 10. 2007
0 views

file1180026507

yasinsky
24. 09. 2007
0 views

yasinsky

healthy body esteem
03. 10. 2007
0 views

healthy body esteem

moodle presentation epfl final
27. 06. 2007
0 views

moodle presentation epfl final

37 Yale SA Program Overview 07
24. 09. 2007
0 views

37 Yale SA Program Overview 07

song slides
11. 08. 2007
0 views

song slides

Stuttgart
18. 06. 2007
0 views

Stuttgart

site wsa
29. 02. 2008
0 views

site wsa

pearson
24. 09. 2007
0 views

pearson

09 s4 fr
11. 03. 2008
0 views

09 s4 fr

EPS
17. 10. 2007
0 views

EPS

OARS CRJ 2006
24. 09. 2007
0 views

OARS CRJ 2006

7Paul Hopkin
11. 12. 2007
0 views

7Paul Hopkin

Sofia 29 09 30 02
23. 11. 2007
0 views

Sofia 29 09 30 02

CSI NetSec2004
29. 10. 2007
0 views

CSI NetSec2004

santTOPch11
11. 08. 2007
0 views

santTOPch11

HumanCapitalFINAL
24. 09. 2007
0 views

HumanCapitalFINAL

Carmelo Polino
22. 10. 2007
0 views

Carmelo Polino

Poeplau ECLOUD07
03. 01. 2008
0 views

Poeplau ECLOUD07

peytonap
17. 09. 2007
0 views

peytonap

BUTE 2005feb Milano COST291
16. 10. 2007
0 views

BUTE 2005feb Milano COST291