planet.chord
Class ChordNode

java.lang.Object
  extended byplanet.generic.commonapi.NodeImpl
      extended byplanet.chord.ChordNode
All Implemented Interfaces:
Node, java.io.Serializable
Direct Known Subclasses:
BadChordNode

public class ChordNode
extends NodeImpl

A Chord node is single entity in the chord network. It extends of the class Node and specializes following the lookup Chord protocol. Moreover, the stabilization implementation, producing the periodic stabilition events.

Author:
Ruben Mondejar , Carles Pairot , Jordi Pujol , Marc Sanchez
See Also:
Serialized Form

Nested Class Summary
 class ChordNode.FindPredListener
           
 class ChordNode.FindSuccListener
           
 class ChordNode.FixFingerTask
          Simple TimerTask that invoke fix_fingers() Node method.
 class ChordNode.GetPreListener
           
 class ChordNode.LookupListener
           
 class ChordNode.StabilizeTask
          Simple TimerTask that invoke stabilize() Node method.
 
Field Summary
protected  java.util.Vector auxCAPI
          Temporal use in Common API methods.
static int BROADCAST
          Type value: The message with this type identifies a broadcast message.
static int DATA
          Type value: It identifies that this message contains an application level Message.
 Id deux
           
static int FIND_PRE
          Type value: Start a set of messages that permits to find the inmediate successor of any new incoming node to the network.
static int FIND_SUCC
          Type value: First message that is send by any node to get its inmediate successor.
 NodeHandle[] finger
           
protected  int finger_changes
          Detect the number of finger changes only on one simulation step.
static int GET_PRE
          Type value: Start a set of messages that permits to find the inmediate node in charge of any key.
protected  boolean hasFailed
           
protected  boolean hasLeaved
           
protected  Id MAX
           
static java.lang.String[] MODES
          This String contains a string representation of each mode value of the RouteMessage.
static int NOTIFY
          Type value: Informs to the node that receive this message its inmediate predecessor.
protected  int null_pointers
           
protected  NodeHandle predecessor
           
protected  int realStabilizationRate
          Number of simulation steps without changes on finger table, that represents a real stabilization of this node.
static int REFRESH
          Mode value: Defines a message's mode that requires only communication on one way.
static int REPLY
          Mode value: Defines the response of a communication.
static int REQUEST
          Mode value: Defines the start of communication that requires response (REPLY).
static int SET_PRE
          Type value: Informs to the node that receive this message its new inmediate predecessor.
static int SET_SUCC
          Type value: Informs to the node that receives this message its new inmediate successor.
protected  int stabRate
          Number of simulation steps without changes on finger table.
 Id[] start
           
 java.util.Vector succ_list
           
static int SUCC_LIST
          Type value: Start a set of messages that permits the harvesting of successors of the node that send originally this message.
protected  NodeHandle[] temp
           
static java.lang.String[] TYPES
          This String contains a string representation of each of types and modes values of the RouteMessage.
 
Fields inherited from class planet.generic.commonapi.NodeImpl
endpoints, id, listeners, nodeHandle, role
 
Constructor Summary
ChordNode(Id id)
          Constructor, create a new BadChordNode instance with this node Id
 
Method Summary
 void broadcast(java.lang.String appId, NodeHandle to, NodeHandle nextHop, Message msg)
          Initiating a Broadcast Message
protected  void clearFingerChanges()
          Clears the counter of the finger table changes
protected  NodeHandle closest_preceding_finger(Id id)
          Finds the closest preceding finger of a node
 void dispatcher(RouteMessage msg)
          Treats the messages and according to the case, executes the generic listeners or listeners specialized, forward the messages or send responses messages
 void fail()
          Sets alive flag to false.
protected  NodeHandle find_predecessor(int pos)
          Finds the predecessor of a node.
protected  NodeHandle find_predecessor(NodeHandle handle)
          Finds the predecessor of a node.
protected  NodeHandle find_successor(int pos)
          Finds the successor of a node.
protected  NodeHandle find_successor(NodeHandle handle)
          Finds the successor of a node.
 int firstLocalLookup(Id key)
          Detects de first position that key is in range of some position of finger table.
protected  void fix_fingers()
          This method allows to update a finger table position.
 java.util.Set getAllLinks()
          Gets all node connections to other nodes as its NodeHandles.
static RouteMessage getBroadcastMessage(java.lang.String appId, NodeHandle from, NodeHandle to, NodeHandle nextHop, Message msg)
          Return a RouteMessage with the specified values.
 NodeHandle getClosestNodeHandle(Id id)
          Returns the NodeHandle closest to id.
static RouteMessage getDataMessage(java.lang.String appId, NodeHandle from, NodeHandle to, NodeHandle nextHop, Message msg)
          Return a RouteMessage with the specified values.
 void getEInGML(java.util.Collection E, GMLConstraint constraint)
          This method is a callback method used to collect all of the edges of a graph according to GML file format for latter visual graph performance.
protected  int getFingerChanges()
          Returns the count of the finger table changes
 java.util.Hashtable getInfo()
          Returns information of the node
 NodeHandle getLocalHandle()
          Return the local NodeHandle.
 NodeHandle getPred()
          Returns the NodeHandle of the present identification of the precursor of the node
 NodeHandle getSucc()
          Returns the NodeHandle of the present identification of the successor of the node
 java.util.Vector getSuccList(int max)
          Returns the successor list of the present node
 boolean isAlive()
          Informs if this node is alive.
 void join(Id bootstrap)
          The node joins in the network
 void leave()
          The node leaves the network
 java.util.Vector localLookup(Id key, int max, boolean safe)
          Returns a list of nodes that can be used as next hops on a route towards key.
 void lookup(Id id)
          Given a key, it generates the message and listener to obtain the owner of this one.
 java.util.Vector neighborSet(int max)
          Obtains an unordered list of up to max nodes that are neighbors of the local node.
 void networkStabilized(boolean networkStable)
          The networkStabilized's method is a callback method used for the network simulator to notify to all nodes the stabilization process has finished and the topology is built up.
protected  void notify(NodeHandle nh)
          Verify if the indicated node is the true predecessor
 Queue outMessages()
          Overwrites the outMessages to evaluates the internal flag hasFailed for not to deliver the outgoing queue of messages.
 void prettyPrintNode()
          Shows for System.out only the owner Id, its predecessor and successor.
 void printNode()
          Shows for System.out all information of the node, including finger table.
 boolean process(int actualStep)
          Given a time fraction, treats the messages and executes the periodicas actions, as for example, the stabilization methods
 boolean range(NodeHandle node, Id rank, Id leftKey, Id rightKey)
          This operation provides information about ranges of keys for which the node is currently a root.
 java.util.Vector replicaSet(Id key, int maxRank)
          Returns an ordered set of nodes on which replicas of the object with this key can be stored.
 void routeData(java.lang.String appId, NodeHandle to, NodeHandle nextHop, Message msg)
          Sends a RouteMessage to the ring.
protected  void routingData(RouteMessage message, NodeHandle nextHop)
          Send a message to unknown destination node via routing.
protected  void sendData(RouteMessage message, NodeHandle hint)
          Send a message to destination node directly.
protected  void setFinger(int pos, NodeHandle handle)
          Sets a especific finger of the finger table
 void setPred(NodeHandle handle)
          Sets the predecessor node
 void setSucc(NodeHandle handle)
          Sets the successor node
protected  void stabilize()
          Verify node immediate successor and tell the successor about this, moreover generate and update the successor list.
 java.lang.String toString()
           
 
Methods inherited from class planet.generic.commonapi.NodeImpl
addMessageListener, dispatchDataMessage, getId, getIdFactory, getNewE, getRegisteredApplications, hasMoreMessages, invokeByStepToAllApplications, isLocalMessage, nextMessage, playsGoodRole, receive, registerApplication, removeMessageListener, send, setGoodRole, setTimer, setTimer
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

REQUEST

public static final int REQUEST
Mode value: Defines the start of communication that requires response (REPLY).

See Also:
Constant Field Values

REPLY

public static final int REPLY
Mode value: Defines the response of a communication.

See Also:
Constant Field Values

REFRESH

public static final int REFRESH
Mode value: Defines a message's mode that requires only communication on one way.

See Also:
Constant Field Values

FIND_SUCC

public static final int FIND_SUCC
Type value: First message that is send by any node to get its inmediate successor.

See Also:
Constant Field Values

FIND_PRE

public static final int FIND_PRE
Type value: Start a set of messages that permits to find the inmediate successor of any new incoming node to the network.

See Also:
Constant Field Values

SET_SUCC

public static final int SET_SUCC
Type value: Informs to the node that receives this message its new inmediate successor.

See Also:
Constant Field Values

SET_PRE

public static final int SET_PRE
Type value: Informs to the node that receive this message its new inmediate predecessor. This type forces to node to change its predecessor.

See Also:
Constant Field Values

GET_PRE

public static final int GET_PRE
Type value: Start a set of messages that permits to find the inmediate node in charge of any key.

See Also:
Constant Field Values

NOTIFY

public static final int NOTIFY
Type value: Informs to the node that receive this message its inmediate predecessor. This type permits to the node to evaluate if this notification informs really of the predecessor of the node.

See Also:
Constant Field Values

SUCC_LIST

public static final int SUCC_LIST
Type value: Start a set of messages that permits the harvesting of successors of the node that send originally this message.

See Also:
Constant Field Values

BROADCAST

public static final int BROADCAST
Type value: The message with this type identifies a broadcast message.

See Also:
Constant Field Values

DATA

public static final int DATA
Type value: It identifies that this message contains an application level Message.

See Also:
Constant Field Values

TYPES

public static final java.lang.String[] TYPES
This String contains a string representation of each of types and modes values of the RouteMessage.


MODES

public static final java.lang.String[] MODES
This String contains a string representation of each mode value of the RouteMessage.


MAX

protected Id MAX

null_pointers

protected int null_pointers

finger_changes

protected int finger_changes
Detect the number of finger changes only on one simulation step.


stabRate

protected int stabRate
Number of simulation steps without changes on finger table.


realStabilizationRate

protected int realStabilizationRate
Number of simulation steps without changes on finger table, that represents a real stabilization of this node.


predecessor

protected NodeHandle predecessor

hasFailed

protected boolean hasFailed

hasLeaved

protected boolean hasLeaved

finger

public NodeHandle[] finger

start

public Id[] start

succ_list

public java.util.Vector succ_list

auxCAPI

protected java.util.Vector auxCAPI
Temporal use in Common API methods.


deux

public Id deux

temp

protected NodeHandle[] temp
Constructor Detail

ChordNode

public ChordNode(Id id)
          throws InitializationException
Constructor, create a new BadChordNode instance with this node Id

Parameters:
id - Id to set to the new node
Method Detail

getDataMessage

public static RouteMessage getDataMessage(java.lang.String appId,
                                          NodeHandle from,
                                          NodeHandle to,
                                          NodeHandle nextHop,
                                          Message msg)
                                   throws InitializationException
Return a RouteMessage with the specified values. If there are RouteMessages free, just build a new one. For generate new instances of RouteMessage will be used the implementation class that appears in properties file.

Parameters:
appId - Application Id name.
from - Source node.
to - Destination node.
nextHop - NextHop node.
Returns:
A RouteMessage with the specified values.
Throws:
InitializationException

getBroadcastMessage

public static RouteMessage getBroadcastMessage(java.lang.String appId,
                                               NodeHandle from,
                                               NodeHandle to,
                                               NodeHandle nextHop,
                                               Message msg)
                                        throws InitializationException
Return a RouteMessage with the specified values. If there are RouteMessages free, just build a new one. For generate new instances of RouteMessage will be used the implementation class that appears in properties file.

Parameters:
appId - Application Id name.
from - Source node.
to - Destination node.
nextHop - NextHop node.
Returns:
A RouteMessage with the specified values.
Throws:
InitializationException

setPred

public void setPred(NodeHandle handle)
Sets the predecessor node

Parameters:
handle - NodeHandle of the predecessor

setSucc

public void setSucc(NodeHandle handle)
Sets the successor node

Parameters:
handle - NodeHandle of the successor

getPred

public NodeHandle getPred()
Returns the NodeHandle of the present identification of the precursor of the node

Returns:
predeccesor NodeHandle

getSucc

public NodeHandle getSucc()
Returns the NodeHandle of the present identification of the successor of the node

Returns:
predeccesor NodeHandle

getSuccList

public java.util.Vector getSuccList(int max)
Returns the successor list of the present node

Parameters:
max - number of the elements to return
Returns:
successor list Vector

clearFingerChanges

protected void clearFingerChanges()
Clears the counter of the finger table changes


getFingerChanges

protected int getFingerChanges()
Returns the count of the finger table changes

Returns:
finger_changes int counter

setFinger

protected void setFinger(int pos,
                         NodeHandle handle)
Sets a especific finger of the finger table

Parameters:
pos - position of the finger
handle - new NodeHandle to change

getInfo

public java.util.Hashtable getInfo()
Description copied from class: NodeImpl
Returns information of the node

Specified by:
getInfo in class NodeImpl
Returns:
info Hashtable with the information

printNode

public void printNode()
Shows for System.out all information of the node, including finger table.


prettyPrintNode

public void prettyPrintNode()
Shows for System.out only the owner Id, its predecessor and successor.


find_successor

protected NodeHandle find_successor(NodeHandle handle)
Finds the successor of a node. If the result if null because the information its not contain in the finger table, it generate a request message and the response message content the real result

Parameters:
handle - NodeHandle of the one node
Returns:
successor Id of the node successor

find_predecessor

protected NodeHandle find_predecessor(NodeHandle handle)
Finds the predecessor of a node. If the result if null because the information its not contain in the finger table, it generate a request message and the response message content the real result

Parameters:
handle - NodeHandle of the one node
Returns:
successor NodeHandle of the node predecessor

closest_preceding_finger

protected NodeHandle closest_preceding_finger(Id id)
Finds the closest preceding finger of a node

Parameters:
id - Id of the one node
Returns:
successor NodeHandle of the node successor

find_successor

protected NodeHandle find_successor(int pos)
Finds the successor of a node. If the result if null because the information its not contain in the finger table, it generate a request message and the the content response message has been store in the finger table

Parameters:
pos - position of NodeHandle in the start table
Returns:
successor NodeHandle of the node successor

find_predecessor

protected NodeHandle find_predecessor(int pos)
Finds the predecessor of a node. If the result if null because the information its not contain in the finger table, it generate a request message and the the content response message has been store in the finger table

Parameters:
pos - position of NodeHandle in the start table
Returns:
successor NodeHandle of the node predecessor

join

public void join(Id bootstrap)
The node joins in the network

Specified by:
join in interface Node
Specified by:
join in class NodeImpl
Parameters:
bootstrap - Id of arbitrary node in the network

leave

public void leave()
The node leaves the network

Specified by:
leave in interface Node
Specified by:
leave in class NodeImpl

stabilize

protected void stabilize()
Verify node immediate successor and tell the successor about this, moreover generate and update the successor list.


notify

protected void notify(NodeHandle nh)
Verify if the indicated node is the true predecessor

Parameters:
nh - node to check

fix_fingers

protected void fix_fingers()
This method allows to update a finger table position.


lookup

public void lookup(Id id)
Given a key, it generates the message and listener to obtain the owner of this one.

Specified by:
lookup in class NodeImpl
Parameters:
id - Id of the key

sendData

protected void sendData(RouteMessage message,
                        NodeHandle hint)
Send a message to destination node directly.

Parameters:
message - Message to deliver from application.
hint - Proposed node handle for the next hop.

routingData

protected void routingData(RouteMessage message,
                           NodeHandle nextHop)
Send a message to unknown destination node via routing.

Parameters:
message - Message to deliver from application.
nextHop - Proposed next hop.

routeData

public void routeData(java.lang.String appId,
                      NodeHandle to,
                      NodeHandle nextHop,
                      Message msg)
Sends a RouteMessage to the ring. If nextHop is null, it shows that the destination node is unknown and the message will be routed. If nextHop is not null, it's the destination NodeHandle and it must be reached directly.

Parameters:
appId - The applicationId The application identifier of the incoming application message.
to - The destination NodeHandle.
nextHop - The next hop NodeHandle if it is known.
msg - The incoming message from above layers.

broadcast

public void broadcast(java.lang.String appId,
                      NodeHandle to,
                      NodeHandle nextHop,
                      Message msg)
Initiating a Broadcast Message

Parameters:
appId - Application which sends this broadcast.
to - Destination of the broadcast.
nextHop - Next hop.
msg - Message to be sent into the broadcast.

dispatcher

public void dispatcher(RouteMessage msg)
Treats the messages and according to the case, executes the generic listeners or listeners specialized, forward the messages or send responses messages

Parameters:
msg - IMessage to treat

process

public boolean process(int actualStep)
Given a time fraction, treats the messages and executes the periodicas actions, as for example, the stabilization methods

Specified by:
process in interface Node
Overrides:
process in class NodeImpl
Parameters:
actualStep - Actual simulation step.
Returns:
true if the node needs to continue the stabilization process. false if node is just stabilized.

isAlive

public boolean isAlive()
Description copied from interface: Node
Informs if this node is alive.

Returns:
true if the node is alive. false if the node has fail or leave.
See Also:
Test if Node is alive

toString

public java.lang.String toString()

getLocalHandle

public NodeHandle getLocalHandle()
Return the local NodeHandle.

Specified by:
getLocalHandle in interface Node
Overrides:
getLocalHandle in class NodeImpl
Returns:
Actual NodeHandle for this Node.
See Also:
Node.getLocalHandle()

fail

public void fail()
Sets alive flag to false.

See Also:
Node.fail()

outMessages

public Queue outMessages()
Overwrites the outMessages to evaluates the internal flag hasFailed for not to deliver the outgoing queue of messages. This implementation is only for Chord overlay.

Specified by:
outMessages in interface Node
Overrides:
outMessages in class NodeImpl
Returns:
null if the node has failed. The outgoing queue if the node is alive or just has leaved at this simulation step.
See Also:
Node.outMessages(), NodeImpl.outMessages()

networkStabilized

public void networkStabilized(boolean networkStable)
The networkStabilized's method is a callback method used for the network simulator to notify to all nodes the stabilization process has finished and the topology is built up.

Parameters:
networkStable - True wether the network is stable.

getEInGML

public void getEInGML(java.util.Collection E,
                      GMLConstraint constraint)
This method is a callback method used to collect all of the edges of a graph according to GML file format for latter visual graph performance.

Parameters:
E - Edge Set
constraint - Constraints for edge selection

localLookup

public java.util.Vector localLookup(Id key,
                                    int max,
                                    boolean safe)
Returns a list of nodes that can be used as next hops on a route towards key. If is safe, the expected fraction of faulty nodes in the list is guaranteed to be no higher than the fraction of faulty nodes in the overlay.

In Chord, must be returns the max successors of key in the node's location table.

Parameters:
key - Target key
max - Number of next hops.
safe - This flag is not consulted.
Returns:
Until a maximum of max nodes to use as next hop, or null if key is not in range of node's location table.
See Also:
Node.localLookup(planet.commonapi.Id, int, boolean)

firstLocalLookup

public int firstLocalLookup(Id key)
Detects de first position that key is in range of some position of finger table.

Parameters:
key - Id to find the first position of finger table is responsible.
Returns:
-1 if the key is not in range of the finger table, or some value between 0..Properties.bitsKey-1

neighborSet

public java.util.Vector neighborSet(int max)
Description copied from interface: Node
Obtains an unordered list of up to max nodes that are neighbors of the local node.

Parameters:
max - Maximum of nodes to return.
Returns:
Neighbor nodes. At the first position appears the predecessor node, and following the rest of successors nodes.
See Also:
Obtains an unordered list of up to max nodes that are neighbors of the local node.

range

public boolean range(NodeHandle node,
                     Id rank,
                     Id leftKey,
                     Id rightKey)
Description copied from interface: Node
This operation provides information about ranges of keys for which the node is currently a root. Returns false if the range could not be determined, true otherwise.

It is an error to query the range of a node not present in the neighbor set.

The [leftKey,rightKey] denotes the inclusive range of key values.

Parameters:
node - Node that is currently a root of some range of keys.
rank - Number of keys that is root the node (rank=rightKey-leftKey).
leftKey - The value that appears in the invokation is the candidate left key of the range. It may be modified to reflect the correct left margin once invokation has finished.
rightKey - Shows once the invokation has finished the left margin of the range. It must be initialized to 0 (zero) before this method could be invoked.
Returns:
true if the range could be determined; false otherwise, including the case of node is not present in the neighbor set returned by neighborSet(). If false is returned, the leftKey and rightKey are not corrects.
See Also:
This operation provides information about ranges of keys for which the node is currently a root. Returns false if the range could not be determined, true otherwise.

It is an error to query the range of a node not present in the neighbor set.

The [leftKey,rightKey] denotes the inclusive range of key values.

replicaSet

public java.util.Vector replicaSet(Id key,
                                   int maxRank)
Description copied from interface: Node
Returns an ordered set of nodes on which replicas of the object with this key can be stored. The maximum number of nodes is maxRank. If the implementation's maximum replica set size is lower, then its maximum replica set is returned.

Parameters:
key - Key from which obtain the replica set.
maxRank - Number of nodes in replica set.
Returns:
Up to maxRank nodes as replica set.
See Also:
Returns the replica node set. The number of successor list is defined in the context.

getAllLinks

public java.util.Set getAllLinks()
Gets all node connections to other nodes as its NodeHandles. The order of NodeHandles is unexpected.

Returns:
A set with all connections as NodeHandles.

getClosestNodeHandle

public NodeHandle getClosestNodeHandle(Id id)
Returns the NodeHandle closest to id.

Specified by:
getClosestNodeHandle in class NodeImpl
Parameters:
id - Id to find.
Returns:
The NodeHandle closest to id.