Dr. Stephen D. Strowes

Theses

1. Compact Routing for the Future Internet

   S.D. Strowes

   • PhD thesis, defended 2012.
   • Abstract:

     The Internet relies on its inter-domain routing system to allow data transfer between any two endpoints regardless of where they are located. This routing system currently uses a shortest path routing algorithm (modified by local policy constraints) called the Border Gateway Protocol. The massive growth of the Internet has led to large routing tables that will continue to grow. This will present a serious engineering challenge for router designers in the long-term, rendering state (routing table) growth at this pace unsustainable.

     There are various short-term engineering solutions that may slow the growth of the inter-domain routing tables, at the expense of increasing the complexity of the network. In addition, some of these require manual configuration, or introduce additional points of failure within the network. These solutions may give an incremental, constant factor, improvement. However, we know from previous work that all shortest path routing algorithms require forwarding state that grows linearly with the size of the network in the worst case.

     Rather than attempt to sustain inter-domain routing through a shortest path routing algorithm, compact routing algorithms exist that guarantee worst-case sub-linear state requirements at all nodes by allowing an upper-bound on path length relative to the theoretical shortest path, known as path stretch. Previous work has shown the promise of these algorithms when applied to synthetic graphs with similar properties to the known Internet graph, but they haven't been studied in-depth on Internet topologies derived from real data.

     In this dissertation, I demonstrate the consistently strong performance of these compact routing algorithms for inter-domain routing by performing a longitudinal study of two compact routing algorithms on the Internet Autonomous System (AS) graph over time. I then show, using the k-cores graph decomposition algorithm, that the structurally important nodes in the AS graph are highly stable over time. This property makes these nodes suitable for use as the “landmark” nodes used by the most stable of the compact routing algorithms evaluated, and the use of these nodes shows similar strong routing performance. Finally, I present a decentralised compact routing algorithm for dynamic graphs, and present state requirements and message overheads on AS graphs using realistic simulation inputs.

     To allow the continued long-term growth of Internet routing state, an alternative routing architecture may be required. The use of the compact routing algorithms presented in this dissertation offer promise for a scalable future Internet routing system.

2. Peer-to-Peer Audio Conferencing

   S.D. Strowes

   • Masters dissertation, submitted 2005.
   • Abstract:

     The intention of IP Multicast as a service provided by network infrastructure was to allow groups of hosts to share similar data, leaving the network to deal with the complexities of group membership and routing issues. One natural use for IP Multicast was group conferencing.

     Adoption of IP Multicast has not been swift, however, leaving conferencing applications designed for use with the service unusable over significant parts of the Internet.

     This dissertation presents Orta, a new peer-to-peer network overlay which is designed to allow group conferencing. The implementation is presented as a reusable software library, and is not tied to any existing application; one application, the Robust Audio Tool, is modified to use this library rather than IP Multicast as a proof-of-concept implementation. Presented are implementation details and evaluation results detailing the characteristics of the overlay, with some focus on its usefulness for real-time applications.