基于模糊二分查找的帧分片算法设计与实现

郑 昱 洪 伟 蔡晓磊

(西安电子工程研究所 西安 710100)

0 引言

为了降低网络设计的复杂性，绝大多数网络通信系统都由多个协议层构成一个整体的协议栈，例如常见的TCP/IP协议栈由应用层、传输层、网络层、数据链路层和物理层组成[1]。各层之间具有数据交互，上层的数据帧作为下层数据帧的有效载荷进行分装处理。各层数据帧的有效载荷通常具有最大长度上限，所以经常会出现下层数据帧的最大有效载荷比上层数据帧长度更小的情况，这时为了下层数据帧能够承载上层数据帧进行有效传输，则需要对上层数据帧进行分片处理，并在接收端对分片进行聚合处理，恢复原先的上层数据帧[2]。

对数据帧进行分片处理需要耗费处理时间，如何设计一种性能优越的帧分片处理算法，对减小协议开销，提高数据吞吐量，降低系统实现难度具有重要意义。本文设计了一种高效的帧分片算法，并基于C语言对其进行了实现。

1 帧分片算法

1.1 算法简介

下层数据帧最典型的为物理层帧，常见物理层数据帧的有效载荷长度具有以下两个特点：

1)最大有效载荷长度会根据下层某些动态变化的发送参数(例如调制编码方式等)而动态改变，即不同发送参数具有不同的最大有效载荷长度。

2)在同一发送参数的情况下，最大有效载荷的长度范围内，不可随意选择载荷长度，只有若干大小不一的固定载荷长度可选。

根据上文可分析得出，当上层数据帧长度大于下层最长有效载荷长度时，需要将上层数据帧分片，切分成下层有效载荷能够承载的数据长度。考虑数据传输的效率，在对上层数据帧进行分片时，分片数量应该越少越好，所以优先考虑使用当前发送参数条件下的最大分片长度对上层数据帧进行分片，当上层数据帧剩余长度不足最大分片长度时，再考虑使用能够承载上层数据帧剩余长度且最接近的分片长度进行分片。

如何快速地找出当前发送参数条件下能够承载最后一个分片的最小有效载荷长度是分片算法的关键。

1.2 数据结构

1)分片长度表

分片长度查找表是用于存储不同发送参数条件下的不同可用分片长度，可用分片长度即下层帧有效载荷长度，根据上文介绍的有效载荷长度的两个特点，分片依据发送参数的不同具有若干大小不一的分片长度。因此，分片长度查找表为二维查找表，如表1所示，其中纵坐标为发送参数，横坐标为分片序号，表中以升序的方式对同一发送参数的不同可用分片长度进行排序。

表1 分片长度查找表

分片序号发送参数 12345……发送参数11010101010发送参数2263474106138发送参数34258138202266…………

2)帧结构

帧的分片传输至接收端后需要重新聚合成为完整的一个上层数据帧，这就需要接收端能够区分各个分片属于哪个上层数据帧，分片的有效数据长度，以及判别分片的顺序，因此在下层数据帧的帧头中需要使用序号域、有效数据长度和更多分片指示，如图1所示。

其中，序号域又由帧序号子域和分片序号子域组成，帧序号子域用于区别分片属于哪一个上层数据帧，分片序号子域用于区分分片在同一上层数据帧的顺序；由于分片中承载的上层数据帧的有效数据长度不一定与分片长度相一致，所以需要使用有效数据长度来说明该分片中承载的上层数据帧有效数据长度数值；更多分片指示用于接收端判断该分片是否为最后一个分片。

帧序号分片序号有效数据长度更多分片指示

图1分片帧头结构

1.3 算法流程

如前文所述，帧分片算法的关键在于快速地在分片长度查找表中找出当前发送参数条件下最合适的最后一个分片长度。常见的表查找方法有顺序查找、二分查找、块查找等，考虑到分片长度查找表为有序表，对于顺序表而言二分查找的性能是最优的[3]，所以采用二分查找的方式查找合适分片长度最为合适。但是，普通的二分查找算法基本都是精确查找算法，即精确地查找出表中与关键字相等的元素。而数据分片时是查找能够承载上层数据帧剩余长度且最接近的分片长度，这个分片长度可能与数据帧剩余长度相等，也可能比数据帧剩余长度更长，所以普通的二分查找算法并不适用于数据分片处理，本文对常用二分查找算法进行相应的改进，形成一种模糊查找的二分查找算法，用于分片长度的查找和选择。

具体算法步骤如图2所示：

1)首先，假设当前分片长度查找表中的分片长度是按照升序的方式进行排列，将表中间位置作为当前查找位置，当前查找的分片长度与数据帧剩余长度进行比较，如果两者相等，则查找成功，当前位置记录的分片长度即是所需的分片长度，如果不相等，则进入步骤2；

2)否则，再判断该分片长度是否大于数据帧剩余长度，如果是，则进入步骤3，如果否，则进入步骤5；

3)判断当前查找位置是否为表首位置，如果是，则查找成功，当前位置记录的分片长度即是所需的分片长度，如果否，则进入步骤4；

4)判断当前查找位置之前的一个元素的分片长度是否小于数据帧剩余长度，如果是，则查找成功，当前位置记录的分片长度即是所需的分片长度，如果否，则将当前查找位置之前的各元素作为一个子表，回到步骤1进行进一步递归查找；

5)将当前查找位置之后的各元素作为一个子表，回到步骤1进一步递归查找。

1.4 算法性能分析

在分片长度查找表中查找最合适的分片长度时，最为常用的查找方法为顺序查找，这里通过与顺序查找方法进行对比，来分析模糊二分查找算法的算法性能。

普通二分查找的算法过程可以对应一棵有n个结点的二叉树[4]，假设该二叉树是一个满二叉树，则对应的最多比较次数为log2(n+1)，所以平均查找长度为log2(n+1)-1。

模拟二分查找与普通二分查找的最大区别在于每次从查找表查找的分片长度是否适合的判断标准不仅仅是与数据长度是否相等，还可以是大于数据长度的最小分片长度。仅仅是每次比较时与普通二分查找算法的判断标准不同，并不增加平均查找长度，因此与普通二分查找的时间复杂度一致，仍为O(log2n)。

由以上分析得知，模糊二分查找算法的平均查找长度和时间复杂度都优于常用的顺序查找算法。

2 分片软件模块实现与测试

2.1 模块实现

依据上文基于模糊二分查找的分片算法，实现标准C语言软件模块[5]，该模块具有以下特点：

1)分片参数可灵活配置；

2)分片长度可根据下层需求进行动态调整；

3)对于常规的各类数据传输过程中分片和聚合处理具有普适性，稍作更改就可以应用于各种数据帧分片聚合系统。

分片模块设计主要包含以下两个处理部分：

1)以最大分片长度对数据进行分片：按照当前发送参数条件下最长分片长度对数据进行分片，将数据长度除以最长分片长度，计算出以最长分片长度进行分片的分片个数，对分片进行组帧并传输分片；

2)查找最后一个分片的分片长度，并对数据进行分片：使用基于模糊查找的二分查找算法查找最后一个分片的分片长度，对最后一个分片进行组帧并传输分片。

具体流程如图3所示，具有以下16个步骤：

1)开始，更新帧序号，确定当前数据的帧序号，并进入步骤2；

2)初始化数据分片的帧头，填入当前数据的帧序号，并进入步骤3；

3)将数据长度除以当前发送参数条件下的最长分片长度，得到以最长分片长度进行分片的分片个数max_frag_cnt，并进入步骤4；

4)初始化循环计数变量i为0，并进入步骤5；

5)判断i是否小于max_frag_cnt，如果是，则进入步骤6，否则进入步骤10；

6)更新分片序号，将分片序号填入分片帧头的分片序号子域，设置分片帧头中的更多分片标识为1，并进入步骤7；

7)计算分片中有效数据载荷的长度，将长度值填入分片帧头的有效数据长度域，并进入步骤8；

8)将分片帧头部分拷贝至发送缓冲区，接着将数据中需要填入分片载荷的部分拷贝至发送缓冲区，更新偏移量，并进入步骤9；

9)将发送缓冲区中的分片数据发送出去，并进入步骤10；

10)获取以最大分片长度进行分片后剩余的数据长度，并进入步骤11；

11)判断剩余的数据长度是否大于0，如果是，则进入步骤12，否则结束分片处理；

12)调用get_last_frag_len函数，使用基于模糊查找的二分查找算法，在分片长度查找表中查找出合适的分片长度，作为最后一个分片的分片长度(具体算法流程参照1.3节)，并进入步骤13；

13)更新分片序号，将分片序号填入分片帧头的分片序号子域，设置分片帧头中的更多分片标识为0，并进入步骤14；

14)计算分片中有效数据载荷的长度，将长度值填入分片帧头的有效数据长度域，并进入步骤15；

15)将分片帧头部分拷贝至发送缓冲区，接着将数据中需要填入分片载荷的部分拷贝至发送缓冲区，更新偏移量，并进入步骤16；

16)将发送缓冲区中的分片数据发送出去，结束分片处理。

2.2 模块测试

该软件模块主要实现对数据包的分片功能，软件具有极强的通用性，通过修改软件接口、全局变量/常量和宏定义的数值即可适配各种数据传输软硬件系统中。因此，在对该软件模块进行测试时，为了增强测试过程的可靠性和测试结果的真实性，降低测试的实现难度，避免传输过程中不可预期的数据错误，采用在单机条件下软件模拟数据传输过程的方式对其进行测试。这种测试方式，可以模拟数据正确或者错误传输的过程，且不受除软件模块以外的软硬件因素的影响。

测试方法步骤如下：

1)首先定义各种宏定义、全局变量和常量，并初始化分片查找表；其次通过软件生成一个一定长度带奇偶校验的数据帧；

2)调用分片函数对其进行分片，并在每片分片结束后调用模拟传输函数模拟数据传输的过程；

3)在模拟传输函数中调用对各个分片进行聚合，直到得到聚合后的数据，对聚合后的数据进行奇偶校验验证分片聚合过程的正确性。

如图4所示，数据分片长度为1200字节，通过分片模块对其进行分片，此时发送参数为0，一共分为3个分片，分片长度分别为405字节、405字节和390字节，再将三个分片进行聚合，最后得到的聚合后数据长度也为1200字节，且数据校验和与原数据一致，说明数据分片聚合成功且正确。

以上步骤为正常处理过程，还能通过在模拟传输函数中添加条件判断语句，使得某些分片传输错误，验证和测试聚合函数对数据包丢失的异常处理能力。

3 结束语

网络通信系统中经常需要对数据进行分片聚合处理，因此良好的分片算法能够有效提升整个网络系统的性能。本文根据常见网络通信系统物理层的分片需求，提出了一种基于模糊二分查找的帧分片算法，并基于C语言对其进行了实现，并在最后对其进行了相应的模拟测试。该分片算法在各类网络通信系统数据分片过程中都具有良好的应用前景。