Network coding is a promising enhancement of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. Peer-to-peer networks are a perfect place to apply network coding due to two reasons: the topology of a peer-to-peer network is constructed arbitrarily, thus it is easy to tailor the topology to facilitate network coding; the nodes in a peer-to-peer network are end hosts which can perform more complex operations such as decoding and encoding than simply storing and forwarding messages. In this paper, we propose a scheme to apply network coding to peer-to-peer file sharing which employs a peer-to-peer network to distribute files resided in a web server or a file server. The scheme exploits a special type of network topology called combination network. It was proved that combination networks can achieve unbounded network coding gain measured by the ratio of network throughput with network coding to that without network coding. Our scheme encodes a file into multiple messages and divides peers into multiple groups with each group responsible for relaying one of the messages. The encoding scheme is designed to satisfy the property that any subset of the messages can be used to decode the original file as long as the size of the subset is sufficiently large. To meet this requirement, we first define a deterministic linear network coding scheme which satisfies the desired property, then we connect peers in the same group to flood the corresponding message, and connect peers in different groups to distribute messages for decoding. Moreover, the scheme can be readily extended to support link heterogeneity and topology awareness to further improve system performance in terms of throughput, reliability and link stress. Our simulation results show that the new scheme can achieve 15%–20% higher throughput than another peer-to-peer multicast system, Narada, which does not employ network coding. In addition, it achieves good reliability and robustness to link failure or churn.

Media streaming is an important Internet application and has received more and more attention in recent years. Traditional media streaming systems are deployed in a server-client mode which scales poorly with the increasing population of the clients. Peer-to-peer media streaming can greatly enhance the scalability of the system by employing the clients to help forward the media content. In this paper, we consider optimizing the overlay construction for peer-to-peer streaming systems with heterogeneous access link bandwidths. Our goal is to maximize the total downloading rate and satisfy the heterogeneous downloading requirements when the uplink bandwidth is limited. We first formalize it into a problem of finding maximum number of edge disjoint trees in a graph which models the peers and their access link bandwidths. Then we give a centralized heuristic algorithm to solve the problem. Based on the centralized algorithm, we further propose a distributed algorithm which constructs an adaptive overlay topology that can adapt itself to the changing peers such that the end-to-end delay and link stress are minimized. We compare our scheme with another recently proposed scheme called MDM through simulations. Our simulation results show that the proposed scheme outperforms MDM by about 30% with respect to the average peer satisfaction. In addition, the proposed scheme achieves less link stress than MDM.

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected by a regular topology, and unstructured peer-to-peer networks in which the topology is arbitrary. Structured peer-to-peer networks usually can provide efficient and accurate services but need to spend a lot of effort in maintaining the regular topology. On the other hand, unstructured peer-to-peer networks are extremely resilient to the frequent peer joining and leaving but this is usually achieved at the expense of efficiency. The objective of this work is to design a hybrid peer-to-peer system for distributed data sharing which combines the advantages of both types of peer-to-peer networks and minimizes their disadvantages. The proposed hybrid peer-to-peer system is composed of two parts: the first part is a structured core network which forms the backbone of the hybrid system; the second part is made of multiple unstructured peer-to-peer networks each of which is attached to a node in the core network. The core structured network can narrow down the data lookup within a certain unstructured network accurately, while the unstructured networks provide a low-cost mechanism for peers to join or leave the system freely. A data lookup operation first checks the local unstructured network, and then, the structured network. This two-tier hierarchy can decouple the flexibility of the system from the efficiency of the system. Our simulation results demonstrate that the hybrid peer-to-peer system can utilize both the efficiency of structured peer-to-peer network and the flexibility of the unstructured peer-to-peer network and achieve a good balance between the two types of networks.

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. A typical scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose an approach to transforming the linear coding problem into a graph theory problem. By utilizing hypergraphs, we model the linear codes by constructing a pseudodual graph of the multicast network. Then, a valid linear code is equivalent to a cover in the pseudodual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, we propose several preprocessing algorithms to further reduce the computation time required by the iterative refinements by reducing the graph size before transformation. An important contribution of this work is that the proposed approach can be readily extended to solve many minimal network coding problems. By assigning different weights to edges, minimal network coding problems are reduced to the shortest path problem in the pseudodual graph. Our simulation results show that the proposed preprocessing algorithms can reduce the computation time by about 40-50 percent in a medium size multicast network compared to the scheme without preprocessing algorithms, and the throughput of the system with network coding is 25 percent higher than that with the traditional approach of multiple multicast trees.

In this paper, we propose a scheme to apply network coding to heterogeneous peer-to-peer media streaming systems. As most peers in a peer-to-peer media streaming system are individual computers connected to the Internet through access links with heterogeneous link capacities, it is desirable to design an adaptive scheme to make efficient use of the bandwidth of the access links. We propose an adaptive network coding scheme for heterogeneous peer-to-peer streaming systems. The media content is encoded into multiple stripes. The peers select one or more stripes to subscribe based on their own download bandwidths. For each stripe, a subgraph is constructed such that the coding probability is maximized. In addition, we propose an overlay topology construction algorithm which takes both upload bandwidth and download bandwidth into consideration. We compare our scheme with another recently proposed scheme called LION through simulations. Our simulation results show that the proposed scheme achieves higher satisfaction and better throughput than LION with or without churn.

Network coding is a promising enhancement of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. Peer-to-peer networks are a perfect place to apply network coding due to two reasons: the topology of a peer-to-peer network is constructed arbitrarily, thus it is easy to tailor the topology to facilitate network coding; the nodes in a peer-to-peer network are end hosts which can perform more complex operations such as decoding and encoding than simply storing and forwarding messages. In this paper, we propose a scheme to apply network coding to peer-to-peer file sharing which employs a peer-to-peer network to distribute files resided in a web server or a file server. The scheme exploits a special type of network topology called combination network. It is proved that combination networks can achieve unbounded network coding gain measured by the ratio of network throughput with network coding to that without network coding. The scheme encodes a file into multiple messages and divides peers into multiple groups with each group responsible for relaying one of the messages. The encoding scheme is designed to satisfy the property that any subset of the messages can be used to decode the original file as long as the size of the subset is sufficiently large. To meet this requirement, we first define a deterministic linear network coding scheme which satisfies the desired property, then we connect peers in the same group to flood the corresponding message, and connect peers in different groups to distribute messages for decoding. Moreover, the scheme can be readily extended to support topology awareness to further improve system performance in terms of throughput, reliability and link stress. Our simulation results show that the new scheme can achieve 15%-20% higher throughput than Narada which does not employ network coding. In addition, it achieves good reliability and robustness to link failure or churn.

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer- to-peer networks in which peers are connected by a regular topology, and unstructured peer-to-peer networks in which the topology is arbitrary. Structured peer-to-peer networks usually can provide efficient and accurate services but need to spend a lot of efforts in maintaining the regular topology. On the other hand, unstructured peer-to-peer networks are extremely resilient to the frequent peer joining and leaving but this is usually achieved at the expense of efficiency. The objective of this work is to design a hybrid peer-to-peer system for distributed data sharing which combines the advantages of both types of peer-to-peer networks and minimizes their disadvantages. The proposed hybrid peer-to-peer system is composed of two parts: the first part is a structured core network which forms the backbone of the hybrid system; the second part is multiple unstructured peer- to-peer networks each of which is attached to a node in the core network. The core structured network can narrow down the data lookup within a certain unstructured network accurately, while the unstructured networks provide a low cost mechanism for peers to join or leave the system freely. A data lookup operation first checks the local unstructured network and then the structured network. This two-tier hierarchy can decouple the flexibility of the system from the efficiency of the system. Our simulation results demonstrate that the hybrid peer-to-peer system can utilize both the efficiency of structured peer-to-peer network and the flexibility of the unstructured peer-to-peer network and achieve a good balance between the two types of networks.

Network coding is a promising generalization of routing which allows a network node to generate output messages by encoding its received messages to reduce the bandwidth consumption in the network. An important application where network coding offers unique advantages is the multicast network where a source node generates messages and multiple receivers collect the messages. Previous network coding schemes primarily considered encoding the messages in a single multicast session. In this paper, we consider the linear inter-session network coding for multicast. The basic idea is to divide the sessions into different groups and construct a linear network coding scheme for each group. To maximize the performance, we introduce two metrics: overlap ratio and overlap width, to measure the benefit that a system can achieve by inter-session network coding. The overlap ratio mainly characterizes the network bandwidth while the overlap width characterizes the system throughput. Our simulation results show that the proposed inter-session network coding scheme can achieve about 30% higher throughput than intra-session network coding.

In this paper, we present a new multicast architecture and the corresponding multicast routing protocol for providing efficient and flexible multicast services over the Internet. Traditional multicast protocols construct and update the multicast tree in a distributed manner, which may cause two problems: first, since each node has only local or partial information on the network topology and group membership, it is difficult to build an efficient multicast tree; second, due to lack of complete information, broadcast is often used for sending control packets and data packets, which consumes a great deal of network bandwidth. In the newly proposed multicast architecture, a few powerful routers, called m-routers, collect multicast-related information and process multicast requests based on the information collected. The m-routers handle most of multicast related tasks, while other routers in the network only need to perform minimum functions for routing. The m-routers are designed to be able to handle simultaneous many-to-many communications efficiently. The new multicast routing protocol, called the Service Centric Multicast Protocol (SCMP), builds a shared multicast tree rooted at the m-router for each group. The multicast tree is computed in the m-router by employing the Delay Constrained Dynamic Multicast (DCDM) algorithm which dynamically builds a delay constrained multicast tree and minimizes the tree cost as well. The physical construction of the multicast tree over the Internet is performed by a special type of self-routing packets in order to minimize the protocol overhead. Our simulation results on NS-2 demonstrate that the new SCMP protocol outperforms other existing protocols and is a promising alternative for providing efficient and flexible multicast services over the Internet.

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. An important scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose a method to transform the linear coding problem to a graph theory problem. With the help of hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. A valid linear code is equal to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, this method can be readily applied to many minimum network coding problems as well.

Reliable multicast is critical to multicast based applications as it provides reliability over the unreliable network. Although the primary function of reliable multicast is loss recovery and flow control which are similar to that of reliable unicast, the inherent property of multicast that multiple receivers coexist in one multicast session imposes new challenges such as acknowledge implosion and poor scalability. Among existing reliable multicast protocols, tree based reliable multicast protocols can achieve the reliability in a scalable fashion. They group the receivers into a hierarchy called the ACK tree and the ACK/NACK messages and retransmitted packets are transmitted between adjacent levels. Since current tree based reliable multicast protocols construct the ACK tree based on the multicast tree which is constructed by the multicast routing protocol, the protocol performance greatly depends on the multicast tree. In this paper, we propose a peer-to-peer (P2P) tree based reliable multicast protocol which constructs the ACK tree in a flexible way as the multicast tree is constructed in a P2P system. In our protocol, any two receivers can be adjacent nodes in the ACK tree. The ACK tree construction process is based on a heuristic function which is designed to minimize the retransmission delay. The child node sends ACK/NACK to the parent node and receives retransmitted packets from the parent node. Our protocol uses window based flow control. The window in the parent node will not advance unless the parent node receives all the ACKs from its child nodes. We conducted extensive simulations to evaluate the protocol. The simulation results show that our protocol achieves good scalability with low retransmission delay and high throughput.

In this paper, we present a new multicast architecture and the associated multicast routing protocol for providing efficient and flexible multicast services over the Internet. Traditional multicast architectures construct and update the multicast tree in a distributed manner, which causes two problems: first, since each node has only local or partial information on the network topology and group membership, it is difficult to build an efficient multicast tree; second, due to lack of the complete information, broadcast is often used when transmitting control packets or data packets, which consumes a great deal of network bandwidth. In the newly proposed multicast architecture, a few powerful routers, called m-routers, collect multicast-related information and process multicast requests based on the information collected, m-routers handle most of multicast related tasks, while other routers only need to perform minimum functions for routing, m-routers are designed to be able to handle simultaneous many-to-many communications efficiently. The new multicast routing protocol, called service centric multicast protocol (SCMP), builds a dynamic shared multicast tree rooted at the m-router for each group. The multicast tree can satisfy the QoS constraint on maximum end-to-end delay and minimize tree cost as well. The tree construction is performed by a special type of self-routing packets to minimize protocol overhead. Our simulation results on NS-2 demonstrate that the new SCMP protocol outperforms other existing protocols and is a promising alternative for providing efficient and flexible multicast services over the Internet

Multicast is an efficient way for group communication over the Internet. The performance of multicast relies greatly on the multicast tree constructed among the group members. Constructing a multicast tree spanning a set of group members with minimum cost is called Steiner tree problem which is a well-known NP-hard problem. Existing heuristic algorithms can build such a Steiner tree statically when the group members are known in advance. However, in many multicast tree dynamically. In addition, QoS is becoming a more important issue in multicast applications, and many applications, pose a tight bound on end-to-end delay. In this paper, we design a heuristic algorithm which can construct a delay constrained minimum cost multicast tree dynamically. Our algorithm can add or remove a group number without rerouting the path between the source and other group members. The algorithm not only avoids packet loss but also saves network bandwidth. Our algorithm guarantees that the end-to-end delay between the source and any group member is bounded with a threshold. Simulation results show that the algorithm achieves a good balance between the cost of a multicast tree and the time of the construction.