12993949
High-Speed Arithmetic Arrays
High-speed multifunction arithmetic arrays for multiplication, division, square and square-root operations are presented in this paper. These arrays seem attractive due to their versatility and speed. A recently described quotient-bit evaluation technique that uses the carry-save method in a nonuniform division array is extended here for the restoring-division process. This array includes the multiplication process as well, and the division time approaches that of multiplication. The design objective of multifunctional arithmetic arrays precludes consideration of other high-speed division techniques. A further extension of the restoring division process is shown to make the design of an array for square/square-root operation straightforward. The two underlying arrays can be coalesced to perform any one of the four operations. Possible methods of merging the arrays, with their relative merits, are also discussed. For illustration purposes, complete internal details of such a generalized pipelined array for 4-bit operation is included in this paper. Due consideration is also given to the possibility of large-scale integration of the different arrays illustrated in this paper.
43408451
Network Intrusion Detection System Using Random Projection Technique
40094538
A Generic Design Methodology for Deadlock-Free Routing in Multicomputer Networks
This paper introduces a generic methodology for defining deadlock-free wormhole routing schemes in any arbitrary network. The basic strategy is to partition a graph into subdigraphs with no cyclic dependencies and selectively assign virtual channels. The usefulness of our scheme is shown for the n-dimensional hypercube, the n-dimensional mesh, and the k-ary n-cube torus by identifying subdigraph characteristics that ensure acyclic routing. Further generalization which allows partial cyclic dependencies without deadlock is achieved by our extended generic methodology. We also illustrate how to identify shortest fixed path and nonminimal adaptive routing schemes using minimum required channels.
22890668
Arithmetic Algorithms in a Negative Base
Algorithms are described for the basic arithmetic operations in a negative base. These algorithms are simpler, faster, and more general than those proposed by Sankar et al.
26743853
Design and Analysis of a Class of Highly Scalable Hierarchical Networks: PdBCube
Abstract A class of hierarchical networks called the dBCube, that provides cost-effective and high-performance communication in large multicomputer systems, has recently been introduced. Such a compound graph of a hypercube and a de Bruijn (dB) graph utilizes every node of the hypercube as a gateway for intercluster communication. This paper presents a partially connected dBCube subclass (PdBCube), wherein the use of fewer nodes as gateways makes the PdBCube highly scalable in terms of both the hypercube and the dB size. This enhancement in scalability can be achieved by two different approaches to assigning gateways. Performance degradation of the proposed PdBCube is illustrated in terms of diameter and average distance. Improvement in track efficiency and reduction in cost are observed to be directly related to a decrease in the number of remote links.
15237323
Testing and Fault Tolerance of Multistage Interconnection Networks
Test length is independent of network size in this simple, straightforward methodology for testing MINs (multistage interconnection networks). It requires only four test sequences for single-fault diagnosis. 26 references.
2759775
Distributed channel management in uncoordinated wireless environments
Wireless 802.11 hotspots have grown in an uncoordinated fashion with highly variable deployment densities. Such uncoordinated deployments, coupled with the difficulty of implementing coordination protocols, has often led to conflicting configurations (e.g., in choice of transmission power and channel of operation) among the corresponding Access Points (APs). Overall, such conflicts cause both unpredictable network performance and unfairness among clients of neighboring hotspots. In this paper, we focus on the fairness problem for uncoordinated deployments. We study this problem from the channel assignment perspective. Our solution is based on the notion of channel-hopping, and meets all the important design considerations for control methods in uncoordinated deployments - distributed in nature, minimal to zero coordination among APs belonging to different hotspots, simple to implement, and interoperable with existing standards. In particular, we propose a specific algorithm called MAXchop, which works efficiently when using only non-overlapping wireless channels, but is particularly effective in exploiting partially-overlapped channels that have been proposed in recent literature. We also evaluate how our channel assignment approach complements previously proposed carrier sensing techniques in providing further performance improvements. Through extensive simulations on real hotspot topologies and evaluation of a full implementation of this technique, we demonstrate the efficacy of these techniques for not only fairness, but also the aggregate throughput, metrics.We believe that this is the first work that brings into focus the fairness properties of channel hopping techniques and we hope that the insights from this research will be applied to other domains where a fair division of a system's resources is an important consideration.
3172403
On overlay schemes to support point-in-range queries for scalable grid resource discovery
A resource directory is a critical component of a grid architecture. P2P computing paradigm could address some of the scalability issues that make distributed resource discovery services challenging. Unfortunately, most existing distributed hash table (DHT) based P2P overlays have difficulty in treating attribute range queries that are common in resource discovery lookups. This paper proposes a general framework for range-based resource discovery. In particular, the proposed framework maps tree-structured logical data (i.e., range indexing) onto a DHT-based physical node space (i.e., resource brokers). In this paper, we consider three mapping schemes from the logical space onto the physical space. Each mapping scheme uses a different replication mechanism to reduce range search time and to achieve load balance. We analytically and experimentally compare the performance characteristics (query/update costs and workload distributions) of these schemes and discuss their applicability under different resource discovery service scenarios.
6124477
A counterexample to a Voronoi region conjecture
Given a 2D-symmetric lattice /spl Lambda/, it was conjectured by Forney (1989) that the projection of the Voronoi region R(/spl Lambda/) onto two coordinates equals the Voronoi region of the constituent 2D-sublattice /spl Lambda//spl nu//sub 2/. We present a three-dimensional counterexample. >
7357174
On the design and quantification of privacy preserving data mining algorithms
The increasing ability to track and collect large amounts of data with the use of current hardware technology has lead to an interest in the development of data mining algorithms which preserve user privacy. A recently proposed technique addresses the issue of privacy preservation by perturbing the data and reconstructing distributions at an aggregate level in order to perform the mining. This method is able to retain privacy while accessing the information implicit in the original attributes. The distribution reconstruction process naturally leads to some loss of information which is acceptable in many practical situations. This paper discusses an Expectation Maximization (EM) algorithm for distribution reconstruction which is more effective than the currently available method in terms of the level of information loss. Specifically, we prove that the EM algorithm converges to the maximum likelihood estimate of the original distribution based on the perturbed data. We show that when a large amount of data is available, the EM algorithm provides robust estimates of the original distribution. We propose metrics for quantification and measurement of privacy-preserving data mining algorithms. Thus, this paper provides the foundations for measurement of the effectiveness of privacy preserving data mining algorithms. Our privacy metrics illustrate some interesting results on the relative effectiveness of different perturbing distributions.
40935363
Beacon Signals: What, Why, How, and Where?
Beacons are primarily radio, ultrasonic, optical, laser or other types of signals that indicate the proximity or location of a device or its readiness to perform a task. Beacon signals also carry several critical, constantly changing parameters, such as power-supply information, relative address, location, timestamp, signal strength, available bandwidth resources, temperature and pressure. Although transparent to the user community, beacon signals have made wireless systems more intelligent and human-like. They are an integral part of numerous scientific and commercial applications, ranging from mobile networks to search-and-rescue operations and location-tracking systems. Beacon signals help synchronize, coordinate and manage electronic resources using miniscule bandwidth. Researchers continue to improve their functionality by increasing signal coverage while optimizing energy consumption. Beacon signals' imperceptibility and usefulness in minimizing communication delays and interference are spurring exploratory efforts in many domains, ranging from the home to outer space.