TreeTopology Class Reference
[Fountain master and slave nodes]

A class to maintain the n-way tree toplogy of slave Fountain nodes. More...

#include <TreeTopology.h>

List of all members.

Public Types

typedef std::map< NodeID,
FountainWireProtPtr > 		ChildNodeContainer
 Shorthand for accessing child Fountain nodes.
enum  { JOIN_TIMEOUT = 2, INCOMING_CONNECTION_TIMEOUT = 10, DEFAULT_CHILDREN_PER_NODE = 2 }
enum  TreeState
 Contains all the states the tree topology can have.

Public Member Functions

 TreeTopology (const NodeID &ID)
 Creates a new TreeTopology object which is empty and in the idle state by default.
 ~TreeTopology ()
 Destructor.
TreeState getState () const
 Get the tree state.
NodeID getAvailableParentNode () const
bool containsNode (const NodeID &node)
 Check if the topology already contains a node with the specified ID.
int addNodeToTree (const NodeID &ID)
 Add a Fountain node to the tree topology.
void handleLostChildRequest (ConstParseMsgPtr request, FountainWireProtPtr con)
 Handle a lostChild request.
void handleLostParentRequest (ConstParseMsgPtr request, FountainWireProtPtr con)
 Handle a lostParent request When a Fountain node in the tree topology loses one of its childConnections, it will connect to us and report the failure. This function is responsible for handling these requests.
int handleLostChild (const NodeID &childID)
 Handles a lost child node of the Master Fountain node.
bool overRecoveryTimeLimit ()
 Check if we're over the recovery time limit.
void finishRebuilding ()
 Sets the tree back to idle if the tree state is rebuild and more than rebuildTimeLimit seconds have elapsed since the rebuild started.
void finishJoin ()
 Sets the tree back to idle if the tree state is join and more than joinTimeLimit seconds have elapsed since the last node joined the tree topology.
int recoverTree (ChildNodeContainer &masterNodeChildren)
 Attempt to recover the tree from a node failure.
void rebuildTree (unsigned int degree=0)
 Rebuilds the tree topology from scratch.
void addTreeTopology (BambooLib::XMLElement *treeTopologyXML)
 Adds the current tree topology to an XMLElement.
unsigned int getTotalRecoveries () const
 Get the total number of tree topology recoveries.
unsigned int getTotalRebuilds () const
 Get the total number of tree topology rebuilds.
double getMaxRecoveryTime () const
 Get the maximum time to recover the tree topology.
double getMinRecoveryTime () const
 Get the minimum time to recover the tree topology.
double getAverageRecoveryTime () const
 Get the average time to recover the tree topology.

Static Public Member Functions

static const char * fountain_convert (TreeState t)
 Convert a TreeState into a c-string.

Private Types

typedef std::list< TreeNode > TreeContainer
 foo
typedef TreeContainer::iterator treeIterator
 makes it easier to use iterators for our tree container
typedef TreeContainer::const_iterator constTreeIterator
 makes it easier to use const_iterators for our tree container

Private Member Functions

bool isReadyToRecover ()
 Test of all the neighboring nodes of a lost node have contacted the master Fountain node.
int replaceNode (const treeIterator &lostNode, const treeIterator &replacementNode)
 Replaces a lost node in the tree with another node.
unsigned int getNumChildren (const constTreeIterator &node) const
 Get the number of child nodes any node in the tree has.
treeIterator findNode (const NodeID &node)
 Find a node in the tree topology based on its NodeID.
treeIterator getReplacementNode ()
 Get the replacement node from the tree.
treeIterator getParent (const NodeID &node)
 Get the parent of a node in the tree based on its NodeID.
treeIterator getChild (const constTreeIterator &parent, unsigned int childNumber)
 Get the child of a node in the tree based on the child's position relative to its parent.
treeIterator getLostNode ()
 Get the lost node of the tree topology.
int setState (TreeState s)
 Set the state of the tree topology.

Private Attributes

TreeContainer tree_
TreeState state_
Timer recoveryTimer_
Timer rebuildTimer_
Timer joinTimer_
NodeID myID_
unsigned int totalRecoveries_
double maxRecoveryTime_
double minRecoveryTime_
double totalRecoveryTime_
unsigned int totalRebuilds_
unsigned int numChildrenPerNode_

Friends

std::ostream & operator<< (std::ostream &output, const TreeTopology &tree)
 ostream operator

Detailed Description

A class to maintain the n-way tree toplogy of slave Fountain nodes.

The TreeTopology class is used by the master Fountain daemon to maintain the tree structure of all the nodes and to recover from a node faialures

Member Enumeration Documentation

anonymous enum
 

Enumerator:
JOIN_TIMEOUT  enum trick to simulate a static const member variable. See Bjarne Stroustrup's FAQ on why this is preferred in certain cases: http://public.research.att.com/~bs/bs_faq2.html#in-class
INCOMING_CONNECTION_TIMEOUT  enum trick to specify the number of seconds to wait for incoming messages from a incoming connection before timing out and disconnecting them
DEFAULT_CHILDREN_PER_NODE  The default number of children for each node in the tree topology.

Constructor & Destructor Documentation

TreeTopology::TreeTopology (  const NodeID &  ID  ) 
 

Creates a new TreeTopology object which is empty and in the idle state by default.

Parameters:
ID The ID of the master Fountain node who instantiated this TreeTopology object

Member Function Documentation

int TreeTopology::addNodeToTree (  const NodeID &  ID  ) 
 

Add a Fountain node to the tree topology.

Parameters:
ID The NodeID of the Fountain node to add
Returns:
SUCCESS if adding the node to the tree topology was successful

FAILURE otherwise

void TreeTopology::addTreeTopology (  BambooLib::XMLElement *  treeTopologyXML  ) 
 

Adds the current tree topology to an XMLElement.

Parameters:
treeTopologyXML a valid XMLElement that is part of a FountainMessage object
Precondition:
state_ is idle
Postcondition:
The tree topology is appended to the XMLElement given as a parameter

bool TreeTopology::containsNode (  const NodeID &  node  ) 
 

Check if the topology already contains a node with the specified ID.

Parameters:
node The NodeID of the node to test
Returns:
true if the node with NodeID node is in the tree topology

false if it is not

const char * TreeTopology::fountain_convert (  TreeState  t  )  [static]
 

Convert a TreeState into a c-string.

Returns:
a c-string containing the text representation of the TreeState t
Parameters:
t A TreeState

NodeID TreeTopology::getAvailableParentNode (   )  const
 

Brief Get the available parent node

Return values:
NodeID Returns the NodeID of the node in the tree with space available for a child node to join

double TreeTopology::getAverageRecoveryTime (   )  const [inline]
 

Get the average time to recover the tree topology.

Returns:
The average time to recover the tree topology

TreeTopology::treeIterator TreeTopology::getChild (  const constTreeIterator &  parent,
unsigned int  childNumber
)  [private]
 

Get the child of a node in the tree based on the child's position relative to its parent.

Parameters:
parent A valid NodeID already in the tree topology with at least 1 child node
childNumber A number between 0 and CHILDREN_PER_NODE
Returns:
An iterator pointing to the child

tree.end() if the parent node was not found or no child exists for that node at the specified position

TreeTopology::treeIterator TreeTopology::getLostNode (   )  [private]
 

Get the lost node of the tree topology.

Returns:
An iterator to the node who's TreeNodeState is lost

tree.end() if the TreeTopology::state is not recovery or if no node can be found that is lost

double TreeTopology::getMaxRecoveryTime (   )  const [inline]
 

Get the maximum time to recover the tree topology.

Returns:
The maximum time to recover the tree topology

double TreeTopology::getMinRecoveryTime (   )  const [inline]
 

Get the minimum time to recover the tree topology.

Returns:
The minimum time to recover the tree topology

unsigned int TreeTopology::getNumChildren (  const constTreeIterator &  node  )  const [private]
 

Get the number of child nodes any node in the tree has.

Returns:
A number between 0 and CHILDREN_PER_NODE

TreeTopology::treeIterator TreeTopology::getParent (  const NodeID &  node  )  [private]
 

Get the parent of a node in the tree based on its NodeID.

Parameters:
node A valid NodeID already in the tree topology
Returns:
An iterator pointing to the parent of the node

tree.end() if no parent was found

TreeTopology::treeIterator TreeTopology::getReplacementNode (   )  [private]
 

Get the replacement node from the tree.

Returns:
An iterator pointing to the replacement node

tree.end() if no replacement node can be found

TreeState TreeTopology::getState (   )  const [inline]
 

Get the tree state.

Returns:
The current TreeState of the tree topology

unsigned int TreeTopology::getTotalRebuilds (   )  const [inline]
 

Get the total number of tree topology rebuilds.

Returns:
The total number of tree topology rebuilds

unsigned int TreeTopology::getTotalRecoveries (   )  const [inline]
 

Get the total number of tree topology recoveries.

Returns:
The total number of tree topology recoveries

int TreeTopology::handleLostChild (  const NodeID &  childID  ) 
 

Handles a lost child node of the Master Fountain node.

Parameters:
childID The NodeID of the child Fountain node that is lost
Returns:
SUCCESS if the lost child node should be removed from the children vector

FAILURE if the lost child node should NOT be removed from the children vector

Exceptions:
FountainException If handling the lost child was not possible and the tree topology should be rebuilt

void TreeTopology::handleLostChildRequest (  ConstParseMsgPtr  request,
FountainWireProtPtr  con
) 
 

Handle a lostChild request.

When a Fountain node in the tree topology loses its parentConnection it will connect to us and report the failure. This function is responsible for handling these requests.

Parameters:
request The lostChild request message
con The connection to the node reporting the lostChild request
Exceptions:
FountainException If handling the lost child request was not possible and the tree topology should be rebuilt

void TreeTopology::handleLostParentRequest (  ConstParseMsgPtr  request,
FountainWireProtPtr  con
) 
 

Handle a lostParent request When a Fountain node in the tree topology loses one of its childConnections, it will connect to us and report the failure. This function is responsible for handling these requests.

Parameters:
request The lostParent request message
con The connection to the node reporting the lostParent request
Exceptions:
FountainException If handling the lost child parent was not possible and the tree topology should be rebuilt

bool TreeTopology::isReadyToRecover (   )  [private]
 

Test of all the neighboring nodes of a lost node have contacted the master Fountain node.

Return values:
bool true if the tree is ready to be recovered, false otherwise

bool TreeTopology::overRecoveryTimeLimit (   ) 
 

Check if we're over the recovery time limit.

Return values:
bool true if the tree state is recovery and more than recoveryTimeLimit seconds have elapsed since the recovery started, false otherwise
Exceptions:
FountainException if the lost node could not be contacted when the tree has been in recovery for more than recoveryTimeLimit seconds

int TreeTopology::recoverTree (  ChildNodeContainer &  masterNodeChildren  ) 
 

Attempt to recover the tree from a node failure.

Parameters:
[in] masterNodeChildren the children container from the master node, needed because the replacement node could become a direct child of the master node
Returns:
SUCCESS if recovering from the tree was successful or not applicable at this time

FAILURE if recovering from the tree was not successful, and the tree should be rebuilt

Exceptions:
FountainException If recovering the tree topology was not possible and it should be rebuilt

int TreeTopology::replaceNode (  const treeIterator &  lostNode,
const treeIterator &  replacementNode
)  [private]
 

Replaces a lost node in the tree with another node.

Parameters:
lostNode The node in the tree that was lost
replacementNode The node in the tree to replace the lost node

int TreeTopology::setState (  TreeState  s  )  [private]
 

Set the state of the tree topology.

Parameters:
s The target TreeState enum of the tree
Returns:
SUCCESS if setting the tree topology's state was successful

FAILURE otherwise

Member Data Documentation

Timer TreeTopology::joinTimer_ [private]
 

The starting time of the last node to join the tree

double TreeTopology::maxRecoveryTime_ [private]
 

Maximum recover time in milliseconds since the master Fountain node started

double TreeTopology::minRecoveryTime_ [private]
 

Minimum recover time in milliseconds since the master Fountain node started

NodeID TreeTopology::myID_ [private]
 

NodeID of the master Fountain node

unsigned int TreeTopology::numChildrenPerNode_ [private]
 

The number of children for each node in the tree topology

Timer TreeTopology::rebuildTimer_ [private]
 

The starting time of rebuilding the tree

Timer TreeTopology::recoveryTimer_ [private]
 

The starting time of recovering from a node failure

TreeState TreeTopology::state_ [private]
 

The current state of the tree make this a class so we can prevent the assignment operator from being used - sjm 9-30-2005

unsigned int TreeTopology::totalRebuilds_ [private]
 

Total number of tree rebuilds

unsigned int TreeTopology::totalRecoveries_ [private]
 

Total number of tree recoveries since the master Fountain node started

double TreeTopology::totalRecoveryTime_ [private]
 

Total time of all recoveries in milliseconds since the master Fountain node started

TreeContainer TreeTopology::tree_ [private]
 

STL container to maintain all node in the tree topology

The documentation for this class was generated from the following files:
Generated on Wed Mar 8 14:43:33 2006 for Fountain by  doxygen 1.4.6