Target-Pursuing

Policies

for

Open

Multiclass

Queueing

Networks

Ioannis

Ch.

Paschalidis

Chang

Su

Michael

C.

Caramanis

Abstract

—We

propose

a

new

parametric

class

of

scheduling

and

routing

policies

for

open

multiclass

queueing

networks.

We

es-

tablish

their

stability

and

show

they

are

amenable

to

distributed

implementation

using

localized

state

information.

We

exploit

our

earlier

work

in

[1]

to

select

appropriate

parameter

values

and

out-

line

how

optimal

parameter

values

can

be

computed.

We

report

numerical

results

indicating

that

we

obtain

near-optimal

policies

(when

the

optimal

can

be

computed)

and

significantly

outperform

heuristic

alternatives.

Index

Terms

—

Scheduling,

Routing,

Multiclass

Queueing

Net-

works,

Fluid

models.

I.

I

NTRODUCTION

R

ECENT

trends

in

communications

and

computing

have

popularized

the

use

of

application

service

providers

(ASPs)

in

running

demanding

applications.

ASPs

own

a

clus-

ter

of

servers,

including,

Web,

database,

and

other

application-

specific

servers,

often

connected

in

a

high-speed

LAN.

Users

can

access

this

cluster

remotely

to

run

the

desired

application,

which

can

involve

multiple

tasks,

e.g.,

accessing

a

Web

in-

terface,

authentication,

queries

to

database

servers,

accessing

other

application

servers.

As

a

result,

overall

performance

is

not

only

dictated

by

communication

latencies,

but,

increasingly,

by

processing

times

of

these

tasks

at

the

various

servers.

Typical

control

actions

that

affect

performance

include

rout-

ing

and

scheduling

or

sequencing

.

Routing

decisions

determine

which

server,

among

potentially

multiple

candidates,

will

be

assigned

to

a

particular

task.

Scheduling

decisions

determine

which

task

to

serve

at

each

point

in

time.

Scheduling

can

be

done

at

both

the

server

level,

among

jobs

that

wait

to

be

pro-

cessed

by

the

server,

and

within

a

server

among

jobs

that

wait

to

access

the

various

server

resources

(e.g.,

CPU,

disk,

NIC,

etc.).

See

for

example

[2]

on

the

importance

of

the

latter

sort

of

scheduling

in

Web

servers.

In

this

paper

we

cast

these

problems

in

a

unified

framework

and

consider

scheduling

and

routing

in

a

Markovian

Multiclass

open

Queueing

NETwork

(MQNET)

.

Nodes

in

the

network

cor-

respond

to

servers

in

the

cluster

and/or

internal

server

resources

Research

partially

supported

by

the

NSF

under

a

CAREER

award

ANI-

9983221

and

grant

ACI-9873339

and

by

the

ARO

under

the

ODDR&E

MURI2001

Program

Grant

DAAD19-01-1-0465

to

the

Center

for

Networked

Communicating

Control

Systems.

I.

Ch.

Paschalidis

is

with

Center

for

Information

and

Systems

Engineer-

ing,

and

the

Department

of

Manufacturing

Engineering,

Boston

University,

15

St.

Mary’s

St.,

Brookline,

MA

02446,

e-mail:

[email protected],

url:

http://ionia.bu.edu/.

C.

Su

is

with

the

Department

of

Manufacturing

Engineering,

Boston

Univer-

sity,

e-mail:

[email protected].

M.

C.

Caramanis

is

with

the

Center

for

Information

and

Systems

Engineering,

and

the

Department

of

Manufacturing

Engineering,

Boston

University,

e-mail:

[email protected].

(e.g.,

CPU

of

server

1).

Jobs

to

be

processed

can

belong

to

mul-

tiple

types

differing

in

their

arrival

processes,

routes

through

the

network,

processing

times,

and

cost

per

unit

of

waiting

time.

The

objective

is

to

minimize

a

weighted

sum

of

mean

waiting

times.

We

should

note

that

although

our

main

motivation

is

to

optimize

the

operation

of

server

clusters,

the

model

we

consider

is

rather

general

and

applies

to

many

other

domains,

including,

manufacturing

systems,

multiprocessor

computer

systems,

and

communication

networks.

Performance

analysis

in

MQNETs

is

notoriously

hard.

Only

a

very

special

class

of

networks,

BCMP

and

Kelly

networks,

have

a

product

form

solution.

Naturally,

optimizing

an

MQNET

is

an

even

harder

problem.

A

version

of

the

scheduling

problem

we

consider

has

been

shown

to

be

EXP-complete

in

[3],

i.e.,

an

exponential-time

algorithm

is

required

to

obtain

an

optimal

policy.

Under

Markovian

assumptions

the

problem

can

be

for-

mulated

as

a

stochastic

dynamic

programming

(DP)

problem,

which

is

only

useful

in

solving

very

small

instances.

There

is,

by

now,

a

fair

amount

of

work

in

optimizing

MQNETs.

A

part

of

the

literature

has

focused

on

heavy-traffic,

Brownian,

approximations

to

derive

policies

in

special

cases,

see,

e.g.,

[4].

[1]

and

[5]

provide

a

polyhedral

approximation

of

the

region

of

achievable

performance

and

obtain

bounds

on

optimal

performance.

This

approximation

is

shown

to

be

exact

in

the

single-node

case

[6].

The

work

on

the

achievable

region

has

also

led

to

results

on

stability

[7].

Stability

is

an

impor-

tant

and

more

basic

question

than

optimization.

It

should

be

noted

that

in

open

MQNETs

the

usual

condition

of

node

uti-

lizations

to

be

less

than

one

is

not

sufficient

for

the

stability

of

all

policies.

[8]

proves

a

seminal

result

establishing

that

the

sta-

bility

of

a

fluid

model

is

a

sufficient

condition

for

the

stability

of

the

stochastic

open

MQNET.

Several

scheduling

policies

have

been

proposed

for

MQNETs,

including,

fluctuation

smoothing

policies

in

[9],

affine

shifts

of

policies

for

the

fluid

model

[10],

tracking

of

heavy-traffic-based

policies

[11],

and

tracking

opti-

mal

trajectories

of

the

fluid

model

[12].

We

propose

a

new

class

of

policies

that

“steer”

the

state

of

the

system

towards

a

pre-determined

and

fixed

“target”.

We

will

refer

to

these

policies

as

target-pursuing

.

They

are

motivated

by

the

efficiency

of

state

feedback

tracking

policies

in

control

and

the

work

in

[1].

As

a

first

indication

of

their

efficiency

we

show

that

they

are

stable.

To

that

end,

and

following

[8]

we

work

with

the

fluid

model.

The

selection

of

an

appropriate

target

significantly

affects

performance.

We

argue

that

the

work

in

[1]

can

lead

to

effective

and

easily

computable

targets.

As

we

will

see

the

proposed

policies

can

be

easily

implemented

in

a

decentralized

manner.

Scheduling

and

routing

decisions

are

made

at

the

individual

nodes

for

the

jobs

they

process

by