HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Abstracts IMA Workshop
Control and Pricing in Communication and Power Networks
March 8-13, 2004

Probability and Statistics in Complex Systems: Genomics, Networks, and Financial Engineering, September 1, 2003 - June 30, 2004

Fernando L. Alvarado (Department of Electrical & Computer Engineering, University of Wisconsin) flalvarado@lrca.com

The Role of Uncertainty on Bidding Strategies for Power System Markets
Slides:   pdf
Paper:   pdf

Joint work with Rajesh Rajaraman (Laurits R. Christensen Associates).

Bidding by market participants is the cornerstone of power markets. It is typically assumed that the optimal bidding strategy in uniform price auctions is to bid marginal production costs in the absence of market power. However this observation is only valid under some restrictive assumptions. In general, even for a price-taker in "simple" uniform price auction markets, optimal bidding in electricity markets requires more complex strategies and depends to a nontrivial extent on the statistical characterization of the price uncertainty of markets. This is because of two main reasons. One, "simple" uniform price electricity market auctions involving more than one product are done sequentially, and expectations of clearing prices in future auctions affect bids in present auctions. Two, the cost characteristics and nature of operational constraints are complex --- typically they are non-convex and have significant inter-temporal features --- and they affect bids in a complex way. This paper illustrates via simple examples how each of several realities of actual power markets can influence bidding patterns by a generator. The paper is a direct extraction and slight extension of some prior work done by the authors which has been reported on several Web sites. In this study we create a world in which startup and shutdown costs are not negligible, where there may be inter-temporal restrictions as to a generator's ability to operate, and where a bidder has more than one (mutually exclusive) product to offer (in our examples, reserves and energy) and where the market clearing price for the product is uncertain. We restrict our attention to a single generator that is a price taker, meaning that the generator is unable to influence clearing price with its bid. We illustrate four effects: (a) the nature of the uncertain future prices can drastically affect bidding behavior, (b) the volatility parameter associated with the uncertainty and not just its mean value can have an influence on optimal bidding behavior, (c) operational restrictions that influence multi-period bids can have an impact on behavior, and (d) correlation or lack of correlation between the uncertain prices of multiple products offered (energy and reserves in our examples) can affect optimal bidding behavior. We also illustrate how a more "complete" (and consequently more complex) market design can simplify bidding behavior, thus leading to an inherent tradeoff between simplicity of market design and simplicity of bidding behavior.

Ross Baldick (Department of Electrical and Computer Engineering, The University of Texas at Austin) Ross.Baldick@engr.utexas.edu http://www.ece.utexas.edu/~baldick

Stability of Supply Function Equilibria: Implications for Daily Versus Hourly Bids in a Poolco Market
Slides:   pdf
Panel Discussion Slides:   html    pdf    ps    ppt

Joint work with William Hogan (Center for Business and Government, John F. Kennedy School of Government, Harvard University).

We consider a supply function model of a poolco electricity market where demand varies significantly over a time horizon such as a day and also has a small responsiveness to price. We show that a requirement that bids into the poolco be consistent over the time horizon has a significant influence on the market outcome. In particular, although there are many equilibria yielding prices at peak that are close to Cournot prices, such equilibria are typically unstable and consequently are unlikely to be observed in practice. The only stable equilibria involve prices that are relatively closer to competitive prices. We demonstrate this result both theoretically under somewhat restrictive assumptions and also numerically using both a three firm example system and a five firm example system having generation capacity constraints. This result contrasts with markets where bids can be changed on an hourly basis, where Cournot prices are possible outcomes. The stability analysis has important policy implications for the design of day-ahead electricity markets.

James B. Carson (RisQuant Energy) JBCarson@RisQuant.com

Weather Simulator as Component of Power Market Monte Carlo Simulator (poster session)

Monte Carlo simulation has become the principal means by which power assets may be valued since there exist few reliable analytic methods. It is well understood that weather has an important influence on load and price in the electric power industry. RisQuant Energy has developed a method whereby simulated weather can be incorporated as a component into a comprehensive power market simulator. Each weather simulator produces hypothetical strands of simulated weather that are statistically consistent with the location's long term history. The weather simulation component drives the market price and load simulators that, in turn, drive the valuation of physical and financial power assets.

For the purposes of this poster session, the model for the weather station BOS (Boston) has been fully articulated. 'Weather' was defined as the average of the daily high and low. For the BOS model, one hundred years of daily history was transformed conventionally, mapped to a sine wave with an annual period, and standard regression procedures applied. The residuals were then washed through an autoregression procedure to complete the model. Those residuals were determined to be normally distributed white noise. The statistical results were then coded into a function call with the date and previous simulated weather as arguments.

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

A Phase Transition Model for Cascading Element Failures in Electric Power Networks
  IMA_Panel_3_12_04.pdf    IMA_Cascade_3_04.pdf

The automated removal from service of branch elements and generation units experiencing overloads during large transient power flows in the electric grid played a significant role in the eastern U.S. blackout of August 2003. The work here develops a model of the electromechanical dynamics of the electric power grid, augmented by component models to represent removal from service of transmission branches and generating units when a specified thresholds of branch flow or frequency excursion are exceeded. Assessing the impact of such protective thresholds on network dynamic response and control has long represented a severe challenge in power systems analysis, with heuristic selection of scenarios for time domain simulation representing the only practical approach in the industry. The representation developed here seeks to analytically capture relevant aspects of cascading failure, in which the outage of a network element stimulates further transient excursions in the system state, risking further overloads and element removals. We will demonstrate that with certain common approximations, the structure of the network dynamics with element failure admits a closed form Lyapunov function, and displays multiple stable equilibria associated with progressively degraded network configurations. The ability of the system to recover from one or more network element removals can then be assessed by judging whether or not the system trajectory is captured in the attractive basin of one of these equilibria. Moreover, the availability of a global Lyapunov function associated with the network dynamics provides a means of approximating these basins of attraction, with possibly for a tractable assessment of the impact of element protection thresholds.

Shi-Jie Deng (School of Industrial and Systems Engineering, Georgia Institute of Technology) deng@isye.gatech.edu http://www.isye.gatech.edu/~deng

Heavy-tailed GARCH Models: Pricing and Risk Management Applications in Electric Power Markets
Slides: pdf

Energy markets, in particular, electricity markets grow rapidly as a result of the restructuring of electric power industries around the world. An accurate electricity price model is crucial for both asset valuation and risk management applications.

In the first half of the talk, we propose alternative non-Gaussian GARCH models that could potentially capture the aspects of heavy-tail and volatility clustering in electricity spot prices induced by mean-reversion, jumps and stochastic volatility. We estimate these GARCH models by applying a two-step quasi-maximum likelihood scheme. The two-step approach is validated by Monte Carlo simulation. In the second half, we concern the problem of constructing confidence intervals for the conditional quantile (namely, Value-at-Risk) based on a GARCH model with heavy-tailed innovations. This problem has not been addressed in the existing literature to our best knowledge. Two methods are proposed: one is the normal approximation method and the other is the data tilting method. These two methods are compared via Monte Carlo simulation, and are applied to estimate the Value-at-Risk of individual electricity forward contract as well as electricity demands at different trading hubs.

This talk is based on joint works with Wenjiang Jiang and Liang Peng, et. al.

Bruce Hajek (Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign) b-hajek@uiuc.edu http://tesla.csl.uiuc.edu/~hajek/

On the Flow of Bits and Bucks in the Internet
Slides:   pdf

Based on joint work with Ganesh Gopal, Sujay Sanghavi, and Sichao Yang.

The Internet is a collection of thousands of autonomous routing domains. The organization is to some extent hierarchical, with a clique of tier 1 networks at the top level. The structure is far from tree-like, due to peering arrangements and multi-homing of networks. We present a general framework for modeling hierarchical networks, based on several methods for aggregation of buyers, and several methods for determining the equivalent demand of a set of agents competing in parallel. Basic questions addressed are the question of when profit functions are unimodal in the offered price or bandwidth offered (so that hill-climbing succeeds in maximizing profit), efficiency of allocation, and transfer of demand through intermediate agents.

In addition, three results are presented regarding the cost of anarchy for flat networks. This work, related to recent work of Johari and Tsitsiklis, addresses the amount of inefficiency caused by strategic behavior of buyers.

Linhai He (Electrical Engineering and Computer Science Department, University of California, Berkeley) linhai@eecs.berkeley.edu

Issues in Pricing Internet Services

One of the critical challenges facing the telecommunications industry today is to increase the profitability for Internet service providers. For historical reasons, the current Internet protocol stack lacks basic features needed to implement efficient economic mechanisms. Consequently, the providers have limited economic incentives to invest in new technology for value-added services. This results in a stagnant industry and limits the evolution of the Internet.

In this talk, we present pricing schemes that would enable the providers to profit from offering differentiated services and share the increased revenues fairly. We first show that with the commonly accepted Differentiated Services model, if prices are not properly differentiated with respect to service quality, then the system may settle into either unstable or inefficient equilibria. We then discuss how to construct pricing schemes that are stable and lead to socially optimal allocation among users.

Pricing issues become more complex when a service needs to be jointly provided by a network of providers. We first show that if providers are allowed to charge freely in their own interest, then the resulting equilibrium could be inefficient, unfair and may discourage future upgrades to the networks. As an alternative, a simple revenue-sharing policy, under which providers would agree to collaborate for increasing their revenues, can be shown to eliminates all the aforementioned drawbacks. For its implementation, a protocol is constructed based on the predicted outcome of the game, so that providers do not have incentive to cheat. We construct a decentralized algorithm that the providers can use to compute the optimal prices and show that the algorithm is scalable and converges to the improved equilibrium.

Marija D. Ilic (Department of Electrical and Computer Engineering, Carnegie Mellon University) milic@ece.cmu.edu http://www.ece.cmu.edu/~milic

A Multi-Layered Approach to Transmission Provision and Pricing in the Electric Power Networks
Slides:  html   pdf    ps    ppt

In this talk, I review three qualitatively different mechanisms of delivering electric power under open access. The first approach is based on optimizing power dispatch under transmission constraints, and providing a bundled electricity price signal which incorporates both energy and systems support charges. This approach is based on the original notions of spot electricity prices [1] underlies today's spot markets in several parts of the U.S. electric grid and is recommended by Professor Hogan at Harvard [1a]. The second approach allows for the electricity trading process to be separate from the transmission system support needed to deliver the traded power. This was introduced by several Berkeley faculties in [2]. The only constraint is that the market participants trade under the technical constraint that the transmission limits are not exceeded. There is no transmission price signal in this method. Finally, the so-called two-level transmission provision and pricing was introduced by Ilic et al at MIT in [3]. This method is based on iterative information exchange between the market participants and the transmission system provider: The market participants inform a system provider concerning the location and amount of power they wish to inject into particular locations within the electric grid, and the system provider, based on all given requests, optimizes use of the available transmission capacity and sends the transmission price signal to the market participants. The market participants adjust their requests, the delivery price gets adjusted, and the transactions are implemented. It is documented in [3] that at the equilibrium all three schemes result in the same optimum under several simplifying assumptions.

In this paper we review the assumptions under which these transmission provision and pricing schemes are designed and compared to:

Analyze current industry proposals for transmission provision and pricing in light of the three methods.

Propose a generalization of the method described in [3] which allows for a multi-layered reliability-related risk management and valuation of system support.

Summarize recent simulation results [4, 5, 6] illustrating typical outcomes of the multi-layered transmission provision and pricing.

1.1.3 References:

[1] Schweppe, F., Caramanis, M., Tabors, R., Bohn, R., Spot Pricing of Electricity, Kluwer Academic Publishers, Boston, MA, 1988.

[1a] Hogan, WW, Contract networks for electric power transmission, Journal of Regulatory Economics, 1992, pp. 211-242.

[2] Wu, FF, Varaiya, P., Spiller, P., Oren, S., Coordinated multilateral trades for electric power networks: theory and implementation. POWER Report PWR-031, Univ. of California Energy Institute, June 1995.

[3] Allen, E., M. Ilic and Z. Younes, "Providing for Transmission in Times of Scarcity: An ISO Cannot Do it All," Electrical Power and Energy Systems, pp. 147- 163, 1999 (Special Issue on Deregulation).

[4] Ilic, M., Hsieh, E., Ramanan, P., Transmission Pricing of Distributed Multilateral Energy Transactions to Ensure System Security and Guide Economic Dispatch, IEEE Trans. on Power Systems, May 2003.

[5] Wang, H, Ilic, M., Vogelsang, I., Multi-Layered Unbundled Delivery of Electricity Service to Customers under Normal Conditions, Proc. of the PES IEEE General Meeting, June 2004, Denver, CO, paper no 04GM1285.

[6] Minoia, A., Ernst, D., Ilic, M., Market dynamics driven by the decision making of both power producers and transmission owners, Proc. of the PES IEEE General Meeting, June 2004, Denver, CO.

Peter Marbach (Department of Computer Science, Bahen Center for Information Technology (BCIT),University of Toronto) marbach@cs.toronto.edu http://www.cs.toronto.edu/~marbach/

Rate Control in Random Access Networks (poster session)

Joint work with Clement Yuen.

We study the link congestion problem in contention-based networks such as wireless LAN's. These networks are characterized by the use of a random access protocol for channel access. We assume adaptive users or applications in the sense that their traffic flows are elastic. We further assume that individuals' service requirements can be characterized by demand functions that are price-sensitive. A price-based rate control strategy, where the price indicates the current congestion state, is considered to control channel congestion. The effectiveness of price-based rate control is studied in the context of the classic slotted ALOHA model with an infinite population. The price as the new state variable is dynamically updated based on control parameters and the ternary channel feedback. Our results show that under this model stabilization of the ALOHA channel can be achieved. In particular, by using drift analysis, we prove that the associated Markov chain is positive recurrent. The resulting steady state probability distribution thus characterizes an operating point for the model. Moreover, a desired operating point as such could be selected by proper choice of the control parameters. We also show that service differentiation is realized at the operating point. From a control perspective, where demand functions become predetermined system parameters, such a price-based scheme offers a simple mechanism to provide service differentiation in a best-effort contention-based network. We also discuss how this scheme can be integrated with price-based rate control for point-to-point networks to provide end-to-end rate control.

Sean P. Meyn (Coordinated Science Laboratory and and Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign) meyn@control.csl.uiuc.edu  http://decision.csl.uiuc.edu/~meyn

Dynamics of Ancillary Service Prices in Power Networks
Slides:   pdf

The talk concerns resource allocation, pricing, and performance evaluation in electric power markets. Our ultimate goal is the integration of new approaches to dynamic control of stochastic networks, with recent results concerning the competitive market equilibrium in network industries, to obtain comprehensive approaches to model reduction and control for network-level bulk power systems.

The talk will describe some modest first steps:

(i) A dynamic flow model constructed for a single-consumer model in analogy with a standard stochastic queuing model.

(ii) The approximation of the socially-optimal policy by an explicit threshold policy.

(iii) The inability to sustain the socially-optimal policy as a decentralized market outcome.

Generalizations to complex models are also described.

Joint work with Prof. I-K. Cho, Department of Economics, and Mike Chen, Coordinated Science Laboratory.

Presentation available on-line http://black.csl.uiuc.edu/~meyn/pages/IMA04.pdf

John Musacchio (Electrical Engineering and Computer Science Department University of California, Berkeley)

Game Theoretic Modeling of Wi-Fi Pricing (poster session)

In this work we study the relationship between a WLAN owner acting as a wireless access provider and a paying client. We model the interaction as a dynamic game in which the players have asymmetric information ¨C the client knows more about her utility function than the access provider knows. We find that if a client has what we call a web browser utility function, it is a Nash equilibrium for the provider to charge the client a constant price per unit time, and that clients with sufficiently high valuations for the service pay the price. In contrast, we find that if a client has what we call a file transferor utility function, with a bounded file length, the client should be unwilling to pay until the final time slot of her file transfer. We also analyze a Bayesian model in which the provider does not know whether he faces a web browser or file transferor type client, and study the case where there is no bound on the client's file length.

Andrew M. Odlyzko (Digital Technology Center, University of Minnesota)  odlyzko@dtc.umn.edu  http://www.dtc.umn.edu/~odlyzko

Pricing and Architecture of the Internet: Historical Perspectives from Telecommunications and Transportation
  html    pdf    ps    ppt

Sophisticated pricing has often been offered as a solution to various assorted deficiencies of the Internet. So far this has not succeeded, and in general historical precedents from telecommunications for introduction of differentiated services and complicated charging methods on the Internet are discouraging.

On the other hand, the history of transportation presents a different picture, with frequent movements towards increasing price discrimination and more complicated pricing (although with many noteworthy reversals). Charging according to the nature of the goods being transported has been and continues to be the norm. Since the incentives to price discriminate are increasing, and the ability to do so is also growing, it is conceivable that telecommunications might break with its historical record and follow the example of transportation. It is therefore of interest to examine the evolution of pricing and quality differentiation in transportation.

Thomas Overbye (Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign)  overbye@ece.uiuc.edu http://www.ece.uiuc.edu/faculty/faculty.asp?overbye

Power System Control: Enhancing the Human-System Interface
  html    pdf   ps    ppt

Some of the operation of the electric grid is automated. However, this degree of automation is much lower than many people assume. Human operators are very much "in the loop," particularly during emergency situations such as during the time period leading up to the August 14th blackout. This work examines how delay in the human-system interface can adversely affect the operation of the grid, and then examines techniques to enhancing this interface, with the goal of reducing control delay. The work discusses methods for helping operators to quickly extract vital information from the large amount of power system data, and to translate this information into effective control actions.

Asuman Ozdaglar (Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, 35-208, Massachusetts Institute of Technology)  asuman@MIT.EDU

Flow Control, Routing, and Performance from Service Provider Viewpoint (poster session)

We consider a game theoretic framework to analyze traffic in a congested network, where a profit-maximizing monopolist sets prices for different routes. Each link in the network is associated with a flow-dependent latency function which specifies the time needed to traverse the link given its congestion. Users have utility functions defined over the amount of data flow transmitted, the delays they incur in transmission, and the expenditure they make for using the bandwidth. Given the prices of the links, each user chooses the amount of flow to send and the routes to maximize the utility he receives. We define an equilibrium of user choices given the prices, show its existence and essential uniqueness, and characterize how this equilibrium changes in response to changes in prices. We then define a monopoly equilibrium (ME) as the equilibrium prices set by the monopolist and the corresponding user equilibrium, and characterize this equilibrium.

We also study the performance of the ME relative to the user equilibrium at zero prices and the social optimum, which would result from the choice of a network planner with full information and full control over the flow and routing choices of users. Although equilibria for a given price vector or without prices are typically inefficient relative to the social optimum, we show that the ME achieves full efficiency for the routing problem (i.e., where each user has a fixed amount of data to transmit). Finally, we consider the case where there are multiple service providers competing for users, and show similar characterization and efficiency results.

This is joint work with Daron Acemoglu, Department of Economics, MIT.

Marty Reiman (Bell Laboratories, Lucent Technologies) marty@research.bell-labs.com  http://cm.bell-labs.com/cm/ms/who/marty/

Revenue Management for a Telecommunications Network

We consider two related 'revenue management' problems for a telecommunications network. In both problems there is a fixed network consisting of a set of interconnected links, each with a specified capacity. There are also several customer classes, each of which is associated with a route in the network. Customers contract in advance for a fixed route over a long term period (e.g. six months). We assume that the contract interval begins at the same time, T, for all customers. In both problems the objective is to maximize the total expected revenue obtained during [0,T]. In the first problem the arrival rates depend on the posted prices for the various routes according to a known demand function, and we consider the problem of dynamically choosing the prices over [0,T]. In the second problem we assume fixed prices and arrival rates, and use admission control.

When the bandwidth on all of the links is large, which is typically true in practice, an asymptotic approach can be used to obtain good policies for both problems. Fluid level (strong law of large numbers) results yield an 'open loop' policy for each problem. Diffusion (central limit theorem) analysis yields 'corrections' to the fluid policies that perform extremely well.

Based on joint work with Rami Atar and Qiong Wang.

Sujay R. Sanghavi (University of Illinois Urbana Champaign) sanghavi@uiuc.edu

Optimal Allocation of a Divisible Good to Strategic Buyers (poster session)
Slides:   pdf
Paper:   pdf

Joint work with Bruce Hajek.

We address the problem of allocating a divisible resource to buyers who value the quantity they receive, but strategize to maximize their net payoff (value minus payment). An allocation mechanism is used to allocate the resource based on bids declared by the buyers. The bids are equal to the payments, and the buyers are assumed to be in Nash equilibrium. For two buyers such an allocation mechanism is found that guarantees that the aggregate value is always greater than $\frac{7}{8}$ of the maximum possible, and it is shown that no other mechanism achieves a larger ratio. For a general finite number of buyers an allocation mechanism is given and an expression is given for its worst case efficiency. For three buyers the expression evaluates to 0.8737, for four buyers to 0.8735 and numerical computations suggest that the numerical value does not decrease when the number of buyers is increased beyond four. A potential application of this work is the allocation of communication bandwidth on a single link.

Éva Tardos (Department of Computer Science, Cornell University) eva@cs.cornell.edu

Price of Anarchy in Network Games
Slides:   pdf

We approach traditional algorithmic questions in networks from the perspective of game theory: we will focus on settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. We will quantify the degradation of quality of solution caused by the selfish behavior of users, and design algorithms that can help mitigate this degradation.

We consider a "selfish" routing in which each network user routes its traffic on the minimum-latency path available to it, ignoring the latency of all other users. We compare this "selfish" routing to a social optimum, where the objective is to route traffic such that the sum of all travel times---the total latency---is minimized. In general the "selfish" assignment of traffic to paths will not minimize the total latency, i.e., the lack of central regulation degrades network performance. In this talk we will quantify the degradation of network performance due to unregulated traffic. Joint work with Tim Roughgarden, Henry Lin and Asher Walkover.

We will also mention results for a simple network design game, which is joint work with A. Dasgupta, E. Anshelevich and T. Wexler.

John N. Tsitsiklis ( Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology)  jnt@mit.edu  http://web.mit.edu/jnt/www/home.html

Efficiency Loss in Resource Allocation and Supplier Selection Games
Slides:   pdf
Paper:   pdf

Motivated by certain proposals for network resource allocation, we analyze a simple game in which the users of congested finite-capacity links anticipate the effect of their actions on the link prices. We discuss existence and uniqueness of a Nash equilibrium, and establish that the efficiency of the system drops by no more than 25% relative to the social optimum. We also discuss the case where the link capacity is elastic but costly. We extend the results to a more general resource allocation mechanism in which a set of producers compete for a limited amount of available resources.

Motivated by electricity markets, we consider an analogous situation involving a set of competing suppliers who bid in order to satisfy a prespecified demand. We show that if each producer's "bid" consists of a supply function within a certain one-parameter family, the efficiency loss at a resulting Nash equilibrium can be bounded and decreases to zero with the number of suppliers.

Finally, we argue that the particular families of demand and supply functions we consider are the only ones that possess certain desirable properties.

This is joint work with Ramesh Johari and Shie Mannor.

George C. Verghese (EECS Department, MIT) verghese@MIT.EDU

Power Network Dynamics: Questions, Examples, Problems

The talk will center on questions related to the modeling, estimation and control of power network dynamics, and will elaborate on some of these questions with illustrative or evocative examples, some drawn from the work of our group. Problems of potential interest to applied mathematicians will be highlighted. The questions include the following:

How are power networks different from communication networks? What are the components, interconnections and important variables? What is normally known about them, who knows, and when? How can one recognize and expose features that are dynamically important? How does the graph structure of the network affect its dynamic behavior? Are there control strategies that exploit connections between graph structure and dynamics? What sorts of deterministic and stochastic aggregation or simplification are desirable or possible in studying dynamic behavior? What has to be or can be done in a decentralized fashion, and what in centralized fashion? How and when are failures confined, how and when do they cascade out of control?

Glenn Vinnicombe and Ioannis C. Lestas (Department of Engineering, University of Cambridge) gv@eng.cam.ac.uk http://www.eng.cam.ac.uk/~gv/ icl20@hermes.cam.ac.uk

Robustness of Optimization Based Internet Congestion Control Models to Deviations from Protocol Structure and Symmetry (poster session)

Scalable stability conditions derived so far for optimization based models of congestion control protocols, can be shown mathematically to hold for arbitrary networks provided the underlying protocol is symmetric. In practical implementations, however, deviation from this symmetry is inevitable. It is hence crucial to establish whether these models are fragile with respect to a relaxation of the symmetry assumption. We prove that this is not the case by presenting scalable, decentralized conditions, that guarantee local stability for models of non-symmetric, TCP like protocols, of arbitrary interconnection. We also illustrate how these conditions converge to those derived for symmetric protocols as the degree of non symmetry becomes smaller. Finally, we show the way the decrease rule in TCP is associated with robust stability to non symmetric deviations from the protocol.

The analysis is based on some recent techniques of bounding the eigenvalues of matrices using convex hulls, by taking advantage of the internal structure of the matrices, which often has an appealing graph theoretic interpretation.

Jean Walrand (Department of Electrical Engineering and Computer Science, University of California at Berkeley)  wlr@eecs.berkeley.edu  http://www.eecs.berkeley.edu/~wlr

Pricing and Revenue Sharing in Multi-Provider Networks
  html    pdf    ps    ppt

One critical challenge facing the telecommunications industry is to increase the Internet's profitability for network service providers. Currently, the network providers have limited economic incentives to invest in technology for value-added services. This situation results in an untapped potential of the network. Two ingredients are essential for improving the situation.

First, the network must implement mechanisms that enable providers to charge services differentially based on their characteristics. Second, the mechanisms must make it possible for the network providers to share the revenues fairly. If they can charge more for better services and collect a fair share of the resulting increased revenues, the network providers have the incentive to provide services that users value more.

In this talk, we describe some results on service differentiation and a protocol for revenue sharing among network providers. The protocol uses a new form of packet marking.

This is joint work with Linhai He, a Ph.D. Candidate at UCB.

John Ting-Yung Wen (Department of Electrical, Computer, & Systems Engineering, Rensselaer Polytechnic Institute, Troy, NY 12180) wen@cat.rpi.edu http://www.cat.rpi.edu/~wen

Passivity-based Methodology for Network Traffic Management (poster session)
  html    pdf    ps    ppt

Joint work with Murat Arcak and Xingzhe Fan.

We will present a unifying methodology for distributed optimization for network traffic management, from traffic routing, flow regulation, to power control. The foundation of our work is the concept of passivity, which is motivated by energy conservation or dissipation in physical systems and has long been used in the stability analysis and design of nonlinear feedback systems. It is an ideal tool for network stability analysis and control design due to its applicability to nonlinear systems and close linkage to optimization. Through the passivity approach, we have developed new classes of distributed dynamic optimization algorithms and explicit conditions for their stability and robustness.

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

Fluid and Brownian Models of Congestion at Flow Level
Slides:  html

Massoulie and Roberts have introduced and studied a flow level model of Internet congestion control, that represents the randomly varying number of flows present in a network where bandwidth is dynamically shared between elastic document transfers.

In this talk, balanced fluid models and Brownian networks will be used to investigate the behavior of the flow level model in heavy traffic, under certain assumptions. Particular interest attaches to the phenomenon of entrainment, whereby congestion at some resources may prevent other resources from working at their full capacity.

This talk is based on joint work with Frank Kelly, Weining Kang and Nam Lee.

Sichao Yang (Department of Electrical & Computer Engineering, Cordinated Science Lab, University of Illinois - Urbana-Champaign) syang8@uiuc.edu

An Efficient Mechanism for Allocation of a Divisible Good with its Application to Network Resource Allocation (poster session)
Slides:   pdf

Joint work with Bruce Hajek.

We propose an efficient mechanism for allocation of a divisible good. Strategic buyers play a game by submitting bids to the seller. The seller allocates the good in proportion to the bids and charges the buyers nonuniform prices according to the mechanism. Under some mild conditions on the valuation functions of the buyers, there is a unique NEP and the allocation at the NEP is efficient. The prices charged to the buyers at the NEP are bounded above, and can be made arbitrarily close to the market clearing price for price-taking buyers. The relationship to work of Vikrey-Clark-Groves, Johari and Tsitsiklis, and Sanghavi and Hajek is discussed.

Lei Ying (Electrical Engineering University of Illinois at Urbana Champaign) lying@students.uiuc.edu

Global Stability of Internet Congestion Controllers with Heterogeneous Delays (poster session)

This is joint work with G.E. Dullerud and R. Srikant.

We study the problem of designing globally stable, scalable congestion control algorithms for the Internet. Prior work has primarily used linear stability as the criterion for such a design. Global stability has been studied only for single node, single source problems. Here, we obtain conditions for a general topology network accessed by sources with heterogeneous delays. We obtain a sufficient condition for global stability in terms of the increase/decrease parameters of the congestion control algorithm and the price functions used at the links.

Connect With Us: