Teleinformática e Redes 1 - Convergência de Redes - Políticas de Escalonamento e Controle de Tráfego

Prévia do material em texto

Convergência de 
Redes
Políticas de Escalonamento
 e Controle de Tráfego
 Profa. Priscila Solís Barreto
O Que Estudamos Ontem
 Gerenciamento de Filas e RED
 Para que serve o QoS?
 Príncipios de QoS
Controle de Fluxo
 Para que serve ? 
 Se a camada destino (n+1) não recupera a 
informação suficientemente rápido, as camadas 
de destino n podem ter overflow 
 O controle de fluxo é um conjunto de 
mecanismos de regulação que controlam a 
transferência de acordo a disponibilidade de 
buffers no destino 
 Exemplos: TCP e HDLC
Temporização
 Nas aplicações multimídia:
 As aplicações que envolvem voz e vídeo geram 
unidades de informação que são relacionadas no 
tempo
 A rede introduz atraso e jitter
 A aplicação de destino deve reconstruir a relação 
temporal entre as unidades de voz e vídeo 
 Como se faz a reconstrução ? 
 Protocolos de recuperação de temporização usam 
timestamps e numeração de sequencia para regular 
as diferenças 
 Exemplos: RTP 
Quando utilizar cada enfoque ?
1 2 3 4 5
Data Data Data
ACK/NAK
Data
1 2 3 4 5
Data Data Data Data
ACK/
NAK
ACK/
NAK
ACK/
NAK
ACK/
NAK
Fim a Fim (Ex. TCP)
Salto a Salto (Ex. HDLC)
Controle de Erro na Camada 
de Transporte
Física
Enlace
Física
Enlace
Sistema 
Final α
Rede Rede
Física
Enlace
Rede
Física
Enlace
Rede
Transporte Transporte
Mensagens Mensagens
Segmentos
Sistema 
Final
Β
Rede
• Protocolo de Transporte (TCP) envia segmentos atraves da rede e executa 
checagem fim a fim e retransmissão
• Se assume que a rede não é confiável
7
O Controle de 
Congestionamento na Internet
 Solução end-system-only 
(TCP)
 Dinamicamente se estima 
o estado da rede
 Perda de pacotes indica 
congestionamento
 Se reduz a taxa de 
transmissão na presença 
de congestionamento
 Roteadores ? Função 
mínima 
TCP
TCP
TCP
Controle 
Escala de tempo
Meses
Capacidade de 
planejamento
RTT (ms)
Feedback 
Control
8
Mais idéias sobre 
gerenciamento de tráfego 
 Melhorar o TCP
 Permanecer com uma arquitetura end-point only 
 Melhorar roteadores para ajudar o TCP 
 Random Early Discard 
 Melhorar roteadores para controlar o tráfego 
 Limitação da taxa
 Enfileiramento justo 
 Prover QoS ao limitar o congestionamento 
9
Mecanismos do Roteador
 Gerenciamento do Buffer : quando e que pacote 
descartar ? 
 Escalonamento: que pacote transmitir logo 
enseguida?
1
2
Scheduler
flow 1
flow 2
flow n
Classifier
Buffer 
gerenciamento
10
Mecanismos de 
Escalonamento e Policiamento 
 escalonamento: escolher o próximo pacote para 
transmissão no enlace pode ser feito seguindo um número 
de políticas;
 FIFO: em ordem de chegada na fila; pacotes que chegam 
no buffer chéio são descartados, ou uma política de 
descarte é usada para determinar qual pacote descartar 
entre os que chegam e aqueles já na fila
11
Políticas de Escalonamento
 Enfileiramento prioritário: classes tem prioridades 
diferentes; a classe pode depender de marcação 
explícita ou informação do cabeçalho ( eg IP fonte ou 
destino), números de porta TCP, etc.
 transmitir o pacote desde a prioridade mais alta com 
uma fila não vazía
 Versões Preemptive e non-preemptive
12
 Round Robin: escanear as filas de classe servindo uma de 
cada classe desde que a fila não esteja vazía
Políticas de Escalonamento
13
 Enfileiramento Weighted Fair : é um Round 
Robin generalizado no qual uma tentativa é 
feita para fornecer uma classe com uma 
quantidade diferenciada de serviço em um 
período de tempo
Políticas de Escalonamento
14
Bottleneck
(10 Mbps)
Exemplo
• 1 UDP (10 Mbps) e 31 TCPs compartilhando 
uma linha de 10 Mbps
UDP (#1) - 10 Mbps
TCP (#2)
TCP (#32)
...
UDP (#1)
TCP (#2)
TCP (#32)
...
15
Throughput de UDP e Fluxos TCP 
com FIFO
0
1
2
3
4
5
6
7
8
9
10
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
Flow Number
Throughput (Mbps)
FIFO
16
Exemplo: Throughput de Fluxos TCP e 
UDP com roteador usando 
enfileiramento Fair Queuing no roteador
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
Flow Number
Throughput (Mbps)
FQ
24.17
Lembrando da Fila FIFO
24.18
Fila com Prioridade
24.19
WFQ 
Reforço de QoS – Traffic Shaping
• Em uma rede de pacotes que implementa 
compartilhamento de recursos, controle de admissão e 
esquemas de escalonamento, ainda é necessário 
trabalhar o tráfego
• Porque? Os usuários poden inadvertidamente 
exceder as taxas especificadas no momento da 
conexão 
• O QoS é normalmente negociado para taxas médias, 
mas ocorrem explosões durante a transmissão e a 
alocação de recursos pode ficar desbalanceada 
• O traffic shaping é necessário na entrada da rede ou 
dentro da rede.
Reforço de QoS – Traffic 
Shaping
 Nas redes de pacotes o controle de admissão e 
a reserva não são suficiêntes para garantir o 
QoS
 Traffic shaping 
 Decide como os pacotes serão enviados na rede  
regula o tráfego
 Decide qando aceitar um fluxo de dados
 Politicas de fluxos
O Objetivo da Formatação de 
Tráfego
 Traffic shape (Formato do tráfego) 
 A maneira como um fluxo descreve seu tráfego na 
rede
 Baseado no formato do tráfego, os gerentes da 
rede podem determinar se o fluxo deve ser 
admitido na rede
 Com um formato de tráfego dado, os gerentes 
da rede podem periodicamente monitorar o 
tráfego do fluxo
Exemplo
 Queremos transmitir dados de 100 Mbps, 
 Formato do tráfego A: temos um pacote de 
tamanho= 100 Mbit e o enviamos uma vez por 
segundo ou 
 Formato do tráfego B: tomamos 1 pacote de 
tamanho= 1 Kbit e o enviamos a cada every 10 
microsegundos?
1 Mbit 1 Mbit
Kth second K+1 th second
A
B
Parâmetros de Formato de Tráfego de 
um Fluxo (Network QoS)
 Traffic Envelope (envoltória do tráfego) 
 Taxa máxima (Peak rate)
 Taxa média (Average rate)
 Tamanho da explosão (Burst length)
 Duração da explosão (Burst duration)
 Service Envelope (envoltória do serviço)
 Atraso máximo tolerável
 Atraso e jitter médio
 Outros ?
Descritores do Tráfego
Classificação das Fontes
 Classificação das Fontes:
 Dados – bursty, levemente periódico, fortemente regular
 Audio – continuo, fortemente periódico, fortemente regular
 Video – continuo, bursty em função da compressão, 
fortemente periódico, levemente regular 
 Classificação das fontes em duas classes:
 Constant Bit Rate (CBR) – audio 
 Variable Bit rate (VBR) – video, data
CS 414 - Spring 2012
24.27
Parâmetros das Fontes
Alocação da Banda
 Tráfego CBR traffic (formato definido pela taxa 
máxima)
 Uma fonte CBR precisa alocação de banda para a taxa 
máxima para uma transmissão sem congestionamento
 Tráfego VBR (formato definido pela taxa média 
e taxa máxima )
 a taxa média pode ser uma pequena fração da taxa 
máxima
 ocorre subutilização de recursos ao fazer uma alocação 
pessimista
 Perdas ocorrem ao fazer uma alocação otimista
Traffic Shaping
Algoritmo Leaky Bucket 
(a) Leaky bucket com água. (b) leaky bucket com pacotes.
Isochronous Traffic Shaping
(Simple Leaky Bucket Traffic Shaper) 
CS 414 - Spring 2012
 Desenvolvido por Jon Turner, 1986 (Washington 
University, St. Louis) 
Traffic Shaping
Algoritmo Leaky Bucket 
Exemplo 
 Considerar um fluxo de audio e tamanho do 
bucket β = 16 Kbytes
 Tamanho do pacote = 1 Kbytes  podem-se acumular 
burst até de 16 pacotes no bucket
 Taxa de regulação ρ = 8 pacotes por segundoou 8KBps ou 
64Kbps 
 Consider um fluxo de vídeo, tamanho do bucket de 
β = 400 Kbytes
 Tamanho do pacote = 40 Kbytes (explosões de 10 pacotes)
 Taxa de regulação ρ = 5 pacotes por segundo, 200 KBps, 
1600Kbps
24.33
Implementação do Leaky Bucket 
Algoritmo Token Bucket
(a) antes. (b) depois.
5-34
O Token bucket permite alguma explosividade (em função do 
número de tokens que o bucket pode manter)
35
Mecanismos de Policiamento
 O token bucket fornece meios para limitar a 
entrada em valores específicos de tamanho 
de burst e taxa média. 
Implementação do Token Bucket
37
Token Bucket
 O bucket pode manter b tokens; um token é gerado a uma taxa 
 r token/sec a menos que o bucket esteja chéio de tokens.
 Em um intervalo de tamanho t, o número de pacotes que são 
admitidos é menor ou igual a (r t + b).
 Um token bucket e uma WFQ podem ser combinados para 
fornecer um límite máximo ao atraso.
Leaky e Token 
Bucket : Exemplo
(a) Entrada ao bucket. 
(b) Saída do leaky bucket. 
Saída do token bucket com 
capacidades de: 
(c) 250 KB, 
(d) 500 KB, 
(e) 750 KB, 
(f) Saída de um token 
bucket de 500KB 
alimentando um leaky 
bucket de 10-MB/sec
Reserva de Recursos
Observar que o Traffic shaping é mais efetivo quanto 
todos os pacotes seguem a mesma rota
Pode-se também, da mesma forma que nos circuitos 
virtuais, alocar uma rota específica para um fluxo e 
reservar recursos ao longo desta rota
Três tipos de recursos podem ser reservados :
● Taxa (que depende da largura de banda)
● Espaço de buffer 
● Ciclos de CPU
No Controle de Admissão
Exemplo de uma especificação de fluxos
Na reserva de recursos, como podem ser especificadas as 
necessidades ? 
Os roteadores devem converter um conjunto de especificações 
para requerimentos de recursos e decidir se aceitam ou não 
esse fluxo. 
Integrated Services (IntServ)
Um enfoque de QoS baseado no fluxo que usa reserva de 
recursos
Conjunto de protocolos objetivando streaming multimedia e 
padronizados pelo IETF.
Permite transmissões unicast e multicast 
Resource reSerVation Protocol (RSVP) é usado para 
reservar recursos em roteadores intermediarios entre emissor 
e receptor
O RSVP permite:
● Vários emissores transmitirem a grupos de receptores
●Usuários individuais podem trocar canais
●Otimiza utilização de largura de banda simultaneamente ao 
eliminar congestionamento
RSVP-The ReSerVation Protocol
(a) A rede (b) O spanning tree multicast para o host 1. 
(c) O spanning tree multicast para o host 2.
Reserva de largura de banda é feita no caminho inverso al 
longo do spanning tree.
RSVP-The ReSerVation Protocol (2)
(a) Host 3 solicita um canal ao host 1. (b) Host 3 solicita um 
segundo canal ao host. (c) Host 5 solicita um canal ao host 1.
Observações
O IntServ é muito popular mas tem alguns problemas:
- Na fase de estabelecimento, o atraso pode ser grande para 
um fluxo entrante
- Os roteadores precisam manter um estado por fluxo que não 
é muito escalável
- A troca de informações routeador-a-routeador é complexa
Um enfoque mais simples é o Differentiated Services 
(DiffServ).
O DiffServ é baseado em classes de tráfego
Differentiated Services (DiffServ)
• Introduz classes de serviço com regras 
de encaminhamento.
• São vendidos serviços
• Cada pacote tem um campo de Type 
of Service. 
• Dependendo da classe de serviço, o 
tratamento pode ser ou não preferencial
Expedited Forwarding
Se 10% do tráfego e expedited e 90% regular  20% da largura 
de banda é dedicada ao expedited.
Assured Forwarding
Uma implementação possível de fluxo de dados 
para assured forwarding.
Existem 4 classes de prioridade e 3 probabilidades 
de descarte: baixa, média e alta 
Label Switching e MPLS
Transmissão de um segmento TCP usando IP, MPLS, 
E PPP (router-to-router).
No MPLS (MulitProtocol Label Switching) a idéia e usar etiquetas
Para cada pacote e rotear usando estas etiquetas
49
Motivos para usar MPLS
 Aproveitar e otimizar o hardware já 
existente
 Encaminhamento de alta velocidade 
 IP Traffic Engineering
 Roteamento baseado em restrições
 Virtual Private Networks (VPN)
 Mecanismos de tunelamento
 Voice/Video sobre IP
 Variação do atraso + Restrições de QoS
MPLS : Terminologia
►LDP: LDP: Label Distribution ProtocolLabel Distribution Protocol 
►LSP: LSP: Label Switched PathLabel Switched Path
►FEC: FEC: Forwarding Equivalence ClassForwarding Equivalence Class
►LSR: LSR: Label Switching RouterLabel Switching Router
►LER: LER: Label Edge Router (Useful term not in Label Edge Router (Useful term not in 
standards)standards)
Componentes da rede MPLS : 
roteadores
Label Switching Routers (LSRs)
(Switch ATM ou Roteador)
Label Edge Routers
(LER)
Visão da rede MPLS
POP4
POP
POP
POP
POP2
POP1
WAN area
Operação do MPLS
 São 5 passo básicos:
 1. Criação de labels e distribuição
 2. Criação de tabelas em cada roteador
 3. Criação de caminhos (LSP)
 4. Inserção de etiquetas e pesquisa
 5. Encaminhamento de pacotes
1. Criação de etiquetas e 
distribuição
 Os roteadores devem associar uma etiqueta a uma FEC, e 
construir suas tabelas
 Usando LDP os roteadores downstream iniciam a 
distribuição de labels e sua associação com a tabela FEC
 Caraterísticas do tráfego são intercambiadas usando o 
LDP.
 LDS usa o TCP como protocolo de sinalização
Upstream LSR Downstream LSR
Pedido de Label
Mapeamento de Label
2. Criação de tabelas
 Ao receber os mapeamentos das etiquetas, 
são inseridos no LFIB
 As entradas são atualizadas ao acontecer re-
negociações dos mapeamentos
3. Criação do LSP
 Um LSP (Label Switched Path) é um 
caminho específico entre dois roteadores 
que utilizam técnicas de comutação de 
etiquetas para o encaminhamento de 
pacotes
 É o caminho entre dois roteadores onde os 
pacotes que fazem parte de uma certa FEC 
devem trafegar.
 São unidirecionais.
Intf
In
Label
In
Dest Intf
Out
3 0.40 47.1 1
Intf
In
Label
In
Dest Intf
Out
Label
Out
3 0.50 47.1 1 0.40
Distribuição de Labels
47.1
47.247.3
1
2
3
1
2
1
2
3
3Intf
In
Dest Intf
Out
Label
Out
3 47.1 1 0.50 Mapeado: 0.40
Pedido: 47.1
Map
eado
: 0.5
0
Pedid
o: 47
.1
Label Switched Path (LSP)
Intf
In
Label
In
Dest Intf
Out
3 0.40 47.1 1
Intf
In
Label
In
Dest Intf
Out
Label
Out
3 0.50 47.1 1 0.40
47.1
47.247.3
1
2
3
1
2
1
2
3
3Intf
In
Dest Intf
Out
Label
Out
3 47.1 1 0.50
IP 47.1.1.1
IP 47.1.1.1
LER de 
entrada
LSR de 
saída
Caminho mais curto
Label Switched Path
Conclusões
 O trabalho semanal é elaborar as conclusões 
dos assuntos discutidos em aula 
complementado com a leitura de um artigo 
indicado que devera ser apresentado em 10 
minutos por cada aluno na próxima aula.
 Relacionar para as aplicações escolhidas no 
paper um ambiente de utilização e justificar 
que elementos poderiam ser implementados 
nesse ambiente para oferecer garantias de 
QoS.