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