セルオートマトンによる相互結合網の輻輳の解析(システム性能評価)

概要

論文の詳細を見る
通信を司る相互結合網は,大規模並列計算機の成否の鍵となる重要な要素であり,これまでにトポロジ,フロー制御,ルーティングアルゴリズムなど,多岐にわたり改善が検討されてきた.一般に相互結合網は,通信負荷が高まるとパケット間の衝突により輻輳状態が生じ,レイテンシが上昇する性質を持つ.そしてさらに最大スループットを超える負荷を与えると系全体が輻輳状態となり,転送性能が著しく低下する現象が現れる.こうした著しい輻輳状態での性能低下は,相互結合網の方式によって致命的となるが,その元となる輻輳の発生・成長のメカニズムはこれまであまり深く検討されていなかった.本論文では,セルオートマトンを用いることで相互結合網をできる限り簡略なモデルで表現し,動的な挙動を観測することにより,輻輳の発生・成長の機構の本質的な解明を行う.セルオートマトンによるシミュレーションの結果,系の内部で輻輳状態になっておりほとんどパケットの移動がない部分と,比較的自由にパケットが移動できる部分とに分離される相転移が起きることを示す.また,相互結合網の転送負荷を,輻輳が現れないレベルから系全体に拡散するレベルまで変化させると,輻輳領域が形成される下限付近の負荷において,輻輳領域が間欠的に出現する現象が起きることを示す.さらに,系内の輻輳の状態を,パケットの移動度をもとに熱力学的エントロピーで表現することを提案する.系内に輻輳領域が発生しパケットの移動度が低下すると,系のエントロピーが低下する.系のエントロピー値の変化によって輻輳の発生・成長・消滅の様子を定量的に表現できる,また,レイテンシで計った相互結合綱の性能と,本論文によるエントロピー値は相反関係にある.さらに,相互結合網シミュレータを用いて検証し,セルオートマトンでの結果に準じた現象が実際の相互結合網上で起きることを示す.このことから,セルオートマトンにより得られた本論文の知見は,相互結合網に拡大適用することができると考えられる.
一般社団法人情報処理学会の論文
2006-05-15

セルオートマトンによる相互結合網の輻輳の解析(システム性能評価)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク