Scalable laws for stable network congestion control - Decision and Control, 2001. Proceedings of the 40th IEEE Conference on

Roeeediog

of

the

40th

IEEE 

Conference

on

Decision

and

Conel

Orbdo,

Florida

USA,

December

2001

Scalable

Laws

for

Stable

Network

Congestion

Control

Fernando

Paganinil

John

Doyle2

Steven

Low3

Abstract

This paper

discusses

flow

control

in

networks,

in

which

sources control

their

rates

based

on

feed-

back signals

received from

the

network links,

a

fea-

ture

present

in

current

TCP

protocols.

We de-

velop

a

congestion

control system

which is

arbitrar-

ily

scalable,

in

the

sense

that

its

stability

is main-

tained

for

arbitrary

network topologies

and

arbi-

trary

amounts

of

delay.

Such a

system

can

be

im-

plemented

in

a decentralized

way

with

information

currently

available

in networks

plus

a small

amount

of

additional

signaling.

1

Introduction

Flow

control

in

a communication

network

like

the

Internet

concerns

the adjustment

of

individual

source transmission

rates

so

that

network resources

are

fully

utilized,

and

link capacities

are

not

ex-

ceeded.

Existing protocols

such

as

TCP

regulate

their

transmission

rates

by

a

congestion

window

of

outstanding

packets;

feedback

signals from

the

net-

work

(packet

acknowledgment

or

loss)

are

used

to

dynamically

adjust

this

window

to

match

available

capacity.

The

additive

increase multiplicative

de-

crease

(AIMD)

algorithm

of

TCP

Tahoe

[6]

and its

enhancements

(Reno,

etc.) has

performed

remark-

ably

well

as

the

network

scales

up

several

orders

of

magnitude.

However

future growth

combined

with

the

upcoming diversity

of

traffic

and

communica-

tion

substrates

will

stretch

the

limits

of

this

simple

algorithm,

calling

for

a

more extensive

analytical

investigation

of

the

problem.

Exciting

progress

has

been

made

very

recently

tw

wards a

theoretical understanding

of

TCP,

both

of

its

equilibrium,

using

optimization

theory,

and its

dynamics,

using control theory.

Key

to

these

de-

velopments

has

been

to

explicitly

model

the

feed-

back signal

generated

by

links

and

communicated

to

sources;

in

practice these signals correspond

to

packet

dropping, or

packet

marking

when

Explicit

Congestion

Notification

(ECN) bits

are

available.

Interpreting

these

signals

as

prices

has

allowed

for

the

rate

assignment

problem

to

be cast in

sup-

plyldemand

terms

[8];

in

a related

interpretation

[13],

prices

correspond

to

Lagrange

multipliers

of

a certain optimization

problem.

When

applied

to

the

existing variants

of

TCP,

this

framework

allows

for

the

analysis

of

the

resulting equilibria

[12].

In

terms

of

the

dynamics

of

TCP,

very

recently

an

analytical

model

has

been developed

[18]

that

correlates

well

with

standard

simulators,

and

al-

lows

for

stability studies

[5].

It

is found

that

TCP

exhibits

oscillatory instabilities

as

delays

grow,

and

perhaps more

surprisingly,

as

link

capacities

grow.

This

motivates

the

investieation

of

new

nrotocols

..

where

one

could provide

guarantees

of

stability,

ro-

bustness

to

delay

and

scalability

to

large capacities

and

arbitrary

topologies.

Some

work in

recent

years

coming from

the

con-

trol community

(e.g.

[I,

19,

161)

has

investigated

both

classical

and

modern

tools

in

these

problems,

however

results

are

mainly

confined

to

single

bot-

tleneck networks.

For

arbitrary

networks,

the

work

on

price signals

bas

allowed for

global

stability

re-

sults

[8,

13,

20,

101,

but

only

when

ignoring

de-

lays.

When

considering

delays,

one

is

forced

to

slow

down

the

control gains

to

retain

stability

(see,

e.g.

[8,

13,

211).

As

noted

in

[9],

this

mechanism

is

already

implicit

in

window-based

protocols

and

it

is

therefore

conceivable

that

one could

obtain

stability

for

arbitrary

delays.

In

this

vein, recent

work

in

[7,

17,

221

has

derived

conditions

for delay

rohustness for

the

protocols

in

181.

In

this paper

we

pose

the

objective

of

finding a

protocol

which

can

be

implemented

in

a decentral-

ized

way

by

sources

and

routers,

and

satisfies some

basic objectives:

efficient use

of

network

resources

in

equilibrium,

and

local

stability

for

arbitrary

ca-

pacities,

delays,

and

routing. These requirements,

laid

out

in

Section

3,

lead

us

to

adopt

some

con-

ditions

for

the

linearized

dynamics:

integration

at

the

links,

and

certain

scalings

on

the

gain

at

sources

and

links.

In

Section

4

we

then

prove

that

a system

with

these

properties

will

satisfy

our

requirements,

combining

ideas

in

[7]

with

methods

of

multivari-

able robust

control.

In

Section

5

we

show

how

'UCLA

Electrical

Engineering,

LOS

~~~~l~~,

CA

90095.

to

implement

the

source

control

laws

by

nonlin-

1594.

Corresponding

author.

E~~~I:

paganini@ee.ue~a.edu.

ear

functions

which

around

equilibrium provide

the

ZControl

and

Dvnamical

Svstems.

Caltech.

Pasadena.

correct

dvnamic

linearization.

and

in

Section 6

we

CA

91125.

give

some

comments

on packet-level

implementa-

3Computer

Science

&

Electrical Engineering,

Caltech,

Pasadena,

CA

91125.

tion.

Conclusions

are

given in

Section

7.

0-7803-7061-9/01/$10.00

O

2001

IEEE

185

2

Problem

Formulation

We

are

concerned with

a system

of

L

communi-

cation links shared

by

a set

of

S

sources.

For

each

link

1

we

have:

the

capacity

CI,

the

aggregate

rate

yl

of

all

flows

through

the

link,

and

the

price sig-

nal

pi.

For

each

source

i

we

have

the

source

rate

xi,

and

the

aggregate

price

qi

of

all links

used by

source

i.

We

will work

with

pow

models,

i.e.

re-

gard these

variables

as

deterministic,

non-negative

real-valued.

We

use

vector

notation

to

collect

the

above variables across all links

or

sources;

thus

we

definec,y,p~R~,andz,q~R~.

We

now

model

the

network, including

the

propa-

gation delays,

in terms

of

the

relationships (in

the

Laplace

domain,

denotes

transpose)

~(s)

=

Rf(~)z(s),

(1)

q(s)

=

Rb(~)~p(s).

(2)

Here

Rf

and

Rb

are

the

delayed forward

and

back-

ward

routing matrices,

defined

by

q

=

qo

+

6q.

Assuming

the

set

of

bottlenecks

is un-

changed

by

this

small

perturbation,

6pr

is only non-

zero

for

bottleneck links. Therefore

for

the

local

analysis

to

follow,

we

can write

the

reduced model

where

the

matrices

R,,

Rb,

and

the

vectors

615,

6g

are

obtained

by

eliminating

the

rows

correspond-

ing

to

non-bottleneck links.

For

simplicity

in

the

sequel,

we

drop

the

"bar"

notation and

assume

the

routing matrices

such

as

(3)

refer

only

to

bottleneck

links.

A subtlety

arises when employing

the

linear equa-

tion

(5) for

incremental

flows:

a bottleneck link

includes

effectively

a saturation

nonlinearity

in

its

outgoing

flow,

preventing

an

increase

62

in one

of

its

source

flows

from

propagating

to

downstream

links.

We

eliminate

this

issue

by

assuming

that

the

target

rate

cr

for each link

is

slightly

lower

than

its

actual

capacity

(a

"virtual"

capacity,

see

[ll]).

This

is also desirable since

it leads

to

empty

equi-

eCr!l8

if source

i

uses link

1

[Rf(s)h,i

=

,

(3)

librium queues.

0

otherwise

We

will

also assume

that

the

matrix

R

=

Rt(0)

=

,.

,

and

similarly for

Rb(s)

with

rll

replaced

by

rtl.

Rb(0)

is of full

row

rank. This

means

that

there

are

link

flows

are

obtained

by

aggregation,

with

no algebraic

constraints

between bottleneck link

respective delays

rll

,

of source

flows

using

the

link;

flows,

ruling

out,

for

instance,

the

situation

where

prices

seen

by

sources

are

aggregations,

with delays

all

flows

through

one link also go

through another.

rtI,

of link prices used

by

the

source.

We

define

the

Note,

that

Our

refer

now

to

total

round

trip

time

(RTT)

by

source,

bottlenecks

only,

and

typically in

the

above

sce-

nario

only

one

of

the

links

would

be

a bottleneck;

r;

=

~b

+

~f

(4)

SO

our

assumption

is quite

generic

r,l

1.1'

This

quantity is

available

to

sources

in real

time.

3

Control

objectives

and

a

proposed

law

What

remains

to

be

specified

is:

(i)

How

the

links

fix

their

prices based on

link

utilization; (ii)

how

We now

proceed

to

lay

out

a series

of

objectives

the

sources fix

their rates

based on

their

aggregate

for

the

feedback

control

laws

in

Purely

local

(lin-

price. These

operations

are

up

to the

designer,

hut

earized)

terms.

These

will

lead

us

to

conjecture

a

have

a

main

restriction:

both

must

be

decentml.

candidate

local

control

law,

which

we

argue

is the

ized. 

For

instance

the

source

rate

z,

can

only

de-

simplest

that

can

satisfy our

requirements,

and

at

pend

on

the

aggregate

price

qi.

~h~

the

same time

allows

for

the

required decentralized

objective

of

this

feedback

is

to

allow

for

flows

to

implementation.

In the

we

will

prove

track

,-hanging

conditions

in

traffic

demand,

link

that

it actually

achieves

our

objectives.

capacity,

routing, etc.

Key design

considerations

A

first

objective

is that

the

target

capacity

cr

is

are

thus

to

ensure

dynamic

stability

and

regula-

matched

at

equilibrium;

this

calls for

an

integra-

tion

of

these systems around

equilibria

that

satisfy

tor

in

the

feedback loop.

As will

become clear

in

desirable

static

properties.

the

to

have

stability

we

must

perform

l-his

paper

is

mainly

concerned

with

the

dy.

the

integration

at

the

lower-dimensional

end

of

the

namic

properties around a

given

equilibrium

point

problem,

i.e.

at

the

links.

So

we

write

so,

yo,po,

qo.

For

more discussion

on

equilibria

see

Section

5,

but

for

now

we

only require

that

yo1

5

el

PI

=

86~1

(link capacities

are

not

exceeded),

and

that

non-

as

in

[13],

i.e.

prices

integrating

excess capacity.

bottleneck links

(those

where

yo1

<

cr)

have

a price

The

constant

@I

will

be

chosen

later.

pol

=

0.

The

next,

main objective is

to

have

local

dynamic

Now

consider

a small

perturbation

around

equi-

stability

for

arbitrary

network delays, link

capaci-

librium;

x

=

so

+

62,

y

=

yo

+

6y,

p

=

pa

+

bp,

ties

and routing

topologies.

186

Regarding

delays,

consider

first

the

case

of

a sin-

gle

link

and

source.

The

link

integrator,

plus

the

network

delay

will

yield

a term

e-"/s

in

the

loop

transfer

function,

which

leads

to

instability

as

7

grows, unless

the

gain

is made

a function

of

T.

In-

deed, introducing

a

gain

l/r

in

the

loop

(specifi-

cally

at

the

source,

which

measures

RTT),

gives

a

loop

transfer function

-,,

e

-

7s

(7)

which is

scale-invariant: namely,

its

frequency

re-

sponse

is

a function

of

0

=

TW,

so

Nyquist

plots

for

all

values

of

r

would fall

on

a single

curve

r,

depicted

below.

If

the

overall

gain

is

kept under

control,

then

we

can

have

stability

for all

r.

Fur-

ther,

closed

loop

time

responses

for different

7's

would

be

the

same

except

for scale.

Summarizing

the

above requirements

in

their

simplest

possible

form,

we

propose

the

source

con-

trol

law

(between

69,

and

bz;)

to

be

the

static

gain

where

a;

is

a parameter.

The

sign

provides

nega-

tive

feedback.

As

link

control,

we

take

an

integrator

with

gain

normalized

by

capacity,

1

bpi

=

-6~1.

Cl

s

(9)

With

this

normalization,

the

price

corresponds

to

a

(virtual)

queueing delay

at

the

link,

similar

to

the

case

of

TCP

Vegas

[3,

141.

4

Linear stability results

I

9~

I

-.

.

-~

0.

Figure

1:

Nyquist

plot

of

eJ8/j0

Going

now

to

the

general network case,

we

will

extend

the

above

by

including a

gain

l/ri

at

each

source.

In

the

multivariable

setting,

however,

we

must

also

compensate

for

the

effect

of

the

routing

matrices

Rf,

Re;

intuitively,

as

more links

partici-

pate

in

the

feedback

the

gain

must

be

appropriately

scaled down.

The

difficulty is

implementing

this

in

a

decentralized fashion,

without

access

to

the

global

routing

information.

One

source

of

information

that

can

be

exploited

is

that

at

equilibrium,

the

aggregate

source

rates

add

up

to

capacity, so

Rzo

=

c.

This

motivates

1

the

following

heuristic:

introduce

(i)

a gain

,8l

=-

9

at

each link;

and

(ii)

a gain

zo;

at

each

source,

in

Figure

2:

Overall

feedback loop

With the

source

and

link

controllers

described

above,

we

proceed

to

study

the

linearized

stability

of

the

closed

loop.

We

express

the

overall,

multi-

variable

feedback

loop

in

the

classical

configuration

of

Figure

2,

with open

loop

transfer

function

L(S)

=

R~(S)KRT(S)C$,

(10)

where

4

is the

identity

matrix

of

size

L,

and

1

X

=

diag(n;),

C

=

diag(-).

4

Note

that

there are

no

unstable

pole/zero

cancel-

lations within

L(s);

the

proposition

below

provides

stability

conditions

for

such multivariable loops

with

integral

control.

Proposition

1

Consider a

standard

unity

feed-

I

back loop,

with

L(s)

=

yF(s);.

Suppose:

addition

to

the

117;

factor.

In

the

case

of

a

single

link,

and

possibly

many

sources,

this

gives

a loop

(9

F(s)

is

analytic

in

Re(s)

>

0,

and

IIF(s)II

5

transfer function

of

0

in

Re(s)

2

0.

zoi

e-j,w

L(jw)

=

--,

(ii)

F(0)

has strictly

positive

eigenualues

CI

riw

i

-.

~.--

(iii)

For

all

7

E

(O,l],

-1

is not

an

eigenvalue

of

which is

a convex

combination

of

points

of

the

form

L(~w),

w

#

0.

(7);

looking

at

the

figure,

it follows

that

this

convex

combination

will

remain

stable

by

a Nyquist

argu-

Then the

closed

loop

is

stable

for

ally

E

(0,1].

ment.

In

the

multiple

link

case,

we

are

still

left

with

the

need

of

bounding

the

gain

of

the

backward

path

In essence,

the

above

conditions

are

a "nominal"

Rb;

an

analogous

strategy

is to

introduce

a gain

&

stability

requirement for

small

y,

that

says

that

at

each source,

Mi

being

the

number

of

bottleneck

we

have

strictly

negative

feedback

of

enough

rank

links

in the

source's

path.

For

a discussion

on

its

to

stabilize all

the

integrators,

and

a

"robustness"

implementation,

see

Section

5.

argument

that

says

we

can

perform a

homotopy

to

187

y

=

1

without bifurcating

into

instability.

Details

of

the

proof

are omitted

for brevity.

Applying

this

to

the

L(s)

in

(lo),

we

take

F(S)

=

R~

(s)KR:(s)c;

we

will

later

add the

scaling

7.

Note

that

(i)

is

automatically

satisfied. For

(ii),

note

that

eig(F(0))

=

eig(Ci

RKR~C~),

where

R

=

Rf

(0)

=

Rb(0)

is the static

routing

ma-

trix.

Assuming

R

has

full

row

rank,

condition (ii)

will

hold. Here

we

see

the

importance

of

putting

the

integrators

at

the

links

(the

lower

dimensional

portion).

If,

instead,

we

tried

to

integrate

at

the

sources,

the

resulting

feedback

matrix

at

DC

would

never have enough

rank

to

stabilize

the

(larger)

number

of

integrators.

What

remains is

to

establish (iii).

For

this

pur-

pose

we

bring in some

more

notation:

Also,

Rb(s)

=

Rf

(-~)diag(e-~<~)

follows

from

(4),

where

R?(s)

=

RF(-s)

is the

adjoint

system.

We

incorporate this notation

to

rewrite

L(s),

for

s

#

0,

in

the

more

convenient form

L(s)

=

Rr(s)XoMA(s)Rt(s)C.

(11)

We

now

tackle

the

robustness argument.

Theorem

2

Consider

an

equilibrium

point

where

rates

match capacity,

i.e.

c

=

Rf

(0)xo.

Let

a,

<

5

and

the

delays

be

arbitrary.

Then

with

L(s)

as

in

(11),

-1

?!

eig(L(iw)),

w

#

0.

Proof:

Since

nonzero

eigenvalues

are

invariant

un-

der

commutation,

and

also

many

of

the

factors in

(11)

are

diagonal,

we

observe

that

Claim:

This

amounts

to

bounding

the

spectral radius

Any

induced

norm

will

do,

but

if we

use

the

1,-

induced

(max-row-sum)

norm,

we

find

that

1

IICRf

(jw)Xollm-in,j

=

max-

le-'~lJwxoil

i

uses

I

1

=max-

C

xoi=1;

i

uses

I

note

we

are

dealing with bottlenecks.

Also

the

norm

llMRjll

is

equal

to

1,

because

each

row

con-

tains

exactly

Mi

elements

of

magnitude

1/Mi.

So

p(P)

<

1

as

claimed. Indeed,

p(P)

=

1

at

w

=

0,

the

eigenvector being

the

vector

of

all ones.

Now

suppose

-1

E

eig(P(jw)A(jw))

for some

w.

We

thus

have a vector

u,

lul

=

1

such

that

y

=Au,

u

=

-Py.

Now

u*y

=

u*Au

=

i

is

a convex

combination

of

the

{Xi},

which

are

points

in

the

curve

r

of

Figure

1,

scaled

by

ai

<

5.

It

is clear from

the

figure

that

such

convex combi-

nations

and

scaling

cannot

reach any point

in

the

half-line

(-w,

-11.

However,

we

also have

using

(12). So

u'y

E

(-w,

-11,

a contradiction.

Remark

1

Some

elements

of

the

proof,

in particu-

lar

the

use

of

1,

induced

norms

to prove

a

spectrnl

radius

bound,

are

inspired

by

the

work

of

[7]

for

the control laws

in

181.

More recently

[22]

has

ex-

tended the

stability argument

for

the

laws

in

[8]

in

a parallel

fashion

to

our

work.

Theorem 2 establishes

(iii)

in Proposition 1; note

that

scaling

down

by

y

is equivalent

to

making

the

a;

smaller.

To

summarize,

we

have:

Theorem

3

Let

Rf

(s),

Ra(s)

denote

the

routing

matrices

of

sources

in

relation

to

the bottleneck

links. Suppose

Rf

(0)

=

Rb(0)

has full

row

rank,

and that

ai

<

f.

Then

the system

with

source

con-

troller gain

(8)

and

link

controller

(9)

is

linearly

stable

for

arbitrary

delays

and

link capacities.

We

have

modeled

a law

consisting only

of

the

integrator

and

delay

dynamics,

but

otherwise with

only gains

at

links

and

sources. Could

this stability

argument extend

to

include

additional

dynamics?

In

this

regard,

a first comment

is

that

there

can

be no

more

pure integrators.

Otherwise

the

Nyquist

plot

in

Figure

1

would

branch towards

-oo, 

and

convex combinations

of

such

points

could

reach

the

critical point.

In

particular,

the

second

order

link laws

used

in

REM

[2]

would

not

qualify.

Given

this,

and

the

requirement

of

scale-invariance

to

delay,

all

additional dynamic

terms

should

be

lo-

cated

at

the

sources,

so

that

they can

he

"clocked"

at

the rate

of

the

round-trip

time.

For

instance

a

term

A

could

be

added

to

the

source controller;

restrictions

on

would

he

required.

188