Encaminhamento com QoS
Sistemas Telemáticos
LESI
Grupo de Comunicações por
Computador
Materiais utilizados
• Tema ainda objecto de I&D (2
doutoramentos nessa área no DI)
• Artigo “Survey of QoS” de Pragyansmita
Paul and S. V. Raghavan
• Adaptação e simplificação de
apresentação dos mesmos autores
Sumário
Vantagens da Qualidade de Serviço (QoS)
QoS Fim-a-Fim
Encaminhamento com QoS
Questões em aberto no Encaminhamento
com QoS
Algoritmos propostos (classificados com
métricas)
Um-para-um
Simples
Dual
Múltiplo
Grupo
Simples
Dual
Múltiplo
QoS
 A um conjunto de métricas e restrições que
são usadas para especificar os requisitos das
aplicações e que devem ser satisfeitas pela
rede de suporte durante a transmissão de
dados.
 As métricas de QoS são:
 Largura de Banda
 Atrasos
 Variação nos atrasos (Jitter)
 Perda de Pacotes (Fiabilidade)
 Número de saltos, Qualidade Áudio/Vídeo, etc.
QoS Fim-a-Fim
 É necessária para:
 Disponibilizar garantias sólidas necesárias pelas
actuais aplicações com temporização crítica e
com necessidades intensivas de largura de
banda.
 Prevenir a deterioração do desempenho da rede
devido a aplicações mal comportadas.
 Para optimizar o desempenho todas as
camadas da pilha de protocolos devem
suportar o QoS a disponibilizar à aplicação
de rede a ser executada.
QoS na Pilha de Protocolos
Aplicação
◄
???
Transporte
◄
???
Rede
◄
???
Ligação Lógica ◄
???
Meio Físico
QoS na Pilha de Protocolos
Aplicação
◄ Diferentes Classificações e
Escalonamento dos pedidos
Transporte
◄ Aceitação/rejeição dos pedidos
de conexão
Rede
◄ Selecção de Percursos de forma
a satisfazer os requisitos das
aplicações
Ligação Lógica ◄ Comunicação de Dados de
Meio Físico
forma satisfazer os requisitos
das camadas superiores
Sequência de acções para
disponibilizar a QoS fim-a-fim
Pedido de QoS
por um host
A
Selecção do Percurso e
transferência dos dados
(Encaminhamento com QoS)
Tradução e negociação
do QoS
Fim da
Transferência dos
dados?
Não
Não
Pedido
aceite?
Sim
A
Sim
Fim da transferência
dos dados
Encaminhamento com QoS
B
Controlo de
Admissão
Busca na tabela de
encaminhamento
Actualização da informação
de estado
Gestão de Recursos
Reserva de Recursos
(opcional)
C
C
Armazenamento e
Escalonamento de pacotes
B
Fim da
Não
Transferência dos
dados?
Sim
Fim da
Transferência de Dados
Negociação de QoS e Controlo
de Admissão
 A negociação começa quando o sistema final
envia o seu pedido de QoS
 O módulo de controlo de admissão verifica se o
pedido deve ser aceite ou rejeitado
 Factores de decisão: LB residual, Nº Tx em curso
 Se a aceitação levar à degradação de desempenho ,
o pedido é rejeitado
 Alternativa: reencaminhamento das aplicações
existentes
 Renegociação do QoS
Negociação de QoS e Controlo
de Admissão(2)
• O sistema final (end-host) pode fazer o
controlo de admissão
– Faz o probe do nível de congestão
– Admite o fluxo se o nível for baixo
• Experiências:
– Menor degradação de desempenho se o
controlo de admissão pelos sistemas finais
em alternativa a ser feito pelos
encaminhadores
Reserva de Recursos
• Uma vez aceite o pedido
– é escolhido o percurso para transmissão de
dados com base em uma ou mais métricas
• Necessária para satisfazer restrições de
QoS da aplicação
• Duas alternativas
– Fazer parte do estabelecimento do percurso
– Ser um processo separado
Armazenamento e Escalonamento dos
Pacotes
• Pacote recém-chegado ao encaminhador
– É transferido para a interface de saída e
armazenado num buffer
– É descartado
• Objectivo:Minimizar o descarte de pacotes
• Algoritmos de gestão de filas
• Algoritmos de escalonamento de pacotes
Algoritmos de Escalonamento
• Fair Queueing (FQ)
– 1 fila por fluxo (informação de estado por fluxo)
• Stochastic Fair Queueing (SFQ)
– Menor nº de filas que FQ, uso de função de hash
• Core Stateless Fair Queueing (CSFQ)
– 2 classes de encaminhadores:
• De fonteira
– mantêm informação de estado por fluxo
– Estimam débito de chegada por fluxo (passam aos
interiores)
• Interiores
» Em situação de congestão, descartam pacotes
aleatóriamente com base nessa estimação
Algoritmos de Gestão de Filas
• RED (Random Early Detection) & RIO
• CHOKe (CHOose and Keep for responsive flows)
– Considerar o buffer como uma amostra estatística do
tráfego
– Em situação de congestão, na chegada de pacote
• Escolhe um pacote do buffer aleatoriamente
– Se for do mesmo fluxo, descarta os dois
– Senão: o do buffer fica intacto e o chegado é aceite em função
do nível de congestão
Lookup da Tabela de Encaminhamento
• Maior gargalo do processo de expedição dos
pacotes
– Mais crítica com tecnologias de alta velocidade
– Unificação simples (tries)
– Unificação mais longa (PATRICIA)
• Multi-Protocol Label Switching (MPLS)
– Etiqueta de comprimento fixo
– Cada pacote tem uma etiqueta
– Etiqueta usada para busca na tabela
Gestão de Recursos
• Necessária para gerir a dinâmica das
conexões estabelecidas
• Reserva estática de recursos
– GR necessária para verificar utilização eficiente
de recursos
• Reserva dinâmica??
• Quando não há reserva de recursos
– Assegurar uma partilha adequada entre as
conexões e que as exigências de cada fluxo é
limitado
– Quando cada serviço recipiente recebe o mínimo
de QoS, considera-se adequada
Fluxos BE num QoS Router
• Para além dos fluxos com QoS, as aplicações
BE devem ser geridas de forma apropriada.
• Exemplo de trabalho nesse sentido
– Restrição de LB para fluxos com QoS
• Usa informação imprecisa para o estado de fluxos
– MaxMin Fair Routing para fluxos BE
• Maximiza a LB para fluxos que recebem menor LB entre
todos
– Escalonamento hierárquico com WFQ para alocação
de LB
Selecção do Percurso – Métricas e
Restrições
Aditiva
Métrica
Multiplicativa
Côncava
w1
w2
w3
Percurso P
w = w1 + w2 + w3
w = w1 . w2 . w3
w = max{w1 , w2 , w3}
Selecção do Percurso – Métricas e
Restrições
Simples
Métricas
Dual
Múltiplas
•Simples: Custo, Largura de Banda, Atraso
•Dual: Custo e Atraso;LB e Atraso; LB e Custo
•Múltiplas: ...
Selecção do Percurso – Métricas e
Restrições
• Como transformar uma métrica multiplicativa em
aditiva?
– w1.w2.w3 => log(w1)+log(w2)+log(w3)
• Como transformar uma métrica dual (múltipla)
numa métrica simples?
– (w1,w2) => w´= w1+k w2
• Como transformar uma métrica com valor real
ou inteiro não limitado numa com valor inteiro
limitado?
– w < c => w’= w* x/c
Selecção de Percurso – ME vs. QoS
Percurso escolhido
min. salto/custo
Percurso
Escolhido ?
[3,7]
1
A
A
1
1
B
F
1
1
1
1
C
E
1
D
1
B
[1,2]
[1,4]
F
[3,1]
[1,4]
[1,1]
[4,1]
C
E
[2,2]
D
[1,2]
Percurso
Métrica
1
Métrica
2
F-B
3
7
F-A-B
5
5
Selecção de Percurso – ME vs. QoS
• Em contextos BE é mais fácil descobrir o PMC
• Em contextos com QoS
– É necessário considerar um conjunto de métricas
• cada aresta do grafo tem mais que uma métrica associada
– A escolha do PMC depende de
• Regra de composição de métricas
• Prioridade/Peso atribuídos a cada métrica
Selecção de Percurso no
Encaminhamento com QOS
Wang e Crowcroft provaram que
encontrar um percurso sujeito a duas
ou mais restrições independentes
(aditivas e/ou multiplicativas) é um
problema NP-Completo.
Selecção de Percurso no
encaminhamento com QoS –
Resultados interessantes
 Quando o número de métricas consideradas
é infinito, é suficiente calcular o percurso de
menor número de saltos, sem se ter que
considerar distribuição dos pesos das
métricas independentes. (resultado com interesse teórico)
 Podem existir classes de grafos nos quais o
encaminhamento com QoS não é NPCompleto. (Referência: P. Van Mieghem, F. A. Kuipers, “On
the Complexity of QoS Routing”, na Computer
Communications.).
Classificação de
Algoritmos/Protocolos
Multicast
Unicast
Simples
• Largura
Bandwidth
de
banda
• Delay
• Atraso
Dual
• Custo +Atraso
• Largura de
banda + atraso
• Qq 2 métricas
aditivas
Múltiplo
• Múltiplas
Simples
• Custo
Dual
• Atraso
• Custo +
Atraso
• Métrica não
aditiva
• Atraso +
Jitter
Múltiplo
• Múltipla
Encaminhamento unicast
Restrição de Largura de Banda
Filtragem da Topologia
N1
1
N5
3
Algoritmo de Guerin Orda
N1
-log (0.1)
0.1
4
N2
5
2
NN5
55
0.2
0.2
N2
0.1
-log (0.1)
3
N4
LB > 2
N3
N4
N3
Problema aditivo
Maximizar Probablidade
(LB Residual > 2)
Classificação de
Algoritmos/Protocolos
Multicast
Unicast
Simples
• LB
• Atraso
Dual
• Custo+Atraso
Múltiplo
• Múltiplas
Simples
• Custo
Dual
• LB + Atraso
• Atraso
• Custo +
Atraso
• Qualquer 2
métricas
aditivas
• Métrica não
aditiva
• Atraso +
Jitter
Múltiplo
• Múltipla
Encaminhamento Unicast com QoS
Restrições de Atraso e Largura de Banda
Algoritmo de Wang Crowcroft
N1
1
N5
3
 Elimina todas as ligações
com largura de banda
inferior à requerida.
4
N2
5
2
3
N4
LB > 2
N3
 A seguir, encontra o
percurso mais curto
relativamente ao atraso no
grafo modificado usando o
algoritmo de Djikstra.
Percurso mais curto com o
Algoritmo de Djikstra
Dado um grafo ponderado G=(V,E), e um par
de vértices vs e vd  V qual é o percurso mais
curto de vs para vd? Isto é qual é o percurso
com a mínima soma dos pesos das arestas?
2
7
3
3
1
8
10
5
6
5
1
7
6
7
3
3
4
2
5
2
1
8
10
5
6
5
1
4
2
7
5
6
Abordagem básica
B
1
2
1
A
C
6
7
3
5
E
8
D
F
H
5
G
6
ABEFH
15
ABEGH
14
ACEFH
16
ACEGH
15
ADEFH
26
ADEGH
25
PMC de A para H = PMC de A para E + PMC de E para H
PMC de A para H = PMC de A para B + SP from B to H.
PMC de A para H = PMC de A para C + SP from C to H.
PMC de A para H = PMC de A para vi + SP from vi to H; "
v i.
Algoritmo de Dijkstra para PMCs
• Síntese:
• Manter uma estrutura de dados com a lista
de nós e pesos dos percursos para esses
nós
• Usar infinito para representar um no
conjunto S de nós para os quais não tenha
sido calculado um percurso
• Em cada iteração, encontrar um nó em S,
calcular o percurso para esse nó e apagá-lo
de S
Algoritmo de Dijkstra para PMCs
• Síntese:
• Manter uma estrutura de dados com a lista
de nós e pesos dos percursos para esses
nós
• Usar infinito para representar um no
conjunto S de nós para os quais não tenha
sido calculado um percurso
• Em cada iteração, encontrar um nó em S,
calcular o percurso para esse nó e apagá-lo
de S
Algoritmo de Dijkstra para PMCs
S = {0}
/* Actual MST */
for i = 0 to n
D[i] = M[0][i]
/* Shortest
path length from 0 to i */
end for
for i = 1 to n-1
find the smallest D[v] such that
v  S
S = S  {v}
for all vertices u  S
if (D[u] > D[v] + M[v][u])
then
D[u] = D[v] + M[v][u]
end if
end for
end for
Algoritmo de Dijkstra
Custo do Percurso mais curto de A para vi atavés de S
B
1
2
1
A
C
7
3
6
F
5
E
H
5
8
G
6
F
5
A B
C D E
F
G H
-- 2
1
?
?
?
A B
C D E
F
G H
-- 2
1
?
?
6
?
S = {A}
D
B
1
2
1
A
C
6
7
3
E
8
D
H
5
G
6
6
S = {A,C}
4
?
Algoritmo de Dijkstra(2)
Custo do Percurso mais curto de A para vi atavés de S
B
1
2
1
A
C
7
3
6
F
5
E
H
5
8
A B
C D E
F
G H
-- 2
1
3
?
?
F
G H
6
G
6
S = {A,C,B}
F
5
A B
C D E
-- 2
1
D
?
B
1
2
1
A
C
6
7
3
E
8
D
H
5
G
6
6
3 10 8
S = {A,C,B,E}
?
Algoritmo de Dijkstra(3)
Custo do Percurso mais curto de A para vi atavés de S
B
1
2
1
A
C
7
3
6
F
5
E
H
5
8
G
6
F
5
A B
C D E
-- 2
1
6
F
G H
3 10 8
?
S = {A,C,B,E,D}
D
B
1
2
1
A
C
6
7
3
E
8
D
H
5
G
6
A B
C D E
-- 2
1
6
F
G H
3 10 8 14
S = {A,C,B,E,D,G}
Algoritmo de Dijkstra (4)
Custo do Percurso mais curto de A para vi atavés de S
B
1
2
1
A
C
7
3
6
F
5
E
H
5
8
A B
C D E
-- 2
1
6
F
G H
3 10 8 14
G
6
S = {A,C,B,E,D,G,F}
F
5
A B
C D E
-- 2
1
D
B
1
2
1
A
C
6
7
3
E
8
D
H
5
G
6
6
F
G H
3 10 8 14
S = {A,C,B,E,D,G,F,H}
Algoritmo de Dijkstra: Exemplo
2
7
3
3
1
8
10
5
6
5
1
4
2
7
5
6
1
2
3
4
5
6
--
3
?
?
?
5
1
2
3
4
5
6
--
3 10 ?
?
5
1
2
5
6
--
3 10 7 12 5
1
2
--
3 10 7 12 5
1
2
--
3 10 7 11 5
1
2
--
3 10 7 11 5
3
3
3
3
4
4
4
4
5
5
5
6
6
6
Classificação de
Algoritmos/Protocolos
Multicast
Unicast
Simples
• LB
• Atraso
Dual
• Custo +Atraso
Múltiplo
• Múltiplas
Simples
• Custo
Dual
• LB + Atraso
• Atraso
• Custo +
Atraso
• Quaisquer 2
métricas
aditivas
• Métrica não
aditiva
• Atraso +
Jitter
Múltiplo
• Múltiplas
Encaminhamento Unicast com QoS
Restrições de quaisquer duas métricas aditivas
[w1,15,w2,15]
N1
[w1,54,w2,54]
[w1,24,w2,24]
N5
N2
[w1,53,w2,53]
[w1,54,w2,54]
[w1,23,w2,23]
N4
N3
w = w 1 + d w2
N1
w15
N5
w53
w12
w24
w54
N4
N2
w23
N3
 Combinação de métricas ponderadas de Jaffe propõe a
minimização duma combinação linear de pesos de 2 ligações
w1 + dw2 onde d=1 ou d=(c1/c2). A última obtém melhores
resultados que a primeira.
 Foi proposta uma estratégia de procura binária para escolher o
peso.
Classificação de
Algoritmos/Protocolos
Multicast
Unicast
Simples
• LB
• Atraso
Dual
• Custo +Atraso
Múltiplo
• Múltiplas
Simples
• Custo
Dual
• LB + Atraso
• Atraso
• Custo +
Atraso
• Quaisquer 2
métricas
aditivas
• Métrica não
aditiva
• Atraso +
Jitter
Múltiplo
• Múltiplas
Problema de Steiner
Seja G=(V, E) um grafo
indirecto com um número
finito de vértices V e um
conjunto de arestas E, e uma
função de custo que atribui a
cada aresta um valor de custo
real e positivo. Dado um
subconjunto S dos vértices de
V, o problema de Steiner é
encontrar um subgrafo G´ de
G, G' =(V', E'), que contém
todos os vértices em S, de tal
forma que o custo de todas
arestas em E' é mínimo. Os
vértices em S são designados
por especiais.
Encaminhamento Multicast com QoS
Restrições de custo
N1
1
1
N5
3
N2
4
2
1
N4
N3
 Uma árvore que alcansa todos
membros do grupo e minimiza o
custo total da árvore partilhada.
Encontrar essa árvore é um
problema NP-Completo.
Algoritmo de Kou, Markowsky e
Berman (KMB)
 Criar um grafo conexo onde as
arestas sejam as distâncias mais
curtas entre os membros do grupo.
 O algoritmo de Prim calcula a a
árvore de menor custo deste grafo
conexo.
 As arestas do grafo conexo são
posteriormente substituídas pelos
percursos mais curtos originais
para obter a árvore de Steiner.
Abordagens para QoS
Serviços Integrados
Abordagem com
informação de estado,
com informação por
fluxo.
Serviço fim-a-fim
grantido por fluxo.
Necessidade de reserva
de recursos.
Serviços
Diferenciados
Abordagem sem
informação de estado e
portanto mais escalável
Diferenciação de serviço
mais grossa. Nós de fronteira
classificam os pacotes
enquanto os nós interiores os
processam de acordo com a
classificação.
Eficácia do Encaminhamento com QoS
 Embora o encaminhamento com QoS aumente a
computação em cada nó, armazenamento de estado
e custo de comunicação, tem a vantagem de
aumentar a utilidade da rede e permitir uma
degração graciosa do desempenho.
 A presença de mecanismos com QoS assegura que
mesmo as aplicações mais convencionais e cujo
QoS sempre foi esquecido obtenham um melhor
desempenho do serviço de rede..
 O encaminhamento com QoS é mais eficaz quando
há desajustamento entre o tráfego e a capacidade da
rede e existem rotas alternativas com menor carga.
.
Questões em aberto
Necessidade de protocolos para
encaminhamento com QoS e técnicas
de negociação de QoS normalizados
Mecanismos eficientes para evitar
percursos com congestão, atrasos altos
de propagação e instabilidade no
processo de selecção de percursos.
(Contd …)
Questões em aberto(2)
 A imprecisão na informação de estado precisa
de ser manipulada de forma apropriada.
 Ao mesmo tempo que se maximiza o número
de fluxos com QoS, deve-se procurar optimizar
o desempenho e tempo de resposta ao tráfego
best-effort.
 Necessidade dum algoritmo/protocolo de QoS
genérico que use por exemplo uma única
métrica representativa de todas as outras com
um mínimo de perda de informação..
Resumo da Aula
 Encaminhamento com QoS
 Algoritmos e protocolos propostos para
encaminhamento com QoS em ambientes unicast e
multicast.
 Benefícios de desenvolvimento de
encaminhamento com QoS na interligação de
redes actualmente.
 Questões em aberto no encaminhamento com
QoS