基于多核处理器的并行路由查找算法研究与实现

发布时间：2017-11-28 15:32

本文关键词：基于多核处理器的并行路由查找算法研究与实现

【摘要】：多核处理器凭借处理速度快、延迟小、吞吐量大和并行处理等特点，被迅速应用于高端路由器。而在基于多核处理器平台的路由查找算法，则成为了路由器数据查找转发的瓶颈。传统基于Hash、Trie树和分段地址的查找算法多应用于串行数据处理的单核处理器中，这些算法应用于多核处理器，由于多核处理器并行处理的特点，容易形成资源竞争，造成数据瓶颈。因此，本文针对多核处理器的特点，，提出了一种基于分割多分支Trie的并行路由查找算法，并利用处理器的Cache和流表思想，对算法做了进一步研究和改进，解决了在多核处理器平台下，路由查找速度慢的问题。首先，针对多核处理器任务调度和并行处理的特点，在研究传统多分支Trie树的基础上，提出了一种基于SDRAM的并行路由查找算法，即分割多分支Trie树算法。该算法将一棵多分支Trie树根据处理器的核数分割成若干子树，每棵子树又构成一棵单独的多分支Trie树，子树中取消了前缀查找，采取组成一个大中间节点的方式。在中间节点之间采用固定步长查询，中间节点内部采用二进制Trie树来表示。由于每个核只在其对应的子树中查找，从而有效避免多个核因资源共享而产生竞争和互斥的问题，同时还保持了较低的时间复杂度和空间复杂度。其次，为进一步提升算法的查找效率，在分割多分支Trie树的基础上，引入了流表的思想。在处理器Cache中建立一张流表，把整个路由查找分为两层，首先到Cache的流表中查找，如果命中，则根据路由表的转发信息将数据包转发，如果未命中，则到SDRAM总表中按照分割多分支Trie的算法查找，查找成功后将该路由信息调入Cache中的流表，方便同一路由再次被查找。其中Cache中的流表采用哈希表结构，用链地址方法防止哈希冲突。当哈希表满时，则采用直接覆盖的方法进行路由淘汰。另外，为了防止Cache流表中因多个核对同一个路由表项操作而产生的竞争问题，设计了一种无锁流表，即将路由表项的删除过程分为两个阶段，第一个阶段为失效，第二个阶段为删除。最后，在高端路由器上对本文提出的算法进行了实验，证明了本算法的实用性。
【学位授予单位】：武汉邮电科学研究院
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP332

【参考文献】

中国期刊全文数据库前10条

1 李振强;郑东去;马严;;TSB:一种多阶段IPv6路由表查找算法[J];电子学报;2007年10期

2 陈蹊;赵跃龙;;多分枝trie树路由查找算法研究[J];电子设计工程;2010年03期

3 杨玉梅;黎仁国;;基于二分查找和Trie的IPv6路由查找算法[J];兰州理工大学学报;2012年04期

4 刘中金;李勇;杨懋;苏厉;金德鹏;曾烈光;;基于可编程硬件的虚拟路由器数据平面设计与实现[J];电子学报;2013年07期

5 郑纬民,杨博,林伟坚,李志光;SMP机群系统上优化通信的并行任务调度[J];中国科学E辑:技术科学;2001年05期

6 李冬梅;施海虎;;负载平衡调度问题的一般模型研究[J];计算机工程与应用;2007年08期

7 李冬梅;施海虎;顾毓清;;基于规则的分层负载平衡调度模型[J];计算机科学;2003年10期

8 王亚刚;杜慧敏;杨康平;;使用Hash表和树位图的两级IPv6地址查找算法[J];计算机科学;2010年09期

9 张明杰,卢锡城;基于二分法搜索hash表的快速IP路由查找算法[J];计算机工程与科学;2000年05期

10 兰舟;孙世新;;基于动态关键任务的多处理器任务分配算法[J];计算机学报;2007年03期