Module rt_simple

Simple implementation of a routing table with linear routing.

Copyright © 2008-2013 Zuse Institute Berlin

Version: $Id$

Behaviours: rt_beh.

Authors: Thorsten Schuett (schuett@zib.de).

Description

Simple implementation of a routing table with linear routing.

Data Types

client_key()

client_key() = [unicode_char()]

custom_message()

custom_message() = none()

external_rt()

external_rt() = node:node_type()

key()

key() = 0..340282366920938463463374607431768211455

128 bit numbers

rt()

abstract datatype: rt()

unicode_char()

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

Function Index

activate/1Activate the routing table.
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_simple process exist and are valid.
client_key_to_binary/1
dump/1Dumps the RT state for output in the web interface.
empty_ext/1
export_rt_to_dht_node/2Converts the internal RT to the external RT used by the dht_node.
filter_dead_node/3Removes dead nodes from the routing table (rely on periodic stabilization here).
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_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_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/2There are no custom messages here.
handle_custom_message_inactive/2No special handling of messages, i.e.
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/3Returns the next hop to contact for a lookup.
succ/2Return the succ No need to lookup the succ in the ERT, only dht_node pids are used anyway.
to_list/1Converts the (external) representation of the routing table to a list {Id, Pid} tuples 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. Noop in rt_simple.

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.

update/3

update(OldRT :: rt(),
       OldNeighbors :: nodelist:neighborhood(),
       NewNeighbors :: nodelist:neighborhood()) ->
          {ok, rt()}

Updates the routing table due to a changed node ID, pred and/or succ.

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(Succ :: rt()) -> [comm:mypid()]

Returns the pids of the routing table entries.

get_size/1

get_size(RT :: 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 :: number(), 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(I :: 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(X1 :: 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.

check_config/0

check_config() -> boolean()

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

handle_custom_message_inactive/2

handle_custom_message_inactive(Msg :: comm:message(),
                               MsgQueue :: msg_queue:msg_queue()) ->
                                  msg_queue:msg_queue()

No special handling of messages, i.e. all messages are queued.

handle_custom_message/2

handle_custom_message(Message :: custom_message() | any(),
                      State :: rt_loop:state_active()) ->
                         unknown_event

There are no custom messages here.

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 the internal RT has changed.

empty_ext/1

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

next_hop/3

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

Returns the next hop to contact for a lookup.

succ/2

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

Return the succ No need to lookup the succ in the ERT, only dht_node pids are used anyway.

export_rt_to_dht_node/2

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

Converts the internal RT to the external RT used by the dht_node. Both are the same here.

to_list/1

to_list(State :: dht_node_state:state()) ->
           [{key(), comm:mypid()}]

Converts the (external) representation of the routing table to a list {Id, Pid} tuples in the order of the fingers, i.e. first=succ, second=shortest finger, third=next longer finger,...

wrap_message/5

wrap_message(Key :: key(),
             Msg :: comm:message(),
             MyERT :: external_rt(),
             Neighbors :: nodelist:neighborhood(),
             Hops :: non_neg_integer()) ->
                comm:message()

Wrap lookup messages. This is a noop in rt_simple.

unwrap_message/2

unwrap_message(Msg :: comm:message(),
               State :: dht_node_state:state()) ->
                  comm:message()

Unwrap lookup messages. This is a noop in rt_simple.


Generated by EDoc, Sep 11 2020, 15:24:59.