Routing e QoS
Francesco Santini IMT-Lucca
venerdì 9 novembre 2007
Contenuti
Applicazioni real-time e QoS
IntServ e RSVP
DiffServ
MPLS
Contenuti
Applicazioni real-time e QoS
IntServ e RSVP
DiffServ
MPLS
Best effort
Consegno i pacchetti al meglio che posso…
Conseguenze:
Tutti i dati vengono trattati alla stessa maniera
Non è possibile avere delle garanzie per un flusso
Difficile offrire servizi su tale schema
Non avendo garanzie ed essendo trattati alla
stesa maniera, in caso di congestione posso
Dati “real-time”
Audio, Voce, Video
Ma anche dati che devono essere
consegnati con una certa precisione:
Posizione e azioni nei giochi
Tele operazioni in medicina (robot)
Controllo industriale (robot)
Quotazioni azioni
Negli ultimi anni, aumento banda dei link e
Real-time applications
Applicazioni sensibili alla “tempesitivtà” dei dati (timeliness)
Deve essere supportato da tutta la rete,
nativamente
Why we need QoS?
Common issues in networks are:
Loss / packet drop
Drop above certain % will influence experience
On congestion different drop algorithms are used.
RED, RIO, WRED*, tail drop
Jitter (variation in delay)
Jitter buffer can handle some jitter (used i.e in VoIP).
Misordering (different routes) (delay)
Delay (queuing)
QoS is basically a set of techniques to handle
Delay: Four sources of delay
1. processing:
check bit errors
determine output link (routing table lookup)
CPU, architecture etc
A B
propagation transmission
2. queueing
time waiting at output link for transmission
depends on congestion level of router and queue size
Four sources of packet delay
3. Transmission delay:
R=link bandwidth (bps)
L=packet length (bits)
time to send bits into link = L/R
4. Propagation delay:
d = length of physical link
s = propagation speed in medium (~2x10
8m/sec)
propagation delay = d/s
A B
propagation transmission
Nodal delay
d
proc= processing delay
Usually small though depending on the processor, a few microsecs?
d
queue= queuing delay
depends on the congestion level
d
trans= transmission delay
= L/R, significant for low-speed links
d = propagation delay
prop trans
queue proc
nodal
d d d d
d
Traceroute
Playback
Playback Buffer
Sequence number
Packet generation Network
delay Buffer Playback Packet
arrival
Esemio VoIP
Classificazione applicazioni
Applications
Elastic Real Time
Intolerant Tolerant
Adaptive Non-Adaptive
Perdita pacchetti
Robot/
Audio
Spostare playback point / Cambiare compressione
Delay Adaptive
De n si ty
100%
99%
97%
Why Not TCP
Don’t want reliable transmission
TCP is purely byte oriented
TCP relies on saturating the net
Retransmitting end-to-end is not a solution
La soluzione
Obiettivo è avere un modello di servizi che:
Mi garantisca effettivamente le richieste
Mi risponda che non è possibile soddisfare tale richiesta al momento
Bisogno di più “classi di servizio” differenti
Mantenere best effort!
Soluzioni esistenti
Architetture
Integrated Services
Differentiated Services
Protocolli
Multi-Protocol Label Switching (MPLS)
Metodologie più generiche
Traffic Engineering
Constraint Based Routing
Soluzioni esistenti(2)
Alcune definizioni
Service Level Agreement (SLA): A service contract between a customer and a service provider that specifies the forwarding service a customer should receive. A
customer may be a user organization or another provider domain (upstream domain).
Traffic profile: A description of the properties of a traffic stream such as rate and burst size.
Scheduling: The process of deciding which packet to send first in a system of multiple queues
Shaping: The process of delaying packets within traffic
stream to cause it to conform to some defined traffic
Definizione di flusso
Flow: A stream of packets with the same source IP address, source port number, destination IP
address, destination port number and protocol ID (unicast or multicast).
• Omogeneo
• Eterogeneo
Contenuti
Applicazioni real-time e QoS
IntServ e RSVP
DiffServ
MPLS
Integrated Service (IntServ)
IntServ framework was developed within IETF to provide individualized QoS guarantees to
individual sessions
provides services on a per flow basis where a flow is a packet stream with common source address, destination address and port number
IntServ routers must maintain per flow state
information
Riferimenti
RFC 1633 - Integrated Services in the Internet Architecture: an Overview
RFC 2211 - Specification of the Controlled-Load Network Element Service
RFC 2212 - Specification of Guaranteed Quality of Service
RFC 2215 - General Characterization Parameters for Integrated Service Network Elements
RFC 2205 - Resource ReSerVation Protocol (RSVP)
IntServ
two key IntServ features:
Reserved Resources
the router must know the amount of its resources currently reserved for on-going sessions
standard resources: link capacity, router buffers
Call Setup
A flow requiring QoS guarantees must be able to
reserve sufficient resources at each router on path
to ensure QoS requirements are met
Role of RSVP
Rides on top of unicast/multicast routing protocols
Must be present at sender(s), receiver(s), and routers
Carries resource requests all the way through the network
At each hop consults admission control and sets
up reservation
Esempio semplice
RSVP Service Model
Make reservations for simplex data streams.
Receiver decides whether to make reservation
Control messages in IP datagrams (proto #46).
PATH/RESV messages sent periodically to refresh soft state on the router
Failed requests return error messages - receiver must try again
No end to end ack for success
Flow Specification
Session must first declare its QoS requirement and characterize the traffic it will send through the network
R-spec: defines the QoS being requested by receiver
T-spec: defines the traffic characteristics of sender
RSVP is the signaling protocol is needed to carry
the R-spec and T-spec to the routers
Filter Specification
The router needs to recognize the packets belonging to that flow
IP of the sender
IP destination
Port number generating the packets
Port number of the receiver
Protocol ID
Any field of the header
PATH Messages
PATH messages carry sender’s Traffic Specifications (TSpec)
Carries also the FilterSpec
Routers note the direction PATH messages arrived and set up reverse path to sender
Receivers send RESV messages that follow reverse path and setup reservations
If reservation cannot be made, user gets an
RESV Messages
RESV messages carry receiver’s QoS needs (R- spec)
Forwarded via reverse path of PATH
Queuing delay and bandwidth requirements
Source traffic characteristics (from PATH)
Filter specification
Which transmissions can use the reserved resources?
Reservation style.
Router performs admission control and reserves
Router Handling of RESV Messages
If new request rejected, send error message.
If admitted:
Install packet filter into forwarding dbase.
Pass flow parameters to scheduler.
Activate packet policing if needed.
Forward RESV message upstream.
Integrated Services - RSVP
Mechanisms
Flow specification
Tell the network what the flow wants
Admission control
Network decides if it can handle flow
Reservation
Enable admission control
Packet classification
Map packets to flows
Scheduling
Forwarding policy
Integrated Services - RSVP
Example
Flowspec
100 msec guaranteed to www.nsf.gov
Reservation
Spec travels down path for approval
Delay guarantee approved by all routers, so admitted
Classification
Packets marked as guaranteed
EXAMPLE policy
guaranteed packets sent first
RSVP Functional Diagram
Application
RSVPD
Admissions Control Packet
Classifier
Packet Scheduler
Policy Control
D A T A
DATA
RSVPD
Policy Control Admissions
Control Packet
Classifier
Packet
Scheduler DATA Routing
Process
Host Router
Soft State
Routers keep state about reservation
Periodic messages refresh state, with PATH and RESV messages
Non-refreshed state times out automatically
Alternative: Hard state
No periodic refresh messages.
State is guaranteed to be there.
State is kept till explicit removal.
Properties of soft state:
Adapts to changes in routes, sources, and receivers.
RSVP Reservation (1)
R4
R5
R3 R2
R1 Host A
24.1.70.210
Host B 128.32.32.69
PATH
PATH PATH
2
2. The Host A RSVP daemon generates a PATH message that is sent to the next hop
PATH
3
3. The PATH message follows the next hop path through R5 and R4 until it gets to Host B.
Each router on the path creates soft session state with the reservation parameters.
1. An application on Host A creates a session, 128.32.32.69/4078, by communicating with the RSVP daemon on Host A.
1
RSVP Reservation (2)
R4
R5
R3 R2
R1 Host A
24.1.70.210
Host B 128.32.32.69
PATH
PATH
PATH
PATH
RESV RESV
RESV
5
RESV
6
6. The RESV message continues to follow the next hop path through R5 and R1 until it gets to Host A. Each router on the path makes a resource reservation.
4. An application on Host B communicates with the local RSVP daemon and asks for a reservation in session 128.32.32.69/4078. The daemon checks for and finds existing session state.
4
RSVP Multicast Reservation (1)
R5 R6
R3 R2
R1
R4 R7
Sender
PATH PATH
PATH
PATH
PATH
PATH
PATH
RSVP Multicast Reservation (2)
R3 R2
R1 Sender
Reservation Merging
Reservations merge as they travel up tree.
R6
R3 R1
R4 R7
(2) 50Kbs
(3) 50Kbs
(5) 100 Kbs (6) 100 Kbs
(7) 100 Kbs
(9) 60Kbs
Token Bucket (TSpec)
Token Bucket Capacity, B
r tokens/sec
Each byte needs a token in order
to pass
Drops packets if token is not available Data
Token Bucket (2)
Beta mi consente di rappresentare i burst di traffico, limitandoli
Sigma di descrive il normale rate previsto dei pacchetti
I dati vengono trasmessi quando esistono sufficienti token per mandarli
Es: bucket = 40 token, 1 token = 1 byte implica che posso
Data
= bucket size in tokens
= rate tokens are added to bucket
Data Queue
In words
Tspec: describe flow’s traffic characterization
Average bandwidth + burstiness: token bucket filter
Token rate: r
Bucket depth: B
Must have a token to send a byte
Must have n tokens to send n bytes
Start with no tokens
Accumulate tokens at rate of r per second
Can accumulate no more than B tokens
Two Service Classes
RSVP supports three service classes
Guaranteed service
Specified maximum delay
Controlled load services
For delay tolerant, adaptive applications
Network shields this traffic from congestion
Best effort
RSVP Routing Problems
IntServ does not specify any route selection of its own
It relies on existing routing protocols to forward its control packets further
Routing is separated from admission control
If route changes, reservation must be made along new route
New reservation takes time to setup
New reservation might fail
Old route could still be working fine
Problemi IntServ
Complessità/Scalabilità = problema centrale per grandi reti backbone
End-to-end
Stato replicato su tutti i router, per ciascun flusso
Le informazioni devono essere rinfrescate periodicamente
Il processo di controllo ammissione avviene per ogni flusso
La richiesta di QoS avviene dinamicamente
Contenuti
Applicazioni real-time e QoS
IntServ e RSVP
DiffServ
MPLS
Differential Service (DiffServ)
In DiffServ, flows are aggregated into
classes that receive “treatment” by class.
More complex operations are pushed out to edge routers and simpler operations done by core routers.
motivated by:
scalability, flexibility, and better-than-best-effort service without RSVP signaling
Flexibility: Flow A better than flow B
Riferimenti
RFC 2474—Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers
RFC 2475—An Architecture for Differentiated Services
RFC 2597—Assured Forwarding PHB Group
RFC 3140—Per Hop Behavior Identification
Codes
DiffServ functional elements
Edge functions:
packet classification
packet marking
traffic conditioning
Core functions:
forwarding based on per-hop behavior (PHB)
associated with packet’s class, no more end-to-
end as in IntServ
DiffServ edge functions
packet classification
classifier selects packets based on values in packet header fields and steers packet to appropriate marking function
how classifier obtains the rules for
classification not yet addressed [RFC 2475 uses term behavior aggregate rather than class of traffic.]
administrator could load table of source addresses
Traffic Conditioner Block (TCB)
Classification: selects a packet in a traffic
Traffic Conditioner Block (TCB)
Traffic Conditioner Block (TCB)
Marking: marks packet to a particular DS
Traffic Conditioner Block (TCB)
DS field
Former ToS Byte = new DS field
0 1 2 3 4 5 6 7
Precedence
version header
length total length (in bytes)
Identification Fragment offset
source IP address destination IP address
options (0 to 40 bytes) (Not used) 4 bytes
time-to-live (TTL) protocol header checksum
bit # 0 7 8 15 16 23 24 31
0 M
F D F ToS
DiffServ core routers
Routers define packet classes and
separate incoming packets into classes.
Treatment is done per class.
Per-hop behavior (PHB) defines
differences in performance among classes.
externally observable performance criteria
that do not specify internal implementation
mechanisms at router.
Router interni
No reservation ma provisioning
La qualità del servizio dipende da
provisioning e da come sono gestire le risorse nella rete
Scalabilità deriva da aggregazione di più
flussi in un numero limitato di classi (DSCP)
PHB types
Default PHB:
Traditional best effort treatment.
Must be implemented
Used for unsupported DSCP
The DSCP (6 bit) pattern is: 000000
PHB types
Expedited Forwarding PHB
Providing low loss, low latency, low jitter,
assured bandwidth, end-to-end service through DS domains
Implies isolation: guarantee for the EF traffic should not be influenced by the other traffic classes
Non-conformant traffic is dropped or shaped.
Possible service: providing a virtual wire
The DSCP (6 bit) pattern is: 101110
PHB types
Assured Forwarding (AF):
A method by which Behavior Aggregates can be given different forwarding assurances.
The intent is that it will be used to implement services that differ relative to each other (e.g., gold, silver,…).
AF defines 4 classes with some bandwidth and buffers allocated to them.
Within each class, there are three drop priorities, which affect which packets will get dropped first if there is
congestion.
AF table
Class Drop
precedence
Class 1 Class 2 Class 3 Class 4
Low Drop
001010 (AF11)
010010 (AF21)
011010 (AF31)
100010 (AF41) Medium
Drop 001100
(AF12) 010100
(AF22) 011100
(AF32) 100100 (AF42)
The DSCP (6 bit) pattern is: xyzab0
xyz is the class: 001-class1 ; 010-class2 ; 011-class3 ; 100-class4
ab is the drop precedence: 01-low ; 10-medium ; 11-high
Service
A service describes the overall treatment of a customer’s traffic within a DS domain.
Customers see services, not PHBs.
To support a service, many components must work together:
Mapping of service to PHBs, traffic conditioning, network provisioning, PHB-based forwarding.
Services in the DiffServ architecture is defined in
the form of Service Level Agreement (SLA).
Putting it all together
Assured Forwarding (AF) PHB
Determining resource allocation per class of service must be done with knowledge about traffic demands for the various traffic
classes.
Conclusioni
Una via di mezzo tra best effort e IntServ
Si basa su provisioning, ma è difficile da effettuare. Più facile con reservation
Più flussi in una sola classe. Meno possibilità
rispetto a IntServ
IntServ e DiffServ: riassunto
IntServ e DiffServ insieme
Approcci complementari:
IntServ: forti garanzie ma limiti scaling
DiffServ: garanzie deboli, ma buon scaling
La soluzione è unirli!
IntServ sui router
DiffServ su tutti gli altri router backbone
Mapping tra classi di servizio IntServ a livello di
servizio DiffServ
IntServ e DiffServ insieme(2)
Contenuti
Applicazioni real-time e QoS
IntServ e RSVP
DiffServ
MPLS
Multi Protocol Label Switching
Uso di un’etichetta di lunghezza fissa per instradare
MPLS è un forwarding scheme
Evoluto da Cisco Tag Switching
Tra Layer 2 (L2, link layer) a Layer 3 (L3, network layer):
“2.5 level”
RFC 3031
Si chiama “multi-protocol” perché, in linea di principio, è in grado di operare con qualunque protocollo di livello 3
(rete) anche se lo si applica tipicamente ad IP.
Permette ai nodi che lo utilizzano di realizzare una
communtazione su base “etichetta” e anche un
MPLS and ISO model
PPP
Physical (Optical - Electrical) 1 2
IP 3
4 Applications
7 to
5
Frame
Relay ATM (*)
TCP UDP
PPP Ethernet ATM
MPLS
Termonologia
I nodi (router) che operano usando MPLS vengono chiamati Label Switching Router (LSR)
La parte di rete che questi nodi compongono viene chiamata Dominio MPLS (MPLS Domain)
I nodi al confine del Dominio, ossia i nodi che ricevono/trasmettono traffico all’esterno del
Dominio vengono chiamati Edge Label Switching
Router (ELSR)
MPLS Cloud
LSR
LER
LSR LER
L3 Routing L3 Routing
Label Swapping Label Swapping
LER
LER
LER L3 Routing L3 Routing
L3 Routing
Funzionamento
L’idea di base è che una certa tipologia di
pacchetti che raggiungono un ELSR debbano venir trasportati all’interno del Dominio tramite MPLS ad un altro ELSR.
In corrispondenza di un indirizzo di destinazione e di un tipo di trattamento richiesto (QoS) viene
definita una specifica Forwarding Equivalent Class (FEC).
Una FEC individua quindi un aggregato di pacchetti diretto ad una stessa destinazione
(intesa o come destinazione finale ocome ELSR)
Funzionamento (2)
Quanto un ELSR riceve un pacchetto IP :
compie una operazione di “Classificazione”, ossia in base a quanto contenuto nell’intestazione identifica l’eventuale FEC di appartenenza;
inserisce fra l’intestazione di livello 2 e il pacchetto IP una Label.
Tale Label:
Identifica la FEC a cui il pacchetto appartiene
Ha una lunghezza costante e breve
Ha un significato “locale alla linea”
Funzionamento (3)
Dall’ELSR di ingresso a quello di uscita tutte le operazioni di forwarding verranno effettuate
utilizzando solo la Label e quindi l’intestazione del pacchetto IP non verrà più letta fino all’ELSR di destinazione.
Gli LSR attraversati leggono la Label, trovano
tramite essa in una tabella il FEC corrispondente ossia l’informazione sulla porta di uscita, la Label successiva ed il tipo di trattamento richiesto.
L’ELSR di uscita (quindi l’ultimo nodo attraversato
all’interno del Dominio MPLS) elimina la Label ed
Label Switched Path
Passi fondamentali
MPLS prevede in sostanza 4 passi fondamentali:
La definizione di una FEC
L’individuazione del percorso LSP.
La creazione (associazione al FEC) e distribuzione delle Label lungo il LSP (si osservi che questa operazione e la precedente si svolgono in modo parallelo e coordinato).
Il meccanismo di forwarding che comprende
l’inserimento della Label, la commutazione sulla base di
essa e la sua rimozione.
Etichette
Per distribuire
Label Distribution Protocol (LDP):
RSVP-TE (Traffic Engineering)
Minimizzare il loro numero (tabelle piccole) anche ridurre il traffico di segnalazione
Aggregation: FEC diversi con la stessa label, per esempio se destinazione è uguale
Label Merging: pacchetti da diversi LSR hanno
Operazioni
Le operazioni che vengono effettuate sul pacchetto in transito nei LSR in relazione alle Label sono sostanzialmente tre:
Pushing, ossia l’inserimento della Label, che viene realizzata dall’ELSR di ingresso.
Swapping, ossia conversione dell’etichetta, realizzata contestualmente all’operazione di commutazione
Popping, ossia l’eliminazione di etichetta
Header
Label popping
Conviene fare il popping al penultimo LSR (Penultimate Popping), perché:
All’utimo nodo il forwarding viene eseguito sulla base del pacchetto IP e quindi l’osservazione della Label è inutile
Lasciarlo significa costringere il nodo a cercae nella
tabella MPLS per scoprire che deve eliminare la Label e quindi usare IP
Non sempre si può fare il Penultimate Popping in
quanto non è detto che l’LSR sia in grado di
Multidominio
Vantaggi
La procedura di forwarding richiede solo l’ispezione di una etichetta (Label) di
dimensioni ridotte e l’esplorazione di una tabella relativamente semplice
Instradamento effettuato anche con altre informazioni, non solo header come IP
Possibile scegliere percorsi per traffic
engineering e QoS
Riferimenti
G. Chaffee, “RSVP: The ReSerVation
Protocol”, Multimedia Research Berkeley Center, (ppt online)
E. Rot and I. Poleg “DiffServ: QoS in
internet”, Presentation for ATM Networks course (EE-046992) (ppt online)
