基于分布式词元编码的大规模名字路由表压缩与查找技术的研究

项目名称： 基于分布式词元编码的大规模名字路由表压缩与查找技术的研究

项目编号： No.61402254

项目类型： 青年科学基金项目

立项/批准年度： 2015

项目学科： 计算机科学学科

项目作者： 汪漪

作者单位： 清华大学

项目金额： 10万元

中文摘要： 与IP网络不同，内容中心网络（NDN）根据内容的名字进行路由查找与转发。名字路由表预计含有1亿到10亿个名字前缀，并且名字前缀长度可变、无上界，比目前的IP路由表要大2～4个数量级。链路接口速率的不断提升，再加上名字结构的复杂性和频繁的路由更新，使得在路由器中存储大规模名字路由表，并实现高速名字查找成为一项极其艰巨的任务。 本课题探索基于词元编码的大规模名字路由表压缩和分布式查找技术，研究内容包括：（1）优化基于词元编码的高速名字查找技术，压缩名字路由表的存储空间，提高单个名字查找引擎的吞吐率；（2）研究基于多线卡协作的分布式名字路由表存储机制，使得路由器能够存储大规模名字路由表；（3）设计分布式更新策略，在不降低系统吞吐率的前提下，实现名字路由表的快速更新。本课题研究的预期成果将对提高NDN路由器性能起到关键作用，为NDN的研究提供重要支撑。

中文关键词： 内容中心网络；名字路由表；名字查找；最长前缀匹配；词元编码

英文摘要： Different from IP network, Named Data Networking (NDN) forwards packets by content names, which have variable and unbounded lengths. A name routing table could contains 100 million, even 1000 million name prefixes, which is several orders of magnitude larger than the current IP routing table. This kind of complex name constitution plus the huge-sized name routing table makes wire-speed NDN name lookup an extremely challenging task. This proposal aims to address the issues of name routing table compression and high-speed name lookup by applying the distributed component encoding in the NDN router. Specifically, we plan to study the following 3 technologies: (1) Compressing the name routing table and improving the name lookup speed by optimizing the process of name component encoding in a single name lookup engine; (2) Studying the distributed cooperation mechanism among the line-cards to story the large-scale name routing table in a router; (3) Designing the distributed update scheme to implement fast update of the name routing table with negligible performance degradation. The research results of this project will be a good help for further study in NDN, especially for the design and implementation of NDN routers.

英文关键词： Named Data Networking；Name Table；Name Lookup；Longest Prefix Match；Component Encoding