Analysis of Latency of Stateless Opportunistic Forwarding in Intermittently Connected Networks

• Published in: IEEE/ACM transactions on networking 2011-08, Vol.19 (4), p.1111-1124
• Main Authors: Chi-Kin Chau, Basu, P.
• Format: Article
• Language: English
• Subjects: Availability; Eigenvalues and eigenfunctions; Fault tolerance; Graph theory; Intermittently connected networks; Markov processes; Mathematical analysis; Mathematical models; Nearest neighbor searches; Network topology; Networks; opportunistic forwarding; Packets (communication); Peer to peer computing; Random walk; random walk in finite graphs; Random walk theory; Searching; spectral graph theory; Statelessness; Studies; Symmetric matrices
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2010.2103321

Stateless opportunistic forwarding is a simple fault-tolerant distributed scheme for packet delivery, data gathering, and information querying in intermittently connected networks by which packets are forwarded to the next available neighbors in a "random walk" fashion until they reach their intended destinations or expire. It has been employed in diverse situations, for instance, when: 1) the global network topology is not known or is highly dynamic; 2) the availability of the next-hop neighbors is not easily controllable; or 3) the relaying nodes are computationally constrained. Data delivery in sensor networks, ad hoc networks, and delay-tolerant networks are well-known applications besides searching in peer-to-peer networks. A major challenge for stateless opportunistic forwarding is the difficulty to predict the end-to-end latency. To facilitate latency evaluation, we study a simplified model of stateless opportunistic forwarding, namely a "weighted random walk" in a finite graph. This paper makes several contributions toward the analysis of this model. 1) By spectral graph theory we derive a general formula to efficiently compute the exact hitting and commute times of random walks with heterogeneous transition times at relay nodes. Such transition times can model the heterogeneous delivery times and availability periods of the next-hop neighbors. 2) We study a common class of distance-regular networks with a varying number of geographical neighbors and obtain exact and approximation formulas for the hitting time in such networks. 3) Based on these results, we study other sophisticated settings, such as random geographical locations, topology-aware forwarding, and multicopy random-walk forwarding. Our results provide the basic analytical tools for managing and controlling the performance of stateless opportunistic forwarding in finite networks.