一种基于矩阵坐标的快速组包算法

杨 琦

(中国电子科技集团公司第二十研究所,陕西 西安 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 结束语

针对网络通信过程中现有的分组包技术的缺陷，设计了一种新型适用于大容量业务包传输的算法。通过建立业务矩阵对分包过程进行优化，使用二部图染色原理提高组包效率，并通过计算机软件对算法进行了仿真验证，证明该算法在业务量较大的情况下，改进后的组包效率高于传统算法。但在业务量稀疏的情况下，该算法表现一般，接下来将进一步提高本算法在不同业务场景中的兼容性和实用性。