Diversity Coloring for Distributed Storage in Mobile Networks

Abstract

Storing multiple copies of files is crucial for ensuring quality of service for data storage in mobile networks. This paper proposes a new scheme, called the K-out-of-N file distribution scheme, for the placement of files. In this scheme files are splitted, and Reed-Solomon codes or other maximum distance seperable (MDS) codes are used to produce file segments containing parity information. Multiple copies of the file segments are stored on gateways in the network in such a way that every gateway can retrieve enough file segments from itself and its neighbors within a certain amount of hops for reconstructing the orginal files. The goal is to minimize the maximum number of hops it takes for any gateway to get enough file segments for the file reconstruction. We formulate the K-out-of-N file distribution scheme as a coloring problem we call diversity coloring. A diversity coloring is defined to be optimal if it uses the smallest number of colors. Upper and lower bounds on the performance of diversity coloring for general graphs are studied. Diversity coloring algorithms for several special classes of graphs - trees, rings and tori - are presented, all of which have linear time complexity. Both the algorithm for trees and the algorithm for rings output optimal diversity colorings. The algorithm for tori guarantees to output optimal diversity coloring when the sizes of tori are sufficiently large.