ACoRN Network Coding School

  • Date: Dec 1-2, 2008
  • Workshop times: Monday 10.00-5.00, Tuesday 9.00-3.00
  • Speakers: Prof. Raymond Yeung and Dr. Terence Chan
  • Location:Institute for Telecommunications Research, Univ. of South Australia

Abstract

Since its inception, network coding has been a vibrant research area and is being heavily investigated. This short course on network coding, error correction and security aims to introduce the audience the state-of-the-art in relevant areas.

Part I: Network coding

Single-source multicast

We will start with an introduction to network coding and explain its advantage over traditional routing. We will first consider the single-source multicast scenario. Unlike its routing counterpart, the maximum network throughput achievable by network coding can be easily determined and is given by Max-Flow Min-Cut bound. We will also prove that linear network codes suffice to achieve the maximum throughput.

Construction of linear network codes

We will then examine two main approaches to linear network code construction. The first one is a deterministic approach in which the code is designed in a centralized fashion assuming full knowledge of the whole network topology. The second approach is random and decentralized. We will give bounds on the probability of decoding error of a randomly generated network code.

Multi-sources multicast and bounding technique

Finally, we will investigate the multi-sources scenario. Unlike its single-source counterpart, not too many results have been obtained so far. Max-Flow Min-Cut bounds are no longer tight in characterizing the set of achievable rates. In fact, we will show that finding the set of achievable rates is extremely hard and is intimately related to the characterization of entropy functions and information inequalities. We will survey techniques that give bounds on the achievable rates. We will conclude the first part by proving the sub-optimality of linear network codes in this general setting.

Part II: Network error correction and security

In the second part, we will focus on using network coding as a tool to enhance robustness and secrecy in communications. We begin with a scenario in which the adversaries aim to obtain information by wiretapping the network. We will show how to construct secure network codes by injecting randomness into network-coded packets so as to prevent eavesdroppers from inferring any information about the transmitted message.

Then we will study a different scenario where the adversaries aim at disrupting communication between legitimate parties by deleting or injecting data packets in networks. We will first consider the case where the network topology is known and fixed. A framework will be given to illustrate how errors injected by the adversaries can be corrected. Bounds on the maximum transmission rate will then be given. In the second case, knowledge on the underlying network topology is absent. We will model the networks as a black box in which random linear network coding is performed, and will then discuss bounds on the maximum transmission rates.

About the speakers

Raymond Yeung

Raymond Yeung is a world-renowned information theorist. Together with N. Cai, S.-Y. R. Li and R. Ahlswede, he started the area of network coding in 2000. He was elected an IEEE Fellow in 2003, in recognition of his contributions to the area. Their pioneering work has introduced a fundamentally new paradigm for network communications. In his subsequent paper with Li and Cai, linear network codes were proposed and shown to be optimal in single-source multicast. The paper was another major breakthrough in the area by showing that network-coding gain can be realized by simple linear coding schemes. The paper was awarded the 2005 IEEE Information Theory Society Best Paper Award.

Prof. Yeung is a Chair Professor of the Department of Information Engineering at The Chinese University of Hong Kong. He is also a visiting Professor of Xidian University and a Consulting Professor of Beijing University of Post and Telecommunications in China.

He was a recipient of the Croucher Senior Research Fellowship for 2000/01, the Best Paper Award (Communication Theory) of the 2004 IEEE International Conference on Communications, Circuits and Systems, the 2005 IEEE Information Theory Society Paper Award, and the Friedrich Wilhelm Bessel Research Award from the Alexander von Humboldt Foundation in 2007. He is a Fellow of the IEEE and the Hong Kong Institution of Engineers.

Terence Chan

Dr. Terence Chan received his B.Sc (Math) and his Master's and Ph.D. degrees in Information Engineering in 1996, 1998 and 2000 respectively, all from The Chinese University of Hong Kong. From February 2002 to June 2004, he was a Post-doctoral Fellow at the Department of Electrical and Computer Engineering at the University of Toronto. From 2004 to 2006, he was an assistant professor at the Department of Computer Science at the University of Regina. Dr. Chan is currently a senior research fellow at Institute for Telecommunications Research.

Chan has made fundamental contributions to information theory, applied to communications networks. He has proposed group theoretic and combinatorial interpretations of information inequalities. As a result of the work, a rich set of tools in combinatorics and group theory becomes available for proving new information inequalities, and more generally, for deriving bounds for network coding capacity region. Together with A. Grant, he also proved that the problem of identifying network coding capacity region is closely related to that of characterizing entropy functions. This resulted in an alternative proof of the suboptimality of linear network codes.

Chan has served as TPC members in various conferences including Workshop on Network Coding, Theory and Applications, IEEE Int. Workshop on Wireless Network Coding, and International Conference Communications and Networking in China. He was a recipient of Croucher Foundation Fellowship and Sir Edward Youde Fellowship in 2002 and 2000 repsectively.

Registration and additional Information

The registration fee is AU$100 for ACoRN Members, AU$300 for Non ACoRN Members and includes coffee/tea breaks and a light lunch. Download the registration form for full details and to register for the workshop.

Support

For eligible ACoRN members financial support is available through the ACoRN Domestic Conference/Workshop Attendance Grants.

Venue

The school will be held in the lecture theatre at the Institute for Telecommunications Research (ITR), University of South Australia, Mawson Lakes campus. The ITR is located in the SPRI building. The University has an A4 map of the campus that shows the SPRI building (W) that you may like to print out.

View the accommodation page for possible accommodation options and also public transport details for travelling to the venue.

Presentations

Please find the following presentations available for download:

 

More information

For more information, please contact ACoRN and the administration staff can either answer your query or pass onto someone who can.