Efficient Scheduling Algorithms for Quality-of-Service Guarantees in the Internet

The unifying theme of this thesis is the design of packet schedulers to provide quality-of-service (QoS) guarantees for various networking problem settings. There is a dual emphasis on both theoretical justification and simulation evaluation. We have worked on several widely different problem settings- optical networks, input-queued crossbar switches, and CDMA wireless networks- and we found that the same set of scheduling techniques can be applied successfully in all these cases to provide per-flow bandwidth, delay and max-min fairness guarantees. We formulated the abstract scheduling problems as a sum of two aspects. First, the particular problem setting imposes constraints which dictate what kinds of trans-mission patterns are allowed by the physical hardware resources, i.e., what are the feasible solutions. Second, the users require some form of QoS guarantees, which translate into optimality criteria judging the feasible solutions. The abstract problem is how to design an algorithm that finds an optimal (or near-optimal) solution among the feasible ones