Atraso em Redes de Comutação de Pacotes

Prévia do material em texto

1 
 
Atraso Fim-a-Fim em Redes de Comutação de Pacotes 
Caroline Carvalho Machado 
 
I. Introdução 
Atualmente as redes de computadores utilizam amplamente a comutação de pacotes 
devido a facilidade para interconectar redes com diferentes arquiteturas, além de fornecer 
alocação dinâmica de recursos e ter boa confiabilidade contra falhas de nó e enlace (link). Por 
outro lado, a comutação de pacotes oferece pouco controle sobre o atraso de pacotes para os 
comutadores [2]. O maior exemplo de rede de comutação de pacotes é a Internet. 
Para que um sistema final possa enviar dados para outro sistema final, o emissor deve 
segmentar os dados em pacotes que serão enviados através de uma série de nós (sistemas finais 
ou roteadores) até o destino. Os sistemas finais estão conectados por links e comutadores. Uma 
característica inerente ao processo de troca de pacotes é o atraso. 
O atraso médio necessário para enviar um pacote da origem ao destino é uma das mais 
importantes medidas de desempenho de redes. Considerações de atraso tem grande influência 
na escolha e desempenho de algoritmos, tais como roteamento e controle de fluxo. Conhecendo 
a distribuição do atraso ao longo da rede é possível redimensionar caminhos ou redesenhar 
partes da rede que atualmente não oferecem atraso limites aceitáveis [1, 3]. Para entender 
profundamente a rede de comutação de pacotes é necessário entender a natureza desses atrasos. 
O objetivo desse trabalho é compreender o atraso de pacotes em redes de 
computadores que se utilizam de comutação de pacotes. Entender o atraso possibilita uma boa 
concepção de algoritmos de rede, tais como algoritmos de roteamento e controle de fluxo, o 
dimensionamento de buffers e capacidade de links. 
 
II. Atraso Fim-a-Fim 
De acordo com o RFC 2212 da Internet Engineering Task Force (IETF) [15], a 
qualidade de serviço da Internet depende do atraso e da largura de banda. Como garantia, limites 
para o atraso são estabelecidos. Ao combinar os parâmetros dos diversos elementos em um 
caminho, é possível calcular o atraso máximo que um pacote de dados experimentará ao ser 
transmitido através desse percurso. O atraso será estável desde que o caminho não mude. 
Atraso total entre dois sistemas finais pode ser dividido em quatro categorias principais 
descritas em [1, 2, 9]: 
 Atraso de processamento (Dp): tempo necessário para examinar o cabeçalho do pacote e 
determinar para onde direcioná-lo, incluindo fatores como o tempo necessário para verificar 
os erros em bits existentes no pacote que ocorreram durante a transmissão. Quase sempre é 
desprezível, no entanto, tem forte influência sobre a produtividade máxima de um roteador 
Independe da quantidade de tráfego tratado pelo nó desde que o poder computacional não 
seja um recurso limitante, caso contrário, uma fila de processamento separada deve ser 
introduzida antes da fila de transmissão. Atrasos em roteadores de alta velocidade são da 
ordem de microssegundos ou menos. 
2 
 
 Atraso de fila (Dq): quando um ou mais pacotes chegam no roteador eles são absorvidos 
pelo buffer e formam uma fila, o tempo decorrido enquanto o pacote espera para ser 
transmitido no enlace é o atraso de fila. Depende da quantidade de outros pacotes que 
chegaram antes. Se a fila estiver vazia e não houver outro pacote sendo transmitido, então 
o tempo de fila do pacote é zero. Varia da ordem de micro a milissegundos. 
 Atraso de transmissão (Dt): tempo necessário para que o primeiros e o último bit do pacote 
sejam transmitidos. Da ordem de micro a milissegundos. 
 Atraso de propagação (Dew): Tempo necessário para propagar um bit desde o início do 
enlace até o roteador seguinte. É determinado pelo tempo necessário para que uma onda 
eletromagnética atravesse o meio físico. É independente do tráfego no enlace. 
Para simplificar o cálculo do atraso fim-a-fim será omitida a possibilidade de um 
pacote requerer retransmissão em um link devido a erros, congestionamento e perda de pacotes. 
Esses problemas não ocorrem com frequência, mas são problemas sérios que quando não 
tratados provocam um aumento significativo do atraso. 
O atraso fim-a-fim pode ser dado pelo acúmulo dos atrasos nodais [9]. Supondo que 
haja N-1 roteadores entre a máquina de origem e a máquina de destino e que a rede não esteja 
congestionada (atrasos de fila desprezíveis), o atraso fim-a-fim (Dee) é dado por: 
𝐷𝑒𝑒 = 𝑁(𝐷𝑝 + 𝐷𝑡 + 𝐷𝑒𝑤) 
Entretanto, o atraso varia de pacote para pacote. O protocolo TCP inclui melhorias no 
algoritmo de retransmissão por timeout que levam em consideração o tamanho do pacote. 
Pacotes longos apresentam atrasos duas ou três vezes menores do que pacotes mais curtos. 
Mensagens de pacote único são favorecidas em detrimento das mensagens multi-pacotes [11]. 
 
III. Distribuição do Atraso 
A melhor forma de analisar o atraso é separá-lo em duas partes, uma fixa ou 
determinística (Dd) e outra indeterminada ou estocástica (Ds). O atraso fixo depende do caminho 
escolhido e não é determinado pelas normas de qualidade de serviços, mas sim pelo mecanismo 
de configuração. Apenas o atraso indeterminado, mais especificamente um dos componentes, 
o atraso de fila, é determinado pelas normas. 
Antes de apresentar as equações para o atraso determinístico e para o estocástico é 
necessário discutir uma característica do atraso de processamento (Dp). Ele é determinado pelo 
poder computacional do nó, pela complexidade dos protocolos e dificilmente é afetado pelo 
tráfego na rede. Entretanto, o atraso de processamento varia de pacote para pacote devido às 
múltiplas tarefas executadas no roteador, portanto também possui uma parte indeterminada [3, 
7]. Logo, Dp é dividido em duas partes, uma fixa (Dpd) e outra indeterminada (Dps): 
𝐷𝑝 = 𝐷𝑝𝑑 + 𝐷𝑝𝑠 
Agora é possível obter as equações separadas para o atrasos fixo (Dd) e para o atraso 
indeterminado (Ds): 
𝐷𝑑 = 𝐷𝑝𝑑 + 𝐷𝑡 + 𝐷𝑒𝑤 
𝐷𝑠 = 𝐷𝑝𝑠 + 𝐷𝑞 
3 
 
Umas típica distribuição de atraso fim-a-fim é mostrada na Figura 1. Cerca de 80% 
das distribuições de atraso pertencem a essa classe conhecida com o heavy-tail, outras 
distribuições de atraso são estudadas em [3, 7]. 
Figura 1 – Histograma de distribuição heavy-tail com a separação entre Dd e Ds. 
 
Fonte: BOVY, C. J. et al., 2002 
O atraso estocástico é fortemente influenciado pelo tráfego, o modelo analítico de 
Poisson foi bastante utilizado mas estudos comprovaram que o tráfego na rede é melhor 
modelado utilizando processos auto-similares devido a função de densidade da cauda cair mais 
lentamente que uma exponencial. A cauda é regida pela lei de potência Pr(X(t) > x) ∼ Kx−α, 
com um índice de cauda α ∈ (0, 2) e uma expansão da constante K [10]. 
Modelos usando Poisson ou outros que não refletem exatamente a dependência de 
longo alcance em tráfego real resultará em simulações e análises que subestimam 
significativamente as medidas de desempenho, tais como atraso médio de pacotes ou tamanho 
máximo da fila [13]. O modelo de Poisson falha em demonstrar a influência de vários fatores 
importantes como tamanho do buffer e duração do congestionamento para o tamanho da fila e 
consequentemente para o atraso. 
 
IV. Atraso de Fila 
Para iniciar um estudo sobre o atraso de fila é importante entender como ele varia em 
função da intensidade do tráfego, esse estudo é feito por Kurose e Ross (2010). Tomando a 
como a taxa média com que os pacotes chegam a fila (pacotes/segundo), R como a taxa de 
transmissão de dados (bits/segundo), L como o tamanho do pacote (bits), então a intensidade 
do tráfego (It) é dada por: 
4 
 
𝐼𝑡 = 
𝐿𝑎
𝑅
 
Se It > 1 então a velocidade com que os bits chegam a fila excederáa velocidade com 
que eles podem ser transmitidos para fora da fila. Nessa situação a fila tenderá a aumentar sem 
limite e o atraso tenderá ao infinito, entretanto a fila possui um limite, o tamanho do buffer, 
uma fila cheia provoca perda de pacotes deteriorando com facilidade a qualidade de serviço da 
rede. 
Para o caso em que It ≤ 1, o atraso na fila será influenciado pela natureza do tráfego. 
Se pacotes chegarem a cada L/R segundos, então a fila estará vazia e não haverá atraso no envio. 
Se pacotes chegarem em rajadas, mas periodicamente, poderá ter um significativo atraso de fila 
médio. Os pacotes que estão na fila sofrem são diferentes, se N pacotes chegarem ao mesmo 
tempo a cada (L/R) N segundos, então o primeiro pacote não sofrerá atraso, o segundo sofrerá 
atraso de L/R segundos e o enésimo de (N-1) L/R segundos. 
Para garantir que os serviços na rede não sofram atrasos de fila muito longos, 
especificações de garantia foram estabelecidas pela IETF [15] levando em consideração um 
modelo de fluido no qual a geração de pacotes é representada por um fluido e o número de 
pacotes na fila é obtido por equações que regem a variação do fluxo. O atraso de fila é medido 
em função de dois parâmetros o tamanho do buffer (B) e a taxa de transmissão de dados (R). 
Esses dois valores estão sobre o controle da aplicação, se o atraso for maior que o esperado, a 
aplicação pode manipular esses valores de forma a reduzi-lo. 
Outros dois termos de erro são importantes para avaliar o atraso de fila, eles descrevem 
o desvio local máximo do modelo de fluido. O termo C é o erro dependente da taxa de 
transmissão R, representa o atraso que um pacote pode experimentar devido aos parâmetros de 
taxa de fluxo. O termo D é o erro por elemento independente de R, representa a pior variação 
do tempo através do elemento da rede. O elemento da rede deve se assegurar que o atraso de 
fila (Dq) para qualquer pacote seja: 
𝐷𝑞 < (
𝐵
𝑅
+
𝐶
𝑅
+ 𝐷) 
Entre as categorias, o atraso de fila sempre foi o mais preocupante, falhas no controle 
do atraso de fila podem provocar problemas graves, nas seções seguintes são apresentadas 
questões intrinsecamente relacionadas ao atraso e tamanho de fila. Ao compreendê-las é 
possível ter uma noção da necessidade de tantos estudos e esforços direcionados a esse tipo de 
atraso. 
 
V. Perda de Pacote 
Em situações normais, perda de pacote ocorre aleatoriamente e com pouca frequência 
devido a erros de transferência (<1%). Entretanto, em situações de congestionamento, quando 
o tráfego está muito intenso, a fração de pacotes perdidos aumenta significativamente [2, 8, 9]. 
Isso ocorre porque o buffer está cheio e, sem espaço para armazenar, o roteador deverá descartar 
os pacotes que estão chegando. 
Quando um pacote é perdido, a aplicação tenta o reenvio. Se a rede estiver 
congestionada, continuar tentando o reenvio até que o pacote encontre espaço na fila apenas 
5 
 
fará com que o congestionamento se agrave e a fila dificilmente diminuirá. Essa situação será 
aprofundada em VI. 
Na tentativa de evitar filas cheias e perda de pacote verificou-se ao longo dos anos um 
aumento significativo no tamanho dos buffers, o que acabou gerando outro problema conhecido 
como bufferbloat que será abordado em VIII. 
 
VI. Congestionamento 
Congestionamento ocorre quando a demanda de um recurso excede a capacidade 
disponível. Os efeitos de tal congestionamento incluem longos atrasos na entrega de dados, 
desperdício de recursos devido à perda de pacotes e até mesmo a ocorrência de colapsos, nos 
quais praticamente toda a comunicação na rede cessa. Em outubro de 1986 a Internet sofreu o 
primeiro de uma série de “colapsos de congestionamento”, durante este período a taxa de 
transferência de dados entre LBL e UC Berkeley caiu de 32 Kbps para 40 bps. 
Uma rede sobrecarregada ou congestionada é identificada através da perda de pacotes, 
que se torna significativo apenas quando a fila está cheia e o tráfego intenso, e através de 
transmissão interrompida por timeout, que geralmente ocorre devido à perda de pacotes. 
A carga sobre a rede pode ser medida através do tamanho médio da fila em intervalos 
fixos de tempo, aproximadamente o tempo de ida e volta de um pacote (RTT). Se Li é a carga 
em um intervalo de tempo i, uma rede é dita não congestionada quando Li varia muito pouco 
no intervalo de tempo. 
𝐿𝑖 = 𝑁 (N constante) 
Se a rede está sujeita a congestionamento, o modelo de ordem zero se torna inválido e 
o tamanho médio da fila se torna a soma de dois termos. O N representa a taxa de chegada de 
novo tráfego e o atraso relacionado a ele, enquanto que o novo termo representa o que ainda 
resta do tráfego do intervalo de tempo anterior e os efeitos dessa sobra, como retransmissão 
devido a timeout. 
𝐿𝑖 = 𝑁 + 𝛾𝐿𝑖−1 
Quando a rede está congestionada, γ se torna grande e o tamanho da fila cresce 
exponencialmente. Para que a rede se estabilize, γ voltar a ser zero, a fontes do tráfego devem 
desacelerar, no mínimo tão rapidamente quanto as filas estão crescendo [8]. 
Há duas estratégias para lidar com o congestionamento. Uma delas é denominada 
“congestion control” que age apenas quando o congestionamento é detectado, enquanto a outra 
é denominada “congestion avoidance” com avanços direcionados para o gerenciamento ativo 
de fila (AQM) e age quando o congestionamento é esperado [14]. 
A estratégia para evitar o congestionamento consiste em duas partes. Primeiro a rede 
deve ser capaz de sinalizar as fontes de tráfego que um congestionamento está ocorrendo ou 
prestes a ocorrer, em contrapartida, as fontes devem desacelerar o tráfego enquanto receberem 
o sinal e acelerarem quando deixarem de receber. 
A outra parte da estratégia consiste em reduzir o tamanho da janela W indicado no 
cabeçalho TCP do pacote. O decréscimo d é multiplicativo e se torna exponencial caso o 
6 
 
congestionamento persista. O tamanho da janela deve retornar ao normal ao fim do 
congestionamento [8]. 
𝑊𝑖 = 𝑑𝑊𝑖−1 (d < 1) 
 
VII. Gerenciamento Ativo de Fila e o Algoritmo RED 
Algoritmos de gerenciamento de fila administram o comprimento das filas de pacotes, 
descartando pacotes quando necessário ou conveniente evitando atrasos de fila muito grandes. 
Tradicionalmente, quando não há AQM, é definido um tamanho máximo em termo de pacotes 
para cada fila, ela deve aceitar pacotes até que seu comprimento máximo seja alcançado e então 
rejeita pacotes até que a fila diminua ao terminar de enviar um dos pacotes. 
Esta técnica é conhecida como "queda de cauda", uma vez que o pacote que chegou 
mais recentemente é descartado quando a fila está cheia. Este método tem duas desvantagens 
importantes. Em algumas situações ela permite que alguns fluxos monopolizem o espaço de 
fila, impedindo que outras conexões obtenham espaço no buffer. Também permite que a fila 
fique cheia ou quase cheia por longos períodos de tempo [4]. É importante reduzir o tamanho 
da fila em seu estado estável, caso contrário, mesmo em uma situação normalizada, os pacotes 
terão de sofrer um atraso de fila considerável. 
O ponto forte do gerenciamento ativo de filas é impedir que o buffer estoure, ele reage 
ao congestionamento rejeitando pacotes antes da fila encher. Descartar pacotes antes do 
transbordamento do buffer, permite que roteadores controlem quando e quantos pacotes irão 
descartar. Um dos mais conhecidos algoritmos de gerenciamento ativo de filas é o Random 
Early Detection (RED). 
O RED descarta pacotes probabilisticamente. A probabilidade de descartar um pacote 
aumenta à medida que o tamanho de fila médio, estimado em certo período de tempo, também 
cresce. De forma que, se a fila estevevazia em um passado recente, os pacotes não serão 
descartados, entretanto, se recentemente a fila esteve cheia ou quase cheia, indicando 
congestionamento persistente, pacotes recém chegados estarão suscetíveis a rejeição. Em 
resumo, o RED é composto por duas partes: a estimativa do tamanho médio da fila e a decisão 
de ter ou não de descartar um pacote [6]. 
De forma simples, um mecanismo de gerenciamento ativo de filas pode fornecer as 
seguintes vantagens para fluxos responsivos (que desaceleram na ocorrência de um 
congestionamento): reduz o número de pacotes descartados em roteadores, proporciona atrasos 
inferiores e permite que novas conexões obtenham espaço no buffer. 
 
VIII. Bufferbloat 
Devido às dificuldades para se implementar AQM’s, se tornou comum a ideia de que 
buffers maiores impediriam o problema de filas cheias. Infelizmente isso acabou gerando um 
problema conhecido como bufferbloat, buffers excessivamente largos e frequentemente cheios 
[5]. Como observado anteriormente em atraso de fila, quando uma fila tende a aumentar sem 
limites, o atraso de fila tende ao infinito. Buffers excessivamente largos, permitem filas 
7 
 
excessivamente grande e atrasos de fila absurdamente maiores. Isso fez com que atrasos de fila 
passa da ordem de milissegundos para vários segundos [12]. 
É importante destaca que filas/buffers em si não são o problema. A fonte do problema 
está no descompasso entre o tamanho da janela do pacote e o largura de banda do gargalo da 
rede. Buffers são colocados em frente a enlaces de comunicação para absorver os pacotes que 
chegam e não podem ser atendidos enquanto outros pacotes estiverem ocupando o enlace, a fila 
gerada nesse processo é a fila boa. Os pacotes não podem chegar ao destino mais rápido do que 
o tempo que leva para enviar um pacote no enlace com a menor taxa de transferência [5]. 
Quando o fluxo de chegada de pacotes se estabiliza, a fila não aumenta nem diminui, 
gerando apenas excesso de atraso, essa é a fila ruim. O caminho para detectar o bufferbloat é 
separar o bom do ruim. A fila boa desaparece em cerca de um RTT, enquanto que a fila ruim 
persiste por vários RTT. Uma maneira para separar os dois tipos de fila é levar em consideração 
o comprimento mínimo da fila ao longo de um intervalo de tempo. 
Os algoritmos CoDel (Controlled Delay Management) usam o comprimento local 
mínimo da fila e o tempo de permanência do pacote através da fila [12]. O menor atraso de fila 
para determinado intervalo é armazenado. Se o tempo de permanência na fila é maior do que o 
calculado, então o algoritmo descarta pacotes para fazer com que o atraso volte ao tamanho 
apropriado. 
 
Referências 
 
[1] BERTSEKAS, D.; GALLAGHER, R. Data Networks. 2ª ed. Prentice Hall, 1991. 
[2] BOLOT, J.-C. End-to-end packet delay and loss behavior in the Internet. Proc. SIGCOM'93, p. 289-
298, 1993. 
[3] BOVY, C. J.; MERTODIMEDJO, H. T.; HOOGHIEMSTRA, G.; UIJTERWAAL, H.; MIEGHEM, 
P. V. Analysis of end-to-end delay measurements in Internet. Proc. PAM 2002, Mar. 2002. 
[4] BRADEN, B; CLARK, D.; CROWCROFT, J.; DAVIE, B.; DEERING, S.; ESTRIN, D.; FLOYD, 
S.; JACOBSON, V.; MINSHALL, G.; PARTRIDGE, C.; PETERSON, L.; RAMAKRISHNAN, K.; 
SHENKER, S.; WROCLAWSKI, J.; ZHANG, L. Recommendations on queue management and 
congestion avoidance in the internet. Network Working Group, RFC, v. 2309, 1998. 
[5] FLOYD, S.; JACOBSON, V. Random Early Detection gateways for Congestion Avoidance, 
IEEE/ACM Transactions on Networking, v.1 n.4, Agosto 1993, p. 397-413, 1993. 
[6] GETTYS, J.; NICHOLS, K. Bufferbloat: Dark buffers in the Internet. Communications of the ACM, 
v. 55 n. 1, p. 57–65, 2012. 
[7] HOOGHIEMSTRA, G.; MIEGHEM, P. V. Delay distributions on fixed Internet paths. Delft 
University of Technology. 2001. 
[8] JACOBSON, V. Congestion avoidance and control. ACM SIGCOMM Computer Communication 
Review. ACM, p. 314-329, 1988. 
[9] KUROSE, J.F.; ROSS, K.W. Redes de Computadores e a Internet: Uma Abordagem Top-Down. 5ª 
ed. Pearson Education, 2010. 
[10] LIEBEHERR, J.; BURCHARD, A.; CIUCU, F. Delay bounds in communication networks with 
heavy-tailed and self-similar traffic. IEEE Transactions on Information Theory, v. 58, n. 2, p. 1010-
1024, 2012. 
8 
 
[11] MILLS, D. Internet delay experiments. RFC 889, 1983. 
[12] NICHOLS, K.; VAN JACOBSON. Controlling Queue Delay. Queue, v. 10, n. 5. 2012. 
[13] PAXSON, V.; FLOYD, S. Wide Area Traffic: The Failure of Poisson Modeling. IEEE/ACM Trans. 
Networking, vol. 3, no. 3, 1995, p. 226-244, 1995. 
[14] RYU, S.; RUMP, C.; QIAO, C. Advances in internet congestion control. Communications Surveys 
& Tutorials, IEEE, v. 5, n. 1, p. 28-39, 2003. 
[15] SHENKER, S.; PARTRIDGE, C.; GUERIN, R. Specification of guaranteed quality of service. 
Network Working Group, RFC, v. 2212, 1997.