MAC499 - Trabalho de Formatura Supervisionado

Suporte para Aplicações com Conhecimento da Rede através de Pesquisa por Pacotes

Aluno: Daniel de Angelis Cordeiro
Orientador: Prof. Alfredo Goldman vel Lejbman
{danielc,gold}@ime.usp.br

Projeto de Iniciação Científica1

Resumo

O objetivo deste trabalho é pesquisar formas de obtenção do estado da rede de forma dinâmica, isto é, queremos obter as características do ambiente de rede onde o sistema se encontra. O foco desta pesquisa são ambientes de grade computacional (grid computing) que são, de forma simplificada, um conjunto de recursos computacionais (aglomerados de PCs e supercomputadores) interconectados.
A análise de sistemas de grade computacional tradicionais nos mostra que a rede não é considerada um recurso para as tarefas da grade. Descobrimos também que sistemas de sondagem especializados produzem resultados mais precisos, mas não são adequados para o ambiente de grade computacional que é formado, tipicamente, por um sistema heterogêneo.
Sistemas de sondagem por pacotes resolvem o problema da heterogeneidade da rede, mas esbarram no problema dos equipamentos de rede que não dão suporte a camada três (TCP/IP) de rede. Podemos utilizar o protocolo ICMP para resolver o problema, mas equipamentos de rede tratam pacotes ICMP e IP de maneiras diferentes, o que produz um resultado que não é preciso.

Sumário

        Parte I:  Projeto de Iniciação Científica
1  Introdução
2  Objetivo
3  Trabalhos Relacionados
    3.1  Sistemas de Grade Computacionais
        3.1.1  Legion
        3.1.2  OurGrid
    3.2  Sistemas Especializados
        3.2.1  SNMP
        3.2.2  ReMoS
    3.3  Pesquisa por Pacotes
        3.3.1  Pesquisa Ativa e Passiva
        3.3.2  Atraso
        3.3.3  Dispersão de Pacotes
        3.3.4  Pacotes de Tamanhos Variados
        3.3.5  Roteamento e Topologia
4  Ferramentas de Pesquisa por Pacotes
    4.1  pathchar
    4.2  netperf
    4.3  netest
    4.4  nettimer
    4.5  igi
5  Atividades Realizadas
6  Conclusão

        Parte II  Experiência Pessoal
7  Desafios e Frustrações
8  Disciplinas do BCC mais relevantes
9  Integração com os membros do InteGrade
10  Trabalhos futuros
11  Conclusões finais
12  Agradecimentos

Parte I
Projeto de Iniciação Científica


1  Introdução

Atualmente, nota-se um aumento no interesse [6] por grades computacionais que são, de forma simplificada, um conjunto de recursos computacionais (aglomerados de PCs e supercomputadores) interconectados. A possibilidade de tal infra-estrutura nos leva a ampliar os horizontes para novos tipos de aplicações de alto desempenho que utilizem recursos da grade de forma eficiente. Para isso, é necessário possibilitar a programação paralela no ambiente distribuído de uma grade computacional.
O projeto InteGrade [1], que está sendo desenvolvido no Instituto de Matemática e Estatística da USP, e no qual este trabalho está inserido, visa construir essa infra-estrutura genérica de middleware que permitirá a criação de uma grade computacional que integrará os recursos computacionais disponíveis em máquinas ociosas em um ambiente de execução unificado.
Para que essa infra-estrutura fornecida pelo InteGrade seja apropriada para programação paralela é necessário que a integração dos recursos computacionais disponíveis leve em conta o ambiente de rede disponível, de forma a minimizar o efeito da troca de mensagens realizadas no desempenho das aplicações paralelas. É necessário, portanto, que o InteGrade seja uma aplicação que consiga obter, de forma dinâmica, informações sobre a rede em que se encontra.
O restante deste trabalho é dividido como segue. A seção 2 explicita os objetivos deste trabalho. A seção 3 descreve os trabalhos relacionados estudados durante esta iniciação científica, enquanto que as atividades realizadas são descritas na seção 5. As conclusões são discutidas na seção 6.

2   Objetivo

O objetivo deste trabalho é pesquisar formas de obtenção do estado da rede de forma dinâmica. Queremos poder estimar as características da rede onde se encontram os recursos computacionais que serão integrados pelo InteGrade. Para tanto, é necessário desenvolver um método de inferência dos recursos da rede de forma não intrusiva, ou seja, que consuma pouca banda e que não necessite de alterações de baixo nível (alterações no sistema operacional, por exemplo) nos nós que compõem a grade.

3   Trabalhos Relacionados

Há três categorias de sistemas relacionados a este trabalho. Em um âmbito mais geral, todos os sistemas de grade computacional conhecidos estão relacionados com o projeto InteGrade e, conseqüentemente, com este trabalho. No âmbito de sondagem de rede, podemos classificar os sistemas existentes em dois tipos: sistemas especializados, ou seja, sistemas que dependem de características específicas de rede em que se encontram e sistemas de pesquisa de rede por pacotes, isto é, que não necessitam de nenhum conhecimento sobre o tipo de rede em que se encontram.
Os sistemas de grade computacionais estudados serão descritos na seção 3.1, os sistemas especializados de sondagem estudados serão descritos em 3.2 e os sistemas de pesquisa por pacotes estudados serão descritos na seção 3.3.

3.1   Sistemas de Grade Computacionais

O padrão Grade [8] define uma grade computacional como um middleware que integra recursos distribuídos de modo a criar um ambiente de execução unificado para as aplicações. Uma grade computacional permite o compartilhamento de recursos de hardware e software em sistemas distribuídos e heterogêneos, viabilizando, assim, a execução de aplicações que fazem uso intensivo de computação.
Diversos sistemas de grade computacional estão sendo desenvolvidos. Como exemplos, podemos citar os sistemas Globus, Legion, Condor, BOINC e os brasileiros OurGrid, Brazilian National Computation Grid, GridRio e InteGrade, entre tantos outros projetos. Dois sistemas de grade computacional foram estudados neste trabalho e serão descritos a seguir: Legion e OurGrid.

3.1.1  Legion

Legion [5] é um sistema de grade computacional que foi desenvolvido pela Universidade de Virginia. Um dos pioneiros em computação em grade, o desenvolvimento do Legion começou em 1993. Em 2001, seus idealizadores fundaram a Avaki, uma empresa que atualmente desenvolve e comercializa sistemas que utilizam a tecnologia do Legion.
O Legion foi desenvolvido utilizando-se o paradigma de orientação a objetos. Em Legion, todos os elementos da Grade são representados por objetos, sejam eles dados ou objetos reais, tais como microscópios, telescópios e outros equipamentos. Alguns dos objetivos da arquitetura são os seguintes:
O Legion se destaca pela sua preocupação com o suporte à aplicações paralelas. O Legion possui uma implementação das bibliotecas MPI (Message Passing Interface) e PVM (Parallel Virtual Machine). Para utilizar um programa escrito em MPI ou PVM no Legion basta recompilá-lo utilizando as bibliotecas fornecidas pelo Legion. Isso permite que a migração da infra-estrutura antiga para a infra-estrutura do Legion seja praticamente instantânea.
Além das bibliotecas, Legion fornece suporte nativo a algumas linguagens de programação paralela. É possível utilizar as linguagens MPL (Mentat Programming Language, uma extensão de C++ para programação paralela), BFS (Basic Fortran Support) e Java.
Por fim, aplicações legadas que não utilizem nenhuma das bibliotecas ou linguagens acima podem ser encapsuladas dentro de objetos Legion. Basta o usuário registrar o programa legado com o comando legion_register_program e o sistema constrói um objeto Legion que encapsula o programa legado e, automaticamente, ele se torna elegível para ser executado pelo sistema. Isso garante que qualquer programa possa ser executado no ambiente do Legion. Se o programa realizar algum tipo de comunicação, basta que o programador escreva um adaptador para o programa legado que converta as chamadas a biblioteca de comunicação à chamadas a métodos de comunicação do Legion.

3.1.2  OurGrid

OurGrid [4] é um projeto de grade computacional desenvolvido em conjunto pela Universidade Federal de Campina Grande e Hewlett-Packard (HP). O objetivo do OurGrid é pesquisar e desenvolver soluções para uso e gerenciamento de grades computacionais. O projeto OurGrid é fundamentado no projeto MyGrid, desenvolvido também na Universidade Federal de Campina Grande, que propôs e desenvolveu uma implementação de um sistema de grade computacional.
O MyGrid é um sistema de grade computacional para aplicações do tipo Bag-of-Tasks, ou seja, para aplicações que sejam compostas por uma seqüência de tarefas independentes entre si. Um dos objetivos do projeto MyGrid é a simplicidade. Seus idealizadores acreditam que um sistema de grade que seja simples de usar é o que os desenvolvedores de aplicações de alto desempenho precisam hoje. Essa simplicidade se reflete tanto na arquitetura do sistema quanto em seu uso.
Para utilizar a infra-estrutura do MyGrid, o desenvolvedor necessita apenas informar quais as informações de entrada de cada tarefa e onde as informações de saída serão armazenadas. Não é necessário utilizar nenhuma biblioteca específica nem se preocupar com questões como o escalonamento das tarefas ou configuração do sistema de grade. Surpreendentemente, não é necessário instalar nenhum programa nos computadores que formarão a rede. É necessário apenas que o usuário tenha algum tipo de acesso remoto como, por exemplo, via SSH (Secure SHell), aos outros nós que compõe a grade.
A arquitetura do MyGrid também é muito simples. Há apenas um escalonador centralizado para todos os nós que compõem a grade. Toda tarefa a ser executada na grade deve ser enviada para este escalonador que, após analisar a carga de trabalho em todos os nós da grade, decidirá qual nó executará cada tarefa. Está prevista na arquitetura do MyGrid a capacidade de interoperabilidade com outros sistemas de grade computacional. Um protótipo de integração com o sistema Globus já está sendo desenvolvido pela equipe do MyGrid.
O sistema Legion permite a execução de programas paralelos que necessitem comunicação entre nós. O OurGrid só permite que problemas embaraçosamente paralelizáveis sejam executados, devido ao modelo de aplicações Bag-of-Tasks utilizado. Porém, o sistema Legion requer que o usuário especifique os nós em que as tarefas serão executadas, ao contrário do OurGrid, que possui um escalonador que define esses nós dinamicamente. O projeto InteGrade visa fornecer suporte para todos os tipos de programas paralelos, atribuindo cada tarefa a um nó da grade de forma dinâmica. Com o uso de sistemas de sondagem de rede, o sistema de escalonamento de tarefas poderá distribuir as tarefas entre nós próximos, diminuindo os efeitos da degradação de desempenho decorrentes da comunicação entre nós.

3.2   Sistemas Especializados

Chamamos de sistemas de sondagem especializados aqueles que necessitam conhecer alguma característica específica da rede onde o sistema se encontra. Este trabalho analisou dois sistemas de sondagem especializados: SNMP e ReMoS.

3.2.1   SNMP

- O Simple Network Management Protocol [7] (SNMP), foi desenvolvido por volta de 1998 e, desde então, tornou-se o padrão de gerenciamento de redes "de facto" da indústria. O SNMP prima por sua simplicidade e flexibilidade. Implementar um agente SNMP em um produto requer muito pouco código e adicionar novas funcionalidades de gerenciamento de rede às existentes requer pouco esforço. Outra característica que tornou o SNMP popular é que a implementação da camada de gerenciamento é independente da implementação da camada de hardware, o que permite mesclar a implementação de múltiplos fornecedores.
SNMP contém dois tipos de elementos primários: gerentes (managers) e agentes (agents). Os gerentes são as interfaces pelas quais o administrador de rede realiza suas tarefas de gerenciamento. Agentes são entidades que fornecem a interface com o dispositivo que está sendo gerenciado. Bridges, hubs e roteadores são exemplos de dispositivos gerenciáveis pelo SNMP. Estes dispositivos contém o que SNMP denomina de "objetos gerenciáveis". Os objetos gerenciáveis são características que estão relacionadas com a operação do dispositivo, como parâmetros de configuração, estatísticas de desempenho, hardware, etc. Esses objetos são agrupados em banco de dados virtual de informações sobre a rede, chamado MIB (management information base). SNMP permite que gerentes e agentes se comuniquem para permitir o acesso a esses objetos.
Um agente, tipicamente:
Um gerente, tipicamente:
A comunicação entre agentes e gerentes SNMP não é orientada a conexão. Em outras palavras, não há conexão pré-estabelecida entre o agente e o gerente antes da transmissão de dados ser realizada. Em conseqüência disso, SNMP não oferece nenhuma garantia sobre o envio dos dados. A comunicação é realizada utilizando-se UDP (User Datagram Protocol) e IP (Internet Protocol).
A desvantagem de utilizar o SNMP como sistema de obtenção de recursos de rede por um sistema de grade computacional é que nem todos os dispositivos de redes possuem agem como agentes SNMP. Muitas vezes o dispositivo não provê suporte a SNMP ou o administrador do sistema desativou o suporte por motivos de segurança. Isso faz com que SNMP não seja uma opção genérica para sistemas de sondagem de rede.

3.2.2   ReMoS

O Remos [3] (REsource MOnitoring System ou sistema de monitoramento de recursos) foi desenvolvido na Carnegie Mellon University e permite que aplicações obtenham informações relevantes sobre o ambiente de rede onde se encontram.
O Remos possui uma interface que disponibiliza as informações sobre o ambiente de rede de forma independente da tecnologia utilizada pela rede. Dessa forma, aplicações que utilizem o Remos podem se adaptar ao ambiente de execução ainda que este seja composto por redes que utilizem diferentes tecnologias.
As informações disponibilizadas pelo Remos são independentes da tecnologia utilizada. Isso significa que, apesar da aplicação utilizar informações coletadas pelo Remos, essas informações são independentes da tecnologia de rede utilizada. Dessa forma, a mesma aplicação poderá ser executada em uma rede que utilize outra tecnologia sem necessidade de mudanças no código-fonte da aplicação.
Outra característica interessante do Remos é sua capacidade de previsão. Os dados coletados durante a execução do Remos são armazenados para referência futura. Aplicações que utilizam o Remos podem obter informações sobre um estado passado. Por exemplo, é possível obter informações sobre o estado da rede há três horas atrás. O sistema Remos possui uma heurística de predição de estado. Um programa pode pedir para o sistema prever como estará a rede daqui a dez minutos, por exemplo, e o Remos utilizará os dados coletados para realizar a previsão.
Há duas formas de obtenção de dados no Remos. A primeira é uma pesquisa de alto nível, denominada flow-based queries, que permite que consultas sobre largura de banda e latência sejam realizadas. A segunda forma de obtenção de dados são as pesquisas de baixo nível, denominada no Remos por logical network topology, que permitem que pesquisas sobre a topologia de rede sejam realizadas. No Remos, a topologia de rede é representada por um grafo onde os vértices são os nós da rede e as arestas representam os custos de comunicação entre os dois nós interligados pela aresta.
A implementação do Remos utiliza o protocolo de gerenciamento de rede SNMP, descrito na seção 3.2.1.

3.3   Pesquisa por Pacotes

Os sistemas de pesquisa por pacotes (packet-probing) são aqueles que utilizam apenas troca de mensagens para inferir características da rede. Isso possibilita usar o mesmo sistema independentemente da tecnologia de rede utilizada, ao contrário dos sistemas especializados vistos na seção 3.2.
A seguir, apresentaremos diferentes técnicas de pesquisa por pacotes, conforme classificadas por Schoonderwoerd [9].

3.3.1   Pesquisa Ativa e Passiva

As várias técnicas usadas por sistemas de pesquisa por pacotes podem ser separadas em duas categorias: pesquisa ativa e pesquisa passiva. Pesquisa ativa significa que o sistema enviará, ativamente, pacotes de sondagem pela rede. Já os sistemas de pesquisa passiva, monitoram o tráfego de rede, sem nenhum tipo de interferência.
Sistemas de pesquisa ativa podem ser tanto de "apenas-envio" (one-way) ou "envio-e-resposta" (two-way). Programas como ping são do tipo de pesquisa de apenas-envio. O ping envia uma mensagem e espera por uma resposta automática, utilizando ICMP e UDP ou TCP. Sistemas de envio-e-resposta utilizam uma arquitetura cliente-servidor. O cliente envia um pacote de sondagem ao servidor, que executa alguns cálculos e responde ou apenas reenvia os dados recebidos ao cliente.
Pesquisa passiva é considerado um método menos confiável do que pesquisa ativa. Alguns pesquisadores afirmam que não é possível extrair nenhum dado útil do monitoramento da rede. Entretanto, há diversos esforços de utilização de pesquisa passiva.

3.3.2   Atraso

O atraso de envio (one-way delay) é o tempo necessário para um pacote viajar de sua origem ao seu destino, utilizando um timestamp e relógios sincronizados. O tempo de envio e resposta (round-trip time) é medido enviando-se um pacote de tamanho pequeno a um servidor e contando o tempo necessário para que a resposta chegue.

3.3.3   Dispersão de Pacotes

Sistemas que utilizam dispersão de pacotes funcionam do seguinte modo. Utilizando-se pacotes do tipo UDP ou ICMP ECHO, seqüências de pacotes são enviados consecutivamentes para o nó de destino, que reenvia os pacotes de volta. Ao passar por um link de menor capacidade, os pacotes serão enfileirados. Após este link, os pacotes terão um espaço entre eles devido ao enfileiramento. O espaço ou dispersão entre os pacotes é definido como o tempo entre a chegada do último bit do primeiro pacote e o tempo da chegada do último bit do segundo pacote. Após passar pelo link de menor capacidade, o tamanho da dispersão, teoricamente, não ficará maior. A dispersão média entre os pacotes da seqüência é medido e a capacidade C, em bytes por segundo, é dado pela fórmula:
C = P/(tdispersao),
onde P é o tamanho do pacote, em bytes, e tdipersao é a média do tempo de dispersão da seqüência, em segundos. A capacidade C é, então, usada como estimativa para a capacidade do link.
A existência de pacotes concomitantes aos pacotes da seqüência, isto é, a existência de tráfego no nó de rede que não seja gerado pelo sistema de pesquisa, faz com que a estimativa de capacidade fique menos acurada.

3.3.4  Pacotes de Tamanhos Variados

A técnica de pacotes de tamanhos variados foi utilizada pela primeira vez na ferramenta pathchar [10]. A idéia básica é que a ferramenta mande um pacote onde o campo TTL (time-to-live) do cabeçalho IP do pacote é definido com um valor específico. Cada dispositivo da camada três de rede (TCP/IP) irá decrementar o valor do TTL em um. Quando o valor de TTL atingir zero, o dispositivo enviará uma mensagem de erro do tipo ICMP TTL-exceeded para o remetente do pacote. Ao receber essa mensagem de erro, a ferramenta pode estimar o tempo de envio e resposta. O tempo de envio e resposta é medido várias vezes para diferentes tamanhos de pacote. Com uma certa dose de sorte, alguns pacotes de resposta chegarão de volta ao remetente sem serem enfileirados nenhuma vez por nenhum dispositivo de rede. Estes representarão os menores tempos de envio e resposta para determinado tamanho de pacote. Os tempos obtidos permitirão que seja estimada a largura de banda do link de menor capacidade.

3.3.5   Roteamento e Topologia

Esta metodologia é a mais antiga e utilizada de todas. Desde 1988 a ferramenta traceroute, criada por Van Jacobson, é utilizada para descobrir por quais nós um pacote passa para chegar a um nó destino em particular. Desta forma, uma pequena parte da topologia de rede se torna visível. Porém, nem todos os pacotes necessariamente seguem um mesmo caminho. Todos as ferramentas que realizam medição por link, isto é, medem as características de rede levando em consideração todo o caminho que os pacotes percorrem, utilizam a mesma técnica. Descobrem todos os dispositivos de rede nível três, enviam pacotes de rede com o campo TTL modificado e esperam os pacotes com as mensagens de erros chegarem.
Devido a diferenciação que os equipamentos de roteamento de rede fazem entre pacotes ICMP e IP, os resultados produzidos por esta técnica não são confiáveis. Entretanto, nota-se que, atualmente, a utilização de outras técnicas de sondagem em conjunto com técnicas de roteamento e topologia estão se tornando uma tendência.
Pode-se notar que os sistemas de grade computacionais tradicionais não consideram as características de rede como um recurso do sistema de grade. Apenas assume-se que a rede existe, e que todos os nós são alcançáveis a partir de qualquer outro, ou seja, o grafo que representa a topologia e a comunicação entre os nós é completo. Nota-se, também, que sistemas de sondagem especializados produzem resultados mais precisos do que os de pesquisa por pacotes, mas necessitam de informações sobre a tecnologia de rede utilizada, o que nem sempre está disponível em ambientes heterogêneos como a Internet. Por fim, temos que sistemas de pesquisa por pacotes produzem estimativas das características do ambiente de rede, mas não modelam bem equipamentos de rede que não operam na camada três de rede (TCP/IP).

4  Ferramentas de Pesquisa por Pacotes

Durante este projeto algumas ferramentas de pesquisa por pacotes foram experimentadas. A seguir, descreveremos as ferramentas pathchar, netperf, nettimer e igi.

4.1  pathchar

Pathchar [10] é uma ferramenta de pesquisa por pacotes idealizada por Van Jacobson, do Lawrence Berkeley Laboratory. O pathchar tenta inferir as características dos links individuais que compõem o caminho entre os dois nós da rede que estão sendo sondados. Para isso, ele mede o tempo de envio-e-resposta para cada nó que compõe o caminho entre os dois nós sondados, utilizando a seguinte fórmula:
tempo de envio e resposta = (latência + tamanho do pacote / banda disponível) + latência,
Onde o tempo de envio e resposta é medido pela ferramenta e a latência pode ser estimada enviando pacotes de tamanho cada vez menor. Ao aplicar essa fórmula para todos os nós que compõe a rede, pathchar consegue determinar qual a largura de banda máxima entre os dois nós sondados.
Para encontrar os nós que compõem o caminho, a ferramenta utiliza o mesmo princípio utilizado pelo traceroute, também idealizado por Jacobson. Um pacote IP é montado de forma que o campo Time-to-Live (TTL) seja pequeno. Cada nó que compõe o caminho, ao receber o pacote, decrementa 1 do valor de TTL e, se TTL chegar a zero, envia uma mensagem de erro ICMP para o remetente do pacote. Se TTL não for zero, envia o pacote para o próximo nó que compõe o caminho.
O pathchar é uma das mais antigas ferramentas de pesquisa por pacotes. Ela foi apresentada no Mathematical Sciences Research Institute em abril de 1997.

4.2  netperf

Netperf [13] é uma ferramenta desenvolvida inicialmente pela Hewlett-Packard (HP) e que posteriormente teve seu código disponibilizado para a seus usuários. O netperf pode ser usado para medir vários aspectos que influenciam o desempenho de redes de computadores. Seu foco primário é na transferência de grandes quantidades de dados e na medição de desempenho de envio-e-resposta utilizando tanto TCP e UDP.
O netperf mede a largura de banda total do link. Durante 10 segundos, a ferramenta mede o tempo gasto para enviar pacotes de tamanhos fixos entre os dois nós que estão sendo sondados. Medindo o tempo gasto e sabendo-se o tamanho dos pacotes enviados, é possível para a ferramenta descobrir qual a banda total disponível.
Das ferramentas analisadas, netperf é a que produz resultados mais precisos. Por outro lado, é a ferramenta que mais gera tráfego durante sua utilização.

4.3  netest

O netest [12] foi desenvolvido para fornecer informações sobre todos os nós que compõem um caminho entre dois nós quaisquer, de forma não intrusiva.
Netest informa a largura de banda total entre os dois nós sondados e exibe diversas informações sobre a configuração das conexões TCP utilizadas entre os nós. Entre essas informações, destaca-se a largura da janela dos pacotes TCP e algumas recomendações para a configuração do sistema de TCP.
Netest é um sistema de pesquisa ativo que utiliza uma metodologia que mescla atraso, visto na seção 3.3.2 e pesquisa por roteamento e topologia, visto na seção 3.3.5.

4.4  nettimer

A ferramenta nettimer [15] propõe uma sondagem que seja menos intrusiva possível, ou seja, que consuma pouca banda, a fim de não degradar o desempenho das aplicações que já estão rodando no nó da rede que está sendo testado. A ferramenta nettimer foi uma das primeiras ferramentas a tentar sondar apenas o link que provoca gargalo, ao invés de tentar medir a largura da banda de todos os links.
Nettimer utiliza duas abordagens para a realização da sondagem. A primeira utiliza um método que baseia-se no conceito de pesquisa passiva (veja seção 3.3.1). A equipe do nettimer desenvolveu uma biblioteca chamada libdpcap que nada mais é do que uma biblioteca para captura distribuída de pacotes. A biblioteca utilizou como base a conhecida biblioteca de captura de pacotes libpcap, que não é distribuída. Com as informações geradas pela libdpcap, o nettimer é capaz de determinar a largura da banda do menor link entre dois nós. Mas, como citado na seção 3.3.1, metodologias baseadas em pesquisa passiva não produzem resultados muito acurados.
A segunda utiliza pesquisa ativa, utilizando a metodologia de atraso, visto na seção 3.3.2.

4.5  igi

O método IGI [14] (Initial Gap Increasing) foi desenvolvido por Peter Steenkiste e Ningning Hu na Carnegie Mellon University. O IGI utiliza pesquisa ativa baseada na metodologia de dispersão de pacotes (ver seção 3.3.3).
O algoritmo IGI envia uma seqüência de pacotes consecutivos. O tempo de envio entre um pacote e outro é crescente durante a execução do algoritmo. A ferramenta, então, monitora a diferença entre a média dos tempos de chegada entre o primeiro e o segundo pacote e o intervalo de tempo entre o envio dos pacotes. Quando esta diferença for próxima de zero, a ferramenta considera que este é o melhor tempo que um pacote consegue realizar entre os dois nós e, conseqüentemente, pode inferir a largura de banda.
Das ferramentas analisadas, esta foi a que apresentou os melhores resultados e o melhor desempenho em ambientes de rede de alta velocidade.
A tabela 1 resume as principais características das ferramentas analisadas.
Ferramenta Pesquisa Metodologia Protocolo Características medidas

pathchar ativa roteamento e topologia UDP e ICMP banda total, latência
netperf ativa atraso TCP e UDP banda total, latência
netest ativa atraso UDP banda total
nettimer ativa e passiva dispersão de pacotes TCP banda total
igi ativa dispersão de pacotes TCP e UDP banda disponível
Tabela 1: Características principais das ferramentas analisadas

5   Atividades Realizadas

As atividades realizadas, em ordem cronológica, foram:

6   Conclusão

Neste estudo, analisamos como alguns sistemas de grade computacional tratam as limitações de desempenho que as redes oferecem. Pesquisamos, também, diversos métodos de sondagem de rede que permitissem que os recursos computacionais disponíveis para sistemas conscientes da rede pudessem obter informações sobre o ambiente de rede de forma dinâmica.
Os sistemas de grade tradicionais não consideram as características de rede como, por exemplo, largura de banda disponível, um recurso do sistema de grade computacional. Informações desta natureza são fundamentais para aplicações paralelas de alto desempenho. No futuro, algoritmos de escalonamento de tarefas [2] farão uso destas informações para minimizar a degradação de desempenho causada pela comunicação feita entre nós da grade. Entre os projetos de grade computacional que tratarão as características de rede como recursos, podemos citar o projeto Globus e o InteGrade.
A pesquisa sobre métodos de sondagem de rede nos mostrou que sistemas especializados normalmente produzem resultados mais precisos. Porém, é necessário que o sistema conheça com antecedência qual o tipo de tecnologia de rede utilizada entre os nós que participam da rede. Essa abordagem não é adequada para grades computacionais, onde o ambiente de rede computacional é heterogêneo e dinâmico, uma vez que qualquer computador interligado a Internet pode começar a participar da grade ou sair dela.
Os métodos de pesquisa por pacotes, em sua maioria, não modelam corretamente os diferentes equipamentos de rede nem a utilização da rede por outros aplicativos. Equipamentos que operam apenas no nível dois da camada de rede, como alguns roteadores, não são percebidos por métodos que utilizam apenas pacotes IP. Métodos que utilizam ICMP detectam esses equipamentos, porém mensagens ICMP são tratados com menor prioridade do que mensagens IP e, portanto, levam a resultados menos precisos. Certas especificidades do sistema operacional e do dispositivo de rede como, por exemplo, o modo como os pacotes são enfileirados no dispositivo de rede se a conexão física estiver sendo usada, deveriam ser considerados por estes métodos para produzir um resultado mais preciso. Mas isso tornaria inviável a criação de um sistema genérico que seja independente da tecnologia utilizada.
No ambiente de grade computacional, a escolha do método de pesquisa de pacote deve ser cuidadosa. O método deve ser rápido e não intrusivo, ou seja, o método não pode degradar o desempenho da comunicação de rede das aplicações que estão sendo executadas nos nós da grade. O sistema deve assegurar, também, que um mesmo nó não participe de duas sondagens em paralelo, pois isso resultaria em resultados enviesados.

Parte II
Experiência Pessoal


A segunda parte desta monografia trata de questões relacionadas a experiência obtida com minha participação no projeto InteGrade e com a realização da pesquisa de métodos de obtenção dinâmicos do estado da rede, relatada na parte I deste trabalho.

7  Desafios e Frustrações

Todos os desafios enfrentados durante a realização deste projeto estão relacionados ao fato de que as pesquisas na área de sondagem de rede são ainda muito recentes e imaturas.
O primeiro desafio foi fazer um mapa desta área de pesquisa. Nós, em um primeiro momento, não conhecíamos nenhum trabalho relacionado a sondagem de redes a não ser o projeto ReMoS, descrito na seção 3.2.2. O estudo do ReMoS nos levou ao estudo do SNMP e à primeira ferramenta de pesquisa por pacote, o pathchar. A partir do artigo [10], realizamos uma pesquisa recursiva nas referências de cada artigo que encontrávamos. Assim, conseguimos obter uma idéia das linhas de pesquisa desta área.
O segundo grande desafio foi conseguir mesclar as informações que obtia lendo cada um dos trabalhos que encontramos. Como o assunto é relativamente novo, ainda não há uma nomenclatura bem definida e cada artigo define os mesmos conceitos utilizando nomes diferentes ou utiliza definições similares, mas não iguais. Isso me atrapalhou bastante no começo, mas depois fui me acostumando. Mais tarde, quando li a tese [9], percebi que não tinha sido o único a ter esse tipo de dificuldade. O primeiro capítulo da tese é uma tentativa de formalização e padronização da nomenclatura utilizada nos artigos sobre pesquisa por pacotes.
A única frustração deste trabalho foi não conseguir encontrar uma ferramenta que consiga resolver os problemas de sondagem de rede para ambientes de grade computacional. Mas fico satisfeito em saber que este trabalho contribui com informações para que esta escolha seja a melhor possível.

8  Disciplinas do BCC mais relevantes

As disciplinas que cursei no BCC que foram mais relevantes para este trabalho foram:
Não posso deixar de citar minha experiência como administrador da Rede GNU/Linux, dos alunos de graduação, no período de janeiro de 2001 à março de 2003. Apesar de ter sido uma tarefa extra-curricular, foi muito importante para o aprendizado de diversos conceitos referentes às redes de computadores que muito me ajudaram durante este projeto.

9  Integração com os membros do InteGrade

A interação com os outros membros do InteGrade foi excelente.
Os membros do projeto InteGrade (atualmente composto por cerca de 4 professores, 3 alunos de doutorado, 6 alunos de mestrado e 3 alunos de graduação) se reúnem duas vezes por mês para que cada um possa relatar o andamento de seus projetos de pesquisa. Durante os relatos, muitas sugestões e críticas eram tecidas para todos os alunos participantes. As reuniões do projeto permitem que todos os alunos acompanhem o andamento de todos os trabalhos que compõem o projeto e permite que cada aluno possa ajudar o outro a realizar seus trabalhos. As sugestões e cobranças que recebi durante estas reuniões me ajudaram muito durante todo o meu trabalho.
Além das reuniões com todos os integrantes do projeto, haviam as reuniões em que participavam apenas eu, meu orientador e o aluno de mestrado Alex Pires de Camargo. Nestas reuniões discutíamos problemas de caráter técnico mais específicos dos que os discutidos nas reuniões do InteGrade. Essa aproximação entre meu projeto e a pesquisa realizada pelo Alex, proporcionada pelo meu orientador, foi benéfica para ambos. Procuramos nos ajudar discutindo idéias e fazendo novas sugestões para ambos os projetos. Além disso, o contato com um projeto de mestrado me ajudou a tomar a decisão de continuar meus estudos no IME, fazendo mestrado.

10  Trabalhos futuros

Para que a pesquisa em sondagem de rede seja completa, ainda há muito trabalho a ser feito.
Primeiramente, os sistemas especializados devem ser melhor estudados. Apesar de serem feitos para ambientes de redes específicos, são muito importantes quando os resultados produzidos pela sondagem de rede devem ser os mais precisos possíveis.
Há inúmeras ferramentas de pesquisa por pacotes que devem ser analisadas também. Este trabalho tentou analisar as ferramentas mais importantes devido as restrições de tempo.
Sondagens baseadas em algoritmos adaptativos também poderiam ser analisadas. Programas de transmissão de vídeo digital como RealPlayer ou Windows Media Player utilizam esses algoritmos para determinar a qualidade da conexão. Este trabalho não analisou nenhum algoritmo deste tipo.

11  Conclusões finais

Esta iniciação científica foi um excelente modo de compreender o que é ser um pesquisador e quais os desafios que isto acarreta. Foi, também, uma boa forma de entrar em contato com as pesquisas em grades computacionais que é uma área promissora e excitante, em temos de pesquisa.
Além disso, este projeto me permitiu aplicar conceitos distintos, aprendidos separadamente durante o curso de bacharelado em computação e durante meu trabalho como administrador da Rede GNU/Linux dos alunos de graduação, em um único trabalho, o que nem sempre podemos fazer durante o decorrer do curso.
Por fim, este trabalho me colocou em contato com as novas pesquisas realizadas na área de sondagem de rede que, sem dúvida, são de uma utilidade inestimável em ambientes de sistemas distribuídos.

12  Agradecimentos

Gostaria de agradecer a diversas pessoas sem as quais este trabalho teria sido muito mais difícil.
Aos meus pais, pelo apoio e compreensão que sempre me deram.
Ao professor Carlos Eduardo Ferreira, pela oportunidade que me deu de entrar em contato com o interessante e trabalhoso ramo de administração de redes.
Aos participantes das listas de usuários dos projetos ReMoS e MyGrid, pela ajuda que me deram e que tornaram possível a experimentação destes sistemas. E a todos os integrantes do projeto InteGrade, por acompanharem de perto este trabalho.
Ao meu orientador, professor Alfredo Goldman, por todas as suas sugestões, críticas e, principalmente, paciência.
Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, pelo financiamento dado através do processo No. 55.2028/02-9.

Referências

[1]
InteGrade: Rumo a um Sistema de Computação em Grade para Aproveitamento de Recursos Ociosos em Máquinas compartilhadas. Andrei Goldchleger, Fabio Kon, Alfredo Goldman Vel Lejbman, Marcelo Finger e Siang Wun Song. Relatório Técnico MAC-IME-USP, outubro 2002.
[2]
A model for parallel job scheduling on dynamical computer grids. Alfredo Goldman e Carlos Queiroz. ACM/IFIP/USENIX International Workshop on Middleware for Grid Computing, Rio de Janeiro, junho 2003.
[3]
ReMoS: A resource monitoring system for network aware applications. Anthony DeWitt, Thomas Gross, Bruce Lowekmap, Nancy Miller, Peter Steenkiste, Jaspal Subhlok e Dean Sutherland. D. Tech. Rep. CMU-CS-97-194, School of Computer Science, Carnegie Mellon University, dezembro 1997.
[4]
Open Grid: A User-Centric Approach for Grid Computing. Walfredo Cirne and Keith Marzullo, Proceedings of the 13th Symposium on Computer Architecture and High Performance Computing, setembro 2001.
[5]
The Core Legion Object Model. Michael Lewis e Andrew Grimshaw, Proceedings of the Fifth IEEE International Symposium on High Performance Distributed Computing, agosto 1996.
[6]
The grid forum http://www.gridforum.org/.
[7]
Simple Network Management Protocol http://www.snmplink.org/.
[8]
Grade: um Padrão Arquitetural. Andrei Goldchleger, Márcio Rodrigo de Freitas Carneiro e Fabio Kon. Relatório Técnico MAC-IME-USP, março 2003.
[9]
Network Performance Measurement Tools - a Comprehensive Comparison. Rody Schoonderwoerd. Tese de mestrado, Vrije Universiteit, Amsterdam, novembro 2002.
[10]
Using pathchar to Estimate Link Characteristics. Allen Downey. In Proceedings of the ACM SIGCOMM, 1999.
[11]
Packet Probing for Network-aware Scientific Applications in Cluster Environments, Sam Storie e Masha Sosonkina. HeteroPar'03.
[12]
Netest: An Tool to Measure the Maximum Burst Size, Available Bandwith and Achievable Throughput. Guojun Jin e Brian Tierney. Disponível em http://www-didc.lbl.gov/NCS/.
[13]
Netperf: A Network Performance Benchmark. Hewlett-Packard Company Information Networks Division. Disponível em http://www.netperf.org/.
[14]
Evaluation and Characterization of Available Bandwidth Probing Techniques. Ningning Hu e Peter Steenkiste. In the IEEE JSAC Special Issue in Internet and WWW Measurement, Mapping, and Modeling, Vol. 21(6), agosto 2003.
[15]
Nettimer: A Tool for Measuring Bottleneck Link Bandwidth. Kevin Lai e Mary Baker. Proceedings of the USENIX Symposium on Internet Technologies and Systems, março 2001.

Nota de rodapé:

1Este projeto é fomentado pelo Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq Proc. No. 55.2028/02-9)

Arquivo gerado automaticamente a partir do TEX por TTH, versão 3.45.
Em 7 dezembro de 2003, 22:40.