Outer Bounds on the Storage-Bandwidth Tradeoff of Linear Exact-Repair Regenerating Codes

Abstract

최근 SNS나 클라우드 서비스의 사용량 증가와 더불어, 대규모의 데이터를 네트워크상에 효율적이고 안정적으로 저장할 수 있는 분산 저장 시스템(distributed storage system)에 대한 연구가 활발하게 진행되고 있다. 분산 저장 시스템은 대규모의 데이터 파일을 네트워크로 연결된 다수의 노드에 분산적으로 저장하는 시스템을 말한다. 일부의 노드가 손실되었을 때, 손실된 노드는 다른 생존한 노드들로부터 전송받은 정보를 이용하여 복구될 수 있어야 한다. 이러한 복구 과정에서 필요한 총 정보량인 복구 대역폭(repair bandwidth)을 최소화하는 것은 분산 저장시스템의 중요한 성능 지표중 하나이다. 협력 재생 부호(Cooperative regenerating codes)는 높은 복구 대역폭을 최소화하는 erasure code의 일종이다. $(n,k,d,r)$-협력 재생 부호는 총 $n$개의 저장소 노드 중 일부의 $k$개의 노드에 저장된 정보만으로 원래의 파일을 복구할 수 있는 기능과 $r$개의 노드 손실이 발생했을때, 임의의 $d$개의 생존한 노드들로부터 정보를 전송받아 복구될 수 있는 기능을 가진다. 이 때, 재생 부호의 각 노드별 저장량 $\alpha$와 복구 대역폭 $\gamma$는 일반적으로 상충관계에 놓여 있음이 알려져 있다. 하지만 새롭게 복구된 노드가 기존 노드와 다른 정보를 가지는 것을 허용하는 기능 복구(functional repair) 모델의 경우, 이 상충관계가 완벽히 밝혀져 있으나, 손실되기 전과 완전히 동일한 노드로의 복구를 요구하는 동일 복구(exact repair) 모델의 경우, 이 상충관계가 명확히 밝혀져 있지 않다. 본 논문에서는 동일 복구 모델의 상충 관계에 대한 두 종류의 외부 경계(outer bound)를 제시한다. 상충 관계의 외부 경계는 기능 복구 부호로는 가능하지만, 동일 복구 부호로는 설계가 불가능한 $(\alpha,\gamma)$ 동작점들을 제시한다. 첫 번째 외부 경계는 일반적인 $(n,k,d,r)$ 파라미터를 가지는 협력 재생 부호를 가정하여 유도되었다. 이 외부 경계는 $d=k=n-1$, $r=1$을 만족하는 경우에 한하여 최적의 상충관계를 밝힌 Prakash 등의 연구 결과를 일반화한 것으로 볼 수 있다. 첫 번째 외부 경계는 $k$가 크거나 $r$이 작거나 $k$와 $d$가 비슷한 조건 하에서 더 좋은 성능을 보임을 확인할 수 있다. 두 번째 외부 경계는 한 번에 한 개의 손실된 노드만을 복구하는 경우로 한정하였을 때를 고려한다. 두 번째 외부 경계는 두 개의 독립적인 부경계(sub-bound)의 합집합으로 표현된다. 두 가지의 부경계들은 각각 성능이 좋아지는 조건이 다름을 실험을 통해 확인할 수 있다. 첫 번째 부경계는 본 논문에서 첫 번째로 제안된 외부 경계와 비슷하게 $k/n$으로 정의되는 코드의 부호화율이 1에 가까울수록 더 좋은 성능을 보이며, 두 번째 부 경계는 반대로 부호화율이 낮아질떄 다른 기존의 외부경계들보다 더 좋은 성능을 보임을 확인할 수 있다.

Distributed storage systems disperse data to a large number of storage nodes connected in a network. When some of the storage nodes fail, a storage system should be able to repair them by downloading data from other surviving nodes. The amount of data traffic during the repair, called repair bandwidth, is one of the important performance metrics of distributed storage systems. Cooperative regenerating codes are a class of recently developed erasure codes which are optimal in terms of minimizing the repair bandwidth. An $(n,k,d,r)$-cooperative regenerating code has $n$ storage nodes, where $k$ arbitrary nodes are enough to reconstruct the original data, and $r$ failed nodes can be repaired cooperatively with the help of $d$ arbitrary surviving nodes. In the regenerating-code framework, there exists a tradeoff between the storage capacity of each node $\alpha$ and the repair bandwidth $\gamma$. The tradeoff of functional repair codes are fully characterized by Shum et al, but the problem of specifying the optimal storage-bandwidth tradeoff of the exact repair codes remains open. In this dissertation, two outer bounds on the storage-bandwidth tradeoff under the exact repair model are proposed. The outer bounds suggest the $(\alpha,\gamma)$ pairs that no exact repair codes can achieve but only functional repair codes can. The first outer bound considers general set of parameters $(n,k,d,r)$. This result can be regarded as a generalization of the outer bound proposed by Prakash et al., which specifies the optimal tradeoff of exact-repair regenerating codes for the case of $d=k=n-1$ and $r=1$. It is verified that the proposed outer bound becomes more effective when $k$ is large, $r$ is small, or $d~(\geq k)$ is close to $k$. The second outer bound is developed for the case of single node repair ($r=1$). The bound is union of two independently derived sub-bounds. Each sub-bound has its own condition to be tighter than the other. One sub-bound can be regarded as an extension of the first outer bound for $r=1$, and becomes more effective in high rates ($k/n >\frac {1}{2}$). The other sub-bound is derived based on the symmetric property of the storage nodes, and is tight in low rates ($k/n <\frac{1}{2}$).