域间路由策略冲突的收敛性分析

Convergence analysis of inter-domain routing policies conflict

边界网关协议(BGP)是一种基于策略的、事件驱动的路径向量协议。以前一般采用静态模型研究BGP收敛问题,不符合BGP事件驱动的特点。针对这个问题,该文基于BGP的简化版本的简单路径向量协议(SPVP),提出稳定路径问题(SPP)的随机高级Petri网模型。模型中使用延时变迁的参数描述BGP消息传播和处理延时的随机性,更加准确地揭示了策略冲突导致路由不收敛的实质。基于该模型提出了冲突定位算法,并证明其正确性。该算法还可以作为SPP的求解算法。

The border gateway protocol （BGP） is a policy-based, event-driven path vector routing protocol. In the past, the routing mechanism has been described statically, which does not conform to the event-driven characteristics of the BGP. Basing on simple path-vector protocol, a stochastic high-level Petri net model of stable path problem is proposed. In this model, the BGP message transmission and processing delays are described by stochastic distribution parameters for the time transitions. The model was used to develop a conflict locating algorithm to find nodes with conflicting policies. The algorithm can also be used to solve the stable path problem.