Advanced Network Architecture Research Group 高速フロー検索アルゴリズム評価のためのアドレス生成手法川辺亮大阪大学大学院基礎工学研究科情報数理系専攻博士前期課程 E-mail: [email protected] 2001/6/7 1 発表の内容 Advanced Network Architecture Research Group 研究の背景研究の目的宛先アドレスのモデル化提案するパケット生成手法評価結果まとめと今後の課題 2001/6/7 2 研究の背景 Advanced Network Architecture Research Group 高速かつ広帯域なネットワークの要求回線容量の増加とルータの性能向上ルータのアドレス検索処理宛先アドレスから次の行き先アドレスの決定フロー識別ルータ性能のボトルネックさまざまなアルゴリズムの提案があるが、実際のトラヒックに基づく性能評価がされていない 2001/6/7 3 研究の目的 Advanced Network Architecture Research Group 実際のトラヒックを考慮した高速アドレス検索アルゴリズムの性能評価手法の提案構築したトラヒックモデルを利用し、トレースデータからトラヒックを予測宛先アドレスフロー特性トラヒックモデルを利用することにより、アドレス検索アルゴリズムの実用時の性能を正しく評価 2001/6/7 4 モデル化対象トラヒック Advanced Network Architecture Research Group モデル化対象 Osaka Univ. Campus Network Internet Router Host 2001/6/7 5 宛先アドレスのモデル化 Advanced Network Architecture Research Group パケット宛先アドレス生成アルゴリズム[1] を使うことで、到着パケットの宛先アドレスをモデル化 ISGFに時間推進不変性を仮定 LRUスタックモデルを利用することにより宛先アドレスを生成 [1] 会田雅樹, 安部哲哉, “パケット宛先アドレス生成アルゴリズム,” IEICE Tech. Rep. (IN99-91), pp. 19-24, July 2000 2001/6/7 6 # of Distinct Address f(T) パケットが持つ宛先アドレスの特性 Advanced Network Architecture Research Group 1e+06 trace data 100000 f (T ) = T 0 . 64 10000 1000 100 10 1 1 10 100 1000 10000100000 1e+06 1e+07 # of Packets T 2001/6/7 7 これまでに提案したアドレス生成手順トレースデータ LRU スタック A B B C 発生 B C C B C A C A Advanced Network Architecture Research Group トレースデータのアドレスを参照回数の多い順にソートトレースデータをスタックのトップから順にLRUスタックに格納参照される確率 a に基づきアドレ i スを順次生成 a i = { f ( g ( i - 1) + 1) - ( i - 1)} - { f ( g ( i ) + 1) - i} 2001/6/7 8 考慮すべき点 Advanced Network Architecture Research Group フロー生成フロー識別を行うルータでは、フロー特性についても考慮する必要フローごとのパケット数同一フロー内のパケットの到着間隔ある時刻におけるアクティブなフロー数 2001/6/7 9 # of Distinct Address f(T) フローが持つ宛先アドレスの特性 Advanced Network Architecture Research Group trace data 0.77 f(T)=T 1e+05 10000 100 10 1 1 10 100 10000 1e+05 1e+07 # of Flows T 2001/6/7 10 Probability Distribution フローごとのパケット数分布 Advanced Network Architecture Research Group 1 0.8 0.6 0.4 0.2 01 2001/6/7 Actual LogNormal Pareto 10 100 1000 Packets/Flow 10000 11 Probability Distribution フローごとのパケット数分布（すその部分） Advanced Network Architecture Research Group 1 0.98 0.96 0.94 0.92 0.91 2001/6/7 Actual LogNormal Pareto 10 100 1000 Packets/Flow 10000 12 提案するパケット生成手順フロー：ポアソン到着 LRU スタック Advanced Network Architecture Research Group 宛先アドレスフロー生成 A B C パケット数：分布に従い決定パケット：ポアソン到着 X 時刻 t 2001/6/7 13 シミュレーションモデル Advanced Network Architecture Research Group アドレス検索アルゴリズム[2]を評価入力キューがあふれない最小の平均到着間隔を最大処理能力とするパラメータ設定フローの平均到着間隔 I_F 同一フロー内の平均パケット到着間隔 I_P(F) フローごとのパケット数は対数正規分布＋パレート分布 [2] M. Uga, K. Shiomoto, “A fast and compact longest prefix look-up method using pointer cache for very long network address,” in Proceedings of IEEE ICCCN ’99, pp. 1240-1247, Apr. 1999 2001/6/7 14 Advanced Network Architecture Research Group シミュレーション結果最大スループット誤差実トラヒック 37.0 mpps ーーランダム 58.8 mpps +64% 提案手法1 35.7 mpps -3% 提案手法2 34.4 mpps -7% 従来広く行われているランダムな宛先アドレスを与える手法と比べ、提案手法1、提案手法2 では大幅な改善が見られる 2001/6/7 15 Advanced Network Architecture Research Group Input Queue Length (packet) 入力キュー長の変動 5000 4500 4000 3500 3000 Actual Model 1 Model 2 急激に変動急激な変動 2500 2000 1500 1000 500 0 0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06 Seq. # of Input Packets 2001/6/7 16 Probability Distribution フローごとのパケット数比較 Advanced Network Architecture Research Group 1 0.8 0.6 0.4 0.2 01 2001/6/7 Actual Model 1 Model 2 10 100 1000 Packets/Flow 10000 17 まとめと今後の課題 Advanced Network Architecture Research Group フロー特性を考慮したトラヒックの生成手法の提案宛先アドレス、フロー特性アドレス検索アルゴリズムの性能を比較的正しく評価フロー識別アルゴリズムへの応用と宛先アドレスの決定手法の改良が今後の課題 2001/6/7 18