Optimized Assignment Algorithm to Maximize the Reduction for Backup System with Multiple Deduplication Methods Installed
Mikito Ogata, Norihisa Komoda · Electronics and Communications in Japan · 2015
SUMMARY Deduplication backup technology removes redundant data segments in a system in order to reduce the capacity usage in the target backup storage. This technique also provides better performance, less resource utilization, less energy consumption, and TCO. This paper describes an optimization method for deduplication backup in an IT system in which multiple deduplication processes are simultaneously installed and activated. The method provides an algorithm for assignment of backup target files to installed deduplication processes to maximize the aggregate deduplication ratio while maintaining the predefined system requirements, such as backup‐windows limitation and resource utilization limitation. In a real‐world system, the time used to perform deduplication in each process is not constant, but variable due to operational resources contention, waiting time in queues, and data characteristics. The proposed method points out that these time parameters can be simulated as following a normal distribution, formularizes discrete assignment programming, then defines combinatory approaches of integer linear programming to incorporate the maximum deduplication ratio and the binary adjustment of parameters so as to ensure that the variance is not exceeded. By utilizing this method, the system can achieve the maximal deduplication ratio while respecting time requirements within a predefined tolerance. The effectiveness of the method is demonstrated through simulations.