Дисертації з теми "Coded data storage"

Recent attempts to increase the capacity of the compact disc (CD) and digital versatile disc (DVD) have explored the use of multilevel recording instead of binary recording. Systems that achieve an increase in capacity of about three times that of conventional CD have been proposed for production. Marks in these systems are multilevel and fixed-length as opposed to binary and variable length in CD and DVD. The main objective of this work is to evaluate the performance of multilevel ($M$-ary) runlength-limited (RLL) coded sequences in optical data storage. First, the waterfilling capacity of a multilevel optical recording channel ($M$-ary ORC) is derived and evaluated. This provides insight into the achievable user bit densities, as well as a theoretical limit against which simulated systems can be compared. Then, we evaluate the performance of RLL codes on the $M$-ary ORC. A new channel model that includes the runlength constraint in the transmitted signal is used. We compare the performance of specific RLL codes, namely $M$-ary permutation codes, to that of real systems using multilevel fixed-length marks for recording and the theoretical limits. The Viterbi detector is used to estimate the original recorded symbols from the readout signal. Then, error correction is used to reduce the symbol error probability. We use a combined ECC/RLL code for phrase encoding. We evaluate the use of trellis coded modulation (TCM) for amplitude encoding. The detection of the readout signal is also studied. A post-processing algorithm for the Viterbi detector is introduced, which ensures that the detected word satisfies the code constraints. Specifying the codes and detector for the $M$-ary ORC gives a complete system whose performance can be compared to that of the recently developed systems found in the literature and the theoretical limits calculated in this research.

There exists many companies which wish to transition toward a more digital workflow. However, many of these companies lack the technical expertise required to undertake such an endeavor. To assist companies in this area, a digitization process model could be used as a stepping-stone toward successful digitization. Currently, however, there exists no such digitization process model. The purpose of this thesis is to suggest such a digitization process model. The goal is to help companies in digitizing their documents and their workflow. The research question used to reach this goal pertains to how a digitization process model should be structured. Due to the lack of currently existing digitization process models, different process models within the field of software engineering where analyzed as a basis. The research was qualitative and explorative in its nature, and it followed design science as its research paradigm. An extensive literature study was conducted before development of the model began. The model was evaluated using interviews together with action research. These interviews focused on evaluating the model based on five criteria which had been defined: (1) interviewee credibility, (2) semantic correctness, (3) syntactic correctness, (4) usefulness, and (5) process flexibility. The results of this thesis is the company document digitization process model (CODED), which, as the name suggests, is a proposed process model for document digitization. This model has been based on information gathered by, partly the literature study, and partly the interviews. The literature study proved the model to be unique, since no similar model existed prior to this thesis. While the interviews proved the model to be valid, since it accomplished all evaluation criteria which had been defined.
Det är många företag som vill gå mot att digitalisera sitt arbetsflöde. Många av dessa företag har däremot en avsaknad av den tekniska expertis som krävs. För att assistera företag i detta skulle en processmodell kunna användas som ett redskap för framgångsrik dokumentdigitalisering. Problemet är att det just nu inte existerar någon sådan processmodell för dokumentdigitalisering. Syftet med denna avhandling är att föreslå en processmodell för digitalisering. Målet är att hjälpa företag i att digitalisera både deras dokument och deras arbetsflöde. Hur en sådan processmodell skulle kunna struktureras är denna rapports forskningsfråga. Det fanns ingen existerande modell att utgå ifrån. Därför användes andra modeller inom området för programvaruteknik som en bas under forskningen. Forskningen var kvantitative och explorativ, och den använde designvetenskap som ett forskningsparadigm. En omfattande litteraturstudie genomfördes innan utvecklingen av processmodellen påbörjades. Modellen evaluerades utifrån intervjuer tillsammans med aktionsforskning. Där intervjuerna har fokuserat på att evaluera modellen utifrån fem kriterier: (1) trovärdighet, (2) semantisk korrekthet, (3) syntaktisk korrekthet, (4) användbarhet, och (5) flexibilitet. Resultatet av denna avhandling är ett förslag till en processmodell för att digitalisera dokument, vid namnet CODED (company document digitization process model). Den föreslagna modellen har baserat både på information som samlats från litteraturstudien, och information från intervjuerna. Litteraturstudien visade att processmodellen är unik, då det ej existerade någon likartad modell tidigare. Intervjuerna visade att modellen är valid, då den uppfyllde de definierade evalueringskriterierna.

Les centres de données sont responsables d'une part importante de la consommation mondiale d'énergie. Cette consommation devrait augmenter dans les années à venir, en raison de la demande croissante de services pour les centres de données. Par conséquent, le besoin d'opérations de centres de données efficaces sur le plan énergétique et à faible émission de carbone augmente rapidement.Cette recherche se concentre sur la conception et la mise en œuvre d'un centre de données à faible émission de carbone et à haut rendement énergétique, alimenté par l'énergie solaire et l'hydrogène, ce qui lui confère une indépendance par rapport au réseau électrique. En conséquence, le centre de données est limité par la limite supérieure de la consommation d'énergie, qui est de 10KWh. La contrainte d'utilisation maximale de l'énergie impose plusieurs défis à la conception, à l'utilisation de l'énergie et à la durabilité du centre de données.Ce travail contribue tout d'abord à la conception d'un centre de données à faible consommation d'énergie tout en respectant la contrainte énergétique globale. Nous avons essayé d'économiser l'énergie du centre de données par un choix judicieux du matériel tout en conservant les performances du centre de données. La deuxième contribution de notre travail fournit des protocoles précieux tels que la réparation paresseuse dans le stockage distribué des données, le placement des tâches et les techniques de gestion de l'énergie pour réduire davantage la consommation d'énergie du centre de données. Grâce aux efforts combinés du bon choix de matériel, de protocoles et de techniques, nous avons réduit de manière significative la consommation d'énergie globale du centre de données
Data centers are responsible for a significant portion of global energy consumption. This consumption is expected to grow in the coming years, driven by the increasing demand for data center services. Therefore, the need for energy-efficient, low-carbon data center operations is growing rapidly.This research focuses on designing and implementing a low-carbon, energy-efficient data center powered by solar and hydrogen, granting it independence from the power grid. As a result, the data center is limited by the upper bound on the energy consumption, which is 10KWh. The maximum usage of energy-constraint imposes several challenges to the design, energy usage, and sustainability of the data center.The work first contributes to designing a low-power budget data center while respecting the overall energy constraint. We tried to save the energy usage of the data center through the right choice of hardware while keeping the performance of the data center intact. The second contribution of our work provides valuable protocols like lazy repair in distributed data storage, job placement, and power management techniques to further reduce the data center's energy usage. With the combined efforts of the right choice of hardware, protocols, and techniques, we significantly reduced the overall energy consumption of the data center

This dissertation presents a new class of irregular low-density parity-check (LDPC) codes of moderate length and high rate. The codes in this class admit low-complexity encoding and have lower error rate floors than other irregular LDPC code design approaches. It is also shown that this class of LDPC codes is equivalent to a class of systematic serial turbo codes and is an extension of irregular repeat-accumulate codes. A code design algorithm based on the combination of density evolution and differential evolution optimization with a modified cost function is presented. Moderate-length, high-rate codes with no error-rate floors down to a bit error-rate of 10-9 are presented. Although our focus is on moderate-length, high-rate codes, the proposed coding scheme is applicable to irregular LDPC codes with other lengths and rates. Applications of these codes to magnetic data storage and wireless transmission channels are then studied. In the case of data storage, we assume an EPR4 partial response model with noise bursts which models media defects and thermal asperities. We show the utility of sending burst noise channel state information to both the partial response detector and the decoder. Doing so eliminates the error rate curve flattening seen by other researchers. The simulation results presented have demonstrated that LDPC codes are very effective against noise bursts and, in fact, are superior to Reed-Solomon codes in the regime simulated. We also have presented an algorithm for finding the maximum resolvable erasure-burst length, Lmax, for a given LDPC code. The simulation results make the possibility of an error control system based solely on an LDPC code very promising. For the wireless communication channel, we assume two types of Gilbert-Elliott channels and design LDPC codes for such channels. Under certain assumptions, this model leads us to what we call the burst-erasure channel with AWGN (BuEC-G), in which bits are received in Gaussian noise or as part of an erasure burst. To design codes for this channel, we take a "shortcut" and instead design codes for the burst-erasure channel (BuEC) in which a bit is received correctly or it is received as an erasure, with erasures occurring in bursts. We show that optimal BuEC code ensembles are equal to optimal binary erasure channel (BEC) code ensembles and we design optimal codes for these channels. The burst-erasure efficacy can also be measured by the maximum resolvable erasure-burst length Lmax. Finally, we present error-rate results which demonstrate the superiority of the designed codes on the BuEC-G over other codes that appear in the literature.

The cavity supports the orthogonal reference beam families as its eigenmodes while enhancing the reference beam power. Such orthogonal eigenmodes are used as additional degree of freedom to multiplex data pages, consequently increase storage densities for volume Holographic Data Storage Systems (HDSS) when the maximum number of multiplexed data page is limited by geometrical factor. Image bearing holograms are multiplexed by orthogonal phase code multiplexing via Hermite- Gaussian eigenmodes in a Fe: LiNbO3 medium with a 532 nm laser at multiple Bragg angles by using Liquid Crystal on Silicon (LCOS) spatial light modulators (SLMs) in reference arms. Total of nine holograms are recorded with three angular and three eigenmode.

In the last decade, cloud storage systems has experienced a rapid growth to account for an important part of cloud-based services. Among them, OpenStack Swift is a open source software to implement an object storage system. Meanwhile, storage providers are making great effort to ensure the quality of their services. One of the key factors of storage systems is the data durability. Fault tolerance mechanisms play an important role in ensuring the data availability. Existing approaches like replication and RAID are used to protect data from lost, while with their own drawbacks. Erasure coding comes as a novel concept applied in the storage systems for the concern of data availability. Studies showed that it is able to provide fault tolerance with redundancies while reducing the capacity overhead, offering a tradeoff between performanc eand cost. This project did an in-depth investigation on the OpenStack Swift and the erasure coding approach. Analysis on erasure coded and replication systems are performed to compare the features of both approaches. A prototype of custom erasure code is implemented as an extension to Swift, offering data storage with promising reliability and performance.
Molnlagring system har upplevt en snabb tillväxt att spela en viktig roll i molnbaserade tjänster under det senaste decenniet. Bland annat är Openstack Swift en programvara med öppen källköd som ska införa som object lagring system. Dessutom har molnlagring system gjort stora ansträngar för att säkerställa kvaliten av sina tjänster. En av de viktigaste faktorerna av molnlagring system är datashållbarheten. Feltoleransmekanismer spelar en viktig roll för att grantera datastillgångår. Bland annat finns det Replikering och RAID används för att skydda data från förlorade trots att de drabbas av många nackdelar. Erasure kodning kommer som nytt koncept som kan tillämpas i lagringssystem för angelägenheten av datastillgänglighet. Forskningar har visat att det kan ge feltolerans med uppsägningar och samtidigt minska kapaciteten och erbjuder en kompromiss mellan prestanda och kostnad. Projekten gjorde en fördjupad undersökning på Openstack Swift och erasure kodning. Analyserna på raderingskodade och replikationssystem har vidtagits för att jämföra egenskaperna hos båda metoder. En prototyp av anpassade radering koden är att implementeras som förlängning till Swift och erbjuder datalagring med lovande tillförlitlighet och prestanda.

Encara que l'emmagatzematge online d'informació és un negoci creixent, no està exempt de problemàtiques, una d'elles és la persistència i accessibilitat de les dades. Cal replicar les dades de manera que si es perd una còpia no es perdi la informació de forma definitiva. Malauradament, la replicació de dades (coneguda com a ``backup'') no és una solució eficient, ja que introdueix molta redundància que provoca sobre costos. Els codis correctors d'errors són coneguts per augmentar la persistència i l'accessibilitat de les dades minimitzant la redundància necessària. Però el seu us introdueix altres problemes com l'anomenat ``repair problem'': com substituir un node d'emmagatzematge descarregant el mínim de dades dels altres nodes. En aquesta dissertació, estudiem l'estat de l'art pel que fa als codis aplicats a sistemes d'emmagatzematge distribuïts, com per exemple el ``cloud storage''. També ens introduïm al ``repair problem'' des de la vessant més aplicada, usant topologies de sistemes reals com els ``data centers''. Concretament, aportem una família de codis regeneratius que anomenem quasi-cyclic flexible regenerating codes i que es caracteritza per minimitzar l'ús de recursos computacionals en el procés de regeneració d'un node. Alhora, aquesta solució minimitza les dades emmagatzemades i l'ample de banda necessari per regenerar un node que falla. També estudiem el cas en que els costos de descàrrega de les dades no són homogenis. En concret, ens centrem en el cas dels racks, on els nodes d'emmagatzematge estan distribuïts en racks, i el cost de descàrrega de dades dels nodes en el mateix rack és molt menor que el cost de descàrrega de dades dels nodes en un altre rack. Aquest nou model generalitza els models teòrics anteriors i ens permet comprovar que els costos poden disminuir si adaptem el model teòric a la topologia concreta del sistema d'emmagatzematge distribuït.
Online data storage is often regarded as a growing business, yet many unresolved issues linger in this specific field and prevent researchers from driving it to full capacity. Data replication (most commonly known as backup) is simply not efficient when improving persistence and accessibility of such data. Error correcting codes are known for their efficiency when adding redundancy to avoid lose of information. Unfortunately, the use of error correcting codes entail additional problems such as the repair problem: how do we replace a storage node downloading as less data as possible from other nodes. In this dissertation, we deepen on state-of-the-art of codes applied to distributed storage systems. Additionally, a family of regenerative codes which we call quasi-cyclic flexible regenerating codes is provided. Quasi-cyclic flexible minimum storage regenerating (QCFMSR) codes are constructed and their existence is well-proven. Quasi-cyclic flexible regenerating codes with minimum bandwidth constructed from a base QCFMSR code are also provided. Quasi-cyclic flexible regenerating codes are very interesting because of their simplicity and low complexity. They allow exact repair-by-transfer in the minimum bandwidth case and an exact pseudo repair-by-transfer in the MSR case, where operations are needed only when a new node enters into the system replacing a lost one. Finally, we propose a new model whereby storage nodes are placed in two racks. This unprecedented two-rack model is generalized to any number of racks. In this specific set-up, storage nodes have different repair costs depending on the rack where they are placed. A threshold function, which minimizes the amount of stored data per node and bandwidth needed to regenerate a failed node, is also shown. This latter threshold function generalizes those given by previous distributed storage models. Tradeoff curves obtained from this threshold function are compared with those obtained from previous models, and it is shown that this new model outperforms previous ones in terms of repair cost.

Whereas there are various initiatives to standardize the storage, processing and use of electronic patient information in the South African health sector, the sector is fragmented through the adoption of various approaches on national, provincial and district levels. Divergent IT systems are used in the public and private health sectors (“Recommendations of the Committee on …” 2003). Furthermore, general practitioners in some parts of the country still use paper as a primary means of documentation and storage. Nonetheless, the use of computerized systems is increasing, even in the most remote rural areas. This leads to the exposure of patient information to various threats that are perpetuated through the use of information technology. Irrespective of the level of technology adoption by practitioners in private healthcare practice, the security and privacy of patient information remains of critical importance. The disclosure of patient information whether intentional or not, can have dire consequences for a patient. In general, the requirements pertaining to the privacy of patient information are controlled and enforced through the adoption of legislation by the governing body of a country. Compared with developed nations, South Africa has limited legislation to help enforce privacy in the health sector. Conversely, Australia, New Zealand and Canada have some of the most advanced legislative frameworks when it comes to the privacy of patient information. In this dissertation, the Australian, New Zealand, Canadian and South African health sectors and the legislation they have in place to ensure the privacy of health information, will be investigated. Additionally, codes of practice and guidelines on privacy of patient information for GPs, in the afore-mentioned countries, will be investigated to form an idea as to what is needed in creating and formulating a new code of practice for the South African GP, as well as a pragmatic tool (checklist) to check adherence to privacy requirements.

In this thesis design and optimization of several distributed algorithms in large-scale networked systems is studied. The studied algorithms operate on networks of autonomous agents in general including the sensor networks and the ad hoc networks. The main focus here is on distributed algorithms operating on large-scale networks. This is due to their robustness to node failure and ability to extend according to the size and topology of the system. Regarding the optimization of the studied algorithms, it is aimed to increase their convergence rate to their equilibrium state considering the constraints of the system including the available bandwidth, memory and power for each agent. The first topic addresses the optimization of two algorithms; namely the distributed random gossip algorithm and the distributed average consensus algorithm. The underlying graph of the network is exploited to provide an analytical solution to the semidefinite programming formulation of the problems. In the second topic, two distributed algorithms are proposed for increasing data persistency in wireless sensor networks based on LT and Raptor codes. In the proposed algorithms, the sensed data is disseminated using random walks with the non-uniform stationary distribution. A new distributed method is proposed for assigning the transition probabilities of the random walks. The third topic studies distributed coding of LT codes in Y networks where multiple sources communicate with the same destination through a common relay node. The Adaptive Distributed LT coding algorithm is proposed that combines the LT codes with the network coding technique. The fourth topic addresses optimization of the LT codes for short message lengths. Unlike previous formulations, the provided novel semidefinite programming formulation has finite number of constraints while it is free of approximation.

This thesis investigates the role of error-correcting codes in Distributed and Pervasive Computing. The main results are at the intersection of Security and Fault Tolerance for these environments. There are two primary areas that are explored in this thesis. 1. We have investigated protocols for large scale fault tolerant secure distributed storage. The two main concerns here are security and redundancy. In one arm of this research we developed SAFE, a distributed storage system based on a new protocol that offers a two-in-one solution to fault-tolerance and confidentiality. This protocol is based on cryptographic properties of error correction codes. In another arm, we developed esf, another prototype distributed persistent storage; esf facilitates seamless hardware extension of storage units, high resilience to loads and provides high availability. The main ingredient in its design is a modern class of erasure codes known as the {em Fountain Codes}. One problem in such large storage is the heavy overhead of the associated fingerprints needed for checking data integrity. esf deploys a clever integrity check mechanism by use of a data structure known as the {em Merkle Tree} to address this issue. 2. We also investigated the design of a new remote authentication protocol. Applications over long range wireless would benefit quite a bit from this design. We designed and implemented LAWN, a lightweight remote authentication protocol for wireless networks that deploys a randomized approximation scheme based on Error correcting codes. We have evaluated in detail the performance of LAWN; while it adds very low overhead of computation, the savings in bandwidth and power are quite dramatic.

Tato diplomová práce představuje model a prototyp kooperativního distributivního systému zálohování dat založeném na P2P komunikační síti. Návrh systému umožňuje uživatelům přispět svým lokálním volným místem na disku do systému výměnou za spolehlivé úložiště jejich dat u jiných uživatelů. Představené řešení se snaží splnit požadavky uživatelů na ukládání dat, zároveň však také řeší, jak se vypořádat s mírou nepředvídatelnosti uživatelů  ohledně poskytování volného místa. To je prováděno dvěma způsoby - využitím Reed - Solomon kódů a zároveň také tím, že poskytuje možnost nastavení parametrů dostupnosti. Jedním z těchto parametrů je časový rozvrh, který značí, kdy uživatel může nabídnout předvídatelný přínos do systému. Druhý parametr se týká spolehlivosti konkrétního uživatele v rámci jeho slíbeného časového úseku. Systém je schopen najít synchronizaci ukládaných dat na základě těchto parametrů. Práce se zaměřuje rovněž na řešení zabezpečení systému proti širšímu spektru možných útoků. Hlavním cílem je publikovat koncept a prototyp. Jelikož se jedná o relativně nové řešení, je důležitá také zpětná vazba od široké veřejnosti, která může produkt používat. Právě jejich komentáře a připomínky jsou podnětem pro další vývoj systému.

Relational databases are the most popular databases used by enterprise applications to store persistent data to this day. It gives a lot of flexibility and efficiency. A process called database normalization helps make sure that the database is free from redundancies and update anomalies. In a Database-First approach to software development, the database is designed first, and then an Object-Relational Mapping (ORM) tool is used to generate the programming classes (data layer) to interact with the database. Finally, the business logic code is written to interact with the data layer to persist the business data to the database. However, in modern application development, a process called Code-First approach evolved where the domain classes and the business logic that interacts with the domain classes are written first. Then an Object Relational Mapping (ORM) tool is used to generate the database from the domain classes. In this approach, since database design is not a concern, software programmers may ignore the process of database normalization altogether. To help software programmers in this process, this thesis takes the theory behind the five database normal forms (1NF - 5NF) and proposes Five Class Normal Forms (1CNF - 5CNF) that software programmers may use to normalize their domain classes. This thesis demonstrates that when the Five Class Normal Forms are applied manually to a class by a programmer, the resulting database that is generated from the Code-First approach is also normalized according to the rules of relational theory.

近年雲存儲發展迅速，它具彈性的收費模式還有使用上的便利性吸引了不少用家把它當作一個備份的平台，如何保障雲端上資料的完整性也就成了一項重要的課題。我們試著探討如何能有效地在客戶端檢查雲端上資料的完整性，並且在探測到雲存儲節點故障以後如何有效地進行修復。抹除碼(Erasure codes)透過產生冗餘，令編碼過後的資料能允許一定程度的缺片。雲端使用者可以利用抹除碼把檔案分散到不同的雲節點，即使其中一些節點壞了用戶還是能透過解碼餘下的資料來得出原檔。我們的研究是基於一種叫再造編碼(Regenerating code)的新興抹除碼。再造編碼借用了網絡編碼(Network coding)的概念，使得在修復錯誤節點的時候並不需要把完整的原檔先重構一遍，相比起一些傳統的抹除碼（如里德所羅門碼Reed-Solomoncode）能減少修復節點時需要下載的資料量。其中我們在FMSR這門再造編碼上實現了一個能有效檢測錯誤的系統FMSR-DIP。FMSR-DIP的好處是在檢測的時候只需要下載一小部份的資料，而且不要求節點有任何的編碼能力，可以直接對應現今的雲存儲。為了驗證我們系統的實用性，我們在雲存儲的測試平台上運行了一系列的測試。
To protect outsourced data in cloud storage against corruptions, enabling integrity protection, fault tolerance, and efficient recovery for cloud storage becomes critical. To enable fault tolerance from a client-side perspective, users can encode their data with an erasure code and stripe the encoded data across different cloud storage nodes. We base our work on regenerating codes, a recently proposed type of erasure code that borrows the concept of network coding and requires less repair traffic than traditional erasure codes during failure recovery. We study the problem of remotely checking the integrity of regenerating-coded data against corruptions under a real-life cloud storage setting. Specifically, we design a practical data integrity protection (DIP) scheme for a specific regenerating code, while preserving the intrinsic properties of fault tolerance and repair traffic saving. Our DIP scheme is designed under the Byzantine adversarial model, and enables a client to feasibly verify the integrity of random subsets of outsourced data against general or malicious corruptions. It works under the simple assumption of thin-cloud storage and allows different parameters to be fine-tuned for the performance-security trade-off. We implement and evaluate the overhead of our DIP scheme in a cloud storage testbed under different parameter choices. We demonstrate that remote integrity checking can be feasibly integrated into regenerating codes in practical deployment.
Detailed summary in vernacular field only.
Chen, Chuk Hin Henry.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2012.
Includes bibliographical references (leaves 38-41).
Abstracts also in Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Preliminaries --- p.4
Chapter 2.1 --- FMSR Implementation --- p.4
Chapter 2.2 --- Threat Model --- p.6
Chapter 2.3 --- Cryptographic Primitives --- p.7
Chapter 3 --- Design --- p.8
Chapter 3.1 --- Design Goals --- p.8
Chapter 3.2 --- Notation --- p.9
Chapter 3.3 --- Overview of FMSR-DIP --- p.11
Chapter 3.4 --- Basic Operations --- p.11
Chapter 3.4.1 --- Upload operation --- p.11
Chapter 3.4.2 --- Check operation --- p.13
Chapter 3.4.3 --- Download operation --- p.15
Chapter 3.4.4 --- Repair operation --- p.16
Chapter 4 --- Implementation --- p.17
Chapter 4.1 --- Integration of DIP into NCCloud --- p.17
Chapter 4.2 --- Instantiating Cryptographic Primitives --- p.18
Chapter 4.3 --- Trade-off Parameters --- p.19
Chapter 5 --- Security Analysis --- p.22
Chapter 5.1 --- Uses of Security Primitives --- p.22
Chapter 5.2 --- Security Guarantees --- p.23
Chapter 5.2.1 --- Corrupting an AECC Stripe --- p.23
Chapter 5.2.2 --- Picking Corrupted Bytes for Checking --- p.25
Chapter 5.2.3 --- Putting It All Together --- p.26
Chapter 6 --- Evaluations --- p.27
Chapter 6.1 --- Running Time Analysis --- p.27
Chapter 6.2 --- Monetary Cost Analysis --- p.30
Chapter 6.3 --- Summary --- p.33
Chapter 7 --- Related Work --- p.34
Chapter 8 --- Conclusions --- p.37
Bibliography --- p.38

碩士
國立交通大學
資訊科學與工程研究所
101
In recent years, network coding plays a key role in distributed storage systems, because of high reliability, security, and low storage cost. However, network coding-based distributed storage systems face an eavesdropping problem when transmitting the repairing data from remote datacenters. This problem is especially crucial in distributed network coded storage systems because more repair bandwidth and repair links are required, compared to conventional replication. In this thesis, we propose an optimization approach to compute the minimum storage according to the required security level. Our numerical results demonstrate that there exists an optimal tradeoff between remote repair bandwidth and storage cost. Moreover, we analyze the relation between security level requirement and the number of remote and local storage nodes, storage cost, data reliability, and secrecy capacity.

This thesis deals with the problem of code design in the setting of distributed storage systems consisting of multiple storage nodes, storing many different data les. A primary goal in such systems is the efficient repair of a failed node. Regenerating codes and codes with locality are two classes of coding schemes that have recently been proposed in literature to address this goal. While regenerating codes aim to minimize the amount of data-download needed to carry out node repair, codes with locality seek to minimize the number of nodes accessed during node repair. Our focus here is on linear codes with locality, which is a concept originally introduced by Gopalan et al. in the context of recovering from a single node failure. A code-symbol of a linear code C is said to have locality r, if it can be recovered via a linear combination of r other code-symbols of C. The code C is said to have (i) information-symbol locality r, if all of its message symbols have locality r, and (ii) all-symbol locality r, if all the code-symbols have locality r. We make the following three contributions to the area of codes with locality. Firstly, we extend the notion of locality, in two directions, so as to permit local recovery even in the presence of multiple node failures. In the first direction, we consider codes with \local error correction" in which a code-symbol is protected by a local-error-correcting code having local-minimum-distance 3, and thus allowing local recovery of the code-symbol even in the presence of 2 other code-symbol erasures. In the second direction, we study codes with all-symbol locality that can recover from two erasures via a sequence of two local, parity-check computations. When restricted to the case of all-symbol locality and two erasures, the second approach allows, in general, for design of codes having larger minimum distance than what is possible via the rst approach. Under both approaches, by studying the generalized Hamming weights of the dual codes, we derive tight upper bounds on their respective minimum distances. Optimal code constructions are identified under both approaches, for a class of code parameters. A few interesting corollaries result from this part of our work. Firstly, we obtain a new upper bound on the minimum distance of concatenated codes and secondly, we show how it is always possible to construct the best-possible code (having largest minimum distance) of a given dimension when the code's parity check matrix is partially specified. In a third corollary, we obtain a new upper bound for the minimum distance of codes with all-symbol locality in the single erasure case. Secondly, we introduce the notion of codes with local regeneration that seek to combine the advantages of both codes with locality as well as regenerating codes. These are vector-alphabet analogues of codes with local error correction in which the local codes themselves are regenerating codes. An upper bound on the minimum distance is derived when the constituent local codes have a certain uniform rank accumulation (URA) property. This property is possessed by both the minimum storage regenerating (MSR) and the minimum bandwidth regenerating (MBR) codes. We provide several optimal constructions of codes with local regeneration, where the local codes are either the MSR or the MBR codes. The discussion here is also extended to the case of general vector-linear codes with locality, in which the local codes do not necessarily have the URA property. Finally, we evaluate the efficacy of two specific coding solutions, both possessing an inherent double replication of data, in a practical distributed storage setting known as Hadoop. Hadoop is an open-source platform dealing with distributed storage of data in which the primary aim is to perform distributed computation on the stored data via a paradigm known as Map Reduce. Our evaluation shows that while these codes have efficient repair properties, their vector-alphabet-nature can negatively a affect Map Reduce performance, if they are implemented under the current Hadoop architecture. Specifically, we see that under the current architecture, the choice of number processor cores per node and Map-task scheduling algorithm play a major role in determining their performance. The performance evaluation is carried out via a combination of simulations and actual experiments in Hadoop clusters. As a remedy to the problem, we also pro-pose a modified architecture in which one allows erasure coding across blocks belonging to different les. Under the modified architecture, the new coding solutions will not suffer from any Map Reduce performance-loss as seen in the original architecture, while retaining all of their desired repair properties

This thesis deals with the problem of code design in the setting of distributed storage systems consisting of multiple storage nodes, storing many different data les. A primary goal in such systems is the efficient repair of a failed node. Regenerating codes and codes with locality are two classes of coding schemes that have recently been proposed in literature to address this goal. While regenerating codes aim to minimize the amount of data-download needed to carry out node repair, codes with locality seek to minimize the number of nodes accessed during node repair. Our focus here is on linear codes with locality, which is a concept originally introduced by Gopalan et al. in the context of recovering from a single node failure. A code-symbol of a linear code C is said to have locality r, if it can be recovered via a linear combination of r other code-symbols of C. The code C is said to have (i) information-symbol locality r, if all of its message symbols have locality r, and (ii) all-symbol locality r, if all the code-symbols have locality r. We make the following three contributions to the area of codes with locality. Firstly, we extend the notion of locality, in two directions, so as to permit local recovery even in the presence of multiple node failures. In the first direction, we consider codes with \local error correction" in which a code-symbol is protected by a local-error-correcting code having local-minimum-distance 3, and thus allowing local recovery of the code-symbol even in the presence of 2 other code-symbol erasures. In the second direction, we study codes with all-symbol locality that can recover from two erasures via a sequence of two local, parity-check computations. When restricted to the case of all-symbol locality and two erasures, the second approach allows, in general, for design of codes having larger minimum distance than what is possible via the rst approach. Under both approaches, by studying the generalized Hamming weights of the dual codes, we derive tight upper bounds on their respective minimum distances. Optimal code constructions are identified under both approaches, for a class of code parameters. A few interesting corollaries result from this part of our work. Firstly, we obtain a new upper bound on the minimum distance of concatenated codes and secondly, we show how it is always possible to construct the best-possible code (having largest minimum distance) of a given dimension when the code's parity check matrix is partially specified. In a third corollary, we obtain a new upper bound for the minimum distance of codes with all-symbol locality in the single erasure case. Secondly, we introduce the notion of codes with local regeneration that seek to combine the advantages of both codes with locality as well as regenerating codes. These are vector-alphabet analogues of codes with local error correction in which the local codes themselves are regenerating codes. An upper bound on the minimum distance is derived when the constituent local codes have a certain uniform rank accumulation (URA) property. This property is possessed by both the minimum storage regenerating (MSR) and the minimum bandwidth regenerating (MBR) codes. We provide several optimal constructions of codes with local regeneration, where the local codes are either the MSR or the MBR codes. The discussion here is also extended to the case of general vector-linear codes with locality, in which the local codes do not necessarily have the URA property. Finally, we evaluate the efficacy of two specific coding solutions, both possessing an inherent double replication of data, in a practical distributed storage setting known as Hadoop. Hadoop is an open-source platform dealing with distributed storage of data in which the primary aim is to perform distributed computation on the stored data via a paradigm known as Map Reduce. Our evaluation shows that while these codes have efficient repair properties, their vector-alphabet-nature can negatively a affect Map Reduce performance, if they are implemented under the current Hadoop architecture. Specifically, we see that under the current architecture, the choice of number processor cores per node and Map-task scheduling algorithm play a major role in determining their performance. The performance evaluation is carried out via a combination of simulations and actual experiments in Hadoop clusters. As a remedy to the problem, we also pro-pose a modified architecture in which one allows erasure coding across blocks belonging to different les. Under the modified architecture, the new coding solutions will not suffer from any Map Reduce performance-loss as seen in the original architecture, while retaining all of their desired repair properties

Wireless Sensor Networks (WSNs) that use tiny wireless devices capable of communicating, processing, and sensing promise to have applications in virtually all fields. Smart homes and smart cities are just few of the examples that WSNs can enable. Despite their potential, WSNs suffer from reliability and energy limitations. In this study, we address the problem of designing Distributed Data Storage Systems (DDSSs) for WSNs using decentralized erasure codes. A unique aspect of WSNs is that their data is inherently decentralized. This calls for a decentralized mechanism for encoding and decoding. We propose a distributed data storage framework to increase data survivability in WSNs. The framework utilizes Decentralized Erasure Codes for Data Survivability (DEC-DS) which allow for determining the amount of redundancy required in both hardware and data to allow sensed data to survive failures in the network. To address the energy limitations, we show two approaches to implement the proposed solution in an energy efficient manner. The two approaches employ Random Linear Network Coding (RLNC) to exploit coding opportunities in order to save energy and in turn prolong network life. A routing based scheme, called DEC Encode-and-Forward (DEC-EaF), applies to networks with routing capability, while the second, DEC Encode-and-Disseminate (DEC-EaD), uses a variation of random walk to build the target code in a decentralized fashion. We also introduce a new decentralized approach to implement Luby Transform (LT)-Codes based DDSSs. The scheme is called Decentralized Robust Soliton Storage (DRSS) and it operates in a decentralized fashion and requires no coordination between sensor nodes. The schemes are tested through extensive simulations to evaluate their performance. We also compare the proposed schemes to similar schemes in the literature. The comparison considers energy efficiency as well as coding related aspects. Using the proposed schemes can greatly improve the reliability of WSNs especially under harsh working conditions.
Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2013-09-30 22:43:04.509

This thesis makes progress towards the fundamental understanding of heterogeneous and dynamic information systems and the way that we store and process massive data-sets. Reliable large-scale data storage: Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. However, traditional erasure codes are associated with high repair cost that is often considered an unavoidable price to pay. In this thesis, we show how to overcome these limitations. We construct novel families of erasure codes that are optimal under various repair cost metrics, while achieving the best possible reliability. We show how these modern storage codes significantly outperform traditional erasure codes. Low-rank approximations for large-scale data processing: A central goal in data analytics is extracting useful and interpretable information from massive data-sets. A challenge that arises from the distributed and large-scale nature of the data at hand, is having algorithms that are good in theory but can also scale up gracefully to large problem sizes. Using ideas from prior work, we develop a scalable lowrank optimization framework with provable guarantees for problems like the densest k-subgraph (DkS) and sparse PCA. Our experimental findings indicate that this low-rank framework can outperform the state-of-the art, by offering higher quality and more interpretable solutions, and by scaling up to problem inputs with billions of entries.
text

The reliable storage of Big Data across a spatially distributed network of nodes, calls for erasure-correcting codes that in addition to protecting against data loss, can also efficiently handle node repair. The need for node repair could arise on account of device failure, need for a maintenance reboot, or simply because the node is busy serving other demands. An important consideration here is the rate of the code, which is the ratio of the number of data symbols to the total amount of storage needed to reliably store these data symbols. In response, coding theorists have come up with two new classes of codes, known respectively as regenerating codes and Locally Recoverable Codes (LRC). While the focus of the thesis is on LRC, there are also contributions to the theory of regenerating codes. Contributions to LRC: A LRC is quite simply, a code where a given code symbol can be recovered by contacting at most r other code symbols, where the parameter r is much smaller than the dimension k of the code. A LRC with sequential recovery, is a code that can recover from an arbitrary set of trerasures in t steps in a sequential fashion. Each step recovers an erased symbol and makes use of at most r other code symbols comprising of unerased symbols as well as previously recovered symbols. In this thesis, a tight upper bound on the rate of LRC with sequential recovery is provided, for any value of the number t of erasures and any value of the locality parameter r ≥ 3. This bound proves an earlier conjecture due to Song, Cai and Yuen. While the bound is valid irrespective of the field over which the code is defined, a matching construction of binary codes that achieve the upper bound on rate is also presented. Contributions to Regenerating Codes: Regenerating codes aim to minimize the amount of data download needed to repair a failed node. Regenerating codes are linear codes that operate over a vector alphabet, i.e., each code symbol in a regenerating code is a vector of α symbols drawn from a field F. An important open question relates to the minimum possible value of α for a given storage overhead. Here we present tight lower bounds on α for the case when the codes belong to a certain class of codes called MSR codes as well as have the property of optimal access, i.e., symbols are accessed and transmitted as such without any computation by helper node for repair of a failed node. Contribution to availability Codes: A code in which each code symbol can be recovered in t different ways using respectively t pairwise disjoint set of code symbols with each set of size at most r is called a code with t-availability. The contributions of the thesis in the direction of t-availability codes include improved upper bounds on the minimum distance dmin of this class of codes, both with and without a constraint on the size q of the code-symbol alphabet. An improved upper bound on code rate R is also provided for a subclass of t-availability codes, termed as codes with strict availability. Among the class of t-availability codes, codes with strict availability typically have high rate. A complete characterization of optimal tradeoff between rate and fractional minimum distance for a special class of t-availability codes is also provided. There are additional results which are not mentioned above including results relating to a class of codes called maximum recoverable codes.

博士
國立中央大學
電機工程學系
86
Some data storage systems use AC-coupling devices which can not convey DC signals. DC-free input signals are required by such a channel. There are two methods to generate DC-free signals to satisfy channel requirements: one is charge constrained modulation codes; the other one is combining (d,k) codes and equalization. In this dissertation, these two methods are investigated. Charge constrained modulations codes discussed in our works includes (1) (d,k;C) codes for peak detection channels (2) (0,G/I;C) codes for partial response channels (3) (d,k;C,n) codes for multitrack recording systems. Schneider equalizers add adequate pulses in recording signal to achieve DC-free. This method is applied on a magnetic recording systems to achieve higher recording density.

Error correcting codes (ECCs) are essential to transmission and data storage sys-tems to protect the information from errors introduced by noisy communication channels. There are two main classes of ECCs, namely algebraic and iterative ECCs. While iterative ECCs like low-density parity-check (LDPC) codes provide improved performance in the waterfall region albeit exhibiting flooring effect for not so well-designed codes, algebraic ECCs like Bose–Chaudhuri–Hocquenghem (BCH) and Reed Solomon (RS) codes provide guaranteed error correction capability irrespective of the waterfall or error floor regions. Due to recent advancements in higher-dimensional data storage technologies like shingled and 2-D magnetic recording (TDMR), 3-DNAND flash memories, and holographic memories, native 2-Dsignal processing and coding techniques are re-quired to overcome inter-symbol interference (ISI) and noise leading to 2-Dburst and random errors. With high data densities beyond 2 Tb/in2 in practical TDMR channels, reliable information storage and retrieval require highly efficient ECCs. The primary motivation of this dissertation is to design efficient hardware architectures for error correcting codes pertaining to 1-Dand 2-Dstorage channels. The focus topics are as follows: (i) First, we designed a high-throughput 1-DLDPC decoder using layered and non-layered min-sum algorithm based on non-uniform quantization on a field programmable gate array (FPGA) kit. Unlike the standard state-of-the-art uniform quantization used in virtually all decoder circuits, our non-uniform quantization technique achieves a slight performance improvement in the signal-to-noise ratio (SNR) using the same bit budget as the uniform case. Using 1 bit lesser than uniform quantization, it yields area savings for the block RAMs used for storing intermediate check node and variable node messages. (ii) We proposed efficient encoding and decoding hardware architectures for (n,k), t-error correcting BCH product codes in the frequency domain. Using the properties of conjugate classes over a finite field, we reduced the algorithmic complexity of the encoder, leading to a significant reduction in the hardware complexity. v vi A low-latency (2t + 2) decoder for the above encoder is also designed. For a particular case of n = 15 and t = 2, the architectures were implemented on a FPGA kit, giving high throughputs of 22.5 Gbps and 5.6 Gbps at 100 MHz for the encoder and decoder respectively. (iii) We proposed fast and efficient hardware architectures for a 2-D BCH code of size n × n, with a quasi-cyclic burst error correction capability of t × t, in the frequency domain for data storage applications. A fully parallel encoder with the ability to produce an output every clock cycle was designed. Using conjugate class properties of finite fields, the algorithmic complexity of the encoder was significantly reduced, leading to a reduction in the number of gates by about 94% compared to the brute force implementation per 2-Dinverse discrete finite field Fourier transform (IDFFFT) point for a 15 × 15, t = 2, 2-DBCH code. We also designed a pipelined, low-latency decoder for the above encoder. The algorithmic complexities of various pipeline stages of the decoder were reduced significantly using finite field properties, reducing the space complexity of the entire decoder. For a particular case of n = 15 and t = 2, the architectures were implemented targeting a Kintex 7 KC-705 FPGA kit, giving high throughputs of 22.5 Gbps and 5.6 Gbps at 100 MHz for the encoder and decoder, respectively. (iv) We developed an efficient design architecture for finding the roots of a bi-variate polynomial over GF(q) by extending the Chien search procedure to two-dimensions. The complexity of the Chien search was reduced to an order of the number of conjugacy classes over GF(qλ), leading to a significant reduction in the computational complexity. We provided an efficient design architecture for our algorithm towards a circuit realization, useful for decoding of 2-Dalgebraic ECCs. v) Native 2-DLDPC codes provide 2-Dburst erasure correction capability and have promising applications in TDMR technology. Though carefully constructed rastered 1-DLDPC codes can provide 2-Dburst erasure correction, they are not as efficient as 2-Dnative codes constructed for handling 2-Dspan of burst erasures. Our contributions are two-fold: (a) We propose a new 2-DLDPC code with girth greater than 4 by generating a parity check tensor through stacking permutation tensors of size p×p×p along the i,j,k axes. The permutations are achieved through circular shifts on an identity tensor along different co-ordinate axes in such a way that it provides a burst erasure correction capability of at least p×p. (b) We propose a fast, efficient, and scalable hardware architecture for a parallel 2-DLDPC decoder based on the proposed code construction for data storage applications. Through efficient indexing of the received messages in a RAM, we propose novel routing mechanisms for messages between the check nodes and variable nodes through a set of two barrel shifters, producing shifts along two axes. Through simulations, we show that the performance of the proposed 2-D LDPC codes match a 1-DQC-LDPC code, with a sharp waterfall drop of 3-4 orders of magnitude over ∼0.3 dB, for random errors over code sizes of ∼32 Kbits or equivalently ∼180×180 2-Darrays. Further, we prove that the proposed native 2-DLDPC codes outperform their 1-Dcounterparts in terms of 2-Dcluster erasure correction ability. For p = 16 and code arrays of size 48 × 48, we implemented the proposed design architecture on a Kintex-7 KC-705 FPGA kit, achieving a significantly high worst case throughput of 12.52 Gbps at a clock frequency of 163 MHz.

碩士
國立清華大學
資訊工程學系所
105
The cloud storage system has been popular recently due to the higher and higher demand of storage space. The cloud providers offer large but cheap storage service. People or companies use them and do not have to pay on hardware or electric utility. Companies can use these features to build its own storage service for benefit too. For cloud storage, erasure code can be used to improve data availability and have potential to reduce download time. Erasure code encode files into chunks and place them in different storage regions for higher availability. Besides, these chunks is smaller than the origin file that the download time can be reduced by using parallel downloading. These chunks can also improve the availability by placed at different regions for avoiding regions failure. However, each region owns different request cost, storage cost or even latency and bandwidth. Besides, users location can largely influence download latency and access cost. With these multiple issues, the main point is how to choose the candidate regions for chunks that can fulfill all requirements. In the past, most thesiss focus on specific features. However, the models from those research are not realistic enough. There are many aspects that we need to take into consideration for being closer to the real world. In this thesis, we propose the method with using erasure code and linear programming to include multiple requirements at the same time and find the best placement strategy. The experiment shows that our work can save money at most 66\% and have at most 50\% performance improvement.

The rapid growth of Cloud based services on the Internet invited many critical security attacks. Consumers and corporations who use the Cloud to store their data encounter a difficult trade-off of accepting and bearing the security, reliability, and privacy risks as well as costs in order to reap the benefits of Cloud storage. The primary goal of this thesis is to resolve this trade-off while minimizing total costs. This thesis presents a system framework that solves this problem by using erasure codes to add redundancy and security to users’ data, and by optimally choosing Cloud storage providers to minimize risks and total storage costs. Detailed comparative analysis of the security and algorithmic properties of 7 different erasure codes is presented, showing codes with better data security comes with a higher cost in computational time complexity. The codes which granted the highest configuration flexibility bested their peers, as the flexibility directly corresponded to the level of customizability for data security and storage costs. In-depth analysis of the risks, benefits, and costs of Cloud storage is presented, and analyzed to provide cost-based and security-based optimal selection criteria for choosing appropriate Cloud storage providers. A brief historical introduction to Cloud Computing and security principles is provided as well for those unfamiliar with the field. The analysis results show that the framework can resolve the trade-off problem by mitigating and eliminating the risks while preserving and enhancing the benefits of using Cloud storage. However, it requires higher total storage space due to the redundancy added by the erasure codes. The storage provider selection criteria will minimize the total storage costs even with the added redundancies, and minimize risks.

碩士
國立中央大學
光電科學與工程學系
106
In this thesis, an optical model considering the density of signal is proposed based on lateral shearing interferometry with use of sparse code through LPF. This model is applied to the conjugate of record side in holographic data storage system for analyzing the record point of the holographic disk. With this optical model, the shearing image in different signal density, modulation mode, filter size can be predicted. In simulation and experiment, the increase of storage capacity is at least 1.368 times by the limitation of twice.

This dissertation considers several coding techniques based on Reed-Solomon (RS) and low-density parity-check (LDPC) codes. These two prominent families of error-correcting codes have attracted a great amount of interest from both theorists and practitioners and have been applied in many communication scenarios. In particular, data storage systems have greatly benefited from these codes in improving the reliability of the storage media. The first part of this dissertation presents a unified framework based on rate-distortion (RD) theory to analyze and optimize multiple decoding trials of RS codes. Finding the best set of candidate decoding patterns is shown to be equivalent to a covering problem which can be solved asymptotically by RD theory. The proposed approach helps understand the asymptotic performance-versus-complexity trade-off of these multiple-attempt decoding algorithms and can be applied to a wide range of decoders and error models. In the second part, we consider spatially-coupled (SC) codes, or terminated LDPC convolutional codes, over intersymbol-interference (ISI) channels under joint iterative decoding. We empirically observe the phenomenon of threshold saturation whereby the belief-propagation (BP) threshold of the SC ensemble is improved to the maximum a posteriori (MAP) threshold of the underlying ensemble. More specifically, we derive a generalized extrinsic information transfer (GEXIT) curve for the joint decoder that naturally obeys the area theorem and estimate the MAP and BP thresholds. We also conjecture that SC codes due to threshold saturation can universally approach the symmetric information rate of ISI channels. In the third part, a similar analysis is used to analyze the MAP thresholds of LDPC codes for several multiuser systems, namely a noisy Slepian-Wolf problem and a multiple access channel with erasures. We provide rigorous analysis and derive upper bounds on the MAP thresholds which are shown to be tight in some cases. This analysis is a first step towards proving threshold saturation for these systems which would imply SC codes with joint BP decoding can universally approach the entire capacity region of the corresponding systems.