Overlay networks are networks operating on the inter-domain level, where the edge hosts learn of each other and, based on knowledge of underlying network performance, they form loosely coupled neighboring relationships. These relationships can be used to induce a specific graph, where nodes are representing hosts and edges are representing neighboring relationships. Graph abstraction and the associated graph theory can be further used to formulate routing algorithms on overlay networks. The main advantage of overlay networks is that they offer the possibility to augment the IP routing as well as the QoS functionality offered by the Internet.