论文部分内容阅读
随着互联网的不断发展,下一代互联网NGI (Next Generation Internet)的研究已受到了广泛的关注,为实现对更广泛接入终端、异构传输网络的统一高效处理,可将数据的标识和查找的过程抽象为四个层面:连接层面、流层面、承载层面和应用层面。本文重点研究基于连接层面和流层面的报文标识和查找技术。对于连接层面而言,报文标识与查找的过程主要是用于确立报文传输路径、实现报文快速转发,通常称之为路由查找;而对于流层面而言,报文标识与查找的过程则主要是用于实现对不同数据流的差异化控制,可在多种应用场景中实现数据流的不同处理,通常也将该过程称之为包分类。随着IPv4地址的日益紧缺,引入下一代互联网NGI的核心协议——IPv6已成为业界的共识,引起了产业界的广泛关注和认可。与IPv4相比,IPv6具有很多优点,但是,IPv6并没有改变网络设备(如路由器)在数据平面的功能。事实上,128位的IPv6地址给路由器的设计和制造提出了更大挑战,特别是对路由器的核心报文查找技术——路由查找和包分类算法提出了更高的要求。因此,研究能够适用于IPv6的报文查找算法是非常关键的,它是实现下一代互联网高效数据传输的一项基础技术。与此同时,IPv6报头中新增的流标签字段也为下一代互联网数据流的标识与查找带来了新的契机。区别与传统数据流的标识方法,基于流标签的数据流标识可以有效地降低报文中某些字段(如端口、协议等)查找的难度,摆脱数据加密对数据流识别带来的影响。因此,研究基于流标签的数据流标识技术也是非常有意义的。本文一方面深入研究基于通用标识的报文查找技术(包括连接层面的路由查找技术和流层面的包分类技术),提出适合IPv6的报文查找新算法;另一方面研究基于流标签的数据流标识技术,提出面向异构网络的数据流标识方法;最后,本文提出了下一代互联网中面向数据流的体系结构。本文主要贡献和创新点包括如下几个方面:(1)本文研究了用于报文标识和查找的数据查找模型,挖掘IPv6寻址结构的特点、IPv6地址分配的特点,并对规则集的特征进行了深入的研究,在此基础上提出并实现了业界首个应用于IPv6包分类的规则生成器ClassBenchv6,为IPv6包分类算法的设计与评估奠定了基础,并得到了业界的认可。(2)本文研究了连接层面的报文标识和查找技术,提出了三个高效的IPv6路由查找算法:LPFS-OHT、BTLPT和DBH算法。LPFS-OHT算法采用最长前缀优先匹配的思想,将较长前缀所对应的Hash表折叠在较短前缀比特树上,从而实现较长前缀的快速定位,并实现“一次匹配即可停止”,算法相比现有最长前缀优先查找树性能提升了40%。BTLPT算法和DBH算法是基于叶子节点集划分框架的算法。本文首次提出了叶子节点集划分框架,将最长前缀匹配问题转换为精确匹配问题,并具有划分集数量最小化、适合动态更新等优点。基于该叶子节点集划分框架,本文提出了BTLPT路由查找算法。该算法的查找访存次数仅为目前路径压缩前缀树和基于前缀范围算法的50%以内,并且占用很少的内存,该算法的性能与地址长度无关,适合在IPv6中使用。此外,DBH路由查找算法突破了基于长度二分查找算法无法实现动态更新的局限,是迄今为止首个能够实现O(logW)的查找性能的动态算法,在IPv6中可实现最坏情况下仅为7次哈希访存。(3)本文研究了流层面的报文标识和查找技术,提出了两个面向IPv6的包分类算法:ODS-BT和H-LCFST。此外,还提出了基于流标签的报文标识技术。ODS-BT算法采用了新颖的规则集空间划分方法,从而实现了高效查找、内存占用少和适合更新的目标,该算法的查找性能与地址长度无关,在IPv6中具有很好的可扩展性。H-LCFST算法通过对规则集特征进行深入分析,充分利用IPv6规则集的特征来设计数据结构,并提出了多个启发式规则可针对不同的规则集特征构建最优的数据结构,实验结果表明该算法能够广泛适应于不同类型的IPv6规则集。此外,为了进一步利用IPv6流标签在标识数据流方面的优势,本文提出了面向异构网络的流标签数据流标识方法,对流标签做了详细的定义,提供灵活的单流、聚合流的识别能力,并将其应用于端对端QoS等级映射领域,为异构网络提供统一的QoS标识平面。本文对流标签做了系统实现及仿真验证,为流标签的进一步应用打下较好的基础。(4)基于上述报文标识与查找技术的研究基础,本文在最后提出了下一代互联网中面向数据流的体系结构FIA,定义了一个新的商业模型,在可信任可运营网络联盟的框架下,提出了基于数据流的控制平面和数据平面架构,并给出了网络中的实施方案。该方案为实现下一代互联网“更大、更快、更安全、更及时、更方便、更可管理和更有效益”的目标提供了一定的解决思路。