# On the Competitiveness of Oblivious Routing:
###### Abstract  
Oblivious routing is a static algorithm for routing arbitrary user demands with the property that the competitive ratio, the proportion of the maximum congestion to the best possible congestion, is minimal. Oblivious routing turned out surprisingly efficient in this _worst-case_ sense: in undirected graphs, we pay only a logarithmic performance penalty, and this penalty is usually smaller than 2 in directed graphs as well. However, compared to an optimal adaptive algorithm, which never causes congestion when subjected to a routable demand, oblivious routing surely has congestion. The open question is of how often is the network in a congested state. In this paper, we study two performance measures naturally arising in this context: the probability of congestion and the expected value of congestion. Our main result is the finding that, in certain directed graphs on \(n\) nodes, the probability of congestion approaches 1 in some undirected graphs, despite the competitive ratio being \(O(1)\). oblivious routing; performance evaluation; theoretical and numerical analysis; polytopes; geometry +
Footnote †: : 2021: 11, 9408. [[https://doi.org/10](https://doi.org/10)]([https://doi.org/10](https://doi.org/10)). extensive simulations on real and synthetic topologies revealed that its value usually remains under 2 [24]. Recently, oblivious routing was combined with other approaches; semi-oblivious and hybrid traffic engineering solutions were developed and investigated [27; 28; 29; 30]. Thus, a deep understanding of the oblivious routing and the analysis of its performance with the competitive ratio might be an important step towards better traffic engineering solutions. Under the hood, the competitive ratio is a worst case metric, conveying the impression that, if its value is low, then we can expect the worst case congestion to manifest over only a small fraction of the traffic matrices and most \"normal\" traffic matrices will be routed with no congestion at all. In this paper, we ask to what extent this intuitive worst-case performance characterization remains valid in a broader statistical sense. We introduce two new routing performance metrics. The _probability of congestion_ (PoC) describes the probability that, over a given demand, distribution congestion shows up somewhere in the network. Easily, if the PoC approaches 1, the network spends most of the time in a congested state. The second metric, the _expected value of congestion_ (EVoC), quantifies the anticipated extent of congestion. We argue that the PoC and the EVoC are revealing statistical performance measures for general static routing algorithms as well as for oblivious routing itself. Not only are they useful as _absolute_ performance metrics but also an appealing _relative_ interpretation also exists. In this setting, traffic matrices are picked uniformly from the set of traffic matrices routable without congestion in the network, and we characterize the competitiveness of oblivious routing by comparing the PoC and the EVoC to those attainable by an optimal routing algorithm. As a main contribution of the paper, we show that the performance penalty of oblivious routing can become arbitrarily large in this sense. In particular, we show that the PoC for oblivious routing grows as \(1-O(\frac{1}{n})\) in certain directed graphs on \(n\) nodes and in some undirected graphs it approaches 1 with \(1-O(c^{n})\), \(c<1\), and this can occur even when the competitive ratio is only \(O(1)\) (in particular, 2 in the first case and 1.5 in the second). In the second part of the paper, numerical evaluation of real life topologies are shown suggesting that the PoC and the EVoC indeed exhibit the worst-case behavior that we identified analytically. The rest of the paper is organized as follows. Related literature is surveyed in Section 2. Then, in Section 3, we recall the geometric framework from [13], and formal definitions for the PoC and the EVoC as well as methods to evaluate them are provided in Section 4.