分布式存储网最小传输开销认证树构建算法

Construction Algorithm of Least Transmission Cost Authentication Tree in Distributed Storage Network

现有的认证树构建算法忽略认证信息在存储网中的访问距离,导致认证树传输开销过大。为此,提出一种传输开销最小化的认证树构建算法。在利用内容片访问热度的基础上,增加存储网中内容片访问距离,度量各个内容片认证信息的传输开销,并将此映射为赫夫曼编码树中各叶子节点的权重,采用贪心策略逐步合并权重最小的子树,形成最终的认证树。仿真结果表明,该算法构建的认证树在存储网中的传输开销最小,与TFDP和α-leaf树相比,生成的认证树可使传输开销分别降低19.8%和9.5%,更适合于分布式存储网中的文件内容认证。

Current generating algorithms of authentication tree ignore the access distance of authentication information, which leads to high transmission cost in distributed storage network. This paper proposes an authentication tree construction algorithm which minimizes the transmission cost. In addition to content piece＇s access frequency, the algorithm introduces access distance in distributed storage network, measures the authentication transmission cost of each content piece. It treats this cost as the weight of Huffman tree, uses greedy strategy to merge least subtrees step by step, and formulates the final authentication tree. The least transmission cost of the authentication tree is proved. Simulation results show that the authentication tree of the algorithm costs 19.8% and 9.5% less than TFDP and α-leaf tree. Thus it suits most for the content authentication in distributed storage network.