Network Coding

Workload

5 ECTS

Prerequisites

  • basic understanding of communication systems
  • interest in wireless and mobile systems
     

Description

The course provides an introduction to the rapidly growing research area of network coding. Network coding allows intermediate nodes in a network to manipulate data, for example by sending out packets that are combinations of previously received packets instead of simply forwarding them. For most practical purposes, these manipulations are linear operations over elements of a finite field. The initial theoretical results on network coding were followed by a wealth of applications in a number of different areas that show that the theoretical insights can be translated into practical gains.

The tutorial is divided into three parts. The first part provides the participants with the theoretical tools necessary to understand the field of network coding and focuses on the underlying algebraic principles. It will also introduce distributed randomized network codes and discuss their properties. We will not assume any prior knowledge of advanced algebra or optimization. Among other things, network coding can be used to increase throughput and robustness as well as reduce storage requirements, delay, and energy consumption.

The second part of the tutorial gives an overview of the different application areas and discusses, which types of networking problems are amenable to network coding (and which aren't). In particular, it covers practical algorithms for data gathering in sensor networks, routing in wireless mesh networks, peer-to-peer networking and content distribution, streaming applications, etc.

Finally, we will discuss implementation aspects in real-world systems. Such systems may range from core network routers all the way down to mobile phones and tiny sensor nodes. The constraints imposed by these devices in terms of available memory and computing power may differ by several orders of magnitude. As a consequence, the encoding and decoding algorithms need to be carefully adapted to the specific problem at hand. As an example, the size of the finite field for the coding operations has an impact on network coding efficiency, but also on the encoding and decoding complexity. Coding operations may be sped up substantially through the use of specialized hardware, as evidenced by the successful implementation of network coding on Graphics Processing Units (GPUs). The energy consumed by the coding operations is of particular importance on mobile devices and needs to be considered to avoid offsetting the energy gains offered by network coding.

Topics covered include:

  1. Introduction
  2. Algebraic foundations of network coding
    • Network code as operations at nodes
    • Min-cut/max-flow from an algebraic perspective
    • Random linear codes
    • Generalizations to correlated sources
    • Beyond multicast
  3. Optimization aspects
    • Moving away from trees – convex optimization of network coding
      • Distributed optimization
      • Applications to P2P download time optimization
    • Optimality of dissemination time –algebraic gossip
    • File dissemination time in wireless systems
  4. Implementation of COPE oriented approaches
    • Routing and Network Coding
    • Basic network topologies
    • Impact of the IEEE802.11 MAC
      • w/o rate adaptation
      • with rate adaption
    • Results
    • Bandwidth
    • Green
  5. Implementation of RLNC oriented approaches
    • Impact of generation and field size
    • Systematic codes
    • Designing rules for network coding on mobile phones
  6. TCP and network coding
    • Combining coding with sliding windows
    • Network combining
  7. Examples of network coding on mobile phones
    • PictureViewer
    • Video Distribution
    • Audio Distribution
  8. Demonstration of network coding on mobile phones
  9. Introduction into the network coding library

 

Texts

Different text books could be used. Further information can be found at http://mobiledevices.kom.aau.dk/ and www.fitzek.net

 

 

Network Coding -Fundamentals and Applications

by Muriel Medard & Alex SprintsonEdited By Muriel Medard & Alex Sprintson

 

 

 

 

 

 

 

Lecturers

Frank H. P. Fitzek is a Professor in the department of Electronic Systems, University of Aalborg, Denmark heading the Mobile Device group. He received his diploma (Dipl.-Ing.) degree in electrical engineering from the University of Technology - Rheinisch-Westfälische Technische Hochschule (RWTH) - Aachen, Germany, in 1997 and his Ph.D. (Dr.-Ing.) in Electrical Engineering from the Technical University Berlin, Germany in 2002 and became Adjunct Professor at the University of Ferrara, Italy.


He co-founded the start-up company acticom GmbH in Berlin in 1999. He has visited various research institutes including Massachusetts Institute of Technology (MIT), VTT, and Arizona State University. In 2005 he won the YRP award for the work on MIMO MDC and received the Young Elite Researcher Award of Denmark. He was selected to receive the NOKIA Champion Award in 2007, 2008, 2009, and 2010. In 2008 he was awarded the Nokia Achievement Award for his work on cooperative networks. His current research interests are in the areas of wireless and mobile communication networks, mobile phone programming, cross layer as well as energy efficient protocol design and cooperative networking.
 

   

Janus Heide is currently a Ph.D Fellow within the research section of Antennas, Propagation, and Radio Networking (APNET) in the Department of Electronic Systems at Aalborg University. He received his M.Sc in electrical engineering with specialization Wireless Communication Engineering in 2009 from Aalborg University, Denmark. From July 2007 he has been working in the Mobile Devices research group at Aalborg University. His main research interests are protocol analysis and design, wireless network systems, characteristics and models, cooperative communication, network coding, and data distribution in ad-hoc and meshed networks.