Search

The supermarket model refers to a system with a large number of queues, where new customers choose $d$ d queues at random and join the one with the fewest customers. This model demonstrates the power of even small amounts of choice, as compared to simply joining a queue chosen uniformly at random, for load balancing systems. In this work we perform simulation-based studies to consider variations where service times for a customer are predicted, as might be done in modern settings using machine learning techniques or related mechanisms. Our primary takeaway is that using even seemingly weak predictions of service times can yield significant benefits over blind First In First Out queueing in this context. However, some care must be taken when using predicted service time information to both choose a queue and order elements for service within a queue; while in many cases using the information for both choosing and ordering is beneficial, in many of our simulation settings we find that simply using the number of jobs to choose a queue is better when using predicted service times to order jobs in a queue. In our simulations, we evaluate both synthetic and real-world workloads–in the latter, service times are predicted by machine learning. Our results provide practical guidance for the design of real-world systems; moreover, we leave many natural theoretical open questions for future work, validating their relevance to real-world situations. [ABSTRACT FROM AUTHOR]

An important function in modern routers and switches is to perform a lookup for a key. Hash-based methods, and in particular cuckoo hash tables, are popular for such lookup operations, but for large structures stored in off-chip memory, such methods have the downside that they may require more than one off-chip memory access to perform the key lookup. Although the number of off-chip memory accesses can be reduced using on-chip approximate membership structures such as Bloom filters, some lookups may still require more than one off-chip memory access. This can be problematic for some hardware implementations, as having only a single off-chip memory access enables a predictable processing of lookups and avoids the need to queue pending requests. We provide a data structure for hash-based lookups based on cuckoo hashing that uses only one off-chip memory access per lookup, by utilizing an on-chip pre-filter to determine which of multiple locations holds a key. We make particular use of the flexibility to move elements within a cuckoo hash table to ensure the pre-filter always gives the correct response. While this requires a slightly more complex insertion procedure and some additional memory accesses during insertions, it is suitable for most packet processing applications where key lookups are much more frequent than insertions. An important feature of our approach is its simplicity. Our approach is based on simple logic that can be easily implemented in hardware, and hardware implementations would benefit most from the single off-chip memory access per lookup. [ABSTRACT FROM AUTHOR]

In many applications, there is a need to identify to which of a group of sets an element $x$ belongs, if any. For example, in a router, this functionality can be used to determine the next hop of an incoming packet. This problem is generally known as set separation and has been widely studied. Most existing solutions make use of hash-based algorithms, particularly when a small percentage of false positives is allowed. A known approach is to use a collection of Bloom filters in parallel. Such schemes can require several memory accesses, a significant limitation for some implementations. We propose an approach using Block Bloom Filters, where each element is first hashed to a single memory block that stores a small Bloom filter that tracks the element and the set or sets the element belongs to. In a naïve solution, when an element $x$ in a set $S$ is stored, it necessarily increases the false positive probability for finding that $x$ is in another set $T$. In this paper, we introduce our One Memory Access Set Separation (OMASS) scheme to avoid this problem. OMASS is designed so that for a given element $x$, the corresponding Bloom filter bits for each set map to different positions in the memory word. This ensures that the false positive rates for the Bloom filters for element $x$ under other sets are not affected. In addition, OMASS requires fewer hash functions compared to the naïve solution. [ABSTRACT FROM PUBLISHER]

In a standard multiple-choice hashing scheme, each item is stored in one of d\geq 2 hash table buckets. The availability of choice in where items are stored improves space utilization. These schemes are often very amenable to a hardware implementation, such as in a router. Recently, researchers have discovered powerful variants where items already in the hash table may be moved during the insertion of a new item. Unfortunately, these schemes occasionally require a large number of items to be moved to perform an insertion, making them inappropriate for a hardware implementation. We show that it is possible to significantly increase the space utilization of multiple-choice hashing schemes by allowing at most one item to be moved during an insertion. Furthermore, our schemes can be effectively analyzed, optimized, and compared using numerical methods based on fluid limit arguments, without resorting to much slower simulations. [ABSTRACT FROM PUBLISHER]

Floating codes are codes designed to store multiple values in a Write Asymmetric Memory, with applications to flash memory. In this model, a memory consists of a block of n cells, with each cell in one of q states {(), 1,..., q -- 1}. The cells are used to represent k variable values from an l-ary alphabet. Cells can move from lower values to higher values easily, but moving any cell from a higher value to a lower value requires first resetting the entire block to an all 0 state. Reset operations are to be avoided; generally a block can only experience a large but finite number of resets before wearing out entirely. A code here corresponds to a mapping from cell states to variable values, and a transition function that gives how to rewrite cell states when a variable is changed. Previous work has focused on developing codes that maximize the worst-case number of variable changes, or equivalently cell rewrites, that can be experienced before resetting. In this paper, we introduce the problem of maximizing the expected number of variable changes before resetting, given an underlying Markov chain that models variable changes. We demonstrate that codes designed for expected performance can differ substantially from optimal worst-case codes, and suggest constructions for some simple cases. We then study the related question of the performance of random codes, again focusing on the issue of expected behavior. [ABSTRACT FROM AUTHOR]

We consider deletion channels and insertion channels under an additional segmentation assumption: the input consists of disjoint segments of b consecutive bits, with at most one error per segment. Under this assumption, we demonstrate simple and computationally efficient deterministic encoding and decoding schemes that achieve a high provable rate even under worst case errors. We also consider more complex schemes that experimentally achieve higher rates under random error. [ABSTRACT FROM AUTHOR]

In a multiple-choice hashing scheme, each item is stored in one of d ≥ 2 possible hash table buckets. The availability of these multiple choices allows for a substantial reduction in the maximum load of the buckets. However, a lookup may now require examining each of the d locations. For applications where this cost is undesirable, Song et al. propose keeping a summary that allows one to determine which of the d locations is appropriate for each item, where the summary may allow false positives for items not in hash table. We propose alternative, simple constructions of such summaries that use less space for both the summary and the underlying hash table. Moreover, our constructions are easily analyzable and tunable. [ABSTRACT FROM AUTHOR]

The capacity of sticky channels, a subclass of insertion channels where each symbol may be duplicated multiple times, is considered. The primary result is to provide nearly tight numerical upper and lower bounds for the independent and identically distributed (i.i.d.) duplication channel. [ABSTRACT FROM AUTHOR]

This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability d. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capacity by utilizing a stronger definition of a typical output from the channel. The new results give the best known provable bounds on the capacity for all values of d. Moreover, the techniques presented here extend to yield lower bounds for channels with certain types of random insertions, namely, duplications, or combinations of duplications and deletions. To demonstrate these techniques in this context, two binary channels are analyzed: a channel where each transmitted bit is copied with probability v and a channel where each transmitted bit is copied a geometrically distributed number of times. [ABSTRACT FROM AUTHOR]

We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes n symbols from a q-ary alphabet, and each symbol is deleted independently with probability p. Taking advantage of recent improvements on the results of Luby and Mitzenmacher for verification-based decoding by Shokrollahi and Wang, we show how to design for any ϵ > 0 and sufficiently large n and q deletion codes with the following properties: the rate is (1 - p)(1 - ϵ), the failure probability is nO(1/ϵ2)/q, and the computational complexity for encoding and decoding is nO(1/ϵ2) log q. We also extend these schemes to obtain the same results even if the undeleted symbols are also transposed arbitrarily, and if a sufficiently small number of random symbols are inserted. [ABSTRACT FROM AUTHOR]

We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability d, is at least (1 - d)/9, by developing a correspondence between the deletion channel and an insertion/deletion channel that we call a Poisson-repeat channel. [ABSTRACT FROM AUTHOR]

This correspondence considers binary deletion channels, where bits are deleted independently with probability d; it improves upon the framework used to analyze the capacity of binary deletion channels established by Diggavi and Grossglauser, improving on their lower bounds. Diggavi and Grossglauser considered codebooks with codewords generated by a first-order Markov chain. They only consider typical outputs, where an output is typical if an N bit input gives an N(1 - ϵd) bit output. The improvements in this correspondence arise from two considerations. First, a stronger notion of a typical output from the channel is used, which yields better bounds even for the codebooks studied by Diggavi and Grossglauser. Second, codewords generated by more general processes than first-order Markov chains are considered. [ABSTRACT FROM AUTHOR]

Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with TCP-friendliness equations over large time scales. In this paper, we quantify the costs and benefits of using noncumulative layering and present a new, scalable multicast congestion control scheme called STAIR that embodies this approach. Our first main contribution is a set of performance criteria on which we base a comparative evaluation of layered multicast schemes. In contrast to the conventional wisdom, we demonstrate that fine-grained rate adjustment can be achieved with only modest increases in the number of layers, aggregate bandwidth consumption and control traffic. The STAIR protocol that we subsequently define and evaluate is a multiple rate congestion control scheme that provides a fine-grained approximation to the behavior of TCP additive increase/multiplicative decrease (AIMD) on a per-receiver basis. [ABSTRACT FROM AUTHOR]

Evaluates the applications and the role of X-compact in the elimination of the bane of compression and logic Built-In Self-Test techniques. Reduction of test response data volume by up to three orders of magnitude; Impact of X-compact on test quality; Elimination of all X-sources due to timing constraints.

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary. [ABSTRACT FROM AUTHOR]

Overlay networks have emerged as a powerful and highly flexible method for delivering content. We study how to optimize throughput of large transfers across richly connected, adaptive overlay networks, focusing on the potential of collaborative transfers between peers to supplement ongoing downloads. First, we make the case for an erasure-resilient encoding of the content. Using the digital fountain encoding approach, end hosts can efficiently reconstruct the original content of size n from a subset of any n symbols drawn from a large universe of encoding symbols. Such an approach affords reliability and a substantial degree of application-level flexibility, as it seamlessly accommodates connection migration and parallel transfers while providing resilience to packet loss. However, since the sets of encoding symbols acquired by peers during downloads may overlap substantially, care must be taken to enable them to collaborate effectively. Our main contribution is a collection of useful algorithmic tools for efficient summarization and approximate reconciliation of sets of symbols between pairs of collaborating peers, all of which keep message complexity and computation to a minimum. Through simulations and experiments on a prototype implementation, we demonstrate the performance benefits of our informed content-delivery mechanisms and how they complement existing overlay network architectures. [ABSTRACT FROM AUTHOR]

An early result in the history of power laws, due to Miller, concerned the following experiment. A monkey types randomly on a keyboard with N letters (N > 1) and a space bar, where a space separates words. A space is hit with probability p; all other letters are hit with equal probability (1 - p) /N. Miller proved that in this experiment, the rank-frequency distribution of words follows a power law. The case where letters are hit with unequal probability has been the subject of recent confusion, with some suggesting that hi this case the rank-frequency distribution follows a lognormal distribution. We prove that the rank-frequency distribution follows a power law for assignments of probabilities that have rational log-ratios for any pair of keys, and we present an argument of Montgomery that settles the remaining cases, also yielding a power law. The key to both arguments is the use of complex analysis. The method of proof produces simple explicit formulas for the coefficient in the power law in cases with rational log-ratios for the assigned probabilities of keys. Our formula in these cases suggests an exact asymptotic formula in the cases with an irrational log- ratio, and this formula is exactly what was proved by Montgomery. [ABSTRACT FROM AUTHOR]

We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if C[sub i.i.d], denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables (C[sub i.i.d.] ≤ C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by C[sub i.i.d.]. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder. [ABSTRACT FROM AUTHOR]

Describes fair layered increase/decrease with dynamic layering (FLID-DL), a new multirate congestion control algorithm for layered multicast sessions. Features of the congestion control algorithm; Key contribution that enables FLID-DL; Motive for using DL.

Describes an ideal, fully scalable protocol for digital fountain, which allows any number of heterogeneous receivers to acquire content with optimal efficiency. Motivator of the design of new multicast and broadcast protocols; Need for multicast or broadcast transmissions to be reliable; Problem with solutions based on adaptive retransmission.

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Although Bloom filters allow false positives, for many applications the space savings outweigh this drawback when the probability of an error is sufficiently low. We introduce compressed Bloom filters, which improve performance when the Bloom filter is passed as a message, and its transmission size is a limiting factor. For example, Bloom filters have been suggested as a means for sharing Web cache information. In this setting, proxies do not share the exact contents of their caches, but instead periodically broadcast Bloom filters representing their caches. By using compressed Bloom filters, proxies can reduce the number of bits broadcast, the false positive probability, and/or the amount of computation per lookup. The cost is the processing time for compression and decompression, which can use simple arithmetic coding, and more memory use at the proxies, which utilize the larger uncompressed form of the Bloom filter. [ABSTRACT FROM AUTHOR]

Focuses on the development of dynamic load balancing model for customer care services. Service of customers based on a first-in-first-out system; Approximation on the behavior of finite systems; Discussion on the possible implication for system design.

Presents a low-density parity-check codes based on irregular graphs and introduces methods for analyzing low-density parity-check codes using concentration bounds based on martingales. Analyzing message passage coding; Results for Gallager's algorithm; Low-density parity-check codes and belief propagation.

Examines the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. Multiprocessor system where incoming tasks with exponentially distributed service requirements arrive as a Poisson process; Description of behavior of sufficiently large systems.

We show that the following simple compression problem is NP-hard: given a collection of documents, find the pair of Huffman dictionaries that minimizes the total compressed size of the collection, where the best dictionary from the pair is used to compress each document. We also show the NP-hardness of finding optimal multiple preset dictionaries for LZ'77-based compression schemes. Our reductions make use of the catalog segmentation problem, a natural partitioning problem. Our results justify heuristic attacks used in practice. [ABSTRACT FROM AUTHOR]