论文部分内容阅读
摘要:随着计算机网络技术的不断发展,网络为用户提供的服务正由传统的数据通信向包括视频会议、VOIP等多媒体实时应用在内的多样化服务转变.路由和转发作为分组网络的核心技术,在用户新业务需求的驱动下正面临着严峻的挑战.首先,基于跳数的最短路径路由算法已不能满足多媒体实时业务可靠服务质量(QoS)路由的需求.设计有效的多维QoS约束下的分离路径路由算法,是新一代路由算法研究需要解决的问题.第二,要为业务进行端到端QoS控制服务就必须提供域间QoS路由,如何降低路由建立过程中所需扩散的数据量,提高域间QoS路由的可扩展性是QoS路由又一需要解决的关键问题.第三,现有IP网络难以为同一会话流的数据包提供确定的路由传输,这不仅给QoS控制带来了困难,也给网络计费、流量工程等管理和优化操作增加了难度.如何在IP网上提供快速灵活的路由转发也是网络QoS路由转发研究的关键问题.第四,网络精确的QoS控制往往依赖于对网络性能边界的定量计算,而传统的网络性能分析模型对具有高突发性和可变性的互联网流量不再有效.如何借助新的网络理论分析工具,对互联网业务流的QoS性能边界进行准确的定量运算,是QOS路由转发研究中十分值得研究的问题.针对上述QoS路由与交换转发中的重要问题,本文进行了全面深入的研究.论文的主要创新工作如下:(1)针对可靠QoS路由中现有多约束分离路径算法难以保证在任意网络中求得客观存在的可行解问题,提出了精确算法设计原则,设计了求解多约束最短链路分离路径对的精确算法LIDOMPA (Link Disjoint Optimal Multi-constrained Paths Algorithm),能够保证求得任意网络中客观存在的最优解.在此基础上,将LIDOMPA扩展为求解多约束最短节点分离路径对的精确算法NODOMPA(Node Disjoint Optimal Multi-constrained Paths Algorithm).理论分析和大量实验证明了本文所提算法能够有效求解多维QoS约束下的最短分离路径对,并实现了较低的算法复杂度.(2)针对域间QoS路由的扩展性问题.提出了一种基于均匀折线的几何聚合方法.为进一步提高聚合性能,将均匀折线法与线段聚合法相结合,提出了一种基于六元组的混合式QoS信息几何聚合算法,该算法可根据聚合精确度选择不同的聚合模型进行聚合,聚合后的信息仅采用六元组数据便可表示,实现了常数阶O(1)的空间复杂度.定义了聚合误差率作为准则来精确衡量几何聚合算法性能的优劣.通过实验证明了本文所提聚合算法的性能优于现有算法,可以实现更低的聚合误差率.实验结果还表明,所设计聚合算法时间开销可行.(3)针对现有网络难以实现可扩展的快速、灵活、安全转发问题.提出了一种基于链路接口ID编码(LIC:Link interface ID Code)的转发方法(LICF:LIC-based Forwarding).该方法通过在通信的源和目的间预先建立起面向连接的LIC路径,可直接根据LIC对数据包进行路由,避免了路由表查询开销,实现了基于显式路由的灵活快速转发,有助于网络服务质量的提高和流量工程的实现.由于不需要路由器存储和管理除路由表外的额外信息,LICF可获得良好的扩展性.由于可隐藏数据包报头的IP地址信息,LICF能有效增强网络通信的安全性.通过原型系统的实验验证了LICF能实现比现有转发技术更低的端到端延时并能有效提高网络的吞吐量和传输性能.(4)在创新点(3)的基础上,将队列调度技术和分形漏桶技术引入到LICF网络,提出了QLICF(QoS-enhanced LICF)网络模型,使之能为业务提供更强的QoS服务.进一步利用近年来新兴起来的网络分析数学工具——网络微积分理论,对QLICF网络中自相关流的端到端延时上界、抖动上界、无丢包节点缓存需求大小上界等确定性QoS性能边界进行了讨论.给出了这些性能边界的定量计算结果.通过大量数值分析讨论了这些性能边界随数据流属性、优先级、网络路径长度等网络参数的变化规律.为进一步优化网络性能,实施网络QoS控制提供了理论依据.