Class of dynamic programming schedulers

• US 20030223365A1
• Filed: 11/07/2002
• Published: 12/04/2003
• Est. Priority Date: 06/04/2002
• Status: Abandoned Application

• Current Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Kowalski, John M.
• Application Number:
  US10/291,018
• Publication Number:
  US 20030223365A1
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

A scheduler for use in an LAN for allocating transmission opportunities includes a scheduling policy mechanism for assigning flow-to-transmit opportunities to the stations based on network constraints; and an optimization mechanism for looking ahead a number of superframes, N_L, to determine an optimal time to assign a transmit opportunity to a station. A method of allocating transmission opportunities includes assigning flow-to-transmit opportunities to the stations based on network constraints; and looking ahead a number of superframes, N_L, to determine an optimal time to assign a transmit opportunity to a station.

Claims

1. In a local area network, having a plurality of stations, and wherein data flow moves over the network in superframes, a scheduler for allocating transmission opportunities, comprising:

a scheduling policy mechanism for assigning flow-to-transmit opportunities to the stations based on network constraints; and

an optimization mechanism for looking ahead a number of superframes, N_L, to determine an optimal time to assign a transmit opportunity to a station.

2. The scheduler of claim 1 wherein the network constraints include (1) the overall rate of the wireless channel is constrained to be less than C_MAX, (2) each flow can be transmitted over wireless channel at rate c_f, which is possibly different for each flow, and (3) the latency and jitter bounds.

3. The scheduler of claim 1 wherein said scheduling policy mechanism schedules transmit opportunities to minimize queue size and to maximize throughput on a channel.

4. The scheduler of claim 3 where throughput is defined as:

5. The scheduler of claim 4 wherein transmit opportunities are allocated to each flow such that P or P′

is optimized.

6. The scheduler of claim 5 wherein transmit opportunities are identified in groups of up to seven transmit opportunities in a superframe.

7. The scheduler of claim 1 wherein said scheduling policy is defined by:

A=[f₁, f₂, . . . , f_n, . . . f_NS],

where A is the tentative assignment of flows-to-transmit opportunities;

f is the flow arriving in the transmit queue at scheduling interval n and NS is the number of transmit opportunities in a superframe.

8. The scheduler of claim 1 which operates according to a protocol defined by:

9. The scheduler of claim 1 wherein the local area network is a network taken from the group of networks consisting of wireless local area networks, hard-wired local area networks and power-line local area networks.

10. In a local area network, having a plurality of stations, and wherein data flow moves over the network in superframes, a method of allocating transmission opportunities, comprising:

assigning flow-to-transmit opportunities to the stations based on network constraints; and

looking ahead a number of superframes, N_L, to determine an optimal time to assign a transmit opportunity to a station.

11. The method of claim 10 wherein the network constraints include (1) the overall rate of the wireless channel is constrained to be less than C_MAX, (2) each flow can be transmitted over wireless channel at rate c_f, which is possibly different for each flow, and (3) the latency and jitter bounds.

12. The method of claim 10 which includes optimizing the system, including maximizing throughput and minimizing pending transmit queue size, including a scheduling policy mechanism for scheduling transmit opportunities to minimize queue size and to maximize throughput on a channel.

13. The scheduler of claim 12 where throughput is defined as:

14. The scheduler of claim 13 wherein said optimizing includes allocating transmit opportunities to each flow such that P or P′

is optimized.

15. The scheduler of claim 14 wherein said optimizing includes identifying transmit opportunities in groups of up to seven transmit opportunities in a superframe.

16. The scheduler of claim 10 wherein said looking ahead includes a scheduling policy wherein:

A=[f₁, f₂, . . . , f_n, . . . f_NS],

where f is the flow arriving in the transmit queue at scheduling interval n and A is the tentative assignment of flows-to-transmit opportunities.

17. The method of claim 10 which operates according to a protocol defined by:

18. The method of claim 10 wherein the local area network is a network taken from the group of networks consisting of wireless local area networks, hard-wired local area networks and power-line local area networks.