MENTOR routing algorithm

The MENTOR routing algorithm is an algorithm for use in routing of mesh networks, specifically pertaining to their initial topology. It was developed in 1991 by Aaron Kershenbaum, Parviz Kermani, and George A. Grove and was published by the IEEE.

Complexity

Empirical observation has shown the complexity class of this algorithm to be O(N²), or Quadratic. This represents "a significant improvement over currently used algorithms, [while still yielding] solutions of a quality competitive with other, much slower procedures."

Methodology

The algorithm assumes three things are conducive to low-"cost" (that is, minimal in distance travelled and time between destinations) topology: that paths will tend to be direct, not circuitous; that links will have a "high utilization"--that is, they will be used to nearly their maximum operating capacity; and that "long, high-capacity links [will be used] whenever possible."

The overall plan is to send traffic over a direct route between the source and destination whenever the magnitude of the requirement is sufficiently large and to send it via a path within a tree in all other cases. In the former case, we are satisfying all three of our goals--we are using a direct path of high utilization and high capacity. In the latter case we are satisfying at least the last two objectives as we are aggregating traffic as much as possible.

The minimum spanning tree on which traffic flows in the latter case is heuristically defined by Dijkstra's algorithm and Prim's algorithm.

References

*Aaron Kershenbaum, Parviz Kermani, George A. Grover. [http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel1%2F26%2F2681%2F00081738.pdf%3Ftp%3D%26isnumber%3D2681%26arnumber%3D81738%26type%3Dref&ei=vJ0uR6aiN52ugwPrv5iIAQ&usg=AFQjCNGG0cLqAcDfRwsWYWWJUGb7N3uzgw&sig2=mEssFbUFic40uC0lEQTIJA "MENTOR: An Algorithm for Mesh Network Topological Optimization and Routing"] , "IEEE Transactions on Communications", April 1991. Accessed November 4 2007.