`
`SATELLITE MULTIPLE
`
`ACCESS PROTOCOLS
`
`
`(C. RETNADHAS
`
`
`
`
`Each one of the independent transpondersin thesatellite is
`designed to accept transmissionat a Selected frequency band,
`i.e.,
`the uplink frequency. The satellite carries out a
`frequency translation to a well-defined frequency band, i.e.,
`ATELLITES provide a convenient medium for
`the downlink frequency. This scheme thus divides the total
`data communication between widespread geo-
`bandwidth of the satellite into well-defined channels. The
`graphic areas. Compared toaterrestrial data
`advantages provided by this schemeare reducedinterference
`network, the satellite system has wide bandwidth,
`problems and improved reliability in that the possibility of
`high accuracy of
`transmission, and high availability of
`losing all the channels due to satellite failure is small.
`transmission medium. The main disadvantagesofthe satellite
`The second method uses
`the basic multiple access
`system arethe inherently long transmission delays (270 ms
`techniques of frequency-division multiple. access (FDMA),
`one way,
`the- effect of
`local weather conditions and
`time-division multiple access (TDMA), and code-division
`interferences, and the high cost of the system. Technological
`advances can reduce the cost and the effect of weather
`multiple access (CDMA).
`conditions on the transmitted signal. The effect of
`long
`transmission delay can be minimized by using effective
`transmission protocols. Because of the above advantages,
`satellite technology has aroused a great deal of interest in
`recent years [7],[14].
`This paper presentsa tutorial on the various protocols used
`in satellite data transmission. The most important character-
`istic of the satellite system is the ability of the earth stations,
`located at geographically dispersed areas,
`to access the
`A simple form of obtaining an FDMAchannelis to divide
`satellite to transmit andto receive data. The area covered by
`the bandwidth of a transponderinto separate nonoverlapping
`a geostationarysatellite is a function ofthe satellite’s receiving
`subchannels, with each user assigned a separate subchannel.
`and transmitting antenna(s). For a large numberof users with
`In FDMA, eachuserhasaccessto a dedicated portionof the
`bursty traffic, a highly efficient way of using the channel
`channelatall times. The main advantages of FDMAarethat
`capacity is to use multiple access techniques. In a multiple
`it
`is simple to implementin that no real-time coordination _
`accessed channel, two or more users may nominally share the
`among transmission of data is needed and can be used to
`channel. The satellite system can provide broadcast capa-
`transmiteither analogor digital signals. For burstytraffic, the
`bility at any given time to all earth stations within its
`channelutilization is poor. This schemeis costeffective for
`transmission coverage area. The combination of multiple
`applications that involve point-to-point trunking.
`access and broadcast capability makes
`it possible to
`In TDMA, each user is scheduled to transmit in short
`configure the earth stations intoafully connected “one-hop”
`nonoverlapping intervals. Therefore, a TDMA scheme
`network.
`requires some form of frame structure and a globaltiming
`mechanism to achieve nonoverlapping transmission. Forthis
`reason, a TDMAsystem is more complex to implement than
`an FDMA.However, an important advantageis the connec-
`tivity. This is obtained becauseall receiverslisten on the same
`channel, while all sources ina TDMAsystem transmit on the
`same common channel]at different times.
`Thethird method uses dynamic sharing of a channelusing
`demand assignmenttechniques. This method maybe usedfor
`circuit-switched voice traffic or packet-switched datatraffic
`
`A numberof multiple access
`protocols are presented. In thefinal
`analysis, it is cost which will dictate
`which protocolis suitable for
`a particular application.
`
`
`
`Protocol for accessing satellites
`efficiently: a tutorial.
`
`CHANNEL DERIVATION
`
`There are three ways to obtain channels in a satellite
`system [8]. In the first method, the channels are obtained by
`using the built-in satellite channelization due to the use of
`multiple transponders operating in different frequency bands.
`
`The author is with the Department of Quantitative and Information Sci-
`ence, Western Illinois University, Macomb, IL 61455.
`.
`
`0163-6804/80/0900.0016 $00.75 © 1980 IEEE
`
`
`
`16
`
`
`APPLE 1009
`
`1
`
`APPLE 1009
`
`
`
`co
`
`[8]. In this paper, we confine ourselves to packet-switched
`data traffic only. The packet-switched data traffic system can
`be divided into random access,
`implicit reservation, and
`explicit reservation systems. In the following discussion, we
`will assume that the wholeof a transponder bandwidth is
`devoted to multiaccess operation,
`the up channel at one
`frequency operating in multiaccess mode and the down
`channel at another frequency operating in broadcast mode.
`The earth stations which arevisible to the satellite antenna
`transmit packetsatthe full available bandwidth. Thesatellite
`after frequency translation retransmits packets at the full
`available bandwidth. The downward packets are received at
`all earth stationswithin the satellite’s coverage. The earth
`stations identify packets destined to them by looking at the
`packet header address. All packets addressed to other
`stations are ignored and those addressedto the station are
`passed onto it.
`
`RANDOM ACCESS SYSTEM
`
`SEPTEMBER1980
`
`in turn, increases the number of
`collision increases, This,
`retransmissions which,
`in turn, increases the chance of a
`collision, and a runaway effect occurs; thus, the channel ,
`becomes unstable. In the absence of a control mechanism
`(5],[10],[13],
`the collision retransmission may produce a
`congested condition with the system throughput becoming
`zero. The purposeofthe controlis to prevent the channel from
`reaching the unstable condition, while optimizing channel
`efficiency and performance during normal operating condi-
`tions [13].
`The low bandwidth utilization of the ALOHAandthe S-
`ALOHAsystemshaveled to many proposals for increasing
`utilization by meansof slot reservation schemes. The object
`of slot reservation schemesis to reserve a particulartimeslot
`for a given station. This ensures that nocollision will take
`place. In general,
`it may be possible to achieve potentially
`high channel efficiency using some form of a reservation
`technique. This increase in channel utilization efficiency is
`obtained at some overheadcost, either in terms ofallocation
`of part of the bandwidth for reservation purposes and/or
`increased complexity of the control mechanismsin transmit-
`ting stations. All reservations methods use some form of
`framing approach, and the reservation schemecanbeeither
`implicit or explicit.
`
`
`
`
`‘One of the protocols used for transmitting packets in a
`random accesssatellite system is the ALOHA protocol. In
`this protocol, each one of the earth stationstransmit packets
`as soon as eachoneof them hasa packet to transmit without
`regard for other stations. Due to the lack of coordination
`IMPLICIT RESERVATION
`amongthe distributed ground stations, packets from different
`stations mayreachthesatellite at the same time andcollide,
`The implicit reservation protocol uses a frame concept to
`thereby destroying the information content. Therefore, a
`the S-ALOHA:channel to permit implicit reservation. A
`subsequentretransmissionofthe packetis required. Because
`frame mayconsist of more than one slot. The total numberof
`of the broadcast capability posed by the down channel,the
`slots can be groupedinto a set of reserved slots and a set of
`transmitting station will be able to detect any collision. No
`slots which can be accessed using the S-ALOHAcontention
`acknowledgmentis necessary in the satellite system in the
`protocol. Efficient channelutilization is obtained by allowing
`eventof collision. The collided packets are retransmitted after
`stations with high traffic rate access to one or moreslots from
`a further random delay in order to avoid therisk of repeated
`the reserved set of slots in each frame.
`collisions. The maximum channel. capacity that is usableis
`this principle with
`The reservation-ALOHA utilizes
`about 18 percent in the ALOHAprotocol.
`implicit reservation-by-useallocation. Reservation-ALOHA
`A substantial increase in usable channel capacity can be
`uses distributed control, and each earth station executes an
`obtained by using the S-ALOHA(slotted-ALOHA)proto-
`identicalallocation algorithm based on the globalinformation
`col, In the S-ALOHAprotocol, the satellite channelis slotted
`available from the channel. Whenevera station successfully
`into segments whose duration is exactly equal
`to the
`transmitsinaslot, all the stations internally assign thatslotin
`transmission time of a single packet (assumingfixed size
`subsequentframesfor exclusive use by the successful station.
`packets). If the earth stations are synchronized to start the
`Thus, each station maintains a ‘history of usage of each
`transmissionof packets at the beginning ofa slot, the channel
`channel slot for one frame duration. This slot is reserved to
`utilization efficiency increases. In the ALOHA protocol,
`this station until the station is finished using it. The stations
`when a collision takes place, the packets may overlapfully
`use the S-ALOHA contention method to access the
`or partially. By using the S-ALOHAprotocol, the partial
`unassigned slots in each frame. In this scheme,there is no
`overlap is eliminated. Under certain assumptions about the
`wayto preventa station from successfully capturing most or
`messagetraffic generated by the earth stations, the channel
`all of the slots in a frame for an indefinite time period.
`utilization efficiency is about 36 percent [1],[9]. This increase
`in channel utilization efficiency is obtained at the cost of
`increased complexity in control compared to the ALOHA
`system.
`Oneof the drawbacksof the.random access system is the
`problem ofinstability, When large numbersof stations are
`active, excessive traffic leads to more collision. After
`collision,
`the channel
`traffic consists of both the newly
`generated packets and the retransmitted packets. As the
`numberof newly generated packets increase, the chance of
`
`
`
`EXPLICIT RESERVATION
`These reservation schemestry to make better use of the
`channel bandwidth by explicitly reserving future channeltime
`for transmitting one or more messagesfor a specific station.
`To obtain good performance,
`the ground stations should
`cooperate with one another to maintain synchronism. Only
`by conforming to the reservationdiscipline can the earth
`stations ensure that packetcollisions will either be eliminated
`
`
`
`
`
`2
`
`
`
`
`
`
`
` Tenn
`
`
`Fig. 2. Satelilte channel for reservation.
`
`in a small slot(ALOHA)at t = 5, then all stationswill receive
`this reservation request at t = 10 (the roundtrip delay). If no
`collision has taken place, thenthe future data slots that can be
`used for data transmission are easily calculated, provided the
`current queue length is known. Assuming the current queue
`length to be 13,
`then the station which requested the
`reservation has to wait until 13 data slots have passed by
`before it can transmit data. In our example,the slots are at
`time t = 21, 22, and 24, 23 being the ALOHAslot. Because
`it takes 5 slot time for the data packets to reach thesatellite,
`the groundstation starts transmission at t = 16, 17, and 19.
`The performanceofthe system is a functionof the value M,
`the numberof data slots available between each reservation
`slot. Assumingthat there are N groundstations, andif each
`one of them is allowed to reserve ‘up to eight slots,
`the
`maximum allowed, then some reservations may carry over
`beyond the next reservationslotif 8N is greater than M. The
`system becomes overloaded if each station is allowed to
`reserve eight further slots. This increases the queue length of
`future reservations, thereby increasing packet delay. This
`situation can be avoidedif each groundstation is constrained
`to a limit of eight future reserved slots at any time [4].
`Another factor which may degrade the performance of the
`system is excessive contention for reservation slots. The
`numberof V slots must be related to the number of earth
`stations andto thelikely traffic activity to be expected.
`In this scheme, the channel maybe in any oneof the two
`states called the ALOHA and RESERVEDstates. Onstart
`up and when it
`so happens that no reservations are
`outstanding, the channel is in ALOHAstate. In ALOHA
`state, the channel consists of only slots of type V.It is possible
`to send acknowledgments, reservations, and even data which
`will fit into the small slots. In this state, a reservation request
`may be transmitted in any of
`the small slots, with no
`- requirementto wait for up to M dataslots to pass by. Once a
`successful reservation has been established,
`the channel
`enters the reservation state and anyfurther reservation can be
`madein the small slot. Once again the channel enters the
`ALOHA mode if the numberof reservations goes to zero.
`
`R-TDMA
`
`This explicit reservation protocolis a modified version of
`the contention andfixed assignment reservation method used
`in (2]. This scheme uses a fixed-assignment technique for
`
`IEEE COMMUNICATIONS MAGAZINE
`
`TI
`
`or reduced drastically. In the explicit reservation scheme, the
`earth stations use part of the channel bandwidth for sending
`reservations for future time slots. This,
`to some extent,
`reduces the total bandwidth available for data transmission.
`By keeping the bandwidth required for reservation propor-
`tionately small compared to that available for data transmis-
`sion, high channel utilization efficiency can be .obtained.
`Comparedto nonreservation schemes, more complexcontrol
`mechanisms are needed in the earth stations. The reserva-
`tions maybesentin separatetimeslots whicharedistinct from
`the time slots used for data transmission or they may be
`combinedwith data transmission (piggybacked) or both. The
`control technique usedto allocate the reserved time slot may
`be central control, distributed control, or a combination of
`both.
`
`RESERVATION ALOHA
`
`scheme makes use of separate time slots for
`This
`reservation, with the control function distributed in all the
`stations. Thesatellite channelis divided into timeslots of fixed
`size [11]. Every M + 1th slot is subdivided into V small slots
`as shownin Fig. 1.
`
`. F
`
`ig. 1. Satellite channel for reservation ALOHA.
`
`The V small slots are used byall the active stations to send
`reservations for future time slots and acknowledgments.
`These V small slots are accessed using the ALOHA
`contention technique. The M large slots carry reserved data
`packets.|
`Whenevera station receives data packets to transmit,it
`randomly selects one of
`the V slots and transmits its
`reservation. This reservation is heard byall the stations. The
`distributed control in each of the earth stations adds the
`broadcasted reservation to the existing reservation count.
`Effectively, all the waiting packets for which a reservation has
`been madejoin one “queuein the sky,” the length of whichis
`knownat all times to all ground stations. The number of
`reserved data slots that can be reserved in one request range
`from oneto eight. The requesting station has now successfully
`reserved a sequenceof future time slots for data transmission.
`Once a reservation is made, each oneof the stations knows
`which future slots belong to them, and no other station need
`concern itself with the details of reservations made by other
`stations.
`Fig. 2 shows an example taken from [11] whichillustrates
`how this reservation schemefunctions, Let us assumethatthe
`total roundtrip delay for signal travelis 10 slot time and there
`are five data slots (M) and six small slots (V). If a station
`transmits a reservationfor three future dataslots so astofall
`
`
`
`3
`
`
`
`
`
`
`——
`SEPTEMBER 1980
`making reservations and allows the total available channel
`capacity to be shared amongall stations that are busy [14].
`Fig. 3 shows the R-TDMAchannel. Onerouting frame on
`the channelis divided into a numberof reservation frames.
`The reservation frame consists ‘of a set of reservation slots
`and a numberoffixed length data slots. Thesedata slots are
`grouped together to form a data frame. A reservation frame
`mayhaveoneor more data frames. Each station is assigned a
`fixed slot in each reservation frame. Each ofthestationsis
`assigned a fixed slot
`in each one of the data frames.
`_ Therefore, each data frame has as manyslots as there are
`stations.
`Each earth station keeps a reservation table to track the
`data slot allocation. To makereservation for data slots, the
`earth station transmits its “new reservation” count in its
`reservation slot. The stations which do not have data to send
`place a valueof zeroin their fixed reservation slots. The new
`reservation countrepresents the number of data packets that
`arrived after the last reservation took place. All the earth
`stations receive the reservation packet and adjust
`their
`reservationtable values by adding the new reservation counts
`at a globally agreed upon time.
`Theallocation of data slots now becomesstraightforward.
`Those stations whose reservation table entries are not zero
`transmit their data packetin their fixed slots. The data slots
`which belongto station with no data packets are assigned in a
`round-robin manner amongthosestations with outstanding
`data packets. The senderfor eachslotis determinedjustprior
`to the slot transmissiontime. In this scheme, synchronization
`is acquired and maintained by having each station sendits
`own reservation table entry in its reservation slot.
`
`
`
`Flg. 4. Frame structure for CFMA channel.
`
`frame. Assuming thatthere are m dataslots in an 1-frame, the
`allocation of data slots is based on assigninga priority order
`for each of the m slots. For example, if the numberof stations
`equals the numberof data slots (N = m) in an I-vector, then
`the priority order for each dataslotis different. Every station
`has one data slot for whichit hasfirst priority, another for
`which it has second priority, and so on downto the least
`priority. If a station does notuseitsfirst priority dataslot, then
`a station with secondpriority to that slot gets a chance to use
`that dataslot.If all stations are busy, then eachof the stations
`will be allocatedits first priority data slot andnostationwill be
`allocated more than one slot in the above example. The
`overhead involvedin this system does not seem to be high in
`terms of channel bandwidth.
`
`CONTENTION-BASED DEMAND —
`ASSIGNMENT PROTOCOL (CPODA)
`This protocol is designed to handle packetized data and
`voicetraffic [7]. It can handletraffic with multiple priority and
`delay class distinctions, variable message lengths, and
`arbitrary load distribution among the stations.
`The channel is divided into fixed size frames, and each’
`frameconsists of reservation andinformation subframes. The
`reservation subframe is divided into fixed size reservation
`slots. In this scheme, the reservation subframeis allowed to
`grow or shrink according to the amountoftraffic. Therefore,
`when the numberofreservations for the information frameis
`zero, the reservation subframe expands to occupy the whole
`frame. Onthe other hand, whenthe system isfully loaded, the
`reservation subframe contracts to the minimum numberof
`slots required to allow reservations by high priority traffic or
`previously idle stations.
`There are two ways in which reservation for information
`subframes can be done. Thefirst way is to send areservation
`in the slots in the reservation subframe. The stations. use
`contention to gain access to the reservation slot. The second
`way is to send the reservation by piggybacking them in the
`
`
`
`CONFLICT-FREE MULTIACCESS (CFMA)
`This scheme [6] eliminates all conflict on the satellite
`multiaccess channel. The channel is divided into frames.
`Each frameis subdivided into an R-vector, an A-vector, and
`an I-vector. Fig. 4 shows the frame structure and three
`vectors. The R-vectoris used to request future reservations
`andis divided into a numberof reservation slots. The number
`of reservationslots in the R-vector is equal to the number of
`earth stations. Each one of the earth stations is assigned a
`reservation slotin the R-frame. This avoids contentionfor the
`reservation slot. The A-vector is divided into a number of
`mini-slots which are.used to send acknowledgment
`for
`previously received packets. An /-vector in a frameis divided
`into dataslots. In this scheme, the maximum numberofslots
`a station may request is equal to the numberofslots in the I-
`
`pesteretree
`
`4}
`pei
`
`sttn
`
`
` Le
`| PATFRAMES era
`
`
`
`jt
`ad Ke‘BavaFeM
`be
`:
`: ResthON siors
`Bey
`“
`[keRESERVATION:FRAME al
`
`Fig. 3. R-TDMA channel.
`
`
`
`
`
`19
`
`4
`
`
`
`
`IEEE COMMUNICATIONS MAGAZINE
`
`
`
`the reserved message transmission. A
`field of
`header
`maximum of only two new reservationsis allowed in each one
`of the messages. This allowsa station transmitting messages
`to use the piggybacking techniqueto build their reservation,
`thereby leaving the reservation subframefree for new entries
`and/or higher priority traffic.
`A distributed control is used to schedule channel timefor
`each earth station to transmit messages. The scheduling is
`done by forming a queueofthe desired transmissionsfrom the
`explicit reservation requested by the stations. The channel
`schedulingin this schemeis some function of messagepriority
`and delay. Thus, a low priority message with a short delay
`constraint may typically be serviced before a highpriority
`messagewith a long delay. The ordering, to some extent,is a
`weighted function ofpriority and delay.
`Each station carries out a consistency check to assure
`scheduling synchronization. A station is in synchronization
`whenits scheduling decision agrees with the actual transmis-
`sion in the channel. A station can bein oneofthree states as
`shown below.
`:
`
`ACQUISITION
`
`INITIAL
`
`A station in the in-sync state is in synchronism with the
`actualtransmission takingplace in the channel. Hence,itcan
`continue sending messagesat the scheduled time. Whenever
`a station detects a numberof inconsistent scheduling within a
`specified imeperiod, it movesto the out-of-syncstate. In this
`state, the station is not allowed to send any message;insteadit
`carries’ out channel scheduling and closely monitors the
`
`channel. If the station, in the monitoring channel,findsitself in
`synchronism again within a fixedperiod of time, it moves
`back to the in-syne state and participates in message
`transmission. Otherwise,
`it moves to the initial acquisition
`state. In this state, the station listens to the new reservations
`on the channel and builds up its channel scheduling
`information. The station does not transmit any message.
`Oncethis station has constructed a reservationlist compatible
`with other stations, it can moveto the out-of-syncstate.
`
`CONCLUSIONS
`
`A number of multiple access protocols have been
`presented, some of which are undergoingtesting for satellite
`communication. These reservation methods provide ameans
`to increase channel utilization compared to nonreservation
`schemes.In all the schemes, one musttrade off complexity of
`implementation with suitable performance. Therefore,
`in
`the final analysis, it is cost which will dictate which of the
`protocol schemesis suitable for a particular application.
`REFERENCES
`
`.
`
`[1] N. Abramson, “Packet switching with satellites,” in Proc. AFIPS
`Conf, vol. 42, June 1973.
`(2] R. Binder, “A dynamic packet-switching system for satellite broadcast
`channel,” in Proc. [CC ’75, San Francisco, CA, June 1975.
`(3] W. R. Crowther et al., “A system for broadcast communication:
`ReservationALOHA,” in Proc. 6th Hawaii Int. Conf. Syst. Sci.,
`Jan. 1973.
`[4] D. W. Davis et al., Computer Networks and Their Protocols. New
`York: Wiley, 1979.
`[5] M. Gerla and L. Kleinrock, “Closed loop stability control for S-
`ALOHA satellite communication,” presented at the Sth Data
`Commun, Symp., Sept. 1977.
`[6] H. R. Hwa, “A framed ALOHAsystem,”in Proc. PACNETSymp.,
`Sendai, Japan, Aug. 1975.
`[7] 1. Jacobs et ‘al., “CPODA—A demand asssignment protocol for
`SATNET,”in Proc. 5th Data Commun. Symp., 1977.
`[8] I. M. Jacobs et al., “General purpose packet satellite network,”
`Proc, [EEE,Nov. 1978.
`[9] L. Kleinrock and S. 5. Lam, “Packet-switchingin a slotted satellite
`channel,” in Proc. AFIPS Conf., vol. 42, June 1973.
`[10] S. Lam and L. Kleinrock, “Packet switching in a multi-access broad-
`cast channel: Dynamic control procedures,” [EEE Trans. Commun.,
`vol. COM-23, Sept. 1975.
`(11] L. G. Roberts, “Dynamic allocation of satellite capacity through
`packetreservation,” in Proc. AFIPS Conf. vol. 42, June 1973.
`[12] “Satellite carrier posed for increasing demands,” Commun. News,
`Mar. 1979.
`.
`[13] F. A. Tobagi et al., “Modeling and measurementtechniquesin packet
`communication networks,” Proc. IEEE, vol. 66, Nov. 1978.
`[14] R. Weissler et al., “Synchronization and multiple access protocols in
`the initial satellite IMP,” in Proc. COMPCON,Fall 1978.
`
`
`'
`
`for Computing Machinery and the IEEE.
`
`C. Retnadhasreceived the Ph.D. degree from
`Iowa State University. He is a faculty member
`in computer science at Western Illinois Univer-
`sity. His research interests include computer
`architecture, computer communication net-
`works, and distributed processing.
`Dr. Retnadhasis a memberof the Association
`
`
`
`20
`
`
`5
`
`