| Abstract |
Network coding is a promising generalization of routing to improve network throughput and provide high reliability. It allows a node to generate output messages by encoding its received messages. It has a wide range of applications from wireless networks to network tomography. In this talk, I will focus on applying network coding to multicast networks, especially peer-to-peer file sharing systems where a file resided in a file server is requested by multiple receivers, or peers. Our proposed approach exploits a special type of network topology called combination network. The peers are divided into multiple groups and the file is encoded into multiple messages 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 give a deterministic linear network coding scheme with constant time complexity. Then the peers in the same group are connected to flood the corresponding message based on some loose rules to accommodate flexibility. The peers in different groups are connected in such a way that each peer is connected to at least a certain number of peers in different groups to guarantee decoding.
I will also discuss a linear network coding construction algorithm which provides a unified solution for a series of minimal network coding problems for multicast networks. The linear coding problem is transformed to a graph theory problem with the help of hypergraphs. A pseudo-dual graph, which is a hypergraph, is constructed based on the graph representing the network topology. Under this transformation, a valid linear code in the original network is equal to a cover in the pseudo-dual hypergraph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time.
|
| Bio |
Min Yang received his BEng degree in computer science from Beijing University of Posts & Telecommunications and MS degrees in computer science from Tsinghua University, China, in 1999 and 2002, respectively. Since 2003, he has been studying towards the PhD degree in the Department of Electrical and Computer Engineering at the State University of New York at Stony Brook. His research interests include multicast, peer-to-peer networks and distributed systems.
|
