ostore.archive.interleaved
Class Interleaved

java.lang.Object
  |
  +--ostore.archive.Erasure
        |
        +--ostore.archive.interleaved.Interleaved

public class Interleaved

extends Erasure

This class extends class Erasure. Interleaved Reed-Solomon is a form of erasure codes and therefore inherits the ability to encode/decode and update an object.

Version:

$Id: Interleaved.java,v 1.11 2003/11/17 23:52:43 emilong Exp $

Author:

Hakim Weatherspoon

Field Summary

protected Cauchy	_cauchy
protected int[]	_cauchy_fragments
protected int[]	_cauchy_message
protected int	_encodeSize encodeSize is the max number of words in any one message encoded by Cauchy
protected int[]	_fragments
static int	_headerSize
protected int	_interleaveFactor interleaveFactor is the number of encode fragments per dissemination fragments INV: interleaveFactor = ceil(Original Message size / encodeSize)
protected int[]	_message
protected int	_Plen Plen is the size in words of a dissemination fragment.
protected int	_Plentot Plentot is the size int words of a dissemination fragment (with index)
protected int[]	_rec_fragments
protected int[]	_rec_message
protected static boolean	DEBUG
static int	ENCODETYPE

Fields inherited from class ostore.archive.Erasure

_fragmentDataLength, _fragmentIndexLength, _fragmentTotalLength, _inverseRate, _node_id, _numFragments, _numMessageFragments, _numRedundantFragments, _size, _verify, sizeOfLong

Constructor Summary

Interleaved(int size, int numFragments, int rate, int encodeBytes, boolean verify, NodeId node_id)
Constructor.

Method Summary

static int	calcBlockSize(int blockSize, int numFragments, int rate, int encodeBytes) returns the message size corresponding to the input block size
void	decode(int[] rec_pckts, int Nrec, int[] rec_message, byte[] data, Stats stat) decodes an object using an erasure code.
void	encode(byte[] bytes, int[] msg, int[] intFrags, Stats stat) encodes an object using an erasure code.
protected void	extractFragments(int[] eFrag, int[] dFrag, int interIndex, int eSize, int dSize, int numFrag, int headerSize) copies fragments from a larger array of them to a smaller one
protected void	extractMessage(int[] msg, int[] whole_msg, int interIndex, int msgSize, int partSize) copies a message from a larger message, starting at an offset specified by interIndex
int	fragmentDataLength() fragmentDataLength is the fragment length in bytes of each fragment excluding the overhead for storing the index.
int	fragmentIndexLength() fragmentIndexLength is the overhead for storing the index.
int	fragmentTotalLength() fragmentTotalLength is the fragment length in bytes including the overhead for storing the index after encoding.
int	getBlockSize(int blockSize, int numFragments, int rate) returns the message size corresponding to the input block size NOTE: this function assumes encodeSize has already been set
int	getEncodeType() returns the encode type of this Erasure coder
int	getFragmentArrayLength() getFragmentArrayLength returns the length of the Fragment array divisible by Erasure.sizeOfLong.
int	getMsgArrayLength() getMsgArrayLength returns the length of the msg array divisible by Erasure.sizeOfLong.
int	getNumFragments() numFragments returns the number of fragments after encoding (without loss of fragments).
protected boolean	initialize() Initialize all class/instance variables.
protected void	integrateFragments(int[] eFrag, int[] dFrag, int interIndex, int eSize, int dSize, int numFrag, int headerSize) copies fragments from a smaller array of them to a larger one
protected void	integrateMessage(int[] msg, int[] whole_msg, int interIndex, int msgSize, int partSize) copies a message from a smaller message into a larger one in a manner specified by interIndex
int	loseFragments(int[] fragments, int[] rec_fragments, double keepRate, int[] pNrec) loseFragments Decide which fragments to keep randomly.
static int	min(int in1, int in2)
int	numMessageFragments() numMessageFragments returns the message number of fragments.
int	numRedundantFragments() numRedundantFragments returns the redundant number of fragments.

Methods inherited from class ostore.archive.Erasure

compareMsg, getBlockSize, getErasure, getInverseRate, getMsg, getSize, instanceRandom, instanceRandomContains, instanciateRandom

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ENCODETYPE

public static final int ENCODETYPE

See Also:

Constant Field Values

DEBUG

protected static final boolean DEBUG

See Also:

Constant Field Values

_cauchy

protected Cauchy _cauchy

_message

protected int[] _message

_rec_message

protected int[] _rec_message

_cauchy_message

protected int[] _cauchy_message

_fragments

protected int[] _fragments

_rec_fragments

protected int[] _rec_fragments

_cauchy_fragments

protected int[] _cauchy_fragments

_interleaveFactor

protected int _interleaveFactor

interleaveFactor is the number of encode fragments per dissemination fragments INV: interleaveFactor = ceil(Original Message size / encodeSize)

_Plen

protected int _Plen

Plen is the size in words of a dissemination fragment. INV: Plen = interleaveFactor * _cauchy.Plen

_Plentot

protected int _Plentot

Plentot is the size int words of a dissemination fragment (with index)

_encodeSize

protected int _encodeSize

encodeSize is the max number of words in any one message encoded by Cauchy

_headerSize

public static final int _headerSize

See Also:

Constant Field Values

Constructor Detail

Interleaved

public Interleaved(int size,
                   int numFragments,
                   int rate,
                   int encodeBytes,
                   boolean verify,
                   NodeId node_id)

Constructor.

Parameters:

size - == size (in bytes) of object to encode/decode.

numFragments - == number of fragments to generate.

rate - == rate of encoding

encodeBytes - == max number of bytes to encode using Cauchy

Method Detail

min

public static final int min(int in1,
                            int in2)

initialize

protected boolean initialize()

Initialize all class/instance variables. all variables are based on size of original object.

extractMessage

protected void extractMessage(int[] msg,
                              int[] whole_msg,
                              int interIndex,
                              int msgSize,
                              int partSize)

copies a message from a larger message, starting at an offset specified by interIndex

Parameters:

msg - == smaller message to be created

whole_msg - == larger message from which smaller message is taken

interIndex - == current index of interleaving

msgSize - == size, in words, of msg

partSize - == size, in words, of pieces of whole_msg NOTE: for all of whole_msg to survive, partSize <= msgSize

integrateMessage

protected void integrateMessage(int[] msg,
                                int[] whole_msg,
                                int interIndex,
                                int msgSize,
                                int partSize)

copies a message from a smaller message into a larger one in a manner specified by interIndex

Parameters:

msg - == smaller message, which is the source

whole_msg - == larger message, which is the destination

interIndex - == current index of interleaving

msgSize - == size, in words, of msg

partSize - == size, in words, of pieces of whole_msg NOTE: for all of whole_msg to survive, partSize <= msgSize

extractFragments

protected void extractFragments(int[] eFrag,
                                int[] dFrag,
                                int interIndex,
                                int eSize,
                                int dSize,
                                int numFrag,
                                int headerSize)

copies fragments from a larger array of them to a smaller one

Parameters:

eFrag - == smaller array of fragments to be created

dFrag - == larger array of fragments, which is the source

interIndex - == current index of interleaving

eSize - == size, in words, of smaller fragments

dSize - == size, in words, of larger fragments

numFrag - == number of fragments to be stored in frag

headerSize - == size, in words, headers

integrateFragments

protected void integrateFragments(int[] eFrag,
                                  int[] dFrag,
                                  int interIndex,
                                  int eSize,
                                  int dSize,
                                  int numFrag,
                                  int headerSize)

copies fragments from a smaller array of them to a larger one

Parameters:

eFrag - == smaller array of fragments, which is the source

dFrag - == larger array of fragments, which is the destination

interIndex - == current index of interleaving

eSize - == size, in words, of smaller fragments

dSize - == size, in words, of larger fragments

numFrag - == number of fragments to be stored in frag

headerSize - == size, in words, headers

getEncodeType

public int getEncodeType()

returns the encode type of this Erasure coder

Specified by:

getEncodeType in class Erasure

Returns:

the encode type of this Erasure coder.

calcBlockSize

public static int calcBlockSize(int blockSize,
                                int numFragments,
                                int rate,
                                int encodeBytes)

returns the message size corresponding to the input block size

Parameters:

blockSize - == initial block size

encodeBytes - == max encoding size

Returns:

return == effective size of a block to be encoded

getBlockSize

public int getBlockSize(int blockSize,
                        int numFragments,
                        int rate)

returns the message size corresponding to the input block size NOTE: this function assumes encodeSize has already been set

Specified by:

getBlockSize in class Erasure

Parameters:

blockSize - = target blockSize (this is the size in bytes of the data to be encoded).

numFragments - = total number of fragments to encode data.

rate - = inverse rate of encoding to encode data.

Returns:

the message in bytes that the data must be when passed to the Erasure encoder. This size correspond to the input blockSize, numFragments, and inverseRate.

getFragmentArrayLength

public int getFragmentArrayLength()

Description copied from class: Erasure

getFragmentArrayLength returns the length of the Fragment array divisible by Erasure.sizeOfLong.

Specified by:

getFragmentArrayLength in class Erasure

Returns:

the length of the Fragment array divisible by Erasure.sizeOfLong.

getMsgArrayLength

public int getMsgArrayLength()

Description copied from class: Erasure

getMsgArrayLength returns the length of the msg array divisible by Erasure.sizeOfLong.

Specified by:

getMsgArrayLength in class Erasure

Returns:

the length of the msg array divisible by Erasure.sizeOfLong.

encode

public void encode(byte[] bytes,
                   int[] msg,
                   int[] intFrags,
                   Stats stat)
            throws ErasureEncodeException

encodes an object using an erasure code. FIXME!!!

Specified by:

encode in class Erasure

Parameters:

bytes - = original msg before encoding (in array of byte form).

msg - = original msg before encoding (in array of int form).

stat - = a Stats object which contains the time to encode object in milliseconds.

Returns:

resulting intFrags from encoding msg (in an array of int form).

ErasureEncodeException

loseFragments

public int loseFragments(int[] fragments,
                         int[] rec_fragments,
                         double keepRate,
                         int[] pNrec)

loseFragments Decide which fragments to keep randomly. INVARIANT: you have already called encode.

Overrides:

loseFragments in class Erasure

Parameters:

fragments - == original msg before encoding.

rec_fragments - == received msg after reception and decoding.

keepRate - == percentage of fragments to keep after reception.

pNrec - == number of received fragments, this is returned.

Returns:

return == number of received.

decode

public void decode(int[] rec_pckts,
                   int Nrec,
                   int[] rec_message,
                   byte[] data,
                   Stats stat)
            throws ErasureDecodeException

decodes an object using an erasure code.

Specified by:

decode in class Erasure

Parameters:

rec_pckts - == TODO

Nrec - == TODO

rec_message - == received msg after reception and decoding.

data - == TODO

stat - == TODO

Returns:

return == time to decode object in milliseconds.

ErasureDecodeException

getNumFragments

public int getNumFragments()

numFragments returns the number of fragments after encoding (without loss of fragments).

Specified by:

getNumFragments in class Erasure

Returns:

return == number of encoded fragments.

numMessageFragments

public int numMessageFragments()

numMessageFragments returns the message number of fragments.

Specified by:

numMessageFragments in class Erasure

Returns:

return == the number of message fragments.

numRedundantFragments

public int numRedundantFragments()

numRedundantFragments returns the redundant number of fragments.

Specified by:

numRedundantFragments in class Erasure

Returns:

return == the number of message fragments.

fragmentDataLength

public int fragmentDataLength()

fragmentDataLength is the fragment length in bytes of each fragment excluding the overhead for storing the index.

Specified by:

fragmentDataLength in class Erasure

Returns:

return == data length for each fragment.

fragmentIndexLength

public int fragmentIndexLength()

fragmentIndexLength is the overhead for storing the index.

Specified by:

fragmentIndexLength in class Erasure

Returns:

return == length of index for each fragment in bytes.

fragmentTotalLength

public int fragmentTotalLength()

fragmentTotalLength is the fragment length in bytes including the overhead for storing the index after encoding.

Specified by:

fragmentTotalLength in class Erasure

Returns:

return == total length of each fragment in bytes.