Abstract: There are vastly routes in Border Gateway Protocol(BGP) router located in the Default-Free Zone. Many developers adopt Path Compressed Tree(PCT) to store the BGP routes. It is found that the performance of PCT algorithm is not so good. The lookup time fluctuates and the store memory is wasted. The performances of PCT are mostly influenced by the character of data source. In order to solve those problems, AVL algorithm is introduced. Comparison results of these two algorithms manifest that the AVL algorithm can improve the lookup performance.

Key words: Border Gateway Protocol(BGP), Path Compressed Tree(PCT), AVL algorithm

摘要： Default-Free Zone内的路由器拥有巨大的路由表项，为了方便实现，大多数开发者在实现过程中均采用路径压缩树的数据结构对边界网关协议路由进行存储。计算机仿真分析发现，采用路径压缩树算法会引起路由搜索时间抖动严重、存储空间利用率低，路径压缩树性能受BGP路由前缀的分布特性影响。引入AVL算法解决存在的问题，可以较好地提高路由查表的性能。

关键词: 边界网关协议, 路径压缩树, AVL算法

CLC Number: 

• TP311