Avaliação do
Você é humano?
8
5
=
Denunciar conteúdo impróprio
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Small world models and a compact routing scheme
Use este link compartilhar ou citar este material: http://educapes.capes.gov.br/handle/1884/58199
Registro completo de metadados
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Vignatti, André Luís | - |
| Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
| Autor(es): dc.creator | Viertel, Santiago, 1986- | - |
| Data de aceite: dc.date.accessioned | 2019-08-21T23:19:40Z | - |
| Data de disponibilização: dc.date.available | 2019-08-21T23:19:40Z | - |
| Data de envio: dc.date.issued | 2019-01-10 | - |
| Data de envio: dc.date.issued | 2019-01-10 | - |
| Data de envio: dc.date.issued | 2018 | - |
| Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/58199 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/58199 | - |
| Descrição: dc.description | Orientador: Prof. Dr. André Luís Vignatti | - |
| Descrição: dc.description | Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 17/10/2018 | - |
| Descrição: dc.description | Inclui referências: p.78-82 | - |
| Descrição: dc.description | Área de concentração: Ciência da Computação | - |
| Descrição: dc.description | Resumo: Os modelos geradores de redes de mundo pequeno são alternativas aleatorizadas de construção de redes onde os nós estão interligados por caminhos curtos. Nesse contexto, um caminho curto tem o comprimento dado por uma função logarítmica no tamanho da rede. Aplicações em redes peer-to-peer, de sensores sem fio e implementação de redes em chip são alguns exemplos computacionais que utilizam redes geradas por modelos matemáticos de mundo pequeno. Esse trabalho apresenta o modelo de redes de mundo pequeno toroidal não direcionado (UTSW). O modelo gera uma grade bidimensional base para modelar o agrupamento dos nós, e conexões aleatórias para modelar caminhos curtos. A presença de caminhos curtos não implica a existência de um algoritmo de roteamento de mensagens que os encontra. Porém, existe um algoritmo de roteamento guloso na literatura que encontra caminhos curtos em redes UTSW, sendo que um caminho curto tem o comprimento dado por uma função polilogarítmica no tamanho da rede. O modelo de mundo pequeno octaédrico (OSW) também é apresentado. Ele gera um grafo planar base sobre o octaedro, que é provado ser similar à geração sobre esferas. Assim, ele simula pessoas e vizinhanças na superfície do planeta. O modelo OSW também gera conexões aleatórias para modelar caminhos curtos. Um algoritmo de roteamento que encaminha mensagens por caminhos curtos também é definido para esse modelo. Ambos os algoritmos de roteamento utilizam o paradigma guloso e decidem para qual vizinho encaminhar uma mensagem com somente a informação na tabela de roteamento do nó. Esses algoritmos requerem pouca memória por nó, encontram caminhos curtos e executam em tempo constante, nos dois modelos apresentados. Por isso, eles são boas opções em roteamento, além do roteamento por caminhos mínimos. No entanto, ambos necessitam de informações de posicionamento geradas pelo modelo matemático. No caso do modelo UTSW, cada nó possui um par ordenado de números naturais que o posiciona na grade bidimensional. Encontrar essas posições quando elas são desconhecidas é desafiador, pois as conexões geradas aleatoriamente dificultam a identificação da grade. Porém, a conexão aleatória de um nó quebra o padrão de grade em sua vizinhança com baixa probabilidade. Essa propriedade topológica das redes UTSW motivou o projeto de um algoritmo de rotulação que encontra as posições na grade com alta probabilidade. Ele realiza uma busca local em cada nó e remove a conexão aleatória, se ela for identificada. Após a varredura, o algoritmo realiza uma busca em largura global na rede resultante, posicionando cada nó com base nas posições já encontradas de seus vizinhos. Um esquema de roteamento compacto para grafos UTSW é então apresentado. Ele é composto por um algoritmo de pré-processamento que utiliza o algoritmo de rotulação para gerar estruturas de dados de tamanho logarítmico para todos os nós e que executa em tempo linear no tamanho da rede. Com isso, o algoritmo de roteamento guloso encaminha mensagens utilizando as estruturas de dados geradas pelo algoritmo de pré-processamento. Palavras-chave: redes de mundo pequeno. modelos geradores. roteamento guloso. algoritmos de rotulação. esquemas de roteamento compactos. | - |
| Descrição: dc.description | Abstract: Small world networks generative models are randomized alternatives of network building where nodes are interconnected by small paths. In this context, a small path has the length given by a logarithmic function in the size of the network. Applications in peer-to-peer networks, wireless sensors and networks on chip are some computational examples that use networks generated by small world mathematical models. This work presents the undirected toroidal small world networks model (UTSW). The model generates a base two-dimensional grid to model the clustering of the nodes, and random connections to model small paths. The presence of small paths does not imply in the existence of a message routing algorithm that finds them. However, there is a greedy routing algorithm in the literature that finds small paths in UTSW networks, where a small path has the length given by a polylogarithmic function in the size of the network. The octahedral small world model (OSW) is also presented. It generates a base planar graph on the octahedron, which is proved to be similar to the generating on spheres. Then, it simulates people and neighborhoods on the surface of the planet. The OSW model also generates random connections to model small paths. A routing algorithm that routes messages through small paths is also defined for this model. Both routing algorithms use the greedy paradigm and decide to which neighbor to forward a message with only the information in the routing table of the node. These algorithms require small amount of memory per node, find small paths and execute in constant time, in both presented models. So, they are good options in routing, besides the routing thought shortest paths. However, both require positioning information generated by the mathematical model. In the case of UTSW model, each node has an ordered pair of natural numbers that positions it on the two-dimensional lattice. Finding these positions when they are unknown is challenging because the randomly generated connections make the grid identification difficult. However, the random connection of a node breaks the lattice pattern in its neighborhood with small probability. This topological property of UTSW networks motivated the design of a labeling algorithm that finds the positions in the lattice with high probability. It executes a local search on each node and removes the random connection if it is identified. After the sweeping, the algorithm executes a global breadth-first search on the resulting network, positioning each node based on the already found positions of its neighbors. A compact routing scheme for UTSW graphs is then presented. It consists of a preprocessing algorithm that uses the labeling algorithm to generate logarithmic size data structures for all nodes and executes in linear time on the size of the network. Thus, the greedy routing algorithm routes messages using the data structures generated by the preprocessing algorithm. Keywords: small world networks. generative models. greedy routing. labeling algorithms. compact routing schemes. | - |
| Formato: dc.format | 82 p. : il. | - |
| Formato: dc.format | application/pdf | - |
| Formato: dc.format | application/pdf | - |
| Palavras-chave: dc.subject | Redes locais de computação | - |
| Palavras-chave: dc.subject | Ciência da Computação | - |
| Palavras-chave: dc.subject | Roteadores (Redes de computação) | - |
| Palavras-chave: dc.subject | Arquivos de computador | - |
| Palavras-chave: dc.subject | Teses | - |
| Título: dc.title | Small world models and a compact routing scheme | - |
| Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo | |
Não existem arquivos associados a este item.
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma:
- O Termo de Uso pode ser modificado pela CAPES a qualquer tempo, sem necessidade de notificação prévia, sendo que tais modificações serão válidas a partir da data de sua veiculação neste portal;
- Para aprovação de cadastro do usuário ao sistema, a CAPES pode requisitar o fornecimento de informações, haja vista a política de segurança adotada, objetivando resguardar a segurança dos usuários nesse ambiente virtual;
- O usuário aceita e declara compreender que, em razão do peculiar ambiente da Internet, a CAPES não poderá garantir que o acesso ao site seja livre de erros ou problemas decorrentes de casos fortuitos, internos ou externos, casos de força maior ou ainda de outros casos não inteiramente sujeitos a controle direto dos administradores do site e, portanto o usuário se obriga a isentar a CAPES de quaisquer reclamações ou indenizações. A CAPES também não se responsabiliza por interrupções, interceptações, invasões, disseminação de vírus ou outros atos ilícitos, típicos e atípicos de ambiente virtual, e de web, dos quais a CAPES não tenha tido intenção deliberada de participar ou praticar;
- O usuário aceita e declara compreender que qualquer texto, marca, áudio, imagem, ou conteúdo veiculados no site são protegidos por direitos de propriedade intelectual o qual deve ser respeitado de acordo com a licença concedida pelo respectivo detentor dos referidos direitos, sob pena de apuração das responsabilidades cabíveis;
-
Desta forma a CAPES se exime de toda e qualquer responsabilidade por eventuais perdas, danos e prejuízos de qualquer natureza decorrentes:
- Do descumprimento da lei, da moral e dos bons costumes, como consequência da transmissão, difusão, armazenamento, disponibilização, recepção, obtenção ou acesso aos conteúdos;
- Da infração aos direitos de propriedade intelectual e industrial, segredos empresariais, compromissos contratuais de qualquer tipo, direitos à honra, à intimidade pessoal e familiar, à imagem das pessoas, direitos de propriedade e de toda e qualquer natureza pertencentes a um terceiro por consequência da transmissão, difusão, armazenamento, disponibilização, recepção, obtenção ou acesso aos conteúdos;
- Da falta de veracidade, precisão, exatidão, pertinência e/ou atualidade dos conteúdos;
- Da inadequação para qual seja o propósito, ou da frustração, das expectativas geradas pelos conteúdos;
- Exceto quando mencionado explicitamente, ou quando se tratar de citação de material alheio ou ilustração, nos limites estabelecidos pela Lei 9.610/98, todo o Conteúdo textual original do Portal eduCAPES está disponível livremente para leitura, entre outros direitos, conforme definido na licença Creative Commons;
- A CAPES não se responsabiliza pelos comentários, opiniões, informações, depoimentos, mensagens, vídeos, textos, imagens, áudios ou qualquer outro tipo de conteúdo que sejam, postados, publicados e disponibilizados através do Portal eduCAPES pelos usuários, sendo a responsabilidade civil e criminal atribuída única e exclusivamente ao autor dos comentários, opiniões, informações, ou mensagens. Todo o conteúdo publicado por usuários são de responsabilidade exclusiva dos mesmos e de caráter completamente independente, sendo que todo e qualquer tipo de opinião, ideal e/ou posição expressados não refletem necessariamente o ponto de vista e a posição do Portal eduCAPES e/ou da CAPES. A CAPES se reserva o direito de armazenar as informações destes autores e/ou Usuários, a fim de viabilizar sua identificação;
- O usuário aceita e declara compreender que a CAPES poderá disponibilizar no Portal eduCAPES, links de acesso para outros sites e endereços virtuais administrados, controlados ou operados por terceiros. Qualquer site conectado a partir do eduCAPES não está sob o controle da CAPES;
- A CAPES não assume nenhuma responsabilidade ou obrigação por qualquer informação, comunicação ou material encontrado em tais sites, ou em qualquer site conectado a tais sites. A CAPES não assume qualquer responsabilidade pelos serviços ou funcionalidades ali dispostos, sendo a decisão de utilização e a forma de relacionamento com os mesmos de exclusiva responsabilidade do usuário, que inclusive isenta a CAPES de fiscalizar o conteúdo ou zelar pela integridade de tais sites ou endereços virtuais.
- O usuário aceita e declara compreender que o acesso a determinadas áreas do site será restrito. Para acessá-las, o usuário deverá fazer o login e cadastrar uma senha de acesso. A senha é individual, sigilosa e intransferível, sendo o usuário o único responsável pela guarda da mesma. O usuário assume toda e qualquer responsabilidade pelo mau uso ou pela utilização da senha por terceiros;
- A CAPES reserva o direito de excluir o cadastro, de excluir o material submetido ou proibir o acesso do usuário ao portal eduCAPES no caso de qualquer abuso ou indício de prática ilícita no uso do site ou de qualquer uso não autorizado ou proibido pelo usuário, nos termos da legislação brasileira;
- As condições estabelecidas no Termo de Aceite e Uso do Site são regidas pela lei brasileira. Sob nenhuma circunstância o usuário deverá violar qualquer lei usando o portal eduCAPES para propósitos que incluam, mas não limitados a isso, difamação ou perturbação de outros, violação de direitos de propriedade intelectual ou de terceiros, envio de material obsceno ou ofensivo, vírus, arquivos corrompidos, ou outros programas que poderiam danificar ou alterar este site ou os computadores de empresa ou de terceiros;
- A CAPES reserva o direito de retirar qualquer conteúdo que infrinja a lei, a moral e os bons costumes nos termos da legislação vigente e também na hipótese de o conteúdo não se coadunar com as finalidades educativas do Portal. A CAPES garante o direito de defesa e contraditório dos usuários. O usuário reconhece que o material enviado por terceiros, que não a CAPES, não é endossado pela mesma.
Concordo e desejo baixar o arquivo
Não concordo e não irei baixar o arquivo
Não concordo e não irei baixar o arquivo