ある2ソースネットワークにおけるブライスのパラドックス  [in Japanese] Braess's Paradox in a Two-source Network  [in Japanese]

Search this Article

Author(s)

Abstract

コンピュータネットワークにおいて,プレイヤーが自分の遅延を最小にしようと伝送経路を選択することを利己的ルーチングという.最近,進化ゲームを用いて利己的ルーチングが解析されている.シングルソース-シングルシンクネットワークでは,ネットワークの伝送遅延を小さくしようと新たに枝を追加した結果,伝送遅延が大きくなってしまう場合があり,ブライスのパラドックスとして知られている.本報告では,マルチソース-シングルシンクネットワークにおける利己的ルーチングを複数集団レプリケータダイナミクスを用いて定式化し,ある2ソースネットワークにおいて,安定な平衡点となるフローを求める.そして,その2ソースネットワークにおいて枝を追加することにより,ブライスのパラドックスと同様のパラドックスが生じることを示す.

Selfish routing is a selfish route selection of players in computer networks. Players are assumed to select paths so as to minimize their data transfer latencies. Recently, selfish routing is analyzed as an evolutionary game. Additional edges are expected to reduce the average latency of data transfers, but such edges may increase the average latency in some single-source single-sink networks. Such a situation is well known as Braess's paradox. In this paper, we formulate multipopulation replicator dynamics of selfish routing in multisource single-sink networks. Then, in a two-source network, we find flows which correspond to stable equilibrium points of the replicator dynamics. We extend Braess's paradox to multisource single-sink networks and show that such a paradox occurs in a network which is added an edge to the two-source network.

Journal

  • IEICE technical report

    IEICE technical report 110(89), 47-52, 2010-06-14

    The Institute of Electronics, Information and Communication Engineers

References:  5

Cited by:  2

Codes

  • NII Article ID (NAID)
    110007890759
  • NII NACSIS-CAT ID (NCID)
    AN10438446
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09135685
  • NDL Article ID
    10754429
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top