Back
 IJCNS  Vol.5 No.10 , October 2012
Random Access Algorithms in Packet Networks—A Review of Three Research Decades
Abstract: We present a coherent and systematic review of Random Access Algorithms for packet networks, as developed over three and a half decades. We consider the appropriate user models and we classify the algorithms according to the channel sensing constraints imposed. We also present a review of the analytical methodologies required for the performance analysis of these algorithms.
Cite this paper: A. T. Burrell and P. Papantoni-Kazakos, "Random Access Algorithms in Packet Networks—A Review of Three Research Decades," International Journal of Communications, Network and System Sciences, Vol. 5 No. 10, 2012, pp. 691-707. doi: 10.4236/ijcns.2012.510072.
References

[1]   N. Abramson, “The ALOHA System: Another Alternative for Computer Communications,” AFIPS’70 (Fall) Proceedings of the November 17-19, New York, 17-19 November 1970, pp. 281-285.

[2]   B. S. Tsybakov and V. A. Mikhailov, “Ergodicity of a Slotted ALOHA System,” Problemy Peredachi Informatsii, Vol. 15, No. 4, 1979, pp. 73-87.

[3]   J. F. Hayes, “An Adaptive Technique for Local Distribution,” IEEE Transactions on Communication, Vol. 26, No. 8, 1978, pp. 1178-1186.

[4]   J. I. Capetanakis, “Tree Algorithms for Packet Broadcast Channels,” IEEE Transactions on Information Theory, Vol. 25, No. 5, 1979, pp. 505-515. doi:10.1109/TIT.1979.1056093

[5]   J. Capetanakis, “Generalized TDMA: The Multi-Accessing Tree Protocol,” IEEE Transactions on Communication, Vol. 27, No. 10, 1979, pp. 1476-1484.

[6]   J. L. Massey, “Collision Resolution Algorithms and Random-Access Communications,” In: G. Longo, Ed., Multi-User Communications (CISM Courses and Lectures Series), Springer-Verlag, New York, 1981, pp. 73-137.

[7]   B. S. Tsybakov and V. A. Mikhailov, “Slotted Multi-Access Packet Broadcasting Feedback Channel,” Probfemy Peredachi Informatsii, Vol. 14, No. 4, 1978, pp. 32-59.

[8]   R. G. Gallager, “Conflict Resolution in Random Access Broadcast Networks,” Proceedings of AFOSR Workshop in Communication Theory and Applications, Provincetown, 17-20 September 1978, pp. 74-76.

[9]   B. S. Tsybakov and V. A. Mikhailov, “Packet Random Multiple Access; Part-and-Try Algorithm,” Problemy Peredachi Informatsii, Vol. 16, No. 4, 1980, pp. 65-79.

[10]   P. Humblet, “On the Throughput of Channel Access Algorithms with Limited Sensing,” IEEE Transactions on Communication, Vol. 34, No. 4, 1986, pp. 345-347. doi:10.1109/TCOM.1986.1096539

[11]   J. Mosely, “An Efficient Contention Resolution Algorithm for Multiple Access Channels,” Massachusetts Institute of Technology, Cambridge, 1979.

[12]   L. Georgiadis and P. Papantoni-Kazakos, “A Collision Resolution Protocol for Random Access Channels with Energy Detectors,” IEEE Transactions on Communication, Vol. 30, No. 11, 1982, pp. 2413-2420. doi:10.1109/TCOM.1982.1095438

[13]   B. S. Tsybakov, “Resolution of a Conflict of Known Multiplicity,” Problemy Peredachi Informatsii, Vol. 16, No. 2, 1980, pp. 69-82.

[14]   M. Georgiopoulos and P. Papantoni-Kazakos, “Collision Resolution Protocols Utilizing Absorptions and Collision Multiplicities,” IEEE Transactions on Communication, Vol. 33, No. 7, 1985, pp. 721-724. doi:10.1109/TCOM.1985.1096366

[15]   N. D. Vvedenskaya and B. S. Tsybakov, “Random Multiple Access of Packets to a Channel with Errors,” Problemy Peredachi Informatsii, Vol. 19, No. 2, 1982, pp. 52-68.

[16]   B. S. Tsybakov and N. D. Vvedenskaya, “Random Multiple-Access Stack Algorithm,” Problemy Peredachi Informatsii, Vol. 16, No. 3, 1980, pp. 80-94.

[17]   B. S. Tsybakov and V. A. Mikhailov, “Free Synchronous Packet Access in a Broadcast Channel with Feedback,” Problemy Peredachi Informatsii, Vol. 14, No. 4, 1978, pp. 259-280.

[18]   B. S. Tsybakov and N. B. Likanov, “Some New Random Multiple Access Algorithms,” Problems of Information Transmission, Vol. 21, No. 2, 1985, pp. 134-154.

[19]   L. Georgiadis and P. Papantoni-Kazakos, “Limited Feedback Sensing Algorithms for the Broadcast Channel,” IEEE Transactions on Information Theory, Vol. 31, No. 2, 1985, pp. 280-294.

[20]   M. Paterakis and P. Papantoni-Kazakos, “A Simple Window Random Access Algorithm with Advantageous Properties,” IEEE Transactions on Information Theory, Vol. 35, No. 5, 1989, pp. 1124-1130. doi:10.1109/18.42234

[21]   A. T. Burrell and P. Papantoni-Kazakos, “A Class of Limited Sensing Random Access Algorithms with Resistance to Feedback Errors and Effective Delay Control,” Journal of Communications and Networks, Vol. 8, No. 1. 2006, pp. 21-27.

[22]   L. Georgiadis and P. Papantoni-Kazakos, “A 0.487 Throughput Limited Sensing Algorithm,” IEEE Transactions on Information Theory, Vol. 33, No.2, 1987, pp. 233-237. doi:10.1109/TIT.1987.1057278

[23]   N. Pippenger, “Bounds on the Performance of Protocols for a Multiple-Access Broadcast Channel,” IEEE Transactions on Information Theory, Vol. 27, No. 2, 1981, pp. 145-151. doi:10.1109/TIT.1981.1056332

[24]   M. Molle, “On the Capacity of Infinite Population Multiple Access Protocols,” IEEE Transactions on Information Theory, Vol. 28, No. 3, 1982, pp. 396-401. doi:10.1109/TIT.1982.1056509

[25]   B. S. Tsybakov and V. A. Mikhailov, “An Upper Bound for Maximum Throughput of Random Access System,” International Symposium on Information Theory, Santa Monica, 1981.

[26]   T. Berger, N. Mehravari, and G. Munson, “On Genie-Aided Upper Bounds to Multiple Access Contention Resolution Efficiency,” Johns Hopkins University, Baltimore, 1981.

[27]   H. Delic, “Sharing Policies in Communication Networks,” Master’s Thesis, University of Virginia, Charlottesville, 1990.

[28]   H. Delic and P. Papantoni-Kazakos, “Performance Analysis for Multi-Channel Random Access Interconnection Analysis,” Proceedings of the 23rd Annual Conference on Information Sciences and Systems, Baltimore, 18-20 March 1989, pp. 695-699.

[29]   H. Delic and P. Papantoni-Kazakos, “An Optimal Policy for Competitive Processing of High and Low Priority Arrivals,” International Journal of Digital and Analog Communication Systems, Vol. 4, No. 3, 1991, pp. 209-224. doi:10.1002/dac.4510040305

[30]   P. Papantoni-Kazakos, “Multiple Access Algorithms for a System with Mixed Traffic: High and Low Priority,” IEEE Transactions on Communication, Vol. 40, No. 3, 1992, pp. 541-555. doi:10.1109/26.135724

[31]   P. Papantoni-Kazakos, H. Delic, M. Paterakis and M. Liu, “Transmission Algorithms for a Multi-Channel Packet Radio System with Priority Users,” International Journal of Digital and Analog Communication Systems (IJDACS), Vol. 6, No. 4, 1993, pp. 193-212.

[32]   P. Papantoni-Kazakos, N. Likhanov and B. S. Tsybakov, “A Protocol for Random Multiple Access of Packets with Mixed Priorities in Wireless Networks,” IEEE JSAC, Vol. 13, No. 7, 1995, pp. 1324-1331.

[33]   J. Kurose, M. Schwartz and Y. Yemini, “Multiple Access Protocols and Time Constrained Communication,” ACM Computing Surveys, Vol. 16, No. 1, 1984, pp. 43-70.

[34]   G. D. Marcus and P. Papantoni-Kazakos, “Dynamic Scheduling Protocols for a Multiple Access Channel,” IEEE Transactions on Communication, Vol. 31, No. 9, 1983, pp. 1046-1054. doi:10.1109/TCOM.1983.1095934

[35]   M. Paterakis, L. Georgiadis and P. Papantoni-Kazakos, “A Full Sensing Window Random-Access Algorithm for Messages with Strict Delay Constraints,” Algorithmica, 1989, Vol. 4, No. 3, pp. 313-328. doi:10.1007/BF01553894

[36]   D. F. Lyons and P. Papantoni-Kazakos, “A Window Random Access Algorithm for Environments with Capture,” IEEE Transactions on Communication, Vol. 37, No. 7, 1989, pp.766-770. doi:10.1109/26.31169

[37]   C. Bisdikian, L. Merakos and L. Georgiadis, “Stability Analysis of Interconnected Single-Hop Random-Access Networks,” IEEE Transactions on Communications, Vol. 40, No. 3, 1992, pp. 556-567. doi:10.1109/26.135725

[38]   R. L. Hamilton and E. J. Coyle, “A Two-Hop Packet Radio Network with Product Form Solution,” Proceedings of the 20th Annual Conference on Information Sciences and Systems, Princeton, 1986, pp. 871-876.

[39]   M. Sidi and I. Cidon, “A Multi-Station Packet Radio Network,” Performance Evaluation, Vol. 8, No. 1, 1988, pp. 65-72. doi:10.1016/0166-5316(88)90013-2

[40]   B. Eklundh, “Channel Utilization and Blocking Probability in a Cellular Mobile Telephone System with Direct Retry,” IEEE Transactions on Communications, Vol. 34, No. 4, 1986, pp. 329-337. doi:10.1109/TCOM.1986.1096544

[41]   Y. Yemini and L. Kleinrock, “An Optimal Adaptive Scheme for Multiple Access Broadcast Communications,” in Proc. Int. Conf. Commun., 1978, pp. 721-725.

[42]   J.-C. Huang and T. Berger, “Delay Analysis of 0.487 Contention resolution Algorithm,” IEEE Transactions on Communications, Vol. 34, No. 9, 1986, pp. 916-926. doi:10.1109/TCOM.1986.1096639

[43]   L. Georgiadis, L. Merakos and P. Papantoni-Kazakos, “A Method for the Delay Analysis of Random Multiple Access Algorithms Whose Delay Process is Regenerative,” IEEE Journal on Selected Areas in Communications, 1987, Vol. 5, No. 6, 1987, pp. 1051-1062. doi:10.1109/JSAC.1987.1146613

[44]   M. Paterakis, L. Georgiadis and P. Papantoni-Kazakos, “On the Relation between the Finite and the Infinite Population Models for a Class of RAA’s,” IEEE Transactions on Communications, Vol. 35, No. 11, 1987, pp. 1239-1240. doi:10.1109/TCOM.1987.1096696

[45]   R. Gallager, “A Perspective on Multiaccess Channels,” IEEE Transactions on Information Theory, Vol. 31, No. 2, 1985, pp. 124-142. doi:10.1109/TIT.1985.1057022

[46]   A. Bar-David and M. Sidi, “Collision Resolution Algorithms in Multistation Packet Radio Networks”, IEEE Transactions on Communications, 1989, vol. 37, pp. 1387-1391. doi:10.1109/26.44212

[47]   G. Fayolle, P. Flajolet, M. Hofri, and P. Jacquet, “The Evaluation of Packet Transmission Characteristics in a Multi-Access Collision Detection Channel with Stack Collision Resolution Protocol,” Computer Science Dept., Technion, Israel Institute of Technology, Haifa, Tech. Rep. 293, Oct. 1983.

[48]   L. Merakos and L. Georgiadis, "Stability of Interconnected Random Access Networks", Proceedings of the 25th IEEE Conference on Decision and Control, Athens, Greece, 1986, pp. 1330-1332.

[49]   B. S. Tsybakov and V. L. Bakirov, "Packet Transmission in Radio Networks", Problemy Peredachi Informatsii, 1985, vol. 21, pp. 80-101.

[50]   B. S. Tsybakov and V. B. Fayngold, “A Non-homogeneous Frame RMA Algorithm”, Problems of Information Transmission, 1989, Vol. 25, No. 2, pp. 126-136.

[51]   R. Rom and M. Sidi, Multiple Access Protocols: Performance and Analysis, Springer-Verlag, 1990. doi:10.1007/978-1-4612-3402-9

[52]   D. Bertsekas and R. G. Gallager, Data Networks, Englewood Cliffs, New Jersey: Prentice-Hall, 1987.

[53]   M. Kaplan, “A Sufficient Condition for Non-ergodicity of a Markov Chain”, IEEE Transactions on Information Theory, 1979, vol. 25, pp. 470-471. doi:10.1109/TIT.1979.1056059

[54]   W. Szpankowski, “Stability Conditions for Multidimensional Queueing Systems with Computer Applications”, Operations Research, 1988, vol. 36, pp. 944-957. doi:10.1287/opre.36.6.944

[55]   W. Szpankowski and V. Rego, “Some Theorems on Instability with Applications to Multi-Access Protocols”, Operations Research, 1988, vol. 36, pp. 958-966. doi:10.1287/opre.36.6.958

[56]   A. G. Pakes, “Some Conditions for Ergodicity and Recurrence of Markov Chains," Operations Research, 1969, vol. 17, pp. 1058-1061. doi:10.1287/opre.17.6.1058

[57]   R. L. Tweedie, “Criteria for Classifying General Markov Chains," Advances in Applied Probability, 1976, vol. 8, pp. 737-771. doi:10.2307/1425932

[58]   J. W. Cohen, On Regenerative Processes in Queueing Theory, New York: Springer-Verlag, 1976. doi:10.1007/978-3-642-95281-4

[59]   L. V. Kantorovich and V. I. Krylov, Approximate Methods of Higher Analysis, New York: Interscience, 1958.

[60]   S. Stidman, Jr., “Regenerative Processes in the Theory of Queues with Applications to the Alternating Priority Queue", Adv. Appl. Prob., 1972, Vol. 4, pp. 542-577. doi:10.2307/1425993

 
 
Top