面向命名数据网的高性能内核级网络缓存方法.pdf
《面向命名数据网的高性能内核级网络缓存方法.pdf》由会员分享,可在线阅读,更多相关《面向命名数据网的高性能内核级网络缓存方法.pdf(8页珍藏版)》请在咨信网上搜索。
1、Computer Engineering and Applications计算机工程与应用2023,59(16)面向命名数据网的高性能内核级网络缓存方法杨济科1,嵩天1,李天龙2,杨雅婷11.北京理工大学 网络空间安全学院,北京 1000812.北京理工大学 计算机学院,北京 100081摘要:命名数据网(named data networking,NDN)是一种以信息为中心的新型网络架构方案,网内缓存是其核心功能之一。现有缓存模块主要以应用级缓存实现为主,存在网络操作效率低、设备兼容性差、部署位置受限等问题。相比于应用级缓存模块,内核级缓存模块可以直接且广泛地部署于通用网络设备上,有助于推动
2、网内缓存技术的规模应用以及NDN网络方案的实际部署。然而,由于NDN网内缓存机制涉及频繁的逐包缓存操作,将网内缓存功能引入内核将会影响内核处理性能。针对这一性能问题,设计并实现了一种内核级缓存方法。该方法维护一个哈希表进行缓存的精确查找,利用NDN名称的结构性,在节点间构建字典树支撑NDN缓存模糊匹配功能。提出使用细粒度的逐槽锁保护缓存查找表,原子操作保护替换队列,将缓存操作多线程并行化。在Linux内核中实现了所提的多线程缓存模块,实验结果表明,所提出的方法可以将缓存模块查找延迟降低至现有方案的一半,并且通过多线程将吞吐量提升至6.785 Mpacket/s。关键词:命名数据网;网内缓存;名
3、称查找;多线程文献标志码:A中图分类号:TP393doi:10.3778/j.issn.1002-8331.2204-0068High-Performance Kernel-Level In-Network Caching for Named Data NetworkingYANG Jike1,SONG Tian1,LI Tianlong2,YANG Yating11.School of Cyberspace Science and Technology,Beijing Institute of Technology,Beijing 100081,China2.School of Comput
4、er Science and Technology,Beijing Institute of Technology,Beijing 100081,ChinaAbstract:Named data networking(NDN)is a new information-centric network architecture.In-network caching is oneof core functions in NDN.Current cache modules are mainly deployed in user-level,which brings issues of network
5、opera-tion efficiency,compatibility among devices and limitation of deployment location.Comparing to user-level cache mod-ule,kernel-level cache module can be directly and widely deployed on general net devices,so it can boost the large-scaledeployment of in-network caching and the practical use of
6、NDN solutions.However,due to the frequent per-packet cachingoperations in NDN,introducing cache into kernel may cause performance issues.To solve these performance issues,thispaper designs and implements a kernel-level cache method.The cache method uses a hash table for exact cache lookup andutilize
7、s the naming conventions of NDN to construct a trie for prefix cache lookup.Furthermore,this paper presents anapproach of using fine-grained per-slot locks for lookup table and atomic operations for replacement queues to parallelizecache operations.The multi-thread cache module is implemented in the
8、 Linux kernel.The experimental results show thatthe proposed cache scheme reduces the lookup latency by half comparing to current solutions,and boosts the throughputup to 6.785 Mpacket/s via multithreading.Key words:named data networking;in-network caching;named lookup;multi-thread网络、通信与安全基金项目:国家重点研
9、发计划(2020YFB1806000)。作者简介:杨济科(1996),男,硕士研究生,研究方向为信息中心网络、网内缓存;嵩天(1980),男,博士,教授,CCF高级会员,研究方向为网络体系结构、网络安全;李天龙(1997),男,博士研究生,研究方向为新一代互联网体系结构、信息中心网络;杨雅婷(1994),通信作者,女,博士,助理教授,研究方向为新一代互联网体系结构、信息中心网络,E-mail:。收稿日期:2022-04-06修回日期:2022-06-20文章编号:1002-8331(2023)16-0240-082402023,59(16)命名数据网(named data networking
10、,NDN)1是一种以信息为中心的新型网络架构,它将网络从现有基于主机地址的端到端通信模式改为基于数据名称的内容获取模式。2009年Jacobson等人提出了信息中心网络(information-centric networking,ICN)2的基本框架,在其影响下Zhang等人3于2010年成立了NDN项目,对这种新型网络架构展开研究,该项目现已获得学术界和工业界的广泛关注。在NDN中,数据依据信息名称而非主机地址传输。因将传输数据与主机地址解耦,NDN可以在路由器上缓存经过的数据包,从而利用缓存包直接在网络中满足将来的数据请求,不用将请求发送至远端服务器。利用网内缓存,NDN可以降低内容获取
11、延迟并提升网络性能。为了研究便利,现有的NDN缓存模块大多实现并运行在应用层。Mansilha等人4提出了DPDK-HCS,但是该方法依赖数据平面开发套件(data plane developmentkit,DPDK)实现,只能适用于特定的高端网络设备,不能直接运行在通用网络设备中。当前运用最广的NDN实现是NFD(NDN forwarding daemon)5,然而NFD为了研究便利而在应用层实现,未考虑实际运行性能,具有较高的内核空间到用户空间的拷贝与交换代价,存在网络操作效率低的问题。为应对现有应用级缓存实现带来的设备兼容性差、网络操作效率低等问题,内核级NDN缓存模块实现可成为一个突破
12、口,适配通用网络设备,并且避免额外的用户空间与内核空间的信息交换,有助于NDN及其相关技术的进一步演进与部署。内核级缓存需要实现在软中断(Softirq)上下文中,通过锁机制保证多线程并行操作的正确性。内核包处理过程处于软中断上下文中,缓存操作也应处于同一上下文中以避免额外的切换代价。软中断由多个处理器分多线程并行执行,因此内核中的缓存模块需要通过锁机制支持线程间协同,以适应软中断上下文环境,避免共享的数据被同时访问或修改而发生错误。锁机制的并行效率是内核级缓存性能的关键,而锁的结构和查找结构是相关的,因此缓存查找结构也需要针对多线程进行设计。由于NDN缓存需要面对逐兴趣包的查找、逐数据包的插
13、入和替换,每个操作都需要锁的保护进行。假如查找结构没有良好的多线程支持,只能使用粗粒度的锁协同,并发操作会因为锁的竞争而被阻塞,严重影响缓存的性能。如图1所示,缓存查找表上的粗粒度全局锁虽然可以保护并发访问的正确性,但是只允许单个线程同时访问,也就无法充分发挥出多线程缓存的性能。因此,在设计缓存查找数据结构的过程中,除了考虑其本身的查找和更新速度,还需要考虑对多线程并行的适应性。此外,缓存的模糊匹配也为查找结构设计带来了额外的挑战。NDN缓存查找时除精确匹配以外,还使用模糊匹配以更好地利用缓存中的数据。缓存模糊查找使用全子名称匹配(all sub-name matching)将兴趣包与以其名称
14、为前缀的数据包匹配,这一匹配模式需要更复杂的缓存查找结构来支持,目前大多数NDN缓存方案并没有支持这一查找模式6。其不同于广受研究的转发信息表(forwarding information base,FIB)中模糊查找的最长前缀匹配(longest prefix matching),因此,传统面向FIB的名称查找研究并不直接适用于缓存模块。针对上述问题,本文设计了一种高性能的内核级NDN缓存模块,并在Linux内核中实现。该缓存模块支持低延迟的缓存精确匹配和模糊匹配查找,通过高效的缓存操作并行化提高吞吐量。本文的主要贡献集中在以下三点:(1)提出了一种快速缓存查找数据结构,该结构使用哈希表进行
15、精确匹配,并在节点间构建字典树。在字典树上从名称前缀开始进行深度优先搜索实现模糊匹配,可以满足NDN缓存的快速查找需求。(2)针对内核软中断上下文的多线程环境,提出了基于锁和原子操作的并行缓存算法。算法使用逐槽锁保护缓存查找表,运用原子指针管理替换队列,从而实现高效并行缓存操作,显著提升缓存吞吐量。(3)为验证所提方法的真实有效性,在Linux内核中实现了上述缓存方法。实验结果验证了本文方案的有效性。1相关工作1.1NDN名称查找名称查找是缓存模块的关键组成,缓存模块需要通过兴趣名找到缓存中与兴趣匹配的数据包。现有查找方法可以分为两类:基于字典树的方法和基于哈希的方法。基于字典树的查找方法将名
16、称存储在字典树结构中,可以压缩查找表存储空间。NCE7通过名称编码构建了一个内存高效的字典树。Song等人8设计了一个基于Patricia树的方法来解决10亿级的名称前缀查找。然而,基于字典树的查找方法性能与名称长度密切相关,且更新操作繁琐,因此更适用于转发信息表而非缓存查找。与之相对的,基于哈希的查找方法更适合长名称匹配并支持高频更新。Varvello等人9使用开放地址哈希表支持10 Gbit/s转发速率下的待定兴趣表(pending数据包数据包兴趣包兴趣包线程1线程2线程3线程4竞争锁!缓存查找表缓存替换队列数据存储区共享的缓存空间图1多线程缓存的锁竞争问题Fig.1Lock conten
17、tion in multi-thread caching杨济科,等:面向命名数据网的高性能内核级网络缓存方法241Computer Engineering and Applications计算机工程与应用2023,59(16)interest table,PIT)操作。Huang等人10提出使用计数二分搜索在哈希表上实现最长前缀匹配,同时还可以支持快速的更新操作。Wang等人11设计了一个用于FIB查找的两阶段布隆过滤器NameFilter,它在第一阶段确定匹配的名称长度,第二阶段找到转发的出口。然而,上述基于哈希的查找方法实现的查找模式只有精确匹配和最长前缀匹配,而NDN需要缓存查找除精确匹
18、配外,还支持全子名称匹配,将兴趣与包含其名称为前缀的数据包进行匹配,使得用户可以通过缓存尽快发现任意匹配的数据,并构造接下来请求的兴趣名6。这一模式目前没有被基于哈希的查找方法所支持。1.2高性能网内缓存实现目前关于NDN缓存的研究,更多聚焦于提升命中率的缓存策略,而关于网内缓存自身速度的研究并不多。NFD5使用C+标准库中的set实现了基于红黑树排序的缓存。Pan等人12利用了到达时间接近的兴趣包名称连续性,实现了位置感知跳表(locality-aware skiplist),以通过上一个被访问的具有相同前缀的包,快速找到当前的目标,而非从表头开始查找。Qazi等人13称B树时间复杂度低于跳
19、表,因此使用B树对缓存构建两级索引,分别为文件树和块树。Zhang等人14使用基于压缩字典树的布隆过滤器快速过滤缓存中不存在的查找请求,降低了低命中率时的查找延迟。Khatouni等人15给出了一个CCN路由器的内核级实现CCN-par,使用线性哈希表索引缓存中的数据包,并用一个工作队列处理到达的网络包。然而这些方法未考虑并行化,限制了其通过多线程进一步提升吞吐量。而现有的并行缓存方法主要致力于将包分给不同的缓存线程,每个缓存线程只维护自己独占的缓存数据结构以避免协同问题。So等人16使用基本的链式哈希表做索引,将包的全名称哈希值作为线程分配依据,但是这样难以实现缓存的全子名称匹配。Mansi
20、lha等人4提出将同一前缀下的包分配给同一个处理器,以利用同一前缀下兴趣接连到达的规律,但是可能导致处理器间负载分配不均衡。NDN-DPDK17在发出和收到的包上附加额外标记,以将模糊匹配成功发回的包分配给原本负责处理请求的线程,需要路径上所有设备都对网络包做额外修改,而且仍然不完全支持缓存的模糊匹配。除此之外,上述的多线程方法使用了针对特定硬件的用户层网络驱动程序,也意味着它们无法移植进内核。就目前所知,如何在内核中实现并行缓存方法仍然是一个待解决的问题。2内核级缓存数据结构本文设计了一种多线程内核级NDN缓存模块,分为缓存查找表、替换队列和数据存储区三部分,结构如图2所示。缓存查找表和替换
21、队列两个结构共同管理数据存储区中的数据。其中,缓存查找表由用于精确匹配的哈希表和用于模糊匹配的字典树共同组成。在哈希表上,一组细粒度的逐槽锁保证在内核软中断环境中缓存查找表上并行的查找和更新操作能够正确进行,同时也尽可能减少竞争锁造成的阻塞。替换队列包括一个先入先出的循环队列和原子性的队首队尾指针,同样保证了并行访问的正确性。缓存模块的调用处于内核软中断的包处理过程中。当NDN包到达缓存节点,网卡将包拷贝至内存后调用软中断唤醒随机处理器上的软中断线程执行内核包处理函数,包处理函数解析NDN包后,若为数据包,则调用缓存模块的插入函数,将包在内存中的地址传递给缓存模块进行缓存。缓存模块根据地址将数
22、据拷贝至数据存储区,然后在逐槽锁的保护下将其插入缓存查找表,并使用原子操作将其置入替换队列。当缓存已被填满时触发替换操作,将替换队列队首的包替换出,并从查找表中删除。缓存处理完成后,软中断线程继续包转发操作。若解析为兴趣包,内核软中断线程调用缓存模块的查找函数,并传递兴趣包的名称等参数,缓存根据名称在查找表进行精确或模糊匹配,如果找到匹配的结果,则将数据存储区中对应数据写入网卡发送队列,向兴趣来源发回数据包。2.1缓存查找结构为了同时满足 NDN 缓存对长名称做快速精确匹配、对名称前缀做模糊匹配和高频更新的需求,本文提出一种将哈希表和字典树结合的混合数据结构用于缓存查找,结合两种结构的优势,抵
23、消相应不足。两种结构的优势和不足分述如下:基于哈希表的结构可以对长名称进行快速的精确匹配查找,并支持多线存储数据存储区 字典树索引节点替换队列队首指针队尾指针循环队列缓存查找表数据数据包删除数据缓存模块删除兴趣包逐槽锁哈希表312312插入(原子性数据)图2缓存模块总体结构图Fig.2Overall diagram of cache module2422023,59(16)程环境下的高频更新。但是使用哈希表实现缓存的模糊匹配需要对缓存中每个数据名的每个前缀额外建立一次索引,会造成高额的内存资源浪费和额外更新代价。基于字典树的查找结构天然支持名称模糊匹配,但是其查找时内存访问次数与名称长度相关,
24、在查找长名称时较慢,且其更新操作难以并行化实现。本文将哈希表和字典树结合构成了缓存查找表,利用了哈希表快速精确匹配的优势和字典树易于实现名称模糊匹配的特性。图3展示了缓存查找表结构图,其基本结构是一个链地址法的哈希表,处于同一哈希槽的节点组成链表相连,并且节点间按名称用孩子兄弟表示法构成组件级字典树。针对长名称的缓存精确匹配可以通过哈希表查找快速完成,仅需一次名称哈希和一次哈希表查找,如图3中的查找1所示。假如对输入名称进行哈希查找的结果不包含数据而只是一个前缀,则缓存从该前缀节点开始做字典树上的深度优先搜索,即可找到模糊匹配的数据,如图3中的查找2所示。在缓存数据时,先将数据名称插入哈希表,
25、再通过哈希表查找父节点(名称比其短一个组件的),将其连接在父节点下。2.2并行查找机制内核软中断环境中的缓存操作会被多个处理器并行地执行,这在提升缓存吞吐量的同时也带来了多线程协同问题。在多个软中断线程同时访问共享的缓存查找表过程中,可能由于操作冲突造成以下问题:(1)重复插入。例如当“/a/1”和“/a/2”两个数据包同时到达路由器,并被分别交给两个内核软中断线程同时执行缓存操作,将它们插入缓存查找表时,两个线程均发现表中不存在所需前缀“/a”,因此两个线程各自向表中插入一次“/a”前缀节点。导致表中存在两个“/a”节点,并将本属于同一子树的“/a/1”和“/a/2”连接到不同的前缀节点下。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面向 命名 数据 性能 内核 网络 缓存 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。