Efficient algorithms for performing packet broadcasts in a mesh network
- 1 January 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 4 (4) , 639-648
- https://doi.org/10.1109/90.532872
Abstract
We consider proeewors communicating over a mesh network with the objective of broadcasting information among each other. One instance of the problem involves a number of nodes all with the same message to be broadcasted. For that problem, a lower-bound on the time to complete the broadcast, and an algorithm whlcb achieves this bound are presented. In another instance, every node in the mesh has packets to be broadcast arriving independently, according to a Poisson random proeeas. The stability region for performing such broadcasts is characterized, and broadcast algorithms which operate efficiently withbs that region are presented. These algorithms involve inter- acting queues whose analysis is known to he very difficult. Toward that end we develop an approximation which models an n- dimensional intinite Markov chain as a single-dimensional infinite Markov chain together with an u-dimensional finite Markov chain. This approximate madel ean he analyzed and the results compare favorably with simulation.Keywords
This publication has 5 references indexed in Scilit:
- A method for delay analysis of interacting queues in multiple access systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Steady-state behavior of interacting queues-a numerical approachIEEE Transactions on Information Theory, 1990
- Efficient routing schemes for multiple broadcasts in hypercubesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- Delay Analysis of Interacting Queues with an Approximate ModelIEEE Transactions on Communications, 1987
- Analysis, stability, and optimization of slotted ALOHA with a finite number of buffered usersIEEE Transactions on Automatic Control, 1981