On erasure coding for distributed storage and streaming communications

The work presented in this thesis revolves around erasure correction coding, as applied to distributed data storage and real-time streaming communications.

First, we examine the problem of allocating a given storage budget over a set of nodes for maximum reliability. The objective is to find an allocation of the budget that maximizes the probability of successful recovery by a data collector accessing a random subset of the nodes. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models, and determine the optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) for a variety of cases. Although the optimal allocation can have nonintuitive structure and can be difficult to find in general, our results suggest that, as a simple heuristic, reliable storage can be achieved by spreading the budget maximally over all nodes when the budget is large, and spreading it minimally over a few nodes when it is small. Coding would therefore be beneficial in the former case, while uncoded replication would suffice in the latter case.

Second, we study how distributed storage allocations affect the recovery delay in a mobile setting. Specifically, two recovery delay optimization problems are considered for a network of mobile storage nodes: the maximization of the probability of successful recovery by a given deadline, and the minimization of the expected recovery delay. We show that the first problem is closely related to the earlier allocation problem, and solve the second problem completely for the case of symmetric allocations. It turns out that the optimal allocations for the two problems can be quite different. In a simulation study, we evaluated the performance of a simple data dissemination and storage protocol for mobile delay-tolerant networks, and observed that the choice of allocation can have a significant impact on the recovery delay under a variety of scenarios.

Third, we consider a real-time streaming system where messages created at regular time intervals at a source are encoded for transmission to a receiver over a packet erasure link; the receiver must subsequently decode each message within a given delay from its creation time. For erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts whose maximum length is sufficiently short or long, we show that a time-invariant intrasession code asymptotically achieves the maximum message size among all codes that allow decoding under all admissible erasure patterns. For the bursty erasure model, we also show that diagonally interleaved codes derived from specific systematic block codes are asymptotically optimal over all codes in certain cases. We also study an i.i.d. erasure model in which each transmitted packet is erased independently with the same probability; the objective is to maximize the decoding probability for a given message size. We derive an upper bound on the decoding probability for any time-invariant code, and show that the gap between this bound and the performance of a family of time-invariant intrasession codes is small when the message size and packet erasure probability are small. In a simulation study, these codes performed well against a family of random time-invariant convolutional codes under a number of scenarios.

Finally, we consider the joint problems of routing and caching for named data networking. We propose a backpressure-based policy that employs virtual interest packets to make routing and caching decisions. In a packet-level simulation, the proposed policy outperformed a basic protocol that combines shortest-path routing with least-recently-used (LRU) cache replacement.

The streaming of 1.3-2.3 MeV cosmic-ray protons during periods between prompt solar particle events

The anisotropy of 1.3 - 2.3 MeV protons in interplanetary space has been measured using the Caltech Electron/Isotope Spectrometer aboard IMP-7 for 317 6-hour periods from 72/273 to 74/2. Periods dominated by prompt solar particle events are not included. The convective and diffusive anisotropies are determined from the observed anisotropy using concurrent solar wind speed measurements and observed energy spectra. The diffusive flow of particles is found to be typically toward the sun, indicating a positive radial gradient in the particle density. This anisotropy is inconsistent with previously proposed sources of low-energy proton increases seen at 1 AU which involve continual solar acceleration.

The typical properties of this new component of low-energy cosmic rays have been determine d for this period which is near solar minimum. The particles have a median intensity of 0.06 protons/ cm^(2)-sec-sr-MeV and a mean spectral index of -3.15.The amplitude of the diffusive anisotropy is approximately proportional to the solar wind speed. The rate at which particles are diffusing toward the sun is larger than the rate at which the solar wind is convecting the particles away from the sun. The 20 to 1 proton to alpha ratio typical of this new component has been reported by Mewaldt, et al. (1975b).

A propagation model with κ_(rr) assumed independent of radius and energy is used to show that the anisotropy could be due to increases similar to those found by McDonald, et al. (1975) at ~3 AU. The interplanetary Fermi-acceleration model proposed by Fisk (1976) to explain the increases seen near 3 AU is not consistent with the ~12 per cent diffusive anisotropy found.

The dependence of the diffusive anisotropy on various parameters is shown. A strong dependence of the direction of the diffusive anisotropy on the concurrently measured magnetic field direction is found, indicating a κ_⊥ less than κ_∥ to be typical for this large data set.

Generalizations and extensions of the Fokker-Planck-Kolmogorov equations

The problem of determining probability density functions of general transformations of random processes is considered in this thesis. A method of solution is developed in which partial differential equations satisfied by the unknown density function are derived. These partial differential equations are interpreted as generalized forms of the classical Fokker-Planck-Kolmogorov equations and are shown to imply the classical equations for certain classes of Markov processes. Extensions of the generalized equations which overcome degeneracy occurring in the steady-state case are also obtained.

The equations of Darling and Siegert are derived as special cases of the generalized equations thereby providing unity to two previously existing theories. A technique for treating non-Markov processes by studying closely related Markov processes is proposed and is seen to yield the Darling and Siegert equations directly from the classical Fokker-Planck-Kolmogorov equations.

As illustrations of their applicability, the generalized Fokker-Planck-Kolmogorov equations are presented for certain joint probability density functions associated with the linear filter. These equations are solved for the density of the output of an arbitrary linear filter excited by Markov Gaussian noise and for the density of the output of an RC filter excited by the Poisson square wave. This latter density is also found by using the extensions of the generalized equations mentioned above. Finally, some new approaches for finding the output probability density function of an RC filter-limiter-RC filter system driven by white Gaussian noise are included. The results in this case exhibit the data required for complete solution and clearly illustrate some of the mathematical difficulties inherent to the use of the generalized equations.

A programmable SIMD vision chip for real-time vision applications

A programmable vision chip for real-time vision applications is presented. The chip architecture is a combination of a SIMD processing element array and row-parallel processors, which can perform pixel-parallel and row-parallel operations at high speed. It implements the mathematical morphology method to carry out low-level and mid-level image processing and sends out image features for high-level image processing without I/O bottleneck. The chip can perform many algorithms through software control. The simulated maximum frequency of the vision chip is 300 MHz with 16 x 16 pixels resolution. It achieves the rate of 1000 frames per second in real-time vision. A prototype chip with a 16 x 16 PE array is fabricated by the 0.18 mu m standard CMOS process. It has a pixel size of 30 mu m x 40 mu m and 8.72 mW power consumption with a 1.8 V power supply. Experiments including the mathematical morphology method and target tracking application demonstrated that the chip is fully functional and can be applied in real-time vision applications.

Extensions of a Theory of Networks for Approximation and Learning: Outliers and Negative Examples

Learning an input-output mapping from a set of examples can be regarded as synthesizing an approximation of a multi-dimensional function. From this point of view, this form of learning is closely related to regularization theory. In this note, we extend the theory by introducing ways of dealing with two aspects of learning: learning in the presence of unreliable examples and learning from positive and negative examples. The first extension corresponds to dealing with outliers among the sparse data. The second one corresponds to exploiting information about points or regions in the range of the function that are forbidden.

Some Extensions of the K-Means Algorithm for Image Segmentation and Pattern Classification

In this paper we present some extensions to the k-means algorithm for vector quantization that permit its efficient use in image segmentation and pattern classification tasks. It is shown that by introducing state variables that correspond to certain statistics of the dynamic behavior of the algorithm, it is possible to find the representative centers fo the lower dimensional maniforlds that define the boundaries between classes, for clouds of multi-dimensional, mult-class data; this permits one, for example, to find class boundaries directly from sparse data (e.g., in image segmentation tasks) or to efficiently place centers for pattern classification (e.g., with local Gaussian classifiers). The same state variables can be used to define algorithms for determining adaptively the optimal number of centers for clouds of data with space-varying density. Some examples of the applicatin of these extensions are also given.

Rough sets, their extensions and applications

Q. Shen and R. Jensen, 'Rough sets, their extensions and applications,' International Journal of Automation and Computing (IJAC), vol. 4, no. 3, pp. 217-218, 2007.

Customers' responses to retail brand extensions

Alexander, N.; and Colgate, N. (2005). Customers' responses to retail brand extensions. Journal of Marketing Management. 21(3-4), pp.393-419 RAE2008

Constructing extensions of CP-maps via tensor dilations with rhe help of von Neumann modules

Gohm, Rolf; Skeide, M., (2005) 'Constructing extensions of CP-maps via tensor dilations with rhe help of von Neumann modules', Infinite Dimensional Analysis, Quantum Probability and Related Topics 8(2) pp.291-305 RAE2008

Dynamic Window-Constrained Scheduling for Real-Time Media Streaming

This paper describes an algorithm for scheduling packets in real-time multimedia data streams. Common to these classes of data streams are service constraints in terms of bandwidth and delay. However, it is typical for real-time multimedia streams to tolerate bounded delay variations and, in some cases, finite losses of packets. We have therefore developed a scheduling algorithm that assumes streams have window-constraints on groups of consecutive packet deadlines. A window-constraint defines the number of packet deadlines that can be missed in a window of deadlines for consecutive packets in a stream. Our algorithm, called Dynamic Window-Constrained Scheduling (DWCS), attempts to guarantee no more than x out of a window of y deadlines are missed for consecutive packets in real-time and multimedia streams. Using DWCS, the delay of service to real-time streams is bounded even when the scheduler is overloaded. Moreover, DWCS is capable of ensuring independent delay bounds on streams, while at the same time guaranteeing minimum bandwidth utilizations over tunable and finite windows of time. We show the conditions under which the total demand for link bandwidth by a set of real-time (i.e., window-constrained) streams can exceed 100% and still ensure all window-constraints are met. In fact, we show how it is possible to guarantee worst-case per-stream bandwidth and delay constraints while utilizing all available link capacity. Finally, we show how best-effort packets can be serviced with fast response time, in the presence of window-constrained traffic.