ノート/ノート
訪問者 1258   最終更新 2008-06-24 (火) 11:01:06

遅延は距離的か?

ネットワーク上の遅延を距離とみなせるのか?
理想的には、各ノード間の遅延を(2次元平面状の)距離でモデルできれば、 いろいろなことが考えやすくなるだろう。
でも、2次元平面になっているのか?もう少し緩めるとしても、距離の条件 である「三角形の2辺の長さの和は、残りの1辺より長い」が成り立つのか?

≪前提の一言≫遅延は輻輳などの状況を考えると大きく振れるのだが、ここでは それは無視する。日現実ではあるが、出発点として「回線上に他には通信がない、 ルータの負荷もゼロである」と考えておく。

ネット側にも制約を設けなければならない。極端な例として全てが片方向通信しか 出来ないようなリンクの場合では、簡単に成り立たなくなるだろう。

A ---(遅延1)---> B ---(遅延1)---> C
^                                 |
+--------------(遅延3)------------+

のようなネットワークは存在する(たとえばA->B, B->Cは地上回線、 C->Aは衛星回線)が、上記の条件は成り立たなくなる。

では、通信が必ず双方向で、両方向の遅延がほぼ同じとするとどうなるだろうか? 両方向で同一とすれば、グラフは指向性である必要はなく、無向性でよい。 点XからYへの経路が複数ある場合、(通常のネットワークでの選択として) その中の最短の経路を選択するとしよう。つまり無向性グラフ上の最短経路を 「距離」とするときの問題となる。(これはほぼ自明か?)

最短経路というところがミソになろう。点A,B,C間の距離を考えるとき、 もしA−Cの距離として、Aから直接Cへ行く経路が長く、A−B−Cのように Bを経由する方が短いとしたら、A−Cの距離としてA−B−Cの距離を採用する ことになる(最短経路だから)。だから必ず、A−Cの距離はA−B−Cの距離 と等しいかそれより短い。

というわけで、安心して三角形の性質は信じてよさそうだ。でも、平面に置けるとは 限らない。たとえば、辺ABを共通とする正三角形ABC,ABDがあって、 CD間の距離も1だったら、正四面体になってしまう。CD間の距離がちょうど ルート2で無い限り、それより長くても短くても平面にはならないだろう。短ければ 普通見慣れた立体になる。長いと??

現実には、長い方がよく起こりそうだ。CDがまっすぐだと思うからいけないので、 回線が少し寄り道していれば長くなるだろう。他方、物理的に平面状にABCDが 配置されていると、CDが物理的な距離より短くなることは難しかろう。

というわけで、双方向回線とし、最短経路を選ぶとしても、平面ではモデル化 できない、少なくともしづらいケースがある、と思う。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-06-24 (火) 11:01:06 (3342d)