DIMACS TR: 96-36
Processor-Ring Communication:
A Tight Asymptotic Bound on Packet Waiting Times
Authors: E. G. Coffman, Jr., Nabil Kahale and F. T. Leighton
ABSTRACT
We consider $N$ processors communicating unidirectionally over a closed
transmission channel, or ring. Each message is assembled into a fixed-
length packet. Packets to be sent are generated at random times by the
processors, and the transit times spent by packets on the ring are also
random. Packets being forwarded, i.e., packets already on the ring, have
priority over waiting packets. The objective of this paper is to analyze
packet waiting times under a greedy policy, within a discrete Markov
model that retains the over-all structure of a practical system, but is
simple enough so that explicit results can be proved. Independent,
identical Bernoulli processes model message generation at the processors,
and i.i.d. geometric random variables model the transit times. Our
emphasis is on asymptotic behavior for large ring sizes, $N$, when
the respective rate parameters have the scaling $\la /N$ and $\mu /N$.
Our main result shows that, if the traffic intensity is fixed at $\rho
= \la / \mu < 1$, then as $N \to \infty$ the expected time a message
waits to be put on the ring is bounded by a constant. This result
verifies that the expected waiting time under the greedy policy is within
a constant factor of that under an optimal policy.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-36.ps.gz
DIMACS Home Page