Network deformation: traffic-aware algorithms for dynamically reducing end-to-end delay in multi-hop wireless networks

ABSTRACT

We present two centralized algorithms that dynamically deform the topology of a multi-hop wireless network in response to changing traffic conditions, so as to reduce the end-to-end packet delay. These algorithms operate by reducing an easily calculable traffic-and-topology-dependent metric that has strong positive correlation to the mean end-to-end network delay. This makes it possible to change the network topology in real time. The first algorithm involves moving existing nodes to create new links, while the second involves adding a new node to the existing network. The new links are added judiciously between nodes with the most traffic fluctuations, in a way that often decreases the total number of network links. Multiple simulations on the original and the deformed networks using the \ns simulator demonstrate that the reductions in end-to-end delay are significantly higher than with the alternative approach of increasing the capacities of the most congested links.

REFERENCES

• 1: 3rd Generation Partnership Project. 3GPP Technical Specification Group Radio Access Network. TS 25.214: Physical Layer Procedures (FDD), 2000.
• 2: A. Basu, D. Dutta, and S. Ramanathan. Characteristic Timescales: Analyzing End-to-end Delay in Networks under High Loads. Bell Laboratories Technical Memorandum ITD-03-44953M, 2004. Available from http://cm.bell-labs.com/cm/cs/doc/04/timescales.pdf.
• 3: P. Bender, P. Black, M. Grob, R. Padovani, N. Sindhusayana, and A. Viterbi. CDMA/HDR: A Bandwidth-efficient High Speed Wireless Data Service for Nomadic Data Users. IEEE Communications Magazine, 38(7):70--77, 2000.
• 4: Jin Cao , William S. Cleveland , Dong Lin , Don X. Sun, On the nonstationarity of Internet traffic, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.102-112, June 2001, Cambridge, Massachusetts, United States
• 5: R. L. Cruz and A. V. Santhanam. Optimal Routing, Link Scheduling and Power Control in Multi-hop Wireless Networks. In Proceedings of Infocom '03, San Francisco, CA, March-April 2003.
• 6: E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1:269--271, 1959.
• 7: C. Eklund, R. B. Marks, K. L. Stanwood, and S. Wang. IEEE Standard 802.16: A Technical Overview of The WirelessMAN™ Air Interface for Broadband Wireless Access. IEEE Communications Magazine, 40(6):98--107, June 2002.
• 8: WLAN Mesh Networking. White Paper, Firetide Networks, Honolulu HI, 2003.
• 9: M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
• 10: David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989481]
• 11: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 12: B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory, 34(5):910--917, September 1988.
• 13: William C. Jakes , Donald C. Cox, Microwave Mobile Communications, Wiley-IEEE Press, 1994
• 14: B. Anthony Kadrovach , Gary B. Lamont, A particle swarm model for swarm-based networked sensor systems, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508968]
• 15: Aman Kansal , Arun A. Somasundara , David D. Jea , Mani B. Srivastava , Deborah Estrin, Intelligent fluid infrastructure for embedded networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990080]
• 16: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 17: M2M Magazine. http://www.m2mmag.com/.
• 18: David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, New York, NY, 2002
• 19: The Mathworks: MATLAB and Simulink for Technical Computing. http://www.mathworks.com/.
• 20: Mesh Networks. http://www.meshnetworks.com/.
• 21: NextWeb Wireless Internet Access. http://www.nextweb.net/.
• 22: Nokia RoofTop Wireless Routing. White Paper, Nokia Wireless Broadband, Mountain View, CA, 2001.
• 23: The Network Simulator --- ns-2. http://www.isi.edu/nsnam/ns/.
• 24: R. K. Pathria. Statistical Mechanics. Pergamon Press, New York, NY, 1972.
• 25: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 26: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 27: M. B. Priestley. Spectral Analysis of Time Series. Academic Press, London, UK, June 1981.
• 28: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 29: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]
• 30: Rocketfuel: An ISP Topology Mapping Engine. http://www.cs.washington.edu/research/networking/rocketfuel/.
• 31: J. J. Sakurai. Modern Quantum Mechanics. Benjamin Cummings, San Francisco, CA, 2nd edition, 1994.
• 32: C. E. Shannon. A Theorem on Coloring The Lines of A Network. Journal of Mathematical Physics, 28:148--151, 1949.
• 33: Strix Access/One Product Description Brochure. Strix Systems, Westlake Village, CA, 2003.
• 34: Gordon L. Stüber, Principles of mobile communication (2nd ed.), Kluwer Academic Publishers, Norwell, MA, 2001
• 35: Wisper Telecommunications. http://www.wispertel.com.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms

Keywords:
deformation, end-to-end delay, multi-hop, topology, traffic-aware, wireless networks