Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giorgio Ventre » 2.Tecniche ed Architetture per la Quality of Service


Indice della lezione

  • Perché Internet “Better-than-Best-Effort” con la Quality of Service (QoS) ?
  • Blocchi strutturali della QoS
  • Protocolli end-to-end: RTP, H.323
  • Protocolli di rete:
    • Integrated Services (IntServ), RSVP.
    • Scalable differentiated services: DiffServ
  • Control Plane: QoS Routing, Traffic Engineering (TE), policy management, pricing models

Perché “Better-than-Best-Effort (QoS)” ?

  • Per supportare un ampio range di applicazioni
    • Real-time, Multimedia, etc
  • Per sviluppare modelli economici sostenibili e nuovi servizi di rete privati
    • Modelli di costo “tutto compreso”, e servizi best-effort non adeguati al business

Quality of Service: Cos’è?

Cos’è la QoS?

  • Migliori performance così come descritto da un set di parametri oppure da misure eseguite in funzione di un set di metriche
  • Parametri generali:
    • Bandwidth
    • Delay, Delay-jitter
    • Packet loss rate (o loss probability)
  • Parametri di Trasporto/Applicazione
    • Timeouts
    • Percentuale di pacchetti “importanti” persi

Cos’è la QoS (contd)?

  • Tali parametri possono essere misurati a differenti livelli di granularità:
    • “Micro” flusso, flusso aggregato, gruppo.
  • QoS considerata “migliore” se:
    • più parametri possono essere specificati;
    • la QoS può essere specificata ad una granularità fine.
  • Spettro della QoS:
    • Best Effort
    • Leased Line

Problemi Fondamentali

Nel caso di disciplina di scheduling di tipo FIFO, il livello di performance assegnato ad un flusso è legato all’arrivo dei pacchetti di tutti gli altri flussi!

  • Non è possibile rendere la QoS gratuita a tutti.
  • Nasce la necessità di utilizzare nuove discipline di scheduling.
Disciplina di scheduling di tipo FIFO

Disciplina di scheduling di tipo FIFO


Problemi Fondamentali

  • Legge di Conservazione
    • (Kleinrock): Σρ(i)Wq(i) = K
  • Indipendentemente dalla disciplina di scheduling selezionata:
    • Il backlog (ritardo) medio è costante.
    • La bandwidth media è costante.
  • Lo Zero-sum game:
    • È necessario riservare risorse per servizi “premium” (di qualità superiore).
Diagramma lavoro/tempo

Diagramma lavoro/tempo


QoS Big Picture: Control/Data Planes

Control Plane

Signaling (Segnalazione); Admission Control oppure Service Level Agreement (Contrattazione); Provisioning/Traffic Engineering (Ingegneria del Traffico/della Fornitura).

Data Plan

Traffic Conditioning (Condizionamento del Traffico): shaping (formazione), policing (controllo), marketing, etc; Traffic Classification (Classificazione del Traffico); Scheduling (Schedulazione); Buffer management (Gestione del Buffer).

QoS Big Picture

QoS Big Picture


Componenti della QoS

  • QoS _ riservare risorse per servizi premium (di qualità superiore)
  • Componenti della QoS:
    • Individuazione di servizi premium (Service/Service Level Agreement design).
    • Quante risorse riservare? (Admission Control/Provisioning).
    • In che modo controllare l’utilizzo delle risorse di rete, come eseguire distribuzione del carico, come gestire in maniera flessibile aggregati di traffico e percorsi? (QoS Routiong, Traffic Engineering).

Componenti della QoS

  • In che modo riservare effettivamente tali risorse in modo distribuito?
    • (Signaling, Provisioning, Policy).
  • In che modo lanciare il servizio quando arriva traffico?
    • (Traffic Shaping, Classification, Scheduling).
  • In che modo monitorare la qualità, valutare e prezzare tali servizi?
    • (Network Management, Accounting, Billing, Pricing).

Come aggiornare Internet per la QoS?

  • Approcci: disaccoppiare l’evoluzione degli end-system dall’evoluzione della rete
  • Protocolli end-to-end: RTP, H.323 etc per incitare la crescita di applicazioni multimediali in grado di adattarsi.
    • Immaginare nuvole best-effort oppure better-than-best-effort.
  • Protocolli di rete: IntServ, DiffServ, RSVP, MPLS, COPS …
    • Per supportare potenzialità better-than-best-effort a livello rete (livello IP).
  • Specifiche per la QOS
  • Traffico
  • Caratterizzazione dei servizi
  • Meccanismi basilari

Specifica dei servizi

  • Loss: probabilità che un pacchetto del flusso venga perso.
  • Delay: tempo che un pacchetto del flusso impiega per arrivare da sorgente a destinazione.
  • Delay jitter: massima differenza tra i ritardi effettivi di due pacchetti del flusso.
  • Bandwidth: massima velocità a cui la sorgente può trasmettere traffico.
  • QoS spectrum:
    • Best Effort
    • Leased Line

Hard Real Time: Servizi Garantiti

  • Contratto di servizio:
    • Network to client: garantire un limite superiore deterministico sul delay per ogni pacchetto in una sessione.
    • Client to network: la sessione non invia più di quello che specifica.
  • Algoritmi di supporto:
    • Admission control basato sull’analisi del caso peggiore.
    • Classification/Scheduling per flusso sui router.

Soft Real Time: Servizio a carico controllato

  • Contratto di servizio:
    • Network to client: prestazioni simili a quelle di una rete best-effort scarica.
    • Client to network: la sessione non invia più di quello che specifica.
  • Algoritmo di supporto:
    • Admission control basato sulla misura di aggregati.
    • Possibilità di eseguire lo Scheduling per aggregato.

Caratterizzazione di traffico e di servizio

  • Per quantificare un servizio bisogna conoscere:
    • Flussi di traffico in arrivo.
    • Il servizio fornito dai router (es.: risorse riservate ad ogni router).
  • Esempi:
    • Caratterizzazione del traffico: token bucket.
    • Il servizio fornito dal router: velocità fissa e dimensione del buffer fisso.

Token Bucket

  • Caratterizzazione in funzione di tre parametri (b, r, R)
    • b: token depth
    • r: average arrival rate
    • R: maximum arrival rate (cioè, capacità del link R)
  • Un bit può essere trasmesso solo quando c’è un token disponibile
    • Quando un bit viene trasmesso risulta consumato esattamente un solo token.
Token bucket

Token bucket


Caratterizzare una sorgente col Token Bucket

  • Curva di arrivo: massima quantità di bit trasmessa al tempo t
  • Utilizzare il Token Bucket per limitare la curva di arrivo
Curva di arrivo

Curva di arrivo


Esempio

  • Curva di arrivo: massima quantità di bit trasmessa al tempo t
  • Utilizzare il Token Bucket per limitare la curva di arrivo
Diagramma dell’esempio

Diagramma dell'esempio


Prenotazione Per-hop

  • Considerati b, r, R ed il ritardo per-hop d
  • Allocare banda ra e spazio all’interno del buffer Ba in modo da garantire d
Prenotazione Per-hop

Prenotazione Per-hop


Cos’è un Service Model?

  • Le misure relative alla QoS (delay, troughput, loss, cost) dipendono dal traffico offerto ed eventualmente da altri processi esterni
  • Un service model cerca di caratterizzare la relazione tra traffico offerto, traffico consegnato, ed eventualmente altri processi esterni
Service Model

Service Model


Processo di Arrivo e Partenza

Processo di Arrivo e Partenza

Processo di Arrivo e Partenza


Traffic Envelope (Curva di arrivo)

Massima quantità di servizio che un flusso può inoltrare in un intervallo di tempo.

Traffic Envelope

Traffic Envelope


Curva di servizio

  • Considerato un flusso che sia inattivo al tempo s e “backlogged” nell’intervallo (s, t).
  • Curva di servizio: è il servizio minimo ricevuto dal flusso nell’intervallo (s, t).

Big Picture

Big Picture

Big Picture


Delay e Buffer Bounds

Delay e Buffer Bounds

Delay e Buffer Bounds


Meccanismi: Traffic Shaping/Policing

  • Token buket: limita l’input per Burst Size (b) e Average Rate (r) specificati
    • Traffico trasmesso su tutto l’intervallo T <= r*T +b
    • (LBAP) Linear Bounded Arrival Process
  • Il traffico in eccesso può essere accodato (marcato in blu) oppure semplicemente eliminato
Token bucket

Token bucket


Meccanismi: Queuing/Scheduling

  • Utilizzare pochi bit in testa per indicare qual è la coda (class) all’interno della quale deve entrare il pacchetto (indicato come CoS).
  • Grosse sorgenti di traffico vanno associate a code ad alta priorità che possono anche essere poco popolate.
    • Basso delay e bassa probabilità di perdita dei pacchetti.
  • Idee: priority, round-robin, classification, aggregation, …
Queuing/Scheduling

Queuing/Scheduling


Meccanismi: Buffer Management/Priority Drop

Idee: packet marking (marcare i pacchetti), queue thresholds (soglia della coda), differential dropping (eliminazione differenziata), buffer assignments (assegnazione del buffer).

Buffer Management/Priority Drop

Buffer Management/Priority Drop


Packet Scheduling

Decidere quando e quale pacchetto inviare sul link di output: solitamente tale funzione è implementata dall’interfaccia di output.

Packet Sheduling

Packet Sheduling


Focus: Scheduling Policies

  • Priority Queuing: le classi hanno differenti livelli di priorità; la classe può dipendere da specifiche informazioni nell’header (es.: IP sorgente o destinazione, numero di porto TCP, etc.).
  • Trasmettere un pacchetto dalla classe a priorità più elevata con un acoda non vuota.
  • Versioni Preemptive e non Preemptive (con e senza prelazione).
Preemptive

Preemptive

Non Preemptive

Non Preemptive


Ancora sulle Scheduling Policies

  • Round Robin: eseguire la scansione delle code relative alle classi per servirne una di ogni classe che sia non vuota.
Round Robin

Round Robin


Discussioni sul Round-Robin

  • Vantaggi: protezione tra flussi
    • Flussi “Misbehaving” non compromettono le prestazioni di flussi “Well-behaving” (Flusso Misbehaving: non implementa alcun tipo di controllo di congestione).
    • FIFO non presenta una tale proprietà.
  • Svantaggi:
    • Più complesso del FIFO.
    • Prevenuto nei confronti di pacchetti grandi – un flusso riceve un servizio proporzionato al numero di pacchetti.

Generalized Processor Sharing (GPS)

  • Assumere un modello fluido del traffico:
    • Visitare a turno ogni coda non vuota (RR).
    • Servire infinitesimi.
    • Il GPS è per l’imparzialità tra max e min.
  • Il GPS non è implementabile!
    • Non è possibile servire infinitesimi, ma solo pacchetti.
Generalized Processor Sharing

Generalized Processor Sharing


Generalized Processor Sharing

In figura:

  • wi – weight of flow I
  • Wi(t1, t2) – total service received by flow i during [t1, t2)
  • W(t1, t2) – total service allocated to all flows during [t1, t2)
  • B(t) – number of flows backlogged
Lavoro che conservi il GPS

Lavoro che conservi il GPS


Fair Rate Computation nel GPS

  • Associare un peso wi ad ogni flusso i.
  • In caso di congestione del link, calcolare f come in figura.
Calcolo di f

Calcolo di f


Bit-by-bit Round Robin

  • Flusso singolo: il clock scatta quando viene trasmesso un pacchetto. Per il pacchetto i:
    • Pi: lunghezza, Ai: tempo di arrivo, Si: tempo di inizio trasmissione, Fi: tempo di fine trasmissione.
    • Fi = Si+Pi = max (Fi-1, Ai) + Pi
  • Flussi multipli: il clock scatta quando viene trasmesso un bit di tutti i flussi attivi -> round number.
    • E’ possibile calcolare Fi per ogni pacchetto se il numero di flussi è noto in ogni istante.

Packet Approximation di Fluid System

  • Tecniche standard per l’approssimazione di fluidi GPS:
    • Selezionare il pacchetto che termina per primo nel GPS considerando che non ci sono arrivi futuri.
  • Importanti proprietà del GPS:
    • Ordine di completamento dei pacchetti nel sistema indipendente da arrivi futuri.
  • Implementazione basata su tempo virtuale:
    • Assegnare un tempo di completamento virtuale per ogni pacchetto in arrivo.
    • Pacchetti serviti in ordine crescente rispetto al tempo virtuale.

Fair Queuing (FQ)

  • Idea: servire pacchetti nell’ordine in cui terminerebbero la trasmissione nel sistema fluid flow.
  • Mappare il bit-by-bit schedule sul packet trasmission schedule.
  • Trasmettere il pacchetto col più basso Fi ad ogni istante.
  • Variante: Weighted Fair Queuing (WFQ).
Fair Queuing

Fair Queuing


Approssimare il GPS con il WFQ

  • Ordine di servizio del sistema Fluid GPS
  • Weighted Fair Queuing
    • Selezionare il primo pacchetto che termina nel GPS
Ordine di servizio

Ordine di servizio

Weighted Fair Queuing

Weighted Fair Queuing


FQ, Esempio

Schema dell’esempio

Schema dell'esempio


Vantaggi dell’FQ

  • L’FQ protegge i flussi well-behaved dai flussi misbehaved.
  • Esempio: 1 UDP (10 Mbps) e 31 TCP condividono un link di 10 Mbps.
Diagrammi dell’esempio

Diagrammi dell'esempio


System Virtual Time: V(t)

  • Misurare il servizio anzicchè il tempo.
  • V(t) – velocità a cui tutti i flussi attivi ricevono servizio
    • C – capacità del link
    • N(t) – numero di flussi attivi nel sistema fluido al tempo t
System Virtual Time

System Virtual Time


System Virtual Time

VGPS: tempo virtuale

System Virtual Time

System Virtual Time


Service Allocation nel GPS

Il servizio ricevuto dal flusso i nell’intervallo [t1, t2) mentre risulta backlogged, è mostrato in figura.

Servizio ricevuto dal flusso i

Servizio ricevuto dal flusso i


Virtual Time Implementation del Weighted Fair Queuing

  • ajk – tempo di arrivo del pacchetto k del flusso j
  • Sjk – tempo di inizio virtuale del pacchetto k del flusso j
  • Fjk – tempo di fine virtuale del pacchetto k del flusso j
  • Ljk – lunghezza del pacchetto k del flusso j
Virtual Time Implementation

Virtual Time Implementation


Virtual Time Implementation del Weighted Fair Queuing

  • Necessità di conservare virtual start per flusso e non per pacchetto.
  • Il tempo di sistema virtuale è utilizzato per resettare il tempo di start di un flusso quando un flusso diventa ancora backlogged dopo essere stato inattivo.

System Virtual Time nel GPS

System Virtual Time

System Virtual Time


Inizio virtuale e tempo di terminazione

Utilizzare quelli che sarebbero tempo di inizio Sik e tempo di fine Fik dei pacchetti in un sistema fluido.

Inizio virtuale e tempo di terminazione

Inizio virtuale e tempo di terminazione


Big Picture

  • L’FQ non elimina la congestione _ può solo gestire la congestione.
  • È necessario eseguire sia controllo di congestione sugli end-host che dotare i router di un supporto al controllo di congestione:
    • Controllo di congestione sugli end-host per adattare.
    • Controllo di congestione sui router per proteggere/isolare.
  • Non bisogna dimenticare la gestione del buffer: è necessario liberare spazio sul buffer in caso di congestione. Quali pacchetti eliminare con l’FQ?
    • Una possibilità: pacchetti dalle code più lunghe.

Tecniche ed Architetture per la QoS in Fast Interconnect

  • La QoS nelle reti LAN e nelle reti Fast Interconnect.
  • Flow Control (Controllo di Flusso).
  • Congestion Management (Gestione delle Congestioni)
  • Service Differentiation (Differenziazione dei Servizi).
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion