1 / 90 Lidando com recursos escassos e heterogêneos em um sistema distribuído atuando como servidor de MMOG Carlos Eduardo Benevides BezerraDefesa de Mestrado

1 / 90

Lidando com recursos escassos e heterogêneos em um sistema distribuído atuando como servidor de MMOG

Carlos Eduardo Benevides Bezerra Defesa de Mestrado

Lidando com recursos escassos e heterogêneos em um sistema distribuído

atuando como servidor de MMOG

Carlos Eduardo Benevides BezerraOrientador: Prof. Dr. Cláudio F. R. Geyer

Dissertação de Mestrado

Porto Alegre, 3 de março de 2009

paralela e

2 / 90



Sumário

Introdução Jogos multijogador Jogos online maciçamente multijogador (MMOGs) Objetivos

Trabalhos Relacionados Distribuição da infra-estrutura de suporte ao MMOG Gerenciamento de interesse Balanceamento de carga

Modelo Base A³: Um Algoritmo de Otimização por Área de Interesse

Utilização de diferentes graus de interesse em uma ADI O Algoritmo A³ Simulações e resultados

Balanceamento de Carga Definições e mapeamento para grafo Algoritmos propostos (ProGReGA, ProGReGA-KH, ProGReGA-KF e BFBCT)

Considerações Finais

3 / 90



Introdução:Jogos multijogador, MMOGs e Objetivos

4 / 90



Introdução: Jogos multijogador

Popularização dos jogos eletrônicos e de computador Consoles: Atari, Master System, Mega Drive, Super Nintendo, PlayStation, Wii

etc. Possibilidade da interação entre jogadores: opção de multijogador, ou

multiplayer Participantes jogando simultaneamente no mesmo console:

até 4 (Nintendo GameCube, Nintendo 64, Wii e outros...) até 8 (Playstation)

Com computadores em rede, a depender do jogo: até 8 (Age of Empires, Diablo II) até 16 (Unreal Tournament) até 32 (Counter-Strike) até 64 (Unreal Tournament III)

5 / 90



Introdução: Jogos multijogador

Nintendo Wii

Counter-Strike

6 / 90



Introdução: MMOGs

Popularização de conexões de banda larga à Internet Número crescente de jogadores online + velocidade e + jogadores: MMOGs

Lineage II (NCSoft, 2003) EVE Online (CCP, 2003) World of Warcraft (Blizzard, 2004) Cabal Online (ESTsoft, 2008)

Permitem a interação simultânea de um grande número de jogadores (Chen; Muntz, 2006): Dezenas a centenas de milhares de

jogadores ao mesmo tempo

7 / 90



Introdução: MMOGsLineage II

8 / 90



Introdução: MMOGsEVE Online

9 / 90



Introdução: MMOGsWorld of Warcraft

10 / 90



Introdução: MMOGsCabal Online

11 / 90



Introdução: MMOGs

Partidas muito longas Travian: MMORTS, com partidas durando de seis meses a um ano World of Warcraft: MMORPG, sem momento determinado para

acabar a partida Mundos vastos e populosos Passagem do tempo independe do jogador Estado persistente, mudando constantemente

O jogador pode sair e voltar para continuar de onde parou Porém, o estado do mundo será diferente de quando ele saiu

12 / 90



Introdução: MMOGs

Jogos baseados em avatar Os MMOGs mais comuns, os de RPG (MMORPGS), são baseados em avatar

Avatar é um personagem que representa o jogador no ambiente virtual do jogo

O avatar executa as ações determinadas pelo jogador O jogador envia comandos ao avatar, que interage com o ambiente virtual e

com avatares de outros jogadores As ações executadas pelo avatar irão mudar o estado do jogo, interferindo no

seu andamento As ações de um jogador modificam o estado do jogo

Os outros jogadores devem ser notificados dessa mudança Outras mudanças de estado (passagem do tempo, criação/destruição de

objeto) também devem ser avisadas aos jogadores envolvidos

13 / 90



Introdução: MMOGs

Geralmente, utiliza-se um servidor central Recebe os comandos dos jogadores e os processa Modifica o estado do jogo com base nessas ações Devolve o estado resultante aos jogadores envolvidos

A manutenção desse servidor é muito cara: Geralmente, usa-se um cluster para suprir a demanda por

processamento O cluster conecta-se à Internet com uma conexão de alguns GBps

(Feng, 2007) Existe um requisito temporal quanto ao limite de atraso de envio

do estado para os jogadores Alternativa: abordagens descentralizadas

14 / 90



Introdução: Objetivos

Propor um modelo descentralizado de suporte a MMOGs Abordagem escolhida: servidor geograficamente distribuído

Tornar mais viável o uso de um servidor geograficamente distribuído formado por nodos de baixo custo: Criar um algoritmo que reduza o uso de largura de banda pelos

nodos servidores; Criar um esquema de balanceamento dinâmico de carga, que

considere a heterogeneidade dos servidores e que reduza o overhead inerente à distribuição

15 / 90



Trabalhos Relacionados:Suporte distribuído para MMOGs,

Gerenciamento de Interesse eBalanceamento de Carga

16 / 90



Trabalhos Relacionados: Suporte distribuído para MMOGs

Modelo cliente-servidor: Alto nível de controle sobre o sistema como um todo Facilita autenticação, persistência e segurança Custa caro É um gargalo e também um ponto único de falha

Para reduzir o custo de manter um servidor central, há algumas alternativas: Arquiteturas par-a-par completamente descentralizadas Arquiteturas híbridas (par-a-par e cliente-servidor) Arquiteturas de servidor distribuído

17 / 90



Trabalhos Relacionados: Arquiteturas P2P completamente descentralizadas

As ações são processadas nos computadores dos próprios jogadores

Cada par processa suas próprias ações e envia o estado resultante aos outros Complexidade de mensagens: O(n²) Provável saturação da banda de upload dos pares Na abordagem tradicional, cada cliente enviava suas ações,

apenas ao servidor É necessário:

Manter o estado do jogo consistente Distribuir o armazenamento e recuperação do estado do jogo

18 / 90




• Em (Schiele et al., 2007), buscou-se tornar mais escaláveis MMOGs sobre esse tipo de suporte

• É proposto pelos autores divisão do ambiente virtual em regiões– Cada região funciona como um jogo

independente e menor– Os pares responsáveis por avatares em

uma mesma região formam uma pequena rede P2P

– Em cada região, os pares ali presentes decidem entre eles o andamento do jogo

– Ao mover-se de uma região para outra, o par saiu do grupo P2P da região antiga e ingressa na rede P2P da nova região

– Alguns pares de um grupo mantém conexões com pares de regiões vizinhas, para trocar informações necessárias

(Schiele et al., 2007)

19 / 90




• Cada região possui um coordenador, eleito dentre os pares

• A função do coordenador é decidir para quem cada atualização de estado é relevante– Ele não faz o envio, apenas notifica

cada par de para quem deve enviar• Problemas:– É necessário que o coordenador

seja confiável– Mesmo com o coordenador, cada

um dos N pares ainda teria que fazer N envios, no pior caso

(Schiele et al., 2007)

20 / 90



Trabalhos Relacionados: Arquiteturas híbridas (par-a-par e cliente-servidor)

As ações podem ser processadas nos computadores dos próprios jogadores ou em um servidor

É definido um critério para determinar quem processará as ações dos jogadores em determinada situação, por ex.:

Tipo de ações executadas Sobrecarga do servidor Sobrecarga dos pares Etc.

Embora haja um servidor central, seu custo de manutenção é reduzido de maneira significativa

Permite controle central do jogo, até certo ponto Mais do que na abordagem completamente descentralizada Menos do que na tradicional (cliente-servidor)

21 / 90




• Em (Vilanova et al., 2008), o mundo do jogo é dividido em espaço social e espaços de ação:– Social: voltado para interações sociais,

como conversar, trocar objetos do jogo, formar grupos etc.

– de Ação: lutar contra monstros, duelar etc.• O espaço social é controlado pelo

servidor• Os jogadores devem requisitar ao

servidor para que seja criado um espaço de ação

• Para cada espaço de ação é formado um grupo P2P

• Cada espaço de ação é gerenciado pelo servidor, embora a simulação seja executada pelos pares

(Vilanova et al., 2008)

22 / 90




• Os espaços de ação permitem interações mais rápidas e com pouca tolerância a atraso, como lutas

• Cada espaço de ação é uma instância do jogo, isolada, com número limitado de participantes

• Os jogadores do espaço de ação formam uma rede P2P entre eles– Cada par é responsável por atualizar os outros– Cada par processa suas próprias ações

• Um par eleito como super-peer– Ordena eventos “fortemente acoplados” para

resolver alguns tipos de inconsistência no estado do jogo

• Problemas:– Não é possível interações de luta entre

mais que algumas dezenas de jogadores– Super-peer precisa ser confiável

(Vilanova et al., 2008)

23 / 90




• Em (Chen; Muntz, 2006), o ambiente virtual é dividido em regiões– Cada região gerenciada por um par, que

atua como sub-servidor– O gerenciador recebe as ações dos pares

de sua região, processa-as e devolve o resultado

• Cada gerenciador pode dispor de reservas– Cada gerenciador encaminha as ações

recebidas dos jogadores a seus reservas– Os reservas processam essas ações,

mantendo uma réplica do estado do jogo e verificando a simulação

– Em caso de colapso do gerenciador, um dos reservas pode assumir a região

• Caso o gerenciador fique sobrecarregado, o servidor assume parte da carga daquela região

(Chen; Muntz, 2006)

24 / 90




• Problemas:– Não há garantias de que o par

eleito como gerenciador é confiável

– Também não há garantias de que ele estará disponível sempre que necessário

– As ações dos jogadores são encaminhadas pelo gerenciador aos seus reservas: podem ser corrompidas

(Chen; Muntz, 2006)

25 / 90




• No FreeMMG (Cecin et al., 2004), o ambiente virtual é dividido em segmentos– Em um mesmo segmentos, os jogadores se

comunicam diretamente, par-a-par– Entre segmentos diferentes, a

comunicação é intermediada pelo servidor• Para verificar a simulação em um

segmento, cada par envia o estado resultante para o servidor– Um par aleatório é inserido no segmento

para evitar trapaças de conluio• Problemas:

– Não há garantias de que a abordagem probabilística para impedir trapaça de conluio irá funcionar

– O modelo é mais voltado para MMORTS

(Cecin et al., 2004)

26 / 90



Trabalhos Relacionados: Arquiteturas de servidor distribuído

Permite utilizar nodos de menor custo

Mantém controle sobre o jogo Separação clara entre quem pode processar as ações do jogo e enviar

atualizações de estado e quem não pode No entanto, é necessário lidar com vários nodos servidores

São necessários mecanismos de sincronização entre os servidores e de balanceamento de carga

As propostas existentes tendem a considerar um sistema servidor instalado em uma rede local, com pouco atraso e alta velocidade

27 / 90



Trabalhos Relacionados: Arquiteturas de servidor distribuído

• Em (Assiotis; Tzanov, 2006), o ambiente virtual é dividido em regiões:– A cada região é atribuído um nodo servidor

• A cada objeto ou entidade no jogo, é atribuída uma trava– Para que um servidor possa alterar o estado de

alguma entidade do jogo, é necessário obter uma trava

• Para atacar o problema de haver aglomerados de jogadores, propõe-se reparticionamentos recursivos do ambiente virtual– A cada nova partição é atribuída um nodo

servidor diferente

• Problemas:– Existe um limite prático para o

reparticionamento de regiões– Considera-se o servidor em uma rede local de

alta velocidade e pouco atraso

(Assiotis; Tzanov, 2006)

28 / 90



Trabalhos Relacionados: Gerenciamento de interesse

Permite determinar o interesse dos jogadores em apenas um subconjunto das informações disponíveis

Reduz-se o número de mensagens, enviando apenas o que é relevante Uma expressão do interesse de um jogador é chamada de área de

interesse - ADI Quase sempre associada à localização de seu avatar em relação aos de outros

jogadores Uma ADI é um subespaço do ambiente virtual

(Rak; Van Hook, 1996): grupos de multicast associados a células do ambiente virtual

Cada participante se subscreve no grupo da sua célula e das vizinhas (Zou; Ammar; Diot, 2001): comparação entre grupos de multicast por

célula e por objeto Tradeoff entre mensagens de atualização de estado e de controle de grupo

29 / 90



Trabalhos Relacionados: Gerenciamento de interesse

(Morgan; Lu; Storey, 2005): predição do que será relevante para um jogador no futuro

Utiliza parâmetros como posição e vetor velocidade Pouco antes de precisar de um estado, o jogador já o obtém

(Morse et al., 1996): taxonomia de sistemas de gerenciamento de interesse Modelo unicast, multicast ou broadcast Filtragem por características intrínsecas ou extrínsecas Domínio de responsabilidade dinâmico ou estático

Como multicast não é amplamente suportado na Internet (El-Sayed, 2004), optou-se aqui pelo modelo unicast

Além disso, com filtragem intrínseca e domínios de responsabilidade dinâmicos

30 / 90



Trabalhos Relacionados: Balanceamento de carga

• A carga em um MMOG está fortemente relacionada à localização dos avatares dos jogadores– São suas ações que devem ser

processadas– Devem ser enviadas atualizações de

estado de objetos próximos ao avatar do jogador

• Agrupam-se os jogadores de acordo com a localização de seus avatares– Divisão do ambiente virtual em células– O formato das células determina

quantos vizinhos cada uma terá – e quantos servidores vizinhos cada servidor terá

– A existência de células deve ser transparente ao jogador

31 / 90




• (De Vleeschauwer et al., 2005): macrocélulas e microcélulas

– Microcélulas são áreas fixas e de tamanho relativamente pequeno no ambiente virtual

– Macrocélulas são conjuntos de microcélulas

– Para transferir e balancear carga, microcélulas são delegadas a uma ou outra macrocélula, dinamicamente

– Cada macrocélula é atribuída a um servidor

– O número de vizinhos de cada servidor torna-se imprevisível, porém isso é compensado pela melhor distribuição da carga do jogo

(De Vleeschauwer et al., 2005)

32 / 90




• (Lee; Lee, 2003): balanceamento com informações locais

– Quando um servidor fica sobrecarregado, ele busca servidores vizinhos, e vizinhos dos vizinhos, para repartir sua carga

– É formado um conjunto de servidores tal que no final da redistribuição, nenhum deles esteja sobrecarregado

– Ao final da formação do conjunto, a carga é redistribuída entre eles

– Consegue-se realizar balanceamento apenas com informações locais e de vizinhos

• Considera-se como carga o número de avatares na região

• Não foi considerado o custo de comunicação entre servidores (rede local)

(Lee; Lee, 2003)

33 / 90




• Dependência entre tarefas causa necessidade de comunicação– Atraso do processamento como um

todo, aguardando o envio/recebimento de mensagens

– Ocupação do link de comunicação entre os processadores

• Uso de grafos em distribuição de tarefas– Vértice representa uma tarefa– Peso do vértice é o custo de

processamento– Aresta representa dependência

(comunicação) entre tarefas– Peso da aresta é o custo de

comunicação– Grafo de tarefas é particionado,

minimizando o corte de aresta– Cada partição é atribuída a um nodo de

processamento

34 / 90




• Problema NP-completo

• Heurísticas:

– Spectral Bisection: (Hendrickson; Leland, 1995)

– GGP: (Karypis; Kumar, 1999)

– Kernighan-Lin: (Kernighan; Lin, 1970)

– Fiduccia-Mattheyses: (Fiduccia; Mattheyses, 1982)

35 / 90



Modelo Base:Nodos servidores geograficamente distribuídos

36 / 90



Modelo Base: Conceitos

Conceitos Ambiente virtual interativo distribuído

Ambiente virtual: “mundo” em que o jogo se passa Interativo: andamento do jogo depende das ações dos jogadores Distribuído: é representado e processado em vários locais (servidor e jogadores)

Entidade: qualquer objeto no ambiente virtual que possua localização, orientação e velocidade

Avatar: entidade que é a representação virtual do participante no mundo do jogo Ação: comando enviado pelo jogador, como mover seu avatar para determinada

posição, atacar, apanhar um objeto etc. Simulação: refere-se ao cálculo do novo estado do ambiente virtual do jogo, baseado

nas ações dos jogadores, em quanto tempo se passou, e no estado anterior Estado: conjunto de valores dos atributos das diferentes entidades do jogo Região: partição do ambiente virtual (geralmente é um espaço contíguo) Fronteira: divisa entre duas regiões

37 / 90



Modelo Base: Proposta

Modelo de distribuição baseado em nodos de baixo custo geograficamente distribuídos

Cada nodo tem recursos um pouco acima de um computador médio, mas bem abaixo de um grande servidor empresarial

Dividir o ambiente virtual do jogo em regiões

Distribuir as regiões entre os nodos servidores

38 / 90



Modelo Base: Proposta

• A cada servidor está associada uma região– O ambiente é contíguo e a divisão em

regiões é transparente aos jogadores

• Na topologia da rede overlay, são adjacentes aqueles servidores associados a regiões vizinhas

• Cada jogador se conecta ao servidor associado à região onde seu avatar se encontra– Localidade dos avatares

• Os servidores se comunicam para possibilitar a interação entre jogadores em diferentes regiões– Troca de atualizações de estado

39 / 90



A³: Um algoritmo de otimização por área de interesse

40 / 90



A³: Introdução

Estado do jogo Cada participante deve ter uma cópia local Maneira mais simples seria enviar cada alteração de estado a todos os participantes

Gerenciamento de interesse Algumas entidades podem ser irrelevantes para um jogador O critério mais utilizado é o da distância entre o avatar e a entidade Tráfego no servidor e clientes é reduzido

Servidores comportarão mais jogadores Clientes terão menor requisito de banda disponível

O estado torna-se incompleto para cada jogador, porém isto não é perceptível

É necessário calcular o interesse de cada jogador, em relação a todas as entidades presentes no jogo

Geralmente, com base na distância

41 / 90



A³: Introdução

• Algoritmos convencionais para gerenciamento de interesse:– Área de interesse circular– Área de interesse baseada em

campo de visão

• Área de interesse circular– Sendo uma das formas mais

simples de uma ADI, verifica-se apenas se a entidade está a menos que uma certa distância menor que o alcance de visão do avatar

– Se estiver, o jogador recebe atualizações de estado daquela entidade

– Caso contrário, não recebe

42 / 90



A³: Introdução

• Área de interesse baseada em campo de visão– Refinamento da área circular,

levando em conta o vetor direção do avatar

– Tem como princípio que o jogador só pode vero que está à frente do seu avatar

– Consiste em um setor de círculo, que dependerá da orientação do avatar

– Com um campo de visão de 180°, reduz-se em 50% o tráfego, em média

– Um problema é a não atualização de entidades que estejam atrás do avatar

43 / 90



A³: Visão geral

• Objetivo:– Reduzir o uso de largura de banda de

upload dos servidores

• Motivação:– Geralmente, a banda de upload é

significativamente inferior à de download

• Princípio:– Em um ambiente com muitas

entidades, alguma destas têm menor relevância para o jogador em questão

– Entidades com menor relevância podem ser atualizadas com uma freqüência menor

– A distância euclidiana das entidades no ambiente virtual é um possível critério para definir o valor desta relevância

– Quanto menor a relevância de uma entidade para um jogador, menor sua freqüência de atualização pra ele

44 / 90



A³: Área de interesse com área próxima

45 / 90



A³: Parâmetros

• Intervalo normal de atualização (IN)– Menor intervalo de tempo entre

duas atualizações de estado consecutivas de uma entidade

• Alcance de visão (V)– Distância até a qual uma entidade

pode estar de um avatar para que ela seja visível

• Distância crítica (C)– Distância dentro da qual qualquer

entidade tem relevância máxima para um determinado jogador

• Coordenadas do avatar (A) e da entidade em questão (E)

46 / 90



A³: Retorno

Relevância (R) Valor real x, x [0, 1]. Representa o quanto uma certa

entidade E é relevante para o avatar A.

Intervalo até a próxima atualização: IP = IN / R

Exemplo: IN = 200 ms Distância implica em R = 0,8 IP = 200 / 0,8 = 250 ms

47 / 90



A³: O algoritmo

48 / 90



A³: Simulações

Simulador utilizado: ns-2

Foi simulado um ambiente bidimensional, com diversos avatares se movendo segundo o modelo de random waypoint

ADIs simuladas:

Sem ADI

Circular

Campo de visão

Circular com relevância graduada

A³

Parâmetros da simulação:

Intervalo normal de atualização: 250 ms

Tamanho do estado de uma única entidade: 100 bytes

Duração de cada sessão de jogo simulada: 20 min.

Área do ambiente virtual: 750 x 750 u.a.

Alcance da visão: 120 u.c.

Distância crítica: 40 u.c.

Ângulo de visão: 180°

49 / 90



A³: Resultados

Publicado no 12th IEEE International Symposium onDistributed Simulation and Real Time Applications

(DS-RT 2008)

50 / 90



Balanceamento de Carga: Um esquema dinâmico para alocação de carga

proporcional aos recursos de cada servidor

51 / 90



Balanceamento de Carga: Introdução

Grande número de jogadores nos MMOGs

O servidor intermedia as interações dos jogadores Recebe ações dos jogadores Envia o estado dos avatares e de outras entidades Tráfego intenso no servidor

Em um servidor distribuído, é necessário repartir a carga de comunicação

Sistema heterogêneo: distribuição proporcional aos recursos de cada nodo servidor

Algumas abordagens, como (Lee; Lee, 2003), definem a carga como o número de jogadores conectados ao servidor

Não funciona, pois deve-se considerar como esses jogadores estão interagindo

52 / 90




Os jogadores podem mover-se livremente em um ambiente vasto Possível existência de pontos de interesse (hotspots) Geralmente, há lugares como cidades e calabouços com tesouros no ambiente

virtual

O tráfego no servidor pode crescer quadraticamente, no pior caso Quando os jogadores estão distantes, o tráfego no servidor cresce linearmente Porém, quando os jogadores estão próximos, o tráfego cresce

quadraticamente

A carga a considerar deve ser o tráfego causado pelos jogadores O tráfego gerado depende do que é relevante para cada avatar

53 / 90




54 / 90




Crescimento lineardo tráfego

Crescimento quadráticodo tráfego

55 / 90




• Distribuição em regiões do ambiente virtual– Existem fronteiras entre as regiões

• Tráfego adicional (overhead)– Se dois jogador interagirem enquanto

conectados a servidores diferentes, estes também precisarão trocar mensagens

– Para que o estado de um jogador chegue ao outro, deve passar primeiro pelos dois servidores

• Para eliminar o overhead, o ideal seria todos os jogadores conectarem-se ao mesmo servidor– Sobrecarga do servidor: problema

inicial

• Solução: definir um critério para distribuir os jogadores de modo que se reduza o overhead

56 / 90



Balanceamento de Carga: Proposta

Esquema proposto:

Dividir o ambiente virtual em células de tamanho e posição fixos

Formar regiões como agrupamentos de células Células podem ser transferidas dinamicamente entre regiões Tratar de maneira relativamente simples a mobilidade dos avatares

Cada região gerencia uma, e apenas uma, região Se o servidor estiver ocioso, sua região é vazia (não contém células)

Balanceamento local Servidor sobrecarregado busca servidores de regiões próximas à sua para que

possam receber algumas células

Carga considerada Uso de largura de banda de envio

57 / 90



Balanceamento de Carga: Definições

Carga de um avatar: largura de banda utilizada pelo servidor para lhe enviar atualizações de estado

Depende da relevância de outras entidades em relação a ele

Carga de uma célula: soma das cargas dos avatares presentes nela

Interação entre células: tráfego de mensagens entre jogadores com avatares em células diferentes

Carga de uma região: soma das cargas das células que a compõem

Carga total do jogo: soma das cargas de todas as células que compõem todo o ambiente virtual

Capacidade do servidor: largura de banda de envio do servidor

Capacidade do sistema: soma da capacidade de todos os servidores do sistema

Uso de recursos do servidor: carga da região / capacidade do servidor

Uso total do sistema: capacidade do sistema / carga total do jogo

Overhead: tráfego adicional causado pela interação entre jogadores em servidores diferentes

58 / 90



Balanceamento de Carga: Mapeamento em grafo

• Vértice: representa uma célula do ambiente virtual

• Aresta: liga dois vértices que representam células adjacentes

• Partição: conjunto de vértices que representa uma região do ambiente virtual

• Peso do vértice: carga da célula que representa

• Peso da aresta: interação entre as células

• Peso da partição: soma do peso de seus vértices

• Corte de aresta: soma dos pesos das arestas que ligam vértices de partições diferentes– É proporcional ao overhead

59 / 90



Balanceamento de Carga: Esquema

O balanceamento de carga proposto se divide em 3 fases: Fase 1: seleção de regiões (e seus servidores) para

participarem do balanceamento

Fase 2: transferência de células entre as regiões do conjunto formado na fase 1, balanceando a carga

Fase 3: refinamento da divisão, para reduzir o overhead

60 / 90



Balanceamento de Carga: Fase 1

Quando fica sobrecarregado, o servidor dispara o mecanismo de balanceamento

Considera-se que um servidor está sobrecarregado se: Uso de seus recursos > 100% (teoricamente)e Uso de seus recursos > Uso total do sistema

Se o sistema não tiver recursos suficientes, todos os nodos devem estar igualmente sobrecarregados

Os nodos devem, então adaptar a qualidade do jogo à disponibilidade de recursos

A partir da região do servidor que disparou o balanceamento, outras regiões vão sendo adicionadas

A fase 1 termina quando o uso médio de recursos dos servidores das regiões selecionadas é menor que 100% ou menor que o uso total do sistema

61 / 90




62 / 90




Recebe como parâmetro o conjunto de regiões formado na fase 1

Essas regiões trocam células, de maneira a transferir a carga de servidores sobrecarregados para servidores ociosos

Aqui, propõem-se quatro algoritmos para a fase 2: ProGReGA ProGReGA-KH ProGReGA-KF BFBCT

63 / 90



Balanceamento de Carga: Fase 2 - ProGReGA

ProGReGA Libera todas as células de todas as regiões que estão participando

Ordena as regiões em ordem decrescente da capacidade do servidor de uma

Para cada região: Atribui a célula (livre) mais pesada A partir daí, busca células vizinhas que tenham a maior interação possível

(reduzindo o overhead) Se não houver mais células vizinhas livres, é atribuída à região a célula livre

mais pesada Quando a carga da região atinge a capacidade máxima do servidor, o algoritmo

passa para a próxima região

64 / 90



Balanceamento de Carga: Fase 2 - ProGReGA

65 / 90



Balanceamento de Carga: Fase 2 – ProGReGA (exemplo 1/9)

• Carga total = 32

• Capacidade de S1 = 30• Fração de cap. de S1 = 0,625• Parcela de peso de S1 = 0,625 x 32 = 20


66 / 90







67 / 90







68 / 90







69 / 90







70 / 90







71 / 90







72 / 90







73 / 90







74 / 90



Balanceamento de Carga: Fase 2 – Variações do ProGReGA

O PRoGReGA libera todas as células para depois redistribuí-las entre as regiões Uma região pode mudar completamente seu conjunto de células Jogadores que estão nessas células terão que migrar para o novo servidor O processo de migração de jogadores é custoso

PRoGReGA-KH Cada região mantém sua célula mais pesada As células que serão adicionadas serão vizinhas à célula que foi mantida A região tenderá a ter um conjunto de células semelhante ao que tinha antes

PRoGReGA-KF Cada região sobrecarregada vai eliminando suas células até que sua fração de carga seja

menor ou igual à fração de capacidade do servidor

Contudo, quanto mais células forem mantidas, mais se restringe o algoritmo, podendo resultar em regiões fragmentadas

75 / 90



Balanceamento de Carga: Fase 2 – ProGReGA-KH e ProGReGA-KF

76 / 90



Balanceamento de Carga: Fase 2 – BFBCT

BFBCT Considera apenas a carga das células, e não a interação entre elas

Transfere células da região sobrecarregada para regiões com recursos ociosos

Verifica as outras regiões, na ordem da mais carregada para a mais livre

Transfere a célula cuja carga seja a mais próxima da capacidade livre da região sendo verificada

A redução do overhead fica totalmente de lado Deixada para depois (fase 3)

77 / 90



Balanceamento de Carga: Fase 2 – BFBCT

78 / 90



Balanceamento de Carga: Fase 3 – Refinamento

Após ser feita a transferência de células entre as regiões

Troca pares de células de região, com os critérios: O overhead será reduzido O balanceamento será mantido

É utilizado o algoritmo de Kernighan e Lin (Kernighan; Lin, 1970) Porém, o K-L é projetada para um par de regiões É executado o K-L para cada par de regiões É repetido, até que nenhuma nova troca possa reduzir o overhead

(hill-climbing)

79 / 90



Balanceamento de Carga: Fase 3 – Refinamento

80 / 90



Balanceamento de Carga: Simulações

8 servidores: S1 ... S8

Capacidade do servidor Si = i x 20000

Espaço de 750 x 750 u.a. dividido em 225 células de 50 x 50

750 avatares Random waypoint Probabilidade do avatar ir a um dos 3 pontos de interesse

Algoritmo de gerenciamento de interesse utilizado: A³

Duração da sessão de jogo simulada: 20 min.

Carga do jogo ajustada de forma que sobrecarregasse o sistema Balanceamento de carga disparado constantemente

81 / 90



Balanceamento de Carga: Resultados (1/4)

82 / 90




83 / 90




84 / 90




85 / 90



Considerações Finais:Conclusões e trabalhos futuros

86 / 90



Considerações Finais: Contribuições

Lidar com recursos escassos A³: redução de mais de 30% do uso de largura de banda, nas

simulações realizadas O princípio do A³ pode ser combinado com diversos outros

algoritmos de ADI

Recursos heterogêneos Criou-se um esquema de balanceamento de carga dinâmico Apenas o servidor sobrecarregado e outros próximos a ele

participam A carga atribuída a cada servidor é proporcional à sua capacidade Conseguiu-se reduzir o overhead causado pela interação de

jogadores em diferentes regiões

87 / 90



Considerações Finais: Publicações e submissões

Publicados: BEZERRA, Carlos Eduardo B.; CECIN, Fábio R.; GEYER, Cláudio F. R.;

A³: a novel interest management algorithm for distributed simulations of MMOGsin: 12-th IEEE International Symposium on Distributed Simulation and Real Time Applications, 2008, Vancouver, BC, Canada.

VILANOVA, Felipe J.; BEZERRA, Carlos Eduardo B.; CRIPPA, Marcos R., CECIN, Fábio R.; GEYER, Cláudio F. R.;P2PSE - A peer-to-peer support for multiplayer gamesin: VII Brazilian Symposium on Computer Games and Digital Entertainment - Computing Track, 2008, Belo Horizonte, MG, Brazil.

Submetido: BEZERRA, Carlos Eduardo B.; GEYER, Cláudio F. R.;

A load balancing scheme for distributed servers of MMOGsin: Massively Multiuser Online Gaming Systems and Applications, Special Issue of Springer’s Multimedia Tools and Applications(aguardando divulgação do resultado)

88 / 90



Considerações Finais: Trabalhos futuros

Mais de um servidor por região Prover tolerância a falhas e dividir a carga de trabalho

Topologia da rede overlay baseada na topologia real Menor atraso na comunicação entre os servidores

Consistência do estado do jogo nos vários servidores Armazenamento distribuído do estado do jogo

Informação de estado mais disponível

Novas técnicas de otimização do uso de largura de banda

89 / 90



Referências (1/2)

ASSIOTIS, M.; TZANOV, V. A distributed architecture for MMORPG. Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, [S.l.], 2006.

CECIN, F.; REAL, R.; OLIVEIRA JANNONE, R. de; GEYER, C.; MARTINS, M.; BARBOSA, J. FreeMMG: a scalable and cheat-resistant distribution model for internet games. IEEE Int. Sym. on Distributed Simulation and Real-Time Applications, [S.l.], p.83–90, 2004.

CHEN, A.; MUNTZ, R. Peer clustering: a hybrid approach to distributed virtual environments. Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, [S.l.], 2006.

DE VLEESCHAUWER, B. et al. Dynamic microcell assignment for massively multiplayer online gaming. Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, [S.l.], 2005.

EL-SAYED. Application-level multicast transmission techniques over the internet. Tese – INPG, 2004.

FIDUCCIA, C.; MATTHEYSES, R. A linear-time heuristic for improving network partitions. Proceedings of the 19th conference on design automation, [S.l.], 1982.

HENDRICKSON, B.; LELAND, R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing, 1995.

LEE, K.; LEE, D. A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution. Proceedings of the ACMsymposium on Virtual reality software and technology, [S.l.], p.160–168, 2003.

90 / 90



Referências (2/2)

KARYPIS et al. A fast and high-quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1999.

KERNIGHAN, B.; LIN, X. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970.

MORGAN, G.; LU, F.; STOREY, K. Interest management middleware for networked games. Proceedings of 32th SIGGRAPH, 2005.

MORSE, K. et al. Interest management in large-scale distributed simulations. Irvine, CA: University of California, 1996. (Technical Report ICS-TR-96-27).

RAK, S.; VAN HOOK, D. Evaluation of grid-based relevance filtering for multicast group assignment. 14th Workshop On Standards For The Interoperability Of Distributed Simulations, 1996.

SCHIELE, G.; SUSELBECK, R.; WACKER, A.; HAHNER, J.; BECKER, C.; WEIS, T. Requirements of Peer-to-Peer-based Massively Multiplayer Online Gaming. Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, [S.l.], p.773–782, 2007.

VILANOVA, F. J.; BEZERRA, C. E. B.; CRIPPA, M. R.; CECIN, F. R.; GEYER, C. F. R. P2PSE - A Peer-to-Peer Support for Multiplayer Games. SBGames 2008, Belo Horizonte, MG, 2008.

ZOU, L.; AMMAR, M.; DIOT, C. An evaluation of grouping techniques for state dissemination in networked multi-user games. MASCOTS, 2001.

Documents

1 / 90 Lidando com recursos escassos e heterogêneos em um sistema distribuído atuando como servidor de MMOG Carlos Eduardo Benevides BezerraDefesa de Mestrado