最適ルーチング政策とは何か？

1．はじめに
バケット交換ネットワークのルーチングは、1960年代から研究されている古い研究領域です。今までに、非常に多くの研究成果がある反面、最適ルーチングの研究となると、非常に簡単な問題でも分かっていないのが現状です。
　最適ルーチングでは、静的（stationary）ルーチングの最適化が多く研究されています。簡単に言いますと、ある目的関数（例えば、スループットや遅延時間）を最大／最小にするように、各経路へ送信するバケットの割合を求める最適化問題です。例えば、ネットワーク内の待ち行列をすべて独立な待ち行列モデルとして扱い、そこから導き出される平均遅延時間を最小にする方法が広く使われています。静的ルーチングは、入力トラヒックが時間的に緩やかに変化する場合のみに有効です。
　一方、動的（dynamic）ルーチングは、ある政策に基づいてルーチングを行います。ルーチング政策の代表として、待ち時間が最も少ない経路を選択する政策（以後、SS政策と略す）があります。最適なルーチングの研究成果は静的ルーチングの場合に比べて少なく、しかも、多くの場合、図1に示すような簡単なモデルに対して研究されてきました。図1は、ある目的関数を最小にするように、すべての到着バケットをいずれかの待ち行列に割り当てるルーチング問題を表しています。今までに、ポアソン到着過程、指数サービス時間の場合、SS政策が平均遅延時間を最小にすることが証明されています。しかしながら、サービス時間が一般分布になると、必ずしもSS政策が最適でないことが証明されています。つまり、最も簡単なモデルでも、否定的な結論しか分かっていないのが現状です。

2．コンピュータによる数値計算
通信トラヒック制御の問題設定では、一般に、入力トラヒックはある確率過程に基づいて到着し、ある確率分布に基づいてサービスを受けるようにモデル化されます。このモデル化は、問題を単純にし、扱いやすくする効果がある反面、重要なものをモデルから取り除いているように思います。例えば、バケット長は、動的ルーチングに影響を与える重要な要因の一つと考えられますが、確率的な取り扱いをすると、各バケットの長の違いが最適政策に反映されにくくなります。そこで、決定論的入力トラヒックに対する最適化問題を設定することにしました。この問題から最適なルーチング政策を取り出すために、始めに、最適化アルゴリズムを使って数値解を求め、次に、得られた複数の数値解から共通する特徴を抽出するという研究プロセスをとっています。しかしながら、入力トラヒックを決定論的に扱うことは、変数の数が非常に大きな組合せ最適化問題を解くことになります。（例えば、バケット数をN、パス数をMとしますと、変数の数は、MのN乗になります）。また、入力トラヒックを決定論的に扱う場合、目的関数が手続き（つまり、プログラム）表現になることが多いため、こき手続きの実行にも時間がかかります。さらに、モデルの複雑さも計算時間に大きく影響します。今までの経験から、トラヒックの合流や分流があると、目的関数の形状が複雑になるため、広域最適解に収束しづらいことが分かりました。このため、変数の数とモデルを単純にしないと、現在の並列コンピュータでも1ヵ月や1年は簡単に費やす計算量になります。しかしながら、決定論的アプローチは、確率的アプローチでは捉えられない特徴や性能を引き出すのではないかと考えています。図2は、これまでに計算した平均遅延時間を最小にする最適ルーチングの性能です。図2は、トラヒック負荷が大きいとき、SS政策よりも優れたルーチング政策が存在することを示唆しています。

3．図2の意味
（1）個人対社会
ルーチングの問題に限らず、さまざまな待ち行列に関わる最適化問題を考える場合、よく問題になるのが、個人（individual）の最適化は社会（social）の最適化と等しいか？　ということです。なぜならば、個人の最適化政策は、比較的簡単に見つけられるのに対して、多くの最適化問題は、社会最適化を目的関数にするためです。この問題は、経営科学やオペレーションズ・リサーチの分野で古くから研究されています。今までの研究では、個人最適化政策は、後から到着するバケット（または、ジョブ、客など）に対する影響を考慮して（経路などを）決定することがないため、到着するバケットの数が多くなるほど、二つの政策の差が大きくなることが分かっています。SS政策が個人最適化政策を表していることを考えると、図2の結果は、まさにこれと同じ結果を表しています。
（2）最短パスルーチングアルゴリズムの課題
現在インタネットでは、SS政策に基づく最短パスルーチングアルゴリズムが使われています。ここで、次のような仮定をします。ネットワーク内のすべてのノード（交換機、ルータ）は、“いつでも”、“すぐに”ネットワーク内のすべての待ち行列の現在の待ち時間に関する情報を得ることができるとします。この結果、最短パスルーチングアルゴリズムは理想的なアルゴリズムのように思えます。なぜならば、よく知られた二つの課題であるルーチング・ループ（バケットが同じ経路を循環する現象）とルーチング振動（トラヒック負荷が振動する現象）がほとんど起きないからです。しかし、図2の結果は、上記のような現実的に不可能な仮定が成り立つとしても、トラヒック負荷が高いときは、最短パスルーチングアルゴリズムの性能は最適との間に差があることを表しています。

4．今後の予定
　最適ルーチング政策は、いわば、“万能の神”による制御と考えられます。なぜならば、最適化問題の中に情報収集や計算能力等に関する制約条件が一切ないからです。また、最適ルーチング政策による制御は、集中的です。このため、一般に、最適ルーチング政策をそのまま実際のアルゴリズムとして使うことはできません。最適ルーチング政策を、有限なリソース（CPU能力、伝送速度など）の制約内で動作する分散アルゴリズムとして実現することが、この研究の最終目標です。