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

• US 20040017825A1
• Filed: 07/26/2002
• Published: 01/29/2004
• Est. Priority Date: 07/26/2002
• Status: Active Grant

• Current Assignee: Gamehancement LLC (Jeffrey M. Gross)
• Original Assignee: Harington Valve LLC (Intellectual Ventures LLC)
• Inventors: Bourlas, Yair, Lin, George, Stanwood, Kenneth
• Granted Patent: US 7,177,275 B2
• Time in Patent Office: Days
• US Class Current: 370/468
• 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 a 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 group within a first frame;

determining whether additional bandwidth is available in the first frame,

if bandwidth is available,

then selecting a second data group that is associated with a second class of service from the data,

allocating bandwidth for the second group within the first frame,

if bandwidth is available in the frame after the second group is allocated,

then grouping excess demand from the first and second classes of service,

allocating bandwidth within the first frame for transmitting the excess demand; 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 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; and

notifying the CPEs of the first and second uplink schedules.

5. The method of claim 4, wherein storing the data comprises assigning queues to each 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 is a strict priority between the plurality of classes.

8. The method of claim 4, wherein the first priority is a modified strict priority between the plurality of classes.

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

10. The method of claim 4, wherein the second scheme is 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 CPEs current modulation to a common modulation.

12. The method of claim 4, further comprising normalizing the data from each CPEs current PHY mode to a PHY unit.

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

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

receiving data from connections at a CPE;

storing the data at the CPE;

determining a first uplink schedule 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 a plurality of classes;

determining a second uplink schedule 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; and

transmitting the received data for the first and second groups to the base station.

15. The method of claim 14, wherein the first allocation scheme is round robin, weighted round robin, deficit round robin, or weighted fair queuing.

16. The method of claim 14, wherein the second allocation scheme is round robin, weighted round robin, deficit round robin, or weighted fair queuing.

17. 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;

if bandwidth is available in the frame after the first portion is allocated,

then 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,

if bandwidth is available in the frame after the second portion is allocated,

then grouping an excess portion of the connection data,

selecting a third portion of the excess portion using a first scheduling technique and

allocating bandwidth within the first frame for transmitting the third portion; and

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

18. A method of scheduling transmission data for an existing group of connections using hierarchical round-robin scheduling comprising:

scheduling bandwidth for a first group of the existing connections divided up into a plurality of classes using a first allocation scheme with a first priority applied between the plurality of classes, wherein each connection has a committed rate; and

scheduling bandwidth for a second group of the existing connections, comprising one or more of the connections in the first group, in excess of the committed rate for each connection that are within peak allowed rates using a second allocation scheme, wherein the plurality of classes have equal priority.

19. The method of claim 18 wherein scheduling bandwidth comprises applying deficit round robin.

20. The method of claim 18 wherein scheduling bandwidth comprises applying weighted round robin.

21. The method of claim 18 wherein scheduling bandwidth comprises applying strict priority.

22. The method of claim 18 wherein scheduling bandwidth comprises applying modified strict priority.

23. A system for allocating communication bandwidth in a frame each connection being associated with a class of service and a committed rate, each class of service having a different first priority than another class of service for committed rates, and each class of service having a different second priority than another class of service above the committed rates, the system comprising:

connection data transmitted by the connections which exceeds the communication bandwidth in the frame; and

a receiving node configured to utilize a plurality of allocation schemes to order the connection data for each class of service, wherein the connection data from each connection that is associated with the same class of service is scheduled using the first priority for connection data up to committed rates, and wherein the connection data from each connection that is associated with the same class of service is scheduled using the second priority for connection data above the committed rates.

24. The system of claim 23 wherein the plurality of allocation schemes comprises weighted round robin.

25. The system of claim 23 wherein the plurality of allocation schemes comprises hierarchical round robin.

26. A system for scheduling connections using hierarchical round-robin scheduling, the system comprising:

a first node configured to receive transmission data from a plurality of connections and allocate portions of a first transmission frame to the transmission data, the plurality of connections being assigned to a plurality of classes of service, committed rates of the plurality of connections are scheduled using deficit round robin with strict priority between the plurality of classes of service, and transmission data in excess of the committed rates, yet within peak allowed rates is scheduled using deficit round robin with all of the plurality of classes of service having equal priority; and

a second node configured to receive the first transmission frame.

27. The system of claim 26, wherein the first node is further configured to allocate the portions from the transmission data wherein PCR (r_CBR,i) is allocated for each connection iε

S_CBR, r_rt-VBR,i is allocated for connection iε

S_rt-VBR, r_nrt-VBR,i=r_nrt-VBR,i^G+r_i^E is allocated for each connection iε

S_nrt-VBR, r_MGR,i=r_MGR,i+r_i^E is allocated for each connection iε

S_MGR, r_UBR,i=r_i^E is allocated for each connection iε

S_UBR, wherein R denotes a wireless link rate for the communication link between the CPE and base station, the connection data comprises constant bit rate connections (CBR), S_CBR denotes the set of CBR connections, N_CBR denotes the number connections in

28. The system of claim 27, wherein the bandwidth for each CPE is normalized from each CPEs current modulation to a common modulation.

29. The system of claim 27, wherein the bandwidth for each CPE is normalized from each CPEs current PHY mode to a PHY unit.

30. The system of claim 29, wherein the PHY unit is modulation symbols.

31. A method of scheduling data for uplink transmission by a CPE where the CPE transmits connection data that is associated with more than one class of service, the method comprising:

receiving connection data at a CPE;

storing the connection data in queues;

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;

if bandwidth is available in the frame after the first portion is allocated,

then selecting a second portion of the connection data that is associated with a second class of service using a second scheduling technique, allocating bandwidth within the first frame for transmitting the second portion;

if bandwidth is available in the frame after the second portion is allocated,

then grouping an excess portion of the connection data that is associated with the first class of service and the second class of service,

selecting a third portion of the excess portion using a first scheduling technique,

allocating bandwidth within the first frame for transmitting the third portion; and

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

32. The method of claim 31, wherein selecting the first, second, and third portions from the connection data is performed, wherein PCR (r_CBR,i) is allocated for each connection iε

S_CBR, r_rt-VBR,i is allocated for connection iε

S_rt-VBR, r_nrt-VBR,i=r_nrt-VBR,i^G+r_i^E is allocated for each connection iε

S_nrt-VBR, r_MGR,i=r_MGR,i^G+r_i^E is allocated for each connection iε

S_MGR, R_UBR,i=r_i^ε

is allocated for each connection iε

S_UBR, wherein R denotes a wireless link rate for the communication link between the CPE and base station, the connection data comprises constant bit rate connections (CBR), S_CBR denotes the set of CBR connections, N_CBR denotes the number connections in

33. The method of claim 32, wherein the bandwidth for each CPE is normalized from each CPEs current modulation to a common modulation.

34. The method of claim 32, wherein the bandwidth for each CPE is normalized from each CPEs current PHY mode to a PHY unit.

35. The method of claim 34, wherein the PHY unit is modulation symbols.

36. A system for scheduling connections between a base station and a customer premise equipment in a transmission frame, the system comprising:

a first node configured to receive transmission data from a plurality of connections and allocate portions of a first transmission frame to the transmission data, the plurality of connections being assigned to a plurality of classes of service, committed rates for a first portion of the plurality of connections is scheduled using weighted round robin, committed rates for a second portion of the plurality of connections is scheduled using deficit round robin, with strict priority between the first and the second portions, and transmission data from the first and the second portions that is in excess of the committed rates, yet within peak allowed rates is scheduled using deficit round robin with same priority between the first and the second portions; and

a second node configured to receive the first transmission frame.

37. The system of claim 36, wherein the first node is further configured to allocate the portions from the transmission data wherein PCR (r_CBR,i) is allocated for each connection iε

S_CBR, r_rt-VBR,i is allocated for connection iε

S_rt-VBR, r_nrt-VBR,i=r_nrt-VBR,i^G+r_i^E is allocated for each connection iε

S_nrt-VBR, r_MGR,i=r_MGR,i^G+r_i^E is allocated for each connection iε

S_MGR, r_UBR,i=r_i^E is allocated for each connection iε

S_UBR, wherein R denotes a wireless link rate for the communication link between the CPE and base station, the connection data comprises constant bit rate connections (CBR), S_CBR denotes the set of CBR connections, N_CBR denotes the number connections in S_CBR, r_CBR=

38. A method of scheduling data for uplink transmission by a CPE where the CPE transmits connection data that is associated with more than one class of service, the method comprising:

receiving connection data from a plurality of connections assigned to a plurality of classes of service;

storing the connection data in queues at the CPE;

grouping the connection data based on each connection data'"'"'s class of service;

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

assigning the selected connection data to a frame using a scheduling technique that prioritizes the connections within the first class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the buffer that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a second class of service that has a lower priority than the first class of service,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the connections within the second class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the buffer that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a third class of service that has a lower priority than the second class of service,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the connections within the third class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the buffer that is associated with the first class of service;

if the frame is not full,

then linking excess demand of the second and the third classes of service together,

selecting connection data that is associated with the linked excess demand,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the linked excess demand; and

transmitting the frame to the base station.

39. A method of scheduling data for downlink transmission by a base station where the base station transmits connection data that is associated with more than one class of service using a plurality of modulation techniques, the method comprising:

receiving connection data from a plurality of connections for transmission to a plurality of CPEs, the plurality of connections being assigned to a plurality of classes of service;

storing the connection data in queues at the base station;

grouping the connection data based on each connection data'"'"'s class of service;

normalizing the connection data to a common modulation;

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

assigning the selected connection data to a frame using a scheduling technique that prioritizes the connections within the first class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a second class of service that has a lower priority than the first class of service,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the connections within the second class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a third class of service that has a lower priority than the second class of service,

assigning the selected connection data to the frame-using a scheduling technique that prioritizes the connections within the third class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then linking excess demand of the second and the third classes of service together,

selecting connection data that is associated with the linked excess demand,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the linked excess demand; and

transmitting the frame to the plurality of CPEs using a plurality of modulation techniques.

40. A method for a base station to schedule data for uplink transmission by a CPE where the CPE transmits connection data that is associated with more than one class of service, the method comprising:

receiving connection data from a plurality of connections assigned to a plurality of classes of service;

storing the connection data in queues at the CPE;

transmitting a logical representation of the queues to the base station;

grouping the connection data based on each connection data'"'"'s class of service;

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

assigning the selected connection data to a frame using a scheduling technique that prioritizes the connections within the first class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a second class of service that has a lower priority than the first class of service,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the connections within the second class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then selecting connection data that is associated with a third class of service that has a lower priority than the second class of service,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the connections within the third class of service;

if the frame is full,

then incrementing the frame count by one,

selecting additional connection data from the queue that is associated with the first class of service;

if the frame is not full,

then linking excess demand of the second and the third classes of service together,

selecting connection data that is associated with the linked excess demand,

assigning the selected connection data to the frame using a scheduling technique that prioritizes the linked excess demand; and

notifying the CPE of the assignments for the selected connection data; and

transmitting the frame to the base station.