文献

J-GLOBAL ID：201202206924144135   整理番号：12A1240811

経路選定品質ゲームを介したネットワークにおける輻輳+拡大近似

Approximating Congestion+Dilation in Networks via “Quality of Routing” Games

著者 (3件)： BUSCH Costas (Louisiana State Univ., LA) ,  KANNAN Rajgopal (Louisiana State Univ., LA) ,  VASILAKOS Athanasios V. (Univ. Western Macedonia, GRC)
資料名： IEEE Transactions on Computers  (IEEE Transactions on Computers)
巻： 61  号： 9  ページ： 1270-1283  発行年： 2012年09月 
JST資料番号： C0233A  ISSN： 0018-9340  CODEN： ICTOB4  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ネットワークの機能性にとって重要な経路選定アルゴリズムは,パケットがネットワーク上で送信される経路を付与する。経路選定における古典的最適化問題は,C(最大端部輻輳)+D(最大経路長/拡大)を最小化するが,C/Dの一方が小さな定数の場合でもNP完全問題である。効率的パケットスケジューリングアルゴリズムの存在に刺激され,プレーヤが同時に2つのパラメータを最適化する双判定基準ゲームを研究した。検証の結果,C+Dゲームは安定化しないインスタンスを有し,QoR(経路選定品質)ゲームは安定化してそれらの平衡がC+D最適化問題に良好な近似を与える。また,最大ゲームは安定化して最高で安定度1を持つが,無秩序の代償が大きい。QoRゲームのNash均衡が困難な最適化問題に対する多ログ近似を付与することを示した。

シソーラス用語： *経路選定 ,  *ゲーム理論 ,  輻輳制御 ,  *Nash均衡 ,  無秩序系 ,  NP完全問題 ,  最適化問題 ,  判定基準 ,  *近似法 ,  品質保証 ,  定理証明 ,  通信網 ,  *通信操作
準シソーラス用語： ネットワークルーティング

分類 (2件)： 計算機網  (JC03000K) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 経路選定 ,  ゲーム ,  輻輳 ,  拡大 ,  近似