Research : Routing
Paul Jakma — A Distributed, Compact Routing Protocol for the Internet
1 December 2016 / routing
Congratulations to Paul Jakma, who graduated this week after successfully completing this PhD thesis on A Distributed, Compact Routing Protocol for the Internet earlier this year.
Alex Waite — Using Actors for Massive Simulation of Distributed Routing Algorithms
20 May 2013 / routing
Congratulations to Alex Waite, who has successfully completed his MSci project on Using Actors for Massive Simulation of Distributed Routing Algorithms. The abstract of his final report reads “Existing simulators designed for the evaluation of distributed graph algorithms tend to be based on a threaded model of concurrency. This leads to scaling issues when simulating particularly large graphs such as Internet-like graphs, or poor utilisation of resources when using large multiprocessor machines. Here, I present a simulator that uses actor-model concurrency to directly model the interactions between nodes in a graph during the simulation of a distributed algorithm. While more closely modelling the behaviour of an abstract network, the actor model brings performance advantages”.
Distributed k-core Decomposition of Dynamic Graphs
13 December 2012 / routing
The k-core decomposition can be used to reveal structure in a graph. It is straight-forward to implement using a centralised algorithm with complete knowledge of the graph, but no distributed k-core decomposition algorithm has been published. In this poster, we present a continuous, distributed, k-core decomposition algorithm for dynamic graphs, outline a proof of correctness, and give initial performance results. We briefly describe an application of this distributed k-core algorithm to landmark selection for compact routing.
New MSci student: Alex Waite
17 September 2012 / routing
Welcome to Alex Waite, who will be doing his MSci project under my supervision. The aim of his project is to build a robust and scalable routing simulator using the Scala programming language. The simulator will use functional programming constructs and the actor model of parallelism to directly model the routing problem, and to allow it to scale to large networks running simulations on clusters or large multicore systems. The simulator will be tested using snapshots of the Internet AS graph, aiming to use them to model features of some proposed compact routing algorithms (e.g., distributed k-shells graph decomposition algorithms for landmark placement or distributed implementations of Thorup-Zwick compact routing).
Harnessing Internet Topological Stability in Thorup-Zwick Compact Routing
13 January 2012 / 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
11 January 2012 / routing
Compact Routing on the Internet AS Graph
15 April 2011 / 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.
New research student: Paul Jakma
4 October 2010 / 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.
Modelling and Analysis of Networked and Distributed Systems
17 June 2010 / routing
I attended the SICSA workshop on Modelling and Analysis of Networked and Distributed Systems at the University of Stirling on 17 June 2010. The aim of the workshop was to bring together researchers in computer networking and formal methods, with the hope of identifying areas of mutual interest, and encouraging joint research.
Graham Mooney — Evaluating Compact Routing Algorithms on Real-World Networks
9 June 2010 / 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.
Talk on Compact Routing for the Internet
30 April 2010 / routing
I gave a seminar at the University of Stirling on 30 April 2010, on the subject Compact Routing for the Internet. In it, I presented some 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
1 December 2009 / 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
22 September 2009 / 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
24 August 2009 / 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
1 July 2007 / 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.