Traffic regulation under the percentile-based pricing policy

With the emerging concept of utility computing, appropriate business models are becoming more and more important for the Internet services. Internet Service Providers (ISP) measure IP network usage for billing in different ways. Percentile-based pricing policy is one of the common billing methods. Percentile-based measurement allows the ISP to bill the customer for the maximum bandwidth used during the billing period while forgiving a small amount of bandwidth spiking. In this paper, we investigate how a customer can regulate the traffic volume under the constraint of a predetermined budget such that the amount of band-width spiking is within the range that the ISP can tolerate. Optimal solutions are presented for the offline case where the traffic demands in each small period are given. A traffic scheduling algorithm is given for the online case where the traffic demands in each small period are unknown in advance. Computations are conducted to illustrate the effectiveness of our solutions. © 2006 ACM.