Every large network — from the internet to datacenter networks — needs a way to manage traffic. But as traffic volumes increase, existing packet scheduling tools used to manage flow become less effective.
Using a new approach, School of Computer Science (SCS) researchers have created a flexible packet scheduling software system that is scalable and up to 40 times faster than existing scheduling software tools.
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.
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 certain rate.”
As central processing units (CPUs) get more memory, they can handle more requests. Network scheduling techniques, however, aren’t keeping up because existing scheduling tools weren’t designed to scale to meet growing traffic volumes. Another research problem in packet scheduling is how to allow for complex scheduling (for example, pushing a bank transaction ahead of video streaming) and improved performance.
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 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.”
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 said Eiffel represents a huge step forward in software packet schedulers, but he wants to continue improving its flexibility. The programming language for schedulers in Eiffel is very low level right now and needs specific instructions to be effective. The researchers plan to make the language even more abstract, so it can be more adaptable in future research.
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.