Un servizio di web caching e prefetching guidato da profili d'utenza (APWebCache)

Capitolo 1: introduzione 2 
monte dei proxy. Sfortunatamente recenti studi suggeriscono che il massimo hit rate 
teorico delle cache, ossia la probabilità di soddisfare la richiesta attraverso la cache, è pari 
a 50%, cioè un documento ogni due non può essere trovato nella cache. 
Una seconda soluzione ai problemi esposti, che può contribuire ad aumentare l’hit rate 
della cache, è il prefetching. Questa tecnica consiste nel rendere disponibili le risorse 
prima che queste siano richieste, eliminando in tal modo il ritardo dovuto alla fase di 
reperimento della risorsa. L’applicazione pratica di questa tecnica comporta però diversi 
problemi, primi fra tutti l’aumento totale di traffico e la difficoltà nella determinazione 
delle richieste future, specialmente in ambito Web, attraverso un’appropriata funzione di 
predizione. 
Un’ulteriore soluzione al problema della riduzione del tempo di risposta è data, 
parzialmente, dalla tecnologia push, in cui è chi genera i contenuti a spingere le 
informazioni verso l’utente finale. Questa tecnica modifica il paradigma di interazione 
dell’utente con la rete. In questo caso l’utente sottoscrive un canale, ossia un contenitore 
di informazioni relative ad un certo argomento, ed automaticamente il sistema invia alla 
postazione dell’utente tutte le informazioni contenute nel canale stesso. Così facendo è 
possibile nascondere all’utente parte del tempo di recupero delle risorse, rendendole 
disponibili all’utente al momento stesso della loro generazione. 
Negli ultimi anni si sono susseguiti svariati studi d’integrazione di queste tecniche al 
fine di cercare di riunire in un'unica struttura i vantaggi di tecniche diverse. 
Con questo lavoro intendiamo proporre una soluzione ai problemi del tempo di risposta 
e del traffico basata sull’integrazione di differenti tecniche di ottimizzazione. 
La nostra soluzione d’integrazione, a differenza delle altre finora proposte, fa uso, oltre 
che delle tecniche citate in precedenza, anche di tecniche di personalizzazione dei servizi, 
quali i filtri collaborativi ed i profili d’utenza. 
L’idea alla base di questa proposta è che personalizzando la cache dei proxy e la 
funzione di predizione si può aumentare l’hit rate delle cache, e di conseguenza ridurre il 
tempo di risposta percepito dall’utente. 
Il sistema, inoltre, non vuole essere semplicemente un’ottimizzazione dei WWW proxy 
server ma bensì anche un sistema di supporto al lavoro di tutti coloro che utilizzano 
Internet come fonte di informazione. Per questo motivo il sistema fornisce all’utente 
anche una serie di riferimenti a documenti della rete in base agli interessi specificati 
dall’utente stesso. 
Capitolo 1: introduzione 3 
Il contributo innovativo di questo lavoro si basa appunto sul tentativo d’integrare 
tecniche provenienti da mondi differenti (quali ad esempio il caching dal mondo della 
progettazione dei computer ed il filtro collaborativo dai sistemi di marketing). 
Per far questo il sistema progettato prevede tre distinte fasi di funzionamento. La prima 
è la fase di sottoscrizione, che viene svolta, almeno in linea di principio, una volta sola, e 
nella quale l’utente fornisce al sistema una serie di informazioni a carattere personale, che 
costituiscono il profilo statico dell’utente, e che denotano gli interessi di medio e lungo 
periodo dell’utente. La seconda fase è rappresentata dall’utilizzo, da parte dell’utente, del 
servizio di caching reso disponibile attraverso un WWW proxy server commerciale. La 
terza fase, che si alternerà alla seconda nel funzionamento a regime del sistema, è 
costituita dal servizio di prefetching; quest’ultimo è finalizzato al recupero di nuovi 
documenti ed è svolto off-line, nei periodi di basso carico della rete, al fine di limitare gli 
svantaggi, in termini di traffico, di tale tecnica. 
La definizione del servizio di prefetching è un ulteriore contributo fornito dal presente 
lavoro in quanto realizzato tramite l’impiego di una apposita funzione d’integrazione di 
differenti tecniche di predizione. 
La funzione d’integrazione si basa sulla combinazione dei risultati forniti da tre diversi 
metodi di base. 
Il primo applica la tecnica dell’analisi di contesto (content based analisys) al fine di 
individuare documenti di particolare rilevanza per il singolo utente sulla base del profilo 
statico dello stesso e grazie all’ausilio delle informazioni fornite da un robot-esploratore 
che cataloga i documenti Web. 
Il secondo applica la tecnica del filtro collaborativo (collaborative filtering) al fine di 
permettere una collaborazione implicita tra gli utenti del sistema basato sulla costruzione 
di un profilo dinamico. Tale profilo è determinato dalle richieste inviate al proxy da ogni 
singolo utente. 
Il terzo metodo, infine, utilizza la tecnica di analisi statistica delle richieste per 
permettere l’aggiornamento off-line dei documenti più popolari presenti nella cache del 
proxy. 
Per valutare quest’architettura si è provveduto a realizzare un prototipo ed a testarlo 
all’interno del centro di ricerca CEFRIEL, presso il quale questo lavoro è stato svolto, 
con l’intento principale di valutare il funzionamento del sistema e di determinare le 
migliori condizioni di funzionamento. 
Infine, è da sottolineare l’indipendenza tra il proxy e la funzione di predizione realizzata 
all’interno dalla nostra architettura, in quanto ciò rende il sistema indipendente 
dall’evoluzione dei WWW proxy server. 
Capitolo 1: introduzione 4 
1.1 Organizzazione della tesi 
Il presente documento è organizzato nel seguente modo. 
Nel capitolo 2 si analizzeranno le principali tecniche di ottimizzazione del WWW 
utilizzate attualmente. In particolare, si descriveranno diffusamente le caratteristiche della 
tecnica del caching e delle sue applicazioni. Si analizzerà inoltre la tecnica del 
prefetching, impiegata per nascondere all’utente finale parte del tempo di recupero delle 
risorse, la tecnica di replicazione delle risorse, utilizzata per distribuire il carico di lavoro 
dei Web server, e la tecnica push, applicata al fine di evitare all’utente l’onerosa fase di 
ricerca e raccolta delle informazioni. 
Nel capitolo 3 si analizzeranno le principali tecniche per la personalizzazione dei servizi 
e per permettere la cooperazione tra utenti differenti. In particolare si descriverà la 
caratterizzazione degli utenti attraverso la raccolta di informazioni esplicite sui loro 
interessi e la tecnica del filtro collaborativo. 
Nel capitolo 4 si presenterà una possibile architettura per l’integrazione delle tecniche 
precedentemente analizzate al fine di ottenerne i vantaggi e ridurne le limitazioni. 
Nel capitolo 5 si descriverà il prototipo del sistema ed i dettagli della sua 
implementazione. 
Nel capitolo 6 si analizzeranno le prestazioni del prototipo al fine di valutare l’utilità del 
sistema e di determinarne le condizioni ideali di funzionamento. 
Nel capitolo 7 infine si descriveranno le conclusioni del lavoro svolto ed i suoi possibili 
sviluppo futuri. 
Capitolo 2 
Tecniche di ottimizzazione del tempo di 
risposta 
In questo capitolo si illustreranno le principali tecniche di ottimizzazione delle 
prestazioni dei sistemi informativi Internet based, in modo particolare in riferimento al 
tempo di risposta percepito dall’utente. Si parlerà quindi di caching, prefetching, 
replicazione e tecnologia push. 
2.1 Caching 
Il caching è una tecnica, che aiuta a portare una parte rilevante dei dati da elaborare in 
una posizione più prossima al luogo dove saranno manipolati. Inizialmente sono state 
utilizzate all’interno dei sistemi operativi, distribuiti e non, al fine di accrescere le 
prestazioni del file system e accelerare le operazioni di Input/Output (d’ora in poi 
semplicemente I/O). Nell’ambito di questi sistemi le tecniche e le strategie di caching 
sono state ampiamente studiate ed ottimizzate. Negli ultimi anni tali tecniche sono tornate 
prepotentemente alla ribalta in seguito allo sviluppo ed alla diffusione delle reti 
telematiche, e di Internet in particolare. Il crescente ed inaspettato, almeno in termini di 
dimensioni, successo di Internet ha determinato la riscoperta di queste tecniche di 
ottimizzazione delle prestazioni, in quanto la capillare diffusione di questa rete ha ben 
presto sovraccaricato la sua struttura determinando un rapido declino delle prestazioni. 
Per rimediare a questo problema si è deciso di applicare ad Internet il concetto di caching. 
Per quanto riguarda le applicazioni di caching ai sistemi informativi Internet based, come 
World Wide Web (WWW), sono disponibili solo una serie di studi e prove sperimentali 
molto recenti a causa della giovane età di questo settore. 
Negli ultimi anni, inoltre, le tecniche di caching hanno assunto un ruolo fondamentale 
grazie alla formalizzazione del concetto di scalabilità, divenuto nel frattempo di 
fondamentale importanza per ogni tipo di applicazione delle tecnologie informatiche. In 
questo documento si adotta la definizione di scalabilità data in [BiOl97]. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 6 
Sia n un parametro unico che misuri le dimensioni del sistema (il numero di “elementi” 
che compongono il sistema), C(n) la funzione matematica che esprime, almeno 
approssimativamente, i costi del sistema e P(n) la funzione matematica che esprime le 
prestazioni del sistema. Sotto queste ipotesi, un sistema è definito scalabile se le funzioni 
C(n) e P(n) hanno un andamento non peggiore di due funzioni di confronto C(n) e 
max
P(n), che rappresentano rispettivamente i costi massimi e le prestazioni minime. Non 
max
esiste un accordo generale su quali debbano essere le funzioni di confronto standard ma 
generalmente si utilizza il seguente criterio: 
1
 Cmax(n)= n Pmax(n) = 
log
 Funzioni di confronto standard per valutare la scalabilità di un sistema. 
Come riportato in [BiOl97], l’utilizzo delle tecniche di caching all’interno di un sistema 
informatico è una condizione necessaria per garantire la scalabilità di tale sistema. 
Il caching è una tecnica utilizzata per aumentare le prestazioni, misurabili attraverso 
vari indicatori, dei sistemi (o strutture) ai quali è applicata dato che permette di ridurre il 
traffico di comunicazioni dei sistemi a parità di utenti serviti. Una cache è spesso definita 
“un posto sicuro dove nascondere o riporre le cose” [PaHe95]. Il termine cache fu il 
nome scelto per indicare il livello della memoria gerarchica che si trovava tra la CPU e la 
memoria principale nella prima macchina commerciale che faceva uso di una gerarchia di 
memorie. Oggi questa parola è utilizzata anche per indicare ogni componente inserito per 
trarre vantaggio dalla località degli accessi (una descrizione del concetto di località si 
trova al paragrafo 2.1.1). 
Costo
Dimensione
Velocità
CPU
MaggiorePiù elevato
Più piccola
Memoria
Memoria
Memoria
Più grandePiù basso
Minore
Figura 2.1: gerarchia di memoria 
n 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 7 
La nascita dell’idea di caching è direttamente legata alla realizzazione delle gerarchie di 
memorie negli elaboratori. Una gerarchia di memoria consiste in un insieme di livelli di 
memoria, ciascuno di diversa velocità e dimensione. A parità di capacità, le memorie 
veloci sono più costose di quelle lente (figura 2.1), per questo di solito si costruiscono 
memorie veloci piccole e memorie grandi lente. 
A causa di questa differenza di costo e velocità, diventa conveniente costruire una 
memoria come una gerarchia di livelli con la memoria più veloce posta più vicina al 
processore. L’obiettivo è quello di fornire all’utente una quantità di memoria pari a quella 
disponibile nella tecnologia più economica, consentendo allo stesso tempo una velocità di 
1
accesso pari a quella garantita dalla memoria più veloce. 
Il caching è stato, poi, applicato alla progettazione di multiprocessori interconnessi 
2
tramite Bus al fine di ridurre il sovraccarico del bus stesso. In questo caso si è 
implementata la tecnologia di caching tramite una memoria ad alta velocità posta tra la 
CPU ed il Bus. La cache manteneva le parole di memoria a cui si accedeva più di recente 
e se la cache era abbastanza capiente, la probabilità di trovare la parola cercata nella 
cache, evitando quindi di effettuare una richiesta al bus, sarebbe stata alta e la quantità di 
traffico sul bus per ogni CPU sarebbe scesa. 
La probabilità di successo (hit) dell’operazione di caching, ossia la probabilità di 
soddisfare la richiesta della CPU attraverso la cache, è detta hit rate. La figura 2.2 può 
3
aiutare a chiarire l’idea alla base dell’utilizzo delle memorie cache nei multiprocessori. 
In questa figura si vede bene la localizzazione della memoria cache e la sua funzione di 
“memoria interna” alla CPU. 
CPU
CPU
Memoria
Cache
Cache
Bus
Figura 2.2: cache per CPU 
Lo stesso principio è stato poi applicato alla realizzazione dei file system dove i 
documenti utilizzati più di frequente sono tenuti nella memoria principale, anziché essere 
recuperati lentamente dal disco, con l’obiettivo di ridurre il tempo di accesso dei 
documenti. Successivamente, si sono ottenuti entrambi i vantaggi applicando il caching 
1
 Si noti che i dati sono trasferiti, di volta in volta, solo tra due livelli adiacenti. 
2
 Questo e gli esempi seguenti, se non espressamente indicato, sono descritti più estesamente in [PaHe95]. 
3
 Sono semplicemente dei calcolatori dotati di più CPU. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 8 
nei sistemi operativi di rete. In tali sistemi, i server effettua il caching dei dati per evitare 
accessi ai dischi, come nel caso del file system, ed i client mantengono una cache locale 
per evitare traffico sulla rete (come per il Bus). Ma la definitiva esplosione di questa 
tecnica, come tecnica di ottimizzazione delle prestazioni, si è avuta con i file system 
distribuiti. In questi sistemi, infatti, il caching ha assunto un’importanza cruciale al fine di 
garantirne le caratteristiche fondamentali, la più importante delle quali è la scalabilità. 
Con queste ultime due applicazione si è passati da implementazioni hardware ad 
implementazioni software del concetto di caching. 
L’ultima evoluzione delle implementazioni di tale concetto si è concretizzata 
all’interno delle reti telematiche. In questo campo si sono realizzate implementazioni, sia 
software e sia miste (Cisco cache engine [http://www.cisco.com] e CacheFlow 
[http://www.cacheflow.com]), del concetto di caching, che saranno descritte nel prossimo 
capitolo, al fine di ridurre il traffico sulla rete ed in particolare sui collegamenti (link) 
internazionali (che sono generalmente sovraccaricati). 
2.1.1 Concetti di base 
In generale, il caching funziona perché sfrutta il principio di località delle applicazioni. 
Questo principio afferma che un’applicazione, in un certo istante di tempo, accede 
soltanto ad una porzione relativamente piccola del suo spazio di indirizzamento. Ci sono 
due tipi di località: 
• Località temporale: quando si fa riferimento ad un elemento, vi è un alta probabilità 
che si faccia riferimento allo stesso elemento entro breve tempo [PaHe95]. 
• Località spaziale: quando si fa riferimento ad un elemento, vi è un alta probabilità 
che si faccia riferimento entro breve tempo ad altri elementi che hanno un indirizzo 
vicino a quello dell’elemento corrente [PaHe95]. 
La validità del principio di località si può intuire pensando, ad esempio, al fatto che 
molti programmi contengono dei cicli, le cui istruzioni ed i cui dati sono richiesti 
ripetutamente. La località temporale è alla base di tutte le implementazioni del concetto 
di caching, mentre solo alcune implementazioni, ad esempio le cache per i processori, 
sfruttano la proprietà di località spaziale dei programmi. Per far questo, infatti, occorre 
4
utilizzare cache con blocchi di memoria di dimensione maggiore dell’unità di memoria. 
4
 Si intende qui con unità di memoria l’oggetto di riferimento nelle procedure di caricamento e rimozione 
delle pagine nei processori. L’unità di memoria può essere una parola (come nei processori) od un insieme 
di documenti (come nel caso del Web caching in cui si salvano nella cache oggetti composti da più file, di 
solito immagini e testi). 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 9 
È evidente come questa seconda proprietà possa essere utilizzata unicamente nel caso di 
caching di blocchi di file e non di file interi, dato che non è possibile stabilire facilmente 
legami tra file differenti. 
2.1.2 Architetture di caching 
Si è già accennato all’interno del paragrafo 1.1 ad alcune architetture utilizzate nelle 
prime applicazioni del concetto di caching, soprattutto nell’ambito della progettazione dei 
sistemi multiprocessori. In particolare, si è mostrato con la figura 1 come è strutturata una 
gerarchia di memoria, nella quale solitamente il livello più vicino al processo è 
implementato con una memoria cache, e con la figura 2.2 un’implementazione hardware 
del concetto di caching nei calcolatori a più processori. In questo paragrafo descriviamo 
architetture di cache più sofisticate e non necessariamente hardware. La necessità di 
definire architetture complesse nasce dalla volontà di applicare il concetto di caching a 
strutture più estese dei calcolatori (quali le reti telematiche), in cui l’organizzazione delle 
informazioni riveste quindi un’importanza cruciale al fine di ottenere prestazioni 
accettabili, dato che la vastità delle strutture impone tempi di recupero degli oggetti più 
lunghi. 
a) Cache singole: l’architettura più semplice di caching è quella composta da una cache 
autonoma ed isolata sulla singola postazione (come per i processori, figura 2.2), 
intesa come stazione di lavoro o terminale, o su ogni singolo client che viene eseguito 
sulla postazione. In questo modo ogni singola postazione può limitare il proprio 
traffico di rete. Si può pensare, ad esempio, ad una rete locale costituita da un server e 
da un certo numero di postazioni client che utilizzano tale server. Le varie postazioni 
possono usufruire di un proprio servizio di caching per limitare le comunicazioni con 
il server. 
Una struttura di questo tipo però porta inevitabilmente ad una duplicazione di 
risorse che, a lungo andare, può rivelarsi molto onerosa (si pensi alla quantità di 
informazioni duplicate, memorizzate nelle varie cache, che hanno generato traffico 
parzialmente evitabile). Inoltre, può capitare che la cache di una postazione disponga 
del documento cercato dalla cache di un’altra postazione ma quest’ultima sia costretta 
a generare un cache miss (si ha un cache miss quando la cache non è in grado di 
soddisfare una richiesta) dato che le due non possono comunicare. Un’architettura di 
questo tipo presenta il vantaggio della semplicità ma è difficilmente applicabile a 
strutture molto estese, come quelle tipiche delle applicazioni distribuite, a causa della 
sua ridotta efficienza in termini di traffico. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 10 
Quest’architettura può essere applicata in svariati modi grazie alla sua semplicità. 
Si può utilizzare, nell’ambito dei sistemi operativi, all’interno dei singoli processi 
client (figura 2.3a), attraverso un processo di gestione della cache (figura 2.3b) che 
fornisca il servizio a tutti i client o si può implementare a livello di postazione 
all’interno delle reti (figura 2.3c), in maniera tale da rendere il servizio trasparente ai 
vari client. Nel primo caso si può vedere dalla figura come ogni client provveda a 
gestire autonomamente la propria cache, realizzata all’interno del proprio spazio. Nel 
secondo caso, invece, il processo di gestione della cache interagisce autonomamente 
con il disco al fine di fornire ai vari processi client il servizio di caching, qualora 
questi lo richiedano. I client non sono obbligati a far uso del caching ma possono 
anche funzionare senza questo servizio interagendo direttamente con il disco 
attraverso il file system. Così facendo si ha il vantaggio che la cache sopravvive alla 
morte dei processi client. Nel terzo caso, il caching è realizzato sulle postazioni client 
di una rete (locale o meno) direttamente all’interno del sistema operativo di rete di 
ogni postazione (è per questo motivo che i client interagiscono con la cache e non con 
5
il disco della postazione). In questo caso, attraverso la cache è possibile recuperare 
documenti del server senza accessi alla rete. 
(a)(b)
Server
(c)
Figura 2.3: applicazioni di cache singole. a) cache all’interno dei singoli client, b) cache come processo 
autonomo di gestione e c) cache a livello di postazione. 
5
 Il tutto ovviamente avviene tramite il file system che nasconde ai client la presenza della cache. Nella 
figura è evidenziata la cache per mostrare dove è realizzata. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 11 
b) Cache gerarchiche: una prima evoluzione della struttura precedente, che accresce 
l’efficienza e di conseguenza riduce i costi a parità di prestazioni, si ha con l’utilizzo 
del concetto di gerarchia introdotto per le memorie (figura 2.1). Utilizzando una 
gerarchia si possono avere ottenere vantaggi in termini prestazionali. 
Una cache gerarchica [Co96], ad esempio organizzata con livelli a base geografica, 
può servire molti più utenti ed avere molti più accessi della cache locale. Se 
posizionate strategicamente, queste cache possono avere grandi capacità di 
memorizzazione e collegamenti di rete molto veloci, così che l’accesso alle loro 
informazioni risulti veloce almeno quanto gli accessi in una rete LAN. Queste cache 
potrebbero inoltre essere utilizzate come punto di distribuzione dove gli “editori” 
automaticamente depositano le informazioni. Intercettando richieste analoghe di 
utenti diversi, un cache server (o proxy) può essere in grado di soddisfare le richieste 
di più utenti attraverso una sola connessione con il sito remoto, nell’ipotesi che tali 
richieste giungano al proxy in un breve lasso di tempo, cosi che la copia del 
documento nella cache possa ritenersi ancora conforme con l’originale. Per ottenere 
la maggior riduzione di traffico sulla rete, la raccolta di richieste individuali dovrebbe 
essere eseguita il più vicino possibile agli utenti. Quando una cache riceve una 
richiesta, questa è confrontata con le richieste recenti. Se una richiesta per quel 
documento si è già verificata, allora la cache restituisce la propria copia del 
documento. 
Il vantaggio nell’uso di una gerarchia di cache si ha quando accadono cache miss; in 
tal caso, infatti, le varie cache possono passare le proprie richieste inevase al livello 
superiore della struttura così da recuperare l’oggetto desiderato da una postazione 
comunque più vicina rispetto al server proprietario dell’oggetto. In questo modo è 
possibile costruire una gerarchia dove ogni livello “serva” una comunità molto vasta 
di utenti. I vantaggi principali di quest’architettura sono perciò la possibilità di 
aggregare un alto numero di utenti e la possibilità, che ogni cache ha, di sfruttare la 
cache di livello superiore (il genitore) in modo tale da accrescere la capacità di 
memorizzazione della singola cache. Il problema principale di questa struttura è il 
6
costo della replicazione delle informazioni nelle cache e l’overhead generato dalla 
gerarchia. Per cache semplici la larghezza della gerarchia è un problema serio dato 
che cache allo stesso livello non possono comunicare tra loro e quindi la duplicazione 
dei dati non può essere attenuata dalla collaborazione. 
6
 Il problema riguarda unicamente le cache dello stesso livello, dato che la struttura gerarchica può 
collaborare verticalmente ma non orizzontalmente, come si può osservare nella figura 2.4. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 12 
Una schematizzazione di quest’architettura è riportata in figura 2.4. Tale figura 
evidenzia l’architettura gerarchica della soluzione e le varie interazioni tra i vari 
oggetti che compongono la gerarchia. Le postazioni che si trovano al secondo livello 
della gerarchia non possiedono una memoria cache dedicata, come le postazioni di 
primo livello, dato che sono postazioni dedicate a fornire esclusivamente il servizio di 
caching ed utilizzano, quindi, come supporto di memorizzazione per la cache l’intero 
disco della postazione. Queste cache di secondo livello si possono pensare come 
cache regionali che servono, quindi, tutti i client attivi sulle varie postazioni della 
regione di competenza. Come si può osservare dalla figura, sono le singole cache che 
possiedono l’informazione sulla gerarchia e la rendono trasparente al singolo client. 
Server
Figura 2.4: schematizzazione di una gerarchia di cache. 
c) Cache cooperanti o rete di cache (Cache Mesh): è, attualmente, l’ultima 
evoluzione delle architetture di caching, introdotta per rendere le implementazioni 
del caching nelle reti di telecomunicazioni più efficienti. È stata introdotta dal 
7
progetto Harvest [ChDa96] [Ha96] dell’università del Colorado che ha anche 
sviluppato l’Internet Cache Protocol (ICP) [WeCl97], descritto nell’appendice B, 
7
 Questo progetto concentra la propria attenzione sul mondo Internet e del World Wide Web. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 13 
per supportare questa architettura (ultimamente si è proposto il Cache Array 
Routing Protocol (CARP) [Va97] [Ro97], descritto nell’appendice C, come 
alternativa a ICP per supportare questa architettura). 
L’architettura delle cache cooperanti, illustrata nella figura 2.5, è una evoluzione 
della gerarchia illustrata al punto b) ed introduce una nuova “figura” nella 
struttura, denominata sibling. La relazione che istituisce una famiglia di sibling si 
affianca alla relazione di discendenza, che determina legami del tipo padre–figlio 
(parent-son), per permettere ai vari oggetti dell’architettura di colloquiare anche 
orizzontalmente (ossia consente a proxy appartenenti allo stesso livello gerarchico 
di interagire tra loro). Da notare che, teoricamente, la nuova relazione potrebbe 
collegare cache di livelli differenti. La selezione del sibling con cui colloquiare 
può essere fatta tramite un confronto fra le specifiche della richiesta da soddisfare 
e le caratteristiche dei vari sibling, alcuni dei quali potrebbero applicare strategie 
di aggregazione di dominio o tematiche (vedi paragrafo 1.1.2) dei documenti. Si è 
quindi passati dalla struttura ad albero, tipica delle gerarchie, a quella a grafo. 
Tuttavia, i software che consentono di gestire una struttura di questo tipo 
differenziano l’utilizzo delle due relazioni, al fine di evitare cicli infiniti (loop). 
La relazione di discendenza è, solitamente, utilizzata per risolvere cache miss 
mentre i sibling sono utilizzati per bilanciare il carico tra le varie cache della 
8
struttura. Attualmente ICP è supportato solo dai software di cache che hanno 
avuto origine con il progetto Harvest. 
Il funzionamento di questa struttura è, ovviamente, leggermente più complesso 
di quello delle architetture precedenti. Ogni proxy che appartiene alla rete di 
cache possiede l’elenco dei propri sibling, a cui può inviare messaggi IPC, e del 
proprio proxy-padre del livello superiore della gerarchia. Quando una richiesta ad 
un proxy della struttura genera un cache miss, il proxy stesso invia, in parallelo, 
un messaggio ICP ai propri sibling (e’ anche possibile indirizzare i messaggi ICP 
sulla base delle caratteristiche della richiesta che ha generato il cache miss). 
• Se il proxy riceve, da almeno un sibling, una risposta affermativa (il sibling 
può soddisfare la richiesta) allora avvia il recupero dell’oggetto tramite una 
normale connessione con il primo sibling che ha risposto affermativamente. 
Se l’oggetto della richiesta è di dimensioni ridotte, allora può essere spedito 
8
 Un scelta di questo tipo è stata fatta in SQUID [Sq97]. Ulteriori dettagli si possono trovare in [MeSl97]. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 14 
9
dai sibling al proxy direttamente con il pacchetto ICP di risposta ed in questo 
caso non è necessaria la normale connessione HTTP. 
• Se, al contrario, il proxy non ottiene nessuna risposta positiva dai sibling 
allora inoltra la richiesta al livello superiore della gerarchia proprio come 
avveniva nella struttura gerarchica discussa al punto b). 
Una gerarchia di parent e sibling implementata con ICP è molto meno rigida 
dell’albero imposto dalle cache gerarchiche. La capacità di inviare richieste 
multiple ai sibling dà accesso ai documenti memorizzati dai cache server dello 
stesso livello gerarchico. È appunto questa la differenza sostanziale tra cache 
cooperanti e cache semplici. Da notare che un proxy può essere configurato per 
mantenere copie locali degli oggetti ottenuti dai sibling, oppure può 
semplicemente “spedire” a questi ultimi le successive richieste per tali oggetti. 
Quest’ultima opzione riduce notevolmente la quantità di repliche dei documenti e 
le richieste di disco di ogni cache server, ma incrementa la quantità di traffico tra 
gli stessi. Le cache cooperanti non hanno effetto quando il documento è trovato 
nella cache di primo livello. 
Il vantaggio principale di quest’architettura è l’aumento della probabilità di 
trovare una copia del documento più vicino, al richiedente, dell’originale 
(attraverso la relazione sibling che aumenta il numero di proxy con cui 
colloquiare) e, di conseguenza, la riduzione del traffico sulla rete. Gli svantaggi 
sono la complessità di gestione di una struttura a grafo ed il pericolo che si 
verifichino dei cicli in fase di “risoluzione” della richiesta. 
Nella figura 2.5, che mostra l’architettura delle cache cooperanti, non si sono 
distinte, nella rappresentazione, le due relazioni dato che concettualmente tale 
distinzione non esiste. La nuova relazione, infatti, è direttamente legata alla 
rimozione del vincolo alla base della gerarchia, ossia relazioni unicamente di 
discendenza. La struttura mostrata in figura è articolata in cache nazionali, 
regionali e locali (sempre in termini geografici) ma questa, pur essendo la 
suddivisione più diffusa, non rappresenta un limite del modello, il quale è 
applicabile anche a suddivisioni differenti (ad esempio per aggregazioni 
tematiche, vedi paragrafo 2.1.3). 
9
 I pacchetti ICP possiedono un certo numero di blocchi dati che, all’occorrenza, possono essere utilizzati 
per trasferire informazioni (poche) tra i soggetti che instaurano la connessione. 
Capitolo 2: tecniche di ottimizzazione del tempo di risposta 15 
ServerServer
Cache nazionaliCache regionali
Postazioni client con cache locale
 Figura 2.5: rete di cache cooperative. 
A questo punto, si possono illustrare tre criteri generali validi per le ultime due strutture 
descritte, individuati in [Ma96], ai quali deve soddisfare un software di supporto al 
caching al fine di poter essere utilizzato sia in una struttura di cache cooperanti e sia in 
una struttura gerarchica. I tre criteri sono: 
1) ogni server deve essere in grado di cooperare con tutti gli altri server della struttura 
alla quale è direttamente connesso, ossia tutti i server raggiungibili con un cammino 
di lunghezza unitaria; 
2) il server realizzato deve essere scalabile almeno di un fattore 100; 
3) il sistema di server deve essere resistente ai guasti, ossia robusto. 
Analizzando brevemente i tre criteri si può affermare che: il primo richiede capacità di 
comunicazione con gli altri server della rete (meglio se tramite ICP), il secondo richiede 
garanzie di scalabilità ed il terzo richiede una certa flessibilità ai fallimenti.