New Packet Scheduling Tool is Scalable, Improves Network Speeds

Large networks — from the internet to data centers — need to manage traffic. But as volumes increase, existing tools used to manage the flow of data requests become less effective.

Using a new approach, Georgia Tech College of Computing researchers have created a flexible packet scheduling software system that is scalable, up to 40 times faster than existing tools, and can handle complex scheduling tasks.

Unlike existing tools, the new scheduling system – known as Eiffel – uses a modified priority queue to efficiently rank and re-rank packets.

The power of packet scheduling

Balancing a network’s traffic requires considering a lot of complex factors. If there are too many requests at once, it won’t run efficiently. Yet not all those requests are of the same importance so prioritizing them is essential.

Many networks rely on packet scheduling to handle the volume. When traffic exceeds capacity, packets are queued. Scheduling decides which packet to take next.

School of Computer Science (SCS) Regents’ Professor Mostafa Ammar compares packet scheduling to plumbing.

“If you try to put water in a pipe too fast, it might overflow,” he said. “But if you put the water through a bucket and put a hole in the bucket, it would control the flow. You can make the hole wider or smaller to let it drip at a certain rate.”

As central processing units (CPUs) get more memory, they can handle more requests. Network scheduling techniques, however, have difficulty keeping up because existing scheduling tools weren’t designed to scale to meet growing traffic volumes. They also weren't designed for complex scheduling tasks, like pushing a bank transaction ahead of video streaming request, or with the ability to have performance upgrades.

[RELATED: Mostafa Ammar is Studying the History of the Internet to Find Its Future]

An efficient and flexible system

To increase efficiency, Eiffel uses a modified ranking function with find first set (FFS) bit operation to order packets in the queue based on their rank. To do so, an annotation mode first ranks a packet’s priority, then an enqueuer component calculates its rank and adds it to a queue in order of its priority.

Eiffel also features a dequeuer component that can re-rank packets as needed for certain scheduling algorithms. The team’s novel use of FFS queues allows them to process a large volume of packets without losing any CPU efficiency.

To make Eiffel flexible, researchers introduced new programming language abstractions. These make the program general enough to create ad hoc scheduling policies as needed.

SCS Ph.D. student Ahmed Saeed started this work as part of a Google internship and published a paper on improving a specific scheduling algorithm last year. After his colleagues at Google expressed interest in addressing more complex scheduling issues, too, he made it a focus of his research, leading to Eiffel that improves the efficiency of all scheduling algorithms.

“It really comes down to the number of flows a single server handles,” he said. “If we have a generally efficient building block that can handle large numbers of flows efficiently, we can also provide flexibility to implement multiple scheduling algorithms quite easily.”

[RELATED: Georgia Tech SCS Ph.D. Student Earns Prestigious Google Fellowship]

The researchers evaluated Eiffel in three network settings to ensure its performance in a variety of scenarios. Depending on the environment, Eiffel performs from five to 40 times better than other scheduling software. Because of this performance, the researchers plan to make Eiffel available as an open source tool.

Saeed will present the paper, Eiffel: Efficient and Flexible Software Packet Scheduling, at USENIX’s Symposium on Networked Systems Design and Implementation (NSDI) in Boston, Massachusetts, from Feb. 26 to 28. He coauthored it with SCS Ph.D. student Yimeng Zhao, Stephen Fleming Chair for Telecommunications Professor Ellen Zegura, Ammar, Google software engineer Nandita Dukkipati, Google Fellow Amin Vahdat, and Carnegie Mellon Qatar Associate Professor Khaled Harras.