Prof. Ciro DApice Dott.ssa Rosanna Manzo 6 – 07 - 2007 ENEA Casaccia Università degli Studi di...
-
Upload
nunziatella-marinelli -
Category
Documents
-
view
215 -
download
0
Transcript of Prof. Ciro DApice Dott.ssa Rosanna Manzo 6 – 07 - 2007 ENEA Casaccia Università degli Studi di...
Prof. Ciro D’ApiceProf. Ciro D’Apice
Dott.ssa Rosanna ManzoDott.ssa Rosanna Manzo
6 – 07 - 20076 – 07 - 2007
ENEA CasacciaENEA Casaccia
Università degli Studi di SalernoUniversità degli Studi di SalernoDipartimento di Ingegneria dell’Informazione Matematica ApplicataDipartimento di Ingegneria dell’Informazione Matematica Applicata
Progetto CRESCO
Attività progetto CRESCO
1. Raffinamento del modello di telecomunicazioni;2. Analisi di problemi di convergenza e sviluppo di
schemi numerici;3. Analisi della politica di instradamento dei pacchetti;4. Ottimizzazione dei coefficienti caratteristici del
traffico; 5. Studio di ottimizzazione sulla rete in modo tale da
preservare la qualità di servizio nel caso in cui uno o più nodi e/o linee di comunicazione non funzionino;
6) Implementazione di algoritmi.
Attività progetto CRESCO
ID Task Name Start End2006 2007 2008
Nov Dec Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec Jan Feb Mar Apr May Jun Jul Aug Sep Oct
1 31/05/200701/11/2006Modellazione
2 31/03/200802/04/2007Sviluppo schemi numerici
3 30/05/200801/05/2007Ottimizzazione politiche instradamento
4 30/05/200801/05/2007Ottimizzazione coefficienti traffico
5 30/05/200801/05/2007Ottimizzazione qualità di servizio
6 30/10/200801/10/2007Implementazione algoritmi
Punto di partenza:Descrizione del modello
Ogni nodo riceve ed invia informazioni (pacchetti).
Ogni pacchetto può essere visto come una particella sulla rete.
Regola 2
I nodi ricevono, processano, e poi smistano i pacchetti. I pacchetti possono essere persi in accordo ad una probabilità che aumenta all’aumentare del numero di pacchetti che devono essere processati. Ogni pacchetto perso viene rispedito di nuovo.
Regola 1
Ogni pacchetto viaggia sulla rete con velocità fissata e con una assegnata destinazione finale.
Modello di una singola linea
Ogni nodo spedisce pacchetti al nodo seguente una prima volta, poi i pacchetti che
vengono persi vengono spediti una seconda volta, e così via.
Non si ha conservazione dei pacchetti in scale temporali piccole, ma in intervalli intermedi, a livello macroscopico, si assume che i pacchetti siano conservati
Il modello consiste della singola legge di conservazione
Perché possiamo modellare una singola linea con una legge di conservazione?
0t xf
Decomposizione verticale di Internet: il Decomposizione verticale di Internet: il protocollo TCP – IP a cinque strati protocollo TCP – IP a cinque strati
Phisycal Layer (e.g., optical fiber, copper)
Data Link Layer (e.g., Ethernet, frame relay)
Network Layer (e.g., Internet Protocol, or IP)
Transport Layer (e.g., Transmission Control Protocol, or TCP)
ApplicationLayer (e.g., HyperText Transfer Protocol, or HTTP; for the World Wide Web, or
WWW) )
Phisycal Layer (e.g., optical fiber, copper)
Data Link Layer (e.g., Ethernet, frame relay)
Network Layer (e.g., Internet Protocol, or IP)
Transport Layer (e.g., Transmission Control Protocol, or TCP)
Application Layer (e.g., HyperText Transfer Protocol, or HTTP; for the World Wide Web,
or WWW) )
Decomposizione di Internet
Probabilità di perdita, velocità e funzione flusso
E’ possibile ricavare la velocità media di trasmissione tra due nodi considerando il
numero di pacchetti che potrebbero andare persi durante la comunicazione.
Probabilità di perdita funzione
della densità
Funzione velocità
Funzione flusso
Tentativo Pacchetti spediti Pacchetti persi
1st (1-p) p
2nd (1-p)p p2
3rd (1-p)p2 p3
Sender Receiver
R
Probabilità di perdita
Funzione velocità e funzione flusso
Reti di telecomunicazioni
Un rete consiste di un insieme finito di linee con giunzioni che collegano le linee di trasmissione.
L’evoluzione della rete può essere descritta da un insieme finito di funzioni i definito su ]0,+∞[ x ]ai,bi[.
RA1: I pacchetti dalle linee entranti vengono spediti sulle uscenti in accordo
alla loro destinazione finale. RA2: I pacchetti vengono spediti verso le linee uscenti in maniera tale da massimizzare il flusso attraverso
la giunzione.
. .
Modelli di confronto
Modello proporzionale eccesso P/E
Sender Receiver
R
C
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Modelli di confronto Modello M/D/1/B: tutti i sender usano la stessa
dimensione dei pacchetti
Sender Reciever
B U F F E R
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Modelli di confronto Modello M/M/1/B : traffico dovuto alla sovrapposizione di molte
sorgenti TCP indipendenti, ciascuna configurata in modo tale da usare una dimensione di pacchetti
Sender Reciever
B U F F E R
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Modelli di confronto
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
congested
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Uno degli svantaggi dell’RA2 è che i pacchetti non venendo instradati verso i nodi congestionati potrebbero entrare in loop.
Questo problema può essere evitato se si assume che i pacchetti con una specifica origine ed una data destinazione viaggino attraverso un path specifico lungo la rete
Problema dei cicli
Soluzione
Introduzione della sorgente e della destinazione del flusso di pacchetti
Raffinamento del modelloSu ogni linea di trasmissione introduciamo il vettore che descrive la tipologia di traffico indicando la percentuale di pacchetti che vanno da una data sorgente s ad una determinata destinazione d. In questo caso i percorsi vengono determinati dal comportamento alle giunzioni in funzione di tali coefficenti
L’evoluzione di segue l’equazione semilineare
0 xt v
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Definizioni base
Una rete di telecomunicazione è individuata dalla seguente 6-upla (I, F, J, S, D, R)
• Archi I: insieme finito di intervalli chiamati linee di trasmissione
, , 1,..., ;i i iI a b R i N
• Flussi F: insieme finito di flussi max: 0,i if R
• Giunzioni J: sottoinsieme finito dell’insieme 1,..., N
• Sorgenti S: sottoinsieme finito dell’insieme rappresentante le linee connesse a sorgenti di traffico
1,..., N
• Destinazioni D: sottoinsieme finito dell’insieme rappresentante le linee connesse alle destinazioni del traffico
• Funzione di distribuzione del traffico R: collezione finita di funzioni rJ
indicanti alle giunzioni J, la direzione del traffico che parte dalla sorgente s ed arriva alla destinazione finale d
1,..., N
Funzione traffic - type
Una funzione traffic - type su una linea Ii è definita come:
: 0, , 0,1i i ia b S D
così che per ogni e 0,t ,i ix a b
,
, , , 1.is S d D
t x s d
In questo caso indica il valore della densità che partendo dalla sorgente s si muove verso la destinazione d
, , ,i t x s d ,i t x
Se rappresenta una traiettoria di pacchetti lungo Ii allora possiamo assumere , , , .i t x t s d const
x t
Considerando il differenziale totale rispetto al tempo otteniamo l’equazione semilineare
, , , , , , , 0.t i x i i it x s d t x s d v t x
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Modello su una singola linea
0, (*)
, , , , , , , 0. (**)
t x
t i x i i i
f
t x s d t x s d v t x
L’equazione (**) dipende dalla soluzione della (*), ad ogni giunzione il valore del coefficiente determina la distribuzione del traffico sulle linee uscentii
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Discutiamo alcune possibili scelte della funzione di distribuzione del traffico
1) : ( ). Jr Inc J S D Out J
Se è di tipo 1 ogni pacchetto ha un percorso determinatoJr
sorgente
destinazione
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Scelta della funzione di distribuzione del traffico
Scelta della funzione di distribuzione del traffico
2) : ( ). Jr Inc J S D Out J
Se è di tipo 2) il traffico è instradato su ogni linea oppure su alcune linee
Jr ( )jI Out J( )jI Out J
E’ possibile definire in due modi differenti , ,Jr i s d
: ( ),
, , ( ).
2a) J
j
r Inc J S D Out J
r i s d Out J
destinazione
sorgente
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
( )
, , , 1 , , ,
, , , , , ,
1
: ( ) 0,1 ,
, , ,..., ,
0 1, 1,..., , 1.
2b)
Out J
J
i s d n i s d n mj J J
n mi s d j i s d jJ J
j n
r Inc J S D
r i s d
with j n n m
sorgente
, , , 1i s d nJ
, , , 2i s d nJ
, , ,i s d n mJ
Scelta della funzione di distribuzione del traffico
Attività 1Attività 1Raffinamento del modelloRaffinamento del modello
Approssimazione numerica nel caso mono – dimensionale:
Si considera una griglia discreta di punti:
: passo spaziale
: passo temporale
xt
, ,
, ,
j
n
x j x j
t n t n
0
0,
,0 , 0,
0, , 0.
t x
b
f
x x x
t t t
Approssimazione della soluzione
Attività 2Attività 2Analisi di problemi di convergenza e sviluppo di schemi numericiAnalisi di problemi di convergenza e sviluppo di schemi numerici
Schema di Godunov:
schema del primo ordine, convergenza non molto veloce.
Schema di Lax – Friedrichs e di Lax – Wendroff : schemi del secondo ordine, convergenza veloce.
Schemi numerici
Attività 2Attività 2Analisi di problemi di convergenza e sviluppo di schemi numericiAnalisi di problemi di convergenza e sviluppo di schemi numerici
Attività 3Attività 3Ottimizzazione della politica di instradamentoOttimizzazione della politica di instradamento
Modelli locali
Ogni instradamento è possibile, e non tiene conto in generale della topologia complessiva della rete.
Modelli parametrici (con sorgenti e destinazioni)
Permettono di includere routers con comportamenti che dipendono sia dalle connessioni locali che dalla topologia globale della rete.
Topologia della rete
Attività 4Attività 4Ottimizzazione dei coefficienti caratteristici del trafficoOttimizzazione dei coefficienti caratteristici del traffico
Rete di telecomunicazioni con un nodo, con due linee entranti e due linee uscenti.
1 2
43
Ottimizzazione della velocità media e ottimizzazione del tempo medio di percorrenza.L’ottimizzazione è basata sul calcolo della soluzione del problema di Riemann alla giunzione.
1 1 2 3 4
31 2 42
1 2 3 4
ˆ ˆ ˆ ˆ , , ;
, , .ˆ ˆ ˆ ˆ
J v v v v g t x
ll l lJ h t x
v v v v
, ;
, .out
in out
in
se
p se
Coefficienti del traffico su rete
• considerando parametri ottimi;• considerando parametri fissi (i parametri della rete vengono scelti
dall’utente all’inizio della simulazione e rimangono costanti durante tutta la durata della simulazione);
• considerando parametri random statici (i parametri della rete vengono scelti in maniera random all’inizio della simulazione e rimangono costanti durante tutta la durata della simulazione).
Le simulazioni sulle rete vengono fatte….
Attività 4Attività 4Ottimizzazione dei coefficienti caratteristici del traffico Ottimizzazione dei coefficienti caratteristici del traffico
Simulazioni
x=0.1
T=30Lunghezza della linea = 100Densità iniziale=0
Nome Priorità Distribuzione
l1 0.3 /
l2 0.2 0.8
l3 / 0.4
l4 0.7 /
l5 0.8 /
l6 / 0.6
l7 / 0.2
0.35
0.35
0.3
p: 0.3
p: 0.7
d: 0.2
p: 0.2
d: 0.8
p: 0.8
d: 0.6
d: 0.4
x=0.12
T=30
Lunghezza della linea = 100
Densità iniziale=0
2.02.07
8.08.02
41
l
l
ll
7.06.06
3.04.03
52
l
l
ll0.35
0.35
0.3
l1: 0.8
l4: 0.8
l1: 0.2
l4: 0.2
l2: 0.6
l5: 0.7
l2: 0.4
l5: 0.3
Un’idea dal simulatore trafficoUn’idea dal simulatore traffico
Simulazione degli algoritmi RA1 e RA2
Attività 4Attività 4Ottimizzazione dei coefficienti caratteristici del trafficoOttimizzazione dei coefficienti caratteristici del traffico
Colore Densità
Nero 0 ≤ < 0.03
Grigio 0.03< ≤ 0.1
Giallo 0.1 < ≤ 0.2
Rosa 0.2< ≤ 0.3
Verde 0.3< ≤ 0.4
Azzurro 0.4 < ≤ 0.5
Blu 0.5< ≤ 0.6
Arancione 0.6 < ≤ 0.7
Viola 0.7< ≤ 0.8
Rosso > 0.8
RA1:
RA2: