Your Digital Fountain

Download source 

Introduction 

Implementation of Luby transform Code in C#, with Demo application in WPF and WCF.

Problem 

The traditional file transmission mechanism is as follows: 

1.         A file is divided into equal length packets. 
2.         Transmitter sends packets one by one.
3.         Receiver acknowledges each received packet as well as lost ones.
4.         Transmitter re-sends packets lost.

       
Now consider a case where a server is to distribute data to multiple receivers, the content can be operating system updates or media files, anything.

Using the traditional method, not only will the server have to keep a duplex communication with the clients, it will also have to maintain a list of which client got which packets, in order to transmit lost ones again.
       


Imagine you are a part of a NASA expedition on a mission to Mars, despite of the very high computing power, the connection to earth is very lossy, many of the packets sent to you are lost, and you cannot present any feedback of which packets to be re-transmitted.

Solution

In a digital fountain, it doesn't matter which packets are received and which are lost, it also doesn't matter the order of received packets.

The server transformers the data into unlimited number of encoded chunks, then the client can reassemble the data given enough number of chunks, regardless of which ones were get and which ones were missed.
        
That's why it was called a fountain, you don't care which drops you get from the fountain, as long as you get enough drops to fill your bottle.

How it works

Encoding

Decoding

 

Example  

Data

Split into k = 6 parts

 

One drop is generated by XORing parts 1, 2 and 3

 

Another drop is generated by XORing part 1, 5 and 6

Drop generation can be repeated over and over again, until necessary

Decode

This is the same as solving an equation system with k unknowns (data parts). Every drop is an equation of the system.

very well, so, if we know the file is divided into K blocks, then we need K drops (equations), right?

wrong! with only k drops, in the most favorable case, decoding is possible only 30% of times.

To increase the probability to decode, it is necessary to collect more than k drops, The number of excess drops is the overhead; the bigger the overhead, the higher the decoding probability.

Note that the overhead is independent of k: 20 excess drops to get 10^-6 failure probability for any k (then better if K is large). 

Code Architecture  

The folder Algorithm is where the implementation logic is, MathHelper is used to solve the linear equations using Gauss–Jordan elimination, Server is a self-hosted WCF service exposing the algorithm, Client is the WPF application that receives the drops into a goblet then decodes it into original file.

Code Explanation

LubyTransform.Encode (The Server part)

At first there's the initialization, we split the data file into blocks.
Notic the variable degree, it determines the maximum number of blocks to be combined.
Here degree is equal to number of generated blocks divided by 2.

   

 public class Encode : IEncode
    {
        #region Member Variables

        readonly IList<byte[]> blocks;
        readonly int degree;
        readonly Random rand;
        readonly int fileSize;
        const int chunkSize = 2;

        #endregion

        #region Constructor

        public Encode(byte[] file)
        {
            rand = new Random();
            fileSize = file.Length;
            blocks = CreateBlocks(file);
            degree = blocks.Count() / 2;
            degree += 2;
        }

        #endregion

Then we have the Encode() method itself

Drop IEncode.Encode()
        {
            int[] selectedParts = GetSelectedParts();
            byte[] data;

            if (selectedParts.Count() > 1)
            {
                data = CreateDropData(selectedParts, blocks, chunkSize);
            }
            else
            {
                data = blocks[selectedParts[0]];
            }

            return new Drop { SelectedParts = selectedParts, Data = data };
        }

simple enough, we choose some blocks randomly (degree is our max number of blocks to be chosen) and combine them, generating the drop data. 

         private byte[] CreateDropData(IList<int> selectedParts, IList<byte[]> blocks, int chunkSize)
        {
            var data = new byte[chunkSize];

            for (int i = 0; i < chunkSize; i++)
            {
                data[i] = XOROperation(i, selectedParts, blocks);
            }

            return data;
        }

        private byte XOROperation(int idx, IList<int> selectedParts, IList<byte[]> blocks)
        {
            var selectedBlock = blocks[selectedParts[0]];
            byte result = selectedBlock[idx];

            for (int i = 1; i < selectedParts.Count; i++)
            {
                result ^= blocks[selectedParts[i]][idx];
            }

            return result;
        } 

The combination is done by XORing the parts together, Note that the number of blocks chosen is different each time a Drop is requested. Each Drop contains the data generated from combination, along with a list of which blocks were combined. 

    public class Drop
    {
        public IList<int> SelectedParts { get; set; }
        public byte[] Data { get; set; }
    }

LubyTransform.Decode (The Client part, putting it all together)

The first thing we do is collect drops, we need K+overhead drops

private string ReceiveMessage()
        {
            var blocksCount = encodeServiceClient.GetNumberOfBlocks();
            var fileSize = encodeServiceClient.GetFileSize();
            var chunkSize = encodeServiceClient.GetChunkSize();
            IList<Drop> goblet = new List<Drop>();

            for (int i = 0; i < blocksCount + overHead; i++)
            {
                var drop = encodeServiceClient.Encode();
                goblet.Add(drop);
            }

            var fileData = _decoder.Decode(goblet, blocksCount, chunkSize, fileSize);
            return Encoding.ASCII.GetString(fileData);
        }
 

From these drops we construct an Augmented Matrix, to be solved by Gauss–Jordan elimination

        byte[] IDecode.Decode(IList<Drop> goblet, int blocksCount, int chunkSize, int fileSize)
        {
            var matrix = BuildMatrix(goblet, blocksCount, chunkSize);
            matrixSolver.Solve(matrix);
            int columnsCount = matrix.GetLength(1);
            byte[] result = new byte[fileSize];

            for (int i = 0; i < result.Length; i++)
            {
                result[i] = (byte)matrix[i, columnsCount - 1];
            }

            return result;
        } 

and that's it, the file is reconstructed.

How to Use the application

1. Start visual studio under administrator privilege.
2. Set Server.Host as the startup project, make sure its up and running.
3. Start a new instance of the Client.Receiver project (right click project-->Debug-->start new instance).
4. Press the Start Receiving button, and you should get the message that was stored on the server.

Points of Interest

• The XORing of blocks is a really expensive process, note the CreateDropData() function, each time a drop is requested, we are looping ChunkSize times. In this particular demo I've set the ChunkSize to 2, but in a real life application it will be no less than 4 Kb, maybe 16 Kb even, that will take an imaginable time! 

• The Gauss-Jordan algorithm executes in O(mnm), that's roughly O(n³). 

Conclusion

As always, I hope I've delivered a clear explanation. If you have a comment\question about the implementation\Code structure please feel free to contact me ;]

Charts were created using http://zwibbler.com/

References  

• Efficient Fountain Codes for Medium Blocklengths By Oliver G. H. Madge and David J. C. MacKay
• Optimal Degree Distributions for LT Codes in Small Cases By Tuomas Tirronen
• Fountain Codes By Daniel Broudy, Peregrine Badger, Renzo Lucioni and Vepul Shekhawat
• DropBox, CloudStorm, SiNBD: Distributed Storage, Digital Fountains and Virtual Devices
• Nick Johnsonz: Damn Cool Algorithms 

History

• 24 Aug 2012 Followed Paulo Zemek's advice of using IList instead of IEnumerable.
• 21 Jul 2012  Initial Release