Apresentação em tema: "Algoritmos distribuídos para ambientes virtuais de larga escala"— Transcrição da apresentação:
Mundo virtual (Hu et al., 2006; Keller & Simon, 2004) Espaço virtual gerado por computador Composto por entidades Avatares: controlados pelos usuários Objetos virtuais: controlados por computadores Dinâmico (tempo-real) Movimento, entrada e saída de entidades Interação entre as entidades Distribuído Entidades participantes em computadores diferentes
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
7 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
8 Arquiteturas Peer-to-peer (Androutsellis-Theotokis & Spinellis, 2004; Chen & Muntz, 2006) Descentralizada Peers independentes Escalável Localidade de conexões Baixo custo Dificuldades Segurança Persistência
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
Redução do custo de troca de mensagens (Hu & Liao, 2004) Comunicação localizada Particionamento do mundo virtual Cliente-servidor Região para cada servidor Peer-to-peer Conexões com vizinhos Áreas de interesse
Conhecimento local (local awareness) Conhecimento que entidade e tem de seus vizinhos (k(e)) dentro da AOI (A(e)) Garantido quando , 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
Conectividade global (global connectivity) Entidade e só conhece as adjacentes É preciso que, ao mover-se, a entidade perceba as outras no caminho Garantido se Ou, alternativamente, se , onde (Keller & Simon, 2004)
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 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)
Se a entidade e moveu-se A propriedade de conectividade global pode ter sido desrespeitada por e Correção 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). 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)
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: 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)
Entidade e quer entrar na posição pose 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
e se desconecta da rede. Ausência de e é detectada pelas entidades afetadas 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
Ao movimentar-se, e notifica todos os vizinhos sobre a nova posição. Se o receptor en é um vizinho de fronteira en determina se um de seus vizinhos envolventes agora está dentro da nova AOI de e. Se sim, notifica-se e. e conecta-se com os novos vizinhos e envia lista dos seus vizinhos envolventes 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
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
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
24 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