This blog post will contrast another interesting aspect of communication and power networks: designing distributed control through optimization. This point of view has been successfully applied to understanding and designing TCP (Transmission Control Protocol) congestion control algorithms in the last 1.5 decades, and I believe that it can be equally useful for thinking about some of the feedback control problems in power networks, e.g., frequency regulation.
Even though this simple and elegant theory does not account for many important details that an algorithm must deal with in a real network, it has been successfully put to practice. Any theory-based design method can only provide the core of an algorithm, around which many important enhancements must be developed to create a deployable product. The most important value of a theory is to provide a framework to understand issues, clarify ideas, and suggest directions, often leading to a new opportunity or a simpler, more robust and higher performing design.
In Part I of this post, I will briefly review the high-level idea using TCP congestion control as a concrete example. I will call this design approach “forward engineering,” for reasons that will become clear later. In Part II, I will focus on power: how frequency regulation is done today, the new opportunities that are in the future, and how forward engineering can help capture these new opportunities.
TCP congestion control
The basic idea is applicable to/has been applied in many areas, but let’s illustrate with a concrete example: TCP congestion control.
TCP provides several transport-layer functions for the Internet, and one of them is congestion control. This is the problem of deciding how fast every TCP source should send its traffic into the network. For most applications, the faster TCP sends, the better their quality of service, so TCP is designed to send as fast as practical. On the other hand, if TCP sends too fast, it will congest the network, and application performance can suffer. So, the congestion control problem is: how fast should every one of the billions of concurrent TCP connections send?
This is difficult because, in general, the global behavior that arises from the interaction of a large number of local algorithms can be cryptic and fragile. How do we understand and design local algorithms whose global behavior is stable, robust, efficient, and most importantly, understandable? For congestion control, this is difficult primarily for two reasons:
- Congestion control is a feedback control system where decisions are made in real time based on the network state. The mathematics of such a system can be very difficult when the system is nonlinear, distributed, time-varying, random, and time-delayed, which the Internet is. What is the steady state and dynamic behavior of the network?
- No one on the Internet knows global state information, so every TCP source must make a local decision (how fast it should send) based on partial information about the system state. Will the (seemingly) uncoordinated individual decisions destabilize the network or drive it into an inefficient state?
The first (modern) congestion control algorithm, TCP Tahoe, was invented by Van Jacobson, then at Berkeley, in 1988. With this algorithm, a TCP source adjusts its sending rate based on packet loss on its path. The next major idea was TCP Vegas, published in 1995 by Larry Brakmo and Larry Peterson, then at the University of Arizona, where a TCP source adjusts its sending rate based on the queueing delay on its path. These algorithms were designed and implemented as local algorithms based primarily on small-scale experiments and simulations. The macroscopic behavior of an arbitrarily large network was understood only around 2000, and it has a beautifully simple characterization: we can interpret all the billions of TCP sources as carrying out a distributed computation over the Internet in real time to optimize a global objective!
What does this mean?
Reverse and forward engineering
Every TCP source adjusts its sending rate in response to a certain congestion measure (e.g. loss probability in TCP Tahoe, or queueing delay in TCP Vegas). Let’s call the congestion measure in the network the congestion prices, because it has a nice economic interpretation (congestion control can be also be interpreted as computing a competitive market equilibrium). These congestion prices change in response to TCP sending rates, thus closing the loop between TCP algorithms that adjust their sending rates and router algorithms that (often implicitly) adjust the congestion prices. It turns out that we can associate a utility function with each TCP source based on its congestion control algorithm. These local algorithms interact over the Internet and when (if) they stabilize into a steady state, the equilibrium values of all TCP sending rates are the unique maximizer of the aggregate utility (sum of all utility functions), subject to network capacity constraints!
What are the equilibrium values of the congestion prices in the network? They turn out to be the Lagrange multipliers associated with the network capacity constraints. It is in this sense that we say TCP congestion control is carrying out a primal-dual algorithm over the Internet in real time to maximize aggregate utility.
This is the reverse engineering of TCP congestion control: we implement and deploy an algorithm first, and understand its global behavior afterwards.
It may not be possible, or critical, that optimality is exactly attained in a real network. Reverse engineering, nonetheless, has two important implications. First, it provides us with a simple framework to understand the macroscopic behavior of an arbitrarily large network under end-to-end congestion control. For instance, it is possible to predict accurately the steady state sending rates and round-trip delays of all TCP sources as well as the steady state queueing delays at all routers under TCP Vegas (or FAST) for any network. Even though congestion control algorithms in the past were not designed with the view of maximizing network utility, by choosing how to adjust their sending rates in response to congestion prices, they inevitably optimize a certain utility function. Different algorithms simply correspond to different underlying utility functions, and these utility functions can be explicitly reverse-engineered from a model of the congestion control algorithm.
Second, it suggests the treatment of practical congestion control algorithms simply as distributed solutions of a network utility maximization. This offers a theory-based design approach where a desirable utility function is first specified and then a congestion control algorithm is derived as a distributed solution to the prototypical optimization problem. The advantage of this approach is that the global behavior of the network is fair, efficient, scalable, and stable by design.
This is the forward engineering of TCP congestion control: we analyze the global behavior of an algorithm at design time, before implementation and deployment.
Internet is a cyber network where the TCP and router dynamics can be designed jointly (at least in principle) for stability and efficiency. In the next post, I will explain how this point of view can help the design of distributed algorithms in a power network where there are physical dynamics that cannot be altered.