文献

J-GLOBAL ID：202002211590891145   整理番号：20A2094732

応答時間を最適化するためのスイッチ上のスケジューリングフロー【JST・京大機械翻訳】

Scheduling Flows on a Switch to Optimize Response Times

著者 (3件)： Jahanjou Hamidreza (Google, Mountain View, CA, USA) ,  Rajaraman Rajmohan (Northeastern University, Boston, MA, USA) ,  Stalfa David (Northeastern University, Boston, MA, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： SPAA ’20  ページ： 305-315  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： フローの応答時間に関連する計量を最適化する目的でスイッチ上のフローのスケジューリングを研究した。入力はスイッチ上のフロー要求のシーケンスであり,スイッチは各頂点(ポート)上の容量を持つ二部グラフにより表現され,フロー要求は関連する要求を持つエッジである。各ラウンドにおいて,エッジの部分集合は,任意の頂点に入射する予定されたエッジの全需要が頂点のほとんどの能力にあるという制約の下でスケジュールできる。このクラスのスケジューリング問題はデータセンタネットワークに応用され,広く研究されている。以前の研究は,完了時間に基づく計量の複雑さを本質的に解決する。しかし,平均または最大応答時間の目的は,より挑戦的である。知る限りでは,フロースケジューリングの文脈において,これらのメトリックスに対する事前近似アルゴリズムの結果は存在しない。応答時間ベースのメトリックを最適化するためのスイッチ上のフロースケジューリングのための最初の近似アルゴリズムを示した。NP-硬度が過去の仕事から直接追従する平均応答時間メトリックのために,スイッチのポート容量が1+cの因子によって増加できると仮定して,最大応答時間メトリックのための任意の正整数cに対して,スイッチのポート容量が1+cの因子によって増加できると仮定して,著者らは,容量を増強せずに4/3より良い近似因子を達成するのがNP困難であることを,著者らは最初に確立した。次に,各ポートの容量が2d_max-1で増加すると仮定して,最適最大応答時間を達成するオフラインアルゴリズムを提示し,そこではd_maxが任意の流れの最大需要である。両アルゴリズムは線形プログラミング緩和に基づいている。また,競合解析のレンズを用いたフロースケジューリングのオンラインバージョンを研究し,高速オンラインヒューリスティックの性能を評価する実験と共に予備的結果を示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *最適化 ,  線形計画法 ,  レンズ ,  *スケジューリング ,  近似法 ,  緩和現象 ,  ポート ,  応答時間 ,  NP困難
準シソーラス用語： 二部グラフ ,  近似アルゴリズム ,  オンライン ,  ホップ数 ,  オフライン , 【Automatic Indexing@JST】

著者キーワード (7件)： 流れ時間 ,  繰返し丸め ,  線形計画法 ,  オンラインアルゴリズム ,  応答時間 ,  スケジューリング ,  スイッチ

分類 (2件)： 計算機網  (JC03000K) ,  通信網  (ND07030A)

タイトルに関連する用語 (4件)： 応答時間 ,  最適化 ,  スケジューリング ,  フロー