• Non ci sono risultati.

Allocazione ottima di contenuti in reti ICN veicolari

N/A
N/A
Protected

Academic year: 2021

Condividi "Allocazione ottima di contenuti in reti ICN veicolari"

Copied!
107
0
0

Testo completo

(1)

Dipartimento di Elettronica, Informazione e Bioingegneria

Laurea magistrale in Ingegneria delle Telecomunicazioni

Allocazione ottima di contenuti

in reti ICN veicolari

Relatore: Prof. Giacomo VERTICALE

Tesi di laurea di:

Federico BRUNO

Matricola: 782891

(2)

Sommario

Internet è diventata in meno di 50 anni parte integrante della vita quo-tidiana di buona parte della popolazione mondiale ma negli anni il suo utilizzo è cambiato profondamente. Oggi l’impiego predominante è come piattaforma per il recupero di contenuti dalla rete, con un peso notevo-le dei video. Un altro utilizzo sempre più importante è l’accesso alla rete in mobilità. Negli ultimi anni i ricercatori hanno iniziato a pensare come evolvere l’architettura di rete basata sul concetto di dove si trova l’oggetto desiderato ad un paradigma basato sul cosa l’utente vuole ottenere.

Questo filone di ricerca prende il nome di Information Centric Networ-king (ICN). Un interessante progetto è il Named Data NetworNetwor-king (NDN). L’architettura NDN si basa su due entità: consumer e producer che rispetti-vamente richiedono contenuti, via Interest Packet, e rispondono alle richie-ste, mediante Data Packet. I contenuti sono divisi in frammenti indipen-denti (chunk). La comunicazione è gestita da 3 strutture presenti in ogni nodo: Forward Information Base (FIB), Pending Interest Table (PIT) e Con-tent Store (CS). Queste strutture permettono di inoltrare le richieste verso la corretta interfaccia di uscita e di far percorre ai dati in risposta il per-corso a ritroso. Il CS mantiene in memoria gli ultimi chunk elaborati, se il

(3)

frammento richiesto è nel CS il nodo intermedio risponde senza inoltrare l’interesse.

Nel lavoro si propongono due modelli di ottimizzazione matematica per studiare l’allocazione ottima dei contenuti in una topologia di rete ad albero binario, in scenario di mobilità degli utenti. Il primo modello mostra la probabilità di successo del sistema in funzione dei parametri di rete mentre il secondo fornisce la quantità totale di memoria da impiega-re nel sistema per otteneimpiega-re una probabilità di successo desiderata. I mo-delli sono stati confrontati con il funzionamento base di NDN attraverso simulazioni.

Il confronto con il simulatore mostra un miglioramento delle presta-zioni del 30% quando il sistema serve 400 utenti e quasi del 100% attorno ai 700 utenti. Il primo modello permette di osservare come l’allocazione di memoria nei CS possa incrementare le prestazioni ed essere una alter-nativa al costoso aggiornamento della capacità degli Access Point (AP). Si notano miglioramenti anche studiando l’incidenza della latenza dei col-legamenti nella rete. Quando gli utenti si spostano con differenti velocità nelle aree di copertura degli AP le prestazioni degradano tanto più il col-legamento è intermittente ma si notano miglioramenti allocando memoria nella rete. Con il secondo modello si stima l’incremento necessario nella memoria complessivamente impiegata quando gli utenti contattano meno AP nel percorso e la distribuzione della memoria nei diversi livelli.

(4)

Abstract

The Internet has became, in less than 50 years, an essential part of ev-eryday life for most of the world’s population but during these years its use has changed dramatically. Today, the predominant use is as a plat-form for retrieving content published on the network, with a consider-able weight of video content. Another increasing use is the access to the network on the move. During the last years, researchers have started to think about how to evolve the network architecture based on the concept of where the desired object is to a paradigm focused on what the user really wants to obtain from the network.

This branch of research is called Information Centric Networking (ICN). An interesting project in this area is the so called Named Data Network-ing (NDN). The NDN architecture is based on two entities: consumer and producer, the first one requests contents through Interest Packets while the second one responds to queries using Data Packets. The contents are di-vided into independent fragments, called chunk. The communication is handled through 3 structures implemented in each node: Forward Infor-mation Base (FIB), Pending Interest Table (PIT) and Content Store (CS). These structures allow to forward the requests to the correct output

(5)

terface and runs the data in response through the backward path. The CS keeps in memory the latest processed chunks; if the requested fragment is still in a CS at an intermediate node, that node responds without forward-ing the interest.

In this work we propose two discrete optimization models in order to evaluate the optimal allocation of content in a binary tree network topol-ogy, in an user’s mobility scenario. The first model evaluate the probability of successof the system as a function of network parameters while the sec-ond one provides the total amount of memory to be put in place to achieve the desired probability of success. The models were compared with the basic operation of NDN through a network simulator.

The comparison with the simulator shows a performance improve-ment up to 30% when the system serves 400 users and nearly 100% for 700 users. The first model allows us to observe how the memory allocation in the CS can increase performance and that it can be an alternative to an expensive upgrade of Access Point (AP) bandwidth. Improvements can be noted by also studying the effect of link delay in the network. When users move with different speeds in the coverage area of an AP, perfor-mance degrades as more as the connection is intermittent, but improve-ments are seen allocating memory within the network. With the second model is evaluated the increase in the overall memory required to be put in place in the network when users contact fewer AP in the path and it is also possibile to study the distribution of memory in the different levels.

(6)

Indice

1 Introduzione 1

1.1 Struttura della tesi . . . 6

2 Stato dell’arte 8 2.1 Modelli di ottimizzazione matematica . . . 8

2.2 Caching e allocazione statica dei contenuti . . . 10

2.3 Mobilità e tecniche di preallocamento . . . 15

2.4 Reti veicolari . . . 17

3 Contesto 19 3.1 Information Centric Networking . . . 19

3.2 Named Data Networking . . . 21

3.2.1 Architettura di rete . . . 21

3.2.2 Descrizione del funzionamento della rete . . . 22

3.2.3 Vantaggi dell’architettura . . . 25

4 Modello allocazione ottima 28 4.1 Scenario . . . 28

4.2 Il modello . . . 29

(7)

4.2.1 Formulazione matematica . . . 31

4.2.2 Indici . . . 31

4.2.3 Dati necessari al calcolo dei parametri . . . 32

4.2.4 Parametri . . . 35

4.2.5 Variabili nel modello . . . 36

4.2.6 Funzione obiettivo . . . 37 4.2.7 Vincoli . . . 37 4.3 Modello duale . . . 39 4.3.1 Formulazione matematica . . . 39 4.3.2 Variabili ed indici . . . 40 4.3.3 Parametri . . . 40 4.3.4 Funzione obiettivo . . . 40 4.3.5 Vincoli . . . 40

4.4 Complessità computazionale dei modelli . . . 41

4.4.1 Primo modello . . . 41

4.4.2 Secondo modello . . . 42

4.5 Tempi di calcolo . . . 42

4.6 Occupazione di memoria . . . 43

5 Implementazione e risultati sperimentali 44 5.1 Simulatore di rete . . . 44

5.1.1 Implementazione in ndnSIM . . . 46

5.2 Presentazione dei risultati . . . 50

5.2.1 Confronto tra modello e simulatore . . . 51

5.2.2 Studio dell’incidenza della popolarità dei contenuti . 53 5.2.3 Studio dell’incidenza del ritardo di trasmissione nel-la rete . . . 56

(8)

5.2.5 Studio del tempo di contatto tra utenti e AP . . . 60 5.2.6 Studio della dimensione dei CS per garantire la

pro-babilità di successo desiderata . . . 62

6 Conclusioni 67 6.1 Sviluppi futuri . . . 70 A Codice AMPL 73 A.1 Modello 1 . . . 73 A.2 Modello 2 . . . 76 B Codice ndnSIM 78

B.1 Caricamento scenario simulazione . . . 78 B.2 Topologia di rete . . . 85

(9)

Elenco delle figure

3.1 Struttura dei pacchetti in Named Data Networking (NDN). Fonte [1] . . . 22 3.2 Schema di inoltro dei messaggi in NDN. Fonte [1] . . . 23 3.3 Schema del meccanismo di inoltro dei messaggi in NDN nel

caso in cui l’Interest venga intercettato nella rete o raggiun-ga il Producer del contenuto. Fonte [2] . . . 24 4.1 Topologia di rete considerata. . . 30 4.2 Andamento della distribuzione di probabilità di Zipf per

differenti valori dell’esponente della popolarità delle richie-ste dei contenuti del catalogo (αr). Il catalogo è composto da

50 contenuti. . . 33 4.3 Occupazione di memoria durante la soluzione del

model-lo matematico in funzione della dimensione del catamodel-logo considerato. . . 43 5.1 Distribuzione di probabilità delle richieste ottenuta nelle

si-mulazioni confrontata con la curva teorica per αr=1. . . 49

(10)

5.2 Tempi di simulazione, espressi in minuti, in funzione del numero di nodi mobili simulati. . . 50 5.3 Probabilità di successo, Psucc, nel recupero dei contenuti

va-lutata usando l’allocazione ottima proposta e ndnSIM con tecnica di caching LRU, al variare del numero di utenti attivi nel sistema. . . 52 5.4 Probabilità di successo, Psucc, nel recupero dei contenuti

va-lutata per differenti valori dell’esponente della popolarità dei contenuti, αr, e per differenti capacità del collegamento

tra utente ed AP, LC1. . . 55

5.5 Probabilità di successo, Psucc, nel recupero dei contenuti

valutata per differenti dimensioni del content store, CS, e differenti valori di latenza del collegamento, τ. . . 57 5.6 Probabilità di successo, Psucc, nel recupero dei contenuti

va-lutata per differenti dimensioni del content store, CS, nei diversi livelli della rete. . . 59 5.7 Probabilità di successo, Psucc, nel recupero dei contenuti

va-lutata variando il Contact Time Ratio, CTR, e le dimensioni dei CS nei differenti livelli della rete. . . 61 5.8 Dimensione totale dei CS necessaria a garantire la

Probabi-lità di successo, Psucc, desiderata calcolata al variare

dell’e-sponente di popolarità dei contenuti, αr, e dei percorsi, αp,

ed al variare del numero di AP incontrati nei percorsi, Ncont. 63

5.9 Intervalli di confidenza al 95% calcolati su 25 soluzioni in-tere diverse per ogni valore di Ncont del secondo modello

(11)

5.10 Quantità di memoria allocata in ogni livello della rete per raggiungere Psucc = 95% in funzione del numero di AP

incontrati, Ncont. . . 65

5.11 Caso Ncont=8: distribuzione della memoria nei livelli

(12)

Elenco delle tabelle

3.1 Panoramica dei principali progetti in ambito Information Centric Networking (ICN). Fonte [3] . . . 27 4.1 Valori assunti dai parametri dello scenario quando non

spe-cificato diversamente. . . 36 4.2 Tempo necessario a trovare un soluzione intera in

funzio-ne del numero di contenuti funzio-nel catalogo e del numero di percorsi considerati. I tempi sono espressi in secondi. . . 42 5.1 Riepilogo scenario per confronto tra modello matematico e

simulatore di rete ndnSIM. . . 53 5.2 Riepilogo scenario per lo studio dell’incidenza della

popo-larità dei contenuti. . . 55 5.3 Riepilogo scenario per studio incidenza del ritardo di

tra-smissione nella rete. . . 57 5.4 Riepilogo scenario per lo studio dell’impiego delle cache

nella rete. . . 59 5.5 Riepilogo scenario per lo studio della velocità degli utenti. . 61

(13)

5.6 Riepilogo scenario per lo studio della quantità di memoria necessario a garantire la Psuccdesiderata. . . 63

(14)

Elenco delle appendici

appendici/ampl_model1.mod . . . 73 appendici/ampl_model2.mod . . . 76 appendici/ndn–scenario–mobility.cc . . . 78 appendici/ndn–topology–mobility.txt . . . 85 xiv

(15)

Abbreviazioni

AP Access Point

CDN Content Delivery Network CS Content Store

CTR Contact Time Ratio FIB Forward Information Base

ICN Information Centric Networking ILP Integer Linear Programming IP Internet Protocol

LRU Least Recently Used NDN Named Data Networking PIT Pending Interest Table

(16)

Capitolo

1

Introduzione

N

el 1969 quattro università della costa ovest degli Stati Uniti furono collegate tra loro, per la prima volta, dalla nascente rete ARPANET. Quarantacinque anni dopo, più di 2 miliardi di utenti accedono a Internet, il traffico di dati prodotto supera i 60 Exabyte al mese e, con la futura "In-ternet delle cose", i dispositivi collegati ad In"In-ternet saranno nell’ordine di 1012.

Tra i trend futuri ha enorme importanza la continua crescita dell’utilizzo di Internet come piattaforma per distribuire contenuti, in larga parte di ti-po video (secondo il Visual Networking Index [4] di Cisco, nel 2013 i video pesavano per il 66% del traffico globale di Internet ed è previsto un incre-mento fino a quasi l’80% entro il 2018 ), ed il collegaincre-mento ad Internet in mobilità (Cisco prevede un aumento del traffico mobile di 10 volte tra il 2013 e il 2018).

Una tendenza più recente, ma da non sottovalutare, è quello della con-nected car(macchina connessa) per cui vari produttori di autovetture e di dispositivi mobili, negli ultimi anni, hanno presentato la propria interpre-tazione.

(17)

Il funzionamento della rete Internet è basato sul protocollo TCP/IP. I pac-chetti del protocollo IP (al livello 3 della pila ISO/OSI) sono strutturati per immagazzinare l’indirizzo logico e fisico della sorgente e della destinazio-ne del pacchetto stesso, il payload, cioè il dato vero e proprio da trasportare, ed altri metadati necessari alla comunicazione.

Il protocollo TCP (livello 4) si occupa del controllo di trasmissione, ren-de cioè affidabile la comunicazione tra sorgente e ren-destinazione gestendo le ritrasmissioni dei pacchetti e la ricezione ordinata dei pacchetti di una co-municazione.

Negli ultimi anni la comunità scientifica ha iniziato ad indagare la possibilità di una ristrutturazione del funzionamento di Internet per me-glio adattarsi all’attuale utilizzo predominante della rete: il recupero di contenuti dalla rete.

L’idea alla base del concetto dell’Information Centric Networking (ICN) è di porre l’attenzione sul contenuto che si vuole ottenere (cosa) invece che sul luogo dove il contenuto è disponibile (dove). Al contrario del protocollo IP dove per ottenere un contenuto è necessario conosce l’indirizzo logico, cioè la posizione del contenuto nella rete, con gli schemi ICN si richiede un contenuto attraverso il suo nome, univocamente riconoscibile nella rete.

Il grande vantaggio è quello di eliminare il concetto di connessione end-to-end tra due punti della rete (host e server). I contenuti, infatti, possono essere divisi in frammenti ed immagazzinati nei nodi intermedi della rete e le richieste possono essere intercettate e soddisfatte in qualsiasi punto della rete. Quest’ultima funzionalità descritta prende il nome di in-network caching.

(18)

Data Networking (NDN), a cui questo lavoro di tesi fa riferimento.

In NDN i contenuti sono univocamente indirizzati attraverso uno schema di denominazione gerarchica. Nel modello di comunicazione esistono due entità, consumer e producer, che rispettivamente esprimono le richieste dei contenuti (Interest Packet) e pubblicano originariamente sulla rete i conte-nuti (i conteconte-nuti sono divisi in frammenti chiamati chunk, i pacchetti di risposta alle richieste sono denominati Data Packet).

I nodi intermedi della rete sono provvisti di una memoria, Content Sto-re (CS), che permette di manteneSto-re una parte dei frammenti di contenuti elaborati.

L’inoltro degli interessi verso la giusta interfaccia di rete di uscita è gestito da una tabella, Forward Information Base (FIB), che associa un no-minativo ad una molteplicità di interfacce di uscita, permettendo implici-tamente la possibilità di sfruttare il multipath nella rete.

Quando le richieste vengono inoltrate verso il successivo nodo, viene sal-vata nella Pending Interest Table (PIT) l’interfaccia da dove era arrisal-vata la richiesta. Queste informazioni vengono utilizzate per instradare i Data Packetche infatti seguono a ritroso il percorso svolto dagli Interest Packet.

L’architettura NDN introduce anche vantaggi per quanto riguarda la sicurezza delle informazioni: ogni chunk è firmato crittograficamente, que-sto permette di poter fidarsi di chunk memorizzati nei nodi intermedi e che non arrivano direttamente dal producer originale del contenuto.

Il superamento del concetto di connessioni (intese come in ambito Inter-net Protocol (IP) tra host e server) ha indubbi vantaggi soprattutto in uno scenario di mobilità.

Attualmente quando un utente effettua l’handover deve ristabilire la con-nessione con il server con cui stava comunicando. In NDN l’utente si

(19)

col-lega ad un nuovo Access Point (AP) ed esprime nuovamente gli interessi che non erano ancora stati soddisfati.

Un vantaggio è che l’interesse potrebbe non necessitare di raggiungere nuovamente il producer del contenuto, ma, se il chunk è ancora disponibile in qualche CS intermedio, può essere soddisfatto più celermente.

In questo lavoro ci si è focalizzati sulla mobilità degli utenti prendendo come scenario di riferimento quello delle reti veicolari.

Nella tesi si considera una topologia di rete ad albero binario struttu-rata su 4 livelli. Il nodo padre è considerato il producer, o repository, dei contenuti, i nodi foglia sono gli AP a cui gli utenti si collegano e richiedo-no i contenuti.

Il catalogo dei contenuti è statico, le probabilità di richiesta di un contenu-to e di scelta di un percorso seguono la distribuzione Zipf.

L’obiettivo è, sfruttando le caratteristiche delle reti NDN, fornire uno schema di allocazione ottima dei contenuti nella rete che permetta all’u-tente di rimanere soddisfatto del sistema, cioè di recuperare il contenuto che desidera con la maggior probabilità possibile durante il suo tragitto. Dallo studio si vogliono anche trarre indicazioni sugli aspetti più impor-tanti per il dimensionamento della rete in una ottica di risparmio dei costi di messa in opera.

Per raggiungere gli obiettivi prefissati si è per prima cosa sviluppato un modello di ottimizzazione matematica che descriva il sistema conside-rato. Il modello proposto è di tipo ILP (Integer Linear Programming) ed è stato risolto numericamente attraverso il software AMPL con il risolutore CPLEX.

(20)

rete come il numero di utenti nel sistema, la banda degli AP, il ritardo di propagazione nella rete, la quantità di memoria posta nei CS sulle presta-zioni.

A partire dal primo modello se ne fornisce un secondo che permette lo studio della quantità totale di memoria da impiegare per raggiungere una probabilità di successo del sistema desiderata.

Il modello matematico è stato confrontato con delle simulazioni effet-tuate con un simulatore ad eventi discreti, ndnSIM, per valutarne la vali-dità e confrontare quanto proposto con il funzionamento attuale delle reti NDN.

Per aderire al modello matematico proposto, l’applicazione consumer che effettua le richiesta è stata modificata e lo spostamento degli utenti è stu-diato attraverso tracce di mobilità sintetiche date in ingresso al simulatore.

Il confronto con il simulatore mostra un miglioramento delle presta-zioni vicino al 30% quando il sistema serve 400 utenti e quasi del 100% attorno ai 700 utenti attivi.

Lo studio dei modelli matematici permette di osservare come l’alloca-zione di memoria nei CS possa incrementare le prestazioni ed essere una interessante alternativa al costoso aggiornamento della capacità degli AP. Nel caso più limitato in banda considerato, 9 Mbps, raddoppiando la ca-pacità del CS il miglioramento è quasi del 15%, praticamente pari all’incre-mento delle prestazioni raggiunto con un auall’incre-mento di un terzo della banda messa a disposizione in accesso.

I CS possono migliorare le prestazioni anche quando alcuni collegamenti nella rete soffrono di un alto ritardo di propagazione: la capacità dei CS può sopperire a questo effetto e garantire la stessa probabilità di successo

(21)

ottenuta quando i nodi sono collegati da link con bassa latenza ovviamen-te al costo del maggiore impiego di memoria.

Nella topologia di rete considerata si nota come impiegare memoria solo negli AP non sia la soluzione ideale ma, l’allocazione di memoria nei nodi interni può migliorare le prestazioni di un valore attorno al 10% in termini di probabilità di successo nel recupero dei contenuti.

Si è poi studiato come cambiano le prestazioni quando gli utenti non si spostano a velocità costante ma rimangano nell’area di copertura degli AP per tempi differenti: un contatto più intermittente degrada le prestazioni circa del 10% pur mantenendo lo stesso tempo totale di permanenza nel sistema.

Dal secondo modello matematico si valuta quanta più memoria si deb-ba disporre nella rete per raggiungere la prodeb-babilità di successo deside-rata: dimezzando gli AP incontrati nel percorso, ma mantenendo uguale il tempo totale nel sistema, la memoria necessaria complessivamente au-menta dell’80% o del 100% in base allo scenario valutato.

Questo modello permette anche di valutare la distribuzione di memoria nei diversi livelli della rete. Si nota un accentuato, ma atteso, sbilancia-mento verso l’implementazione di maggiore memoria nel primo livello della rete.

1.1 Struttura della tesi

Il seguito della tesi è strutturata come segue:

• Capitolo 2: fornisce una visione generale della situazione sulla ricer-ca acricer-cademiricer-ca nell’ambito di questo lavoro di tesi;

(22)

• Capitolo 3: introduce brevemente il concetto di Information Centric Networking (ICN) e della variante considerata in questa tesi: Named Data Networking (NDN);

• Capitolo 4: descrive lo scenario considerato in questo lavoro ed i mo-delli di ottimizzazione matematica introdotti valutandone inoltre la complessità computazionale;

• Capitolo 5: descrive lo scenario di simulazione utilizzato per vali-dare i modelli e fornisce una dettagliata presentazione dei risultati ottenuti;

• Capitolo 6: fornisce le conclusioni del lavoro svolto ed accenna pos-sibili sviluppi futuri.

(23)

Capitolo

2

Stato dell’arte

N

el corso degli ultimi anni, l’Information Centric Networking (ICN) è stato un argomento di studio molto trattato.

La ricerca spazia dall’architettura di rete, alla scalabilità del sistema di na-mingproposto, alla mobilità, alla sicurezza e privacy delle comunicazioni fino alla interoperabilità con gli attuali sistemi basati sul protocollo IP.

Nel seguito verrà fornita una panoramica dei principali contributi alla ricerca, in riferimento all’argomento trattato nella tesi, evidenziando dif-ferenze e peculiarità di quanto proposto.

Si rimanda al capitolo 3 per una introduzione al concetto di ICN ed una dettagliata spiegazione dell’architettura Named Data Networking (NDN).

2.1 Modelli di ottimizzazione matematica

La modellazione matematica è un indispensabile strumento per lo stu-dio teorico delle reti di telecomunicazioni.

(24)

In [5] viene presentato un modello di ottimizzazione matematica che, cercando la soluzione sub-ottima del problema di allocazione dei contenu-ti nella rete, ha come obietcontenu-tivo di minimizzare il consumo energecontenu-tico nella rete.

La topologia di rete considerata è a maglia e cerca di rappresentare le ca-ratteristiche delle reti commerciali di backbone.

La popolarità dei contenuti è descritta attraverso la distribuzione di Zipf con esponente tra 0.5 e 1.

Nella tesi si considera una topologia ad albero binario e l’obiettivo del modello è massimizzare la probabilità di recupero del contenuto deside-rato, trascurando gli aspetti di efficienza energetica.

Interessante ai fini di questo lavoro è il contributo [6], nel quale viene proposta una architettura denominata Content Distribution Community Infrastructure (CDCI) basata sul WiFi tradizionale.

L’idea è di installare in ogni access point della rete un file server che cerca di soddisfare le richieste senza collegarsi al server remoto.

In un’ottica di mobilità, e quindi di contatti intermittenti con gli Access Point, i vantaggi sono di evitare le riconnessioni con il server lontano nella rete e di diminuire il traffico in uscita dall’access point.

Uno schema simile può funzionare nel momento in cui gli utenti condi-vidono interessi simili (per esempio video popolari e, in ottica veicolare, informazioni sul traffico) ed è quindi probabili che le stesse richieste ven-gano espresse da più utenti.

Gli autori presentano un modello che indichi come memorizzare in manie-ra ottima i contenuti nei file server locali con l’obiettivo di massimizzare

(25)

la probabilità media di recuperare il file. Propongono inoltre un algoritmo euristico per la soluzione del modello.

Gli autori considerano un catalogo di 100 file con dimensione casuale, po-polarità secondo la distribuzione Zipf con esponente α ∈ {0; 0.8; 1.5} e 50 Access Point con diametro di copertura pari a 250 metri.

Il modello proposto è stato usato come punto di partenza del lavoro di te-si.

Il modello è stato adattato ai concetti e alle specificità della architettu-ra NDN, si è considearchitettu-rata una rete di distribuzione ad albero che possa anch’essa avvicinare i contenuti agli utenti in aggiunta alla memoria in-stallata negli Access Point e si è posto nel nodo padre dell’albero il nodo depositario di tutto il catalogo considerato.

2.2 Caching e allocazione statica dei contenuti

Un importante ambito di ricerca riguarda come sfruttare efficientemen-te i Conefficientemen-tent Store (CS) disponibili nelle reti NDN.

In [7] vengono presentate evidenze per cui allocare memoria in ma-niera eterogenea nella rete non migliorare le prestazioni rispetto ad una allocazione omogenea di risorse.

Per questo lavoro gli autori hanno simulato, attraverso il loro simulatore ccnSim, circa 1200 ore di dinamiche NDN considerando reti con fino a 60 nodi, un catalogo confrontabile con quello di Youtube (circa 108contenuti

per 1 PB di dati video, con dimensione del singolo file distribuita geome-tricamente con media 10 MB) e Content Store con capacità fino a 10GB. I contenuti sono distribuiti secondo la legge di Zipf con α ∈ {1.25; 1.5} e

(26)

viene fatto notare come questo sia un parametro molto influente e come possa alterare notevolmente i risultati per specifiche topologie di rete.

Al contrario in [8] e [9] viene affermato che si ottengono maggiori be-nefici nell’allocare più risorse nella parte periferica della rete, più vicino all’utente finale.

In [8] viene considerata una rete ad albero binario e fissano l’esponente di popolarità dei contenuti a 0.8. Nel lavoro vengono valutate varie tecniche di caching deterministiche e probabilistiche concludendo che soprattutto per i contenuti di tipo Video on Demand (VoD) dovrebbero essere memo-rizzati ai bordi della rete.

Anche in questo lavoro viene evidenziata l’importanza della scelta dell’e-sponente di popolarità dei contenuti per ottenere risultati significativi.

Per provare a rispondere a queste contraddizioni gli autori di [10] pro-pongono un nuovo modello di ottimizzazione per studiare il problema dell’allocazione della cache nella rete.

Viene poi presentato un estensivo studio, tramite simulazioni, dell’impat-to di vari parametri come dell’impat-topologia, dimensione della rete, popolarità dei contenuti e diverse tecniche di gestione della cache. Dalle conclusioni si apprende che:

• allocare cache omogeneamente nella rete è altamente inefficiente (que-sto lo si nota soprattutto in reti con più di 100 nodi);

• la topologia della rete gioca un ruolo importante nelle decisioni pro-gettuali: in reti di tipo inter-AS la cache andrebbe allocata il più pos-sibile nei nodi centrali della rete mentre, in reti tipo quelli degli

(27)

In-ternet Service Provider (ISP), si dovrebbe favorire l’allocazione di memoria nei nodi ai bordi della rete;

• la popolarità dei contenuti distribuiti nella rete è un fattore chiave nel dimensionamento ottimo del sistema. In caso di richieste dei con-tenuti uniformemente distribuite su tutto il catalogo è più efficiente privilegiare il posizionamento della cache nei nodi centrali della rete, al contrario, se le richieste sono molto polarizzate, andrebbe preferi-to un posizionamenpreferi-to della cache nei nodi periferici (in quest’ultimo caso si nota un alto livello di replicazione dei contenuti);

• l’allocazione di cache nella rete ha impatto anche sulla tecnica di gestione della cache stessa.

Questi ultimi lavori provano a tracciare le linee guida per il dimen-sionamento di reti NDN senza però addentrarsi nei vantaggi che queste possono apportare alla mobilità dell’utente.

Anche nel mondo web è possibile introdurre schemi di caching uti-lizzando i Proxy Server, questi servizi memorizzano un insieme di pagine web che possono essere visitate dagli utenti senza contattare il Web Server che le pubblica in rete.

In [11] viene studiato il posizionamento dei Proxy Server nella rete In-ternet tenendo come obiettivi la minimizzazione della latenza complessiva del caricamento di una pagina dal web.

Viene fornito un modello matematico che permette di trovare la soluzione ottima del posizionamento nel caso di topologia di rete ad albero binario dove il Web Server è il nodo padre dell’albero.

(28)

Il posizionamento consiste nell’installare un numero limitato e deciso a priori di Proxy scegliendo i nodi migliori tra tutti quelli disponibili nella rete considerata. Ad ogni nodo è associato un peso che rappresenta il traf-fico di rete ed un parametro che può descrivere latenza del collegamento, hop countod altre metriche.

In [12] vengono studiati diversi algoritmi di scelta e aggiornamento dei contenuti da mantenere nei Proxy Server. L’obiettivo è ridurre la laten-za percepita dagli utenti, servendo le richieste senlaten-za contattare, ad ogni richiesta della stessa pagina, il server web originario.

L’algoritmo di scelta degli oggetti da precaricare utilizza parametri come la popolarità ed il tempo di vita del contenuto (valutato come differenza di tempo tra due modifiche successive dell’oggetto).

La quantità di banda usata nella rete è considerata come parametro di co-sto dell’algoritmo e le prestazioni vengono valutate in termini di Hit Ratio del contenuto.

Il posizionamento ottimo dei Proxy Server nella rete e della scelta delle pagine è un problema confrontabile con quello dell’allocazione ottima dei contenuti nella rete NDN. In questo caso però è possibile sfruttare la dis-seminazione dei frammenti di contenuti, chunk, in tutti i nodi della rete.

Un’altra architettura di rete che può avere grossi vantaggi da una ef-ficiente tecnica di posizionamento ed allocazione dei contenuti sono le Content Delivery Network (CDN).

Le CDN sono un sistema distribuito per la consegna di contenuti nella re-te, in larga parte usati per lo streaming multimediale, audio e video.

(29)

L’obiettivo è instradare la richiesta verso il nodo tale per cui vengano mas-simizzate le prestazioni in termini di tempo di consegna, carico della rete o vicinanza rispetto all’utente.

In [13] viene proposto un modello per la valutazione del posiziona-mento ottimo, ma statico, dei contenuti (repliche) in una CDN, conside-rando uno scenario di mobilità degli utenti.

Nel modello è rappresentato lo spostamento degli utenti in funzione del tempo e dello spazio, cioè della loro posizione.

La funzione obiettivo del modello minimizza il traffico totale nel backbone della rete considerata. I risultati di questo primo modello sono utilizzati come lower bound del traffico generato per l’allocazione ottima dei conte-nuti nella rete; questo è conseguenza del fatto che il modello richiede la conoscenza a priori di tutte le future richieste da parte degli utenti carat-terizzati nel sistema.

Gli autori forniscono un secondo modello per il posizionamento dinamico dei contenuti attraverso un metodo statistico di previsione delle richieste. Questo algoritmo euristico viene eseguito sui vari server per ricalcolare dinamicamente il posizionamento delle repliche nella rete.

In NDN il posizionamento può essere realizzato a livello di frammenti di contenuto disposti ottimamente nella rete, in principio non è necessa-rio posizionare una intera replica dell’oggeto. Inoltre l’architettura NDN non necessita un sistema separato di reindirizzamento verso la posizione ottima a cui richiedere l’oggetto desiderato.

(30)

2.3 Mobilità e tecniche di preallocamento

Gli articoli [14] e [15] offrono una panoramica dello stato della ricerca nell’ambito della mobilità in ICN.

Entrambi i lavori evidenziano i benefici che, le differenti implementazioni del paradigma ICN (DONA, CCN, NetInf, NDN, PSIRP) forniscono nel campo della mobilità dell’utente.

In [14] vengono messi in luce i principali temi da approfondire nel fu-turo: gestione della mobilità del produttore di contenuti, meccanismi di routing dinamico resistenti alla ricollocazione non prevedibile del posi-zionamento dei contenuti.

Tra i punti di forza vengono elencati la facilità di implementare il multiho-mingdell’utente, il superamento della necessità di ristabilire la connessio-ne con il server dopo l’handover dell’utente ed una diminuzioconnessio-ne del falli-mento della rete dovuta alla replicazione dei contenuti.

L’articolo [15] si focalizza sulla architettura NDN e, dopo aver indicato i limiti del protocollo Internet Protocol (IP) nel supporto della mobilità, evidenzia alcuni interessanti aspetti positivi di un approccio data-oriented:

• sicurezza dei dati indipendente dalla posizione;

• miglioramento delle prestazioni dovuto al caching nella rete; • supporto alla mobilità dei consumatori e produttori di contenuti; • adattabilità a scenari differenti dovuta alla flessibilità della strategia

(31)

In [16] gli autori propongono un meccanismo proattivo di caching dei contenuti (PCNDN).

L’idea è di far trovare all’utente i contenuti richiesti, ma non ancora otte-nuti completamente, già pronti nel nodo al quale si collegherà dopo aver effettuato handover.

Allo scopo gli autori modificano l’Interest Packet del protocollo NDN e mo-strano attraverso simulazioni un miglioramento delle prestazioni rispetto alla architettura NDN standard in termini di delivery ratio ed una diminu-zione del tempo di latenza dell’handover.

Con lo stesso principio proattivo in [17] viene proposto un algoritmo (Selective Neighbor Caching) che, valutandone una funzione di costo in termini di ritardo medio e di utilizzo della cache disponibile, sceglie i nodi per i quali inizializzare la procedura di precaricamento.

Il lavoro è presentato in ambito PSI (Public-Subscribe Internetworking) e CCN (Content-Centric Networking).

In [18] vengono introdotti i Delegated Interest. Una modifica al funzio-namento di CCN grazie alla quale i nodi possono inviare un Interest Packet per conto di altri nodi.

Il meccanismo viene azionato dall’utente prima di effettuare l’handover per indicare al punto di accesso successivo di iniziare ad inoltrare richie-ste per conto proprio.

Il lavoro di tesi è basato sulla proposta NDN, non ne modifica i mecca-nismi standard ma cerca di sfruttarne le peculiarità come il caching nella rete.

(32)

2.4 Reti veicolari

In [19] viene proposto uno schema di prefetching predittivo dei con-tenuti nelle reti veicolari e nuove strategie di handoff per migliorare la latenza del download e diminuire il tempo di instaurazione della connes-sione al nuovo Access Point (AP).

Nella tesi ci si concentra sull’algoritmo di allocazione dei contenuti del-la rete perchè in ambito NDN non è necessario ristabilire del-la connessione end-to-end con il server, gli interessi non ancora soddisfatti vengono sem-plicemente riespressi appena il collegamento con il nuovo AP è attivo.

Essendo NDN una architettura di rete recente diversi lavori ne studia-no l’applicabilità al concetto di reti veicolari.

In [20] gli autori si chiedono se il paradigma NDN possa essere di aiuto allo sviluppo delle future reti veicolari.

Viene proposta una architettura di rete chiamata Content-Centric Ve-hicular Networking (CCVN) che modifica la proposta NDN base per ren-derla più adatta al contesto veicolare.

Gli autori supportano la loro proposta evidenziando delle prestazioni mi-gliori rispetto ad una classica architettura basata su TCP/IP.

Anche in [21] e [22] il protocollo NDN viene adattato al contesto delle reti veicolare Vechicle to Vechicle (V2V) mettendo in luce i vantaggi di una tecnologia che pone l’attenzione sul contenuto da ottenere invece che sul luogo dove il contenuto è disponibile.

(33)

Il lavoro di tesi si concentra su una architettura di rete Vehicle to Infra-structure (V2I) invece che V2V.

(34)

Capitolo

3

Contesto

Q

uesto capitolo offre una breve introduzione al concetto di Informa-tion Centric Networking (ICN), le idee alla base di esso e i progetti di ricerca che, attualmente, lo stanno sviluppando.

Nel paragrafo successivo viene introdotto estesamente lo schema Na-med Data Networking (NDN).

In ambito NDN, nel capitolo 4, vengono introdotti i modelli matema-tici sviluppati durante questo lavoro di tesi e, nel capitolo 5, vengono ampiamente discussi i risultati ottenuti.

3.1 Information Centric Networking

Negli anni ’60 e ’70, quando le idee e i concetti alla base di Internet vennero sviluppati, l’unico esempio di successo di rete globale era la rete telefonica.

Il protocollo TCP/IP fu pensato e progettato per risolvere lo stesso proble-ma alla base delle comunicazioni tramite rete telefonica: una conversazio-ne punto-punto tra due entità collegate alla rete.

(35)

Nel corso degli anni però la diffusione di Internet è aumentata smisu-ratamente, così come sono cambiate le necessità e le abitudini degli utenti connessi.

Attualmente il maggiore utilizzo di Internet è quello della distribuzione di contenuti, principalmente video (secondo Cisco [4], nel 2013, il 66% del traffico globale di Internet è stato generato da video).

L’utente, quando accede alla rete, non è interessato a dove si trova il contenuto ma a cosa vuole ottenere dalla rete stessa.

Il datagramma Internet Protocol (IP) è strutturato proprio per identifi-care i due end-point del flusso di comunicazione, senza porre l’attenzione sul contenuto trasportato.

L’idea alla base dell’ICN è focalizzare l’interesse sul contenuto da rice-vere attraverso la rete (cosa) superando il concetto di server da raggiungere (dove).

Parte di questi concetti sono già stati implementati nelle Content Delive-ry Network (CDN), fondamentali per l’attuale funzionamento della rete Internet.

Le CDN sono sviluppate come reti overlay di Internet mentre lo studio delle reti ICN porta profondi cambiamenti nell’architettura e nel funzio-namento base della rete.

La prima idea di rete contenuto-centrica si trova, già nel 2000, nel pro-getto TRIAD (Translating Relaying Internet Architecture integrating Acti-ve Directories, [23]).

Nel corso degli anni si sono sviluppati diversi progetti di ricerca: DONA ([24]), 4WARD ([25]), PSIRP/PURSUIT ([26]), SAIL ([27]), CONET ([28]), NetInf ([29]) e CCN/NDN ([1]).

(36)

Nella tabella 3.1 si vuole offrire una panoramica generale dei progetti in ambito ICN.

3.2 Named Data Networking

Il paradigma NDN è stato presentato nel 2009 da Van Jacobson et al in [1] dove gli autori presentano il progetto, i concetti principali dell’architet-tura di rete proposta e le future direzioni di ricerca.

3.2.1 Architettura di rete

In NDN sono definiti due tipi di nodi:

• Consumer: nodo che richiede un contenuto;

• Producer: nodo che pubblica in rete il contenuto o che possiede l’og-getto richiesto in cache;

e due tipi di pacchetti (schematizzati in figura 3.1):

• Interest Packet: inviato dal Consumer, esprime la richiesta del conte-nuto attraverso il nome dell’oggetto desiderato;

• Data Packet: inviato da un nodo in risposta ad un Interest Packet, è il contenuto richiesto;

Il funzionamento della rete è gestito attraverso altre 3 strutture dati: • Forward Information Base (FIB): è usata per inoltrare l’Interest

Pac-ketverso un nodo che possegga il contenuto richiesto.

La tabella è popolata tramite un protocollo di routing basato sui nomi dei contenuti.

(37)

Figura 3.1: Struttura dei pacchetti in NDN. Fonte [1]

• Pending Interest Table (PIT): memorizza l’interfaccia (possono es-sere anche più di una) dalla quale è arrivato un Interest Packet.

Quando il nodo riceve un Data Packet interroga la FIB e inoltra il pacchetto verso l’interfaccia che lo aveva richiesto;

• Content Store (CS): è la cache del nodo NDN.

Viene interrogata all’arrivo di un Interest Packet, se il contenuto è presente viene inviato in risposta senza inoltrare al nodo successivo l’interesse.

In figura 3.2 è mostrato lo schema di funzionamento dell’inoltro dei messaggi in NDN.

3.2.2 Descrizione del funzionamento della rete

Per ricevere un contenuto, il Consumer invia un Interest Packet che con-tiene il nome che identifica l’oggetto desiderato nel campo Content Name. Il nome è strutturato gerarchicamente, per esempio:

(38)

Figura 3.2: Schema di inoltro dei messaggi in NDN. Fonte [1]

indica il terzo segmento della prima versione del video richiesto.

La struttura gerarchica dei nomi consente una necessaria aggregazione delle informazioni di routing.

Il nodo NDN che riceve l’Interest Packet memorizza l’interfaccia dalla quale il pacchetto è arrivato e, interrogando la FIB, inoltra il pacchetto ver-so l’interfaccia d’uscita corretta.

Quando l’Interest Packet arriva ad un nodo NDN che possiede il contenuto richiesto, un Data Packet viene inviato verso il richiedente.

Come descritto in precedenza, Interest e Data Packet non contengono in-formazioni sul richiedente del contenuto, quindi il Data Packet percorre a ritroso il percorso dell’Interest grazie alle informazioni salvate nelle PIT nei nodi intermedi.

È interessante evidenziare che se ad un nodo arrivano più Interest Pac-ketper lo stesso contenuto, soltanto il primo ricevuto verrà inoltrato

(39)

men-tre, nella PIT, verranno registrate tutte le interfacce richiedenti.

Dopo aver consultato la PIT vengono rimosse le voci riguardo l’interesse appena soddisfatto.

Contestualmente il Data Packet viene memorizzato nel CS del nodo che potrà quindi soddisfare immediatamente gli interessi per quel contenuto senza inoltrare nuovamente l’interesse.

In figura 3.3 è mostrato il meccanismo di inoltro dei messaggi nel caso in cui il contenuto venga recuperato dal producer o nel caso in cui sia già disponibile in un nodo intermedio.

Figura 3.3: Schema del meccanismo di inoltro dei messaggi in NDN nel caso in cui l’Interest venga intercettato nella rete o raggiunga il Producer del contenuto. Fonte [2]

(40)

3.2.3 Vantaggi dell’architettura

• Sicurezza

In NDN ogni Data Packet è firmato crittograficamente. Questa firma, combinazione del dato trasportato e delle informazioni del creatore del contenuto, permette all’utente di fidarsi del contenuto ricevuto indipendentemente da dove (nodo intermedio nella rete) sia stato ottenuto.

La firma crittografica è requisito obbligatorio del sistema: le applica-zioni non possono ometterla.

• In-network caching

Anche i router IP sono dotati di buffer di memoria ma il grande vantaggio dell’architettura NDN è quello di poter rispondere diret-tamente con i dati già memorizzati nel CS mentre, nel router IP, la cache è usato solo per l’elaborazione dei pacchetti in coda.

Le cache possono essere gestite attraverso varie tecniche: Sostituzio-ne Casuale, Least Recently Used (LRU), Least Frequently Used (LFU) o tecniche più complesse che potranno essere introdotte.

• Livello di trasporto trasparente

NDN non introduce un nuovo livello di trasporto, ma ne sposta le funzionalità direttamente nelle applicazioni NDN e nella gestione dell’inoltro dei messaggi.

La rete NDN è progettata per funzionare correttamente come livello superiore di qualunque tipo di rete sottostante (incluso IP).

I nodi NDN possono gestire il carico di traffico attraverso il dimen-sionamento della PIT (numero di richieste pendenti) verso una sin-gola interfaccia (hop-by-hop): il controllo di congestione è quindi

(41)

otte-nuto evitandone la dipendenza dai nodi finali.

Nel momento in cui un collegamento tra nodi NDN è congestionato, la cache può intervenire per limitarne l’impatto in quanto, non appe-na collegamento sarà di nuovo operativo, gli interessi che saranno ritrasmessi potranno essere soddisfatti direttamente dal CS.

• Strategia d’inoltro

La strategia di inoltro degli Interest Packet è parte fondamentale e molto flessibile del funzionamento delle reti NDN.

La sua versatilità consiste nel poter decidere dinamicamente come meglio sfruttare tutte le interfacce a disposizione nella FIB e superare il concetto di singolo miglior percorso (best path) del routing IP .

In NDN si può sfruttare facilmente il concetto di percorsi multipli, con la garanzia intrinseca nell’architettura di non creare percorsi ad anello all’interno della rete (loop).

(42)

DONA CCN PSIRP NetInf CONET Spazio dei nomi piatto gerar chico piatto piatto entrambi con str uttura con str uttura con str uttura Integrità dei nomi firma firma firma o firma o firma hash contenuto hash contenuto Nomi interpr etabili no sì no no sì Modello di astrazione no no no sì -delle informazioni Granularità dati oggetti pacchetti oggetti oggetti chunk Routing delle richieste basato sui nomi basato sui nomi NRS NRS ibrido NRS ibrido Routing dei dati per corso inverso per corso inverso sour ce routing per corso inverso per corso inverso con stato nel router con filtri Bloom Livello di trasporto IP diversi IP ,PSIRP diversi specifico (IP incluso) (IP incluso) (come TCP) Tabella 3.1: Panoramica dei principali pr ogetti in ambito ICN. Fonte [3]

(43)

Capitolo

4

Modello per l’allocazione ottima di

contenuti

I

n questo capitolo vengono presentati due modelli di ottimizzazione ma-tematica Integer Linear Programming (ILP) per studiare il problema dell’allocazione ottima dei contenuti, in contesto di mobilità, nelle reti Named Data Networking (NDN).

Il lavoro svolto prende spunto dal modello presentato in [6], estenden-do il concetto di Content Distribution Community (CDC), introestenden-dotto in uno scenario di rete veicolare basato su WiFi tradizionale, allo schema NDN dove gli Access Point (AP) sono collegati ad una rete di distribu-zione dei contenuti.

Nel capitolo 5 verranno discussi dettagliatamente i risultati ottenuti.

4.1 Scenario

Il modello proposto descrive una situazione dove un utente entra nel sistema scegliendo uno tra i molteplici percorsi possibili ed inizia a inviare

(44)

Interest Packet per il contenuto che vuole ottenere. Ogni contenuto è sud-diviso in un numero prefissato di chunk; a percorsi e contenuti è associata una popolarità di scelta che segue la distribuzione di Zipf [30].

I percorsi sono caratterizzati dalla sequenza di AP che l’utente incontra. Quando l’utente entra nell’area di copertura di un nuovo AP semplice-mente inoltra nuovasemplice-mente gli Interest Packet dei chunk che non sono anco-ra stati soddisfatti.

Per ogni contatto con l’AP ne viene calcolata la durata che dipende dal raggio di copertura dell’AP e dalla velocità di spostamento dell’utente. La banda messa a disposizione dall’AP viene uniformemente suddivisa tra tutti gli utenti collegati.

I nodi della rete sono dotati di Content Store (CS) dove vengono memo-rizzati chunk dei contenuti, se il chunk richiesto non è disponibile negli AP, e le risorse di banda lo permettono, è possibile recuperare parte dei contenuti da altri nodi nella rete.

Come mostrato in figura 4.1 si è considerata una topologia di rete ad albero binario, strutturata su 4 livelli.

Non essendo considerata la variabile tempo nel modello, i valori in esame sono da considerarsi sempre come valori medi.

4.2 Il modello

Un modello di ottimizzazione matematica è essenzialmente scompo-nibile in 3 componenti base: funzione obiettivo, vincoli ed equazioni per definire l’insieme di esistenza delle variabili.

La funzione obiettivo del modello proposto massimizza la probabilità che un utente richieda un contenuto e, durante la sua permanenza all’interno

(45)

Figura 4.1: Topologia di rete considerata.

del sistema, riesca a recuperarlo completamente.

I vincoli tengono conto della banda disponibile nella rete (tra AP e utenti finali e tra i nodi dell’albero di distribuzione), della capacità dei CS nella rete, della distribuzione dei contenuti nei CS e delle maggiori risorse ne-cessarie a recuperare un contenuto più questo è lontano dall’utente. Il modello è un problema di ottimizzazione discreta, le variabili utilizzate sono intere positive oppure binarie.

Per risolvere il modello è stato usato il software di ottimizzazione AMPL [31] con il risolutore CPLEX [32].

Nei paragrafi successivi il modello viene presentato nella sua formula-zione matematica e dettagliatamente spiegato.

(46)

4.2.1 Formulazione matematica

max: X j Reqj X v PvAjv (4.1) X i,l

Recivjl· mi,v = Ajv· Sj ∀j, ∀v (4.2)

X

l

(γivl· Recivjl) 6 MDBiv1 ∀i, ∀v, ∀j (4.3)

Recivjl 6 Xijl ∀i, ∀v, ∀j, ∀l (4.4)

X j Xij1 6 CS ∀i (4.5) X i∈I,j Xij2 6 CS I = {1, 2}, {3, 4}, {5, 6}, {7, 8} (4.6) X i∈I,j Xij3 6 CS I = {1, 2, 3, 4}, {5, 6, 7, 8} (4.7)

Recivjl 6 MDBivl−

X

q∈Q

Recivjqs ∀i, ∀v, ∀j, l = 2, 3, 4,Q = {1, ..., l − 1}

(4.8) Xijl > 0, Recivjl > 0, Ajv∈{0, 1} (4.9)

4.2.2 Indici

• Access Point: i ∈ I = {1, . . . , I} • Contenuti: j ∈ J = {1, . . . , C} • Percorsi: v ∈ V = {1, . . . , V}

(47)

4.2.3 Dati necessari al calcolo dei parametri

Di seguito vengono brevemente introdotti i dati necessari al calcolo dei parametri successivamente usati per risolvere il modello matematico. (Tra parentesi sono indicati i valori dei parametri usati quando non espres-samente specificato diverespres-samente)

• Numero totale di utenti nel sistema: Utot (Utot=700);

• Diametro di copertura di ogni AP: d (d = 250 m); • Gli utenti si muovono alla velocità: s (s = 90 km/h);

• Tempo di connessione dell’utente all’AP: Tcon = d/s(Tcon =10s);

• Dimensione di ogni chunk: Dchunk(1000 byte);

• Banda disponibile: LCl(LC1 = 9 Mbps, LC1,2,3= 1 Gbps);

• Latenza di trasmissione: τ (τ = 0.25 ms);

• La probabilità che il contenuto jesimo sia richiesto segue la legge di Zipf con esponente αred è:

Reqj = j−αr/

PC j=1j−αr

con αr= 1;

In figura 4.2 è mostrato l’andamento della distribuzione di probabi-lità per diversi valori di αr.

(48)

5 10 15 20 25 30 35 40 45 50 0 5 · 10−2 0.1 0.15 0.2 0.25 Contenuto richiesto Req j αr=0 αr=0.2 αr=0.4 αr=0.6 αr=0.8 αr=1

Figura 4.2: Andamento della distribuzione di probabilità di Zipf per differenti valori del-l’esponente della popolarità delle richieste dei contenuti del catalogo (αr). Il catalogo è

composto da 50 contenuti.

• La probabilità che il percorso vesimo sia scelto segue la distribuzione di Zipf con esponente αped è:

Pv = j−αp/

PV

j=1j−αp.

con αp= 1;

• Il numero di utenti in ogni percorso è calcolato come: Uv = Utot· Pv

• La variabile binaria miv (matrice dei contatti) è uguale a 1 se l’utente

nel percorso v si collega all’AP i, 0 altrimenti; • Il numero medio di utenti connessi all’AP iesimo è:

Ui=

PV

v=1Uvmiv/

PV v=1miv

(49)

• Il numero massimo di chunk che un nodo al livello l può consegnare all’iesimo AP per gli utenti nel vesimo percorso è definito come:

MDBilv(Maximum Downloadable Burst).

L’MDB dipende dalla banda disponibile che viene condivisa tra tutte le richieste in arrivo.

Si assume che la banda sia uniformemente divisa tra gli utenti colle-gati allo stesso AP i lungo il percorso v e garantita all’utente.

MDBilv= LCl· Tiv Dchunk  X j∈I(l,j) Uj −1 (4.10) dove Tiv= Tcon· mivè la durata della connessione tra AP i e l’utente

lungo il percorso v.

I(l, j) indica l’insieme di AP che condividono il collegamento di li-vello lesimo con il jesimo AP:

I(l, j) =                            {j} se l = 1 o l = 2 {j, j + 1} se l = 3 e j mod 2 = 1 I(l, j − 1) se l = 3 e j mod 2 = 0 {j, j + 1, j + 2, j + 3} se l = 4 e j mod 4 = 1 I(l, j + 1 − (j mod 4)) se l = 4 e j mod 4 6= 1

• Contact Time Ratio (CTR): indica il rapporto tra il tempo di transito più lungo e più corto all’interno del raggio di copertura di un AP. A parità di tempo di permanenza nel sistema si sono introdotte tem-pi di percorrenza diversi all’interno dell’area servita da un AP ipo-tizzando la possibilità per l’utente di muoversi più o meno veloce-mente. (CTR = 1)

(50)

• γivl > 1 rappresenta il rapporto tra il tempo necessario a recuperare

un chunk del contenuto iesimo da un CS al livello l (> 1) per un utente del percorso v ed il tempo per recuperare lo stesso chunk dal CS nell’AP (l = 1). È calcolato come: γivl = L X l=1 T chunkivl+2τ T chunkiv1+2τ.

dove Tchunkilv = Dchunk/MDBilv è il tempo di trasmissione per

un singolo chunk usando l’MDB disponibile dal nodo al livello l.

4.2.4 Parametri

• Reqj ∈ [0, 1]: probabilità di richiedere il jesimo contenuto;

• Pv ∈ [0, 1]: probabilità di scegliere il vesimo percorso;

• Sj ∈ Z: dimensione del jesimo contenuto (1000 chunk);

• MDBilv ∈ Z: MDB disponibile, per il singolo utente nel percorso

vesimo connesso all’AP iesimo, dal livello lesimo;

• γivl ∈ Z: rappresenta il costo maggiore nel recuperare chunk dai CS

più lontani nell’albero di distribuzione;

• CS ∈ Z: capacità del CS espressa in numero di chunk.

(51)

Parametro Descrizione Valore τ latenza del collegamento 0.25 ms LC1 capacità del link in accesso 9 Mbit/s

LCl capacità dei link (l > 1) 1 Gbit/s

L livelli dell’albero 4

I numero di AP 8

C dimensione del catalogo 50 contenuti αr esponente della popolarità dei contenuti 1

V numero di percorsi 5

αp esponente della popolarità dei percorsi 1

Utot numero totale di utenti 700

Sj lunghezza dei contenuti 1000 chunk

Dchunk dimensione dei chunk 1000 byte

CS dimensione del CS 2000 chunk

d diametro di copertura dell’AP 250 m

s velocità del veicolo 90 km/h

CT R contact time ratio 1

Tcon durata della connessione con AP 10 s

miv indicatore di connettività 0/1

Tabella 4.1: Valori assunti dai parametri dello scenario quando non specificato diversamente.

4.2.5 Variabili nel modello

• Xijl ∈ Z: numero (intero) di chunk del contenuto j memorizzato nel

(52)

• Ajv ∈{0, 1}: variabile binaria, è uguale a 1 se il contenuto j è

recupe-rabile durante il percorso v, 0 altrimenti;

• Recijlv∈ Z: numero (intero) di chunk del contenuto j recuperato dal

CS di livello l connesso all’AP i durante il percorso v.

4.2.6 Funzione obiettivo

La funzione obiettivo del modello (4.1) massimizza la probabilità di riuscire a recuperare interamente un contenuto, durante il percorso dell’u-tente nel sistema.

Essa dipende dalla probabilità di richiesta dei contenuti, Reqj, e dalla

pro-babilità che l’utente scelga un percorso tra quelli possibili, Pv.

Ajv è la variabile binaria che esprime se il contenuto è recuperato oppure

no.

4.2.7 Vincoli

• Recuperablità

Il vincolo (4.2) significa che un contenuto è valutato recuperabile se la somma dei chunk recuperati dal sistema è uguale al numero di chunk che compongono il contenuto stesso.

• Banda disponibile in accesso

L’equazione (4.3) impone che il numero massimo di chunk che pos-sono essere recuperati è limitato dalla banda disponibile agli utenti in accesso.

(53)

γivl accentua il fatto che più lontani sono i chunk nell’albero di

di-stribuzione, più alto è il costo (valutato in termini di banda usata) per recuperarli.

• Disponibilità nei CS

Con (4.4) il numero massimo di chunk recuperabili è limitato dal numero di chunk memorizzati nel CS.

• Capacità dei CS

Le equazioni (4.5), (4.6) e (4.7) esprimono il fatto che, la somma di chunk, di tutti i contenuti, salvati nei CS di livello l= 1, 2, 3 collegati all’APinon possono eccedere la capacità massima del CSl.

CS4 è considerato il repository dell’intero catalogo, quindi il vincolo non affligge questo CS.

• Capacità del collegamento

L’equazione (4.8) impone che il numero di chunk recuperati, in tutti i percorsi, dal CSlnon può superare il numero massimo di chunk che

il nodo può servire.

• Vincoli sui tipi di variabili

Infine, l’equazione (4.9) impone che le variabili di decisione siano positive e che Ajvsia una variabile binaria.

(54)

4.3 Modello duale

Il modello precedente può essere modificato per studiare il sistema da un altro punto di vista.

La funzione obiettivo è stata modificata per minimizzare l’occupazione dei CS nella rete garantendo che il sistema raggiunga una probabilità di suc-cesso desiderata.

Di seguito viene fornita la formulazione matematica e spiegate le modifi-che rispetto al modello precedente.

4.3.1 Formulazione matematica

min: X i,j,l Xijl (4.11) X j Reqj X v PvAjv > Psucc (4.12) X i,l

Recivjl· mi,v = Ajv· Sj ∀j, ∀v (4.13)

X

l

(γivl· Recivjl) 6 MDBiv1 ∀i, ∀v, ∀j (4.14)

Recivjl 6 Xijl ∀i, ∀v, ∀j, ∀l (4.15)

Recivjl 6 MDBivl−

X

q∈Q

recivjq ∀i, ∀v, ∀j, l = 2, 3, 4,Q = {1, ..., l − 1}

(4.16) Xijl > 0, Recivjl > 0, Ajv∈{0, 1}, Psucc ∈ [0, 1] (4.17)

(55)

4.3.2 Variabili ed indici

Variabili e indici rimangono invariati nella formulazione del secondo modello matematico.

4.3.3 Parametri

In questo secondo modello è stato aggiunto il parametro che rappre-senta la probabilità di successo desiderata:

• Psucc(Psucc =95%)

Gli altri parametri rimangono invariati rispetto alla formulazione prece-dente.

4.3.4 Funzione obiettivo

La funzione obiettivo (4.11) minimizza l’occupazione di memoria nei CS, per ogni contenuto, per ogni nodo e per ogni livello della rete.

4.3.5 Vincoli

Tra i vincoli è stato eliminato quello che riguarda la capacità nei CS ed è stata aggiunta l’equazione (4.12) che impone la probabilità di successo desiderata nel sistema.

Gli altri vincoli rimangono invariati rispetto alla formulazione precedente.

In appendice A.2 è fornito il codice AMPL del secondo modello mate-matico.

(56)

4.4 Complessità computazionale dei modelli

La complessità del modello matematico è espressa in termini di nume-ro di variabili e di vincoli attivi durante la ricerca della soluzione.

Negli scenari considerati, la cardinalità degli insiemi è la seguente: • Access Point: I = 8 • Catalogo: J = 50 • Percorsi: V = 5 • Livelli dell’albero: L = 4

4.4.1 Primo modello

• Numero di variabili ] var = I · V · J · L + V · J + I · J · (L − 1) = =8 · 5 · 50 · 4 + 5 · 50 + 8 · 50 · (4 − 1) = =9450 In generale: ] var =O(J · (I · V · L + V + L − 1)) • Numero di vincoli ] vinc = V · J + I · V · J + I · V · J · L + I + 4 + 2 + I · V · J · (L − 1) = =5 · 50 + 8 · 5 · 50 + 8 · 5 · 50 · 4 + 8 + 4 + 2 + 8 · 5 · 50 · (4 − 1) = =16264 In generale: ] vinc = O(2 · I · V · J · L)

(57)

4.4.2 Secondo modello

• Numero di variabili

Il numero di variabili è identico al primo modello matematico. • Numero di vincoli

] vinc = V · J + I · V · J + I · V · J · LI · V · J · (L − 1) = =5 · 50 + 8 · 5 · 50 + 8 · 5 · 50 · 4 + 8 · 5 · 50 · (4 − 1) = =16250

In termini generali la complessità è la medesima del primo modello.

4.5 Tempi di calcolo

Nella tabella 4.2 sono mostrati i tempi di calcolo per trovare una solu-zione intera attraverso AMPL.

Si nota come l’aumento del catalogo e, soprattutto, l’introduzione dei di-versi percorsi nella rete allunghino i tempi necessari per trovare una solu-zione ammissibile.

J = 50 J = 100 J = 500 J = 1000 V = 1 7.45 19.61 101.61 289.47 V = 5 208.77 890.24 (*) (*)

Tabella 4.2: Tempo necessario a trovare un soluzione intera in funzione del numero di contenuti nel catalogo e del numero di percorsi considerati. I tempi sono espressi in secondi.

(58)

4.6 Occupazione di memoria

Attraverso le statistiche di AMPL (comando option times) è possibile visualizzare l’occupazione della memoria durante la soluzione del primo modello proposto.

In figura 4.3 ne è dato esempio in funzione della dimensione del cata-logo considerato e per V = 1.

50 100 500 1000 0 250 500 750 1000 1250 Dimensione catalogo, J Occupazione memoria [MByte]

Figura 4.3: Occupazione di memoria durante la soluzione del modello matematico in funzione della dimensione del catalogo considerato.

(59)

Capitolo

5

Implementazione e risultati

sperimentali

Q

uesto capitolo è dedicato alla presentazione dei risultati ottenuti. Inizialmente si introduce il simulatore di rete utilizzato per vali-dare il modello matematico proposto, successivamente si offre uno studio dettagliato dei due modelli di ottimizzazione.

Nell’ultimo capitolo verranno discusse le conclusioni tratte dal lavoro svolto.

5.1 Simulatore di rete

Per procedere alla validazione del modello matematico è stato usato il simulatore di rete ndnSIM [33].

NdnSIM è un modulo del diffuso NS-3 [34], simulatore di rete ad eventi discreti scritto in C++. Le funzionalità della architettura Named Data Net-working (NDN) sono introdotte attraverso una serie di classi separate.

(60)

Di seguito vengono brevemente descritti le componenti base del simula-tore:

• ndn::L3Protocol: implementazione delle interazioni fondamentali del-l’architettura NDN, ricezione di Interest e Data Packet da livelli supe-riori e infesupe-riori attraverso delle strutture chiamate Face;

• Face: astrazione necessaria per fornire una comunicazione uniforme con le applicazioni (ndn::AppFace) oppure con altri nodi simulati (ndn::NetDeviceFace), supporta moduli per la gestione della conge-stione a livello di collegamento;

• ndn::ContentStore: astrazione delle cache per Data Packet nei nodi di rete;

• ndn::Pit: astrazione della Pending Interest Table (PIT), tiene traccia delle Face dove sono ricevuti gli Interest Packet, delle Face dove gli interessi sono inoltrati e dei nonce degli Interest Packet già elaborati; • ndn::ForwardingStrategy: astrazione e implementazione base

dell’i-noltro di Interest e Data Packet.

• ndn::Fib: astrazione della Forward Information Base (FIB), può esse-re usata dalla strategia di inoltro.

Ogni componente, ad eccezione della struttura base ndn::L3Protocol, of-fre numerose implementazioni differenti che possono essere scelte nello scenario di simulazione.

Nuove procedure possono inoltre essere aggiunte a partire da quelle già presenti.

(61)

5.1.1 Implementazione in ndnSIM

In appendice B.1 è fornito il codice per eseguire lo scenario di simula-zione.

Di seguito sono descritte le principali modifiche al funzionamento base di ndnSIM e le funzionalità introdotte.

Mobilità

NS-3 mette a disposizione vari modelli di mobilità (Constant Position, Constant Velocity, Constant Acceleration, Random Position, Random Walk, Random Waypoint) implementabili negli scenari di simulazione ma, in ag-giunta, eredita dalla versione precedente del simulatore, NS-2 [35], la pos-sibilità di caricare tracciati di mobilità sintetici.

Per attenersi il più possibile allo scenario descritto nel modello matemati-co si è scelto di sfruttare questa sematemati-conda funzionalità.

Il file che rappresenta la traccia di mobilità desiderata viene generato at-traverso uno script MATLAB.

Per ogni utente si indica la posizione e lo spostamento voluto, istante per istante secondo la seguente notazione:

$ns_ at <time> “$node_(<id>) setdest <x> <y> <speed>” Per esempio:

$ns_ at 25.50 "$node_(0) setdest 10.00 10.00 2.00" impone, per il nodo 0, uno spostamento all’istante di tempo 25.50 secondi verso le coordinate x = 10.00 e y = 10.00 con velocità 2 unità/s.

Lo spostamento indicato è sempre relativo alla posizione precedente del nodo selezionato.

(62)

Il file per caricare la topologia sulla quale i nodi sono fatti muovere nel simulatore è fornito in appendice B.2. Questo file è interpretato dal simu-latore attraverso la classe "AnnotatedTopologyReader" a disposizione.

Richieste degli utenti

In ndnSIM sono disponibili alcuni esempi di applicazioni installabili sui nodi che eseguono le richieste di contenuti però, al momento, non è gestito il concetto di chunk ma ogni oggetto richiesto è considerato indi-pendente.

Nel modello si ipotizza, coerentemente con l’architettura NDN, che i con-tenuti siano suddivisi in chunk e che l’utente voglia recuperare un conte-nuto, cioè ottenere tutti i frammenti di cui questo è composto.

Nel modello si ipotizza, inoltre, che le richieste avvengano attraverso una gestione tramite finestra, alla ricezione di un chunk viene richiesto il chunk successivo.

Per ottenere uno schema di consumer coerente con il modello matemati-co si è provveduto ad integrare tra loro ed adattare gli esempi presenti nel simulatore con il nome di consumer-zipf-mandelbrot"ed "ndn-consumer-window".

L’applicazione costruita utilizza la scelta casuale del contenuto da ri-chiedere, con la probabilità di richiesta del singolo contenuto pesata se-condo la distribuzione di Zipf.

Inizialmente viene estratto un numero casuale intero (1 6 rand 6 50) che indica la classe di popolarità del contenuto da richiedere, nel campo Content Namedell’Interest Packet viene inserito il valore seq:

seq = (rand −1) ∗ 1000

(63)

Quando un Data Packet è ricevuto il campo Content Name viene così elaborato:

chunk = seq +1 mod 1000 contenuto =bseq/1000 + 1c

Quando chunk = 0 vuol dire che è stato completamente recuperato il file desiderato, contenuto indica la classe di popolarità del file richiesto. Se il contenuto non è terminato, seq viene incrementato, inserito in un nuovo Interest Packet ed inviato.

Il consumer gestisce anche un Time Out che viene azionato quando il Data Packetnon è ricevuto entro un tempo impostato come soglia. In que-sto caso l’Interest Packet del chunk interessato viene ricostruito ed inviato nuovamente.

Quando il consumer riceve tutti i chunk di cui è costituito il contenuto non procede ad inviare richieste per nuovi contenuti.

Nel grafico 5.1 è mostrato il confronto tra la curva teorica della distri-buzione Zipf per αr = 1 e le probabilità di richiesta per ogni contenuto

misurate nel simulatore.

Si nota come, con un numero di richieste simulate sufficientemente ampio, la distribuzione ottenuta ben approssimi quella teorica.

(64)

5 10 15 20 25 30 35 40 45 50 0 5 · 10−2 0.1 0.15 0.2 0.25 Contenuto richiesto Req j Simulazione Curva teorica

Figura 5.1: Distribuzione di probabilità delle richieste ottenuta nelle simulazioni confrontata con la curva teorica per αr=1.

Interfaccia radio

Nei nodi simulati in ndnSIM viene installato il protocollo NDN che si occupa della comunicazione a livello di rete. La trasmissione dei chunk avviene attraverso l’installazione del modulo WiFi nei nodi.

In NS3 il WiFi messo a disposizione attraverso la classe "WifiHelper" che permette di impostare il raggio di copertura delle comunicazioni ed altri parametri riguardo la propagazione.

Nelle simulazioni si considera uno scenario semplificato per cui la poten-za ricevuta dal nodo è pari alla potenpoten-za trasmessa dall’Access Point (AP) fino a quando è nell’area coperta dal segnale e nulla non appena esce dalla copertura, non è considerata l’attenuazione del segnale dovuta alla distan-za.

(65)

A livello MAC è stato utilizzato il componente "ns3::AdhocWifiMac" mo-dificato per non consentire la comunicazione tra nodi mobili ma soltanto tra utenti e AP.

Tempi di simulazione

Nel grafico 5.2 sono forniti i tempi di simulazione misurati in funzione del numero di nodi introdotti nella rete.

10000 2000 3000 4000 5000 6000 7000 8000 9000 1000 2000 3000 4000 5000 6000 7000

Numero di nodi simulati

Tempo

di

simulazione

(minuti)

Figura 5.2: Tempi di simulazione, espressi in minuti, in funzione del numero di nodi mobili simulati.

5.2 Presentazione dei risultati

Di seguito viene presentato lo studio dei modelli matematici e degli esperimenti con il simulatore.

Figura

Figura 3.1: Struttura dei pacchetti in NDN. Fonte [1]
Figura 3.2: Schema di inoltro dei messaggi in NDN. Fonte [1]
Figura 3.3: Schema del meccanismo di inoltro dei messaggi in NDN nel caso in cui l’Interest venga intercettato nella rete o raggiunga il Producer del contenuto
Figura 4.1: Topologia di rete considerata.
+7

Riferimenti

Documenti correlati

L’allocazione dinamica della memoria si verifica quando un programma richiede al sistema operativo un blocco di memoria dichiarando, preventivamente, la dimensione dello stesso..

Di conseguenza, in un sistema sanitario in cui l’entità delle risorse è “limitata” e il principio di equità è considerato determinante per l’accesso alle prestazioni sanitarie,

[r]

Questo implica che il nodo che può essere estratto da una coda sia sempre il primo nodo inserito nella stessa (struttura dati di tipo F.I.F.O. ossia First In First Out). Le

I La funzione malloc della libreria stdlib.h alloca uno spazio di memoria contiguo nell’heap e restituisce un puntatore al primo byte allocato. I In case di fallimento restituisce

Utilizzando entrambi gli ingressi, il sistema ` e completamente raggiungibile per cui esiste sicuramente una matrice K tale da posizionare a piacere i poli del sistema

Nelle simulazioni, eettuate a computer utilizzando MATLAB, si consid- era l'uplink di una cella di una rete radiomobile con una stazione base che si trova al suo centro e avente

Indeed, taking the Chicago-based Polish daily Zgoda as an example, between 1907 and 1912 the proportion of editorials dealing wih the American issues was about