Simulation comparison of RED and REM - Networks, 2000. (ICON 2000). Proceedings. IEEE International Conference on

Simulation

Comparison

of

RED

and

REM.

Sanjeewa Athuraliya

Steven

Low

Department

of

EEE,

University

of

Melbourne, Australia

{

sadsa, slow} @ee.mu.oz.au

Abstract-We

propose

earlier an optimization

based

low

control for

the Internet

called 

Random

Exponential

Marking

(REM).

REM

consists

of a

link algorithm,

that

probabastically

marks

packets inside the

net-

work,

and a

source

algorithm,

that adapts

source

rate

to

observed

mark-

ing.

The marking

probability

is

exponential in a

link

congestion

mea-

sure,

so

that

the

e&-tc-end

marking

probability

is

exponential

in

apath

congestion

measure. Because

of

the

finer

measure

of

congestion

pro-

vided

by

REM,

sources

do

not constantly probe the network

for

spare

capacity,

but

settle

around

a globally

optimal

equilibrium,

thus avoiding

the

perpetual

cycle

of

sinking into

and

mcovering

from

congestion. In

this

paper

we

compare

the performance

of

REM

with

Reno

over

RED

through

simulation.

I. INTRODUCTION

We

proposed

earlier

a flow

control scheme for

the

Internet

called

Random Exponential

Marking (REM)

[

11.

It is derived

from

an

optimization model where

each source

is character-

ized

by

a utility

function that

models

its

valuation

of

band-

width and the goal is

to

maximize aggregate source utility

over

their

transmission

rates

subject

to

capacity constraints

[18],

[20].

The

basic

flow

control algorithm

can be regarded

as a

distributed computation performed

by

the sources and

links to

minimize

the dual problem. The

algorithm

how-

ever

requires

communication between

sources

and

links.

This

communication

requirement

is greatly simplified

in

[19],

[

11

and

leads

to REM, a

binary

feedback scheme similar

to Ran-

dom Early

Detection

(RED)

[

lo].

The

purpose

of

this paper

is to

compare

REM

and

RED

through simulation.

The

value

of

the

optimization

model presented in

[

181,

[20]

is twofold.

First,

though it

may

not be possible,

nor

critical,

that optimality

is exactly

attained

in

a real network, the op-

timization framework

offers a

means

to

explicitly steer the

entire

network towards

a desirable

operating point. Second

it makes possible

a systematic

method

to

design and refine

practical

flow

control schemes,

which

can

be treated sim-

ply

as

implementations

of

a certain

optimization algorithm,

where

modifications

to the

flow

control

mechanism

is

guided

by

modifications

to the

optimization

algorithm.

This

work

is

supported

by

the

Aushalian

Research

Council

under

grants 

S499705,A49930405

andS4005343.

The:

paper

is

structured

as

follows. In

Section

I1 we

sum-

marize our optimization model and the

REM

algorithm.

In

Section

I11

we

summarize

the

RED

algorithm.

In

Section

IV

we

present preliminary simulation

results

to compare the

per-

formance

of

REM

with

RED.

We

conclude

in Section

V with

future

work.

11.

OPTIMIZATION

MODEL

AND

REM

Consider

a network

that consists

of

a set

L

=

{

1,

.

. . ,

L}

of

unidirectional

links

of

capacity

q,

1

E

L.

The

network

is shared

by

a set

S

=

(1,

. .

.

,

S}

of

sources. Source

s

is

characterized

by

four parameters

(L(s),

U,,

m,,

M,).

The

path

L(s)

L

is a subset

of

links

that

source

s

uses,

U,

:

R+

-+

R

is a utility

function,

m,

2

0

and

M,

5

00

are

the minimum and maximum transmission

rates,

respectively,

required

by

source

s.

Source

s

attains

a utility

U,(x,) 

when

it transmits

at

rate

x,

that satisfies

m,

5

x,

5

M,.

We

assume

U,

is increasing

and strictly concave

in its argument.

Let

I,s

=

[m,,

M,]

denote

the

range

in which source rate

x,

must

lie

and

I

=

(I,

,

s

E

S)

be

the vector.

For

each link

1

let

S(1)

=

{s

E

S

1

E

L(s)}

be

the

set

of

sources

that

use

link

1.

Note

that

1

E

L(s)

if andonly

ifs

E

S(1).

Our

objective is

to

choose source

rates

x

=

(z,, 

s

E

5’)

so

as

to:

m=z,

€1.

U,

(56) 

(1)

8

subjectto

x,

5

cl,

1

=

1,.

.

.,L.

(2)

sES(I)

The constraint

(2)

says

that the total

source

rate at

any link

1

is

less

than the capacity.

A

unique maximizer, called the primal

optimal

solution, exists

since the

objective

function

is strictly

concave, and hence

continuous, and

the

feasible

solution set

is compact.

Though the

objective function

is separable

in

x,,

the

source

rates

x8

are coupled

by

the constraint

(2).

Solving the primal

problem

(1-2)

directly requires coordination

among possibly

all

sources

and

is impractical

in real

networks. The

key

to

68

0-7695-0777-8100

$10.00

0

2000

IEEE

a distributed and decentralized solution

is to look

at its

dual,

e.g.,

[2,

Chapter

61

In

[18],

[20] we propose

to

solve the dual problem using

the

gradient projection algorithm that leads to the following

optimization

flow

control algorithm:

Al:

Basic

Algorithm

Pl(t

+

1)

=

[pdt)

+

y(z"t)

-

Cl)]+

G(t)

=

zs(p"(t))

=

maz{m,,min{M,,

u;-'(p"(t))}}

The

dual variable

pl

can be interpreted

as

the price per unit

bandwidth

at

link

1.

Then

ps

is

the

total

price per unit

bandwidth

for

all

links

in

the path

of

s.

Here

z'(t)

:=

CsGs(l)

z,(t)

is the aggregate source

rate at

link

1

at

time

t,

and [z]+

=

max{z,

0).

Hence a link raises

or

reduces

its

price according as the demand

zz

(t)

is greater

or

less

than

the

supply

q

of bandwidth.

It is shown

in [20]

that provided

all utility

functions are

strictly

concave increasing and

their

second derivatives are

bounded away

from

zero, the basic algorithm

A1

converges

to yield the optimal rates

for

a sufficiently

small step-size

y.

As

discussed

there,

though the optimization problem

is for-

mulated as a

static

problem the

flow

control algorithm natu-

rally

adapts

to

changing link capacities and

set

of

sources

at a

link:

simply use the current link capacity

cl

(t)

and the current

set

S(1;

t)

of sources

at link

1.

Algorithm

A1

requires communication of link prices

to

sources and source rates

to

links,

and hence cannot be

im-

plemented

on

the Intemet.

In

[

11 we show

that a link can simply update

it's

price ac-

cording

to

~i(t

+

1)

=

[pi(t)

+

Y(albl(t)

+

i'(t)

-

cl)]'

where

i6

(t)

is the aggregate

input

rate

at link

1

and

bl

(t)

is the

aggregate queue length. Both the aggregate input

rate

2l(t)

and the backlog

bl

(t)

can be measured

at link

1.

The inclusion

of

bl

(t)

ensures small queue

at high

utilization.

Here

ai

>

0

is a small constant that can

be

different

at different

links.

In

equilibrium, price

p*

stabilizes.

For a non-bottleneck link

with

p:

=

0,

backlog

is zero

b;

=

0

and

i*l

5

Q.

For a bot-

tleneck link

with

p;

>

0,

we

must

have

alb;

+

2*l

=

q.

If

the equilibrium

buffer

is nonzero

b;

>

0,

then the input

rate

is strictly less

than the capacity

2*l

<

q,

and hence

the buffer

b;

could not have been

in equilibrium. Hence,

by

contradic-

tion,

we

must

have both

zero

buffer

b;

=

0

and

full utilization

2*'

=

cl

in equilibrium, provided prices

are

fed back exactly

to sources.

In

the reversed direction we propose a method

in that

com-

municates link prices to sources using only binary feedback.

The

basic idea

is for

a link

to

mark a packet with a probabil-

ity

that

is exponential

to

its

link price

pl

(t)

so

that the end

to

end marking probability of a packet

is exponential

to the

path

price

p"(t).

ml(t)

=

1

-

q5-pr(t)

(3)

m"(t)

1

-

n

(1

-mi(t))

=

1

-

f$-p"(t)

(4)

=

KL(5)

where

>

1

is a constant. and

wherep"(t)

=

cl,--(,)

pl(t)

is apath

congestion measure, the

sum

of link congestion mea-

sures along source

s's

path. Source

s

estimates

this

end-to-

end marking probability

mS(t)

by the fraction

h"(t)

of

its

packets marked

in

period

t,

and estimates the

path

conges-

tion measure

ps

(t)

by inverting

(4): 

F(t)

=

-log+(l

-

hs(t))

(5)

where

log4

is

logarithm to base

4.

It then

adjusts

its

rate

using marginal

utility:

zs(t)

=

[u;-l($s(t))lz: 

(6)

where

U;-'

is

the inverse

of

the marginal

utility,

[z]:

=

max{min{z,

b},

U}.

We

get window size through multiply-

ing

this

source

rate

by the estimated round

trip

time of the

connection. See

[l]

for

details.

This

can be implemented

us-

ing the proposed

ECN

(Explicit Congestion Notification)

bit

in the

IF'

header

191,

[23].

When prices are fed back only approximately

using

a sin-

gle

bit,

as

in

REM,

the source rates and backlogs

fluctuate

around

their

equilibrium values.

The

random fluctuation can

be attributed

to noise and delay associated

with

estimation

of

path

prices

by

the sources

from

marked packets. This elim-

inates the need

for

explicit communication from sources

to

links.

A2:

REM

Combining these two simplifications yields the

REM

algo-

rithm. Figure

1

and Figure

2

give pseudo-code

for

source and

link

algorithms.

For the simulation

we

use a smoothed version of the source

algorithm. In the smoothed version the price

is estimated and

window

adjusted once

in

each round

trip

time. For each ad-

justment, the

window

is incremented

or

decremented

by

1

ac-

cording as the target value determined by the price

as

in

the

69

periodically

update aggregate input rate:

udpate marking probability

ml:

in

t

(1

-

6)

x

in

+

6

x

new-in

pi

c

max{pl

+

y(o1

x

buffer

+

in

-

capacity),

0)

ml

t

l-+-Pt

endperiodically

while

buffer

not

empty

endwhile

mark packet with probability

ml

as

it leaves

Saved variables:

in:

aggregate

input rate estimate

pi

:

link

price

ml

:

current marking probability

Fixed parameters:

6:

weight

in aggregate input

rate estimation

y:

stepsize

in

price

adjustment

al:

weight

of

buffer

in price

adjustment

9:

base in marking probability

computation

newin:

current

aggregate input

rate

buff

er:

current

buffer occupancy

(may be smoothed)

capacity:

cmnt

link

capacity

(may

be

estimated)

Temporary

variables:

~

~~~

Fig.

1.

Pseudocode for

link

algorithm

original

algorithm

is larger

or

smaller

than the

current

win-

dow.

See

[

11.

111.

COMPARISON

WITH

RED

AND

RENO

RED

[lo]

is a link

algorithm

and

has

been widely

experi-

mented

together

with

TCP

Reno.

In

this section

we

remark

on

several differences between

REM

and

RED

with

Reno.

A.

Comparison

Before comparing the performance

of

REM and

RED,

we

first make two

remarks,

first on

the interpretation

of

marks

in

RED and REM and

then

on

the

network

behavior.

First a mark

in RED

is a request

to slow

down.

It signals

congestion

at

some bottleneck along a path.

Reno

responds

by

halving

its window.

Marking

in REM,

on the

other hand,

allows

a source to estimate

the

aggregate

shadow

price

of

its

path.

Given

that,

whether a

source

should

slow

down,

or

speed up,

depends

on

its

marginal

utility.

This

is a conse-

quence

of

the exponential

form

of

REM's marking probabil-

ity.

A

REM

source does

not need

to

constantly probe

the

network

for

spare capacity,

as

Reno does.

This

eliminates the

perpectual cycle

of

sinking into congestion and recovering

from

it.

for

each

ACK

arrival

update round trip time estimate:

update

fraction

of

marks

in

the

last

N

ACKs

calculate

new

rate:

RTT

t

(1

-

B)

X

RTT

+

B

x

RTTdf-ACK

if

fraction

=

0

elseif

fraction

=

1

else

x.

e

max-rate

xs

t

man-rate

ps

-

log(1-fraction)

log

9

x,

t

max{min{w,

/ps,

maxrate}, minrate}

endif

set

window

size:

window

t

ceiling

(2,

x

RTT)

enidfor

Saved

variables:

-

RTT:

round

trip time estimate

fraction:

fraction

of

marks

in last

N

ACKs

window:

window

size

/3:

weight

in

RTT

estimation

N:

sample size for price estimation

9:

base

in price estimation

maxrate:

maximum source rate

man-rate:

minimum source rate

Temporary

variables:

RTT-o

f

ACK:

round

trip

time

of

new

ACK

ps

:

path price

xs:

source rate

Fixed parameters:

Fig.

2.

Pseudocode for source algorithm

with

U,(xs)

=

w,

logx,.

Second

the

behavior

of

a network

of

RED routers shared

by

a set

of

Reno sources seems hard to understand [22].

Tractable

models

with multiple

sources

and

multiple links

need to

be

developed

to

provide a

conceptual

understanding

of

iissues

such as stability and

fairness [13],

[16]. 

REM on

the

other

hand

is an

implementation

of

the

basic

model

of

1201

using binary feedback.

The stability

and

fairness

of

the basic

algorithm

have been

established

in

[20],

and

they

determine

the macroscopic behavior

of

REM.

Indeed,

the behavior

of

the network

as

a

whole under

REM is

easily understandable:

the sources

and

links

form

a distributed computation system

to

carry

out a stochastic gradient

algorithm

to

solve the dual

problem.

IV.

SIMULATION

STUDIES

We

now

compare,

through simulation,

REM

and RED

with

1\11

simulations

are

conducted

in the

ns-2

simulator

for the

Reno

in terms

of

stability, robustness and

fairness.

70

single link network of Figure

3

with

n

sources.

ROUTER

-

cpacketdm

Fig.

3.

Network

Topology.

The

sources may

have

different round

trip

propagation de-

lays

in

different experiments. They

all

execute

FI’P

(File

Transfer Protocol),

i.e., all

are

greedy.

The

size

of each packet

is

1KB. 

At

therouter a

buffer with

a capacity

of

100

packets

is

used. Packets

are

served in FIFO order and are marked with a

probability determined by the link algorithm

(REM

or

RED).

The

first

experiment studies the robustness of RED and

REM

to parameter

setting.

For RED

we

use maximum threshold

=

80,

minimum

threshold

=

20,

maximum probability

=

0.1

and

wp

=

0.002

[lo].

We

run the simulation

for

200 seconds.

At

Os

10

sources

are active and

on

each

50s

thereafter

10

more sources

acti-

vate

until

the

total

number of sources

is

equal

to

40

at 200s.

All

sources

have

the same propagation delay of 20ms. The

bottleneck link (shared

link)

has

a capacity

of

4

packets/ms.

Figure

4

give the simulation

results

for

RED. As simulation

results

indicate the

queue

length steadily increase as more

sources become

active.

With

40

sources

active,

there

is

a

average queueing delay of about 20ms which

is comparable

with

the propagation

delay. When

the number

of

connections

is equal

to

10,20,

a value

of

0.1

for

the maximum probability

allows congestion notification to

be

signalled

to a sufficiently

large proportion

of

connections. Hence the offered load

is

reduced appropriately thus resulting

in

a smoothed and

low

buffer occupancy. But

when

a large number

of

connections

are

active,

the congestion notification

is to weak

and

results

in

a increased buffer occupancy. These simulation

results

show

the

difficulty in

choosing RED parameters

to give

satisfac-

tory performance

in the face

of

changing network conditions.

They

are

consistent

with

earlier

studies

[6],

[7]

On the otherhand

REM

seems

to

be

quite

robust to vary-

ing

traffic

load.

We

repeat

the

simulation study

with REM.

The

utility

functions of the

REM

sources

are

w,

log

z,,

where

w,

is equal to the bottleneck link capacity.

The

other REM

parametrs are

set

at

S

=

0.02,

p

=

0.02,

N

=

50,

y

=

0.001

and

at

=

0.1.

The

results

are

given in Figure

5.

The per-

formance

is very

good with a high

utilization

(>

96%)

and

small queue. There

are

spikes in the buffer occupancy

when

sources

join. The

key

feature

of

REM

is

low

buffer

occu-

pancy

at steady

state

while achieving a high

utilization at

the

same time as the number of active connections changes.

0

,I,,

,

I

0

20

40

O

BO

1w

120

140

IO

180

200

time

(-.I

Fig.

4.

Queue

Length

for

RED. 

Fig.

5.

Queue

Length

for

REM. 

The

second experiment studies faimess and

is on

the same

network topology.

It consists

of

six

connections

having

dif-

ferent propagation delays equal to

10,

20,

...,

60.The

results

are

given in

Figure

6.

Reno sources

with

large propagation

71

delays are

discriminated

against,

as observed

in many previ-

ous

studies

[3], [8],

[lo],

[17], [21].

The

throughput share

under

REM

on the other-hand is independent

of

propagation

delay.

e

;

02

3

io15

01

005

0

1

2

3

4

5

8

Fig.

6. Throughput share.

V.

CONCLUSION

We

have

presented

a Random Exponential

Marking algo-

rithm 

for

flow

control as

a practical implementation

of

the

basic

algorithm

of

[18], [20]

that achieves social optimality.

Simulation

results

show that

it is robust and that its

fairness

is

independent

of

propagation delay. Even

though

REM

has

been presented

as

consisting

of

both a link and a

source

al-

gorithm,

its

unique advantage is that it provides each source

with

a congestion measure that

is aggregated over its path.

It

can

thus work with

other source

algorithms that can exploit

this

path

congestion measure.

REFERENCES

[7]

PI.

Feng,

D.

Kandlur,

D.

Saha,

and

K.

Shin.

A self-configuring

RED

gateway.

In

Proceedings

of

INFOCOM'99,

March 1999.

[8]

S.

Floyd.

Connections with multiple congested

gateways

in

packet-

switched networks, Part

I: one-way

traffic.

Computer Communications

Review,

21(5), October 1991.

[9]

S.

Floyd.

TCP

and Explicit Congestion

Notification.

ACM

Computer

Communication Review,

24(5), October 1994.

[lo]

S.

Floyd

and

V.

Jacobson. Random early detection

gateways

for con-

gestion avoidance.

IEEEIACM

Trans. on Networking,

1(4):397413,

August 1993.

[ll]

R..

J.

Gibbens and

E

P. Kelly.

Resource pricing

and

the

evolution

of

c'ongestion

control.

Automafica,

35, 1999.

[12]

Jmxd

Golestani and Supratik Bhattacharyya.

End-toend

congestion

control

for

the Intemet:

A

global optimization

framework.

In

Pro-

ceedings

of

International

Con$

on

Network Protocols

(ICNP),

October

1998.

[13]

Paul

Hurley, Jean-Yves

Le Boudec,

and

Patrick

Thiran.

A note

on

the

faimess

of

additive increase and multiplicative decrease.

In

Proceed-

ings

of the

ITC,

volume

16, June 1999.

[14]

F.

P.

Kelly.

Charging and rate control

for

elastic

traffic.

European

Transactions on Telecommunications,

8:33-37,

1997.

http://www.statslab.camac.uk/-Welastic.html. 

[15]

Frank 

P. Kelly,

Aman Maulloo, and David Tan. Rate control

for

com-

munication networks: Shadow prices, proportional faimess and stabil-

ity.

Journal

of

Operations Research Society,

49(3):237-252,

March

1998.

[16]

Srisankar Kunniyur and

R.

Srikant.

End-to-end

congestion control

schemes:

utility

functions, random losses and ECN

marks. 

In

Pro-

ceedings

of

IEEE

Infocom,

March 2000.

[17] T.

V.

Lakshman and Upamanyu

Madhow.

The

performance

of

TCPm

for

networks with high

bandwidMelay

products and random loss.

IEEELACM

Transactions

on

Networking,

5(3):336350,

June

1997.

[181

David E.

Lapsley and Steven

H.

Low. An

optimization approach

to

ABR

control. In

Proceedings

of

the

ICC,

June

1998.

[19]

Steven

H.

Low.

Optimization

flow

control with on-line measurement.

In

Proceedings

of

the

ITC,

volume 16, June 1999.

[20]

Steven

H.

Low

and David

E.

Lapsley.

Optimization

flow

c:ontrol,

I:

basic algorithm and convergence.

IEEELACM

Transactions

on

Networking,

7(6):861-874,

December

1999.

~ittp://www.ee.mu.oz.au/staff/slow/resea.

[21]

Matthew

Mathis,

Jeffrey

Semke, Jamshid Mahdavi, and

Teunis

Ott.

The

macroscopic behavior

of

the

TCP

congestion avoidance algorithm.

ACM

Computer Communication Review,

27(3), July 1997.

[22]

Pdartn

May,

Thomas 

Bonald, and Jean-Chrysostome Bolot. Analytic

evaluation

of

RED performance. In

Proceedings

of IEEE

Infocom,

March 2000.

[23]

I<.

K.

Ramakrishnan and

S.

Floyd.

A

Proposal

to

add Explicit Con-

gestion

Notification

(ECN) to

IP.

Intemet draft draft-kksjf-ecn-01

at,

July

1998.

Sanjeewa Athuraliya, Steven

Low,

and

David Lapsley.

Ran-

dom Exponential

Marking.

Submitted for publication,

hnp://www.ee.mu.oz.au/staff/slow/researc~,

January 2000.

D.

Bertsekas.

Nonlinear Programming.

Athena Scientific, 1995.

Thomas 

Bonald.

Comparison

of

TCP

Reno and

TCP

Vegas

via

fluid

approximation. In

Workshop

on

rhe

Modeling

of

TCP,

December 1998.

Available

at

http://www.dmi.ens.fr/r/%7Emisrral/tcpworkshop.ht1nl. 

Lawrence

S.

Brakmo and Larry

L.

Peterson. TCP

Vegas:

end to end

congestion avoidance on

a global Internet.

IEEE

Journal

on

Selected

Areas

in

Communications,

13(8), October

1995.

Costas

Courcouktis,

Vasilios

A.

Sins,

and

George D. Stamoulis. Inte-

gration

of

pricing and

flow

control for

ABR

services

in ATM

networks.

Proceedings

of

Globecom

'96,

November 1996.

W.

Feng,

D.

Kandlur, 

D.

Saha, 

and

K.

Shin. 

BLUE: a

new

class

of

active

queue

management algorithms. Technical report,

University

of

Michigan, Michigan, USA, 1999.

UM

CSE-TR-387-99.

72