NeTS: Small: Universal Packet Scheduling

International Computer Science Institute, Berkeley CA

Investigators

Abstract

It is of vital importance that we maintain and evolve the infrastructure that underlies the modern Internet. A fundamental question within this infrastructure is that of `packet scheduling' which determines the order in which data is transmitted across the switches and links that form the Internet's infrastructure. Packet scheduling is thus a richly explored research topic: as networks evolve to support new applications and technologies, so do the requirements placed on packet schedulers, hence researchers and practitioners alike have continued to develop new schedulers to suit current needs. The implicit assumption to date has been that new scheduling goals necessitate new scheduling algorithms. The research being undertaken in this project posits an alternate viewpoint: rather than design new scheduling algorithms as new needs emerge, it asks whether there exists a single scheduling algorithm that can be tuned (i.e., through configuration changes) to match the performance of any scheduling algorithm. Thus the project addresses a seemingly simple question: Is there a universal packet scheduling (UPS) algorithm? The results will clarify the fundamental limits of any packet scheduling algorithm as well as influence the development of network switch hardware. The existence of a universal or near-universal packet scheduler could lower the barrier to evolving network infrastructure and hence contribute to the broader goal of ensuring that the Internet continues to serve as a transformative communication service for the nation. The results of the research will be incorporated into the curriculum for networking courses at both the undergraduate and graduate levels.