Coding and scheduling in networks for erasures and broadcast

Gummadi, Subha R.

Permalink

https://hdl.handle.net/2142/29831 Copy

Description

Title

Coding and scheduling in networks for erasures and broadcast

Author(s)

Gummadi, Subha R.

Issue Date

2012-02-06T20:20:29Z

Director of Research (if dissertation) or Advisor (if thesis)

Sreenivas, Ramavarapu S.

Doctoral Committee Chair(s)

Sreenivas, Ramavarapu S.

Committee Member(s)

• Chekuri, Chandra S.
• Hajek, Bruce
• Kumar, P.R.
• Milenkovic, Olgica
• Srikant, Rayadurgam

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Erasure Codes
• Wireless Broadcast
• Distributed Storage
• Stochastic Control
• Broadcast Server
• Online Knapsack Problems

Abstract

This dissertation is concerned with the design and analysis of algorithms that address two related issues in communication networks, namely erasures and broadcast. Erasures are an appropriate model for communication channels from a network layer perspective. A class of efficient and flexible codes known as fountain codes, is available to deal with erasures for the basic erasure channel. However, in the network applications that we consider, it remains a challenging problem to design efficient and scalable codes. For an erasure code, the efficiency of encoding and decoding algorithms is distinct from the efficiency of reconstructing erased code symbols from other code symbols, which is of importance in storage applications. In our work, we propose new codes together with algorithms to efficiently repair lost code symbols, simultaneously with low encoding and decoding complexities. Our work on codes for storage also leads us to systematic fountain codes with improved complexity. We also study the design and analysis of degree distributions for fountain codes when the receivers have side information, and we provide upper and lower bounds on the overhead. In a network with multiple hops from the source, we construct a code to import the one-hop traits of LT codes end-to-end using an idea based on online encoding, which is also one of the components of the repair algorithm for storage codes that we propose. We then consider wireless erasure networks, where local broadcast is another property which influences the role of coding beyond that of merely dealing with erasures. We show that feedback signaling is a critical factor that defines the role of coding in this situation, in the sense that it is one way to avoid the extensive feedback signaling that is necessary for routing policies. To characterize this more precisely, we consider a formal notion of restricted feedback signaling and derive the throughput of routing policies with restricted feedback on a two-hop network. This allows us to obtain a lower bound on the throughput when the losses are independent, and also to show that it is possible to have arbitrary degradation of throughput with dependent losses. Finally, we consider optimization problems involving the control of a queue whose server is defined by the broadcast property, where each service satisfies all the customers simultaneously. Customers in the queue incur holding costs. We consider two constraints on the server and derive the associated optimal controls. For the first constraint, a constant non-negative cost is charged per service whereas in the second type, we consider an online running constraint on the ability to operate the broadcast server. To address this, we solve a more general problem called the online knapsack problem where one needs to choose a sequence of actions over time, with each action incurring a stochastic cost and also consuming a resource, which is replenished stochastically over time with a given rate. The objective is to minimize the total cost subject to the constraint of not exhausting the resource at any point. We derive a limiting characterization of the optimal policy by showing the convergence of the scaled value function to that of a continuous time problem when the discount factor vanishes. In other words, this provides a method to approximate such problems when the discount factor is effective over a long duration and consequently, the magnitude of transactions in each time slot vanishes in comparison to the long-term utility.

Graduation Semester

2011-12

Permalink

http://hdl.handle.net/2142/29831

Copyright and License Information

Copyright 2011 Subha R. Gummadi

Owning Collections