OverSim
Classes | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Friends | List of all members
IterativeLookup Class Reference

This class implements a basic greedy lookup strategy. More...

#include <IterativeLookup.h>

Inheritance diagram for IterativeLookup:
RpcListener AbstractLookup Comparator< OverlayKey >

Classes

class  RpcInfo
class  RpcInfoVector

Public Member Functions

virtual int compare (const OverlayKey &lhs, const OverlayKey &rhs) const
 compares two OverlayKeys and indicates which one is closer to the key to look up
 IterativeLookup (BaseOverlay *overlay, RoutingType routingType, const IterativeLookupConfiguration &config, const cPacket *findNodeExt=NULL, bool appLookup=false)
virtual ~IterativeLookup ()
void lookup (const OverlayKey &key, int numSiblings=1, int hopCountMax=0, int retries=0, LookupListener *listener=NULL)
 Lookup siblings for a key.
const NodeVector & getResult () const
 Returns the result of the lookup.
bool isValid () const
 Returns true, if the lookup was successful.
void abortLookup ()
 Aborts a running lookup.
uint32_t getAccumulatedHops () const
 Returns the total number of hops for all lookup paths.
- Public Member Functions inherited from RpcListener
virtual ~RpcListener ()
 destructor
- Public Member Functions inherited from AbstractLookup
virtual ~AbstractLookup ()
 Virtual destructor.
- Public Member Functions inherited from Comparator< OverlayKey >
virtual ~Comparator ()
 virtual destructor

Protected Types

typedef std::map< int, int > PendingPings
typedef std::set< NodeHandle > MajoritySiblings
typedef UNORDERED_MAP
< TransportAddress,
RpcInfoVector,
TransportAddress::hashFcn > 		RpcInfoMap

Protected Member Functions

virtual IterativePathLookup * createPathLookup ()
 This method creates a new path lookup.
virtual FindNodeCall * createFindNodeCall (cPacket *findNodeExt=NULL)
 Creates a find node call message.
bool addSibling (const NodeHandle &handle, bool assured=false)
 adds a node to the siblings NodeVector
void setVisited (const TransportAddress &addr, bool visitedFlag=true)
 adds/deletes visited nodes to/from the visited TransportAddress::Set
bool getVisited (const TransportAddress &addr)
 indicates if the specified node has been visited before
void setPinged (const TransportAddress &addr)
 marks a node as already pinged for authentication
bool getPinged (const TransportAddress &addr)
 verify if this node has already been pinged for authentication
void setDead (const TransportAddress &addr)
 add a dead node to the dead node list
bool getDead (const TransportAddress &addr)
 check if a node seems to be dead
virtual void handleRpcResponse (BaseResponseMessage *msg, cPolymorphic *context, int rpcId, simtime_t rtt)
 This method is called if an RPC response has been received.
virtual void handleRpcTimeout (BaseCallMessage *msg, const TransportAddress &dest, cPolymorphic *context, int rpcId, const OverlayKey &destKey=OverlayKey::UNSPECIFIED_KEY)
 This method is called if an RPC timeout has been reached.
void sendRpc (const NodeHandle &handle, FindNodeCall *call, IterativePathLookup *listener, int rpcId)
virtual void start ()
void stop ()
void checkStop ()
- 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 Attributes

OverlayKey key
 key to lookup
BaseOverlay * overlay
 ptr to overlay
LookupListener * listener
 lookup listener
std::vector
< IterativePathLookup * > 		paths
 parallel paths
RoutingType routingType
 RoutingType for this lookup.
IterativeLookupConfiguration config
 lookup configuration
cPacket * firstCallExt
 additional info for first findNode()
uint32_t finishedPaths
 number of finished paths
uint32_t successfulPaths
 number of successful paths
uint32_t accumulatedHops
 total number of hops (for all paths)
bool finished
 true, if lookup is finished
bool success
 true, if lookup was successful
bool running
 true, if lookup is running
int retries
 number of retries, if lookup fails
bool appLookup
SimTime startTime
 time at which the lookup was started
NodeVector siblings
 closest nodes
TransportAddress::Set visited
 nodes already visited
TransportAddress::Set dead
 nodes which seem to be dead
TransportAddress::Set pinged
 nodes already pinged
MajoritySiblings majoritySiblings
 map for majority decision on correct siblings
int numSiblings
 number of siblings
int hopCountMax
 maximum hop count
PendingPings pendingPings
 number of pending ping calls
RpcInfoMap rpcs

Friends

class IterativePathLookup
class BaseOverlay

Detailed Description

This class implements a basic greedy lookup strategy.

It uses the standard metric for greedy behaviour. If another metric is needed, the distance function can be replaced by overriding the distance method.

Author
Sebastian Mies

Definition at line 81 of file IterativeLookup.h.

Member Typedef Documentation

typedef std::set<NodeHandle> IterativeLookup::MajoritySiblings
protected

Definition at line 154 of file IterativeLookup.h.

typedef std::map<int,int> IterativeLookup::PendingPings
protected

Definition at line 153 of file IterativeLookup.h.

typedef UNORDERED_MAP<TransportAddress, RpcInfoVector, TransportAddress::hashFcn> IterativeLookup::RpcInfoMap
protected

Definition at line 237 of file IterativeLookup.h.

Constructor & Destructor Documentation

IterativeLookup::IterativeLookup ( BaseOverlay *  overlay,
RoutingType  routingType,
const IterativeLookupConfiguration &  config,
const cPacket *  findNodeExt = NULL,
bool  appLookup = false 
)

Definition at line 69 of file IterativeLookup.cc.

:
overlay(overlay),
routingType(routingType),
config(config),
firstCallExt(NULL),
finished(false),
success(false),
running(false),
appLookup(appLookup)
{
if (findNodeExt) firstCallExt = static_cast<cPacket*>(findNodeExt->dup());
if ((config.parallelPaths > 1) && (!config.merge)) {
throw cRuntimeError("IterativeLookup::IterativeLookup(): "
"config.merge must be enabled for "
"using parallel paths!");
}
if (config.verifySiblings && (!config.merge)) {
throw cRuntimeError("IterativeLookup::IterativeLookup(): "
"config.merge must be enabled for "
"using secure lookups!");
}
if (config.majoritySiblings && (!config.merge)) {
throw cRuntimeError("IterativeLookup::IterativeLookup(): "
"config.merge must be enabled for "
"using majority decision for sibling selection!");
}
/*
if (config.useAllParallelResponses && (!config.merge)) {
throw cRuntimeError("IterativeLookup::IterativeLookup(): "
"config.merge must be enabled if "
"config.useAllParallelResponses is true!");
}*/
}
IterativeLookup::~IterativeLookup ( )
virtual

Definition at line 111 of file IterativeLookup.cc.

{
stop();
delete firstCallExt;
overlay->removeLookup(this);
}

Member Function Documentation

void IterativeLookup::abortLookup ( )
virtual

Aborts a running lookup.

This method aborts a running lookup without calling the listener and delete the lookup object.

Implements AbstractLookup.

Definition at line 118 of file IterativeLookup.cc.

{
if (listener != NULL) {
delete listener;
listener = NULL;
}
for (RpcInfoMap::iterator i = rpcs.begin(); i != rpcs.end(); i++) {
overlay->cancelRpcMessage(i->second.nonce);
}
rpcs.clear();
delete this;
}
bool IterativeLookup::addSibling ( const NodeHandle &  handle,
bool  assured = false 
)
protected

adds a node to the siblings NodeVector

Parameters
handleNodeHandle of the node to add
assuredtrue, if this node was already authenticated
Returns
true if operation was succesful, false otherwise

Definition at line 416 of file IterativeLookup.cc.

Referenced by IterativePathLookup::handleResponse(), handleRpcResponse(), IterativePathLookup::sendRpc(), and start().

{
bool result = false;
EV << "[IterativeLookup::addSibling() @ " << overlay->getThisNode().getIp()
<< " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
<< " Adding potential sibling " << handle
<< endl;
majoritySiblings.insert(handle);
if (config.verifySiblings && !assured && !getVisited(handle)) {
// ping potential sibling for authentication
if (siblings.isAddable(handle) && !getPinged(handle)) {
int id = intuniform(1, 2147483647);
int nonce = overlay->pingNode(handle, -1, 0, NULL, NULL, this, id);
pendingPings.insert(make_pair(id, nonce));
setPinged(handle);
}
return false;
}
if (numSiblings == 0) {
if (handle.getKey() == key) {
siblings.clear();
siblings.push_back( handle );
result = true;
}
} else {
if (config.parallelPaths == 1 && !config.verifySiblings) {
result = true;
if (!siblings.isFull()) {
siblings.push_back(handle);
}
} else {
if (siblings.add(handle) >= 0) {
result = true;
}
}
}
return result;
}
void IterativeLookup::checkStop ( )
protected

Definition at line 289 of file IterativeLookup.cc.

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

{
bool finishLookup = false;
if (config.majoritySiblings && (numSiblings > 0) &&
finishedPaths == (uint32_t)config.parallelPaths) {
if (majoritySiblings.size() <= (uint)numSiblings) {
// TODO: better check that all nodes have sent the same siblings
MajoritySiblings::iterator it;
for (it = majoritySiblings.begin(); it != majoritySiblings.end(); it++) {
siblings.add(*it);
}
success = true;
finishLookup = true;
}
}
// check if there are rpcs pending or lookup finished
if (((successfulPaths >= 1) && (numSiblings == 0) && (siblings.size() >= 1)) ||
((finishedPaths == (uint32_t)config.parallelPaths) &&
(numSiblings > 0) && (pendingPings.size() == 0))) {
/*
std::cout << "successfulPaths: " << successfulPaths
<< ", numSiblings: " << numSiblings
<< ", siblings.size(): " << siblings.size()
<< ", finishedPaths: " << finishedPaths
<< ", config.parallelPaths: " << config.parallelPaths
<< ", pendingPings.size(): " << pendingPings.size()
<< std::endl;
*/
for (uint32_t i=0; i<paths.size(); i++) {
success |= paths[i]->success;
}
finishLookup = true;
} else if ((rpcs.size() == 0) && (pendingPings.size() == 0)) {
finishLookup = true;
}
if (finishLookup == true) {
// TODO: should not be needed, but sometimes finishedPaths seems
// to be smaller than config.parallelPaths
if (successfulPaths >= 1) {
success = true;
}
if (success == false) {
//std::cout << overlay->getThisNode().getKey() << " lookup of " << key << " failed: hops :" << accumulatedHops << endl;
}
if (success == false && retries > 0) {
//std::cout << "IterativeLookup::checkStop(): Retry..." << endl;
retries--;
LookupListener* oldListener = listener;
listener = NULL;
stop();
listener = oldListener;
start();
} else {
//std::cout << "IterativeLookup::checkStop(): No retry!" << endl;
for (RpcInfoMap::iterator i = rpcs.begin(); i != rpcs.end(); i++) {
overlay->cancelRpcMessage(i->second.nonce);
}
rpcs.clear();
delete this;
}
}
}
int IterativeLookup::compare ( const OverlayKey &  lhs,
const OverlayKey &  rhs 
) const
virtual

compares two OverlayKeys and indicates which one is closer to the key to look up

Parameters
lhsthe first OverlayKey
rhsthe second OverlayKey
Returns
-1 if rhs is closer, 0 if lhs and rhs are equal and 1 if rhs is farther away to the key to lookup

Reimplemented from Comparator< OverlayKey >.

Definition at line 404 of file IterativeLookup.cc.

{
//std::cout << key << ": l=" << lhs << ", r=" << rhs << std::endl;
return overlay->distance(lhs, key/*, useAlternativeMetric*/).compareTo(overlay->distance(rhs, key/*, useAlternativeMetric*/));
}
FindNodeCall * IterativeLookup::createFindNodeCall ( cPacket *  findNodeExt = NULL)
protectedvirtual

Creates a find node call message.

This method can be overridden to add some additional state information to the FindNodeCall message.

Parameters
findNodeExtPointer to a optional cMessage, that may contain overlay specific data to be attached to FindNode RPCs and BaseRouteMessages
Returns
pointer to a new FindNodeCall message.

Definition at line 366 of file IterativeLookup.cc.

Referenced by IterativePathLookup::sendRpc(), and start().

{
FindNodeCall* call = new FindNodeCall("FindNodeCall");
if (appLookup) {
call->setStatType(APP_LOOKUP_STAT);
} else {
call->setStatType(MAINTENANCE_STAT);
}
if (routingType == EXHAUSTIVE_ITERATIVE_ROUTING) {
call->setExhaustiveIterative(true);
} else {
call->setExhaustiveIterative(false);
}
call->setLookupKey(key);
call->setNumRedundantNodes(config.redundantNodes);
call->setNumSiblings(numSiblings);
if (routingType == EXHAUSTIVE_ITERATIVE_ROUTING) {
call->setExhaustiveIterative(true);
} else {
call->setExhaustiveIterative(false);
}
call->setBitLength(FINDNODECALL_L(call));
// duplicate extension object
if (findNodeExt) {
call->addObject(static_cast<cObject*>(findNodeExt->dup()));
call->addBitLength(findNodeExt->getBitLength());
}
return call;
}
IterativePathLookup * IterativeLookup::createPathLookup ( )
protectedvirtual

This method creates a new path lookup.

It may be overloaded to enhance IterativePathLookup with some new information/features.

Returns
The new path lookup

Definition at line 361 of file IterativeLookup.cc.

{
return new IterativePathLookup(this);
}
uint32_t IterativeLookup::getAccumulatedHops ( ) const
virtual

Returns the total number of hops for all lookup paths.

Returns
The accumulated number of hops.

Implements AbstractLookup.

Definition at line 730 of file IterativeLookup.cc.

{
return accumulatedHops;
}
bool IterativeLookup::getDead ( const TransportAddress &  addr)
protected

check if a node seems to be dead

Parameters
addrTransportAddress of the node
Returns
true, if the node seems to be dead

Definition at line 479 of file IterativeLookup.cc.

Referenced by IterativePathLookup::handleTimeout(), and IterativePathLookup::sendRpc().

{
return (dead.count(addr) != 0);
}
bool IterativeLookup::getPinged ( const TransportAddress &  addr)
protected

verify if this node has already been pinged for authentication

Parameters
addrTransportAddress of the node
Returns
false if addr was not already pinged, true otherwise

Definition at line 489 of file IterativeLookup.cc.

Referenced by addSibling().

{
return (pinged.count(addr) != 0);
}
const NodeVector & IterativeLookup::getResult ( ) const
virtual

Returns the result of the lookup.

Returns
The result node vector.

Implements AbstractLookup.

Definition at line 719 of file IterativeLookup.cc.

{
// return sibling vector
return siblings;
}
bool IterativeLookup::getVisited ( const TransportAddress &  addr)
protected

indicates if the specified node has been visited before

Parameters
addrTransportAddress of the node
Returns
false if addr is not in visited, true otherwise

Definition at line 469 of file IterativeLookup.cc.

Referenced by addSibling(), and IterativePathLookup::sendRpc().

{
return (visited.count(addr) != 0);
}
void IterativeLookup::handleRpcResponse ( BaseResponseMessage *  msg,
cPolymorphic *  context,
int  rpcId,
simtime_t  rtt 
)
protectedvirtual

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

Parameters
msgThe response message.
contextPointer to an optional state object. The object has to be handled/deleted by the handleRpcResponse() code
rpcIdThe RPC id.
rttThe Round-Trip-Time of this RPC

Reimplemented from RpcListener.

Definition at line 498 of file IterativeLookup.cc.

{
// check flags
if (finished || !running)
return;
// get source, cast messages and mark node as visited
const TransportAddress& src = msg->getSrcNode();
FindNodeResponse* findNodeResponse = dynamic_cast<FindNodeResponse*>(msg);
PingResponse* pingResponse = dynamic_cast<PingResponse*>(msg);
FailedNodeResponse* failedNodeResponse =
dynamic_cast<FailedNodeResponse*>(msg);
if (pingResponse != NULL) {
pendingPings.erase(rpcId);
// add authenticated sibling
addSibling(pingResponse->getSrcNode(), true);
}
// handle find node response
if (findNodeResponse != NULL) {
// std::cout << "time: " << simTime() << " node: " << overlay->thisNode << " this: " << this << " received rpc with nonce: " << findNodeResponse->getNonce() << " from: " << findNodeResponse->getSrcNode() << endl;
// check if rpc info is available, no -> exit
if (rpcs.count(src) == 0)
return;
// get info
RpcInfoVector infos = rpcs[src];
rpcs.erase(src);
// iterate
bool rpcHandled = false;
for (uint32_t i=0; i<infos.size(); i++) {
// get info
const RpcInfo& info = infos[i];
// do not handle finished paths
if (info.path->finished)
continue;
// check if path accepts the message
// make an exception for responses with siblings==true
if (!rpcHandled &&
(info.path->accepts(info.vrpcId) ||
((routingType == EXHAUSTIVE_ITERATIVE_ROUTING)
|| (findNodeResponse->getSiblings() &&
config.acceptLateSiblings)))) {
info.path->handleResponse(findNodeResponse);
rpcHandled = true;
} else {
EV << "[IterativeLookup::handleRpcResponse()]\n"
<< " Path does not accept message with id " << info.vrpcId
<< endl;
info.path->handleTimeout(NULL, findNodeResponse->getSrcNode(),
info.vrpcId);
}
// count finished and successful paths
if (info.path->finished) {
finishedPaths++;
// count total number of hops
accumulatedHops += info.path->hops;
if (info.path->success)
successfulPaths++;
}
}
}
// handle failed node response
if (failedNodeResponse != NULL) {
cPacket* findNodeExt = NULL;
if (failedNodeResponse->hasObject("findNodeExt")) {
findNodeExt =
(cPacket*)failedNodeResponse->removeObject("findNodeExt");
}
for (std::vector<IterativePathLookup*>::iterator i = paths.begin();
i != paths.end(); i++) {
(*i)->handleFailedNodeResponse(failedNodeResponse->getSrcNode(),
findNodeExt,
failedNodeResponse->getTryAgain());
}
}
checkStop();
}
void IterativeLookup::handleRpcTimeout ( BaseCallMessage *  msg,
const TransportAddress &  dest,
cPolymorphic *  context,
int  rpcId,
const OverlayKey &  destKey = OverlayKey::UNSPECIFIED_KEY 
)
protectedvirtual

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

Parameters
msgThe original RPC message.
destThe destination node
contextPointer to an optional state object. The object has to be handled/deleted by the handleRpcResponse() code
rpcIdThe RPC id.
destKeythe destination OverlayKey

Reimplemented from RpcListener.

Definition at line 596 of file IterativeLookup.cc.

{
// check flags
if (finished || !running)
return;
if (dynamic_cast<PingCall*>(msg) != NULL) {
pendingPings.erase(rpcId);
checkStop();
return;
}
// check if rpc info is available
if (rpcs.count(dest)==0) {
//std::cout << "IterativeLookup::handleRpcTimeout(): RPC Timeout, but node"
// << " is not in rpcs structure!" << endl;
return;
}
// mark the node as dead
setDead(dest);
RpcInfoVector infos = rpcs[dest];
rpcs.erase(dest);
// iterate
for (uint32_t i=0; i < infos.size(); i++) {
const RpcInfo& info = infos[i];
// do not handle finished paths
if (info.path->finished)
continue;
// delegate timeout
info.path->handleTimeout(msg, dest, info.vrpcId);
// count finished and successful paths
if (info.path->finished) {
finishedPaths++;
// count total number of hops
accumulatedHops += info.path->hops;
if (info.path->success)
successfulPaths++;
}
}
checkStop();
}
bool IterativeLookup::isValid ( ) const
virtual

Returns true, if the lookup was successful.

Returns
true, if the lookup was successful.

Implements AbstractLookup.

Definition at line 725 of file IterativeLookup.cc.

Referenced by stop().

{
return success && finished;
}
void IterativeLookup::lookup ( const OverlayKey &  key,
int  numSiblings = 1,
int  hopCountMax = 0,
int  retries = 0,
LookupListener *  listener = NULL 
)
virtual

Lookup siblings for a key.

Parameters
keyThe key to lookup
numSiblingsNumber of siblings to lookup
hopCountMaxMaximum hop count
retriesNumber of retries if lookup fails
listenerListener to inform, when the lookup is done

Implements AbstractLookup.

Definition at line 689 of file IterativeLookup.cc.

{
EV << "[IterativeLookup::lookup() @ " << overlay->overlay->getThisNode().getIp()
<< " (" << overlay->overlay->getThisNode().getKey().toString(16) << ")]\n"
<< " Lookup of key " << key
<< endl;
// check flags
if (finished || running)
return;
// set params
this->key = key;
this->numSiblings = numSiblings;
this->hopCountMax = hopCountMax;
this->listener = listener;
this->retries = retries;
if ((routingType == EXHAUSTIVE_ITERATIVE_ROUTING)
&& (numSiblings > config.redundantNodes)) {
throw cRuntimeError("IterativeLookup::lookup(): "
"With EXHAUSTIVE_ITERATIVE_ROUTING numRedundantNodes "
"must be >= numSiblings!");
}
// start lookup
start();
}
void IterativeLookup::sendRpc ( const NodeHandle &  handle,
FindNodeCall *  call,
IterativePathLookup *  listener,
int  rpcId 
)
protected

Definition at line 650 of file IterativeLookup.cc.

Referenced by IterativePathLookup::sendRpc().

{
// check flags
if (finished || !running) {
delete call;
return;
}
// create rpc info
RpcInfo info;
info.path = listener;
info.vrpcId = rpcId;
// send new message
if (rpcs.count(handle) == 0) {
RpcInfoVector newVector;
overlay->countFindNodeCall(call);
newVector.nonce = overlay->sendUdpRpcCall(handle, call, NULL,
-1, 0, -1, this);
// std::cout << "time: " << simTime() << " node: " << overlay->thisNode << " new rpc with nonce: " << newVector.nonce << " to: " << handle << endl;
rpcs[handle] = newVector;
} else {
EV << "[IterativeLookup::sendRpc()]\n"
<< " RPC already sent...not sent again"
<< endl;
delete call;
}
// register info
rpcs[handle].push_back(info);
}
void IterativeLookup::setDead ( const TransportAddress &  addr)
protected

add a dead node to the dead node list

Parameters
addrTransportAddress of the node to add

Definition at line 474 of file IterativeLookup.cc.

Referenced by handleRpcTimeout().

{
dead.insert(addr);
}
void IterativeLookup::setPinged ( const TransportAddress &  addr)
protected

marks a node as already pinged for authentication

Parameters
addrTransportAddress of the node to mark as already pinged

Definition at line 484 of file IterativeLookup.cc.

Referenced by addSibling().

{
pinged.insert(addr);
}
void IterativeLookup::setVisited ( const TransportAddress &  addr,
bool  visitedFlag = true 
)
protected

adds/deletes visited nodes to/from the visited TransportAddress::Set

Parameters
addrTransportAddress of the node to add
visitedFlagif true node is added, else node is erased

Definition at line 461 of file IterativeLookup.cc.

Referenced by IterativePathLookup::handleFailedNodeResponse(), IterativePathLookup::handleResponse(), and start().

{
if (visitedFlag)
this->visited.insert(addr);
else
this->visited.erase(addr);
}
void IterativeLookup::start ( )
protectedvirtual

Definition at line 131 of file IterativeLookup.cc.

Referenced by checkStop(), and lookup().

{
// init params
successfulPaths = 0;
finishedPaths = 0;
accumulatedHops = 0;
// init flags
finished = false;
success = false;
running = true;
// init siblings vector
siblings = NodeVector(numSiblings == 0 ? 1 : numSiblings, this);
visited.clear();
dead.clear();
pinged.clear();
startTime = simTime();
// get local closest nodes
FindNodeCall* call = createFindNodeCall(firstCallExt);
NodeVector* nextHops = overlay->findNode(key, overlay->getMaxNumRedundantNodes(),
(routingType == EXHAUSTIVE_ITERATIVE_ROUTING) ? -1 : numSiblings, call);
bool err;
setVisited(overlay->getThisNode());
// if this node is new and no nodes are known -> stop lookup
if (nextHops->size() == 0) {
//std::cout << "IterativeLookup: No next hops known" << endl;
finished = true;
success = false;
} else if ((numSiblings == 0)
&& overlay->isSiblingFor(overlay->getThisNode(),
key, numSiblings,
&err)) {
if (overlay->getThisNode().getKey() == key) {
addSibling(overlay->getThisNode(), true);
success = true;
} else {
std::cout << "IterativeLookup: numSiblings==0 and no node with this id"
<< endl;
success = false;
}
finished = true;
}
// finish lookup if the key is local and siblings are needed
else if (numSiblings != 0 && routingType != EXHAUSTIVE_ITERATIVE_ROUTING &&
overlay->isSiblingFor(overlay->getThisNode(), key,
numSiblings, &err)) {
for (uint32_t i=0; i<nextHops->size(); i++) {
addSibling(nextHops->at(i), true);
}
success = finished = true;
}
// if the key was local or belongs to one of our siblings we are finished
if (finished) {
// calls stop and finishes the lookup
delete nextHops;
delete call;
delete this;
return;
}
// extract find node extensions
cPacket* findNodeExt = NULL;
if (call->hasObject("findNodeExt"))
findNodeExt = (cPacket*)call->removeObject("findNodeExt");
delete call;
// not enough nodes for all paths? -> reduce number of parallel paths
if ((uint32_t)config.parallelPaths > nextHops->size()) {
config.parallelPaths = nextHops->size();
}
// create parallel paths and distribute nodes to paths
for (int i = 0; i < config.parallelPaths; i++) {
// create state
IterativePathLookup* pathLookup = new IterativePathLookup(this);
paths.push_back(pathLookup);
// populate next hops
for (uint32_t k=0; (k * config.parallelPaths + i) < nextHops->size(); k++) {
pathLookup->add(nextHops->at(k * config.parallelPaths + i));
}
// send initial rpcs
pathLookup->sendRpc(config.parallelRpcs, findNodeExt);
}
//std::cout << "nextHops size: " << nextHops->size()
//<< " numSiblings: " << numSiblings
//<< " redundantNodes: " << config.redundantNodes
//<< " thisNode " << overlay->getThisNode().ip
//<< " nextHop " << nextHops->at(0).ip << endl;
delete nextHops;
delete findNodeExt;
checkStop();
}
void IterativeLookup::stop ( )
protected

Definition at line 240 of file IterativeLookup.cc.

Referenced by checkStop(), and ~IterativeLookup().

{
// only stop if running
if (!running)
return;
for (uint32_t i=0; i<paths.size(); i++) {
success |= paths[i]->success;
}
// cancel pending rpcs
for (RpcInfoMap::iterator i = rpcs.begin(); i != rpcs.end(); i++) {
overlay->cancelRpcMessage(i->second.nonce);
}
rpcs.clear();
// cancel pending ping rpcs
for (PendingPings::iterator i = pendingPings.begin(); i != pendingPings.end(); i++) {
overlay->cancelRpcMessage(i->second);
}
pendingPings.clear();
// delete path lookups
for (uint32_t i = 0; i < paths.size(); ++i) {
delete paths[i];
}
paths.clear();
// reset running flag
running = false;
finished = true;
#if 0
EV << "[IterativeLookup::stop() @ " << overlay->getThisNode().getIp()
<< " (" << overlay->getThisNode().getKey().toString(16) << ")]\n"
<< " Lookup " << (isValid() ? "succeeded\n" : "failed\n")
<< " (" << successfulPaths << " successful paths)\n"
<< " (" << finishedPaths << " finished paths)"
<< endl;
#endif
// inform listener
if (listener != NULL) {
listener->lookupFinished(this);
listener = NULL;
}
}

Friends And Related Function Documentation

friend class BaseOverlay
friend

Definition at line 86 of file IterativeLookup.h.

friend class IterativePathLookup
friend

Definition at line 85 of file IterativeLookup.h.

Referenced by createPathLookup(), and start().

Member Data Documentation

uint32_t IterativeLookup::accumulatedHops
protected

total number of hops (for all paths)

Definition at line 123 of file IterativeLookup.h.

Referenced by getAccumulatedHops(), handleRpcResponse(), handleRpcTimeout(), and start().

bool IterativeLookup::appLookup
protected

Definition at line 128 of file IterativeLookup.h.

Referenced by createFindNodeCall().

IterativeLookupConfiguration IterativeLookup::config
protected

lookup configuration

Definition at line 119 of file IterativeLookup.h.

Referenced by IterativePathLookup::accepts(), IterativePathLookup::add(), addSibling(), checkStop(), createFindNodeCall(), IterativePathLookup::handleResponse(), handleRpcResponse(), IterativePathLookup::handleTimeout(), IterativePathLookup::IterativePathLookup(), lookup(), IterativePathLookup::sendNewRpcAfterTimeout(), IterativePathLookup::sendRpc(), and start().

TransportAddress::Set IterativeLookup::dead
protected

nodes which seem to be dead

Definition at line 151 of file IterativeLookup.h.

Referenced by getDead(), setDead(), and start().

bool IterativeLookup::finished
protected

true, if lookup is finished

Definition at line 124 of file IterativeLookup.h.

Referenced by handleRpcResponse(), handleRpcTimeout(), isValid(), lookup(), sendRpc(), start(), and stop().

uint32_t IterativeLookup::finishedPaths
protected

number of finished paths

Definition at line 121 of file IterativeLookup.h.

Referenced by checkStop(), handleRpcResponse(), handleRpcTimeout(), start(), and stop().

cPacket* IterativeLookup::firstCallExt
protected

additional info for first findNode()

Definition at line 120 of file IterativeLookup.h.

Referenced by IterativeLookup(), start(), and ~IterativeLookup().

int IterativeLookup::hopCountMax
protected

maximum hop count

Definition at line 157 of file IterativeLookup.h.

Referenced by lookup(), and IterativePathLookup::sendRpc().

OverlayKey IterativeLookup::key
protected

key to lookup

Definition at line 114 of file IterativeLookup.h.

Referenced by addSibling(), compare(), createFindNodeCall(), IterativePathLookup::handleResponse(), lookup(), and start().

LookupListener* IterativeLookup::listener
protected

lookup listener

Definition at line 116 of file IterativeLookup.h.

Referenced by abortLookup(), checkStop(), lookup(), sendRpc(), and stop().

MajoritySiblings IterativeLookup::majoritySiblings
protected

map for majority decision on correct siblings

Definition at line 155 of file IterativeLookup.h.

Referenced by addSibling(), and checkStop().

int IterativeLookup::numSiblings
protected

number of siblings

Definition at line 156 of file IterativeLookup.h.

Referenced by addSibling(), checkStop(), createFindNodeCall(), IterativePathLookup::handleResponse(), IterativePathLookup::handleTimeout(), lookup(), and start().

BaseOverlay* IterativeLookup::overlay
protected

ptr to overlay

Definition at line 115 of file IterativeLookup.h.

Referenced by abortLookup(), addSibling(), checkStop(), compare(), IterativePathLookup::handleResponse(), IterativePathLookup::handleTimeout(), IterativePathLookup::IterativePathLookup(), lookup(), sendRpc(), start(), stop(), and ~IterativeLookup().

std::vector<IterativePathLookup*> IterativeLookup::paths
protected

parallel paths

Definition at line 117 of file IterativeLookup.h.

Referenced by checkStop(), handleRpcResponse(), start(), and stop().

PendingPings IterativeLookup::pendingPings
protected

number of pending ping calls

Definition at line 158 of file IterativeLookup.h.

Referenced by addSibling(), checkStop(), handleRpcResponse(), handleRpcTimeout(), and stop().

TransportAddress::Set IterativeLookup::pinged
protected

nodes already pinged

Definition at line 152 of file IterativeLookup.h.

Referenced by getPinged(), setPinged(), and start().

int IterativeLookup::retries
protected

number of retries, if lookup fails

Definition at line 127 of file IterativeLookup.h.

Referenced by checkStop(), and lookup().

RoutingType IterativeLookup::routingType
protected

RoutingType for this lookup.

Definition at line 118 of file IterativeLookup.h.

Referenced by createFindNodeCall(), IterativePathLookup::handleResponse(), handleRpcResponse(), IterativePathLookup::handleTimeout(), IterativePathLookup::IterativePathLookup(), lookup(), IterativePathLookup::sendRpc(), and start().

RpcInfoMap IterativeLookup::rpcs
protected

Definition at line 238 of file IterativeLookup.h.

Referenced by abortLookup(), checkStop(), handleRpcResponse(), handleRpcTimeout(), sendRpc(), and stop().

bool IterativeLookup::running
protected

true, if lookup is running

Definition at line 126 of file IterativeLookup.h.

Referenced by handleRpcResponse(), handleRpcTimeout(), lookup(), sendRpc(), start(), and stop().

NodeVector IterativeLookup::siblings
protected

closest nodes

Definition at line 149 of file IterativeLookup.h.

Referenced by addSibling(), checkStop(), getResult(), and start().

SimTime IterativeLookup::startTime
protected

time at which the lookup was started

Definition at line 129 of file IterativeLookup.h.

Referenced by IterativePathLookup::handleResponse(), IterativePathLookup::handleTimeout(), and start().

bool IterativeLookup::success
protected

true, if lookup was successful

Definition at line 125 of file IterativeLookup.h.

Referenced by checkStop(), isValid(), start(), and stop().

uint32_t IterativeLookup::successfulPaths
protected

number of successful paths

Definition at line 122 of file IterativeLookup.h.

Referenced by checkStop(), handleRpcResponse(), handleRpcTimeout(), start(), and stop().

TransportAddress::Set IterativeLookup::visited
protected

nodes already visited

Definition at line 150 of file IterativeLookup.h.

Referenced by getVisited(), setVisited(), and start().

The documentation for this class was generated from the following files: