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


Download (348kB) | Preview


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 > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 06 Nov 2013 11:17
Last Modified: 06 Jan 2022 13:40

Actions (login required)

View Item View Item