3.3 Violations of the Triangle Inequality

Figure 3: In all three data sets, over half of all node pairs fail the Tang/Crovella triangle inequality test, because there exists a third node between the nodes in the pair that produces a shorter path than the direct path between the two nodes. A large fraction of these violating pairs have paths that are significantly faster.

Network coordinate embeddings that use Euclidean distances make the assumption that the triangle inequality is not violated to a great extent by a large fraction of pairs of nodes. The triangle inequality states that for any triangle the length of a given side must be less than the sum of the other two sides but greater than the difference between the two sides, i.e., the sides must be able to form a triangle. When the latencies between node triples cannot form a triangle, they are said to violate the triangle inequality. Nodes with large and frequent violations tend to be the ones with the largest individual prediction error and their existence decreases overall accuracy (see [18] and Section 7.3).

We use a method from Tang and Crovella to examine the severity of triangle inequality violations [31]. This method normalizes the severity of each violation, permitting an all-pairs comparison. For each node pair, we find the shortest path between the two that passes through a third node. Thus, for all pairs of nodes i and j, we find the best alternative path through a node $k$ and normalize by the latency between i and j:

$$rpl = min_{k} \left ( \frac{d(i,k)+d(k,j)}{d(i,j)} \right )$$

Figure 3 illustrates the cumulative distribution of this quantity, the relative path length. Note that any fraction below 1 is a violation: there exists a path through an alternative node that is faster than the direct path. 83 percent of the Azureus pairs, 85 percent of MIT King, and 68 percent of the PlanetLab subset violate the triangle inequality. In contrast to earlier work that examined several small-scale data sets [31], we find the fraction of pairs with the largest violations to be quite large: Tang and Crovella found only 10 percent of nodes had an alternative path that is greater than or equal to 20 percent faster; here 37 percent of Azureus pairs and 22 percent of MIT King pairs exhibit this large level of violation.

We examined the cause of the large fraction of pairs with very low rpl (less than $0.1$) in Azureus. We found that only a few nodes were members of many of these low rpl pairs. What distinguished these nodes -- and what was the cause of their frequent participation in triangle inequality violations -- was that their delay to non-PlanetLab nodes was atypically large, on the order of seconds, while their delay to other PlanetLab nodes remained typical (less than a second). In effect, this extended one side of the triangles these nodes participated in: d(i,j) became large while d(i,k) and d(k,j) did not. Because PlanetLab nodes that exhibited this behavior were co-located, we conjecture that the Azureus traffic to non-PlanetLab sites was being artificially limited at site gateways, while traffic to PlanetLab nodes avoided this traffic shaping. Rather than being a construct of the PlanetLab environment, this effect, leading to bi- or multi-modal latency distributions, will be the norm for at least some participants in Internet-scale applications that use well-known ports and consume a large amount of bandwidth, such as Azureus, because some sites will limit traffic and some will not. Like the round trip time spread, Azureus' violations foreshadow a higher embedding error.