Weak state versus strong state: An analysis of a probabilistic state mechanism for dynamic networks

Abstract

Network protocols coordinate their decision making using information about entities in remote locations. Such information is provided by state entries. To remain valid, the state information needs to be refreshed via control messages. When it refers to a dynamic entity, the state has to be refreshed at a high rate to prevent it from becoming stale. In capacity constrained networks, this may deteriorate the overall performance of the network. The concept of weak state has been proposed as a remedy to this problem in the context of routing in mobile ad-hoc networks. Weak state is characterized by probabilistic semantics and local refreshes as opposed to strong state that is interpreted as absolute truth. A measure of the probability that the state remains valid, i.e. confidence, accompanies the state. The confidence is decayed in time to adapt to dynamism and to capture the uncertainty in the state information. This way, weak state remains valid without explicit state refresh messages. We evaluate the consistency of weak state and strong state using two notions of distortion. Pure distortion measures the average difference between the actual value of the entity and the value that is provided by the remote state. Informed distortion captures both this difference and the effect of confidence value on state consistency. Using a mathematical analysis and simulations, we show that weak state reduces the distortion values when it provides information about highly dynamic entities and/or it is utilized for protocols that is required to incur a low amount of overhead. © 2013 Springer Science+Business Media New York.