基于树结构的分布式BGP路由计算迭代算法

随着互联网规模的迅速增长,下一代核心路由器的研究重点正在向可扩展体系结构的方向发展.分布式路由协议计算是可扩展路由器需要解决的关键问题之一.作为已经在骨干网上广泛部署的重要路由协议,BGP协议的分布式模型及其相关算法的研究是可扩展路由器体系结构中的重要研究课题.本文基于BGP路由计算模型,对“路径选优”这一BGP基本操作的特性进行了深入分析,提出了一种按照树状结构来组织路由计算过程的模型,基于此模型可以分布式计算BGP路由.针对两类典型的可扩展路由器体系结构,本文分别提出了相应的迭代树算法,对算法给出了性能改进的理论分析.通过模拟实验,验证了本文所述模型的实际性能.

Design and Implementation of the Distributed BGP Routing Processing in Extensible Router Systems

With the rapid growth of Internet, the research of the next generation router focuses on the extensible architecture router. As an important routing protocol, which has been deployed widely in the backbone, BGP is becoming critical to promote the models and algorithms under a distributed manner. This is one of the hot topics of the router's extensible architecture. This paper studies the path selection behavior, which is the fundamental operation in BGP. According to the analysis, a tree-based structure is proposed to model the computational process. Each node iterates the route selection in this model. Two algorithms are given in this paper for two classical extensible router architectures respectively. Then the performance promotions for the algorithms are evaluated theoretically. Finally, experiments are made to verify the model and the performance.