MENTORルーティングアルゴリズム

MENTORルーティングアルゴリズムは、メッシュネットワークのルーティング、特に初期トポロジーに関係するアルゴリズムです。1991年にAaron Kershenbaum、Parviz Kermani、George A. Groveによって開発され、IEEEで公開されました。

複雑

経験的観察によると、このアルゴリズムの計算量はO(N²)、つまり2乗であることが示されています。これは「現在使用されているアルゴリズムに比べて大幅に改善されているにもかかわらず、他のはるかに低速な手順と競合できる品質の解が得られる」ことを意味します。

方法論

このアルゴリズムでは、低コストの（つまり、移動距離と目的地間の時間が最小限である）トポロジーを実現するために、次の 3 つの要素が考慮されていると想定しています。パスは迂回的ではなく直接的になる傾向があること、リンクの「使用率が高い」、つまり、リンクがほぼ最大限の動作容量まで使用されること、および「可能な限り、長距離で大容量のリンクが使用される」ことです。

全体的な計画は、要件の大きさが十分に大きい場合は常に送信元と宛先間の直接ルートでトラフィックを送信し、それ以外の場合はツリー内のパスを経由して送信することです。前者の場合、高い利用率と高い容量を備えた直接パスを使用しているため、3つの目標すべてを達成しています。後者の場合、トラフィックを可能な限り集約しているため、少なくとも最後の2つの目標は達成しています。

後者の場合にトラフィックが流れる最小全域木は、ダイクストラのアルゴリズムとプリムのアルゴリズムによって経験的に定義されます。

参考文献

• Aaron Kershenbaum、Parviz Kermani、George A. Grover。「MENTOR：メッシュネットワークのトポロジ最適化とルーティングのためのアルゴリズム」、IEEE Transactions on Communications、1991年4月。2007年11月4日アクセス。