Online Multi-path Routing in a Maze

摘要

We consider the problem of route discovery in a mesh network with faulty nodes. The number and the positions of the faulty nodes are unknown. It is known that a flooding strategy like expanding ring search can route a message linear in the minimum number of steps d while it causes a traffic (I.e. the total number of messages) of O(d~2). For optimizing traffic a single-path strategy is optimal producing traffic O(d+p), where p is the number of nodes that are adjacent to faulty nodes. We present a deterministic multi-path online routing algorithm that delivers a message within O(d) time steps causing traffic O{d + p log~2 d). This algorithm is asymptotically as fast as flooding and nearly traffic-optimal up to a polylogarithmic factor.