1 Search Results for "Rajan, Varun"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.350

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-dev.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}
}

Refine by Author
1 Rajan, Varun

Refine by Classification

Refine by Keyword
1 Distributed data structures
1 Fault tolerant algorithms
1 Routing
1 Space efficiency
1 Tight bounds

Refine by Type
1 document

Refine by Publication Year
1 2012

1 Search Results for "Rajan, Varun"

Space Efficient Edge-Fault Tolerant Routing

Abstract

Cite as

Thanks for your feedback!

Could not send message