Cheung, Man Hon. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 89-94). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Rayleigh Fading Channels --- p.1 / Chapter 1.2 --- Ultra-Wideband (UWB) Communications --- p.2 / Chapter 1.2.1 --- Definition --- p.2 / Chapter 1.2.2 --- Characteristics --- p.3 / Chapter 1.2.3 --- UWB Signals --- p.4 / Chapter 1.2.4 --- Applications --- p.5 / Chapter 1.3 --- Cooperative Communications --- p.7 / Chapter 1.4 --- Outline of Thesis --- p.7 / Chapter 2 --- Background Study --- p.9 / Chapter 2.1 --- Interference-Aware Routing --- p.9 / Chapter 2.2 --- Routing in UWB Wireless Networks --- p.11 / Chapter 2.3 --- Cooperative Communications and Routing --- p.12 / Chapter 3 --- Cooperative Routing in Rayleigh Fading Channel --- p.15 / Chapter 3.1 --- System Model --- p.16 / Chapter 3.1.1 --- Transmitted Signal --- p.16 / Chapter 3.1.2 --- Received Signal and Maximal-Ratio Combining (MRC) --- p.16 / Chapter 3.1.3 --- Probability of Outage --- p.18 / Chapter 3.2 --- Cooperation Criteria and Power Distribution --- p.21 / Chapter 3.2.1 --- Optimal Power Distribution Ratio --- p.21 / Chapter 3.2.2 --- Near-Optimal Power Distribution Ratio β´ة --- p.21 / Chapter 3.2.3 --- Cooperation or Not? --- p.23 / Chapter 3.3 --- Performance Analysis and Evaluation --- p.26 / Chapter 3.3.1 --- 1D Poisson Random Network --- p.26 / Chapter 3.3.2 --- 2D Grid Network --- p.28 / Chapter 3.4 --- Cooperative Routing Algorithm --- p.32 / Chapter 3.4.1 --- Cooperative Routing Algorithm --- p.33 / Chapter 3.4.2 --- 2D Random Network --- p.35 / Chapter 4 --- UWB System Model and BER Expression --- p.37 / Chapter 4.1 --- Transmit Signal --- p.37 / Chapter 4.2 --- Channel Model --- p.39 / Chapter 4.3 --- Received Signal --- p.39 / Chapter 4.4 --- Rake Receiver with Maximal-Ratio Combining (MRC) --- p.41 / Chapter 4.5 --- BER in the presence of AWGN & MUI --- p.46 / Chapter 4.6 --- Rake Receivers --- p.47 / Chapter 4.7 --- Comparison of Simple Routing Algorithms in ID Network --- p.49 / Chapter 5 --- Interference-Aware Routing in UWB Wireless Networks --- p.57 / Chapter 5.1 --- Problem Formulation --- p.57 / Chapter 5.2 --- Optimal Interference-Aware Routing --- p.58 / Chapter 5.2.1 --- Link Cost --- p.58 / Chapter 5.2.2 --- Per-Hop BER Requirement and Scaling Effect --- p.59 / Chapter 5.2.3 --- Optimal Interference-Aware Routing --- p.61 / Chapter 5.3 --- Performance Evaluation --- p.64 / Chapter 6 --- Cooperative Routing in UWB Wireless Networks --- p.69 / Chapter 6.1 --- Two-Node Cooperative Communication --- p.69 / Chapter 6.1.1 --- Received Signal for Non-Cooperative Communication --- p.69 / Chapter 6.1.2 --- Received Signal for Two-Node Cooperative Communication --- p.70 / Chapter 6.1.3 --- Probability of Error --- p.71 / Chapter 6.2 --- Problem Formulation --- p.75 / Chapter 6.3 --- Cooperative Routing Algorithm --- p.77 / Chapter 6.4 --- Performance Evaluation --- p.80 / Chapter 7 --- Conclusion and Future Work --- p.85 / Chapter 7.1 --- Conclusion --- p.85 / Chapter 7.2 --- Future Work --- p.86 / Chapter 7.2.1 --- Distributed Algorithm --- p.87 / Chapter 7.2.2 --- Performance Analysis in Random Networks --- p.87 / Chapter 7.2.3 --- Cross-Layer Optimization --- p.87 / Chapter 7.2.4 --- Game Theory --- p.87 / Chapter 7.2.5 --- Other Variations in Cooperative Schemes --- p.88 / Bibliography --- p.89

Traditionally, on-chip network communication was achieved with shared medium networks where devices shared the transmission medium with only one device driving the network at a time. To avoid performance losses, it required a fast bus arbitration logic. However, a single shared bus has serious limitations with the heterogeneous and multi-core communication requirements of today's chip designs. Point-to-point or direct networks solved some of the scalability issues, but the use of routers and of rather complex algorithms to connect nodes during each cycle caused new bottlenecks. As technology scales, the on-chip physical interconnect presents an increasingly limiting factor for performance and energy consumption. Network-on-chip, an emerging interconnect paradigm, provide solutions to these interconnect and communication challenges. Motivated by future bottom-up self-assembled fabrication techniques, which are believed to produce largely unstructured interconnect fabrics in a very inexpensive way, the goal of this thesis is to explore the design trade-offs of such irregular, heterogeneous, and unreliable networks. The important measures we care about for our complex on-chip network models are the information transfer, congestion avoidance, throughput, and latency. We use two control parameters and a network model inspired by Watts and Strogatz's small-world network model to generate a large class of different networks. We then evaluate their cost and performance and introduce a function which allows us to systematically explore the trade-offs between cost and performance depending on the designer's requirement. We further evaluate these networks under different traffic conditions and introduce an adaptive and topology-agnostic ant routing algorithm that does not require any global control and avoids network congestion.

This thesis contributes toward the design of a reliable and energy-efficient transport system for Wireless Sensor Networks. Wireless Sensor Networks have emerged as a vital new area in networking research. In many Wireless Sensor Network systems, a common task of sensor nodes is to sense the environment and send the sensed data to a sink node. Thus, the effectiveness of a Wireless Sensor Network depends on how reliably the sensor nodes can deliver their sensed data to the sink. However, the sensor nodes are susceptible to loss for various reasons when there are dynamics in wireless transmission medium, environmental interference, battery depletion, or accidentally damage, etc. Therefore, assuring reliable data delivery between the sensor nodes and the sink in Wireless Sensor Networks is a challenging task. The primary contributions of this thesis include four parts. First, we design, implement, and evaluate a cross-layer communication protocol for reliable data transfer for data streaming applications in Wireless Sensor Networks. We employ reliable algorithms in each layer of the communication stack. At the MAC layer, a CSMA MAC protocol with an explicit hop-by-hop Acknowledgment loss recovery is employed. To ensure the end-to-end reliability, the maximum number of retransmissions are estimated and used at each sensor node. At the transport layer, an end-to-end Negative Acknowledgment with an aggregated positive Acknowledgment mechanism is used. By inspecting the sequence numbers on the packets, the sink can detect which packets were lost. In addition, to increase the robustness of the system, a watchdog process is implemented at both base station and sensor nodes, which enable them to power cycle when an unexpected fault occurs. We present extensive evaluations, including theoretical analysis, simulations, and experiments in the field based on Fleck-3 platform and the TinyOS operating system. The designed network system has been working in the field for over a year. The results show that our system is a promising solution to a sustainable irrigation system. Second, we present the design of a policy-based Sensor Reliability Management framework for Wireless Sensor Networks called SRM. SRM is based on hierarchical management architecture and on the policy-based network management paradigm. SRM allows the network administrators to interact with the Wireless Sensor Network via the management policies. SRM also provides a self-control capability to the network. This thesis restricts SRM to reliability management, but the same framework is also applicable for other management services by providing the management policies. Our experimental results show that SRM can offer sufficient reliability to the application users while reducing energy consumption by more than 50% compared to other approaches. Third, we propose an Energy-efficient and Reliable Transport Protocol called ERTP, which is designed for data streaming applications in Wireless Sensor Networks. ERTP is an adaptive transport protocol based on statistical reliability that ensures the number of data packets delivered to the sink exceeds the defined threshold while reducing the energy consumption. Using a statistical reliability metric when designing a reliable transport protocol guarantees the delivery of adequate information to the users, and reduces energy consumption when compared to the absolute reliability. ERTP uses hop-by-hop Implicit Acknowledgment with a dynamically updated retransmission timeout for packet loss recovery. In multihop wireless networks, the transmitter can overhear a forwarding transmission and interpret it as an Implicit Acknowledgment. By combining the statistical reliability and the hop-by-hop Implicit Acknowledgment loss recovery, ERTP can offer sufficient reliability to the application users with minimal energy expense. Our extensive simulations and experimental evaluations show that ERTP can reduce energy consumption by more than 45% when compared to the state-of- the-art protocol. Consequently, sensor nodes are more energy-efficient and the lifespan of the unattended Wireless Sensor Network is increased. In Wireless Sensor Networks, sensor node failures can create network partitions or coverage loss which can not be solved by providing reliability at higher layers of the protocol stack. In the final part of this thesis, we investigate the problem of maintaining the network connectivity and coverage when the sensor nodes are failed. We consider a hybrid Wireless Sensor Network where a subset of the nodes has the ability to move at a high energy expense. When a node has low remaining energy (dying node) but it is a critical node which constitutes the network such as a cluster head, it will seek a replacement. If a redundant node is located in the transmission range of the dying node and can fulfill the network connectivity and coverage requirement, it can be used for substitution. Otherwise, a protocol should be in place to relocate the redundant sensor node for replacement. We propose a distributed protocol for Mobile Sensor Relocation problem called Moser. Moser works in three phases. In the first phase, the dying node determines if network partition occurs, finds an available mobile node, and asks for replacement by using flooding algorithm. The dying node also decides the movement schedule of the available mobile node based on certain criteria. The second phase of the Moser protocol involves the actual movement of the mobile nodes to approach the location of the dying node. Finally, when the mobile node has reached the transmission of the dying node, it communicates to the dying nodes and moves to a desired location, where the network connectivity and coverage to the neighbors of the dying nodes are preserved.

Thesis (Ph. D.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Thesis (M.S.)--State University of New York at Binghamton, Dept. of Electrical & Computer Engineering, 2006. / Includes bibliographical references.

Network virtualization can offer more flexibility and better manageability for the future Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on a shared infrastructure provider (InP) network. A major challenge in this respect is the VN embedding problem that deals with the efficient mapping of virtual resources on InP network resources. Previous research focused on heuristic algorithms for the VN embedding problem assuming that the InP network remains operational at all times. In this thesis, we remove that assumption by formulating the survivable virtual network embedding (SVNE) problem and developing baseline policy heuristics and an efficient hybrid policy heuristic to solve it. The hybrid policy is based on a fast re-routing strategy and utilizes a pre-reserved quota for backup on each physical link. Our evaluation results show that our proposed heuristic for SVNE outperforms baseline heuristics in terms of long term business profit for the InP, acceptance ratio, bandwidth efficiency, and response time.

As the role of the Internet has been steadily gaining in importance, overlays are increasingly being used to provide new services and to deploy older ones. Some of the services for which overlays have been proposed include multicast, quality of service (QoS), search, and resilient networks. The use of overlays, in turn, has led to more interest in improving their performance. The performance of an overlay network depends significantly on how the network is structured, i.e., the placement of the nodes in the underlying network topology, the links between the overlay nodes and the access links of these nodes. This thesis focuses on algorithms for improving the performance of

Two research topics in next-generation optical networks with wavelength-division multiplexing (WDM) technologies were investigated: (1) scalability of network management and control, and (2) resilience/reliability of networks upon faults and attacks. In scalable network management, the scalability of management information for inter-domain light-path assessment was studied. The light-path assessment was formulated as a decision problem based on decision theory and probabilistic graphical models. It was found that partial information available can provide the desired performance, i.e., a small percentage of erroneous decisions can be traded off to achieve a large saving in the amount of management information. In network resilience under malicious attacks, the resilience of all-optical networks under in-band crosstalk attacks was investigated with probabilistic graphical models. Graphical models provide an explicit view of the spatial dependencies in attack propagation, as well as computationally efficient approaches, e.g., sum-product algorithm, for studying network resilience. With the proposed cross-layer model of attack propagation, key factors that affect the resilience of the network from the physical layer and the network layer were identified. In addition, analytical results on network resilience were obtained for typical topologies including ring, star, and mesh-torus networks. In network performance upon failures, traffic-based network reliability was systematically studied. First a uniform deterministic traffic at the network layer was adopted to analyze the impacts of network topology, failure dependency, and failure protection on network reliability. Then a random network layer traffic model with Poisson arrivals was applied to further investigate the effect of network layer traffic distributions on network reliability. Finally, asymptotic results of network reliability metrics with respect to arrival rate were obtained for typical network topologies under heavy load regime. The main contributions of the thesis include: (1) fundamental understandings of scalable management and resilience of next-generation optical networks with WDM technologies; and (2) the innovative application of probabilistic graphical models, an emerging approach in machine learning, to the research of communication networks.

This dissertation starts by realizing that network management is a very complex and error-prone task. The major causes are identified through interviews and systematic analysis of network config- uration data on two large campus networks. This dissertation finds that network events and dynamic reactions to them should be programmatically encoded in the network control program by opera- tors, and some events should be automatically handled for them if the desired reaction is general. This dissertation presents two new solutions for managing and configuring networks using Software- Defined Networking (SDN) paradigm: Kinetic and Coronet. Kinetic is a programming language and central control platform that allows operators to implement traffic control application that reacts to various kinds of network events in a concise, intuitive way. The event-reaction logic is checked for correction before deployment to prevent misconfigurations. Coronet is a data-plane failure recovery service for arbitrary SDN control applications. Coronet pre-plans primary and backup routing paths for any given topology. Such pre-planning guarantees that Coronet can perform fast recovery when there is failure. Multiple techniques are used to ensure that the solution scales to large networks with more than 100 switches. Performance and usability evaluations show that both solutions are feasible and are great alternative solutions to current mechanisms to reduce misconfigurations.

Network virtualization can offer more flexibility and better manageability for the future Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on a shared infrastructure provider (InP) network. A major challenge in this respect is the VN embedding problem that deals with the efficient mapping of virtual resources on InP network resources. Previous research focused on heuristic algorithms for the VN embedding problem assuming that the InP network remains operational at all times. In this thesis, we remove that assumption by formulating the survivable virtual network embedding (SVNE) problem and developing baseline policy heuristics and an efficient hybrid policy heuristic to solve it. The hybrid policy is based on a fast re-routing strategy and utilizes a pre-reserved quota for backup on each physical link. Our evaluation results show that our proposed heuristic for SVNE outperforms baseline heuristics in terms of long term business profit for the InP, acceptance ratio, bandwidth efficiency, and response time.