Investigating the Potential of the Inter-IXP Multigraph for the Provisioning of Guaranteed End-to-End Services

Abstract

Modern Internet applications, from HD video-conferencing to remote control of power-plants, pose increasing demands on network latency, bandwidth and availability. Centralized inter-domain brokers and controllers are being explored in the literature (and in early stages in the industry), as an approach to support the requirements of such applications across domains. In this work, we take a first look into the properties of the global Internet substrate that could support inter-domain routing with QoS guarantees. We propose using IXPs as strategic locations for stitching guaranteed path segments and analyze the properties of the resulting substrate. This is represented as a dense multigraph, where each vertex is an IXP and each edge is a path segment crossing an ISP which connects a pair of IXPs. By analyzing ISP membership data for 229 IXPs, we build a first map of the IXP multigraph of the Internet and highlight its high path diversity and global client reach. About 40% of the total IPv4 address space can be served directly with just a handful of IXPs, while path diversity on the IXP multigraph increases by up to 29 times, as opposed to current Internet valley-free routing. Second, we introduce algorithms that inter-domain QoS mediators can use to embed paths on such multigraphs, subject to bandwidth and latency constraints. Our algorithmic variants work in an online, offline, and hybrid manner and aim at maximizing the number of paths that can be embedded. Through thorough simulations based on the mapped IXP multigraph, we show that our algorithms scale to the sizes of the measured graphs and can serve diverse path request mixes.