Distributed Storage in Heterogeneous and Asymmetric Networks
Tobias Langner · 2009
We introduce a distribution problem that examines the question of how the fragments of a file should be distributed to multiple servers such that the asymmetric bandwidths of the servers are used optimally by the bidirectional transmission in order to minimise the transfer times. We present three efficient techniques that solve this problem optimally. The first algorithm, IterativeSqueezing, iteratively improves an initial solution by cleverly redistributing data from slow to fast servers until the optimum solution is achieved. The BinarySearch approach formulates the distribution problem as a maximum flow problem and deduces a predicate that states whether a solution with given time bounds exists. This criterion is used to guide the search through the solution space to the optimal solution while adhering to the binary search paradigm. The fastest of the three methods called AnalyticalScaling, builds on the results of the BinarySearch algorithm by examining its key instrument, the total data function, in greater detail from an analytical point of view and thereby determines the optimal solution. All algorithms are thoroughly analysed with respect to optimality and runtime complexity. We present the experimental results from the implementation of our algorithms that clearly confirm the theoretical results derived in this work.