最適なネットワーク設計をめざして
1．はじめに
通信ネットワーク（以下ネットワーク）は、どのように設計・構築したらよいのでしょうか？
近年、インターネットが急速に普及してきました。電子メールやWWWなどのデータトラヒックは、ここ数年のうちに電話トラヒックを追い抜く勢いで急増しています。ネット配信サービスなどのビジネス展開や、高速転送技術などの研究開発も急速に進み、ネットワークをとりまく環境は、ますます複雑化しつつあります。
このような状況に対応するため、通信事業者や企業などでは、ネットワークの度重なる増強・更新を強いられています。ここで重要な意味を持つのが、ネットワークの最適設計です。ネットワーク構築のための一般的手順を図1に示します。図に示すように、ネットワーク設計には、初期設計と再設計の2種類が考えられますが、コスト制約内でできる限り予測される変化に強い初期設計および予測外の変化に対してはできる限り無駄を抑えた再設計を行うことが重要です。
LANのようなユーザ側が構築するネットワークでは、スペシャリストの経験と勘によって初期設計を行い、実運用中に問題点が表面化してくると、そのボトルネックを解消すべくさらに経験と勘によって再設計するという試行錯誤的アプローチがとられているのが現状だと思います。小規模なネットワークではそれでも何とかなるかも知れませんが、ネットワークが大規模化／複雑化してくると、経験と勘にたよる設計では、ネットワーク性能の予測できない劣化や、無駄な設備投資を繰り返すことになりかねません。
このような背景のもと、私達は、“ネットワークの最適設計”という古くて新しい研究課題に取り組むことにしました。
2．ネットワーク設計の考え方
私達は、ネットワーク設計を最適資源配分問題として捉えて、ネットワーク設備容量およびトラヒック配分の最適化を行うことを考えました。この最適化によって、ネットワークの潜在性能を引き出し、かつ無駄な設備投資を抑えるネットワーク設計ができると考えられます。
以下、ネットワークモデル、制御変数と制約条件、評価関数、そして最適化方法の順に説明していきます。
まず、ネットワークモデルです。本研究では、インターネットに代表されるコネクションレス型パケット通信網を想定しました。ネットワークは、ノードとリンクから構成されるものとします。ノードは、到着パケットに対してまずルーチング処理を行い、次に出力リンク別のフォワーディング処理を行います（図2）。リンクはある帯域を持ち、リンク長に比例した伝送遅延を持つものとします。
次に制御変数と制約条件です。ノードサービス速度配分率、リンク帯域配分率およびトラヒック配分率の3種類を制御変数として定義しました。ノードサービス速度配分率とは、ネットワーク全体の総ノードサービス速度が一定という制約条件のもとで全ノードにサービス速度を配分する割合です。リンク帯域配分率は、ネットワーク全体の総リンク帯域が一定という制約条件のもとで全リンクに帯域を配分する割合です。最後に、トラヒック配分率は、ある対地間に生起するパケットトラヒックをとりうる経路に配分する割合のことです。
次に評価関数です。ネットワーク性能を評価するための指標は様々なものが考えられますが、本研究では比較的一般的な、通信品質とネットワーク設備使用率に着目して、次のような評価関数を定義しました。
U = w1D + w2Ln + w3Ll
ここで、Dはパケット転送時間の平均値、Ln はノード使用率の最大値、Llはリンク使用率の最大値、そしてw1、w2およびw3は重み係数です。
最後に最適化方法です。ネットワークが大規模化／複雑化すればするほど、制御変数の数が増大し、さらに変数どうしが複雑に相互作用するため、最適設計が困難になります。私達は、ATRで開発された高次元アルゴリズム[1]によって本問題を解くことにしました。すなわち、評価関数を最小化する各制御変数を高次元アルゴリズムによって数値計算します。高次元アルゴリズムの詳細はここでは省きますが、多変数問題の最適化に特に有効である、局所的な安定解にひっかかりにくいなどの特徴を持つ最適化計算方法です。
3．ネットワーク設計の一例
25ノードの格子状ネットワークモデルを仮定しました（図3）。このモデルは、16個のエッジノード（以下EN）、9個のバックボーンノード（以下BN）およびそれらを格子状に結ぶ80本の有向リンクから構成されています。本ネットワーク設計は、制御変数総数＝16,953の多変数最適化問題になります。
このネットワークにおいて、パケットトラヒックが全ノードからポアソン生起するものとします。便宜的にこのトラヒックを、グループ1：EN間トラヒック、グループ2：EN〜BN間トラヒックおよびグループ3：BN間トラヒックの3つのグループに分類します。そしてグループ別のパケット生起率の総和の比率によって、トラヒック需要分布を設定します。ここでは、以下に示す2種類のトラヒック需要分布パターンを用います。
EN負荷型パターン Λ1:Λ2:Λ3=4:2:1BN負荷型パターン Λ1:Λ2:Λ3=1:2:4Λn(n=1,2,3)は、グループnのパケット生起率の総和であり、Λ1+Λ2+Λ3は一定とします。
この2種類のトラヒック需要分布パターン（EN負荷型およびBN負荷型）のもとで、本ネットワークモデルの最適設計を行ってみました。
その設計結果の一部として、ノードサービス速度の配分率を図4および図5に示します。横軸はノード番号、縦軸はノードサービス速度配分率です。図4では、ENにノードサービス速度がより多く配分され、逆に図5では、BNにより多くのノードサービス速度が配分されていることがわかります。つまり、”トラヒック需要が集中する部分により多くのノードサービス速度が配分される”という、我々の直感とよく一致する設計値（資源配分）を得ることができました。リンク帯域配分率およびトラヒック配分率についても同様の結果を得ました。これらの結果は、トラヒック需要に対して強いネットワーク設計ができるよい見通しを与えています。
4．今後の課題
以上、私達が提案するネットワークの最適設計法の一端を紹介しました。この研究は、まだ初期段階にあります。今後の課題としては、まず他のネットワーク設計法との比較評価があげられます。さらに、電子メールやWWWトラヒックを想定したネットワーク設計、トラヒックと各制御変数との因果関係の評価およびトポロジーまで含めたネットワーク設計法への拡張などを行いたいと考えています。最終的には、次世代通信網のためのスタンダードなネットワーク設計法の確立をめざしています。
Copyright(c)2002（株）国際電気通信基礎技術研究所
