rice.pastry.routing
Class RoutingTable

java.lang.Object
  |
  +--java.util.Observable
        |
        +--rice.pastry.routing.RoutingTable

All Implemented Interfaces:

java.util.Observer

public class RoutingTable

extends java.util.Observable

implements java.util.Observer

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 ⁿ ) . 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,v 1.15 2003/05/11 05:34:19 amislove Exp $

Author:

Andrew Ladd, Peter Druschel

Field Summary

static int

idBaseBitLength The routing calculations will occur in base 2 idBaseBitLength

Constructor Summary

RoutingTable(rice.pastry.NodeHandle me, int max)
Constructor.

Method Summary

rice.pastry.NodeSet	alternateRoutes(rice.pastry.Id key, int max) Determines a set of alternate hops towards a given key.
static int	baseBitLength() return the bit length of the base
rice.pastry.NodeHandle	bestAlternateRoute(rice.pastry.Id key) Determines an alternate hop numerically closer to the key than the one we are at.
rice.pastry.NodeHandle	get(rice.pastry.NodeId nid) Gets the node handle associated with a given id.
rice.pastry.routing.RouteSet	getBestEntry(rice.pastry.Id key) Gets the set of handles that match at least one more digit of the key than the local nodeId.
rice.pastry.routing.RouteSet	getRouteSet(int index, int digit) Gets the set of handles at a particular entry in the table.
rice.pastry.routing.RouteSet[]	getRow(int i) Get a row from the routing table.
int	numColumns() return ths number of columns in the routing table
int	numRows() return the number of rows in the routing table
void	put(rice.pastry.NodeHandle handle) Puts a handle into the routing table.
rice.pastry.NodeHandle	remove(rice.pastry.NodeId nid) Removes a node id from the table.
java.lang.String	toString() produces a String representation of the routing table, showing the number of node handles in each entry
void	update(java.util.Observable o, java.lang.Object arg) Is called by the Observer pattern whenever a RouteSet in this table has changed.

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, 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 static int idBaseBitLength

The routing calculations will occur in base 2 ^{idBaseBitLength}

Constructor Detail

RoutingTable

public RoutingTable(rice.pastry.NodeHandle me,
                    int max)

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

return the number of rows in the routing table

Returns:

number of rows

baseBitLength

public static int baseBitLength()

return the bit length of the base

Returns:

baseBitLength

bestAlternateRoute

public rice.pastry.NodeHandle bestAlternateRoute(rice.pastry.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 rice.pastry.NodeSet alternateRoutes(rice.pastry.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

getRouteSet

public rice.pastry.routing.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 rice.pastry.routing.RouteSet getBestEntry(rice.pastry.Id key)

Gets the set of handles that match at least one more digit of the key than the local nodeId.

Parameters:

key - the key

Returns:

a read-only set of possible handles, or null if none are known

put

public void put(rice.pastry.NodeHandle handle)

Puts a handle into the routing table.

Parameters:

handle - the handle to put.

get

public rice.pastry.NodeHandle get(rice.pastry.NodeId 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 rice.pastry.routing.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 rice.pastry.NodeHandle remove(rice.pastry.NodeId nid)

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.

update

public void update(java.util.Observable o,
                   java.lang.Object arg)

Is called by the Observer pattern whenever a RouteSet in this table has changed.

Specified by:

update in interface java.util.Observer

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