12715963
Multiple-antenna signal constellations for fading channels
In this correspondence, we show that the problem of designing efficient multiple-antenna signal constellations for fading channels can be related to the problem of finding packings with large minimum distance in the complex Grassmannian space. We describe a numerical optimization procedure for finding good packings in the complex Grassmannian space and report the best signal constellations found by this procedure. These constellations improve significantly upon previously known results.
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. >
21366301
The EM Side-Channel(s)
We present results of a systematic investigation of leakage of compromising information via electromagnetic (EM) emanations from CMOS devices. These emanations are shown to consist of a multiplicity of signals, each leaking somewhat different information about the underlying computation. We show that not only can EM emanations be used to attack cryptographic devices where the power side-channel is unavailable, they can even be used to break power analysis countermeasures.
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.
14060994
On nearest neighbor indexing of nonlinear trajectories
In recent years, the problem of indexing mobile objects has assumed great importance because of its relevance to a wide variety of applications. Most previous results in this area have proposed indexing schemes for objects with linear trajectories in one or two dimensions. In this paper, we present methods for indexing objects with nonlinear trajectories. Specifically, we identify a useful condition called the convex hull property and show that any trajectory satisfying this condition can be indexed by storing a careful representation of these objects in a traditional index structure. Since a wide variety of relevant nonlinear trajectories satisfy this condition, our result significantly expands the class of trajectories for which nearest neighbor indexing schemes can be devised. We also show that even though many non-linear trajectories do not satisfy the convex hull condition, an approximate representation can often be found which satisfies it. We discuss examples of techniques which can be utilized to find representations that satisfy the convex hull property. We present empirical results to demonstrate the effectiveness of our indexing method.
15003245
Probabilistic treatment of MIXes to hamper traffic analysis
The goal of anonymity providing techniques is to preserve the privacy of users, who has communicated with whom, for how long, and from which location, by hiding traffic information. This is accomplished by organizing additional traffic to conceal particular communication relationships and by embedding the sender and receiver of a message in their respective anonymity sets. If the number of overall participants is greater than the size of the anonymity set and if the anonymity set changes with time due to unsynchronized participants, then the anonymity technique becomes prone to traffic analysis attacks. We are interested in the statistical properties of the disclosure attack, a newly suggested traffic analysis attack on the MIXes. Our goal is to provide analytical estimates of the number of observations required by the disclosure attack and to identify fundamental (but avoidable) 'weak operational modes' of the MIXes and thus to protect users against a traffic analysis by the disclosure attack.
32852748
Asynchronous Parallel Arc Consistency Algorithms on a Distributed Memory Machine
Abstract The use of arc consistency algorithms can greatly reduce the search space of a constraint satisfaction problem by preprocessing and eliminating variable assignments which can never participate in a solution. This paper examines two variations in the frequency of communications of three parallel arc consistency algorithms on distributed memory machines. This paper also examines the effect of simple load balancing versus the more robust mean field annealing graph partitioning heuristic on speedup. Through actual machine experimentation, we compute time required for the algorithms based on such parameters as distribution of work, frequency of message passing, and load balancing. Results indicate that the configuration with less frequent communications and the robust load balancing yields the best speedup.
206573197
Efficient Deadlock-Free Wormhole Routing and Virtual-Channel Reduction in Shuffle-Based Networks
Many aspects of shuffle-based networks have recently been studied by numerous researchers. However, no attention has been paid to deadlock-free wormhole routing algorithms. In this paper, for a set of shuffle-based networks, we introduce a graph-partitioning technique that enables a deadlock-free routing algorithm with fewer virtual channels than the known algorithms. This is achieved for the de Bruijn digraphs which are shown to require a maximum ofm? ?(m? 1)/r? virtual channels per physical channel, wheremis the diameter andris the radix. Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) graph and the Shuffle?Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r,Nb,n) requires a maximum ofm? ?(m? 1)/r? virtual channels for the outcluster channels, and a maximum ofm+ 1 ? ?m/r? virtual channels for the incluster channels in most cases, wherem= ?logrNb?,ris the radix of a generalized de Bruijn graph of sizeNb, andnrepresents the number of dimensions in a binary hypercube. We also show that a maximum ofm? ?(m? 1)/2? virtual channels are required in shuffle-exchange networks with 2mnodes.
1945809
A Parallelization Domain Oriented Multilevel Graph Partitioner
In this paper we present a novel multilevel graph partitioning algorithm, KACE, which uses knowledge about the domain and employs several graph transformation techniques. Both functional and structural parallelism in the sequential code are explored to improve the quality of parallel tasks. Statistical information about communication times between nodes as a function of message size and/or other factors are used to have a better estimate of balancing factors, code replication, and synchronization penalties. This enables us to use a task cohesion algorithm to obtain a coarse version of the partitioned graph. Many of KACE's parameters are shown to have definite impact on the parallelized program code.
17088385
QoS and energy aware routing for real-time traffic in wireless sensor networks
Wireless sensor networks are being built to facilitate automated information gathering in military, industrial, environmental and surveillance applications. Many such applications of Sensor Networks require improved QoS (packet delivery within a defined deadline) guarantees as well as high reliability. These applications demand high packet delivery ratio and are extremely delay-sensitive. However, certain factors limit the ability of the multihop sensor network to achieve the desired goals. These factors include the delay caused by network congestion, hot regions in the network, limited energy of the sensor nodes, packet loss due to collisions and link failure. In this paper, we propose an energy aware dual-path routing scheme for real-time traffic, which balances node energy utilization to increase the network lifetime, takes network congestion into account to reduce the routing delay across the network and increases the reliability of the packets reaching the destination by introducing minimal data redundancy. This paper also introduces an adaptive prioritized Medium Access Layer (MAC) to provide a differentiated service model for real-time packets. Our claims are well supported by simulation results.
12552557
Minimizing the effect of deafness and hidden terminal problem in wireless ad hoc networks using directional antennas
In this work we addresses the issue of deafness and hidden terminal problem in Mobile Ad Hoc Networks (MANETs) using directional antennas. To minimize these effects, we propose a MAC protocol for directional Antennas (MDA) 5 which employs a novel Enhanced Directional Network Allocation Vector (EDNAV) scheme and, and an efficient technique of Diametrically Opposite Directions (DOD) transmission of RTS and CTS. We compare MDA with IEEE 802.11 and two recently proposed directional MAC schemes and results show that MDA outperforms these protocols in the majority of scenarios investigated. We also point out that the performance does depend on the network topology and the traffic pattern.