Winter 2004

IMA Tutorial:

Control and Pricing in Communication and Power Networks

March 7, 2004

Organizers:

Christopher L. DeMarco
Department of Electrical and Computer Engineering
University of Wisconsin-Madison
demarco@engr.wisc.edu
http://www.engr.wisc.edu/ece/faculty/demarco_christopher.html

Thomas G. Kurtz
Center for Mathematical Sciences
University of Wisconsin-Madison
kurtz@math.wisc.edu
http://www.math.wisc.edu/~kurtz/

Ruth J. Williams
Department of Mathematics
University of California, San Diego
williams@math.ucsd.edu
http://math.ucsd.edu/~williams/

The tutorial will introduce some of the main issues in the design and operation of communication and power networks and will provide background helpful in understanding the material to be presented during the Workshop. While the connectivity of power and communications networks may be similar, the physics of these networks is very different. The tutorial and the following workshop should provide a better understanding of both the similarities and the differences in these systems.

Abstracts

Network Control, Pricing, and the Role of Cascading Failure Phenomena in Electric Power Grids
Christopher L. DeMarco, University of Wisconsin - Madison

While sharing a number of broad qualitative features with problems in control and resource allocation for other large scale networks such as the internet, electric power grids present a range of unique challenges. Three major technological characteristics distinguish control and pricing problems in electric power: (i) the commodity being delivered is inefficient to store, so production tracks consumption across the entire interconnected grid, nearly instantaneously; (ii) the majority of branches in the delivery network are passive elements, with branch flows dictated by nonlinear relations to nodal boundary conditions, rather than by direct control; (iii) many constraints on operation represent physical limits whose violation can yield costly equipment damage and threats to human safety. Adding to the complexity of analysis is the U.S. electric power system's uneven regulatory policy transition, in which certain physical elements contributing to grid control operate in competitive markets (generators), while the others (e.g., switched capacitor banks, adjustable tap transformers) operate under the authority of regulated regional transmission monopolies.

This tutorial will give an overview of the mathematical models used to predict both dynamic and steady state performance of physical quantities in the electric power grid. Starting from the nonlinear constraints on network power flow, and the nature of financial offers and bids for electric power production and consumption, the relation of so-called "locational marginal prices" to an underlying optimization formulation will be reviewed. Issues in developing effective offer and bid strategies from these locational prices, and related issues for setting regulatory structures to govern these, will be highlighted. The tutorial will conclude with an overview of techniques for predicting cascading failure phenomena. Research to improve these techniques could play a key role in balancing operational strategies that favor efficiency under "normal" conditions, versus strategies that favor mitigation of risk of extremely high cost, low probability failure events such as the eastern U.S. blackout of August 2003.

Pricing and Control for the Internet
R. Srikant, University of Illinois, Urbana-Champaign

In the first part of the tutorial, we will present a general introduction to the architecture of the Internet. Various protocols for scheduling, admission control, routing and congestion control will be introduced. We will then focus our attention on TCP, the widely-used protocol for file transfer in the Internet today. Jacobson's TCP congestion control algorithm has been remarkably successful in regulating file transfers and facilitating the phenomenal growth of the Internet over the last decade. This congestion control mechanism was designed for networks where the required data rate per user is small (less than one Mbps) and the round-trip times are small (of the order of a few milliseconds). However, access speeds, application requirements and file transfer distances continue to increase. Using simple tools from queueing theory and delay-differential equations, we will illustrate the need to redesign the congestion management mechanisms in the Internet to efficiently deliver high data rates over long distances.

In the second part of the tutorial, we will concentrate on pricing and control mechanisms that have recently led to the design of scalable TCP protocols. Starting with Kelly's model of resource allocation in a heterogeneous Internet, it will be shown that congestion management can be viewed as a distributed algorithm for fair resource allocation in the Internet. We will illustrate the use of tools from convex optimization, stochastic processes and control theory in designing congestion control mechanisms at the end users and congestion indication mechanisms at the routers that deliver an efficient loss-free, delay-free service over the Internet.

LIST OF CONFIRMED PARTICIPANTS