Faculty of Engineering and Natural Sciences
Weak State and Its Evaluation for Large Scale Dynamic Networks
Utku Günay Acer
Routing protocols in communication networks rely on routing table entries (“states”) to make decisions on how to forward packets. When paths to a destination node change, the corresponding states become invalid and need to be refreshed with control messages. In large and highly dynamic networks, this overhead can crowd out capacity for data traffic. If the network is intermittently connected, source-destination pairs may never be connected by a complete path. In this case, it is not even possible to refresh routing table states at remote nodes and the routing protocols cannot use valid and explicit state information to perform routing.
For such large scale, dynamic networks in which refreshing routing state is not feasible or possible, we propose the concept of weak state. Weak state is interpreted as a probabilistic hint, not as absolute truth. Weak state can remain valid without explicit messages, by systematically reducing the confidence in its accuracy. We build routing protocols using the concept of weak state for connected yet dynamic Mobile Ad-hoc Networks (MANETs) and intermittently connected Delay Tolerant Networks (DTNs).
For MANETs, Weak State Routing (WSR) is a novel routing protocol that uses weak state along with random directional walks for forwarding packets. When a packet reaches a node, and the routing state at the node has higher confidence about the destination than that held by the packet, the walk direction is biased. The packet reaches the destination via a sequence of directional walks, punctuated by biasing decisions. WSR also uses random directional walks for disseminating routing state, and provides mechanisms for aggregating weak state.
In DTNs, routing is achieved by the “store-carry-forward” paradigm. Our proposition Weak State Routing protocol for Delay Tolerant Networks (WSR-D) exploits the direction of node mobility along with the explicit information provided by weak state. A node receives a packet only if it is moving towards the region where the destination node is believed to be located. WSR-D disseminates weak state using a local osmosis mechanism, where nodes exchange information about the network opportunistically in node contacts. Weak state concept is particularly useful for DTNs because it allows to maintain valid state information without depending upon external control messages.
Our simulation results show that WSR offers a very high packet delivery ratio (_ 98%). Control traffic overhead scales as O(N) and the state complexity is _(N3/2), where N is the number of nodes. Packets follow longer paths compared to prior protocols but the average path length is asymptotically efficient and scales as O(pN). Despite longer paths, WSR’s end-to-end packet delivery delay is much smaller due to the dramatic reduction in protocol overhead. WSR-D on the other hand, in comparison to protocols that use no information or implicit information to perform routing in DTNs, deliver a higher portion of the packets with smaller average delays and causing much less message transfer, increasing the network goodput.
We also investigate the effect of state weak-ness on the consistency of state information. We define two metrics,pure distortion and informed distortion, to evaluate the consistency of the weak state paradigm and compare it against strong state (i.e. deterministic state that relies on explicit refresh messages to remain valid). Pure distortion measures the average gap between the actual value of the state and the value maintained at a remote node. On the other hand, the use of confidence increases the protocol’s ability to cope with even large pure distortion. The resulting effective distortion is captured by the informed distortion metric. We analytically show that weak state causes significantly less distortion values than strong state.
Bio:Utku Günay Acer is a post-doctoral research fellow in Institut National de Recherche en Informatique et en Automatique (INRIA), Sophia Antipolis, France. He received the B.S. degree with high honors from Sabancı University, Turkey in 2004, and the M.S. and Ph.D. degrees from Rensselaer Polytechnic Institute (RPI), Troy, NY, USA in 2005 and 2009, respectively. His current research interests include performance evaluation and protocol design for variable topology networks with an emphasis on large scale ad-hoc and disruption tolerant networks.
September 3, 2009, 13:40, FENS 2019