Dissertations / Theses on the topic 'Multicasting (Computer networks) Network processors'

Thesis (M.S. in Computer Science and M.S. in Electrical Engineering)--Naval Postgraduate School, March 2004.
Thesis advisor(s): Su Wen, Jon Butler. Includes bibliographical references (p. 53-54). Also available online.

Classification and scheduling are key functionalities of a network processor. Network processors are equipped with application specific integrated circuits (ASIC), so that as IP (Internet Protocol) packets arrive, they can be processed directly without using the central processing unit. A new network processor is proposed called the video network processor (VNP) for real time broadcasting of video streams for IP television (IPTV). This thesis explores the challenge in designing a combined classification and scheduling module for a VNP. I propose and design the classifier-scheduler module which will classify and schedule data for VNP. The proposed module discriminates between IP packets and video packets. The video packets are further processed for digital rights management (DRM). IP packets which carry regular traffic will traverse without any modification. Basic architecture of VNP and architecture of classifier-scheduler module based on content addressable memory (CAM) and random access memory (RAM) has been proposed. The module has been designed and simulated in Xilinx 9.1i; is built in ISE simulator with a throughput of 1.79 Mbps and a maximum working frequency of 111.89 MHz at a power dissipation of 33.6mW. The code has been translated and mapped for Spartan and Virtex family of devices.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, September 2003.
Thesis advisor(s): Geoffrey Xie, John H. Gibson. Includes bibliographical references (p. 149-151). Also available online.

Thesis (M.S. in Computer Science) Naval Postgraduate School, September 1996.
Thesis advisor(s): D.P. Brutzman, Michael J. Zyda. "September 1996." Includes bibliographical references: (p. 119-121). Also available online.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003.
Includes bibliographical references (leaves 75-79). Also available in electronic version. Access restricted to campus users.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2004.
Includes bibliographical references (leaves 59-62). Also available in electronic version. Access restricted to campus users.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2004.
Includes bibliographical references (leaves 34-37). Also available in electronic version. Access restricted to campus users.

Delay tolerant networks (DTNs) are a class of emerging networks that exhibit significantly different characteristics from today's Internet, such as intermittent connectivity, large delay, and high loss rates. DTNs have important applications in disaster relief, military, rural Internet access, environmental sensing and surveillance, interplanetary communication, underwater sensing, and vehicular communication. While not the common case for networking, DTNs represent some of the most critical cases, where the ability to communicate can make a huge difference for human lives. Supporting effective communication in DTNs, however, is challenging. First, with intermittent connectivity, DTNs are often extremely limited in capacity. Second, given resource limitations and uncertainty in DTNs, it is critical to deliver data efficiently and robustly. The situation is especially acute for multicast which sends data to multiple destinations. This thesis seeks to address these two issues. To enhance network capacity in DTNs, we propose a message ferrying scheme that exploits the use of special mobile nodes (called message ferries) and controlled device mobility to deliver data. Message ferries are utilized to transport data via mobility between sources and destinations. We develop a foundation for the control of the mobility of message ferries, and nodes if possible, to cooperatively deliver data under a variety of conditions. We also study another approach which deploys new nodes called throwboxes to enhance capacity. Throwboxes are small and inexpensive wireless devices. By relaying data between mobile nodes, throwboxes are able to create data transfer opportunities that otherwise would not exist. We systematically investigate the issues of deployment and routing, and develop algorithms for various deployment and routing approaches. Based on extensive evaluation, we obtain several findings to guide the design and operation of throwbox-augmented DTNs. To address the issue of efficient and robust data delivery, we focus on DTN multicasting. Given the unique characteristics of DTNs, traditional solutions such as IP multicast can not be simply ported to DTNs. We identify the limitations of IP multicast semantics in DTNs and define new semantic models for DTN multicast. Based on these semantic models, we develop and evaluate several multicast routing algorithms with different routing strategies.

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2004.
Includes bibliographical references (leaves 71-77). Also available in electronic version. Access restricted to campus users.

Simulation has become an important way to observe and understand various networking phenomena under various conditions. As the demand to simulate larger and more complex networks increases, the limited computing capacity of a single workstation and the limited simulation capability of a single network simulator have become apparent obstacles to the simulationists. In this research we develop techniques that can scale a simulation to address the limited capacity of a single workstation, as well as techniques that can compose a simulation from different simulator components to address the limited capability of a single network simulator. We scale a simulation with two different approaches: 1) We reduce the resource requirement of a simulation substantially, so that larger simulations can fit into one single workstation. In this thesis, we develop three technqiues (Negative Forwarding Table, Multicast Routing Object Aggregation and NIx-Vector Unicast Routing) to aggregate and compress the large amount of superfluous or redundant routing state in large multicast simulations. 2) The other approach to scale network simulations is to partition a simulation model in a way that makes the best use of the resources of the available computer cluster, and distribute the simulation onto the different processors of the computer cluster to obtain the best parallel simulation performance. We develop a novel empirical methodology called BencHMAP (Benchmark-Based Hardware and Model Aware Partitioning) that runs small sets of benchmark simulations to derive the right formulas of calculating the weights that are used to partition the simulation on a given computer cluster. On the other hand, to address the problem of the limited capability of a network simulator, we develop techniques for building complex network simulations by composing from independent components. With different existing simulators good at different protocol layers/scenarios, we can make each simulator execute the layers where it excels, using a simulation backplane to be the interface between different simulators. In this thesis we demonstrate that these techniques enable us to not only scale up simulations by orders of magnitude with a good performance, but also compose complex simulations with high fidelity.

This thesis explores the design and experimental implementation of GPF, a novel protocol-independent, multi-match packet classification framework. This framework is targeted and optimised for flexible, efficient execution on NVIDIA GPU platforms through the CUDA API, but should not be difficult to port to other platforms, such as OpenCL, in the future. GPF was conceived and developed in order to accelerate classification of large packet capture files, such as those collected by Network Telescopes. It uses a multiphase SIMD classification process which exploits both the parallelism of packet sets and the redundancy in filter programs, in order to classify packet captures against multiple filters at extremely high rates. The resultant framework - comprised of classification, compilation and buffering components - efficiently leverages GPU resources to classify arbitrary protocols, and return multiple filter results for each packet. The classification functions described were verified and evaluated by testing an experimental prototype implementation against several filter programs, of varying complexity, on devices from three GPU platform generations. In addition to the significant speedup achieved in processing results, analysis indicates that the prototype classification functions perform predictably, and scale linearly with respect to both packet count and filter complexity. Furthermore, classification throughput (packets/s) remained essentially constant regardless of the underlying packet data, and thus the effective data rate when classifying a particular filter was heavily influenced by the average size of packets in the processed capture. For example: in the trivial case of classifying all IPv4 packets ranging in size from 70 bytes to 1KB, the observed data rate achieved by the GPU classification kernels ranged from 60Gbps to 900Gbps on a GTX 275, and from 220Gbps to 3.3Tbps on a GTX 480. In the less trivial case of identifying all ARP, TCP, UDP and ICMP packets for both IPv4 and IPv6 protocols, the effective data rates ranged from 15Gbps to 220Gbps (GTX 275), and from 50Gbps to 740Gbps (GTX 480), for 70B and 1KB packets respectively.
LaTeX with hyperref package

Recently, there has been a global trend among the telecommunication industry on the rapid deployment of IPTV (Internet Protocol Television) infrastructure and services. While the industry rushes into the IPTV era, the comprehensive understanding of the status and dynamics of IPTV network lags behind. Filling this gap requires in-depth analysis of large amounts of measurement data across the IPTV network. One type of the data of particular interest is device or system log, which has not been systematically studied before. In this dissertation, we will explore the possibility of utilizing system logs to serve a wide range of IPTV network management purposes including health monitoring, troubleshooting and performance evaluation, etc. In particular, we develop a tool to convert raw router syslogs to meaningful network events. In addition, by analyzing set-top box (STB) logs, we propose a series of models to capture both channel popularity and dynamics, and users' activity on the IPTV network.

The purpose of this thesis is to develop some new algorithms based on optimization techniques for solving some problems in some areas of telecommunications and the Internet. There are two main parts to this thesis. In the first part we discuss optimization based stochastic and queueing models in telecommunications network corrective maintenance. In the second part we develop optimization based clustering (OBC) algorithms for network evolution and multicast routing. The most typical scenario encountered during mathematical optimization modelling in telecommunications, for example, is to minimize the cost of establishment and maintenance of the networks subject to the performance constraints of the networks and the reliability constraints of the networks as well. Most of these optimization problems are global optimization, that is, they have many local minima and most of these local minima do not provide any useful information for solving these problems. Therefore, the development of effective methods for solving such global optimization problems is important. To run the telecommunications networks with cost-effective network maintenance,we need to establish a practical maintenance model and optimize it. In the first part of the thesis, we solve a known stochastic programming maintenance optimization model with a direct method and then develop some new models. After that we introduce queue programming models in telecommunications network maintenance optimization. The ideas of profit, loss, and penalty will help telecommunications companies have a good view of their maintenance policies and help them improve their service. In the second part of this thesis we propose the use of optimization based clustering (OBC) algorithms to determine level-constrained hierarchical trees for network evolution and multicast routing. This problem is formulated as an optimization problem with a non-smooth, non-convex objective function. Different algorithms are examined for solving this problem. Results of numerical experiments using some artifiicial and real-world databases are reported.
Doctor of Philosophy

The purpose of this thesis is to develop some new algorithms based on optimization techniques for solving some problems in some areas of telecommunications and the Internet. There are two main parts to this thesis. In the first part we discuss optimization based stochastic and queueing models in telecommunications network corrective maintenance. In the second part we develop optimization based clustering (OBC) algorithms for network evolution and multicast routing. The most typical scenario encountered during mathematical optimization modelling in telecommunications, for example, is to minimize the cost of establishment and maintenance of the networks subject to the performance constraints of the networks and the reliability constraints of the networks as well. Most of these optimization problems are global optimization, that is, they have many local minima and most of these local minima do not provide any useful information for solving these problems. Therefore, the development of effective methods for solving such global optimization problems is important. To run the telecommunications networks with cost-effective network maintenance,we need to establish a practical maintenance model and optimize it. In the first part of the thesis, we solve a known stochastic programming maintenance optimization model with a direct method and then develop some new models. After that we introduce queue programming models in telecommunications network maintenance optimization. The ideas of profit, loss, and penalty will help telecommunications companies have a good view of their maintenance policies and help them improve their service. In the second part of this thesis we propose the use of optimization based clustering (OBC) algorithms to determine level-constrained hierarchical trees for network evolution and multicast routing. This problem is formulated as an optimization problem with a non-smooth, non-convex objective function. Different algorithms are examined for solving this problem. Results of numerical experiments using some artifiicial and real-world databases are reported.
Doctor of Philosophy

Multicast has long been considered an attractive service for the Internet for the provision of multiparty applications. For over a decade now multicast has been a proposed IETF standard. Though there is a strong industry push towards deploying multicast, there has been little multicast deployment by commercial Internet Service Providers (ISPs) and more importantly most end-users still lack multicast capabilities. Depending on the underlying network infrastructure, the ISP has several options of implementing his multicast capabilities. With significantly faster and more sophisticated protocols being designed and prototyped, it is expected that a whole new gamut of applications that are delay sensitive will come into being. However, the incentives to resolve the conflicting interests of the ISPs and the end-users have to be provided for successful implementation of these protocols. Thus we arrive at the following economic questions: What is the strategy that will enable the ISP recover his costs ? How can the end-user be made aware of the cost of his actions ? Naturally, the strategies of the ISP and the end-user depend on each other and form an economic game. The research problems addressed in this thesis are: A pricing model that is independent of the underlying transmission protocols is prefered. We have proposed such a pricing scheme for multicast independent of the underlying protocols, by introducing the concept of pricing points* These pricing points provide a range of prices that the users can expect during a particular time period and tune their usage accordingly. Our pricing scheme makes both the sender and receiver accountable. Our scheme also provides for catering to heterogeneous users and gives incentive for differential pricing. We explore a number of formulations of resource allocation problems arising in communication networks as optimization models. Optimization-based methods were only employed for unicast congestion control. We have extended this method for single rate multicast. We have also devised an optimization-based approach for multicast congestion control that finds an allocation rate to maximize the social welfare. Finally we also show that the session-splitting problem can also be cast as an optimization problem. The commonly used "max-min" fairness criteria suffers from serious limitations like discriminating sessions that traverse large number of links and poor network utilization. We provide an allocation scheme that reduces discrimination towards multicast sessions that traverse many links and also improves network utilization.

Load distribution problems in distributed computing networks have attracted much attention in the literature. A major objective in these studies is to distribute the processing load so as to minimize the time of processing of the entire load. In general, the processing load can be indivisible or divisible. An indivisible load has to be processed in its entirety on a single processor. On the other hand, a divisible load can be partitioned and processed on more than one processor. Divisible loads are either modularly divisible or arbitrarily divisible. Modularly divisible loads can be divided into pre-defined modules and cannot be further sub-divided. Further, precedence relations between modules may exist. Arbitrarily divisible loads can be divided into several fractions of arbitrary lengths which usually do not have any precedence relations. Such type of loads are characterized by their large volume and the property that each data element requires an identical and independent processing. One of the important problems here is to obtain an optimal load distribution, which minimizes the processing time when the distribution is subject to communication delays in the interconnecting links. A specific application in which such loads are encountered is in edge-detection of images. Here the given image frame can be arbitrarily divided into many sub-frames and each of these can be independently processed. Other applications include processing of massive experimental data. The problems associated with the distribution of such arbitrarily divisible loads are usually analysed in the framework of what is known as divisible job theory. The research work reported in this thesis is a contribution in the area of distributing arbitrarily divisible loads in distributed computing systems subject to communication delays. The main objective in this work is to design and analyseload distribution strategies to minimize the processing time of the entire load in a given network. Two types of networks are considered, namely (i) single-level tree (or star) network and (ii) linear network. In both the networks we assume that there is a non-zero delay associated with load transfer. Further, the processors in the network may or may not be equipped with front-ends (Le., communication co-processors). The main contributions in this thesis are summarized below. First, a mathematical formulation of the load distribution problem in single-level tree and linear networks is presented. In both the networks, it is assumed that there are (m +1) processors and m communication links. In the case of single-level tree networks, the load to be processed is assumed to originate at the root processor, which divides the load into (m +1) fractions, keeps its own share of the load for processing, and distributes the rest to the child processors one at a time and in a fixed sequence. In all the earlier studies in the literature, it had been assumed that for a load distribution to be optimal, it should be such that all the processors must stop computing at the same time. In this thesis, it is shown that this assumption is in general not true, and holds only for a restricted class of single-level tree networks which satisfy a certain condition. The concept of an equivalent network is introduced to obtain a precise formulation of this condition in terms of the processor and link speed parameters. It is shown that this condition can be used to identify processor-link pairs which can be eliminated from a given network (i.e., these processors need not be given any computational load) without degrading its time performance. It is proved that the resultant reduced network (a network from which these inefficient processor-link pairs have been removed) gives the optimal time performance if and only if the load distribution is such that all the processors stop computing at the same time instant. These results are first proved for the case when the root processor is equipped with a front-end and then extended to the case when it is not. In the latter case, an additional condition, between the speed of the root processor and the speed of each of the links, to be satisfied by the network is specified. An optimal sequence for applying these conditions is also obtained. In the case of linear networks the processing load is assumed to originate at the processor situated at one end of the network. Each processor in the network keeps its own load fraction for computing and transmits the rest to its successor. Here too, in all the earlier studies in the literature, it has been assumed that for the processing time to be a minimum, the load distribution must be such that all the processors must stop computing at the same instant in time. Though this condition has been proved by others to be both necessary and sufficient, a different and more rigorous proof, similar to the case of single-level tree network, is presented here. Finally, the effect of inaccurate modelling on the processing time and on the above conditions are discussed through an illustrative example and it is shown that the model adopted in this thesis gives reasonably accurate results. In the case of single-level tree networks, so far it has been assumed that the root processor distributes the processing load in a fixed sequence. However, since there are m child processors, a total of m! different sequences of load distribution are possible. Using the closed-form derived for the processing time, it is proved here that the optimal sequence of load distribution follows the decreasing order of link speeds. Further, if physical rearrangement of processors and links is allowed, then it is shown that the optimal arrangement follows a decreasing order of link and processor speeds with the fastest processor at the root. The entire analysis is first done for the case when the root processor is equipped with a front-end, and then extended to the case when it is not. In the without front-end case, it is shown that the same optimal sequencing result holds. However, in an optimal arrangement, the root processor need not be the fastest. In this case an algorithm has been proposed for obtaining optimal arrangement. Illustrative examples are given for all the cases considered. Next, a new strategy of load distribution is proposed by which the processing time obtained in earlier studies can be further minimized. Here the load is distributed by the root processor to a child processor in more than one installment (instead of in a single installment) such that the processing time is further minimized. First; the case in which all the processors are equipped :tn front-ends is considered. Recursive equations are obtained for a heterogeneous network and these are solved for the special case of a homogeneous network (having identical processors and identical links). Using this closed-form solution, the ultimate limits of performance are explored through an asymptotic analysis with respect to the number of installments and number of processors in the network. Trade-off relationships between the number of installments and the number of processors in the network are also presented. These results are then extended to the case when the processors are not equipped with front-ends. Finally, the efficiency of this new strategy of load distribution is demonstrated by comparing it with the existing single-installment strategy in the literature. The multi-installment strategy explained above is then applied to linear net-As. Here, .the processing load is assumed to originate at one extreme end of the network, First the case when all the processors are equipped with front-ends is considered. Recursive equations for a heterogeneous network are obtained and these are solved for the special case of a homogeneous network. Using this closed form solution, an asymptotic analysis is performed with respect to the number of installments. However, the asymptotic results with respect to the number of processors was obtained computationally since analytical results could not be obtained. It is found that for a given network, once the number of installments is fixed, there is an optimum number of processors to be used in the network, beyond which the time performance degrades. Trade-off relationships between the number of installments and the number of processors is obtained. These results are then extended to the case when the processors are not equipped with front-ends. Comparisions with the existing single-installment strategy is also done. The single-installment strategy discussed in the literature has the disadvantage that the front-ends of the processors are not utilized efficiently in a linear network. This is due to the fact that a processor starts computing its own load fraction only after the entire load to be communicated through its front-end has been received. In this thesis, a new strategy is proposed in which a processor starts computing as soon as it receives its load fraction, simultaneously allowing its front-end to receive and transmit load to its successors. Recursive equations are developed and solved for the special case of a heterogeneous network in which the processors and links are arranged in the decreasing order of speeds. Further, it is shown that in this strategy, if the processing load originates in the interior of the network, the sequence of load distribution should- be such that the load should be first distributed to the side with a lesser number of processors. An expression for the optimal load origination point in the network is derived. A comparative study of this strategy with an earlier strategy is also presented. Finally, it is shown that even though the analysis is carried out for a special case of a heterogeneous network, this load distribution strategy can also be applied to a linear network in which the processors and links are arbitrarily arranged and still obtain a significant improvement in the time performance.

An important objective of tactical ad hoc networks is to deliver threat information from sensors to shooters efficiently and quickly. The information sent to a particular shooter should contain warnings about threats that are within some distance and/or within some time of the shooter's current location. In this thesis we develop a novel multicast model that distributes this form of threat information in a message efficient manner. In addition, information about allied force can also be distributed in a similar way. We present results from extensive simulations that demonstrate the efficiency of our protocol and discuss the scalability of this model to larger networks.
Graduation date: 2001

Wong, Ho Yin Starsky.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2002.
Includes bibliographical references (leaves 81-85).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Motivation --- p.1
Chapter 1.2 --- Problems of IP multicast --- p.2
Chapter 1.3 --- End-system multicast --- p.3
Chapter 1.4 --- The Challenge of ESM --- p.3
Chapter 1.5 --- Document Roadmap --- p.4
Chapter 2 --- System Architecture --- p.5
Chapter 3 --- ESM Protocol --- p.8
Chapter 3.1 --- ESM: Tree Formation Protocol --- p.8
Chapter 3.1.1 --- Example of Tree Formation Protocol --- p.14
Chapter 3.1.2 --- "The proof of ""Tree Formation Protocol always main- tains a tree topology""" --- p.15
Chapter 3.1.3 --- "The proof of ""Tree Formation Protocol guarantees that there is no partition in the ESM-tree""" --- p.16
Chapter 3.1.4 --- State Transition Diagram for Tree Formation Protocol --- p.16
Chapter 3.2 --- ESM: Data Transfer --- p.28
Chapter 3.3 --- ESM: Tree Optimization Protocol CONTENTS --- p.30
Chapter 3.3.1 --- Example of Tree Optimization Protocol --- p.37
Chapter 3.3.2 --- "The proof of ""Distributed Locking Protocol avoids loop formation and tree partition""" --- p.38
Chapter 3.3.3 --- State Transition Diagram for Tree Optimization Protocol --- p.39
Chapter 3.4 --- ESM: Node Leaving Protocol --- p.46
Chapter 3.4.1 --- Example of ESM: Node Leaving Protocol --- p.51
Chapter 3.4.2 --- State Transition Diagram for Node Leaving Protocol --- p.53
Chapter 4 --- Performance Evaluation --- p.60
Chapter 4.1 --- Experiment 1 - Comparisons between IP Unicast and ESM --- p.61
Chapter 4.2 --- Experiment 2 - Comparisons between different ESM topologies --- p.64
Chapter 4.3 --- Experiment 3 - Comparison between different thresholds for tree optimization operation --- p.67
Chapter 4.4 --- Experiment 4 - NS2 Simulation --- p.69
Chapter 5 --- Related Work --- p.74
Chapter 6 --- Concluding Remarks --- p.78
Chapter 6.1 --- Contributions --- p.78
Chapter 6.2 --- Future Work --- p.79
Chapter 6.2.1 --- Large-scale Experiments --- p.79
Chapter 6.2.2 --- Evaluation for non-reliable data transfer --- p.79
Chapter 6.2.3 --- Investigation of tree-optimization activation threshold --- p.80

Thesis (M.S.)--Florida State University, 2003.
Advisor: Dr. Xin Yuan, Florida State University, College of Arts and Sciences, Dept. of Computer Science. Title and description from dissertation home page (viewed Apr. 7, 2004). Includes bibliographical references.

In recent years there has been an exponential growth in Internet traffic resulting in increased network bandwidth requirements which, in turn, has led to stringent processing requirements on network layer devices like routers. Present backbone routers on OC 48 links (2.5Gbps) have to process four million minimum-sized packets per second. Further, the functionality supported in the network devices is also on the increase leading to programmable processors, such as Intel's IXP, Motorola's C5 and IBM's.NP. These processors support multiple processors and multiple threads to exploit packet-level-parallelism inherent in network workloads. This thesis studies the performance of network processors. We develop a Petri Net model for a commercial network processors (Intel IXP 2400,2850) for three different applications viz., IPv4 forwarding, Network Address Translation and IP security protocols. A salient feature of the Petri net model is its ability to model the application, architecture and their interaction in great detail. The model is validated using the intel proprietary tool (SDK 3.51 for IXP architecture) over a range of configurations. Our Performance evaluation results indicate that 1. The IXP processor is able to support a throughput of 2.5 Gbps for all modeled applications. 2. Packet buffer memory (DRAM) is the bottleneck resource in a network proces sor and even multithreading is ineffective beyond a total of 16 threads in case of header processing applications and beyond 32 threads for payload processing applications. Since DRAM is the bottleneck resource we explore the benefits of increasing the DRAM banks and other software schemes like offloading the packet header to SRAM. The second part of the thesis studies the impact of parallel processing in network processor on packet reordering and retransmission. Our results indicate that the concurrent processing of packets in a network processor and buffer allocation schemes in TFIFO leads to a significant packet reordering, (61%), on a 10-hop network (with packet sizes of 64 B) which in turn leads to a 76% retransmission under the TCP fast-restransmission algorithm. We explore different transmit buffer allocation schemes namely, contiguous, strided, local, and global for transmit buffer which reduces the packet retransmission to 24%. Our performance results also indicate that limiting the number of microengines can reduce the extent of packet reordering while providing the same throughput. We propose an alternative scheme, Packetsort, which guarantees complete packet ordering while achieving a throughput of 2.5 Gbps. Further, we observe that Packetsort outperforms, by up to 35%, the in-built schemes in the IXP processor namely, Inter Thread Signaling (ITS) and Asynchronous Insert and Synchronous Remove (AISR). The final part of this thesis investigates the performance of the network processor in a bursty traffic scenario. We model bursty traffic using a Pareto distribution. We consider a parallel and pipelined buffering schemes and their impact on packet drop under bursty traffic. Our results indicate that the pipelined buffering scheme outperforms the parallel scheme.

Thesis (M.Sc.)--York University, 2005. Graduate Programme in Computer Science and Engineering.
Typescript. Includes bibliographical references (leaves 139-145). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss &rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR11871

by Patrick C.K. Wu.
Thesis (M.Phil.)--Chinese University of Hong Kong, 1998.
Includes bibliographical references (leaves 57-[59]).
Abstract also in Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Research Objectives --- p.2
Chapter 1.2 --- Organization of the Thesis --- p.2
Chapter 2 --- Background --- p.4
Chapter 2.1 --- Reliable Multicasting --- p.4
Chapter 2.2 --- Related Work --- p.5
Chapter 2.2.1 --- RMTP --- p.5
Chapter 2.2.2 --- RMP --- p.6
Chapter 2.2.3 --- RAMP --- p.7
Chapter 2.3 --- Multicast with Scalable Reliability (MSR) --- p.8
Chapter 3 --- Traffic Shaping in MSR --- p.10
Chapter 3.1 --- Single Queue System --- p.11
Chapter 3.2 --- Scaling factor α --- p.12
Chapter 4 --- Retransmission Scheme in MSR --- p.15
Chapter 4.1 --- Packet Loss Detection and Requests for Retransmission at the Receivers --- p.17
Chapter 4.2 --- Retransmission at the Sender --- p.19
Chapter 4.3 --- Dynamic Adjustment of Retransmission Timeout Value --- p.22
Chapter 4.4 --- Scaling Reliability using Transmit-Display Window --- p.29
Chapter 5 --- NACK Implosion Prevention --- p.31
Chapter 5.1 --- Electing a Representative Receiver --- p.32
Chapter 5.2 --- Determining T --- p.33
Chapter 5.3 --- Determining β --- p.34
Chapter 6 --- Performance Study of MSR --- p.38
Chapter 6.1 --- Performance Study of MSR in Simple Network Topologies --- p.39
Chapter 6.2 --- Star Topology --- p.40
Chapter 6.3 --- Tree Topology --- p.44
Chapter 6.4 --- Exploring the use of MSR Gateway --- p.47
Chapter 7 --- Conclusion and Future Work --- p.50
Chapter 7.1 --- Future Work --- p.50
Chapter 7.2 --- Conclusions --- p.51
Chapter A --- MSR Packet Formats --- p.52
Chapter A.1 --- MSR Fixed Header --- p.52
Chapter A.2 --- MSR Audio Data Header --- p.54
Chapter A.3 --- MSR NACK Packets --- p.55
Bibliography --- p.57

Chan Kwun-chung.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2001.
Includes bibliographical references (leaves 71-73).
Abstracts in English and Chinese.
摘要 --- p.II
ABSTRACT --- p.III
ACKNOWLEDGEMENT --- p.V
TABLE OF CONTENTS --- p.VI
LIST OF FIGURES --- p.X
LIST OF SYMBOLS --- p.XII
Chapter 1. --- INTRODUCTION --- p.1
Chapter 1.1 --- Contributions --- p.3
Chapter 1.2 --- Organization of the Thesis --- p.4
Chapter 1.3 --- Publications --- p.5
Chapter 2. --- RELATED WORKS --- p.6
Chapter 2.1 --- Previous VOD System --- p.7
Chapter 2.1.1 --- Service Model --- p.7
Chapter 2.1.1.1 --- Unicast VOD --- p.7
Chapter 2.1.1.2 --- Multicast VOD --- p.8
Chapter 2.1.2 --- Architecture --- p.9
Chapter 2.1.2.1 --- Centralized Architecture --- p.9
Chapter 2.1.2.2 --- Distributed Architecture --- p.10
Chapter 2.1.3 --- Interactive Function --- p.11
Chapter 2.1.3.1 --- Limited Interactive Function --- p.11
Chapter 2.1.3.2 --- Unlimited Interactive Function --- p.11
Chapter 2.1.4 --- Split and Merge Operation --- p.12
Chapter 2.1.4.1 --- SAM Scheme (Split and Merge) --- p.12
Chapter 2.1.4.2 --- SRMDRU Scheme (Single Rate Multicast Double Rate Unicast) --- p.14
Chapter 2.2 --- Previous Caching Algorithm --- p.15
Chapter 2.2.1 --- LFU (Least Frequently Used) --- p.15
Chapter 2.2.2 --- LRU (Least Recently Used) --- p.15
Chapter 2.2.3 --- Media Stream Caching --- p.15
Chapter 3. --- DESIGN OFA NOVEL VOD SYSTEM --- p.17
Chapter 3.1 --- System Architecture --- p.18
Chapter 3.1.1 --- Multicast Video Server Cluster (MVSC) --- p.19
Chapter 3.1.2 --- Unicast Video Server Cluster (UVSC) --- p.20
Chapter 3.1.3 --- Multicast Backbone Network (MBN) --- p.20
Chapter 3.1.4 --- Local Distribution Network (LDN) --- p.21
Chapter 3.1.5 --- Distributed Interactive Server (DIS) --- p.21
Chapter 3.1.6 --- Distributed Proxy Server (DPS) --- p.22
Chapter 3.1.7 --- Client Station (CS) --- p.22
Chapter 3.2 --- Batched Multicast Transmission --- p.24
Chapter 3.3 --- Split and Merge Operation --- p.26
Chapter 3.4 --- Interactive Function --- p.31
Chapter 3.4.1 --- Pause --- p.31
Chapter 3.4.2 --- Slow Motion --- p.35
Chapter 3.4.3 --- Various Speed Fast Forward / Fast Rewind (FF/REW) --- p.37
Chapter 3.4.4 --- Jump Forward/Jump Backward (JF/JB) --- p.42
Chapter 3.5 --- Performance Analysis --- p.46
Chapter 3.5.1 --- Model --- p.46
Chapter 3.5.2 --- System Parameters --- p.49
Chapter 3.5.3 --- Results --- p.49
Chapter 4. --- DESIGN OF A VIDEO PROXY SYSTEM --- p.57
Chapter 4.1 --- Video Proxy System --- p.58
Chapter 4.1.1 --- Priority Function --- p.59
Chapter 4.1.2 --- Two-Stage Replacement Policy --- p.60
Chapter 4.1.3 --- Caching Policy --- p.61
Chapter 4.2 --- Performance Evaluation --- p.63
Chapter 4.2.1 --- Simulation Environment --- p.63
Chapter 4.2.2 --- Performance Metric --- p.64
Chapter 4.2.3 --- Results --- p.64
Chapter 5. --- CONCLUSION --- p.69
BIBLIOGRAPHY --- p.71

Network on Chips[1][2][3][4] are critical elements of modern System on Chip(SoC) as well as Chip Multiprocessor(CMP)designs. Network on Chips (NoCs) help manage high complexity of designing large chips by decoupling computation from communication. SoCs and CMPs have a multiplicity of communicating entities like programmable processing elements, hardware acceleration engines, memory blocks as well as off-chip interfaces. With power having become a serious design constraint[5], there is a great need for designing NoC which meets the target communication requirements, while minimizing power using all the tricks available at the architecture, microarchitecture and circuit levels of the de-sign. This thesis presents a holistic, QoS based, power optimal design solution of a NoC inside a CMP taking into account link microarchitecture and processor tile configurations. Guaranteeing QoS by NoCs involves guaranteeing bandwidth and throughput for connections and deterministic latencies in communication paths. Label Switching based Network-on-Chip(LS-NoC) uses a centralized LS-NoC Management framework that engineers traffic into QoS guaranteed routes. LS-NoC uses label switching, enables band-width reservation, allows physical link sharing and leverages advantages of both packet and circuit switching techniques. A flow identification algorithm takes into account band-width available in individual links to establish QoS guaranteed routes. LS-NoC caters to the requirements of streaming applications where communication channels are fixed over the lifetime of the application. The proposed NoC framework inherently supports heterogeneous and ad-hoc SoC designs. A multicast, broadcast capable label switched router for the LS-NoC has been de-signed, verified, synthesized, placed and routed and timing analyzed. A 5 port, 256 bit data bus, 4 bit label router occupies 0.431 mm2 in 130nm and delivers peak band-width of80Gbits/s per link at312.5MHz. LS Router is estimated to consume 43.08 mW. Bandwidth and latency guarantees of LS-NoC have been demonstrated on streaming applications like Hiper LAN/2 and Object Recognition Processor, Constant Bit Rate traffic patterns and video decoder traffic representing Variable Bit Rate traffic. LS-NoC was found to have a competitive figure of merit with state-of-the-art NoCs providing QoS. We envision the use of LS-NoC in general purpose CMPs where applications demand deterministic latencies and hard bandwidth requirements. Design variables for interconnect exploration include wire width, wire spacing, repeater size and spacing, degree of pipelining, supply, threshold voltage, activity and coupling factors. An optimal link configuration in terms of number of pipeline stages for a given length of link and desired operating frequency is arrived at. Optimal configurations of all links in the NoC are identified and a power-performance optimal NoC is presented. We presents a latency, power and performance trade-off study of NoCs using link microarchitecture exploration. The design and implementation of a framework for such a design space exploration study is also presented. We present the trade-off study on NoCs by varying microarchitectural(e.g. pipelining) and circuit level(e.g. frequency and voltage) parameters. A System-C based NoC exploration framework is used to explore impacts of various architectural and microarchitectural level parameters of NoC elements on power and performance of the NoC. The framework enables the designer to choose from a variety of architectural options like topology, routing policy, etc., as well as allows experimentation with various microarchitectural options for the individual links like length, wire width, pitch, pipelining, supply voltage and frequency. The framework also supports a flexible traffic generation and communication model. Latency, power and throughput results using this framework to study a 4x4 CMP are presented. The framework is used to study NoC designs of a CMP using different classes of parallel computing benchmarks[6]. One of the key findings is that the average latency of a link can be reduced by increasing pipeline depth to a certain extent, as it enables link operation at higher link frequencies. Abstract There exists an optimum degree of pipelining which minimizes the energy-delay product of the link. In a 2D Torus when the longest link is pipelined by 4 stages at which point least latency(1.56 times minimum) is achieved and power(40% of max) and throughput (64%of max) are nominal. Using frequency scaling experiments, power variations of up to40%,26.6% and24% can be seen in 2D Torus, Reduced 2D Torus and Tree based NoC between various pipeline configurations to achieve same frequency at constant voltages. Also in some cases, we find that switching to a higher pipelining configuration can actually help reduce power as the links can be designed with smaller repeaters. We also find that the overall performance of the ICNs is determined by the lengths of the links needed to support the communication patterns. Thus the mesh seems to perform the best amongst the three topologies(Mesh, Torus and Folded Torus) considered in case studies. The effects of communication overheads on performance, power and energy of a multiprocessor chip using L1,L2 cache sizes as primary exploration parameters using accurate interconnect, processor, on-chip and off-chip memory modelling are presented. On-chip and off-chip communication times have significant impact on execution time and the energy efficiency of CMPs. Large cache simply larger tile area that result in longer inter-tile communication link lengths and latencies, thus adversely impacting communication time. Smaller caches potentially have higher number of misses and frequent of off-tile communication. Energy efficient tile design is a configuration exploration and trade-off study using different cache sizes and tile areas to identify a power-performance optimal configuration for the CMP. Trade-offs are explored using a detailed, cycle accurate, multicore simulation frame-work which includes superscalar processor cores, cache coherent memory hierarchies, on-chip point-to-point communication networks and detailed interconnect model including pipelining and latency. Sapphire, a detailed multiprocessor execution environment integrating SESC, Ruby and DRAM Sim was used to run applications from the Splash2 benchmark(64KpointFFT).Link latencies are estimated for a16 core CMP simulation on Sapphire. Each tile has a single processor, L1 and L2 caches and a router. Different sizesofL1 andL2lead to different tile clock speeds, tile miss rates and tile area and hence interconnect latency. Simulations across various L1, L2 sizes indicate that the tile configuration that maximizes energy efficiency is related to minimizing communication time. Experiments also indicate different optimal tile configurations for performance, energy and energy efficiency. Clustered interconnection network, communication aware cache bank mapping and thread mapping to physical cores are also explored as potential energy saving solutions. Results indicate that ignoring link latencies can lead to large errors in estimates of program completion times, of up to 17%. Performance optimal configurations are achieved at lower L1 caches and at moderateL2 cache sizes due to higher operating frequencies and smaller link lengths and comparatively lesser communication. Using minimal L1 cache size to operate at the highest frequency may not always be the performance-power optimal choice. Larger L1 sizes, despite a drop in frequency, offer a energy advantage due to lesser communication due to misses. Clustered tile placement experiments for FFT show considerable performance per watt improvement (1.2%). Remapping most accessed L2 banks by a process in the same core or neighbouring cores after communication traffic analysis offers power and performance advantages. Remapped processes and banks in clustered tile placement show a performance per watt improvement of5.25% and energy reductionof2.53%. This suggests that processors could execute a program in multiple modes, for example, minimum energy, maximum performance.

Indiana University-Purdue University Indianapolis (IUPUI)
In general, profiling sensors are low-cost crude imagers that typically utilize a sparse detector array, whereas traditional cameras employ a dense focal-plane array. Profiling sensors are of particular interest in applications that require classification of a sensed object into broad categories, such as human, animal, or vehicle. However, profiling sensors have many other applications in which reliable classification of a crude silhouette or profile produced by the sensor is of value. The notion of a profiling sensor was first realized by a Near-Infrared (N-IR), retro-reflective prototype consisting of a vertical column of sparse detectors. Alternative arrangements of detectors have been implemented in which a subset of the detectors have been offset from the vertical column and placed at arbitrary locations along the anticipated path of the objects of interest. All prior work with the N-IR, retro-reflective profiling sensors has consisted of wired detectors. This thesis surveys prior work and advances this work with a wireless profiling sensor prototype in which each detector is a wireless sensor node and the aggregation of these nodes comprises a profiling sensor’s field of view. In this novel approach, a base station pre-processes the data collected from the sensor nodes, including data realignment, prior to its classification through a back-propagation neural network. Such a wireless detector configuration advances deployment options for N-IR, retro-reflective profiling sensors.