位相空間の最適化と計算機ネットワークの経路制御
-
TuvianNavy
- 2003
- 1
- 1
- 1
-
- いいね！1
(change of )*state
@TuvianNavy
「ヴェブレンと私は独立に，ポアンカレの「位置解析(Analysis situs)」の皮を剥いで，純粋に組合せ論的な骨組みにしたことがありますが，私たちはあえて自分たちの研究を数年間発表しませんでした」(ワイル『精神と自然』p.342)
2015-05-15 23:16:20
(change of )*state
@TuvianNavy
「開いた重み付きグラフで表現したい、時不変で無い何か」の性質を「相対性」と言ってしまうといろいろ要らざる摩擦を起こすので、少しでも状況を改善したい
2015-05-18 22:26:13
(change of )*state
@TuvianNavy
ほとんどすべての任意のグラフ理論家は同じ用語を使わない、と書いてあって、専門家のことはともかく、たしかに自分のような通信系のSEは完全グラフをフルメッシュトポロジー、隣接をネイバーと呼んでるなあ、と
2015-08-04 17:51:36
(change of )*state
@TuvianNavy
William Hamiltonの閉路とspanning treeって関係ある？と思ったらなんか変換できるっぽい
2015-05-28 21:58:04
(change of )*state
@TuvianNavy
@TuvianNavy 閉じた一筆書きの経路というのはつまり重み付けを適切にしてやれば巡回群になるということ
2015-05-28 22:00:07
(change of )*state
@TuvianNavy
@TuvianNavy 数学的にはBellman-Fordが有名、現実の実装としては経路情報のやりとりのプロトコルとアルゴリズムをひとまとめにしてOSPF（L2のSTPも同類）、EIGRP、RIPなどの種類がある
2015-05-27 04:52:30
(change of )*state
@TuvianNavy
@TuvianNavy DijkstraもBellman-Fordも単一の計算機で実行する前提の記述が普通だろうが、通信の経路制御は分散計算であり、プロトコルとアルゴリズムの間に密接な関係がある LaTeXのLamportはこの辺りが専門だった筈
2015-05-27 16:42:38
(change of )*state
@TuvianNavy
@TuvianNavy エミュレータをバックトラックさせるために確率過程のどこに居るか、という情報が必要になる
2015-05-27 16:51:21
(change of )*state
@TuvianNavy
@TuvianNavy TCP/IPのネットワークでいう「1ホップ」つまり隣接するルータ（パケット交換機）との接続はΔt→εでの「光円錐」に相当していて、隣接ルータから届く経路情報（当該ルータ近傍の幾何）の距離値（計量）を翻訳して矛盾のない全体像を作るのがルーティングアルゴリズム
2015-05-27 04:48:32なんで突然ここで相対性理論のアナロジーがぽこっと出てくるかというと、相互に通信しているゲートウェイ同士の経路表が矛盾している状態というのは「異なる慣性系から見た場合質量などが違って見える」というのと似ているからです、Lamportは分散システムでの出来事の整列が可能になるためには個々のコンポーネント間の時計のズレがどの程度でなければならないか、といったことを研究していたのです
(change of )*state
@TuvianNavy
@TuvianNavy 具体的な開集合系(高々1hopで到達可能な宛先、高々2hopで到達可能な宛先、…)を構成してみせないとポエムっていわれる
2015-05-30 04:43:12訂正：これは開集合系ではなくて近傍系ですね（特定のノードを中心に考えているから）もちろんこれでも位相は定義できてます
有限集合の場合閉集合と開集合は定義の差でしかない(必ずclopenになる)けど、たとえば「1hop未満で相互に到達可能な相異なるゲートウェイの集合」＝空集合、「2hop未満で・・・」と定義すれば開集合系、「高々0hopで相互に到達可能な相異なるゲートウェイの集合」＝空集合、「高々1hopで・・・」と定義すれば閉集合系になるはず
(change of )*state
@TuvianNavy
@TuvianNavy 実際には各ルータ上の経路表がネットワーク全体という位相多様体の局所像になっていて、その位相多様体を計算しているんだけど、関数値では使いものにもならないから具体的な経路表に落としている
2015-05-30 04:51:57
(change of )*state
@TuvianNavy
ローカルの経路表上に冗長経路が載ってる場合、これは位相多様体の単なる局所像ではないんだけど、これどうするか、やっぱり論文にして数学をちゃんと書かないとだめかも
2015-05-30 05:03:18冗長経路もそうですけどスタブエリアを許す場合など経路情報のやりとりが有向グラフになる場合も考えると実は「箙(quiver)」一般の話になっています
(change of )*state
@TuvianNavy
@TuvianNavy 実際の宇宙と計算機ネットワークの違いは、相互の通信量の多いルータ同士が勝手に「重力」で引き合って近くなったりすることはないということ（これは人間が通信料を節約するためにサーバの配置を工夫することで長期的にはそうなっていく）
2015-05-27 04:58:37
(change of )*state
@TuvianNavy
@TuvianNavy ルーティングアルゴリズムの言葉で言うshortest path firstはFermat原理のこと
2015-05-28 04:58:27
(change of )*state
@TuvianNavy
@TuvianNavy 正確には、電磁気学的真空の挙動としてのFermat原理を通信機器でエミュレートするときの名前がshortest path first
2015-05-28 05:01:18
(change of )*state
@TuvianNavy
@TuvianNavy これが変分原理として効いてくるので、network topologyは（プロトコルのある種の詳細には影響されることなく）ある最適状態に収束することになる
2015-05-28 05:03:45
(change of )*state
@TuvianNavy
@TuvianNavy ただし、メッセージの交換頻度やネットワークの初期状態、ルータの起動順序が選ばれる「最適」状態にどう寄与するか、など、細かく考えるとややこしい挙動はいくらでも出てくる（意思決定／社会選択理論と同様の議論）
2015-05-28 05:09:30
(change of )*state
@TuvianNavy
@TuvianNavy 実務上はSTPのコストやHSRP、BGPでの経路フィルタリングやLP、MED値などの設定値決定の際に「どの状態が勝ち残るか、勝ち残るべきか」という議論は普通に行なわれる
2015-05-28 05:31:54