Yang, X and Grothey, A (2012) 'Solving the Top-percentile traffic routing problem by Approximate Dynamic Programming.' IMA Journal of Management Mathematics, 23 (4). pp. 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.

Item Type:	Article
Uncontrolled Keywords:	top-percentile pricing multihoming stochastic routing policy approximate dynamic programming
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 Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor:	Elements
Depositing User:	Elements
Date Deposited:	18 Nov 2014 10:52
Last Modified:	06 Jan 2022 13:40
URI:	http://repository.essex.ac.uk/id/eprint/11686

Actions (login required)

View Item