Research Repository

Approximate dynamic programming with Bézier Curves/Surfaces for Top-percentile Traffic Routing

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). 698 - 707. ISSN 0377-2217

[img]
Preview
Text
ERGO-10-008.pdf

Download (348kB) | Preview

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. © 2011 Elsevier B.V. All rights reserved.

Item Type: Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Jim Jamieson
Date Deposited: 06 Nov 2013 11:17
Last Modified: 04 Feb 2019 23:15
URI: http://repository.essex.ac.uk/id/eprint/8271

Actions (login required)

View Item View Item