Routing table module. More...

#include <PastryRoutingTable.h>

Inheritance diagram for PastryRoutingTable:

Public Member Functions
void	initializeTable (uint32_t bitsPerDigit, double repairTimeout, const NodeHandle &owner)
	Initializes the routing table.
const NodeHandle &	lookupNextHop (const OverlayKey &destination)
	gets the next hop according to the Pastry routing scheme.
virtual const NodeHandle &	findCloserNode (const OverlayKey &destination, bool optimize=false)
	try to find a node numerically closer to a given key with the same shared prefix as the current node in the routing table.
void	findCloserNodes (const OverlayKey &destination, NodeVector *nodes)
virtual const TransportAddress &	failedNode (const TransportAddress &failed)
	tells the routing table that a node has failed
virtual const TransportAddress &	repair (const PastryStateMessage msg, const PastryStateMsgProximity prox)
	attempt to repair the routing using a received REPAIR message
virtual void	dumpToStateMessage (PastryStateMessage *msg) const
	dump content of the table to a PastryStateMessage
virtual void	dumpRowToMessage (PastryStateMessage *msg, int row) const
	dump content of a single row of the routing table to a state message
int	getLastRow ()
	gets the number of rows in the routing table
std::vector< TransportAddress > *	getRow (uint8_t row) const
virtual const TransportAddress &	getRandomNode (int row)
	returns a random node from the routing table
bool	mergeNode (const NodeHandle &node, simtime_t prox)
	merge a node in the IRoutingTable
bool	initStateFromHandleVector (const std::vector< PastryStateMsgHandle > &handles)
	initialize table from vector of PastryStateMsgHandles with STATE messages received during JOIN phase.
virtual void	dumpToVector (std::vector< TransportAddress > &affected) const
	appends all routing table entries to a given vector of TransportAddresses, needed to find all Nodes to be notified after joining.
Public Member Functions inherited from PastryStateObject
void	handleMessage (cMessage *msg)
int	numInitStages (void) const
void	initialize (int stage)
virtual const NodeHandle &	getDestinationNode (const OverlayKey &destination)
	gets the final node according to the Pastry routing scheme.
virtual const TransportAddress &	repair (const PastryStateMessage *msg, const PastryStateMsgProximity &prox)
	attempt to repair state using a received REPAIR message
virtual bool	mergeState (const PastryStateMessage msg, const PastryStateMsgProximity prox)
	update own state based on a received PastryStateMessage
bool	isCloser (const NodeHandle &test, const OverlayKey &destination, const NodeHandle &reference=NodeHandle::UNSPECIFIED_NODE) const
	test a given NodeHandle if it is closer to a given destination
bool	specialCloserCondition (const NodeHandle &test, const OverlayKey &destination, const NodeHandle &reference=NodeHandle::UNSPECIFIED_NODE) const
	test a given NodeHandle if it is closer to a given destination, but only if the shared prefix length with the destination is at least equal to the shared prefix length with our own node

Public Attributes
uint32_t	nodesPerRow

Private Member Functions
virtual void	earlyInit (void)
void	addRow (void)
	adds a new line to the routing table
uint32_t	digitAt (uint32_t n, const OverlayKey &key) const
	returns n'th pastry digit from a key
const PastryExtendedNode &	nodeAt (uint32_t row, uint32_t col) const
	returns routing table entry at specified position
void	findNextNodeToAsk (PRTTrackRepair &track) const
	helper function, updates a PRTTrackRepair structure to point to the next node that can be asked for repair

Private Attributes
double	repairTimeout
std::vector< PRTRow >	rows
std::vector< PRTTrackRepair >	awaitingRepair

Additional Inherited Members
Static Protected Member Functions inherited from PastryStateObject
static const PastryExtendedNode &	unspecNode ()
Protected Attributes inherited from PastryStateObject
NodeHandle	owner
	stores the NodeHandle of the owner of this PastryStateObject.
uint32_t	bitsPerDigit

Detailed Description

Routing table module.

This module contains the routing table of the Chord implementation.

Author: Felix Palmen

See Also: Pastry

Definition at line 64 of file PastryRoutingTable.h.

Member Function Documentation

void PastryRoutingTable::addRow ( void )

private

adds a new line to the routing table

Definition at line 354 of file PastryRoutingTable.cc.

Referenced by initializeTable(), and mergeNode().

{
    PRTRow row(nodesPerRow, unspecNode());
    // place own node at correct position:
    (row.begin() + digitAt(rows.size(), owner.getKey()))->node = owner;
    rows.push_back(row);
}

uint32_t PastryRoutingTable::digitAt	(	uint32_t	n,
		const OverlayKey &	key
	)		const

private

returns n'th pastry digit from a key

Parameters

n	which digit to return
key	extract digit from this key

Returns: a pastry digit

Definition at line 29 of file PastryRoutingTable.cc.

Referenced by addRow(), findCloserNode(), lookupNextHop(), and mergeNode().

{
    return key.getBitRange(OverlayKey::getLength() - ++n * bitsPerDigit,
                           bitsPerDigit);
}

void PastryRoutingTable::dumpRowToMessage	(	PastryStateMessage *	msg,
		int	row
	)		const

virtual

dump content of a single row of the routing table to a state message

Parameters

msg	the state message to be filled with entries
row	the number of the row

Definition at line 217 of file PastryRoutingTable.cc.

Referenced by BasePastry::createStateMessage().

{
    uint32_t i = 0;
    uint32_t size = 0;
    std::vector<PRTRow>::const_iterator itRows;
    PRTRow::const_iterator itCols;
    msg->setRoutingTableArraySize(nodesPerRow);
    if ((row == -1) || (row > (int)rows.size())) {
        itRows = rows.end() - 1;
    } else if (row > (int)rows.size()) {
        EV << "asked for nonexistent row";
        // TODO: verify this - added by ib
        msg->setRoutingTableArraySize(0);
        return;
    } else {
        itRows = rows.begin() + row - 1;
    }
    for (itCols = itRows->begin(); itCols != itRows->end(); itCols++) {
        if (!itCols->node.isUnspecified()) {
            ++size;
            msg->setRoutingTable(i++, itCols->node);
        }
    }
    // TODO: verify this - added by ib
    msg->setRoutingTableArraySize(size);
}

void PastryRoutingTable::dumpToStateMessage ( PastryStateMessage * msg ) const

virtual

dump content of the table to a PastryStateMessage

Parameters

msg	the PastryStateMessage to be filled with entries

Implements PastryStateObject.

Definition at line 196 of file PastryRoutingTable.cc.

Referenced by BasePastry::createStateMessage().

{
    uint32_t i = 0;
    uint32_t size = 0;
    std::vector<PRTRow>::const_iterator itRows;
    PRTRow::const_iterator itCols;
    msg->setRoutingTableArraySize(rows.size() * nodesPerRow);
    for (itRows = rows.begin(); itRows != rows.end(); itRows++) {
        for (itCols = itRows->begin(); itCols != itRows->end(); itCols++) {
            if (!itCols->node.isUnspecified()) {
                ++size;
                msg->setRoutingTable(i++, itCols->node);
            }
        }
    }
    msg->setRoutingTableArraySize(size);
}

void PastryRoutingTable::dumpToVector ( std::vector< TransportAddress > & affected ) const

virtual

appends all routing table entries to a given vector of TransportAddresses, needed to find all Nodes to be notified after joining.

Parameters

affected the vector to fill with routing table entries

Implements PastryStateObject.

Definition at line 342 of file PastryRoutingTable.cc.

Referenced by Pastry::changeState(), and Pastry::doSecondStage().

{
    std::vector<PRTRow>::const_iterator itRows;
    PRTRow::const_iterator itCols;
    for (itRows = rows.begin(); itRows != rows.end(); ++itRows)
        for (itCols = itRows->begin(); itCols != itRows->end(); ++itCols)
            if (!itCols->node.isUnspecified())
                affected.push_back(itCols->node);
}

void PastryRoutingTable::earlyInit ( void )

privatevirtual

Definition at line 37 of file PastryRoutingTable.cc.

{
    WATCH_VECTOR(rows);
}

const TransportAddress & PastryRoutingTable::failedNode ( const TransportAddress & failed )

virtual

tells the routing table that a node has failed

Parameters

failed the failed node

Returns: a node to ask for REPAIR or TransportAddress::UNSPECIFIED_NODE

Implements PastryStateObject.

Definition at line 378 of file PastryRoutingTable.cc.

Referenced by Bamboo::handleFailedNode(), and Pastry::handleFailedNode().

{
    std::vector<PRTRow>::iterator itRows;
    PRTRow::iterator itCols;
    PRTTrackRepair tmpTrack;
    bool found = false;
    // find node in table:
    for (itRows = rows.begin(); itRows != rows.end(); itRows++) {
        for (itCols = itRows->begin(); itCols != itRows->end(); itCols++) {
            if ((! itCols->node.isUnspecified()) &&
                    (itCols->node.getIp() == failed.getIp())) {
                itCols->node = NodeHandle::UNSPECIFIED_NODE;
                itCols->rtt = PASTRY_PROX_UNDEF;
                found = true;
                break;
            }
        }
        if (found) break;
    }
    // not found, nothing to do:
    if (!found) return TransportAddress::UNSPECIFIED_NODE;
    // else fill temporary record:
    tmpTrack.failedRow = itRows - rows.begin();
    tmpTrack.failedCol = itCols - itRows->begin();
    tmpTrack.node = TransportAddress::UNSPECIFIED_NODE;
    findNextNodeToAsk(tmpTrack);
    tmpTrack.timestamp = simTime();
    if (tmpTrack.node.isUnspecified())
        return TransportAddress::UNSPECIFIED_NODE;
    awaitingRepair.push_back(tmpTrack);
    return awaitingRepair.back().node;
}

const NodeHandle & PastryRoutingTable::findCloserNode	(	const OverlayKey &	destination,
		bool	optimize = `false`
	)

virtual

try to find a node numerically closer to a given key with the same shared prefix as the current node in the routing table.

this method is to be called, when a regular next hop couldn't be found or wasn't reachable.

Parameters

destination	the destination key
optimize	if set, check all nodes and return the best/closest one

Returns: a closer NodeHandle or NodeHandle::UNSPECIFIED_NODE if none was found

Implements PastryStateObject.

Definition at line 96 of file PastryRoutingTable.cc.

Referenced by BasePastry::findNode().

{
    if (destination == owner.getKey())
        opp_error("trying to find closer node to own key!");
    const PastryExtendedNode* entry;
    if (optimize) {
        // pointer to later return value, initialize to unspecified, so
        // the specialCloserCondition() check will be done against our own
        // node as long as no node closer to the destination than our own was
        // found.
        const NodeHandle* ret = &NodeHandle::UNSPECIFIED_NODE;
        // a numerically closer node can only be found in the row containing
        // nodes with the same prefix length and in the row above.
        int shl = owner.getKey().sharedPrefixLength(destination) / bitsPerDigit;
        int digit = digitAt(shl, destination);
        int x = digitAt(shl, owner.getKey()); // position index of own node
        // first try the row with same prefix length:
        int n = nodesPerRow;
        int a = digit - 1; // position index of search to the left
        int b = digit + 1; // position index of search to the right
        while ((a >= 0) || (b < n)) {
            // no need to continue search in one direction when own entry is
            // reached:
            if (a == x) a = -1;
            if (b == x) b = n;
            if (a >= 0) {
                entry = &(nodeAt(shl, a));
                if ((!entry->node.isUnspecified()) &&
                        specialCloserCondition(entry->node, destination, *ret))
                    ret = &(entry->node);
                a--;
            }
            if (b < n) {
                entry = &(nodeAt(shl, b));
                if ((!entry->node.isUnspecified()) &&
                        specialCloserCondition(entry->node, destination, *ret))
                    ret = &(entry->node);
                b++;
            }
        }
        // it this was not the first row, two more nodes to check:
        if (shl != 0) {
            // go up one row:
            x = digitAt(--shl, owner.getKey());
            if (destination < owner.getKey()) {
                entry = &(nodeAt(shl, digit - 1));
                if ((!entry->node.isUnspecified()) &&
                        specialCloserCondition(entry->node, destination, *ret))
                    ret = &(entry->node);
            } else {
                entry = &(nodeAt(shl, digit + 1));
                if ((!entry->node.isUnspecified()) &&
                        specialCloserCondition(entry->node, destination, *ret))
                    ret = &(entry->node);
            }
        }
        return *ret; // still unspecified if no closer node was found
    } else {
        // no optimization, return the first closer node found
        for (uint32_t y = 0; y < rows.size(); ++y) {
            for (uint32_t x = 0; x < nodesPerRow; ++x) {
                entry = &(nodeAt(y, x));
                if ((!entry->node.isUnspecified()) &&
                        specialCloserCondition(entry->node, destination))
                    return entry->node;
            }
        }
        return NodeHandle::UNSPECIFIED_NODE;
    }
}

void PastryRoutingTable::findCloserNodes	(	const OverlayKey &	destination,
		NodeVector *	nodes
	)

virtual

Implements PastryStateObject.

Definition at line 179 of file PastryRoutingTable.cc.

Referenced by BasePastry::findNode().

{
    //TODO
    const PastryExtendedNode* entry;
    for (uint32_t y = 0; y < rows.size(); ++y) {
        for (uint32_t x = 0; x < nodesPerRow; ++x) {
            entry = &(nodeAt(y, x));
            if (!entry->node.isUnspecified()
            /* && specialCloserCondition(entry->node, destination)*/)
                nodes->add(entry->node);
        }
    }
}

void PastryRoutingTable::findNextNodeToAsk ( PRTTrackRepair & track ) const

private

helper function, updates a PRTTrackRepair structure to point to the next node that can be asked for repair

Parameters

track the PRTTrackRepair structure

Definition at line 466 of file PastryRoutingTable.cc.

Referenced by failedNode(), and repair().

{
    const TransportAddress* ask;
    if (track.node.isUnspecified()) {
        track.askedRow = track.failedRow;
        if (track.failedCol == 0)
            track.askedCol = 1;
        else
            track.askedCol = 0;
        ask = static_cast<const TransportAddress*>(
                &(nodeAt(track.askedRow, track.askedCol).node));
        track.node = *ask;
        if ( (! track.node.isUnspecified()) &&
                (track.node != owner) )
            return;
    }
    do {
        // point to next possible position in routing table:
        track.askedCol++;
        if ((track.askedRow == track.failedRow) &&
                (track.askedCol == track.failedCol)) track.askedCol++;
        if (track.askedCol == nodesPerRow) {
            if ((track.askedRow > track.askedCol) ||
                    (track.askedRow == (rows.size() - 1))) {
                // no more nodes that could be asked, give up:
                track.node = TransportAddress::UNSPECIFIED_NODE;
                return;
            }
            track.askedRow++;
            track.askedCol = 0;
        }
        ask = static_cast<const TransportAddress*>(
                &(nodeAt(track.askedRow, track.askedCol).node));
        if (track.node.isUnspecified() ||
            (!ask->isUnspecified() && track.node != *ask))
            track.node = *ask; //only happens if track.node == owner
        else track.node = TransportAddress::UNSPECIFIED_NODE;
    }
    while (track.node.isUnspecified() || (track.node == owner) );
}

int PastryRoutingTable::getLastRow ( )

gets the number of rows in the routing table

Returns: the number of rows in the routing table

Definition at line 264 of file PastryRoutingTable.cc.

Referenced by Pastry::doRoutingTableMaintenance(), Bamboo::getNextRowToMaintain(), BasePastry::getRTLastRow(), and BasePastry::handleRequestRoutingRowCall().

{
    return rows.size();
}

const TransportAddress & PastryRoutingTable::getRandomNode ( int row )

virtual

returns a random node from the routing table

Parameters

row	the row to choose a random node from

Returns: a random node or TransportAddress::UNSPECIFIED_NODE

Definition at line 270 of file PastryRoutingTable.cc.

Referenced by Bamboo::doLocalTuning(), and Pastry::doRoutingTableMaintenance().

{
    std::vector<PRTRow>::const_iterator itRows;
    PRTRow::const_iterator itCols;
    uint32_t rnd;
    itRows = rows.begin() + row;
    if (itRows >= rows.end()) {
        EV << "[PastryRoutingTable::getRandomNode()]\n"
           << "    tried to get random Node from nonexistent row"
           << endl;
    }
    rnd = intuniform(0, nodesPerRow - 1, 0);
    itCols = itRows->begin() + rnd;
    while (itCols != itRows->end()) {
        if (!itCols->node.isUnspecified()) return itCols->node;
        else itCols++;
    }
    itCols = itRows->begin() + rnd;
    while (itCols >= itRows->begin()) {
        if (!itCols->node.isUnspecified()) return itCols->node;
        else itCols--;
    }
    return TransportAddress::UNSPECIFIED_NODE;
}

std::vector< TransportAddress > * PastryRoutingTable::getRow ( uint8_t row ) const

Definition at line 247 of file PastryRoutingTable.cc.

Referenced by BasePastry::getRTRow().

{
    std::vector<TransportAddress>* temp = new std::vector<TransportAddress>;
    if ((row < 1) || (row > (int)rows.size())) return temp;
    std::vector<PRTRow>::const_iterator itRows = rows.begin() + row - 1;
    for (PRTRow::const_iterator itCols = itRows->begin();
         itCols != itRows->end(); ++itCols) {
        if (itCols != itRows->end() && !itCols->node.isUnspecified()) {
            temp->push_back(itCols->node);
        }
    }
    return temp;
}

void PastryRoutingTable::initializeTable	(	uint32_t	bitsPerDigit,
		double	repairTimeout,
		const NodeHandle &	owner
	)

Initializes the routing table.

This should be called on startup

Parameters

bitsPerDigit	Pastry configuration parameter
repairTimeout	Pastry configuration parameter
owner	the node this table belongs to

Definition at line 43 of file PastryRoutingTable.cc.

Referenced by BasePastry::baseChangeState().

{
    this->owner = owner;
    this->repairTimeout = repairTimeout;
    this->bitsPerDigit = bitsPerDigit;
    nodesPerRow = 1 << bitsPerDigit; // 2 ^ bitsPerDigit
    // forget old routing table contents in case of restart:
    if (!rows.empty()) rows.clear();
    // clear pending repair requests:
    if (!awaitingRepair.empty()) awaitingRepair.clear();
    // Create first row in table:
    addRow();
}

bool PastryRoutingTable::initStateFromHandleVector ( const std::vector< PastryStateMsgHandle > & handles )

initialize table from vector of PastryStateMsgHandles with STATE messages received during JOIN phase.

The vector has to be sorted by JoinHopCount of the messages

Parameters

handles the vector of PastryStateMsgHandles

Returns: true on success

Definition at line 329 of file PastryRoutingTable.cc.

Referenced by Pastry::mergeState().

{
    std::vector<PastryStateMsgHandle>::const_iterator it;
    int hopCheck = 0;
    for (it = handles.begin(); it != handles.end(); ++it) {
        if (it->msg->getRow() != ++hopCheck) return false;
        mergeState(it->msg, it->prox);
    }
    return true;
}

const NodeHandle & PastryRoutingTable::lookupNextHop ( const OverlayKey & destination )

gets the next hop according to the Pastry routing scheme.

Parameters

destination the destination key

Returns: the NodeHandle of the next Node or NodeHandle::UNSPECIFIED_NODE if no next hop could be determined

Definition at line 73 of file PastryRoutingTable.cc.

Referenced by BasePastry::findNode().

{
    if (destination == owner.getKey()) opp_error("trying to lookup own key!");
    uint32_t shl = owner.getKey().sharedPrefixLength(destination) / bitsPerDigit;
    uint32_t digit = digitAt(shl, destination);
    if (shl >= rows.size()) {
        EV << "Pastry: Unable to find next hop for " << destination
           << ", row is empty." << endl;
        return NodeHandle::UNSPECIFIED_NODE;
    }
    const PastryExtendedNode& next = nodeAt(shl, digit);
    if (next.node.isUnspecified()) {
        EV << "Pastry: Unable to find next hop for " << destination
           << ", routing table entry is empty." << endl;
    }
    return next.node;
}

bool PastryRoutingTable::mergeNode	(	const NodeHandle &	node,
		simtime_t	prox
	)

virtual

merge a node in the IRoutingTable

Parameters

node	the node to merge
prox	proximity value of the node

Returns: true if node was merged

Implements PastryStateObject.

Definition at line 297 of file PastryRoutingTable.cc.

Referenced by Bamboo::lookupFinished(), and BasePastry::proxCallback().

{
    if (node.getKey() == owner.getKey())
        opp_error("trying to merge node with same key!");
    uint32_t shl;
    uint32_t digit;
    PRTRow::iterator position;
    shl = owner.getKey().sharedPrefixLength(node.getKey()) / bitsPerDigit;
    digit = digitAt(shl, node.getKey());
    while (rows.size() <= shl) addRow();
    position = (rows.begin() + shl)->begin() + digit;
    if (position->node.isUnspecified() || (prox < position->rtt)) {
        EV << "[PastryRoutingTable::mergeNode()]\n"
           << "    Node " << owner.getKey()
           << endl;
        EV << "        placing node " << node.getKey() << "in row "
           << shl << ", col" << digit << endl;
        if (! position->node.isUnspecified()) {
            EV << "        (replaced because of better proximity: "
            << prox << " < " << position->rtt << ")" << endl;
        }
        position->node = node;
        position->rtt = prox;
        return true;
    }
    return false;
}

const PastryExtendedNode & PastryRoutingTable::nodeAt	(	uint32_t	row,
		uint32_t	col
	)		const

private

returns routing table entry at specified position

Parameters

row	the number of the row
col	the number of the column

Definition at line 63 of file PastryRoutingTable.cc.

Referenced by findCloserNode(), findCloserNodes(), findNextNodeToAsk(), lookupNextHop(), and repair().

{
    if (rows.size() <= row) return unspecNode();
    if (col >= nodesPerRow) return unspecNode();
    return *((rows.begin()+row)->begin()+col);
}

const TransportAddress & PastryRoutingTable::repair	(	const PastryStateMessage *	msg,
		const PastryStateMsgProximity *	prox
	)

virtual

attempt to repair the routing using a received REPAIR message

Parameters

msg	the state message of type REPAIR
prox	record of proximity values matching the state message

Returns: another node to ask for REPAIR or TransportAddress::UNSPECIFIED_NODE

Definition at line 417 of file PastryRoutingTable.cc.

Referenced by Pastry::checkProxCache().

{
    std::vector<PRTTrackRepair>::iterator it;
    simtime_t now = simTime();
    // first eliminate outdated entries in awaitingRepair:
    for (it = awaitingRepair.begin(); it != awaitingRepair.end();) {
        if (it->timestamp < (now - repairTimeout))
            it = awaitingRepair.erase(it);
        else it++;
    }
    // don't expect any more repair messages:
    if (awaitingRepair.empty()) return TransportAddress::UNSPECIFIED_NODE;
    // look for source node in our list:
    for (it = awaitingRepair.begin(); it != awaitingRepair.end(); it++)
        if (it->node == msg->getSender()) break;
    // if not found, return from function:
    if (it == awaitingRepair.end()) return TransportAddress::UNSPECIFIED_NODE;
    // merge state:
    mergeState(msg, prox);
    // repair not yet done?
    if (nodeAt(it->failedRow, it->failedCol).node.isUnspecified()) {
        // ask next node
        findNextNodeToAsk(*it);
        if (it->node.isUnspecified()) {
            // no more nodes to ask, give up:
            EV << "[PastryRoutingTable::repair()]\n"
               << "    RoutingTable giving up repair attempt."
               << endl;
            awaitingRepair.erase(it);
            return TransportAddress::UNSPECIFIED_NODE;
        }
        else return it->node;
    }
    // repair done: clean up
    EV << "[PastryRoutingTable::repair()]\n"
       << "    RoutingTable repair was successful."
       << endl;
    return TransportAddress::UNSPECIFIED_NODE;
}