# US 2003/0223365 A1 · Class of dynamic programming schedulers

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

- Number: US 2003/0223365 A1
- Document ID: US20030223365A1
- Status: Published application
- Kind: A1
- Application number: 10/291,018
- Filed: 2002-11-07
- Published: 2003-12-04
- Earliest claimed: 2002-06-04
- Assignees: Sharp Laboratories of America, Inc.
- Inventors: John M. Kowalski
- Web page: https://patentgrep.com/patent/US20030223365A1

## CPC

- H04L 67/62: Establishing a time schedule for servicing the requests
- H04L 67/61: taking into account QoS or priority requirements
- H04W 74/04: Scheduled access (hybrid access H04W74/02)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## 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, NL, 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, NL, to determine an optimal time to assign a transmit opportunity to a station.

## Claims

### Claim 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, NL, to determine an optimal time to assign a transmit opportunity to a station.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 3)

The scheduler of claim 3 where throughput is defined as:
4 P = ∑ j = 1 i + J ⁢ ⁢ ∑ f = 1 F ⁢ λ j f ⁢ ⁢ T
where λjfT represents the length of a packet from flow f at time j successfully transmitted, and j is the time index; and wherein queue minimization is represented by:
5 P ′ = ∑ j = 1 i + J ⁢ ⁢ ∑ f = 1 F ⁢ q j f ⁢
where i it the time in which the optimization is done and qjf is the length of the queue.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 5)

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

### Claim 7 (depends on 1)

The scheduler of claim 1 wherein said scheduling policy is defined by:
A=[f1, f2, . . . , fn, . . . fNS],
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.

### Claim 8 (depends on 1)

The scheduler of claim 1 which operates according to a protocol defined by:
4 At time k, with schedule at A*k−1, do: For i=0 to NL−1 % Loop on number of frames to look ahead For n=1 to NS %Loop on number of TxOPs For f=1 to F % Loop on flows Can (fn in Ak+1) be assigned to flow f? If (YES) then: Does that assignment determine future assignments of flows due to constraints? IF (YES) then: A)Make those provisional assignments to all future TxOPs; B) Compute revised queue lengths; C) Carry out all further computations for this assignment based on the number of transmit ops this assignment affects; D) Goto to next choice of f for the “starting” value of “n” and “i” prior to the first “YES” above; E) Store Candidate for next loop; END IF; ELSE; F) Store Candidate for next loop; Update queue length computations based on provisional transmission; Choose (from among the) provisional state assignment(s), based on the constraint set, one with the smallest remaining queue size.

### Claim 9 (depends on 1)

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.

### Claim 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, NL, to determine an optimal time to assign a transmit opportunity to a station.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 12)

The scheduler of claim 12 where throughput is defined as:
6 P = ∑ j = 1 i + J ⁢ ⁢ ∑ f = 1 F ⁢ λ j f ⁢ ⁢ T
where λjfT represents the length of a packet from flow f at time j successfully transmitted, and j is the time index; and wherein queue minimization is defined as:
7 P ′ = ∑ j = 1 i + J ⁢ ⁢ ∑ f = 1 F ⁢ q j f ⁢
where i it the time in which the optimization is done and qjf is the length of the queue, and wherein said optimizing includes either maximizing throughput or minimizing transmit queue size.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 10)

The scheduler of claim 10 wherein said looking ahead includes a scheduling policy wherein:
A=[f1, f2, . . . , fn, . . . fNS],
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.

### Claim 17 (depends on 10)

The method of claim 10 which operates according to a protocol defined by:
5 At time k, with schedule at A*k−1, do: For i=0 to NL−1 % Loop on number of frames to look ahead For n=1 to NS %Loop on number of TxOPs For f=1 to F % Loop on flows Can (fn in Ak+i) be assigned to flow f? If (YES) then: Does that assignment determine future assignments of flows due to constraints? IF (YES) then: A)Make those provisional assignments to all future TxOPs; B) Compute revised queue lengths; C) Carry out all further computations for this assignment based on the number of transmit ops this assignment affects; D) Goto to next choice of f for the “starting” value of “n” and “i” prior to the first “YES” above; E) Store Candidate for next loop; END IF; ELSE; F) Store Candidate for next loop; Update queue length computations based on provisional transmission; Choose (from among the) provisional state assignment(s), based on the constraint set, one with the smallest remaining queue size.

### Claim 18 (depends on 10)

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.
