Just another Community
JaCOP
Organization Protocol
JaCOPIntroduzione
Il punto di partenza
Una comunità/rete di pari è così detta perché
costituita da nodi che possono agire
contemporaneamente da clienti e da
servitori
Il fatto che il numero di potenziali servitori sia
pari al numero dei nodi conferisce ai servizi
p2p di un alto livello di disponibilità
Il meccanismo che permette ai nodi di
conoscersi tuttavia è di tipo C/S con server
centralizzato
Questo significa che la caduta del server ha
come effetto al disgregazione dell’intera
comunità
JaCOPIntroduzione
Possibili soluzioni
Se ne possono individuare rapidamente due:
1. Replicazione del server



ha un costo contenuto
mantiene centralizzato il controllo della
comunità
un evento imprevisto potrebbe isolare la
sottorete su cui si trovano i server
2. Intervento sul meccanismo di
definizione della comunità
In modo da renderlo:



privo di server centralizzati
robusto
scalabile
E’ stata percorsa la seconda strada (... anche perché più interessante)
JaCOPIntroduzione
Soluzione 1
connessioni dirette tra ogni coppia di nodi
 massimo numero di connessioni (n*(n-1))...
 ma massima robustezza
JaCOPIntroduzione
Soluzione 1
connessioni dirette tra ogni coppia di nodi
 massimo numero di connessioni (n*(n-1))..
 ma massima robustezza
Soluzione 2
ogni nodo è connesso solo ad un’altro
 minimo numero di connessioni (n-1)...
 ma minima robustezza (la rete resiste alla
caduta di un solo nodo)
JaCOPIntroduzione
Soluzione 1
rete punto a punto
 massimo numero di connessioni (n*(n-1))..
 ma massima robustezza
Soluzione 2
ogni nodo è connesso solo ad un’altro
 minimo numero di connessioni (n-1)...
 ma minima robustezza (la rete resiste alla
caduta di un solo nodo)
Soluzione 3
rete resistente alla caduta di k nodi (k si dice
grado di coesione)


è un buon compromesso
richiede che tra ogni coppia di nodi
esistano almeno k cammini distinti che
li congiungono
è stata perseguita la terza soluzione
JaCOPGli algoritmi – A1
il primo passo è stato definire un algoritmo
per la costruzione di una rete con le proprietà
desiderate
Idee base



i nodi si aggiungono uno ad uno mediante
un’operazione detta “join” (giunzione)
ogni nodo può fare da server per un join
(punto di giunzione)
quando un nodo effettua un join viene
messo a conoscenza da parte del server di
alcuni dei suoi vicini
A1 (algoritmo di costruzione)
Durante una giunzione il servant passa
all’altro nodo k-1 suoi vicini scelti a caso
si può dimostrare che una rete costruita
con A1 ha grado di coesione k
k=2
JaCOPGli algoritmi – A1
Struttura
L’insieme dei nodi ottenuti durante una
operazione di join, più il punto di giunzione, si
dicono “struttura” del nodo che effettua la
giunzione.
Sa a è di struttura per b si scrive: a S b
Relazione di dipendenza
Si dice che a “dipende da” b, e si scrive:
ab
se b S a o c1, ...cn tali che b S cn, ... c1 S a
La relazione di dipendenza definisce sulla
rete un ordine parziale
k=2
Rispetto ad un nodo la rete si può dividere in
due porzioni “dipendente” ed “indipendente”
la chiave del funzionamento di A1 è che grazie ad esso ogni nodo ha almeno k legami
con la rete indipendente
JaCOPGli algoritmi – A3
Perché una rete costruta con A1 possa
essere di qualche utilità occorre:
 che sia visitabile
 che lo sia in modo efficiente
Osservazione
L’insieme dei legami tra nodi e rispettivo
punto di giunzione definisce uno spanning
tree sulla rete
A3 sfrutta questo fatto per esplorare in modo
efficiente la rete
A3 (algoritmo di esplorazione)
Per ogni nodo sia BL(n) l’insieme dei nodi ad
esso giuntati e FL(n) il punto di giunzione
A partire da un nodo n si esplora prima
BL(n) e poi FL(n).
Ad ogni passo il nodo di provenienza è
sempre escluso dall’esplorazione
k=2
JaCOPGli algoritmi – A2
Non è sufficiente che un rete possa sostenere
senza partizionarsi la caduta di k nodi
Occorre che essa sia riorganizzata in modo
che anche dopo la caduta per ogni nodo
esistano k legami con la porzione di rete
da esso indipendente
A2 (algoritmo di ristrutturazione)
Si distinguono due sottocasi:
Caso A: il nodo caduto non è il punto di
giunzione (re-join)


se il nodo non è di struttura non si fa nulla
se è di struttura si effettua una nuova
operazione di join al punto di giunzione
corrente
k=2
JaCOPGli algoritmi – A2

il punto di giunzione sceglie tra i propri
vicini un pool di candidati da utilizzare
come nuova struttura
Al nodo che effettua il join sono passati:


i nodi che fanno parte della sua struttura
corrente (che vengono così riciclati)
nodi scelti dal pool, fino ad arrivare al
numero di k-1
I nodi candidati devono essere indipendenti
dal nodo che effettua il re-join
Il pool è calcolato mediante un algoritmo di
programmazione dinamica che suppone:


che tutti i nodi di struttura di un dato nodo
siano vicini del punto di giunzione
che il punto di giunzione conosca la
struttura di tutti i suoi vicini
k=2
JaCOPGli algoritmi – A2
Caso B: il nodo caduto è il punto di
giunzione (new-join)


il nodo sceglie uno dei suoi vicini di
struttura ed effettua verso di esso un nuova
operazione di join
tutto procede come nel caso precendente,
ma i nodi della struttura corrente vengono
riciclati solo se compaiono nel pool dei
candidati
questo è necessario perché rimangano
soddisfatte le condizioni per il funzionamento
dell’algoritmo che elabora il pool
k=2
JaCOPGli algoritmi – Variante del modello
Variante
Per evitare di caricare troppo dei nodi può
essere utile cercare di bilancare la rete
Questo può essere fatto:
 assegnado ad ogni nodo un fattore di
carico
 introducendo la possibilità di delegare una
richiesta di join
Fattore di carico
Come fattore di carico si è scelto:
L(n) = #conn/C(n)
Dove C(n) è la capacità del nodo
Dal pool dei candidati si scelgono i nodi
con carico minore
Delega
Se il nodo che riceve una richiesta di join
ha un vicino meno carico delega la richiesta
al vicino con carico minore
C=1
C=2
4
1
0.75
C=4
2
C=1
k=2
max numero di deleghe = 1
JaCOPIl protocollo – introduzione
Note introduttive
Il protocollo sviluppato è a livello applicativo
Suppone l’esistenza di una rete sottostante,
su cui si fanno le seguenti assunzioni:


la rete è fornita di un meccanismo di
identificazione dei nodi
i pacchetti non vengono perduti e sono
consegnati in ordine
Il set TCP + IP soddisfa queste ipotesi, il set
UDP + IP solo la prima
Per ottenere portabilità i pacchetti sono in
formato XML
Per ragioni di chiarezza il protocollo è stato
suddiviso in sottoprotocolli
<?xml version="1.0" encoding="UTF-8"?>
<joinRequest>
<community>comunità</community>
<senderLoadFactor>1.2</senderLoadFactor>
<receiverLoadFactor>0.75</receiverLoadFactor>
<receiverIsStructure/>
<node>
<address>192.168.30.17</address>
<port>3330</port>
<loadFactor>1.2</loadFactor>
</node>
<force/>
<nodeList>
<node>
<address>192.168.30.16</address>
<port>3330</port>
<loadFactor>1</loadFactor>
<structure/>
</node>
<node>
<address>192.168.30.15</address>
<port>3330</port>
<loadFactor>0.2</loadFactor>
</node>
</nodeList>
</joinRequest>
JaCOPIl protocollo – introduzione
Note introduttive
Ogni nodo mantiene le seguenti strutture
dati:
Per ognuno dei sottoprotocolli descritti
valgono le seguenti affermazioni:







F(n) = insieme dei vicini
FL(n) = punto di giunzione
BL(n) = vicini per cui il nodo corrente
è punto di giunzione
S(n) = struttura
S(n, a) = vicini che fanno parte della
struttura di un altro vicino
FL(a) = punto di giunzione dei vicini
dipendenti



su ogni nodo può essere in
esecuzione una sola conversazione
alla volta
si considerano prioritarie le
conversazioni attivate da richieste
provenienti da nodi indipendenti
una conversazione non prioritaria può
essere interrotta da una
conversazione prioritaria, ma non
viceversa
una conversazione non prioritaria non
può essere interrotta da una
conversazione non prioriatria
JaCOPIl protocollo – P1
P1 (protocollo di join)
E’ innescato dall’invio/arrivo di un pacchetto
“richiesta di join”
Nessun nodo può rispondere ad una
richiesta di join se la sua struttura non è
“completa”
join request [client, S(client), flag force]
client
servant
Il servant determina il pool dei candidati,
quindi sceglie la nuova struttura; i nodi di
struttura esistenti vengono riciclati solo se
compaiono nel pool
newStructure[ {chosen nodes}, connectionRank ]
servant
client
k=2
JaCOPIl protocollo – P1
Il servant quindi informa i nodi scelti del
nuovo vicino e della sua struttura
newNeighbor [ client, { client structure } ]
client
ch. node
i vicini rispondono con una conferma, ma
non modificano il proprio stato
ok[ ]
ch.node
client
Il server ricalcola il pool dei nodi di
struttura e controlla che la struttura passata
sia ancora valida
Questo è necessario perché richieste di join
in esecuzione su altri nodi potrebbero alterare
le dipendenze
k=2
JaCOPIl protocollo – P1
Se i nodi scelti sono ancora validi il servant
invia ad essi ed al client dei messaggi di
conferma
ok [ ]
servant
ch.node
ok [ ]
servant
client
Il client aggiunge i nuovi nodi, inizia a
monitorarli ed elimina quelli della vecchia
struttura che non sono stati riciclati
Il servant e i nodi scelti aggiungono il
nuovo vicino ed iniziano a monitorarlo;
memorizzano la sua struttura
k=2
JaCOPIl protocollo – P1
Il client rimuove tutti i vicini il cui punto di
giunzione è tra i nodi di struttura non
riciclati
questo è necessario perché esiste una
“finestra” di tempo in cui i nodi di struttura
che saranno scartati possono passare il
nodo corrente a nodi giuntati
Il client invia ai nodi ad esso giuntati un
messaggio che indica di rimuovere i nodi di
struttura non riciclati
faultNotification [{ not recycl. nd }]
client
joined nd.
in questo modo la struttura dei nodi giuntati
rimane costituita da vicini del punto di
giunzione
k=2
JaCOPIl protocollo – P2
P2 (notifica nuovi vicini)
Tramite questo protocollo un nodo viene
notificato della presenza di un nuovo vicino
dipendente
newNeighbor [ node, { node structure } ]
client
servant
Del nuovo vicino viene indicata anche la
struttura
ok [ ]
client
servant
ok [ ]
client
servant
dopo il secondo “ok” il servant aggiunge il
vicino, ed aggiorna la struttura condivisa
S(servant, node), memorizza il punto di
giunzione del nuovo nodo
k=2
JaCOPIl protocollo – P3
P3 (notifica di eliminazione)
Indica ad un nodo di rimuovere alcuni dei suoi
vicini (perché parte della struttura non
riciclata del punto di giunzione)
fault notification [ { fallen nodes } ]
client
servant
il servant:
 rimuove i vicini indicati
 rimuove tutti i vicini dipendenti il cui
punto di giunzione è tra i nodi
eliminati
 invia ai nodi ad esso giuntati un
messaggio che indica di rimuovere i
nodi da esso eliminati
fault notification [ { deleted nodes } ]
servant
joined nd.
k=2
JaCOPIl protocollo – P4
P4 (riorganizzazione)
E’ innescato dalla caduta di un vicino di
struttura. Si distiguono due casi:
1) il nodo caduto non era il punto di
giunzione
>> si effettua una nuova operazione di join
verso lo stesso punto di giunzione (re-join)
2) il nodo caduto era il punto di giunzione
>> si sceglie un nuovo punto di giunzione tra i
vicini di struttura e si effettua una nuova
operazione di join (new-join)
k=2
JaCOPIl protocollo – P5
P5 (monitoraggio)
Permette di conoscere lo stato dei vicini, in
particolare:
 se sono attivi o meno
 il loro fattore di carico
A intervalli regolari ogni nodo emette dei
messaggi di heartbeat, cui il ricevente
risponde (se il mittente non è riconosciuto
come vicino non vi è alcuna risposta)
heartbeat [ ]
client
servant
heartbeat [ ]
client


k=2
servant
una mancata risposta indica che il nodo
non è attivo
tra le informazioni sul mittente trasmesse
c’è il suo fattore di carico
JaCOPImplementazione - Introduzione
Caratteristiche dell’applicazione
Struttura a livelli
>> E’ stata realizzata in Java
Alla base c’è il framework descritto
>> Come protocollo di base è stato scelto
UDP
Sfruttando le sue funzionalità sono stati
costruiti:



è più leggero di TCP
ma non garantisce la consegna dei
pacchetti, né il loro arrivo in ordine
>> Per questo è stato necessario introdurre
un framework che rimediasse alla mancanza
PA

una applicazione che implementa il
protocollo come servizio (attuatore di
protocollo)
una seconda applicazione per il test
dell’algoritmo A3
A3 TEST
FRAMEWORK
JaCOPImplementazione - Framework
Caratteristiche del framework
Il framework sviluppato:




gestisce la ritrasmissione e la consegna
in ordine dei pacchetti
definisce il concetto di conversazione
è realizzato come un sistema ad eventi
il nocciolo dell’architettura è il seguente:
Conversazione:
scambio di pacchetti tra due o più nodi
>> è avviata dal nodo che invia il primo
pacchetto
>> vi partecipano tutti i nodi che
rispondono ad un pacchetto che ne fa
parte
JaCOPImplementazione - Framework
Il receiver e il transmitter sono implementati come thread



l’InGate utilizza una socket per ricevere
pacchetti, l’Unmarshaller ne permette la
decodifica
Il Receiver attende costantemente l’arrivo
di pacchetti
quando ne arriva uno innesca un evento e
lo inserisce nel Dispatchter, costituito da
una collezione di mailbox associate
ciascuna ad una conversazione



i pacchetti da inviare vengono inseriti in
una coda FIFO (OutQueue)
il Transmitter preleva pacchetti dalla coda
l’OutGate permette il loro invio su una
socket, previa codifica effettuata dal
Marshaller
JaCOPImplementazione – Protocol Actuator
Architettura dell’attuatore di protocollo
Si è scelto di descrivere l’attuatore di protocollo per componenti, a causa della sua
complessità





i moduli principali dell’attuatore si basano
sul ConversationFramework
il modulo JaCOP Actuator implementa il
protocollo JaCOP
l’Heartbeat System esegue il protocollo di
heartbeat
il modulo Node Status mantiene
informazioni sullo stato del nodo
L’interfaccia utente può intervenire
sull’attuatore di protocollo per innescare
una giunzione o sul modulo Node Status
per avere informazioni
JaCOPImplementazione – Protocol Actuator
Funzionamento dell’attuatore di protocollo
La ricezione di un messaggio di richiesta, di uno di notifica o una richiesta di giunzione da
parte dell’utente causano l’attivazione di un thread che gestisce la conversazione
Per ogni sottoprotocollo dunque esistono in generale due tipi di thread: “client” e “server”
Il rispetto del corretto ordine di esecuzione è affidato ad un apposito sistema di controllo



la classe ControlSystem fa da facciata e
mentiene un registro dei trhead in
esecuzione
la classe SystemSemaphore implementa
un semaforo binario che dà la precedenza
ai thread prioritari
il vincolo che un nodo non possa
rispondere a richieste di giunzione se non
ha stuttura integra è implementato
mediante una variabile condizione
JaCOPConclusioni e sviluppi futuri
Conclusioni
Gli aspetti salienti del lavoro svolto sono stati:



la definizione di algoritmi per la costruzione di una rete connessa con grado di coesione
arbitrario, per la sua ristrutturazione e per la sua esplorazione
la specifica di un insieme i protocolli per realizzare e mantenere dinamicamente queste
reti in un ambiente distribuito
una implementazione del protocollo basata su reti UDP/IP e su un framework per la
gestione delle conversazioni
Sviluppi futuri
Alcuni sviluppi futuri possono essere:





migliorare il protocollo aumentandone l’efficienza
risoluzione di alcuni problemi (problema del partizionamento, bottleneck dello spanning
tree in A3)
l’implementazione di politiche per l’accesso alle comunità
aggiungere sicurezza alle comunicazione, ad esempio cifrandone i contenuti
trovare modalità efficienti per l’individuazione di nodi o contenuti specifici sulla rete