Optimization Online


Approximate Dynamic Programming with Bezier Curves/Surfaces for Top-percentile traffic routing

Xinan Yang(s0677435***at***sms.ed.ac.uk)
Andreas Grothey(a.grothey***at***ed.ac.uk)

Abstract: Multi-homing is used by Internet Service Provider (ISP) to connect to the Internet via different network providers. This study investigates the optimal routing strategy under multi-homing in the case where network providers charge ISPs according to top-percentile pricing (i.e. based on the $\theta$-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. To overcome this we suggested to use Approximate Dynamic Programming (ADP) to construct approximations of the value function in previous work, which works nicely for medium size instances of TpTRP. In this work we keep working on the ADP model, use Bezier Curves/Surfaces to do the aggregation over time. This modification accelerates the efficiency of parameter training in the solution of the ADP model, which makes the real-sized TpTRP tractable.

Keywords: top-percentile pricing, multi-homing, stochastic, routing policy, approximate dynamic programming, Bezier Curves/Surfaces

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Other Topics (Dynamic Programming )

Citation: Technical Report ERGO 10-008, School of Mathematics, University of Edinburgh, Dec/2010.

Download: [PDF]

Entry Submitted: 01/05/2011
Entry Accepted: 01/05/2011
Entry Last Modified: 01/05/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society