Compact roundtrip routing in directed networks (extended abstract)

ABSTRACT

The first sublinear average space universal compact routing schemes for directed networks are presented. For each integer k ≥ 1, they use O(k log n) size addresses; O(kn 1/k+1)-sized routing tables on average at each node; and achieve roundtrip routes of stretch at most 2k+1-1 in any (weighted) directed network. We extend our results to yield universal compact roundtrip routing schemes with the stronger requirement that they use sublinear maximum space at every node. These schemes also use O(k log n) size addresses and achieve roundtrip routes of stretch at most 2k+1 - 1 in any (weighted) directed network, and they bound the maximum sized table at each node by O(kn 3k+1/2·3k).

REFERENCES

• 1: D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). Unpublished manuscript.
• 2: D. Aingworth , C. Chekuri , R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 28-30, 1996, Atlanta, Georgia, United States
• 3: B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
• 4: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 5: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999 [doi>10.1137/S0097539794271898]
• 6: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 7: Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
• 8: Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.93-102, January 05-07, 1997, New Orleans, Louisiana, United States
• 9: Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.255-260, January 17-19, 1999, Baltimore, Maryland, United States
• 10: D. Dor , S. Halperin , U. Zwick, All pairs almost shortest paths, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.452, October 14-16, 1996
• 11: Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
• 12: C. Gavoille. A survey on interval routing scheme. Technical Memo RR-1182-97, Laboratoire Bordelais de Recherche en Informatique, Oct. 1997.
• 13: L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
• 14: D. Peleg and A. A. Sch~ffer. Graph spanners. J. of Graph Theory, 13:99-116, 1989.
• 15: David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]
• 16: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 17: Uri Zwick, All Pairs Shortest Paths in weighted directed graphs ? exact and almost exact algorithms, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.310, November 08-11, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Management