楊 琦

(中國電子科技集團(tuán)公司第二十研究所,陜西 西安 710068)

0 引 言

隨著信息技術(shù)的快速發(fā)展，各個行業(yè)普遍對業(yè)務(wù)傳輸、信息交換效率方面提出了較高要求，因此性能優(yōu)越的業(yè)務(wù)傳輸組包算法成為提高傳輸效率的關(guān)鍵所在。

目前主流的分組包傳輸方法有以下2種：

應(yīng)答式分組包方法：發(fā)送端將要發(fā)送的業(yè)務(wù)包按閾值分割成小包，再進(jìn)行標(biāo)記，標(biāo)記依次為0，1，2，3，…，N。按順序進(jìn)行發(fā)送，即發(fā)送端發(fā)出第1包，接收端收到業(yè)務(wù)包后給予應(yīng)答，發(fā)送端再發(fā)第2包，…，依此類推，接收端在按順序收到業(yè)務(wù)的同時進(jìn)行組包。雖然這種方法可靠性高，不會出現(xiàn)分組包錯誤，但每發(fā)送一包，都需要等待對端的接收應(yīng)答，等待應(yīng)答花費(fèi)的時間較長，造成發(fā)送效率、組包效率較低。

全發(fā)送分組包方法：發(fā)送端同樣將要發(fā)送的業(yè)務(wù)包進(jìn)行分割并進(jìn)行標(biāo)記，發(fā)送端通過多個端口或者線程同時進(jìn)行發(fā)送，此時發(fā)送端不必按照順序發(fā)送業(yè)務(wù)包，發(fā)送每個業(yè)務(wù)包前也不用等待接收端的應(yīng)答，此時接收端不再是按順序接收。所有業(yè)務(wù)包發(fā)送完畢后，接收端再按照業(yè)務(wù)包標(biāo)記的順序進(jìn)行查找并組包。這種方法的優(yōu)點(diǎn)是業(yè)務(wù)包發(fā)送較快，但在進(jìn)行組包的過程中需要花費(fèi)大量的時間按順序查找業(yè)務(wù)包。

本算法的思想是發(fā)送端在發(fā)送業(yè)務(wù)包前，將業(yè)務(wù)包拆分并進(jìn)行特殊編號，在接收端通過建立業(yè)務(wù)矩陣將接收到的業(yè)務(wù)包放置在相應(yīng)位置，再按照設(shè)計的矩陣坐標(biāo)算法對接收到的業(yè)務(wù)包進(jìn)行快速組包，大大提高組包效率。

1 數(shù)學(xué)建模

1.1 業(yè)務(wù)特性

傳統(tǒng)的分組包算法將要發(fā)送的業(yè)務(wù)包按閾值拆分成若干個小包，分別標(biāo)記為0，1，2，3，…，2N-1，2N?？傆?N+1個業(yè)務(wù)包，如圖1所示。接收端對收到的業(yè)務(wù)包進(jìn)行遍歷，按照分包的順序重新將業(yè)務(wù)包進(jìn)行組合。

圖1 傳統(tǒng)業(yè)務(wù)包拆分示意圖

本算法從業(yè)務(wù)標(biāo)記、業(yè)務(wù)組包方式2個方面入手，借助二部圖染色的原理對全發(fā)送分組包進(jìn)行優(yōu)化。

將圖1中拆分后的業(yè)務(wù)包繼續(xù)標(biāo)記，分成0<0>1，1<1>2，2<2>3，3<3>4，…，XX+1，YY+1，ZZ+1，…，如圖2所示。

圖2 基于矩陣坐標(biāo)業(yè)務(wù)包拆分示意圖

括號內(nèi)為業(yè)務(wù)包的序號，括號左邊為輸入端號，括號右邊為輸出端號，將第一個業(yè)務(wù)包稱作包頭，最后一個業(yè)務(wù)包稱作尾包。除去頭包和尾包，每一包在查找自己位置的時候，可以找到2個合適的包。例如連續(xù)3個業(yè)務(wù)包，X包、Y包、Z包，我們將X和Z稱為Y包的上包和下包，因此只要找上包X和下包Z中的一個，就可以確定Y的位置。因此Y包可以從上游和下游2個位置同時找與它相通的包。接下來對每個業(yè)務(wù)包的輸入端和輸出端除以2，得到新的輸入端和輸出端。通過這種處理方法，可以將每個業(yè)務(wù)包的上包和下包與該業(yè)務(wù)包放置在業(yè)務(wù)矩陣的同行同列中，在計算過程中提高了組包效率。

1.2 算法步驟

步驟1：將圖2中每個業(yè)務(wù)包的下標(biāo)進(jìn)行分解，輸入端和輸出端對2進(jìn)行整除，以此得到0<0>0，0<1>1，1<1>1，…，將得到后的輸入端號的坐標(biāo)作為矩陣的行，輸出端號的坐標(biāo)作為矩陣的列，建立業(yè)務(wù)矩陣[2]，如圖3所示。

圖3 算法流程圖

步驟2：將每收到一個業(yè)務(wù)的輸入、輸出端口號按照步驟1的方法進(jìn)行處理，放置在N×N矩陣相應(yīng)的位置，每個業(yè)務(wù)在矩陣中的位置按C[i,j]進(jìn)行表示，i代表所在行，j代表所在列。待接收端將所有來自發(fā)送端的業(yè)務(wù)包收齊后，選擇業(yè)務(wù)矩陣中C[i,j](i0,i2N,j0,j2N)位置處的元素作為起始包。

步驟3：查詢到的業(yè)務(wù)包命名為C[i,j]。

(1) 若i=0，j=0，或i=2Nmod(2)，j=2Nmod(2)，繼續(xù)執(zhí)行步驟4。

(2) 若i，j均不為零或N，繼續(xù)執(zhí)行步驟5。

步驟4：組包完畢，停止查詢。

步驟5：判斷i和j的關(guān)系。

(1) 若i=j，則繼續(xù)查找C[i-1,j]，將該業(yè)務(wù)包放置于C[i,j]的左側(cè)進(jìn)行組包，然后取i=i-1，j=j,返回步驟3。同時查找C[i,j+1]。將該業(yè)務(wù)包放置于C[i,j]的右側(cè)進(jìn)行組包，然后取i=i，j=j+1，返回步驟3。

(2) 若i

(3) 若i>j，業(yè)務(wù)矩陣建立有誤，停止查詢并檢查業(yè)務(wù)矩陣建立是否存在問題。

算法流程圖如圖3所示。

使用業(yè)務(wù)矩陣的優(yōu)點(diǎn)在于當(dāng)接收端每收到一個業(yè)務(wù)包的同時，可以在業(yè)務(wù)矩陣中確定它的唯一位置，同時業(yè)務(wù)矩陣也確定了該業(yè)務(wù)包相關(guān)聯(lián)的上包和下包的位置，在進(jìn)行組包的時候就避免了大量的重復(fù)搜索，而且該業(yè)務(wù)包與其相鄰的業(yè)務(wù)包必然處于同行同列，可以從2個方向同時進(jìn)行查找，即使一個查找方向因?yàn)闃I(yè)務(wù)包未到來而產(chǎn)生中斷，另一個方向依然可以進(jìn)行查找組包從而大大提高組包的效率，該組包技術(shù)在業(yè)務(wù)包數(shù)量較大時查找效率較高。

以圖4為例，選擇業(yè)務(wù)包4，所在位置為C[2,2]按照次步驟進(jìn)行組包，組包順序如圖5所示。

圖4 業(yè)務(wù)矩陣示意圖

圖5 組包順序示意圖

2 仿真驗(yàn)證

下面通過VS2010軟件對算法的組包效率進(jìn)行驗(yàn)證，橫軸是接收端到來業(yè)務(wù)的百分比，縱軸是組包花費(fèi)的時間。業(yè)務(wù)包傳輸采用的技術(shù)手段來自于作者參與的項(xiàng)目。以業(yè)務(wù)包總量為10 Mb，每個業(yè)務(wù)包大小20 kb為例，作者進(jìn)行了500次仿真驗(yàn)證的情況下，得到的平均統(tǒng)計結(jié)果如圖6所示。在業(yè)務(wù)包到來數(shù)量逐漸增多的情況下，基于矩陣坐標(biāo)的組包算法的花費(fèi)時間要少于傳統(tǒng)的全發(fā)送組包算法。在業(yè)務(wù)量超過50%的情況下，基于矩陣坐標(biāo)的組包算法耗時出現(xiàn)下降，因?yàn)闃I(yè)務(wù)量較少的情況下，業(yè)務(wù)矩陣在查詢的過程中因?yàn)槿鄙贅I(yè)務(wù)包造成查詢中斷，只能不斷地重新遍歷查找未被組包的業(yè)務(wù)包，因此花費(fèi)時間較長。在到來業(yè)務(wù)增多的情況下，業(yè)務(wù)矩陣在查詢過程中出現(xiàn)查詢中斷的次數(shù)將大大減少，查找業(yè)務(wù)包的效率得到提高，因此組包耗時出現(xiàn)下降。

圖6 組包耗時對比圖

3 結(jié)束語

針對網(wǎng)絡(luò)通信過程中現(xiàn)有的分組包技術(shù)的缺陷，設(shè)計了一種新型適用于大容量業(yè)務(wù)包傳輸?shù)乃惴?。通過建立業(yè)務(wù)矩陣對分包過程進(jìn)行優(yōu)化，使用二部圖染色原理提高組包效率，并通過計算機(jī)軟件對算法進(jìn)行了仿真驗(yàn)證，證明該算法在業(yè)務(wù)量較大的情況下，改進(jìn)后的組包效率高于傳統(tǒng)算法。但在業(yè)務(wù)量稀疏的情況下，該算法表現(xiàn)一般，接下來將進(jìn)一步提高本算法在不同業(yè)務(wù)場景中的兼容性和實(shí)用性。