An analytical solution to the multicommodity network flow problem with weighted random routing

We derive an analytical expression for the mean load at each node of an arbitrary undirected graph for the non-uniform multicommodity flow problem under weighted random routing. We show the mean load at each node, net of its demand and normalized by its (weighted) degree, is a common multiplier equal to the trace of the product of two matrices: the Laplacian of the demand matrix and the generalized inverse of the graph Laplacian. For the case of uniform demand, this common multiplier reduces to the sum of the inverses of the non-zero eigenvalues of the graph Laplacian. We note that such a closed-form expression for the network capacity for the general multicommodity network flow problem has not been reported before and even though random routing is not a practical procedure, it enables derivation of a tight upper bound for the capacity of the network under more standard routing policies. Using this said expression, we compute network load for a sample of demand matrices for some prototypical networks, including the uniform demand (same between all node pairs) and broadcast demand (one source node and all other nodes as destinations) and finally derive estimates of the mean load in some asymptotic cases.