一、引言
目前,網(wǎng)格的發(fā)展越來(lái)越受到大家的重視,它們可以在不同國(guó)家甚至不同州的機(jī)器之間傳輸甚至到達(dá)幾千G字節(jié)的大文件,將大規(guī)模的數(shù)據(jù)處理分散到世界范圍的各個(gè)組織中.網(wǎng)格的應(yīng)用需要高速遠(yuǎn)距離網(wǎng)絡(luò)的支持,這可能需要網(wǎng)絡(luò)速度達(dá)到622Mbit/s或是更高.在這種情況下,傳統(tǒng)的TCP擁塞控制算法就不太適用了.這主要有以下三方面的原因:
(1)傳統(tǒng)的TCP擁塞控制機(jī)制在高速網(wǎng)絡(luò)中反應(yīng)性比較差,這是因?yàn)門CP在高速網(wǎng)絡(luò)中對(duì)分組丟失的反應(yīng)要敏感得多.這主要是由于它的擁塞避免算法是基于AIMD(Additive Increase Multiplicative Decrease,和式增加積式減少)的.所以一個(gè)分組的丟失在高速網(wǎng)絡(luò)中所造成的后果是很嚴(yán)重的:一個(gè)分組丟失被檢測(cè)出來(lái)之后,TCP連接就會(huì)將帶寬減半(積式減少),這樣就會(huì)不止花上幾百毫秒或是多達(dá)幾秒鐘,甚至花上幾分鐘或是幾個(gè)小時(shí)來(lái)恢復(fù)所有的可用帶寬(和式增加).另外,慢啟動(dòng)也會(huì)造成TCP在高速網(wǎng)絡(luò)中性能的下降,但是它的影響要比擁塞避免小點(diǎn).因?yàn)橥ㄟ^(guò)三個(gè)重復(fù)的ACK來(lái)判斷分組丟失的情況要比超時(shí)經(jīng)常得多,因此TCP連接會(huì)花費(fèi)大多數(shù)時(shí)間在擁塞避免算法上.
(2)傳統(tǒng)的TCP總是把分組丟失解釋為擁塞,而假定鏈路錯(cuò)誤造成的分組丟失是可以忽略的,但是在高速網(wǎng)絡(luò)中,這種假設(shè)是不成立的.當(dāng)數(shù)據(jù)傳輸速率比較高時(shí),鏈路錯(cuò)誤是不能忽略的.由鏈路錯(cuò)誤引起的分組丟失和由網(wǎng)絡(luò)擁塞引起的分組丟失的可能性是相同的.因此,不能籠統(tǒng)地認(rèn)為分組丟失都是由網(wǎng)絡(luò)擁塞引起的.因此,當(dāng)一個(gè)TCP分組丟失后我們不應(yīng)該認(rèn)為就是出現(xiàn)了網(wǎng)絡(luò)擁塞,擁塞的判斷需要兩個(gè)連續(xù)的分組丟失.
(3)傳統(tǒng)的TCP不能使用網(wǎng)絡(luò)鏈路的所有容量.這主要是由于在AIMD算法中,TCP從一個(gè)分組丟失到帶寬的恢復(fù)所用的時(shí)間比較長(zhǎng).這是目前所有TCP版本(TCPTahoe、TCPReno、New-Reno、SACK、Vegas等)的一個(gè)固有的問(wèn)題.而高速遠(yuǎn)距離網(wǎng)絡(luò)的造價(jià)是比較高的,所以對(duì)容量的浪費(fèi)是不可原諒的.
針對(duì)以上TCP傳統(tǒng)算法的缺陷,網(wǎng)格計(jì)算中的TCP擁塞控制提出了一個(gè)新的帶寬使用的公平性原則和增減算法,對(duì)于克服傳統(tǒng)TCP在快速遠(yuǎn)距離網(wǎng)絡(luò)中的不足起到了很好的作用.
二、帶寬減少算法
在適用于網(wǎng)格應(yīng)用的快速遠(yuǎn)距離網(wǎng)絡(luò)中,可以假設(shè)連接的可用帶寬在相當(dāng)長(zhǎng)的時(shí)間(大致是10min到1h)內(nèi)是保持不變的,這個(gè)假設(shè)對(duì)與其他類型的網(wǎng)絡(luò)基本上也是成立的.根據(jù)這個(gè)假設(shè),可以做如下的近似:對(duì)于一個(gè)長(zhǎng)時(shí)間的TCP連接,可用帶寬ABW可以看作是一些分段表示的常數(shù).
根據(jù)以上的簡(jiǎn)化模型,我們可以對(duì)TCP和式增加積式減少的帶寬增減算法進(jìn)行修改.在用于網(wǎng)格計(jì)算的TCP擁塞控制中,當(dāng)一個(gè)TCP連接檢測(cè)到網(wǎng)絡(luò)擁塞時(shí)(用于網(wǎng)格計(jì)算的TCP擁塞控制,對(duì)于擁塞的判斷標(biāo)準(zhǔn)是在一個(gè)相同的擁塞窗口中至少有兩個(gè)連續(xù)的分組丟失,只有一個(gè)分組丟失被認(rèn)為是鏈路錯(cuò)誤),并不是將帶寬減半,而是減少ABWi-ABWi+1,ABWi+1由式(1)得出 =-1
(1)
式中 ABWi- 在階段i的可用帶寬;
C- 鏈路容量的估計(jì)值; ABWi在較長(zhǎng)時(shí)間(一般式10min到1h)內(nèi)是常數(shù).由于 ABWi是C的一部分,所以
A i,E αi,(0≤αi≤1)∧(ABWi=αiC)(2)
由式(1)和式(2)可以得到
αi+1= (3)
ABWi-ABWi+1= (4)
式(4)就是用于網(wǎng)格計(jì)算的TCP擁塞控制,采用新的減少帶寬的算法,相應(yīng)傳統(tǒng)TCP的減少算法可以由以下表示
ABWJi-ABWJi+1== (5)
由式(5)可以得出
αi+1=αi /2 (6)
當(dāng)αi=5%時(shí),由(3)式可得αi+1=4.76%,而由(6)式得到αi+1=2.5%,如果C=622Mbit/s,那么新的算法可以節(jié)省14Mbit/s的帶寬;當(dāng)αi=20%時(shí),由(3)式可得αi+1=16.7%,而由(6)式得到αi+1=10%,如果C=622Mbit/s,那么新的算法可以節(jié)省41Mbit/s的帶寬.所以,當(dāng)擁塞發(fā)生后,新的算法減少的帶寬比較少,這樣恢復(fù)起來(lái)也比較快.當(dāng)αi=0或αi=100%時(shí),也就是當(dāng)鏈路中只有一個(gè)或有無(wú)限多TCP流時(shí),兩種算法取得一致.但是,在網(wǎng)格應(yīng)用的網(wǎng)絡(luò)中,這兩種情況出現(xiàn)的比較少.
三、帶寬增加算法
用于網(wǎng)格計(jì)算的TCP擁塞控制所使用的帶寬增加算法有些復(fù)雜,它可以分為五種情況來(lái)分析:
(1)當(dāng)鏈路剛剛經(jīng)歷了擁塞,并且我們假定這個(gè)擁塞現(xiàn)象是暫時(shí)的,我們首先根據(jù)式(4)來(lái)減少帶寬,然后再通過(guò)二分檢索法增加帶寬到以前的穩(wěn)定狀態(tài):ABWi.如果在這個(gè)過(guò)程中沒(méi)有新的分組丟失,那么TCP連接就應(yīng)該保持在階段i,然后根據(jù)情況(3)來(lái)處理;如果我們檢測(cè)到同一個(gè)擁塞窗口中至少有兩個(gè)分組丟失,那么TCP連接就應(yīng)該從階段過(guò)渡i到階段i+1,并且根據(jù)情況(2)來(lái)處理.
(2)當(dāng)網(wǎng)絡(luò)出現(xiàn)新的擁塞問(wèn)題時(shí),我們來(lái)得到一個(gè)新的帶寬穩(wěn)定值A(chǔ)BWi+1,ABWi+1要比ABWi小.在這種方法中,增加和減少帶寬都使用二分檢索法,一旦有分組丟失我們就減少帶寬,否則就增加帶寬.這種方法能比較迅速地使可用帶寬穩(wěn)定到ABWi+1.網(wǎng)絡(luò)穩(wěn)定在階段i+1后,在根據(jù)情況(3)來(lái)處理.
(3)在這種情況下,TCP連接以速率ABWi傳輸數(shù)據(jù).當(dāng)檢測(cè)到擁塞發(fā)生時(shí),就根據(jù)情況(1)來(lái)處理;如果直到TCP占用計(jì)時(shí)器(它的值由經(jīng)驗(yàn)獲得,但一般希望是10min到1h)關(guān)閉仍沒(méi)有擁塞發(fā)生,就根據(jù)情況(4)來(lái)處理.
(4)TCP已經(jīng)以速率ABWi傳輸數(shù)據(jù)很長(zhǎng)時(shí)間而沒(méi)有檢測(cè)到擁塞,因此我們希望可用帶寬增加,進(jìn)入一個(gè)新的階段i+1,在這個(gè)階段ABWi+1應(yīng)該比現(xiàn)在的ABWi大.所以,一旦TCP占用計(jì)時(shí)器關(guān)閉,我們就開(kāi)始增加帶寬到ABWi+1,ABWi+1可以根據(jù)式(7)獲得=+1 (7)
如果在這個(gè)過(guò)程中檢測(cè)到擁塞,就根據(jù)情況(1)來(lái)處理.
(5)建立一個(gè)新的TCP連接,并且為可用帶寬ABW0賦初始值為鏈路的容量C,然后再根據(jù)第(2)種情況來(lái)分析.
四、結(jié)束語(yǔ)
以上是用于網(wǎng)格計(jì)算的TCP擁塞控制所使用的新的帶寬增減的算法,它克服了傳統(tǒng)的AIMD算法的保守性,可以較充分地使用鏈路容量,所以在高速遠(yuǎn)距離網(wǎng)絡(luò)中,它的效率比較好.但是這種算法還存在著一些缺陷:鏈路容量C的估計(jì)總是近似的,而且精確度也未知;容量的估計(jì)需要花費(fèi)時(shí)間,對(duì)于短時(shí)存在的TCP連接,有可能用于容量估計(jì)的時(shí)間比連接存在的時(shí)間還要長(zhǎng);實(shí)際的網(wǎng)絡(luò)中,路由是會(huì)改變的,所以發(fā)送端計(jì)算出的容量有可能和實(shí)際TCP連接使用的容量不一致.
目前,網(wǎng)格的發(fā)展越來(lái)越受到大家的重視,它們可以在不同國(guó)家甚至不同州的機(jī)器之間傳輸甚至到達(dá)幾千G字節(jié)的大文件,將大規(guī)模的數(shù)據(jù)處理分散到世界范圍的各個(gè)組織中.網(wǎng)格的應(yīng)用需要高速遠(yuǎn)距離網(wǎng)絡(luò)的支持,這可能需要網(wǎng)絡(luò)速度達(dá)到622Mbit/s或是更高.在這種情況下,傳統(tǒng)的TCP擁塞控制算法就不太適用了.這主要有以下三方面的原因:
(1)傳統(tǒng)的TCP擁塞控制機(jī)制在高速網(wǎng)絡(luò)中反應(yīng)性比較差,這是因?yàn)門CP在高速網(wǎng)絡(luò)中對(duì)分組丟失的反應(yīng)要敏感得多.這主要是由于它的擁塞避免算法是基于AIMD(Additive Increase Multiplicative Decrease,和式增加積式減少)的.所以一個(gè)分組的丟失在高速網(wǎng)絡(luò)中所造成的后果是很嚴(yán)重的:一個(gè)分組丟失被檢測(cè)出來(lái)之后,TCP連接就會(huì)將帶寬減半(積式減少),這樣就會(huì)不止花上幾百毫秒或是多達(dá)幾秒鐘,甚至花上幾分鐘或是幾個(gè)小時(shí)來(lái)恢復(fù)所有的可用帶寬(和式增加).另外,慢啟動(dòng)也會(huì)造成TCP在高速網(wǎng)絡(luò)中性能的下降,但是它的影響要比擁塞避免小點(diǎn).因?yàn)橥ㄟ^(guò)三個(gè)重復(fù)的ACK來(lái)判斷分組丟失的情況要比超時(shí)經(jīng)常得多,因此TCP連接會(huì)花費(fèi)大多數(shù)時(shí)間在擁塞避免算法上.
(2)傳統(tǒng)的TCP總是把分組丟失解釋為擁塞,而假定鏈路錯(cuò)誤造成的分組丟失是可以忽略的,但是在高速網(wǎng)絡(luò)中,這種假設(shè)是不成立的.當(dāng)數(shù)據(jù)傳輸速率比較高時(shí),鏈路錯(cuò)誤是不能忽略的.由鏈路錯(cuò)誤引起的分組丟失和由網(wǎng)絡(luò)擁塞引起的分組丟失的可能性是相同的.因此,不能籠統(tǒng)地認(rèn)為分組丟失都是由網(wǎng)絡(luò)擁塞引起的.因此,當(dāng)一個(gè)TCP分組丟失后我們不應(yīng)該認(rèn)為就是出現(xiàn)了網(wǎng)絡(luò)擁塞,擁塞的判斷需要兩個(gè)連續(xù)的分組丟失.
(3)傳統(tǒng)的TCP不能使用網(wǎng)絡(luò)鏈路的所有容量.這主要是由于在AIMD算法中,TCP從一個(gè)分組丟失到帶寬的恢復(fù)所用的時(shí)間比較長(zhǎng).這是目前所有TCP版本(TCPTahoe、TCPReno、New-Reno、SACK、Vegas等)的一個(gè)固有的問(wèn)題.而高速遠(yuǎn)距離網(wǎng)絡(luò)的造價(jià)是比較高的,所以對(duì)容量的浪費(fèi)是不可原諒的.
針對(duì)以上TCP傳統(tǒng)算法的缺陷,網(wǎng)格計(jì)算中的TCP擁塞控制提出了一個(gè)新的帶寬使用的公平性原則和增減算法,對(duì)于克服傳統(tǒng)TCP在快速遠(yuǎn)距離網(wǎng)絡(luò)中的不足起到了很好的作用.
二、帶寬減少算法
在適用于網(wǎng)格應(yīng)用的快速遠(yuǎn)距離網(wǎng)絡(luò)中,可以假設(shè)連接的可用帶寬在相當(dāng)長(zhǎng)的時(shí)間(大致是10min到1h)內(nèi)是保持不變的,這個(gè)假設(shè)對(duì)與其他類型的網(wǎng)絡(luò)基本上也是成立的.根據(jù)這個(gè)假設(shè),可以做如下的近似:對(duì)于一個(gè)長(zhǎng)時(shí)間的TCP連接,可用帶寬ABW可以看作是一些分段表示的常數(shù).
根據(jù)以上的簡(jiǎn)化模型,我們可以對(duì)TCP和式增加積式減少的帶寬增減算法進(jìn)行修改.在用于網(wǎng)格計(jì)算的TCP擁塞控制中,當(dāng)一個(gè)TCP連接檢測(cè)到網(wǎng)絡(luò)擁塞時(shí)(用于網(wǎng)格計(jì)算的TCP擁塞控制,對(duì)于擁塞的判斷標(biāo)準(zhǔn)是在一個(gè)相同的擁塞窗口中至少有兩個(gè)連續(xù)的分組丟失,只有一個(gè)分組丟失被認(rèn)為是鏈路錯(cuò)誤),并不是將帶寬減半,而是減少ABWi-ABWi+1,ABWi+1由式(1)得出 =-1
(1)
式中 ABWi- 在階段i的可用帶寬;
C- 鏈路容量的估計(jì)值; ABWi在較長(zhǎng)時(shí)間(一般式10min到1h)內(nèi)是常數(shù).由于 ABWi是C的一部分,所以
A i,E αi,(0≤αi≤1)∧(ABWi=αiC)(2)
由式(1)和式(2)可以得到
αi+1= (3)
ABWi-ABWi+1= (4)
式(4)就是用于網(wǎng)格計(jì)算的TCP擁塞控制,采用新的減少帶寬的算法,相應(yīng)傳統(tǒng)TCP的減少算法可以由以下表示
ABWJi-ABWJi+1== (5)
由式(5)可以得出
αi+1=αi /2 (6)
當(dāng)αi=5%時(shí),由(3)式可得αi+1=4.76%,而由(6)式得到αi+1=2.5%,如果C=622Mbit/s,那么新的算法可以節(jié)省14Mbit/s的帶寬;當(dāng)αi=20%時(shí),由(3)式可得αi+1=16.7%,而由(6)式得到αi+1=10%,如果C=622Mbit/s,那么新的算法可以節(jié)省41Mbit/s的帶寬.所以,當(dāng)擁塞發(fā)生后,新的算法減少的帶寬比較少,這樣恢復(fù)起來(lái)也比較快.當(dāng)αi=0或αi=100%時(shí),也就是當(dāng)鏈路中只有一個(gè)或有無(wú)限多TCP流時(shí),兩種算法取得一致.但是,在網(wǎng)格應(yīng)用的網(wǎng)絡(luò)中,這兩種情況出現(xiàn)的比較少.
三、帶寬增加算法
用于網(wǎng)格計(jì)算的TCP擁塞控制所使用的帶寬增加算法有些復(fù)雜,它可以分為五種情況來(lái)分析:
(1)當(dāng)鏈路剛剛經(jīng)歷了擁塞,并且我們假定這個(gè)擁塞現(xiàn)象是暫時(shí)的,我們首先根據(jù)式(4)來(lái)減少帶寬,然后再通過(guò)二分檢索法增加帶寬到以前的穩(wěn)定狀態(tài):ABWi.如果在這個(gè)過(guò)程中沒(méi)有新的分組丟失,那么TCP連接就應(yīng)該保持在階段i,然后根據(jù)情況(3)來(lái)處理;如果我們檢測(cè)到同一個(gè)擁塞窗口中至少有兩個(gè)分組丟失,那么TCP連接就應(yīng)該從階段過(guò)渡i到階段i+1,并且根據(jù)情況(2)來(lái)處理.
(2)當(dāng)網(wǎng)絡(luò)出現(xiàn)新的擁塞問(wèn)題時(shí),我們來(lái)得到一個(gè)新的帶寬穩(wěn)定值A(chǔ)BWi+1,ABWi+1要比ABWi小.在這種方法中,增加和減少帶寬都使用二分檢索法,一旦有分組丟失我們就減少帶寬,否則就增加帶寬.這種方法能比較迅速地使可用帶寬穩(wěn)定到ABWi+1.網(wǎng)絡(luò)穩(wěn)定在階段i+1后,在根據(jù)情況(3)來(lái)處理.
(3)在這種情況下,TCP連接以速率ABWi傳輸數(shù)據(jù).當(dāng)檢測(cè)到擁塞發(fā)生時(shí),就根據(jù)情況(1)來(lái)處理;如果直到TCP占用計(jì)時(shí)器(它的值由經(jīng)驗(yàn)獲得,但一般希望是10min到1h)關(guān)閉仍沒(méi)有擁塞發(fā)生,就根據(jù)情況(4)來(lái)處理.
(4)TCP已經(jīng)以速率ABWi傳輸數(shù)據(jù)很長(zhǎng)時(shí)間而沒(méi)有檢測(cè)到擁塞,因此我們希望可用帶寬增加,進(jìn)入一個(gè)新的階段i+1,在這個(gè)階段ABWi+1應(yīng)該比現(xiàn)在的ABWi大.所以,一旦TCP占用計(jì)時(shí)器關(guān)閉,我們就開(kāi)始增加帶寬到ABWi+1,ABWi+1可以根據(jù)式(7)獲得=+1 (7)
如果在這個(gè)過(guò)程中檢測(cè)到擁塞,就根據(jù)情況(1)來(lái)處理.
(5)建立一個(gè)新的TCP連接,并且為可用帶寬ABW0賦初始值為鏈路的容量C,然后再根據(jù)第(2)種情況來(lái)分析.
四、結(jié)束語(yǔ)
以上是用于網(wǎng)格計(jì)算的TCP擁塞控制所使用的新的帶寬增減的算法,它克服了傳統(tǒng)的AIMD算法的保守性,可以較充分地使用鏈路容量,所以在高速遠(yuǎn)距離網(wǎng)絡(luò)中,它的效率比較好.但是這種算法還存在著一些缺陷:鏈路容量C的估計(jì)總是近似的,而且精確度也未知;容量的估計(jì)需要花費(fèi)時(shí)間,對(duì)于短時(shí)存在的TCP連接,有可能用于容量估計(jì)的時(shí)間比連接存在的時(shí)間還要長(zhǎng);實(shí)際的網(wǎng)絡(luò)中,路由是會(huì)改變的,所以發(fā)送端計(jì)算出的容量有可能和實(shí)際TCP連接使用的容量不一致.