Why:
Sophisticated scheduling algorithms have been developed in the networking theory community for many years, yet most of them require communication overhead through message passing. Recent works show the promising potential of CSMA, without any message passing, for achieving utility optimality. Can these simple algorithms be actually deployed?
What:
The proliferation of wireless devices, systems, and services in the past decade has been truly remarkable. Given that all these wireless networks transmit signals in the air, interference management has become ever more important. Similar to a cocktail party where people's conversations interfere with one another, two common degrees of freedom to control interference in wireless networks are: "when to talk" and "how loud to talk", i.e., scheduling and power control, respectively. Power control research can be found under Network Optimization page. On wireless scheduling, we develop a unifying framework that puts each of the existing scheduling algorithms as a point in a 3-dimensional tradeoff space with axes as throughput, delay, and complexity. This explains prior counter-intuitive results in the area, like maintaining the same throughput while reducing time-complexity of the scheduling algorithm, by showing that an exponential price on delay may need to be paid. It also offers a unified way to compare the variety of scheduling algorithms available to network designers. A natural question then becomes: can very simple algorithms be designed to approach optimality of throughput without any message passing among users? In 2008, theoretical developments suggest that utility-optimal, message-passing-free scheduling protocols can run on adaptive CSMA, optimal in the sense that the best network utility can be approached arbitrarily tightly. The mathematical proof contains an innovative approach to approximate hard combinatorial problems. In collaboration with KAIST and Rice University, we implement the algorithm in WiFi hardware. We demonstrat where the theoretical predictions were valid, thus ready for technology transfer, and where they are not due to the ideal assumptions taken, thus identifying the gaps between theory and systems.
Who:
Collaboration with Yung Yi and Song Chong at KAIST and Ed Knightly at Rice.
Selected Publications:
B. Nardelli, J. Lee, K. Lee, Y. Yi, S. Chong, E. Knightly, and M. Chiang, 'Experimental evaluation of optimal CSMA', Proceedings of IEEE INFOCOM, 2011.
J. Lee, J. Lee, Y. Yi, S. Chong, A. Proutiere, and M. Chiang, 'Implementing utility optimal CSMA', Proceedings of Allerton Conference, September 2009
J. Liu, Y. Yi, A. Proutiere, M. Chiang, and H. V. Poor, 'Towards utility optimal random access without message passing', (Invited Paper) Wiley Journal on Wireless Communications and Mobile Computing, Special Issue on Advances in Wireless Communications and Networking, December 2009.
Y. Yi, A. Proutiere, and M. Chiang, 'Complexity-stability-delay tradeoff in scheduling over wireless networks', Proc. ACM MobiHoc, May 2008.
Y. Yi, J. Zhang, and M. Chiang, 'Delay and effective throughput of wireless scheduling in heavy traffic regmines: Vacation model for complexity', Proc. ACM MobiHoc, May 2009.
A. H. Mohsenian-Rad, J. Huang, M. Chiang and V. W. S. Wong, 'Utility-optimal random access: Reduced complexity, fast convergence, and robust performance', IEEE Transactions on Wireless Communications, vol. 8, no. 2, pp. 898-911, February 2009.
