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 θ-th highest volume of traffic shipped). We call this problem the Top-percentile Traffic Routing Problem (TpTRP). The TpTRP is a multi-stage stochastic optimisation problem in which routing decision should be made before knowing the amount of traffic that is to be shipped in the following time period. The stochastic nature of the problem forms the critical difficulty of the problem.
Solution approaches based on Stochastic Integer Programming (SIP) techniques 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 (ADP) which exploit the structure of the problem to construct approximations of the value function in SDP. Thus the curse of dimensionality if largely avoided.
Top-percentile pricing, multi-homing, stochastic, routing policy, approximate dynamic programming
Written: 24 February 2010
Submitted for publication
