page 2  (23 pages)
to previous section1
3to next section

- 2 -

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

level-skipping 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-


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


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 renewal-theoretic results to obtain p? n, the probability that

our "tagged" arrival joins the system during a CRI of length n:

p? n = Sk kpk

hhhhhhh = Nhh
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