内容中心网络非确定性路由查找与转发技术的研究

Named Data Networking (NDN) forwards packets according to the names in packets. An NDN Name, the only identity of a content, has variable and unbounded lengths. The name lookup in NDN devices complies with the longest prefix match. This kind of complex name constitution plus the matching rule make name lookup in NDN as an extremely challenging task..This proposal aims to address the name lookup challenge in NDN by applying the stateful characteristic of NDN which can help NDN devices to identify the loop packets. The name lookup mechanism can simplify the matching process and compress the name table via introduce tiny errors, which can be corrected by NDN networks. In this way, the name table can be loaded into the Commercial devices and the name lookup algorithm can be ran effectively. Specifically, we plan to research on the following three techniques. 1) The model of the approximate name lookup; 2) The algorithms of approximate name lookup; and 3) the implementation and experiments of the proposed approximate name lookup algorithms and mechanisms..The research results of this project will be a good help for further study in NDN, especially for the design and implementation of NDN devices.

内容中心网络以名字作为内容的唯一标识，根据名字进行数据包的查找与转发。由于名字具有不定长、无上界的特点，以及路由查找需要满足最长前缀匹配的要求，使得名字查找成为内容中心网络的重要研究内容和艰巨挑战。确定性名字查找算法需要存储网络的全局信息并在查找过程中严格保证正确性，使其需要巨大的存储空间、极高的计算复杂度。.本项目拟利用NDN网络“有状态”的特性，即自身能够检测数据包回路的特性，研究非确定性路由查找与转发技术，从而有效降低名字路由表的存储空间、提高名字查找引擎的各项性能，使得高速、大规模名字路由表的查找技术能够在商用设备上实现线速名字查找，满足NDN路由器对于名字查找的低存储开销、高查找速度的性能要求，推动NDN在实际网络中的应用和进一步发展。主要研究内容包括：1）非确定性名字查找机制的数学建模；2) 非确定性名字查找算法的研究；3) 非确定性名字查找机制的实现与试验。

内容中心网络作为一种未来互联网的体系结构，其目标是更好地满足用户未来更加快速、便捷地访问互联网内容的需求。与现有的IP网络相比，内容中心网络旨在实现从以设备为中心向以内容为中心转变。与IP网络中的路由器不同，内容中心网络中的路由器根据所请求内容的名字进行路由查找与转发。名字查找比IP地址查找更加复杂、更加困难，主要表现在：1）可变长、不定长、层次化的名字结构比IP地址复杂；2）名字路由表预计将比目前的IP路由表要大2～3个数量级；3）由于内容的频繁发布和删除，名字路由表比IP路由表具有更加频繁的路由更新。链路接口速率的不断提升，再加上名字结构的复杂性，使得在大规模的名字路由表中实现线速名字查找成为一项极其艰巨的任务，需要在名字查找算法、数据结构和系统实现等方面有实质性的创新与突破。.本项目提出了一种基于两级布隆过滤器的快速名字查找方法并进行了性能评价。第一级面向字符串的布隆过滤器用于确定查询的名字所对应的可能的最长名字前缀；第二级合并的布隆过滤器用于找出名字的最长前缀所对应的转发端口。优化后的名字查找引擎仅需要使用234.27 MB存储空间来存放10M名字路由表，且在CPU平台上能实现每秒37,000,000次的名字查找和每秒3,000,000次的更次操作。.本项目的研究成果将极大的推动内容中心网络在现有商用器件上落地。