臺灣博碩士論文加值系統

不管在任何形式的網路上，由於網路頻寬的可貴性以及傳輸的有效traffic congestion control永遠扮演一個重要的角色。
本論文主要目的在於為ATM的ABR service設計一套congestion control的演算法。ATM protocol stack中的ATM layer（相當於ISO protocol stack中的第二層data link layer ），並沒有對ATM cell做link by link的error control，因此若其中一個cell被drop or lost，上層的整個PDU（protocol data unit）都要重新傳送，非常浪費頻寬。而ATM中的ABR service主要是用來傳輸data application（如file transfer）的資料，data application最重視的莫過於資料的正確性，綜合上述兩點，可以知道ABR service對於ATM cell lost是非常敏感。
再者，在ATM的四種service中，ABR service的priority比CBR﹑VBR service的priority低，ATM networks中的任一個switch node，經由CAC（call admission control）switch決定接受CBR service的request，其link的頻寬是固定的﹑有限的，且CBR service的priority比ABR service高，因此switch發出訊息要求ABR connections的source端降低傳送速度，以空出頻寬來服務剛剛建立的CBR connection。而等到CBR connection結束時，或是VBR connections traffic降低時，switch發出訊息要求ABR connections的source端提高傳送速度，以利用剩餘的頻寬。因此ABR service是一種Best-effort service。
而我們研發出來的頻寬分配演算法是一個非常符合經濟效益的演算法，因為在switch上每一條連線只有6 bits的負擔，而所有增進基本的頻寬分配演算法的改良機制，都把機制本身所造成的負擔加諸在連線的source端上，使得我們的頻寬分配演算法能有媲美於ER方法的效能，但在switch上的負擔確又遠低於ER方法。更甚者，switch在計算max-min fair share時的計算複雜度只有O(1)，遠低於ER方法的O(N)。

Traffic congestion control always plays an important role in any kind of networks due to the scarcity of bandwidth. There are four service categories in ATM networks：Constant Bit Rate (CBR) Service, Variable Bit Rate (VBR) Service, Available Bit Rate (ABR) Service, and Unspecified Bit Rate (UBR) Service. Because CBR and VBR services both have higher priority than ABR service, ABR service is
considered a best-effort service. Our thesis tries to design a congestion control algorithm for ATM ABR service.
The algorithm we developed is very cost-effective. Every ABR connection only needs 6-bit storage in an ATM switch. Moreover, our computation complexity of calculating max-min fair share is O(1). The performance of our algorithm on the GFC[2] test network appears very good.

第一章 導論 1
1.1 背景 1
1.2 ABR service congestion control的機制 1
1.3 Max-min fairness 2
1.4 相關的研究 3
1.5 研究動機與目的 4
第二章 基本演算法 6
2.1 終端系統 6
2.2 Switch系統 7
2.3 效能分析 17
第三章 改良機制 19
3.1 RDF參數的初始化與動態調整制 19
3.2 Source端猜測連線的Max-min Fair Share機制 23
3.3 其他較次要的改良機制 27
第四章 實驗結果與效能分析 30
4.1 簡單的網路拓樸 30
4.2 複雜的網路拓樸 34
第五章 結論及未來的研究方向 51
5.1 結論 51
5.2 未來的研究方向 51
參考文獻 52

[1] J. M Jaffe, “ Bottleneck Flow Control “ IEEE Trans
Commun. , vol. 29, July 1981,pp. 954-62.
[2] A. Charny, D. Clark and R. Jain, “ Congestion Control
With Explicit Indication “
Proc. ICC’95, June 1995.
[3] L. Roberts, “ Enhanced PRCA ( Proportional Rate-Control
Algorithm ) “ ATM Forum cont. 94-0735R1, Aug 1994.
[4] K. —Y. Siu and H. —Y Tzeng, “ Adaptive proportional
rate control ( APRC ) with relative congestion indication
“ ATM forum contribution 94-0888, Sep 1994.
[5] R. Jain, S. Kalyanaraman, and R. Viswanathan, “
Simulation result：The EPRCA+ scheme “, ATM forum
contribution 94-0833, October 1994.
[6] F. Chiussi , Y. Xia, and V. P. Kumar, “ Dynamic Max Rate
Control Algorithm for Availabel Bit Rate Service in ATM
Network. “ GlOBECOM’96 ,pp. 2108-2117.
[7] Sudhakar Muddu, Fabio M. Chiussi, Christos Tryfonas, and
Vijay P. Kumar “ Max Min Rate Control Algorithm for
Available Bit Rate Service in ATM Network “ ICC’96 ,pp.
412-18.
[8] A. Charny. “ An algorithm for rate allocation in a cell
switching network with feedback “ Master’s thesis,
Massachusetts Institute of Technology, May 1994.
[9] R. Jain, S. Kalyanaraman, and R. Viswanathan, “ A sample
switch algorithm “ ATM forum contribution 95-0178R, Feb.
1995.
[10] L. Kalampoukas, A. Varma, and K. K. Ramakrishnan, “ An
Efficient Rate Allocation Algorithm for ATM Networks
Providing Max-min fairness “, Proc. 6th
IFIP Int’l. Conf. High Performance Networking, Sept
1995 ,pp. 143-54.
[11] Yan Moret, Serge Fdida, “ ERAQLES an Efficient Explicit
Rate Algorithm for ABR “, INFOCOM’97, pp. 801-05.
[12] S. Fahmy, R. Jain, S .Kalyanaraman, R. Goyal, B.
Vandalore, “ On Determining the Fair Bandwidth Share for
ABR Connections in ATM Networks “ ICC’98, pp. 1485-91.
[13] The ATM forum, “ The ATM Forum Traffic Management
Specification V4.0 “ 1996.
[14] Yiwei Thomas Hou, Hernry H. —Y Tzeng , Shivendra S.
Panwar “ A Generic Weight-Based Network Bandwidth Shareing
Policy for ATM ABR Service “ ICC’98, pp 1492-1499.
[15] Fabio M. Chiussi , Y. T. Wang “An ABR Rate-Based
Congestion Control Algorithm for ATM Switches with Per-VC
Queueing “ INFOCOM’97, pp 711-778.
[16] Fabio M. Chiussi, Ye Xia, and Vijay P. Kumar “ Virtual
Queueing Techniques for ABR service：Improving ABR/VBR
Interaction “ INFOCOM’97, pp 406-418
[17] Ting-Li Ling, and Ness Shroff “ A Novel Flow Control
Mechanism for ABR Traffic in ATM Networks ” ICC’97.
[18] Wenya Qi, and Shixin Cheng “ A New Oscillation avoid Flow
Control Scheme using Explicit Rate Indications “
GLOBECOM’97, pp. 1422-1425
[19] Hiroyuki Ohsayuki,Masayuki Murata and Hideo Miyahara “
Designing Efficient Explicit-Rate Switch Algorithm with
Max-Min Fairness for ABR Service Class in ATM Networks “
GLOBECOM’97, pp 182-186.
[20] Ambalavanar Arulambalam, Xiaoqiang Chen and Nirwan Ansari
“ An Intelligent Explicit Rate Control Algorithm for ABR
Service in ATM Networks “ GLOBECOM’97, pp 200-204.
[21] Yiwei Thomas Hou, Hernry H. —Y Tzeng , Shivendra S.
Panwar “ A Weighted Max-Min Fair Rate Allocation for
Available Bit Rate Service “ INFOCOM’97 pp 492-497.
[22] David Lapsley and Steven Low “ An Optimization Approach
to ABR Control “ ICC’98, pp 1500-1504
[23] P. P. Mishra, H. Kanakia and S. K. Tripathi, “ On Hop-by-
Hop Rate-Based Congestion Control ”, IEEE/ACM Trans on
Networking, 1996, pp. 224-239
[24] D. Tsang and W. Wong. “ A New Rate-Based Switch Algorithm
for ABR Traffic to Achieve Max-Min Fairness with Analytical
Approximation and Delay Adjustment “ INFOCOM’96, pp 1174-
1181.
[25] Y. T. Hou, H. Tzeng, S. S. Panwar, and V. P. Kumar “ Fair
Network Bandwidth Allocation with Minimum Rate Guarantee
and Its Implementations “ ICC’97, pp 1411-1416.