Como estimar latência e largura de banda?

Hilton Garcia Fernandes

Este é mais um texto sobre latência e largura de banda de redes de computadores do blog Tecnologias sem Fio [1], iniciado com o texto Latência e largura de banda [2], que apresentou os conceitos de acordo com o modelo matemático linear, que é relativamente simples.

Em De onde vem a latência da rede ? [3], também neste blog, foram listados os fenômenos da rede que dão origem a uma demora constante em sua resposta.

Neste texto vão ser comentadas as formas de se estimar os parâmetros latência e largura de banda. Estimar significa que os parâmetros são oscilantes, devido a variações de capacidade da rede.

Além disso, é preciso escolher forma de medir os tempos de passagens de mensagem rede -- pois existem muitas formas de usar a rede: leitura e escrita de e-mail, navegação pela Web etc.

Formulação do problema

Qualquer usuário de uma rede, como a Internet [4], sabe que a disponibilidade da rede podem variar. Sendo assim, os valores que se calcula são estimativas; similares às médias, por exemplo.

Além disso, também há o problema de como obter a medida: apesar de ser intuitivo falar nos conceitos, existem muitas formas de se usar uma rede, sendo a Internet apenas uma delas. Por isto, escolhe-se um conjunto limitado de atividades que permita calcular medida; em termos usuais em computação, escolhe-se um benchmark [5].

Apresentação conceitual do benchmark usado

Para medir o tempo de passagem de uma mensagem de um computador A para um outro B, seria preciso que o B informasse em que momento recebeu a mensagem. Para isso teria que enviar uma outra mensagem. Infelizmente, há um problema de sincronização dos relógios dos computadores A e B: como as redes são rápidas, uma mensagem leva pouquíssimo tempo e, os relógios teriam que estar ajustados com muita precisão, o que pode não ser fácil fazer.

Outra solução é que A envie uma mensagem e aguarde a resposta de B a ela. Assim, terá toda temporização do processo é feita em um único computador. Este é o objetivo do benchmark chamado ping-pong [6].

Ele pode ser representado pelo diagrama a seguir, sugerido por [7]



Para que o computador A envie a mensagem para B, será necessário que a mensagem atravesse camadas de rede, como comentado em [3]. Isto é simbolizado pelo declive d1. A mensagem passa então pela rede durante o tempo t1, quando é recebida por B.

As informações da mensagem então atravessam as camadas de rede, agora no sentido inverso, da camada física para aquela de aplicação, durante o tempo s1. Recebida a mensagem por B, ela é imediatamente enviada de volta para A. Precisa então atravessar camadas de rede, agora daquela de aplicação para a física, o que é feito durante o tempo d2.

E agora a mensagem é transmitida de B para A durante um tempo t2. Quando chega em A, atravessa novamente camadas de rede, durante tempo s2, quando é finalmente recebida pelo programa de benchmark.

O tempo T´ que A mede do envio à recepção da mensagem é a somatória de todos os tempos:


Se condições de rede forem as mesmas, e os computadores A e B forem razoavelmente similares, t1 = t2 = t. E, do mesmo modo, é razoável supor que os tempos de descida à rede são iguais: d1 = d2 = d. E, ainda, que os tempos de subida da camada física até a de aplicação são iguais também: s1 = s2 = s.

Assim, o tempo total se torna:


Considera-se agora os tempos de descida d e subida s de camadas da rede como sendo um único tempo p de percorrer camadas de rede; ou seja: p = d + s. Assim, tem-se a fórmula


Esta fórmula faz lembrar que o tempo medido em A é realmente o dobro do tempo de transmissão de uma mensagem de A para B apenas, sem o retorno: apenas o ping, sem o pong.


É claro que o tempo T vai ser maior quanto maior for o número de bytes transmitidos; exatamente o que ocorre com t. Contudo, p vai ser o mesmo, independente do tamanho da mensagem. Assim, voltando ao modelo linear


É fácil ver que:

1. α, a constante de custo, é equivalente a p, o tempo em que mensagem "sobe" e "desce" a hierarquia de camadas de rede, da camada física àquela de aplicação e vice-versa;



2. t, o tempo em que a mensagem foi transmitida, é função do número de bytes a ser transmitidos --- equivale no caso a βn;



3. o tempo total de transmissão T de uma mensagem com n bytes é mesmo função apenas de n e, por isso, é representado como T(n).

De fato, usando métodos estatísticos é possível estimar α e β. A estatística mostra que é praticamente total o ajuste do modelo linear às medidas de rede obtidas por benchmarks como o ping-pong.

Estas conclusões são discutidas a seguir.

Calculando parâmetros através de estatística

A estimativa dos parâmetros α é β é feita através de regressão linear [8]. Em poucas palavras, isto implica em minimizar o erro da aproximação do modelo linear aos tempos medidos de T. São feitas muitas medidas de tempos, para mensagens de diferentes tamanhos: Em notação mais formal, são feitas m medidas de tempos para vários tamanhos de mensagem, que serão chamadas Ti e ni.

(Uma das técnicas para minimizar a variabilidade minimizar os erros de medida é fazer várias medidas de tempo para um mesmo tamanho de mensagem.)

A técnica básica para essa estimativa se chama método dos mínimos quadrados (MMQ) [9]. Trata-se de minimizar o erro quadrático, o somatório de cada diferença entre o medido e o calculado. Isto é expresso pela fórmula:

onde Ti são os tempos medidos; para cada cada um deles um correspondente tamanho de mensagem ni. Assim, o tempo T1 foi obtido quando se usou mensagem de tamanho n1 etc.

A estatística fornece ferramentas para validar, ou não, a aproximação -- principalmente se os ajustes não foram muito bons, por exemplo devido a oscilações de tráfego na rede. A ferramenta chamada ANOVA [10] permite avaliar se a aproximação foi tão ruim que o parâmetros β pode ser considerado nulos. Ou seja: não há nenhuma relação entre o tempo T de transmissão da mensagem e n, o tamanho dela em bytes.

O teste t de Student [11] permite avaliar individualmente a qualidade dos parâmetros. Isto é: o quanto α e β ajudam a explicar o comportamento de T em função de valores de n.

R [12] é um Software Livre [13] para estatística muito completo, de excelente qualidade, que tem esses recursos já implementados.

Referências

[1] Tecnologias sem fio
https://tecnologiassemfio.blogspot.com/
Visitado em 30/07/2010

[2] Latência e largura de banda
http://tecnologiassemfio.blogspot.com/2010/07/latencia-e-largura-de-banda.html
Visitado em 30/07/2010

[3] De onde vem a latência da rede ?
http://tecnologiassemfio.blogspot.com/2010/07/de-onde-vem-latencia-da-rede.html
Visitado em 30/07/2010

[4] Internet
https://secure.wikimedia.org/wikipedia/pt/wiki/Internet
Visitado em 28/07/2010

[5] Benchmark (computação)
https://secure.wikimedia.org/wikipedia/pt/wiki/Benchmark_%28computa%C3%A7%C3%A3o%29
Visitado em 28/07/2010

[6] What does ping pong benchmark mean?
http://icl.cs.utk.edu/hpcc/faq/index.html#132
Visitado em 28/07/2010

[7] Benchmarking of Multicast Communication Services
ftp://ftp.cse.msu.edu/pub/acs/reports/msu-cps-acs-103.ps.gz
Visitado em 28/07/2010

[8] Regressão linear
https://secure.wikimedia.org/wikipedia/pt/wiki/Regress%C3%A3o_linear
Visitado em 28/07/2010

[9] Método dos mínimos quadrados
https://secure.wikimedia.org/wikipedia/pt/wiki/Mmq
Visitado em 28/07/2010

[10] Regressão e ANOVA
http://www.fm.usp.br/dim/regressao/rquadrado.php
Visitado em 29/07/2010

[11] Teste t de Student
http://www.exatec.unisinos.br/~gonzalez/valor/inferenc/testes/testet.html
Visitado em 29/07/2010

[12] The R Project for Statistical Computing
http://www.r-project.org/
Visitado em 29/07/2010

[13] Software livre
https://secure.wikimedia.org/wikipedia/pt/wiki/Software_livre
Visitado em 29/07/2010