Dynamic Overlay Networks for Robust and Scalable Routing

Dynamic Overlay Networks for Robust and Scalable Routing

Bart De Vleeschauwer, Filip De Turck, Bart Dhoedt, Piet Demeester
DOI: 10.4018/978-1-61520-686-5.ch023
(Individual Chapters)
No Current Special Offers


This chapter discusses the use of peer-to-peer overlay networks to route around failures and congestion points in the Internet. The motivation for this type of overlay network is that often the network layer takes considerable time to react to link failure and is typically not capable of avoiding congestion. For instance, it has been reported that link failure may take the BGP system more than fifteen minutes to react. As a result, the services going over these links suffer from lost connectivity or severe quality degradation in the case of congestion. One technique to solve this problem is to use overlay routing techniques to detect these problems and to route around the problematic link(s). In this chapter we elaborate on the overall architecture of such a system. The concept is introduced and the architecture and implementation of prototype components implementing the behavior is discussed. Subsequently it is described how the overlay topology can be managed dynamically to achieve the same performance as a full mesh topology with a number of overlay edges that scales linearly with the number of nodes in the network.
Chapter Preview


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.

Key Terms in this Chapter

Algorithm: A sequence of steps that together form a problem-solving procedure.

Implementation: The actual code and program that performs a specific functionality.

Topology Management: The activity of managing a topology and determining which nodes and edges are present in the topology.

Prototype: A sample implementation of a component that is typically developed to illustrate the behavior.

Congestion: The problem that occurs when more data needs to be sent on a link than the capacity that is available on that link. This will result in packet loss and large delays.

Overlay Routing: The concept of using an overlay network to route packets, as a result packets will follow a different route than when the normal direct Internet route is followed.

Overlay Network: A network formed by a number of server or end-hosts located at the edge of the network.

Peer-to-peer Network: A network formed by a number of end-hosts that together offer a service, such as file sharing, VoIP and overlay routing.

Complete Chapter List

Search this Book: