MIT Research News' Journal

Programmable network routers

Like all data networks, the networks that connect servers in giant server farms, or servers and workstations in large organizations, are prone to congestion. When network traffic is heavy, packets of data can get backed up at network routers or dropped altogether.

Also like all data networks, big private networks have control algorithms for managing network traffic during periods of congestion. But because the routers that direct traffic in a server farm need to be superfast, the control algorithms are hardwired into the routers’ circuitry. That means that if someone develops a better algorithm, network operators have to wait for a new generation of hardware before they can take advantage of it.

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 still keep up with the blazing speeds of modern data networks. The researchers outline their system in a pair of papers being presented at the annual conference of the Association for Computing Machinery’s Special Interest Group on Data Communication.

“This work shows that you can achieve many flexible goals for managing traffic, while retaining the high performance of traditional routers,” says Hari Balakrishnan, the Fujitsu Professor in Electrical Engineering and Computer Science at MIT. “Previously, programmability was achievable, but nobody would use it in production, because it was a factor of 10 or even 100 slower.”

“You need to have the ability for researchers and engineers to try out thousands of ideas,” he adds. “With this platform, you become constrained not by hardware or technological limitations, but by your creativity. You can innovate much more rapidly.”

The first author on both papers is Anirudh Sivaraman, an MIT graduate student in electrical engineering and computer science, advised by both Balakrishnan and Mohammad Alizadeh, the TIBCO Career Development Assistant Professor in Electrical Engineering and Computer Science at MIT, who are coauthors on both papers. They’re joined by colleagues from MIT, the University of Washington, Barefoot Networks, Microsoft Research, Stanford University, and Cisco Systems.

Different strokes

Traffic management can get tricky because of the different types of data traveling over a network, and the different types of performance guarantees offered by different services. With Internet phone calls, for instance, delays are a nuisance, but the occasional dropped packet — 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 could be tolerable, but missing data isn’t.

Similarly, a network may guarantee equal bandwidth distribution among its users. Every router in a data network has its own memory bank, called a buffer, where it can queue up packets. 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 tiny text document, the network might want to bump some of the video packets in favor of the text, to help guarantee both users a minimum data rate.

A router might also want to modify a packet to convey information about network conditions, such as whether the packet encountered congestion, where, and for how long; it might even want to suggest new transmission rates for senders.

Computer scientists have proposed hundreds of traffic management schemes involving complex rules for determining which packets to admit to a router and which to drop, in what order to queue the packets, and what additional information to add to them — all under a variety of different circumstances. And while in simulations many of these schemes promise improved network performance, few of them have ever been deployed, because of hardware constraints in routers.

The MIT researchers and their colleagues set themselves the goal of finding a set of simple computing 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 space on-chip.

To test their designs, they built a compiler — a program that converts high-level program instructions into low-level hardware instructions — which they used to compile seven experimental traffic-management algorithms onto their proposed circuit elements. If an algorithm wouldn’t compile, or if it required an impractically large number of circuits, they would add new, more sophisticated circuit elements to their palette.

Assessments

In one of the two new papers, the researchers provide specifications for seven circuit types, each of which is slightly more complex than the last. Some simple traffic management algorithms require only the simplest circuit type, while others require more complex types. But even a bank of the most complex circuits would take up only 4 percent of the area of a router chip; a bank of the least complex types would take up only 0.16 percent.

Beyond the seven algorithms they used to design their circuit elements, the researchers ran several other algorithms through their compiler and found that they compiled to some combination of their simple circuit elements.

“We believe that they’ll generalize to many more,” says Sivaraman. “For instance, one of the circuits allows a programmer to track a running sum — something that is employed by many algorithms.”

In the second paper, they describe the design of their scheduler, the circuit element that orders packets in the router’s queue and extracts them for forwarding. In addition to queuing packets according to priority, the scheduler can also stamp them with particular transmission times and forward them accordingly. Sometimes, for instance, it could be useful for a router to slow down its transmission rate, in order to prevent bottlenecks elsewhere in the network, or to help ensure equitable bandwidth distribution.

Finally, the researchers drew up specifications for their circuits in Verilog, the language electrical engineers typically use to design commercial chips. Verilog’s built-in analytic 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, forwarding a packet of data every nanosecond.

“There are a lot of problems in computer networking we’ve never been able to solve at the speed that traffic actually flows through the network, because there wasn’t support directly in the network devices to analyze the traffic or act on the traffic as it arrives,” says Jennifer Rexford, a professor of computer science at Princeton University. “What’s exciting about both of these works is that they really point to next-generation switch hardware that will be much, much more capable — and more importantly, more programmable, so that we can really change how the network functions without having to replace the equipment inside the network.”

“At the edge of the network, applications change all the time,” she adds. “Who knew Pokémon Go was going to happen? It’s incredibly frustrating when applications’ needs evolve years and years more quickly than the equipment’s ability to support it. Getting the time scale of innovation inside the network to be closer to the time scale of innovation in applications is, I think, quite important.”

Family and friends recall Drew Esquivel

At a memorial service for Drew Esquivel in California, a family friend described a photo that reflected the rising MIT senior’s joyful, adventurous spirit.

Drew and his friends were jumping off some boulders into a pool, all “getting some good air,” according to Steve Vargas, whose family has been close to Drew’s for many years. High above the others, arms outstretched as if shouting “Cowabunga!,” soared Drew.

“He was a go-for-it guy,” Vargas said. “He’d say, ‘Let’s get going.’ ‘I’ll go first.’ ‘We can DO this!’ Drew also had the ability to move others to action and used that wisely to accomplish great things. … We all know he was fiercely competitive, yet he encouraged the success of others and found joy in it.”

Drew Esquivel died on July 16, killed by an alleged drunk driver in Brooklyn, New York. Rising MIT junior Sophia Tabchouri, alum James Balchunas '14, and a third friend, Divya Menezes, were all seriously injured.

On campus at MIT and at the California memorial service in July, which drew hundreds of people from across the country, those who knew Drew recalled a gifted, fun-loving, and compassionate young man, who shared tight bonds with his family and friends.

An “energetic, curious, engaged” student

A native of Healdsburg, California, Drew was majoring in electrical engineering and computer science. He had been living in New York for the summer, working at an internship with the mobile marketing firm Appboy.

MIT faculty knew him as a strong student who connected easily with others, in classes, campus life, and on the wrestling club, of which he was an officer and respected leader.

“His smiling face and gentle manner is imprinted in my mind,” says Arvind, the Johnson Professor of Computer Science and Engineering at MIT and Drew’s academic advisor. “We used to meet to discuss his course registration every term, and he would tell me what was going on his life. I knew he was keen on wrestling but he did not quite fit my naive model of a wrestler, who I thought ought to look more menacing.”

Hari Balakrishnan, the Fujitsu Professor in Electrical Engineering and Computer Science, got to know Drew well while teaching him in Course 6.S062 (Mobile and Sensor Computing), a small class co-taught with Professor Sam Madden, that involved programming for iPhones in XCode.

“Drew was a pleasure to talk to and interact with, both in class and during our project meetings through the term,” says Balakrishnan. “He was energetic, curious, engaged. A great team player. Not only smart technically, but he also had the ability to collaborate well with others and communicate ideas well.”

In Balakrishnan’s course, Drew’s group developed a location-based, gesture-encrypted messaging application that allowed users to send each other targeted messages based on their locations.

Drew also participated in the Undergraduate Research Opportunities Program (UROP) in the Laboratory for Computational Physiology, where he worked on developing electronic medical record systems for underserved areas.

In high school, Drew attended the distinguished Summer Science Program in New Mexico. When selected for the prestigious scholarship that would give him a full ride to MIT, Drew told the Healdsburg Tribune, “I have been thinking of college since second grade. I always had a dream school in mind and that made it easy to focus on school.”

Athlete and adventurer

A member of MIT’s wrestling club, Drew was named most valuable player in 2015 and rookie of the year in 2014. He was team captain, a three-time National Collegiate Wrestling Association (NCWA) national qualifier, and a NCWA Northeast conference finalist.

In high school, Drew was a varsity swimmer as well as wrestler, and he ran cross-country. He was an Eagle Scout who completed 50-mile hikes with his troop in the High Sierras, and he adventured in the California outdoors with his family and their friends, backpacking, kayaking, and skiing.

Drew’s adventurous spirit and strong work ethic led him to scale many summits, both literal and figurative, says his mother, Susanne Esquivel. “He always ‘bagged the peak,’ thought outside the box to solve problems, strove to be the best, found joy in helping others, put family and friends first, and had fun,” she says.

Forging bonds at MIT

Drew was very “deliberate” about where he applied to college, according to Susanne Esquivel, who says he was “really only interested in Stanford or MIT.” He was offered early admission to Stanford, in his home state, but he had also applied for and received a James Family Foundation scholarship, available at the time to a student at his high school, which provided full tuition to a highly competitive, out-of-state school.

So, Drew attended MIT’s Campus Preview Weekend and returned “excited and firmly committed to MIT,” Susanne says: “He felt he had found the right environment for learning, competing, and making life-long friends. He was right. He received the best education in the world and took advantage of amazing opportunities and making a difference.”

On campus, Drew became very close with his friends, including his fraternity brothers at Lambda Chi Alpha.

“I remember meeting Drew at a fraternity event in the fall of 2013. I noticed immediately how lively and happy he was to be there meeting all these new people — his energy was infectious,” said rising senior Zak Psaras, in a eulogy at the memorial service.

“As quickly as he bonded with the world around him, he bonded with the city and each of us,” Psaras said, reminiscing about the tight-knit group of friends he and Drew were part of.

“Drew knew how to make everyone laugh and would go out of his way to make others feel included, Psaras said. “He never failed to see the good in others. For as comical as Drew was, he always knew when to be serious. If he noticed one of his friends was feeling down, he would be the first to check in. He always went out of his way to make conversation with those who needed it most. When he would ask ‘How's it going, man?’ in the most nonchalant, genuine way possible, you knew he wanted the real answer.

“We all deserve to have a Drew in our lives,” Psaras said.

Drew is survived by his parents, Susanne and Andrew Esquivel, and his sisters, Elisabeth and Emma, all of Healdsburg, California; his grandfather Donald B. Boyd, PhD of Greenwood, Indiana; and his grandparents Andy and Maria Esquivel of Fremont, Ohio.

His parents have established the Drew Esquivel Memorial Scholarship, through the Rotary Club of Healdsburg Sunrise Foundation. This annual, merit-based scholarship will be available to graduates from Healdsburg High School.

A July 20 gathering at the MIT chapel also honored Drew. It followed an email sent to the MIT community at the request of MIT President L. Rafael Reif, who was traveling at the time, in which Chancellor Cynthia Barnhart extended MIT’s deepest sympathy to Drew’s family and friends. To the larger circle of the accident victims’ MIT friends and connections, “we join you in your shock and grief,” she wrote. A memorial service for Drew at MIT is planned for early in the fall semester.