基于局部性原理跳表的内容路由器缓存快速查找机制

• 作者: 张雪贝 潘恬 黄韬
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 内容中心网络 内容路由器 排队网络 跳表 局部性 查找算法
• 年，卷（期）: 2018,（9）
• 所属期刊栏目: 网络技术
• 页码范围: 2029-2043
• 页数: 15页
• 分类号: TP393
• 字数: 13971字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.02029

摘要

当前的互联网流量模型正迅速从端到端通信发展为内容的传播共享.为了适应这种变化,学术界提出了内容中心网络(CCN)的未来网络架构.在内容中心网络中,终端主机根据内容的名字而不是内容所在主机的IP地址进行通信.内容路由器作为底层基础设施,承载着内容请求和内容响应的高速交换的任务.不同于IP路由器的无状态转发模型,内容路由器的数据平面因具备网络缓存功能而更加复杂.尽管网络缓存可以有效减轻网络拥塞,但这样的设计也将额外的状态附加到网络中间节点上,这在一定程度上破坏了网络设计中的“端到端”原则.这些额外状态给路由器的数据平面造成了性能负担,也使内容路由器数据包转发成为当下热门的研究课题.内容路由器包含转发信息库(FIB)、待定兴趣表(PIT)和内容缓存(CS)三个模块.针对基于名字的最长前缀匹配、名字路由表的状态爆炸、待定兴趣表的频繁更新等问题,目前大量研究工作围绕FIB和PIT开展性能优化.然而,尽管CS也存在潜在的性能问题,却较少有工作对其进行讨论.FIB、PIT和CS在内容路由器中以流水线的形式存在,而流水线的处理速度由最慢的流水段决定.因此,为了提高内容路由器的整体性能,有必要首先确定其性能瓶颈,然后进行针对性的优化.在该文中,为了避免盲目的性能优化,我们首先建立了基于开放排队网络的数学模型.通过定量分析,文章发现CS是整个路由器的性能瓶颈.目前,已有工作采用跳表作为CS的数据结构.然而由于其O(logn)的查找复杂度,经典跳表在处理高速网络流量时依然存在性能问题.受到网络流量中广泛存在的时间局部性和空间局部性的启发,我们提出了局部性原理跳表来提升CS的性能.在新的设计中,考虑到新到达的内容请求可能与之前到达的内容请求共享相同的名字前缀,且所请求的内容块通常处于邻近的存储空间,因此在查找跳表时可以直接从该前缀先前命中的跳表结点附近开始查找.这样可以避免每次都从跳表的头结点开始重复的查找,从而节省大量时间.实验结果表明,局部性原理跳表可以在x86处理器上实现1.796 Mpps的单线程吞吐率,这是经典跳表查找速度的三倍.对于500B大小的数据包包长来说,CS的单线程吞吐率可以高达7.016 Gbps.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄韬	北京邮电大学网络与交换技术国家重点实验室	61	544	10.0	21.0
3	潘恬	北京邮电大学网络与交换技术国家重点实验室	2	7	1.0	2.0
9	张雪贝	北京邮电大学网络与交换技术国家重点实验室	1	1	1.0	1.0