Hop-by-Hop Routing with Node-Dependent Topology Information

This paper is focused on the problem of hop-by-hop routing in a network where different nodes have different views of the network topology. In particular, each node may be aware of just a subset of the network links, perceiving the rest as if their cost was infinite. We formalize the idea of node's individual view of the network with the concept of visibility sets and introduce a routing approach based on the notion of a feasible path, i.e., such path in the node's visibility set that satisfies certain specified restrictions. It is shown that, in a network with general visibility sets, forwarding the packet along an optimal feasible path is necessary and sufficient to guarantee its eventual delivery to destination without being dropped or routed to the same node twice. Based on the proposed approach, we derive the precise routing policy and formulate an efficient algorithm to search for a family of one-to-all optimal feasible paths in a network with embedded visibility sets. We then proceed to prove the correctness of the algorithm.