meteor.dht.chord
Class ChordServiceImpl

java.lang.Object
  java.lang.Thread
      meteor.dht.chord.ChordServiceImpl

All Implemented Interfaces:

ChordService, DHTService, net.jxta.discovery.DiscoveryListener, java.util.EventListener, net.jxta.platform.Module, net.jxta.rendezvous.RendezvousListener, java.lang.Runnable, net.jxta.service.Service

public class ChordServiceImpl

extends java.lang.Thread

implements ChordService, net.jxta.discovery.DiscoveryListener, net.jxta.rendezvous.RendezvousListener

The implementation of the DHT service providing an implementation for the DHT querying

Author:

Vincent Matossian December 2003

Field Summary

java.lang.String	handlerName
net.jxta.peergroup.PeerGroup	peergroup
static java.lang.String	refModuleSpecID

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Fields inherited from interface meteor.dht.chord.ChordService

refModuleClassID

Fields inherited from interface net.jxta.platform.Module

START_AGAIN_PROGRESS, START_AGAIN_STALLED, START_OK

Constructor Summary

ChordServiceImpl()
Constructor for the DHT service implementation

Method Summary

void	addListener(DHTListener listener) Add a listener to this class.
void	blockOnSend() Synchronization for the Messaging between peers
void	bootstrap(java.lang.String peerID) Start the bootstrapping
void	checkPredecessor() Checks if predecessor is alive If not remove the current predecessor
java.math.BigInteger	closest_preceding_node(java.math.BigInteger id) If the id of the successor of the node we are at is between this identifier and the desired identifier return this node
void	discoveryEvent(net.jxta.discovery.DiscoveryEvent e) Is called when a discovery message is received Used ONLY during the bootstrap protocol
java.math.BigInteger	find_predecessor(java.math.BigInteger id, int mode, int owner) Find the predecessor of a node id This is used in the update_others protocol, during stabilization and is part of a test shell command findpredecessor.
void	find_successor(QueryMessage query) The query contains the target identifier to look for If this identifier is visible from this node's finger table then it updates its finger table just as a fix_finger routine The forwarding of the query in the process of finding the successor is defined in MessageHandler.processQuery not in find_successor because it is the responsibility of the messaging to forward queries this may seem confusing as it differs a bit from Chord's pseudocode.
void	fix_fingers() Periodically fix fingers by finding successor of the next identifier (n+1,2,4,8,16 etc...)
void	get(java.lang.String key) Hashtable primitive to retrieve an entry from the table
FingerTable	getFingerTable()
net.jxta.document.Advertisement	getImplAdvertisement() Get the Implemetation advertisement
net.jxta.service.Service	getInterface()
java.math.BigInteger	getNodeID(java.lang.String id) Hashes the JXTA peer id into an overlay node id
java.math.BigInteger	getTopologySize() Returns the size of the topoloy as an Integer In the case of a ring, the size of the ring, In the case of a mesh, the width ot th mesh
boolean	inInterval(java.math.BigInteger id, java.math.BigInteger begin, java.math.BigInteger end, boolean incLeft, boolean incRight) Checks whether id is in the interval [begin,end] or (begin,end) depending on the boolean inclusive
void	init_finger_table(java.math.BigInteger bootstrap) Initializes the finger table of this node before starting the stabilization protocol Sequence of things done: finger[0].node= bootstrap.find_successor(finger[0].start) predecessor = successor.predecessor successor.predecessor = this for i=0 to m if(finger[i+1].start E [this,finger[i].node)) finger[i+1].node=finger[i].node else finger[i+1].node=bootstrap.find_successor(finger[i+1].start)
void	init(net.jxta.peergroup.PeerGroup group, net.jxta.id.ID assignedID, net.jxta.document.Advertisement implAdv) Invoked when the service is added to the peergroup in the Loader class.
boolean	isLocal(java.math.BigInteger id) Looks up the local finger table and returns true if the id is present
void	join(java.lang.String bootstrap) The JOIN protocol If the target is identical to the local ID i.e.
int	log2(java.math.BigInteger x) Log base 2
void	lookup(java.math.BigInteger target, int owner) Lookup the successor of an identifier.
void	lookup(java.math.BigInteger target, int owner, int mode) Lookup the successor of an identifier
void	lookup(java.math.BigInteger target, int owner, java.lang.String squidQuery) Lookup the successor of an identifier with a SquidQuery
void	notify(java.math.BigInteger id) Notify successor that this node may be its predecessor
void	notifyReceived() Invoked in messageHandler's processResponse to notify the lookup Service that a response for its blocking query has just been received, and the response identifier of the query set as successor ID.
void	put(java.lang.String key, java.lang.String value) Hashtable primitive to insert an element in the table
void	receivedDHTEntry(QueryMessage query) Received a DHT Entry
void	receivedPingMessage() Received a Ping Message from predecessor
void	receivedPredecessor(java.math.BigInteger predecessor) When a predecessor query is answered this method is invoked from the MessageHandler processResponse.
void	receivedQuery(QueryMessage query) Received a Squid Query message
void	receivedStringMessage(QueryMessage resp) Processing simple String messages
void	receivedSuccessor(QueryMessage responseMessage) This method is invoked from the MessageHandler processResponse.
void	removeListener(DHTListener listener) Remove a listener
void	rendezvousEvent(net.jxta.rendezvous.RendezvousEvent event) Raised on Rendezvous Event
void	run() Start the thread running periodically Stabilization and finger fixing protocols
void	setTopologySize(int s) Set the size of the topology For a ring, the size of the ring For a mesh, the width of the mesh
void	stabilize_fingers() Update the fingertable on a predecessor reset event
void	stabilize_others(QueryMessage q) When a node has failed and is detected the stabilization protocol sends updates around the ring to other nodes starting from its predecessor
void	stabilize() Stabilization protocol This routine is invoked periodically at a rate defined in the run method by the variable RATE.
int	startApp(java.lang.String[] args) Invoked when calling peergroup.startApps in Loader class.
void	stopApp() Invoked when application stops
void	update_finger_table(QueryMessage qm) UPdate finger table if (s E [n,finger[i].node)) finger[i].node = s p=predecessor p.update_finger_table(s,i)
void	update_others() Updates all nodes that might point to this current node p=find_predecessor(n-2^(i-1)) p.update_finger_table(n,i)

Methods inherited from class java.lang.Thread

activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, getContextClassLoader, getName, getPriority, getThreadGroup, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setName, setPriority, sleep, sleep, start, stop, stop, suspend, toString, yield

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

refModuleSpecID

public static final java.lang.String refModuleSpecID

peergroup

public net.jxta.peergroup.PeerGroup peergroup

handlerName

public java.lang.String handlerName

Constructor Detail

ChordServiceImpl

public ChordServiceImpl()

Constructor for the DHT service implementation

Method Detail

getImplAdvertisement

public net.jxta.document.Advertisement getImplAdvertisement()

Get the Implemetation advertisement

Specified by:

getImplAdvertisement in interface net.jxta.service.Service

Returns:

the advertisement associated to this implementation

getInterface

public net.jxta.service.Service getInterface()

Specified by:

getInterface in interface net.jxta.service.Service

Returns:

this implementation of the DHT service interface

addListener

public void addListener(DHTListener listener)

Add a listener to this class. All registered listeners will be notified when a receivedQuerry and receivedSuccessor event occurs. (See MessageHandler)

Specified by:

addListener in interface ChordService

removeListener

public void removeListener(DHTListener listener)

Remove a listener

Specified by:

removeListener in interface ChordService

init

public void init(net.jxta.peergroup.PeerGroup group,
                 net.jxta.id.ID assignedID,
                 net.jxta.document.Advertisement implAdv)
          throws net.jxta.exception.PeerGroupException

Invoked when the service is added to the peergroup in the Loader class. Init obtains a reference to the peergroup

Specified by:

init in interface net.jxta.platform.Module

Parameters:

group - the peergroup to which this implementaiton belongs

implAdv - the implementaiton advertisement for this module

Throws:

net.jxta.exception.PeerGroupException

startApp

public int startApp(java.lang.String[] args)

Invoked when calling peergroup.startApps in Loader class. Gets the services from the peergroup and defines the credentials.

Specified by:

startApp in interface net.jxta.platform.Module

stopApp

public void stopApp()

Invoked when application stops

Specified by:

stopApp in interface net.jxta.platform.Module

setTopologySize

public void setTopologySize(int s)

Set the size of the topology For a ring, the size of the ring For a mesh, the width of the mesh

Specified by:

setTopologySize in interface DHTService

getTopologySize

public java.math.BigInteger getTopologySize()

Description copied from interface: DHTService

Returns the size of the topoloy as an Integer In the case of a ring, the size of the ring, In the case of a mesh, the width ot th mesh

Specified by:

getTopologySize in interface DHTService

Returns:

the size of the topology

getFingerTable

public FingerTable getFingerTable()

Specified by:

getFingerTable in interface ChordService

Returns:

returns the finger table

getNodeID

public java.math.BigInteger getNodeID(java.lang.String id)

Description copied from interface: DHTService

Hashes the JXTA peer id into an overlay node id

Specified by:

getNodeID in interface DHTService

Returns:

the Node ID on the ring

log2

public int log2(java.math.BigInteger x)

Log base 2

Specified by:

log2 in interface ChordService

bootstrap

public void bootstrap(java.lang.String peerID)

Start the bootstrapping

Specified by:

bootstrap in interface DHTService

discoveryEvent

public void discoveryEvent(net.jxta.discovery.DiscoveryEvent e)

Is called when a discovery message is received Used ONLY during the bootstrap protocol

Specified by:

discoveryEvent in interface net.jxta.discovery.DiscoveryListener

join

public void join(java.lang.String bootstrap)

The JOIN protocol If the target is identical to the local ID i.e. this is the bootstrap node then set Finger Table Successor and Predecessor and start the periodic updates If not ask bootstrap node to find this node's successor

Specified by:

join in interface DHTService

init_finger_table

public void init_finger_table(java.math.BigInteger bootstrap)

Initializes the finger table of this node before starting the stabilization protocol Sequence of things done: finger[0].node= bootstrap.find_successor(finger[0].start) predecessor = successor.predecessor successor.predecessor = this for i=0 to m if(finger[i+1].start E [this,finger[i].node)) finger[i+1].node=finger[i].node else finger[i+1].node=bootstrap.find_successor(finger[i+1].start)

Specified by:

init_finger_table in interface ChordService

update_others

public void update_others()

Updates all nodes that might point to this current node p=find_predecessor(n-2^(i-1)) p.update_finger_table(n,i)

Specified by:

update_others in interface ChordService

update_finger_table

public void update_finger_table(QueryMessage qm)

UPdate finger table if (s E [n,finger[i].node)) finger[i].node = s p=predecessor p.update_finger_table(s,i)

Specified by:

update_finger_table in interface ChordService

lookup

public void lookup(java.math.BigInteger target,
                   int owner)

Lookup the successor of an identifier.

Specified by:

lookup in interface ChordService

lookup

public void lookup(java.math.BigInteger target,
                   int owner,
                   int mode)

Lookup the successor of an identifier

Specified by:

lookup in interface DHTService

lookup

public void lookup(java.math.BigInteger target,
                   int owner,
                   java.lang.String squidQuery)

Lookup the successor of an identifier with a SquidQuery

Specified by:

lookup in interface ChordService

find_successor

public void find_successor(QueryMessage query)

The query contains the target identifier to look for If this identifier is visible from this node's finger table then it updates its finger table just as a fix_finger routine The forwarding of the query in the process of finding the successor is defined in MessageHandler.processQuery not in find_successor because it is the responsibility of the messaging to forward queries this may seem confusing as it differs a bit from Chord's pseudocode.

Specified by:

find_successor in interface ChordService

Parameters:

query - the QueryMessage defining the Target ID, the Local ID etc...

Returns:

does not return

find_predecessor

public java.math.BigInteger find_predecessor(java.math.BigInteger id,
                                             int mode,
                                             int owner)

Find the predecessor of a node id This is used in the update_others protocol, during stabilization and is part of a test shell command findpredecessor.

Specified by:

find_predecessor in interface ChordService

Parameters:

id - the node identifier to find the predecessor of

mode - the mode in which the query is to be sent SYNCH or ASYNCH

owner - the Owner of the query, USER or CHORD

Returns:

the prededecessor node identifier id

closest_preceding_node

public java.math.BigInteger closest_preceding_node(java.math.BigInteger id)

If the id of the successor of the node we are at is between this identifier and the desired identifier return this node

Specified by:

closest_preceding_node in interface ChordService

inInterval

public boolean inInterval(java.math.BigInteger id,
                          java.math.BigInteger begin,
                          java.math.BigInteger end,
                          boolean incLeft,
                          boolean incRight)

Checks whether id is in the interval [begin,end] or (begin,end) depending on the boolean inclusive

Specified by:

inInterval in interface ChordService

isLocal

public boolean isLocal(java.math.BigInteger id)

Looks up the local finger table and returns true if the id is present

Specified by:

isLocal in interface ChordService

Returns:

true if the identifier is in range

stabilize

public void stabilize()

Stabilization protocol This routine is invoked periodically at a rate defined in the run method by the variable RATE. The objective of stabilization is to maintain the finger table up to date. In this method a Message is sent to the successor of this node asking it for its predecessor. Upon reception of the predecessor, the next method, receivedPredecessor is invoked A precheck is performed, if the current node's predecessor if identical to that node's id then there is only a single node in the network. If the successor node is the current node but the predecessor is different, then the successor has to be set to the predecessor id, case where there is two nodes in the network. Other cases will require a message to be sent to the sucessor.

Specified by:

stabilize in interface ChordService

notify

public void notify(java.math.BigInteger id)

Notify successor that this node may be its predecessor

Specified by:

notify in interface ChordService

receivedPredecessor

public void receivedPredecessor(java.math.BigInteger predecessor)

When a predecessor query is answered this method is invoked from the MessageHandler processResponse. This is part of the stabilization protocol, when a successor node returns its predecessor. The predecessor ID is checked for existence in (localID,successor) If it does belong between this node's id and its successor then this node's successor is updated and a Notification message is sent to our successor to inform it that we are its "new" predecessor.

Specified by:

receivedPredecessor in interface ChordService

Parameters:

predecessor - the returned predecessor ID from this node's successor

receivedSuccessor

public void receivedSuccessor(QueryMessage responseMessage)

This method is invoked from the MessageHandler processResponse. Similarly to receivedPredecessor, receivedSuccessor is raised when a node returns a successor identifier. This is used more often than for Predecessor queries, as it is needed by the JOIN Protocol, FINGER FIXING protocol as well as any Identifier LOOKUP.

Specified by:

receivedSuccessor in interface ChordService

receivedQuery

public void receivedQuery(QueryMessage query)

Received a Squid Query message

receivedDHTEntry

public void receivedDHTEntry(QueryMessage query)

Received a DHT Entry

receivedPingMessage

public void receivedPingMessage()

Received a Ping Message from predecessor

receivedStringMessage

public void receivedStringMessage(QueryMessage resp)

Processing simple String messages

blockOnSend

public void blockOnSend()

Synchronization for the Messaging between peers

Specified by:

blockOnSend in interface ChordService

notifyReceived

public void notifyReceived()

Invoked in messageHandler's processResponse to notify the lookup Service that a response for its blocking query has just been received, and the response identifier of the query set as successor ID.

Specified by:

notifyReceived in interface ChordService

fix_fingers

public void fix_fingers()

Periodically fix fingers by finding successor of the next identifier (n+1,2,4,8,16 etc...)

Specified by:

fix_fingers in interface ChordService

checkPredecessor

public void checkPredecessor()

Checks if predecessor is alive If not remove the current predecessor

Specified by:

checkPredecessor in interface ChordService

stabilize_fingers

public void stabilize_fingers()

Update the fingertable on a predecessor reset event

stabilize_others

public void stabilize_others(QueryMessage q)

When a node has failed and is detected the stabilization protocol sends updates around the ring to other nodes starting from its predecessor

run

public void run()

Start the thread running periodically Stabilization and finger fixing protocols

Specified by:

run in interface java.lang.Runnable

rendezvousEvent

public void rendezvousEvent(net.jxta.rendezvous.RendezvousEvent event)

Raised on Rendezvous Event

Specified by:

rendezvousEvent in interface net.jxta.rendezvous.RendezvousListener

put

public void put(java.lang.String key,
                java.lang.String value)

Hashtable primitive to insert an element in the table

Specified by:

put in interface DHTService

get

public void get(java.lang.String key)

Hashtable primitive to retrieve an entry from the table

Specified by:

get in interface DHTService