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

• US 7,609,631 B2
• Filed: 02/05/2007
• Issued: 10/27/2009
• Est. Priority Date: 07/26/2002
• Status: Expired due to Fees

• Current Assignee: Gamehancement LLC (Jeffrey M. Gross)
• Original Assignee: Harington Valve LLC (Intellectual Ventures LLC)
• Inventors: Lin, George, Bourlas, Yair, Stanwood, Kenneth
• Primary Examiner(s): Harper; Kevin C
• Application Number:
  US11/671,207
• Publication Number:
  US 20070153690A1
• Time in Patent Office: 995 Days
• Field of Search: 370/328, 370/230, 370/329, 370/431, 370/458
• 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 UBR 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. An apparatus at a customer premises equipment (CPE) transmitting node, the apparatus comprising:

means at the CPE transmitting node for receiving data in frames from a plurality of connections, the plurality of connections being associated with multiple classes of service;

means at the CPE transmitting node for selecting a first data group associated with a first class of service;

means at the CPE transmitting node for allocating bandwidth for the first data group within a first frame to meet a minimum guaranteed rate associated with the first class of service;

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

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

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

2. The apparatus of claim 1 wherein the means for transmitting transmits 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 apparatus of claim 1 wherein the means for transmitting transmits a logical representation of the data to the first receiving node;

and wherein the means for receiving receives a scheduling map, the scheduling map including bandwidth allocations for the first data group, the second data group, and the excess demand in the first frame.

4. An apparatus, comprising:

means for receiving data from one or more customer premises equipment (CPE) stations associated with a plurality of connections, the connections being associated with a plurality of classes of service;

means at a base station for determining a first uplink schedule for a first group of the connections up to committed rates associated with the connections, the means for determining using a first allocation scheme with a first priority applied between at least two of the plurality of classes of service;

wherein the means for determining determines at the base station a second uplink schedule for a second group of the connections, the second group of connections including one or more connections of the first group and the second group of connections requesting additional allocation in excess of associated ones of the committed rates that are within peak allowed rates, wherein the means for determining determines the second uplink schedule using a second allocation scheme, wherein the plurality of classes have equal priority;

means for notifying the one or more CPE stations of the first and second uplink schedules; and

means for normalizing data from the one or more CPE stations to a common modulation.

5. The apparatus of claim 4, and further comprising means for associating at least one queue with one or more of the connections.

6. The apparatus of claim 4, wherein the first priority includes a strict priority between at least two of the plurality of classes of service.

7. The apparatus of claim 4, wherein the first priority includes a modified strict priority between at least two of the plurality of classes of service.

8. The apparatus of claim 4, wherein the first allocation scheme includes an allocation scheme selected from a group consisting essentially of round robin, weighted round robin, deficit round robin, and weighted fair queuing.

9. The apparatus of claim 4, wherein the second allocation scheme includes an allocation scheme selected from a group consisting essentially of round robin, weighted round robin, deficit round robin, and weighted fair queuing.

10. An apparatus at a base station, the apparatus comprising:

means for receiving connection data at the base station;

means at the base station for selecting a first portion of the connection data that is associated with a first class of service using a first scheduling technique;

means at the base station for allocating bandwidth within a first frame for transmitting the first portion to a customer premises equipment (CPE) station for meeting a first minimum guaranteed data rate associated with the first class of service;

wherein the means for selecting selects a second portion of the connection data that is associated with a second class of service using a second scheduling technique and wherein the means for allocating allocates bandwidth within the first frame for transmitting the second portion to the CPE station for meeting a second minimum guaranteed data rate associated with the second class of service subject to an availability of bandwidth in the first frame following the allocation of the bandwidth for transmission of the first portion;

means at the base station for grouping a third portion of the connection data that includes an excess portion of the connection data; and

wherein the means for allocating allocates bandwidth within the first frame for transmitting the third portion to the CPE station subject to an availability of bandwidth in the first frame following the allocation of the bandwidth for transmission of the second portion; and

means at the base station for transmitting the first, second, and third portions, based on their respective the allocated bandwidth, during the first frame to the CPE station.

11. A system, comprising:

a customer premises equipment (CPE) station having a plurality of queues to store data from associated connections for transmission to an associated base station in allocatable time slots of frames transmitted in at least one of a plurality of uplink communication channels, one or more of the connections being associated with one of a plurality of classes of service, the 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 the first and second classes of service among the plurality of classes of service;

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

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

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

12. The system of claim 11, further comprising a communication hub adapted to provide a video delivery service to one or more subscribers.

13. The system of claim 11, further comprising a communication hub adapted to provide a telephony service to one or more subscribers.

19. The system of claim 11, further comprising a communication hub coupled to the base station by a back haul, the communication hub being adapted to provide Internet access to one or more subscribers at the CPE stations.

14. A system, comprising:

one or more customer premises equipment (CPE) stations adapted to receive connection data from a base station through a downlink portion of a wireless communication link, wherein the base station is coupled to a communication hub by a back haul, the communication hub being adapted to provide Internet access to one or more subscribers at the one or more CPE stations;

wherein the base station is configured to;

receive the connection data from the back haul;

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

allocate bandwidth in the downlink portion within a first frame for transmission of the first portion to meet a first minimum guaranteed data rate associated with the first class of service;

select a second portion of the received connection data that is associated with a second class of service using a second scheduling technique and allocate bandwidth within the first frame for transmission of the second portion to meet a second minimum guaranteed data rate associated with the second class of service, wherein the allocation of bandwidth for transmission of the second portion is subject to an availability of bandwidth in the first frame following the allocation of the bandwidth for transmission of the first portion;

group a third portion of the connection data that includes an excess portion of the connection data; and

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

transmit the first, second, and third portions, based on their respective allocated bandwidth, during the first frame to the one or more CPEs.

15. The system of claim 14, wherein the communication hub is further adapted to provide a video delivery service to the one or more subscribers.

16. The system of claim 15, wherein the communication hub is further adapted to provide a telephony service to the one or more subscribers.

17. A base station, comprising:

a transmitter to transmit connection data in a downlink portion of a wireless communication link to one or more customer premises equipment (CPE) stations; and

a computing device adapted to;

allocate bandwidth in the downlink portion within a first frame for transmission of a first portion of the connection data using a first scheduling technique, the first portion of the connection data being associated with a first class of service, to meet a first minimum guaranteed data rate associated with the first class of service;

allocate bandwidth within the first frame for transmission of a second portion of the connection data using a second scheduling technique, the second portion of the connection data being associated with a second class of service, to meet a second minimum guaranteed data rate associated with the second class of service, wherein the allocation of bandwidth for transmission of the second portion is subject to an availability of bandwidth in the first frame following the allocation of the bandwidth for transmission of the first portion; and

allocate bandwidth within the first frame for transmission of the third portion subject to an availability of bandwidth in the first frame following the allocation of the bandwidth for transmission of the second portion.

18. A customer premises equipment (CPE) station, comprising:

a plurality of queues to store data from associated connections for transmission to a base station in allocatable time slots of frames for transmission in an uplink communication channel, one or more of the connections being associated with one of a plurality of classes of service; and

a computing device adapted to;

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

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

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

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