Redes Tolerantes a Atrasos e Desconexões

Prévia do material em texto

Capítulo
5
Redes Tolerantes a Atrasos e Desconexões
Carina T. de Oliveira1, Marcelo D. D. Moreira1, Marcelo G. Rubinstein2,
Luís Henrique M. K. Costa1 e Otto Carlos M. B. Duarte1
1COPPE/Poli - Universidade Federal do Rio de Janeiro ∗
2PEL/DETEL - FEN - Universidade do Estado do Rio de Janeiro
Abstract
The huge success of the Internet in the last three decades is related to its protocols pro-
file named TCP/IP due to their flexibility, efficiency, and robustness that allow supporting
several applications in different scenarios. However, in scenarios with high delay and fre-
quent disruptions, TCP/IP protocols simply do not work and new protocols are necessary.
Networks that possess these characteristics are called Delay and Disruption Tolerant
Networks (DTNs). The IRTF has proposed a DTN architecture that uses the store-and-
forward technique on an overlay, called bundle layer. Thus, this chapter describes the
problems related to the TCP/IP architecture, presents the architecture and the protocol
proposed for DTNs, and reviews a number of existent projects and applications. Routing
in DTNs, being a great challenge, is also focused on and the main problems and solution
proposals are presented. Finally, several open issues are presented.
Resumo
O enorme sucesso da Internet nas últimas três décadas se deve ao seu perfil de protocolos
denominados TCP/IP por causa da sua flexibilidade, eficiência e robustez, que permitem
suportar diversas aplicações em diferentes cenários. No entanto, em cenários com longos
atrasos e freqüentes desconexões, os protocolos TCP/IP simplesmente não funcionam e
novos protocolos são necessários. Redes que possuem estas características são chamadas
de redes tolerantes a atrasos e desconexões (Delay and Disruption Tolerant Networks
- DTNs). O IRTF está propondo uma arquitetura para DTNs que se serve da técnica
armazena-e-encaminha em uma sobrecamada denominada de agregação (bundle layer).
Assim, este capítulo descreve os problemas relacionados à arquitetura TCP/IP, apresenta
a arquitetura e o protocolo que estão sendo propostos para as DTNs e ilustra uma série
de projetos e aplicações existentes. O roteamento nas DTNs, por ser um grande desafio,
é também focado e são apresentados os principais problemas e propostas de soluções.
Finalmente, diversos temas ainda em aberto são apresentados.
∗Este trabalho foi realizado com recursos do CNPq, CAPES, FINEP, RNP, FUJB e FAPERJ.
5.1. Introdução
A arquitetura da Internet é uma solução tecnológica de comprovado sucesso, sendo
utilizada no mundo todo para interconectar os mais variados tipos de dispositivos de co-
municação, em diferentes cenários e dando suporte a diversas aplicações. Entretanto,
algumas premissas necessárias ao bom funcionamento da arquitetura da Internet não são
encontradas em determinados ambientes, tornando o perfil de protocolos da Internet ina-
dequado e pouco robusto. Exemplos de tais ambientes são: comunicações sem fio, co-
municações entre dispositivos móveis, comunicações entre dispositivos com restrições de
energia, comunicações rurais, comunicações em campo de batalha, comunicações subma-
rinas, comunicações interplanetárias etc. Estes ambientes, considerados “desafiadores”,
possuem em comum a dificuldade de manter uma comunicação fim-a-fim com baixa la-
tência e pequena perda de pacotes. Devido a estas características, as redes que consideram
estes aspectos foram denominadas Redes Tolerantes a Atrasos e Desconexões (Delay and
Disruption Tolerant Networks - DTNs). Apesar de o termo DTN ser o mais utilizado
na literatura, também podem ser encontradas outras terminologias, tais como: redes com
conectividade eventual, redes móveis parcialmente conectadas, redes desconectadas, re-
des com conectividade transiente, redes incomuns, redes extremas e, mais recentemente,
Redes com Desafios (CHAllenged NeTworkS - CHANTS) [Chen et al., 2006].
Um exemplo de ambiente onde os protocolos convencionais da Internet não fun-
cionam são as redes ad hoc móveis (Mobile Ad hoc NETworks - MANETs), onde a to-
pologia da rede pode mudar constantemente quando a mobilidade dos nós é muito alta,
provocando freqüentes desconexões [Fall, 2005, Hanbali et al., 2005]. Outro exemplo são
as redes de sensores sem fio, onde os nós precisam economizar energia e por isso perma-
necem desligados periodicamente, causando o particionamento da rede e conectividade
intermitente. Assim, o caminho entre a origem e o destino pode não existir durante um
período ou, ainda, pode ser que um caminho entre a origem e o destino nunca chegue
a ficar completamente conectado. As características destes e de outros novos ambien-
tes de rede conduzem a uma série de desafios que precisam ser vencidos: freqüentes
desconexões, atrasos longos e/ou variáveis (da ordem de horas ou dias), conectividade
intermitente, recursos limitados dos dispositivos de comunicação, alta taxa de erros etc.
Em resumo, as principais características encontradas nas Redes Tolerantes a Atra-
sos e Desconexões são:
• atrasos longos e/ou variáveis - uma DTN pode chegar a ter atrasos da ordem de
horas e, até mesmo, dias. A variação do atraso também pode chegar a estes valores.
O atraso fim-a-fim é determinado através da soma dos tempos de atraso salto-a-
salto. Basicamente, é formado por quatro componentes: tempo de espera, atraso nas
filas, atraso de transmissão e atraso de propagação [Jones et al., 2005]. A primeira
componente corresponde ao tempo de espera de cada nó pelo nó de destino ou pela
chegada de um nó intermediário que possa encaminhar as suas mensagens. O atraso
nas filas corresponde aos atrasos variáveis que ocorrem nas filas dos nós antes de
uma mensagem corrente ser entregue. Em seguida, existem o atraso de transmissão
da mensagem e o atraso correspondente ao tempo de propagação do sinal (latência)
a cada contato entre dois nós;
• freqüentes desconexões - desconexões podem ocorrer pela mobilidade que provoca
constantes mudanças na topologia da rede, por péssimas condições de comunicação
(desvanecimentos), por economia de recursos como em sensores sem fio onde sen-
sores dormem para poupar energia, por negação de serviço como o ato do inimigo
sujar a freqüência (jamming) em operações militares. Estes eventos podem resultar
em uma conectividade intermitente da rede, ou seja, na inexistência de um caminho
fim-a-fim entre um nó fonte e um nó de destino.
A principal causa da Internet convencional não funcionar bem em redes com lon-
gos atrasos e freqüentes desconexões está na operação do protocolo Transmission Control
Protocol (TCP) [Postel, 1981]. O TCP é um protocolo de transporte orientado a conexão
que garante confiabilidade na entrega de dados fim-a-fim em cima de redes não confiá-
veis. O TCP foi projetado para operar independentemente da infra-estrutura de sub-rede,
não se preocupando com o tipo de tecnologia usada (ex. fibra, coaxial, par trançado, ra-
diofreqüência etc.) sobre a qual o protocolo Internet Protocol (IP) opera. Como ilustrado
na Figura 5.1, a operação do TCP pode ser dividida em três fases: estabelecimento de
conexão, transferência de dados e desconexão. O estabelecimento de conexão se faz com
a troca de três mensagens (three-way handshake). Em seguida, inicia-se a transferência
de dados, onde a boa recepção dos dados pelo destino deve ser sinalizada por reconheci-
mentos positivos (acknowledgments - ACKs). O encerramento de uma conexão TCP se
dá com a troca de quatro mensagens. Fica evidente que o bom funcionamento do TCP
requer a existência de um caminho fim-a-fim entre fonte e destino durante todo o período
correspondente à sessão de comunicação, atrasos de comunicação relativamente pequenos
e baixa taxa de erros [Fall, 2003].
Figura 5.1. As fases da operação do TCP.
Para contornar os problemas de atrasos e desconexões, as redes DTN se servem
da técnica de comutação de mensagens [Warthman, 2003] além de armazenamento per-
sistente. Na comutação de mensagens nenhum circuito é estabelecido com antecedên-
cia entre a origem e o destino, nãoexistindo qualquer fase anterior ao envio de dados.
Quando uma mensagem precisa ser enviada, ela é armazenada e encaminhada nó a nó
desde a origem até o destino. Por utilizar essa técnica, diz-se que as DTNs são redes
do tipo armazena-e-encaminha (store-and-forward), ou seja, primeiro a mensagem é re-
cebida integralmente e armazenada para, em seguida, ser enviada ao próximo nó, que
pode ou não ser o destino. Assim, não há necessidade de o nó de destino estar ativo
quando o nó de origem envia a mensagem, pois os nós intermediários podem armazenar a
mensagem e entregá-la mais tarde. Como prova deste conceito, um bom exemplo são os
resultados obtidos em [Demmer et al., 2004a] através da comparação de três protocolos
de entrega de mensagens: DTN, Simple Mail Transfer Protocol (SMTP) e Simple File
Transfer Protocol (SFTP). Inicialmente, são propostas duas configurações. A primeira
configuração representa uma comunicação comum da Internet que necessita do estabele-
cimento de uma conexão fim-a-fim antes da troca de dados. Por isso, esta é chamada de
E2E (end-to-end). Como ilustrado na Figura 5.2, no E2E cinco nós são dispostos em uma
topologia linear onde somente o nó de origem e o nó de destino executam daemons do
protocolo, enquanto os três outros nós intermediários executam o encaminhamento IP. Na
segunda configuração, é utilizada a comutação de mensagens onde cada nó armazena-e-
encaminha a mensagem salto a salto (HOP), indicada na Figura 5.2 pela linha pontilhada
que sobe até a parte central de cada nó intermediário. Nesse caso, os cinco nós executam
daemons do protocolo.
Figura 5.2. As configurações fim-a-fim (E2E) e salto-a-salto (HOP). Figura adap-
tada de [Demmer et al., 2004a].
Quatro experimentos são realizados para avaliar a utilização da largura de banda
pelos diferentes protocolos. Em cada experimento é introduzido um período de descone-
xão para cada enlace. Todas as desconexões são cíclicas, de forma que um enlace fica
ativado por um minuto e desativado por três minutos. O primeiro experimento é chamado
de “alinhado”, pois todos os enlaces são ativados ao mesmo tempo. O segundo experi-
mento é chamado de “deslocado”, pois o instante da ativação de um enlace é deslocado de
10 segundos em relação ao instante da ativação do enlace anterior. O terceiro experimento
é “seqüencial”, o que significa que somente um enlace fica ativo por vez. O último expe-
rimento é chamado de “aleatório” e, como o próprio nome indica, o instante da ativação
dos enlaces ocorre aleatoriamente. Também é avaliada a taxa máxima alcançada (MAX)
para cada um dos experimentos com o objetivo de mostrar que em alguns experimentos
a largura de banda é desperdiçada. O gráfico da Figura 5.3 apresenta os resultados dos
quatro experimentos para cada configuração (E2E e HOP) de acordo com o protocolo de
entrega de mensagens (DTN, SMTP e SFTP). Como pode ser visto pelo gráfico, em todos
os experimentos tanto o DTN (HOP) quanto o SMTP (HOP) alcançam um desempenho
notável quando comparado com os outros, com destaque para o protocolo DTN (HOP),
que em todos os experimentos permanece próximo da MAX. Estes experimentos são uma
prova incontestável de que o perfil de protocolos TCP/IP não atende às características da
DTN e que a comutação de mensagens provê bons resultados.
Figura 5.3. Percentual de utilização de largura de banda na configuração fim-
a-fim (E2E) e salto-a-salto (HOP) para os protocolos DTN, SMTP e SFTP. Figura
adaptada de [Demmer et al., 2004a].
Deve ser ressaltado que a operação armazena-e-encaminha em DTNs difere da-
quela de outros protocolos tradicionais de rede. Por exemplo, em redes IP baseadas nesta
operação, o armazenamento ocorre por um pequeno período de tempo até que os pacotes
sejam encaminhados para o próximo nó. Este armazenamento é normalmente feito por
memórias dinâmicas (ex. chips de memória de roteadores) e o tempo de armazenamento é
da ordem de milissegundos. Em contraste, como as DTNs não operam sobre enlaces que
estão sempre disponíveis, é esperado que os nós armazenem mensagens durante algum
tempo. Nesse caso, o tempo de armazenamento em DTNs pode ser até da ordem de horas
ou dias, sendo preciso alguma forma de armazenamento persistente e robusto (ex. disco
rígido, memória flash de dispositivos portáteis) para preservar as informações diante de
reinicializações no sistema.
Embora o enfoque inicial tenha sido feito em relação ao protocolo TCP, outros
protocolos usados na Internet convencional também não apresentam bom desempenho.
Protocolos de roteamento como o Border Gateway Protocol (BGP), Interior Gateway
Protocols (IGPs) (Route Information Protocol - RIP, Open Shortest Path First - OSPF),
e de resolução de nomes (Domain Name Service - DNS) devem ser revistos para DTNs.
Além destes protocolos, também podem ser citadas as aplicações voltadas aos usuários e
os protocolos de suporte, tais como HyperText Transfer Protocol (HTTP), protocolos de
compartilhamento peer-to-peer, Simple Mail Transfer Protocol (SMTP), Post Office Pro-
tocol (POP), Internet Message Access Protocol (IMAP) e File Transfer Protocol (FTP).
Pode-se dizer que estes protocolos provêem serviços que realizam entregas de datagramas
fim-a-fim, troca de mensagens de forma confiável, seleção de caminhos intra-domínios,
resolução de nomes, compartilhamento de dados, dentre outros.
Como o uso da técnica de comutação de mensagens (nó-a-nó) e o armazenamento
persistente são mandatórios em DTN, surge a questão de “em que camada” aplicar esta
tecnologia. É claro que a técnica de comutação de mensagens pode ser feita na camada
aplicação e, desta forma, os nós intermediários se comportariam como gateways de apli-
cação. No entanto, seria necessário que todas as aplicações fossem desenvolvidas levando
em conta os problemas de atraso e desconexões. Além disso, para obter interoperabili-
dade entre redes convencionais e redes DTNs é importante que as especificidades se en-
contrem acima da camada TCP. Portanto, a solução adotada pelo Internet Research Task
Force (IRTF) foi a utilização de uma sobrecamada (overlay) ao TCP/IP e logo abaixo
da camada de aplicação. Esta camada recebeu o nome de camada de agregação (bundle
layer).
Os principais conceitos, problemas e as principais propostas de soluções em DTNs
são vistas a seguir. Inicialmente, na Seção 5.2 é apresentada a proposta do IRTF para a
arquitetura das DTNs. Na Seção 5.3 é apresentado o protocolo de agregação especificado
para DTN. Na Seção 5.4 são apresentadas as principais aplicações e projetos relaciona-
dos. A Seção 5.5 apresenta o estado da arte dos protocolos de roteamento especialmente
projetados para DTNs. Finalmente, a Seção 5.6 apresenta as tendências futuras na área.
5.2. A Arquitetura DTN
A necessidade de uma nova arquitetura capaz de suprir as características pecu-
liares das DTNs foi promovida na década de 90 durante o desenvolvimento do projeto
Internet InterPlaNetária (IPN) por um grupo de engenheiros2 do Jet Propulsion Labora-
tory (JPL) da agência espacial americana NASA [Farrell et al., 2006a]. O objetivo do IPN
é definir é definir uma arquitetura de redes que permita a interoperabilidade da Internet
convencional (“terrestre”) com uma Internet Interplanetária, que envolve outros planetas
e astronaves em movimento3 [IPN, 2007]. O grande problema da Internet Interplanetária
é o atraso que pode ser de horas e até dias.
Observou-se que as soluções para o projeto IPN também atendiam aos problemas
de quebras de conexões bastante comuns em algumas redes terrestres. Assim, em 2002, o
Internet Research Task Force (IRTF) [IRTF, 2007], uma comunidade que realiza pesqui-
sas de longo prazo referentes ao funcionamento da Internet, criou um grupo de pesquisa
em redes tolerantes a atrasos (Delay Tolerant Network Research Group - DTNRG) com
o objetivo de empregar o conceito de DTN também em ambientes operacionais terres-
tres [DTNRG, 2006]. No ano de 2004, a Defense Advanced Research Projects Agency
2Grupo liderado por Vint Cerf, um dos “pais” da Internet.
3O projeto aindaestá em andamento como um grupo especial (IPN Special-Interest Group - IPNSIG)
dentro da Internet Society.
(DARPA) realizou uma chamada de trabalhos4 denominada redes tolerantes a descone-
xões (disruption-tolerant networks), também chamada DTN [DARPA, 2004]. Apesar da
diferença entre os nomes, o IPN, o DTNRG e a DARPA trabalham em busca de uma
solução comum para resolver os problemas associados às DTNs [Farrell e Cahill, 2006].
A proposta de uma arquitetura DTN é definida em um Internet Draft que descreve como
um conjunto de nós se organiza para armazenar e encaminhar mensagens em ambientes
sujeitos a atrasos longos e/ou variáveis e com freqüentes desconexões [Cerf et al., 2006].
A arquitetura DTN prevê a utilização da técnica de comutação de mensagens e
o armazenamento persistente dos dados definindo uma sobrecamada (overlay) abaixo da
camada de aplicação. Esta nova camada é denominada camada de agregação (Bundle
Layer) e o protocolo de agregação é executado em todos os nós pertencentes à rede DTN,
denominados nós DTN, da origem até o destino, à semelhança da camada IP. As “sub-
redes” são denominadas redes regionais e a arquitetura em sobrecamada permite tornar
a DTN totalmente independente das diversas redes regionais, permitindo que as aplica-
ções se comuniquem através de múltiplas regiões. Para garantir interoperabilidade com
qualquer tipo de rede, esta sobrecamada se situa acima da camada transporte das redes
que se servem do perfil de protocolos TCP/IP. Como ilustrado na Figura 5.4, as camadas
abaixo da camada de agregação são definidas de acordo com a conveniência do ambiente
de comunicação de cada região, podendo ser específicas para cada região englobada pela
DTN.
Figura 5.4. A camada de agregação.
As aplicações das DTNs enviam mensagens de tamanhos variáveis chamadas de
unidades de dados da aplicação (Application Data Units - ADUs). As mensagens são
transformadas pela camada de agregação em uma ou mais unidades de dados de protocolo
(Protocol Data Units - PDUs) denominadas agregados (bundles), que são armazenados
e encaminhados pelos nós DTN. Cabe ressaltar que o termo agregado foi escolhido para
ser usado em DTN, ao invés de transação, para evitar a associação a algum tipo de inte-
ratividade [Cerf et al., 2001] que é ineficaz em ambientes de longos atrasos e freqüentes
desconexões. Assim, nestes ambientes, por exemplo, o pedido de transferência de um
4Valor de 22 milhões de dólares (http://www.dtic.mil/descriptivesum/Y2006/DARPA/0603760E.pdf).
arquivo pode ser enviado contendo os dados necessários para a autenticação do usuário
(ex. login/senha), o nome do arquivo desejado e o diretório local onde o arquivo deve ser
entregue. Todas essas informações são “agregadas” e enviadas de uma única vez evitando
diversas trocas de mensagens que são realizadas numa transferência de arquivos realizada
em uma rede TCP/IP convencional. Como será visto na Seção 5.5, múltiplas cópias do
mesmo agregado podem existir simultaneamente em diferentes partes da rede, tanto na
memória local de um ou em mais nós DTN quanto em trânsito entre os nós.
Dependendo das características da rede regional atravessada, pode ser necessá-
rio reduzir o tamanho do agregado para que ele possa ser encaminhado. As funções de
fragmentação e reagrupamento do agregado são executadas pelo protocolo de agregação.
Após a fragmentação, cada fragmento continua sendo visto como um agregado que pode
ser fragmentado outras vezes. Dois ou mais fragmentos podem ser reagrupados em qual-
quer lugar da rede, formando um novo agregado.
5.2.1. Os Tipos de Contatos
Em DTNs não é assumido que todos os nós são alcançáveis e podem ser conta-
tados a qualquer instante. Essa característica das DTNs contrasta fortemente com o que
é assumido para a Internet convencional, que considera que as entidades comunicantes
estão sempre alcançáveis. Por isso, um conceito importante que deve ser considerado na
arquitetura DTN é o de contato. Um contato corresponde a uma ocasião favorável para
os nós trocarem dados. A arquitetura DTN classifica os contatos em: persistente, sob
demanda, programado, oportunista e previsível. Possibilidades de falhas sempre existem
para qualquer tipo de contato. Porém, dependendo do tipo de contato, as falhas podem
ser mais freqüentes, como é o caso dos contatos previsíveis. Os cinco tipos de contatos
são detalhados a seguir.
Os Contatos Persistentes
Os contatos persistentes são aqueles que estão sempre disponíveis. Uma cone-
xão Internet sempre disponível como a Digital Subscriber Line (DSL) é um exemplo de
contato persistente.
Os Contatos sob Demanda
Os contatos sob demanda são aqueles que requerem alguma ação para que sejam
instanciados, mas que, uma vez acionados, funcionam como contatos persistentes até
serem encerrados. Do ponto de vista do usuário, uma conexão discada pode ser vista
como um exemplo de contato sob demanda. Outro exemplo de contato sob demanda é em
redes de sensores que requerem o envio de uma mensagem específica para “acordar” os
sensores que estão dormindo.
Os Contatos Programados
Em algumas DTNs, uma agenda de contato pode ser preestabelecida entre dois
ou mais nós antes que ocorra a troca de informações. O horário e a duração de cada
contato são estabelecidos previamente entre os nós comunicantes. Por isso, esse tipo de
contato estabelecido é denominado contato programado. Uma característica das redes
com contatos programados é a exigência de uma sincronização do tempo na rede para que
a troca de informações seja realizada com sucesso.
As aplicações espaciais são um exemplo de rede com contatos programados, pois
a movimentação dos elementos da rede (planetas, satélites, naves espaciais etc.) e os
atrasos relativos às longas distâncias envolvidas são significativos [Burleigh et al., 2003].
Na Figura 5.5 é apresentado um cenário com dois planetas: Planeta A e Planeta B. No
Planeta A, o nó mantém um contato persistente com um satélite, que se movimenta ao
longo de uma órbita fixa e que por isso possibilita que todas as suas futuras posições
sejam conhecidas. O nó do Planeta B possui uma informação armazenada que deve ser
entregue ao nó do Planeta A. Em um determinado instante, previamente programado, o
nó do Planeta B envia uma mensagem em direção ao Planeta A. Através da Figura 5.5 (a)
é possível perceber que, no momento do envio da mensagem, o nó do Planeta B possui
um enlace desconectado/obstruído com o satélite. Entretanto, a recepção da mensagem
pelo satélite, ilustrada na Figura 5.5 (b), é realizada com sucesso, garantindo a entrega da
mensagem ao nó do Planeta A. Em aplicações terrestres pode-se imaginar comunicações
com contatos programados em uma rede de sensores onde determinados nós “acordam”
em horários preestabelecidos, voltando a “dormir”, para poupar energia, fora dos horários
programados.
Figura 5.5. Exemplo de contatos programados.
Os Contatos Previsíveis
Os contatos previsíveis são aqueles nos quais os nós podem fazer previsões sobre o
horário e a duração dos contatos com base em históricos de contatos previamente realiza-
dos. Ao contrário dos contatos programados, os contatos previsíveis possuem certo grau
de incerteza do contato. Assim, algumas rotas da origem ao destino podem ser previstas,
mas possuem alguma incerteza em relação a sua ocorrência, horário ou duração. Dado
um nível de segurança suficiente, as rotas podem ser escolhidas baseadas nas informações
de experiências passadas.
A rede rural esparsa ilustrada na Figura 5.6 é um exemplo de DTN com contatos
previsíveis. Esse tipo de rede vem sendo utilizado para oferecer acesso à Internet a baixo
custo para habitantes de áreas remotas que não são atendidas a contento pelas atuais tec-
nologias de rede [Seth et al., 2006, KioskNet, 2007, FMS, 2007, Pentland et al., 2004].
Estas áreas estão representadas na Figura 5.6 pela Região 2. Geralmente, estas áreas
se encontram a quilômetros de distância das grandes cidades com acesso à Internet em
banda larga (Região 1), de forma que não existe conectividade fim-a-fimentre o nó
fonte e o nó de destino durante todo o período correspondente à sessão de comunica-
ção. Para superar os problemas ocasionados pela conectividade intermitente entre as
duas regiões, ônibus públicos e motos são utilizados como mensageiros móveis, sendo
responsáveis pelo armazenamento, transporte e entrega de dados entre as regiões. Es-
tes mensageiros também são conhecidos como pontos de acesso móveis (mobile access
points - MAPs) [Pentland et al., 2004]. Os mensageiros móveis são equipados com um
ponto de acesso e um dispositivo de armazenamento. Assim, o upload e o download
dos dados ocorre quando o mensageiro móvel entra na área de cobertura de cada região,
também equipada com pontos de acesso. Neste cenário específico, o mensageiro móvel
desempenha o papel de agente tradutor das características incompatíveis da Região 1 e
da Região 2, além de agir como um buffer armazenando os dados que precisam ser troca-
dos entre as regiões. Em função da distância entre a área isolada e a cidade, o atraso de
comunicação geralmente é de algumas horas. Como as visitas dos mensageiros móveis
são variáveis, estando sujeitas a falhas mecânicas e problemas ambientais (ex. uma es-
trada interditada), as regiões não possuem informações precisas sobre a próxima troca de
dados [Guo et al., 2006]. Porém, podem se basear em históricos das últimas visitas dos
mensageiros móveis para estimar o horário e a duração das próximas visitas.
Figura 5.6. Exemplo de rede rural esparsa com contatos previsíveis.
Os Contatos Oportunistas
Os contatos oportunistas ocorrem diante de encontros não previamente programa-
dos entre os nós. Esse tipo de contato tem como objetivo obter vantagens de contatos
realizados totalmente ao acaso para realizar a comunicação com qualquer nó que esteja
fora do alcance de um nó fonte. Assim, utiliza-se a capacidade dos nós se comunicarem
localmente com os seus vizinhos para criar possibilidades de comunicação com outros
nós que estão fora do alcance. Esta é uma característica inédita que não existe similar
na Internet convencional. O conceito de contato oportunista permite comunicação entre
nós na qual em nenhum momento existe um caminho inteiramente conectado entre eles,
o que inviabiliza a comunicação na Internet convencional. Geralmente, os nós que es-
tabelecem contatos oportunistas desconhecem qualquer informação acerca do estado, da
localização ou dos padrões de mobilidade dos outros nós. Além disso, os nós são autôno-
mos, o que significa que cada nó possui um controle independente de si mesmo e de seus
movimentos.
Como exemplo, suponha que Maria deseja encontrar-se com sua amiga Paula para
entregar um dinheiro que estava lhe devendo. Porém, por algum motivo, Maria não con-
segue se comunicar com Paula. Certo dia, na universidade, Maria encontra Pedro, o irmão
de Paula. Sabendo que Pedro é uma pessoa confiável, Maria entrega-lhe o dinheiro, pas-
sando para ele a responsabilidade de entregar o dinheiro a Paula. Quando chega em casa,
Pedro encontra a irmã e entrega o dinheiro. Assim, apesar das duas amigas não terem se
encontrado pessoalmente (conectividade intermitente), Maria (nó fonte) conseguiu fazer
com que o dinheiro chegasse até Paula (nó de destino) através de uma pessoa intermediá-
ria (nó intermediário) que encontrou ao acaso na universidade (contato oportunista).
Esse é um exemplo que pode acontecer entre seres humanos, mas que atualmente
pode ser implementado também entre dispositivos eletrônicos sem-fio como celulares,
laptops, palmtops, pagers, Personal Digital Assistants (PDAs) etc.
O contato oportunista e a comunicação de dispositivos portáteis se constitui num
novo paradigma de comunicação entre usuários denominado Pocket Switched Networks
(PSNs) [Hui et al., 2005, Lindgren et al., 2006]. Neste trabalho, é considerado um novo
modelo de redes que atua dentro do contexto de DTN, pois realiza a comunicação na au-
sência de conectividade fim-a-fim, obtendo vantagem de qualquer oportunidade de trans-
missão ao longo do trajeto do dispositivo móvel para que o encaminhamento das mensa-
gens seja realizado até o destino.
Por exemplo, em [Leguay et al., 2006] são realizados experimentos nos quais a
movimentação de um grupo de estudantes com dispositivos de bolso bluetooth de pe-
queno alcance, denominados iMotes, são utilizados como forma de propagar um jornal
eletrônico dentro de uma universidade e em locais populares próximos como centros co-
merciais, lojas, restaurantes e bares. Dentre os resultados apresentados, são avaliados
os contatos oportunistas realizados entre os próprios integrantes do grupo de estudantes.
Além disso, também são avaliados os contatos externos, ou seja, os contatos oportunistas
do grupo de estudantes com dispositivos de pessoas comuns portando um celular, PDA,
laptop etc. Os experimentos demonstram que o fato de alguns estudantes da universidade
colaborarem com o experimento resulta em uma taxa de entrega de 90%. Além disso,
também é apresentado o interesse no uso de dispositivos externos como encaminhadores
do jornal eletrônico quando o tamanho da infra-estrutura tende a crescer.
5.2.2. O Ponto de Extremidade
A arquitetura DTN define o conceito de ponto de extremidade (endpoint DTN).
Um ponto de extremidade é um grupo de nós DTN. Um nó DTN pode ser membro de
um ou mais pontos de extremidade. A abstração de ponto de extremidade é semelhante
a um grupo multicast. Por outro lado, o ponto de extremidade pode ter apenas um nó.
Um agregado é considerado entregue com sucesso quando um subconjunto mínimo de
nós do ponto de extremidade recebê-lo sem erro. Esse subconjunto é denominado grupo
mínimo de recepção (MRG - Minimum Reception Group) de um ponto de extremidade.
O MRG pode fazer referência a um único nó, o que seria equivalente a uma transmissão
unicast, um nó dentre um grupo de nós (anycast) ou a todos os nós do grupo (multicast
ou broadcast).
5.2.3. O Identificador de Ponto de Extremidade
Um ponto de extremidade é identificado por um identificador de ponto de extre-
midade (Endpoint IDentifier - EID), que corresponde a um nome expresso sintaticamente
como um identificador uniforme de recursos (Uniform Resource Identifier - URI).
Os Esquemas URI
A sintaxe geral de um URI oferece meios simples e extensíveis para a identificação
de recursos [Berners-Lee et al., 2005]. Cada URI inicia com uma estrutura denominada
nome do esquema. Esse nome é um elemento de um conjunto de esquemas gerenciado
globalmente pelo Internet Assigned Numbers Authority (IANA) [IANA, 2007]. Como
exemplos de esquemas permanentes mais comuns gerenciados pelo IANA, destacam-se:
ftp, http, dns, pop, imap, mailto, snmp e telnet. Após o nome do esquema do URI existe
uma série de caracteres obrigatórios definidos para cada esquema. Essa parte do URI é
denominada parte específica do esquema (Scheme Specific Part - SSP). Assim, cada URI
pode ser caracterizado pela estrutura geral seguinte:
<nome do esquema> : <parte específica do esquema>
Os exemplos abaixo ilustram esquemas URI e suas variações em relação à sintaxe:
http://www.gta.ufrj.br/publicacoes/
mailto:carina@gta.ufrj.br
ftp://ftp.gta.ufrj.br
A sintaxe geral dos URIs é útil para registrar nomes de pontos de extremidade
que formam as DTNs. Como nomes, os EIDs não são obrigatoriamente relacionados à
organização da topologia ou ao roteamento. Entretanto, essas relações não são proibidas.
Como um ponto de extremidade pode ser formado por um ou mais nós DTN, conseqüen-
temente, um EID pode fazer referência a um ou mais nós DTN. Quando um EID faz
referência a um ponto de extremidade composto por mais de um nó DTN, o nome do
esquema deve definir um conjunto de regras sintáticas e semânticas que expliquem como
analisar e interpretar o SSP de um EID.
A Vinculação Tardia
O princípio de vinculação tardia (late binding) é fundamental em redes tolerantes
a atraso e desconexões. Vinculação significa interpretar a parte específica do esquema
(SSP) de um identificador de Ponto de Extremidade (EID) com o objetivo de encami-nhar uma mensagem em direção ao(s) seu(s) destinatário(s). A vinculação tardia signi-
fica que a vinculação não ocorre necessariamente na fonte no momento que a origem
envia uma mensagem para o destino. Para compreender a utilidade da vinculação tar-
dia, é importante analisar como é feita a vinculação do nome ao endereço IP na Internet
convencional. Quando se envia uma mensagem de correio eletrônico na Internet para o
destinatário fulano@gta.ufrj.br há, primeiramente, uma processo resolução de nomes de
domínio que traduz o nome do destinatário fulano@gta.ufrj.br para um endereço IP, por
exemplo 146.164.69.69. Isto é feito pelo protocolo (Domain Name System - DNS) da
Internet. Portanto, antes do envio da mensagem já se sabe o endereço do destino que é
representado pelo endereço IP do destino. Pela própria estrutura de endereçamento IP
da Internet, antes da mensagem ser enviada sabe-se, pelo endereço IP, que o destinatário
“fulano” se encontra no Brasil, na UFRJ e no Grupo de Teleinformática e Automação da
COPPE/UFRJ. Assim, a resolução de endereço, ou vinculação do nome ao endereço IP do
destino é feita antes dos dados serem enviados e, por isto, é chamada de vinculação ante-
cipada (early binding). A partir daí basta encaminhar a mensagem eletrônica salto-a-salto
até que ela chegue ao fulano. Isto funciona bem na Internet, pois assume-se que existe um
caminho da origem até o destino e sabe-se exatamente onde se encontra o destino pelo
endereço IP. Nas redes tolerantes a atrasos e desconexões isto pode não ser possível. Seja
por exemplo o caso de um destino móvel onde a associação sejam as coordenadas x e y de
onde se encontra o destino. O momento no qual a mensagem é enviada e o momento onde
a mensagem chega ao destino possuem coordenadas x e y diferentes. Assim, é fundamen-
tal prover uma maior flexibilidade nas vinculações como, por exemplo, a vinculação do
identificador de ponto de extremidade (EID) do destino na origem, ou a cada salto em um
dos nós intermediários, ou, possivelmente, no(s) destino(s).
Assim, a vinculação tardia é vantajosa porque o tempo de uma mensagem em
trânsito pode exceder o tempo de validade da vinculação, tornando a vinculação na fonte
impossível ou inválida. A maneira como a vinculação tardia opera varia de acordo com o
esquema URI utilizado [Farrell e Cahill, 2006].
5.2.4. A Transferência de Custódia
As redes tolerantes a atrasos e desconexões se servem do protocolo de agregação
e dos protocolos que operam nas camadas abaixo da camada de agregação para a retrans-
missão nó a nó em casos de perdas ou dados corrompidos. Entretanto, como os protoco-
los que operam abaixo da camada de agregação não são executados de modo fim-a-fim na
DTN, os mecanismos que provêem confiabilidade fim-a-fim só podem ser implementados
na camada de agregação [Warthman, 2003].
A camada de agregação suporta a retransmissão nó a nó através do mecanismo
denominado Transferência de Custódia (TC), que tem como objetivo passar a respon-
sabilidade da entrega de uma mensagem de um nó para outro nó, iniciando na origem
e sendo completada no destino [Fall et al., 2003]. Por exemplo, para entregas ponto-a-
ponto (unicast), isto significa mover uma cópia de uma mensagem para mais perto (em
termos de alguma métrica de roteamento) do destino. Para realizar a transferência de cus-
tódia, a camada de agregação utiliza um temporizador e retransmissões para implementar
um mecanismo de reconhecimento custódia-a-custódia. Como ilustrado na Figura 5.7,
quando um nó DTN emissor envia um agregado para o próximo nó, ele solicita a trans-
ferência de custódia e inicia o temporizador de retransmissão. Se a camada de agregação
do próximo salto aceitar a custódia, é retornado um reconhecimento (ACK) para o nó
emissor. Porém, se nenhum reconhecimento for retornado antes do temporizador expirar,
o nó emissor reenvia o agregado. O valor atribuído para o temporizador de retransmissão
pode ser distribuído entre os nós junto com a informação de roteamento, mas também
pode ser calculado localmente baseado em históricos de experiências passadas. Os nós
que aceitam a transferência de custódia são denominados custódios.
Figura 5.7. A Transferência de Custódia (TC).
A arquitetura DTN não exige que todos os nós DTN aceitem a transferência de
custódia [Cerf et al., 2006]. Por isso, não pode ser considerado um mecanismo salto-a-
salto legítimo. Em caso de não aceitação da custódia, o temporizador e o mecanismo
de retransmissão não são empregados, de forma que o sucesso da entrega de mensagens
depende somente dos protocolos subjacentes. Por exemplo, pode ser possível que um
nó tenha capacidade de armazenamento suficiente para agir como custódio, mas opte por
não aceitar a transferência de custódia quando sua capacidade de bateria estiver abaixo de
um determinado limiar. Os nós DTN também podem tomar decisões individuais sobre a
aceitação da custódia baseados, por exemplo, no roteamento, em políticas de segurança,
no tamanho, na prioridade ou no tempo máximo de vida da mensagem.
Em DTNs, um dos recursos mais disputados é o acesso ao armazenamento em
cada nó. Enquanto que em muitas redes as mensagens são simplesmente descartadas
quando a memória esgota, o mesmo não pode ser feito em DTNs se a custódia tiver
sido aceita. Um custódio só pode apagar um agregado em duas situações: primeira, se
transferir o agregado para um outro custódio; segunda, se o tempo de vida do agregado
expirar. O ideal seria o armazenamento estar bem distribuído através da rede e os nós
possuírem uma capacidade de armazenamento suficientemente persistente e robusta para
armazenar agregados até o encaminhamento ocorrer.
5.2.5. As Classes de Prioridades
A arquitetura DTN define classes de prioridades para a entrega de mensagens. Es-
sas classes diferenciam o tráfego baseadas no grau de urgência especificado pela aplicação
para a entrega das mensagens. Os serviços do sistema de correios convencionais podem
ser comparados às classes de prioridades oferecidas pela arquitetura DTN, pois o tráfego
geralmente não é interativo e, freqüentemente, possui um sentido único. Nos correios
convencionais, em geral, não há garantia quanto ao tempo que levará a entrega, contudo,
são oferecidas algumas classes de serviço: encomenda normal, encaminhamento de men-
sagens urgentes (telegrama), entrega no mesmo dia da postagem, encomenda expressa
etc.
A arquitetura DTN define três classes de prioridades: baixa (bulk), normal (nor-
mal) e expressa (expedited). A classe baixa é a de menor prioridade. Nenhum agregado
dessa classe é transportado até que todos os agregados das outras classes sejam transmi-
tidos. Os agregados da classe normal são transportados antes dos agregados da classe
baixa e os agregados da classe expressa são enviados com prioridade sobre as outras duas
classes.
5.2.6. Os Registros Administrativos e as Opções de Entrega
A arquitetura DTN define “registros administrativos” como mensagens (também
agregados) utilizadas para prover informações sobre a entrega dos agregados na DTN.
Esses registros têm certa semelhança com as mensagens ICMP (Internet Control Message
Protocol) do IP, utilizadas para diagnóstico de condições de erro da rede (ex. erros de
transmissão). A diferença é que as mensagens ICMP são retornadas para o nó fonte,
enquanto os registros administrativos também podem ser enviados para nós intermediários
da DTN.
São definidos dois tipos de registros administrativos. O primeiro tipo de registro
administrativo é composto por um relatório denominado Sinalização de Custódia. Esse
relatório é enviado por um nó DTN como resposta ao recebimento de uma solicitação
de transferência de custódia de um agregado. Um indicador booleano é utilizado para
informar ao nó que enviou o pedido se a custódia foi recusada (0) ou aceita (1). Esse tipo
de relatório pode ser enviado por qualquer nó DTN da rede. O segundo tipo de registro
administrativo é formado por vários relatórios que informam o estado do agregado, sendo
por isso denominado de relatórios sobre oestado do agregado (Bundle Status Reports -
BSRs). Os relatórios sobre o estado do agregado são: Estado da Entrega do Agregado,
Estado do Reconhecimento, Estado da Recepção do Agregado, Estado da Aceitação da
Custódia, Estado do Encaminhamento do Agregado e Estado do Agregado Apagado.
As condições para o envio desses registros administrativos estão relacionadas di-
retamente com opções de entrega definidas pela arquitetura DTN. Essas opções são de-
terminadas pela aplicação, que ao enviar uma unidade de dados pode requisitar qualquer
combinação das opções de entrega disponíveis. A informação sobre as opções requisi-
tadas pela aplicação é levada juntamente com cada agregado produzido pela camada de
agregação. São definidas oito opções básicas:
1. pedido de transferência de custódia: solicitação para que um agregado seja en-
tregue utilizando os procedimentos de transferência de custódia decritos na Se-
ção 5.2.4;
2. pedido de aceitação de custódia pelo nó fonte: a aplicação requer que o nó DTN
fonte suporte transferência de custódia para os agregados que são enviados. Se
a transferência de custódia não estiver disponível na fonte quando esta opção é
requisitada, o pedido de transferência entre a camada de aplicação e a camada de
agregação falha. Este tipo de pedido provê uma forma da aplicação exigir que o nó
DTN fonte aceite a custódia dos agregados enviados (por exemplo, armazenando
de forma persistente os agregados);
3. notificação de entrega do agregado: solicitação de um relatório do Estado da En-
trega do Agregado quando a ADU é entregue ao(s) destinatário(s). Essa opção tam-
bém é conhecida como aviso de recebimento (return receipt). Como ilustrado na
Figura 5.8, esse relatório corresponde a um aviso único enviado pelo nó de destino
para os nós que participaram do encaminhamento do agregado, podendo o relatório
chegar até o nó DTN fonte [Warthman, 2003];
Figura 5.8. Exemplo de notificação de entrega do agregado.
4. notificação de reconhecimento positivo do agregado pela aplicação: solicita-
ção de um relatório do Estado do Reconhecimento. A diferença entre o relatório
do Estado do Reconhecimento e o relatório do Estado da Entrega do Agregado é
que o primeiro relatório é gerado pela camada de aplicação do destino, enquanto o
segundo é gerado pela camada de agregação do destino;
5. notificação de recepção de agregado: solicitação de um relatório do Estado da
Recepção do Agregado. Esse relatório é gerado sempre que um agregado é recebido
por um nó DTN;
6. notificação de aceitação da custódia: solicitação de um relatório do Estado da
Aceitação da Custódia quando o agregado é aceito utilizando a transferência de
custódia. Como ilustrado na Figura 5.9, esse relatório é gerado para os nós que so-
licitaram a custódia do agregado, inclusive para o nó DTN fonte [Warthman, 2003];
Figura 5.9. Exemplo de notificação de aceitação da custódia.
7. notificação de encaminhamento do agregado: solicitação de um relatório do Es-
tado do Encaminhamento do Agregado sempre que um agregado é encaminhado
para outro nó DTN. Como ilustrado na Figura 5.10, esse relatório é gerado para os
nós que encaminharam o agregado, inclusive para o nó DTN fonte [Warthman, 2003];
Figura 5.10. Exemplo de notificação de encaminhamento do agregado.
8. notificação de apagamento do agregado: solicitação de um relatório do Estado
do Agregado Apagado. Esse relatório é enviado quando um agregado é apagado do
buffer de um nó DTN. O objetivo é informar o motivo pelo qual o descarte ocorreu.
A solicitação de relatórios sobre o estado do agregado pode resultar no aumento
inaceitável do tráfego de agregados na rede. Por isso, a arquitetura DTN define que a
geração dos relatórios seja obrigatória somente em um caso: quando um agregado aceito
sob custódia é apagado. Em todos os outros casos, a decisão sobre a geração dos BSRs
é limitada por políticas locais. Porém, é importante destacar que em muitas DTNs o en-
caminhamento de agregados é unidirecional, ou seja, um nó DTN intermediário utilizado
no encaminhamento ou o próprio nó de destino são incapazes de gerar relatórios de volta
para o nó que lhe enviou o agregado. Desta forma, a geração dos relatórios depende do
cenário DTN em questão. Por exemplo, não é recomendado o envio de relatórios em redes
de alta mobilidade com nós que se movimentam aleatoriamente.
Um protocolo de segurança pode ser opcionalmente implementado na camada de
agregação (Bundle Security Protocol) [Symington et al., 2006]. Se os procedimentos de
segurança definidos nesse protocolo estiverem habilitados, mais três opções de entrega se
tornam disponíveis:
1. pedido de confidencialidade: a confidencialidade garante o sigilo das informações
trocadas por pontos de extremidade. Neste caso, é exigido que as informações das
unidades de dados da aplicação (ADUs) sejam secretas para os nós DTN que não
sejam o nó fonte ou os nós membros do EID destino;
2. pedido de autenticação: a autenticação garante que uma dada entidade é realmente
quem ela diz ser;
3. pedido de detecção de erro: requer que as mudanças nos campos que não podem
ser alterados (ex. EID da fonte, EID de destino, carga útil) sejam fortemente veri-
ficados (ex. através de criptografia) para garantir a integridade dos dados, ou seja,
afirmar que as informações recebidas por um nó não foram modificadas durante o
trânsito ao longo da rede.
5.3. O Protocolo de Agregação
O protocolo de agregação (Bundle Protocol) é especificado em um Internet Draft
[Scott e Burleigh, 2006].
Cada agregado consiste de dois ou mais “blocos”. O termo bloco é utilizado no
lugar de cabeçalho, pois um bloco pode estar no início ou no fim da unidade de dados de
protocolo. O primeiro bloco, chamado bloco primário, é obrigatório. Esse bloco contém
as informações básicas necessárias para encaminhar um agregado até o destino e existe
apenas um bloco primário por agregado. Somente um dos blocos seguintes pode conter
a carga útil (payload) dos dados. Além desses dois blocos, cada agregado pode possuir
outros blocos com campos adicionais, denominados blocos de extensão, que ainda estão
sendo definidos na especificação do protocolo.
Diversos campos que não possuem tamanho fixo utilizam a codificação denomi-
nada valores numéricos auto-delimitantes (Self-Delimiting Numeric Values - SDNVs). O
SDNV codifica um número binário sem sinal em octetos, com sete bits de valores e com
o bit mais significativo de cada octeto igual a 1, exceto para o último octeto cujo bit mais
significativo é igual a 0 de modo a indicar o fim do SDNV. Assim, a delimitação do ta-
manho de um campo é dada pela própria codificação que indica continuação no octeto até
que o bit mais significativo de um octeto seja igual a 1. Essa codificação não é apropriada
para valores tipicamente maiores do que 56 bits, em função da sobrecarga gerada pela
adição de um bit a cada sete bits. Portanto, alguns campos não são codificados em SDNV,
mas geralmente possuem o comprimento do campo representado em SDNV. Por razões
óbvias, os campos de tamanho fixo em geral não utilizam a codificação SDNV.
O formato do bloco primário é apresentado na Figura 5.11. Nessa figura, os cam-
pos com codificação SDNV são apresentados por um número arbitrário de bytes por con-
veniência de representação. O bloco primário é formado por diversos campos. Em todos
os campos exceto nos campos versão e matriz de octetos do dicionário é utilizada a codi-
ficação SDNV.
Figura 5.11. O formato do bloco primário.
O campo versão de 1 octeto indica a versão do protocolo, sendo que a versão atual
é a de número 5.
O campo bits de sinalização de controle de processamento (bundle processing
control flags) contém vinte e um subcampos, todos de 1 bit. A codificação SDNV desses
campos gera 24 bits, representados na Figura 5.11 pelo campo bits de sinalização de
controle de processamento.
Os bits de 1 a 7 caracterizam o agregado como a seguir:
• bit 1: indica se o agregado é um fragmento;
• bit 2: indica se a unidade de dados da aplicação corresponde a umregistro adminis-
trativo;
• bit 3: sinaliza que o agregado não deve ser fragmentado;
• bit 4: indica quando uma transferência de custódia é solicitada;
• bit 5: indica que o ponto de extremidade do destino contém somente um nó;
• bit 6: indica se um reconhecimento é solicitado pela aplicação;
• bit 7: reservado para uso futuro.
Os bits de 8 a 14 estão relacionados à classe de serviço do agregado. Os bits 8
e 9 são utilizados para indicar a prioridade do agregado, sendo 00 a classe de prioridade
baixa, 01 a classe de prioridade normal e 10 a classe de prioridade expressa. Os bits 10 a
14 também estão reservados para futura utilização.
Os bits de 15 a 21 são correspondentes aos pedidos de relatórios como a seguir:
• bit 15: indica uma solicitação de um relatório sobre o Estado da Recepção do Agre-
gado;
• bit 16: indica uma solicitação de um relatório sobre o Estado da Aceitação da Cus-
tódia;
• bit 17: indica uma solicitação de um relatório sobre o Estado do Encaminhamento
do Agregado;
• bit 18: indica uma solicitação de um relatório sobre o Estado da Entrega do Agre-
gado;
• bit 19: indica uma solicitação de um relatório sobre o Estado do Agregado Apa-
gado;
• bit 20: reservado para uso futuro;
• bit 21: reservado para uso futuro.
O campo comprimento do bloco contém o tamanho total do restante dos campos
do bloco.
Os campos seguintes são deslocamento do esquema do destino (destination scheme
offset), deslocamento da parte específica do esquema do destino (destination scheme-
specific part offset), deslocamento do esquema da fonte, deslocamento da parte específica
do esquema da fonte, deslocamento do esquema do “reportar-para” (report-to scheme
offset), deslocamento da parte específica do esquema do reportar-para, deslocamento do
esquema do custódio (custodian scheme offset) e deslocamento da parte específica do es-
quema do custódio. Todos esses campos se relacionam aos deslocamentos que devem ser
utilizados a partir do início da matriz de octetos do dicionário para o esquema e para a
parte específica do esquema do destino, da fonte, do reportar-para e do custódio, respec-
tivamente. Um dos objetivos dessa configuração é evitar a replicação desnecessária de
trechos comuns de esquemas e de partes específicas de esquemas do destino, da fonte,
do reportar-para e do custódio. Por exemplo, se as URIs da fonte, do reportar-para e do
custódio forem as mesmas, o dicionário poderá conter uma só cadeia de octetos apontada
três vezes, de modo a economizar no tamanho da matriz de octetos do dicionário.
A estampa de tempo de criação (creation timestamp) é composta de dois campos
SDNV. O primeiro é o instante da estampa de tempo de criação (creation timestamp time)
do agregado, expresso em segundos desde o início do ano 2000. O segundo SDNV cha-
mado número de seqüência da estampa de tempo de criação (creation timestamp sequence
number) consiste de um número inteiro positivo monotonicamente crescente que pode ser
zerado a cada segundo. Ambos são utilizados para diferenciar agregados criados por uma
mesma fonte.
O campo seguinte corresponde ao tempo de vida (lifetime) do agregado represen-
tado em segundos a partir do seu tempo de criação.
O comprimento do dicionário contém o tamanho da matriz de octetos do dicioná-
rio.
A matriz de octetos do dicionário é formada pela concatenação dos nomes de
esquemas e dos nomes de partes específicas de esquemas terminados com o caracter null
de todos os pontos de extremidade utilizados no bloco primário.
Os campos seguintes somente são utilizados no caso de fragmentos. Estes blocos
são representados na Figura 5.11 pela cor cinza. O primeiro indica o deslocamento do
fragmento em relação ao início da unidade de dados da aplicação. O segundo campo
corresponde ao tamanho total da unidade original de dados da aplicação. O tempo da
estampa de tempo de criação junto com o identificador do ponto de extremidade da fonte
e no caso do agregado ser um fragmento o deslocamento do fragmento e o comprimento
da carga útil identificam o agregado.
O formato do bloco de carga útil do agregado é apresentado na Figura 5.12. Esse
bloco é formado pelos campos tipo do bloco, bits de sinalização de controle de proces-
samento de bloco, comprimento do bloco e carga útil. Os campos bits de sinalização de
controle de processamento de bloco e comprimento de bloco são SDNVs. O tipo de bloco
e a carga útil não utilizam essa codificação de forma análoga aos campos versão e matriz
de octetos do dicionário do bloco primário.
Figura 5.12. O formato do bloco de carga útil.
O primeiro campo de 8 bits identifica o tipo de bloco. No caso do bloco de carga
útil, o valor desse campo é 1.
O campo bits de sinalização de controle de processamento de bloco contém sete
subcampos de 1 bit cada, como a seguir:
• bit 1: indica que o bloco deve ser replicado em todos os fragmentos;
• bit 2: indica que um relatório de status deve ser transmitido se o bloco não puder
ser processado;
• bit 3: indica que o agregado deve ser apagado se não puder ser processado;
• bit 4: indica se o bloco é o último;
• bit 5: indica que o bloco deve ser descartado se não puder ser processado;
• bit 6: indica que o bloco foi encaminhado sem ter sido processado;
• bit 7: está reservado para uso do protocolo de segurança.
O comprimento do bloco contém o tamanho do restante do bloco, ou seja, da carga
útil. O último campo contém a carga útil do bloco.
5.4. As Aplicações e os Projetos
Os conceitos de redes tolerantes a atrasos e desconexões (DTNs) podem ser apli-
cados em acesso “não usual” à Internet, monitoramento, comunicação submarina, comu-
nicação em ambientes de batalha e comunicação espacial.
Diversas localidades do mundo não possuem a infra-estrutura necessária para a
utilização de aplicações comuns como o correio eletrônico e a World Wide Web (WWW).
Normalmente são regiões rurais ou regiões residenciais habitadas por pessoas de baixo
poder aquisitivo. Essas localidades encontram-se, em geral, afastadas dos grandes cen-
tros, onde existem diversas formas de acesso à Internet como a banda larga e o modem
discado. Há atualmente uma grande preocupação em relação ao isolamento dessas áreas
excluídas digitalmente. Como as soluções convencionais de redes são muito caras ou não
podem ser implementadas nessas áreas, uma alternativa corresponde ao uso de DTNs de
forma a lidar com as conexões intermitentes que ocorrem nas tentativas de comunicação
entre a região “rica” e a região excluída digitalmente. “Mulas de dados” (data MULES)5
são em geral empregadas para fazer o transporte de dados entre as regiões. Diversos
projetos atuam nesse contexto de integração digital em países subdesenvolvidos.
O grupo de pesquisa Technology and Infrastructure for Emerging Regions (TIER)
[TIER, 2007] da Universidade da Califórnia em Berkeley tem por objetivo levar a revolu-
ção da tecnologia de informação às populações dos países em desenvolvimento. O grupo
atua em diversas áreas como educação, saúde, comunicação sem fio, armazenamento dis-
tribuído e tecnologias da fala. O projeto TierStore procura contornar as dificuldades exis-
tentes para a execução de aplicações como o correio eletrônico e a web em regiões com co-
nectividade intermitente ou sem conectividade [TierStore, 2007, Demmer et al., 2004b].
O TierStore utiliza um ou mais centros de dados com acesso à Internet para prover um
armazenamento confiável e permanente. Servidores proxies e dispositivos podem ser uti-
lizados para fazer um armazenamento prévio de dados de modo a aumentar o acesso aos
dados compartilhados. A comunicação entre os servidores proxies e os centros de da-
dos pode ser realizada através de satélites Low Earth Orbit (LEO), cuja conectividade é
intermitente; e entre os servidores proxies e os dispositivos pode-se usar redes sem fio
tradicionais que também podem possuir conectividade intermitente. Em função de diver-
sas aplicações utilizarem armazenamento de arquivos como interface entre a aplicação e a
rede e também em função da conectividade intermitente,o TierStore utiliza um sistema de
armazenamento hierárquico de arquivos em cima do protocolo de agregação (Seção 5.3).
Um protótipo foi testado no Camboja e o projeto continua ainda em desenvolvimento.
O projeto Sámi Network Connectivity [Sámi, 2007] tem como objetivo principal
prover acesso à Internet ao povo Sámi, que é uma população nômade da região da Suécia
e de outros países escandinavos. Os Sámis vivem principalmente do pastoreio de renas,
passando grande parte do tempo fora de suas vilas sem contato com outros Sámis que
ficam nas vilas. Esse povo não possui nenhum tipo de comunicação confiável na maioria
das áreas nas quais trabalham e vivem. Em função disso, o projeto utiliza o conceito de
5O termo MULE vem do acrônimo Mobile Ubiquitous LAN Extensions usado por [Shah et al., 2003] e
apresentado na Seção 5.5.2. O termo Data Mule tem sido bastante usado em DTNs e os autores assumiram
a tradução “mula de dados” para indicar a trasferência de informações por veículos motorizados, pessoas
ou animais.
DTN para prover correio eletrônico, acesso à web e transferência de dados aos Sámis. Um
projeto piloto foi iniciado em 2004 em uma das vilas Sámis. O protocolo de agregação
é utilizado para mover dados entre nós utilizando roteamento oportunístico (Seção 5.5)
através de nós fixos e móveis. Os nós móveis periodicamente fazem o trajeto entre as
comunidades residenciais, passando por pontos onde os agregados podem ser trocados e,
também, por outros pontos com acesso à Internet. Futuramente pretende-se monitorar os
rebanhos de renas através da utilização de redes de sensores e de veículos utilizados na
neve para servirem como mulas de dados de forma a transportar os dados obtidos pelos
sensores.
O Wizzy Digital Courier [Wizzy Digital Courier, 2007] é um projeto que visa ofe-
recer acesso à Internet a escolas rurais da África do Sul. Esse acesso pode ser feito através
da utilização à noite de modens discados em função do menor custo das ligações (custo
fixo por 12 horas) ou através de um mensageiro (courier) para as localidades que não
possuem telefone. Nesse caso, o mensageiro utiliza uma motocicleta ou uma bicicleta,
como uma mula de dados, para transferir os dados entre as localidades sem acesso e as
com acesso à Internet. O transporte é realizado através de dispositivos de armazenamento
com interface USB (pen drives) ou através de redes sem fio, com as quais não é necessário
entrar na escola para obter os dados. Atualmente seis escolas estão sendo atendidas por
esse serviço.
A First Mile Solutions [FMS, 2007] também trabalha com o objetivo de prover
acesso à Internet em áreas remotas não atendidas por esse serviço. As mulas de dados,
aqui chamadas de pontos de acesso móveis, são ônibus, motos ou barcos, que são respon-
sáveis pelo transporte físico dos dados entre quiosques das vilas e os grandes centros. A
organização utiliza uma arquitetura proprietária chamada DakNet e desenvolve produtos
especializados como hubs e pontos de acesso. Há projetos pilotos implementados em
Ruanda, Camboja, Costa Rica e Índia.
Ainda na classe de acesso não usual à Internet, alguns projetos são voltados para
a provisão de acesso sem a vertente de inclusão digital em regiões em desenvolvimento.
O projeto KioskNet [KioskNet, 2007, Seth et al., 2006] da Universidade de Water-
loo, no Canadá, provê acesso à Internet confiável e de baixo custo a quiosques rurais, nos
quais são realizados serviços de cartório, de consultas médicas e relativas a agricultura,
e outros. Nesse projeto a tolerância à desconexão surge em função dos problemas de
energia existentes nos países em desenvolvimento e dos custos de outras soluções. Cada
quiosque possui um ou mais computadores baratos e simples e um equipamento chamado
controlador que se comunica por rádio com computadores carregados em ônibus, carros
e caminhões (Figura 5.13). Esses veículos oportunisticamente fazem o papel de mula
de dados, transportando os dados dos quiosques para gateways com acesso à Internet e
vice-versa. Os pesquisadores do projeto estenderam o protocolo de agregação, incorpo-
rando por exemplo um encaminhamento de caminho reverso. Uma vila da Índia recebeu
a primeira implementação da solução em 2006.
O Drive-thru Internet [Drive-thru Internet, 2007] é um projeto da Universidade
de Tecnologia de Helsinki que visa prover acesso à Internet a usuários em veículos tra-
fegando em estradas a velocidades que podem chegar a quase 200 km/h. Colocam-se
pontos de acesso à Internet espalhados pela cidade, estradas comuns e estradas sem li-
Figura 5.13. Visão geral do KioskNet [KioskNet, 2007].
mite de velocidade utilizando a tecnologia IEEE 802.11. Em função do acesso intermi-
tente obtido pela passagem pelos pontos de acesso, um protocolo que habilita sessões de
comunicação de longa duração na presença de conectividade intermitente foi desenvol-
vido [Ott e Kutscher, 2005].
O projeto DieselNet [DieselNet, 2006] da Universidade de Massashusetts Amherst,
nos Estados Unidos, se serve de uma rede formada por 40 ônibus da cidade de Amherst,
cobrindo uma área total de 150 milhas quadradas. Os ônibus são equipados com compu-
tadores e três antenas de radiofreqüência: um ponto de acesso IEEE 802.11b para pro-
ver acesso Dynamic Host Configuration Protocol (DHCP) aos passageiros e transeuntes,
uma segunda interface IEEE 802.11b que constantemente procura outros ônibus e ofertas
DHCP e um rádio de longo alcance que permite a comunicação com as estações recep-
toras das informações coletadas. Além disso, um dispositivo GPS (Global Positioning
System) grava periodicamente a localização de cada ônibus. O software embarcado per-
mite realizar atualizações das aplicações e capturar informações sobre a mobilidade dos
ônibus e a conectividade e vazão da rede.
Diversos tipos de aplicações de monitoramento empregam atualmente redes de
sensores. Essas redes em geral se caracterizam por nós organizados em clusters, sendo
que cada nó possui capacidade limitada de processamento, pouca memória e energia res-
trita. Um dos maiores problemas em redes de sensores é o gerenciamento de energia. Em
geral, os nós procuram se coordenar para economizarem energia como um todo. Isso faz
com que as comunicações entre os nós sensores estejam sujeitas a atrasos em função de
um ou mais nós estarem em um estado de conservação de energia, impedidos de transmitir
ou receber dados. Esse problema de energia é ainda mais grave para os nós que estão na
vizinhança de um gateway, pois a quantidade gasta de energia nesse caso é ainda maior,
podendo levar a um particionamento da rede. De modo a diminuir esses problemas, DTNs
estão sendo empregadas em diversos projetos.
O projeto SeNDT (Sensor Networking with Delay Tolerance) [SeNDT, 2005], de-
senvolvido pelo Trinity College Dublin, tem por objetivo auxiliar autoridades públicas,
Organizações Não Governamentais (ONGs) e empresas no monitoramento do meio am-
biente. O projeto utiliza redes de sensores tolerantes a atrasos a fim de possibilitar o
monitoramento da qualidade da água de lagos e da poluição sonora em rodovias. Um
problema enfrentado pelo projeto é a grande extensão geográfica do lago escolhido para
monitoramento, que impede o uso das redes de sensores tradicionais, devido ao elevado
custo da implementação de uma rede altamente densa. Para contornar esse problema,
foram utilizadas tecnologias de DTNs. Os sensores (Figura 5.14) foram divididos em re-
giões e mulas de dados trafegam entre essas regiões, garantindo a conectividade da rede.
A outra aplicação do projeto é o monitoramento da poluição sonora em rodovias. Para
isso foram instaladas unidades de sensoriamento, equipadas com antenas IEEE 802.11,
que enviam as informações coletadas mediante uma consulta do operador, que pode per-
manecer em seu veículo durante a operação. Essa solução mostrou-se bastante vantajosa
devido ao baixo custo, robustez e tolerância a atrasos.
Figura 5.14. Modelo de sensor usado no projeto SeNDT [SeNDT, 2005].
No projeto ZebraNet [ZebraNet, 2002] da Universidadede Princeton, nos Esta-
dos Unidos, são utilizados nós sensores sem fio, que são inseridos em colares colocados
em zebras (Figura 5.15) e coletam periodicamente informações sobre a localização dos
animais. Para determinar a localização de cada zebra, cada colar utiliza um sistema de
posicionamento global (GPS) que periodicamente obtém as coordenadas da posição da
zebra e as armazena em uma memória flash no colar. Como não existe nenhum serviço
celular ou uma comunicação broadcast cobrindo a região, as informações são armazena-
das nos colares para que, em seguida, sejam enviadas para uma estação-base móvel. No
caso do projeto, a disponibilidade da estação-base móvel é esporádica, pois ela corres-
ponde a um carro conduzido pelos pesquisadores que coletam as informações enquanto
o veículo está em movimento pela região. Como nem todos os colares estão dentro do
alcance da estação-base, dados podem não ser enviados diretamente para a estação-base.
Para solucionar esse problema, os colares também trocam informações entre si, salto-
a-salto, de forma que a maior quantidade possível de informação chegue até a estação-
base [Juang et al., 2002]. O projeto ZebraNet utiliza um sistema de entrega de mensagens
de forma assíncrona e estuda a relação entre o consumo de energia dos colares de acordo
com o tipo de protocolo adotado para a troca de informações. Assim, como os nós da
rede (as zebras e a estação-base móvel) estão em constante movimento, a topologia da
rede muda freqüentemente, provocando inúmeras conexões e desconexões. Todas essas
características resultam em uma conectividade intermitente tanto entre as zebras quanto
entre as zebras e a estação-base móvel.
Figura 5.15. Zebra com um colar-sensor no pescoço [Farrell e Cahill, 2006].
O projeto CarTel [Hull et al., 2006] do Instituto de Tecnologia de Massachusetts
(MIT), nos Estados Unidos, consiste em um sistema computacional móvel formado por
nós móveis equipados com sensores capazes de coletar, processar, enviar e visualizar os
dados sensoriados. Os nós são automóveis nos quais foram embarcados computadores
acoplados a uma série de sensores. Cada nó armazena e processa localmente as informa-
ções sensoriadas antes de enviá-las a uma estação central, onde os dados são armazenados
em um banco de dados para futuras análises e visualizações. O sistema CarTel é robusto à
conectividade intermitente e variável da rede. Os nós utilizam contatos oportunistas, atra-
vés de conexões Wi-Fi e Bluetooth à Internet, ou mulas de dados para se comunicar com a
estação central. A estação central e os nós móveis utilizam uma pilha de protocolos para
DTNs denominada CafNet para se comunicar. O sistema CarTel foi implementado em
seis carros nas cidades de Boston e Seattle nos Estados Unidos. O sistema tem sido utili-
zado para analisar tempos de deslocamentos nas cidades, implementações metropolitanas
de redes sem fio e funcionamento dos automóveis.
Existem também alguns projetos que implementam redes de comunicação de da-
dos submarinas. A comunicação submarina não utiliza radiofreqüência devido ao seu
pequeno alcance na água, pois o alcance de uma tecnologia WiFi se mediria em centíme-
tros. Redes acústicas, usando sonares a taxas da ordem de 1 kbps, são em geral utilizadas
para viabilizar uma comunicação debaixo d´água. Este meio de comunicação pode ser
considerado hostil uma vez que apresenta desvanecimento, múltiplos caminhos, reflexões
(no fundo e na superfície do mar) etc. Assim, a taxa de erros neste meio é considerável
mesmo com o uso de pequenos pacotes com códigos corretores de erros. O barulho de
um navio passando perto destas redes normalmente inviabiliza qualquer transmissão por
dezenas de minutos. Além disso, a velocidade do som na água é de cerca de 1500 m/s,
muito menor do que a velocidade da luz no vácuo que é de 3x108 m/s. Essa velocidade
de propagação faz com que, para uma mesma distância, o atraso de propagação do som
na água seja muito maior do que o atraso para a luz no ar. Redes de múltiplos saltos são
utilizadas para cobrir grandes áreas, portanto deve ser dada atenção especial às aplicações
sensíveis ao atraso [Sozer et al., 2000]. As interrupções, a alta taxa de erro e o longo
atraso sugerem o uso de DTNs nas comunicações submarinas. O projeto Seaweb da ma-
rinha americana [Rice, 2005] provê funcionalidades de alcance, localização e navegação,
utilizando redes formadas por bóias, veículos submarinos autônomos e nós repetidores.
Em 1998, a agência norte-americana Defense Advanced Research Projects Agency
(DARPA) financiou um grupo no laboratório de pesquisa da NASA, denominado Jet Pro-
pulsion Laboratory (JPL), como parte da iniciativa chamada Next Generation Internet. O
objetivo era projetar uma arquitetura para a Internet Interplanetária (InterPlaNet - IPN). A
idéia do projeto era combinar os trabalhos de padronização das comunicações espaciais
com o estado da arte das técnicas desenvolvidas pela comunidade da Internet. O obje-
tivo final era prover comunicação fim-a-fim em um ambiente interplanetário multirredes.
O nome Internet Interplanetária foi deliberadamente escolhido para sugerir uma integra-
ção futurística das infra-estruturas de comunicação terrestre e espacial a fim de prover
o avanço da inteligência humana através do Sistema Solar. Recentemente, o projeto da
Internet Interplanetária deixou de ser financiado pela DARPA e passou ao domínio da
NASA. A arquitetura da Internet Interplanetária possui três princípios básicos. O primeiro
princípio consiste em utilizar os próprios protocolos da Internet, ou protocolos baseados
neles, para formar redes locais de baixo atraso. Outro princípio visa a construção de uma
rede dorsal (backbone) especializada para interconectar essas redes locais. Espera-se que
essa rede dorsal inclua satélites encaminhadores de dados. O terceiro princípio visa a
formação de uma “rede de internets”. Da mesma forma que a pilha de protocolos TCP/IP
possibilitou a formação de uma “rede de redes” com a Internet, a Internet Interplanetária
utilizará a sobrecamada de agregação (Seção 5.2) para integrar um conjunto heterogêneo
de internets.
5.5. Os Protocolos de Roteamento
Um desafio comum a todas as categorias de DTN é o roteamento, pois é preciso
projetar protocolos capazes de superar os problemas dos atrasos extremamente longos e
das freqüentes desconexões, já que os protocolos convencionais não estão aptos a mani-
pular eficientemente a transmissão de dados em DTNs. É importante observar que em
algumas DTNs é necessário determinar rotas na rede sem que exista um caminho fim-a-
fim entre a fonte e o destino no momento do cálculo da rota.
Nesta seção, é apresentado o estado da arte dos principais protocolos de rotea-
mento projetados para DTNs. Como existem vários tipos de DTN, diferentes soluções
foram propostas na literatura. De acordo com [Zhang, 2006], estas propostas podem ser
analisadas de acordo com o grau da informação disponível sobre a topologia da rede. Por
isso, as DTNs são divididas de acordo com o cenário, determinístico ou estocástico.
5.5.1. O Cenário Determinístico
Em DTNs, a topologia da rede é dinâmica, pois alguns enlaces podem existir
durante apenas alguns intervalos de tempo. Como conseqüência, a conectividade de uma
rede DTN é variável ao longo do tempo e, de forma mais grave ainda, pode ser possível
que dois nós específicos nunca estejam conectados, ou seja, em um instante qualquer não
existe um caminho entre a origem e o destino. No entanto, utilizando armazenamento
persistente e um protocolo de roteamento específico, estes nós podem se comunicar.
Como visto anteriormente, o tempo durante o qual um enlace existe é chamado
de contato. Os contatos podem ser determinísticos, previsíveis ou aleatórios. Quando
todos os contatos são determinísticos, diz-se que o cenário é determinístico, ou seja, tem-
se conhecimento de quando ocorrem os contatos da rede ou, em última instância, da
topologia da rede em qualquer instante de tempo.
A topologia de rede é normalmente modelada porum grafo, onde os vértices são
os nós da rede e os arcos são os enlaces de comunicação. Numa rede tradicional, o
conjunto de enlaces é fixo e na maior parte do tempo a rede está conectada. Desta forma,
a tarefa do algoritmo de roteamento é encontrar um caminho entre dois nós neste grafo.
Em geral, o algoritmo procura um caminho da origem até o destino que minimize alguma
métrica, como por exemplo, o atraso ou o número de enlaces no caminho. O caminho
com o menor número de enlaces, ou menor número de saltos, é chamado o caminho mais
curto entre dois nós da rede. Este caminho pode ser calculado utilizando o algoritmo de
Dijkstra, ou do “caminho mais curto primeiro” (Shortest Path First - SPF). O algoritmo
de Dijkstra constrói uma lista de caminhos ordenados por comprimento. A cada passo,
o algoritmo retira o primeiro caminho desta lista, o mais curto. O algoritmo termina
quando foi descoberto o caminho mais curto para o destino desejado. Por outro lado,
em uma DTN, os enlaces podem existir apenas por intervalos de tempo, que podem ser
determinados ou desconhecidos. Se estes contatos são conhecidos, a topologia da DTN
é determinística, e é possível modelá-la por um grafo temporal no qual são associados
tempos de existência aos arcos do grafo. Na seção a seguir, um modelo de grafo temporal
encontrado na literatura é apresentado. O algoritmo de Dijkstra pode ser utilizado em
grafos temporais, mas exige modificações, como apresentado a seguir.
Nos cenários determinísticos, assume-se que a duração dos contatos é conhecida.
No entanto, pode-se assumir também que mais alguma informação é conhecida como,
por exemplo, a capacidade de armazenamento dos nós da rede. Assim, dependendo
da quantidade de informação disponível, diferentes algoritmos podem ser construídos.
Em [Jain et al., 2004] diferentes tipos e quantidades de informação acerca da DTN são
classificadas e modeladas por “oráculos”. Um oráculo é simplesmente uma abstração.
Cada oráculo é capaz de responder a quaisquer perguntas sobre um assunto, por exemplo,
a quantidade de buffer de um nó qualquer da rede. Algoritmos que exploram diferentes
oráculos são comparados na Seção 5.5.1.2.
5.5.1.1. O Modelo de Grafo Temporal
Ferreira propõe um modelo de grafos evolutivos para redes ad hoc móveis que
pode ser aplicado a redes DTN [Ferreira, 2004]. Como nas DTNs, em redes ad hoc a
mobilidade dos nós pode fazer com que haja muitas desconexões e que uma rota fim-
a-fim entre dois nós da rede nunca venha a existir. No entanto, se os nós armazenarem
mensagens e as encaminharem escolhendo os momentos adequados, estas podem ser en-
tregues, como em uma DTN. No modelo proposto, um grafo evolutivo é composto por
uma seqüência indexada de subgrafos, onde o subgrafo associado a um índice corres-
ponde à topologia da rede durante o intervalo de tempo correspondente àquele índice.
Pode-se representar um grafo evolutivo por um conjunto de vértices, e enlaces, como em
um grafo normal, e adicionando-se aos enlaces etiquetas com os índices correspondentes
aos intervalos de tempo em que o enlace é válido, como na Figura 5.16. Nesta figura, o
enlace entre os nós A e B existe durante os intervalos de tempo 1, 2, 3 e 4, enquanto que
o enlace E-G existe apenas durante o intervalo de tempo 5.
Figura 5.16. Exemplo de grafo temporal de uma DTN.
Num grafo evolutivo, podem ser definidas jornadas, sinônimo de rotas que são
construídas levando-se em consideração as restrições de tempo de existência dos enlaces.
Uma jornada é constituída de uma seqüência de enlaces, da mesma forma que uma rota
em um grafo normal. No entanto, em uma jornada deve ser levada em consideração a
restrição de que o próximo enlace nunca pode ser um enlace que só existiu em subgrafos
passados. Assim, uma mensagem não pode ser transmitida sobre um enlace que só existiu
antes do envio da mensagem. Por exemplo, na Figura 5.16, uma mensagem pode ser
transmitida do nó A para o nó G usando os enlaces A-B, B-C, C-F e F-G. Esta jornada A-
B-C-F-G pode ser realizada entre os intervalos de tempo 1 e 3, pois respeita os intervalos
de existências dos enlaces envolvidos. Já o caminho A-B-D-G não constitui uma jornada,
pois uma mensagem não pode ser enviada de B para D antes do intervalo de tempo 3; por
outro lado, o enlace seguinte no caminho só existe durante os intervalos 1 e 2.
A partir dos conceitos de grafo evolutivo e jornadas, podem ser construídos al-
goritmos com diferentes métricas como objetivo. Em [Ferreira, 2004] são propostos três
algoritmos baseados em modificações do algoritmo de Dijkstra. O primeiro tenta encon-
trar a “jornada mais cedo”, ou seja, a jornada que faz com que a mensagem chegue o
mais cedo possível no nó de destino. Na Figura 5.16 a jornada mais rápida entre A e G
seria A-B-C-F-G. O segundo algoritmo tenta encontrar a jornada com o menor número
de saltos. Na Figura 5.16, esta jornada seria A-E-G. Já no terceiro algoritmo, o objetivo
é encontrar a jornada que gasta o menor tempo para entregar a mensagem. Neste caso,
devem ser levados em conta os tempos de transmissão e de propagação das mensagens
sobre os enlaces. Note que a jornada “mais cedo” é diferente da jornada “mais rápida”.
Imagine um trabalhador que realiza o trajeto casa-trabalho. Saindo de casa às 7:30 h, o
trajeto dura 1 hora, e o trabalhador chega às 8:30 h. Suponha que se ele sair de casa às
11:00 h, quando há muito menos tráfego, ele conclua o mesmo trajeto em 20 minutos. Na
primeira jornada o trabalhador chega mais cedo, na segunda, mais rápido.
5.5.1.2. O Modelo de Oráculos de Informação
Em [Jain et al., 2004] foi feito um estudo sobre os algoritmos de roteamento para
redes DTN em cenários determinísticos. A quantidade de informação conhecida da rede
foi dividida em oráculos de conhecimento. Como apresentado a seguir, é discutível se
as informações providas por cada um dos oráculos podem ser obtidas em uma aplicação
real. No entanto, a importância deste trabalho está na classificação do tipo de informação
e no quanto cada uma destas informações pode melhorar o desempenho do algoritmo de
roteamento.
Os Oráculos
As informações acerca das DTNs foram divididas em quatro oráculos distintos.
Cada oráculo é uma abstração que corresponde a dizer “a informação sobre o assunto está
disponível para todos os nós”. Obviamente, dependendo da informação, um determinado
oráculo pode ser ou não realizável na prática. A hipótese de base é que, como se trata de
um cenário determinístico, a movimentação de todos os nós é conhecida e, portanto, os
instantes e durações de todos os contatos também o são.
O primeiro oráculo é o “Oráculo de Resumo de Contatos”. Este oráculo fornece
informações resumidas sobre os contatos, ou seja, ele é capaz de dizer o tempo médio
necessário até que um novo contato seja realizado entre dois nós, mas não o instante e a
duração exata dos contatos. O Oráculo de Resumo de Contatos fornece, portanto, uma
informação invariante no tempo sobre os contatos.
Já o “Oráculo de Contatos” possui mais informação que o primeiro. Este oráculo
é capaz de responder o instante de início e a duração de todos os contatos entre dois nós
quaisquer da rede. Ou seja, o Oráculo de Contatos é o equivalente do grafo temporal
completo da DTN.
O “Oráculo de Ocupação” é capaz de informar, em qualquer instante de tempo, a
ocupação dos buffers de transmissão em qualquer nó da rede. Esta informação pode ser
usada, por exemplo, para evitar congestionamentos. É importante notar que a informação
provida por este oráculo é dependente, ela própria, do algoritmo de roteamento utilizado.
Este é o oráculo de mais difícil realização prática.
O último oráculo é o “Oráculo de Demanda de Tráfego”, capaz de informar a
demanda de tráfego de todos os nós em qualquer instante de tempo. Para tanto, este
oráculo precisa conhecer todas as mensagens que todos os nós da rede desejam enviar a
qualquer tempo.
Os Algoritmos
O primeiro algoritmo de roteamento é o mais simples. Quase nenhuma informa-
ção da rede é utilizada e não há “cálculo” do caminho. No