# On the Competitiveness of Oblivious Routing:
## 3 Model and Notations  
Let the network topology be given by a directed or undirected graph \(G(V,E)\), let \(n=|V|\) and \(m=|E|\). For simplicity, we shall refer to both the _arcs_\(\{i,j\}\) in directed graphs and the _edges_\((i,j)\) in undirected graphs as _links_, using the notation \((i,j)\). Let the vector of (finite) link capacities be \(c=[c_{ij}>0:(i,j)\in E]\) (see Table 2 for a summary on notations). Users are represented by the set of unique source-destination pairs \((s_{k},d_{k}):k\in\mathcal{K}=\{1,\ldots,K\}\). Let \(\theta_{k}\) denote the momentary demand of the \(k\)th user presented at the source node \(s_{k}\). The vector \(\theta=[\theta_{k}:k\in\mathcal{K}]\) is called a traffic matrix. A convenient way to describe a routing algorithm is through its associated _routing function_\(\mathcal{S}\). In general, a routing function tells how to map a traffic matrix to the links in the network: \(u=\mathcal{S}(\theta)\). Here, \(u\) is a column \(Km\)-vector formed by separate column \(m\)-vectors \(u_{k}\) for each \(k\in\mathcal{K}\), where \(u_{k}=[u_{ij}^{k}:(i,j)\in E]\) describes the amount of flow from \(\theta_{k}\) routed to the link \((i,j)\). The routing function \(\mathcal{S}\) is often decomposed into separate routing functions \(\mathcal{S}_{k}\) for each \(k\in\mathcal{K}\): \(u_{k}=\mathcal{S}_{k}(\theta)\), and for each link \((i,j)\); \(u_{ij}^{j}=\mathcal{S}_{k}^{ij}(\theta)\). For the rest of this paper, we only consider _distributed_, _static_ routing functions \(u_{k}=\mathcal{S}_{k}(\theta)=F_{k}\theta\), where \(\mathcal{S}_{k}\) only depends on \(\theta_{k}\) and \(F_{k}\) is a static \(m\times K\) matrix for each \(k\). The congestion produced by a routing function \(\mathcal{S}\), when subjected to some traffic matrix \(\theta\), is measured by the _maximum link utilization_\(\kappa_{\mathcal{S}}(\theta)\):  
\[\kappa_{\mathcal{S}}(\theta)=\max_{(i,j)\in E}\frac{1}{c_{ij}}\sum_{k\in \mathcal{K}}\mathcal{S}_{k}^{ij}(\theta)\enspace.\] \begin{table}
\begin{tabular}{l l l c} \hline \hline
**Algorithm** & **Properties** & **Complexity** & **Competitive Ratio** \\ \hline [PERSON] [19] & hierarchical decomposition & NP-complete & \(O(\log^{3}n)\) \\ [PERSON] et al. [20] & hierarchical decomposition & polynomial & \(O(\log^{2}n\log\log n)\) \\ [PERSON] [22] & hierarchical decomposition & polynomial & \(O(\log n)\) \\ [PERSON] et al. [24] & LP & polynomial & \(O(\log n)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A summary of oblivious routing algorithms. In the geometric model of [13], a traffic matrix \(\theta_{k}\) corresponds to a point in the \(K\)-dimensional Euclidean space \(\mathbb{R}^{K}\), a routing \(u\) is embedded in the \(Km\)-dimensional Euclidean space \(\mathbb{R}^{Km}\), and the routing function is a mapping from the former space to the latter space. The _throughput_ or _demand polytope_ (Throughout this paper, we will use the term throughput polytope to emphasize that we mean the polytope of all demands routable somehow through the network without any link over-utilization.) \(T\) is defined as the set of traffic matrices \(\theta\) for which there is a routing \(u\) that accommodates \(\theta\) in the network with no link over-utilization: \(T=\{\theta:\exists\mathcal{S}\) so that \(\kappa_{\mathcal{S}}(\theta)\leq 1\}\subset\mathbb{R}^{K}\). Some \(\theta\) is called _admissible_ if \(\theta\in T\). The throughput polytope has the following geometric properties [40]:  
* \(T\) is the intersection of finitely many half-spaces, and thus it is indeed a polytope [43];
* as such, \(T\) is convex: \(\forall\theta_{1},\theta_{2}\in T:\lambda\theta_{1}+(1-\lambda)\theta_{2}\in T\) for all \(\lambda\in[0,1]\);
* under mild regularity conditions, \(T\) is full-dimensional;
* \(T\) is _down-monotone_: for each \(\theta\in T\), it holds that \(\forall 0\leq\tau\leq\theta:\tau\in T\). The second geometric ingredient is the feasible region.