Average stretch analysis of compact routing schemes

This paper presents some analytic results concerning the pivot interval routing (PIR  ) strategy of [T. Eilam, C. Gavoille, D. Peleg, Compact routing schemes with low stretch factor, J. Algorithms 46(2) (2003) 97–114, Preliminary version appeared. in: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, June 1998, pp. 11–20.] That strategy allows message routing on every weighted nn-node network along paths whose stretch   (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at most three, with routing tables of size O(nlog3/2n) bits per node. In addition, the route lengths are at most 2D2D (⌈1.5D⌉⌈1.5D⌉ for uniform weights) where D   is the weighted diameter of the network. The PIRPIR strategy can be constructed in polynomial time and can be implemented so that the generated scheme is in the form of an interval routing scheme (IRS  ), using at most O(nlogn) intervals per link. Here, it is shown that there exists an unweighted nn-node graph GG and an identity assignment IDID for its nodes such that for every R∈PIRR∈PIR on GG with a set of pivots computed by a greedy cover algorithm (respectively, a randomized algorithm), AvStrG(R)>3-o(1)AvStrG(R)>3-o(1) (respectively, with high probability). Also, it is shown that for almost every unweighted nn-node graph GG, and for every R∈PIRR∈PIR on GG, AvStrG(R)=1.875±o(1)AvStrG(R)=1.875±o(1). A comparison between PIRPIR and HCPkHCPk, the hierarchical routing strategy presented in [B. Awerbuch, A. Bar-Noy, N. Linial, D. Peleg, Improved routing strategies with succinct tables, J. Algorithms 11 (1990) 307–341.] is also given.