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

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.

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

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.

History. Problem posted May 2003 and mentioned in subsequent talks. But no doubt similar questions have been devised by others.