OverSim
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
NTree Class Reference

A p2p protocol for MMOGs and virtual worlds. More...

#include <NTree.h>

Inheritance diagram for NTree:
BaseOverlay BaseRpc BaseTcpSupport TopologyVis RpcListener

Public Member Functions

virtual ~NTree ()
virtual void initializeOverlay (int stage)
 Initializes derived-class-attributes.
virtual void finishOverlay ()
 collects statistical data in derived class
virtual void handleUDPMessage (BaseOverlayMessage *msg)
 Processes messages from underlay.
virtual void handleTimerEvent (cMessage *msg)
virtual void handleAppMessage (cMessage *msg)
 Processes "timer" self-messages.
virtual bool handleRpcCall (BaseCallMessage *msg)
 Processes Remote-Procedure-Call invocation messages.
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.
- 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)
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.
virtual int getMaxNumSiblings ()
 Query the maximum number of siblings (nodes close to a key) that are maintained by this overlay protocol.
virtual int getMaxNumRedundantNodes ()
 Query the maximum number of redundant next hop nodes that are returned by findNode().
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.
virtual OverlayKey distance (const OverlayKey &x, const OverlayKey &y, bool useAlternative=false) const
 This method should implement the distance between two keys.
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

void setBootstrapedIcon ()
void handleMove (GameAPIPositionMessage *posMsg)
 Handles a move message from the application.
void handleMoveMessage (NTreeMoveMessage *moveMsg)
 Handles a move message from the network.
void handleJoinCall (NTreeJoinCall *joinCall)
 Handles request to join a group.
void handleJoinResponse (NTreeJoinResponse *joinResp)
 Handles the acknowledgement to join a group.
void handleJoinCallTimeout (NTreeJoinCall *joinCall, const TransportAddress &oldNode)
 Gets called if a join call times out Well try to re-join if needed.
void handlePingCall (NTreePingCall *pingCall)
 Handles a ping If the ping was send to a node in the n-tree, it is answered with information about the satte of that n-tree node (children, aggregated size)
void handlePingResponse (NTreePingResponse *pingResp, NTreePingContext *context)
 Handles a ping response.
void handlePingCallTimeout (NTreePingCall *pingCall, const TransportAddress &oldNode, NTreePingContext *context)
 Handles a ping timeout Inform others about the failed node, replace it if needed.
void handleDivideCall (NTreeDivideCall *divideCall)
 Handles a request to divide a group.
void handleDivideResponse (NTreeDivideResponse *divideResp, NTreeGroupDivideContext *context)
 Handles an acknowledgement that a group was divided as requested.
void handleDivideCallTimeout (NTreeDivideCall *divideCall, const TransportAddress &oldNode, NTreeGroupDivideContext *context)
 Gets called if a divide call times out Re-send the request to a different node.
void handleAddMessage (NTreeGroupAddMessage *addMsg)
 Handles an information message that somebody joined a group we are a member of.
void handleDeleteMessage (NTreeGroupDeleteMessage *deleteMsg)
 Handles an information message that a group we are a member of is going to be deleted.
void handleLeaveMessage (NTreeLeaveMessage *leaveMsg)
 Handles an information message that somebody left a group we are a member of.
void handleCollapseMessage (NTreeCollapseMessage *collapseMsg)
 Handles an information message that a subtree we are part of is collapsed.
void handleReplaceMessage (NTreeReplaceNodeMessage *replaceMsg)
 Handles a request to replace a failed or leaving node.
void handleTakeOverMessage (NTreeTakeOverMessage *takeMsg)
 Handles an information message that a node took over the responsibilities of a failed or leaving node.
void handleNodeGracefulLeaveNotification ()
 This method gets call **.gracefulLeaveDelay seconds before it is killed if this node is among the gracefulLeaveProbability nodes.
void divideNode (NTreeGroupDivideContext *context)
 Divide a group that has gotten to large into four subgroups.
void collapseTree (std::map< NTreeScope, NTreeNode >::iterator node)
 Collapse a subtree that has too few children.
void joinGroup (Vector2D position)
 Joins the group that is responsible for a given position.
void leaveGroup (Vector2D position, bool force=false)
 Leaves a group for a given position.
void pingNodes ()
 Ping all children of all groups.
void checkParentTimeout ()
 Check if a parent failed to send a ping for a longer time.
void routeViaNTree (const Vector2D &pos, cPacket *msg, bool forward=false)
 Route a message through the N-Tree to the closest know node to the given position.
void sendToGroup (const NTreeGroup &grp, cPacket *msg, bool keepMsg=false)
 Sends a message to all members of a group.
void sendToGroup (const std::set< NodeHandle > &grp, cPacket *msg, bool keepMsg=false)
 Sends a message to all members of a group.
void sendMessage (const TransportAddress &dest, cPacket *msg, bool forward=false)
 Sends a message to a host.
void changeState (int state)
 Change the internal state of the protocol.
std::list< NTreeGroup >::iterator findGroup (const Vector2D &pos)
 Find a group that is responsible for the given position from the local list of groups.
std::list< NTreeGroup >::iterator findGroup (const Vector2D &pos, double size)
 Find a group that is responsible for the given position from the local list of groups Only return a group if it maches the exact scope given.
std::map< NTreeScope,
NTreeNode >::iterator 		findNTreeNode (const Vector2D &pos)
 Find the lowest ntree node that contains the given position.
std::map< NTreeScope,
NTreeNode >::iterator 		findNTreeNode (const Vector2D &pos, double size)
 Find the group that matches the given scope.
NodeHandle getRandomNode (std::set< NodeHandle > invalidNodes=std::set< NodeHandle >())
 Return a random node.
- 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 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 NodeVector * findNode (const OverlayKey &key, int numRedundantNodes, int numSiblings, BaseOverlayMessage *msg=NULL)
 Implements the find node call.
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 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

unsigned int AOIWidth
unsigned int maxChildren
double areaDimension
Vector2D position
NTreeGroup * currentGroup
simtime_t pingInterval
cMessage * joinTimer
cMessage * pingTimer
std::list< NTreeGroup > groups
std::map< NTreeScope, NTreeNode > ntreeNodes
unsigned int joinsSend
unsigned int joinBytes
unsigned int joinTimeout
unsigned int divideCount
unsigned int collapseCount
unsigned int treeMaintenanceMessages
unsigned int treeMaintenanceBytes
unsigned int movesSend
unsigned int moveBytes
- 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

A p2p protocol for MMOGs and virtual worlds.

Provides the GameAPI interface Based upon: GauthierDickey, C., Lo, V., and Zappala, D. 2005. "Using n-trees for scalable event ordering in peer-to-peer games". In Proceedings of the international Workshop on Network and Operating Systems Support For Digital Audio and Video (Stevenson, Washington, USA, June 13 - 14, 2005). NOSSDAV '05. ACM, New York, NY, 87-92. DOI= http://doi.acm.org/10.1145/1065983.1066005

Author
STephan Krause

Definition at line 45 of file NTree.h.

Constructor & Destructor Documentation

NTree::~NTree ( )
virtual

Definition at line 1439 of file NTree.cc.

{
cancelAndDelete(joinTimer);
cancelAndDelete(pingTimer);
}

Member Function Documentation

void NTree::changeState ( int  state)
protected

Change the internal state of the protocol.

Parameters
statethe state (see enum States in BaseOverlay.h)

Definition at line 1323 of file NTree.cc.

{
switch( newState ){
case INIT:
state = INIT;
if( !joinTimer->isScheduled() ) {
scheduleAt( ceil(simTime() + (simtime_t) par("joinDelay")), joinTimer );
}
break;
case READY:
state = READY;
setBootstrapedIcon();
if( !currentGroup && groups.size() ) currentGroup = &groups.front();
setOverlayReady( true );
break;
case JOIN:
state = JOIN;
setOverlayReady( false );
break;
case SHUTDOWN:
state = SHUTDOWN;
cancelAndDelete( pingTimer );
pingTimer = NULL;
setOverlayReady( false );
break;
}
setBootstrapedIcon();
}
void NTree::checkParentTimeout ( )
protected

Check if a parent failed to send a ping for a longer time.

Definition at line 1070 of file NTree.cc.

{
// Go throup all nodes. iterator is incremented in-loop to allow deletion
for(std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.begin(); it != ntreeNodes.end(); ){
if( it->second.parent.isUnspecified() || (it->second.lastPing == 0) ) {
++it;
continue;
}
if( it->second.lastPing + pingInterval + pingInterval < simTime() ){
// Parent timed out
EV << "[NTree::checkParentTimeout() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Parent for node" << it->second << " timed out\n";
// Replace parent if parent is root. Other parents will be replaced by their parents
// Also, only sibling[0] does the replacing to avoid conflicts.
if( it->second.parentIsRoot ) {
if( it->second.siblings[0] == thisNode ){
EV << " Parent was root. Replacing him\n";
NTreeReplaceNodeMessage* replaceMsg = new NTreeReplaceNodeMessage("Replace failed ROOT.");
replaceMsg->setOrigin( Vector2D(areaDimension/2.0, areaDimension/2.0) );
replaceMsg->setSize( areaDimension );
replaceMsg->setIsLeaf( false );
replaceMsg->setChildrenArraySize( 4 );
replaceMsg->setOldNode( it->second.parent );
std::set<NodeHandle> invalidNodes;
for( unsigned int i = 0; i < 4; ++i ){
replaceMsg->setChildren( i, it->second.siblings[i] );
invalidNodes.insert( replaceMsg->getChildren(i) );
}
replaceMsg->setBitLength( NTREEREPLACE_L(replaceMsg) );
const NodeHandle& dest = getRandomNode( invalidNodes );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += replaceMsg->getByteLength();
);
sendMessage(dest, replaceMsg );
}
++it;
} else {
// else drop node
if( it->second.group ){
if( currentGroup && *currentGroup == *it->second.group ){
currentGroup = NULL;
}
groups.remove( *it->second.group );
}
ntreeNodes.erase( it++ );
}
} else {
++it;
}
}
}
void NTree::collapseTree ( std::map< NTreeScope, NTreeNode >::iterator  node)
protected

Collapse a subtree that has too few children.

Parameters
nodethe new leaf of the subtree

Definition at line 1168 of file NTree.cc.

{
EV << "[NTree::CollapseTree() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Collapsing tree" << node->second << "\n";
// Inform children
NTreeCollapseMessage* collapseMsg = new NTreeCollapseMessage("Collapse Tree");
collapseMsg->setPlayer( thisNode );
collapseMsg->setBitLength( NTREECOLLAPSE_L(collapseMsg) );
for( unsigned int i = 0; i < 4; ++i ){
collapseMsg->setOrigin( node->second.scope.getSubScope(i).origin );
collapseMsg->setSize( node->second.scope.getSubScope(i).size );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += collapseMsg->getByteLength();
collapseCount ++;
);
sendMessage( node->second.children[i], collapseMsg->dup() );
// and update node
node->second.children[i] = NodeHandle::UNSPECIFIED_NODE;
node->second.childChildren[i].clear();
node->second.aggChildCount[i] = 0;
}
delete collapseMsg;
// create group for node
NTreeGroup newGroup( node->second.scope );
newGroup.leader = thisNode;
newGroup.members.insert( thisNode );
groups.push_front( newGroup );
node->second.group = &(groups.front());
}
void NTree::divideNode ( NTreeGroupDivideContext *  context)
protected

Divide a group that has gotten to large into four subgroups.

Parameters
contextA context pointer to coordinate the four new children

Definition at line 1126 of file NTree.cc.

{
EV << "[NTree::divideNode() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Trying to divide node " << context->nodeScope << "\n";
std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.find( context->nodeScope );
if( it == ntreeNodes.end() ){
EV << " However, node is not in the list of known nodes\n";
return;
}
if( !it->second.group ){
EV << " However, node has no known group attached\n";
return;
}
// Inform group members
NTreeGroupDeleteMessage* delMsg = new NTreeGroupDeleteMessage("Delete Group due to divide");
delMsg->setOrigin( context->nodeScope.origin );
delMsg->setSize( context->nodeScope.size );
delMsg->setBitLength( NTREEDELETE_L(delMsg) );
for( unsigned int i = 0; i < 4; ++i ){
delMsg->setNewChild(i, context->newChild[i] );
}
RECORD_STATS(
divideCount ++;
treeMaintenanceMessages+= it->second.group->members.size();
treeMaintenanceBytes += it->second.group->members.size()*delMsg->getByteLength();
);
sendToGroup( *it->second.group, delMsg );
// delete group
if( currentGroup && *currentGroup == *it->second.group ){
currentGroup = NULL;
}
groups.remove( *it->second.group );
it->second.group= NULL;
// add children to ntreeNode
for( unsigned int i = 0; i < 4; ++i ){
it->second.children[i] = context->newChild[i];
}
}
std::list< NTreeGroup >::iterator NTree::findGroup ( const Vector2D &  pos)
protected

Find a group that is responsible for the given position from the local list of groups.

Parameters
posthe position

Definition at line 1372 of file NTree.cc.

{
for( std::list<NTreeGroup>::iterator it = groups.begin(); it != groups.end(); ++it ){
if( it->isInScope( pos ) ) return it;
}
return groups.end();
}
std::list< NTreeGroup >::iterator NTree::findGroup ( const Vector2D &  pos,
double  size 
)
protected

Find a group that is responsible for the given position from the local list of groups Only return a group if it maches the exact scope given.

Parameters
posthe origin of the group
sizethe size of the group

Definition at line 1380 of file NTree.cc.

{
for( std::list<NTreeGroup>::iterator it = groups.begin(); it != groups.end(); ++it ){
if( it->scope.origin == pos && it->scope.size == size ) return it;
}
return groups.end();
}
std::map< NTreeScope, NTreeNode >::iterator NTree::findNTreeNode ( const Vector2D &  pos)
protected

Find the lowest ntree node that contains the given position.

Parameters
posthe position

Definition at line 1388 of file NTree.cc.

{
double size = areaDimension + 1;
std::map<NTreeScope,NTreeNode>::iterator bestNode = ntreeNodes.end();
for( std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.begin(); it != ntreeNodes.end(); ++it ){
if( it->second.isInScope( pos ) && it->second.scope.size < size ){
bestNode = it;
size = bestNode->second.scope.size;
}
}
return bestNode;
}
std::map< NTreeScope, NTreeNode >::iterator NTree::findNTreeNode ( const Vector2D &  pos,
double  size 
)
protected

Find the group that matches the given scope.

Parameters
posthe origin of the node
sizethe size of the scope

Definition at line 1401 of file NTree.cc.

{
return ntreeNodes.find( NTreeScope( pos, size ) );
}
void NTree::finishOverlay ( )
virtual

collects statistical data in derived class

Reimplemented from BaseOverlay.

Definition at line 1424 of file NTree.cc.

{
simtime_t time = globalStatistics->calcMeasuredLifetime(creationTime);
if (time < GlobalStatistics::MIN_MEASURED) return;
globalStatistics->addStdDev("NTree: Joins send per second", joinsSend / time );
globalStatistics->addStdDev("NTree: Join bytes send per second", joinBytes / time );
globalStatistics->addStdDev("NTree: Join timeouts per second", joinTimeout / time );
globalStatistics->addStdDev("NTree: Tree maintenance messages send per second", treeMaintenanceMessages / time );
globalStatistics->addStdDev("NTree: Tree maintenance bytes send per second", treeMaintenanceBytes / time );
globalStatistics->addStdDev("NTree: Move messages send per second", movesSend / time );
globalStatistics->addStdDev("NTree: Move bytes send per second", moveBytes / time );
globalStatistics->addStdDev("NTree: Tree collapsed per second", collapseCount / time );
globalStatistics->addStdDev("NTree: Tree divides per second", divideCount / time );
}
NodeHandle NTree::getRandomNode ( std::set< NodeHandle >  invalidNodes = std::set<NodeHandle>())
protected

Return a random node.

Parameters
invalidNodesa list of nodes that should not be returned

Definition at line 1406 of file NTree.cc.

{
// FIXME: This is cheating...
bool found = false;
NodeHandle dest;
while( !found ){
dest = globalNodeList->getRandomNode();
found = true;
for( std::set<NodeHandle>::iterator it = invalidNodes.begin(); it != invalidNodes.end(); ++it ){
if( dest == *it ){
found = false;
break;
}
}
}
return dest;
}
void NTree::handleAddMessage ( NTreeGroupAddMessage *  addMsg)
protected

Handles an information message that somebody joined a group we are a member of.

Parameters
addMsgthe information message

Definition at line 514 of file NTree.cc.

{
std::list<NTreeGroup>::iterator it = findGroup( addMsg->getOrigin() );
if( it == groups.end() ){
EV << "[NTree::handleAddMessage() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received add message for unknown group scope=" << addMsg->getOrigin() << "\n";
return;
}
EV << "[NTree::handleAddMessage() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received add message for group scope=" << addMsg->getOrigin() << "\n"
<< " Player=" << addMsg->getPlayer().getKey().toString(16) << "\n";
it->members.insert( addMsg->getPlayer() );
}
void NTree::handleAppMessage ( cMessage *  msg)
virtual

Processes "timer" self-messages.

Parameters
msgA self-message Processes non-commonAPI messages
msgnon-commonAPIMessage

Reimplemented from BaseOverlay.

Definition at line 238 of file NTree.cc.

{
if( GameAPIPositionMessage *posMsg = dynamic_cast<GameAPIPositionMessage*>(msg) ) {
if( state == READY ) {
handleMove( posMsg );
} else if ( state == JOIN ) {
// We are not connected to the overlay, inform app
CompReadyMessage* msg = new CompReadyMessage("Overlay not READY!");
msg->setReady(false);
msg->setComp(getThisCompType());
send( msg, "appOut");
} else if ( state == INIT ) {
// This is only called for the first MOVE message
TransportAddress bootstrapNode = bootstrapList->getBootstrapNode();
if( bootstrapNode.isUnspecified() ){
NTreeGroup grp(Vector2D(areaDimension/2,areaDimension/2), areaDimension);
grp.leader = thisNode;
grp.members.insert(thisNode);
groups.push_front(grp);
NTreeScope initialScope(Vector2D(areaDimension/2,areaDimension/2), areaDimension);
NTreeNode root(initialScope);
root.group = &groups.front();
ntreeNodes.insert(make_pair(initialScope,root));
changeState( READY );
} else {
// Trigger login
changeState( JOIN );
position = posMsg->getPosition();
NTreeJoinCall* joinMsg = new NTreeJoinCall("Login");
joinMsg->setPosition( position );
joinMsg->setBitLength( NTREEJOINCALL_L(joinMsg) );
sendUdpRpcCall( bootstrapNode, joinMsg );
}
setBootstrapedIcon();
}
delete msg;
}
}
void NTree::handleCollapseMessage ( NTreeCollapseMessage *  collapseMsg)
protected

Handles an information message that a subtree we are part of is collapsed.

Parameters
collapseMsgthe information message

Definition at line 579 of file NTree.cc.

{
EV << "[NTree::handleCollapseMessage() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Got collapse message for group " << collapseMsg->getOrigin() << "\n";
std::map<NTreeScope,NTreeNode>::iterator it = findNTreeNode( collapseMsg->getOrigin(), collapseMsg->getSize() );
if( it != ntreeNodes.end() ){
if( it->second.group ){
EV << " Informing group\n";
// leaf, inform group
NTreeGroupDeleteMessage* delMsg = new NTreeGroupDeleteMessage("Delete Group due to collapse");
delMsg->setOrigin( collapseMsg->getOrigin() );
delMsg->setSize( collapseMsg->getSize() );
for( unsigned int i = 0; i < 4; ++i ){
delMsg->setNewChild( i, collapseMsg->getPlayer() );
}
delMsg->setBitLength( NTREEDELETE_L(delMsg) );
RECORD_STATS(
treeMaintenanceMessages += it->second.group->members.size();
treeMaintenanceBytes += it->second.group->members.size()*delMsg->getByteLength();
);
sendToGroup( *it->second.group, delMsg );
// delete group
if( currentGroup && *currentGroup == *it->second.group ){
currentGroup = NULL;
}
groups.remove( *it->second.group );
} else {
// node, inform children
EV << " Informing children\n";
for( unsigned int i = 0; i < 4; ++i ){
EV << " ==> " << it->second.children[i] << "\n";
collapseMsg->setOrigin( it->second.scope.getSubScope(i).origin );
collapseMsg->setSize( it->second.scope.getSubScope(i).size );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += collapseMsg->getByteLength();
);
sendMessage( it->second.children[i], collapseMsg->dup() );
}
}
// delete node
ntreeNodes.erase( it );
}
}
void NTree::handleDeleteMessage ( NTreeGroupDeleteMessage *  deleteMsg)
protected

Handles an information message that a group we are a member of is going to be deleted.

Parameters
deleteMsgthe information message

Definition at line 530 of file NTree.cc.

{
std::list<NTreeGroup>::iterator it = findGroup( deleteMsg->getOrigin(), deleteMsg->getSize() );
// Group already deleted
if( it == groups.end() ) return;
// Check if I believe to own the group
// In that case, delete the corresponding node
ntreeNodes.erase( it->scope );
// Join new sub-group
if( it->isInScope(position) ){
NTreeJoinCall* joinCall = new NTreeJoinCall("JOIN GROUP");
joinCall->setPosition(position);
joinCall->setBitLength( NTREEJOINCALL_L(joinCall) );
RECORD_STATS(
joinsSend++;
joinBytes += joinCall->getByteLength();
);
sendMessage( deleteMsg->getNewChild( it->scope.origin.getQuadrant( position )), joinCall);
}
// delete group
if( currentGroup == &(*it) ) currentGroup = NULL;
groups.erase( it );
}
void NTree::handleDivideCall ( NTreeDivideCall *  divideCall)
protected

Handles a request to divide a group.

Parameters
divideCallthe request

Definition at line 806 of file NTree.cc.

{
EV << "[NTree::handleDivide() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n";
std::list<NTreeGroup>::iterator it = findGroup( divideCall->getOrigin(), divideCall->getSize() );
if( it == groups.end() ){
EV << " Received divide message for unknown group scope=" << divideCall->getOrigin() << "\n";
} else {
EV << " Divide group " << it->scope << "\n";
}
// Calculate new scope
NTreeScope oldScope(divideCall->getOrigin(), divideCall->getSize() );
NTreeScope newScope = oldScope.getSubScope( divideCall->getQuadrant() );
// If we own the node that is beeing divided, something went wrong
// However, ther is nothing we can do about it except removing the offending node
// Sombody obviously took over without us noticing
ntreeNodes.erase( oldScope );
// Create new group, delete old group
NTreeGroup newGroup(newScope);
newGroup.leader = thisNode;
newGroup.members.insert(thisNode);
groups.push_front(newGroup);
if( it != groups.end() ){
if( currentGroup == &(*it) ){
currentGroup = &groups.front();
}
groups.erase( it );
}
// Create new ntreeNode
NTreeNode newNode(newScope);
newNode.parent = divideCall->getSrcNode();
newNode.group = &groups.front();
ntreeNodes.insert(make_pair(newScope,newNode));
// Acknowledge Divide
NTreeDivideResponse* divideResp = new NTreeDivideResponse("Divide ACK");
divideResp->setQuadrant( divideCall->getQuadrant() );
divideResp->setBitLength( NTREEDIVIDERESPONSE_L(divideResp) );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += divideResp->getByteLength();
);
sendRpcResponse( divideCall, divideResp );
}
void NTree::handleDivideCallTimeout ( NTreeDivideCall *  divideCall,
const TransportAddress &  oldNode,
NTreeGroupDivideContext *  context 
)
protected

Gets called if a divide call times out Re-send the request to a different node.

Parameters
divideCallthe original request
oldNodethe host the original request was send to
contexta context pointer to correlate answers to the group that is to be divided

Definition at line 868 of file NTree.cc.

{
std::set<NodeHandle> invalidNodes;
invalidNodes.insert( thisNode );
NodeHandle dest = getRandomNode( invalidNodes );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += divideCall->getByteLength();
);
NTreeGroupDivideContextPtr* contextPtr = new NTreeGroupDivideContextPtr;
contextPtr->ptr = context;
sendUdpRpcCall( dest, divideCall->dup(), contextPtr );
}
void NTree::handleDivideResponse ( NTreeDivideResponse *  divideResp,
NTreeGroupDivideContext *  context 
)
protected

Handles an acknowledgement that a group was divided as requested.

Parameters
divideRespthe acknowledgement
contexta context pointer to correlate answers to the group that is to be divided

Definition at line 855 of file NTree.cc.

{
context->newChild[ divideResp->getQuadrant() ] = divideResp->getSrcNode();
for( unsigned int i = 0; i < 4; ++i ){
if( context->newChild[i].isUnspecified() ){
// Some responses still missing
return;
}
}
divideNode( context );
delete context;
}
void NTree::handleJoinCall ( NTreeJoinCall *  joinCall)
protected

Handles request to join a group.

Parameters
joinCallthe request

Definition at line 281 of file NTree.cc.

{
// Check if we know the group
std::list<NTreeGroup>::iterator grpIt = findGroup( joinCall->getPosition() );
if( grpIt != groups.end() ) {
// If we are leader, acknowlede Join
if( grpIt->leader == thisNode ) {
// Inform group about new member
NTreeGroupAddMessage* grpAdd = new NTreeGroupAddMessage("New group member");
grpAdd->setPlayer( joinCall->getSrcNode() );
grpAdd->setOrigin( grpIt->scope.origin );
grpAdd->setBitLength( NTREEADD_L(grpAdd) );
RECORD_STATS(
treeMaintenanceMessages += grpIt->members.size();
treeMaintenanceBytes += grpIt->members.size()*grpAdd->getByteLength();
);
sendToGroup( *grpIt, grpAdd );
grpIt->members.insert( joinCall->getSrcNode() );
// Acknowledge Join, send information about group
NTreeJoinResponse* joinResp = new NTreeJoinResponse("Join ACK");
joinResp->setOrigin( grpIt->scope.origin );
joinResp->setSize( grpIt->scope.size );
joinResp->setMembersArraySize( grpIt->members.size() );
unsigned int i = 0;
for( std::set<NodeHandle>::iterator it = grpIt->members.begin(); it != grpIt->members.end(); ++it ) {
joinResp->setMembers( i, *it );
++i;
}
joinResp->setBitLength( NTREEJOINRESPONSE_L(joinResp) );
sendRpcResponse( joinCall, joinResp );
// If group is to big, divide group
if( grpIt->members.size() > maxChildren && !grpIt->dividePending && grpIt->scope.size > 2*AOIWidth ){
EV << "[NTree::handleJoinCall() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Group got too big. Trying to divide group\n";
grpIt->dividePending = true;
std::map<NTreeScope,NTreeNode>::iterator nit = ntreeNodes.find( grpIt->scope );
if( nit == ntreeNodes.end() ){
EV << " Host is leader of a group, but not NTreeNode of that group.\n"
<< " This should not happen. Dropping group\n";
if( currentGroup == &(*grpIt) ){
currentGroup = NULL;
}
groups.erase( grpIt );
return;
}
EV << " Sending divide calls\n";
NTreeDivideCall* divideCall = new NTreeDivideCall("Divide Group");
divideCall->setOrigin( nit->second.scope.origin );
divideCall->setSize( nit->second.scope.size );
divideCall->setBitLength( NTREEDIVIDECALL_L(divideCall) );
NTreeGroupDivideContext* divideContext = new NTreeGroupDivideContext;
divideContext->nodeScope = nit->second.scope;
// select 4 random members of the group to become leader of subgroup
// "lotto" algoritm so nobody gets elected twice
unsigned int numMembers = grpIt->members.size();
unsigned int numbers[numMembers];
for( i = 0; i < numMembers; ++i ) numbers[i] = i;
unsigned int upperbound = numMembers;
for (i = 0; i < 4; ++i)
{
upperbound--;
unsigned int index = intuniform(0, upperbound);
std::set<NodeHandle>::iterator newChild = grpIt->members.begin();
std::advance( newChild, numbers[index] );
if( *newChild == thisNode ) { // don't select myself
--i;
} else {
NTreeDivideCall* msg = divideCall->dup();
msg->setQuadrant( i );
EV << " ==> " << (TransportAddress) *newChild << "\n";
NTreeGroupDivideContextPtr* contextPtr = new NTreeGroupDivideContextPtr;
contextPtr->ptr = divideContext;
sendUdpRpcCall( *newChild, msg, contextPtr);
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += msg->getByteLength();
);
}
swap(numbers[index], numbers[upperbound]);
}
delete divideCall;
}
} else {
// forward join to leader
sendMessageToUDP( grpIt->leader, joinCall );
}
return;
}
// We don't know the group, forward join via the NTree
routeViaNTree( joinCall->getPosition(), joinCall, true );
}
void NTree::handleJoinCallTimeout ( NTreeJoinCall *  joinCall,
const TransportAddress &  oldNode 
)
protected

Gets called if a join call times out Well try to re-join if needed.

Parameters
joinCallthe original call
oldNodethe host the original call was send to

Definition at line 436 of file NTree.cc.

{
if( state != READY ){
EV << " Overlay not ready. Trying to re-join overlay\n";
changeState( INIT );
}
joinTimeout++;
// TODO: Other cases when re-try is useful?
}
void NTree::handleJoinResponse ( NTreeJoinResponse *  joinResp)
protected

Handles the acknowledgement to join a group.

Parameters
joinRespthe acknowledgement (also holds information about the group)

Definition at line 382 of file NTree.cc.

{
EV << "[NTree::handleJoinResponse() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " JOIN ACK for group " << joinResp->getOrigin()
<< "-" << joinResp->getSize() << "\n";
std::list<NTreeGroup>::iterator git = findGroup( joinResp->getOrigin(), joinResp->getSize() );
// Check for conflicting groups
NTreeScope groupScope( joinResp->getOrigin(), joinResp->getSize() );
for( std::list<NTreeGroup>::iterator it = groups.begin(); it != groups.end(); ++it ){
if( it != git && (it->isInScope( groupScope.origin ) || groupScope.contains( it->scope.origin ) )){
// Oops, conflicting group found. joinResp is probably outdated
EV << " Conflicting group found. Ignoring JOIN ACK\n";
// if our login resulted in a divide, and we got the divide earlier that the ack,
// we missed to update our state. fixing.
if( state != READY ){
changeState( READY );
}
return;
}
}
// if group already known, clear member list (new member list will be taken from message)
if( git != groups.end() ){
if( git->leader != thisNode ) {
EV << " Group already known. Refreshing member list\n";
git->members.clear();
} else {
// We are leader of the already known group. Something's fishy, ignore join
EV << " Group already known; and I'm leader of that group. Ignoring ACK\n";
return;
}
} else {
// Else create new group
NTreeGroup grp(joinResp->getOrigin(), joinResp->getSize());
groups.push_front(grp);
git = groups.begin();
}
// Fill in member list and leader of the group from message
git->leader = joinResp->getSrcNode();
for( unsigned int i = 0; i < joinResp->getMembersArraySize(); ++i ){
git->members.insert( joinResp->getMembers(i) );
}
// If we were still joining the overlay, we are now ready to go
if( state != READY ){
changeState( READY );
}
}
void NTree::handleLeaveMessage ( NTreeLeaveMessage *  leaveMsg)
protected

Handles an information message that somebody left a group we are a member of.

Parameters
leaveMsgthe information message

Definition at line 557 of file NTree.cc.

{
std::list<NTreeGroup>::iterator it = findGroup( leaveMsg->getPosition() );
if( it != groups.end() ){
it->members.erase( leaveMsg->getPlayer() );
}
// If player not otherwise known
for( it = groups.begin(); it != groups.end(); ++it ){
if( it->members.find( leaveMsg->getPlayer() ) != it->members.end() ){
return;
}
}
// Inform app
GameAPIListMessage* gameMsg = new GameAPIListMessage("NEIGHBOR_DELETE");
gameMsg->setCommand(NEIGHBOR_UPDATE);
gameMsg->setRemoveNeighborArraySize(1);
gameMsg->setRemoveNeighbor(0, leaveMsg->getPlayer() );
send(gameMsg, "appOut");
}
void NTree::handleMove ( GameAPIPositionMessage *  posMsg)
protected

Handles a move message from the application.

Parameters
posMsgthe move message

Definition at line 446 of file NTree.cc.

{
position = posMsg->getPosition();
NTreeMoveMessage* moveMsg = new NTreeMoveMessage("MOVE");
moveMsg->setPlayer( thisNode );
moveMsg->setPosition( position );
moveMsg->setBitLength( NTREEMOVE_L(moveMsg) );
// Send to old group
if( currentGroup ){
sendToGroup( *currentGroup, moveMsg, true);
RECORD_STATS(
movesSend += currentGroup->members.size();
moveBytes += moveMsg->getByteLength() * currentGroup->members.size();
globalStatistics->addStdDev( "NTree: Area size", currentGroup->scope.size );
);
}
// Find group for new position
if( !currentGroup || !currentGroup->isInScope( position ) ){
std::list<NTreeGroup>::iterator it = findGroup( position );
if( it != groups.end() ) {
sendToGroup( *it, moveMsg, true );
currentGroup = &(*it);
RECORD_STATS(
movesSend += currentGroup->members.size();
moveBytes += moveMsg->getByteLength() * currentGroup->members.size();
);
} else {
EV << "[NTree::handleMove() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< "WARNING: no group for new position. Some updates may get lost!\n";
joinGroup( position );
}
}
delete moveMsg;
if( currentGroup ){
// Join new groups in our AoI and leave groups outside the AoI
NTreeScope& scope = currentGroup->scope;
NTreeScope area(Vector2D(areaDimension/2.0,areaDimension/2.0),areaDimension);
Vector2D aoiRight(AOIWidth/2.0, 0);
Vector2D aoiTop(0, AOIWidth/2.0);
Vector2D groupRight(scope.size/2.0 +1, 0);
Vector2D groupTop(0, scope.size/2.0 +1);
if(area.contains( position + aoiRight )) joinGroup(position + aoiRight);
if(area.contains( position - aoiRight )) joinGroup(position - aoiRight);
if(area.contains( position + aoiTop )) joinGroup(position + aoiTop);
if(area.contains( position - aoiTop )) joinGroup(position - aoiTop);
if(area.contains( position + (aoiRight + aoiTop)/sqrt(2))) joinGroup(position + (aoiRight + aoiTop)/sqrt(2));
if(area.contains( position + (aoiRight - aoiTop)/sqrt(2))) joinGroup(position + (aoiRight - aoiTop)/sqrt(2));
if(area.contains( position - (aoiRight + aoiTop)/sqrt(2))) joinGroup(position - (aoiRight + aoiTop)/sqrt(2));
if(area.contains( position - (aoiRight - aoiTop)/sqrt(2))) joinGroup(position - (aoiRight - aoiTop)/sqrt(2));
if( scope.contains( position + aoiRight )) leaveGroup( scope.origin + groupRight );
if( scope.contains( position - aoiRight )) leaveGroup( scope.origin - groupRight );
if( scope.contains( position + aoiTop )) leaveGroup( scope.origin + groupTop );
if( scope.contains( position - aoiTop )) leaveGroup( scope.origin - groupTop );
if( scope.contains( position + (aoiRight + aoiTop)/sqrt(2))) leaveGroup( scope.origin + groupRight + groupTop);
if( scope.contains( position + (aoiRight - aoiTop)/sqrt(2))) leaveGroup( scope.origin + groupRight - groupTop);
if( scope.contains( position - (aoiRight + aoiTop)/sqrt(2))) leaveGroup( scope.origin - groupRight + groupTop);
if( scope.contains( position - (aoiRight - aoiTop)/sqrt(2))) leaveGroup( scope.origin - groupRight - groupTop);
}
}
void NTree::handleMoveMessage ( NTreeMoveMessage *  moveMsg)
protected

Handles a move message from the network.

Parameters
moveMsgthe move message

Definition at line 627 of file NTree.cc.

{
// Inform app
GameAPIListMessage* gameMsg = new GameAPIListMessage("NEIGHBOR_UPDATE");
gameMsg->setCommand(NEIGHBOR_UPDATE);
gameMsg->setAddNeighborArraySize(1);
gameMsg->setNeighborPositionArraySize(1);
gameMsg->setAddNeighbor(0, moveMsg->getPlayer() );
gameMsg->setNeighborPosition(0, moveMsg->getPosition() );
send(gameMsg, "appOut");
RECORD_STATS(
globalStatistics->addStdDev(
"NTree: MoveDelay",
SIMTIME_DBL(simTime()) - SIMTIME_DBL(moveMsg->getCreationTime())
);
);
}
void NTree::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 980 of file NTree.cc.

{
for(std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.begin(); it != ntreeNodes.end(); ++it ){
// Replace me on all nodes
NTreeReplaceNodeMessage* replaceMsg = new NTreeReplaceNodeMessage("Replace me");
replaceMsg->setOrigin( it->second.scope.origin );
replaceMsg->setSize( it->second.scope.size );
replaceMsg->setParent( it->second.parent );
if( it->second.group ){
replaceMsg->setIsLeaf( true );
replaceMsg->setChildrenArraySize( it->second.group->members.size() );
unsigned int i = 0;
for( std::set<NodeHandle>::iterator mit = it->second.group->members.begin(); mit != it->second.group->members.end(); ++mit ){
replaceMsg->setChildren(i, *mit );
++i;
}
} else {
replaceMsg->setIsLeaf( false );
replaceMsg->setChildrenArraySize( 4 );
for( unsigned int i = 0; i < 4; ++i ){
replaceMsg->setChildren(i, it->second.children[i] );
}
}
replaceMsg->setBitLength( NTREEREPLACE_L(replaceMsg) );
// Search random node to replace me
std::set<NodeHandle> invalidNodes;
invalidNodes.insert( thisNode );
if( !it->second.parent.isUnspecified() ){
invalidNodes.insert( it->second.parent );
}
if( !it->second.group ) {
for( unsigned int i = 0; i < 4; ++i ){
invalidNodes.insert( it->second.children[i] );
}
}
const NodeHandle& dest = getRandomNode( invalidNodes );
// Inform node of his new responsabilities
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += replaceMsg->getByteLength();
);
sendMessage( dest, replaceMsg );
}
while( groups.size() ){
// Leave all groups
leaveGroup( groups.begin()->scope.origin, true );
}
// clear ntree
ntreeNodes.clear();
currentGroup = NULL;
changeState( SHUTDOWN );
}
void NTree::handlePingCall ( NTreePingCall *  pingCall)
protected

Handles a ping If the ping was send to a node in the n-tree, it is answered with information about the satte of that n-tree node (children, aggregated size)

Parameters
pingCallthe ping request

Definition at line 647 of file NTree.cc.

{
if( NTreeNodePingCall* nodePing = dynamic_cast<NTreeNodePingCall*>(pingCall) ){
// node Ping
// compute my scope
NTreeScope origScope( pingCall->getOrigin(), pingCall->getSize() );
NTreeScope myScope;
myScope = origScope.getSubScope( nodePing->getQuadrant() );
std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.find( myScope );
if( it != ntreeNodes.end() ){
// TODO: save parentParent?
if( nodePing->getParent().isUnspecified() ) it->second.parentIsRoot = true;
for( unsigned int i = 0; i < 4; ++i ){
it->second.siblings[i] = nodePing->getSiblings(i);
}
it->second.lastPing = simTime();
// Answer ping
NTreeNodePingResponse* nodeResp = new NTreeNodePingResponse("PONG");
if( it->second.group ){
// leaf
nodeResp->setAggChildCount( it->second.group->members.size() );
nodeResp->setMembersArraySize( it->second.group->members.size() );
unsigned int i = 0;
for( std::set<NodeHandle>::iterator childIt = it->second.group->members.begin();
childIt != it->second.group->members.end(); ++childIt ){
nodeResp->setMembers( i++, *childIt );
}
} else {
// ordinary node
unsigned int aggChildCount = 0;
nodeResp->setMembersArraySize( 4 );
for( unsigned int i = 0; i < 4; ++i ){
aggChildCount += it->second.aggChildCount[i];
nodeResp->setMembers( i, it->second.children[i] );
}
nodeResp->setAggChildCount( aggChildCount );
}
nodeResp->setBitLength( NTREENODEPINGRESPONSE_L(nodeResp) );
sendRpcResponse( nodePing, nodeResp );
} else {
delete pingCall;
}
} else {
// Group ping
std::list<NTreeGroup>::iterator it = findGroup( pingCall->getOrigin(), pingCall->getSize() );
if( it != groups.end() ){
// TODO: save parentParent
}
// Answer ping
NTreePingResponse* pingResp = new NTreePingResponse("PONG");
pingResp->setBitLength( NTREEPINGRESPONSE_L(pingResp) );
sendRpcResponse( pingCall, pingResp );
}
}
void NTree::handlePingCallTimeout ( NTreePingCall *  pingCall,
const TransportAddress &  oldNode,
NTreePingContext *  context 
)
protected

Handles a ping timeout Inform others about the failed node, replace it if needed.

Parameters
pingCallthe original ping call
oldNodethe (failed) host the ping was send to
contexta context which allows to correlate the response to a gertain node in the n-tree

Definition at line 743 of file NTree.cc.

{
if( context ){
std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.find( context->nodeScope );
if( it != ntreeNodes.end() && !it->second.group){
// If child found, replace it
if( oldNode == it->second.children[context->quadrant ]){
NTreeReplaceNodeMessage* replaceMsg = new NTreeReplaceNodeMessage("Replace failed node");
replaceMsg->setOrigin( context->nodeScope.getSubScope(context->quadrant).origin );
replaceMsg->setSize( context->nodeScope.getSubScope(context->quadrant).size );
replaceMsg->setParent( thisNode );
replaceMsg->setOldNode( oldNode );
replaceMsg->setIsLeaf( it->second.childChildren[context->quadrant].size() != 4 ||
(it->second.childChildren[context->quadrant].size() == it->second.aggChildCount[context->quadrant]) );
replaceMsg->setChildrenArraySize( it->second.childChildren[context->quadrant].size() );
unsigned int i = 0;
for( std::set<NodeHandle>::iterator cit = it->second.childChildren[context->quadrant].begin();
cit != it->second.childChildren[context->quadrant].end(); ++cit ){
replaceMsg->setChildren( i, *cit );
++i;
}
replaceMsg->setBitLength( NTREEREPLACE_L(replaceMsg) );
// Find node to replace failed node
std::set<NodeHandle> invalidNodes;
invalidNodes.insert( thisNode );
if( !it->second.parent.isUnspecified() ){
invalidNodes.insert( it->second.parent );
}
if( !replaceMsg->getIsLeaf() ) {
for( unsigned int i = 0; i < 4; ++i ){
invalidNodes.insert( replaceMsg->getChildren(i) );
}
}
const NodeHandle& dest = getRandomNode( invalidNodes );
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += replaceMsg->getByteLength();
);
sendMessage(dest, replaceMsg );
}
}
delete context;
} else {
// Group ping. Simple delete node from all groups
for( std::list<NTreeGroup>::iterator it = groups.begin(); it != groups.end(); ++it ){
// we have to search the group members manually, as we only have a TransportAddress to compare
for( std::set<NodeHandle>::iterator mit = it->members.begin(); mit != it->members.end(); ++mit ){
if( oldNode == *mit ){
NTreeLeaveMessage* leaveMsg = new NTreeLeaveMessage("Failed member");
leaveMsg->setPlayer( *mit );
leaveMsg->setPosition( it->scope.origin );
leaveMsg->setBitLength( NTREELEAVE_L(leaveMsg) );
sendToGroup( *it, leaveMsg );
it->members.erase( mit );
break;
}
}
}
}
}
void NTree::handlePingResponse ( NTreePingResponse *  pingResp,
NTreePingContext *  context 
)
protected

Handles a ping response.

Parameters
pingRespthe ping response
contexta context which allows to correlate the response to a gertain node in the n-tree

Definition at line 708 of file NTree.cc.

{
if( NTreeNodePingResponse* nodePing = dynamic_cast<NTreeNodePingResponse*>(pingResp) ){
std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.find( context->nodeScope );
if( it != ntreeNodes.end() && !it->second.group){
// If child found, update children info in node
if( it->second.children[context->quadrant] == nodePing->getSrcNode() ){
it->second.aggChildCount[context->quadrant] = nodePing->getAggChildCount();
it->second.childChildren[context->quadrant].clear();
for( unsigned int ii = 0; ii < nodePing->getMembersArraySize(); ++ii ){
it->second.childChildren[context->quadrant].insert( nodePing->getMembers( ii ) );
}
// Collapse tree if aggChildCount is too low
unsigned int aggChildCount = 0;
for( unsigned int i = 0; i < 4; ++i ){
if( !it->second.aggChildCount[i] ) {
aggChildCount = maxChildren;
break;
}
aggChildCount += it->second.aggChildCount[i];
}
if( aggChildCount*2 < maxChildren ){
collapseTree( it );
}
} else {
// child not found
// TODO: what to do now?
}
}
}
delete context;
}
void NTree::handleReplaceMessage ( NTreeReplaceNodeMessage *  replaceMsg)
protected

Handles a request to replace a failed or leaving node.

Parameters
replaceMsgthe replacement request

Definition at line 882 of file NTree.cc.

{
EV << "[NTree::handleReplaceMessage() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Was asked to replace " << replaceMsg->getOldNode() << " for group " << replaceMsg->getOrigin() << "\n";
// Create new ntreeNode
NTreeScope newScope( replaceMsg->getOrigin(), replaceMsg->getSize() );
NTreeNode newNode(newScope);
newNode.parent = replaceMsg->getParent();
if( replaceMsg->getIsLeaf() ){
std::list<NTreeGroup>::iterator it = findGroup( replaceMsg->getOrigin(), replaceMsg->getSize() );
if( it == groups.end() ){
NTreeGroup newGrp( newScope );
// TODO: check for conflicting groups?
groups.push_front( newGrp );
it = groups.begin();
}
it->leader = thisNode;
it->members.insert( thisNode );
for( unsigned int i = 0; i < replaceMsg->getChildrenArraySize(); ++i ){
it->members.insert( replaceMsg->getChildren(i) );
}
newNode.group = &(*it);
} else {
for( unsigned int i = 0; i < 4; ++i ){
newNode.children[i] = replaceMsg->getChildren(i);
}
}
ntreeNodes.insert(make_pair(newScope,newNode));
// Inform parent+children
NTreeTakeOverMessage* takeMsg = new NTreeTakeOverMessage("I took over");
takeMsg->setPlayer( thisNode );
takeMsg->setOrigin( newScope.origin );
takeMsg->setSize( newScope.size );
takeMsg->setBitLength( NTREETAKEOVER_L(takeMsg) );
sendMessage( newNode.parent, takeMsg->dup() );
sendMessage( replaceMsg->getOldNode(), takeMsg->dup() ); // also inform old node if is is (against expectations) still alive
RECORD_STATS(
treeMaintenanceMessages+=2;
treeMaintenanceBytes += 2*takeMsg->getByteLength();
);
if( newNode.group ){
RECORD_STATS(
treeMaintenanceMessages += newNode.group->members.size();
treeMaintenanceBytes += newNode.group->members.size()*takeMsg->getByteLength();
);
sendToGroup( *newNode.group, takeMsg );
} else {
for( unsigned int i = 0; i < 4; ++i ){
RECORD_STATS(
treeMaintenanceMessages++;
treeMaintenanceBytes += takeMsg->getByteLength();
);
sendMessage( newNode.children[i], takeMsg->dup() );
}
delete takeMsg;
}
}
bool NTree::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 86 of file NTree.cc.

{
if( state == SHUTDOWN ){
return false;
}
// delegate messages
RPC_SWITCH_START( msg )
RPC_DELEGATE( NTreeJoin, handleJoinCall );
RPC_DELEGATE( NTreePing, handlePingCall );
RPC_DELEGATE( NTreeDivide, handleDivideCall );
RPC_SWITCH_END( )
return RPC_HANDLED;
}
void NTree::handleRpcResponse ( BaseResponseMessage *  msg,
cPolymorphic *  context,
int  rpcId,
simtime_t  rtt 
)
virtual

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 102 of file NTree.cc.

{
if( state == SHUTDOWN ){
return;
}
RPC_SWITCH_START(msg);
RPC_ON_RESPONSE( NTreeJoin ) {
EV << "[NTree::handleRpcResponse() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received a NTreeJoin RPC Response: id=" << rpcId << "\n"
<< " msg=" << *_NTreeJoinResponse << " rtt=" << rtt
<< endl;
handleJoinResponse( _NTreeJoinResponse );
break;
}
RPC_ON_RESPONSE( NTreePing ) {
EV << "[NTree::handleRpcResponse() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received a NTreePing RPC Response: id=" << rpcId << "\n"
<< " msg=" << *_NTreePingResponse << " rtt=" << rtt
<< endl;
handlePingResponse( _NTreePingResponse, dynamic_cast<NTreePingContext*>(context) );
break;
}
RPC_ON_RESPONSE( NTreeDivide ) {
EV << "[NTree::handleRpcResponse() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Received a NTreeDivide RPC Response: id=" << rpcId << "\n"
<< " msg=" << *_NTreeDivideResponse << " rtt=" << rtt
<< endl;
handleDivideResponse( _NTreeDivideResponse, check_and_cast<NTreeGroupDivideContextPtr*>(context)->ptr );
delete context;
break;
}
RPC_SWITCH_END( );
}
void NTree::handleRpcTimeout ( BaseCallMessage *  msg,
const TransportAddress &  dest,
cPolymorphic *  context,
int  rpcId,
const OverlayKey &  destKey 
)
virtual

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 141 of file NTree.cc.

{
if( state == SHUTDOWN ){
return;
}
RPC_SWITCH_START(msg)
RPC_ON_CALL( NTreePing ) {
EV << "[NTree::handleRpcTimeout() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Ping RPC Call timed out: id=" << rpcId << "\n"
<< " msg=" << *_NTreePingCall
<< " oldNode=" << dest
<< endl;
handlePingCallTimeout( _NTreePingCall, dest, dynamic_cast<NTreePingContext*>(context) );
break;
}
RPC_ON_CALL( NTreeJoin ) {
EV << "[NTree::handleRpcTimeout() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Join RPC Call timed out: id=" << rpcId << "\n"
<< " msg=" << *_NTreeJoinCall
<< " oldNode=" << dest
<< endl;
handleJoinCallTimeout( _NTreeJoinCall, dest );
break;
}
RPC_ON_CALL( NTreeDivide ) {
EV << "[NTree::handleRpcTimeout() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Ping RPC Call timed out: id=" << rpcId << "\n"
<< " msg=" << *_NTreeDivideCall
<< " oldNode=" << dest
<< endl;
handleDivideCallTimeout( _NTreeDivideCall, dest, check_and_cast<NTreeGroupDivideContextPtr*>(context)->ptr );
delete context;
break;
}
RPC_SWITCH_END( )
}
void NTree::handleTakeOverMessage ( NTreeTakeOverMessage *  takeMsg)
protected

Handles an information message that a node took over the responsibilities of a failed or leaving node.

Parameters
takeMsgthe information message

Definition at line 946 of file NTree.cc.

{
// CHeck if group leader gets replaced
std::list<NTreeGroup>::iterator git = findGroup( takeMsg->getOrigin(), takeMsg->getSize() );
if( git != groups.end() ){
git->leader = takeMsg->getPlayer();
}
// Check if a node gets replaced
NTreeScope takeScope( takeMsg->getOrigin(), takeMsg->getSize() );
for(std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.begin(); it != ntreeNodes.end(); ++it ){
// Check if parent is replaced
if( takeMsg->getSize() == it->second.scope.size*2.0 ){
for( unsigned int i = 0; i < 4; ++i ){
if( takeScope.getSubScope(i) == it->first ){
it->second.parent = takeMsg->getPlayer();
}
}
// Else check if child is replaced
} else if( takeMsg->getSize()*2.0 == it->second.scope.size && !it->second.group ){
for( unsigned int i = 0; i < 4; ++i ){
if( it->first.getSubScope(i) == takeScope ){
it->second.children[i] = takeMsg->getPlayer();
}
}
} else if( it->second.scope == takeScope && takeMsg->getPlayer() != thisNode ){
// Uh-oh. Somebody replaced me. Yield ownership
ntreeNodes.erase( it );
return;
}
}
}
void NTree::handleTimerEvent ( cMessage *  msg)
virtual

Reimplemented from BaseRpc.

Definition at line 215 of file NTree.cc.

{
if( state == SHUTDOWN ){
return;
}
if( msg == joinTimer ) {
// send a fake ready message to app to get initial position
CompReadyMessage* msg = new CompReadyMessage("fake READY");
msg->setReady(true);
msg->setComp(getThisCompType());
send( msg, "appOut");
// send initial AOI size to the application
GameAPIResizeAOIMessage* gameMsg = new GameAPIResizeAOIMessage("RESIZE_AOI");
gameMsg->setCommand(RESIZE_AOI);
gameMsg->setAOIsize(AOIWidth);
send( gameMsg, "appOut");
} else if( msg == pingTimer ){
pingNodes();
checkParentTimeout();
scheduleAt( simTime() + pingInterval, pingTimer );
}
}
void NTree::handleUDPMessage ( BaseOverlayMessage *  msg)
virtual

Processes messages from underlay.

Parameters
msgMessage from UDP

Reimplemented from BaseOverlay.

Definition at line 185 of file NTree.cc.

{
if( state == SHUTDOWN ){
delete msg;
return;
}
if( NTreeMoveMessage* moveMsg = dynamic_cast<NTreeMoveMessage*>(msg) ){
handleMoveMessage( moveMsg );
delete moveMsg;
} else if( NTreeGroupAddMessage* addMsg = dynamic_cast<NTreeGroupAddMessage*>(msg) ){
handleAddMessage( addMsg );
delete addMsg;
} else if( NTreeGroupDeleteMessage* deleteMsg = dynamic_cast<NTreeGroupDeleteMessage*>(msg) ){
handleDeleteMessage( deleteMsg );
delete deleteMsg;
} else if( NTreeLeaveMessage* leaveMsg = dynamic_cast<NTreeLeaveMessage*>(msg) ){
handleLeaveMessage( leaveMsg );
delete leaveMsg;
} else if( NTreeCollapseMessage* collapseMsg = dynamic_cast<NTreeCollapseMessage*>(msg) ){
handleCollapseMessage( collapseMsg );
delete collapseMsg;
} else if( NTreeReplaceNodeMessage* replaceMsg = dynamic_cast<NTreeReplaceNodeMessage*>(msg) ){
handleReplaceMessage( replaceMsg );
delete replaceMsg;
} else if( NTreeTakeOverMessage* takeMsg = dynamic_cast<NTreeTakeOverMessage*>(msg) ){
handleTakeOverMessage( takeMsg );
delete takeMsg;
}
}
void NTree::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 BaseOverlay.

Definition at line 43 of file NTree.cc.

{
// because of IPAddressResolver, we need to wait until interfaces are registered,
// address auto-assignment takes place etc.
if(stage != MIN_STAGE_OVERLAY) return;
maxChildren = par("maxChildren");
if( maxChildren < 5 ){
throw new cRuntimeError("To allow a proper quad-tree, maxChildren has to be 5 or bigger");
}
AOIWidth = par("AOIWidth");
thisNode.setKey(OverlayKey::random());
areaDimension = par("areaDimension");
currentGroup = NULL;
joinTimer = new cMessage("joinTimer");
pingTimer = new cMessage("pingTimer");
pingInterval = par("pingInterval");
scheduleAt( simTime() + pingInterval, pingTimer );
// FIXME: Use standard baseOverlay::join()
changeState( INIT );
// statistics
joinsSend = 0;
joinBytes = 0;
joinTimeout = 0;
divideCount = 0;
collapseCount = 0;
treeMaintenanceMessages = 0;
treeMaintenanceBytes = 0;
movesSend = 0;
moveBytes = 0;
WATCH_MAP( ntreeNodes );
WATCH_LIST( groups );
}
void NTree::joinGroup ( Vector2D  position)
protected

Joins the group that is responsible for a given position.

Parameters
positionthe position

Definition at line 1203 of file NTree.cc.

{
std::list<NTreeGroup>::iterator grpIt = findGroup( position );
if( grpIt == groups.end() ) {
NTreeJoinCall* joinCall = new NTreeJoinCall("JOIN GROUP");
joinCall->setPosition( position );
joinCall->setBitLength( NTREEJOINCALL_L(joinCall) );
RECORD_STATS(
joinsSend++;
joinBytes += joinCall->getByteLength();
);
routeViaNTree( position, joinCall );
}
}
void NTree::leaveGroup ( Vector2D  position,
bool  force = false 
)
protected

Leaves a group for a given position.

Parameters
positionthe position
forceif set to true, leave group even if I'm leader of that group

Definition at line 1218 of file NTree.cc.

{
std::list<NTreeGroup>::iterator grpIt = findGroup( position );
// Don't leave group if I'm leader of that group (except if forced)
if( grpIt != groups.end() && (grpIt->leader != thisNode || force) ) {
NTreeLeaveMessage* leaveMsg = new NTreeLeaveMessage("Leave Group");
leaveMsg->setPlayer( thisNode );
leaveMsg->setPosition( position );
leaveMsg->setBitLength( NTREELEAVE_L(leaveMsg) );
sendToGroup( *grpIt, leaveMsg );
if( currentGroup == &(*grpIt) ){
EV << "[NTree::leaveGroup() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " WARNING: Leaving group " << position << "\n"
<< " This group is marked as current group!\n";
currentGroup = NULL;
}
groups.erase( grpIt );
}
}
void NTree::pingNodes ( )
protected

Ping all children of all groups.

Definition at line 1036 of file NTree.cc.

{
for(std::map<NTreeScope,NTreeNode>::iterator it = ntreeNodes.begin(); it != ntreeNodes.end(); ++it ){
unsigned int i = 0;
if( it->second.group ){
// Leaf
NTreePingCall* pingCall = new NTreePingCall("PING");
pingCall->setOrigin( it->second.scope.origin );
pingCall->setSize( it->second.scope.size );
pingCall->setParent( it->second.parent );
pingCall->setBitLength( NTREEPINGCALL_L(pingCall) );
sendToGroup( *it->second.group, pingCall );
} else {
NTreeNodePingCall* pingCall = new NTreeNodePingCall("PING");
pingCall->setOrigin( it->second.scope.origin );
pingCall->setSize( it->second.scope.size );
pingCall->setParent( it->second.parent );
for( i = 0; i < 4; ++i ){
pingCall->setSiblings(i, it->second.children[i] );
}
pingCall->setBitLength( NTREENODEPINGCALL_L(pingCall) );
for( i = 0; i < 4; ++i ){
pingCall->setQuadrant( i );
sendUdpRpcCall( it->second.children[i], pingCall->dup(), new NTreePingContext(it->second.scope, i) );
}
delete pingCall;
}
}
}
void NTree::routeViaNTree ( const Vector2D &  pos,
cPacket *  msg,
bool  forward = false 
)
protected

Route a message through the N-Tree to the closest know node to the given position.

Parameters
posthe position
msgthe message
forwardShould be set to true if the message was not created by the local node

Definition at line 1240 of file NTree.cc.

{
NodeHandle dest;
if( ntreeNodes.size() ) {
// Check if pos is in scope of one ntree node
std::map<NTreeScope,NTreeNode>::iterator it = findNTreeNode( pos );
if( it != ntreeNodes.end() ){
// Forward message to appropriate child
dest = it->second.getChildForPos( pos );
} else {
// else send to parent of highest ntreeNode
dest = ntreeNodes.begin()->second.parent;
}
} else {
// No Ntree known. Send to group leader
if( currentGroup ){
dest = currentGroup->leader;
} else if( groups.size() ){
dest = groups.begin()->leader;
} else { // No group known. We have to re-join. (Even though a JOIN might still be in progress)
EV << "[NTree::routeViaNTree() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " No ntree node and no group known. Dropping message & re-join!\n";
changeState( INIT );
delete msg;
return;
}
}
if( forward && dest == thisNode ) {
EV << "[NTree::routeViaNTree() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Trying to route message " << msg << " to myself\n"
<< " This will result in a loop. Dropping message\n";
delete msg;
} else {
sendMessage( dest, msg, forward );
}
}
void NTree::sendMessage ( const TransportAddress &  dest,
cPacket *  msg,
bool  forward = false 
)
protected

Sends a message to a host.

Silently discards the message if the destination is unspecified

Parameters
destthe destination address
msgthe message
forwardshould be set to true if the message was not created by the local node

Definition at line 1298 of file NTree.cc.

{
if( dest.isUnspecified() ) {
EV << "[NTree::sendMessage() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " WARNING: Trying to send message " << msg
<< " to unspecified destination. Dropping packet!\n";
delete msg;
return;
}
// TODO: statistics?
BaseCallMessage* rpc = dynamic_cast<BaseCallMessage*>(msg);
if( rpc && !forward ){
// Slightly evil: If an OverlayKey is set, the RPC response
// may get dropped if it was forwarded (because OverSim expects
// frowarding to be done with BaseRoutMessages. Which we can't do,
// because we are not routing to overlay keys but to positions.
// Thus, we cast the OverlayKey away.
sendUdpRpcCall( TransportAddress(dest), rpc );
} else {
sendMessageToUDP( dest, msg );
}
}
void NTree::sendToGroup ( const NTreeGroup &  grp,
cPacket *  msg,
bool  keepMsg = false 
)
protected

Sends a message to all members of a group.

Parameters
grpthe group
msgthe message
keepMsgdo not free the memory occupied by msg after sending

Definition at line 1280 of file NTree.cc.

{
EV << "[NTree::sendToGroup() @ " << thisNode.getIp()
<< " (" << thisNode.getKey().toString(16) << ")]\n"
<< " Send message " << msg << "\n"
<< " to group scope=" << grp.scope.origin << "\n";
NTree::sendToGroup( grp.members, msg, keepMsg );
}
void NTree::sendToGroup ( const std::set< NodeHandle > &  grp,
cPacket *  msg,
bool  keepMsg = false 
)
protected

Sends a message to all members of a group.

Parameters
grpthe group
msgthe message
keepMsgdo not free the memory occupied by msg after sending

Definition at line 1289 of file NTree.cc.

{
for( std::set<NodeHandle>::iterator it = grp.begin(); it != grp.end(); ++it ){
sendMessage( *it, msg->dup(), false );
}
if (!keepMsg) delete msg;
}
void NTree::setBootstrapedIcon ( )
protected

Definition at line 1354 of file NTree.cc.

{
if(ev.isGUI()) {
if(state == READY) {
getParentModule()->getParentModule()->getDisplayString().setTagArg("i2", 1, "green");
getDisplayString().setTagArg("i", 1, "green");
}
else if(state == JOIN) {
getParentModule()->getParentModule()->getDisplayString().setTagArg("i2", 1, "yellow");
getDisplayString().setTagArg("i", 1, "yellow");
}
else {
getParentModule()->getParentModule()->getDisplayString().setTagArg("i2", 1, "red");
getDisplayString().setTagArg("i", 1, "red");
}
}
}

Member Data Documentation

unsigned int NTree::AOIWidth
protected

Definition at line 266 of file NTree.h.

double NTree::areaDimension
protected

Definition at line 268 of file NTree.h.

unsigned int NTree::collapseCount
protected

Definition at line 321 of file NTree.h.

NTreeGroup* NTree::currentGroup
protected

Definition at line 270 of file NTree.h.

unsigned int NTree::divideCount
protected

Definition at line 320 of file NTree.h.

std::list<NTreeGroup> NTree::groups
protected

Definition at line 277 of file NTree.h.

unsigned int NTree::joinBytes
protected

Definition at line 317 of file NTree.h.

unsigned int NTree::joinsSend
protected

Definition at line 316 of file NTree.h.

unsigned int NTree::joinTimeout
protected

Definition at line 318 of file NTree.h.

cMessage* NTree::joinTimer
protected

Definition at line 274 of file NTree.h.

unsigned int NTree::maxChildren
protected

Definition at line 267 of file NTree.h.

unsigned int NTree::moveBytes
protected

Definition at line 327 of file NTree.h.

unsigned int NTree::movesSend
protected

Definition at line 326 of file NTree.h.

std::map<NTreeScope,NTreeNode> NTree::ntreeNodes
protected

Definition at line 278 of file NTree.h.

simtime_t NTree::pingInterval
protected

Definition at line 272 of file NTree.h.

cMessage* NTree::pingTimer
protected

Definition at line 275 of file NTree.h.

Vector2D NTree::position
protected

Definition at line 269 of file NTree.h.

unsigned int NTree::treeMaintenanceBytes
protected

Definition at line 324 of file NTree.h.

unsigned int NTree::treeMaintenanceMessages
protected

Definition at line 323 of file NTree.h.

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