Reconocimiento de estructura de red con Python.
Tengo el problema de que tengo que reconocer la estructura de una red “planar” (todos los dispositivos en el mismo espacio de direcciones 192.168.10.0). Los dispositivos individuales son Raspberry Pi configurados como puentes. A través de bridge-utils, puedo leer las direcciones MAC de los dispositivos anteriores. Así que tengo las direcciones MAC cruzadas para cada dispositivo.
Ahora quiero usar un algoritmo para reconocer la estructura a partir de estas direcciones MAC. La siguiente imagen muestra la estructura que estoy buscando:
estructura de red buscada
A continuación se muestra una lista de los nodos pasados para cada dispositivo (SBx significa sensor box):
SB1: mac0
SB2: mac0, mac1
SB3: mac0, mac1, mac2
SB4: mac0, mac1
SB5: mac0, mac1, mac4
SB6: mac0, mac1, mac2
SB7: mac0, mac1, mac4
Mi enfoque hasta ahora es el siguiente:
nodos = []
(nodos, cajas) = self._obtener_nodos_ordenados()
# para el cambio entre las ramas
n = []
n1_cnt = []
n2_cnt = []
for llave, valor in dict(Counter(map(len, nodos))).items():
n.append(valor)
n1_cnt = n[:]
n1_cnt.insert(0, 0)
del n1_cnt[len(n1_cnt)-1]
n2_cnt = n[:]
del n2_cnt[0]
n2_cnt.append(0)
for i in range(max_paso):
if i == max_longitud:
break
print(f'--- Paso {i+1} -----------------------')
for j, n1 in enumerate(nodos[i+n1_cnt[i]]):
print(f'Nodo (superior) {j}: {n1}')
for t in range(n2_cnt[i]):
for k, n2 in enumerate(nodos[i+t+1]):
print(f'Nodo (inferior) {k}: {n2}')
if n1 in n2:
self.__conectar_nodos(n1, n2)
print('----------------------------------')
max_paso # número máximo de pasos de la estructura
max_longitud # lista con la cantidad de nodos por paso (por ejemplo, en este ejemplo 2 nodos en el paso 1 -> SB2 y SB4)
nodos # lista 2D con todas las direcciones MAC pasadas por nodo (la lista está ordenada por longitud)
En una configuración en cadena funciona, pero tan pronto como hay una rama, hay problemas.
Gracias por tu ayuda.
Saludos, Michael
davy.ai
Solución para reconocer la estructura de una red plana
Problema
El problema en cuestión es reconocer la estructura de una red “plana” compuesta por múltiples dispositivos Raspberry Pi configurados como puentes. Los dispositivos se encuentran en el mismo espacio de direcciones
192.168.10.0
y sus direcciones MAC se pueden leer utilizandobridge-utils
. Dadas las direcciones MAC de los dispositivos anteriores, necesitamos determinar la estructura de la red.Enfoque
El enfoque adoptado hasta ahora consiste en utilizar un algoritmo para reconocer la estructura a partir de las direcciones MAC. Las direcciones MAC se han recopilado en una lista de nodos pasados para cada dispositivo (es decir,
SB1
solo tiene una dirección MAC ySB2
tiene dos). El siguiente paso es utilizar un algoritmo para reconocer la estructura a partir de estos datos.El algoritmo actual funciona en una configuración en cadena, pero encuentra problemas cuando hay una rama en la red. El algoritmo implica recorrer las ramas de la red y conectar los nodos correctamente.
Solución
Para reconocer la estructura de la red, podemos utilizar un algoritmo de recorrido de árbol. Podemos comenzar creando una estructura de datos de árbol para representar la red, donde cada nodo representa un dispositivo Raspberry Pi y sus hijos representan los dispositivos a los que está conectado. Luego podemos recorrer el árbol y conectar los nodos según sus direcciones MAC.
Se pueden seguir los siguientes pasos para implementar este enfoque:
SB1
) al árbol.SB2
aSB7
), recorrer el árbol para encontrar el nodo que coincida con la mayoría de las direcciones MAC. Si hay un empate, elegir el nodo que esté más cerca en el árbol.Una vez que se haya construido el árbol, podemos utilizar una biblioteca de
treeview
para mostrar la estructura de la red.Con este enfoque, podemos reconocer la estructura de la red incluso cuando hay múltiples ramas. La complejidad temporal de este algoritmo es O(n^2), donde n es el número de dispositivos en la red.
Conclusión
Reconocer la estructura de una red plana compuesta por dispositivos Raspberry Pi puede ser un desafío, especialmente cuando hay múltiples ramas en la red. Al utilizar un algoritmo de recorrido de árbol para construir una estructura de datos de árbol que represente la red, podemos conectar los nodos según sus direcciones MAC y reconocer la estructura de la red.