# On the Competitiveness of Oblivious Routing:
## 5 On the Competitiveness of Oblivious Routing
### Statistical Competitiveness in Undirected Graphs  
Oblivious routing is particularly competitive in undirected graphs in the worst-case sense, thanks to the firm \(O(\log n)\) upper bound on \(\alpha\). In statistical sense, competitiveness seems less appealing. Below, we show that there exist undirected graphs on \(O(n)\) nodes in which \(\eta\) grows as \(1-O(c^{n})\) where \(c<1\) is constant, even though \(\alpha\) is still \(O(1)\). Theorem 5.1: _For any \(K\geq 2\) integer and even, there is an undirected graph on \(2K+4\) nodes with \(\alpha<\frac{3}{2}\) and \(\eta>1-3(0.97)^{K}\)._  
Figure 1: Directed graph (**a**) and polytopes \(T\) and \(R\) for \(K=3\) (**b**) exploiting the high probability of congestion even for competitive ratio less than 2. Proof. : Consider the undirected graph in Figure 2 for any \(K\geq 2\) and even, let all link capacities be \(1\), and let the source-destination pairs be \((s_{k},d_{k}):k\in 0,\ldots,K\). First, we construct the oblivious routing and calculate \(\alpha(K)\) as a function of \(K\), and then we obtain an approximation on \(\eta\). _1. Competitive ratio:_ Along the same lines as above, for the splitting ratios (see Figure 2) we find \(\beta=\frac{1}{2}\) and \(\delta=\frac{3}{K+3}\), and so \(\alpha(K)=\delta+\frac{K\delta}{2}=\frac{3(K+2)}{2(K+3)}\). Observe that \(\alpha<\frac{3}{2}\). _2. The probability of congestion:_ Using the above expressions for \(\beta\) and \(\delta\), the feasible region \(R\) is given by the inequality representation \(R=\{\theta\in\mathbb{R}^{K+1}:0\leq\theta_{i}\leq 2\;\forall 0\leq i\leq K,\; \theta_{j}+\sum_{i=0\
eq j}^{K}\frac{\theta_{i}}{K+3}\leq 2\;\forall 0\leq i\leq K,\;\sum_{i=0}^{K}\frac{3}{K+3}\theta_{i}\leq 2\;\}\), and the throughput polytope \(T\) can be written as:  
\[T=\{\theta\in\mathbb{R}^{K+1}: 0\leq\theta_{i}\leq 2 \forall 0\leq i\leq K \tag{9}\] \[\sum_{i=0}^{K}\theta_{i}\leq K+2\quad\} \tag{10}\]  
Here, again, instead of calculating the volumes directly we take lower and upper approximations. Define \(R^{\prime}\) as \(R^{\prime}=\{\theta\in\mathbb{R}^{K+1}:0\leq\theta_{i}\leq 2\;\forall 0\leq i\leq K,\; \theta_{j}+\sum_{i=0\
eq j}^{K}\frac{\theta_{i}}{K+3}\leq 2\;\forall 0\leq i\leq K\}\). Clearly, \(R^{\prime}\) is obtained from \(R\) by excluding a valid inequality, and thus \(R^{\prime}\supseteq R\). We derive the volume of \(R^{\prime}\) by enumerating its extreme points and then obtaining a triangulation. The extreme points of \(R^{\prime}\) can be written as \(\{\theta_{L}h_{L}^{\pi(L)}\}\), where \(\theta_{L}=\frac{2(K+3)}{K+3+L}\) for all \(L\in\{0,\ldots,K\}\) and \(h_{L}^{\pi(L)}\) is the \(\pi(L)\)-th permutation of the \([1,\ldots,1,0,\ldots,0]^{T}\) vector containing exactly \(L+1\) ones. We observe that the set \(\{h_{L}^{\pi(L)}\}_{L\in\{0,\ldots,K\}}\) together with the origin gives precisely the extreme points of a unit hypercube of dimension \(K+1\). Any \((K+1)\)-dimensional hypercube can be split into \((K+1)!\) simplices, and, as \(R^{\prime}\) is structurally equivalent to such a \((K+1)\)-dimensional hypercube, this gives a valid triangulation for \(R^{\prime}\) as well. The volume of a simplex in our triangulation is given by \(\frac{1}{(K+1)! }|\det(\theta_{0}h_{L}^{\pi_{0}}\;\ldots\;\theta_{K}h_{K}^{ \pi_{K}})|=\prod_{L=0}^{K}\theta_{L}\frac{1}{(K+1)! }|\det(h_{0}^{\pi_{0}}\; \ldots\;h_{K}^{\pi_{K}})|=\prod_{L=0}^{K}\theta_{L}V_{i}\), where \(V_{i}\) is the volume of the \(i\)th simplex. The volume of \(R^{\prime}\) is obtained by summing the volumes of these simplices: \(\text{Vol}(R^{\prime})=\sum_{i}\prod_{L=0}^{K}\theta_{L}V_{i}=\prod_{L=0}^{K} \theta_{L}\sum_{i}V_{i}=\prod_{L=0}^{K}\theta_{L}\). Here, the last equation comes from the fact that \(\sum_{i}V_{i}\) is exactly the volume of the unit hypercube. The volume of \(T\) can be derived similarly. Let \(\theta_{L}^{*}h_{L}^{\pi(L)}\) be defined as the intersection of the directions \(h_{L}^{\pi(L)}\) with the boundary of \(T\) and define \(T^{\prime}\) as the convex hull of these points plus the origin.