BGP路由查表算法的分析与改进  

Analysis and Improvement of BGP Route Lookup Algorithm

作　　者：马海龙[1] 郭云飞[1] 陈乐然[2] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002 [2]解放军信息工程大学理学院,郑州450001

出　　处：《计算机工程》2009年第2期4-5,9,共3页Computer Engineering

基　　金：国家“973”计划基金资助项目(2007CB307100)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]