Encaminhamento com QoS

Sistemas Telemáticos

LESIGrupo de Comunicações por Computador

Materiais utilizados

• Tema é ainda objecto de I&D

• 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-umSimples Dual Múltiplo

GrupoSimples 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 forma satisfazer os requisitos das camadas superioresMeio Físico

Sequência de acções para disponibilizar a QoS fim-a-fim

Fim da Transferência dos

dados?

Fim da transferência dos dados

Sim

Não

A

Selecção do Percurso e transferência dos dados

(Encaminhamento com QoS)Tradução e negociação do QoS

Pedido de QoS por um host

Pedidoaceite?

Não Sim

A

Encaminhamento com QoSControlo de Admissão

Actualização da informaçãode estado

Reserva de Recursos(opcional)

Armazenamento e Escalonamento de pacotes

B

B

Busca na tabela deencaminhamento

Gestão de Recursos

Fim da Transferência dos

dados?

Fim daTransferência de Dados

Sim

CNão

C

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 rejeitadoFactores de decisão: LB residual, Nº Tx em cursoSe a aceitação levar à degradação de desempenho ,

o pedido é rejeitado Alternativa: reencaminhamento das aplicações

existentesRenegociaçã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 for feito 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 são limitadas

– 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

Métrica

w1 w2 w3

Percurso P

Multiplicativa

w = w1 . w2 . w3

Aditiva

w = w1 + w2 + w3

Côncava

w = max{w1 , w2 , w3}

Selecção do Percurso – Métricas e Restrições

Métricas

Simples

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 Métrica 1 Métrica 2

F-B 3 7

F-D-B 5 5

F-E-D-C-B 7 6

Percurso escolhidomin. salto/custo

PercursoEscolhido ?

D

E

F

1 1

11

1 1

1 1

1A

B

C

[1,2]

[1,2]

B[1,4]

[1,1]

A

[3,7]

[1,4]

[4,1]

[2,2]

CE

[3,1]

D

F

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 é NP-Completo. (Referência: P. Van Mieghem, F. A. Kuipers, “On the Complexity of QoS Routing”, na Computer

Communications.).

Classificação de Algoritmos/Protocolos Unicast

Simples MúltiploDual

Multicast

Simples MúltiploDual

• Múltiplas • Múltipla• Bandwidth

• Delay

• Custo +Atraso

• Largura de banda + atraso

• Qq 2 métricas aditivas

• Custo

• Atraso

• Métrica não aditiva

• Custo + Atraso

• Atraso + Jitter

• Largura de banda

• Atraso

Encaminhamento unicast Restrição de Largura de Banda

Filtragem da Topologia Algoritmo de Guerin Orda

N1

N3N4

N2N5

1

2

4

3

3 5

LB > 2

N1

N3N4

N2N5

1

2

4

3

3 5

N1

N3N4

N2N5

4

3

3 5

Maximizar Probablidade (LB Residual > 2)

N1

N3N4

N2N5

N1

N3N4

N2N5

N1

N3N4

N2N5

0.1

0.1

0.2

0.2

N1

N3N4

N2

0.1

0.1

0.2

0.2N5N5

N1

N3N4

N2

-log (0.1)

-log (0.1)

Problema aditivo

Classificação de Algoritmos/Protocolos Unicast

Simples MúltiploDual

Multicast

Simples MúltiploDual

• Múltipla• Custo

• Atraso

• Métrica não aditiva

• Custo + Atraso

• Atraso + Jitter

• Múltiplas• LB

• Atraso

• Custo+Atraso

• LB + Atraso

• Qualquer 2 métricas aditivas

Encaminhamento Unicast com QoS Restrições de Atraso e Largura de Banda

Algoritmo de Wang Crowcroft

N1

N3N4

N2N5

1

2

4

3

3 5

LB > 2

Elimina todas as ligações com largura de banda inferior à requerida.

A seguir, encontra o percurso mais curto relativamente ao atraso no grafo modificado usando o algoritmo de Djikstra.

N1

N3N4

N2N5

1

2

4

3

3 5

LB > 2LB > 2LB > 2

N1

N3N4

N2N5

4

3

3 5

LB > 2

N1

N3N4

N2N5

4

3

3 5

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?

1

2

4

6

3

5

10

7

81

5

67

2

3

5

1

2

4

6

3

5

10

7

81

5

67

2

3

5

Abordagem básica

PMC de A para H = PMC de A para B + PMC from B to H.

PMC de A para H = PMC de A para C + PMC from C to H.

PMC de A para H = PMC de A para vi + PMC from vi to H;

vi.

A B E F H 15

A B E G H 14

A C E F H 16

A C E G H 15

A D E F H 26

A D E G H 25

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

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 PMCsS = {0} /* Actual MST */for i = 0 to n D[i] = M[0][i] /* Shortest path length from 0 to i */

end forfor 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 forend for

Algoritmo de Dijkstra

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

S = {A}

S = {A,C}

Custo do Percurso mais curto de A para vi através de S

A B C D E F G H

-- 2 1 6 ? ? ? ?

A B C D E F G H

-- 2 1 6 4 ? ? ?

Algoritmo de Dijkstra(2)

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

S = {A,C,B,E}

S = {A,C,B}

A B C D E F G H

-- 2 1 6 3 ? ? ?

A B C D E F G H

-- 2 1 6 3 10 8 ?

Custo do Percurso mais curto de A para vi atavés de S

Algoritmo de Dijkstra(3)

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

S = {A,C,B,E,D,G}

S = {A,C,B,E,D}

A B C D E F G H

-- 2 1 6 3 10 8 ?

A B C D E F G H

-- 2 1 6 3 10 8 14

Custo do Percurso mais curto de A para vi atavés de S

Algoritmo de Dijkstra (4)

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

A

B

D

C E

F

G

H

21

6

3

8

17

5 6

5

S = {A,C,B,E,D,G,F,H}

S = {A,C,B,E,D,G,F}

A B C D E F G H

-- 2 1 6 3 10 8 14

A B C D E F G H

-- 2 1 6 3 10 8 14

Custo do Percurso mais curto de A para vi atavés de S

Algoritmo de Dijkstra: Exemplo

1

2

4

6

3

5

10

7

81

5

67

2

3

5

1 2 3 4 5 6

-- 3 ? ? ? 5

1 2 3 4 5 6

-- 3 10 ? ? 5

1 2 3 4 5 6

-- 3 10 7 12 5

1 2 3 4 5 6

-- 3 10 7 12 5

1 2 3 4 5 6

-- 3 10 7 11 5

1 2 3 4 5 6

-- 3 10 7 11 5

Classificação de Algoritmos/Protocolos Unicast

Simples MúltiploDual

Multicast

Simples MúltiploDual

• Múltiplas• Custo

• Atraso

• Métrica não aditiva

• Custo + Atraso

• Atraso + Jitter

• Múltiplas• LB

• Atraso

• Custo +Atraso

• LB + Atraso

• Quaisquer 2 métricas aditivas

Encaminhamento Unicast com QoS Restrições de quaisquer duas métricas aditivas

Combinação de métricas ponderadas de Jaffe propõe a minimização duma combinação linear de pesos 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.

N1

N3N4

N2N5

[w1,15,w2,15]

[w1,54,w2,54]

[w1,12,w2,12]

[w1,23,w2,23]

[w1,24,w2,24]

[w1,53,w2,53]

w = w1 + d w2

N1

N3N4

N2N5

w15 w12

w23w54

w53 w24

Classificação de Algoritmos/Protocolos Unicast

Simples MúltiploDual

Multicast

Simples MúltiploDual

• Múltiplas• Custo

• Atraso

• Métrica não aditiva

• Custo + Atraso

• Atraso + Jitter

• LB

• Atraso

• Custo +Atraso

• LB + Atraso

• Quaisquer 2 métricas aditivas

• Múltiplas

Árvore 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´ conexo e acíclico de G (árvore), 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.

Árvore geradora mínima

• No caso particular de todos os nós da topologia fazerem parte do grupo (ou seja quando S=V), o problema é mais simples e resolve-se calculando a árvore geradora mínima:

– Algoritmo de Prim – Algoritmo de Kruskall – …

Algoritmo de Prim

• Começa por seleccionar um qualquer vértice (não importa qual), adicionando-o à solução. Depois, iterativamente, escolhe-se a aresta de menor custo, com ligação a vértices da solução, que não forma ciclos e junta-se à solução:

O={1} (raiz da árvore). P={2,...,n}Enquanto (P <> Vazio)

Escolher aresta K(i,j) de menor custo,

com i pertencente a O e j pertencente a P

Fazer O = O U {k}

Fazer P = P \ {k}

– Demo: http://students.ceid.upatras.gr/~papagel/project/prim.htm

Algoritmo de Kruskall

• Selecciona a aresta de menor custo. Iterativamente adiciona sempre a aresta de menor custo ainda não seleccionada que não forme ciclos:

A1=0,A2=A

Enquanto (|A1| < n-1 arestas) ≥ && A2=0 fazer

Escolher aresta a(i,j) de A2 de menor custo

A2=A2-{a(i,j)}

Se vértices V(i) e V(j) não pertencem à mesma árvore:

Juntar as árvores de V(i) e V(j) numa única árvore.

– Demo: http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

Encaminhamento Multicast com QoS

Restrições de custo Uma árvore que alcança 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.

N1

N3N4

N2N5

1

2

3 4

1

1

Abordagens para QoS

Abordagem com informação de estado, com informação por fluxo.

Abordagem sem informação de estado e portanto mais escalável

Serviço fim-a-fim garantido por fluxo. Necessidade de reserva de recursos.

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.

Serviços Integrados Serviços Diferenciados

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 (1)

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.

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 QoSAlgoritmos 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