臺灣博碩士論文加值系統

在現今的多媒體網路普遍的情況下，要滿足不同的需求，服務品質控制是必要的機制，而其中主動式佇列管理(Active Queue Management, AQM)便是相當重要的一環。因此，本篇論文將針對演算法GREEN (Global Random Early Estimation for Nipping)做適當的修改。GREEN將先期偵測擴展為先期預估，進行預估方法是利用網路目前的變化狀況。透過這個方法，可以做到比偵測更早獲取網路的狀態且做快速決策。而在修改過後在模擬的表現上有較為穩定的效果，且不影響原本的好效能。
本篇論文另外也提出了一個新的演算法，稱為PASS (drop with Probability And StatisticS)。一般AQM一定使用隨機的方式來丟棄封包，而在此吾人將隨機的方式分為機率(probability)及統計(statistics)，PASS對於TCP flows使用drop with probability，對UDP flows則使用drop with statistics。這樣的機制即使在無DiffServ的環境仍可使用。PASS仿效了CHOKe還有CHOKeW使用match drop，不同的是，PASS的match drop只使用在UDP flows且無須比較flow id，使得UDP不會無限制的取得頻寬，且以更有效率的方法丟棄封包，進而達到與CHOKe和CHOKeW相同的TCP protection。

Nowadays, the multimedia networks are common. To satisfy the different requirements in the multimedia networks, the QoS control mechanisms are necessary. Among these, the active queue management (AQM) plays an important role. Therefore, this thesis modifies the algorithm “GREEN (Global Random Early Estimation for Nipping).” GREEN enhances the concept of “Early” to “Early Estimation” by early estimating the network status. The network status obtained by estimation is earlier than by detection. In this way, the decision in the AQM can be made more quickly. After modification, the algorithm iss more stable than original GREEN and still keeps the original good features.
This thesis also proposes a novel AQM algorithm named PASS (drop with Probability And StatisticS). In general, AQM should drop packet with random. We classify the random manner into two types: probability and statistics. For TCP flows, PASS drops the packets with probability, and for UDP flows PASS drops packets statistics. This method should works even for the networks without DiffServ. PASS uses the “match drop” like CHOKe and CHOKeW. But the difference is that the match drop of PASS just uses for UDP flows and there are no comparisons of flow id. In this way, the throughput of unresponsive flows is suppressed to protect TCP flows like CHOKe and CHOKeW. Furthermore, the overall algorithm is more efficiency.

中文摘要 I
英文摘要 II
致謝 IV
目錄 V
圖表 VI
第一章 緒論
1.1 研究背景 1
1.2 研究動機 4
1.3 論文架構 8
第二章 GREEN 演算法
2.1 前言 9
2.2 GREEN 12
2.2.1調整GREEN演算法 18
2.3 數值模擬結果與討論 21
2.4 結論 36
第三章 PASS 演算法
3.1 前言 37
3.2 PASS 40
3.3 數值模擬結果與討論 44
3.4 結論 56
第四章 結論 57
參考文獻 58

[1]R. Braden, D. Clark, and S. Shenker, "Integrated services in the Internet architecture: an overview," Internet RFC 1633, June 1994.
[2]S. Blake, D. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated services," Internet RFC 2475, Dec. 1998.
[3]S. Shenker, C. Partridge, and R. Guerin, "Specification of Guaranteed quality of service," Internet RFC 2212, Sep. 1997.
[4]J. Wrockawski, "Specification of the controlled-load network element service," Internet RFC 2211, Sep. 1997.
[5]V. Jocobson, K. Nichols, and K. Poduri, "An expedited forwarding PHB,"RFC2598, Internet Engineering Task Force, June 1999.
[6]J.Heinanen, F. Baker, W. Weiss, and J. Wrociawski, "Assured forwarding PHB group,"RFC2597, Internet Engineering Task Force, June 1999.
[7]J. Postel, "Service mappings," RFC 795, Sep. 1981.
[8]Nichols, K., Blake, S., Baker, F. and D. Black, "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers", RFC 2474, Dec. 1998.
[9]Y. Thomas Hou, Zhenhai Duan, Zhi-Li Zhang, and Takafumi Chujo, "Providing Scalable Support for Multiple QoS Guarantees: Architecture and Mechanisms," IEEE, 2001.
[10]H. Shimonishi and H. Sluzuki, "Performance analysis of weighted round robin cell scheduling and its improvement in ATM networks," IEICE Trans. Comm., vol. E81-B, no. 5, pp. 910-918, May 1998.
[11]J. C. R. Bennett and H. Shang, "WF2Q: Worst-case Fair Weight Fair Queueing," INFOCOM’96. Fifteenth AANNUAL Joint Conference of the IEEE Computer Societies. Networking the Next Generation. vol.1, pp.120-128, 1996.
[12]S. Floyd and V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM trans. networking, vol.1, no.4, pp.397-413, 1993.
[13]O. Elloumi and H. Afifi, "Improving RED algorithm performance in ATM networks," IEEE GLOBECOM ''97, vol.2, pp.1062-1066, 1997.
[14]R. Guerin and V. Peris, "Quality-of-service in packet network: basic mechanisms and direction," Computer Networks, vol. 31, 1999, pp.169-189.
[15]V. Jacobson, "Congestion avoidance and control," SIGCOMM ‘88, Aug. 1988, pp.314-329.
[16]E. Hashem, “Analysis of random drop for gateway congestion control”, Rep. LCS TR-465, Lab. for Comput. Sci., M.I.T., p.103, 1989.
[17]L. Zhang, “A new architecture for packet switching network protocols”, MIT/LCS/TR-455, Lab. for Comput. Sci., M.I.T., 1998.
[18]O. Elloumi and H. Afifi, “Improving RED algorithm performance in ATM networks,” IEEE GLOBECOM ''97, vol.2, pp.1062 -1066, 1997.
[19]R. Guerin and V. Peris, ”Quality-of-service in packet network: basic mechanisms and direction”, Computer Networks, vol. 31, 1999, pp.169-189.
[20]Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S.,Estrin,D., Floyd, S.. Jacobson, V., Minshall, G., Pamidge, C., Pererson,L.,Ramakrisbnan,K., Shenker,S., Wroclawski, J., Zhang, L., “Recommendationson queue management and congestion avoidance in the internet”,IETF RFC (Informational) 2309, April 1998.
[21]R. Pan, B. Prabhakar, and K. Psounis,”CHOKe: A Stateless Active QueueManagement Schemefor Approximating Fair Bandwidth Allocation”, IEEE INFOCOM''01
[22]S. Wen, Y. Fang and H. Sun,”CHOKeW: Bandwidth Differentiation and TCP Protection in Core Networks”,IEEE Vol. 3, pp.1456 - 1462 Oct. 2005
[23]Lain-Chyr Hwang, Cheng-Yuan Ku, Steen J. Hsu, and Huan-Ying Lo, "QoS Buffer Management of Multimedia Networking with GREEN algorithm," JOURNAL OF COMMUNICATIONS AND NETWORKS, Vol. 3, No. 4, pp. 334-341, Dec. 2001.
[24]Tain, A., Karandikar, A. and Verma, R.,”An adaptive prediction base approach for congestion estimation in active queue management(APACE)”,IEEE Vol. 7, pp.4153 – 4157, Dec. 2003
[25]ns-2 (Network Simulator version 2). [Online]. Available:http://www.isi.edu/nsnam/ns/
[26]Huan-Ying Lo, Lain-Chyr Hwang, “QoS Buffer Management in the Internet “Department of Electrical Engineering, I-Shou University Jun 2001
[27]Wu-chang Feng, Shin, K.G., Kandlur, D.D., Saha, D. “The BLUE active queue management algorithms”, Vol. 10, Issue 4, pp.:513 – 528, Aug. 2002
[28]J. Postel, "Transmission Control Protocol," RFC793, USC/Information Sciences Institute, Sep. 1981.
[29]J. Postel, "User Datagram Protocol," RFC768, USC/Information Sciences Institute, Aug. 1980.
[30]V. Jacobson, "Congestion avoidance and control," SIGCOMM ‘88, Aug. 1988, pp.314-329.
[31]W. Stevens, " TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms" Internet RFC2001, Jan. 1997.
[32]W. Stevens, M. Allman, V. Paxson, " TCP Congestion Control" Internet RFC2581, Apr. 1999
[33]S. Floyd, T. Henderson, A. Gurtov, " The NewReno Modification to TCP''s Fast Recovery Algorithm" RFC3782, USC/Information Sciences Institute, Apr. 2004
[34]S. Floyd, M. Mathis, A. Romanow, " TCP Selective Acknowledgment Options" Internet RFC2018, Oct. 1996
[35]S. Wen and Y. Fang, CHOKeW Patch on ns, April 2005. [Online].Available: http://www.ecel.ufl.edu/ wen/chokew.zip