# On the Competitiveness of Oblivious Routing:
## 7 Conclusions  
Oblivious routing is a possible alternative for adaptive routing strategies when engineering network traffic as it avoids continuous reconfiguration of routing policies. Furthermore, oblivious routing is a promising candidate for minimum-congestion routing in large networks. This is due the fact that it is fundamentally distributed and comes equipped with a hard logarithmic congestion bound. This bound, however, is intrinsically of worst-case nature. In this paper, we took the first steps toward a statistical performance characterization. Our contributions in this regard are three-fold.  
First, we defined new performance metrics, the probability of congestion (PoC) and the expected value of congestion (EVoC), valid for any static routing algorithm. Second, we showed how to evaluate the PoC and the EVoC quantitatively, under the assumption that traffic matrices are uniformly distributed in a demand set \(\Theta\). We believe that this assumption is reasonable, and especially so for the case of oblivious routing, yet we note that the development goes similarly even if the assumption does not hold, but volume computation will generally need to be substituted with integration over convex bodies, a problem of the same computational complexity. Third, we have restated the PoC and the  
Figure 4: The PoC the competitive ratio for (**a**) the directed AS1239 and (**b**) the directed AS6461 topology, as the function of the number of users and number of paths.  
Figure 3: The PoC, the competitive ratio, and the EVoC for the _directed_ version of (**a**) the NSF, (**b**) the AS3257, (**c**) the AS1239, (**d**) the AS6461, the (**e**) AS3967 and (**f**) the AS1755 topology, and _undirected_ version of (**g**) the NSF, (**h**) the AS3257, and (**i**) the AS1755 topology, as the function of the number of users \(K\).  
EVoC as qualitative statistical competitive measures, and we found that competitiveness of oblivious routing vanishes in terms of these measures.  
Our findings, in some part, could be attributed to the strange behavior of volumes in large dimensions that is often referred to as the _curse of dimensionality_. In extremely large dimensions \(\text{Vol}((1+\lambda)P)\) grows very fast with \(\lambda\) for any polytope \(P\), and this causes \(\eta\) to almost surely approach 1 as \(K\to\infty\). Our analytic results, however, indicate that \(\eta\approx 1\) occurs even when the dimension \(K\) is still moderate to be relevant to practice. Moreover, it appears that competitiveness is mostly determined by the number of source-destination pairs, and path diversity has very little impact.  
It is important to emphasize that these results do not qualify oblivious routing _per se._ For once, oblivious routing is optimized for the competitive ratio and not for the PoC or the EVoC, and it is perfectly possible (however improbable) that an algorithm tuned for the PoC would yield better competitiveness. Second, our results are only for the case when no information on anticipated demands is available. Indeed, earlier work [6] showed that, with a suitably precise guess on input traffic, oblivious routing can become highly efficient. However, compared to an optimal adaptive algorithm [13; 14] (which never causes congestion when subjected to a routable demand), oblivious routing (which almost surely does) is not competitive at all. These findings perhaps shed some new light on the age-old static vs. adaptive routing debate as well.  
Finally, it is an open question as to whether it is possible to close the performance gap--measured in terms of the competitive ratio and PoC--between an optimal adaptive routing algorithm and the oblivious routing, by introducing some adaptiveness to the oblivious routing in the form of arbitrary finite routing regions.  
This research received no external funding.  
Not applicable.  
The authors declare no conflict of interest.