论文部分内容阅读
内容中心网络作为一种未来互联网的体系结构,其目标是更好地满足用户未来更加快速、便捷地访问互联网内容的需求。与现有的IP网络相比,内容中心网络旨在实现从以设备为中心向以内容为中心转变。与IP网络中的路由器不同,内容中心网络中的路由器根据所请求内容的名字进行路由查找与转发。名字查找比IP地址查找更加复杂、更加困难,主要表现在:1)可变长、不定长、层次化的名字结构比IP地址复杂;2)名字路由表预计将比目前的IP路由表要大2~3个数量级;3)由于内容的频繁发布和删除,名字路由表比IP路由表具有更加频繁的路由更新。链路接口速率的不断提升,再加上名字结构的复杂性,使得在大规模的名字路由表中实现线速名字查找成为一项极其艰巨的任务,需要在名字查找算法、数据结构和系统实现等方面有实质性的创新与突破。为攻克线速名字查找这个关键技术,本文提出、实现了多种创新的方法与机制,取得如下成果:1.设计与实现了一个基于GPU的线速名字查找引擎。创新的名字路由表查找算法、基于GPU体系结构的多数据流流水线技术和名字交织存储技术,帮助名字查找引擎在0.1毫秒系统时延的约束下实现线速名字查找。基于实际系统的大量实验结果表明:使用现有的低成本的商业化GPU设备实现线速名字查找是可行的;在10M名字路由表(具有10,000,000条名字前缀)中,基于GPU的名字查找引擎可实现每秒63,520,000次的名字查找,并保证名字查找时延小于0.1毫秒。2.提出了一种基于两级布隆过滤器的快速名字查找方法并进行了性能评价。第一级面向字符串的布隆过滤器用于确定查询的名字所对应的可能的最长名字前缀;第二级合并的布隆过滤器用于找出名字的最长前缀所对应的转发端口。优化后的名字查找引擎仅需要使用234.27MB存储空间来存放10M名字路由表,且在CPU平台上能实现每秒37,000,000次的名字查找和每秒3,000,000次的更次操作。3.为提升基于GPU的名字查找引擎的可扩展性和实用性,提出了基于名字词元编码的可扩展名字查找方法。在局部词元编码机制和状态转移数组的协助下,名字词元编码方法均衡了存储空间、查找吞吐率、查找时延、名字路由表构建速度和更新速度等各项性能,使得基于GPU的名字查找引擎成为实际可部署的线速名字查找引擎。