Rice Pastry API

rice.pastry.routing
Class RoutingTable

java.lang.Object
  extended by java.util.Observable
      extended by rice.pastry.routing.RoutingTable
All Implemented Interfaces:
NodeSetEventSource

public class RoutingTable
extends java.util.Observable
implements NodeSetEventSource

The Pastry routing table.

The size of this table is determined by two constants:

We write out node ids as numbers in base 2 b . They will have length D = ceiling(log 2 b 2 n ). The table is stored from 0...(D-1) by 0...(2 b - 1). The table stores a set of node handles at each entry. At address [index][digit], we store the set of handles were the most significant (numerically) difference from the node id that the table routes for at the index th digit and the differing digit is digit. An index of 0 is the least significant digit.

Version:
$Id: RoutingTable.java 4654 2009-01-08 16:33:07Z jeffh $
Author:
Andrew Ladd, Peter Druschel

Field Summary
 byte idBaseBitLength
          The routing calculations will occur in base 2 idBaseBitLength
 NodeHandle myNodeHandle
           
protected  PastryNode pn
           
static int TEST_FAIL_EXISTING_ARE_BETTER
           
static int TEST_FAIL_NO_PREFIX_MATCH
           
static int TEST_SUCCESS_AVAILABLE_SPACE
           
static int TEST_SUCCESS_BETTER_PROXIMITY
           
static int TEST_SUCCESS_ENTRY_WAS_DEAD
           
static int TEST_SUCCESS_NO_ENTRIES
           
 
Constructor Summary
RoutingTable(NodeHandle me, int max, byte base, PastryNode pn)
          Constructor.
 
Method Summary
 void addNodeSetListener(NodeSetListener listener)
           
 void addObserver(java.util.Observer o)
          Deprecated. use addNodeSetListener
 NodeSet alternateRoutes(Id key, int max)
          Determines a set of alternate hops towards a given key.
 java.util.Iterator<NodeHandle> alternateRoutesIterator(Id key)
          More efficient implementation, but less accurate, doesn't include lower levels of rt.
 java.util.List<NodeHandle> asList()
          Does not return self
 byte baseBitLength()
          return the bit length of the base
 NodeHandle bestAlternateRoute(Id key)
          Determines an alternate hop numerically closer to the key than the one we are at.
 NodeHandle bestAlternateRoute(int minLiveness, Id key)
          Determines an alternate hop numerically closer to the key than the one we are at.
 void deleteObserver(java.util.Observer o)
          Deprecated. use deleteNodeSetListener
 void destroy()
          Unregisters as an observer on all nodehandles.
 NodeHandle get(Id nid)
          Gets the node handle associated with a given id.
 RouteSet getBestEntry(Id key)
          Gets the set of handles that match at least one more digit of the key than the local Id.
 RouteSet getRouteSet(int index, int digit)
          Gets the set of handles at a particular entry in the table.
 RouteSet[] getRow(int i)
          Get a row from the routing table.
 void nodeSetUpdate(java.lang.Object o, NodeHandle handle, boolean added)
          Is called by the Observer pattern whenever a RouteSet in this table has changed.
 int numColumns()
          return ths number of columns in the routing table
 int numEntries()
           
 short numRows()
          return the number of rows in the routing table
 int numUniqueEntries()
           
 java.lang.String printSelf()
           
 boolean put(NodeHandle handle)
          Puts a handle into the routing table.
 NodeHandle remove(NodeHandle nh)
          Removes a node id from the table.
 void removeNodeSetListener(NodeSetListener listener)
           
 int test(NodeHandle handle)
           
 java.lang.String toString()
          produces a String representation of the routing table, showing the number of node handles in each entry
 
Methods inherited from class java.util.Observable
clearChanged, countObservers, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

idBaseBitLength

public byte idBaseBitLength
The routing calculations will occur in base 2 idBaseBitLength


myNodeHandle

public NodeHandle myNodeHandle

pn

protected PastryNode pn

TEST_FAIL_NO_PREFIX_MATCH

public static final int TEST_FAIL_NO_PREFIX_MATCH
See Also:
Constant Field Values

TEST_FAIL_EXISTING_ARE_BETTER

public static final int TEST_FAIL_EXISTING_ARE_BETTER
See Also:
Constant Field Values

TEST_SUCCESS_BETTER_PROXIMITY

public static final int TEST_SUCCESS_BETTER_PROXIMITY
See Also:
Constant Field Values

TEST_SUCCESS_ENTRY_WAS_DEAD

public static final int TEST_SUCCESS_ENTRY_WAS_DEAD
See Also:
Constant Field Values

TEST_SUCCESS_AVAILABLE_SPACE

public static final int TEST_SUCCESS_AVAILABLE_SPACE
See Also:
Constant Field Values

TEST_SUCCESS_NO_ENTRIES

public static final int TEST_SUCCESS_NO_ENTRIES
See Also:
Constant Field Values
Constructor Detail

RoutingTable

public RoutingTable(NodeHandle me,
                    int max,
                    byte base,
                    PastryNode pn)
Constructor.

Parameters:
me - the node id for this routing table.
max - the maximum number of entries at each table slot.
Method Detail

numColumns

public int numColumns()
return ths number of columns in the routing table

Returns:
number of columns

numRows

public short numRows()
return the number of rows in the routing table

Returns:
number of rows

baseBitLength

public byte baseBitLength()
return the bit length of the base

Returns:
baseBitLength

bestAlternateRoute

public NodeHandle bestAlternateRoute(Id key)
Determines an alternate hop numerically closer to the key than the one we are at. This assumes that bestEntry did not produce a live nodeHandle that matches the next digit of the key.

Parameters:
key - the key
Returns:
a nodeHandle of a numerically closer node, relative to the key

bestAlternateRoute

public NodeHandle bestAlternateRoute(int minLiveness,
                                     Id key)
Determines an alternate hop numerically closer to the key than the one we are at. This assumes that bestEntry did not produce a live nodeHandle that matches the next digit of the key.

Parameters:
key - the key
Returns:
a nodeHandle of a numerically closer node, relative to the key

alternateRoutes

public NodeSet alternateRoutes(Id key,
                               int max)
Determines a set of alternate hops towards a given key.

Parameters:
key - the key
max - the maximal number of alternate hops requested
Returns:
a set of nodehandles, or null if no alternate hops exist

alternateRoutesIterator

public java.util.Iterator<NodeHandle> alternateRoutesIterator(Id key)
More efficient implementation, but less accurate, doesn't include lower levels of rt.

Parameters:
key -
Returns:

getRouteSet

public RouteSet getRouteSet(int index,
                            int digit)
Gets the set of handles at a particular entry in the table.

Parameters:
index - the index of the digit in base 2 idBaseBitLength .0 is the least significant.
digit - ranges from 0... 2 idBaseBitLength - 1 . Selects which digit to use.
Returns:
a read-only set of possible handles located at that position in the routing table, or null if none are known

getBestEntry

public RouteSet getBestEntry(Id key)
Gets the set of handles that match at least one more digit of the key than the local Id.

Parameters:
key - the key
Returns:
a read-only set of possible handles, or null if none are known

put

public boolean put(NodeHandle handle)
Puts a handle into the routing table.

Parameters:
handle - the handle to put.

test

public int test(NodeHandle handle)

get

public NodeHandle get(Id nid)
Gets the node handle associated with a given id.

Parameters:
nid - a node id
Returns:
the handle associated with that id, or null if none is known.

getRow

public RouteSet[] getRow(int i)
Get a row from the routing table.

Parameters:
i - which row
Returns:
an array which is the ith row.

remove

public NodeHandle remove(NodeHandle nh)
Removes a node id from the table.

Parameters:
nid - the node id to remove.
Returns:
the handle that was removed, or null if it did not exist.

nodeSetUpdate

public void nodeSetUpdate(java.lang.Object o,
                          NodeHandle handle,
                          boolean added)
Is called by the Observer pattern whenever a RouteSet in this table has changed.

Parameters:
o - the RouteSet
arg - the event

toString

public java.lang.String toString()
produces a String representation of the routing table, showing the number of node handles in each entry

Overrides:
toString in class java.lang.Object

printSelf

public java.lang.String printSelf()

numEntries

public int numEntries()

numUniqueEntries

public int numUniqueEntries()

addObserver

public void addObserver(java.util.Observer o)
Deprecated. use addNodeSetListener

Generates too many objects to use this interface

Overrides:
addObserver in class java.util.Observable

deleteObserver

public void deleteObserver(java.util.Observer o)
Deprecated. use deleteNodeSetListener

Generates too many objects to use this interface

Overrides:
deleteObserver in class java.util.Observable

addNodeSetListener

public void addNodeSetListener(NodeSetListener listener)
Specified by:
addNodeSetListener in interface NodeSetEventSource

removeNodeSetListener

public void removeNodeSetListener(NodeSetListener listener)
Specified by:
removeNodeSetListener in interface NodeSetEventSource

asList

public java.util.List<NodeHandle> asList()
Does not return self

Returns:
list of NodeHandle

destroy

public void destroy()
Unregisters as an observer on all nodehandles.


Rice Pastry API

Copyright © 2001-2005 - Rice Pastry.


Imprint-Dataprotection