DOC PREVIEW
CMU 15441 Computer Networking - lecture

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 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 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

2/16/2008115-441 Computer NetworkingLecture 10 – Routers and Routing1Peter SteenkisteDepartments of Computer Science andElectrical and Computer Engineering15-441 Networking, Spring 2008http://www.cs.cmu.edu/~dga/15-441/S08Outlinez ICMPz How do Routers Works?22z Routingz Distance vectorInternet Control Message Protocol (ICMP)z Short messages used to send error & other control informationz Examples» Ping request / response– Can use to check whether remote host reachableDii hbl33»Destination unreachable– Indicates how packet got & why couldn’t go further» Flow control– Slow down packet delivery rate» Redirect– Suggest alternate routing path for future messages» Router solicitation / advertisement– Helps newly connected host discover local router» Timeout– Packet exceeded maximum hop limitIP MTU Discovery with ICMPz Typically send series of packets from one host to anotherhosthostrouterrouterMTU = 4000MTU = 1500MTU = 200044yp y pz Typically, all will follow same route» Routes remain stable for minutes at a timez Makes sense to determine path MTU before sending real packetsz Operation» Send max-sized packet with “do not fragment” flag set» If encounters problem, ICMP message will be returned– “Destination unreachable: Fragmentation needed”– Usually indicates MTU encounteredIP MTU Discovery with ICMPhostrouterMTU = 1500MTU = 2000tICMPFrag. NeededMTU = 200055MTU = 4000hostMTU = 1500IPPacketLength = 4000, Don’t FragmentrouterIP MTU Discovery with ICMPhostMTU = 1500MTU = 2000tICMPFrag. NeededMTU = 1500router66MTU = 4000hostMTU = 1500IPPacketLength = 2000, Don’t Fragmentrouter2/16/20082MTU = 4000IP MTU Discovery with ICMPhosthostMTU = 1500MTU = 2000routerrouter77» When successful, no reply at IP level– “No news is good news”» Higher level protocol might have some form of acknowledgementIPPacketLength = 1500, Don’t FragmentOutlinez ICMPz How do Routers Works?88z Routingz Distance vectorRouter Architecture: Key Functionsz Run routing algorithms/protocol (RIP, OSPF, BGP)» Done by routing processorz Switching datagrams from incoming to outgoing link» Common case handled by line cards99Linput portoutput portLine CardLine Card Line CardRouter Physical LayoutJuniper T seriesCrossbar1010Cisco 12000LinecardsSwitchLine Cardsz Often uses special purpose hardware (e.g. ASICs)1111z Network interface cardsz Fast path (common-case) processing» Decrement TTL» Recompute checksum» Forward to next hop line card– Forwarding engineLine Card: Input Port1212Decentralized switching:z Process common case (fast-path) packets» Decrement TTL, update checksum, forward packetz Given datagram dest., lookup output port using routing table in input port memoryz Queue needed if datagrams arrive faster than forwarding rate into switch fabricPhysical layer:bit-level receptionData link layer:e.g., Ethernet2/16/20083Line Card: Output Port1313z Queuing required when datagrams arrive from fabric faster than the line transmission rateRouter Processorz Runs routing protocol and downloads forwarding table to forwarding enginesz Performs “slow” path processing1414» ICMP error messages» IP option processing» Fragmentation» Packets destined to routerThree Types of Switching Fabrics1515Switching Via a MemoryFirst generation routers Æ looked like PCsz Packet copied by system’s (single) CPUz Speed limited by memory bandwidth (2 bus crossings per datagram)InputPtOutputPtMemory1616PortPortSystem BusModern routers•Input port processor performs lookup, copy into memory• Cisco Catalyst 8500Switching Via a Busz Datagram from input port memory to output port memory via a shared busz Bus contention: switching speed limited by bus 1717pybandwidthz 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)Switching Via an InterconnectionNetworkz Overcome bus bandwidth limitationsz Crossbar provides full NxN interconnect» Expensive1818z Banyan networks & other interconnection nets initially developed to connect processors in multiprocessor» Typically less capable than complete crossbarz Cisco 12000: switches Gbps through the interconnection network2/16/20084Bufferingz Suppose we have N inputs and M outputs»Multiple packets for same output Æoutput contentionSwitching fabric may force different1919»Switching fabric may force different inputs to wait Æ Switch contentionz Solution – buffer packets when/where needed: input, switch, or outputz What happens when these buffers fill up?»Packets are THROWN AWAY!! This is where packet loss comes fromOutlinez ICMPz How do Routers Works?2020z Routingz Distance vectorIP Forwarding versus Routingz The Story So Far… » IP addresses are structure to reflect Internet structure» IP packet headers carry these addressesRouter2121» When Packet Arrives at Router– Examine header to determine intended destination– Look up in table to determine next hop in path– Send packet out appropriate portz How do we generate the forwarding table?Graph Modelz Represent each router as nodez Direct link between routers represented by edge» Symmetric links ⇒ undirected graphz Edge “cost” c(x,y) denotes measure of difficulty of using link» delay, $ cost, or congestion level2222z Task» Determine least cost path from every node to every other node– Path cost d(x,y) = sum of link costsAEFCDB23641113Routes from Node AAEFCD23641113Forwarding Table for ADest Cost Next HopA0AB4BC6E2323z Properties» Some set of shortest paths forms tree– Shortest path spanning tree» Solution not unique– E.g., A-E-F-C-D also has cost 7ABC6D7BE2EF5EWays to Compute Shortest Pathsz Centralized» Collect graph structure in one place» Use standard graph algorithm» Disseminate routing tables2424z Link-state» Every node collects complete graph structure» Each computes shortest paths from it» Each generates own routing tablez Distance-vector» No one has copy of graph» Nodes construct their own tables iteratively» Each sends information about its table to neighbors2/16/20085Outlinez ICMPz How do Routers Works?2525z Routingz Distance vectorDistance-Vector MethodEFCD2361113Initial Table for ADest Cost Next HopA0AB4BC ∞ –2626z Idea: At any time, have cost/next hop of best known path to destination» Use cost ∞ when no path is knownz Initially» Only have entries for directly connected nodesADB4D∞–E2EF6FDistance-Vector Updatexzyc(x,z)d(z,y)d(x y)2727z Update(x,y,z)d ← c(x,z) + d(z,y) # Cost of path from x


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

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

12 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?