Route Computation for Reliable Delivery of Threshold Secret Shared Content

Nagao OGINO  Hidetoshi YOKOTA  

IEICE TRANSACTIONS on Communications   Vol.E98-B   No.1   pp.209-218
Publication Date: 2015/01/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E98.B.209
Type of Manuscript: PAPER
Category: Network
reliable content delivery,  threshold secret sharing,  route optimization,  greedy method,  adjustment of link distance,  

Full Text: PDF>>
Buy this Article

A threshold secret sharing scheme protects content by dividing it into many pieces and distributing them among different servers. This scheme can also be utilized for the reliable delivery of important content. Thanks to this scheme, the receiver can still reconstruct the original content even if several pieces are lost during delivery due to a multiple-link failure. Nevertheless, the receiver cannot reconstruct the original content unless it receives pieces more than or equal to the threshold. This paper aims to obtain reliable delivery routes for the pieces, as this will minimize the probability that the receiver cannot reconstruct the original content. Although such a route optimization problem can be formulated using an integer linear programming (ILP) model, computation of globally optimum delivery routes based on the ILP model requires large amounts of computational resources. Thus, this paper proposes a lightweight method for computing suboptimum delivery routes. The proposed greedy method computes each of the delivery routes successively by using the conventional shortest route algorithm repeatedly. The link distances are adjusted iteratively on the basis of the given probability of failure on each link and they are utilized for the calculation of each shortest route. The results of a performance evaluation show that the proposed method can compute sub-optimum delivery routes efficiently thanks to the precise adjustment of the link distances, even in backbone networks on a real-world scale.