Frequently Asked Questions

This page tries to answer common questions about network coding and Kodo.

Network Coding

Questions about general terms and concepts in network coding.

What is a source, sink, and relay?

One common application for erasure correcting codes (which includes network coding) is to improve the performance of computer networks or communication networks in general. For such applications, specific terminology is often used to precisely define the roles of the different entities in the network. For example:

A source is a device that transmits data to one or more other devices(s). This is also often called the server.

A sink is a device that receives data from other devices(s). These are also sometimes referred to as the clients.

A relay is a device that receives data from other devices(s) and re-transmits that data to other devices(s), typically the relay itself is not interested in receiving the data.

What do we mean by the original data?

The original data is a file or a buffer stored in memory before it is passed to the erasure correcting code. We sometimes also refer to this as the uncoded data.

What is a code?

Coding can be thought of as transforming the original data to a form that is more appropriate for transportation. The erasure codes that are implemented in Kodo can be used to recover packet erasures. A packet erasure is the loss of a packet, similar to a lost letter in the postal service.

What is a rateless code?

With a rateless code an infinite number of representations of the original data can be created, unlike for codes with a rate where a fixed number of representations are possible. That makes it possible to recover from any number of erasures with a rateless code.

What is a finite field?

A finite field or Galois Field (GF) is a mathematical construct and entails to much explanations to be included here. It is not necessary to have a deep understanding of finite fields, but some understanding is useful. Simplified a finite field is a variable where special rules are defined for the arithmetic operations. These rules guarantee that the result of operating on a finite field will always result in a value that is in the field which is very useful on computers with fixed precision. One common field is the binary field GF(2) where addition is defined by the XOR operation. Typically GF(2) or GF(2^8) is used since they correspond to a bit and a byte respectively. The size of a field is typically denoted \(q\).

What is an element?

An element is an element in a GF which can be thought of as a variable with the type of a specific finite field variable.

What is a symbol?

A symbol is a vector of GF elements that represent some data. The size of a symbol is given by the number of elements and the size of each element.

\(|\boldsymbol{s}| = n \cdot \log_2(q) ~ [b]\)

As an example 16 elements in GF(2) can represent two bytes.

What is a generation?

Each generation constitutes \(g\) symbols of size \(m\), where \(g\) is called the generation size. The \(g\) original symbols in one generation, are arranged in the matrix \(\boldsymbol{M}= [ \boldsymbol{m}_1 ; \boldsymbol{m}_2 ; \dots ; \boldsymbol{m}_g ]\), where \(\boldsymbol{m}_i\) is a column vector. In an application the block of data can be a file or a part of a media stream, and is divided into \(\lceil \frac{B}{m} \rceil\) pieces, called symbols. Generation number 0 constitutes the first g symbols, or the first \(g \cdot m\) bytes of data, there are \(\lceil \frac{B}{g \cdot m} \rceil\) of such generations.

What is the generation size?

The generation size is the number of symbols in the generation denoted \(g\).

What is a coding vector?

The coding vector describes how a coded symbol was coded. It contains a coefficient (which is a element) for each symbol in the generation.

The coding vector is typically denoted; \(\boldsymbol{v} = \{v_0; v_1; ... ; v_{g-1} \}\)

This column vector of elements are the coefficients which have been multiplied onto the original symbols.

What is a coded symbol?

A coded symbol is a symbol which is a combination of the original symbols in a generation. Therefore a coded symbol is a representation of all the data in a generation, but it has the same size as an original symbol.

A coded symbol is encoded by multiplying the original data with a coding vector; \(\boldsymbol{x} = \boldsymbol{M} \cdot \boldsymbol{v}\). See encoding for a more detailed description, and recoding for how coded symbols are created when recoding.

What is a coded packet?

Is a pair of a coded symbol and a coding vector. To decode a coded symbol the corresponding coding vector must be known and therefore typically the two are transmitted together in a single packet; \(\{ \boldsymbol{v}, \boldsymbol{x} \}\)

What is linear dependency?

A packet is non-innovative or linearly dependent if it only contains information about previously known symbols. In other words, the packet can be reduced to the zero vector using the linear combination of some (partially) decoded symbols.

What is systematic coding?

Systematic coding means first transmitting all symbols in two stages. In the first stage, the sender transmits all original symbols uncoded. In the second stage, the sender generates random linear combinations of the original symbols in order to correct any packet losses which might have occurred during the first stage.

What is the code density?

The code density can be defined as the ratio of non-zero elements in an coding vector. Full density can be achieved by selecting coding coefficients according to a random uniform distribution. In contrast, sparse codes use many zero coefficients in the coding vectors which makes the encoding process significantly faster. The density of a coding vector is the ratio of non-zero elements in the coding vector.

\(d(\boldsymbol{v}) = \frac{\sum_{i=1}^g \boldsymbol{v}_i \neq 0}{g}\), where: \(\boldsymbol{v}_i\) is the coding vector

The density is sometimes also referred to as the degree.

How does encoding work?

To encode a new symbol \(\boldsymbol{x}\) from a generation at the source, \(\boldsymbol{M}\) is multiplied with a randomly generated coding vector \(\boldsymbol{v}\) of length \(g\), \(\boldsymbol{x} = \boldsymbol{M} \cdot \boldsymbol{v}\). In this way we can construct \(g+r\) coded symbols and coding vectors, where \(r\) is any number of redundant symbols as the code is rateless. When a coded symbol is transmitted on the network it is accompanied by its coding vector, and together they form a coded packet. A practical interpretation is that each coded symbol, is a combination or mix of the original symbols from one generation. The benefit is that nearly infinite coded symbols can be created.

How does decoding work?

In order for a sink to successfully decode a generation, it must receive \(g\) linearly independent symbols and coding vectors from that generation. All received symbols are placed in the matrix \(\boldsymbol{\hat{X}} = [\boldsymbol{\hat{x}_1} ; \boldsymbol{\hat{x}_2} ; \dots ; \boldsymbol{\hat{x}_g}]\) and all coding vectors are placed in the matrix \(\boldsymbol{\hat{V}}=[\boldsymbol{\hat{v}_1} ; \boldsymbol{\hat{v}_2} ; \dots ;\boldsymbol{\hat{v}_g} ]\), we denote \(\boldsymbol{\hat{V}}\) the coding matrix. The original data \(\boldsymbol{M}\) can then be decoded as \(\boldsymbol{\hat{M}} = \boldsymbol{\hat{X}} \cdot \boldsymbol{\hat{V}}^{-1}\). In practice if approximately any \(g\) symbols from a generation are received the original data in that generation can be decoded. This is a much looser condition, compared to when no coding is used, where exactly all \(g\) unique original symbols must be collected.

How does recoding work?

Any node that have received \(g'\), where \(g' = [2,g]\) is the number of received linearly independent symbols from a generation and is equal to the rank of \(\boldsymbol{\hat{V}}\), can recode. All received symbols are placed in the matrix \(\boldsymbol{\hat{X}} = [\boldsymbol{\hat{x}_1} ; \boldsymbol{\hat{x}_2} ; \dots ; \boldsymbol{\hat{x}_{g'}}]\) and all coding vectors in the matrix \(\boldsymbol{\hat{V}} = [\boldsymbol{\hat{v}_1} ; \boldsymbol{\hat{v}_2} ; \dots ; \boldsymbol{\hat{v}_{g'}}]\). To recode a symbol these matrices are multiplied with a randomly generated vector \(\boldsymbol{w}\) of length g’, \(\boldsymbol{\tilde{v}} = \boldsymbol{\hat{G}} \cdot \boldsymbol{w}\), \(\boldsymbol{\tilde{x}} = \boldsymbol{\hat{X}} \cdot \boldsymbol{w}\). In this way we can construct \(r'\) randomly generated recoding vectors and \(r'\) recoded symbols. \(r'>g'\) is possible, however a node can never create more than \(g'\) independent symbols. Note that \(\boldsymbol{w}\) is only used locally and that there is no need to distinguish between coded and recoded symbols. In practice this means that a node that have received more than one symbol can recombine those symbols into recoded symbols, similar to the way coded symbols are constructed at the source.

How can the role of a node change during a session?

A sink can become a relay, and a relay can become a source. As an example lets consider a topology with three nodes, A, B and C. B has a link to both A and C, but A and C only have a link to B, and therefore cannot communicate directly. A is the source and hold data that is to be transmitted to both sinks B and C. Initially A transmits coded packets to B. After some time B holds some coded (and uncoded) packets but not the full data from A and starts to send recoded packets to C, B has now become a relay. After some more time B has received enough packets from A to decode the original data, B continues to send packets to C, but B is now a source since it has all the original data and can encode.

How does coding affect the overhead?

Network Coding involves some overhead as it is necessary to communicate additional information in the coded packets (in the coding vectors). In practice, the size of the coding vector is generally small compared to the packet payload. The exact size depends on the finite field size, the generation size and the coding vector representation.

Another source of overhead is linear dependency since a random code might produce a small number of linearly dependent (redundant) coded packets. This should be considered if we choose a small field size or low/sparse code density.

In practice, we can use a systematic code to ensure reliability with a low overhead. This is the recommended approach in single-hop networks.

How does the generation size affect delay?

The generation size \(g\) is the number of symbols over which encoding is performed, and defines the maximal number of symbols that can be combined into a coded symbol. Data is decoded on a per generation level, thus at least \(g\) symbols must be received before decoding is possible. Hence the size of a generation \(g \cdot m\) dictates the decoding delay which is the minimum amount of data that must be received before decoding is possible.

Why do we need generations?

If a whole file was considered one big block, then the computational complexity of the encoding and decoding operations would be very high. This is especially problematic on mobile and embedded devices with limited computational capabilities. Therefore, large data sets are typically split into several equal-sized generations.

When are the lost symbols/packets recovered?

Let’s suppose the \(N\) packets were lost from a generation and the sender does not have any information about which packets were lost. In this case, at least \(N\) coded packets are required to recover them. Note that the packets will not be recovered one-by-one, but all at once after the decoder processes \(N\) innovative coded packets.