Search Results

Documents authored by Rajan, Varun


Document
Space Efficient Edge-Fault Tolerant Routing

Authors: Varun Rajan

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)


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.

Cite as

Varun Rajan. Space Efficient Edge-Fault Tolerant Routing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 350-361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{rajan:LIPIcs.FSTTCS.2012.350,
  author =	{Rajan, Varun},
  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 =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.350},
  URN =		{urn:nbn:de:0030-drops-38721},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.350},
  annote =	{Keywords: Routing, Fault tolerant algorithms, Space efficiency, Distributed data structures, Tight bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail