Loading article…
MENTORルーティングアルゴリズムは、メッシュネットワークのルーティング、特に初期トポロジーに関連するルーティングに使用されるアルゴリズムです。1991年にAaron Kershenbaum、Parviz Kermani、およびGeorge A. Groveによって開発され、IEEEによって公開されました。
実証的な観察によると、このアルゴリズムの計算量はO(N²)、つまり2乗であることが示されています。これは、「現在使用されているアルゴリズムに比べて大幅な改善であり、同時に、はるかに処理速度の遅い他の手法と同等の品質の解が得られる」ことを意味します。
このアルゴリズムは、低コスト（つまり、目的地間の移動距離と時間が最小限）なトポロジーを実現するために、次の3つの要素が重要であると仮定しています。経路は迂回せず、直接的になる傾向があること。リンクの利用率が高いこと、つまり、リンクがほぼ最大運用容量まで利用されること。そして、「可能な限り、長くて容量の大きいリンクが使用される」こと。
全体的な計画としては、要求されるトラフィック量が十分に大きい場合は、送信元と宛先間の直接経路でトラフィックを送信し、それ以外の場合はツリー構造内の経路で送信します。前者の場合、利用率と容量の高い直接経路を使用しているため、3つの目標すべてを達成できます。後者の場合、トラフィックを可能な限り集約しているため、少なくとも最後の2つの目標は達成できます。
後者の場合にトラフィックが流れる最小全域木は、ダイクストラ法とプリム法によってヒューリスティックに定義される。