ostore.tapestry.impl
Class RoutingTable

java.lang.Object
  |
  +--ostore.tapestry.impl.RoutingTable
All Implemented Interfaces:
QuickSerializable

public class RoutingTable
extends Object
implements QuickSerializable

Implements the routing table interface.

Version:
$Id: RoutingTable.java,v 1.50 2003/05/19 20:20:55 strib Exp $
Author:
Ben Y. Zhao

Inner Class Summary
static class RoutingTable.Available
           
 
Field Summary
 PatchworkTable _patchwork
           
static int BITS_PER_DIGIT
           
static int DIGIT_VALUES
           
static int DIGITS_PER_GUID
           
 int node_status
           
 
Constructor Summary
RoutingTable(InputBuffer buffer)
           
RoutingTable(NodeId self_node_id, SecureHash guid)
           
RoutingTable(NodeId self_node_id, SecureHash guid, Classifier classifier)
           
 
Method Summary
 RouteEntry _route_to_root(int[] dest_digits, boolean exact, boolean prefix, int[] digit)
           
 RouteEntry _surrogate(int[] dest_digits, int dest_digit, int hop)
           
 boolean addBackup(int digit, int value, NodeId nid, Double latency, SecureHash guid)
          Deprecated. As of 7/24/2002 in favor of RoutingTable.write()
 void addDistance(double rtt, NodeId nid, SecureHash newguid)
          Method to add the latency measurement to the data structures
 boolean addSelf(SecureHash self)
           
 int bits_per_digit()
           
 int digit_values()
           
 int digits_per_guid()
           
static int[] digits(SecureHash h)
           
 Map get_node_map()
           
 LinkedList get_removed_nodes()
           
 NodeId get_self_node_id()
           
 RouteEntry[][] get_table()
           
 RouteEntry getEntry(int digit, int value)
           
 boolean isAttached()
           
 NodeId nextSurrogate(HashSet ignoredNodes, SecureHash selfguid)
          method that calculates the NEXT best surrogate hop other than the current node for ANY key/GUID.
 SecureHash node_id_to_guid(NodeId node_id)
           
 Double node_to_latency(NodeId node_id)
           
 LinkedList optimize(double delta, NodeId nid, SecureHash newguid)
          This function simply calls the more general optimize function with the minlevel set to 0
 LinkedList optimize(double delta, NodeId nid, SecureHash newguid, int minlevel)
           
static String printGuid(SecureHash x)
           
 SecureHash put_node_id_to_guid(NodeId node_id, SecureHash guid)
           
 void putEntry(int digit, int value, RouteEntry re)
           
 void pw_update(DeltaMsg pdrm)
          Update the Patchwork statistics to RoutingTable, given the newest delta ent out by Patchwork model.
 NodeId read(int which_digit, int digit_value)
           
 boolean remove(TapestryNeighborInfo ni)
          Remove for dummies.
 NodeId route_to_root(int[] dest_digits, boolean exact, boolean prefix, int[] digit)
          Route to the root of the tree for dest_digits, assuming that the first digit [0] - 1 digits have already been accounted for, and return the next node in the routing path.
 void serialize(OutputBuffer buffer)
          Add the object to the buffer.
protected  void setSink(SinkIF sink)
           
 NodeId surrogate(int[] dest_digits, int dest_digit, int hop)
          Find the surrogate for an empty routing table entry.
 String toShortString()
           
 String toString()
           
 boolean write(int which_digit, int digit_value, NodeId node_id, SecureHash node_guid, Double latency)
          Add primary/backup routes to the routing table.
 boolean write(TapestryNeighborInfo ni)
          Write for dummies.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

BITS_PER_DIGIT

public static final int BITS_PER_DIGIT

DIGITS_PER_GUID

public static final int DIGITS_PER_GUID

DIGIT_VALUES

public static final int DIGIT_VALUES

node_status

public int node_status

_patchwork

public PatchworkTable _patchwork
Constructor Detail

RoutingTable

public RoutingTable(NodeId self_node_id,
                    SecureHash guid,
                    Classifier classifier)

RoutingTable

public RoutingTable(NodeId self_node_id,
                    SecureHash guid)

RoutingTable

public RoutingTable(InputBuffer buffer)
             throws QSException
Method Detail

isAttached

public boolean isAttached()

digit_values

public int digit_values()

digits_per_guid

public int digits_per_guid()

bits_per_digit

public int bits_per_digit()

node_id_to_guid

public SecureHash node_id_to_guid(NodeId node_id)

put_node_id_to_guid

public SecureHash put_node_id_to_guid(NodeId node_id,
                                      SecureHash guid)

node_to_latency

public Double node_to_latency(NodeId node_id)

read

public NodeId read(int which_digit,
                   int digit_value)

write

public boolean write(TapestryNeighborInfo ni)
Write for dummies.

remove

public boolean remove(TapestryNeighborInfo ni)
Remove for dummies.

write

public boolean write(int which_digit,
                     int digit_value,
                     NodeId node_id,
                     SecureHash node_guid,
                     Double latency)
Add primary/backup routes to the routing table. This function takes in distance info about a new route, and compares it against the current latencies in the current entry, and places it in order of shortest latency first.
Parameters:
which_digit - digit of entry being added
digit_value - value of entry's Guid at the relevant digit
node_id - NodeId of entry being added
latency - Last tested latency of new entry
node_guid - Guid of new entry
Returns:
Whether the new node was actually useful (shorter) and therefore inserted into the RouteEntry.

optimize

public LinkedList optimize(double delta,
                           NodeId nid,
                           SecureHash newguid)
This function simply calls the more general optimize function with the minlevel set to 0
Parameters:
newguid - The guid of some node
nid - The nodeid of that node
delta - is the estimated RTT distance from us to that node
Returns:
Linked list of levels where node was added, or null if none

optimize

public LinkedList optimize(double delta,
                           NodeId nid,
                           SecureHash newguid,
                           int minlevel)
Parameters:
newguid - The guid of some node
nid - The nodeid of that node
delta - is the estimated RTT distance from us to that node
minlevel - is the minimum level that changes can take place
Returns:
Linked list of levels where node was added, or null if none

addBackup

public boolean addBackup(int digit,
                         int value,
                         NodeId nid,
                         Double latency,
                         SecureHash guid)
Deprecated. As of 7/24/2002 in favor of RoutingTable.write()

Add primary/backup routes to the routing table. This function takes in distance info about a new route, and compares it against the current latencies in the current entry, and places it in order of shortest latency first.
Parameters:
digit - digit of entry being added
value - value of entry's Guid at the relevant digit
nid - NodeId of entry being added
latency - Last tested latency of new entry
guid - Guid of new entry
Returns:
Whether the new node was actually useful (shorter) and therefore inserted into the RouteEntry.

getEntry

public RouteEntry getEntry(int digit,
                           int value)

putEntry

public void putEntry(int digit,
                     int value,
                     RouteEntry re)

addDistance

public void addDistance(double rtt,
                        NodeId nid,
                        SecureHash newguid)
Method to add the latency measurement to the data structures
Parameters:
rtt - Estimated roundtrip distance
nid - NodeId of new node
newguid - Guid of new node

route_to_root

public NodeId route_to_root(int[] dest_digits,
                            boolean exact,
                            boolean prefix,
                            int[] digit)
Route to the root of the tree for dest_digits, assuming that the first digit [0] - 1 digits have already been accounted for, and return the next node in the routing path.
Parameters:
dest_digits - the digits of the destination GUID
exact - whether this should be an exact match; if this parameter is true, the function will return null if there is no such node.
digit - the digit to start routing from
Returns:
the next node in the routing path, if any; return null if there is no such node and return _self_node_id if the current node is the deterministic root

_route_to_root

public RouteEntry _route_to_root(int[] dest_digits,
                                 boolean exact,
                                 boolean prefix,
                                 int[] digit)

surrogate

public NodeId surrogate(int[] dest_digits,
                        int dest_digit,
                        int hop)
Find the surrogate for an empty routing table entry.
Parameters:
dest_digits - The array of ints representing the destination guid
dest_digit - The digit value that points to an empty entry
hop - Which hop are we looking for the surrogate route on
Returns:
null if we are definitely the surrogate, and the NodeId of the next person to ask if we cannot tell from this hop yet.

_surrogate

public RouteEntry _surrogate(int[] dest_digits,
                             int dest_digit,
                             int hop)

nextSurrogate

public NodeId nextSurrogate(HashSet ignoredNodes,
                            SecureHash selfguid)
method that calculates the NEXT best surrogate hop other than the current node for ANY key/GUID. Assumes we're currently the best surrogate, then looks for the next surrogate from the right most digit to the left. The first non-null value in the table found would be the next hop to the next surrogate. We also make sure that we take in a HashSet, and ignore those nodes when searching for the next surrogate. This is to avoid binary loops, where A and B think the other is the next best surrogate for an object. For example: A=1234, B=1235 for GUID=1233, where no other nodes match prefix of 123X.
Returns:
NodeId of the next best surrogate hop if we were not around

addSelf

public boolean addSelf(SecureHash self)

digits

public static int[] digits(SecureHash h)

toString

public String toString()
Overrides:
toString in class Object

toShortString

public String toShortString()

printGuid

public static String printGuid(SecureHash x)

serialize

public void serialize(OutputBuffer buffer)
Description copied from interface: QuickSerializable
Add the object to the buffer.
Specified by:
serialize in interface QuickSerializable
Following copied from interface: ostore.util.QuickSerializable
Parameters:
buffer - the output buffer to add the object to

get_node_map

public Map get_node_map()

get_table

public RouteEntry[][] get_table()

get_self_node_id

public NodeId get_self_node_id()

get_removed_nodes

public LinkedList get_removed_nodes()

pw_update

public void pw_update(DeltaMsg pdrm)
Update the Patchwork statistics to RoutingTable, given the newest delta ent out by Patchwork model. At current time, we only update loss_rate to RoutingTable.
Returns:
LinkedList of messages to be sent by whoever calls this

setSink

protected void setSink(SinkIF sink)