Comments
Transcript
Modelli di Traffico per Reti di Telecomunicazione
Modelli di Traffico per Reti di Telecomunicazione Introduzione al corso: • introduzione ai modelli di traffico • programma del corso e modalità d’esame Università di Brescia - Facoltà di Ingegneria A.A. 2004/2005 Docenti: Alberto Signoroni - Francesco Gringoli Corso di Laurea Specialistica in Ingegneria delle Telecomunicazioni Obiettivi del corso Studio della “fenomenologia” legata al traffico trasportato in una rete di TLC – Traffico: doppio significato • movimento (traffic): bit in movimento -> bisogno di CAPACITA’ • scambio (business): scambio di messaggi -> bisogno di SERVIZIO Ricerca e applicazione di modelli matematici per l’ausilio alla decisione su problematiche di breve e di lungo periodo: es. configurazione, dimensionamento, pianificazione degli investimenti riguardanti reti di TLC – Capacità di soddisfare (servire) le “richieste” • Problema delle PERDITE • Problema dei RITARDI Lucido 2 GRADO di SERVIZIO offerto Modelli di Traffico per Reti di TLC - a.a.2004/05 Modellistica per un sistema di TLC Ricercare e adottare un buon MODELLO è esigenza comune nei processi deduttivi e decisionali (descrizione e risoluzione di problemi). Nei sistemi e reti di TLC, modelli di traffico possono essere adottati per singole componenti o porzioni estese del sistema. Per ciascuna situazione da affrontare, nella ricerca di un buon modello sono necessarie: • conoscenza delle tecnologie e degli apparati coinvolti • conoscenza degli strumenti matematici (in particolare processi stocastici) ed un MODELLO di TRAFFICO verrà descritto in termini di • proprietà statistiche del traffico (es. richieste Poissoniane) • struttura (es. coda di attesa con N serventi) • comportamento (es. paritario vs criteri di priorità) Lucido 3 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Modellistica per un sistema di TLC mondo deterministico mondo stocastico MODELLO trend periodici TRAFFICO (USERS) STRUTTURA (HW) mobile-net guasti COMPORTAMENTO (SW) La natura statistica del TRAFFICO e le relazioni tra le componenti del modello richiedono l’utilizzo degli strumenti matematici relativi ai processi stocastici Lucido 4 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Modellistica per un sistema di TLC Metodologia per la ricerca di un modello : metodologia a spirale propongo o raffino un modello deduco i parametri del modello osservo calcolo risultati estraggo dati confronto con le attese Strumenti per la ricerca di un modello: strumenti teorici Lucido 5 case studies Modelli di Traffico per Reti di TLC - a.a.2004/05 simulazione … Modellistica per un sistema di TLC Nella modellizzazione del traffico per reti di TLC viene spesso utilizzato il termine “Teletraffico” Problematiche di cui si occupa l’ingegneria del Teletraffico Analisi e misurazione delle prestazioni del sistema: – sono noti: dimensionamento e traffico Progetto delle infrastrutture e servizi di rete: – sono noti: prestazioni e traffico Pianificazione degli investimenti e delle risorse: – sono: prestazioni e dimensionamento (eventualmente previsioni di traffico per stabilire un piano temporale degli interventi) Lucido 6 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Modellistica per un sistema di TLC “Ingegneria del Teletraffico” : applicazione della teoria della probabilità alla soluzione di problematiche di pianificazione, valutazione di prestazioni, funzionamento e manutenzione dei sistemi di telecomunicazione. [Teletraffic Engineering Handbook - TEH] http://www.tele.dtu.dk/teletraffic/ Lucido 7 Modelli di Traffico per Reti di TLC - a.a.2004/05 Programma del corso… MODELLI di TRAFFICO per RETI di TELECOMUNICAZIONE Modellistica per le Reti di TLC Modelli stocastici: Sistemi a Coda • reti con perdite • reti con attesa senza perdite • reti con attesa e perdite Tipologie, valutazione e misura del Traffico • traffico offerto, smaltito, rifiutato, reinstradato • grandezze e unità di misura del traffico PRIMA PARTE del corso Lucido 8 Reti telefoniche Reti a commutazione di pacchetto Reti mobili e wireless - Componenti delle reti: • “nodi” (commutazione, instradamento, controllo di congestione, politiche di accesso al mezzo) - Servizi e Grado di Servizio (GoS) - Affidabilità e manutenzione SECONDA PARTE del corso Modelli di Traffico per Reti di TLC - a.a.2004/05 Programma del corso: prima parte Sistemi a coda (teoria delle code e reti di code) I sistemi a coda possono essere visti come classe applicativa della generica famiglia dei sistemi di flusso (trasporto merci, acquedotti, telefonia, circolazione sanguigna, servizio mensa, processi produttivi, programmazione multi-thread, sportelli pubblici,…) n1 ti n2 A B n3 Siamo interessati, per esempio, al servizio di trasporto sul percorso AÆBÆA (es. chiamata telefonica) : • vi sono nodi (che eseguono operazioni, compiti) e canali (ove fluisce il traffico ti) • il traffico è costituito da un flusso di entità da trasportare • caratteristiche del traffico: istanti di richiesta di un servizio (arrivi), loro entità • il nodo fornisce un servizio in un certo tempo, può quindi essere libero o occupato • nei nodi si possono sperimentare CODE (attese) o PERDITE (superi di capacità, guasti) Lucido 9 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Programma del corso: prima parte Domande che si pone l’entità in coda: Perché devo stare in coda ? Quanto a lungo dovrò aspettare per essere servito ? In quale momento potrei essere servito più rapidamente ? Quante entità devono essere servite prima di me ? Qual è il tempo medio di servizio ? Posso prendere un appuntamento ? Posso scavalcare la coda ? C’è un percorso alternativo più conveniente ? Corro il rischio di non essere affatto servito ? Gli strumenti necessari per rispondere a queste domande (tranne che alla prima…) e ad altri quesiti sono descritti all’interno della teoria delle code Il flusso (traffico) è casuale Æ occorre identificare i processi stocastici che descrivono: sequenza degli arrivi Lucido 10 struttura e disciplina di servizio Modelli di Traffico per Reti di TLC - a.a.2004/05 … Programma del corso: prima parte Teoria delle code e reti di code Materiale di riferimento Processi di Markov – Introduzione ai processi markoviani – Catene di Markov a tempo discreto – Catene di Markov a tempo continuo – Processi di nascita/morte Processi di arrivo Testo – A. Papoulis – S.U. Pillai, “Probability, Random Variables and Stochastic Processes”, 4th ed., McGrawHill, 2002. – L. Kleinrock, “Sistemi a coda”, Hoepli, 1992. – Generalità sui processi puntuali di arrivo Lucidi forniti durante il corso – Teorema di Little Materiale utile reperibile su WEB – Processi Poissoniani Elementi di teoria delle code – Notazione di Kendall – Code markoviane M/M/1, M/M/n, M/M/∞ – Altre code fondamentali Reti di code – Reti di code Markoviane aperte e chiuse – Teorema di Burke – Reti di code acicliche Lucido 11 – ITU-D SG2, “Teletraffic Engineering Handbook”, V.B. Iversen (ed.), 2003, http://www.tele.dtu.dk/teletraffic/ – E. Brockmeyer, et al. “The life and works of A.K. Erlang” Trans. of the Danish Academy of Technical Sciences, No.2, 1948. http://www.com.dtu.dk/teletraffic/Erlang.html – Sito del corso di “Modelli di Reti di TLC” – Politecnico di Torino http://www.tlc-networks.polito.it/Modelli_reti/ Modelli di Traffico per Reti di TLC - a.a.2004/05 Programma del corso: seconda parte Applicazione dei modelli di traffico per il dimensionamento e la simulazione delle reti di TLC 1. 2. 3. 4. 5. Congestione nelle reti a pacchetto a. Definizione di congestione e principi generali di controllo b. Qualita del servizio (QoS) c. Controllo della congestione nei flussi end-to-end TCP d. Evoluzione del protocollo TCP: Tahoe, Reno, New Reno, SACK Introduzione alla simulazione di una rete a pacchetti: simulazione ad eventi discreti a. Descrizione di Network Simulator 2 (NS2) b. Programmazione di NS2: script Otcl Architettura dei router per il supporto della QoS a. Algoritmi per il traffic shaping: leaky bucket, token bucket b. Politiche di gestione delle code: FIFO, FQ, Bit-Round FQ, WFQ c. Politiche avanzate di gestione della congestione: RED. ECN d. Classi di traffico: CBR, VBR, ABR, UBR. Tecniche di accesso al mezzo: allocazione statica del canale, allocazione dinamica del canale a. Protocolli ad accesso multiplo: ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA b. Corrispondente analisi prestazionale Introduzione alla teoria della commutazione a. Reti di connessione b. Teorema di Clos, reti di Clos c. Proprieta di un nodo di commutazione: reti bloccanti, non bloccanti e riarrangiabili, reti multistadio, topologie STS e TST Lucido 12 Modelli di Traffico per Reti di TLC - a.a.2004/05 Orario, prerequisiti, modalità d’esame Orario – Lunedì N7 14:30 – 18:30 (normalmente fino alle 17:30) – Giovedì Elab2 14:30 – 18:30 (normalmente fino alle 17:30) Prerequisiti – Reti di Telecomunicazione A – Teoria dei Fenomeni Aleatori Modalità d’esame – Scritto (esercizi e teoria) e orale Sito Web: http://www.ing.unibs.it/tlc/didattica/modtraf/ E-mail: Lucido 13 [email protected] [email protected] Modelli di Traffico per Reti di TLC - a.a.2004/05 Modelli di Traffico per Reti di Telecomunicazione Concetti di base relativi al traffico: • definizioni, misure e variazioni del traffico • Grado di Servizio in un sistema di TLC Università di Brescia - Facoltà di Ingegneria A.A. 2004/2005 Docenti: Alberto Signoroni - Francesco Gringoli Corso di Laurea Specialistica in Ingegneria delle Telecomunicazioni Definizione e misura del traffico Il termine traffico viene solitamente usato in riferimento ad una “intensità” di traffico, che possiamo definire come segue: DEF Intensità di traffico (Erlang): rispetto ad un pool di risorse di servizio, si definisce quantità istantanea di traffico il numero di risorse occupate n(t) ad un certo istante temporale t. DEF Intensità media di traffico nell’intervallo T : è la media temporale di n(t) I(T ) = nT ,t0 1 t0 + T = ∫ n(t)dt T t0 Unità di misura di I : erlang [erl] o [E] (adimensionale) DEF Volume di traffico V(T ) = T ⋅ I(T ) Unità di misura di V (con T = 1h) : erlang-ora [Eh] Lucido 15 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Definizione e misura del traffico Traffico Smaltito (carried) As : traffico smaltito da un gruppo di risorse di servizio in un sistema di TLC in un certo intervallo di tempo T. E’ una quantità misurabile. Si esprime in termini di intensità di traffico media (in erlang - erl). Esempio risorse: 10 servitori; mediamente 3.5 servitori risultano impegnati (es. linee occupate) Æ As=3.5 erl NB: nel caso di una sola linea 0≤ As ≤1 erl, se As=1erl significa che la linea è occupata per il 100% del tempo. Se ho m linee e sempre As=1erl, significa che le linee sono occupate per il (100/m)% del tempo. da [TEH] In figura si mostra una misurazione dell’intensità di traffico (istantanea e media) smaltita. Lucido 16 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Definizione e misura del traffico Traffico Offerto (offered) A : è una quantità teorica e indipendente dal sistema; corrisponde al traffico smaltito da un sistema con risorse di servizio illimitate, ovvero da un sistema di TLC che non rifiuta nessuna chiamata. Equivale a: A = λ⋅s dove λ : frequenza degli arrivi (es. frequenza media di chiamate nell’unità di tempo) s : tempo medio di servizio (es. durata media della chiamata) Esempio risorse: λ = 10 chiamate/ora , s = 0.35 ora/chiamata Æ A = 3.5 erl NB: Unità di misura erlang (adimensionale e indipendente dall’unità di tempo usata) Traffico Perso o Rifiutato (lost or rejected) Ap : traffico non gestibile a causa di una mancanza di capacità di servizio (sistemi con perdita). E’ sempre vero che: Ap = A − As ovvero A = As + Ap = (λs + λp)⋅ s con λs frequenza di richieste smaltite e λp frequenza di richieste rifiutate. Dalla misurazione di λs e di s, possiamo esprimere As= λs⋅s Lucido 17 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Definizione e misura del traffico Utilizzo di un sistema di traffico (traffic theory) U= λs ⋅ s m Con m numero di servitori (risorse, linee). U indica la percentuale media di tempo in cui un servitore risulta occupato (se tutti i servitori sono uguali), oppure anche la frazione dei servitori in media occupati. NB: in un sistema in regime stabile dovrà necessariamente essere 0 ≤ U < 1. Utilizzo di un canale di trasmissione dell’informazione (information theory) In questo caso s può rappresentare l’esigenza media di trasmissione espressa in bit/accesso e λs numero di accessi/sec. Data C, capacità del canale, espressa in bit/sec, definiamo l’utilizzo del canale di trasmissione come: U= λs ⋅ s C NB: teoria dell’informazione e teoria del traffico hanno punti in comune ma vanno tenute distinte. Non utilizzeremo concetti di teoria dell’informazione in qs corso. Lucido 18 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Definizione e misura del traffico ESERCIZIO Traffico di connessioni Internet Dial-Up: i 500 utenti di un nodo di accesso generano dalle 20:30 alle 21 un numero medio di 150 connessioni Internet della durata media di 9 minuti e velocità di trasferimento media 32kbps. Valutare il traffico offerto, quello generato da ciascun utente ed il volume di traffico orario. • intensità di chiamata λ=150 chiamate/mezzora = 300 call/hour, • tempo medio di chiamata s= 9 minuti Æ traffico offerto A=(300/60)x9=45 erl Æ traffico generato in media da ogni utente 45/500=0.09 erl Æ volume di traffico orario V=45x1h=45 Eh nb il bit-rate di trasferimento dati non c’entra nulla con il traffico offerto Lucido 19 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Definizione e misura del traffico ESERCIZIO Traffico in una officina meccanica: in un’officina autorizzata per la revisione di autoveicoli arrivano 5 clienti/ora, il tempo medio di revisione è di 15 minuti, ed un 30% delle autovetture deve fermarsi in officina per piccole riparazioni, con un tempo medio della riparazione di 25 minuti. Calcolare il traffico sulle catene di revisione e nell’area riparazioni. • traffico revisione ARev= 5 clienti/ora ⋅ 1/60 ora/min ⋅ 15min = 1.25 erl • traffico riparazioni ARev= 5 ⋅ 30/100 ⋅ 1/60 ⋅ 25 = 0.625 erl • traffico complessivo A = 1.25 + 0.625 = 1.875 erl Osservazioni: i valori di traffico sono valori medi. Sono indicatori per il dimensionamento. Si capisce che non basta 1 catena di revisione mentre può risultare sufficiente una postazione di riparazione. Dal traffico complessivo si può pensare che sia possibile allestire una o entrambe le catene di revisione come postazione di riparazione al bisogno. Tuttavia per poter dimensionare il “sistema officina” secondo criteri di Grado di Servizio (performance del sistema) e Qualità di Servizio (sperimentate dall’utente), occorrerà definire tali criteri ed affrontare un problema di gestione delle code (occorrerà definire un Modello di Traffico). Lucido 20 Modelli di Traffico per Reti di TLC - a.a.2004/05 Variazioni di traffico Variazioni di traffico sono dovute a fenomeni diversi e su scale temporali anche molto disomogenee: Variazioni di lungo periodo - trend (anni): progresso tecnologico, cambiamenti sociali… Utilizzati nella predizione per il dimensionamento e gli investimenti infrastrutturali. Variazioni di medio periodo - variazioni stagionali (mesi): periodi di vacanza - periodi con scadenze… - variazioni settimanali (giorni) giorni feriali - festivi - variazioni giornaliere (ore): ore notturne - ora di punta, … Si possono definire fluttuazioni casuali attorno a profili caratterizzanti Variazioni di breve periodo - fluttuazioni casuali (minuti-secondi): gli utenti agiscono indipendentemente gli uni dagli altri, modellizzazione stocastica dei processi di arrivo (processi di Poisson), Variazioni da suddividere in variazioni di frequenza degli arrivi (es. intensità delle chiamate telefoniche) e variazioni del tempo medio di servizio (es. durata delle telefonate, tempo di occupazione delle linee) Lucido 21 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Variazioni di traffico Esempio [TEH]: rilevazione del numero di chiamate in una centrale di commutazione telefonica (Danimarca, 1973). Distribuzione media giornaliera: Risoluzione temporale: 15’ Periodo di osservazione: 10 giorni lavorativi (lun-ven) Distribuzione di un lunedì mattina Risoluzione temporale: 1’ Si noti • lieve scostamento dal trend • fluttuazioni casuali Lucido 22 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Variazioni di traffico Esempio [TEH]: Internet Danimarca Dial-up connections (19 gennaio 1999) Numero medio di chiamate Durata media della chiamata (sec) Lucido 23 Modelli di Traffico per Reti di TLC - a.a.2004/05 Il concetto di “ora di punta” “Ora di punta” (busy hour): si può intuire come questo concetto risulti importante nel dimensionamento di un sistema di flusso (di servizio, di TLC). L’obiettivo è quello di avere un riferimento giornaliero (eventualmente legato ai trend di più lungo periodo*) di picco di traffico e di momento nel quale esso avviene. Il giorno scandisce la vita degli utenti e ritma i carichi degli apparati. La quantità “ora” (60 min) è commisurata ad un periodo di tempo né troppo lungo (per evitare scarsa risoluzione temporale del posizionamento) né troppo corto (per evitare scarsa confidenza statistica del posizionamento). Diverse definizioni di “ora di punta”: •TCBH (time consistent busy hour): i 60’ (accuratezza d’inizio: 15’) in cui, in base ad un certo periodo* di osservazione, si verifica in media il traffico più elevato. •ADPH (average daily peak hour): media, su un certo periodo*, dei valori di traffico rilevati durante l’ora di picco giornaliera. •FDMH (fixed daily measured hour): fissata una certa ora del giorno, è la media del traffico rilevato in quell’ora rispetto ad un certo periodo* di osservazione. AADPH ≥ ATCBH ≥ AFDMH Lucido 24 Modelli di Traffico per Reti di TLC - a.a.2004/05 Il concetto di “blocco” “Blocco” di un sistema di TLC: un sistema di TLC (es. telefonico) non viene dimensionato in modo da poter ospitare contemporaneamente le chiamate di tutti gli utenti, ma viene dimensionato in modo che possa gestire il traffico dell’ora di punta con un certo (solitamente ampio) margine di funzionamento (in modo da poter gestire burst momentanei del traffico). • L’esperienza dell’utente dovrebbe essere la medesima di quella di avere sempre a disposizione una linea di chiamata (multiplexing statistico). • Dai valori di traffico offerto nell’ora di punta vengono ricavati (secondo criteri di Grado di Servizio) i parametri di dimensionamento del sistema per quanto riguarda il traffico smaltito. • Il dimensionamento secondo i criteri scelti determina le performance del sistema, che andranno costantemente misurate nel tempo. • Tuttavia il corretto dimensionamento e la garanzia di un certo Grado di Servizio non garantiscono il buon fine di ciascuna chiamata da parte dell’utente. Nel sistema (o in una sua parte) si può verificare una condizione di blocco (secondo una certa probabilità di blocco PB) di una chiamata, quando viene superata la capacità del sistema di servire chiamate (A>m). Lucido 25 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Il concetto di “blocco” Æ Sistemi con perdite (loss systems): La chiamata che sperimenta un blocco viene scartata (persa). Performance coinvolte: call congestion: frazione di chiamate che osservano tutte le risorse o serventi occupati time congestion: frazione di tempo in cui tutti i serventi sono occupati traffic congestion: frazione di traffico non gestito o perso, eventualmente dopo più tentativi Æ Sistemi con attesa (waiting systems): La chiamata che sperimenta un blocco viene messa in una coda d’attesa (buffer). Performance coinvolte: waiting time: tempo di attesa – di interesse il suo valor medio e la sua distribuzione statistica Politiche d supporto: Preventive: controllo di congestione Correttive: reinstradamento, ricerca di un percorso alternativo Problematiche coinvolte nel dimensionamento e nella valutazione delle performance di un sistema di TLC (es. telefonica): • intensità di chiamata λ (ora di punta, es. arrivi Poissoniani) • comportamento dell’utente (es. tasso di tentativi su linea occupata vs “tasto 5”) • errori umani (es. “attenzione, il numero selezionato è inesistente”) • stato del ricevente (es. “tu tu tu tu…”) • blocco del sistema (PB) Lucido 26 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Il concetto di “blocco” Probabilità di blocco: formula di Erlang (Erlang-B) PB = Π p ( A, m) = Am m! Ai ∑i =0 i! m con A = traffico offerto m = numero di servitori (linee) PB = probabilità di blocco Πp= probabilità di perdita Viene impiegata nei sistemi con perdite, nell’ipotesi che la chiamata bloccata venga automaticamente persa (cancellata). • Formula che approssima bene la situazione di traffico sulla rete telefonica tradizionale (arrivi poissoniani). • Noi la vedremo nell’ambito dei sistemi a coda, in particolare questo è un caso di sistema con perdita a coda nulla. • Traffico smaltito e persoperso Ac=A⋅(1- Πp) Ap=A⋅Πp Lucido 27 ESEMPIO numero di linee in funzione del traffico con Πp= 1% A m A/m 3 8 2.7 10 18 1.8 30 42 1.4 100 117 1.17 300 324 1.08 1000 1029 1.03 NB al crescere di m, mÆA Modelli di Traffico per Reti di TLC - a.a.2004/05 … Il concetto di “blocco” ESEMPIO A=3erl, m=6, Πp Erlang-B 36 6! Πp = 0 = 0.0522 1 2 3 3 3 33 34 35 36 + + + + + + 0! 1! 2! 3! 4! 5! 6! m A Lucido 28 Erlang-B A Modelli di Traffico per Reti di TLC - a.a.2004/05 Æ 5.2% Grado di Servizio (GoS) Service (network) QoS User experience GoS QoS definita in ITU-T recomendation E.800 come: The collective effect of service performance, which determine the degree of satisfaction of a user of a service. GoS definita in ITU-T recomendation E.600 come: A number of traffic engineering variables to provide a measure of adequacy of a group of resources under specified conditions. These GoS variables may be probability of loss, dial tone delay, etc. Lucido 29 Modelli di Traffico per Reti di TLC - a.a.2004/05 … Grado di Servizio (GoS) Teoria delle code e delle reti di code strumento teorico utile al progettista della rete Parametri di QoS relativi al traffico Politiche di servizio ? GoS standard (progetto) GoS results (sistema reale) Politiche di progetto Service Level Agreement – SLA contratto tra utente e gestore di reti di TLC in cui l’utente (che desidera una certa QoS) comprende cosa possa garantire il sistema in termini di GoS Lucido 30 Modelli di Traffico per Reti di TLC - a.a.2004/05