摘要
为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2017年第3期99-104,共6页
Computer Engineering
基金
国家自然科学基金(61262030
61572146
61363030)
广西自然科学基金(2015GXNSFAA139285
2014GXNSFAA118354)
广西可信软件重点实验室基金
广西高等学校高水平创新团队
卓越学者计划项目
关键词
路由表
路由查找
代数决策图
符号算法
最长前缀匹配
伪布尔函数
routing table
routing lookup
Algebraic Decision Diagram ( ADD )
symbolic algorithm
longest prefix matching
pseudo Boolean function