New Paradigm of Network Communications

The conventional way of data transmission, such as over a telephone network or on the Internet, was like postal delivery—one station forwards the parcel to the next, and on to the next and so forth. This transmission mode is called “store-and-forward”. Since the 1980s, there have been a few instances where data did not get stored but broken up and mixed during the transmission process and which were decoded or converted back to their original message at the receiving end. Commodities of real objects do not enjoy this malleability as data, which can be coded and decoded, do.

Advantage of information over commodity

For decades, however, the implications of this alternative way of transmitting data had not been fully recognized or its application explored, with two exceptions in 1988: the introduction of “Redundant Array of Independent Disks” in magnetic data storage; and the work of Prof. Robert Li, Professor at the Department of Information Engineering of CUHK, on optimizing the capacity of transmission channels while he was with Bellcore in New Jersey. Another example was the work on satellite communications in 1997 by Prof. Raymond W. Yeung, Choh-Ming Li Professor of Information Engineering of CUHK and Prof. Zhen Zhang of the University of Southern California.

All was very well except that no common mathematical formulation or structural model had emerged to break down disciplinary barriers and connect the dots as well as the different researchers and theoreticians working in disparate but related fields.

A butterfly was born

In the summer of 1997, following up on his work with Professor Zhang, Professor Yeung started working with Dr. Ning Cai of the University of Bielfeld, Germany on applying the new mode of transmitting data in a general setting. In September he discussed his work in Germany with Professor Li, who at that time was thick in the writing of a book on switching theory. In what turned out to be an extremely important meeting between the two, Professor Li worked out a simple illustration of the benefit of Network Coding (NC), now known as the Butterfly Network. Although each of them had his own theoretical and/or practical preoccupations, both of them were fascinated by the Butterfly Network. The algebraic significance behind the Butterfly Network was so compelling that Professor Li actually suspended his book writing for almost two months to devote himself to working out further details.

Two theories of NC were born as a result. First, a nonlinear theory was formulated in an information-theoretic way by Professor Yeung and Professor Cai. Second, a linear theory was formulated by Professor Li as a linear-algebraic generalization of the Butterfly Network. Eventually, the nonlinear theory, together with the Butterfly Network, was published in a journal paper entitled “Network Information Flow” in July 2000. Two different formulations of a general setting both proved the superior efficiency of NC over the “store-and-forward” mode.

Linear NC adopts linear coding/decoding mechanisms, which are easy to implement in practice. They also keep the theory mathematically tidy. Since 2003, NC has been an increasingly popular research topic and revolutionized the study of data flow through networks. Professor Li, Professor Yeung and Professor Cai won the 2005 IEEE Information Theory Society Paper Award with their 2003 paper entitled “Linear Network Coding”. The achievement in NC has led to the establishment of the Institute of Network Coding in CUHK, funded by an Areas-of-Excellence grant and co-directed by Professor Li and Professor Yeung.