In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\log\log n)$ are navigable. We show that for doubling dimension $\gg\log\log n$, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability.

Modeling communications in wireless networks is a challenging task, since it requires a simple mathematical object on which efficient algorithms can be designed but which must also reflect the complex physical constraints inherent in wireless networks, such as interferences, the lack of global knowledge, and purely local computations. As a tractable mathematical object, the unit disk graph (UDG) is a popular model that has enabled the development of efficient algorithms for crucial networking problems. In a rho-UDG, two nodes are connected if and only if their distance is at most rho, for some rho > 0. However, such a connectivity requirement is basically not compatible with the reality of wireless networks due to the environment of the nodes as well as the constraints of radio transmission. For this purpose, the signal interference plus noise ratio model (SINR) is the more commonly used model. The SINR model focuses on radio interferences created over the network depending on the distance to transmitters. Nevertheless, due to its complexity, this latter model has been the subject of very few theoretical investigations and lacks of good algorithmic features. In this paper, we demonstrate how careful scheduling of the nodes enables the two models to be combined to give the benefits of both the algorithmic features of the UDG and the physical validity of the SINR. Precisely, we show that it is possible to emulate a 1/radic(n ln n)-UDG that satisfies the constraints of the SINR over any set of n wireless nodes distributed uniformly in a unit square, with only a O(ln3n) time and power stretch factor. The main strength of our contribution lies in the fact that the scheduling is set in a fully distributed way and considers non-uniform power ranges, and it can therefore fit the sensor network setting. Moreover, our scheduling is optimal up to a polylogarithmic factor in terms of throughput capacity according to the lower bound of Gupta and Kumar.

A large amount of algorithms has recently been designed for the Internet under the assumption that the distance defined by the round-trip delay (RTT) is a metric. Moreover, many of these algorithms (e.g., overlay network construction, routing scheme design, sparse spanner construction) rely on the assumption that the metric has bounded ball growth or bounded doubling dimension. This paper analyzes the validity of these assumptions and proposes a tractable model matching experimental observations. On the one hand, based on Skitter data collected by CAIDA and King matrices of Meridian and P2PSim projects, we verify that the ball growth of the Internet, as well as its doubling dimension, can actually be quite large. Nevertheless, we observed that the doubling dimension is much smaller when restricting the measures to balls of large enough radius. Moreover, by computing the number of balls of radius r required to cover balls of radius R > r, we observed that this number grows with R much slower than what is predicted by a large doubling dimension. On the other hand, based on data collected on the PlanetLab platform by the All-Sites-Pings project, we confirm that the triangle inequality does not hold for a significant fraction of the nodes. Nevertheless, we demonstrate that RTT measures satisfy a weak version of the triangle inequality: there exists a small constant p such that for any triple u, v, w, we have RTT(u,v) les rho-max{RTT(u,w),RTT(w,v)}. (Smaller bounds on p can even be obtained when the triple u, v, w is skewed). We call inframetric a distance function satisfying this latter inequality. Inframetrics subsume standard metrics and ultrametrics. Based on inframetrics and on our observations concerning the doubling dimension, we propose an analytical model for Internet RTT latencies. This model is tuned by a small set of parameters concerning the violation of the triangle inequality and the geometrical dimension of the network. We demonstrate the tractability of our model by designing a simple and efficient compact routing scheme with low stretch. Precisely, the scheme has constant multiplicative stretch and logarithmic additive stretch.

We present a dynamic process for network evolution, aiming at explaining the emergence of the small world phenomenon. We prove that a local forgetting process combined with mobility produces shortcuts allowing navigability.

Augmented graphs were introduced for the purpose of analyzing the "six degrees of separation between individuals" observed experimentally by the sociologist Standley Milgram in the 60's. Formally, an augmented graph is a pair (G,φ) where G is a graph, and φ is a collection of probability distributions {φu, u ∈ V(G)}. Every node u ∈ V(G) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr{u → v} = φu(v). In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. Roughly, augmented graphs aim at modeling the structure of social networks, while greedy routing aims at modeling the searching procedure applied in Milgram's experiment. Our objective is to design efficient universal augmentation schemes, i.e., augmentation schemes that give to any graph G a collection of probability distributions φ such that greedy routing in (G,φ) is fast. It is known that the uniform scheme φunif is a universal scheme ensuring that, for any n-node graph G, greedy routing in (G,φunif) performs in O(√n) expected number of steps. Our main result is the design of a universal augmentation scheme φ such that greedy routing in (G,φ) performs in Õ(n1/3) expected number of steps for any n-node graph G. We also show that under some more restricted model, the √n-barrier cannot be overcome.

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem P is a way, for every possible input I of P, to provide an "advice" (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem P can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (log n,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t ≥ Ω (√n). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log(n) to constant.

We investigate the problem of optimizing the routing performance of a virtual network by adding extra random links. Our asynchronous and distributed algorithm ensures, by adding a single extra link per node, that the resulting network is a navigable small world, i.e., in which greedy routing, using the distance in the original network, computes paths of polylogarithmic length between any pair of nodes with probability 1-O(1/n). Previously known small world augmentation processes require the global knowledge of the network and centralized computations, which is unrealistic for large decentralized networks. Our algorithm, based on a careful multi-layer sampling of the nodes and the construction of a light overlay network, bypasses these limitations. For bounded growth graphs, i.e., graphs where, for any node u and any radius r the number of nodes within distance 2r from u is at most a constant times the number of nodes within distance r, our augmentation process proceeds with high probability in O(log n log D) communication rounds, with O(log n log D) messages of size O(log n) bits sent per node and requiring only O(log n log D) bit space in each node, where n is the number of nodes, and D the diameter. In particular, with the only knowledge of original distances, greedy routing computes, between any pair of nodes in the augmented network, a path of length at most O(log2 n log2 D) with probability 1 - O(1/n), and of expected length O(log n log2 D). Hence, we provide a distributed scheme to augment any bounded growth graph into a small world with high probability in polylogarithmic time while requiring polylogarithmic memory. We consider that the existence of such a lightweight process might be a first step towards the definition of a more general construction process that would validate Kleinberg's model as a plausible explanation for the small world phenomenon in large real interaction networks.