Yang, X and Grothey, A (2012) 'Solving the top-percentile traffic routing problem by approximate dynamic programming.' IMA Journal of Management Mathematics, 23 (4). 413 - 434. ISSN 1471-678X

Preview

Text ERGO-10-003.pdf Download (295kB) | Preview

Abstract

Internet Service Providers (ISPs) have the ability to route their traffic over different network providers. This study investigates the optimal routing strategy under multihoming in the case where network providers charge ISPs according to top-percentile pricing (i.e. based on the θth highest volume of traffic shipped). We call this problem the Top-percentile Traffic Routing Problem (TpTRP). The TpTRP is a multistage stochastic optimization problem. Routing decision for every time period should be made before knowing the amount of traffic that is to be sent. The stochastic nature of the problem forms the critical difficulty of this study. Solution approaches based on Stochastic Integer Programming or Stochastic Dynamic Programming (SDP) suffer from the curse of dimensionality, which restricts their applicability. To overcome this, we suggest to use Approximate Dynamic Programming, which exploits the structure of the problem to construct continuous approximations of the value functions in SDP. Thus, the curse of dimensionality is largely avoided. The authors 2012. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.2012 © The authors 2012. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.

Item Type:	Article
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Z Bibliography. Library Science. Information Resources > ZA Information resources > ZA4050 Electronic information resources
Divisions:	Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User:	Jim Jamieson
Date Deposited:	18 Nov 2014 10:52
Last Modified:	04 Feb 2019 23:15
URI:	http://repository.essex.ac.uk/id/eprint/11686

Actions (login required)

View Item