Delay Tolerant Network Routing

Abstract

No contexto de redes de computadores, a mobilidade dos nós pode causar desafios à entrega de dados. Particularmente, isso aumenta a probabilidade de quebras nas conexões, tornando improvável a ocorrência de caminhos de ponta a ponta desde a origem até ao destino. Sendo que as arquiteturas e protocolos usados pela Internet de hoje em dia dependem da existência de tais caminhos, estes terão provavelmente mau desempenho sob estas condições.As Redes Tolerantes a Atraso lidam com estas condições difíceis assumindo a existência de quebras, que podem ser compensadas pela existência de armazenamento em cada nó. Isto permite aos nós armazenar dados assim que são recebidos, transportá-los enquanto se movem, e mais tarde encaminhá-los para outro nó com que entre em contacto. Assim, neste paradigma de Armazenamento-Transporte-Encaminhamento, a mobilidade é vista como algo que pode ser explorado para o benefício da rede. Cada nó encaminha e gere os seus dados de acordo com uma certa estratégia de encaminhamento, que tem um impacto significativo no desempenho da rede.Nesta dissertação, propomos um modelo simplificado de um cenário de sensores em ambiente urbano, em que Unidades de Recolha de Dados reúnem dados de sensores que têm que ser entregues a Unidades de Beira de Estrada, por entidades que se movem entre elas. Para descrever esta Rede Tolerante a Atraso, usamos uma Cadeia de Markov homogénea, de tempo discreto, e de estados finitos. Neste contexto, a mobilidade, comunicação e encaminhamento são modelados separadamente, permitindo o uso de diferentes implementações para cada um deles. Também introduzimos um quadro de análise para este modelo, que descreve como calcular múltiplas métricas de desempenho da rede. Com isto, analisamos um cenário real específico, permitindo-nos otimizar a estratégia de encaminhamento.

In the context of computer networks, node mobility can pose challenges to data delivery. Particularly, it increases the likelihood of disruptions to the connections, making it unlikely for an end-to-end path from the source to the destination to ever exist. Given that the architecture and protocols of today's Internet depend on such paths, they are likely to perform poorly under such conditions.Delay-Tolerant Networks handle these challenging conditions by assuming the existence of disruptions, which can be compensated by having some storage in each node. This allows nodes to store data as soon as it is received, carrying it with them as they move, and being able to later forward it to another node they come into contact with. Therefore, in this store-carry-forward paradigm, mobility is seen as something to be exploited for the benefit of the network. Each node forwards and manages its data according to a certain routing strategy, which has a major impact in the network's performance.In this dissertation, a simplified model of a urban sensing scenario is proposed, where Data Collecting Units gather sensor data which is to be delivered to Road Side Units by entities that move between them. A finite-state discrete-time homogeneous Markov chain is used to describe this Delay-Tolerant Network. In that context, mobility, communication and routing are modelled separately, permitting the usage of different implementations of each. We also introduce an analysis framework for this model, which describes how to calculate multiple network performance metrics. With this, a specific real-world scenario can be analysed, enabling a certain type of routing strategy to be optimized.