Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
To send or not to send: Reducing the cost of data transmission
== Speaker ==
Koyel Mukherjee
== Abstract ==
Frequently, ISPs charge for Internet use not based on peak
bandwidth usage, but according to a percentile (often the
95th percentile) cost
model. In other words, the time slots with the top 5 percent
(in the case of 95th percentile) of
data transmission volume do not affect the cost of transmission. Instead,
we are
charged based on the
volume of traffic sent in the 95th
percentile
slot.
In such an environment, by allowing a short delay in transmission of some
data,
we may be able to reduce our cost considerably.
We provide an optimal solution to the offline version of this problem
(in which the job arrivals are known), for any delay $D>0$.
The algorithm works for any choice of percentile.
We also show that there is no efficient deterministic online algorithm for
this
problem. However, for a slightly different problem,
where the maximum amount of data transmitted is used for cost accounting,
we provide an online algorithm with a competitive ratio of
$\frac{2D+1}{D+1}$.
Furthermore, we prove that no online algorithm can achieve a competitive
ratio $
$\frac{2D+1}{D + F(D)}$ where
$F(D) = \sum^{D+1}_{i=1}{\frac{i}{D+i}}$
for any $D>0$ in an adversarial setting.
We also provide a heuristic that can be used in an online setting
where the network traffic has a strong correlation over consecutive
accounting $
based on the solution to the offline percentile problem.
Experimental results are used to illustrate the performance of the
algorithms proposed in this work.
oint work with: Leana Golubchik, Samir Khuller and Yuan Yao.
To send or not to send: Reducing the cost of data transmission
== Speaker ==
Koyel Mukherjee
== Abstract ==
Frequently, ISPs charge for Internet use not based on peak
bandwidth usage, but according to a percentile (often the
95th percentile) cost
model. In other words, the time slots with the top 5 percent
(in the case of 95th percentile) of
data transmission volume do not affect the cost of transmission. Instead,
we are
charged based on the
volume of traffic sent in the 95th
percentile
slot.
In such an environment, by allowing a short delay in transmission of some
data,
we may be able to reduce our cost considerably.
We provide an optimal solution to the offline version of this problem
(in which the job arrivals are known), for any delay $D>0$.
The algorithm works for any choice of percentile.
We also show that there is no efficient deterministic online algorithm for
this
problem. However, for a slightly different problem,
where the maximum amount of data transmitted is used for cost accounting,
we provide an online algorithm with a competitive ratio of
$\frac{2D+1}{D+1}$.
Furthermore, we prove that no online algorithm can achieve a competitive
ratio $
$\frac{2D+1}{D + F(D)}$ where
$F(D) = \sum^{D+1}_{i=1}{\frac{i}{D+i}}$
for any $D>0$ in an adversarial setting.
We also provide a heuristic that can be used in an online setting
where the network traffic has a strong correlation over consecutive
accounting $
based on the solution to the offline percentile problem.
Experimental results are used to illustrate the performance of the
algorithms proposed in this work.
oint work with: Leana Golubchik, Samir Khuller and Yuan Yao.
