Includes bibliographical references (p. 45-47).

Includes bibliographical references (p. 113-119).

Thesis (Ph. D.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 132-137). Also available in electronic version. Access restricted to campus users.

Advances in micro-embedded computing systems, coupled with developments in wireless technology have enabled the deployment of large scale wireless and sensor networks for many important applications. These networks are characterized by local geographic connectivity among nodes and by very little computational and storage capabilities at each node. Moreover, data transfer is mainly through packet forwarding by intermediary nodes. Due to the nature of their connectivity, nodes may have extremely limited information about their network, possibly only of their one-hop neighbors. In such a scenario where the nodes may have limited/erroneous network state information, we study the two basic network primitives: (i) point-to-point routing and (ii) broadcasting. First, we study the problem of point-to-point routing in a network of nodes where each node has a corresponding destination to send/receive data. We consider geographic routing (routing based on the position of the nodes), as this routing scheme is scalable and of low complexity and well suited to operate over sensor networks. We study the effect of imperfect routing information on the path lengths of the individual routes. We provide error models for the routing errors and demonstrate routing strategies that achieve order-wise optimal delays even when only a small fraction of the nodes have any (possibly imperfect) geographic information. We characterize the throughput capacity of the network and show that for a class of progressive routing strategies with limited routing data, the throughput capacity is order-wise optimal. While much of the current research focuses on greedy routing in uniform sensor networks, we study routing in imperfect (anisotropic) networks where greedy geographic forwarding fails due to holes (nodes without any neighbors that are closer to the destination). We develop routing strategies in such networks that operate with geographic location at the nodes to achieve order-wise optimal delays while maximizing the network throughput capacity. These algorithms inherit the beneficial properties of geographic routing algorithms such as scalability and low complexity while providing near-optimal throughput and delay in a robust manner. We also study routing strategies in networks where the traffic demand may be non-uniform. Routing schemes such as geographic routing that minimize some metric of routing distance cause local points of congestion as they do not consider the traffic demands across different parts of the network and may concentrate traffic along some paths that lie across regions of higher demand. We design randomized routing schemes based on geographic routing that are shown to be able to support any traffic demand that is achievable (i.e. achievable by any other scheme). Second, we study the issue of broadcasting in networks with limited local information. We analyze broadcast schemes where nodes have little geographic information or state information (memory of transmitted packets). We demonstrate randomized broadcast algorithms that utilize the limited information and perform broadcasting with minimal transmission overheads. Further, we also study branching random walks in R[superscript d], in the context of broadcasting a message over a spatial network to understand the asymptotic distribution of the broadcast. We derive analytic results on the density of these branching processes / text

Off-chip interconnection networks provide for communication between processors and components within computer systems. Semiconductor process technology trends have led to the inclusion of multiple processors and components onto a single chip and recently research has focused on interconnection networks, on-chip, to connect them together. On-chip networks provide a scalable, high-bandwidth interconnect, integrated tightly with the microarchitecture to achieve high performance. On-chip networks present several new challenges, different from off-chip networks, including tighter constraints in power, area and end-to-end latency. In this dissertation, I propose interconnection network architectures that address the unique design challenges of power and end-to-end latency on chip. My work in the design, implementation and evaluation of the on-chip networks of the TRIPS project’s prototype processor, a real hardware implementation, is the foundation for my work in on-chip networking. Based on my analysis of the TRIPS on-chip networks and their workloads, I propose, design, and evaluate novel network architectures for congestion monitoring and adaptive routing that are matched to the design constraints of on-chip networks. In the TRIPS system we designed, and implemented in silicon, a distributed processor microarchitecture where traditional processor components are divided into a collection of self-contained tiles. One novel aspect of the TRIPS system is the control and data networks that the tiles use to communicate with one another. I worked on the design and implementation of one of these networks, the On-Chip Network (OCN). The OCN, a 4x10 mesh network, interconnects the tiles of the L2 cache, the two processor cores and various I/O units. Another on-chip network, the Operand Network (OPN), interconnects the execution units and serves as a bypass network, integrated tightly with the processor core. In this document I evaluate these two on-chip networks and their workloads, these evaluations serve as case studies in how on-chip design constraints affect the design of on-chip networks. In the examination of the TRIPS OCN and OPN networks, one insight we gained was that network resource imbalances can lead to congestion and poor performance. We found these imbalances are transient with time and task. Timely information about the status of the network can be used to balance the resource utilization, or reduce power. A challenge lies in providing the right information, conveyed in a timely fashion, as the metrics and methods used in off-chip networks do not map well to on-chip networks. In this document, I propose and evaluate several metrics of network congestion for their utility and feasibility in an on-chip environment. In our examination of the TRIPS on-chip networks we also found that minimizing end-to-end packet latency was critical to maintaining good system performance. Effective use of the congestion information without impact to end-to-end latency is another challenge in on-chip networking. I explore novel adaptive routing techniques that address the challenge of managing the end-to-end latency. A method that produces good results is aggregation of network status information, reducing both the bandwidth and latency required for status information transmission. In this dissertation I examine how well this technique and others compare with conventional oblivious and adaptive routing. / text

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

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Peer-to-peer (P2P) video streaming has become a very popular and cost-effective solution to provide video-on-demand (VoD) streaming service to a large group of Internet users. Recent advances of layered video coding are shown to be promising in addressing the problem of receiver heterogeneity in P2P streaming networks. The key idea is to encode a raw video into multiple non-overlapped layers. Peers in the network can enjoy different streaming qualities by subscribing to different number of layers according to their specific network bandwidth. In this thesis, a systematic and comprehensive study of layered P2P VoD streaming networks is conducted. We first investigate the overlay construction problem that concerns the strategy of forming a logical overlay network for peers to exchange data pieces. We propose a neighbor relationship management algorithm to maintain a stable yet diversified neighbor set to facilitate adding or dropping a video layer, i.e. layer adaptation. Subsequently, an incentive scheme is designed to differentiate neighbors’ contributions at different layers, and a peer is allowed to adjust its number of neighbors according to its average service response time. We then develop an efficient layer adaptation algorithm for adjusting the number of video layers a peer subscribes to. We use a sliding buffer window for video piece scheduling, and make use of the time difference between the playback point and the starting point of the sliding window to initiate the process of adding or dropping a layer. A probing period is also introduced to ensure the adding decision is indeed correct. We next focus on designing piece scheduling algorithm for video data exchange among peers. At each peer, a utility function for calculating the relative importance of each missing video data piece is designed. In piece scheduling, a peer prefers a piece with higher utility value. We show that our utility based piece scheduling algorithm yields better video quality than conventional approaches. Last but not least, we study the request peer selection problem for identifying the most suitable neighbor for a peer to make a piece request. Two algorithms are designed, smallest service response time first (SSF) and closest playback point first (CPF). SSF ensures peers with larger uplink bandwidths to serve more requests, and CPF encourages a newly joined peer to contribute its uplink bandwidth as quickly as possible. We show that there exists a sweet spot by properly combining the two together. Although our algorithms are presented sequentially in addressing each of the problems above, they do interact with each other. Throughout our study, a comprehensive packet-level simulator is used to closely examine and analyze such interactions. With that, our algorithms are judicially designed and fine-tuned for best performance. To the best of our knowledge, our in-house developed simulator is the most comprehensive packet-level simulator for layered P2P VoD streaming. / published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

The combination of traditional process migration and the new virtualization technology enables mobility of virtual machines and resource provisioning within data centers. While applied to wide area network (WAN), a traditional migration algorithm has to adjust itself according to the various WAN situations and VM status. This thesis identifies four performance measurements of a VM migration: total migration time, downtime, remote up time and performance degradation. It observes that the total migration time and the remote up time of traditional pre-copy over WAN is too long to tolerate. This thesis claims that even for WAN, post-copy could be used to improve the total migration time and remote up time, only by introducing tolerable, predictable and controllable performance degradation. The adaptiveness of the migration algorithm is concerned. It proposes a hybrid solution of pre-copy and post-copy, both for memory and storage, to do the migration. In the hybrid solution, a fraction of memory (Mfrac) and a fraction of storage (Sfrac) are migrated in the pre-copy and freeze-and-copy phase, and the remaining are migrated in the post-copy phase. A model-based solution with the help of profiling is proposed to adaptively find the best combination of Mfrac and Sfrac. The evaluation part suggests that the proposed solution could adapt to different application behaviors and network conditions. / published_or_final_version / Computer Science / Master / Master of Philosophy

Peer-to-Peer (P2P) technology has been developed rapidly during the past few years. Due to its superiorities on robustness and scalability, P2P technology has been viewed as a promising networking technology and many studies have been done on how to improve P2P technology. P2P file distribution, as a major application of P2P technology, has also been studied a lot. The amount of time required for all peers to get the file has been considered as a major optimization metric, which we refer as the file distribution time. Researchers have proposed protocols to minimize the file distribution time for different cases. However, most of the existing works are based on the single-file scenario. On the other hand, studies show that in a file sharing application, users may download multiple files at the same time. In this thesis, we analyze the file distribution time for the distribution of multiple files in both wired and wireless networks. We develop explicit expressions for lower bound of time needed to distribute multiple files in a heterogeneous P2P fluid model. Unlike the single-file scenario, we demonstrate that the theoretical lower bound in multi-file scenario is not always achievable. With a comprehensive consideration of all the configurations, we develop algorithms to partition the bandwidth of all the peers for a particular file such that the file distribution time is optimal. / published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy