Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## rice.pastry.routing
Class RoutingTable

    java.lang.Object
      java.util.Observable
          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:

- `nodeIdBitLength`which determines the number of bits in a node id (which we call n ).
- `idBaseBitLength`which is the base that table is stored in (which we call b ).

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 3418 2006-10-11 13:22:51Z jeffh $
Author:
  Andrew Ladd, Peter Druschel

Field Summary
`byte` | `idBaseBitLength` The routing calculations will occur in base 2 idBaseBitLength
`NodeHandle` | `myNodeHandle` DESCRIBE THE FIELD
`protected PastryNode` | `pn` DESCRIBE THE FIELD
`static int` | `TEST_FAIL_EXISTING_ARE_BETTER` DESCRIBE THE FIELD
`static int` | `TEST_FAIL_NO_PREFIX_MATCH` DESCRIBE THE FIELD
`static int` | `TEST_SUCCESS_AVAILABLE_SPACE` DESCRIBE THE FIELD
`static int` | `TEST_SUCCESS_BETTER_PROXIMITY` DESCRIBE THE FIELD
`static int` | `TEST_SUCCESS_ENTRY_WAS_DEAD` DESCRIBE THE FIELD
`static int` | `TEST_SUCCESS_NO_ENTRIES` DESCRIBE THE FIELD

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

Method Summary
`void` | `addNodeSetListener(NodeSetListener listener)` Adds the specified NodeSet listener to receive NodeSet events from this component.
`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.List` | `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()` DESCRIBE THE METHOD
`byte` | `numRows()` return the number of rows in the routing table
`int` | `numUniqueEntries()` DESCRIBE THE METHOD
`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)` Removes the specified NodeSet listener so that it no longer receives NodeSet events from this component.
`int` | `test(NodeHandle handle)` A unit test for JUnit
`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

  DESCRIBE THE FIELD

### pn

    protected PastryNode pn

  DESCRIBE THE FIELD

### TEST_FAIL_NO_PREFIX_MATCH

    public static final int TEST_FAIL_NO_PREFIX_MATCH

  DESCRIBE THE FIELD

  See Also:
    Constant Field Values

### TEST_FAIL_EXISTING_ARE_BETTER

    public static final int TEST_FAIL_EXISTING_ARE_BETTER

  DESCRIBE THE FIELD

  See Also:
    Constant Field Values

### TEST_SUCCESS_BETTER_PROXIMITY

    public static final int TEST_SUCCESS_BETTER_PROXIMITY

  DESCRIBE THE FIELD

  See Also:
    Constant Field Values

### TEST_SUCCESS_ENTRY_WAS_DEAD

    public static final int TEST_SUCCESS_ENTRY_WAS_DEAD

  DESCRIBE THE FIELD

  See Also:
    Constant Field Values

### TEST_SUCCESS_AVAILABLE_SPACE

    public static final int TEST_SUCCESS_AVAILABLE_SPACE

  DESCRIBE THE FIELD

  See Also:
    Constant Field Values

### TEST_SUCCESS_NO_ENTRIES

    public static final int TEST_SUCCESS_NO_ENTRIES

  DESCRIBE THE FIELD

  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.
    `base` - DESCRIBE THE PARAMETER
    `pn` - DESCRIBE THE PARAMETER

Method Detail

### 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

### 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.

### numColumns

    public int numColumns()

  return ths number of columns in the routing table

  Returns:
    number of columns

### numRows

    public byte 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:
    `minLiveness` - DESCRIBE THE PARAMETER
    `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

### put

    public boolean put(NodeHandle handle)

  Puts a handle into the routing table.

  Parameters:
    `handle` - the handle to put.
  Returns:
    DESCRIBE THE RETURN VALUE

### test

    public int test(NodeHandle handle)

  A unit test for JUnit

  Parameters:
    `handle` - DESCRIBE THE PARAMETER
  Returns:
    DESCRIBE THE RETURN VALUE

### remove

    public NodeHandle remove(NodeHandle nh)

  Removes a node id from the table.

  Parameters:
    `nh` - DESCRIBE THE PARAMETER
  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
    `handle` - DESCRIBE THE PARAMETER
    `added` - DESCRIBE THE PARAMETER

### 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`
  Returns:
    A string representation of the object.

### numEntries

    public int numEntries()

  DESCRIBE THE METHOD

  Returns:
    DESCRIBE THE RETURN VALUE

### numUniqueEntries

    public int numUniqueEntries()

  DESCRIBE THE METHOD

  Returns:
    DESCRIBE THE RETURN VALUE

### 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`
  Parameters:
    `o` - The feature to be added to the Observer attribute

### 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`
  Parameters:
    `o` - DESCRIBE THE PARAMETER

### addNodeSetListener

    public void addNodeSetListener(NodeSetListener listener)

  Adds the specified NodeSet listener to receive NodeSet events from this component. If listener l is null, no exception is thrown and no action is performed.

  Specified by:
    `addNodeSetListener` in interface `NodeSetEventSource`
  Parameters:
    `listener` - Contains the NodeSetListener for NodeSetEvent data.

### removeNodeSetListener

    public void removeNodeSetListener(NodeSetListener listener)

  Removes the specified NodeSet listener so that it no longer receives NodeSet events from this component. This method performs no function, nor does it throw an exception, if the listener specified by the argument was not previously added to this component. If listener l is null, no exception is thrown and no action is performed.

  Specified by:
    `removeNodeSetListener` in interface `NodeSetEventSource`
  Parameters:
    `listener` - Contains the NodeSetListener for NodeSetEvent data.

### asList

    public java.util.List asList()

  Does not return self

  Returns:
    list of NodeHandle

### destroy

    public void destroy()

  Unregisters as an observer on all nodehandles.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2005 - Rice Pastry.