横田祐
STPは、ネットワークトポロジーでループが生じた場合に、ブロードキャストパケットが飛び交ってしまい、通信できなくなる障害を回避するために考案された。STPのないネットワークは重みが全て１のグラフである。だから、ループが生じるとパケットの経路がわからなくなる。STPの一番重要な点はネットワークというグラフに重みを導入することである。だから、STPは最短経路の計算と同じ種類の問題である。重みがあるから「最短」を考えられるのであり、重みがなければ「最短」も「最長」もわからない。トポロジーは相互に変形可能な２つの図形を同じと考えるのであり、長さは考慮されないから。重み＝長さを考慮すればトポロジーではなく、重みつきのグラフである。
さて、拙作の最短経路の計算では、あるゲームの町々を移動する時のコスト(所要日数や移動費用)を考慮して、最短経路を計算する。STPと違うのはループを回避するアルゴリズムはプログラムに内蔵されている点である(後述)。最短経路の計算で問題となるのは、当然、計算コストである。経路の探索では２つの町の移動コストを最適化しながら畳み込んで行くから、大雑把に見積もって、計算コストはO(n2)である。これは、少ない節(ノード)では問題ないが、例えばノードが1万となると、計算量は1億倍となる。アドレスで考えよう。IPv4(32bitアドレス)では計算量は最大64bitアドレス全部となる。IPv6(128bitアドレス)では計算量は最大256bitアドレス全部となる。そして、その計算は全てのノードが別々に行う必要がある。なぜなら、経路情報はパケットに入っていないから(入っているのは宛先アドレスと送信元アドレスだけ)。固定長パケットだからそうなる。STPだけではなくNATでも同じ問題が起こる。ノンブロッキングハブのようにノード数2128のグラフを解かなければならない。NAPTなら16bitポートも入れてノード数2144のグラフを解かなければならない。
STPではループを作っているノードのうち、特定のノード間の通信を遮断することで実質的にループを無効化している。拙作の最短経路プログラムでは、アルゴリズムとして、ループを検出した場合にその経路候補を破棄している。STPのように自発的？に計算する方法もある。それは、ループを形成しないように特定のノード間の移動コストを極端に大きくすることである。