OverSim
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
oversim::Koorde Class Reference

Koorde overlay module. More...

#include <Koorde.h>

Inheritance diagram for oversim::Koorde:
oversim::Chord BaseOverlay ProxListener BaseRpc BaseTcpSupport TopologyVis RpcListener

Public Member Functions

virtual ~Koorde ()
virtual void initializeOverlay (int stage)
 Initializes derived-class-attributes.
virtual void handleTimerEvent (cMessage *msg)
virtual void handleUDPMessage (BaseOverlayMessage *msg)
 Processes messages from underlay.
virtual void recordOverlaySentStats (BaseOverlayMessage *msg)
 Collect overlay specific sent messages statistics.
virtual void finishOverlay ()
 collects statistical data in derived class
virtual void updateTooltip ()
 updates information shown in tk-environment
- Public Member Functions inherited from oversim::Chord
 Chord ()
virtual ~Chord ()
OverlayKey distance (const OverlayKey &x, const OverlayKey &y, bool useAlternative=false) const
 This method should implement the distance between two keys.
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

virtual void changeState (int state)
 changes node state
virtual void handleDeBruijnTimerExpired ()
 handle an expired de bruijn timer
virtual bool handleRpcCall (BaseCallMessage *msg)
 handle an expired fix_fingers timer (dummy function)
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)
 This method is called if an RPC timeout has been reached.
virtual void handleRpcJoinResponse (JoinResponse *joinResponse)
 handle a received JOIN response
virtual void handleRpcDeBruijnRequest (DeBruijnCall *deBruinCall)
 handle a received DEBRUIJN request
virtual void handleRpcDeBruijnResponse (DeBruijnResponse *deBruijnResponse)
 handle a received DEBRUIJN response
virtual void handleDeBruijnTimeout (DeBruijnCall *deBruijnCall)
 handle a DEBRUIJN timeout
virtual NodeHandle findDeBruijnHop (const OverlayKey &destKey, KoordeFindNodeExtMessage *findNodeExt)
 returns the NodeHandle of the next hop to destination key using the de Bruijn list
NodeVector * findNode (const OverlayKey &key, int numRedundantNodes, int numSiblings, BaseOverlayMessage *msg)
 Implements the find node call.
virtual OverlayKey findStartKey (const OverlayKey &startKey, const OverlayKey &endKey, const OverlayKey &destKey, int &step)
 find a "good" routing key to destKey between startingKey and endKey with the longest matching prefix possible
virtual const NodeHandle & walkDeBruijnList (const OverlayKey &key)
 Given a key the function checks if the key falls between two nodes in the de Bruijn list.
virtual const NodeHandle & walkSuccessorList (const OverlayKey &key)
 Given a key the function checks if the key falls between two nodes in the de successor list.
virtual bool handleFailedNode (const TransportAddress &failed)
 Handles a failed node.
virtual void rpcJoin (JoinCall *call)
 Join Remote-Procedure-Call.
virtual void findFriendModules ()
 Assigns the finger table and successor list module to our reference.
virtual void initializeFriendModules ()
 initializes finger table and successor list
- Protected Member Functions inherited from oversim::Chord
virtual void handleJoinTimerExpired (cMessage *msg)
 handle a expired join timer
virtual void handleStabilizeTimerExpired (cMessage *msg)
 handle a expired stabilize timer
virtual void handleFixFingersTimerExpired (cMessage *msg)
 handle a expired fix_fingers timer
virtual void handleNewSuccessorHint (ChordMessage *chordMsg)
 handle a received NEWSUCCESSORHINT message
virtual NodeVector * closestPreceedingNode (const OverlayKey &key)
 looks up the finger table and returns the closest preceeding node.
virtual void joinOverlay ()
 Join the overlay with a given nodeID in thisNode.key.
virtual void joinForeignPartition (const NodeHandle &node)
 Join another overlay partition with the given node as bootstrap node.
virtual 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 rpcFixfingers (FixfingersCall *call)
 Fixfingers Remote-Procedure-Call.
virtual void rpcNotify (NotifyCall *call)
 NOTIFY Remote-Procedure-Call.
void rpcStabilize (StabilizeCall *call)
 STABILIZE Remote-Procedure-Call.
virtual void pingResponse (PingResponse *pingResponse, cPolymorphic *context, int rpcId, simtime_t rtt)
virtual void pingTimeout (PingCall *pingCall, const TransportAddress &dest, cPolymorphic *context, int rpcId)
virtual void handleRpcNotifyResponse (NotifyResponse *notifyResponse)
virtual void handleRpcStabilizeResponse (StabilizeResponse *stabilizeResponse)
virtual void handleRpcFixfingersResponse (FixfingersResponse *fixfingersResponse, double rtt=-1)
- 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 handleNodeGracefulLeaveNotification ()
 This method gets call **.gracefulLeaveDelay seconds before it is killed if this node is among the gracefulLeaveProbability nodes.
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 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
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

int deBruijnDelay
 number of seconds between two de bruijn calls
int deBruijnNumber
 number of current nodes in de bruijn list; depend on number of nodes in successor list
int deBruijnListSize
 maximal number of nodes in de bruijn list
int shiftingBits
 number of bits concurrently shifted in one routing step
bool useOtherLookup
 flag which is indicating that the optimization other lookup is enabled
bool useSucList
 flag which is indicating that the optimization using the successorlist is enabled
bool breakLookup
 flag is used during the recursive step when returning this node
bool setupDeBruijnBeforeJoin
 if true, first setup the de bruijn node using the bootstrap node and than join the ring
bool setupDeBruijnAtJoin
 if true, join the ring and setup the de bruijn node using the bootstrap node in parallel
int deBruijnCount
 number of de bruijn calls
int deBruijnBytesSent
 number of bytes sent during de bruijn calls
NodeHandle * deBruijnNodes
 List of de Bruijn nodes.
NodeHandle deBruijnNode
 Handle to our de Bruijn node.
cMessage * deBruijn_timer
 timer for periodic de bruijn stabilization
- Protected Attributes inherited from oversim::Chord
int joinRetry
int stabilizeRetry
 // retries before neighbor considered failed
double joinDelay
double stabilizeDelay
 stabilize interval (secs)
double fixfingersDelay
double checkPredecessorDelay
int successorListSize
bool aggressiveJoinMode
 use modified (faster) JOIN protocol
bool extendedFingerTable
unsigned int numFingerCandidates
bool proximityRouting
bool memorizeFailedSuccessor
bool newChordFingerTable
bool mergeOptimizationL1
bool mergeOptimizationL2
bool mergeOptimizationL3
bool mergeOptimizationL4
cMessage * join_timer
cMessage * stabilize_timer
cMessage * fixfingers_timer
cMessage * checkPredecessor_timer
int joinCount
int stabilizeCount
int fixfingersCount
int notifyCount
int newsuccessorhintCount
int joinBytesSent
int stabilizeBytesSent
int notifyBytesSent
int fixfingersBytesSent
int newsuccessorhintBytesSent
int keyLength
 length of an overlay key in bits
int missingPredecessorStabRequests
 missing StabilizeCall msgs
NodeHandle predecessorNode
 predecessor of this node
TransportAddress bootstrapNode
 node used to bootstrap
ChordFingerTable * fingerTable
 pointer to this node's finger table
ChordSuccessorList * successorList
 pointer to this node's successor list
- 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

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

Koorde overlay module.

Implementation of the Koorde KBR overlay as described in "Koorde: A simple degree-optimal distributed hash table" by M. Kaashoek and D. Karger

Author
Jochen Schenk
See Also
Chord, ChordSuccessorList

Definition at line 50 of file Koorde.h.

Constructor & Destructor Documentation

oversim::Koorde::~Koorde ( )
virtual

Definition at line 74 of file Koorde.cc.

{
cancelAndDelete(deBruijn_timer);
}

Member Function Documentation

void oversim::Koorde::changeState ( int  state)
protectedvirtual

changes node state

Parameters
statestate to change to

Reimplemented from oversim::Chord.

Definition at line 79 of file Koorde.cc.

{
Chord::changeState(toState);
switch(state) {
case INIT:
// init de Bruijn nodes
deBruijnNode = NodeHandle::UNSPECIFIED_NODE;
for (int i=0; i < deBruijnListSize; i++) {
deBruijnNodes[i] = NodeHandle::UNSPECIFIED_NODE;
}
updateTooltip();
break;
case JOIN:
if (setupDeBruijnBeforeJoin) {
// setup de bruijn node before joining the ring
cancelEvent(join_timer);
cancelEvent(deBruijn_timer);
scheduleAt(simTime(), deBruijn_timer);
} else if (setupDeBruijnAtJoin) {
cancelEvent(deBruijn_timer);
scheduleAt(simTime(), deBruijn_timer);
}
break;
case READY:
// init de Bruijn Protocol
cancelEvent(deBruijn_timer);
scheduleAt(simTime(), deBruijn_timer);
// since we don't need the fixfingers protocol in Koorde cancel timer
cancelEvent(fixfingers_timer);
break;
default:
break;
}
}
NodeHandle oversim::Koorde::findDeBruijnHop ( const OverlayKey &  destKey,
KoordeFindNodeExtMessage *  findNodeExt 
)
protectedvirtual

returns the NodeHandle of the next hop to destination key using the de Bruijn list

Parameters
destKeyThe destination key
findNodeExtThe FindNodeExtensionMessage
Returns
next hop to destination key

Definition at line 473 of file Koorde.cc.

{
if (findNodeExt->getRouteKey().isUnspecified()) {
if (!deBruijnNode.isUnspecified()) {
int step;
findNodeExt->setRouteKey(findStartKey(thisNode.getKey(),
successorList->getSuccessor().getKey(), destKey,
step));
findNodeExt->setStep(step);
} else {
breakLookup = true;
return successorList->getSuccessor();
}
}
// check if the route key falls in our responsibility or
// else forward the message to our successor
if (findNodeExt->getRouteKey().isBetweenR(thisNode.getKey(),
successorList->getSuccessor().getKey())) {
if ((unsigned int)findNodeExt->getStep() > destKey.getLength())
error("Koorde::findDeBruijnHop - Bounding error: "
"trying to get non existing bit out of overlay key!");
// update the route key
OverlayKey add = OverlayKey(destKey.getBit(destKey.getLength() -
findNodeExt->getStep()));
for (int i = 1; i < shiftingBits; i++) {
add = (add << 1) + OverlayKey(destKey.getBit(destKey.getLength() -
findNodeExt->getStep() - i));
}
OverlayKey routeKey = (findNodeExt->getRouteKey()<<shiftingBits) + add;
findNodeExt->setRouteKey(routeKey);
findNodeExt->setStep(findNodeExt->getStep() + shiftingBits);
if (deBruijnNode.isUnspecified()) {
breakLookup = true;
if (useSucList)
return walkSuccessorList(findNodeExt->getRouteKey());
else
return successorList->getSuccessor();
}
// check if the new route key falls between our
// de Bruijn node and its successor
if (deBruijnNumber > 0) {
if (findNodeExt->getRouteKey().isBetweenR(deBruijnNode.getKey(),
deBruijnNodes[0].getKey())) {
return deBruijnNode;
} else {
// otherwise check if the route key falls between
// our de Bruijn successors
NodeHandle nextHop = walkDeBruijnList(findNodeExt->
getRouteKey());
return nextHop;
}
} else {
return deBruijnNode;
}
} else {
breakLookup = true;
// if optimization is set search the successor list and
// de bruijn node to find "good" next hop
if (useSucList) {
if (deBruijnNode.isUnspecified()) {
return walkSuccessorList(findNodeExt->getRouteKey());
} else {
NodeHandle tmpHandle =
walkSuccessorList(findNodeExt->getRouteKey());
// todo: optimization - check complete deBruijnList
if (deBruijnNode.getKey().isBetween(tmpHandle.getKey(),
findNodeExt->getRouteKey())) {
return deBruijnNode;
} else {
return tmpHandle;
}
}
} else
return successorList->getSuccessor();
}
}
void oversim::Koorde::findFriendModules ( )
protectedvirtual

Assigns the finger table and successor list module to our reference.

Reimplemented from oversim::Chord.

Definition at line 764 of file Koorde.cc.

{
successorList = check_and_cast<ChordSuccessorList*>
(getParentModule()->getSubmodule("successorList"));
}
NodeVector * oversim::Koorde::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
keyThe lookup key.
numRedundantNodesMaximum number of next hop nodes to return.
numSiblingsnumber of siblings to return
msgA pointer to the BaseRouteMessage or FindNodeCall message of this lookup.
Returns
NodeVector with closest nodes.

Reimplemented from oversim::Chord.

Definition at line 405 of file Koorde.cc.

{
// TODO: return redundant nodes for iterative routing
// TODO: try to always calculate optimal routing key (if e.g.
// the originator didn't have its deBruijnNode set already, the
// routing key may be very far away on the ring)
NodeVector* nextHop = new NodeVector();
KoordeFindNodeExtMessage *findNodeExt = NULL;
if (state != READY)
return nextHop;
if (msg != NULL) {
if (!msg->hasObject("findNodeExt")) {
findNodeExt = new KoordeFindNodeExtMessage("findNodeExt");
findNodeExt->setRouteKey(OverlayKey::UNSPECIFIED_KEY);
findNodeExt->setStep(1);
findNodeExt->setBitLength(KOORDEFINDNODEEXTMESSAGE_L);
msg->addObject( findNodeExt );
}
findNodeExt = (KoordeFindNodeExtMessage*) msg->getObject("findNodeExt");
}
if (key.isUnspecified()) {
error("Koorde::findNode() - direct Messaging is no longer in use.");
} else if (key.isBetweenR(predecessorNode.getKey(), thisNode.getKey())) {
// the message is destined for this node
nextHop->push_back(thisNode);
} else if (key.isBetweenR(thisNode.getKey(),
successorList->getSuccessor().getKey())){
// the message destined for our successor
nextHop->push_back(successorList->getSuccessor());
} else {
// if useOtherLookup is enabled we try to use
// our successor list to get to the key
if (useOtherLookup) {
NodeHandle tmpNode = walkSuccessorList(key);
if (tmpNode !=
successorList->getSuccessor(successorList->getSize() - 1)) {
nextHop->push_back(tmpNode);
} else {
NodeHandle tmpHandle = findDeBruijnHop(key, findNodeExt);
if (tmpHandle != thisNode || breakLookup) {
nextHop->push_back(tmpHandle);
breakLookup = false;
} else {
return findNode(key, numRedundantNodes, numSiblings, msg);
}
}
} else {
// find next hop using either the de Bruijn node and
// its successors or our own successors
NodeHandle tmpHandle = findDeBruijnHop(key, findNodeExt);
if (tmpHandle != thisNode || breakLookup) {
nextHop->push_back(tmpHandle);
breakLookup = false;
} else {
return findNode(key, numRedundantNodes, numSiblings, msg);
}
}
}
return nextHop;
}
OverlayKey oversim::Koorde::findStartKey ( const OverlayKey &  startKey,
const OverlayKey &  endKey,
const OverlayKey &  destKey,
int &  step 
)
protectedvirtual

find a "good" routing key to destKey between startingKey and endKey with the longest matching prefix possible

Parameters
startKeybegin of the (key) interval
endKeyend of the (key) interval
destKeydestination key - should be matched as good as possible
stepreference to return the bit position
Returns
a "good" routing key to start from

Definition at line 664 of file Koorde.cc.

{
OverlayKey diffKey, newStart, tmpDest, newKey, powKey;
int nBits;
if (startKey == endKey)
return startKey;
diffKey = endKey - startKey;
nBits = diffKey.log_2();
if (nBits < 0) {
nBits = 0;
}
while ((startKey.getLength() - nBits) % shiftingBits != 0) {
nBits--;
}
step = nBits + 1;
#if 0
// TODO: work in progress to find better start key
uint shared;
for (shared = 0; shared < (startKey.getLength() - nBits); shared += shiftingBits) {
if (destKey.sharedPrefixLength(startKey << shared) >= (startKey.getLength() - nBits - shared)) {
break;
}
}
uint nBits2 = startKey.getLength() - shared;
newStart = (startKey >> nBits2) << nBits2;
tmpDest = destKey >> (destKey.getLength() - nBits2);
newKey = tmpDest + newStart;
std::cout << "startKey: " << startKey.toString(2) << endl
<< "endKey : " << endKey.toString(2) << endl
<< "diff : " << (endKey-startKey).toString(2) << endl
<< "newKey : " << newKey.toString(2) << endl
<< "destKey : " << destKey.toString(2) << endl
<< "nbits : " << nBits << endl
<< "nbits2 : " << nBits2 << endl;
// is the new constructed route key bigger than our start key return it
if (newKey.isBetweenR(startKey, endKey)) {
std::cout << "HIT" << endl;
return newKey;
} else {
nBits2 -= shiftingBits;
newStart = (startKey >> nBits2) << nBits2;
tmpDest = destKey >> (destKey.getLength() - nBits2);
newKey = tmpDest + newStart;
if (newKey.isBetweenR(startKey, endKey)) {
std::cout << "startKey: " << startKey.toString(2) << endl
<< "endKey : " << endKey.toString(2) << endl
<< "diff : " << (endKey-startKey).toString(2) << endl
<< "newKey : " << newKey.toString(2) << endl
<< "destKey : " << destKey.toString(2) << endl
<< "nbits : " << nBits << endl
<< "nbits2 : " << nBits2 << endl;
std::cout << "HIT2" << endl;
return newKey;
}
}
std::cout << "MISS" << endl;
#endif
newStart = (startKey >> nBits) << nBits;
tmpDest = destKey >> (destKey.getLength() - nBits);
newKey = tmpDest + newStart;
// is the new constructed route key bigger than our start key return it
if (newKey.isBetweenR(startKey, endKey)) {
return newKey;
}
// If the part of the destination key smaller than the one of
// the original key add pow(nBits) (this is the first bit where
// the start key and end key differ) to the new constructed key
// and check if it's between start and end key.
newKey += powKey.pow2(nBits);
if (newKey.isBetweenR(startKey, endKey)) {
return newKey;
} else {
// this part should not be called
throw cRuntimeError("Koorde::findStartKey(): Invalid start key");
return OverlayKey::UNSPECIFIED_KEY;
}
}
void oversim::Koorde::finishOverlay ( )
virtual

collects statistical data in derived class

Reimplemented from oversim::Chord.

Definition at line 626 of file Koorde.cc.

{
// statistics
simtime_t time = globalStatistics->calcMeasuredLifetime(creationTime);
if (time >= GlobalStatistics::MIN_MEASURED) {
globalStatistics->addStdDev("Koorde: Sent DEBRUIJN Messages/s",
deBruijnCount / time);
globalStatistics->addStdDev("Koorde: Sent DEBRUIJN Bytes/s",
deBruijnBytesSent / time);
}
Chord::finishOverlay();
}
void oversim::Koorde::handleDeBruijnTimeout ( DeBruijnCall *  deBruijnCall)
protectedvirtual

handle a DEBRUIJN timeout

Parameters
deBruijnCallthe message which timed out

Definition at line 392 of file Koorde.cc.

{
if (setupDeBruijnBeforeJoin && (state == JOIN)) {
// failed to set initial de bruijn node
// -> get a new bootstrap node and try again
changeState(JOIN);
return;
}
cancelEvent(deBruijn_timer);
scheduleAt(simTime(), deBruijn_timer);
}
void oversim::Koorde::handleDeBruijnTimerExpired ( )
protectedvirtual

handle an expired de bruijn timer

Definition at line 164 of file Koorde.cc.

{
OverlayKey lookup = thisNode.getKey() << shiftingBits;
if (state == READY) {
if (successorList->getSize() > 0) {
// look for some nodes before our actual de-bruijn key
// to have redundancy if our de-bruijn node fails
lookup -= (successorList->getSuccessor(successorList->getSize() /
2).getKey() - thisNode.getKey());
}
if (lookup.isBetweenR(thisNode.getKey(),
successorList->getSuccessor().getKey())
|| successorList->isEmpty()) {
int sucNum = successorList->getSize();
if (sucNum > deBruijnListSize)
sucNum = deBruijnListSize;
deBruijnNode = thisNode;
for (int i = 0; i < sucNum; i++) {
deBruijnNodes[i] = successorList->getSuccessor(i);
deBruijnNumber = i+1;
}
updateTooltip();
} else if (lookup.isBetweenR(predecessorNode.getKey(),
thisNode.getKey())) {
int sucNum = successorList->getSize();
if ((sucNum + 1) > deBruijnListSize)
sucNum = deBruijnListSize - 1;
deBruijnNode = predecessorNode;
deBruijnNodes[0] = thisNode;
for (int i = 0; i < sucNum; i++) {
deBruijnNodes[i+1] = successorList->getSuccessor(i);
deBruijnNumber = i+2;
}
updateTooltip();
} else {
DeBruijnCall* call = new DeBruijnCall("DeBruijnCall");
call->setDestKey(lookup);
call->setBitLength(DEBRUIJNCALL_L(call));
sendRouteRpcCall(OVERLAY_COMP, TransportAddress(deBruijnNode),
call->getDestKey(), call, NULL,
DEFAULT_ROUTING);
}
cancelEvent(deBruijn_timer);
scheduleAt(simTime() + deBruijnDelay, deBruijn_timer);
} else {
if (setupDeBruijnBeforeJoin || setupDeBruijnAtJoin) {
DeBruijnCall* call = new DeBruijnCall("DeBruijnCall");
call->setDestKey(lookup);
call->setBitLength(DEBRUIJNCALL_L(call));
sendRouteRpcCall(OVERLAY_COMP, bootstrapNode, call->getDestKey(),
call, NULL, DEFAULT_ROUTING);
scheduleAt(simTime() + deBruijnDelay, deBruijn_timer);
}
}
}
bool oversim::Koorde::handleFailedNode ( const TransportAddress &  failed)
protectedvirtual

Handles a failed node.

This method is called whenever a node given by findNode() was unreachable. The default implementation does nothing at all.

Parameters
failedthe failed node
Returns
true if lookup should retry here

Reimplemented from oversim::Chord.

Definition at line 130 of file Koorde.cc.

{
if (!deBruijnNode.isUnspecified()) {
if (failed == deBruijnNode) {
deBruijnNode = deBruijnNodes[0];
for (int i = 0; i < deBruijnNumber - 1; i++) {
deBruijnNodes[i] = deBruijnNodes[i+1];
}
if (deBruijnNumber > 0) {
deBruijnNodes[deBruijnNumber - 1] = NodeHandle::UNSPECIFIED_NODE;
--deBruijnNumber;
}
} else {
bool removed = false;
for (int i = 0; i < deBruijnNumber - 1; i++) {
if ((!deBruijnNodes[i].isUnspecified()) &&
(failed == deBruijnNodes[i])) {
removed = true;
}
if (removed ||
((!deBruijnNodes[deBruijnNumber - 1].isUnspecified())
&& failed == deBruijnNodes[deBruijnNumber - 1])) {
deBruijnNodes[deBruijnNumber - 1] =
NodeHandle::UNSPECIFIED_NODE;
--deBruijnNumber;
}
}
}
}
return Chord::handleFailedNode(failed);
}
bool oversim::Koorde::handleRpcCall ( BaseCallMessage *  msg)
protectedvirtual

handle an expired fix_fingers timer (dummy function)

Parameters
msgthe timer self-message

Reimplemented from oversim::Chord.

Definition at line 245 of file Koorde.cc.

{
if (state == READY) {
// delegate messages
RPC_SWITCH_START( msg )
RPC_DELEGATE( DeBruijn, handleRpcDeBruijnRequest );
RPC_SWITCH_END( )
if (RPC_HANDLED) return true;
} else {
EV << "[Koorde::handleRpcCall() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received RPC call and state != READY!"
<< endl;
}
return Chord::handleRpcCall(msg);
}
void oversim::Koorde::handleRpcDeBruijnRequest ( DeBruijnCall *  deBruinCall)
protectedvirtual

handle a received DEBRUIJN request

Parameters
deBruinCallthe message to process

Definition at line 328 of file Koorde.cc.

{
// The key lies between thisNode and its predecessor and
// because routing the message to the predecessor of a key
// is near to impossible we set the deBruijnNodes here
// and the information is as actual as the predecessor pointer.
//
// If this is the only node in the ring, it is the temporary de bruijn
// node for the joining node.
if ((predecessorNode.isUnspecified() && successorList->isEmpty())
|| deBruijnCall->getDestKey().isBetweenR(predecessorNode.getKey(),
thisNode.getKey())) {
DeBruijnResponse* deBruijnResponse =
new DeBruijnResponse("DeBruijnResponse");
if (predecessorNode.isUnspecified()) {
deBruijnResponse->setDBNode(thisNode);
} else {
deBruijnResponse->setDBNode(predecessorNode);
}
int sucNum = successorList->getSize() + 1;
deBruijnResponse->setSucNum(sucNum);
deBruijnResponse->setSucNodeArraySize(sucNum);
deBruijnResponse->setSucNode(0, thisNode);
for (int k = 1; k < sucNum; k++) {
deBruijnResponse->setSucNode(k, successorList->getSuccessor(k-1));
}
deBruijnResponse->setBitLength(DEBRUIJNRESPONSE_L(deBruijnResponse));
sendRpcResponse(deBruijnCall, deBruijnResponse);
} else if (deBruijnCall->getDestKey().isBetweenR(thisNode.getKey(),
successorList->getSuccessor().getKey())) {
error("Koorde::handleRpcDeBruijnRequest() - unknown error.");
} else {
error("Koorde::handleRpcDeBruijnRequest() - "
"Request couldn't be delivered!");
}
}
void oversim::Koorde::handleRpcDeBruijnResponse ( DeBruijnResponse *  deBruijnResponse)
protectedvirtual

handle a received DEBRUIJN response

Parameters
deBruijnResponsethe message to process

Definition at line 369 of file Koorde.cc.

{
int sucNum = deBruijnResponse->getSucNum();
if (sucNum > deBruijnListSize)
sucNum = deBruijnListSize;
for (int i = 0; i < sucNum; i++) {
deBruijnNodes[i] = deBruijnResponse->getSucNode(i);
deBruijnNumber = i+1;
}
deBruijnNode = deBruijnResponse->getDBNode();
updateTooltip();
if (setupDeBruijnBeforeJoin && (state == JOIN)) {
// now that we have a valid de bruijn node it's time to join the ring
if (!join_timer->isScheduled()) {
scheduleAt(simTime(), join_timer);
}
}
}
void oversim::Koorde::handleRpcJoinResponse ( JoinResponse *  joinResponse)
protectedvirtual

handle a received JOIN response

Parameters
joinResponsethe message to process

Reimplemented from oversim::Chord.

Definition at line 304 of file Koorde.cc.

{
Chord::handleRpcJoinResponse(joinResponse);
// has to be canceled in Koorde
cancelEvent(fixfingers_timer);
// immediate deBruijn protocol
cancelEvent(deBruijn_timer);
scheduleAt(simTime(), deBruijn_timer);
}
void oversim::Koorde::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 oversim::Chord.

Definition at line 264 of file Koorde.cc.

{
Chord::handleRpcResponse(msg, context, rpcId, rtt);
RPC_SWITCH_START( msg )
RPC_ON_RESPONSE( DeBruijn ) {
handleRpcDeBruijnResponse(_DeBruijnResponse);
EV << "[Koorde::handleRpcResponse() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " DeBruijn RPC Response received: id=" << rpcId
<< "\n msg=" << *_DeBruijnResponse << " rtt=" << rtt
<< endl;
break;
}
RPC_SWITCH_END( )
}
void oversim::Koorde::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
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 oversim::Chord.

Definition at line 283 of file Koorde.cc.

{
Chord::handleRpcTimeout(msg, dest, context, rpcId, destKey);
RPC_SWITCH_START( msg )
RPC_ON_CALL( DeBruijn ) {
handleDeBruijnTimeout(_DeBruijnCall);
EV << "[Koorde::handleRpcTimeout() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " DeBruijn RPC Call timed out: id=" << rpcId
<< "\n msg=" << *_DeBruijnCall
<< endl;
break;
}
RPC_SWITCH_END( )
}
void oversim::Koorde::handleTimerEvent ( cMessage *  msg)
virtual

Reimplemented from oversim::Chord.

Definition at line 119 of file Koorde.cc.

{
if (msg->isName("deBruijn_timer")) {
handleDeBruijnTimerExpired();
} else if (msg->isName("fixfingers_timer")) {
handleFixFingersTimerExpired(msg);
} else {
Chord::handleTimerEvent(msg);
}
}
void oversim::Koorde::handleUDPMessage ( BaseOverlayMessage *  msg)
virtual

Processes messages from underlay.

Parameters
msgMessage from UDP

Reimplemented from oversim::Chord.

Definition at line 239 of file Koorde.cc.

{
Chord::handleUDPMessage(msg);
}
void oversim::Koorde::initializeFriendModules ( )
protectedvirtual

initializes finger table and successor list

Reimplemented from oversim::Chord.

Definition at line 770 of file Koorde.cc.

{
// initialize successor list
successorList->initializeList(par("successorListSize"), thisNode, this);
}
void oversim::Koorde::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
stagethe init stage

Reimplemented from oversim::Chord.

Definition at line 37 of file Koorde.cc.

{
// because of IPAddressResolver, we need to wait until interfaces
// are registered, address auto-assignment takes place etc.
if (stage != MIN_STAGE_OVERLAY)
return;
// fetch some parameters
deBruijnDelay = par("deBruijnDelay");
deBruijnListSize = par("deBruijnListSize");
shiftingBits = par("shiftingBits");
useOtherLookup = par("useOtherLookup");
useSucList = par("useSucList");
setupDeBruijnBeforeJoin = par("setupDeBruijnBeforeJoin");
setupDeBruijnAtJoin = par("setupDeBruijnAtJoin");
// init flags
breakLookup = false;
// some local variables
deBruijnNumber = 0;
deBruijnNodes = new NodeHandle[deBruijnListSize];
// statistics
deBruijnCount = 0;
deBruijnBytesSent = 0;
// add some watches
WATCH(deBruijnNumber);
WATCH(deBruijnNode);
// timer messages
deBruijn_timer = new cMessage("deBruijn_timer");
Chord::initializeOverlay(stage);
}
void oversim::Koorde::recordOverlaySentStats ( BaseOverlayMessage *  msg)
virtual

Collect overlay specific sent messages statistics.

This method is called from BaseOverlay::sendMessageToUDP() for every overlay message that is sent by a node. Use this to collect statistical data for overlay protocol specific message types.

Parameters
msgThe overlay message to be sent to the UDP layer

Reimplemented from oversim::Chord.

Definition at line 641 of file Koorde.cc.

{
Chord::recordOverlaySentStats(msg);
BaseOverlayMessage* innerMsg = msg;
while (innerMsg->getType() != APPDATA &&
innerMsg->getEncapsulatedPacket() != NULL) {
innerMsg =
static_cast<BaseOverlayMessage*>(innerMsg->getEncapsulatedPacket());
}
switch (innerMsg->getType()) {
case RPC: {
if ((dynamic_cast<DeBruijnCall*>(innerMsg) != NULL) ||
(dynamic_cast<DeBruijnResponse*>(innerMsg) != NULL)) {
RECORD_STATS(deBruijnCount++; deBruijnBytesSent +=
msg->getByteLength());
}
break;
}
}
}
void oversim::Koorde::rpcJoin ( JoinCall *  call)
protectedvirtual

Join Remote-Procedure-Call.

Parameters
callRPC Parameter Message

Reimplemented from oversim::Chord.

Definition at line 317 of file Koorde.cc.

{
Chord::rpcJoin(joinCall);
if (predecessorNode == successorList->getSuccessor()) {
// second node join -> need to setup our de bruijn node
handleDeBruijnTimerExpired();
}
}
void oversim::Koorde::updateTooltip ( )
virtual

updates information shown in tk-environment

Reimplemented from oversim::Chord.

Definition at line 584 of file Koorde.cc.

{
//
// Updates the tooltip display strings.
//
if (ev.isGUI()) {
std::stringstream ttString;
// show our predecessor, successor and de Bruijn node in tooltip
ttString << "Pred "<< predecessorNode << endl << "This "
<< thisNode << endl
<< "Suc " << successorList->getSuccessor() << endl
<< "DeBr " << deBruijnNode << endl;
ttString << "List ";
for (unsigned int i = 0; i < successorList->getSize(); i++) {
ttString << successorList->getSuccessor(i).getIp() << " ";
}
ttString << endl;
ttString << "DList ";
for (int i = 0; i < deBruijnNumber; i++) {
ttString << deBruijnNodes[i].getIp() << " ";
}
ttString << endl;
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());
// draw an arrow to our current successor
showOverlayNeighborArrow(successorList->getSuccessor(), true,
"m=m,50,0,50,0;ls=red,1");
}
}
const NodeHandle & oversim::Koorde::walkDeBruijnList ( const OverlayKey &  key)
protectedvirtual

Given a key the function checks if the key falls between two nodes in the de Bruijn list.

If no match is found the last node in the de Bruijn list is returned.

Parameters
keythe key to check
Returns
either the node directly preceding key or the node which has the shortest distance to the key

Definition at line 558 of file Koorde.cc.

{
if (deBruijnNumber == 0)
return NodeHandle::UNSPECIFIED_NODE;
for (int i = 0; i < deBruijnNumber-1; i++) {
if (key.isBetweenR(deBruijnNodes[i].getKey(),deBruijnNodes[i+1].getKey())) {
return deBruijnNodes[i];
}
}
return deBruijnNodes[deBruijnNumber-1];
}
const NodeHandle & oversim::Koorde::walkSuccessorList ( const OverlayKey &  key)
protectedvirtual

Given a key the function checks if the key falls between two nodes in the de successor list.

If no match is found the last node in the de successor list is returned.

Parameters
keythe key to check
Returns
either the node directly preceding key or the node which has the shortest distance to the key

Definition at line 572 of file Koorde.cc.

{
for (unsigned int i = 0; i < successorList->getSize()-1; i++) {
if (key.isBetweenR(successorList->getSuccessor(i).getKey(),
successorList->getSuccessor(i+1).getKey())) {
return successorList->getSuccessor(i);
}
}
return successorList->getSuccessor(successorList->getSize()-1);
}

Member Data Documentation

bool oversim::Koorde::breakLookup
protected

flag is used during the recursive step when returning this node

Definition at line 83 of file Koorde.h.

cMessage* oversim::Koorde::deBruijn_timer
protected

timer for periodic de bruijn stabilization

Definition at line 96 of file Koorde.h.

int oversim::Koorde::deBruijnBytesSent
protected

number of bytes sent during de bruijn calls

Definition at line 89 of file Koorde.h.

int oversim::Koorde::deBruijnCount
protected

number of de bruijn calls

Definition at line 88 of file Koorde.h.

int oversim::Koorde::deBruijnDelay
protected

number of seconds between two de bruijn calls

Definition at line 77 of file Koorde.h.

int oversim::Koorde::deBruijnListSize
protected

maximal number of nodes in de bruijn list

Definition at line 79 of file Koorde.h.

NodeHandle oversim::Koorde::deBruijnNode
protected

Handle to our de Bruijn node.

Definition at line 93 of file Koorde.h.

NodeHandle* oversim::Koorde::deBruijnNodes
protected

List of de Bruijn nodes.

Definition at line 92 of file Koorde.h.

int oversim::Koorde::deBruijnNumber
protected

number of current nodes in de bruijn list; depend on number of nodes in successor list

Definition at line 78 of file Koorde.h.

bool oversim::Koorde::setupDeBruijnAtJoin
protected

if true, join the ring and setup the de bruijn node using the bootstrap node in parallel

Definition at line 85 of file Koorde.h.

bool oversim::Koorde::setupDeBruijnBeforeJoin
protected

if true, first setup the de bruijn node using the bootstrap node and than join the ring

Definition at line 84 of file Koorde.h.

int oversim::Koorde::shiftingBits
protected

number of bits concurrently shifted in one routing step

Definition at line 80 of file Koorde.h.

bool oversim::Koorde::useOtherLookup
protected

flag which is indicating that the optimization other lookup is enabled

Definition at line 81 of file Koorde.h.

bool oversim::Koorde::useSucList
protected

flag which is indicating that the optimization using the successorlist is enabled

Definition at line 82 of file Koorde.h.

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