• Entrar
    Ver item 
    •   Página inicial
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • Teses & Dissertações
    • Ver item
    •   Página inicial
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • Teses & Dissertações
    • Ver item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Um algoritmo heurístico para roteamento robusto e eficiente baseado em avaliação de fluxo máximo

    Thumbnail
    Visualizar/Abrir
    Dissertacao_Maverson_Eduardo_Schulze_Rosa.pdf (566.6Kb)
    Data
    2008
    Autor
    Rosa, Maverson Eduardo Schulze
    Metadata
    Mostrar registro completo
    Resumo
    Resumo: Os protocolos de roteamento são baseados em tabelas de roteamento e, à medida em que ocorrem alteraçãoes na topologia da rede, essas tabelas permanecem desatualizadas durante um certo período de tempo (latência de convergência), até que as informações sejam atualizadas. No BGP (Border Gateway Protocol), o protocolo de roteamento externo utilizado na Internet, esse período é de aproximadamente três minutos, sendo que já foram observados picos de até quinze minutos. Durante esse período, pacotes de dados podem ser perdidos e conexões podem ser interrompidas. Recentemente, foi proposta uma estratégia de roteamento dinâmico tolerante a falhas que possibilita o correto funcionamento do roteamento durante esse período. Essa estratégia baseia-se na utilização de um critério de fluxo máximo, utilizado em conjunto com outros critérios e um mecanismo de backtracking, para avaliar os caminhos possíveis em uma rede. O presente trabalho propõe um algoritmo heurístico que possibilita a utilização de tabelas de roteamento que correlacionam um endereço de destino à múltiplos endereços de saída, ordenados de acordo com estimativas da robustez dos caminhos. Essas tabelas propiciam o backtracking de mensagens durante o processo de encaminhamento, em contraste com a estratégia anterior, que realiza um cálculo completo das estimativas a cada mensagem encaminhada. São também apresentados uma prova formal da correção do algoritmo proposto e resultados de simulações comparando-o com outras alternativas. Esses resultados comprovam que, com uma alteração no formato das tabelas de roteamento e um pequeno aumento no comprimento médio dos caminhos percorridos, é possível efetuar o roteamento robusto de mensagens de forma eficiente.
     
    Abstract: Several routing protocols are based on routing tables that must be updated as the network topology changes. From the instant of time the change occurs and the tables are updated (convergence latency), packets can be dropped and connections broken. In the BGP (Border Gateway Protocol), the Internet exterior routing protocol, this period is approximately three minutes, and peaks up to fifteen minutes have been observed. Recently a fault-tolerant routing algorithm that improves the correctness of routing during this period was proposed. This algorithm uses a backtracking mechanism combined with maximum flow evaluation to select network paths. Nevertheless the algorithm as it is proposed cannot be deployed to real networks. The present work is based on that algorithm, but proposes a new heuristic algorithm that allows routing tables to be used. These tables correlate multiple output addresses, ordered according estimates of robustness and enable backtracking during the forwarding process. This contrasts with the previous algorithm, which performs a full evaluation for each forwarded message. A correctness proof and experimental results btained with simulation are also presented, comparing the algorithm to Dijkstra’s shortest-path first algorithm and to the previous algorithm. These results show that robust routing is more efficient with small changes in the format of currently used routing tables and with a small increase of the average length of shortest paths.
     
    URI
    https://hdl.handle.net/1884/18524
    Collections
    • Teses & Dissertações [10558]

    DSpace software copyright © 2002-2022  LYRASIS
    Entre em contato | Deixe sua opinião
    Theme by 
    Atmire NV
     

     

    Navegar

    Todo o repositórioComunidades e ColeçõesPor data do documentoAutoresTítulosAssuntosTipoEsta coleçãoPor data do documentoAutoresTítulosAssuntosTipo

    Minha conta

    EntrarCadastro

    Estatística

    Ver as estatísticas de uso

    DSpace software copyright © 2002-2022  LYRASIS
    Entre em contato | Deixe sua opinião
    Theme by 
    Atmire NV