基于網(wǎng)絡(luò)擁塞問(wèn)題的三大擁塞避免技術(shù)探究

◆龐雙龍

（廣東創(chuàng)新科技職業(yè)學(xué)院信息工程學(xué)院 廣東 523960）

基于網(wǎng)絡(luò)擁塞問(wèn)題的三大擁塞避免技術(shù)探究

◆龐雙龍

（廣東創(chuàng)新科技職業(yè)學(xué)院信息工程學(xué)院 廣東 523960）

隨著科學(xué)技術(shù)的的進(jìn)步，越來(lái)越多的用戶加入互聯(lián)網(wǎng)去獲取資源，一定程度造成網(wǎng)絡(luò)擁塞的狀態(tài)，網(wǎng)絡(luò)的吞吐量也會(huì)迅速下降，所以如何解決網(wǎng)絡(luò)擁塞問(wèn)題對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展至關(guān)重要。本文介紹了三種擁塞避免的方法，并對(duì)其特點(diǎn)進(jìn)行了比較分析，僅供廣大讀者參考。

計(jì)算機(jī)網(wǎng)絡(luò); 吞吐量; 擁塞避免

0 前言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，人們對(duì)網(wǎng)絡(luò)資源的競(jìng)爭(zhēng)也在加劇。這種競(jìng)爭(zhēng)會(huì)影響網(wǎng)絡(luò)的性能。雖然在負(fù)載很輕的時(shí)候所有的網(wǎng)絡(luò)都能夠正常的工作，但是大規(guī)模網(wǎng)絡(luò)時(shí)有一些問(wèn)題也會(huì)隨之暴露出來(lái)。在網(wǎng)絡(luò)面臨的所有問(wèn)題中，最常見的也是最值得注意的就是數(shù)據(jù)的丟失問(wèn)題，雖然在一個(gè)網(wǎng)絡(luò)中造成數(shù)據(jù)丟失的原因有很多，但網(wǎng)絡(luò)擁塞是最常見的原因。簡(jiǎn)單來(lái)講，當(dāng)用戶對(duì)資源的索取越來(lái)越多，當(dāng)對(duì)資源的需求超出了網(wǎng)絡(luò)的容量時(shí)，網(wǎng)絡(luò)中大量排隊(duì)的數(shù)據(jù)導(dǎo)致報(bào)文丟失時(shí)便會(huì)產(chǎn)生擁塞。在擁塞期間，網(wǎng)絡(luò)的吞吐量可能會(huì)降至零，而路徑延遲會(huì)變得非常高。擁塞避免技術(shù)能夠讓網(wǎng)絡(luò)在一個(gè)延遲低、吞吐量很高的狀態(tài)下運(yùn)行并能夠預(yù)防網(wǎng)絡(luò)進(jìn)入擁塞的狀態(tài)。

1 DECbit

DECbit是早期的擁塞避免方法之一。該方法要求網(wǎng)絡(luò)交換機(jī)與流量源共同協(xié)作。在DECbit方法中，當(dāng)網(wǎng)絡(luò)交換機(jī)的平均隊(duì)列長(zhǎng)度大于或者等于1時(shí)即被視為擁塞。處于擁塞狀態(tài)的網(wǎng)絡(luò)交換機(jī)會(huì)在數(shù)據(jù)包的網(wǎng)絡(luò)層頭部設(shè)置擁塞指示位。非擁塞交換機(jī)則不會(huì)對(duì)擁塞指示位字段進(jìn)行任何操作。這就需要在數(shù)據(jù)包的頭部添加一個(gè)擁塞位。如果在數(shù)據(jù)包到達(dá)時(shí),路由器的平均隊(duì)列長(zhǎng)度大于或者等于1,那么路由器就將這個(gè)數(shù)據(jù)包中的擁塞位設(shè)置為1。在目的端擁塞的值將被復(fù)制到確認(rèn)消息的傳輸層首部中。該確認(rèn)消息稍后會(huì)被發(fā)送至源端。每次經(jīng)歷兩個(gè)往返時(shí)間，源就會(huì)更新下自己的窗口。如果檢測(cè)到在這段時(shí)間內(nèi)至少有50%的確認(rèn)消息將擁塞位設(shè)置為1,那么窗口大小將從當(dāng)前的congestionW減小至β* congestionW。否則擁塞窗口的數(shù)值將會(huì)增加至congestionW+α，其中β=0.875，α=1。該方案占用了最小的網(wǎng)絡(luò)反饋量，即只利用網(wǎng)絡(luò)層首部中的一個(gè)比特位來(lái)指出擁塞,能夠適應(yīng)網(wǎng)絡(luò)中發(fā)生的短暫性變化,并且使網(wǎng)絡(luò)收斂到高效的運(yùn)行狀態(tài)。

2 隨機(jī)早期檢測(cè)

隨機(jī)早期檢測(cè)（Random Early Detection，RED）方法由Sally Floyd 與 VanJacobson在20世紀(jì)90年代早期提出來(lái)的，RED與DECbit技術(shù)類似。他們通過(guò)程序設(shè)定每臺(tái)路由器對(duì)自身的隊(duì)列長(zhǎng)度進(jìn)行監(jiān)測(cè)，當(dāng)監(jiān)測(cè)到擁塞即將發(fā)生時(shí)，就會(huì)通知源端調(diào)整窗口大小。它們的主要區(qū)別有兩方面，首先RED不像DECbit一樣，不會(huì)通過(guò)向源端發(fā)送一個(gè)擁塞通知的方法來(lái)很明確的告知擁塞即將發(fā)生。通常RED會(huì)通過(guò)丟棄自身的一個(gè)數(shù)據(jù)包來(lái)向源端進(jìn)行暗示，因此源端能夠通過(guò)隨后的超時(shí)事件以及冗余確認(rèn)消息有效的了解到擁塞的發(fā)生。其次兩者的第二個(gè)區(qū)別在于RED確定在什么時(shí)候丟棄數(shù)據(jù)包以及丟棄哪一個(gè)數(shù)據(jù)包的細(xì)節(jié)問(wèn)題，舉一個(gè)簡(jiǎn)單的例子:在先進(jìn)先出（FIFO）中與其等到隊(duì)列全滿后才不得不丟棄隨后到達(dá)的每一個(gè)數(shù)據(jù)包，我們不如在隊(duì)列長(zhǎng)度超過(guò)某一個(gè)丟棄值時(shí)以一定的概率來(lái)決定是否丟棄每一個(gè)到達(dá)的數(shù)據(jù)包。這一思想被稱作早期隨機(jī)丟棄（RED）。RED算法定義了如何監(jiān)控隊(duì)列長(zhǎng)度以及何時(shí)丟棄數(shù)據(jù)包的具體方法。RED被設(shè)計(jì)用于和TCP一起工作。TCP是通過(guò)超時(shí)、冗余確認(rèn)消息等來(lái)檢測(cè)當(dāng)前的擁塞。RED字母縮寫中的“early”表示希望路由器在不得不丟棄數(shù)據(jù)包之前就開始丟棄數(shù)據(jù)包，這樣能快速地通知源端減小擁塞窗口，從而獲得比正常狀況更快的速率。也就是說(shuō)路由器在其緩沖區(qū)空間完全耗盡之前就丟棄了一些數(shù)據(jù)包，從而迫使源端降低發(fā)送速率避免此后丟棄大量的數(shù)據(jù)包。值得我們注意的是，如果將被丟棄的數(shù)據(jù)包用標(biāo)記的方法來(lái)代替，那么就可以簡(jiǎn)單的將顯式的反饋機(jī)制與RED方法結(jié)合在一起協(xié)同工作，至于RED方法是如何決定丟棄數(shù)據(jù)包的時(shí)間以及怎樣去選擇丟棄的數(shù)據(jù)包，我們可以通過(guò)一個(gè)簡(jiǎn)單的先進(jìn)先出隊(duì)列來(lái)舉例說(shuō)明。RED在隊(duì)列的長(zhǎng)度超過(guò)某一丟棄水平時(shí)，就會(huì)以一定的概率來(lái)決定是否丟棄每個(gè)到達(dá)的數(shù)據(jù)包，而不是一直等到隊(duì)列全滿后才不得不丟棄隨后到達(dá)的每個(gè)數(shù)據(jù)包。

3 基于源的擁塞避免

RED與DECbit這兩種擁塞避免技術(shù)都依賴于路由器和交換機(jī)。它們有時(shí)又被稱之為基于路由器的擁塞避免技術(shù)，在此類方法中，源端通過(guò)對(duì)往返時(shí)延RTT數(shù)值變化的監(jiān)控來(lái)檢測(cè)擁塞的到來(lái)，這類技術(shù)的基本思想是通過(guò)觀測(cè)網(wǎng)絡(luò)中的若干信號(hào)，從而得知某臺(tái)路由器的隊(duì)列正在增長(zhǎng)，如果不對(duì)這種情況采取相應(yīng)措施就會(huì)產(chǎn)生擁塞。而基于源的擁塞避免描述了一種從終端終端主機(jī)檢測(cè)擁塞初級(jí)階段（發(fā)生在丟包之前）的策略。TCP Vegas是Brakmo提出的一種新的TCP實(shí)現(xiàn)。Vegas將測(cè)量到的吞吐量與期望值，或者說(shuō)是與理想的吞吐量做比較。Vegas使用了一種新的重傳機(jī)制。這是在快速重傳的基礎(chǔ)上做出的一種改進(jìn)方案。在原始的快速重傳機(jī)制中，三個(gè)冗余的確認(rèn)消息表明丟包，這樣一個(gè)數(shù)據(jù)包就能在超時(shí)之前被重新傳輸。Vegas為每個(gè)發(fā)送出去的數(shù)據(jù)包都設(shè)置了一個(gè)時(shí)間戳，從而在接收到每一個(gè)確認(rèn)消息時(shí)都計(jì)算出往返時(shí)間。當(dāng)收到一個(gè)冗余的確認(rèn)消息時(shí)，Vegas都會(huì)檢查數(shù)據(jù)包的時(shí)間戳與當(dāng)前時(shí)間的差值是否大于超時(shí)時(shí)間。如果大于，那么Vegas就會(huì)重傳該數(shù)據(jù)包，從而不再等待第三個(gè)冗余確認(rèn)消息的到來(lái)。該方法是對(duì)Reno算法的一種改進(jìn)。在TCP Reno中窗口在很多情況下可能會(huì)比較小，因此源端可能不會(huì)接收到三個(gè)冗余的確認(rèn)消息，或者確認(rèn)消息可能會(huì)丟在網(wǎng)絡(luò)中。根據(jù)接收到的非冗余確認(rèn)消息，若該消息是重傳之后收到的第一個(gè)或第二個(gè)確認(rèn)消息，Reno會(huì)檢查從數(shù)據(jù)包發(fā)出之后經(jīng)過(guò)的時(shí)間是否大于超時(shí)時(shí)間，如果大于就會(huì)重傳數(shù)據(jù)包，如果有任何數(shù)據(jù)包在重傳之后丟失，那么這些數(shù)據(jù)包就會(huì)被直接重傳而不必等待冗余確認(rèn)消息。為了避免擁塞，Vegas將實(shí)際的吞吐量與期望的吞吐量進(jìn)行比較。期望的吞吐量被定義為此前檢測(cè)到的所有吞吐量的最小值。實(shí)際吞吐量則是指從發(fā)出一個(gè)數(shù)據(jù)包到接收到對(duì)應(yīng)確認(rèn)消息所經(jīng)歷的時(shí)間內(nèi)傳輸出的字節(jié)數(shù)與該數(shù)據(jù)包往返時(shí)間的比值。然后Vegas將實(shí)際吞吐量和期望吞吐率的差值與閾值α和β進(jìn)行比較。當(dāng)差值小于α?xí)r，窗口大小將線性地增長(zhǎng); 當(dāng)差值大于β時(shí)，窗口大小將線性地減小。Reno的慢啟動(dòng)機(jī)制會(huì)導(dǎo)致許多數(shù)據(jù)包的丟失。因?yàn)榇翱诖笮≡诿總€(gè)往返時(shí)間內(nèi)是成倍增加的，一旦突破瓶頸而最終超載，那么期望的損失將是當(dāng)前窗口大小的一半。由于網(wǎng)絡(luò)帶寬的增加，那么慢啟動(dòng)所造成丟失數(shù)據(jù)包的數(shù)量也會(huì)隨之增加。Brakmo提出了一種改進(jìn)的慢啟動(dòng)機(jī)制，其中每隔兩個(gè)往返時(shí)間窗口大小才翻一倍，因此在每?jī)蓚€(gè)往返時(shí)間內(nèi)窗口的大小都不會(huì)改變，這使得期望吞吐率與實(shí)際吞吐率的比較更加準(zhǔn)確。它不同之處在于需要設(shè)定一個(gè)新的閾值，算法會(huì)在新的閾值點(diǎn)前切換線性的增長(zhǎng)和減小。

4 結(jié)語(yǔ)

綜上所述，隨著社會(huì)的不斷進(jìn)步，計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)迅猛發(fā)展，并不斷涌現(xiàn)出新的技術(shù)。在今后的發(fā)展過(guò)程中應(yīng)該加大對(duì)網(wǎng)絡(luò)擁塞避免方面的研發(fā)力度，使其技術(shù)水平得到大幅度的提高，從而提升計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展水平。

[1][印]Narasimha Karumanchi A.DamodaramM.Sreen ivasa Rao.許昱偉等譯.計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)教程[M].北京:機(jī)械工業(yè)出版社，2016.

[2][美]L.LarryL.Peterson S.BruceS.Davie.王勇，張飛龍.等譯.計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)方法[M].北京:機(jī)械工業(yè)出版社，2015.

[3][美]W.Richard Stevens.范建華，胥光輝等譯.TCP/IP詳解卷1協(xié)議[M].北京:機(jī)械工業(yè)出版社，2014.

[4][美]Andrew S.Tanenbaum DavidJ.Wetherall.嚴(yán)偉，潘愛民.譯.計(jì)算機(jī)網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2012.

[5]吳功宜.計(jì)算機(jī)網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2007.