Grothey, A and Yang, X (2012) Approximate dynamic programming with B�zier Curves/Surfaces for Top-percentile Traffic Routing. European Journal of Operational Research, 218 (3). pp. 698-707. DOI https://doi.org/10.1016/j.ejor.2011.11.041
Grothey, A and Yang, X (2012) Approximate dynamic programming with B�zier Curves/Surfaces for Top-percentile Traffic Routing. European Journal of Operational Research, 218 (3). pp. 698-707. DOI https://doi.org/10.1016/j.ejor.2011.11.041
Grothey, A and Yang, X (2012) Approximate dynamic programming with B�zier Curves/Surfaces for Top-percentile Traffic Routing. European Journal of Operational Research, 218 (3). pp. 698-707. DOI https://doi.org/10.1016/j.ejor.2011.11.041
Abstract
Multi-homing is used by Internet Service Providers (ISPs) to connect to the Internet via different network providers. This study develops a routing strategy under multi-homing 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). Solution approaches based on Stochastic Dynamic Programming require discretization in state space, which introduces a large number of state variables. This is known as the curse of dimensionality in state space. To overcome this, in previous work we have suggested to use approximate dynamic programming (ADP) to construct value function approximations, which allow us to work in continuous state space. The resulting ADP model provides well performing routing policies for medium sized instances of the TpTRP. In this work we extend the ADP model, by using B�zier Curves/Surfaces to obtain continuous-time approximations of the time-dependent ADP parameters. This modification reduces the number of regression parameters to estimate, and thus accelerates the efficiency of parameter training in the solution of the ADP model, which makes realistically sized TpTRP instances tractable. We argue that our routing strategy is near optimal by giving bounds.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Top-percentile pricing; Multi-homing; Stochastic; Routing policy; Approximate dynamic programming; B�zier urves/Surfaces |
Subjects: | Q Science > QA Mathematics |
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: | 06 Nov 2013 11:17 |
Last Modified: | 30 Oct 2024 09:15 |
URI: | http://repository.essex.ac.uk/id/eprint/8271 |
Available files
Filename: ERGO-10-008.pdf