Congestion in networks: SOC, HOT and the percolation-fragmentation
phase transition
Here a network is a graph whose edges have prescribed
capacities. We are also given a
demand matrix \(M(v,w)\).
The interpretation is that, simultaneously for all pairs
\((v,w)\), we want to transport a quantity of \(M(v,w)\) units of
stuff per unit time from \(v\) to \(w\) through the network,
with the constraint that the total amount of stuff per unit
time moving along a given edge cannot exceed that edge's capacity.
Of course this is a standard setting, known as
multicommodity flow.
There is a yes/no question: do there exist feasible solutions
at all?
When the answer is yes, one can go on to other questions such as
-
Optimize some other quantities (time, cost) subject to feasibility
- Devise decentralized routing algorithms
- study the queueing network version, where
demand fluctuates randomly in time with expectation M(v,w)
all of which have substantial literature.
But we want to consider the case where the answer is
(barely) no.
In this case there is some total demand
\(D = \sum_{v,w} M(v,w)\)
and we can seek the maximum possible demand that can
be satisfied, that is the maximum
\(D_1\) of \(\sum_{v,w} M_1(v,w)\)
subject to \(M_1(v,w) \leq M(v,w) \)
and to the capacity constraints.
Consider the setting where the network is fixed and the
demand increases, say
linearly with time \(t\), so that
\(M(t) = tM\)
with total demand \(tD\) and maximum satisfied demand \(D_1(t)\).
Then there is a
"marginal satisfiability proportion"
\( r(t) = (1/D) d/dt(D_1(t)) \)
which we expect to decrease with t.
Consider the \(t\) for which \(r(t) = 0.95\), say,
and consider the set \(E(t) \) of edges with spare capacity at that time.
Visualize the network as having a backbone of high-capacity
edges and a periphery of low-capacity links to
degree-1 vertices.
Intuitively, there are two qualitatively different possibilities.
-
Parts of the periphery become congested first.
In this case \( E(t) \) will consist of a single
giant connected component
which comes near almost every vertex,
but where a fraction of vertices are not touched.
- Alternatively, the long-range capacity between some two different
parts of the networks may become congested first.
In this case \(E(t)\) will consist of two large connected components,
touching almost every vertex.
Now these two cases can be distinguished by the behavior of r(t).
In the first case we expect \(r(t)\) to decrease smoothly from 1.
In the second case we expect a rapid decrease from 1 to
some level \(\alpha\) representing the proportion of demand which
does not require passing the congested interface.
But there is a third possibility, which is that both effects
take place simultaneously.
In this case \(E(t)\) changes abruptly from having a single
giant connected component
which comes near almost every vertex,
to consisting of many small components;
and \(r(t)\) will change abruptly from near 1 to near 0.
This behavior is in part analogous to the transition
of percolation clusters
from supercritical to subcritical,
and hence we call it the
percolation-fragmentation phase transition.
For a given network, one expects only a small subset of all
possible demand matrices \(M\) to have this phase transition property.
On the other hand, consider networks which are designed with
some demands in mind, or which evolve in some adaptive way.
For instance
- Given a network and current demand, design the cheapest
network improvement (higher edge capacities) which will handle
twice the current demand. Then consider the behavior of \(r(t) \)
as demand increases in some random way, say
\(M_{v,w}(t) = M X_{v,w}(t) \)
for random \(X_{v,w}(t) \) with mean and variance linear in t,
and let \(t_0 \) be the time when this mean equals 2.
-
Suppose demand increases in some random way, and suppose
we just add capacity to edges in some minimal-cost way
whenever the network becomes congested,
until some time \( t_0 \); then stop adding capacity.
In both cases we expect to see this phase transition around
\(t_0\).
The former could be considered an instance of HOT
(highly optimized tolerance)
and the latter an instance of SOC
(self-organized criticality).
So a broad research project is to study \(r(t)\) in examples.
One can do analytic calculations in very simple networks,
then simulations of artificial networks, then look at
real networks.
But the specific open problem
is to find the right "toy model" in which analytic calculations can be done.
We seek something simple, analogous to the M/M/1 model in queueing theory or to the
Erdos-Renyi random graph model as a model for percolation.
Update (2/18).
Of course there has been a huge literature on networks since 2003, but I have not noticed work
very similar to this.
History.
Problem posted May 2003 and mentioned in subsequent talks.
But no doubt similar questions have been devised by others.
Back to Open Problem list