TE-723 – Comunicação de Dados - 2002
Prof. Dr. Eduardo Parente Ribeiro
Preservando QoS (atraso per-hop)
Apesar de se ter Fluxo Agregado
Preserving QoS Guarantees in Spite of Flow Aggregation
IEEE Trans. Network, feb/02
Aluno: Sinésio Julio Barberini
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Investigar se a QoS pode ser garantida
para um fluxo de pacotes agregado.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Programadores com garantia de taxa => reserva de:
Capacidade do buffer;

Largura de banda;
- Se estes recursos não estão disponíveis no
instante requisitado para a conexão da rede, a
requisição é negada!

Taxa de aplicação não excede a taxa negociada.
(aplicações em tempo real - áudio e vídeo)

Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Fluxo = seqüência de pacotes de uma aplicação:


Fluxo agregado = fluxos múltiplos chamados
constituintes reunidos em um único fluxo;
Taxa do fluxo agregado = soma das taxas
reservadas dos fluxos constituintes;
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Propósito de um fluxo agregado:




Melhorar a eficiência dos programadores;
Simplificar o gerenciamento dos fluxos;
Fila única - simplifica gerenciamento de buffers;
Redução do número de fluxos facilita a
programação de rotas;
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
• Canal de saída equipado com programador (rota);
•Regra: first-in-first-out;
•Saída livre, o programador escolhe o pacote recebido e transfere-o à saída;
•Taxa: no mínimo igual ao fluxo reservado.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Notação para cada fluxo f e programadores s

R.f
taxa de transferência reservada a f (B/s);

p.f.i
i-ésimo pacote do fluxo f;

L.f.i
comprimento (B) do pacote p.f.i;

A..s.f.i
instante de chegada do pacote p.f.i ao programador s;

E.s.f.i
instante de saída do pacote p.f.i do programador s;

Lmáx.f
comprimento máximo do pacote para o fluxo f ;

Lmáx.s
comprimento máximo do pacote para todos os fluxos no programador s;

C.s
capacidade (B/s) do canal de saída do programador s;
Definimos o tempo inicial S..s.f.i e tempo final F..s.f.i de um p.f.i da seguinte forma:

S..s.f.i
instante ao qual p.f.i é direcionado ao canal de saída de s;

F.s.f.i
instante ao qual p.f.i sai do programador s;
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Definição 1
Seja um fluxo de entrada f de um programador s
Lembrar que:
L.f.i/R..f = tempo =comprimento (B)/taxa(B/s)
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Tipos de programadores
•Programador Proporcional à taxa
•Programador Canal em tempo real
•Programador Em tempo inicial
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Programadores proporcional à taxa



Deste que o fluxo f reserva a taxa R.f do programador s, uma forma de definir o
prazo final do pacote p.f.i, é o p.f.i não sair mais tarde do que F.s.f.i + .s para
uma pequena constante .s (usualmente .s=Lmax.s/C.s).
Com um prazo final proporcional à taxa, o atraso per-hop de cada pacote é no
máximo Lmax.f/R.f + .s .
Este limite de atraso está acoplado com a taxa reservada do fluxo. Para diminuir
o atraso per-hop, logicamente, uma grande taxa deve ser reservada.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Programadores canal em tempo real

A cada fluxo f é definido um par de valores (.f, T.f), e o tamanho do pacote
é fixado . Assume-se que pacotes deste fluxo chegam com uma separação
inter-pacotes de no mínimo T.f, e o programador garante o atraso per-hop
de no máximo .f. Então o prazo final de cada pacote é o seu tempo de
chegada mais .f. Este prazo final é flexível, já que cada fluxo escolhe seu
valor .f.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Programadores em tempo inicial


São suficientemente flexíveis para representar prazos finais proporcional a taxa e em tempo real.

Se escolhemos .s.f.i.=Lmax.f/R.f + .s tempo inicial e proporciona a taxa serão iguais;

Se fazemos T.f =L.f/R.f, fazemos os prazos finais do tempo inicial igual ao tempo real.
Já que no programador em tempo inicial, o instante inicial do pacote determina o instante de saída de um
programador, devemos examinar como o instante inicial de um pacote muda de um programador para o
programador seguinte.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Teorema 1:
Dois programadores em tempo inicial consecutivos, sendo eles s e t e um caminho de fluxo f.
Teorema 2:
Seja t1,t2,.......tk uma seqüência de programadores em tempo inicial.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Agregando o fluxo
O fluxo é sempre separado
em seus constituintes imediatos
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Agregar de forma justa
•Limitaremos o tempo inicia de g em t como se o fluxo não fosse agregado.
•No lugar de s temos um programador que não agregue o fluxo e;
• f, h e d são entradas individuais do programador t.
•Do teorema 1 temos (sendo s um programador em tempo inicial):
Agr. é justo se:
Ñ-Agr. é justo se:
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
End-to-end diminui?
Visão intuitiva
Considerar agora, um fluxo agregado usando atraso proporcional à taxa:
Relembrando:
Entrega proporcional à taxa cada pacote p.g.i de um fluxo de entrada g:
• Sai do programador s não mais tarde do que F.s.g.j + .s
(.s é uma constante (geralmente Lmax.s/C.s))
• O atraso per-hop sem agregar é Lmax.f/R.f + Lmax.s/C.s
•Agregando é Lmax.g/R..g + Lmax.s/C.s onde g é a raiz do fluxo f em s
• f é um constituinte de g então R.f<R.g
•Logo o atraso agregado é menor do que sem agregar desde que Lmax.gLmax.f.
Conclui-se que agregando com atraso proporcional à taxa diminui-se o atraso end-to-end.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Roteador com 2 canais de entrada
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Logo, o acréscimo no tempo inicial do pacote raiz p.f.i no roteador é:
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Um aumento no tempo inicial é inversamente proporcional a R.g1.
Uma vez que R.g1R.f1 o aumento máximo acontece quando R.g1  R.f1
Pr em tempo inicial
Agr em tempo inicial
O incremento adicional causado por se ter agregado o fluxo é Lmax/R.f1!
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Assumamos que na entrada da rede o fluxo f1 é agregado com pelo
menos mais um fluxo com a mesma taxa. Então, R.g1 2R.f1. Neste
caso o acréscimo no tempo inicial do primeiro roteador é:
Pr em tempo inicial
Agr em tempo inicial
=
Logo, o aumento do per-hop no instante inicial de f1.
É o mesmo sem fluxo agregado!
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Vejamos um cenário mais real, com um maior número de fluxos
agregados com f1. Assumamos R.g1 10R.f1. O aumento do per-hop no
primeiro roteador é:
Pr em tempo inicial
Agr em tempo inicial
Logo, o aumento do per-hop no instante inicial de f1:
Diminui com o fluxo agregado em 1/5!
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
Conclusões
•Agregar múltiplos fluxos em um único fluxo preserva o limite de atraso end-to-end!
•As vantagens de se agregar um fluxo:
-Simplificar a programação (rotas)
-Reduzir o número de fluxos de entrada em um programador
O fluxo agregado só é separado em seus constituintes imediatos
(O autor acredita que talvez seja possível separar fluxos agregados sem expor todos os seus constituintes )
A análise da QoS foi direcionada ao atraso per-hop.
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica
Preserving QoS Guarantees in Spite of Flow Aggregation
FIM
Ministério da Educação
UNIVERSIDADE FEDERAL DO PARANÁ
Programa de Pós-Graduação em Engenharia Elétrica