Copyright © 2013-2015 Zuse Institute Berlin
Version: $Id$
Behaviours: rt_beh.
Authors: Magnus Mueller (mamuelle@informatik.hu-berlin.de), Jens Fischer (jensvfischer@gmail.com).
Flexible routing table. Two flexible routing tables (FRTs) are implemented, FRT-chord and grouped FRT-chord (GFRT). The functions specific to these two implementations can be found at the end of this file (seperated by ifdefs).
client_key() = [unicode_char()]
custom_info() = undefined | term()
custom_message() = {get_rt, SourcePID :: comm:mypid()} | {get_rt_reply, RT :: rt()} | {trigger_random_lookup} | {rt_get_node, From :: comm:mypid()} | {rt_learn_node, NewNode :: mynode()} | {rt_get_neighbor, From :: comm:mypid()} | {rt_learn_neighbor, NewNode :: mynode()}
entry_type() = normal | source | sticky
abstract datatype: external_rt()
key() = rt_chord:key()
mynode() = {Id :: key(), IdVersion :: non_neg_integer(), DHTNodePid :: comm:mypid(), RTLoopPid :: comm:mypid() | none}
abstract datatype: rt()
rt_entry() = #rt_entry{node = undefined | mynode(), type = undefined | entry_type(), adjacent_fingers = {key() | undefined, key() | undefined}, custom = custom_info()}
rt_entry_info_t() = undefined
unicode_char() = 0..55295 | 57344..65533 | 65536..1114111
activate/1 | Activate the routing table. |
allowed_nodes/1 | |
check/5 | Notifies the dht_node and failure detector if the routing table changed. |
check/6 | Notifies the dht_node if the (external) routing table changed. |
check_config/0 | Checks whether config parameters of the rt_frtchord process exist and are valid. |
check_rt_integrity/1 | Check that all entries in an rt are well connected by their adjacent fingers. |
check_well_connectedness/1 | Check that the adjacent fingers of a RT are building a ring. |
client_key_to_binary/1 | |
dump/1 | Dumps the RT state for output in the web interface. |
dump_to_csv/1 | Dump the routing table into a CSV string. |
empty_ext/1 | |
export_rt_to_dht_node/2 | |
filter_dead_node/3 | Removes dead nodes from the routing table (rely on periodic stabilization here). |
frt_check_config/0 | Checks whether config parameters of the rt_frtchord/rt_gfrtchord process exist and are valid. |
get_key_segment/1 | |
get_random_in_interval/1 | Gets input similar to what intervals:get_bounds/1 returns and calculates a random key in this range. |
get_random_in_interval/2 | Gets input similar to what intervals:get_bounds/1 returns and calculates Count number of random keys in this range (duplicates may exist!). |
get_random_key_from_generator/3 | Generate a random key from the pdf as defined in (Nagao, Shudo, 2011) TODO I floor the key for now; the key generator should return ints, but returns float. |
get_random_node_id/0 | Generates a random node id, i.e. |
get_range/2 | Gets the number of keys in the interval (Begin, End]. |
get_replica_keys/1 | Returns the replicas of the given key. |
get_size/1 | Returns the size of the routing table. |
get_size_ext/1 | Returns the size of the external routing table. |
get_source_id/1 | Get the id of the source node. |
get_source_node/1 | Get the source node of a routing table. |
get_split_key/3 | Gets the key that splits the interval (Begin, End] so that the first interval will be (Num/Denom) * range(Begin, End). |
get_split_keys/3 | Splits the range between Begin and End into up to Parts equal parts and returning the according split keys. |
handle_custom_message/2 | Handle custom messages. |
handle_custom_message_inactive/2 | Trigger need to be resend here w/o queuing to avoid trace infestation. |
hash_key/1 | Hashes the key to the identifier space. |
init/0 | This function is called during the startup of the rt_loop process and is allowed to send trigger messages. |
init_stabilize/2 | Triggered by a new stabilization round, renews the routing table. |
n/0 | Returns the size of the address space. |
next_hop/3 | |
rt_entry_info/4 | |
succ/2 | Return the succ. |
to_list/1 | Converts the external representation of the routing table to a list in the order of the fingers, i.e. |
to_pid_list/1 | Returns the pids of the routing table entries. |
unwrap_message/2 | Unwrap lookup messages. |
update/3 | Updates the routing table due to a changed node ID, pred and/or succ. |
wrap_message/5 | Wrap lookup messages. |
client_key_to_binary(Key :: client_key()) -> binary()
init() -> ok
This function is called during the startup of the rt_loop process and is allowed to send trigger messages.
activate(Neighbors :: nodelist:neighborhood()) -> rt()
Activate the routing table. This function is called during the activation of the routing table process.
hash_key(Key :: client_key() | binary()) -> key()
Hashes the key to the identifier space.
get_random_node_id() -> key()
Generates a random node id, i.e. a random 128-bit number.
init_stabilize(Neighbors :: nodelist:neighborhood(), RT :: rt()) -> rt()
Triggered by a new stabilization round, renews the routing table. Check: - if node id didn't change, i.e. only preds/succs changed, update sticky entries - if node id changed, just renew the complete table and maybe tell known nodes that something changed (async and optimistic -> if they don't care, we don't care)
update(OldRT :: rt(), OldNeighbors :: nodelist:neighborhood(), NewNeighbors :: nodelist:neighborhood()) -> {trigger_rebuild, rt()} | {ok, rt()}
Updates the routing table due to a changed node ID, pred and/or succ. - We must rebuild the complete routing table when the source node id changed - If only the preds/succs changed, adapt the old routing table
filter_dead_node(RT :: rt(), DeadPid :: comm:mypid(), Reason :: fd:reason()) -> rt()
Removes dead nodes from the routing table (rely on periodic stabilization here).
to_pid_list(RT :: rt()) -> [comm:mypid()]
Returns the pids of the routing table entries.
get_size(Rt_t :: rt()) -> non_neg_integer()
Returns the size of the routing table.
get_size_ext(RT :: external_rt()) -> non_neg_integer()
Returns the size of the external routing table.
n() -> 340282366920938463463374607431768211456
Returns the size of the address space.
Gets the number of keys in the interval (Begin, End]. In the special case of Begin==End, the whole key range as specified by n/0 is returned.
get_split_key(Begin :: key(), End :: key() | 340282366920938463463374607431768211456, SplitFraction :: {Num :: non_neg_integer(), Denom :: pos_integer()}) -> key() | 340282366920938463463374607431768211456
Gets the key that splits the interval (Begin, End] so that the first interval will be (Num/Denom) * range(Begin, End). In the special case of Begin==End, the whole key range is split. Beware: SplitFactor must be in [0, 1]; the final key will be rounded down and may thus be Begin.
get_split_keys(Begin :: key(), End :: key() | 340282366920938463463374607431768211456, Parts :: pos_integer()) -> [key()]
Splits the range between Begin and End into up to Parts equal parts and returning the according split keys.
get_random_in_interval(SimpleI :: intervals:simple_interval2()) -> key()
Gets input similar to what intervals:get_bounds/1 returns and calculates a random key in this range. Fails with an exception if there is no key.
get_random_in_interval(SimpleI :: intervals:simple_interval2(), Count :: pos_integer()) -> [key(), ...]
Gets input similar to what intervals:get_bounds/1 returns and calculates Count number of random keys in this range (duplicates may exist!). Fails with an exception if there is no key.
Returns the replicas of the given key.
get_key_segment(Key :: key()) -> pos_integer()
dump(RT :: rt()) -> KeyValueList :: [{Index :: string(), Node :: string()}]
Dumps the RT state for output in the web interface.
dump_to_csv(RT :: rt()) -> [char()]
Dump the routing table into a CSV string
check_config() -> boolean()
Checks whether config parameters of the rt_frtchord process exist and are valid.
Generate a random key from the pdf as defined in (Nagao, Shudo, 2011) TODO I floor the key for now; the key generator should return ints, but returns float. It is currently unclear if this is a bug in the original paper by Nagao and Shudo. Using erlang:trunc/1 should be enough for flooring, as X >= 0
handle_custom_message_inactive(Msg :: custom_message(), MsgQueue :: msg_queue:msg_queue()) -> msg_queue:msg_queue()
Trigger need to be resend here w/o queuing to avoid trace infestation.
handle_custom_message(Message :: custom_message(), State :: rt_loop:state_active()) -> rt_loop:state_active() | unknown_event
Handle custom messages. The following messages can occur: - TODO explain messages
check(OldRT :: rt(), NewRT :: rt(), OldERT :: external_rt(), Neighbors :: nodelist:neighborhood(), ReportToFD :: boolean()) -> NewERT :: external_rt()
Notifies the dht_node and failure detector if the routing table changed. Provided for convenience (see check/5).
check(OldRT :: rt(), NewRT :: rt(), OldERT :: external_rt(), OldNeighbors :: nodelist:neighborhood(), NewNeighbors :: nodelist:neighborhood(), ReportToFD :: boolean()) -> NewERT :: external_rt()
Notifies the dht_node if the (external) routing table changed. Also updates the failure detector if ReportToFD is set. Note: the external routing table only changes if the internal RT has changed.
empty_ext(Neighbors :: nodelist:neighborhood()) -> external_rt()
next_hop(Neighbors :: nodelist:neighborhood(), ERT :: external_rt(), Id :: key()) -> succ | comm:mypid()
succ(ERT :: external_rt(), Neighbors :: nodelist:neighborhood()) -> comm:mypid()
Return the succ
export_rt_to_dht_node(RT :: rt(), Neighbors :: nodelist:neighborhood()) -> external_rt()
to_list(State :: dht_node_state:state()) -> [{Id :: key(), DHTPid :: comm:mypid()}]
Converts the external representation of the routing table to a list in the order of the fingers, i.e. first=succ, second=shortest finger, third=next longer finger,...
get_source_node(RT :: rt()) -> rt_entry()
Get the source node of a routing table
Get the id of the source node.
check_rt_integrity(RT :: rt()) -> boolean()
Check that all entries in an rt are well connected by their adjacent fingers
wrap_message(Key :: key(), Msg :: comm:message(), MyERT :: external_rt(), Neighbors :: nodelist:neighborhood(), Hops :: non_neg_integer()) -> {'$wrapped', mynode(), comm:message()} | comm:message()
Wrap lookup messages. For node learning in lookups, a lookup message is wrapped with the global Pid of the
unwrap_message(Msg :: comm:message(), State :: dht_node_state:state()) -> comm:message()
Unwrap lookup messages. The Pid is retrieved and the Pid of the current node is sent to the retrieved Pid
check_well_connectedness(RT :: rt()) -> boolean()
Check that the adjacent fingers of a RT are building a ring
allowed_nodes(RT :: rt()) -> [rt_entry()]
rt_entry_info(Node :: mynode(), Type :: entry_type(), PredId :: key(), SuccId :: key()) -> rt_entry_info_t()
frt_check_config() -> boolean()
Checks whether config parameters of the rt_frtchord/rt_gfrtchord process exist and are valid.
Generated by EDoc, Sep 11 2020, 15:25:01.