Conflict free network coding for distributed storage networks

In this paper, we design a conflict free instantly decodable network coding (IDNC) solution for file download from distributed storage servers. Considering previously downloaded files at the clients from these servers as side information, IDNC can speed up the current download process. However, transmission conflicts can occur since multiple servers can simultaneously send IDNC combinations of files to the same client, which can tune to only one of them at a time. To avoid such conflicts and design more efficient coded download patterns, we propose a dual conflict IDNC graph model, which extends the conventional IDNC graph model in order to guarantee conflict free server transmissions to each of the clients. We then formulate the download time minimization problem as a stochastic shortest path problem whose action space is defined by the independent sets of this new graph. Given the intractability of the solution, we design a channel-aware heuristic algorithm and show that it achieves a considerable reduction in the file download time, compared to applying the conventional IDNC approach separately at each of the servers.