Routing e QoS Francesco Santini IMT-Lucca venerdì 9 novembre 2007.

Routing e QoS

Francesco SantiniIMT-Lucca

venerdì 9 novembre 2007

15 novembre 2007Corso di Laurea in Economia

Informatica

Contenuti

Applicazioni real-time e QoS IntServ e RSVP DiffServ MPLS


Informatica

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 scartare i pacchetti


Informatica

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 miglioramento algoritmi compressione


Informatica

Real-time applications

Applicazioni sensibili alla “tempesitivtà” dei dati (timeliness)

Deve essere supportato da tutta la rete, nativamente


Informatica

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 these issues for selected services.


Informatica

Delay: Four sources of delay 1. processing:

check bit errors determine output link

(routing table lookup) CPU, architecture etc

A

B

propagation

transmission

processing queueing

2. queueing time waiting at output

link for transmission depends on congestion

level of router and queue size


Informatica

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 (~2x108 m/sec) propagation delay = d/s

A

B

propagation

transmission

processing queueing


Informatica

Nodal delay

dproc = processing delay Usually small though depending on the processor,

a few microsecs? dqueue = queuing delay

depends on the congestion level dtrans = transmission delay

= L/R, significant for low-speed links dprop = propagation delay

a few microsecs to hundreds of msecs

proptransqueueprocnodal ddddd


Informatica

Traceroute


Informatica

Playback

Playback Buffer

T

Seq

uenc

e nu

mbe

r

ime

Packet g

eneration

Networkdelay

Buffer Playback

Packetarrival


Informatica

Esemio VoIP

Sequence N

umber

Time

Sendin

g Buffer Empty

Buffer is emptying Stop and buffer(Audio playback pause)

Enough packets in buffer, resume playback

Original delayAdditional delay

Playba

ck


Informatica

Classificazione applicazioni

Applications

Elastic Real Time

Intolerant Tolerant

AdaptiveNon-Adaptive

Delay AdaptiveRate Adaptive

Perdita pacchetti

wwwemail

Robot/Audio

Spostare playback point /Cambiare compressione

Robot medico


Informatica

Delay Adaptive

50

msec

Density

150 250

100%99%97%


Informatica 16

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


Informatica

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!


Informatica

Soluzioni esistenti

Architetture Integrated Services Differentiated Services

Protocolli Multi-Protocol Label Switching (MPLS)

Metodologie più generiche Traffic Engineering Constraint Based Routing


Informatica

Soluzioni esistenti(2)


Informatica

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 profile.


Informatica

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


Informatica

Contenuti



Informatica

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


Informatica

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)


Informatica

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


Informatica

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


Informatica

Esempio semplice


Informatica

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


Informatica

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


Informatica

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

flowspec + filterspec = flowdescriptor


Informatica

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 error


Informatica

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 resources


Informatica

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.


Informatica

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


Informatica

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


Informatica

RSVP Functional Diagram

Application

RSVPD

AdmissionsControl

PacketClassifier

PacketScheduler

PolicyControl

DATA

DATA

RSVPD

PolicyControl

AdmissionsControl

PacketClassifier

PacketScheduler

DATA

RoutingProcess

Host Router


Informatica

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. Recovers from failures Cleans up state after receivers drop out


Informatica

RSVP Reservation (1)

R4

R5

R3R2

R1

Host A24.1.70.210

Host B128.32.32.69PATH

PATH

PATH

2

2. The Host A RSVP daemon generates a PATH message that is sent to the next hop RSVP router, R1, in the direction of the session address, 128.32.32.69.

PATH3

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


Informatica

RSVP Reservation (2)

R4

R5

R3R2

R1

Host A24.1.70.210

Host B128.32.32.69

PATHPATH

PATH

PATH

RESV

RESV

RESV

5

5. The Host B RSVP daemon generates a RESV message that is sent to the next hop RSVP router, R4, in the direction of the source address, 24.1.70.210.

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


Informatica

RSVP Multicast Reservation (1)

R5 R6

R3R2

R1

R4 R7

Sender

Receiver

PATH

PATH

PATH

PATH

PATH

PATH

PATH

PATHPATH


Informatica

RSVP Multicast Reservation (2)

R5 R6

R3R2

R1

R4 R7

Sender

Receiver


Informatica

Reservation Merging

Receiver#1

Receiver#2

Receiver#3

Reservations mergeas they travel up tree.

R6

R3

R1

R4 R7

(1) 50Kbs

(2) 50Kbs

(3) 50Kbs

(4) 100 Kbs

(5) 100 Kbs

(6) 100 Kbs

(7) 100 Kbs

(8) 60Kbs

(9) 60Kbs


Informatica

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

Buffers data until tokens become available

Data


Informatica

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 mandare burst di 40 byte Nel tempo t, la quantità di traffico e limitata a ß + ρt

Data

= bucket size in tokens= rate tokens are added to bucket

Data Queue


Informatica

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


Informatica

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


Informatica

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

Route pinning Always use the route where reservation is in

place


Informatica

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


Informatica

Contenuti



Informatica

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


Informatica

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

RFC 3246—An Expedited Forwarding PHB


Informatica

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


Informatica

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

done under control of TBA signaling protocol


Informatica

Traffic Conditioner Block (TCB)

Classification: selects a packet in a traffic stream based on the content of some portion of the packet header


Informatica


Metering: checks whether the traffic falls within the negotiated profile.


Informatica


Marking: marks packet to a particular DS behavior aggregate


Informatica


Shaper/Droper: delays if necessary and then forwards or discards the packets .


Informatica

DS field

Former ToS Byte = new DS field

0 1 2 3 4 5 6 7Precedence

CurrentlyUnused

Differentiated Services Codepoint (DSCP)

versionheaderlength

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 15 23 248 317 16

0MF

DF

ToS


Informatica

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.


Informatica

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)


Informatica

PHB types

Default PHB: Traditional best effort treatment. Must be implemented Used for unsupported DSCP

The DSCP (6 bit) pattern is: 000000


Informatica

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


Informatica

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.

Non-conformant traffic is remarked.


Informatica

AF table

Class

Dropprecedence

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)

High Drop

001110(AF13)

010110(AF23)

011110(AF33)

100110(AF43)

The DSCP (6 bit) pattern is: xyzab0

xyz is the class: 001-class1 ; 010-class2 ; 011-class3 ; 100-class4ab is the drop precedence: 01-low ; 10-medium ; 11-high


Informatica

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).


Informatica

Putting it all together


Informatica

Assured Forwarding (AF) PHB

Determining resource allocation per class of service must be done with knowledge about traffic demands for the various traffic classes.


Informatica

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


Informatica

IntServ e DiffServ: riassunto


Informatica

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


Informatica

IntServ e DiffServ insieme(2)


Informatica

Contenuti



Informatica

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 instradamento tipo “Circuito Virtuale” su base flusso.


Informatica

MPLS and ISO model

PPP

Physical (Optical - Electrical) 1

2

IP 3

4

Applications7to5

FrameRelay

ATM (*)

TCP UDP

PPP Ethernet ATM

MPLS


Informatica

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)


Informatica

MPLS Cloud

LSR

LER

LSR

LER

IP PacketIP Packet w/ Label

L3 RoutingL3 Routing

Label SwappingLabel Swapping

LER

LERLER

L3 RoutingL3 Routing

L3 Routing


Informatica

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) che devono avere lo stesso trattamento


Informatica

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”


Informatica

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 instrada il pacchetto nuovamente sulla base dell’indirizzo IP.


Informatica

Label Switched Path


Informatica

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.


Informatica

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 label diversa per la stessa FEC


Informatica

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 effettuata dall’ultimo o dal penultimo LSR


Informatica

Header

S= the current label is the last in the stack


Informatica

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 accorgersi di essere il penultimo del LSP.


Informatica

Multidominio


Informatica

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

Tunneling efficiente


Informatica

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)

R. Bolla, “Servizi Multimediali e Qualità del Servizio (QdS) su IP – MPLS”, appunti di Telematica 2, università di Genova.


Informatica

Contatti:[email protected]

Routing e QoS Francesco Santini IMT-Lucca venerdì 9 novembre 2007.

Documents

Transcript of Routing e QoS Francesco Santini IMT-Lucca venerdì 9 novembre 2007.