周小波 延时容忍网络的路由技术研究
中国科学技术大学
博士学位论文
延时容忍网络的路由技术研究
姓名：周晓波
申请学位级别：博士
专业：通信与信息系统
指导教师：洪佩琳
20080301
摘要
络状况，因为网络状态相对稳定，传统网络中，当前的网络状况一般是通过路由信息交互协议获取的过去某个时刻的网络状况的预测得到的。ＤＴＮ需要未来较长时间内的网络状况，仅仅通过对过去状况的简单预测并不准确，因此需要需要引入先验知识。
在研究了ＭＡＮＥＴ，ＷＳＮ等网络路由协议的基础上，本文主要对ＤＴＮ的路由研究作出了如下贡献：
着眼于路由算法的信息集中最重要的参数一一延时，建立了ＤＴＮ中数据包的单跳延时模型。把延时作为选择最佳路径的标准可以减少数据包在网络中的驻留时间，减少网络缓存的消耗，反过来增加网络的容量。在ＤＴＮ的研究中延时的构成以及其量化的分析还没有涉及。本文给出了单跳的范围，即链路上的延时模型，指出延时构成的几个基本量，娶口传输延时、排队延时、等待链路建立延时和传播延时。为了分析这几个参量的相互关系，把链路作为服务窗建立排队模型，提出了一种新的“带随机休假的非空竭排队系统”，利用排队论的分析方法，对队列长度、排队延时进行随机分解，最后得到队长和延时的分布函数，以及它们与业务分布等参数的数学期望之间的关系。最后通过仿真证实了实际测量值和计算值之间有很高的拟合度，在～定精度下本文的分析结果可以成立。
在标准ＥａｒｌｉｅｓｔＤｅｌｉｖｅｒｙ算法的基础上，把先验知识的准确性考虑进去，提出ＡＥＤ（Ａｄ印ｔｉｖｅＥａｒＩｉｅｓｔＤｅｌｉｖｅｒｙ）算法。ＥａｒｌｉｅｓｔＤｅｌｉｖｅ哆算法只具有理论上的意义，它给出了一种很好的描述ＤＴＮ路由问题的方式：但是在实用性方面，它对先验知识过高的需求造成实现的困难。但是，从另一个方面来看，现实中存在这一些可以预先知道链路容量函数的场景，例如卫星通信；这时Ｅ础ｉｅｓｔＤｅｌｉｖｅ叫算法可以提供更好的路由效果，但是，现实中预知的链路容量函数总是存在误差，如何衡量这种误差，以及如何使ＥａｒｌｉｅｓｔＤｅｌｉｖｅｒｙ算法在误差下也能够有较好的性能就成为了本文的一个研究内容。首先，建立误差模型，从理论上分析丢包概率与误差强度的关系，给出了表达式；然后，把误差的标准差作为参数去修正延时，就是ＡＥＤ算法。仿真表明新的算法对误差的容忍能力有明显提高。
提出一种基于模板运算的运动模式识别框架ＰＭ３Ｄ，并提出基于运动模式的路由模型。运动模式是用来描述节点（群）的运动规律的概念，但是本文中的运动模式不关注物理的参数，而是宏观上的模式；这种模式可以从网络的空．时图的各元素（只考虑。和１，也就是通和断）之间的位置关系中反映出来。一种基于模板运算的机制ＰＭ３Ｄ被用来从空．时图中识别这些运动模式，并用一个统一的数据结构一一访问列表（ＶＬ：ＶｉｓｉｔＬｉｓｔ）来存储。运动模式的引入并不依赖于具体的路由算法，但是需要在路由决策时加入对ＶＬ的应用，即需要一个接口让路由算法来访问ＶＬ，并从中获得必要的信息以辅助决定下一跳。仿真结果表明ＰＭ３Ｄ能够识别出运动模式，并且运动模式能够反映出网络拓扑的变化趋势，提高了数据投递率。
关键词：延时容忍网络，自组织，延时模型，ＡＥＤ，运动模式，ＰＭ３Ｄ
ＩＩ
第ｌ章绪论
第１章绪论
以ＴＣＰ，【Ｐ协议为主体的因特网（Ｉｎｔｅｍｅｔ）改变了人们的生活方式，与Ｉｎｔｅｒ∞ｔ不同。各种工业用途的专用网络似乎远离人们的视线，但是它们在人们日常生活的幕后扮演着重要的角色。例如，道路监测网络为保障通行安全起了重要作用，矿场的监测网络能及时发现和通告危险，而灾难发生地的临时通信网络为救灾命令的下达和执行提供了有力的支持。还有很多科研中使用的专用网络，例如野生动物监测，自动放牧系统等。这类网络的绝大部分都有这些特征：以无线电波为载体、节点能力受限、节点移动频繁、通信环境恶劣等。在这类网络里，用于Ｉｎｔｅｍｅｔ的协议很难正常工作，于是人们提出延时容忍网络（ＤＴＮ：Ｄｅｌａｙ呵ｂＩｅｆ卸ｔＮｅｔ、ｊＩｒｏｒｋ）的概念来描述这类网络，并努力为之建立一套协议标准。
Ｄ１附主要有两个来源：最初研究星际通信网络的ＩＰＮ（Ｉｎｔｅｒ－ＰｌａｎｅｔＮｅｔｗｏｒｋ）…项目把节点间的长延时、高不对称性和间歇性连接作为主要的场景加以考虑，ｌＰＮ研究的对象具有特殊性一一其节点的轨迹是可以用数学模型表达的；另一个来源是当下无线自组织类网络（包括ＭＡＮＥＴ．ＭｏｂｉＩｅＡｄｈｏｃＮｅｔｗｏｒｋ和ＷＳＮ：晰ｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋ等）研究的扩展，一般把无线自组织类网络看作移动性较高，但连通性可以保证，但现实的需求并不能保证这个假设，因此人们开始关注网络间歇性分割的场景，并由此扩展出ＩＣＮ（Ｉｎｔｅｒ－ＣｏｎｎｅｃｔｅｄＮｅｔｗｏｒｋ）和ＩＣＭＡＮ（Ｉｎｔｅｒ．Ｃ叩ｎｅｃｂｅｄＭＡＮＥＴ）两类网络。
ＫｅｖｉｎＦａｌｌ考虑了上述两种网络中所蕴含的共同特性后，提出在挑战性的（ＣＩｌａｌｌｅｎｇｅｄ）环境中实现网络互联的模型，即Ｄ，烈的概念“‘。这个Ｄ１Ｎ的概念以及其体系结构模型成为了球ＩＩＦ（ＩｎｔｅｍｅｃＲｅｓｅａｒｃｈ协ｋＦ０ｒ∞）的ＤＴＮｆｇ工作组的研究的主要内容，但是对网络研究影响最大的还是ＤＴＮ对路由模型的改变。即对网络分割的关注。
从路由的角度来看，Ｄ１Ｎ是一类特殊的网络模型，其不同于其他网络模型的一个根本特征在于Ｄ１ｍ不假设在路由期间源端到目的端路径的存在性。基于这一点，传统的以Ｄｉｊｋｓｔｒａ算法（准确的说是静态Ｄｉｊｋｓｔｍ算法，因为ＤＴＮ中会使用一种时变的Ｄｉｊｋｓ咖算法）为基础的路由协议将不能很好的工作，因为这些协议隐含了一个根本假设就是网络拓扑的改变远远慢于数据包的端到端延时（ＲＴＴ：Ｒｏｕｎｄ嘶ｐ西ｍｅ），也就是说网络拓扑相对于数据传递来说是慢变的。甚至可以认为是静态的１，端到端的路径是存在的（否则就认为目的端不可达）。从这个角度看，ＤＴＮ的路由协议扩展了路由可能性的范围，使那些在传统路由协议下不可能被投递到目的端的数据包能够参与路由。或者说ＤＴＮ重新定义了路径的概念。在传统网络中，甚至包括ＭＡＮ刚ＭｏｂｉｌｅＡｄｈｏｃＮｅｔｗｏｒｋ），虽然考虑的拓扑的动态性，但是１其实传统有线网络的路由协议能支持变化的拓扑。但是其路由计算过程是针对某一个拓扑的，也就是说它发现拓扑的改变，并随之调整端到端路径，而路径本身是依附于一个固定的拓扑的，即是有某个时刻的拓扑（一个有向图）的边和顶点序列构成的。Ｄ１Ｎ则不行，它的端到端路径中的某些边可能只出现在某个特定时刻的拓扑中．
１
第ｌ章绪论
拓扑的稳态持续时间相对于数据包的ＲＴＴ来说还是还是要高很多；这样，在一次数据投递过程中，拓扑是静态的，路径是与时间无关的。这由两方面决定，即链路延时相对较小以及拓扑的连通度相对较高。而ＤｒＩＮ下，数据包每转发一次之后，网络的拓扑可能已经改变，网络中有的链路已经不存在了，同时又有新的链路建立：这样，从整体看来，路径在时间的维度上是有纵深的，即ＤＴＮ路径中的每一条链路只有在数据包位于该链路的两端的节点上时该链路依然存在时才是有效链路。
本文中关于静态拓扑和动态拓扑的理解参看图１．１（图中‰如＋１】表示一个时间段），本文中凡是提到拓扑动态性和静态性都需按这种方式解释。
在讨论节点Ａ到节点Ｄ的数据投递路径时，对于有线网络（图中左边），说它的拓扑是静态的是指其端到端路径要么是Ａ【ｔ。，ｔ。】一ｑｔ。Ａ】一Ｄｆｔｏｔｔ。１要么是Ａ【ｔＩ．纠一ＪＥｉ【￡Ｉ，ｔ２】一Ｄ‰ｔ。ｌ：对于ＤＴＮ（图中右边），说它的拓扑是动态的是指它的路径是Ａ（￡ｏＩｔ。ｊ一钸。．ｔ。Ｊ—ｑ亿ｔ，Ｊ—Ｄ【ｔｌ，嘲和Ａ‰ｔ。１一ｑｔ２，ｔ。ｌ—ｑｔ。，ｔ。ｌ—Ｄｆ‰“ｌ。因此可以说传统有线网络的拓扑在路由期间拓扑是静态的。
【ｔＤ’ｔｌｌ
ｌ‘Ｉ．１２ｌ
有线网络
图１．１理解静态拓扑和动态拓扑
在这个基础上，对于路由算法而言，其输入已经不再是一个静态的无向图了，而是一个随时间变化的图，其输出也变成以（链路，时间）二元组为基本元素的序列了。针对这个变化，人们提出了空．时图（Ｓｐａｃｅ．１ｒｉｍｅＧｒａｐｈ）来描述ＤＴＮ的拓扑。在空．时图中，网络中的节点处于很多个层中，每一层代表了一个时刻的拓扑，数据包可能的传递路径就足从第一层的源节点开始逐层往下（沿时间方向）直到遇到目的节点。
路由问题是ＤＴＮ研究的重点，但是ＤＴＮ不仅有路由协议，它包含一个完整的协议族?目前ＩＲＴＦ（ＩｎｔｅｍｅｔＲｅｓｅａｒｃｈ协ｋＦｏＩ℃ｅ）”’的工作组Ｄ１Ｎ曙（Ｄｅｌａｙ－Ｔｏｌｅ姗ｔＮｅｔｗｏｒｋＲｅ∞ａｒｃｈＧｒｏｕｐ）”’致力于Ｄ，ｒＮ的标准化工作。本论文针对ＤＴＮ的路由协议，研究与路由协议相关的三２