NDN中基于树比特位图的高效路由查找技术

摘要

近年来，互联网飞速发展，逐步深入日常生活的方方面面。传统TCP/IP网络以位置为驱动的通信模型越来越不适应当下或未来互联网以信息和服务为驱动的需求。针对传统网络在移动性、安全性和可扩展性方面的缺陷，新型网络架构应运而生。命名数据网络(Named Data Networking，NDN)就是一个典型的代表。它带来了全新的以数据为驱动的通信模型——将关注的焦点从“在哪里”转移到了“是什么”。
　　通信模型的变革进一步催生了路由转发机制的演进。在IP网络中，路由转发的关键操作是路由查找，即依据数据包的目的IP地址，在转发信息表中进行最长前缀匹配。而在NDN的转发过程中，涉及两种数据包，三张信息表;路由查找不仅涉及最长前缀匹配，还需要进行精确匹配和维护频繁的表项更新;查找的对象不再是简单、定长的IP地址，而是结构复杂、不定长且无理论上限的数据名。因此，在查找性能、更新效率和存储可扩展性等诸多方面，NDN数据名查找都面临更严峻的挑战。
　　本文首先从IP地址查找入手，再到NDN数据名查找，分别针对上述三个挑战对相关工作进行了广泛的调研和全面的综述。基于对应用需求和相关工作的的深入了解，本文以字典树为基础，结合树比特位图(TreeBitmap)技术和数据名分层编码技术，提出了一种新型的查找结构(Bimap-basedNameTrie，BNT)，并设计了相应的查找和更新算法。实验表明，BNT以存储开销为代价，在查找速度和更新性能方面较之前人工作都获得了大幅提升，相比于NCE(NameComponentEncoding)查找与更新时间仅为其1％。虽然牺牲了存储效率，但是存储一个包含近3百万条数据的转发信息表，只需593.72MB的内存。
　　针对BNT单个节点在极端情况下可能产生空间爆炸的隐患，本文设计了一种巧妙的编码切割方案，并对特里树的节点结构进行优化，去除了大量的冗余指针，在保持查找和更新优势的同时，提升了存储可扩展性。在小数据下，与BNT相比存储空间减少了33％;在一千万条数据名的大数据下，存储开销仅为720.84MB，并同时拥有和BNT近似的查找与更新开销。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景和意义

1．1．1 命名数据网络

1．1．2 路由转发

1．1．3 路由查找

1．2 国内外研究现状

1．3 主要研究内容

1．4 本文的组织结构

第2章 相关工作介绍

2．1 IP地址查找

2．1．1 查找加速技术

2．1．2 存储压缩技术

2．1．3 高效更新技术

2．1．4 树比特位图

2．2 NDN数据名查找

2．2．1 基于哈希的数据名查找

2．2．2 NDN数据名分层编码

2．2．3 NDN基于压缩特里树的数据名查找

2．3 小结

第3章 NDN中基于树比特位图的路由查找技术

3．1 BNT节点结构

3．2 构建BNT

3．2．1 分层数据名编码

3．2．2 BNT构造算法

3．2．3 BNT数据名查找算法

3．2．4 BNT更新算法

3．2 BNT算法复杂度分析

3．3 实验结果与评估

3．3．1 实验环境

3．3．2 实验数据

3．3．3 实验评估

3．4 小结

第4章 NDN中基于编码切割的数据名查找算法

4．1 CBNT算法动机

4．2 CBNT节点结构

4．3 CBNT树形结构

4．4 CBNT相关算法

4．4．1 CBNT构造算法

4．4．2 CBNT查找算法

4．4．3 CBNT更新算法

4．4 CBNT算法复杂度分析

4．5 实验结果与评估

4．6 小结

结论

参考文献

致谢

附录A 攻读学位期间发表的学术论文