University of British Columbia
A minimum-work weighted fair queuing algorithm for guaranteed end-to-end and quality-of-service in packet networks
Abstract
dc:descriptionEmerging applications in multimedia communications and Virtual Private Networks (VPNs) require data networks to provide Quality-of-Service (QoS) guarantees, such as delay and/or jitter bounds, to individual packet flows. Providing such guarantees can be achieved by link scheduling mechanisms along the path of these packets. Among the many packet-scheduling techniques proposed for this problem, Weighted Fair Queuing (WFQ) offers the best delay and fairness guarantees. However, all previous work on WFQ has been focused on developing inefficient approximations of the scheduler because of perceived scalability problems in the WFQ computation. This thesis proves that the previously well accepted O(N) time-complexity for WFQ implementation, where N is the number of active flows handled by the scheduler, is not true. The other key contribution of the thesis is a novel Minimum- Work Weighted Fair Queuing (MW-WFQ) algorithm which is an 0(1) algorithm for implementing WFQ. In addition, the thesis presents several performance studies demonstrating the power of the proposed algorithm in providing precise delay bounds to a large number of sessions with diverse QoS requirements, whereas other well known scheduling techniques have failed to provide the same guarantees for the same set of sessions.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy - PhD
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Electrical and Computer Engineering
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2002
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Tayyar, Haitham Fahmi
Rights
dc:rights- Statement dc:rights
-
- For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/13577