tapestry.impl
Class Router

java.lang.Object
  |
  +--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.3 2004/05/06 22:28:19 hweather Exp $

Author:

Sean C. Rhea and Ben Y. Zhao and Jeremy Stribling

Nested 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. if it is this much bigger than the last link taken)
static int	LOCALOBJS
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."
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_icmp_ping_msg(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_cont(GetPtrResp gpr, RouteObjRootMsg 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_cont(GetPtrResp gpr, TapestryLocateMsg msg)
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_cont(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, LinkedList l) Method to check local pointers for an object, and if found, sends RouteObjDest messages to the actual locations of the objects.
protected void	route_to_dest(SecureHash guid, Object userData)

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

See Also:

Constant Field Values

LOCALOBJS

public static final int LOCALOBJS

See Also:

Constant Field Values

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.

See Also:

Constant Field Values

LOCAL_OPT_PUBLISH_ALL_LINKS

public static final int LOCAL_OPT_PUBLISH_ALL_LINKS

See Also:

Constant Field Values

LOCAL_OPT_PUBLISH_LOCAL_MISROUTE

public static final int LOCAL_OPT_PUBLISH_LOCAL_MISROUTE

See Also:

Constant Field Values

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

Exception

destroy

public void destroy()
             throws Exception

Specified by:

destroy in interface EventHandlerIF

Exception

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(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_tapestry_locate_msg

protected void handle_tapestry_locate_msg(TapestryLocateMsg msg)

handle_tapestry_locate_msg_cont

protected void handle_tapestry_locate_msg_cont(GetPtrResp gpr,
                                               TapestryLocateMsg msg)

handle_route_obj_root_msg

protected void handle_route_obj_root_msg(RouteObjRootMsg msg)

handle_route_obj_root_msg_cont

protected void handle_route_obj_root_msg_cont(GetPtrResp gpr,
                                              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

EventHandlerException

route_to_dest

protected void route_to_dest(SecureHash guid,
                             Object userData)

route_to_dest_cont

protected boolean route_to_dest_cont(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,
                                     LinkedList l)
                              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.

QSException

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

EventHandlerException

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