Research : Routing

Harnessing Internet Topological Stability in Thorup-Zwick Compact Routing

Posted on in category routing

Thorup-Zwick (TZ) compact routing guarantees sublinear state growth with the size of the network by routing via landmarks and incurring some path stretch. It uses a pseudo-random landmark selection designed for static graphs, and unsuitable for Internet routing. We propose a landmark selection algorithm for the Internet AS graph that uses k-shells decomposition to choose landmarks. Using snapshots of the AS graph from 1997—2010, we demonstrate that the ASes in the maximal k-shell are highly-stable over time, and form a sufficient landmark set for TZ routing in the overwhelming majority of cases (in the remainder, adding the next k-shell suffices). We evaluate path stretch and forwarding table sizes, and show that these landmark sets retain low average path stretch with tiny forwarding tables, but are better suited to the dynamic nature of the AS graph than the original TZ landmark selection algorithm.

Stephen Strowes — Compact Routing for the Future Internet

Posted on in category routing

Congratulations to Stephen Strowes, who successfully defended his PhD thesis (on “Compact Routing for the Future Internet”) today. The abstract of his dissertation is:

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.

Update (18 February 2012): the final version of Stephen's dissertation is now available.

Compact Routing on the Internet AS Graph

Posted on in category routing

Compact routing algorithms have been presented as candidates for scalable routing in the future Internet, achieving near-shortest path routing with considerably less forwarding state than the Border Gateway Protocol. Prior analyses have shown strong performance on power-law random graphs, but to better understand the applicability of compact routing algorithms in the context of the Internet, they must be evaluated against real- world data. To this end, we present the first systematic analysis of the behaviour of the Thorup-Zwick (TZ) and Brady-Cowen (BC) compact routing algorithms on snapshots of the Internet Autonomous System graph spanning a 14 year period. Both algorithms are shown to offer consistently strong performance on the AS graph, producing small forwarding tables with low stretch for all snapshots tested. We find that the average stretch for the TZ algorithm increases slightly as the AS graph has grown, while previous results on synthetic data suggested the opposite would be true. We also present new results to show which features of the algorithms contribute to their strong performance on these graphs.

  • Stephen Strowes, Graham Mooney, and Colin Perkins, Compact Routing on the Internet AS-Graph, Proceedings of the 14th IEEE Global Internet Symposium, Shanghai, China, April 2011. DOI:10.1109/INFCOMW.2011.5928931

PhD Student Scholarships

Posted on in category routing

The College of Science and Engineering at the University of Glasgow is pleased to announce the availability of College postgraduate research scholarships for PhD registration in 2011. These prestigious scholarships are highly competitive and we seek candidates who can demonstrate excellence in a single discipline or cross-disciplinary expertise. The scholarship will be for up to three and a half years and will meet the cost of fees (at the home-EU level) and provide a stipend at the Research Council recommended rates.

Prospective candidates must have secured the support of a PhD supervisor prior to application. Candidates who have an interest in routing for the future Internet, in particular in developing scalable alternatives to BGP, are encouraged to contact me by email including a draft research proposal, to discuss whether they would be a suitable candidate for my support.

The deadline for applications to the College is 09:00 hours (GMT) on Monday 28 February 2011. You are advised to contact me in plenty of time to develop and prepare your application before this deadline.

New research student: Paul Jakma

Posted on in category routing

Welcome to Paul Jakma, who starts work as a new research student under my supervision today. Paul is sponsored by SICSA, and will be working on new interdomain Internet routing algorithms.

Graham Mooney — Evaluating Compact Routing Algorithms on Real-World Networks

Posted on in category routing

Congratulations to Graham Mooney who graduates with an MSci in Computing Science, after submitting his thesis on Evaluating Compact Routing Algorithms on Real-World Networks. This dissertation uses simulation to compare the performance of the Thorup-Zwick and Brady-Cowen compact routing algorithms on snapshots of the Internet AS graph over a 12 year period. The results indicate that these algorithms behave consistently over time, and exhibit extremely small forwarding tables with very low path inflation.

Compact Routing for the Internet

Posted on in category routing

I'm giving a seminar at the University of Stirling on 30 April 2010, on the subject Compact Routing for the Internet. This talk will present initial results comparing the performance of the Thorup-Zwick (TZ) and Brady-Cowen compact routing schemes on snapshots of the Internet AS graph, and report on the ideas for a practical landmark selection algorithm for TZ compact routing.

Deterministic, Reduced-Visibility Inter-Domain Forwarding

Posted on in category routing

Inter-domain forwarding state is growing at a super-linear rate, rendering older routers obsolete and increasing the cost of replacement. A reduction of state will alleviate this problem. In this paper, we outline a new reduced-state inter-domain forwarding mechanism. We carefully drop portions of the advertised forwarding state using a utility measure for prefixes based on the length of the prefix and the path length to its origin. A deterministic forwarding algorithm uses the resulting partial view. The graph of connections between autonomous systems is shallow, offering many viable paths for data flows, a property we aim to use to achieve minimal detrimental effect on delay and AS path stretch.

New MSci Project Student: Graham Mooney

Posted on in category routing

Welcome to Graham Mooney, who will be doing his MSci project under the supervision of myself and Stephen Strowes. Graham will be working on the simulation of compact routing algorithms, to understand the trade off between performance and complexity for various different compact routing algorithms.

Trilogy Future Internet Summer School

Posted on in category routing

Stephen will be attending the Trilogy project's Future Internet Summer School and presenting some early work on Randomness for Reduced-State Inter-Domain Forwarding.

New research student: Stephen Strowes

Posted on in category routing

Welcome to Stephen Strowes, who starts work as a new research student under my supervision today. Stephen is an EPSRC-funded student, who will be working on alternative network architectures.