Multiple-access protocols and time-constrained communication

ABSTRACT

During the past ten years, the field of multiple-access communication has developed into a major area of both practical and theoretical interest within the field of computer communications. The multiple-access problem arises from the necessity of sharing a single communication channel among a community of distributed users. The distributed algorithm used by the stations to share the channel is known as the multiple-access protocol. In this paper we examine the multiple-access problem and various approaches to its resolution.

In this survey we first define the multiple-access problem and then present the underlying issues and difficulties in achieving multiple-access communication. A taxonomy for multiple-access protocols is then developed in order to characterize common approaches and to provide a framework within which these protocols can be compared and contrasted. Different proposed protocols are then described and discussed, and aspects of their performance are examined. The use of multiple-access protocols for "real- time" or "time-constrained" communication applications, such as voice transmission, is examined next. Issues in time-constrained communication are identified, and recent work in the design of time-constrained multiple-access protocols is surveyed.

REFERENCES

• 1: ABRAMSON, N. 1970. The ALOHA system--Another alternative for computer communications, in Proceedings of the AFIPS Fall Joint Computer Conference (Houston, Tex., Nov. 17-19). AFIPS Press, Montvale, N.J., pp. 281-285.
• 2: ABRAMSON, N. 1973. Packet switching with satellites. In Proceedings of the AFIPS National Computer Conference (New York, June 4-8). AFIPS Press, Montvale, N.J., pp. 695-703.
• 3: ABRAMSON, N. 1977. The throughput of packet broadcasting channels. IEEE Trans. Commun. COM-25, 1 (Jan.), 117-128.
• 4: ARTHURS, E., AND STUCK, B. W. 1979. A theoretical traffic performance analysis of an integrated voice-data virtual circuit packet switch. JrEEE Trans. Commun. COM-27, 7 (July), 1104-1111.
• 5: BIALLY, T., MCLAUGHLIN, A. J., AND WEINSTEIN, C. J. 1980a. Voice communications in integrated digital voice and data networks. IEEE Trans. Commun. COM-28, 9 (Sept.), 1478-1490.
• 6: BIALLY, T., GOLD, B., AND SENEFF, S. 1980b. A technique for adaptive voice control in integrated packet networks. IEEE Trans. Commun. COM- 28, 3 (Mar.), 325-333.
• 7: BULLINGTON, K., ANO FRASER, J. 1959. Engineering aspects of TASI. Bell Syst. Tech. J. 38, 2 (Mar.), 353-364.
• 8: Bvx, W., CLOSS, F., JANSON, P. A., KUMMERL}~, K., AND MULLER, H. R. 1981. A reliable token ring system for local area communication. In Proceedings of the National Telecommunications Conference (New Orleans, La., Nov. 29-Dec. 3). IEEE, Piscataway, N.J., pp. A2.2.1-A2.2.6.
• 9: CAPE?ANAKIS, J. I. 1979. Generalized TDMA: The multi-accessing tree protocol. IEEE Trans. Commun. COM-27, 10 (Oct.), 1476-1484.
• 10: CARLEIAL, A., AND HELLMAN, M. 1975. Bistable behavior of ALOHA-type systems. IEEE Trans Cornmun. COM-23, 4 (Apr.), 401-409.
• 11: CHLAMTAC, i., FRANTA, W. R., AND LEVIN, K. D. 1979. BRAM: The broadcast recognizing access method. IEEE Trans. Commun~ COM-27, 8 (Aug.), 1183-1190.
• 12: CLARK, D., PROGRAN, K., AND REED, D. 1978. An introduction to local area networks. Prec. IEEE 66, 11 (Nov.), 1497-1516.
• 13: Danny Cohen, Issues in transnet packetized voice communication, Proceedings of the fifth symposium on Data communications, p.6.10-6.13, September 27-29, 1977, Snowbird, Utah, United States [doi>10.1145/800103.803349]
• 14: COVIELLO, G. J. 1979. Comparative discussion of circuit vs. packet switched voice. IEEE Trans. Commun. COM-27, 8 (Aug.), 1153-1160.
• 15: CRUZ, R., AND HAJEK, B. 1982. A new upper bound to the throughput of a multi-access broadcast channel. IEEE Trans. Inf. Theory IT-28, 3 (May), 402-405.
• 16: M. Y. Elsanadidi , Wesley W. Chu, An analysis of a time window multiaccess protocol with collision size feedback (WCSF), Proceedings of the Computer Network Performance Symposium, p.112-118, April 13-14, 1982, College Park, Maryland, United States
• 17: FARBER, D. J., FELDMAN, J., HEINRICH, F., HOP- WOOD, M., LARSON, K., LOOMIS, D., AND ROWE, L. 1973. The distributed computing system. In Proceedings of the 7th Annual IEEE Computer Society International Conference (COMPCON) (San Francisco, Calif., Feb. 27-Mar. 1). IEEE, Piscataway, N.J., pp. 31-34.
• 18: W. D. Farmer , E. E. Newhall, An experimental distributed switching system to handle bursty computer traffic, Proceedings of the first ACM symposium on Problems in the optimization of data communications systems, p.1-3, October 13-16, 1969, Pine Mountain, Georgia, United States [doi>10.1145/800165.805236]
• 19: Guy Fayolle , Erol Gelenbe , Jacques Labetoulle, Stability and Optimal Control of the Packet Switching Broadcast Channel, Journal of the ACM (JACM), v.24 n.3, p.375-386, July 1977 [doi>10.1145/322017.322019]
• 20: FISCHER, M. J., AND HARRIS, T. C. 1976. A model for evaluating the performance of an integrated circuit and packet switched multiplex structure. IEEE Trans Comrnun. COM-24, 2 (Feb.), 195- 202.
• 21: FORGIE, J. W. 1975. Speech transmission in packet switched store and forward networks. In Proceedings of the AFIPS National Computer Conference (Anaheim, Ca., May 19-22). AFIPS Press, Montvale, N.J., pp. 137-142.
• 22: FRATTA, L., BORGONOVO, F., AND TOBAGI, F. 1981. The EXPRESS-NET: A local area communication network integrating voice and data. in Performance of Data Communication Systems, G. Pujolle, Ed. Elsevier North-Holland, New York, 1981, pp. 77-88.
• 23: GALLAGER, R. G. 1976. Basic limits on protocol information in data communication networks. IEEE Trans. In{. Theory IT-22, 4 (July), 385- 398.
• 24: GALLAGER, R. G. 1978. Conflict resolution in randora access broadcast networks. In Proceedings of the AFOSR Workshop in Communication Theory and Applications (Provincetown, Mass., Sept. 17- 20). IEEE, Piscataway, N.J., pp. 74-76.
• 25: GEORGIADIS, L., AND PAPANTONI-KAZAKOS, P. 1981. A collision resolution process using energy detectors. In Proceedings of the National Te/ecomrnunwations Conference (New Orleans, La., Nov. 29-Dec. 3). IEEE, Piscataway, N.J., pp. E3.6.1- E3.6.5.
• 26: GITMAN, I., FRANK, H., O(~CHIOGROSSO, B., AND HSIEH, W. 1977. Issues in integrated network design. In Proceedings o{ the International Cornmnunxatmns Con{erence (Chicago, I11., June 12- 15). IEEE, Piscataway, N.J., pp. 38.1-36-38.1-43.
• 27: Timothy A Gonsalves, Packet-voice communication on an ethernet local computer network: an experimental study, Proceedings of the symposium on Communications Architectures & Protocols, March 08-09, 1983, Austin, Texas
• 28: GOPAL, P. M., WONG, J. W., AND MAJITHIA, J. C. 1981. An evaluation of playout strategies for voice transmission in packet networks. In Proceedings of the Computer Networking Symposium (Gaithersburg, Md., Dec. 8). IEEE, Piscataway, N.J., pp. 33-38.
• 29: GRAM~, A., SOHRABY, K., AND HAYES, J. 1982. Further results on probing. In Proceedings of the Internatwnal Communications Conference (Philadelphia, Pa., June 13-17). iEEE, Piscataway, N.J., pp. 1C.3.1-1C.3.3.
• 30: GRUBER, J. G. 1981. Delay related issues in integrated voice and data networks. IEEE Trans. Cornrnun COM-29, 6 (June), 786-800.
• 31: HAYES, J. F. 1978. An adaptive technique for local distribution. IEEE Trans. Comrnun. COM-26, 8 (Aug.), 1178-1186.
• 32: KAHN, R., GRONEMEYER, S. A., BURCHFIEL, J., AND KUNZELMAN, R. C. 1978. Advances in packet radio technology. Prec. IEEE 66,11 (Nov.), 1468- 1496.
• 33: KIM, B. 1983. Two adaptive token ring strategies for real-time traffic. In Proceedings o{ the Computer Networking Symposium (Silver Spring, Md., De~ 13). IEEE, Piscataway, N.J., pp. 119-121.
• 34: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 35: KLEINROCK, L. 1977. Performance of distributed multi-access computer communication systems. In 1977 IFIP Congress Procee&ngs (Toronto, Canada, Aug. 8-12). Elsevier North-Holland, Amsterdam, pp. 547-552.
• 36: KLEINROCK, L., AND LAM, S. S. 1975. Packet switching in a multiaccess broadcast channel: Performance evaluation. IEEE Trans. Commun. COM- 23, 4 (Apr.), 410-423.
• 37: KLEINROCK, L., AND SCHOLL, M. O. 1980. Packet switching in radio channels: New conflict-free multiple access schemes. IEEE Trans. Commun. COM-28, 7 (July), 1015-1029.
• 38: KLEINROCK, L., AND TOBAGI, F. A. 1975. Packet switching in radio channels: Part I--Carrier sense multiple access modes and their throughput-delay characteristics. IEEE Trans. Commun. COM-23, 12 (Dec.), 1400-1416.
• 39: James Francis Kurose, Time-constrained communication in multiple access networks (data communication, protocols), 1984
• 40: KUROSE, J. F., ANO SCHWARTZ, M. 1983. A family of window protocols for time-constrained applications in CSMA networks, in Proceedings o{ the INFOCOM 83 (San Diego, Calif., Apr. 18-21). IEEE, Piscataway, N.J., pp. 405-413.
• 41: James F. Kurose , Mischa Schwartz , Yechiam Yemini, Controlling window protocols for time-constrained communication in a multiple access environment, Proceedings of the eighth symposium on Data communications, p.75-84, October 03-06, 1983, North Falmouth, Massachusetts, United States
• 42: LAM, S. S., AND KLEINROCK, L. 1975. Packet switching in a multiaccess broadcast channel: Dynamic control procedures. IEEE Trans. Commun. COM- 23, 9 (Sept.), 891-904.
• 43: LIMB, J., AND FLORES, C. 1982. Description of FAS- NET--A unidirectional local-area communications network. Bell Syst. Tech. J. 61, 7 (Sept.), 1413-1440.
• 44: MAGLARIS, B., AND LISSACK, T. 1981. A priority TDMA protocol for satellite data communications. In Proceedings o{ the International Communications Con{erence (Denver, Colo., June 14- 18). IEEE, Piscataway, N.J., pp. 73.3.1-73.3.5.
• 45: MAXEMCHUK, N. 1982. A variation of CSMA/CD that yields movable TDM slots in integrated voice/data local networks. Bell Syst. Tech. J. 61, 7 (Sept.), 1527-1550.
• 46: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 47: MIT DSN 1982. Workshop on Distributed Sensor Networks (Lexington, Mass., Jan.). MiT Lincoln Laboratories, Lexington, Mass.
• 48: MITTAL, K. K., AND VENffI~SANOPOULOS, A. N. 1981. On the dynamic control of the Urn scheme for multiple access broadcast communication systems. IEEE Trans. Commun. COM-29, 7 (July), 962-970. ~
• 49: MOLLE, M. L. 1981. Extensions and unifications of the multiple access communication problem. Tech. Rep. CSD-810730, Computer Science Dept., University of California, Los Angeles, July, 1981.
• 50: MOLLE, M. 1982. On the capacity of infinite population multiple access protocols. IEEE Trans. in{. Theory IT-28, 3 (May), 396-401.
• 51: MOWAFI, O. A., AND KELLY, W. J. 1980. Integrated voice/data packet switching techniques for future military networks. IEEE Trans. Commun. COM- 28, 9 (Sept.), 1655-1662.
• 52: NuTr, G. J., AND BAYER, D. L. 1982. Performance of CSMA/CD networks under combined voice and data loads. IEEE Trans. Commun. COM-30, 1 (Jan.), 6-11.
• 53: PiPPENGER, N. 1981. Bounds on the performance of protocols for a multiple access broadcast channel. IEEE Trans. inf. Theory IT-27, 2 (Mar.)., 145- 151.
• 54: POKRESS, R., Ed. 1984. Special issue on integrated services digital networks. IEEE Commun. Mag. 22, i (Jan.).
• 55: Jerome H. Saltzer , David D. Clark , Kenneth T. Pogran, Why a ring?, Proceedings of the seventh symposium on Data communications, p.211-217, October 27-29, 1981, Mexico City, Mexico
• 56: Mischa K. Schwartz, Computer Communications Network Design and Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 57: John F. Shoch , Jon A. Hupp, Measured performance of an Ethernet local network, Communications of the ACM, v.23 n.12, p.711-721, Dec. 1980 [doi>10.1145/359038.359044]
• 58: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 59: TOBAGI, F., AND KLEINROCK, L. 1977. Packet switching in radio channels: Part iV--St~tbility considerations and dynamic control in carrier sense multiple access. IEEE Trans. Commun. COM-25, 10 (Oct.), 1103-1119.
• 60: TOWSLEY, D., AND VENKATESH, G. 1982. Window random access protocols for local comput~,r networks. IEEE Trans Comput. C-31, 8 (Aug. l~, 715- 722.
• 61: Yechiam Yemini, On channel sharing in discrete-time, multi-access broadcast communication, 1979

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Network communications
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design