(57)【要約】【課題】  パケット転送処理負荷を分散させることと、各リンクの誤り率を低減させることの両立が課題である。【解決手段】  パケットのパスルートについてのスワップ情報を演算するスワップ演算部と、スワップ演算部の演算結果に基づいて第1ラベルを調整の設定をするラベル処理部とを有する演算部を、制御装置に設ける。【選択図】  図１
2010246063.tif 000002
【特許請求の範囲】
【請求項１】
第１ラベルを付与されたパケットの送受信を行う複数のノードと接続され、前記ノードへの制御信号の送受信を行う通信処理部と、
前記通信処理部と接続される演算部とを有する制御装置であって、
前記演算部は、
前記パケットのパスルートについてのスワップ情報を演算するスワップ演算部と、
前記スワップ演算部の演算結果に基づいて、前記第1ラベルを調整の設定をするラベル処理部とを有し、
前記通信処理部は、前記ラベル処理部の設定に基づいて前記制御信号を前記ノードへ送受信することを特徴とする制御装置。
【請求項２】
前記第1ラベルと前記パスルートとに関する情報を格納するデータベース部をさらに有することを特徴とする請求項１に記載の制御装置。
【請求項３】
前記第1ラベルと前記パスルートとに関する情報を格納するデータベース部をさらに有し、
前記ラベル演算部は、前記スワップ演算部の演算結果に基づいて、前記データベース部から前記情報を読み出し、前記第1ラベル、及び前記スワップ情報に対応する第２ラベルを前記ノードに設定することを特徴とする請求項１に記載の制御装置。
【請求項４】
前記スワップ演算部は、前記パスルートについて、前記データベース部を参照して、スワップ数を最小化するように前記スワップ情報を演算することを特徴とする請求項１に記載の制御装置。
【請求項５】
前記スワップ演算部は、前記パスルートでのスワップ部位を分散するように前記スワップ情報を演算することを特徴とする請求項１に記載の制御装置。
【請求項６】
前記データベース部は、前記情報として、前記パスルートに対応するラベルパターン情報を格納することを特徴とする請求項１に記載の制御装置。
【請求項７】
前記データベース部は、前記情報として、前記パスルート、始点ポート及び終点ポートとの対応情報を格納することを特徴とする請求項１に記載の制御装置。
【請求項８】
前記スワップ演算部は、前記ラベルパターン情報について分散度情報を求めることを特徴とする請求項６に記載の制御装置。
【請求項９】
前記スワップ演算部は、前記情報を参照して、最長ルートを抽出し、前記最長ルートを用いて前記スワップ情報を演算することを特徴とする請求項１に記載の制御装置。
【請求項１０】
前記パスルート、前記パスルートの始点ポート及び終点ポートの入力を受ける入力部をさらに有することを特徴とする請求項１に記載の制御装置。
【請求項１１】
前記パスルート、前記パスルートの始点ポート及び終点ポート、及びパス開通指令の入力を受ける入力部をさらに有することを特徴とする請求項１に記載の制御装置。
【請求項１２】
前記ラベル処理部は、前記入力部が受ける入力に基づいて前記データベース部の検索をし、前記検索の結果に基づいて設定を行うことを特徴とする請求項２に記載の制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークの監視制御装置およびプログラムに係り、特にMPLS(Multi-Protocol Label Switching、マルチプロトコルラベルスイッチング) ネットワークの制御方式に関する。
【背景技術】
【０００２】
昨今、多様なサービスを行う次世代ネットワークへの移行に向けて、多種のクライアントプロトコルを収容する伝送ネットワークが必要となっている。
【０００３】
多種のクライアントプロトコルを収容する方式として、フレームやパケットにラベルと呼ばれる識別子を付加して転送する、MPLS(Multi-Protocol Label Switching、マルチプロトコルラベルスイッチング)とよばれる方式が注目を浴びている。
【０００４】
次世代ネットワークにおいては、高い通信路の伝送品質が要求される。パケット転送方式を用いたネットワークにおいては、各ノードの転送処理能力を上回るトラフィックがあるノードに流入すると、パケットロスが発生し、伝送品質が低下する。あるノードに対して、トラフィックが集中すると、網全体としては余剰処理能力があるにもかかわらず、パケットロスが発生する。
【０００５】
従って、何らかの方法により、負荷を分散させることが出来るならば、網全体での収容効率をより高めることが可能となる。或いは、網全体として同等のトラフィックを、より処理能力が低いノードから構成される網に、収容することが可能となる。
【０００６】
各ノードの転送処理負荷を分散させる為に、トラフィックの実測値を各ノード間で交換し、交換した実測値に基づいて転送経路を制御する方法が、特許文献１に開示されている。
【０００７】
一方、パケットロスによる品質低下は、各ノード間のリンクの伝送誤りによっても引き起こされる。データの伝送誤り率を低減することを目的として、ATM（Asynchronous Transfer Mode）網において、ATMセルのヘッダを対象とした誤り訂正符号を各セルに付与し、この符号に基づいて誤りを訂正する手法が非特許文献１に開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開2007-060476号公報
【非特許文献】
【０００９】
【非特許文献１】ITU-T, I.432.1, "B-ISDN user-network interface - Physical layer specification: General characteristics", 1999
【発明の概要】
【発明が解決しようとする課題】
【００１０】
パケット転送処理負荷を分散させ、且つ、各リンクの伝送誤りを低減することにより、通信路の伝送品質を向上させ、また、より処理能力が低いノードから構成される網に、収容することが可能となる。
【００１１】
MPLS網に、非特許文献1と同様の誤り訂正方式を適用する場合、パケット転送処理として、転送先を決定する処理のほかに、誤り訂正符号の計算処理が必要となる。誤り訂正符号の処理負荷の増大は、パケットロスの発生を引き起こす要因となるため、誤り訂正符号の処理負荷を分散させることで、伝送品質の向上及びトラフィックの収容効率の向上が可能である。
【００１２】
まず、誤り訂正符号を適用しないMPLS方式において、通信路の伝送品質が下がってしまうことを示す。
【００１３】
誤り訂正符号を付与しないMPLS方式において、ラベルに1ビットでも誤りがあると正しい経路選択が行えないため、パケットを破棄、または違うノードに転送してしまう。1ビットの誤りによって、１パケット分のロスになってしまうため、BER(Bit Error Rate)が高くなってしまう。図１９、２０を参照して、ラベルに誤りが発生した場合のパケット転送の例を説明する。”30”というラベルを付与されたパケット200#6を200#7に転送中にラベル値が1ビット誤り、”31”となってしまった場合、ノードBにラベル値”31”のパケットをノードDに転送するという設定はされていない場合、パケットを破棄、またはノードBにラベル値”31”のパケットを違うノードに転送するという設定がされている場合、違うノードに転送してしまう。いずれの場合も、パケットロスとなる。
【００１４】
次に、誤り訂正符号の処理負荷が、ラベルスワップを行うパケット数に依存することを示す。
【００１５】
図２０は誤り訂正符号を適用したラベルの例を示している。ノードのスイッチ部が12byteのラベル201を誤り訂正の対象にした3byteの誤り訂正符号202を算出し、ヘッダ部分として付与することで、ラベルの1ビットの誤り訂正を実現している。
【００１６】
前述の通り、誤り訂正符号202はラベル201より算出するため、ラベルスワップを行う度に誤り訂正符号202を算出しなければならない。よって、誤り訂正符号を導入したMPLSネットワークにおいて、ラベルスワップに伴うノード毎の処理負荷の増加はさらに大きなものとなっている。ノードあたりのラベルスワップ処理負荷が大きすぎると、パケットあたりの処理時間が長くなり、ノードの処理性能の限界を超えると、パケット遅延、パケットロスが引き起こされる。
【００１７】
このような状況について、パケット転送処理負荷を分散させることと、各リンクの誤り率を低減させることが課題となる。また、誤り訂正以外にも、ラベルスワップの度に再実行が必要な処理(例えば暗号化等)を適用したシステムにおいても同様の課題が生じうる。
【課題を解決するための手段】
【００１８】
以上のように、ラベルスワップを行うパケット数の増加に依存して、誤り訂正符号の処理負荷もまた増加する。従って、ラベルスワップ処理を分散させることにより、誤り訂正符号の処理負荷もまた、分散させることが可能となる。
【００１９】
そもそも、ラベルを非常に長く定義することで、始点から終点まで同一ラベルで転送すれば、ラベルスワップの必要がないため、誤り訂正符号の処理負荷を低減することはできる。しかしMPLS方式は、短いラベルによるオーバーヘッドの小ささを特徴としているため、長いラベルを用いると、転送効率が落ちてしまう。
【００２０】
したがって、高い転送効率を維持したまま、誤り訂正符号の処理負荷を軽減するためには、ラベルスワップ処理をできるだけ少なくした上で各ノードに分散させる処理が必要である。
【００２１】
上述した課題は、ネットワーク全体のラベルスワップ数を低減し、ラベルスワップ数をできるだけ各ノードに分散させるように、付与するラベルを決定する手法を設けることで、解決が可能である。
【００２２】
本発明による制御装置は一例として、第１ラベルを付与されたパケットの送受信を行う複数のノードと接続され、前記ノードへの制御信号の送受信を行う通信処理部と、前記通信処理部と接続される演算部とを有する制御装置であって、前記演算部は、前記パケットのパスルートについてのスワップ情報を演算するスワップ演算部と、前記スワップ演算部の演算結果に基づいて、前記第1ラベルを調整の設定をするラベル処理部とを有し、前記通信処理部は、前記ラベル処理部の設定に基づいて前記制御信号を前記ノードへ送受信する。
【発明の効果】
【００２３】
転送効率を下げることなく、パケット廃棄率を低減したパケットトランスポートシステムを実現することができる。
【図面の簡単な説明】
【００２４】
【図１】MPLSシステムの構成図である。
【図２】ラベルを利用したパスの例である。
【図３】MPLSノードのブロック図である。
【図４】管理マネージャの機能ブロック図である。
【図５】管理マネージャのハードブロック図である。
【図６】トポロジテーブルを説明する図である。
【図７】パステーブルを説明する図である。
【図８】装置テーブルを説明する図である。
【図９】ラベルテーブルを説明する図である。
【図１０】ラベルパターンを説明する図である。
【図１１】管理マネージャにおけるパス開通画面である。
【図１２】パス開通処理のフローチャートである。
【図１３】スワップ最小化処理のフローチャートである。
【図１４】スワップ分割最小化処理のフローチャートである。
【図１５】最小パターン更新処理のフローチャートである。
【図１６】スワップ分散処理のフローチャートである。
【図１７】ルート分割表を示す図である。
【図１８】出力表を示す図である。
【図１９】MPLS方式におけるBERの高さを説明する図である。
【図２０】誤り符号訂正のラベルモデルを示す図である。
【発明を実施するための形態】
【００２５】
以下、本発明の最良の形態について、実施例を用い図面を参照しながら説明する。
【実施例１】
【００２６】
図１を参照して、MPLSシステムの構成を説明する。図１において、100#1〜100#5の5台のMPLSノード(ノード装置)により、MPLSネットワークを構成している。各MPLSノード100は、ノード間網21により接続される。
【００２７】
MPLSノード100と 管理マネージャ1は、主回線とは別の管理情報転送用ネットワーク20により接続されたMPLSノード100#1、100#4をゲートウェイとして論理的に接続される。管理マネージャ1は管理情報転送用ネットワーク20を通じて、遠隔にてMPLSノード100の監視制御を行う。
【００２８】
MPLSノード100における、ノード間網21との接続口について、”Side01”、”Side02”、”Side03”、”Side04”と定義する。
【００２９】
実施例１においては、MPLSノード100とノード間網21の接続口の数は、最大４つとなっているが、本実施例を実施するにあたり、２つ以上の接続口であれば実施が可能であり、接続口の数の上限を定めるものではない。
【００３０】
管理マネージャ1は、図４で説明するラベル処理部48及び通信処理部44を通して、各MPLSノード100にラベルの設定を行うことで、パス22を開通する。各部についての詳細は後述する。
【００３１】
図１において、ネットワーク例を示しているが、本実施例の実施にあたり、物理的なネットワークトポロジの形式は自由な構成をとることができる。例としてリング状のトポロジ、線形トポロジ、ツリー型のトポロジ、メッシュトポロジにおいても実施可能である。また、管理情報転送用ネットワーク20のトポロジに関しても同様に、自由な構成をとれる。
【００３２】
図２を参照して、ラベルスワップを用いたパスについて説明する。ラベル”1”を付与したパケット200#1をノード100#1から、ノード100#2、ノード100#4を中継して、ノード100#5に転送するパス22#2を考える。ノード100#1は、管理マネージャ1により「ラベル”1”のパケットはラベル”1”をラベル”0”に書き換えてWest方向に転送する」という設定がされている。ノード100#2は、管理マネージャ1により「ラベル”0”のパケットはラベルを”0”のままにしてSouth方向に転送する」という設定がされている。同様に管理マネージャ1によりノード100#4、100#5にラベルスワップの設定を行うことで、パケット200を転送するパス22#2の開通を実現する。
【００３３】
図３を参照してMPLSノード100の構成を説明する。図３において、MPLSノード100は、通信インタフェース101、スイッチ部103、監視制御部104を有する。
【００３４】
以下にMPLSノード100におけるパケット転送を説明する。
【００３５】
MPLSノード100間通信時のパケットの流れについて説明する。MPLSノード100間から転送されてきたパケットは、通信インタフェース101にてスイッチ部103に転送される。次にスイッチ部103にて、ラベルのスワップ、誤り訂正符号の付与処理を行い、通信インタフェース101に転送される。次に通信インタフェース101にてノード間網21を通じて隣接ノードに転送される。
【００３６】
外部ネットワークからMPLSノード100へのパケット転送の流れについて説明する。外部ネットワークより転送されたパケットは、通信インタフェース101にてスイッチ部103に転送される。次にスイッチ部103にて、ラベルのスワップ、誤り訂正符号の付与処理を行い、通信インタフェース101に転送される。次に通信インタフェース101にてノード間網21を通じて隣接ノードに転送される。
【００３７】
MPLSノード100から外部ネットワークへのパケット転送の流れについて説明する。MPLSノード100より、転送されたパケットは、通信インタフェース101にてスイッチ部103に転送される。次にスイッチ部103にて、ラベルのスワップ、誤り訂正符号の付与処理を行い、通信インタフェース101に転送される。次に通信インタフェース101にて外部ネットワークに転送される。
【００３８】
以下に各部の詳細について説明する。
【００３９】
通信インタフェース101は、ノード間網21と接続することで、隣接したMPLSノード100とのパケットの送受信を行う。隣接したMPLSノード100から受信したパケットを適正な信号に変換し、スイッチ部103に転送する。逆にスイッチ部103から受信したパケットを適正な信号に変換し、隣接したMPLSノード100に転送する。
【００４０】
通信インタフェース101は、MPLSネットワーク外のケーブルと接続することで、MPLSネットワーク外のノードとのパケットの送受信を行う。MPLSネットワーク外のノードから受信したパケットを適正な信号に変換し、スイッチ部103に転送する。逆に逆にスイッチ部103から受信したパケットを適正な信号に変換し、MPLSネットワーク外のノードに転送する。
【００４１】
図3において方路Side01、Side03の通信インタフェース101は、外部ネットワークとの接続、方路Side02、Side04の通信インタフェース101は、隣接ノードとの接続に使用しているが、本発明の実施において各通信インタフェース101の接続先は方路によって固定されず自由である。例えばSide01の通信インタフェースを用いて、隣接ノードとの接続を行うことも可能である。
【００４２】
スイッチ部103は、受信したパケットに付与されているラベル及び入力ポートを参照し、MPLSノード100に設定されているラベルテーブルに従って、ラベルのスワップ、誤り訂正符号の演算、付与及び宛先通信インタフェース101または通信インタフェース101へのパケット転送を行う。
【００４３】
監視制御部104は、通信インタフェース101、通信インタフェース101、スイッチ部103にて検出した警報、イベント通知を収集し、その結果を管理マネージャ1へ通知する。また、監視制御装置部104は、管理マネージャ1からの制御によりスイッチ部103にたいしてラベルテーブルの設定を行う。
【００４４】
管理マネージャ1は、PC・WS等の一般的な情報処理装置であり、パス22を管理するためのソフトウェアがインストールされ、ユーザにより起動される。図４を参照して、管理マネージャ1の構成を説明する。ここで、図４は管理マネージャ 1の機能ブロック図である。
【００４５】
図４において、管理マネージャ1は入力部40、出力部41を用いてユーザにより操作される。演算部42は、MPLSノード100の監視制御に必要な演算を行い、必要な情報をデータベース部43に保持する。演算部42は、MPLSノード100に命令を実行する際に、通信処理部44に通信命令を送信し、管理マネージャ1とMPLSノード100間の通信を実現する。演算部42は、画面表示部45、スワップ演算部50、ラベル処理部48、パス管理部49にて構成される。
【００４６】
画面表示部45は、パス開通画面G00(図１１)を表示する。このため、図１１を用いて後述する。ラベル処理部48は、スワップ演算部50にて演算した結果を元に、データベース部43の更新及び、通信処理部44に通信命令（制御信号）を送信する。パス管理部49は、パス開通実行後にデータベース部43に新規開通したパスの情報を更新する。スワップ演算部50は、スワップ最小化処理部46、スワップ分散処理部47にて構成され、パケットのパスルートについてのスワップ情報を演算する。スワップ最小化処理部46、スワップ分散処理部47は、それぞれスワップ最小化処理B00（図１３）、スワップ分散処理E00（図１６）を担当する。このため、図１３〜図１６を用いて後述する。
【００４７】
図５を参照して、管理マネージャ1のハードウェア構成を説明する。ここで、図５は管理マネージャのハードウェアブロック図である。図５において、管理マネージャ1は、内部伝送路37で相互接続された中央演算処理装置（CPU）30、主記憶装置（メインメモリ）31、ネットワークカード（NIC：Network Interface Card）32、入出力部34、補助記憶装置33と、入出力部34に接続された入力部35、出力部36から構成される。
【００４８】
図４と図５との対比から明らかなように、演算部42の機能45〜50は、主記憶装置31上のプログラムを、CPU30が実行することによって、実現している。
【００４９】
図６，７，８，９は管理マネージャ1のデータベース部43が保有するテーブルを示している。各部の詳細を以下に説明する。
【００５０】
図６により、管理マネージャ1のデータベース部43が保有するトポロジテーブルT00の説明を行う。
【００５１】
各MPLSノード100にて、通信インタフェース101、通信インタフェース101の実装、装置内ケーブル、ノード間網の接続等のハード接続がおこなわれた後、ユーザは管理マネージャ1に対して、MPLSノード100の情報をトポロジテーブルT00として登録する。図６に示すトポロジテーブルT00は、ノード名情報T01、IPアドレス情報T02、Side01側の接続先情報T03、Side02側の接続先情報T04、Side03側の接続先情報T05、Side04側の接続先情報T06で構成する。
【００５２】
図７により、管理マネージャ1のデータベース部43が保有するパステーブルT10の説明を行う。
【００５３】
管理マネージャ1により、パス開通を行う際に、パスの情報をパステーブルT10に追加する。図７において、パステーブルT10は、パス名情報T11、パスルート情報T12、始点ポート情報T13、終点ポート情報T14で構成する。
【００５４】
図８により、管理マネージャ1のデータベース部43が保有する装置テーブルT20の説明を行う。
【００５５】
管理マネージャ1により通信インタフェース101の登録を行う際に、ユーザは方路Side01、Side02、Side03、Side04を選択する。管理マネージャ1は、ユーザの選択結果に従い、通信インタフェース101と方路の対応情報を装置テーブルT20に追加する。管理マネージャ1は、ユーザの選択結果に従い、通信インタフェース101の情報を装置テーブルT20に追加する。図８において、装置テーブルT20は、ノード名情報T21、方路情報T22、ポート情報T23で構成する。
【００５６】
図９により、管理マネージャ1のデータベース部43が保有するラベルテーブルT30の説明を行う。
【００５７】
管理マネージャ1によりパス開通を行う際に、スワップ演算部50の結果に従い、各装置に設定する入力ポート・ラベル、出力ポート・ラベルの情報を、ラベルテーブルT30に追加する。図９において、ラベルテーブルT30は、ノード名情報T31、入力ラベル情報T32、入力ポート情報T33、出力ラベル情報T34、出力ポート情報T35で構成する。図９に示す例においては、ラベルテーブルT30の入力ポートは全て*で同じ情報となっているため、入力ポートに依存せず、入力ラベルのみを参照するようなラベルテーブルとなっている。
【００５８】
図２、図１０により、スワップ演算部50にて用いるラベルパターンを説明する。図１０はラベルパターンの例であり、管理マネージャ1はスワップ演算部50にて行われる演算に一時的に使用するがテーブルとして保持しない。
【００５９】
パケットに付与されたラベルは、パス22の経路上のMPLSノード100を通過する毎に変化していく。そのラベルの遷移の様子を矢印で繋いだものをラベルパターンとする。例えば図２における、パスルートA→B→D→Eであるパス22#2のラベルパターンは、1→0→0→1→1といえる。図１０において、パスルートA→B→D→Eのラベルパターンが1→0→0→1→1となっていることを確認できる。
【００６０】
図１１により、管理マネージャ1におけるパス開通画面例G00を説明する。
【００６１】
管理マネージャ1の画面表示部（入力部）45はパス開通画面G00を表示する。ユーザはパス名G01、パスルートG02、始点ポートG03、終点ポートG04を入力する。ユーザが開通ボタン（パス開通指令の入力手段）G05を押下すると、管理マネージャ1はパス名G01、パスルートG02、始点ポートG03、終点ポートG04が正常に入力されていることを確認し、パス開通処理A00を実行する。
【００６２】
パス開通処理A00は図１２を用いて後述する。
【００６３】
図１２により、管理マネージャ1によるパス開通処理A00を説明する。
【００６４】
パス開通処理A00において、管理マネージャ1はG00にてユーザが入力した情報を用いて、スワップ最小化処理B00にて、スワップ数が最小になるようなラベルパターン候補を算出し、スワップ分散処理E00にて、スワップ数がノード間に最も分散されるようなラベルパターンを算出し、決定したラベルパターンをノードに設定し、管理マネージャが保有するラベルテーブルT30、パステーブルT10を更新する。
【００６５】
以下にパス開通処理A00各部の詳細を説明する。
【００６６】
パス開通画面G00にてユーザが入力したパス名、パスルート、始点ポート、終点ポートを用いて、管理マネージャ1がパス開通処理を開始する(A01)。
【００６７】
管理マネージャ1のスワップ演算部50が、A01の入力であるパスルートを入力として、スワップ最小化処理B00を実行する(A02)。スワップ最小化処理B00については図１３を用いて後述する。
【００６８】
管理マネージャ1のスワップ最小化処理部46は、パス開通画面G00にてユーザが入力したパスルート、A02にて出力したラベルパターン候補を入力として、スワップ分散処理E00を実行する(A03)。スワップ分散処理E00については図１６を用いて後述する。
【００６９】
管理マネージャ1のラベル処理部48が、A03にて出力したラベルパターン、A01の入力である始点ポート、終点ポートを用いて、通信処理部44を通じて、パスルート経路のMPLSノード100について、トポロジテーブルT00のノード名情報T01、IPアドレス情報T02を参照することで通信を行い、ラベル設定を行う(A04)。
【００７０】
管理マネージャ1のラベル制御部48が、A03にて出力したラベルパターンを、データベース部43が保有するT30ラベルテーブルに追加する(A05)。
【００７１】
管理マネージャ1のパス管理部49が、A01の入力であるパス名、パスルート、始点ポート、終点ポートを、管理マネージャ1のデータベース部43が保有するパステーブルT10に追加する(A06)。
【００７２】
管理マネージャ1は、以上の処理をもってパス開通処理A00を終了する(A07)。
【００７３】
図１３により、管理マネージャ1のスワップ演算部50(特にはスワップ最小化処理部46)によるスワップ最小化処理B00を説明する。
【００７４】
入力であるパスルートにおいて、経路上にあるMPLSノード100のスワップ数の総和が最小になる時の、スワップ数の総和を最小スワップ数、ラベルパターン(複数存在しうる)を最小パターンとおく。また、パスルートのうち、スワップを行わずに転送が可能な区間をスワップ無ルートとおく。スワップ無ルートの最小スワップ数は0である。
【００７５】
スワップ最小化処理B00において、管理マネージャ1は最小スワップ数、最小パターンの初期化後に、経路上のラベルテーブルにおいて最長のスワップ無ルートを算出する。最長のスワップ無ルートは複数存在しうるが、その全てにおいて、スワップ分散最小化処理C00を実行し、スワップ無ルートそれぞれの最小スワップ数、最小パターンを算出する。スワップ無ルートそれぞれの最小スワップ数、最小パターン、及び、最小スワップ数、最小パターンを最小パターン更新処理D00において最小スワップ数、最小パターンの更新を行い、全ての最長のスワップ無ルートにおいて、最小パターン算出した時の最小パターンをラベルパターン候補として出力する。
【００７６】
以下にスワップ最小化処理B00各部の詳細を説明する。
【００７７】
管理マネージャ1のスワップ最小化処理部46は、入力されたパスルートを用いて、スワップ最小化処理を開始する(B01)。
【００７８】
スワップ最小化処理部46は、最小スワップ数の初期値としてパスルートの長さを代入し、最小パターンの初期値として空集合を代入する(B02)。
【００７９】
スワップ最小化処理部46は、データベース部43が保有するラベルテーブルT30を用いて、経路上のラベル使用状況を演算することで、パスルートの部分ルートであり、スワップ数が0であるルートの中で最も長いルートを算出し長さをmとする。長さmのルートは複数存在しうる(B03)。
【００８０】
スワップ数0であり長さmのルートのうち、１つをRとする(B04)。
【００８１】
スワップ最小化処理部46は、B01で入力されたパスルート及び、B04で定めたRを入力として、スワップ分割最小化処理C00を実行する(B05)。スワップ分割最小化処理C00については、図１４を用いて後述する。
【００８２】
スワップ最小化処理部46は、B02にて定義した最小スワップ数、最小パターン、及びB05で出力されたRの最小スワップ数、Rの最小パターンを入力として、最小パターン更新処理D00を実行する(B06)。最小パターン更新処理D00については、図１５を用いて後述する。
【００８３】
スワップ最小化処理部46は、スワップ数0であり長さmのルートにおいて、B05〜B06未実行のルートがあるか無いかを判定する。B05〜B06未実行のルートがある場合、該当ルートに対してB05〜B06を実行し、無い場合B08に遷移する(B07)。
【００８４】
B04〜B07にて算出した最小スワップ数は、B05にて分割後のルートそれぞれの最小スワップ数をB06にて加算した結果であるが、分割前のルート全体としては、よりスワップ数が小さいルートが存在しうる。これを探索するため、スワップ最小化処理部46は、以下の判定式を満たす場合、mにm-1を代入しB04〜B06の処理を実行する(B08)。
【００８５】
【数１】
2010246063.tif 000003
上記判定式は、スワップ数が0であるルートの中で最長ルートの長さは、ルートの長さ/(ルートの最小スワップ数＋１)以上になる性質を用いている。
判定B07、B08を用いることで、スワップ数が最小になる可能性がある全てのルートに対してB05〜B06実施し、スワップ最小化処理部46は、最小パターンをラベルパターン候補として出力する(B09)。  管理マネージャ1は、以上の処理をもってスワップ最小化処理B00を終了する(B10)。
【００８６】
図１４により、管理マネージャ1のスワップ演算部50、特にはスワップ分散処理部47によるスワップ分割最小化処理C00を説明する。
【００８７】
パスルートを複数に分割する場合に、分割後の複数のパスルートを分割パスルートとする。
【００８８】
スワップ分割最小化処理C00において、管理マネージャ1は図１７で説明するルート分割表U00に従い、パスルートをスワップ無ルートとそれ以外の部分に分割する。分割表U00にて分割しないと判定された場合、つまりパスルートとスワップ無ルートが一致していた場合、出力表U10に従い、0を最小スワップ数、スワップ無ルートのラベルパターンを最小パターンとして出力する。分割表U00にて分割を行うと判定された場合、分割した全てのパスルートに対し、スワップ最小化処理B00を行い、図１８で説明する出力表U10に従い、最小スワップ数・最小パターンを出力する。スワップ最小化処理B00によりスワップ分割最小化処理C00を呼び出し、スワップ分割最小化処理C00によりスワップ最小化処理B00呼び出すことでこれ以上分割できない状態になるまで、再帰的に分割する。
【００８９】
以下に分割最小化処理C00各部の詳細を説明する。
【００９０】
スワップ最小化処理部46は、入力されたパスルート、スワップ無ルートを用いて、スワップ分割最小化処理を開始する(C01)。
【００９１】
スワップ最小化処理部46は、ルート分割表U00に従い、C01にて入力されたパスルートを分割する(C02)。
【００９２】
スワップ最小化処理部46は、C02にて分割を行わなかったか否かについて判定を行う(C03)。分割を行わなかった場合、C07に遷移する。C07については後述する。分割を行った場合、分割されたパスルート(以降分割パスルートとする)のうちの１つをRとおく(C04)。
【００９３】
スワップ最小化処理部46は、C04にて定義したRを入力として、スワップ最小化処理B00を実行する(C05)。
【００９４】
スワップ最小化処理部46は、スワップ最小化処理B00を未実施の分割パスルートがあるか否かを判定する。スワップ最小化処理未実施の分割パスルートがある場合、該当分割パスルートを入力として、スワップ分割最小化処理B00を実施し、無い場合、C07に遷移する(C06)。
【００９５】
スワップ最小化処理部46は、出力表U10に従い、最小スワップ数・最小パターンを出力する(C07)。
【００９６】
管理マネージャ1は、以上の処理をもってスワップ分割最小化処理C00を終了する(C08)。
【００９７】
図１７により、スワップ最小化処理部46がスワップ分割最小化処理のC02にて用いるルート分割表U00を説明する。
【００９８】
ルート分割表U00は、C01にて入力されたパスルートの始点・終点及び、スワップ無しルートの始点・終点の情報を用いて、どのようにルート分割を行うかを示している。スワップ無しルートの始点がパスルートの始点と一致するとき、及びスワップ無しルートの終点がパスルートの終点と一致するとき、ルートを分割しない(U01)。スワップ無しルートの始点がパスルートの始点と一致しないとき、及びスワップ無しルートの終点がパスルートの終点と一致するとき、スワップ無しルートとそれ以外の計２つのルートに分割する(U02)。スワップ無しルートの始点がパスルートの始点と一致するとき、及びスワップ無しルートの終点とパスルートの終点と一致しないとき、スワップ無しルートとそれ以外の計２つのルートに分割する(U03) 。スワップ無しルートの始点がパスルートの始点と一致しないとき、及びスワップ無しルートの終点がパスルートの終点と一致しないとき、スワップ無しルートとそれ以外の２つのルート、計３つのルートに分割する(U02)
図１８により、スワップ最小化処理部46がスワップ分割最小化処理のC07にて用いる出力表U10を説明する。
【００９９】
出力表U10は、C01にて入力されたパスルートの始点・終点及び、スワップ無しルートの始点・終点の情報、及び分割ルートの最小スワップ数、最小パターンを用いて、どのように最小スワップ数、最小パターンを出力するかを示している。
【０１００】
スワップ無しルートの始点がパスルートの始点と一致するとき、及びスワップ無しルートの終点がパスルートの終点と一致するとき、最小スワップ数は0、最小パターンはスワップ無しルートを出力する(U11)。スワップ無しルートの始点がパスルートの始点と一致するとき、及びスワップ無しルートの終点がパスルートの終点と一致しないとき、スワップ無しルート以外の分割ルートの最小スワップ数に１を加算した値を最小スワップ数、スワップ無ルートとスワップ無しルート以外の分割ルートにおける全組合せのルートを最小パターンとして出力する(U12)。１を加算する理由は、スワップ無しルートとスワップ無しルート以外の分割ルートの間でスワップが発生するからである。スワップ無しルートの始点がパスルートの始点と一致しないとき、及びスワップ無しルートの終点がパスルートの終点と一致するとき、スワップ無しルート以外の分割ルートの最小スワップ数に１を加算した値を最小スワップ数、スワップ無ルートとスワップ無しルート以外の分割ルートにおける全組合せのルートを最小パターンとして出力する(U13)。１を加算する理由は、スワップ無しルートとスワップ無しルート以外の分割ルートの間でスワップが発生するからである。スワップ無しルートの始点がパスルートの始点と一致しないとき、及びスワップ無しルートの終点がパスルートの終点と一致しないとき、スワップ無しルート以外の分割ルートの最小スワップ数合計に２を加算した値を最小スワップ数、スワップ無ルートとスワップ無しルート以外の分割ルートにおける全組合せのルートを最小パターンとして出力する(U14)。2を加算する理由は、スワップ無しルートとスワップ無しルート以外の分割ルートの間でスワップが発生するからである。
【０１０１】
図１５により、管理マネージャ1による最小パターン更新処理D00を説明する。
【０１０２】
最小パターン更新処理D00において、管理マネージャ1は入力を比較し、Rの最小スワップ数がそれまでの最小スワップ数よりも小さい場合は上書きを行い、等しい場合は追加を行う。
【０１０３】
以下に最小パターン更新処理D00各部の詳細を説明する。
【０１０４】
スワップ最小化処理部46は、入力された最小スワップ数、最小パターン、Rの最小スワップ数、Rの最小パターンを用いて最小パターン更新処理D00を開始する(D01)。
【０１０５】
スワップ最小化処理部46は、Rの最小スワップ数と最小スワップ数の比較演算を行う(D02)。Rの最小スワップ数が最小スワップ数より大きい場合、スワップ最小化処理部46は、は最小スワップ数、最小パターンの更新を行わず、D05に遷移する。Rの最小スワップ数が最小スワップ数と一致する場合、スワップ最小化処理部46は、最小パターンにRの最小パターンを加え(D03)、D05に遷移する。Rの最小スワップ数が最小スワップ数より小さい場合、スワップ最小化処理部46は、最小スワップ数にRの最小スワップ数を代入し、最小パターンにRの最小パターンを代入し(D04)、D05に遷移する。
【０１０６】
スワップ最小化処理部46は、更新したスワップ数・最小パターンを出力する(D05)。
【０１０７】
管理マネージャ1は、以上の処理をもって最小パターン更新処理D00を終了する(D06)。
【０１０８】
図１６により、管理マネージャ1によるスワップ分散処理E00を説明する。
【０１０９】
スワップ分散処理E00において、管理マネージャ1は全てのラベルパターン候補にたいして、採用時のスワップ数の標本分散（分散度情報）を算出し、最も少ないラベルパターンを出力する。
【０１１０】
以下にスワップ分散処理E00各部の詳細を説明する。
【０１１１】
スワップ分散処理部47は、入力されたパスルート、ラベルパターンを用いて、スワップ分散処理E00を開始する(E01)。
【０１１２】
スワップ分散処理部47は、ラベルパターン候補のうち、標本分散を算出していないラベルパターン候補の１つと、データベース部43が保有するラベルテーブルT30を用いて、そのラベルパターンが採用された場合の仮のラベルテーブルを作成する(E02)。
【０１１３】
スワップ分散処理部47は、E02にて作成された仮のラベルテーブルについて、スワップ数の標本分散を算出する(E03)。スワップ数の標本分散の算出には、以下の方法を用いる。仮のラベルテーブルより、ノード毎のスワップ数を算出する。ノード毎のスワップ数について、以下の数式を用いて標本分散σ2を算出する。
【０１１４】
【数２】
2010246063.tif 000004
【０１１５】
例えば、E01にて入力されたパスルートが、A→B→C→D→Eであり、あるラベルパターン候補を採用した場合のノード毎のスワップ数がそれぞれ、(3, 1, 2, 2, 4)であったとする。前述の数式より、このラベルパターンの標本分散は1.04と算出できる。
【０１１６】
標本分散は、統計学において標本が標本平均からどれだけばらけているかの指標として一般的に用いられている。スワップ分散処理部47は、標本分散を算出していないラベルパターン候補があるか否かの判定を行う(E04)。標本分散を算出していないラベルパターン候補があれば、E02〜E03を行い、標本分散を算出する。標本分散を算出していないラベルパターン候補が無ければ、E05に遷移する。
【０１１７】
スワップ分散処理部47は、ラベルパターン候補の中で最も標本分散が小さいラベルパターン候補を、ラベルパターンとして出力する。最も標本分散が小さいラベルパターン候補が複数存在した場合、辞書順で最も先頭に来るラベルパターン候補をラベルパターンとして出力する(E05)。
【０１１８】
統計学において、標本分散の値が大きいほど分散しているとしている。最も標本分散が小さいラベルパターン候補を選ぶことで、ラベルスワップ数をノード間に分散させることが可能である。
【０１１９】
管理マネージャ1は、以上の処理をもってスワップ分散処理E00を終了する(E06)。
【０１２０】
トポロジテーブルT00、パステーブルT10、装置テーブルT20、ラベルテーブルT30においては、ノードによるネットワークトポロジを構成する情報、パスを制御する情報、通信インタフェースと方路の対応情報、パケットに付与されたラベルから転送する方路が判別する情報を備えていれば、テーブル構成が異なっていても本実施例は実現可能である。
【０１２１】
パス開通画面例G00においては、パスを開通するのに必要な情報を入力する手段が備わっていれば、画面構成が異なっていても本実施例は実現可能である。
【０１２２】
パス開通処理A00においては、スワップ数が最小で、ノード毎に分散されているラベルパターンを決定し、その結果を用いて、ノードへのラベル設定、管理マネージャ1への情報の反映を実施、という流れであれば、処理の順序が異なっていても本実施例は実施可能である。
【０１２３】
スワップ最小化処理B00においては、スワップ数が最小であるようなラベルパターン候補を算出する処理であれば、異なったアルゴリズムを用いても本実施例実施可能である。
【０１２４】
スワップ分散処理E00においては、スワップ数をノード毎に分散させるようなラベルパターンを算出する処理であれば、異なったアルゴリズムを用いても本実施例は実施可能である。
【０１２５】
実施例１において、誤り訂正を適用したシステムを説明したが、暗号化等のホップ毎に実施が必要な処理を適用したシステムにおいても本実施例は実施可能である。
【０１２６】
上述した実施例に拠れば、管理マネージャ1によるパス開通時に、総スワップ数が最も小さく、スワップ数を各ノード間に最も分散させたラベルパターンを使用することが可能となる。総スワップ数が最も小さく、スワップ数を各ノード間に最も分散させたラベルパターンを使用することで、ノードあたりの負荷を抑えることを可能とし、パケットロスのリスクを下げることが可能となり、信頼性の高いMPLSネットワークを実現する。
【符号の説明】
【０１２７】
１…管理マネージャ、２０…管理情報転送用ネットワーク、２１…ノード間網、２２…パス、３０…中央演算処理装置、３１…主記憶装置、３２…ネットワークカード、３３…補助記憶装置、３４…入出力部、３５…入力部、３６…出力部、３７…コンピュータ内部伝送路、４２…演算部、４３…データベース部、４４…通信処理部、４５…画面表示部、４６…スワップ最小化処理部、４７…スワップ分散処理部、４８…ラベル処理部、４９…パス管理部、５０…スワップ演算部、１００…MPLSノード、１０１…通信インタフェース、１０３…スイッチ部、１０４…監視制御部、２００…パケット、２０１…ラベル、２０２…誤り訂正符号、２０３…データ
【図１】
2010246063.tif 000005
【図２】
2010246063.tif 000006
【図３】
2010246063.tif 000007
【図４】
2010246063.tif 000008
【図５】
2010246063.tif 000009
【図６】
2010246063.tif 000010
【図７】
2010246063.tif 000011
【図８】
2010246063.tif 000012
【図９】
2010246063.tif 000013
【図１０】
2010246063.tif 000014
【図１１】
2010246063.tif 000015
【図１２】
2010246063.tif 000016
【図１３】
2010246063.tif 000017
【図１４】
2010246063.tif 000018
【図１５】
2010246063.tif 000019
【図１６】
2010246063.tif 000020
【図１７】
2010246063.tif 000021
【図１８】
2010246063.tif 000022
【図１９】
2010246063.tif 000023
【図２０】
2010246063.tif 000024