Throughput-optimal multi-hop broadcast algorithms

ABSTRACT

In this paper we design throughput-optimal dynamic broadcast algorithms for multi-hop networks with arbitrary topologies. Most of the previous broadcast algorithms route packets along spanning trees, rooted at the source node. For large time-varying networks, computing and maintaining a set of spanning trees is not efficient, as the network-topology may change frequently. In this paper we design a class of dynamic algorithms which make packet-by-packet scheduling and routing decisions and hence, obviate the need for maintaining any global topological structures, such as spanning trees. Our algorithms may be conveniently understood as a non-trivial generalization of the familiar back-pressure algorithm, which makes unicast packet routing and scheduling decisions, based on local queue-length information and does not require to maintain end-to-end paths. However, in the broadcast setting, due to packet duplications, it is hard to define appropriate queuing structures. We design and prove the optimality of a virtual-queue based algorithm, where virtual-queues are defined for subsets of nodes. We then propose a multi-class broadcast policy which combines the above scheduling algorithm with in-class-in-order packet forwarding, resulting in significant reduction in complexity. Finally, we evaluate performance of the proposed algorithms via extensive numerical simulations.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009.
2. R. Durrett. Probability: theory and examples. Cambridge university press, 2010.
3. D. V. Lindley. The theory of queues with a single server. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 48, pages 277--289. Cambridge Univ Press, 1952.
4. L. Massoulie, A. Twigg, C. Gkantsidis, and P. Rodriguez. Randomized decentralized broadcasting algorithms. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 1073--1081. IEEE, 2007.
5. M. J. Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):1--211, 2010.
6. R. Rustin. Combinatorial Algorithms. Algorithmics Press, 1973.
7. S. Sarkar and L. Tassiulas. A framework for routing and congestion control for multicast information flows. Information Theory, IEEE Transactions on, 48(10):2690--2708, 2002.
8. A. Sinha, G. Paschos, and E. Modiano. Tech report {online}: Throughput-optimal multi-hop broadcast algorithms. http://arxiv.org/abs/1604.00446
9. A. Sinha, G. Paschos, C. ping Li, and E. Modiano. Throughput-optimal broadcast on directed acyclic graphs. In Computer Communications (INFOCOM), 2015 IEEE Conference on, pages 1248--1256, April 2015.
10. L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Automatic Control, IEEE Transactions on, 37(12):1936--1948, 1992.
11. D. Towsley and A. Twigg. Rate-optimal decentralized broadcasting: the wireless case, 2008.
12. D. B. West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
13. E. Wong and B. Hajek. Stochastic processes in engineering systems. Springer Science & Business Media, 2012.
14. S. Zhang, M. Chen, Z. Li, and L. Huang. Optimal distributed broadcasting with per-neighbor queues in acyclic overlay networks with arbitrary underlay capacity constraints. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 814--818. IEEE, 2013.

Index Terms

• Networks

  • Network algorithms

    • Control path algorithms

      • Network control algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms