Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Rajan, Varun http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-38721
URL:

Space Efficient Edge-Fault Tolerant Routing

pdf-format:


Abstract

Let G be an undirected weighted graph with n vertices and m edges, and k >= 1 be an integer. We preprocess the graph in O^~(mn) time, constructing a data structure of size O^~ k deg{v}+n^{1/k}) words per vertex v in V, which is then used by our routing scheme to ensure successful routing of packets even in the presence of a single edge fault. The scheme adds only O(k) words of information to the message. Moreover, the stretch of the routing scheme, i.e., the maximum ratio of the cost of the path along which the packet is routed to the cost of the actual shortest path that avoids the fault, is only O(k^2). Our results match the best known results for routing schemes that do not consider failures, with only the stretch being larger by a small constant factor of O(k). Moreover, a 1963 girth conjecture of Erdos, known to hold for k=1,2,3 and 5, implies that Omega(n^{1+1/k}) space is required by any routing scheme that has a stretch less than 2k+1. Hence our data structures are essentially space efficient. The algorithms are extremely simple, easy to implement, and with minor modifications, can be used under a centralized setting to efficiently answer distance queries in the presence of faults. An important component of our routing scheme that may be of independent interest is an algorithm to compute the shortest cycle passing through each edge. As an intermediate result, we show that computing this in a distributed model that stores at each vertex the shortest path tree rooted at that node requires Theta(mn) message passings in the worst case.

BibTeX - Entry

@InProceedings{rajan:LIPIcs:2012:3872,
  author =	{Varun Rajan},
  title =	{{Space Efficient Edge-Fault Tolerant Routing}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{350--361},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3872},
  URN =		{urn:nbn:de:0030-drops-38721},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.350},
  annote =	{Keywords: Routing, Fault tolerant algorithms, Space efficiency, Distributed data structures, Tight bounds}
}

Keywords: Routing, Fault tolerant algorithms, Space efficiency, Distributed data structures, Tight bounds
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Related Scholarly Article:
Issue date: 2012
Date of publication: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI