Some Performance and Design Aspects of Overlay Networks

Csaba Király (
Department of Telecommunications, Budapest University of Technology and Economics
June, 2012
Full text (external site)


The general objective of this thesis is to identify key performance issues and bottlenecks of overlay networks, analyze their impact on state of the art systems, and
to provide new techniques to improve performance. The thesis is divided into two
main parts.

The goal of the first part is to analyze performance characteristics of Anonymous Routing Overlays, and to overcome their most important performance problem, i.e. high end-to-end delays.

First, we provide deeper insight into the transport mechanisms hidden behind some of these abstract overlay technologies by showing an analysis of TCP
dynamics in the case of short-lived connections, deriving detailed performance
characteristics (such as completion time distribution) through an open multiclass
queuing network model of TCP.

Performance differences between TCP based and datagram based overlay networks are then studied through the example of Anonymous Routing Overlays.
First, onion routing networks and their most prevalent example, the Tor application is described. We present an analysis of some of the networking technologies
applied and their consequences. Then we propose a novel system design for anonymous routing, called IPpriv, an overlay network similar in its scope to Tor, but
different in its design choices and performance characteristics. The peculiarity of IPpriv is not just its datagram based design approach, but that it entirely
relies on IPsec, therefore providing improved performance due to kernel level or
router based operation.

In the second part of the thesis another widely used example of overlay networks will be considered: peer-to-peer (P2P) networks. More specifically, our goal
is to analyze and improve the performance of live P2P Streaming Overlays.

In P2P streaming, scheduling is the decision of what to send and whom to send
it to. First, we present some performance bounds valid for idealized conditions,
and propose a novel scheduling algorithm that achieves this bound under these
simplified assumptions. We extend this study by lifting some of the assumptions, namely, bandwidth homogeneity, describing a network-aware variant of this
scheduling algorithm that considers the bandwidth of other peers and outperforms
other algorithms known from the literature.

Finally, we provide an example of how overlay networks allow the application of
some networking concepts even if the underlying network does not provide support
for it. Namely, packet priority support is mostly missing on the large-scale Internet, still, applications serving as ”overlay routers” allow us to implement effective
prioritization techniques. We introduce the design of a media-aware scheduler
and show how it influences system performance, including a study of the effective
end-user perceived video quality improvements.