UNIVERSIDADE TECNOLOGICA FEDERAL DO PARAN´ A´ … fileLuis Carlos Erpen De Bona HyperBone: Uma Rede Overlay Baseada em Hipercubo Virtual para Computa¸c˜ao Distribu´ıda na Internet

UNIVERSIDADE TECNOLOGICA FEDERAL DO PARANA

Programa de Pos-Graduacao em Engenharia Eletrica e Informatica Industrial

TESE

apresentada a Universidade Tecnologica Federal do Parana

para a obtencao do grau de

DOUTOR EM CIENCIAS

por

LUIS CARLOS ERPEN DE BONA

HYPERBONE: UMA REDE OVERLAY BASEADA EM HIPERCUBO

VIRTUAL PARA COMPUTACAO DISTRIBUIDA NA INTERNET

Banca Examinadora:

Orientador:

Prof. Dr. ELIAS PROCOPIO DUARTE JR. DEP. INFORMATICA, UFPR

Co-orientador:

Profa. Dra. KEIKO VERONICA ONO FONSECA CPGEI, UTFPR

Examinadores:

Prof. Dr. BRUNO SCHULZE LNCC, MCT

Prof. Dr. SERGIO SCHEER CESEC, UFPR

Prof. Dr. CARLOS ALBERTO MAZIERO PPGIA, PUCPR

Prof. Dr. LUIS ALLAN KUNZLE DEP. INFORMATICA, UFPR

Curitiba, Julho de 2006.

Luis Carlos Erpen De Bona

HyperBone: Uma Rede Overlay

Baseada em Hipercubo Virtual para

Computacao Distribuıda na Internet

Tese submetida ao Programa de Pos-Graduacao em

Engenharia Eletrica e Informatica Industrial da Uni-

versidade Tecnologica Federal do Parana como requi-

sito parcial para a obtencao do grau de Doutor em

Ciencias.

Orientador: Prof. Dr. Elias P. Duarte Jr.

Co-orientadora: Profa. Dra. Keiko V. O. Fonseca.

CURITIBA

2006

Dedico esta tese,

A memoria de meu pai, Luiz De Bona Neto.

Agradecimentos

Ao escrever estes agradecimentos, busquei lembrar de todos que de alguma maneira

estiveram presentes e foram decisivos para que esta tese existisse. Meu primeiro agrade-

cimento e para minha famılia, em especial meus pais, Adelia e Luiz (in memoriam), e

meu irmao Marco, que desde sempre nao mediram esforcos para oferecer todas condicoes

necessarias para que eu realizasse meus estudos.

Remetendo ao meu tempo de graduacao, poderia agradecer a varios professores que

eu admiro e foram importantes em minha formacao. Mas sei que estes entenderao meu

agradecimento: Prof. Alexandre Direne, meus sinceros e grandes agradecimentos por tudo.

No rumo da opcao pela vida academica, sem duvida, tenho muito a agradecer ao Prof.

Elias P. Duarte Jr., orientador deste trabalho e de muitos outros desde os tempos da ini-

ciacao cientıfica. Obrigado pelos ensinamentos, pela paciencia e pela ajuda em todos estes

anos. Aproveitando o tema da orientacao deste trabalho, agradecimentos a Profa. Keiko

O. Fonseca, que sempre ofereceu injecoes de animo e ajudou em tudo que foi necessario

para completar esta tese.

Na reta final, nao posso deixar de agradecer as pessoas presentes durante o perıodo

do sandwich em Barcelona: Joan Climent, Gema Albiach, Sandra Sandri e meninas, Roy

Verholen, Carlos Bonetti e Fabio Fonseca. Tios, salut i forca al canut. Na Universitat

Politecnica de Catalunya (UPC), agradeco fortemente ao Prof. Leandro Navarro e seu

grupo de pesquisa, que proporcionou recursos e ideias importantes para consolidar esta

tese, moltes gracies per tot.

Finalmente, meus grandes amigos, Marcos Castilho, Marcos Sunye, Lıgia Setenareski,

Fabiano Silva e Letıcia Peres, agradeco mais do que por esta tese: agradeco pela amizade,

pelas conversas e pela ajuda em todos momentos. So tenho a dizer, muito obrigado!

Though this be madness,

yet there is method in it

Hamlet, Act 2, Scene 2

Sumario

Lista de Figuras v

Lista de Tabelas vii

Resumo viii

Abstract ix

1 Introducao 1

2 Sistemas Distribuıdos de Larga Escala na Internet 5

2.1 Grades Computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.1 Primeira Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.2 Segunda Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.3 Terceira Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2 Programacao Paralela e Distribuıda com MPI . . . . . . . . . . . . . . . . 18

2.3 Redes Overlay Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Diagnostico Distribuıdo 31

3.1 O Modelo PMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 O Algoritmo Adaptive-DSD . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3 O Algoritmo Hi-ADSD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Sumario iii

3.4 O Algoritmo Hi-ADSD with Detours . . . . . . . . . . . . . . . . . . . . . 37

3.5 O Algoritmo Hi-ADSD with Timestamps . . . . . . . . . . . . . . . . . . . 41

3.5.1 Diagnostico Dinamico de Eventos . . . . . . . . . . . . . . . . . . . 42

3.5.2 Especificacao do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . 43

4 Diagnostico Distribuıdo Baseado no Algoritmo DiVHA 47

4.1 Modelo do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2 Especificacao do Algoritmo de Diagnostico Distribuıdo . . . . . . . . . . . 49

4.3 O Algoritmo DiVHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.4 Provas Formais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.5 Resultados de Simulacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.5.1 Numero de Testes Necessarios . . . . . . . . . . . . . . . . . . . . . 55

4.5.2 Latencia para Deteccao de Eventos . . . . . . . . . . . . . . . . . . 57

4.5.3 Comparacao com Outros Algoritmos . . . . . . . . . . . . . . . . . 59

5 HyperBone: Uma Rede Overlay Escalavel 62

5.1 Modelo do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.2 Construindo e Mantendo o Hipercubo Virtual . . . . . . . . . . . . . . . . 64

5.2.1 Algoritmo de Roteamento no Hipercubo Virtual . . . . . . . . . . . 65

5.2.2 Parametros de Disponibilidade . . . . . . . . . . . . . . . . . . . . . 67

5.3 Exemplos de Execucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.4 Implementacao e Resultados Experimentais . . . . . . . . . . . . . . . . . 71

5.4.1 Sistema de Monitoracao . . . . . . . . . . . . . . . . . . . . . . . . 71

5.4.2 Estrategia de Roteamento no HyperBone . . . . . . . . . . . . . . . 74

5.4.3 Executando Aplicacoes Paralelas no HyperBone . . . . . . . . . . . 76

6 Conclusao 81

Sumario iv

Referencias 84

Lista de Figuras

1 HyperBone formado por 8 nodos espalhados pela Internet. . . . . . . . . . 2

2 Sistema executando o algoritmo ADSD. . . . . . . . . . . . . . . . . . . . 34

3 Sistema de 8 nodos agrupados em clusters no algoritmo Hi-ADSD. . . . . 35

4 Clusters testados pelo nodo 0 executando o algoritmo Hi-ADSD. . . . . . 36

5 O grafo T (S) para um sistema com 8 nodos. . . . . . . . . . . . . . . . . 38

6 Sistema executando o algoritmo Hi-ADSD with Detours. . . . . . . . . . . 39

7 Especificacao do algoritmo Hi-ADSD with Detours. . . . . . . . . . . . . . 40

8 O grafo TFF0 para um sistema com 8 nodos. . . . . . . . . . . . . . . . . 44

9 Um exemplo de Ci,s,p: C0,3,2. . . . . . . . . . . . . . . . . . . . . . . . . . 44

10 Clusters testados pelo nodo 0. . . . . . . . . . . . . . . . . . . . . . . . . . 45

11 Diagnostico distribuıdo baseado no algoritmo DiVHA. . . . . . . . . . . . 50

12 Especificacao do algoritmo DiVHA. . . . . . . . . . . . . . . . . . . . . . . 51

13 Sistema de 8 nodos agrupados em clusters pelo algoritmo DiVHA. . . . . . 51

14 Aresta adicionada do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s. . . . . . . . . . 54

15 Numero de testes necessarios para um sistema com 64 nodos. . . . . . . . . 56

16 Numero de testes necessarios para um sistema com 128 nodos. . . . . . . . 57

17 Numero de testes necessarios para um sistema com 256 nodos. . . . . . . . 58

18 Latencia para sistemas com 512 nodos. . . . . . . . . . . . . . . . . . . . . 59

19 Latencia para sistemas com 32, 64, 128, 256, 512 e 1024 nodos. . . . . . . . 60

20 O algoritmo para criacao e manutencao do hipercubo virtual. . . . . . . . 65

21 Algoritmo de manutencao da tabela de rotas no HyperBone. . . . . . . . . 66

Lista de Figuras vi

22 Exemplo de roteamento para um sistema com 8 nodos no HyperBone. . . . 67

23 Algoritmo de atualizacao das informacoes sobre os estados de disponibili-

dade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

24 Exemplo de sistema com 16 nodos executando o HyperBone. . . . . . . . . 69

25 Representacao das iteracoes do algoritmo DiVHA. . . . . . . . . . . . . . . 70

26 Exemplo de sistema com 16 nodos apos falha do nodo 4. . . . . . . . . . . 70

27 Probabilidade acumulada para o tempo de permanencia nos estados working

e unresponsive. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

28 Probabilidade acumulada para o tempo de permanencia nos estados available

e unavailable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

29 Histograma da taxa de disponibilidade dos nodos. . . . . . . . . . . . . . . 75

30 Propagacao da informacao de um evento no nodo 4. . . . . . . . . . . . . 76

Lista de Tabelas

1 Ci,s para um sistema com 8 nodos. . . . . . . . . . . . . . . . . . . . . . . 36

2 Simulacoes de um sistema com 64 nodos executando os algoritmos Hi-ADSD

e Hi-ADSD com detours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Numero medio de testes necessarios para diagnosticar um sistema com 64

nodos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4 Latencia media para diagnosticar um evento em um sistema com 512 nodes. 61

5 Relacao de ganho da estrategia de roteamento do HyperBone. . . . . . . . 76

6 Resultados da execucao do MPIbench no HyperBone. . . . . . . . . . . . 77

7 Resultado da execucao de um buscador de senhas no HyperBone. . . . . . 77

8 Comparativo de vazao entre os dispositivos ch hyperbone e ch p4. . . . . . 79

9 Comparativo do tempo de execucao do MPI-PovRay entre os dispositivos

ch hyperbone e ch p4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Resumo

Este trabalho apresenta o HyperBone, uma rede overlay baseada em hipercubo virtual

que oferece servicos de monitoracao e roteamento, permitindo a execucao de aplicacoes dis-

tribuıdas na Internet. O hipercubo e uma estrutura escalavel por definicao, apresentando

caracterısticas topologicas importantes como: simetria, diametro logarıtmico e boas pro-

priedades para tolerancia a falhas. O hipercubo virtual e mantido pelo algoritmo DiVHA

(Distributed Virtual Hypercube Algorithm), que garante propriedades do hipercubo mesmo

quando o numero de nodos nao e potencia de dois. A especificacao do algoritmo DiVHA

e as provas formais de sua correcao sao apresentadas neste trabalho. Um algoritmo de di-

agnostico distribuıdo baseado no hipercubo virtual tambem e proposto. Sao apresentadas

as provas de correcao do algoritmo de diagnostico, bem como resultados experimentais obti-

dos por simulacao. No HyperBone e considerado um ambiente sujeito a situacoes dinamicas

de falhas, nas quais nodos falham e se recuperam continuamente, deixando o sistema para

depois serem reintegrados. Uma estrategia para classificar os nodos de acordo com sua

estabilidade e apresentada. Alem da monitoracao, o HyperBone oferece servicos de comu-

nicacao atraves do roteamento de mensagens. O algoritmo de roteamento proposto utiliza

as melhores rotas no hipercubo virtual. O HyperBone foi implementado no PlanetLab,

um ambiente constituıdo por nodos ao redor do mundo conectados pela Internet sujeitos a

altas carga de processamento e de trafego de rede. Os resultados experimentais mostram a

capacidade do HyperBone monitorar sistemas altamente instaveis como o PlanetLab, assim

como a capacidade de executar aplicacoes MPI paralelas usando o hipercubo virtual.

Abstract

This thesis presents HyperBone, an overlay network based on a virtual hypercube that

offers services such as monitoring and routing, allowing the execution of distributed ap-

plications across the Internet. Hypercubes are scalable by definition, presenting several

properties such as symmetry and logarithmic diameter, that are advantageous for distri-

buted and parallel applications. HyperBone nodes run the Distributed Virtual Hypercube

Algorithm (DiVHA) in order to keep hypercube properties even when the number of nodes

is not a power of two. The specification of the DiVHA algorithm as well as the formal

proofs of its correctness are presented. A distributed diagnosis algorithm based on the vir-

tual hypercube is also proposed, along with its experimental results accomplished through

simulation. The system is considered to be subject to a dynamic fault situation, in which

nodes may continuously fail and recover, vanishing from the system to possibly restart

further ahead in time. A strategy of node classification according to its stability is presen-

ted. Besides monitoring HyperBone also offers a routing service. The routing algorithm

proposed is capable of determining optimal routes in the virtual hypercube. HyperBone is

implemented in PlanetLab, an environment built up with nodes spread around the world

interconnected by the Internet, subjected to high processing and network loads. The expe-

rimental results suggest how capable HyperBone is of monitoring highly unstable systems,

such as PlanetLab, and of executing parallel MPI applications in the virtual hypercube.

1

1 Introducao

Diversos sistemas distribuıdos de larga escala tem surgido na Internet nos ultimos anos.

O desenvolvimento destes sistemas e consequencia da Internet ter permitido interconectar

um grande numero de recursos computacionais. Alem disso, protocolos e padroes vem

derrubando a barreira da heterogeneidade das tecnologias. A computacao em grade (FOS-

TER; KESSELMAN, 1997; OURGRID, 2005), ou grid computing, e as redes peer-to-peer (P2P)

(CLARK, 2001) sao exemplos de tecnologias que tem permitido acessar e utilizar esses re-

cursos, formando sistemas distribuıdos de grande porte e dinamicos, nos quais nodos nao

sao permanentes, se integrando e deixando continuamente o sistema, que esta sujeito a

falhas e recuperacoes tambem contınuas.

Uma abordagem promissora para construir esses sistemas distribuıdos de larga escala

na Internet sao as redes overlay (AMIR; DANILOV, 2003). Em princıpio as aplicacoes dis-

tribuıdas poderiam gerenciar seus recursos acessando diretamente a rede subjacente, mas

uma rede overlay pode oferecer servicos como manutencao da rede, seguranca e alta dispo-

nibilidade que dificilmente poderiam ser providos no nıvel de rede. Em redes P2P as redes

overlay tem sido utilizadas como forma de tornar o sistema escalavel (DOVAL; O’MAHONY,

2003), outras redes overlay destinam-se a melhorar os servicos oferecidos pelos protocolos

da Internet, como suportar QoS ou multicast (QBONE, 2005; ERIKSSON, 1994) ou ainda

oferecer formas de roteamento alternativas (ANDERSEN; BALAKRISHNAN; MORRIS, 2001).

Este trabalho apresenta o HyperBone (BONA; DUARTE Jr.; FONSECA, 2005; BONA et

al., 2006), uma rede overlay formada por nodos espalhados pela Internet interligados por

1 Introducao 2

enlaces virtuais, que sao arestas de um hipercubo virtual, implementadas como conexoes

TCP (Transmission Control Protocol) persistentes. Os nodos do HyperBone sao hosts da

Internet capazes de realizar tarefas de processamento. Os nodos realizam testes entre si e

trocam informacao sobre o resultado destes testes, implementando um sistema distribuıdo

de monitoracao. Se o numero de nodos e uma potencia de dois e todos nodos estao sem

falhas, a topologia do sistema e um hipercubo completo. A figura 1 mostra o HyperBone

sendo executado em 8 nodos, as linhas pontilhadas indicam os enlaces virtuais.

Figura 1: HyperBone formado por 8 nodos espalhados pela Internet.

A principal caracterıstica do sistema e a escalabilidade, o hipercubo e uma estrutura es-

calavel por definicao, que apresenta caracterısticas topologicas importantes como: simetria,

diametro logarıtmico e boas propriedades para tolerancia a falhas (TIEN; RAGHAVENDRA,

1993; KRULL; WU; MOLINA, 1992; SAAD; SCHULTZ, 1998). Deve ser destacado neste tra-

balho que as caracterısticas que dificultam a utilizacao dos hipercubos para arquiteturas

de maquinas paralelas nao estao presentes no hipercubo virtual: o numero de nodos nao

precisa ser potencia de dois e o custo de adicionar ligacoes, que sao virtuais, e baixo.

Mesmo quando o numero de nodos nao e potencia de dois ou alguns nodos nao estao

disponıveis, o HyperBone ainda e capaz de manter as propriedades logarıtmicas do hiper-

cubo. A topologia e mantida pelo HyperBone utilizando o algoritmo DiVHA (Distributed

1 Introducao 3

Virtual Hypercube Algorithm), tambem proposto neste trabalho. O DiVHA efetivamente

calcula os enlaces do hipercubo virtual, permitindo aos nodos se auto-organizarem man-

tendo caracterısticas do hipercubo como o diametro logarıtmico. O sistema e dinamico, ou

seja, os nodos podem falhar e se recuperar constantemente.

O algoritmo DiVHA esta relacionado com o diagnostico distribuıdo (MASSON; BLOUGH;

SULLIVAN, 1996). Os algoritmos de diagnostico definem estrategias de testes que permitem

que todos os nodos sem falha de um sistema determinem o estado de todos os outros

nodos do sistema. As assercoes sobre o sistema feitas pelos algoritmos de diagnostico sao

bastante diferentes das feitas no DiVHA, especialmente porque os algoritmos de diagnostico

consideram que os nodos sao capazes de determinar o estado de outros nodos com 100%

de precisao (PREPARATA; CHIEN, 1967), o que e uma assercao que nao pode ser cumprida

em sistemas assıncronos (FISCHER; LYNCH; PATERSON, 1985). Por outro lado, a forma

de organizar os testes e o fluxo de informacao e bastante semelhante. Tambem e proposto

neste trabalho um algoritmo de diagnostico distribuıdo baseado no DiVHA (BONA; DUARTE

Jr.; FONSECA, 2006). O algoritmo e formalmente especificado, sao apresentadas provas de

correcao e resultados experimentais obtidos atraves de simulacao.

As caracterısticas topologicas do hipercubo virtual permitem implementar um sistema

de monitoracao distribuıda onde os nodos sem falha podem determinar o estado de todos

outros nos do sistema em no maximo log2N rodadas de testes, requerendo no maximo

N ∗ (log2N)2 testes. De nosso conhecimento, nenhum outro algoritmo distribuıdo de mo-

nitoracao apresenta um numero tao baixo de mensagens. O HyperBone introduz ainda

uma estrategia que permite cada nodo manter uma lista dos nodos que estao apresentando

comportamento estavel e que podem ser utilizados para executar tarefas de processamento.

O HyperBone e capaz de rotear mensagens pelos enlaces do hipercubo virtual, ofe-

recendo um servico de comunicacao escalavel que permite a qualquer par de nodos se

comunicar diretamente usando rotas com distancia logarıtmica, sem a necessidade de esta-

belecer enlaces entre todos os nodos. Todo o trafego entre os nodos e tunelado pelos enlaces

1 Introducao 4

virtuais, facilitando a instalacao de nodos atras de firewalls restritivos. O roteamento no

hipercubo virtual permite ainda encontrar rotas alternativas aquelas usadas pelos nodos

quando se comunicam diretamente pela Internet. Uma estrategia de roteamento que per-

mite escolher as rotas com menor custo no hipercubo virtual tambem e apresentada neste

trabalho.

O HyperBone foi implementado no PlanetLab (PLANETLAB, 2005), um ambiente que

permite avaliar aplicacoes distribuıdas em escala global sob condicoes reais. Os resultados

experimentais mostram o funcionamento do sistema de monitoracao validando a estrategia

proposta para identificar nodos estaveis. Os experimentos tambem mostram a capacidade

de executar aplicacoes distribuıdas em escala mundial utilizando a rede overlay oferecida

pelo HyperBone, nestes experimentos foram executadas aplicacoes paralelas usando MPI

(Message Passing Interface) (MESSAGE PASSING INTERFACE FORUM, 1994). Uma imple-

mentacao alternativa do HyperBone (MELLO et al., 2006), que permite as aplicacoes MPI

acessarem diretamente o hipercubo virtual, tambem foi apresentada e avaliada.

O restante deste trabalho esta organizando da seguinte maneira. O capıtulo 2 apresenta

algumas das principais abordagens existentes atualmente para a organizacao de sistemas

distribuıdos de grande porte. O capıtulo 3 apresenta o diagnostico distribuıdo e os al-

goritmos de diagnostico relacionados com o DiVHA. No capıtulo 4, o algoritmo DiVHA

e especificado, e um novo algoritmo de diagnostico baseado do DiVHA e proposto, bem

como sao apresentadas provas formais de correcao e resultados experimentais obtidos por

simulacao. O HyperBone e apresentado e especificado no capıtulo 5, onde sao apresenta-

dos resultados da implementacao e execucao do HyperBone no PlanetLab. Finalmente, o

capıtulo 6 conclui este trabalho.

5

2 Sistemas Distribuıdos de Larga

Escala na Internet

A popularizacao das redes de computadores, em especial a Internet, permitiu interco-

nectar um grande numero de recursos computacionais. Os protocolos de rede difundidos

nas ultimas decadas derrubaram a barreira da heterogeneidade das diversas tecnologias de

redes. A disponibilidade destes recursos tem permitido o aparecimento de sistemas dis-

tribuıdos de larga escala, compostos por um grande numero de unidades espalhadas por

todo o planeta.

As redes overlay (AMIR; DANILOV, 2003) sao uma alternativa para implementar servicos

de rede distribuıdos. As redes overlay sao redes logicas construıdas sobre a rede fısica. Em

princıpio as aplicacoes distribuıdas poderiam gerenciar seus recursos acessando diretamente

a rede subjacente, mas uma rede overlay pode oferecer servicos como manutencao da rede,

seguranca e alta disponibilidade que dificilmente poderiam ser providos no nıvel de rede.

Este trabalho apresenta o HyperBone, uma rede overlay que permite a execucao de

aplicacoes distribuıdas na Internet. O HyperBone esta relacionado aos sistemas para com-

putacao em grades, uma das tecnologias que trata os problemas de agregar e coordenar

recursos na Internet, sendo apresentada na secao 2.1. Este trabalho apresenta exemplos de

execucoes de programas paralelos usando o HyperBone no PlanetLab. A secao 2.2 apre-

sentas os principais trabalho relacionados com a execucacao deste tipo de aplicacoes em

grades computacionais. As redes overlay P2P, que sao outra abordagem para o problema

de compartilhamento de recursos e execucao de tarefas, sao apresentadas na secao 2.3.

2.1 Grades Computacionais 6

2.1 Grades Computacionais

O objetivo principal de um ambiente de grades e compartilhar recursos computacionais

em grandes redes de computadores como a Internet. O termo grade computacional pode

ser empregado para muitos tipos de problemas de compartilhamento de recursos. Com

isto a definicao precisa do termo “grade” pode variar de acordo com fatores como o tipo,

uso e grau de heterogeneidade dos recursos envolvidos ou mesmo da arquitetura utilizada

pelo ambiente. Esta secao tem como objetivo apresentar diferentes conceitos e projetos

em grade computacionais. A subsecao 1 apresenta o que podem se considerar como os

primeiros esforcos e projetos de computacao em grade. A subsecao 2 apresenta a segunda

geracao de grades computacionais, um dos paradigmas mais estudados e desenvolvidas atu-

almente. Finalmente, a subsecao 3 apresenta um novo paradigma para o compartilhamento

de recursos, correspondente a terceira geracao de grade computacional.

2.1.1 Primeira Geracao

Os primeiros esforcos para a criacao de grades computacionais deram-se sob o nome de

metacomputacao por volta dos anos 1990 com a interligacao de sıtios de supercomputacao

com o objetivo de oferecer recursos computacionais para aplicacoes de alto desempenho. Os

projetos mais importantes sao de 1995 e foram o FAFNER (Factoring via Network-Enabled

Recursion) (NORTHEAST PARALLEL ARCHITECTURES CENTER, 2005) e o I-WAY (Infor-

mation Wide Area Year) (FOSTER et al., 1997), o primeiro relacionado com a interligacao

de estacoes de trabalho e o segundo com a unificacao de recursos de supercomputacao.

O FAFNER foi um projeto destinado a fatoracao de numeros muito grandes, um desafio

computacionalmente intensivo muito relevante para seguranca digital. Como este tipo de

processamento pode ser quebrado em pequenas partes, mesmo um computador bastante

modesto pode contribuir de forma util para o processamento. Outra caracterıstica desta

aplicacao e nao haver a necessidade de uma rede de alta velocidade. O FAFNER apresentou


uma serie de limitacoes, como a grande necessidade de intervencao humana para recolher

os resultados e a incapacidade dos nodos se comunicarem entre si. Apesar disto, foi uma

iniciativa de sucesso, dando origem a sucessores como o SETI@home (SETI INSTITUTE,

2005).

O I-WAY foi um projeto direcionado a ligacao de supercomputadores. Era direcionado

a aplicacoes de alto desempenho, exigindo assim uso de redes de alta velocidade, ficando

limitado portanto a sıtios que possuıam esta estrutura. Uma das inovacoes do projeto foi

o desenvolvimento de um agenciador de recursos (resource broker), conceitualmente muito

similar aos agenciadores de recursos dos projetos de grade atuais.

Um experimento realizado com o I-WAY foi a tentativa de usar uma camada de comu-

nicacao chamada Nexus (FOSTER; KESSELMAN; TUECKE, 1996) para executar aplicacoes

paralelas. Apesar do grande esforco realizado nao foi possıvel obter um ambiente estavel

para execucao dessas aplicacoes. As causas provaveis foram a heterogeneidade dos sistemas

interligados por uma rede de baixa velocidade e uma limitacao da escala relacionada com

problema de exaustao de descritores de arquivos e sockets de rede abertos. Apesar deste

infortunio, o I-WAY e considerado uma experiencia de sucesso, influenciando o desenvolvi-

mento do projeto Globus (FOSTER; KESSELMAN, 1997; UNIVERSITY OF CHICAGO, 2005),

que e um dos padroes de grades mais aceitos atualmente, assim como o projeto Legion

(GRIMSHAW; WULF, 1997).

Apesar do FAFNER e do I-WAY serem considerados como as primeiras iniciativas em

grades computacionais, o termo grid propriamente dito so foi apresentado oficialmente com

a publicacao do livro The Grid: Blueprint for a New Computing Infrastructure (FOSTER;

KESSELMAN, 1998). O termo grid surge como uma analogia a rede eletrica (electric power

grid), que prove acesso a eletricidade de forma pervasiva e teve importancia dramatica

no desenvolvimento da sociedade. O grid denota uma infraestrutura para prover acesso

confiavel, consistente, pervasivo e barato para uma larga escala e variedade de recursos

computacionais.


2.1.2 Segunda Geracao

As tecnologias de redes de alta velocidade e a adocao de padroes permitiram viabili-

zar as grades como uma infraestrutura distribuıda em escala global, suportando diversas

aplicacoes que requeiram computacao e dados em grande escala. Na segunda geracao fica

claro que a grade computacional deve ter como objetivo esconder a natureza heterogenea do

ambiente e prover aos usuarios e aplicacoes acesso aos recursos de uma maneira uniforme.

Os desafios a serem atacados sao a heterogeneidade, escalabilidade e adaptabilidade.

A heterogeneidade e um desafio porque um ambiente de grade envolve uma multiplici-

dade de recursos heterogeneos por natureza e sujeitos a diversos domınios administrativos.

Assim, e necessario se preocupar em como prover acesso uniforme aos diversos recursos sem

prejudicar as polıticas de administracao locais.

A escalabilidade tambem e um desafio porque um ambiente de grades pode envolver mi-

lhares ou ate milhoes de recursos em um unico ambiente, o que leva a potenciais problemas

de degradacao de desempenho e dificuldades para os sistemas de informacao e monitora-

mento. Alem disto a escala aumenta ainda mais o numero de organizacoes que podem

compor as grades, aumentando a heterogeneidade e a necessidade de tratar questoes de

autenticacao e confiabilidade.

Finalmente, a adaptabilidade tambem e um desafio, pois nao e esperado que um am-

biente de grade permaneca sem alteracoes por um longo perıodo. Os gerenciadores de

recursos e as aplicacoes devem ser capazes de comportar-se dinamicamente, extraindo o

maximo possıvel dos recursos disponıveis. Na questao de adaptabilidade tambem devem

ser considerados aspectos como a tolerancia a falhas.

Uma serie de caracterısticas sao esperadas de uma ambiente de grade:

Hierarquia administrativa: Espera-se que um ambiente de grades possa ser bastante

grande em termos de componentes (computadores e outros recursos de hardware ou


software), nao e razoavel que cada componente do sistema tenha que interagir di-

retamente com todos os outros componentes. Assim, sao necessarios mecanismos e

estrategias para particionar o domınio e determinar o fluxo de informacao adminis-

trativa pela grade.

Servicos de comunicacao: As aplicacoes podem requerer diversas classes de servicos

de comunicacao, indo de comunicacao ponto-a-ponto confiavel ate multicast nao-

confiavel, ou ainda suporte aos protocolos usados para transferencia em grande vo-

lume (bulk), streaming, comunicacao em grupo e outros usados por paradigmas de

objetos distribuıdos. Alem disto, pode ser necessario atender alguns parametros de

qualidade de servicos (QoS - Quality of Service) . O ambiente de grade deve estar

preparado para atender ou pelo menos permitir estas diversas classes de servico de

comunicacao.

Servicos de informacao: No ambiente de grades pode estar disponıvel um grande con-

junto de recursos de caracterısticas distintas. Devido a dinamicidade do ambiente a

tendencia e que exista uma grande variacao neste conjunto com a entrada de novos re-

cursos e o desaparecimento de outros. Assim, e necessario um servico de informacao

que ofereca um servico de diretorio para prover informacoes sobre os recursos dis-

ponıveis e um mecanismos que permita aos domınios administrativos registrar in-

formacoes sobre os recursos disponıveis.

Servico de nomes: E necessario que a grade tenha um espaco de nomes uniforme que

permita nomear a grande variedade de recursos, como computadores, servicos ou da-

dos, que compoem o sistema. Em alguns sistemas o DNS (Domain Name Service)

pode ser suficiente, porem e comum que seja necessario utilizar esquemas mais com-

plexos como o LDAP (Lightweight Directory Access Protocol) (WAHL; KILLE; HOWES,

1997) .

Sistema de arquivos distribuıdos: As aplicacoes distribuıdas geralmente requerem acesso


a arquivos que podem estar distribuıdos entre muitos servidores. Um sistema de ar-

quivos distribuıdos prove um espaco de nome global, suporte a uma diversidade de

protocolos da maneira mais transparente possıvel para as aplicacoes e ainda se preo-

cupa com as questoes de otimizacao e desempenho proprias do ambiente.

Seguranca e autorizacao: A seguranca e uma das questoes mais complexas e impor-

tantes. Os recursos envolvidos estao sujeitos a polıticas de administracao diversas

que precisam interagir para proporcionar os acessos necessarios de forma segura. As

questoes de confidencialidade, integridade, autenticacao e auditabilidade devem ser

sempre observadas. A seguranca deve se preocupar nao apenas em negar ou permitir

acesso, mas tambem em delimitar este acesso.

Monitoracao: A dinamicidade do ambiente de grade impoe que sempre existam compo-

nentes do sistema mudando de estado. Ainda podem ser implementados mecanismos

de tolerancia a falhas que precisam conhecer o estado do sistema. Desta forma, um

ambiente de grades necessita prover ferramentas que permitam monitorar seus com-

ponentes.

Gerenciamento de recursos: Alem de permitir o acesso aos recursos e necessario ao

ambiente de grade proporcionar mecanismos para realizar o controle deste recursos.

O principal objetivo do sistema de gerenciamento de recursos e escalonar o uso de

recursos de maneira eficiente.

Diversos trabalhos em grades computacionais apresentaram estrategias e modelos para

atacar os problemas e implementar as caracterısticas apresentadas. As proximas sessoes

apresentam alguns dos trabalho mais relevantes.

Globus

O Globus Toolkit (FOSTER; KESSELMAN, 1997; UNIVERSITY OF CHICAGO, 2005) e um

projeto que prove um conjunto de servicos e bibliotecas para dar suporte a infraestrutura


e aplicacoes em grades. O Globus tem evoluıdo constantemente e vem sendo considerado

um padrao de facto para a computacao em grades. Esta sessao apresenta a versao 2 (GT2)

do Globus, que corresponde ao paradigma de grades computacionais da segunda geracao.

Atualmente o Globus esta em sua versao 3 (GT3), entretanto o GT3 impoe um paradigma

diferente, que nem sempre e facilmente adotado em todos cenarios de uso do Globus, assim

atualmente muitos ambientes de grades continuam utilizando o GT2.

O Globus e uma colecao de modulos que prove servicos de baixo custo para implementar

servicos de grade. Os principais componentes sao o GSI (Grid Security Infrastructure),

o GRAM (Globus Resource Allocation Manager) e o MDS (Monitoring and Discovering

System), descritos a seguir.

O GSI e base do sistema e e utilizado para: prover autenticacao e comunicacao segura

sobre uma rede aberta; suportar seguranca entre os diversos domınios administrativos,

evitando um sistem de seguranca centralizado; e suportar single sign-on para os usuarios

da grade, incluindo delegacao de credenciais.

O GSI e baseado em criptografia de chave publica, certificados X.509 e no protocolo de

comunicacao SSL (Secure Sockets Layer), com as extensoes necessarias para single sign-on

e delegacao. A implementacao do GSI esta em conformidade com a GSS-API (Generic

Security Service API), que e uma API padrao para seguranca de sistemas promovida pelo

IETF (Internet Engineering Task Force).

O GRAM e responsavel pela gerencia de recursos, ele prove uma interface padrao

para requisitar e utilizar sistemas remotos e para a submissao e controle de tarefas. O

objetivo e esconder a grande variedade de mecanismos de gerencia locais, fazendo com que

os desenvolvedores de aplicacoes somente necessitem conhecer a interface do GRAM. O

sistema de autorizacao do GRAM e baseado nas identidades GSI e em mecanismos para

mapear estas identidades para as polıticas locais de administracao de usuarios.

O MDS prove as ferramentas necessarias para construir um sistema de informacoes


para grades baseado no servico de diretorio LDAP. O LDAP e utilizado para padronizar

os metodos de consulta as informacoes de sistema e para construir um espaco de nomes

uniforme para as informacoes fornecidas pelas muitas organizacoes que podem compor o

sistema.

O MDS e dividido nos modulos GIIS (Grid Index Infomation Service) e GRIS (Grid

Resource Information Service). O GRIS e o modulo responsavel por colher as informacoes

dos recursos, gerar os dados e proporcionar uma interface para consultar estas informacoes.

O GIIS prove um meio de agregar informacoes dos diversos GRIS que compoem o sistema,

servindo de repositorio de informacoes sobre todo o sistema, ou determinado sub-conjunto.

As aplicacoes entao podem consultar o GIIS em busca de informacoes, como recursos

disponıveis.

O Globus tambem implementa uma versao estendida do bem conhecido protocolo FTP

chamdo de GridFTP. As extensoes permitem o uso de protocolos de seguranca, acesso

parcial de arquivos e gerenciamento do paralelismo de transferencia em alta velocidade.

Alem dos elementos principais da arquitetura o Globus ainda prove diversos servicos

para facilitar o desenvolvimento de aplicacao. O GlobusIO oferece um servico de comu-

nicacao dentro da grade em um estilo similar a programacao em socket TCP/IP. O GASS

(Global Access to Secondary Storage) e utilizado para permitir o acesso a arquivos den-

tro da grade de forma simplificada, permitindo a reutilizacao de programas em linguagem

C padrao que fazem acesso a arquivo com pouca ou nenhuma modificacao. O DUROC

(Dynamically-Updated Request Online Coallocator) prove uma interface conveniente para

obter recursos e executar trabalhos atraves de multiplos gerenciadores de recursos de forma

coordenada.


Legion

O Legion (GRIMSHAW; WULF, 1997) e um metasistema baseado em objetos, projetado

para construir um sistema de milhoes de nodos e trilhoes de objetos, interligados por redes

de alta velocidade. O projeto iniciou em 1993 e em 1997 teve sua primeira implementacao

divulgada.

O objetivo e dar aos usuarios a impressao de estar trabalhando em um unico compu-

tador com acesso a todos tipos de dados e recursos fısicos. Grupos de usuarios podem

construir grupos virtuais de trabalho para pesquisa colaborativa e troca de informacoes.

No Legion tudo e objeto: todos os recursos sao apresentados como Objetos Legion,

que sao processos ativos e independentes que respondem a invocacoes feitas por outros

objetos do sistema. A IDL (Interface Description Language) pode ser usada para descrever

a interface das classes de objetos.

Considerando o potencialmente grande numero de objetos que podem compor o sistema

, e oferecido um espaco de nomes controlado pelos usuarios chamado de context space, que

permite encontrar e usar objetos espalhados no sistema. Ainda, existe um esquema para

armazenar de forma persistente os objetos do sistema.

O Legion define a API para um conjunto de objetos nucleo (core objects) que supor-

tam servicos basicos como: nomeacao e ligacao; abstracao de recursos de processamento;

representacao persistente de objetos e ativacao, desativacao e delecao de objetos.

Condor

Muitos sistemas fazem uso de recursos heterogeneos distribuıdos geograficamente, se

aproximando dos objetivos dos grid. O Condor (UNIVERSITY OF WISCONSIN MADISON,

2005; LITZKOW; LIVNY; MUTKA, 1998) e um sistema de gerenciamento de recursos e tare-

fas, concebido para trabalhar com processamento em lote utilizando o poder de processa-


mento de estacoes ociosas. O proposito do Condor e fornecer grande quantidade de poder

computacional a medio ou longo prazo.

O Condor recebe as tarefas dos usuarios e escolhe onde executa-las baseado em uma

determinada polıtica, e ainda prove os meios para acompanhar a execucao destas tarefas

e obter os resultados. As tarefas submetidas recebem um conjunto de restricoes como

necessidade de processamento e quantidade de memoria. Os donos das maquinas partici-

pantes do sistema tambem informam as restricoes de uso, por exemplo que so compartilha

sua maquina quando ela esta ociosa. O escalonador procura a melhor forma de casar os

requisitos das tarefas com os recursos disponıveis.

Um dos recursos interessantes do Condor e a capacidade de suspensao das tarefas

(LITZKOW et al., 1997). O mesmo mecanismo usado para a suspensao tambem permite que

uma tarefa seja migrada de uma maquina que deixou de estar ociosa para uma ociosa.

Entretanto o Condor surgiu para trabalhar em redes locais e questoes de seguranca e

de domınio administrativo local nao sao tratadas. O Condor-G (FREY et al., 2001) e uma

versao do Condor preparada para integrar-se com o Globus, permitindo a interligacao de

varios domınios Condor.

2.1.3 Terceira Geracao

A segunda geracao trouxe a interoperabilidade essencial para viabilizar a computacao

em grande escala, mas o progresso das solucoes deixou aparente novos aspectos que impli-

caram em modificacoes no paradigma.

Percebeu-se que seria valioso para aplicacoes nas grades reutilizar de forma flexıvel

componentes e recursos de informacao espalhados pela grade. A solucao para este problema

orientou o desenvolvimento dos ambientes de grades para modelos orientados a servico

com uma maior atencao para os metadados. O enfoque se deslocou da abordagem de

compartilhamento de recursos para a abordagem de compartilhamento de servicos (FOSTER;


KESSELMAN; TUECKE, 2001; FOSTER et al., 2002).

A abordagem orientada a servicos por si so tem implicacoes na estrutura da informacao,

pois o emprego flexıvel de recursos distribuıdos pela grade para composicao de aplicacoes

tem requisitos proprios. E necessario ter informacoes sobre funcionalidade, disponibilidade

e interface para os varios componentes que vao compor a aplicacao, alem disto esta in-

formacao deve ter uma interpretacao pre-acordada para que possa ser processada de forma

automatica pelas maquinas.

Na terceira geracao sao introduzidos termos como colaboracao distribuıda e orga-

nizacoes virtuais (VOs) (FOSTER; KESSELMAN; TUECKE, 2001). O foco e a necessidade

de compartilhamento de recursos para solucao de problemas em conjunto. As organizacoes

virtuais sao portanto conjuntos de recursos sujeitos a um controle bastante claro de acesso.

Estas VOs sao provedores de recursos, por exemplo uma VO pode ser membro de um projeto

para construir uma aeronave e estar provendo os recursos computacionais para simular um

tunel de vento, ou ser um provedores de informacoes para tomada de decisoes estrategicas.

Enfim uma VO prove um recurso computacional qualquer que pode ser empregado para

resolver problemas de forma cooperativa.

Esta nova visao de grades computacionais se coaduna com o aumento da populari-

dade do paradigma de Web Services (IBM WEB SERVICES ARCHITECTURE TEAM, 2000),

uma tecnologia baseada em protocolos da Internet que visa ser padrao para arquiteturas

baseadas em servico.

Web Services

Os Web Services sao um paradigma de computacao distribuıda baseado em padroes da

Internet. Basicamente, um Web Service encapsula uma determinada tarefa, recebendo os

parametros pela rede e retornando o resultado. Os protocolos utilizados permitem que esses

servicos estejam nas mais diferentes plataformas e sejam escritos em qualquer linguagem.


As mensagens trocadas sao escritas em XML (eXtensible Markup Language) (WORLD

WIDE WEB CONSORTIUM, 2005c), e o SOAP (Simple Object Access Protocol) prove um

mecanismo de transporte para estas mensagens (WORLD WIDE WEB CONSORTIUM, 2005a).

O XML e uma linguagem padronizada, extensıvel e estruturada, promovida pelo W3C

(World Wide Web Consortium). A independencia de dados, ou a separacao do conteudo de

sua apresentacao, e a caracterıstica essencial do XML. A apresentacao de um documento

XML pode variar de acordo com o uso.

O SOAP e utilizado para possibilitar a transferencia de dados em um sistema dis-

tribuıdo ou rede. E um protocolo baseado em XML, portanto e basicamente um conjunto

de esquemas em XML que descrevem a forma de transmitir mensagens pela rede, incluindo

o tipo de dados que as mensagens podem conter e a maneira em que devem estar estrutu-

radas. O protocolo mais comum para o SOAP e o HTTP, mas qualquer protocolo pode ser

utilizado.

Outra caracterıstica e que os Web Services tambem sejam auto-descritivos, provendo

informacao do que eles fazem e como podem ser utilizados. Estas descricoes geralmente

costumam ser feitas utilizando o WSDL (Web Services Description Language) (WORLD

WIDE WEB CONSORTIUM, 2005b).

Finalmente, e possıvel ter repositorios com informacoes sobre os Web Services dis-

ponıveis para as aplicacoes. Isto e feito pelo UDDI (Universal Description, Discovery and

Integration) (OASIS OPEN, 2005).

Todo Web Service e acompanhado de um WSDLfile que lista as capacidades do servico,

seu estado, localizacao e provedores. O arquivo WSDL define os tipos de mensagem que

ele pode enviar e receber, bem como os dados que a aplicacao chamadora deve prover.


2.1.3.1 Open Grid Services Architecture

O OGSA (Open Grid Services Architecture) (FOSTER et al., 2002) e um esforco para

definir uma arquitetura padronizada para grades computacionais. O OGSA define uma

arquitetura baseada no princıpio que todos os recursos sao servicos.

O OGSA suporta a criacao, manutencao e arranjo dos servicos mantidos pelas VOs.

Um servico e definido com uma entidade de rede que prove alguma capacidade, como

recursos computacionais, recursos de armazenamento, rede, programas ou base de dados.

No OGSA um Grid Service e um Web Service que prove um conjunto de interfaces padrao

bem definido. Algumas interfaces padrao requeridas pelo OGSA sao:

Descoberta : Os clientes necessitam mecanismos para descobrir os servicos disponıveis e

para determinar as caracterısticas destes servicos de tal forma que possam configurar

a si e as suas requisicoes para estes servicos.

Criacao dinamica de servicos : A habilidade de criar e gerenciar automaticamente no-

vos servicos e fundamental na OGSA. Para isto e definido um servico de criacao

de servicos. O OGSA define uma interface padrao (factory) e uma semantica que

qualquer servico de criacao de servicos deve prover.

Gerenciamento de tempo de vida : Em um sistema que incorpora instancias de servicos

transientes e providas de estado (stateful) devem ser providos mecanismos para acom-

panhar o tempo de vida destes servicos. Assim, e possıvel determinar um tempo de

criacao para o servico, bem como uma validade.

Notificacao : Os objetos devem ser capazes de notificar uns ao outros de maneira assıncrona

as mudancas em seus estados.

Uma das caracterısticas do OGSA e suportar multiplos protocolos para a ligacao do

servico. As questoes pertinentes a autenticacao e invocacao do servico sao consideradas

como problemas dos protocolos de ligacao.

2.2 Programacao Paralela e Distribuıda com MPI 18

O OGSI (Open Grid Services Infrastructure) (TUECKE et al., 2003; GLOBAL GRID FO-

RUM, 2005) e um conjunto de especificacoes WSDL que define as interfaces padrao, com-

portamentos e esquemas para computacao em grades de acordo com o OGSA, ou seja, e a

especificacao em WSDL dos Grid Services.

O Globus 3.0 implementa o OGSA e as especificacoes definidas pelo OGSI, mas mantem

todo os servicos do GT2 como alternativas aos servicos GT3. A nova versao do Globus,

GT4, abandona o OGSI que se mostrou uma especificacao muito complexa.

2.2 Programacao Paralela e Distribuıda com MPI

Algumas aplicacoes podem ser paralelizadas, ou seja, divididas de forma a serem dis-

tribuıdas e serem executadas de forma distribuıda e simultanea em varios processadores.

O modelo de passagem de mensagens para computacao paralela se mostrou com um para-

digma expressivo e eficiente para programacao paralela. Inicialmente havia uma falta de

padronizacao, existindo muitas implementacoes destes modelos que em geral guardavam

uma mesma semantica. A partir de 1992 se organizou um forum com o objetivo de criar um

padrao que possibilitasse a portabilidade das aplicacoes que faziam uso de troca de men-

sagens. Como resultado, em 1994, foi publicada o MPI Standard 1.0 (MESSAGE PASSING

INTERFACE FORUM, 1994).

O MPI e uma interface de programacao para aplicacoes baseadas em troca de mensa-

gens. O MPI inclui operacoes para troca de mensagem ponto-a-ponto como o MPISend e

MPIRecv. Para grupos de processadores, o MPI prove as operacoes coletivas. Os proces-

sadores sao identificados por numeros e estes identificadores sao chamados ranks. Alem do

rank os processadores podem ser identificados de acordo com topologias virtuais, relacio-

nadas com a semantica da aplicacao.

O MPICH (GROPP et al., 1996) e uma das implementacoes mais populares e testadas do

padrao de interface para troca de mensagens. Os objetivos principais do MPICH sao atingir


alto desempenho e portabilidade. Atualmente o MPICH e uma implementacao completa

do padrao MPI com extensoes para suportar funcoes de I/O paralelo definido no padrao

MPI2 (MESSAGE PASSING INTERFACE FORUM, 1997).

O MPICH-G2 (FOSTER; KARONIS, 1998; KARONIS; TOONEN; FOSTER, 2003) e a imple-

mentacao da biblioteca MPICH para ambientes em grade baseada no Globus. Os servicos

do Globus sao utilizados para autenticacao, autorizacao, comunicacao e submissao de traba-

lhos. Uma vantagem deste modelo e estar baseada em um codigo ja bastante desenvolvido

e testado que e o do MPICH. A estrategia do MPICH-G2 para melhorar o desempenho e

utilizar as bibliotecas para comunicacao internas quando estas estiverem disponıveis e so-

mente fazer a comunicacao atraves do Globus quando os processos estiverem em diferentes

domınios.

Antes de iniciar uma aplicacao MPICH-G2 o usuario usa o GSI para obter uma cre-

dencial para se autenticar. O usuario tambem pode usar o MDS para selecionar os com-

putadores que serao utilizados, de acordo com configuracao, disponibilidade e conectivi-

dade de rede. Uma vez autenticado, o usuario requisita a criacao da computacao MPI.

O MPICH-G2 usa o RSL (Resource Specification Language) para descrever os trabalhos

a serem executados. Baseados nestas estruturas o MPICH-G2 chama a biblioteca de co-

alocacao distribuıda DUROC para escalonar e iniciar a aplicacao pelos varios computadores

especificados pelo usuario. O DUROC usa o GRAM para iniciar e gerenciar as subcom-

putacoes MPI. Para cada subcomputacao o DUROC gera uma requisicao para um servidor

GRAM que autentica o usuario, realiza a autenticacao local e interage com o escalonador

local para iniciar os processos. O GASS e utilizado para transferir os executaveis em MPI

e colher os resultados das saıdas e entradas padrao.

Uma vez iniciado, o MPICH-G2 seleciona o meio mais eficiente de computacao possıvel

entre dois processos, usando as bibliotecas MPI especıficas ou o Globus IO para TCP. Nao

existe entretanto meio de aglutinar as conexoes entre domınios distintos, assim, podemos

ter centenas ou milhares de conexoes Globus IO passando entre os domınios. Alem disto


todo participante da computacao distribuıda necessita ter um IP valido na Internet. Este

e um problema, especialmente porque muitas vezes em clusters somente uma das maquinas

possui um endereco valido.

Outra caracterıstica importante do MPICH-G2 e a utilizacao das informacoes especifi-

cadas no script RSL para criar aglutinamento em multiplos nıveis dos processos baseados

na topologia da rede. Alem do rank, cada processo tem um identificador de profundidade

topologica e uma cor. Sao quatro nıveis de profundidade topologica e em cada nıvel to-

pologico, um processo MPI que tem a mesma cor pode se comunicar no nıvel de rede.

Quanto a aplicacao, o MPICH esta direcionado principalmente a interligar centros de pro-

cessamento paralelo. O problema de escala para interligar um grande numero de pequenos

centros de computacao ou mesmo computadores individuais nao e avaliado.

O PACX-MPI (Parallel Computer eXtension) (BEISEL; GABRIEL; RESCH, 1997) e uma

implementacao do padrao do MPI que objetiva o acoplamento de sistema de computacao

de alto desempenho atraves de grades computacionais. O PACX-MPI e baseado em tres

conceitos fundamentais: utilizacao de dois nıveis hierarquicos utilizando bibliotecas de co-

municacao totalmente independentes para cada um destes nıveis; utilizacao das bibliotecas

especıficas locais para as operacoes internas; e, utilizacao de servidores de comunicacao. Os

dois primeiros conceitos sao bastante similares aos apresentados pelo MPICH-G2, a grande

diferenca e a utilizacao dos servidores de comunicacao entre os diferentes domınios para

empacotar as comunicacoes e evitar milhares de conexoes entre os sistemas. Alem disto a

existencia de um servidor diminui problemas com firewalls e com a necessidade de todos os

participantes da computacao precisarem enderecos validos na rede.

O PACX-MPI nao utiliza uma infraestrutura de grade para tratar problemas como

identificacao, autenticacao e submissao dos processos. Novamente e um modelo mais di-

recionado a interligacao de sıtios de processamento local, onde as regras de seguranca sao

acordadas de forma nao automatica pelos gerentes.


O MagPIe (KIELMANN et al., 1999) (magpie e um passaro que sobrevoa areas extensas

coletando coisas) e uma biblioteca MPI baseada no MPICH. Este trabalho considera que as

operacoes de comunicacao coletivas sao construıdas levando em consideracao redes locais ou

redes de sistema com uma latencia muito menor que as redes WAN (Wide Area Networks).

O principal objetivo do MagPIe e otimizar as operacoes de comunicacao coletivas em rede

WAN. Os algoritmos propostos no MagPIe levam em conta a hierarquia presente nas WANs

e procura diminuir o trafego pelo enlaces mais lentos. Sao apresentados algoritmos para

as 14 operacoes coletivas do MPI. Outro objetivo do MagPIe e evitar qualquer tipo de

modificacao nos programas tradicionais de MPI.

Resultados de simulacao mostram melhorias de 4 a 8 vezes no desempenho das operacoes

coletivas. A metodologia empregada tambem evita a necessidade de modificacoes nos

codigos escritos utilizando o MPI. O MagPIe demonstra que no ambiente de grades pode

se obter melhorias de desempenho otimizando as implementacoes das operacoes coletivas.

Em (SUPINSKI; KARONIS, 1999) e abordada a questao de como avaliar o desempenho de di-

fusoes em ambiente de grade. Em (GENAUD; GIERSCH; VIVIEN, 2003; KARONIS et al., 2000)

sao apresentadas abordagens para otimizar as operacoes coletivas em ambientes paralelos.

Em sistemas compostos por milhoes de nodos a falha ou desconexao destes nodos e um

evento frequente e deve ser considerado. Um estudo de disponibilidade com computadores

pessoais (BOLOSKY et al., 2000) dentro de uma rede de 64 mil maquinas, demonstrou que

5% a 10% das maquinas tornam-se inacessıveis no perıodo de 24 horas. Finalmente um

estudo do tempo de vida determinou que 1/3 das maquinas e desativada no perıodo de 24

horas. Esta situacao tende a ser ainda pior no ambiente de Internet. Desta forma, prover

o MPI de tolerancia a falhas e um requisito para executar com sucesso aplicacoes paralelas

no ambiente de grades. Atualmente existem diversas arquiteturas para prover tolerancia

a falhas usando diferentes tecnicas. Os diversos sistemas de tolerancia a falhas podem ser

classificados basicamente pelo nıvel em que se introduzem na pilha de software ou pela

tecnica de tolerancia a falhas empregada.


Quanto ao nıvel de introducao do mecanismo de tolerancia a falhas podemos ter os

seguintes casos: o programador da aplicacao salva periodicamente os resultados inter-

mediarios em um meio confiavel e os recupera em caso de necessidade; se instrumentaliza

o MPI para receber notificacoes de falha e aceitar reconfiguracoes do contexto de comu-

nicacao; se oferece uma implementacao do MPI que prove deteccao e recuperacao de falhas

de forma totalmente automatica. As implementacoes transparentes tem a grande vantagem

de permitir a migracao de aplicacoes ja existentes sem necessidade de modificacao.

A implementacao desse tipo de ambiente depende da utilizacao de estrategias de check-

point e/ou registro de mensagens (message logging) (ELNOZAHY et al., 2002). O checkpoint

(CHANDY; LAMPORT, 1985) e uma estrategia que armazena o estado do processo em meio

de armazenamento estavel para proposito de migracao ou recuperacao voltando a um es-

tado anterior (rollback). Um processo interrompido pode continuar a execucao a partir do

ultimo checkpoint.

A estrategia de checkpoint global pode ser dividida em: nao coordenado, induzido por

comunicacao e coordenado. Nos protocolos de checkpoint coordenado, todos os processos

coordenam seus checkpoints de forma que o estado global do sistema, composto pelos check-

points de todos os processos, seja coerente. Nos modelos de checkpoint nao coordenado,

os checkpoints de cada processo sao executados de forma independente. O problema deste

enfoque e que pode ser necessario realizar roolbacks encadeados ate a situacao inicial do

processamento para obter um estado consistente.

As estrategias de checkpoint induzido por comunicacao tentam ser uma versao in-

termediaria entre as estrategias de checkpoint coordenado e o nao coordenado. As de-

pendencias de causalidade sao analisadas em todas mensagens, forcando o checkpoint de

alguns processos quando for detectado algum risco de inconsistencia. O problema desta

estrategia e a falta de escalabilidade, que pode levar a um grande numero de checkpoints, e

os requisitos de frequencia e armazenamentos dos checkpoints que podem ser imprevisıveis.


Outra tecnica que pode ser empregada para obter tolerancia a falha e o registro de

mensagem. Esta tecnica se baseia na possibilidade de repetir a computacao realizada

submetendo os processos ao mesmo indeterminismo. No caso de um sistema de troca de

mensagens os elementos de indeterminismo sao justamente as mensagens recebidas pelos

processos.

As estrategias de registro de mensagem podem ser classificas em tres modelos (ALVISI;

MARZULLO, 1995). No registro pessimista os processos precisam aguardar que o registro

da mensagem seja feito em meio permanente, para so entao poder produzir os resultados

consequentes da mensagem. Isto simplifica a recuperacao mas impoe alto custo para as

operacoes livres de falha. No modelo otimista a aplicacao nao fica aguardando o registro

da mensagem, entretanto esta estrategia pode tornar necessaria a realizacao de rollback

em nodos que nao falharam, mas apresenta melhor desempenho em ambientes livres de

falha. A estrategia de registro causal tenta conciliar as duas estrategias, realizando registros

locais das mensagens enviadas e da relacao causal delas. Em (BOUTEILLER et al., 2003b)

e apresentada uma avaliacao sobre a eficiencia das estrategias de checkpoint e registro de

mensagens para MPI.

O CoCheck (STELLNER, 1996) e um dos primeiro esforcos para ter uma implementacao

do MPI confiavel. O CoCheck estende o mecanismos de checkpoint para um unico processo

do Condor para um sistema distribuıdo de troca de mensagens. O CoCheck e baseado

em uma implementacao propria de MPI. Um coordenador central confiavel e mantido para

realizar os procedimentos de checkpoint e rollback. Para evitar os problemas conhecidos

de inconsistencia global ou efeito domino o CoCheck descarrega todas as mensagens em

transito antes de realizar o checkpoint. Um dos problemas desta estrategia e o custo para

descarregar todas as mensagens. Outra deficiencia e a existencia de um coordenador central,

que pode criar um gargalo tanto para a execucao do checkpoint como para o rollback.

O Starfish (AGBARIA; FRIEDMAN, 1999) prove um ambiente de tolerancia a falhas ba-

seado no Ensemble (HAYDEN, 1997), que e um ambiente de comunicacao em grupo. Todos


processos MPI abrigam um daemon que participa de um grupo. As comunicacoes de con-

trole, notificacao de falhas e demais mensagens internas sao feitas utilizando as primitivas

de comunicacao de grupo do Ensemble. Uma vantagem do Starfish e a flexibilidade. A

abordagem utilizada permite que seja possıvel optar, por exemplo, em usar checkpoint co-

ordenado ou nao-coordenado. Tambem pode ser usado um modelo de tolerancia a falhas

transparente ou no nıvel do usuario.

O MPI/FT (BATCH et al., 2001) prove servicos de deteccao e recuperacao para os

processos MPI, estes servicos sao projetados para minimizar o overhead de acordo com

o modelo de execucao de aplicacao. Os modelos de execucao de aplicacao sao abstracoes

derivadas de combinacoes de topologias e tecnicas de programacao paralela. De acordo com

o modelo e utilizado checkpoint e ou redundancia de tarefas para prover a tolerancia a falhas.

A opcao por redundancia de tarefa tem o inconveniente da necessidade de implementar

tecnicas de votacao. Na arquitetura do MPI/FT tambem estao previstos diversos sensores

usados para deteccao de falhas no nıvel de aplicacao, MPI, rede ou sistema operacional.

Um coordenador central monitora o progresso da aplicacao, registra as mensagens e reinicia

os processos falhos a partir de um checkpoint.

O MPI-FT(LOUCA et al., 1991) e baseado na implementacao LAM-MPI (SQUYRES;

LUMSDAINE, 2003) do padrao MPI, e utiliza processos de monitoramento chamados obser-

vadores para prover deteccao de falhas e mecanismos de recuperacao no nıvel de processo

do MPI. O detector de falhas e baseado na verificacao da existencia dos processos MPI

nos nodos. Sao propostas duas estrategias de registro de mensagens, uma otimista, des-

centralizada, requerendo que cada processo MPI armazene as mensagens enviadas; outra

pessimista, centralizada, com todo registro no observador. Para recuperacao o MPI-FT

cria novos processos para substituir os processos falhos e reinicia a execucao. A execucao

sempre e feita do inıcio, o que implica em alto custo para a recuperacao e requer alta ca-

pacidade de armazenamento para as mensagens. A vantagem desta estrategia e nao haver

a necessidade de realizar checkpoint.


O FT-MPI (FAGG; DONGARRA, 2000) trata as falhas no nıvel de comunicacao do MPI

e deixa que a aplicacao gerencie a recuperacao. Quando uma falha e detectada todos os

processos da comunicacao sao informados sobre a falha. Esta informacao e transmitida

para a aplicacao atraves de retorno na chamada MPI. Entao a aplicacao pode tomar as

decisoes apropriadas e executar as operacoes de correcao. A vantagem desta abordagem e o

desempenho, ja que nao ha praticamente overhead envolvido. Entretanto e preciso adaptar

as aplicacoes MPI para fazer tolerancia a falhas.

O MPICH-V (BOLSICA et al., 2000) e um ambiente para tolerancia a falhas baseado em

checkpoint/rollback e registro pessimista distribuıdo de mensagens . O MPICH-V e cons-

truıdo para ser um projeto adaptavel ao maior numero de implementacoes do padrao MPI

e permitir execucao de aplicacoes sobre computadores voluntarios da Internet. O ultimo

objetivo impoe requisitos de tolerancia a falhas transparente, ou seja, a nao necessidade

de modificar as aplicacoes MPI, ser escalavel para um grande numero de nodos e envolver

apenas bibliotecas no nıvel do usuario. Considerando o ambiente de Internet de grande ins-

tabilidade dos nodos, o MPICH-V trabalha com o conceito de volatilidade. A volatilidade

e relacionado com o fato de que os nodos considerados falhos sao substituıdos por outros e

os resultados produzidos depois de sua desconexao nao sao utilizados na computacao MPI

em que ele participava.

A arquitetura do MPICH-V e composta pelas seguintes entidades: Dispatchers, Memoria

de Canal (CM - Channel Memory ), Servidor de Checkpoint (CS - Check Point Server) e os

nodos que realizam a computacao propriamente dita. Os CMs sao responsaveis por prover

o registro de mensagens, ou seja, guardar o contexto de comunicacao. Os CMs tunelam

e servem de repositorios para as mensagens do sistema. Cada CM e responsavel por um

conjunto de nodos, assim para cada nodo existe um unico CM responsavel chamado de

home CM. Todas mensagens enviadas para um nodo sao enviadas por seu home CM. Para

cada nodo, o contexto de execucao e salvo, periodicamente provocado pela recepcao de um

sinal, no CS.


O dispatcher faz a coordenacao dos recursos necessarios para realizar uma determinada

computacao. Para isto atribui nodos para executar o CM, CS e os processo do MPI. Alem

disto o dispatcher precisa armazenar o mapa de atribuicao dos CMs e CSs em um Registro

de Servico Estavel. Assim quando um nodo executa uma aplicacao MPI ele primeiro

contacta o Servico de Registro que resolve o endereco do CS e CM de acordo com seu rank

no MPI. O dispatcher tambem e responsavel por realizar a deteccao de falhas. Durante a

execucao dos testes os nodos enviam heartbeats para ele, quando um timeout ocorre uma

nova tarefa MPI e lancada para substituir a falha, e os contextos de mensagem e execucao

sao restaurados. Quanto ao nodo falho, caso tente se reintegrar ao sistema sera reintegrado

como um novo nodo, ja que ele ja foi substituıdo na computacao.

O MPICH-V2 (BOUTEILLER et al., 2003a) e a geracao seguinte do MPICH-V, tambem

sendo baseado em checkpoint nao coordenado e registro de mensagens pessimista. O

MPICH-V2 se preocupa com o fato de que o CM impoe um grande impacto no desem-

penho, tornando alto o custo da tolerancia a falhas, ja que para se obter um desempenho

satisfatorio existe a necessidade de utilizar-se um grande numero de CMs. A estrategia do

MPICH-V2 e dividir o registro das mensagens em duas partes: a mensagem propriamente

dita e registrada no nodo de processamento que a esta gerando; o evento correspondente ao

envio da mensagem e armazenado em um registrador de eventos confiavel. A quantidade de

informacao armazenada no registrador de eventos e proporcional ao numero de mensagens

transmitidas e nao ao tamanho.

O registro dos eventos serve para armazenar as informacoes de dependencia entre as

mensagens trocadas pelos processadores. Um relogio logico e usado para criar uma ordem

nestas mensagens. O objetivo e poder repetir as comunicacoes feitas entre os nodos e

reconstruir informacoes perdidas em caso de falha, ja que as mensagens sao registradas

apenas localmente. A estrategia do MPICH-V2 e uma melhoria consideravel sob a versao

anterior, entretanto a arquitetura ainda continua necessitando elementos confiaveis como

o registrador de eventos, o dispatcher e o CSs. O que cria problemas de escalabilidade e

2.3 Redes Overlay Peer-to-Peer 27

deixar o sistema vulneravel a falhas destes componentes.

2.3 Redes Overlay Peer-to-Peer

Recentemente, redes overlay tem sido propostas em sistemas P2P como alternativa

para solucionar os problemas de escalabilidade (DOVAL; O’MAHONY, 2003). A computacao

P2P e uma abordagem para compartilhar grande quantidade de recursos. Na computacao

P2P as maquinas compartilham dados ou recursos, como ciclos de computacao ociosos

ou capacidade de armazenamento, via Internet ou redes privadas. Em uma rede P2P a

nocao de cliente e servidor e relativa, de forma que os processos apresentam funcoes tanto

de clientes como de servidores. Assim as maquinas podem se comunicar diretamente e

gerenciar suas tarefas sem utilizar servidores centrais. Isto permite que a computacao P2P

seja mais escalavel que o modelo tradicional cliente-servidor, apresentando-se como uma

das melhores abordagens para criar redes globais de compartilhamento de recursos.

Encontramos redes overlay em sistemas P2P implementando as mais diversas topo-

logias, como: malha, no Pastry (ROWSTRON; DRUSCHEL, 2001) e Tapestry (ZHAO et al.,

2004); anel, no Chord (STOICA et al., 2001); torus d-dimensional, no CAN (RATNASAMY et

al., 2001); e borboleta em (FIAT; SAIA, 2002) e (SAIA et al., 2002). Estas redes overlay orga-

nizam a rede subjacente de forma a facilitar a busca de objetos armazenados nos nodos que

compoem o sistema. Esta estrategia melhora a escalabilidade do sistema, evitando o uso

de algoritmos de inundacao para propagar requisicoes de busca, por exemplo. As tabelas

hash distribuıdas sao uma das tecnicas mais comuns empregadas para construir estas redes

(BALAKRISHNAN et al., 2003).

O CAN e uma das propostas de implementacao distribuıda de tabelas hash. O CAN

utiliza uma abordagem geometrica para organizar os nodos. Sao atribuıdas posicoes para

os nodos em um espaco d-dimensional em um d−torus. Para organizar os nodos e atribuir


objetos para compartilhamento, o CAN usa funcoes d-hash, o que permite ao nodo obter

uma chave espaco d para si proprio. Cada nodo mantem uma tabela com O(d) entradas e

qualquer nodo pode ser alcancado em O(dN1/d) saltos, em um sistema com N nodos. Desta

forma, a tabela de roteamento nao cresce de acordo com o numero de nodos no sistema, mas

o numero de saltos necessarios para atingir o destino e maior que logN , especificamente

O(dN1/d).

O Pastry e uma rede P2P para localizacao de objetos e roteamento de mensagens. No

Pastry cada nodo e identificado por um identificador unico de 128-bits. Este identificador

e utilizado para indicar a posicao do nodo em um espaco circular. Cada aplicacao pode

atribuir um unico identificador, ou chave, para um objeto. Esta chave e mapeada para

um nodo na rede e as mensagens sao roteadas pelos nodos cujos identificadores estao

numericamente mais proximos da chave.

Considerando uma rede com N nodos, o Pastry pode rotear uma mensagem para o

nodo mais proximo de uma dada chave com um numero de saltos na ordem de O(logN),

mantendo uma tabela de roteamento com um numero de entradas na ordem de O(logN)

linhas. As entradas em uma linha n da tabela, se referem aos nodos cujo identificador com-

partilha os n primeiros dıgitos, mas nao o (n+ 1)−esimo bit, com o nodo atual. Associado

a cada entrada da tabela de roteamento esta o endereco IP dos nodos mais proximo (a

proximidade e estimada pelo tempo de round trip). Alem da tabela de roteamento, cada

nodo mantem uma lista dos vizinhos imediatos, chamada leaf set.

As mensagens sao roteadas de acordo com a maior coincidencia com a chave destino.

Se a chave estiver na faixa dos identificadores contidos no leaf set, entao a mensagem e

roteada para o nodo cujo identificador e o mais proximo da chave. Caso contrario, o nodo

busca em sua tabela pelo nodo cujo identificador possua um um prefixo com um numero

maior de bits coincidentes com a chave do que o nodo atual. Se este nodo nao existir,

a mensagem e enviada para um nodo cujo identificador possua um prefixo com o mesmo

numero de bits coincidentes com a chave que o nodo atual, mas que esteja numericamente


mais proximo da chave.

O Tapestry e bastante similar ao Pastry, mas tem uma abordagem diferente para ma-

pear as chaves para os nodos. No Tapestry nao existe o leaf set e a vizinhanca de nodos

nao e conhecida. Os identificadores tem 160 bits que sao divididos em dıgitos de 16 bits.

As mensagens sao encaminhadas sucessivamente para nodos com um identificadores com

numero de dıgitos coincidentes progressivamente maiores. Quando a tabela de roteamento

de um nodo nao tem uma entrada para um nodo com o n−esimo dıgito coincidente, a

mensagem e encaminhada para o nodo cujo identificador possua o valor mais proximo no

n−esimo dıgito. Este procedimento e chamado surrogate routing e mapeia as chaves para

um unico nodo com um identificador similar. O numero esperado de saltos de roteamento

e log16N .

O Chord usa um espaco circular de identificadores de 160 bits para organizar os nodos.

Ao contrario do Pastry e Tapestry, o Chord encaminha mensagens apenas no sentido horario

do espaco circular de identificadores. Ao inves do roteamento baseado em prefixo do Pastry,

o Chord mantem uma tabela chamada de finger table. Esta tabela contem o identificador e o

endereco IP de ate 160 nodos. A i−esima entrada na finger table do nodo n se refere ao nodo

que sucede n em pelo menos em n+2i−1 saltos no espaco circular de identificadores. Assim,

a primeira entrada aponta para os sucessor direto do nodo n, e as entradas subsequentes se

referem a nodos com distancia repetidamente dobradas de n. Cada nodo tambem mantem

ponteiros para seus predecessores e para os seus k sucessores no espaco de identificadores.

O numero de saltos esperados para rotear uma mensagem no Chord e 1/2log2N .

As redes overlay P2P descritas acima apresentam uma abordagem distinta da rede

overlay proposta neste trabalho. Estao destinadas para armazenar e recuperar conteudo

organizando a topologia do sistema em funcao das chaves dos objetos armazenados. O

HyperBone visa oferecer servicos de comunicacao e monitoracao permitindo a execucao de

aplicacoes distribuıdas, especialmente em sistemas instaveis. A instabilidade do sistema

e abordada por alguns trabalhos em P2P (FIAT; SAIA, 2002; SAIA et al., 2002), mas no-


vamente estes trabalhos sao direcionadas especificamente para a busca de informacao, o

foco e como manter acessıvel toda ou parte da informacao armazenada na rede mesmo em

caso de falha dos nodos. A questao da deteccao de falhas em redes overlay e tratada em

(ZHUANG et al., 2005), onde sao avaliadas diversas classes de algoritmos. O estudo emprega

modelos analıticos, simulacao e experimentacao usando metricas como tempo de deteccao,

probabilidade de falsos positivos, overhead de controle e taxa de perda de pacotes. As

conclusoes deste trabalho evidenciam a importancia do compartilhamento de informacao

de monitoracao e a necessidade de sistemas eficientes de monitoracao.

Quanto ao uso de hipercubos como topologia para rede virtual, podemos citar o Hyper-

cup (SCHLOSSER et al., 2002). O algoritmo proposto naquele trabalho baseia-se em posicoes

livres e ocupadas em um hipercubo. Um nodo que funciona como peer de uma rede P2P

e deseja se integrar ao sistema faz um pedido de entrada e recebe uma posicao livre no

hipercubo. Entao, esta posicao se torna ocupada ate que este nodo deixe o sistema. Para

manter a integridade do sistema uma mensagem de broadcast e enviada para avisar todos

os nodos que uma posicao do hipercubo se tornou ocupada ou vazia. Um problema no Hy-

percup e que o sistema somente e capaz de tratar a ocorrencia de um unico evento, entrada

ou saıda de um unico nodo a cada vez: o tratamento de multiplos eventos simultaneos e

apontada como trabalho futuro.

31

3 Diagnostico Distribuıdo

Considere um sistema com N nodos. Assuma que o sistema e totalmente conectado,

ou seja, existe um enlace de comunicacao entre qualquer par de nodos, considere ainda que

os nodos podem estar falhos ou sem-falhas e que os enlaces de comunicacao nao falham. O

objetivo do diagnostico distribuıdo em nıvel de sistema e permitir que todos os nodos sem-

falhas determinem o estado, falho ou sem-falhas, de todos os nodos do sistema. Os nodos

em um sistema de diagnostico sao capazes de testar outros nodos e determinar seu estado

corretamente. Utilizando algoritmos de diagnostico distribuıdo e possıvel construir siste-

mas de monitoracao de rede tolerante a falhas (BIANCHINI; BUSKENS, 1991). Este capıtulo

apresenta conceitos e algoritmos de diagnostico em nıvel de sistema, que serao posterior-

mente utilizados na apresentacao do algoritmo DiVHA, utilizado para a manutencao na

topologia virtual do HyperBone.

3.1 O Modelo PMC

O modelo PMC foi proposto por Preparata, Metze e Chien, o nome do modelo vem

das iniciais dos nomes dos autores (PREPARATA; CHIEN, 1967). O modelo PMC utiliza a

teoria de grafos em seu formalismo, os vertices representam unidades do sistema capazes

de testar outras unidades, ou nodos, e as arestas direcionadas indicam os testes realizados.

Uma aresta saindo do nodo u para o nodo v significa que o nodo u testa o nodo v. Cada

teste corresponde a um estımulo enviado cuja resposta sera classificada em pass ou fail

mapeados respectivamente para 0 e 1 nos pesos das arestas. O conjunto destes resultados

3.1 O Modelo PMC 32

e definido como sendo a sındrome do sistema.

Para determinar o estado de cada nodo do sistema e necessario analisar a sındrome,

onde resume-se a tarefa de diagnostico. Nem sempre a existencia de um teste com o

resultado fail significa que o nodo testado e falho. Isto porque o resultado de um teste so

deve ser considerado caso o nodo testador nao esteja falho. Se o nodo testador for falho o

resultado do teste nao e previsıvel e nao informa nada a respeito do nodo testado.

No modelo PMC nao sao consideradas falhas de enlaces e o sistema e representado por

um grafo completo. Os testes realizados sao fixados previamente e o conjunto destes testes

determina se um sistema pode ou nao ser diagnosticado. Em (PREPARATA; CHIEN, 1967;

HAKIMI; AMIN, 1974) sao examinadas as condicoes necessarias e suficientes para que um

conjunto de testes permita obter o diagnostico correto do sistema.

Um sistema e dito t-diagnosticavel em um passo quando e possıvel identificar todas

as unidades falhas atraves da analise da sındrome. Para que um sistema com N nodos

seja t-diagnosticavel em um passo, o numero de unidades falhas, t, nao pode ultrapassar

N−12

. Alem disto cada unidade deve ser testada por pelo menos t outras unidades. Entao

num sistema com N = 2t + 1 sao necessarios N ∗ N−12

testes, portanto o numero de testes

requeridos e O(N2).

A estrategia de fixar previamente todos os testes pode dificultar o diagnostico, pois

e preciso atribuir antecipadamente testes que compensem os testes que deixam de ser

executados pelas unidades com falhas. Desta forma, foram criados os algoritmos adaptativos

(HAKIMI; NAKAJIMA, 1984) onde os testes nao sao fixos, sendo determinados de acordo com

os resultados dos testes realizados anteriormente.

Outra caracterıstica do modelo PMC e a necessidade de um nodo que receba todos os

resultados dos testes e realize o diagnostico. A ideia de eliminar esta unidade, distribuindo

a tarefa de diagnostico entre os nodos que realizam os testes e que fez surgir os algoritmos

distribuıdos (HOSSEINI; KUHL; REDDY, 1984).

3.2 O Algoritmo Adaptive-DSD 33

3.2 O Algoritmo Adaptive-DSD

O algoritmo Adaptive Distributed Sytem-level Diagnosis (ADSD) (BIANCHINI; BUS-

KENS, 1991, 1992) e um algoritmo de diagnostico em nıvel de sistema ao mesmo tempo

distribuıdo e adaptativo criado por Bianchini e Buskens. Por ser distribuıdo, nao existe

uma unidade central para realizacao do diagnostico. Por ser adaptativo, a configuracao dos

testes vai alterando-se durante a execucao do algoritmo.

Os algoritmos adaptativos possuem a nocao de rodadas de testes (testing rounds), que

e o perıodo de tempo necessario para que todos os nodos sem-falhas executem os testes

que lhe foram atribuıdos. No algoritmo ADSD a rodada de testes e definida como o tempo

necessario para que todos os nodos sem-falha do sistema testem pelo menos um nodo sem-

falhas. A latencia e definida como o numero de rodadas de testes necessarias para que todos

os nodos do sistema realizem o diagnostico de um evento ocorrido. Um evento e a transicao

de um nodo do estado de sem-falhas para falho ou do estado de falho para sem-falhas. O

numero de testes realizados a cada rodada de testes e a latencia sao medidas utilizadas

para comparar a eficiencia de algoritmos de diagnostico adaptativos.

No algoritmo ADSD cada nodo testa outros nodos ate encontrar um nodo sem-falhas do

qual colhe informacoes para atualizar suas informacoes de diagnostico. Uma consequencia

da estrategia de testes do ADSD e que cada nodo e testado por um unico nodo sem-falhas

a cada rodada.

Em um sistema com N nodos executando o algoritmo ADSD, os nodos sao identificados

como u1, u2,...,uN . O nodo ui tambem e chamado nodo i. A adicao usada e modulo N ,

de modo que o nodo uN e seguido por uN + 1 que e u0, formando um anel de nodos. Os

testes sao realizados sequencialmente, assim ui testa ui+1 e seguintes ate encontrar um

nodo sem-falhas, entao atualiza sua informacao local de diagnostico com as informacoes

lidas do nodo testado. Estas informacoes sao resultantes tanto de testes realizados pelo

nodo testado como de informacoes lidas de outros nodos.

3.3 O Algoritmo Hi-ADSD 34

0

2

6

7

4

3

5

1

Figura 2: Sistema executando o algoritmo ADSD.

A figura 2 mostra um sistema executando o algoritmo ADSD. Os nodos assinalados com

“X” estao falhos e os nao assinalados sem-falhas. Em uma rodada de testes cada nodo testa

sequencialmente seus sucesssores. O nodo 0, por exemplo, testa o nodo 1, descobrindo que

o nodo 1 esta falho, entao testa o nodo 2, sem-falhas, lendo as informacoes de diagnostico

dele. De forma analoga comportam-se os nodos 2, 3, 6 e 7.

Em termos de quantidade de testes a cada rodada, o algoritmo ADSD e considerado

eficiente sendo executados no maximo N testes a cada rodada. Quanto a latencia, podem

ser necessarias ate N rodadas para que todos os nodos realizem o diagnostico de um evento.

Isto ocorre porque a informacao sobre o estado de um nodo e passada para apenas um novo

nodo a cada rodada. Como em cada rodada os testes estao sendo feitos sequencialmente

por u0, u1, etc, se o nodo uN falhar, entao o nodo uN−1 detecta a falha, mas apenas na

outra rodada o nodo uN−2 le informacoes de uN−1 e descobre a falha em uN , da mesma

forma os demais nodos vao obtendo a informacao nas rodadas de teses seguintes. Com isto,

podem ser necessarias N rodadas de testes ate a informacao da falha de uN chegar a u0.

3.3 O Algoritmo Hi-ADSD

O algoritmo Hierarchical Adaptive Distributed System-Level Diagnosis (Hi-ADSD) (DU-

ARTE Jr.; NANYA, 1998) e hierarquico, alem de ser distribuıdo e adaptativo, realizando testes


baseados numa estrategia de dividir para conquistar.

A hierarquizacao dos testes e alcancada utilizando o conceito de clusters. Os clusters

sao conjuntos de nodos testados a cada rodada, o tamanho aumenta progressivamente a

cada rodada sempre sendo uma potencia de dois. Um cluster de p nodos nj, ..., nj+p−1 onde

j MODp = 0 e p e uma potencia de dois, e definido recursivamente como um nodo, quando

p = 1; ou como a uniao de dois clusters, um contendo os nodos nj, ..., nj+p/2−1 e outro

nj+p/2, ..., nj+p−1. A figura 3 mostra um sistema de oito nodos organizado em clusters.

0 1

7632

4 5

Figura 3: Sistema de 8 nodos agrupados em clusters no algoritmo Hi-ADSD.

Um nodo sem-falhas inicialmente realiza testes em clusters de tamanho 1 (20), nas

proximas rodadas os clusters tem tamanho 2 (21), 4 (22), 8 (23) ate atingir N/2 (2(log2N)−1)

nodos. A lista ordenada de nodos testados por um determinado nodo i em um cluster de

tamanho 2s−1 e dada por Ci,s. A expressao que caracteriza Ci,s e dada como segue:

Ci,s ={nt|t = (i MOD 2s + 2s−1 + j) MOD 2s−1+a+

(i DIV 2s) ∗ 2s + b ∗ 2s−1; j = 0, 1, ..., 2s−1 − 1} ,

onde

a =

1 se MOD 2s < 2s−1

0 outros casos

b =

1 se a = 1 AND (i MOD 2s + 2s−1 + j)

MOD 2s−1+a + (i DIV 2s) ∗ 2s < i

0 outros casos

Quando um nodo i realiza testes em nodos pertencentes a Ci,s, ele executa testes sequen-

cialmente ate encontrar um nodo sem-falhas, ou ate descobrir que todos os outros nodos


estao falhos. Pela funcao Ci,s quando dois nodos diferentes testam nodos de um cluster eles

iniciam testando nodos diferentes. A tabela 1 mostra a funcao Ci,s para um sistema com 8

nodos.

Tabela 1: Ci,s para um sistema com 8 nodos.

s C0,s C1,s C2,s C3,s C4,s C5,s C6,s C7,s

1 1 0 3 2 5 4 7 62 2, 3 3, 2 0, 1 1, 0 6, 7 7, 6 4, 5 5, 43 4, 5, 6, 7 5, 6, 7, 4 6, 7, 4, 5 7, 4, 5, 6 0, 1, 2, 3 1, 2, 3, 0 2, 3, 0, 1 3, 0, 1, 2

Quando um nodo sem-falhas e testado ele fornece informacoes sobre todos os nodos da

Ci,s ao qual ele pertence. Se nenhum nodo sem-falhas e encontrado em uma determinada

Ci,s o nodo i passa a testar Ci,s+1 no mesmo intervalo de testes, ate encontrar um nodo

livre de falhas, ou descobrir que todos os nodos estao falhos. A figura 4 mostra os clusters

testados pelo nodo 0. Inicialmente o nodo 0 testa o nodo 1 do cluster de tamanho 1, na

proxima rodada de testes testa o cluster de tamanho 2 composto pelos nodos 2 e 3, por fim

testa o cluster de tamanho 4 que contem os nodos 4, 5, 6 e 7 e entao retorna para testar o

cluster de tamanho 0.

0 1

2 3

4 5 6 7

Figura 4: Clusters testados pelo nodo 0 executando o algoritmo Hi-ADSD.

O algoritmo realiza testes de forma assıncrona, isto significa que em uma mesma ro-

dada os nodos podem estar testando clusters de tamanhos diferentes. A latencia pode

chegar a, no maximo, (log2N)2 rodadas de testes. Simulacoes (DUARTE Jr.; NANYA, 1998)

demonstraram que a latencia em geral e menor que (log2N)2, e que se os nodos estiverem

realizando os testes de forma sincronizada a latencia e da ordem de log2N rodadas de teste.

3.4 O Algoritmo Hi-ADSD with Detours 37

No algoritmo Hi-ADSD existe uma situacao de falhas em que pode ser executados N2/4

testes em uma unica rodada. Suponha que exista um cluster com tamanho N/2 onde todos

os nodos estao falhos e que os N/2 nodos restantes e sem-falhas realizem testes sobre este

cluster falho. Entao teremos N/2 nodos realizando N/2 cada, resultando em um total de

N2/4 testes. Portanto, neste pior caso o numero de testes executados em uma rodada pode

ser da ordem O(N2), que e a mesma ordem de complexidade de algoritmos de forca bruta.

3.4 O Algoritmo Hi-ADSD with Detours

Com o objetivo de diminuir o numero maximo de testes realizados no algoritmo Hi-

ADSD surgiu o algoritmo Hi-ADSD with Detours (DUARTE Jr.; BRAWERMAN; ALBINI,

1998). O objetivo e cumprido por meio de uma mudanca na estrategia de testes. O

resultado e que a cada log2N rodadas sao executados no maximo Nlog2N testes. Os clus-

ters sao organizados da mesma maneira que no algoritmo Hi-ADSD e a latencia tambem e

mantida.

No algoritmo Hi-ADSD with Detours, quando o nodo testa um nodo falho de um de-

terminado cluster ele nao continua a testar os demais nodos deste cluster. Nesta situacao o

cluster e dito bloqueado e o nodo testador procura obter informacoes sobre os nodos deste

cluster ao testar outros clusters. As informacoes podem ser obtidas por caminhos alter-

nativos no grafo de testes. Estes caminhos alternativos sao chamados de detours. Testes

extras sao realizados nos nodos do cluster bloqueado para os quais nao foram encontrados

detours.

Os nodos do algoritmo Hi-ADSD with Detours sao organizados em clusters da mesma

forma que no algoritmo Hi-ADSD. A definicao de Ci,s tambem e a mesma adotada no

Hi-ADSD original, apresentada na secao anterior.

Uma rodada de testes e definida como o perıodo de tempo no qual todos os nodos sem-

falhas testam um cluster. A latencia do algoritmo e definida como o numero de rodadas


de testes necessarias para que todos os nodos sem-falha do sistema realizem o diagnostico

de um evento. Considera-se que durante o diagnostico de um evento um novo evento nao

ocorre no sistema.

O grafo de testes livres de falhas do sistema, T (S), e um grafo onde os vertices sao os

nodos do sistema e uma aresta direcionada entre o nodo i e j indica que o nodo i testou

o nodo j como sem-falhas no ultimo intervalo de teste. Quando todos os nodos estao

sem-falhas T (S) e um hipercubo.

A distancia de diagnostico entre o nodo i e o nodo p, di,p, e a menor distancia entre

os nodos i e p em T (S). Por exemplo, na figura 5, podemos verificar que d0,5 = 2, ou

seja a distancia de diagnostico do nodo 0 ate o nodo 5 e 2. Ainda, define-se Di,k como

sendo o conjunto de todos os nodos p tal que di,p ≤ k. Assim de acordo com a figura 5,

D0,1 = {1, 2, 4}, D0,2 = {1, 2, 4, 3, 5, 6} e D0,3 = {1, 2, 4, 3, 5, 6, 7}.

2

5

41

3 6

7

0

Figura 5: O grafo T (S) para um sistema com 8 nodos.

Ri,s,p e a lista ordenada de nodos que podem ser alcancadas pelo nodo i a partir do

nodo p com distancia de diagnostico menor ou igual a s e menor que a distancia do nodo

i quando todos os nodos estao sem-falhas. Ri,s,p e dada pela expressao abaixo. A figura 5

mostra R0,3,2 = {6, 7}.

Ri,s,p = (Ci,s ∩ Dp,s−1) − Di,di,p

Um detour do nodo i ao nodo j e um caminho em T (S) do nodo i ao nodo j passando


por nodos fora do cluster ao qual o nodo j pertence. O detour deve ter exatamente o mesmo

numero de arestas do caminho mais curto entre i e j no caminho que contem apenas nodos

do cluster ao qual j pertence.

A figura 6 mostra um sistema com 8 nodos executando o algoritmo Hi-ADSD with

Detours, os nodos assinalados estao falhos. As linhas pontilhadas mostram os testes que

seriam executados pelo Hi-ADSD sem detours para diagnosticar os nodos 5, 6 e 7. No Hi-

ADSD with Detours a informacao do nodo 5 e obtida atraves do nodo 1, e as informacoes

sobre os nodos 6 e 7 sao obtidas atraves do nodo 2.

0 1

7632

4 5

Figura 6: Sistema executando o algoritmo Hi-ADSD with Detours.

A especificacao do algoritmo e feita utilizando as funcoes more-info e more-tests. O

testador executa more-info depois de testar um nodo sem-falhas para determinar se e ne-

cessario obter informacoes adicionais pelo nodo testado. A funcao e dada abaixo, onde:

nodo i e o testador; nodo p e o nodo sem-falhas testado em Ci,s′ ; a lista Ri,log2N,p contem

todos os nodos cujas informacoes podem ser obtidas pelo nodo i atraves do nodo p; e o

conjunto Bi,s contem os nodos bloqueados de um dado Ci,s. Quando o nodo testado em

um dado cluster esta falho e o testador nao obtem informacoes sobre os outros nodos do

cluster, estes nodos sao chamados de bloqueados.

more-info(i, p) = Ri,log2N,p ∩ Bi,s, s′ < s <= log2N

A funcao more-tests e executada quando um nodo falho e testado, para determinar se


e necessario executar testes adicionais no mesmo cluster, ou seja, se nao existem detours

para os nodos bloqueados. A funcao more-tests e dada pela formula abaixo, onde o nodo i

e o testador, o nodo p e o nodo testado falho, Ci,s,p a lista contendo todos nodos sobre os

quais o nodo p pode dar informacao para o nodo i e s varia de acordo com o Ci,s ao qual p

pertence:

more-testes(i, s) = Bi,s − Ri,s,p|p ∈ Ci,s′ e 1 <= s′ < s

O pseudo codigo e apresentado na figura 7.

ALGORITHM Hi−ADSD with Detours { at node i }i n i t i a l i z e a l l s e t s Bi , s empty ;REPEAT FOREVER

FOR s = 1 to LogN DOp := f i r s t node in Ci , st e s t (p)IF p i s f au l t−f r e e THEN

get Ci , s d i a gno s i s in fo rmat ion ;update Bi , s ;get more in fo ( i , p ) d i a gno s i s in fo rmat ion ;update Bi , s ;

ELSE p i s f a u l t y THENBi , s = Ci , s − pWHILE more−t e s t s ( i , s ) i s not empty DO

k = f i r s t node in more t e s t s ( i , s )t e s t ( k ) ; Bi , s = Bi , s − k ;IF k i s f au l t−f r e e THEN

get Bi , s d i a gno s i s in fo rmat ion ; update Bi , s ;get more in fo ( i , k ) d i a gno s i s in fo rmat ion ; update Bi , s ;

END IFEND WHILE

END IFEND FOR

END REPEAT

Figura 7: Especificacao do algoritmo Hi-ADSD with Detours.

Simulacoes mostram que o Hi-ADSD with Detours (DUARTE Jr.; BRAWERMAN; ALBINI,

1998) precisa de um numero menor de testes em relacao ao Hi-ADSD original em diversas

situacoes de falhas. Na tabela 2 estao os resultados da simulacao de um sistema com

64 nodos. Os resultados mostram que o emprego de detours diminui o numero de testes

necessarios para completar o diagnostico do sistema.

3.5 O Algoritmo Hi-ADSD with Timestamps 41

Tabela 2: Simulacoes de um sistema com 64 nodos executando os algoritmos Hi-ADSD eHi-ADSD com detours

Situacao de Falha Hi-ADSD Hi-ADSD with Detours

32 nodos falhos de 383 285forma aleatoriaPior caso do Hi-ADSD 1184 191Pior caso do Hi-ADSD 384 384with Detours

3.5 O Algoritmo Hi-ADSD with Timestamps

Eventos sao definidos como a mudanca de estado de um nodo detectada pelo algoritmo

de diagnostico. Um evento ocorre quando um nodo falho se torna sem-falhas ou quando

um nodo sem-falhas se torna falho. Os algoritmos hierarquicos baseados no modelo PMC

assumem situacoes de falhas estaticas, nao podendo haver um novo evento enquanto todos

os nodos sem-falhas do sistema nao detectarem o evento anterior. Esta assercao e artificial

e pode nao ser garantida facilmente em um sistema real.

O algoritmo Hi-ADSD with Timestamps (DUARTE Jr.; ALBINI; BRAWERMAN, 2000) e

um algoritmo baseado no algoritmo Hi-ADSD with Detours e trabalha com falhas dinamicas,

onde eventos podem ocorrer antes do diagnostico do evento anterior ter sido completado

por todos os nodos. O timestamp e uma informacao guardada sobre o estado de cada

nodo do sistema, a informacao e um contador incrementado a cada mudanca de estado

(RANGARAJAN; DAHBURA; ZIEGLER, 1995; DUARTE Jr. et al., 1997). A utilidade do times-

tamp e permitir datar informacoes, distinguindo as informacoes mais atualizadas das menos

atualizadas.

Ao testar um nodo sem-falhas em um cluster, no algoritmo Hi-ADSD with Timestamps,

nao sao obtidas somente informacoes sobre o cluster do nodo testado e possıveis detours.

Sempre que um nodo i testa um nodo j como sem-falhas sao lidas informacoes de diagnostico

de todos os nodos que estao a uma distancia de diagnostico de ate log2N − 1 do nodo i

passando pelo nodo j, um conjunto que tem sempre N/2 nodos. Como as informacoes


sobre um determinado nodo podem ser obtidas a partir de varios nodos testados, entao

emprega-se o timestamp para selecionar a informacao de diagnostico mais recente.

A latencia media do algoritmo Hi-ADSD with Timestamps e reduzida em relacao ao

algoritmo Hi-ADSD with Detours. O numero maximo de testes e o mesmo do Hi-ADSD

with Detours ja que a estrategia de testes e a mesma. Simulacoes feitas em sistemas

de 512 nodos mostram que o algoritmo Hi-ADSD with Timestamps (DUARTE Jr.; ALBINI;

BRAWERMAN, 2000) e em media quatro vezes mais rapido para completar o diagnostico de

uma falha que o Hi-ADSD with Detours. Para este sistema de 512 nodos o Hi-ADSD with

Detours teve uma latencia de 40 rodadas de teste, enquanto no Hi-ADSD with Timestamps

a latencia foi de 12 rodadas.

3.5.1 Diagnostico Dinamico de Eventos

Uma das melhorias do Hi-ADSD with Timestamps em relacao aos outros algoritmos

hierarquicos e a capacidade de diagnosticar certos eventos dinamicos, ou seja, eventos

que ocorrem antes do diagnostico do evento anterior por todos os nodos sem-falha. O

modelo de falhas estatico, adotado pelos demais algoritmos hierarquicos de diagnostico

apresentados, considera que um novo evento nao ocorre antes que todos os nodos sem-falhas

tenham diagnosticado o evento anterior. O modelo estatico considera que o algoritmo de

diagnostico esta analisando uma imagem retirada do sistema em um determinado intervalo

de tempo (BLOUGH; BROWN, 1999). O modelo estatico entretanto nao e adequado para

um ambiente real, uma vez que falhas podem ocorrer durante a execucao do algoritmo de

diagnostico. Considerando-se um modelo de falhas dinamico e necessaria a especificacao

de um procedimento de recuperacao para os nodos que sao reparados durante a execucao

do algoritmo.

Quando um nodo falho e reparado, ele nao tem informacoes de diagnostico sobre o sis-

tema. A medida em que o nodo comeca a executar testes e obter informacoes de diagnostico

de outros nodos sem-falhas ele atualiza sua informacao de diagnostico. E necessario distin-


guir informacoes de diagnostico atualizadas e nao atualizadas. Caso contrario a informacao

incorreta, nao atualizada, pode ser propagada pelo sistema.

Considere que as informacoes de diagnostico que cada nodo mantem sobre os nodos

do sistema sao organizadas em uma tabela, onde cada linha corresponde a um nodo. Um

campo chamado u-bit pode ser inserido em cada linha e utilizado para indicar se a in-

formacao de diagnostico foi ou nao atualizada desde a inicializacao do nodo. Este campo

pode ser implementado como um bit, cujo valor 1 indica que informacao e atualizada e 0

em outro caso.

Ao reparar-se de uma falha o nodo atribui a todos os seus u-bits o valor 0. Ao encon-

trar um nodo sem-falhas que ja tenha completado o processo de inicializacao ele obtem

informacoes de todos os nodos do sistema. Caso um testador se recupere e teste todos os

nodos como falhos (ou nao encontre nenhum nodo sem-falhas atualizado) entao ele pre-

cisa atribuir todos u-bits para 1. Durante a inicializacao do algoritmo ocorre algo similar,

pois apesar de encontrar nodos sem-falhas estes nodos ainda nao possuem informacao de

diagnostico atualizadas, ou seja, tem o u-bit igual a 0.

3.5.2 Especificacao do Algoritmo

Considere um sistema S composto de N nodos, que podem estar falhos ou sem-falhas.

Assuma que o sistema e totalmente conectado, ou seja, existe um enlace de comunicacao

entre qualquer par de nodos, e os enlaces nao falham. Neste sistema os nodos sem-falhas

sao capazes de testar e comunicar os resultados de forma confiavel.

O intervalo de testes e definido como o perıodo de tempo no qual um nodo sem-falhas

testa um cluster. O grafo de testes livres de falhas do sistema, T (S), e um grafo direcionado

cujos vertices representam os nodos do sistema e uma aresta direcionada entre o nodo i e j

indica que o nodo i testou o nodo j como sem-falhas no ultimo intervalo de teste. Quando

todos os nodos estao sem-falhas T (S) e um hipercubo. A distancia de diagnostico entre o


nodo i e o nodo p, di,p, e a menor distancia entre os nodos i e p em T (S).

O grafo de testes livres de falhas de i, TFFi, e um grafo direcionado cujos vertices sao

os nodos de S. Existe a aresta direcionada de a para b, ab, em TFFi se ab pertence a T (S)

e di,a < di,b. A figura 8 mostra TFF0 para um sistema com 8 nodos.

2

5

41

3 6

7

0

Figura 8: O grafo TFF0 para um sistema com 8 nodos.

Ci,s,p e definido como a lista ordenada de nodos que podem ser alcancados pelo nodo i

a partir do nodo p com uma distancia de diagnostico menor ou igual a s − 1. A figura 9

mostra C0,3,2. A funcao Ci,s,p corresponde ao cluster testado quando o nodo i e o testador.

2

5

41

3 6

7

0

Figura 9: Um exemplo de Ci,s,p: C0,3,2.

A estrategia de testes do algoritmo Hi-ADSD with Timestamps e a mesma utilizada pelo

algoritmo Hi-ADSD with Detours. A cada intervalo de testes um nodo testa um cluster.

Apos log2N intervalos de testes o primeiro cluster e testado novamente. A figura 10 mostra


os clusters testados pelo nodo 0. Quando o nodo 0 testa o nodo 1 obtem informacoes sobre

os nodos do cluster C0,3,1, ou seja, nodo 1, nodo 3, nodo 5 e nodo 7. Os outros dois clusters

testados, C0,3,2 e C0,3,4, sao analogos.

0

2

5

41

3 6

7

Figura 10: Clusters testados pelo nodo 0.

No algoritmo Hi-ADSD with Timestamps sempre que um nodo sem-falhas e testado

sao obtidas informacoes do conjunto de nodos com distancia de no maximo log2N − 1, ou

seja, sobre N/2 nodos. No Hi-ADSD with Detours o tamanho do conjunto de informacoes

obtidas e limitado pelo tamanho do cluster testado mais os nodos retornados pela funcao

more-info.

A limitacao do conjunto de informacoes obtidas no detours e necessaria porque no

algoritmo Hi-ADSD with Detours um nodo i nao pode obter informacoes de diagnostico

sobre um nodo j de dois ou mais nodos. No Hi-ADSD with Timestamps o nodo i pode obter

informacoes sobre um nodo j de dois ou mais nodos sem-falhas. Neste caso e necessario

determinar qual informacao sobre o estado de j e mais recente. Por exemplo, na figura 10,

e possıvel verificar que o nodo 0 pode obter informacoes sobre o nodo 5 pelos clusters C0,3,1

e C0,3,4.

O timestamp e um mecanismo que permite datar a informacao de diagnostico e e im-

plementado com um contador das mudancas de estado. Cada vez que um teste e executado

e o testador descobre que o nodo testado mudou de estado o contador e incrementado.


Para garantir que o nodo i mantenha as informacoes mais recentes sobre nodo j ele

precisa comparar o timestamp do estado de j obtido com o seu timestamp local. Se o

timestamp do estado de j obtido e menor que o timestamp de j local entao a informacao de

diagnostico e desatualizada e i nao deve atualizar o estado de j. Caso contrario, o timestamp

local de j for menor do que o obtido a informacao e mais nova, entao o timestamp local e

a informacao de diagnostico devem ser atualizadas.

Se o primeiro nodo testado de Ci, s, p estiver falho, o testador tentara encontrar detours

para os nodos destes clustres atraves de outros nodos sem-falhas testados. Um teste extra

somente e executado em cluster se nao forem encontrados detours.

47

4 Diagnostico Distribuıdo Baseado

no Algoritmo DiVHA

Este capıtulo apresenta um novo algoritmo de diagnostico distribuıdo, hierarquico e

adaptativo baseado no Distributed Virtual Hypercube Algorithm (DiVHA). Dado um con-

junto de nodos e seus estados, o algoritmo DiVHA determina um grafo de testes com uma

topologia baseada no hipercubo. Quando todos os nodos estao sem-falha o grafo e um

hipercubo completo. Na presenca de nodos falhos, a topologia deixa de ser um hipercubo

completo, e testes sao adicionados de forma a preservar duas proprieadades do hipercubo:

o diametro logarıtmico, ou seja, a distancia entre qualquer par de nodos i e j no grafo de

testes nunca e maior que log2N ; e o numero maximo de arestas Nlog2N .

O algoritmo de diagnostico utiliza o algoritmo DiVHA para atribuir os testes e deter-

minar o fluxo de informacao no sistema. Tirando proveito das caracterstıcas do grafo do

DiVHA, o novo algoritmo de diagnostico permite que todos os nodos sem-falha determinem

o estado de todos outros nos do sistema em no maximo log2N rodadas de testes, reque-

rendo no maximo N ∗ (log2N)2 testes. De nosso conhecimento, nenhum outro algoritmo

distribuıdo de monitoracao apresenta um numero tao baixo de mensagens.

O restante deste capıtulo esta organizando da seguinte maneira. A secao 4.1 apresenta

o modelo do sistema. O algoritmo de diagnostico e especificado na secao 4.2, na sequencia

a secao 4.3 apresentada a especificacao do algoritmo DiVHA. A prova de correcao dos

algoritmos propostos e apresentada na secao 4.4. Finalmente a secao 4.5 traz resultados

obtidos da simulacao do novo algoritmo de diagnostico.

4.1 Modelo do Sistema 48

4.1 Modelo do Sistema

Considere um sistema S composto por um conjunto de N nodos, n0, n1,...,nN−1. Al-

ternativamente nos referimos ao nodo ni como nodo i. O sistema e considerado totalmente

conectado, ou seja, qualquer par de nodos pode se comunicar diretamente. Assumimos

tambem um sistema sıncrono onde os relogios nao estao sincronizados.

Um nodo ni pode assumir um de dois estados, sem-falha ou falho. Um evento e definido

como a mudanca de estado de um nodo, tanto de sem-falha para falho como de falho para

sem-falha. A colecao dos estados de todos os nodos e o estado do sistema. Se considera

tambem um modelo dinamico para os estados do sistema, ou seja, os nodos podem alternar

continuamente entre o estado falho e o estado sem-falha.

Um nodo no estado sem-falha e considerado como capaz de testar outros nodos e infor-

mar corretamente os resultados destes testes. Um teste consiste em uma tarefa atribuıda

pelo nodo testador ao nodo testado. A tarefa e executada e o resultado devolvido para o

testador que compara o resultado com o esperado. Isto significa que o diagnostico traba-

lha com uma classe de falhas melhor caracterizada como falha de computacao, que ocorre

quando um processo falha em produzir a resposta esperada para uma dada entrada. Os

testes sao realizados periodicamente, dentro de um intervalo de testes fixo, que pode variar

dependendo da tecnologia do sistema, de alguns poucos nanosegundos a varios minutos.

Uma rodada de testes e definida como o perıodo de tempo em que todos os nodos no

estado sem-falha executam seus testes. A latencia do sistema e definida como o tempo

necessario para que todos nodos no estado sem-falha descubram a ocorrencia de um novo

evento.

4.2 Especificacao do Algoritmo de Diagnostico Distribuıdo 49

4.2 Especificacao do Algoritmo de Diagnostico Dis-

tribuıdo

Seja o grafo de testes, tambem chamado T (S), um grafo direcionado cujos nodos sao

os nodos de S. Existe uma aresta direcionada do nodo i para o nodo j se o nodo i testa o

nodo j na rodada de testes mais recente. Assim T (S) representa todos os testes executados

na ultima rodada de testes. Quando todos os nodos estao no estado sem-falha, T (S) e um

hipercubo. Quando alguns nodos sao considerados falhos, T (S) deixa de ser um hipercubo e

novas arestas sao adicionadas com o objetivo de preservar duas propriedades do hipercubo:

(1) o diametro logarıtmico, ou seja, a distancia entre qualquer par de nodos i e j em T (S)

nunca e maior que log2N ; e (2) o numero total de arestas em T (S) nunca e maior que

Nlog2N .

O algoritmo mostrado na figura 11 e executado por todos os nodos para determinar e

obter informacoes sobre o estado dos outros nodos do sistema, com o objetivo de manter o

hipercubo. A cada rodada de testes todos nodos no estado sem-falha executam seus testes,

o conjunto de testes atribuıdos ao nodo i chamado t(i) e o conjunto de nodos adjacentes

ao nodo i em T (S). Seja a distancia do nodo i para o nodo j, chamada di,j ou d(i, j), o

tamanho do caminho com menor numero de arestas do nodo i para o nodo j em T (S). Seja

Di,k o conjunto de todos os nodos p tal que di,p ≤ k.

Quando o nodo i testa um nodo j no estado sem-falha ele obtem informacao sobre

todos os nodos k com distancia de j menor ou igual a log2N − 1, ou seja k ∈ Dj,log2N−1, tal

que dj,k < di,k. Quando todos os nodos em T (S) estao no estado sem-falha, em um unico

teste o testador obtem informacoes de estado de sobre N/2 nodos. Ao executar todos seus

testes o nodo i obtem informacoes sobre o estado de todos os nodos do sistema.

E possıvel que um nodo i obtenha informacao sobre um nodo k atraves de um ou mais

nodos. Para garantir que o nodo i obtenha apenas a informacao mais nova de estado do

nodo k utilizamos o mecanismo de timestamps. Esta estrategia permite datar a informacao

4.3 O Algoritmo DiVHA 50

Dis t r ibuted Diagnos i s with DiVHAT(S)=DiVHA(S)DO

FOR EACH j IN t ( i )t e s t ( j )IF the s t a t e o f t e s t ed node has changed THEN

update s t a tu s and timestamp in format ion about jIF node j i s f au l t−f r e e THEN

get from j in fo rmat ion aboutnodes k in Dk, logN−1 such that d( j , k ) < d( i , k )

update l o c a l in fo rmat ion comparing timestampsIF new events have been d i s cove r ed THEN

update T(S) with DiVHAEND FORSLEEP un t i l the next Test ing I n t e r v a l

FOREVER

Figura 11: Diagnostico distribuıdo baseado no algoritmo DiVHA.

de estado, ou seja, e possıvel determinar se uma informacao recebida e mais nova que

outra tambem recebida ou ja mantida. O timestamp e implementado como um contador

das mudancas de estados, em outras palavras o timestamp e incrementado sempre que um

teste e executado e o testador descobre que o estado no nodo testado foi alterado. Quando

um nodo detecta um evento, ele executa o algoritmo DiVHA, apresentado abaixo, que

determina o novo conjunto de testes que devem ser executados pelo nodo.

4.3 O Algoritmo DiVHA

Os nodos do sistema executam o algoritmo DiVHA (Distributed Virtual Hypercube

Algorithm) com o objetivo de determinar o conjunto de testes a ser executado dado o

estado percebido do sistema. A especificacao do DiVHA e dada na figura 12.

Inicialmente o grafo T (S) tem apenas vertices, correspondentes aos nodos do sistema,

e nenhuma aresta. Os nodos sao organizados de forma hierarquica para calcular as arestas.

Clusters sao utilizados para agrupar nodos, que sao conjuntos de nodos cujo tamanho cresce

progressivamente em potencias de 2. Um cluster de p nodos nj, ..., nj+p−1, onde p e uma

potencia de 2 e e maior que 1, e formado pela uniao de dois clusters, um contendo os

nodos nj, ..., nj+p/2−1 e outro nj+1, ..., nj+p−1. A figura 13 mostra um sistema de 8 nodos

4.3 O Algoritmo DiVHA 51

DiVHA( system S)T(S) i n i t i a l l y does not have any edgeFOR s=1 to logN do

FOR d i s t ance=1 to s doFOR each f a u l t f r e e node i =0 . . .N−1 do

FOR each node j that be longs c ( i , s ) such that h( i , j ) = d i s t anceIF (d( i , j ) > s or non ex i s t en t ) THEN

add edge ( i , j ) to T( s )next i

UNTIL d( i , j ) <= s , such that node i i s f au l t−f r e eand node j be longs to c ( i , s )

Figura 12: Especificacao do algoritmo DiVHA.

organizado em clusters. Um cluster Ci,s pode ser definido recursivamente pela expressao:

Ci,s = Cj,s−1 ∪ Ci,s−1, j = i ⊕ 2s−1 e

Ci,1 = j, j = i ⊕ 1

O algoritmo considera os clusters do menor para o maior, ou seja, o tamanho do cluster e

incrementado com s variando de 1 ate log2N . A cada iteracao o algoritmo computa arestas

de nodos sem-falha i, variando i indo de 0 ate N − 1, para nodos pertencentes a Ci, s.

Desta forma sao adicionadas arestas entre o nodo 0 e nodos pertencentes ao cluster C0,s,

entre o nodo 1 e os nodos pertencentes ao cluster C1,s, e assim por diante ate o nodo N − 1

e os nodos pertencentes ao cluster CN−1,s. Uma aresta e adicionada entre o nodo i e o

nodo j ∈ Ci, s sempre que nao existir um caminho do nodo i para o nodo j em T (S) com

distancia ≤ s. Uma iteracao termina quando existe pelo menos um caminho com tamanho

≤ s entre todo nodo i no estado sem-falha e os nodos pertencentes a Ci, s.

0 1

7632

4 5

Figura 13: Sistema de 8 nodos agrupados em clusters pelo algoritmo DiVHA.

A adicao de arestas e feita de forma distribuıda entre os nodos do sistema baseando-se

4.4 Provas Formais 52

nas distancias do hipercubo. A distancia no hipercubo do nodo i para o nodo j, chamada

hi,s ou h(i, j), e o numero de arestas no caminho mais curto entre o nodo i e o nodo

j em um hipercubo perfeito. Esta estrategia para adicao de arestas permite formar um

hipercubo quando todos os nodos estao no estado sem-falha e distribuir entre os nodos de

forma balanceada as arestas adicionais que podem ser necessarias quando existem nodos

considerados falhos.

4.4 Provas Formais

Nesta secao sao apresentadas as provas formais que o DiVHA garante o diametro lo-

garıtmico do sistema mesmo quando o numero de nodos no estado sem falha nao e potencia

de 2, e que o numero total de arestas em T (S) nao e maior que Nlog2N . Tambem provamos

que a latencia para deteccao de eventos e log2N no pior caso.

Teorema 1. No grafo T (S) determinado pelo algoritmo DiVHA, a distancia de qualquer

nodo sem-falha para qualquer outro nodo e ≤ log2N .

Demonstracao. Considere o algoritmo da figura 12, o laco mais externo a cada iteracao

insere arestas que garantem d(i, j) ≤ s para todo ni sem-falha ∈ S e nj ∈ Ci,s. Vamos

provar por inducao que ao termino de cada iteracao s temos d(na, nb) ≤ s para todo

na, nb ∈ Ci,s+1. Dado que Ci,log2N+1 = S, ao final da ultima iteracao a distancia de qualquer

nodo sem-falha para outro nodo e menor ou igual a log2N .

Base. Na iteracao em que s = 1, d(na, nb) = 1 para todo na sem-falha, nb ∈ Ci,2.

Na primeira iteracao sao inseridas arestas garantindo d(ni, nj) ≤ 1 para todo ni sem-

falha ∈ S e nj ∈ Ci,s. Por definicao Ci,2 = Ci,1∪Cj,1, i = k⊕1, ou ainda, Ci,2 = Ci,1 ∪{ni}.

Suponha na sem-falha, nb ∈ Ci,2. Entao nb ∈ Ca,1 e logo d(na, nb) = 1, ja que d(i, j) ≤ s

para todo ni sem-falha ∈ S e nj ∈ Ci,s.


Hipotese de Inducao. Na iteracao s, d(na, nb) ≤ s para todo na sem-falha, nb ∈ Ci,s+1.

Passo. Ao final da iteracao s+1 a d(na, nb) ≤ s+1 para todo na sem-falha, nb ∈ Ci,s+2.

Na iteracao s+1 sao inseridas arestas garantindo d(ni, nj) ≤ s+1 de todo ni sem-falha

∈ S para todo nj ∈ Ci,s+1. Ci,s+2 e dado por Ci,s+1 ∪ Cj,s+1, j = i ⊕ 2s. Suponha na sem-

falha e nb ∈ Ci,s+2. Se na, nb pertencem ao mesmo cluster s + 1 pela hipotese de inducao,

d(na, nb) ≤ s; se na e nb pertencem a clusters s+1 distintos, entao na ∈ Cb,s+1 e nb ∈ Ca,s+1.

Logo d(na, nb) ≤ s + 1 porque nb ∈ Ca,s+1 e d(ni, nj) ≤ s + 1 para todo ni sem-falha e todo

nj ∈ Ci,s+1. Portanto d(na, nb) ≤ s + 1 para todo na sem-falha, nb ∈ Ci,s+2.

Teorema 2. No grafo T (S) determinado pelo algoritmo DiVHA, o numero maximo de ares-

tas e Nlog2N .

Demonstracao. Considere o algoritmo da figura 12, a cada iteracao s sao adicionadas ares-

tas entre clusters Ci,s e Cj,s distintos formando Ci,s+1. Suponha que uma aresta e adicionada

do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s, como mostra a figura 14. Da demonstracao indu-

tiva do teorema 1, d(ni, nk) ≤ s − 1 para todo ni sem-falha ∈ Ci,s, com a aresta inserida

aresta ij → jk, temos d(ni, nl) ≤ s para todo ni sem-falha ∈ Ci,s. Assim o DiVHA nao

insere nenhuma outra aresta para nl nesta iteracao, ou seja, um nodo recebe no maximo

uma aresta por iteracao; como o numero total de iteracoes e log2N , cada nodo em T (S)

recebe no maximo log2N arestas, e T (S) tem no maximo Nlog2N arestas.

Teorema 3. Uma alteracao percebida no estado de um nodo demora no maximo log2N

rodadas de testes para ser propagada para todos os nodos no estado sem-falha.

Demonstracao. Suponha que um evento ocorra no nodo e. Vamos demonstrar por inducao

que todo nodo no estado sem-falha a distancia d do nodo e descobre o evento em no maximo

d rodadas de testes. Como a distancia maxima no grafo T (S) dado pelo DiVHA e log2N ,

a inducao e suficiente para provar o teorema.


Figura 14: Aresta adicionada do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s.

Base: Todo nodo ni sem-falha tal que d(ni, ne) = 1 descobre o evento em ne em no

maximo uma rodada de testes. Trivial, todo os nodo sem-falha testa todos nodos a distancia

1 a cada rodada de testes.

Hipotese de Inducao: Todo nodo ni sem-falha tal que d(ni, ne) = d descobre o evento

em ne em no maximo d rodadas de testes.

Passo: Todo nodo ni sem-falha tal que d(ni, ne) = d + 1 descobre o evento em ne em

no maximo d + 1 rodadas de testes.

Considere nj tal que d(nj, ne) < d+1, existe portanto um caminho {nj = n0, ..., nd+1 =

ne} com d + 1 arestas entre o nodo nj e o nodo ne. O caminho {n1, ..., nd+1 = ne} tem d

arestas, logo n1 esta a distancia d do nodo e e pela hipotese de inducao descobre o evento

em no maximo d rodadas de testes. Como nj e adjacente a n1 e testa n1 em no maximo uma

rodada de testes, dado que d(n1, ne) ≤ log2N e d(n1, e) < d(nj, e), nj obtem informacao

sobre o novo estado do nodo ne ao testar n1. Logo, nj descobre o evento em ne em no

maximo d + 1 rodadas de testes.

4.5 Resultados de Simulacao 55

4.5 Resultados de Simulacao

Nesta secao sao apresentados resultados obtidos da simulacao do novo algoritmo de di-

agnostico baseado no algoritmo DiVHA. A simulacao foi conduzida utilizando a linguagem

de simulacao de eventos discretos SMPL (Simple Portable Simulation Language) (MAC-

DOUGALL, 1987). Os nodos foram modelados como estrutras do SMPL, cada nodo foi

identificado com um numero de token SMPL. Foram conduzidas tres series de experimen-

tos. A primeira serie de experimentos mostra o numero de testes necessarios como funcao

do numero de nodos falhos. A segunda serie de experimentados apresentados mostra a

latencia do algoritmo para uma serie de situacoes de falhas geradas aleatoriamente. Fi-

nalmente, a terceira serie de experimentos compara o novo algoritmo com algorimos de

diagnostico distribuıdos e hierarquicos publicados anteriormente.

4.5.1 Numero de Testes Necessarios

O proposito destes experimento e medir o numero de testes necessarios em um sistema

executando o algoritmo de diagnostico baseado no DiVHA. Foram simulados sistemas com

64, 128 e 256 nodos, sendo geradas cerca de 5 milhoes de situacoes de falhas diferentes. Para

cada situacao de falha DiVHA foi executado e o grafo de testes do sistemas construıdo. O

grafo de teste determina o numero de testes executados no sistema, dado que cada aresta

no grafo representa um teste a ser realizado.

O grafo apresentado na figura 15 apresenta os resultados obtidos por simulacao para

um sistema com 64 nodos. O eixo X representa o numero de nodos falhos na situacao de

falha. O eixo Y apresenta o melhor caso e o pior caso do numero de testes executados para

as situacoes de falhas simuladas. O melhor caso corresponde a situacao de falhas que requer

o menor numero de testes, o pior caso corresponde a situacao de falhas que requer o maior

numero de testes. Estes resultados mostram que o numero de testes diminui conforme o

numero de nodos falhos aumenta. Assim, o pior caso para o numero de testes corresponde


a situacao de falhas em que todos os nodos estao sem-falha.

0

24

48

72

96

120

144

168

192

216

240

264

288

312

336

360

384

63 60 56 52 48 44 40 36 32 28 24 20 16 12 8 4 0

# te

stes

# nodos no estado falho

pior casomelhor caso

Figura 15: Numero de testes necessarios para um sistema com 64 nodos.

Com o objetivo de verificar a escalabilidade do algoritmo o experimento anterior foi

repetido para sistemas com 128 e 256 nodos. O grafo na figura 16 mostra o resultado para

um sistema com 128 nodos. O grafo na figura 17 mostra o resultado para um sistema com

256 nodos. Comparando os resultados obtidos para sistemas com 64, 128 e 256 nodos, po-

demos concluir que o algoritmo apresenta um comportamente muito similar para diferentes

tamanhos de sistema. O fato de que o pior caso para o numero de testes e logarıtmico, ou

seja, no maximo Nlog2N testes sao executados em uma dada rodada de testes, tambem foi

confirmado por resultados de simulacao.


0

56

112

168

224

280

336

392

448

504

560

616

672

728

784

840

896

127 120 112 104 96 88 80 72 64 56 48 40 32 24 16 8 0

# te

stes




4.5.2 Latencia para Deteccao de Eventos

A latencia e o numero de rodadas de testes necessarias para que todos nodos sem-falha

realizem o diagnostico de um evento. O proposito desta serie de experimentos e verificar a

latencia para detectar um evento sob diferente situacoes de falhas. O primeiro experimento

conduzido foi em um sistema simulado de 512 nodos. Neste experimento inicialmente todos

os nodos estavam sem-falhas, entao o numero de nodos falhos era aumentado de 1 ate N−1.

Quando restava apenas um nodo sem-falha no sistema, os nodos eram sucessivamente

recuperados ate que todos os nodos se tornam-se novamente sem-falha. Este experimento

foi repetido 20 vezes medindo a latencia de 10200 eventos. O histograma na figura 18

mostra a distribuicao de frequencia da latencia observada para os eventos simulados. A

maioria dos eventos foi diagnosticada com um numero de rodadas cerca da latencia media


0

128

256

384

512

640

768

896

1024

1152

1280

1408

1536

1664

1792

1920

2048

255 240 224 208 192 176 160 144 128 112 96 80 64 48 32 16 0

# te

stes




esperada, ou seja, cerca da media entre a latencia mınima (uma rodada) e latencia maxima

(log2N rodadas). Somando o numero de eventos diagnosticados em 3, 4 e 5 rodadas temos

8490 eventos, o que corresponde a 83.4% do numero de total de eventos simulados.

O mesmo experimento foi conduzido para sistemas com 32, 64, 128 e 256 nodos. O

grafico na figura 19 mostra a latencia observada para cada tamanho de sistema. As barras

mostram a latencia teorica maxima e mınima para cada tamanho de sistema. A linha

mostra a latencia observada com maior frequencia. Os resultados confirmam que a latencia

cresce de forma logarıtmica e que a maior dos eventos sao diagnosticados em cerca de

(log2N)/2 rodadas.


0

500

1000

1500

2000

2500

3000

3500

987654321

Fre

quên

cia

Latência (rodadas)

148

518

1989

3628

2873

940

97 6 1

Figura 18: Latencia para sistemas com 512 nodos.

4.5.3 Comparacao com Outros Algoritmos

Nesta subsecao comparamos os resultados do novo algoritmo de diagnostico com os

algoritmos Hi-ADSD e Hi-ADSD com Timestamps. Os resultados apresentados para os

algoritmos Hi-ADSD e Hi-ADSD with Timestamps sao aqueles publicados em (DUARTE Jr.;

ALBINI; BRAWERMAN, 2000).

A tabela 3 mostra o numero medio de testes executados conforme o aumento de nodos

falhos. A primeira coluna apresenta o numero de nodos falhos, a segunda coluna o numero

medio de testes para o algoritmos Hi-ADSD with Timestamps, a terceira coluna o numero

de testes para o algoritmo de diagnostico baseado no DiVHA. O numero dentro de paren-

teses e o numero de testes adicionais necessarios, ou seja, o numero total de arestas no

grafo de testes menos o numero de arestas existente no hipercubo completo. Quando ha

poucos nodos falhos ambos algoritmos executam quase o mesmo numero de testes. Con-

forme aumenta o numero de nodos falhos o novo algoritmo apresenta um comportamento


0

1

2

3

4

5

6

7

8

9

10

11

1024 512 256 128 64 32

Latê

ncia

(ro

dada

s)

Tamanho do sistema (nodos)

Figura 19: Latencia para sistemas com 32, 64, 128, 256, 512 e 1024 nodos.

Tabela 3: Numero medio de testes necessarios para diagnosticar um sistema com 64 nodos.

Nodos Hi-ADSD with DiVHAfalhos Timestamps

0 384 (0) 384 (0)1 378 (0) 378 (0)2 374 (2) 372 (0)4 369 (9) 360 (0)6 367 (19) 350 (2)12 350 (38) 316 (4)32 320 (128) 216 (24)

melhor que o Hi-ADSD with Timestamps. Com 32 nodos falhos no sistema, na media

o algoritmo DiVHA necessita apenas 24 testes adicionais, enquanto o algoritmo Hi-ADSD

with Timestamps requerer 128 testes adicionais. Isto representa uma diminuicao de 5 vezes

no numero de testes adicionais. Estes resultados mostram que a estrategia do algoritmo

DiVHA para minimizar o numero de arestas adicionais tem um impacto efetivo no numero

total de testes executados.


Tabela 4: Latencia media para diagnosticar um evento em um sistema com 512 nodes.

Rodadas

Hi-ADSD 40Hi-ADSD withTimestamps 12

DiVHA 4

Outra comparacao realizada e quanto a latencia media para detectar um evento. E

considerado um sistema com 512 nodos onde um evento de falha ou recuperacao ocorre em

um dado nodo. Na tabela 3 podemos ver que em media o algoritmo DiVHA e 10 vezes

mais rapido que o Hi-ADSD original e 3 vezes mais rapido que o algoritmo Hi-ADSD com

Timestamps. Devemos notar que a definicao de rodadas de testes aplicada pelo algoritmo

DiVHA e diferente da empregada pelos outros algoritmos. Portanto o menor numero de

rodadas de testes nao implica em numa diminuicao no numero total de testes realizados

para diagnosticar um evento.

62

5 HyperBone: Uma Rede Overlay

Escalavel

O HyperBone e uma rede overlay formada por nodos espalhados pela Internet interliga-

dos por enlaces virtuais. Um enlace e implementado como uma conexao TCP persistente.

Se o numero de nodos e uma potencia de dois e todos os nodos estao funcionando sem

falhas, a topologia do sistema e um hipercubo completo. Quando o numero de nodos nao

e potencia de dois, ou alguns nodos nao estao disponıveis, o HyperBone ainda e capaz

de manter as propriedades logarıtmicas do hipercubo. O algoritmo DiVHA (Distributed

Virtual Hypercube Algorithm) e empregado, permitindo aos nodos calcular de forma in-

dependente seus enlaces virtuais na rede. Este capıtulo apresenta o modelo do sistema,

a especificacao do HyperBone, exemplos de execucao e os resultados obtidos da imple-

mentacao e experimentacao do sistema.

5.1 Modelo do Sistema

Considere um sistema S composto por um conjunto de N nodos, n0, n1,...,nN−1. Al-

ternativamente nos referimos ao nodo ni como nodo i. O sistema e considerado totalmente

conectado, ou seja, qualquer par de nodos pode se comunicar diretamente. Os relogios nao

sao sincronizados e nao sao feitas assercoes sobre as velocidades relativas dos processadores.

Um nodo ni pode assumir um de dois estados, working ou unresponsive. Um evento

e definido como a mudanca de estado de um nodo, tanto de working para unresponsive

como de unresponsive para working. A colecao dos estados de todos os nodos e o estado do

5.1 Modelo do Sistema 63

sistema. Se considera tambem um modelo dinamico para os estados do sistema, ou seja, os

nodos podem alternar entre o estado unresponsive e o estado working continuamente.

Os nodos sao capazes de realizar testes em outros nodos, assim um nodo testador

determina o estado do nodo testado. Os testes sao realizados periodicamente, dentro de

um intervalo de testes fixo, que pode variar dependendo da tecnologia do sistema, de alguns

poucos nanosegundos a varios minutos. Um nodo no estado working e considerado como

capaz de testar outros nodos e informar corretamente os resultados destes testes. Um teste

consiste em uma tarefa atribuıda pelo nodo testador ao nodo testado. A tarefa e executada

e o resultado devolvido para o testador que compara o resultado com o esperado. Um

intervalo de timeout e empregado para limitar a espera pelo resultado, a ocorrencia do

timeout e equivalente a uma resposta incorreta. Como o sistema e assıncrono, o timeout

nao e um indicativo concreto de que o nodo esta falho (crashed), assim um teste indica

apenas que o nodo ou esta funcionando corretamente ou nao respondeu corretamente a um

teste enviado ou ainda que nao respondeu dentro de um intervalo esperado.

Uma rodada de testes e definida como o perıodo de tempo em que todos os nodos

no estado working executam seus testes. A latencia do sistema e definida como o tempo

necessario para que todos nodos no estado working descubram a ocorrencia de um novo

evento.

Ainda consideramos que os nodos possam ser classificados em available e unavailable.

Um nodo available e um nodo que permanece no estado working por tempo suficiente para

ser considerado estavel e portanto disponıvel para receber tarefas. Um nodo unavailable e

um nodo que ainda nao pode ser considerado estavel, e por isso nao esta disponıvel para

receber tarefas. Cada nodo mantem informacoes sobre os estados de disponibilidade de

todos os outros nodos.

5.2 Construindo e Mantendo o Hipercubo Virtual 64

5.2 Construindo e Mantendo o Hipercubo Virtual

Seja o grafo de topologia virtual, tambem chamado Tv(S), um grafo direcionado cujos

nodos sao os nodos de S. Se existe uma aresta direcionada do nodo i para o nodo j,

entao existe um enlace virtual do nodo i para o nodo j. Atraves dos enlaces virtuais sao

trocadas as mensagens de testes, assim como roteadas as mensagens enviadas entre os

nodos. Cada nodo mantem uma tabela de roteamento que permita rotear uma mensagem

para um determinado destino. No HyperBone e proposta uma estrategia de roteamento

que permite determinar as rotas de menor custo no hipercubo virtual.

O algoritmo apresentado na figura 20 e executado a cada rodada de testes por todos

nodos no estado working para manter o hipercubo virtual. Este algoritmo de manutencao

do hipercubo virtual e baseado no algoritmo de diagnostico apresentado na figura 11 da

secao 4.2. Sao inseridas no algoritmos as estruturas necessarias para estabelecer os enlaces

virtuais entre os nodos, manter a tabela de roteamento e determinar a lista de nodos

estaveis. O algoritmo DiVHA usado para determinar a topologia do hipercubo virtual

dado o estado percebido do sistemas e aquele apresentado na secao 4.3.

A cada rodada de testes os nodos no estado working executam seus testes, ou seja,

testam os nodos pertencentes a t(i) que e o conjunto de nodos adjacentes ao nodo i em

Tv(S). Se um nodo i testa um dado nodo j e preciso criar o enlace virtual ligando o nodo

i ao nodo j. Este enlace virtual e implementado como uma conexao TCP/IP. Uma falha

ao criar o enlace virtual, estabelecer a conexao TCP/IP, equivale a testar um nodo como

unresponsive.

Para atualizar a informacao de estado do sistema, quando o nodo i testa um nodo j

no estado working ele obtem informacao sobre todos os nodos k com distancia de j menor

ou igual a log2N − 1, ou seja k ∈ Dj,log2N−1, tal que dj,k < di,k. Alem da informacao de

diagnostico, tambem e obtida informacao de roteamento deste conjunto de nodos. Quando

um nodo detecta um evento, ele executa o algoritmo DiVHA, apresentado na secao 4.3, que


HyperBone Construct ion & MaintenanceTv(S)=DiVHA(S)DO

FOR EACH j IN t ( i )IF i i s not connected to j THEN

cr ea t e v i r t u a l l i n k between i and jIF i i s connect to j THEN

t e s t ( j )ELSE

j i s unrespons iveIF the s t a t e o f t e s t ed node has changed THEN

update s t a tu s in fo rmat ion about jIF node j i s working THEN

get from j d i a gno s i s and rout ing in fo rmat ion aboutnodes k in Dk, logN−1 such that d( j , k ) < d( i , k )

update l o c a l in fo rmat ion comparing timestampsupdate l o c a l rout ing in fo rmat ion

IF new events have been d i s cove r ed THENupdate T(S) with DiVHA

END FORupdate a v a i l a b l e / unava i l ab l e nodes l i s tSLEEP un t i l the next Test ing I n t e r v a l

FOREVER

Figura 20: O algoritmo para criacao e manutencao do hipercubo virtual.

determina o novo conjunto de testes que devem ser executados pelo nodo. Os algoritmos

para atualizar as informacoes de roteamento e para determinar os estados de disponibilidade

sao apresentados nas subsecoes seguintes.

5.2.1 Algoritmo de Roteamento no Hipercubo Virtual

O HyperBone e capaz de rotear mensagens entre os nodos atraves dos enlaces virtuais.

A cada rodada, alem de atualizar as informacoes de estado de sistema, tambem e atualizada

a informacao de roteamento. O algoritmo de roteamento e apresentado na figura 21. O

vetor route mantem a tabela de roteamento, ou seja, determina o proximo salto para rotear

uma mensagem para um determinado nodo. O vetor rcost mantem uma estimativa de

custo para atingir cada nodo do sistema dada a rota atual.

Quando um nodo i testa um nodo j como working, o custo do enlace i → j e estimado e

a informacao de custo para atingir o nodo j atualizada. Alem disso, sao obtidas informacoes


da tabela de custos do nodo j (rcost_j). Para cada nodo k que pode ser alcancado pelo

nodo i passando pelo nodo j uma comparacao de custo e realizada. Se o custo atual de

alcancar um nodo k (rcost[k]) for maior que o custo de alcancar este nodo k passando

pelo nodo j (rcost[j] + rcost_j[k]) entao o nodo j representa a melhor rota atual para

o nodo k. Neste caso informacao de custo e atualizada e a tabela local de roteamento passa

a apontar o nodo j como a nova rota para o nodo k.

HyperBone Routing Table Maintenance at node iroute keeps the rout ing tab l er c o s t keeps the es t imate co s t to reach a given nodeWHEN updating in fo rmat ion from node j

r c o s t [ j ] = co s t measured from node i to node jr c o s t j = GET rout ing co s t t ab l e from node JFOR EACH node k in Dk, logN−1 such that dj , k < di , k

IF ( r c o s t [ k ] > r c o s t [ j ]+ r c o s t j [ k ] )r c o s t [ k ] = r c o s t [ j ]+ r c o s t j [ k ]route [ k ] = j ;

END IFEND FOR

END

Figura 21: Algoritmo de manutencao da tabela de rotas no HyperBone.

No algoritmo de roteamento proposto neste trabalho o numero de saltos necessario

para rotear uma mensagem para qualquer nodo nunca e maior que log2N . Alem disto, a

rota e escolhida de forma a minimizar o custo. Estas propriedades sao fundamentais para

implementar servicos de busca de objetos e/ou comunicacao ponto a ponto ou em grupo

de forma eficiente usando o HyperBone.

A figura 22 mostra um exemplo de execucao do algoritmo de roteamento para um

sistema com 8 nodos. No exemplo, e mostrado o comportamento do algoritmo para o nodo

7. O nodo 3, o nodo 5 e o nodo 6 estao diretamente conectados ao nodo 7, entao eles

simplesmente testam o nodo 7 e estimam o custo do enlace. Por exemplo, o custo estimado

do enlace do nodo 3 para o nodo 7 e 40 ms. O nodo 2 pode alcancar o nodo 7 tanto pelo

nodo 3 como pelo nodo 6. O custo do nodo 2 para o nodo 3 e 30 ms, e o custo do nodo 3

para o nodo 7 e 40 ms, entao o custo da rota do nodo 2 para o nodo 7 passando pelo nodo

3 e 70 ms. Da mesma maneira, o custo da rota do nodo 2 para o nodo 7 passando pelo


nodo 6 e 110 ms. Assim, a tabela de roteamento do nodo numero 2 vai indicar o nodo 3

como melhor rota para o nodo 7. Como exemplo final, o nodo 0 tem 3 possıveis rotas para

o nodo 7: nodo 1, com custo 50 ms mais 110 ms; node 2 com custo de 10 ms mais 70 ms

e nodo 7 com custo 130 ms mais 20 ms. Portanto a rota com menor custo do nodo 0 para

o nodo 7 e aquela passando pelo nodo 2 que tem custo total de 80 ms. Com a tabela de

rota construıda neste exemplo, uma mensagem do nodo 0 para o nodo 7 primeiro e enviada

para o nodo 2, entao para o nodo 3 e entao finalmente chega ao nodo 7.

Figura 22: Exemplo de roteamento para um sistema com 8 nodos no HyperBone.

5.2.2 Parametros de Disponibilidade

Consideramos que os nodos podem passar por perıodos de instabilidade que causam

falhas de desempenho, fazendo com que seu estado alterne entre unresponsive e working.

Dada esta assercao, considere duas situacoes: a) um nodo que vem continuamente res-

pondendo corretamente aos testes, falha ao responder corretamente um teste, voltando em

seguida a responder os testes corretamente. Boa parte das aplicacoes poderia suportar um


pequeno perıodo, evitando assim o possıvel custo de considerar o nodo como falho; b) em

outra situacao, um nodo apenas responde corretamente aos testes por pequenos intervalos

de tempo. Este nodo nao deveria ser considerado como disponıvel em nenhum momento, ja

que nao consegue atender os requisitos dos testes por um perıodo de tempo razoavel. Com

o objetivo de tratar estes casos, este trabalho introduz os parametros de disponibilidade

que permitem classificar os nodos em available e unavailable.

Os parametros de disponibilidade sao definidos por um perıodo mınimo de tempo pre-

definido em que o nodo deve permanecer no estado working para ser considerado available, e

por um perıodo mınimo de tempo que o nodo deve permanecer no estado unresponsive para

ser considerado unavailable. Esta estrategia facilita a monitoracao de sistemas altamente

instaveis, com mudancas contınuas de estado dos nodos. Cada nodo mantem informacoes

sobre os estados de disponibilidade de todos os outros nodos.

A figura 23 mostra o algoritmo executado pelo HyperBone ao final de cada rodada,

com o objetivo de manter as informacoes sobre os estados de disponibilidade dos nodos.

O estado de cada nodo e verificado, se um nodo permancer no estado working por um

intervalo de tempo mınimo Wt entao este nodo e considerado como available. De maneira

analoga, se um nodo permanecer por um intervalo de tempo Ut no estado unresponsive e

considerado como unavailable. Se nenhuma destas condicoes se verificar, o nodo mantem

o estado de disponibilidade anterior. Os intervalos de tempo Wt e Ut sao parametros do

sistema e dependem dos requisitos das tarefas que se pretende executar.

HyperBone a v a i l a b i l i t y in fo rmat ion maintainance a lgor i thm at node iFOR each node i =0 . . .N−1 do

IF node i i s working f o r the g iven Wt time THENnode i as a v a i l a b l e

IF node i i s unrespons ive f o r the g iven Ut time THENnode i as unava i l ab l e

END

Figura 23: Algoritmo de atualizacao das informacoes sobre os estados de disponibilidade.

5.3 Exemplos de Execucao 69

5.3 Exemplos de Execucao

Esta secao apresenta exemplos de execucao do HyperBone e do algoritmo DiVHA.

Considere um sistema com 16 nodos, e o estado inicial ilustrado na figura 24.a, na qual os

nodos em cinza estao no estado unresponsive. As arestas finas sao as arestas do hipercubo,

as arestas grossas indicam arestas adicionadas pelo DiVHA. A figura 24.b mostra o fluxo

de informacoes de estados do sistema para o nodo 0, os nodos agrupados representam o

conjunto de nodos sobre os quais o nodo 0 obtem informacao durante os testes, por exemplo

ao testar o node 3, o nodo 0, obtem informacoes sobre o nodo 11, nodo 15 e nodo 7.

a:Enlaces do overlay. b:Fluxo de informacoes para o nodo 0.

Figura 24: Exemplo de sistema com 16 nodos executando o HyperBone.

Suponha que o nodo 4 se torne unresponsive, cada nodo ao obter o novo estado do nodo

4 executa o DiVHA determinando a nova topologia do sistema. A figura 25 representa a

execucao do DiVHA a cada iteracao s. Na primeira iteracao sao adicionadas arestas para

formar caminhos com tamanho ≤ 1 entre todo nodo i e os clusters Ci,0, essa iteracao e trivial

incluindo apenas arestas do hipercubo. A iteracao (2) garante caminhos com tamanho ≤ 2

para clusters Ci,2. Nessa iteracao se verifica a inexistencia de caminhos entre nodo 0 e nodo

3, nodo 3 e nodo 0, nodo 9 e nodo 10, e nodo 10 e nodo 9, assim sao adicionadas as arestas

0 → 3, 3 → 0, 0 → 9, 9 → 0. A iteracao (3) garante caminhos com tamanho ≤ 3 para

5.3 Exemplos de Execucao 70

os clusters Ci,3, no caso nao sao necessarias arestas alem das convencionais do hipercubo.

Finalmente, na iteracao (4) sao incluıdas as arestas 0 → 9, 9 → 0, 6 → 10 e 10 → 6 para

garantir os caminhos de tamanho 4 entre esses nodos.

iteracao 1 iteracao 2 interacao 3 interacao 4

Figura 25: Representacao das iteracoes do algoritmo DiVHA.

A figura 26.a mostra o hipercubo virtual final para o sistema com o nodo 4 falho. As

arestas mais grossas indicam arestas adicionais, sendo que as arestas pontilhadas represen-

tam os testes adicionais que ja existiam antes da falha do nodo 4. A figura 26.b mostra a

nova configuracao do fluxo de informacoes para o nodo 0.

a:Enlaces do overlay. b:Fluxo de informacoes para o nodo 0.

Figura 26: Exemplo de sistema com 16 nodos apos falha do nodo 4.

5.4 Implementacao e Resultados Experimentais 71

5.4 Implementacao e Resultados Experimentais

O HyperBone foi implementado como daemons de rede que executam em cada nodo

agregado ao sistem. Os nodos se comunicam atraves de conexoes TCP/IP permanentes,

correspondentes aos enlaces virtuais definidos pelo algoritmo DiVHA. Os testes consistem

no envio de uma mensagem para o nodo testado que deve ser respondida dentro de um

perıodo de tempo definido.

Um aspecto importante da implementacao e que o HyperBone e transparente para as

aplicacoes. Se uma aplicacao deseja se comunicar atraves do hipercubo virtual basta que use

enderecos IP exclusivamente (Internet Protocol) alocados para o HyperBone. Por exemplo,

se a rede 10.0.0.0/8 esta reservada para o HyperBone, basta a aplicacao usar enderecos

desta faixa para se comunicar usando o hipercubo virtual. Esse recurso e implementando

atraves da interface tun/tap (TUNTAP, 2005) que implementa um dispositivo de rede virtual

que forca o recebimento de pacotes de uma aplicacao em espaco de usuario, ao inves de

recebe-los do protocolo da camada de enlace.

O ambiente de experimentacao escolhido foi o PlanetLab (PLANETLAB, 2005), que e

um ambiente composto por computadores distribuıdos em todo mundo conectados pela In-

ternet, atualmente contando com 631 maquinas em mais de 25 paıses. Os experimentos se

destinaram a avaliar o HyperBone no aspecto de estabilidade, sistema de monitoracao, sis-

tema de comunicacao/roteamento e capacidade de execucao de aplicacoes. Os experimentos

realizados e os resultados obtidos sao descritos nas proximas subsecoes.

5.4.1 Sistema de Monitoracao

Para avaliar o sistema de monitoracao o HyperBone foi instalado em 128 maquinas

do PlanetLab e sua execucao acompanhada durante cerca de 3 semanas. Os sistema foi

executado com diversos parametros, ao final considerando os tempos medios de resposta

no PlanetLab conclui-se que um valor de timeout adequado seria de 7 segundos e o inter-


valo entre os inıcios de duas rodadas de testes foi fixado em 10 segundos. Os resultados

apresentados sao relativos aos dados obtidos do registro de execucao do sistema com estes

parametros durante 6 dias.

Um dos experimentos realizados visou descobrir o tempo em que os nodos permanecem

em um dado estado antes de sofrerem um novo evento. Considerando o timeout relati-

vamente pequeno para a carga do PlanetLab, os nodos nao eram capazes de atender por

perıodos longos e contınuos os requisitos temporais impostos pelos testes, o resultado e

que foi detectado um grande numero de eventos. Registramos cerca de 200 mil eventos em

6 dias o que representa uma taxa aproximada de 1388 eventos/hora. O grafico da figura

27 mostra a distribuicao acumulada para o tempo de permanencia nos estados working e

unresponsive antes da ocorrencia de um novo evento. Podemos observar que, na grande

maioria dos casos, os nodos permaneceram working por menos de 10 minutos e unresponsive

por menos de 120 segundos.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

6d3d1d10h5h2h1h30 min10 min5 min2min1min30s15s10s6s4s3s2s1s

Pro

babi

lidad

e ac

umul

ada

Tempo de permanência no estado

unresponsiveworking

Figura 27: Probabilidade acumulada para o tempo de permanencia nos estados working eunresponsive.


O grande numero de eventos registrados justificou na pratica a utilidade dos parametros

de estabilizacao introduzidos no HyperBone. Baseado nos tempos observados no grafico da

figura 27 decidiu-se considerar um nodo unavailable apenas apos permanecer 120 segundos

no estado unresponsive, e considerar um nodo available apos permanecer 600 segundos no

estado working. Com esses parametros o numero de eventos percebidos para os estados

unavailable e available foi de apenas 1050, ou seja, uma taxa menor que 8 eventos/hora,

numeros significativamente reduzidos considerando o resultado acima descrito.

Na pratica esta forma de classificar os nodos permite descobrir o conjunto de nodos

que apresentam comportamento mais estavel em comparacao aos outros. Pode-se dizer que

aumenta a granularidade com que se enxerga o estado do sistema. Por exemplo, um nodo

available apenas deixa de ser considerado available se passar mais que 120 segundos como

unresponsive; um nodo unavailable apenas sera considerado available se passar por mais de

600 segundos sendo considerado working.

Desta forma, nodos que ficam silenciosos por pequeninos intervalos de tempo tambem

sao considerados estaveis. O grafico da figura 28 mostra a probabilidade acumulada para o

tempo de permanencia nos estados available e unavailable. Observamos perıodos maiores

em que nodos permanecem em um unico estado, por exemplo, em cerca de 40% dos casos

os nodos permaneceram mais de 1 hora no estado available antes de um evento e em 80%

dos casos os nodos permaneceram mais que 30 minutos no estado unavailable.

Outra medida obtida foi a taxa de disponibilidade dos nodos baseada nos estados

available e unavailable. O histograma da figura 29 mostra a distribuicao de frequencia da

disponibilidade dos nodos. Apesar das instabilidades do sistema observamos que 47 nodos

apresentaram disponibilidade entre 80% e 90% e 20 nodos acima de 90%. As taxas de

disponibilidade muito baixas foram relativas a nodos que estavam inacessıveis ou falhos.

Por fim, examinamos os limites de tempo para a propagacao dos eventos no hipercubo.

Escolhemos um perıodo e um nodo que estivesse alternando repetidamente de estado, e


0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

6d3d1d10h5h2h1h30 min10 min5 min2min

Pro

babi

lidad

e ac

umul

ada

Tempo de permanência no estado

unavaliableavaliable

Figura 28: Probabilidade acumulada para o tempo de permanencia nos estados available eunavailable.

observamos o estado deste nodo a partir de outros nodos com diferentes distancias no

hipercubo. O nodo 4 teve seus eventos observados, os pontos de observacao foram: nodo

5 a distancia 1, nodo 7 a distancia 2, nodo 77 a distancia 3, nodo 118 a distancia 4, nodo

44 a distancia 5, nodo 122 a distancia 6 e finalmente nodo 123 a distancia 7, a maior

possıvel tendo em vista o numero total de nodos do hipercubo, 128. A figura 30 mostra os

resultados obtidos, o relogio utilizado para registrar os eventos foi o relogio das maquinas,

que estava sincronizado por NTP (Network Time Protocol). Pode-se comprovar por estes

resultados que os nodos obtem as informacoes dentro do intervalo de tempo esperado.

5.4.2 Estrategia de Roteamento no HyperBone

O proposito deste experimento foi avaliar a estrategia de roteamento empregado pelo

HyperBone. Para este experimentos, instalamos o HyperBone em 256 maquinas do Plane-

tLab. O sistema foi inicializado e deixado em execucao por um dado perıodo de tempo, e


0

5

10

15

20

25

30

35

40

45

50

0.9−10.8−0.90.7−0.80.6−0.70.5−0.60.4−0.50.3−0.40.2−0.30.1−0.20−0.1

Núm

ero

de n

odos

Taxa de disponibilidade

Figura 29: Histograma da taxa de disponibilidade dos nodos.

entao um snapshot do sistema foi tirado. O snapshot obteve informacao sobre a topologia

virtual atual e os custos estimados de cada enlace virtual.

Com estes dados, foram obtidos os custos para todas as possıveis rotas com o menor

numero de saltos entre todos os pares de nodos do sistema. A tabela 5 mostra a com-

paracao do custo da rota escolhida pelo HyperBone, com o custo destas outras possıveis

rotas. Cada coluna representa os resultados obtidos para rotas com um dado tamanho. A

primeira linha compara o custo da rota de maior custo entre dois nodos com o custo da

rota determinada pelo HyperBone. De maneira similiar, a segunda linha compara o custo

medio das rotas entre dois nodos com o custo da rota determinada pelo HyperBone. Os

resultados apresentados sao obtidos da media destas comparacoes para todos os possıveis

pares de nodos. Para pares de nodos que estao a distancia 1 existe apenas uma rota, as-

sim a rota escolhida pelo HyperBone e a unica possıvel. Conforme a distancia entre os

nodos aumenta o numero de possıveis rotas tambem aumenta e se percebe a vantagem da

estrategia de roteamento do HyperBone. Para rotas com tamanho 8, na media as rotas do

HyperBone tem um custo 8,71 vezes menor que a pior rota possıvel, e 3,32 vezes menor

que o custo medio das rotas disponıveis. Estes resultados mostram que a estrategia de


working

faulty

working

faulty

working

faulty

working

faulty

working

faulty

working

faulty

working

faulty

12h11h10h9h8h7h6h5h4h3h2h1h

tempo (s)

Nodo 5 Nodo 7 Nodo 77 Nodo 118 Nodo 44 Nodo 122 Nodo 123

Figura 30: Propagacao da informacao de um evento no nodo 4.

roteamento do HyperBone tem realmente um forte impacto no custo total de roteamento.

Tabela 5: Relacao de ganho da estrategia de roteamento do HyperBone.

Numero de saltos da rota1 2 3 4 5 6 7

Pior caso 1:1 1:2,06 1:2,88 1:4,11 1:5,54 1:7,07 1:8,71Media 1:1 1:1,53 1:1,87 1:2,27 1:2,64 1:2,97 1:3,32

5.4.3 Executando Aplicacoes Paralelas no HyperBone

A capacidade de execucao de aplicacoes no HyperBone foi avaliada executando aplicacoes

paralelas usando MPI. Nestes experimentos foi utilizado um hipercubo virtual formado por

256 maquinas do PlanetLab. A cada teste, baseado nas informacoes de monitoracao dispo-

nibilizadas pelo HyperBone, se selecionava no hipercubo virtual o conjunto de nodos que

apresentava o comportamento mais estavel.

O objetivo do primeiro experimento foi comprovar o funcionamento das primitivas de


comunicacao do MPI sobre o HyperBone. Foi utilizado o MPIbench (MPIBENCH, 2005),

um benchmark que exercita as principais funcoes do MPI, tanto de comunicacao ponto a

ponto (MPI_Send e MPI_Receive) como de comunicacao em grupo, por exemplo difusao

(MPI_Broadcast). A tabela 6 apresenta o resultado da execucao do MPIbench. Cada

coluna representa os resultados de um tipo de teste do MPIbench, as linhas mostram

o tamanho de mensagens utilizado em cada teste. O resultado a ser observado nao e

o desempenho propriamente dito, mas sim o fato dos testes terem sido executados com

sucesso e sem necessidade de modificar a aplicacao mesmo num ambiente instavel como o

PlanetLab.

Tabela 6: Resultados da execucao do MPIbench no HyperBone.

Tamanho da Latencia Biband Roundtrip Bandwidth Broadcast Reduce Alltoall AllReduceMensagem µ s KB/s trans./s KB/s KB/s KB/s KB/s KB/s

8192 25650.24 259.97 11.83 232.29 54.81 21.11 100.40 17.8516384 43234.49 420.03 8.12 312.55 47.13 32.10 100.80 22.4632768 82235.52 552.82 5.13 341.39 34.26 32.19 121.13 15.4865536 207180.25 567.78 2.53 375.95 36.26 37.48 98.11 20.09

O segundo experimento realizado teve como objetivo verificar a possibilidade de execu-

tar aplicacoes reais em MPI usando o HyperBone. Foi executada uma aplicacao em MPI

que paraleliza a tarefa de encontrar uma senha em um determinado espaco de busca. A

tabela 7 mostra taxa de chaves avaliada por segundo obtida em sistemas com 16, 32 e 64

nodos. Podemos observar que o sistema teve uma escalabilidade razoavel tanto de 16 para

32 nodos, como de 32 para 64 nodos.

Tabela 7: Resultado da execucao de um buscador de senhas no HyperBone.

Nodos Senhas por segundo

16 31368.1432 42968.3364 50200.20


5.4.3.1 Dispositivo MPI para o HyperBone

Um outro conjunto de experimentos executando aplicacoes distribuıdas paralelas foi

executado. No lugar de usar a implementacao do HyperBone baseada na interface TUN/TAP,

foi utilizado o ch hyperbone. O ch hyperbone utiliza dispositivos do MPI chamados ADI

(Abstract Device Interface)(CROPP, 1995) que abstrai o transporte das mensagens per-

mitindo as aplicacoes em MPI acessarem diretamente o hipercubo virtual. O objetivo

destes experimentos foi avaliar a possibilidade de utilizar o HyperBone como alternativa

para execucao de programas MPI em ambientes de grade e/ou sujeito a falhas. Com

ch hyperbone seria possıvel modificar o comportamento das primitivas de comunicacao

MPI, permitindo implementar sistemas MPI adaptados a grades computacionais e tambem

tolerantes a falha.

Os experimento realizados com o ch hyperbone foram realizados usando maquinas de

um cluster de estacoes, interligado por interfaces de rede ethernet de 1Gbps. Um dos

experimento realizados mediu o impacto do roteamento das mensagens atraves do hiper-

cubo, os resultados obtidos foram comparados com o dispositivo ch p4, que e o ADI padrao

utilizado em redes TCP/IP. A vazao foi medida utilizando o tempo de execucao de um

programa que usa as primitivas do MPI para transferir 100.000 mensagens de 8KB cada.

Para o ch hyperbone foi medida a vazao entre pares de nodos a diferentes distancias no

hypercubo. A vazao atingida com o ch p4 foi medida apenas entre dois nodos.

Os resultados do teste de vazao sao apresentados na tabela 8. A primeira coluna repre-

senta a vazao obtida com o dispositivo ch p4. As colunas seguintes a vazao obtida com o

ch hyperbone para nodos a diferente distancias no hipercubo. A vazao atingida nos experi-

mentos pelo ch hyperbone em relacao ao ch p4 variou de 96,32%, para nodos diretamente

conectados, diminuindo gradativamente para 50,22% com nodos a distancia 4. Como espe-

rado, o roteamento das mensagens e a camada ADI resultam em um overhead no sistema.

Entretanto, deve se considerar que muitos algoritmos paralelos sao baseadas no hipercubo,


ou em estruturas contidas no hipercubo, diminuindo a necessidade de comunicacao entre

nodos distantes no hipercubo. Alem disto, o crescimento do custo de roteamento e apenas

logarıtmico, ja que as rotas tem distancia maxima log2N . Desta forma, estes resultados

mostram a viabilidade de utilizar do hipercubo virtual como plataforma para execucao do

aplicacoes em MPI na Internet.

Tabela 8: Comparativo de vazao entre os dispositivos ch hyperbone e ch p4.

ch p4 ch hyperbone1 1 2 3 4

Vazao (Mbps/s) 653.97 629.17 474.72 463.67i 328.07

Outro experimento executado foi executando o MPI-PovRay (MPI-POVRAY, 2003), que

e um software de renderizacao de imagens baseado na estrutura mestre-escravo. Foram

realizados experimentos comparando o tempo de renderizacao de imagem de 1000x500

pixels utilizando o ch hyperbone e o ch p4. Os experimento foram realizados em sistemas

com 2, 4, 8 e 16 nodos. A tabela 9 apresenta os resultados do tempo de execucao do MPI-

PovRay. As colunas representam o numero de nodos no sistema. A primeira linha apresenta

o tempo de execucao em segundos para o ch hyperbone. A segunda linha apresenta o tempo

de execucao em segundos para o ch p4. Verificamos que os tempos de execucao sao muito

similares, mostrando que em aplicacoes onde o tempo de processamento domina o tempo

de comunicacao, o custo de utilizar hipercubo virtual pode ser desprezıvel.

Tabela 9: Comparativo do tempo de execucao do MPI-PovRay entre os dispositivosch hyperbone e ch p4.

Numero de nodos2 4 8 16

ch hyperbone 111,66 s 37,66 s 17 s 10,33 sch p4 109,33 s 36.0 s 20,33 s 11 s

O conjunto de experimentos realizados com o ch hyperbone mostram a viabilidade da

utilizacao do hipercubo virtual como rede overlay para aplicacoes MPI. O ch hyperbone


poderia ser utilizado para prover implementacoes MPI adaptadas ao ambiente de grades,

integrando o sistema com ambientes de grades como o Globus, ou ainda prover tolerancia

a falhas.

81

6 Conclusao

Este trabalho apresentou o HyperBone, uma rede overlay que aproveita caracterısticas

topologicas do hipercubo para oferecer servicos escalaveis de comunicacao e monitoracao

para sistemas distribuıdos em larga escala na Internet. O HyperBone implementa um

hipercubo virtual que e reconfigurado dinamicamente para se adaptar as constantes falhas,

recuperacoes e perıodos de instabilidade apresentados pelos nodos do sistema.

O HyperBone e baseado no algoritmo DiVHA, tambem proposto neste trabalho. O

algoritmo DiVHA e utilizado pelo HyperBone e permite que os nodos do sistema man-

tenham, de forma distribuıda, independente e determinıstica, a topologia do hipercubo

virtual, garantido duas propriedade: (1) diametro logaritmico, a distancia entre qualquer

par de nodos e menor ou igual a log2N ; (2) numero maximo de enlaces e Nlog2N . O

DiVHA foi especificado e foram apresentadas as provas formais de correcao do algoritmo.

Um novo algoritmo de diagnostico distribuıdo baseado no DiVHA tambem foi proposto,

especificado e formalmente provado neste trabalho. Este novo algoritmo oferece um sis-

tema de monitoracao distribuıda que permite aos nodos sem falha determinar o estado de

todos os outros nodos do sistema em no maximo log2N rodadas de testes, requerendo no

maximo N ∗ (log2N)2 testes. Resultados experimentais obtidos por simulacao tambem fo-

ram apresentados, comparando o algoritmo de diagnostico baseado no DiVHA com outros

algoritmos de diagnostico similares.

Os nodos do sistema utilizam o HyperBone para se comunicar, todas as mensagens

trocadas entre os nodos sao tuneladas e roteadas atraves dos enlaces do hipercubo virtual,

6 Conclusao 82

permitindo a qualquer par de nodos se comunicar atraves de rotas com distancia maxima

igual a log2N enlaces. Uma estrategia de roteamento que permite determinar as melhores

rotas disponıveis no hipercubo virtual tambem foi proposta. Resultados experimentais

demonstram que as rotas determinadas pelo algoritmo de roteamento podem apresentar

um custo de 8,71 vezes menor que outras rotas no hipercubo.

O HyperBone tambem introduziu uma estrategia para lidar com sistemas nos quais

os nodos apresentam comportamento bastante instavel, alternando frequentemente entre

estados. Esta estrategia classifica os nodos em nodos em available e unavailable e introduz

os parametros de disponibilidade. Estes parametros sao definidos por um perıodo mınimo de

tempo pre-definido em que o nodo deve permanecer no estado working para ser considerado

available, e por um perıodo mınimo de tempo que o nodo deve permanecer no estado

unresponsive para ser considerado unavailable. Isto permite determinar os nodos que estao

apresentando comportamento mais estavel e tem a maior probabilidade de ser utilizados

para tarefas de processamento.

O HyperBone foi implementado utilizando a interface tun/tap provendo uma rede over-

lay transparente para as aplicacoes. O sistema foi testado no PlanetLab que oferece um am-

biente dinamico com os nodos sujeitos a altas carga de processamento e rede. Um conjunto

de testes avaliou o sistema de monitoracao, o HyperBone foi instalado em 128 maquinas

do PlanetLab e sua execucao acompanhada durante cerca de 3 semanas. Estes experi-

mentos avaliaram a funcionalidade do sistema e comprovaram a utilidade dos parametros

de disponibilidade. Outro conjunto de experimentos verificou a possibilidade de execu-

tar aplicacoes paralelas em usando o HyperBone. O ch hyperbone, uma implementacao

alternativa do HyperBone baseada na camada ADI do MPI, tambem foi avaliada.

Trabalhos futuros incluem a implementacao de primitivas de comunicacao em grupo

no hipercubo virtual, permitindo realizar difusao e multicast de forma eficiente. Outro

trabalho futuro e a integracao do HyperBone com um sistema de buscas de informacao,

implementando a busca de forma a tirar proveito da topologia. A integracao do HyperBone

6 Conclusao 83

com uma arquitetura de grades, como o Globus, e outro possıvel trabalho futuro. Final-

mente, outra perspectiva de trabalho e a integracao de mecanismos de tolerancia a falhas

no HyperBone, permitindo a execucao de aplicacoes de longa vida na Internet.

84

Referencias

AGBARIA, A.; FRIEDMAN, R. Starfish: Fault-tolerant dynamic MPI programs onclusters of workstations. 8th International Symposium on High Performance DistributedComputing, p. 167–176, 1999.

ALVISI, L.; MARZULLO, K. Message logging: Pesimistic, optimistic, causal and optimal.15th International Conference on Distributed Computing Systems (ICDSS 1995), p.229–236, 1995.

AMIR, Y.; DANILOV, C. Reliable communication in overlay networks. InternationalConference on Dependable Systems and Networks (DSN 2003), p. 511–520, 2003.

ANDERSEN, D. G.; BALAKRISHNAN, H.; MORRIS, M. F. K. R. Resilient overlaynetworks. Operating Systems Review, p. 131–145, 2001.

BALAKRISHNAN, H. et al. Looking up data in P2P systems. Communications of theACM, v. 46, n. 2, p. 43–48, 2003.

BATCH, R. et al. MPI/ft: Architecture and taxonomies for fault-tolerant. 1st IEEEInternational Symposium of Cluster Computing and the Grid, p. 26–33, 2001.

BEISEL, T.; GABRIEL, E.; RESCH, M. An extension to MPI for distributed computingon MPPs. Lecture Notes in Computer Science, p. 75–82, 1997.

BIANCHINI, R. P.; BUSKENS, R. An adaptive distributed system-level diagnosisalgorithm and its implementation. 21st International Symposium on Fault-TolerantComputing, p. 222–229, 1991.

BIANCHINI, R. P.; BUSKENS, R. Implementation of on-line distributed system-leveldiagnosis theory. IEEE Transactions on Computers, v. 41, p. 616–626, 1992.

BLOUGH, D. M.; BROWN, H. W. The broadcast comparison model for on-line faultdiagnosis in multicomputer systems: Theory and implementation. IEEE Transactions onComputers, v. 48, p. 470–493, 1999.

BOLOSKY, W. J. et al. Feasibility of a serveless distributed file system deployed on anexisting set of desktop PCs. ACM international conference on Measurement and modelingof computer systems, SIGMETRICS, p. 34–43, 2000.

BOLSICA, G. et al. Mpich-v: Towards a scalable fault tolerant MPI for volatile nodes. p.1–18, 2000.

Referencias 85

BONA, L. C. E.; DUARTE Jr., E. P.; FONSECA, K. V. O. Uma arquitetura de gradebaseada em hipercubo virtual. 3o Workshop de Computacao em Grids e Aplicacoes(WCGA), p. 1–5, 2005.

BONA, L. C. E.; DUARTE Jr., E. P.; FONSECA, K. V. O. Self diagnosis based on thedistributed virtual hypercube algorithm. The Latin American Autonomic ComputingSymposium (LAACS), 2006.

BONA, L. C. E. et al. Hyperbone: Uma rede overlay baseada em hipercubo virtual sobrea internet. 24o. Simposio Brasileiro de Redes de Computadores (SBRC), 2006.

BOUTEILLER, A. et al. MPICH-V2: A fault tolerant MPI for volatile nodes basedon pessimistic sender based message logging. IEEE/ACM SC 2003: High PerformanceNetworking and Computing, p. 25–25, 2003.

BOUTEILLER, A. et al. Coordinated checkpoint versus message log for fault tolerantMPI. IEEE International Conference on Cluster Computing (CLUSTER’03), p. 242–250,2003.

CHANDY, K. M.; LAMPORT, L. Distributed snapshots: Determining global states ofdistributed systems. Transactions on Computer Systems, v. 3, n. 1, p. 63–75, 1985.

CLARK, D. Face-to-face with peer-to-peer networking. IEEE Computer, v. 34, n. 1, p.18–21, 2001.

CROPP, W. Abstract device interface specification. Argonne National Laboratory, 1995.

DOVAL, D.; O’MAHONY, D. Overlay networks: A scalable alternative for P2P. IEEEInternet Computing, v. 7, n. 3, p. 2–5, 2003.

DUARTE Jr., E. P.; ALBINI, L. C. P.; BRAWERMAN, A. An algorithm for distributeddiagnosis of dynamic fault and repair events. 7th IEEE International Conference onParallel and Distributed Systems, IEEE/ICPADS’00, p. 299–306, 2000.

DUARTE Jr., E. P.; BRAWERMAN, A.; ALBINI, L. C. P. A diagnosis algorithm basedon clusters with detours. Available at http://www.inf.ufpr.br/ elias., 1998.

DUARTE Jr., E. P. et al. Non-broadcast network fault-monitoring based on system-leveldiagnosis. 5th IFIP/IEEE international symposium on Integrated network management V: integrated management in a virtual world: integrated management in a virtual world, p.597–609, 1997.

DUARTE Jr., E. P.; NANYA, T. A hierarchical adaptive distributed system-level diagnosisalgorithm. IEEE Transactions on Computers, v. 47, n. 1, p. 34–45, 1998.

ELNOZAHY, E. N. et al. A survey of rollback-recovery protocols in message-passingsystems. ACM Computing Surveys, v. 34, n. 3, p. 375–408, 2002.

ERIKSSON, H. Mbone: The multicast backbone. Communications of the ACM, v. 37, p.54–60, 1994.

Referencias 86

FAGG, G.; DONGARRA, J. FT-MPI: Fault tolerant MPI. Lecture Notes in ComputerScience: Proceedings of EuroPVM-MPI 2000, 2000.

FIAT, A.; SAIA, J. Censorship resistant peer-to-peer content addressable networks. 13thACM-SIAM Symposium on Discrete Algorithms, p. 94–103, 2002.

FISCHER, M. J.; LYNCH, N. A.; PATERSON, M. S. Impossibility of distributedconsensus with one faulty process. J. ACM, v. 32, n. 2, p. 374–382, 1985.

FOSTER, I. et al. Software infrastructure for the i-way high performance distributedcomputing experiment. 5th IEEE Symposium on High Performance Distributed Computing,p. 562–571, 1997.

FOSTER, I.; KARONIS, N. A grid-enabled MPI: Message passing in heterogeneousdistributed computing systems. SuperComputing 98, p. 1–11, 1998.

FOSTER, I.; KESSELMAN, C. Globus: A metacomputing infrastructure toolkit.International Journal of Supercomputer Applications, v. 11, n. 3, p. 115–128, 1997.

FOSTER, I.; KESSELMAN, C. The Grid: Blueprint for a new Computing Infrastructure.[S.l.]: Morgan Kaufmann, 1998.

FOSTER, I. et al. The physiology of the grid: Open grid services architecture fordistributed systems integration. The Forth Global Grid Forum, 2002.

FOSTER, I.; KESSELMAN, C.; TUECKE, S. The nexus approach to integratingmultithreading and communication. Journal of Parallel and Distributed Computing(JPDC), v. 37, n. 1, p. 70–82, 1996.

FOSTER, I.; KESSELMAN, C.; TUECKE, S. The anatomy of the grid: Enabling scalablevirtual organizations. International Journal of Supercomputer Applications and HighPerformance Computing, p. 81–89, 2001.

FREY, J. et al. Condor-g: A computation management agent for multi-institutional grids.10th IEEE Symposium on High Performance Distributed Computing (HPDC10), p. 83–91,2001.

GENAUD, S.; GIERSCH, A.; VIVIEN, F. Load-balancing scatter operations for gridcomputing. International Parallel and Distributed Processing Symposium (IPDPS 2003),v. 30, n. 8, p. 923–946, 2003.

GLOBAL GRID FORUM. Global Grid Forum. 2005. Http://www.gridforum.org/. Acessoem: dez. 2005.

GRIMSHAW, A. S.; WULF, W. A. The legion vision of a worldwide virtual computer.Communications of the ACM, v. 40, n. 1, p. 39–45, 1997.

GROPP, W. et al. MPICH: A high-performance portable implementation of MPI. ParallelComputing, v. 22, n. 6, p. 789–828, 1996.

HAKIMI, S. L.; AMIN, A. T. Characterization of connection assignments of diagnosablesystems. IEEE Transactions on Computers, v. 23, p. 86–88, 1974.

Referencias 87

HAKIMI, S. L.; NAKAJIMA, K. On adaptive system diagnosis. IEEE Transactions onComputers, v. 33, p. 234–240, 1984.

HAYDEN, M. The Ensemble System. Tese (Doutorado) — Cornel University, Dept.Computer Sciences, 1997.

HOSSEINI, S. H.; KUHL, J. G.; REDDY, S. M. A diagnosis algorithm for distributedcomputing systems with failure and repair. IEEE Transactions on Computers, v. 33, p.223–233, 1984.

IBM WEB SERVICES ARCHITECTURE TEAM. Web services architecture overview.the next stage of evolution for e-business. IBM Technical Document, Web ArchitectureLibrary, 2000.

KARONIS, N.; TOONEN, B.; FOSTER, I. Mpich-g2: A grid-enabled implementation ofthe message passing interface. Journal of Parallel and Distributed Computing (JPDC),v. 63, n. 5, p. 551–563, 2003.

KARONIS, N. T. et al. Exploiting hierarchy in parallel computer networks to optimizecollective operation performance. In International Parallel and Distributed ProcessingSymposium (IPDPS’00), p. 374–384, 2000.

KIELMANN, T. et al. Magpie: MPI collective communication operations for clusteredwide area systems. in ACM SIGPLAN Symposium on Principles and Practice of ParallelProgramming (Ppopp 99), p. 131–140, 1999.

KRULL, J. M.; WU, J.; MOLINA, A. M. Evaluation of a fault-tolerant distributedbroadcast algorithm in hypercube multicomputers. 20th ACM Annual Computer ScienceConference, p. 11–18, 1992.

LITZKOW, M.; LIVNY, M.; MUTKA, M. Condor - a hunter of idle workstations. 8thInternational Conference of Distributed Computing Systems, p. 104–111, 1998.

LITZKOW, M. et al. Checkpoint and migration of unix processes in the condor distributedprocessing system. Technical Report 1346, Universidade de Wisconsin-Madison, 1997.

LOUCA, S. et al. Mpi-ft: Portable fault tolerant scheme for MPI. Parallel ProcessingLetter, v. 10, n. 4, p. 371–382, 1991.

MACDOUGALL, M. H. Simulating computer systems: techniques and tools. [S.l.]: MITPress, 1987. ISBN 0-262-13229-X.

MASSON, G. M.; BLOUGH, D.; SULLIVAN, G. F. Fault-tolerant computer systemdesign. [S.l.]: Prentice-Hall, Inc., 1996. ISBN 0-13-057887-8.

MELLO, S. L. et al. ch hyperbone: Um dispositivo para execucao de programas MPI emhipercubos virtuais. 4o Workshop de Computacao em Grids e Aplicacoes (WCGA), 2006.

MESSAGE PASSING INTERFACE FORUM. MPI: A message-passing interface standard.International Journal of Supercomputer Applications, v. 8, n. 3/4, p. 165–414, 1994.

Referencias 88

MESSAGE PASSING INTERFACE FORUM. MPI-2: Extensions to the message passinginterface. U. Tennessee, 1997.

MPI-POVRAY. Distributed Povray using MPI message passing. 2003.Http://www.verrall.demon.co.uk/mpipov/. Acesso em marco de 2003.

MPIBENCH. MPIbench Home Page. 2005. Http://icl.cs.utk.edu/projects/llcbench/-mpbench.html. Acesso em: dez. 2005.

NORTHEAST PARALLEL ARCHITECTURES CENTER. RSA Factoring by Web. 2005.Http://www.npac.syr.edu/factoring.html. Acesso em: dez. 2005.

OASIS OPEN. Universal Description, Discovery and Integration (UDDI). 2005.Http://www.uddi.org/. Acesso em: dez. 2005.

OURGRID. OurGrid Home Page. 2005. Http://www.ourgrid.org/. Acesso em: dez. 2005.

PLANETLAB. PlanetLab: An Open Plataform for Developing, Deploying, and AccessPlanetary-Scale Services. 2005. Http://www.planet-lab.org. Acesso em: dez. 2005.

PREPARATA, G. M. F.; CHIEN, R. T. On the connection assignment problem ofdiagnosable systems. IEEE Transactions on Electronic Computers, v. 16, p. 848–854,1967.

QBONE. QBone Home Page. 2005. Http://qbone.internet2.edu. Acesso em: dez. 2005.

RANGARAJAN, S.; DAHBURA, A. T.; ZIEGLER, E. A. A distributed system-leveldiagnosis for arbitrary network topologies. IEEE Transactions on Computers, v. 44, p.312–333, 1995.

RATNASAMY, S. et al. A scalable content addressable network. ACM SIGCOMM, p.161–197, 2001.

ROWSTRON, A.; DRUSCHEL, P. Pastry: Scalable distributed object location androuting for large-scale peer-to-peer systems. IFIP/ACM International Conference onDistributed Systems Platforms, p. 329–350, 2001.

SAAD, Y.; SCHULTZ, M. H. Topological properties of hypercube. ACM Transactions onComputers, v. 37, n. 7, p. 867–872, 1998.

SAIA, J. et al. Dynamically fault-tolerant content addressable networks. 1st InternationalWorkshop on Peer-to-Peer Systems (IPTPS ’02), p. 270–279, 2002.

SCHLOSSER, M. et al. Hypercup - hypercubes, ontologies and P2P networks. LectureNotes on Computer Science, v. 2530, p. 112–124, 2002.

SETI INSTITUTE. Home SETI Institute. 2005. Http://www.seti.org/. Acesso em: dez.2005.

SQUYRES, J. M.; LUMSDAINE, A. A component architecture for LAM/MPI. 10thEuropean PVM/MPI Users’ Group Meeting, p. 379–387, 2003.

Referencias 89

STELLNER, G. Cocheck: Checkpointing and process migration for MPI. 10th IEEEInternational Parallel Processing Symposium (IPPS 96), p. 526–531, 1996.

STOICA, I. et al. Chord: A scalable peer-to-peer lookup service for internet application.ACM SIGCOMM, p. 149–160, 2001.

SUPINSKI, B.; KARONIS, N. T. Accurately measuring MPI broadcasts in a computationalgrid. 8th IEEE Symposium on High Performance Distributed Computing, p. 4, 1999.

TIEN, S.-B.; RAGHAVENDRA, C. S. Algorithms and bounds for shortest paths anddiameter in faulty hypercubes. IEEE Transactions on Parallel and Distributed Systems, p.713–718, 1993.

TUECKE, S. et al. Open grid services infrastructure (ogsi) version 1.0. Global Grid ForumDraft Recommendation, 2003.

TUNTAP. Universal TUN/TAP Driver. 2005. Http://vtun.sourceforge.net/tun/. Acessoem: dez. 2005.

UNIVERSITY OF CHICAGO. The Globus Alliance. 2005. Http://www.globus.org.Acesso em: dez. 2005.

UNIVERSITY OF WISCONSIN MADISON. Condor Project Homepage. 2005.Http://www.cs.wisc.edu/condor/. Acesso em: dez. 2005.

WAHL, M.; KILLE, S.; HOWES, T. Lightweight directory access protocol (v3). Requestfor Comments (RFC) 2251, 1997.

WORLD WIDE WEB CONSORTIUM. SOAP Standard. 2005.Http://www.w3.org/TR/soap/. Acesso em: dez. 2005.

WORLD WIDE WEB CONSORTIUM. Web Services Description Language (WSDL).2005. Http://www.w3.org/TR/wsdl. Acesso em: dez. 2005.

WORLD WIDE WEB CONSORTIUM. XML Protocol Working Group. 2005.Http://www.w3c.org/2000/xp/Group/. Acesso em: dez. 2005.

ZHAO, B. Y. et al. Tapestry: a resilient global-scale overlay for service deployment. IEEEJournal on Selected Areas in Communications, v. 2, n. 1, p. 41–53, 2004.

ZHUANG, S. et al. On failure detection algorithms in overlay networks. 24th IEEEInfocom 2005, p. 13–17, 2005.

Documents

UNIVERSIDADE TECNOLOGICA FEDERAL DO PARAN´ A´ … fileLuis Carlos Erpen De Bona HyperBone: Uma Rede Overlay Baseada em Hipercubo Virtual para Computa¸c˜ao Distribu´ıda na Internet