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

楊 琦

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

0 引 言

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

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

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

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

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

1 數學建模

1.1 業務特性

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

圖1 傳統業務包拆分示意圖

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

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

圖2 基于矩陣坐標業務包拆分示意圖

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

1.2 算法步驟

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

圖3 算法流程圖

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

步驟3：查詢到的業務包命名為C[i,j]。

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

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

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

步驟5：判斷i和j的關系。

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

(2) 若i

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

算法流程圖如圖3所示。

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

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

圖4 業務矩陣示意圖

圖5 組包順序示意圖

2 仿真驗證

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

圖6 組包耗時對比圖

3 結束語

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