Oblivious Routing for Networks With Dual Uncertainties in Demand and Capacity

Abstract

The Oblivious Routing (OR) problem seeks to determine a static routing strategy that minimizes the worst-case network performance under uncertain traffic demands. Most existing studies assume fixed link capacities and consider uncertainty only in traffic demand. However, in many practical networks, particularly wireless and satellite networks, link capacities are also subject to significant fluctuations. This paper investigates a generalized OR problem that explicitly accounts for uncertainties in both traffic demand and link capacity. We formulate the problem as a nonlinear programming (NLP) model and then transform it into an equivalent linear programming (LP) formulation, enabling efficient computation of the routing solution. Extensive experiments on benchmark networks and randomly generated topologies demonstrate the effectiveness of the proposed approach. Compared with the conventional OR model that assumes fixed link capacities, the proposed capacity-variation-aware routing consistently achieves lower worst-case link utilization under capacity uncertainty while maintaining practical computation times. In the evaluated scenarios, the proposed method achieves an improvement ratio of up to 211% compared to the traditional OR approach.