Overlay network
strutturate per
applicazioni peer to peer
Lorenzo Castelli
Overlay network
Overlay network in un’applicazione
peer to peer: la rete virtuale formata
dai nodi dell’applicazione e dai loro
riferimenti verso gli altri nodi.
Organizzazioni classiche
• Centralizzata
• Non strutturata
Meccanismi di ricerca classici
• Client-Server
• Broadcast (limitato)
Overlay network strutturate
Reti decentralizzate ma strutturate,
che forniscono garanzie sulla
complessità della ricerca
(generalmente O(logN)).
Realizzano il key based routing: dato
un’indirizzo, effettuare il routing verso il
nodo attivo con indirizzo più vicino a
tale indirizzo.
Forniscono la base su cui costruire
servizi distribuiti ad alto livello:
• Distributed hash table (DHT)
• Decentralized object location and
routing (DOLR)
• Multicast
Architettura di un nodo
Applicazione peer to peer
Middleware peer to peer
Overlay network
Algoritmi di
routing
Gestione
routing table
Routing table
Servizi di rete
Canali di
comunicazione
Trasporto
Rete
Monitoring rete
...
Servizi di rete
Servizi
• Canali di comunicazione
• Monitoring della rete
Tecniche
• Frammentazione e deframmentazione dei
messaggi
• Conferma di ricezione, time-out, sliding
window e protocollo di connessione per
comunicazioni affidabili
• Stima round-trip time e loss rate
• Tecniche anti-congestione
Standard
• UDP
• TCP
• SCTP
Elementi overlay network
Spazio degli indirizzi
• Ampio (es. 160 bit)
• Sufficiente per hash crittografici
Generazione indirizzi univoci
• Universally unique identifier
• A partire da indirizzo IP
• Assegnati da un’organismo centrale
Funzione di distanza
• XOR
• Sottrazione
• Definizioni complesse
Topologia della rete
• Anello
• Albero
Routing
Condizione da garantire
Dato un’indirizzo di destinazione D, qualunque
nodo di indirizzo A è collegato ad almeno un
nodo di indirizzo B tale che d(B,D) < d(A,D),
oppure d(A,D) è minima.
Key based routing
Seguire i nodi via via più vicini fino alla
destinazione.
Complessità
• O(N)
• O(logN)
•…
Protocollo
• Ricorsivo
• Iterativo
DHT
Dizionario distribuito ispirato alle tabelle hash
classiche.
Put
• Calcolo di un’indirizzo univoco I a partire dalla
chiave (funzione hash crittografica)
• Inserimento della coppia chiave-valore nel
nodo con indirizzo più vicino a I
Get
• Calcolo dell’indirizzo I a partire dalla chiave
• Recupero del valore dal nodo con indirizzo più
vicino a I
Manutenzione
• Scambio dei dati al join/leave dei nodi
• Ridondanza per resistenza ai failure
DOLR
Sistema di pubblicazione-localizzazione di
risorse, in grado di fornire alte probabilità di
ottimalità.
Pubblicazione
• Calcolo dell’indirizzo I della risorsa
• Per ogni nodo presente sul percorso fra il
publisher e la radice:
– Inserimento di un puntatore al publisher
associato alla risorsa
Routing
• Calcolo dell’indirizzo I della risorsa
• Invio del messaggio verso la radice
• Deviazione del messaggio non appena si
incontra un nodo che contiene il puntatore al
publisher
Multicast
Organizzazione di canali di distribuzione di
messaggi.
Join-leave
• Calcolo della radice del canale
• Invio di un messaggio apposito alla radice
• Nei nodi intermedi fra il mittente e la radice,
gestione di una lista di “figli” in modo tale da
creare-distruggere un ramo fra radice e
mittente
Invio in multicast
• Calcolo della radice del canale
• Invio del messaggio alla radice
• Propagazione del messaggio dalla radice ai
figli in modo ricorsivo, in modo da percorrere
tutto l’albero
Progetto
Realizzazione di una tabella hash distribuita.
Chimera
• Overlay network basata sugli algoritmi di
Tapestry-Pastry.
• Ottima (e al momento unica?)
implementazione centrata sull’estensibilità e la
flessibilità
• Ancora estremamente prototipale!
DHT realizzata
• Fornisce un dizionario distribuito che associa
stringhe a stringhe
• Funzioni di Put, Get, e manutenzione del
dizionario
• Nessuna ridondanza (può essere costruita in
uno strato superiore)