关键词: 收敛时间, BGP协议, 自治系统, 路由策略, 有向竞争图, 稳定路径问题

Abstract: BGP convergence time is studied on the basis of dispute digraph, which reveals the relationships between routing policies of different autonomous systems. Dispute arc and transmission arc of the dispute digraph indicate respectively the policy conflict and policy consistency. The results show that the routing convergence time correlates with the length of the longest path in dispute digraph for a network. The BGP convergence time based on dispute digraph is given. The convergence time is greater than or equals to the minimum. Time required for the local longest paths, which only consists of the transmission arcs followed with or without a dispute arc in the dispute digraph corresponding to the network, whereas it is less than or equals to the maximum time required for all the paths of the dispute digraph. The convergence time given is proved sound and exemplified through an SSFNET simulation.