Name
Abstract | ||
|---|---|---|
We define a family of Distributed Hash Table systems whose aim is
to combine the routing efficiency of randomized networks e.g. optimal
average path length O(log^2 n \over delta log delta) with delta degree
with the programmability and startup efficiency of a uniform overlay
that is, a deterministic system in which the overlay network is transitive
and greedy routing is optimal. It is known that \omega(log n) is
a lower bound on the average path length for uniform overlays with
=(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151�163,
2004).
Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently
introduced variation of greedy routing that allows us to achieve
optimal average path length in randomized networks. The advantage
of our proposal is that of allowing the NoN technique to be implemented
without adding any overhead to the corresponding deterministic network.
We propose a family of networks parameterized with a positive integer
c which measures the amount of randomness that is used. By varying
the value c, the system goes from the deterministic case (c=1) to
an �almost uniform� system. Increasing c to relatively low values
allows for routing with asymptotically optimal average path length
while retaining most of the advantages of a uniform system, such
as easy programmability and quick bootstrap of the nodes entering
the system.
We also provide a matching lower bound for the average path length
of the routing schemes for any c. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00224-007-9074-x | Theory Comput. Syst. |
Keywords | Field | DocType |
Peer-to-peer,Overlay network,Greedy routing | Average path length,Multipath routing,Equal-cost multi-path routing,Combinatorics,Link-state routing protocol,Dynamic Source Routing,Path vector protocol,Static routing,Routing table,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 1 | 1432-4350 |
Citations | PageRank | References |
2 | 0.36 | 15 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Giovanni Chiola | 1 | 682 | 96.53 |
| Gennaro Cordasco | 2 | 344 | 47.06 |
| Luisa Gargano | 3 | 725 | 71.91 |
| Mikael Hammar | 4 | 163 | 16.22 |
| Alberto Negro | 5 | 74 | 11.67 |
| Vittorio Scarano | 6 | 609 | 71.49 |