Back to search

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:description

Emerging 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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Tayyar, Haitham Fahmi. A minimum-work weighted fair queuing algorithm for guaranteed end-to-end and quality-of-service in packet networks. doctoral thesis, University of British Columbia, 2002. http://hdl.handle.net/2429/13577