The MENTOR routing algorithm is an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 for use in routing

Routing

Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...

 of mesh networks, specifically pertaining to their initial topology

Network topology

Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....

. 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

Quadratic

In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms...

. 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

Minimum spanning tree

Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...

 on which traffic flows in the latter case is heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

ally defined by Dijkstra's algorithm

Dijkstra's algorithm

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...

 and Prim's algorithm

Prim's algorithm

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...

.