Transcript Slide 1
Internet Routers Past, Present and Future Nick McKeown Stanford University British Computer Society June 2006 Outline What is an Internet router? The early days: Modified computers What limits performance: Memory access time Programmable against uncertainty The middle years: Specialized for performance Needed new architectures, theory, and practice So how did we do? Now: Internet showing its age Simple model breaking down The future: Simplify (again) or move over © Nick McKeown 2006 Ada Lovelace 001100 011001 110101 11011 http://www.adalovelace.com http://www.adalovelace.com Ada Lovelace © Nick McKeown 2006 Routers process heads Data Head © Nick McKeown 2006 Head Definitions N 1 … 2 3 R … … 4 5 8 6 7 N = number of linecards. Typically 8-32 per chassis R = line-rate. 1Gb/s, 2.5Gb/s, 10Gb/s, 40Gb/s, 100Gb/s Capacity of router = N x R © Nick McKeown 2006 Data Header 01000111100010101001110100011001 1. Internet Address 2. Age 3. Checksum to protect header © Nick McKeown 2006 Lookup internet address Check and update checksum Check and update age © Nick McKeown 2006 Barebones Router Router Control and Management © Nick McKeown 2006 Barebones Router © Nick McKeown 2006 Barebones Router © Nick McKeown 2006 Bottlenecks Memory, memory, … 1 © Nick McKeown 2006 2 DRAM as bottleneck DRAM then DRAM now d Address Data d Address Data DRAMs designed to maximize number of bytes d has stayed constant (yield) d determines access time (capacitance) a Access time (“speed”) has stayed constant © Nick McKeown 2006 Outline What is an Internet router? The early days: Modified computers What limits performance: Memory access time Programmable against uncertainty The middle years: Specialized for performance Needed new architectures, theory, and practice So how did we do? The present: Internet showing its age Simple model breaking down The future: Simplify or move over © Nick McKeown 2006 Early days: Modified Computer Must run at rate N x R R R R R R R R R Bottlenecks © Nick McKeown 2006 2nd Generation Router R R R R © Nick McKeown 2006 Early days: Modified Computer • Function more important than speed • 1993 (WWW) changed everything • We badly needed – Some new architecture – Some theory – Some practice © Nick McKeown 2006 3rd Generation Router: Switch NxR © Nick McKeown 2006 © Nick McKeown 2006 1xR Arbiter © Nick McKeown 2006 Arbiter Arbiter Arbiter Arbiter Arbiter Arbiter Arbiter Arbiter © Nick McKeown 2006 Developed at Abrizio Inc. Arbiter 4th Generation Router Multirack; optics inside Optical links 100s of metres Linecards © Nick McKeown 2006 Switch More 4th Generation Routers Alcatel 7670 RSP Juniper TX8/T640 TX8 Avici TSR © Nick McKeown 2006 Cisco CRS-1 Power consumption per chassis 16 14 Power (kW) 12 10 8 6 4 2 0 1990 1993 1996 1999 2002 2003 2004 © Nick McKeown 2006 5th Generation routers? Load-balancing over passive optics © Nick McKeown 2006 5th Generation routers? Load-balancing over passive optics Zero-power switching Passive No arbiter Optical Guaranteed performance Switch (AWGR) Electronic processing at R a Very scalable. Petabits? © Nick McKeown 2006 Examples of Router Theory 1. 2. 3. There’s something special about “2” Making fast queues How big should the queue be? © Nick McKeown 2006 Case 1: Placing calls Crosspoint switch Permutation 1 1 1 1 D 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 0 0 0 1 1 0 0 0 0 0 0 11 0 A crosspoint switch supports all permutations So it is “non-blocking” 2 But it needs N crosspoints © Nick McKeown 2006 Case 1: Placing Calls Uncertainty costs 1 10 0 0 1 1 0 0 0 0 0 0 0 0 01 1 0 0 0 0 0 0 0 0 0 0 0 0 © Nick McKeown 2006 0 0 0 11 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 If I give you the permutation, you can route it. If I give you entries one at a time, you can’t. Clos (1950s): But if you make it run 2 times faster you can route calls one at a time. Case 2: Mimicking NxR © Nick McKeown 2006 Case 2: Mimicking 1xR © Nick McKeown 2006 Are they equivalent? NR No. R © Nick McKeown 2006 Case 2: Mimicking 1xR © Nick McKeown 2006 ?xR Algorithm Now are they equivalent? NR Yes, if it runs 2 times faster. R 2R Algorithm © Nick McKeown 2006 Case 3: Are they equivalent? Yes, if it runs 2 times faster. © Nick McKeown 2006 Case 4: Routing packets with uncertainty R 1 Rates 0.1 0.3 0.5 0.1 0.2 0.1 0.2 0.5 0.5 0.3 0.1 0.1 © Nick McKeown 2006 0.2 0.3 0.2 0.3 Algorithm If you know the rates, you can find a sequence of permutations: = 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 But we don’t know the rates (they are always changing) Case 4: Routing packets with uncertainty 2 3 © Nick McKeown 2006 If you choose the permutations one at a time, and you can spend as long as you want choosing, then you can support any pattern of rates. But if you have to make decisions one at a time, then the switch has to run 2 times faster. Case 5: Load-balancing Load-balancing to support all rate matrices: – Requires the network to run 2 times faster Case 6: Local versus global decisions Local (“selfish”) routing decisions: – Cost twice as much as global decisions © Nick McKeown 2006 Examples of Router Theory 1. 2. 3. There’s something special about “2” Making fast queues How big should the queue be? © Nick McKeown 2006 Fast Queues 1 Cheap and plentiful Too slow 2 Fast enough 50x as expensive Network industry buys over $500M of SRAMs per year. Computer industry has its own solution: Cache in SRAM, Store in DRAM But networking can’t tolerate a “miss-rate” © Nick McKeown 2006 Fast Queues 3 Fast as SRAM Big as DRAM Never misses 1 Q SRAM size: Qbln Q © Nick McKeown 2006 Developed as “Network Memory” by Nemo Systems Examples of Router Theory 1. 2. 3. There’s something special about “2” Making fast queues How big should the queue be? © Nick McKeown 2006 How big should the queue be? ? © Nick McKeown 2006 Packet delay = T ? R Rule of thumb: Queue needs to hold 2T x R packets © Nick McKeown 2006 How big should the queue be? The story so far # packets at 10Gb/s 1,000,000 10,000 20 2T R 2T R O(20) n Where © Nick McKeown 2006 n = number of flows passing through router Outline What is an Internet router? The early days: Modified computers Needed new architectures, theory, and practice So how did we do? The present: Internet showing its age Programmable against uncertainty The middle years: Specialized for performance What limits performance: Memory access time Simple model breaking down The future: Simplify or move over © Nick McKeown 2006 What to expect Link speeds followed Moore’s Law User demand doubled every year Router capacity limited by memory speed DRAM is no faster now than 10 years ago a Routers should have fallen behind © Nick McKeown 2006 Backbone router capacity Followed Moore’s Law 1Tb/s 100Gb/s 10Gb/s Router capacity per chassis doubled every 18 months 1Gb/s 1986 © Nick McKeown 2006 1988 1990 1992 1994 1996 1998 2000 2002 2004 Outline What is an Internet router? The early days: Modified computers What limits performance: Memory access time Programmable against uncertainty The middle years: Specialized for performance Needed new architectures, theory, and practice So how did we do? The present: Internet showing its age Simple model breaking down The future: Simplify or move over © Nick McKeown 2006 What’s happened since End of the Internet end-to-end model + Uncertainty + Lack of competition a Explosion of complexity in routers IPv6, multicast, ACLs, firewall, virtual routing, MPLS, Diffserv, IntServ, RSVP, ATM, IP Tunnels, IPSec, VPNs, Virtual routing, Calea, … a Power-hungry, expensive, unreliable © Nick McKeown 2006 Packet processing gets harder Operations per arriving packet What we’d like (more features) What we can do if 1. We’re lucky 2. Line-rates don’t exceed 3. We ignore power Moore’s Law More likely… 1997 © Nick McKeown 2006 2001 time Outline What is an Internet router? The early days: Modified computers What limits performance: Memory access time Programmable against uncertainty The middle years: Specialized for performance Needed new architectures, theory, and practice So how did we do? The present: Internet showing its age Simple model breaking down The future: Simplify or move over © Nick McKeown 2006 Prediction Increased need for dependability & reliability of the whole network © Nick McKeown 2006 Unfashionable Predictions In 10 years, big routers will be much simpler Fewer features Much smaller queues (Prevailing wisdom is that they will become more complex with big queues) © Nick McKeown 2006 Current network operators Grossly over-provisioned Hard to predict traffic now Harder to predict traffic growth Resilience against failure of routers and links Over-provision by 50% to protect against 2% failures Customers hate delay and delay variation Current usage less than 10% No network provider makes profit from public Internet service Subsidised by voice (especially mobile) and VPNs © Nick McKeown 2006 Trends in networks • Consolidation of (i.e. reduction in) number of network providers – Does it converge on competition or monopoly? • Emerging structure around population centres – One regional centre per 5-10 million people – UK: 5-10 centres – USA: 30-50 centres • Increased “meshing” and load-balancing © Nick McKeown 2006 Current Structure Reproduced with permission of Bill Cheswick, Lumeta Inc © Nick McKeown 2006 Emerging Structure © Nick McKeown 2006 Can we exploit emerging structure and consolidation to make networks simpler, more dependable and even profitable? Valiant Load-Balancing © Nick McKeown 2006 Valiant Load-Balancing Operates over logical mesh of optical circuits Supports all traffic patterns No need to over-provision against uncertainty Resilient against failure Network can be designed for any amount of resilience Over-provision by 5% to provably protect against 5% failures (1:1 instead of 20:1) Simple Routing Cost Can be used close to 100% load Less expensive than today’s network © Nick McKeown 2006 Unfashionable Predictions In 10 years, we will be close to a monopoly. (Get over it) In 15 years, flow-by-flow load-balancing will be common. © Nick McKeown 2006 What about optical routers? Prevailing wisdom “A router must... 1. Process headers, 2. Switch packet-by-packet, and 3. Buffer packets during times of congestion. Optics suck at all three.” Emerging possibilities 1. 2. 3. Process headers: Carry headers slower; process electronically. Switch packets: Valiant Load Balancing means no packet-by-packet sw Buffer packets: 20-50 packets might be enough in the backbone DARPA DOD-N Program (LASOR and IRIS Projects) © Nick McKeown 2006 Integrated optical buffers Think: 10-50 packets on a chip © Nick McKeown 2006 [Burmeister and Bowers, UCSB] Unfashionable Predictions In 15 years, optical routers will be possible (Not ready to predict that they will be necessary) © Nick McKeown 2006 Unfashionable Predictions In 10 years, big routers will be much simpler Fewer features Much smaller queues …and they will have to compete with optical dynamic circuit switches (DCS) © Nick McKeown 2006 Structure of switching centers © Nick McKeown 2006 Circuit switches control the topology SONET/SDH, DWDM © Nick McKeown 2006 Conventional Wisdom Circuit switching finally eliminated? © Nick McKeown 2006 Circuit Switches Advantages of circuit switches – Well-suited to optics – Circuit switches are simple “Start with a packet switch and throw 90% of it away” – – – – Higher capacity per unit volume Higher capacity per watt Lower cost per Gb/s No queues, no delay variation Disadvantages – They are unfashionable © Nick McKeown 2006 DCS: Capacity on demand between border routers © Nick McKeown 2006 © Nick McKeown 2006 Unfashionable Predictions In 15 years, fast dynamic circuit switches will be common Will big routers be something of the past….? © Nick McKeown 2006 Thank you!