Abstract
We consider the problem of routing a message in a mesh network with faulty nodes. The number and positions of faulty nodes is unknown. It is known that a flooding strategy like expanding ring search can route a message in the minimum number of steps h while it causes a traffic (i.e. the total number of messages) of \({\mathcal O}(h^{2})\). For optimizing traffic a single-path strategy is optimal producing traffic \({\mathcal O}(p + h)\), where p is the perimeter length of the barriers formed by the faulty nodes. Therefore, we define the comparative traffic ratio as a quotient over p+h and the competitive time ratio as a quotient over h. Optimal algorithms with constant ratios are known for time and traffic, but not for both. We are interested in optimizing both parameters and define the combined comparative ratio as the maximum of competitive time ratio and comparative traffic ratio. Single-path strategies using the right-hand rule for traversing barriers as well as multi-path strategies like expanding ring search have a combined comparative ratio of Θ(h). It is an open question whether there exists an online routing strategy optimizing time and traffic for meshes with an unknown set of faulty nodes. We present an online strategy for routing with faulty nodes providing sub-linear combined comparative ratio of \(h^{{\mathcal O}(\sqrt{\frac{{\rm log log}h}{{\rm log}h}})}\).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D., Westbrook, J., Zhu, W.: Robot navigation with range queries. In: Proc. of the 28th Annual ACM Symposium on Theory of Computing, pp. 469–478 (1996)
Berman, P.: On-line searching and navigation. In: Fiat, A., Woeginger, G.J. (eds.) Dagstuhl Seminar 1996. LNCS, vol. 1442, pp. 232–241. Springer, Heidelberg (1998)
Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM Journal on Computing 26, 110–137 (1997)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wireless networks 7(6), 609–616 (2001)
Cole, R.J., Maggs, B.M., Sitaraman, R.K.: Reconfiguring Arrays with Faults Part I: Worst-case Faults. SIAM Journal on Computing 26(16), 1581–1611 (1997)
Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM Journal on Computing 30(1), 300–317 (2000)
Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. 11th Canadian Conference on Computational Geometry, pp. 51–54 (1999)
Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proc. of the 6th int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 24–33 (2002)
Lumelsky, V.J.: Algorithmic and complexity issues of robot motion in an uncertain environment. Journal of Complexity 3(2), 146–182 (1987)
Lumelsky, V.J., Stepanov, A.A.: Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica 2, 403–430 (1987)
Mauve, M., Widmer, J., Hartenstein, H.: A survey on position-based routing in mobile ad hoc networks. IEEE Network Magazine 15(6), 30–39 (2001)
Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. In: Proc. of the 16th Int. Colloq. on Automata, Languages, and Programming (ICALP 1989), pp. 610–620. Elsevier Science Publishers Ltd. Amsterdam (1989)
Rao, N., Kareti, S., Shi, W., Iyenagar, S.: Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical report, Oak Ridge National Laboratory, ORNL/TM-12410 (1993)
Rührup, S., Schindelhauer, C.: Competitive time and traffic analysis of position-based routing using a cell structure. In: Proc. of the 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IPDPS/WMAN 2005), p. 248 (2005)
Rührup, S., Schindelhauer, C.: Online routing in faulty meshes with sub-linear comparative time and traffic ratio. Technical report, University of Paderborn, tr-rsfb-05-076 (2005)
Wu, J.: Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels. IEEE Transactions on Parallel and Distributed Systems 11, 149–159 (2000)
Wu, J., Jiang, Z.: Extended minimal routing in 2-d meshes with faulty blocks. In: Proc. of the 1st Intl. Workshop on Assurance in Distributed Systems and Applications (in conjuction with ICDCS 2002), pp. 49–55 (2002)
Zakrevski, L., Karpovsky, M.: Fault-tolerant message routing for multiprocessors. In: Parallel and Distributed Processing, pp. 714–730. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rührup, S., Schindelhauer, C. (2005). Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_5
Download citation
DOI: https://doi.org/10.1007/11561071_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)