Algoritmo de enrutamiento MENTOR

El algoritmo de enrutamiento MENTOR es un algoritmo para el enrutamiento de redes malladas , específicamente en lo que respecta a su topología inicial . Fue desarrollado en 1991 por Aaron Kershenbaum, Parviz Kermani y George A. Grove, y publicado por el IEEE.

La observación empírica ha demostrado que la complejidad de este algoritmo es O(N²), o cuadrática . Esto representa una mejora significativa con respecto a los algoritmos utilizados actualmente, al tiempo que ofrece soluciones de una calidad comparable a la de otros procedimientos mucho más lentos.

El algoritmo parte de la base de que tres factores contribuyen a una topología de bajo "coste" (es decir, con una distancia y un tiempo mínimos entre destinos): que las rutas tenderán a ser directas, no indirectas; que los enlaces tendrán una "alta utilización", es decir, se utilizarán casi a su máxima capacidad operativa; y que "se utilizarán enlaces largos y de alta capacidad siempre que sea posible".

El plan general consiste en enviar el tráfico por una ruta directa entre el origen y el destino cuando la magnitud del requerimiento sea suficientemente grande, y enviarlo a través de una ruta dentro de un árbol en todos los demás casos. En el primer caso, cumplimos con nuestros tres objetivos: utilizamos una ruta directa con alta utilización y alta capacidad. En el segundo caso, cumplimos al menos con los dos últimos objetivos, ya que agregamos el tráfico tanto como sea posible.

El árbol de expansión mínima por el que fluye el tráfico en este último caso se define heurísticamente mediante el algoritmo de Dijkstra y el algoritmo de Prim .

• Aaron Kershenbaum, Parviz Kermani, George A. Grover. "MENTOR: Un algoritmo para la optimización topológica y el enrutamiento de redes malladas" , IEEE Transactions on Communications , abril de 1991. Consultado el 4 de noviembre de 2007.