Combinatorial approaches to scalability problems in storage, networking, and communications
Abstract/Contents
- Abstract
- As computing systems have grown larger and more interconnected, every single layer in the underlying technologies has had to scale correspondingly in order to continue to support these systems. In this dissertation, we take a critical look at the scaling challenges in the storage, networking, and communications layers, by considering the combinatorial aspects of existing approaches. By recognizing the need for understanding the combinatorics of these problems, we are then able to provide efficient solutions that perform well even as problem domains get significantly larger. In the first part of this dissertation, we present a systematic method for designing storage systems where node repair is efficient even as the system scales to large numbers of nodes. In this scheme, data chunk replication is used to guarantee storage reliability. By distributing data chunks and their replicas through the storage system according to a Steiner system design, node repair can be heavily parallelized, thus resulting in higher data availability. We show that the design of such storage systems can be extended to scenarios where node sizes are much larger than replication degrees. Via these constructions, which are based on bipartite cage graphs and mutually orthogonal Latin squares, the resulting designs are guaranteed to require the fewest number of storage nodes for the given parameters. Furthermore, the scheme is scalable, since these storage systems can be easily expanded without need for frequent reconfiguration. In the second part of this dissertation, we focus on the class of network coding problems known as the non-uniform demand problem, and show how network codes for these problems can be efficiently constructed even as the networks become larger. The non-uniform demand network coding problem is a single-source, multiple-sink network transmission problem where the sinks may have heterogeneous demands, and is generally an NP-complete problem. In this work, we present non-uniform network demand scenarios under which network coding solutions can be found in polynomial time. This is accomplished by relating the demand problem with the graph coloring problem and then applying results from the strong perfect graph theorem. In the third part of this dissertation, we consider an interference alignment scheme in an ergodic setting. Here, interference alignment is achieved by pairing complementary channel realizations in order to amplify signals and cancel interference. Unfortunately, such a scheme is prone to large delays in decoding message symbols when there are many users. Thus in this work we take an in-depth look at the causes of such delays and propose better schemes that mitigate these issues. We show that delay can be mitigated by using outputs from potentially more than two channel realizations, at the possible cost of reduced data rate. We further demonstrate the tradeoff between rate and delay via a timesharing strategy.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Koo, Joseph Clarence |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Gill, John T III |
| Thesis advisor | Gill, John T III |
| Thesis advisor | Boyd, Stephen P |
| Thesis advisor | Saberi, Amin |
| Advisor | Boyd, Stephen P |
| Advisor | Saberi, Amin |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Joseph Clarence Koo. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph. D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Joseph Clarence Koo
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...