A Migration Approach to Optimal Control of Wireless Networks

(NSF Grant CNS-1524317)

PI: Eytan Modiano

Recent growth in mobile and media-rich applications has greatly increased the demand for wireless capacity, straining wireless networks. This dramatic increase in demand poses a challenge for current wireless networks, and calls for new algorithms that make better use of scarce wireless resources.  Recently developed algorithms for optimally managing wireless resources hold the promise of significant performance improvement, but require all of the nodes in the network to be upgraded with new functionality – which is both costly and impractical.  This project introduces a novel architectural paradigm for wireless networks, whereby optimal algorithms are designed to operate in networks with both new and legacy nodes.  This new paradigm allows optimal algorithms to be incrementally deployed alongside existing schemes, thus providing a migration path for new control algorithms, and the promise of dramatic improvement in network performance at incremental cost.

This project develops a novel overlay architecture for implementing optimal network control algorithms over legacy networks. New nodes, capable of implementing sophisticated network control algorithms, will be connected in a virtual network overlay that operates on top of the legacy network.  The research will answer fundamental questions about which nodes must be upgraded with new functionality and the tradeoff between the number of new upgraded nodes and network performance.  The project will develop new routing algorithms that send packets from their sources to their destinations in the overlay network, and transmission scheduling algorithms for mitigating the effect of wireless interference. These new algorithms will be designed to operate efficiently in a network with a mix of new and legacy nodes, by taking interoperability into account.  Thus, this project will answer fundamental questions about the introduction of new control techniques into legacy networks, and provide a promising approach to bridging the gap between new techniques developed for universal deployment and the reality of the networks in operation today.

Our research goals include:

  • development of an overlay architecture for implementing optimal network control algorithms over a legacy network, using a limited number of overlay nodes.
  • development ofnew routing and flow control algorithms that operate over the overlay network.
  • development of optimal scheduling algorithms for a wireless network with a mix of controllable and uncontrollable nodes.
  • validation of our algorithms using a combination of simulation, emulation, and testbed implementation. 

 

Participants:
Prof. Eytan Modiano, PI
Thomas Stahlbuhk, graduate student
Abhishek Sinha, graduate student

 

SIgnificant Results:

In [1] we developed an Overlay Architecture for Throughput Optimal Multipath Routing.  Legacy networks are often designed to operate with simple single-path routing, like shortest-path, which is known to be throughput suboptimal. On the other hand, previously proposed throughput optimal policies (i.e., backpressure) require every device in the network to make dynamic routing decisions.  We developed an overlay architecture for dynamic routing such that only a subset of devices (overlay nodes) need to make dynamic routing decisions. We determine the essential collection of nodes that must bifurcate traffic for achieving the maximum multicommodity network throughput. We apply our optimal node placement algorithm to several graphs and the results show that a small fraction of overlay nodes is sufficient for achieving maximum throughput.  In [2] we address the problem of optimal routing in overlay networks. We develop a throughput optimal dynamic routing algorithm for such overlay networks called the Optimal Overlay Routing Policy (OORP).  OORP is derived using the classical dual subgradient descent method, and it can be implemented in a distributed manner. We show that the underlay queue-lengths can be used as a substitute for the dual variables. We also propose various schemes to gather the information about the underlay that is required by OORP and compare their performance via extensive simulations.

In [3] we consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast and anycast traffic in general wireless networks. We propose an online dynamic policy, called Universal Max-Weight (UMW), which solves the above problem efficiently. To the best of our knowledge, UMW is the first throughput-optimal algorithm of such versatility in the context of generalized network flow problems. 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 to the well-known throughput-optimal Back- Pressure (BP) policy which allows for packet cycling, resulting in excessive delay. Extensive simulation results show that the proposed policy incurs a substantially lower delay as compared to the BP policy. 

In [4]  We consider a wireless system consisting of both legacy (uncontrollable) and new (controllable) nodes.   The Legacy network is uncooperative and its users transmit on their channels whenever their buffers are nonempty. The new (controllable) nodes cannot directly observe the legacy network’s transmissions and must rely upon receiver feedback to avoid collisions. Our objective is to devise scheduling policies for the controllable network, so that its users may opportunistically transmit over the channels without degrading the legacy network’s throughput. To this end, we first analyze a network consisting of a single legacy and single new user communicating over one shared channel. We characterize the achievable throughput of the new user by formulating the problem as a partially observable Markov decision process and derive upper and lower bounds on the maximum performance. We then use these results to characterize the capacity region of larger networks. We formulate a queue length-based scheduling policy, Longest Queue First, that adaptively allocates channel resources to the secondary users and relate its performance to the capacity region.

 

Related Publications:

[1] Nathaniel M. Jones, Georgios S. Paschos, Brooke Shrader, and Eytan Modiano, "An Overlay Architecture for Throughput Optimal Multipath Routing,"  IEEE/ACM Transactions on Networking, 2017, to appear.

[2] Anurag Rai, Rahul Singh, Eytan Modiano, "A Distributed Algorithm for Throughput Optimal Routing in Overlay Networks,"  IEEE/ACM Transactions on Networking, submitted, 2017.

[3] Abhishek Sinha and Eytan Modiano, "Optimal Control for Generalized Network-Flow Problems,"  IEEE Infocom, 2017.

[4] Thomas Stahlbuhk, Brooke Shrader, Eytan Modiano, “Throughput Maximization in Uncooperative Spectrum sharing networks,”  IEEE International Symposium on Information Theory,  2016.