Method and system for providing satellite bandwidth on demand using multi-level queuing

• US 6,985,455 B1
• Filed: 08/02/2000
• Issued: 01/10/2006
• Est. Priority Date: 03/03/2000
• Status: Expired due to Term

• Current Assignee: Hughes Network Systems LLC (Echostar Corporation)
• Original Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Inventors: Torres, Robert J., Demers, Stephanie, Heath, Robert Jeff, Ramaswamy, Sreenivas
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Moore, Ian N.
• Application Number:
  US09/631,269
• Time in Patent Office: 1,987 Days
• Field of Search: 370/351, 370/395.1, 370/395.2, 370/395.21, 370/395.41, 370/395.42, 370/43, 370310-319, 370321-323, 370325-346, 370/229, 370230-234, 370/468, 370/437, 370412-420, 370/428, 370/429, 370/401, 455/450, 455/12.1, 455/452.2, 714/42, 395/183.18, 710/57, 710240-243, 710/52, 710/53, 710/65, 710/66, 710/68, 710/316, 710/26, 710/3
• US Class Current: 370/316
• CPC Class Codes: H04B 7/1858 Arrangements for data transmission on the physical system, i.e. for data bit transmission between network components

Abstract

An approach for allocating bandwidth in a satellite communication system is disclosed. The system includes a set of global queues that store bandwidth requests, which are received from a number of satellite terminals. The received bandwidth request include a high priority rate request, a low priority rate request, a high priority volume request, and a low priority volume request. A bandwidth control processor determines bandwidth request type and priority of the received bandwidth requests and places the bandwidth requests in the appropriate global queues based upon the determined bandwidth request type and priority. Each of the global queues corresponds to a data rate associated with of each a plurality of channels. The system also utilizes a set of local queues that correspond to the channels. The BCP moves the bandwidth requests from the global queues to the local queues. The BCP then allocates the transmission slots in response to the bandwidth requests stored in the local queues.

Claims

1. A method of performing bandwidth allocations, the method comprising:

receiving a bandwidth request from a terminal, wherein the bandwidth request includes a rate request;

determining bandwidth request type and priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channels;

filling the one local queue with subsequent rate requests up to a queuing threshold that is dynamically established according to a total number of rate requests in the local queues;

filling another one of the local queues with additional rate requests upon filling the one local queue beyond the queuing threshold; and

allocating transmission slots in response to the bandwidth request stored in the one local queue.

2. The method as in claim 1, wherein the bandwidth request includes a volume request, the rate request specifying a constant number of transmission slots, the volume request specifying a specific number of transmission slots.

3. The method as in claim 1, wherein the queuing threshold in the step of filling the one local queue is predetermined.

4. The method as in claim 1, wherein the global queues in the placing step are designated according to the bandwidth request type and the associated priority.

5. The method as in claim 1, wherein the bandwidth request type and priority of the received bandwidth request include a high priority rate request, a low priority rate request, a high priority volume request, and a low priority volume request.

6. The method as in claim 1, wherein the bandwidth request in the receiving step includes a volume request and is received over at least one of a contention channel or a data channel, the method further comprising:

receiving a piggybacked volume request over the data channel;

placing the piggybacked volume request in a corresponding one of the global queues;

determining whether the plurality of channels are oversubscribed; and

selectively discarding the piggybacked volume request based upon the step of determining whether the plurality of channels are oversubscribed.

7. The method as in claim 6, wherein the step of determining whether the plurality of channels are oversubscribed comprises:

determining whether each of the plurality of local queues exceeds a respective queuing threshold.

8. The method as in claim 1, wherein the plurality of channels are designated as data channels that are sequentially ordered, the allocating step comprising:

selectively assigning the transmission slots according to a prescribed order of the data channels based upon the bandwidth request type.

9. The method as in claim 8, wherein the prescribed order in the selectively assigning step begins with the first data channel if the bandwidth request type is rate request.

10. The method as in claim 8, wherein the prescribed order in the selectively assigning step begins with the last data channel if the bandwidth request type is volume request.

12. The method as in claim 1, wherein the bandwidth request is an original volume request, the method further comprising:

receiving a follow-up volume request;

associating the follow-up volume request with the original volume request; and

placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues.

14. The method as in claim 1, further comprising:

receiving a plurality of volume requests; and

spreading the volume requests across each of the local queues.

15. The method as in claim 14, wherein each of the local queues has a counter that counts a quantity of the volume requests in the respective local queue, the distributing step comprising:

comparing counter values of the counters with respective predetermined thresholds corresponding to the local queues.

11. A method of performing bandwidth allocations, the method comprising:

receiving a bandwidth request from a terminal;

determining bandwidth request type and Priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channels;

allocating transmission slots in response to the bandwidth request stored in the one local queue;

receiving a plurality of rate requests;

receiving a defragmentation command; and

moving the rate requests from the local queues to the corresponding global queues for reallocation in response to the defragmentation command.

13. A method of performing bandwidth allocations, the method comprising:

receiving a bandwidth request from a terminal, wherein the bandwidth request includes an original volume request;

determining bandwidth request type and priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channel;

allocating transmission slots in response to the bandwidth request stored in the one local queue;

receiving a follow-up volume request;

associating the follow-up volume request with the original volume request;

placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues; and

maintaining a database of pointers for the terminal, one of the pointers specifying the particular local queue.

16. A communication system for performing bandwidth allocations, the system comprising:

a plurality of global queues, each of the global queues being configured to store a bandwidth request received from a terminal, wherein the bandwidth request includes a rate request;

a bandwidth control processor (BCP) coupled the plurality of global queues, the bandwidth control processor being configured to determine bandwidth request type and priority of the received bandwidth request and to place the bandwidth request in one of a plurality of a global queues based upon the determined bandwidth request type and priority, wherein each of the global queues corresponds to a data rate of each of a plurality of channels; and

a plurality of local queues coupled to the BCP, the plurality of local queues corresponding to the plurality of channels, one of the plurality of local queues storing the bandwidth request which is moved from the one global queue based on loading of the channels, the one local queue being filled with subsequent rate requests up to a queuing threshold that is dynamically established according to a total number of rate requests in the local queues, another one of the local queues being filled up with additional rate requests in response to the one local queue being filled beyond the queuing threshold,

wherein the BCP allocates transmission slots in response to the bandwidth request stored in the one local queue.

17. The system as in claim 16, wherein the bandwidth request includes a volume request, the rate request specifying a constant number of transmission slots, the volume request specifying a specific number of transmission slots.

18. The system as in claim 16, wherein the queuing threshold is predetermined.

19. The system as in claim 16, wherein the global queues are designated according to the bandwidth request type and the associated priority.

20. The system as in claim 16, wherein the bandwidth request type and priority of the received bandwidth request include a high priority rate request, a low priority rate request, a high priority volume request, and a low priority volume request.

21. The system as in claim 16, wherein the bandwidth request includes a volume request and is received over at least one of a contention channel or a data channel, a follow-up volume request associated with the volume request being placed in a corresponding one of the global queues, the BCP selectively discarding the follow-up volume request upon determining that the plurality of channels are oversubscribed.

22. The system as in claim 21, wherein the BCP determines oversubscription of the plurality of channels by examining whether each of the plurality of local queues exceeds a respective queuing threshold.

23. The system as in claim 16, wherein the plurality of channels are designated as data channels that are sequentially ordered, the BCP selectively assigning the transmission slots according to a prescribed order of the data channels based upon the bandwidth request type.

24. The system as in claim 23, wherein the prescribed order begins with the first data channel if the bandwidth request type is rate request.

25. The system as in claim 23, wherein the prescribed order begins with the last data channel if the bandwidth request type is volume request.

27. The system as in claim 16, wherein the bandwidth request is an original volume request, the BCP associating a follow-up volume request with the original volume request and placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues.

29. The system as in claim 16, wherein one of the global queues stores a plurality of volume requests, the BCP spreading the volume requests across the local queues.

30. The system as in claim 29, wherein each of the local queues has a counter that counts a quantity of the volume requests in the respective local queue, the BCP comparing counter values of the counters with predetermined thresholds corresponding to the local queues.

26. A communication system for performing bandwidth allocations, the system comprising:

a plurality of global queues, each of the global queues being configured to store a bandwidth request received from a terminal;

a bandwidth control processor (BCP) coupled the plurality of global queues, the bandwidth control processor being configured to determine bandwidth request type and priority of the received bandwidth request and to place the bandwidth request in one of a plurality of a global queues based upon the determined bandwidth request type and priority wherein each of the global queues corresponds to a data rate of each of a plurality of channels; and

a plurality of local queues coupled to the BCP, the plurality of local queues corresponding to the plurality of channels, one of the plurality of local queues storinq the bandwidth request which is moved from the one global queue based on loading of the channels, wherein the BCP allocates transmission slots in response to the bandwidth request stored in the one local queue,

wherein the BCP is configured to move rate requests from the local queues to the corresponding global queues for reallocation in response to a defragmentation command.

28. A communication system for performing bandwidth allocations, the system comprising:

a plurality of global queues, each of the global queues being configured to store a bandwidth request received from a terminal;

a bandwidth control processor (BCP) coupled the plurality of global queues, the bandwidth control processor being configured to determine bandwidth request type and priority of the received bandwidth request and to place the bandwidth request in one of a plurality of a global queues based upon the determined bandwidth request type and priority, wherein each of the global queues corresponds to a data rate of each of a plurality of channels; and

a plurality of local queues coupled to the BCP, the plurality of local queues corresponding to the plurality of channels, one of the plurality of local queues storing the bandwidth request which is moved from the one global queue based on loading of the channels, wherein the BCP allocates transmission slots in response to the bandwidth request stored in the one local queue, wherein the bandwidth request includes an original volume request, the BCP associating a follow-up volume request with the original volume request and placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues; and

a database coupled to the BCP, the database storing a plurality of pointers for the terminal, one of the pointers specifying the particular local queue.

31. A computer readable medium containing program instructions for execution on a computer system, which when executed by a computer, cause the computer system to perform method steps for allocating bandwidth, said method comprising the steps of:

receiving a bandwidth request from a terminal, wherein the bandwidth request includes a rate request;

determining bandwidth request type and priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channels;

filling the one local queue with subsequent rate requests up to a queuing threshold that is dynamically established according to a total number of rate requests in the local queues;

filling another one of the local queues with additional rate requests upon filling the one local queue beyond the queuing threshold; and

allocating transmission slots in response to the bandwidth request stored in the one local queue.

32. The computer-readable medium as in claim 31, wherein the bandwidth request includes a volume request, the rate request specifying a constant number of transmission slots, the volume request specifying a specific number of transmission slots.

33. The computer-readable medium as in claim 31, wherein the queuing threshold in the step of filling the one local queue is predetermined.

34. The computer-readable medium as in claim 31, wherein the global queues in the placing step are designated according to the bandwidth request type and the associated priority.

35. The computer-readable medium as in claim 31, wherein the bandwidth request type and priority of the received bandwidth request include a high priority rate request, a low priority rate request, a high priority volume request, and a low priority volume request.

36. The computer-readable medium as in claim 31, wherein the bandwidth request in the receiving step includes a volume request and is received over at least one of a contention channel or a data channel, the computer-readable medium further comprising computer-executable instructions for causing the computer system to perform the steps of:

receiving a piggybacked volume request over the data channel;

placing the piggybacked volume request in a corresponding one of the global queues;

determining whether the plurality of channels are oversubscribed; and

selectively discarding the piggybacked volume request based upon the step of determining whether the plurality of channels are oversubscribed.

37. The computer-readable medium as in claim 36, wherein the step of determining whether the plurality of channels are oversubscribed comprises:

determining whether each of the plurality of local queues exceeds a respective queuing threshold.

38. The computer-readable medium as in claim 31, wherein the plurality of channels are designated as data channels that are sequentially ordered, the allocating step comprising:

selectively assigning the transmission slots according to a prescribed order of the data channels based upon the bandwidth request type.

39. The computer-readable medium as in claim 38, wherein the prescribed order in the selectively assigning step begins with the first data channel if the bandwidth request type is rate request.

40. The computer-readable medium as in claim 38, wherein the prescribed order in the selectively assigning step begins with the last data channel if the bandwidth request type is volume request.

42. The computer-readable medium as in claim 31, wherein the bandwidth request is an original volume request, the computer-readable medium further comprising computer-executable instructions for causing the computer system to perform the steps of:

receiving a follow-up volume request;

associating the follow-up volume request with the original volume request; and

placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues.

44. The computer-readable medium as in claim 31, further comprising computer-executable instructions for causing the computer system to perform the steps of:

receiving a plurality of volume requests; and

spreading the volume requests across each of the local queues.

45. The computer-readable medium as in claim 44, wherein each of the local queues has a counter that counts a quantity of the volume requests in the respective local queue, the distributing step comprising:

comparing counter values of the counters with respective predetermined thresholds corresponding to the local queues.

41. A computer readable medium containing program instructions for execution on a computer system, which when executed by a computer, cause the computer system to perform method steps for allocating bandwidth, said method comprising the steps of:

receiving a bandwidth request from a terminal;

determining bandwidth request type and priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channels;

allocating transmission slots in response to the bandwidth request stored in the one local queue;

receiving a plurality of rate requests;

receiving a defragmentation command; and

moving the rate requests from the local queues to the corresponding global queues for reallocation in response to the defragmentation command.

43. A computer readable medium containing program instructions for execution on a computer system, which when executed by a computer, cause the computer system to perform method steps for allocating bandwidth, said method comprising the steps of:

receiving a bandwidth request from a terminal, wherein the bandwidth request includes an original volume request;

determining bandwidth request type and priority of the received bandwidth request;

placing the bandwidth request in one of a plurality of a global queues based upon the determining step, each of the global queues corresponding to a data rate of each of a plurality of channels;

moving the bandwidth request from the one global queue to one of a plurality of local queues, the plurality of local queues corresponding to the plurality of channels, wherein the bandwidth request is moved based on loading of the channels;

allocating transmission slots in response to the bandwidth request stored in the one local queue;

receiving a follow-up volume request;

associating the follow-up volume request with the original volume request;

placing the follow-up volume request to a particular local queue that stored the original bandwidth request among the plurality of local queues; and

maintaining a database of pointers for the terminal, one of the pointers specifying the particular local queue.