Mobile network estimation

ABSTRACT

Mobile systems must adapt their behavior to changing network conditions. To do this, they must accurately estimate available network capacity. Producing quality estimates is challenging because network observations are noisy, particularly in mobile, ad hoc networks. Current systems depend on simple, exponentially-weighted moving average (EWMA) filters. These filters are either able to detect true changes quickly or to mask observed noise and transients, but cannot do both. In this paper, we present four filters designed to react quickly to persistent changes while tolerating transient noise. Such filters are agile when possible, but stable when necessary, adapting their behavior to prevailing conditions. These filters are evaluated in a variety of networking situations, including persistent and transient change, congestion, and topology changes. We find that one filter, based on techniques from statistical process control provides performance superior to the other three. Compared to two EWMA filters, one agile and the other stable, it is able to offer the agility of the former in four of five scenarios and the stability of the latter in three of four scenarios.

REFERENCES

• 1: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 2: J.-C. Bolot. Characterizing end-to-end packet delay and loss behavior in the Internet. Journal of High Speed Networks, 2(3):305-23, 1993.
• 3: Lee Breslau , Deborah Estrin , Kevin Fall , Sally Floyd , John Heidemann , Ahmed Helmy , Polly Huang , Steven McCanne , Kannan Varadhan , Ya Xu , Haobo Yu, Advances in Network Simulation, Computer, v.33 n.5, p.59-67, May 2000 [doi>10.1109/2.841785]
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: R. B. Brown and P. Y.C.Hwang. Introduction ot Random Signals and Applied Kalman Filtering. John Wiley & Sons, Inc., 1997.
• 6: Robert L. Carter , Mark E. Crovella, Server Selection Using Dynamic Path Characterization in Wide-Area Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1014, April 09-11, 1997
• 7: Allen B. Downey, Using pathchar to estimate Internet link characteristics, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.241-250, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 8: D. Duchamp. Issues in wireless mobile computing. In Proceedings of the Third Workshop on Workstation Operating Systems, pages 2-10, Key Biscayne, FL, USA, April 1992.
• 9: A. Gelb. Applied Optimal Estimation. M.I.T. Press, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1974.
• 10: IEEE. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Std 802.11-1999.
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, T. Imielinski and H. Korth, editors. Chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
• 13: R. H. Katz. Adaptation and mobility in wireless information systems. IEEE Personal Communications, 1(1):6-17, 1994.
• 14: R. H. Katz and E. A. Brewer. The case for wireless overlay networks. In Proceedings 1996 SPIE Conference on Multimedia and Networking, pages 77-88, San Jose, CA, January 1996.
• 15: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 16: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
• 17: K. Lai and M. Baker. Measuring bandwidth. In Proceedings of INFOCOM '99, pages 235-45, New York, NY, USA, March 1999.
• 18: Kevin Lai , Mary Baker, Measuring link bandwidths using a deterministic model of packet delay, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.283-294, August 28-September 01, 2000, Stockholm, Sweden
• 19: S. Low. Traffic management of ATM networks: service provisioning, routing, and traffic shaping. PhD thesis, University of California, Berkeley, 1992.
• 20: D. C. Montgomery. Introduction to statistical quality control. John Wiley & Sons, Inc., 3rd edition, 1997.
• 21: Brian D. Noble , M. Satyanarayanan , Dushyanth Narayanan , James Eric Tilton , Jason Flinn , Kevin R. Walker, Agile application-aware adaptation for mobility, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.276-287, October 05-08, 1997, Saint Malo, France
• 22: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 23: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 24: S. E. Rigdon, E. N. Cruthis, and C. W. Champ. Design strategies for individuals and moving range control charts. Journal of Quality Technology, 26(4):274-87, October 1994.
• 25: U. Schmid and W. A. Halang. Synchronized UTC for distributed real-time systems. In Proceedings of the IFAC Workshop on Real Time Programming, pages 101-107, Pergamon, Oxford, UK, June 1994.
• 26: Western Electric. Statistical Quality Control Handbook. Western Electric Corporation, Indianapolis, Inc., 1956.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Cellular architecture (e.g., mobile)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Measurement, Performance

Keywords:
adaptive systems, filtering, mobile network estimation