Also, like all data networks, large private networks have control algorithms for managing network traffic during periods of congestion. But because the routers that direct traffic in a server farm have to be extremely fast, the control algorithms are hard-wired into the routers' circuitry. This means that if someone develops a better algorithm, network operators have to wait for a new generation of hardware before they can incorporate such an improvement.
Researchers at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) and five other organizations hope to change that with routers that are programmable but can keep up with the breakneck speeds of modern data networks.
“This work demonstrates that many flexible traffic management goals can be achieved while preserving the high performance of traditional routers,” says Hari Balakrishnan, the Fujitsu Professor in the Department of Electrical Engineering and Computer Science at MIT. “Previously, programmability was achievable, but no one used it in production because it was a factor of 10 or even 100 times slower.”
“You need the ability of researchers and engineers to test thousands of ideas,” he adds. “With this platform, you become limited not by hardware or technological constraints, but by your creativity. You can innovate much more rapidly.”
The first author of the paper is Anirudh Sivaraman, an MIT graduate student in electrical engineering and equipment science, advised by Balakrishnan and Mohammad Alizadeh, the TIBCO Assistant Professor of Career Development in Electrical Engineering and Computer Science at MIT, who are co-authors of the papers on the work. They are joined by collaborators from MIT, the University of Washington, Barefoot Networks, Microsoft Research, Stanford University, and Cisco Systems.
Different Impacts:
Traffic management can be complicated due to the different types of data that travel across a network and the different performance guarantees offered by various services. With internet phone calls, for example, delays are a nuisance, but occasional dropped data packets (which might translate to a missing word in a sentence) could be tolerable. With a large data file, on the other hand, a slight delay might be tolerable, but dropped data is not.
Similarly, a network can guarantee equal bandwidth distribution among its users. Each router in a data network has its own memory bank, called a buffer, where packets can be queued. If one user has filled a router's buffer with packets from a single high-definition video, and another is trying to download a comparatively small text document, the network might want to dump some of the video packets in favor of the text to help guarantee users a minimum data rate.
A router might also want to modify a packet to transmit information about network conditions, such as whether the packet has encountered congestion, where, and for how long; it might even want to suggest new transmission speeds to senders.
Computer scientists have proposed hundreds of traffic management schemes with complex rules for determining which packets a router should accept and which to drop, in what order packets should be queued, and what additional information to add—all under a variety of different circumstances. And while simulations of many of these schemes promise improved network performance, some have not been deployed due to hardware limitations in routers.
MIT researchers and their collaborators set out to find a set of simple computational elements that could be arranged to implement diverse traffic management schemes without compromising the operating speeds of today's best routers and without taking up too much on-chip space.
To test their designs, they built a compiler—a program that translates high-level program instructions into low-level hardware instructions—which they used to compile seven experimental traffic management algorithms into their proposed circuit elements. If an algorithm failed to compile, or if it required an impractical number of circuits, they would add new, more sophisticated circuit elements to its palette.
Evaluations
In one of the two new papers, the researchers provide specifications for seven types of circuits, each slightly more complex than the last. Some simple traffic management algorithms require only one type of circuit, while others require more complex types. But even a bank of the most complex circuits would use only 4 percent of a router chip's surface area; a bank of the less complex types would use only 0.16 percent.
Beyond the seven algorithms used to design their circuit elements, the researchers ran several algorithms through their compiler and found that they compiled into some combination of their simple circuit elements.
"We think they're going to generalize to many more," says Sivaraman. "For example, one of the circuits allows a programmer to keep track of a running sum, which is used by many algorithms."
In the second paper, they describe the design of their scheduler, a circuit element that sorts packets in the router's queue and extracts them for forwarding. In addition to queuing packets according to their priority, the scheduler can also mark them with specific transmission times and forward them accordingly. Sometimes, for example, it might be useful for a router to slow its transmission rate in order to avoid network bottlenecks elsewhere or to help ensure an equitable distribution of bandwidth.
Finally, the researchers developed the specifications for their circuits in Verilog, the language electrical engineers often use to design commercial chips. Verilog embedded in the analysis tools verified that a router using the researchers' circuits would be fast enough to support the packet rates common in today's high-speed networks—transmitting a data packet every nanosecond.
###
Written by Larry Hardesty, MIT
