# US 2003/0223428 A1 · Method and apparatus for scheduling aggregated resources

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

- Number: US 2003/0223428 A1
- Document ID: US20030223428A1
- Status: Published application
- Kind: A1
- Application number: 10/157,763
- Filed: 2002-05-28
- Published: 2003-12-04
- Earliest claimed: 2002-05-28
- Inventors: Jose Maria Blanquer Gonzalez; Banu Ozden
- Web page: https://patentgrep.com/patent/US20030223428A1

## CPC

- H04L 47/623: {Weighted service order}
- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 47/50: Queue scheduling
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system and apparatus are disclosed for proportional sharing of multiple servers among competing flows. Single server weighted fair queuing (WFQ) principles are extended to a multi-server system consisting of N servers each operating at a rate of r, referred to as a multi-server fair queuing (MSFQ) system, to provide an output rate of Nr. An aggregated resource scheduling process proportionally shares the multiple servers among the competing flows. MSFQ does not share some of the properties of WFQ. The MSFO system of the present invention closely approximates a GPS system in terms of the delay a packet can experience and the cumulative service a flow receives. A disclosed MSF2Q algorithm extends the single server work of the WF2Q system to provide bounded fairness and generate “smooth” schedules. The MSF2Q system restricts the packets eligible for scheduling using a packet regulator at the exit of the flow queues which delays the eligibility of the packets to the WFQ scheduler.

## Claims

### Claim 1

A method for ensuring a desired level of service over a plurality of resources to a plurality of flows, comprising the steps of:
providing a buffer for storing said flows; and
providing information from said buffer to one or more idle ones of said plurality of resources, wherein said plurality of resources are proportionally shared among said plurality of flows.

### Claim 2 (depends on 1)

The method according to claim 1, wherein said resources are network connections.

### Claim 3 (depends on 1)

The method according to claim 1, wherein said resources are storage connections.

### Claim 4 (depends on 1)

The method according to claim 1, further comprising the step of selecting one or more of a plurality of idle resources.

### Claim 5 (depends on 1)

The method according to claim 1, further comprising the step of selecting one or more of said flows from said buffer based on an earliest GPS timestamp.

### Claim 6 (depends on 1)

The method according to claim 1, further comprising the step of providing an information regulator to ensure that:
at time t, the selected information satisfies the following constraint:
18 W ^ i ⁡ ( 0 , t ) < W i ⁡ ( 0 , t ) ⁢ ⁢ or ⁢ ⁢ ( W ^ i ⁡ ( 0 , t ) = W i ⁡ ( 0 , t ) ⁢ ⁢ and ⁢ ⁢ o ^ i < ⌈ r i ⁡ ( t ) r ⌉ ) ,
where W(0, t) and Ŵ(0,τ) denote the total number of bits serviced by gps and msfq, respectively, and ôi(t) denotes the number of outstanding flow i packets at an MSF2Q system at time t:

### Claim 7 (depends on 1)

The method according to claim 1, wherein said buffer has a size that exceeds a GPS equivalent buffer by up to (N−1)Lmax, where N is the number of said resources and Lmax denotes the maximum packet length.

### Claim 8 (depends on 1)

The method according to claim 1, wherein said method demonstrates a maximum delay for said information, p, as follows:
19 d _ p - d p ≤ ( N - 1 ) ⁢ L p Nr + L max r
where N is the number of resources, Lmax denotes the maximum information length, Lp denotes the length of a given information, p, {overscore (d)}p and dp denote the departure time of the information under MSFQ and GPS, respectively, and r is the rate of each of said resources.

### Claim 9 (depends on 1)

The method according to claim 1, wherein said method demonstrates a maximum amount by which the service received under GPS exceeds the service received under MSFQ, specified for any r as follows:
W(0,τ)−{overscore (W)}(0,τ)≦(N−1)Lmax
where N is the number of resources, Lmax denotes the maximum information length, W(0, τ) and {overscore (W)}(0,τ) denote the total number of bits serviced by GPS and MSFQ, respectively, by time τ.

### Claim 10 (depends on 1)

The method according to claim 1, wherein said method demonstrates a maximum amount by which the service a given flow receives under GPS exceeds the service the flow receives under MSFQ, specified for any τ, as follows:
W(0,τ)−{overscore (W)}i(0,τ)≦NLmax,
where W(0, t) and {overscore (W)}(0,τ) denote the total number of bits serviced by GPS and MSFQ, respectively, by time τ.

### Claim 11 (depends on 6)

The method according to claim 6, wherein said method demonstrates a maximum amount by which the service a given flow receives under GPS lags the service the flow receives under MSF2Q, specified for any τ, as follows:
Ŵi(0,τ)−Wi(0,τ)≦NLi,max
where W(0, t) and Ŵ(0,τ) denote the total number of bits serviced by GPS and MSF2Q, respectively, by time τ.

### Claim 12

A system for ensuring a desired level of service over a plurality of resources to a plurality of flows, comprising:
a buffer for storing said flows;
a memory that stores computer-readable code; and
a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to:
provide information from said buffer to an idle one or more of said plurality of resources, wherein said plurality of resources are proportionally shared among said plurality of flows.

### Claim 13 (depends on 12)

The system according to claim 12, wherein said resources are network connections.

### Claim 14 (depends on 12)

The system according to claim 12, wherein said resources are storage connections.

### Claim 15 (depends on 12)

The system according to claim 12, wherein said processor is further configured to select one of a plurality of idle resources.

### Claim 16 (depends on 12)

The system according to claim 12, wherein said processor is further configured to select one or more of said flows from said buffer based on an earliest GPS timestamp.

### Claim 17 (depends on 12)

The system according to claim 12, wherein said processor is further configured to provide an information regulator to ensure that:
at time t, the selected information satisfies the following constraint:
20 W ^ i ⁡ ( 0 , t ) < W i ⁡ ( 0 , t ) ⁢ ⁢ or ⁢ ⁢ ( W ^ i ⁡ ( 0 , t ) = W i ⁡ ( 0 , t ) ⁢ ⁢ and ⁢ ⁢ o ^ i < ⌈ r i ⁡ ( t ) r ⌉ ) ,
where W(0, t) and Ŵ(0,τ) denote the total number of bits serviced by GPS and MSFQ, respectively, and ôi(t) denotes the number of outstanding flow i packets at an MSF2Q system at time t.

### Claim 18 (depends on 12)

The system according to claim 12, wherein said buffer has a size that exceeds a GPS equivalent buffer by up to (N−1)Lmax, where N is the number of said resources and Lmax denotes the maximum packet length.

### Claim 19 (depends on 12)

The system according to claim 12, wherein said system demonstrates a maximum delay for said information, p, as follows:
21 d _ p - d p ≤ ( N - 1 ) ⁢ L p Nr + L max r
where N is the number of resources, Lmax denotes the maximum information length, Lp denotes the length of a given information, p, {overscore (d)}p and dp denote the departure time of the information under MSFQ and GPS, respectively, and r is the rate of each of said resources.

### Claim 20 (depends on 12)

The system according to claim 12, wherein said system demonstrates a maximum amount by which the service received under GPS exceeds the service received under MSFQ, specified for any τ as follows:
W(0,τ)−{overscore (W)}(0,τ)≦(N−1)Lmax
where N is the number of resources, Lmax denotes the maximum information length, W(0, t) and {overscore (W)}(0,τ) denote the total number of bits serviced by GPS and MSFQ, respectively, by time τ.

### Claim 21 (depends on 12)

The system according to claim 12, wherein said method demonstrates a maximum amount by which the service a given flow receives under GPS exceeds the service the flow receives under MSFQ, specified for any τ, as follows:
Wi(0,τ)−{overscore (W)}i(0,τ)≦NLmax,
where W(0, t) and {overscore (W)}(0,τ) denote the total number of bits serviced by GPS and MSFQ, respectively, by time τ.

### Claim 22 (depends on 17)

The system according to claim 17, wherein said method demonstrates a maximum amount by which the service a given flow receives under GPS lags the service the flow receives under MSF2Q, specified for any τ, as follows:
Ŵi(0,τ)−Wi(0,τ)≦NLi,max
where W(0, t) and Ŵ(0,τ) denote the total number of bits serviced by GPS and MSF2Q, respectively, by time τ.

### Claim 23

A system for ensuring a desired level of service over a plurality of resources to a plurality of flows, comprising the steps of:
a buffer for storing said flows; and
means for providing information from said buffer to an idle one or more of said plurality of resources, wherein said plurality of resources are proportionally shared among said plurality of flows.

### Claim 24 (depends on 23)

The system according to claim 23, wherein said resources are network connections.

### Claim 25 (depends on 23)

The system according to claim 23, wherein said resources are storage connections.

### Claim 26 (depends on 23)

The system according to claim 23, further comprising means for selecting one of a plurality of idle resources.
