N O TA S D E A U L A , R E V 7 . 0 – U E R J 2 0 1 8 – F L Á V I O A L E N C A R D O R
Redes de Comunicações
Filas
Flávio Alencar do Rego Barros Universidade do Estado do Rio de Janeiro
E-mail: [email protected]
Fascículo
1 Ê G O B A R R O S
1
UERJ 2018 Redes de Comunicações 1 Pg.1
Os cursos de Redes de Comunicações 1 e 2 estão organizados de forma a cobrir
na sua primeira parte (Redes de Comunicações 1) os conceitos mais gerais, ferramentas
de análise e descrição de redes, cabendo à segunda parte (Redes de Comunicações 2) o
estudo mais detalhado dos principais tipos de redes existentes e as técnicas mais
modernas envolvidas.
Estas notas de aulas se destinam a reduzir o trabalho de cópia do aluno durante
as aulas, mas também oferecer material de apoio na forma de exercícios propostos e
referências onde o aluno poderá complementar seu estudo. É importante perceber que
este material NÃO esgota o que o aluno deve ler durante o curso, nem mesmo substitui
a participação em sala de aula, devendo ser encarado como material de apoio.
O material de apoio, além destes fascículos, inclui por cada capítulo uma lista de
exercícios e sempre um ou mais textos adicionais (normalmente papers) ou um
programa, a ser distribuído ao longo do curso por via eletrônica.
Capítulos: 1.Teoria de Filas; 2.Estruturas e Modelos de Redes; 3.Comunicação de Dados; 4.Técnicas de Múltiplos Acessos; 5.Tratamento de Erros(*); 6.Infraestrutura TCP/IP – LANs(*). (*) Estes capítulos poderão eventualmente fazer parte de Redes de Comunicações 2 no próximo semestre. O final de Redes 1 determina o início de Redes 2 em sequência! Outro aspecto que diferencia as duas cadeiras é que Redes 1 é totalmente teórica, enquanto Redes 2 tem uma parte de experimentos de laboratório.
Processos Estocásticos e Teoria de Filas formam a base matemática mais
essencial para análise de redes de comunicações por vários motivos. Quando se pensa
em utilização de redes, nos defrontamos com questões de tráfego, processos de chegada
e de saída de pacotes e, para redes de dados em particular, fundamentalmente nos
UERJ 2018 Redes de Comunicações 1 Pg.2
interessa o tempo de espera dos pacotes nos roteadores do interior da rede, ou seja, o seu
comportamento em filas. As limitações da rede são muito mais afetadas pelas filas de
espera que propriamente pelas questões de transmissão e propagação propriamente
ditas.
A modelagem do comportamento das redes pode, assim, ser bem representadas
pelas ferramentas derivadas dos modelos básicos de filas e, a partir destes, pode-se
simular comportamentos, estratégias e resultados.
Posto isto, é importante observar que para trabalhar com os modelos de filas e
processos estocásticos, o ferramental essencial envolve probabilidade e variáveis
aleatórias discretas e contínuas. Portanto, vamos iniciar o curso fazendo uma breve
revisão disto (com viés para redes, que é o nosso interesse).
UERJ 2018 Redes de Comunicações 1 Pg.3
UERJ 2018 Redes de Comunicações 1 Pg.4
Vide lista 1.3
UERJ 2018 Redes de Comunicações 1 Pg.5
Vide lista 1.4
UERJ 2018 Redes de Comunicações 1 Pg.6
UERJ 2018 Redes de Comunicações 1 Pg.7
Dimensionar um sistema baseado em filas envolve resolver o contraditório entre
a visão de usuário e a visão gerencial do fornecedor do serviço, e as medidas de
desempenho das redes (também chamados parâmetros de efetividade) devem ser
olhadas dentro deste ponto de vista. São elas, dentre outras, o tempo médio de espera na
fila, o tempo médio de atendimento e o número médio de elementos na fila.
Especificamente para nosso interesse maior (redes!), mesmo filas teóricas e
irreais (por exemplo, com armazenamento infinito, que é algo impossível, pois os
roteadores apresentam memória RAM limitada) tem serventia, pois podem nos oferecer
resultados aproximados para aqueles parâmetros de efetividade. Como muitos outros
fatores de menor importância também afetam tais parâmetros, via de regra, estas
aproximações acabam por se revelar bastante úteis.
Vale frisar neste momento que certas medidas de desempenho das redes vão ser
expressas por variáveis aleatórias contínuas, outras por variáveis discretas, outras ainda
constantes. Um segundo aspecto a frisar é que das visões contraditórias entre usuário e
sistema, pode resultar uma variável aleatória que deveria ser minimizada dentro de uma
visão e maximizada dentro de outra.
UERJ 2018 Redes de Comunicações 1 Pg.8
UERJ 2018 Redes de Comunicações 1 Pg.9
Observe que p0 deveria ser minimizada na visão do cliente (pronto atendimento),
mas na visão gerencial o custo poderia ser imenso com grande quantidade de servidores,
ou seja, existe uma dualidade entre as duas visões!
A caracterização das filas envolvem os 5 parâmetros:
1. Processo de chegadas
2. Processo de saídas
3. Número de postos de atendimento
4. Capacidade de cada posto de atendimento
5. Disciplina da fila
Os dois primeiros (chegadas/saídas) deverão ter um tratamento estatístico, os
dois próximos (número de postos/capacidade) meramente contagem e o último
(disciplina) serão tratados por heurísticas, a mais simples e popular é a FIFO (First In
First Out) ou FCFS (First Come First Served).
As úteis relações de Little (parâmetros de efetividade) pressupõem:
λ - taxa média de chegadas; µ - taxa média de atendimento
Em qualquer sistema de filas é suposto ambos conhecidos.
UERJ 2018 Redes de Comunicações 1 Pg.10
A relação ρ = λ/ µ , conhecida como intensidade de tráfego, relaciona o número
de elementos chegando por unidade de tempo com o número de elementos atendidos
por unidade de tempo. Importa desde já pontuar que ρ TEM que ser menor que 1, senão
não tem fila (o sistema “engarrafa”! Pense na ponte Rio-Niterói no caso em que entram
mais carros do que saem. Evidentemente, assim, chega um momento que não podem
entrar mais carros na Ponte). ATENÇÃO: para QUALQUER problema de filas esta
condição TEM que ser verificada à priori!
Observe que conhecido N_
(número médio de elementos no sistema) é possível
derivar os outros parâmetros de efetividade via equações de Little.
Outra ferramenta matemática (e estatística) que dá conta das chegadas e saídas
deriva das chamadas Cadeias de Markov, com chegadas e saídas podendo ser descritas
como um processo de nascimento e morte como descreveremos a seguir. O ponto de
partida é o Processo de Poisson.
Processo de Poisson: Pn(t + ∆t) = p[(n) em t E (0) em ∆t] + p[(n-1) em t E (1) em ∆t] + ... +
UERJ 2018 Redes de Comunicações 1 Pg.11
p[(0) em t E (n) em ∆t] = pn-1(t)p1(∆t) + pn-2(t)p2(∆ t) + ... + pn(t)p0(∆t) TODAS ZERO
Aplicando limite à equação e restringindo para n = 0 ; após n = 1 e
generalizando chegamos àquelas relações do slide 1-14.
PROVA:
a) Termo genérico: (n elementos no sistema)
t ∆t
n 0 321321ttptnp
ttoptnpttnp
∆
∆−+
∆−
∆=∆+
λλ
)(1)(11
)()()(
n-1 1
então: dttndp
tnptnpt
tnpttnp
t
)()(1)(
)()(
0lim =−+−=
∆−∆+
→∆λλ
b) Caso particular: (n=0, 0 elementos no sistema)
t ∆t
0 0 321ttoptopttop
λ−
∆=∆+
1)()()(
então: dttodp
topt
topttop
t
)()(
)()(
0lim =−=
∆−∆+
→∆λ
0)( =⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅−=∈⇒ nttop λ
c) Caso particular: (n=1, 1 elemento no sistema)
t ∆t
1 0 321321ttptop
ttoptpttp
∆
∆+
∆−
∆=∆+
λλ
)(1)(1
)()(1)(1
0 1
então: dttdptptop
ttpttp
t
)(1)(1)()(1)(1
0lim =−=
∆−∆+
→∆λλ
UERJ 2018 Redes de Comunicações 1 Pg.12
1)(1 =⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅∈= − nttp tλλ⇒
Generalizando: 0!
)()( >⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅∈
∈=−
− nn
tttptn
tn
λλ λλ
Propriedade: Se as chegadas em uma fila seguem o processo de Poisson, então o tempo
entre chegadas sucessivas é exponencialmente distribuído.
O Processo de Nascimento e Morte, este sim é o modelo essencial para o
tratamento de filas. Trata-se de uma generalização do Processo de Poisson. Considera-
se agora que durante um tempo infinitesimal das três, uma: a) não chega nenhum
elemento, não sai nenhum elemento (significa que em ∆t não tem elemento novo no
sistema); b) chega um, e não sai nenhum (significa que em ∆t tem um elemento novo no
sistema); c) chega um cliente, sai um elemento (significa que em ∆t não tem elemento
novo no sistema). Perceba que estas hipóteses são compatíveis com o Processo de
Poisson! O slide 1-16 ilustra estas hipóteses e os resultados obtidos.
Chamamos aqui sua atenção para o caso do cálculo de p0, quando o sistema não
tem elementos durante t, não entra nenhum elemento novo em ∆t, portanto, não tem
nenhuma probabilidade de sair elemento em ∆t!
UERJ 2018 Redes de Comunicações 1 Pg.13
A tabela de possibilidades de chegadas e saídas mostradas no slide 1-16 nos
permite equacionar:
Pn(t + ∆t) = pn(t)[1 - λn ∆t – 0 (∆t)][1 - µn ∆t – 0 (∆t)] + pn-1(t)[λn-1 ∆t – 0 (∆t)][1 - µn-1 ∆t – 0 (∆t)] + pn+1(t)[1 - λn+1 ∆t – 0 (∆t)][µn+1 ∆t – 0 (∆t)]
Desenvolvendo de modo similar ao que fizemos no Processo de Poisson e
também supondo regime estacionário, onde as derivadas no tempo são zero, obtemos o
resultado mostrado no slide 1-16. Observe que, de novo, na prática, se usa os λs iguais e
os µs iguais nas equações acima.
De posse destas ferramentas e resultados podemos passar a caracterizar cada tipo
particular de fila. A primeira, M/M/1/∞/FIFO, é a mais simples, e, certamente, a mais
importante, porque grande número de sistemas de redes pode ser aproximado por este
tipo de fila, onde o armazenamento é suficientemente grande para ser considerado ∞,
apenas um servidor, regime de atendimento do tipo FIFO e entradas e saídas aleatórias
de elementos (markovianas).
UERJ 2018 Redes de Comunicações 1 Pg.14
A forma mais popular de descrever filas, como já mencionado, considera
processos de chegada e de saída markovianos, regido pelas idéias dos processos de
“nascimento e morte”. Porém, em certas situações, quase nada se conhece sobre eles
(sistema G/G/1). Sabe-se apenas que: λτ é o número de chegadas no sistema, p0 é a
fração onde o servidor está livre e 1/µ é o tempo médio de serviço.
Como no regime permanente as entradas se igualam às saídas, e que as saídas
podem ser avaliadas assim:
saídas = tempo de serviço/tempo médio de serviço = (τ - p0 τ)/(1/µ ) λτ = µτ (1 – p0), então:
p0 = 1 - ρ Para que o sistema seja estável: 0 < ρ < 1
UERJ 2018 Redes de Comunicações 1 Pg.15
No sistema M/M/1 as chegadas são markovianas, valem os resultados que já
obtivemos:
pn+1 = (λ + µ)pn/ µ - λ pn-1/ µ p1 = λ p0/ µ, assim: p1 = (λ/µ) p0; p2 = (λ/µ)2 p0; p3 = (λ/µ)3 p0; ... pn = (λ/µ)n p0, ou seja:
pn = ρn (1 - ρ)
Fique claro aqui: para este sistema, a probabilidade de existirem n elementos no
sistema depende EXCLUSIVAMENTE de ρ. Da mesma forma, o pronto atendimento
(que vimos ser variável fundamental tanto do ponto de vista do cliente, quanto do
servidor!).
UERJ 2018 Redes de Comunicações 1 Pg.16
Prova de :1
_
ρρ−
=N
( ) ( ) ( ) ( ) ( )∑∑∑∑∑ =−=−=−=−=== −−
k
k
k
k
k
k
k
k
kk kkkkkpNEN 11
_
1111][ ρρρρρρρρρρ
( ) ( ) ( ) ( )( ) ρ
ρ
ρρρ
ρρρρρ
ρρρρ
ρρρ
−=
−−=
−
−=−=
−= ∑∑ 121
111
1111dd
k
kdd
k
kdd
Uma derivação útil é:
} }
ρρµ
λµλ
µλ
λρρ
λρρ
−=⇒
−=⋅
−=⋅
−=⇒
−=
1
__
1
11
1
11
_
1
_
__
SWW
WW
N
s
N
(tempo no servidor)
UERJ 2018 Redes de Comunicações 1 Pg.17
Uma correlação útil é aquela entre o tempo médio de resposta e o grau de
utilização do sistema (dado por ρ, lembra?) para um dado percentil (aqui é fornecido
sem demonstrações):
−
=y
Wyt100
100ln)(_
, onde y é o percentil em questão (vide lista 1.9).
Observe que _
W se amarra com ρ, enquanto S_
W é normalmente fixado, pois depende
da tecnologia existente no momento.
UERJ 2018 Redes de Comunicações 1 Pg.18
Vamos agora estudar um sistema estritamente realístico, onde a capacidade de
armazenamento é limitada (K). Por exemplo, um roteador contém memória RAM
limitada, de modo que se chegar pacotes além do seu limite de armazenamento, é sua
OBRIGAÇÃO descartá-lo. Naturalmente esta restrição vai afetar os diversos parâmetros
de efetividade da fila.
UERJ 2018 Redes de Comunicações 1 Pg.19
Em filas M/M/1/K somente K elementos podem entrar no sistema (pK é a probabilidade
do sistema estar CHEIO).
Agora muda apenas que: pn = ρn p0 válido para 1≤ n ≤ K, a partir deste número o
roteador deve descartar.
Pelo teorema da probabilidade total: 1 = 0ΣK p0 ρn
= p0 0ΣK ρn = p0{0Σ∞ ρn - K+1Σ∞ ρn } = p0 {1/(1- ρ) – (ρ)K+1 - (ρ)K+2 - ...} = = p0 {1/(1- ρ) – ρK+1 (1 + ρ + ...)} = p0 {1/(1- ρ) – ρK+1 (1/(1 - ρ))} = = p0 (1 – ρK+1 )/(1 - ρ), então: p0 = (1 - ρ)/ (1 – ρK+1 ) , e, conseqüentemente : pn = {(1 - ρ)/ (1 – ρK+1 )} ρn
Fazendo ∑==K
nnpNEN0
_
][ então chegamos à equação do número médio de elementos
no sistema mostrado no slide 1-21.
Observe que, usando Little:
( )opNqN −−= 1__
UERJ 2018 Redes de Comunicações 1 Pg.20
Observe também que ´
__
λ
N=W , onde λ’ é a taxa efetiva de ingresso no sistema, e vale:
λ’ = λ - λ pK = λ(1 - pK)
Exemplo:
Uma interface de rede atende pacotes que chegam a uma taxa de 5 pacotes/seg seguindo
um processo de Poisson e seu tempo de atendimento (de um pacote) é de 1/6 de
segundo em média, tempo este exponencialmente distribuído.
a) Supondo não haver limite de bufferização:
a.1) calcule os parâmetros de efetividade e o tempo ocioso do servidor;
a.2) se é suportável esperar 0.5 segs para processamento, calcule a probabilidade do pacote esperar mais que isto;
a.3) quais são as probabilidades de existirem na fila mais de 4, 10 e 30 pacotes?
b) Supondo agora haver descarte a partir de 5 pacotes no sistema, recalcule o tempo ocioso do servidor e os parâmetros de efetividade;
c) Se é suportável esperar 0.5 segundos, ao fim do qual o pacote é descartado, calcule a probabilidade de descarte com esta restrição;
d) Qual a probabilidade de descarte no sistema sem a restrição temporal?
Resposta: Possivelmente em sala de aula.
UERJ 2018 Redes de Comunicações 1 Pg.21
Vamos agora fazer a generalização de filas, não só com armazenamento restrito,
mas também para certo número de servidores trabalhando em paralelo. As
demonstrações aqui nos interessam menos que os resultados finais e as características
peculiares deste sistema.
UERJ 2018 Redes de Comunicações 1 Pg.22
Imaginemos múltiplos servidores idênticos, mas ainda capacidade infinita de
armazenamento (M/M/c/∞). Então, os coeficientes de elemento e de uso do sistema são,
respectivamente:
r = λ/µ e ρ = λ/c µ conseqüentemente:
p0 = 1/{0Σc-1 (rc/n!) + (rc/c!).1/(1 - ρ)}, o que permitirá derivar: Nq = (p0 rc+1)/{(c-1)! (c-r)2}
Restringindo-se agora a capacidade (M/M/c/K) valem as mesmas hipóteses para
r e ρ, mas também λ’ = λ(1 - pK). Assim, obtém-se p0 mostrado no slide 1-23 e, com
ele, deriva-se Nq, também mostrado no slide 1-23. Os demais parâmetros saem por
Little. Para ρ = 1 são válidos:
UERJ 2018 Redes de Comunicações 1 Pg.23
∑−
=
+−⋅+=
1
0)1(
!!
1c
n
cno
cKcr
nr
p e
( )1]1)(1(1[
1!)( 12
_=+−−−−⋅
−= −+− ρρρρ
ρρρ
ΚcKcKc
oq cK
ccp
N
Também são considerados para 0 ≤ n ≤ c-1 e c ≤ n ≤ K, respectivamente:
opn
nrnp ⋅=
! e op
ccnc
crnp ⋅
−=
!
É interessante observar que sistemas “self-service”, como as applets Java, são do tipo
M/M/ ∞/ ∞. Neste caso:
r = λ/µn , p0 = exp(-r) e assim:
qN_
= q_
W = 0 (não há filas)
_W = 1/ µ ;
_N = λ/µ , onde µ denota a taxa de permanência no sistema.
UERJ 2018 Redes de Comunicações 1 Pg.24
Como podem se comportar os roteadores? Como tratar o fluxo de pacotes recebidos?
Para responder a estas questões precisamos analisar as políticas de escalonamento de
filas e a questão do descarte de pacote.
UERJ 2018 Redes de Comunicações 1 Pg.25
Vamos aproveitar o momento que discutimos as disciplinas das filas para uma
primeira abordagem de tráfego na principal rede de dados: a Internet. A abordagem é
meramente informativa, sem maiores preocupações quantitativas.
A Internet não foi projetada para demanda de serviços sofisticados, diferente do
projeto das redes ATM (veremos ambas em detalhes no futuro). O serviço de
datagramas IP sem conexão (também analisaremos isto brevemente!) apresenta as
características mostradas no slide 1-25. Roteadores tradicionais fazem escalonamento
FCFS (First Come First Served, equivalente ao que estamos chamando de FIFO) sem
examinar o tipo de tráfego ou marcá-lo. Não existe aqui controle de tráfego, garantias de
justiça ou isolação de tráfego. O projeto das Redes de Serviços Integrados – Banda
Larga (B-ISDN) definiu a tecnologia ATM para sua infraestrutura, e, diferente da
Internet (que usa a suíte TCP/IP), agregou desde o projeto estas preocupações. Apenas
recentemente a Internet passou a buscar o atendimento de QoS (Quality of Service)
através das tecnologias de Serviços Integrados (IntServ) e de Serviços Diferenciados
(DiffServ), ambos serão objeto de nosso estudo em Redes 2. Por que foi assim? Porque a
preocupação com QoS surgiu quando multimídia entrou na Rede, e isto foi depois da
UERJ 2018 Redes de Comunicações 1 Pg.26
proposta TCP/IP, enquanto ATM, mais nova, incorporou esta preocupação no seu
nascedouro.
Vamos, por ora, voltar à Internet convencional. Tráfegos pela Rede são diferentes e
com necessidades diversas.
Na Internet, no entanto, a demanda de tráfego é cada vez mais variada e
sofisticada. Estes tráfegos devem compartilhar enlaces e atender a diferentes padrões,
como ilustrado no slide 1-26. O elemento básico da infraestrutura de redes, o roteador,
apresenta filas de recepção e de transmissão, podendo na eventualidade de experimentar
“fila cheia” descartar pacotes. É bom também ter em mente que o maior vilão do atraso
na Internet é o congestionamento nas filas de roteadores, situação que exigirá maior
processamento de escalonamento e/ou descarte.
Devemos aqui pontuar que aplicações diversas exigem também de forma diversa
a infraestrutura da Internet, em termos de, principalmente, retardo, perdas e banda. Se
diz que as aplicações são mais (ou menos) elásticas a estes parâmetros.
UERJ 2018 Redes de Comunicações 1 Pg.27
As demandas de tráfego pelas aplicações podem ser classificadas como
mostrado no slide 1-27. Algumas destas aplicações poderiam tirar proveito do apoio da
rede, portanto, torna-se necessário um novo comportamento no suporte da rede para
reduzir tais carências.
Na Internet a transmissão de pacotes não é escalonada. O protocolo TCP (que
veremos em detalhes futuramente) roda apenas nas pontas da rede e tenta compensar os
problemas de não escalonamento através de uma porta que pode bufferizar dados,
porém, se a fila for muito grande, adiciona-se retardo desnecessário, se for muito
pequena, aumenta muito as perdas.
De tudo que foi exposto, torna-se claro a necessidade de políticas para
escalonamento e para gerência de enfileiramento (gerência de buffer e descarte). É o que
veremos agora.
UERJ 2018 Redes de Comunicações 1 Pg.28
Para disciplinas de filas, além da tradicional FIFO (ou FCFS) temos as
alternativas:
1.Múltiplas prioridades: É a extensão à FIFO com o estabelecimento de uma FIFO
para cada prioridade. Características:
- controle simples de retardo para classes altas.
- sem isolação, sem garantias de justiça.
2. WFQ (Weighted Fair Queuing): Assegura justiça estabelecendo o número de
finalizações (NF). Quanto menor NF, o pacote é servido primeiro.
NF = RN + número de bits do pacote, onde RN é o round-number
- se a fila está vazia, o menor NF é servido.
- se a fila não está vazia, é calculado:
NF = NFMAX + número de bits do pacote
3. HWFQ (WFQ hierárquico): O excesso de banda pode ser redistribuído segundo uma
hierarquia.
UERJ 2018 Redes de Comunicações 1 Pg.29
No exemplo mostrado no slide 1-29, pacotes chegando são indicados por setas
numeradas na parte de cima, o número indica a ordem de chegada, enquanto partidas
são indicadas na parte de baixo. O tempo que o pacote gasta em serviço corresponde ao
retângulo sombreado. Como a disciplina da fila é FIFO, os pacotes partem na mesma
ordem que chegam. Observe que após a partida do pacote 4, o enlace permanece certo
tempo ocioso, até a chegada do pacote 5.
Esta é a disciplina de filas mais comum (popular) por ser mais simples e barata
de projetar. No entanto, para um cenário de QoS, é a mais ineficiente, observe o
comportamento de ti na figura.
UERJ 2018 Redes de Comunicações 1 Pg.30
Uma estratégia mais elaborada é manter filas de maior prioridade que outras
dentro do roteador. Um pacote que chega é classificado em uma ou mais classe de
prioridade e colocado na respectiva fila. O critério de seleção da prioridade é feito
baseado no campo Type of Service (ToS) no pacote IPv4 (veremos futuramente em
detalhes) ou então baseado no endereço fonte ou destino, ou mesmo outro critério
qualquer. Cada classe de prioridade tem sua própria fila e entre pacotes de mesma classe
a política de serviço é tipicamente a tradicional FIFO.
UERJ 2018 Redes de Comunicações 1 Pg.31
No slide 1-31 se encontra um exemplo uma operação de filas com prioridade. Os
pacotes 1, 3 e 4 pertencem à classe de prioridade alta, enquanto pacotes 2 e 5 pertencem
à classe de prioridade baixa. Durante a transmissão do pacote 1, os pacotes 2 e 3
chegam e são enfileirados respectivamente nas filas de prioridade baixa e alta. Após a
transmissão do pacote 1, o pacote 3 (de mais alta prioridade) é selecionado para
transmitir em seguida (Mesmo que o pacote 2 tenha chegado um pouco antes!). O
pacote 4 (mais prioritário) chega durante a transmissão do pacote 2 (menos prioritário).
Se a disciplina é de fila de prioridade não-preemptiva, a transmissão do pacote 2 não
é interrompida, o 4 só transmite após o fim da transmissão do pacote 2.
UERJ 2018 Redes de Comunicações 1 Pg.32
Uma disciplina alternativa é o enfileiramento round robin. Aqui, pacotes são
também classificados em classes, porém, ao invés de permanecerem em uma fila estrita
de prioridade, um escalonador round robin alterna serviços entre as classes. Na forma
mais simples de escalonamento round robin, um pacote classe 1 é transmitido, após, um
pacote classe 2, após, um pacote classe 1, e assim sucessivamente. Um refinamento seu
é a disciplina conservativa de trabalho, onde o enlace nunca fica ocioso se existe
pacotes de qualquer classe para transmissão. No slide 32 está ilustrado um exemplo,
onde pacotes 1, 2 e 4 pertencem à classe 1, e pacotes 3 e 5 pertencem à classe 2. O
pacote 1 começa ser transmitido logo após sua chegada na fila de saída, pacotes 2 e 3
chegam durante a transmissão do pacote 1, portanto vão para respectivas filas. Após a
transmissão do pacote 1 o escalonador comuta para um pacote classe 2, portanto,
transmite pacote 3! Ao final da transmissão do pacote 3, o escalonador comuta para
classe 1, portanto, transmite pacote 2, e seguiria assim sucessivamente. Ao final da
transmissão do pacote 2, porém, só existe enfileirado o pacote 4 (também classe 1),
portanto, a disciplina conservativa de trabalho garantirá que o pacote 4 será
transmitido a seguir do pacote 2.
UERJ 2018 Redes de Comunicações 1 Pg.33
Uma Generalização da disciplina round robin chamada disciplina Weighted
Fair Queuing (WFQ) tem sido muito usada em arquiteturas QoS e é empregado nos
roteadores de hoje em dia. Nela, pacotes que chegam são também classificados e
enfileirados na área apropriada. Como no escalonamento round robin, um escalonador
WFQ servirá as classes de maneira circular (no exemplo do slide 1-33, classe 1, classe
2, classe 3, classe 1, etc). WFQ é também uma disciplina conservativa de trabalho.
WFQ difere de round robin, na medida que cada classe pode receber uma quantidade
de serviço diferencial durante cada intervalo de tempo. Especificamente, considere cada
classe, i, ser associada a um peso, wi. Sob WFQ, durante qualquer intervalo de tempo
no qual existem pacotes classe i para enviar, será garantido para esta classe uma fração
do serviço igual a wi/(Σwj), onde a soma no denominador é calculada sobre todas as
classes que também tenham pacotes enfileirados para transmissão. No pior caso, mesmo
que todas as classes tenham pacotes enfileirados, a classe i terá ainda garantias de
receber uma fração wi/(Σwj) da banda. Assim, para um enlace com taxa de transmissão
R, a classe i sempre alcançará um throughput de, no mínimo, R.wi/(Σwj).
UERJ 2018 Redes de Comunicações 1 Pg.34
As estratégias básicas para descarte de pacotes são:
a)“descarta da cauda”: é a mais simples, Se o buffer enche, descarta o pacote que chega.
Não casa bem com TCP.
b)“descarta da cabeça”: até que tenha espaço para o que chega.
c)“descarta da mais longa”: idem, para várias filas.
Fluxos de dados podem ser medidos de acordo com algum perfil de tráfego. Se
eles excedem este perfil, os pacotes podem ser marcados para sofrerem preferência no
descarte. Entre os esquemas de descarte sobressai o RED (Random Early Detection)
que tenta detectar o início do congestionamento antes que a fila encha, medindo o
comprimento médio dela. Chegando a um limite, o pacote que chega pode ser
descartado com probabilidade proporcional à quantidade de vezes que o limite foi
alcançado. Observe o resultado no slide 1-35 a seguir.
UERJ 2018 Redes de Comunicações 1 Pg.35
Neste caso, o TCP é instruído a reduzir o ritmo enquanto ainda existe espaço na
fila. (RED casa bem com TCP).
Uma variante é o WRED (Weighted RED) onde o dispositivo usa alguma
inteligência em selecionar o tráfego a descartar primeiro. (só para ilustrar, mas sem
entrar em detalhes, ele faz isto baseado em IP TOS e na extensão de enlace de dados
IEEE802.1p).
Uma forma mais avançada ainda é o FRED (Flow RED) que monitora o
comprimento da fila por fluxo e descarta pacotes dos fluxos mais profundos primeiro. A
racionalidade é que, enquanto emissores “bem comportados” (aqueles mais adaptativos)
fazem backoff, um fluxo não adaptativo pode consumir exagerada banda no
congestionamento. Com FRED, este tipo de fluxo será considerado inelástico e tratados
como tal.
Considerando em conjunto uma e outra ação nos roteadores, descarte e
escalonamento, temos as disciplinas de filas que eles obedecem.
UERJ 2018 Redes de Comunicações 1 Pg.36
UERJ 2018 Redes de Comunicações 1 Pg.37
UERJ 2018 Redes de Comunicações 1 Pg.38
A forma com que as aplicações interagem com estas disciplinas propiciadas pela
infraestrutura de rede será objeto de nossa atenção em capítulo futuro (Redes 2) onde se
analisará QoS (Quality of Service).
UERJ 2018 Redes de Comunicações 1 Pg.39
Texto de apoio deste capítulo: 1-QueueingAnalysis.pdf