cmu.eduNick Mckeown's paperNick Mckeown's paper The original version of this paper appears in Business Communication Review. WHITE PAPER:A Fast Switched Backplane for a Gigabit Switched Router by Nick McKeown (tel: 650/725-3641; fax: 650/725-6949; email: [email protected]) a professor of electrical engineering and computer science at Stanford University. He received his PhD from the University of California at Berkeley in 1995. From 1986-1989 he worked for Hewlett-Packard Labs, in their network and communications research group in Bristol, England. In spring 1995, he worked for Cisco Systems as an architect of the Cisco 12000 GSR router. Nick serves as an editor for the IEEE Transactions on Communications. He is the Robert Noyce Faculty Fellow at Stanford and recipient of a fellowship from the Alfred P. Sloan Foundation. Nick researches techniques for high-speed networks, including high-speed Internet routing and architectures for high-speed switches. More recently, he has worked on the analysis and design of cell-scheduling algorithms, memory architectures and the economics of the Internet. His research group is currently building the Tiny Tera; an all-CMOS Terabit-per-second network switch. Table of Contents1 Abstract2 The Architecture of Internet Routers3 Why We Need Switched Backplanes4 Switched Backplanes: An Overview4.1 Crossbar Switch4.2 Fixed- vs. Variable-Length Packets4.3 Input Queuing and Virtual Output Queuing4.4 Crossbar Scheduling Algorithms4.5 The iSLIP Algorithm5 Unicast Traffic: Performance Comparison6 Controlling Delay7 Supporting Multicast Traffic7.1 Scheduling Multicast Traffic7.2 ESLIP: Combining Unicast and Multicast8 Concluding Remarks9 References1 AbstractThere is a new trend in the architecture of high-performance Internet routers: congested, shared backplanes are being replaced by much faster switched backplanes that allow multiple packets to be transferred simultaneously. This paper explains why switched backplanes are needed now, and the technical problems that must be solved in their design. Although others are taking the same approach, we will focus, as an example, on the switched backplane developed for the Cisco 12000 GSR.This router's backplane can switch 16 ports simultaneously, each with a line rate of 2.4 Gbps. It uses a number of new technologies that enable a parallel, compact design, providing extremely high throughput for both unicast and multicast traffic. Integrated support for priorities on the backplane allows the router to provide distinguished qualities of service for multimedia applications.Top of Page2 The Architecture of Internet Routershttp://www-2.cs.cmu.edu/~srini/15-744/F02/readings/McK97.html (1 of 15) [9/18/2002 11:15:28 AM]Nick Mckeown's paper We begin by revisiting the general architecture of an IP router, as shown in a simplified form in Figure 1. Router functions can be separated into two types:1. Datapath Functions: operations that are performed on every datagram that passes through the router. These are most often implemented in special purpose hardware, and include the forwarding decision, the backplane and output link scheduling.2. Control Functions: operations that are performed relatively infrequently. These are invariably implemented in software and include the exchange of routing table information with neighboring routers, as well as system configuration and management.Therefore, when trying to improve the per-packet performance of a router, we naturally focus on the datapath functions. Let's take a closer look at the datapath functions, by tracing the typical path of a packet through an IP router: ● The Forwarding Decision: When a datagram arrives, its destination address is looked up in a forwarding table. If the address is found, a next-hop MAC address is appended to the front of the datagram, the time-to-live (TTL) field of the IP datagram header is decremented, and a new header checksum is calculated.● The Backplane: The datagram is then forwarded across the backplane to its outgoing port (or ports). While waiting its turn to be transferred across the backplane, the datagram may need to be queued: if insufficient queue space exists, the datagram may need to be dropped, or it may be used to replace other datagrams.● The Output-Link Scheduler: When it reaches the outgoing port, the datagram waits for its turn to be transmitted on the output link. In most routers today, the outgoing port maintains a single first-come-first-served (FIFO) queue and transmits datagrams in the order they arrive. More advanced routers distinguish datagrams into different flows, or priority classes, and carefully schedule the departure time of each datagram in order to meet specific quality of service guarantees.Over the years, particular router architectures have been selected on the basis of a number of factors, including cost, number of ports, required performance and currently available technology. While the detailed implementation of individual commercial routers have remained proprietary, all routers have evolved along similar lines. Moreover, at any one time, higher-performance routers have differed from lower-performance devices in similar ways.The first trend in router evolution has been to implement more of the datapath functions in hardware. Recent improvements in CMOS technology integration have made it possible to implement a larger number of functions in ASIC components, moving datapath functions that were once performed in software to special-purpose hardware. Increased integration doesn't merely enable the same functions to be performed at similar speed for a lower cost; with sufficient hardware, system performance can also be significantly improved.The second trend has been toward parallelism, either to achieve higher performance or to allow the use of lower-cost components. Third, and most important to our discussion here, there has been a trend away from the use of shared buses (also referred to as shared-memory backplanes). Buses that are shared between multiple functions can become congested, especially if the bus bandwidth doesn't match the aggregate data rate of the ports and CPU I/O, thus limiting the performance of the system.http://www-2.cs.cmu.edu/~srini/15-744/F02/readings/McK97.html (2 of 15) [9/18/2002 11:15:28 AM]Nick Mckeown's paper As shown in Figure 2(a), the earliest routers were built around a conventional computer architecture: a shared central bus, with a central CPU, memory and
View Full Document
Unlocking...