Click here to Skip to main content
Click here to Skip to main content

Your Digital Fountain

, 23 Aug 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
Reliable transmission of bulk data over lossy connection without worrying about packets loss

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(n3). 

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  

History

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Omar Gameel Salem
Software Developer
Australia Australia
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms and automation.
 
Amateur guitarist/ keyboardist, squash player.
 
If you have a question\suggestion about one of my articles, or you want an algorithm implemented in C#, feel free to contact me.
Follow on   LinkedIn

Comments and Discussions

 
Questionthe code (as of 24 Aug 2012) is broken Pinmemberrost.bel7-Jun-14 21:59 
AnswerRe: the code (as of 24 Aug 2012) is broken PinmemberOmar Gameel Salem9-Jun-14 0:35 
GeneralMy vote of 5 PinmemberSavalia Manoj M16-Aug-13 2:32 
Questionsoliton distribution? PinmemberMember 924594520-Jul-13 22:48 
AnswerRe: soliton distribution? PinmemberOmar Gameel Salem20-Jul-13 22:55 
GeneralMy vote of 5 PinmemberChristoph Keller10-Jan-13 2:08 
GeneralMy vote of 5 PinmemberChristian Amado24-Aug-12 16:48 
GeneralMy vote of 5 PinmemberNicolas Gordillo24-Aug-12 4:51 
GeneralMy vote of 5 PinmemberYusuf Uzun16-Aug-12 1:06 
GeneralMy vote of 5 PinmemberMihai MOGA8-Aug-12 5:26 
QuestionDecoding and failure ratio PinmemberGalatei24-Jul-12 10:32 
AnswerRe: Decoding and failure ratio PinmemberOmar Gamil24-Jul-12 23:18 
QuestionAre these references for this processes PinmemberMicroImaging23-Jul-12 18:49 
AnswerRe: Are these references for this processes PinmemberOmar Gamil23-Jul-12 22:12 
GeneralPerhaps a comparison would be in order... PinmemberAndrew Rissing23-Jul-12 8:25 
GeneralRe: Perhaps a comparison would be in order... PinmemberOmar Gamil23-Jul-12 12:14 
GeneralRe: Perhaps a comparison would be in order... PinmemberAndrew Rissing23-Jul-12 15:31 
GeneralRe: Perhaps a comparison would be in order... PinmemberOmar Gamil23-Jul-12 22:10 
GeneralRe: Perhaps a comparison would be in order... PinmemberAndrew Rissing24-Jul-12 3:51 
GeneralMy vote of 4 PinmemberSouthmountain21-Jul-12 10:38 
GeneralXOROperation... 2 problems PinmvpPaulo Zemek21-Jul-12 5:07 
GeneralRe: XOROperation... 2 problems PinmemberOmar Gamil21-Jul-12 5:29 
GeneralRe: XOROperation... 2 problems PinmvpPaulo Zemek21-Jul-12 5:48 
SuggestionCode blocks PinmvpMeshack Musundi20-Jul-12 22:46 
GeneralMy vote of 5 PinmemberHexxellor20-Jul-12 20:13 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.141022.2 | Last Updated 24 Aug 2012
Article Copyright 2012 by Omar Gameel Salem
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid