Resequencing analysis of stop-and-wait ARQ for parallel multichannel communications

ABSTRACT

In this paper, we consider a multichannel data communication system in which the stop-and-wait automatic-repeat-request protocol for parallel channels with an in-sequence delivery guarantee (MSW-ARQ-inS) is used for error control. We evaluate the resequencing delay and the resequencing buffer occupancy, respectively. Under the assumption that all channels have the same transmission rate but possibly different time-invariant error rates, we derive the probability generating function of the resequencing buffer occupancy and the probability mass function of the resequencing delay. Then, by assuming the Gilbert-Elliott model for each channel, we extend our analysis to time-varying channels. Through examples, we compute the probability mass functions of the resequencing buffer occupancy and the resequencing delay for time-invariant channels. From numerical and simulation results, we analyze trends in the mean resequencing buffer occupancy and the mean resequencing delay as functions of system parameters. We expect that the modeling technique and analytical approach used in this paper can be applied to the performance evaluation of other ARQ protocols (e.g., the selective-repeat ARQ) over multiple time-varying channels.

REFERENCES

• 1: S. S. L. Chang, "Theory of information feedback systems," IEEE Trans. Inf. Theory, vol. IT-2, pp. 29-40, 1956.
• 2: M. E. Anagnostou and E. N. Protonotarios, "Performance analysis of the selective repeat ARQ protocol," IEEE Trans. Commun., vol. COM-34, pp. 127-135, 1986.
• 3: M. Moeneclaey, H. Nruneel, I. Bruyland, and D. Y. Chung, "Throughput optimization for a generalized stop-and-wait ARQ scheme," IEEE Trans. Commun., vol. COM-34, pp. 205-207, 1986.
• 4: Z. Rosberg and N. Shacham, "Resequencing delay and buffer occupancy under the selective-repeat ARQ," IEEE Trans. Inf. Theory, vol. 35, pp. 166-173, 1989.
• 5: L. Badia, M. Rossi, and M. Zorzi, "SR ARQ packet pelay ptatistics on parkov channels in the presence of variable arrival rate," IEEE Trans. Wireless Commun., vol. 5, pp. 1639-1644, 2006.
• 6: R. Fantacci, "Queueing analysis of the selective repeat automatic repeat request protocol wireless packet networks," IEEE Trans. Veh. Technol., vol. 45, pp. 258-264, 1996.
• 7: J. G. Kim and M. K. Krunz, "Delay analysis of selective repeat ARQ for a Markovian source over a wireless channel," IEEE Trans. Veh. Technol., vol. 49, pp. 1968-1981, 2000.
• 8: L. B. Le, E. Hossain, and A. S. Alfa, "Delay statistics and throughput performance for multi-rate wireless networks under multiuser diversity," IEEE Trans. Wireless Commun., vol. 5, pp. 3234-3243, 2006.
• 9: M. Rossi, L. Badia, and M. Zorzi, "SR ARQ delay statistics on N-state Markov channels with non-instantaneous feedback," IEEE Trans. Wireless Commun., vol. 5, pp. 1526-1536, 2006.
• 10: D. Towsley, "A statistical analysis of ARQ protocols operating in a nonindependent error environment," IEEE Trans. Commun., vol. COM-29, pp. 971-981, 1981.
• 11: S. D. Vuyst, "Analysis of discrete-time queueing systems with multi-dimensional state space," Ph.D. dissertation, Gent Univ., Ghent, Belgium, 2006.
• 12: R. W. Chang, "Synthesis of band-limited orthogonal signals for multi-channel data transmission," Bell Syst. Tech. J., vol. 45, pp. 1775-1796, 1966.
• 13: Ahmad R. Bahai , Burton R. Saltzberg, Multi-Carrier Digital Communications: Theory and Applications of Ofdm, Plenum Publishing Co., 1999
• 14: J. H. Winters, "On the capacity of radio communication systems with diversity in a rayleigh fading environment," IEEE J. Sel. Areas Commun., vol. SAC-5, pp. 871-878, 1987.
• 15: J.-F. Chang and T.-H. Yang, "Multichannel ARQ protocols," IEEE Trans. Commun., vol. 41, pp. 592-598, 1993.
• 16: W.-C. Wu, S. Vassiliadis, and T.-Y. Chung, "Performance analysis of multi-channel ARQ protocols," in Proc. 36th Midwest Symp. Circuits & Systems, 1993, vol. 2, pp. 1328-1331.
• 17: S. Fujii, Y. Hayashida, and M. Komatu, "Exact analysis of delay performance of go-back-N ARQ scheme over multiple parallel channels," Electron. Commun. Japan, vol. 84, no. 9, pt. 1, pp. 27-41, 2001.
• 18: Z. Ding and M. Rice, "Throughput analysis of ARQ protocols for parallel multichannel communications," in Proc. IEEE GLOBECOM, 2005, pp. 1279-1283.
• 19: Z. Ding, "ARQ Techniques for MIMO Communication Systems," Ph. D., Dept. of Elec. Comput. Eng., Brigham Yong Univ., Provo, UT, 2006.
• 20: N. Shacham and B. C. Shin, "A selective-repeat-ARQ protocol for parallel channels and its resequencing analysis," IEEE Trans. Commun., vol. 40, pp. 773-782, 1992.
• 21: E. N. Gilbert, "Capacity of a burst-noise channel," Bell System Technical Journal, vol. 39, no. 5, pp. 1253-1266, 1960.
• 22: E. O. Elliott, "Estimates of error rates for codes on burst-noise channels," Bell Syst. Tech. J., vol. 42, no. 5, pp. 1977-1997, 1963.
• 23: J. Abate and W. Whitt, "Numerical inversion of probability generating functions," Oper. Res. Lett., vol. 12, no. 4, pp. 245-251, 1992.
• 24: W. Stallings, Data and Computer Communications, 6th ed. Upper Saddle River, NJ: Prentice-Hall, 2000, ch. 2.
• 25: Stephen B. Wicker, Error control systems for digital communication and storage, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 26: P. Bremaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. New York: Springer-Verlag, 1998.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
SW-ARQ, in-sequence delivery, modeling and performance, multichannel data communications, resequencing buffer occupancy, resequencing delay