Example of an optimal (left) and non optimal (right) path configuration. The optimal is minimizing both traffic congestion and total path length; in the non optimal each user takes its shortest path, causing congestion on some edges.
Large interacting systems are often controlled by local interactions: the state of a variable depends directly only on the state of the surrounding neighborhood. The question is how to exploit this distributed character to optimize the network and in particular, we are interested in the problem of routing optimization.
In communication networks, it is often the case that a network manager (e.g an Internet Service Provider) wants to optimize a global cost function where, ideally, all the network users' communication requests are not only satisfied but also with a guaranteed quality-of-service. This translates in a cost function that penalizes both the total traffic and transmission delay, summed over the users. To study this problem we deploy the distributed formalism of message-passing algorithms borrowing ideas from statistical physics of disordered systems. By exploiting the distributed character of this approach we are able to improve state-of-the-art results both in terms of finding a more optimal solution and in faster time.