臺灣博碩士論文加值系統

在壅塞的網路中，產生flow數目越多的節點會得到比較多的頻寬，這會使得其他節點得不到公平的服務。我們得知使用多個虛擬佇列(virtual queue)可以解決節點flow數目之差異性所造成網路不公平的問題。當網路中的每個節點都使用一個虛擬佇列時，在每個單位時間動態地去調整每個虛擬佇列的初始丟棄機率(initial drop probability)就可以使每個節點得到公平的頻寬。但是，當節點很多時，使用很多的虛擬佇列並不實際。因此在本篇論文中，我們希望將網路中的每一個節點作分群，將flow數目相差不多的節點分在相同群組。被分在相同群組的節點共同使用一個虛擬佇列。在實驗中，實作模擬工具軟體ns2，將會幫助驗證。若是每個節點所獲得的頻寬差異越小，Fairness index會越接近1，代表網路越公平。從計算fairness index中，我們可以了解在網路中節點分群的結果。舉例，從實驗中，當網路有50個節點，使用10個虛擬佇列，其fairness index等於0.984。我們所提出的方法可以有效減少使用虛擬佇列的個數，還可以讓網路中的每個節點可以得到合理公平的頻寬。

In a congested network, an aggressive node could acquire more bandwidth for itself by intentionally increasing the number of flows. This leads to a serious problem of fairness in bandwidth allocation. This problem can be solved by a technique known as virtual queue. In the network, each node employs a virtual queue with an initial drop probability. The probability is dynamically adjusted for each node to acquire a fair share of the bandwidth. However, the virtual-queue technique has a major drawback, it bccomes considerably difficult and impractical to manage a large number of virtual queues, as the number of nodes explodes. In this thesis, we propose an efficient method to deal with this problem. Our idea is to sort nodes into groups on the basis of flow numbers. Nodes with similar flow numbers are placed in a group and they share a single virtual queue for bandwidth allocation. We verify the effectiveness of our proposed method through a simulation tool – ns2. By calculating fairness index, we are able to evaluate the performance of our method operating in various conditions. The simulation results show that the proposed method can effectively reduce the number of virtual queues in use. In addition, it guarantees that all the nodes receive a fair treatment of bandwidth allocation.

中文摘要 ......................... i
Abstract ......................... ii
目錄 ............................. iii
表目錄 ........................... v
圖目錄 ........................... vi
第一章 導論 .................... 1
1.1　簡介 ...................... 1
1.2　研究動機 .................. 3
第二章　背景知識 ................. 6
2.1　壅塞 ...................... 7
2.2　簡介TCP壅塞控制 ........... 10
2.3 簡介Drop-tail機制 ........... 14
2.4　簡介RED機制 ................. 15
第三章　問題與解決方案 ........... 17
3.1　欲解決的問題 .............. 17
3.2　解決方案 .................. 26
3.2.1　分群演算法 ............ 26
3.2.2　MSF-RED演算法 ......... 32
3.2.3　重複分群 .............. 35
第四章　程式模擬與評估 ........... 36
4.1　程式設定 .................. 36
4.2　程式模擬 .................. 37
4.2.1　虛擬佇列個數的影響 .... 37
4.2.2　節點個數的影響 ........ 43
4.2.3　flow variance的影響 ... 48
第五章 結論 .................... 54
參考文獻 ......................... 56

[1] Hsien-Ming Wu , Chin-Chi Wu , Woei Lin ,”SF-RED – a Novel Server-based AQM to Provide Inter-Server Fairness Service ,” in Proc. The Twelfth IEEE International Conference on Parallel and Distributed Systems (ICPADS2006) , July 2006
[2] Mark Parris , Kevin Jeffay , Don Smith , “Responsive vs. Unresponsive Traffic : Active Queue Management for a Better-Than-Best-Effort Service ,” http://www.cs.unc.edu/~jeffay/papers/IEEE-Networks-01.pdf.
[3] W. R. Stevens , ”TCP/IP Illustrated, Vol.1:The Protocols ,” Addison-Wesley , Reading , Mass. 1994.
[4] V. Jacobson , “Congestion avoidance and control ,” in Proc. ACM SIGCOMM , pp.157-187 , January 1995.
[5] Wu-chang Feng , Kang G. Shin , Dilip D. Kandlur and Debanjan Saha , “The BLUE Active Queue Management Algorithms ,“ IEEE/ACM Trans. Networking , vol.10 , no. 4 , pp.513-528 , August 2002.
[6] S. Floyd , S. , & K. Fall , “Promoting the Use of End-to-End Congestion Control in the Internet ,” IEEE/ACM Transactions on Networking, pp.458-472 , August 1999.
[7] B. Braden , D. Clark , J. Crowcroft , B. Davie , S. Deering , D. Estrin , S. Floyd , V. Jacobson , G. Minshall , C. Partridge , L. Peterson , K. Ramakrishnan , S. Shenker , J. Wroclawski , & L. Zhang , “Recommendations on Queue Management and Congestion Avoidance in the Internet ,” Internet draft , work in progress , 1998.
[8] S. Floyd and V. Jacobson , “Random early detection gateways for congestion avoidance ,” IEEE/ACM Trans. Networking , vol.1 , No.4 , pp.397-413 , Aug. 1993.
[9] V. Firoiu , M. Borden , “A Study of Active Queue Management for Congestion Control ,” in Proc. IEEE INFOCOM , pp.1435-1444 , Mar. 2000.
[10] C.V. Hollot , Vishal Misra , Don Towsley and Wei-Bo Gong , “On Designing Improved Controllers for AQM Routers Supporting TCP Flows ,” in Proc. IEEE INFOCOM , pp.1726-1734 , 2001.
[11] Qiang Chen and Oliver W. W. Yang , “On Designing Self-Tuning Controllers for AQM Routers Supporting TCP Flows Based on Pole Placement ,” IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS , VOL. 22 , NO. 10 , pp.1965-1974 , December 2004.
[12] William Stallings , “High-speed Networks and Internets : Performance and Quality of Service 2/e ,” Prentice Hall , pp.256-259 , 2002.
[13] K. Ramakrishnan and S. Floyd , “A Proposal to add Explicit Congestion Notification (ECN) to IP ,“ RFC2481 , January 1999.
[14] S. Floyd , “TCP and Explicit Congestion Notification ,” Computer Communication Review , pp.8-23 , October 1994.
[15] Jae Chung and Mark Claypool , “Analysis of Active Queue Management ,” in Proc. The Second IEEE International Symposium on Network Computing and Applications , pp.359-366 , 2003.
[16] W. Feng , D. Kandlur , D. Saha , and K. Shin , “A Self-Configuring RED Gateway ,” In Proc. IEEE INFOCOM , pp.1320-1328 , 1999.
[17] Sally Floyd , Ramakrishna Gummadi, and Scott Shenker ,”Adaptive RED: An Algorithm for Increasing the Robustness of RED’s Active Queue Management ,” http://www.icir.org/floyd/papers/adaptiveRed.pdf , August 1 , 2001, under submission.
[18] Srisankar S. Kunniyur , R. Srikant , “An adaptive Virtual Queue(AVQ) Algorithm for Active Queue Management ,” IEEE/ACM Trans. Networking , vol. 12 , no. 2 , pp.286-299 , April 2004.
[19] B. Wydrowski and M. Zukerman , “GREEN : An Active Queue Management Algorithm for a Self Managed Internet ,” in Proc. ICC 2002 , vol. 4 , pp.2368-2372 , 2002.
[20]Sally Floyd , “RED : Discussions of Setting Parameters ,” http://www.icir.org/floyd/REDparameters.txt , 1997.
[21] Rajendra K.Jain , Dah-Ming W.Chiu , William R.Hawe. , ”A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems ,” Sept. 1984. DEC Research Report TR-301.