Research (Updated October 2006)

This is an outdated summary for 2003-2006 

Research Page for 2007-2010 can be found at scenic.princeton.edu after November 8, 2009

My research aims to build a new theoretical foundation for the analysis and design of communication networks, to develop a conceptually simple understanding of the architectural principles amid the complexities of network engineering, and to construct new mathematical methodologies of nonlinear and stochastic optimization for tangible impacts on how people access information.

This page outlines my current research activities, organized under four areas and eight subareas. These research activities are often combined with curriculum development projects, and sometimes pursued jointly with industrial partners to enhance the practical impacts of theoretical innovations. As an effort to try to highlight the intellectual heritage of open problems in theoretical networking research, there are also four descriptions of important open problems where a lot of progress has recently been made. (There are obviously many more publications, sometimes hundreds of them, on these important problems. If there are some important ones that I'm missing in the chronology of highlights, please email me.) Two survey papers are also linked here. For a complete list of publications beyond these six papers, please see Publications . For lecture notes of a course on Optimization of Communication Systems, please see Class .

Area 1: A Mathematical Theory of Network Architectures

Architecture determines functionality allocation: 'who does what' and 'how to connect them', rather than just resource allocation. It is often more influential, harder to change, and less understood than any specific resource allocation scheme. In networking, functionality allocations can happen, for example, between the network management system and network elements, between end-users and intermediate routers, and between source control, routing, and physical resource sharing. The study of network architectures involves the exploration and comparison of alternatives in functionality allocation. Fundamental understanding of architectures has been established in communication (source-channel separation theorem), in control (controller-plant-sensor-actuator), and in computation (input-processor-memory-output). But such understanding architecture in networking has been limited and primitive. We are working on a set of conceptual frameworks and mathematical languages for a clear and rigorous foundation of network architectures.

Area 1A: Layering As Optimization Decomposition LAD page

Layered architectures form one of the most fundamental structures of network design. While the general principle of layering is widely recognized as one of the key reasons for the enormous success of data networks, there is little quantitative understanding to guide a systematic, rather than an ad hoc, process of designing layered protocol stack for wired and wireless networks.

One possible perspective to rigorously and holistically understand layering is to integrate the various protocol layers into a single coherent theory, by regarding them as carrying out an asynchronous distributed computation over the network to implicitly solve a global optimization problem. Different layers iterate on different subsets of the decision variables using local information to achieve individual optimality. Taken together, these local algorithms attempt to achieve a global objective. Such a design process of modularization can be quantitatively understood through the mathematical language of decomposition theory for constrained optimization. Different 'vertical decompositions' of an optimization problem, in the form of a generalized Network Utility Maximization (NUM), are mapped to different layering schemes in a communication network. Each decomposed subproblem in a given decomposition corresponds to a layer, and certain functions of primal or Lagrange dual variables (coordinating the subproblems) correspond to the interfaces among the layers. 'Horizontal decompositions' can be further carried out within one functionality module into distributed computation and control over geographically disparate network elements. Since different decompositions lead to alternative layering architectures, we can also tackle the question 'how and how not to layer' by investigating the pros and cons of decomposition methods.

'Layering as Optimization Decomposition' attempts at shrinking the 'knowledge tree' on cross layer design rather than growing it. It is important to note that 'Layering as Optimization Decomposition' is not the same as the generic phrase of 'cross-layer optimization'. What is unique about this framework is that it views the network as the optimizer itself, puts the end user application needs as the optimization objective, establishes the globally optimal performance benchmark, and offers a common set of methodologies to design modularized and distributed solutions that may attain the benchmark. It provides a top-down approach to design layered protocol stacks from first principles. The resulting conceptual simplicity stands in contrast to the ever-increasing complexity of communication networks. The two cornerstones for the rigor and relevance of this framework are 'networks as optimizers' and 'layering as decompositio'. Together, they provide a promising angle to understand not just what 'works' in the current layered protocol stacks, but also why it works, what may not work, and what alternatives network designers have.

There have been many recent research activities along the above lines by research groups around the world. Many of these activities were inspired by the seminal work by Kelly et. al. in 1998, which initiated a fresh approach of optimization-based modeling and decomposition-based solutions to simplify our understanding of the complex interactions of network congestion control. Since then, this approach has been substantially extended in many ways beyond just congestion control, and now forms a promising direction towards a mathematical theory of network architectures. The following paper surveys the current status of this research area, including 10 key messages, 20 commonly encountered methodologies, and a list of future research challenges. Another source of three related survey papers is the IEEE JSAC special issue August 2006.

Survey Article 1. M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, 'Layering as optimization decomposition: A mathematical theory of network architectures', Proceedings of the IEEE, vol. 95, no. 1, pp. 252-312, January 2007.

Area 1B: Quantifying Network X-ities

Almost all of the existing theoretical foundations for networks have focused on traditional performance metrics, eg, throughput, delay, loss, energy. However, it is becoming increasingly important that networks not only provide good performance, but do so in the face of an uncertain, error-prone, and ever-changing environment. The need for robustness leads to a set of new metrics that we refer to as Network X-ities: evolvability, scalability, dependability, diagnosability, manageability, optimizability, etc; Practitioners appreciate that Network X-ities are critically important and often supersede performance metrics. Yet these Network X-ities often lack quantitative frameworks or even well-defined units and meaning. The goal of this challenging research direction is to build a rigorous foundation for explicitly considering Network X-ities as a first principle in the design of networks, rather than a fuzzy after-thought.

The intellectual challenge for this ambitious undertaking is tremendous. We have several successful starting points, eg, the Evolvable Network Design Tool that uses stochastic dynamic programming to optimize large-scale, multi-year network evolutions, and the 'design for optimizability' work for Internet routing as discussed below. This is just the beginning of long-term efforts to provide the intellectual foundation for a network science that reaches beyond the performance-centric mentality and studies the performance-X-ities tradeoff.

Open Problem Case 1: Minimum-cost Link-state-determined Intra-domain Routing

A key difficulty is this problem is that the optimization of Internet traffic engineering is nonconvex and with integer constraints. It turns out that simple changes to the underlying protocol assumptions (design for optimizability), together with a reformulation of the problem to bring in, simultaneously, link weights and flow spliting as optimizaion variables, leads to a very efficient two-stage relaxation algorithm. A brief chronology of highlights:

In 1950s-1960s, Bellman and Ford, and Dijkastra proposed shortest path routing algorithms.

In 1980s-1990s, intra-domain routing algorithms based on link weights are used in the Internet OSPF and IS-IS protocols.

In late 1990s, more complex MPLS protocols are proposed, but they lose many desirable features in OSPF, such as distributed determination of flow splitting and ease of management.

In 2000, Fortz and Thorup presented local search methods to approximately solve the NP-hard problem in OSPF.

In 2000-2004, many improvements to local search methods, and suggestions of simulated annealing methods presented.

In 2003, Sridharan, Guerin, and Diot proposed to use a centralized greedy computation to select the subset of next hops for each prefix to attain load balancing much better than even splitting among the shortest paths.

In 2005, Fong, Gilbert, Kannan, and Strauss proposed to allow flows on non-shortest paths, but loops may be present and performance under multi-desintation scenarios is not clear.

In 2006, Xu, Chiang, and Rexford proposed the DEFT protocol, which uses exponential penalty on non-shortest path flows and reformulates the problem to incorporate both link weights and flow splitting into the optimization simultaneously. A two-stage approximation algorithm then solves this nonconvex, nonsmooth problem to within 1% of suboptimality gap when OSPF by local search has 200% suboptimality gap. DEFT is also proved to be never worse than OSPF while it has the same protocol complexity.

D. Xu, M. Chiang, and J. Rexford, 'DEFT: Distributed exponentially weighted flow splitting', Proc. IEEE INFOCOM, May 2007.

Recently, Xu, Chiang, and Rexford further proved that link state routing and hop by hop forwarding can achieve optimal traffic engineering, with the optimal link weights computed in polynomial time.

Area 2: Broadband Access Networks

Access networks are often the rate-reach-reliability-quality bottleneck of end-to-end connections in wide area networks. Realizing the vision of truly broadband and ubiquitous access to almost everyone in the U.S. is a formidable task, with many significant technical and socio-economic challenges. In partnership with some of the key companies in the space of access networking, we are working on a variety of fundamental research topics that will help resolve the access bottleneck.

Area 2A: Wired Broadband Access: FAST Copper Project FAST Copper Page

FAST Copper is a multi-year, U.S. NSF funded project that started in 2004, and is currently pursued jointly by the research groups of Mung Chiang at Princeton University, John Cioffi at Stanford University, and Alexader Fraser at Fraser Research Lab, and in collaboration with several industrial partners including AT&T. The goal of the FAST Copper Project is to substantially improve the rate, reach, reliability, and quality in copper-last-mile broadband access to everyone with a phone line, through the combination of fiber/DSL deployment, engineering innovations, and fundamental research.

This goal will be achieved through two threads of research: dynamic and joint optimization of resources in Frequency, Amplitude, Space, and Time (thus the name `FAST', note that FAST Copper project is completely different from the TCP FAST project at Caltech, which is a project that improves the transport layer protocol) to overcome the attenuation and crosstalk bottlenecks, and the integration of communication, networking, computation, modeling, and distributed information management for architectural design of broadband access networks.

The overall solution is a hybrid fiber/DSL deployment where fiber is pushed into the access network but copper takes over the last mile, thereby utilizing the best of ubiquity, broadband, reliability, and economic viability. Can substantially higher data rate and application throughput be attained over DSL through research innovations? We believe the answer is definitely positive. To achieve data rates significantly higher than the current levels on low-twist unshielded telephone wires demands thinking about transmission on copper wires in a new way. This project combines innovative optimization and signal processing techniques with novel network architectures and protocols,

There are two shifts of mentality that underlines the wide range of activities in FAST Copper:

The first key idea is that, instead of holding the traditional view that each twisted pair is an independent channel, we model a bundled cable of twisted pairs as one aggregate multi-user communication system. Multiple users compete against and cooperate with each other in this system. We can explicitly take into account the crosstalk effects (both near-end and far-end) that currently form the data rate bottleneck, and to exploit potential cooperation in sharing limited resources

The second key idea is that today's traffic over broadband access, including voice, data, and video, are predominately supported by packet switched IP. We can exploit the burstiness of the application traffic through aggressive statistical multiplexing, with admission control, traffic shaping, scheduling, and priority queuing mechanisms to ensure the desired tradeoff between the number of application flows supported and the Quality of Service attainable.

Progress in the project come from solving important problems in the fundamental research disciplines of information theory (multi-carrier interference channel), signal processing (multi-user transceiver design), optimization theory (nonconvex and coupled problems), graph theory (survivable tree topology design), stochastic theory (processor sharing and queuing networks), distributed control (feedback control at different timescales), and network protocol design (resource allocation and functionality allocation). As an example, progress made on one of these challenges is summarized below.

Open Problem Case 2: Spectrum Management in Multi-carrier Interference Channel

A key difficulty in this problem is that the optimization is nonconvex and globally coupled (acorss both users and tones). It turns out that the idea of 'static pricing' can be used to decouple the users, and 'dynamic pricing' to decouple the tones for each user. A brief chronology of highlights:

In early 1990s, Cioffi invented ADSL based on discrete multitone modulation.

In early to late 1990s, many researchers including Cioffi's group proposed various spectrum management and bit loading algorithms for variants of DSL.

In early 2000s, work on dynamic, instead of static, spectrum management started.

In 2002, Yu, Ginis, and Cioffi proposed Iterative Waterfilling (IW) algorithm, which is autonomous, low complexity, convergent under certain conditions for certain two-user case, but substantially suboptimal in terms of rate region achieved.

In 2003, Chung strenghthened convergence conditions for IW.

In 2004, Luo provided further characterization of convergence of IW under symmetric channel condition.

In 2004, Cendrillon, Yu, Moonen, Verlinden, and Bostoen proposed Optimal Spectrum Balancing (OSB), which is optimal but centralized and exponential complexity.

In 2005, Lui and Yu, and Cendrillon and Moonen proposed Iterative Spectrum Balancing (ISB), which is near-optimal but centralized and high complexity.

In 2006, Papandriopoulos and Evans proposped SCALE, which is optimal but requires global coordination by message passing.

In 2006, Cendrillon, Huang, Chiang, and Moonen proposed Autonomous Spectrum Balancing (ASB), which is autonomous, low complexity, convergent whenever IW converges, and still near-optimal.

R. Cendrillon, J. Huang, M. Chiang, and M. Moonen, 'Autonomous Spectrum Balancing for Digital Subscriber Lines', To appear IEEE Transactions of Signal Processing, 2007.

Area 2B: Wireless Broadband ACcess: Cellular Network Design

Wireless cellular networks present one of the most transformative access tecnologies that have changed how people communicate on the move. In collaboration with Qualcomm Flarion, we are investigating both architectural issues and specific resource allocation algorithms in CDMA and OFDM based systems, including SIR assignment, power control, scheduling, antenna beamforming, bandwidth allocation, base station assignment, and mobility control. Recent progress made on power control is discussed below.

Open Problem Case 3: Distributed and Jointly Optimal SIR and Power Control in Multi-cellular Uplink

A key difficulty in this problem is that the constraint set of the optimization is coupled in a way that cannot be simply decoupled to enable distributed solution. A new reparameterization of the constraint set through the left, rather than the right, Perron-Frobenious eigenvectors turns out to be necessary. A brief chronology of highlights:

In early 1990s, Qualcomm's solution to near-far problem in 2G CDMA uplink through equalization of received power.

In 1992, Zander characterized the feasibility region of attainable SIR in terms of spectral radius of a matrix of system parameters.

In 1993, Foschini and Miljanic proposed a distributed power control that converges to the target SIR vector, provided that the vector is feasible and fixed.

In mid to late 1990s, a large body of research work on distributed power control in cellular networks uplink, eg, Mitra, Wong, etc.

In 1995, Yates provided a general framework based on the Foschini Miljanic algorithm.

In 1995, Bambos, Chen, and Pottie proposed a robust version of Foschini Miljanic power control.

In late 1990s, 2.5G and 3G data networks demand a joint optimization of SIR assignment and power control.

In 2000-2002, Saraydar, Mandayam, and Goodman used game theory for distributed joint SIR assignment and power control. Convergence to Nash equilibrium is studied, but global optimality may be lost.

In 2002, O'Neill, Chiang, Julian, and Boyd solved special cases in high SIR regime optimally but centrally.

In 2003-2004, O'Neill, Julian, and Boyd, and Chiang, solved general cases in high SIR regime optimally but centrally.

In 2004-2005, Boche and Stanczak characterized convexity and log convexity of the feasbility region in more general terms.

In 2006, Hande, Rangan, and Chiang presented a distributed algorithm that converges to the jointly optimal SIR assignment and power control.

P. Hande, S. Rangan, and M. Chiang, 'Distributed uplink power control for optimal SIR assignment in cellular data networks'', Submitted to IEEE/ACM Transactions of Networking, August 2006. Also in Proceedings of IEEE INFOCOM, April 2006.

Area 3: Nonlinear Optimization of Communication Systems

Linear programming has found important applications in communication networks for several decades. In particular, network flow problems, ie, minimizing linear cost subject to linear flow conservation and capacity constraints, include important special cases such as the shortest path routing and maximum flow problems. Recently, there have been many research activities that utilize the power of recent developments in nonlinear convex optimization to tackle a much wider scope of problems in the analysis and design of communication systems. These research activities are driven by both new demands in the study of communications and networking, and new tools emerging from optimization theory. In particular, a major breakthrough in optimization over the last two decades has been the development of powerful theoretical tools, as well as highly efficient computational algorithms like the interior-point method, for nonlinear convex optimization, ie, minimizing a convex function, subject to upper bound inequality constraints on other convex functions. Since the early 1990s, it has been recognized that the watershed between efficiently solvable optimization problems and intractable ones is convexity. The last decade has witnessed the appreciation-application cycle for convex optimization, where more applications are developed as more people start to appreciate the capabilities of convex optimization in modeling, analyzing, and designing communication systems. When tackling the much more difficult nonconvex optimization problems, there are some classical approaches, which have been enhanced by new ones in recent years.

The phrase 'optimization of communication systems' in fact carries three different meanings. In the most straight-forward way, an analysis or design problem in a communication system may be formulated as minimizing a cost, or maximizing a utility function, or determining feasibility over a set of variables confined within a constraint set. In a more subtle and recent approach of 'reverse engineering', a given network protocol may be interpreted as a distributed algorithm solving an implicitly defined global optimization problem. In yet another approach, the underlying theory of a network control method or a communication strategy may be generalized using nonlinear optimization techniques, thus extending the scope of applicability of the theory.

Area 3A: NUM: Network Utility Maximization

NUM can be both used as a modeling tool to initiate the study of network architectural alternatives through decomposition theory and as a solution tool to tackle specific resource allocation problems. The Basic NUM (BNUM) is the problem of maximizing a sum of increasing and concave utility functions over linear capacity constraints on the source rate vector. This simplest version of NUM is also known as monotropic programming. Substantially more complicated versions of Generalized NUM (GNUM) and Stochastic NUM (SNUM) have been studied and applied in recent years.

In GNUM, depending on who is interested in the outcome of network design, there are two types of objective functions: sum of utility functions by end users, which can be functions of rate, reliability, delay, jitter, power level, etc, and a network-wide cost function by network operators, which can be functions of congestion level, energy efficiency, network lifetime, collective estimation error, etc. Utility functions can be coupled across the users, and may not have an additive structure (eg, network lifetime). Maximizing a weighted sum of all utility functions is only one of the possible formulations. An alternative is multi-objective optimization to characterize the Pareto-optimal tradeoff between the user objective and the operator objective. Another set of formulations is game-theoretic between users and operators, or among users or operators themselves.

While utility models lead to objective functions, the constraint set of a GNUM formulation incorporates the following two types of constraints. First is the collection of physical, technological, and economic restrictions in the communication infrastructure. Second is the set of per-user, hard, inelastic QoS constraints that cannot be violated at the equilibrium. This is in contrast to the utility objective functions, which may represent elastic QoS demands of the users.

There has been a lot of progress recently made on GNUM, including approaches to tackle the following challenges: nonconcave utility functions, nonconvex constraint set, integer constraints, coupled utility functions, nonsmooth utility functions, and distributed utility-lifetime tradeoff.

Area 3B: GP: Geometric Programming GP Page

GP is a class of nonlinear optimization with many useful theoretical and computational properties. Over the last few years, GP has been used to solve a variety of problems in the analysis and design of communication systems, including information theory problems, signal processing algorithms, queuing system optimization, and many network resource allocation problems such as power control and congestion control. Through the connections with large deviation theory and general market equilibrium theory, we also start to understand why, in addition to how, GP can be applied to a surprisingly wide range of problems in communication systems. These applications have in turn spurred new research activities on GP, especially generalizations of GP formulations and development of distributed algorithms to solve GP in a network. The following monograph provides both an in-depth tutorial on the theory, algorithms, and modeling methods of GP, and a comprehensive survey on the applications of GP to the study of communication systems.

Survey Article 2. M. Chiang, 'Geometric programming for communication systems', Foundations and Trends in Communications and Information Theory, vol. 2, no. 1-2, pp. 1-154, August 2005.

Area 4: Stochastic Analysis of Communication Systems

Stochastic theory of communication networks has a long and rich history. However, many key problems in this area remain open despite decades of effort. In his seminal paper in 1998, Kelly used a deterministic fluid model to remove packet level details and microscopic queuing dynamics, followed by an optimization/game/control-theoretic approach. By assuming deterministic fluids with infinite backlog, we can avoid the difficulty of coupling across links in a general queuing network, and are often able to obtain insights on the structures of network resource allocation.

An analogy can be drawn with Shannon's seminal work in 1948. By turning the focus from finite-blocklength codes to the regime of infinite-blocklength codes, thus enabling the Law of Large Numbers to take effect, Shannon provided architectural principles (eg, source-channel-separation) and established fundamental limits (eg, channel capacity) in his mathematical theory of communication. Since then, the complicating issues associated with the design of practical codes have been brought back into the framework.

Area 4A: Stochastic Network Theory

It is time to incorporate stochastic network dynamics, at the following four levels: session (or flow, user) level, packet level, channel level, and topology level, back to GNUM formulations. This leads to challenging models of queuing networks. For example, service rates of queues are determined by distributed solution to NUM, while parameters of NUM formulations are in turn stochastically varying according to states of the queues.

A combination of stochastic network control and optimization-based resource allocation raises many new questions, including stochastic stability, average case performance, outage performance, and, eventually, the distribution of attained utility (or other QoS parameters such as delay) as induced by the distributions of the stochastic models. Solving all these problems at all four levels of stochastic dynamics would represent a long overdue union between stochastic network theory and network optimization theory.

We have been exploring three topics in this area this year: session-level stochastic stability under general file size distribution, packet-level noisy feedback's impact on convergence, and channel-level dynamic's impact on convergence and optimality of distributed optimization algorithms.

Session-level stochastic stability is the most extensively-studied problem in this area: under what conditions will a certain distributed algorithm of a NUM problem remain stochastically stable, in the sense that the number of sessions and the total queue length in the network remain finite? Since real traffic does not follow exponential distribution of workload (or file size), we cannot assume Markov arrival statistics.

Open Problem Case 4: Stochastic Stability of NUM for General File Size Distribution

A key difficulty in this problem is that the queue service rates are determined by an underlying optimization problem, and, for general arrival statistics, stability cannot be proved through the positive recurrence of a Markov chain. Establishing fluid model through appropriate scaling and constructing the right Lyapunov function are necessary. A brief chronology of highlights:

In 1960s, Rockafellar and others studied the properties of the deterministic formulation of the basic NUM.

In 1998, Kelly, Maulloo, and Tan presented the basic NUM problem for distributed rate control.

In 1999-2002, researchers including Low, Srikant, etc. showed that TCP congestion control algorithms are implicitly solving different NUM problems.

In 1999, Roberts and Massoulie initiated the study of session level stochastic stability.

In 1999, de Veciana, Lee, and Konstantopulos proved stability for the case of Poission arrival with exponential filesize distribution, general topology, homogeneous utility (all sources have the same utility function), and alpha (in alpha-fair utility function) equal to 1 or infinity.

In 2001, Bonald and Massoulie proved stability for Poission arrival with exponential filesize distribution, general topology, heterogeneous utility (the general case of each source having a possibly different utility function), and general alpha.

In 2004, Lin and Shroff, and Srikant, proved stability for Poission arrival with exponential filesize distribution and fast timescale dynamics (without timescale separation), general topology, homogeneous utility, and alpha greater than 1.

In 2005, Ye, Qu, and Yuan proved stability for general arrival and exponential filesize distribution, general topology, heterogeneous utility, and general alpha.

In 2005, Bramson proved stability for general filesize distribution, general topology, homogeneous utility, and alpha=infinity.

In 2005, Lakshmikantha, Beck, and Srikant proved stability for phase type distribution, 2 by 2 grid topology, homogeneous utility, and alpha=1.

In 2006, Massoulie proved stability for phase type distribution, general topology, homogeneous utility, and alpha=1.

In 2006, Gromoll and Williams proved stability for general distribution, tree topology, homogeneous utility, and general alpha.

In 2006, Chiang, Shah, and Tang proved stability for general distribution, general topology, heterogeneous utility, and sufficiently small alpha, as well as 1/(1+alpha) approximate stability for general alpha.

M. Chiang, D. Shah, and A. Tang, 'Stochastic stability of network utility maximization: General file size distribution', Submitted to IEEE Transactions of Information Theory, September 2006. Also in Proc. Allerton Conference, Sept. 2006.

Area 4B: Information Theory

Data transmission and compression with state information model various communication scenarios, such as the Wyner-Ziv model and Gelfand-Pinsker model. We showed that the known results in eight special cases in fact all belong to a common form, and can be extended to the general case of two-sided state information. In the case of channels with state information at the transmitter, we formulated a new problem of tradeoff between sending pure information and helping receiver's state estimation. For additive Gaussian noise channels, we completed characterized the optimal tradeoff region between channel capacity and estimation error, with a converse proof and an achievability scheme by power allocation between two extreme signalling strategies.