|
Size: 15200
Comment:
|
Size: 15219
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Modulo PeerServices - Appunti - Algoritmi principali = === Algoritmo di instradamento completo === |
= Modulo PeerServices - Appunti - Algoritmi 1 / 2 = <<TableOfContents(2)>> == Algoritmo di instradamento completo == |
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 n0·n1·...·nj dove j = x.lvl.
m’.x̄ = la tupla x̄0·x̄1·...·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).
- Se visible_by_someone_inside_my_gnode(t, j+1):
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.
- Try:
- 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.
- Se (! participant_maps.has_key(p_id)):
- 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.
- Try:
- 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̄0·x̄1·...·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).
- Se visible_by_someone_inside_my_gnode(t, k+1):
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.
- Try:
- 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.
- Try:
- 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))
- Se participant_maps.has_key(p_id):
- Svolgi quanto segue in una nuova tasklet portando dietro p_id=m’.p_id, lvl=g.lvl, pos=g.pos:
- Se t rappresenta un g-nodo visibile nella nostra mappa:
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.