内容中心网络CCN(Content Centric Networking)的提出是网络技术的一次革新,传统IP网络关心信息“在哪儿”,而CCN直接关心请求的数据“是什么”,数据本身成为因特网架构中的核心要素,从根本上解决IP地址耗尽、安全性和移动性等传统问题,其系统架构及相关支撑技术研究已成为热点。查表是内容中心网络的研究重点之一。CCN中信息或者数据的传递基于数据名字而不是IP地址,表项规模比IP路由表高出两个数量级,达到108条;基于TCAM或分布式存储单元等传统的实现手段不能满足CCN表项的容量需求。目前对CCN查找技术的研究尚处于起步阶段,既缺乏整体的解决思路,也没有针对性的高效算法,需要在理论模型、算法研究、工程实现等层面展开全方位的研究。本文围绕其转发信息表FIB与未决兴趣表PIT这两大不同需求特点的查找问题开展了以下研究工作:1、描述IP前缀集的二进制树模型无法用于表示FIB前缀集,必须寻找新的合理模型。根据CCN前缀集层次化命名的基本属性特征,提出一种基于有根树的FIB名字前缀树模型,并分析总结实际域名特点,指出了该模型参数的统计特性。该模型具有较强的理论和工程应用价值。2、已有空间利用率高的算法,如布鲁姆过滤器,通常要求很高的存储器访问带宽,被迫依赖于分布式存储单元实现,容量受限,不能满足FIB的规模需求。利用大容量存储单元一次访问可获得很宽数据的特点,并考虑实际FIB的负载特性,提出一种负载均衡的FIB最长匹配快速搜索方法,称为EMA-NPMA算法,并分析给出了调整成功率定理以及任意次块空间比例的理论计算式,在此基础上给出误判率、吞吐率的估算方法。理论分析和仿真实验表明,在付出一定误判率代价的条件下,该算法很好地满足了名字前缀匹配在空间和时间上的双重要求,每一条目表示仅需10多个比特,且90%以上的前缀最长匹配均可以一次存储器访问完成。以一片容量为1.25G比特的RLDRAM为例,算法可在误判率低于5%的条件下,以每秒约60M次的包转发速率,实现规模高达100M条的名字前缀的最长匹配。3、基于d-left的完美哈希可获得很好的空间利用率,但每一个条目查询可能需要d次查找,吞吐率低。本文首先提出一种基于最小完美哈希函数(MPHF)的哈希桶索引机制。分析发现,d-left可模型化为一个可容纳更多冲突项的哈希桶,为此,提出建立虚拟哈希桶并利用所提的索引机制来确定条目所在的子表,实现d-left哈希表查找的无误判准确定位,将对哈希表的访问限制到确定的一次。分析和仿真表明,算法为每一条目付出约10比特的空间代价,但只需一次存储器访问,从而可利用片外大容量存储单元来解决CCN前缀集这样超大规模哈希表的查找加速难题。4、MPHF函数适用于面向静态条目集合的应用场景,用于动态数据集的索引时,由于条目更新造成MPHF函数变化带来更新效率问题。为此,对MPHF函数更新效率问题进行数学建模和理论分析,提出条目添加的平均搬移数定理,理论上给出了搬移次数与可选MPHF函数个数间的关系,并因此提出用地址映射表来实现无搬移的快速更新。5、PIT作为CCN区别于IP的重要特征,其选择性超时老化和逐包处理机制,大大增加了查表处理的难度。总结归纳不同PIT流量对搜索引擎的不同处理要求,提出一种PIT搜索引擎的操作模型,定量描述不同PIT流量分布对搜索引擎的吞吐率需求。6、基于定时扫描的老化方法对存储器带宽要求高,基于软件维护的老化方法则实时性差。PIT表项规模大、查找关键字长且可变,适合采用布鲁姆过滤器作为搜索引擎。本文在布鲁姆过滤器双缓存老化机制的基础上,提出了适合PIT的改进算法A2-PIT,以很少的精度损失,即可实现无需额外扫描带宽和通信代价的高效选择性超时老化。7、PIT查找的最坏性能发生在链路中所有包均为新兴趣包的情形,而新兴趣包均为布鲁姆过滤器的无匹配条目。本文在研究了布鲁姆过滤器条目无匹配时的特点的基础上,提出一种布鲁姆过滤器无匹配查找加速控制方法,只需付出很少的主处理器逻辑资源代价,即可大大改善吞吐率最坏性能,将包转发率提高到约为原来的1.5倍。