Archive for the ‘modelagem’ Category

Como estimar latência e largura de banda ?

29 de julho de 2010

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 pode 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]

Diagrama conceitual do benchmark ping-pong

Diagrama conceitual do benchmark ping-pong

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 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.wordpress.com/
Visitado em 28/07/2010

[2] Latência e largura de banda
https://tecnologiassemfio.wordpress.com/2010/07/07/latencia-e-largura-de-banda/
Visitado em 28/07/2010

[3] De onde vem a latência da rede ?
https://tecnologiassemfio.wordpress.com/2010/07/21/de-onde-vem-a-latencia-da-rede-2/
Visitado em 28/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

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.

Anúncios

De onde vem a latência da rede ?

21 de julho de 2010

Hilton Garcia Fernandes

No texto Latência e largura de banda [1], neste blog Tecnologias sem Fio [2], foi discutido o modelo linear

no qual a latência α é um custo constante em tempo da transmissão de n bytes. O fator β multiplicado pelo número de bytes, é associado à máxima banda disponível na rede. Isto é: 1/β é a banda máxima disponível.

Entendidos os conceitos no modelo linear, falta tentar entender o que causa os custos.

A latência pode ser associada a vários fatores

  • em uma rede cabeada do tipo Ethernet [3], é necessário evitar colisões [4]. Ou seja: dois pacotes serem enviados ao mesmo tempo na mesma rede. Há um algoritmo chamado CSMA/CD [5], que permite detectar colisões.
    Seu custo é aproximadamente fixo para um único pacote;
  • em uma rede sem fio do tipo Wi-Fi [6], há um problema semelhante. Neste caso, devido a características do meio físico das ondas eletromagnéticas, o algoritmo é chamado de CSMA/CA [7], e busca evitar colisões (ou collision avoidance), em vez de detectá-las.
    Aqui, o custo também é relativamente fixo para um único pacote;
  • outro problema, a cada dia mais relevante no mundo de internets [8], ou redes interconectadas — e da Internet [9], ou grande rede mundial — é a transferência entre redes, ou roteamento [10]. Neste caso, os pacotes de informação são reescritos, para levar em conta a entrada em outras rede. E isto tem um custo, de novo a cada pacote;
  • ainda há um outro componente dos custos fixos: o chamado encapsulamento e desencapsulamento de pacotes de dados — tanto do ponto de vista teórico da arquitetura OSI [11], ou daquele em geral implementado, a arquitetura TCP/IP [12].
    Em um caso ou outro, a rede é dividida em diversos níveis (ou camadas), o que permite, por exemplo, a independência de tecnologias — redes usando diferentes suportes físicos conseguem comunicar entre si: computadores ligados em redes 3G [13] podem se falar com outros em redes DSL [14]
    O custo de de transferir pacotes entre diferentes camadas da rede também ocorre pacote a pacote.
  • fragmentação de pacotes [15]: pacotes muito grandes podem ter que ser quebrados em pedaços menores, se forem maiores que o tamanho máximo de pacotes naquele segmento de rede, o MTU [16].

Todos estes custos ocorrem pacote a pacote. Sendo assim, se uma mensagem for suficientemente longa para ser quebrada em vários pacotes na rede, sofrerá várias vezes as mesmas negociações de colisão, de roteamento etc. ?

De fato, isto ocorrerá. Mas há efeitos que minoram este poder multiplicativo:

  • aquisição do meio: quando um computador começa a transmitir pela rede, mantém durante algum tempo o direito de transmitir. Isto está incorporado aos algoritmos de tratamento de colisões justamente para minimizar os custos de seguidas negociações;
  • pipelining [17], ou efeito “linha de montagem”: em uma linha de montagem [18], o fato de haver várias unidades trabalhando em paralelo em diferentes partes de um bem a ser montado garante que o intervalo entre o término de diferentes produtos seja menor do que o tempo total de produção de um produto.
    Um velho professor explicava pipelines dizendo que o tempo total para produzir um Volkswagen Sedan (o popular fusca) era de 48 horas. Contudo, o tempo entre um Sedan e outro era de apenas 40 minutos.
    No caso de uma transmissão de rede, há pelo menos dois níveis de paralelismo: a CPU, que processa o encapsulamento dos pacotes e a placa de rede, que faz as negociações de nível mais baixo, necessárias para encaminhar a mensagem pela rede, fazendo negociações CSMA/CA, por exemplo.

Em próximas postagens em Tecnologias sem Fio serão apresentados mais detalhes da estimativa dos importantes parâmetros latência e largura de banda, bem como parâmetros complementares — que podem melhorar a compreensão das redes.

Referências

[1] Latência e largura de banda
https://tecnologiassemfio.wordpress.com/2010/07/07/latencia-e-largura-de-banda/
Visitado em 16/07/2010

[2] Tecnologias sem Fio
https://tecnologiassemfio.wordpress.com/
Visitado em 16/07/2010

[3] Ethernet
https://secure.wikimedia.org/wikipedia/pt/wiki/Ethernet
Visitado em 16/07/2010

[4] Colision domain
https://secure.wikimedia.org/wikipedia/en/wiki/Collision_domain
Visitado em 16/07/2010

[5] CSMA/CD
https://secure.wikimedia.org/wikipedia/en/wiki/CSMA/CD
Visitado em 16/07/2010

[6] Wi-Fi
https://secure.wikimedia.org/wikipedia/pt/wiki/Wi-fi
Visitado em 16/07/2010

[7] CSMA/CA
https://secure.wikimedia.org/wikipedia/en/wiki/CSMA/CA
Visitado em 16/07/2010

[8] Internetworking
https://secure.wikimedia.org/wikipedia/en/wiki/Internetworking
Visitado em 16/07/2010

[9] Internet
https://secure.wikimedia.org/wikipedia/en/wiki/Internet
Visitado em 16/07/2010

[10] Roteamento
https://secure.wikimedia.org/wikipedia/pt/wiki/Roteamento
Visitado em 16/07/2010

[11] OSI model
https://secure.wikimedia.org/wikipedia/en/wiki/OSI_model

Visitado em 16/07/2010

[12] TCP/IP model
https://secure.wikimedia.org/wikipedia/en/wiki/TCP/IP_model
Visitado em 16/07/2010

[13] 3G
https://secure.wikimedia.org/wikipedia/pt/wiki/3G
Visitado em 16/07/2010

[14] DSL
https://secure.wikimedia.org/wikipedia/pt/wiki/
Visitado em 16/07/2010

[15] IP fragmentation
https://secure.wikimedia.org/wikipedia/en/wiki/IP_fragmentation
Visitado em 16/07/2010

[16] Maximum transfer unit
https://secure.wikimedia.org/wikipedia/en/wiki/Maximum_transmission_unit
Visitado em 16/07/2010

[17] Pipelining
https://secure.wikimedia.org/wikipedia/en/wiki/Pipelining
Visitado em 16/07/2010

[18] Assembly line
https://secure.wikimedia.org/wikipedia/en/wiki/Assembly_line
Visitado em 16/07/2010

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.

Latência e largura de banda

7 de julho de 2010

Hilton Garcia Fernandes

Muito já foi dito e continua a ser falado sobre latência e largura de banda, dois conceitos fundamentais para a compreensão e caracterização das redes de computadores. É uma pena que, mesmo que sob os nomes equivalentes em inglês, latency e bandwidth, não é fácil encontrar na Web, a teia mundial dos computadores, definições claras e precisas dos termos. Talvez estes pertençam àquele tipo de termo que é reservado apenas a estudiosos práticos e estudantes acadêmicos de redes de computadores.

Um dos melhores textos sobre o assunto é [1], que define latência e largura de banda com bom humor e clareza. Aqui se usará a matemática, que pode apresentar esses conceitos com precisão e também clareza — apesar de que com menos humor.

É costumeiro descrever o tempo [2] — digamos em segundos — que é gasto em uma dada rede para transmitir uma mensagem de de n bytes como sendo

Usando termos matemáticos, esta é a equação de uma reta, onde α é a constante, ou coeficiente linear. E β é o gradiente da reta, ou coeficiente angular.

Se fosse possível transmitir uma mensagem de 0 bytes, o tempo T(0) seria α segundos. O parâmetro α é chamado de latência, ou até mesmo “latência da mensagem de zero bytes”. Para entender o significado de β na fórmula para T(n), vale a pena considerar a taxa de transferência B(n) conseguida para n bytes. Ela é

A taxa de transferência é calculada dividindo-se o número de bytes transferidos pelo tempo que a transferência ocorreu.

Para poder analisar melhor a fórmula, vale a pena considerar o inverso de B(n), ou

Voltando a B(n), tem-se

Quando n é muito grande, a divisão α/n fica muito pequena e tem-se:

Este é a máxima taxa de transmissão desta rede. Por isso, é costumeiro chamar o parâmetro 1/β de largura de banda da rede. Para evitar a divisão é que Hockney [2] apresenta a mesma fórmula para T(n) com o coeficiente angular na forma inversa, ou seja:

Deste modo, Hockney [2] pode falar na largura de banda como sendo ρ apenas, não como a divisão 1/β. Mas esta é apenas uma conveniência: os conceitos são os mesmos.

Conclusão

Resumindo:

  • latência (ou latency) é um custo inicial da rede, pago em toda transmissão de mensagem que nela seja feita — até mesmo na mensagem teórica de comprimento zero bytes.
  • largura de banda (ou bandwidth) é o desempenho máximo de uma rede, só atingido teoricamente em mensagens de tamanho infinito — do qual a rede se aproxima para mensagens muito grandes.

De qualquer modo, considera-se que latência e largura de banda como parâmetros capazes de descrever uma rede quase completamente.

Em próximas postagens em Tecnologias sem Fio serão apresentados mais detalhes destes dois importantes parâmetros, bem como parâmetros complementares — que podem melhorar a compreensão das redes.

Referências

[1] It’s the Latency, Stupid
http://rescomp.stanford.edu/~cheshire/rants/Latency.html
Visitado em 02/06/2010

[2] R. Hockney, “The communication challenge for MPP: Intel Paragon and Meiko CS-2,” Parallel Computing, vol. 20, no. 3, pp. 389-398, March 1994.

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.

Redes mesh e grafos

22 de janeiro de 2010

Hilton Garcia Fernandes

As redes sem fio do tipo mesh (a expressão em português “redes sem fio em malha” não tem sido usada no Brasil) [1] conectam entre si pontos de acesso (AP) [2] diretamente por rádio, evitando assim a necessidade de conexões cabeadas e ampliando a cobertura da rede sem fio para não apenas um AP, mas vários.

O conceito é muito amplo, mas normalmente é aplicado apenas a redes sem fio locais, as chamadas WLAN, principalmente do tipo Wi-Fi [3].

Os computadores clientes de um AP sem conexão direta à Internet podem obter essa conexão através de um outro AP que a possua, pelo processo chamado de hopping, ou pulo: o AP sem conexão com a Internet repassa os pacotes de informação para aquele que a possui. Depois, o AP conectado repassa os pacotes da resposta da Internet para aquele AP que sem conexão direta, que por sua vez, repassa ao cliente que solicitou a conexão.

As redes sem fio em malha podem ser estudadas de várias formas. Uma das mais interessantes, com certeza é a via dos grafos [4].

A teoria dos grafos é baseada em conceitos simples e poderosos. Um grafo pode ser simplesmente descrito como um conjunto de objetos que se conecta em pares. Os objetos são chamados vértices (ou nós) e as conexões entre eles são chamadas arestas.

Em termos das redes mesh, cada AP seria um nó e cada conexão entre eles seria uma aresta. Grafos que modelam redes mesh podem ser considerados não dirigidos, pois se há conexão de um primeiro AP para um segundo, com certeza há do segundo para o primeiro.

Grafos podem ser conexos, quando de um nó é possível chegar a qualquer outro, mesmo que seja necessário passar por mais de uma aresta. Grafos com o mínimo de arestas necessário para serem conexos são chamados árvores [5]. Em termos matemáticos, se n é o número de nós de uma árvore, o número de arestas dela será n – 1.

Ora, redes mesh têm como propriedade interessante a tolerância a falhas. Em outras palavras, isto significa que há vários caminhos entre um AP e outro. Por exemplo, entre um AP sem conexão com a Internet e outro conectado. Se um dos caminhos não for mais possível, haverá outra alternativa, eventualmente menos rápida, mas ainda assim capaz de permitir o acesso à Internet.

Por isso, uma rede mesh tem que ter mais do que o mínimo de conexões possível, para que haja redundância em pelo menos uma conexão. Ou seja: nestes termos, a rede mesh do grafo mencionado teria que ter pelo menos n arestas. Uma rede totalmente conectada [6] é uma rede com
n*(n – 1)/2
conexões, o que não é viável para redes maiores.

Outro ponto que favorece a qualidade de uma rede mesh é que a quantidade de conexões seja o melhor distribuída possível, sem que um único nó contenha todas conexões redundantes — pois este nó será um ponto de falha da rede; se ele cair, cairá parte importante da rede. O número de conexões de um dado nó é chamado grau desse nó.

O programa descstat.g [7] calcula estatísticas básicas dos nós de um dado grafo — uma das mais importantes é chamada coeficiente de variação [8], e mede a disparidade dos graus dos vértices de um grafo. Idealmente, o coeficiente de variação seria zero para uma rede onde todos nós tivessem o mesmo número de conexões.

O programa connect.g [9] avalia se um dado grafo é ou não conexo. No caso de redes mesh, identifica se todos pontos da rede se vêem ou não.

Tanto descstat.g [7] quanto connect.g [9] foram escritos usando-se o ambiente de programação gvpr, desenvolvido por Emden R. Gansner, disponível no pacote graphviz [10], um Software Livre poderoso, flexível e muito usado para visualização de grafos.

Referências

[1] Wireless mesh network

[2] Wireless access point

[3] Wi-Fi

[4] Teoria dos grafos

[5] Árvore (teoria dos grafos)

[6] Fully-connected network

[7] descstat.g

[8] Coeficiente de variação

[9] connect.g

[10] graphviz

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.