
Computation of the Packet Delay in Massey's Standard and Modified
Tree Conflict Resolution Algorithms with Gated Access
Mart L. Molle and Alvin C. Shih
Computer Systems Research Institute
University of Toronto
Toronto, Ontario M5S 1A1
Recently, Polyzos derived methods for calculating conflict resolution
interval lengths when the number of contenders in the initial set is
Poisson distributed with a given mean. From these formulae, Polyzos
computed the mean and standard deviation of the packet delay under
window access. In this report, we show how to extend his methods to
handle gated access.
1. Overview
The goal in this study is to find the mean and standard deviation of the packet delay in Massey's
Standard and Modified Tree Algorithms [2], which we denote by the STA and the MTA respectively.
These algorithms use gated access to select packets for transmission in a given conflict resolution interval
(CRI), and thereafter use a recursive binary preorder tree traversal algorithm (optionally including the
levelskipping modification) to resolve the resulting conflicts, if any.
The approach is to examine the delay from the point of view of a randomly chosen "tagged" packet.
Under gated access, the delay for the "tagged" packet can be partitioned into the following two com
ponents:
t the residualiiiiiii lifeiii of the CRI that is ongoing at the moment of arrival. This covers the time until the
"gate" opens, admitting the "tagged" packet (and possibly some others) into the conflict resolution
process.
t 2 the ageiii of the next CRI at the moment where the tagged packet leaves the system at the end of its
successful transmission. This covers the rest of the time from the first transmission of the "tagged"
packet until it is successful.
The notation t and t 2 to describe these two delay components is chosen for compatibility with
Polyzos[1]. However, our work differs substantially from that of Polyzos, because t and t 2 depend on the
solution to an embedded Markov chain, describing the sequence of CRI lengths in the execution of the pro
tocol. This is quite different from Polyzos' study, where t and t 2 are i.i.d. and the most important part of
the delay is the lag of the window, t 1, which does not appear in gated access.
Our approach is as follows: first, we solve the Markov chain to obtain the distribution of CRI lengths
in steady state, represented by:
pfi = (p1, p2, p3, . . . )
where pn is the probability that a randomly chosen CRI will be n slots long. Next, we use the fact that we
have Poisson packet arrivals to apply standard renewaltheoretic results to obtain p? n, the probability that
our "tagged" arrival joins the system during a CRI of length n:
p? n = Sk kpk
npn
hhhhhhh = Nhh
npn
hhhh (1)
Intuitively, we must weight CRI's of length n in proportion to the product of their relative length and rela
tive frequency of occurrence, since Poisson arrivals take a random look at the time axis. So, p? n is the pro
bability that a random packet arrives during a CRI of length n.
If we condition on the event that our "tagged" packet arrives during a CRI of length n, then t has a
uniform distribution over the interval [0,n), and the distribution of t 2 should be conditioned on the fact that
the "tagged" packet will be competing with a group of other packets having a Poisson distribution with
mean l . n. Thus, assuming we use random addressing (i.e., splitting via random "coin tosses" rather than