Optimal networks, congestion and Braess' paradox

Networks that are efficient and robust to failures tend to have either star-like or homogeneous structures in their connectivity. The choice of optimal structure depends on the network's load. The results presented in this paper are: (a) For source-routing networks the change from one structure to another is smooth and does not depends on network congestion. (b) The addition of extra links to the optimal network reduces its overall performance. This performance deterioration is small if the network structure has a narrow degree distribution centred around the mean. (c) If the network has a subset of nodes, which are more efficient in the delivery of traffic, the optimal network has a tier structure.