An analysis of convergence delay in path vector routing protocols

Path vector routing protocols such as the Border Gateway Protocol (BGP) are known to suffer from slow convergence following a change in the network topology or policy. Although a number of convergence enhancements have been proposed recently, there has been no general analytical framework to assess and compare the various proposed algorithms. In this paper we present such a general framework to analyze the upper bounds of path vector protocols' convergence delay under shortest path routing policy and single link failure. Our framework takes into account important factors such as network connectivity, failure location, and routing message processing delay. It can be used to analyze both standard BGP and all the proposed convergence improvement algorithms in the case of shortest path routing policy and single link failure. It enables us to obtain previously unavailable analytical results, including the delay bounds of path fail-over for standard BGP and its convergence enhancements. Our analysis shows that BGP fail-over delay bounds are mainly determined by two factors: (1) the distance between the failure location and the destination, and (2) the length of the longest alternate path to reach the destination after the failure. These two factors are captured formally by our analysis and can explain why existing convergence enhancements often provide only limited improvements in fail-over events. Moreover, explicitly modeling message processing delay reveals insights into the impacts of connectivity richness (i.e., node degree and total number of links in the network), and also the effectiveness of different enhancements. These new results enable one to better understand and compare the behavior of various path vector protocols under different topology structures, network sizes, and message delays.