Announced retransmission random access system

Claims

What is claimed is:

1. A contention system for transmitting information among a plurality of transmitter-receivers along a transmission path having a delay which is long compared with the duration of an information message, so that the transmitter-receivers cannot directly establish the current status of the transmission path, the system comprising:

means for establishing a uniform time frame among said transmitter-receivers, said time frame including recurrent frame intervals, each frame interval including a predetermined plurality of sequential information message intervals, each information message interval including a minislot interval preceding an information transmission interval, each minislot interval including a plurality of sequential minislots equal to said predetermined plurality;

random initial transmission time selection means associated with each of said transmitter-receivers for accepting during a current frame interval information to be transmitted and for randomly selecting as a selected information message interval during which transmission will occur one of said information message intervals from among available ones of said predetermined plurality of information message intervals in the selected frame interval next following said current frame interval;

random retransmission time selection means associated with each of said transmitter-receivers for randomly selecting as a retransmission information message interval one of said information message intervals from among said predetermined plurality of information message intervals in a retransmission frame interval following said selected frame interval by at least said delay;

announcing and transmission means associated with each of said transmitter-receivers for transmitting an announcement message during the minislot interval of said selected information message interval, and within said minislot interval of said selected information message interval, within that minislot corresponding in minislot sequence within said minislot interval to the sequential position of said one of said retransmission information message intervals within said retransmission frame interval, thereby announcing to all receivers that particular information transmission interval during which retransmission of said information to be transmitted will occur in the event that a collision occurs in said selected information message interval within said selected frame interval;

collision identifying means associated with each of said transmitter-receivers for identifying collisions within said information message intervals;

identifying and inhibiting means associated with each said transmitter-receivers for identifying said available ones of said predetermined plurality of information message intervals in said selected frame interval, said identifying and inhibiting means excluding as available information message intervals those information message intervals which are both announced by any of said announcing and transmission means as being for retransmission of information in the event of a collision, and identified by said collision identifying means as being associated with a collision.

2. A contention access communications system for transmitting information among a plurality of transmitter-receivers by way of a transmission path having a time delay between any transmitter and any receiver which is long by comparison with the duration of an information message, the system comprising:

timing means for establishing a uniform time frame among said transmitter-receivers, said time frame including recurrent frame intervals, each frame interval including a common minislot interval and an information interval including a predetermined plurality of message slots, said common minislot interval including a plurality equal to said predetermined plurality of time-sequential common minislots, said message slots each including an information message interval and an individual minislot interval including a plurality equal to said predetermined plurality of individual minislots;

random initial transmission time selection means associated with each of said transmitter-receivers for accepting during a current frame interval information to be transmitted and for selecting as an initial transmission message slot one of a plurality of available ones of said predetermined plurality of message slots in an initial transmission frame interval following said current frame interval;

random retransmission time selection means associated with each of said transmitter-receivers for randomly selecting as a first retransmission message slot one of said message slots in a first retransmission frame following said initial transmission frame by at least said delay;

announcing and transmission means associated with each of said transmitter-receivers and responsive to said timing means, to said random initial transmission time selection means, and to said random retransmission time selection means for transmitting said information during said initial transmission message slot, and for, during said individual minislot interval of said initial transmission message slot, transmitting a first retransmission announcement in that individual minislot corresponding in individual minislot sequence within said individual minislot interval to the sequence position of said first retransmission message slot within the sequence of said message slots of said first retransmission frame, thereby announcing to all said transmitter-receivers that particular message slot in which retransmission of said information is scheduled to take place in the event of a collision occurring in said initial transmission message slot;

collision identification means associated with each of said transmitter-receivers and responsive to said announcing and transmission means for identifying a collision within said information message interval of said initial transmission message slot;

counting means associated with each of said transmitter-receivers and responsive to said collision means and to said announcing and transmission means for establishing the number of collisions which occur in each frame for which each retransmission message slot is selected, and for identifying said first retransmission message slot as one of having been selected once in said first retransmission frame and therefore being a valid first transmission slot and having been selected more than once in said first retransmission frame and therefore being an invalid first retransmission slot;

first inhibiting means coupled to said counting means and to said random initial transmission time selection means for excluding from said plurality of available message slots those message slots of a frame interval designated as valid;

second random retransmission time selection means associated with each of said transmitter-receivers and coupled to said counting means, for, in response to designation of said first retransmission message slot as invalid, randomly selecting a further retransmission message slot from among message slots of a further retransmission frame following said first retransmission frame by at least said delay; and

first retransmission means coupled to said random retransmission time selection means, to said collision identification means and to said counting means for retransmitting said information during said first retransmission message slot if said counting means designates it as valid, and, when said counting means designates said first retransmission message slot as invalid, for inhibiting retransmission of said information during said first retransmission frame, and for, during said common minislot interval of said first retransmission frame, transmitting a further retransmission announcement in that common minislot corresponding in common minislot sequence to the sequence position of said further retransmission message slot within the sequence of said message slots of said further retransmission frame, thereby announcing to all said transmitter-receivers that particular message slot in which further retransmission of said information is scheduled to take place.

3. A system according to claim 2 wherein

said collision identification means further identifies collisions occurring within said individual minislot interval of said initial transmission message slot and within said common minislot interval of said initial transmission frame interval.

4. A system according to claim 3 wherein more than one bit per minislot is transmitted.

5. A contention transmitter-receiver for a contention system for transmitting information along a transmission path having a delay which is long compared with the duration of an information message, so that the transmitter-receiver cannot directly establish the current status of the transmission path, the system including means for establishing a uniform time frame along all associated transmitter-receivers, said time frame including recurrent frame intervals, each frame interval including a predetermined plurality of sequential information message intervals, each information message interval including a minislot interval preceding an information transmission interval, each minislot interval including a plurality of sequential minislots equal to said predetermined plurality;

said transmitter-receiver comprising:

random initial transmission time selection means for responding during a current frame interval to acceptance of information to be transmitted to other transmitter-receivers of the system and for randomly selecting as an initial transmission information message interval one of said information message intervals from among available ones of said predetermined plurality of information message intervals in the initial transmission frame interval next following said current frame interval;

random retransmission time selection means for randomly selecting as a retransmission information message interval one of said information message intervals from among said predetermined plurality of information message intervals in a retransmission frame interval following said initial transmission frame interval by at least said delay;

announcing and transmission means coupled to said random initial transmission time selection means and to said random retransmission time selection means for transmitting an announcement message during the minislot interval of said initial transmission information message interval, and within said minislot interval of said initial transmission information message interval, within that minislot corresponding in minislot sequence within said minislot interval to the sequential position of said one of said information message intervals within said retransmission frame interval, thereby announcing to all said associated transmitter-receivers that particular information transmission interval during which retransmission of said information to be transmitted will occur in the event that a collision occurs in said initial transmission information message interval within said initial transmission frame interval;

collision identifying means for identifying collisions within said information message intervals; and

identification and inhibiting means coupled to said collision identifying means and to said random initial transmission time selection means for identifying said available ones of said predetermined plurality of information message interval in said retransmission frame interval, said inhibiting means excluding as available information message intervals those information message intervals received from said system which are both announced as being for retransmission of information in the event of a collision, and identified by said collision identifying means as being associated with a collision.

6. A contention transmitter-receiver for a contention system for transmitting information among a plurality of similar transmitter-receivers by way of a transmission path having a time delay between any transmitter and any receiver which is long by comparision with the duration of an information message, the system including:

timing means for establishing a uniform time frame among said transmitter-receivers, said time frame including recurrent frame intervals, each frame interval including a common minislot interval and an information interval including a predetermined plurality of message slots, said common minislot interval including a plurality equal to said predetermined plurality of time-sequential common minislots, said message slots each including an information message interval and an individual minislot interval including a plurality equal to said predetermined plurality of individual minislots, said transmitter-receiver comprising:

random initial transmission time selection means for accepting during a current frame interval information to be transmitted and for selecting as an initial transmission message slot one of a plurality of available ones of said predetermined plurality of message slots in an initial transmission frame interval following said current frame interval;

random retransmission time selection means for randomly selecting as a first retransmission message slot one of said message slots in a first retransmission frame following said initial transmission frame by at least said delay;

announcing and transmission means responsive to said random initial transmission time selection means and to said random retransmission time selection means for transmitting said information during said initial transmission message slot, and for, during said individual minislot interval of said initial transmission message slot, transmitting a first retransmission announcement in that individual minislot corresponding in individual minislot sequence with said individual minislot interval to the sequence position of said first retransmission message slot within the sequence of said message slots of said first retransmission frame, thereby announcing to all said transmitter-receivers that particular message slot in which retransmission of said information is scheduled to take place in the event of a collision occurring in said initial transmission message slot;

collision identification means for identifying a collision within said information message interval, within said individual minislot interval of said initial transmission message slot and within said common minislot interval of said initial transmission frame interval;

counting means coupled to said collision identification means for establishing the number of collisions which occur in each frame for which each retransmission message slot is selected, and for identifying said first retransmission message slot as one of (a) having been selected once in said first retransmission frame and therefore being a valid first retransmission slot and (b) having been selected more than once in said first retransmission frame and therefore being invalid;

first inhibiting means coupled to said counting means and to said random initial transmission time selection means for excluding from said plurality of available message slots those message slots of a frame interval designated as valid;

random second retransmission time selection means coupled to said counting means, for, in response to designation of said first retransmission message slot as invalid, randomly selecting a further retransmission message slot from among message slots of a further retransmission frame following said first retransmission frame by at least said delay; and

first retransmission means coupled to said random retransmission time selection means, to said random second retransmission time selection means, and to said counting means for retransmitting said information during said first retransmission message slot if said counting means designates it as valid, and, when said counting means designates said first retransmission message slot as invalid, for inhibiting retransmission of said information during said first retransmission frame, and for, during said common minislot interval of said first retransmission frame, transmitting a further retransmission announcement in that common minislot corresponding in common minislot sequence to the sequence position of said further retransmission message slot within the sequence of said message slots of said further retransmission frame, thereby announcing to all said transmitter-recievers that Particular message slot in which further retransmission of said information is scheduled to take place.

7. A method for communicating information among a plurality of transmitter-recievers by way of a transmission path having a path time delay which is long by comparison with the duration of a packet of information, comprising the steps of:

establishing a uniform time frame among said transmitter-receivers, including recurrent frame intervals;

establishing within each of said frame intervals a predetermined plurality of time-sequential message slots;

esabilishing within each of said message slots a time sequence of an information interval and a second plurality of time sequential minislots, said second plurality being equal to said first plurality;

at a first transmitter-receiver of said plurality of transmitter-receivers, accepting during a current frame interval first information to be transmitted to all of said transmitter-receivers;

at said first transmitter-receiver, organizing said first information into a first original packet to be transmitted over said transmission path;

at said first transmitter-receiver, randomly selecting a first original transmission message slot from among said first plurality of message slots in a transmission frame interval next following said current frame interval, said first original transmission message slot being selected for original transmission of a first original information packet including said first information;

at said first transmitter-receiver, randomly selecting a first retransmission message slot from among said plurality of message slots in a retransmission frame interval following said transmission frame interval by a period at least equal to said path time delay;

transmitting into said transmission path at said first transmitter-receiver said first original packet during said information interval of said first original transmission message slot and a first retransmission signal during that minislot corresponding in minislot sequence position to the sequential position of said first retransmission message slot within said plurality of message slots in said retransmission frame;

at a second transmitter-receiver of said plurality of transmitter-receivers, accepting during said current frame interval second information to be transmitted to all of said transmitter-receivers;

at said second transmitter-receiver, organizing said second information into a second orginal packet to be transmitted over said transmission path;

at said second transmitter-receiver, randomly selecting a second original transmission message slot from among said first plurality of message slots in said transmission frame interval, said second original transmission message slot being selected for original transmission of a second original information packet including said second information;

at said second transmitter-receiver, randomly selecting a second retransmission message slot from among said plurality of message slots in said retransmission frame interval;

transmitting into said transmission path at said second transmitter-receiver said second original packet during said information interval of said second original transmission message slot and a second retransmission signal during that minislot corresponding in minislot sequence position to the sequential position of said second retransmission mesage slot within said plurality of message slots in said retransmission frame, whereby if said first and second original transmission message slots happen to be identical a collision occurs and said first and second information is scrambled as received, but said first and second retransmission signals are identifiable;

at all said transmitter-receivers, generating a collision signal in response to an inability to recover information during said collision;

at all said transmitter-receivers except said first and second transmitter-receivers, inhibiting transmission during said first and second retransmission message slots of said retransmission frame interval in response to said collision signal;

at said first transmitter-receiver, in response to said collision signal, retransmitting said first information as a first retransmission packet during said first retransmission message slot in said retransmission frame;

at said second transmitter-receiver, in response to said collision signal, retransmitting said second information as a second retransmission packet during said second retransmission message also in said retransmission frame.

BACKGROUND OF THE INVENTION

This invention relates generally to a time synchronized random (contention type) access system employing a single wideband channel time shared by a plurality of random access transmit stations in which packets of information are transmitted in time slots selected randomly from one station to another. More particularly, the invention relates to such a system in which the instances of two or more transmitters selecting the same time slots for transmission of a message, resulting in a conflict, is reduced dramatically, thereby increasing the efficiency of the system, that is the useful percentage of available time slots.

In systems of the type being discussed there are a number of ground stations and a master station which can be either a ground station which performs a function of synchronizing the transmission of packets of information, all of which must be retransmitted from the satellite in a time synchronous manner. Similarly, transmissions from the ground stations to the satellites are timed so that they arrive at the satellite in a time synchronous manner.

It is apparent that without some precaution being taken that the number of conflicts or collisions between data packets from two stations arriving in the same time slot is an entirely random matter and occurs at much higher frequency than would be the case where certain precautions are taken, such as the techniques employed in the present invention. Statistically, with no precautions, the utilization of random time slots is approximately 37% without precaution being taken to avoid conflicts or collisions between messages from different transmitters in the same time slots. As will be seen later herein, the efficiency of the usage of the time slots can be raised to 53% and even to 60% by employing certain precautionary techniques which form the basis of the present invention, which has been given the name Announced Retransmission Random Access (ARRA). The basic concept of the present invention is to reduce these wasteful collisions in the random access channel by requiring the station terminals to transmit an announcement with each data packet or message specifying an intended retransmission time slot or message slot along with every transmitted message. Thus in the event of a collision, the other terminal stations in the system will know which slot the particular message which collided with another message will be retransmitted in, and can avoid placing new transmissions in that message time slot.

Basically the ARRA scheme set forth in the present invention completely eliminates collision between new message transmissions and retransmitted messages, thus resulting in a significantly higher throughput than conventional random access systems, such as slotted ALOHA and the Capetenakis Tree algorithm. The ALOHA system is well known art as defined in Abramson, "The ALOHA System--Another Alternative for Computer Communication", AFIPS Conference Proceedings, 1970 Fall Joint Computer Conference, Vol. 37, pp. 281-285. Capetanakis Tree algorithm is defined by J. I. Capetanakis, "Generalized TDMA: The Multi-Accessing Tree Protocol", IEEE, Transactions on Communications, Vol. 27, No. 10, Oct. 1979, pp. 1476-1483.

The two ARRA schemes as described in detailed in the present invention are realized with a relatively small amount of logic and storage at each of the terminals. Two realizations are described. The first realization is called basic ARRA and has a capacity (maximum normalized throughput) of 0.53, which means that approximately 50% of the time slots are successfully utilized. The second scheme is called Extended ARRA and achieves a capacity of 0.6, at the expense of a slightly greater terminal complexity. The main application area for the protocol of systems described herein are in satellite communication systems with many relatively low cost digital terminals (ground stations) sharing a common channel. For completely terrestrial networks with low propagation delay, high throughput random access systems (e.g., such as Xerox's Ethernet) already exist. For the satellite channel (which has a high propagation delay of 0.27 seconds) ARRA provides the highest throughput along with low delay among the comparable random access schemes currently described in the literature.

SUMMARY OF THE INVENTION

In a preferred form of the invention there is provided a transmission system employing a master station such as a satellite and a plurality of ground stations capable of transmitting and receiving data packets to and from each other via said master station. The master station comprises first logic system for dividing absolute time into time frames and time frames into message (time) slots with each message slot having a small percentage of its allotted time interval divided into minislots and with each minislot in each message slot corresponding to a particular message slot in a future time frame and second logic system including random number selection means responsive to the selection of message slots in the same current time frame by two or more data packets, and a third logic system randomly selects a minislot for each message slot in which a data packet is to be transmitted in the current time frame with the selected minislot for each message slot in the current time frame defining the particular message slot in the future time frame in which the data packet is to be transmitted. In case two stations select the same message plot in the current time frame to cause a conflict. A future frame is defined herein as a time frame which occurs after the data packet in the current time frame has propagated from its originating ground station to the satellite and then back to the originating ground station.

DESCRIPTION OF THE DRAWING

In the drawings:

FIG. 1 is a diagram showing the time slot arrangement for the basic ARRA system;

FIG. 2 is an enlarged view of one of the message slots and the group of minislots that accompanies each message slot of FIG. 1, and also shows a blow up of the minislots that accompanies each message slot;

FIG. 3 is a diagram of the message slots contained in a frame of the extended ARRA system and also the group of minislots in the common minislot pool (CMP);

FIG. 4 is an expanded view of one of the message slots of FIG. 3 and also an expanded view of the minislots associated with that particular message slot;

FIG. 5 is an expanded view of the minislots in the common minislot pool of FIG. 3 employed in the extended ARRA. It will be noted that the basic ARRA shown in FIGS. 1 and 2 has no common minislot pool;

FIG. 6 is a general block diagram for implementing channel format for the basic ARRA shown in FIGS. 1 and 2 and also for implementing the extended ARRA channel format shown in FIGS. 3, 4 and 5 with the difference for implementing the basic and extended ARRA formats being primarily in the logic contained in the transmit scheduler 210 of FIG. 6;

FIG. 7 is a block diagram of a transmit scheduler employed to implement the basic ARRA format shown in FIGS. 1 and 2;

FIG. 8 is the schematic diagram for implementing the extended ARRA format with of the transmit schedule for implementing the extended ARRA format shown in FIGS. 3, 4, 5.

DETAILED DESCRIPTION OF THE INVENTION

Referring now to FIG. 1 there are shown two frames of the basic ARRA system, 98 and 99, each having a number of message slots, numbered from 1 to K. Each frame is t.sub.f seconds in length and each message slot has a time duration of t.sub.m. Two of the message slots in frame 99 are identified as message slots 100 and 101. Also shown are a group of minislots whose time duration is very small compared to that of a message slot and occur at the beginning of each message slot. For message slots 100 and 101 this group of minislots, which can number from two up to perhaps a dozen, depending on the size of the system, are labeled by reference characters 104 and 106 and cover a total time period which is less than 1% of the time duration of a message slot and is more likely to be less than 0.5% of the time duration of the single message slot.

For the purposes of discussion of the specification, assume that the number of minislots at the beginning of each message slot in FIG. 1 is 8, so that in FIG. 2, which shows an expanded view of the minislot, K is equal to 8 and .DELTA.t is the time duration of a single minislot. Thus K..DELTA.t can be of the order of 0.5% of t, which is the time duration of the message slot. It will be noted that t.sub.m is a time period (as shown in FIG. 2) equal to the time period t of the message slot minus K.DELTA.t or the total time period of the K minislots.

In both the Basic and the Extended ARRA formats there are two types of data packet transmission. There is an original transmission which is a transmission that occurs for the first time, and a retransmission which is a previously unsuccessful transmission that occurs for a second time or perhaps a third time, as will be seen later. Assume that in the system being discussed there are ten ground stations identified as stations A, B, C, D, E, F, G, H, I and J, each of which is capable of generating and receiving packets of data.

As discussed above, there are two types of formats that can be employed to cover two types of collisions between the data packets in a given message slot. The first case, which employs the channel format for basic ARRA, is the simplest format and processes those instances where two stations transmit at the same time in the same message slot.

Assume the simplest situation where no conflict can occur. Assume that station A wants to send a message to station B. Station A generates a packet of data and by random selection of message slot in the very next frame transmits it via message slot 94, in frame 98 to station B. Message slot 94 contains 8 minislots as defined above. When Station A generates this packet of information, one of the minislots in message slot 94 is picked at random and a pulse placed therein. Let's assume that this minislot is minislot 2 in FIG. 2. If Station A and Station B are the only two stations involved and no other stations are sending messages, there are no complications. The message is transmitted via the satellite, Station B receives it, and there is a portion of the data packet which contains an address which identifies Station B as the recipient of the message. Station B recognizes the message as being its own and receives and stores it. However, it should be noted that all stations in addition to Station B and A receive the information that a message has been transmitted in message slot 94 and that minislot 2 has been selected. The selection of message slot 94 means that if another station had in fact transmitted a message such as Station C during the same message slot 94, the information contained in the message slot would be garbled and unintelligible to both recipients.

It has been assumed that minislot 2 in message slot 94 had been picked to accompany the message transmitted from Station A. Now the selection of minislot 2 indicates that in case of a conflict, such as will now occur between Stations A and C in message slot 94, a retransmission must occur during the next available frame in which a retransmission can occur. Such retransmission by station A will be to that message slot identified by the pulse in minislot 2, which will correspond to message slot 2 in the next frame in which the retransmission can occur. Correspondingly, if Station C placed a pulse in minislot number 3, it would retransmit in message slot 3 of the future retransmission frame.

It should be noted that the next frame in which retransmission can occur is defined as follows. A message transmitted from Station A, for example, must radiate to the satellite and then be retransmitted back to the ground station, which requires a finite amount of time. The first complete frame that is received upon completion of this round trip of the message originating at Station A is examined by logic in each of the ground stations to determine which minislots have pulses therein. All the stations will know that Stations will retransmit in the announced message slots 2 and 3 respectively. It should be further noted that retransmission of the data packets from Station A and C occur in the immediately occurring frame after the first frame received after the round trip interval defined above, so that the retransmission of the data packets of Stations A and C will occur after a second round trip interval of the data packets to the satellite and back to the ground station. However, all other stations except Stations A and C will be able to transmit new packets of information, in all message slots in the retransmission frame excluding those indicated by minislots accompanied by collisions in the message slot. This is further explained in the following.

Let's assume Station A wants to send a message to Station B. It gets this packet of information and by random selection sends it in message slot 94. This message slot 94 contains a number of minislots which have been labeled 1, 2, 3 . . . K in FIG. 2. When Station A generates its data packet it's going to put a pulse at random in one of the minislots. Assume it picks minislot 2 and places a pulse in minislot 2. If Station A and Station B are the only two stations involved, and no other station is sending messages, there are no complications. The message is transmitted via the satellite, Station B receives it, and there is a part of the packet of information that contains an address to Station B which says, in effect, Station B this is your message. Station B recognizes the message as being its own and receives and processes such message. However, it's very possible that one of the other stations, for example Station C, transmits a message to Station D about the same time Station A transmitted its message. Station C formed its package and transmitted it during message slot 94. Now there are two messages in one message slot 94 and they are conflicting. One of them is addressed to go to Station B and the other is addressed to go to Station D. Assume that Station C arbitrarily picked at random minislot 3 as its retransmission choice in case of a conflict. The selection of minislot 3 has the following meaning. There are two stations, A and C, transmitting in the same message slot 94. Station A, by its selection of 2, had declared that it will retransmit its packet in the event of a conflict in the later message slot 2 during a subsequent frame, which frame is measured by the round trip propagation time of the entire system from one ground station to the common satellite and back to another ground station. Station C by its selection of minislot 3 has declared that if there is a conflict it will retransmit its message in message slot 3 on the next frame after the round trip propagation time of the whole system which would be the same frame as the retransmission of the message originally transmitted by Station A.

The information regarding the minislots 2 and 3 of Stations A and C is retransmitted via the satellite to all of the ground stations in the whole system so that all the ground stations know there is going to be a retransmission on the next available retransmission frame in minislots 2 and 3. Such other stations, however, do not know that these transmissions are going to be from Stations A and C and they further do not know the destinations of the retransmissions. The other stations simply know that these two message slots 2 and 3 in the next retransmission frame after the first round trip propagation time of the whole system are going to be occupied. Consequently, the remaining stations will consider the message slots 2 and 3 in this second frame, the retransmission frame, off limits to them for that frame. It is obvious that the system has now reduced the total number of possible conflicts and increased the efficiency of the system.

Assume now that the next frame does occur and that in message slot 2 there will be a retransmission from Station A, which will be addressed to Station B and received by Station B. The next message slot in the same frame will be message slot 3 and the recipient Station D which will receive and process such message. However, other complications can arise because somewhere in the system there could have been another station, such as Stations F and G, sending messages at the same time. That is to say that Station F transmitted a message and Station G also transmitted a message in the first frame 96 and selected by random selection minislots 2 and 4, respectively. More specifically, assume that Station F selected minislot 2, and Station G selected minislot 4. Stations F and A have now both selected minislot 2 in the next possible retransmission frame occurring after the round trip propagation time to the satellite and back to the ground station.

When retransmission of the data packets of transmitters A and F is attempted in this first retransmission frame after the first propagation time interval, it is apparent that the system is retransmitting two messages from A and F in the same message slot, namely, message slot 2 in the retransmission frame after the first propagation time interval. It is also apparent that the two messages originating from transmitters A and F, although they are retransmissions, represent essentially the same problem as the original conflicting transmission from transmitters A and B. Thus, when transmitters A and F attempt to transmit in message slot 2 in the second frame, each will pick a new minislot at random. Assume that this time transmitter A selects minislot 6 and F selects minislot 8. When they retransmit after the second propagation time interval of the system it is possible that there will be no conflict.

As discussed briefly above, there is a structure in FIGS. 6 and 7 to implement basic ARRA format shown in FIGS. 1 and 2. The structure of FIG. 7 and the structure of FIG. 8 is employed to implement the extended ARRA format shown in FIGS. 3, 4 and 5.

Before discussing the structure of FIGS. 6, 7 and 8, consider first the channel format for the extended ARRA shown in FIGS. 3, 4 and 5, which is an improvement over the basic ARRA of FIGS. 1 and 2. As background, it will be recalled that in FIGS. 1 and 2 it's possible to have two stations A and C as transmitters which select the same minislot randomly so that when the retransmission frame occurs the messages sent by transmitters A and C cannot be successfully transmitted to their destination because the conflict has already been established by selection of the same minislot 2. This is a problem that is solved by the structure of FIGS. 3, 4 and 5, which uses a common minislot pool (CMP). In the logic implementing the extended ARRA system shown in FIGS. 3-5, there is additional logic in each of the ground stations