UNIVERSIT`A DEGLI STUDI DI PISA
FACOLT `
A DI INGEGNERIA
Corso di Laurea in Ingegneria delle Telecomunicazioni Tesi di Laurea
Analisi delle prestazioni di algoritmi di scheduling basata sulla teoria del Network Calculus
Candidato: Relatori:
Giuseppina Moffa Prof. Stefano Giordano
Prof. Michele Pagano
Ing. Federico Rossi
Poich´e tutti i Possibili pretendono l’Esistenza nell’Intelletto divino in proporzione al loro grado di perfezione, il risultato di tutte queste pretese non pu`o non essere il mondo attuale come il pi`u perfetto possibile.
Indice
Introduzione v
1 Basi di Network Calculus 1
1.1 Basi del Calcolo Min-plus . . . 2
1.1.1 Alcune funzioni diF . . . . 3 1.1.2 Operazioni di base . . . 6 1.2 Curve di Arrivo . . . 14 1.3 Curve di Servizio . . . 17 1.4 Bound Fondamentali . . . 20 1.5 Concatenazione di elementi . . . 23 1.6 Shaper . . . 26 1.7 Packetizer . . . 31
2 La caratterizzazione del servizio 39 2.1 Il concetto di curva di servizio . . . 40
2.2 Alcuni elementi di rete . . . 42
ii INDICE
2.2.2 Link . . . 43
2.2.3 Regolatori di traffico . . . 44
2.2.4 Scheduler . . . 46
2.3 Server LR . . . . 47
2.3.1 Definizione formale di server LR . . . 48
2.3.2 Il modello LR come curva di servizio rate latency . . . 52
2.4 Server Guaranteed Rate . . . 55
2.5 Adaptive Service Guarantee . . . 59
2.6 Packet Scale Rate Guarantee . . . 64
3 Scheduling 71 3.1 Caratteristiche generali degli algoritmi di scheduling . . . 73
3.1.1 Fairness . . . 77 3.2 Discipline di scheduling . . . 82 3.2.1 FCFS . . . 82 3.2.2 Fair Queueing . . . 84 3.2.3 Il modello GPS . . . 85 3.2.4 Algoritmo SCED . . . 88
3.3 Deficit Round Robin . . . 92
3.4 Un modello LR per l’algoritmo DRR . . . . 95
4 Uno scenario di simulazione 103 4.1 Verifica della propriet`a di curva di servizio . . . 107
INDICE iii
4.2 Realizzazione delle simulazioni e analisi dei risultati . . . 111
4.3 Un esempio di concatenazione . . . 129
Introduzione
L’esigenza di differenziazione del servizio, imposta dal diffondersi di appli-cazioni multimediali su Internet, ha alimentato negli ultimi anni un’area di ricerca estremamente attiva per lo sviluppo e l’analisi di tecniche che permettano di garantire quella che viene genericamente indicata come QoS (Quality of Service).
A partire dall’architettura Integrated Services (Intserv) [1], il cui scopo `
e quello di differenziare il servizio con una granularit`a molto fine, pratica-mente basata sul singolo flusso, fino alla pi`u recente Differentiated Services
(Diffserv) [2], che propone l’aggregazione di pi`u microflussi in un numero limitato di classi di servizio a vantaggio di una maggiore scalabilit`a, sono sta-ti propossta-ti numerosi meccanismi per il controllo della QoS, con parsta-ticolare enfasi per gli algoritmi di scheduling e di gestione delle code.
Gli aspetti che definiscono globalmente la QoS di una rete possono essere molteplici, ad esempio l’affidabilit`a, la sicurezza e chiaramente le prestazio-ni. Metriche tipiche per la valutazione di queste ultime sono la banda, il ritardo o il jitter sul ritardo e il tasso di perdita. Il Network Calculus `e un’elegante teoria, basata sull’algebra min plus [3], proposta per quantifica-re le garanzie di QoS che le diverse architettuquantifica-re sono in grado di forniquantifica-re in
vi Introduzione
termini prestazionali, affronta cio`e il problema da un punto di vista che pu`o essere definito performance-centric.
In particolare esso fornisce efficaci astrazioni dei meccanismi di
schedu-ling e di regolazione del traffico che permettono di ricavare bound
determi-nistici in termini di throughput e ritardo end to end relativi al cosiddetto
worst case, oltre che informazioni per un dimensionamento dei buffer nei
dispositivi di rete, tale da assicurare l’assenza di perdite.
La grande forza della teoria risiede nel fatto che, poich`e l’attenzione vie-ne focalizzata sul worst case, permette di derivare garanzie deterministiche sul servizio anche senza la conoscenza delle propriet`a statistiche dei flussi d’arrivo, purch´e questi possano essere in qualche modo “limitati”. Va notato infatti che la caratterizzazione statistica dei flussi potrebbe comportare una serie di difficolt`a aggiuntive in relazione al Service Level Agreement (SLA) stabilito tra i fornitori di servizio Internet (ISP, Internet Service
Provi-der) e i sistemi utenti, in quanto non permette di valutare senza ambiguit`a eventuali violazioni da parte dei traffici dei contratti “stipulati”.
Ci`o che distingue una semplice rete best effort da una in grado di gestire la QoS `e proprio la possibilit`a di differenziare il servizio e fornire garanzie specifiche a ciascun flusso. A tal fine risulta decisiva la funzione degli al-goritmi di scheduling, la cui politica determina l’ordine in cui i pacchetti devono essere serviti.
Data la variet`a dei meccanismi di scheduling proposti in letteratura e l’eterogeneit`a delle reti esistenti, `e fondamentale disporre di uno strumento d’analisi generale che prescinda dalle peculiarit`a dello schema utilizzato. La combinazione del modello LR [4] con il concetto di curva di servizio proposto
Introduzione vii
nell’ambito della teoria del network calculus [5] per la caratterizzazione dei dispositivi di rete si rivela particolarmente adatto a tale scopo.
Nella scelta della disciplina di scheduling `e necessario tener conto di molteplici fattori tra cui la complessit`a, la fairness, la protezione, le garanzie sulle prestazioni e la regione di schedulabilit`a.
L’algoritmo di riferimento, in termini di fairness, `e costituito dal GPS [6], un modello fluido ideale, praticamente irrealizzabile, che serve i flussi in modo continuo e simultaneo. Gli algoritmi che tentano di emularne il comportamento (WFQ [7], SCFQ [8], WF2Q [9]) sono soggetti ad
un’ele-vata complessit`a computazionale, che li rende inadeguati nel caso di reti ad elevata velocit`a e comporta notevoli costi implementativi. Questi sono al-cuni dei motivi che negli ultimi anni hanno spostato l’interesse della ricerca sulle discipline di scheduling basate sul meccanismo di round robin, le qua-li vengono anche riferite come discipqua-line frame based. Queste, seppur non eccessivamente efficienti per quel che riguarda la fairness, almeno sul breve termine, in generale godono di una complessit`a di implementazione relati-vamente bassa, in quanto non prevedono complicati calcoli di deadline e, sotto opportune ipotesi, garantiscono un tempo costante per l’accodamento e il disaccodamento dei pacchetti.
Uno dei pi`u noti algoritmi frame based `e il DRR [10], che si dimostra [4] appartenere alla classe generale degli scheduler LR e per il quale sono dati [4, 11] anche alcuni bound sulla latency.
Nel presente lavoro di tesi vengono affrontate problematiche e implica-zioni pratiche dei concetti puramente teorici definiti nell’ambito della teoria del network calculus, con particolare riferimento agli scheduler DRR.
viii Introduzione
Pi`u in dettaglio, la tesi `e organizzata come segue: nel primo capitolo vengono illustrati gli elementi di base del network calculus dei quali si far`a uso nei capitoli successivi.
Nel secondo capitolo `e presentata una panoramica dei modelli sviluppati nell’ambito del network calculus per la caratterizzazione del servizio e viene inoltre data un’accurata descrizione del modello di server LR.
Nel terzo capitolo vengono affrontate le problematiche connesse con i meccanismi di scheduling, con particolare attenzione alla questione della
fairness e alla schematizzazione LR dell’algoritmo DRR
Nel quarto e ultimo capitolo si riporta l’analisi simulativa condotta per verificare la propriet`a di curva di servizio dell’algoritmo di scheduling DRR.
