Speaker
Nasser Barjesteh
Title
Duality relations in finite queueing models
Abstract
Motivated
by
applications
in
multimedia
streaming
and
in
energy
systems,
we
study
duality
relations
in
finite
queues.
Dual
of
a
queue
is
defined
to
be
a
queue
in
which
the
arrival
and
service
processes
are
interchanged.
In
other
words,
dual
of
the
G¬1/G2/1/K
queue
is
the
G2/G1/1/K
queue,
a
queue
in
which
the
inter-arrival
times
have
the
same
distribution
as
the
service
times
of
the
primal
queue
and
vice
versa.
Similarly,
dual
of
a
fluid
flow
queue
with
cumulative
input
C(t)
and
available
processing
S(t)
is
a
fluid
queue
with
cumulative
input
S(t)
and
available
processing
C(t).
We
are
primarily
interested
in
finding
relations
between
the
overflow
and
underflow
of
the
primal
and
dual
queues.
Then,
using
existing
results
in
the
literature
regarding
the
probability
of
loss
and
the
stationary
probability
of
queue
being
full,
we
can
obtain
estimates
on
the
probability
of
starvation
and
the
probability
of
the
queue
being
empty.
The
probability
of
starvation
corresponds
to
the
probability
that
a
queue
becomes
empty,
i.e.,
the
end
of
a
busy
period.
We
study
the
relations
between
arrival
and
departure
Palm
distributions
and
their
relations
to
stationary
distributions.
We
consider
both
the
case
of
point
process
inputs
as
well
as
fluid
inputs.
We
obtain
inequalities
between
the
probability
of
the
queue
being
empty
and
the
probability
of
the
queue
being
full
for
both
the
time
stationary
and
Palm
distributions
by
interchanging
arrival
and
service
processes.
In
the
fluid
queue
case,
we
show
that
there
is
an
equality
between
arrival
and
departure
distributions
that
leads
to
an
equality
between
the
probability
of
starvation
in
the
primal
queue
and
the
probability
of
overflow
in
the
dual
queue.
The
techniques
are
based
on
monotonicity
arguments
and
coupling.
The
usefulness
of
the
bounds
is
illustrated
via
numerical
results.
Supervisor
Professor Catherine Rosenberg