1400 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-~~, NO. 12, DECEMBER 1975 Packet Switching in Radio Channels: Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics LEONARD KLEINROCK, FELLOW, IEEE, AND FOUAD A. TOBAGI Absfract-Radio communication is considered as a method for providing remote terminal access to computers. Digital byte streams from each terminal are partitioned into packets (blocks) and trans- mitted in a burst mode over a shared radio channel. When many terminals operate in this fashion, transmissions may conflict with and destroy each other. A means for controlling this is for the termi- nal to sense the presence of other transmissions; this leads to a new method for multiplexing in a packet radio environment: carrier sense multiple access (CSMA). Two protocols are described for CSMA and their throughput-delay characteristics are given. These results show the large advantage CSMA provides as compared to the random ALOHA access modes. L I. INTRODUCTION ARGE COMPUTER installations, enormous data banks, and extensive national computer networks are now becoming available. They constitute large expensive resources which must be utilized in a cost/effective fashion. The constantly growing number of computer applications and their diversity render the problem of accessing these large resources a rather fundamental one. Prior to 1970, wire connections were the principal means for communica- tion among computers and between users and computers. The reasons were simplc: dial-up and leased telephone lines were available and could provide inexpensive and reasonably reliable communications for short distances, using a readily available and widespread technology. It was long recognized that this technology was inadequate for the needs of a computer-communication system which is required to handle bursty traffic (i.e., large peak to average data rates). For example, the inadequacies in- cluded the long dial-up and connect time, the minimum three-minute tariff structure, the fixed and limited data rates, etc. However, it was not until 1969 that the cost to swit.ch communication bandwidth dropped below the cost of the bandwidth being switched [l]. At that time, the new technology of packet-switched computer networks emerged and developed a cost/effect]ive means for con- necting computers together over long-distance high-speed munication of the IEEE Communications Society for publication Paper approved by the Associate Editor for Computer Com- after presentation at the National Computer Conference, Anaheim, Calif., 1975. Manuscript received December 5, 1974; revised June 11, 1975. This work was supported in part by the Advanced Research Projects Agency, Department of Defense under Contract DAHC15- The authors are with the Computer Science Department, Uni- 7343-0368. versity of California, Los Angeles, Calif. 90024. lines. However, these networks did not solve the local in- terconnection problem, namely, how can one efficiently provide access from the user to the network itself? Cer- tainly, one solution is to use wire connections here also. An alternate solution is the subject of this paper, namely, ground radio packet switching. We wish to consider broadcast radio communications as an alternative for computer and user communications. The ALOHA System [a] appears to have been the first such system to employ wireless communications. The ad- vantages in using broadcast radio communications are many: easy access to central computer installations and computer networks; collection and dissemination of data over large distributed geographical areas independent of, the availability of preexisting (telephone) wire networks; the suitability of wireless connections for communications with and among mobile users (a constantly growing area of interest and applications) ; easily bypassed hostile terrain; etc. Perhaps, this broadcast property is the key feature in radio communication. The Advanced Research Projects Agency (ARPA) of the Department of Defense recently undertook a new effort whose goal is to develop new techniques for packet radio communication among geographically distributed, fixed or mobilc, user termina.ls and to provide improved fre- quency management strategies to meet the critical shortage of RF spectrum. The research presented in this paper is an integral part of the total design effort of this system which encompasses many other research topics [3]-[SI. Consider an environment consisting of a number of (possibly mobile) users in line-of-sight and within range of each other, all communicating over a (broadcast) radio channel in a common frequency band. The classical ap- proach for satisfying the requirement of two users who need to communicate is to provide a communication chan- nel for their use so long as their need continues (line- switching). However, the measurements of Jackson and Stubbs [lo] show that such allocation of scarce communi- cation resources is extremely wasteful. Rather than pro- viding channels on a user-pair basis, we much prefer to provide a single high-speed channel to a large number of users which can be shared in some fashion. This, then, allows us to take advantage of the powerful “large number laws” which state that with very high probability, the demand at any instant will be approximately equal toKLEINROCK AND TOBAGI: PACKET SWITCHING IN RADIO CHANNELS: PART I 1401 the sum of the average demands of that population. We wish to take advantage of these gains due to resource sharing. Of interest to this paper is the consideration of radio channels for packet switching (also called packet radio channels). A packet is merely a package of data prepared by one user for transmission to some other user in the system. As soon as we deal with shared channels in a packet-switching mode, then we must be prepared to re- solve conflicts which arise when more than one demand is simultaneously placed upon the channel. In packet radio channels, whenever