Algoritmos distribuídos
para ambientes virtuais
de larga escala
Trabalho da disciplina
Algoritmos Distribuídos (2007.1)
Rodrigo de Souza Lima Espinha
Conteúdo


Introdução
Algoritmos para ambientes virtuais de larga
escala





SOLIPSIS
VON
Análise e comparação
Conclusão
Referências
Ambientes virtuais
distribuídos

Mundo virtual (Hu et al., 2006; Keller & Simon, 2004)


Espaço virtual gerado por computador
Composto por entidades



Dinâmico (tempo-real)



Avatares: controlados pelos usuários
Objetos virtuais: controlados por computadores
Movimento, entrada e saída de entidades
Interação entre as entidades
Distribuído

Entidades participantes em computadores diferentes
Ambientes virtuais
distribuídos
Ambientes virtuais
distribuídos

Aplicações (Hu & Liao, 2004)


Simulações militares
Massively Multiplayer Online Games (MMOG)



World of Warcraft
The Sims Online
Mundos virtuais


SOLIPSIS (Keller & Simon, 2004; SOLIPSIS, 2007)
Second Life
Requisitos

Requisitos (Hu et al., 2006)







Desempenho
 Tempo-real
Consistência
 Mesma visão do mundo
 Descoberta de outras entidades
Tolerância a falhas
Disponibilidade
Persistência
Segurança
 Autenticação
 Detecção de trapaceiros
Escalabilidade
Arquiteturas

Cliente-servidor (Knutsson et al., 2004; Chen & Muntz, 2006)



Facilidade para atender a requisitos como
segurança e persistência
Mais utilizado comercialmente
Clusters de servidores para suportar grande
número de usuários


Alto custo de manutenção
Dificuldades de escalabilidade
Arquiteturas

Peer-to-peer (Androutsellis-Theotokis & Spinellis, 2004; Chen & Muntz, 2006)

Descentralizada


Escalável



Peers independentes
Localidade de conexões
Baixo custo
Dificuldades


Segurança
Persistência
Arquiteturas

Híbridas (Chen & Muntz, 2006; Lee et al., 2007)


Redução de custos para fabricantes de jogos
Servidores




Autenticação
Persistência
Interações pesadas entre entidades
Peers


Comunicação com peers próximos
Escalabilidade
Estratégias para
Escalabilidade

Redução do custo de troca de mensagens
(Hu & Liao, 2004)


Comunicação localizada
Particionamento do mundo virtual

Cliente-servidor


Peer-to-peer


Região para cada servidor
Conexões com vizinhos
Áreas de interesse
Algoritmos estudados

Sistemas peer-to-peer


SOLIPSIS
VON: Voronoi-Bases Overlay Network
(Hu & Liao, 2004; Hu et al., 2006)


Estratégias para escalabilidade
Técnicas de geometria computacional
SOLIPSIS

Mundo virtual




Toro bidimensional
Grafo (G) de entidades (E) e conexões (C)
Áreas de interesse (AOI)
Imagens extraídas de (Keller & Simon, 2004; SOLIPSIS, 2007)
SOLIPSIS
Propriedades

Conhecimento local (local awareness)



Conhecimento que entidade e tem de seus
vizinhos (k(e)) dentro da AOI (A(e))
Garantido quando a(e)  k (e), onde a(e) são
entidades dentro da AOI
Se e pertence a A(e’) e A(e’’)

e’ e e’’ serão notificados de mundaças em e
SOLIPSIS
Propriedades

Conectividade global (global connectivity)




Entidade e só conhece as adjacentes
É preciso que, ao mover-se, a entidade perceba
as outras no caminho
Garantido se pose  CH (k (e))
Ou, alternativamente, se
h  H (e) : h(e)  k (e)
, onde
H (e)  {h  E : pose  CH (h)}
(Keller & Simon, 2004)
SOLIPSIS
Manutenção da consistência local
3.
e monitora seus vizinhos k(e)
e’ move-se para outra posição
e detecta que e’ k(e) entrou na
AOI de e’’ k(e), então notifica é’’
sobre e’

Garante-se que
1.
2.



e’’ é informada da chegada de e’
e’’ obtém as informações de vizinhança
enquanto se move
Mensagens redundantes ajudam a
evitar entidades maliciosas
(Keller & Simon, 2004)
SOLIPSIS
Manutenção da conectividade global
Se a entidade e moveu-se


A propriedade de conectividade global pode ter
sido desrespeitada por e
Correção

1.
2.
3.
e detecta a inconsistência (verifica se o ângulo
direcional (e1 e ef) < )
e envia mensagem de query para as entidades
no setor .
Se e1 recebe a mensagem e respeita a
propriedade, então está conectada a uma
entidade e2 do semi-plano 1 t.q.  (e2 e ef) <
 (e1 e ef).
1.
Se  (e2 e ef) < , a conectividade global é
restaurada. Senão, recursivamente retorna-se para
o passo 2, com e2 em vez de e1..

Eventualmente encontra-se um candidato que
atenda à propriedade. Então a conectividade
global é restaurada.
(Keller & Simon, 2004)
SOLIPSIS
Entrada de entidade
Entidade e quer entrar em pose = (xe, ye)

e encontra um ponto de entrada (outro peer (e0) do
mundo)
A partir de e0, caminha-se para e (estratégia gulosa
– menor distância).
Quando, para en, não houver vizinho mais próximo
de e que en, começa a “circundar” e:
1.
2.
3.
1.
2.
3.
4.
5.
6.
4.
en assume ser vizinho mais próximo de e e
estabelece conexão.
Caminha-se para em, a entidade mais próxima de e
diferente de en.
em conecta-se a e.
Encontra-se o vizinho mais próximo, formando
polígono convexo ao redor de e.
Se d(e, em+1) < d(e, en), retorna-se ao passo 2, com
e0 = em+1.
Senão, procuram-se entidades (em+1) mais próximas
a e que estão no semi-plano definido por (e, em), na
direção iniciada por en. Repetem-se as etapas 3.1 a
3.6, com en = em+1, até que o semi-plano de (e, en)
seja atravessado, o que representa a criação de um
polígono convexo ao redor de e.
e é notificada sobre o fim do algoritmo, e passa a
fazer parte da rede.
(Keller & Simon, 2004)
VON

Diagrama de Voronoi da entidade e



Vizinhos envolventes
Vizinhos de fronteira
Vizinhos regulares
Hu et al., 2006
VON
Entrada de entidade
Entidade e quer entrar na posição pose

1.
2.
3.
4.


e contacta o servidor de acesso, (pode ser o primeiro peer (e0) a
participar da rede) e obtém id global.
Caminha-se na direção de pose (estratégia gulosa - menor distância),
até encontrar a região de en, onde e será inserido.
en envia a sua lista de vizinhos para e.
e entra em contato com os novos vizinhos e constrói um diagrama de
Voronoi. Os vizinhos também atualizam seus diagramas para incluir a
nova entidade.
A região de en será agora
dividida com e
Somente as regiões dos
vizinhos envolventes serão
afetadas.
Hu et al., 2006
VON
Saída / falha de entidade
e se desconecta da rede.
Ausência de e é detectada pelas entidades afetadas
1.
2.
1.
2.
3.
4.
e é vizinho envolvente de outras entidades
Timeouts
Entidades das quais e é vizinho de fronteira são notificadas por
outros vizinhos ainda na rede.
Entidades afetadas atualizam seus diagramas de Voronoi.
Hu et al., 2006
VON
Movimentação de entidade
Ao movimentar-se, e notifica todos os vizinhos sobre a nova posição.
Se o receptor en é um vizinho de fronteira
1.
2.
1.
2.
e conecta-se com os novos vizinhos e envia lista dos seus vizinhos
envolventes
3.
1.
4.
en determina se um de seus vizinhos envolventes agora está dentro da
nova AOI de e.
Se sim, notifica-se e.
Vizinhos de e agora podem notificá-la de outros eventuais vizinhos que
ainda estejam faltando.
e desconecta-se dos antigos vizinhos que não estão mais na AOI.
Hu et al., 2006
Análise e Comparação

Problema tratado: escalabilidade




p2p tem grande potencial
Segurança e persistência não são abordados
Reduzem-se as mensagens trocadas por peer, mas
ainda maior que na arquitetura cliente-servidor
Pior caso: n-1 vizinhos

Ocorre raramente
Hu & Liang, 2004
Análise e Comparação

Modelo de sistema




Assíncrono: algoritmos não assumem limite de tempo
 Porém, desejável que participantes do mundo virtual
percebam-se sincronizados com os outros
Número de nós da rede e topologia dinâmicos
Falhas temporárias de (poucas) entidades ou de omissão
de canais
 Vizinhos colaboram para manter consistência
 Entidade que voltou a funcionar entra no sistema como
uma nova
Canais de comunicação seguros
Análise e Comparação

Entidades podem ficar temporariamente
inconsistentes


Enventualmente a consistência é restaurada
pelos vizinhos
Tamanho da área de interesse (AOI)


Ruim se muito pequena ou grande
AOI dinâmica


Capacidade da entidade
Densidade da AOI
Análise e Comparação

Espaço do mundo virtual é 2D

Generalização (?)

SOLIPSIS



Fecho convexo 3D
3-torus
VON

Diagrama de Voronoi 3D
Conclusão

Algoritmos apresentados



Foco em escalabilidade
Segurança, persistência, etc. ainda devem ser
investigados
Arquiteturas híbridas?
Bibliografia









CAVAGNA, R.; BOUVILLE, C., ROYAN, J. P2P Network for very large virtual environment. In
Proceedings of the ACM Symposium on Virtual Reality Software and Technology (Limassol, Cyprus,
November 01 - 03, 2006). VRST '06. ACM Press, New York, NY, 269-276.
CHEN, A.; MUNTZ, R. R. Peer clustering: a hybrid approach to distributed virtual environments. In Proc.
of 5th ACM SIGCOMM, Out. 2006.
HAMPEL, T.; BOPP, T.; HINN, R. A peer-to-peer architecture for massive multiplayer online games. In
Proceedings of 5th ACM SIGCOMM Workshop on Network and System Support For Games (Singapore,
October 30 - 31, 2006).
HU, S.; LIAO, G. Scalable peer-to-peer networked virtual environment. In Proceedings of 3rd ACM
SIGCOMM Workshop on Network and System Support For Games (Portland, Oregon, USA, August 30 30, 2004). NetGames '04. ACM Press, New York, NY, 129-133.
HU, S.; CHEN, J.; CHEN, T. VON: a scalable peer-to-peer network for virtual environments. In IEEE
Network, 4(2), pp. 22-32, jul-ago, 2006.
KELLER, J.; SIMON, G. SOLIPSIS: A Massively Multi-Participant Virtual World. In Proc. Of PDPTA 2003,.
pg. 262-268; 2003.
KNUTSSON, B.; LU, H.; XU, W.; HOPKINGS, B. Peer-to-peer support for Massively Multiplayer Games.
In IEEE INFOCOM, 2004.
Lee, D., Lim, M., Han, S., and Lee, K. 2007. ATLAS: A Scalable Network Framework for Distributed
Virtual Environments. Presence: Teleoper. Virtual Environ. 16, 2 (Apr. 2007), 125-156. DOI=
http://dx.doi.org/10.1162/pres.16.2.125.
SOLIPSIS. SOLIPSIS Web Site. http://solipsis.netofpeers.net. Acessado em jun. 2007.
FIM
Perguntas?