Skip to main content Skip to navigation

School of Engineering

Network coding

Communication in the Engineering sense refers to the process of transferring information between two or more places in a form that can be processed by communications equipment. Communication systems convey information, which is precisely defined for mathematical analysis but may be taken loosely to mean the symbols that make up the message. A transmission system is of little use if it cannot transmit information reliably, to help in this process a set of input bits is processing it in some way to produce a different set of output bits, known as coding. Often there are more output bits than input bits because redundant information has been added to help in message recovery.

Coding has also been used to compress computer files and for encrypting messages. In 2000, a new use for coding was proposed: to increase the efficiency of message transmission through a computer network. Nodes in a traditional communications network pass on information unaltered if they are not the intended recipient, and all coding takes place at the transmitter and the receiver. In network coding, by allowing the intermediate nodes to modify messages, it has been shown that more information may be sent through a network in a given time, in comparison to just forwarding the messages unaltered. Finding the right network codes is not easy, nor is deciding which network nodes should carry out the coding. In fact, some of the problems are of a type that is very difficult to solve in any reasonable time.

A current research project, led by Dr. Mark Leeson, is investigating the employment of evolutionary computing to the search for network codes. This work applies methods derived from nature, known as evolutionary algorithms, to some currently interesting problems in network coding. The starting point is the selection of nodes for coding via genetic algorithms, which has only recently been considered in the literature. The performance of genetic algorithms will be compared with genetic programming for this problem for the first time in this work.

In parallel, the dynamic nature of modern communication networks is also considered. Through this phase of the work, network codes will be shown to be practical for future communication networks. Valuable insight into the adaptation of evolutionary algorithms for important areas will also be gained.

Network coding is an important development in modern communications and combining it with evolutionary algorithms will have a significant impact on the development of new codes for the data-hungry world of today and tomorrow.

Network Coding

Classic network coding example

In this, a source is attempting to send a message to two sinks; this is thus a multicast problem (one source and multiple receivers). In the figure each link has a capacity of 1 unit per time slot but a multicast rate of 2 units per timeslot is possible by network coding applied at node 3. The source sends both messages a and b which are coded via the sum modulo 2 at node 3. Sink 1 may recover b by further modulo 2 addition of a to the received sum a+b, with a similarly recoverable at sink 2 by the addition of b.

Examination of the network shown reveals that coding is only required at node 3 to achieve enhanced capacity. The question that arises from this observation is to whether it is possible to determine more generally which nodes in a given network need to perform network coding. The problem is NP-hard in general for multicast, with the order of the checking process growing rapidly to an infeasible size as the number of nodes increases. Such a problem is highly suitable for the application of the evolutionary algorithms that form part of the core competences of the ICT Group. There has been some work in this area in the USA but work here is the first in the UK.

In recent work, genetic algorithms based on permutation representations and ripple spreading have been designed.

Following on from this, network coding has been applied to automatic repeat request (ARQ) schemes.

 
 
 
 

Selected publications