図面 (/)

技術 ルーティングテーブル生成装置、ルーティングテーブル生成方法、及びプログラム

出願人 日本電信電話株式会社
発明者 高橋洋介鈴木晃人辻野雅之石橋圭介塩本公平
出願日 2015年10月29日 (5年8ヶ月経過) 出願番号 2015-212464
公開日 2017年5月18日 (4年1ヶ月経過) 公開番号 2017-085388
状態 特許登録済
技術分野 広域データ交換
主要キーワード マクロフロー 通過割合 送出割合 リンク率 内点法 数理計画問題 各転送装置 マッチングルール
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年5月18日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (12)

課題

任意の方法で得られた経路情報を設定可能な転送装置の範囲を拡張すること。

解決手段

ルーティングテーブル生成装置は、転送装置に関する発着ノード別のトラヒック量についてのルーティングテーブルエントリ別の割合の集合を、前記転送装置による転送先ごとのグループ分類する分類部と、前記割合が分類されたグループに対応する転送先が、当該割合に係る前記エントリの条件に合致した場合の転送先となるように前記各エントリを生成する生成部とを有し、前記分類部は、前記グループごとに、当該グループに分類された割合の総和と、当該グループに対応する転送先に対して前記発着ノード別のトラヒックに関して入力された、転送先別のトラヒック量の割合の目標値との差分が最小となるように、前記エントリ別のトラヒック量の割合の集合を分類する。

概要

背景

限られたネットワークリソースを用いてトラヒックを効率的に収容する技術として、到着トラヒックを予測し、予測結果に基づいてトラヒックの経路を制御するトラヒックエンジニアリング技術が研究されている。トラヒックエンジニアリングの例として、ネットワーク内の最大リンク利用率を最小化することを目的とした経路制御などが考えられる。最大リンク利用率とは、ネットワーク内において最も混雑している(最も利用率の高い)リンクの利用率をいう。また、リンクの利用率とは、リンクの帯域に対するトラヒック需要の割合をいう。

トラヒックエンジニアリングでは、トラヒック需要、ネットワークのトポロジ情報、及びリンク情報等から構成した数理最適化問題を用いて経路情報を算出する。トラヒックエンジニアリングのための代表的な数理最適化問題として、線形計画問題整数計画問題とが知られている。なお、トラヒック需要とは、将来におけるトラヒック量予測値をいう。

トラヒックエンジニアリングのための線形計画問題を数1(式(1.1)〜(1.6))に示す(特許文献2)。

ここで、ネットワークは、有効グラフG(V、E)で表現される。Vはノード集合、Eはリンクの集合を表す。また、ノードi∈Vからノードj∈Vまでのリンク容量はcij∈Eと表す。ノードpからノードqまでのトラヒック需要は、tpqと表す。

は、トラヒック需要tpqについて、リンク(i,j)の通過割合を示し、ルーティング変数と呼ばれる。通過割合とは、トラヒック需要tpqに対して、リンク(i,j)に分配されたトラヒック量の割合をいう。例えば、2つのリンクを有する転送装置において、トラヒック需要tpqについての一方のリンクの通過割合が0.3であれば、他方のリンクの通過割合は0.7である。rは、最大リンク利用率を示しており、数1ではrを最小化するようなルーティング変数の値を求めている。

式(1.1)は、最大リンク利用率を最小化する目的関数を示しており、式(1.2)〜式(1.6)は制約条件である。式(1.2)及び式(1.3)は、フロー保存則を示している。式(1.4)は、リンク(i,j)を通過するトラヒックの総和がリンク容量×最大リンク利用率を超えないことを示している。式(1.5)及び(1.6)は、ルーティング変数

と、最大リンク利用率rとの値域を示している。

この線形計画問題では、ネットワーク内の最大リンク利用率を最小化するような経路情報が解として求められる。経路情報は、各転送装置におけるトラヒックの複数の出力ポートへの送出割合として得られる。ここで得られた経路情報をネットワークに設定するためには、各転送装置においてトラヒックを任意の割合でマルチパス分割できる必要がある。

トラヒックをマルチパス分割するための技術として、IPルータにおけるECMP(Equal-Cost Multi-path)技術がある。ECMPは、コストが等しい出力ポートに対してトラヒックを等分割して送信する技術であり、任意の割合でマルチパス分割することはできない。

一方、OpenFlow1.3以降において、Group TableにおけるSelect機能を使うことで、任意の粒度でトラヒックをマルチパス分割することができる。しかし、Select機能は、OpenFlow1.3仕様の中で、必ず実装しなければならない必須機能とされていないため、OpenFlow1.3に準拠したスイッチであっても利用できないことがある。

次に、トラヒックエンジニアリングのための整数計画問題を数4(式(2.1)〜(2.6))に示す。

数4は、数1において、式(1.5)を式(2.5)に置き換えたものである。

この整数計画問題では、数1の場合と同様に、ネットワーク内の最大リンク利用率を最小化するような経路情報が解として求められる。しかしながら、式(2.5)により、解が整数値であることが制約条件になっているため、得られる経路情報は、各転送装置におけるトラヒックの単一の出力ポートとなる。ここで得られた経路情報をネットワークに設定するにあたっては、各転送装置においてトラヒックを任意の割合でマルチパス分割できる必要がない。このため、整数計画問題で得られた経路は線形計画問題で得られた経路よりも幅広いネットワークに設定することが可能である。

概要

任意の方法で得られた経路情報を設定可能な転送装置の範囲を拡張すること。ルーティングテーブル生成装置は、転送装置に関する発着ノード別のトラヒック量についてのルーティングテーブルエントリ別の割合の集合を、前記転送装置による転送先ごとのグループ分類する分類部と、前記割合が分類されたグループに対応する転送先が、当該割合に係る前記エントリの条件に合致した場合の転送先となるように前記各エントリを生成する生成部とを有し、前記分類部は、前記グループごとに、当該グループに分類された割合の総和と、当該グループに対応する転送先に対して前記発着ノード別のトラヒックに関して入力された、転送先別のトラヒック量の割合の目標値との差分が最小となるように、前記エントリ別のトラヒック量の割合の集合を分類する。

目的

トラヒックエンジニアリングの例として、ネットワーク内の最大リンク利用率を最小化することを目的とした

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

それぞれが異なる条件と、前記条件に合致したトラヒック転送先を示す情報とを含む複数のエントリが構成するルーティングテーブルを利用して転送対象のトラヒックの転送先を決定する転送装置に関する発着ノード別のトラヒック量についての前記エントリ別の割合の集合を、前記転送装置による転送先ごとのグループ分類する分類部と、前記割合が分類されたグループに対応する転送先が、当該割合に係る前記エントリの条件に合致した場合の転送先となるように前記各エントリを生成する生成部とを有し、前記分類部は、前記グループごとに、当該グループに分類された割合の総和と、当該グループに対応する転送先に対して前記発着ノード別のトラヒックに関して入力された、転送先別のトラヒック量の割合の目標値との差分が最小となるように、前記エントリ別のトラヒック量の割合の集合を分類する、ことを特徴とするルーティングテーブル生成装置

請求項2

前記分類部は、以下の最適化問題但し、ziは、i番目の転送先のグループに関する前記目標値と前記総和との差分、Mは、前記ルーティングテーブルのエントリの数、Nは、転送先の数、piは、i番目の転送先に関して算出された転送先別のトラヒック量の割合、aiは、i番目の転送先に対応するグループに分類された割合の総和、uijは、j番目ルーティングエントリがi番目の転送先に対応するグループに分類された場合に1、そうでない場合に0、を解くことで、前記エントリ別のトラヒック量の割合の集合を分類する特徴とする請求項1に記載のルーティングテーブル生成装置。

請求項3

それぞれが異なる条件と前記条件に合致したトラヒックの転送先を示す情報とを含む複数のエントリが構成するルーティングテーブルを利用して転送対象のトラヒックの転送先を決定する転送装置に関する発着ノード別のトラヒック量についての前記エントリ別の割合の集合を、前記転送装置による転送先ごとのグループに分類する分類手順と、前記割合が分類されたグループに対応する転送先が、当該割合に係る前記エントリの条件に合致した場合の転送先となるように前記各エントリを生成する生成手順とをコンピュータが実行し、前記分類手順は、前記グループごとに、当該グループに分類された割合の総和と、当該グループに対応する転送先に対して前記発着ノード別のトラヒックに関して入力された、転送先別のトラヒック量の割合の目標値との差分が最小となるように、前記エントリ別のトラヒック量の割合の集合を分類する、ことを特徴とするルーティングテーブル生成方法

請求項4

前記分類手順は、以下の最適化問題但し、ziは、i番目の転送先のグループに関する前記目標値と前記総和との差分、Mは、前記ルーティングテーブルのエントリの数、Nは、転送先の数、piは、i番目の転送先に関して算出された転送先別のトラヒック量の割合、aiは、i番目の転送先に対応するグループに分類された割合の総和、uijは、j番目のルーティングエントリがi番目の転送先に対応するグループに分類された場合に1、そうでない場合に0、を解くことで、前記エントリ別のトラヒック量の割合の集合を分類する特徴とする請求項3に記載のルーティングテーブル生成方法。

請求項5

請求項3又は4に記載のルーティングテーブル生成方法をコンピュータに実行させるためのプログラム

技術分野

背景技術

0002

限られたネットワークリソースを用いてトラヒックを効率的に収容する技術として、到着トラヒックを予測し、予測結果に基づいてトラヒックの経路を制御するトラヒックエンジニアリング技術が研究されている。トラヒックエンジニアリングの例として、ネットワーク内の最大リンク利用率を最小化することを目的とした経路制御などが考えられる。最大リンク利用率とは、ネットワーク内において最も混雑している(最も利用率の高い)リンクの利用率をいう。また、リンクの利用率とは、リンクの帯域に対するトラヒック需要の割合をいう。

0003

トラヒックエンジニアリングでは、トラヒック需要、ネットワークのトポロジ情報、及びリンク情報等から構成した数理最適化問題を用いて経路情報を算出する。トラヒックエンジニアリングのための代表的な数理最適化問題として、線形計画問題整数計画問題とが知られている。なお、トラヒック需要とは、将来におけるトラヒック量予測値をいう。

0004

トラヒックエンジニアリングのための線形計画問題を数1(式(1.1)〜(1.6))に示す(特許文献2)。

0005

ここで、ネットワークは、有効グラフG(V、E)で表現される。Vはノード集合、Eはリンクの集合を表す。また、ノードi∈Vからノードj∈Vまでのリンク容量はcij∈Eと表す。ノードpからノードqまでのトラヒック需要は、tpqと表す。

0006

は、トラヒック需要tpqについて、リンク(i,j)の通過割合を示し、ルーティング変数と呼ばれる。通過割合とは、トラヒック需要tpqに対して、リンク(i,j)に分配されたトラヒック量の割合をいう。例えば、2つのリンクを有する転送装置において、トラヒック需要tpqについての一方のリンクの通過割合が0.3であれば、他方のリンクの通過割合は0.7である。rは、最大リンク利用率を示しており、数1ではrを最小化するようなルーティング変数の値を求めている。

0007

式(1.1)は、最大リンク利用率を最小化する目的関数を示しており、式(1.2)〜式(1.6)は制約条件である。式(1.2)及び式(1.3)は、フロー保存則を示している。式(1.4)は、リンク(i,j)を通過するトラヒックの総和がリンク容量×最大リンク利用率を超えないことを示している。式(1.5)及び(1.6)は、ルーティング変数

0008

と、最大リンク利用率rとの値域を示している。

0009

この線形計画問題では、ネットワーク内の最大リンク利用率を最小化するような経路情報が解として求められる。経路情報は、各転送装置におけるトラヒックの複数の出力ポートへの送出割合として得られる。ここで得られた経路情報をネットワークに設定するためには、各転送装置においてトラヒックを任意の割合でマルチパス分割できる必要がある。

0010

トラヒックをマルチパス分割するための技術として、IPルータにおけるECMP(Equal-Cost Multi-path)技術がある。ECMPは、コストが等しい出力ポートに対してトラヒックを等分割して送信する技術であり、任意の割合でマルチパス分割することはできない。

0011

一方、OpenFlow1.3以降において、Group TableにおけるSelect機能を使うことで、任意の粒度でトラヒックをマルチパス分割することができる。しかし、Select機能は、OpenFlow1.3仕様の中で、必ず実装しなければならない必須機能とされていないため、OpenFlow1.3に準拠したスイッチであっても利用できないことがある。

0012

次に、トラヒックエンジニアリングのための整数計画問題を数4(式(2.1)〜(2.6))に示す。

0013

数4は、数1において、式(1.5)を式(2.5)に置き換えたものである。

0014

この整数計画問題では、数1の場合と同様に、ネットワーク内の最大リンク利用率を最小化するような経路情報が解として求められる。しかしながら、式(2.5)により、解が整数値であることが制約条件になっているため、得られる経路情報は、各転送装置におけるトラヒックの単一の出力ポートとなる。ここで得られた経路情報をネットワークに設定するにあたっては、各転送装置においてトラヒックを任意の割合でマルチパス分割できる必要がない。このため、整数計画問題で得られた経路は線形計画問題で得られた経路よりも幅広いネットワークに設定することが可能である。

先行技術

0015

特許第5747393号公報
特許第7542981号公報

発明が解決しようとする課題

0016

計算時間の観点で線形計画問題と整数計画問題とを比較すると、線形計画問題は、解法としてシンプレックス法内点法といった効率的なアルゴリズムが存在し、大規模な問題においても高速に解を導出することができる。一方、整数計画問題は、NP困難であることが知られており、解導出のための効率的なアルゴリズムが存在しない。このため、整数計画問題では、大規模な問題においては現実的な実行時間で解を導出することが困難となる。

0017

次に、「得られる最適経路の性能」の観点で線形計画問題と整数計画問題を比較すると、線形計画問題は、解として整数を含めた実数全てを許容するのに対して、整数計画問題は、解として整数のみを許容する。このように、線形計画問題は、整数計画問題より広い解空間から解を導出できるため、得られる解の最適性、すなわち最適経路の性能は高い。数1及び数2の例のように、ネットワーク内の最大リンク利用率を目的関数とした場合には、線形計画問題(数1)で得られた最適経路の方が、ネットワーク内の最大リンク利用率をより低減させた経路が得られる。

0018

このように、線形計画問題による最適経路計算は、「計算時間」及び「得られる経路の性能」の観点で優れているものの、得られた最適経路を設定できる転送装置が限られる、という課題が存在する。

0019

したがって、線形計画問題による最適経路計算等、任意の方法によって求められた経路情報を転送装置に設定可能な技術が求められる。

0020

本発明は、上記の点に鑑みてなされたものであって、任意の方法で得られた経路情報を設定可能な転送装置の範囲を拡張することを目的とする。

課題を解決するための手段

0021

そこで上記課題を解決するため、ルーティングテーブル生成装置は、それぞれが異なる条件と、前記条件に合致したトラヒックの転送先を示す情報とを含む複数のエントリが構成するルーティングテーブルを利用して転送対象のトラヒックの転送先を決定する転送装置に関する発着ノード別のトラヒック量についての前記エントリ別の割合の集合を、前記転送装置による転送先ごとのグループ分類する分類部と、前記割合が分類されたグループに対応する転送先が、当該割合に係る前記エントリの条件に合致した場合の転送先となるように前記各エントリを生成する生成部とを有し、前記分類部は、前記グループごとに、当該グループに分類された割合の総和と、当該グループに対応する転送先に対して前記発着ノード別のトラヒックに関して入力された、転送先別のトラヒック量の割合の目標値との差分が最小となるように、前記エントリ別のトラヒック量の割合の集合を分類する。

発明の効果

0022

任意の方法で得られた経路情報を設定可能な転送装置の範囲を拡張することができる。

図面の簡単な説明

0023

本発明の実施の形態におけるネットワーク構成例を示す図である。
本発明の実施の形態におけるルーティングテーブル生成装置のハードウェア構成例を示す図である。
本発明の実施の形態におけるルーティングテーブル生成装置の機能構成例を示す図である。
ルーティングテーブル生成装置が実行する処理手順の一例を説明するためのフローチャートである。
或る転送装置の構成例を示す図である。
経路計算装置によって算出された経路情報の一例を示す図である。
或る転送装置に関するトラヒック情報の一例を示す図である。
ポート・リンク情報の構成例を示す図である。
出力ポート別最適トラヒック量割合の集合の一例を示す図である。
エントリ別観測トラヒック量割合の集合の分類結果の一例を示す図である。
ルーティングテーブルの生成結果の一例を示す図である。

実施例

0024

以下、図面に基づいて本発明の実施の形態を説明する。図1は、本発明の実施の形態におけるネットワーク構成例を示す図である。図1には、端末50a〜50d、転送装置40a〜40c、制御装置20、経路計算装置30、及びルーティングテーブル生成装置10が示されている。なお、端末50a〜50dを区別しない場合、端末50という。また、転送装置40a〜40cを区別しない場合、転送装置40という。

0025

各端末50は、トラヒックを発生させる装置である。すなわち、各端末50は、トラヒックの発信元又は宛先に相当する。各端末50は、いずれかの転送装置40にネットワークを介して接続される。なお、トラヒックとは、ネットワーク上の通信の流れをいい、通信は、例えば、パケットの集合等によって構成される。

0026

各転送装置40は、トラヒックを転送中継)する装置である。転送装置40の一例として、SDN(Software Defined Network)/OpenFlowに対応したスイッチ(OpenFlowスイッチ)が挙げられる。各転送装置40は、いずれかの端末50又は他の転送装置40にリンクを介して接続される。各転送装置40は、ルーティングエントリの集合であるルーティングテーブルを有し、ルーティングテーブルに従って、転送対象のトラヒックの出力先の出力ポート(転送先)を決定する。ルーティングエントリは、トラヒックに対する条件であるマッチングルールと、マッチングルールに合致したトラヒックの出力ポート(転送先)を示す出力ポート情報とを含む。マッチングルールは、トラヒックの識別情報IPヘッダ情報やTCPヘッダ情報やMPLS(Multi-Protocol Label Switching)ヘッダ情報等を含み、ルーティングエントリごとに異なる。マッチングルールには、少なくとも発着ノードを識別できる情報(発着アドレス情報、MPLSヘッダ情報等)が含まれている必要がある。本実施の形態が有効に機能するためには、発着ノードの識別情報以外の識別子がマッチングルールに追加されており、発着ノード別フローより細かい粒度でのトラヒック制御が可能となっていることが望ましい。例えば、特許文献1で示されるような、発着ノード別マクロフローは、本実施に好適である。

0027

なお、本実施の形態において、「ノード」とは、いずれかの転送装置40をいい、端末50は含まれない。したがって、本実施の形態において着目されるトラヒックは、図1において、転送装置40間を接続するリンクL1〜L3におけるトラヒックをいう。

0028

各転送装置40は、また、ルーティングエントリごとのパケット数又はバイト数(以下、「トラヒック量」という。)を計測し、計測結果を制御装置20に送信する。

0029

制御装置20は、各転送装置40に対してルーティングテーブルを設定する装置である。制御装置20の一例として、SDN/OpenFlowに対応したコントローラ(OpenFlowコントローラ)が挙げられる。制御装置20は、また、定期的に転送装置40にアクセスし、各時刻におけるルーティングエントリのマッチングルールとエントリカウンタ値を取得できる。エントリカウンタ値は、当該ルーティングエントリにマッチして転送されたトラヒック量を示す。なお、制御装置20と各転送装置40との接続形態は、所定のものに限定されない。

0030

経路計算装置30は、ネットワーク構成情報及びトラヒック情報を収集し、発着ノード別トラヒックごと、かつ、転送装置40ごとに、最適経路を示す経路情報を算出する。経路情報は、数1に基づいて算出される。経路計算装置30によって算出される経路情報xijpqは、発信側のノードp(転送装置40)から宛先のノードq(転送装置40)に送信される発着ノード別トラヒックについて、ノードiがj番目出力リンク(i,j)にトラヒックを送信する割合を表す。以降、この経路情報xijpqを「出力リンク別最適トラヒック量割合」という。なお、上記したように、本実施の形態において「ノード」は、転送装置40のことをいう。したがって、発着ノード別トラヒックとは、転送装置40間別のトラヒックをいう。

0031

ルーティングテーブル生成装置10は、経路計算装置30によって算出された経路情報と、制御装置20から取得したトラヒック情報とに基づいて、各転送装置40のルーティングテーブルを生成する。

0032

図2は、本発明の実施の形態におけるルーティングテーブル生成装置のハードウェア構成例を示す図である。図2のルーティングテーブル生成装置10は、それぞれバスBで相互に接続されているドライブ装置100、補助記憶装置102、メモリ装置103、CPU104、及びインタフェース装置105等を有する。

0033

ルーティングテーブル生成装置10での処理を実現するプログラムは、CD−ROM等の記録媒体101によって提供される。プログラムを記憶した記録媒体101がドライブ装置100にセットされると、プログラムが記録媒体101からドライブ装置100を介して補助記憶装置102にインストールされる。但し、プログラムのインストールは必ずしも記録媒体101より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置102は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。

0034

メモリ装置103は、プログラムの起動指示があった場合に、補助記憶装置102からプログラムを読み出して格納する。CPU104は、メモリ装置103に格納されたプログラムに従ってルーティングテーブル生成装置10に係る機能を実行する。インタフェース装置105は、ネットワークに接続するためのインタフェースとして用いられる。

0035

なお、制御装置20や経路計算装置30も、図2と同様のハードウェア構成を有していてもよい。また、ルーティングテーブル装置10、制御装置20、経路計算装置30は、1以上の共通のコンピュータを用いて実現されてもよい。

0036

図3は、本発明の実施の形態におけるルーティングテーブル生成装置の機能構成例を示す図である。図3において、ルーティングテーブル生成装置10は、入力情報取得部11、分類部12、及び生成部13等を有する。これら各部は、ルーティングテーブル生成装置10にインストールされた1以上のプログラムが、CPU104に実行させる処理により実現される。

0037

入力情報取得部11は、ルーティングテーブルの生成に必要な情報を制御装置20及び経路計算装置30から取得する。制御装置20からは、転送装置40のルーティングテーブルと、転送装置40において観測されたトラヒック情報が取得される。経路計算装置30からは、最適経路として算出された経路情報が取得される。

0038

分類部12は、入力されたトラヒック情報及び経路情報に基づいて、転送装置40ごとに、当該転送装置40のルーティングテーブルを構成する各ルーティングエントリを、当該転送装置40の出力ポートごとのグループに分類する。分類の方法については後述される。

0039

生成部13は、分類部12による分類結果に基づいて、各転送装置40のルーティングテーブルを生成(更新)する。より詳しくは、生成部13は、既存のルーティングテーブルにおける各ルーティングエントリのマッチングルールに対応する出力ポート情報を更新する。

0040

以下、ルーティングテーブル生成装置10が実行する処理手順について説明する。図4は、ルーティングテーブル生成装置が実行する処理手順の一例を説明するためのフローチャートである。

0041

テップS101において、入力情報取得部11は、経路計算装置30から各転送装置40に関して算出された経路情報を取得し、制御装置20から各転送装置40のルーティングテーブル及びトラヒック情報を取得する。

0042

本実施の形態では、便宜上、或る1つの転送装置40(以下、「転送装置X」という。)に着目して説明する。転送装置Xは、図5に示されるような構成を有することとする。

0043

図5に示されるように、転送装置Xは、Port_a、Port_b、又はPort_cによって識別される3つの出力ポートを有する。各出力ポートには、リンク(Link_X、Link_Y、又はLink_Z)が接続されている。なお、図1において、各転送装置40が他の転送装置40と接続されるリンクは1つであるが、転送装置Xについては、便宜上、他の転送装置40と接続されるリンクが3つであるとする。

0044

転送装置Xは、また、ルーティングテーブルT1を有する。ルーティングテーブルT1は、マッチングルールとして、Rule_1〜Rule_11を含む。例えば、Rule_1又はRule_5にマッチ(合致)したトラヒックは、Port_aから出力され、Rule_2又はRule_4にマッチしたトラヒックは、Port_bから出力され、Rule_3にマッチしたトラヒックは、Port_cから出力されるように各ルーティングエントリは設定されている。なお、ルーティングテーブルT1において、Rule_6〜Rule_11に対する出力ポートは、便宜上、省略されている。

0045

このような転送装置Xについて、経路計算装置30は、数1に基づいて、図6に示されるような経路情報を算出したとする。

0046

図6は、経路計算装置によって算出された経路情報の一例を示す図である。図6に示されるように、或る一つの転送装置40に関する経路情報は、発着ノード別のトラヒックについての各出力リンクへのトラヒック量の割合である「発着ノード別最適トラヒック量割合」の集合である。

0047

一方、制御装置20からは、転送装置Xに関して、図5に示したルーティングテーブルT1と、図7に示されるような取得されるトラヒック情報が取得される。

0048

図7に示されるように、転送装置Xに関して制御装置20〜取得されるトラヒック情報は、転送装置Xにおいて観測された、発着ノード別のトラヒック量についての、マッチングルール別の割合である、エントリ別観測トラヒック量割合の集合である。

0049

続いて、入力情報取得部11は、取得された経路情報及びトラヒック情報を、ルーティングテーブルの生成処理都合の良い形式に加工する(ステップS102)。

0050

例えば、図6示される出力リンク別ト最適ラヒック量割合は、出力ポート別最適トラヒック量割合に変換される。当該変換は、転送装置Xにおいて保持されている「ポート・リンク情報」を利用して行われる。

0051

図8は、ポート・リンク情報の構成例を示す図である。図8に示されるように、ポート・リンク情報は、出力ポートと出力リンクとの対応関係を示す。基本的に、出力ポートと出力リンクとは1対1に対応する。図8では、図5の転送装置Xにおけるポート・リンク情報が示されている。なお、ポート・リンク情報は、例えば、制御装置20を介して転送装置Xから取得される。

0052

図6の各出力リンク別最適トラヒック量割合に対応する「出力リンク」が、図8のポート・リンク情報に基づいて、「出力ポート」に置換されることで、出力ポート別最適トラヒック量割合の集合が得られる。図9に、出力ポート別最適トラヒック量割合の集合の一例を示す。

0053

また、入力情報取得部11は、制御装置20から取得されたトラヒック情報についても加工を行う。図7では、便宜上、加工結果である「エントリ別観測トラヒック量割合」が示されているが、厳密には、制御装置20から取得されるトラヒック情報は、「エントリ別観測トラヒック量」である。入力情報取得部11は、各エントリ別観測トラヒック量について、発着ノード単位での割合を求めることで、「エントリ別観測トラヒック量割合」を得る。

0054

なお、転送装置40内のルーティングテーブルはルーティングエントリ毎のトラヒック量のカウンタ値を保存している。このカウンタ値を計測することで、「エントリ別観測トラヒック量」を得ることができる。

0055

なお、これから生成されるルーティングテーブルT1は、将来において使用されるものである。したがって、「エントリ別観測トラヒック量」がそのまま用いられるのではなく、「エントリ別観測トラヒック量」が、将来において予測されるトラヒック需要の予測値に変換された結果に基づいて、「エントリ別観測トラヒック量割合」が算出されてもよい。例えば、線形予測、ARIMA等によって予測値が算出されてもよい。本実施の形態では、トラヒック需要が一定であるとの仮定に基づいて、「エントリ別観測トラヒック量」がそのまま予測値として利用される例について説明する。

0056

続いて、分類部12は、発着ノードごとに、当該発着ノードに関するエントリ別観測トラヒック量割合の集合を、当該発着ノードに関して出力ポート別最適トラヒック量割合が割り当てられている出力ポート別のグループに分類する(ステップS103)。

0057

特定の発着ノード別トラヒックに対する、出力ポート別最適トラヒック量割合をP(p1,p2,p3,...,pN)とし、エントリ別観測トラヒック量割合をF(f1,f2,f3,...,fM)とした場合、分類部12は、Fを任意に組み合わせて出力ポート別近似トラヒック量割合A(a1,a2,a3,...,aN)を生成する。すなわち、エントリ別観測トラヒック量割合の集合が、出力ポート別のグループに分類される。Aについて式(3.1)で表す。

0058

ここで、uijは、Fの組み合わせを表す0−1変数であり、aiにfjが含まれる場合に1、それ以外の場合に0を表す。fjは、いずれか1つのaiにのみ含まれる。この条件について式(3.2)、(3.3)で表す。

0059

この際、分類部12は、出力ポート別近似トラヒック量割合Aと出力ポート別最適トラヒック量割合Pとの誤差(差分)が最も小さくなるように、出力ポート別近似トラヒック量割合Aを生成する。出力ポート別近似トラヒック量割合Aと出力ポート別最適トラヒック量割合Pとの誤差を式(3.4)で表す。

0060

式(3.1)から(3.4)により、以下の数理計画問題定式化できる。

0061

しかしながら、この数理計画問題は、目的関数が非線形関数であるため、効率的な解導出が困難である。そこで、誤差ベクトルZ(z1,...,zN)を導入し、数8を、下記のような0−1整数計画問題へと変換する。

0062

数9では、式(3.4)の非線形関数が、式(3.6)、(3.7)、及び(3.8)で表現されている。

0063

なお、数9における各パラメータの意味を改めて説明すると、以下の通りである。
ziは、i番目の出力ポートのグループに関する出力ポート別最適トラヒック量割合と出力ポート別近似トラヒック量割合との差分(誤差)である。
Mは、ルーティングテーブルT1のルーティングエントリの数である。
Nは、出力ポートの数である。
piは、i番目の出力ポートに関して算出された出力ポート別最適トラヒック量割合である。
aiは、i番目の出力ポートに対応するグループに分類されたエントリ別観測トラヒック量割合の総和である。

0064

分類部12は、数9の最適化問題解くことで、誤差ベクトルZを最小化するような、マッピング変数uijを得る。その結果、エントリ別観測トラヒック量割合の集合は、誤差ベクトルZが最小となるように、出力ポート別のグループに分類される。

0065

図10は、エントリ別観測トラヒック量割合の集合の分類結果の一例を示す図である。図10に示される「最適化問題」は、数9のことである。当該最適化問題が解かれることにより、uijの値が求まり、その結果、各マッチングルールは、出力ポート別のグループに分類される。図10では、マッチングルールとしてRule_1、Rule_2、又はRule_4を含む3つのルーティングエントリが、Port_aのグループに分類され、マッチングルールとしてRule_3又はRule_5を含む2つのルーティングエントリが、Port_bに分類された例が示されている。

0066

なお、図10では、特定の発着ノード別トラヒック(Node1−Node2)に関するuijの算出結果が示されているが、転送装置Xにおいて観測された各発着ノード別トラヒックについて、uijが算出され、発着ノード別トラヒックごとに、マッチングルールが、出力ポート別のグループに分類される。

0067

続いて、生成部13は、分類部12による分類結果に基づいて、転送装置XのルーティングテーブルT1を生成(更新)する(ステップS104)。

0068

図11は、ルーティングテーブルの生成結果の一例を示す図である。図11では、エントリ別観測トラヒック量割合と出力ポート別最適トラヒック量割合とがルーティングテーブル生成装置10に入力され、ルーティングテーブル生成装置10からルーティングテーブルT1が出力されることが示されている。生成されたルーティングテーブルT1は、制御装置20によって転送装置Xに設定される。その結果、トラヒックを効果的に分散させ、ネットワークの使用効率を向上可能な経路制御が転送装置Xによって実行されることになる。

0069

なお、上記の処理手順は、転送装置X以外の各転送装置40に関しても実行される。

0070

上述したように、本実施の形態によれば、トラヒックスプリット機能を有さない転送装置40においても、数1の線形計画問題で得られた経路を設定できるようになる。したがって、発着ノード間に複数のパスが存在する環境において、マルチパスを有効活用することで最適経路に近付けることができる。また、線形計画問題の2つの利点(「計算時間が短い」、「得られる最適経路の性能が高い」)を得ることができる。その結果、大規模なネットワークに対して現実的な時間で高性能な最適経路を様々な転送装置に設定することができる。

0071

なお、数9は、転送装置別、かつ、発着ノード別の問題である。各転送装置、発着ノード間で数9を並列に計算可能であるため、並列計算可能な計算機をルーティングテーブル生成装置10に用いることで、ネットワーク全体の最適経路解を高速に導出できる。

0072

また、本実施の形態では、経路計算装置30によって数1に基づいて算出される経路情報がルーティングテーブルの生成に際しての目標値とされる例について説明したが、ルーティングテーブル生成装置10に入力される経路情報は、斯かる経路情報に限定されない。例えば、最大リンク率以外のパラメータの最適化が目的関数とされてもよい。また、図9に示した出力ポート別最適トラヒック量割合の目標値が、人の任意によって設定されてもよい。また、どのような経路を得たいかに応じて、最適経路以外の経路に関する経路情報が目標値として入力されてもよい。

0073

また、上記では、ルーティングエントリにおいて転送先を示す情報として、出力ポート情報が含まれる例について説明したが、当該転送先を示す情報は、転送パス転送経路)を示す情報(以下、「転送パス情報」という。)であってもよい。すなわち、各ルーティングエントリは、マッチングルールと転送パス情報とを含む。転送装置40は、転送対象のトラヒックに合致するマッチングルールを含むルーティングエントリに基づいて転送パスを判定し、転送パスに対応する出力ポートから当該トラヒックを出力する。転送パスと出力ポートとの対応情報は、転送装置40に記憶されている。また、転送パスと出力ポートとの関係は、必ずしも1対1ではない。この場合、上記における「出力ポート」は、「転送パス」に置き換えられればよい。例えば、経路計算装置30によって算出される経路情報は、転送パス別に、トラヒック量割合を示す情報となる。したがって、上記における「出力ポート別最適トラヒック量割合」は、「転送パス別最適トラヒック量割合」に置き換えられればよい。

0074

上記より、本実施の形態において、出力ポート及び転送パスは、転送装置40による転送先の一例である。

0075

以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。

0076

10ルーティングテーブル生成装置
11入力情報取得部
12分類部
13 生成部
20制御装置
30経路計算装置
40a、40b、40c転送装置
50a、50b、50c、50d端末
100ドライブ装置
101記録媒体
102補助記憶装置
103メモリ装置
104 CPU
105インタフェース装置
B バス

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日本電信電話株式会社の「 検知装置および検知プログラム」が 公開されました。( 2021/04/30)

    【課題・解決手段】正規化部(11)が、複数のWebサーバへのアクセスログのURIを、複数のURI間で類似する表記を統一して正規化済URIに変更する。算出部(12)が、送信元が同一のアクセスログのうち、... 詳細

  • 株式会社NTTドコモの「 転送制御システム、網側装置及び位置管理装置」が 公開されました。( 2021/04/30)

    【課題】移動体通信網においてパケットの移動距離を短くした上で確実にパケットを移動通信端末に届かせる転送制御システム、網側装置及び位置管理装置を提供する。【解決手段】転送制御システム1は、移動体通信網N... 詳細

  • 上田日本無線株式会社の「 中継装置および通信システム」が 公開されました。( 2021/04/30)

    【課題】本発明は、パケットの中継を制限するために実行される処理を単純化することを目的とする。【解決手段】無線端末20は中継装置18−1に接続要求パケットを送信する(S1)。通信状態が予め定められた条件... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ