Resource Assignment In File Distribution Systems

ABSTRACT:As an important platform of information dissemination, file distribution system is challenged by the conflict between the network resource limitations and the high-level user requirements, which not only affects the quality of service and increases the system cost, but also seriously hinders the evolution and expansion of the network business. This paper analyses the datasets of file downloading and user’s ON/OFF process in large-scale file distribution systems (PPTV and QQ XuanFeng), locating several bottleneck problems:the shortage of resources caused by unreasonable assignment of file-copy and bandwidth, the excessive consumption of resources caused by Flash Crowd and user churn, etc. Towards these issues, this paper builds theoretical models, and proposes resource assignment strategies. The main work and innovations of this paper are summarized as follows:(1) Based on the datasets of user’s ON/OFF process in the file distribution system, analysis results indicate that user’s online duration is related to user’s arrival time; and our further simulation proves that user’s periodic daily churn can be characterized only by combining these two factors. We also model the user churn by introducing the dynamic departure probability to express its correlation.(2) To deal with the issue of unreasonable assignment of resources when file distribution system is in steady state, the algorithms of copy assignment and bandwidth allocation are proposed. First, considering the impact of the mean and variance of user’s requests, the optimal copy assignment algorithm with fairness, which attends to keep the ratio of copies and requests for each file to be the same, is obtained by solving the objective function. Simulation results show that when the mean and variance is equivalent, the fairness of the algorithm is50%higher than the traditional proration assignment. This value will increase to87%when the variance is larger. We then propose the criteria of copy placement strategy. It is found that placing popular file and unpopular files together could increase bandwidth utilization and reduce bandwidth scramble, but detrimental to the fairness of the file. Finally, three upload bandwidth allocation algorithms for users are proposed to ensure the fairness of the file, including the optimal allocation algorithm, centralized heuristic algorithm based on Max-Min and distributed heuristic algorithm based on GPS. Simulation results demonstrate that the fairness of the distributed algorithm is75%higher than the widely used equal allocation, and the fairness of the centralized algorithm is close to the theoretical optimal value.(3) To deal with the issue of the large server bandwidth consumption under flash crowd in a file distribution system, the peer assisted pre-allocation (PAPA) strategy is proposed. First, based on the fluid model, the relationship among the required server bandwidth, the user arrival rate, leaving rate and download speed is formulated. It is found that the peak bandwidth is caused by the lack of seeds before the system is stable. Then the pre-allocation strategy is proposed, in which the system allocates the file copies to the assist nodes (helpers) before they are releasd, in order to increase the seeds when the flash crowd occurs, and then ease the server peak bandwidth consumption. By setting the bandwidth of steady state to be the objective peak bandwidth, parameters of the strategy such as the arrival rates of helpers, the start and end time of task are devised. Numerical simulation and actual system test show that PAPA can significantly reduce the server’s peak bandwidth by more than30%.(4) To deal with the issue that user churn leads to the low storage resource utilization in the reservation cloud download system, a dynamic resource allocation strategy is proposed. Base on the user churn’s Markov model, the closed expression among the storage consumption, user experience and user churn is deduced. Then we decomposed the consumption into two parts:waiting consumption and download consumption. On this basis, we propose the dynamic resource allocation schemes including switching speed (SS) and gradually increasing speed (GS), which will convert or increase server download speed according to user’s ON/OFF status changes, thus reduce storage consumption of the two parts. Theoretical analysis and simulation comparison between the new strategy and the constant rate scheme shows that the integrated use of the two schemes can reduce storage consumption by approximately33%.