一種基于矩陣坐標的快速組包算法

楊 琦

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

0 引 言

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

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

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

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

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

1 數學建模

1.1 業(yè)務特性

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

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

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

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

圖2 基于矩陣坐標業(yè)務包拆分示意圖

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

1.2 算法步驟

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

圖3 算法流程圖

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

步驟3：查詢到的業(yè)務包命名為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的關系。

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

(2) 若i

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

算法流程圖如圖3所示。

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

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

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

圖5 組包順序示意圖

2 仿真驗證

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

圖6 組包耗時對比圖

3 結束語

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