| Offline (cloud) download system is a new file distribution system. Different from traditional download applications, download servers of off-line download system download the file instead of users, such that the users do not have to remain active. Such design can save users’download time and resources, and give users a better download experience. However, with the increasing of the number of users and new file resources, operators of off-line download system are facing two challenges:storage pressure and bandwidth overhead. Actual business system uses LRU or LFU algorithm to solve the problem of storage pressure. Although the above algorithms can also help alleviating bandwidth pressure in a certain extent, but they are not specifically designed to do so. Thus, how to minimize network bandwidth while not degrading user experience, is still one of the key concerns of network operators.The existing optimization algorithms are not suitable for find the minimal bandwidth, since their optimization objectives are not bandwidth. (In fact, they assume bandwidth is a given condition.) Bandwidth is a variable to be optimized in our case. It makes the optimization problem difficult, since we have to consider other optimization objectives simultaneously. Therefore, finding the optimal bandwidth becomes the problem studied in this paper.In this paper, we study the optimal bandwidth based on reservation window (RW). RW is defined as the interval between a user’s request time and download time. Offline download system is a reservation system, so we can obtain each download tasks’request time and download time. Based on RW, the main work and contribution of this paper is:(1) To find the optimal bandwidth, we propose the "pits-filing" algorithm. The idea is to make the total bandwidth as equally as possible at any time, by adjusting the download speeds of different tasks in different time. This algorithm sorts all request time instants and download time instants to form multiple time segments (optimization segments). Then it arranges download rates of different tasks in each optimization segment, to minimize the maximum bandwidth calculated in each round.(2) To fast approach the optimal bandwidth, we further propose an EDF approximation algorithm. The idea of this heuristic algorithm is to find a sub-optimal ("minimal") bandwidth which can complete all users’ requests, by trying different bandwidth using EDF. The low complexity of EDF can greatly reduce the computation time, so it can be used in engineering calculation.(3) In addition, considering time-of-use pricing mode of ISP, we also put forward an optimal algorithm to realize the best time-of-use leasing bandwidth scheme. This algorithm can optimize the rental cost of bandwidth in theory and provide a theoretical basis for the design of practical algorithm of bandwidth.Finally, this paper conducts a serial of large-scale simulations by using the real data set of Tencent offline download system. The results of the simulations mutually verify the performance of the proposed algorithms, which gives similar optimized bandwidth results. Furthermore, by using raw data of one day, the computation costs are 16 hours for simplified "pits-filing" algorithm, and 23 minutes for EDF approximation algorithm, respectively. The latter can approach the optimal bandwidth with high precision. By using the data of the previous day to predict the bandwidth of current day, the prediction error is only 0.22%. |
PDF Full Text Request