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 NodeImpl 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.
protected  int bitsPerKey
          Number of bits per key to use as current configuration.
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
          Current finger table.
protected  int fingerChanges
          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
          Flag that shows when this node has failed.
protected  boolean hasLeaved
          Flag that shows when this node has leaved.
protected  boolean hasReceivedSucc
          Shows when has been received the GET_PRE response, requested on the stabilize() method to find the successor.
protected  Id MAX
          Maximum Id value with the current configuration.
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 nullPointers
          Index to use within stabilization process onto the finger table.
protected  NodeHandle predecessor
          The current predecessor in the Chord ring.
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
          The starting indices for the finger table (as Finger[k].start).
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.
 java.util.Vector succList
          Current successor list.
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()
          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
 void buildEdges(java.lang.String resultName, java.util.Collection edgeCollection, ResultsConstraint constraint)
          This method is a callback method used to collect all edges of a graph according to resultName format.
protected  void cleanSuccList()
          Deletes all NodeHandles that exceeds the required size of successor list.
protected  void clearFingerChanges()
          Clears the counter of the finger table changes
protected  NodeHandle closestPrecedingFinger(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 findPredecessor(int pos)
          Finds the predecessor of a node.
protected  NodeHandle findPredecessor(NodeHandle handle)
          Finds the predecessor of a node.
protected  NodeHandle findSuccessor(int pos)
          Finds the successor of a node.
protected  NodeHandle findSuccessor(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 fixFingers()
          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.
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(NodeHandle 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.
 java.util.Vector neighborSet(int max)
          Obtains an unordered list of up to max nodes that are neighbors of the local node.
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, int mode)
          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
 Node setValues(Id newId)
          Sets the new Id for this 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
addEdges, addMessageListener, buildMessage, buildMessage, buildNewEdge, dispatchDataMessage, getId, getRegisteredApplication, getRegisteredApplications, hasMoreMessages, inMessages, invokeByStepToAllApplications, isLocalMessage, nextMessage, playsGoodRole, receive, registerApplication, removeMessageListener, send, sendMessage, sendMessage, sendMessage, sendMessage, 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
Maximum Id value with the current configuration.


nullPointers

protected int nullPointers
Index to use within stabilization process onto the finger table.


fingerChanges

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


stabRate

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


bitsPerKey

protected int bitsPerKey
Number of bits per key to use as current configuration.


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
The current predecessor in the Chord ring.


hasFailed

protected boolean hasFailed
Flag that shows when this node has failed.


hasLeaved

protected boolean hasLeaved
Flag that shows when this node has leaved.


hasReceivedSucc

protected boolean hasReceivedSucc
Shows when has been received the GET_PRE response, requested on the stabilize() method to find the successor.


finger

public NodeHandle[] finger
Current finger table.


start

public Id[] start
The starting indices for the finger table (as Finger[k].start).


succList

public java.util.Vector succList
Current successor 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()
          throws InitializationException
Constructor, create a new BadChordNode instance with this node Id

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

cleanSuccList

protected void cleanSuccList()
Deletes all NodeHandles that exceeds the required size of successor list.


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.


findSuccessor

protected NodeHandle findSuccessor(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

findPredecessor

protected NodeHandle findPredecessor(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

closestPrecedingFinger

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

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

findSuccessor

protected NodeHandle findSuccessor(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

findPredecessor

protected NodeHandle findPredecessor(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(NodeHandle 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

fixFingers

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


sendData

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

Parameters:
message - Message to deliver from application.
hint - Proposed node handle for the next hop.
mode - Message mode (REQUEST or REFRESH)

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()

buildEdges

public void buildEdges(java.lang.String resultName,
                       java.util.Collection edgeCollection,
                       ResultsConstraint constraint)
This method is a callback method used to collect all edges of a graph according to resultName format.

Parameters:
resultName - Result type name to use.
edgeCollection - Edge collection where to put in all produced ResultEdges.
constraint - ResultsConstraint 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 interface Node
Specified by:
getClosestNodeHandle in class NodeImpl
Parameters:
id - Id to find.
Returns:
The NodeHandle closest to id.

setValues

public Node setValues(Id newId)
               throws InitializationException
Sets the new Id for this node.

Specified by:
setValues in interface Node
Overrides:
setValues in class NodeImpl
Parameters:
newId - The new Id.
Returns:
The same instance, after it has been updated.
Throws:
InitializationException
See Also:
Node.setValues(planet.commonapi.Id)