What is New about the Internet Delay Space?

1. Introduction

Delay is usually considered as an important metric of the network performance, which provides a basic metric for the network performance evaluation and optimization. In recent years, many delay-based application optimizing schemes have been proposed to improve the user experience. The typical methods include constructing a high performance overlay network and selecting preferred severs to transfer data (Poese, Frank.&Ager, 2010). For example, Xbox, a popular Microsoft game player, uses the network coordinate system Htrae to assist the player to choose severs with least delay (Agarwal&Lorch, 2009). The famous BitTorrent client Azureus implements the network system Vivaldi to accelerate the downloading speed. Thus, the modeling of the Internet delay space has become an important research issue.

From the mathematic view, the Internet delay space modeling aims at finding a homeomorphic space to the delay space, and mapping the Internet node as a virtual node in an m-dimensional space and assigning each node a coordinate to estimate the pairwise end-to-end delay. This embedding idea can efficiently reduce the measurement overhead (Poese, Frank.&Ager, 2010). In most cases, the NCS designers treat the delay space as a metric space and select the embedding space based on their own observations or hypothesis. Based on the hypothesis that there exists a linear relationship between geodistance and delay, the Euclidean based space was put forward (Mario, Fabián, Balachander, Walter, Georgios & Erman, 2014). While based on the non-linear model, the hyperbolic model (Shavitt & Tankel. 2008) and the tree metric space model (Venugopalan, Malkhi&Kuhn, 2009) were proposed. However, these models cannot embed all of the datasets accurately.

• Definition 1 Metric Space: A metric space M is defined by the pair (X, d), where X represents the set of valid objects and d is a metric. A metric is a function d: X×X →R, such that for x_i, x_j, x_k ∈X, d satisfies the following properties:

• (positiveness) d(x_i, x_j)≥0,

• (symmetry) d(x_i, x_j)= d(x_i, x_j),

• (triangle inequality) d(x_i, x_j)≤d(x_i, x_k)+ d(x_k, x_j).

The researches on the characters of the Internet delay space can be grouped into three classes: the relationship between geodistance and delay (Khan, Kwon, Kim& Choi, 2013), Triangle Inequality Violation (TIV) (Zheng, Lua & Pias, 2005), (Kaafar, Gueye & Cantin, 2008) and its dimensionality (Abrahao & Kleinberg, 2008). However, there are three issues to be resolved: (1) all of the observations are drawn from the measurement data which can only represent part of the Internet but not whole; (2) the observations are different and even contrary to one another, such as Lee, et al., found out there are more TIVs when delay is small, while Zhu et al. hold the opposite conclusion; (3) the topology and routing of the Internet is evolving all the time, and thus the former observations may not be right for the present networks. Thus, a comprehensive measurement and analysis of the Internet delay space is needed to reveal the essence and rules of the Internet delay space.