published_or_final_version / abstract / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

As human dependence on computing technology increases, so does the need for computer system dependability. This dissertation introduces Consul, a communication substrate designed to help improve system dependability by providing a platform for building fault-tolerant, distributed systems based on the replicated state machine approach. The key issues in this approach--ensuring replica consistency and reintegrating recovering replicas--are addressed in Consul by providing abstractions called fault-tolerant services. These include a broadcast service to deliver messages to a collection of processes reliably and in some consistent order, a membership service to maintain a consistent system-wide view of which processes are functioning and which have failed, and a recovery service to recover a failed process. Fault-tolerant services are implemented in Consul by a unified collection of protocols that provide support for managing communication, redundancy, failures, and recovery in a distributed system. At the heart of Consul is Psync, a protocol that provides for multicast communication based on a context graph that explicitly records the partial (or causal) order of messages. This graph also serves as the basis for novel algorithms used in the ordering, membership, and recovery protocols. The ordering protocol combines the semantics of the operations encoded in messages with the partial order provided by Psync to increase the concurrency of the application. Similarly, the membership protocol exploits the partial ordering to allow different processes to conclude that a failure has occurred at different times relative to the sequence of messages received, thereby reducing the amount of synchronization required. The recovery protocol combines checkpointing with the replay of messages stored in the context graph to recover the state of a failed process. Moreover, this collection of protocols is implemented in a highly-configurable manner, thus allowing a system builder to easily tailor an instance of Consul from this collection of building-block protocols. Consul is built in the x-Kernel and executes standalone on a collection of Sun 3 work-stations. Initial testing and performance studies have been done using two applications: a replicated directory and a distributed wordgame. These studies show that the semantic based order is more efficient than a total order in many situations, and that the overhead imposed by the checkpointing, membership, and recovery protocols is insignificant.

Approved for public release, distribution unlimited / This thesis will focus on academia, specifically the Naval Postgraduate School, and its requirement to implement an education program that allows facilitators to properly inform future students on the gradual implementation of Internet Protocol version 6 (IPv6) technology while phasing out Internet Protocol version 4 (IPv4) from the current curriculum as the transition to IPv6 progresses. The DoD's current goal is to complete the transition of all DoD networks from IPv4 to IPv6 by fiscal year 2008. With this deadline quickly approaching, it is imperative that a plan to educate military and DoD personnel be implemented in the very near future. It is my goal to research and suggest a program that facilitators can use that will show the similarities, changes, advantages, and challenges that exist for the transition. / US Marine Corps (USMC) author.

by Ma Chun Ho Eric. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 102-105). / Abstracts in English and Chinese. / INTERNET ROUTING AND PRICING --- p.1 / ABSTRACT --- p.I / ACKNOWLEDGEMENTS --- p.III / LIST OF FIGURES --- p.IV / LIST OF TABLES --- p.VI / CONTENTS --- p.VII / Chapter CHAPTER1 --- Introduction --- p.1 / Chapter 1.1 --- What is Internet? --- p.1 / Chapter 1.2 --- Internet Routing and Pricing --- p.3 / Chapter 1.3 --- Overview of QoS Routing --- p.4 / Chapter 1.3.1 --- Classification of Routing --- p.6 / Chapter 1.3.2 --- Optimal Routing --- p.7 / Chapter 1.4 --- An Introduction to Internet Economics --- p.8 / Chapter 1.4.1 --- Internet Externality --- p.9 / Chapter 1.4.2 --- Current Pricing Practice --- p.10 / Chapter 1.4.3 --- Network Interconnection --- p.14 / Chapter 1.4 --- Organization of Thesis --- p.16 / Chapter CHAPTER2 --- Economic Theory for Interconnection Model --- p.18 / Chapter 2.1 --- Introduction --- p.18 / Chapter 2.2 --- Demand and Supply --- p.20 / Chapter 2.2.1 --- Consumer Behavior --- p.20 / Chapter 2.2.2 --- Demand Curve --- p.25 / Chapter 2.2.3 --- Price Elasticity --- p.30 / Chapter 2.2.4 --- Estimation of Market Demand --- p.32 / Chapter 2.3 --- Market Structure --- p.33 / Chapter 2.3.1 --- Competitive Firm --- p.34 / Chapter 2.3.2 --- Monopoly --- p.35 / Chapter 2.3.3 --- Oligopoly --- p.35 / Chapter 2.4 --- Game Theory --- p.35 / Chapter 2.4.1 --- The Payoff Matrix of a game --- p.36 / Chapter 2.4.2 --- Nash Equilibrium --- p.37 / Chapter 2.4.3 --- Mixed Strategies --- p.38 / Chapter 2.4.4 --- Existence of Nash Equilibrium --- p.39 / Chapter 2.5 --- Summary --- p.39 / Chapter CHAPTER3 --- Problem Formulation Interconnection Network for Pricing and Routing in Internet --- p.40 / Chapter 3.1 --- Introduction --- p.40 / Chapter 3.2 --- Problem Formulation --- p.41 / Chapter 3.2 --- Existence of NEP Interconnection Network --- p.46 / Chapter 3.3 --- "A ""Cookbook"" Procedure" --- p.53 / Chapter 3.4 --- Cookbook Examples --- p.54 / Chapter 3.5 --- Summary --- p.65 / Chapter CHAPTER4 --- Price Competition for Interconnection Models --- p.66 / Chapter 4.1 --- Introduction --- p.66 / Chapter 4.2 --- Competitive Pricing of Parallel Networks --- p.66 / Chapter 4.2.1 --- Model and Problem Formulation --- p.67 / Chapter 4.2.2 --- Existence of Nash Equilibrium Point --- p.68 / Chapter 4.2.3 --- Numerical Example and Properties --- p.71 / Chapter 4.3 --- Price Collusion for Serial Networks --- p.75 / Chapter 4.3.1 --- Model and Problem Formulation --- p.75 / Chapter 4.3.2 --- Existence of Nash Equilibrium Point --- p.77 / Chapter 4.3.3 --- Numerical Example and Properties --- p.79 / Chapter 4.4 --- Summary --- p.83 / Chapter CHAPTER5 --- Price Distortion for Series-Parallel Networks with Dominant Carriers --- p.85 / Chapter 5.1 --- Problem Motivation and Formulation --- p.85 / Chapter 5.2 --- Properties under NEP --- p.90 / Chapter 5.3 --- A Simple Simulation --- p.95 / Chapter 5.5 --- Summary --- p.98 / Chapter CHAPTER6 --- Conclusion --- p.99 / BIBLIOGRAPHY --- p.102

by Hui Chi Chun Ronald. / Thesis submitted in: December 1998. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 62-66). / Abstract also in Chinese. / Chapter Chapter 1. --- Introduction --- p.1 / Chapter Chapter 2. --- AON Architecture --- p.7 / Chapter 2.1 --- WCC Dimension Reduction Node Architecture --- p.10 / Chapter 2.2 --- Restoration of a Survivable AON --- p.13 / Chapter Chapter 3. --- Network Dimensioning Problem --- p.15 / Chapter 3.1 --- Problem Setting --- p.16 / Chapter 3.2 --- Two Solution Approaches --- p.16 / Chapter 3.2.1 --- Minimum Variance Algorithm (MVA) --- p.17 / Chapter 3.2.2 --- Minimum Variance Subroutine (MVS) --- p.19 / Chapter 3.3 --- Shortest Path Algorithm (SPA) --- p.21 / Chapter 3.4 --- An Illustrative Example --- p.22 / Chapter 3.5 --- Performance Comparisons --- p.26 / Chapter Chapter 4. --- Network Management for AON Restoration --- p.31 / Chapter 4.1 --- Surveillance Network --- p.31 / Chapter 4.2 --- Signaling Network --- p.32 / Chapter 4.3 --- Network Management System --- p.32 / Chapter 4.4 --- CCS7 Adaptation for Supporting AON Restoration --- p.34 / Chapter Chapter 5. --- Complete Restoration Algorithm for AON --- p.40 / Chapter 5.1 --- Link-Based Restoration Algorithm --- p.43 / Chapter 5.2 --- Source-Based Restoration Algorithm --- p.44 / Chapter 5.3 --- Case Studies --- p.45 / Chapter 5.3.1 --- Case I and II --- p.45 / Chapter 5.3.2 --- Case III --- p.50 / Chapter 5.4 --- Completely Restorable Network planning --- p.52 / Chapter 5.5 --- A Summary on Problem Formulations --- p.55 / Chapter Chapter 6. --- Conclusion --- p.57 / Reference --- p.62

Lau Kwok Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 66-67). / Abstracts in English and Chinese. / Acknowledgement --- p.1 / Abstract --- p.2 / 摘要 --- p.3 / Chapter Chapter 1 --- Introduction --- p.6 / Chapter Chapter 2 --- Background and Related Work --- p.9 / Chapter 2.1 --- Application-Layer Bandwidth Differentiation --- p.9 / Chapter 2.2 --- Related Work --- p.14 / Chapter 2.2.1 --- Bandwidth Differentation --- p.14 / Chapter 2.2.2 --- Shared Congestion Management --- p.15 / Chapter 2.2.3 --- Flow Partition --- p.16 / Chapter Chapter 3 --- VPS Protocol Architecture --- p.17 / Chapter 3.1 --- Virtual and Actual Flows --- p.18 / Chapter 3.2 --- VPS Controller --- p.21 / Chapter Chapter 4 --- ACK Translation --- p.25 / Chapter 4.1 --- Fast Retransmit and Fast Recovery --- p.27 / Chapter 4.2 --- Timeout --- p.30 / Chapter 4.3 --- Packet and ACK Reordering --- p.33 / Chapter 4.4 --- False Duplicate ACK Suppression --- p.35 / Chapter 4.5 --- Maxburst --- p.37 / Chapter 4.6 --- Memory Overhead and Computation Complexity --- p.38 / Chapter Chapter 5 --- Bandwidth Differentiation --- p.41 / Chapter 5.1 --- Distribution of Virtual Packets --- p.41 / Chapter 5.2 --- Temporary Suspension of Actual Flows --- p.43 / Chapter 5.3 --- Receive Window Limit --- p.44 / Chapter 5.4 --- Limited Data Transmission --- p.44 / Chapter Chapter 6 --- Performance Evaluatoin --- p.45 / Chapter 6.1 --- Performance Metric --- p.45 / Chapter 6.2 --- Simulation Setup --- p.46 / Chapter 6.3 --- Performance over Different Time Scales --- p.47 / Chapter 6.4 --- Performance over Different Bottleneck Bandwidth --- p.53 / Chapter 6.5 --- Performance over Different Application-specified Ratios --- p.54 / Chapter 6.6 --- Performance over Different Number of Flows --- p.57 / Chapter 6.7 --- Heterogeneous Receivers --- p.60 / Chapter Chapter 7 --- Conclusions and Future Work --- p.65 / Bibliography --- p.66

Zheng, Pengxuan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 53-57). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.v / Table of Contents --- p.vi / List of Figures --- p.viii / List of Tables --- p.ix / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Related Work --- p.2 / Chapter 1.3 --- Our Contribution --- p.3 / Chapter 1.4 --- Organization of the Thesis --- p.4 / Chapter Chapter 2 --- Background Overview --- p.6 / Chapter 2.1.1 --- Traditional Wireless Networks --- p.6 / Chapter 2.2 --- Exponential Backoff --- p.7 / Chapter 2.2.1 --- Introduction --- p.7 / Chapter 2.2.2 --- Algorithm --- p.8 / Chapter 2.2.3 --- Assumptions --- p.9 / Chapter 2.3 --- System Description --- p.9 / Chapter 2.3.1 --- MPR Capability --- p.9 / Chapter 2.3.2 --- Backoff Slot --- p.10 / Chapter 2.3.3 --- Carrier-sensing and Non-carrier-sensing Systems --- p.11 / Chapter Chapter 3 --- Multipacket Reception in WLAN --- p.12 / Chapter 3.1 --- MAC Protocol Description --- p.13 / Chapter 3.2 --- Physical Layer Methodology --- p.16 / Chapter 3.2.1 --- Blind RTS Separation --- p.17 / Chapter 3.2.2 --- Data Packet Detection --- p.19 / Chapter Chapter 4 --- Exponential Backoff with MPR --- p.21 / Chapter 4.1 --- Analytical Model --- p.22 / Chapter 4.1.1 --- Markov Model --- p.22 / Chapter 4.1.2 --- Relations betweenpt andpc --- p.23 / Chapter 4.2 --- Simulation Settings --- p.26 / Chapter 4.3 --- Asymptotic Behavior of Exponential Backoff --- p.27 / Chapter 4.3.1 --- Convergence ofpt andpc --- p.27 / Chapter 4.3.2 --- Convergence of Npt --- p.29 / Chapter Chapter 5 --- Non-carrier-sensing System --- p.31 / Chapter 5.1 --- Performance Analysis --- p.31 / Chapter 5.1.1 --- Throughput Derivation --- p.31 / Chapter 5.1.2 --- Throughput Analysis --- p.32 / Chapter 5.1.3 --- Convergence of S --- p.36 / Chapter 5.2 --- Infinite Population Model --- p.38 / Chapter 5.2.1 --- Attempt Rate --- p.38 / Chapter 5.2.2 --- Asymptotic Throughput of Non-carrier-sensing System --- p.39 / Chapter Chapter 6 --- Carrier-sensing System --- p.43 / Chapter 6.1 --- Throughput Derivation --- p.43 / Chapter 6.2 --- Asymptotic Behavior --- p.44 / Chapter Chapter 7 --- General MPR Model --- p.48 / Chapter Chapter 8 --- Conclusions --- p.51 / Bibliography --- p.53

Network applications and Internet services fail all too frequently. However, end users cannot effectively identify the root cause using traditional troubleshooting techniques due to the limited capability to distinguish failures caused by local network elements from failures caused by elements located outside the local area network. To overcome these limitations, we propose a new approach, one that leverages collaboration of user machines to assist end users in diagnosing various failures related to Internet connectivity and poor network performance. First, we present DYSWIS ("Do You See What I See?"), an automatic network fault detection and diagnosis system for end users. DYSWIS identifies the root cause(s) of network faults using diagnostic rules that consider diverse information from multiple nodes. In addition, the DYSWIS rule system is specially designed to support crowdsourced and distributed probes. We also describe the architecture of DYSWIS and compare its performance with other tools. Finally, we demonstrate that the system successfully detects and diagnoses network failures which are difficult to diagnose using a single-user probe. Failures in lower layers of the protocol stack also have the potential to disrupt Internet access; for example, slow Internet connectivity is often caused by poor Wi-Fi performance. Channel contention and non-Wi-Fi interference are the primary reasons for this performance degradation. We investigate the characteristics of non-Wi-Fi interference that can severely degrade Wi-Fi performance and present WiSlow ("Why is my Wi-Fi slow?"), a software tool that diagnoses the root causes of poor Wi-Fi performance. WiSlow employs user-level network probes and leverages peer collaboration to identify the physical location of these causes. The software includes two principal methods: packet loss analysis and 802.11 ACK number analysis. When the issue is located near Wi-Fi devices, the accuracy of WiSlow exceeds 90%. Finally, we expand our collaborative approach to the Internet of Things (IoT) and propose a platform for network-troubleshooting on home devices. This platform takes advantage of built-in technology common to modern devices --- multiple communication interfaces. For example, when a home device has a problem with an interface it sends a probe request to other devices using an alternative interface. The system then exploits cooperation of both internal devices and remote machines. We show that this approach is useful in home networks by demonstrating an application that contains actual diagnostic algorithms.

No description available.