A stabilizing AQM based on virtual queue dynamics in supporting TCP with arbitrary delays - Decision and Control, 2003. Proceedings. 42nd IEEE Conference on

Proceedings

of

the

42nd

IEEE

Conference

on

Decision

and

Control

Maui, Hawaii

USA,

December

2003

ThM03-2

A

Stabilizing

AQM

Based

on

Virtual

Queue

Dynamics

in

Supporting

TCP

with

Arbitrary

Delays

Ki

Baek

Kim,

Ao

Tang,

Steven

H.

Low

Departments

of

CS

and

EE

California Institute

of

Technology,

Pasadena,

CA

91

125

kkb

@

di.

ens

.fr,

aotang

@

caltech.edu,

slow

@

caltech.edu

Abstract-

This

paper

studies

how

to

design

a

stabilizing

AQM

in supporting TCP

(Transmission

Control Protocol) with

arbitrary delays.

For

the well-known

AlMD

(Additive Increase

Multiplicative Decrease) dynamic model

of

TCP,

our

study

shows

that

we

can

compensate

for

arbitrary delays

explicitly

by

applying

a modified virtual

queue

dynamics that makes

the

equilibrium

queuing

delay

zero.

This

study

also

verifies that

a simplified

AQM

AVQ

(Adaptive

Virtual

Queue)

is the state-

feedback control

for

the

AIMD

model based

on

the virtual

queue dynamics.

I.

INTRODUCTION

Since

TCP

Reno/AQM

Droptail has

been

proposed in

[l],

the current internet

is

still

using

Reno/Droptail

and

its

variants

as

a congestion control

strategy.

Droptail,

which

drops packets

when

the queue

is

full,

is

not

appropriate

as

a feedback control for high-speed networks

since links are likely to

have

large queues

in

high-speed

networks

and

this

may

increase

the

average delay

in

the

network. More importantly, Droptail can often cause the

global synchronization [2]

and

thus

have

low

throughput.

In

order to overcome these problems,

RED

(Random Early

Detection)

has been

suggested in [3] which randomly drops

packets proportionally to the

average

queue length. Since

then,

there

have been

a lot of

investigations about

how

to

tune

design parameters in RED

[4],

[5].

They

show

that

RED

is

not enough

to

stabilize TCP

and

thus

not

easy to fully

utilize the

given

network resources.

As

a result,

new AQM

algorithms

such

as

BLUE

[6J,

AVQ

(Adaptive

Virtual

Queue)

[7]

and

REM

(Random Exponential Marking)

[XI

have been

suggested.

However,

all these papers

did

not address appro-

priately

how

to tune gains

of

their

AQM

structures for closed-

loop stability since

they lack

of

a TCP dynamic model, in

spite that stabilizing the closed-loop system

is

necessary to

get the maximum utilization.

In

order

to

address this

problem,

paper

[9] has

developed

a dynamic

model

to

reflect AIMD

(Additive Increase Multi-

plicative Decrease)

mode

of

TCP

and

paper

[

101

has

applied

the

transfer function approach

to

the stabilizing RED design

problem based

on

the

AIMD

model. As

a sequence, papers

[ll].

[12]

have investigated

how

to

scale gains

of

PI-type

REM (Proportional-Integral)

in

terms of queue length

and

The

first

author

moves

to'INIUA-ENS,

ENS-DI

45

rue

d'Ulm

75005,

Paris

FRANCE.

P-type

AVQ

in

terms

of

aggregate, respectively,

for

closed-

loop stability.

The

papers

[13],

[14]

have

suggested PI-type

AQM

in terms of aggregate in

an

inner loop.

However,

all

these results based

on

the transfer function approach

do

not

consider

what

is

a natural

state-feedback

control

to

stabilize

the given

TCP

and queue dynamics.

In addition, they

did not

consider

how

to compensate for delays explicitly

even if

they

know

the previous dynamic information

and

delays, where

this kind

of

control strategy

is

called

delay-independent

(or

memoryless) control in the control literature.

It is well-known

that the delay-independent control

has

a limit

on

performance

in

the presence

of

a large delay

[15],

[16]

compared,with

the

delay-dependent

(or

memory)

control, i.e.,

we

cannot

fully

utilize

the

given

network

resources.

Recently,

the papers

[17J,

[IQ, 

[I91

formulate a simplified

version

of

the

AQM

design

problem

for the

well-known

AZMD

dynamic model

in

[9]

as state-space models.

Thereby,

they

showed that PD-type

(Proportional-Derivative)

AQM

is

a natural state-feedback

control

structure

to

stabilize

TCP

Reno

for

the

first

time in the networking literature

to our

knowledge, where RED can

be

classified

as

P-type

AQM

in

terms

of

queue length. They also

proposed

delay-dependent

AQMs

to compensate

for

delays

in

congestion measure

ex-

plicitly and discussed the impact

of

different

AQM

structures

on performance.

However, they assume that

the forward

delay between source and link

is zero

when

they

compensate

for

delays explicitly. Through

ns

simulations,

they

show that

this

assumption cannot

be

ignored

in

the

presence

of

large

delays.

Thus,

it is

necessary to

investigate

how

to design a

stabilizing

AQM

without

any assumption

about

delay.

This paper attempts

to

address this issue

by

applying a

modified

virtual queue dynamics.

For

simplicity

of

designing

a stabilizing

AQM

as

in

[lo],

[ll],

[13], [14],

we

assume

single

link

and

homogeneous sources

with

the same

window,

and

no short

flows,

where

the real network

is asymmetric

as

shown

in

[20].

We

also

do

not

consider inpuvstate constraints

and

uncertainty

which

are intrinsically

included

in

real net-

works and

ns

simulator, although our

work

can

be extended

to

more realistic problems

using

modem

control

theories

and

technologies.

Then,

our

study shows

that

we

can

compensate

for

ar-

bitrary delays explicitly

by

employing

a modified

virtual

queue dynamics

that

makes the equilibrium queuing delay

zero. As a subsidiary result

of

this

study,

we

verify that a

0-7803-7924-1/03/$17.00

02003

IEEE

3665

simplified

AVQ,

which

is

P-type delay-independent

AQM

in

terms

of

aggregate,

is

a state-feedback control for the

AIMD model based

on

the virtual queue dynamics. Finally,

we

illustrate the proposed results via the non-deterministic

nonlinear

ns

simulator. The simulation results should

be

considered as backing

up

the proposed theoretical results

qualitatively rather than as their direct illustration.

11.

AQM

DESIGN COMPENSATING

ARBITRARY

DELAYS

Consider

N

homogeneous TCP Reno sources with the

same

window

size modeled

by

[9]

sharing a single link

of

capacity

c

with

the

queue

dynamics

modeled

by

where

wS(t)

is

TCP

window

size in packets

of

source

s

at time

t,

T,f(t)

is the

forward delay from

source

to link,

T,b(t)

is

the

backward delay

from

link

to

source,

7,(t)

is

the round trip time

(T,(t)

=

T,f(t)

+

T,b(t>),

p(t)

is

the loss

probability at time

t

that

is

implemented at

links,

b(t)

is

the real queue length,

y(t)

is aggregate rate,

and

c

is the link

capacity

in

packets/sec.

We

define the source rate

by

z,(t)

=

w,(t)/(d,

+

b(t)/c),

where

d,

is the round trip propagation

delay

of

source

s.

As

in

[lo],

we

assume sources

are

identical

d,

=

d

and

all

have

the common

window

ws(t)

w(t);

we

assume delays take their equilibrium values and

are

constant,

so

that

7,

=

7.

In

the

above

model, the

first and

second parts

of

the

first

equation represent

AI

and

MD

behaviors at sources,

respectively, where

the

second equation represents the real

queue dynamics

at

link. For

this

AIMD 

model,

our

papers

[17],

[18],

[19]

propose what

is

a natural feedback control

structure for stabilizing the

given

TCP, 

how

to compensate for

delays

explicitly, and

a unified

AQM

framework based which

interprets a simplified RED

131

and

REWI

(Proportional-

Integral)

[8], 

[

111

as different approximations.

However, they

assume

that

the forward delay

.r,f(t)

is zero since the nonzero

T,f(t)

produces a state-delay for the linearized system

of

the

AIMD

model

(1) that makes

it

impossible

to

compensate

for delays

in

a

closed-form.

Through

ns

simulations,

they

show

that this assumption cannot be ignored in

the

presence

of

large delays.

This

problem naturally leads to

the

present

work.

The

key

idea to overcome

this

problem

is-to 

add

the

following

niodijed

virtual

queue

dynantics

(k(t))

at the

router’ to

the

AIMD model

(1):

=

71

I-YzC

+

Y(t)I,

where

&(t)

is

the

virtual

queue length, and

yl(>

0)

and

yz

are free design parameters.

In

this paper,

we

assume that

o<y2

<

1.

Let

(w*,

b*,p*)

be

the

equilibrium point.

If

0

<

yz

<

1,

the equilibrium

point

of

y(.)

is

y*

=

yzc

due

to

the

virtual

queue dynamics. Hence,

we

have

b*

=

0,

T*

=

7f

+T~

=

d,

Since

the

virtual queue

dynamxs

is

dominant near the

equilibrium point,

we

approximate that

the

real queue

b(-)

is

zero near

the

operating point from

now

on

in

this

paper.

Then, system (1)

based

on

the above virtual

queue

dynam-

ics is converted to the equivalent form

w*

=

d

2-

2NZ

Nyzcy

and

p*

=

-

2N2+{dyZc)Z’

-

r”(t

-

4

+

71724

-

&(t)

+

YlYZC)

b(t)

=

f(i(t),

i(t

-

d),p(t

-

d)).

In

general,

it is

difficult

to systematically

find

a nonlinear

function

p(t)

which guarantees the global asymptotic stability

for

nonlinear dynamical systems

with

delays. As a starting

point

to

address these problems

and

as

a method

to

avoid

the

nonnegative constraint, the present paper considers an equi-

librium point with

positive

values and studies

$e

linearized

version

of

the

derived dynamical system

(2)

on

i(t),

i(t

-

d)

and

p(t

-

d)

near the equilibrium point.

From

(2),

we can get the following model

of

the linearized

TCP

and

virtual queue dynamics:

&t)

=

Az&(t)

+

BIGp(t

-

d),

(3)

where

ii(t)

=

$t), &(t)

=

$t),

@(t)

=

p(t)

-

p*,

&(O) 

and

{6p(u),

0

E

[-d,

01)

are

given,

A2

=

-2NZ:y;cZdZ

B1

=

-

y1(2Nz~$czdz).

Refer to Section VI in Appendix

for

derivation

of

(3).

Note that the above

model

does

not

include

any

time

delay

in

the

state variable

6&(t)

and

only

includes

tlie time

delay

in

the

control

6p(t

-

d).

This interesting and non-intuitive

feature allows

us

to

employ the explicit compensation method

used

in

our

companion papers

[17],

[18], [I91

as

shown in

the following subsection.

2

2cN

and

‘If

y1

=

72

=

1,

the

virtual

queue dynamics

is

equal

to

the

real

queue

dynamics,

and

the

AVQ

in

[

121

assumes

y1

<

0

while

we

assumes

yi

>

0

in

this

paper.

3666

From

the

above

model,

we

can

naturally get a P-type state-

feedback

AQM

in

terms

of

aggregate:

bp(t)

=

Hp&(t)

(4)

if

we

ignore the time delay

d

(i.e.,

d

=

0)

in

the control

bp(t).

How

to

compensate for the delay explicitly

and

how

to obtain a stabilizing gain

Hp

is discussed later in

this

paper.

The

derived

P-type

AQM

structure,. which

we

also

did

not expect,

is

interesting

again

as follows:

If

we

linearize

the

AVQ

p(t)

=

p(i(t))

in

[7],

[12],

we

also

have

a P-

type

control structure

bp(t)

=

Hg

&t),

i.e., our study

supports their argument

that

the

AVQ

is

an

appropriate

control structure to stabilize TCP Reno based

on

the virtual

queue dynamics in the absence

of

delays

As

shown in [SI,

[Ill,

[13],

[17],

[lS],

[19],

we

can make

the

steady-state tracking error approach zero faster

by

adding

integral control action [21]

to

the original system

as

follows:

i(t)

=

Az(t)

+

Bb$(t

-

d),

(5)

where

-.

-

z(0)

and

{b$(a),a

E

[-d,O]}

are

given,

~(t)

=

1

i;?;

1,

A

=

01

a,],

B

=

[:]I. 

Refer to Section

VI

i'n

Apiendix

for

derivation of

(5).

For

the.

above

minimal

representation

with

state variables

(66(t),

Sb(t)),

we

can

get

a PI-type state-feedback

AQM

@(t)

=

H

~(t)

=

HrGi(t)

+

Npb&(t)

(6)

if we

ignore

the

time delay

d

(i.e.,

d

=

0)

in the control

Note

that

the proposed PI-type

AQM

does

not

require the

equilibrium

point

p*

but requires the initial

loss

probability

p(to),.while

the proposed

P-type

AQM

needs

p*.

Now,

we

are

ready

to

show how

to compensate the delays

and

how

to

get

a stabilizing gain. Although the following

results

can

easily be obtained from

[17],

[18], [19],

we

introduce

them

in order for this paper to be self-contained.

In

the

we

consider only the PI-type

AQM

structure

(6)

since

we

can handle P-type

AQM

(4)

as

a special case

of

the

PI-type

AQM.

bP(t).

111.

EXPLICIT

DELAY

COMPENSATION AND

A

STABILIZING

GAIN

The

delayed

system

(5)

can be converted to the equivalent

nominal

system

S,(t)

=

As,(t)

+

Bb$(t),

(7)

where

seit)

=

[s~(t),

sz(t)lT,

B

=

[0,

&IT,

I%

=

B

A?e-A2

(;-e--A2d

1'

A2e-A2d

(biqt)

+

iL&) 

+

f5&) 

+

iLZd(t)

(1

-

e-A2d)

Sl(t)

=

Refer

to

Section VII in Appendix

for

derivation of

(7).

It

is

easy to see that the closed-loop system

of

(7)

is

asymptotically stable

if and

only

if the original system

(5)

is

asymptotically stable.

From the above state-space

model,

we

can naturally get

PI-type delay-dependent (or memory)

AQM

b$(t)

=

HI"

S](t)

+

H$

sz(t).

(8)

Now,

we

get a stabilizing optimal gain

of

the proposed

control structures.

For

this purpose,

we

consider the follow-

ing performance index:

min

l+m

(Qls:(a)

+

Q&(a)

+

@'(a))

da,

'

(9)

6P(.) 

where

Q1

>

0

and

Q2

2

0.

Proposition

I:

The stabilizing optimal

gain

of

the

pro-'

posed

PD-type

AQM

(8),

which minimizes

the transient cost

(9),

is

given

by

Az

+

/A;

+

B:Qz

+

2dz

H,d

=

a,

Proof:

The

optimal control that minimizes

(9)

is

given

by

Hg

=

-

B1

6@*(t)

=

-BTKese(t).

cl

Proposition

1

implies that the solution

of

the problem

(9)

is

a

stabilizing

AQM

algorithm, specified

by

(H;,

H;).

Conversely, given

any

AQM

of

this structure,

it solves (9)

with

appropriate weights

Qi,

as

the next

result says. It

can

be easily

proved

from Proposition 1.

Proposition

2:

Given

a stabilizing

AQM

ao(t)

=

[HI,

H2]~e(t)

that satisfies

&HI

<

0

and

Az+B1H2

<

0,

it solves problem (9)

with weights:

U

Proposition

3:

Given

the

eigenvalues

and

A2

of the

closed-1oop.system (7),

where real

parts

of

A1

and

XZ

are

negative,

it solves

the

problem

(9)

with

weights:

In

order

for

an

AQM

@(t)

=

[HI

Hzfse(t)

to

be

a

stabilizing optimal control

when

the system

is

controllable

and

observable for system

(5),

it should satisfy

H1

>

0.

The

implication

of

HI

=

0

is that at least one

of

the eigenvalues

Xi

is zero, implying

that

the convergence

rate is

very

slow

and

the original nonlinear system could

be

unstable according

to

the center manifold theorem

[22].

As

shown

in Proposition

2,

if

HZ

=

0,

then

we

have

XI

+

A2

=

A2

+

B1

HZ

I

AZ-where

the last inequality follows from the fact that

A2

<

0,

B1

<

0

3667

and

Hz

2

0.

Since

all

eigenvalues should

have

negative

real parts

for

the closed-loop

stability,

the

above

inequality

means that

the sum

of

the

real

parts

of

the

eigenvalues

is less

negative

when

H2

=

0

than when

H2

>

0.

This suggests

that

we

need

to

add

P-type

control

in

order

to

make

the dynamics

move

faster.

Iv.

ns

SIMULATIONS

In

this section,

we

illustrate

performance

of

the derived

structures

via

two simulation examples. Note

that

the pro-

posed

AQMs,

which

are designed for

the

linearized system

(3),

are

implemented

in

ns

simulator which

has

stochastic

and

nonlinear

dynamics.

Thus,

the simulation

results

should

be

considered

as

backing up

our

study

qualitatively

rather

than

its

direct illustration.

For

ease

of

selection

of

stabilizing

optimal

gains, we

set

two eigenvalues

of

the closed-loop system

to

be

equal

(i.e..

X

=

XI

=

XZ).

Then,

we have

only

to

design

X

<

0

in

order

to

get

the

stabilizing

optimal

gains.

The

dynamic behavior

of

the

closed-loop system depends on

how

to

design

A.

A

larger

1x1

makes

the system

move

faster, i.e.,

makes

the

system

go

to

the equilibrium

faster.

However,

if

the

value

of

1x1

is

too

high, the

closed-loop system can also easily deviate from

the

equilibrium point due

to

nonlinearity and randomness

of

ns

simulator.

Since

the

stabilizing

gains

in

this

paper are derived

from

the deterministic linearized model near the equilibrium

point, the value

of

1x1

should not

be

so

high.

Similarly

to

[lo],

[ll],

we

simulate a single bottleneck link

with

capacity

c

=

4000

pkts/sec shared by

N

=

100

Reno

sources.

The

AQM

at the bottleneck link uses ECN marking.

If

there

is

no

specification,

we assume that the propagation

delay

is

d,

=

250ms.

Marking probability

of

each

AQM

is

updated every 2ms,

i.e.,

the sampling time

is

T,

=

2ms

(&(t)

=

b(t

-

T,)

+

T,-{l(y(t

-

T,)

-

y2c)).

The simulation

duration

is

30

sec,

where

this

duration

is enough

to illustrate

the

proposed

results.

For

all

simulations,

we

set

y1

=

1,

72

=

0.95,

and

X

=

-1.35,

where the maximum throughput

is

proportional

to

yz

E

(0,l).

Thus,

72

should

be

enough

large.

If

d,

is

too

small, the equilibrium

loss

probability

p*

becomes

high

and thus

TCP

Reno

can

experience time-out

many

times.

Since

the

TCP

Reno model

(1)

works

only

when

p*

is

small,

we

do

not

consider the

case

that

d,

is

small.

A.

P-type

and

PI-type

memoryless

AQMs

P-type

and

PI-type memoryless

AQMs.

In

this 

example,

we

illustrate

performances

of

the proposed

P and

PI-type

memoryless

AQMs

are

implemented by

p*

-

-yl(y(t)

-

TZC)

B1

P(t)

=

&o)

+

Hl(i(t)

-

i(to>)

+

TlHZ(Y(t)

-

Y(t0))l 

respectively,

where

H1

=

-&

and

HZ

=

--.

Figure

1

illustrates that

PI-type memoryless

AQM

(92

%)

seems

to have

a higher

utilization

than P-type memoryless

AQM

(77

%),

while both

of

them

have

a very

small queuing

delay

and

are

stabilizing.

B.

PI-type memoryless

and

PI-type memory

AQMs

control

structure.

In

this

example,

we

illustrate

the performance

of

a memory

PI-type

memory

AQM

is

implemented

by

P(t)

=

+

Hld(W

-

&(to))

+

TlHzd(Y(t)

-

Y(t0))

+H,d!?ld(t)

+

H2d!?Zd(t),

(12)

where

H,d

=

-%,

H$

=

-1X2(1-e-AZd)+A2(A2-2X)1

BI

A2e-A2d

9

and

Figure

2

shows

that

PI-type memory

AQM

has a

slightly

higher

utilization

(86%)

than PI-type memoryless

AQM

(82%)

in

the presence of large propagation delays,

while

they have

similar performance 92% when

d,

=

250ms.

Both

of

them

have very

small queuing delays and

are

stabilizing.

From

this

simulation

result,

we can

see

that

the

stabilizing

P-type

m6im)Iess

AQM

10

15

al

25

6me

(sec)

Fig.

1.

Average

window

w(t)

trajectory

3660