Università degli Studi di Salerno
Dipartimento di Ingegneria dell’Informazione Matematica Applicata
Progetto CRESCO
ENEA Casaccia
6 – 07 - 2007
Prof. Ciro D’Apice
Dott.ssa Rosanna Manzo
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
2006
ID
Task Name
Start
2007
2008
End
Nov
1
Modellazione
01/11/2006
31/05/2007
2
Sviluppo schemi numerici
02/04/2007
31/03/2008
3
Ottimizzazione politiche instradamento
01/05/2007
30/05/2008
4
Ottimizzazione coefficienti traffico
01/05/2007
30/05/2008
5
Ottimizzazione qualità di servizio
01/05/2007
30/05/2008
6
Implementazione algoritmi
01/10/2007
30/10/2008
Dec
Jan
Feb
Mar
Apr
May
Jun
Jul
Aug
Sep
Oct
Nov
Dec
Jan
Feb
Mar
Apr
May
Jun
Jul
Aug
Sep
Oct
Punto di partenza:
Descrizione del modello
Ogni nodo riceve ed invia informazioni (pacchetti).
Ogni pacchetto può essere visto come una particella sulla rete.
Regola 1
Regola 2
Ogni pacchetto viaggia sulla rete
con velocità fissata e con una
assegnata destinazione finale.
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.
Modello di una singola linea
Perché possiamo modellare una singola linea con una legge di conservazione?
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
t  f    x  0
Decomposizione di Internet
Decomposizione verticale di Internet:
protocollo TCP – IP a cinque strati
ApplicationLayer
(e.g., HyperText
HyperText Transfer
Application
Layer (e.g.,
Transfer
Protocol, or
or HTTP;
or
Protocol,
HTTP; for
for the
theWorld
WorldWide
WideWeb,
Web,
orWWW)
WWW)) )
Transport
Layer
(e.g.,
Transmission
Transport
Layer
(e.g.,
Transmission
Control
Control
Protocol,
or TCP)
Protocol,
or TCP)
Network Layer (e.g., Internet Protocol, or IP)
Network Layer (e.g., Internet Protocol, or IP)
Data Link Layer (e.g., Ethernet, frame relay)
Data Link Layer (e.g., Ethernet, frame relay)
PhisycalLayer
Layer(e.g.,
(e.g., optical
optical fiber,
Phisycal
fiber, copper)
copper)
il
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
Probabilità di perdita
Sender
d
Receiver
R
Tentativo
Pacchetti spediti
Pacchetti persi
1st
(1-p)
p
2nd
(1-p)p
p2
3rd
(1-p)p2
p3
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.
Attività 1
Raffinamento del modello
Modelli di confronto

Modello proporzionale eccesso P/E
Sender
R
C
Receiver
Attività 1
Raffinamento 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à 1
Raffinamento 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à 1
Raffinamento del modello
Modelli di confronto
Attività 1
Raffinamento del modello
Problema dei cicli
Uno degli svantaggi dell’RA2 è che i pacchetti non venendo instradati
verso i nodi congestionati potrebbero entrare in loop.
congested
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
Attività 1
Raffinamento del modello
Soluzione
Introduzione della sorgente e della destinazione del flusso di pacchetti
Raffinamento del modello
Su 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
 t  v  x  0
Attività 1
Raffinamento 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
Ii   ai , bi   R, i  1,..., N ;
i

R
• Flussi F: insieme finito di flussi f i : 0, max
• Giunzioni J: sottoinsieme finito dell’insieme 1,...,  N 
• Sorgenti S: sottoinsieme finito dell’insieme 1,..., N  rappresentante le linee
connesse a sorgenti di traffico
• Destinazioni D:
sottoinsieme finito dell’insieme
linee connesse alle destinazioni del traffico
• Funzione
1,..., N 
rappresentante le
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
Attività 1
Raffinamento del modello
Funzione traffic - type
Una funzione traffic - type su una linea Ii è definita come:
 i : 0,    ai , bi   S  D
0,1
così che per ogni t  0,  e x   ai , bi 

sS , d D
 i  t , x, s, d   1.
In questo caso  i  t , x, s, d  indica il valore della densità i  t , x  che partendo
dalla sorgente s si muove verso la destinazione d
Se x  t  rappresenta una traiettoria di pacchetti lungo Ii allora possiamo assumere
 i  t , x  t  , s, d   const.
Considerando il differenziale totale rispetto al tempo otteniamo l’equazione
semilineare
 t i  t , x, s, d    x i  t , x, s, d   vi  i  t , x    0.
Attività 1
Raffinamento del modello
Modello su una singola linea

 t  f    x  0, (*)


 t i  t , x, s, d    x i  t , x, s, d   vi  i  t , x    0. (**)
L’equazione (**) dipende dalla soluzione della (*), ad ogni giunzione il valore del
coefficiente  i determina la distribuzione del traffico sulle linee uscenti
Attività 1
Raffinamento del modello
Scelta della funzione di distribuzione del traffico
Discutiamo alcune possibili scelte della funzione di distribuzione del traffico
1) rJ : Inc  J   S  D  Out ( J ).
Se rJ è di tipo 1 ogni pacchetto ha un percorso determinato
destinazione
sorgente
Attività 1
Raffinamento del modello
Scelta della funzione di distribuzione del traffico
2) rJ : Inc  J   S  D
Out ( J ).
Se rJ è di tipo 2) il traffico è instradato su ogni linea I j  Out ( J ) oppure su
alcune linee I j  Out ( J )
E’ possibile definire rJ  i, s, d  in due modi differenti
2a) rJ : Inc  J   S  D
rj  i, s, d   Out ( J ).
sorgente
Out ( J ),
destinazione
Attività 1
Raffinamento del modello
Scelta della funzione di distribuzione del traffico
2b) rJ : Inc( J )  S  D   0,1
Out ( J )

,

rj  i, s, d    Ji , s ,d ,n 1 ,...,  Ji , s ,d ,n  m ,
with 0  
i , s ,d , j
J
 1, j  n  1,..., n  m ,
nm

j  n 1
 Ji , s ,d , j  1.
 J i ,s ,d ,n 1
 J i ,s ,d ,n  2
sorgente
 J i , s ,d ,n  m
Attività 2
Analisi di problemi di convergenza e sviluppo di schemi numerici
Approssimazione della soluzione
Approssimazione numerica nel caso mono – dimensionale:
 t  f    x  0,

   x, 0   0  x  , x  0,

   0, t   b  t  , t  0.
Si considera una griglia discreta di punti:
x j  jx, j  ,
tn  nt , n  ,
x
t
: passo spaziale
: passo temporale
Attività 2
Analisi di problemi di convergenza e sviluppo di schemi numerici
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.
Attività 3
Ottimizzazione della politica di instradamento
Topologia della rete
Modelli locali
Modelli parametrici
(con
sorgenti
e
destinazioni)
Ogni instradamento è
possibile, e non tiene
conto in generale della
topologia
complessiva
della rete.
Permettono di includere
routers con comportamenti
che dipendono sia dalle
connessioni locali che dalla
topologia globale della rete.
Attività 4
Ottimizzazione dei coefficienti caratteristici del traffico
Coefficienti del traffico su rete
1
3
2
Rete di telecomunicazioni con un
nodo, con due linee entranti e due
linee uscenti.
4
Ottimizzazione della velocità media e ottimizzazione del tempo medio di percorrenza.
L’ottimizzazione è basata sul calcolo della soluzione del problema di Riemann alla
giunzione.
J1  v  ˆ1   v  ˆ 2   v  ˆ 3   v  ˆ 4   g  t , x,   ;
l3
l1
l2
l4
J2 



 h  t , x,   .
v  ˆ1  v  ˆ 2  v  ˆ 3  v  ˆ 4 
 , se in  out ;
 
 p, se out  in .
Attività 4
Ottimizzazione dei coefficienti caratteristici del traffico
Simulazioni
Le simulazioni sulle rete vengono fatte….
•
•
•
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).
Un’idea dal simulatore traffico
Simulazione degli algoritmi RA1 e RA2
x=0.12
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.3
d: 0.6
Distribuzione
l2: 0.6
Priorità
l5: 0.3
p: 0.2
p: 0.3
0.35
d: 0.8
0.35
d: 0.4
p: 0.8
Nome
l2: 0.4
l4: 0.8
p: 0.7
T=30
Lunghezza della
linea = 100
Densità iniziale=0
0.35
l1: 0.8
d: 0.2
x=0.1
l 2 l5
l 3 0.4 0.3
l 6 0.6 0.7
l1: 0.2
Densità iniziale=0
l4: 0.2
Lunghezza della
linea = 100
l5: 0.7
T=30
l1 l 4
l 2 0.8 0.8
l 7 0.2 0.2
0.3
Attività 4
Ottimizzazione 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: