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.