Building parallel regeneration trees in distributed storage systems with asymmetric links

Distributed storage systems provide reliable storage service by storing data, with a certain amount of redundancy, into a substantial number of storage nodes. In order to compensate the data loss incurred by node failures, the lost data should be regenerated. Tree-structured regeneration, during which storage nodes may relay the network traffic, has shown its potential to improve the efficiency of the regeneration process in the network with symmetric links. In this paper, we consider tree-structured regeneration in the network with asymmetric links, and analyze its expected time spend during the regeneration. Moreover, we further reduce the regeneration time by constructing multiple parallel regeneration trees. We proposed two optimal algorithms with polynomial time complexity, to construct multiple edge-disjoint and multiple edge-sharing parallel regeneration trees, respectively. We evaluate our algorithms by the simulation using real data measured in PlanetLab. The simulation results show that multiple parallel regeneration trees can reduce the regeneration time by 75% and keep the file availability more than 98%.