Ngai Chi Kin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 57-59). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Linear Network Coding --- p.12 / Chapter 3 --- Combination Networks --- p.16 / Chapter 4 --- Multi-Source Multicast Networks --- p.31 / Chapter 5 --- Multi-source Network Coding with two sinks --- p.42 / Chapter 6 --- Conclusion --- p.55 / Bibliography --- p.59

Liu Wing Chun. / Thesis submitted in: July 2003. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 55-57). / Abstracts in English and Chinese. / Acknowledgement --- p.I / Abstract --- p.II / 摘要 --- p.III / Chapter Chapter 1 --- Introduction --- p.1 / Chapter Chapter 2 --- Related Works --- p.5 / Chapter 2.1 --- Fixed-Segment Fixed-Bandwidth Schemes --- p.6 / Chapter 2.2 --- Variable-Segment Fixed-Bandwidth Schemes --- p.7 / Chapter 2.3 --- Fixed-Segment Variable-Bandwidth Schemes --- p.8 / Chapter 2.4 --- Variable-Segment Variable-Bandwidth Schemes --- p.9 / Chapter 2.5 --- Performance Bounds of Periodic Broadcastings --- p.10 / Chapter Chapter 3 --- Consonant Broadcasting --- p.12 / Chapter 3.1 --- Type-I Channels --- p.14 / Chapter 3.2 --- Type-II Channels --- p.15 / Chapter 3.3 --- Client Buffer --- p.17 / Chapter Chapter 4 --- Performance Evaluation --- p.19 / Chapter 4.1 --- Startup Latency versus Network Bandwidth --- p.20 / Chapter 4.2 --- Startup Latency versus Client Access Bandwidth --- p.22 / Chapter 4.3 --- Client Buffer Requirement --- p.24 / Chapter Chapter 5 --- Grouped Consonant Broadcasting --- p.25 / Chapter 5.1 --- Bandwidth Partitioning and Reception Schedule --- p.26 / Chapter 5.2 --- Client Buffer Requirement --- p.28 / Chapter 5.3 --- Performance Tradeoffs --- p.30 / Chapter Chapter 6 --- Implementation and Benchmarking --- p.34 / Chapter 6.1 --- Practical Issues --- p.35 / Chapter 6.2 --- Experimental Results --- p.36 / Chapter Chapter 7 --- Dynamic Consonant Broadcasting --- p.39 / Chapter 7.1 --- Virtual Transmission Schedules --- p.40 / Chapter 7.2 --- Dynamic Broadcasting Schedules --- p.42 / Chapter 7.3 --- Performance Evaluation --- p.44 / Chapter Chapter 8 --- Variable-bit-rate Video Streaming --- p.46 / Chapter 8.1 --- Transmission Schedules --- p.46 / Chapter 8.2 --- Playback Continuity --- p.48 / Chapter 8.3 --- Performance Evaluation --- p.50 / Chapter Chapter 9 --- Conclusions --- p.53 / Bibliography --- p.55

Wong Ying Wai. / Thesis submitted in: December 2003. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 64-66). / Abstracts in English and Chinese. / Acknowledgement --- p.I / Abstract --- p.II / 摘要 --- p.III / Chapter Part I - --- Recursive Patching --- p.1 / Chapter Chapter 1 --- Introduction --- p.2 / Chapter Chapter 2 --- Transition Patching --- p.5 / Chapter Chapter 3 --- Recursive Patching --- p.9 / Chapter Chapter 4 --- Stream Assignment --- p.12 / Chapter 4.1 --- The Equal-Split Stream Assignment Scheme --- p.12 / Chapter 4.2 --- A Hierarchical Equal-Split Stream Assignment Scheme --- p.14 / Chapter Chapter 5 --- Performance Evaluation --- p.16 / Chapter Chapter 6 --- Conclusion --- p.18 / Bibliography --- p.19 / Chapter Part II - --- Interactive Multicast Video Streaming --- p.21 / Chapter Chapter 1 --- Introduction --- p.22 / Chapter Chapter 2 --- Background --- p.25 / Chapter 2.1 --- Multicast Streaming Algorithms --- p.25 / Chapter 2.2 --- Interactive Playback Support --- p.30 / Chapter Chapter 3 --- Interactive Multicast Streaming --- p.34 / Chapter 3.1 --- Interactivity Model --- p.34 / Chapter 3.2 --- Request Scheduling --- p.36 / Chapter 3.3 --- Client Buffer Management --- p.37 / Chapter 3.4 --- Performance Impact --- p.39 / Chapter Chapter 4 --- Static Full Stream Scheduling --- p.45 / Chapter Chapter 5 --- Adaptive Full Stream Scheduling --- p.48 / Chapter Chapter 6 --- Performance Evaluation --- p.52 / Chapter 6.1 --- Optimization of the Full Stream Threshold --- p.52 / Chapter 6.2 --- Latencies Comparisons --- p.57 / Chapter 6.3 --- Effect of Client Buffer Constraint --- p.58 / Chapter 6.4 --- Just-in-Time Simulation --- p.60 / Chapter Chapter 7 --- Conclusion --- p.63 / Bibliography --- p.64

Ma Tianbai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 49-51). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Incentive P2P System Overview --- p.6 / Chapter 3 --- Resource Distribution Mechanism --- p.11 / Chapter 4 --- Resource Competition Game --- p.22 / Chapter 4.1 --- Theoretical Competition Game --- p.22 / Chapter 4.2 --- Practical Competition Game Protocol --- p.26 / Chapter 5 --- Generalized Mechanism and Game --- p.33 / Chapter 5.1 --- Generalized Mechanism with Incentive --- p.33 / Chapter 5.2 --- Generalized Mechanism with Utility --- p.35 / Chapter 6 --- Experiments --- p.38 / Chapter 7 --- Conclusion --- p.48

Lin Wing Kai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 90-96). / Abstracts in English and Chinese. / Abstract/ 摘要 --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- """We are not alone""" --- p.1 / Chapter 1.2 --- Definition of P2P systems --- p.3 / Chapter 1.2.1 --- Terminologies --- p.4 / Chapter 1.2.2 --- Principles --- p.5 / Chapter 1.3 --- From sharing to replication --- p.7 / Chapter 1.3.1 --- Replication: why and how --- p.7 / Chapter 1.3.2 --- Advantages of P2P replication systems --- p.8 / Chapter 1.3.3 --- Typical replication approaches --- p.10 / Chapter 1.3.4 --- Difficulties in replication: resource allocation and replication strategy --- p.10 / Chapter 1.3.5 --- Why do peers cooperate? --- p.12 / Chapter 1.4 --- Contribution of this thesis --- p.13 / Chapter 1.4.1 --- Thesis organization --- p.13 / Chapter 2 --- Background Study --- p.15 / Chapter 2.1 --- Introduction --- p.15 / Chapter 2.2 --- Overview of P2P systems --- p.16 / Chapter 2.2.1 --- The original story --- p.16 / Chapter 2.2.2 --- Switching to decentralization --- p.16 / Chapter 2.2.3 --- Peer availability --- p.17 / Chapter 2.2.4 --- Other than file sharing --- p.18 / Chapter 2.3 --- Understanding replication --- p.20 / Chapter 2.3.1 --- File availability redefined --- p.20 / Chapter 2.3.2 --- Storage requirement analysis --- p.21 / Chapter 2.3.3 --- MTTF analysis --- p.22 / Chapter 2.3.4 --- Replica placement --- p.24 / Chapter 2.3.5 --- Other performance enhancement schemes --- p.27 / Chapter 2.4 --- Understanding cooperation --- p.28 / Chapter 2.5 --- Discussions --- p.30 / Chapter 3 --- Performance of erasure code replication --- p.32 / Chapter 3.1 --- Introduction --- p.32 / Chapter 3.2 --- Parameters definition --- p.33 / Chapter 3.2.1 --- File availability: whole file replication --- p.33 / Chapter 3.2.2 --- File availability: erasure code replication --- p.34 / Chapter 3.2.3 --- Properties of erasure code replication --- p.35 / Chapter 3.2.4 --- Effects of replication parameters --- p.36 / Chapter 3.2.5 --- Optimal value of b --- p.39 / Chapter 3.2.6 --- Analytical derivation --- p.40 / Chapter 3.3 --- Some practical considerations --- p.42 / Chapter 3.3.1 --- Cost of erasure code replication --- p.42 / Chapter 3.3.2 --- Sensitivity analysis --- p.44 / Chapter 3.4 --- Concluding remarks --- p.45 / Chapter 4 --- Distributed replication strategies --- p.48 / Chapter 4.1 --- Introduction --- p.48 / Chapter 4.2 --- The P2P replication system --- p.50 / Chapter 4.2.1 --- Erasure code replication --- p.50 / Chapter 4.2.2 --- Peers modelling --- p.51 / Chapter 4.2.3 --- Resource allocation problem --- p.52 / Chapter 4.2.4 --- Replication goal --- p.54 / Chapter 4.3 --- Decentralized adaptation --- p.56 / Chapter 4.3.1 --- Neighbour discovery and parameters exchange --- p.56 / Chapter 4.3.2 --- Storage resource estimation --- p.57 / Chapter 4.4 --- Heuristic strategies --- p.58 / Chapter 4.4.1 --- Random strategy --- p.58 / Chapter 4.4.2 --- Group partition strategy --- p.59 / Chapter 4.4.3 --- Highest available first (HAF) strategy --- p.61 / Chapter 4.5 --- Case studies --- p.65 / Chapter 4.5.1 --- Simulation results --- p.66 / Chapter 4.6 --- Concluding remarks --- p.69 / Chapter 5 --- Before cooperation: why do peers join? --- p.72 / Chapter 5.1 --- Introduction --- p.72 / Chapter 5.2 --- Information sharing club (ISC) model --- p.73 / Chapter 5.3 --- An example: music information sharing club --- p.75 / Chapter 5.4 --- Necessary condition for ISC to grow --- p.76 / Chapter 5.4.1 --- Music information sharing club example with simple requests --- p.78 / Chapter 5.5 --- Concluding remarks --- p.81 / Chapter 6 --- Conclusion --- p.83 / Chapter A --- Proof in this thesis --- p.86 / Bibliography --- p.90

Clock skew caused by variation is one of the most important problems in clock network synthesis today. Even if a clock network is designed to have zero skew, variation such as capacitive load and power supply will cause differences in arrival time of a clock signal. Non-tree clock network is considered to be an effective way to address the skew variation problem. Due to its inherent redundancy, clock mesh is very tolerant to variation. However, it costs much excessive amount of power compared to a clock tree. Link based non-tree clock network is an economic way to reduce clock skew caused by variation. Instead of using a dense mesh, only a number of links are inserted into a tree, so the power increase is small. Several existing works focus on the effect of cross link as well as the construction of such cross link structure. However, it is still not very clear where cross links should be inserted to achieve the most clock skew reduction with small wire resources. In this thesis, we propose a new method using linear program to solve this problem. In our approach, clock skew in a non-tree clock network is computed using an idea of load redistribution and non-tree decomposition. The delay information obtained is then used to select the node pairs for cross link insertion. Our methodology tries to insert cross links where skew can be reduced most effectively. Our method also considers tradeoff between cross link length and skew reduction effect. We compare our result with the most similar work on this problem [1] and a recent work [4] which inserts links between internal nodes of a tree. Experiments show that our method can reduce skew under variation effectively. We achieve 28% clock skew reduction with only 40% link resources. / Qian, Fuqiang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 51-55). / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Clock Distribution Network --- p.1 / Chapter 1.2 --- Our Contributions --- p.6 / Chapter 1.3 --- Organization of the Thesis --- p.8 / Chapter 2 --- Literature Review --- p.9 / Chapter 2.1 --- Exact Zero Skew --- p.9 / Chapter 2.2 --- DME Algorithm --- p.11 / Chapter 2.3 --- Combinatorial Algorithms for Fast Clock Mesh Optimization --- p.12 / Chapter 2.4 --- MeshWorks: An Efficient Framework for Planning, Synthesis and Optimization of Clock Mesh Networks --- p.14 / Chapter 2.5 --- Reducing Clock Skew variability via Cross Links --- p.16 / Chapter 2.6 --- Statistical Based Link Insertion for Robust Clock Network Design --- p.18 / Chapter 2.7 --- Variation Tolerant Buffered Clock Network Synthesis with Cross Links --- p.20 / Chapter 2.8 --- Cross Link Insertion for Improving Tolerance to Variations in Clock Network Synthesis --- p.22 / Chapter 3 --- Clock Network Construction with Cross Links --- p.24 / Chapter 3.1 --- Signal Delay and Clock Skew in Non-tree Clock Network --- p.24 / Chapter 3.1.1 --- Computing Delay in Non-tree Network --- p.25 / Chapter 3.1.2 --- Effect of a Cross Link on Clock Skew --- p.27 / Chapter 3.2 --- Link Insertion for Non-tree Clock Network --- p.28 / Chapter 3.2.1 --- Motivation of Computing Delay for Link Insertion --- p.29 / Chapter 3.2.2 --- Overall Flow for Cross Link Insertion --- p.30 / Chapter 3.2.3 --- Linear Program for Selecting Node Pairs --- p.31 / Chapter 3.2.4 --- Reducing the Number of Optimizations --- p.35 / Chapter 3.2.5 --- Experimental Results --- p.37 / Chapter 4 --- Buffered Clock Network with Cross Links --- p.41 / Chapter 4.1 --- Link Insertion in Buffered Clock Network --- p.41 / Chapter 4.1.1 --- Delay Calculation in Buffered Clock Network --- p.42 / Chapter 4.1.2 --- Linear Program Formulation for Buffered Clock Network --- p.43 / Chapter 4.2 --- Experimental Results and Comparison --- p.44 / Chapter 4.3 --- Possible Extensions --- p.46 / Chapter 4.3.1 --- Link Insertion at Internal Nodes --- p.46 / Chapter 4.3.2 --- Modeling Clock Buffer Delay Variation --- p.47 / Chapter 5 --- Conclusion --- p.49 / Bibliography --- p.51

Song Lihua. / "September 2000." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (p. 93-[98]). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

I designed, implemented and evaluated a decentralised context-aware content distribution middleware. It can support a variety of applications, with all network communication handled transparently behind a tuple space based interface. Content is inserted into the network with an associated condition stipulating the context that must be matched to receive it. Conditions can be expressed using conjunctions, disjunctions, a form of universal and existential quantification and nested block scopes. Conditions are mapped onto a set of spatial indexes to enable lookup; and these are inserted into a distributed multi-dimensional spatial data structure (e.g. an R-Tree). They are also translated into an OWL representation to enable evaluation. Nodes bind to their most geographically proximate neighbours which allows distance-sensitive context sharing. The middleware is capability-aware, pushing computationally expensive tasks onto more capable nodes. I evaluated my system through benchmarks and simulation, defining condition classes which collectively represent a large portion of the condition space. Random conditions were generated from these classes. Node mobility was controlled through a number of probability distributions. Benchmark evaluation times were reasonable, evaluating 500 typical messages in 1.4 seconds each. When the number of stored contexts were reduced, this improved dramatically, evaluating 500 much more complicated conditions in one-tenth of a second each. The number and complexity of context parameters has a major impact on efficiency. The number of spatial indexes generated was reasonable for most conditions, with a 95th percentile of 6. However, existential quantification was a challenge for both condition evaluation and index generation due to the potentially large number of possible combinations of conditions. As expected, simulations found that the distribution of workload was very uneven because nodes tend to cluster in large cities; meaning that most communication is localised within these areas. Also, node density had a dramatic impact on the number of received messages as nodes within sparse areas were unable to obtain context information which precluded condition evaluation. I achieved my research goals of developing a distributed context-aware content distribution framework.

The design of a communication network has a critical impact on its effectiveness at delivering service to the users of a large scale compute infrastructure. In particular, the reliability of such networks is increasingly vital in the modern world, as more and more of our commercial and social activity is conducted using digital platforms. Systems to assure service availability have been available since the emergence of Mainframes, with the System 360 in 1964, and although commercially widespread, the scientific understanding is not as deep as the problem warrants. The basic operating principle of most service assurance systems combines the gathering of status messages, which we term as events, with algorithms to deduce from the events where potential failures may be occurring. The algorithms to identify which events are causal, known as root cause analysis or fault localization, usually rely upon a detailed understanding of the network structure in order to determine those events that are most helpful in diagnosing and remediating a service threatening problem. The complex nature of root cause algorithms introduces scalability limits in terms of the number of events that can be processed per second. Unfortunately as networks grow, the volume of events produced continues to increase, often dramatically. The dependence of root cause analysis algorithms on network structure presents a significant challenge as networks continue to grow in scale and complexity. As a consequence of this, and the growing reliance upon networks as part of the key fabric of the modern economy, the commercial importance and the scale of the engineering challenges are increasing significantly. In this thesis I outline a novel approach to improving the scalability of event processing using a mathematical property of networks, graph entropy. In the first two papers described in this thesis, I apply an efficiently computable approximation of graph entropy to the problem of identifying important nodes in a network. In this context, importance is a measure of whether the failure of a node is more likely to result in a significant impact on the overall connectivity of the network, and therefore likely to lead to an interruption of service. I show that by ignoring events from unimportant network nodes it is possible to significantly reduce the event rate that a root cause algorithm needs to process. Further, I demonstrate that unimportant nodes produce very many events, but very few root causes. The consequence is that although some events relating to root causes are missed, this is compensated for by the reduction in overall event rate. This leads to a significant reduction of the event processing load on management systems, and therefore increases the effectiveness of current approaches to root cause analysis on large networks. Analysis of the topology data used in the first two papers revealed interesting anomalies in the degree distribution of the network nodes. This motivated the later focus of my research to investigate how graph entropy and network design considerations could be applied to the dynamical evolution of networks structures, most commonly described using the Preferential Attachment model of Barabási and Albert. A common feature of a communication network is the presence of a constraint on the number of logical or physical connections a device can support. In the last of the three papers in the thesis I develop and present a constrained model of network evolution, which demonstrates better quantitative agreement with real world networks than the preferential attachment model. This model, developed using the continuum approach, still does not address a fundamental question of random networks as a model of network evolution. Why should a node's degree influence the likelihood of it acquiring connections? In the same paper I attempt to answer that question by outlining a model that links vertex entropy to a node's attachment probability. The model successfully reproduces some of the characteristics of preferential attachment, and illustrates the potential for entropic arguments in network science. Put together, the two main bodies of work constitute a practical advance on the state of the art of fault localization, and a theoretical insight into the inner workings of dynamic networks. They open up a number of interesting avenues for further investigation.

Lam, Kwok Tai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 64-66). / Abstracts in English and Chinese. / Chapter 1 --- Introduction to Network Security via Efficient IP Traceback --- p.10 / Chapter 1.1 --- Motivation --- p.10 / Chapter 1.2 --- DDoS Attacker Traceback Problem --- p.11 / Chapter 1.3 --- Document Roadmap --- p.13 / Chapter 2 --- Background --- p.14 / Chapter 2.1 --- Probabilistic Edge Marking Algorithm --- p.14 / Chapter 2.1.1 --- Probabilistic Edge Marking Procedure --- p.15 / Chapter 2.1.2 --- Attack Graph Construction Procedure --- p.17 / Chapter 2.1.3 --- Advantages and Disadvantages of Algorithm --- p.19 / Chapter 3 --- Attacker Traceback: Linear Topology --- p.22 / Chapter 3.1 --- Determination of Local Traffic Rates --- p.23 / Chapter 3.2 --- Determination of Minimum Stable Time tmin --- p.25 / Chapter 3.3 --- Elimination of Attackers --- p.26 / Chapter 4 --- Attacker Traceback: General Topology --- p.30 / Chapter 4.1 --- Determination of Local Traffic Rates --- p.30 / Chapter 4.2 --- Determination of Minimum Stable Time tmin --- p.33 / Chapter 5 --- Simulations --- p.36 / Chapter 5.1 --- Simulation 1 - Correctness and robustness of estimating the min- imum stable time tmin --- p.37 / Chapter 5.1.1 --- Simulation l.A - Influence on tmin by different packet arrival processes --- p.37 / Chapter 5.1.2 --- Simulation l.B - Influence on tmin by different packet arrival processes under MMPP --- p.38 / Chapter 5.1.3 --- Simulation l.C - Influence on tmin and variance of traffic rate estimation by different pthreshold --- p.39 / Chapter 5.2 --- Simulation 2 - Factors which influence the minimum stable time tmin --- p.40 / Chapter 5.2.1 --- Simulation 2.A - Influence on tmin by different length of the attack path --- p.41 / Chapter 5.2.2 --- Simulation 2.B - Influence on tmin by the relative posi- tions of the attackers --- p.42 / Chapter 5.2.3 --- Simulation 2.C - Influence on tmin by different ATR and different length of the attack path --- p.43 / Chapter 5.3 --- Simulation 3 - Extension to General Network Topology --- p.45 / Chapter 5.3.1 --- Simulation 3.A - Influence on tmin by different ATR and different diameter of the network topology --- p.45 / Chapter 5.3.2 --- Simulation 3.B - Influence on tmin by different number of attackers --- p.46 / Chapter 5.4 --- Simulation 4 - Extension to Internet Topology --- p.47 / Chapter 5.4.1 --- Simulation 4.A - Influence on tminby different diameter of the network topology --- p.49 / Chapter 5.4.2 --- Simulation 4.B - Influence on tmin by different number of attackers --- p.50 / Chapter 6 --- Experiments --- p.51 / Chapter 6.1 --- Experiment 1: Simple DoS Attack --- p.53 / Chapter 6.1.1 --- Experiment l.A - Influence on tmin by different types of DDoS attack --- p.54 / Chapter 6.1.2 --- Experiment l.B - Influence on tmin by different length of the attack path --- p.55 / Chapter 6.2 --- Experiment 2: Coordinated DoS Attack --- p.55 / Chapter 6.2.1 --- Experiment 2.A - Influence on tmin by the relative posi- tions of the attackers --- p.56 / Chapter 6.2.2 --- Experiment 2.B - Influence on tmin by different number of attackers --- p.58 / Chapter 7 --- Related Work --- p.59 / Chapter 8 --- Conclusion --- p.62 / Bibliography --- p.64