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

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. .

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

与IP网络不同，内容中心网络（Named Data Networking,NDN）根据内容的名字进行路由查找与转发。名字查找比IP地址查找更加复杂、更加困难，主要表现在：（1）可变长、无上界、层次化的名字结构比IP地址复杂；（2）名字路由表预计将比目前的IP路由表要大2～4个数量级；（3）由于内容的频繁发布和删除，名字路由表比IP路由表具有更加频繁的路由更新。链路接口速率的不断提升，再加上名字结构的复杂性，使得在大规模名字路由表中实现高速名字查找成为一项极其艰巨的任务。.本课题探索基于多线卡协作的大规模名字路由表高速查找技术，研究内容包括：（1）优化基于词元编码的高速名字查找技术，压缩名字路由表的存储空间，提高单个名字查找引擎的吞吐率；（2）研究基于多线卡协作的分布式名字路由表存储机制，使得路由器能够存储大规模名字路由表；（3）设计分布式更新策略，使得在不降低系统吞吐率的前提下，实现名字路由表的快速更新。.在国家自然科学基金青年基金资助的2015.01～2015.12期间（1年），共发表论文5篇（注明受本项目NSFC No.61402254资助），其中CCF A类期刊1篇，CCF A类会议1篇，B类会议1篇，其他论文2篇；构建基于词元编码的分布式名字查找原型系统，并将源代码和测试数据向外部开发，网址：http://s-router.cs.tsinghua.edu.cn/namelookup.org/。.通过网络爬虫在全球4个地点的抓取，已获取80M个域名作为名字路由表中的名字前缀，进行名字查找引擎的测试。单名字查找引擎的查找速率已经超过50M次查找每秒，更新速率达到1.2M次每秒，平均单次查找时延小鱼100 us，平均每个名字前缀占用49.6字节的存储空间。在多线卡协作方式下，在仅使用原先存储5.1%的存储空间下，依然保持单卡的查找速度和访问延迟。.本项目通过研究多个线卡间协作来实现大规模名字路由表在NDN 路由器中的存放，并结合词元编码技术来进一步压缩名字路由表的存储空间和加快名字查找的速度，设计并实现支持线速查找、高速更新的分布式名字查找技术，为NDN技术的进一步发展和商用，做出了贡献。