Memoryless routing in convex subdivisions: random walks are optimal
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex \(t\) for a packet currently located at vertex \(v\) is made based only on the coordinates of \(v, t\), and the neighborhood \(N(v)\) of \(v\). In this paper, the authors study the limitations of such algorithms. In particular, it is shown that, for any (randomized) memoryless routing algorithm \(\mathcal A\), there exists a convex subdivision on which \(\mathcal A\) takes \(\Omega(n^2)\) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by \textit{P. Bose} et al. in [Int. J. Comput. Geom. Appl. 12, No. 4, 283--295 (2002; Zbl 1152.68478)] and by \textit{P. Bose} and \textit{P. Morin} [SIAM J. Comput. 33, No. 4, 937--951 (2004; Zbl 1061.65014)] requires \(2^{\Omega(n)}\) time to route between some pair of vertices.
This page was built for publication: Memoryless routing in convex subdivisions: random walks are optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q419369)
