a ferramenta euclideana - NCC
Transcrição
a ferramenta euclideana - NCC
ESTIMANDO ATRASOS EM REDES DE COMPUTADORES ATRAVÉS DE SISTEMAS DE COORDENADAS – A FERRAMENTA EUCLIDEANA Felipe Madruga2, Rafael Coelho², Jean Hamerski2,3, Marcelo Pias¹, Nelson Duarte Filho² ¹ Digital Technology Group Computer Laboratory University of Cambridge - Cambridge, UK ² Departamento de Matemática Fundação Universidade Federal do Rio Grande (FURG) Rio Grande, RS – Brasil ³Instituto de Informática Universidade Federal do Rio Grande do Sul (UFRGS) Porto Alegre, RS – Brasil {felmadruga,rafaelvc}@gmail.com, [email protected], [email protected], [email protected] Resumo. Este artigo aborda a Euclideana, ferramenta construída sob a forma de um sistema distribuído, capaz de estimar atrasos em redes de computadores. As estimativas são realizadas através da associação da topologia da rede a um espaço euclideano, onde a métrica de distância nesse espaço corresponde ao RTT entre pontos da rede. São apresentadas as bases científicas e tecnológicas adotadas para a construção da ferramenta e um exemplo capaz de ilustrar o funcionamento das idéias propostas. O sistema será utilizado no Projeto GIGA [RNP 2004], através do Projeto GigaIQoM [RNP 2005]. Palavras-chave: Medições em Redes de Computadores, Mapas Topológicos. 1. INTRODUÇÃO Um importante serviço de monitoramento, em uma rede de computadores, é o de estimativa de atrasos entre pontos nos quais medições não podem ser fácil ou diretamente obtidas. Por exemplo, entre hosts que não participam de infra-estruturas de medições ativas eventualmente existentes. Uma maneira de realizar esse serviço é construir um espaço euclideano onde os hosts e roteadores são localizados através de um sistema de coordenadas. Com técnicas desse tipo, que têm sido propostas e utilizadas em sistemas como o Lighthouses [Pias et al. 2004], o Virtual Landmarks [Tang and Crovella 2003], e o PIC [Costa et al. 2004], é possível estimar, com uma certa precisão, o atraso entre dois hosts, realizando apenas alguns testes envolvendo um conjunto pequeno de pontos de referência ’landmarks/lighthouses’, conforme são descritos na literatura. Apresenta-se neste trabalho a Euclideana, ferramenta que utiliza uma combinação de técnicas para a criação de um sistema de coordenadas para representar os atrasos entre os pontos de uma rede. A ferramenta, implementada através de um sistema de servidores distribuídos, atribui coordenadas num espaço euclideano, onde as medidas de distância tendem a refletir, dentro de uma precisão possível, os atrasos de ida e volta (Round Trip Time RTT) da rede. Uma vez que a cada ponto da rede pode ser atribuída uma coordenada, os atrasos entre dois pontos quaisquer podem então ser facilmente obtidos. É importante notar que as coordenadas são inferidas tão somente a partir de medições realizadas entre as ’landmarks/lighthouses’ e os pontos de interesse, o que torna a proposta viável. Através dela é possível amplificar o escopo de aplicação dos resultados de eventuais ferramentas de medições ativas existentes na rede, para pontos onde essas medições não foram efetivamente realizadas, e com isso reduzir o tráfego de teste. Cabe também salientar que a ferramenta encontra-se em fase de avaliação, e um dos aspectos que está sendo investigado diz respeito à precisão dos seus resultados frente aos requisitos das aplicações avançadas a serem experimentadas na rede do Projeto GIGA [RNP 2004], onde ela será instalada através do Projeto GigaIQoM [RNP 2005]. No que diz respeito a trabalhos relacionados, em [Ledlie et al. 2007] apresentam-se aspectos sobre cálculo de coordenadas em redes de computadores. São descritos resultados como os aqui buscados, porém utilizando Algoritmo Vivaldi [Dabek et al. 2004]. Discute-se uma API para serviços distribuídos de estimativa, sendo que as operações por ela fornecidas incluem medidas de intervalo de confiança e erro. Além disto, filtros são utilizados para aumentar a precisão dos resultados. Na seção que segue, resumem-se as bases científicas e tecnológicas sobre as quais a Ferramenta Euclideana encontra-se assentada. Na seção 3, se descreve a arquitetura básica de funcionamento da ferramenta, na seção 4 são apresentados resultados preliminares, e na seção 5, tecem-se considerações finais e propõem-se trabalhos futuros a serem realizados. 2. LIGHTHOUSES Uma técnica importante para representação de informações de proximidade em redes de computadores denomina-se Lighthouses [Pias et al. 2004],sendo ela a escolhida para construir a ferramenta de estimativa de atrasos aqui apresentada. A escolha dessa técnica se deu por motivos de escalabilidade (as coordenadas podem ser obtidas a partir de medições locais); por ela utilizar apenas transformações lineares para a atribuição de coordenadas aos pontos de rede (o que propicia rapidez no cálculo das coordenadas e obtenção de coordenadas exclusivas para cada ponto); e por ela se mostrar suficientemente precisa. 2.1 Objetivo do Lighthouses O objetivo do Lighthouses é estimar coordenadas para pontos de rede, a partir de informações métricas locais. No caso, o RTT de pacotes. Em termos matemáticos, isso corresponde a atribuir coordenadas a pontos geométricos, mapeando espaços métricos locais em espaços vetoriais locais (ver Figura 1), mais especificamente espaços euclideanos, e transformar as coordenadas locais em coordenadas globais, através de matrizes de transição. Outras técnicas (como GNP [Ng and Zhang 2002] e PIC [Costa et al. 2004]) se dispõem a fazer o mesmo, porém favorecendo a formação de gargalos, por operarem de modo centralizado sobre um espaço global. Figura 1. Mapeamentos entre espaços métricos e vetoriais. 2.2 Descrição do Método Para se obter as coordenadas de um ponto de rede, são medidos os RTTs dos elementos de um subconjunto de servidores de posicionamento entre si, e deles com o ponto em questão. Os elementos do subconjunto constituem a base de um sistema de coordenadas que possibilita descrever localmente a posição do ponto. Em técnicas como a GNP (Global Network Positioning) [Ng and Zhang 2002], há uma base central, sendo os seus servidores de posicionamento acionados para todos os processos de estimativas de coordenadas, o que favorece a ocorrência de gargalos. Já na técnica Lighthouses [Pias et al. 2004], esse problema é minimizado devido a existência de múltiplas bases locais, que possibilitam um melhor balanceando de carga e tornam o sistema mais confiável (a queda de um servidor não ocasiona uma falha global). A determinação dos componentes da base local (os lighthouses) pode ser feita através de algum processo de seleção apropriado, como os métodos propostos em [Tang and Crovella 2004]. Após determinados os lighthouses, efetuadas as medições e obtidas as coordenadas locais, há que se computar as coordenadas globais. Para isso, associa-se a base local à base de referência global, através de uma matriz de transição, e aplica-se essa matriz às coordenadas locais, obtendo-se as coordenadas globais. A seguir, melhor se esclarece essa descrição. 2.3. Gênese do sistema e transformação das coordenadas locais em globais Para dar início a um sistema de Lighthouses com dimensão k seleciona-se um subconjunto de k +1 pontos de rede; realizam-se medidas de atraso entre eles (RTT’s); e, aplicando-se métodos da Álgebra Linear sobre os dados obtidos nas medições - ortonormalização de Gram-Schmidt e combinações lineares -, computa-se a base de um sistema de coordenadas com dimensão k. Esses pontos passam a ser os primeiros k+1 lighthouses e a base computada passa a ser a base de referência global G. Cabe aqui salientar que o número teórico mínimo de pontos de rede, necessário a construção de um sistema de coordenadas com dimensão k, é k + 1. Porém, na prática, devido às imprecisões das medições dos RTT’s, e às características dos grafos (Internet routing) que se tenta mapear em espaços euclideanos, utilizam-se k+1+c pontos. Sendo c uma constante que representa pontos de referência adicionais, com vistas à melhoria da precisão das coordenadas obtidas. 2.4. Um exemplo para ilustrar o método Suponha um sistema com seis lighthouses, n1, n2, n3, n4, n5 e n6, e um ponto de rede, n7, do qual se pretende obter as coordenadas (ver Figura 2). Considerando que o subconjunto de lighthouses escolhido para formar a base local é constituído por n4, n5 e n6, são esses os servidores que irão realizar as medições locais, entre si e com n7. Aplicando-se o método da orto-normalização de Gram-Schmidt, e realizando algumas combinações lineares sobre os dados obtidos nas medições, podem-se computar as coordenadas locais de n4, n5, n6 e n7 (ver Figura 3). De posse das coordenadas globais e lo- cais de n4, n5 e n6, obtém-se a matriz de transição entre esses dois sistemas de coordenadas. Por fim, utilizando essa matriz de transição, calculam-se as coordenadas globais de n7. Salienta-se que para o cálculo das coordenadas globais de n7 não é necessária a realização de qualquer outra medição. Figura 2. Lighthouses Figura 3. Bases locais 3. Arquitetura A ferramenta de medições, projetada com o objetivo de oferecer serviços de estimativa de atrasos, pode ser acionada de qualquer ponto da rede (host cliente) através das seguintes duas primitivas: • posição(k): retorna as coordenadas do ponto de rede k (um cliente ou servidor); • distancia(i,j): retorna a distância entre os pontos de rede i e j. A arquitetura funcional da ferramenta corresponde a um sistema distribuído executando em computadores denominados Servidores de Posicionamento - SPs. Cada SP é capaz de realizar as seguintes ações, implementadas em módulos específicos: • Cálculo da matriz de distâncias de um subconjunto de SPs: tem como objetivo inferir a matriz de distâncias entre os elementos de um subconjunto de SPs, a partir da qual será obtida a base necessária ao cálculo das coordenadas locais de um ponto de rede; • Obtenção da distância até um ponto: tem como objetivo medir o RTT até um ponto de rede especificado, com o objetivo de completar as informações necessárias ao cálculo das coordenadas do tal ponto; • Cálculo das coordenadas de um ponto: tem como objetivo computar as coordenadas de um ponto, a partir da matriz de distâncias entre os elementos de um subconjunto de SPs (obtida no módulo descrito no primeiro item), e das distâncias entre esses SPs e o ponto de rede em questão (obtidas nos módulos descritos no item anterior); • Cálculo de distâncias entre dois pontos: tem como objetivo calcular a distância entre dois pontos de rede, a partir das coordenadas desses pontos (obtidas no módulo descrito no item anterior). Quando um host cliente h necessita as coordenadas de um ponto de rede k (um servidor ou outro cliente) ele questiona um servidor SPq acionando a primitiva posição(k); se necessita a distância entre dois pontos i e j, aciona a primitiva distancia(i, j). Ao receber uma solicitação desses tipos o SPq infere a matriz de distâncias entre os elementos de um subconjunto de SPs por ele escolhido, encaminha pedidos aos servidores desse subconjunto para que eles obtenham as suas distâncias até os pontos k, ou i e j, conforme a primitiva solicitada, e as informem a ele. Ao final dessa rodada, o SPq possui todas as informações necessárias ao cálculo das coordenadas de k ou a distância entre i e j. São elas a matriz de distâncias entre servidores adequados; e as distâncias entre esses servidores e o(s) ponto(s) em questão. A partir disso, calcula a informação solicitada e a entrega ao host h. Esse funcionamento encontra-se ilustrado, através do fluxo de mensagens do sistema, na Figura 4. Ali, exemplifica-se o cômputo da distância entre os hosts i e j solicitada por um cliente h ao servidor de posicionamento SPq. Há também que se evidenciar que todos os SPs necessitam conhecer as suas coordenadas globais, para possibilitar a obtenção das matrizes de transição, conforme descrito na seção 2. Para isso, há que prever uma fase de inicialização/reinicialização do sistema, na qual, a partir de um subconjunto de quatro SPs, escolhido para constituir a base global, todos os demais calculem as suas coordenadas globais. Por fim, salienta-se que, como a característica distância possui a propriedade de simetria - distancia(i, j) = distancia(j, i), as medições realizadas para obtê-las também devem ser, motivo pelo qual se admite que RTT’s são medidas simétricas. Figura 4. Arquitetura de referência 4. Resultados Preliminares Experimentos para avaliar preliminarmente a ferramenta Euclidiana encontram-se em andamento. Com três medidores posicionados em hosts do PlanetLab, em Berkeley (planet6.berkeley.intelresearch.net) na USP (planetlab2.larc.usp.br) e em Cornell (planetlab6.cs.cornell.edu), foram estimados os RTTs entre o host www.ncc.furg.br e vinte e sete hosts espalhados pelo mundo, utilizando o programa ping. Repetiram-se em três momentos esses experimentos e 81 valores medidos e estimados foram então obtidos. Foram computados os erros percentuais ocorridos entre as estimativas e as medições, gerando o gráfico da Figura 5, que ilustra a Distribuição de Probabilidades Cumulativas obtida para os erros ocorridos. Figura 5. Distribuição de Probabilidades Ali está mostrado, por exemplo, que 25% dos valores estimados apresentam um erro menor do que 12%, 50% dos valores estimados apresentam erro menor do que 26% e 75% dos valores estimados um erro menor do que 39%. Talvez esses erros possam ser diminuídos se melhores escolhas para posicionamento dos medidores forem realizadas. Tais escolhas estão sendo estudadas. 5. Conclusões e Trabalhos Futuros Foram descritas neste artigo as bases científicas e tecnológicas; e a arquitetura de referência da Euclideana, ferramenta capaz de obter estimativas de atraso entre hosts de uma rede de computadores. Tal ferramenta realiza essas estimativas associando a topologia da rede à um espaço euclideano, onde a medida de distância nesse espaço corresponde ao RTT entre pontos da rede. Também foi apresentado um exemplo capaz de ilustrar o funcionamento das idéias propostas. Apesar de constituir-se sob a forma de um protótipo, a ferramenta construída é capaz de demonstrar as funcionalidades da proposta. Devido a dificuldades encontradas para instalar o sistema em uma rede concreta, construiu-se um experimento no qual o protótipo foi instalado sobre alguns hosts geograficamente distribuídos da Internet, e funciona de modo estático. Ou seja, os servidores de posicionamento são fixos e as solicitações de serviços de medição de atraso devem ser encaminhadas a certo servidor. Em http://www.ncc.furg.br/euclideana podem ser encontradas maiores informações sobre o uso da ferramenta. Por fim, registra-se que alguns aspectos de projeto associados à ferramenta que ainda necessitam ser ajustados, mas somente poderão ser resolvidos na medida em que o sistema for implementado numa rede concreta. São eles: quais os SPs que deverão participar da fase de inicialização/reinicialização do sistema, e quando ele deve ser reinicializado; quais os SPs que devem ser acionados pelo Servidor de Posicionamento que receber uma consulta; e a pertinência da construção de caches nos servidores com o objetivo de aumentar a eficiência dos processos de estimativa, através de buscas diretamente realizadas sobre resultados obtidos em consultas anteriores. Antes de instalar o sistema na Rede Giga [RNP 2004], conforme previsto no Projeto GigaIQoM [RNP 2005], se pretende realizar avaliações sobre os resultados gerados pela ferramenta, utilizando o PlanetLab como testbed [Peterson et al. 2005]. Ainda a título de trabalhos futuros, se pretende avaliar a imprecisão das coordenadas e das distâncias calculadas, e como essas imprecisões serão informadas às aplicações. Para isso, os resultados apresentados em [Ledlie et al. 2007] deverão inspirar a solução aqui buscada. REFERÊNCIAS [1]Costa, M., Castro, M., Rowstron, A., and Key, P. (2004). Pic: Practical internet coordinates for distance estimation. [2]Dabek, F., Cox, R., Kaashoek, F., and Morris, R. (2004). Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM ’04 Conference, Portland, Oregon. [3]Ledlie, J., Gardner, P., and Seltzer, M. (2007). Network coordinates in the wild. In Proceedings of NSDI 2007. [4]Ledlie, J., Pietzuch, P., and Seltzer, M. Stable and accurate network coordinates. In Proceedings of ICDCS 2006. [5]Ng, T. and Zhang, H. (2002). Predicting internet network distance with coordinate-based approaches. In IEEE Infocom 02. [6]Peterson, L., Pai, V., Spring, N., and Bavier, A. (2005). Using planetlab for network research: Myths, realities, and best practices. In PlanetLab Design Note (PDN-05- 028). [7]Pias, M., Crowcroft, J., Wilbur, S., Harris, T., and Bhati, S. (2004). Lighthouses for scalable distributed location. In Proc of IPTPS’03. RNP (2004). www.rnp.br/pd/giga/. [8]RNP (2005). www.rnp.br/ arquivo/gt/2004/proposta gt medicoes.pdf. [9]Tang, L. and Crovella, M. (2003). Virtual landmarks for the internet. In IMC ’03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pages 143– 152, New York, NY, USA. ACM Press [10]Tang, L. and Crovella, M. (2004). Geometric exploration of the landmark selection problem. In PAM, pages 63–72.