講演抄録/キーワード |
講演名 |
2015-11-20 11:00
不可分フロー平滑化問題に対するタイセットを用いた分散アルゴリズムの考察 ○山田正史・石垣原野・篠宮紀彦(創価大) CAS2015-46 MSS2015-20 |
抄録 |
(和) |
近年の大規模なデータセンターなどの存在により,特定のリンクへの負荷集中を解消するトラフィックエンジニアリングを実現する技術が求められている.本稿では通信ネットワークをグラフへモデル化し,通信ネットワークのトラフィックエンジニアリングを固定の送信先と送信元のペアに対する不可分フロー平滑化問題として定式化する.そして,サイクル構造をなす辺集合であるタイセットを用いた平滑化手法を応用し,不可分フロー平滑化問題の解決を目指す.提案手法は,サイクル構造内の負荷率が最小になるような経路の組み合わせを求める.この操作をサイクル構造ごとに繰り返すことで,ネットワーク全体の平滑化を実現する.この手法はシミュレーションの結果,グラフの頂点数が多いグラフほど効果的な平滑化が可能であることがわかった.また,グラフの頂点数と平滑化完了までにかかるラウンド数や時間との関係性の評価も行った. |
(英) |
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 / / / / |
文献情報 |
信学技報, vol. 115, no. 315, CAS2015-46, pp. 15-20, 2015年11月. |
資料番号 |
CAS2015-46 |
発行日 |
2015-11-13 (CAS, MSS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2015-46 MSS2015-20 |
研究会情報 |
研究会 |
MSS CAS IPSJ-AL |
開催期間 |
2015-11-20 - 2015-11-21 |
開催地(和) |
指宿市民会館 大会議室 |
開催地(英) |
Ibusuki CityHall |
テーマ(和) |
グラフ、ペトリネット、ニューラルネット及び一般 |
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
CAS |
会議コード |
2015-11-MSS-CAS-AL |
本文の言語 |
日本語 |
タイトル(和) |
不可分フロー平滑化問題に対するタイセットを用いた分散アルゴリズムの考察 |
サブタイトル(和) |
|
タイトル(英) |
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 |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
山田 正史 / Masashi Yamada / ヤマダ マサシ |
第1著者 所属(和/英) |
創価大学 (略称: 創価大)
Soka University (略称: Soka Univ.) |
第2著者 氏名(和/英/ヨミ) |
石垣 原野 / Genya Ishigaki / イシガキ ゲンヤ |
第2著者 所属(和/英) |
創価大学 (略称: 創価大)
Soka University (略称: Soka Univ.) |
第3著者 氏名(和/英/ヨミ) |
篠宮 紀彦 / Norihiko Shinomiya / シノミヤ ノリヒコ |
第3著者 所属(和/英) |
創価大学 (略称: 創価大)
Soka University (略称: Soka Univ.) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2015-11-20 11:00:00 |
発表時間 |
25分 |
申込先研究会 |
CAS |
資料番号 |
CAS2015-46, MSS2015-20 |
巻番号(vol) |
vol.115 |
号番号(no) |
no.315(CAS), no.316(MSS) |
ページ範囲 |
pp.15-20 |
ページ数 |
6 |
発行日 |
2015-11-13 (CAS, MSS) |