ostore.archive.cauchy
Class Cauchy

java.lang.Object
  |
  +--ostore.archive.Erasure
        |
        +--ostore.archive.cauchy.Cauchy

public class Cauchy

extends Erasure

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

Version:

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

Author:

Hakim Weatherspoon

Field Summary

protected int[]	_fragments
protected int[]	_message
protected Parameters	_p
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

Cauchy(int size, int numFragments, int inverseRate, boolean verify, NodeId node_id)
CONSTRUCTOR

Method Summary

static int	calcBlockSize(int blockSize, int numFragments, int inverseRate) calcBlockSize returns the message size corresponding to the input block size.
static int	calcLfield(int blockSize, int numFragments, int inverseRate) Calculates the best Lfield for a given blockSize.
static int	calcNsegs(int blockSize, int numFragments, int inverseRate, int Lfield) Calculates the best Nsegs for a given blockSize.
boolean	compareMsg(int[] msg, int[] rec_msg) compareMsg compares the original msg with the encoded/decoded message.
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) encode encodes an object using an erasure code.
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 inverseRate) getBlockSize returns the message size corresponding to the input block size.
int	getEncodeType() 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(int size, int numMsgFragments) Initialize all class/instance variables.
void	initializeForEncoding() Prepares this Cauchy object to encode a block.
int	Lfield() Lfield returns the length of the Galois Field.
int	Mlen() Mlen returns the length of the message, in words.
int	Nseg() Nseg returns the number of segments in each fragment.
int	numMessageFragments() numMessageFragments returns the message number of fragments.
int	numRedundantFragments() numRedundantFragments returns the redundant number of fragments.
int	Plen() Plen returns the length of the packets, in words.
int	Plentot() Plentot returns the length of the packets, in words, including the index.

Methods inherited from class ostore.archive.Erasure

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

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

protected static final boolean DEBUG

See Also:

Constant Field Values

ENCODETYPE

public static final int ENCODETYPE

See Also:

Constant Field Values

_p

protected Parameters _p

_message

protected int[] _message

_rec_message

protected int[] _rec_message

_fragments

protected int[] _fragments

_rec_fragments

protected int[] _rec_fragments

Constructor Detail

Cauchy

public Cauchy(int size,
              int numFragments,
              int inverseRate,
              boolean verify,
              NodeId node_id)

CONSTRUCTOR

Parameters:

size - == size, in bytes, of the block to be encoded

numFragments - == number of total fragments to produce

inverseRate - == inverseRate of encoding

Method Detail

initialize

protected boolean initialize(int size,
                             int numMsgFragments)

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

Parameters:

size - == set size of object to encode/decode.

numMsgFragments - == number of message fragments.

calcLfield

public static int calcLfield(int blockSize,
                             int numFragments,
                             int inverseRate)

Calculates the best Lfield for a given blockSize.

Parameters:

blockSize - == size in bytes of the block to be encoded.

numFragments - == number of fragments.

inverseRate - == inverse of inverseRate of encoding.

Returns:

return == best Lfield for a given blockSize.

calcNsegs

public static int calcNsegs(int blockSize,
                            int numFragments,
                            int inverseRate,
                            int Lfield)

Calculates the best Nsegs for a given blockSize.

Parameters:

blockSize - == size in bytes of the block to be encoded.

numFragments - == number of fragments.

inverseRate - == inverse of inverseRate of encoding.

Lfield - == best Lfield for the other parameters.

Returns:

return == best Nsegs for a given blocksize.

calcBlockSize

public static int calcBlockSize(int blockSize,
                                int numFragments,
                                int inverseRate)

calcBlockSize returns the message size corresponding to the input block size.

Parameters:

blockSize - == size in bytes of the block to be encoded.

numFragments - == number of fragments.

inverseRate - == inverse of inverseRate of encoding.

Returns:

return == the message size corresponding to the input block size.

getEncodeType

public int getEncodeType()

getEncodeType returns the encode type of this Erasure coder.

Specified by:

getEncodeType in class Erasure

Returns:

return == the encode type of this Erasure coder.

getBlockSize

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

getBlockSize returns the message size corresponding to the input block size.

Specified by:

getBlockSize in class Erasure

Parameters:

blockSize - == size of block in bytes.

numFragments - == total number of fragments for block.

inverseRate - = inverseRate of encoding.

Returns:

return == the message size corresponding to the input block size.

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.

initializeForEncoding

public void initializeForEncoding()
                           throws ErasureEncodeException

Prepares this Cauchy object to encode a block. Calling this method inside of encode() allows one Cauchy object to encode multiple blocks serially, rather than just one.

ErasureEncodeException

encode

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

encode encodes an object using an erasure code.

Specified by:

encode in class Erasure

Parameters:

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

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

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

Returns:

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

ErasureEncodeException

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 - == received fragments after encoding.

Nrec - == number of fragments received.

rec_message - == TODO

data - == TODO

stat - == time to decode object in milliseconds.

Returns:

return == received msg after reception and decoding (in array of ints form).

ErasureDecodeException

compareMsg

public boolean compareMsg(int[] msg,
                          int[] rec_msg)

compareMsg compares the original msg with the encoded/decoded message.

Parameters:

msg - == original msg before encoding.

rec_msg - == received msg after reception and decoding. INVARIANT: _size is defined at constructor (size in bytes);

Returns:

return==true if original and received/decoded message are equal; otherwise, false.

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.

Nseg

public int Nseg()

Nseg returns the number of segments in each fragment.

Returns:

return==the number of segments in each fragment.

Lfield

public int Lfield()

Lfield returns the length of the Galois Field.

Returns:

return==the length of the Galois Field.

Mlen

public int Mlen()

Mlen returns the length of the message, in words.

Returns:

return == the length of the message, in words.

Plen

public int Plen()

Plen returns the length of the packets, in words.

Returns:

return == the length of the packet in words, excluding index.

Plentot

public int Plentot()

Plentot returns the length of the packets, in words, including the index.

Returns:

return == the length of the packets, in words, including index.