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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
We denote the semantics of the state as a subscript throughout the paper.
We note that the distortion also depends on the timeout parameter, χ. Using this parameter, the receiver detects whether a number of consecutive refresh messages are missed, which implies that the sender stopped refreshing messages. Hence, χ should be a function of T. Scaling λ and T does not yield the identical distortion values because χ scales with T but not with λ. However, the resulting difference is always very small (less than 0.001) as the timeout probability is very small. For clarity, we represent the performance with respect to λT. We take the same approach in the following sections as well.
Obtaining the information about these properties is beyond the scope of this paper.
Note that in this case, the state update interval λ has no effect on the confidence value. As a result, scaling λ and T yields different informed distortion values for weak state. Thus, we show the effect of these two parameters in two separate figures.
In the example scenario, we set C to the maximum distance between two points in the region A, i.e. \(C=2,000\sqrt{2}\)
References
Abouzeid, A., & Bisnik, N. (2011). Geographic protocol information and capacity deficit in mobile wireless ad hoc networks. IEEE Transactions on Information Theory, 57(8), 5133–5150.
Acer, U. G., Abouzeid, A., & Kalyanaraman, S. (2009). An evaluation of weak state mechanism design for indirection in dynamic networks. In INFOCOM.
Acer, U. G., Kalyanaraman, S., & Abouzeid, A. A. (2010). Weak state routing for large-scale dynamic networks. IEEE/ACM Transactions on Networking, 18(5), 1450–1463.
Acer, U. G., Kalyanaraman, S., & Abouzeid, A. A. (2011) DTN routing using explicit and probabilistic routing table states In Wireless Networks.
Clark, D. D. (1988). The design philosophy of the DARPA internet protocols. In SIGCOMM (pp. 106–114). ACM
Coleri, S., Cheung, S. Y., & Varaiya, P. (2004). Sensor networks for monitoring traffic. In: Allerton conference on communication, control and computing.
Grossglauser, M., & Vetterli, M. (2006). Locating mobile nodes with EASE: Learning efficient routes from encounter histories alone. IEEE/ACM Transactions on Networking, 14(3), 457–469.
Guo, S., Falaki, M. H., Oliver, E. A., Rahman, S. U., Seth, A., Zaharia, M. A., et al. (2007). Design and implementation of the kiosknet system. In International conference on information technologies and development.
Ji, P., Ge, Z., Kurose, J., & Towsley, D. (2007). A comparison of hard-state and soft-state signaling protocols. IEEE/ACM Transactions on Networking, 15(2), 281–294.
Keshav, S. (2006). Efficient and decentralized computation of approximate global state. Computer Communication Review, 36(1), 69–74.
Kumar, A., Xu, J., & Zegura, E. W. (2005). Efficient and scalable query routing for unstructured peer-to-peer networks. In INFOCOM.
Li, J., Jannotti, J., De Couto, D., Karger, D., & Morris, R. (2000). A scalable location service for geographic ad hoc routing. In MobiCom.
Liang, B., & Haas, Z. J. (2003). Predictive distance-based mobility management for multidimensional pcs networks. IEEE/ACM Transactions on Networking, 11, 718–732.
Lindgren, A., Doria, A., & Schelen, O. (2004). Probabilistic routing in intermittently connected networks. In First international workshop on service assurance with partial and intermittent resources (SAPIR).
Lui, J. C. S., Misra, V., & Rubenstein, D. (2004). On the robustness of soft state protocols. In International conference on network protocols, ICNP.
Manfredi, V., Crovella, M., & Kurose, J. (2011) Understanding stateful vs stateless communication strategies for ad hoc networks. In MobiCom (pp. 313–324).
Oppenheim, A. V., Willsky, A. S., & Nawab, S. H. (1996). Signals & systems (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall, Inc.
Papoulis, A., & Pillai, U. S. (2001). Probability, random variables and stochastic processes. McGraw-Hill Science/Engineering/Math, December.
Perkins, C. E., & Royer, E. (1999). Ad-hoc on-demand distance vector routing. In IEEE WMCSA.
Piorkowski, M., Raya, M., Lugo, A., Papadimitratos, P., Grossglauser, M., & Hubaux, J.-P. (2008). TraNS: Realistic joint traffic and network simulator for VANETs. ACM SIGMOBILE Mobile Computing and Communications Review, 12(1), 31–33.
Raman, S., & McCanne, S. (1999). Model, analysis, and protocol framework for soft state-based communication. Computer Communication Review, 29(4), 15–25.
Richard, C., Perkins, C., & Westphal, C. (2005). Defining an optimal active route timeout for the AODV routing. In SECON.
Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant Nos. 0627039 and 0322956.
Author information
Authors and Affiliations
Corresponding author
Additional information
An earlier version of this paper appeared in Infocom’09 [2].
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Acer, U.G., Kalyanaraman, S. & Abouzeid, A.A. Weak state versus strong state: an analysis of a probabilistic state mechanism for dynamic networks. Wireless Netw 20, 639–654 (2014). https://doi.org/10.1007/s11276-013-0618-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11276-013-0618-5