# US 2005/0030896 A1 · Adaptively changing weights for fair scheduling in broadcast environments

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

- Number: US 2005/0030896 A1
- Document ID: US20050030896A1
- Status: Published application
- Kind: A1
- Application number: 10/940,333
- Filed: 2004-09-14
- Published: 2005-02-10
- Earliest claimed: 1999-10-08
- Assignees: Microsoft Corporation
- Inventors: Paramvir Bahl; Nitin Vaidva
- Web page: https://patentgrep.com/patent/US20050030896A1

## CPC

- H04L 47/621: {Individual queue per connection or flow, e.g. per VC}
- H04L 47/50: Queue scheduling
- H04L 47/522: {Dynamic queue service slot or variable bandwidth allocation}
- H04L 47/6255: {queue load conditions, e.g. longest queue first}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Adaptively changing weights for fair scheduling in broadcast environments is disclosed. In one embodiment, a computer-implemented method for allocating bandwidth among a plurality of flows, such as nodes, sharing an output link, such as a network, is disclosed. The method includes adaptively determining a weight for each flow, based on a predetermined criteria, and allocating a portion of bandwidth to each flow proportionally to the weight for the flow. In one embodiment, the predetermined criteria takes into account an input rate of data packets for each flow, while in another embodiment, the predetermined criteria takes into account an queue size for each flow.

## Claims

### Claim 1

A computer-implemented method for allocating bandwidth in a broadcast environment comprising a plurality of end nodes among a plurality of flows associated with respective end nodes and sharing an output link comprising:
adaptively determining at each end node a weight for each flow associated with that end node based on a predetermined criteria; and
allocating at each end node a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.

### Claim 2 (depends on 1)

The method of claim 1, wherein the predetermined criteria comprises an input rate for each flow.

### Claim 3 (depends on 2)

The method of claim 2, wherein adaptively determining a weight for each flow comprises:
determining the input rate for the flow; and
adaptively determining the weight for the flow as the input rate multiplied by a normalizing constant.

### Claim 4

(Cancelled)

### Claim 5

(Cancelled)

### Claim 6 (depends on 1)

The method of claim 1, wherein the predetermined criteria comprises the queue size for each flow.

### Claim 7 (depends on 6)

The method of claim 6, wherein adaptively determining a weight for each flow comprises:
determining a number of packets in the flow at a given time;
adapatively determining the weight for the flow as the number of packets in the flow divided by a maximum number of packets allowed in the flow.

### Claim 8

A computer-implemented method for allocating bandwidth among a plurality of flows sharing an output link comprising:
adaptively determining a weight for each flow based on a predetermined criterion as
w
⁡
(
τ
)
=
Avg
⁢
⁢
queue
⁢
⁢
size
⁡
(
τ
)
Max
⁢
⁢
allowed
⁢
⁢
queue
⁢
⁢
size
,
where Avg queue size(τ) is the queue size at time τ, and Max allowed queue size specifies a maximum allowed size of a queue; and
allocating a portion of bandwidth to each flow at an end node associated with that flow based on the weight for the flow.

### Claim 9 (depends on 1)

The method of claim 1, wherein each flow corresponds to a queue over at least one node.

### Claim 10 (depends on 1)

The method of claim 1, wherein the output link comprises a local-area network (LAN).

### Claim 11 (depends on 1)

The method of claim 1, wherein the output link comprises a wireless network.

### Claim 12

A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for allocating bandwidth in a broadcast environment comprising a plurality of end nodes among a plurality of flows associated with respective end nodes and sharing an output link comprising:
adaptively determining at each end node a weight for each flow associated with that end node based on an input rate for each flow; and
allocating at each end node a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.

### Claim 13 (depends on 12)

The medium of claim 12, wherein adaptively determining a weight for each flow comprises:
determining the input rate for the flow; and
adaptively determining the weight for the flow as the input rate multiplied by a normalizingconstant.

### Claim 14

(Cancelled)

### Claim 15

(Cancelled)

### Claim 16

A machine-readable medium having instructions stored thereon for execution by a processor of a particular one of a plurality of end nodes of a broadcast environment to perform a method for allocating bandwidth in the broadcast environment among a plurality of flows sharing an output link comprising:
adaptively determining a weight at the particular end node for each flow associated with that end node based on the queue size for each flow; and
allocating a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.

### Claim 17 (depends on 16)

The medium of claim 16, wherein adaptively determining a weight for each flow comprises:
estimating a number of packets in the flow at a given time;
adaptively determining the weight for the flow as the number of packets in the flow divided by a maximum number of packets allowed in the flow.

### Claim 18

A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for allocating bandwidth among a plurality of flows sharing an output link comprising:
adaptively determining a weight for each flow based on the queue size for each flow, wherein adaptively determining a weight for each flow comprises determining the weight as
w
⁡
(
τ
)
=
Avg
⁢
⁢
queue
⁢
⁢
size
⁡
(
τ
)
Max
⁢
⁢
allowed
⁢
⁢
queue
⁢
⁢
size
,
where Avg queue size(τ) is the queue size at time τ, and Max allowed queue size specifies a maximum allowed size of a queue; and
allocating a portion of bandwidth to each flow based on the weight for the flow.

### Claim 19

A computerized system comprising:
a broadcast environment output link having a bandwidth, the broadcast environmentcomprising a plurality of end nodes; and
a plurality of flows, each flow being associated with one end node, each flow sharing the bandwidth of the output link proportional in a proportion based on a corresponding adaptive weight based on a predetermined criteria applied at the end node associated with the flow.

### Claim 20 (depends on 19)

The system of claim 19, wherein the predetermined criteria comprises an input rate for each flow.

### Claim 21 (depends on 19)

The system of claim 19, wherein the predetermined criteria comprises the queue size for each flow.

### Claim 22 (depends on 19)

The system of claim 19, wherein the output link comprises a wireless network (LAN) communicatively coupling the plurality of flows.

### Claim 23 (depends on 19)

The system of claim 19, wherein the output link comprises a wireless network communicatively coupling the plurality of flows.

### Claim 24 (depends on 19)

The system of claim 19, further comprising at least one node, such that at least one of the plurality of flows is located at each node.

### Claim 25 (depends on 8)

The method of claim 8 wherein the adaptively determining the weight for each flow based on the predetermined criterion comprises adaptively determining the weight for each flow based on the queue size and an input rate.

### Claim 26 (depends on 8)

The method of claim 8 wherein the output link comprises a local area network.

### Claim 27 (depends on 8)

The method of claim 8 wherein the output link comprises a wireless network.

### Claim 28 (depends on 18)

The medium of claim 18 wherein the adaptively determining the weight for each flow based on the predetermined criterion comprises adaptively determining the weight for each flow based on the queue size and an input rate.

### Claim 29 (depends on 18)

The medium of claim 18 wherein the output link comprises a local area network.

### Claim 30 (depends on 18)

The medium of claim 18 wherein the output link comprises a wireless network.
