Encoding for Degraded broadcast Channels and Resource Allocation for Content Distribution in Peer-to-Peer Networks

The broadcast communication network is a telecommunication network with exactly one source and multiple receivers. This dissertation presents results regarding to two different broadcast communication systems: broadcast channels (BC) and peer-to-peer (P2P) networks. The BC is a single-hop communication network consisting of one transmitter and multiple receivers which observe the transmitted signal through different channels and decode their individual messages. In contrast, the P2P network1 is a multi-hop broadcast or multi-cast communication network consisting of one source node, possibly some relay nodes, and multiple receivers which download transmitted packages through different routings and decode a common message.;This first part of the dissertation explores encoding schemes for degraded broadcast channels (DBC) which are BCs with a sequence of receivers, each receiving a degraded version of the signal received by the previous receiver. We are interested in what we call "natural" encoding for the DBC. A natural encoding (NE) scheme is one in which symbols from independent codebooks, each using the same alphabet, are combined using the same single-letter function that adds distortion to the channel. This dissertation shows that NE schemes achieve the boundary of the capacity region for the multi-user broadcast Z channel, the two-user group-additive DBC, and the two-user discrete multiplicative DBC. This dissertation also defines and studies the input-symmetric DBC and introduces a permutation encoding approach for the input-symmetric DBC and proves its optimality.;In addition, this dissertation provides an explicit expression for the capacity region of the two-user broadcast Z channel. Specifically, the NE scheme for the the two-user broadcast Z channel is to encode the information messages corresponding to each user independently and then transmit the binary OR of these two streams. Nonlinear turbo codes that provide a controlled distribution of ones and zeros are used to demonstrate a low-complexity scheme that works close to the optimal boundary.;Inspired by Witsenhausen and Wyner, we define and explore the conditional entropy bound F* for DBCs. Denote q as the distribution of the channel input X. For any given q, and H(Y|X) ≤ s ≤ H(Y), where H( Y|X) is the conditional entropy of Y given X and H(Y) is the entropy of Y, define the function F*TYX,TZX (q, s) as the infimum of H(Z|U), the conditional entropy of Z given U with respect to all discrete random variables U such that a) H( Y|U) = s, and b) U and Y, Z are conditionally independent given X. This dissertation studies the function F*, its properties and its calculation. This dissertation then represents the capacity region of the DBC X → Y → Z using the function F*TYX,TZX . Finally, this dissertation applies these results to several classes of DBCs and their encoders as discussed above.;The second part of the dissertation investigates the problem of transferring a file from one server to multiple receivers in a peer-to-peer (P2P) network. The objective is to minimize the weighted sum download time (WSDT) for the one-to-many file transfer. Previous work has shown that, given an order at which the receivers finish downloading, the minimum WSDT can be solved in polynomial time by convex optimization, and can be achieved by linear network coding, assuming that node uplinks are the only bottleneck in the network. This dissertation, however, considers heterogeneous peers with both uplink and downlink bandwidth constraints specified. The static scenario is a file-transfer scheme in which the network resource allocation remains static until all receivers finish downloading. This dissertation shows that the static scenario can be optimized in polynomial time by convex optimization, and the associated optimal static WSDT can be achieved by linear network coding. This dissertation also proposes static routing-based and rateless-coding-based schemes that both have almost-optimal empirical performances. The dynamic scenario is a file-transfer scheme which can re-allocate the network resource during the file transfer. This dissertation also proposes a dynamic rateless-coding-based scheme, which provides significantly smaller WSDT than the optimal static scenario does.;1A general P2P network can simultaneously contain multiple multi-cast communications, and hence have more than one source nodes. In this dissertation, we focus on the simplified model of the P2P network which contains only one broadcast or muti-cast communication.