DOC PREVIEW
CMU 15441 Computer Networking - Lecture

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

15-441 Computer NetworkingLecture 7 –Bridging, Addressing gg, gand ForwardingCopyright ©, 2007-10 Carnegie Mellon UniversityScalekkyak yak…•What breaks when we keep adding people•What breaks when we keep adding people to the same wire?9-21-06Lecture 8: Bridging/Addressing/Forwarding 2Scaleyak yak…yy•What breaks when we keep adding people•What breaks when we keep adding people to the same wire?Only solution: split up the people onto•Only solution: split up the people onto multiple wiresB t h th t lk t h th ?9-21-06Lecture 8: Bridging/Addressing/Forwarding 3•But how can they talk to each other?Problem 1 –Reconnecting LANsgyak yak…yy• When should these boxes forward packets between wires?• How do you specify a destination?•How does your packet find its way?9-21-06Lecture 8: Bridging/Addressing/Forwarding 4How does your packet find its way?Outline • Bridging• Internetworks• Methods for packet forwarding• Traditional IP addressing9-21-06Lecture 8: Bridging/Addressing/Forwarding 5Building Larger LANs: Bridgesgg g• Extend reach of a single shared medium•Connect two or more“segments”by copying data frames between•Connect two or more segments by copying data frames between them• Only copy data when needed  key difference from repeaters/hubs• Reduce collision domain compared with single LAN• Separate segments can send at once  much greater bandwidth• Challenge: learning which packets to copy across links9-21-06Lecture 8: Bridging/Addressing/Forwarding 6LAN 1 LAN 2Transparent Bridgespg• Design goals:gg• Self-configuring without hardware or software changes• Bridge do not impact the operation of the individual LANs• Three parts to making bridges transparent:1)For arding frames1)Forwarding frames2) Learning addresses/host locations3)Spanning tree algorithm9-21-06Lecture 8: Bridging/Addressing/Forwarding 7)pg gFrame ForwardinggBridge1132• A machine with MAC Address lies in the direction of numberportof the bridgeMACdirection of number portof the bridge• For every packet, the bridge “looks up” the entry for the packets destination MACMAC AddressPortA21032C9A5911Age36entry for the packets destination MAC address and forwards the packet on that port.• Other packets are broadcast – why?8711C98900AA299A323C90842215019-21-06Lecture 8: Bridging/Addressing/Forwarding 8• Timer is used to flush old entries301B2369011C269551900119031611Learning Bridgesgg• Manually filling in bridge tables?Ti i•Time consuming, error-prone• Keep track of source address of packets arriving on every link showing what segment hosts are onlink, showing what segment hosts are on• Fill in the forwarding table based on this informationhost host host host hosthostBridge9-21-06Lecture 8: Bridging/Addressing/Forwarding 9host host host host hosthostSpanning Tree Bridgespg g• More complex topologies can provide redundancy.• But can also create loops.Wh t i th bl ith l ?•What is the problem with loops?• Solution: spanning treehost host host host hosthostBridge Bridge9-21-06Lecture 8: Bridging/Addressing/Forwarding 10host host host host hosthostSpanning Tree ProtocolOverviewOverviewEmbed a tree that provides a single unique path to h d ti tieach destination:1) Elect a single bridge as a root bridge2)Each bridge calculates the distance of the2)Each bridge calculates the distance of the shortest path to the root bridge3) Each LAN identifies a designated bridge, the b id l t t th t It ill f d k tbridge closest to the root. It will forward packets to the root.4)Each bridge determines aroot port, which will4)Each bridge determines a root port, which will be used to send packets to the root5) Identify the ports that form the spanning tree9-21-06Lecture 8: Bridging/Addressing/Forwarding 11Spanning Tree AlgorithmStepsSteps• Root of the spanning tree is the bridge with the lowest identifier.All fB3B521•All ports are part of tree• Each bridge finds shortest path to the root.•Remembers port that is on theB7B211•Remembers port that is on the shortest path• Used to forward packets• Select for each LAN the B1designated bridge that has the shortest path to the root.• Identifier as tie-breakerB4B6119-21-06Lecture 8: Bridging/Addressing/Forwarding 12• Responsible for that LAN611Spanning Tree Algorithmpg g• Each node sends configuration message to all neighbors.• Identifier of the sender• Id of the presumed root•Distance to the presumed rootB3B5Distance to the presumed root• E.g. B5 sends (B5, B5, 0)• When B receive a message, it decide whether the solution is better than their local solutionB7B2better than their local solution.• A root with a lower identifier?• Same root but lower distance?• Same root, distance but sender h l id tifi ?B1has lower identifier?• After convergence, each bridge knows the root, distance to root, root port, and designated bridge for B4B69-21-06Lecture 8: Bridging/Addressing/Forwarding 13pggeach LAN.6Spanning Tree Algorithm(part 2)(part 2)• Each bridge B can now select gwhich of its ports make up the spanning tree:• B’s root portAll t f hi h B i thB3B5•All ports for which B is the designated bridge on the LAN• Bridges can not configure their portsB7B2ports.• Forwarding state or blocked state, depending on whether the port is part of the spanning treeRidilldB1•Root periodically sends configuration messages and bridges forward them over LANs they are responsible for.B4B69-21-06Lecture 8: Bridging/Addressing/Forwarding 14they are responsible for.6Spanning Tree AlgorithmExampleExample•Node B2:B3B5Node B2:• Sends (B2, B2, 0)• Receives (B1, B1, 0) from B1• Sends (B2, B1, 1) “up”•Continues the forwarding foreverB7B2Continues the forwarding forever• Node B1:• Will send notifications forever• Node B7:•Sends (B7 B7 0)B1•Sends (B7, B7, 0)• Receives (B1, B1, 0) from B1• Sends (B7, B1, 1) “up” and “right”• Receives (B5, B5, 0) - ignored•Receives(B5B11)-betterB4B6•Receives (B5, B1, 1) -better• Continues forwarding the B1 messages forever to the “right”9-21-06Lecture 8: Bridging/Addressing/Forwarding 156Problem 2 –Bridging Weaknessesgg• Doesn’t handle incompatible LAN technologiestechnologies• How well does it scale?9-21-06Lecture 8: Bridging/Addressing/Forwarding 16Outline • Bridging• Internetworks• Methods for packet forwarding• Traditional IP addressing9-21-06Lecture 8: Bridging/Addressing/Forwarding 17What is an


View Full Document

CMU 15441 Computer Networking - Lecture

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

14 pages

Lecture

Lecture

78 pages

Lecture

Lecture

35 pages

Lecture

Lecture

4 pages

Lecture

Lecture

4 pages

Lecture

Lecture

29 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

44 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

13 pages

Lecture

Lecture

47 pages

Lecture

Lecture

49 pages

Lecture

Lecture

7 pages

Lecture

Lecture

18 pages

Lecture

Lecture

15 pages

Lecture

Lecture

74 pages

Lecture

Lecture

35 pages

Lecture

Lecture

17 pages

lecture

lecture

13 pages

Lecture

Lecture

21 pages

Lecture

Lecture

14 pages

Lecture

Lecture

53 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

10 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

lecture

lecture

11 pages

lecture

lecture

7 pages

Lecture

Lecture

10 pages

lecture

lecture

46 pages

lecture

lecture

7 pages

Lecture

Lecture

8 pages

lecture

lecture

55 pages

lecture

lecture

45 pages

lecture

lecture

47 pages

lecture

lecture

39 pages

lecture

lecture

33 pages

lecture

lecture

38 pages

lecture

lecture

9 pages

midterm

midterm

16 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

46 pages

Lecture

Lecture

8 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

9 pages

Lab

Lab

3 pages

Lecture

Lecture

53 pages

Lecture

Lecture

51 pages

Lecture

Lecture

38 pages

Lecture

Lecture

42 pages

Lecture

Lecture

49 pages

Lecture

Lecture

63 pages

Lecture

Lecture

7 pages

Lecture

Lecture

51 pages

Lecture

Lecture

35 pages

Lecture

Lecture

29 pages

Lecture

Lecture

65 pages

Lecture

Lecture

47 pages

Lecture

Lecture

41 pages

Lecture

Lecture

41 pages

Lecture

Lecture

32 pages

Lecture

Lecture

35 pages

Lecture

Lecture

15 pages

Lecture

Lecture

52 pages

Lecture

Lecture

16 pages

Lecture

Lecture

4 pages

lecture

lecture

27 pages

lecture04

lecture04

46 pages

Lecture

Lecture

46 pages

Lecture

Lecture

13 pages

lecture

lecture

41 pages

lecture

lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

Lecture

Lecture

38 pages

lecture

lecture

11 pages

Lecture

Lecture

42 pages

Lecture

Lecture

12 pages

Lecture

Lecture

36 pages

Lecture

Lecture

46 pages

Lecture

Lecture

35 pages

Lecture

Lecture

34 pages

Lecture

Lecture

9 pages

lecture

lecture

49 pages

class03

class03

39 pages

Lecture

Lecture

8 pages

Lecture 8

Lecture 8

42 pages

Lecture

Lecture

20 pages

lecture

lecture

29 pages

Lecture

Lecture

9 pages

lecture

lecture

46 pages

Lecture

Lecture

24 pages

Lecture

Lecture

41 pages

Lecture

Lecture

37 pages

lecture

lecture

59 pages

Lecture

Lecture

47 pages

Lecture

Lecture

34 pages

Lecture

Lecture

38 pages

Lecture

Lecture

28 pages

Exam

Exam

17 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

9 pages

Project

Project

20 pages

Lecture

Lecture

40 pages

L13b_Exam

L13b_Exam

17 pages

Lecture

Lecture

48 pages

Lecture

Lecture

10 pages

Lecture

Lecture

52 pages

21-p2p

21-p2p

16 pages

lecture

lecture

77 pages

Lecture

Lecture

18 pages

Lecture

Lecture

62 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

Project

Project

20 pages

Lecture

Lecture

47 pages

Lecture

Lecture

38 pages

Lecture

Lecture

35 pages

Roundup

Roundup

45 pages

Lecture

Lecture

47 pages

Lecture

Lecture

39 pages

Lecture

Lecture

13 pages

Midterm

Midterm

22 pages

Project

Project

26 pages

Lecture

Lecture

11 pages

Project

Project

27 pages

Lecture

Lecture

10 pages

Lecture

Lecture

50 pages

Lab

Lab

9 pages

Lecture

Lecture

30 pages

Lecture

Lecture

6 pages

r05-ruby

r05-ruby

27 pages

Lecture

Lecture

8 pages

Lecture

Lecture

28 pages

Lecture

Lecture

30 pages

Project

Project

13 pages

Lecture

Lecture

11 pages

Lecture

Lecture

12 pages

Lecture

Lecture

48 pages

Lecture

Lecture

55 pages

Lecture

Lecture

36 pages

Lecture

Lecture

17 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?