Performance Analysis of Finite Nonhomogeneous Population Tree Conflict Resolution Algorithms Using Constant Size Window Access

Multiple-access protocols control access to a broadcast communication channel. Tree conflict resolution algorithms are the heart of some distributed multiple-access protocols with nice properties like stability, high capacity, and low delay under light load. We consider a random access protocol based on a tree conflict resolution algorithm similar to one first proposed by Capetanakis, but in which constant size windows on the arrival time axis are used to admit packets into the algorithm instead of the more common "free" or "blocked" access methods. We obtain exact recursive relationships for the (steady-state) distribution of packet delay, and thus, the exact throughput-delay curve for any finite (in general, nonhomogeneous) configuration under a Bernoulli-per-window arrival model. Then, we consider the address assignment problem. We show that by choosing an appropriate addressing scheme, we can improve the performance of the algorithm with respect to both mean delay and maximum throughput.