Events Calendar

Bringing Network Coding Closer to Practice

Speaker: Christina Fragouli, Swiss Federal Institute of Technology (EPFL), Switzerland

Talk Title: Bringing Network Coding Closer to Practice

Abstract: The paradigm of network coding allows intermediate nodes in a network to not only forward but also combine their incoming information flows. This modern application of coding to the theory and practice of communication networks raises novel and exciting research problems, and is promising to have an impact in diverse areas of network communications that include multicasting, network monitoring, resource sharing, network security, among other areas.

However, one of the main challenges is to realize the benefits of network coding functionalities with implementable computational complexity. We illustrate through two examples how algorithmic and combinatorial tools can be applied to make progress on this challenging question.

One of the challenges in the deployment of network coding is the fact that network nodes may need to perform operations over relatively large finite fields. We propose instead to use vector network coding, where nodes process and combine binary packets by multiplying them with binary coding matrices, as opposed to scalar coefficients over a field. We introduce an algebraic framework for vector network coding, and provide a polynomial time algorithm for the design of coding matrices, that aims to minimize the size of the employed matrices, and thus reduce the encoding complexity. Our algorithm reduces the problem of finding small size matrices to the problem of finding a small degree coprime factor of an algebraic polynomial, and leads to solutions not possible with using scalar network coding.

We then consider a specific application. Our scenario is that a group of wireless nodes want to exchange a secret key, such that no eavesdropper can guess the key. Using network coding techniques, we develop a protocol that enables the group of nodes to agree on secret bits at a rate depending on the properties of the wireless network that interconnects them. Our protocol uses simple, polynomial-time operations and does not require any changes to the physical or MAC-layer of network devices. We formally prove and experimentally demonstrate that our protocol can generate information-theoretically secret keys in a realistic setting.


Biography: Christina Fragouli is a tenure track Professor in the School of Computer and Communication Sciences, EPFL, Switzerland. She received the B.S. degree in Electrical Engineering from the National Technical University of Athens, Athens, Greece, in 1996, and the M.Sc. and Ph.D. degrees in electrical engineering from the University of California, Los Angeles, in 1998 and 2000, respectively. She has worked at the Information Sciences Center, AT&T Labs, Florham Park New Jersey, and the National University of Athens. She also visited Bell Laboratories, Murray Hill, NJ, and DIMACS, Rutgers University. From 2006 to 2007, she was an FNS Professor in the School of Computer and Communication Sciences, EPFL, Switzerland.

Her research interests are in network information flow theory and algorithms, network coding, wireless sensor networks, and connections between communications, networking and computer science. She received the Fulbright Fellowship for her graduate studies, the Outstanding Ph.D. Student Award 2000-2001, UCLA, Electrical Engineering Department, the Zonta award 2008 in Switzerland, and the Young Investigator ERC grant award in 2009. She served as an editor for IEEE Communications Letters, and is currently serving as an editor for IEEE Transactions on Information Theory, IEEE Transactions on Communications, IEEE Transactions on Mobile Computing and Elsevier Computer Communications.

Host: Giuseppe Caire, caire@usc.edu, EEB 528, x04683

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos