Internet traffic is as succeptible to Braess’ paradox as is vehicle traffic. Kagan Tumer and David H. Wolpert at NASA Ames Research Center present an improvement to greedy internet traffic routing algorithms in their paper “Avoiding Braess’ Paradox through Collective Intelligence”.

We have talked about how imposing rules from outside the system can help improve performance in a Braess’ paradox situation. What Tumer and Wolpert’s work adds to the theory is the possibility that in fact local rules can also help to alleviate the effect of Braess’ paradox on global performance.

Tumer and Wolpert first show that Shortest Path Algorithms (SPAs), which each router on the internet uses to attempt to minimize the latency of packets it sends through the network, lead to Braess’ paradox situations just as individual drivers trying to minimize their travel time does so in road networks, when the load on the network is relatively high. They then propose a routing algorithm based on the COIN (COllective INtelligence) concept that allows individual nodes to make independent routing decisions which result in improved traffic flow over the entire network. Their algorithm operates under the restriction that the private utility of each node increases if and only if the world utility (analogous to social welfare in market networks) also increases [Tumer 10, 11]. In essence, their algorithm makes each node in the network value its choices of routing paths according to how using each path will benefit performance of the network as a whole, rather than just benefitting (in the short run) the performance of the individual node. Each node in the network ‘learns’ which routing paths are most beneficial to the global system using a fairly simple machine learning algorithm.

Tumer and Wolpert’s algorithm does not necessarily find the optimal routing configuration for a given network (which is a difficult problem in general). However, it does succeed in avoiding Braess’ paradox in situations where the greedy algorithm fails to–often with a significant increase in performance. In cases where adding an extra route to the network causes latency to increase significantly using the greedy routing algorithm, with the COIN algorithm there is often little or no increase in latency, and in some cases even a significant drop in latency–in effect, the algorithm has become smart enough to not fall into Braess’ paradox situations.

Whether to use top-down regulations or ‘intelligent’ local rules to avoid Braess’ paradoxes seems to depend on the nature of the network you are investigating. For internet traffic, local rules are much preferred because of the decentralized nature of the internet–there is no central authority (at least not yet) to tell internet servers how to route their traffic, and even if there was, its regulatory influence would be subject to the same problems as any other internet traffic. For road traffic, however, transportation authorities often have good control of the roadways and a bird’s-eye-view of the network, and so can much more effectively make decisions for traffic flows than can individual drivers, whose only thoughts are “I need to get to work!”.