Universal Packet Scheduling

This project addresses a seemingly simple question: Is there a universal packet scheduling algorithm? More precisely, researchers are analyzing whether there is a single packet scheduling algorithm that, at a network-wide level, can perfectly match the results of any given scheduling algorithm. The question of universal packet scheduling is being investigated from both a theoretical and empirical perspective.

Prior theoretical analysis by the PI suggests that, in general, the answer to whether a universal packet scheduler exists is "no". However, further analysis suggests that the classical Least Slack Time First (LSTF) scheduling algorithm comes theoretically closest to being universal. From an applied perspective, early results suggest that LSTF can be used in practice to meet common network performance objectives such as minimizing mean flow completion time (FCT), minimizing tail packet delays, and maximizing fairness.

Many open questions remain on both the theoretical and applied fronts that this project addresses. Key questions include: (i) understanding the exact conditions under which universality is feasible, (ii) deriving bounds on the extent to which universality - when infeasible - might be violated, (iii) evaluating empirically the extent to which LSTF can replay a wide range of scheduling algorithms and meet a range of performance objectives under realistic network settings, (iv) understanding how a UPS can be applied in conjunction with active queue management (AQM) techniques, (v) developing the system architecture for a UPS that can be implemented in router hardware for high speed operation, and so forth.