On Exploiting Link State Techniques for Internet Mapping

Internet mapping, or network metrics measurement, is receiving significant attention due to applications in the strategic placement of data and server mirrors to improve the user perceived performance of the Internet. The challenge is in creating a scalable, Internet-wide service to effectively route users to a server based on network proximity, server capacity and load, path congestion, and bandwidth. Recent proposals call for distributing instrumentation to periodically probe end-to-end paths. However, active end-to-end probing presents the need to sacrifice accuracy for efficiency and scalability. In this paper, we examine the efficacy of exploiting Link State techniques to alleviate this contention. Link State routing protocols are well known at the network layer for efficiency, rapid convergence, and self-stabilization, but also for limitations in scaling to very large networks. We propose an adaptation of Link State routing techniques for efficient, wide-area server selection. We present solutions, in this application layer routing context, to scalability and policy-based routing issues endemic to hop-by-hop Internet measurement. We examine both active and passive path discovery to supplement Link State probing. Finally, we evaluate our techniques using generated Internet topologies as well as experimental data collected from Internet probing.