Click here to Skip to main content
11,505,486 members (58,685 online)
Click here to Skip to main content

Your Digital Fountain

, 28 Nov 2014 CPOL 30.2K 215 68
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). 

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, AI, machine learning and nlp.

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

 
Questiondrop, and sent and received file Pin
Member 1170860521-May-15 2:53
memberMember 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
memberMember 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
memberMember 1170860526-May-15 20:10 
QuestionMessage "Please make sure the WCF service is running" Pin
Member 1127064827-Nov-14 22:30
memberMember 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
memberMember 1127064829-Nov-14 21:58 
Questionthe code (as of 24 Aug 2012) is broken Pin
rost.bel7-Jun-14 21:59
memberrost.bel7-Jun-14 21:59 
AnswerRe: the code (as of 24 Aug 2012) is broken Pin
Omar Gameel Salem9-Jun-14 0:35
memberOmar Gameel Salem9-Jun-14 0:35 
AnswerRe: the code (as of 24 Aug 2012) is broken Pin
Member 1127064828-Nov-14 2:51
memberMember 1127064828-Nov-14 2:51 
GeneralMy vote of 5 Pin
Savalia Manoj M16-Aug-13 2:32
memberSavalia Manoj M16-Aug-13 2:32 
Questionsoliton distribution? Pin
Member 924594520-Jul-13 22:48
memberMember 924594520-Jul-13 22:48 
AnswerRe: soliton distribution? Pin
Omar Gameel Salem20-Jul-13 22:55
memberOmar Gameel Salem20-Jul-13 22:55 
GeneralMy vote of 5 Pin
Christoph Keller10-Jan-13 2:08
memberChristoph Keller10-Jan-13 2:08 
GeneralMy vote of 5 Pin
Christian Amado24-Aug-12 16:48
memberChristian Amado24-Aug-12 16:48 
GeneralMy vote of 5 Pin
Nicolas Gordillo24-Aug-12 4:51
memberNicolas Gordillo24-Aug-12 4:51 
GeneralMy vote of 5 Pin
Yusuf Uzun16-Aug-12 1:06
memberYusuf Uzun16-Aug-12 1:06 
GeneralMy vote of 5 Pin
Mihai MOGA8-Aug-12 5:26
memberMihai MOGA8-Aug-12 5:26 
QuestionDecoding and failure ratio Pin
Galatei24-Jul-12 10:32
memberGalatei24-Jul-12 10:32 
AnswerRe: Decoding and failure ratio Pin
Omar Gamil24-Jul-12 23:18
memberOmar Gamil24-Jul-12 23:18 
QuestionAre these references for this processes Pin
MicroImaging23-Jul-12 18:49
memberMicroImaging23-Jul-12 18:49 
AnswerRe: Are these references for this processes Pin
Omar Gamil23-Jul-12 22:12
memberOmar Gamil23-Jul-12 22:12 
GeneralPerhaps a comparison would be in order... Pin
Andrew Rissing23-Jul-12 8:25
memberAndrew Rissing23-Jul-12 8:25 
GeneralRe: Perhaps a comparison would be in order... Pin
Omar Gamil23-Jul-12 12:14
memberOmar Gamil23-Jul-12 12:14 
GeneralRe: Perhaps a comparison would be in order... Pin
Andrew Rissing23-Jul-12 15:31
memberAndrew Rissing23-Jul-12 15:31 
GeneralRe: Perhaps a comparison would be in order... Pin
Omar Gamil23-Jul-12 22:10
memberOmar Gamil23-Jul-12 22:10 
GeneralRe: Perhaps a comparison would be in order... Pin
Andrew Rissing24-Jul-12 3:51
memberAndrew Rissing24-Jul-12 3:51 
GeneralMy vote of 4 Pin
Southmountain21-Jul-12 10:38
memberSouthmountain21-Jul-12 10:38 
GeneralXOROperation... 2 problems Pin
Paulo Zemek21-Jul-12 5:07
mvpPaulo Zemek21-Jul-12 5:07 
GeneralRe: XOROperation... 2 problems Pin
Omar Gamil21-Jul-12 5:29
memberOmar Gamil21-Jul-12 5:29 
GeneralRe: XOROperation... 2 problems Pin
Paulo Zemek21-Jul-12 5:48
mvpPaulo Zemek21-Jul-12 5:48 
SuggestionCode blocks Pin
Meshack Musundi20-Jul-12 22:46
mvpMeshack Musundi20-Jul-12 22:46 
GeneralMy vote of 5 Pin
Hexxellor20-Jul-12 20:13
memberHexxellor20-Jul-12 20:13 
GeneralMy vote of 5 Pin
Shaunak De20-Jul-12 19:28
memberShaunak De20-Jul-12 19:28 

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 | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 28 Nov 2014
Article Copyright 2012 by Omar Gameel Salem
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid