| Abstract: | Redes Tolerantes a Atrasos (Delay Tolerant Network - DTN) são redes sujeitas a interrupções frequentes, altos atrasos e elevadas taxas de erro. Nessas redes os nodos são móveis e fazem o papel de roteadores, armazenando e fazendo o repasse das mensagens que precisam ser entregues. O foco deste trabalho está nas redes DTN estocásticas, nas quais as mudanças topológicas não são conhecidas e surgem técnicas para tentar aumentar a probabilidade de sucesso no roteamento, utilizando conhecimento histórico do comportamento da rede na tomada da decisão. As redes DTN possuem algumas semelhanças com as redes ad hoc, mas devido às constantes disrupções que ocorrem nas redes DTN, o problema do roteamento é tratado de forma diferente. Em cenários esparsos, devido à falta de conectividade dos nodos, as redes DTN apresentam maior percentual de mensagens entregues, a custo de maiores atrasos. Um estudo comparando esses dois tipos de redes é realizado por este trabalho, comprovando esse aspecto. Este trabalho propõe três variações de um protocolo de roteamento para redes DTN estocásticas que utiliza uma métrica chamada de “potencial de entrega” usada na decisão do repasse das mensagens. O potencial de entrega é uma medida histórica que indica o número de encontros em que os nodos estão envolvidos em um período de tempo. No intuito de aumentar a probabilidade de encontrar o destinatário, a estratégia prioriza o roteamento a nodos que tenham um número alto de encontros. O protocolo inicial é chamado de APRP (Adaptive Potential Routing Protocol ) e, em comparação com outros protocolos para o mesmo tipo de rede, apresenta um percentual de mensagens entregues equivalente a esses protocolos, com um overhead bastante reduzido, especialmente para redes esparsas (importantes em DTN).Uma variação do APRP utiliza um mecanismo de confirmação de mensagens já entregues com o intuito de liberar espaço em buffer para mensagens novas. Tal variação é chamada de APRP-Ack e apresenta desempenho superior ao APRP, ao custo de um aumento no atraso médio na entrega das mensagens. Por fim, é proposto o APRP-Group, com o objetivo de reduzir o atraso gerado pelo APRP e APRP-Ack. O APRP-Group busca identificar grupos de nodos com potenciais de entrega similares e decidir sobre o repasse das mensagens com base em tais grupos. Este protocolo apresenta uma redução significativa no atraso de entrega, se comparado ao APRP e APRP-Ack, mantendo baixos os custos de comunicação e mantendo ou melhorando níveis de entrega. Os diferentes protocolos foram simulados em um ambiente específico para DTN e comparados com protocolos da literatura, especialmente com o Spray and Wait devido ao seu alto desempenho reportado na literatura.
Delay Tolerant Network (DTN) are networks in which frequent interruptions, high delay, and high error rates may occur. In these networks the nodes are mobile and play the role of routers, storing and transferring messages that need to be delivered. This thesis consider the stochastic DTN, where the topological changes are not known in advance and techniques are proposed that try to increase the probability of success in the routing, using, for instance, historical knowledge of network behavior in the routing decision. DTN has some similarities to ad hoc networks, but due to frequent disruptions that occur in DTN, the routing problem is handled differently. In sparse scenarios, due to lack of connectivity of nodes, DTN has higher percentage of delivered messages, at the price of higher delays. A study comparing these two kinds of networks is carried out by this thesis, providing quantitative information about this aspect. This work proposes three variations of a routing protocol for stochastic DTN based on a metric called “delivery potential”, which is used while deciding how messages are forwarded. The delivery potential is a historical measure that indicates the number of meetings in which the nodes are involved in a period of time. In order to increase the probability to find the destination, the strategy gives priority to routing nodes that have a high number of meetings. The initial protocol is called ARPR (Adaptive Potential Routing Protocol) and, in comparison with other protocols for the same type of network, presents a percentage of delivered messages equivalent to these protocols, with a very low overhead, especially for sparse networks (important in DTN).An APRP variation uses an acknowledgement mechanism for messages already delivered in order to release space in buffer for new messages. This variation is called APRP-Ack and has better performance than ARPR, despite causing an increase in the average delay in the delivery of messages. Finally, the APRP-Group is proposed, in order to reduce the delay generated by APRP-Ack. The APRP-Group seeks to identify groups of nodes with similar delivery potential and decide on the forwarding of messages based on these groups. This protocol provides a significant reduction in the delivery delay, compared to APRP and APRP-Ack, maintaining low costs of communication and maintaining or improving levels of delivery. The above mentioned proposed protocols where evaluated using a DTN specific simulation environment specific and compared to analogous protocols from the literature, specially with the Spray and Wait due to its high performance reported in the literature. |
