An empirical study of bandwidth predictability in mobile computing

ABSTRACT

While bandwidth predictability has been well studied in static environments, it remains largely unexplored in the context of mobile computing. To gain a deeper understanding of this important issue in the mobile environment, we conducted an eight-month measurement study consisting of 71 repeated trips along a 23Km route in Sydney under typical driving conditions. To account for the network diversity, we measure bandwidth from two independent cellular providers implementing the popular High-Speed Downlink Packet Access (HSDPA) technology in two different peak access rates (1.8 and 3.6Mbps). Interestingly, we observe no significant correlation between the bandwidth signals at different points in time within a given trip. This observation eventually leads to the revelation that the popular time series models, e.g. the Autoregressive and Moving Average, typically used to predict network traffic in static environments are not as effective in capturing the regularity in mobile bandwidth. Although the bandwidth signal in a given trip appears as a random white noise, we are able to detect the existence of patterns by analyzing the distribution of the bandwidth observed during the repeated trips. We quantify the bandwidth predictability reflected by these patterns using tools from information theory, entropy in particular. The entropy analysis reveals that the bandwidth uncertainty may reduce by as much as 46% when observations from past trips are accounted for. We further demonstrate that the bandwidth in mobile computing appears more predictable when location is used as a context. All these observations are consistent across multiple independent providers offering different data transfer rates using possibly different networking hardware.

REFERENCES

• 1: "High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2." {Online}. Available: http://www.3gpp.org/ftp/specs/html-info/25308.htm
• 2: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 3: Yi Qiao , Jason Skicewicz , Peter Dinda, An Empirical Study of the Multiscale Predictability of Network Traffic, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, p.66-76, June 04-06, 2004 [doi>10.1109/HPDC.2004.3]
• 4: A. Sang and S. Q. Li, "A Predictability Analysis of Network Traffic," in Proc. of IEEE Infocom 2000, Tel Aviv, Israel, Mar. 2000.
• 5: J. Zhang and I. Marsic, "Link Quality and Signal-to-Noise Ratio in 802.11 WLAN with Fading: A Time-Series Analysis," in Proc. of Vehicular Technology Conference 2006 Fall, Montreal, Canada, Sep. 2006.
• 6: J. P. Singh, T. Alpcan, P. Agarwal, and V. Sharma, "An Optimal Flow Assignment Framework for Heterogeneous Network Access," in Proc. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2007), Helsinki, Finland, Jun. 2007.
• 7: J. Derksen, R. Jansen, M. Maijala, and E. Westerberg, "HSDPA Performance and Evolution," Ericsson Review, no. 03, pp. 117--120, 2006.
• 8: K. Mattar, A. Sridharan, H. Zang, I. Matta, and A. Bestavros, "TCP Over CDMA2000 Networks : A Cross-Layer Measurement Study," in Proc. of PAM 2007, Louvain-la-neuve, Belgium, Apr. 2007.
• 9: W. L. Tan, F. Lam, andW. C. Lau, "An Empirical Study on 3G Network Capacity and Performance," in Proc. of IEEE Infocom 2007, Anchorage, Alaska, USA, May 2007.
• 10: Y. Lee, "Measured TCP Performance in CDMA1x EV-DO Network," in Proc. of PAM 2006, Adelaide, Australia, Mar. 2006.
• 11: Pablo Rodriguez , Rajiv Chakravorty , Julian Chesterfield , Ian Pratt , Suman Banerjee, MAR: a commuter router infrastructure for the mobile Internet, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990091]
• 12: Vladimir Bychkovsky , Bret Hull , Allen Miu , Hari Balakrishnan , Samuel Madden, A measurement study of vehicular internet access using in situ Wi-Fi networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161097]
• 13: J. Ött and D. Kutscher, "Drive-thru Internet: IEEE 802.11b for Automobile Users," in Proc. of IEEE Infocom 2004, Hong Kong, China, Mar. 2004.
• 14: N. Gershenfeld, Signal entropy and the thermodynamics of computation, IBM Systems Journal, v.35 n.3-4, p.577-586, 1996
• 15: Jean-Marc François , Guy Leduc, Entropy-based knowledge spreading and application to mobility prediction, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France [doi>10.1145/1095921.1095924]
• 16: A. Bhattacharya and S. K. Das, "LeZi-Update: An Information-Theoretic Framework for Personal Mobility Tracking in PCS Networks," in Proc. of ACM MobiCom 1999, Seattle, Washington, USA, Aug. 1999.
• 17: Constantinos Dovrolis , Parameswaran Ramanathan , David Moore, Packet-dispersion techniques and a capacity-estimation methodology, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.963-977, December 2004 [doi>10.1109/TNET.2004.838606]
• 18: Rohit Kapoor , Ling-Jyh Chen , Li Lao , Mario Gerla , M. Y. Sanadidi, CapProbe: a simple and accurate capacity estimation technique, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 19: Mark Claypool , Robert Kinicki , William Lee , Mingzhe Li , Gregory Ratner, Characterization by measurement of a CDMA 1x EVDO network, Proceedings of the 2nd annual international workshop on Wireless internet, p.2-es, August 02-05, 2006, Boston, Massachusetts [doi>10.1145/1234161.1234163]
• 20: N. Thompson, G. He, and H. Luo, "Flow Scheduling for End-host Multihoming," in Proc. of IEEE Infocom 2006, Barcelona, Catalunya, Spain, Apr. 2006.
• 21: C. E. Shannon, "Prediction and entropy of printed English," Bell System Technical Journal, vol. 30, pp. 50--64, 1951.
• 22: T. Batu , L. Fortnow , R. Rubinfeld , W. D. Smith , P. White, Testing that distributions are close, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.259, November 12-14, 2000

INDEX TERMS

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
bandwidth predictability, entropy, information theory, measurement, mobile computing, time series