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.
KeywordsRandom AccessPacket NetworksChannel SensingThroughput and Delay AnalysisSensitivity to Feedback ErrorsLimit Poisson User Model
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.
B. S. Tsybakov and V. A. Mikhailov, “Ergodicity of a Slotted ALOHA System,” Problemy Peredachi Informatsii, Vol. 15, No. 4, 1979, pp. 73-87.
J. F. Hayes, “An Adaptive Technique for Local Distribution,” IEEE Transactions on Communication, Vol. 26, No. 8, 1978, pp. 1178-1186.
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
J. Capetanakis, “Generalized TDMA: The Multi-Accessing Tree Protocol,” IEEE Transactions on Communication, Vol. 27, No. 10, 1979, pp. 1476-1484.
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.
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.
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.
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.
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
J. Mosely, “An Efficient Contention Resolution Algorithm for Multiple Access Channels,” Massachusetts Institute of Technology, Cambridge, 1979.
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
B. S. Tsybakov, “Resolution of a Conflict of Known Multiplicity,” Problemy Peredachi Informatsii, Vol. 16, No. 2, 1980, pp. 69-82.
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
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.
B. S. Tsybakov and N. D. Vvedenskaya, “Random Multiple-Access Stack Algorithm,” Problemy Peredachi Informatsii, Vol. 16, No. 3, 1980, pp. 80-94.
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.
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.
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.
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
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.
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
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
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
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.
T. Berger, N. Mehravari, and G. Munson, “On Genie-Aided Upper Bounds to Multiple Access Contention Resolution Efficiency,” Johns Hopkins University, Baltimore, 1981.
H. Delic, “Sharing Policies in Communication Networks,” Master’s Thesis, University of Virginia, Charlottesville, 1990.
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.
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
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
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.
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.
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.
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
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
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
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
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.
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
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
Y. Yemini and L. Kleinrock, “An Optimal Adaptive Scheme for Multiple Access Broadcast Communications,” in Proc. Int. Conf. Commun., 1978, pp. 721-725.
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
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
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
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
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
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.
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.
B. S. Tsybakov and V. L. Bakirov, "Packet Transmission in Radio Networks", Problemy Peredachi Informatsii, 1985, vol. 21, pp. 80-101.
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.
R. Rom and M. Sidi, Multiple Access Protocols: Performance and Analysis, Springer-Verlag, 1990. doi:10.1007/978-1-4612-3402-9
D. Bertsekas and R. G. Gallager, Data Networks, Englewood Cliffs, New Jersey: Prentice-Hall, 1987.
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
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
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
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
R. L. Tweedie, “Criteria for Classifying General Markov Chains," Advances in Applied Probability, 1976, vol. 8, pp. 737-771. doi:10.2307/1425932
J. W. Cohen, On Regenerative Processes in Queueing Theory, New York: Springer-Verlag, 1976. doi:10.1007/978-3-642-95281-4
L. V. Kantorovich and V. I. Krylov, Approximate Methods of Higher Analysis, New York: Interscience, 1958.
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