32993584
Analysis of a class of cluster-based multiprocessor systems
In this thesis, a cluster-based multiprocessor system is described. Analytical modeling techniques have been developed to compute the cluster-based system reliability. The bandwidth availability is analytically evaluated for uniform and favorite memory references. The results obtained for the cluster-based system are compared with those of the crossbar and multiple-bus systems for the same values of system parameters. The cluster-based system reliability and bandwidth availability are enhanced by proposing a slight modification of the cluster-based system architecture; and the reliability and bandwidth availability of the modified system are analytically evaluated showing the resulting enhancement due to the proposed modification. 
The cluster-based system reduces the network complexity by employing two levels of hierarchy. However, a number of levels greater than two may be needed in systems that have a large number of processors and memory modules, since the goal is to reduce the network complexity without losing much of the performance. The hierarchy of the cluster-based system is extended to any arbitrary number of levels m by introducing a generalized class of m-level hierarchical multiprocessor systems. This system is equivalent to the well-known crossbar system when there is no hierarchy (m = 1), and to the cluster-based system when the number of levels equals two (m = 2). The performance of the m-level hierarchical multiprocessor system is analyzed in terms of the system bandwidth for both hierarchical nonuniform reference (H N R) and uniform reference (U R) models. The results show that for higher rate of local requests the m-level system performs fairly closely to the crossbar system and outperforms a typical multiple-bus system (with the number of buses equal to half the number of processors). The bandwidth of the m-level system is evaluated for different values of m and the results are compared with those of a crossbar system (m = 1). Finally, expressions are derived for the reliability and the bandwidth availability of the m-level hierarchical multiprocessor system for any arbitrary number of levels m for H N R and U R models. The reliability and bandwidth availability results obtained for the m-level system are compared with those of the crossbar and multiple-bus systems.
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.
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.
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.
43408451
Network Intrusion Detection System Using Random Projection Technique
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.
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.
1271310
Policy ratification
It is not sufficient to merely check the syntax of new policies before they are deployed in a system; policies need to be analyzed for their interactions with each other and with their local environment. That is, policies need to go through a ratification process. We believe policy ratification becomes an essential part of system management as the number of policies in the system increases and as the system administration becomes more decentralized. In this paper, we focus on the basic tasks involved in policy ratification. To a large degree, these basic tasks can be performed independent of policy model and language and require little domain-specific knowledge. We present algorithms from constraint, linear, and logic programming disciplines to help perform ratification tasks. We provide an algorithm to efficiently assign priorities to the policies based on relative policy preferences indicated by policy administrators. Finally, with an example, we show how these algorithms have been integrated with our policy system to provide feedback to a policy administrator regarding potential interactions of policies with each other and with their deployment environment.
11368060
Packet classifiers in ternary CAMs can be smaller
Serving as the core component in many packet forwarding, differentiating and filtering schemes, packet classification continues to grow its importance in today's IP networks. Currently, most vendors use Ternary CAMs (TCAMs) for packet classification. TCAMs usually use brute-force parallel hardware to simultaneously check for all rules. One of the fundamental problems of TCAMs is that TCAMs suffer from range specifications because rules with range specifications need to be translated into multiple TCAM entries. Hence, the cost of packet classification will increase substantially as the number of TCAM entries grows. As a result, network operators hesitate to configure packet classifiers using range specifications. In this paper, we optimize packet classifier configurations by identifying semantically equivalent rule sets that lead to reduced number of TCAM entries when represented in hardware. In particular, we develop a number of effective techniques, which include: trimming rules, expanding rules, merging rules, and adding rules. Compared with previously proposed techniques which typically require modifications to the packet processor hardware, our scheme does not require any hardware modification, which is highly preferred by ISPs. Moreover, our scheme is complementary to previous techniques in that those techniques can be applied on the rule sets optimized by our scheme. We evaluate the effectiveness and potential of the proposed techniques using extensive experiments based on both real packet classifiers managed by a large tier-1 ISP and synthetic data generated randomly. We observe significant reduction on the number of TCAM entries that are needed to represent the optimized packet classifier configurations.
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.
13652126
Using certes to infer client response time at the web server
As businesses continue to grow their World Wide Web presence, it is becoming increasingly vital for them to have quantitative measures of the mean client perceived response times of their web services. We present Certes (CliEnt Response Time Estimated by the Server), an online server-based mechanism that allows web servers to estimate mean client perceived response time, as if measured at the client. Certes is based on a model of TCP that quantifies the effect that connection drops have on mean client perceived response time by using three simple server-side measurements: connection drop rate, connection accept rate and connection completion rate. The mechanism does not require modifications to HTTP servers or web pages, does not rely on probing or third party sampling, and does not require client-side modifications or scripting. Certes can be used to estimate response times for any web content, not just HTML. We have implemented Certes and compared its response time estimates with those obtained with detailed client instrumentation. Our results demonstrate that Certes provides accurate server-based estimates of mean client response times in HTTP 1.0/1.1 environments, even with rapidly changing workloads. Certes runs online in constant time with very low overhead. It can be used at websites and server farms to verify compliance with service level objectives.