Robust optimization for OSPF routing

Abstract

On OSPF protocol, given a et of weights for each link, the data are routed through the shortest paths between the sender and the receiver. The OSPF weight setting problem consists in defining the assignment of link weights such that the respective shortest path routing results in the least congested network. Most of the works in the literature assume that a single static demand matrix is available. However, the traffic on computer networks may significantly vary in different periods of time, and it is not practical for the network operator to manually change the weights of the links each time significant variation in traffic occurs. These factors motivated the development of optimization models for OSPF weight setting that deal with traffic uncertainties. Instead of minimizing the average congestion over all scenarios as is the case of the works in the literature, we propose a new optimization models, based on Robust Optimization, where the congestion in each scenario is considered individually. We argue that the user experiences each scenario individually. Therefore, a solution that is good on average may sometimes result in a bad quality-of-service from the user point of view. Computational experiments, performed on realistic and artificial instances, show that, compared to the approach that minimizes the average case, our approach is able to reduce the congestion regret by 25%, while increasing the average congestion by only 0,72%, indicating that our approach may be a better alternative for weight setting in OSPF networks.