Probability
and Statistics in Complex Systems: Genomics, Networks, and
Financial Engineering, September 1, 2003 - June 30, 2004
Abstracts:
IMA
Workshop:
March
8-13, 2004
Photo
Gallery Material
from Talks
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)
Slides: pdf
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
Slides: 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
Papers:
HajekGopal.pdf
HajekYang.pdf
SanghaviHajek.pdf
YangHajek.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
Slides: html
pdf
ps
ppt
Paper: pdf
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
Slides: 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
Slides: 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)
Slides: 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.
