Edinburgh Research Explorer

Approximate dynamic programming with Bezier Curves/Surfaces for Top-percentile Traffic Routing

Research output: Contribution to journalArticlepeer-review

Related Edinburgh Organisations

Original languageEnglish
Pages (from-to)698-707
Number of pages10
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 May 2012


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 0th 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 Bezier 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. (C) 2011 Elsevier B.V. All rights reserved.

    Research areas

  • Top-percentile pricing, Multi-homing, Stochastic, Routing policy, Approximate dynamic programming, Bézier Curves/Surfaces

Download statistics

No data available

ID: 1875479