Download source
Implementation of Luby transform Code in C#, with Demo application in WPF and WCF.
The traditional file transmission mechanism is as follows:
- A file is divided into equal length packets.
- Transmitter sends packets one by one.
- Receiver acknowledges each received packet as well as lost ones.
- 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.
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.
Encoding
Decoding
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).
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.
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.
- Start visual studio under administrator privilege.
- Set Server.Host as the startup project, make sure its up and running.
- Start a new instance of the Client.Receiver project (right click project-->Debug-->start new instance).
- Press the Start Receiving button, and you should get the message that was stored on the server.
- 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).
History
- 24 Aug 2012 Followed Paulo Zemek's advice of using
IList
instead of IEnumerable
. - 21 Jul 2012 Initial Release