Optimal Routing in Gossip Networks

In this paper we introduce the Gossip Network model where travelers can obtain information about the state of dynamic networks by gossiping with peer travelers using ad-hoc communication. Travelers then use the gossip information to recourse their path and find the shortest path to destination. We study optimal routing in stochastic, time independent gossip networks, and demonstrate that an optimal routing policy may direct travelers to make detours to gather information. A dynamic programming equation that produces the optimal policy for routing in gossip networks is presented. In general the dynamic programming algorithm is intractable; however for two special cases a polynomial optimal solution is presented