Comments
Description
Transcript
RETI DI TELECOMUNICAZIONE Definizioni
RETI DI TELECOMUNICAZIONE Reti di Code Definizioni ¾ In molti sistemi gli utenti per ottenere un servizio devono attraversare diversi serventi in cascata 9 Dopo aver ottenuto il servizio da un servente devono mettersi in attesa per ottenere il servizio offerto da un successivo servente ¾ Tali sistemi possono essere modellati come una rete di code ¾ Le reti a commutazione di pacchetto sono un classico esempio di rete di code ¾ Le reti di code possono essere 9 Chiuse Il numero di pacchetti è fisso, si ha solo circolazione del traffico in rete 9 Aperte Il numero di pacchetti è variabile, il traffico viene immesso nella rete in opportuni nodi e può uscire dalla rete da altri nodi Reti di Code 2 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 1 Definizioni ¾ Esempio rete di code aperta ¾ Esempio rete di code chiusa Reti di Code 3 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Esempio ¾ Il mescolarsi dei flussi di traffico complica la caratterizzazione dello stesso ai vari nodi: 9 Si consideri il seguente esempio relativo a una cascata di due nodi 9 Al sistema arrivano pacchetti che seguono una distribuzione di Poisson e di dimensione fissa 9 Supponiamo sia C1=C2=C la capacità di trasmissione dei due nodi 9 La prima coda può essere modellata come un sistema M/D/1 Se la lunghezza di ogni singolo pacchetto è L, sarà T = 1/µ = L/C il tempo di trasmissione degli stessi Dal primo nodo usciranno pacchetti di dimensione L ad intervalli T1≥ T 9 Nella seconda coda quindi non vi sarà mai accodamento dato che ogni pacchetto che arriva viene sempre trasmesso in un tempo T2 = T Reti di Code 4 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 2 Teorema di Jackson Modello del generico nodo i della rete di code Reti di Code 5 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson ipotesi ¾ Consideriamo un generico nodo i di una rete di code aperta costituita da K nodi che soddisfano le seguenti condizioni: 1. Ogni nodo è un sistema M/M/mi: 9 Il nodo i ha mi serventi e il tempo di servizio medio è 1/µi 2. I clienti arrivano al generico nodo i con una frequenza (1) 9 Il primo termine è relativo ai clienti che vengono dall’esterno 9 Il secondo termine è relativo ai clienti che vengono dagli altri nodi 9 Un cliente che finisce il suo servizio al nodo i si trasferisce immediatamente ad un altor nodo j con probabilità qij o lascia la rete con probabiltià qid , sarà (2) Reti di Code 6 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 3 Teorema di Jackson tesi ¾ Se indichiamo con il vettore la configurazione in cui ci siano ni clienti accodati alla generica i-esima coda ¾ Sarà la probabilità che tale configurazione si verifichi ¾ Nelle ipotesi fatte sarà dove con Pi {ni } si è indicata la probabilità che nella coda i siano accodati ni clienti (risultato in forma prodotto) Reti di Code 7 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Applicando le equazioni di bilanciamento globale al vettore si trova (3) Dove rappresenta il rate con il quale si raggiunge una configurazione n perché arriva un cliente dall’esterno (1° termine) un cliente viene servito ed esce dalla rete (2° termine) un cliente viene servito e si accoda su un altro nodo della rete (3° termine) Reti di Code 8 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 4 Teorema di Jackson dimostrazione ¾ Sarà infatti ¾ Sostituendo la (2) nella (3) si trova (4) Reti di Code 9 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ La precedente equazione è soddisfatta dalla seguente relazione (5) 9 che costituiscono le equazioni di bilanciamento dettagliate secondo le quali la frequenza secondo la quale una determinata coda cambia stato per incremento del numero di pacchetti è uguale alla stessa frequenza secondo la quale la stessa coda (o un’altra coda nel sistema) cambia stato per decremento del numero di pacchetti ¾ Per la dimostrazione sostituiamo la (5) nella (4) Reti di Code 10 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 5 Teorema di Jackson dimostrazione ¾ Semplificando i termini si trova ciò dimostra che le equazioni di bilanciamento dettagliate soddisfano l’equazione di bilanciamento globale Reti di Code 11 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Sviluppando la (5) possiamo scrivere posto i ¾ Indicato con e con posto i Reti di Code 12 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 6 Teorema di Jackson dimostrazione possiamo scrivere ¾ Il procedimento può essere ripetuto per la posizione j per cui Reti di Code 13 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Generalizzando per tutti i K nodi della rete si ricava ¾ Per determinare la probabilità dello stato 0 consideriamo la condizione di normalizzazione su tutte le possibili configurazioni ¾ Sostituendo la relazione trovata Reti di Code 14 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 7 Teorema di Jackson dimostrazione ¾ Se ipotizziamo che esiste una distribuzione di probabilità stazionaria deve essere ¾ Nella relazione si può quindi scambiare la sommatoria con la produttoria la sommatoria può essere riscritta come Reti di Code 15 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Applicando la soluzione per la serie geometrica di ragione < 1 si trova ¾ E quindi la dimostrazione del teorema Reti di Code 16 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 8 Teorema di Jackson dimostrazione ¾ Il teorema vale anche per reti di code chiuse ¾ In questo caso non esiste traffico entrante per cui l’equazione (2) può essere riscritta come (2') ¾ Analogamente la (3), equazione di bilanciamento globale, diviene (3') Dato che i pacchetti che vengono serviti da una coda vengono sempre accodati in un’altra Reti di Code 17 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Anche in questo caso le equazioni di bilanciamento dettagliate assumono la forma (5') ¾ Ancora una volta queste equazioni soddisfano l’equazione di bilanciamento globale (4'), sostituendo… Reti di Code 18 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 9 Teorema di Jackson dimostrazione … 9 C.V.D. Reti di Code 19 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Teorema di Jackson dimostrazione ¾ Anche in questo caso sarà ¾ Da cui generalizzando per tutti i K nodi della rete ¾ Osserviamo però che per 9 In una rete chiusa, se il numero N di pacchetti è superiore al numero K di nodi, qualche nodo dovrà sempre contenere dei pacchetti accodati Reti di Code 20 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 10 Teorema di Jackson dimostrazione ¾ In generale si trova quindi che ¾ Tenendo in considerazione tutte le possibilità nelle quali gli N pacchetti si possono accodare nei K nodi Reti di Code 21 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Approssimazione di indipendenza di Kleinrock ¾ Una rete a commutazione di pacchetto può essere modellata come una rete di code aperta ¾ La correlazione fra i tempi di interarrivo in un nodo e la distribuzione dei tempi di servizio nel nodo precedente non permettono di applicare il teorema di Jackson ¾ In particolari condizioni si può applicare il principio di indipendenza di Kleinrock che consente di considerare indipendenti i tempi di interarrivo e la lunghezza dei pacchetti Reti di Code 22 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 11 Approssimazione di indipendenza di Kleinrock ¾ Consideriamo una rete in cui i flussi entranti seguono percorsi p(K) costituiti da sequenze di collegamento ¾ Se Xp(k) è la frequenza di arrivo del percorso p(k) allora la frequenza di arrivo globale fra un generico nodo i e un generico nodo j sarà dove la sommatoria è estesa a tutti i percorsi che attraversano il collegamento (i, j) ¾ Il principio di Kleinrock dice che il mescolarsi dei vari flussi di traffico che attraversano un collegamento (i, j) ha l’effetto di ripristinare le condizioni di indipendenza tra tempi di arrivo e lunghezza dei pacchetti Reti di Code 23 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Approssimazione di indipendenza di Kleinrock ¾ L’approssimazione è ragionevole se: 9 Gli arrivi ai nodi d’ingresso della rete sono poissoniani 9 Le lunghezze dei pacchetti sono distribuiti esponenzialmente 9 Il carico in rete è vicino ai valori massimi ¾ Se è vero l’approssimazione di Kleinrock possiamo considerare valido il teorema di Jackson per cui si può assumere il modello M/M/1 per ogni collegamenti (i, j) ¾ Il valore atteso di pacchetti in coda sarà dove 1/µij è il tempo di trasmissione medio sul collegamento (i, j) Reti di Code 24 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 12 Approssimazione di indipendenza di Kleinrock ¾ Per ogni singolo collegamento possiamo applicare il teorema di Little per cui il tempo medio di attesa in coda sul singolo collegamento (i, j) sarà ¾ Considerata la frequenza di arrivo del traffico totale in ingresso al sistema sarà Reti di Code 25 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Approssimazione di indipendenza di Kleinrock ¾ Applicando ancora la legge di Little si può ricavare il tempo di attesa medio dei clienti nel sistema ¾ Il periodo medio di attraversamento del sistema dato un particolare percorso p(k) può essere calcolato sommando i percorsi medi su ogni tratta che lo interessa Reti di Code 26 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 13 Esempio Reti di Code 27 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) Esempio ¾ Supponendo che il rate di servizio medio sia di 3 pacchetti/secondo calcolare 9 Il ritardo medio sul collegamento 1-2-3 9 Il ritardo medio su tutta la rete Reti di Code 28 Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano) 14