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

Abstract

Abstract 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 constant 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 constant 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 (weighted) random routing is not a practical procedure, it enables us to derive a (tight) upper bound for the capacity of the network under more standard routing policies. Using this new expression, we compute network capacity for a sample of demand matrices for some prototypical networks, including uniform demand (one unit between all node pairs) and broadcast demand (one unit between a source node and each other node as destination), and finally derive estimates of the mean load in some asymptotic cases.

Keywords

• Multicommodity flow
• Network load
• Steady state
• Laplacian of a graph
• Laplacian of the demand matrix
• Weighted random walk