Universität Paderborn » SFB 901 » Projects » Project Area A » A2 » Abstract

Subproject A2 (until June 30, 2015)

Realizing and Optimizing Overlays over Physical Networks


Distributed applications often profit from custom-tailored overlays on top of an actual network. In this subproject, we will investigate approaches for such overlays to continuously adapt the overlay structure to available and required resources. Main candidates for such approaches are the use of abstract coordinate systems that will admit local routing algorithms, strategies to search for suitable neighbours, and the controlled manipulation of the actual, underlying network. These approaches will continuously adapt to changing resource and load situations. We shall use analysis, simulation, and experiments as evaluation techniques.

Metric embedding of interhet hosts into an Internet Coordinate System using a lighouses-based approach.

Underlay Characterisation

Modern overlay networks try to adapt to the structure of their underlay network, e.g. the internet, in order to improve communication in between their hosts. Since each host only establishes a small set of connections to other hosts in the overlay, these connections have to be chosen with respect to the underlays characteristics.

Normally these characteristics are estimated via an Internet Coordinate System (ICS). In most ICS approaches, hosts are metrically embedded into a coordinate system using latency information in between the hosts. Most prominent here, are the lighthouses-based approaches, where hosts, which are to be embedded, measure their latency to hosts from a special subset of all existing hosts in the network, called lighthouses.

However, the metrical embedding of hosts into ICS requires that the triangle-inequality is always fulfilled; a requirement that cannot be met in the environment of the internet, where peering-agreements and traffic-engineering can distort latency significantly. Therefore ICS can only approximately use latency to map internet hosts into a coordinate system. This arises the question: is latency a good characterization of the internet's structure?Therefore, our current work focuses on finding alternative characteristics of the internet and use them to formulate a distance-function, which can then be used to create and optimize the overlay network.

Routing in a planar graph.

Overlay Construction and Routing

We want to use the characterisation of internet hosts, e.g. by embedding into an ICS or by providing a distance-function, to create an overlay network which improves the communication patterns in between the hosts of the overlay. To achieve this, the following properties of the overlay are desirable:

  • The graph of the overlay resembles a spanner-graph.
  • The graph of the overlay has a constant node-degree.
  • The graph of the overlay supports a local routing strategy.

Local routing means that one host only needs to have information of its immediate neighbors or, as a bit relaxed rule, of its indirect neighbors up to a certain, but constant, hop-distance. Our goal is, to create overlay networks, which can themselves serve as underlays for other application-layer overlays.

As a starting-point, we have reviewed the existing ICS approaches and found an approach that provided high accuracy, using the L-infinity metric for embedding. Currently we are researching the construction of four-sector-graphs under the L-infinity metric and their properties.

Other research tracks are the examination of properties of delaunay triangulations which are constructed using arbitrary distance functions, performing efficient multicast-communication on the constructed overlays and fallback mechanisms for cases where local routing fails.

Optimization of disadvantegous overlay creation by adapting the underlay network.

Overlay Networks Modifying their Underlay

It is not always possible to construct a sufficiently good overlay from a given underlay network. For example specific roles of the involved nodes in an overlay network could require a specific overlay structure. If this structure cannot be properly mapped onto the underlay the only option left is to change the underlay.

In addition underlay networks can contain holes in their structure, which in turn could lead to routing failures using local strategies. So far, this has been met by switching to a recovery strategy using global knowledge of the network. Since this knowledge has to be obtained, either in advance or upon a failure of a local routing strategy, this incurs additional overhead.

With the advent of Wavelength Division Multiplex (WDM) switches, the modification of underlay networks has become possible on the physical layer, but so far this technology has mainly been used for traffic engineering where the network is manually adapted to observed traffic pattern.

Our research focuses on the development of automatic WDM assignment algorithms, which can reconfigure the physical network on-the-fly. In our approach this on-the-fly reconfiguration does not happen merely on the observed traffic pattern, but is driven by the structural requirements of the applications, forming the overlay network.