Throughput-optimal multi-hop broadcast algorithms
Author(s)
Paschos, Georgios; Sinha, Abhishek; Modiano, Eytan H
DownloadModiano_Throughput-optimal multi.pdf (658.0Kb)
OPEN_ACCESS_POLICY
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
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.
Date issued
2016-07Department
Massachusetts Institute of Technology. Department of Aeronautics and Astronautics; Massachusetts Institute of Technology. Laboratory for Information and Decision SystemsJournal
Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing - MobiHoc '16
Publisher
Association for Computing Machinery (ACM)
Citation
Sinha, Abhishek, Georgios Paschos, and Eytan Modiano. “Throughput-Optimal Multi-Hop Broadcast Algorithms.” 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 5-8 July, 2016, Paderborn, Germany, ACM Press, 2016. 51–60.
Version: Original manuscript
ISSN
978-1-4503-4184-4