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 re-evaluate our fundamental networking principles in order to obtain significant gains in wireless network performance. All current architectures (e.g., Wi-Fi, 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 simplification. In contrast, if neighboring nodes pool their resources, and cooperate in their signal transmissions, the network could turn interference to its advantage for potentially many-fold increase in network capacity. This cooperative viewpoint is what we have been studying as part of a two-pronged strategy for success (1) Network-centric Cooperative Signal Design; and (2) Signal-centric Cooperative Network Design.

Summary of Accomplishments

  1. Addressed the long-standing 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 NP-hard. In nonfading environments, low-complexity 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 time-scales than convergence occurs in these lower-complexity 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 low-complexity 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 well-known 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 short-term opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.

  2. 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 cross-­layer 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 time-­average block-­size 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 near-­optimal 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 state-of-the-art 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.

  3. In work by PI Sabharwal, a new precoding-based intersession network coding (NC) scheme has been proposed, which applies the interference alignment technique, originally devised for wireless interference channels, to the 3-unicast problem of directed acyclic networks. Motivated by the graph-theoretic characterizations of classic linear NC results, we investigate several key relationships between the point-to-point network channel gains and the underlying graph structure. Such relationships are critical when characterizing graph- theoretically the feasibility of precoding-based solutions. One example of the applications of our results is to answer the conjectures of the 3-unicast interference alignment technique in the work by Sabharwal et. al and the corresponding graph-theoretic 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.

  4. We have continued enhancing the line of investigation that shows how one can exploit multi-channel 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 near-optimality, 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.

  5. 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.

  6. 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

  1. C. Joo and N. B. Shroff, "On the Delay Performance of In-network Aggregation in Lossy Wireless Sensor Networks," IEEE/ACM Trans. on Networking, vol. 22, no. 2, April. 2014, pp. 662 - 673.

  2. 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.

  3. H. Cai, I. Koprulu, N. B. Shroff, "Exploiting Double Opportunities for Latency-Constrained Content Propagation in Wireless Networks," IEEE/ACM Trans. on Networking (ToN), accepted for publication.

  4. J. Choi, C. Joo, J. Zhang, and N. B. Shroff, "Distributed Link Scheduling under SINR Model in Multi-hop Wireless Networks," IEEE/ACM Trans. on Networking, vol. 22, no. 4, Aug. 2014, pp. 1204 – 1217.

  5. J. Liu, N. B. Shroff, C. Xia, and H. Sherali, "Joint Congestion Control and Routing Optimization: An Efficient Second-Order Distributed Approach," IEEE/ACM Trans. on Networking (ToN), accepted for publication.

  6. 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.

  7. 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. 1702-1719.

  8. B. Ji, C. Joo and N. B. Shroff, “Delay-based Back-pressure Scheduling in Multi-hop Wireless Networks,” IEEE/ACM Trans. on Networking, vol.21, no.5, Oct. 2013, pp.1539—1552.

  9. C. Joo and N. B. Shroff, “On the Delay Performance of In-network Aggregation in Lossy Wireless Sensor Networks,” IEEE/ACM Trans. on Networking, vol. 22, no. 2, April. 2014, pp. 662 - 673.

  10. D. Qian, D. Zheng, J. Zhang, N. B. Shroff, and C. Joo, “Distributed CSMA Algorithms for Link Scheduling in Multi-hop MIMO Networks under SINR Model,” IEEE/ACM Trans. on Networking, vol. 21, no. 3, pp. 746-759, June, 2013.

  11. 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.

  12. 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. 27-38.

  13. S. Hariharan and N. B. Shroff, “On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests,” IEEE/ACM Trans. on Networking, vol. 22, no. 1, Feb. 2014, pp. 151-164.

  14. 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. 1245-1256.

  15. S. Murugesan, P. Schniter, and N. B. Shroff, “Multiuser Scheduling in a Markov-modeled Downlink using Randomly Delayed ARQ Feedback,” IEEE Trans. on Information Theory, vol. 58, Issue 2, pp. 1025 - 1042, 2012.

  16. 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.

  17. 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. 126-137.

  18. 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

  1. 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.

  2. 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.

  3. J. Han, N. B. Shroff and C.-C. Wang, “Analysis of Precoding-based Intersession Network Coding and The Corresponding 3-Unicast Interference Alignment Scheme,” in Proceedings of 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, September 28-30, 2011.

  4. J. Liu, C. H. Xia, N. B. Shroff and H. D. Sherali, “Distributed Cross-Layer Optimization in Wireless Networks: A Second-Order Approach,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013 (Runner-up paper, 1 best paper and 2 runner-up papers selected out of 1600+ submitted papers).

  5. 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.

  6. B. Ji, C. Joo and N. B. Shroff, “Exploring the Inefficiency and Instability of Back-Pressure Algorithms,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.

  7. S. Chen, T. Bansal, Y. Sun, P. Sinha, and N. B. Shroff, “Life-Add: Lifetime Adjustable Design for WiFi Networks with Heterogeneous Energy Supplies,” IEEE WiOPT'13, Tsukuba Science City, Japan, May 2013 (Best Student Paper Award).

  8. W. Ouyang, A. Eryilmaz, N. B. Shroff, “Low-complexity 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.

  9. S. Li, Z. Zheng, E. Ekici and N. B. Shroff, “Maximizing Social Welfare in Operator-based Cognitive Radio Networks under Spectrum Uncertainty and Sensing Inaccuracy,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.

  10. 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.

  11. B. Ji, G. R. Gupta, X. Lin and N. B. Shroff, “Performance of Low-Complexity Greedy Scheduling Policies in Multi-Channel Wireless Networks: Optimal Throughput and Near-Optimal Delay,” IEEE INFOCOM’13, Turin, Italy, Apr. 2013.

  12. 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.

  13. 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.

  14. 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

Ohio State University logo The Ohio State University | Dreese Laboratories 2015 Neil Ave, Room 205 | Columbus, Ohio 43210