ALMA MATER STUDIORUM · UNIVERSITÀ DI BOLOGNA
`
`Facoltà di Scienze Matematiche, Fisiche e Naturali
`Corso di Laurea Specialistica in Informatica
`
`MECCANISMI SCALABILI DI ACCESSO A
`CONTENT DISTRIBUTION NETWORK:
`UNO STUDIO SPERIMENTALE
`
`Tesi di Laurea in Sistemi Middleware
`
`Relatore:
`Chiar.mo Prof.
`FABIO PANZIERI
`
`Presentata da:
`MARCO COCCIARINI
`
`Parole chiave: Servizi Web, PlanetLab, Load Balancing, Overlay Networks, Scalabilità
`
`Sessione I
`
`AnnoAccademico2004-2005
`
`Microsoft Ex. 1038, p. 1
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Microsoft Ex. 1038, p. 2
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`Microsoft Ex. 1038, p. 2
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`A. . .
`mia madre Rosalba, mio padre Ezio, mia sorella Laura
`ed alla memoria di Emil.
`
`Microsoft Ex. 1038, p. 3
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Microsoft Ex. 1038, p. 4
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`Microsoft Ex. 1038, p. 4
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Indice
`
`Introduzione
`
`1 Lo stato dell’arte
`1.1 Cenni sul protocollo HTTP . . . . . . . . . . . . . . . . . . . . . . . . .
`1.1.1
`Struttura del protocollo . . . . . . . . . . . . . . . . . . . . . . .
`1.1.2 Le richieste HEAD e GET . . . . . . . . . . . . . . . . . . . . .
`1.1.3
`Il campo range . . . . . . . . . . . . . . . . . . . . . . . . . . .
`1.1.4 Connessioni persistenti . . . . . . . . . . . . . . . . . . . . . . .
`1.2 Servizi Web Replicati . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`1.2.1 Gestione server-side . . . . . . . . . . . . . . . . . . . . . . . .
`1.2.2 Gestione client-side . . . . . . . . . . . . . . . . . . . . . . . . .
`
`2 Distribuzione di carico client-centered: C2LD
`2.1 La versione precedente di C2LD . . . . . . . . . . . . . . . . . . . . . .
`2.1.1 Motivazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.1.2 Modus operandi
`. . . . . . . . . . . . . . . . . . . . . . . . . .
`2.1.3 Dimensione del frammento . . . . . . . . . . . . . . . . . . . . .
`2.1.4 Repliche in difficoltà . . . . . . . . . . . . . . . . . . . . . . . .
`2.1.5 L’architettura software e la sua implementazione . . . . . . . . .
`2.1.5.1
`Soluzioni algoritmiche: prima GET . . . . . . . . . . .
`2.1.5.2
`Il linguaggio C++ . . . . . . . . . . . . . . . . . . . .
`2.1.5.3
`Classi progettate ed implementate . . . . . . . . . . . .
`2.2 La nuova versione del software C2LD . . . . . . . . . . . . . . . . . . .
`2.2.1 Lo storico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`2.2.2
`Politiche per l’inoltro della richiesta iniziale . . . . . . . . . . . .
`2.2.3
`Politiche per lo scaricamento di file di grandi dimensioni . . . . .
`
`3
`
`5
`6
`6
`9
`9
`10
`11
`11
`13
`
`17
`18
`18
`18
`19
`19
`26
`26
`28
`29
`33
`33
`37
`39
`
`i
`
`Microsoft Ex. 1038, p. 5
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`ii
`
`INDICE
`
`3 PlanetLab come TestBed realistico per verificare la scalabilità di C2LD
`3.1 PlanetLab: idee e princìpi alla base del progetto . . . . . . . . . . . . . .
`3.1.1 Virtualizzazione Distribuita
`. . . . . . . . . . . . . . . . . . . .
`3.1.2 Gestione disaccoppiata . . . . . . . . . . . . . . . . . . . . . . .
`3.1.3 Evoluzione efficiente . . . . . . . . . . . . . . . . . . . . . . . .
`3.2 PlanetLab come base per la “nuova internet” . . . . . . . . . . . . . . . .
`3.3 Breve storia di PlanetLab dalla nascita ad oggi . . . . . . . . . . . . . . .
`3.4 Scelte progettuali e caratteristiche tecniche principali
`. . . . . . . . . . .
`3.4.1 L’architettura dal punto di vista locale . . . . . . . . . . . . . . .
`3.4.2 L’architettura dal punto di vista globale . . . . . . . . . . . . . .
`3.4.3 Le macchine virtuali
`. . . . . . . . . . . . . . . . . . . . . . . .
`3.4.3.1
`I Vserver: virtualizzazione ed utente root . . . . . . . .
`3.4.3.2
`I Raw Socket protetti
`. . . . . . . . . . . . . . . . . .
`Servizi di amministrazione: installazione ed aggiornamento del
`sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.4.4.1
`Il CD di boot . . . . . . . . . . . . . . . . . . . . . . .
`3.4.4.2
`Il boot server e l’aggiornamento del software . . . . . .
`PlanetLab versione 3.0: principali novità
`. . . . . . . . . . . . .
`3.4.5.1 Node Manager
`. . . . . . . . . . . . . . . . . . . . .
`3.4.5.2
`Il kernel
`. . . . . . . . . . . . . . . . . . . . . . . . .
`3.5 Confronto con altre piattaforme concorrenti
`. . . . . . . . . . . . . . . .
`3.5.1
`PlanetLab e The Grid . . . . . . . . . . . . . . . . . . . . . . . .
`3.5.2
`PlanetLab e RON . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.6 Limiti di PlanetLab . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`3.7 Conclusioni
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3.4.4
`
`3.4.5
`
`43
`44
`46
`47
`49
`52
`56
`59
`60
`63
`65
`66
`68
`
`68
`69
`70
`70
`73
`73
`76
`76
`79
`81
`84
`
`87
`4 Test svolti e risultati ottenuti
`88
`4.1 Studio ed analisi dell’ambiente di test PlanetLab . . . . . . . . . . . . . .
`90
`4.2 Configurazione della piattaforma: scelta dei nodi client e server . . . . . .
`4.3 Selezione della versione ottimale del software C2LD . . . . . . . . . . . 104
`4.3.1 Risultati ottenuti: test su singolo file grande . . . . . . . . . . . . 109
`4.3.2 Risultati ottenuti: test su singolo file piccolo . . . . . . . . . . . . 112
`4.3.3 Risultati ottenuti: test su homepage completa . . . . . . . . . . . 113
`4.3.4 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
`
`Microsoft Ex. 1038, p. 6
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Indice
`
`iii
`
`4.4 Test di scalabilità del software C2LD . . . . . . . . . . . . . . . . . . . . 115
`4.5 Test comparativo tra C2LD e BitTorrent
`. . . . . . . . . . . . . . . . . . 122
`4.5.1
`Introduzione a BitTorrent . . . . . . . . . . . . . . . . . . . . . . 122
`4.5.2
`Protocollo e funzionamento di BitTorrent
`. . . . . . . . . . . . . 123
`4.5.3 Test svolti e risultati ottenuti
`. . . . . . . . . . . . . . . . . . . . 131
`4.5.4 Ulteriori considerazioni
`. . . . . . . . . . . . . . . . . . . . . . 138
`
`139
`5 Futuri sviluppi: miglioramenti ed ampliamenti
`5.1 Politiche di aggiornamento dello storico . . . . . . . . . . . . . . . . . . 140
`5.2 Struttura dello storico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
`5.3 Politiche di funzionamento di C2LD . . . . . . . . . . . . . . . . . . . . 143
`
`Conclusioni
`
`Ringraziamenti
`
`Bibliografia
`
`147
`
`149
`
`151
`
`Microsoft Ex. 1038, p. 7
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`3.4. Scelteprogettualiecaratteristichetecnicheprincipali
`
`65
`
`un insieme di advertisement. Durante il passo 3, il broker combina gli advertisement con
`le richieste del servizio in termini di risorse, producendo una specifica di slice. Il broker
`richiede all’agente i ticket necessari per la slice, durante il passo 4, e l’agente risponde
`con i ticket. Infine, al passo 5, il servizio presenta i ticket al nodo per cui questi sono
`validi; il nodo istanzia una macchina virtuale associandole le risorse relative e ritorna al
`servizio un lease per questa VM.
`
`3.4.3 Le macchine virtuali
`
`In questa sezione verrà descritto il modo in cui PlanetLab implementa le macchine vir-
`tuali presenti su ogni nodo. L’obiettivo del consorzio centrale è quello di evolvere il
`Virtual Machine Monitor (VMM), supportando inizialmente una sola API ben nota (le
`chiamate di sistema Linux) e successivamente cambiarne l’implementazione sottostante
`con il tempo.
`
`A fine 2002, in occasione del previsto passaggio dalla versione 1.0 alla 2.0 di Pla-
`netLab, la nozione di isolation kernel è stata proposta da alcuni gruppi di ricerca in so-
`stituzione del precedente sistema di virtualizzazione del kernel. Successivamente è sta-
`ta valutata l’effettiva applicabilità di questo nuovo sistema con esiti purtroppo negativi:
`infatti nella versione 3.0 di PlanetLab è ancora presente un approccio basato su virtua-
`lized kernel.
`I sistemi basati su isolation kernel come ad esempio Denali [WSG02] e
`Xenoservers [FHH+03] [WHHP02] forniscono un’interfaccia di isolamento a basso li-
`vello che assomiglia molto ad una virtualizzazione dell’hardware reale. In questo tipo
`di approccio la protezione e l’allocazione delle risorse viene eseguita al livello in cui si
`trova l’interfaccia di isolamento, mentre gli utenti nello scrivere le loro applicazioni fanno
`riferimento alle API del sistema operativo che viene eseguito all’interno della macchina
`virtuale. La differenza fondamentale con i sistemi di virtualizzazione del kernel risiede nel
`fatto che questi ultimi (generalmente si tratta di sistemi operativi Unix-like, come Linux)
`non distinguono tra l’interfaccia nella quale si mette in atto il meccanismo di protezione
`e l’interfaccia di chiamate di sistema usata dagli sviluppatori di applicazioni. La scelta
`è quindi ricaduta su un approccio di tipo virtualized kernel, in virtù della sua maggior
`flessibilità e delle migliori prestazioni da esso offerte.
`
`Microsoft Ex. 1038, p. 8
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Bibliografia
`
`155
`
`[SGP04] Karl-André Skevik, Vera Goebel, e Thomas Plagemann. Analysis of
`bittorrent and its use for the design of a p2p based streaming protocol for
`a hybrid cdn. Department of Informatics - University of Oslo Technical
`Report, June 2004.
`
`[SHJ+03] Nabah S., Franke H., Choi J., Seetharaman C., Kaplan S., Singhi N.,
`Kashyap V., e Kravetz M. class-based prioritized resource control in linux.
`In Proceedings of Linux Symposium OLS 2003 (Ottawa, Ontario, Canada),
`July 2003.
`
`[SJPS+05] Lee Sung-Ju, Sharma Puneet, Banerjee Sujata, Basu Sujoy, e Fonseca
`Rodrigo. Measuring bandwidth between planetlab nodes. HP Labs Technical
`Report HPL-2005-24. To be published in Passive and Active Measurement
`Workshop (PAM 2005) 31 March -1 April 2005, Boston, MA, USA, March
`2005.
`
`[Sta03] William Stallings. Cryptography and Network Security (Third Edition).
`Prentice Hall, 2003.
`
`[UoA05] CS Department University of Arizona. http://www.cs.arizona.edu/scout/.
`Homepage del progetto Scout, 2005.
`
`[WHHP02] Andrew Warfield, Steve Hand, Timothy L. Harris, e Ian Pratt. Isolation oh
`shared network resources in xenoservers. PlanetLab Design Note PDN-02-
`006, November 2002.
`
`[WPRK03] Mike Wawrzoniak, Larry Peterson, Timothy Roscoe, e Scott Karlin. A
`simple common sensor interface for planetlab. PlanetLab Technical Report
`PDN-03-010, May 2003.
`
`[WSG02] Andrew Whitaker, Marianne Shaw, e Steven D. Gribble. Denali: A
`scalable isolation kernel. Proceedings of the Tenth ACM SIGOPS European
`Workshop, Saint-Emilion, France, September 2002.
`
`Microsoft Ex. 1038, p. 9
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`