Module rt_frt

Flexible routing table.

Copyright © 2013-2015 Zuse Institute Berlin

Version: $Id$

Behaviours: rt_beh.

Authors: Magnus Mueller (mamuelle@informatik.hu-berlin.de), Jens Fischer (jensvfischer@gmail.com).

Description

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

Data Types

client_key()

client_key() = [unicode_char()]

custom_info()

custom_info() = undefined | term()

custom_message()

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

entry_type() = normal | source | sticky

external_rt()

abstract datatype: external_rt()

key()

key() = rt_chord:key()

mynode()

mynode() = 
    {Id :: key(),
     IdVersion :: non_neg_integer(),
     DHTNodePid :: comm:mypid(),
     RTLoopPid :: comm:mypid() | none}

rt()

abstract datatype: rt()

rt_entry()

rt_entry() = 
    #rt_entry{node = undefined | mynode(),
              type = undefined | entry_type(),
              adjacent_fingers =
                  {key() | undefined, key() | undefined},
              custom = custom_info()}

rt_entry_info_t()

rt_entry_info_t() = undefined

unicode_char()

unicode_char() = 0..55295 | 57344..65533 | 65536..1114111

Function Index

activate/1Activate the routing table.
allowed_nodes/1
check/5Notifies the dht_node and failure detector if the routing table changed.
check/6Notifies the dht_node if the (external) routing table changed.
check_config/0Checks whether config parameters of the rt_frtchord process exist and are valid.
check_rt_integrity/1Check that all entries in an rt are well connected by their adjacent fingers.
check_well_connectedness/1Check that the adjacent fingers of a RT are building a ring.
client_key_to_binary/1
dump/1Dumps the RT state for output in the web interface.
dump_to_csv/1Dump the routing table into a CSV string.
empty_ext/1
export_rt_to_dht_node/2
filter_dead_node/3Removes dead nodes from the routing table (rely on periodic stabilization here).
frt_check_config/0Checks whether config parameters of the rt_frtchord/rt_gfrtchord process exist and are valid.
get_key_segment/1
get_random_in_interval/1Gets input similar to what intervals:get_bounds/1 returns and calculates a random key in this range.
get_random_in_interval/2Gets 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/3Generate 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/0Generates a random node id, i.e.
get_range/2Gets the number of keys in the interval (Begin, End].
get_replica_keys/1Returns the replicas of the given key.
get_size/1Returns the size of the routing table.
get_size_ext/1Returns the size of the external routing table.
get_source_id/1Get the id of the source node.
get_source_node/1Get the source node of a routing table.
get_split_key/3Gets the key that splits the interval (Begin, End] so that the first interval will be (Num/Denom) * range(Begin, End).
get_split_keys/3Splits the range between Begin and End into up to Parts equal parts and returning the according split keys.
handle_custom_message/2Handle custom messages.
handle_custom_message_inactive/2Trigger need to be resend here w/o queuing to avoid trace infestation.
hash_key/1Hashes the key to the identifier space.
init/0This function is called during the startup of the rt_loop process and is allowed to send trigger messages.
init_stabilize/2Triggered by a new stabilization round, renews the routing table.
n/0Returns the size of the address space.
next_hop/3
rt_entry_info/4
succ/2Return the succ.
to_list/1Converts the external representation of the routing table to a list in the order of the fingers, i.e.
to_pid_list/1Returns the pids of the routing table entries.
unwrap_message/2Unwrap lookup messages.
update/3Updates the routing table due to a changed node ID, pred and/or succ.
wrap_message/5Wrap lookup messages.

Function Details

client_key_to_binary/1

client_key_to_binary(Key :: client_key()) -> binary()

init/0

init() -> ok

This function is called during the startup of the rt_loop process and is allowed to send trigger messages.

activate/1

activate(Neighbors :: nodelist:neighborhood()) -> rt()

Activate the routing table. This function is called during the activation of the routing table process.

hash_key/1

hash_key(Key :: client_key() | binary()) -> key()

Hashes the key to the identifier space.

get_random_node_id/0

get_random_node_id() -> key()

Generates a random node id, i.e. a random 128-bit number.

init_stabilize/2

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/3

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/3

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/1

to_pid_list(RT :: rt()) -> [comm:mypid()]

Returns the pids of the routing table entries.

get_size/1

get_size(Rt_t :: rt()) -> non_neg_integer()

Returns the size of the routing table.

get_size_ext/1

get_size_ext(RT :: external_rt()) -> non_neg_integer()

Returns the size of the external routing table.

n/0

n() -> 340282366920938463463374607431768211456

Returns the size of the address space.

get_range/2

get_range(Begin :: key(),
          End :: key() | 340282366920938463463374607431768211456) ->
             number()

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/3

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/3

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/1

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/2

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.

get_replica_keys/1

get_replica_keys(Key :: key()) -> [key()]

Returns the replicas of the given key.

get_key_segment/1

get_key_segment(Key :: key()) -> pos_integer()

dump/1

dump(RT :: rt()) ->
        KeyValueList :: [{Index :: string(), Node :: string()}]

Dumps the RT state for output in the web interface.

dump_to_csv/1

dump_to_csv(RT :: rt()) -> [char()]

Dump the routing table into a CSV string

check_config/0

check_config() -> boolean()

Checks whether config parameters of the rt_frtchord process exist and are valid.

get_random_key_from_generator/3

get_random_key_from_generator(SourceNodeId :: key(),
                              PredId :: key(),
                              SuccId :: key()) ->
                                 key()

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/2

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/2

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/5

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/6

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/1

empty_ext(Neighbors :: nodelist:neighborhood()) -> external_rt()

next_hop/3

next_hop(Neighbors :: nodelist:neighborhood(),
         ERT :: external_rt(),
         Id :: key()) ->
            succ | comm:mypid()

succ/2

succ(ERT :: external_rt(), Neighbors :: nodelist:neighborhood()) ->
        comm:mypid()

Return the succ

export_rt_to_dht_node/2

export_rt_to_dht_node(RT :: rt(),
                      Neighbors :: nodelist:neighborhood()) ->
                         external_rt()

to_list/1

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/1

get_source_node(RT :: rt()) -> rt_entry()

Get the source node of a routing table

get_source_id/1

get_source_id(RT :: rt()) -> key()

Get the id of the source node.

check_rt_integrity/1

check_rt_integrity(RT :: rt()) -> boolean()

Check that all entries in an rt are well connected by their adjacent fingers

wrap_message/5

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/2

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/1

check_well_connectedness(RT :: rt()) -> boolean()

Check that the adjacent fingers of a RT are building a ring

allowed_nodes/1

allowed_nodes(RT :: rt()) -> [rt_entry()]

rt_entry_info/4

rt_entry_info(Node :: mynode(),
              Type :: entry_type(),
              PredId :: key(),
              SuccId :: key()) ->
                 rt_entry_info_t()

frt_check_config/0

frt_check_config() -> boolean()

Checks whether config parameters of the rt_frtchord/rt_gfrtchord process exist and are valid.


Generated by EDoc, Feb 29 2016, 16:12:17.