Network Coding Theory

By Raymond W. Yeung, Shuo-Yen Robert Li, Ning Cai and Zhen Zhang

Consider a network consisting of point-to-point communication channels. Each channel transmits information noiselessly subject to the channel capacity. Data is to be transmitted from the source node to a prescribed set of destination nodes. Given the transmission requirements, a natural question is whether the network can fulfill these requirements and how it can be done efficiently.

In existing computer networks, information is transmitted from the source node to each destination node through a chain of intermediate nodes by a method known as store-and-forward. In this method, data packets received from an input link of an intermediate node are stored and a copy is forwarded to the next node via an output link. In the case when an intermediate node is on the transmission paths toward multiple destinations, it sends one copy of the data packets onto each output link that leads to at least one of the destinations. It has been a folklore in data networking that there is no need for data processing at the intermediate nodes except for data replication.

This text aims to be a tutorial on the basics of the theory of network coding. The intent is a transparent presentation without necessarily presenting all results in their full generality. Part I is devoted to network coding for the transmission from a single source node to other nodes in the network. It starts with describing examples on network coding in the next section. Part II deals with the problem under the more general circumstances when there are multiple source nodes each intending to transmit to a different set of destination nodes.

Following are the few topics covered in this Network coding book.

• Linear coding
• Nonlinear coding
• Random coding
• Static codes
• Convolutional codes
• Group codes
• Alphabet size
• Code construction
• Algorithms/protocols
• Cyclic networks
• Undirected networks
• Link failure/Network management
• Separation theorem
• Error correction/detection
• Cryptography
• Multiple sources
• Multiple unicasts
• Cost criteria
• Non-uniform demand
• Correlated sources
• Max-flow/cutset/edge-cut bound
• Superposition coding
• Networking
• Routing
• Wireless/satellite networks
• Ad hoc/sensor networks
• Data storage/distribution
• Implementation issues
• Matrix theory
• Complexity theory
• Graph theory
• Random graph
• Tree packing
• Multicommodity flow
• Game theory
• Matriod theory
• Information inequalities
• Noisy channels
• Queueing analysis
• Rate-distortion
• Multiple descriptions
• Latin squares
• Reversible networks
• Multiuser channels
• Joint network-channel coding

Read More/Try It

Thinking Networks - the Large and Small of it

By Kieran Greer

The book is titled 'Thinking Networks - the Large and Small of it'. The topics covered span from large global networks to small local neural-like networks, hence the title. The book is mainly a research monograph, but it also contains blue sky research suggestions and also some informative or teaching sections. This book tries to cover research areas that look at adding autonomous or reasoning capabilities to information networks. It would be of interest to both academic or industrial researchers looking to build intelligent networks. For example, the telecommunications sector might want to add intelligent services to the Internet or a mobile environment. The book however could be used to build networks that range in size from large Internet-based networks to small local neural network-like structures, and ultimately suggests an architecture on which to build a network that might even begin to 'think'. Some of the research has been proven, while the more ambitious claims or suggestions are for future research.

The book covers areas such as the Internet/p2p/ mobile networks, SOA, Semantic Networks (Semantic Web, Ontologies, Web Services, Grid), AI (including Autonomous systems, Intelligent, Cognitive or Neural Network-like systems, and Bio-inspired networks), XML-based languages and query processes. It is available from different online stores and is also listed on the ACM portal. The technologies that are described in this book are also strongly related to the new 'Cloud Computing' architecture that is being talked about for the Internet.

Read More/Try It