Dynamic Overlay Networks for Robust and Scalable Routing

Introduction

Routing in the Internet still exhibits a number of inefficiencies that can result in a suboptimal route being followed when there is a better route available, according to a metric such as delay or loss (Almes, 1999). Another problem with the routing process is that sometimes connectivity can be lost altogether. While some failures are short lived, sometimes these periods of lost connectivity can last more than fifteen minutes (Savage et al., 1999)(Savage, Anderson, et al., 1999). Overlay networks offer a technique to enhance an underlying network by pushing some functionality to a higher layer without requiring changes in the lower layers. When using an overlay routing network, a number of nodes form a virtual overlay topology and use the monitoring information available in this topology to enhance a service. Monitoring information can be gathered using active probing. In this chapter, a peer-to-peer overlay network is used to detect end-to-end connectivity problems and route the traffic via intermediate overlay servers. As a result a different route than the normal network route is followed, which leads to better values for delay and packet loss and can also provide an alternative route when the network itself was not yet able to restore the connectivity. This concept is illustrated in Figure 1, where the clients in domain 1 use an intermediate overlay hop, a component in domain 3, to send the packets destined for the clients in domain 2.

Figure 1.

An example of overlay routing around IP link failure

The architecture of these overlay networks consists of two distinct components. Overlay access components are used to determine whether or not traffic would benefit from the overlay rerouting. When this is the case, the overlay access component adds a number of headers to the packet to make it overlay network compliant and sends it to an overlay server component. These overlay server components are responsible for forming an overlay routing network. They sustain the connectivity between each other by maintaining an overlay topology and routing tables. By using active monitoring, the overlay servers are able to have a view on the connectivity in the underlying network. Information on this connectivity is exchanged between the servers and based on this information the overlay routing tables are calculated. When an overlay packet arrives at an overlay server, it consults its routing table to determine the next overlay hop and sends the packet further on its way to its final destination. In this chapter we discuss the actual architecture of these components and show the validity of this approach using evaluation results of prototype components. Using commodity hardware it is possible to treat 100,000s of packets/second on each overlay server and overlay packet treatment incurs a sub millisecond delay.

A critical problem faced by the overlay networks is how to manage the overlay routing topology. One of the challenges is whether to choose a topology with a lot of overlay edges, which requires a lot of network probing and much communication overhead or a topology with a lower number of edges which is more vulnerable to network failure. Traditional overlay routing networks use a Full Mesh approach. However, such a topology has a number of overlay edges that scales quadratically with the number of overlay servers. In Almes et al. (1999), the authors report that due to the usage of a full mesh topology the RON overlay network only scales up to 50 nodes. Therefore, we discuss how using smaller topologies and dynamically managing the topology makes it possible to achieve a similar resilience as a full mesh approach but with fewer edges. A number of algorithms are presented to construct the initial overlay topology and to dynamically adapt this topology when failures in the underlying networks occur. Simulation is used to demonstrate the validity of the approach. The simulation results show that it is possible to use a topology with a limited amount of overlay edges that matches the performance of using a Full Mesh topology.