# On the Competitiveness of Oblivious Routing:
## 6 Numerical Results  
We conducted several rounds of numerical evaluations on various network topologies obtained from real sources to augment the mathematical analysis with practical insights. The goal was to see whether oblivious routing produced the same poor competitiveness in real networks that we identified in the course of the mathematical analysis. In line with this goal, we treated the PoC and the EVoC as competitive measures, and thus we fixed \(\Theta=T\). We ran the first round of evaluations on the ISP data maps from the Rocketfuel dataset [47; 48]. We used the same method as in [24] to obtain approximate POP-level topologies: we collapsed the topologies so that nodes correspond to cities, we eliminated leaf-nodes, and we set link capacities inversely proportional to the link weights. In this paper, only the results for the AS1239, AS3257, AS6461, AS9367, and AS1755 topologies are shown (for more details see Table 3). Another round of evaluations was conducted on the NSFNET Phase II topology [49]. Note that these topologies are inherently directed and symmetric. To facilitate experimenting with undirected networks as well, we obtained undirected versions by substituting each oppositely directed arc with an undirected edge. From these topologies, we generated a series of increasingly more complex configurations by adding gradually more source-destination pairs. Recall that the number of source-destination pairs \(K\) determines the dimensions of the underlying geometric space and thus it has a profound impact on both the PoC and the EVoC. In our experiments, \(K\) was increased from 2 to 30. For each \(K\), fifteen independent samples were generated picking the source and the destination uniformly at random according to bimodal distribution. In every instance, two maximally node-disjoint paths were provisioned per user. We experimented with more paths per user, but the results remained basically the same (see later). For the PoC, we need to obtain the throughput polytope (which is a difficult task in itself [40]), the feasible region, and the volumes thereof. For \(K\leq 9\), we computed the volumes exactly using Vinci [50], and, for the rest of the data points, due to the high complexity of exact volume computation, we used a volume approximation algorithm based on [PERSON] algorithm [51] that was crafted in C++. For the EVoC, we also need to solve a multi-parametric program as mentioned above, for which we used the Multi \begin{table}
\begin{tabular}{c c c c c c c} \hline
**Topology** & **NSF** & **AS1239** & **AS1755** & **AS3257** & **AS3967** & **AS6461** \\ \hline Cities (PoPs) & 12 & 44 & 23 & 50 & 22 & 22 \\ Links & 30 & 83 & 38 & 80 & 37 & 42 \\ \hline \end{tabular}
\end{table} 
Table 3: Network topologies used in the evaluations. The table lists the number cities and inter-city links, which we refer to as PoPs. Parametric Toolbox [52] for Matlab. Finally, the competitive ratio was always computed accurately in Matlab. Figure 3 depicts the exact and approximate results for the PoC, the competitive ratio, and EVoC in four directed and two undirected networks. Our most important observation is that real networks, directed or undirected, exhibited the same worst case competitiveness in terms of the PoC and the EVoC we found earlier analytically. The PoC grows beyond 80% for as few as about 10 users, and as the number of users entered the range of the number of nodes (about 20-30 in our cases), it surpassed 90% and approaches 100% with very high confidence. The EVoC grew beyond 1, indicating symptoms of grave congestion. Recall that this is despite of the fact that an optimal routing algorithm would not produce any congestion at all in these scenarios. This is despite that the competitive ratio remains relatively low (less than 1.5-1.7).