Router DesignToday’s LectureWhat’s In A RouterWhat a Router Chassis Looks LikeWhat a Router Line Card Looks LikeBig, Fast Routers: Why Bother?Summary of Routing FunctionalityGeneric Router ArchitectureInnovation #1: Each Line Card Has the Routing TablesSlide 10First Generation RoutersSecond Generation RoutersSlide 13Innovation #2: Switched BackplaneHead-of-Line BlockingSpeedupCombined Input-Output QueuingSolution: Virtual Output QueuesRouter Components and FunctionsCrossbar SwitchingEarly Crossbar Scheduling AlgorithmAlternatives to the Wavefront SchedulerProcessing: Fast Path vs. Slow PathRecent Trends: ProgrammabilityScheduling and FairnessMax-Min FairnessExampleHow to Achieve Max-Min FairnessWhy QoS?IP Address LookupIP Lookups find Longest PrefixesSlide 32Address Tables are LargeSlide 34Lookups Must be FastIP Address Lookup: Binary TriesIP Address Lookup: Patricia TrieAddress Lookup: Direct TrieFaster LPM: AlternativesFaster Lookup: AlternativesIP Address Lookup: SummaryFourth-Generation: Collapse the POPFourth-Generation RoutersMulti-rack routersFuture: 100Tb/s Optical RouterChallenges with Optical SwitchingRouter Design(Nick Feamster)February 11, 20082Today’s Lecture•The design of big, fast routers•Partridge et al., A 50 Gb/s IP Router•Design constraints–Speed–Size–Power consumption•Components•Algorithms–Lookups and packet processing (classification, etc.)–Packet queuing–Switch arbitration3What’s In A Router•Interfaces–Input/output of packets•Switching fabric–Moving packets from input to output•Software–Routing–Packet processing–Scheduling–Etc.4What a Router Chassis Looks LikeCisco CRS-1 Juniper M3206ft19”2ftCapacity: 1.2Tb/s Power: 10.4kWWeight: 0.5 TonCost: $500k3ft2ft17”Capacity: 320 Gb/s Power: 3.1kW5What a Router Line Card Looks Like1-Port OC48 (2.5 Gb/s)(for Juniper M40)4-Port 10 GigE(for Cisco CRS-1)Power: about 150 Watts21in2in10in6Big, Fast Routers: Why Bother?•Faster link bandwidths•Increasing demands•Larger network size (hosts, routers, users)7Summary of Routing Functionality•Router gets packet•Looks at packet header for destination•Looks up routing table for output interface•Modifies header (TTL, IP header checksum)•Passes packet to output interface8Generic Router ArchitectureLookupIP AddressUpdateHeaderHeader ProcessingData Hdr Data Hdr1M prefixesOff-chip DRAMAddressTableAddressTableIP Address Next HopQueuePacketBufferMemoryBufferMemory1M packetsOff-chip DRAMQuestion: What is the difference between this architecture and that in today’s paper?9Innovation #1: Each Line Card Has the Routing Tables•Prevents central table from becoming a bottleneck at high speeds•Complication: Must update forwarding tables on the fly. –How does the BBN router update tables without slowing the forwarding engines?10Generic Router ArchitectureLookupIP AddressUpdateHeaderHeader ProcessingAddressTableAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableAddressTableData HdrData HdrData HdrBufferManagerBufferMemoryBufferMemoryBufferManagerBufferMemoryBufferMemoryBufferManagerBufferMemoryBufferMemoryData HdrData HdrData HdrInterconnection Fabric11RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically <0.5Gb/s aggregate capacityShared BusLine InterfaceCPUMemoryFirst Generation RoutersOff-chip Buffer12RouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemoryTypically <5Gb/s aggregate capacitySecond Generation Routers13Third Generation RoutersLineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemory“Crossbar”: Switched BackplaneLine InterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically <50Gb/s aggregate capacity14Innovation #2: Switched Backplane•Every input port has a connection to every output port•During each timeslot, each input connected to zero or one outputs•Advantage: Exploits parallelism•Disadvantage: Need scheduling algorithm15Head-of-Line BlockingOutput 1Output 2Output 3Input 1Input 2Input 3Problem: The packet at the front of the queue experiences contention for the output queue, blocking all packets behind it.Maximum throughput in such a switch: 2 – sqrt(2)M.J. Karol, M. G. Hluchyj, and S. P. Morgan, “Input Versus Output Queuing on a Space-Division Packet Switch,” IEEE Transactions On Communications, Vol. Com-35, No. 12, December 1987, pp. 1347-1356.16Speedup•What if the crossbar could have a “speedup”?Key result: Given a crossbar with 2x speedup, any maximal matching can achieve 100% throughput. S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakarm, “Matching Output Queueing with a Combined Input Output Queued Switch”, Proceedings of INFOCOM,1998.I.e., does as well as a switch with Nx speedup.17Combined Input-Output Queuing•Advantages–Easy to build•100% can be achieved with limited speedup•Disadvantages–Harder to design algorithms•Two congestion points•Flow control at destinationinput interfaces output interfacesCrossbar18Solution: Virtual Output Queues•Maintain N virtual queues at each input– one per output Output 1Output 2Output 3Input 1Input 2Input 3N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch,” IEEE Transactions on Communications, Vol. 47, No. 8, August 1999, pp. 1260-1267.19Router Components and Functions•Route processor–Routing–Installing forwarding tables–Management•Line cards–Packet processing and classification–Packet forwarding•Switched bus (“Crossbar”)–Scheduling20Crossbar Switching•Conceptually: N inputs, N outputs–Actually, inputs are also outputs•In each timeslot, one-to-one mapping between inputs and outputs.•Goal: Maximal matchingL11(n)LN1(n)Traffic Demands Bipartite MatchMaximumWeight Match*( )( ) arg max( ( ) ( ))TS nS n L n S n 21Early Crossbar Scheduling Algorithm•Wavefront algorithmProblems: Fairness, speed, …22Alternatives to the Wavefront Scheduler•PIM: Parallel Iterative Matching–Request: Each input sends requests to all outputs for which it has packets–Grant: Output selects an input at random and grants–Accept: Input selects from its received grants•Problem: Matching may not be maximal•Solution: Run several times•Problem: Matching may not be “fair”•Solution: Grant/accept in round robin instead of