Scheduling method and system for communication systems that offer multiple classes of service

• US 7,177,275 B2
• Filed: 07/26/2002
• Issued: 02/13/2007
• Est. Priority Date: 07/26/2002
• Status: Expired due to Term

• Current Assignee: Gamehancement LLC (Jeffrey M. Gross)
• Original Assignee: Harington Valve LLC (Intellectual Ventures LLC)
• Inventors: Bourlas, Yair, Lin, George, Stanwood, Kenneth
• Primary Examiner(s): Harper; Kevin C.
• Application Number:
  US10/207,648
• Publication Number:
  US 20040017825A1
• Time in Patent Office: 1,663 Days
• Field of Search: 370/328, 370/431, 370442-444, 370458-459, 370229-230, 370/468
• US Class Current: 370/230
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 72/569 of the traffic information

Abstract

A method and system for prioritizing connection data that is associated with different classes of service for transmission in a frame based communication system. These classes of service can include CBR, nrt-VBR, MGR, and UPR traffic. One embodiment of the scheduling method and system uses hierarchical round-robin (HRR) with deficit round-robin (DRR). In this embodiment, the scheduling method and system guarantees minimum rates of nrt-VBR and MGR traffic to the connections. The excess bandwidth is then fairly allocated between the existing connections and their classes of service. For example, the excess is allocated for UBR traffic and for the excess demands of the nrt-VBR and MGR connections. In one embodiment, the scheduling method and system allocates the excess bandwidth in a frame to the existing connections using weighted round robin to differentiate between different classes of service. In one embodiment, excess allocation to nrt-VBR and MGR connections is rolled back into the deficit counters for the minimum guaranteed rates of nrt-VBR and MGR connections.

Claims

1. A method of scheduling data from a plurality of connections for transmission in a frame based communication system and between a transmitting node and at least one receiving node, the plurality of connections being associated with multiple classes of service, the method comprising:

receiving data from the plurality of connections at the transmitting node;

selecting a first data group that is associated with a first class of service from the data;

allocating bandwidth for the first data group within a first frame to meet a minimum guaranteed data rate associated with said first class of service;

allocating bandwidth for a second data group associated with a second class of service within the first frame to meet a minimum guaranteed rate associated with said second class of service subject to an availability of bandwidth in said first frame following said allocation of bandwidth for said first data group;

allocating bandwidth within the first frame for transmitting excess demand subject to an availability of bandwidth in said first frame following said allocation of bandwidth for said second group; and

transmitting the first data group, the second data group, and the excess demand to a first receiving node during the first frame.

2. The method of claim 1, further comprising transmitting the first data group, the second data group, and the excess demand to a second receiving node, the plurality of connections being associated with the first and second receiving nodes.

3. The method of claim 1, further comprising:

transmitting a logical representation of the data to the receiving node; and

transmitting a scheduling map to the transmitting node, the scheduling map comprising bandwidth allocations for the first data group, the second data group, and the excess demand in the first frame.

4. A method of scheduling uplink transmission data from customer premise equipment (CPEs) by a base station using hierarchical round-robin scheduling comprising:

receiving data from connections at the CPEs, the connections being associated with a plurality of classes;

storing the data at each CPE;

transmitting a representation of the received data to the base station;

determining a first uplink schedule at the base station for a first group of the connections up to each connection'"'"'s committed rate using a first allocation scheme with a first priority applied between at least two of the plurality of classes;

determining a second uplink schedule at the base station for a second group of the connections, which comprise one or more of the connections from the first group, which request additional allocation in excess of the committed rates that are within peak allowed rates using a second allocation scheme, wherein the plurality of classes have equal priority;

notifying the CPEs of the first and second uplink schedules; and

normalizing the data from each CPEs current modulation to a common modulation.

5. The method of claim 4, wherein storing the data comprises assigning at least one queue to each of at least some of the connections.

6. The method of claim 4, wherein the logical representation comprises bandwidth requests from the connections.

7. The method of claim 4, wherein the first priority comprises a strict priority between at least two of the plurality of classes.

8. The method of claim 4, wherein the first priority comprises a modified strict priority between at least two of the plurality of classes.

9. The method of claim 4, wherein the first allocation scheme comprises round robin, weighted round robin, deficit round robin, or weighted fair queuing.

10. The method of claim 4, wherein the second allocation scheme comprises round robin, weighted round robin, deficit round robin, or weighted fair queuing.

11. The method of claim 4, further comprising normalizing the data from each CPE'"'"'s current PHY mode to a PHY unit.

12. The method of claim 11, wherein the PHY unit is modulation symbols.

13. A method of scheduling data for downlink transmission in a communication system which uses multiple modulations, wherein a base station transmits connection data that is associated with more than one modulation technique to more than one CPE, the method comprising:

receiving connection data at the base station;

storing the connection data;

selecting a first portion of the connection data that is associated with a first class of service using a first scheduling technique;

allocating bandwidth within a first frame for transmitting the first portion to meet a first minimum guaranteed data rate associated with said first class of service;

selecting a second portion of the connection data that is associated with a second class of service using a second scheduling technique and allocating bandwidth within the first frame for transmitting the second portion to meet a second minimum guaranteed data rate associated with said second class of service subject to an availability of bandwidth in said first frame following said allocation of said bandwidth for transmission of said first portion,

grouping a third portion of the connection data comprising an excess portion of the connection data and

allocating bandwidth within the first frame for transmitting the third portion subject to an availability of bandwidth in said first frame following said allocation of said bandwith for transmission of said second portion; and

transmitting the first, second, and third portions during the first frame to the CPEs.

14. A system comprising:

a base station capable of receiving information on one or more uplink communication channels; and

a CPE station comprising a plurality of queues for storing data from associated connections for transmission to said base station in allocatable time slots of frames transmitted in at least one of said uplink communication channels, one or more of said connections being associated with one of a plurality of classes of service, said CPE station being adapted to;

establish a priority between at least first and second classes of service based, at least in part, on a ranking of said first and second classes of service among said plurality of classes of service;

allocate time slots of a frame in said at least one of said uplink communication channels to a one or more of said queues associated with a first group of said connections associated with said first class of service to meet a data rate commitment associated with said first group of said connections;

allocate time slots of said frame to one or more of said queues associated with a second group of said connections associated with said second class of service to meet a data rate commitment associated with said second group of said connections; and

allocate any remaining time slots of said frame between said first and second groups of connections according to said priority between said at least first and second classes of service.

15. The system of claim 14, wherein said priority comprises a strict priority.

16. The system of claim 14, wherein said priority comprises a modified strict priority.

17. The system of claim 14, wherein said CPE station is further adapted to allocate time slots among queues associated with said first group of connections according to a round robin allocation scheme.

18. The system of claim 14, wherein said CPE station is further adapted to allocate time slots among queues associated with said first group of connections according to a weighted round robin scheme.

19. The system of claim 14, wherein said CPE station is further adapted to allocate time slots among queues associated with said first group of connections according to a deficit round robin scheme.