caa a22 4500 445878037 CHVBK 20180317145533.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s11081-010-9130-2 doi (NATIONALLICENCE)springer-10.1007/s11081-010-9130-2 Top-percentile traffic routing problem by dynamic programming [Elektronische Daten] [Andreas Grothey, Xinan Yang] Multi-homing is a technology used by Internet Service Provider (ISP) to connect to the Internet via different network providers. To make full use of the underlying networks with minimum cost, an optimal routing strategy is required by ISPs. This study investigates the optimal routing strategy in case where network providers charge ISPs according to top-percentile pricing. We call this problem the Top-percentile Traffic Routing Problem (TpTRP). The TpTRP is a multistage stochastic optimisation problem in which routing decision should be made before knowing the amount of traffic that is to be routed in the following time period. The stochastic nature of the problem forms the critical difficulty of this study. In this paper several approaches are investigated in modelling and solving the problem. We begin by modelling the TpTRP as a multi-stage stochastic programming problem, which is hard to solve due to the integer variables introduced by top-percentile pricing. Several simplifications of the original TpTRP are then explored in the second part of this work. Some of these allow analytical solutions which lead to bounds on the achievable optimal solution. We also establish bounds by investigation several "naive” routing policies. In the end, we explore the solution of the TpTRP as a stochastic dynamic programming problem by a discretization of the state space. This SDP model gives us achievable routing policies on medium size instances of TpTRP, which of course improve the naive routing policies. With a classification of the SDP decision table, a crude routing policy for realistic size instances can be developed from the smaller size SDP model. Springer Science+Business Media, LLC, 2011 Top-percentile nationallicence Multi-homing nationallicence Mixed-integer stochastic programming problem nationallicence Dynamic programming nationallicence Grothey Andreas School of Mathematics, College of Science and Engineering, The University of Edinburgh, Edinburgh, UK aut Yang Xinan School of Mathematics, College of Science and Engineering, The University of Edinburgh, Edinburgh, UK aut Optimization and Engineering Springer US; http://www.springer-ny.com 12/4(2011-12-01), 631-655 1389-4420 12:4<631 2011 12 11081 https://doi.org/10.1007/s11081-010-9130-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11081-010-9130-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Grothey Andreas School of Mathematics, College of Science and Engineering, The University of Edinburgh, Edinburgh, UK aut NATIONALLICENCE 700 1- Yang Xinan School of Mathematics, College of Science and Engineering, The University of Edinburgh, Edinburgh, UK aut NATIONALLICENCE 773 0- Optimization and Engineering Springer US; http://www.springer-ny.com 12/4(2011-12-01), 631-655 1389-4420 12:4<631 2011 12 11081 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer