# On the Competitiveness of Oblivious Routing:
## 3 Model and Notations
The _feasible region_\(R(\mathcal{S})\) for some \(\mathcal{S}\) describes the set of traffic matrices that can be accommodated in the network by \(\mathcal{S}\) without causing link over-subscription: \(R(\mathcal{S})=\{\theta:\kappa_{\mathcal{S}}(\theta)\leq 1\}\subset\mathbb{R}^{K}\). For a static routing function \(\mathcal{S}\), the feasible region \(R(\mathcal{S})\) is a down-monotone a polytope [13]. We call \(\mathcal{S}\) an _optimal_ routing function if its feasible region coincides with the set of all admissible traffic matrices: \(R(\mathcal{S})\equiv T\). An optimal routing function is guaranteed to exist [13; 14], but it might need to be _adaptive_ (i.e., \(\frac{\partial^{2}\mathcal{S}}{\partial\theta^{2}}\
eq 0\)) and/or _centralized_ (\(k\
eq l\
eq\frac{\partial\mathcal{S}_{k}}{\partial\theta^{2}}=0\)). In contrast to optimal routing, _oblivious routing_ is simple, static, and distributed. Within the context of this paper, we only treat the so-called _congestion minimizing_ version of oblivious routing algorithms, defined as the static routing function \(\mathcal{S}_{\text{0 BL}}\) that minimizes the maximum congestion compared to an optimal routing algorithm \(\mathcal{S}_{\text{opt}}\) over all traffic matrices [23; 24]:  
\[\mathcal{S}_{\text{0 BL}}=\operatorname*{argmin}_{\mathcal{S}}\max_{\theta\in \mathbb{R}^{K}}\frac{\kappa_{\mathcal{S}}(\theta)}{\kappa_{\mathcal{S}_{\text{ opt}}}(\theta)}\;. \tag{1}\] \begin{table}
\begin{tabular}{l l} \hline \(G(V,E)\) & a directed graph, with the set of nodes \(V\) (\(|V|=n\)) and the set of directed \\  & edges \(E\) (\(|E|=m\)) \\ \(c\) & the column \(m\)-vector of edge capacities \\ \((s_{k},d_{k})\) & the set of source-destination pairs (or users) for \(k\in\mathcal{K}=\{1,\ldots,K\}\) \\ \(\mathcal{P}_{k}\) & the set of \(s_{k}\to d_{k}\) paths assigned to some \(k\in\mathcal{K}\) \\ \(p_{k}\) & the number of paths for user \(k\), \(p_{k}=|\mathcal{P}_{k}|\) \\ \(p\) & number of all paths, \(p=\sum_{k\in\mathcal{K}}p_{k}\) \\ \(P_{k}\) & the \(m\times p_{k}\) path-arc incidence matrix for \(\mathcal{P}_{k}\) \\ \(P_{k}^{ij}\) & the row of \(P_{k}\) corresponding to some \((i,j)\in E\) \\ \(up\) & scalar, describing the traffic routed at path \(P\) \\ \(u_{k}\) & a column-vector, whose components are \(u_{P}:P\in\mathcal{P}_{k}\) for some \(k\in\mathcal{K}\) (whether \\  & we mean \(u_{k}\) or \(u_{P}\) will always be clear from the context) \\ \(u\) & a column vector representing a particular choice of \(u_{P}\)s (a “routing”) \\ \(w_{p}\) & weight/delay of path \(p\) \\ \(\theta_{k}\) & the demand/throughput of some user \(k\in\mathcal{K}\) \\ \(\theta\) & a column \(K\)-vector representing a particular combination of throughputs (a “traffic matrix”) \\ \(M\) & flow polytope, the set of path flows corresponding to \(\mathcal{P}\) subject to non-negativity and capacity constraints \\ \(\mathcal{S}\) & a routing function, \(\mathcal{S}:\mathbb{R}^{K}\mapsto\mathbb{R}^{p}\) \\ \(f_{k}\) & traffic splitting ratios for the static routing function of \(k\in\mathcal{K}\) \\ \(1^{T}\) & a row vector whose each coordinate is 1 \\ \(\kappa_{\mathcal{S}}(\theta)\) & maximum link utilization \\ \(T\) & throughput polytope, i.e., the set of traffic matrices realizable in the network \\ \(R(\mathcal{S})\) & the set of demands routable by \(\mathcal{S}\), subject to capacity constraints \\ \hline \end{tabular}
\end{table} 
Table 2: Notations. This definition implicitly fixes the so-called _competitive ratio_\(\alpha(\mathcal{S})=\max_{\theta}\frac{\kappa_{\mathcal{S}}(\theta)}{\kappa_{ \mathcal{S}_{\text{opt}}}(\theta)}\) as _the_ way to measure the performance and the competitiveness of a routing function \(\mathcal{S}\). In the next section, we argue that this performance metric leaves some important performance aspects in obscurity.