大规模名字路由表高速查找技术的研究

Current Internet was designed in 1960s, with the original purpose to provide end-to-end conversations and communications, where participating entities are positioned with unique IP addresses. Today, half a century after its invention, the Internet has witnessed profound evolution in technology and user needs. Information technologies provide powerful means to produce, distribute and retrieve information (or, data content in general); overwhelming data content and proliferating Internet usage have, therefore, made content sharing the dominant need of Internet users - a transition that has posed fundamental challenges to the design philosophy of the Internet. Content-Centric Networking (CCN), recently proposed as a clean-slate future Internet architecture, embraces this fundamental transition with an innovative perspective - instead of addressing the location of wanted contents, the Internet should operate based on the identity of contents, naturally fitting the content centric property of today's Internet usage. Named Data Networking (NDN) is an instance of the approach. In particular, every distinct content/entity is referenced by a name that is unique within some network domain. Accordingly, communication in CCN is no longer address-based, but name-based. CCN routers forward packets based on the requested content name(s) carried by each packet, by looking up a forwarding table consisting of content name prefixes. CCN name lookup complies with longest prefix matching (LPM) and backbone CCN routers can have large-scale forwarding tables. Wire speed name lookup presents a research challenge because of stringent requirements on memory occupation, throughput, latency and fast incremental update. Practical name lookup engine design and implementation, therefore, require elaborate design-level innovation plus implementation-level re-engineering. This proposal aims to address the issue of high-speed NDN routing lookup. Specifically, we plan to study the following technical details: 1) effective compression algorithm for massive name lookup routing table; 2) methods to reduce the searching complexity of name table lookup; 3) exploring new architecture of applying cache mechanism to accelerate the name table lookup speed as well as more efficient cache replacement strategy; 4) elaborating the optimized hardware implementation to further boost the name lookup speed. Research results will provide potential technical support to the design and implementation of future NDN routers.

互联网应用正面临着转型时期，信息共享与有效检索已成为用户的主要需求，而早期的设备共享的必要性已经减弱。因此，以内容为中心的新型互联网最近被提出，其特征之一是用名字来标识内容，因而有别于目前的用IP地址来定位主机。由字符串组成的名字长度较长且不固定，名字前缀组成的路由表将比现有的IP路由表大几个数量级，且需要支持更加快速的路由增量更新。名字路由查找远比IP路由查找复杂得多，因而高速名字最长匹配查找成为一个富有挑战性的难题。本申请以NDN网络高速路由查找为背景，旨在解决大规模名字路由表的高速查找问题。具体地，计划研究以下内容：1）有效压缩大规模名字集合路由表的算法；2）降低名字路由表查找计算复杂度的方法；3）利用cache提高查找速度的结构和替换策略；4）利用硬件加速名字路由查找的优化实现方法。研究结果将对设计与实现NDN路由器提供技术支持。

本课题研究的主要内容和贡献包括：.1）提出了一种基于贪心策略和近似完美哈希表的名字查找机制。基于前缀分布特性的贪心策略能有效减少最长前缀匹配过程中哈希表的查找次数，从而改进名字查找引擎的性能；近似完美哈希表来代替传统的哈希表，使得在保持O(1)的哈希查找速度的同时，能够有效的压缩存储空间，提高查找速率；.2）提出了一个统计最优的最短搜索路径动态规划算法，该算法能够根据路由转发表中地址前缀的分布情况动态的生成统计最优的搜索路径，从而有效的减少最长前缀匹配过程中，哈希表的探查次数；.3）名字查找比IP 地址查找具有更高的复杂度，这使得大规模的、涉及多张表的高速率、低时延转发成为一项艰巨的任务。为此，我们提出了“统一索引”的概念，把三张表的索引整合在一起，只需一次查找就能得出结果，避免了原来的三次查找，降低了转发时延并提高了查找速率；.4）提出一种名为CONSERT 的最优压缩算法，经过压缩后的最优转发表拥有的前缀数量最少，而且转发的行为保持不变。实验表明，CONSERT 算法能够有效减少名字转发表中的前缀数量，进而降低存储开销；.5）在数据平面上，PIT 除了记录路由的状态，同时还具有请求聚合的功能，即将多个相同的请求聚合为一个，以减少向网络上游（从用户到服务器方向）转发的流量。提出对PIT 的一种全新的观点：PIT 是一个基于TTL (Time To Live) 的缓存。建立了PIT 的分析模型，并给出了对上述两个指标的计算方法。模型和仿真的结果非常契合。. 发表（录取、投出）学术论文36多篇，其中在ACM/IEEE Transactions on Networking、IEEE JASC、IEEE INFOCOM等计算机学会制订的A类会议、A类期刊发表（录用）了论文7篇。获得2014 IEEE/ACM IWQoS Symposium最佳论文奖，这是该会议自成立21年来Best Paper Award首次奖励给亚洲研究学者。我们的部分研究成果被引用在美国自然基金重点研究计划的NDN网站上（https://named-data.net/publications/on_incremental_deployment_ndn/）。课题执行期间，课题负责人多次在国内召开的专业会议上做特邀技术报告