ISAA: Boost Repair Process by Constructing the Degree Constrained Optimal Repair Tree for Erasure-coded Systems

To ensure data reliability, large-scale distributed systems usually adopt erasure codes to restore failed nodes. However, existing erasure-coded repair strategies will cause heavy network traffics, which will increase the repair time. In order to boost the repair process, we consider optimizing the...

Full description

Saved in:
Bibliographic Details
Main Authors: Du, Xianzhi, Zhu, Bing, Deng, Zhihang, Shum, Kenneth W., Wang, Weiping
Format: Conference Proceeding
Language:English
Subjects:
Bandwidth
Codes
Maintenance engineering
NP-hard problem
Prufer code
repair tree
Simulated annealing
simulated annealing algorithm
Simulation
Telecommunication traffic
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:To ensure data reliability, large-scale distributed systems usually adopt erasure codes to restore failed nodes. However, existing erasure-coded repair strategies will cause heavy network traffics, which will increase the repair time. In order to boost the repair process, we consider optimizing the repair path which can be abstracted to a repair tree. Moreover, we add a degree constraint to each node to avoid local congestion. In this paper, we study the degree constrained optimal repair tree, which is an NP-hard problem. Current methods cannot find the optimal solution in a short time in complex non-uniform bandwidth networks. To obtain the optimal repair tree, an improved simulated annealing algorithm (ISAA) based on the Prufer code representation is proposed in this paper. In addition, we simulate the repair process of erasure codes in a non-uniform bandwidth network and experiments show that the repair time reduction can reach up to 66.4% and 88.6% with ISAA over Repair Pipelining and Partial-Parallel-Repair.
ISSN:2690-5965
DOI:10.1109/ICPADS60453.2023.00037