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

Routing Lookup Algorithm Based on Algebraic Decision Diagram

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