Scheduling Method and System for Communication Systems That Offer Multiple Classes of Service

• US 20070153690A1
• Filed: 02/05/2007
• Published: 07/05/2007
• 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,609,631 B2
• Time in Patent Office: Days
• 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-40. -40. (canceled)

41. An apparatus comprising:

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

means for selecting a first data group associated with a first class of service;

means for 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;

means for allocating bandwidth within the first frame for a second data group associated with a second class of service, 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;

means for 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

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

42. The apparatus of claim 41, and further comprising means for 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.

43. The apparatus of claim 41, and further comprising:

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

means for 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.

44. 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 for determining a first uplink schedule at the base station for a first group of the connections up to committed rates associated with said connections using a first allocation scheme with a first priority applied between at least two of the plurality of classes of service;

means for determining a second uplink schedule at the base station for a second group of the connections, said second group of connections comprising one or more connections of said first group and requesting additional allocation in excess of associated ones of said committed rates that are within peak allowed rates 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 said one or more CPE stations to a common modulation.

45. The apparatus of claim 44, and further comprising means for associating at least one queue with one or more of said connections.

46. The apparatus of claim 44, wherein the first priority comprises a strict priority between at least two of the plurality of classes of service.

47. The apparatus of claim 44, wherein the first priority comprises a modified strict priority between at least two of the plurality of classes of service.

48. The apparatus of claim 44, wherein the first allocation scheme comprises an allocation scheme selected from the group consisting essentially of round robin, weighted round robin, deficit round robin and weighted fair queuing.

49. The apparatus of claim 44, wherein the second allocation scheme comprises an allocation scheme selected from the group consisting essentially of round robin, weighted round robin, deficit round robin and weighted fair queuing.

50. An apparatus comprising:

means for receiving connection data at a base station;

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

means 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 said first class of service;

means for 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 for meeting 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;

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

means for 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 bandwidth for transmission of said second portion; and

means for transmitting the first, second, and third portions during the first frame to said CPE station.

51. 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 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; and

a communication hub connected to said base station by a back haul, said communication hub comprising a switch adapted to provide Internet access to one or more subscribers at said CPE stations.

52. The system of claim 51, wherein said communication hub is further adapted to provide a video delivery service to said one or more subscribers.

53. The system of claim 51, wherein said communication hub is further adapted to provide a telephony service to said one or more subscribers.

54. A system comprising:

a base station;

one or more customer premises equipment (CPE) stations adapted to receive connection data from said base station through a downlink portion of a wireless communication link; and

a communication hub connected to said base station by a back haul, said communication hub comprising a switch adapted to provide Internet access to one or more subscribers at said one or more CPE stations,

wherein said base station is further adapted to;

receive said connection data from said back haul;

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

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

select a second portion of said 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 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;

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

allocate 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 bandwidth for transmission of said second portion; and

transmit the first, second, and third portions during the first frame to the one or more CPEs.

55. The system of claim 54, wherein said communication hub is further adapted to provide a video delivery service to said one or more subscribers.

56. The system of claim 55, wherein said communication hub is further adapted to provide a telephony service to said one or more subscribers.

57. 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 computer adapted to;

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

allocate bandwidth within the first frame for transmitting a second portion of said connection data using a second scheduling technique, said second portion of said connection data being associated with a second class of service, 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; and

allocate 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 bandwidth for transmission of said second portion.

58. A CPE station comprising:

a plurality of queues for storing 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 said connections being associated with one of a plurality of classes of service; and

a computer 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 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.