TY - GEN

T1 - To send or not to send

T2 - 32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

AU - Golubchik, Leana

AU - Khuller, Samir

AU - Mukherjee, Koyel

AU - Yao, Yuan

PY - 2013/9/2

Y1 - 2013/9/2

N2 - 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 2D+1/D+1. Furthermore, we prove that no online algorithm can achieve a competitive ratio better than 2D+1/D+F(D) where F(D) = ∑D+1i=1 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 cycles, based on the solution to the offline percentile problem. Experimental results are used to illustrate the performance of the algorithms proposed in this work.

AB - 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 2D+1/D+1. Furthermore, we prove that no online algorithm can achieve a competitive ratio better than 2D+1/D+F(D) where F(D) = ∑D+1i=1 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 cycles, based on the solution to the offline percentile problem. Experimental results are used to illustrate the performance of the algorithms proposed in this work.

UR - http://www.scopus.com/inward/record.url?scp=84883087672&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883087672&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2013.6567053

DO - 10.1109/INFCOM.2013.6567053

M3 - Conference contribution

AN - SCOPUS:84883087672

SN - 9781467359467

T3 - Proceedings - IEEE INFOCOM

SP - 2472

EP - 2480

BT - 2013 Proceedings IEEE INFOCOM 2013

Y2 - 14 April 2013 through 19 April 2013

ER -