Click here to Skip to main content
15,867,686 members
Articles / Desktop Programming / WPF

Your Digital Fountain

Rate me:
Please Sign up or sign in to vote.
4.97/5 (45 votes)
28 Nov 2014CPOL4 min read 87.7K   215   71   35
Reliable transmission of bulk data over lossy connection without worrying about packets loss

Download source 

Image 1Image 2

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.
       
Image 3

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.

Image 4

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
Image 5

Decoding

Image 6 

Example  

Data

Image 7

Split into k = 6 parts

Image 8 

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

Image 9 

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

Image 10

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

 

Decode

Image 11

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.

Image 12

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  

Image 13

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.

 

   

C#
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

 

 

C#
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. 

C#
 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. 

C#
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

C#
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

C#
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). 

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)


Written By
Software Developer
Egypt Egypt
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

Comments and Discussions

 
Questiondrop, and sent and received file Pin
Member 1170860521-May-15 2:53
Member 1170860521-May-15 2:53 
AnswerRe: drop, and sent and received file Pin
Omar Gameel Salem22-May-15 14:53
professionalOmar Gameel Salem22-May-15 14:53 
GeneralRe: drop, and sent and received file Pin
Member 1170860526-May-15 2:15
Member 1170860526-May-15 2:15 
GeneralRe: drop, and sent and received file Pin
Omar Gameel Salem26-May-15 14:09
professionalOmar Gameel Salem26-May-15 14:09 
GeneralRe: drop, and sent and received file Pin
Member 1170860526-May-15 20:10
Member 1170860526-May-15 20:10 
QuestionMessage "Please make sure the WCF service is running" Pin
Member 1127064827-Nov-14 22:30
Member 1127064827-Nov-14 22:30 
AnswerRe: Message "Please make sure the WCF service is running" Pin
Omar Gameel Salem28-Nov-14 17:59
professionalOmar Gameel Salem28-Nov-14 17:59 
GeneralRe: Message "Please make sure the WCF service is running" Pin
Member 1127064829-Nov-14 21:58
Member 1127064829-Nov-14 21:58 
Questionthe code (as of 24 Aug 2012) is broken Pin
rost.bel7-Jun-14 21:59
rost.bel7-Jun-14 21:59 
AnswerRe: the code (as of 24 Aug 2012) is broken Pin
Omar Gameel Salem9-Jun-14 0:35
professionalOmar Gameel Salem9-Jun-14 0:35 
AnswerRe: the code (as of 24 Aug 2012) is broken Pin
Member 1127064828-Nov-14 2:51
Member 1127064828-Nov-14 2:51 
GeneralMy vote of 5 Pin
Savalia Manoj M16-Aug-13 2:32
Savalia Manoj M16-Aug-13 2:32 
Questionsoliton distribution? Pin
GusBricker20-Jul-13 22:48
GusBricker20-Jul-13 22:48 
AnswerRe: soliton distribution? Pin
Omar Gameel Salem20-Jul-13 22:55
professionalOmar Gameel Salem20-Jul-13 22:55 
GeneralMy vote of 5 Pin
Christoph Keller10-Jan-13 2:08
Christoph Keller10-Jan-13 2:08 
GeneralMy vote of 5 Pin
Christian Amado24-Aug-12 16:48
professionalChristian Amado24-Aug-12 16:48 
GeneralMy vote of 5 Pin
Nicolas Gordillo24-Aug-12 4:51
Nicolas Gordillo24-Aug-12 4:51 
GeneralMy vote of 5 Pin
Yusuf Uzun16-Aug-12 1:06
Yusuf Uzun16-Aug-12 1:06 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA8-Aug-12 5:26
professionalȘtefan-Mihai MOGA8-Aug-12 5:26 
QuestionDecoding and failure ratio Pin
Galatei24-Jul-12 10:32
Galatei24-Jul-12 10:32 
AnswerRe: Decoding and failure ratio Pin
Omar Gameel Salem24-Jul-12 23:18
professionalOmar Gameel Salem24-Jul-12 23:18 
QuestionAre these references for this processes Pin
MicroImaging23-Jul-12 18:49
MicroImaging23-Jul-12 18:49 
AnswerRe: Are these references for this processes Pin
Omar Gameel Salem23-Jul-12 22:12
professionalOmar Gameel Salem23-Jul-12 22:12 
GeneralPerhaps a comparison would be in order... Pin
Andrew Rissing23-Jul-12 8:25
Andrew Rissing23-Jul-12 8:25 
GeneralRe: Perhaps a comparison would be in order... Pin
Omar Gameel Salem23-Jul-12 12:14
professionalOmar Gameel Salem23-Jul-12 12:14 

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

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