D. Rosaci
Naming
Il ruolo dei nomi nei SD
• i nomi sono usati per condividere le
risorse, identificare univocamente le
entità e far riferimento alla loro
posizione
• Per risovere i nomi è necessario
implementare un sistema di naming
• Il naming nei SD si differenzia da
quello per sistemi non distribuiti per
l’implementazione
D. Rosaci
Naming
2
Nomi, identificatori e indirizzi
• Un nome è una stringa di bit o caratteri
utilizzati per riferirsi a un’entità
• Un’entità è una qualsiasi risorsa: un host,
una stampante, un file, un oggetto…
• Per operare su un’entità in genere occorre
accedervi attraverso un access point
• Il nome del punto d’accesso di un’entità è
chiamato indirizzo dell’entità
D. Rosaci
Naming
3
Nomi, identificatori e indirizzi
• Un entità può avere più punti di accesso, quindi più
indirizzi
• Un’entità può cambiare indirizzo nel tempo
• Importante: un’entità che cambia punto di accesso
nel tempo, come viene identificata?
• Esistono entità (ad esempio servizi Web) che sono
associate a punti di accesso variabili nel tempo (ad
esempio cambia la locazione della macchina server
che li ospita)
• I nomi di queste entità dovrebbero essere
indipendenti dagli indirizzi (variabili) dei punti di
accesso di volta in volta associati
D. Rosaci
Naming
4
Problematiche sul naming
• Se un’entità ha più punti d’accesso,
quale nome associare all’entità?
• Es. un Web service di un’azienda è
distribuito su più Web server, con
differenti indirizzi. Quale indirizzo è il
migliore?
• Occorre un nome (nell’esempio, un
nome per il Web service)
indipendente dalla posizione.
D. Rosaci
Naming
5
Identificatori
• Sono nomi aventi particolari
caratteristiche:
– Un identificatore si riferisce al massimo
ad una entità
– Ogni entità è referenziata al massimo da
un identificatore
– Un identificatore si riferisce sempre alla
stessa entità (cioè non è mai riusato)
D. Rosaci
Naming
6
Indirizzi e identificatori
• Poiché un indirizzo può essere assegnato a
più entità, non è un nome adatto per fungere
da identificatore
• Alcuni nomi sono particolarmente adatti per
essere ricordati, e quindi usati facilmente,
dalle persone: nomi human-friendly
• Questi nomi sono in genere rappresentati da
stringhe di caratteri (es. nomi DNS)
D. Rosaci
Naming
7
Legame identificatore-indirizzo
•
•
•
•
•
•
•
C’è uno stretto legame tra la risoluzione dei nomi nei SD ed il routing
dei messaggi
Un sistema di naming mantiene un collegamento nome-indirizzo per
le entità
Una tabella di coppie (nome,indirizzo) non è però adatta a realizzare
il naming dei sistemi distribuiti, che spesso si espandono in grandi
reti di calcolatori
Ciò che succede è che invece un nome viene scomposto in molte
parti, come ftp.cs.vu.nl
Un client che ha bisogno di conoscere l’indirizzo del punto di accesso
di ftp.cs.vu.nl risolverà prima nl per trovare il server NS(nl)
responsabile dei nomi relativi a nl, quindi passerà il resto del nome a
NS(nl)
Quest’ultimo risolverà il nome vu identificando il server NS(vu.nl)
responsabile dei nomi che terminano con vu.nl, e passerà il resto del
nome a NS(vu.nl)
Si continua così a procedere come sopra
D. Rosaci
Naming
8
Tre tipologie di naming
• Naming Semplice
• Naming Gerarchico
• Naming basato sugli attributi
D. Rosaci
Naming
9
Naming semplice
• In questi sistemi i nomi sono stringhe
di bit casuali, non strutturati
• Distinguiamo:
– Soluzioni semplici
– Approcci home-based
– Hash Table distribuite
D. Rosaci
Naming
10
Naming semplice: soluzioni
semplici
•
•
•
•
•
•
•
Valido per localizzare un’entità su reti locali
In tale ambito, un messaggio contenente l’identificatore del mittente è
messo in rete, ed è richiesto ad ogni macchina di controllare se
possiede l’identificatore
Principio usato nel protocollo di risoluzione degli indirizzi ARP per
trovare l’indirizzo a livello data-link di una macchina dato il solo
indirizzo IP
In ARP, una macchina mette in rete un messaggio chiedendo chi sia
il proprietario di un certo indirizzo IP. Il destinatario risponde col suo
indirizzo data-link (l’indirizzo Ethernet)
Il broadcasting diventa inefficiente man mano che la rete cresce
Alternativa: Multicasting. Solo un numero ristretto di macchine riceve
il messaggio
Es: un impiegato di un’azienda, quando entra in rete, riceve oltre
all’IP un’assegnazione ad un gruppo multicast. Se qualcuno lo cerca,
manda la richiesta al gruppo multicast, specificando l’IP
D. Rosaci
Naming
11
Naming semplice: soluzioni
semplici
• Un’altra soluzione semplice sono i puntatori
forwarding
• Quando un’entità si sposta da A a B, lascia
su A un forward alla sua nuova posizione su
B
• Quindi un client può rintracciare l’entità
seguendo la catena di puntatori forwarding
• Inconvenienti:
– Le catene possono diventare molto lunghe
– Ogni punto intermedio deve mantenere le
informazioni di forwarding
– Sistema vulnerabile all’interruzione della catena
D. Rosaci
Naming
12
Naming semplice: Hash Table
Distribuite
• Le illustriamo tramite il sistema Chord
• Chord usa uno spazio degli identificatori a m
bit per assegnare identificatori casuali ai
nodi e chiavi a specifiche entità
• Il numero di bit è di solito 128 o 160, a
seconda di quale funzione di hash viene
usata
• Un’entità con chiave k cade sotto la
giurisdizione del nodo con il più piccolo
identificatore id maggiore o uguale a k
• Questo nodo è chiamato succ(k)
D. Rosaci
Naming
13
Naming semplice: Hash Table
Distribuite
• Questione fondamentale: come risolvere la chiave k
nell’indirizzo di succ(k)?
• Approccio ovvio (e non scalabile): ogni nodo p tiene
traccia del suo predecessore pred(p) e del suo
successore succ(p+1).
• In questo caso, quando un nodo p riceve una
richiesta con chiave k, vede se pred(p)<k<=p. In
caso positivo, restituisce il suo stesso indirizzo
come risposta alla richiesta. In caso negativo,
inoltra la richiesta al suo predecessore o al suo
successore, a seconda del valore di k
• La complessità di questa ricerca è lineare
D. Rosaci
Naming
14
Naming semplice: Hash Table
Distribuite
• Chord non usa l’approccio lineare, ma un approccio fingertable
• Ogni nodo di Chord mantiene una tabella (finger table) di al
massimo m elementi
• Nella finger table Fp del nodo p ci sono memorizzati gli indirizzi
di alcuni nodi successivi a p, dove la distanza tra i nodi cresce
esponenzialmente
• Fp[i]=succ(p+2i-1), i=1,2,….
• Quindi l’i-esimo elemento punta al nodo successivo a p di
almeno 2i-1 posizioni
• Per individuare una chiave k, il nodo p stabilisce se è lui
stesso a gestire k, altrimenti vede se k ricade tra p e Fp[1] e in
tal caso gira la richiesta a Fp[1], altrimenti inoltra una richiesta
al nodo q con indice j nella finger table tale che:
• q=Fp[j-1]<k<=Fp[j]
D. Rosaci
Naming
15
Naming semplice: Hash Table
Distribuite
• La ricerca in Chord richiede solo log(N) passi, dove
N è il numero di nodi nel sistema
• In un grande sistema distribuito i nodi generalmente
entrano ed escono dal sistema continuamente
• L’entrata di un nodo in Chord è semplice. Quando p
vuole unirsi al sistema, esso contatta un nodo
arbitrario nel sistema e chiede la ricerca di
succ(p+1). Una volta che questo nodo è stato
identificato, p si inserisce nell’anello. Anche l’uscita
ha analoga semplicità
• La complessità sta nel tenere aggiornate le finger
table.
D. Rosaci
Naming
16
Naming semplice: Hash Table
Distribuite
• Occorre che ogni nodo q controlli la correttezza di
Fq[1], in quanto questo elemento si riferisce al nodo
successivo a q nell’anello, ovvero a succ(q+1).
• q deve periodicamente contattare succ(q+1) ed
eseguire una ricerca di pred(succ(q+1)). Se
q=pred(succ(q+1)) si ha consistenza, altrimenti vuol
dire che un nuovo nodo p è entrato nell’anello, e
quindi q deve aggiornare Fq[1]= a p.
• A questo punto occorre controllare che a anche p
abbia aggiornato il proprio predecessore a q.
• Controlli simili dovranno poi essere effettuati per
tutti gli altri nodi della hash table
D. Rosaci
Naming
17
Naming strutturato
• I nomi semplici si adattano bene alle
macchine, ma non all’uomo che deve usarli
con facilità e quindi memorizzarli
• Nel naming strutturato, i nomi sono
organizzati nel cosiddetto spazio dei nomi
• Lo spazio dei nomi può essere
rappresentato con un grafo orientato e
etichettato con due tipi di nodi
– Nodi foglia
– Nodi directory
D. Rosaci
Naming
18
Naming strutturato: nodi foglia
• Un nodo foglia rappresenta una data
entità e non ha archi in uscita
• In genere contiene informazioni
sull’entità (ad esempio il suo indirizzo)
da fornire ai client
• Può contenere anche lo stato
dell’entità, come nel caso dei file
system dove i nodi foglia contengono i
file veri e propri
D. Rosaci
Naming
19
Naming strutturato: nodi
directory
• Un nodo directory ha vari archi in uscita,
ognuno etichettato con un nome
• Ogni nodo directory contiene quindi una
directory table, in cui ogni elemento
rappresenta il nodo finale di un arco in
uscita e l’etichetta dell’arco
• Un nodo che ha solo archi in uscita e
nessuno in entrata è chiamato nodo root.
D. Rosaci
Naming
20
Esempio di naming strutturato
D. Rosaci
Naming
21
Percorsi di naming
• Ogni percorso N in un grafo dei nomi può essere chiamato
con la sequenza delle etichette degli archi corrispondenti al
percorso:
• N: <label-1,label-2,..,label-n>
• Il nodo N è il primo nodo del percorso
• Se il primo nodo in un pathname è il nodo root il percorso è
detto percorso assoluto, altrimenti è detto percorso relativo
• Molti spazi dei nomi sono organizzati come un albero, con un
unico nodo radice e ammettendo un solo arco in entrata per
ogni nodo
• In questi spazi, ogni nodo ha un unico pathname assoluto
• In altri spazi, è consentito che un nodo abbia più archi in
entrata, ma non vengono ammessi cicli (grafi orientati aciclici)
D. Rosaci
Naming
22
Risoluzione dei nomi
• Dato un pathname
N: <label-1,label-2,..,label-n>
• occorre recuperare tutte le informazioni associate al nodo a
cui il pathname punta
• Si inizia dal nodo N del grafo dei nodi, dove si cerca nella
directory table l’etichetta label-1 e che restituisce
l’identificatore del nodo n1 a cui si riferisce label-1
• La risoluzione quindi continua col nodo n1, cercando nella
table di n1 l’etichetta label-2 e restituendo il nodo associato
• Si arriva alla fine a restituire l’ultimo nodo del path, che è
quello cercato, insieme alle informazioni ad esso associate
D. Rosaci
Naming
23
Meccanismo di chiusura
• Un meccanismo di chiusura specifica
come e dove iniziare la risoluzione di
un nome
• Per esempio, la risoluzione di un nome
nel file system di UNIX fa uso del fatto
che la posizione del nodo root nel
disco logico che rappresenta il file
system è implicitamente conosciuta
D. Rosaci
Naming
24
Implementazione di uno spazio
dei nomi
• Lo spazio dei nomi costituisce il cuore di un
naming service
• Un naming service è un servizio che
consente agli utenti di aggiungere, eliminare
e cercare nomi
• Un naming service è implementato
attraverso uno o più name server
• Se la rete è locale, basta un solo name
server
• Se il servizio è per reti geografiche, occorre
distribuirlo su più name server
D. Rosaci
Naming
25
Distribuzione dello spazio dei
nomi
• E’ opportuno suddividere lo spazio dei nomi in livelli
logici
• Il livello globale è costituito dal nodo root e dai
nodi immediatamente vicini alla root, caratterizzati
da un alto livello di stabilità della directori table. Tali
nodi rappresentano in genere istituzioni, aziende o
gruppi di aziende
• Il livello amministrativo è costituito dai nodi che
rappresentano singole entità (es. dipartimenti) che
appartengono alla stessa unità amministrativa
• Il livello gestionale è costituito dai nodi che
cambiano più frequentemente, ad es. associati agli
host di una rete locale
D. Rosaci
Naming
26
Es: spazio dei nomi nel DNS
• Lo spazio dei nomi è suddiviso in parti non sovrapponibili,
chiamate zone del DNS
D. Rosaci
Naming
27
Distribuzione dello spazio dei
nomi: livello globale
• Una zona è implementata in un name server separato
• I name server di ogni livello devono soddisfare requisiti diversi
• I name server del livello globale devono essere altamente
disponibili (se uno di questi name server si guasta un’ampia
parte dello spazio dei nomi diventa irragiungibile)
• Visto che le directory table del livello globale non cambiano
spesso, i client possono memorizzare in memorie cache i
risultati delle ricerche. I name server possono quindi non
rispondere in tempi molto veloci alle richieste. E’ invece
necessario avere un alto throughput
• A livello globale, disponibilità e prestazioni possono essere
ottenute combinando meccanismi di caching con politiche di
replicazione dei server (entrano qui in gioco problematiche di
consistenza dei dati)
D. Rosaci
Naming
28
Distribuzione dello spazio dei
nomi: livello amministrativo
• La disponibilità di un name server a livello
amministrativo è importante per i client della stessa
azienda, ma non ha ripercussioni per gli utenti al di
fuori dell’azienda
• In merito alle prestazioni, si può fare un discorso
simili a quello fatto per i name server del livello
globale
• Tuttavia, a livello amministrativo le risposte alle
ricerche devono essere più rapidi, così come gli
aggiornamenti. E’ inaccettabile ad es. che un
account per un nuovo utente richieda delle ore
prima di essere attivato
• Di solito a livello amministrativo si usano macchine
ad alte prestazioni
D. Rosaci
Naming
29
Distribuzione dello spazio dei
nomi: livello gestionale
• A livello gestionale, i requisiti relativi alla
disponibilità sono in genere meno
impegnativi
• E’ spesso sufficiente usare una singola
macchina dedicata come name server,
correndo il rischio di temporanee
indisponibilità
• Le prestazioni a questo livello sono invece
un punto cruciale, e a causa dei continui
aggiornamenti delle directory table, le
politiche di caching sono spesso inefficaci
D. Rosaci
Naming
30
Distribuzione dello spazio dei
nomi: riepilogo
Elemento
Globale
Amministrativo
Gestionale
Scala
Globale
Azienda
Dipartimento
Numero nodi
Pochi
Molti
Moltissimi
Tempi di risposta
alle ricerche
Secondi
Millisecondi
Immediato
Propagazione
aggiornamenti
Lenta
Immediata
Immediata
Numero di repliche
Molte
Nessuna o poche
Nessuna
Applicazione
caching lato client
Si
Si
A volte
D. Rosaci
Naming
31
Implementazione della
risoluzione dei nomi
• Supponiamo per semplicità che non vi sia
replicazione dei name server né uso di
caching lato client
• Ogni client ha accesso ad un name resolver
locale, responsabile di avviare il processo di
risoluzione
• Esempio di path da risolvere:
– Root:<nl,vu,cs,ftp,pub,globe,index.html>
– URL corrispondente:
ftp://ftp.cs.vu.nl/pub/globe/index.html
D. Rosaci
Naming
32
Implementazione della
risoluzione dei nomi
• Due meccanismi di risoluzione
possibili:
– Risoluzione iterativa
– Risoluzione ricorsiva
D. Rosaci
Naming
33
Risoluzione iterativa
• Il name resolver passa al root name server (di cui conosce
l’indirizzo) il nome completo
• Nel nostro esempio, il root name server risolve l’indirizzo del
nome nl e restituisce questo indirizzo al name resolver
• Il bane resolver passa il resto del pathname, cioè
nl:<vu,cs,ftp,pub,globe,index.html> a quel name server nl
• nl può risolvere solo l’indirizzo di vu, e restituisce al name
resolver il nome del name server di vu
• Il name resover contatterà il name server di vu, che risolverà
sia l’etichetta cs sia successivamente quella ftp, e quindi
restituirà l’indirizzo del name server ftp
• A questo punto il name resolver contatterà il name server ftp,
che risolverà le etichette pub,globe e index.html, e restituendo
al name resolver l’indirizzo della risorsa (un file html) che potrà
venire trasferita dal client mediante protocollo FTP
D. Rosaci
Naming
34
Risoluzione ricorsiva
• Invece di restituire ogni risultato intermedio
al name resolver del client, il name server
contattato restituisce il risultato direttamente
al name server successivo
• L’inconveniente di questa risoluzione è che
viene richiesto a ciascun name server un
grado di prestazioni superiore
• Di solito questo carico è pesante, ed a livello
globale i name server supportano solo la
risoluzione iterativa
D. Rosaci
Naming
35
Risoluzione ricorsiva: vantaggi
• Ogni name server può gradualmente
imparare, e salvare nella sua cache, gli
indirizzi dei name server di livello più basso
• A livello globale e a livello amministrativo gli
indirizzi cambiano poco spesso, quindi il
caching è molto efficace
• Inoltre la comunicazione con la risoluzione
ricorsiva è in genere più veloce, perché il
name server contattato non deve restituire il
risultato al name resolver
D. Rosaci
Naming
36
Domain Name System (DNS)
•
•
•
•
•
•
•
•
•
•
Il DNS di Internet è uno dei più diffusi servizi di naming distribuiti oggi
in uso
E’ usato per ricercare gli indirizzi IP degli host e dei mail server
E’ organizzato gerarchicamente come un albero con radice
Un’etichetta è una stringa case insensitive, alfanumerica, della
lunghezza massima di 63 caratteri
La lunghezza di un pathname completo è limitata a 255 caratteri
La rappresentazione in forma di stringa di un nome è costituita
dall’elenco delle sue stringhe, da sinistra verso destra. La root è
rappresentata da un punto
Es:flits.cs.vu.nl. (il punto per semplicità si omette)
Dato che un nodo ha esattamente un arco in entrata, l’etichetta di
questo arco viene usata come nome del nodo
Un sottoalbero è chiamato dominio. Il path del nodo radice del
sottoalbero è chiamato nome del dominio
Il contenuto di un nodo è costituito da un insieme di resouce record
D. Rosaci
Naming
37
Tipi di resource record
Tipo
Entità associata
Descrizione
SOA
Zona
Mantiene informazioni sulla zona rappresentata (es. indirizzo email
dell’amministratore)
A
Host
Contiene l’indirizzo IP dell’host (se l’host ha più IP, avremo un record per
ogni I)
MX
Dominio
Si riferisce al mail server associato al nodo (tutte le email indirizzate a
questo nodo verranno recapitate al mail server specificato)
SRV
Dominio
Si riferisce a un server che gestisce uno specifico servizio (es. Web
server)
NS
Zona
Si riferisce a un name server che implementa la zona rappresentata
CNAME
Nodo
Link simbolico con il nome primario del nodo rappresentato (un host può
avere anche molti alias, che vengono implementati memorizzando in
CNAME il nome primario)
PTR
Host
Contiene il nome canonico dell’host. E’ usato dal DNS in nodi creati per
permettere di rintracciare il nome canonico di un host a partire dall’IP.
Questi nodi si creano aggiungeno all’IP il suffisso in-addr.arpa
HINFO
Host
Mantiene informazioni sull’host associato
HOST
Qualunque
Contiene qualunque informazione utile
D. Rosaci
Naming
38
Implementazione del DNS
• Il DNS è suddiviso solo in livello globale e livello
amministrativo. Il livello gestionale è costituito dai
file system locali e quindi non fa parte del DNS
• Ogni zona è gestita da un name server primario, di
solito replicato, che gestisce gli aggiornamenti,
modificando la base di dati locale al DNS primario
• I name server secondari di una zona non possono
accedere alla base di dati, ma chiedono il
trasferimento del contenuto al name server primario
(trasferimento di zona)
• Una base di dati del name server è implementata
come un insieme di file, il più importante dei quali
contiene i resource records di tutti i nodi della zona
D. Rosaci
Naming
39
Esempio di base di dati DNS
D. Rosaci
Naming
40
Sottodomini implementati in
zone diverse
D. Rosaci
Naming
41