57 research outputs found
Motion detection: a neural network approach.
No full textby Yip Pak Ching.Thesis (M.Phil.)--Chinese University of Hong Kong, 1992.Includes bibliographical references (leaves 97-100).Chapter 1 --- Introduction --- p.1Chapter 1.1 --- Background --- p.1Chapter 1.2 --- The Objective of Machine Vision --- p.3Chapter 1.3 --- Our Goal --- p.4Chapter 1.4 --- Previous Works and Current Research --- p.5Chapter 1.5 --- Organization of the Thesis --- p.8Chapter 2 --- Human Movement Perception --- p.11Chapter 2.1 --- Basic Mechanisms of Vision --- p.11Chapter 2.2 --- Functions of Movement Perception --- p.12Chapter 2.3 --- Five Ways to Make a Spot of Light Appear to Move --- p.14Chapter 2.4 --- Real Movement --- p.15Chapter 2.5 --- Mechanisms for the Perception of Real Movement --- p.16Chapter 2.6 --- Apparent Motion --- p.18Chapter 3 --- Machine Movement Perception --- p.21Chapter 3.1 --- Introduction --- p.21Chapter 3.2 --- Perspective Transformation --- p.21Chapter 3.3 --- Motion Detection by Difference Image --- p.22Chapter 3.4 --- Accumulative Difference --- p.24Chapter 3.5 --- Establishing a Reference Image --- p.26Chapter 3.6 --- Optical Flow --- p.27Chapter 4 --- Neural Networks for Machine Vision --- p.30Chapter 4.1 --- Introduction --- p.30Chapter 4.2 --- Perceptron --- p.30Chapter 4.3 --- The Back-Propagation Training Algorithm --- p.33Chapter 4.4 --- Object Identification --- p.34Chapter 4.5 --- Special Technique for Improving the Learning Time and Recognition Rate --- p.36Chapter 5 --- Neural Networks by Supervised Learning for Motion Detection --- p.39Chapter 5.1 --- Introduction --- p.39Chapter 5.2 --- Three-Level Network Architecture --- p.40Chapter 5.3 --- Four-Level Network Architecture --- p.45Chapter 6 --- Rough Motion Detection --- p.50Chapter 6.1 --- Introduction --- p.50Chapter 6.2 --- The Rough Motion Detection Network --- p.51Chapter 6.3 --- The Correlation Network --- p.54Chapter 6.4 --- Modified Rough Motion Detection Network --- p.56Chapter 7 --- Moving Object Extraction --- p.59Chapter 7.1 --- Introduction --- p.59Chapter 7.2 --- Three Types of Images for Moving Object Extraction --- p.59Chapter 7.3 --- Edge Enhancement Network --- p.62Chapter 7.4 --- Background Remover --- p.63Chapter 8 --- Motion Parameter Extraction --- p.66Chapter 8.1 --- Introduction --- p.66Chapter 8.2 --- 2-D Motion Detection --- p.66Chapter 8.3 --- Normalization Network --- p.67Chapter 8.4 --- 3-D Motion Parameter Extraction --- p.70Chapter 8.5 --- Object Identification --- p.70Chapter 9 --- Motion Parameter Extraction from Overlapped Object Images --- p.72Chapter 9.1 --- Introduction --- p.72Chapter 9.2 --- Decision Network --- p.72Chapter 9.3 --- Motion Direction Extraction from Overlapped Object Images by Three-Level Network Model with Supervised Learning --- p.75Chapter 9.4 --- Readjustment Network for Motion Parameter Extraction from Overlapped Object Images --- p.79Chapter 9.5 --- Reconstruction of the Overlapped object Image --- p.82Chapter 10 --- The Integrated Motion Detection System --- p.87Chapter 10.1 --- Introduction --- p.87Chapter 10.2 --- System Architecture --- p.88Chapter 10.3 --- Results and Concluding Remarks --- p.91Chapter 11 --- Conclusion --- p.93References --- p.9
Indo-European vocabulary in Old Chinese : a new thesis on the emergence of Chinese language and civilization in the late Neolithic age
No full textThis study is a much expanded version of the paper I read at the XXXII International Congress for Asian and North African Studies on August 28, 1986 in Hamburg (Germany). Contents 1. Recent developments in the field of historical linguistics 2. Monosyllabic structure of Chinese words and Indo-European stems 3. Tonal accents of Middle Chinese 4. Preliminaries on the comparison of consonants and vowels 5. Some IE stems corresponding to Chinese words of entering tone 6. Middle Chinese tones and final consonants of IE stems 7. Some IE stems corresponding to Chinese words of rising tone 8. Some IE stems corresponding to Chinese words of vanishing tone 9. Some IE stems corresponding to Chinese words of level tone 10. Reconstruction of Middle Chinese vocalism according to Yün-ching 11. Old Chinese vocalism 12. Vocalic correspondences between Chinese and IE 13. Initials of Old Chinese 14. Initial consonant clusters in Old Chinese as seen from IE-stems 15. Proximity of Chinese to Germanic 16. Relation of Old Chinese to neighboring languages 17. Emergence of Chinese Empire and language in the middle of the third millennium B.C. Appendix * Abbrevations * Bibliography * Rhyme Tables of Early Middle Chinese (600) * Rhyme Tables of Early Mandarin (1300) * Word Index o English o Pinyin In 1786, just over two hundred years ago, comparative historical linguistics was born, when Sir William Jones (1746-1794) discovered the relationship between Old-Indian Sanskrit, Greek, and Latin. Since then, the emerging Indo-European philology has thrown much light on the early history of mankind in Eurasia. During the past two hundred years, many suggestions were also made in regard to relationships of Indo-European to other languages such as Semitic, Altaic, Austronesian, Korean etc., but Indo-Europeanists commonly rejected such attempts for want of convincing evidence. As to Chinese, Joseph Edkins was the first to advance the thesis of its proximity to Indo-European. In his work China's Place in Philology. An Attempt to show that the Language of Europe and Asia have a Common Origin (1871) he presented a number of Chinese words similar to those of Indo-European. In his time, Edkins' thesis seemed bold and extravagant. But today, more than a hundred years later, we are in a much better position to carry out a comprehensive and well-founded comparative study. Since the end of the nineteenth century, many Sinologists have been engaged in reconstruction of the mediaeval and archaic readings of Chinese characters. Among them, Karlgren (1889-1978) was the most successful, and in 1940 he published a comprehensive phonological and etymological dictionary entitled Grammata Serica. In the meantime, the Indo-Europeanists Alois Walde (1869-1924) and Julius Pokorny (1887-1970) were devoting themselves to the compilation of a useful etymological dictionary. The result was the Indogermanisches Etymologisches Wörterbuch by Pokorny (1959) which provides a solid basis for our lexical comparisons. Soon thereafter, some Sinologists made use of the two dictionaries by Karlgren and Pokorny to compare Chinese and Indo-European words. In 1967, an unaffiliated German scholar, Jan Ulenbrook, published an article "Einige Übereinstirnrnungen zwischen dem Chinesischen und dem Indogermanischen", in which he claimed that 57 words are related. Shortly afterwards, Tor Ulving of the University of Goteborg, Sweden, wrote a review of this article framing the title as a question: "Indo-European elements in Chinese?" While working on his thesis on word families in Chinese, Ulving compiled for his own use two dictionaries: "Archaic Chinese - English" and "English - Archaic Chinese", and discovered thereby 238 Chinese words similar to Indo-European roots. In spite of this considerable number of word equivalents, however, Mr. Ulving became discouraged and, as he told me in his letter of April, 1986, has given up his researches in this field. The skepticism, common among Indo-Europeanists in regard to comparative studies with other languages, is largely based on the dogmatic opinion that only morphology is relevant but not vocabulary. Since the typology of Chinese seems to preclude a cognate relation to Indo-European, they are inclined to discard any lexical correspondences as merely accidental or onomatopoetic. Besides, prehistorical contacts and mixtures between these languages seem not conceivable, as the Indo-Europeans are supposed to have originated in Northern Europe or at best in the Central Asian steppe, thousands of miles away from East Asia. Hence, any research into a relationship between Old Chinese and Indo-European languages would be but futile from the outset. Yet there are also opposing views among Indo-Europeanists. Investigations into Germanic languages and the oldest Indo-European language, Hittite, led some of them to a critical revision of the prevailing conception about a Proto-Indo-European. Hermann Hirt (1934) for instance states: "Inflexion of Indo-European languages is due to a relatively late development, and its correct comprehension can be achieved only by proceeding from the time of non-inflexion." And Carl Karstien (1936) holds the opinion that "Chinese corresponds most ideally to the hypothetic prototype of Indo-European." Regarding vocabulary, there are striking similarities in the monosyllabic structure of the basic words. In modern German and English, all the words of everyday speech are monosyllabic and their stereotypical structure is: initial consonant(s) + vowel(s) + final consonant(s). The same word structure is valid for Chinese as well. It is fundamentally different from the disyllabic structure of Altaic words and from the triconsonantal-disyllabic structure of Semitic words. Characteristic of the monosyllabic word structure is, besides, the complexity of the syllable nucleus, which consists of different vowels and vowel clusters in contrast to the monophthongal vocalism of polysyllabic words. Another objection raised to comparisons between Chinese and Indo-European is the existence of tonal accents in Chinese. Since most modern Indo-European languages have only expiratory accents, Chinese is considered to be a highly exotic language. Yet, even in Chinese, the use of tonal accents as a means of lexical differentiation is a result of comparatively recent development in the long history of Chinese language, the earliest monuments of which date back to 1300 B.C. (cf. Chang 1970, p.21). Unknown to Old Chinese, the existence of tonal accents was for the first time mentioned in the 5th century by Shen Yüeh (441-513). In Middle Chinese (Mch.) there were four tone categories: A P'ing-sheng 平 a level tone (which developed into Mandarin tone 1 or 2). B Shang-sheng 上 a rising tone (Mandarin tone 3). C Ch'u-sheng 去 a vanishing, i.e. falling tone (Mandarin tone 4). D Ju-sheng 入 an entering tone with a staccato effect, the word being abruptly stopped by a final consonant -p, -t, -k. (In Early Mandarin the words of this tone lost their final consonant and were distributed among the tones 2, 3 and 4, respectively according to the phonation of initials). In Middle Chinese, words of the entering tone were the only group which still preserved the final stops and therefore a close syllabic structure. So they are most appropriate for convincing comparisons with monosyllabic Indo-European word stems. The final stops -p, -t, -k of the entering tone are nowadays still extant in daily speech of several dialects in South China as well as in Chinese borrowings in Japanese, Vietnamese and Korean. As a speaker of a Taiwan dialect of Minnan origin, I could immediately identify some Indo-European stems with corresponding Chinese words. Besides, the command of Japanese and German was also a great help for this study. In the following lists I have chosen a number of Indo-European stems which are phonetically and semantically equivalent to Chinese words. Correspondences in initial and final consonants refer to the points of articulation, thus we have equations: IE labials = Old Chinese labials, IE dentals = dentals, IE l, r = dentals (cf. p. 31); Ø, i (final and medial) IE velars = velars and laryngeals, and occasionally (the so-called "satem"-forms) IE velars = dental sibilants and affricates. Regarding the manner of articulation, there are no regular correspondences between Indo-European and Chinese consonants like Grimm's law which is valid among Indo-European dialects to a certain extent. But this is not astonishing, since in Old Chinese the alternation of initials in voicing was a conventional means of creating new words from one basic form. The rules of vocalic correpondences among Indo-European dialects are quite complex. Vowels permanently change their qualities from one language to another, and from time to time within one language also, as is well known from the history of English pronunciations. Generally, the vocalism of Old Greek is taken as the standard for Proto-Indo-European. Old Chinese vowels corresponds nearly (cf. p. 30), but the details about the reconstruction of Middle and Old Chinese vocalism will be treated later (pp. 26-30). For the moment, it is necessary to notice in advance that the stem of ablauting Germanic verbs is the form of preterite or noun, rather than that of infinitive as assumed hitherto. Therefore, in some cases I must slightly modify the basic vowel of verbal stems given in Pokorny, in order to get better basis for comparison. As Old Chinese verbs were non-flexional, they might probably have preserved the original vowel the best
Shelf-life Extension of Leafy Vegetables: Evaluating the Impacts
No full textCrop Production/Industries,
Transistors and tunnel diodes enabled by large-scale MoS<sub>2</sub> nanosheets grown on GaN
No full textWe report growth, fabrication, and device results of MoS2-based transistors and diodes implemented on a single 2D/3D material platform. The 2D/3D platform consists of a large-area MoS2 thin film grown on SiO2/p-GaN substrates. Atomic force microscopy, scanning electron microscopy, and Raman spectroscopy were used to characterize the thickness and quality of the as-grown MoS2 film, showing that the large-area MoS2 nanosheet has a smooth surface morphology constituted by small grains. Starting from the same material, both top-gated MoS2 field effect transistors and MoS2/SiO2/p-GaN heterojunction diodes were fabricated. The transistors exhibited a high on/off ratio of 105, a subthreshold swing of 74 mV dec-1, field effect mobility of 0.17 cm2 V-1 s-1, and distinctive current saturation characteristics. For the heterojunction diodes, current-rectifying characteristics were demonstrated with on-state current density of 29 A cm-2 and a current blocking property up to -25 V without breakdown. The reported transistors and diodes enabled by the same 2D/3D material stack present promising building blocks for constructing future nanoscale electronics.</p
Li yong jiu shan ma da zao ke kao gao xiao de shu ju zhong xin
No full textPh.D.Modern data centers provide cloud computing services and big data analytics by clustering commodity machines. failures are commonplace in such an environment, which degrade data availability and durability. Erasure coding protects data storage against failures with low redundancy ratio. However, the penalty in data recovery prevents erasure coding being further adopted in practice. To guarantee reliability and boost performance of modern data centers with erasure coding, we study two problems in real-world data centers and present our systems. In this thesis, we aim to estimate the reliability of data centers with erasure coding and achieve low latencies with erasure-coded caching.Firstly, we study the problem of analyzing the reliability on modern data centers with erasure coding. Modern data centers adopt a hierarchical architecture in which multiple nodes are grouped into racks and the cross-rack bandwidth is typically more limited than the inner-rack bandwidth. In such a data center, there are two types of redundancy placement schemes: one is flat placement, in which erasure-coded data is distributed across distinct nodes, each of which is located in a different rack in order to maximize the fault tolerance against rack failures; another is hierarchical placement, in which erasure-coded data is distributed across fewer racks, or equivalently multiple nodes per rack, to trade rack-level fault tolerance for the reduction of cross-rack repair traffic. Thus, the choices of erasure codes and redundancy placement in erasure-coded data centers raise new reliability issues. Chapter 3 explores to conduct a comprehensive reliability analysis by taking into account the hierarchical nature of erasure-coded data centers. We build a discrete-event simulator called SimEDC, which reports various reliability metrics of an erasure-coded data center based on the configurable inputs of the data center topology, erasure codes, redundancy placement, and failure/repair patterns of different subsystems obtained from statistical models or production traces. Our simulation results show that placing erasure-coded data in fewer racks generally improves reliability by reducing cross-rack repair traffic, even though it sacrifices rack-level fault tolerance in the face of correlated failures.In the second part, we study the performance variation in large-scale data centers. The performance variation (or long tail) is often caused by the presence of stragglers, which refers to the nodes that remain operational but with slow performance. However, detecting and pinpointing the stragglers is non-trivial due to the complexity of root causes analysis and limited knowledge about the full storage stack. Thus, Chapter 4 explores to tolerate the stragglers with erasure coding in order to cut the tail latencies. We present POCache, a parity-only caching design that provides robust straggler tolerance. To limit the erasure coding overhead, POCache slices blocks into smaller subblocks and parallelizes the coding operations at the subblock level. Also, it leverages a straggler-aware cache algorithm that takes into account both file access popularity and straggler estimation to decide what parity blocks are cached. We integrate POCache into Hadoop 3.1 HDFS to mitigate the straggler impact while preserving the functionalities and performance of normal HDFS operations.In summary, we propose two systems to guarantee reliability and improve performance with erasure coding for modern data centers.現代數據中心把普通計算機連接成集羣來提供雲計算和大數據分析服務。在這樣的存儲環境中，故障是很常見的，損害了數據的可用性和持久性。糾刪碼能夠用少量的存儲開銷來保障數據在故障發生時的可靠性。但是，恢復數據的極大開銷阻止了糾刪碼在實際存儲中的進一步應用。爲保障現代基於糾刪碼的數據中心的可靠性並提升其性能，我們研究了兩個來自於現實數據中心的問題並針對性的提出了兩個新系統。在這篇論文中，我們致力於分析採用糾刪碼存儲數據的數據中心的可靠性以及結合糾刪碼和緩存來獲取穩定的性能。首先，我們研究如何分析評估基於糾刪碼的數據中心的可靠性。現代數據中心採用等級分層的架構，該架構將多個節點（即服務器）集合成機架，這樣機架間的帶寬很有限，遠小於機架內的帶寬。在這樣分層的數據中心中，存在兩種數據存放機制：一種是水平分布，所有採用糾刪碼計算過的數據分布在不同的節點上，而且每個節點都位於不同的機架內，這樣可以最大程度的容納機架故障；另一種是層級分布，所有採用糾刪碼計算過的數據分布在少一些的機架中，也就是說每一臺機架中有多個節點來存放數據，通過犧牲機架間的容錯能力來減少修復數據時的機架間的網絡帶寬消耗。因此，在基於糾刪碼的數據中心中，糾刪碼的選擇和數據的存放位置衍生出一些新的關於數據可靠性的問題。第三章就此做了深入研究，把數據中心的等級分層特性考慮在內，進行了一系列全面深入的可靠性分析。我們提出新系統SimEDC，基於輸入的數據中心拓撲結構、糾刪碼參數、數據存放位置、以及從統計模型或工業界的實際記錄中得到的故障或修復模式來匯報基於糾刪碼的數據中心的可靠性評估。我們的模擬結果表明：把用糾刪碼計算過的數據放到較少的機架中，雖然在處理關聯性故障時犧牲了機架間的容錯能力，但因爲減少了機架間網絡帶寬的消耗從而提高了數據中心的可靠性。在本論文的第二部分，我們研究了在大規模數據中心的性能波動問題。性能波動（或者說長延時）通常是由落後節點引起的，這裏的落後節點是指性能變慢仍在運行的服務器。但是，檢測並準確的定位這些落後節點並不容易，因爲確定導致長延時的根源問題是一個復雜的過程況且我們很難完全了解整個存儲棧。所以，第四章研究了如何利用糾刪碼來容許落後節點的出現從而降低尾部延時。我們提出新系統POCache，一種緩存糾刪碼計算出的數據來有效的容忍落後節點的出現。POCache 將數據塊分成更小的小數據塊並在小數據塊層面來並行做糾刪碼的計算，以此來降低糾刪碼的額外開銷。同時，POCache 系統採用了一種意識到落後節點存在的緩存算法，兼顧文件讀取的熱度和對落後節點的評估來決定緩存哪些數據。我們在保持了原系統的功能和性能的同時，將POCache 應用到Hadoop 3.1HDFS 上並獲得穩定優良的性能。綜上所述，本論文從可靠性和服務延時兩個方面研究了基於糾刪碼的數據中心中存在的問題，並且針對每一方面提出一個新的系統來保障數據的可靠性存儲並提高數據中心的服務性能。Zhang, Mi.Thesis Ph.D. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 102-110).Abstracts also in Chinese.Title from PDF title page (viewed on 12, January, 2021).Zhang, Mi
Gao su wang lu liu liang fen xi zhong de gao xiao suan fa yu xi tong
No full textHuang, Qun.Thesis Ph.D. Chinese University of Hong Kong 2015.Includes bibliographical references (leaves 163-171).Abstracts also in Chinese.Title from PDF title page (viewed on 01, November, 2016).Huang, Qun
Jiu shan ma zai fen bu shi cun chu xi tong zhong de zui you xiu fu fang fa yi ji tong yi guan li de yan jiu
No full textPh.D.Modern data centers provide storage services by running distributed storage systems on many storage servers, where failures become common cases. To ensure data availability and durability, distributed storage systems either apply replication, where each block is stored with multiple replicas, or erasure coding, where a number of data blocks are encoded as a set of coded-blocks, such that an unavailable data block can be reconstructed by a subset of coded-blocks. Compared with replication, erasure coding provides data availability with lower storage overhead; thus, many distributed storage systems apply erasure coding to provide reliable storage services. However, erasure coding has two drawbacks. Firstly, erasure coding incurs high repair penalty when reconstructing an unavailable data block, which requires much more than the size of the original data block to be transferred across the network, and thus leads to poor repair performance. Secondly, it requires non-trivial engineering work to introduce new erasure coding solutions to existing distributed storage systems as erasure coding management is tightly coupled with the basic workflows of distributed storage systems. In this thesis, we focus on solving these two problems and enable optimal repair and unified management of erasure coding in distributed storage systems.We first focus on improving the repair performance in a hierarchical data center, which is often bottlenecked by cross-rack network transfer. Recent theoretical results show that the cross-rack repair traffic can be minimized through repair layering, whose idea is to partition a repair operation into inner-rack and cross-rack layers. However, how repair layering should be implemented and deployed in practice remains an open issue. We address this issue by proposing a practical repair layering framework called DoubleR. We design two families of practical double regenerating codes (DRC), which not only minimize the cross-rack repair traffic but also have several practical properties that improve state-of- the-art regenerating codes. We implement and deploy DoubleR atop HDFS-RAID (Facebook’s version of Hadoop Distributed File System) and show that DoubleR maintains the theoretical guarantees of DRC and improves the repair performance of regenerating codes in both node recovery and degraded read operations.We then focus on improving the repair performance in general erasure-coded storage by presenting a technique, repair pipelining. By pipelining the repair of failed data in small-size units across storage nodes, repair pipelining reduces the single-block repair time to approximately the same as the normal read time for a single block in homogeneous environments. We further design different variants of repair pipelining algorithms for heterogeneous environments and multi-block repair operations. We implement a repair pipelining prototype, called ECPipe, and integrate it as a middleware system into three open-source distributed storage systems, including HDFS-RAID, Hadoop-3.1.1 HDFS, and Quantcast File System. Experiments on a local testbed and Amazon EC2 show that repair pipelining significantly improves the performance of degraded reads and full-node recovery over existing repair techniques.Finally, we focus on solving the problem of managing different erasure coding solutions in distributed storage systems. Research studies have proposed theoretically proven erasure codes or efficient repair algorithms to make erasure coding more viable. However, integrating new erasure coding solutions into existing distributed storage systems is a challenging task and requires nontrivial re-engineering of the underlying storage workflows. We present OpenEC, a unified and configurable framework for readily deploying a variety of erasure coding solutions into existing distributed storage systems. OpenEC decouples erasure coding management from the storage workflows of distributed storage systems, and provides erasure coding designers with configurable controls of erasure coding operations through a directed-acyclic-graph- based programming abstraction. We prototype OpenEC on HDFS-RAID and Hadoop-3.0 HDFS with limited code modifications. Experiments on a local cluster and Amazon EC2 show that OpenEC preserves both the operational performance and the properties of erasure coding solutions; OpenEC can also automatically optimize erasure coding operations to improve repair performance.現代數據中心通過分布式存儲系統向外提供存儲服務。大型的數據中心由很多存儲服務器組成, 在這種情況下，服務器發生故障導致數據丟失或者受損成為了一個很常見的問題。为了保證數據可用性和持久性，分布式存儲系統可以應用多副本技術（每個數據塊存儲多個副本），或者糾刪碼技術（一定數量的數據塊經過編碼，使得其中受損的數據塊可以由一部分未受損的數據塊修復）。與多副本技術相比，糾刪碼技術能在提供數據可用性的同時降低存儲開銷，所以許多分布式存儲系統應用糾刪碼來確保數據的可靠性。然而，糾刪碼技術有兩個缺點。第一，用糾刪碼來修復數據的時候需要從網絡上下載大量的數據（比需要修復的數據量大得多），這導致了數據修復的性能不好。第二，由於糾刪碼的管理與分布式存儲系統中的基本操作緊耦合，導致將新的糾刪碼解決方案應用到現有的分布式存儲中需要大量工程才能做到。本論文主要研究並解決了這兩個問題，使得糾刪碼能為分布式存儲系統提供最優的修復性能，同時，也為糾刪碼的管理提供了統一的框架，使得糾刪碼能很快的應用到分布式存儲系統中。首先，我們提高了分層網絡數據中心中糾刪碼的數據修復性能。在分層網絡數據中心中，跨機架網絡傳輸性能是整個糾刪碼數據修復過程的瓶頸。理論研究結果已經證明分層數據修復技術能最小化糾刪碼在數據修復過程中產生的跨機架傳輸的數據量。它將數據修復操作分成兩層，即機架內的部分修復與跨機架的數據整合。然而，怎樣將分層數據修復技術應用到分布式存儲系統中依然是一個開放性的研究問題。我們提出了一個分層數據修復的框架，DoubleR，來解決這個問題。我們首先設計了兩組重複再生碼（DRC），它們不僅能最小化數據修復過程中產生的跨機架傳輸的數據量，而且，它們能提升經典再生碼的數據修復性能。然後，我們在HDFS-RAID 中實現了分層數據修復框架DoubleR，並將我們設計的兩組重複再生碼通過DoubleR 應用到了HDFS 中。我們的實驗表明DRC 能提升再生碼的數據修復性能。第二，我們提出了流水線數據修復的技術，repair pipelining,來提升一般網絡結構的數據中心中糾刪碼的數據修復性能。這個技術將一個數據塊的修復分為了很多個小數據片的修復，並流水線的修復所有的數據片。在扁平化網絡架構的數據中心中，流水線數據修復能降低單個數據塊的修復時間，使得其接近正常讀一個數據塊的時間。同時我們也擴展了repair pipelining 使它能夠支持分層網絡架構數據中心，以及同一條帶中多數據塊的同時修復。我們設計並實現了應用repair pipelining 進行數據修復的中間件，ECPipe，並將repair pipelining 應用到了三個開源的分布式存儲系統中（HDFS-RAID, Hadoop-3.1.1 HDFS, Quantcast File System）。我們的實驗證明repair pipelining 極大的提升了分布式存儲系統的數據修復性能。第三，我們解決了在分布式存儲系統中管理多種糾刪碼解決方案的問題。為了提升糾刪碼在分布式存儲系統中的可用性，研究人員既從理論上設計了新的，更實用的糾刪碼，也提出了更有效的數據修復算法。然而，將這些新的糾刪碼解決方案應用到現有的分布式存儲系統中是一個非常具有挑戰性的工作。這需要大量的修改分布式存儲系統的工作流程。為了解決這個問題，我們為分布式存儲系統設計了一個統一的，可編程控制的糾刪碼管理系統，OpenEC。它可以很快的將一個糾刪碼解決方案應用到現有的分布式存儲系統中。OpenEC 將糾刪碼的控制模塊從分布式存儲系統的存儲流程中解構出來，並通過提供一種基於有向圖的編程模型讓糾刪碼設計人員能在這個系統中方便的控制糾刪碼的各種操作。在修改少量系統源代碼的情況下，我們將OpenEC 應用到了HDFS-RAID 和Hadoop 3.0 HDFS 中。我們的實驗結果表明，OpenEC 不僅能保證糾刪碼各種操作的性能，還能保持不同糾刪碼設計的特性，同時OpenEC 還可以自動優化糾刪碼的操作來提升它在分布式存儲系統中的性能。Li, Xiaolu.Thesis Ph.D. Chinese University of Hong Kong 2020.Includes bibliographical references (leaves 161-175).Abstracts also in Chinese.Title from PDF title page (viewed on 20, September 2021).Li, Xiaolu
Log-structured flash-based storage with endurance, reliability, and performance guarantees
No full textPh.D.Flash-based solid state drives (SSDs) have become the mainstream persistent storage in datacenters, desktops and laptops in the past decade. SSDs are known to achieve lower latency in data access and consume less power than traditional hard-disk drives (HDDs). To lower its storage cost, recent technology advancements focus on increasing the capacity of SSDs, yet at the expense of their lifespan. To better utilize the lifespan of SSDs, SSD-aware storage usually adopts log-structured designs to avoid write amplification that is not only harmful to SSDs, but also adds extra latency to user operations.In this thesis, we propose two applications of log-structured designs in SSD storage to improve its endurance, reliability and performance. Specifically, we consider parity logging over SSD arrays, and value logging in key-value (KV) stores.First, we propose a storage layer, EPLOG , that mitigates parity update overhead via the novel scheme elastic parity logging. It enhances the endurance and reliability of SSD arrays via redirecting parity traffic to separate log devices, and boosts the update performance by eliminating pre-reads of data when computing parities. We implement EPLOG as a storage prototype and study its impact on the endurance, reliability and performance of SSD storage via thorough testbed experiments and case studies.Second, we propose a novel value management approach, HashKV , that adopts hash-based data grouping atop KV separation. HashKV not only enables efficient updates via deterministic mappings between values and storage space, but it also addresses hotness awareness and workloads of different KV pair sizes. We prototype HashKV and compare it to the current KV separation design via extensive testbed evaluations.Finally, we conclude the contributions of this thesis and suggest future work in related research areas.在過去的十年，固態硬碟逐漸成為數據中心、桌上電腦和行動電腦中的主要儲存裝置。固態硬碟的隨機讀寫延遲比傳統硬碟低，耗電量亦較少。可是，當固態硬碟的容量隨著近年的技術發展進一步提高，儲存單元的可讀寫壽命卻被縮短。因此，在資料更新密集的情況下，固態硬碟的可靠性仍然備受關注。為了更有效運用固態硬碟的可用壽命，具有固態硬碟感知的儲存系統普遍採用日誌結構(log-structured)設計來減少寫入放大，因為寫入放大不但額外損耗固態硬碟的壽命，同時亦對用家一般的讀寫帶來延遲。在本論文中，我們提出兩個在固態儲存系統中應用日誌結構設計的新方案，以提升系統的耐久度、可靠性和速度。這兩個方案分別針對陣列儲存系統中奇偶校驗信息塊的更新方法，及鍵值對儲存數據庫中值的更新方法。首先，我們提出一個新的儲存層實踐，EPLOG。它以創新的彈性校驗信息塊更新(elastic parity logging)方案來減低更新時的額外開銷。它誘導校驗信息塊的更新到日誌儲存裝置上，從而提升儲存系統的耐久度和可靠性。同時，它在寫入更新時避免讀取原來的數據作更新校驗信息塊之用，以提高寫入速度。我們實現了EPLOG的原型，並透過深入的平台測試和個案研究來探討 EPLOG 如何影響固態儲存系統的耐久度、可靠性和速度。其次，我們提出一個在鍵值分離中以雜湊式數據分群(hash-based data grouping)方式來管理值的新方案，HASHKV。HASHKV不但以確定性的值和位址對映來達致更有效率的更新，更可以支援數據冷熱感知和大小不同的鍵值對。我們實現了HASHKV的原型，並透過深入的平台測試與現有的鍵值分離設計作比較。最後，我們總結本論文之貢獻，並對日後在此範疇中的相關工作提出建議。Chan, Hoi Wan."November 2018."Thesis Ph.D. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 80-86).Abstracts also in Chinese.Title from PDF title page (viewed on 06, July, 2020)
Ke ni sketch suan fa zai da gui mo wang luo ce liang zhong de ying yong
No full textPh.D.Network measurement in massive network traffic is challenging due to the stringent requirements of fast packet processing and limited resource availability. Given the fast-speed and ever-increasing network traffic, maintaining per-flow state in network measurement tasks inevitably has tremendous resource demands. This motivates us to explore Invertible sketches for various network measurement tasks to perform the measurement in real-time at scale. Invertible sketches are summary data structures that significantly mitigate memory footprints with bounded errors. By "invertible'', we mean that the measurement results can be readily recovered from only the sketch data structure itself.We focus on three network measurement tasks, namely heavy flow detection, superspreader detection, and hierarchical heavy hitter detection. For each measurement task, we identify the challenges in the face of huge-volume traffic and limited available resources for measurement. Then we propose our sketch-based approaches addressing the challenges and evaluate our approaches with real-world network traces. Our approaches consider both the sketch algorithm design and the deployment in both software and hardware.We first consider heavy flow detection. We focus on two types of heavy flows: (i) heavy hitters that are flows with an unexpectedly high volume of traffic, and (ii) heavy changers that are flows with an unexpectedly high change of traffic volume in a short duration. Heavy flows may imply abnormal events, such as performance outliers and potential DDoS attacks. We present MV-Sketch, a fast and compact invertible sketch that supports heavy flow detection with small and static memory allocation. MV-Sketch tracks candidate heavy flows inside the sketch data structure via the idea of majority voting, such that it incurs small memory access overhead in both update and query operations, while achieving high detection accuracy. We present theoretical analysis on the memory usage, performance, and accuracy of MV-Sketch in both local and network-wide scenarios. We further show how MV-Sketch can be implemented and deployed on P4-based programmable switches subject to hardware deployment constraints. We conduct evaluation in both software and hardware environments. Trace-driven evaluation in software shows that MV-Sketch achieves higher accuracy than existing invertible sketches, with up to 3.38✕ throughput gain. We also show how to boost the performance of MV-Sketch with SIMD instructions. Furthermore, we evaluate MV-Sketch on a Barefoot Tofino switch and show how MV-Sketch achieves line-rate measurement with limited hardware resource overhead.We then consider superspreader detection. Superspreaders are hosts with a large number of distinct connections, which usually reveal the occurrence of anomalies in networks, such as DDoS attacks, port scanning, and worm propagation. Superspreaders remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch instances can be merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on SpreadSketch in terms of space and time complexities as well as error bounds. Trace-driven evaluation shows that SpreadSketch achieves higher accuracy and performance over state-of-the-art sketches. Furthermore, we prototype SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.Lastly, we study the hierarchical heavy hitter (HHH) detection. HHHs are hierarchical aggregates with exceptionally huge amounts of traffic. One notable application of HHH detection is to identify distributed denial-of-service (DDoS) or botnet attacks, in which the traffic aggregates of multiple attack flows can bring substantial damage to a network. Finding HHHs is critical to network management, yet it is often challenged by the requirements of real-time and accurate detection, fast packet processing, and resource efficiency. We present MVPipe, an invertible sketch data structure that achieves both lightweight updates and fast convergence in HHH detection. MVPipe builds on the skewness property of IP traffic to process packets via a pipeline of majority voting executions, such that most packets can be updated for only one or few aggregation levels. We show how MVPipe can be feasibly deployed in P4-based programmable switches subject to limited switch resources. We also theoretically analyze the accuracy and coverage properties of MVPipe. Evaluation with real-world Internet traces shows that MVPipe achieves high accuracy, high throughput, and fast convergence compared to six state-of-the-art HHH detection schemes. It also incurs low resource overhead in the Barefoot Tofino switch deployment.高速網絡中的海量流量以及有限的資源給網絡測量帶來了巨大的挑戰。在网络测量任务中為每一個網絡流維護一個紀錄不可避免地需要消耗巨量的资源。這啟發我们將可逆sketch算法應用于各种网络测量任务中，以進行实时地大規模地测量。可逆sketch是一種摘要数据结构，它可以在有限的誤差範圍內顯著地减少內存佔用量。可逆指測量結果可以快速地從sketch的數據結構中得到。本文主要研究三个經典的网络测量問題。針對每個問題，我們首先分析其在高速網絡中面臨的挑戰。然後，我們提出基於sketch算法的解決方案，並用真實的網絡流量對所提方案進行驗證和評估。我們的解決方案既考慮了sketch的算法設計，又包含了sketch在軟件環境和硬件交換機上的部署。首先，我們解決了大流檢測問題。我們關注兩種大流：(1)重擊流，它們具有異常大的流量；(2) 巨變流，它們在短時間內產生異常大的流量變動。 大流的出現通常預示網絡中異常事件的發生，例如性能異常和潛在的分布式拒絕服務攻擊。我們提出了MV-Sketch,一種快速緊湊的可逆sketch算法。MV-Sketch支持在靜態分配的小內存中進行大流檢測。MV-Sketch利用主投票算法找出網絡中可能的大流，並將它們存到sketch中。MV-Sketch實現了高精度大流檢測，同時產生有限的存儲器訪問開銷。我們對MV-Sketch在局部檢測和全網檢測的複雜度，速度以及準確度都進行了理論分析。同時我們也進一步討論了如何在硬件資源約束下，將MV-Sketch部署和實現在可編程硬件交換機中。我們在軟硬件環境中均對MV-Sketch進行了驗證。軟件環境中的實驗結果顯示，MV-Sketch比現有的sketch算法擁有更高的檢測精度，以及高達3.38倍的吞吐增益。我們利用單指令多數據流，對MV-Sketch的速度進行了更進一步的優化和提高。此外，我們在Barefoot Tofino可編程交換機上對MV-Sketch的評估結果顯示，MV-Sketch在有限的硬件資源條件下，可實現線速測量。其次，我們解決了超級傳播者的檢測問題。超級傳播者指網絡中具有大量不同通信連接的主機，它通常揭示了網絡中的異常情況，例如發生分布式拒絕服務攻擊，端口掃描，病毒傳播等。超級傳播者對生產網絡構成了嚴重的威脅。如何實時大規模地準確地檢測超級傳播者仍然是一個具有挑戰性的問題。我們提出了SpreadSketch，一種可逆的概要數據結構，用於整網範圍內檢測超級傳播者，並在空間使用，性能和準確性上具有理論保障。SpreadSketch將可能的超級傳播者以及它們的傳播程度存儲在靜態分配的空間中。它支持多個不同的SpreadSketch實例進行合併，進而找出全網視圖中的超級傳播者以及它們的傳播量。我們就空間和時間複雜度以及誤差範圍對SpreadSketch進行了理論分析和證明。基於真實網絡數據流量的驗證實驗表明，SpreadSketch與同類型解決方案相比，具有更高精度和速度。此外，我們將SpreadSketch實現在了可編程交換機中，並驗證了其在商用硬件中部署的可行性。最後，我們解決了分層大流檢測的問題。分層大流指具有巨大流量的網絡流聚合。分層大流檢測的一個顯著應用是識別分布式拒絕服務或殭屍網絡攻擊。這其中多個小攻擊流的流量聚合可能會對網絡造成巨大的破壞。檢測分層大流對網絡管理至關重要。然而，在準確，快速，以及資源高效的要求下，分層大流檢測面臨著諸多難點。我們提出了MVPipe，一種可在分層大流檢測中實現輕量級網絡流處理和快速精度收斂的可逆概要數據結構。MVPipe利用網絡流高度偏斜的特點，管道式地執行多個主投票過程來處理網絡流量。因此，大多數數據包只需進行一次或幾次聚合便可篩選出分層大流。我們討論了如何在硬件資源限制下將MVPipe部署在可編程交換機中。同時，我們從理論上分析了MVPipe的精度和對大流的覆蓋度。基於真實網絡流量的實驗表明，與六種最新的分層大流檢測方案相比，MVPipe具有更高的精度，速度以及快速收斂的能力。在BarefootTofino可編程交換機的部署中，MVPipe也具有較低的資源開銷。Tang, Lu.Thesis Ph.D. Chinese University of Hong Kong 2020.Includes bibliographical references (leaves 161-173).Abstracts also in Chinese.Title from PDF title page (viewed on 6, September 2021).Tang, Lu
- …
