lunes, 19 de mayo de 2008

Como diseñar una red cableada de datos o telefonia en forma optima usando matematica discreta y en particular el algoritmo de kruskal


Esto es un grafo con sus vertices y aristas

Hola a todos, me animo a escribir este post, debido a que en las clases de redes de datos que dicto muchas veces los estudiantes me han consultado sobre como se debe hacer el diseño de una red cableada de datos de tal manera que esta sea optima.

Optima se refiere a usar la menor cantidad de cable, conectando todos los puntos y que su diseño cumpla con las normas del cableado estructurado.

(Hacer un cableado de red usando las normas de cableado estructurado es muy pero muy diferente a tender cable de red a la loca sin ton ni son,por eso siempre traten de ajustarse a los parametros dados por la teoria del cableado estructurado)

Pues bien, debido a esas inquietudes aqui les presento un metodo matematico para hacer el diseño optimo de una red. Siii no se extrañen he escrito correctamente, metodo matematico, y no estoy loco aunque mi hija dice lo contrario.
El metodo esta basado en la teoria de matematica discreta (grafos, digrafos, arboles, matrices de adyacencia, matrices de incidencia, circuitos eulerianos y circuitos hamiltonianos)... ojo no me he fumado nada jejejej.

La solucion del problema planteado a continuacion es facil de resolver usando los grafos, luego obteniendo un arbol minimo (algo que se llama MST, minimun spannign tree) para hallar el MST pues usamos el algoritmo de kruskal el cual esta descrito mas adelante.
Bueno esta es la idea ahora paso a como hacerlo:

El problema basico planteado es el siguiente:

Tenemos una area determinada donde existen una cantidad n de oficinas y en cada oficina uno o mas puntos de red, la idea es hacer el diseño correcto del cableado estructurado de esta red, de tal manera que consumamos la menor cantidad posible de cable de red en unir todas las oficinas y los puntos de red que hay en ella.

Manos a la obra:
1.- Primero debemos tener en cuenta que por lo general los diseños de redes en la actualidad se hacen siguiendo la topologia de red llamada estrella y tambien arbol.
Pues bien si esto es asi, entonces el hallar el MST de la red se ajusta con algunas pequeñas modificaciones a las topologias estrella y arbol de una red.

2.- Realizamos el grafo correspondiente:
a.- Como tenemos un plano del area en donde se ubican las oficinas y los puntos de red (sino lo tienen pidanlo o haganlo pero que se ajuste mucho a la realidad fisica) entonces sera facil hacer el grafo correspondiente, donde tendremos que cada punto de red es un nodo o vertice y las distancias entre los puntos de red seran las aristas.
b.-Una vez obtenido el grafo correspondiente que debe ser conexo, sin lazos y no orientado entonces ya el problema se convierte en un problema netamente matematico.
c.- A partir de este grafo se debe hallar el arbol generador minimo.
d.- Para hallar el arbol minimo (MST) yo uso el algoritmo de kruskal.
e.- Una vez hallado este arbol ya es tema de llevar a la practica lo obtenido.
y que hemos obtenido, pues distancias minimas entre cada nodo y que provengan de un vertice principal que podria ser un switch de core o un siwtch de borde, depende de como hallamos hecho el diseño de la red.
Las distancias minimas pues seran los caminos que debemos tomar para colocar canaletas y el cable de red que una los puntos de red.

Pues bien esta descripcion aparentemente es compleja pero no se asusten es bastante sencilla, inclusive el desarrollo de los grafos y luego el ejecutar el algoritmo de kruskal es facil.

Umm para los novatos creo que esto seria muy buena manera de empezar a realizar sus diseños de una manera matematica y usando conceptos de ingenieria, para los ya no tan novatos como yo creo que es una buena manera de verificar si nuestros calculos empiricos son correctos y ademas es una manera de poder mejorar nuestro trabajo y optimizarla.

Para los que no siguen carreras de Ingenieria y no ven ni por asomo matematicas discretas pues no se asusten, la teoria de matematica discreta es sencilla y facilmente aplicable a muchos problemas practicos, por lo tanto con darle una leida y entender sus principios pues dominaran este tema.

A continuacion amplio informacion sobre el algoritmo de kruskal y su procedimiento para hallar el arbol minimo.
Espero que los ayude y si pueden enviar sus comentarios se los agradecedereos todos los que ampliemos nuestros conocimientos:

1.-Cuál es la aplicación práctica del Algoritmo de Kruskal?
Rpta:
La aplicación practica del Algoritmo Kruskal es la de encontrar un árbol generador mínimo es decir buscar un árbol donde los vértices y donde el valor de total de todas las aristas del árbol sea el mínimo posible
Un árbol de peso mínimo es un árbol optimo.
En el algoritmo de kruskal se tiene como origen a un grafo no dirigido, conexo y sin lazos.
Ahora el hallar un arbol de peso minimo (MST) sirve para solucionar problemas relaciones con distribución de redes de energia, redes de comunicaciones y demas problemas donde se pueda llevar este a un modelo de grafos y aquí aplicar el algoritmo de kruskal para hallar la solucion al problema.
Las aplicaciones de los árboles abarcadores mínimos son múltiples: obtención de redes eléctricas o de comunicaciones eficientes, creación de laberintos aleatorios.
Entre los problemas sobre grafos, uno de los de mayor interés por su enorme abanico de aplicaciones es la obtención del Árbol de recubrimiento de peso mínimo. En lo que sigue nos referiremos a éste árbol por las siglas de su nombre en inglés, MST (Minimum Spanning Tree).
La determinación del MST tiene innumerables aplicaciones en diversas ramas de la ciencia y la tecnología. Por ejemplo, este tipo de árboles pueden usarse directamente como base para optimizar el diseño de redes de transmisión de energía o de información cuando la topología de las conexiones debe ser (o conviene que sea) arborescente. En otras áreas, el MST puede usarse para determinar agrupamientos naturales de datos. Si tenemos una colección de datos y alguna manera de medir la disimilitud o “distancia” entre ellos, podemos ver esta colección como el conjunto de nodos de un grafo y las disimilitudes entre objetos como aristas de un grafo completamente interconectado. El
MST de un grafo de este tipo tiene la propiedad de que si se eliminan sus aristas de mayor peso (disimilitud) se obtiene un “bosque” en el que cada (sub-)árbol agrupa todos los datos similares o “próximos” entre sí.
Ejemplo de problema solucionado por el sistema de MST:
La división Créditos de Arsa libera ordenes de clientes de chapa galvanizada que forman el backlog de Expedición. Con las órdenes del backlog Expedición forma “camiones”, es decir, conjuntos de órdenes que serán transportadas por un mismo camión a una o varias localidades de las aproximadamente 250 localidades del país que demandan la chapa. El transporte por camión tiene un costo no lineal que depende de la trayectoria que une Haedo/Canning con la(s) localidad(es) destino y del tonelaje transportado. Aproximadamente se despachan 40 camiones por día, 20 desde Haedo y otros 20 desde Canning. El problema consiste en determinar la carga y ruta de esos camiones para minimizar la suma de los costos de todos los camiones despachados

2.-Explicar escuetamente el procedimiento de aplicación del Algoritmo de Kruskal.
Rpta:
Condiciones:
El algoritmo de kruskal produce un arbol generador minimo a partir de un grafo no dirigido, conexo y sin lazos, donde el numero de vértices es |V| = n
Procedimiento:
1.- Se pone el contador i =1 (i es un contador)
Seleccionamos una arista e1 tal que el peso de la misma arista sea la mas pequeña.
(si hay varias aristas con el mismo peso, elegimos cualquiera de ellas)
2.- Para un valor de 1 ≤ i ≤ n – 2 seleccionamos la arista ei+1 de las aristas restantes de modo que el peso de la misma arista sea la mas pequeña posible y no genere ciclos.
(si hay varias aristas con el mismo peso elegimos cualquiera de ellas)
3.- Reemplazamos i con i + 1
Si i = n – 1 el subgrafo determinado por las aristas e1, e2, e3 hasta en-1 es conexo con n vértices y n-1 aristas entonces ahí termina el proceso.
Pero si i < >
Como veran el procedimiento de solucion ha sido diseñado para una red cableada pero creo que tambien es posible realizarla para redes inalambricas ya que cada nodo sera un punto de red inalambrico cliente y las aristas seran la distancia maxima que puede haber para que cada nodo reciba la señal inalambrica desde el generador principal.

Un grafo es un diagrama que consta de nodos o vertices que representan un objeto , las aristas son los caminos que unen los vertices y estos pueden tener un peso o no, el peso puede ser por ejemplo la distancia en metros entre cada nodo, o cualquier medida a ser aplicable segun el caso.
Si desean saber mas sobre la teoria de grafos aqui les dejo unos links:

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/minimaexp.htm
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/kruskal/appletKruskal.htm
Este ultimo link es un applet para ver el procedimiento en forma practica.

saludos a todos

Miguel

No hay comentarios.: