Modulo PeerServices - Appunti - Algoritmi 1 / 2

Contents

Modulo PeerServices - Appunti - Algoritmi 1 / 2
1. Algoritmo di instradamento completo

Algoritmo di instradamento completo

IPeersResponse contact_peer(p_id, x̄, request, timeout_exec, exclude_myself, respondant, exclude_tuple_list=null) throws PeersNoParticipantsInNetworkError

Gli argomenti passati sono:
- int p_id,
- PeerTupleNode x̄,
- IPeersRequest request,
- int timeout_exec,
- bool exclude_myself,
- out PeerTupleNode respondant,
- PeerTupleGNodeContainer? exclude_tuple_list=null.
refuse_message = null.
respondant = null.
target_levels = x̄.tuple.size.
exclude_gnode_list = new ArrayList di HCoord.
bool opzionale = False.
Se services.has_key(p_id):
- opzionale = services[p_id].p_is_optional.
- Se NOT services[m’.p_id].is_ready():
  - exclude_myself = True.
Altrimenti:
- opzionale = True.
Mette in exclude_gnode_list tutti i g-nodi risultanti da get_non_participant_gnodes(p_id).
Se exclude_myself:
- Mette HCoord(0, pos[0]) in exclude_gnode_list.
Se exclude_tuple_list = null:
- exclude_tuple_list = new PeerTupleGNodeContainer(target_levels).
assert(exclude_tuple_list.top == target_levels).
Per ogni PeerTupleGNode gn in exclude_tuple_list:
- int case, HCoord ret.
- Calcola convert_tuple_gnode(gn, out case, out ret).
- Se case = 2:
  - Cioè gn rappresenta un g-nodo visibile nella mia topologia.
  - Metti ret in exclude_gnode_list.
non_participant_tuple_list = new PeerTupleGNodeContainer(target_levels).
IPeersResponse? response = null.
While True (ciclo 1):
- x = approximate(x̄, exclude_list=exclude_gnode_list). Restituisce un HCoord o null.
- Se x = null:
  - Se refuse_message ≠ null:
    - Lancia eccezione PeersRefuseExecutionError in base a refuse_message.
  - Lancia eccezione PeersNoParticipantsInNetworkError. L'algoritmo termina.
- Se x.lvl = 0 AND x.pos = pos[0]:
  - Try:
    - response = services[p_id].exec(request).
  - Se riceve PeersRefuseExecutionError:
    - Valorizza refuse_message in base all'errore.
    - Mette HCoord(0, pos[0]) in exclude_gnode_list.
    - Continua con la prossima iterazione del ciclo 1.
  - Restituisce response. Termina l'algoritmo.
- m’ = new PeerMessageForwarder.
- m’.n = la tupla n₀·n₁·...·n_j dove j = x.lvl.
- m’.x̄ = la tupla x̄₀·x̄₁·...·x̄_j-1. E' null se j = 0.
- m’.lvl = x.lvl.
- m’.pos = x.pos.
- m’.p_id = p_id.
- m’.msg_id = un identificativo generato a caso per questo messaggio.
- Per ogni PeerTupleGNode t in exclude_tuple_list:
  - # Scopriamo se t è interno a x:
  - int case, HCoord ret.
  - Calcola convert_tuple_gnode(t, out case, out ret).
  - Se case = 3:
    - Cioè t rappresenta un g-nodo non visibile nella mia topologia interno a ret.
    - Se ret.equals(x):
      - ε = t.top - t.tuple.size
      - t’ = new PeerTupleGNode(t.tuple.slice(0, j-ε), j).
      - m’.exclude_tuple_list.add(t’).
- Per ogni PeerTupleGNode t in non_participant_tuple_list:
  - Se visible_by_someone_inside_my_gnode(t, j+1):
    - m’.non_participant_tuple_list.add(t).
- Calcola timeout_instradamento = f ( map_paths.i_peers_get_nodes_in_my_group(x.lvl + 1) ).
- Prepara waiting_answer = new WaitingAnswer(request, x come PeerTupleGNode con top = x.lvl+1).
- waiting_answer_map[m’.msg_id] = waiting_answer.
- IAddressManagerRootDispatcher gwstub
- IAddressManagerRootDispatcher? failed = null
- bool necessita_ricalcolo = False
- While True:
  - Try:
    - Calcola gwstub = map_paths.i_peers_gateway(x.lvl, x.pos, null, failed)
  - Se riceve l'eccezione PeersNonexistentDestinationError:
    - necessita_ricalcolo = True.
    - Esci dal ciclo.
  - Try:
    - Esegue gwstub.peers_manager.forward_peer_message(m’).
  - Se riceve l'eccezione StubError o DeserializeError:
    - failed = gwstub.
    - Continua con la prossima iterazione del ciclo.
  - Esci dal ciclo.
- Se necessita_ricalcolo:
  - Rimuovi waiting_answer_map[m’.msg_id].
  - Aspetta alcuni istanti.
  - Continua con la prossima iterazione del ciclo 1.
- tempo_attesa = timeout_instradamento.
- While True (ciclo 2):
  - Try:
    - Sta in attesa su waiting_answer.ch per max tempo_attesa.
    - Se waiting_answer.exclude_gnode ≠ null:
      - # significa che abbiamo ricevuto notizia di un gnodo da escludere.
      - waiting_answer.exclude_gnode è un PeerTupleGNode che rappresenta un g-nodo h dentro il mio g-nodo di livello top.
      - Crea t, una istanza di PeerTupleGNode con top=target_levels che rappresenta il g-nodo h.
      - Se è visibile nella mia mappa:
        Crea g, una istanza di HCoord che rappresenta il g-nodo h.
        Mette g in exclude_gnode_list.
      - Mette t in exclude_tuple_list.
      - Rimuovi waiting_answer_map[m’.msg_id].
      - Esci dal ciclo 2.
    - Altrimenti-Se waiting_answer.non_participant_gnode ≠ null:
      - # significa che abbiamo ricevuto notizia di un gnodo non partecipante.
      - waiting_answer.non_participant_gnode è un PeerTupleGNode che rappresenta un g-nodo h dentro il mio g-nodo di livello top.
      - Crea t, una istanza di PeerTupleGNode con top=target_levels che rappresenta il g-nodo h.
      - Se è visibile nella mia mappa:
        Crea g, una istanza di HCoord che rappresenta il g-nodo h.
        Se opzionale:
        Se (! participant_maps.has_key(p_id)):
        Lancia eccezione PeersNoParticipantsInNetworkError. L'algoritmo termina.
        map = participant_maps[p_id].
        Toglie g da map.participant_list.
        Mette g in exclude_gnode_list.
      - Mette t in exclude_tuple_list.
      - Mette t in non_participant_tuple_list.
      - Rimuovi waiting_answer_map[m’.msg_id].
      - Esci dal ciclo 2.
    - Altrimenti-Se respondant = null e waiting_answer.respondant_node ≠ null:
      - # significa che abbiamo consegnato il messaggio.
      - respondant = waiting_answer.respondant_node come tupla globale nel g-nodo di ricerca.
      - tempo_attesa = timeout_exec.
    - Altrimenti-Se waiting_answer.response ≠ null:
      - # significa che abbiamo ricevuto la risposta.
      - response = waiting_answer.response.
      - Rimuovi waiting_answer_map[m’.msg_id].
      - Esci dal ciclo 2. Poi uscirai dal ciclo 1.
    - Altrimenti-Se respondant ≠ null e waiting_answer.refuse_message:
      - # significa che l'attuale respondant ha rifiutato di elaborare la richiesta.
      - Valorizza refuse_message = waiting_answer.refuse_message.
      - Crea t, una istanza di PeerTupleGNode con top=target_levels che rappresenta il nodo respondant.
      - Se è visibile nella mia mappa:
        Crea g, una istanza di HCoord che rappresenta il nodo respondant.
        Mette g in exclude_gnode_list.
      - Mette t in exclude_tuple_list.
      - Rimuovi waiting_answer_map[m’.msg_id].
      - Esci dal ciclo 2.
    - Altrimenti:
      - # significa che abbiamo ricevuto un nuovo valore in waiting_answer.min_target.
      - NOP.
  - Se riceve l'eccezione TimeoutError:
    - # dobbiamo trattare waiting_answer.min_target come da escludere.
    - waiting_answer.min_target è un PeerTupleGNode che rappresenta un g-nodo h dentro il mio g-nodo di livello top.
    - Crea t, una istanza di PeerTupleGNode con top=target_levels che rappresenta il g-nodo h.
    - Se è visibile nella mia mappa:
      - Crea g, una istanza di HCoord che rappresenta il g-nodo h.
      - Mette g in exclude_gnode_list.
    - Mette t in exclude_tuple_list.
    - Rimuovi waiting_answer_map[m’.msg_id].
    - Esci dal ciclo 2.
- Se response ≠ null:
  - Esci dal ciclo 1.
# Uscito dal ciclo 1.
Restituisce response.

void forward_peer_message(m’)

Recupera caller, cioè le informazioni sul chiamante del metodo remoto.
bool opzionale = False.
bool exclude_myself = False.
Se services.has_key(m’.p_id):
- opzionale = services[m’.p_id].p_is_optional.
- exclude_myself = NOT services[m’.p_id].is_ready().
Altrimenti:
- opzionale = True.
Se pos[m’.lvl] = m’.pos:
- Si veda sotto tra gli algoritmi helper.
- Se NOT my_gnode_participates(m’.p_id, m’.lvl):
  - nstub = back_stub_factory.i_peers_get_tcp_inside(m’.n.tuple).
  - Calcola gn istanza di PeerTupleGNode che rappresenta HCoord(m’.lvl, m’.pos) con top = m’.n.tuple.size.
  - Try:
    - Esegue nstub.peers_manager.set_non_participant(m’.msg_id, gn).
  - Se riceve StubError o DeserializeError:
    - Ignora.
- Altrimenti:
  - exclude_gnode_list = new ArrayList di HCoord.
  - Metti in exclude_gnode_list tutti i g-nodi risultanti da get_non_participant_gnodes(p_id).
  - Se exclude_myself:
    - Mette HCoord(0, pos[0]) in exclude_gnode_list.
  - Per ogni PeerTupleGNode gn in m’.exclude_tuple_list:
    - int case, HCoord ret.
    - Calcola convert_tuple_gnode(gn, out case, out ret).
    - Se case = 1:
      - Cioè gn rappresenta un mio g-nodo di livello ret.lvl:
      - Metti in exclude_gnode_list tutti i g-nodi risultanti da get_all_gnodes_up_to_level(ret.lvl).
    - Se case = 2:
      - Cioè gn rappresenta un g-nodo visibile nella mia topologia:
      - Metti in exclude_gnode_list ret.
  - bool consegnato = False.
  - While not consegnato:
    - x = approximate(m’.x̄, exclude_list=exclude_gnode_list). Restituisce un HCoord o null.
    - Se x = null:
      - nstub = back_stub_factory.i_peers_get_tcp_inside(m’.n.tuple).
      - Calcola gn istanza di PeerTupleGNode che rappresenta HCoord(m’.lvl, m’.pos) con top = m’.n.tuple.size.
      - Try:
        Esegue nstub.peers_manager.set_failure(m’.msg_id, gn).
      - Se riceve StubError o DeserializeError:
        Ignora.
      - Esci dal ciclo. Poi proseguirà con l'elaborazione delle informazioni di non partecipazione.
    - Altrimenti-Se x.lvl = 0 AND x.pos = pos[0]:
      - nstub = back_stub_factory.i_peers_get_tcp_inside(m’.n.tuple).
      - Calcola tuple_respondant istanza di PeerTupleNode che rappresenta HCoord(0, pos[0]) con top = m’.n.tuple.size.
      - Try:
        IPeersRequest request = nstub.peers_manager.get_request(m’.msg_id, tuple_respondant).
        Try:
        IPeersResponse resp = services[m’.p_id].exec(request).
        nstub.peers_manager.set_response(m’.msg_id, resp).
        Se riceve PeersRefuseExecutionError e:
        Try:
        Prepara un messaggio err_msg dal quale sarà possibile ricostruire l'eccezione.
        Esegue nstub.peers_manager.set_refuse_message(m’.msg_id, err_msg).
        Se riceve StubError o DeserializeError:
        Ignora.
      - Se riceve PeersUnknownMessageError:
        Ignora.
      - Se riceve StubError o DeserializeError:
        Ignora.
      - Esci dal ciclo. Poi proseguirà con l'elaborazione delle informazioni di non partecipazione.
    - Altrimenti:
      - m’’ = copia di m’.
      - m’’.lvl = x.lvl.
      - m’’.pos = x.pos.
      - m’’.x̄ = la tupla x̄₀·x̄₁·...·x̄_k-1 dove k = x.lvl. E' null se k = 0.
      - Per ogni PeerTupleGNode t in m’.exclude_tuple_list:
        # Scopriamo se t è interno a x:
        int case, HCoord ret.
        Calcola convert_tuple_gnode(t, out case, out ret).
        Se case = 3:
        Cioè t rappresenta un g-nodo non visibile nella mia topologia interno a ret.
        Se ret.equals(x):
        ε = t.top - t.tuple.size
        t’ = new PeerTupleGNode(t.tuple.slice(0, k-ε), k).
        m’’.exclude_tuple_list.add(t’).
      - Per ogni PeerTupleGNode t in m’.non_participant_tuple_list:
        Se visible_by_someone_inside_my_gnode(t, k+1):
        m’’.non_participant_tuple_list.add(t).
      - IAddressManagerRootDispatcher gwstub
      - IAddressManagerRootDispatcher? failed = null
      - While True:
        Try:
        Calcola gwstub = map_paths.i_peers_gateway(m’’.lvl, m’’.pos, caller, failed)
        Se riceve l'eccezione PeersNonexistentDestinationError:
        Aspetta alcuni istanti.
        Esci dal ciclo. Ripeterà il calcolo di approximate.
        Try:
        Esegue gwstub.peers_manager.forward_peer_message(m’’).
        Se riceve l'eccezione StubError o DeserializeError:
        failed = gwstub.
        Continua con la prossima iterazione del ciclo.
        consegnato = True.
        nstub = back_stub_factory.i_peers_get_tcp_inside(m’.n.tuple).
        Calcola gn istanza di PeerTupleGNode che rappresenta HCoord(x.lvl, x.pos) con top = m’.n.tuple.size.
        Try:
        Esegue nstub.peers_manager.set_next_destination(m’.msg_id, gn).
        Se riceve StubError o DeserializeError:
        Ignora.
        Esci dal ciclo. Poi proseguirà con l'elaborazione delle informazioni di non partecipazione.
Altrimenti:
- IAddressManagerRootDispatcher gwstub
- IAddressManagerRootDispatcher? failed = null
- While True:
  - Try:
    - Calcola gwstub = map_paths.i_peers_gateway(m’.lvl, m’.pos, caller, failed)
  - Se riceve l'eccezione PeersNonexistentDestinationError:
    - Rinuncia all'instradamento. Esci dal ciclo.
  - Try:
    - Esegue gwstub.peers_manager.forward_peer_message(m’).
  - Se riceve l'eccezione StubError o DeserializeError:
    - failed = gwstub.
    - Continua con la prossima iterazione del ciclo.
  - Esci dal ciclo.
Se opzionale AND participant_maps.has_key(m’.p_id):
- Per ogni TupleGNode t in m’.non_participant_tuple_list:
  - Se t rappresenta un g-nodo visibile nella nostra mappa:
    - Calcola g = istanza di HCoord rappresentante lo stesso g-nodo di t.
    - Se g ∈ participant_maps[m’.p_id].participant_list:
      - Svolgi quanto segue in una nuova tasklet portando dietro p_id=m’.p_id, lvl=g.lvl, pos=g.pos:
        Si veda sotto l'algoritmo di rilevamento della non partecipazione.
        Se check_non_participation(p_id, lvl, pos):
        Se participant_maps.has_key(p_id):
        participant_maps[p_id].participant_list.remove(HCoord(lvl,pos))

HCoord? approximate(x̄, exclude_list)

Gli argomenti sono:
- PeerTupleNode? x̄,
- List di HCoord exclude_list.
Se x̄ = null:
- # la destinazione sono io o nessun altro.
- x = new HCoord(0,pos[0]). Cioè x rappresenta me.
- Se x not in exclude_list:
  - Return x.
- Altrimenti:
  - Return null.
valid_levels = x̄.tuple.size. Specificando una tupla con un numero di posizioni inferiore al numero totale dei livelli della rete si richiede a questa funzione (e di coseguenza al resto dell'algoritmo di instradamento verso l'hash_node) di restringere la ricerca all'interno di un certo g-nodo.
HCoord? ret = null.
min_distance = -1.
Per l che va da 0 a valid_levels-1: Per p che va da 0 a gsizes[l]-1: Se pos[l] ≠ p: Se map_paths.i_peers_exists(l, p):
- x = new HCoord(l,p). Cioè x rappresenta un g-nodo a cui io non appartengo, visibile nella mia topologia, interno al g-nodo in cui la ricerca è eventualmente circoscritta, esistente nella rete.
- Se x not in exclude_list:
  - PeerTupleNode tuple_x = make_tuple_node(x, valid_levels).
  - distance = dist(x̄, tuple_x).
  - Se min_distance = -1 OR distance < min_distance:
    - ret = x.
    - min_distance = distance.
x = new HCoord(0,pos[0]). Cioè x rappresenta me.
Se x not in exclude_list:
- PeerTupleNode tuple_x = make_tuple_node(x, valid_levels).
- distance = dist(x̄, tuple_x).
- Se min_distance = -1 OR distance < min_distance:
  - ret = x.
  - min_distance = distance.
Return ret.

int dist(x̄, x)

Gli argomenti sono:
- PeerTupleNode x̄,
- PeerTupleNode x.
assert(x̄.tuple.size == x.tuple.size).
distance = 0.
Per j da x.tuple.size-1 a 0:
- distance *= gsizes[j].
- distance += x.tuple[j] - x̄.tuple[j].
- Se x̄.tuple[j] > x.tuple[j]:
  - distance += gsizes[j].
Return distance.