<p>Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.</p>

Scaling of CMOS to nanometer dimensions has enabled dramatic improvement in digital power efficiency, with lower VDD supply voltage and decreased power consumption for logic functions. However, most traditionally prevalent ADC architectures are not well suited to the lower VDD environment. The improvement in time resolution enabled by increased digital speeds naturally drives design toward time-domain architectures such as voltage-controlled-oscillator (VCO) based ADCs. The major obstacle in the VCO-based technique is linearizing the VCO voltage-to-frequency characteristic. Achieving signal-to-noise (SNR) performance better than -40dB requires some form of calibration, which can be realized by analog or digital techniques, or some combination. A further challenge is implementing calibration without degrading energy efficiency performance. This thesis project discusses a complete design of a 10 bit three stage ring VCO-based ADC. A lookup-table (LUT) digital correction technique enabled by the "Split ADC" calibration approach is presented suitable for linearization of the ADC. An improvement in the calibration algorithm is introduced to ensure LUT continuity. Measured results for a 10 bit 48.8-kSps ADC show INL improvement of 10X after calibration convergence.

A substantial increase in the number of internet users and the traffic volume bring new challenges for network router design. The current routers need to support higher link data rates and large number of line cards to accommodate the growth of the internet traffic, which necessitate an increase in physical space, power and memory use. Packet forwarding, which is one of the major tasks of a router, has been a performance bottleneck in internet infrastructure. In general, most of the packet forwarding algorithms are implemented in software. However, hardware based solutions has also been popular in recent years because of their high throughput performance. Besides throughput, memory efficiency, incremental/dynamic updates and power consumption are the basic performance challenges for packet forwarding architectures. Hardware-based packet forwarding engines for network routers can be categorized into two groups that are ternary content addressable memory (TCAM) based and dynamic/static random access memory (DRAM/SRAM) based solutions. TCAM-based architectures are simple and hence popular solutions for today&rsquo / s routers. However, they are expensive, power-hungry, and oer little adaptability to new addressing and routing protocols. On the other hand, SRAM has higher density, lower power consumption, and higher speed. The common data structure used in SRAM-based solutions for performing longest prefix matching (LPM) is some type of a tree. In these solutions, multiple memory accesses are required to find the longest matched prefix. Therefore, parallel and pipelining techniques are used to improve the throughput. This thesis studies TCAM and SRAM based parallel and pipelined architectures for high performance packet forwarding. We proposed to use a memory efficient disjoint prefix set algorithm on TCAM based parallel IP packet forwarding engine to improve its performance. As a fundamental contribution of this thesis, we designed an SRAM based parallel, intersecting and variable length multi-pipeline array structure (SAFIL) for trie-based internet protocol (IP) lookup. We also proposed a novel dual port SRAM based high throughput IP lookup engine (SAFILD) which is built upon SAFIL. As an alternative to traditional binary trie, we proposed a memory efficient data structure called compact clustered trie (CCT) for IP lookup. Furthermore, we developed a novel combined length-infix pipelined search (CLIPS) architecture for high performance IPv4/v6 lookup on FPGA. Finally, we designed a memory efficient clustered hierarchical search structure (CHSS) for packet classification. A linear pipelined SRAM-based architecture for CHSS which is implemented on FPGA is also proposed.

The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. This problem was first introduced by Grenander and brought to computer science by Bentley in 1984. This problem has been branched out into other problems based on their characteristics. k-overlapping maximum subarray problem where the overlapping solutions are allowed, and k-disjoint maximum subarray problem where all the solutions are disjoint from each other are those. For k-overlapping maximum subarray problems, significant improvement have been made since the problem was first introduced. For k-disjoint maximum subarrsy, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(kn^3) time is easily obtainable for two-dimensions, little study has been undertaken to better this. This paper introduces a faster algorithm for the k-disjoint maximum sub-array problem under the conventional RAM model, based on distance matrix multiplication. Also, DMM reuse technique is introduced for the maximum subarray problem based on recursion for space optimization.

Hypertext markup language 5 (HTML5), a new standard for HTML, enriched with additional features is expected to override all the basic underlying overhead needed by other applications. By the advent of new extension, HTML5, the web’s basic language is transplanted from a simple page layout into rich web application development language. Furthermore, with the release of HTML5, traditional browsing is expected to change and modify accordingly and on the other hand the potential users will have an alternative rather than sticking in platform and OS dependent native applications. This thesis deals with the readiness assessment of HTML5 with regard to different smart phones- Android and Windows. In order to visualize the fact, we analyzed different constraints like DNS lookup time, page loading time, memory and CPU consumption associated with two applications-Flash and HTML5 running right through the smart phones. Furthermore, the comparative analysis is performed in different network scenarios- Wi-Fi and 3G and user experience is estimated based on network parameters. From the experiments and observations taken, we found that android phones provide better support for HTML5 web applications than windows mobile devices. Also, the HTML5 applications loading time is limited by the browser rendering time rather that the content loading time from the network and is also dependent on hardware configuration of device used.

The aim of this dissertation is to provide a unified treatment of various spell checkers and correctors. Firstly, the spell checking and correcting problems are formally described in mathematics in order to provide a better understanding of these tasks. An approach that is similar to the way in which denotational semantics used to describe programming languages is adopted. Secondly, the various attributes of existing spell checking and correcting techniques are discussed. Extensive studies on selected spell checking/correcting algorithms and packages are then performed. Lastly, an empirical investigation of various spell checking/correcting packages is presented. It provides a comparison and suggests a classification of these packages in terms of their functionalities, implementation strategies, and performance. The investigation was conducted on packages for spell checking and correcting in English as well as in Northern Sotho and Chinese. The classification provides a unified presentation of the strengths and weaknesses of the techniques studied in the research. The findings provide a better understanding of these techniques in order to assist in improving some existing spell checking/correcting applications and future spell checking/correcting package designs and implementations. / Dissertation (MSc)--University of Pretoria, 2009. / Computer Science / unrestricted

In this study, the focus is on facilitating the API discovery process for developers and organizations. According to research articles, APIs are discussed in this research as the fundamental areas that are considered significant when developers or organizations explore an API. The areas include usability, documentation, stability, collaborative communities, and the popularity of an API. We created a design and creation research process and listed key aspects of each mentioned area above in a final artifact, where the idea is to allow people to look at the artifact and use it in a possible API exploration. In conclusion, the artifact covers usability, documentation, stability, and collaborative communities. There are leading questions in the artifact to determine whether or not an API is suitable for a given purpose.

Simulating the human heart is a challenging problem, with simulations being very time consuming, to the extent that some can take days to compute even on high performance computing resources. There is considerable interest in computational optimisation techniques, with a view to making whole-heart simulations tractable. Reliability of heart model simulations is also of great concern, particularly considering clinical applications. Simulation software should be easily testable and maintainable, which is often not the case with extensively hand-optimised software. It is thus crucial to automate and verify any optimisations. CellML is an XML language designed for describing biological cell models from a mathematical modeller’s perspective, and is being developed at the University of Auckland. It gives us an abstract format for such models, and from a computer science perspective looks like a domain specific programming language. We are investigating the gains available from exploiting this viewpoint. We describe various static checks for CellML models, notably checking the dimensional consistency of mathematics, and investigate the possibilities of provably correct optimisations. In particular, we demonstrate that partial evaluation is a promising technique for this purpose, and that it combines well with a lookup table technique, commonly used in cardiac modelling, which we have automated. We have developed a formal operational semantics for CellML, which enables us to mathematically prove the partial evaluation of CellML correct, in that optimisation of models will not change the results of simulations. The use of lookup tables involves an approximation, thus introduces some error; we have analysed this using a posteriori techniques and shown how it may be managed. While the techniques could be applied more widely to biological models in general, this work focuses on cardiac models as an application area. We present experimental results demonstrating the effectiveness of our optimisations on a representative sample of cardiac cell models, in a variety of settings.

This dissertation studies the design of an efficient adaptive digital baseband predistorter for modern cellular handsets that combines low power consumption, low implementation complexity, and high performance. The proposed enhancements are optimized for hardware implementation. We first present a thorough study of the optimal spacing of linearly-interpolated lookup table predistorters supported by theoretical calculations and extensive simulations. A constant-SNR compander that increases the predistorter's supported input dynamic range is derived. A corresponding low-complexity approximation that lends itself to efficient hardware design is also implemented in VHDL and synthesized with the Synopsys Design Compiler. This dissertation also proposes an LMS-based predistorter adaptation that is optimized for hardware implementation and compares the effectiveness of the direct and indirect learning architectures. A novel predistorter design with quadrature imbalance correction capability is developed and a corresponding adaptation scheme is proposed. This robust predistorter configuration is designed by combining linearization and I/Q imbalance correction into a single function with the same computational complexity as the widespread complex-gain predistorter.

>Magister Scientiae - MSc / Many South African Deaf people use their mobile phones for communication with SMSs yet they would prefer to converse in South African Sign Language. Deaf people with a capital `D' are different from deaf or hard of hearing as they primarily use sign language to communicate. This study explores how to design and evaluate a prototype that will allow a Deaf person using SASL to tell a hearing doctor how s/he is feeling and provide a way for the doctor to respond. A computer{based prototype was designed and evaluated with the Deaf people in a previous study. Results from the user trial of the computer{based mock{up indicated that Deaf users would like to see the prototype on a cell phone. Those user trial results, combined with our own user survey results conducted with Deaf people, are used as requirements. We built a prototype for a mobile phone browser by embedding SASL videos inside XHTML pages using Adobe Flash. The prototype asks medical questions using SASL videos. These questions are arranged in an organized way that helps in identifying a medical problem. The answers to the questions are then displayed in English and shown to the doctor on the phone. A content authoring tool was also designed and implemented. The content authoring tool is used for populating the prototype in a context free manner allowing for plug and play scenarios such as a doctor's office, Department of Home A airs or police station. A focus group consisting of Deaf people was conducted to help in the design and pilot trial of the system. A final user trial was conducted with more than thirty Deaf people and the results are presented and analyzed. Data is collected with questionnaires, semi-structured interviews and video recordings. The results indicate that most of the Deaf people found the system easy to learn, easy to navigate through, did not get lost and understood the sign language in the videos on the mobile phone. The hand gestures and facial expressions on the sign language videos were clear. Most of them indicated they would like to use the system for free, and that the system did not ask too many questions. Most of them were happy with the quality of the sign language videos on the mobile phone and would consider using the system in real life. Finally they felt their private information was safe while using the system. Many South African Deaf people use their mobile phones for communication with SMSs yet they would prefer to converse in South African Sign Language. Deaf people with a capital `D' are different from deaf or hard of hearing as they primarily use sign language to communicate. This study explores how to design and evaluate a prototype that will allow a Deaf person using SASL to tell a hearing doctor how s/he is feeling and provide a way for the doctor to respond. A computer{based prototype was designed and evaluated with the Deaf people in a previous study. Results from the user trial of the computer{based mock{up indicated that Deaf users would like to see the prototype on a cell phone. Those user trial results, combined with our own user survey results conducted with Deaf people, are used as requirements. We built a prototype for a mobile phone browser by embedding SASL videos inside XHTML pages using Adobe Flash. The prototype asks medical questions using SASL videos. These questions are arranged in an organized way that helps in identifying a medical problem. The answers to the questions are then displayed in English and shown to the doctor on the phone. A content authoring tool was also designed and implemented. The content authoring tool is used for populating the prototype in a context free manner allowing for plug and play scenarios such as a doctor's office, Department of Home A airs or police station. A focus group consisting of Deaf people was conducted to help in the design and pilot trial of the system. A final user trial was conducted with more than thirty Deaf people and the results are presented and analyzed. Data is collected with questionnaires, semi-structured interviews and video recordings. The results indicate that most of the Deaf people found the system easy to learn, easy to navigate through, did not get lost and understood the sign language in the videos on the mobile phone. The hand gestures and facial expressions on the sign language videos were clear. Most of them indicated they would like to use the system for free, and that the system did not ask too many questions. Most of them were happy with the quality of the sign language videos on the mobile phone and would consider using the system in real life. Finally they felt their private information was safe while using the system. / South Africa