Robust delay-constrained routing in telecommunications

Hijazi, Hassan; Bonami, Pierre; Ouorou, Adam
July 2013
Annals of Operations Research;Jul2013, Vol. 206 Issue 1, p163
Academic Journal
In telecommunications, operators usually use market surveys and statistical models to estimate traffic evolution in networks or to approximate queuing delay functions in routing strategies. Many research activities concentrated on handling traffic uncertainty in network design. Measurements on real world networks have shown significant errors in delay approximations, leading to weak management decisions in network planning. In this work, we introduce elements of robust optimization theory for delay modeling in routing problems. Different types of data uncertainty are considered and linked to corresponding robust models. We study a special case of constraints featuring separable additive functions. Specifically, we consider that each term of the sum is disturbed by a random parameter. These constraints are frequent in network based problems, where functions reflecting real world measurements on links are summed up over end-to-end paths. While classical robust formulations have to deal with the introduction of new variables, we show that, under specific hypotheses, the deterministic robust counterpart can be formulated in the space of original variables. This offers the possibility of constructing tractable robust models. Starting from Soyster's conservative model, we write and compare different uncertainty sets and formulations offering each a different protection level for the delay constrained routing problem. Computational experiments are developed in order to evaluate the 'price of robustness' and to assess the quality of the new formulations.


Related Articles

  • Mathematical programming approaches for dual multicast routing problem with multilayer risk cost. Liang, Zhe; Lee, Chungmok; Chaovalitwongse, W. // Annals of Operations Research;Mar2013, Vol. 203 Issue 1, p101 

    This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to...

  • A cross-layer QoS-aware optimization protocol for guaranteed data streaming over wireless body area networks. Ababneh, Nedal; Timmons, Nicholas; Morrison, Jim // Telecommunication Systems;Feb2015, Vol. 58 Issue 2, p179 

    In this paper, we study the problem of routing, bandwidth and flow assignment in wireless body area networks (BANs). We present an adaptive joint routing and bandwidth allocation protocol for traffic streaming in BAN. Our solution considers BAN for real-time data streaming applications, where...

  • Robust Optimization of Schedules Affected by Uncertain Events. Vujanic, Robin; Goulart, Paul; Morari, Manfred // Journal of Optimization Theory & Applications;Dec2016, Vol. 171 Issue 3, p1033 

    In this paper, we present a new method for finding robust solutions to mixed-integer linear programs subject to uncertain events. We present a new modeling framework for such events that result in uncertainty sets that depend parametrically on the decision taken. We also develop results that can...

  • Optimal Traffic Re-Grooming rooming Model for Heterogeneous Carrier Ethernet Services over WDM Optical Network. Resendo, Leandro Colombi // Journal of Microwaves, Optoelectronics & Electromagnetic Applica;Dec2013, Vol. 12 Issue 2, p628 

    This paper proposes three novel integer linear programming (ILP) formulations, where the first model deals with the Grooming, Routing, Wavelength Assignment, and Carrier Ethernet Interface Allocation Problem (GRWA-I); the second to Traffic Re-Grooming Problem (TRGP) to accommodate demand changes...

  • A Self-Learning Particle Swarm Optimization for Robust Multi-Echelon Capacitated Location–Allocation–Inventory Problem. Tirkolaee, Erfan Babaee; Mahmoodkhani, Javad; Bourani, Mehdi Ranjbar; Tavakkoli-Moghaddam, Reza // Journal of Advanced Manufacturing Systems;Dec2019, Vol. 18 Issue 4, p677 

    This paper addresses a multi-echelon capacitated location–allocation–inventory problem under uncertainty by providing a robust mixed integer linear programming (MILP) model considering production plants at level one, central warehouses at level two, and the retailers at level three...

  • Synchronized routing of active and passive means of transport. Meisel, Frank; Kopfer, Herbert // OR Spectrum;Mar2014, Vol. 36 Issue 2, p297 

    This paper addresses a routing problem where the fulfillment of transport requests requires two types of transport resources, namely, passive and active means of transport. The passive means are used for holding the cargo that is to be shipped from pickup to delivery locations. The active means...

  • Multi-product Capacitated Single-Allocation Hub Location Problems: Formulations and Inequalities. Correia, Isabel; Nickel, Stefan; Saldanha-da-Gama, Francisco // Networks & Spatial Economics;Mar2014, Vol. 14 Issue 1, p1 

    In this paper we extend the classical capacitated single-allocation hub location problem by considering that multiple products are to be shipped through the network. We propose a unified modeling framework for the situation in which no more than one hub can be located in each node. In...

  • Exact approach to reliability of wireless mesh networks with directional antennas. Żotkiewicz, Mateusz; Pióro, Michał // Telecommunication Systems;May2014, Vol. 56 Issue 1, p201 

    The paper is devoted to modeling and optimization of reliable wireless mesh networks that employ directional antennas. We introduce two mixed-integer programming formulations that allow to simultaneously characterize routing patterns and transmission schedules. The first model allows for...

  • A MIXED INTEGER-PROGRAMMING MODEL FOR PERIODIC ROUTING OF SPECIAL VESSELS IN OFFSHORE OIL INDUSTRY. Jahromi, Abdolhamid Eshraghniaye; Yazdeli, Roohollah Ighani // International Journal of Industrial Engineering;2015, Vol. 22 Issue 5, p524 

    In order to maintain the production of offshore oil wells, the National Iranian Oil Company periodically services facilities and equipment located in oil wellheads with mobile wellhead servants. It also gives technical supports to oil wellheads and mobile wellhead servants with supporter...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics