Francimary P.Garcia [email protected] Agentes para Balanceamento de Carga e Alocação de Tarefas em Sistemas Distribuídos

Francimary P.Garcia [email protected]

Agentes para Balanceamento Agentes para Balanceamento de Carga e Alocação de Tarefas de Carga e Alocação de Tarefas em Sistemas Distribuídos.em Sistemas Distribuídos.


••RoteiroRoteiro

• MOTIVAÇÃO.MOTIVAÇÃO.

• ANALISANDO BALANCEAMENTO DE CARGA.ANALISANDO BALANCEAMENTO DE CARGA.

• CONTRACT NET PROTOCOL.CONTRACT NET PROTOCOL.

• UMA APLICAÇÃO DO CNP.UMA APLICAÇÃO DO CNP.

• CONCLUSÃO.CONCLUSÃO.


MOTIVAÇÃO:MOTIVAÇÃO:

• Muitos são os problemas causados por Muitos são os problemas causados por distribuições de cargas não balanceadas distribuições de cargas não balanceadas em situações reais de nossa vida, como em situações reais de nossa vida, como por exemplo, o transito intenso em por exemplo, o transito intenso em algumas ruas, ou a alta utilização, em um algumas ruas, ou a alta utilização, em um CPD, das máquinas mais poderosas, que CPD, das máquinas mais poderosas, que tendem a estar sempre sobrecarregadas, tendem a estar sempre sobrecarregadas, enquanto outras menos poderosas estão enquanto outras menos poderosas estão livres.livres.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE DE CARGA.CARGA.• A distribuição de carga é essencial A distribuição de carga é essencial

para o uso eficiente de processadores para o uso eficiente de processadores em ambientes computacionais em ambientes computacionais distribuídos e paralelos, onde existe distribuídos e paralelos, onde existe compartilhamento de recursos.compartilhamento de recursos.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)• O PROBLEMA DA ESCOLHA DO BAR:

•A decisão de ir a um bar é um processo estocástico, mas a decisão de qual bar, é uma decisão autônoma da pessoa.

•A priori não existe nenhuma relação entre a pessoa e os bares disponíveis.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)• Baseado na teoria da Aprendizagem Reforçada, os agentes de tomada de decisão agem em um padrão puramente local. Desta forma, um agente só saberá quão eficiente é o serviço em um restaurante depois que ele o escolher como um lugar para comer.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)• Um job pode rodar em qualquer recurso, não existe limite no número de job’s servidos simultaneamente por um dado recurso, portanto não ocorre fila.

•No entanto, a qualidade do serviço fornecido pelo recurso em um dado tempo, deteriora com o número de agentes que o usam naquele tempo.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)

•REGRAS DE SELEÇÃO DE RECURSO:

•É o coração desta discussão e se baseará em informações puramente locais.

•Depois que cada agente executa um job, ele guarda o nome do recurso R, os tempos Tstart e T stop da execução e o tamanho do job S.

•Entrada de SR (R,T1,T2,S).


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)•Cada agente A, condensa suas informações de execução de job’s dentro de um vetor chamado ESTIMADOR DE EFICIÊNCIA e denotado por eeA.

•O tamanho do vetor é o número de recursos, e a i-éssima entrada no vetor representa a avaliação do agente da eficiência corrente do recurso i.

•Existe também um vetor jdA, com o número de job’s completados, submetidos por A, em cada um dos recursos, desde o início do tempo.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)•ATUALIZANDO O ESTIMADOR DE EFICIÊNCIA:

•eeA(R) := WT + (1-W)eeA(R)

•onde:

•T = (t2 - t1)/S

•W = w + (1 - w)/jdA(R)



•SELECIONANDO O RECURSO:

0 ) ( se ) ( { : ) ( ' R A n A Ajd R ee R pd

0 (R)jd se ]E[ee A-nA •onde:

•n : valor real positivo

•E[eeA] :média dos valores de eeA(R) para todos os recursos, quando jdA(R)>o



•SELECIONANDO O RECURSO:

•O valor de n definirá o recurso. Quando o n é muito alto, n>=20, o agente sempre escolherá o recurso com os melhores registros.

•No entanto, a técnica de sempre escolher os melhores resultados, nem sempre é a mais adequada, pois impede o agente de se aproveitar das melhorias na capacidade ou carga de outros recursos.



•BCSR X Regra de Aprendizagem com Baixo n:

•As regras de aprendizagem selecionam recursos que não obtiveram melhores resultados no passado. Visto que o ambiente é dinâmico e os outros recursos podem ter melhorado sua performance no decorrer do tempo.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)•Exemplos:

•Dois recursos R1 e R2, com capacidades fixas, R1 = 2R2.

•Usando BCSR:

•R1

•R2

•CARGA BAIXA •CARGA ALTA•AGENTES ESCOLHEM R1

•AGENTES PREFEREM R2.



•Exemplos:

•Usando BCSR:

•R1

•R2

•CARGA BAIXA •CARGA ALTA •CARGA BAIXA

•AGENTES• ESCOLHEM r1

•AGENTES •ESCOLHEM R2

•CONTINUAM COM R2



•BCSR nem sempre é uma boa escolha;

•As mudanças de carga são imprevisíveis;

•Os agentes devem se adaptar as mudanças, que podem ser mudanças de carga ou mudanças na capacidade dos recursos.


ANALISANDO ANALISANDO BALANCEAMENTOBALANCEAMENTO DE CARGA DE CARGA (cont.)(cont.)•ANALISANDO CASOS:

•1- CARGA FIXA:

•Regras de seleção não adaptativas são satisfatórias;

•2-MUDANDO A CARGA/CAPACIDADES:

•A performance melhora quanto maior é a exploração que se faz dos recursos, ficando melhor quando o agente atualiza os estimadores de eficiência, de outra forma, o custo da atividade de exploração será maior que o ganho.


CONTRACT NET CONTRACT NET PROTOCOL - PROTOCOL -

CNP.CNP.• É um protocoloÉ um protocolo para alocação de tarefas, para alocação de tarefas, efetivado através de contratos.efetivado através de contratos.

• Um contrato é um acordo explícito Um contrato é um acordo explícito entre um agente que gera uma tarefa - entre um agente que gera uma tarefa - o gerente e um agente disposto a o gerente e um agente disposto a executar a tarefa - o contratado.executar a tarefa - o contratado.

• Um agente pode ter as duas funções.Um agente pode ter as duas funções.


CNP (cont.)CNP (cont.)

• O PROCESSO DE NEGOCIAÇÃO:O PROCESSO DE NEGOCIAÇÃO:

• PASSO 1:PASSO 1:

•AGENTE 1 RECEBE UMA TAREFA PARA EXECUTAR.




• PASSO 2: PASSO 2: ANUNCIANDO.ANUNCIANDO.

•AG.1 GERENTE

•AG.2•AG.3

•AG.4•AG.5




• PASSO 3 : PASSO 3 : OFERTAS.OFERTAS.

•AG.1 GERENTE

•AG.2•AG.3

•AG.4•AG.5




• PASSO 4 : PASSO 4 : ESCOLHER VENCEDOR.ESCOLHER VENCEDOR.

•AG.1 GERENTE

•AG.2•AG.3

•AG.4•AG.5


CNP (cont.)CNP (cont.)• PROBLEMAS:PROBLEMAS:

– Não detecta nem resolve conflitos;Não detecta nem resolve conflitos;

– O gerente não informa os ofertadores que O gerente não informa os ofertadores que foram recusados;foram recusados;

– Agentes não podem recusar ofertas;Agentes não podem recusar ofertas;

– Tarefas com tempo crítico não podem ser Tarefas com tempo crítico não podem ser atendidas;atendidas;

– Gera intensa comunicação.Gera intensa comunicação.


CNP (cont.)CNP (cont.)• VANTAGENS:VANTAGENS:

– Agentes podem fazer ofertas para Agentes podem fazer ofertas para múltiplas tarefas;múltiplas tarefas;

– Fornece um balanceamento de carga Fornece um balanceamento de carga natural.natural.


CNP (cont.)CNP (cont.)• O PROBLEMA DA CONFIANÇA:O PROBLEMA DA CONFIANÇA:

– Em negociações mútuas entre agentes, Em negociações mútuas entre agentes, deve existir confiança entre eles, no deve existir confiança entre eles, no que se refere ao serviço oferecido.que se refere ao serviço oferecido.


CNP (cont.)CNP (cont.)• PROBLEMA DO CONGESTIONAMENTO:PROBLEMA DO CONGESTIONAMENTO:

– Destinatário Focalizado:Destinatário Focalizado:• Alta Carga: Agentes com recursos livres, Alta Carga: Agentes com recursos livres,

anunciam sua disponibilidade;anunciam sua disponibilidade;

• Baixa Carga: Agentes com tarefas, anunciam Baixa Carga: Agentes com tarefas, anunciam suas tarefas.suas tarefas.

– Restringindo o Público:Restringindo o Público:• Agentes anunciam apenas para um Agentes anunciam apenas para um

subconjunto de agentes.subconjunto de agentes.


UMA APLICAÇÃO DO CNPUMA APLICAÇÃO DO CNP• • TRACONET - TRAnsportation Cooperation TRACONET - TRAnsportation Cooperation NETNET

É um sistema de roteamento de veículos de É um sistema de roteamento de veículos de transporte, baseado no custo marginal.transporte, baseado no custo marginal.

- Agentes localmente calculam seu custo marginal - Agentes localmente calculam seu custo marginal para executar um conjunto de tarefas.para executar um conjunto de tarefas.

- A escolha do contratador é baseada unicamente - A escolha do contratador é baseada unicamente neste custo.neste custo.

- Atributos do veículo são avaliados.- Atributos do veículo são avaliados.


CONCLUSÃO:CONCLUSÃO:

•Para maior produtividade de ambientes multi-recursos é essencial a distribuição de cargas de trabalho entre os diversos recursos, de forma equilibrada, sem sobregarregar nem subcarregar nenhum dos recursos.


REFERÊNCIAS:REFERÊNCIAS:• 1. Schaerf. Andrea, Shoham.Yoav, 1. Schaerf. Andrea, Shoham.Yoav,

Tennenholtz.Moshe. Adaptive Load Balancing: A Tennenholtz.Moshe. Adaptive Load Balancing: A Study in Multi-Agent Learning. Journal of Artificial Study in Multi-Agent Learning. Journal of Artificial Intelligence Research (1995).Intelligence Research (1995).

• 2. Jenninngs.Nicholas, Sycara.Katia, 2. Jenninngs.Nicholas, Sycara.Katia, Wooldrige.Michael. A Roadmap of Agent Research Wooldrige.Michael. A Roadmap of Agent Research and Development.and Development.

• 3.Kraus.Sarit. An Overview of Incentive Contracting3.Kraus.Sarit. An Overview of Incentive Contracting

• 4. Sandholm.Tuomas.An Implementation of the 4. Sandholm.Tuomas.An Implementation of the Contact Net Protocol Based on Marginal Cost Contact Net Protocol Based on Marginal Cost Calculation.Calculation.


REFERÊNCIAS (cont.):REFERÊNCIAS (cont.):• 5. Sandholm.Tuomas, Lesser.Victor. Issues in 5. Sandholm.Tuomas, Lesser.Victor. Issues in

Automated Negociation and Eletronic Automated Negociation and Eletronic Commerce: Extending the Contract Net Commerce: Extending the Contract Net Framework.Framework.

Documents

Francimary P.Garcia [email protected] Agentes para Balanceamento de Carga e Alocação de Tarefas em Sistemas Distribuídos