ANAIS

XXIX Simpósio Brasileiro de Redes de Computadores e Sistemas

Distribuídos 30 de maio a 3 de junho de 2011

Campo Grande, MS

I Workshop on Autonomic Distributed Systems (WoSIDA)

Editora Sociedade Brasileira de Computação (SBC)

Organizadores

Raimundo José de Araúlo Macêdo (UFBA) Fábio Moreira Costa (UFG)

Ronaldo Alves Ferreira (UFMS)

Realização Faculdade de Computação

Universidade Federal de Mato Grosso do Sul (UFMS)

Promoção Sociedade Brasileira de Computação (SBC)

Laboratório Nacional de Redes de Computadores (LARC)

ii Anais

Copyright © 2011 da Sociedade Brasileira de Computação Todos os direitos reservados Capa: Venise Melo Produção Editorial: Lucilene Vilela Gonçalves, Ronaldo Alves Ferreira Cópias Adicionais: Sociedade Brasileira de Computação (SBC) Av. Bento Gonçalves, 9500 – Setor 4 – Prédio 43.412 – Sala 219 Bairro Agronomia – CEP 91.509-900 – Porto Alegre – RS Fone: (51) 3308-6835 E-mail: sbc@sbc.org.br Dados Internacionais de Catalogação na Publicação (CIP)

Workshop on Autonomic Distributed Systems (1.: 2011 : Campo Grande, MS). Anais / I Workshop on Autonomic Distributed Systems; organizadores Raimundo José

de Araújo Macêdo... et al. – Porto Alegre : SBC, c2011. 43 p. ISSN 2177-496X 1. Redes de computadores. 2. Sistemas distribuídos. I. Macêdo, Raimundo José de

Araújo. II. Título.

I Workshop on Autonomic Distributed Systems iii

Promoção Sociedade Brasileira de Computação (SBC) Diretoria Presidente José Carlos Maldonado (USP) Vice-Presidente Marcelo Walter (UFRGS) Diretor Administrativo Luciano Paschoal Gaspary (UFRGS) Diretor de Finanças Paulo Cesar Masiero (USP) Diretor de Eventos e Comissões Especiais Lisandro Zambenedetti Granville (UFRGS) Diretora de Educação Mirella Moura Moro (UFMG) Diretora de Publicações Karin Breitman (PUC-Rio) Diretora de Planejamento e Programas Especiais Ana Carolina Salgado (UFPE) Diretora de Secretarias Regionais Thais Vasconcelos Batista (UFRN) Diretor de Divulgação e Marketing Altigran Soares da Silva (UFAM) Diretor de Regulamentação da Profissão Ricardo de Oliveira Anido (UNICAMP) Diretor de Eventos Especiais Carlos Eduardo Ferreira (USP) Diretor de Cooperação com Sociedades Científicas Marcelo Walter (UFRGS)

iv Anais

Promoção Conselho Mandato 2009-2013 Virgílio Almeida (UFMG) Flávio Rech Wagner (UFRGS) Silvio Romero de Lemos Meira (UFPE) Itana Maria de Souza Gimenes (UEM) Jacques Wainer (UNICAMP) Mandato 2007-2011 Cláudia Maria Bauzer Medeiros (UNICAMP) Roberto da Silva Bigonha (UFMG) Cláudio Leonardo Lucchesi (UFMS) Daltro José Nunes (UFRGS) André Ponce de Leon F. de Carvalho (USP) Suplentes – Mandato 2009-2011 Geraldo B. Xexeo (UFRJ) Taisy Silva Weber (UFRGS) Marta Lima de Queiroz Mattoso (UFRJ) Raul Sidnei Wazlawick (PUCRS) Renata Vieira (PUCRS) Laboratório Nacional de Redes de Computadores (LARC) Diretoria Diretor do Conselho Técnico-Científico Artur Ziviani (LNCC) Diretor Executivo Célio Vinicius Neves de Albuquerque (UFF) Vice-Diretora do Conselho Técnico-Científico Flávia Coimbra Delicato (UFRN) Vice-Diretor Executivo Luciano Paschoal Gaspary (UFRGS) Membros Institucionais CEFET-CE, CEFET-PR, IME, INPE/MCT, LNCC, PUCPR, PUC-RIO, SESU/MEC, UECEM UERJ, UFAM, UFBA, UFC, UFCG, UFES, UFF, UFMG, UFMS, UFPA, UFPB, UFPE, UFPR, UFRGS, UFRJ, UFRN, UFSC, UFSCAR, UNICAMP, UNIFACS, USP

I Workshop on Autonomic Distributed Systems v

Realização Comitê de Organização Coordenação Geral Ronaldo Alves Ferreira (UFMS) Coordenação do Comitê de Programa Artur Ziviani (LNCC) Bruno Schulze (LNCC) Coordenação de Palestras e Tutoriais Nelson Luis Saldanha da Fonseca (UNICAMP) Coordenação de Painéis e Debates José Augusto Suruagy Monteiro (UNIFACS) Coordenação de Minicursos Fabíola Gonçalves Pereira Greve (UFBA) Coordenação de Workshops Fábio Moreira Costa (UFG) Coordenação do Salão de Ferramentas Luis Carlos Erpen De Bona (UFPR) Comitê Consultivo Antônio Jorge Gomes Abelém (UFPA) Carlos André Guimarães Ferraz (UFPE) Francisco Vilar Brasileiro (UFCG) Lisandro Zambenedetti Granville (UFRGS) Luci Pirmez (UFRJ) Luciano Paschoal Gaspary (UFRGS) Marinho Pilla Barcellos (UFRGS) Paulo André da Silva Gonçalves (UFPE) Thais Vasconcelos Batista (UFRN)

vi Anais

Realização Organização Local Brivaldo Alves da Silva Jr. (UFMS) Edson Norberto Cáceres (UFMS) Eduardo Carlos Souza Martins (UFMS/POP-MS) Hana Karina Sales Rubinstejn (UFMS) Irineu Sotoma (UFMS) Kátia Mara França (UFMS) Luciano Gonda (UFMS) Lucilene Vilela Gonçalves (POP-MS) Márcio Aparecido Inácio da Silva (UFMS) Marcos Paulo Moro (UFGD) Massashi Emilson Oshiro (POP-MS) Nalvo Franco de Almeida Jr. (UFMS) Péricles Christian Moraes Lopes (UFMS) Renato Porfírio Ishii (UFMS)

I Workshop on Autonomic Distributed Systems vii

Mensagem do Coordenador Geral Sejam bem-vindos ao XXIX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC 2011) em Campo Grande, MS. É um prazer e uma distinção organizar um simpósio de tamanha relevância para a Computação no Brasil, mais ainda por ser a primeira vez que a Região Centro-Oeste tem o privilégio de sediá-lo. O SBRC é um evento anual promovido pela Sociedade Brasileira de Computação (SBC) e pelo Laboratório Nacional de Redes de Computadores (LARC). Ao longo dos seus quase trinta anos, o SBRC tornou-se o mais importante evento científico nacional em Redes de Computadores e Sistemas Distribuídos e um dos maiores da área de Informática no país. O SBRC 2011 está com uma programação bastante rica, de qualidade diferenciada e que consiste em: 18 sessões técnicas de artigos completos que abordam o que há de mais novo nas áreas de redes de computadores e sistemas distribuídos; três sessões técnicas para apresentação de ferramentas selecionadas para o Salão de Ferramentas; cinco minicursos, com quatro horas de duração, sobre temas atuais; três palestras e três tutoriais com pesquisadores de alto prestígio internacional; e três painéis sobre assuntos de interesse da comunidade. Além dessas já tradicionais atividades do simpósio, ocorrerão em paralelo oito workshops: XVI Workshop de Gerência e Operação de Redes e Serviços (WGRS), XII Workshop da Rede Nacional de Ensino e Pesquisa (WRNP), XII Workshop de Testes e Tolerância a Falhas (WTF), IX Workshop em Clouds, Grids e Aplicações (WCGA), VII Workshop de Redes Dinâmicas e Sistemas P2P (WP2P), II Workshop de Pesquisa Experimental da Internet do Futuro (WPEIF), I Workshop on A utonomic Distributed Systems (WoSIDA) e I Workshop de Redes de Acesso em Banda Larga (WRA). O desafio de organizar um evento como o SBRC só pode ser cumprido com a ajuda de um grupo especial. Eu tive a f elicidade de contar com a co laboração de inúmeras pessoas ao longo desta jornada. Meus sinceros agradecimentos aos membros dos Comitês de Organização Geral e Local por realizarem um trabalho de excelente qualidade e com muita eficiência, a qualidade da programação deste simpósio é fruto do trabalho dedicado dessas pessoas. Sou grato a Faculdade de Computação da UFMS por ter sido uma facilitadora ao longo de todo o pr ocesso de organização, desde a nossa proposta inicial até o fechamento da programação. Gostaria de agradecer, também, ao Comitê Gestor da Internet no Brasil (CGI.br), às agências governamentais de fomento e aos patrocinadores por reconhecerem a importância do S BRC e investirem recursos financeiros fundamentais para a realização do evento. Com o apoio financeiro recebido, foi possível manter os custos de inscrição baixos e oferecer um programa social de alta qualidade. Em nome do Comitê Organizador, agradeço a todos os participantes pela presença em mais esta edição do SBRC e d esejo uma semana produtiva, agradável e com estabelecimento de novas parcerias e amizades.

Ronaldo Alves Ferreira Coordenador Geral do SBRC 2011

viii Anais

Mensagem do Coordenador de Workshops do SBRC 2011 Os workshops são uma parte tradicional do que hoje faz do SBRC o principal evento da área no país, sendo responsáveis por atrair uma parcela cada vez mais expressiva de participantes para o S impósio todos os anos. O SBRC 2011 pr ocurou manter essa tradição, com a realização de workshops já considerados parte do circuito nacional de divulgação científica nas várias subáreas de Redes de Computadores e S istemas Distribuídos, como o WTF (Workshop de Testes e Tolerância a Falhas), o W CGA (Workshop em Clouds, Grids e Aplicações), o WGRS ( Workshop de Gerência e Operação de Redes e Serviços) e o WP2P (Workshop de Redes Dinâmicas e Sistemas P2P). Incluímos também nesta lista de iniciativas bem sucedidas o WRNP (Workshop da Rede Nacional de Ensino e Pesquisa), que cumpre o importantíssimo papel de fazer a ponte entre as comunidades técnica e científica da área. Como novidade em 2011, e reconhecendo o s urgimento e o fortalecimento de novas linhas de pesquisa de expressiva importância dentro da comunidade brasileira de Redes e Sistemas Distribuídos, procuramos incentivar a criação de novos workshops dentro do Simpósio. Foi com esse intuito que introduzimos pela primeira vez no SBRC a chamada aberta de workshops, por meio da qual membros da comunidade foram convidados a submeter propostas de workshops inéditos para realização em conjunto com o S BRC 2011. Em resposta à chamada, recebemos nove propostas de alta qualidade, das quais oito foram aceitas e seus respectivos proponentes convidados a organizarem os workshops no SBRC em Campo Grande. Das oito propostas aceitas, cinco tratavam dos workshops já tradicionais acima mencionados, e uma referia-se à segunda edição de um workshop mais recentemente criado, mas que teve sua primeira edição realizada de forma muito bem sucedida no SBRC 2010, o WPEIF (Workshop de Pesquisa Experimental da Internet do Futuro). As outras duas propostas foram resultado direto da chamada aberta de workshops e resultaram na adição de dois novos eventos ao leque do SBRC, o WRA (Workshop de Redes de Acesso em Banda Larga) e o WoSiDA (Workshop on Autonomic Distributed Systems), ambos com ótima aceitação pela comunidade, a julgar pelos números de submissões de trabalhos recebidos. Esperamos que 2011 s eja mais um ano de sucesso para os workshops do S BRC, em particular para aqueles criados nesta edição do Simpósio, e para que eles continuem contribuindo como importantes fatores de agregação para os avanços promovidos pela comunidade científica da área de Redes e Sistemas Distribuídos no Brasil. Aproveitamos para agradecer o i nestimável apoio recebido de diversos membros da comunidade e, em particular, da Organização Geral do SBRC 2011. A todos, um excelente SBRC em Campo Grande!

Fábio M. Costa Coordenador de Workshops do SBRC 2011

I Workshop on Autonomic Distributed Systems ix

Mensagem do Coordenador do WoSIDA The Workshop on Autonomic Distributed Systems (WoSiDA), Co-located with the Brazilian Symposium on Computer Networks and Distributed Systems, was aimed at bringing together researchers and practitioners from the distributed systems community to discuss the fundamental principles, state of the art, and critical challenges of self-managing or autonomic distributed systems.

The WoSiDA 2011 program included 9 position papers selected from 17 submissions. The reviewing and selecting process was careful, where each paper was distributed to at least three members of the technical program committee. The acceptance decision was taken after an evaluation of all reviews, paying attention to the review’s comments - not just the review’ scores. The accepted papers are those considered by the reviewers the most solid work among the set analyzed, and they cover distinct aspects of autonomic distributed systems. Together the accepted papers give a broad view of what is being investigated in this field mainly in Brazil, but also Portugal. Besides the presentation and discussion of the accepted papers, organized into three technical sections, we planned a panel where invited speakers can present distinct views on the design of autonomic distributed systems. Finally, I would like to thank very much the program committee members for having accepted the challenge of building this program, and the organizers of SBRC 2011 for their support.

Raimundo José de Araújo Macêdo Coordenador do WoSiDA 2011

x Anais

Comitê de Programa do WoSIDA Antonio Alfredo F. Loureiro (UFMG) Antonio Casimiro Costa (FCUL - Portugal) Carlos Andre Guimarães Ferraz (UFPE) Edmundo Madeira (UNICAMP) Flávio Assis Silva (UFBA) Joberto Martins (UNIFACS) Lisandro Zambenedetti Granville (UFRGS) Luciano Paschoal Gaspary (UFRGS) Luís da Cunha Lamb (UFRGS) Luis Rodrigues (INESC-ID/IST-UTL - Portugal) Neuman Souza (UFC) Orlando Loques (UFF) Renato Cerqueira (PUC-Rio) Raimundo José de Araújo Macêdo (UFBA) Rui Oliveira (UMINHO - Portugal) Sérgio Gorender (UFBA)

I Workshop on Autonomic Distributed Systems xi

Revisores do WoSIDA Antonio Alfredo F. Loureiro (UFMG) Antonio Casimiro Costa (FCUL - Portugal) Carlos Andre Guimarães Ferraz (UFPE) Edmundo Madeira (UNICAMP) Flávio Assis Silva (UFBA) Joberto Martins (UNIFACS) Lisandro Zambenedetti Granville (UFRGS) Luciano Paschoal Gaspary (UFRGS) Luís da Cunha Lamb (UFRGS) Luis Rodrigues (INESC-ID/IST-UTL - Portugal) Neuman Souza (UFC) Orlando Loques (UFF) Renato Cerqueira (PUC-Rio) Raimundo José de Araújo Macêdo (UFBA) Rui Oliveira (UMINHO - Portugal) Sérgio Gorender (UFBA)

xii Anais

I Workshop on Autonomic Distributed Systems xiii

Sumário

Sessão Técnica 1 .............................................................................................................. 1

Aplicações Autônomas + Sistemas Simples = Futuro Feliz? Fernanda G. Oliveira e Vinod E. F. Rebello (UFF) ..................................................... 3

Computação em Nuvem Autônoma: Oportunidades e Desafios Flávio R. C. Sousa, Leonardo O. Moreira e Javam C. Machado (UFC) ..................... 7

Sintonia Automática de Banco de Dados em Nuvem Mônica Regina da Silva, Javam de Castro Machado, José Maria Monteiro e José Antônio F. de Macêdo (UFC) ..................................................................................... 11

Sessão Técnica 2 ............................................................................................................ 15

From Static to Dynamic Protocols: Adapting Timeouts for Improved Performance A. Casimiro e M. Dixit (University of Lisbon) ............................................................ 17

Automatically Tuned on Multicore Systems Murilo Boratto (UNIVASF), Leandro Coelho (UNEB) e Brauliro Leal (UNIVASF). 21

Gerência Autonômica de Redes DTN Ewerton M. Salvador, Daniel F. Macedo e José Marcos S. Nogueira (UFMG) ....... 25

Sessão Técnica 3 ............................................................................................................ 29

Combinação de Expertise em Classificadores para Sistemas Autonômicos Grinaldo Oliveira e Joberto Martins (UFBA-UEFS-UNIFACS) ............................... 31

Uma Proposta para o Monitoramento e Controle Inteligente de Tráfego Urbano Gilberto Nakamiti (PUC-Campinas/UNIP), Fábio Pessôa de Sá (FATEC-PG), José Henrique Ventura e Vinicius Eduardo S. da Silva (UNIP) ......................................... 35

Um Sistema Autônomo para a Coordenação de Dispositivos Móveis Baseada em Coalizões Sobrepostas Vitor A. dos Santos, Giovanni C. Barroso, Mario F. Aguilar (UFC), Antonio de B. Serra (IFCE) e José M. Soares (UFC) ....................................................................... 39

Índice por Autor ........................................................................................................... 43

I Workshop on Autonomic Distributed Systems

♦ Sessão Técnica 1

Aplicacoes Autonomas + Sistemas Simples = Futuro Feliz?

Fernanda G. Oliveira, Vinod E. F. Rebello

Instituto de Computacao – Universidade Federal Fluminense (UFF)Niteroi, RJ – Brasil

{fgoliveira,vinod}@ic.uff.br

Abstract. The trend in computer architecture is to provide more single servercompute power through multiple multicore processors. In order to maximizeutilization, administrators consolidate multiple diverse applications on fewerservers. One adverse impact is that the corresponding software stack is beco-ming increasingly varied and complex. While virtualization appears to addresscompatibility issues and foster consolidation by isolating disparate applicationsin separate VMs, this isolation only further increases the resource managementoverhead and makes efficient utilization harder. This paper advocates the deve-lopment of smart autonomic applications that execute in a social community asmodel to manage large scale distributed computing environments.

Resumo. A tendencia em arquitetura de computadores e prover mais podercomputacional atraves de multiplos processadores multicore. Para maximizara utilizacao, administradores consolidam multiplas e distintas aplicacoes empoucos servidores. Um impacto negativo e o fato da pilha de software estar setornando cada vez mais variada e complexa. Enquanto a virtualizacao aparecepara lidar com problemas de compatibilidade e promover consolidacao iso-lando diferentes aplicacoes em VMs separadas, isto faz aumentar ainda mais ooverhead de gerenciamento e dificulta obter melhor eficiencia. Este artigo de-fende o desenvolvimento de aplicacoes autonomas inteligentes executando emuma comunidade social como modelo para gerenciar ambientes de larga escala.

1. IntroducaoO tema de computacao autonoma [Huebscher e McCann 2008] vem recebendo umaatencao maior como uma estrategia de gerencia. Os ambientes computacionais parale-los atuais estao crescendo em termos de recursos e em escala mundial gracas a Internet,na forma de grades e nuvens computacionais, e o uso da autonomia aparenta ser umasolucao para obter-se uma utilizacao eficiente. Enquanto uma grande quantidade de com-putadores torna-se bem mais disponıvel, em contrapartida surgem diversos problemasrelacionados ao alto grau de complexidade para gerenciar os inumeros e diferentes tiposde recursos. Heterogeneidade, compartilhamento, seguranca e suscetibilidade a falhas saoalgumas das dificuldades enfrentadas, porem que podem ser atacadas pelas propriedadesself-*s da computacao autonoma.

Alem da inumera quantidade de recursos, a grande variedade de caracterısticas deaplicacoes gera dificuldades no projeto de sistemas de gerenciamento genericos. Mesmooferecendo parcial autonomia, tais sistemas nao provem bom desempenho a todos ostipos de aplicacoes (geralmente so poucos tipos delas). Sem entender suas necessidades e

I Workshop on Autonomic Distributed Systems 3

comportamento, seria impossıvel atingir uma execucao eficiente. O objetivo deste artigo ediscutir um modo de promover autonomia descentralizada e por aplicacao, diferentementedas solucoes tradicionais que buscam uma gerencia centralizada. Na Secao 2 e feita umacomparacao qualitativa com o tipo mais comum de gerenciamento. A Secao 3 descreveuma solucao para aplicacoes autonomas e alguns resultados. A Secao 4 conduz umavisao futura baseada no conceito de uma Sociedade Autonoma onde aplicacoes convivemcompartilhando um ambiente computacional.

2. Gerenciador de Recursos vs. Gerenciador de AplicacoesCom o advento da computacao em grade e em nuvem, por um lado, uma grande quan-tidade de recursos computacionais fica disponıvel para desenvolvedores de aplicacoesque requerem alta escala de processamento e memoria, como e o caso das aplicacoes ci-entıficas (E-Science). Por outro lado, prover uma forma de gerenciar todo este potencialcomputacional de forma eficiente e um desafio para a pesquisa na area.

Um dos grandes desafios para tornar o gerenciamento de ambientes distribuıdoseficiente e tratar o modo como aplicacoes e suas tarefas sao gerenciadas entre os recur-sos do sistema. Dentre os middlewares (camada de software existente entre a aplicacaoe a infraestrutura) mais estudados e desenvolvidos, no contexto de grades computaci-onais, estao aqueles classificados como Sistemas Gerenciadores de Recursos (RMSs -sigla em ingles) [Krauter et al. 2002]. Geralmente desenvolvidos com um gerenciadorcentral (broker), o objetivo de um RMS e maximizar a utilizacao dos recursos de formaparcialmente autonoma, independentemente dos requisitos e caracterısticas internas dasaplicacoes. Os servicos necessarios para o gerenciamento e monitoramento dos recur-sos devem ser instalados previamente em cada computador, o que pode dificultar suadistribuicao pelos ambientes distribuıdos de larga escala.

Assim como a gerencia de sistemas distribuıdos, aplicacoes em si tambem vemtornando-se complexas e diversas em carater. Somando estes dois fatos, RMSs podemnao ser boas alternativas devido ao seu tipo de gerenciamento generico, focado apenas nosistema como um todo. Contrariamente, um Sistema Gerenciador de Aplicacoes (AMS)esta associado a cada instancia da aplicacao, esperando-se obter um maior desempenhodevido a uma gerencia descentralizada onde as decisoes sao tomadas de forma autonoma,baseadas nas caracterısticas proprias da aplicacao e no estado previsto do ambiente. Alemdisso, como geralmente tais sistemas estao ligados a aplicacao, as funcionalidades ne-cessarias vem embutidas nela, facilitando sua portabilidade.

3. Sistema Gerenciador de Aplicacoes EasyGridEste artigo faz referencia ao uso do Sistema Gerenciador de Aplicacoes EasyGridou EasyGrid AMS [Boeres e Rebello 2003], um estudo pratico no desenvolvimento deaplicacoes autonomas. Este middleware oferece um framework de desenvolvimento deaplicacoes autonomas para a transformacao automatica e transparente de programas pa-ralelos - em particular aplicacoes de HPC que pouco aceitam tecnicas que atrasam aexecucao - escritos em MPI (para ambientes homogeneos tradicionais) em programascapazes de tirar proveito mais eficientemente de ambientes distribuıdos atuais e futuros.

O EasyGrid AMS fornece a aplicacao um conjunto de funcionalidades self-* paramanter sua execucao eficiente em sistemas distribuıdos e dinamicos. Atraves dele, a

4 Anais

aplicacao e capaz de tornar-se ciente do sistema - system-aware - e de reagir as suasmudancas temporais; e capaz de detectar e recuperar-se de falhas [Silva e Rebello 2007];e disponibiliza de um escalonamento dinamico eficiente [Nascimento et al. 2008]. Alemdisso, em termos de desenvolvimento, o EasyGrid AMS fornece uma base para aconstrucao da aplicacao - atraves do modelo de execucao 1PTask (um processo por ta-refa) [Sena et al. 2007] - que possibilita a aquisicao de melhor desempenho e flexibilidadeno gerenciamento das tarefas especialmente em sistemas dinamicos.

Sob o modelo 1PTask, aplicacoes conseguem obter otimo desempenho devidoa auto-otimizacao e a auto-recuperacao. Porem, para a auto-configuracao, deve-seanalisar especificamente suas caracterısticas que, muitas vezes, e essencial para umaboa paralelizacao. Portanto, dado que tem-se um middleware com funcionalidadespara o desenvolvimento de aplicacoes autonomas, existe a dificuldade de saber comofazer uma boa divisao da aplicacao entre os recursos disponıveis. Neste contexto,alguns trabalhos ja foram realizados usando aplicacoes de diversas areas cientıficascomo: astrofısica (N-body) [Ribeiro et al. 2010], bioinformatica (geometria molecu-lar) [Oliveira e Rebello 2010] e escalonamento de jogos esportivos [Araujo 2008].

3.1. Alguns ResultadosEm [Sena et al. 2007], um teste compara versoes da aplicacao Thermions (da area defısica) rodando com e sem o EasyGrid AMS em varios cenarios envolvendo clusters egrids. Tal experimento mostra que a aplicacao executando junto ao middleware EasyGridapresenta overhead menor que 2% comparado as versoes sem o middleware em um am-biente de cluster. Quando o ambiente muda para grid, o desempenho da aplicacao como EasyGrid melhora significantemente em comparacao com a implementacao tradicional.O custo da deteccao e tratamento de falhas tambem acrescenta um baixo overhead, emcerca de ate 2% [Silva e Rebello 2007].

Os resultados obtidos em [Araujo 2008] revelam nao so a melhora no tempo deexecucao mas tambem na qualidade da solucao da aplicacao, ja que os problemas tra-tados por ela sao heurısticas. Resultados obtidos em [Oliveira e Rebello 2010] apre-sentam speed-ups (comparado a versoes tradicionais) proximos ao linear, concluindoque aplicacoes com tarefas de diferentes granularidade conseguem obter bons resultadosmesmo em ambientes dinamicos e tem potencial para usufruir de uma grande quanti-dade de recursos. Mais focado em ambientes intrinsecamente dinamicos e heterogeneos,aplicacoes maleaveis autonomas sao trabalhadas em [Ribeiro et al. 2010] onde elas mu-dam sua propria configuracao. Os resultados mostram desempenho superior comparadoas abordagens tradicionais do problema e, de novo, um baixo overhead.

4. Sociedade AutonomaEnquanto o controle descentralizado e mais escalavel comparado as solucoes RMSs, acoordenacao de acoes para obter uma melhor utilizacao e significantemente mais difıcilsem uma visao global dos recursos. Um problema enfrentado pelo uso de AMS e o fato dadisputa pelos recursos entre duas ou mais aplicacoes autonomas poderem atrapalhar umaa outra. Por exemplo, se a funcionalidade de auto-otimizacao emprega heurısticas gulosascujo objetivo e executar a aplicacao no menor tempo possıvel, as acoes tomadas podemprejudicar outras aplicacoes. Usando uma regra comportamental simples e adotando me-tas de tempo de execucao para aplicacoes [Rodrigues 2009], uma solucao inicial permite

I Workshop on Autonomic Distributed Systems 5

que multiplas aplicacoes executem cordialmente no ambiente distribuıdo. As aplicacoessao cientes de que fazem parte de uma sociedade e comportam-se altruistamente quandoha folga em suas metas, de modo que todas saiam ganhando em desempenho.

5. ConclusaoPara reduzir o custo e aumentar a abrangencia, o EasyGrid AMS e projetado por classes deaplicacoes para fornece-las autonomia. Tendo em vista os resultados ja obtidos em traba-lhos desenvolvidos com codigos cientıficos e alguns de producao, acredita-se fortementeque a autonomia focada na aplicacao traz grandes benefıcios nas execucoes em ambientesdistribuıdos. Estes resultados abrem uma nova linha de pesquisa de gerencia que envolveanalise e programacao do comportamento para ambientes de multiplas aplicacoes system-aware. Elas terao que interagir como em uma sociedade, onde compartilham recursosdiferentes, cada aplicacao com sua propria meta. Alem disso, uma solucao hıbrida entreAMS e RMS nao esta descartada, onde uma troca de informacao entre ambos pode ajudara achar uma configuracao otima das aplicacoes e do ambiente de execucao.

ReferenciasAraujo, A. P. F. (2008). Paralelizacao Autonomica de Metaheurısticas em Ambientes de

Grid. PhD thesis, Departamento de Informatica, Pontifıcia Universidade Catolica doRio de Janeiro, Rio de Janeiro, RJ, Brasil.

Boeres, C. e Rebello, V. E. F. (2003). EasyGrid: Towards a framework for the automaticgrid enabling of MPI applications. In Proceedings of the First International Workshopon Middleware for Grid Computing, pages 256–260, Rio de Janeiro, Brazil.

Huebscher, M. C. e McCann, J. A. (2008). A survey of autonomic computing-degrees,models, and applications. ACM Comput. Surv., 40:7:1–7:28.

Krauter, K., Buyya, R., e Maheswaran, M. (2002). A taxonomy and survey of grid re-source management systems. Software Practice and Experience, 32:135–164.

Nascimento, A. P., Sena, A. C., Silva, J. A., Vianna, D. Q. C., Boeres, C., e Rebello,V. E. F. (2008). Autonomic application management for large scale MPI programs.International Journal of High Performance Computing and Networking, 5(4):227–240.

Oliveira, F. G. e Rebello, V. E. F. (2010). Algoritmos branch-and-prune autonomos.In SBRC ’10, XXVIII Simposio Brasileiro de Rede de Computadores e Sistemas Dis-tribuıdos, Gramado, RS.

Ribeiro, F., Sena, A., Nascimento, A., Boeres, C., e Rebello, V. E. F. (2010). A self-configuring N-body application. In SBAC-PAD’10: Proceedings of the InternationalWorkshop on Challenges in e-Science (CIS’10), Petropolis, Rio de Janeiro, Brazil.

Rodrigues, H. (2009). Grid S.A.: Uma sociedade autonoma. Master’s thesis, Instituto deComputacao, Universidade Federal Fluminense.

Sena, A., Nascimento, A., Silva, J., Vianna, D., Boeres, C., e Rebello, V. E. F. (2007).On the advantages of an alternative MPI execution model for grids. In CCGRID ’07,pages 575–582, Rio de Janeiro, Brazil. IEEE Computer Society.

Silva, J. e Rebello, V. E. F. (2007). Low Cost Self-healing in MPI Applications. In RecentAdvances in Parallel Virtual Machine and Message Passing Interface, 14th EuropeanPVM/MPI User’s Group Meeting, pages 144–152. Springer.

6 Anais

Computacao em Nuvem Autonoma: Oportunidades e DesafiosFlavio R. C. Sousa 1, Leonardo O. Moreira 1, Javam C. Machado 1

1 Mestrado e Doutorado em Ciencia da Computacao (MDCC)Universidade Federal do Ceara (UFC) – Fortaleza, CE – Brasil

{sousa,leoomoreira,javam}@ufc.br

Abstract. Cloud computing is a recent trend of technology aimed at providingon-demand services with payment based on usage. However, this computingmodel requires major technological changes, especially in the autonomous ma-nagement because the cloud environment presents a great number and variety ofresources. Service providers, in turn, need to address issues of scalability, avai-lability, performance, and cost. This paper aims to discuss cloud computing andautonomic management, highlighting opportunities and research challenges inthis context.

Resumo. Computacao em nuvem e uma tendencia recente de tecnologia cujoobjetivo e proporcionar servicos sob demanda com pagamento baseado nouso. Entretanto, este modelo de computacao requer grandes mudancas tec-nologicas, principalmente no gerenciamento autonomo, pois o ambiente em nu-vem apresenta uma grande quantidade e variedade de recursos. Os provedoresde servico, por sua vez, necessitam tratar aspectos de escalabilidade, disponi-bilidade, desempenho e custo. Este artigo tem como objetivo discutir sobre acomputacao em nuvem e o gerenciamento autonomo, destacando oportunidadese desafios de pesquisa neste contexto.

1. IntroducaoComputacao em nuvem fornece infraestrutura, plataforma e software como um servicosob demanda com pagamento baseado no uso [Buyya et al. 2009]. Com isso, as em-presas e os desenvolvedores nao precisam realizar grandes investimentos em hardware emanutencao para implementar servicos, permitindo mais foco em inovacao e na melhoriados negocios das empresas [Sousa et al. 2010]. Por outro lado, os ambientes de nuvemsao inerentemente grandes, complexos, heterogeneos e altamente dinamicos e os provedo-res devem tratar questoes de qualidade do servico, disponibilidade e eficiencia energetica.Os nıveis de complexidade na nuvem excedem a capacidade humana, forcando a reti-rada das pessoas do processo de gerencia e aumentando a autonomia dos sistemas. Alemdisso, solucoes para o gerenciamento neste contexto devem se adaptar as mudancas ecomportamentos da nuvem de acordo com instrucoes especificadas em alto nıvel pelosadministradores destas solucoes.

A computacao autonoma e inspirada em sistemas biologicos para lidar com de-safios de complexidade, dinamismo e heterogeneidade [Kephart and Chess 2003], ca-racterısticas presentes nos ambientes de computacao em nuvem e, assim, fornece umaabordagem promissora neste contexto. Embora a computacao em nuvem apresente cer-tas caracterısticas autonomas como o provisionamento automatico de recursos, seu ob-jetivo e reduzir o custo dos recursos ao inves de reduzir a complexidade do sistema

I Workshop on Autonomic Distributed Systems 7

[Zhang et al. 2010]. Na proxima secao apresentamos oportunidades e desafios de pes-quisa no gerenciamento autonomo do ambiente de computacao em nuvem e, na ultimasecao, as conclusoes deste trabalho.

2. Oportunidades e DesafiosA computacao em nuvem e um paradigma cada vez mais popular e tem atraıdo esforcosda industria e da academia. Associado a isto, a computacao autonoma permite melhoraros esforcos ja aplicados neste contexto [CometCloud 2011]. A seguir destacamos algunsdesafios e oportunidades de pesquisa em computacao em nuvem autonoma.

2.1. Desenvolvimento de Sistemas Autonomos para Nuvem

A nuvem e um sistema autonomo onde hardware e software podem ser automaticamentereconfigurados, orquestrados e estas modificacoes sao apresentadas de forma transparentepara os usuarios. Neste contexto, diferentes modelos evoluıram rapidamente para apro-veitar as tecnologias de software, plataformas de programacao, armazenamento de dadose infraestrutura de hardware como servicos. Enquanto estes modelos se referem ao nucleodos servicos de computacao em nuvem, suas inter-relacoes tem sido ambıguas e a viabi-lidade de sua interoperabilidade e questionavel. Alem disso, cada servico de computacaoem nuvem possui interfaces e protocolos diferentes [Youseff et al. 2008].

O gerenciamento do ambiente de nuvem possui algumas caracterısticas que di-ferem de outros ambientes, dentre as quais podemos destacar a intervencao humana li-mitada, carga de trabalho altamente variavel e uma grande quantidade e variedade derecursos compartilhados. De acordo com as requisicoes dos usuarios, estes recursos saoexpandidos ou reduzidos para manter a qualidade do servico. Associado a isso, os prove-dores de servicos em nuvem devem tratar aspectos de pagamento baseado no uso enquantoutilizam recursos compartilhados para varios usuarios. Com isso, tem-se um ambientedinamico, elastico e distribuıdo, o que dificulta o desenvolvimento de solucoes para ogerenciamento destes ambientes.

Um sistema autonomo para nuvem deve monitorar o comportamento e desempe-nho do ambiente, tratar questoes de tolerancia a falhas, elasticidade e balanceamento dacarga de trabalho, modelar e prever o comportamento para as cargas de trabalho e realizaracoes para lidar com as variacoes destas cargas. Tecnicas de aprendizagem de maquinapodem ser utilizadas para classificar a carga de trabalho e prever o custo de operacoes, me-lhorando o provisionamento [Agrawal et al. 2011]. Questoes de seguranca, privacidade econfidencialidade tambem devem ser abordadas, visto que os elementos autonomos cola-boram para realizar suas atividades. Por fim, e importante definir uma forma de integrarestes novos sistemas autonomos aos sistemas existentes.

2.2. Polıticas para Computacao em Nuvem

As polıticas devem representar as propriedades dos sistemas autonomos e o comporta-mento, objetivos, adaptacao e interacao entre os elementos autonomos, assim com a in-fluencia externa e a demanda do sistema. Assim, as polıticas devem ser simples, permi-tindo a intervencao humana de forma precisa e evitando a definicao de objetivos inconsis-tentes. Para tanto, pode-se desenvolver modelos matematicos e algoritmos que, de acordocom objetivos de alto nıvel, auxiliem a garantir os objetivos [Paton et al. 2009]. Como a

8 Anais

quantidade de recursos gerenciados pelos agentes na nuvem e muito grande, um desafioe garantir que o comportamento resultante dos objetivos individuais de cada agente iraconduzir a realizacao de um objetivo comum.

No ambiente de nuvem, as polıticas, regras ou requisitos sao orientados aonegocio. Contudo, mas nao existe uma padronizacao destas regras. O grau de automacao,abstracao para o usuario e customizacao das polıticas e regras que regem um servico podevariar bastante. Alguns sistemas oferecerem aos usuarios a possibilidade de construcaode condicoes simples com base em certas metricas, por exemplo, CPU, memoria, en-quanto outros utilizam metricas no nıvel do servico, por exemplo, relacao custo/benefıcioe permitem estrategias mais complexas [Vaquero et al. 2011]. Dessa forma, um desafio econceber polıticas de alto nıvel que capturem tanto aspectos tecnicos como os objetivosdo negocio. As abordagens para o desenvolvimento de polıticas baseadas em ontologiaspodem ser uma alternativa [Strassner et al. 2009]. Ontologias podem ser utilizadas para aorganizacao do domınio de conhecimento de computacao em nuvem, seus componentese suas relacoes, ajudando a comunidade na melhor compreensao das tecnologias.

2.3. Monitoramento de Ambientes em NuvemO monitoramento e essencial para o ambiente de computacao em nuvem, visto que esteambiente esta se alterando constantemente de forma a atingir os objetivos. Para garan-tir a qualidade do servico, utiliza-se a abordagem baseada em acordo de nıvel de servico(SLA), que contem informacoes sobre os nıveis de disponibilidade, desempenho e penali-dades em caso de violacao destes nıveis. No ambiente em nuvem, o objetivo e minimizara quantidade de recursos necessarios para garantir a qualidade do servico, o que reduz oscustos. Dessa forma, uma questao e como gerenciar de forma automatica os recursos dis-ponıveis e a carga de trabalho do sistema para garantir a qualidade do servico e melhorara utilizacao destes recursos. Tecnicas de monitoramento adaptativas e dinamicas deveraoser desenvolvidas para tratar esta questao.

De acordo com o modelo de servico (IaaS, PaaS ou SaaS) utilizado, o gerencia-mento autonomo e diferente. Por exemplo, um provedor IaaS, em geral, gerencia apenasrecursos da sua infraestrutura, ao passo que, um provedor de PaaS ou SaaS pode precisargerenciar a utilizacao dos recursos em diferentes infraestruturas. Dessa forma, no modelode PaaS e, principalmente, no modelo de SaaS deve-se ter solucoes de monitoramentopara melhorar a utilizacao dos recursos e verificar a garantia dos servicos considerandodiferentes infraestruturas.

Outro ponto importante e obter informacoes sobre cada elemento, ja que nem to-dos os dispositivos possuem uma interface padronizada. [Lim et al. 2009] discutem sobrea utilizacao de sensores e atuadores em ambientes de computacao em nuvem e apresen-tam algumas questoes de pesquisa, tais como obter informacoes sobre os componentesdo ambiente. Para monitorar a nuvem, [Lee et al. 2010] propoem uma abordagem parao monitoramento deste ambiente baseada em redes de sensores. Tecnicas como MapRe-duce podem ser utilizadas para o processamento do grande volume de dados coletadospelos sensores, bem como para construir uma base de conhecimento.

3. ConclusaoEste artigo apresentou problemas e oportunidades para o gerenciamento autonomo deambientes de computacao em nuvem. O desenvolvimento de sistemas autonomos e as

I Workshop on Autonomic Distributed Systems 9

caracterısticas do monitoramento foram discutidos e alguns desafios foram detalhados.Este artigo nao tem a pretensao de descrever exaustivamente as tecnicas existente para aconstrucao de ambientes de nuvens com autonomia de gerenciamento. Outras tecnicassao igualmente viaveis. O grupo de Cloud Computing da UFC participa intensamente naespecificacao e na construcao de um sistema autonomo para o ambiente de nuvem.

ReferenciasAgrawal, D., Abbadi, A. E., Das, S., and Elmore, A. J. (2011). Database scalability, elasticity, and

autonomy in the cloud - (extended abstract). In Database Systems for Advanced Applications -16th International Conference, DASFAA 2011, pages 2–15.

Buyya, R., Yeo, C. S., Venugopal, S., Broberg, J., and Brandic, I. (2009). Cloud computing andemerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility.Future Gener. Comput. Syst., 25(6):599–616.

CometCloud (2011). CometCloud: An Autonomic Cloud Engine. www.cometcloud.org.

Kephart, J. O. and Chess, D. M. (2003). The vision of autonomic computing. Computer, 36(1):41–50.

Lee, K., Murray, D., Hughes, D., and Joosen, W. (2010). Extending sensor networks into thecloud using amazon web services. In Proceedings of the 1st IEEE International Conference onNetworked Embedded Systems for Enterprise Applications, NESEA 2010, pages 1–7. IEEE.

Lim, H. C., Babu, S., Chase, J. S., and Parekh, S. S. (2009). Automated control in cloud compu-ting: challenges and opportunities. In Proceedings of the 1st workshop on Automated controlfor datacenters and clouds, ACDC ’09, pages 13–18, New York, NY, USA. ACM.

Paton, N. W., Aragao, M. A. T., Lee, K., Fernandes, A. A. A., and Sakellariou, R. (2009). Optimi-zing utility in cloud computing through autonomic workload execution. IEEE Data Eng. Bull.,32(1):51–58.

Sousa, F. R. C., Moreira, L. O., Macedo, J. A. F., and Machado, J. C. (2010). Gerenciamento deDados em Nuvem: Conceitos, Sistemas e Desafios, pages 101–130. In: PEREIRA, A. C. M.;PAPPA, G. L.; WINCKLER, M.; GOMES, R. L. (Org.). Topicos em Sistemas Colaborativos,Interativos, Multimıdia, Web e Bancos de Dados, SWIB 2010, 1. ed. SBC, Belo Horizonte.

Strassner, J., de Souza, J. N., van der Meer, S., Davy, S., Barrett, K., Raymer, D., and Samudrala, S.(2009). The design of a new policy model to support ontology-driven reasoning for autonomicnetworking. J. Network Syst. Manage., 17(1-2):5–32.

Vaquero, L. M., Rodero-Merino, L., and Buyya, R. (2011). Dynamically scaling applications inthe cloud. SIGCOMM Comput. Commun. Rev., 41:45–52.

Youseff, L., Butrico, M., and Da Silva, D. (2008). Toward a unified ontology of cloud computing.In Grid Computing Environments Workshop, 2008. GCE ’08, pages 1–10.

Zhang, Q., Cheng, L., and Boutaba, R. (2010). Cloud computing: state-of-the-art and researchchallenges. Journal of Internet Services and Applications, 1:7–18.

10 Anais

Sintonia Automática de Banco de Dados em Nuvem

Mônica Reginada Silva1, Javam de Castro Machado1, José Maria Monteiro1,José Antônio F. de Macêdo1

1Departamento de Computação – Universidade Federal do Ceará (UFC)Campus do Pici - Bloco 910 – 60.455-760 – Fortaleza – CE – Brasil

{monicareginadasilva,javam,monteiro,jose.macedo}@lia.ufc.br

Abstract. This paper presents an approach for autonomic tuning in cloud data-base. In this work, we classify the tuning actions in three levels: DBMS, virtualmachine and cloud. The designed mechanism focuses on DBMS tuning level,seeking to improve system performance through changes in DBMS parametersand settings. The proposed ideas extend previous work adding the use of SLAsand a generic cost model, and support for elasticity.

Resumo. Este artigo apresenta uma abordagem para a sintonia automática desistemas de bancos de dados em ambientes de computação em nuvem. Nestetrabalho, classificamos as ações de sintonia em três níveis: SGBD, máquinavirtual e nuvem. O mecanismo concebido concentra-se nos ajustes a nível deSGBD, buscando melhorar o desempenho do sistema por meio de alterações nosparâmetros e configurações do próprio SGBD. As idéias propostas estendem ostrabalhos anteriores adicionando a utilização de SLAs e de um modelo de custosgenérico, além do suporte à elasticidade rápida.

1. Introdução

A Computação em nuvem tem por objetivo proporcionar serviços de Tecnologia da Infor-mação (TI) sob demanda com pagamento baseado no uso. A nuvem computacional é ummodelo de computação em que dados, arquivos e aplicações residem em servidores físi-cos ou virtuais, acessíveis por meio de uma rede em qualquer dispositivo compatível (fixoou móvel), e que podem ser acessados a qualquer hora, de qualquer lugar, sem a neces-sidade de instalação ou configuração de programas específicos. Assim, a infra-estruturada computação em nuvem pode ser vista como umpool de recursos computacionais (vir-tualmente) infinito (e elástico) oferecido no modoself-service, por um terceiro via ummodelo “pague o quanto usa” [Sousa 2010].

Neste trabalho, consideramos que um banco de dados em nuvem consiste de umsistema de banco de dados (SBD) executado em máquinas virtuais (Virtual Machines-VMs) pré-configuradas e disponibilizadas por um provedor de infra-estrutura como umserviço (IaaS -Infrastructure as a Service), onde os dados estão distribuídos, particiona-dos e/ou replicados, de forma transparente, com a finalidade de melhorar o desempenho,a escalabilidade e a disponibilidade dos sistemas. Elasticidade rápida de recursos, auto-nomia e acordo de níveis de serviço também são aspectos relevantes no contexto de umSBD em nuvem [Sousa 2010].

I Workshop on Autonomic Distributed Systems 11

Provedores de IaaS devem oferecer seus serviços de dados respeitando osacordosde níveis de serviço (SLA -Service Level Agreement) negociados com o usuário. Assim,o SLA fornece informações sobre o nível de qualidade esperado para o serviço de dados,o qual pode ser especificado em termos de: disponibilidade, tempo de resposta, vazão,dentre outros. Além disso, o SLA especifica também penalidades em caso de violaçãodo nível de qualidade contratado [Sousa 2010]. Desta forma, o provedor necessita moni-torar o desempenho do SBD disponibilizados na nuvem e, caso o seu desempenho estejainferior ao valor contratado, ele deve ajustar os parâmetros e a configuração do SBD (Da-tabase Tuning) com a finalidade de melhorar o desempenho do sistema, assegurando oatendimento dos SLAs, mesmo na ocorrência de um aumento inesperado da demanda.

Contudo, esta não é uma tarefa fácil (mesmo para DBAs experientes) devido àquantidade de SBDs hospedados (centenas ou milhares de SBDs virtualizados), ao vo-lume dos dados armazenados e à grande quantidade de ajustes possíveis (índices, tamanhodosbuffersde memória, etc). Além disso, em geral, não se sabe a localização física dosdados ou como os dados foram particionados ou replicados. Logo, espera-se que estastarefas sejam realizadas automaticamente e sem intervenção humana [Soror et al. 2007].Neste contexto, propomos uma abordagem para a sintonia automática de SBDs em am-bientes de computação em nuvem, a qual busca melhorar o desempenho do sistema pormeio de alterações nos parâmetros e configurações do próprio SBD. O mecanismo pro-posto estende os trabalhos anteriores adicionando a utilização de SLAs e de um modelode custos genérico, além do suporte à elasticidade rápida.

2. A Abordagem Proposta

A sintonia automática de bancos de dados (self-tuning database) tem sido bastante inves-tigada nos últimos anos. Porém, o ambiente de computação em nuvem introduz algunsdesafios particulares, os quais fazem com que a teoria existente necessite ser adaptadapara a realidade dos bancos de dados em nuvem. A seguir, discutimos algumas dessesdesafios:

• Modelo de Custo Genérico:A forma de calcular o custo de execução de umadeterminada consulta ou carga de trabalho deve basear-se no custo econômico(medido em Dólar) referente aos recursos utilizados para sua execução e não maisno custo computacional (número de I/Os, etc). Este fato decorre da utilização dosconceitos de serviço medido e “pagamento pelo uso”.

• Mudança do Paradigma de Otimização :Antes, o objetivo da sintonia era mi-nimizar o tempo de resposta para uma carga de trabalho dado um conjunto fixode recursos (memória, disco, etc). Agora, o objetivo da tarefa de sintonia passa aser minimizar a utilização dos recursos dado um tempo de resposta máximo fixoe previamente acordado (SLA).

Para ilustrar essa questão, suponha a existência de uma consultaqk cujo tempode resposta acordado no SLA seja igual a30s (slaqk

= 30s). Considere agoraque a consultaqk foi executada com tempo de resposta igual a45s (rtqk

= 45s).Analisando a consultaqk observou-se que duas ações de sintonia eram possíveis:(i) a criação de um índiceij e (ii) a criação de uma visão materializadamvt. As-suma que criando-se essas duas estruturas o tempo de resposta deqk passasse para15s (rt

′

qk= 15s). Assuma também que criando-se apenas o índiceij o tempo de

12 Anais

resposta deqk fosse iguala 30s (rt′′

qk= 30s). Note que, na abordagem tradicio-

nal de sintonia de bancos de dados as duas estruturas (ij e mvt) seriam criadas.Contudo, para a sintonia de um SBD em nuvem somente o índiceij deveria sercriado, uma vez que isso já seria suficiente para atender o SLA (minimizando osrecursos utilizados e maximizando o lucro do provedor) e que a criação demvt

adicionaria um gasto de recursos (disco) desnecessário. Além disso, é importanteque a abordagem proposta forneça suporte tanto para que o SLA seja definido anível das consultas quanto a nível da carga de trabalho como um todo.

• Elasticidade: Na computação em nuvem recursos podem ser adquiridos de formarápida e elástica, em alguns casos automaticamente, caso haja a necessidade deescalar com o aumento da demanda, e liberados, na retração dessa demanda. Paraos usuários, os recursos disponíveis para uso parecem ser ilimitados e podem seradquiridos em qualquer quantidade e a qualquer momento [Sousa 2010]. Assim,uma abordagem eficiente para a sintonia de BDs em nuvem deve agora consi-derar e suportar a possibilidade da ocorrência de uma mudança na configuraçãoda infra-estrutura utilizada pelo SBD durante a realização de uma ação de sinto-nia. Por exemplo, suponha que decidiu-se particionar os dados armazenados peloSBD, com a finalidade de melhorar o seu desempenho. Contudo, durante a rea-lização desta tarefa novas máquinas virtuais contendo instâncias do SBD foramadicionadas, ou que uma máquina virtual contendo uma instância do SBD foi mo-vida para uma outra máquina física. A solução de sintonia automática do SBD emnuvem deve suportar esse tipo de ocorrências simultâneas.

Neste trabalho, classificamos as ações de sintonia que podem ser aplicadas à umsistema de banco de dados em nuvem em três diferentes níveis:

• Nível do SGBD:As ações de sintonia neste nível buscam alterar os parâmetros e aconfiguração do SGBD com o objetivo de melhorar o seu desempenho. Algumasações que podem ser realizadas neste nível são: a criação de índices, visões ma-terializadas, particionamento de tabelas, alteração do tamanho da área dobufferde memória, alteração no nível de multi-programação (MultiProgramming Level -MPL), dentre outras.

• Nível de Máquina Virtual: A virtualização permite que máquinas virtuais com-partilhem umpoolde recursos físicos (memória, disco, CPU) de uma mesma má-quina física. Por meio do monitor de máquinas virtuais (VMM -Virtual MachineMonitor) é possível gerenciar as VMs e, dinamicamente, alocar ou desalocar re-cursos dehardware. Este cenário torna possível um novo conjunto de ações desintonia, as quais envolvem a adição de recursos físicos (ainda disponíveis) com afinalidade de assegurar o cumprimento dos SLAs.

• Nível da Nuvem:Apesar da elasticidade dos recursos dehardware, uma máquinafísica possui recursos limitados, os quais podem não ser suficientes para um bomdesempenho de todas as VMs. Neste caso, a infra-estrutura da computação emnuvem pode ser ajustada. As ações de sintonia possíveis neste nível incluem aalocação de novas máquinas físicas, instanciação de novas VMs ou migração deVMs parahostscom uma maior quantidade de recursos disponíveis.

Vale destacar que as ações de sintonia presentes na abordagem proposta podemser classificadas como pertencentes ao nível do SGBD (Figura 1).

I Workshop on Autonomic Distributed Systems 13

Figura 1. Níveis de Sintonia para BDs em Nuvem

3. Trabalhos RelacionadosExistem alguns trabalhos que já exploraram a auto-sintonia em nuvens computacionais. OStarfish [Herodotou et al. 2011], por exemplo, é um sistema auto-sintonizável projetadosobre o Hadoop para análise sobre grandes conjuntos de dados.[Xu et al. 2008] busca ogerenciamento autonômico de recursos em um centro de dados virtualizados, baseando-se tanto na visão local do contêiner virtual quanto na visão global de um pool de recur-sos. Contudo, não leva em consideração o custo de migração de máquinas virtuais emcaso de haver poucos recursos disponíveis e também não procura atender aos SLAs. Já[Nguyen Van et al. 2009] propõe um gerenciador autonômico de recursos virtualizados,o qual leva em consideração os SLAs, além da capacidade de recursos locais para instan-ciação e alocação de novas VMs e migração de VMs já existentes.4. ConclusõesA abordagem proposta para a sintonia automática de SBDs em nuvem busca melhorar odesempenho do sistema por meio de alterações nos parâmetros e configurações do próprioSBD. O mecanismo proposto estende os trabalhos anteriores adicionando a utilização deSLAs e de um modelo de custos genérico, além do suporte à elasticidade rápida.ReferênciasHerodotou, H., Lim, H., Luo, G., Borisov, N., Dong, L., Cetin, F. B., and Babu, S. (2011). Star-

fish: A self-tuning system for big data analytics. InCIDR 2011, Fifth Biennial Conference onInnovative Data Systems Research, Asilomar, CA, USA, Online Proceedings.

Nguyen Van, H., Dang Tran, F., and Menaud, J.-M. (2009). Autonomic virtual resource manage-ment for service hosting platforms. InProceedings of the 2009 ICSE Workshop on SoftwareEngineering Challenges of Cloud Computing, CLOUD ’09, pages 1–8, Washington, DC, USA.IEEE Computer Society.

Soror, A. A., Aboulnaga, A., and Salem, K. (2007). Database virtualization: A new frontier fordatabase tuning and physical design. Inin Proceedings of ICDE Workshops (SMDB 2007, page388.

Sousa, F. R. d. C. (2010). Gerenciamento de dados em nuvem. Te-chnical report, Departamento de Computação, UFC. Disponível emwww.es.ufc.br/flavio/files/Gerenciamento_Dados_Nuvem.pdf.

Xu, J., Zhao, M., Fortes, J., Carpenter, R., and Yousif, M. (2008). Autonomic resource mana-gement in virtualized data centers using fuzzy logic-based approaches.Cluster Computing,11:213–227. 10.1007/s10586-008-0060-0.

14 Anais

I Workshop on Autonomic Distributed Systems

♦ Sessão Técnica 2

From static to dynamic protocols: adapting timeouts forimproved performance∗

A. Casimiro1, M. Dixit1

1University of Lisbon, Faculty of Sciences (FCUL)

{casim,mdixit}@di.fc.ul.pt

Abstract. When network delays are unstable and susceptible to network con-tention, such as in wireless environments, it becomes important to dynamicallyadapt timeout values in order to address performance concerns. In this paperwe discuss the problem of transforming static timeout-based protocols into pro-tocols that dynamically select timeout values for improved performance. Wepropose a methodological approach and we present an example that illustrateshow the methodology applies in practice.

1. IntroductionIn asynchronous distributed systems, a fundamental problem is to ensure the progressof a protocol despite the possible occurrence of process crashes or network failures. Atypical solution is to use timeouts, which prevent waiting indefinitely for messages thatmay never arrive. When the timeout expires, the protocol assumes that a failure occurredand decides accordingly. However, since the decision might be wrong (if the system is justslow), special care must be taken to secure safety properties. In consequence, the typicalconcern in the definition of protocols for asynchronous systems is to ensure safety, whilethe problem of selecting a good timeout value is often ignored. In this paper we arguethat in asynchronous systems it is also important to carefully select timeouts, namely inwireless settings, to improve performance. We propose an approach to transform staticprotocols into dynamic ones, in which timeouts are adaptive, and we provide a shortexample to illustrate how the approach may be applied to an existing protocol.

2. MotivationWhy is the problem of timeout selection often ignored? In general, this happens becauseof the following main reasons. First, sometimes timing assumptions are hidden fromthe protocol (e.g. encapsulated in a failure detector), making it impossible to directlydeal with the issue of timeout selection. Second, independently of the specific timeoutvalues, safety is preserved and only performance may become an issue. Finally, usinglarge timeouts is often not a problem in the normal case, and just affects performancewhen faults indeed occur. In this case, the trade-off will be the possible large delay todeal with exceptions, that is, to detect faults. Performance ends up being dependent on:a) how large timeouts must be set, and b) how frequent are still the exceptions.

Therefore, it is fundamental to know about the temporal behavior of the executionenvironment. Local Area Networks (LANs) constitute a very favorable environment from

∗This work was partially supported by the FCT, through project TRONE (CMU-PT/RNQ/0015/2009)and the Multiannual and CMU-Portugal programmes.

I Workshop on Autonomic Distributed Systems 17

a temporal perspective. Network delays are very small (in the order of microseconds),very stable across different LANs, independent of the communicating nodes and they arenot much affected by contention. In general, in LANs it is possible and easy to selectsome small upper bound for communication delays, which will hold with a very highprobability. Therefore, distributed protocols usually perform well in these environments.On the other hand, in large-scale networks (WANs) delays are much higher and theystrongly depend on the specific end points. Moreover, they are not so stable over time,due to route changes and global traffic load fluctuations. Therefore, dynamic timeoutselection and adaptation becomes more important in these environments. The problem iseven more relevant in wireless networks. Delays are also much larger than in LANs and,in addition, they are strongly affected by contention. Depending on the number of nodesthat communicate within a single hop distance, the delay can significantly change. Thisis illustrated in Figure 1, which compares the execution time of a consensus protocol ina LAN and in a wireless network. The results were obtained using a LAN in our lab andthe Emulab testbed [White et al. 2002], for a different number, n, of processes.

1 Local area network

0,2

0,4

0,6

0,8

1

P(f

inis

h r

ou

nd

) n=4

n=7

n=10

n=13

n=16

Local area network

0

0,2

0,4

0,6

0,8

1

[0,100) [100,200) [200,300) [300,400) [400,500) [500,600)

P(f

inis

h r

ou

nd

)

Time to finish round (ns)

n=4

n=7

n=10

n=13

n=16

Local area network

0

0,2

0,4

0,6

0,8

1

[0,5) [5,10) [10,15) [15,20) [20,25) [25,30) [30,35) [35,40) [40,45) [45,50)

P(f

inis

h r

ou

nd

)

Time to finish round (ms)

n=4

n=7n=10

n=13

n=16

Wireless network

Figure 1. Protocol execution delays in a LAN and in a wireless network.

Given the previous discussion, we argue that the problem of timeout selection,which has been treated as a minor issue in the context of distributed protocols for asyn-chronous systems, should be given particular attention when considering large-scale andwireless networks, for performance and practicality reasons. Furthermore, we believe thatit is possible to transform static protocols, which do not consider adaptive timeouts, intodynamic ones that perform better in environments of varying timeliness. This is what wediscuss next.

3. A methodology for structured timeout adaptationGiven a static timeout-based protocol, the objective is to make it dynamic in the sim-plest possible way. We propose a modular approach, in which there is an independentservice that provides the right timeout, which depends on the requirements specified bythe protocol or application. A mapping layer is needed in order to translate performanceobjectives into requirements that the service can handle. Given that, we consider a com-position involving the timeout provisioning service, the mapping layer and, on top, thetimeout-based protocol or application.

3.1. Timeout provisioning service

The objective of the timeout provisioning service is to provide a timeout to be used by theprotocol, which may be assumed to hold with a given probability, also called coverage.In our previous work we have designed Adaptare [Dixit et al. 2011], which is a proba-bilistic framework for dependable adaptation that may be used as a timeout provisioning

18 Anais

service. Adaptare assumes that observed temporal variables can be described in proba-bilistic terms, that distributions change over time, but that they do not change arbitrarilyfast. This allows to collect enough information for building useful probabilistic charac-terizations. The input to Adaptare are sample observations of the temporal variable (forinstance, continuously measured network delays). Using these samples Adaptare teststheir fit to various probabilistic distributions in order to obtain a probabilistic characteri-zation of the current state. Adaptare is then able to determine a bound (a timeout), whichwill hold with (at least) the specified coverage, provided at its interface.

3.2. Mapping layerIn order to obtain a timeout from Adaptare it is necessary to provide the required coveragefor the timeout. The coverage must be derived from performance requirements, althoughthis might not be trivial. In the simplest case, it will be known that the best performanceis achieved for a certain coverage. For instance, the performance of timeout-based failuredetectors may be specified in terms of the mistake rate, which directly corresponds tothe probability that a timeout expires too early. In this case, no specific mapping layerwould be needed as the mistake rate would serve as the required coverage. In othercases, performance requirements are specified in terms of variables that cannot be directlytranslated into a coverage, like the execution time. In these cases, a mapping layer willbe used to translate requirements into a coverage value, which will be bound to a specificprotocol or application. In fact, the layer will implement a cost/benefit function expressedin terms of 〈coverage,timeout〉 pairs. These pairs are obtained from Adaptare whenevernecessary, that is, when the protocol asks for a new timeout. When this happens, themapping layer will execute a procedure that uses the cost/benefit function to determine ifthere is a new 〈coverage,timeout〉 pair that brings a relative improvement with respect tothe currently considered pair. When the probabilistic characterization of the environmentchanges, it is expected that a new timeout will be selected.

3.3. Timeout-based protocolFor transforming a static timeout-based protocol into a dynamic one, it is fundamental tofirst identify the timing variable of interest, on which the timeout is applied. For instance,in a pull-based failure detector the variable of interest is the round-trip delay of the re-quest/reply pair, while in some round-based protocol it may be the delay for completing around. Then, the protocol must be instrumented for monitoring the temporal variable andfor sending the measured values to Adaptare. Finally, whenever the timeout is used theremust be a call to Adaptare for updating its value. The approach requires some changes tothe protocol code, in particular to collect samples of the temporal variable. This is a fixeddevelopment cost, but the overhead in performance is not significant.

4. Application exampleWe applied the described approach to a consensus protocol designed for wireless en-vironments [Moniz et al. 2009], for improving its performance. The protocol executes inrounds with several phases, in which every process sends a broadcast and waits for a givennumber of messages in order to make progress towards a consensus decision. A timeoutprevents processes to wait indefinitely if no sufficient messages are received. In this case,processes start a new phase and resend the broadcast. In the original implementation, thetimeout was fixed.

I Workshop on Autonomic Distributed Systems 19

To be able to use an adaptive timeout, we first identified the temporal variableto be the time required for receiving a message, measured from the beginning of a newphase. All the delays are measured and used to feed a local instance of Adaptare, which isthus able to characterize the time it takes to receive a message. Concerning the mappinglayer, the fast termination requirements of the consensus protocol were transformed to acoverage requirement in the following way. Given the protocol definition, it is possibleto know how many messages must be received in each phase in order to make progress,which is n/2 + 1 for n participating processes. Therefore, a good criteria for achievingoptimized performance is to use a timeout whose coverage (the probability that it will belarge enough) allows to receive this precise number of messages. The coverage is thus setto the number of required messages over the total number of possibly received messages.

We ran some experiments in the Emulab wireless environment to compare im-plementations with static and dynamic timeouts. In particular, we wanted to know howthe number of nodes would impact on performance. Therefore, the experiments weredone with 4, 7, 10, 13 and 16 nodes. As expected, we were able to observe the benefitsof using an adaptive timeout. In particular, we observed that the average timeout in thedynamic implementation was increasing linearly from 13ms (with 4 processes) to about25ms (with 16 processes), thus adapting to the increased contention and communicationdelays, when increasing the number of nodes. In the static implementation, with a 10mstimeout, the average latency of consensus was increasing much faster, reaching 225ms for16 processes, while it was just 114ms in the dynamic version. We also observed that theaverage number of broadcasts per round was kept almost stable in the dynamic version(between 3 and 6), while in the static version it increased from 4 to 23.

5. ConclusionIn this short paper we argued about the need for transforming static into timeout adap-tive protocols, namely in wireless networks. We proposed an approach that requires aminimum amount of changes to static protocols, while still allowing them to benefit fromdynamic timeouts. A timeout provisioning service is key to the approach, in conjunctionwith a mapping layer. The approach was applied to transform a static consensus proto-col for wireless environments and the results allowed us to conclude that it is possible toachieve the intended performance improvements.

ReferencesDixit, M., Casimiro, A., Lollini, P., Bondavalli, A., and Verissimo, P. (2011). Adaptare:

Supporting automatic and dependable adaptation in dynamic environments. ACMTransactions on Autonomous and Adaptive Systems, (to appear). Also as Dep. of In-formatics, Univ. of Lisboa, Technical report TR-09-19.

Moniz, H., Neves, N. F., Correia, M., and Verissimo, P. (2009). Randomization canbe a healer: consensus with dynamic omission failures. In Proceedings of the 23rdInternational Conference on Distributed Computing, pages 63–77.

White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M.,Barb, C., and Joglekar, A. (2002). An integrated experimental environment for dis-tributed systems and networks. In 5th Symposium on Operating Systems Design andImplementation, pages 255–270, Boston, MA, USA.

20 Anais

Automatically Tuned on Multicore SystemsMurilo Boratto1, Leandro Coelho2, Brauliro Leal1

1 Colegiado de Engenharia da Computacao (CECOMP)Universidade Federal do Vale do Sao Francisco (UNIVASF)

Av. Antonio Carlos Magalhaes, 510, Santo Antonio, 48902-300,Juazeiro – Bahia – Brazil

2Nucleo de Arquitetura de Computadores e Sistemas Operacionais (ACSO)Universidade do Estado da Bahia (UNEB)

Rua Silveira Martins, 2555, Cabula, 41195-001,Salvador – Bahia – Brasil

{murilo.boratto, brauliro.leal}@univasf.edu.br, leandrocoelho@uneb.br

Abstract. Automatic tuning techniques have been used in the design of seve-ral programming algorithms in recent years. This paper aims to explore theprogramming routines that can be automatically adapted to the computationalsystem conditions. Techniques have been developed in different fields, and es-pecially in linear algebra routines. In this work the possibility of applyingautomatic optimization techniques to solve the triangular system problem isanalyzed. The routines are developed along with their theoretical executiontime, t(s) = f(s, AP , SP ), where s represents the problem size, SP are systemparameters, and AP are algorithmic parameters.

1. IntroductionDuring the last years different auto-optimization techniques of parallel routines havebeen developed with the purpose of achieving routines that automatically tune to thecharacteristics of computer systems and that are able to run efficiently independent ofthe knowledge of end-users in parallel programming. The potential users of high per-formance parallel systems are mainly scientists and engineers that require problem sol-ving with an elevated computational cost, but that normally do not have an extendedknowledge in parallelism. Auto-optimization techniques have been applied in differentfields [Brewer 1994], specially in linear algebra routines [Chen et al. 2003], which makeup the basic computing element in the resolution of many scientific problems.

One of the techniques used in the development of routines with auto-optimization capabi-lity uses the parametrization of the execution time model [Cuenca et al. 2005]. The mo-dels can be used to make some of the decisions that enable the routine to reduce its execu-tion time. The methodology applied consists of identifying algorithm and system parame-ters to analyze the algorithm, both theoretically and experimentally, with the purpose ofdetermining the influence of system parameter values in the selection of the best algo-rithm parameter values. The team that has developed this piece of work has experiencein the application of automatic optimization techniques in Jacobi methods for the eigen-value problem [Cuenca et al. 2001], LU and QR factorization [Song et al. 2010], and the

I Workshop on Autonomic Distributed Systems 21

problem of least squares in Toeplitz matrices [Alberti et al. 2004]. The application of theprevious ideas to different algorithmic schemes is currently being worked on, such as dy-namic programming schemes [Martınez et al. 2006], as well as traversal algorithms forsolution trees [Gimenez et al. 2006]. The present work is mainly concerned with auto-optimization of parallel algorithm schemes knowledge field, studying the application ofalgorithm optimization techniques in which an execution time parametrization is able tobe done, centering on multicore systems.

In this work, analysis and application of automatic optimization techniques were pro-posed. The basic idea behind of the optimization consists of obtaining routine executiontime in the form of: t(s) = f(s, AP, SP) [Cuenca et al. 2004], where s represents the sizeof the problem, SP system parameters, and AP algorithm parameters. The intention is tostudy techniques that allow the development of parallel routines that automatically tuneto the characteristics of the parallel system where they will be executed. This way theusers are provided with routines capable of running efficiently in the respective workingenvironment, regardless of the characteristics of the system and the knowledge of the userabout parallel programming.

Firstly, to test the developed methodology, the resolution of triangular systems is studi-ed as an example. In these cases, the system parameters are costs of basic arithmeticoperations and communication, and algorithmic parameters are block size and numberof threads. Some methods used to estimate these parameters are analyzed. In executiontime, the value of the algorithm parameters with which the problem is solved is obtainedby estimating the values through the theoretical model, where values of system parametersare automatically substituted (number of threads and block size), previously obtained inan installation process.

2. Experimental ResultsThis section shows experimental results of the implemented algorithms for the auto-optimized to solve the triangular system problem. Experiments were done in one typeof architecture, machine with 2 processors with 4 physical cores per processor. Includingarchitecture IntelrCore 2 Quad, 3 GHz clock rate and 16 GB. An icc compiler and MKLlibrary for LAPACK [MKL 2009] were used, are Intel proprietary providing support forthe OpenMP API. Previously, a methodology to self-optimized parallel implementationhas been presented. The code was run several times with different problem sizes (n) fordifferent block sizes (sb) and varying the number of threads (nth) take this off through anexecutable code. A significant improvement in execution time was obtained and searchis done to find the best SP parameters. A self-optimized parallel implementation hasbeen taken as parameter to build the theoretical modeling of the execution time with thefollowing:

t(n) = f(n,AP, g(n,AP )) = f(n, sb, nth, g(n, sb, nth)). (1)

The optimum block size and number of threads are not a constant value. It depends onthe platform and on the problem size. Thus, a good selection for each specific case ofthis block size and number of threads is important. For the system the routine has beenexecuted for different reasonable block sizes (16, 32, 64, 128, 512 and 1024) and numberof threads (2, 3, 4, 5, 6, 7 and 8) comparing the experimental with theoretical model.

22 Anais

In charts of the Fig. 1 (1)(2) it is a comparison performance between sequential implemen-tation corresponding a call DTRSV BLAS routine and self-optimized parallel implemen-tation with the best parameters. Basing on execution times observed, has been obtainedautomatically optimum number of threads and block size, finding the best combination ofparameters for this platform. After varying the amount of threads in experiments, it hasbeen observed that performance was improved by using a block size of 1024. This is justi-fied by the cache-level exploring nature of multicore architecture which perfectly adjuststo the block size found. The charts in the Fig. 1 (3)(4) shows the comparison betweenthe performance of self-optimized parallel and sequential implementation using block de-composition, having the same trend as the previous case, but with a potential increasedue to the number of processors and cores of the tested node. When looking at the tablefor optimal experimented block size, it can be seen that task calculation time decreaseswith the number of used threads. This reduction in time occurs until we reach 8 threadswhen the number of cores is 8. Moreover, asynchrony provides algorithms with superscalability, unlike distributed memory, having in the management of performed tasks, aworkload balance between thread execution.

0

256

512

768

1024

1280

0 10000 20000 30000 40000 50000 60000 70000

Siz

eblo

ck

Size of the problem

Self-optimised for the Best SizeBlock

Sizeblock

0

2

4

6

8

10

0 10000 20000 30000 40000 50000 60000 70000

Thre

ads

Size of the problem

Self-optimised for the Best Number of Threads

Threads

0

2

4

6

8

10

12

14

10000 20000 30000 40000 50000 60000 70000

Tim

e(s

econds)

Size of the Problem

Experimental Time

SequentialParallel

0

2

4

6

8

10000 20000 30000 40000 50000 60000 70000

Speedup

Size of the Problem

Speedup

Speedup

0

2

4

6

8

1 2 3 4 5 6 7 8

Speedup

Threads

Speedups Octaprocessor Cluster Quadcluster

12800320004000064000

0

2

4

6

8

0 1 2 3 4 5 6 7 8 9 10

Speedup

Threads

Speedups Experiments

12800320004000064000

Figure 1. (1)(2) Self-Optimized for search the best block size and number ofthreads. (3)(4) Comparison between the performance the self-optimized paral-lel versus sequential routine. (5)(6) Comparison speedups with several cores.

I Workshop on Autonomic Distributed Systems 23

3. ConclusionsThis work has studied the usage of auto-optimization techniques in multicore systemsusing as example the resolution of triangular systems. For instance, the resolution oftridiagonal systems of equations have shown better performance through block decom-position. Thus, the intention is to validate the auto-optimization methodology for a widerange of parallel schemes.

However, it is know that the presented technique (i.e., the one used for the development oflibraries with the capability of automatic optimization) could be adapted to other heteroge-neous schemes, by simply varying the strategy of workload to processors. On the otherhand, it could be interesting the usage previously acquired knowledge in parallel skeletonschemes. Moreover, users will be able to easily generate specific functions of the skeleton,just programming in sequential way. Thus, the parallel execution becomes transparent tothe user, neither being necessary parallel programming nor knowledge in parallelism tobe able to obtain reduced execution times.

ReferencesAlberti, P., Alonso, P., Vidal, A., Cuenca, J., and Gimenez, D. (2004). Designing polyli-

braries to speed up parallel computations. International Journal of High PerformanceComputing Applications, 1(1/2/3):75–84.

Brewer, E. (1994). Portable High Performance Supercomputing: High Level PlatformDependent Optimization. PhD thesis, Massachusetts Institute of Technology.

Chen, Z., Dongarra, J., Luszczek, P., and Roche, K. (2003). Self adapting softwarefor numerical linear algebra and LAPACK for clusters. Parallel Computing, 29(11-12):1723–1743.

Cuenca, J., Gimenez, D., and Gonzalez, J. (2001). Modelling the behaviour of linearalgebra algorithms with message passing. pages 282–289. IEEE Computer Society.

Cuenca, J., Gimenez, D., and Gonzalez, J. (2004). Architecture of an automatically tunedlinear algebra library. Parallel Computing, 30(2):187–210.

Cuenca, J., Gimenez, D., and Martınez, J. P. (2005). Heuristics for work distributionof a homogeneous parallel dynamic programming scheme on heterogeneous systems.Parallel Comput., 31(7):711–735.

Gimenez, D., Cuenca, J., Martınez, J. P., Beltran, J. M., Boratto, M., and Vidal, A. M.(2006). Parametrizacion de esquemas algorıtmicos paralelos para autooptimizacion.In XVII Jornadas de Paralelismo.

Martınez, J. P., Almeida, F., and Gimenez, D. (2006). Mapping in heterogeneous sys-tems with heuristical methods. Workshop on state-of-the-art in Scientific and ParallelComputing, Sweden. Lecture Notes in Computing Science (LNCS).

MKL (2009). Intel Math Kernel Library for Linux. User’s Guide. Available in:http://developer.intel.com.

Song, F., Ltaief, H., Hadri, B., and Dongarra, J. (2010). Scalable tile communication-avoid QR factorization on multicore cluster systems. SC’10, ACM SIGARCH/IEEEComputer Society, pages 13–19.

24 Anais

Gerencia Autonomica de Redes DTN∗

Ewerton M. Salvador, Daniel F. Macedo, Jose Marcos S. Nogueira1 Departamento de Ciencia da Computacao

Universidade Federal de Minas GeraisBelo Horizonte-MG, Brasil

{ewerton,damacedo,jmarcos}@dcc.ufmg.br

Abstract. Disruption and delay tolerant networks (DTN for short) are employedin situations where node connections are sporadic. These characteristics ham-per the constant establishment of end-to-end paths, make the maximum RTT ex-cessive and considerably increase the probability of packet drops, which makedifficult the use of classic network management approaches. DTN nodes shouldemploy autonomic management approaches, in order to deal with the wide rangeof situations that can occur during the moments when there is no connection withthe rest of the network. Despite the frequent disconnections, we argue that it ispossible to define network-wide high-level management policies, even thougheach node will employ slightly different policies due to their autonomic opera-tion.

Resumo. Redes tolerantes a atrasos e desconexoes (ou redes DTN) sao em-pregadas em situacoes onde a conexao entre nos e esporadica. Estas carac-terısticas impedem o constante estabelecimento de caminhos fim-a-fim, tornamexcessivo o RTT maximo e aumentam consideravelmente a probabilidade dedescarte de pacotes, o que dificulta o emprego de metodos tradicionais de geren-ciamento de redes. Os nos DTN deverao empregar metodos de gerenciamentoautonomico, a fim de lidar com a vasta gama de situacoes que podem ocorrerdurante os diversos momentos de desconexao com o restante da rede. Ape-sar das desconexoes frequentes, argumentamos que e possıvel definir polıticasde alto nıvel para o gerenciamento da rede como um todo, mas os nos teraopolıticas ligeiramente diferentes entre si devido a operacao autonomica.

1. IntroducaoAs redes tolerantes a atrasos e desconexoes (Delay Tolerant Networks, ou simples-

mente DTN) foram desenvolvidas pensando-se em se prover comunicacao em ambientesonde a desconexao dos enlaces de comunicacao sao frequentes, atraves do emprego demecanismos do tipo store and forward para o roteamento de mensagens [Cerf et al. 2007].As DTNs foram originadas a partir dos esforcos voltados ao estabelecimento de umarede interplanetaria. Contudo, e possıvel se fazer uso de diversas caracterısticas dessetipo de rede em aplicacoes terrestres, especialmente em cenarios onde as aplicacoes saoassıncronas e nao sensıveis a grandes variacoes nas condicoes de entrega [Ivansic 2009].

Dificilmente as solucoes existentes para o gerenciamento de redes de computa-dores, especialmente as redes TCP/IP, irao se adequar bem a essas novas exigencias im-postas pelas redes DTN, conforme iremos detalhar na proxima secao deste artigo. A

∗Os autores gostariam de agradecer ao CNPq, a CAPES e a FAPEMIG pelo investimento realizado nodesenvolvimento deste trabalho.

I Workshop on Autonomic Distributed Systems 25

construcao de um sistema de gerenciamento DTN constitui um problema em aberto epermanece um verdadeiro desafio de engenharia [Birrane and Cole ]. O presente artigodescreve uma possıvel solucao para este problema, atraves do emprego de tecnicas degerenciamento baseado em polıticas (Policy-Based Network Management, ou PBNM)e de mecanismos de computacao autonomica. Dentre as vantagens desta abordagem,destacam-se a possibilidade de gerencia das redes DTN em um alto nıvel de abstracao e acapacidade dos nos de tomarem decisoes autonomicas de forma a permitir que um no re-torne a um estado anterior conhecidamente valido nos casos em que alguma operacao degerenciamento erronea tenha sido executada. O restante deste artigo esta organizado daseguinte forma: a Secao 2 descreve os desafios vigentes quanto a elaboracao de solucoesde gerenciamento para redes DTN; a proposta de uma arquitetura de gerenciamento edescrita na Secao 3; por fim, conclusoes sao apresentadas na Secao 4.

2. Desafios na Gerencia de Redes DTNA seguir serao descritos os principais desafios existentes na missao de se desen-

volver solucoes de gerenciamento para redes DTN.

Altos atrasos de propagacao de mensagens. A alta mobilidade, baixa confia-billidade dos enlaces e a baixa densidade de nos fazem com que mensagens em transitopossam demorar horas ou ate mesmo dias para serem entregues aos seus destinatarios.Isto complica enormemente a gerencia de redes, uma vez que e muito difıcil manter umavisao da configuracao da rede, e praticamente impossıvel de se empregar mecanismos dealarmes para a notificacao de situacoes anormais.

Frequentes desconexoes. As desconexoes fazem com que grandes secoes da redefiquem incomunicaveis. Entretanto, os grupos de nos frequentemente podem comunicarentre si, de forma que a rede poder manter a sua operacao de forma local. Assim sendo, etentador instalar um gerente local em cada um destes grupos, de forma que a rede operede forma autonoma. Tal abordagem requer mecanismos de negociacao, uma vez que estesgrupos podem vir a se juntar no futuro, depois de operarem grandes intervalos de temposde forma isolada. Assim, as polıticas dos grupos podem ser significativamente diferentes.

Limitacoes de buffer. Redes DTN utilizam o paradigma store and forward. Men-sagens em transito, desta forma, sao armazenadas em memoria secundaria nos nos. Estefato, aliado ao emprego de comutacao de mensagens, gera grande pressao sobre os buffersde mensagens. Os buffers possuem capacidades limitadas, sendo necessario empregarpolıticas de descarte de mensagens para lidar com altas demandas de armazenamento. Asmensagens podem ser arbitrariamente longas (por exemplo, um filme ou uma mensagemde voz), de forma que uma mensagem grande o bastante pode forcar o no a descartar todasas mensagens inicialmente armazenadas no buffer.

Desta forma, a gerencia centralizada de uma rede DTN e inviavel. As solucoesde gerenciamento DTN devem ser distribuıdas, onde parte ou toda a gerencia da rededevera ocorrer sem intervencao de um servidor central. O modelo de decisao (modeloshierarquicos, gerenciamento por delegacao ou gerenciamento totalmente distribuıdo) aser empregado deve ser estudado posteriormente.

3. Uma Arquitetura de Gerenciamento Multi-NıveisDevido a organizacao das redes DTN e suas caracterısticas, acreditamos que uma

arquitetura de gerenciamento multi-nıveis seja a melhor solucao. Pelo menos dois nıveis

26 Anais

de gerenciamento irao existir. Em um nıvel mais alto, o gerente da rede especificapolıticas de alto nıvel (provavelmente polıticas de negocio tais como maximize o tempode vida da rede, usuarios nao autorizados nao devem acessar a rede), que irao determi-nar a operacao da rede de forma geral. Estas polıticas serao refinadas, de forma a seremtraduzidas em polıticas que irao atuar em cada dispositivo da rede.

3.1. Refinamento de polıticasTomando como modelo a hierarquia de polıticas proposta por Strassner

[Strassner 2003], conhecida como policy continuum, sera necessario definir qual nıvel depolıticas serao derivadas pelo gerente da rede. Estas polıticas serao, entao, disseminadas atoda a rede. As polıticas enviadas pelo gerente devem ser genericas o suficiente de formaque possam demorar horas ou ate dias para serem instaladas em toda a rede. Polıticasmuito especıficas, caso demorem a ser instaladas em todos os nos da rede, podem gerarinterrupcoes no servico. Um exemplo seria a troca de uma chave-mestra de criptografia.Caso os nos que possuam a nova chave mestra parem de aceitar mensagens utilizando achave antiga, as mensagens antigas que ainda nao chegaram aos seus destinatarios naopoderao ser abertas.

Assim, faz-se necessario analisar o modelo de policy continuum para determinarqual nıvel da hierarquia ficara responsavel pelo refinamento, disseminacao e monitoracaodas polıticas empregadas. Ao mesmo tempo, o numero de nıveis de gerentes e o tamanhoda area sob a responsabilidade dos mesmos deverao ser analisados considerando aspec-tos tais como quantidade de recursos necessarios para a gerencia, atraso medio para ainstalacao de novas configuracoes e obtencao de dados de monitoracao, possibilidade deemprego de alarmes, entre outros.

3.2. Acomodando desconexoes e interrupcoesPara que seja possıvel permitir desconexoes e interrupcoes, as arquiteturas de

gerenciamento de DTNs deverao permitir que regioes da rede operem de forma autonoma.Cada regiao, ou grupo de nos que operem independente do resto da rede, devera possuirum gerente local. Este ira gerenciar a configuracao dos nos sob seu comando, podendoate mesmo mudar as polıticas de gerencia utilizadas na regiao. Essa flexibilidade fara comque partes da rede operem com polıticas ligeiramente diferentes.

Alem da operacao desconectada, o tempo de propagacao de novas polıticas de altonıvel pode ser muito alto, bem como as mensagens de disseminacao de novas polıticassao susceptıveis a perdas. Assim, e impossıvel para uma entidade central monitorar se osnos estao aplicando as polıticas definidas para a rede. Tal monitoramento deve ser feitolocalmente, uma vez que o gerente da rede nao podera coletar dados de gerenciamento emintervalos regulares. Gerentes locais deverao realizar esse monitoramento, operando deforma autonoma em relacao ao gerente da rede. Como as polıticas poderao estar defasadasem algumas regioes da rede, os gerentes poderao realizar decisoes de gerencia baseadasem polıticas antigas, gerando assim diferencas nas configuracoes dos grupos.

Outra preocupacao e a disseminacao de comandos e alarmes na rede DTN. Osbuffers, sendo limitados, deverao empregar mecanismos baseados em prioridade para odescarte de mensagens. As mensagens de gerenciamento deveriam possuir uma priori-dade alta, uma vez que uma configuracao incorreta na rede poderia acarretar perdas signi-ficativas de desempenho, ou ate mesmo a interrupcao do seu servico. Uma alta prioridade

I Workshop on Autonomic Distributed Systems 27

evitaria o descarte de mensagens de gerencia, evitando que mensagens de instalacao denovas configuracoes ou mesmo alarmes sejam perdidos.

3.3. Agrupando os nos DTNComo definido anteriormente, o gerenciamento em redes DTN ira ocorrer por

regioes. Cada regiao tera o seu gerente, que sera um no comum que realizara a tarefa degerenciar os outros nos durante um certo intervalo de tempo. Os gerentes serao re-eleitosperiodicamente, de forma a tolerar particoes na rede, a desconexao do no gerente e umadegradacao na comunicacao com o gerente. Da mesma forma, dois grupos anteriormenteisolados de nos podem vir a se juntarem (por exemplo, se numa rede montada em umcenario de emergencia, dois grupos de resgate se encontrarem para realizar salvamentosem uma mesma area), requerendo uma federacao dos dois grupos. Este processo irademandar uma negociacao das polıticas a serem empregadas, uma vez que os gerentesdos dois grupos poderao ter derivado polıticas diferentes, mesmo sendo controlados pelomesmo gerente de rede.

O tamanho dos grupos ira depender de fatores tais como a conectividade da rede,o custo associado a coleta e monitoracao de dados de configuracao dos nos, bem como ocusto de coordenacao entre os gerentes. Como exemplo, um modelo de decisao totalmentedistribuıdo, onde cada no decide isoladamente qual acao tomar, e extremamente tolerantea desconexoes e atrasos, entretanto devera possuir um grande overhead de processamentoe comunicacao. Modelos parcialmente distribuıdos baseados em hierarquias serao menoscustosos, entretanto faz-se necessario identificar a quantidade de nıveis de hierarquia bemcomo a quantidade de particoes em cada nıvel hierarquico.

4. ConclusoesEste artigo apresentou os desafios relacionados ao gerenciamento de redes DTN.

Devido as suas caracterısticas, as redes DTN deverao empregar solucoes autonomicas degerencia. Entretanto, a inexistencia de caminhos fim-a-fim requer o desenvolvimento denovas arquiteturas de gerencia que tolerem altos atrasos e frequentes conexoes.

Considerando um sistema baseado em polıticas, as solucoes empregando umaorganizacao hierarquica e parcialmente distribuıda deverao apresentar os melhores re-sultados. Entretanto, estudos deverao ser realizados para identificar a melhor quantidadede nıveis a serem empregados na hierarquia, bem como a quantidade de grupos em que arede devera ser particionada. Alem disso, as longas desconexoes poderao criar diferencasnas polıticas e configuracoes entre as regioes da rede, de forma que a arquitetura deverasuportar ligeiras modificacoes nas polıticas de cada regiao.

ReferenciasBirrane, E. and Cole, R. G. Management of Disruption-Tolerant Networks: A Systems

Engineering Approach. In Proceedings of the SpaceOps 2010 Conference, Alabama,United States. April 2010.

Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and Weiss,H. (2007). Delay-tolerant networking architecture. RFC 4838 (Informational).

Ivansic, W. (2009). DTN network management requirements. Internet Draft (Informa-tional).

Strassner, J. (2003). Policy-Based Network Management. Morgan Kaufmann.

28 Anais

I Workshop on Autonomic Distributed Systems

♦ Sessão Técnica 3

Combinação de Expertise em Classificadores para Sistemas Autonômicos

Grinaldo Oliveira, Joberto Martins

Doutorado MultiInstitucional em Ciência da Computação (UFBA-UEFS-UNIFACS) Av. Adhemar de Barros, s/n - Campus de Ondina, Salvador - Bahia, CEP 40.170-110

grinaldo@gmail.com, joberto@unifacs.br

Abstract. Classifiers algorithms have been used as a way to improve world’s perception by autonomic systems. However, it is known that the accuracy of these classifiers depends on its accumulated learning. This work proposes a combined classifier approach and presents an expertise combination model strategy in order to improve the classification process.

Resumo. Algoritmos classificadores têm sido usados como uma forma de melhorar a percepção de mundo por sistemas autonômicos. Entretanto, é percebido que a acurácia destes classificadores depende de seu aprendizado acumulado. Este artigo aborda o uso de conjunto de classificadores e apresenta um modelo de combinação de expertise como estratégia de melhoria do processo de classificação.

1. Introdução

Um dos aspectos importantes em um sistema autonômico é sua capacidade de detectar e responder a um comportamento errôneo ou mudanças de condições com pouca ou nenhuma intervenção humana. Claramente, a tomada de decisão é uma questão crítica em tais sistemas, que devem saber como e quando invocar ações corretivas com base em experiências passadas (KASTEN, 2007).

A utilização de sistemas de aprendizado baseados em mineração de dados, métodos estatísticos ou algoritmos de classificação tem recebido crescente atenção para diagnósticos de falhas e outras demandas. Seu uso sustenta-se no fato de que padrões podem ser aprendidos e descobertos a partir do comportamento apresentado por um sistema gerenciado (GUAN 2010; KASTEN 2007; LI 2003).

De uma maneira formal, é dito que uma máquina aprende a partir de uma experiência E assimilada em um conjunto de tarefas T e performance medida P, se sua performance nas tarefas T, quando medidas em P, aumentam com a experiência E adquirida (MITCHEL, 1997).

No paradigma de aprendizado de máquina, a “aquisição de experiências” em algoritmos classificadores provém de processos indutivos, onde um classificador para uma categoria ci é construído sob o “aprendizado” de características herdadas de um conjunto de dados previamente rotulados sob ci (MARTINS, 2003). Esta abordagem, apesar dos bons resultados, demanda tempo e alocação de recursos computacionais, enquanto não se consegue consolidar um classificador eficiente (DIETTERICH 1997; KOTSIANTIS, 2004).

I Workshop on Autonomic Distributed Systems 31

Como forma de acelerar ou melhorar os resultados do processo de classificação, técnicas de combinação de classificadores têm sido utilizadas [XU, 2009]. Neste caso, é possível, da forma mais comum, combinar as hipóteses geradas por vários classificadores (TSYMBAL, 2003) ou, da forma menos tradicional, mesclar seu aprendizado ou expertise com o intuito de gerar um único classificador eficiente (BARANAUSKAS, 2001; OLIVEIRA, 2004).

Esta última estratégia possui alguns benefícios e desafios a serem abordados.

O presente artigo apresenta na seção 2 uma proposta de mesclagem de expertise baseada no algoritmo de classificação estatística Naive Bayes e levanta, na seção 3, algumas questões relativas à combinação de expertise.

2. Combinando de Expertise com Naive Bayes

Oliveira (2004) apresenta uma proposta de combinação das características provenientes de vários classificadores com o intuito de otimizar o processo de treinamento e possibilitar a construção de um único classificador mais eficiente, conforme a figura 1.

Exemplos

Avaliação

Aprendizado

Algoritmo deAprendizadoNaive-Bayes

Conjunto deCaracterísticas

(atributo,frequência,classe)

T1

Hipótese 1

Algoritmo deAprendizadoNaive-Bayes

Conjunto deCaracterísticas

(atributo,frequência,classe)

Ts

Hipótese s

...

Amostras deAprendizado

Atribuição dePesos (classe x

precisão)Filtro Estatístico

Atribuição dePesos (classe x

precisão)Filtro Estatístico

Algoritmo deMesclagem

Conjunto deCaracterísticas

Mesclado (atributo,frequência, classe)

Amostras deAvaliação

...Combinação de Classificadores

Peso

Peso

Figura 1. Arquitetura para combinação de classificadores naive bayes.

Para determinar a classe associada a um conjunto de dados, utilizando-se um classificador Naive Bayes, calcula-se, conforme a fórmula do quadro 1, a probabilidade de todas as possíveis classes e, ao final, escolhe-se aquela com a maior probabilidade

32 Anais

(MITCHEL, 1997). Esta fórmula baseia-se na coleta de um conjunto de características adquiridas pelo classificador (xi|C=ci) durante seu processo de aprendizado.

)()|()|( iii

ii cCPcCxPxcCP =×=== ∏

Quadro 1. Fórmula Naive Bayes

Com o objetivo de demonstrar a eficácia da técnica de mesclagem proposta, Oliveira (2004) apresenta a implementação de uma ferramenta denominada Expertext e dois estudos de casos relacionados ao seu uso. Nesta oportunidade, o trabalho apresenta também algumas conclusões a respeito da técnica proposta de mesclagem, condensadas aqui na próxima seção.

3. Questões Relativas à Combinação de Expertise

Tradicionalmente, a combinação de classificadores se dá através da combinação de suas hipóteses. Porém, ao invés de combinar as hipóteses de um conjunto de especialistas sobre um determinado assunto, por que não mesclar a expertise individual de cada um a fim de compor um único especialista?

Esta estratégia possui alguns benefícios interessantes observados por Oliveira (2004) em seu trabalho:

• Os especialistas podem ser treinados isoladamente, em momentos diferentes, sem necessidade de consumo de recursos de um único ambiente. Além disto, o histórico de aprendizado de cada especialista contribui para uma diversidade de suposições interessantes no processo de combinação.

• Os especialistas contribuem enviando sua expertise a fim de serem combinadas em um único especialista. Assim, o que irá ser demandado em um processo de avaliação de hipóteses final será apenas o esforço do super especialista, e não o esforço individual de cada especialista.

• A expertise final pode ser devolvida a cada especialista para uma melhor avaliação de hipóteses no ambiente ao qual está inserido.

Há, entretanto, alguns questionamentos a serem realizados:

• No processo de combinação é necessária uma avaliação de cada expertise para evitar a presença de maus especialistas que possam denegrir ou diminuir a expertise final. Além disto, os conhecimentos que possam ser supérfluos ao alvo de estudo das hipóteses devem ser descartados para não gerar perturbações na expertise final. Assim, é necessário algum tipo de avaliação prévia de sua qualidade. Como fazer isto sem correr o risco de gerar falsas avaliações?

• O processo de combinação de expertise é um pouco mais fácil em algoritmos classificadores simbólicos, como percebido em (BARANAUSKAS, 2001), porém pode-se mostrar mais complexo em algoritmos baseados em redes neurais, agrupamentos ou estatísticos.

I Workshop on Autonomic Distributed Systems 33

Assim, como realizar a junção de expertise nestes outros tipos de algoritmos?

• É possível realizar esta estratégia de combinação em algoritmos de classificação não supervisionados ?

Características intrínsecas a um sistema autonômico, como as habilidades de auto-configuração, auto-cura, auto-otimização ou auto-proteção, pressupõem a implementação de bons tomadores de decisão. Desta forma, considerando os princípios anteriormente citados neste artigo, a combinação de expertise configura-se com uma possível estratégia a ser seguida na construção de soluções voltadas para este fim.

4. Referências

BARANAUSKAS, J. A. Extração automática de conhecimento por múltiplos indutores. Tese de Doutorado, ICMC-USP. 2001.

DIETTERICH, T. Machine Learning Research: Four Current Directions. AI Magazine,18(4), 1997.

GUAN, Q.; FU, S. auto-AID: A Data Mining Framework for Autonomic Anomaly Identification in Networked Computer Systems. 29th IEEE International Performance Computing and Communications Conference (IPCCC), December 2010.

KASTEN, E.P.; MCKINLEY, P.K. "MESO: Supporting online decision making in autonomic computing systems," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 4, pp. 485-499, Abril de 2007.

KOTSIANTIS, S. B.; PINTELAS, P. E. An Online Ensemble Of Classifiers, The Fourth International Workshop on Pattern Recognition in Information Systems – PRIS-2004, In conjunction with 6th International Conference on Enterprise Information Systems, Porto - Portugal 14-17, Abril de 2004.

LI, Z; SRINIVASAN, SM; CHEN, Z; SHOU, Y; TZVETKOV, P; YAN, X; HAN, J (2003) Using data mining for discovering patterns in autonomic storage systems. Proceedings of the 2003 ACM workshop on algorithms and architectures for self-managing systems, San Diego, CA, Junho de 2003.

MARTINS, J. Classificação de páginas na internet. Trabalho de Conclusão (Mestrado). Instituto de Ciências Matemáticas e de Computação. USP. São Carlos, 2003.

MITCHEL, T. Machine Learning. McGraw-Hill, 1997.

OLIVEIRA, G. L. Categorização Automática De Documentos Por Múltiplos Classificadores Naive Bayes. Dissertação (Grau de Mestre em Redes de Computadores), Universidade Salvador, Salvador-Bahia, 2004.

TSYMBAL, A., PUURONEN, S., PATTERSON, D. Ensemble Feature Selection with the Simple Bayesian Classification. Information Fusion, Elsevier Science, Vol. 4, No.2, 2003.

XU, L; AMARI, S. Combining Classifiers and Learning Mixture-of-Experts. Encyclopedia of Artificial Intelligence 2009: 318-326

34 Anais

Uma Proposta para o Monitoramento e Controle Inteligente de Tráfego Urbano

Gilberto Nakamiti1,3, Fábio Pessôa de Sá2, José Henrique Ventura3, Vinicius Eduardo S. da Silva3

1 CEATEC - Pontifícia Universidade Católica de Campinas

Rod. D. Pedro I, km 136 – 13086-900 - Campinas, SP, Brasil

2 Faculdade de Tecnologia de Praia Grande, Praia Grande, SP, Brasil

3 Universidade Paulista, Campinas, SP, Brasil

nakamiti@puc-campinas.edu.br, fabio@fatecpg.com.br,

josehenriqueventura@hotmail.com, viniciuspontocom@gmail.com

Abstract. This paper describes an urban traffic control system which aims at

contributing to achieve more efficient traffic management. It includes fuzzy

sets, case-based reasoning, and genetic algorithms to handle dynamic and

unpredictable traffic scenarios.

Resumo. Esse artigo descreve um sistema de controle de tráfego urbano que

visa contribuir para um gerenciamento de tráfego mais eficiente. São

utilizados teoria dos conjuntos nebulosos, raciocínio baseado em casos e

algoritmos genéticos para lidar com as situações dinâmicas e imprevisíveis do

tráfego urbano.

I. Introdução

O problema do controle de tráfego urbano é essencial para o gerenciamento das cidades

e as vidas de seus cidadãos. Com o crescimento continuo das frotas de veículos, o

problema agrava-se particularmente nas grandes cidades.

Dentre as características desejadas para sistemas de controle de tráfego urbano

estão sua adaptabilidade a diferentes condições de tráfego, poder de reação a eventos,

respostas eficazes e rápidas, confiabilidade e tolerância a falhas, dentre outras.

Este trabalho descreve um sistema de controle de tráfego urbano que envolve

teoria dos conjuntos nebulosos, raciocínio baseado em casos e algoritmos genéticos,

estendendo uma primeira versão desenvolvida anteriormente pelo primeiro autor. As

diversas técnicas empregadas visam contribuir para atingir algumas das características

desejadas para este tipo de aplicação. O projeto atual é parte do programa “Cidades

Inteligentes”, financiado pela FINEP e que conta com trabalhos de várias universidades

brasileiras.

II. Trabalhos Relacionados

I Workshop on Autonomic Distributed Systems 35

Vários trabalhos têm tratado do problema de controle inteligente de tráfego,

considerando a comunicação entre os nós ou as estratégias de tomada de decisão. Em

[Katiyar 2011] e em [Lee 2010], por exemplo, os nós comunicam entre si, auto-

organizam-se e reagem a eventos utilizando uma infraestrutura de redes de sensores sem

fio. A predição de fluxo de tráfego é tratada em trabalhos como em [Pang 2008], que

utiliza uma rede neuro-fuzzy para obter maior precisão na predição de fluxo de tráfego

em séries de tempo caóticas. Um ambiente de supervisão é apresentado em [Bouamrane

2005] para identificar distúrbios e avaliar ações corretivas no sistema de tráfego.

III. Estratégia de Controle de Trânsito

O sistema de controle de tráfego é composto por agentes controladores localizados em

cada cruzamento onde há semáforos. Esses agentes são responsáveis por coletar

informações vindas de sensores (fluxo de tráfego e filas de veículos) e estabelecer uma

política local para controlar os semáforos. Além disso, eles são capazes de se comunicar

com os agentes vizinhos e com um agente supervisor.

Cada agente raciocina sobre as condições do trânsito, analisando variáveis como

o fluxo de veículos, filas de veículos, e tempos de espera. Condições locais são mais

relevantes do que condições mais remotas, e o agente supervisor deverá interferir na

política de controle.

Condições usuais de trânsito são modeladas através de regras da teoria dos

conjuntos nebulosos. Essas regras são usadas para treinar os agentes de modo a prepará-

los para lidas com cenários mais complexos. Quando um agente precisa ser reiniciado,

as regras nebulosas podem ser empregadas para que um agente possa tomar uma

decisão razoável. Um exemplo detalhado dessa estratégia nebulosa é mostrado em

[Nakamiti 2002].

Figura. 1. A estrutura de um caso

Como é virtualmente impossível modelar todas as situações de trânsito

possíveis, incluindo interações entre cruzamentos locais e remotos, é necessária uma

estratégia mais abrangente, adaptativa e flexível.

Dessa maneira, os agentes também implementam uma solução híbrida genética-

baseada em casos. Os casos são representados como uma série de slots (genes),

divididos em três seções: uma seção de atributos utilizada para representar e caracterizar

o caso, uma seção de ações utilizada para lembrar as ações de controle adotadas na

situação em questão, e uma seção de resultados com informações relacionadas ao

desempenho obtido com as ações descritas. (ver Figura 1). Cada slot na seção de

atributos representa uma variável de trânsito em especial, como fluxo do tráfego,

número de veículos na fila e tempo de espera (local e remoto). Os slots de ação

36 Anais

representam a estratégia de controle escolhida, como o tempo adotado para que o

semáforo permaneça verde ou vermelho naquela situação. Os slots de resultados

guardam informações sobre se ocorreu ou não variação, em relação a tamanhos de filas

e tempo de espera.

A aplicação de regras nebulosas gera a base de casos inicial. Após isso a

situação do trânsito é continuamente identificada, baseada nas variáveis citadas e é

usada para obter um subconjunto dos casos armazenados, baseado nas características de

similaridade e desempenho (geração zero). Essa geração será combinada através de

algoritmos genéticos. Na primeira versão do sistema, este processo ocorreu somente

uma vez por ciclo de semáforos. Mesmo sendo possível obter bons resultados utilizando

esse sistema, somente uma geração de casos de semáforos era obtida em cada ciclo.

Agora estamos investigando as melhorias no desempenho com uma simulação em

background, ou seja, estamos criando uma segunda camada de simulação. Casos

genéticos serão produzidos e testados na segunda camada até que o sistema atinja um

tempo limite e tenha que tomar uma decisão de controle. Nesse momento, o sistema irá

escolher o melhor caso produzindo pela thread executada em background para utilizar

no sistema de simulação. Esperamos que essa abordagem propicie um comportamento

mais eficiente e adaptativo.

As ações descritas no caso selecionado são tomadas, e o sistema armazena os

resultados. Os resultados incluem o aumento, a estabilidade, ou a redução das filas de

veículos e tempo de espera.

IV. Supervisor

Além dos agentes controladores, o sistema irá incluir um agente supervisor (que está

ainda sendo implementado). O supervisor ficará localizado no departamento de trânsito

da cidade. Algumas funcionalidades implementadas pelo agente supervisor também

serão implementadas pelos agentes controladores, especialmente por questões de

tolerância a falhas e outros problemas relacionados a sistemas distribuídos.

O supervisor também incluirá regras nebulosas para detectar situações anormais

de tráfego, e também bons resultados obtidos pelos agentes controladores. Dependendo

da situação, o próprio supervisor irá tentar resolver os problemas de trânsito, ou até

mesmo informar um operador de trânsito humano, que irá ter acesso contínuo à situação

atual do trânsito através de uma interface de controle.

O agente supervisor irá armazenar os casos genéticos recebidos dos agentes de

controle, de modo que os melhores casos poderão ser usados por agentes similares em

situações similares. Irá também ser capaz de forçar uma política de controle, quando as

estratégias adotadas pelos agentes de controle não estiverem sendo eficazes ou não

forem desejadas. Obviamente, essa funcionalidade poderá também ser utilizada em

casos de emergência.

VI. Resultados Iniciais

Uma primeira versão do sistema de controle de trânsito foi implementada assim como

as estratégias convencionais de simulação para comparação de desempenho.

I Workshop on Autonomic Distributed Systems 37

Figura. 2. Tamanho médio das filas

Os testes mostram a média para filas de veículos e tempo de espera em três

abordagens: o SIMTUR apresentado neste artigo, uma estratégia simultânea, e outra

sequencial. Informações reais do centro de Campinas - SP - Brasil, foram coletadas nas

terças-feiras e quintas-feiras entre às 18:30 e 19:30, correspondente à hora do pico da

tarde. Os testes apresentados ainda não incluíam a presença de um supervisor. As três

estratégias foram testadas com 60%, 80%, 100%, 120% e 130% do fluxo do trânsito

monitorado. A Figura 2 mostra os resultados obtidos em relação à média de veículos por

faixa na fila ao final da fase de vermelho. Com o fluxo de tráfego medido (100%), por

exemplo, a primeira versão apresentou 3.4 veículos contra 4.5 veículos nas estratégias

convencionais. Quando testamos os sistemas aumentando em 30% o fluxo de trânsito

em horário de pico, o SIMTUR apresentou média de 8.9 veículos por faixa. As outras

estratégias levaram o trânsito da cidade a uma situação caótica.

VII. Conclusão

Este artigo apresentou um simulador de um sistema de controle de trânsito. Este sistema

é parte de um sistema maior voltado ao controle e gerenciamento de trânsito. Ainda há

muito trabalho a ser feito de modo a melhorar as estratégias de controle, segurança,

tolerância a falhas, disponibilidade, entre outros, porém os primeiros resultados obtidos

nas simulações parecem bastante promissores.

Referências K. Bouamrane, C. Tahon, M. Sevaux, B. Beldgilali (2005), “Decision Making System for

Regulation of a Bimodal Urban Transportation Network, Associating a Classical and a Multi-

Agent Approaches”, Journal Informatica, IOS Press, Amsterdan, pp. 473-502.

V. Katiyar, P. Kumar, N. Chand (2011), “An Intelligent Transportation System Architecture

using Wirelles Sensor Network”, International Journal of Computer Applications, vol. 14, no.

2, pp. 22-26.

W. Lee, S. Tseng, W. Shieh (2010), “Collaborative real-time traffic information generation and

sharing framework for the intelligent transportation system”, Information Sciences, vol. 180,

no. 1.

G. Nakamiti, R. Freitas, F. Gomide (2002), “Intelligent, Real-Time Traffic Control”,

International Journal of Smart Engineering Systems Design, vol. 4, no.1, pp. 49-62.

M. Pang, X. Zhao (2008), “Traffic Flow Prediction of Chaos Time Series by Using Subtractive

Clustering for Fuzzy Neural Network Modeling”, 2o International Symposium on Intelligent

Information Technology Application, Washington, pp.23-27.

0

5

10

15

20

25

30

60 80 100 120 130

SIMTUR Simultaneous Progressive

38 Anais

Um Sistema Autonomo para a Coordenacao de DispositivosMoveis baseada em Coalizoes Sobrepostas

Vitor A. dos Santos1, Giovanni C. Barroso1, Mario F. Aguilar1,Antonio de B. Serra2, Jose M. Soares1

1Departamento de Teleinformatica – Universidade Federal do Ceara(UFC)

2Instituto Federal de Educacao, Ciencia e Tecnologia do Ceara (IFCE)

vitor@ufc.br, gcb@fisica.ufc.br, mario.fiallos@gmail.com,

prof.serra@gmail.com, marques.soares@gmail.com

Abstract. In this work, we focus on problems modeled as a set of activities tobe scheduled and accomplished by mobile autonomous devices that communi-cate via a mobile ad hoc network. In such situations, the communication cost,computational efforts and environment uncertainty are key challenges.We propose an autonomic system that coordinates the dynamic formation ofoverlapping coalitions and the scheduling of tasks within them. Heuristics forcalculating the size of coalitions, as well as for scheduling tasks are proposed.The system is applied to solve the problem of area coverage in a simulated envi-ronment and the results show that good schedules are obtained with lower costof communication and computation in comparison with the solution based onglobally known information.

Resumo. Neste trabalho, sao tratados os problemas modelados como ativida-des a serem escalonadas e realizadas por times de dispositivos moveis autonomosque se comunicam atraves de uma rede movel ad hoc. Em tais situacoes, o custoda comunicacao e a incerteza do ambiente envolvido configuram dificuldadesprincipais.E proposto um sistema autonomo que coordena a formacao dinamica de co-alizoes sobrepostas e o escalonamento de atividades dentro de tais coalizoes.Heurısticas para o calculo do tamanho e tempo de vida de coalizoes, bem comopara o escalonamento de atividades sao propostas. O sistema e aplicado paraa solucao do problema da cobertura de area em um ambiente simulado e osresultados mostram que bons escalonamentos sao obtidos a um menor custode comunicacao e computacao em comparacao com a solucao baseada eminformacao globalmente conhecida.

1. IntroducaoHa diversos problemas que envolvem a coordenacao de times de dispositivos moveis quese comunicam atraves de uma rede movel ad hoc no intuito de compartilharem e escalona-rem atividades geograficamente dispersas em um ambiente desconhecido. A cobertura dearea [Gonzalez and Gerlein 2009] e o transporte de carga [Murata and Nakamura 2004]sao exemplos destes problemas. O problema da cobertura de area e bem conhecido nocampo da robotica, com diversas pesquisas relacionadas a cobertura realizada por um

I Workshop on Autonomic Distributed Systems 39

unico robo. Uma forma de resolver este problema atraves de um time e particionar aarea original em subareas de forma que a cobertura de cada subarea e uma atividade a serrealizada por um robo dentro do time e o desafio que surge e escalonar tais atividades.

O controle distribuıdo de dispositivos moveis autonomos que atuam cooperativa-mente para o escalonamento e realizacao de atividades e um problema desafiador, pois oescalonamento distribuıdo de atividades e NP-Completo [Tsitsiklis and Athans 1985] e acomunicacao para o compartilhamento de dados pode comprometer a escalabilidade dosistema.

Assim, neste trabalho e proposto um sistema nao centralizado autonomo queadota um mecanismo baseado em coalizoes sobrepostas que restringe a distribuicao deinformacao entre os dispositivos e, dessa forma, reduz os esforcos computacional e decomunicacao envolvidos. Cada dispositivo e capaz de organizar suas proprias coalizoese calcular escalonamentos de atividades a partir do conhecimento obtido dentro destascoalizoes.

No levantamento de trabalhos relacionados, nao foram encontradas solucoes queenvolvessem a formacao de coalizoes sobrepostas e informacao parcialmente distribuıdacomo mecanismos de reducao do espaco de busca dos escalonamentos. Ha algumasheurısticas para a reducao do espaco de busca nos casos em que atividades requeremum esforco de inicializacao [Allahverdi et al. 2008]. Tais heurısticas seriam adequadasao contexto aqui considerado, pois atividades geograficamente dispersas frequentementerequerem um deslocamento inicial. Contudo, esses escalonadores nao consideram timesmoveis e custos de comunicacao. Barbulescu et al. [Barbulescu et al. 2010] propoem ummecanismo de coordenacao para o escalonamento de atividades por dispositivos moveis.Entretanto, os autores nao tratam das questoes de comunicacao e formacao de coalizoes.

A seguir, a secao 2 descreve o sistema proposto, a secao 3 e dedicada ao estudode caso realizado para avaliar o sistema. Por fim, a secao 4 apresenta as conclusoes dotrabalho.

2. Descricao do sistema propostoA arquitetura do sistema proposto em cada dispositivo e composta por tres modulos prin-cipais, como ilustrado na Figura 1. A estrutura de dados principal mantem informacoessobre os estados dos dispositivos, suas coalizoes e atividades. Atividades representamobjetivos menores a serem alcancados para a solucao do problema.

O Modulo de Apoio a Decisao e responsavel pelo calculo de escalonamentose formacao de coalizoes, a qual e baseada na k-vizinhanca de um dispositivo. A k-vizinhanca de um dispositivo γ no tempo t e um conjunto formado pelos k mais proximosdispositivos de γ em um intervalo de tempo. O algoritmo para o calculo de k-vizinhancautiliza elementos da rede movel ad hoc e aplica ideia similar a do protocolo conhecidocomo k-neigh [Blough et al. 2003]. Para o calculo de escalonamentos, e proposta umaheurıstica chamada de Escolha k-Gulosa Alternada, a qual se baseia na heurıstica PickMinimum Weighted Processing Time (PMWP) [Arnaout et al. 2006]. Nesta abordagem,as melhores atividades sao escolhidas alternadamente para cada dispositivo.

O modulo de coordenacao e responsavel por organizar os passos que envolvema formacao de coalizoes, escalonamento de atividades e compartilhamento de dados do

40 Anais

domınio.

Figura 1. Arquitetura do sistema em cada dispositivo.

3. Estudo de CasoO sistema proposto foi implementado, validado e avaliado a partir da sua aplicacao emum estudo de caso. Tal estudo foi realizado sobre o problema da cobertura de area, queconsiste do mapeamento de uma extensao em area utilizando-se um grupo de robos. Foiadotada uma abordagem de cobertura em forma de espirais baseada no algoritmo BSA[Gonzalez and Gerlein 2009], onde os dispositivos utilizam obstaculos, paredes e pontosja cobertos para realizarem percursos circulares. Cada atividade e definida como umasubregiao a ser coberta. Inicialmente, cada dispositivo possui somente uma atividade.Novas atividades, entretanto, podem surgir ao longo de um missao, ao passo que o algo-ritmo BSA produz novas subregioes.

Os testes foram realizados em dois ambientes com dimensoes 80x80, mas comdistribuicao de obstaculos diferentes. Foram avaliadas tres abordagens para a coberturade area de acordo com o sistema proposto: BSA com escalonamento EkGA e grandescoalizoes, na qual coalizoes estaticas sao contruıdas, BSA com escalonamento EkGA ecoalizoes dinamicas, que e baseada na proposta de formacao de coalizoes dinamicas e aversao BSA-CM[Gonzalez and Gerlein 2009], versao distribuıda do algoritmo BSA.

O tempo final de realizacao de uma missao aqui considerado corresponde a maiorquantidade de acoes realizadas por um dispositivo. No caso da cobertura de area, cadaacao corresponde a uma unidade mınima de area do ambiente simulado percorrida. Osgraficos da Figura 2 apresentam as relacoes entre os tempos absolutos obtidos e limitesinferiores de tempo calculados como uma razao da area total a ser coberta pelo numerode dispositivos.

4. ConclusoesO mecanismo do coalizoes sobrepostas do sistema autonomo proposto mostrou-se ca-paz de reduzir o espaco de busca referente a construcao de escalonamentos e o volume demensagens enviadas. A reducao do espaco de busca nao afetou substancialmente a capaci-dade de construcao de bons escalonamentos, uma vez que as atividades eram sensıveis aslocalizacoes dos dispositivos, e a formacao de coalizoes por dispositivos proximos ja pos-sibilitou escalonamentos satisfatorios. Isto foi observado a partir dos graficos de tempo

I Workshop on Autonomic Distributed Systems 41

Figura 2. Percentuais de tempos finais em relacao ao limite inferior de tempo nosambientes simulados com obstaculos: (a) aleatorios. (b) horizontais.

final, que mostraram tempos finais para as solucoes baseadas no sistema proposto naosuperiores a 150% do limite inferior de tempo, nos testes em ambientes com obstaculosaleatorios, e 170%, nos testes em ambientes com obstaculos horizontais.

ReferenciasAllahverdi, A., Ng, C. T., Cheng, T. C. E., and Kovalyov, M. Y. (2008). A survey of sche-

duling problems with setup times or costs. European Journal of Operational Research,187(3).

Arnaout, J.-P., Rabadi, G., and Mun, J. H. (2006). A dynamic heuristic for the stochasticunrelated parallel machine scheduling problem. International Journal of OperationsResearch, 3:136–143.

Barbulescu, L., Rubinstein, Z. B., Smith, S. F., and Zimmerman, T. L. (2010). Distributedcoordination of mobile agent teams: the advantage of planning ahead. In Proceedingsof the 9th International Conference on Autonomous Agents and Multiagent Systems:volume 1 - Volume 1, AAMAS ’10, pages 1331–1338, Richland, SC. InternationalFoundation for Autonomous Agents and Multiagent Systems.

Blough, D. M., Leoncini, M., Resta, G., and Santi, P. (2003). The k-neigh protocolfor symmetric topology control in ad hoc networks. In Proceedings of the 4th ACMinternational symposium on Mobile ad hoc networking & computing, MobiHoc ’03,pages 141–152, New York, NY, USA. ACM.

Gonzalez, E. and Gerlein, E. (2009). Bsa-cm: A multi-robot coverage algorithm. InProceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web In-telligence and Intelligent Agent Technology - Volume 02, WI-IAT ’09, pages 383–386,Washington, DC, USA. IEEE Computer Society.

Murata, T. and Nakamura, T. (2004). Multi-agent cooperation using genetic networkprogramming with automatically defined groups. In Genetic and Evolutionary Com-putation GECCO 2004, volume 3103 of Lecture Notes in Computer Science, pages712–714. Springer Berlin / Heidelberg.

Tsitsiklis, J. and Athans, M. (1985). On the complexity of decentralized decision makingand detection problems. Automatic Control, IEEE Transactions on, 30(5):440–446.

42 Anais

I Workshop on Autonomic Distributed Systems 43

Índice por Autor

A Aguilar, M. F. ..................................... 39

B Barroso, G. C. ..................................... 39 Boratto, M. .......................................... 21

C Casimiro, A. ........................................ 17 Coelho, L. ........................................... 21

D da Silva, M. R. .................................... 11 da Silva, V. E. S. ................................. 35 de Macêdo, J. A. F. ............................. 11 de Sá, F. P. .......................................... 35 Dixit, M. ............................................. 17 dos Santos, V. A. ................................ 39

L Leal, B. ............................................... 21

M Macedo, D. F. ..................................... 25

Machado, J. C. ............................... 7, 11 Martins, J. .......................................... 31 Monteiro, J. M. .................................. 11 Moreira, L. O. ...................................... 7

N Nakamiti, G. ....................................... 35 Nogueira, J. M. S. .............................. 25

O Oliveira, F. G. ...................................... 3 Oliveira, G. ........................................ 31

R Rebello, V. E. F. .................................. 3

S Salvador, E. M. .................................. 25 Serra, A. de B. .................................... 39 Soares, J. M. ....................................... 39 Sousa, F. R. C. ..................................... 7

V Ventura, J. H. ..................................... 35

Patrocínios:

9 772177 496009

ISSN 2177-496X