Routing-policy aware peering for large content providers

• We investigate the impact of routing policies and peering policies on the selection of peering connections for content providers.
• We formulate the policy-aware peering problem, and prove that the problem is NP-complete.
• We provide a heuristic algorithm to solve policy-aware peering problem.
• We examine the lower bound of peering connections to cover end users in today’s Internet.
• We investigate 5 large content providers, and find that adding as little as 3–5 new peering connections can enhance their connection to end users significantly.

Large content providers, such as Google, Yahoo, and Microsoft, aim to directly connect with consumer networks and place the content closer to end users. Exchanging traffic directly between end users and content providers can reduce the cost of transit services. However, direct connection to all end users is simply not feasible. Content providers by-and-large still rely on transit services to reach the majority of end users. We argue that routing policies are an important factor in considering the selection of ISPs for content providers. Therefore, determining which ISP to peer or use as a transit becomes a key question for content providers. In this paper, we formulate the policy-aware peering problem, in which we determine not only which ISP to connect with, but also the kind of peering agreement to establish. We prove that such a policy-aware peering problem is NP-complete, and propose a heuristic algorithm to solve the problem. Further, we perform a large-scale measurement study of the peering characteristics of five large content providers, and evaluate the existing peering connections deployed by the content providers. Our measurement results show that changing the existing peering agreements or adding as little as 3–5 new peering connections can enhance the connection between content providers and end users significantly.