The MENTOR routing algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for use in
routing
Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched ...
of
mesh networks, specifically pertaining to their initial
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
. 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,
hile still yieldingsolutions 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
ill be usedwhenever 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
heuristic
A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
ally defined by
Dijkstra's algorithm and
Prim's algorithm.
References
*Aaron Kershenbaum, Parviz Kermani, George A. Grover
"MENTOR: An Algorithm for Mesh Network Topological Optimization and Routing" ''IEEE Transactions on Communications'', April 1991. Accessed November 4, 2007.
Routing algorithms
Mesh networking
{{compu-network-stub