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
Figura 3. Ruteo proactivo.
otros vecinos cada vez m
´
as lejanos al nodo que inicialmente
distribuye la informaci
´
on, luego ser
´
a responsabilidad de cada
nodo decidir si la informaci
´
on recibida le es de utilidad o no.
En la figura 3 se muestra un ejemplo de una red junto con las
respectivas tablas de ruteo en cada nodo, en la misma puede
verse la estructura del
´
arbol binario y las rutas por defecto
que se instalan hacia los predecesores de primer orden y
sucesores de primer orden.
II-E. Conexi
´
on de nodos en ANTop
En el protocolo ANTop no hay ning
´
un servidor central
ni jerarqu
´
ıas, por lo tanto todos los nodos tienen la misma
funcionalidad. Lo primero que necesita un nodo para conec-
tarse es obtener una direcci
´
on primaria, ya que de otra forma
no podr
´
ıa ser distinguido de otros nodos. Una vez obtenida,
puede comenzar a enviar y recibir paquetes de otros nodos,
as
´
ı como a ceder su espacio de direcciones o adquirir
direcciones secundarias para mejorar la conectividad.
II-E0a. Establecimiento de conexi
´
on: Cuando un no-
do desea conectarse a la red primero tiene que obtener una
direcci
´
on primaria. Para ello, debe notificar a sus vecinos pa-
ra que
´
estos le ofrezcan direcciones primarias. Esto lo hace
enviando un paquete de tipo PAR (Primary Address Request)
en modo broadcast, para que todos sus vecinos lo reciban y
respondan a su vez con un paquete PAP (Primary Address
Proposal), sugiriendo direcciones primarias. El primer nodo
que se conecta a la red (es decir que no existe ning
´
un otro
nodo en su
´
area de cobertura), no recibir
´
a respuesta a cambio
del env
´
ıo del paquete PAR. Por esta raz
´
on el mismo asignar
´
a
la primera direcci
´
on del hipercubo cuyos bits tiene un valor
cero en su totalidad. El segundo nodo que quiera conectarse
a la red, enviar
´
a un paquete PAR, en modo broadcast, y
cuando el primer nodo participante de la red, recibe dicho
pedido, debe responder con un paquete PAP, cuyo destino
ser
´
a la direcci
´
on del segundo nodo, es decir que no ser
´
a
enviado en modo broadcast. Luego de enviar el PAR, el nodo
2 espera un determinado tiempo para colectar las ofertas
de direcci
´
on R y vencido dicho intervalo, elige la opci
´
on
con mayor m
´
ascara. Es decir, el espacio de direcciones m
´
as
grande. En este caso, solo recibir
´
a una respuesta del nodo 1.
Una vez que el segundo nodo acepta la direcci
´
on, lo anuncia
enviando un paquete PAN (Primary Address Notification)
al nodo 1, notificando que acepta su propuesta y que
´
este
incremente su m
´
ascara a un valor de uno. Notar que el
mensaje PAN se env
´
ıa en modo broadcast para que todos
los nodos que propusieron una direcci
´
on sepan que una fue
elegida. El nodo que ofreci
´
o la direcci
´
on elegida ceder
´
ıa
ese espacio de direcciones, y se enviar
´
a un paquete de tipo
PANC (Primary Address Notification Confirmation). Si el
paquete PAN que env
´
ıa el nodo que quiere conectarse a la
red, se perdiese, entonces el nodo que ofreci
´
o la direcci
´
on
elegida no enviar
´
a el PANC, y por lo tanto el proceso de
conexi
´
on del nuevo nodo queda incompleto. Frente a este
escenario, el nodo entrante vuelve a iniciar el ciclo de env
´
ıo
de paquetes PAR.
II-E0b. Direcci
´
on estable: Una vez que el proceso
de conexi
´
on de un nodo a finalizado, el mismo tiene una
direcci
´
on R en el hipercubo y ser
´
a vecino de todos aquellos
nodos que cumplan con dos condiciones:
Estar adentro del alcance de la placa inal
´
ambrica
Diferencia de un bit en las direcciones R.
Al momento de rutear un paquete, cada nodo debe tener
conocimiento de cuales de sus vecinos est
´
an activos en la
red, de lo contrario, se perder
´
an paquetes por ser reenviados
a nodos que ya no forman parte de la red. Para lograr
esto, cada nodo env
´
ıa peri
´
odicamente un paquete de control
del tipo HB (Heart Beat) en modo broadcast. Cuando un
nodo recibe un HB, chequean en su tabla de vecinos si ya
tiene registrado el origen como un vecino. En caso negativo,
agrega una entrada al final de la tabla (generada por una
lista de registros), en caso positivo se marca mediante una
bandera que un nuevo HB ha sido recibido para ese nodo.
Peri
´
odicamente, se recorre la tabla de vecinos y se chequean
cuales vecinos no han enviado HB. En esos casos, se da un
valor de uno a una variable que representa la cantidad de
veces que no se ha recibido este aviso de actividad. Se repite
este mecanismo, y se incrementa la variable si corresponde.
Cuando llega un HB de ese vecino, la variable toma un valor
nulo nuevamente. Cuando la misma llega un determinado
valor m
´
aximo, configurable, se considera que el nodo ya no
est
´
a en la red.
II-F. Establecimiento de direcci
´
on secundaria
Dado que este tipo de direcciones tienen el objetivo de
mejorar la conexidad de los nodos, solamente se realizan una
vez finalizado el proceso de direcci
´
on primaria. Adem
´
as,
dicha direcci
´
on est
´
a supeditada a la primaria. Dado que
los nodos conectados se env
´
ıan peri
´
odicamente paquetes
HB, cada nodo al recibirlo puede comprobar si hay alguna
direcci
´
on secundaria para asignarse y obtener conectividad
con el vecino que env
´
ıo el paquete. Si es posible asignar
una direcci
´
on, entonces se env
´
ıa un paquete SAP (Secondary
Address Proposal), y se espera un paquete SAN (Secondary
Address Notification) en respuesta. El paquete SAP contiene
la direcci
´
on secundaria con el cual el nodo que lo reciba,
tendr
´
a conectividad con el emisor del paquete. En el caso
que el vecino responda con el paquete SAN, el emisor del
paquete SAP se auto asigna la direcci
´
on secundaria creando
un enlace secundario. Luego de haber enviado un paquete
SAP como propuesta de direcci
´
on secundaria, se espera un
temporizador en el cual no se enviar
´
a paquetes SAP como
propuesta a otros nodos, si no que se espera la confirmaci
´
on
SAN del vecino con el que se est
´
a negociando un enlace
secundario. El nodo que recibe el paquete SAP, aparte de
reenviar el mensaje de confirmaci
´
on SAN, agrega como
vecino la direcci
´
on secundaria propuesta y lo marca con
conectividad por enlace secundario.
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
73
http://elektron.fi.uba.ar
II-G. Desconexi
´
on de nodos
Cuando un nodo se desconecta, sus vecinos dejar
´
an de
recibir sus HB. Al cabo de un determinado tiempo, ellos
consideran que el mismo abandon
´
o la red, y lo eliminara
de su tabla de vecinos. Quien sea el padre
1
del nodo,
recuperar
´
a el espacio de direcciones cedido cuando el mismo
se conect
´
o, de modo tal que puede ser utilizado nuevamente.
Cuando un nuevo nodo intenta conectarse dicho espacio es
el primero en ofrecerse. Una vez que todos los recuperados
fueron cedidos, se continua con la sesi
´
on del resto de las
direcciones.
III. NUMERACI
´
ON DE REDES EN ANTOP
Dado que en este trabajo analizamos los casos de frag-
mentaci
´
on y mezcla de redes, es necesario que cada red
tenga un n
´
umero de identificaci
´
on que nos permita dis-
tinguirlas (que fue identificado en [2]); este aspecto no
estaba contemplado en la definici
´
on original [1]. Uno de
los principales inconvenientes en la mezcla surge en base
a las posibles replicas de direcciones de hipercubo de
nodos que anteriormente pertenec
´
ıan a diferentes redes antes
de mezclarse. Por ejemplo, la red 1 compuesta por los
nodos A y B, con direcci
´
on y m
´
ascara 0000/1 y 1000/1
respectivamente; y una red 2 compuesta s
´
olo por el nodo C
con direcci
´
on 0000/0. Si se supone que el nodo C entra en
el alcance del B, entonces este
´
ultimo va tener dos nodos
vecinos (A y C) con la misma direcci
´
on, destruyendo as
´
ı el
concepto de direccionamiento por adyacencia, en el que se
basa ANTop. As
´
ı mismo las mezcla de dos redes distintas
podr
´
ıan tener varias direcciones repetidas.
Por lo tanto proponemos extender en direccionamiento
de ANTop de forma que las redes que son creadas indepen-
dientemente est
´
en identificadas por un campo del protocolo
n
´
umero de red. Dicho campo depende directamente de
par
´
ametros propio del nodo que tiene la primera direcci
´
on
del hipercubo. En el momento que un nuevo nodo se conecte
a alguna red, este hereda el n
´
umero de red correspondiente
a la red. En la fragmentaci
´
on y mezcla de las redes ANTop,
el n
´
umero de red y la direcci
´
on relativa de los nodos
ir
´
an variando dependiendo de la red o las redes formadas
resultantes.
III-A. Algoritmo de asignaci
´
on de n
´
umero de red
En primer lugar se discute el valor que tiene que tener el
n
´
umero de red de una red ANTop.
La principal caracter
´
ıstica que debe tener el n
´
umero
de red es ser
´
unico e irrepetible. Como se ha explicado
anteriormente, un nodo aislado crea una nueva red con la
direcci
´
on con todos ceros, pero ahora deber
´
a generar un
n
´
umero de red que est
´
e relacionado a caracter
´
ısticas
´
unicas
de cada primer nodo; por ejemplo la direcci
´
on MAC del
adaptador Wi-Fi 802.11. Proponemos como identificaci
´
on
para de red ANTop uno de los tres bytes del campo NIC
de la direcci
´
on MAC (del cuarto a; sexto byte de la MAC).
Todos los dem
´
as nodos que se conecten mantendr
´
an dicha
identificaci
´
on de red. En nuestra implementaci
´
on usamos el
primer byte de la NIC (el cuarto de la MAC). El algoritmo
1 de asignaci
´
on de n
´
umero de red est
´
a acompa
˜
nado del
1
nodo padre es aquel que cedi
´
o la direcci
´
on primaria al conectarse a la
red.
Figura 4. Red ANTop antes de la fragmentaci
´
on.
algoritmo de asignaci
´
on de direcci
´
on primaria. En decir, que
acompa
˜
na los tiempos y procesos de asignaci
´
on de la misma
manera como se genera la direcci
´
on primaria.
Algorithm 1 Asignaci
´
on de n
´
umero de red
1: if se recibi
´
o al menos un paquete PAP con direcci
´
on disponible
then
2: Esperar a que llegue un paquete PANC o que transcurra
un tiempo T PANC;
3: if se recibi
´
o un paquete PANC then
4: Se asigna al n
´
umero de red el valor del campo de
n
´
umero de red del mensaje PAP con menor m
´
ascara;
5: end if
6: else
7: if se recibi
´
o un paquete PAR indicando que no hay direc-
ciones disponibles then
8: No se puede conectar y no se asigna ning
´
un valor de
n
´
umero de red;
9: Fin del algoritmo;
10: end if
11: Al n
´
umero de red se asigna el valor del cuarto byte de la
direcci
´
on MAC del dispositivo;
12: end if
IV. FRAGMENTACI
´
ON DE REDES ANTOP
En la figura 4 se muestra una red ANTop cuya estructura
se presentan las tablas de vecinos de cada uno de los nodos.
Notar que los nodos tienen registrados las direcciones R de
sus vecinos porque reciben los paquetes HB. Por ejemplo el
nodo C recibe paquetes HB de los nodos A, D y E; y por
lo tanto C tiene registrado las direcciones R de cada uno de
ellos en su tabla de vecinos. Ahora, si el nodo A se desplaza
f
´
ısicamente hacia la izquierda a tal punto de salir del alcance
del nodo C, el nodo C en principio va mantener en su tabla
de registros de vecino a la direcci
´
on R del nodo A, como
tambi
´
en el nodo A mantendr
´
a a C en su tabla de vecinos
Luego de tres ciclos de env
´
ıos de HB, cuyo temporizador del
ciclo es configurable en la implementaci
´
on del protocolo,
tanto el nodo A como el nodo C, se van a eliminar de
sus tablas de vecinos respectivamente (ver figura 5). Se ve
claro que la fragmentaci
´
on ocurri
´
o, y esquem
´
aticamente se
observa dos redes separadas como resultado. De las dos
redes resultantes, una tiene que tomar el rol de disparar
el mecanismo de fragmentaci
´
on, y la otra directamente no
tomar
´
a acci
´
on alguna.
Suponiendo que en la figura 5, el nodo A es el padre del
nodo C, entonces la red fragmentada ser
´
a aquella en el cual
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
74
http://elektron.fi.uba.ar
Figura 5. Red ANTop fragmentada.
Figura 6. Fragmentaci
´
on de red ANTop con enlace secundario.
est
´
a compuesta por los nodos C, D y E. En principio se ve
que es necesario que un nodo pierda a su padre, pero no es
condici
´
on suficiente.
Dado la existencia de las direcciones secundarias, el
escenario de la figura 6 muestra un caso en el que no
hay fragmentaci
´
on. Por lo tanto, para verificar que no
existan otras conexiones, hay que disparar un mecanismo
de exploraci
´
on para asegurar que no existan otros enlaces
(direcciones secundarias).
El algoritmo 2 detector de fragmentaci
´
on, es un proceso
que corre cada vez que el nodo reciba un paquete HB.
IV-A. Proceso de asignaci
´
on de direcciones
En principio una red fragmentada con las direcciones R
y m
´
ascara que fueron definida antes de la fragmentaci
´
on,
se podr
´
ıan conservar y cumplir con las caracter
´
ısticas de
una red ANTop. Sin embargo la red fragmentada conserva
el mismo n
´
umero de red que la red original, y como
se ver
´
a m
´
as adelante, este campo ser
´
a importante que se
diferencie entre redes independientes ante una posible futura
mezcla de redes ANTop. Entonces es inevitable disparar
un mecanismo que informe a todos los nodos de la red
fragmentada para cambiar su n
´
umero de red. El nodo que
detecta la fragmentaci
´
on, se asigna la primer direcci
´
on del
hipercubo y elige su direcci
´
on de red (distinta a la actual),
y dispara el mecanismo de renombramiento de los nodos en
la red fragmentada.
En la figura 7 se muestra una red ANTop, conformada
por los nodos A, B, C, D y E. En el momento que el
Algorithm 2 Detector de Fragmentaci
´
on
Require: paquete HB
Ensure: None
1: if se recibi
´
o un paquete HB then
2: Se procesa el paquete HB;
3: Se actualiza la tabla de vecinos;
4: goto linea 7;
5: else return;
6: end if
7: if si hay un vecino que tiene menor distancia a la raiz que el
padre actual then
8: Agrego al vecino como padre;
9: end if
10: if Si el padre no es un vecino then
11: if Si no se encuentran enlaces secundario entre las partes
then
12: Iniciar proceso de fragmentaci
´
on;
13: return;
14: end if
15: else return;
16: end if
Figura 7. Direccionamiento de red ANTop fragmentada.
nodo C pierde conexi
´
on con el nodo A, los nodos C,
D y E forman la red fragmentada. El nodo C es el que
detectar
´
a la fragmentaci
´
on y ser
´
a el encargado de disparar el
mecanismo de fragmentaci
´
on: se asigna la primer direcci
´
on
del espacio del hipercubo (la direcci
´
on R 0000). El nodo
C env
´
ıa un mensaje a los nodos D y E para que se ajusten
sus par
´
ametros del protocolo y que se conserve la relaci
´
on
de vecinos entre s
´
ı. Lo que se hace es que los nodos
subordinados desplacen los bits a izquierda de su direcci
´
on,
agregando ceros desde la derecha. Esta
´
ultima operaci
´
on se
la conoce como la operaci
´
on de shift de ceros a izquierda.
La cantidad de operaciones de desplazamiento depender
´
a de
un valor en particular que se llama m
´
ascara inicial (mi)
2
del nodo que dispara el mecanismo de fragmentaci
´
on (nodo
detector).
IV-B. Paquetes de control
En el proceso de fragmentaci
´
on, a partir del nodo detector
y sus nodos subordinados recibir
´
an mensaje de control que
transmite la informaci
´
on necesaria para que puedan cambiar
su direcci
´
on R y m
´
ascara. Los paquetes de control que se
utiliza en el proceso de fragmentaci
´
on ser
´
an FAR (Fragment
Address Request) y FAN (Fragment Address Notification).
2
mi: valor de la m
´
ascara obtenida al conectarse a la red.
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
75
http://elektron.fi.uba.ar
Figura 8. Env
´
ıo de paquetes FAR desde el nodo detector.
El mensaje FAR b
´
asicamente transmite el valor de la m
´
asca-
ra inicial del nodo detector, mientras que el FAN es un
mensaje de confirmaci
´
on del haber recibido correctamente
dicho FAR. En el trabajo [13] se pueden consultar en detalle
los campos y la informaci
´
on que portan.
IV-C. Algoritmos de envi
´
o de mensaje de control
Los algoritmos desarrollados son tres. El primero es
ejecutado en el nodo detector en el momento que detecta
la fragmentaci
´
on, el segundo algoritmo se ejecuta cuando
se recibe un paquete FAR, y el tercero cuando se recibe un
mensaje FAN.
IV-C0a. Fragmentaci
´
on: Los mensajes FAR y FAN,
se deben enviar a todos los nodos de la red fragmentada,
empezando desde el nodo detector hasta el final del
´
arbol.
El algoritmo 3 se ejecuta en el nodo detector al momento
que detecta que la fragmentaci
´
on ocurri
´
o, donde el mismo
debe avisar a todos sus nodos vecinos (hijos), barriendo su
tabla de vecinos y enviando a cada uno de ellos un mensaje
FAR como se muestra en la figura 8.
Algorithm 3 Fragmentaci
´
on
Require: None
Ensure: None
1: Suspender el env
´
ıo y procesamiento de paquetes HB;
2: Suspender el servicio Rendez Vous;
3: Asignar n
´
umero de red (4to byte MAC del nodo detector);
4: Shift de ceros a izquierda mi veces a la direcci
´
on primaria;
5: m = m − mi ;
6: Ajustar la tabla de direcciones recuperadas;
7: Borrar tabla de rutas;
8: Enviar FAR a los hijos que tienen enlace principal;
9: Borrar tabla de nombres Rendez Vous;
10: Borrar tabla de vecinos;
11: Setear la m
´
ascara inicial en cero;
12: return;
IV-C0b. Procesamiento FAR: En el momento que un
nodo reciba un paquete FAR, debe seguir con el env
´
ıo hasta
el final del
´
arbol. Por ende, en el procesamiento del FAR,
debe de enviar en principio el paquete FAR a todos los
vecinos subordinados si es que tiene, y tambi
´
en el paquete
de confirmaci
´
on FAN al nodo del quien recibi
´
o el FAR,
como se muestra en la figura 9. El algoritmo 4, muestra el
procesamiento del FAR como tambi
´
en resuelve la direcci
´
on
R y m
´
ascara que se debe asignar cada nodo.
IV-C0c. Procesamiento FAN: El nodo que env
´
ıa un
mensaje FAR, debe de suspender el servicio de env
´
ıo HB
Figura 9. Env
´
ıo de paquetes FAR y FAN de nodos intermedios.
Algorithm 4 Procesamiento FAR
Require: Paquete FAR
Ensure: None
1: Suspender el env
´
ıo y procesamiento de paquetes HB;
2: Suspender el servicio Rendez Vous;
3: if la direcci
´
on destino del FAR es la direcci
´
on secundaria then
4: Enviar confirmaci
´
on FAN al nodo que env
´
ıo FAR;
5: Shift de ceros a izquierda m
F AR
veces a la dir. secundaria;
6: m
secundaria
= m
secundaria
− m
F AR
;
7: if el tratamiento de direcci
´
on primaria ocurri
´
o then
8: Reanudar servicio de HB y Rendez Vous;
9: end if
10: return;
11: end if
12: Agregar como vecino y padre al nodo que envi
´
o FAR;
13: Enviar confirmaci
´
on FAN al nodo que env
´
ıo FAR;
14: Asignar el n
´
umero de red del campo del paquete FAR;
15: Shift de ceros a izquierda m
F AR
veces a la dir. primaria;
16: Ajustar la tabla de direcciones recuperadas;
17: Borrar tabla de rutas;
18: Borrar tabla de nombres Rendez Vous;
19: Enviar FAR a los hijos que tienen enlace principal;
20: Borrar tabla de vecinos excepto el nodo padre;
21: m = m − m
F AR
;
22: mi = mi − m
F AR
;
23: if no se env
´
ıo paquete FAR then
24: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on secundaria ocurri
´
o then
25: Reanudar servicio de HB y Rendez Vous;
26: end if
27: end if
28: return;
y los paquetes de registro y resoluci
´
on a los servidores
Rendez Vous. La
´
unica manera de que se restablezca, es por
medio de la recepci
´
on de un mensaje FAN de alg
´
un nodo
subordinado. En el caso que un nodo contenga una direcci
´
on
secundaria, deber
´
a esperar a que termine el proceso de asig-
naci
´
on de la nueva direcci
´
on R y m
´
ascara, tanto la primaria
como la secundaria, para restablecer dichos servicios. Esto
´
ultimo se muestra en el algoritmo 5 de procesamiento de
FAN.
V. MEZCLA DE REDES ANTOP
En la siguiente figura 10, se encuentran dos redes ANTop
independientes y numeradas. En cada nodo tiene identificada
la direcci
´
on primaria, la m
´
ascara y el n
´
umero de red que
es igual a todos los nodos que pertenecen a la misma red.
Por ejemplo, el nodo B tiene la direcci
´
on primaria 1000, la
m
´
ascara 1 y el n
´
umero de red 3d. Suponiendo que uno de
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
76
http://elektron.fi.uba.ar
Algorithm 5 Procesamiento FAN
Require: Paquete FAN
Ensure: None
1: if si a
´
un no se restableci
´
o el servicio de HB y Rendez Vous
then
2: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on primaria y secundaria ocurri
´
o then
3: Reanudar servicio de HB y Rendez Vous;
4: end if
5: end if
6: return;
Figura 10. Dos redes ANTop independientes y numeradas.
los nodos se desplaza f
´
ısicamente hasta lograr la mezcla de
ambas redes. Si el nodo Y se desplaza sin perder vinculo
de comunicaci
´
on con el nodo Z y a su vez entra dentro del
alcance del nodo C perteneciente a otra red ANTop, va a
intercambiar mensajes de control ANTop pero ahora con un
extra de informaci
´
on aportada por el campo n
´
umero de red
que nos permitir
´
a saber a que red pertenece y armar una
l
´
ogica de decisi
´
on seg
´
un el caso que se presente.
En el momento que el nodo Y reciba el mensaje HB del
C como se muestra en la figura 11 (y por lo tanto C cuando
reciba el HB de Y ), detecta que los n
´
umeros de red difieren,
por lo que dispara el mecanismo de mezcla.
´
Este consistir
´
a
en el renombramiento de direcciones de una red ANTop a
otra, y habr
´
a que elegir cu
´
al de los dos se elige.
La red que ser
´
a renombrada en una mezcla es aquella
que tiene el mayor n
´
umero de red entre ambas (ver su
justificaci
´
on en el trabajo [13]). El algoritmo 6 muestra como
decide una red en el momento de la mezcla con otra, y se
inicia con la recepci
´
on del HB. El proceso de mezcla lo
inicia la red que no ser
´
a renombrada, ya que
´
esta tendr
´
a
que pasarle ciertos par
´
ametros a la otra red (la que ser
´
a
renombrada). A su vez, dicho algoritmo sirve como filtro
para procesar solo los paquetes HB que tienen un n
´
umero
de red igual a la red a la que pertenece.
V-A. Proceso de asignaci
´
on de direcciones
Este proceso procura que se mantenga la estructura de
direcciones R basados en hipercubo, cuyo concepto es la
esencia del protocolo ANTop y porque es m
´
as econ
´
omico.
En el esquema mostrado anteriormente de la figura 11, en el
momento que se mezcla las dos redes ANTop por medio del
par de nodos C-Y , el nodo C activa el mecanismo de mezcla
renombrando a la Red 2 seg
´
un la jerarqu
´
ıa de asignaci
´
on de
direcci
´
on del mismo a partir de su direcci
´
on R 0100/2. El
resultado de la mezcla se muestra en la figura 12, en donde
Figura 11. Mezcla de dos redes ANTop numeradas.
Algorithm 6 Detector de Mezcla
Require: N
´
umero de red del paquete HB
Ensure: None
1: if n
´
umero de red local < n
´
umero de red del paquete HB then
2: Iniciar proceso de mezcla;
3: No procesar paquete HB;
4: return;
5: end if
6: if n
´
umero de red local = n
´
umero de red del paquete HB then
7: Procesar paquete HB;
8: return;
9: end if
10: if n
´
umero de red local > n
´
umero de red del paquete HB then
11: No procesar paquete HB;
12: return;
13: end if
se agrego un bit m
´
as en las direcciones para mostrar en
detalle las direcciones asignadas.
En la mezcla se muestran los cambios en color rojo, tanto
de direcciones R como tambi
´
en de m
´
ascara y n
´
umero de
red para los nodos que integraban la Red 2 y el nodo C
en particular de la Red 1. Las m
´
ascaras cambian ya que
deben respetar el espacio de direcciones asignados seg
´
un el
nodo que le antecede y le sucede. Por ejemplo, el nodo C
al ceder el espacio de direcciones 01100 con m
´
ascara 2 a
Y , debe aumentar en 1 su m
´
ascara dando como resultado
m
´
ascara 3. Luego Y resulta de m
´
ascara 4 porque le cede el
espacio de direcciones 01110 y m
´
ascara 4 al nodo Z, y se
contin
´
ua por todos los nodos de la Red 2. El resultado es
similar al proceso de asignaci
´
on de direcci
´
on dado primero
por la conexi
´
on del nodo Y enviando un paquete PAR en
modo broadcast y el nodo C asign
´
andole una direcci
´
on
con un mensaje PAP. Luego el proceso es completado con
los mensajes PAN y PANC. Se repite el mismo proceso
cuando el segundo nodo en conectarse sea el Z que le llega
una propuesta de direcci
´
on R a partir de la recepci
´
on del
mensaje PAP del nodo Y , y con el resto de los nodos. Sin
embargo lo
´
ultimo descripto, ser
´
ıa como la interpretaci
´
on
del resultado similar a la del mecanismo de mezcla que
se propone en esta secci
´
on. Es decir, que en la mezcla no
habr
´
a paquetes de control PAR, PAP, PAN o PANC para el
renombramiento de una de las dos redes, sino que se dise
˜
nan
nuevos paquetes de control que se definen m
´
as adelante. En
el proceso de asignaci
´
on de direcciones se dividen en dos
vetas, es decir, que el mecanismo de mezcla en realidad
estar
´
a compuesto por dos mecanismos distintos en el que a
uno lo llamaremos mecanismo 1 y al otro mecanismo 2.
V-A0a. Mecanismo 1: Para explicar el mecanismo
1, se plantea los siguientes casos para renombrar una red
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
77
http://elektron.fi.uba.ar
Figura 12. Resultado propuesto de la mezcla de dos redes ANTop.
Figura 13. Primer caso de tratamiento de direcci
´
on del mecanismo 1 de
mezcla.
ANTop en la mezcla.
Primer Caso. La idea es encontrar una soluci
´
on para
renombrar ciertos nodos de una red en el proceso de mezcla,
sin que la topolog
´
ıa y el orden de la estructura de direcciones
R formadas entre s
´
ı cambie lo menos posible. El primer caso
se muestra en la figura 13.
En dicha figura, se observa que la mezcla comienza
por medio del par de nodos A y B. Dado que la Red 2
tiene un identificador de mayor que la otra, el proceso de
renombrabiento se realiza en esta red.
En la topolog
´
ıa del ejemplo planteado, como resultado
de la nueva direcci
´
on del nodo B, est
´
a escrita en color
rojo y azul arriba de la direcci
´
on 10000/3 antes de la
mezcla. Se puede observar que est
´
a compuesta por dos cifras
diferenciadas por los colores. El prefijo en rojo 01 coincide
con el prefijo de la direcci
´
on 01000 con m
´
ascara 2 del
nodo A. Luego el resto de la cifra en azul, coincide con
la direcci
´
on del nodo mismo antes de la mezcla. Haciendo
el mismo an
´
alisis para los nodos subordinado del nodo B,
Figura 14. Segundo caso de tratamiento de direcci
´
on del mecanismo 1 de
mezcla.
vemos que podemos aplicar el mismo criterio. S
´
olo el nodo
E no cumplir
´
ıa con la estrategia mencionada, ya que el
resultado de la direcci
´
on R luego de la mezcla ser
´
ıa 01000
que coincide con al direcci
´
on R del nodo A. Entonces el
criterio mencionado funciona para los nodos subordinado del
nodo que forma parte del par que se establece la mezcla. Esta
soluci
´
on nos permite que las direcciones por los menos de
los nodos subordinados permanezcan con la misma relaci
´
on
de distancias y jerarqu
´
ıa entre s
´
ı. Para el caso del nodo E,
hay otro tratamiento de renombramiento de direcciones que
se ver
´
a en el mecanismo 2. Las m
´
ascaras resultantes en los
nodo B, C y D, se pueden obtener sumando su m
´
ascara
de cada uno antes de la mezcla, con la m
´
ascara del nodo
A antes de la mezcla (por ejemplo, inicialmente el nodo C
tiene m
´
ascara 2). Luego de la mezcla, suma la m
´
ascara 2
del nodo A antes de la mezcla, obteniendo como resultado
la m
´
ascara 4. Si se observa la m
´
ascara del nodo A despu
´
es
de la mezcla, resulta de ser 3 ya que en la mezcla toda la
red quedar
´
a en el espacio de direcci
´
on dependiente del nodo
C, por ende
´
este debe de ceder el espacio aumentando en
uno su m
´
ascara.
Segundo caso. En el primer caso, el nodo E tiene la primera
direcci
´
on del espacio de direcci
´
on por hipercubo, es decir,
todos los bits significativos en cero. En el segundo caso el
nodo E tiene un valor 10000/3 como se muestra en la figura
14.
Si aplicamos el mismo criterio del primer caso al nodo B,
luego de la mezcla como resultado se obtiene la direcci
´
on
R = 01110. Calculando la distancia entre el nodo A y
la direcci
´
on resultante del nodo B, obtenemos la distancia
2. La idea en la mezcla es que en el par de nodos que
entran en juego y desencadenan la mezcla, est
´
en a distancia
1, en donde no ocurre con el criterio del caso anterior.
El mecanismo 1 en el esquema de la figura 14, solo ser
´
a
aplicado a los nodos B, C y D. Para que el nodo B sea un
subordinado en direcci
´
on R del nodo A, tiene que cumplir
con dos caracter
´
ısticas: que la resultante de la direcci
´
on R
tenga el prefijo de la direcci
´
on del nodo A hasta el valor
de la m
´
ascara de este
´
ultimo, y que est
´
e a distancia uno de
dicho nodo A. Una de la maneras es que cada nodo realice
un desplazamiento de ceros a la izquierda la cantidad de
veces seg
´
un el valor de la m
´
ascara inicial (mi) del nodo
B. La cantidad exacta de dicha operaci
´
on es del valor de
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
78
http://elektron.fi.uba.ar
Figura 15. Tercer caso de tratamiento de direcci
´
on del mecanismo 1 de
mezcla.
mi(B) − 1 del nodo B (ver el trabajo [13]. ). Por ejemplo,
el nodo C, luego de la cantidad de (2 − 1) operaciones
de desplazamiento de ceros, se obtiene 11000; y aplicando
el criterio del primer caso visto, obtenemos la direcci
´
on R
resultante 01110. Si se realiza el mismo procedimiento para
el nodo B y D, se obtienen los mismos resultado que en el
primer caso.
Luego se realiza el proceso visto en el caso anterior, en
donde se vuelve a realizar el desplazamiento de ceros pero
esta vez a la derecha y la cantidad del valor de la m
´
ascara
del nodo A antes de la mezcla. Por
´
ultimo se realiza una
operaci
´
on OR con la direcci
´
on del nodo A. La m
´
ascara luego
de la mezcla se pod
´
ıa obtener con la suma de la m
´
ascara
antes de la mezcla, m
´
as la m
´
ascara del nodo A tambi
´
en antes
de la mezcla. Pero ahora hay que considerar el concepto
de la operaci
´
on extra que trat
´
o en este caso. Cuando se
menciono que para obtener la direcci
´
on R resultante, en
primer medida es necesario realizar el desplazamiento de
ceros a izquierda la cantidad de mi(B )−1 veces. En realidad
lo que se est
´
a realizando es que se aumenta el espacio
de direcciones la cantidad de mi(B) − 1, es decir, que la
m
´
ascara resultante ahora hay que restarle mi(B) − 1 a la
suma de la m
´
ascara local y m
´
ascara del nodo A antes de la
mezcla. La m
´
ascara despu
´
es de la mezcla se puede obtener
aplicando la siguiente ecuaci
´
on 1.
m
mezcla
= m(A) + m −
mi(B) − 1
(1)
La m
´
ascara inicial tambi
´
en de debe fijar nuevamente ya
que si en un futuro vuelve a ocurrir una mezcla o frag-
mentaci
´
on, puedan ejecutarse correctamente los algoritmos
desarrollados en este articulo. La m
´
ascara inicial resultante
se puede calcular con la siguiente ecuaci
´
on 2.
mi
mezcla(x)
= m(A) + 1 +
mi(x) − mi(B)
(2)
Tercer caso. Falta un caso m
´
as por analizar, y es cuando
el nodo B tiene la direcci
´
on R con todos los bits en cero
como se muestra en la figura 15. Todos los nodos de la Red
2 sin contar el B, ser
´
an subordinados de este
´
ultimo, por
ende el tratamiento de direcciones que veremos ser
´
a valida
para todos los nodos de dicha red.
El criterio del primer caso no se podr
´
a aplicar a este
esquema, ya que el nodo B al realizar el desplazamiento
de ceros a derecha de la cantidad de m
´
ascara 2 del nodo
A, obtendremos la misma direcci
´
on 00000. Y cuando se
agregue el prefijo 01 del nodo A, se tendr
´
a como resultado
la misma direcci
´
on del nodo A. Como primera medida de
debe crear una dimensi
´
on por medio del vector 10000.
Dicho vector tiene la caracter
´
ıstica de poseer el bit m
´
as
significativo en 1, y luego se podr
´
a utilizar en cada nodo,
desplaz
´
andolo a derecha y crear la dimensi
´
on faltante. La
estrategia consistir
´
a primero de tomar el vector 10000 y
realizarle al operaci
´
on de desplazamiento de ceros a derecha
la cantidad de veces la m
´
ascara del nodo A. Luego se vuelve
a realizar la operaci
´
on de desplazamiento de ceros a derecha
a la direcci
´
on R actual de cada nodo, la cantidad de veces
la m
´
ascara del nodo A m
´
as uno. Por
´
ultimo, se realiza la
operaci
´
on OR en entre las dos direcciones que obtuvimos
m
´
as la direcci
´
on R del nodo A. Por ejemplo, el nodo D se
obtiene su direcci
´
on R luego de la mezcla de la siguiente
operaci
´
on.
00100|00001|01000 → 01101
1. 00100 : El vector 10000, se realiza la operaci
´
on de
desplazamiento de ceros hacia derecha la cantidad de
veces la m
´
ascara 2 del nodo A.
2. 00001 : la direcci
´
on R actual del nodo D 01000, se
realiza la operaci
´
on de desplazamiento de ceros la
cantidad de veces la m
´
ascara 2 del nodo A m
´
as 1,
o sea 3.
3. 01000 : Direcci
´
on R del nodo A.
El
´
ultimo ejemplo se puede aplicar para todos los nodos
de la Red 2, y se podr
´
a observar que cumple con lo mostrado
en la figura 15. Los valores de las m
´
ascara y mi de cada
nodo, se podr
´
a aplicar las mismas ecuaciones 1 y 2 del
segundo caso.
V-A0b. Mecanismo 2: En la figura 16 del primer caso
del mecanismo 1, el nodo E es antecesor del nodo B en
donde se produce la mezcla. Como se comento, el meca-
nismo 1 contempla a aquellos nodos que son subordinados
del nodo B, por ende, el nodo E queda fuera del alcance de
dicho mecanismo. Por tal motivo se desarrolla el mecanismo
2, que se enfoca en resolver las direcciones R de todos
aquellos nodos que no son subordinados al par receptor en
una mezcla de dos redes ANTop. En la figura 16, tenemos
el caso de una mezcla entre el nodo A y B. Tanto el nodo B
y C, corren el mecanismo 1 y se asignan las direcciones
y m
´
ascara seg
´
un en el primer caso. Para los nodos que
pertenecen a la rama del nodo E desde el nodo B, tendr
´
an
un tratamiento particular en la direcci
´
on y m
´
ascara. En este
caso el mecanismo 2 tendr
´
a efecto sobre los nodos E y F.
Cuando el nodo B notifica a su vecinos sobre la existencia
de la mezcla, los mensajes que le transmitir
´
a a C ser
´
a
distinto el mensaje que le transmitir
´
a a E. En primer lugar
el nodo C necesita cierta informaci
´
on propia del mecanismo
1, en cambio el nodo E recibir
´
a otro tipo de informaci
´
on
acorde al mecanismo 2. En primer lugar vamos a describir
el tratamiento de las direcciones sobre los nodos E y F ,
que tiene como resultado en la figura 16. El mecanismo 2,
propone b
´
asicamente que los nodos de la rama se vayan
asignando las direcciones del espacio del hipercubo, seg
´
un
el valor de la direcci
´
on R y m
´
ascara del nodo predecesor
de la rama. Por ejemplo, el nodo E recibe el mensaje del
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
79
http://elektron.fi.uba.ar
Figura 16. Tratamiento de direcciones mecanismo 2.
mecanismo 2 del nodo B, en donde le avisa que se asigne el
pr
´
oximo espacio de direcciones seg
´
un la direcci
´
on y m
´
ascara
actual del propio nodo B, es decir, direcci
´
on R 11000 y
m
´
ascara 3. Esto
´
ultimo, se considera que el nodo B ya se
asigno su nueva direcci
´
on por medio del mecanismo 1 antes
que le env
´
ıe el mensaje al nodo E por el mecanismo 2,
en donde el resultado se ven en color rojo en el esquema,
propios de los cambios del producidos por el mecanismo 1,
y los cambios del mecanismo 2 se muestran en color verde.
Entonces el nodo E, se asignar
´
a el pr
´
oximo espacio dando
como resultado la direcci
´
on R 11010 y m
´
ascara 4. Luego
el nodo B incrementa en 1 el valor de su m
´
ascara, dando
como resultado 4. El mismo proceso ocurre entre el nodo E
y F , en donde el nodo E env
´
ıa un mensaje del mecanismo 2
al nodo F con la direcci
´
on 11010 y m
´
ascara 4. Este
´
ultimo
se asigna la siguiente direcci
´
on del espacio de direcciones,
o sea, direcci
´
on R 11011 y m
´
ascara 5. Por
´
ultimo el nodo
E incrementa en uno su m
´
ascara resultando el valor de 5.
El valor de m
´
ascara inicial de cada nodo, se puede obtener
con el valor de la m
´
ascara del nodo del que recibimos el
mensaje por mecanismo 2, sum
´
andole el valor de 1. Por
ejemplo, el nodo E, toma el valor de la m
´
ascara 3 del nodo
B y le suma 1, obteniendo una mi de 4.
V-A0c. Algoritmos de env
´
ıo de mensajes de control:
Los algoritmos desarrollados son cinco. En una mezcla, el
nodo que comienza el proceso lo llamaremos par emisor,
y el otro lo llamaremos par receptor (el de la red que
cambia sus par
´
amtro). Por ejemplo en la figura 12 el par
emisor es el C, y el par receptor es el Y . Para el caso del
mecanismo 1 los paquetes de control que se utiliza en el
proceso de mezcla ser
´
an MAR1 (Mix Address Request 1)
y MAN1 (Mix Address Notification 1). Para el caso del
mecanismo 2 los paquetes de control que se utiliza en el
proceso de mezcla ser
´
an MAR2 (Mix Address Request 2) y
MAN2 (Mix Address Notification 2). El primero es el que
ser
´
a expuesto es el ejecutado en el par emisor. Luego se
analizan los algoritmos que se ejecutan cuando se reciben
los paquetes de control MAR1, MAN1, MAR2 y MAN2.
Mezcla. En un proceso de mezcla, como se describi
´
o ante-
riormente, en principio entran en acci
´
on dos nodos en el que
llamamos par emisor y par receptor. Cuando el par emisor
detecta la mezcla por medio del nodo par receptor, este
comienza el mecanismo de mezcla ejecutando el algoritmo
7 en el cual se encargar
´
a de enviar el mensaje MAR1 al
Figura 17. Env
´
ıo del paquete MAR1 del par emisor al par receptor.
nodo receptor como se muestra en la figura 17.
Si el env
´
ıo del mensaje MAR1 lo hace con su direcci
´
on
R, puede ocurrir que dicha direcci
´
on exista en la red con la
que se mezcla, por ende antes de enviar el paquete MAR1,
debe cambiar la direcci
´
on R a una que llamaremos direcci
´
on
por defecto. Esta
´
ultima direcci
´
on tendr
´
a como caracter
´
ıstica
una direcci
´
on que no est
´
e dentro del espacio de direcciones
del hipercubo. Por otro lado, par emisor debe suspender los
servicio de env
´
ıo HB y los paquetes de registro y resoluci
´
on
a los servidores Rendez Vous.
Algorithm 7 Mezcla
Require: None
Ensure: None
1: Suspender el env
´
ıo y procesamiento de paquetes HB;
2: Suspender el servicio de registraci
´
on y resoluci
´
on de nombres
Rendez Vous;
3: Asignar como direcci
´
on R, la direcci
´
on por defecto;
4: Enviar MAR1 al nodo receptor;
5: return;
Procesamiento MAR1. En la figura 17, muestra al nodo
receptor recibiendo el MAR1 del nodo emisor, donde el
nodo receptor dispara el mecanismo de env
´
ıo de paquetes
MAR1 a los nodos subordinados y MAR2 al nodo padre
como se observa en la figura 18. En este caso los vecinos
V 2 y V n recibir
´
an el mensaje MAR1, y el V 1 recibir
´
a
el mensaje MAR2. Antes se debe suspender el servicio
de env
´
ıo HB y el servicio de resoluci
´
on y de registro
a los servidores Rendez Vous. Luego del env
´
ıo de los
paquetes MAR1 y MAR2, se debe enviar el mensaje de
confirmaci
´
on MAN1 al par emisor. El algoritmo 8, describe
el procesamiento de un paquete MAR1.
Si un nodo contiene direcci
´
on secundaria y no envi
´
o
ning
´
un mensaje MAR1 o MAR2, se deber
´
a esperar que
ambas direcciones, la primaria y la secundaria, se asignen
las direcciones correspondiente en el proceso de mezcla para
restablecer el servicio de HB y de registro y resoluci
´
on de
nombres Rendez Vous. Tambi
´
en se muestra el calculo de
m
´
ascara y mi seg
´
un el caso de que se trate, si es par receptor
o un nodo intermedio como lo son V 2 y V n en la figura 18.
El nodo al correr dicho algoritmo distingue si tiene el perfil
de par receptor o no. La distinci
´
on se debe por un lado a
los diferencia del calculo de m
´
ascara y mi, y por el otro la
necesidad de enviar un paquete MAR2 en el caso del par
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
80
http://elektron.fi.uba.ar
Figura 18. Env
´
ıos de MAR1 y MAR2 del par receptor, y confirmaci
´
on
MAN1 al nodo emisor.
receptor, que en los dem
´
as nodos no es necesario.
Algorithm 8 Procesamiento MAR1
Require: Paquete MAR1
Ensure: None
1: Suspender el env
´
ıo y procesamiento de paquetes HB;
2: Suspender el servicio Rendez Vous;
3: if la direcci
´
on destino del MAR1 es la dir. secundaria then
4: m
sec
= m
sec
+ m
paremisor
− (mi
parreceptor
− 1);
5: Enviar confirmaci
´
on MAN1 al nodo que env
´
ıo MAR1;
6: Tratamiento de mecanismo 1 a la direcci
´
on secundaria;
7: if el tratamiento de direcci
´
on primaria ocurri
´
o then
8: Reanudar servicio de HB y Rendez Vous;
9: end if
10: return;
11: end if
12: Asignar el n
´
umero de red del campo del paquete MAR1;
13: if es el nodo receptor then
14: m = m + m
paremisor
− (mi − 1);
15: mi = m
paremisor
+ 1;
16: else
17: m = m + m
paremisor
− (mi
parreceptor
− 1);
18: mi = m
paremisor
+ 1 + (mi − mi
parreceptor
);
19: end if
20: Borrar tabla de nombres Rendez Vous;
21: if tiene vecinos a distancia 1 de la direcci
´
on primaria then
22: Enviar MAR1 a los hijos que tienen enlace principal;
23: Si es el par receptor y tiene nodo padre, enviarle MAR2;
24: end if
25: Borrar tabla de vecinos;
26: if no se env
´
ıo paquete MAR1 o MAR2 then
27: Enviar confirmaci
´
on MAN1 al nodo que env
´
ıo MAR1;
28: Tratamiento de mecanismo 1 a la direcci
´
on primaria, y a
la tabla de direcciones recuperadas;
29: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on secundaria ocurri
´
o then
30: Reanudar servicio de HB y Rendez Vous;
31: end if
32: else
33: Enviar confirmaci
´
on MAN1 al nodo que env
´
ıo MAR1;
34: end if
35: return;
Procesamiento MAR2. En la figura 18, se muestra a V 1 que
recibe un paquete MAR2 del par receptor. Al procesar dicho
paquete, V 1 debe de seguir propagando el mecanismo 2 a
todo los nodos de su rama, ver figura 19. Para ello primero
se suspende el servicio de HB y de registro y resoluci
´
on
de nombres Rendez Vous. Tambi
´
en se debe distinguir si
el destino del paquete MAR2 recibido corresponde a la
Figura 19. Propagaci
´
on de mensaje MAR1, MAR2 y sus confirmaciones.
direcci
´
on primaria o secundaria si es que tiene. En el caso de
que el destino del mensaje MAR2 es la direcci
´
on primaria,
luego se env
´
ıa paquete MAR2 a todos los vecino que est
´
an
distancia uno de la direcci
´
on primaria excepto al nodo del
quien recibi
´
o el MAR2. Por
´
ultimo, para reanudar los ser-
vicios de HB y de registro y resoluci
´
on de nombres Rendez
Vous, se debe esperar hasta que tanto la direcci
´
on primaria
como la secundaria se hayan tratados por los mecanismo
correspondientes. En el caso de que no se haya enviado
ning
´
un paquete MAR2, ya que el mismo es el
´
ultimo de
la rama el mecanismo 2, debe de asignarse la direcci
´
on R
correspondiente al mecanismo 2.
Procesamiento MAN1. En la figura 18, se muestra al
nodo receptor enviando el mensaje de confirmaci
´
on MAN1
al par emisor. Este al recibirlo y procesarlo, habilita a
reanudar el servicio de HB y de registro y resoluci
´
on de
nombres Rendez Vous y tambi
´
en da la orden de volver a
asignarse la direcci
´
on que tenia inicialmente antes de la
mezcla. El mensaje de confirmaci
´
on, avisa al emisor de
paquetes MAR1, que recibi
´
o dicho paquete y por ende puede
restablecer sus servicios y asignarse la direcci
´
on R y mi con
la que contar
´
a de ahora en m
´
as luego del proceso de mezcla;
ver algoritmo 10.
Procesamiento MAN2. El procesamiento MAN2 del algo-
ritmo 11 es muy similar al del MAN1, s
´
olo se diferencia que
al restablecer los servicios y asignar la direcci
´
on R, utiliza
los campos de datos y procedimientos del mecanismo 2. Por
ende, el algoritmo cuando reconstruye la direcci
´
on R final,
debe tener el mismo efecto que si se hubiese reconstruido
la direcci
´
on R mediante procesamiento MAN1.
VI. CONCLUSIONES
En este art
´
ıculo, hemos presentado los algoritmos de
fragmentaci
´
on y mezcla que completan las funcionalidades
de ANTop, permitiendo que le mismo funcione correc-
tamente para redes ad-hoc o de sensores, donde adem
´
as
de proveer una infraestructura es necesario asegurar un
m
´
ınimo de consumo de energ
´
ıa y una maximizaci
´
on de
la capacidad de transmisi
´
on de informaci
´
on. Tal como se
ha mencionado en la introducci
´
on., otros protocolos para
redes ad-hoc (BATMAN
´
o BABEL por ejemplo) construyen
y mantiene tablas de ruteo por cada destino, y para ello
utilizan los mecanismos de inundaci
´
on de mensajes que son
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
81
http://elektron.fi.uba.ar
Algorithm 9 Procesamiento MAR2
Require: Paquete MAR2
Ensure: None
1: Suspender el env
´
ıo y procesamiento de paquetes HB;
2: Suspender el servicio Rendez Vous;
3: if la direcci
´
on destino del MAR2 es la dir. secundaria then
4: m
secundaria
= mascara M AR2;
5: Enviar confirmaci
´
on MAN2 al nodo que env
´
ıo MAR2;
6: Tratamiento de mecanismo 2 a la direcci
´
on secundaria;
7: if el tratamiento de direcci
´
on primaria ocurri
´
o then
8: Reanudar servicio de HB y Rendez Vous;
9: end if
10: return;
11: end if
12: Asignar el n
´
umero de red del campo del paquete MAR2;
13: m = mascara M AR2;
14: mi = m;
15: Borrar tabla de nombres Rendez Vous;
16: if tiene vecinos a distancia 1 de la direcci
´
on primaria then
17: Enviar MAR2 a los hijos que tienen enlace principal,
excepto el nodo que env
´
ıo MAR2;
18: Por cada MAR2 enviado, sumar 1 a m;
19: end if
20: Borrar tabla de vecinos;
21: if no se env
´
ıo paquete MAR2 then
22: Enviar confirmaci
´
on MAN2 al nodo que env
´
ıo MAR2;
23: Tratamiento de mecanismo 2 a la direcci
´
on primaria;
24: Borrar tabla de direcciones recuperadas;
25: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on secundaria ocurri
´
o then
26: Reanudar servicio de HB y Rendez Vous;
27: end if
28: else
29: Enviar confirmaci
´
on MAN2 al nodo que env
´
ıo MAR2;
30: end if
31: return;
Algorithm 10 Procesamiento MAN1
Require: Paquete MAN1
Ensure: None
1: if si a
´
un no se restableci
´
o el servicio de HB y Rendez Vous
then
2: if la direcci
´
on primaria es igual a la direcci
´
on por defecto
then
3: Asignar la direcci
´
on R primaria inicial;
4: m = m + 1;
5: Reanudar servicio de HB y Rendez Vous;
6: else
7: Tratamiento de mecanismo 1 a la direcci
´
on primaria y
a la tabla de direcciones recuperadas;
8: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on primaria y secundaria ocurri
´
o then
9: Reanudar servicio de HB y Rendez Vous;
10: end if
11: end if
12: end if
13: return;
Algorithm 11 Procesamiento MAN2
Require: Paquete MAN2
Ensure: None
1: if si a
´
un no se restableci
´
o el servicio de HB y Rendez Vous
then
2: Tratamiento de mecanismo 2 a la direcci
´
on primaria;
3: Borrar tabla de direcciones recuperadas;
4: if no tiene direcci
´
on secundaria o el tratamiento de la
direcci
´
on primaria y secundaria ocurri
´
o then
5: Reanudar servicio de HB y Rendez Vous;
6: end if
7: end if
8: return;
excesivamente costosos en t
´
erminos de energ
´
ıa y capacidad
del canal para cada nodo. Estos costos se ven reflejados
sobre todo para redes de gran tama
˜
no, que el protocolo
ANTop ha demostrado un correcto funcionamiento tal como
se ve en los trabajos [6] y [11].
Por
´
ultimo, hemos puesto a disposici
´
on del p
´
ublico una
implementaci
´
on para Linux basados en Debian, ver [12].
REFERENCIAS
[1] J. Ignacio Alvarez-Hamelin, Aline C Viana, and Marcelo D De Amo-
rim. Dht-based functionalities using hypercubes. In Ad-Hoc Networ-
king, pages 157–176. Springer, 2006.
[2] Mat
´
ıas Campolo. Estudio y an
´
alisis del funcionamiento de ANTop so-
bre IPv6. http://cnet.fi.uba.ar/matias.campolo/Tesis Matias Campolo.
pdf, 2012.
[3] J. Chroboczek. The Babel Routing Protocol. RFC 6126 (Experimen-
tal), April 2011. Updated by RFCs 7298, 7557.
[4] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and
Clifford Stein. Introduction to algorithms second edition. The Press
MIT press Cambridge, 2001.
[5] Elis Kulla, Makoto Ikeda, Leonard Barolli, and Rozeta Miho. Impact
of source and destination movement on manet performance conside-
ring batman and aodv protocols. In Broadband, Wireless Computing,
Communication and Applications (BWCCA), 2010 International Con-
ference on, pages 94–101. IEEE, 2010.
[6] Alejandro Marcu. Desarrollo y simulaci
´
on de un protocolo para redes
adhoc. http://cnet.fi.uba.ar/alejandro.marcu/Tesis Alejandro Marcu.
pdf, 2007.
[7] A Neumann, C Aichele, and M Lindner. Better approach to mobile ad-
hoc networking (batman) draft-wunderlich-openmesh-manet-routing-
00. URL: http://tools. ietf. org/html/draft-wunderlich-openmesh-
manet-routing-00 [cited 4 February, 2014], 2008.
[8] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc On-Demand
Distance Vector (AODV) Routing. RFC 3561 (Experimental), July
2003.
[9] Charles E Perkins and Pravin Bhagwat. Highly dynamic destination-
sequenced distance-vector routing (dsdv) for mobile computers. In
ACM SIGCOMM computer communication review, volume 24, pages
234–244. ACM, 1994.
[10] D. Savage, J. Ng, S. Moore, D. Slice, P. Paluch, and R. White. Cisco’s
Enhanced Interior Gateway Routing Protocol (EIGRP). RFC 7868
(Informational), May 2016.
[11] Gast
´
on Tejia. Estudio y an
´
alisis de mecanismos orientados al
robustecimiento de ANTop, utilizando ruteo proactivo. http://cnet.
fi.uba.ar/gaston.tejia/Tesis Gaston Tejia.pdf, 2010.
[12] Pablo Torrado and J. Ignacio Alvarez-Hamelin. ANTop (Adjacent
Networks Topologies) ad-hoc routing. https://github.com/CoNexDat/
ANTop, 2018.
[13] Pablo Dami
´
an Torrado. Fragmentaci
´
on y Mezcla de redes ad-hoc
utilizando el protocolo ANTop sobre IPv6. http://cnet.fi.uba.ar/pablo
torrado/Tesis Pablo Torrado.pdf, 2018.
Revista elektron, Vol. 2, No. 2, pp. 71-82 (2018)
ISSN 2525-0159
82
http://elektron.fi.uba.ar
