# On the Competitiveness of Oblivious Routing:
## 2 Related Work  
Oblivious routing is an attractive paradigm for networks, where centralized control or frequent reconfigurations are infeasible or unacceptable. It is the answer for the question, how to route the traffic, without a priori knowledge of the traffic demand.  
One of the first results on oblivious routing dates back to the 1980s, when [PERSON] and [PERSON] studied oblivious routing on hypercubes [18]. Their randomized scheme has the competitive ratio \(O(\log n)\), where \(n\) is the number of nodes in the network. Despite the first early results, the breakthrough came only in 2002, when [PERSON] showed that, for generic undirected graphs, the maximum congestion is within a \(O(\log^{3}n)\) factor of the lowest possible congestion [19]. This result was non-constructive, and the running time of the algorithm's precomputation phase was exponential.  
In the next years, the competitive ratio and the complexity of the algorithms was subsequently improved by [PERSON], [PERSON] and [PERSON] [20], and later by [PERSON] [22] from \(O(\log^{3}n)\) to \(O(\log^{2}n\log\log n)\) and to \(O(\log n)\), respectively (see Table 1). It was also shown that [PERSON]'s \(O(\log n)\) bound is asymptotically tight as there are networks on which no oblivious routing algorithm exists with sub-logarithmic competitive ratio [31; 32]. However, for directed graphs, no logarithmic congestion guarantee exists [23].  
Meanwhile, algorithms were proposed to solve the oblivious routing problem in polynomial time, most notably the LP formulation given by [PERSON] et al. [24]. Their numerical evaluations also suggest that the competitive ratio in most real-world network topologies is 2 or less: in contrast the \(O(\log n)\) overprovisioning suggested by [PERSON]'s worst-case result, it is sufficient to overprovision the capacity of each edge of the network by a factor not more than 2.  
Oblivious routing algorithms require routing tables polynomial in the network size. [PERSON] and [PERSON] designed an oblivious routing schemes that only requires small routing tables (polylogarithmic tables in the network size) and, at the same time, still guarantees a close-to-optimal load [33].  
However, oblivious routing is a well-studied problem for traffic engineering on the Internet [34; 35; 36; 37], due to its ability to avoid continuous route reconfiguration, it has found its place in the wireless world, as well [38; 39].  
[PERSON] et al. were the first ones to systematically study the geometric properties of various routings [13; 40; 41; 42]. They showed that, under reasonable regularity conditions, the set of demand combinations a capacitated graph admits (the so-called throughput polytope), and the set of demands a routing can place in the network without congestion (the feasible region), are compact, down-monotone, \(K\)-dimensional polyhedra, where \(K\) is the number of source-destination pairs.  
They used this geometric view to study fair allocation of network resources in a routing-independent manner [40] and to develop new, hybrid distributed-centralized semi-oblivious routing algorithms [13]. Nevertheless, no attempts have been made to convert this geometric framework into a comprehensive performance characterization for oblivious routing this far.