RFC815-IP分片重组

转载请标明出处:http://hushengdong.com/2016/10/30/RFC815-IP%E5%88%86%E7%89%87%E9%87%8D%E7%BB%84/

最近在看IP分片重组的部分,在网上搜索了一下RFC815的中文翻译文章,没有找到一个合适的,索性自己下载了原版文档来看,正好以前并没有翻译过文档,RFC815文档也不是很长,正好拿来开始,翻译的也有许多自己不太明白,后续再完善吧。

David D. Clark
MIT计算机科学实验室
计算机系统通讯组
1982年7月

1 引言

IP协议的一个特性是分片和重组,在某些特定的情况下,单个数据包在到达目的地之前会被分割为

多个数据包分片,接收主机端的IP层必须在所有分片都到达之后才能重新组装,IP分片的文档对分片和重组给了很详细的描述,并提供了几个范例。文档也提供了一个可能的重组算法,本文档描述了一个可能在某些机器上更合适的替代算法实现。

对重组过程的简单检查可能会更复杂,首先,必须要跟踪所有的分片,这会有一个小的跟踪工作,其当一个新的片到达的时候,能够用不同的方式将新片和已经跟踪的片组合起来,可能是精确的完全填充在2个片之间的空隙,也有可能会覆盖现有的片数据,甚至和现有的片完全重叠,还有可能填充在2个分片之间并且和2边的片都不接触,这样看来,不同的IP选项导致重组过程需要一个很复杂的测试算法。
事实上,重组的过程是相当简单的。本文档描述了一种最大限度减少校验的方式,这需要一个和没有分片之前的IP包大小一样的缓冲区,可以重组以任何顺序和方式到来的数据包,并且适用于大多数的操作系统。

读者应该查看IP相关的文档以确定熟悉了重组的一般概念,包括IP首部的一些为了分片和重组设置的特殊域。

2 算法的简单描述

为了定义重组算法,首先要先定义一些术语,重组数据包含一些sequences的到达的分片和没有到的,我们把没有到的分片空出来的区域叫做洞,每一个洞有2个数字特征值,洞的第一个数字序列和最后一个数字序列,即洞的头和尾,这一对数字我们叫做对洞的描述,对于一个特定的包我们假设所有的洞都有这样的描述并且被统一维护在一个链表中。

通常的描述如下:当一个新的分片到达的时候,它将会填充1个或多个洞,我们将会检查每一个链表中的每一个元素来确定是否有洞被新的分片填充了,如果恰好被填充了,就从链表中把洞的描述删除,最后,会一个分片会把所有的洞都填充使所有的分片都相互连接起来,在这一刻,数据包重组成功,下一步就是把数据包传送给高一级别的协议来处理。

算法将会被分成2部分来描述,在第1部分,为了确定是否有洞被新到达的分片所填充,我们将会展示当一个新的分片到达的时候处理的步骤;在第2部分的描述中,我们将会展示一个极其简单的你会觉得不可思议的管理这个洞的链表的算法。(这是作者在炫耀吗?最简单的算法实现了最强大的功能。)

3 分片处理算法

新到达的分片可以填充已经存在的洞,最简单的情况,正好填充了某一个洞,或者在洞的头或者尾留下了一个更小的洞,或者2边都不靠,把原来的洞一分为二为更小的洞,因为这种种的可能,似乎当一个新的分片到达的时候,必须做很多的测试,这将会是一个负责的校验算法,实际上,算法可以做到新片最多4次比较就达到目的。

我们从第1个分片到达的时候开始,最开始我们复制了1个和原来IP数据包一样大小的一个缓冲区,维护洞的链表里也只有1项,这个洞表示数据包全部都丢失了,此时,洞的开始是0,结尾是无限大(这个无限大可以是一个很大的整形数字,比576要大,取决于算法的实现者怎么选择了),剩下的8个步骤就是把新来的分片填充到缓冲区中,新来的分片也被2个数字描述,分片的头数字和结尾数字:

  • 1、从链表中选择下一个洞,如果没有,转第8步。
  • 2、如果新到达分片的头数字比当前洞的尾要大,转第1步。
  • 3、如果新到达分片的尾数字比当前洞的头要小,转第1步。
    (如果第2步或者第3步的判断都命中,表示新到达的分片不覆盖任何的洞,我们不需要关注这个洞,直接回到开始,重新选择下一个洞)
  • 4、把洞从链表中删除。
    (因为不管是第2步命中或者第3步命中了,都表示新到达的分片以某种方式覆盖到当前洞了,这样的话,当前洞的描述就失效了,我们将会删除它,在接下来的第5步和第6步中,我们将会判断是否需要创建新的洞)
  • 5、如果新的分片的头比洞的头要大,创建1个新的洞,新的洞的头是旧的洞的头,新的洞的尾是新片的 头减1。
    (如果第5步命中的话,表示当前洞的前半部分没有被填充,我们创建了一个新的较小的洞来描述这缺失的前半部分。)
  • 6、如果新的分片的尾比洞的尾要小的话,同时分片的标志位MR是1(表示还有更多片),会创建1个新 的洞,新洞的头是新到达分片的尾加1,新洞的尾是旧洞的尾。
    (这1步是第5步的镜像操作,很相似,最开始,我们不知道重组的数据包有多大,于是我们创建了一个从头是0,尾是无限大的洞,最终,我们收到了最后一个分片,在这一刻,这个洞的尾到无限大可以被丢弃了,包含最后一个分片的包在MR标志位,这1步的检测会让我们不用创建一个从数据包尾到无限大的无用的洞)
  • 7、转到第1步。
  • 8、如果维护洞的链表空了,重组完成,把它转发给更高1个级别的协议,不然的话,直接返回。

4 管理洞的链表的算法

在这8步中最复杂的部分不是执行这些测试,而是新增或者删除链表中维护的洞,因为没有限制在重组过程中创建的洞的数量,可能有人会想出来1个比我们将要介绍的算法的复杂度更高的存储管理算法,我们将会介绍1个非常简单的算法,就是仅把每一个洞的描述放到洞本身的第1个字节(这块翻译的不对,原文是:however Just put each hole descriptor in the firstocteets of the hole itself.),根据重组算法的定义,最小的洞是8字节,为了存储洞的头和尾,每一个洞需要2个字节,另外我们需要2个额外的字节来串联洞的链表以实现该特性。(翻译的不正确,原文是:An additional two octets will be required to thread together the entries on the hole descriptor list ,this leaves at least two more octets to deal with implementation idiosyncrasies)

在这个存储管理策略中仅仅有1个明显的缺陷,那就是在把数据从分片复制到重新组装的缓冲区之前,就要把上面提到的8个步骤执行一次,如果想先复制分片数据到缓冲区,会破坏1个或者多个洞,一旦按照上述算法开始运行,任何将要被删除或者分解的洞已经是过时无效的洞了。

5 loose ends 释放结尾

通过重组缓冲区来散射洞到一个链表上,才能找到洞的信息,反过来需要一个指向链表的头的指针,在大多数情况下,指针可以存储在重组缓冲区实现方案专门开辟的描述块上,如果重组缓冲区没有设计这样的块,一个看起来不友好但是有效的诀窍是存在IP数据报的头部一些已经不再需要的段上,很明显比如校验和字段。

当最后一个分片到达的时候,IP数据报的长度字段需要被计算并填充到长度字段上。

6 选项

前面的算法做了一个理想的假设,它假设IP数据报没有选项需要被重组,难点在于一直要等接收到IP数据报的第一个分片才能知道IP头有多大,那是因为一些选项被复制到每一个分片,但是有一些像纪录路由信息的字段就只在第一片(第一个分片是指包含了原始0字节的分片)。

不知道IP头的长度,就不知道把分片填充到缓冲区的什么位置,如果第一个到达的分片正好是第一片,那不存在问题,否则,(对于上面说的问题),有2种解决方法,第一种是为重组缓冲区预留足够大的空间,实际上不需要特别大,64字节就足够了,第二种可以先假设(原文是用的gamble)第一片不包含选项,如果第一片到了发现有选项,再把缓冲区里的数据移动合适的距离来存放选项信息,唯一一个复制数据的危险是会破坏洞的链表,如何untrash(恢复)指向洞的指针很容易明白。

IP数据报的记录路由选项有一个特性,就是每一个分片到达目的地的路径可能会不一样,不同的分片可能纪录的路由器跳转路径也不一样,一般来说,目的地址通常不太关心怎么到达的,程序关心第一片分片中的路由器跳转路径然后忽略其它分片的。

7 完整算法

有2个附加的内容,第1个:当1个分片到达的时候,有必要找到这个分片在缓冲区中的位置,这就需要一个机制来遍历当前系统中的所有缓冲区,怎么区分的呢?用4个字段来判断当前分片属于哪个缓冲区:外部和本地的IP地址、进程ID、IP报的标识符字段(16位)

第2个:关注TTL生存期,需要发现是否有分片因为TTL被减到1导致分片失效,这样系统可以把这个无用的IP报删除,可以创建一个后台程序,每秒钟把TTL减1(这对吗?)或者可以在第一片分片到达的时候纪录下时间,然后用一些定时器或者是系统方案,to repa the datagram when its time has come.

包含所有部分的完整算法曾经在BCPL做了一个测试,完整的算法使用了1.5页的链表(指的是纸带吗?),生成了大约400个机器指令,算法部分实际上只包含20行左右的洞管理代码,本文档描述的算法实际上是作者原始版本的简化版本,感谢她在MIT的高瞻远瞩的观察测试。