Online Routing in Faulty Mesh Networks
Stefan Ruhrup, University of Paderborn, Germany
In this talk we consider the following online route discovery problem:
Given a two-dimensional mesh network with faulty nodes. The number and
the position of the faulty nodes are not known in advance and there is
no restriction on the size or the shape of the faulty blocks. Now, the
problem is to find a path from a given source node to a target node.
With a flooding strategy like expanding ring search the time to reach
the target is linear in the minimum number of steps d, but the traffic
(the total number of messages) grows quadratically - regardless of the
presence of faulty nodes. Single-path strategies for essentially the
same problem have been developed in the field of geographic routing and
online navigation. Optimal single-path strategies include a traversal
of
the faulty blocks and produce a traffic of O(d + p), where p is the
perimeter of the faulty blocks (i.e. the number of nodes adjacent to
faulty nodes). Unfortunately, the time to discover the path is also O(d
+ p). Both approaches, flooding and single-path route discovery, fail
to
optimize time and traffic at the same time.
We present a multi-path online routing algorithm that finds a path in
time O(d) with traffic O(d + p log^2 d). This algorithm is
asymptotically as fast as flooding and nearly traffic-optimal up to a
poly-logarithmic factor.