Policy-rich interdomain routing with local coordination

Abstract The Internet has evolved from a hierarchical and multi-tiered interconnection network to a meshed network, where autonomous systems (ASes) are interconnected with a dense topology and more and more potential paths can be used to reach a destination. However, routing policies are the key to enable these potential paths and to allow the selection of these paths. While the Gao–Rexford guidelines provide routing policies that derive a safe routing system, those potential paths are not enabled by the Gao–Rexford guidelines. A survey on deployed routing policies has shown that a significant portion of networks or ASes do not follow the Gao–Rexford guidelines completely. In this paper, we propose to broaden routing policies that enable the availability of diverse paths and provide flexibility in selecting these paths. We systematically bring out more and more flexible routing policies to implement various routing requirements. More specifically, we propose FlexibleRC, PeerBoost and hierarchical sibling routing policies and derive sufficient conditions for guaranteeing the routing system derived by these routing policies to be safe. The sufficient conditions can be verified through coordination among neighboring ASes. Thus, local coordination guarantees the routing system to be safe.