ostore.tapestry.impl
Class Router

java.lang.Object
  |
  +--ostore.tapestry.impl.Router
All Implemented Interfaces:
EventHandlerIF, ProfilableIF, SingleThreadedEventHandlerIF

public class Router
extends Object
implements SingleThreadedEventHandlerIF, EventHandlerIF, ProfilableIF

Handles the routing functions of Tapestry. TODO: The back pointers are currently maintained in sorted linked lists which are sorted by distance. All the elements in a list have the same guid, and the lists are stored in a map indexed by those guids. I don't have to tell you that this is inefficient, but I can't get Java's TreeSet class to replace the lists. I think it has something to do with what the Javadocs call compare being "compatible with" equals. I don't know. In any case, the backpointers will need to be stored on disk at some point, not all in memory, so this will all need an overhauling then. --srhea, 12/18/2001

Version:
$Id: Router.java,v 1.144 2003/06/20 23:04:49 strib Exp $
Author:
Sean C. Rhea and Ben Y. Zhao

Inner Class Summary
 class Router.MsgTime
          A Comparator used to compare the enqueue time for message in multicast queue.
static class Router.ObjectMap
           
 
Field Summary
static byte[] _match_bytes
           
static boolean FRLS
          Boolean flag that turns FRLS mode on or off.
static int LOCAL_OPT_BACKUPS
          The default number of backups to publish to while optimizing
static int LOCAL_OPT_HOPS
          The default initial time-to-live for the local optimizations that only get forwarded for a few hops.
static int LOCAL_OPT_NEAREST
          The default number of links on the same level to publish to while optimizing
static int LOCAL_OPT_PUBLISH_ALL_LINKS
           
static int LOCAL_OPT_PUBLISH_BACKUP
          The following flags represent flags for local optimizations during publishing.
static int LOCAL_OPT_PUBLISH_LOCAL_MISROUTE
           
static int LOCAL_OPT_THRESHOLD_FACTOR
          The factor by which to judge whether or not a link is too long to take (i.e.
static int LOCALROOTOBJS
           
static boolean MULTICAST
          The constant that defines whether multicast is turned on or not.
static int MULTICAST_QUEUE_SIZE
          The size of the multicast convergence queue, which we use to drop duplicate messages which are produced by the multicast routing mechanism.
static int THRESHOLD_DEAD
          Threshold for determining when a node is "dead." If a node's updated link loss rate is rated above THRESHOLD_DEAD for this current period, then it is "dead." Config name = inactive_node_threshold
static int THRESHOLD_FRLS
          The maximum failure rate tolerable that defines "reachable" in our FRLS scheme.
static int THRESHOLD_MULTICAST
          The constant that defines when multicast is triggered for a message.
static int THRESHOLD_REPLACE
          If a node has been "dead/inactive" for a consecutive number of periods equal or greater than THRESHOLD_REPLACE, it is removed from the routing table and we try to replace it using repair algorithms.
 
Constructor Summary
Router()
           
 
Method Summary
static void BUG(String msg)
           
 void destroy()
           
static void dumpRevpointers(HashMap revs, int level)
           
 ChannelHandler get_channel_handler()
           
 RoutingTable get_routing_table()
           
 SecureHash get_self_guid()
           
 NodeId get_self_node_id()
           
 SinkIF get_sink()
           
static Set getRevpointers(Map revs, int level)
           
static int guidCompare(SecureHash one, SecureHash two)
          Compare two guids and return the index (starting with 0) of the first differing digit.
protected  void handle_bloom_wrapper(BloomWrapper wrapper)
           
protected  void handle_icmp_ping_msg(ostore.tapestry.channel.ICMPPingMsg msg)
           
protected  void handle_publish_msg(PublishMsg msg)
           
protected  void handle_republish_request(RepublishRequestMsg msg)
           
protected  void handle_route_msg(RouteMsg msg)
           
 void handle_route_obj_dest_msg(RouteObjDestMsg msg)
           
protected  void handle_route_obj_root_msg(RouteObjRootMsg msg)
           
protected  void handle_stages_init_signal()
          For use in derived classes.
protected  void handle_tapestry_locate_msg(TapestryLocateMsg msg)
           
protected  void handle_tapestry_prefix_route_msg(TapestryPrefixRouteMsg msg)
           
protected  void handle_tapestry_publish_msg(TapestryPublishMsg msg)
           
protected  void handle_tapestry_route_msg(TapestryRouteMsg msg)
           
protected  void handle_tapestry_unpublish_msg(TapestryUnpublishMsg msg)
           
 void handleEvent(QueueElementIF item)
           
 void handleEvents(QueueElementIF[] items)
           
 void init(ConfigDataIF config)
           
 boolean isDuplicate(QueueElementIF item)
           
 int profileSize()
           
protected  void publish(SecureHash src, SecureHash guid, TapestryTag ttag, boolean publish, NodeId lasthop, int qos)
           
protected  void publish(SecureHash src, SecureHash guid, TapestryTag ttag, boolean publish, NodeId lasthop, int qos, int local_opts, int local_opts_ttl)
           
protected  boolean route_to_dest(SecureHash guid, SecureHash src, TapestryQuery query, TapestryQueryState state, QuickSerializable user_data, int user_data_length, InputBuffer user_data_buffer, int hopInit, int TTL, int qos)
          Method to check local pointers for an object, and if found, sends RouteObjDest messages to the actual locations of the objects.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LOCALROOTOBJS

public static final int LOCALROOTOBJS

MULTICAST

public static boolean MULTICAST
The constant that defines whether multicast is turned on or not. This value has no effect, and the run time value is determined by config scripts. If it is not found in the config files, it's set to false by default. Config name = ft_multicast

THRESHOLD_MULTICAST

public static int THRESHOLD_MULTICAST
The constant that defines when multicast is triggered for a message. If the loss rate is greater than THRESHOLD_MULTICAST*100, then the message is multicast across the links. Config name = multicast_threshold

MULTICAST_QUEUE_SIZE

public static int MULTICAST_QUEUE_SIZE
The size of the multicast convergence queue, which we use to drop duplicate messages which are produced by the multicast routing mechanism. Config name = multicast_queue_size

FRLS

public static boolean FRLS
Boolean flag that turns FRLS mode on or off. This is set here by default, and can only be turned off by specifying the config argument "disable_frls" to true. Config name = disable_frls

THRESHOLD_FRLS

public static int THRESHOLD_FRLS
The maximum failure rate tolerable that defines "reachable" in our FRLS scheme. FRLS is determined by scanning according to link latency and picking the first node with loss rate less than THRESHOLD_FRLS. Config name = frls_threshold

THRESHOLD_DEAD

public static int THRESHOLD_DEAD
Threshold for determining when a node is "dead." If a node's updated link loss rate is rated above THRESHOLD_DEAD for this current period, then it is "dead." Config name = inactive_node_threshold

THRESHOLD_REPLACE

public static int THRESHOLD_REPLACE
If a node has been "dead/inactive" for a consecutive number of periods equal or greater than THRESHOLD_REPLACE, it is removed from the routing table and we try to replace it using repair algorithms. Config name = replace_node_threshold

_match_bytes

public static final byte[] _match_bytes

LOCAL_OPT_PUBLISH_BACKUP

public static final int LOCAL_OPT_PUBLISH_BACKUP
The following flags represent flags for local optimizations during publishing. Which optimizations to use are indicated by the local_opts field in TapestryPublishMsg. The supported operations are described in TapestryPublishMsg.

LOCAL_OPT_PUBLISH_ALL_LINKS

public static final int LOCAL_OPT_PUBLISH_ALL_LINKS

LOCAL_OPT_PUBLISH_LOCAL_MISROUTE

public static final int LOCAL_OPT_PUBLISH_LOCAL_MISROUTE

LOCAL_OPT_BACKUPS

public static int LOCAL_OPT_BACKUPS
The default number of backups to publish to while optimizing

LOCAL_OPT_NEAREST

public static int LOCAL_OPT_NEAREST
The default number of links on the same level to publish to while optimizing

LOCAL_OPT_THRESHOLD_FACTOR

public static int LOCAL_OPT_THRESHOLD_FACTOR
The factor by which to judge whether or not a link is too long to take (i.e. if it is this much bigger than the last link taken)

LOCAL_OPT_HOPS

public static int LOCAL_OPT_HOPS
The default initial time-to-live for the local optimizations that only get forwarded for a few hops.
Constructor Detail

Router

public Router()
Method Detail

isDuplicate

public boolean isDuplicate(QueueElementIF item)

BUG

public static final void BUG(String msg)

init

public void init(ConfigDataIF config)
          throws Exception
Specified by:
init in interface EventHandlerIF

destroy

public void destroy()
             throws Exception
Specified by:
destroy in interface EventHandlerIF

profileSize

public int profileSize()
Specified by:
profileSize in interface ProfilableIF

handle_stages_init_signal

protected void handle_stages_init_signal()
For use in derived classes.

dumpRevpointers

public static void dumpRevpointers(HashMap revs,
                                   int level)

getRevpointers

public static Set getRevpointers(Map revs,
                                 int level)

handle_icmp_ping_msg

protected void handle_icmp_ping_msg(ostore.tapestry.channel.ICMPPingMsg msg)

handle_tapestry_route_msg

protected void handle_tapestry_route_msg(TapestryRouteMsg msg)

handle_tapestry_prefix_route_msg

protected void handle_tapestry_prefix_route_msg(TapestryPrefixRouteMsg msg)

handle_route_msg

protected void handle_route_msg(RouteMsg msg)

handle_tapestry_publish_msg

protected void handle_tapestry_publish_msg(TapestryPublishMsg msg)

handle_tapestry_unpublish_msg

protected void handle_tapestry_unpublish_msg(TapestryUnpublishMsg msg)

handle_republish_request

protected void handle_republish_request(RepublishRequestMsg msg)

handle_publish_msg

protected void handle_publish_msg(PublishMsg msg)

handle_bloom_wrapper

protected void handle_bloom_wrapper(BloomWrapper wrapper)

handle_tapestry_locate_msg

protected void handle_tapestry_locate_msg(TapestryLocateMsg msg)

handle_route_obj_root_msg

protected void handle_route_obj_root_msg(RouteObjRootMsg msg)

handle_route_obj_dest_msg

public void handle_route_obj_dest_msg(RouteObjDestMsg msg)

handleEvent

public void handleEvent(QueueElementIF item)
                 throws EventHandlerException
Specified by:
handleEvent in interface EventHandlerIF

route_to_dest

protected boolean route_to_dest(SecureHash guid,
                                SecureHash src,
                                TapestryQuery query,
                                TapestryQueryState state,
                                QuickSerializable user_data,
                                int user_data_length,
                                InputBuffer user_data_buffer,
                                int hopInit,
                                int TTL,
                                int qos)
                         throws QSException
Method to check local pointers for an object, and if found, sends RouteObjDest messages to the actual locations of the objects.
Parameters:
guid - The GUID of the object searched for
hopInit - The # of hops taken to get here from the query source
Returns:
Boolean on whether the query is satisfied. If true, it means we're done.

guidCompare

public static int guidCompare(SecureHash one,
                              SecureHash two)
Compare two guids and return the index (starting with 0) of the first differing digit.

publish

protected void publish(SecureHash src,
                       SecureHash guid,
                       TapestryTag ttag,
                       boolean publish,
                       NodeId lasthop,
                       int qos)

publish

protected void publish(SecureHash src,
                       SecureHash guid,
                       TapestryTag ttag,
                       boolean publish,
                       NodeId lasthop,
                       int qos,
                       int local_opts,
                       int local_opts_ttl)

handleEvents

public void handleEvents(QueueElementIF[] items)
                  throws EventHandlerException
Specified by:
handleEvents in interface EventHandlerIF

get_self_node_id

public NodeId get_self_node_id()

get_self_guid

public SecureHash get_self_guid()

get_sink

public SinkIF get_sink()

get_channel_handler

public ChannelHandler get_channel_handler()

get_routing_table

public RoutingTable get_routing_table()