Agentes para Balanceamento de
Carga e Alocação de Tarefas em
Sistemas Distribuídos.
Francimary P.Garcia [email protected]
•Roteiro
•
MOTIVAÇÃO.
•
ANALISANDO BALANCEAMENTO DE CARGA.
•
CONTRACT NET PROTOCOL.
•
UMA APLICAÇÃO DO CNP.
•
CONCLUSÃO.
Francimary P.Garcia [email protected]
MOTIVAÇÃO:
• Muitos são os problemas causados por
distribuições de cargas não balanceadas em
situações reais de nossa vida, como por
exemplo, o transito intenso em algumas
ruas, ou a alta utilização, em um CPD, das
máquinas mais poderosas, que tendem a
estar sempre sobrecarregadas, enquanto
outras menos poderosas estão livres.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA.
• A distribuição de carga é essencial para o
uso eficiente de processadores em
ambientes computacionais distribuídos e
paralelos, onde existe compartilhamento
de recursos.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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).
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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)
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•SELECIONANDO O RECURSO:
A
pd ' ( R) : {ee A( R)n se
E[ee A ]-n
se
jd A( R)  0
jd A (R)  0
•onde:
•n : valor real positivo
•E[eeA] :média dos valores de eeA(R)
para todos os recursos, quando jdA(R)>o
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•Exemplos:
•Dois recursos R1 e R2, com capacidades
fixas, R1 = 2R2.
•Usando BCSR:
•CARGA BAIXA
•R1
•CARGA ALTA
•AGENTES ESCOLHEM R1
•R2
Francimary P.Garcia [email protected]
•AGENTES PREFEREM R2.
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•Exemplos:
•Usando BCSR:
•CARGA BAIXA
•R1
•CARGA ALTA
•CARGA BAIXA
•AGENTES
•ESCOLHEM R2
•CONTINUAM COM R2
•AGENTES
• ESCOLHEM r1
•R2
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (cont.)
•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.
Francimary P.Garcia [email protected]
ANALISANDO BALANCEAMENTO
DE CARGA (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.
Francimary P.Garcia [email protected]
CONTRACT NET PROTOCOL CNP.
• É um protocolo para alocação de tarefas,
efetivado através de contratos.
• Um contrato é um acordo explícito entre um
agente que gera uma tarefa - o gerente e um
agente disposto a executar a tarefa - o
contratado.
• Um agente pode ter as duas funções.
Francimary P.Garcia [email protected]
CNP (cont.)
• O PROCESSO DE NEGOCIAÇÃO:
• PASSO 1:
•AGENTE 1 RECEBE
UMA TAREFA PARA
EXECUTAR.
Francimary P.Garcia [email protected]
CNP (cont.)
• O PROCESSO DE NEGOCIAÇÃO:
• PASSO 2:
ANUNCIANDO.
•AG.3
•AG.2
•AG.1 GERENTE
•AG.4
Francimary P.Garcia [email protected]
•AG.5
CNP (cont.)
• O PROCESSO DE NEGOCIAÇÃO:
• PASSO 3 :
OFERTAS.
•AG.3
•AG.2
•AG.1 GERENTE
•AG.4
Francimary P.Garcia [email protected]
•AG.5
CNP (cont.)
• O PROCESSO DE NEGOCIAÇÃO:
• PASSO 4 :
ESCOLHER VENCEDOR.
•AG.3
•AG.2
•AG.1 GERENTE
•AG.4
Francimary P.Garcia [email protected]
•AG.5
CNP (cont.)
• PROBLEMAS:
– Não detecta nem resolve conflitos;
– O gerente não informa os ofertadores que foram
recusados;
– Agentes não podem recusar ofertas;
– Tarefas com tempo crítico não podem ser
atendidas;
– Gera intensa comunicação.
Francimary P.Garcia [email protected]
CNP (cont.)
• VANTAGENS:
– Agentes podem fazer ofertas para múltiplas
tarefas;
– Fornece um balanceamento de carga natural.
Francimary P.Garcia [email protected]
CNP (cont.)
• O PROBLEMA DA CONFIANÇA:
– Em negociações mútuas entre agentes, deve
existir confiança entre eles, no que se refere
ao serviço oferecido.
Francimary P.Garcia [email protected]
CNP (cont.)
• PROBLEMA DO CONGESTIONAMENTO:
– Destinatário Focalizado:
• Alta Carga: Agentes com recursos livres,
anunciam sua disponibilidade;
• Baixa Carga: Agentes com tarefas, anunciam
suas tarefas.
– Restringindo o Público:
• Agentes anunciam apenas para um
subconjunto de agentes.
Francimary P.Garcia [email protected]
UMA APLICAÇÃO DO CNP
• TRACONET - TRAnsportation Cooperation
NET
É um sistema de roteamento de veículos de
transporte, baseado no custo marginal.
- Agentes localmente calculam seu custo
marginal para executar um conjunto de tarefas.
- A escolha do contratador é baseada
unicamente neste custo.
- Atributos do veículo são avaliados.
Francimary P.Garcia [email protected]
CONCLUSÃO:
•Para maior produtividade de ambientes multirecursos é essencial a distribuição de cargas
de trabalho entre os diversos recursos, de
forma equilibrada, sem sobregarregar nem
subcarregar nenhum dos recursos.
Francimary P.Garcia [email protected]
REFERÊNCIAS:
• 1. Schaerf. Andrea, Shoham.Yoav,
Tennenholtz.Moshe. Adaptive Load Balancing: A
Study in Multi-Agent Learning. Journal of Artificial
Intelligence Research (1995).
• 2. Jenninngs.Nicholas, Sycara.Katia,
Wooldrige.Michael. A Roadmap of Agent Research
and Development.
• 3.Kraus.Sarit. An Overview of Incentive Contracting
• 4. Sandholm.Tuomas.An Implementation of the
Contact Net Protocol Based on Marginal Cost
Calculation.
Francimary P.Garcia [email protected]
REFERÊNCIAS (cont.):
• 5. Sandholm.Tuomas, Lesser.Victor. Issues in
Automated Negociation and Eletronic Commerce:
Extending the Contract Net Framework.
Francimary P.Garcia [email protected]