NAME

Net::OnlineCode::Encoder - Rateless Forward Error Correction Encoder

SYNOPSIS

  use Net::OnlineCode ':xor'
  use Net::OnlineCode::Encoder;
  use strict;

  my ($message,$msg_size,$blocksize);

  my $blocks = int(0.5 + ($msg_size / $blocksize));
  my @blocks = map { substr $message, $_ * $blocksize, $blocksize }
                 (0.. $blocks -1);

  my $initial_rng = Net::OnlineCode::RNG->new;
  my $msg_id      = $rng->seed_random;
  my $encoder     = Net::OnlineCode::Encoder->new(
    mblocks     => $blocks,
    initial_rng => $rng,
    # ...
  );

  # Send initial parameters and $msg_id (rng seed) to receiver
  # ...

  # Send an infinite stream of packets to receiver
  while (1) {
    my $block_id = $rng->seed_random;
    my @xor_list = $encoder->create_check_block($rng);

    # XOR all blocks in xor_list together
    my $block = $blocks[shift @xor_list];
    fast_xor_strings(\$block, map { $blocks[$_] } @xor_list);

    # Send $msg_id, $block_id and (xored) $block to receiver
    # ...
  }

DESCRIPTION

This module implements the "encoder" side of the Online Code algorithm for rateless forward error correction. Refer to the the Net::OnlineCode documentation for the technical background.

The basic outline for how the encoder works is follows:

  • The user breaks the input message into a number of blocks

  • The user seeds a random number generator ("rng") and saves the seed value (as the "message ID")

  • The constructor uses the random number generator to compute some number of "auxiliary" blocks. Auxiliary blocks are the XOR of some number of message blocks

  • The user sends details such as file size, number of blocks and the random seed to the receiver

  • (using the same seed value and random number generator algorithm, the receiver can calculate which message blocks each auxiliary block is comprised of)

Once the initial stage is complete, the sender sends a number of check blocks to the receiver. Check blocks are the XOR of some number of message blocks and/or auxiliary blocks. The above example shows the sender sending an infinite stream of check blocks, but in practice only a finite number will be sent. Schemes for deciding how many check blocks to send can be based on:

  • the probability that the complete message can be decoded based on encoder parameters, assumed network packet loss rate and number of packets already sent;

  • the use of positive acknowledgements from the receiver; or

  • the use of negative acknowledgements from the receiver

Practical implementations will also have to account for the receiving host or network link going down as well as problems with ACK/NAK messages becoming lost, as well as dealing with network congestion. They may also have to enforce timeouts and methods for fixing the sending rate or for flow control in general. The implementation will also depend to a great degree on the nature of the transmission, such as whether it is over a TCP or UDP channel, whether it is unicast or multicast, the expected latency for acknowledgement packets and, in the case of multicast, the number of receivers. As a result, a complete protocol description is beyond the scope of this document.

The procedure for sending a single check block is as follows:

  • the user generates a new random number generator seed which will become the check block's block ID

  • the call to create_check_block uses the rng to create a random check block

  • the check block is comprised of the XOR of various randomly-selected message or auxiliary blocks

  • (using the same seed value and random number generator algorithm, the receiver can calculate which message and auxiliary blocks comprise the received check block)

  • the return value of create_check_block is a list of message blocks (auxiliary blocks being expanded into their component message blocks automatically)

  • the user XORs each of the message blocks returned to create the check block

  • the user sends the message ID (if multiple messages may be sent at once), the block ID and the check block contents

SEE ALSO

See Net::OnlineCode for background information on Online Codes.

This module is part of the GnetRAID project. For project development page, see:

  https://sourceforge.net/projects/gnetraid/develop

AUTHOR

Declan Malone, <idablack@users.sourceforge.net>

COPYRIGHT AND LICENSE

Copyright (C) 2013-2015 by Declan Malone

This package is free software; you can redistribute it and/or modify it under the terms of the "GNU General Public License" ("GPL").

The C code at the core of this Perl module can additionally be redistributed and/or modified under the terms of the "GNU Library General Public License" ("LGPL"). For the purpose of that license, the "library" is defined as the unmodified C code in the clib/ directory of this distribution. You are permitted to change the typedefs and function prototypes to match the word sizes on your machine, but any further modification (such as removing the static modifier for non-exported function or data structure names) are not permitted under the LGPL, so the library will revert to being covered by the full version of the GPL.

Please refer to the files "GNU_GPL.txt" and "GNU_LGPL.txt" in this distribution for details.

DISCLAIMER

This package is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the "GNU General Public License" for more details.