Network coding for application layer multicast

Today's Internet uses routing to deliver messages from end to end. Network coding is a generalization of routing which allows relay nodes to encode messages in addition to duplicating and forwarding messages. It is proved that network coding can achieve multicast capacity and therefore improve the throughput of a multicast network significantly. Application layer multicast (ALM) is a perfect candidate to apply network coding due to two reasons: first, ALM is built on peer-to-peer networks whose topology can be arbitrary so it is easy to tailor the topology to facilitate network coding second, the nodes in ALM are end hosts which are powerful enough to perform complex encoding and decoding operations.This thesis presents the following contributions to the theory and practice of network coding and its application to ALM. First, we propose a general approach to apply linear network coding to multicast networks. We investigate a series of minimal network coding problems and propose a systematic approach to solve them under a unified framework. Then we apply linear network coding to the peer-to-peer file sharing system and the peer-to-peer media streaming system respectively. These two systems have different features and requirements. For the peer-to-peer file sharing system, we focus on the throughput and reliability. The overlay topology is constructed in such a way that it can be looked as a union of multiple combination networks. We propose a general linear network coding scheme for combination networks and adapt it to the peer-to-peer file sharing system. The simulation shows great improvement in both throughput and reliability compared to other systems without network coding. For the peer-to-peer media streaming system, we focus on the heterogeneity and bandwidth utilization of the access links of peers. We adopt the network model that the bandwidth bottleneck lies only at the edge of the network. The media content is encoded into multiple stripes through Multiple Description Coding (MDC). Peers subscribes to the stripes based on their download bandwidths. Random linear network coding is performed within the same stripe. By combining MDC and network coding, peers achieve much higher satisfaction in terms of received downloading rate. Besides, we investigate the inter-session linear network coding problem between multiple simultaneous multicast sessions. Two metrics are introduced to evaluate the network coding benefit based on which we propose a practical inter-session network coding scheme for multicast networks. The system throughput is increased by about 30% in terms of throughput in most cases when compared to intra-session network coding.