Chord's finger table module. More...

#include <ChordFingerTable.h>

Public Member Functions
virtual int	numInitStages () const
virtual void	initialize (int stage)
virtual void	handleMessage (cMessage *msg)
virtual void	initializeTable (uint32_t size, const NodeHandle &owner, Chord *overlay)
	Sets up the finger table.
virtual void	setFinger (uint32_t pos, const NodeHandle &node, Successors const *sucNodes=NULL)
	Sets a particular finger to point to node.
virtual void	setFinger (uint32_t pos, const Successors &nodes)
virtual bool	updateFinger (uint32_t pos, const NodeHandle &node, simtime_t rtt)
virtual const NodeHandle &	getFinger (uint32_t pos)
	Returns the NodeVector of a particular finger.
virtual NodeVector *	getFinger (uint32_t pos, const OverlayKey &key)
bool	handleFailedNode (const TransportAddress &failed)
void	removeFinger (uint32_t pos)
	Deletes a particular finger.
virtual uint32_t	getSize ()
	Returns the size of the finger table.
Private Attributes
uint32_t	maxSize
	maximum size of the finger table
std::deque< FingerEntry >	fingerTable
	the finger table vector
Chord *	overlay
	pointer to the main chord module

Detailed Description

Chord's finger table module.

This modul contains the finger table of the Chord implementation.

Author:: Markus Mauch, Ingmar Baumgart

See also:: Chord

Definition at line 52 of file ChordFingerTable.h.

Member Function Documentation

const NodeHandle & oversim::ChordFingerTable::getFinger ( uint32_t pos ) [virtual]

Returns the NodeVector of a particular finger.

Parameters:

pos

number of the finger to get

Returns:: NodeVector of the particular finger(s)

Definition at line 173 of file ChordFingerTable.cc.

Referenced by oversim::Chord::closestPreceedingNode(), and oversim::Chord::handleStabilizeTimerExpired().

{
    if (pos >= maxSize) {
        throw new cRuntimeError("ChordFingerTable::getFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;

    if (p >= fingerTable.size()) {
        return overlay->successorList->getSuccessor();
    }
    while (fingerTable[p].first.isUnspecified() &&
            (p < (fingerTable.size() - 1))) {
        ++p;
    }
    if (fingerTable[p].first.isUnspecified())
        return overlay->successorList->getSuccessor();
    return fingerTable[p].first;

NodeVector * oversim::ChordFingerTable::getFinger	(	uint32_t	pos,
		const OverlayKey &	key
	)			`[virtual]`

Definition at line 194 of file ChordFingerTable.cc.

{
    if (pos >= maxSize) {
        throw new cRuntimeError("ChordFingerTable::getFinger(): "
                                "Index out of bound");
    }

    NodeVector* nextHop = new NodeVector();
    uint32_t p = maxSize - pos - 1;

    if (p < fingerTable.size()) {
        for (Successors::const_iterator it = fingerTable[p].second.begin();
             it != fingerTable[p].second.end(); it++) {

            if(!key.isBetweenLR(fingerTable[p].first.getKey(), it->second.getKey())) {
                nextHop->push_back(it->second);
            }
        }
    } else {
        nextHop->push_back(overlay->successorList->getSuccessor());
        return nextHop;
    }

    if (nextHop->size() == 0) {
        if (fingerTable[p].first.isUnspecified()) {
            //TODO use other finger
            nextHop->push_back(overlay->successorList->getSuccessor());
        } else {
            nextHop->push_back(fingerTable[p].first);
        }
    }

    return nextHop;

uint32_t oversim::ChordFingerTable::getSize ( ) [virtual]

Returns the size of the finger table.

Returns:: number of fingers

Definition at line 60 of file ChordFingerTable.cc.

Referenced by oversim::Chord::closestPreceedingNode().

{
    return maxSize;

bool oversim::ChordFingerTable::handleFailedNode ( const TransportAddress & failed )

Definition at line 131 of file ChordFingerTable.cc.

Referenced by oversim::Chord::handleFailedNode().

{
    bool ret = false;
    for (int p = fingerTable.size() - 1; p >= 0; p--) {
        if (!fingerTable[p].first.isUnspecified() &&
            failed == fingerTable[p].first) {
            fingerTable[p].first = NodeHandle::UNSPECIFIED_NODE;
            ret = true;
        }
        for (std::multimap<simtime_t, NodeHandle>::iterator it =
             fingerTable[p].second.begin(); it != fingerTable[p].second.end();
             ++it) {
            if (failed == it->second) {
                fingerTable[p].second.erase(it);
                break;
            }
        }
    }

    return ret;

void oversim::ChordFingerTable::handleMessage ( cMessage * msg ) [virtual]

Definition at line 47 of file ChordFingerTable.cc.

{
    error("this module doesn't handle messages, it runs only in initialize()");

void oversim::ChordFingerTable::initialize ( int stage ) [virtual]

Definition at line 35 of file ChordFingerTable.cc.

{
    // because of IPAddressResolver, we need to wait until interfaces
    // are registered, address auto-assignment takes place etc.
    if(stage != MIN_STAGE_OVERLAY)
        return;

    maxSize = 0;

    WATCH_DEQUE(fingerTable);

void oversim::ChordFingerTable::initializeTable	(	uint32_t	size,
		const NodeHandle &	owner,
		Chord *	overlay
	)			`[virtual]`

Sets up the finger table.

Sets up the finger table and makes all fingers pointing to the node itself. Should be called on startup to initialize the finger table.

Parameters:

	size	number of fingers
	owner	set all fingers to the key of node handle owner
	overlay	pointer to the main chord module

Definition at line 52 of file ChordFingerTable.cc.

Referenced by oversim::Chord::initializeFriendModules().

{
    maxSize = size;
    this->overlay = overlay;
    fingerTable.clear();

virtual int oversim::ChordFingerTable::numInitStages ( ) const [inline, virtual]

Definition at line 56 of file ChordFingerTable.h.

    {
        return MAX_STAGE_OVERLAY + 1;
    }

void oversim::ChordFingerTable::removeFinger ( uint32_t pos )

Deletes a particular finger.

Parameters:

pos

number of the finger to get

Definition at line 153 of file ChordFingerTable.cc.

Referenced by oversim::Chord::handleFixFingersTimerExpired(), and oversim::Chord::handleRpcFixfingersResponse().

{
    if (pos >= maxSize) {
        throw new cRuntimeError("ChordFingerTable::removeFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;

    if (p >= fingerTable.size()) {
        return;
    } else if (p == (fingerTable.size() - 1)) {
        fingerTable.pop_back();
    } else {
        Successors tempSuccessors;
        fingerTable[p] = FingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                     tempSuccessors);
    }

void oversim::ChordFingerTable::setFinger	(	uint32_t	pos,
		const Successors &	nodes
	)			`[virtual]`

Definition at line 88 of file ChordFingerTable.cc.

{
    setFinger(pos, nodes.begin()->second, &nodes);

void oversim::ChordFingerTable::setFinger	(	uint32_t	pos,
		const NodeHandle &	node,
		Successors const *	sucNodes = `NULL`
	)			`[virtual]`

Sets a particular finger to point to node.

Parameters:

	pos	number of the finger to set
	node	set finger to this node
	sucNodes	optional pointer containing a list of successors of this finger

Definition at line 65 of file ChordFingerTable.cc.

Referenced by oversim::Chord::handleRpcFixfingersResponse(), and setFinger().

{
    if (pos >= maxSize) {
        throw new cRuntimeError("ChordFingerTable::setFinger(): "
                                "Index out of bound");
    }

    uint32_t p = maxSize - pos - 1;
    Successors tempSuccessors;

    while (fingerTable.size() <= p) {
        fingerTable.push_back(FingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                          tempSuccessors));
    }

    if (sucNodes != NULL) {
        fingerTable[p] = FingerEntry(node, *sucNodes);
    } else {
        fingerTable[p] = FingerEntry(node, tempSuccessors);
    }

bool oversim::ChordFingerTable::updateFinger	(	uint32_t	pos,
		const NodeHandle &	node,
		simtime_t	rtt
	)			`[virtual]`

Definition at line 93 of file ChordFingerTable.cc.

Referenced by oversim::Chord::handleRpcFixfingersResponse(), oversim::Chord::pingResponse(), and oversim::Chord::proxCallback().

{
    if (rtt < 0)
        return false;

    if (pos >= maxSize) {
         throw new cRuntimeError("ChordFingerTable::updateFinger(): "
                                 "Index out of bound");
     }

    uint32_t p = maxSize - pos - 1;

    while (fingerTable.size() <= p) {
        Successors tempSuccessors;
        fingerTable.push_back(FingerEntry(NodeHandle::UNSPECIFIED_NODE,
                                          tempSuccessors));
    }

    Successors::iterator it;
    for (it = fingerTable[p].second.begin(); it != fingerTable[p].second.end();
         it++) {

        if (it->second == node) {
            break;
        }
    }

    if (it == fingerTable[p].second.end()) {
        return false;
    }

    fingerTable[p].second.erase(it);
    fingerTable[p].second.insert(std::make_pair(rtt, node));

    return true;