No description available.

No description available.

With the extent of the web expanding at an increasing rate, the problems caused by broken links are reaching epidemic proportions. Studies have indicated that a substantial number of links on the Internet are broken. User surveys indicate broken links are considered the third biggest problem faced on the Internet. Currently Walden's Paths Path Manager tool is capable of detecting the degree and type of change within a page in a path. Although it also has the ability to highlight missing pages or broken links, it has no method of correcting them thus leaving the broken link problem unsolved. This thesis proposes a solution to this problem in Walden's Paths. The solution centers on the idea that "significant" keyphrases extracted from the original page can be used to accurately locate the document using a search engine. This thesis proposes an algorithm to extract representative keyphrases to locate exact copies of the original page. In the absence of an exact copy, a similar but separate algorithm is used to extract keyphrases that will help locating similar pages that can be substituted in place of the missing page. Both sets of keyphrases are stored as additions to the page signature in the Path Manager tool and can be used when the original page is removed from its current location on the Web.

As effective routing is critical in mobile ad hoc networks (MANETs), the Ad Hoc On-demand Distance Vector (AODV) has been extensively studied in recent years. AODV is a single path routing protocol that requires a new route discovery procedure whenever a link breaks, such frequent route discoveries incur a high routing overhead and increase end-to-end delay. Therefore, by modifying the AODV protocol, this work presents a novel backup routing scheme capable of repairing disrupted links locally without activating a route re-discovery procedure. Additionally, backup paths are established based on 2-hop neighbor knowledge. These backup paths are geographically close to the primary path in order to provide efficient recovery from route failure and maintain an adequate routing length. Simulation results indicate that the proposed backup routing scheme obtains a lower average end-to-end delay and less routing overhead than those of the Ad hoc On-demand Multipath Distance Vector (AOMDV) and the conventional AODV.

published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

Using numerical simulations and combinatorics, this dissertation focuses on connections between random matrix theory and graph theory.We examine the adjacency matrices of three-regular graphs representing one-face maps. Numerical studies have revealed that the limiting eigenvalue statistics of these matrices are the same as those of much larger, and more widely studied classes of random matrices. In particular, the eigenvalue density is described by the McKay density formula, and the distribution of scaled eigenvalue spacings appears to be that of the Gaussian Orthogonal Ensemble (GOE).A natural question is whether the eigenvalue statistics depend on the genus of the underlying map. We present an algorithm for generating random three-regular graphs representing genus zero one-face maps. Our numerical studies of these three-regular graphs have revealed that their eigenvalue statistics are strikingly different from those of three-regular graphs representing maps of higher genus. While our results indicate that there is a limiting eigenvalue density formula in the genus zero case, it is not described by any established density function. Furthermore, the scaled eigenvalue spacings appear to be described by the exponential distribution function, not the GOE spacing distribution.The embedded graph of a genus zero one-face map is a planar tree, and there is a correlation between its vertices and the primitive cycles of the associated three-regular graph. The second half of this dissertation examines the structure of these embedded planar trees. In particular, we show how the Dyck path representation can be used to recast questions about the probabilistic structure of random planar trees into straightforward counting problems. Using this Dyck path approach, we find:1. the expected number of degree k vertices adjacent to j degree d vertices in a random planar tree, 2. the structure of the planar tree's adjacency matrix under a natural labeling of the vertices, and 3. an explanation for the existence of eigenvalues with multiplicity greater than one in the tree's spectrum.

Thesis (Ph. D.)--University of Hong Kong, 2000. / Includes bibliographical references (leaves 93-98).

No description available.

Current CMOS-based technologies are facing design challenges related to the continuous scaling down of the minimum feature size, according to Moore’s law. Moreover, conventional computing architecture is no longer an effective way of fulfilling modern applications demands, such as big data analysis, pattern recognition, and vector processing. Therefore, there is an exigent need to shift to new technologies, at both the architecture and the device levels. Recently, memristor devices and structures attracted attention for being promising candidates for this job. Memristor device adds a new dimension for designing novel circuits and systems. In addition, high-density memristor-based crossbar is widely considered to be the essential element for future memory and bio-inspired computing systems. However, numerous challenges need to be addressed before the memristor genuinely replaces current memory and computing technologies, which is the motivation behind this research effort. In order to address the technology challenges, we begin by fabricating and modeling the memristor device. The devices fabricated at our local clean room enriched our understanding of the memristive phenomenon and enabled the experimental testing for our memristor-based circuits. Moreover, our proposed mathematical modeling for memristor behavior is an essential element for the theoretical circuit design stage. Designing and addressing the challenges of memristor systems with practical complexity, however, requires an extra step, which takes the form of a reliable and modular simulation platform. We, therefore, built a new simulation platform for the resistive crossbar, which can simulate realistic size arrays filled with real memory data. In addition, this simulation platform includes various crossbar nonidealities in order to obtain accurate simulation results. Consequently, we were able to address the significant challenges facing the high density memristor crossbar, as the building block for resistive-based memory systems and neural computing. For gateless arrays, we present multiport array structure and readout technique, which for the first time introduces a closed-form solution for the challenging crossbar sneak-paths problem. Moreover, a new adaptive threshold readout methodology is proposed, which employs the memory hierarchy locality property in order to improve the access time to the memristor crossbar. Another fast readout technique based on binary counters is presented for locality-less crossbar systems. On the other hand, for gated arrays, we present new readout technique and circuitry that combines the advantages of the gated and gateless memristor arrays, namely the high-density and low-power consumption. In general, the presented structures and readout methodologies empower much faster and power efficient access to the high-density memristive crossbar, compared to other works presented in the literature. Finally, at the circuit level, we propose novel reactance-less oscillators based on memristor devices, which find promising applications in embedded systems and bio-inspired computing. Altogether, we believe that our contributions to the emerging technology help to push it to the next level, shortening the path towards better futuristic computing systems.

We present an online distributed algorithm, the Causation Logging Algorithm (CLA), in which Autonomous Systems (ASes) in the Internet individually report route oscillations/flaps they experience to a central Internet Routing Registry (IRR). The IRR aggregates these reports and may observe what we call causation chains where each node on the chain caused a route flap at the next node along the chain. A chain may also have a causation cycle. The type of an observed causation chain/cycle allows the IRR to infer the underlying policy routing configuration (i.e. the system of economic relationships and constraints on route/path preferences). Our algorithm is based on a formal policy routing model that captures the propagation dynamics of route flaps under arbitrary changes in topology or path preferences. We derive invariant properties of causation chains/cycles for ASes which conform to economic relationships based on the popular Gao-Rexford model. The Gao-Rexford model is known to be safe in the sense that the system always converges to a stable set of paths under static conditions. Our CLA algorithm recovers the type/property of an observed causation chain of an underlying system and determines whether it conforms to the safe economic Gao-Rexford model. Causes for nonconformity can be diagnosed by comparing the properties of the causation chains with those predicted from different variants of the Gao-Rexford model.