Weak state and its evaluation for routing in large scale dynamic networks.

摘要

Routing protocols in communication networks rely on routing table entries ("states") to make decisions on how to forward packets. For resilient routing, states should always be up-to-date. As the network size increases and it becomes more dynamic, most routing table entries at every router must be updated. A natural consequence is the huge increase in control traffic that crowds out the network capacity. For such large and dynamic networks, we propose to use probabilistic routing tables, where routing table entries are considered as a probabilistic hints (called weak state), and not absolute truth. We build routing protocols using the concept of weak state for mobile ad-hoc networks (MANETs) and delay tolerant networks (DTNs).;For MANETs, we propose the Weak State Routing (WSR) protocol that uses the concept of random directional walks (i.e. walks in randomly chosen directions) as a primitive both for disseminating weak state, and for forwarding packets. In particular, when a random directional walk for forwarding a packet reaches a node, it consults the weak-state at the node, and biases its walk direction if the node has stronger information (in terms of confidence) about the destination location.;In DTNs, an additional challenge is that a complete path may never exist between a source-destination pair and routing is achieved by the store-carry-forward paradigm. Intermittent connectivity also prevents the control messages from diffusing in the network. Hence, it is difficult to maintain consistent routing states. We propose Weak State Routing protocol for Delay Tolerant Networks (WSR-D) that uses explicit mappings with weak states. Weak state is particularly useful for DTNs because it has probabilistic semantics and can be refreshed locally. WSR-D disseminates weak state using a local osmosis mechanism. It employs a biasing technique similar to that of WSR. WSR-D exploits node mobility rather than node positions. A packet is forwarded to an intermediate node only if it is moving in a direction closer to the direction given by the biasing weak state.;Our simulation results show that WSR offers a high packet delivery ratio, more than 98%. Protocol overhead scales as O(N), N being the number of nodes. The state complexity of the protocol is theta(N3/2). Even though packets follow paths longer than the shortest paths, the average path length is asymptotically efficient and scales as O( N ). Despite longer paths, WSRs end-to-end packet delivery delay is much smaller than the prior work because of the dramatic reduction in control traffic overhead. WSR-D achieves very high delivery ratio even when the buffer space in the nodes is limited. It reduces the number of packet transfers between nodes in comparison to prior work at the cost of increased delay.;We also investigate the effect of state weak-ness on the consistency of 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.;In the final part of this dissertation, we investigate the random walks on dynamic time-graphs. Random walks form the basis of the unstructured methods. We investigate the effect of dynamism in the network on the random walk performance, which is a strong indicator of network connectivity. Such networks are modeled by a novel 3-mode adjacency tensor. The expected hitting time of a random walk in a dynamic network is small if the network is well connected. The representation also leads to the information whether a node can be reached by another node after a certain number of time steps, which is indicated by reachability tensor. We unfold the reachability tensor around the mode or dimension that models time to obtain a matrix. Our experiments show that the correlation between the expected hitting time and the second singular-value of this matrix is above 0.95. Hence, it is a strong indicator of network connectivity. (Abstract shortened by UMI.)