Dynamic packet fragmentation for wireless channels with failures

ABSTRACT

It was shown recently [7-9], under quite general conditions, that retransmission-based protocols may result in power-law delays and possibly zero throughput even if the distribution of packets (data units) is very concentrated, e.g., exponential or Gaussian. This phenomenon occurs irrespective of whether the cause of retransmissions is due to channel failures in the data link layer [7] or collisions in ALOHA-type protocols in the MAC layer [9]. These theoretical findings are in agreement with empirical measurements in [18], showing that the utilization of the 802.11 protocol is only 40%, basically due to retransmissions.

In order to alleviate this problem, we propose a new dynamic packet fragmentation algorithm that can adaptively match channel failure characteristics. This algorithm is based on the mathematical insights developed in [7, 8]. As a first order approximation to the channel dynamics, we assume that the channel is either available for a period of time or unavailable. Then, our fragmentation algorithm divides the original packets into smaller ones whose size is bounded by the kth largest value among the last k+m channel availability periods. We also discuss mechanisms for aggregating smaller packets into larger ones, which, in combination with fragmentation, can further improve the performance.

Under the renewal assumptions on the channel dynamics, we prove that our fragmentation method results in k additional moments for the total transmission time until all the fragments are successfully transmitted, i.e., the transmission time has a much more concentrated distribution and, in particular, the channel will always have a positive throughput. In addition, we argue that by tuning the parameter m, the number of introduced new packets can be kept reasonably small as well. Furthermore, we demonstrate through simulations that the superior performance of our fragmentation algorithm extends beyond the renewal assumptions used in the analysis to time varying and/or correlated channels. For practical implementation of the algorithm, we also discuss approaches to measuring the channel availability periods, especially in situations when the channel dynamics may not be directly observable.

It is worth mentioning that our algorithm can be used for designing efficient checkpointing schemes in other systems that are prone to failures, e.g., distributed computing systems.

REFERENCES

• 1: S. Asmussen, P. Fiorini, L. Lipsky, T. Rolski, and R. Sheahan. Asymptotic behavior of total times for jobs that must start over if a failure occurs. Juen 2007, preprint; Mathematics of Operations Research, to appear.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: E. G. Coffman, Jr. , Leopold Flatto , Paul E. Wright, A stochastic checkpoint optimization problem, SIAM Journal on Computing, v.22 n.3, p.650-659, June 1993 [doi>10.1137/0222043]
• 4: Pierre M. Fiorini , Robert Sheahan , Lester Lipsky, On unreliable computing systems when heavy-tails appear as a result of the recovery procedure, ACM SIGMETRICS Performance Evaluation Review, v.33 n.2, p.15-17, September 2005 [doi>10.1145/1101892.1101898]
• 5: Predrag R. Jelenkovic , Xiaozhu Kang , Jian Tan, Adaptive and scalable comparison scheduling, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 6: P. R. Jelenkovic, X. Kang, and J. Tan. Heavy-tailed limits for medium size jobs and comparison scheduling. Annals of Operations Research, Special Issue on Stochastic Performance Models for Resource Allocation in Communication Systems, 2008, to appear.
• 7: P. R. Jelenkovic and J. Tan. Can retransmissions of superexponential documents cause subexponential delays? In Proceedings of IEEE INFOCOM'07, Anchorage, Alaska, USA, May 2007.
• 8: P. R. Jelenkovic and J. Tan. Characterizing heavy-tailed distributions induced by retransmissions. Technical report, Department of Electrical Engineering, Columbia University, EE2007-09-07, September 2007. Eprint arXiv: 0709.1138v2.
• 9: P. R. Jelenkovic and J. Tan. Is ALOHA causing power law delays? In Proceedings of the 20th International Teletraffic Congress, Ottawa, Canada, June 17-21 2007.
• 10: C. A. Kent and J. C. Mogul. Fragmentation considered harmful. Proceedings of ACM SIGCOMM, August 1987.
• 11: V. Kulkarni, V. Nicola, and K. Trivedi. The completion time of a job on a multimode system. Advances in Applied Probability, 19(4):932--954, December 1987.
• 12: Eytan Modiano, An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols, Wireless Networks, v.5 n.4, p.279-286, July 1999 [doi>10.1023/A:1019111430288]
• 13: S. V. Nagaev. Large deviations of sums of independent random variables. The Annals of Probability, 7(5):745--789, 1979.
• 14: A. Orda and R. Rom. Optimal packet fragmentation and routing in computer networks. Networks, 29(1):11--28, December 1998.
• 15: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 16: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 17: Tahiry Razafindralambo , Isabelle Guérin Lassous , Luigi Iannone , Serge Fdida, Dynamic packet aggregation to solve performance anomaly in 802.11 wireless networks, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain [doi>10.1145/1164717.1164761]
• 18: Maya Rodrig , Charles Reis , Ratul Mahajan , David Wetherall , John Zahorjan, Measurement-based characterization of 802.11 in a hotspot setting, Proceedings of the 2005 ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080148.1080150]
• 19: Robert Sheahan , Lester Lipsky , Pierre Fiorini, The Effect of Different Failure Recovery Procedures on the Distribution of Task Completion Times, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 16, p.282.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.426]
• 20: Robert Sheahan , Lester Lipsky , Pierre M. Fiorini , Søren Asmussen, On the completion time distribution for tasks that must restart from the beginning if a failure occurs, ACM SIGMETRICS Performance Evaluation Review, v.34 n.3, December 2006 [doi>10.1145/1215956.1215967]
• 21: J. Shoch. Packet fragmentation in Inter-network protocols. Computer Networks, 3(1):3--8, 1979.
• 22: J. Tourrilhes. Fragment adaptive reduction: coping with various interferers inradio unlicensed bands. IEEE ICC 2001, 1:239--244, June 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Performance, Theory

Keywords:
channel with failures, checkpoints, dynamic fragmentation, heavy-tailed distributions, light-tailed distributions, packet fragmentation, power laws, retransmissions, time varying channel, wireless ad-hoc/sensor networks