在目前新興整合服務的高速封包交換網路下，封包排程演算法在交換器與路由器當中，對於提供應用程式的網路服務品質扮演一個很重要的角色。

在這篇論文裡面，我們提出一個新的公平排程演算法，叫做Weighted Class Fair Queuing(WCFQ)。WCFQ是一個有著低複雜度，公平性，和有好的網路延遲表現的排程器。主要的方法是將傳送速率相近的flow分類。這個排程方法分成兩部分，在類別外的排程與在類別內的排程。在類別外的排程是利用以credit 為基本的方法來選擇要排程的類別。接著，類別內的排程則利用類似Round-Robin方法來挑選一個flow傳送封包。我們也提供簡單的分析來說明我們的複雜度與公平性。

最後我們將Weighted Class Fair Queuing實做在NS2模擬器上， 並與其他排程方法比較兩節點之間的網路延遲。我們經由實驗證明 WCFQ 擁有好的網路延遲表現。

In the emerging high-speed integrated-services packet switched networks, packet scheduling algorithms in switches and routers play a critical role in providing the Quality-of-Service (QoS) guarantees required by many applications.

In the thesis, we propose a new fair scheduling algorithm called Weighted Class Fair Queuing (WCFQ). WCFQ is a low complexity scheduler with bandwidth fairness, and has good delay performance. The key idea is that group flows with similar weight into the same flow class. The scheduling discipline is divided two part, inter-class scheduling and intra-scheduling. The inter-class scheduling employs credit-based scheme to choose the flow class. Next, the intra-class scheduling decides what flow within the flow class is scheduled in similar round-robin manner. We also provide a trivial analysis to explain our complexity and fairness.

Finally, we implement Weighted Classes Fair Queuing in NS2 network simulator to compare the end to end delay with other existing fair scheduling algorithms. We demonstrate that WCFQ has good delay performance through simulation.

[1] Bennett, J., and Zhang, H. , “Hierarchical packet fair queueing algorithms,” ACM SIGCOMM’96, 1996.
[2] Bennett, J., and Zhang, H. , “WF2Q : Worst case fair weighted fair queuing,” IEEE INFOCOM’96,1996.
[3] Cheung, S., and Pencea, C. , “BSFQ: Bin sort fair queuing,” IEEE INFOCOM’02 , pp. 1640-1649, 2002.
[4] Chuanxiong, G. , “SRR: an O(1) time complexity packet scheduler for flows in multi-service packet networks,” ACM SIGCOMM’01 , pp. 211-222, 2001.
[5] Demers, A., Keshav, S., and Shenker, S. , “Analysis and simulation of a fair queuing algorithm,” ACM SIGCOMM’89 , vol. 19, no. 4, pp. 3-12, 1989.
[6] Golestani, S. , “A self-clocked fair queueing scheme for broadband applications,” IEEE INFOCOM’94 , pp. 636-646, 1994.
[7] Lenzini, L., Mingozzi, E., and Stea, G. , “Aliquem: a novel DRR implementation to achieve better latency and fairness at O(1) complexity,” IWQoS’02 , 2002.
[8] Parekh, A., and Gallager, R. , “A generalized processor sharing approach to flow control in integrated services networks: The single node case,” IEEE/ACM Transactions on Networking , vol.1, no. 3, pp. 344-357, 1993.
[9] Pan, D., and Yang, Y. , “Credit Based Fair Scheduling for Packet Switched Networks” , IEEE INFOCOM’05, vol. 2, pp. 843-854, 2005.
[10] Ramabhadran, S., and Pasquale, J. , “Stratified round robin: a low complexity packet scheduler with bandwidth fairness and bounded delay,” ACM SIGCOMM’03, pp. 239-250, 2003.
[11] Shreedhar, M., and Varghese, G. , “Efficient fair queuing using deficit round robin,” IEEE/ACM Transaction on Networking , vol. 4, no.3, pp. 375-385, 1995.
[12] Stiliadis, D., and Varma, A. , “Efficient fair queueing algorithms for packet switched networks,” IEEE/ACM Transactions on Networking 6 , April 1998.
[13] Stiliadis, D., and Varma, A. , “Rate proportional servers: A design methodology for fair queueing algorithms,” IEEE/ACM Transactions on Networking 6 , April 1998.
[14] Tsao S.-C. , and Lin Y.-D., “Pre-Order Deficit Round Robin : a new scheduling algorithm for packet switched networks,” Computer Network, vol. 35, pp. 287-305, February 2001.
[15] www.cisco.com. Cisco GSR.
[16] Xu, J., and Lipton, R. , “On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms,” ACM SIGCOMM ’02 2002.
[17] Mckenney, P. , “Stochastic fair queueing,” Internetworking: Research and Experience, vol. 2, pp. 113--131, Jan. 1991.