| 講演名 | 2015-11-20 不可分フロー平滑化問題に対するタイセットを用いた分散アルゴリズムの考察 山田 正史(創価大), 石垣 原野(創価大), 篠宮 紀彦(創価大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年の大規模なデータセンターなどの存在により，特定のリンクへの負荷集中を解消するトラフィックエンジニアリングを実現する技術が求められている．本稿では通信ネットワークをグラフへモデル化し，通信ネットワークのトラフィックエンジニアリングを固定の送信先と送信元のペアに対する不可分フロー平滑化問題として定式化する．そして，サイクル構造をなす辺集合であるタイセットを用いた平滑化手法を応用し，不可分フロー平滑化問題の解決を目指す．提案手法は，サイクル構造内の負荷率が最小になるような経路の組み合わせを求める．この操作をサイクル構造ごとに繰り返すことで，ネットワーク全体の平滑化を実現する．この手法はシミュレーションの結果，グラフの頂点数が多いグラフほど効果的な平滑化が可能であることがわかった．また，グラフの頂点数と平滑化完了までにかかるラウンド数や時間との関係性の評価も行った． |
| 抄録(英) | The demand for traffic engineering to alleviate load concentrations on links has increased for large-scale networks such as data center networks. In this paper, a communication network is modeled as a graph, and a balancing problem of an unsplittable flow which has a fixed pair of source and destination is formulated in the graph. An existing method using a set of edges that form a cycle structure called a tie-set is applied to the unsplittable flow balancing problem. The proposed method is carried out by obtaining a combination of routes that minimizes the load factor of a cycle structure. Balancing of a whole network is achieved by repeating this process for each cycle structure. Our simulation result shows that this approach is more effective for larger graphs in terms of the balancing. The execution time for which our method completes the balancing is also evaluated. |
| キーワード(和) | 不可分フロー / ネットワークフロー問題 / タイセット / グラフ理論 |
| キーワード(英) | unsplittable flow / network flow problem / tie-set / graph theory |
| 資料番号 | CAS2015-46,MSS2015-20 |
| 発行日 | 2015-11-13 (CAS, MSS) |
| 研究会情報 | |
| 研究会 | MSS / CAS / IPSJ-AL |
|---|---|
| 開催期間 | 2015/11/20(から2日開催) |
| 開催地（和） | 指宿市民会館 大会議室 |
| 開催地（英） | Ibusuki CityHall |
| テーマ（和） | グラフ、ペトリネット、ニューラルネット及び一般 |
| テーマ（英） | |
| 委員長氏名（和） | 山根 智(金沢大) / 田中 聡(村田製作所) |
| 委員長氏名（英） | Satoshi Yamane(Kanazawa Univ.) / Satoshi Tanaka(Murata) |
| 副委員長氏名（和） | 名嘉村 盛和(琉球大) / 高橋 俊彦(新潟大) |
| 副委員長氏名（英） | Morikazu Nakamura(Univ. of Ryukyus) / Toshihiko Takahashi(Niigata Univ.) |
| 幹事氏名（和） | 中田 充(山口大) / 豊嶋 伊知郎(東芝) / 山脇 大造(日立) / 越田 俊介(東北大) |
| 幹事氏名（英） | Mitsuru Nakata(Yamaguchi Univ.) / Ichiro Toyoshima(Toshiba) / Taizou Yamawaki(Hitachi) / Shunsuke Koshita(Tohoku Univ.) |
| 幹事補佐氏名（和） | 金城 秀樹(沖縄大) / 橘 俊宏(湘南工科大) / 中村 洋平(日立) |
| 幹事補佐氏名（英） | Hideki Kinjo(Okinawa Univ.) / Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Circuits and Systems / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 不可分フロー平滑化問題に対するタイセットを用いた分散アルゴリズムの考察 |
| サブタイトル（和） | |
| タイトル（英） | Characteristics of a distributed algorithm for balancing unsplittable flow with tie-sets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 不可分フロー / unsplittable flow |
| キーワード(2)（和/英） | ネットワークフロー問題 / network flow problem |
| キーワード(3)（和/英） | タイセット / tie-set |
| キーワード(4)（和/英） | グラフ理論 / graph theory |
| 第 1 著者 氏名（和/英） | 山田 正史 / Masashi Yamada |
| 第 1 著者 所属（和/英） | 創価大学(略称：創価大) Soka University(略称：Soka Univ.) |
| 第 2 著者 氏名（和/英） | 石垣 原野 / Genya Ishigaki |
| 第 2 著者 所属（和/英） | 創価大学(略称：創価大) Soka University(略称：Soka Univ.) |
| 第 3 著者 氏名（和/英） | 篠宮 紀彦 / Norihiko Shinomiya |
| 第 3 著者 所属（和/英） | 創価大学(略称：創価大) Soka University(略称：Soka Univ.) |
| 発表年月日 | 2015-11-20 |
| 資料番号 | CAS2015-46,MSS2015-20 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | CAS-315,MSS-316 |
| ページ範囲 | pp.15-20(CAS), pp.15-20(MSS), |
| ページ数 | 6 |
| 発行日 | 2015-11-13 (CAS, MSS) |