# US 2004/0017825 A1 · Scheduling method and system for communication systems that offer multiple classes of service

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0017825 A1
- Document ID: US20040017825A1
- Status: Published application
- Kind: A1
- Application number: 10/207,648
- Filed: 2002-07-26
- Published: 2004-01-29
- Earliest claimed: 2002-07-26
- Inventors: Kenneth Stanwood; George Lin; Yair Bourlas
- Web page: https://patentgrep.com/patent/US20040017825A1

## CPC

- H04W 72/543: based on requested quality, e.g. QoS
- H04L 47/50: Queue scheduling
- H04W 72/52: based on load
- H04W 72/569: {of the traffic information}
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 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.

### Claim 5 (depends on 4)

The method of claim 4, wherein storing the data comprises assigning queues to each of the connections.

### Claim 6 (depends on 4)

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

### Claim 7 (depends on 4)

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

### Claim 8 (depends on 4)

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

### Claim 9 (depends on 4)

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

### Claim 10 (depends on 4)

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

### Claim 11 (depends on 4)

The method of claim 4, further comprising normalizing the data from each CPEs current modulation to a common modulation.

### Claim 12 (depends on 4)

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

### Claim 13 (depends on 12)

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

### Claim 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.

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 14)

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

### Claim 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.

### Claim 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.

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 18)

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

### Claim 21 (depends on 18)

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

### Claim 22 (depends on 18)

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

### Claim 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.

### Claim 24 (depends on 23)

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

### Claim 25 (depends on 23)

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

### Claim 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.

### Claim 27 (depends on 26)

The system of claim 26, wherein the first node is further configured to allocate the portions from the transmission data wherein PCR (rCBR,i) is allocated for each connection iεSCBR, rrt-VBR,i is allocated for connection iεSrt-VBR, rnrt-VBR,i=rnrt-VBR,iG+riE is allocated for each connection iεSnrt-VBR, rMGR,i=rMGR,i+riE is allocated for each connection iεSMGR, rUBR,i=riE is allocated for each connection iεSUBR, 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), SCBR denotes the set of CBR connections, NCBR denotes the number connections in
9 S CBR , r CBR = ∑ i = 1 N CBR ⁢ r CBR , i
denotes the total bandwidth allocated for SCBR, Srt-VBR denotes the set of rt-VBR connections, Nrt-VBR denotes the number connections in Srt-VBR, effective bandwidth (rrt-VBR,i) is calculated for each connection iεSrt-VBR,
10 r rt ⁢ - ⁢ VBR = ∑ i = 1 N rt ⁢ - ⁢ VBR ⁢ r rt ⁢ - ⁢ VBR , i
denotes the total bandwidth allocated for SCBR, Snrt-VBR denotes the set of nrt-VBR connections, Nnrt-VBR denotes the number connections in Snrt-VBR, rnrt-VBR,iG=SCRi is the guaranteed allocation, riE=(R−rCBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
11 r nrt - VBR G = ∑ i = 1 N nrt - VBR ⁢ ⁢ r nrt - VBR , i G
denotes the total guaranteed bandwidth allocated for Snrt-VBR, rnrt-VBRP=PCRi denotes the peak rate for iεSnrt-VBR, SMGR denotes the set of MGR connections, NMGR denotes the number connections in SMGR, rMGR,iG=MCRi is the guaranteed allocation, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
12 r MGR G = ∑ i = 1 N MGR ⁢ ⁢ r MGR , i G
denotes the total guaranteed bandwidth allocated for SMGR, rMGR,P=PCRi denotes the peak rate for iεSMGR, SUBR denotes the set of UBR connections, NUBR denotes the number connections in SUBR, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth; and
wi for a simple round robin case is
13 1 ( N nrt - VBR + N MGR + N UBR ) ,
for a weighted round robin case for nrt-VBR connections,
14 w i = r nrt - VBR i P - r nrt - VBR i G ∑ i = 1 N nrt - VBR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ ( r UBR i ) i = 1 N UBR ,
for a weighted round robin case for MGR connections,
15 w i = r MGR , i P - r nrt - VBR i G ∑ i = 1 N nrt - VBR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ ( r UBR i ) i = 1 N UBR ,
and for a weighted round robin case for UBR connections,
16 w i = r UBR i ∑ i = 1 N nrt - VBR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ ( r UBR i ) i = 1 N UBR .

### Claim 28 (depends on 27)

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

### Claim 29 (depends on 27)

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

### Claim 30 (depends on 29)

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

### Claim 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.

### Claim 32 (depends on 31)

The method of claim 31, wherein selecting the first, second, and third portions from the connection data is performed, wherein PCR (rCBR,i) is allocated for each connection iεSCBR, rrt-VBR,i is allocated for connection iεSrt-VBR, rnrt-VBR,i=rnrt-VBR,iG+riE is allocated for each connection iεSnrt-VBR, rMGR,i=rMGR,iG+riE is allocated for each connection iεSMGR, RUBR,i=riε is allocated for each connection iεSUBR, 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), SCBR denotes the set of CBR connections, NCBR denotes the number connections in
17 S CBR , r CBR = ∑ i = 1 N CBR ⁢ ⁢ r CBR , i
denotes the total bandwidth allocated for SCBR, Srt-VBR denotes the set of rt-VBR connections, Nrt-VBR denotes the number connections in Srt-VBR effective bandwidth (rrt-VBR,i) is calculated for each connection iεSrt-VBR,
18 r rt - VBR = ∑ i = 1 N rt - VBR ⁢ ⁢ r rt - VBR , i
denotes the total bandwidth allocated for SCBR, Srt-VBR denotes the set of nrt-VBR connections, Nnrt-VBR denotes the number connections in Snrt-VBR, rnrt-VBR,iG=SCRi is the guaranteed allocation, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
19 r nrt - VBR G = ∑ i = 1 N nrt - VBR ⁢ ⁢ r nrt - VBR , i G
denotes the total guaranteed bandwidth allocated for Snrt-VBR, rnrt-VBRP=PCRi denotes the peak rate for iεSnrt-VBR, SMGR denotes the set of MGR connections, NMGR denotes the number connections in SMGR, rMGR,iG=MCRi is the guaranteed allocation, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
20 r MGR G = ∑ i = 1 N MGR ⁢ ⁢ r MGR , i G
denotes the total guaranteed bandwidth allocated for SMGR, rMGR,P=PCRi denotes the peak rate for iεSMGR, SUBR denotes the set of UBR connections, NUBR denotes the number connections in SUBR, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth; and in accordance with the following equations, wi for a simple round robin case is
21 1 / ( N nrt - VBR + N MGR + N UBR ) ,
for a weighted round robin case for nrt-VBR connections,
22 w i = r nrt - VBR i P - r nrt - VBR i G ∑ i = 1 N nrt - VBR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) ,
for a weighted round robin case for MGR connections,
23 w i = r MGR i P - r MGR i G ∑ i = 1 N nrt - VBR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) ,
and for a weighted round robin case for UBR connections,
24 w i = r UBR i ∑ i = 1 N nrt - VBR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) .

### Claim 33 (depends on 32)

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

### Claim 34 (depends on 32)

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

### Claim 35 (depends on 34)

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

### Claim 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.

### Claim 37 (depends on 36)

The system of claim 36, wherein the first node is further configured to allocate the portions from the transmission data wherein PCR (rCBR,i) is allocated for each connection iεSCBR, rrt-VBR,i is allocated for connection iεSrt-VBR, rnrt-VBR,i=rnrt-VBR,iG+riE is allocated for each connection iεSnrt-VBR, rMGR,i=rMGR,iG+riE is allocated for each connection iεSMGR, rUBR,i=riE is allocated for each connection iεSUBR, 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), SCBR denotes the set of CBR connections, NCBR denotes the number connections in SCBR, rCBR=
25 ⁢ r CBR = ∑ i = 1 N CBR ⁢ r CBR , i
denotes the total bandwidth allocated for SCBR, Srt-VBR denotes the set of rt-VBR connections, Nrt-VBR denotes the number connections in Srt-VBR, effective bandwidth (rrt-VBR,i) is calculated for each connection iεSrt-VBR,
26 r rt - VBR = ∑ i = 1 N rt - VBR ⁢ r rt - VBR , i
denotes the total bandwidth allocated for SCBR, Snrt-VBR denotes the set of nrt-VBR connections, Nrt-VBR denotes the number connections in Snrt-VBR, rnrt-VBR,iG=SCRi is the guaranteed allocation, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
27 r nrt - VBR G = ∑ i = 1 N nrt - VBR ⁢ ⁢ r nrt - VBR , i G
denotes the total guaranteed bandwidth allocated for Snrt-VBR, rnrt-VBR,P=PCRi denotes the peak rate for iεSnrt-VBR, SMGR denotes the set of MGR connections, NMGR denotes the number connections in SMGR, rMGR,i=MCRi is the guaranteed allocation, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth,
28 r MGR G = ∑ i = 1 N MGR ⁢ r MGR , i G
denotes the total guaranteed bandwidth allocated for SMGR, rMGR,P=PCRi denotes the peak rate for iεSMGR, SUBR denotes the set of UBR connections, NUBR denotes the number connections in SUBR, riE=(R−rCBR−rrt-VBR−rnrt-VBRG−rMGRG)·wi is the fair portion of the excess bandwidth; and
wi for a simple round robin case is
29 1 / ( N nrt - VBR + N MGR + N UBR )
for a weighted round robin case for nrt-VBR connections,
30 w i = r nrt - VBR i P - r nrt - VBR i G ∑ i = 1 N nrt - VBR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) ,
for a weighted round robin case for MGR connections,
31 w i = r MGR , i P - r MGR , i G ∑ i = 1 N nrt - VBR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) ,
and for a weighted round robin case for UBR connections,
32 w i = r UBR i ∑ i = 1 N nrt - VBR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N MGR ⁢ ⁢ ( r nrt - VBR i P - r nrt - VBR i G ) + ∑ i = 1 N UBR ⁢ ( r UBR i ) .

### Claim 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.

### Claim 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.

### Claim 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.
