Solving the Top-percentile traffic routing problem by Approximate Dynamic Programming

Internet Service Providers (ISPs) have the ability to route their traffic over different network providers. This study investigates the optimal routing strategy under multihoming 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). The TpTRP is a multistage stochastic optimization problem. Routing decision for every time period should be made before knowing the amount of traffic that is to be sent. The stochastic nature of the problem forms the critical difficulty of this study. Solution approaches based on Stochastic Integer Programming or Stochastic Dynamic Programming (SDP) suffer from the curse of dimensionality, which restricts their applicability. To overcome this, we suggest to use Approximate Dynamic Programming, which exploits the structure of the problem to construct continuous approximations of the value functions in SDP. Thus, the curse of dimensionality is largely avoided.