The Internet provides a best-effort service, which gives a robust fault-tolerant network.
However, the performance of the paths found in regular Internet routing is suboptimal.
As a result, applications rarely achieve all the benefits that the Internet can provide. The
problem is made more difficult because the Internet is formed of competing ISPs which
have little incentives to reveal information about the performance of Internet paths. As a
result, the Internet is sometimes referred as a ‘black-box’. Detouring uses routing overlay
networks to find alternative paths (or detour paths) that can improve reliability, latency
and bandwidth. Previous work has shown detouring can improve the Internet. However,
one important issue remains—how can these detour paths be found without conducting
large-scale measurements?
In this thesis, we describe practical methods for discovering detour paths to improve
specific performance metrics that are scalable to the Internet. Particularly we concentrate
our efforts on two metrics, latency and bandwidth, which are arguably the two most important
performance metrics for end-user’s applications. Taking advantage of the Internet
topology, we show how nodes can learn about segments of Internet paths that can be exploited
by detouring leading to reduced path latencies. Next, we investigate bandwidth
detouring revealing constructive detour properties and effective mechanisms to detour
paths in overlay networks. This leads to Ukairo, our bandwidth detouring platform that is
scalable to the Internet and tcpChiryo, which predicts bandwidth in an overlay network
through measuring a small portion of the network.