Abstract
In systems using shortest-path routing tables, a single link failure is enough to interrupt the message transmission by disconnecting one or more shortest path spanning trees. The on-line recomputation of an alternative path or of the entire new shortest path trees, rebuilding the routing tables accordingly, is rather expensive and causes long delays in the message’s transmission [5, 10]. Hopefully, some of these costs will be reduced if the serial algorithms for dynamic graphs (e.g., those of [1]) could be somehow employed; to date, the difficulties of finding an e.cient distributed implementation have not been overcome (e.g., see [9]).
Research partially supported by “Progetto ALINWEB”, MIUR, Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale, NSERC Canada, and the Swiss BBW 03.0378-1 for EC contract 001907 (DELIS).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: CRC Handbook of Algorithms and Theory. CRC Press, Boca Raton (1997)
Di Salvo, A., Proietti, G.: Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 99–110. Springer, Heidelberg (2004)
Flocchini, P., Mesa, T., Pagli, L., Prencipe, G., Santoro, N.: Efficient protocols for computing optimal swap edges. In: Proc. of 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004) (2004) (to appear)
Itai, A., Rodeh, M.: The multi-tree approach to reliability in distributed networks. Information and Computation 79, 43–59 (1988)
Ito, H., Iwama, K., Okabe, Y., Yoshihiro, T.: Polynomial-time computable backup tables for shortest-path routing. In: Proc. of 10th Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), pp. 163–177 (2003)
Mohanty, H., Bhattacharjee, G.P.: A distributed algorithm for edge-disjoint path problem. In: Proc. of 6th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 344–361 (1986)
Nardelli, E., Proietti, G., Widmayer, P.: Finding all the best swaps of a minimum diameter spanning tree under transient edge failures. Journal of Graph Algorithms and Applications 2(1), 1–23 (1997)
Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algoritmica 35, 56–74 (2003)
Narvaez, P., Siu, K.Y., Teng, H.Y.: New dynamic algorithms for shortest path tree computation. IEEE Transactions on Networking 8, 735–746 (2000)
Peterson, L.L., Davie, B.S.: Computer Networks: A Systems Approach, 3rd edn. Morgan Kaufmann, San Francisco (2003)
Proietti, G.: Dynamic maintenance versus swapping: An experimental study on shortest paths trees. In: Näher, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 207–217. Springer, Heidelberg (2001)
Tarjan, R.E.: Application of path compression on balanced trees. Journal of ACM 26, 690–715 (1979)
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
Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Widmayer, P., Zuva, T. (2005). Computing All the Best Swap Edges Distributively. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_11
Download citation
DOI: https://doi.org/10.1007/11516798_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)