Modulo PeerServices - Appunti - Algoritmi 1 / 2

Algoritmo di instradamento completo

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

• Gli argomenti passati sono:
  • int p_id,

  • PeerTupleNode x̄,

  • RemoteCall request,

  • int timeout_exec,
  • bool exclude_myself,

  • out PeerTupleNode respondant,

  • PeerTupleGNodeContainer? exclude_tuple_list=null
  • bool reverse=False.

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

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

• ISerializable? response = null.

• While True (ciclo 1):

  • x = approximate(x̄, exclude_list=exclude_gnode_list, reverse). Restituisce un HCoord o null.

  • Se x = null:

    • Lancia eccezione PeersNoParticipantsInNetworkError. L'algoritmo termina.

  • Se x.lvl = 0 AND x.pos = pos[0]:
    • Si passa all'esecuzione del messaggio e l'algoritmo termina. Cioè restituisce services[p_id].exec(request).

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

  • m’.reverse = reverse.

  • 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 RPCError:
      • 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.
        • Altrimenti:
          • 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.
        • Altrimenti:
          • 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 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 waiting_answer.respondant_node ≠ null:
        • # significa che abbiamo consegnato il messaggio.
        • respondant = waiting_answer.respondant_node.
        • tempo_attesa = timeout_exec.
      • 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.
      • Altrimenti:
        • 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 RPCError:
      • 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, m’.reverse). 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 RPCError:
          • 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:

          • RemoteCall request = nstub.peers_manager.get_request(m’.msg_id, tuple_respondant).

          • ISerializable resp = services[m’.p_id].exec(request).

          • nstub.peers_manager.set_response(m’.msg_id, resp).

        • Se riceve PeersUnknownMessageError:

          • Ignora.
        • Se riceve RPCError:
          • 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 RPCError:
            • 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 RPCError:
            • 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 RPCError:
      • 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, reverse=False)

• Gli argomenti sono:

  • PeerTupleNode? x̄,

  • List di HCoord exclude_list,
  • bool reverse=False.
• 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, reverse).

    • 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, reverse).

  • Se min_distance = -1 OR distance < min_distance:

    • ret = x.
    • min_distance = distance.
• Return ret.

int dist(x̄, x, reverse=False)

• Gli argomenti sono:

  • PeerTupleNode x̄,

  • PeerTupleNode x,

  • bool reverse=False.
• Se reverse:
  • Return dist(x, x̄). L'algoritmo termina.
• 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.