  Erasure coding is a storage-efficient alternative to replication for
achieving reliable data backup in distributed storage systems. During the
storage process, traditional erasure codes require a unique source node to
create and upload all the redundant data to the different storage nodes.
However, such a source node may have limited communication and computation
capabilities, which constrain the storage process throughput. Moreover, the
source node and the different storage nodes might not be able to send and
receive data simultaneously -- e.g., nodes might be busy in a datacenter
setting, or simply be offline in a peer-to-peer setting -- which can further
threaten the efficacy of the overall storage process. In this paper we propose
an "in-network" redundancy generation process which distributes the data
insertion load among the source and storage nodes by allowing the storage nodes
to generate new redundant data by exchanging partial information among
themselves, improving the throughput of the storage process. The process is
carried out asynchronously, utilizing spare bandwidth and computing resources
from the storage nodes. The proposed approach leverages on the local
repairability property of newly proposed erasure codes tailor made for the
needs of distributed storage systems. We analytically show that the performance
of this technique relies on an efficient usage of the spare node resources, and
we derive a set of scheduling algorithms to maximize the same. We
experimentally show, using availability traces from real peer-to-peer
applications as well as Google data center availability and workload traces,
that our algorithms can, depending on the environment characteristics, increase
the throughput of the storage process significantly (up to 90% in data centers,
and 60% in peer-to-peer settings) with respect to the classical naive data
insertion approach.
