  In large-scale distributed storage systems (DSS), reliability is provided by
redundancy spread over storage servers across the Internet. Network coding (NC)
has been widely studied in DSS because it can improve the reliability with low
repair time. To maintain reliability, an unavailable storage server should be
firstly replaced by a new server, named new comer. Then, multiple storage
servers, called providers, should be selected from surviving servers and send
their coded data through the Internet to the new comer for regenerating the
lost data. Therefore, in a large-scale DSS, provider selection and data routing
during the regeneration phase have great impact on the performance of
regeneration time. In this paper, we investigate a problem of optimal provider
selection and data routing for minimizing the regeneration time in the DSS with
NC. Specifically, we first define the problem in the DSS with NC. For the case
that the providers are given, we model the problem as a mathematical
programming. Based on the mathematical programming, we then formulate the
optimal provider selection and data routing problem as an integer linear
programming problem and develop an efficient near-optimal algorithm based on
linear programming relaxation (BLP). Finally, extensive simulation experiments
have been conducted, and the results show the effectiveness of the proposed
algorithm.
