Siempre que se acerca la fecha de entrega de cualquier proyecto, el estrés aumenta considerablemente. A la cercanía de la fecha se sumaba que llevábamos toda la mañana sin conexión de red y, por lo tanto, no podíamos acceder a los repositorios que están en la delegación central, para poder seguir con el trabajo. Mi superior inmediato, Gaznápiro, no paraba de pasear de arriba a abajo de la sala, y cada vez que pasaba ante nosotros refunfuñando, mi compañero, el señor Lego se mostraba visiblemente más nervioso. Como uno ya está de vuelta de casi todo y he acabado asumiendo que los problemas de mis jefes son de mis jefes y no míos (al igual que los sueldos de mis jefes son de mis jefes y no míos) cogí al señor Lego del brazo y casi arrastrándolo lo saqué fuera de la oficina para invitarle a un café.
Siempre se cae la red cuando más falta hace -se quejaba el sr. Lego- A ver si inventan una red a prueba de fallos.
De hecho, sr. Lego, las redes TCP/IP actuales son tolerantes a fallos -empecé a decir-. En la teoría, claro. Están diseñadas para que si un nodo de la red cae, se pueda reencaminar el tráfico por otro.
El Sr. Lego me confesó que no tenía muy claro eso de las redes, los nodos, los caminos y los paquetes. ¿cómo decide un router a qué nodo tiene que enviar un paquete?
Bueno Sr. Lego, en realidad los conceptos detrás del diseño de redes vienen de lejos y no son tan complicados. Si quiere le cuento algunas cosas que aprendí mientras trabajaba con mi amigo Descollante como administrador de redes.
El Sr. Lego no contestó, así que interpreté que me permitía, sin mucho entusiasmo, seguir adelante.
Para simplificar usaremos los grafos para modelar las redes. Un grafo está compuesto por un conjunto de nodos que pueden o no estar conectados entre sí. En nuestro modelo, la velocidad de transmisión puede ser distinta entre dos nodos, ya sea por limitaciones físicas, técnicas o simplemente por que haya más tráfico en un enlace concreto. Para representar esto le damos un peso a cada enlace o arista. Esto es lo que se llama un grafo ponderado. Para simplificar, vamos a suponer que la comunicación es siempre bidireccional entre nodos, aunque en la vida real podría darse el caso de que dos nodos sólo pudieran comunicarse en un sentido (por un cortafuegos, por ejemplo) o incluso que la velocidad fuera distinta en un sentido y el otro (porque haya más paquetes esperando ser enviados en un sentido, por ejemplo). En ese caso usaríamos un digrafo o grafo dirigido para representar el modelo.
Cogí una servilleta e hice el siguiente esquema.
Cada nodo representa un router en la red, y cada línea es un enlace con su peso (velocidad de transmisión). En una red real, los pesos podrían cambiar dinámicamente según las condiciones de la red (tráfico, caída de un enlace, interferencias o ruidos en la comunicación, etc...). Para nuestro ejemplo lo supondremos estático por simplificar.
Ya veo, entonces para ir del nodo 1 al 4 podemos coger el camino 1-3-4 y 1-2-4 ¿no?
Efectivamente sr. Lego, de hecho también podríamos coger el 1-3-2-4 o el 1-2-3-4. O incluso los routers podrían decidir por su propia cuenta seguir la ruta 1-2-3-1 indefinidamente. Es lo que se llama un bucle o ciclo, y es muy importante que un paquete que se transmita por la red no quede dando vueltas en un bucle y no llegue a su destino. ¿Alguna idea de como solucionarlo sr. Lego?
Bueno, podríamos hacer que los paquetes lleven la cuenta de por cuántos routers han pasado y si supera cierta cantidad, pues se descartan.
Bien sr. Lego, de hecho en TCP/IP, los routers van aumentando un contador de saltos que tiene el paquete de forma que cuando superan un valor llamado TTL (Time To Live) estos son descartados. Esto soluciona el problema de que no queden indefinidamente dando vueltas por la red, pero no soluciona el problema de que entren en un bucle. Para este caso, nos interesaría obtener un grafo en el que hayamos eliminado los bucles, o lo que es lo mismo, un árbol que mantenga un único camino posible entre nodos, y a ser posible, que los caminos que queden sean los mejores. Es lo que se conoce como árbol de expansión, árbol recubridor o spanning tree, como dicen los hijos de Shakespeare.
Kruskal, que por cierto falleció no hace muchos meses, fue un matemático que propuso un algoritmo para encontrar el árbol de expansión mínimo de un grafo dado. Es mínimo porque el árbol que nos interesa es aquel en el cual la suma de los pesos de las aristas es mínimo.
Los pasos del algoritmo de Kruskal son los siguientes:
1 - Se selecciona la arista con menor valor (si hay más de una, cualquiera de ellas).
2 - Repetir el paso 1 siempre que la arista elegida no forme ciclo con cualquiera de las seleccionadas anteriormente.
3 - El algoritmo termina cuando hemos seleccionado n-1 aristas del grafo (n=número de nodos), o lo que es lo mismo, todos los nodos tienen alguna arista seleccionada.
En nuestro ejemplo el algoritmo sería:
- Seleccionamos la arista (2,4) con peso 1
- Seleccionamos la arista (2,3) con peso 2
- Seleccionamos la arista (5,7) con peso 2
- Seleccionamos la arista (5,6) con peso 2
- Seleccionamos la arista (3,5) con peso 2
- Descartamos la arista (6,7) con peso 3, ya que forma ciclo con (5,6) y (5,7).
- Seleccionamos la arista (1,2) con peso 3
En este punto hemos acabado, ya que tenemos n-1 aristas seleccionadas, quedando el siguiente árbol de expansión.
Ahora podríamos enviar un paquete desde un punto a otro de la red con la seguridad de que nunca entrará en un bucle. Protocolos como STP (Spanning Tree Protocol) se encargan de construir este tipo de árboles dentro de una gran red, aunque utilizan mecanismos adicionales algo más complejos que los de Kruskal. Estos protocolos actúan en el nivel 2 de la capa OSI.
Además el camino será siempre mínimo -dijo el sr. Lego mientras apuraba su taza de café.
Fijesé sr. Lego que el algoritmo de Kruskal nos asegura que la suma de los pesos de las aristas será mínimo, pero nada más. Por ejemplo, si quisiera enviar un paquete del nodo 6 al 7, si lo hacemos a través del árbol de expansión tendríamos que seguir el camino 6-5-7 con un coste de 4. Mientras que en el grafo original hubiéramos llegado directamente con el camino 6-7 con un coste de 3.
Los actuales algoritmos de enrutamiento como RIP (Routing Information Protocol), BGP (Border Gateway Protocol) u OSPF (Open Shortest Path First), que actúan en el nivel 3 de la capa OSI, son capaces de encontrar el camino más óptimo a partir de las condiciones actuales de la red (tráfico, congestión, estado de los enlaces, etc...). La mayoría de estos protocolos se basan en un algoritmo creado por Edsger Dijkstra, que es un algoritmo (del tipo voraz) capaz de encontrar el camino más corto en un grafo o digrafo ponderado como es el caso de nuestra red de ejemplo. Concretamente se encarga de calcular la distancia mínima de un nodo inicial al resto de nodos del grafo.
En el algoritmo de Dijkstra se etiqueta cada nodo con la tupla [dist, padre] donde la dist es la distancia mínima desde el nodo inicial (distancia acumulada) y padre es el nodo predecesor en el camino mínimo que une el nodo inicial con el que se está calculando.
Básicamente los pasos del algoritmo son:
1 - Seleccionamos el nodo no visitado con menor distancia acumulada.
2 - Sumamos la distancia acumulada con la distancia a los nodos adyacentes y los etiquetamos con [dist, padre]. En caso de que alguno de los nodos adyacentes esté ya etiquetado nos quedamos con el de menor distancia acumulada.
3 - Marcamos el nodo actual como visitado y regresamos al paso 1.
Pero mejor lo vemos con un ejemplo. Vamos a calcular el camino mínimo desde el nodo 1 al resto de nodos en nuestro grafo -dije mientras acumulaba una buena provisión de servilletas en las que dibujar.
Elegimos el primer nodo (el nodo 1) y lo marcamos con distancia 0 y sin padre.
Etiquetamos los dos nodos adyacentes con la distancia y el nodo predecesor.
También marcamos el nodo 1 como visitado (en rojo).
Seleccionamos el nodo con menor distancia acumulada. En este caso el 2 que tiene peso acumulado 3. Seleccionamos los nodos adyacentes y los etiquetamos con el peso acumulado (peso del nodo actual más el peso de la arista del nodo adyacente). Como padre ahora pondremos el nodo 2.
Como ves el nodo 3 tiene ahora dos etiquetas, así que nos quedamos con la de menor peso.
Marcamos el nodo 2 como visitado.
Seleccionamos el nodo 4 que es el de menor peso acumulado. En este caso ya no tenemos en cuenta el nodo 2 porque ya está marcado como visitado ni el nodo 3 porque el peso acumulado que tiene marcado es menor que el nuevo, así que etiquetamos el nodo 5 y marcamos el 4 como visitado.
El siguiente nodo de menor peso acumulado es el 3. Como el 4 ya está visitado sólo nos queda por etiquetar el 5. En este caso, como el nuevo peso acumulado es menor reetiquetamos con el nuevo peso y el nuevo padre. Marcamos el nodo 3 como visitado.
Seleccionamos el nodo 5 y etiquetamos los dos nodos adyacentes no vitados. Seguidamente lo marcamos como visitado.
Finalmente seleccionamos el 6 y como no mejora el peso acumulado hasta el nodo 7 no cambiamos la etiqueta. Lo mismo ocurre con el 7, así que marcamos ambos como visitados y obtenemos finalmente los siguientes pesos y caminos:
Ahora podemos responder cualquier pregunta que nos hagan sobre el grafo. Por ejemplo:
¿Cuál es la distancia (peso) mínima desde el nodo 1 al nodo 7? Directamente podemos contestar que es 9, ya que es su peso acumulado.
¿Cuál es el camino mínimo del nodo 1 al 7? Sólo hay que mirar quién es el padre del nodo 7 e ir recorriendo el camino hacia atrás viendo quién es el padre de cada nodo hasta llegar al 1. En este caso, el camino mínimo es 1-2-3-5-7.
El Sr. Lego parecía pensativo mientras terminaba de dibujar los esquemas.
¿Y esto se podría aplicar, por ejemplo, a el cálculo de la ruta más corta para un viaje por carretera? -dijo el Sr. Lego
Claro que sí, y también para la obtención de la mejor ruta para un viaje en metro. Las aplicaciones son muchas y muy variadas.
Ya de vuelta en la oficina el Sr. Lego se enfrascó en la tarea de hacer una implementación del algoritmo de Dijkstra mientras se recuperaba la conectividad en la red y este fue el resultado.
- import sys
- def dijkstra(grafo, nodo_inicial):
- etiquetas = {}
- visitados = []
- pendientes = [nodo_inicial]
- nodo_actual = nodo_inicial
- # nodo inicial
- etiquetas[nodo_actual] = [0,'']
- # seleccionar el siguiente nodo de menor peso acumulado
- while len(pendientes) > 0:
- nodo_actual = nodo_menor_peso(etiquetas, visitados)
- visitados.append(nodo_actual)
- # obtener nodos adyacentes
- for adyacente, peso in grafo[nodo_actual].iteritems():
- if adyacente not in pendientes and adyacente not in visitados:
- pendientes.append(adyacente)
- nuevo_peso = etiquetas[nodo_actual][0] + grafo[nodo_actual][adyacente]
- # etiquetar
- if adyacente not in visitados:
- if adyacente not in etiquetas:
- etiquetas[adyacente] = [nuevo_peso, nodo_actual]
- else:
- if etiquetas[adyacente][0] > nuevo_peso:
- etiquetas[adyacente] = [nuevo_peso, nodo_actual]
- del pendientes[pendientes.index(nodo_actual)]
- return etiquetas
- def nodo_menor_peso(etiquetas, visitados):
- menor = sys.maxint
- for nodo, etiqueta in etiquetas.iteritems():
- if etiqueta[0] < menor and nodo not in visitados:
- menor = etiqueta[0]
- nodo_menor = nodo
- return nodo_menor
- if __name__ == "__main__":
- grafo = {
- '1': {'3':6, '2':3},
- '2': {'4':1, '1':3, '3':2},
- '3': {'1':6, '2':2, '4':4, '5':2},
- '4': {'2':1, '3':4, '5':6},
- '5': {'3':2, '4':6, '6':2, '7':2},
- '6': {'5':2, '7':3},
- '7': {'5':2, '6':3}}
- etiquetas = dijkstra(grafo, '1')
- print etiquetas
No hay comentarios:
Publicar un comentario