Technical reports

Compact forbidden-set routing

Andrew D. Twigg

December 2006, 115 pages

This technical report is based on a dissertation submitted June 2006 by the author for the degree of Doctor of Philosophy to the University of Cambridge, King’s College.

DOI: 10.48456/tr-678

Abstract

We study the compact forbidden-set routing problem. We describe the first compact forbidden-set routing schemes that do not suffer from non-convergence problems often associated with Bellman-Ford iterative schemes such as the interdomain routing protocol, BGP. For degree-d n-node graphs of treewidth t, our schemes use space O(t² d polylog(n)) bits per node; a trivial scheme uses O(n²) and routing trees use Ω(n) per node (these results have since been improved and extended – see [Courcelle, Twigg, Compact forbidden-set routing, 24th Symposium on Theoretical Aspects of Computer Science, Aachen 2007]. We also show how to do forbidden-set routing on planar graphs between nodes whose distance is less than a parameter l. We prove a lower bound on the space requirements of forbidden-set routing for general graphs, and show that the problem is related to constructing an efficient distributed representation of all the separators of an undirected graph. Finally, we consider routing while taking into account path costs of intermediate nodes and show that this requires large routing labels. We also study a novel way of approximating forbidden-set routing using quotient graphs of low treewidth.

Full text

PDF (1.1 MB)

BibTeX record

@TechReport{UCAM-CL-TR-678,
  author =	 {Twigg, Andrew D.},
  title = 	 {{Compact forbidden-set routing}},
  year = 	 2006,
  month = 	 dec,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-678.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-678},
  number = 	 {UCAM-CL-TR-678}
}