DOC PREVIEW
CMU CS 15744 - 08-routers

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

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

Unformatted text preview:

115-744: Computer NetworkingL-8 RoutersForwarding and Routers• Forwarding• IP lookupHi hdt hitt•High-speed router architecture• Readings• [McK97] A Fast Switched Backplane for a Gigabit Switched Router• [KCY03] Scaling Internet Routers Using Optics• Know RIP/OSPF2• Optional• [D+97] Small Forwarding Tables for Fast Routing Lookups• [BV01] Scalable Packet ClassificationOutline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding3What Does a Router Look Like?• Currently:• Network controllerLi d•Line cards• Switched backplane• In the past?• Workstation• Multiprocessor workstationLi d h d b4•Line cards + shared bus2Line Cards• Network interface cards• Provides parallel processing of packets• Fast path per-packet processing• Forwarding lookup (hardware/ASIC vs. software)5Network Processor• Runs routing protocol and downloads forwarding table to line cardsSli dititf ditbltll•Some line cards maintain two forwarding tables to allow easy switchover• Performs “slow” path processing• Handles ICMP error messages• Handles IP option processing6Switch Design Issues• Have N inputs and M outputs• Multiple packets for same output – output contention•Switch contentionswitch cannot support arbitrary set•Switch contention –switch cannot support arbitrary set of transfers• Crossbar•Bus• High clock/transfer rate needed for bus• Banyan net• Complex scheduling needed to avoid switch contentionSltibff kt h dd7•Solution –buffer packets where neededSwitch Buffering • Input buffering• Which inputs are processed each slot – schedule?•Head of line packets destined for busy output blocks other packetsHead of line packets destined for busy output blocks other packets• Output buffering• Output may receive multiple packets per slot• Need speedup proportional to # inputs• Internal buffering• Head of line blocking•Amount of buffering needed8•Amount of buffering needed3Line Card Interconnect• Virtual output buffering• Maintain per output buffer at inputSl h d fli bl ki bl•Solves head of line blocking problem• Each of MxN input buffer places bid for output • Crossbar connect• Challenge: map of bids to schedule for crossbar9ISLIP10ISLIP (cont.)11What Limits Router Capacity?1012Approximate power consumption per rack246810Power (kW)12021990 1993 1996 1999 2002 2003Power density is the limiting factor today4Multi-rack Routers Reduce Power DensityCrossbarLinecards13SwitchLinecardsExamples of Multi-rack RoutersAlcatel 7670 RSPJuniper TX8/T640TX8ChiaroAvici TSR14Limits to Scaling• Overall power is dominated by linecards• Sheer numberOti lWAN t•Optical WAN components• Per packet processing and buffering.• But power density is dominated by switch fabric15Multi-rack Routers Reduce Power Density16SwitchLinecardsLimit today ~2.5Tb/s¾ Electronics¾ Scheduler scales <2x every 18 months¾ Opto-electronic conversion5Question• Instead, can we use an optical fabric at 100Tb/s with 100% throughput?• Conventional answer: No• Need to reconfigure switch too often• 100% throughput requires complex electronic scheduler.17If Traffic is Uniform…In OutRRR/NR/NRIn OutRR/NR/NR/NR/NRNR/≤NR /≤NR /≤R18In OutRRR/NR/NR/NReal Traffic is Not UniformIn OutRRR/NR/NRNR /≤NR /≤NR /≤RRRIn OutRR/NR/NR/NR/NRNR/≤NR /≤NR /≤RR?19In OutRRR/NR/NR/NRNR /≤NR /≤NR /≤RROutRR/NR/NTwo-stage Load-Balancing SwitchIn OutRR/NR/NROutRR/NR/NR/NR/NIn OutRR/NR/NR/NR/NR20OutRR/NR/NR/NLoad-balancing stage Switching stageIn OutRR/NR/NR/NR100% throughput for weakly mixing, stochastic traffic[C.-S. Chang, Valiant]6OutRR/NInRR/N3133OutOutRR/NR/NR/NR/NR/NInInRR/NR/NR/NR/NR/N1221OutRR/NR/NR/NInRR/NR/NR/N3OutRR/NInRR/N1OutOutRR/NR/NR/NR/NR/NInInRR/NR/NR/NR/NR/N23322OutRR/NR/NR/NInRR/NR/NR/N33In OtStatic WDM SwitchingAABCDA, A, A, AOut In Out In Out Array WaveguideRouter(AWGR)Passive andAlmost ZeroBCA, B, C, DA, B, C, DA, B, C, DB, B, B, BC, C, C, CDDDD23In Out PowerDA, B, C, DD, D, D, D4 WDM channels, each at rate 2R/NLinecard DataflowWDMλ1λ1, λ2,.., λΝ222 2 2RRInWDMλ1WDMλ1λNRRλ1, λ2,.., λΝλ1, λ2,.., λΝ2RR21λN21311124RWDMλ1λNλ1, λ2,.., λΝROutWDMλN242111131 1 1 17Outline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding25Original IP Route Lookup• Address classes• A: 0 | 7 bit network | 24 bit host (16M each)B 10 | 14 bi k | 16 bi h (64K)•B: 10 | 14 bit network | 16 bit host (64K)• C: 110 | 21 bit network | 8 bit host (255)• Address would specify prefix for forwarding table• Simple lookup26Original IP Route Lookup – Example• www.cmu.edu address 128.2.11.43• Class B address – class + network is 128.2•Lookup 128.2 in forwarding tableLookup 128.2 in forwarding table• Prefix – part of address that really matters for routing• Forwarding table contains• List of class+network entries• A few fixed prefix lengths (8/16/24)• Large tables•2 Million class C networks27•2 Million class C networks• 32 bits does not give enough space encode network location information inside address – i.e., create a structured hierarchyCIDR Revisited• Supernets• Assign adjacent net addresses to same orgCl l ti (CIDR)•Classless routing (CIDR)• How does this help routing table?• Combine routing table entries whenever all nodes with same prefix share same hop• Routing protocols carry prefix with destination network address28• Longest prefix match for forwarding8CIDR IllustrationProvider is given 201.10.0.0/21201.10.0.0/22 201.10.4.0/24 201.10.5.0/24 201.10.6.0/23Provider29CIDR Shortcomings• Multi-homing• Customer selecting a new provider201.10.0.0/21Provider 1 Provider 230201.10.0.0/22201.10.4.0/24201.10.5.0/24 201.10.6.0/23 or Provider 2 addressOutline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding31Trie Using Sample DatabaseRoot• P1 = 10*Sample DatabaseTrie01P5 P401P100P60P200• P2 = 111*• P3 = 11001*• P4 = 1*• P5 = 0*P6 1000*132P7P80001P3•P6 = 1000*• P7 = 100000*• P8 = 1000000*9Speeding up Prefix Match (P+98)• Cut prefix tree at 16 bit depth • 64K bit maskBi 1 if i b l ( h d)•Bit = 1 if tree continues below cut (root head)• Bit = 1 if leaf at depth 16 or less (genuine head)• Bit = 0 if part of range covered by


View Full Document

CMU CS 15744 - 08-routers

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download 08-routers
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 08-routers 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 08-routers 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?