UCSC-CRL-06-17: Disruption-Tolerant Routing with Scoped Propagation of Control Information

J. Boice, J.J. Garcia-Luna-Aceves, K. Obraczka
10/25/2006 09:00 AM
Computer Engineering
We consider the problem of routing messages through a network with episodic connectivity without a priori knowledge of node schedules or locations. We present Steward Assisted Routing (StAR), an efficient loop-free routing framework that can operate in networks that are well-connected as well as in networks that exhibit intermittent connectivity; the proposed protocol uses steward nodes to deliver data to destinations that may be partitioned from the source. We also introduce a companion protocol, Scoped Contact and Interest Propagation (SCIP), which contains mechanisms with which dissemination of routing control information for destinations of interest is scoped to a well-defined region of the network. We evaluate our protocols through simulations with four distinct mobility scenarios, including two that are generated using data traces from real networks. Our results show that StAR achieves delivery rates comparable to Epidemic routing with far less signaling overhead. We also show that the addition of SCIP to StAR reduces route maintenance overhead significantly without impacting delivery rates.