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 their destinatio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on vehicular technology 2005-07, Vol.54 (4), p.1473-1487
Main Authors: Shavitt, Y., Shay, A.
Format: Article
Language:English
Subjects:
Access methods and protocols, osi model
Algorithms
Applied sciences
Communication networks
Computer networks
Costs
Dynamic programming
Exact sciences and technology
Floating car data
Intelligent networks
Mathematical analysis
Mathematical models
Mobile agents
Mobile communication
Networks
online decision problem
Optimization
Peer to peer computing
peer to peer networks
Policies
Road vehicles
Routing
Routing (telecommunications)
shortest path
Stochastic processes
Studies
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
transportation network
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 their 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. We show that ordinarily gossiping helps travelers decrease their expected path cost. However, in some scenarios, depending on the network parameters, gossiping could increase the expected path cost. The parameters that determine the effect of gossiping on the path costs are identified and their influence is analyzed. This dependency is fairly complex and was confirmed numerically on grid networks.
ISSN:0018-9545
1939-9359
DOI:10.1109/TVT.2005.851351