CS 268: Computer NetworkingL-8 Routers2Forwarding and Routers• Forwarding• IP lookup• High-speed router architecture• Readings• [McK97] A Fast Switched Backplane for a GigabitSwitched Router• [KCY03] Scaling Internet Routers Using Optics• Know RIP/OSPF3Outline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding4What Does a Router Look Like?• Currently:• Network controller• Line cards• Switched backplane• In the past?• Workstation• Multiprocessor workstation• Line cards + shared bus5Line Cards• Network interface cards• Provides parallel processing of packets• Fast path per-packet processing• Forwarding lookup (hardware/ASIC vs. software)6Network Processor• Runs routing protocol and downloads forwardingtable to line cards• Some line cards maintain two forwarding tables to alloweasy switchover• Performs “slow” path processing• Handles ICMP error messages• Handles IP option processing7Switch Design Issues• Have N inputs and M outputs• Multiple packets for same output – output contention• Switch contention – switch cannot support arbitrary setof transfers• Crossbar• Bus• High clock/transfer rate needed for bus• Banyan net• Complex scheduling needed to avoid switch contention• Solution – buffer packets where needed8Switch Buffering• Input buffering• Which inputs are processed each slot – schedule?• Head 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 needed9Line Card Interconnect• Virtual output buffering• Maintain per output buffer at input• Solves head of line blocking problem• Each of MxN input buffer places bid for output• Crossbar connect• Challenge: map of bids to schedule for crossbar10ISLIP11ISLIP (cont.)Thermal Image of TypicalCluster RackRackSwitchM. K. Patterson, A. Pratt, P. Kumar,“From UPS to Silicon: an end-to-end evaluation of datacenter efficiency”, Intel Corporation13What Limits Router Capacity?0246810121990 1993 1996 1999 2002 2003Power (kW)Approximate power consumption per rackPower density is the limiting factor todayFYI--Network Element Power• 96 x 1 Gbit port Cisco datacenter switch consumes around 15 kW -- equivalent to100x a typical dual processor Google server @ 145 W• High port density drives network element design, but such high power density makesit difficult to tightly pack them with servers• Is an alternative distributed processing/communications topology possible?Power/Cooling Issues16CrossbarLinecardsSwitchLinecardsMulti-rack Routers Reduce Power Density17Examples of Multi-rack RoutersAlcatel 7670 RSPJuniper TX8/T640TX8ChiaroAvici TSR18Limits to Scaling• Overall power is dominated by linecards• Sheer number• Optical WAN components• Per packet processing and buffering.• But power densit y is dominated by switch fabric19Multi-rack Routers Reduce Power DensitySwitchLinecardsLimit today ~2.5Tb/s Electronics Scheduler scales <2x every 18 months Opto-electronic conversion20Question• Instead, can we use an optical fabric at100Tb/s with 100% throughput?• Conventional answer: No• Need to reconfigure switch too often• 100% throughput requires complex electronicscheduler.21If Traffic is Uniform…RInInInOutOutOutRRRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NRNR /!NR /!NR /!R22Real Traffic is Not UniformRInInInOutOutOutRRRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NRNR /!NR /!NR /!RRNR /!NR /!NR /!RRNR /!NR /!NR /!RRRR?23OutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NTwo-stage Load-Balancing SwitchLoad-balancing stage Switching stageInInInOutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NRRR100% throughput for weakly mixing, stochastic traffic[C.-S. Chang, Valiant]24OutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NInInInRRRR/NR/NR/NR/NR/NR/NR/NR/NR/N31233325OutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NInInInRRRR/NR/NR/NR/NR/NR/NR/NR/NR/N31233326In Out In Out In Out In Out Static WDM SwitchingArray WaveguideRouter(AWGR)Passive andAlmost ZeroPowerABCDA, B, C, DA, B, C, DA, B, C, DA, B, C, DA, A, A, AB, B, B, BC, C, C, CD, D, D, D4 WDM channels,each at rate 2R/N27RWDMλ1λNλ1, λ2,.., λΝROutWDMλ1λNWDMλ1λNRRλ1, λ2,.., λΝλ1, λ2,.., λΝ2RR421Linecard DataflowWDMλ1λNλ1, λ2,.., λΝ2222 2 2131111111R R3In1 1 1 1Outline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding2829Original IP Route Lookup• Address classes• A: 0 | 7 bit network | 24 bit host (16M each)• 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 lookup30Original IP Route Lookup – Example• www.berkeley.edu address 128.32.136.12• Class B address – class + network is 128.32• Lookup 128.32 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 networks• 32 bits does not give enough space encode networklocation information inside address – i.e., create astructured hierarchy31CIDR Revisited• Supernets• Assign adjacent net addresses to same org• Classless routing (CIDR)• How does this help routing table?• Combine routing table entries whenever all nodes withsame prefix share same hop• Routing protocols carry prefix with destination networkaddress• Longest prefix match for forwarding32CIDR 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/23Provider33CIDR Shortcomings• Multi-homing• Customer selecting a new provider201.10.0.0/21201.10.0.0/22201.10.4.0/24201.10.5.0/24 201.10.6.0/23 or Provider 2 addressProvider 1 Provider 2Outline• IP router design• IP route lookup• Variable prefix match algorithms• Alternative methods for packet forwarding3435 Trie Using Sample Database0 1RootP5 P40 1P100P6P7P8000P2001P3• P1 = 10*• P2 = 111*• P3 = 11001*• P4 = 1*• P5 = 0*• P6 = 1000*• P7 = 100000*• P8 = 1000000*Sample DatabaseTrie136How To Do Variable Prefix Match128.2/16101619128.32/16128.32.130/240 128.32.150/24default0/00• Traditional method – Patricia Tree• Arrange route entries into a series of bit
View Full Document
Unlocking...