TY - GEN

T1 - On region-based fault tolerant design of distributed file storage in networks

AU - Banerjee, Sujogya

AU - Shirazipourazad, Shahrzad

AU - Sen, Arunabha

PY - 2012

Y1 - 2012

N2 - Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.

AB - Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.

UR - http://www.scopus.com/inward/record.url?scp=84861639764&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861639764&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2012.6195704

DO - 10.1109/INFCOM.2012.6195704

M3 - Conference contribution

AN - SCOPUS:84861639764

SN - 9781467307758

T3 - Proceedings - IEEE INFOCOM

SP - 2806

EP - 2810

BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012

T2 - IEEE Conference on Computer Communications, INFOCOM 2012

Y2 - 25 March 2012 through 30 March 2012

ER -