Team Members:
Ram RamanathanAbhishek SamantaTom La Porta
Background:
Consider the following problem: a multi-hop wireless network running OLSR [2] routing over 802.11 radios needs to be deployed in a roughly regular structure (Manhattan grid). Each node needs
a VoIP stream to another node (say randomly chosen) and is active 20% of the time. Roughly how many nodes N can one deploy?
Such a question, with straightforward variations, may arise in a deploying a wireless network in diverse situations: deploying instant infrastructure after a disaster, a community mesh network in a
rural area, a military infrastructure-less network, a sensor network, etc. Often, the answer does not need to be precise, but quick, and for a wide range of parameter combinations. Currently the only reasonable way available to answer such questions is to construct a simulation model and iterate over different values of N to find the upper bound. Not only does this take a prohibitively long time when N is large, but also requires re-running over again to answer follow up questions: what if we used a faster radio, or used different protocols in place of OLSR and 802.11, or a different encoding for VoIP is used? What if it is a different topology or a different traffic pattern? Last, but not least, simulations do not provide insight into the relationships between parameters.
Analytical modeling appears a natural fit. However, much of the analytical research thus far has been along asymptotic lines (e.g [3, 4, 5, 6]). While these have provided tremendous insight in the limiting case, asymptotic scalability has limited applicability to finite real-world networks. A network may be asymptotically unscalable, yet scale comfortably to the requisite number of nodes in a given deployment. Further, such work does not consider control protocols, bottleneck phenomena, and the multiplicity of traffic types that are an inherent part of real-world systems.
Goal:
The goal of this project was to deliver a model of a wireless network in a closed form equation. The variable of the equation being various network parameters.
Publication:
[ Ram Ramanathan, Abhishek Samanta, and Tom La Porta. Symptotics: a framework for analyzing the scalability of real-world wireless networks, in PE-WASUN 2012. ]
References:
[1] [ G. R. Morrow. Proclus: A commentary on the first book of Euclid’s Elements, Princeton University Press, 1970.]
[2] [ T. Clausen and P. Jacquet. Optimized link state routing, in IETF RFC 3626, 2003.]
[3] [ P. Gupta and P. R. Kumar The capacity of wireless networks, in IEEE Transactions on Information Theory, vol. 46, pp. 388–404, 2000.]
[4] [ M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks, in IEEE/ACM Transactions on Networking, vol. 10, pp. 477–486, 2002.]
[5] [ M. Franceschetti, O. Dousse, D. N. C. Tse, and P. Thiran. Closing the gap in the capacity of wireless networks via percolation theory, in Information Theory, IEEE Transactions on, vol. 53, pp. 1009-1018, March 2007.]
[6] [ A. Ozgur, O. Leveque, and D. N. C. Tse. Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks, in IEEE Trans. Inf. Theory, vol. 53, pp. 3549 - 3572, 2007.]
[7] [ S. Yi, Y. Pei, and S. Kalyanaraman. On the capacity improvement of ad hoc wireless networks using directional antennas , in 4th ACM MobiHoc, pp. 108 - 116, 2003.]
[8] [ F. Penna, R. Garello, D. Figlioli, and M. Spirito. Exact non-asymptotic threshold for eigenvalue-based spectrum sensing, in Proc. CROWNCOM ’09, pp. 1 - 5, June 2009]
[9] [ J. Liebeherr, A. Burchard, and F. Ciucu, “Non-asymptotic delay bounds for networks with heavy-tailed traffic,” in Proc. IEEE INFOCOM, pp. 1 - 9, March 2010.]
[10] [ G. Bianchi. Performance analysis of the ieee 802.11 distributed coordination function, Selected Areas in Communications, IEEE Journal on, vol. 18, pp. 535 –547, mar 2000.]
[11] [ J. Jangeun, P. Peddabachagari, and M. Sichitiu. Theoretical maximum throughput of ieee 802.11 and its applications , in Proceeding of NCA 2003, June 2003]
[12] [ A. Jindal and K. Psounis. The achievable rate region of 802.11-scheduled multihop networks, in IEEE/ACM Transaction of Network, vol. 17, pp. 1118–1131, August 2009.]
[13] [ A. Jindal and K. Psounis. The achievable rate region of 802.11-scheduled multihop networks, in IEEE/ACM Trans. of Netw., vol. 17, pp. 1118–1131, August 2009.]
[14] [ D. Nguyen and P. Minet. Analysis of mpr selection in the olsr protocol, in Advanced Information Networking and Applications Workshops, 2007, AINAW ’07. 21st International Conference on,
vol. 2, pp. 887 –892, may 2007.]
[15] [ G. Mergen and L. Tong. Stability and capacity of regular wireless networks, in Information Theory, IEEE Transactions on, vol. 51, pp. 1938 – 1953, June 2005.]
[16] [ G. Barrenetxea, B. Berefull-Lozano, and M. Vetterli. Lattice networks: capacity limits, optimal routing, and queueing behavior, in IEEE/ACM Trans. Netw., vol. 14, pp. 492–505, June 2006.]
[17] [ N. Zhang and A. Anpalagan. Sensitivity of swan qos model in manets with proactive and reactive routing: a simulation study, in Telecommunication Systems, vol. 44, pp. 17–27, 2010.]
[18] [ J. S. Baras, S. Perumal, V. Tabatabaee, K. Somasundaram, and P. Purkayastha. Loss network models and multiple metric performance sensitivity analysis for mobile wireless multi-hop
networks, in Proc. WICON ’08, 2008.]
[19] [ W. Stein et al., Sage Mathematics Software (Version 4.7.2). The Sage Development Team, 2011. http://www.sagemath.org.]
[20] [ M. Gast. 802.11 Wireless Networks: A Definitive Guide. O’Reilly Publications, 2005.]
[21] [ S. Ramanathan. A unified framework and algorithm for channel assignment in wireless networks, Wirel. Netw., vol. 5, pp. 81–94, March 1999.]
[22] [C. Young. Usap: A unifying dynamic distributed multichannel tdma slot assignment protocol, in Proc. IEEE MILCOM, Oct 1996.]
[23] [Q. Chen, F. Schmidt-Eisenlohr, D. Jiang, M. Torrent-Moreno, L. Delgrossi, and H. Hartenstein. Overhaul of ieee 802.11 modeling and simulation in ns-2, in Proceedings of MSWiM ’07, pp. 159–168, 2007]
[24] [Tech info: Voip codecs. Online; accessed 15-January-2012]