Lab Contact: Mark Batty
Supervisor: Dr Jagdish J. Modi
Special Resources: None

Efficient Parallel Internet Routing Algorithms

This should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise. Some background reading on path problems, with applications to Internet Routing, would be helpful but not essential.

The aim of the project is to propose and implement a parallel algorithm for finding minimal-distance paths between a finite set of nodes, and where several equally good paths exist, then to further choose between them based on some other criterion, for example, reliability or bandwidth. Thus the problem incorporates at least two parameters [1][2].

In the past students have considered rail and road networks minimizing a single parameter such as distance or time, and found an algorithm analogous to matrix multiplication to be suitable for parallel computation [3]. Dijkstra’s algorithm is found not to be easily parallelisable. However, unlike a rail or road network, where the number of shortest paths between nodes is very small, on the internet topology very frequently there are many “shortest” paths between pairs of nodes, and in this case we choose between these many paths on the basis of some other criterion such as reliability or bandwidth. It turns out that this two-parameter problem can be considered as an extension of the single-parameter problem, and many of the algorithmic aspects carry through.

The dataset can be downloaded from the Internet Topology Zoo website here. The distances between nodes can be readily calculated using the longitudes and latitudes provided. In the design of the algorithm, I would suggest the following be taken into consideration:

To choose using Flynn’s classification [4] the best parallel computation model suitable for each phase of the algorithm.
To limit the scope and concentrate on a specific network provider, for example the Colt Telecom network, with a total of 152 nodes.
To consider such developments as improving the efficiency of computation by avoiding large sparse areas in order to minimise data movements using the Fox-Otto algorithm [5].
To identify and temporarily remove nodes that are not necessary for computing the shortest paths to reduce the processor connectivity.

Parallel computers have as a core structure a set of interconnected processors. The optimal choice of interconnection for a particular problem may not always be available [6]. It would be interesting to explore the features of the two-dimensional graph arising from the connections between destinations (edges), and to relate this to processor topology based on lattice, tree or the hypercube. The student may also wish to consider the problem in terms of the mathematical concept of a semi-ring structure, to understand more precisely the properties of the ensuing problem, and some of the open problem areas [1][2].

References

[1] Dynerowicz S., Griffin T. G., On the Forwarding Paths Produced by Internet Routing Algorithms. Seweryn Dynerowicz (University of Namur, Belgium), Timothy G. Griffin. ICNP 2013.
[2] Griffin T. J., Lecture Notes, Algebraic Path Problems with applications to Internet Routing, Computer Laboratory, University of Cambridge, 2013.
[3] Batty M. Parallel Route Planning for the London Underground, Diploma in Computer Science, Computer Laboratory, 2007.
[4] Flynn, M.J. (1966). Very high speed computing systems. Proceedings of IEEE,54 (12).
[5] Akpan, O. Efficient parallel implementation of the Fox algorithm. Computer Science Department, Bowie State University, 2003.
[6] Modi J. Parallel Algorithms and Matrix Computation, OUP, 1988.
[7] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, second edition, 2003.
[8] Grama, Gupta, Karypis, Kumar. Introduction to Parallel Computing, Pearson Education, second edition, 2005.