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.