Browse Prior Art Database

A CARRIER SENSE MULTIPLL ACCESS PROTOCOL FOR LOCAL NETWORKS

IP.com Disclosure Number: IPCOM000128702D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 17 page(s) / 49K

Publishing Venue

Software Patent Institute

Related People

Simon S. Lam: AUTHOR [+3]

Abstract

A consequence of bursty traffic in computer communications is that among a large population of network users, at any one time only a small, number of them have data to send (ready users). In this environment, the performance of an access protocol for ~i broadcast network depends mainly upon how quickly one of the ready users can be identified and given sole access to the shared channel. The relative merits of the access protocols of polling, probing and carrier sense multiple access (CSMA) with respect to this channel assignment delay in local networks are considered. A central controller is needed for polling and probing while CSMA employs distributed control. A specific CSMA protocol is defined which requires that "collisions" in the channel be detected Lind that the users involved in a collision abort their transmissions quickly. In addition, it is assumed that the contention algorithm is adaptive and gives rise to a stable channel. An analytic model is developed. Our main result is the moment generating function of the distributed queue size (number of ready users). Mean value formulas for message delay and channel assignment delay are also derived. These results on queue size and delay are the major contribution of this paper, since they are not available in prior CSMA models in closed analytical form. Numerical results are given to illustrate the performance of the CSMA protocol. When the channel utilization is light to moderate, the mean channel assign-ment delay of the CSMA protocol. is significantly less than that of both polling and probingz consequently, the mean message delay is much smaller. It is also shown that when queueing of messages is permitted at individual users, the maximum channel throughput of CSMA approaches unity in the limit of very long queues. Finally, simulation results of several adaptive control algorithms are presented. The accuracy of our analytic formulas was carefully studied and found to be very good in all cases considered. Keywords: Local networks, broadcast chatITIC], m1litiple access protocols, distributed queueing, performance analysis, queueing theory.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A CARRIER SENSE MULTIPLL ACCESS PROTOCOL FOR LOCAL NETWORKS

Simon S. Lam

TR - 113 October 1979

Department of compuLer Sciences UniversLt v oF Toxa.,-; it Austin Austin, Texas 78712

To appear in Computer Networks. This work was supported by National. Science Foundation under Grant No. ENG78-01803.

Abstract

A consequence of bursty traffic in computer communications is that among a large population of network users, at any one time only a small, number of them have data to send (ready users). In this environment, the performance of an access protocol for ~i broadcast network depends mainly upon how quickly one of the ready users can be identified and given sole access to the shared channel. The relative merits of the access protocols of polling, probing and carrier sense multiple access (CSMA) with respect to this channel assignment delay in local networks are considered. A central controller is needed for polling and probing while CSMA employs distributed control. A specific CSMA protocol is defined which requires that "collisions" in the channel be detected Lind that the users involved in a collision abort their transmissions quickly. In addition, it is assumed that the contention algorithm is adaptive and gives rise to a stable channel. An analytic model is developed. Our main result is the moment generating function of the distributed queue size (number of ready users). Mean value formulas for message delay and channel assignment delay are also derived. These results on queue size and delay are the major contribution of this paper, since they are not available in prior CSMA models in closed analytical form. Numerical results are given to illustrate the performance of the CSMA protocol. When the channel utilization is light to moderate, the mean channel assign-ment delay of the CSMA protocol. is significantly less than that of both polling and probingz consequently, the mean message delay is much smaller.

It is also shown that when queueing of messages is permitted at individual users, the maximum channel throughput of CSMA approaches unity in the limit of very long queues. Finally, simulation results of several adaptive control algorithms are presented. The accuracy of our analytic formulas was carefully studied and found to be very good in all cases considered.

Keywords: Local networks, broadcast chatITIC], m1litiple access protocols, distributed queueing, performance analysis, queueing theory.

1. Introduction

Multipoint networks have been widely used in local networking for the interconnection of terminals to a central site: either a central computing facility or a gateway to a resource sharing computer network. The terminals are typically unintelligent and nccess to the shared data path

University of Texas Page 1 Dec 31, 1979

Page 2 of 17

A CARRIER SENSE MULTIPLL ACCESS PROTOCOL FOR LOCAL NETWORKS

(channel) is managed by the central site using a polling protocol...