作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

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

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

  1. (桂林电子科技大学 广西可信软件重点实验室,广西 桂林 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   

  1. (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

摘要: 为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(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

中图分类号: