Improved compact routing schemes for dynamic trees

ABSTRACT

A classical routing problem consists of assigning a label and distinct port numbers to each node of a graph, such that for every node v, given its own label and the label of any destination vertex u, node v can find which of its incident port numbers leads to the next vertex on a shortest path connecting v and u. In the static (fixed topology) setting, such a routing scheme is evaluated by the label size, i.e., the maximal number of bits stored in a label. Naturally, special attention is given to compact schemes, which are schemes enjoying asymptotically optimal labels. Many routing schemes were proposed for the static setting. However, the more realistic and complex dynamic setting, in which topology changes may occur at arbitrary nodes, has received much less attention. In the dynamic setting, the occurrence of topology changes may force the scheme to occasionally update the (hopefully short) labels, by delivering information from place to place. This raises a natural tradeoff between the size of the labels and the number of messages required for maintaining them. The above dynamic routing problem was proposed by Afek, Gafni, and Ricklin (1989), who also presented an elegant and rather efficient dynamic routing scheme for trees, supporting one type of topology change, namely, the addition of a leaf. Various attempts for improving the tradeoff between the label size and the message complexity as well as for supporting more types of topology changes on trees, were subsequently proposed. Still, the best known compact routing scheme for dynamic trees has very high message complexity, namely, O(n^ε) amortized messages per topological change. Moreover, previous routing schemes for dynamic trees support at most two kinds of topology changes, namely, the addition and the removal of a leaf node. In this paper, we present two compact routing schemes for dynamic trees that incur extremely low message complexity and can support more types of topology changes than previous schemes. We first present a dynamic compact routing scheme that supports the additions of both leaves and internal nodes and incurs only O(log n) amortized message complexity per node. We then extend that scheme obtaining a dynamic compact routing scheme that supports additions of both leaves and internal nodes as well as deletions of nodes of degree at most 2. The extended scheme incurs O(log² n) amortized message complexity per topological change.

REFERENCES

• 1: Yehuda Afek , Baruch Awerbuch , Serge Plotkin , Michael Saks, Local management of a global resource in a communication network, Journal of the ACM (JACM), v.43 n.1, p.1-19, Jan. 1996 [doi>10.1145/227595.227596]
• 2: Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146411]
• 3: Y. Afek , E. Gafni , M. Ricklin, Upper and lower bounds for routing schemes in dynamic networks, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.370-375, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63505]
• 4: Serge Abiteboul , Stephen Alstrup , Haim Kaplan , Tova Milo , Theis Rauhe, Compact Labeling Scheme for Ancestor Queries, SIAM Journal on Computing, v.35 n.6, p.1295-1309, 2006 [doi>10.1137/S0097539703437211]
• 5: Yehuda Afek , Michael Saks, Detecting global termination conditions in the face of uncertainty, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.109-124, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41850]
• 6: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton , Jack Zito, Two Simplified Algorithms for Maintaining Order in a List, Proceedings of the 10th Annual European Symposium on Algorithms, p.152-164, September 17-21, 2002
• 7: Reuven Bar-Yehuda , Shay Kutten, Fault tolerant distributed majority commitment, Journal of Algorithms, v.9 n.4, p.568-582, Dec. 1988 [doi>10.1016/0196-6774(88)90017-X]
• 8: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 9: Y. Emek and A. Korman. Estimating the Number of Events in a Network:an Online Distributed problem, 2008.
• 10: Pierre Fraigniaud , Cyril Gavoille, Routing in Trees, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.757-772, July 08-12, 2001
• 11: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 12: Sampath Kannan , Moni Naor , Steven Rudich, Implicit representation of graphs, SIAM Journal on Discrete Mathematics, v.5 n.4, p.596-603, Nov. 1992 [doi>10.1137/0405049]
• 13: Haim Kaplan , Tova Milo , Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.954-963, January 06-08, 2002, San Francisco, California
• 14: A. Korman. General compact labeling schemes for dynamic trees.J. Distributed Computing, 20(3):179--193, 2007.
• 15: Amos Korman , Shay Kutten, Controller and estimator for dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281127]
• 16: A. Korman and D. Peleg. Compact Separator Decomposition for Dynamic Trees and Applications. J. Distributed Computing, to appear. (Preliminary version appeared in DISC 2007).
• 17: A. Korman, D. Peleg, and Y. Rodeh. Labeling schemes for dynamic treenetworks. Theory Comput. Syst., 37(1):49--75, 2004.
• 18: Amos Korman , David Peleg, Labeling schemes for weighted dynamic trees, Information and Computation, v.205 n.12, p.1721-1740, December, 2007 [doi>10.1016/j.ic.2007.08.004]
• 19: Amos Korman , David Peleg, Dynamic routing schemes for graphs with low local density, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-18, August 2008 [doi>10.1145/1383369.1383372]
• 20: N. Santoro and R. Khatib. Labelling and implicit routing in networks. The Computer Journal 28, (1985), 5-8.
• 21: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 22: J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987 [doi>10.1093/comjnl/30.4.298]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Network topology; Network communications

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Trees; Distributed data structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
distributed algorithms, dynamic trees, routing schemes