Dr. Thomas Fuhrmann, Kendy Kutzner

Abstract:

Unfortunately, from all known "Distributed Hash Table"-based overlay networks only a few of them relate to proximity in terms of latency. So a query routing can come with high latency when very distant hops are used. One can imagine hops are from one continent to the other in terms of here and back. Thereby it is possible that the target node is located close to the requesting node. Such cases increase query latency to a great extent and are responsible for performance bottlenecks of a query routing.

There exist two main strategies to reduce latency in the query routing process: Proximity Neighbor Selection and Proximity Route Selection. As a new proposal of PNS for the IGOR overlay network, Merivaldi is developed. Merivaldi represents a combination of two basic ideas: The first idea is the Meridian framework and its Closest-Node- Discovery without synthetic coordinates. The second idea is Vivaldi, a distributed algorithm for predicting Internet latency between arbitrary Internet hosts. Merivaldi is quite similar to Meridian. It differs in using no direct Round Trip Time measurements like Meridian does to obtain latency characteristics between hosts. Merivaldi obtains latency characteristics of nodes using the latency prediction derived from the Vivaldi-coordinates. A Merivaldi-node forms exponentially growing latency-rings, i.e., the rings correspond to latency distances to the Merivaldi-node itself. In these rings node-references are inserted with regard to their latency characteristics. These node-references are obtained through a special protocol. A Merivaldi-node finds latency-closest nodes through periodic querying its ring-members for closer nodes. If a closer node is found by a ring-member the query is forwarded to this one until no closer one can be found. The closest on this way reports itself to the Merivaldi-node.

Exemplary analysis show that Merivaldi means only a modest burden for the network. Merivaldi uses O(log N) CND-hops at maximum to recognize a closest node, where N is the number of nodes. Empirical tests demonstrate this analysis. Analysis shows, the overhead for a Merivaldi-node is modest. It is shown that Merivaldi's Vivaldi works with high quality with the used PING-message type.

BibTex:

@diplomathesis{kising07proxselectigor,
  author = {Yves Philippe Kising},
  title = {Proximity Neighbor Selection and Proximity Route Selection for the Overlay-Network IGOR},
  type = {Diploma Thesis},
  address = {Lehrstuhl fuer Netzwerkarchitekturen, TU Muenchen, Germany},
  month = jun # "~15",
  year = 2007,
  url = {http://i30www.ira.uka.de/teaching/theses/pasttheses/}
}