One of the fundamental problems in Computer Networking is to efficiently transport packets belonging to different sessions, such as unicast, broadcast, multicast and anycast, collectively known as the generalized flows. The problem is to design an efficient routing, and wireless link scheduling policy, which achieves the entire capacity region. Currently, a throughput-optimal algorithm (Backpressure) is known only for the unicast problem and little progress has been made towards a universal algorithm addressing the generalized flow problem. In this thesis, we propose provably optimal algorithms for the broadcast and the generalized flow problems.
We begin our study with the problem of optimal broadcasting in a wireless Directed Acyclic Graph (DAG). Existing policies achieve the broadcast capacity by balancing traffic over a set of spanning trees, which are difficult to maintain in a large and time-varying network. We propose a fundamentally new broadcast policy, which is decentralized, utilizes local queue-length information only, does not require the use of global topological structures, such as spanning trees and offers the useful feature of in-order delivery of packets. It also yields a new characterization of broadcast capacity in wireless DAGs, which further leads to an efficient algorithm for computing the capacity under the primary interference constraints. The algorithm extends gracefully to time-varying wireless networks. We next study the problem of broadcasting in networks with arbitrary topology and derive a new dynamic broadcast policy which can be viewed as “Backpressure on sets”. This yields an efficient solution to the problem when combined with a multi-class in-order packet scheduling rule.
Finally, we study the generalized flow problem and derive an online dynamic policy, called Universal Max-Weight (UMW), which yields an efficient solution. To the best of our knowledge, UMW is the first throughput-optimal algorithm of such versatility in this context. Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing, and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and link scheduling policy. This is in contrast with the Backpressure policy which allows for packet cycling, resulting in excessive delay. The proposed algorithmic paradigm is surprisingly general and yields solutions to other related problems, such as optimal broadcasting with point-to-multipoint links. The proof of throughput-optimality of the UMW policy combines techniques from stochastic Lyapunov theory with a sample path argument from adversarial queueing theory and may be of independent theoretical interest.
