|
|
 |
| |
|
|
|
Efficient Inference of AS-Level Paths in the Internet |
|
|
|
PP: 1583-1593 |
|
|
|
Author(s) |
|
|
|
Qixin Gao,
Feng Wang,
Lixin Gao,
|
|
|
|
Abstract |
|
|
| Routing protocols maintain connectivity of Internet routers and hosts and determine the path that a packet traverses. Inferring
Internet paths is critical for evaluating the performance of Internet applications and services, such as cloud services and content delivery.
Unlike intra-domain routing protocols, which typically use the shortest paths, inte-domain routing protocol apply local policies for
selecting routes/paths and propagating routing information. These routing policies are typically constrained by contractual commercial
agreements between ASes. It is well-known that routing policies can impact the AS path that an AS may select for delivering a
packet. Thus, the ability to infer the AS-level paths is critical to evaluate the impact of routing policies on the performance of Internet
applications and services. In addition, inferring AS-level paths is also important for content providers, such as Google and Amazon,
to determine routing policies to ensure small latency in delivering content. However, inferring AS-level paths is challenging. Internet
path selection largely depends on routing policies, which in turn are determined independently by network administrators and are
considered as confidential information. In this paper, we present three common routing policies in the Internet and formulate the
problem of inferring routing policy conforming AS-level paths. We present efficient algorithms for inferring the Internet AS-level
paths. The algorithms are proved to be optimal in terms of the ability of derive the policy-conforming AS-level paths. We further
quantify the efficiency of these algorithms. |
|
|
|
|
|
|
|
