技术专栏
TECH FOCOS
IP数据报重组算法及实觋
3 解放军信息工程学院 陈蕾蕾 ●____ ‘一 曲保章
要：分片与重组是 P机制之一。 P教据报可以在网关赴被分片，各报片分别传送。 的主机将接收
到的各个报片重组为原始数据报。本文首先介绍了IP报片重组的常规算法并在此基础上介绍了一种较为
简单的算法厦其实现。 ，
关键词：必 塑童鸯，坌苎，重丝，型}，重组缓冲区。
Internet是目前国际上规模最
大的计算机网问网，它通过TCP／
IP协议组解决了异种网络的通信
问题。IP协议即互联网协议是整个
TCP／IP协议组的传送系统。IP
模块负责主机与主机之间的通信 。
它处理来 自高层的数据，填充 IP
报头，然后将该 IP数据报交付下
一 层进行帧的封装。在 Interuet环
境下。由于不同的物理网络其最大
传输单元 (MTU)的帧长不同，一
个 IP数据报在一个物理网络中能
够被完垒封装，到另一个物理网络
中就未必了。为此。IP协议担任了
分片与重组机制：由网美将原 IP
数据报划分为若干较小的报片，分
别进行传送。目的主机将收集所有
的报片并将其重组为原 IP报文。
一
、IP数据报格式
及分片规则
IP数据报符台典型分组的一
般格式，由报头和数据区两部分组
成。如图1所示：
与控制分片和重组有关的数据
报报头域有三个 ：标识域、标志域、
片偏移域。标识是信源机赋予数据
报的标识符，同一个数据报的各个
报片标识域是相同的。标志域中
“不分片”位置位时，数据报不能被
分片。“片未完”位置位时，说明该片
不是原数据报的最后一片。片偏移
域指出本片数据在原始数据报数据
区中的偏移量，重组时片的顺序是
由片偏穆决定的。
IP数据报被分片后，每一个分
片由数据部分和片头组成。其中片
头域基本上从原始数据报中拷贝而
来。各个报片片头中的标志域及片
3
，
偏移域各不相同。另外，原数据报
的选项域中仅有部分选项被拷贝到
所有报片中，而另有一些选项仅在
偏移为零的报片中出现。因此，重
组过程 中 IP数据报的报头域主要
由偏移最小的报片决定。
二、常规算法概述
首先，在接收到第一个报片时，
为待组 IP数据报开辟一片重组缓
冲区。该缓冲区由源地址、目的地
址、坍议、标识而唯一确定。由于IP
0 4 S l6 19 24 3
版本『头标长l服务类型l 总 长
标 i,q l标志l 片 偏 移
生存时间 I 协 议 f 头标校验和
源 IP 地 址
信 宿 lP地 址
选 项 域 填 充 域
数 据
囤 1
ELEcTRoNlcs ToDAY J‰I l ％8 3 1
维普资讯
技术专栏
TECI-I F0CUS
数据报包括报头以及数据两部分 ，
与之相对应，重组缓冲区也由报头
缓冲区和数据缓冲区构成。每当一
个新的报片到达时，根据片头巾的
上述四种参数域而判定此报片应归
属于哪一个重组缓冲区，再视其片
偏移域以及片头标长，片总长度域
的值将该报片应归属于哪一个重组
缓冲区，再视其片偏移域以及片头
标长 ，片总长度域的值将该报片的
数据部分拷贝到数据缓冲区的适宜
位置。由于片偏移以8字节为单位，
片头标长以4字节为单位，片总长
以单字节为单位，在拷贝时应注意，
若以字节来计，位置是从(片偏移★
8)到 (总长一头标长★4+片偏移★
8)。
为了判定一个 IP数据报的各
个报片是否均已到达，算法设置了
变量 TDL以及报片到达标志位表
FRBT。TDL是总数据长度，在算
法开始时赋值为0。当偏移最大的
报片到达时，根据其片偏移以及片
长度可以确定整个数据报的数据长
度 (版偏移+片总长一片头标长)，
此时可以为 TDL赋值。FRBT中
的每一位均代表待重组 IP数据报
数据区的8个字节，也是初值为
0。若包含这8个字节的报片已经收
到并拷贝完毕，则将此位置为 1。因
此，每接收到一个报片，在完成上文
所述的数据拷贝工作后 ，应将
FRBT中从片偏移到 (片偏移+
(总长一头标长★4+7)／8)的各位
置为 l。显然，当待重组 IP数据报
的各个报片均到达以后，TDL不为
0(总数据长度已经确定)且 FRBT
中从 0到 (TDL+7)／8的各位均
为 1。进行上述两个条件的判定可
以知道重组工作是否已经完成。
在待重组 IP数据报头的处理
32 今8电子 溯 年第7嘏
上，由于选项域仅在偏移为 0的报
片中与原始数据报一致，而且仅当
接收到偏移最大的报片时，才能根
据其偏移以及片的长度而确定下原
始数据报的总长 。这样，原始数据
报报头的填写可以这两个特殊报片
的片头为基准。当接收到偏移为 0
的报片时，填写报头缓冲区的大部
分区域，头标长以及选项域均在此
时可以确定。当接收到偏移最大的
最大的报片 (“分片未完 位为 0)
时，可以确定总长并填人报头缓冲
区。
另外，算法必须提供数据报延
迟控制 机制 。接收到第一个报 片
后，启动一个重组定时器计时。若
在规定时间内尚未收到全部报片 ，
则放弃整个数据报并报出错信息。
常规算法通过标志位表来记录
IP数据报的重组情况，每8个字节
就需要一个标志位。下文介绍的一
种算法实现可以将这种记录工作大
大减轻 ，尤其是 当报片长度较大
时。
三、简化算法所需参数
及数据结构
此算法中重组缓冲区是一个整
体 。在待重组 IP数据报报头的处
理上 。由于原始数据报的报头长度
是由偏移为 0的报片片头决定的，
而各报片又非按序到达，一开始并
无法确定应在重组缓冲区中留下多
大的空间给报头。简单起见，可以
在缓冲区的头部 留下 64字节的空
间，这是 IP数据报的头长度可 以
达到的最大值。
算法所需参数及数据结构如
下 ：
1．hole．first与 hole．1ast
IP数据报的重组问题实现上
是一个向重组缓冲区填补空缺的过
程。算法开始时重组缓冲区是一个
完全空缺的“孔”(hole)。随着各报
片的陆续到来，不断对 “孔”进行填
充与覆盖，“孔 的数量及大小将在
填充的过程中不断变化。当所有的
“孔”最终被填满，IP数据报重组完
成。在此为每一个“孔”定义两个参
数：
hole．first：该“孔”第一个字节
相对重组缓冲区头部的位置偏移量
(以字节为单位)；
hole．1ast：该“孔”最后一个字
节相对于重组缓冲区头部的位置偏
移量。
显然，起始阶段只存在一个
“孔 ，其参数为 hole．first=0，
hole．1ast=infinite。由于 IP数据
报最大长度为 576字节 ，在此可取
infinite为 576。
2．frag．first与 frag．1ast
每一个报片也可用两个参数来
描述 ：
frag．first：该报片第一个字节
在原始数据报中的偏移量；
frag．1ast：该报片最后一个字
节在原始数据报中的偏移量。
由于已假定原始数据报的报头
长度为 64字节 ，则 frag．first：
64+该报片片头偏移域的值★8，
frag．1ast=frag．first+该报片总
长域的值一该报片片头长度域的值
-／~4o
3．孔参数寰
一 个 IP数据报在重组的过程
中会出现多个 “孔”，有必要将它们
组织起来。所有“孔”的参数 hole．
first与hole．1ast均放置在一个孔
参数表中，并且采用指针将它们联
系起来。参数表中的每一项由三部
维普资讯
技术专栏
TECH FOCUS
裹 1
分组成：hole．first、hole．1ast及指
向下一个孔参数的指针。表头处可
设一头指针 header。如图2所示 ：
显然，算法开始时参数表如表
l：
当重组完成，算法结束后，所有
的孔不复存在．则 header为空。
四、简化算法的实现
第一部分：当一个新的 IP数
据报到达时，根据其报头中的“不分
片”位判断其是否为报片。若是，则
根据片头中的源地址域、目的地址
域、协议域、标识域来确定它应归属
于哪一个重组缓冲区，找到相应的
孔参数表。否则，直接将该 IP数据
困 2
报交付高层。
第二部分：针对该报片的偏移
以及长度值计算出frag．first和
frag．1ast。与重组缓冲区中的各个
“孔”进行比较，看是否会将某些
“孔”完成或部分覆盖掉，继而修改
孔参数表。具体步骤如下：
1．从孔参数表中选择下一项．
若已无可选项，进行算法第三部分；
2．若 frag．first> hole．1ast。
转至步骤 1；
3．若 frag．1ast<hole．first．
转至步骤 1；
4．从孔参数中将该项删除；
5．若 frag．first>hole．first．
则构造一新的孔参数 ，其中 Dew．
hole．first=hole．first．newhole．
1ast=frag．first—l，并将该参数加
人到孔参数表 中；
6．若 frag．1ast<hole．1ast且
该报片片头中的 。分片未完”位置
位 ，则构造一新的孔参数 ，其 中
newhole．first=frag．first+1．
newhole．1ast=hole．1ast，并将该
参数加人到孔参数表中；
7．转至步骤 l。
第三部分：根据frsg．first与
frag．1ast将该报片的数据部分拷
贝到重组缓冲区的相应位置。
第四部分：判断header是否为
空，若为空，说明重组已经完成。否
则还要继续等待下一个报片的到
来。
五、补充说明
1．原始数据报 头的填写啄则
以及重组定 时器的使用 同常规算
法。
2．如果对算法的存储结构进
行改进，将每一个“孔”的插述参数
及联系指针存放在该“孔 所占据空
间的头部而不再额外消耗内存 。由
于在第三部分数据拷贝工作之前被
覆盖的“孔”其参数已经作废 ，故不
会造成影响。在内存资源较为紧张
的情况下不失为一种解决办法。
(上接第42页)
Ic卡的发展趋势
IC卡随着大规模集成电路及
大容量存储芯片的发展而产生，也
必将随着计算机技术、网络技术、半
导体技术等高速发展而发展、壮大
起来。又由于IC卡本身有诸多突
出优点：存储的信息量大——内部
有RAM、Eprom、E2prom存储器，
并可分成若干个应用区，便于一卡
多用及方便保管。持卡人可以存放
个人信息、帐户余额及金融交易需
要的识别、交易确认的信息等。安
全性高——卡内信息加密后不可复
制。密码核对错误本身白毁功能，绝
对安全可靠性使其在应用中对计算
机网络的实时性、敏感性要求降低。
这样有利于在网络通用环境下及脱
机情况下使用。加上体积轻小，携
带方便等特点，使 IC卡的应用领
域几乎达到无限制的地步。IC卡品
种繁多，新技术不断增加，这充分说
明了 IC卡的强大生命力和用户的
信赖程度。在全球 IC产业市场竞
争更加激烈的情况下，IC卡必然向
更高层次方向发展；诸如接触型 IC
卡迅速向非接触型 IC卡转移，低
存储容量的IC卡向高存储容量发
展，单功能 IC卡向多功能 IC卡转
化，单系统的IC卡向多系统 IC卡
转化，由非银行系统转向银行系统
应用，由民用转用军用，由局域罔向
罔际网迁移等。
ELEcTRoNlcs TonAY l 燃 33
维普资讯
