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. DOI https://doi.org/10.1093/imaman/dps002
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. DOI https://doi.org/10.1093/imaman/dps002
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. DOI https://doi.org/10.1093/imaman/dps002
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 > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 18 Nov 2014 10:52 |
Last Modified: | 23 Oct 2024 04:59 |
URI: | http://repository.essex.ac.uk/id/eprint/11686 |
Available files
Filename: ERGO-10-003.pdf