Improved queuing algorithms in QoS enabled Internet node

Abstract

This project is supported by the Hong Kong Polytechnics University research grant no. G-V989. In this project, traditional queuing algorithms were studied and analyzed. Two new algorithms are proposed. Weighted Deficit Probability Drop (WDPD) further enhances the throughput fairness among groups of different weighted flows. Weighted Deficit Round Robin (WDRR) enables low complexity QoS. There are many existing queuing algorithms and some of them are implemented and introduced in the commercial market. Weighted Fair Queuing (WFQ), which was introduced in 1993 and is being implemented in most of the Cisco Routers, which use to aggregate traffics less than 2 Mbps. Although the WFQ and Worst-case Fair Weighted Fair Queuing Plus (WF2Q+) are relatively fair among the same weighted flow, their algorithm needs high computational cost to calculate the virtual finish time and the eligible virtual finish time respectively. They are used to approximate the General Processor Sharing (GPS) system. The high computational requirement of the algorithm makes it impractical to be implemented on high-speed link to support similar Quality of Service (QoS). In this thesis, a number of queuing algorithms are introduced and analyzed. Network simulations are used to validate the network properties of the algorithms. Fairness is hard to define and quantify, a different point of view on the ambiguous term "fairness" will be discussed. At last, two new algorithms: the Weighted Deficit Probability Drop (WDPD) and the Weighted Deficit Round Robin (WDRR) are developed and discussed. WDPD enables a higher fairness between different weighted flows and WDRR enables a low complexity QoS support in Internet node.