Stability metrics and criteria for path-vector routing

Since so far, most studies on path-vector routing stability have been conducted by means of ad-hoc analysis of Border Gateway Protocol (BGP) data traces. None of them consider the specification of an analytic method including the use of stability metrics for the systematic analysis of BGP traces and associated meta-processing for determining the local state of the routing system. In this paper, we define a set of stability metrics that characterize the local stability properties of path-vector routing such as BGP. By means of these metrics we derive a stability decision criterion that can be applied during the BGP route selection process. Results obtained using real BGP datasets show that 90% of the routes are not affected by a path length increase when selected based on this criterion. Moreover, among the remaining 10% a significant fraction of the routes is covered by a path length increase of one-hop. These results corroborate the assumption that enforcing stability would not come at the detriment of increasing the stretch of the routing paths.