Performance Evaluation of Interval-Searching Conflict Resolution Algorithms
Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1985
A single multiaccess channel is studied with the outcome of a transmission being either 'idle'.'success'.or 'collision' (ternary channel).Packets involved in a collision must be retransmitted, and an efficient way to solve a collision is known in the literature as Gallager-Tsybakov-Mikhailov (G1M) algorithm.which falls into class of interval-searching contention resolution algorithms.Perfonnance analysis of the algorithm was based on a numerical solution of some recurrence equations and on a numerical evaluation of some series.The obvious drawback of such an analysis is lack of insight into the behaviour of the algorithm.We shall present a new approach of looking at the algorithm and discuss some attempts of analyzing its performance.In particular, expected lengths of a resolved interval and a conflict resolution interval as well as throughput of the algorithm will be discussed using asymptotic approximation and "a small input rate" approximation.Finally, we generalize these results to cover a wider class of interval-searching algorithms.