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 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 the actual Internet graph.
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 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 tested, 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
future Internet routing system.