Fragmentaci
´
on y Mezcla de redes ad-hoc
usando el protocolo ANTop
Fragmentation and assimilation of ad-hoc networks using the ANTop protocol
Pablo Torrado
Facultad de Ingenier
´
ıa, Universidad de Buenos Aires
ptorrado@cnet.fi.uba.ar
Abstract− The ANTop (Adjacent Network Topology) is a
distributed and decentralized protocol for ad-hoc networks.
It is based on a hypercube address space where the nodes
names are mapped to assure their adjacency, allowing greedy
routing protocols to find the optimum route. A distributed
mechanism, to match real names to the network address, is
implemented by distributed hashing tables. In this work we
address the partition and assimilation networks problems, to
complete the functionalities of ANTop, and we also provide a
complete implementation for Linux systems.
Keywords: ad-hoc networks, IoT, Internet
Resumen—ANTop (Adjacent Network Topology) es un pro-
tocolo distribuido y descentralizado para redes ad-hoc. Est
´
a
basado en un hipercubo para el espacio de direccionamiento,
donde se asegura la adyacencia de las direcciones de los nodos,
lo cual permite que protocolos de ruteo glutones encuentren
la ruta
´
optima. Un mecanismo distribuido, que establece una
analog
´
ıa entre los nombres reales y las direcciones de red,
es implementado usando tablas distribuidas de hash. En este
trabajo nosotros estudiamos los problemas de partici
´
on y
mezcla, con el fin de completar las funcionalidades de ANTop,
y proveer una implementaci
´
on en sistemas Linux.
Palabras clave: redes ad-hoc, IoT, Internet.
I. INTRODUCCI
´
ON
En el presente trabajo se presenta nuevas funcionalidades
al protocolo de ruteo ANTop (Adjacent Network Topology)
para redes ad-hoc, desarrollado en los trabajos [1], [2],
[6], [11], [13]. El alcance de este trabajo es responder
a la aplicaci
´
on del protocolo de ruteo ANTop ante las
problem
´
aticas de fragmentaci
´
on y mezcla de redes, muy
com
´
un en redes ad-hoc y tambi
´
en de sensores. A parte
de ANTop, en la actualidad existen protocolos de ruteos
para redes ad-hoc como B.A.T.M.A.N. (Better Approach
To Mobile Ad-hoc Networking) [5], [7] y BABEL [3],
[4], [8]–[10], que cuyas diferencias b
´
asicas con nuestra
propuesta reside en que sus algoritmos de ruteo se basan en
un conocimiento global de la estructura de la red (ejemplo
cada nodo calcula el pr
´
oximo salto hacia el nodo destino,
para cada destino). Para ello, dichos protocolos deben de
enviar paquetes a la red de tal forma de descubrir cu
´
al es la
ruta mas eficiente de un nodo hacia al otro como destino,
disminuyendo el ancho de banda
´
util disponible en la red.
En cambio, ANTop propone un direccionamiento basado en
un hipercubo, definiendo as
´
ı la estructura de la red sin la
necesidad del env
´
ıos de paquetes de reconocimiento de red,
lo que permite ahorra energ
´
ıa y capacidad de los canales
para la transmisi
´
on de la informaci
´
on
´
util.
En este articulo se propone presentar las caracter
´
ısticas
principales del protocolo ANTop en primer lugar, para
dar el contexto de su funcionamiento; y luego detallar las
problem
´
aticas de fragmentaci
´
on y mezcla con sus algoritmos
para mitigarlos.
II. EL PROTOCOLO ANTOP
Como se menciono antes, ANTop es un protocolo di-
se
˜
nado para redes ad-hoc, con un esquema descentralizado,
ya que todos los nodos conectados tienen igual jerarqu
´
ıa,
pudiendo cumplir las mismas funciones, como ser la asig-
naci
´
on de direcciones a los nuevos vecinos, resoluci
´
on de
direcciones a partir de un identificador universal o efectuar
el ruteo de paquetes. Es por esta raz
´
on que su direcci
´
on,
dependiente de su ubicaci
´
on en la red, cambiar
´
a frecuente-
mente; y por lo tanto se vuelve imprescindible contar con
un identificador universal del nodo. Este identificador, sin
embargo, no ser
´
a suficiente para poder rutear un paquete
hacia su destino. En respuesta a
´
este requerimiento, surge el
concepto de Distributed Hash Tables (DHT), es decir, Tablas
de Distribuidas de Hash. Incorporando esta abstracci
´
on a la
capa de red, ANTop define una t
´
ecnica de ruteo indirecto,
en la cual nodos llamados Rendez Vous son responsables
de guardar la direcci
´
on de red de otros nodos, asoci
´
andola
con su identificador universal. Como se dijo anteriormente,
cualquier nodo que se conecte a la red ad-hoc podr
´
ıa actuar
como Rendez Vous.
II-A. Ruteo Indirecto
Cada nodo cuenta con tres direcciones. La primera es
la direcci
´
on universal U, la cual es conocida por cualquier
otro nodo que quiera establecer una comunicaci
´
on. Al ser
totalmente independiente de la capa de red, puede ser cual-
quier tipo de identificador. La segunda direcci
´
on de un nodo,
la relativa R, es aquella dependiente de la ubicaci
´
on en la
topolog
´
ıa de red y la que nos permitir
´
a rutear los paquetes. Si
el nodo se mueve, este identificador cambiar
´
a. Finalmente
la tercer direcci
´
on, la virtual V, se obtiene aplicando una
funci
´
on de Hash lineal a la U y ser
´
a la direcci
´
on R, que
estar
´
a contenida dentro del espacio del nodo Rendez Vous
T , qui
´
en est
´
a a cargo de proveer el identificador relativo
asociado a esa direcci
´
on U. El esquema de ruteo indirecto
funciona en la siguiente forma. En la figura 1 el nodo
origen s, requiere comunicarse con el destino f , pero no
sabe su direcci
´
on R, tan s
´
olo la U. Por esta raz
´
on, s
contactara al nodo Rendez Vous T quien conoce la direcci
´
on
R correspondiente al nodo f (notar que este
´
ultimo se
registr
´
o con T al conectarse a la red). A continuaci
´
on T
env
´
ıa un mensaje a s, que contiene la direcci
´
on R de f,
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
71
Recibido: 06/08/18; Aceptado: 19/11/18
, Argentina
Figura 1. Modelo de ruteo indirecto.
Figura 2. Direccionamiento basado en hipercubo.
y entonces de modo el nodo s puede enviar paquetes a f
porque conoce su ubicaci
´
on en la red.
II-B. Direccionamiento y ruteo en ANTop
El protocolo ANTop propone dos metodolog
´
ıas para
enviar un paquete: el ruteo proactivo y el ruteo reactivo.
En el primero de ellos las tablas de ruteo se construyen
y se mantienen actualizadas constantemente, asegurando
una ruta a cada nodo de la red, en todo momento. En el
segundo esquema las rutas se generan bajo demanda y se
mantienen durante un determinado lapso de tiempo. Dada
una redes ad-hoc, donde la posici
´
on de cada nodo puede
variar con frecuencia, dependiendo de cu
´
an r
´
apido var
´
ıan se
elige el primer (poca variaci
´
on) o segundo esquema (r
´
apida
variaci
´
on).
Para poder realizar el ruteo, ANTop define un esquema
de direccionamiento basado en hipercubos. Estos son una
generalizaci
´
on de un cubo de tres dimensiones, a un n
´
umero
d. Cada nodo tiene una coordenada de valor 0 o 1 en cada
dimensi
´
on, entonces el n
´
umero total de nodos 2
d
. Cada nodo
est
´
a conectado a aquellos cuyas coordenadas var
´
ıan s
´
olo
en una dimensi
´
on. En la figura 2 se muestra un hipercubo
de dimensi
´
on 4. ANTop utiliza las coordenadas de cada
nodo en el hipercubo para asignar a cada nodo que se
conecta una direcci
´
on R. Adicionalmente, el nuevo nodo
podr
´
a recibir otras direcciones, denominadas secundarias, de
otros nodos ya conectados a la red, con el fin de mejorar su
interconexi
´
on.
En este esquema, es f
´
acil ver que la distancia entre
dos nodos. Como vemos la distancia en el hipercubo est
´
a
definida por la cantidad de dimensiones con coordenadas
distintas; que se puede obtener aplicando una funci
´
on XOR
entre ambas direcciones. Por ejemplo la distancia entre los
nodos 0100 y 0110 es 1. La distancia se puede pensar como
la cantidad de nodos m
´
ınima por el que un mensaje de un
nodo debe pasar para llegar a un destinatario.
Cuando un nuevo nodo est
´
a en el radio de cobertura
de alguno de los ya conectados a la red, har
´
a un pedido
en modo broadcast para que le sea asignada una direcci
´
on
de hipercubo. Este pedido ser
´
a escuchado por los posibles
vecinos del nuevo nodo los cuales le ofrecer
´
an una direcci
´
on
que difiere en s
´
olo una coordenada (un bit) respecto de la
propia. Cada nodo de la red contar
´
a con, adem
´
as de una
direcci
´
on R, una m
´
ascara que permitir
´
a definir un espacio
de direcciones que ese nodo administra. Tomando como
ejemplo un hipercubo de dimensi
´
on d = 4, el nodo A con
direcci
´
on y m
´
ascara 1000/3, estar
´
a cargado de administrar
las direcciones 1000 y 1001. Cuando un nuevo nodo desee
conectarse a la red, A podr
´
a cederle la direcci
´
on 1001/4.
En caso de que esto suceda, es decir que efectivamente
el nuevo nodo acepte esta propuesta como su direcci
´
on
R, A aumentar
´
a su m
´
ascara a un valor de 4. Es en esta
forma que A delega parte de su espacio de direcciones con
su correspondiente administraci
´
on a un nuevo nodo que se
conecte a la red.
II-C. Ruteo reactivo
El direccionamiento basado en un hipercubo, presenta
un aporte que simplifica el proceso de ruteo. Esto puede
verse claramente si se considera el caso de un hipercubo
completo, es decir aquel en el que todas las direcciones
est
´
an siendo usadas por nodos. Para ilustrar esto
´
ultimo se
puede considerar (ver 2) el caso en que el nodo 0001 quiere
enviar un mensaje al nodo 1101 en un hipercubo de d = 4.
Es posible ver la distancia entre ambos, que resulta ser de
2, por ser la diferencia en bits entre ambas direcciones. Al
existir todos los nodos en la red, es posible saber a priori
que el camino 0001 → 1001 → 1101 ser
´
a v
´
alido para rutear
el paquete, y la cantidad de saltos que el mismo transitar
´
a
es igual a la distancia entre los nodos. Como puede verse,
el nodo origen sin disponer a
´
un de ninguna ruta, ya sabe
un posible camino al destino con distancia m
´
ınima. En un
hipercubo incompleto, en cambio, algunas direcciones no
estar
´
an siendo efectivamente utilizadas por nodos, con lo
cual no es posible asegurar un camino a priori. Sin embargo,
es posible que algunos caminos con distancia m
´
ınima si
existan y por lo tanto vale la pena intentar rutear el paquete
en esa direcci
´
on. Esto mismo es lo que hace ANTop, ya que
bajo su esquema de ruteo reactivo, los paquetes se env
´
ıan en
primera instancia a aquel vecino cuya distancia al destino sea
menor, al tiempo que este
´
ultimo repetir
´
a el procedimiento
para lograr rutear el paquete. Si durante esta exploraci
´
on,
se llega a un callej
´
on sin salida, el paquete ser
´
a devuelto
por donde vino para que el nodo que originalmente envi
´
o
el paquete en esa direcci
´
on pueda enviarlo a su pr
´
oximo
vecino, eligi
´
endolo por el mismo criterio de distancia al
destino.
II-D. Ruteo proactivo
El ruteo proactivo consiste de instalar en cada nodo
rutas estables que b
´
asicamente se resuelve haciendo uso
de la informaci
´
on ya existente en los nodos debido al
mecanismo de asignaci
´
on de direcciones tanto primarias
como secundarias (II-F), y en base a determinados criterios
que son detallados en el trabajo [11], permiten que diferentes
nodos compartan informaci
´
on de ruteo y la distribuyan en
un
´
area de alcance acotado. Finalmente una vez que un nodo
recibe informaci
´
on de ruteo de un vecino depender
´
a de los
criterios de redistribuci
´
on si la misma es propagada hacia
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
72
http://elektron.fi.uba.ar