基于代数决策图的路由查找算法

doi:10.3969/j.issn.1000-3428.2017.03.018

计算机工程

基于代数决策图的路由查找算法

徐周波,胡魁,常亮,古天龙

(桂林电子科技大学广西可信软件重点实验室,广西桂林 541004)

收稿日期:2016-03-14 出版日期:2017-03-15 发布日期:2017-03-15
作者简介:徐周波(1976—),女,副教授、博士,主研方向为符号计算、智能规划;胡魁,硕士研究生;常亮,教授、博士;古天龙,教授、博士生导师。
基金资助:
国家自然科学基金(61262030,61572146,61363030);广西自然科学基金(2015GXNSFAA139285,2014GXNSFAA118354);广西可信软件重点实验室基金;广西高等学校高水平创新团队及卓越学者计划项目。

Routing Lookup Algorithm Based on Algebraic Decision Diagram

XU Zhoubo,HU Kui,CHANG Liang,GU Tianlong

(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China)

Received:2016-03-14 Online:2017-03-15 Published:2017-03-15

摘要/Abstract

摘要： 为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。

关键词: 路由表, 路由查找, 代数决策图, 符号算法, 最长前缀匹配, 伪布尔函数

Abstract: In order to solve the problem of high storage redundancy and low search efficiency caused by the increasing number of routing table entries in the proess of routing lookup,an improved routing lookup algorithm based on Algebraic Decision Diagram(ADD) is proposed. According to the characteristic of symbolic algorithm,routing table entries are expressed as a pseudo Boolean function. Considering the features of routing table structure and the advantages of symbolic algorithm,a prefix-based routing table is constructed by ADD structure,and the algorithm of routing table update,deleting and look-up is also given. With the open source routing table provided by International Project Management Association(IPMA),the experimental results show that the algorithm can effectively reduce the number of memory access in routing table operation and save the routing table storage space.

Key words: routing table, routing lookup, Algebraic Decision Diagram(ADD), symbolic algorithm, longest prefix matching, pseudo Boolean function

中图分类号:

TP393

徐周波,胡魁,常亮,古天龙. 基于代数决策图的路由查找算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.03.018.

XU Zhoubo,HU Kui,CHANG Liang,GU Tianlong. Routing Lookup Algorithm Based on Algebraic Decision Diagram[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.03.018.

https://www.ecice06.com/CN/Y2017/V43/I3/99

参考文献

参考文献［1］Sun Y, Egi N,Shi G,et al.Content-based Route Lookup Using CAMs［C］//Proceedings of 2012 IEEE Global Communications Conference.Washington D.C.,USA:IEEE Press,2012:2677-2682. ［2］Zheng Kai,Hu Chengchen,Lu Hongbin.A TCAM-based Distributed Parallel IP Lookup Scheme and Performance Analysis［J］.IEEE/ACM Transactions on Networking,2006,14(4):863-875. ［3］Kuo Fangchen,Chang Yeim-kuan,Su Cheng-chien.A Memory-efficient TCAM Coprocessor for IPv4/IPv6 Routing Table Update［J］.IEEE Transactions on Computers,2014,63(9):2110-2121. ［4］Waldvogel M,Varghese G,Turner J,et al.Scalable High Speed IP Routing Lookups［J］.ACM SIGCOMM Computer Communication Review,1997,27(4):25-36. ［5］Gupta P,Prabhakar B,Boyd S.Near-optimal Routing Lookups with Bounded Worst Case Performance［C］//Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Washington D.C.,USA:IEEE Press,2000:1184-1192. ［6］范富明,李念军,雷升平,等.基于哈希表与多比特树的路由查找算法［J］.计算机工程,2015,41(9):63-67. ［7］Waldvogel M,Varghese G,Turner J et al. Scalable High Speed IP Routing Lookups［J］.ACM SIGCOMM Computer Communication Review,1997,27(4):25-36. ［8］Srinivasan V,Varghese G.Fast Address Lookups Using Controlled Prefix Expansion［J］.ACM Transactions on Computer Systems,1999,17(1):1-40. ［9］Yilmaz P A,Belenkiv A,Uzun N,et al.A Triebased Algorithm for IP Lookup［C］//Proceedings of Global Telecommunications Conference.Washington D.C.,USA:IEEE Press,2000:593-598. ［10］Kumar S,Becchi M,Crowley P,et al.CAMP:Fast and Efficient IP Lookup Architecture［C］//Proceedings of 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York,USA:ACM Press,2006:51-60. ［11］谭明锋,高蕾,龚正虎.IP路由查找算法研究概述［J］.计算机工程与科学,2006,28(6):77-80. ［12］Sangireddy R,Somani A K.High-speed IP Routing with Binary Decision Diagrams Based Hardware Address Lookup Engine［J］.IEEE Journal on Selected Areas in Communications,2003,21(4):513-521. ［13］朱云洁,朱凌众.LPM路由查找算法及其应用［J］.硅谷,2010(10):127. ［14］古天龙,徐周波.有序二叉树决策图及应用［M］.北京:科学出版社,2009. ［15］徐恪,徐明伟,吴建平,等.路由查找算法研究综述［J］.软件学报,2002,13(1):42-50. ［16］张琦,金胤丞,李苗,等.Trie树路由查找算法在网络处理器中的实现［J］.计算机工程,2014,40(1):98-102. 编辑陆燕菲

[1]	李建辉,张永棠. 一种基于偏移编码特里树的高效IP寻址算法[J]. 计算机工程, 2017, 43(4): 84-89.
[2]	范富明,李念军,雷升平,吉萌. 基于哈希表与多比特树的路由查找算法[J]. 计算机工程, 2015, 41(9): 63-67.
[3]	杨壮林,郭宇波,赵梦恋. 基于运算部件的可重构密码算法处理架构[J]. 计算机工程, 2015, 41(11): 89-93.
[4]	张琦，金胤丞，李苗，章建雄. Trie树路由查找算法在网络处理器中的实现[J]. 计算机工程, 2014, 40(1): 98-102.
[5]	林沛，杨裔，陈宜漂，邓毓博. 基于裂痕故障块的自适应容错路由表算法[J]. 计算机工程, 2013, 39(12): 102-106.
[6]	李惠民，沈海斌. 不规则Mesh NoC上基于路由表的路由[J]. 计算机工程, 2013, 39(10): 279-282,286.
[7]	张依依, 祝跃飞, 高翔. 针对BGP路由器的DDoS攻击及防范措施[J]. 计算机工程, 2012, 38(19): 103-106.
[8]	王瑞青, 杜慧敏, 王亚刚. 基于Hash和CAM的IPv6路由查找算法[J]. 计算机工程, 2012, 38(08): 50-53.
[9]	武凌. 网络处理器路由表同步机制的研究与实现[J]. 计算机工程, 2011, 37(9): 251-253,256.
[10]	马慧, 陈艳格. 基于资源路由表的P2P改进模型[J]. 计算机工程, 2011, 37(4): 104-106.
[11]	刘敏霞, 余杰, 李强, 陈志新. P2PSIP系统的路由表安全研究[J]. 计算机工程, 2011, 37(20): 97-99.
[12]	骆珍荣, 刘玉华, 许凯华, 张翼. WSN中基于分簇的实时传输算法[J]. 计算机工程, 2011, 37(16): 101-103.
[13]	马慧, 胡子义. 基于IPv6的三层混合P2P覆盖网络模型[J]. 计算机工程, 2011, 37(10): 96-98.
[14]	王必晴, 钟志水, 孟伟东, 袁晓勇, 王福成. S-Chord：一种层次式Chord路由模型[J]. 计算机工程, 2011, 37(01): 96-97,100.
[15]	余晓磊, 江红, 杨璀琼. WSN中改进的IPv6路由查找算法[J]. 计算机工程, 2010, 36(21): 115-117.

选择文件类型/文献管理软件名称

选择包含的内容

基于代数决策图的路由查找算法

Routing Lookup Algorithm Based on Algebraic Decision Diagram

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于代数决策图的路由查找算法

Routing Lookup Algorithm Based on Algebraic Decision Diagram

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价