### Technical Report ERGO 10-003

#### Solving the top-percentile traffic routing problem by approximate dynamic programming

*Andreas Grothey and Xinan Yang*

##### 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 θ-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.

##### Keywords:

Top-percentile pricing, multi-homing, stochastic, routing policy, approximate dynamic programming

##### Download:

ERGO-10-003.pdf

##### History:

Written: 24 February 2010

##### Status:

Submitted for publication