Università “G.D’Annunzio” Pescara
Facoltà di economia
Corso di laurea specialistica in Economia Informatica
FUNZIONAMENTO E DIFFERENZE TRA
PROTOCOLLI DI
CACHING COOPERATIVO
(ICP,HTCP,CD,CARP)
Seminario per il corso di
“RETI DI CALCOLATORI E SICUREZZA” ’05/’06
Docente: Stefano Bistarelli
Studente: Caniglia Maria Giacinta
Caniglia Maria Giacinta
1
SOMMARIO

Introduzione (Web caching e web replication);

Protocolli:
•
ICP: caratteristiche, implementazione, applicazioni e problematiche;
HTCP: caratteristiche, implementazione, applicazioni e problematiche ;
•
CD: caratteristiche, implementazione, applicazioni e problematiche ;
•
CARP: caratteristiche, implementazione, applicazioni e problematiche;
•

Conclusioni: confronti tra i protocolli
Caniglia Maria Giacinta
2
INTRODUZIONE
La crescente richiesta di servizi Internet e, soprattutto,
l’enorme numero di accessi a dati e servizi resi disponibili
da web server hanno determinato un considerevole
aumento del traffico di rete che, in alcuni casi, può
provocare il congestionamento delle linee di trasmissione
con conseguente degrado nelle prestazioni. Per cercare di
limitare questi problemi, vengono comunemente utilizzate
due differenti tecnologie: Web Replication (USA) e Web
Caching (Europa). Entrambe le tecnologie cercano di
ridurre il fenomeno della congestione della rete e di
migliorare la qualità del servizio, ma utilizzano approcci
diversi.
Caniglia Maria Giacinta
3
WEB REPLICATION
Web Replication si basa sul concetto di ridondanza.
Più server web, dislocati in differenti aree geografiche offrono
gli stessi servizi replicando, totalmente o solo in parte, dati e
software disponibili in un particolare sito. Gli obiettivi sono:
ridurre il traffico indirizzato a server con alta frequenza di
accessi, diminuendo il carico computazionale della macchina
che offre tali servizi, e dare all’utenza un servizio migliore,
consentendo l’accesso a delle repliche che hanno una migliore
“connessione”.
Questa tecnica non riduce effettivamente il traffico di rete, ma
lo ripartisce su differenti cammini, dirigendo le richieste verso
server distribuiti che replicano dati e servizi.
Caniglia Maria Giacinta
4
WEB CACHING
Web Caching indica la memorizzazione temporanea di pagine
web in locazioni più vicine al richiedente (cache server)
rispetto alla sorgente dell’informazione (originweb server). In
tal modo, richieste successive dello stesso oggetto possono
essere soddisfatte direttamente dal cache server, riducendo il
tempo che trascorre tra la richiesta e la disponibilità
dell’oggetto, cioè la latenza. Abbreviando il cammino di rete
degli oggetti Internet, la tecnologia di web caching ottimizza
l’utilizzo della banda trasmissiva, riduce il traffico sulla
rete, e migliora la qualità del servizio offerto all’utente. Ma,
di contro, può comportare problemi di inconsistenza tra
l’oggetto originale e le copie temporanee.
Le macchine che offrono il servizio di cache possono operare
in modalità stand-alone (non c’è l’interazione tra le caches)
oppure possono cooperare.
Caniglia Maria Giacinta
5
CACHING COOPERATIVO
La cooperazione tra cache può essere:
PARENT:subordinazione gerarchica
SIBLING: i server agiscono allo stesso
livello, la cooperazione è
distribuita;
Caniglia Maria Giacinta
6
ICP
INTERNET CACHE
PROTOCOL
Caniglia Maria Giacinta
7
ICP :storia…
Nel 1994 nasce e viene sviluppato come parte fondamentale
del progetto Harvest ed è stato il 1° protocollo intercache.
Nel 1995 da Harvest vengono creati 2 nuovi progetti: Netcache
e Squid cache che apportano delle modifiche all’ICP.
Nel 1997, visto il notevole uso di Squid e Netcache, si
adottano 2 documenti (rfc2186-2187) che descrivono la
versione 2 del protocollo.
Caniglia Maria Giacinta
8
ICP: caratteristiche

OBBIETTIVO : determinare la presenza di determinati oggetti
nelle cache vicine ;
Non permette di testare la
congestione della rete
anche se può fornirne une
stima
E’ basato su UDP
 Offre la funzionalità di selezione delle cache:
i massaggi ICP possono contenere informazioni utili per la scelta
della sorgente migliore per un oggetto.
 E’ molto diffuso
Caniglia Maria Giacinta
9
ICP: funzionamento
Le fasi di una transazione ICP
sono:
1. La cache locale riceve una
richiesta HTTP dalla cache
del client;
2. La cache locale invia la
query ICP alle altre cache
(parent o sibling);
3. Le cache ricevono la query e
inviano la risposta;
4. La cache locale riceve la
risposta e la invia al client.
Caniglia Maria Giacinta
10
ICP: formato messaggio
Ogni messaggio è formato da 20 byte fissi che sono l’intestazione
più una parte variabile che è il payload.
Identificatore che deve
essere copiato nella
risposta
Il suo contenuto dipende
dal tipo di messaggio
Caniglia Maria Giacinta
11
ICP: tipologie di messaggi
Value Name
Description
0
ICP_OP_INVALID
non è inviato intenzionalmente, non ha campi
1
ICP_OP_QUERY
è il messaggio di richiesta dell’oggetto
2
ICP_OP_HIT
3
ICP_OP_MISS
4
ICP_OP_ERR
è la risposta inviata dai server che hanno nella
loro cache l’oggetto richiesto
è la risposta inviata nel caso non si ha
l’oggetto
indica il tipo di errore in cui si è incorso
Caniglia Maria Giacinta
12
tipologie di messaggi (…segue)
… ci sono alcuni opcode che sono in disuso come ad esempio
ICP_OP_SECHO e ICP_OP_DECHO.
Inoltre bisogna fare un discorso a parte per il tipo ICP_HIT_OBJ
che è tipo un HIT solo che contiene anche l’oggetto richiesto, il
trasferimento avviene senza la richiesta HTTP questo permette di
risparmiare tempo e banda.
Però lo stesso rfc sconsiglia l’uso di questo opcode perché in esso
manca l’header HTTP e perché si può rischiare la frammentazione
del messaggio e la perdita di pezzi.
Caniglia Maria Giacinta
13
ICP: applicazioni
Sono elencate nell’rfc 2187 tra le principali:
 Harvest prima Squid poi;
 Network appliance;
 Cisco cache engine;
 Volera;
 Ecc…
Caniglia Maria Giacinta
14
ICP : problematiche

Ritardi: dipendono da quanto sono distanti le cache e dalla
% di risposte che sono hits.

Larghezza di banda: una transazione ICP occupa circa
160 byte senza includere le intestazioni UDP e IP.

False hits: nel pacchetto ICP non è incluso l’header HTTP
che darebbe informazioni importanti sul pacchetto.

Uso di UDP
Caniglia Maria Giacinta
15
ICP : problematiche (…segue)


Query per oggetti “uncachable”
Unwanted query: riguarda il fatto che potrebbero
configurare il nostro sito come un “vicino” senza il nostro
permesso rallentando il traffico,per evitare ciò dobbiamo
configurare la nostra cahe in modo che risponda con
ICP_OP_DENIED.


Scalabilità
Uso di ICP_OP_OBJ
Caniglia Maria Giacinta
16
HTCP
Hyper Text Caching
Protocol
Caniglia Maria Giacinta
17
HTCP: caratteristiche









Protocollo di comunicazione inter-cache nato per colmare le carenze
dell’ICP, è ancora sperimentale ed è regolato dall’rfc 2756
Include nel pacchetto l’header HTTP: supporta l’autenticazione
Ha segnato il passaggio da HTTP/1.0 a HTTP/1.1
Permette di gestire insiemi di cache e monitorarne le attività in tempo
reale
È supportato da pochi prodotti
Con esso si può chiedere ad una cache di cancellare o modificare un dato
oggetto
Il suo messaggio ha una struttura complessa
Usa UDP per il trasporto
Causa un notevole overhead sulla rete
Caniglia Maria Giacinta
18
HTCP: formato messaggio
Un messaggio HTCP ha 3 sezioni fondamentali:
1. HEADER: indica la lunghezza del messaggio e la
versione del protocollo, occupa 4byte.
Caniglia Maria Giacinta
19
HTCP: formato messaggio (…segue)
2. DATA: consiste in 8 campi di lunghezza variabile, è il
messaggio vero e proprio e cambia al variare
del tipo di messaggio.
È diverso da length dell’header
Indica il tipo di
errore nelle
risposte
Identifica in modo univoco
La transazione HTCP
Distingue tra query (=0)
e risposta (=1)
Flag di un bit che se vale 1
in una query vuol dire che si
vuole la risposta.
Caniglia Maria Giacinta
20
HTCP: formato messaggio (…segue)
3. HUTH:serve a garantire un certo livello di sicurezza tale
che un messaggio non possa essere “spoofed” da
terzi.
Ora in cui è generata la “signature” è
espressa in numero di secondi
trascorsi dallo “unix-time” che è il
01/01/1970
Scadenza chiave
Nome della chiave che verrà usata
dall’algoritmo HMAC-MD5
Caniglia Maria Giacinta
21
HTCP: tipologie di messaggi
HTCP 0.0 definisce 5 opcode:

NOP (null operation)
è simile ad un ping è usato per vedere i ritardi della rete tra
cache;

TST
testa l’esistenza di un oggetto nella cache vicina ,nelle query,
nelle risposte vale 0 se l’oggetto è presente, 1altrimenti.

MON (monitor opcode)
con esso la cache informa le altre sugli oggetti che ha aggiunto,
modificato o cancellato.
Caniglia Maria Giacinta
22
HTCP: tipologie di messaggi (…segue)

SET
permette ad una cache di spingere le altre a delle modifiche
attraverso una query, nella risposta ci sarà un codice che vale 0
se la richiesta è stata accettata, altrimenti è 1.

CLR (Clear opcode)
è usato per indicare che un vicino ha rimosso dalla sua cache
un oggetto, questa caratteristica è utile per vedere se un
oggetto è stato eliminato dal server originario
Caniglia Maria Giacinta
23
HTCP: problematiche


Complessità del messaggio
Precisione o velocità?
La transazione HTCP può includere l’intestazione http e
questo comporta un elevato utilizzo di tempo e memoria perciò
il sever in ogni momento deve scegliere se inviare header
parziali o totali.


Scalabilità
Uso dell’UDP
Caniglia Maria Giacinta
24
CD
CACHE DIGEST
Caniglia Maria Giacinta
25
CD: caratteristiche






E’ un nuovo protocollo che affronta i problemi della latenza e
della congestione legati all’ ICP e all’HTCP
Consente il peering tra cache senza ricorrere allo scambio
query/reply
Permette ai peer di mantenere un sommario: “DIGEST” del
contenuto delle cache con cui hanno relazioni
I digest possono esistere come oggetti cacheati quindi soggetti
alle stesse regole dei comuni oggetti di cache
Riduce la % di “miss” e il ritardo di lookup
Al momento è usato solo da Squid nella sua versione 5.
Caniglia Maria Giacinta
26
CD: formato messaggio
Un messaggio CD è formato da un intestazione di 128-byte
seguita da un Bloom filter di dimensioni variabili, la struttura
dell’header è:
Stima del n° di oggetti contenibili
nel digest
N° di oggetti codificati nella lista
Tiene traccia degli oggetti rimossi dalla
cache da quando è stata creata la lista
Contatore del numero di funzioni
hash usate nel Bloom Filter
Caniglia Maria Giacinta
27
CD : Bloom Filter
E’ un algoritmo che codifica un set di dati con l’aiuto di una funzione hash. E’
definito da due parametri : K funzioni hash e un array di M bit.
I bit del filtro sono usati per codificare in modo efficiente un insieme di
oggetti, nel caso di CD gli URL.
Per costruire un Bloom filter si scorrono gli oggetti dell’insieme applicando ad
ognuno le K funzioni hash e ottenendo K valori che rappresentano un bit di
posizione nel filtro che può essere acceso o spento.
Se K>M applico il modulo per far rientrare il valore nei limiti
Se K<M vuol dire che ci saranno bit che non verranno mai accesi
Possiamo dire quindi che un filtro è una sequenza di 1 e 0 in Squid e anche
detto Bitmap dove se il bit è 1 vuol dire che l’oggetto è in memoria, 0
altrimenti.
Caniglia Maria Giacinta
28
CD: implementazione
Comprende:
1. KEYS: dati ai quali è applicata la funzione hash, è
un identificatore unico per ogni oggeto in cache, la
sua struttura è:
Caniglia Maria Giacinta
29
CD: implementazione (…segue)
2. FUNZIONE HASH: algoritmo che prende dei dati
in input (key) e produce un intero per output.
3. DIMENSIONAMENTO DEI FILTRI:
consiste nel dare un valore ad M è un passo importante
perché se M troppo piccolo si ha una % più alta di
insuccesso, se M troppo grandi si avranno nel filtro dei bit
sempre a zero quindi spazio sprecato.
4. SELEZIONE OGGETTI PER LA LISTA:
non tutti gli oggetti sono inseriti nella digest
5. SCAMBIO DEI DIGEST : si usa HTTP
Caniglia Maria Giacinta
30
…riassumendo
CD, oggi, è supportato solo da Squid le cache
che lo usano periodicamente si scambiano una
sorta di riassunti sugli oggetti che contengono.
Tali riassunti non sono né un elenco di URL né
l’hashing di URL ma dei “filtri” che sono il
risultato dell’algoritmo Bloom Filter.
Il bitmap o filtro è disponibile ad altre cache
con una connessione HTTP ad un determinato
URL.
Caniglia Maria Giacinta
31
CD: problematiche

Scalabilità

Complessità nella costruzione dei digest

Mancanza di documentazione

Scarsa diffusione
Caniglia Maria Giacinta
32
CARP
Cache Array Routing
Protocol
Caniglia Maria Giacinta
33
CARP : caratteristiche






Sviluppato dalla Microsoft come parte dei propri prodotti proxy server
Da molti non è considerato un vero e proprio protocollo ma un algoritmo
È utile nelle architetture piatte di cache dove sono presenti dei cluster di
macchine perché con l’uso di una funzione hash permette di condividere lo
spazio delle URL tra più cache.
Ottimizza le prestazioni del sistema: le richieste fatte dai client sono
ripartite in modo uniforme tra più macchine in modo da evitare la
duplicazione degli oggetti nei server.
Le sue regole forniscono un metodo veloce ed efficiente per creare insiemi
di web cache (array), gestirne la comunicazione, bilanciare il carico del
server massimizzando la % di Hit e minimizzando la latenza.
Ha la proprietà di lineare scalabilità: lo score è calcolato per ogni membro
del gruppo.
Caniglia Maria Giacinta
34
CARP: implementazione
Comprende 2 fasi principali:

DEFINIZIONE DELLA TABELLA DEI
MEMBRI (proxy array membership)

FUNZIONE DI ROUTING
Caniglia Maria Giacinta
35
PROXY ARRAY MEMBERSHIP
Un esempio può essere:
Proxy Array Information/1.0
ArrayEnabled: 1
ConfigID: 12345
ArrayName: My-Array
ListTTL: 3600
INFORMAZIONI
GLOBALI
proxy1.isp.net 10.2.3.4 3128 http://proxy.isp.net/carp.txt
SmartCache-v1 21600 UP 1 2048
proxy2.isp.net 10.2.3.5 3128 http://proxy.isp.net/carp.txt
SmartCache-v1 20127 UP 1 2048
proxy3.isp.net 10.2.3.6 3128 http://proxy.isp.net/carp.txt
SmartCache-v1 22928 UP 1 2048
Caniglia Maria Giacinta
LISTA
MEMBRI
36
PROXY ARRAY MEMBERSHIP (..segue)
Nome del dominio del proxy
Indirizzo dove si trova la
copia corrente della tabella
di array
proxy1.isp.net 10.2.3.4 3128 http://proxy.isp.net/carp.txt
SmartCache-v1 21600
UP 1 2048
Cache size
Venditore e versione
Load factor
State time
Caniglia Maria Giacinta
37
Funzione di routing
E’ un algoritmo che calcola un punteggio (score) per ogni
membro dell’array in modo che quando si effettua la richiesta
questa è inoltrata solo ai membri con score più alto.
Lo score si calcola attraverso 3 valori:



Hash dell’URL;
Hash del nome della cache
Peso della cache
Caniglia Maria Giacinta
38
CARP: applicazioni
La principale applicazione si ha nei sistemi di
webcache Microsoft Proxy & ISA Server
Squid lo usa solo come client per selezionare
un membro dell’array non è in grado di
partecipare in modo attivo all’array.
Caniglia Maria Giacinta
39
CARP: problematiche




Non predice i cache hits
Può essere usato solo da alcuni web client
Mancanza di documentazione
Scalabilità
Caniglia Maria Giacinta
40
CONCLUSIONI
CHE
PROTOCOLLO
USARE?
Caniglia Maria Giacinta
41
CONCLUSIONI
La scelta del protocollo da usare dipende da molti fattori, ci
sono una serie di “linee guida” che possono aiutare a scegliere
il migliore.
ICP
SE si ha bisogno di far
inter-operare le cache di
prodotti diversi
SE si vuole costruire
una “rete” di cache
Caniglia Maria Giacinta
42
CONCLUSIONI
SE siamo interessati
alla sicurezza
SE la rete presenta
dei ritardi o una
elevata congestione
SE c’è un firewall
NO
ICP
Caniglia Maria Giacinta
43
CONCLUSIONI
HTCP è simile a ICP solo che ha una % di
false hit più bassa e offre l’autenticazione.
Di contro però i messaggi HTCP occupano
molta banda: circa 5 volte in più di un
messaggio ICP
Caniglia Maria Giacinta
44
CONCLUSIONI
E’ consigliabile usare CD quando si vuole
rendere possibile lo scambio di contenuti tra le
memorie senza incorrere in elevati ritardi.
E’ sconsigliato l’uso di CD su connessioni
lente perché il trasferimento saturerebbe il
link.
Caniglia Maria Giacinta
45
CONCLUSIONI
CARP è la scelta logica quando si hanno
gruppi di cache amministrati da una singola
organizzazione.
Carp non permette creare una sibling
relationship.
Caniglia Maria Giacinta
46
RIFERIMENTI




“Web Caching” Duane Wessels -O’Reilly -Edizione 2001
www.rfc-editor.org
www.squid-cache.org
“Free software per web caching” Laura Abba, Marina Buzzi,
Francesco Gennai, IAT- CNR Pisa Massimo Ianigro Area della
Ricerca CNR Bari

www.ircache.net
Caniglia Maria Giacinta
47