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
|
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 |