On the Stability of Rational Inbound-Dependent Interdomain Route Selection

In this paper, we analyze the stability of interdomain routing under two extensions. First, we investigate the general model that the preference of an AS depends on not only its egress routes to the destinations but also its inbound traffic pattern. Second, instead of studying a specific route selection algorithm, we study a general class of route selection algorithms which we call rational route selection algorithms. We present a sufficient condition to guarantee routing convergence in a heterogeneous network where each AS runs any rational route selection algorithm. We also show that there exist networks which will have persistent route oscillations even when the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.