Braess’s Pardox and Its Real-World Implications
In class, we learned about the interesting phenomenon of Braess’s Paradox, a case where an additional connection between to things, say roads to destinations, increased latency or wait time despite the increased overall capacity of the links. The classic example that was used, was that the addition of a bridge to a destination actually increased capacity, but not much detail was gone into discussing just how prevalent this problem can be. So, is Braess’s Paradox simply an intellectual curiosity, or is it truly a real world problem. In this blog post, we will dig deeper on the material covered in class and see its real world application and implications, especially in the networking field and what this implies for designers of networks.
Braess’s Paradox was discovered in 1968 and has since generated a great deal of research, particularly in transportation, networking, and theoretical computer science. Interestingly, little is known about whether or not this paradox is simply a pathological case. From an empirical standpoint, there has only been small anecdotal “evidence” that such a paradox occurs. But, let’s think larger for a second. Rather than thinking from the classical transportation framework, of which there are far fewer links, think about this paradox from a networking (internet networking that is) perspective. Surely, there are far more internet routing routes than there are roads. What happens to Braess’s Paradox, when the number of connections to nodes increases?
Unfortunately, a study conducted at Harvard University in 2008, found that as the number of nodes increases towards infinity, the probability of Braess’s Paradox increases to 1. In terms of roads, this isn’t too bad; it is infeasible that we will ever have enough roads for Braess’s Paradox to present itself as a problem. But from a networking perspective, this finding is chilling since it states that the more connections we have between routers (the nodes), the more likely it is that we run into an instance where overall latency is increased. The problem? The amount of people using the Internet is increasing, as is the Internet itself. In fact, Cisco expects that the amount of Internet traffic by 2015 (conducted in 2012) will approach one zettabyte (1ZB). For comparisons sake, 1ZB is 1,000,000,000,000 times larger than 1GB. As traffic increases, the necessity for more links and nodes (routers) will be needed. This will, in turn, increases the probability of Braess’s Paradox. To make things even worse, the Harvard article makes an even stronger claim: There is a constant p > 1 such that, with high probability as n approaches infinity, there is a choice of traffic rate such that the Braess’s ratio of a random network is at least ρ. What does this mean? It means that removing edges can improve latency by a constant factor. Moreover, greedy algorithms are also used in network routing, for example finding the locally closest neighbor, to route to transmit packets faster, so as the internet grows larger, this paradox will become a problem, and an ever increasing one at that.
However, there is hope; Braess’s Paradox primarily occurs when the user is selfish, that is, each user acts solely for his/her own gain. Since much of Internet routing is done by complex algorithms to maximize flow across the network, Braess’s appearance can be minimized. Moreover, a study conducted in 2010 indicated that as demand increases Braess’s Paradox tends to disappear. However, this particular study was in physical roads and it is not evident whether or not the same result will transfer over to routing networks. Even better, the author of the 2008 study came to the conclusion that Braess’s Paradox only occurs over a certain range of traffic rate, and this range is not particularly large.
As for the people designing the algorithms to maintain Internet traffic, they have a hard job coming up. The best way to minimize the chances for Braess’s Paradox is to maximize flow globally rather than locally. However, this is harder than it seems, especially as the number of node increases. It is far easier to choose the best next node from a local perspective than a global perspective, especially as more nodes are created.
Hopefully, by now, the reader has been convinced that Braess’s Paradox is not simply an intellectual curiosity, but a problem that will reveal itself soon, especially as the internet grows even larger. But if the reader is still not convinced, here are some additional instances where the paradox unexpectedly occurs:
In social networks:
– http://www.technologyreview.com/view/510801/braess-paradox-infects-social-networks-too-say-computer-scientists/
In power grids:
– http://phys.org/news/2012-10-power-grid-blackouts-braess-paradox.html
In material science:
– http://www.technologyreview.com/view/428492/how-to-make-a-metamaterial-that-expands-under-pressure-and-contracts-in-tension/
It certainly makes one wonder, what will we, as a collective whole, do as usage, population, etc. increases? Additional edges and links will decrease overall capacity, yet more capacity is needed. Indeed, Braess’s Paradox will become a big deal in the near future, and one that we need to figure out a way to counteract soon.
Additional References:
– http://www.brandignity.com/2012/02/just-how-fast-is-the-internet-growing-infographic/
– http://phys.org/news203665202.html
– http://www.eecs.berkeley.edu/~gvaliant/papers/rbp_full.pdf