‘ On Earth Day at 1990 , New York City’s Transportation Commissioner decided to close 42d Street , which as every New Yorker knows is always congested. “Many predicted it would be doomsday,” said the Commissioner, Lucius J. Riccio. “You didn’t need to be a rocket scientist or have a sophisticated computer queuing model to see that this could have been a major problem.”

But to everyone’s surprise, Earth Day generated no historic traffic jam. Traffic flow actually improved when 42d Street was closed.

To mathematicians, this may be a real-world example of Braess’s paradox, a statistical theorem that holds that when a network of streets is already jammed with vehicles, adding a new street can make traffic flow even more slowly. Seeking Out a New Street

The reason is that in crowded conditions, drivers will pile into a new street, clogging both it and the streets that provide access to it. By the same token, removing a major thoroughfare may actually ease congestion on the streets that normally provide access to it. And because other major streets are already overcrowded, diverting still more traffic to them may not make much difference. ‘

I took the above part from NYTimes article which is published in 1990.It is listed in the references.

I will show you the routing protocol behavior which is used in today networks and try to see whether Braess’s paradox is apply for them. Before going into routing protocol behavior detail, let me explain the Braess paradox with the below picture.

In the figure above , T is the load. 40 and 45 is the time to go from point A to END and Start to point B respectively. Start to A and B to END delay is changing based on the traffic load. Assume A to B link is not there; we will add it later and see the behavior.

If A-B link is not there, Start-A-END path takes the same time with Start-B-END path. So 4000 driver can use the both paths. Start-A-END will take 2000/100 + 45 = 65 minutes. Start-B-END will be 45 + 2000/100 = 65 minutes as well.

Now assume path from A to B is added with the 1 min (very low latency) travel time. And the drivers heard this new path. In this situation, all drivers will choose the Start-A route rather than the Start-B route, because Start-A will only take 4000/100 = 40 minutes at its worst, whereas Start-B is guaranteed to take 45 minutes.

When they reach to point A, since it is only 1 min all the drivers will choose A-B path. Because A-END will take 45 minutes, A-B-END will take 1 + 4000/100 = 41minutes.

If we calculate new path, Start-A-B-End is 4000/100 + 1 + 4000/1 = 81 minutes. We see that if the drivers would communicate before to not to use A-B link and used both paths (Start-A-END, Start-B-END) , they would only travel 65 minutes rather than 81 minutes. Now even one driver thinks at point A that if He goes from point A to END, total travel time will be 85 minutes since He spent 40 minutes to reach to point A from Start.

**Analyze:**

If we analyze the behavior, from Start to A and from B to END, delay is not fixed value, it changes based on load. From A to END and From Start to B, delay is fixed and it is not changing based on load. Changing the delay with the increase load can be explained with bandwidth attribute. If you have enough bandwidth which can be thought as enough line on the road for the cars, so delay can stay as constant, but bandwidth is not sufficient, due to congestion, delay will increase. (There is always fixed propagation delay though due to distance)

Let’s analyze whether Braess Paradox occurs for EIGRP and OSPF without going too much technical detail. For those who want to discuss technical aspects of them or other protocols behavior, comments are always welcome.

**OSPF :**

OSPF uses link bandwidth for its path selection. Metric is derived from the bandwidth and every link bandwidth is known by every node, then nodes can calculate end to end path while adding all the link bandwidth to the equation since they have full visibility. Assume all the link bandwidth is the same between every points.

At the Start point , cars would know if they go Start-A-END and Start-B-END will take same amount of time to pass, so half of the driver go from top path, half of them go from bottom path. When you add A-B path, OSPF would remove it from the SPF tree since it makes the total metric (Derived from bandwidth) higher.

**EIGRP : **

EIGRP is different than OSPF. It uses bandwidth and delay for metric calculation. It uses the minimum bandwidth and total end to end delay for the calculation. There is no full visibility, if node has two paths the destination it calculates the best and sends it to upstream device.

In this example Point A has two paths to the END after adding A-B path, which is A-END and A-B-END. We assumed all the bandwidth is the same, and total delay will be important to decide the best path.In the example above A-END and A-B paths have fixed delay; B-END path delay is changing based on load. But EIGRP doesn’t use load for the metric calculation. Delay is always fixed and derived from the interface bandwidth. EIGRP delay doesn’t change based on load or any other attribute. That is why, delay will be two times higher on A-B-END path, compare to A-END.

Point A will send the information to Start point that it can reach to END through A-END path. Same calculation and path announcement is also true for Point B. Point B will send only Point B-END path to Start point. EIGRP draft specifies 5 attributes for metric calculation and one of them is load. But in the actual implementation, EIGRP only uses bandwidth and delay which are also known as K1 and K3 attributes. If EIGRP would use load as well and change the delay based on load automatically, then Braess Paradox would occur.

**References:**

Umair Hoodbhoy says

September 1, 2014 at 7:11 pmMore than acting selfishly, it is an assumption that everyone else acts rationally. But in reality not everyone acts rationally and as a result you have inconsistent behaviors. If you could factor for the decision making process of drivers accurately, you could do fairly well in reducing the total drive time. Of course routing protocols will use metrics to act rational and enforce consistency.

Orhan Ergun says

September 2, 2014 at 8:13 amI see your point and it is true but, since everyone individually acts rationally it creates this paradox. If all the drivers would agree in the first place to not to use the short path ( A-B ), like collective rationality , then we wouldn’t see this behavior at all.

For the routing protocol, at least for EIGRP we could see the behavior if EIGRP would take load also into consideration for metric calculation, and change the delay based on load , Braess paradox would occur.We discussed this behavior with Donnie Savage who is the EIGRP author, and yes even once load reaches 4500 drivers , load balancing would occur between A-END and A-B-END.

Thanks for reading this boring article by the way 🙂