Implementação e Análise de Desempenho de um Mecanismo Adaptativo para Tolerância a Falhas em Sistemas Distribuídos com QoS

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 5
 
  Implementação e Análise de Desempenho de um Mecanismo Adaptativo para Tolerância a Falhas em Sistemas Distribuídos com QoS
Share
Transcript
  Implementação e Análise de Desempenho de um Mecanismo Adaptativo para Tolerância a Falhas em Sistemas Distribuídos com QoS Sérgio Gorender 1 , Raimundo J. A. Macêdo, Matheus Cunha Laboratório de Sistemas Distribuídos (LaSiD) Departamento de Ciência da Computação (DCC) Universidade Federal da Bahia (UFBA) Av. Adhemar de Barros S/N, Ondina, Salvador - BA, CEP: 40.170-11 {gorender, macedo, matheusc}@ufba.br Resumo.  Tolerância a falhas e adaptabilidade são requisitos importantes para sistemas distribuídos modernos, especialmente aqueles que precisam se adaptar dinamicamente para diferentes níveis de qualidade de serviço ( QoS  ). Neste artigo, apresentamos a implementação de uma infraestrutura de comunicação e gerenciamento de recursos de QoS  , implementada sobre uma rede de estações LINUX equipadas com um pacote de controle de trafego (  DiffServ ). Baseados nesta estrutura, mostramos a implementação de um mecanismo de tolerância a falhas adaptável em tempo de execução ( run-time ) a diferentes níveis de QoS  , o qual é composto de um detector de defeitos e um módulo de consenso. O protocolo de consenso apresentado goza de uma propriedade bastante interessante: a de poder operar concomitantemente, numa mesma execução, com diferentes níveis de QoS   para processos distintos, caracterizando um modelo híbrido de tolerância a falhas. Também apresentamos dados de desempenho coletados a partir de vários experimentos onde foram medidos os tempos de obtenção de consenso para cenários diversos. Abstract.  Fault tolerance and adaptability are important issues for modern distributed systems. The capability of dynamically adapting to distinct run-time conditions is especially relevant for environments where negotiated QoS conditions cannot always be delivered between communicating processes. In this paper, we present an implementation of a framework for communication and resource management, using a network of LINUX workstations, which were equipped with a traffic control packet. We also implemented a fault tolerant mechanism, composed of a failure detector and a consensus protocol, which dynamic adapts to distinct QoS levels. The consensus protocol has the property that in the same consensus distinct processes can have different QoS, which characterize a hybrid fault tolerant model. We also measure the execution of the consensus, and present the result of these experiments. 1  Aluno de doutorado do CIN/UFPE, pesquisador do LaSiD/UFBA e professor do DCC/UFBA e da Faculdade Ruy Barbosa.  1. Introdução Tolerância a falhas adaptativa é um requisito importante para sistemas distribuídos modernos, especialmente em sistemas que executam em ambientes com diferentes níveis de qualidade de serviço ( QoS  ) [20]. Os mecanismos de tolerância à falhas, em geral, assumem um modelo de execução específico. No modelo síncrono existem limites temporais conhecidos e garantidos para os serviços de execução (execução de passos dos processos e transferência de mensagens), enquanto que no modelo assíncrono estes limites temporais não existem. Para o modelo assíncrono foi provado em [10] a impossibilidade de se obter o consenso tolerando falhas. Devido a esta impossibilidade foram criados os modelos chamados parcialmente síncronos, que estendem o modelo assíncrono com características síncronas [9, 8, 7, 19]. O consenso distribuído é freqüentemente utilizado como uma forma de testar a tolerância à falhas destes modelos, além de ser utilizado em diversas aplicações distribuídas. Por outro lado, utilizando as novas tecnologias para prover um ambiente de execução com diferentes níveis de serviço [3, 5, 20], podemos obter um ambiente híbrido, no qual convivem serviços de execução isócronos (serviços realizados dentro de limites de tempo previamente definidos) e serviços de execução não isócronos (sem limites de tempo). Além disso, os serviços de execução podem ter o seu nível de qualidade alterado dinamicamente, o que exige dos sistemas a capacidade de se adaptar a estas alterações. Ou seja, além das aplicações, os mecanismos de tolerância a falhas precisam ser adaptativos nesses ambientes com QoS. Neste artigo, apresentamos a implementação de uma infraestrutura de comunicação e gerenciamento de recursos de QoS  , implementada sobre uma rede de estações LINUX equipadas com pacotes de controle de tráfego funcionando segundo a arquitetura Serviços Diferenciados (  DiffServ ) [5]. Baseados nessa estrutura, mostramos a implementação de um mecanismo de tolerância a falhas, composto de um detector de defeitos e um módulo de consenso, que são adaptáveis em tempo de execução ( run-time ) a diferentes níveis de QoS   [11, 12]. O protocolo de consenso descrito goza de uma propriedade bastante interessante: a de poder operar concomitantemente, numa mesma execução, com diferentes níveis de QoS   para os processos distintos, caracterizando um modelo híbrido de tolerância a falhas. Também apresentamos dados de desempenho coletados a partir de vários experimentos onde foram medidos os tempos de obtenção de consenso para cenários diversos. Na seção 2, a seguir, são apresentadas uma infraestrutura de comunicação e gerenciamento de recursos e sua implementação. Na seção 3 são apresentados os conceitos básicos de um detector de defeitos adaptativo e de um algoritmo de consenso híbrido e adaptativo, assim como a implementação destes dois mecanismos. Na seção 4 são apresentados resultados obtidos com a execução do protótipo implementado e uma análise de desempenho. Os trabalhos correlatos são apresentados na seção 6 e na seção 7 apresentamos algumas conclusões. 2. Infraestrutura de comunicação e gerenciamento de recursos O ambiente de comunicação é composto por canais de comunicação, os quais são providos com diferentes níveis de serviço, segundo a arquitetura Serviços Diferenciados (  DiffServ ) para prover QoS [5]. A arquitetura DiffServ determina que os fluxos de informação (pacotes de dados) a ser transferidos sejam atribuídos a classes de serviço para o encaminhamento de pacotes. Estas classes de serviço determinam o nível do  serviço de comunicação que será provido ao fluxo de pacotes. Cada classe é definida baseada em requisitos, tais como um atraso limitado ou não limitado para a transferência de pacotes, um  jitter   (variação no atraso) alto ou restrito, uma maior ou menor prioridade para o descarte de pacotes e uma maior ou menor largura de banda. Cada classe de serviço na arquitetura  DiffServ  é identificada através de um valor especial, chamado  DiffServ Code Point   (DSCP), o qual é armazenado no campo Type of Service  (ToS) do cabeçalho IP de cada pacote. Quando um pacote entra em uma rede  DiffServ , diversos campos de seu cabeçalho IP são analisados com o objetivo de se identificar a que classe de encaminhamento o pacote deve ser associado (classificação do pacotes), e o pacote tem um valor DSCP armazenado no seu campo ToS (marcação do pacote). O roteador que marca os pacotes é chamado de roteador de borda. Os demais roteadores no caminho do pacote até o seu destino (rota), os quais são chamados de roteadores de núcleo, apenas analisam o valor DSCP armazenado mo cabeçalho do pacote e encaminham o pacote de acordo com a classe de serviço associada a este valor. Existem diversas classes de serviço definidas na arquitetura  DiffServ . Entre estas, os Serviços Expressos fornecem uma comunicação isócrona, garantindo limites máximos para a transferência de pacotes. Esta garantia é fornecida através de altas prioridades para o encaminhamento, e de uma alta taxa de transmissão, suficiente para transmitir imediatamente todo pacote que chegue a um roteador. As demais classes fornecem serviços de comunicação não isócronos, sem garantias temporais. Estas classes atribuem diferentes prioridades para o descarte de pacotes, no caso de haver congestionamentos nos roteadores. Chamamos os canais de comunicação criados com serviços isócronos (Serviço Expresso) de canais de comunicação timely , e os canais de comunicação criados com serviços não isócronos de canais untimely . Implementamos classes de serviço isócrono e não isócrono para o encaminhamento de fluxos de pacotes foram implementadas no ambiente de execução, o qual é composto por em estações LINUX configuradas para funcionar como roteadores. Para criar estas classes de serviço utilizamos um pacote de controle de tráfego para o LINUX, chamado TC. Este pacote define uma linguagem, a qual é utilizada para a definição das classes de serviço para o encaminhamento de pacotes, através da construção de scripts . As classes de serviço são criadas a partir da definição de filas para o armazenamento dos pacotes a serem encaminhados, uma para cada classe. Para cada fila é definida uma prioridade para o encaminhamento de pacotes, além de um algoritmo específico para o gerenciamento da fila e disciplinas de filas adequadas à definição da classe. A disciplina de fila DSMark [20] implementa a marcação de pacotes com um valor DSCP nos roteadores de borda, antes de estes roteadores encaminharem os pacotes. Esta mesma disciplina de fila é utilizada pelos roteadores de núcleo para classificarem cada pacote para a classe de serviço apropriada, dependendo apenas do conteúdo do campo ToS (valor DSCP). Na definição das filas para o encaminhamento de pacotes, o TC permite definir a largura de banda aplicada a cada fila, a prioridade para o encaminhamento de pacotes, o algoritmo de fila a ser utilizado e outros requisitos, permitindo assim a definição de uma classe de encaminhamento isócrona, com uma alta largura de banda e prioridade máxima para o encaminhamento de pacotes. A infraestrutura de gerenciamento de comunicação (QoS Provider) e o mecanismo para sistemas distribuídos tolerantes a falhas (detector de defeitos e consenso) foram implementados na linguagem Java e testados sobre o ambiente de  comunicação criado com o LINUX e o pacote TC. 2.1 QoS Provider Denominamos de QoS Provider   o mecanismo que desenvolvemos e implementamos cuja atribuição é criar canais de comunicação para a aplicação e gerenciar o nível do serviço de comunicação fornecido a cada canal. Este mecanismo executa distribuído em módulos associados aos processos do sistema. Gerenciar a QoS dos canais de comunicação implica em negociar o nível do serviço a ser provido a cada canal e monitorar este serviço durante a sua execução. As funções CreateChannel() ,  DefineQoS() ,  Delay()  e QoS()  são chamadas pelos processos das aplicações distribuídas para criar canais de comunicação entre processos, negociar a QoS   para um determinado canal de comunicação, determinar o atraso na transferência de mensagens para um canal de comunicação e monitorar a QoS   corrente atribuída a um canal de comunicação. É importante notar que a função  Delay()  retorna um valor probabilístico se o canal de comunicação for untimely , mas retorna um valor determinado caso este canal de comunicação seja timely . Além destas funções, o QoS Provider monitora todos os canais de comunicação timely , para verificar se estes canais continuam sendo providos com serviços isócronos. Esta monitoração é feita utilizando mensagens de um protocolo de sinalização, que permitam a troca de informações entre os módulos do QoS Provider e os roteadores e provedores de serviços de comunicação. Sempre que for identificada alguma alteração na qualidade de serviço provida a um canal, fazendo este canal passar a untimely , esta alteração é sinalizada aos processos comunicantes.   Os conceitos que foram utilizados no desenvolvimento do QoS Provider foram baseados em diversas arquiteturas desenvolvidas para prover QoS   fim-a-fim a aplicações distribuídas [3], como por exemplo a arquitetura Omega e o dispositivo QoS Broker [18]. 2.2 Implementação do QoS Provider Foi desenvolvida uma implementação inicial do QoS Provider com o objetivo básico de criar canais de comunicação e fornecer estes canais para os processos solicitantes. Nesta implementação as funções CreateChannel()  e  Delay()  foram implementadas. As demais funcionalidades do QoS Provider, tais como negociar a QoS   dos canais de comunicação e monitorar esta QoS   ainda estão sendo desenvolvidas. Nesta implementação inicial as classes de serviço isócrono e não isócrono são criadas diretamente nos roteadores LINUX, através da execução de scripts  criados com a linguagem TC. Desta forma, a cada teste realizado, pudemos estabelecer os canais de comunicação como sendo timely  ou untimely . O QoS Provider possui duas classes principais, Provider   e  Negotiator  . A classe Provider   faz a interface entre o processo que está requisitando o canal de comunicação e o provedor de serviço da rede, e utiliza a classe  Negotiator   para acessar o provedor de serviço de comunicação. Quando um processo solicita a criação de um canal de comunicação com um outro processo, a instância da classe  Negotiator   pertencente ao processo solicitante envia uma mensagem  BeginNegotiation  ao outro processo. Ao receber esta mensagem, a instância da classe  Negotiator   deste outro processo registra a requisição e envia uma mensagem  EndNegotiation  para o processo solicitante, finalizando assim o estabelecimento do canal de comunicação. O canal de comunicação  criado é do tipo UDP/IP . 3. Implementação de um mecanismo adaptativo tolerante a falhas para sistemas distribuídos Apresentamos uma visão geral do mecanismo adaptativo tolerante a falhas para sistemas distribuídos [11, 12], o qual foi implementado em Java/LINUX sobre a infraestrutura de comunicação apresentada na seção 2. Um sistema distribuído é composto por um conjunto Π ={p 1 , ..., p n } de processos, conectados por canais de comunicação pertencentes ao conjunto C={c 1/2 , ..., c 1/n , ..., c n-1/n }. Os conjuntos Π  e C formam o grafo completo DS( Π , C}. Assumimos no nosso sistema o modelo assíncrono aumentado com detectores de defeitos não confiáveis, como apresentado por Chandra & Toueg em [6]. Assumimos adicionalmente que os canais de comunicação podem ser fornecidos com QoS  , de acordo com a arquitetura Serviços Diferenciados, como apresentado na seção anterior. Assumimos também que os processos falham por crash . 3.1 Detector de defeitos adaptativo O detector de defeitos adaptativo executa distribuído em módulos, um para cada processo do sistema. Os módulos do detector de defeitos dos processos em funcionamento enviam solicitações periódicas de mensagens de heartbeat   para todos os demais módulos através dos canais de comunicação, e esperam por mensagens de heartbeat   em resposta, até a ocorrência de um timeout  , previamente calculado. O timeout   para cada mensagem de heartbeat   é calculado a partir do atraso para a transferência de mensagens, o qual é determinado para cada canal de comunicação. Por sua vez, este atraso é calculado pela função  Delay()  do QoS Provider. Para canais de comunicação timely  o atraso informado pela função  Delay()  é garantido, enquanto o canal permanecer timely , enquanto que para canais untimely  o atraso informado é probabilístico. Considerando as classes de serviço dos canais de comunicação existem dois tipos de detecção de defeitos: suspeitas, no caso de o canal de comunicação ser untimely , e notificações, se o canal de comunicação for timely . Como os módulos divulgam as notificações realizadas, um processo que possua ao menos um canal de comunicação timely  será notificado por todos os processos corretos, caso venha a falhar. Conseqüentemente, podemos classificar os processos operacionais como suspeitáveis ou notificáveis, inserindo a identificação destes processos, respectivamente, nos conjuntos suspeitáveis  e notificáveis . Esta classificação é efetuada e atualizada por cada módulo do detector de defeitos, a partir da análise de uma representação local do grafo DS com informações sobre a QoS   de cada canal de comunicação, obtidas através da função QoS() do QoS Provider, e de informações que são trocadas entre os módulos. Apenas processos cuja identificação pertence ao conjunto notificáveis  podem ser notificados pelos módulos do detector de defeitos. Os demais processos só podem ser suspeitos de terem falhado. Processos notificáveis não podem ser erroneamente suspeitos por nenhum módulo do detector de defeitos, uma vez que um módulo que não possua canal de comunicação timely  com este processo não irá monitorá-lo, apenas notificando uma falha deste processo, se receber uma mensagem, de outro módulo, comunicando esta notificação. Processos que são notificados têm a sua identificação retirada do conjunto
Related Search
Similar documents
View more
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x