NeTS: Large: Collaborative Research: Foundations for Network Cooperation at Signal Scale
List of personnel
Principal Investigators:
 The Ohio State University (Ness Shroff)
 Rice University (Ashutosh Sabhrawal, Edward Knightly, Behnaam Aahzhang)
 Princeton University (Mung Chiang)
 Duke University (Rob Calderbank)
Vision
The overall goal of this project is to reevaluate our fundamental networking principles in order to obtain significant gains in wireless network performance. All current architectures (e.g., WiFi, cellular, mesh) are based on interference avoidance, which advocates eliminating simultaneous transmissions to avoid collisions at the receivers. However, this elegant principle is largely an artifact of design simpliﬁcation. In contrast, if neighboring nodes pool their resources, and cooperate in their signal transmissions, the network could turn interference to its advantage for potentially manyfold increase in network capacity. This cooperative viewpoint is what we have been studying as part of a twopronged strategy for success (1) Networkcentric Cooperative Signal Design; and (2) Signalcentric Cooperative Network Design.
Summary of Accomplishments

Addressed the longstanding open problem of developing simple distributed scheduling mechanisms that are provably efficient in the context of fading. It has been known that scheduling algorithms designed to achieve throughput optimality and good delay performance often require solving the Maximum Weighted Independent Set (MWIS) problem. However, under most realistic network settings, the MWIS problem is known to be NPhard. In nonfading environments, lowcomplexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster timescales than convergence occurs in these lowercomplexity algorithms. Hence, these algorithms cannot take advantage of opportunistic gains, and may no longer result in achieving good performance. In this work we develop a lowcomplexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size (provided that the conflict graph has bounded maximum vertex degree), and achieves provable performance guarantees (arbitrarily close to that of the wellknown centralized Greedy Maximal Scheduler). We verify that the throughput and the delay of our proposed scheme are close to those of the optimal MaxWeight that solves MWIS at each time. Further, we implement our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The experiment results show that our implementation successfully accounts for wireless fading, attains the shortterm opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.

We investigated the design of network resource allocation schemes when the channel information is uncertain or not even available. This is the case when CSI is very expensive to obtain, a scenario which is quite typical in wireless networks. Therefore, a critical question is how to optimally manage network resources in the absence of such information. To that end, we first studied the unicast case and developed a crosslayer solution for downlink cellular systems with imperfect (and possibly no) CSI at the transmitter. We use rateless codes to resolve channel uncertainty. To keep the decoding complexity low, we explicitly incorporate timeaverage blocksize constraints, and aim to maximize the system utility. By using a modified Lyapunov drift method, we develop a dynamic network control scheme, which yields a nearoptimal network utility. Via simulations, we show that our results improve network throughput above 60% over fixed rate codes, making a clear case for the intelligent use of rateless codes in wireless systems. Part of this work appeared in IEEE INFOCOM’13.
We then extended this work to include both unicast and multicast traffic, where the unicast CSI could be imperfect, but for multicast groups we assumed no CSI. Further, our focus was to design practical schemes that would eliminate the need for frequent ACKs, which have really been the main reason why multicast transmissions have not taken off (the ack explosion problem). Under this setting we are able to design efficient cross layer techniques, again using rateless codes at the physical layer, which show both theoretically and via simulations results, substantial improvements over stateoftheart techniques. In particular, we show that current solutions that use fixed rate physical layer codes are inefficient. This work was presented at IEEE INFOCOM’14.

In work by PI Sabharwal, a new precodingbased intersession network coding (NC) scheme has been proposed, which applies the interference alignment technique, originally devised for wireless interference channels, to the 3unicast problem of directed acyclic networks. Motivated by the graphtheoretic characterizations of classic linear NC results, we investigate several key relationships between the pointtopoint network channel gains and the underlying graph structure. Such relationships are critical when characterizing graph theoretically the feasibility of precodingbased solutions. One example of the applications of our results is to answer the conjectures of the 3unicast interference alignment technique in the work by Sabharwal et. al and the corresponding graphtheoretic characterization conditions. We have answered these questions posed by PI Sabhrawal. Parts of this work have appeared in Allerton and has been submitted for journal publication.

We have continued enhancing the line of investigation that shows how one can exploit multichannel capability that is afforded by the latest PHY layer technologies in order to develop scheduling mechanisms for wireless networks that have high throughput, low delay, and low complexity. This is work in collaboration with researchers at AT&T Bell Labs and Purdue University, and shows how the power of techniques from disparate disciplines (large deviation theory, complexity theory, approximation algorithms, and network control) can be harnessed to provide solutions that are both efficient and easy to implement. In particular, our solutions bring the complexity down from the current state of the art of O(n^5) to O(n^2.5 log n) for achieving true optimality, and down to O(n^2) for achieving nearoptimality, where n is a system parameter related to the number of channels and number of users. This work has been recently accepted in two papers in the IEEE/ACM Trans. on Networking. More recently, we have extended this work to exploit channel correlation inherent in wireless systems, and are still able to prove provably efficient theoretical bounds.

In a series of recent works, we have investigated the use of control mechanisms (scheduling, congestion control, and routing) that moves away from traditional combinatorial models, allowing transmissions to coexist under the more general SINR interference models. In this domain, we have developed provably efficient algorithms for a wide variety of physical layer scenarios, including MIMO systems. In these works we have both theoretical algorithms as well as actual implementations.

We show that if efficient coding techniques such as rateless and incremental redundancy codes, they can help reduce delays substantially. For example, it is now well known that if fixed rate codes are used or if packets are simply retransmitted when outages occur, this could result in heavy tailed transmission delays, which could also substantially reduce the practical throughput. However, in a recently accepted paper in the IEEE/ACM Trans. on Networking we show that when incremental redundancy coding is used, these delays are always guaranteed to be light tailed, thus making a case for using such codes in practical systems. Given the aforementioned benefits of rateless codes in terms of reducing ACKs delays, we ask another interesting question on whether and how one can achieve network capacity using such codes. In another recently accepted paper in the IEEE/ACM Trans. on Networking, we show that we characterize the throughput of a broadcast network with receivers using rateless codes as a function of the block size. We allow the channel to be correlated across time. We explicitly show how the throughput behaves for different values of the coding block size as a function of number of users in the broadcast or multicast group.
Publications
Journal
C. Joo and N. B. Shroff, "On the Delay Performance of Innetwork Aggregation in Lossy Wireless Sensor Networks," IEEE/ACM Trans. on Networking, vol. 22, no. 2, April. 2014, pp. 662  673.
C. Joo, X. Lin, J. Ryu, and N. B. Shroff, "Distributed Greedy Approximation to Maximum Weighted Independent Set for Scheduling with Fading Channels," IEEE/ACM Trans. on Networking (ToN), accepted for publication.
H. Cai, I. Koprulu, N. B. Shroff, "Exploiting Double Opportunities for LatencyConstrained Content Propagation in Wireless Networks," IEEE/ACM Trans. on Networking (ToN), accepted for publication.
J. Choi, C. Joo, J. Zhang, and N. B. Shroff, "Distributed Link Scheduling under SINR Model in Multihop Wireless Networks," IEEE/ACM Trans. on Networking, vol. 22, no. 4, Aug. 2014, pp. 1204 – 1217.
J. Liu, N. B. Shroff, C. Xia, and H. Sherali, "Joint Congestion Control and Routing Optimization: An Efﬁcient SecondOrder Distributed Approach," IEEE/ACM Trans. on Networking (ToN), accepted for publication.
W. Ouyang, A. Eryilmaz, and N. B. Shroff, "Asymptotically Optimal Downlink Scheduling over Markovian Fading Channels," IEEE/ACM Trans. on Networking (ToN), accepted for publication.
W. Ouyang, S. Murugesan, A. Eryilmaz, N. B. Shroff, "Exploiting Channel Memory for Joint Estimation and Scheduling in Downlink Networks  A Whittle's Indexability Analysis," IEEE Trans. on Information Theory, vol. 61, no. 4, Apr. 2015, pp. 17021719.
B. Ji, C. Joo and N. B. Shroff, “Delaybased Backpressure Scheduling in Multihop Wireless Networks,” IEEE/ACM Trans. on Networking, vol.21, no.5, Oct. 2013, pp.1539—1552.
C. Joo and N. B. Shroff, “On the Delay Performance of Innetwork Aggregation in Lossy Wireless Sensor Networks,” IEEE/ACM Trans. on Networking, vol. 22, no. 2, April. 2014, pp. 662  673.
D. Qian, D. Zheng, J. Zhang, N. B. Shroff, and C. Joo, “Distributed CSMA Algorithms for Link Scheduling in Multihop MIMO Networks under SINR Model,” IEEE/ACM Trans. on Networking, vol. 21, no. 3, pp. 746759, June, 2013.
J. Liu, N. B. Shroff, and H. D. Sherali, “On Optimal Power Allocation for MIMO Cooperative Networks with Multiple Relays,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 30, Issue 2, Feb. 2012.
J. Tan, B.T. Swapna and N. B. Shroff, “Retransmission Delays with Bounded Packets: Power law body and Exponential tail,” IEEE/ACM Trans. on Networking, vol. 22, no. 1, Feb. 2014, pp. 2738.
S. Hariharan and N. B. Shroff, “On SamplePath Optimal Dynamic Scheduling for SumQueue Minimization in Forests,” IEEE/ACM Trans. on Networking, vol. 22, no. 1, Feb. 2014, pp. 151164.
S. Li, Z. Zheng, E. Ekici, and N. B. Shroff, “Maximizing System Throughput by Cooperative Sensing in Cognitive Radio Networks,” IEEE/ACM Trans. on Networking, vol. 22, no. 4, Aug. 2014, pp. 12451256.
S. Murugesan, P. Schniter, and N. B. Shroff, “Multiuser Scheduling in a Markovmodeled Downlink using Randomly Delayed ARQ Feedback,” IEEE Trans. on Information Theory, vol. 58, Issue 2, pp. 1025  1042, 2012.
X. Zhang, Y. Sun, X. Chen, S. Zhou, J. Wang and N. B. Shroff, “Distributed Power Allocation for Coordinated Multipoint Transmissions in Distributed Antenna Systems,” IEEE Trans. on Wireless Communications, Vol. 12, Issue 5, pp. 2281 2291, May. 2013.
Y. Yang and N. B. Shroff, ”Throughput of Rateless Codes over Broadcast Erasure Channels,” IEEE/ACM Trans. on Networking, vol. 23, no. 1, Feb. 2015, pp. 126137.
Y. Yang, J. Tan, N. B. Shroff and H. El Gamal, ”Delay Asymptotics with Retransmissions and Incremental Redundancy Codes over Erasure Channels,” IEEE Trans. on Information Theory, vol. 60, no. 3, Mar. 2014, pp. 1932  1944.
Conference
Y. Kim, K. Lee, and N. B. Shroff, "An Analytical Framework to Characterize the Efficiency and Delay in a Mobile Data Offloading System," ACM Mobihoc'14, Philadelphia, PA, Aug. 2014.
Y. Sun, C. E. Koksal, K. Kim, and N. B. Shroff, "Scheduling of Multicast and Unicast Services under Limited Feedback by using Rateless Codes," IEEE INFOCOM'14, Toronto, Canada, Apr. 2014.
J. Han, N. B. Shroff and C.C. Wang, “Analysis of Precodingbased Intersession Network Coding and The Corresponding 3Unicast Interference Alignment Scheme,” in Proceedings of 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, September 2830, 2011.
J. Liu, C. H. Xia, N. B. Shroff and H. D. Sherali, “Distributed CrossLayer Optimization in Wireless Networks: A SecondOrder Approach,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013 (Runnerup paper, 1 best paper and 2 runnerup papers selected out of 1600+ submitted papers).
C. Joo, X. Lin, J. Ryu, and N. B. Shroff, “Distributed Greedy Approximation to Maximum Weighted Independent Set for Scheduling with Fading Channels,” ACM Mobihoc'13, Bangalore, India, July 2013.
B. Ji, C. Joo and N. B. Shroff, “Exploring the Inefficiency and Instability of BackPressure Algorithms,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.
S. Chen, T. Bansal, Y. Sun, P. Sinha, and N. B. Shroff, “LifeAdd: Lifetime Adjustable Design for WiFi Networks with Heterogeneous Energy Supplies,” IEEE WiOPT'13, Tsukuba Science City, Japan, May 2013 (Best Student Paper Award).
W. Ouyang, A. Eryilmaz, N. B. Shroff, “Lowcomplexity Optimal Scheduling Over Correlated Fading Channels with ARQ Feedback,” IEEE 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT’12), Paderborn, Germany, May 2012.
S. Li, Z. Zheng, E. Ekici and N. B. Shroff, “Maximizing Social Welfare in Operatorbased Cognitive Radio Networks under Spectrum Uncertainty and Sensing Inaccuracy,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.
Y. Sun, C. E. Koksal, S. Lee and N. B. Shroff, “Network Control without CSI using Rateless Codes for Downlink Cellular Systems,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.
B. Ji, G. R. Gupta, X. Lin and N. B. Shroff, “Performance of LowComplexity Greedy Scheduling Policies in MultiChannel Wireless Networks: Optimal Throughput and NearOptimal Delay,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.
Y. Kim, K. Lee, N. B. Shroff and I. Rhee, “Providing Probabilistic Guarantees on the Time of Information Spread in Opportunistic Networks,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.
Y. Sun, C. E. Koksal, K. Kim, and N. B. Shroff, “Scheduling of Multicast and Unicast Services under Limited Feedback by using Rateless Codes,” in Proceedings of the IEEE INFOCOM’14, Toronto, Canada, April 2014.
Y. Yang and N. B. Shroff, “Throughput of Rateless Codes over Broadcast Erasure Channels,” ACM Mobihoc 2012, Hilton Head Island, South Carolina, June 2012.
Ohio State Engineering:
Excellence • Impact • Innovation