Prioritized Dominating-Set Broadcasting for Optimal Random Broadcasting

In random broadcasting or dynamic broadcast, source packets that have to be broadcast to all the other nodes are generated at each node of a network or a parallel/distributed system at random instances or in an uncoordinated manner. In this paper, we propose a priority-based routing scheme, to be referred to as prioritized dominating-set broadcasting (PDB), for random broadcasting in k-ary n-cubes. PDB can lead to a family of algorithms optimized for different switching techniques and communication models. It is also applicable to various other network topologies. Our goal is to minimize the average reception delay under heavy load, without compromising the maximum achievable throughput.