home · mobile · calendar · colloquia · 2010-2011 · 

Colloquium - Chen

Optimization, Game, and Layering in Complex Networked Systems
California Institute of Technology

Analysis and design of networked systems has benefited tremendously from a rigorous and holistic approach that employs powerful decomposition tools in optimization theory and game theory to modularize and distribute the design, optimization, and control of networked systems and protocols. The most important feature of such a theory-based approach is not the specific algorithms proposed and analyzed, but that we can derive from first principle the layering structure and modularity of various mechanisms, the interfaces between these mechanisms, and the control/signaling information that must cross these interfaces to achieve a certain performance and robustness.

In this talk, I will first give an overview of essential ideas of the theory-based approach, and then as case studies, discuss two specific network design problems in optimization and game-theoretic frameworks respectively. The first problem is cross-layer design in wireless ad hoc networks. We extend the basic network utility maximization problem to include more protocol layers and the constraints imposed by wireless communications, and develop a general technique to analyze the stability and optimality of dual decomposition for any queueing networks with interdependent, time-varying parallel servers. Based on these results, we propose a layered, but loosely coupled, network architecture that integrates congestion control, routing and scheduling that achieves global optimality, even in a time-varying environment. The second problem is a game-theoretic approach to contention control. We develop a random access game where a medium access control protocol is interpreted as a distributed strategy update algorithm to achieve a Nash equilibrium. The random access game model provides a unique perspective to reverse engineer existing contention-based protocols and a general framework to design better ones. It is a general construction, as it can be reverse-engineered from existing MAC protocols, forward-engineered from desired operating points, or designed based on heuristics. Methods derived from concrete random access game models achieve optimal performance and can provide flexible service differentiations. I will conclude my talk with a brief discussion of future research on foundational theory for the theory-based approach, and its application to future Internet design, energy-aware network design, and power networks.

Lijun Chen received his PhD in Control and Dynamical Systems from the California Institute of Technology (Caltech) in 2007. He is currently a Research Scientist in Computing and Mathematical Sciences Department at Caltech. His main research interest is in complex networked systems (specifically, communication/computer networks and power networks, and their interplay with economics), optimization and game theory and their engineering applications, and theoretical foundation for complex networks. He was a co-recipient of the Best Paper award of 2007 IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS).

Sponsored by the Interdisciplinary Telecommunications Program.
Hosted by Timothy Brown.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)