Priority-based bandwidth allocation and bandwidth-on-demand in a low-earth-orbit satellite data communication network

• US 6,366,761 B1
• Filed: 10/06/1998
• Issued: 04/02/2002
• Est. Priority Date: 10/06/1998
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Teledesic, LLC (Michael J. Larson, MBA)
• Inventors: Montpetit, Marie-José
• Primary Examiner(s): Bost, Dwayne
• Assistant Examiner(s): CRAVER, CHARLES R
• Application Number:
  US09/167,410
• Time in Patent Office: 1,274 Days
• Field of Search: 455/427, 455/428, 455/429, 455/430, 455/12.1, 455/13.1, 455/13.2, 455/434, 455/445, 455/446, 455/447, 455/450, 455/453, 455/455, 370/230, 370/232, 370/236, 370/316, 370/321, 370/322, 370/347, 370/348, 370/412-418, 370/436, 370/442-444, 370/437, 370/458-461
• US Class Current: 455/12.1
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00
• CPC Class Codes: H04B 7/195 Non-synchronous stations

Abstract

A data communication system and method that allocates an amount of bandwidth to a ground terminal for uplink transmission of one or more data packets in a low-Earth-orbit (LEO) satellite data communication network. A bandwidth request message is generated and transmitted to a bandwidth allocation processing unit in the LEO satellite data communication network. The bandwidth request message requests allocation of an amount of bandwidth to a ground terminal for uplink transmission of one or more data packets and identifies a priority status of the data packets for which bandwidth is sought. The bandwidth allocation processing unit allocates bandwidth to the ground terminal in accordance with the priority status identified in the bandwidth request message. Allocated bandwidth is reported to the ground terminal in a bandwidth allocation response. If sufficient bandwidth is not available to satisfy a bandwidth request message, the bandwidth request may be denied or a partial allocation of bandwidth may be permitted. Furthermore, bandwidth allocated for transmission of data packets having a lower priority status may be preempted in favor of bandwidth for transmitting data packets having a higher priority status. Bandwidth allocation is managed using a data structure having a number of slots that represent portions of the bandwidth which are selectively allocated to ground terminals for uplink transmission of data packets.

Claims

1. A method of allocating bandwidth for uplink transmission of one or more data packets in a non-geosynchronous orbit (NGSO) satellite data communication network, comprising:

(a) generating a bandwidth request message requesting allocation of an amount of bandwidth to a ground terminal for uplink transmission of one or more data packets, each of the one or more data packets individually having a priority status assigned thereto, the bandwidth request message identifying the priority status of the data packets for which bandwidth is sought;

(b) transmitting the bandwidth request message to a bandwidth allocation processing unit;

(c) processing the bandwidth request message at the bandwidth allocation processing unit to allocate bandwidth to the ground terminal in accordance with the priority status identified in the bandwidth request message, the processing producing an allocation outcome;

(d) generating a bandwidth allocation response reporting the allocation outcome; and

(e) transmitting the bandwidth allocation response to the ground terminal.

2. The method of claim 1, wherein a bandwidth request message identifying a higher priority status is processed before a bandwidth request message identifying a lower priority status.

3. The method of claim 1, wherein processing the bandwidth request message includes:

(a) defining a data structure that represents the bandwidth for uplink transmission of data packets, wherein the data structure includes a plurality of slots that represent portions of the bandwidth;

(b) selecting one or more slots in the data structure to be allocated to the ground terminal, wherein the number of slots selected is based on the amount of bandwidth requested in the bandwidth request message; and

(c) allocating the selected one or more slots to the ground terminal, thereby allocating the portion of bandwidth represented by the one or more slots to the ground terminal for uplink transmission of data packets having the priority status identified in the bandwidth request message.

4. The method of claim 3, wherein each slot of the plurality of slots represents both a time portion and a frequency portion of the bandwidth.

5. The method of claim 4, wherein the data structure is a table indexed in a first dimension by time portions of the bandwidth and in a second dimension by frequency portions of the bandwidth.

6. The method of claim 4, wherein selecting a slot in the data structure includes:

(a) searching the data structure for an unallocated slot;

(b) if an unallocated slot is found, determining whether the unallocated slot may be allocated to the ground terminal; and

(c) selecting the unallocated slot if the unallocated slot may be allocated to the ground terminal.

7. The method of claim 6, wherein determining whether the unallocated slot may be allocated to the ground terminal includes determining whether the ground terminal has already been allocated a slot that represents a time portion of the bandwidth that overlaps the time portion represented by the unallocated slot.

8. The method of claim 6, wherein determining whether the unallocated slot may be allocated to the ground terminal includes determining whether the unallocated slot represents a frequency portion of the bandwidth that is different from a frequency portion represented by a slot already allocated to the ground terminal for a different time portion of the bandwidth.

9. The method of claim 3, further including:

(a) if the number of slots selected does not satisfy the amount of bandwidth requested in the bandwidth request message, determining whether a partial bandwidth allocation is permitted;

(b) if partial bandwidth allocation is permitted, allocating the selected slots to the ground terminal; and

(c) retaining the bandwidth request for reprocessing, wherein the amount of bandwidth requested by the bandwidth request message is reduced by the amount of bandwidth represented by the selected slots that were allocated.

10. The method of claim 9, wherein partial bandwidth allocation is permitted only for transmission of data packets having a low priority status identified in the bandwidth request message.

11. The method of claim 3, wherein selecting a slot in the data structure includes:

(a) searching the data structure for an allocated slot;

(b) if an allocated slot is found, determining whether the allocation of the slot may be preempted in favor of allocation to the ground terminal to satisfy the bandwidth request message being processed;

(c) if the allocation of the slot may be preempted, deallocating the allocated slot; and

(d) selecting the deallocated slot.

12. The method of claim 11, wherein determining whether the allocation of the slot may be preempted includes determining whether the priority status of the data to be transmitted using the allocated slot is lower than the priority status identified in the bandwidth request message.

13. The method of claim 11, wherein the allocation of a slot may be preempted only for transmission of data packets having a high priority status identified in the bandwidth request message.

14. The method of claim 11, further comprising selecting and allocating another slot in the data structure to replace the bandwidth allocation of the preempted slot.

15. The method of claim 1, wherein the bandwidth allocation processing unit is implemented onboard a NGSO satellite in the NGSO satellite data communication network.

16. The method of claim 1, wherein the bandwidth allocation processing unit is implemented in a bandwidth processing terminal on the Earth and a message notifying of allocated bandwidth is periodically transmitted by the bandwidth processing terminal to the NGSO satellite whose bandwidth is being allocated.

17. The method of claim 1, wherein the amount of bandwidth requested in the bandwidth request message represents a rate of data packet transmission, and wherein bandwidth allocated for a rate of data packet transmission remains allocated until specifically deallocated.

18. The method of claim 1, wherein the amount of bandwidth requested in the bandwidth request message represents a volume of data packets to be transmitted, and wherein bandwidth is allocated for transmission of a volume of data packets having a high priority status only if the requested bandwidth can be fully allocated in a single frame.

19. The method of claim 1, wherein a bandwidth request message requesting bandwidth for a ground terminal that does not have an existing bandwidth allocation is processed before a bandwidth request message requesting bandwidth for a ground terminal that already has an existing bandwidth allocation.

20. The method of claim 1, wherein a bandwidth request message is generated in response to data packets placed in a data packet send queue that exceed a threshold set for the data packet send queue.

21. The method of claim 1, wherein the bandwidth allocation response is transmitted to a number of ground terminals and the ground terminal to which the bandwidth allocation response is directed acts upon the bandwidth allocation response while the remaining ground terminals receiving the transmission ignore the bandwidth allocation response.

22. The method of claim 1, wherein the bandwidth request message is processed at the bandwidth allocation processing unit in accordance with programmable rules stored in a memory accessible to the bandwidth allocation processing unit.

23. A data communication system for a non-geosynchronous orbit (NGSO) satellite data communication network, comprising:

(a) one or more ground terminals that generate and transmit bandwidth request messages to a bandwidth allocation processing unit to obtain allocation of an amount of bandwidth for uplink transmission of data packets, each of the data packets individually having a priority status assigned thereto; and

(b) a bandwidth allocation processing unit for allocating bandwidth to the one or more ground terminals in response to transmitted bandwidth request messages, wherein a bandwidth request message identifies the priority status of the data packets to be transmitted, and wherein bandwidth is allocated in accordance with the amount of bandwidth and priority status identified in the bandwidth request message.

24. The data communication system of claim 23, wherein the bandwidth allocation processing unit is implemented onboard a NGSO satellite in the NGSO satellite data communication network.

25. The data communication system of claim 24, wherein bandwidth request messages transmitted to the NGSO satellite are entered into a queue in a memory accessible to the bandwidth allocation processing unit implemented onboard the satellite.

26. The data communication system of claim 25, wherein the memory includes multiple queues and bandwidth request messages are entered into a queue corresponding to the priority status identified in the bandwidth request messages.

27. The data communication system of claim 23, wherein the bandwidth allocation processing unit is implemented in a bandwidth processing terminal on the Earth and a message notifying of allocated bandwidth is periodically transmitted by the bandwidth