Conjunto de algoritmos MENTOR

Etapa 2: Creación de la topología inicial
Método basado en árboles Prim-Dijkstra

    Método de construcción de árboles Prim-Dijkstra

    Para explicar el algoritmo Prim-Dijkstra, es necesario recordar que éste nace a partir de la conjunción del algoritmo  Prim y del algoritmo Dijkstra.  Ambos algoritmos se encargan de construir árboles. El algoritmo de Prim trata de minimizar el costo de los enlaces al escoger enlaces pequeños. Debido a que el árbol es bastante circuitoso, sin embargo, las longitudes de ruta son demasiado largas para construir una red útil. El algoritmo de Dijkstra produce nodos en donde la mayoría del tráfico transita a través de un nodo central. Esto produce rutas mucho más cortas pero puede producir redes muy caras. Mediante el algoritmo Prim-Dijkstra es posible obtener soluciones intermedias que produzcan árboles en donde los enlaces no sean tan caros como en un árbol SPT (Shortest Path Tree) o las rutas tan largas como en un MST (Minimum Spanning Tree). 

    Ambos algoritmos inician dando a cada nodo una etiqueta inicial, y en ciclos buscan entre los nodos para hallar aquél con la etiqueta más pequeña, incorporando al árbol al nodo con la etiqueta más pequeña y finalmente reetiquetando a todos los vecinos.

    En ambos casos podemos en forma eficiente obtener al nodo vecino más cercano al reetiquetar los vecinos de cada nuevo nodo que se incorpora en el árbol. La idea es construir un árbol al iniciar con un nodo e incorporando nodos al árbol al seleccionar aquél que tenga la mejor etiqueta. Para el árbol Prim-Dijkstra la etiqueta es:

    Donde 0 <= a <= 1 es una constante que se usa para parametrizar los cálculos.

    Para dos valores de a, el significado en los árbols Prim-Dijkstra es claro: Si a=0, entonces se construye un árbol MST. Si a=1, entonces construimos un árbol SPT a partir de la raíz. Esto se observa al revisar las etiquetas usadas en el algoritmo de Prim y en el algoritmo de Dijkstra:
     



    Para valores intermedios de a, se construye un árbol que interpola entre un árbol MST y un árbol SPT. 

    A diferencia del algoritmo de Prim, que puede iniciar de cualquier vértice, la selección del nodo al centro del árbol es muy importante en el algoritmo de Prim-Dijkstra. Antes de invocar el algoritmo, se debe seleccionar un vértice como raíz.
     

    Las siguientes secciones explican con detalle los siguientes temas:
     


 
    Grafos con pesos y árboles de extensión mínima
     
     
    • Definición:
    Un grafo G tiene pesos si tiene un número real asociado a cada arco (edge). El peso de un arco se denota por w(e). Y con frecuencia denotaremos al grafo como (G, w). Si G’ es cualquier subgrafo de G, entonces 

    A menos que se especifique lo contrario, se supondrá que la función de asignación de peso "w(e)" asigna un peso positivo.

    Si G está conectado, entonces se desea seleccionar un subgrafo conectado con el peso mínimo. Es fácil de entender que G debe ser un árbol. Si el grafo no es un árbol, entonces contiene ciclos. Removiedo el arco "e" que tenga el mayor peso en el ciclo, aún así se tendrá un grafo conectado. Debido a que w(e) > 0, entonces se reduce el peso.

    El problema de hallar árboles de extensión mínima (Minimum Spanning Trees MST) es el tema de 2 algoritmos importantes de la teoría de grafos. A continuación se presentan:
     

       
    • Algoritmo de Kruskal:
      El algoritmo es el siguiente:
      1. Revisar que el grafo está conectado. Si no lo está, cancelar.
      2. Ordenar los arcos del grafo G en orden ascendente de pesos.
      3. Marcar cada nodo como un componente separado.
      4. Continuar revisando los arcos hasta que se haya aceptado |G| -1. Sea "e" el arco candidato.
        • Si los dos extremos de "e" están en diferentes componentes, juntar los dos componentes y aceptar el arco.
        • Incrementar en 1 el número de arcos aceptados.
    El punto esencial del algoritmo de Kruskal es que solamente añade enlaces que conectan 2 piezas previamente no conectadas al grafo. Después de añadir |V| -1 arcos el grafo está conectado.
     
     
    • Algoritmo de Prim
      El algoritmo de Prim se comporta en forma diferente. En lugar de ordenar los arcos desde un principio, empieza con un árbol que consiste de un nodo simple y sin arcos, T0= (v, f). Para ir de T0 al siguiente árbol, T1, añadiendo al arco de costo más bajo que sea posible. Esto involucra examinar todos los nodos que sean adyacentes a "v" y hallar aquél que está conectado a "v" por el arco con el menor peso.


    En realidad, se está hallando en cada iteración al nodo que contenga la etiqueta con el mínimo valor de la siguiente expresión:

    Teorema:. 
     

      Si G es un grafo con pesos asociados a los arcos, entonces los algoritmos de Kruskal y Prim producen un árbol de extensión mínima.
    Al ordenar los pesos de los arcos, el algoritmo de Kruskal se asegura que nunca sea considerado un enlaces antes de que se hayan considerado todas las alternativas con pesos más bajos. Solamente rechaza los arcos entre extremos en el mismo componente. En este caso ya había una ruta entre los extremos de el arco, y al añadirlo se produciría un ciclo. Los demás arcos en el ciclo tendrían un menor peso debido a que fueron añadidos previamente, por lo que el arbol producido debe ser un árbol de extensión mínima MST.

    En el algoritmo de Prim se extiende al árbol un nodo o un arco a la vez. Debido a que siempre se escoge al arco más corto posible, el árbol resultante debe ser un árbol de extensión mínima ó MST.


 
    Arboles de ruta más corta - Shortest Path Trees (SPT)

    Dado un grafo conectado G, el algoritmo de Prim construye un árbol MST (Minimum Spanning Tree). Un árbol MST no tiene ningún nodo distinguido, esto es, dado cualquier nodo inicial para el algoritmo de Prim, construimos el mismo árbol MST si éste es único. Hay otro algoritmo famoso de la teoría de grafos, el algoritmo de Dijkstra, que construye un grafo con un nodo como raíz. Pero antes de ver el algoritmo de Dikjstra se necesitan revisar algunas definiciones:
     

        Definición:

        Dado un grafo con pesos en los arcos (G,w), y dos nodos n1 y n2, la ruta más corta de n1 a n2 es una ruta P tal que la suma de pesos en los arcos que forman parte de la ruta sea mínima.

        Una de las propiedades interesantes de las rutas mas cortas es que éstas estan anidadas. P.ej. si n3 es en la ruta mas corta "P" que va de n1 a n2, entonces podemos partir la ruta en dos partes: P1 es la parte de la ruta que va de n1 a n3, y P2 es la parte de la ruta de n3 a n2. Entonces, se puede decir que tanto P1 y P2 son las rutas más cortas entre sus puntos terminales.
         

    Dada esta observación podemos definir el árbol de ruta más corta (arbol SPT)
         
        Definición:

        Dado un grafo con pesos en los arcos (G, w) y un nodo n1, un árbol de ruta más corta con raíz en n1, es un árbol T tal que para cualquier otro nodo n2 que forma parte del grafo, la ruta que va de n1 a n2 en el árbol T es la ruta más corta entre los nodos.
         
         
         

    Algoritmo de Dijkstra para árboles SPT (Shortest Path Tree) árboles de ruta más corta:

    El algoritmo de Dijkstra es bastante eficiente para calcular el árbol SPT con raíz en un determinado nodo. A continuación se explica dicho algoritmo:

    1. Marcar todos los nodos como no revisados y dar a cada nodo una etiqueta de "infinito"
    2. Fijar la etiqueta para la raíz en "0" y el predecesor de la raíz como la raíz en si misma. La ruta será el único nodo que es su propio predecesor.
    3. Ciclar hasta que se hayan revisado todos los nodos:
      • Hallar el nodo "n" con la etiqueta más pequeña. Debido a que la etiqueta representa la distancia a la raíz, la llamaremos "d_min".
      • Marcar el nodo como revisado.
      • Revisar todos los nodos adyacentes "m" y ver si la distancia a la raiz pasando por "n" es mejor que la distancia almacenada en la etiqueta de "m". Si tal es el caso, actualizar la etiqueta y actualizar pred[m]=n
    1. Cuando termina el ciclo, tenemos un árbol almacenado en formato de predecesores, con raíz en el nodo con etiqueta "0".


    En realidad, en el paso 3 se está obteniendo al nodo con la etiqueta que contenga el mínimo valor de la siguiente expresión:

    Este código es algo diferente al código del algoritmod de Prim. Ahora se obtiene una red en lugar de un grafo. En una red cada enlace usualmente está representado por arcos con dos direcciones, 1 en cada dirección, debido a que el tráfico puede ser asimétrico y los retrasos son mayores en 1 dirección que en la otra. 
     

    Si se corre el algoritmo de Dijkstra en un grafo disperso, se obtendrá un árbol con algunos nodos que no se conectan directamanete a la raíz sino mediante nodos intermedios. Si se corre el algoritmo en un grafo completo, entonces usualmente obtendremos una estrella.
     


 
    Repaso de teoría de grafos

    Definición 1. "Grafo"

    Un grafo G consiste de un conjunto de vértices V y un conjunto de arcos E. Cada arco, "e" tiene dos puntos o vértices extremos v1 y v2. El grafo G se denota como el par (V, E).
    Los arcos generalmente conectan a 2 vértices diferentes. Sin embargo, esto no es un requerimiento.


    Definición 2. "Bucle, Rizo o Loop"

    Un loop o bucle es un arco en donde ambos extremos son el mismo punto.
    Generamlemte tenemos un arco entre cualquier par de vértices, pero no hay una razón formal para suponer esto.


    Definición 3. "Arcos Paralelos"

    Dos arcos en un grafo son paralelos si tienen los mismos extremos.


    Definición 4. "Grafo simple"

    Un grafo es simple si no tiene bucles o arcos paralelos.

    La mayoría del uso que se haga de grafos involucrarán grafos simple, sin embargo en algunas veces, cuando se considere la confiabilidad, será necesario introducir arcos paralelos si la red tiene enlaces redundantes.


    Definición 5. "Grado de un nodo"

    El grado de un nodo es el número de arcos del grafo que tienen al nodo como extremo.


    Definición 6. "Nodos adyacentes"

    Dos nodos v1 y v2 son adyacentes si hay un arco "e" que los tenga como puntos extremos.


    Definición 7. "Ruta"

    Una ruta entre dos vertices v1 y v2 consiste de un conjunto de arcos (e1, e2, …en) tales que ei y ei+1 tienen un vértice común; v1 es un extremo de e1 y v2 es un extremo de en


    Definición 8. "Ciclo"

    Un ciclo en un grafo G es una ruta no vacía de un vértice v1 hacia sí mismo.


    Definición 9. "Grafo Conectado"

    Un grafo G está conectado si, dado cualquier par de nodos v1 y v2, existe una ruta entre ellos.


    Definición 10 "Subgrafo"

    Un subgrafo G’ de un grafo G, es un par (V’, E’) en donde

    V’ es subconjunto de V

    E’ es subconjunto de E

    Si el arco "e" pertenece a E’, entonces ambos puntos extremos v1 y v2 deben pertenecer a V’.
    Un tipo especial de subgrafo es un componente. Si un grafo no está conectado, está entonces compuesto de múltiples piezas conectadas.


    Definición 11. "Componente"

    Un componente de un grafo es un subgrafo conectado máximo de V.

    A continuación se dan algunos ejemplos de componentes:

    Si G=(V,f ) es el grafo que no tiene arcos, entonces cada componente es un vértice v

    Si G=Kn es el grafo completo en n vértices, entonces hay un arco entre cada par de vértices o C(n,2) arcos en total. Este grafo está conectado. La ruta de v1 a v2 es el arco e=(v1,v2)

    Si v=(v1, v2, …,vn) se definen a los arcos como sigue: Dados 2 vértices vi y vj, hay un arco entre ellos sí y solo si i ¹ j y i – j es par. Entonces hay 2 componentes: C1=(v1, v3, v5, …) y C2=(v2, v4, v6, …)


    Definición 12: "Grafos isomórficos"

    Dos grafos G1 y G2 son isomórficos si hay un mapeo 1 a 1 f: V1 ® V2 tal que (v1, v2) Î E1 si y solo si 
    (f(v1),f(v2)) Î E2


    Definición 13. "Arbol"

    Un árbol T =(V,E) es un grafo simple conectado y sin ciclos.


    Teorema . "Relación en la cantidad de nodos y arcos en un árbol"

    Cualquier árbol con "n" nodos tiene "n-1" arcos.

    Los árboles son muy importantes en el diseño de redes. Los árboles son diseños óptimos de redes cuando se tienen enlaces de muy alta capacidad o que son sumamente caros y que no hay restricciones de confiabilidad.


    Definición 14. "Estrella"

    Un árbol T=(V, E) es una estrella si solamente 1 nodo tiene un grado mayor a 1.


    Definición 15. "Cadena"

    Un árbol T=(V, E) es una cadena si no hay un ningún nodo que tengra grado mayor a 2.

    Definición 16: "Grafo con pesos asociados"

    Un grafo G tiene pesos si tiene un número real asociado a cada arco (edge). El peso de un arco se denota por w(e). Y con frecuencia denotaremos al grafo como (G, w). Si G’ es cualquier subgrafo de G, entonces 

    A menos que se especifique lo contrario, se supondrá que la función de asignación de peso "w(e)" asigna un peso positivo.


    Definición 17: "Hop"

    El número de hops entre el nodo n1 y el nodo n2 es el número de arcos en la ruta seleccionada por el algoritmo de ruteo del tráfico que fluye de n1 hacia n2. Si se escoge una sola ruta por el algoritmo de ruteo o si todas las rutas seleccionadas tienen el mismo número de arcos, entonces se denota a dicho número como hops (n1, n2).


    Definición 18. "Número promedio de hops en una red"

    El número promedio de hops en una red, es:


    El número promedio de hops es muy importante cuando examinamos los diseños de los árboles MST. Podemos ver los hops de la siguiente forma. La suma del tráfico en todos los enlaces es igual al tráfico total multiplicado por el número promedio de hops.


    Así que el incremento en el número de hops produce un crecimiento de tráfico que atraviesa a los enlaces.

    Así, de esto es posible ver que los árboles MST no son buenas soluciones para cuando el tráfico y número de nodos empiezan a crecer. El principal problema de MST como diseños de redes, es que éstos tienden a tener rutas muy largas y circuitosas


 
 
 
    Algoritmo MENTOR para multiplexores
    árboles Prim-Dijkstra



    En la segunda etapa, se utiliza el método Prim-Dijkstra para construir un árbol conteniendo a todos los nodos backbone obtenidos en la etapa anterior:

    En el primer paso de la segunda etapa, se seleccionan los nodos backbone con el momento más pequeño para ser la mediana o centro de la red. 

    Para ello, es necesario considerar que el momento de un nodo backbone está definido por:

    En la siguiente figura se muestra que este nodo central será el nodo backbone que está dentro del círculo que contiene a las coordenadas (xctr, yctr). 

    En el segundo paso de la segunta etapa se construye un árbol híbrido Prim-Dijkstra con su nodo raíz en el centro o mediana de la red. El método Prim-Dijkstra se parametriza por un parámetro a tal que

    Lo único nuevo acerca de esta versión del  método Prim-Dijkstra es que sólamente se permite a los nodos backbone ser puntos interiores del árbol. La siguiente figura muestra al árbol Prim-Dijkstra obtenido:

 
    Algoritmo MENTOR para ruteadores
    árboles Prim-Dijkstra


    En la segunda etapa, se utiliza el método Prim-Dijkstra para construir un árbol conteniendo a todos los nodos backbone obtenidos en la etapa anterior:

    En el primer paso de la segunda etapa, se seleccionan los nodos backbone con el momento más pequeño para ser la mediana o centro de la red. 

    Para ello, es necesario considerar que el momento de un nodo backbone está definido por:

    En la siguiente figura se muestra que este nodo central será el nodo backbone que está dentro del círculo que contiene a las coordenadas (xctr, yctr). 

    En el segundo paso de la segunta etapa se construye un árbol híbrido Prim-Dijkstra con su nodo raíz en el centro o mediana de la red. El método Prim-Dijkstra se parametriza por un parámetro a tal que

    Lo único nuevo acerca de esta versión del  método Prim-Dijkstra es que sólamente se permite a los nodos backbone ser puntos interiores del árbol. La siguiente figura muestra al árbol Prim-Dijkstra obtenido:


     
     


 
    Algoritmo MENTOR II
    árboles Prim-Dijkstra


    Esta etapa es exactamente igual a la de la versión de MENTOR:

    En la segunda etapa, se utiliza el método Prim-Dijkstra para construir un árbol conteniendo a todos los nodos backbone obtenidos en la etapa anterior:

    En el primer paso de la segunda etapa, se seleccionan los nodos backbone con el momento más pequeño para ser la mediana o centro de la red. 

    Para ello, es necesario considerar que el momento de un nodo backbone está definido por:

    En la siguiente figura se muestra que este nodo central será el nodo backbone que está dentro del círculo que contiene a las coordenadas (xctr, yctr). 

    En el segundo paso de la segunta etapa se construye un árbol híbrido Prim-Dijkstra con su nodo raíz en el centro o mediana de la red. El método Prim-Dijkstra se parametriza por un parámetro a tal que

    Lo único nuevo acerca de esta versión del  método Prim-Dijkstra es que sólamente se permite a los nodos backbone ser puntos interiores del árbol. La siguiente figura muestra al árbol Prim-Dijkstra obtenido:



     
     


 
    Algoritmo AMENTOR
    árboles Prim-Dijkstra




    Esta etapa es exactamente igual a la de la versión de MENTOR y MENTOR-II:

    En la segunda etapa, se utiliza el método Prim-Dijkstra para construir un árbol conteniendo a todos los nodos backbone obtenidos en la etapa anterior:

    En el primer paso de la segunda etapa, se seleccionan los nodos backbone con el momento más pequeño para ser la mediana o centro de la red. 

    Para ello, es necesario considerar que el momento de un nodo backbone está definido por:

    En la siguiente figura se muestra que este nodo central será el nodo backbone que está dentro del círculo que contiene a las coordenadas (xctr, yctr). 

    En el segundo paso de la segunta etapa se construye un árbol híbrido Prim-Dijkstra con su nodo raíz en el centro o mediana de la red. El método Prim-Dijkstra se parametriza por un parámetro a tal que

    Lo único nuevo acerca de esta versión del  método Prim-Dijkstra es que sólamente se permite a los nodos backbone ser puntos interiores del árbol. La siguiente figura muestra al árbol Prim-Dijkstra obtenido:

 
    Algoritmo MENTour
    árboles Prim-Dijkstra


    • MENTour no utiliza a un árbol Prim-Dijkstra para obtener la topología inicial del backbone.