In interdomain routing, competing network operators encode policies about possible routes in routing protocol configuration. The operation of the protocol should lead to satisfactory routes for all operators, but this process may not terminate or take a long time, exploring exponentially many alternative paths before stabilizing. In this paper, we study convergence for the partial policy specification model where preferences are set for only some paths and the ranking for the remaining paths is indifferent to the network operator. We consider policy restrictions that ensure a network to stabilize quickly. Specifically, we show that even when each operator only specifies preferences for two paths and each path has at most three hops, a network may still encounter exponentially many steps before convergence. However, restricting the policy any further ensures poly-time convergence. From another direction, it is well known that preferences based only on the ‘next-hop’ node always converge within linear-time. We show that even relaxing the preference to be based on the ‘next-two-hop’ leads to exponential-time convergence. Finally, we further study policy completion that leads to a stable state that minimizes the hop-length of the longest path, and establish a hardness result along with an approximation algorithm.
['Alexander J. T. Gurney', 'Sanjeev Khanna', 'Yang Li']
Rapid convergence versus policy expressiveness in interdomain routing