论文部分内容阅读
在过去几十年中,基于TCP/IP网络架构的互联网取得了空前的成功。但是随着新的应用场景出现及人们对多媒体内容需求的急剧增加,传统互联网架构正经受着严峻的考验。因此设计一个能满足新场景和新需求的互联网体系架构,已经成为计算机网络研究领域的重要课题之一。近年来提出的以信息内容为中心的全新的网络架构,正逐渐受到越来越多研究者的关注。而命名数据网络,正是这种新型网络架构的代表,近几年发展尤为迅速,并取得了一系列理论和应用成果。 但是,如何进一步提高命名数据网络路由转发模块的性能仍是研究的重点和难点。路由转发表是该模块至关重要的组成部分,路由转发表不仅要能被快速构建,还要支持高速的动态名字查找。所谓动态查找,是指当进行名字查找时,路由转发表还需同时支持表项的插入、更新和删除操作。 针对这些问题,本文从名字查找的动态性、表的构建效率和节省内存开销的角度考虑,提出了一种基于自适应基数树的高效动态名字查找方法。该方法不仅能利用命名数据网络命名规则和基数树结构的特点,实现动态名字查找和表的快速构建,同时还能利用中间节点大小可以自适应调整的特点,大幅降低内存开销,利用这种新方法实现的路由转发表,本文称之为动态自索引转发表DSIF(DynamicSelf-Index FIB)。 为了使自适应基数树更加符合路由转发表的最长前缀匹配原则,本文还对自适应基数树进行了改进,不仅调整了中间节点和叶子节点的类型,还对插入和查找等操作也进行了相应修改,使得用于路由查找的名字路径无需分解为多级名字前缀进行多次匹配查找,本文只需一次查找操作便可以快速获取正确的转发端口。 此外,为了进一步提升动态名字查找的效率以及降低转发表的内存开销,本文在DSIF中引入了两种现有的空间压缩技术,其中路径节点压缩技术降低了中间节点的数量,而分支延迟扩展技术则节省了长名字前缀的内存开销。同时,这两种技术对于动态名字查找效率的提高也起到了一定的作用。 最终的实验评估表明,利用本文提出方法实现的DSIF能够支持高效的动态名字查找,还能保证路由转发表的构建速度,并在一定程度上节省了新建额外索引的内存开销,能满足转发模块对高性能转发表的需求。