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 transmission 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. Our schedulers are based on a credit scheme. Specifically, flows receive credits at their guaranteed rate, and the arrival stream is compared to the credit stream acting as a reference. From this comparison, we derive various parameters such as the amount of unspent credits of a flow and the waiting time of a packet since its corresponding credit arrived. We then design algorithms which prioritize flows based on these parameters. We demonstrate, both by rigorous theoretical proofs and by simulations, that these parameters can be bounded. By bounding these parameters, our schedulers provide various per-flow QoS guarantees on average rate, packet delay, queue length and fairness.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2000

Author dc:creator

• Kam, Anthony C. (Anthony Chi-Kong)

Advisor dc:contributor.advisor

• Kai-Yeung Siu.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/9066

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/9066