Top-percentile traffic routing problem
View/ Open
original_files.zip (960.0Kb)
Date
25/06/2012Author
Yang, Xinan
Metadata
Abstract
Multi-homing is a technology used by Internet Service Provider (ISP) to connect
to the Internet via multiple networks. This connectivity enhances the network
reliability and service quality of the ISP. However, using multi-networks may
imply multiple costs on the ISP. To make full use of the underlying networks with
minimum cost, a routing strategy is requested by ISPs. Of course, this optimal
routing strategy depends on the pricing regime used by network providers. In
this study we investigate a relatively new pricing regime – top-percentile pricing.
Under top-percentile pricing, network providers divide the charging period into
several fixed length time intervals and calculate their cost according to the traffic
volume that has been shipped during the θ-th highest time interval. Unlike
traditional pricing regimes, the network design under top-percentile pricing has
not been fully studied. This paper investigates the optimal routing strategy in
case where network providers charge ISPs according to top-percentile pricing. We
call this problem the Top-percentile Traffic Routing Problem (TpTRP). As the
ISP cannot predict next time interval’s traffic volume in real world application,
in our setting up the TpTRP is a multi-stage stochastic optimisation problem.
Routing decisions should be made at the beginning of every time period before
knowing the amount of traffic that is to be sent. The stochastic nature of the
TpTRP forms the critical difficulty of this study.
In this paper several approaches are investigated in either the modelling or solving
steps of the problem. We begin by exploring several simplifications of the original
TpTRP to get an insight of the features of the problem. Some of these allow
analytical solutions which lead to bounds on the achievable optimal solution. We
also establish bounds by investigating several “naive” routing policies. In the
second part of this work, we build the multi-stage stochastic programming model
of the TpTRP, which is hard to solve due to the integer variables introduced in
the calculation of the top-percentile traffic. A lift-and-project based cutting plane method is investigated in solving the SMIP for very small examples of TpTRP.
Nevertheless it is too inefficient to be applicable on large sized instances. As an
alternative, we explore the solution of the TpTRP as a Stochastic Dynamic Programming
(SDP) problem by a discretization of the state space. This SDP model
gives us achievable routing policies on small size instances of the TpTRP, which of
course improve the naive routing policies. However, the solution approach based
on SDP suffers from the curse of dimensionality which restricts its applicability.
To overcome this we suggest using Approximate Dynamic Programming (ADP)
which largely avoids the curse of dimensionality by exploiting the structure of the
problem to construct parameterized approximations of the value function in SDP
and train the model iteratively to get a converged set of parameters. The resulting
ADP model with discrete parameter for every time interval works well for
medium size instances of TpTRP, though it still requires too long to be trained
for large size instances. To make the realistically sized TpTRP problem solvable,
we improve on the ADP model by using 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 realistically sized
TpTRP tractable.