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 (PastryRoutingRowMessage *msg, int row) const
	dump content of a single row of the routing table to a message
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
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 Attributes
uint32_t	nodesPerRow
Private Member Functions
virtual void	earlyInit (void)
	initialize watches etc.
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

Detailed Description

Routing table module.

This module contains the routing table of the Chord implementation.

Author:: Felix Palmen

See also:: Pastry

Definition at line 63 of file PastryRoutingTable.h.

Member Function Documentation

void PastryRoutingTable::addRow ( void ) [private]

adds a new line to the routing table

Definition at line 351 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 28 of file PastryRoutingTable.cc.

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

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

void PastryRoutingTable::dumpRowToMessage	(	PastryRoutingRowMessage *	msg,
		int	row
	)			const `[virtual]`

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

Parameters:

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

Definition at line 207 of file PastryRoutingTable.cc.

Referenced by BasePastry::sendRoutingRow(), and BasePastry::sendStateTables().

{
    uint32_t i = 0;
    uint32_t size = 0;
    std::vector<PRTRow>::const_iterator itRows;
    PRTRow::const_iterator itCols;

    msg->setRoutingTableArraySize(nodesPerRow);
    if (row == -1) {
        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);
        }
    }
    msg->setRoutingTableArraySize(size);
}

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 236 of file PastryRoutingTable.cc.

{
    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 186 of file PastryRoutingTable.cc.

Referenced by Pastry::doSecondStage(), and BasePastry::sendStateTables().

{
    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 339 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 ) [private, virtual]

initialize watches etc.

Implements PastryStateObject.

Definition at line 34 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 373 of file PastryRoutingTable.cc.

Referenced by Pastry::handleFailedNode(), and Bamboo::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 88 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 170 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 459 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 (!ask->isUnspecified() && !track.node.isUnspecified() && track.node == *ask)
//            std::cout << "burp! " << owner.getKey() << " " << (static_cast<const NodeHandle*>(ask))->key << "\n("
//            << track.failedRow << ", " << track.failedCol << ") -> ("
//            << track.askedRow << ", " << track.askedCol << ")"
//            << std::endl;

        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 265 of file PastryRoutingTable.cc.

Referenced by Pastry::doRoutingTableMaintenance(), Bamboo::getNextRowToMaintain(), Pastry::handleUDPMessage(), and Bamboo::handleUDPMessage().

{
    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;
}

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 39 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 327 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->getJoinHopCount() != ++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 66 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 296 of file PastryRoutingTable.cc.

Referenced by Bamboo::lookupFinished(), BasePastry::pingResponse(), 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 58 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 411 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;
}