| 1. |
- Gerami, Majid, 1976-
(författare)
-
Coding, Computing, and Communication in Distributed Storage Systems
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Conventional studies in communication networks mostly focus on securely and reliably transmitting data from a source node (or multiple source nodes) to multiple destinations. A more general problem appears when the destination nodes are interested in obtaining functions of the data available in distributed source nodes. For obtaining a function, transmitting all the data to a destination node and then computing the function might be inefficient. In order to exploit the network resources efficiently, the general problem offers distributed computing in combination with coding and communication. This problem has applications in distributed systems, e.g., in wireless sensor networks, in distributed storage systems, and in distributed computing systems. Following this general problem formulation, we study the optimal and secure recovery of the lost data in storage nodes and in reconstructing a version of a file in distributed storage systems. The significance of this study is due to the fact that the new trends in communications including big data, Internet of things, low latency, and high reliability communications challenge the existing centralized data storage systems. Distributed storage systems can rectify those issues by distributing thousands of storage nodes (possibly around the globe), and then benefiting users by bringing data to their proximity. Yet, distributing the storage nodes brings new challenges. In these distributed systems, where storage nodes are connected through links and servers, communication plays a main role in their performance. In addition, a part of network may fail or due to communication failure or delay there might exist multi versions of a file. Moreover, an intruder can overhear the communications between storage nodes and obtain some information about the stored data. Therefore, there are challenges on reliability, security, availability, and consistency. To increase reliability, systems need to store redundant data in storage nodes and employ error control codes. To maintain the reliability in a dynamic environment where storage nodes can fail, the system should have an autonomous repair process. Namely, it should regenerate the failed nodes by the help of other storage nodes. The repair process demands bandwidth, energy, or in general transmission costs. We propose novel techniques to reduce the repair cost in distributed storage systems. First, we propose {surviving nodes cooperation} in repair, meaning that surviving nodes can combine their received data with their own stored data and then transmit toward the new node. In addition, we study the repair problem in multi-hop networks and consider the cost of transmitting data between storage nodes. While classical repair model assumes the availability of direct links between the new node and surviving nodes, we consider that such links may not be available either due to failure or their costs. We formulate an optimization problem to minimize the repair cost and compare two systems, namely with and without surviving nodes cooperation. Second, we study the repair problem where the links between storage nodes are lossy e.g., due to server congestion, load balancing, or unreliable physical layer (wireless links). We model the lossy links by packet erasure channels and then derive the fundamental bandwidth-storage tradeoff in packet erasure networks. In addition, we propose dedicated-for-repair storage nodes to reduce the repair-bandwidth. Third, we generalize the repair model by proposing the concept of partial repair. That is, storage nodes may lose parts of their stored data. Then in partial repair, the lost data is recovered by exchanging data between storage nodes and using the available data in storage nodes as side information. For efficient partial-repair, we propose two-layer coding in distributed storage systems and then we derive the optimal bandwidth in partial repair. Fourth, we study security in distributed storage systems. We investigate security in partial repair. In particular, we propose codes that make the partial repair secure in the senses of strong and weak information-theoretic security definitions. Finally, we study consistency in distributed storage systems. Consistency means that distinct users obtain the latest version of a file in a system that stores multi versions of a file. Given the probability of receiving a version by a storage node and the constraint on the node storage space, we aim to find the optimal encoding of multi versions of a file that maximizes the probability of obtaining the latest version of a file or a version close to the latest version by a read client that connects to a number of storage nodes.
|
|
| 2. |
- Gerami, Majid, et al.
(författare)
-
Decentralized minimum-cost repair for distributed storage systems
- 2013
-
Ingår i: Communications (ICC), 2013 IEEE International Conference on. - : IEEE conference proceedings. - 9781467331227 ; , s. 1910-1914
-
Konferensbidrag (refereegranskat)abstract
- There have been emerging lots of applications for distributed storage systems e.g., those in wireless sensor networks or cloud storage. Since storage nodes in wireless sensor networks have limited battery, it is valuable to find a repair scheme with optimal transmission costs (e.g., energy). The optimal-cost repair has been recently investigated in a centralized way. However a centralized control mechanism may not be available or is very expensive. For the scenarios, it is interesting to study optimal-cost repair in a decentralized setup. We formulate the optimal-cost repair as convex optimization problems for the network with convex transmission costs. Then we use primal and dual decomposition approaches to decouple the problem into subproblems to be solved locally. Thus, each surviving node, collaborating with other nodes, can minimize its transmission cost such that the global cost is minimized. We further study the optimality and convergence of the algorithms. Finally, we discuss the code construction and determine the field size for finding feasible network codes in our approaches.
|
|
| 3. |
- Gerami, Majid, et al.
(författare)
-
Exact optimized-cost repair in multi-hop distributed storage networks
- 2014
-
Ingår i: 2014 IEEE International Conference on Communications, ICC. - : IEEE Computer Society. - 9781479920037 ; , s. 4120-4124
-
Konferensbidrag (refereegranskat)abstract
- The problem of exact repair of a failed node in multi-hop networked distributed storage systems is considered. Contrary to the most of the current studies which model the repair process by the direct links from surviving nodes to the new node, the repair is modeled by considering the multi-hop network structure, and taking into account that there might not exist direct links from all the surviving nodes to the new node. In the repair problem of these systems, surviving nodes may cooperate to transmit the repair traffic to the new node. In this setting, we define the total number of packets transmitted between nodes as repair-cost. A lower bound of the repair-cost can thus be found by cut-set bound analysis. In this paper, we show that the lower bound of the repair-cost is achievable for the exact repair of MDS codes in tandem and grid networks, thus resulting in the minimum-cost exact MDS codes. Further, two suboptimal (achievable) bounds for the large scale grid networks are proposed.
|
|
| 4. |
- Gerami, Majid, et al.
(författare)
-
Optimal-cost repair in multi-hop distributed storage systems
- 2011
-
Ingår i: IEEE International Symposium on Information Theory - Proceedings. - : IEEE. - 9781457705953 ; , s. 1437-1441
-
Konferensbidrag (refereegranskat)abstract
- In distributed storage systems reliability is achieved through redundant storage nodes distributed in the network. Then a data collector can recover source information even if some nodes fail. To maintain reliability, an autonomous and efficient protocol should be used to reconstruct the failed node. Therepairprocess causes traffic in the network. Recent results in e.g., [1], [2] found the optimal traffic-storage tradeoff, and proposed regenerating codes to achieve the optimality. We investigate the link costs and the impact of network topologies during therepairprocess. We formulate the minimum costrepairproblem in joint and decoupled methods. We investigate the required field size for the joint method. For the decoupled method, we show that the optimization problem is linear for the linear cost. We further show that the cooperation of surviving nodes could efficiently exploit the network topology and reduce therepaircost. The numerical results in tandem, star and grid networks show the benefits of our methods in term of the repair cost.
|
|
| 5. |
- Gerami, Majid, et al.
(författare)
-
Optimal-cost repair in multi-hop distributed storage systems with network coding
- 2016
-
Ingår i: Transactions on Emerging Telecommunications Technologies. - : Wiley-Blackwell. - 2161-5748 .- 2161-3915. ; 27:11, s. 1539-1549
-
Tidskriftsartikel (refereegranskat)abstract
- We study the transmission cost of repair in a distributed storage system, where storage nodes are connected together through an arbitrary network topology, and there is a cost in the use of the network link. Contrary to the classical model, where there exists a link between a pair of storage node, in our repair model there might not exist a link between some pairs of storage nodes or it might be expensive to use. For that, we propose surviving nodes cooperation in repair, meaning that the surviving nodes as the intermediate nodes combine their received packets with their own stored packets and then transmit coded packets towards the new node. We show that surviving node cooperation can reduce the repair-cost, the sum of the costs for transmitting repairing data between the surviving nodes and the new node. For the system that allows surviving node cooperation, we find the minimum-cost codes in repair by firstly deriving a lower bound of the repair-cost through an optimization problem and then proposing achievable codes. We show the gain of the proposed codes in reducing the repair-cost in some scenarios.
|
|
| 6. |
- Gerami, Majid, et al.
(författare)
-
Optimal secure partial-repair in distributed storage systems
- 2017
-
Ingår i: 2017 51st Annual Conference on Information Sciences and Systems, CISS 2017. - : Institute of Electrical and Electronics Engineers (IEEE). - 9781509047802
-
Konferensbidrag (refereegranskat)abstract
- Consider a distributed storage system where parts of the source file fragments in storage nodes are lost. We denote a storage node that lost a part of its fragments as a faulty storage node and a storage node that lost non of its fragment as a complete storage node. In a process, termed as partial repair, a set of storage nodes (among faulty and complete storage nodes) transmit repairing fragments to other faulty storage nodes to recover the lost fragments. We first investigate the optimal partial repair in which the required bandwidth for recovering the lost fragments is minimal. Next, we assume that an eavesdropper wiretaps a subset of links connecting storage nodes, and overhears a number of repairing fragments. We then study optimal secure partial-repair in which the partial-repair bandwidth is minimal and the eavesdropper obtains no information about the source file by overhearing the repairing fragments. We propose optimal secure codes for exact partial-repair in a special scenario.
|
|
| 7. |
- Gerami, Majid, et al.
(författare)
-
Partial Repair for Wireless Caching Networks With Broadcast Channels
- 2015
-
Ingår i: IEEE Wireless Communications Letters. - : Institute of Electrical and Electronics Engineers (IEEE). - 2162-2337 .- 2162-2345. ; 4:2, s. 145-148
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the repair problem for wireless caching networks when parts of stored packets in cashing nodes are lost. We first develop theoretical lower bounds on the number of necessary transmission packets over error-free broadcast channels for repair. Then we discuss the impact of the distribution of the lost packets among caching nodes. Finally, we study the construction of repair codes and propose the optimal exact repair for some special scenarios.
|
|
| 8. |
- Gerami, Majid, et al.
(författare)
-
Repair for distributed storage systems with erasure channels
- 2013
-
Ingår i: Communications (ICC), 2013 IEEE International Conference on. - : IEEE conference proceedings. - 9781467331227 ; , s. 4058-4062
-
Konferensbidrag (refereegranskat)abstract
- We study the repair problem of distributed storage systems in erasure networks where the packets transmitted from surviving nodes to the new node might be lost. The fundamental storage-bandwidth tradeoff is calculated by multicasting analysis in erasure networks. The optimal tradeoff bound can be asymptotically achieved when the number of transmission (packets) goes to infinity. For a limited number of transmission, we study the probability of successful regenerating. Then, we investigate two approaches of increasing the probability of successful regenerating, namely, by connecting more surviving nodes or by increasing the storage space of nodes. Using more nodes may pose larger delay and in certain situation it might not be possible to connect to more nodes too. We show that in addition to reducing repair bandwidth, increasing storage space can also increase reliability for repair.
|
|
| 9. |
- Gerami, Majid, et al.
(författare)
-
Repair for distributed storage systems with packet erasure channels and dedicated nodes for repair
- 2016
-
Ingår i: IEEE Transactions on Communications. - : Institute of Electrical and Electronics Engineers (IEEE). - 0090-6778 .- 1558-0857. ; 64:4, s. 1367-1383
-
Tidskriftsartikel (refereegranskat)abstract
- We study the repair problem in distributed storage systems where storage nodes are connected through packet erasure channels and some nodes are dedicated to repair [termed as dedicated-for-repair (DR) storage nodes]. We first investigate the minimum required repair-bandwidth in an asymptotic setup, in which the stored file is assumed to have an infinite size. The result shows that the asymptotic repair-bandwidth over packet erasure channels with a fixed erasure probability has a closed-form relation to the repair-bandwidth in lossless networks. Next, we show the benefits of DR storage nodes in reducing the repair bandwidth, and then we derive the necessary minimal storage space of DR storage nodes. Finally, we study the repair in a nonasymptotic setup, where the stored file size is finite. We study the minimum practical-repair-bandwidth, i.e., the repair-bandwidth for achieving a given probability of successful repair. A combinatorial optimization problem is formulated to provide the optimal practical-repair-bandwidth for a given packet erasure probability. We show the gain of our proposed approaches in reducing the repair-bandwidth.
|
|
| 10. |
- Gerami, Majid, et al.
(författare)
-
Secure Partial Repair in Wireless Caching Networks with Broadcast Channels
- 2015
-
Ingår i: 2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015. - 9781467378765 ; , s. 353-360
-
Konferensbidrag (refereegranskat)abstract
- We study security in partial repair in wireless caching networks where parts of the stored packets in the caching nodes are susceptible to be erased. Let us denote a caching node that has lost parts of its stored packets as a sick caching node and a caching node that has not lost any packet as a healthy caching node. In partial repair, a set of caching nodes ( among sick and healthy caching nodes) broadcast information to other sick caching nodes to recover the erased packets. The broadcast information from a caching node is assumed to be received without any error by all other caching nodes. All the sick caching nodes then are able to recover their erased packets, while using the broadcast information and the non-erased packets in their storage as side information. In this setting, if an eavesdropper overhears the broadcast channels, it might obtain some information about the stored file. We thus study secure partial repair in the senses of information-theoretically strong and weak security. In both senses, we investigate the secrecy caching capacity, namely, the maximum amount of information which can be stored in the caching network such that there is no leakage of information during a partial repair process. We then deduce the strong and weak secrecy caching capacities, and also derive the sufficient finite field sizes for achieving the capacities. Finally, we propose optimal secure codes for exact partial repair, in which the recovered packets are exactly the same as erased packets.
|
|
