Network Compress-Forward
Tue., Nov 10, 2009
2:00 - 3:30 PM
400 Cory (Hughes room)
2:00 - 3:30 PM
400 Cory (Hughes room)
(this seminar also serves as Lecture 19 in Prof. Abbas El Gamal's seminar course)
From torch relays at the Great Wall of China to the wireless ad-hoc mesh network architecture in the One Laptop Per Child Project, relaying is one of the fundamental building blocks of network communication. Over the past 30 years, a 3-node relay channel (1 source, 1 relay, and 1 destination) has been studied in network information theory as a toy model to provide basic design principles for optimal relaying. At one extreme, the relay decodes the intended message from the source and forwards it to the destination. As Cover and El Gamal showed, this simple multi-hop decode-forward coding scheme can be further improved by coherent transmission between the source and relay, and more sophisticated decoding at the destination. This paradigm of relaying is widely adopted in wireless mesh networks.
At the other extreme, the relay instead summarizes its noisy observation of the source signal and forwards the summary description. This compress-forward relaying, again proposed by Cover and El Gamal, can be viewed as a natural generalization of wireless repeaters that simply amplify and forward the noisy observation. The relay operation in the compress-forward coding scheme is less sensitive to the end-to-end operations at the source and destination, making it more attractive than decode-forward. Yet its potential for a general network has not been fully explored due to the apparent difficulty in extending the single relay compress-forward to multiple relays.
In this talk, we extend the compress-forward coding scheme to a general network with multiple sources and multiple destinations, demonstrating that it provides a robust and scalable building block for relaying. In particular, we show that the network compress-forward coding scheme extends all previously known results on relay networks (except for decode-forward), including multicast network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros, and coding for linear erasure networks by Smith and Vishwanath. The key idea behind network compress-forward is message repetition coding in which the source transmits a single message over multiple transmission blocks.
Joint work with Sung Hoon Lim (KAIST, currently visiting UCSD), Abbas El Gamal (Stanford), and Sae-Young Chung (KAIST)
Short bio:
Young-Han Kim is an assistant professor in the Department of Electrical and Computer Engineering at the University of California, San Diego. Professor Kim’s research primarily focuses on network information theory and the role of feedback in communication networks. More broadly, he is interested in statistical signal processing and information theory, with applications in communication, control, computation, networking, data compression, and learning.
Professor Kim received his B.S. degree with honors in Electrical Engineering from Seoul National University, in 1996, where he was a recipient of the General Electric Foundation Scholarship. After a three-and-half-year stint as a software architect at Tong Yang Systems, Seoul, Korea, working on several industry projects such as developing the communication infrastructure for then newly opening Incheon International Airport, he resumed his graduate studies at Stanford University, and received his Ph.D. degree in Electrical Engineering (M.S. degrees in Statistics and in Electrical Engineering) in 2006.
Professor Kim is a recipient of the 2008 NSF Faculty Early Career Development (CAREER) Award.
From torch relays at the Great Wall of China to the wireless ad-hoc mesh network architecture in the One Laptop Per Child Project, relaying is one of the fundamental building blocks of network communication. Over the past 30 years, a 3-node relay channel (1 source, 1 relay, and 1 destination) has been studied in network information theory as a toy model to provide basic design principles for optimal relaying. At one extreme, the relay decodes the intended message from the source and forwards it to the destination. As Cover and El Gamal showed, this simple multi-hop decode-forward coding scheme can be further improved by coherent transmission between the source and relay, and more sophisticated decoding at the destination. This paradigm of relaying is widely adopted in wireless mesh networks.
At the other extreme, the relay instead summarizes its noisy observation of the source signal and forwards the summary description. This compress-forward relaying, again proposed by Cover and El Gamal, can be viewed as a natural generalization of wireless repeaters that simply amplify and forward the noisy observation. The relay operation in the compress-forward coding scheme is less sensitive to the end-to-end operations at the source and destination, making it more attractive than decode-forward. Yet its potential for a general network has not been fully explored due to the apparent difficulty in extending the single relay compress-forward to multiple relays.
In this talk, we extend the compress-forward coding scheme to a general network with multiple sources and multiple destinations, demonstrating that it provides a robust and scalable building block for relaying. In particular, we show that the network compress-forward coding scheme extends all previously known results on relay networks (except for decode-forward), including multicast network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros, and coding for linear erasure networks by Smith and Vishwanath. The key idea behind network compress-forward is message repetition coding in which the source transmits a single message over multiple transmission blocks.
Joint work with Sung Hoon Lim (KAIST, currently visiting UCSD), Abbas El Gamal (Stanford), and Sae-Young Chung (KAIST)
Short bio:
Young-Han Kim is an assistant professor in the Department of Electrical and Computer Engineering at the University of California, San Diego. Professor Kim’s research primarily focuses on network information theory and the role of feedback in communication networks. More broadly, he is interested in statistical signal processing and information theory, with applications in communication, control, computation, networking, data compression, and learning.
Professor Kim received his B.S. degree with honors in Electrical Engineering from Seoul National University, in 1996, where he was a recipient of the General Electric Foundation Scholarship. After a three-and-half-year stint as a software architect at Tong Yang Systems, Seoul, Korea, working on several industry projects such as developing the communication infrastructure for then newly opening Incheon International Airport, he resumed his graduate studies at Stanford University, and received his Ph.D. degree in Electrical Engineering (M.S. degrees in Statistics and in Electrical Engineering) in 2006.
Professor Kim is a recipient of the 2008 NSF Faculty Early Career Development (CAREER) Award.
UC Berkeley Networking
Kristen Woyach and Pulkit Grover Last Modification Date: Wednesday, August 19, 2009
Kristen Woyach and Pulkit Grover Last Modification Date: Wednesday, August 19, 2009