Home Problem Statement: TE-based route selection can lead to route oscilation!
A fundamental feature of Interdomain route selection for interdomain traffic engineering is that routes for a set of destinations be chosen jointlyto satisfy traffic engineering constraints and meet traffic engineering objectives.
We analyze the general route selection model in which ASes coordinate the route selection of multiple destinations.
We find that there exist networks where the interaction of the route selection of multiple destinations can cause routing instability, even though the networks are guaranteed to converge to a unique route selection when each destination is considered alone.
Guidelines for interdomain TE
We introduce a game theoretical model for route selection for egress interdomain traffic engineering and derive a sufficient condition to guarantee routing convergence. Specifically, taking into account the business relationships among ASes, we analyze a set of practical guidelines and show that if ASes follow these guidelines, route selection is guaranteed to converge to a unique solution, without global coordination. Here is the set of practical guidelines:
- there is no provider-customer loop in the network;
- all ASes have fixed typical export policies;
- the routing decisions for customer-reachable and peerprovider-reachable destinations follow the standard joint-route preference policy.
Our evaluations using current Internet AS topology show that if these guidelines are not followed, the network could be unstable even when just a small number of ASes coordinate their route selection of just two destinations.
Chaos: be careful with ingress-dependent TE!
Despite the success of these guidelines, we also investigate a more general model where the preference of an AS depends on both egress routes and ingress traffic patterns; we show that there are networks which will be unstable when the ASes strictly follow AS business guidelines, and adopt any adaptive route selection algorithms.
Paper Toys
- Stable Route Selection for Interdomain Traffic Engineering, Yang Richard Yang, Haiyong Xie, Hao Wang, Li Erran Li, Yanbin Liu, Avi Silberschatz, and Arvind Krishnamurthy. To appear in IEEE Network Magazine --- Special Issue on Interdomain Routing, November/December 2005. (PDF)
- On the Stability of Rational, Heterogeneous Interdomain Route Selection, Hao Wang, Haiyong Xie, Yang Richard Yang, Li Erran Li, Yanbin Liu, and Avi Silberschatz. In Proceedings of 13th International Conference on Network Protocols (ICNP '05), Boston, October 2005. (PDF)
- Stable Egress Route Selection for Interdomain Traffic Engineering: Model and Analysis, Hao Wang, Haiyong Xie, Yang Richard Yang, Li Erran Li, Yanbin Liu, and Avi Silberschatz. In Proceedings of 13th International Conference on Network Protocols (ICNP '05), Boston, October 2005. (PDF)
- On Stable Route Selection for Interdomain Traffic Engineering: Models, Analysis, and Guidelines, Hao Wang, Haiyong Xie, Yang Richard Yang, Li Erran Li, Yanbin Liu, and Avi Silberschatz, Yale Computer Science Technical Report YALEU/DCS/TR-1316, Feb. 2005. (PDF)
- Stable Egress Route Selection for Interdomain Traffic Engineering: Model, Analysis and Policies, Hao Wang, Haiyong Xie, Yang Richard Yang, Li Erran Li, Yanbin Liu, and Avi Silberschatz, In poster session, ACM SIGCOMM '05, Philadelphia, PA, August 2005. (PDF)
- On the Stability of Interdomain Inbound Traffic Engineering, Hao Wang, Haiyong Xie, Yang Richard Yang, In poster session, ACM SIGCOMM '05, Philadelphia, PA, August 2005. (PDF)