bamboo.router
Class Router

java.lang.Object
  bamboo.util.StandardStage
      bamboo.router.Router

All Implemented Interfaces:

EventHandlerIF, SingleThreadedEventHandlerIF

public class Router
extends StandardStage
implements SingleThreadedEventHandlerIF

The routing and dynamic ring maintenance code for Bamboo.

Version:

$Id: Router.java,v 1.110 2005/03/02 23:37:08 srhea Exp $

Author:

Sean C. Rhea

Nested Class Summary

protected static class	Router.AppData
protected static class	Router.ApplicationInfo
static class	Router.DuplicateApplicationException Thrown if registerApplication(long, bamboo.util.Curry.Thunk2, bamboo.util.Curry.Thunk2, bamboo.util.Curry.Thunk2, bamboo.util.Curry.Thunk6, bamboo.util.Curry.Thunk6) is called with a duplicate application ID.
static interface	Router.LookupCb
protected static interface	Router.NetMsgResultCB
protected class	Router.PartitionCheckCB
protected static class	Router.PendingLookupInfo
protected class	Router.PeriodicPingCB
protected class	Router.ProbePingCB
protected class	Router.RecursiveRouteCB
protected class	Router.SecondChancePingCB

Field Summary

protected Map<Long,Router.ApplicationInfo>	apps
protected static int[]	bit_select
protected int	DIGIT_BITS
protected int	DIGIT_VALUES The number of possible distinct values for each digit.
protected Set<ostore.util.NodeId>	down_nodes
protected int	down_nodes_cap
protected int	far_rt_alarm_period
protected Runnable	farRoutingTableAlarm
protected LinkedList<ostore.util.NodeId>	gateways
protected int	GUID_BITS
protected int	GUID_DIGITS The number of digits in each identifier.
protected boolean	ignore_possibly_down
protected boolean	immediate_join
protected boolean	initialized
protected static Map<ostore.util.NodeId,Router>	instances
protected Curry.Thunk3<Integer,Integer,Integer>	joinAlarm
protected Map<NeighborInfo,Double>	latency_map
protected LeafSet	leaf_set
protected int	leaf_set_size
protected Runnable	leafSetAlarm
protected LocationCache	location_cache
protected int	lookup_rt_alarm_period
protected Runnable	lookupRoutingTableAlarm
protected Curry.Thunk1<BigInteger>	lookupTimeout
protected int	ls_alarm_period
protected BigInteger	MODULUS The modulus of the ring of identifiers.
protected int[]	my_digits
protected BigInteger	my_guid
protected NeighborInfo	my_neighbor_info
protected int	near_rt_alarm_period
protected Runnable	nearRoutingTableAlarm
protected boolean	no_rexmit_routes
protected int	partition_check_alarm_period
protected Runnable	partitionCheckAlarm
protected boolean	pastry_mode
protected Map<BigInteger,Router.PendingLookupInfo>	pending_lookups
protected int	periodic_ping_period
protected Set<NeighborInfo>	periodic_pings
protected static int	PING_ITER
protected Runnable	pingAlarm
protected Set<NeighborInfo>	pings_in_flight
protected boolean	PNS
protected Map<NeighborInfo,Long>	possibly_down
protected Random	rand
protected Runnable	ready
protected Set<NeighborInfo>	reverse_rt
protected RoutingTable	rt
protected long	start_time_ms
protected LinkedList<QueueElementIF>	waitq

Fields inherited from class bamboo.util.StandardStage

acore, classifier, DEBUG, event_types, inb_msg_types, logger, my_node_id, my_sink, outb_msg_types, sim_running

Constructor Summary

Router()

Method Summary

protected void	add_to_down_nodes(ostore.util.NodeId n) Deprecated.
protected boolean	add_to_ls_ping_time(NeighborInfo ni, double rtt_ms)
protected void	add_to_ls(NeighborInfo ni)
protected void	add_to_rrt(NeighborInfo ni)
protected boolean	add_to_rt_ping_time(NeighborInfo ni, double rtt_ms)
protected void	add_to_rt(NeighborInfo ni)
static long	app_id(Class clazz) Deprecated. Use the applicationID(java.lang.Class) function instead.
protected void	application_enqueue(SinkIF sink, QueueElementIF item)
static long	applicationID(Class clazz) Computes an app_id based on the class name for convenience.
BigInteger	calc_dist(BigInteger a, BigInteger b)
protected NeighborInfo	calc_next_hop(BigInteger guid, boolean use_lc)
protected int	config_get_seconds(ConfigDataIF config, String name, int default_value)
protected void	deliver(BigInteger src, BigInteger dest, ostore.util.NodeId is, long app_id, int tries, long wait_ms, long est_rtt_ms, ostore.util.QuickSerializable payload)
int	digitsPerID() The number of digits per identifier being used by this router.
protected int	est_hops_to_go(BigInteger guid, boolean use_lc)
protected void	generic_msg_failure(NeighborInfo ni, Runnable retry)
protected void	generic_msg_success(NeighborInfo ni)
protected void	handle_join_req(JoinReq req)
protected void	handle_join_resp(JoinResp resp)
protected void	handle_leaf_set_changed(LeafSetChanged msg)
protected void	handle_leaf_set_req(LeafSetReq req)
protected void	handle_lookup_resp_msg(LookupRespMsg resp)
protected void	handle_monitor_node_down(NeighborInfo ni)
protected void	handle_net_lat_resp(ostore.network.NetworkLatencyResp resp)
protected void	handle_net_msg_result(ostore.network.NetworkMessageResult result)
protected void	handle_route_continue(BambooRouteContinue req)
protected void	handle_route_init(BambooRouteInit req)
protected void	handle_route_msg(RouteMsg req)
protected void	handle_router_app_reg_req(BambooRouterAppRegReq req)
protected void	handle_routing_table_req(RoutingTableReq req)
protected void	handle_routing_table_resp(RoutingTableResp resp)
protected void	handle_rt_annc(RoutingNeighborAnnounce annc)
void	handleEvent(QueueElementIF item)
protected boolean	have_rtt_ms(NeighborInfo ni)
BigInteger	id() The identifier of this node.
void	init(ConfigDataIF config)
static Router	instance(ostore.util.NodeId nodeID) Returns the Router stage for a given Bamboo node.
void	lookup(BigInteger id, Router.LookupCb cb, Object user_data)
BigInteger	modulus() One larger than the largest identifier supported by the system.
protected void	notify_leaf_set_changed()
protected void	notify_leaf_set_changed(Router.ApplicationInfo onlyThisOne)
protected void	notify_reverse_routing_table_changed(BambooNeighborInfo[] added, BambooNeighborInfo[] removed)
protected void	notify_routing_table_changed(BambooNeighborInfo[] added, BambooNeighborInfo[] removed)
protected long	randomPeriod(int mean)
void	registerApplication(long id, Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> leafSetChanged, Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> routingTableChanged, Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> reverseRoutingTableChanged, Curry.Thunk6<BigInteger,BigInteger,ostore.util.NodeId,Long,Long,ostore.util.QuickSerializable> routeUpcall, Curry.Thunk6<BigInteger,BigInteger,ostore.util.NodeId,Long,Long,ostore.util.QuickSerializable> routeDeliver) Register an application (such as bamboo.dht.Dht) to use the Router.
protected boolean	remove_from_ls(NeighborInfo ni)
protected boolean	remove_from_rrt(NeighborInfo ni)
protected boolean	remove_from_rt(NeighborInfo ni)
void	routeContinue(BigInteger src, BigInteger dest, ostore.util.NodeId immediateSource, long applicationID, boolean intermediateUpcall, ostore.util.QuickSerializable payload) Coninue a routing operation after an upcall.
void	routeInit(BigInteger dest, long applicationID, boolean intermediateUpcall, ostore.util.QuickSerializable payload) Initiate a routing operation to dest.
protected double	rtt_ms(NeighborInfo ni)
protected void	send_ping(NeighborInfo ni)
protected void	set_initialized()
protected void	use_as_periodic_ping(NeighborInfo ni, ostore.network.NetworkMessage outb)
int	valuesPerDigit() The number of values per digit in each identifier being used by this router.
protected int	weighted_random_rt_level()

Methods inherited from class bamboo.util.StandardStage

BUG, BUG, BUG, config_get_boolean, config_get_double, config_get_int, config_get_string, configGetInt, destroy, dispatch, enqueue, handleEvents, lookup_stage, now_ms, timer_ms

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

instances

protected static Map<ostore.util.NodeId,Router> instances

apps

protected Map<Long,Router.ApplicationInfo> apps

MODULUS

protected BigInteger MODULUS

The modulus of the ring of identifiers. If you want to get at this value, get it from BambooRouterAppRegResp.

GUID_DIGITS

protected int GUID_DIGITS

The number of digits in each identifier. If you want to get at this value, get it from BambooRouterAppRegResp.

GUID_BITS

protected int GUID_BITS

DIGIT_VALUES

protected int DIGIT_VALUES

The number of possible distinct values for each digit. If you want to get at this value, get it from BambooRouterAppRegResp.

DIGIT_BITS

protected int DIGIT_BITS

PING_ITER

protected static final int PING_ITER

See Also:

Constant Field Values

PNS

protected boolean PNS

ignore_possibly_down

protected boolean ignore_possibly_down

no_rexmit_routes

protected boolean no_rexmit_routes

latency_map

protected Map<NeighborInfo,Double> latency_map

possibly_down

protected Map<NeighborInfo,Long> possibly_down

periodic_pings

protected Set<NeighborInfo> periodic_pings

my_guid

protected BigInteger my_guid

my_digits

protected int[] my_digits

my_neighbor_info

protected NeighborInfo my_neighbor_info

initialized

protected boolean initialized

waitq

protected LinkedList<QueueElementIF> waitq

location_cache

protected LocationCache location_cache

down_nodes

protected Set<ostore.util.NodeId> down_nodes

down_nodes_cap

protected int down_nodes_cap

immediate_join

protected boolean immediate_join

leaf_set

protected LeafSet leaf_set

leaf_set_size

protected int leaf_set_size

rt

protected RoutingTable rt

gateways

protected LinkedList<ostore.util.NodeId> gateways

rand

protected Random rand

periodic_ping_period

protected int periodic_ping_period

partition_check_alarm_period

protected int partition_check_alarm_period

ls_alarm_period

protected int ls_alarm_period

near_rt_alarm_period

protected int near_rt_alarm_period

far_rt_alarm_period

protected int far_rt_alarm_period

lookup_rt_alarm_period

protected int lookup_rt_alarm_period

pastry_mode

protected boolean pastry_mode

start_time_ms

protected long start_time_ms

reverse_rt

protected Set<NeighborInfo> reverse_rt

pingAlarm

protected Runnable pingAlarm

partitionCheckAlarm

protected Runnable partitionCheckAlarm

leafSetAlarm

protected Runnable leafSetAlarm

ready

protected Runnable ready

nearRoutingTableAlarm

protected Runnable nearRoutingTableAlarm

bit_select

protected static final int[] bit_select

farRoutingTableAlarm

protected Runnable farRoutingTableAlarm

lookupRoutingTableAlarm

protected Runnable lookupRoutingTableAlarm

joinAlarm

protected Curry.Thunk3<Integer,Integer,Integer> joinAlarm

pings_in_flight

protected Set<NeighborInfo> pings_in_flight

pending_lookups

protected Map<BigInteger,Router.PendingLookupInfo> pending_lookups

lookupTimeout

protected Curry.Thunk1<BigInteger> lookupTimeout

Constructor Detail

Router

public Router()
       throws Exception

Throws:

Exception

Method Detail

instance

public static Router instance(ostore.util.NodeId nodeID)

Returns the Router stage for a given Bamboo node.

app_id

public static final long app_id(Class clazz)

Deprecated. Use the applicationID(java.lang.Class) function instead.

Computes an app_id based on the class name for convenience.

applicationID

public static final long applicationID(Class clazz)

Computes an app_id based on the class name for convenience.

registerApplication

public void registerApplication(long id,
                                Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> leafSetChanged,
                                Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> routingTableChanged,
                                Curry.Thunk2<BambooNeighborInfo[],BambooNeighborInfo[]> reverseRoutingTableChanged,
                                Curry.Thunk6<BigInteger,BigInteger,ostore.util.NodeId,Long,Long,ostore.util.QuickSerializable> routeUpcall,
                                Curry.Thunk6<BigInteger,BigInteger,ostore.util.NodeId,Long,Long,ostore.util.QuickSerializable> routeDeliver)
                         throws Router.DuplicateApplicationException

Register an application (such as bamboo.dht.Dht) to use the Router.

Parameters:

id - A value to identify this application in route messages sent across the network.

leafSetChanged - Called when the leaf set changes. The first array is the new predecessor list; the second is the new successor list.

routingTableChanged - Called when the routing table changes. The first array is the nodes added to the routing table; the second is those removed from the routing table.

reverseRoutingTableChanged - Called when we are added to or removed from some other node's routing table. The first array is the nodes added to the routing table; the second is those removed from the routing table.

routeUpcall - Called when a message is routed through this node, and the source specified that it should upcall at nodes that are not the root of the destination ID. The arguments are source ID, destination ID, immediate source IP:port, the queuing time before the message was forwarded, the estimated round trip time from the immediate source to this node, and the payload.

routeDeliver - Called when we are the root for a route message. The arguments are source ID, destination ID, immediate source IP:port, the queuing time before the message was forwarded, the estimated round trip time from the immediate source to this node, and the payload.

Throws:

Router.DuplicateApplicationException - if registerApplication has already been called with this id

id

public BigInteger id()

The identifier of this node.

modulus

public BigInteger modulus()

One larger than the largest identifier supported by the system.

digitsPerID

public int digitsPerID()

The number of digits per identifier being used by this router.

valuesPerDigit

public int valuesPerDigit()

The number of values per digit in each identifier being used by this router.

routeInit

public void routeInit(BigInteger dest,
                      long applicationID,
                      boolean intermediateUpcall,
                      ostore.util.QuickSerializable payload)

Initiate a routing operation to dest. Place the message to be sent in payload. To receive the message, the node responsible for dest must have registered an application (see registerApplication) with the given applicationID. If intermediateUpcall is true, a the routeUpcall function object given in that call to registerApplication will be called on each intermediate node in the path. To continue the routing operation, that node must call routeContinue. Finally, the routeDeliver function object given in the call to registerApplication will be called once the message reaches the node responsible for dest.

routeContinue

public void routeContinue(BigInteger src,
                          BigInteger dest,
                          ostore.util.NodeId immediateSource,
                          long applicationID,
                          boolean intermediateUpcall,
                          ostore.util.QuickSerializable payload)

Coninue a routing operation after an upcall. See the comments for routeInit(java.math.BigInteger, long, boolean, ostore.util.QuickSerializable) for more information.

config_get_seconds

protected int config_get_seconds(ConfigDataIF config,
                                 String name,
                                 int default_value)

init

public void init(ConfigDataIF config)
          throws Exception

Specified by:

init in interface EventHandlerIF

Overrides:

init in class StandardStage

Throws:

Exception

handleEvent

public void handleEvent(QueueElementIF item)

Specified by:

handleEvent in interface EventHandlerIF

Overrides:

handleEvent in class StandardStage

handle_net_msg_result

protected void handle_net_msg_result(ostore.network.NetworkMessageResult result)

randomPeriod

protected long randomPeriod(int mean)

use_as_periodic_ping

protected void use_as_periodic_ping(NeighborInfo ni,
                                    ostore.network.NetworkMessage outb)

generic_msg_success

protected void generic_msg_success(NeighborInfo ni)

generic_msg_failure

protected void generic_msg_failure(NeighborInfo ni,
                                   Runnable retry)

handle_rt_annc

protected void handle_rt_annc(RoutingNeighborAnnounce annc)

handle_monitor_node_down

protected void handle_monitor_node_down(NeighborInfo ni)

handle_leaf_set_req

protected void handle_leaf_set_req(LeafSetReq req)

handle_leaf_set_changed

protected void handle_leaf_set_changed(LeafSetChanged msg)

handle_router_app_reg_req

protected void handle_router_app_reg_req(BambooRouterAppRegReq req)

application_enqueue

protected void application_enqueue(SinkIF sink,
                                   QueueElementIF item)

deliver

protected void deliver(BigInteger src,
                       BigInteger dest,
                       ostore.util.NodeId is,
                       long app_id,
                       int tries,
                       long wait_ms,
                       long est_rtt_ms,
                       ostore.util.QuickSerializable payload)

handle_route_continue

protected void handle_route_continue(BambooRouteContinue req)

handle_route_init

protected void handle_route_init(BambooRouteInit req)

handle_route_msg

protected void handle_route_msg(RouteMsg req)

set_initialized

protected void set_initialized()

weighted_random_rt_level

protected int weighted_random_rt_level()

handle_lookup_resp_msg

protected void handle_lookup_resp_msg(LookupRespMsg resp)

handle_routing_table_req

protected void handle_routing_table_req(RoutingTableReq req)

handle_routing_table_resp

protected void handle_routing_table_resp(RoutingTableResp resp)

notify_routing_table_changed

protected void notify_routing_table_changed(BambooNeighborInfo[] added,
                                            BambooNeighborInfo[] removed)

notify_reverse_routing_table_changed

protected void notify_reverse_routing_table_changed(BambooNeighborInfo[] added,
                                                    BambooNeighborInfo[] removed)

notify_leaf_set_changed

protected void notify_leaf_set_changed()

notify_leaf_set_changed

protected void notify_leaf_set_changed(Router.ApplicationInfo onlyThisOne)

handle_join_req

protected void handle_join_req(JoinReq req)

handle_join_resp

protected void handle_join_resp(JoinResp resp)

send_ping

protected void send_ping(NeighborInfo ni)

handle_net_lat_resp

protected void handle_net_lat_resp(ostore.network.NetworkLatencyResp resp)

add_to_ls

protected void add_to_ls(NeighborInfo ni)

add_to_ls_ping_time

protected boolean add_to_ls_ping_time(NeighborInfo ni,
                                      double rtt_ms)

remove_from_ls

protected boolean remove_from_ls(NeighborInfo ni)

add_to_rt

protected void add_to_rt(NeighborInfo ni)

add_to_rt_ping_time

protected boolean add_to_rt_ping_time(NeighborInfo ni,
                                      double rtt_ms)

remove_from_rt

protected boolean remove_from_rt(NeighborInfo ni)

add_to_rrt

protected void add_to_rrt(NeighborInfo ni)

remove_from_rrt

protected boolean remove_from_rrt(NeighborInfo ni)

have_rtt_ms

protected boolean have_rtt_ms(NeighborInfo ni)

rtt_ms

protected double rtt_ms(NeighborInfo ni)

calc_next_hop

protected NeighborInfo calc_next_hop(BigInteger guid,
                                     boolean use_lc)

est_hops_to_go

protected int est_hops_to_go(BigInteger guid,
                             boolean use_lc)

calc_dist

public BigInteger calc_dist(BigInteger a,
                            BigInteger b)

add_to_down_nodes

protected void add_to_down_nodes(ostore.util.NodeId n)

Deprecated.

The existence of this function is a total hack to get the PIER people through a paper deadline. It will disappear shortly thereafter. That said, given the identifier of a node which is running in this JVMand a guid, it returns whether the node is the owner of the guid.

lookup

public void lookup(BigInteger id,
                   Router.LookupCb cb,
                   Object user_data)