擁塞控制新算法：試算平衡

夏長會

(河南財政金融學(xué)院 工程經(jīng)濟學(xué)院，河南 鄭州 451464)

0 引言

所謂擁塞是指網(wǎng)絡(luò)中對某一資源的需求超過了該資源所能提供的可用部分，導(dǎo)致網(wǎng)絡(luò)性能變壞的情況，用關(guān)系式表示為：對資源的需求>可用資源[1]。在網(wǎng)絡(luò)中，若許多資源需求同時發(fā)出，就會產(chǎn)生網(wǎng)絡(luò)擁塞，網(wǎng)絡(luò)的性能就會明顯變壞，網(wǎng)絡(luò)吞吐量[2]將急速下降。因此，擁塞控制的意義不言而喻。有效地控制擁塞，將大大提高網(wǎng)絡(luò)的運營效率和性能，使網(wǎng)絡(luò)資源更好地實現(xiàn)共享。

為了避免網(wǎng)絡(luò)擁塞，學(xué)者們提出了許多行之有效的辦法。Jacobson在認(rèn)為TCP(transmission control protocol)的滑窗機制是有效的同時，提出了慢開始(slow-start)[3]、擁塞避免(congestion avoidance)算法[4]。其后在此基礎(chǔ)上增加了快速重傳算法[5]和快速恢復(fù)算法[6];于是形成了目前廣泛使用的TCP擁塞控制策略的4個核心組成部分。以后又出現(xiàn)了TCP改進版本,如New-reno、SACK、Vegas等[7]。這些算法盡管使網(wǎng)絡(luò)傳輸情況大大改善，也增大了網(wǎng)絡(luò)的吞吐量，但存在諸多不足，主要表現(xiàn)在以下3個方面。

1)資源分配的不公平性[8]。 由于Internet是一種盡力而為(best effort) 的服務(wù)模式,大家爭用有限的資源。源端的目標(biāo)就是盡可能多地占有帶寬。按照傳統(tǒng)擁塞控制算法，當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞時,路由器開始丟棄包。實際上大多數(shù)包的丟失是由于路由器將包丟棄而造成的,而并非由于包損壞。因此當(dāng)包發(fā)生丟棄時,發(fā)送端認(rèn)為網(wǎng)絡(luò)出現(xiàn)了擁塞,需要按擁塞避免算法將發(fā)送窗口減半,以減輕網(wǎng)絡(luò)擁塞。在多個TCP連接共享一個網(wǎng)絡(luò)瓶頸時,這些TCP連接爭用有限的帶寬,使得各個連接占有的帶寬不等,甚至少數(shù)幾個連接占完了所有帶寬,而多數(shù)連接無法通過網(wǎng)絡(luò)傳遞數(shù)據(jù)，造成嚴(yán)重失衡。

2)極易破壞數(shù)據(jù)流的平滑性以及與QOS(quality of service)的結(jié)合[9]。傳統(tǒng)的擁塞控制算法，使TCP每發(fā)現(xiàn)一個報文丟失就將窗口減半，發(fā)送方發(fā)送速率產(chǎn)生劇烈的抖動，極大地破壞了數(shù)據(jù)流的平滑性,導(dǎo)致接收者感受到服務(wù)質(zhì)量的顯著下降，尤其在實時媒體流應(yīng)用逐漸增多的今天, 傳統(tǒng)算法的不足更加突出。

3)網(wǎng)絡(luò)整體效率低下。在傳統(tǒng)算法下，以犧牲整體效率(efficiency) 為代價[10]來減少網(wǎng)絡(luò)擁塞發(fā)生。由于傳統(tǒng)的擁塞控制算法不能從根本上解決擁塞控制問題,某種程度上加重了擁塞情況的發(fā)生，在實際運用中常遇到許多難以逾越的障礙,網(wǎng)絡(luò)性能無法得到充分的提高或明顯的改善。

針對上述傳統(tǒng)擁塞控制算法的不足，根據(jù)網(wǎng)絡(luò)中對某一資源的需求與該資源所能提供的可用部分之間的關(guān)系，本文借鑒會計學(xué)中試算平衡理論，提出了試算平衡算法，可有效地控制擁塞，實現(xiàn)資源分配的公平匹配，保持?jǐn)?shù)據(jù)流傳輸?shù)钠交裕商岣呔W(wǎng)絡(luò)運營的整體效率、穩(wěn)定性和安全性(security)。

1 擁塞控制新算法——試算平衡

所謂試算平衡，就是通過按一定比例控制各部分資源的使用程度，從而限制網(wǎng)絡(luò)對資源的需求，以實現(xiàn)全局資源的供需平衡，其實質(zhì)是實現(xiàn)網(wǎng)絡(luò)各部分資源的匹配，也就是說綜合考慮網(wǎng)絡(luò)中各資源要素，通過對資源需求的再分配，實現(xiàn)網(wǎng)絡(luò)資源供給與需求的相對平衡，進而對擁塞實現(xiàn)更好的控制，以達到避免擁塞的目的。

1.1 將網(wǎng)絡(luò)上各資源分別按容量從大到小，或速率從高到低進行分層排序

設(shè)a為節(jié)點緩存容量，b為鏈路容量，c為處理機速率，d為其他，排序情況見表1，其中

1)a1>a2> …>an-1>an，a1為網(wǎng)絡(luò)節(jié)點的最大緩存容量，an為節(jié)點的最小緩存容量；

2)b1>b2>…>bn-1>bn，b1為鏈路最大容量值，bn為鏈路最小容量值；

3)c1>c2>…>cn-1>cn，c1為處理機速率最高值，cn為處理機速率最低值；

4)d1>d2> …>dn-1>dn，d1為其他類網(wǎng)絡(luò)資源的最大值，dn為其他類網(wǎng)絡(luò)資源的最小值。

表1 網(wǎng)絡(luò)資源分層排序Tab.1 Hierarchical sorting of network resource

1.2 求網(wǎng)絡(luò)資源基礎(chǔ)平衡點

分別以an、bn、cn、dn為標(biāo)準(zhǔn)，測定出與其相匹配的其他資源的值，分別設(shè)為a、b、c、d，其匹配情況見表2。

表2 網(wǎng)絡(luò)資源匹配情況測算Tab.2 Matching calculation of network resource

1)求出標(biāo)準(zhǔn)值與其匹配值之和，分別用a′、b′、c′、d′表示，則

a′=an+b1+c1+d1，b′=bn+a1+c2+d2，c′=cn+a2+b2+d3，d′=dn+a3+b3+c3。

2)比較a′、b′、c′、d′的大小，取最小值為基礎(chǔ)平衡點的值(設(shè)為T)。

Min{a′，b′，c′，d′},若a′最小，則T=an;若b′最小，則T=bn;若c′最小，則T=cn;若d′最小，則T=dn。

1.3 根據(jù)網(wǎng)絡(luò)資源基礎(chǔ)平衡點，確定并計算“余地”資源比例

試算平衡在強調(diào)資源平衡配置的同時，設(shè)有“余地”資源。所謂“余地”資源是指在不影響網(wǎng)絡(luò)正常運行的情況下，將一定比例的資源留作備用，以防網(wǎng)絡(luò)運行中不測事件發(fā)生擁塞的資源。

設(shè)an為基礎(chǔ)平衡點，則與其相匹配的其他資源值為b1、c1、d1。

1)求出bn、cn、dn與an匹配值的差,分別設(shè)其差為m1、m2、m3，則m1=an-b1，m2=cn-c1，m3=dn-d1。

2)求出m1、m2、m3占其對應(yīng)資源最小值的百分比，分別設(shè)為β1、β2、β3，則β1= (m1/bn)×100%，β2=(m2/cn) ×100%，β3= (m3/dn)×100%。

3)取β1、β2、β3的最大值作為“余地”資源的比例(設(shè)為δ)，即δ=max{β1，β2，β3}。

由上述計算可以看出，“余地”資源的大小，要看資源各類別最高層與最低層的差別程度，又要看資源間的匹配程度：若最高層與最低層差別越大，則“余地”資源所占的比例就越大，否則就越小。若各資源間的匹配程度越高，則“余地”資源所占的比例就越小；否則，若資源間的匹配程度越低，“余地”資源所占比例就越大。

當(dāng)m1=m2=m3=0時，“余地”資源的比例δ=0，也就是說，這時網(wǎng)絡(luò)資源是完全匹配的。

事實上，由于受經(jīng)濟、政治、地域、環(huán)境等諸多因素的影響，無論是現(xiàn)在還是將來，網(wǎng)絡(luò)的資源配置，都將存在著不匹配的問題，只是通過人們的共同努力，不匹配的程度會變得越來越低。采用試算平衡雖然可以實現(xiàn)網(wǎng)絡(luò)上的虛擬平衡，但網(wǎng)絡(luò)運行中仍存在許多不可測因素，因此，在資源平衡配置的同時，留出“余地”資源十分必要。其作用是一旦節(jié)點發(fā)生擁塞，發(fā)生擁塞處根據(jù)需求自動啟用“余地”資源，化解擁塞。擁塞解除后，資源自動恢復(fù)原狀態(tài)下工作。

1.4 根據(jù)基礎(chǔ)平衡點及確定的“余地”資源比例，計算網(wǎng)絡(luò)各資源的使用程度

假設(shè)an為基礎(chǔ)平衡點，“余地”資源為δ，則不同層次資源使用的比例如表3；若設(shè)bn為基礎(chǔ)平衡點，“余地”資源為δ時，各資源使用比例見表4。同樣也可求出cn、dn為基礎(chǔ)平衡點，“余地”資源為δ的各資源使用的比例。

表3 基于基礎(chǔ)平衡點an網(wǎng)絡(luò)資源使用程度測算Tab.3 Using degree of network resource measurement based on basic equilibrium point an

表4 基于基礎(chǔ)平衡點bn網(wǎng)絡(luò)資源使用程度測算表Tab.4 Using degree of network resource measurement based on basic equilibrium point bn

1.5 根據(jù)計算出各資源的使用程度，確定對資源的需求的抑制程度

假設(shè)an為基礎(chǔ)平衡點，“余地”資源為δ，則不同層次資源需求的抑制比例如表5；若設(shè)bn為基礎(chǔ)平衡點，“余地”資源為δ時，各資源需求的抑制比例如表6。同樣也可求出cn、dn為基礎(chǔ)平衡點，“余地”資源為δ，對不同層次資源的需求的抑制比例。

表5 基于基礎(chǔ)平衡點an 各資源需求抑制比例計算表Tab.5 Calculation of resource demand suppression ratio based on basic equilibrium point an

表6 基于基礎(chǔ)平衡點bn各資源需求抑制比例計算表Tab.6 Calculation of resource demand suppression ratio based on basic equilibrium point bn

由此可以看出，采用試算平衡算法，基礎(chǔ)平衡點的值越小，網(wǎng)絡(luò)上可用的各種資源利用程度越低，對資源的需求抑制程度就越高；否則，基礎(chǔ)平衡點的值越大，資源的利用程度就越高，對資源的需求抑制程度就越低。

當(dāng)T=a1=a2=…=an時，則節(jié)點緩存容量的利用可達到最高程度，對該資源的需求的抑制程度為0；當(dāng)T=b1=b2=…=bn時，則鏈路容量的利用可達到最高程度，對該資源的需求抑制程度為0。

2 仿真運算

假定目前網(wǎng)絡(luò)各資源容量或速率狀況如表7，其中an=128，bn=100，cn=1.1，具體運算步驟如下。

1)設(shè)經(jīng)過測定，分別以an、bn、cn為標(biāo)準(zhǔn)，相匹配的其他資源值如表8。

2)求基礎(chǔ)平衡點T。a1=128+75+0.9=203.9；b1=100+192+1.5=293.5；c1=1.1+260+85=346.1。Min{a1，b1，c1}=Min{203.9，293.5，346.1 }=230.9，因為a1最小，所以基礎(chǔ)平衡點T=an=128。

3)求“余地”資源的比例。求出與bn、cn、與an匹配值的差，m1=100-75=25，m2=1.1-0.9=0.2；求出各差值(m1、m2)占其對應(yīng)標(biāo)準(zhǔn)值(bn、cn)的百分比，δ1=(m1/bn)×100%=(25/100)×100%=25%，δ2=(m2/cn)×100%=(0.2/1.1)×100%=18%。比較δ1、δ2的大小，取最大值作為“余地”資源的比例。δ= Max{δ1，δ2}=Max{25%,18%}=25%。

4)計算當(dāng)前狀態(tài)下，各類不同層次的資源使用比例見表9。

5)確定對網(wǎng)絡(luò)各資源的需求的抑制比例，見表10。

表7 網(wǎng)絡(luò)資源容量速率情況表Tab.7 Capacity rate situation of network resource

表8 標(biāo)準(zhǔn)匹配資源值測算表Tab.8 Value measurement of standard matching resource

表9 當(dāng)前狀態(tài)下各類不同層次的資源使用比例測算表Tab.9 Calculation of utilization ratio of various resources under the current state

注：1.128×(1-25%)/512×100%=18.75%；2.128×(1-25%)/480×100%=20%；3.1-25%=75%；4.75×(1-25%)/1 000×100%=5.625%；5.75×(1-25%)/900×100%=6.25%；6.75×(1-25%)/100×100%=56.25%；7.0.9×(1-25%)/40×100%=1.69%；8.0.9×(1-25%)/35×100%=1.93%；9.0.9×(1-25%)/1.1×100%=61.4%

表10 網(wǎng)絡(luò)資源需求抑制比例測算表/%Tab.10 Proportion calculation of network resource demand restraint/%

計算表明，目前情況下，由于各資源的值層次落差很大，若要建立網(wǎng)絡(luò)的虛擬平衡，不但要保留相當(dāng)大的“余地”資源的比例(高達25%)用于化解擁塞，而且對各資源的需求的抑制程度較高，資源利用程度較低。低層次資源除節(jié)點緩存容量利用程度達到75%，其余均不到62%,而對其需求的抑制程度均在25%以上。高層次資源利用程度更低，均不及20%，而對其資源需求的抑制程度均在80%以上。由此可見，在實現(xiàn)網(wǎng)絡(luò)上的虛擬平衡條件下，縮小資源各層次的落差，減少資源的層次數(shù)是解決問題的關(guān)鍵。只有這樣，才能縮小“余地”資源的比例，提高資源的利用程度，從而降低對資源需求的抑制比例。而要做到這一點，除限制低容量資源的利用外，網(wǎng)絡(luò)資源統(tǒng)一配置十分必要。

3 結(jié)束語

這種擁塞控制新算法，首先通過網(wǎng)絡(luò)各資源按照一定標(biāo)準(zhǔn)進行排序；然后根據(jù)各資源匹配值，求出網(wǎng)絡(luò)資源的基礎(chǔ)平衡點；根據(jù)網(wǎng)絡(luò)資源的基礎(chǔ)平衡點，確定并計算出“余地”資源的比例；根據(jù)基礎(chǔ)平衡點來確定“余地”資源比例，計算出各網(wǎng)絡(luò)資源的使用程度，進而確定對資源需求的抑制程度。

采用此算法，網(wǎng)絡(luò)運行中資源各部分供給與需求相對平衡，再加上設(shè)有 “余地” 資源以防不測，網(wǎng)絡(luò)將更少發(fā)生擁塞，甚至不發(fā)生擁塞；由于在網(wǎng)絡(luò)中實現(xiàn)了資源的基本匹配和相對公平，網(wǎng)絡(luò)性能十分穩(wěn)定，出現(xiàn)數(shù)據(jù)丟失和信息錯傳的概率極小，可以提供高質(zhì)量的信息傳輸；在一定程度上也遏制了“黑客”對網(wǎng)絡(luò)的惡意攻擊，對網(wǎng)絡(luò)安全起到積極的保護作用；就網(wǎng)絡(luò)系統(tǒng)的整體資源而言，將獲得較高的運營效率和較好的經(jīng)濟效益。但在各資源匹配程度較差的情況下，會導(dǎo)致一些高性能資源的利用程度較低。若通過協(xié)議方式或者統(tǒng)一配置資源的方式，縮小各資源性能配置上的差異，則可以解決這一問題。