Chromatic scheduler for network traffic with disparate service requirements

• US 8,285,298 B2
• Filed: 12/23/2009
• Issued: 10/09/2012
• Est. Priority Date: 12/23/2009
• Status: Expired due to Fees

• Current Assignee: AT&T Mobility II LLC (AT&T, Inc.)
• Original Assignee: AT&T Mobility II LLC (AT&T, Inc.)
• Inventors: Noriega, Dimas, Brisebois, Arthur, De Rosa, Giuseppe
• Primary Examiner(s): ZEWDU, MELESS NMN
• Application Number:
  US12/646,809
• Publication Number:
  US 20110149879A1
• Time in Patent Office: 1,021 Days
• Field of Search: 455/418, 455/420, 455423-425, 455/448, 455450-451, 4554521-4522, 455/453, 455/500, 455/509, 455512-513, 455/517, 455/522, 455/524, 455/550.1, 455/556.2, 455560-561, 370328-330, 370332-333, 370/338, 370/341, 370/343, 370/348
• US Class Current: 455/453
• 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 84/045 using private Base Stations, e.g. femto Base Stations, home Node B

Abstract

System(s) and method(s) are provided for managing network capacity in a wireless network that serves various traffic flows with disparate quality of service requirements. Management is based on multi-stage scheduling in frequency-time domain. A first scheduling stage generates an allocation of radio resources that minimizes inter-cell interference amongst a plurality of base stations. Based on the first-stage allocation of radio resources, a second scheduling stage computes flow capacity for a set of radio resources specific to a base station, and acquires guaranteed-bit-rate (GBR) and non-guaranteed GBR traffic flows. GBR traffic flows are matched to computed flow capacity to generate an allocation of frequency-time resources. In second scheduling stage, GBR traffic flows are scheduled based at least in part on allocated resources and priority queuing. Based on allocation(s) in first and second scheduling stages, a third scheduling stage schedules non-GBR traffic flows based at least in part on fair scheduling.

Claims

1. A method, comprising:

employing at least one processor to execute code instructions retained in a memory, the code instructions, in response to execution facilitated by the at least one processor, perform operations, comprising;

allocating a set of physical resource blocks for a set of base stations based at least in part on a load condition of at least one base station in the set of base stations;

scheduling a set of guaranteed-bit-rate data flows for the set of base stations based on the allocated set of physical resource blocks; and

scheduling a set of non-guaranteed-bit-rate data flows for the set of base stations based on an available radio resource subsequent to the scheduling of the set of guaranteed-bit-rate data flows.

2. The method of claim 1, wherein the allocating is reiterated with a first period, the scheduling of the set of guaranteed-bit-rate data flows is reiterated with a second period, and the scheduling of the set of non-guaranteed-bit-rate data flows is reiterated with a third period, the first period is longer than the second period, and the second period is longer than the third period.

3. The method of claim 1, wherein the allocating the set of physical resource blocks for the set of base stations based at least in part on the load condition of the at least one base station in the set of base stations includes:

exchanging the load condition with the set of base stations;

for a set of radio resources, analyzing an allocation of frequency and power for the set of base stations to achieve a defined capacity;

based on the analyzing, assigning the set of physical resource blocks to each base station in the set of base stations.

4. The method of claim 3, further comprising:

configuring a resource exclusion list that spans the set of physical resource blocks assigned to each base station in the set of base stations.

5. The method of claim 1, wherein the allocating the set of physical resource blocks for the set of base stations based at least in part on the load condition of the at least one base station in the set of base stations includes:

collecting the load condition from the set of base stations;

for a set of radio resources, analyzing at least one inter-base station allocation of frequency and power to achieve a defined capacity;

assigning the set of physical resource blocks to each base station in the set of base stations;

for the set of base stations, configuring a resource exclusion list that spans the set of physical resource blocks assigned to each base station of the set of base stations; and

delivering the configured resource exclusion list.

6. The method of claim 1, wherein the scheduling the set of guaranteed-bit-rate data flows based on the allocated set of physical resource blocks includes:

acquiring a channel quality indicator and associated modulation and coding scheme indicator for the set of physical resource blocks; and

computing flow capacity based at least in part on the acquired channel quality indicator and the associated modulation and coding scheme indicator, wherein the flow capacity is computed through a service function.

7. The method of claim 6, further comprising:

acquiring the set of guaranteed-bit-rate data flows;

generating a resource reservation list based on the computed flow capacity and bit requirements of the acquired set of guaranteed-bit-rate data flows; and

scheduling the acquired set of guaranteed-bit-rate data flows according to priority queuing and resources reserved through the resource reservation list.

8. The method of claim 7, further comprising:

producing a list of available physical resource blocks for the non-guaranteed-bit-rate data flows based at least in part on the generated resource reservation list.

9. The method of claim 1, wherein scheduling the set of non-guaranteed-bit-rate data flows based on the available radio resource(s) subsequent to the scheduling of the set of guaranteed-bit-rate data flows includes:

acquiring a channel quality indicator and an allowable modulation and coding scheme per physical resource block in the set of physical resource blocks allocated to the non-guaranteed-bit-rate data flows;

if a nearly-current load condition requests additional physical resource blocks for the non-guaranteed-bit-rate data flows;

unmasking a set of unused physical resource blocks reserved for the guaranteed-bit-rate data flows; and

allocating the unmasked physical resource blocks to the non-guaranteed-bit-rate data flows to augment the set of physical resource blocks allocated to the non-guaranteed-bit-rate data flows; and

based on the allocated physical resource blocks to the non-guaranteed-bit-rate data flows, scheduling the non-guaranteed-bit-rate data flows according to fair queuing.

10. The method of claim 9, further comprising:

if the nearly-current load condition does not require additional physical resource blocks for the non-guaranteed-bit-rate data flows, scheduling the non-guaranteed-bit-rate data flows according to the fair queuing based on the set of physical resource blocks allocated to the non-guaranteed-bit-rate data flows.

11. The method of claim 7, wherein the generating includes extracting a service curve that bounds an available guaranteed bit rate, the service curve is based in part on the computed flow capacity.

12. A non-transitory computer-readable medium with code instructions stored thereon that, in response to execution, cause a computing device to perform operations, comprising:

allocating a set of radio resources for a set of base stations based at least in part on a load condition of at least one base station in the set of base stations;

scheduling a set of guaranteed-bit-rate data flows for the set of base stations based on the allocated set of radio resources; and

scheduling a set of non-guaranteed-bit-rate data flows for the set of base stations based on available radio resources subsequent to the scheduling of the set of guaranteed-bit-rate data flows.

13. The non-transitory computer-readable medium of claim 12, wherein the allocating is reiterated with a first period, the scheduling the set of guaranteed-bit-rate data flows is reiterated with a second period, and the scheduling the set of non-guaranteed-bit-rate data flows is reiterated with a third period, the first period is longer than the second period, and the second period is longer than the third period.

14. A system, comprising:

a first component that periodically supplies an allocation of physical resource blocks for each base station in a set of base stations;

a second component that periodically schedules at least one guaranteed-bit-rate traffic flow for the set of base stations based on the allocation of the physical resource blocks; and

a third component that periodically schedules at least one non-guaranteed-bit-rate traffic flow for the set of base stations based on an available radio resource subsequent to the scheduling of the at least one guaranteed-bit-rate traffic flow.

15. The system of claim 14, a first period with which the first component supplies the allocation of the physical resource blocks is longer than a second period with which the second component schedules the at least one guaranteed-bit-rate traffic flow, and the second period is longer than a third period with which the third component schedules the at least one non-guaranteed-bit-rate traffic flow.

16. The system of claim 15, wherein, to supply the allocation, the first component analyzes allocations of frequency resources and power to achieve a defined capacity of the set of base stations.

17. The system of claim 14, wherein, to schedule the at least one guaranteed-bit-rate traffic flow based on the allocation of the physical resource blocks, the second component:

computes a flow capacity for the allocation of the physical resource blocks based on at least one service curve;

acquires the at least one guaranteed-bit-rate traffic flow and computes an arrival curve;

based on the arrival curve, matches a bit-rate requirement of the at least one acquired guaranteed-bit-rate traffic flow to the computed flow capacity for the allocation of the physical resource blocks;

generates a resource reservation list for the at least one guaranteed-bit-rate traffic flow; and

schedules the at least one guaranteed-bit-rate traffic flow in accordance with priority queuing and the generated resource reservation list.

18. The system of claim 14, wherein, to schedule the at least one non-guaranteed-bit-rate traffic flow based on the available radio resource subsequent to the scheduling of the at least one guaranteed-bit-rate data flow, the second component:

acquires channel quality indicators and modulation and coding scheme indicators for at least one frequency-time resource allocated to the at least one non-guaranteed-bit-rate traffic flow; and

in response to a load condition determined based at least in part on the channel quality indicators and modulation and coding scheme indicators requesting an additional frequency-time resource for the at least one non-guaranteed-bit-rate traffic flow, the second component;

augments the additional frequency-time resource allocated to the at least one non-guaranteed-bit-rate traffic flow with unused radio resources available to the set of guaranteed-bit-rate traffic flows; and

based on the augmented additional frequency-time resource, schedules at least one non-guaranteed-bit-rate traffic flow in accordance with fair scheduling.

19. The system of claim 14, wherein the first component receives the allocation of physical resource blocks for each base station in the set of base stations.

20. The system of claim 15, wherein the first period is two orders of magnitude longer than the second period, and the second period is one order of magnitude longer than the third period.