Abstract & Bio

The seminal paper on network coding by Ahlswede, Cai, Li and Yeung (2000) showed that the information throughput in a communication network can be increased if routers, instead of being dumb store-and-forward devices, are allowed to combine incoming information (packets) before forwarding. In our semi-tutorial presentation, we discuss an efficient algorithm [1] for determining how, for a given network, routers can combine incoming packets such as to achieve the highest possible information throughput. The algorithm applies if all sinks in the network are interested in the same information, communication is delay-less, and the directed graph modelling the network is cycle-free and has unit capacity edges.

We also reminisce on how the seven-author paper [1] came into being.

[1] S. Jaggi, P. Sanders, PA Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, “Polynomial time algorithms for multicast network code construction,” IEEE Transactions on Information Theory, IEEE Transactions on, vol. 51, no. 6, pp. 1973–1982, 2005.

Biography

Since obtaining his M.Sc degree in mathematics from Eindhoven University in 1986, Ludo Tolhuizen has been with Philips Research where, amongst others, he has co-developed the error-correcting coding scheme in the Blu-Ray Disc system. In 1996, he obtained his PhD degree from Eindhoven University with a thesis on “Co-operating error-correcting codes”. Dr. Tolhuizen served as associate editor coding theory for IEEE Transactions on Information Theory from 2006 until 2009, and as secretary of the IEEE Benelux Information Theory Section from 2002 until 2008. His research interests include error-correcting codes, discrete mathematics and information theory.

Abstract & Bio

Cyclic networks present a challenge that is traditionally avoided in many papers in network coding literature by assuming that the network they deal with is acyclic. Nevertheless, in practice most networks will present cycles and this is specially so in the case of wireless networks, as we will discuss here. In our presentation we will explain the different types of cyclicity that may be present in cyclic networks and extend the “seminal” idea in the LIF algorithm (presented in the previous talk of the session by L. Tolhuizen) in order to design an algorithm to encode in presence of cycles of any type. The two key ideas here are the use of Mason’s formula to compute transfer functions in a circuit and the consideration of delay (both natural and introduced ad-hoc) in the transmission through each link. The talk will also discuss the case of wireless networks, and show how actively avoiding cyclicity can result in a penalty in terms of total transmission power.

Main references:

[1] Á. Barbero and Ø. Ytrehus,

“Introduction to Network Coding for Acyclic and Cyclic Networks,” Selected Topics in Information and Coding Theory, Woungang, Misra and Misra (eds.) World Scientific, pp. 339-423, 2010.

[2] M. Ravanbakhsh, Á. Barbero and Ø. Ytrehus, “Power savings of cyclic network coding for multicast on wireless networks,” Proceedings of IEEE Information Theory Workshop, Cairo, Jan. 2010.

Biography

Ángela Barbero received the graduation and the doctorate in Mathematics from the University of Valladolid, Spain, and is currently a professor at the Department of Applied Mathematics in the same University. In the last years she is a regular visitor of the Selmer Center of the University of Bergen in Norway. She is currently at the Selmer Center supported by a grant from the NILS mobility project-Abel Extraordinary Chair through the EEA Financial Mechanism.

Abstract & Bio

Real-world wireless multihop networks differ from traditional wired networks in that (1) information messages are sent through a local broadcast signal which will reach the transmitter´s closest neighbours, (2) each node in the network will receive a signal corresponding to the superposition of messages sent by all transmitting neighbours, and (3) signals sent over the channel may be subjected to a complicated mixture of noise, fading, path loss, shadowing, and other effects. The deterministic network model, recently introduced by Avestimehr, Diggavi, and Tse, captures the broadcast and superposition characteristics of such a channel, while eliminating the random components of the channel by assuming perfect channel coding. The model can be shown to approximate the behaviour of a multihop wireless channel subjected to white Gaussian noise. This talk will review some approaches to the surprisingly challenging task of deriving the information flow and corresponding coding solutions for a single unicast session on such a network. It will also include new results from ongoing research focused on the case where the deterministic network is derived from a two dimensional geometric network.

Biography

Øyvind Ytrehus has been a professor at the University of Bergen, Norway since 1992. His research interests include coding and information theory.