Broose bucket module. More...

#include <BrooseBucket.h>

Public Member Functions
virtual int	numInitStages () const
virtual void	initialize (int stage)
virtual void	handleMessage (cMessage *msg)
virtual bool	add (const NodeHandle &node, bool isAlive=false, simtime_t rtt=MAXTIME)
	adds a broose node handle to the bucket
virtual void	remove (const NodeHandle &node)
	removes a broose node handle from the bucket
virtual const BrooseHandle &	get (uint32_t pos=0)
	returns a specific broose handle
virtual const OverlayKey &	getDist (uint32_t pos=0)
	returns distance of a specific broose handle
virtual void	initializeBucket (int shiftingBits, uint32_t prefix, int size, Broose *overlay, bool isBBucket=false)
	initializes a bucket
virtual uint32_t	getSize ()
	returns number of current entries
virtual uint32_t	getMaxSize ()
	returns number of maximal entries
virtual void	fillVector (NodeVector *result)
	Fills a NodeVector with all bucket entries.
virtual bool	isEmpty ()
	checks if the bucket is empty
virtual void	clear ()
	removes all entries from the bucket
virtual int	longestPrefix (void)
	return the longest prefix of all entries
virtual bool	keyInRange (const OverlayKey &key)
	checks if the key close to the owner's id
virtual int	getPos (const NodeHandle &node)
	returns the position of a node in this bucket
virtual int	getFailedResponses (const NodeHandle &node)
	returns the number of failed responses to a specific broose handle
virtual void	increaseFailedResponses (const NodeHandle &node)
	increase the number of failed responses to a specific broose handle
virtual void	resetFailedResponses (const NodeHandle &node)
	resets the counter of failed responses to a specific broose handle
virtual void	setRTT (const NodeHandle &node, simtime_t rpcRTT)
	sets the round trip time to a specific broose handle
virtual simtime_t	getRTT (const NodeHandle &node)
	returns the round trip time to a specific broose handle
virtual void	setLastSeen (const NodeHandle &node, simtime_t lastSeen)
	updates the timestamp of a specific node
virtual simtime_t	getLastSeen (const NodeHandle &node)
	returns the timestamp of a specific node
void	output (int maxEntries=0)
	displays the content of the bucket on standard out

Protected Attributes
std::map< OverlayKey, BrooseHandle >	bucket
	data structure representing the bucket
std::map< OverlayKey, BrooseHandle >::iterator	bucketIter
	iterator to navigate through the bucket
unsigned int	maxSize
	maximal size of the bucket
OverlayKey	key
	the node's key shifted to fit the bucket and used to measure distance to other keys
Broose *	overlay
	pointer to the main Broose module
bool	isBBucket
	true, if this bucket is the node's BBucket

Detailed Description

Broose bucket module.

This modul contains the bucket of the Broose implementation.

Author: Jochen Schenk

See Also: Broose

Definition at line 43 of file BrooseBucket.h.

Member Function Documentation

bool BrooseBucket::add	(	const NodeHandle &	node,
		bool	isAlive = `false`,
		simtime_t	rtt = `MAXTIME`
	)

virtual

adds a broose node handle to the bucket

Parameters

node	the NodeHandle to add
isAlive	true, if it is known that the node is alive
rtt	measured round-trip-time to node

Returns: true, if the node was known or has been added

Definition at line 70 of file BrooseBucket.cc.

Referenced by Broose::changeState(), and Broose::handleBucketTimerExpired().

{
    OverlayKey tmp = key ^ node.getKey();
    bucketIter = bucket.find(tmp);
    if (bucketIter == bucket.end()) {
        // new node
        if (bucket.size() < maxSize) {
             bucketIter = bucket.insert(make_pair(tmp,node)).first;
        } else {
            std::map<OverlayKey, BrooseHandle>::iterator back = --bucket.end();
            // is the new node closer than the one farthest away,
            // remove the one and add the other
            if (back->first > tmp) {
                if (isBBucket) {
                    // call update() for removed sibling
                    overlay->callUpdate(back->second, false);
                }
                bucket.erase(back);
                bucketIter = bucket.insert(make_pair(tmp,node)).first;
            } else {
                // doesn't fit into bucket
                return false;
            }
        }
        if (isBBucket) {
            // call update() for new sibling
            overlay->callUpdate(node, true);
        }
    }
    if (isAlive) {
        bucketIter->second.failedResponses = 0;
        bucketIter->second.lastSeen = simTime();
    }
    if (rtt != MAXTIME) {
        bucketIter->second.rtt = rtt;
    }
    return true;
}

void BrooseBucket::clear ( )

virtual

removes all entries from the bucket

Definition at line 189 of file BrooseBucket.cc.

{
    bucket.clear();
}

void BrooseBucket::fillVector ( NodeVector * result )

virtual

Fills a NodeVector with all bucket entries.

Parameters

result a pointer to an existing NodeVector, which gets filled with all bucket entries

Definition at line 194 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        result->add(bucketIter->second);
    }
}

const BrooseHandle & BrooseBucket::get ( uint32_t pos = 0 )

virtual

returns a specific broose handle

Parameters

pos	position of the broose handle in the bucket

Definition at line 137 of file BrooseBucket.cc.

Referenced by Broose::changeState(), and Broose::handleBucketTimerExpired().

{
    if (pos > bucket.size()) {
        error("Index out of bounds(BrooseBucket).");
    }
    uint32_t i = 0;
    std::map<OverlayKey, BrooseHandle>::iterator it;
    for (it = bucket.begin(); it != bucket.end(); it++, i++) {
        if (pos == i) {
            return it->second;
        }
    }
    return BrooseHandle::unspecifiedNode();
}

const OverlayKey & BrooseBucket::getDist ( uint32_t pos = 0 )

virtual

returns distance of a specific broose handle

Parameters

pos	position of the broose handle in the bucket

Definition at line 155 of file BrooseBucket.cc.

Referenced by keyInRange().

{
    if (pos > bucket.size()) {
        error("Index out of bounds(BrooseBucket).");
    }
    uint32_t i = 0;
    std::map<OverlayKey, BrooseHandle>::iterator it;
    for (it = bucket.begin(); it != bucket.end(); it++, i++) {
        if (pos == i) {
            return it->first;
        }
    }
    return OverlayKey::UNSPECIFIED_KEY;
}

int BrooseBucket::getFailedResponses ( const NodeHandle & node )

virtual

returns the number of failed responses to a specific broose handle

Parameters

node	broose handle to check

Returns: number of failed responses

Definition at line 273 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            return bucketIter->second.failedResponses;
    }
    return -1;
}

simtime_t BrooseBucket::getLastSeen ( const NodeHandle & node )

virtual

returns the timestamp of a specific node

Parameters

node	broose handle to which the timestamp will be retrieved

Returns: the retrieved timestamp

Definition at line 325 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            return bucketIter->second.lastSeen;
    }
    return -2;
}

uint32_t BrooseBucket::getMaxSize ( )

virtual

returns number of maximal entries

Returns: number of maximal entries

Definition at line 179 of file BrooseBucket.cc.

{
    return maxSize;
}

int BrooseBucket::getPos ( const NodeHandle & node )

virtual

returns the position of a node in this bucket

Parameters

node	broose handle to check

Returns: the position of the node (0 = first node, -1 = node not in bucket)

Definition at line 262 of file BrooseBucket.cc.

{
    int i = -1;
    std::map<OverlayKey, BrooseHandle>::iterator it;
    for (it = bucket.begin(); it != bucket.end(); it++, i++) {
        if (node.getIp() == it->second.getIp())
            return i;
    }
    return i;
}

simtime_t BrooseBucket::getRTT ( const NodeHandle & node )

virtual

returns the round trip time to a specific broose handle

Parameters

node	broose handle to which the rtt will be retrieved

Returns: rtt to the specific node

Definition at line 308 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            return bucketIter->second.rtt;
    }
    return -2;
}

uint32_t BrooseBucket::getSize ( )

virtual

returns number of current entries

Returns: number of current entries

Definition at line 174 of file BrooseBucket.cc.

Referenced by Broose::changeState(), and Broose::handleBucketTimerExpired().

{
    return bucket.size();
}

void BrooseBucket::handleMessage ( cMessage * msg )

virtual

Definition at line 44 of file BrooseBucket.cc.

{
    error("BrooseBucket::handleMessage() shouldn't be called!");
}

void BrooseBucket::increaseFailedResponses ( const NodeHandle & node )

virtual

increase the number of failed responses to a specific broose handle

Parameters

node	broose handle which counter will be increased

Definition at line 282 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            bucketIter->second.failedResponses++;
    }
}

void BrooseBucket::initialize ( int stage )

virtual

Definition at line 36 of file BrooseBucket.cc.

{
    if(stage != MIN_STAGE_OVERLAY)
        return;
    WATCH_MAP(bucket);
}

void BrooseBucket::initializeBucket	(	int	shiftingBits,
		uint32_t	prefix,
		int	size,
		Broose *	overlay,
		bool	isBBucket = `false`
	)

virtual

initializes a bucket

Parameters

shiftingBits	specifies the kind of the bucket
prefix	in case of a R bucket specifies the prefix
size	maximal size of the bucket
overlay	pointer to the main Broose module
isBBucket	true, is this bucket is the node's BBucket

Definition at line 49 of file BrooseBucket.cc.

Referenced by Broose::changeState(), and Broose::handleBucketTimerExpired().

{
    maxSize = size;
    this->overlay = overlay;
    this->isBBucket = isBBucket;
    if (shiftingBits < 0) {
        key = overlay->getThisNode().getKey() << -shiftingBits;
    } else {
        key = overlay->getThisNode().getKey() >> shiftingBits;
    }
    if (prefix != 0) {
        OverlayKey tmp(prefix); // constraint
        tmp = tmp << (overlay->getThisNode().getKey().getLength() - shiftingBits);
        key = key + tmp;
    }
    bucket.clear();
}

bool BrooseBucket::isEmpty ( )

virtual

checks if the bucket is empty

Returns: true if the bucket is empty

Definition at line 184 of file BrooseBucket.cc.

{
    return bucket.empty();
}

bool BrooseBucket::keyInRange ( const OverlayKey & key )

virtual

checks if the key close to the owner's id

Parameters

key	key to check

Returns: true if node is close

Definition at line 239 of file BrooseBucket.cc.

{
    OverlayKey dist;
    if (bucket.size() == 0)
        return false;
    // check if the function was called to perform on a B bucket
    if (isBBucket) {
        if (bucket.size() <=  (maxSize / 7))
            return true;
        else
            dist = getDist((maxSize / 7) - 1);
    } else
        dist = getDist(bucket.size()-1);
    if ((key ^ overlay->getThisNode().getKey()) <= dist)
        return true;
    else
        return false;
}

int BrooseBucket::longestPrefix ( void )

virtual

return the longest prefix of all entries

Returns: the longest prefix

Definition at line 202 of file BrooseBucket.cc.

{
    if (bucket.size() < 2)
        return 0;
    return bucket.begin()->second.getKey().sharedPrefixLength(
                                             (--bucket.end())->second.getKey());
}

virtual int BrooseBucket::numInitStages ( ) const

inlinevirtual

Definition at line 46 of file BrooseBucket.h.

    {
        return MAX_STAGE_OVERLAY + 1;
    }

void BrooseBucket::output ( int maxEntries = 0 )

displays the content of the bucket on standard out

Parameters

maxEntries the maximal number of entries which will be printed

Definition at line 211 of file BrooseBucket.cc.

{
    BrooseHandle node;
    OverlayKey dist;
    EV << "[BrooseBucket::output() @ " << overlay->getThisNode().getIp()
       << " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
       << "    BucketSize/MaxSize: " << bucket.size() << "/" << maxSize
       << endl;
    int max;
    max = bucket.size();
    if (maxEntries != 0 && maxEntries < max) {
        max = maxEntries;
    }
    int i;
    for (bucketIter = bucket.begin(), i = 0; i < max; bucketIter++, i++) {
        dist = bucketIter->first;
        node = bucketIter->second;
        EV << "    " << dist << " " << node.getKey() << " " << node.getIp() << " RTT: "
           << node.rtt << " LS: " << node.lastSeen
           << endl;
    }
}

void BrooseBucket::remove ( const NodeHandle & node )

virtual

removes a broose node handle from the bucket

Parameters

node	broose handle which will be removed

Definition at line 117 of file BrooseBucket.cc.

{
    unsigned int i = 0;
    for (bucketIter = bucket.begin(); bucketIter != bucket.end(); i++) {
        if (bucketIter->second.getIp() == node.getIp()) {
            if (isBBucket && (i < (maxSize/7))) {
                // call update() for removed sibling
                overlay->callUpdate(node, false);
                if (bucket.size() > (maxSize/7)) {
                    // new replacement sibling
                    overlay->callUpdate(get(maxSize/7), true);
                }
            }
            bucket.erase(bucketIter++);
        } else {
            ++bucketIter;
        }
    }
}

void BrooseBucket::resetFailedResponses ( const NodeHandle & node )

virtual

resets the counter of failed responses to a specific broose handle

Parameters

node	broose handle which counter will be reset

Definition at line 290 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            bucketIter->second.failedResponses = 0;
    }
}

void BrooseBucket::setLastSeen	(	const NodeHandle &	node,
		simtime_t	lastSeen
	)

virtual

updates the timestamp of a specific node

Parameters

node	broose handle to which the timestamp will be updated
lastSeen	timestamp of the last message

Definition at line 317 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp())
            bucketIter->second.lastSeen = time;
    }
}

void BrooseBucket::setRTT	(	const NodeHandle &	node,
		simtime_t	rpcRTT
	)

virtual

sets the round trip time to a specific broose handle

Parameters

node	broose handle to which the rtt will be stored
rpcRTT	rtt to the specific node

Definition at line 299 of file BrooseBucket.cc.

{
    for (bucketIter = bucket.begin(); bucketIter!=bucket.end(); bucketIter++) {
        if (node.getIp() == bucketIter->second.getIp()) {
            bucketIter->second.rtt = rpcRTT;
        }
    }
}