Title :
Conflict multiplicity estimation and batch resolution algorithms
Author :
Cidon, Israel ; Sidi, Moshe
Author_Institution :
IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA
fDate :
1/1/1988 12:00:00 AM
Abstract :
The standard model of a multiple-access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. An algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch-resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete-resolution and partial-resolution algorithms are presented
Keywords :
multi-access systems; packet switching; telecommunication channels; batch resolution algorithms; complete resolution algorithms; conflict multiplicity estimation; multiple-access channel; packet transmission; partial-resolution algorithms; ternary feedback; tree algorithms; Algorithm design and analysis; Distributed algorithms; Feedback; Time measurement; Tree graphs;
Journal_Title :
Information Theory, IEEE Transactions on