Columbia University Joint CS/EE Networking Seminar Series

Automated Design of MAC Protocols

Professor Volkan Rodoplu

University of California, Santa Barbara

Oct. 26, 3:00PM CS Conference Room

Abstract: We establish a framework for the automated generation of Medium Access Control (MAC) Protocols for wireless networks. The need for rapid design of networking protocols in application-specific contexts has increased dramatically over recent years. Each new application requires high performance in its own domain as well as a rapid design cycle. Furthermore, changes in physical layer technology quickly render previously high-performance protocols obsolete. Currently, there are no tools to automate the design of networking protocols. We propose a methodology and a design chain for the automated generation of MAC protocols.

The two key problems we solve are: (1) The incorporation of the impact of control packet information into MAC protocol optimization, which is an important advance over extant approaches to protocol optimization that assume a fixed control plane, and optimize only the numerical values of the parameters, (2) The complexity problem: The "protocol space" that embodies the possibilities of all such protocols grows rapidly. We develop a new method, called "Symbolic Monte Carlo Simulation", which accumulates a symbolic expression for the objective function as we traverse the global state space without explicitly enumerating it. This approach provides a smooth trade-off between computational complexity, and the accuracy with which the actual objective function is approximated via symbolic simulation. The optimization program is automatically generated by symbolic Monte Carlo, which is then plugged into a standard non-linear solver to produce the optimal protocol.

We formulate the MAC protocol problem to handle any number of multiple neighborhoods, in the presence of acknowledgments, and solve it using the above approach. As an example, a 9-node, multi-neighborhood problem can be solved in 3 minutes on MATLAB at a 10% margin-of-error with respect to the value of the optimal throughput. This is a significant advance in labor time over "hand-designed" protocols that take months to develop, and for which no optimality guarantees can be given. In the future, this approach has the potential to change the way that MAC protocols are designed from "hand-designed protocols" to protocols designed via design automation chains.

Speaker Biography: Volkan Rodoplu received his B.S. degree in Electrical Engineering from Princeton University in 1996 and his M.S. degree in Electrical Engineering from Stanford University in 1998. He worked for Texas Instruments (Dallas, TX) in 1998, and for Tensilica, Inc. (Santa Clara, CA) in 2000-2001. He received his Ph.D. in Electrical Engineering from Stanford University in 2003, and subsequently joined the Department of Electrical and Computer Engineering at UCSB, where he is currently an Associate Professor.

He is the recipient of the National Science Foundation CAREER Award (2007), University of California Regents' Junior Faculty Fellowship (2006), Stanford Department of Electrical Engineering Outstanding Service Award (2000), Andreas Bechtolsheim Stanford Graduate Fellowship (1997), Stanford Department of Electrical Engineering Fellowship (1996), George B. Wood Legacy Prize at Princeton (1996), and G. David Forney Prize at Princeton (1996), and the John W. Tukey Award (1995).