We present Sound Covert, a novel technique using the machine's audio buffer to secretly (and silently) communicate between applications. Sound Covert can achieve more than 2.6Mbps, four orders of magnitude faster than previously published covert channels. Sound Covert can be used for bidirectional communication between malicious applications anywhere within a given VM (including across users and sand boxes), as well as for sending information from within a VM to an application running on the host OS of the same physical machine. It can also be used for sending information from a compromised external web page to a local malicious application through an innocent, unaltered web browser running in the target application's VM. Similarly, Sound Covert enables a malicious application in a VM that also runs a web server to send data to a malicious partner application running on any machine (or VM) that has a web browser.

SDSM is a novel approach for providing secure directory-based distributed shared memory to CPUs that are connected via an untrusted medium. SDSM scales efficiently to thousands of CPUs with less than 0.8% performance reduction, compared to a system with no security.

In multi-level-cell memory, such as flash and phase-change memory, shrinking cell size and the growing number of levels per cell worsen the access rate to capacity ratio and even reduce access rate. We present minimal maximum-level programming, a scheme for expediting cell programming by sharing physical cells among multiple data sectors and exploiting the fact that making moderate changes to a cell's charge level is faster than making large ones. In particular, we encode the data such that in the k th writing of data to a cell, only the lowest k+1 levels are utilized. Unlike in previously proposed cell-sharing schemes, different same-size data sectors occupy different numbers of physical cells, and a cell may hold a fraction of a bit of a given data sector. Nevertheless, the exposed sector size remains unchanged. Data are encoded, but without redundancy. In a four-level cell example, we achieve up to 75% reduction in write latency. Read latency may be degraded, depending on the percentage of utilized capacity.

In multi-level-cell (MLC) memory such as Flash and Phase-change memory, shrinking cell size and the growing number of levels per cell worsen the access-rate to capacity ratio and even reduce access rate. We present Minimal Maximum-Level Programming (MMLP), a scheme for expediting cell writing by sharing physical cells among multiple data pages and exploiting the fact that making moderate changes to a cell's level is faster than making large ones. Reading is also expedited by requiring fewer reference comparisons. In a four-level cell example, we achieve a 32% reduction in write/read latency relative to prior art with negligible area overhead.

This work addresses the scalability and efficiency of RAM-based storage systems wherein multiple objects must be retrieved per user request. Here, much of the CPU work is per server transaction, not per requested item. Adding servers and spreading the data across them also spreads any given set of requested items across more servers, thereby increasing the total number of server transactions per user request. The resulting poor scalability, dubbed the Multi-get Hole, has been reported in Web 2.0 systems using memcached - a popular memory-based key-value storage system. We present Replicate and Bundle (RnB), a somewhat unintuitive approach: rather than add CPUs, we add memory. Object replicas are mapped “randomly” to servers, and requested objects are bundled, selecting replicas so as to minimize the number of servers accessed per user request and thus the total CPU work per request. We studied RnB via simulation in the context of DRAM-based storage, utilizing micro benchmarks and implemented RnB modules for calibration. Our results show that RnB substantially reduces the number of transactions per request, making operation more efficient. Also, unlike most alternatives, RnB permits flexible growth and relatively easy deployment. Finally, in systems wherein data is replicated for other reasons, RnB is nearly free.

In write-once memory (e.g., Flash), a cell's level can only be raised, and erasure is only in bulk. The total number of erasures (endurance) is limited, and drops sharply with technology shrinkage and with cell-capacity increase. The normalized write capacity (ratio of total amount of data that can be written to storage capacity) drops similarly. Various coding schemes enable overwrites at the expense of storage capacity. With all of them, whenever desired data cannot be written to its current page, the page is “retired” for subsequent erasure. Interestingly, however, a retired page can still be used for writing other data, and it has been proposed to try and use retired pages. Simulation results are promising. In this paper, after briefly presenting Retired Page Utilization, we cast it as a cross-page coding technique. We employ Markovian analysis to derive the expected number of random-data writes with RPU, and show how the required state space can sometimes be substantially reduced.

The estimated covariance matrix is a building block for many algorithms, including signal and image processing. The Covariance Method is an estimator for the covariance matrix, favored both as an estimator and in view of the convenient properties of the matrix that it produces. However, the considerable computational requirements limit its use. We present a novel computation algorithm for the covariance method, which dramatically reduces the computational complexity (both ALU operations and memory access) relative to previous algorithms. It has a small memory footprint, is highly parallelizable and requires no synchronization among compute threads. On a 40-core X86 system, we achieve 1200X speedup relative to a straightforward singlecore implementation; even on a single core, 35X speedup is achieved.

In NAND Flash memory featuring multi-level cells (MLC), the width of threshold voltage distributions about their nominal values affects the permissible number of levels and thus storage capacity. Unfortunately, inter-cell coupling causes a cell's charge to affect its neighbors' sensed threshold voltage, resulting in an apparent broadening of these distributions. We present a novel approach, whereby the data written to Flash is constrained, e.g., by forbidding certain adjacent-cell level combinations, so as to limit the maximum voltage shift and thus narrow the distributions. To this end, we present a new family of constrained codes. Our technique can serve for capacity enhancement (more levels) or for improving endurance, retention and bit error rate (wider guard bands between adjacent levels). It may also be combined with various programming order techniques that mitigate the inter-cell coupling effects and with decoding techniques that compensate for them.

Motivated by a problem of transmitting supplemental data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with n receivers R1,..., Rn. He holds an input x ∈ {0,01l}nand wishes to broadcast a single message so that each receiver Ri can recover the bit xi. Each Rihas prior side information about x, induced by a directed graph Grain nodes; Ri knows the bits of a; in the positions {j | (i,j) is an edge of G}.G is known to the sender and to the receivers. We call encoding schemes that achieve this goal INDEXcodes for {0,1}nwith side information graph G. In this paper we identify a measure on graphs, the minrank, which exactly characterizes the minimum length of linear and certain types of nonlinear INDEX codes. We show that for natural classes of side information graphs, including directed acyclic graphs, perfect graphs, odd holes, and odd anti-holes, minrank is the optimal length of arbitrary INDEX codes. For arbitrary INDEX codes and arbitrary graphs, we obtain a lower bound in terms of the size of the maximum acyclic induced subgraph. This bound holds even for randomized codes, but has been shown not to be tight.

Soft errors (or transient faults) are temporary faults that arise in a circuit due to a variety of internal noise and external sources such as cosmic particle hits. Though soft errors still occur infrequently, they are rapidly becoming a major impediment to processor reliability. This is due primarily to processor scaling characteristics. In the past, systems designed to tolerate such faults utilized costly customized solutions, entailing the use of replicated hardware components to detect and recover from microprocessor faults. As the feature size keeps shrinking and with the proliferation of multiprocessor on die in all segments of computer-based systems, the capability to detect and recover from faults is also desired for commodity hardware. For such systems, however, performance and power constitute the main drivers, so the traditional solutions prove inadequate and new approaches are required. We introduce two independent and complementary microarchitecture-level techniques: double execution and double decoding. Both exploit the typically low average processor resource utilization of modern processors to enhance processor reliability. double execution protects the out-of-order part of the CPU by executing each instruction twice. Double decoding uses a second, low-performance low-power instruction decoder to detect soft errors in the decoder logic. These simple-to-implement techniques are shown to improve the processor's reliability with relatively low performance, power, and hardware overheads. Finally, the resulting ¿excessive¿ reliability can even be traded back for performance by increasing clock rate and/or reducing voltage, thereby improving upon single execution approaches.

Congestion arises in cluster-based supercomputers due to contention for links, spreads due to oversubscription of communication resources, and reduces performance. We mitigate it using efficient, scalable adaptive routing and explicit rate calculation. We use virtual circuits for in-order packet delivery; path setup is performed by switches locally with no blocking or backtracking. For random permutations in a slightly enriched fat-tree topology, maximum contention is reduced by up to 50% relative to static routing, but only rate control can translate this into actual gain. Unfortunately, TCP's window-based rate control fails because of the low bandwidth-delay product, and small buffers moreover cause congestion spreading even with a single-packet window. InfiniBand's CCA employs multiple parameters, which must apparently be tuned per topology and traffic pattern. Focusing on phase-based applications, we present a distributed explicit rate-assignment algorithm for completion-time minimization of the communication phase (min-max flow completion). Also, a generally applicable packet-injection scheme for a source with different-rate flows that realizes desired rates even with very small switch buffers. Simulations show that adaptive routing alone is ineffective, rate control's effectiveness is limited, yet together they shorten the communication phase by tens of percents. Finally, our explicit rate-calculation algorithm is faster than current reactive schemes.

A stream compiler (ASC) generates net lists for hardware (FPGA) accelerators from C-like descriptions, obviating the need for hardware skills. The authors present a backend adapter that enables integration of such accelerators with a processor core in the same FPGA. Development of hybrid ASC-accelerated applications using software-only skills is thus made possible, as illustrated by a hybrid power-conscious iDCT implementation

Motivated by a problem of transmitting data over broadcast channels (BirkandKol, INFOCOM1998), we study the following coding problem: a sender communicates with n receivers Rl,.., Rn. He holds an input x isin {0, 1}nand wishes to broadcast a single message so that each receiver Rican recover the bit xi. Each Rihas prior side information about x, induced by a directed graph G on n nodes; Riknows the bits of x in the positions {j | (i, j) is anedge of G}. We call encoding schemes that achieve this goal INDEX codes for {0, 1}nwith side information graph G. In this paper we identify a measure on graphs, the minrank, which we conjecture to exactly characterize the minimum length of INDEX codes. We resolve the conjecture for certain natural classes of graphs. For arbitrary graphs, we show that the minrank bound is tight for both linear codes and certain classes of non-linear codes. For the general problem, we obtain a (weaker) lower bound that the length of an INDEX code for any graph G is at least the size of the maximum acyclic induced subgraph of G

This paper focuses on local computations of distributed aggregation problems on fixed graphs. We define a new metric on problem instances, Veracity Radius (VR), which captures the inherent possibility to compute them locally. We prove that VR yields a tight lower bound on output-stabilization time, i.e., the time until all nodes fix their outputs, as well as a lower bound on quiescence time. We present an efficient aggregation algorithm, I-LEAG, which reaches both output stabilization and quiescence within a time that is proportional to the VR of the problem instance, and is also efficient in terms of per-node communication and memory. We empirically show that the VR metric also effectively captures the performance of previously suggested efficient aggregation protocols, and that I-LEAG significantly outperforms these protocols in several respects.

The Informed-Source Coding On Demand (ISCOD) approach for efficiently supplying nonidentical data from a central server to multiple caching clients over a broadcast channel is presented. The key idea underlying ISCOD is the joint exploitation of the data blocks already cached by each client, the server's full knowledge of client-cache contents and client requests, and the fact that each client only needs to be able to derive the blocks requested by it rather than all the blocks ever transmitted or even the union of the blocks requested by the different clients. We present two-phase ISCOD algorithms: the server first creates ad-hoc error-correction sets based on its knowledge of client states; next, it uses erasure-correction codes to construct the data for transmission. Each client uses its cached data and the received supplemental data to derive its requested blocks. The result is up to a several-fold reduction in the amount of transmitted supplemental data. Also, we define k-partial cliques in a directed graph and cast ISCOD in terms of partial-clique covers.

The infiniband (IB) system area network (SAN) enables applications to access hardware directly from user level, reducing the overhead of user-kernel crossings during data transfer. However, distributed applications that exhibit close coupling between network and OS services may benefit from accessing IB from the kernel through IB's native verbs interface, which permits tight integration of these services. We assess this approach using a sequential-consistency distributed shared memory (DSM) system as an example. We first develop primitives that abstract the low-level communication and kernel details, and efficiently serve the application's communication, memory, and scheduling needs. Next, we combine the primitives to form a kernel DSM protocol. The approach is evaluated using our full-fledged Linux kernel DSM implementation over infiniband. We show that overheads are reduced substantially, and overall application performance is improved in terms of both absolute execution time and scalability relative to an entirely user level implementation.

This paper addresses the efficient multicast dissemination of bulk data from a single server to numerous clients. The challenge is complex: a client may commence reception at arbitrary times, should receive as little "extra" data as possible until it can reconstruct the entire content, and should have flexibility in choosing the data rate. From the network perspective, the data rate over any link should be as close as possible to the maximum single-downstream-client subscription rate. Also, the solution should scale to huge files and numerous subscribers, and should withstand changing network conditions and packet loss. Finally, it should be friendly to other traffic. For any base client-subscription rate and integer factors thereof, we jointly achieve all these goals in a near-optimal way while using standard ("any k of N") block erasure-correcting codes. Scalability in file size is attained by breaking the file into equisized groups of equisized blocks and separately encoding each group. The other properties are attained by a unique open-loop layered multicast transmission schedule. Each client merely subscribes to one or more standard multicast groups. The need to use special, nonstandard and possibly proprietary codes that scale well is thus obviated.

Bandwidth-optimal open-loop near-video-on-demand streaming (NVOD) entails the optimal assignment of transmission rates to a large number of program segments. These are transmitted concurrently and repetitively at their assigned rates. At any given time in its viewing of the program, a client must record data belonging to a contiguous subsequence of the segments for subsequent display. Limited client recording rates and storage capacity affect the rate assignments. In practice, the concurrent streams must be time-multiplexed onto a single channel, and efficient operation of the client disk drive used to store received data until its viewing prevents fine-grain multiplexing. The bucket-interleaving multiplexing scheme presented in this paper guarantees that each segment is repeated in its entirety within any contiguous time interval of the appropriate length, and reduces the required client "rate-smoothing" RAM buffer by two orders of magnitude relative to pure earliest-deadline-first multiplexing.

Slotted multichannel ALOHA is the access scheme of choice for short messages and for reserving channels for longer ones in many satellite-based networks. This paper proposes schemes for increasing the capacity (maximum attainable throughput) of multichannel slotted ALOHA subject to meeting a user-specified deadline with a (high) required probability, thereby jointly capturing the users' requirements and the system owner's desires. The focus is on short yet multislot messages. A key idea is to achieve a low probability of missing the deadline by permitting a large maximum resource expenditure per message, while holding the mean expenditure low in order to minimize "pollution." For a K-slot message, redundant single-slot fragments are constructed using block erasure-correcting codes, such that any K fragments suffice for message reception. With multiround coding, an optimized number of fragments are transmitted in each round until K are received or the deadline is reached. Even with very strict constraints, capacities that approach the 1/e limit are attained. The coding-reservation scheme raises capacity above 1/e by allowing the hub, upon receipt of any message fragment(s), to grant contention-free slots for the remaining required fragments. Both schemes are also adapted for use with single-transmitter stations at a small performance penalty in most cases. Finally, because capacity is maximized by minimizing the mean per-message transmission resources, the transmission scheme is also energy-efficient.

Redundant traffic dispersal exploits the topological redundancy of networks and improves load balancing by replicating each message or partitioning it into several "data" packets and generating several "redundant" ones; all are then sent over different paths to the destination. The redundancy overcomes the "weakest link" problem, but increases the load. This paper introduces "prioritized dispersal", whereby "redundant" packets receive lower priority than the "data" ones. Moreover, the use of non-FCFS queuing policies for the redundant packets leads to the timely arrival of at least a fraction of them even under heavy load. Queuing-theoretic analysis shows the new schemes to substantially outperform non-prioritized ones in terms of both the blocking probability and that of delay exceeding a specified limit. One possible use of prioritized dispersal, which is discussed in this paper, is to improve the quality of service for best-effort traffic in ATM networks with multiple paths between nodes. Another is in conjunction with ad hoc path trunking. Additional likely uses include parallel access to mirrored data sites and reliable multicast.

This paper shows how to improve the classic multichannel slotted ALOHA protocols by judiciously using redundant transmissions. The focus is on user-oriented requirements: a deadline along with a permissible probability of failing to meet it. Subject to satisfying those, maximization of capacity is the optimization goal. When there is no success/failure feedback prior to the deadline, the use of information dispersal with some redundancy provided by error-correcting codes for the data in conjunction with a replicated, separately transmitted synchronization preamble, is proposed. It is shown to sharply reduce the overhead resulting from the use of shorter packets and to significantly increase the capacity. When the deadline permits several transmission-feedback rounds, we propose a novel replication-based retransmission policy: all attempts except the final one entail the transmission of a single or very few copies, and a larger number of copies are transmitted in the final attempt. This sharply increases channel capacity, even with a single transmitter per station. The proposed approaches are particularly suitable for high-bandwidth satellites with on-board processing.

This paper shows how to improve the classic multi-channel slotted ALOHA protocols by judiciously using redundant transmissions. The focus is on user-oriented requirements: deadlines and a permissible probability of failing to meet them. Subject to those, maximization of throughput is the optimization goal. When there is with no success/failure feedback prior to the deadline, the use of information dispersal with some redundancy provided by error-correcting codes for the data in conjunction with a replicated, separately-transmitted synchronization preamble sharply reduces the overhead resulting from the use of shorter packets and significantly increases the capacity. When the permissible delay is several times greater than the round-trip propagation delay, we propose a novel retransmission policy: all attempts except the final one entail the transmission of a single or very few copies, and the remaining copies are transmitted in the final attempt. This sharply increases channel capacity.

We present the informed source coding on-demand (ISCOD) approach for efficiently supplying non-identical data from a central server to multiple caching clients through a broadcast channel. The key idea underlying ISCOD is the joint exploitation of the data already cached by each client, the server's full awareness of client cache contents and client requests, and the fact that each client only needs to be able to derive the items requested by it rather than all the items ever transmitted or even the union of the items requested by the different clients. We present a set of two-phase ISCOD algorithms. The server uses these algorithms to assemble ad-hoc error correction sets based its knowledge of every client's cache content and of the items requested by it; next, it uses error-correction codes to construct the data that is actually transmitted. Each client uses its cached data and the received supplemental data to derive the items that it has requested. This technique achieves a reduction of up to tens of percents in the amount of data that must be transmitted in order for every client to be able to derive the data requested by it. Finally, we define k-partial cliques in a directed graph, and cast the two phase approach in terms of partial clique covers. As a byproduct of this work, bounds and a close approximation for the expected cardinality of the maximum matching in a random graph have been derived and are outlined.

The most prominent single-hop interconnection (SHI) topology is the single broadcast channel, or bus, which is used in local area networks (LANs) such as Ethernet. The uniform-traffic capacity of switchless, non-bus-oriented, fiber-optic SHIs among N stations, each equipped with a small number of transmitters and receivers, can be as high as /spl Theta/(log/sub 2/N) concurrent transmissions on a single wavelength with round-robin scheduling in a time-slotted system. However, their capacity with the slotted ALOHA access scheme does not increase with N. (The capacity of bus-oriented interconnections, in contrast, varies across time-slotted access schemes by, at most, a factor of e.) This paper quantifies the contribution of several factors to capacity. Merely avoiding destructive interference with ongoing receptions contributes, at most, a factor of e over slotted ALOHA, the same as in bus-oriented interconnections. For an interconnection among two-transmitter, single-receiver stations, whose capacity is log/sub 2/N with global scheduling and 2/e with slotted ALOHA, also avoiding transmissions to blocked receivers increases capacity to, at most, log/sub 2/log/sub 2/N. These results suggest that the added complexity of non-bus-oriented SHIs may be warranted only if they are operated in ways that permit the selection of "good" combinations of (source, destination) pairs for concurrent transmission, and further research should focus on those.

Passive, single-hop interconnections among N stations, each with several transmitters and receivers, provide a communication path between any two stations using one of the transmitters and receivers of each station. Such interconnections which permit a polylogarithmic (in N) number of concurrent transmissions using only spatial separation have previously been described. It is shown how to optimally compose the layouts of any two-fiber-optic single-hop interconnections to form that of the product interconnection. A general method is presented for optimally transforming a layered directed acyclic graph so as to balance the indegree and outdegree of intermediate vertices without altering (source, destination) connectivity.>

A shared directional multichannel (SDM) consists of a set of inputs and a set of outputs to which transmitters and receivers respectively, are connected. A signal placed at any given input reaches a subset of the outputs, and a channel is specified by the sets of outputs that are reachable from each input. A message is received successfully at an output of the channel if and only if it is addressed to the receiver connected to that output and no other signals reach that output at the same time. Constructive lower bounds as well as some upper bounds on the uniform-traffic capacity of SDM-based single-hop interconnections between a set of multitransmitter source stations and a set of multireceiver destination stations are derived. A bidirectional interconnection among a set of stations can be obtained by representing each station as one source station and one destination station. It is shown that with randomized transmissions, SDMs that can be described as a collection of buses can perform as well as any other channels. With deterministic scheduling, however, the use of certain non-bus-oriented SDMs yields a much higher interconnection capacity.>

A rasterizer converts a document described in some page-description language into a sequence of full-page bitmaps (pagemaps), which can then be printed or displayed. The page-parallel rasterizer harnesses multiple processors to work on the same document, thereby permitting cost-effective high-speed rasterization of complex documents. Any given page is processed by a single processor, hence the name. For performance reasons, it is desirable to permit out-of-order rasterization as well as to share memory and computation results among the processors. However, this can result in deadlock. Online algorithms are presented for controlling the rasterizer so as to avoid deadlock without being overly restrictive. It is shown that previously proposed approaches for deadlock avoidance cannot be applied directly due to a special form of nonexclusive allocation of shared resources. A solution is given, thereby extending the applicability of deadlock avoidance. The approach should be useful in a variety of similar situations that may occur in other applications.>

The single-path selective-broadcast interconnection (SBI) is a static, passive interconnection among a set of stations, each equipped with multiple c transmitters and receivers. It uses c/sup 2/ buses, each interconnecting a subset of the stations, and provides a single common bus to any two stations. The author explores those merits of this SBI which are related directly to its implementation in fiber optics. When compared with c buses, each interconnecting all stations, the SBI is shown to offer substantial advantages in power budget and the maximum number of stations that can be interconnected without repeaters or amplifiers. It is also attractive in terms of the required passive fiber optic components such as fiber segments and star couplers. For a fixed power budget and direct detection, the capacity of this SBI is shown to be highest among bus-oriented single-hop interconnections for both a uniform traffic pattern and the worst-case unknown skew.>

The emergence of application programs that take advantage of highly expressive page description languages has sharply increased the amount of computing required for rasterizing an average page, and single-microprocessor rasterizers presently limit the performance of most printers. The pipelined-parallel architecture employs intrapage parallelism to permit the construction of cost-effective multiprocessor rasterizers for computer-driven high-function printers. Initially, blocks of datastream that are independent in terms of datastream environment are identified by a sequential “scanner“. They are then processed in parallel, and each is converted into a multitude of simple, regular objects, which are sorted by “geographical” target on the page into “bins” that correspond to a predetermined partition of the page. Sequencing information is retained. The bins are then processed in parallel (sequentially within each bin) to build the full-page bitmap. The phases are pipelined for increased performance. By breaking rasterization into two main stages and parallelizing along a different dimension in each of them, we are able to attain intrapage parallelism while maintaining correctness, even with non commutative merging modes, such as “overpaint”.

The author presents the topological design space of single-hop interconnection among multitransceiver stations (no intermediate switches and no forwarding). They explore a class of such interconnections for which the throughput with a uniform traffic pattern is proportional to the square of the number of transceivers per station. These interconnections consist of a collection of buses, each of which interconnects a proper subset of the stations, and are referred to as selective-broadcast interconnections. They are compared with a multiple-broadcast-bus interconnection in terms of station hardware, throughput, delay, and power budget.>