15-744: Computer NetworkingForwarding and RoutersOutlineWhat Does a Router Look Like?Line CardsNetwork ProcessorSwitch Design IssuesSwitch BufferingLine Card InterconnectISLIPISLIP (cont.)What Limits Router Capacity?Multi-rack Routers Reduce Power DensityExamples of Multi-rack RoutersLimits to ScalingSlide 16QuestionIf Traffic is Uniform…Real Traffic is Not UniformTwo-stage Load-Balancing SwitchSlide 21Slide 22Static WDM SwitchingLinecard DataflowSlide 25Original IP Route LookupOriginal IP Route Lookup – ExampleCIDR RevisitedCIDR IllustrationCIDR ShortcomingsSlide 31Trie Using Sample DatabaseSpeeding up Prefix Match (P+98)Prefix TreeSlide 36Slide 37Slide 38Speeding up Prefix Match - AlternativesSlide 40Slide 41Techniques for Forwarding PacketsSource RoutingSlide 44Virtual Circuits/Tag SwitchingVirtual Circuits ExamplesVirtual CircuitsIP Datagrams on Virtual CircuitsSlide 49Summary: Addressing/Classification15-744: Computer NetworkingL-8 Routers2Forwarding and Routers•Forwarding•IP lookup•High-speed router architecture•Readings•[McK97] A Fast Switched Backplane for a Gigabit Switched Router•[KCY03] Scaling Internet Routers Using Optics•Know RIP/OSPF•Optional•[D+97] Small Forwarding Tables for Fast Routing Lookups•[BV01] Scalable Packet Classification3Outline•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 forwarding table to line cards•Some line cards maintain two forwarding tables to allow easy 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 set of 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.)12What Limits Router Capacity?Approximate power consumption per rackPower density is the limiting factor today13CrossbarLinecardsSwitchLinecardsMulti-rack Routers Reduce Power Density14Examples of Multi-rack RoutersAlcatel 7670 RSPJuniper TX8/T640TX8ChiaroAvici TSR15Limits to Scaling•Overall power is dominated by linecards•Sheer number•Optical WAN components•Per packet processing and buffering.•But power density is dominated by switch fabric16Multi-rack Routers Reduce Power DensitySwitchLinecardsLimit today ~2.5Tb/s Electronics Scheduler scales <2x every 18 months Opto-electronic conversion17Question•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.18If Traffic is Uniform…RInInInOutOutOutRRRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NRNR /NR /NR /R19Real Traffic is Not UniformRInInInOutOutOutRRRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NRNR /NR /NR /RRNR /NR /NR /RRNR /NR /NR /RRRR?20OutOutOutRRRR/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]21OutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NInInInRRRR/NR/NR/NR/NR/NR/NR/NR/NR/N33123333322OutOutOutRRRR/NR/NR/NR/NR/NR/NR/NR/NR/NInInInRRRR/NR/NR/NR/NR/NR/NR/NR/NR/N33123333323In 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/N24RWDM1NROutWDM1NWDM1NRR2RR421Linecard DataflowWDM1N2222222222221133111111111111R R3In11111111Outline•IP router design•IP route lookup•Variable prefix match algorithms•Alternative methods for packet forwarding2526Original 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 lookup27Original 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 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 network location information inside address – i.e., create a structured hierarchy28CIDR 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 with same prefix share same hop•Routing protocols carry prefix with destination network address•Longest prefix match for forwarding29CIDR 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/23Provider30CIDR 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
View Full Document
Unlocking...