Random access communication system with scheduled data transmission and asynchronous contention scheduling

• US 4,774,707 A
• Filed: 09/10/1986
• Issued: 09/27/1988
• Est. Priority Date: 09/10/1986
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Raychaudhuri, Dipankar
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US06/905,506
• Time in Patent Office: 748 Days
• Field of Search: 370/85, 370/89, 370/93, 370/95, 370/104
• US Class Current: 370/447
• CPC Class Codes: H04B 7/18528 Satellite systems for providing two-way communications service to a network of fixed stations, i.e. fixed satellite service or very small aperture terminal [VSAT] system
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 74/02 Hybrid access

Abstract

In a communication system serving a plurality of transmitter-receivers, high capacity is achieved by asynchronous contention access of relatively short reservation request packets, which if successfully transmitted result in the scheduled, noncontention transmission of relatively long message data packets. In a first embodiment, the reservation request packets bear information relating to the duration of the message data packets, so that appropriate message data transmission time may be scheduled. Unsuccessful or colliding reservation request packets are retransmitted. In a second embodiment, the reservation requests packets do not include duration information, and the message data packets have fixed duration. In the second embodiment, collision resolution techniques allow the message data scheduling without retransmission of some colliding reservation request packets. It is also possible to operate in both modes, by scheduling random length message data transmissions as a result of noncolliding reservation request packets, and by scheduling fixed duration message data transmissions when reservation request packets collide.

Claims

1. A random access contention system for providing packet communications among a plurality of transmitter-receivers by way of different paths through a transmission medium, each path being used for transmission of both reservation request packets and data packets and exhibiting a respective similar-value transmission delay therethrough of substantial length compared to the durations of at least some packets, no path between each different pair of transmitter-receivers being fully included in the path between any other different pair of transmitter-receivers, said system comprising:

transmission means associated with each transmitter-receiver, said transmission means being coupled to said transmission medium and adapted for accepting information to be transmitted, for forming said information into at least one data packet for scheduled transmission by way of said transmission medium, for generating at least one reservation request packet associated with each said data packet, and for transmitting one of said reservation request packets by way of said transmission medium at a random time other than when transmission by that transmission means is inhibited, each said reservation request packet being of a similar duration that is many times shorter than the similar-value transmission delay between each pair of transmitter-receivers and substantially shorter than at least most said data packets;

receiving means associated with each transmitter-receiver and coupled to said transmission medium for receiving its own reservation request packets and other packets originating from other transmitter-receivers;

means for controlling when data packets are transmitted by each transmitter-receiver so as to avoid collision with any said reservation request packet and with data packets from any other of said plurality of transmitter-receivers, which means includes

respective status determining means associated with each transmitter-receiver and coupled to the associated receiving means, and

respective control and scheduling means associated with each transmitter-receiver and coupled to the associated status determining means and transmission means;

respective means included within the status determining means of each transmitter-receiver, for identifying the successful reception by that transmitter-receiver of its said own reservation packet and for generating in response an own successful reservation request signal;

respective means included within the status determining means of each transmitter-receiver, for identifying the successful reception by the transmitter-receiver of a reservation packet other than its own, and generating in response an other successful reservation request signal;

respective means included within the said control and scheduling means of each said transmitter-receiver for causing said transmission means of that transmitter-receiver means to begin transmission of a said data packet thereof in response to said successful own reservation request signal, said transmission of said data packet beginning at an initiation time delayed from said successful reception of its said own reservation request packet by a time delay, said time delay having a first delay component and a second delay component, said first delay component being at least as long as the duration of one of said reservation request packets but many times shorter than any of said similar-value transmission delays, and said second delay component being at times zero-valued; and

respective inhibiting means included in the control and scheduling means of each transmitter-receiver for inhibiting all transmission from the transmission means of that transmitter-receiver for a selected time following said initiation time in response to said other successful reservation request signal, which inhibiting thereby determines the duration of said second delay component for that transmitter-receiver.

2. A system according to claim 1 wherein said control and scheduling means further comprises stacking means coupled to said status determining means for, in response to said successful own reservation request signal, causing said data packet to be transmitted by said transmission means beginning at the later of said initiation time and the end of said selected time.

3. A system according to claim 1 wherein said transmission means includes means for encoding said reservation request packet with time information relating to the duration of the associated one of said data packets;

said receiving means includes means for decoding said time information to form decoded time information; and

said control and scheduling means further sets said selected time in response to said decoded time information.

4. A system according to claim 1 wherein:

said transmission means includes means for forming said data packets with uniform duration; and

said control and scheduling means further comprises means for setting said selected time to one of zero time and an integer multiple of said uniform duration, said integer including unity.

5. A system according to claim 4 wherein:

said status determining means further comprises first collision resolution means for determining if said own reservation request packet is the first received among a plurality of packets received at overlapping times, and for generating a FIRST signal in response thereto; and

said control and scheduling means further comprises means for setting said selected time to one of said zero time and unity multiple of said uniform duration, in response to said FIRST signal.

6. A system according to claim 5 wherein:

said status determining means further comprises second collision resolution means for determining if said own reservation request packet is the last received among a plurality of packets and for generating a LAST signal in response thereto; and

said control and scheduling means further comprises means for setting said selected time to the other one of said zero time and unity multiple of said uniform duration, in response to said LAST signal.

7. A system according to claim 1 wherein:

said status determining means further comprises means for producing an own reservation packet collision signal in response to unsuccessful reception of said own reservation request packet; and

said control and scheduling means further comprises retransmission control means for causing said transmission means to retransmit said reservation request packet at a random time in response to said own reservation packet collision signal.

8. A system according to claim 7 wherein:

said data packets formed by said transmission means are of uniform duration;

said status determining means further comprises means for producing, in the event of a collision of said own reservation request packet, a FIRST signal if said own packet is first among those colliding, and a LAST signal if said own packet is last among those colliding; and

said control and scheduling means further comprises means for setting said initiation time to a time delayed from the reception of the last signal among those colliding by said time equal to the duration of one of said reservation request packets, and for causing said transmission means to begin to transmit said data packet in response to said FIRST signal at said initiation time, and for setting said initiation time to a time delayed from the reception of the last signal among those colliding by the sum of said time equal to the duration of one of said reservation request packets plus said uniform duration, and for causing said transmission means to begin to transmit said data packet in response to said LAST signal at said initiation time.

9. A random access contention system for providing packet communications among a plurality of transmitter-receivers by way of different paths through a transmission medium, each path being used for transmission of both reservation request packets and data packets and exhibiting a respective similar-value transmission delay therethrough of substantial length compared to the durations of at least some packets, no path between each different pair of transmitter-receivers being fully included in the path between any other different pair of transmitter-receivers, said system comprising:

transmission means associated with each transmitter-receiver and coupled to said transmission medium, and adapted for accepting information to be transmitted, for forming the information into data packets, each of which requires a uniform a duration for scheduled transmission by way of said transmission medium, for generating in association with each of said data packets a reservation request packet requiring a second duration for transmission, for originally transmitting said reservation request packet by way of said transmission medium at a random time other than when transmission by that transmission means is inhibited, for transmitting said data packet upon receipt of a data transmit command, for retransmitting said reservation request packet at a random time in response to a reservation request packet retransmit command, and for being inhibited from transmitting by an inhibit signal, each said reservation request packet being of similar duration that is many times shorter than the transmission delay between each pair of transmitter-receivers and substantially shorter than at least most said data packets;

receiving means associated with each transmitter-receiver and coupled to said transmission path, and adapted for receiving from said transmission medium its own reservation request packet originating with the associated said transmission means and also adapted for receiving other packets originating from other transmitter-receivers;

means for controlling when data packets are transmitted by each transmitter-receiver so as to avoid collision with any said reservation request packet and with data packets fro many other of said plurality of transmitter-receivers, which means includes the elements claimed hereinafter;

status determining means associated with each transmitter-receiver and coupled to the associated said transmission means and to the associated said receiving means for establishing the successful transmission or collision of said own reservation request packet and the successful transmission of other reservation request packets; and

control and scheduling means associated with each transmitter-receiver and coupled to the associated said transmission means and to the associated said status determining means for generating and coupling said inhibit signal to said transmission means for inhibiting all transmission from said transmission means for a selected duration following successful transmission of each of said other reservation request packet retransmission command to said transmission means in response to at least some collisions of said own reservation request packet, and for generating and coupling said data transmission command to said transmission means at a time delayed by at least said second duration in response to successful transmission of said own reservation request packet.

10. A contention type random access system for burst communication ammong a plurality of transmitter-receivers by way of a transmission mediuim, the transmission path through said medium between any transmitter and any receiver having a time delay which is long compared with the duration of an information packet, so that the current status of its transmission path cannot be determined by any transmitter-receiver, the system comprising:

a source of information to be transmitted associated with each transmitter-receiver, said information being intended for at lest one transmitter-receiver ohter than the transmitting transmitter-receiver;

controllable transmission means associated with each transmitter-receiver and coupled to the associated said source of information for receiving said information to be transmitted and for forming said information to be transmitted into information packets of uniform duration, and for each information packet generating and transmitting at least one reservation request over said transmission medium in the form of at least one reservation request packet, each having a leading edge, a predetermined duration, and a lagging edge;

receiving means associated with each transmitter-receiver and coupled to said transmission medium for receiving from. said transmission medium its own reservation request packets originating from the associated said transmission means, and for receiving other reservation request packets and other information packets originating from transmission means associated with other transmitter-receivers, said receiving means producing idle signals when each said transmission path thereto is idle and also producing active signals when any one of said transmission paths thereto is active;

in each transmitter-receiver respective first timing means coupled to said receiving means and to said transmitting means and responsive to said active and idle signals for generating a first signal when each said transmission path thereto is idle for an interval preceding and contiguous with the expected time of reception of a leading edge of its own reservation request packet transmitted by the associated transmission means, for generating a second signal when at least one said transmission path thereto is active for an interval preceding and contiguous with said expected time of reception of said leading edge of said own reservation request packet, for genrating a third signal when each said transmission path thereto is idle for an interval following and contiguous with a lagging edge of said own resrvation request packet, for generating a fourth signal when at least one said transmission path thereto is active for an interval following and contiguous with said time of reception of said lagging edge of said own reservation request packet, for generating a fifth signal when a said other reservation request packet having said predetermined duration is received from said other transmission-receivers, indicative of a successful reservation request transmission, and for generating a sixth signal when a reservation request packet having in excess of said predetermined duration is received from said other transmitter-receivers, indicative of a collision; and

in each transmitter-receiver, respective control means coupled to said transmission means, to said receiving means and to said timing means, for inhibiting said transmission means from transmitting reservation request and information packets for a time equal to the sum of two of said uniform durations plus one said predetermined duration in response to said sixth signal, for inhibiting said transmission means form transmitting reservation request and information packets for a time equal to the sum of the a predetermined number of said uniform durations and one of said predetermined durations in response to said fifth signal, for causing, in response to said first and fourth signals, said transmission means to transmit said information packet beginning at a time following a time marker by said predetermined duration, and for causing, in response to said second and third signals, said transmission means to transmit said information packet beginning at a time following said time marker by the sum of said predetermined duration and said uniform duration.

11. A transmitter-receiver for a random access system for burst communications among a plurality of similar associated transmitter-receivers by way of a transmission medium, the transmission path through said medium between any transmitter and any receiver, including the associated receiver, having a time delay which is long by comparision with the duration of an information packet, the transmitter-receiver comprising:

transmission means adapted to be coupled to said transmission medium and adapted to be coupled to a source of information to be transmitted for forming said information to be transmitted into information packets having nonumiform duration, and for forming one or more reservation reqeust packets of predetermined duration associated with each of said information packets, which reservation request packets bear information relating to the duration of the associated information packet, and which are intended to reserve an information packet transmission time for said associated information packets which reserved time begins one said predetermined duration following successful reception of said reservation request packets, and for transmitting said reservation request packets at random times;

receiving means adapted to be coupled to said transmission medium for receiving therefrom its own reservation request packets oringinating from said associated transmission means, and other information packets and other reservation request packets originating from other transmitter-receivers;

timing and logic means ocupled to said receiving means and to said transmission means for identifying successful reception of said other reservation request packets and successful reception of said own reservation request packets; and

control and timing means coupled to said transmission means, to said receiving means and to said timing and logic means for inhibiting said transmission means in response to successful reception of each of said other reservation request packets for an original inhibited time period equal to the sum of said predetermined duration plus the information packet duration borne by said other reservation request packet, for extending said original inhibited time period by the information packet duratlion borne by a successfully received other reservation request packet intended for reserving information packet transmission time beginning before the expiration of said original inhibited time period, and for causing said transmission means in response to successful reception of one of said own reservation request packets to transmit said information packet associated with said own reservation request packet beginning at a time which is the later of one said predetermined duration following successful reception of said own reservation request packet and the expiration of one of said original and extended inhibited time periods.

12. A transmitter-receiver for a random access system for burst communications among a plurality of similar associated transmitter-receivers by way of a transmission medium, the transmission path through said medium between any transmitter and any receiver, including the associated receiver, having a time delay which is long by comparision with the duration of an information packet, the transmitter-receiver comprising:

controllable transmission means adapted to be coupled to said transmission medium and adapted to be coupled to a source of information to be transmitted for forming said information to be transmitted into information packets of uniform duration, and for forming one or more reservation request packets of predetermined duration in association with each of said information packets, and for transmitting said reservation request packets so formed at random times;

receiving means adapted to be coupled to said transmission medium for receiving therefrom its own reservation request packets originating from the associated said transmission means, other reservation request packets originating from other transmitter-rceivers of the system, and other information packets originating form other transmitter-receivers of the system;

status deteriming means coupled to said receiving means for producing third and fourth signals indicative of successful reception of said own reservation request packets and said other reservation request packets, respectively, for generating an other reservation request packet collision signal in response to a collision of two or more packets other than said own reservation request packets and, for generating one of a FIRST signal when said own rservation request packet is earliest among a plurality of colliding packets and a LAST signal when said own resrvation request packet is latest among a plurality of colliding packets; and

control means coupled to said status determining means and to said transmission means for inhibiting said transmission means from;

all transmission for a duration plus one said uniform duration in response to said fourth signal, for causing said transmission means to transmit said own information packet beginning at a time delayed from a time maerker by one said predetermined duration in response to one of said third signal and said FIRST signal, for inhibiting said transmission means from all transmission for a duration which is equal to the sum of two said uniform durations plus one said predetermined duration in response to said other reservation request packet collision signal, and for causing said transmission means to transmit said own information packet beginning at a time delayed from said time marker by the sum of said predetermined duration plus one said uniform duration in response to said LAST signal.

13. A method for burst communication among a plurality of similar associated non-relaying transmitter-receivers by way of a transmission medium, the transmission path through said medium between each pair of transmitter-receivers having a time delay which is long by comparision with the duration of an information packet, the method comprising the steps at each transmitter-receiver of:

arranging for the time delays between each pair of transmitter-receivers to be substantially the same,

accepting offered information to be transmitted to form accepted information;

forming said accepted information into information packets to be transmitted;

forming a reservation request packet of predetrmined duration associated with each one of said information packets;

selecting a random time during which any said transmitter-receiver is not inhibited from all transmission for transmitting one of said reservation request packets via said transmission meidum;

transmitting said one of said reservation request packets into the sending end of transmission paths through said transmission medium at said random time;

receiving from said transmission medium own reservation request packets originating from the same transmitter-receiver by which they are received, other reservation request packets originating from transmitter-receivers other than the receiving transmitter-receiver, and information packets;

setting a time marker corresponding to the end of each continuous period of reception which includes a reservation request packet;

inhibiting all transmissions in response to noncolliding reception of one of said other reservation request packets, for a period of time beghinning from said time marker and extending for at least the sum of said predetermined duration plus the duration of that oen of said information packets associated with said one of said other reservation request packet successfully received;

in response to noncolliding reception of an own reservation request packet, transmitting that one of said information packets associated with said own reservation request packet noncollidingly received, beginning at a time delayed from said time marker by at least said predetermined duration.

14. A method according to claim 13, wherein:

said step of forming said accepted information into information packets further comprises the step of forming said information packets with uniform duration; and

further comprising steps of;

inhibiting all transmissions in response to reception of colliding other reservation request packets, for a period of time beginning at said time marker and extending for a duration equal to the sum of one said predetermined duration plus two said uniform durations;

in response to colliding reception of said own reservation request packet determining if said own packet was first, last or neither first nor last in collision;

inhibiting all transmission in response to colliding reception of said own reservation request packet and a determination that said own reservation request packet was one of first and last in collision, for a period extending from said time marker of one said predetermined duration, and immediately thereafter transmitting that one of said information packets associated with said own reservation request packet which was said one of first and last in collision; and

inhibiting all transmission in response to colliding reception of said own reservation request packet and a determination that said own reservation request packet was neither first nor last, for a period extending from said time marker at least equal to the sum of said predetermined duration plus one said uniform duration.

15. A method according to claim 14, further comprising the steps of:

in response to colliding reception of said own reservation request packet and a determination that said own reservation request packet was the other one of first and last in collision, transmitting that one of said information packets associated with said own reservation request packet which was said other one of first and last in collision, beginning at a time following said time marker by the sum of one said predetermined duration plus one said uniform duration; and

in response to colliding reception of said own reservation request packet and a determination that said own reservation request packet was neither first nor last, inhibiting all transmission for a further period of one said uniform duration for a total period of inhibition measured from said time marker of the sum of one said predetermined duration plus tw said uniform durations.

16. A method according to claim 13, wherein:

said step of forming said accepted information into information packets to be transmitted includes the step of forming said information packets to be transmitted with nonuniform duration;

said step of forming a reservation request packet includes the step of loading said reservation request packet with duration information relating to the duration of said nonuniform duration of that information packet associated with said reservation request packet; and

further comprising the step of;

after said receiving step, if possible extracting from said own and said other reservation request packets said duration information borne by said own and other reservation request packets; and

in response to collision of said own packet, whereby said duration information cannot be extracted, retransmitting said own reservation request packet through said transmission medium at a random time during which all transmission is not inhibited.

17. A method according to claim 16, further comprising the steps of:

in response to noncolliding reception of one of said other reservation request packets sequentially received following a prior noncolliding reception of one of said own and said other reservation request packet by a time period less than the duration of that one of said information packets associated with that one of said reservation request packets involved in said prior reception, inhibiting all transmission for a further period equal to the duration of that information packet associated with the second of said sequentially received other reservation request packets; and

in response to noncolliding reception of one of said own reservation request packets sequentially received following a prior noncolliding reception of one of said own and said other reservation request packets by a time period less than the duration of that one of said information packets associated with that one of said reservation request packets involved in said prior reception, transmitting that one of said information packets associated with the second of said sequentially received own reservation request packets.

18. A transmitter-receiver for a random access system for burst communications among a plurality of like transmitter-receivers by way of a transmission medium, each transmission path through said medium between any transmitter and any receiver, including the associated receiver, having a time delay which is long by comparison with the duration of an information packet, the transmitter-receiver comprising:

controllable transmission means coupled to said transmission medium and adpated to be coupled to a source of information to be transmitted for forming said information into information packets having an random duration, for forming one or more reservation request packets associated with each information packet, said reservation request packets including a leading edge, a predetermined duration, and a lagging edge, and time information relating to said duration of said information packet with which they are associated, for controllably transmitting said information packets by way of a path through said transmission meidum, and for one of originally transmitting said reservation request packets and retransmitting said reservation request packets in the form of retransmitted reservation request packets;

receiving means coupled to said transmission medium for receiving from said transmission medium information packets and for also receiving from said transmission medium its own originally transmitted reservation request packets originating from the associated transmission means, other originally transmitted reservation request packets, and other retransmitted reservation request packets originating from other transmitter-receivers in said system, for producing idle signals when each of the transmission paths thereto through said transmission medium is idle and for producing active signals when any said transmission path thereto is active;

timing and logic means coupled to said transmission means and to said receiving means for generating a first signal in response to said idle signal occurring immediately preceding the expected time of reception of a leading edge of each return own reservation request packet, for generating a second signal in response to said active signal occurring immediately preceding said expected time of reception of said leading edge of each returned own reservation request packet, for generating a third signal in response to said active signal immediately following the expected time of receipt of a lagging edge of each returned own reservation request packet, for generating a fourth signal in response to said idle signal occurring immediately following said expected time of receipt of said lagging edge of each said own reservation request packet, for generating a fifth signal in response to said active signals being produced continuously for a period exceeding said predetermined duration, and for generating a timing marker at the moment said active signals are no longer produced; and

control means coupled to said timing and logic means, to said receiving means and to said trransmission means for inhibiting said transmission means in response to said first and fourth signals associated with reception of an other reservation request packet for an inhibited period measured from said timing marker which is at least equal to the sum of said predetermined duration plus said duration indicated by said time information associated with said other reservation request packet, for causing said transmission means to transmit said information packet in response to said first and fourth signals associated with reception of said own reservation request packet beginning at a time measured from said timing marker at least equal to a said predetermined duration, for causing said transmission means to retransmit at a random time said own reservation request packet in response to either of said second and third signals associated with reception of said own packet.