The MENTOR routing algorithm is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

for use in

routing Routing is the process of selecting a path for traffic in a 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 telephone netw ...

mesh networks A mesh network is a local area network topology in which the infrastructure nodes (i.e. bridges, switches, and other infrastructure devices) connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate wit ...

, specifically pertaining to their initial

topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...

. 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 A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...

on which traffic flows in the latter case is

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...

ally defined by

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

and

Prim's algorithm In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every v ...

References

{{Reflist *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