#include <Kademlia.h>

Inheritance diagram for Kademlia:

Public Member Functions
	Kademlia ()
	~Kademlia ()
void	initializeOverlay (int stage)
	Initializes derived-class-attributes.
void	finishOverlay ()
	collects statistical data in derived class
void	joinOverlay ()
	Join the overlay with a given nodeID in thisNode.key.
bool	isSiblingFor (const NodeHandle &node, const OverlayKey &key, int numSiblings, bool *err)
	Query if a node is among the siblings for a given key.
int	getMaxNumSiblings ()
	Query the maximum number of siblings (nodes close to a key) that are maintained by this overlay protocol.
int	getMaxNumRedundantNodes ()
	Query the maximum number of redundant next hop nodes that are returned by findNode().
void	handleTimerEvent (cMessage *msg)
bool	handleRpcCall (BaseCallMessage *msg)
	Processes Remote-Procedure-Call invocation messages.
void	handleUDPMessage (BaseOverlayMessage *msg)
	Processes messages from underlay.
virtual void	proxCallback (const TransportAddress &node, int rpcId, cPolymorphic *contextPointer, Prox prox)
Public Member Functions inherited from BaseOverlay
	BaseOverlay ()
virtual	~BaseOverlay ()
	Virtual destructor.
States	getState ()
bool	isMalicious ()
	Returns true, if node is malicious.
bool	isInSimpleMultiOverlayHost ()
	Returns true if overlay is one in an array, inside a SimpleMultiOverlayHost.
const simtime_t &	getCreationTime ()
void	join (const OverlayKey &nodeID=OverlayKey::UNSPECIFIED_KEY)
	Join the overlay with a given nodeID.
virtual NodeVector *	local_lookup (const OverlayKey &key, int num, bool safe)
	finds nodes closest to the given OverlayKey
virtual NodeVector *	neighborSet (int num)
void	sendMessageToUDP (const TransportAddress &dest, cPacket *msg, simtime_t delay=SIMTIME_ZERO)
	Sends message to underlay.
void	sendToKey (const OverlayKey &key, BaseOverlayMessage *message, int numSiblings=1, const std::vector< TransportAddress > &sourceRoute=TransportAddress::UNSPECIFIED_NODES, RoutingType routingType=DEFAULT_ROUTING)
	Sends a message to an overlay node, with the generic routing algorithm.
void	registerComp (CompType compType, cModule *module)
cModule *	getCompModule (CompType compType)
cGate *	getCompRpcGate (CompType compType)
void	sendMessageToAllComp (cMessage *msg, CompType srcComp)
bool	providesKbr ()
virtual uint8_t	getBitsPerDigit ()
bool	getMeasureAuthBlock ()
BootstrapList &	getBootstrapList () const
virtual OverlayKey	estimateMeanDistance ()
	returns mean distance between OverlayKeys in the network
virtual uint32_t	estimateOverlaySize ()
	estimates the current number of nodes online
Public Member Functions inherited from BaseRpc
	BaseRpc ()
const NodeHandle &	getThisNode ()
	Returns the NodeHandle of this node.
simtime_t	getUdpTimeout ()
Public Member Functions inherited from RpcListener
virtual	~RpcListener ()
	destructor
Public Member Functions inherited from BaseTcpSupport
virtual void	socketDataArrived (int connId, void yourPtr, cPacket msg, bool urgent)
virtual void	socketEstablished (int connId, void *yourPtr)
virtual void	socketPeerClosed (int connId, void *yourPtr)
virtual void	socketFailure (int connId, void *yourPtr, int code)
virtual void	socketStatusArrived (int connId, void yourPtr, TCPStatusInfo status)
Public Member Functions inherited from TopologyVis
	TopologyVis ()
void	showOverlayNeighborArrow (const NodeHandle &neighbor, bool flush=true, const char *displayString=NULL)
	Draws an arrow from this node to neighbor.
void	deleteOverlayNeighborArrow (const NodeHandle &neighbor)
	Removes an arrow from this node to neighbor.

Protected Member Functions
NodeVector *	findNode (const OverlayKey &key, int numRedundantNodes, int numSiblings, BaseOverlayMessage *msg)
	Implements the find node call.
void	handleRpcResponse (BaseResponseMessage msg, cPolymorphic context, int rpcId, simtime_t rtt)
	This method is called if an RPC response has been received.
void	handleRpcTimeout (BaseCallMessage msg, const TransportAddress &dest, cPolymorphic context, int rpcId, const OverlayKey &destKey)
	This method is called if an RPC timeout has been reached.
void	handleBucketRefreshTimerExpired ()
	handle a expired bucket refresh timer
OverlayKey	distance (const OverlayKey &x, const OverlayKey &y, bool useAlternative=false) const
	This method should implement the distance between two keys.
void	updateTooltip ()
	updates information shown in GUI
virtual void	lookupFinished (bool isValid)
virtual void	handleNodeGracefulLeaveNotification ()
	This method gets call **.gracefulLeaveDelay seconds before it is killed if this node is among the gracefulLeaveProbability nodes.
Protected Member Functions inherited from BaseOverlay
int	numInitStages () const
	Sets init stage.
void	bindToPort (int port)
	Tells UDP we want to get all packets arriving on the given port.
virtual void	route (const OverlayKey &key, CompType destComp, CompType srcComp, cPacket *msg, const std::vector< TransportAddress > &sourceRoute=TransportAddress::UNSPECIFIED_NODES, RoutingType routingType=DEFAULT_ROUTING)
	Routes message through overlay.
void	callDeliver (BaseOverlayMessage *msg, const OverlayKey &destKey)
	Calls deliver function in application.
void	callForward (const OverlayKey &key, BaseRouteMessage *msg, const NodeHandle &nextHopNode)
	Calls forward function in application.
void	callUpdate (const NodeHandle &node, bool joined)
	Informs application about state changes of nodes or newly joined nodes.
void	handleMessage (cMessage *msg)
	Checks for message type and calls corresponding method.
void	handleBaseOverlayMessage (BaseOverlayMessage *msg, const OverlayKey &destKey=OverlayKey::UNSPECIFIED_KEY)
	Handles a BaseOverlayMessage
virtual void	handleAppMessage (cMessage *msg)
	Processes "timer" self-messages.
virtual void	receiveChangeNotification (int category, const cPolymorphic *details)
	callback-method for events at the NotificationBoard
virtual void	handleTransportAddressChangedNotification ()
	This method gets call if the node has a new TransportAddress (IP address) because he changed his access network.
virtual void	handleNodeLeaveNotification ()
	This method gets call **.gracefulLeaveDelay seconds before it is killed.
virtual void	recordOverlaySentStats (BaseOverlayMessage *msg)
	Collect overlay specific sent messages statistics.
void	setOverlayReady (bool ready)
	Sets the overlay ready icon and register/deregisters the node at the GlobalNodeList.
virtual AbstractLookup *	createLookup (RoutingType routingType=DEFAULT_ROUTING, const BaseOverlayMessage msg=NULL, const cPacket findNodeExt=NULL, bool appLookup=false)
	Creates an abstract iterative lookup instance.
virtual void	removeLookup (AbstractLookup *lookup)
	Removes the abstract lookup instance.
virtual void	joinForeignPartition (const NodeHandle &node)
	Join another overlay partition with the given node as bootstrap node.
virtual bool	handleFailedNode (const TransportAddress &failed)
	Handles a failed node.
virtual void	lookupRpc (LookupCall *call)
virtual void	nextHopRpc (NextHopCall *call)
void	countFindNodeCall (const FindNodeCall *call)
void	countFailedNodeCall (const FailedNodeCall *call)
bool	internalHandleRpcCall (BaseCallMessage *msg)
	Handles internal rpc requests.
void	internalHandleRpcResponse (BaseResponseMessage msg, cPolymorphic context, int rpcId, simtime_t rtt)
	Handles rpc responses internal in base classes
void	internalHandleRpcTimeout (BaseCallMessage msg, const TransportAddress &dest, cPolymorphic context, int rpcId, const OverlayKey &destKey)
	Handles rpc timeouts internal in base classes
void	internalSendRouteRpc (BaseRpcMessage *message, const OverlayKey &destKey, const std::vector< TransportAddress > &sourceRoute, RoutingType routingType)
CompType	getThisCompType ()
	Return the component type of this module.
Protected Member Functions inherited from BaseRpc
void	initRpcs ()
	Initializes Remote-Procedure state.
void	finishRpcs ()
	Deinitializes Remote-Procedure state.
virtual void	internalHandleRpcMessage (BaseRpcMessage *msg)
	Handles incoming rpc messages and delegates them to the corresponding listeners or handlers.
uint32_t	sendRouteRpcCall (CompType destComp, const TransportAddress &dest, const OverlayKey &destKey, BaseCallMessage msg, cPolymorphic context=NULL, RoutingType routingType=DEFAULT_ROUTING, simtime_t timeout=-1, int retries=0, int rpcId=-1, RpcListener *rpcListener=NULL)
	Routes a Remote-Procedure-Call message to an OverlayKey.
uint32_t	sendRouteRpcCall (CompType destComp, const OverlayKey &destKey, BaseCallMessage msg, cPolymorphic context=NULL, RoutingType routingType=DEFAULT_ROUTING, simtime_t timeout=-1, int retries=0, int rpcId=-1, RpcListener *rpcListener=NULL)
	Routes a Remote-Procedure-Call message to an OverlayKey.
uint32_t	sendRouteRpcCall (CompType destComp, const TransportAddress &dest, BaseCallMessage msg, cPolymorphic context=NULL, RoutingType routingType=DEFAULT_ROUTING, simtime_t timeout=-1, int retries=0, int rpcId=-1, RpcListener *rpcListener=NULL)
	Sends a Remote-Procedure-Call message using the overlay's UDP port This replaces ROUTE_DIRECT calls!
uint32_t	sendUdpRpcCall (const TransportAddress &dest, BaseCallMessage msg, cPolymorphic context=NULL, simtime_t timeout=-1, int retries=0, int rpcId=-1, RpcListener *rpcListener=NULL)
	Sends a Remote-Procedure-Call message to the underlay
uint32_t	sendInternalRpcCall (CompType destComp, BaseCallMessage msg, cPolymorphic context=NULL, simtime_t timeout=-1, int retries=0, int rpcId=-1, RpcListener *rpcListener=NULL)
	Sends an internal Remote-Procedure-Call between two tiers
void	cancelRpcMessage (uint32_t nonce)
	Cancels a Remote-Procedure-Call.
void	cancelAllRpcs ()
	Cancels all RPCs.
void	sendRpcResponse (TransportType transportType, CompType destComp, const TransportAddress &dest, const OverlayKey &destKey, BaseCallMessage call, BaseResponseMessage response)
	Send Remote-Procedure response message and deletes call message.
void	sendRpcResponse (BaseCallMessage call, BaseResponseMessage response)
	Send Remote-Procedure response message to UDP and deletes call message.
int	pingNode (const TransportAddress &dest, simtime_t timeout=-1, int retries=0, cPolymorphic context=NULL, const char caption="PING", RpcListener *rpcListener=NULL, int rpcId=-1, TransportType transportType=INVALID_TRANSPORT)
	ping a node by its TransportAddress
virtual void	pingResponse (PingResponse pingResponse, cPolymorphic context, int rpcId, simtime_t rtt)
virtual void	pingTimeout (PingCall pingCall, const TransportAddress &dest, cPolymorphic context, int rpcId)
bool	internalHandleMessage (cMessage *msg)
Protected Member Functions inherited from RpcListener
virtual void	handleRpcResponse (BaseResponseMessage *msg, const RpcState &rpcState, simtime_t rtt)
	This method is called if an RPC response has been received.
virtual void	handleRpcTimeout (const RpcState &rpcState)
	This method is called if an RPC timeout has been reached.
Protected Member Functions inherited from BaseTcpSupport
void	handleTCPMessage (cMessage *msg)
	Member function to handle incoming TCP messages.
void	bindAndListenTcp (int port)
	Member function to bind service to the specified port and listen afterwards.
bool	isAlreadyConnected (TransportAddress address)
	Member function to check if the service is already connected.
void	establishTcpConnection (TransportAddress address)
	Member function to establish a connection to the specified node.
void	sendTcpData (cPacket *msg, TransportAddress address)
	Member function to send TCP data to the specified node.
virtual void	handleConnectionEvent (EvCode code, TransportAddress address)
	Member function to handle passive connection events.
virtual void	handleDataReceived (TransportAddress address, cPacket *msg, bool urgent)
	Member function to handle incoming data.
virtual void	handleIncomingConnection (TransportAddress address)
	Member function to handle newly opened connections.
void	closeTcpConnection (TransportAddress address)
	Member function to close an established connection.
void	setTcpOut (cGate *gate)
	Member function to set local gate towards the TCP module during init phase.
cGate *	getTcpOut ()
	Member function to get local gate towards the TCP module.
Protected Member Functions inherited from TopologyVis
void	initVis (cModule *terminal)

Protected Attributes
uint32_t	k
uint32_t	b
uint32_t	s
uint32_t	maxStaleCount
bool	exhaustiveRefresh
bool	pingNewSiblings
bool	secureMaintenance
	if true, ping not authenticated nodes before adding them to a bucket
bool	newMaintenance
bool	enableReplacementCache
bool	replacementCachePing
uint	replacementCandidates
int	siblingRefreshNodes
int	bucketRefreshNodes
bool	activePing
bool	proximityRouting
bool	proximityNeighborSelection
bool	altRecMode
simtime_t	minSiblingTableRefreshInterval
simtime_t	minBucketRefreshInterval
simtime_t	siblingPingInterval
cMessage *	bucketRefreshTimer
cMessage *	siblingPingTimer
Protected Attributes inherited from BaseOverlay
int	numAppDataForwarded
	number of forwarded app data packets
int	bytesAppDataForwarded
	number of forwarded app data bytes at out-gate
int	numAppLookupForwarded
	number of forwarded app lookup packets
int	bytesAppLookupForwarded
	number of forwarded app lookup bytes at out-gate
int	numMaintenanceForwarded
	number of forwarded maintenance packets
int	bytesMaintenanceForwarded
	number of forwarded maintenance bytes at out-gate
int	numFindNodeSent
int	bytesFindNodeSent
int	numFindNodeResponseSent
int	bytesFindNodeResponseSent
int	numFailedNodeSent
int	bytesFailedNodeSent
int	numFailedNodeResponseSent
int	bytesFailedNodeResponseSent
std::vector< HopDelayRecord * >	singleHopDelays
simtime_t	creationTime
	simtime when the node has been created
GlobalNodeList *	globalNodeList
	pointer to GlobalNodeList in this node
NotificationBoard *	notificationBoard
	pointer to NotificationBoard in this node
UnderlayConfigurator *	underlayConfigurator
	pointer to UnderlayConfigurator in this node
BootstrapList *	bootstrapList
	pointer to the BootstrapList module
GlobalParameters *	globalParameters
	pointer to the GlobalParameters module
uint32_t	overlayId
	identifies the overlay this node belongs to (used for multiple overlays)
bool	debugOutput
	debug output ?
RoutingType	defaultRoutingType
bool	useCommonAPIforward
	forward messages to applications?
bool	collectPerHopDelay
	collect delay for single hops
bool	routeMsgAcks
	send ACK when receiving route message
uint32_t	recNumRedundantNodes
	numRedundantNodes for recursive routing
bool	recordRoute
	record visited hops on route
bool	drawOverlayTopology
bool	rejoinOnFailure
bool	sendRpcResponseToLastHop
	needed by KBR protocols for NAT support
bool	dropFindNodeAttack
	if node is malicious, it tries a findNode attack
bool	isSiblingAttack
	if node is malicious, it tries a isSibling attack
bool	invalidNodesAttack
	if node is malicious, it tries a invalidNode attack
bool	dropRouteMessageAttack
	if node is malicious, it drops all received BaseRouteMessages
int	localPort
	used UDP-port
int	hopCountMax
	maximum hop count
bool	measureAuthBlock
	if true, measure the overhead of signatures in rpc messages
bool	restoreContext
	if true, a node rejoins with its old nodeId and malicious state
int	numDropped
	number of dropped packets
int	bytesDropped
	number of dropped bytes
cOutVector	delayVector
	statistical output vector for packet-delays
cOutVector	hopCountVector
	statistical output vector for hop-counts
States	state
IterativeLookupConfiguration	iterativeLookupConfig
RecursiveLookupConfiguration	recursiveLookupConfig
LookupSet	lookups
bool	kbr
	set this to true, if the overlay provides KBR services
Protected Attributes inherited from BaseRpc
NodeHandle	thisNode
	NodeHandle to this node.
BaseOverlay *	overlay
bool	debugOutput
	debug output ?
GlobalStatistics *	globalStatistics
	pointer to GlobalStatistics module in this node
CompType	thisCompType
NeighborCache *	neighborCache
	pointer to the neighbor cache
CryptoModule *	cryptoModule
	pointer to CryptoModule
int	numPingSent
int	bytesPingSent
int	numPingResponseSent
int	bytesPingResponseSent
Protected Attributes inherited from TopologyVis
cModule *	thisTerminal
GlobalNodeList *	globalNodeList
	pointer to corresponding node

Private Member Functions
void	routingInit ()
void	routingDeinit ()
int	routingBucketIndex (const OverlayKey &key, bool firstOnLayer=false)
	Returns the index of the bucket the key would reside with respect to Kademlia parameters.
KademliaBucket *	routingBucket (const OverlayKey &key, bool ensure)
	Returns a Bucket or `NULL` if the bucket has not yet allocated.
bool	routingAdd (const NodeHandle &handle, bool isAlive, simtime_t rtt=MAXTIME, bool maintenanceLookup=false)
	Adds a node to the routing table.
bool	routingTimeout (const OverlayKey &key, bool immediately=false)
	Removes a node after a number of timeouts or immediately if immediately is true (behaves like routingRemove).
void	refillSiblingTable ()
void	sendSiblingFindNodeCall (const TransportAddress &dest)
void	setBucketUsage (const OverlayKey &key)
bool	recursiveRoutingHook (const TransportAddress &dest, BaseRouteMessage *msg)
bool	handleFailedNode (const TransportAddress &failed)

Private Attributes
uint32_t	bucketRefreshCount
uint32_t	siblingTableRefreshCount
uint32_t	nodesReplaced
KeyDistanceComparator < KeyXorMetric > *	comparator
KademliaBucket *	siblingTable
std::vector< KademliaBucket * >	routingTable
int	numBuckets

Friends
class	KademliaLookupListener

Additional Inherited Members
Public Types inherited from BaseOverlay
enum	States { INIT = 0, BOOTSTRAP = 1, DISCOVERY = 2, PREJOIN = 3, JOIN = 4, POSTJOIN = 5, READY = 6, REFRESH = 7, SHUTDOWN = 8, FAILED = 9, RSET = JOIN, BSET = POSTJOIN }
Protected Types inherited from BaseOverlay
typedef UNORDERED_SET < AbstractLookup *, lookupHashFcn, lookupHashFcn >	LookupSet

Detailed Description

Kademlia overlay module.

Author: Sebastian Mies, Ingmar Baumgart, Bernhard Heep

This class implements the Kademlia protocol described in P. Maymounkov and D. Mazières, "Kademlia: A Peer-to-Peer Information System Based on the XOR Metric", Lecture Notes in Computer Science, Peer-to-Peer Systems: First International Workshop (IPTPS 2002). Revised Papers, 2002, 2429/2002, 53-65

The recursive routing mode (R/Kademlia) is described in B. Heep, "R/Kademlia: Recursive and Topology-aware Overlay Routing", Proceedings of the Australasian Telecommunication Networks and Applications Conference 2010 (ATNAC 2010), Auckland, New Zealand, 2010

The security extensions (S/Kademlia) are described in I. Baumgart and S. Mies, "S/Kademlia: A Practicable Approach Towards Secure Key-Based Routing", Proceedings of the 13th International Conference on Parallel and Distributed Systems (ICPADS '07), Hsinchu, Taiwan, 2007

Definition at line 61 of file Kademlia.h.

Constructor & Destructor Documentation

Kademlia::Kademlia ( )

Definition at line 162 of file Kademlia.cc.

{
    siblingTable = NULL;
    comparator = NULL;
    bucketRefreshTimer = NULL;
    siblingPingTimer = NULL;
}

Kademlia::~Kademlia ( )

Definition at line 170 of file Kademlia.cc.

{
    routingDeinit();
    delete siblingTable;
    delete comparator;
    cancelAndDelete(bucketRefreshTimer);
    cancelAndDelete(siblingPingTimer);
}

Member Function Documentation

OverlayKey Kademlia::distance	(	const OverlayKey &	x,
		const OverlayKey &	y,
		bool	useAlternative = `false`
	)		const

protectedvirtual

This method should implement the distance between two keys.

It may be overloaded to implement a new metric. The default implementation uses the standard-metric d = abs(x-y).

Parameters

x	Left-hand-side Key
y	Right-hand-side key
useAlternative	use an alternative distance metric

Returns: OverlayKey Distance between x and y

Reimplemented from BaseOverlay.

Definition at line 1421 of file Kademlia.cc.

{
    if (!useAlternative) return x^y; // KeyXorMetric().distance(x, y);
    return KeyPrefixMetric().distance(x, y);
}

NodeVector * Kademlia::findNode	(	const OverlayKey &	key,
		int	numRedundantNodes,
		int	numSiblings,
		BaseOverlayMessage *	msg
	)

protectedvirtual

Implements the find node call.

This method simply returns the closest nodes known in the corresponding routing topology. If the node is a sibling for this key (isSiblingFor(key) = true), this method returns all numSiblings siblings, with the closest neighbor to the key first.

Parameters

key	The lookup key.
numRedundantNodes	Maximum number of next hop nodes to return.
numSiblings	number of siblings to return
msg	A pointer to the BaseRouteMessage or FindNodeCall message of this lookup.

Returns: NodeVector with closest nodes.

Reimplemented from BaseOverlay.

Definition at line 969 of file Kademlia.cc.

Referenced by recursiveRoutingHook().

{
    if (numSiblings > getMaxNumSiblings()) {
        opp_error("(Kademlia::findNode()) numRedundantNodes or numSiblings "
                  "too big!");
    }
#if 0
    if (numRedundantNodes < 2) {
        throw cRuntimeError("Kademlia::findNode(): For Kademlia "
                                "redundantNodes must be at least 2 "
                                "and lookupMerge should be true!");
    }
#endif
    // create temporary comparator
    KeyDistanceComparator<KeyXorMetric>* comp =
        new KeyDistanceComparator<KeyXorMetric>( key );
    // select result set size
    bool err;
    int resultSize;
    if (numSiblings < 0) {
        // exhaustive iterative doesn't care about siblings
        resultSize = numRedundantNodes;
    } else {
        resultSize = isSiblingFor(thisNode, key, numSiblings, &err) ?
                (numSiblings ? numSiblings : 1) : numRedundantNodes;
    }
    assert(numSiblings || numRedundantNodes);
    NodeVector* result = new NodeVector(resultSize, comp);
    if (siblingTable->isEmpty()) {
        result->add(thisNode);
        delete comp;
        return result;
    }
    // R/Kademlia: in recursive mode just speed up route messages //TODO iterative PR
    bool returnProxNodes = false;
    if (proximityRouting) {
        if (msg &&
            (!dynamic_cast<FindNodeCall*>(msg->getEncapsulatedPacket()) &&
             !dynamic_cast<FindNodeCall*>(msg))) {
            returnProxNodes = true;
        }
    }
    ProxNodeVector* resultProx = NULL;
    KademliaPRComparator* compProx = NULL;
    if (returnProxNodes) {
        compProx = new KademliaPRComparator(key);
        resultProx = new ProxNodeVector(resultSize, NULL, NULL, compProx, 0, resultSize);
    }
    // add items from buckets
    int index;
    int mainIndex = routingBucketIndex(key);
    int startIndex = routingBucketIndex(key, true);
    int endIndex = routingBucketIndex(siblingTable->back().getKey());
    // add nodes from best fitting bucket
    if (mainIndex != -1) {
        KademliaBucket* bucket = routingTable[mainIndex];
        if (bucket != NULL && bucket->size()) {
            for (KademliaBucket::iterator i=bucket->begin(); i!=bucket->end(); i++) {
                result->add(*i);
                if (returnProxNodes)
                    resultProx->add(*i);
                //EV << "Kademlia::findNode(): Adding "
                //   << *i << " from bucket " << mainIndex << endl;
            }
        }
    }
    // add most fitting buckets
    if (startIndex >= endIndex || !result->isFull()) {
        for (index = startIndex; index >= endIndex; --index) {
            // add bucket to result vector
            if (index == mainIndex) continue;
            KademliaBucket* bucket = routingTable[index];
            if (bucket != NULL && bucket->size()) {
                for (KademliaBucket::iterator i=bucket->begin(); i!=bucket->end(); i++) {
                    result->add(*i);
                    if (returnProxNodes)
                        resultProx->add(*i);//std::make_pair(*i, i->getRtt()));
                    //EV << "Kademlia::routingGetClosestNodes(): Adding "
                    //   << *i << " from bucket " << index << endl;
                }
            }
        }
        // add nodes from sibling table
        for (KademliaBucket::iterator i = siblingTable->begin();
             i != siblingTable->end(); i++) {
            result->add(*i);
            if (returnProxNodes)
                resultProx->add(*i);
        }
        // add local node
        result->add(thisNode);
        if (returnProxNodes) {
            KademliaBucketEntry temp = thisNode;
            if (!result->size() || (*result)[0] == thisNode) {
                temp.setProx(Prox::PROX_SELF);
                resultProx->add(temp);
            } else {
                temp.setProx(Prox::PROX_UNKNOWN);
                resultProx->add(temp);
            }
        }
    }
    // add more distant buckets
    for (index = mainIndex + 1; !result->isFull() && index < numBuckets;
         ++index) {
        // add bucket to result vector
        KademliaBucket* bucket = routingTable[index];
        if (bucket != NULL && bucket->size()) {
            for (KademliaBucket::iterator i=bucket->begin(); i!=bucket->end(); i++) {
                result->add(*i);
                if (returnProxNodes)
                    resultProx->add(*i);
                //EV << "[Kademlia::routingGetClosestNodes()]\n"
                //   << "    Adding " << *i << " from bucket " << index
                //   << endl;
            }
        }
    }
    if (returnProxNodes && resultProx->size() && result->size() &&
        (KeyPrefixMetric().distance(key, (*resultProx)[0].getKey()) <
         KeyPrefixMetric().distance(key, (*result)[0].getKey()))) {
        result->clear();
        for (uint32_t i = 0; i < resultProx->size(); ++i) {
            result->push_back((*resultProx)[i]/*.first*/);
        }
    }
    delete compProx;
    delete resultProx;
    delete comp;
    return result;
}

void Kademlia::finishOverlay ( )

virtual

collects statistical data in derived class

Reimplemented from BaseOverlay.

Definition at line 180 of file Kademlia.cc.

{
    simtime_t time = globalStatistics->calcMeasuredLifetime(creationTime);
    if (time < GlobalStatistics::MIN_MEASURED) return;
    globalStatistics->addStdDev("Kademlia: Nodes replaced in buckets/s",
                                nodesReplaced / time);
    globalStatistics->addStdDev("Kademlia: Bucket Refreshes/s",
                                bucketRefreshCount / time);
    globalStatistics->addStdDev("Kademlia: Sibling Table Refreshes/s",
                                siblingTableRefreshCount / time);
}

int Kademlia::getMaxNumRedundantNodes ( )

virtual

Query the maximum number of redundant next hop nodes that are returned by findNode().

Returns: int number of redundant nodes returned by findNode().

Reimplemented from BaseOverlay.

Definition at line 280 of file Kademlia.cc.

{
    return k;
}

int Kademlia::getMaxNumSiblings ( )

virtual

Query the maximum number of siblings (nodes close to a key) that are maintained by this overlay protocol.

Returns: int number of siblings.

Reimplemented from BaseOverlay.

Definition at line 275 of file Kademlia.cc.

Referenced by findNode(), isSiblingFor(), sendSiblingFindNodeCall(), and setBucketUsage().

{
    return s;
}

void Kademlia::handleBucketRefreshTimerExpired ( )

protected

handle a expired bucket refresh timer

Definition at line 1323 of file Kademlia.cc.

Referenced by handleTimerEvent().

{
    // refresh buckets
    if (state != READY || (((simTime() - siblingTable->getLastUsage()) >
                            minSiblingTableRefreshInterval))) {
        // R/Kademlia
        if (defaultRoutingType == SEMI_RECURSIVE_ROUTING ||
            defaultRoutingType == FULL_RECURSIVE_ROUTING ||
            defaultRoutingType == RECURSIVE_SOURCE_ROUTING) {
            //TODO real exhaustive-recursive lookup
            createLookup()->lookup(getThisNode().getKey() + OverlayKey::ONE,
                                   0, hopCountMax, 0,
                                   new KademliaLookupListener(this));
        } else if (exhaustiveRefresh) {
            //TODO config shit
            int baseRedundantNodes = iterativeLookupConfig.redundantNodes;
            iterativeLookupConfig.redundantNodes = siblingRefreshNodes;
            createLookup(EXHAUSTIVE_ITERATIVE_ROUTING)->lookup(
                 getThisNode().getKey(), siblingRefreshNodes,
                 hopCountMax, 0, new KademliaLookupListener(this));
            iterativeLookupConfig.redundantNodes = baseRedundantNodes;
        } else if (newMaintenance) {
            //for (KademliaBucket::iterator i = siblingTable->begin();
            //     i != siblingTable->end(); i++) {
            //    sendSiblingFindNodeCall(*i);
            //}
            if (siblingTable->size()) {
                sendSiblingFindNodeCall(siblingTable->at(intuniform(0,siblingTable->size()-1)));
            }
            state = READY;
            setOverlayReady(true);
        } else {
            createLookup()->lookup(getThisNode().getKey(), s, hopCountMax, 0,
                                   new KademliaLookupListener(this));
        }
        siblingTable->setLastUsage(simTime());
        ++siblingTableRefreshCount;
    }
    if (state == READY) {
        if (siblingTable->size()) {
            // get bit index of most significant digit that differs
            // from our next sibling's key to prevent us from refreshing
            // buckets, which can't contain any nodes
            int32_t diff = OverlayKey::getLength() - b*(getThisNode().getKey().
                sharedPrefixLength(siblingTable->front().getKey(), b) + 1);
            int bucketsRefreshedPerTask = 0;
            for (int32_t i = OverlayKey::getLength() - b; i >= diff; i -=b ) {
                for (int32_t d=0; d < ((1 << b) - 1); d++) {
                    int32_t index = (i / b) * ((1 << b) - 1) + d;
                    if (index < 0) continue;
                    if ((routingTable[index] == NULL) ||
                        ((simTime() - routingTable[index]->getLastUsage()) >
                        minBucketRefreshInterval)) {
                        OverlayKey refreshKey =
                            getThisNode().getKey() ^ (OverlayKey(d+1) << i);
                        // R/Kademlia
                        if (defaultRoutingType == SEMI_RECURSIVE_ROUTING ||
                            defaultRoutingType == FULL_RECURSIVE_ROUTING ||
                            defaultRoutingType == RECURSIVE_SOURCE_ROUTING) {
                            //TODO real exhaustive-recursive lookup
                            createLookup()->lookup(refreshKey, 0,
                                                   hopCountMax, 0,
                                                   new KademliaLookupListener(this));
                        } else if (exhaustiveRefresh) {
                            //TODO config shit
                            int baseRedundantNodes = iterativeLookupConfig.redundantNodes;
                            iterativeLookupConfig.redundantNodes = bucketRefreshNodes;
                            createLookup(EXHAUSTIVE_ITERATIVE_ROUTING)->lookup(
                                refreshKey, bucketRefreshNodes, hopCountMax,
                                0, new KademliaLookupListener(this));
                            iterativeLookupConfig.redundantNodes = baseRedundantNodes;
                        } else {
                            createLookup()->lookup(refreshKey, s, hopCountMax, 0,
                                             new KademliaLookupListener(this));
                        }
                        ++bucketsRefreshedPerTask;
                        ++bucketRefreshCount;
                        setBucketUsage(refreshKey);
                    }
                }
            }
            RECORD_STATS(globalStatistics->recordOutVector(
                                   "Kademlia: Buckets Refreshed Per Task",
                                   bucketsRefreshedPerTask));
        }
        // schedule next bucket refresh process
        cancelEvent(bucketRefreshTimer);
        scheduleAt(simTime() + (std::min(minSiblingTableRefreshInterval,
                        minBucketRefreshInterval) / 10.0), bucketRefreshTimer);
    }
}

bool Kademlia::handleFailedNode ( const TransportAddress & failed )

private

Definition at line 846 of file Kademlia.cc.

{
    assert(!failed.isUnspecified());
    KademliaBucket::iterator i;
    // check sibling table
    for (i = siblingTable->begin(); i != siblingTable->end(); ++i) {
        if (failed == *i) break;
    }
    if (i != siblingTable->end()) {
        // remove from sibling table
        NodeHandle oldSibling = *i;
        siblingTable->erase(i);
        // call update() for removed sibling
        deleteOverlayNeighborArrow(oldSibling);
        callUpdate(oldSibling, false);
        updateTooltip();
        // try to refill with new closest contact
        refillSiblingTable();
    } else {
        // check buckets
        uint32_t m;
        for (m = 0; m < routingTable.size(); ++m) {
            if (routingTable[m] != NULL) {
                for (i = routingTable[m]->begin(); i != routingTable[m]->end();
                     ++i) {
                    if (failed == *i) {
                        // remove from routing table
                        routingTable[m]->erase(i);
                        return (siblingTable->size() != 0);
                    }
                }
            }
        }
    }
    return (siblingTable->size() != 0);
}

void Kademlia::handleNodeGracefulLeaveNotification ( )

protectedvirtual

This method gets call **.gracefulLeaveDelay seconds before it is killed if this node is among the gracefulLeaveProbability nodes.

Reimplemented from BaseOverlay.

Definition at line 831 of file Kademlia.cc.

{
    // send failed node call to all siblings
    FailedNodeCall* call = new FailedNodeCall();
    call->setFailedNode(getThisNode());
    call->setBitLength(FAILEDNODECALL_L(call));
    for (KademliaBucket::iterator i = siblingTable->begin();
         i != siblingTable->end(); i++) {
        countFailedNodeCall(call);
        sendUdpRpcCall(*i, call->dup());
    }
    delete call;
}

bool Kademlia::handleRpcCall ( BaseCallMessage * msg )

virtual

Processes Remote-Procedure-Call invocation messages.

This method should be overloaded when the overlay provides RPC functionality.

Returns: true, if rpc has been handled

Reimplemented from BaseRpc.

Definition at line 1159 of file Kademlia.cc.

{
    bool maintenanceLookup = (msg->getStatType() == MAINTENANCE_STAT);
    RPC_SWITCH_START(msg)
    RPC_ON_CALL(Ping) {
        // add active node
        OverlayCtrlInfo* ctrlInfo =
            check_and_cast<OverlayCtrlInfo*>(msg->getControlInfo());
        routingAdd(ctrlInfo->getSrcRoute(), true, MAXTIME, maintenanceLookup);
        break;
    }
    RPC_ON_CALL(FindNode)
    {
        // add active node
        OverlayCtrlInfo* ctrlInfo =
            check_and_cast<OverlayCtrlInfo*>(msg->getControlInfo());
        routingAdd(ctrlInfo->getSrcRoute(), true, MAXTIME, maintenanceLookup);
        break;
    }
    RPC_SWITCH_END()
    return false;
}

void Kademlia::handleRpcResponse	(	BaseResponseMessage *	msg,
		cPolymorphic *	context,
		int	rpcId,
		simtime_t	rtt
	)

protectedvirtual

This method is called if an RPC response has been received.

Parameters

msg	The response message.
context	Pointer to an optional state object. The object has to be handled/deleted by the handleRpcResponse() code
rpcId	The RPC id.
rtt	The Round-Trip-Time of this RPC

Reimplemented from RpcListener.

Definition at line 1183 of file Kademlia.cc.

{
    bool maintenanceLookup = (msg->getStatType() == MAINTENANCE_STAT);
    OverlayCtrlInfo* ctrlInfo =
        dynamic_cast<OverlayCtrlInfo*>(msg->getControlInfo());
    NodeHandle srcRoute = (ctrlInfo ? ctrlInfo->getSrcRoute()
                                    : msg->getSrcNode());
    RPC_SWITCH_START(msg)
        RPC_ON_RESPONSE(Ping) {
            if (state == INIT) {
                // schedule bucket refresh timer
                cancelEvent(bucketRefreshTimer);
                scheduleAt(simTime(), bucketRefreshTimer);
                cancelEvent(siblingPingTimer);
                scheduleAt(simTime() + siblingPingInterval, siblingPingTimer);
                state = JOIN;
            }
        }
        RPC_ON_RESPONSE(FindNode)
        {
            if (state == INIT) {
                state = JOIN;
                // bootstrap node is trustworthy: add all nodes immediately
                routingAdd(srcRoute, true, rtt, maintenanceLookup);
                for (uint32_t i=0; i<_FindNodeResponse->getClosestNodesArraySize(); i++)
                    routingAdd(_FindNodeResponse->getClosestNodes(i), true,
                               MAXTIME-1, maintenanceLookup);
                if (newMaintenance) {
                    createLookup()->lookup(getThisNode().getKey(), s, hopCountMax, 0,
                                       new KademliaLookupListener(this));
                } else {
                    // schedule bucket refresh timer
                    cancelEvent(bucketRefreshTimer);
                    scheduleAt(simTime(), bucketRefreshTimer);
                    cancelEvent(siblingPingTimer);
                    scheduleAt(simTime() + siblingPingInterval, siblingPingTimer);
                }
                break;
            }
            // add active node
            if (defaultRoutingType == SEMI_RECURSIVE_ROUTING ||
                defaultRoutingType == FULL_RECURSIVE_ROUTING ||
                defaultRoutingType == RECURSIVE_SOURCE_ROUTING) {
                rtt = MAXTIME;
            }
            setBucketUsage(srcRoute.getKey());
            // add inactive nodes
            for (uint32_t i=0; i<_FindNodeResponse->getClosestNodesArraySize(); i++)
                routingAdd(_FindNodeResponse->getClosestNodes(i), false,
                           MAXTIME, maintenanceLookup);
            break;
        }
    RPC_SWITCH_END()
    // add node that responded
    routingAdd(srcRoute, true, rtt, maintenanceLookup);
}

void Kademlia::handleRpcTimeout	(	BaseCallMessage *	msg,
		const TransportAddress &	dest,
		cPolymorphic *	context,
		int	rpcId,
		const OverlayKey &	destKey
	)

protectedvirtual

This method is called if an RPC timeout has been reached.

Parameters

msg	The original RPC message.
dest	The destination node
context	Pointer to an optional state object. The object has to be handled/deleted by the handleRpcResponse() code
rpcId	The RPC id.
destKey	the destination OverlayKey

Reimplemented from RpcListener.

Definition at line 1250 of file Kademlia.cc.

{
    if (dest.isUnspecified()) return;
    try {
        RPC_SWITCH_START(msg)
        RPC_ON_CALL(Ping) {
            if (state == INIT) {
                joinOverlay();
                return;
            }
            const NodeHandle& handle = dynamic_cast<const NodeHandle&>(dest);
            routingTimeout(handle.getKey());
            break;
        }
        RPC_ON_CALL(FindNode) {
            if (state == INIT) {
                joinOverlay();
                return;
            }
            const NodeHandle& handle = dynamic_cast<const NodeHandle&>(dest);
            routingTimeout(handle.getKey());
            setBucketUsage(handle.getKey());
            break;
        }
        RPC_SWITCH_END()
    } catch (...) {
        EV << "[Kademlia:handleRpcTimout() @ " << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    ERROR: RPC timeout without key ("
           << msg << " -> " << dest << ")" << endl;
        return;
    }
}

void Kademlia::handleTimerEvent ( cMessage * msg )

virtual

Reimplemented from BaseRpc.

Definition at line 1121 of file Kademlia.cc.

{
    if (msg == bucketRefreshTimer) {
        handleBucketRefreshTimerExpired();
    } else if (msg == siblingPingTimer) {
        if (siblingPingInterval == 0) {
            return;
        }
        for (KademliaBucket::iterator i = siblingTable->begin();
             i != siblingTable->end(); i++) {
            pingNode(*i);
        }
        scheduleAt(simTime() + siblingPingInterval, msg);
    }
}

void Kademlia::handleUDPMessage ( BaseOverlayMessage * msg )

virtual

Processes messages from underlay.

Parameters

msg	Message from UDP

Reimplemented from BaseOverlay.

Definition at line 1139 of file Kademlia.cc.

{
    // only used for recursive Kademlia
    OverlayCtrlInfo* ctrlInfo =
            check_and_cast<OverlayCtrlInfo*>(msg->removeControlInfo());
    KademliaRoutingInfoMessage* kadRoutingInfoMsg =
            check_and_cast<KademliaRoutingInfoMessage*>(msg);
    routingAdd(kadRoutingInfoMsg->getSrcNode(), true);
    for (uint32_t i = 0; i < kadRoutingInfoMsg->getNextHopsArraySize(); i++) {
        routingAdd(kadRoutingInfoMsg->getNextHops(i),
                   kadRoutingInfoMsg->getNextHops(i).getIsAlive());
    }
    delete ctrlInfo;
    delete msg;
}

void Kademlia::initializeOverlay ( int stage )

virtual

Initializes derived-class-attributes.

Initializes derived-class-attributes, called by BaseOverlay::initialize(). By default this method is called once. If more stages are needed one can overload numInitStages() and add more stages.

Parameters

stage the init stage

Reimplemented from BaseOverlay.

Definition at line 95 of file Kademlia.cc.

{
    if (stage != MIN_STAGE_OVERLAY)
        return;
    // Kademlia provides KBR services
    kbr = true;
    // setup kademlia parameters
    minSiblingTableRefreshInterval = par("minSiblingTableRefreshInterval");
    minBucketRefreshInterval = par("minBucketRefreshInterval");
    siblingPingInterval = par("siblingPingInterval");
    exhaustiveRefresh = par("exhaustiveRefresh");
    maxStaleCount = par("maxStaleCount");
    pingNewSiblings = par("pingNewSiblings");
    enableReplacementCache = par("enableReplacementCache");
    replacementCachePing = par("replacementCachePing");
    replacementCandidates = par("replacementCandidates");
    secureMaintenance = par("secureMaintenance");
    newMaintenance = par("newMaintenance");
    // R/Kademlia
    activePing = par("activePing");
    proximityRouting = par("proximityRouting");
    proximityNeighborSelection = par("proximityNeighborSelection");
    altRecMode = recordRoute = par("altRecMode");
    k = par("k");
    b = par("b");
    s = par("s");
    siblingRefreshNodes = par("siblingRefreshNodes");
    if (siblingRefreshNodes <= 0) {
        siblingRefreshNodes = 5 * s;
    }
    bucketRefreshNodes = par("bucketRefreshNodes");
    if (bucketRefreshNodes <= 0) {
        bucketRefreshNodes = iterativeLookupConfig.redundantNodes;
    }
    // calculate number of buckets: ( (2^b)-1 ) * ( keylength / b )
    numBuckets = ((1L << b) - 1L) * (OverlayKey::getLength() / b);
    // init routing and sibling table
    siblingTable = new KademliaBucket(s * 5, NULL);
    // initialize pointers
    routingTable.assign(numBuckets, (KademliaBucket*)NULL);
    WATCH_VECTOR(*siblingTable);
    WATCH_VECTOR(routingTable);
    // self-message
    bucketRefreshTimer = new cMessage("bucketRefreshTimer");
    siblingPingTimer = new cMessage("siblingPingTimer");
    // statistics
    bucketRefreshCount = 0;
    siblingTableRefreshCount = 0;
    nodesReplaced = 0;
    comparator = NULL;
}

bool Kademlia::isSiblingFor	(	const NodeHandle &	node,
		const OverlayKey &	key,
		int	numSiblings,
		bool *	err
	)

virtual

Query if a node is among the siblings for a given key.

Query if a node is among the siblings for a given key. This means, that the nodeId of this node is among the closest numSiblings nodes to the key and that by a local findNode() call all other siblings to this key can be retrieved.

Parameters

node	the NodeHandle
key	destination key
numSiblings	The nodes knows all numSiblings nodes close to this key
err	return false if the range could not be determined

Returns: bool true, if the node is responsible for the key.

Reimplemented from BaseOverlay.

Definition at line 755 of file Kademlia.cc.

Referenced by findNode().

{
    if (key.isUnspecified())
        error("Kademlia::isSiblingFor(): key is unspecified!");
    if (state != READY) {
        EV << "[Kademlia::isSiblingFor()] @ "
           << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    state != READY"
           << endl;
        *err = true;
        return false;
    }
    if (numSiblings > getMaxNumSiblings()) {
        opp_error("Kademlia::isSiblingFor(): numSiblings too big!");
    }
    // set default number of siblings to consider
    if (numSiblings == -1) {
        numSiblings = getMaxNumSiblings();
    }
    if (numSiblings == 0) {
        *err = false;
        return (node.getKey() == key);
    }
    if (siblingTable->size() < (uint)numSiblings) {
        *err = false;
        return true;
    }
    if (siblingTable->isFull() &&
        ((thisNode.getKey() ^ key) >
         (thisNode.getKey() ^ siblingTable->back().getKey()))) {
        EV << "[Kademlia::isSiblingFor()] @ "
           << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    Not sure if I am sibling for " << key << " !\n"
           << "    (" << key << " is not closer to me than "
           << siblingTable->back().getKey() << ")"
           << endl;
        *err = true;
        return false;
    }
    KeyDistanceComparator<KeyXorMetric>* comp =
        new KeyDistanceComparator<KeyXorMetric>(key);
    // create result vector
    NodeVector* result = new NodeVector(numSiblings, comp);
    for (KademliaBucket::iterator i=siblingTable->begin();
         i != siblingTable->end(); i++) {
        result->add( *i);
    }
    // add local node
    result->add(thisNode);
    *err = false;
    delete comp;
    if (result->contains(node.getKey())) {
        delete result;
        return true;
    } else {
        delete result;
        assert(!(numSiblings == 1 && key == node.getKey()));
        return false;
    }
}

void Kademlia::joinOverlay ( )

virtual

Join the overlay with a given nodeID in thisNode.key.

Join the overlay with a given nodeID in thisNode.key. This method may be called by an application to join the overlay with a specific nodeID. It is also called if the node's IP address changes.

Reimplemented from BaseOverlay.

Definition at line 204 of file Kademlia.cc.

Referenced by handleRpcTimeout(), and lookupFinished().

{
    // remove current node handle from the bootstrap list
    if (!thisNode.getKey().isUnspecified()) {
        bootstrapList->removeBootstrapNode(thisNode);
    }
    // initialize routing
    routingDeinit();
    routingInit();
    TransportAddress handle = bootstrapList->getBootstrapNode();
    if (!handle.isUnspecified()) {
        if (secureMaintenance) {
            sendSiblingFindNodeCall(handle);
        } else {
            // ping the bootstrap node to start bootstrapping
            pingNode(handle);
        }
    } else {
        // we're the only node in the network
        state = READY;
        setOverlayReady(true);
        // schedule bucket refresh timer
        cancelEvent(bucketRefreshTimer);
        scheduleAt(simTime(), bucketRefreshTimer);
        cancelEvent(siblingPingTimer);
        scheduleAt(simTime() + siblingPingInterval, siblingPingTimer);
    }
}

void Kademlia::lookupFinished ( bool isValid )

protectedvirtual

Definition at line 1302 of file Kademlia.cc.

Referenced by KademliaLookupListener::lookupFinished().

{
    if (state == JOIN) {
        cancelEvent(bucketRefreshTimer);
        if (siblingTable->size() == 0) {
            // initial lookup failed - get new bootstrap node
            joinOverlay();
            return;
        }
        scheduleAt(simTime(), bucketRefreshTimer);
        if (!newMaintenance) {
            state = READY;
            setOverlayReady(true);
        }
    }
}

void Kademlia::proxCallback	(	const TransportAddress &	node,
		int	rpcId,
		cPolymorphic *	contextPointer,
		Prox	prox
	)

virtual

Implements ProxListener.

Definition at line 1290 of file Kademlia.cc.

{
    Enter_Method_Silent();
    if (prox != Prox::PROX_TIMEOUT) {
        routingAdd((const NodeHandle&)node, true, prox.proximity);
    } else {
        routingTimeout(((const NodeHandle&)node).getKey());
    }
}

bool Kademlia::recursiveRoutingHook	(	const TransportAddress &	dest,
		BaseRouteMessage *	msg
	)

private

Definition at line 889 of file Kademlia.cc.

{
    if (msg->getSrcNode() != thisNode) {
        if (!msg->getDestKey().isUnspecified()) {
            routingAdd(msg->getSrcNode(), true);
            if (altRecMode && dest != thisNode) return true;
            NodeVector* nextHops = findNode(msg->getDestKey(), /*recursiveLookupConfig.redundantNodes*/ k, s, msg);
            KademliaRoutingInfoMessage* kadRoutingInfoMsg =
                new KademliaRoutingInfoMessage();
            kadRoutingInfoMsg->setSrcNode(thisNode);
            kadRoutingInfoMsg->setDestKey(msg->getDestKey());
            kadRoutingInfoMsg->setNextHopsArraySize(nextHops->size());
            kadRoutingInfoMsg->setName("KadRoutingInfoMsg");
            for (uint32_t i = 0; i < nextHops->size(); i++) {
                kadRoutingInfoMsg->setNextHops(i, (*nextHops)[i]);
                if (thisNode == kadRoutingInfoMsg->getNextHops(i)) {
                    kadRoutingInfoMsg->getNextHops(i).setIsAlive(true);
                }
            }
            kadRoutingInfoMsg->setBitLength(KADEMLIAROUTINGINFO_L(kadRoutingInfoMsg));
            delete nextHops;
            if (!altRecMode) {
                sendMessageToUDP(msg->getSrcNode(), kadRoutingInfoMsg, 0.000001);
            } else {
                // alternative maintenance mode
                std::vector<TransportAddress> sourceRoute;
                for (int i = msg->getVisitedHopsArraySize() - 1/*2*/; i >= 0; i--) {
                    //TODO remove loops
                    sourceRoute.push_back(msg->getVisitedHops(i));
                }
                //sourceRoute.push_back(msg->getSrcNode());
                sendToKey(OverlayKey::UNSPECIFIED_KEY, kadRoutingInfoMsg, 0,
                          sourceRoute, NO_OVERLAY_ROUTING);
            }
            //TODO should be sent after baseroutemsg
        } else if (altRecMode &&
                   dynamic_cast<KademliaRoutingInfoMessage*>(msg->
                           getEncapsulatedPacket())) {
            // alternative mode: infoMsg on its way back
            KademliaRoutingInfoMessage* infoMsg =
                static_cast<KademliaRoutingInfoMessage*>(msg->decapsulate());
            NodeVector* nextHops = findNode(infoMsg->getDestKey(), k, s, msg);
            // merge vectors
            KeyDistanceComparator<KeyXorMetric> comp(infoMsg->getDestKey());
            MarkedNodeVector temp(UINT16_MAX, &comp);
            for (uint32_t i = 0; i < nextHops->size(); i++) {
                temp.push_back((*nextHops)[i]);
            }
            delete nextHops;
            for (uint32_t i = 0; i < infoMsg->getNextHopsArraySize(); i++) {
                routingAdd(infoMsg->getNextHops(i),
                           infoMsg->getNextHops(i).getIsAlive());
                temp.add(infoMsg->getNextHops(i));
            }
            infoMsg->setNextHopsArraySize(temp.size());
            for (uint32_t i = 0; i < temp.size(); ++i) {
                infoMsg->setNextHops(i, temp[i]);
                if (thisNode == infoMsg->getNextHops(i)) {
                    infoMsg->getNextHops(i).setIsAlive(true);
                }
            }
            infoMsg->setBitLength(KADEMLIAROUTINGINFO_L(infoMsg));
            msg->encapsulate(infoMsg);
        }
    }
    return true;
}

void Kademlia::refillSiblingTable ( )

private

Definition at line 700 of file Kademlia.cc.

Referenced by handleFailedNode(), and routingTimeout().

{
    if (siblingTable->size() == 0 ||
        siblingTable->isFull())
        return;
    int index = routingBucketIndex(siblingTable->back().getKey()) - 1;
    assert(index > 0);
    while ((routingTable[index] == NULL ||
            routingTable[index]->empty()) &&
            index < (int)(OverlayKey::getLength() - 1)) {
        index++;
    }
    if (index < (int)OverlayKey::getLength() &&
            routingTable[index] != NULL && routingTable[index]->size()) {
        KademliaBucket sortedBucket(k, comparator);
        for (uint32_t i = 0; i < routingTable[index]->size(); ++i) {
            sortedBucket.add(routingTable[index]->at(i));
        }
        siblingTable->add(sortedBucket.front());
        // call update() for new sibling
        if (!secureMaintenance) {
            showOverlayNeighborArrow(sortedBucket.front(), false,
                                     "m=m,50,100,50,100;ls=green,1");
            callUpdate(sortedBucket.front(), true);
        }
        // remove node from bucket
        routingTable[index]->erase(routingTable[index]->
              findIterator(sortedBucket.front().getKey()));
        assert(siblingTable->isFull());
        BUCKET_CONSISTENCY(routingTimeout: end refillSiblingTable());
    }
}

bool Kademlia::routingAdd	(	const NodeHandle &	handle,
		bool	isAlive,
		simtime_t	rtt = `MAXTIME`,
		bool	maintenanceLookup = `false`
	)

private

Adds a node to the routing table.

Parameters

handle	handle to add
isAlive	true, if it is known that the node is alive
rtt	measured round-trip-time to node
maintenanceLookup	true, if this node was learned from a maintenance lookup

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

maintenanceLookup ||

Definition at line 320 of file Kademlia.cc.

Referenced by handleRpcCall(), handleRpcResponse(), handleUDPMessage(), proxCallback(), recursiveRoutingHook(), and routingTimeout().

{
    BUCKET_CONSISTENCY(routingAdd: start);
    // never add unspecified node handles
    if (handle.isUnspecified() || handle.getKey() == getThisNode().getKey()) {
        return false;
    }
    EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
       << " (" << thisNode.getKey().toString(16) << ")]\n"
       << "    inserting node " << handle << " (rtt = ";
    if (rtt == MAXTIME) {
        EV << "<unknown>";
    } else {
        EV << SIMTIME_DBL(rtt);
    }
    EV << ", isAlive = " << (isAlive?"true":"false")
       << ") ..." << endl;
    // bucket index
    KademliaBucket::iterator i;
    bool result = false;
    bool authenticated = (isAlive && (rtt != MAXTIME));
    bool needsRtt = (activePing && ((rtt == MAXTIME) ? true : false));
    // convert node handle
    KademliaBucketEntry kadHandle = handle;
    kadHandle.setRtt(rtt);
    kadHandle.setLastSeen(simTime());
    /* check if node is already a sibling -----------------------------------*/
    if ((i = siblingTable->findIterator(kadHandle.getKey()))
         != siblingTable->end()) {
        // not alive? -> do not change routing information
        if (isAlive) {
            if (!secureMaintenance || authenticated) {
                if (kadHandle.getRtt() == MAXTIME) {
                    kadHandle.setRtt(i->getRtt());
                }
                // refresh sibling
                (*i) = kadHandle;
            } else {
                if (maintenanceLookup) {
                    return false;
                }
                if ((i->getIp() != kadHandle.getIp()) ||
                    (i->getPort() != kadHandle.getPort())) {
                    // sibling could have changed transport address
                    // ping new address for authentication
                    pingNode(kadHandle);
                    return false;
                }
            }
        }
        BUCKET_CONSISTENCY(routingAdd: node is sibling);
        EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    ... node is already in the sibling table." << endl;
        return true;
    }
    /* check if node is already in a bucket ---------------------------------*/
    KademliaBucket* bucket = routingBucket(kadHandle.getKey(), false);
    if (bucket != NULL && (i = bucket->findIterator(kadHandle.getKey() ) )
            != bucket->end() ) {
        // not alive? -> do not change routing information
        if (isAlive) {
            if (!secureMaintenance || authenticated) {
                if (kadHandle.getRtt() == MAXTIME) {
                    kadHandle.setRtt(i->getRtt());
                }
                // R/Kademlia
                if (needsRtt && (kadHandle.getRtt() == MAXTIME)) {
                    Prox prox =
                        neighborCache->getProx(kadHandle, NEIGHBORCACHE_DEFAULT, -1,
                                               this, NULL);
                    if (prox != Prox::PROX_SELF &&
                        prox != Prox::PROX_UNKNOWN &&
                        prox != Prox::PROX_WAITING &&
                        prox != Prox::PROX_TIMEOUT) {
                        kadHandle.setProx(prox);
                        //routingAdd(handle, true, prox.proximity);//ctrlInfo->getSrcRoute() //TODO
                    } /*else if (prox == Prox::PROX_TIMEOUT) {
                        // remove from bucket
                        bucket->erase(i);
                        return false;
                    }*/ //TODO inform NC that node is alive
                    else {
                        EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
                           << " (" << thisNode.getKey().toString(16) << ")]\n"
                           "    ... node not added, but ping sent." << endl;
                        return false;
                    }
                }
                // remove old handle
                bucket->erase(i);
                // re-add to tail
                bucket->push_back(kadHandle);
            } else {
                if (maintenanceLookup) {
                    return false;
                }
                if ((i->getIp() != kadHandle.getIp()) ||
                    (i->getPort() != kadHandle.getPort())) {
                    // sibling could have changed transport address
                    // ping new address for authentication
                    pingNode(kadHandle);
                    return false;
                }
            }
        }
        BUCKET_CONSISTENCY(routingAdd: node is in bucket);
        EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    ... node is already in bucket "
           << routingBucketIndex(kadHandle.getKey()) << "." << endl;
        return true;
    }
    /* check if node can be added to the sibling list -----------------------*/
    if (siblingTable->isAddable(kadHandle) ) {
        if (secureMaintenance && !authenticated) {
            if (!maintenanceLookup || (isAlive && (rtt == MAXTIME))) {
                // received a FindNodeCall or PingCall from a potential sibling
                // or new nodes from a FindNodeResponse app lookup
                pingNode(kadHandle);
            } else if (newMaintenance) {
                // new node from sibling table refresh
                //sendSiblingFindNodeCall(kadHandle);
                pingNode(kadHandle);
            }
            return false;
        }
        // ping new siblings
        if (pingNewSiblings && !isAlive) {
            pingNode(kadHandle);
        }
        // R/Kademlia
        else if (needsRtt) {
            // old version: pingNode(), now:
            Prox prox =
                    neighborCache->getProx(kadHandle, NEIGHBORCACHE_DEFAULT, -1,
                                           this, NULL);
            if (prox != Prox::PROX_SELF &&
                prox != Prox::PROX_UNKNOWN &&
                prox != Prox::PROX_TIMEOUT) {
                kadHandle.setProx(prox);
            } else if (prox == Prox::PROX_TIMEOUT) {
                // do not put handle into sibling table
                EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
                   << " (" << thisNode.getKey().toString(16) << ")]\n"
                   << "    ... node not added (node timeout)." << endl;
                return false;
            }
        }
        bool finished = false;
        int siblingPos = -1;
        // check if sibling list is full so a handle is preemted from the list
        if (siblingTable->isFull()) {
            // get handle thats about to be preempted
            KademliaBucketEntry oldHandle = siblingTable->back();
            assert(oldHandle.getKey() != kadHandle.getKey());
            // add handle to the sibling list
            siblingPos = siblingTable->add(kadHandle);
            EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
               << " (" << thisNode.getKey().toString(16) << ")]\n"
               << "    ... node added to sibling table, replacing "
               << (NodeHandle)oldHandle << endl;
            // change, so that the preempted handle is added to a bucket
            kadHandle = oldHandle;
            // call update() for removed sibling
            if (!secureMaintenance) {
                deleteOverlayNeighborArrow(oldHandle);
                callUpdate(oldHandle, false);
            }
            // return always true, since the handle has been added
            result = true;
        } else {
            // simply add the handle and stop
            siblingPos = siblingTable->add(kadHandle);
            EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
               << " (" << thisNode.getKey().toString(16) << ")]\n"
               << "    ... node added to sibling table." << endl;
            // don't need to add kadHandle also to regular buckets
            finished = true;
        }
        assert(siblingPos > -1);
        updateTooltip();
        // call update() for new sibling
        showOverlayNeighborArrow(siblingTable->at(siblingPos), false,
                                 "m=m,50,100,50,100;ls=green,1");
        callUpdate(siblingTable->at(siblingPos), true);
        if (finished) {
            BUCKET_CONSISTENCY(routingAdd: node is now sibling);
            return true;
        }
    }
    /* add node to the appropriate bucket, if not full ---------------------*/
    bucket = routingBucket(kadHandle.getKey(), true);
    if (!bucket->isFull()) {
        if (secureMaintenance && !authenticated) {
            if ((isAlive && (rtt == MAXTIME))) {
                // received a FindNodeCall or PingCall from a potential new bucket entry
                // or new nodes from a FindNodeReponse app lookup
                // optimization: don't send a ping for nodes from FindNodeResponse for app lookups
                pingNode(kadHandle);
            }
            return false;
        }
        //EV << "[Kademlia::routingAdd()]\n"
        //   << "    Adding new node " << kadHandle
        //   << " to bucket " << routingBucketIndex(kadHandle.getKey())
        //   << endl;
        // PNS
        if (needsRtt || proximityNeighborSelection) {
             //pingNode(handle, -1, 0, NULL, NULL, NULL, -1, UDP_TRANSPORT, false);
             Prox prox =
                 neighborCache->getProx(kadHandle, NEIGHBORCACHE_DEFAULT, -1,
                                        this, NULL);
             if (prox != Prox::PROX_SELF &&
                 prox != Prox::PROX_UNKNOWN &&
                 prox != Prox::PROX_TIMEOUT) {
                 //routingAdd(handle, true, prox.proximity);//ctrlInfo->getSrcRoute() //TODO
                 kadHandle.setProx(prox);
             }
         }
        bucket->push_back(kadHandle);
        result = true;
        EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
           << " (" << thisNode.getKey().toString(16) << ")]\n"
           << "    ... node added to bucket "
           << routingBucketIndex(kadHandle.getKey())
           << " which was not yet full." << endl;
    } else if (isAlive) {
        //PNS node replacement
        if (proximityNeighborSelection &&
            kadHandle.getProx() != Prox::PROX_UNKNOWN) {
            KademliaBucket::iterator kickHim, it;
            kickHim = it = bucket->begin();
            ++it;
            while (it != bucket->end()) {
                if (it->getRtt() > kickHim->getRtt()) {
                    kickHim = it;
                }
                ++it;
            }
            if (kickHim->getRtt() > kadHandle.getRtt()) {
                KademliaBucketEntry temp = *kickHim;
                bucket->erase(kickHim);
                bucket->push_back(kadHandle);
                kadHandle = temp;
                EV << "[Kademlia::routingAdd()] @ " << thisNode.getIp()
                   << " (" << thisNode.getKey().toString(16) << ")]\n"
                   << "    ... added to bucket "
                   << routingBucketIndex(kadHandle.getKey())
                   << " (PNS: replacing another node)." << endl;
            }
        }
        if (enableReplacementCache && (!secureMaintenance || authenticated)) {
            bucket->replacementCache.push_front(kadHandle);
            if (bucket->replacementCache.size() > replacementCandidates) {
                bucket->replacementCache.pop_back();
            }
            if (replacementCachePing) {
                KademliaBucket::iterator it = bucket->begin();
                while (it != bucket->end() && (it->getPingSent() == true)) {
                    it++;
                }
                if (it != bucket->end()) {
                    pingNode(*it);
                    it->setPingSent(true);
                }
            }
        }
    }
    // PNS
    else if (proximityNeighborSelection) {
        neighborCache->getProx(kadHandle, NEIGHBORCACHE_QUERY, -1, this, NULL);
        //pingNode(kadHandle);
    }
    BUCKET_CONSISTENCY(routingAdd: end);
    return result;
}

KademliaBucket * Kademlia::routingBucket	(	const OverlayKey &	key,
		bool	ensure
	)

private

Returns a Bucket or NULL if the bucket has not yet allocated.

If ensure is true, the bucket allocation is ensured.

Parameters

key	The key of the node
ensure	If true, the bucket allocation is ensured

Returns: Bucket* The Bucket

Definition at line 304 of file Kademlia.cc.

Referenced by routingAdd(), routingTimeout(), and setBucketUsage().

{
    // get bucket index
    int num = routingBucketIndex(key);
    if (num < 0)
        return NULL;
    // get bucket and allocate if necessary
    KademliaBucket* bucket = routingTable[ num ];
    if (bucket == NULL && ensure)
        bucket = routingTable[ num ] = new KademliaBucket( k, comparator );
    // return bucket
    return bucket;
}

int Kademlia::routingBucketIndex	(	const OverlayKey &	key,
		bool	firstOnLayer = `false`
	)

private

Returns the index of the bucket the key would reside with respect to Kademlia parameters.

Parameters

key	The key of the node
firstOnLayer	If true bucket with smallest index on same layer is returned

Returns: int The index of the bucket

Definition at line 285 of file Kademlia.cc.

Referenced by findNode(), refillSiblingTable(), routingAdd(), and routingBucket().

{
    // calculate XOR distance
    OverlayKey delta = key ^ getThisNode().getKey();
    // find first subinteger that is not zero...
    int i;
    for (i = key.getLength() - b; i >= 0 && delta.getBitRange(i, b) == 0;
         i -= b);
    if (i < 0)
        return -1;
    if (!firstOnLayer)
        return (i / b) * ((1 << b) - 1) + (delta.getBitRange(i, b) - 1);
    else
        return (i / b) * ((1 << b) - 1) + (pow(2, b) - 2);
}

void Kademlia::routingDeinit ( )

private

Definition at line 255 of file Kademlia.cc.

Referenced by joinOverlay(), and ~Kademlia().

{
    // delete buckets
    for (uint32_t i = 0; i < routingTable.size(); i++) {
        if (routingTable[i] != NULL) {
            delete routingTable[i];
            routingTable[i] = NULL;
        }
    }
    if (siblingTable != NULL) {
        siblingTable->clear();
    }
    if (comparator != NULL) {
        delete comparator;
        comparator = NULL;
    }
}

void Kademlia::routingInit ( )

private

Definition at line 239 of file Kademlia.cc.

Referenced by joinOverlay().

{
    // set join state
    state = INIT;
    setOverlayReady(false);
    // setup comparator
    comparator = new KeyDistanceComparator<KeyXorMetric>(thisNode.getKey());
    siblingTable->setComparator(comparator);
    updateTooltip();
    BUCKET_CONSISTENCY(routingInit: end);
}

bool Kademlia::routingTimeout	(	const OverlayKey &	key,
		bool	immediately = `false`
	)

private

Removes a node after a number of timeouts or immediately if immediately is true (behaves like routingRemove).

Parameters

key	Node's key to remove
immediately	If true, the node is removed immediately

Returns: true, if the node has been removed

Definition at line 630 of file Kademlia.cc.

Referenced by handleRpcTimeout(), proxCallback(), and refillSiblingTable().

{
    BUCKET_CONSISTENCY(routingTimeout: start);
    // key unspecified? yes -> ignore
    if (key.isUnspecified())
        return false;
    // bucket index
    KademliaBucket::iterator i;
    /* check if the node is one of the siblings -----------------------------*/
    if ((i = siblingTable->findIterator(key)) != siblingTable->end()) {
        i->incStaleCount();
        i->setPingSent(false);
        if (i->getStaleCount() > maxStaleCount || immediately) {
            // remove from sibling table
            NodeHandle oldSibling = *i;
            siblingTable->erase(i);
            // lost last sibling?
            if (siblingTable->size() == 0) {
                join();
                return true;
            }
            BUCKET_CONSISTENCY(routingTimeout: is sibling);
            // try to refill with new closest contact
            refillSiblingTable();
            // call update() for removed sibling
            deleteOverlayNeighborArrow(oldSibling);
            callUpdate(oldSibling, false);
            updateTooltip();
            return true;
        }
    }
    /* check if node is already in a bucket ---------------------------------*/
    KademliaBucket* bucket = routingBucket(key, false);
    if (bucket != NULL && (i = bucket->findIterator(key) ) != bucket->end() ) {
        i->incStaleCount();
        i->setPingSent(false);
        if (i->getStaleCount() > maxStaleCount || immediately) {
            // remove from routing table
            bucket->erase(i);
            if (enableReplacementCache) {
                if (bucket->replacementCache.size()) {
                    routingAdd(bucket->replacementCache.front(), true,
                               bucket->replacementCache.front().getRtt());
                    bucket->replacementCache.pop_front();
                    nodesReplaced++;
                }
            }
        }
        BUCKET_CONSISTENCY(routingTimeout: is in bucket);
        return true;
    }
    BUCKET_CONSISTENCY(routingTimeout: end);
    return false;
}

void Kademlia::sendSiblingFindNodeCall ( const TransportAddress & dest )

private

Definition at line 193 of file Kademlia.cc.

Referenced by handleBucketRefreshTimerExpired(), and joinOverlay().

{
    FindNodeCall* call = new FindNodeCall("FindNodeCall");
    call->setExhaustiveIterative(true);
    call->setLookupKey(thisNode.getKey());
    call->setNumRedundantNodes(siblingRefreshNodes);
    call->setNumSiblings(getMaxNumSiblings());
    call->setBitLength(FINDNODECALL_L(call));
    sendUdpRpcCall(dest, call);
}

void Kademlia::setBucketUsage ( const OverlayKey & key )

private

Definition at line 739 of file Kademlia.cc.

Referenced by handleBucketRefreshTimerExpired(), handleRpcResponse(), and handleRpcTimeout().

{
    KademliaBucket* bucket = routingBucket(key, true);
    if (bucket) {
        bucket->setLastUsage(simTime());
    }
    if ((siblingTable->size() < (uint32_t)getMaxNumSiblings())
        || ((siblingTable->at(getMaxNumSiblings() - 1).getKey() ^ thisNode.getKey())
                >= (key ^ thisNode.getKey()))) {
        siblingTable->setLastUsage(simTime());
    }
}

void Kademlia::updateTooltip ( )

protected

updates information shown in GUI

Definition at line 1429 of file Kademlia.cc.

Referenced by handleFailedNode(), routingAdd(), routingInit(), and routingTimeout().

{
    if (ev.isGUI()) {
        std::stringstream ttString;
        // show our nodeId in a tooltip
        ttString << "This: " << thisNode << endl << "Siblings: "
                 << siblingTable->size();
        getParentModule()->getParentModule()->getDisplayString().
        setTagArg("tt", 0, ttString.str().c_str());
        getParentModule()->getDisplayString().
        setTagArg("tt", 0, ttString.str().c_str());
        getDisplayString().setTagArg("tt", 0, ttString.str().c_str());
    }
}