Conjunto de algoritmos MENTOR Etapa 4: Topología de acceso al backbone Método del acceso Esau-Williams Método de acceso basado en Esau-Williams La heurística asociada con el algoritmo Esau-Williams resuelve problemas relacionados con la creación de un árbol de capacidad mínima (Capacitated Minimum Spanning Tree CMST) Definición del problema del árbol de capacidad mínima (Capacitated Minimum Spanning Tree CMST): Dado un nodo central N0 y un conjunto de otros nodos (N1, N2, …, Nn), un conjunto de pesos (w1, w2, …, wn) para cada nodo, la capacidad de enlace "W", y una matriz de costos Cost(i,j), el problema consiste en hallar un conjunto de árboles T1, …Tk, tales que cada nodo Ni pertenezca exactamente a un árbol Tj, y que cada árbol Tj contenga a N0. La idea central del algoritmo Esau-Williams se basa en la función de tradeoff. La función de tradeoff se diseña para hallar puntos deseables y lograr construir buenos árboles. Inicialmente, cada nodo empieza en un árbol con 1 nodo (él mismo). Debido a que el árbol no estará conectado con el centro, nos referimos al árbol como "componente" en el sentido de la teoría de grafos. Se calcula entonces la función tradeoff para cada nodo: El tradeoff asociado con la unión de los componentes Ni y Nj calcula los ahorros potenciales de ir hacia un vecino en lugar de tener una línea hasta el nodo central. El tradeoff es atractivo sólo si éste es negativo. Mientras menor es el tradeoff (o mejor dicho, mientras más negativo) los ahorros serán más atractivos. Sin embargo, la unión entre nodos puede que no produzca un diseño válido. Existe una función que checa que se cumpla la siguiente condición: antes de que se permita la unión entre el par de nodos. El algoritmo termina cuando los tradeoff son todos positivos o se ha probado toda la lista de posibles fusiones. Los pasos del algoritmo Esau-Williams para obtener un árbol de capacidad mínima (Capacitated Minimum Spanning Tree CMST), son los siguientes:     Inicializar todos los tradeoffs: Seleccionar el tradeoff mínimo:       Si la red viola la siguiente restricción:       o bien forma trayectoria cerrada entonces:  regresar a 2.   Añadir el enlace que va del nodo "Ni" al nodo "Nj" y fijar          Si ya están todos los nodos conectados entonces terminar. De lo contrario, continuar en paso 2. El algoritmo Esau-Williams es un algoritmo heurístico que garantiza que el árbol que crea cumple con la restricción de capacidad. Generalmente, el algoritmo Essau-Williams hace un buen trabajo en hacer que pequeños nodos quepan en líneas compartidas. En todos los casos para tráfico homogéneo, se tiene menos de un 1% de los diseños que no son creíbles. Los resultados se pueden resumir de la siguiente forma: Para tráfico homogéneo, el algoritmo Esau-Williams tiende a producir buenos resultados. Para un número muy grande de nodos, la tasa de falla es mayor.

 

Algoritmo MENTOR para multiplexores acceso Esau-Williams MENTOR y MENTOR-II con árboles Esau-Williams Cuando se utiliza topología estrella para conectar a los nodos terminales con los nodos del backbone, muy probablemente el porcentaje de utilización de los enlaces sea demasiado bajo y esto vaya en contra de la premisa de tener componentes bien utilizados. Es posible utilizar los algoritmos Esau-Williams, Sharma, y MSLA para el diseño de acceso local. Estos algoritmos se pueden usar con MENTOR y con MENTOR-II. El objetivo es construir accesos de árbol en lugar de accesos en estrella. Hay dos casos a considerar:   Primer caso:  Supóngase que cada nodo terminal está conectado a un solo nodo backbone. Este caso se aplica cuando se está usando el algoritmo MENTOR original o cuando MENTOR-II ha añadido sólamente enlaces directos y no enlaces 1-commodity. Entonces la red consiste de un backbone "B" que posiblemente sea una malla y que los otros nodos "N – B" están en una conexión estrella al backbone de acuerdo a la selección del valor del parámetro a. Para cada se define Sb es el conjunto de aquellos nodos que están conectados al nodo b, pero que no forman parte del backbone. Si se restringe el problema a observar solamente a entonces se tiene un problema de acceso local que puede ser optimizado con cualquiera de los algoritmos Esau-Williams, Sharma, o MSLA    Segundo caso:  MENTOR ha añadido un enlace entre un nodo backbone y un nodo terminal, o cuando MENTOR-II ha añadido un enlace 1-commodity.  En este caso un nodo terminal "E" puede tener múltiples conexiones al backbone. Se podría tratar de añadir al nodo "E" a árboles de acceso múltiple, por ejemplo en B1 y B2, y cuidadosamente separar el tráfico que entra al backbone en B1 del tráfico que entra en B2. Sin embargo, es mucho más fácil "promover" al nodo "E" para que sea parte del backbone. El conjunto  se quedará vacío pero el punto es el remover al nodo E de otros conjuntos SE. Esto es consistente con la idea de que el backbone de la red es la parte que está conectada en malla.   Método de acceso basado en árboles Esau-Williams

 

Algoritmo MENTOR para ruteadores acceso Esau-Williams MENTOR y MENTOR-II con árboles Esau-Williams Cuando se utiliza topología estrella para conectar a los nodos terminales con los nodos del backbone, muy probablemente el porcentaje de utilización de los enlaces sea demasiado bajo y esto vaya en contra de la premisa de tener componentes bien utilizados. Es posible utilizar los algoritmos Esau-Williams, Sharma, y MSLA para el diseño de acceso local. Estos algoritmos se pueden usar con MENTOR y con MENTOR-II. El objetivo es construir accesos de árbol en lugar de accesos en estrella. Hay dos casos a considerar:   Primer caso:  Supóngase que cada nodo terminal está conectado a un solo nodo backbone. Este caso se aplica cuando se está usando el algoritmo MENTOR original o cuando MENTOR-II ha añadido sólamente enlaces directos y no enlaces 1-commodity. Entonces la red consiste de un backbone "B" que posiblemente sea una malla y que los otros nodos "N – B" están en una conexión estrella al backbone de acuerdo a la selección del valor del parámetro a. Para cada se define Sb es el conjunto de aquellos nodos que están conectados al nodo b, pero que no forman parte del backbone. Si se restringe el problema a observar solamente a entonces se tiene un problema de acceso local que puede ser optimizado con cualquiera de los algoritmos Esau-Williams, Sharma, o MSLA    Segundo caso:  MENTOR ha añadido un enlace entre un nodo backbone y un nodo terminal, o cuando MENTOR-II ha añadido un enlace 1-commodity.  En este caso un nodo terminal "E" puede tener múltiples conexiones al backbone. Se podría tratar de añadir al nodo "E" a árboles de acceso múltiple, por ejemplo en B1 y B2, y cuidadosamente separar el tráfico que entra al backbone en B1 del tráfico que entra en B2. Sin embargo, es mucho más fácil "promover" al nodo "E" para que sea parte del backbone. El conjunto  se quedará vacío pero el punto es el remover al nodo E de otros conjuntos SE. Esto es consistente con la idea de que el backbone de la red es la parte que está conectada en malla.   Método de acceso basado en árboles Esau-Williams

 

Algoritmo MENTOR II acceso Esau-Williams MENTOR y MENTOR-II con árboles Esau-Williams Cuando se utiliza topología estrella para conectar a los nodos terminales con los nodos del backbone, muy probablemente el porcentaje de utilización de los enlaces sea demasiado bajo y esto vaya en contra de la premisa de tener componentes bien utilizados. Es posible utilizar los algoritmos Esau-Williams, Sharma, y MSLA para el diseño de acceso local. Estos algoritmos se pueden usar con MENTOR y con MENTOR-II. El objetivo es construir accesos de árbol en lugar de accesos en estrella. Hay dos casos a considerar:   Primer caso:  Supóngase que cada nodo terminal está conectado a un solo nodo backbone. Este caso se aplica cuando se está usando el algoritmo MENTOR original o cuando MENTOR-II ha añadido sólamente enlaces directos y no enlaces 1-commodity. Entonces la red consiste de un backbone "B" que posiblemente sea una malla y que los otros nodos "N – B" están en una conexión estrella al backbone de acuerdo a la selección del valor del parámetro a. Para cada se define Sb es el conjunto de aquellos nodos que están conectados al nodo b, pero que no forman parte del backbone. Si se restringe el problema a observar solamente a entonces se tiene un problema de acceso local que puede ser optimizado con cualquiera de los algoritmos Esau-Williams, Sharma, o MSLA    Segundo caso:  MENTOR ha añadido un enlace entre un nodo backbone y un nodo terminal, o cuando MENTOR-II ha añadido un enlace 1-commodity.  En este caso un nodo terminal "E" puede tener múltiples conexiones al backbone. Se podría tratar de añadir al nodo "E" a árboles de acceso múltiple, por ejemplo en B1 y B2, y cuidadosamente separar el tráfico que entra al backbone en B1 del tráfico que entra en B2. Sin embargo, es mucho más fácil "promover" al nodo "E" para que sea parte del backbone. El conjunto  se quedará vacío pero el punto es el remover al nodo E de otros conjuntos SE. Esto es consistente con la idea de que el backbone de la red es la parte que está conectada en malla. Método de acceso basado en árboles Esau-Williams

 

Algoritmo AMENTOR acceso Esau-Williams MENTOR, MENTOR-II y AMENTOR con árboles Esau-Williams Cuando se utiliza topología estrella para conectar a los nodos terminales con los nodos del backbone, muy probablemente el porcentaje de utilización de los enlaces sea demasiado bajo y esto vaya en contra de la premisa de tener componentes bien utilizados. Es posible utilizar los algoritmos Esau-Williams, Sharma, y MSLA para el diseño de acceso local. Estos algoritmos se pueden usar con MENTOR, MENTOR-II y con AMENTOR. El objetivo es construir accesos de árbol en lugar de accesos en estrella. Hay dos casos a considerar:   Primer caso:  Supóngase que cada nodo terminal está conectado a un solo nodo backbone. Este caso se aplica cuando se está usando el algoritmo MENTOR original o cuando MENTOR-II (o AMENTOR) ha añadido sólamente enlaces directos y no enlaces 1-commodity. Entonces la red consiste de un backbone "B" que posiblemente sea una malla y que los otros nodos "N – B" están en una conexión estrella al backbone de acuerdo a la selección del valor del parámetro a. Para cada se define Sb es el conjunto de aquellos nodos que están conectados al nodo b, pero que no forman parte del backbone. Si se restringe el problema a observar solamente a entonces se tiene un problema de acceso local que puede ser optimizado con cualquiera de los algoritmos Esau-Williams, Sharma, o MSLA    Segundo caso:  MENTOR ha añadido un enlace entre un nodo backbone y un nodo terminal, o cuando MENTOR-II (o AMENTOR) ha añadido un enlace 1-commodity.  En este caso un nodo terminal "E" puede tener múltiples conexiones al backbone. Se podría tratar de añadir al nodo "E" a árboles de acceso múltiple, por ejemplo en B1 y B2, y cuidadosamente separar el tráfico que entra al backbone en B1 del tráfico que entra en B2. Sin embargo, es mucho más fácil "promover" al nodo "E" para que sea parte del backbone. El conjunto  se quedará vacío pero el punto es el remover al nodo E de otros conjuntos SE. Esto es consistente con la idea de que el backbone de la red es la parte que está conectada en malla. Método de acceso basado en árboles Esau-Williams

 

Algoritmo MENTour acceso Esau-Williams MENTOR, MENTOR-II, AMENTOR, y MENTour con árboles Esau-Williams Cuando se utiliza topología estrella para conectar a los nodos terminales con los nodos del backbone, muy probablemente el porcentaje de utilización de los enlaces sea demasiado bajo y esto vaya en contra de la premisa de tener componentes bien utilizados. Es posible utilizar los algoritmos Esau-Williams, Sharma, y MSLA para el diseño de acceso local. Estos algoritmos se pueden usar con MENTOR, MENTOR-II, AMENTOR y con MENTour. El objetivo es construir accesos de árbol en lugar de accesos en estrella. Hay dos casos a considerar:   Primer caso:  Supóngase que cada nodo terminal está conectado a un solo nodo backbone. Este caso se aplica cuando se está usando el algoritmo MENTOR original o cuando MENTOR-II (o AMENTOR o MENTour) ha añadido sólamente enlaces directos y no enlaces 1-commodity. Entonces la red consiste de un backbone "B" que posiblemente sea una malla y que los otros nodos "N – B" están en una conexión estrella al backbone de acuerdo a la selección del valor del parámetro a. Para cada se define Sb es el conjunto de aquellos nodos que están conectados al nodo b, pero que no forman parte del backbone. Si se restringe el problema a observar solamente a entonces se tiene un problema de acceso local que puede ser optimizado con cualquiera de los algoritmos Esau-Williams, Sharma, o MSLA    Segundo caso:  MENTOR ha añadido un enlace entre un nodo backbone y un nodo terminal, o cuando MENTOR-II (o AMENTOR o MENTour) ha añadido un enlace 1-commodity.  En este caso un nodo terminal "E" puede tener múltiples conexiones al backbone. Se podría tratar de añadir al nodo "E" a árboles de acceso múltiple, por ejemplo en B1 y B2, y cuidadosamente separar el tráfico que entra al backbone en B1 del tráfico que entra en B2. Sin embargo, es mucho más fácil "promover" al nodo "E" para que sea parte del backbone. El conjunto  se quedará vacío pero el punto es el remover al nodo E de otros conjuntos SE. Esto es consistente con la idea de que el backbone de la red es la parte que está conectada en malla. Método de acceso basado en árboles Esau-Williams