Exit Policy Violations in Multi-Hop Overlay Routes: Analysis and Mitigation

The traffic exchanged between two overlay nodes in different autonomous systems (AS) is always subjected to a series of inter-domain policies. However, overlay routing often manages to get around these policy restrictions by relaying traffic through multiple legitimate segments, in order to achieve its selfish goals (e.g., better latency paths between end- systems). We focus on the violation of a generalized exit policy, which specifies the exact next hop AS and the egress inter- domain link for a destination address prefix. We characterize the different types of these exit policy violations and investigate their extent in a Planetlab testbed. It is conceivable that the native ASes will eventually realize the negative impact of the exit violations and adopt stringent strategies to enforce the exit policies, thereby causing deterioration in overlay performance. In this context, based on our findings from a previous study[l], we develop a pricing-based strategy that an overlay service provider can use to obtain permits from a near-optimal set of native ASes, in an effort to regain its routing advantage within a fixed budget. Further, we illustrate the use of this approach on our case study overlay network.