パスワードを忘れた? アカウント作成
5011 story

利己的なルータ 72

ストーリー by GetSet
思いやりが必要ってこと? 部門より

mpls曰く、"ZDNet の記事 に よると、コーネル大学のコンピュータ科学者(Eva Tardos、Tim Roughgarden) が、「コンピュータネットワークはそれぞれが高速回線を利用して トラフィックを振り分けようとすると「自己中心的」になる傾向があり、 回線を混雑させて速度を落としてしまう」との研究結果を発表したとの こと。
たしかに、現在の OSPF や RIP といったプロトコル (BGP も) は、 ネットワーク全体のトラフィック量をみてルーティングするわけで はないので、回線が詰まるところは詰まってしまいます。クダンの 研究者は「ネットワーク全体を見渡してルーティングすればもっと 速くなるよ。」と言いたいようですが、障害時の収束とかを考えて いるのか甚だ疑問です。全体見渡せば見渡すだけ収束が遅くなると おもわれるんですが。。。
(MPLS-TE 等の技術もあることはありますが、インターネット全体に 適用できるようなしろもんじゃありません。)"

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • うりこみ (スコア:4, 参考になる)

    by reo (4042) on 2003年02月17日 11時06分 (#260752) 日記

    現在のインターネットに導入するにはまだ遠い遠い道のりがありますが、僕が先日発表した修士論文で語られている自律分散型のルーティングでは、最短遅延経路は選択されないかわりに、自己中心的な輻輳を回避する機能を有しています。数理的解析との比較がまだなので説得力に乏しいのが難点ですが。

    自己中心的になると手痛いしっぺ返しを食らう様(べつに手痛いしっぺ返しを食らうよう仕組まれているわけではない)がグラフに表れていて興味深かったです。

    --
    Hiroki (REO) Kashiwazaki
    • by mpls (8235) on 2003年02月17日 11時37分 (#260780) 日記
      各々のルータをニューロンとみなして、ニューラルネットワークと
      してネットワークを動かして最適経路を見つけるとかやると面白い
      かもしれませんね。自分の負荷とかもニューロンの発火の因子とし
      て使えばなんとかなりそうかも。

      いつまでたっても収束しないネットワークができあがるかもしれね
      っすが。
      --
      --- show mpls ldp neighbor
      親コメント
      • Re:うりこみ (スコア:2, 興味深い)

        by reo (4042) on 2003年02月17日 12時05分 (#260802) 日記

        研究途上で考えていたことは、いったい彼ら(ルータ)は他のどのようなものと類似しているのだろうか、ということでした。#260749 [srad.jp]にあるような道路交通における最適手法の獲得手法が根本にあります。本研究室の研究紹介 [hokudai.ac.jp]にあるような旅人と道筋の住民というモデルです(ここに掲載されているのは結構古い結果なので「なーんだヘボ」とか思われるかもしれません。そして未だにヘボから脱却できていません)。それからニューロネットワークについても考え、小さな生命体から大きな生命体へと進化していくという規模拡大の途上で途切れることなく体の隅々に電気信号を送ることができる仕組みは何であろうかというのは未だに僕の興味の対象です。でも自律分散経路制御では強化学習をすることが困難というのが難点。今後そこらへんをどんどん導入しては失敗してを繰り返す予定です。

        自律分散指向のルーティングから得られる結果は非常に興味深いものであり、想像力を逞しくするならば、そこには現在の世界の紛争の構図や平和への道筋すら見えてくるような気がします。逆にさらにミクロな世界も同時に見えてきて、そういった森羅万象の記述が数値から見えてくるのは非常に楽しいものです。あとはそれが妄想でないことを実証するだけなんですけどね‥。だけ

        --
        Hiroki (REO) Kashiwazaki
        親コメント
        • by Anonymous Coward
          ナッシュ均衡というキーワードで調べていないなら、速攻で調べること。
      • by sameshima (10060) on 2003年02月17日 14時03分 (#260882) 日記
        通信が多いと太くなる
        とか。。
        親コメント
      • by Anonymous Coward
        どう読んでも人工ニューラルネットワーク(ANN)を理解した上でのコメントとは思えない…
        • by mpls (8235) on 2003年02月17日 12時31分 (#260816) 日記
          ルータでつながったネットワークって、巡回セールスマン問題に 似てたので、Hopfield 型ニューラルネットワークでなんとかでき るんじゃないかという妄想をしてみました。 とはいっても、 これ [nec.com]とか、アナログ交換機にニューラルネット [bartels.de]とか、そういうのを考えている人は いるようですよ。
          --
          --- show mpls ldp neighbor
          親コメント
          • Re:すんません (スコア:1, 参考になる)

            by Anonymous Coward on 2003年02月17日 13時23分 (#260860)
            "routing" と "neural networks" をキーワードにして検索したような結果を理解もせずに出しちゃだめですよ。両方ともANNに経路を選択させてるだけでしょ。前者は4ページの構成の図を見れば明らかだし、後者も "Rule based routing using Neural Net Technology" って冒頭に書いてあるじゃないですか。あなたが言ってるような「ルーターをニューロンと見なして…」なんていうのとは全く違う話です。
            親コメント
            • by mpls (8235) on 2003年02月17日 13時44分 (#260873) 日記
              いや、ホントにすまんです。ルータをニューロンとみなしてって
              のは勘違いも甚だしいのはよーくわかっております。Hopfield 型
              で routing ってのも、各ネットワークのノードとその間のリンク
              のコストから Matrix おこして、そこからニューラルネットをおこ
              してどーこーするってのが必要なのもよーくわかっております。

              ただ、「ニューラルネットを使ってルーティング」っていうことを
              言いたかっただけなんです。

              # そんな私の卒論/修論は Hopfield 型ニューラルネットを使った
              # 最適化についてなんですよ ;^)
              --
              --- show mpls ldp neighbor
              親コメント
              • by Anonymous Coward
                ># そんな私の卒論/修論は Hopfield 型ニューラルネットを使った
                ># 最適化についてなんですよ ;^)

                「ニューラルネットを使ってルーティング」

                それならばなおさら誤解のないような表記ができるはずです。
                次の論文を
  • by user-key (12079) on 2003年02月17日 11時04分 (#260749)
    ヘタに研究者が研究するより、宅配のドライバーと共同研究を行った方が良い成果が出るように思われ。
    •  たしか宅配便の会社にも研究者が居たと思う。

       ベテランドライバーが経験と勘で組んだルートより、物流配送ルート作成システムが地図と道路状況のデータベースを元に組んだルートの方が早く終わったって実験結果があったし。
       一見、遠回りに見えるルートも実は最適化された結果というシステムで、最新版は道路状況で動的にルートが組めるんじゃなかったかな?

       そんなわけで物流システムの研究者。もしくは、その基礎を作った軍の補給システムの研究者が加わるのが良いかと思われます。
      --
      --- どちらなりとご自由に --- --
      親コメント
      • 蟻を研究して物流に応用したという話を聞いたことがあります。
        ウィルスに感染したときは、植物のように感染点の周りの細胞
        がアポトーシスしてウィルスを遮断するというのとかも応用
        できないでしょうか?
        親コメント
        • by reo (4042) on 2003年02月17日 12時00分 (#260800) 日記

          ACO [Ant Colony Optimization] [ulb.ac.be]ですね。そのほかにSwarm Intelligence(文献いっぱいのリンク集はこちらのNASAのページ [nasa.gov]どうぞ)なんてのもあります。

          --
          Hiroki (REO) Kashiwazaki
          親コメント
          • by WATT (7709) on 2003年02月17日 23時00分 (#261211) 日記
            最適解探索をするAnt Colonyを単純にトラフィック分散のためのルーティングに適応した場合、みんなフェロモンで強められた同じルートに行きたがり、まさに今回のような利己的なものになってしまいそうです。
            以前見た、ALifeや関数最適化関連の論文では、動的環境におけるAnt Colonyもあったので、そういったもので多少は対応はできそうな気もしますが…。もちろん、TSPの一類型といえる物流にはうまく適用できると思います。

            # って今回のネタは最短ルート探索じゃなく、トラフィック分散なんだよね
            親コメント
      • ところがどっこい。家を回るだけならシステムの方が最適かもしれま
        せんが、実際は「ハンコ」を貰わなければならないのです。
        昼間、家に誰も居なかったり、居たとしても「それは息子宛だから息
        子が帰ってきた頃にもう一度来てくれ」とか……。
        ですから、「本当の宅配」となると宅配テリトリーにおける経験ってバ
        カにならないですよ。

        時間指定されている荷物ばっかりじゃないし。
        届け先が店だと配達時間帯があるし……。

        # え、ハンコが必要になる宅配の話じゃないって?
        # ごめんなさい
        親コメント
        •  一般家庭向けの宅配便は、物流システムの中でもほんの一握りですから。(w;

           多くは物流システムとして会社や店舗や配送拠点の間を結んでいるので、必ず誰か受け取る人が居てサインしてくれる事が前提です。
           宅配便業者の場合は、これに不在と再配達の為の管理機能を組みこんで拡張してあげないと使えないかと。

           ・・・っと、解かってるだろうと思いつつ反論。
          --
          --- どちらなりとご自由に --- --
          親コメント
      • ベテランドライバーが経験と勘で組んだルートより、物流配送ルート作成システムが地図と道路状況のデータベースを元に組んだルートの方が早く終わったって実験結果があったし。

        ベテランドライバーの、引き裂かれるプライドとモチベーション低下を加味すると、かえって遅かったりして。

        # 根拠はないので AC

        •  配送先リストと地図を元に手作業で作っていたのが、コンピュータが配送順リストをプリントしたり、カーナビで案内してくれるようになるので、ドライバーとしては負担軽減になるかと。
           もともと負担軽減のためのシステムだったはずだし。
          --
          --- どちらなりとご自由に --- --
          親コメント
  • by L.Nizah (7804) on 2003年02月17日 14時05分 (#260883)
    どのような規模で実験したのかは分かりませんが、幾つか引っかかる点があります。

    ルータが転送するパケットには、当然ルーティング自体に使用されるパケットも含まれるわけで、一般にルーティングプロトコルが複雑なほどルーティングトラフィックは増加します。
    また、複雑なルーティングプロセスを実行するルータの負荷も高くなり、結果として局地的なスループットは低下します(…そのはず)
    ネットワーク全体を上手く使うことで、それを補うだけの性能が得られるとしても、次は規模の問題が発生します。

    ネットワーク全体の情報を扱うと言う事は、ネットワークが大規模な物になればその情報は爆発的に増加し、扱いきれなくなってしまうでしょう。
    で、更に(OSPFのエリアとかみたいに)スケーラビリティに対応出来るようにしたとしても、扱いが複雑になるという管理上の困難が、そして更に……

    いや、別にケチつけたいわけじゃなくて純粋に興味があるだけなんですけどね(^^;
    • by L.Nizah (7804) on 2003年02月17日 14時10分 (#260886)
      実験したネットワークはどんなトポロジーだったんだろう?
      極端な話、単純なツリー型じゃ全く役に立たないよなぁ。
      親コメント
      • by Anonymous Coward
        同じ疑問を感じてみたり。

        擬似網を構成してその中で検証したとしてもRoutingのポリシーをどうしたのかが疑問。
        通常企業LAN/WANなんかだと、トラフィックのポリシールーティングやらルータの負荷を低く押さえて効率的にRoutingするかを設計
  • 件の論文は、 (スコア:1, 参考になる)

    by Anonymous Coward on 2003年02月17日 10時33分 (#260729)
    これ [cornell.edu]ですね(How Bad is Selfish Routing)。
    Eva Tardosは、ネットワーキングにおけるゲーム理論の研究者だそうです。

    しかしまだ読んでないのでAC
  • by watanabe_aki (10227) on 2003年02月17日 11時46分 (#260792)
    最も効率の良い振り分けをすると、回線は上手に使えても振り分け側の負担が増えるだけじゃない?(マシンへの負荷、それを制御するプログラムの複雑化等)しわ寄せは確実にあるわけで・・・。

    機械の性能や情報輸送量の限界の上昇と共にネットの利用も多くなっているので、永遠のテーマだね。

  • GHOSTが生まれてるんですきっと。
    人形遣いとか。

    そのうち、お土産を期待するようになりますよ。
    --

    # I will work seriously this year!

  • 記事より:
    > Tardos氏らは、ルータがパケットを送信する方法の数学的な分析を実施し、伝送速度は理想的なシステムに比べて最大1.33倍向上することが判明した。

    原文読んだけど、「伝送速度」じゃなくて「伝送時間」。
    「理想的なシステムに比べ平均伝送時間が最大 1.33 倍増加することが判明した」
    つまり理想的な状態より悪化してるってことだよね。
    --
    # mishimaは本田透先生を熱烈に応援しています
  • by yashichi (10118) on 2003年02月17日 15時41分 (#260936)
    本題と外れて申し訳ないのですが、『障害時の収束』という用語の意味をお聞きしたいのですが・・・。
    障害時に特定パスに負荷が集中するというふうに単純に解釈していいのでしょうか。

    最近この分野を勉強中で専門的な用語の使い方がよくわからず四苦八苦しています。
    『収束』と聞くとどうしてもある値に漸近するイメージしか湧かないのですが、
    それがネットワークトポロジーにおいてどういう状況を指すのかなと・・・。

    • by mpls (8235) on 2003年02月17日 16時30分 (#260954) 日記
      あるノードが障害状態となったときに、そのノードを通る
      パスは使わないようにすると思います。そういうネットワーク
      の状態変化が起こると、ネットワーク全体として自律的に
      そのノードを通るパスを通らないようにしようとするわけですが、
      その計算がおわることを「収束」という意味で書いておりました。
      --
      --- show mpls ldp neighbor
      親コメント
    • by yashichi (10118) on 2003年02月17日 16時56分 (#260972)
      なるほど!
      完全に誤解していました+理解しました。
      これまではインターネットというものを比較的静的に捉えていたんですが、
      実際は非平衡定常(笑)な状態にあってダイナミックに変化しているんですね。
      これでいろんな話が繋がりました。どうもありがとうございました。
      親コメント
  • くだん (スコア:0, オフトピック)

    by Minap (9371) on 2003年02月17日 10時13分 (#260719) ホームページ 日記
    クダンの」って何だろう・・・「件の」の間違いじゃ?(w;

    [goo.ne.jp]
    --
    --- どちらなりとご自由に --- --
typodupeerror

にわかな奴ほど語りたがる -- あるハッカー

読み込み中...