Delay analysis of tree conflict resolution algorithm with and without broadcast reservation using random or pseudo random addressing

Abstract

An analysis is made of the performance of tree conflict resolution algorithms. A system with a finite number of users is considered, and each user provides buffers to store backlogged packets. In particular, the delay and system capacity of Capetanakis's original tree protocol and the broadcast reservation (BR) protocol using both random and pseudo random addressing are studied. Due to the nature of random access, the maximum throughput is low (only 0.348 for the original tree protocol). To improve it, the BR protocol combines the original tree protocol with the idea of demand assignment and yields very good delay-throughput. For the tree protocols, the random addressing scheme is fair but less efficient than deterministic addressing. To have fair and efficient addressing, an addressing scheme called pseudo random addressing is studied It is as efficient as deterministic addressing and yet as fair as random addressing.