ネットワークシステム、及び転送制御識別子の割当方法
【課題】パケット転送装置の転送制御テーブルの検索処理時間の上限値を保証し、転送制御識別子の検索処理の効率の向上と、転送制御識別子空間の有効活用とを両立するネットワークシステムを提供することを目的とする。
【解決手段】複数のパケット転送装置を備え、複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた場合の転送制御テーブル検索部の検索負荷を算出し、算出された検索負荷が所定値以下である場合、割当候補の転送制御識別子を割り当て、検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とする。
【解決手段】複数のパケット転送装置を備え、複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた場合の転送制御テーブル検索部の検索負荷を算出し、算出された検索負荷が所定値以下である場合、割当候補の転送制御識別子を割り当て、検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のパケット転送装置を備えるネットワークシステムに関し、特に、パケット転送装置が転送方法を決定するための転送制御識別子を割り当てるネットワークシステムに関する。
【背景技術】
【０００２】
パケット転送装置は、自身に入力されたパケットからヘッダを取り出し、ヘッダに含まれる転送制御識別子をキーとして、転送制御テーブルを検索することによって、入力されたパケットの転送方法を決定する。
【０００３】
例えば、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）網におけるパケット転送装置は、パケットのヘッダに含まれるラベル値をキーとして、ＭＰＬＳクロスコネクトテーブルを検索する。これによって、パケット転送装置は、パケット転送先の方路及び新たなラベル値を決定し、決定したラベル値をヘッダに格納した上で、決定した方路に向けてパケットを送信する。パケット転送先の方路はパケット毎に異なるため、パケット転送装置は、パケットが入力されるたびに、入力されたパケットをキーとしてＭＰＬＳクロスコネクトテーブルを検索しなければならない。
【０００４】
ＭＰＬＳクロスコネクトテーブルのエントリ数は、当該ＭＰＬＳクロスコネクトテーブルを備えるパケット転送装置が収容するパスの本数が多いほど多くなる。また、パケット転送装置のＭＰＬＳクロスコネクトテーブルの検索頻度はパケットの到着頻度が高いほど高くなる。したがって、多くのパスを収容するパケット転送装置、又は、高速な通信インタフェースを備えるパケット転送装置では、転送制御テーブル（例えば、ＭＰＬＳクロスコネクトテーブル）の検索処理の効率化が必要である。
【０００５】
転送制御テーブルの検索処理の効率化する方法として、Ｂ−Ｔｒｅｅ等のツリー構造を用いて転送制御テーブルを検索する方法が知られている。このツリー構造を用いる検索方法による転送制御テーブルの検索時間は、理想的には転送制御テーブルの登録エントリ数の対数時間となるが、転送制御テーブルに登録されている転送制御識別子の分布によっては、リニアサーチによる検索時間と同等まで低下する。
【０００６】
ハッシュ関数を用いて転送制御テーブルを検索する方法では、ハッシュ値の衝突（Ｃｏｌｌｉｓｉｏｎ）の発生によって、検索処理の効率が低下したり、検索が失敗することが知られている。ハッシュ値が衝突した場合の問題を解決する技術が知られている（例えば、特許文献１及び特許文献２参照）。
【０００７】
特許文献１には、「複数個のハッシュ表を含み、その各々が異なった計算されたインデックスで同時にアクセスされる」ことによって、転送エントリの検索を実現するネットワークスイッチが開示されている。
【０００８】
特許文献２には、「ハッシュテーブル形式の各種プロトコルテーブルの検索時間を短縮できるＩＰアドレス動的割り当て装置」が開示されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特表２００３−５１０９６３号公報
【特許文献２】特開２０００−２７８３２２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したように、ハッシュ値を使用して転送制御テーブルを検索する場合において、ハッシュ値の衝突が発生した場合の対処方式がいくつか知られている。しかしながら、いずれの対処方式を用いても、転送制御テーブルの検索が失敗してしまうか、転送制御テーブルの検索効率が低下してしまうという問題があった。
【００１１】
例えば、Ｃｈａｉｎｅｄ Ｈａｓｈ Ｍｅｔｈｏｄでは、ハッシュ値が同じになるデータをリスト形式で管理するため、ハッシュ値が同じになるデータが多くなり、リスト長が長くなるにつれて、処理効率は低下する。
【００１２】
特許文献１に記載された技術では、ハッシュ値の衝突による処理効率の低下を防止することによって検索処理時間を短縮できるが、検索処理時間の上限値を保証できない。ここで、パケット転送装置は、検索処理時間がパケット到着間隔を超過してしまうと、自身に到着したパケットを処理できなくなり、パケットを消失してしまう。したがって、ネットワークの通信品質を保証するためには、パケット転送装置の検索処理時間の上限値を保証することが必要となる。
【００１３】
以上より、本発明は、パケット転送装置の転送制御テーブルの検索処理時間の上限値を保証し、転送制御識別子の検索処理の効率を向上させるネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の代表的な一例を示せば、複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、前記パケット転送装置は、前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索部と、前記転送制御テーブル検索手段によって検索された前記転送方法で前記パケットを転送するパケット転送部と、を備え、前記ネットワークシステムは、前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索部の検索負荷を算出する検索負荷算出部と、前記検索負荷算出部によって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とする。
【００１５】
なお、転送制御識別子は、パケットの転送経路に関する転送制御識別子、ＱｏＳに関する転送制御識別子、及び警報転送に関する転送制御識別子の少なくとも一つを含む。
【００１６】
転送経路に関する転送制御識別子には、宛先情報、コネクション識別子、トレイル識別子、ネットワーク識別子、及び制御フラグ等である。
【００１７】
宛先情報は、例えば、ＭＡＣアドレス及びＩＰアドレス等である。コネクション識別子は、ＡＴＭのＶＰＩ（Virtual Path Identifier）／ＶＣＩ（Virtual Channel Identifier）、及びフレームリレーのＤＬＣＩ（Data-Link Connection Identifier）である。
【００１８】
ネットワーク識別子は、ＶＬＡＮ ＩＤ、ＰＢＢ（IEEE802.11ａｈ Provider Backbone Bridge）におけるＳ−ＴＡＧ／Ｃ−ＴＡＧ／Ｉ−ＳＩＤを含む拡張ＶＬＡＮ ＩＤ等である。
【００１９】
制御フラグは、ＩＰヘッダのルータアラート、及びＭＰＬＳのルータアラートラベル等である。
【００２０】
ＱｏＳに関する識別子は、具体的には、フロー識別情報及び転送廃棄優先制御情報の少なくとも一方である。フロー識別情報は、ＭＡＣアドレス、Ｅｔｈｅｒｔｙｐｅ、ＩＰアドレス、ＴＣＰ／ＵＤＰのポート番号、ＩＰｖ６のフローラベルの少なくとも一つである。また、転送廃棄優先制御情報は、ＩＰヘッダ及びＭＰＬＳヘッダのＤＳＣＰ／ＴＯＳ、並びにＬ−ＬＳＰのラベル値の少なくとも一つである。
【００２１】
警報転送に関する転送制御識別子とは、イーサＯＡＭフレームに含まれるＯＡＭ種別等の情報を含む。
【００２２】
また、転送制御テーブル検索部の検索方法は、ハッシュ関数に依らず、ツリー状のデータ構造を用いてもよい。この場合、検索処理の負荷の度合いはツリーの深さである。
【発明の効果】
【００２３】
本発明によれば、パパケット転送装置の転送制御テーブルの検索処理時間の上限値を保証でき、転送制御識別子の検索処理の効率を向上させることができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１実施形態のネットワークシステムの構成図である。
【図２】本発明の第１実施形態のパケット転送装置のインタフェース部に付与されるインタフェース名称の説明図である。
【図３】本発明の第１実施形態のラベル割当部の構成を示すブロック図である。
【図４】本発明の第１実施形態のスイッチ処理部の構成を示すブロック図である。
【図５】本発明の第１実施形態の監視制御装置のハードウェア構成を示すブロック図である。
【図６】本発明の第１実施形態のパス経路テーブルの説明図である。
【図７Ａ】本発明の第１実施形態の監視制御装置に記憶されるクロスコネクトテーブルの説明図である。
【図７Ｂ】本発明の第１実施形態のパケット転送装置に記憶されるクロスコネクトテーブルの説明図である。
【図８】本発明の第１実施形態の割当済ラベルテーブルの説明図である。
【図９】本発明の第１実施形態のあるパケット転送装置のハッシュ生成部によるハッシュ演算例の説明図である。
【図１０】本発明の第１実施形態の監視制御装置の衝突検出部のハッシュ生成部によるハッシュ演算例の説明図である。
【図１１】本発明の第１実施形態のパケット転送装置のハッシュテーブルの説明図である。
【図１２】本発明の第１実施形態の衝突検出部のハッシュテーブルの説明図である。
【図１３】本発明の第１実施形態のパケットネットワークで通信されるＭＰＬＳパケットの説明図である。
【図１４】本発明の第１実施形態のシステム規定パラメータテーブルの説明図である。
【図１５Ａ】本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置及びパケット転送装置の前半のシーケンス図である。
【図１５Ｂ】本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置及びパケット転送装置の後半のシーケンス図である。
【図１６】本発明の第１実施形態の新たなパスを確立する場合の経路管理部によって実行される処理のフローチャートである。
【図１７】本発明の第１実施形態の新たなパスを確立する場合のラベル割当部によって実行される処理のフローチャートである。
【図１８】本発明の第１実施形態の新たなパスを確立する場合の衝突検出部によって実行される処理のフローチャートである。
【図１９】本発明の第１実施形態の新たなパスを確立する場合のパケット転送装置の転送宛先制御部２２３によって実行される処理のフローチャートである。
【図２０】本発明の第１実施形態のパケット転送装置によるパケット転送処理のフローチャートである。
【図２１】本発明の第１実施形態のパケット転送装置のハッシュテーブルの説明図である。
【図２２】本発明の第１実施形態の衝突検出部１１６のハッシュテーブルの説明図である。
【図２３】本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブルの説明図である。
【図２４】本発明の第２実施形態のネットワークシステムの構成図である。
【図２５】本発明の第３実施形態のネットワークシステムの構成図である。
【図２６】本発明の転送制御識別子を管理するための２分探索木によるデータ構造の説明図である。
【発明を実施するための形態】
【００２５】
（第１実施形態）
以下、本発明の第１実施形態を図１〜図２３を用いて説明する。
【００２６】
図１は、本発明の第１実施形態のネットワークシステムの構成図である。
【００２７】
ネットワークシステムは、パケット転送装置Ａ２１〜Ｄ２４（以下、総称する場合、パケット転送という）及びリンク回線３１〜３５によって構成されるパケットネットワーク１、及び、パケット転送装置を監視する監視制御装置１１を備える。
【００２８】
監視制御装置１１は、ルータ装置４１〜４５等によって構成される制御用ネットワーク回線によってパケット転送装置と接続される。
【００２９】
パケット転送装置は、パケットを入出力するインタフェース部（２１ａ〜２１ｈ、２２ａ〜２２ｄ、２３ａ〜２３ｄ、及び２４ａ〜２４ｈ）、自身に入力されたパケットの出力先となるインタフェース部を切り替えるスイッチ処理部（ＳＷ処理部）（２１２、２２２、２３２、及び２４２）、及び、パケット転送装置の各部を制御する制御部（２１１、２２１、２３１、及び２４１）を備える。
【００３０】
図１では、パケット転送装置Ａ２１のインタフェース部２１ａとパケット転送装置Ｂ２２のインタフェース部２２ａとがリンク回線３１によって接続される。パケット転送装置Ａ２１のインタフェース部２１ｂとパケット転送装置Ｃ２３のインタフェース部２３ｂとがリンク回線３２によって接続される。パケット転送装置Ｂ２２のインタフェース部２２ｃとパケット転送装置Ｄ２４のインタフェース部２４ａとがリンク回線３３によって接続される。パケット転送装置Ｄ２４のインタフェース部２４ｂとパケット転送装置Ｃ２３のインタフェース部２３ｃとがリンク回線３４によって接続される。パケット転送装置Ｂ２２のインタフェース部２２ｄとパケット転送装置Ｃ２３のインタフェース部２３ａとがリンク回線３５によって接続される。
【００３１】
監視制御装置１１は、通信路確立要求部１１７、経路管理部１１１、通信部１１２、クロスコネクトテーブル１１３、パス経路テーブル１１４、及びラベル割当部１１５を備える。
【００３２】
通信路確立要求部１１７は通信路（パス）の確立を要求する。経路管理部１１１は、パケットネットワーク１内の経路制御を管理する。通信部１１２は、パケット転送装置と通信する。
【００３３】
クロスコネクトテーブル１１３は、パケット転送装置に入力されたパケットの転送方法を管理する転送制御テーブルの一種であり、ここでは、パケット転送装置ごとのＭＰＬＳクロスコネクト状態を管理するテーブルである。なお、クロスコネクトテーブル１１３の詳細は、図７Ａで説明する。
【００３４】
パス経路テーブル１１４は、パケットネットワーク１内のパス経路を管理するテーブルであり、図６で詳細を説明する。
【００３５】
ラベル割当部１１５は、転送制御識別子となるＭＰＬＳラベル値を各パケット転送装置に割り当てる。ラベル割当部１１５は、ＭＰＬＳラベル値のハッシュ値の衝突度合いを検出する衝突検出部１１６を備える。ラベル割当部１１５の詳細は、図３で説明する。
【００３６】
図１に示すパケットネットワーク１にはパスＰ１及びパスＰ２が確立されている。
【００３７】
パスＰ１について説明する。
【００３８】
パケット転送装置Ａ２１のインタフェース部２１ｃから入力されたパケットがインタフェース部２１ａからリンク回線３１に出力される。このパケットは、パケット転送装置Ｂ２２のインタフェース部２２ａに入力され、インタフェース部２２ｃからリンク回線３３に出力される。そして、このパケットは、パケット転送装置Ｄ２４のインタフェース部２４ａに入力され、インタフェース部２４ｈから出力される。
【００３９】
次に、パスＰ２について説明する。
【００４０】
パケット転送装置Ａ２１のインタフェース部２１ｅから入力されたパケットがインタフェース部２１ａからリンク回線３１に出力される。このパケットは、パケット転送装置Ｂ２２のインタフェース部２２ａに入力され、インタフェース部２２ｄからリンク回線３５に出力される。そして、このパケットは、パケット転送装置Ｃ２３のインタフェース部２３ａに入力され、インタフェース部２３ｄからリンク回線３４に出力される。そして、このパケットは、パケット転送装置Ｄ２４のインタフェース部２４ｂに入力され、インタフェース部２４ｇから出力される。
【００４１】
ここで、監視制御装置１１とパケット転送装置との接続について説明する。
【００４２】
パケット転送装置Ａ２１の制御部２１１はルータ装置４１に接続され、パケット転送装置Ｂ２２の制御部２２１はルータ装置４２に接続され、パケット転送装置Ｃ２３の制御部２３１はルータ装置４３に接続され、パケット転送装置Ｄ２４の制御部２４１はルータ装置４４に接続される。これらのルータ装置４１〜４４はルータ装置４５に接続され、ルータ装置４５は監視制御装置１１の通信部１１２に接続される。
【００４３】
このように、監視制御装置１１と各パケット転送装置Ａ２１〜Ｄ２４とが接続される。
【００４４】
図２は、本発明の第１実施形態のパケット転送装置のインタフェース部に付与されるインタフェース名称の説明図である。
【００４５】
インタフェース符号はパケット転送装置のインタフェース部の図１に示す符号である。インタフェース名称は、説明を簡単にするために、各インタフェース部に付与した名称であり、例えば、インタフェース部２１ａのインタフェース名称はＩＦ＿Ａ１という。
【００４６】
図３は、本発明の第１実施形態のラベル割当部１１５の構成を示すブロック図である。
【００４７】
ラベル割当部１１５は、管理部１１５１、割当済ラベルテーブル１１５２、及び衝突検出部１１６を備える。
【００４８】
なお、監視制御装置１１は、監視するパケット転送装置の数だけラベル割当部１１５を備える。一つのラベル割当部１１５は一つのパケット転送装置に対応するものとする。
【００４９】
管理部１１５１は、ラベル割当部１１５を管理及び制御する。割当済ラベルテーブル１１５２は、すでに割り当てられたラベルをパケット転送装置ごとに管理するテーブルであり、図８で詳細を説明する。
【００５０】
衝突検出部１１６は、パケット転送装置ごとに転送制御識別子のハッシュ値の衝突度合いを検出するもので、ハッシュ生成部１１６１及びハッシュテーブル１１６２を備える。
【００５１】
ハッシュ生成部１１６１は、パケット転送装置に備わる図４に示すハッシュ生成部２２３４と同じハッシュ関数によってハッシュ値を生成する。すなわち、ハッシュ生成部１１６１は、パケット転送装置に備わる図４に示すハッシュ生成部２２３４が生成するハッシュ値の分布と同じハッシュ値の分布を生成する。
【００５２】
ハッシュテーブル１１６２は、パケット転送装置ごとに割り当てられたラベルと当該ラベルのハッシュ値との対応関係を管理するテーブルであり、図１２で詳細を説明する。
【００５３】
図４は、本発明の第１実施形態のスイッチ処理部２２２の構成を示すブロック図である。
【００５４】
スイッチ処理部２２２は、転送宛先制御部２２３、及びパケット転送部２２４を備える。
【００５５】
まず、転送宛先制御部２２３について説明する。
【００５６】
転送宛先制御部２２３は、パケット転送制御装置のインタフェース部に入力されたパケットを出力するインタフェース部及び当該パケットに付与するラベルを特定する。転送宛先制御部２２３は、管理部２２３１、クロスコネクトテーブル２２３２、ハッシュテーブル２２３３、及びハッシュ生成部２２３４を備える。
【００５７】
管理部２２３１は、クロスコネクトテーブル２２３２、ハッシュテーブル２２３３、及びハッシュ生成部２２３４を制御する。
【００５８】
クロスコネクトテーブル２２３２は、ＭＰＬＳクロスコネクト状態を管理するテーブルである。具体的には、クロスコネクトテーブル２２３２は、入力されたパケットに含まれる入力ラベル又はパケットが入力されたインタフェース部（入力インタフェース）と、当該パケットを出力するインタフェース（出力インタフェース）及び当該パケットに付与される出力ラベルとを対応付けて管理する。なお、クロスコネクトテーブル２２３２の詳細は、図７Ｂで説明する。
【００５９】
ハッシュテーブル２２３３は、ハッシュ生成部２２３４が生成した入力ラベルのハッシュ値をキーとしてクロスコネクトテーブル２２３２を検索するために用いられるテーブルであり、入力ラベルのクロスコネクト情報と当該入力ラベルのハッシュ値との対応関係を管理する。なお、ハッシュテーブル２２３３の詳細は、図１２で詳細を説明する。
【００６０】
ハッシュ生成部２２３４は、入力ラベルのハッシュ値を生成する。
【００６１】
次に、パケット転送部２２４について説明する。
【００６２】
パケット転送部２２４は、入力インタフェースに入力されたパケットを転送宛先制御部２２３に渡し、転送宛先制御部２２３によって特定された出力ラベルをパケットに付与し、当該パケットを転送宛先制御部２２３によって特定された出力インタフェース部から出力する。パケット転送部２２４は、パケット転送制御部２２４１、受信パケット解析部２２４２、パケットスイッチ部２２４３、及び送信パケット生成部２２４４を備える。
【００６３】
パケット転送制御部２２４１は、受信パケット解析部２２４２、パケットスイッチ部２２４３、及び送信パケット生成部２２４４を制御する。
【００６４】
受信パケット解析部２２４２は、入力インタフェースに入力されたパケットを解析し、解析したパケットの入力ラベル及び入力インタフェース識別子を少なくとも含む情報を転送宛先制御部２２３に渡すとともに、解析したパケットをパケットスイッチ部２２４３に渡す。
【００６５】
パケットスイッチ部２２４３はパケットのクロスコネクト処理を実行する。具体的には、パケットスイッチ部２２４３は、受信パケット解析部２２４２から渡されたパケットに、転送宛先制御部２２３によって特定された出力ラベルを付与し、送信パケット生成部２２４４に渡す。
【００６６】
送信パケット生成部２２４４は、パケットスイッチ部２２４３から渡されたパケットを転送宛先制御部２２３によって特定された出力インタフェースに渡す。
【００６７】
なお、図４では、パケット転送装置Ｂ２２のスイッチ処理部２２２について説明したが、他のパケット転送装置Ａ２１、Ｃ２３、及びＤ２４のスイッチ処理部も同じ構成である。
【００６８】
図５は、本発明の第１実施形態の監視制御装置１１のハードウェア構成を示すブロック図である。
【００６９】
監視制御装置１１は、メモリ１１ａ、ＣＰＵ１１ｂ、二次記憶装置１１ｃ、及び通信インタフェース１１ｄ等のハードウェアによって構成される。メモリ１１ａには、ＣＰＵ１１ｂが実行するプログラム１１ｅ、及びＣＰＵ１１ｂが利用するデータ１１ｆが必要に応じて格納される。
【００７０】
例えば、通信路確立要求部１１７、経路管理部１１１、通信部１１２、ラベル割当部１１５の機能は、監視制御装置１１のＣＰＵ１１ｂがこれらに対応するプログラムを実行することによって実現される。
【００７１】
図６は、本発明の第１実施形態のパス経路テーブル１１４の説明図である。
【００７２】
パス経路テーブル１１４は、パケットネットワーク１に確立されたパスを管理する。パス経路テーブル１１４は、パスＩＤ１１４１及びパス経路１１４２を含む。
【００７３】
パスＩＤ１１４１には、パケットネットワーク１に確立されたパスの一意な識別子が登録される。パス経路１１４２には、パスが通る順にパケット転送装置のインタフェース部のインタフェース名称が登録される。
【００７４】
図６に示すパス経路テーブル１１４には、図１で説明したパスＰ１及びＰ２が登録される。なお、パスＰ１及びＰ２の経路については図１で説明したので説明を省略する。
【００７５】
図７Ａは、本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブル１１３の説明図である。
【００７６】
クロスコネクトテーブル１１３は、パス経路テーブル１１４によって管理されるパスが経由するパケット転送装置における入力インタフェース及び入力ラベルと出力インタフェース及び出力ラベルとの対応関係を示すクロスコネクト情報を管理する。
【００７７】
クロスコネクトテーブル１１３は、装置１１３１、入力ラベル１１３２、入力インタフェース１１３３、出力インタフェース１１３４、及び出力ラベル１１３５を含む。
【００７８】
装置１１３１には、パスが経由する各パケット転送装置の一意な識別子が登録される。入力ラベル１１３２には、入力ラベルのラベル値が登録される。入力インタフェース１１３３には、データが入力されるインタフェースの一意な識別子が登録される。
【００７９】
出力インタフェース１１３４には、入力されたパケットの出力先となるインタフェース部の一意な識別子が登録される。出力ラベル１１３５には、入力されたパケットに付与されるラベル値が登録される。
【００８０】
なお、ＭＰＬＳパケットネットワークでは、転送制御識別子としてＭＰＬＳラベル値を用いるが、パスの始点となるパケット転送装置に入力されるパケットにＭＰＬＳラベルは付与されず、また、パスの終点となるパケット転送装置が出力するパケットにＭＰＬＳラベルは付与されない。このため、図７Ａでは、パスＰ１の始点となるパケット転送装置Ａ２１のエントリの入力ラベル１１３２にはラベル値が登録されず、パスＰ１の終点となるパケット転送装置Ｄ２４のエントリの出力ラベル１１３５にはラベル値が登録されない。
【００８１】
また、パスの始点となるパケット転送装置と終点となるパケット転送装置との間の中間パケット転送装置、及び終点となるパケット転送装置は、入力されたパケットの出力インタフェース及び出力ラベルを入力インタフェースではなく入力ラベルによって決定する。このため、図７Ａでは、パスの中間パケット転送装置となるパケット転送装置Ｂ２２及び終点となるパケット転送装置Ｄ２４のエントリの入力インタフェース１１３３にはインタフェース部の識別子が登録されない。
【００８２】
図７Ｂは、本発明の第１実施形態のパケット転送装置に記憶されるクロスコネクトテーブル２２３２の説明図である。
【００８３】
パケット転送装置に記憶されるクロスコネクトテーブル２２３２には、監視制御装置１１に記憶されるクロスコネクトテーブル１１３に登録されたクロスコネクト情報のうち、当該パケット転送装置に対応するクロスコネクト情報が登録される。パケット転送装置は、自身に記憶されたクロスコネクトテーブル２２３２を監視制御装置１１からの指示に基づいて更新する。これについては、図１５Ｂ及び図１９で詳細を説明する。
【００８４】
クロスコネクトテーブル２２３２は、入力ラベル２２３２１、入力インタフェース２２３２２、出力インタフェース２２３２３、及び出力ラベル２２３２４を含む。
【００８５】
図７Ｂは、パケット転送装置Ｂ２２のクロスコネクトテーブル２２３２を一例として示す。
【００８６】
入力ラベル２２３２１は図７Ａに示す入力ラベル１１３２と同じであり、入力インタフェース２２３２２は図７Ａに示す入力インタフェース１１３３と同じであり、出力インタフェース２２３２３は図７Ａに示す出力インタフェース１１３４、及び出力ラベル２２３２４は図７Ａに示す出力ラベル１１３５と同じであるので、説明を省略する。
【００８７】
図８は、本発明の第１実施形態の割当済ラベルテーブル１１５２の説明図である。
【００８８】
割当済ラベルテーブル１１５２は、図３で説明したように、すでに割り当てられた入力ラベルを管理するテーブルである。
【００８９】
割当済ラベルテーブル１１５２は、入力ラベル１１５２１及び割当状況１１５２２を含む。
【００９０】
入力ラベル１１５２１には、すでに割り当てられた入力ラベルの値が登録される。割当状況１１５２２にはすでに割り当てられたことを示す「済」が登録される。
【００９１】
図８に示す割当済ラベルテーブル１１５２は、入力ラベル「２０１」〜「２０７」がすでに割り当てられたことを示す。
【００９２】
次に、図９及び図１０を用いてハッシュ演算例について説明する。
【００９３】
図９は、本発明の第１実施形態のあるパケット転送装置のハッシュ生成部２２３４によるハッシュ演算例２２３４１の説明図である。
【００９４】
ハッシュ生成部２２３４は、入力ラベルを入力値２２３４２としてハッシュ演算することによって、入力ラベルをハッシュ値２２３４３に変換する。
【００９５】
パケット転送装置で使用されるハッシュ関数は種々の関数が知られているが、本実施形態のパケット転送装置はいずれのハッシュ関数を使用してもよい。本実施形態では、説明の簡単にするため、ハッシュ生成部２２３４は、入力値の剰余を用いてハッシュ値を計算するものとする。具体的には、ハッシュ生成部２２３４は、式１を計算することによって入力値をハッシュ値に変換するものとする。
【００９６】
＜ハッシュ値＞＝（＜入力値＞−２００）ｍｏｄ６＋１・・・（式１）
例えば、図９に示すハッシュ演算例２２３４１では、入力値２２３４２「２０１」のハッシュ値２２３４３は「１」となる。
【００９７】
なお、入力値の剰余を用いたハッシュ値の算出方法において、接続されるリンク回線が多いパケット転送装置ほど、入力値を割る数を大きく設定したほうがよい。これは、接続されるリンク回線が多いパケット転送装置ほど、多くの入力ラベルが設定されるため、剰余の数が多いほどハッシュ値の衝突を防止できるためである。
【００９８】
図１０は、本発明の第１実施形態の監視制御装置１１の衝突検出部１１６のハッシュ生成部１１６１によるハッシュ演算例１１６１１の説明図である。
【００９９】
図１０にハッシュ演算例１１６１１を示すハッシュ生成部１１６１は、図９で説明したパケット転送装置のハッシュ生成部２２３４に対応するものである。
【０１００】
ハッシュ生成部１１６１は、入力ラベルを入力値１１６１２としてハッシュ演算することによって、入力ラベルをハッシュ値１１６１３に変換する。
【０１０１】
衝突検出部１１６のハッシュ生成部１１６１が使用するハッシュ関数は、パケット転送装置のハッシュ生成部２２３４が使用するハッシュ関数と同じである必要はないが、ハッシュ生成部１１６１が算出したハッシュ値の分布傾向は、ハッシュ生成部２２３４が算出したハッシュ値の分布傾向と同じである必要がある。このため、入力値の剰余を用いてハッシュ値を算出する方法の場合、ハッシュ生成部１１６１における剰余を算出するために入力値を割る数と、ハッシュ生成部２２３４における剰余を算出するために入力値を割る数とが同じであればよい。
【０１０２】
ハッシュ生成部１１６１は、式２を計算することによって入力値をハッシュ値に変換するものとする。
【０１０３】
＜ハッシュ値＞＝（＜入力値＞−２００）ｍｏｄ６＋２・・・（式２）
例えば、図１０に示すハッシュ演算例１１６１１では、入力値１１６１２「２０１」のハッシュ値２２３４３は「２」となる。
【０１０４】
なお、衝突検出部１１６は、パケット転送装置のハッシュ生成部２２３４に対応するハッシュ生成部１１６１を、パケット転送装置のハッシュ生成部２２３４の数だけ備える。
【０１０５】
図１１は、本発明の第１実施形態のパケット転送装置のハッシュテーブル２２３３の説明図である。
【０１０６】
ハッシュテーブル２２３３には、ハッシュ生成部２２３４によって算出された入力ラベルのハッシュ値と当該入力ラベルとの対応関係が格納される。
【０１０７】
ハッシュテーブル２２３３は、ハッシュ値２２３３１、ラベルＡ２２３３２、ラベルＢ２２３３３、及び、ラベルＣ２２３３４を含む。
【０１０８】
ハッシュ値２２３３１には、ハッシュ生成部２２３４が式１を計算することによって算出し得るハッシュ値（１〜６）が登録される。
【０１０９】
ラベルＡ２２３３２〜ラベルＣ２２３３４には、ハッシュ値に対応する入力ラベルが登録される。
【０１１０】
例えば、入力ラベル「２０１」及び「２０７」のハッシュ値「１」となるため、ハッシュテーブル２２３３のハッシュ値２２３３１「１」のエントリのラベルＡ２２３３２には「２０１」が登録され、ラベルＢ２２３３３には「２０７」が登録される。
【０１１１】
図１２は、本発明の第１実施形態の衝突検出部１１６のハッシュテーブル１１６２の説明図である。
【０１１２】
ハッシュテーブル１１６２には、ハッシュ生成部１１６１によって算出された入力ラベルのハッシュ値と当該入力ラベルとの対応関係が格納される。
【０１１３】
ハッシュテーブル１１６２は、ハッシュ値１１６２１、ラベルＡ１１６２２、ラベルＢ１１６２３、及び、ラベルＣ１１６２４を含む。ハッシュ値１１６２１は、図１１で説明したハッシュ値２２３３１と同じであるので説明を省略する。ラベルＡ１１６２２〜ラベルＣ１１６２４は、図１１で説明したラベルＡ２２３３２〜ラベルＣ２２３３４と同じであるので説明を省略する。
【０１１４】
なお、図１１及び図１２に示すハッシュテーブル２２３３及びハッシュテーブル１１６２はラベルＡ〜ラベルＣを含むので同一のハッシュ値となる入力ラベルを三つまで登録できるが、ハッシュテーブル２２３３及びハッシュテーブル１１６２に登録可能な同一のハッシュ値となる入力ラベルの数は三つに限定するものではない。
【０１１５】
図１３は、本発明の第１実施形態のパケットネットワーク１で通信されるＭＰＬＳパケット５１の説明図である。
【０１１６】
ＭＰＬＳパケット５１は、ヘッダ部５１１及びデータ部５１２によって構成される。ヘッダ部５１１は転送制御識別子であるラベル５１１１を含む。
【０１１７】
図１４は、本発明の第１実施形態のシステム規定パラメータテーブル５２の説明図である。
【０１１８】
システム規定パラメータテーブル５２には、新たなラベルを割り当てる場合のパケット転送装置ごとのポリシーに関する情報が登録される。システム規定パラメータテーブル５２は、監視制御装置１１の管理者によって入力デバイスを介して監視制御装置１１に入力され、監視制御装置１１のメモリ１１ａに保持される。
【０１１９】
システム規定パラメータテーブル５２は項目５２１及び値５２２を含む。項目５２１には、衝突上限数を識別するための情報及びラベル範囲を識別するための情報が登録される。衝突上限数は同一のハッシュ値となる入力ラベル上限数であり、ラベル範囲は使用可能なラベル値の範囲である。衝突上限数のエントリの値５２２には「１」が登録され、ラベル範囲のエントリの値５２２には「１００−９９９」が登録される。
【０１２０】
次に、パスＰ１を新たに確立する場合の監視制御装置１１及びパケット転送装置のシーケンスについて、図１５Ａ及び図１５Ｂを説明する。
【０１２１】
図１５Ａは、本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置１１及びパケット転送装置の前半のシーケンス図である。
【０１２２】
通信路確立要求部１１７は、パケット転送装置間で通信路（パス）を確立する必要がある場合、パス開通要求を経路管理部１１１に入力する（９０１）。図１５Ａでは、通信路確立要求部１１７は、図１に示すパスＰ１を確立するためのパス開通要求を経路管理部１１１に入力する。当該パス開通要求には、始点となるパケット転送装置のインタフェース部、終点となるパケット転送装置のインタフェース部、及びパス種別等がパス開通条件として含まれる。
【０１２３】
経路管理部１１１は、パス開通要求が入力された場合、入力されたパス開通要求に含まれるパス開通条件を取得する（９０１１）。そして、経路管理部１１１は、取得した始点及び終点に基づいて任意のアルゴリズム（例えば、ダイクストラ法）を用いてパス経路を決定し、決定したパス経路をパス経路テーブル１１４に登録するとともに、決定したパス経路に基づいてクロスコネクトテーブル１１３を更新する（９０１２）。
【０１２４】
クロスコネクトテーブル１１３の更新方法について説明する。
【０１２５】
経路管理部１１１は、図７Ａに示すクロスコネクトテーブル１１３に装置１１３１にパスＰ１が経由するパケット転送装置Ａ２１、Ｂ２２及びＤ２４の識別子が登録される三つのエントリを新たに追加する。
【０１２６】
そして、経路管理部１１１は、パスＰ１の始点となるパケット転送装置Ａ２１のエントリの入力ラベル１１３２にラベル値を登録せず、入力インタフェース１１３３にパス開通条件に含まれる始点となるインタフェース部の一意な識別子（ＩＦ＿Ａ３）を登録し、出力インタフェース１１３４にパス経路に含まれるパケット転送装置Ａ２１の出力インタフェースの一意な識別子（ＩＦ＿Ａ１）を登録する。なお、ステップ９０１２の処理の段階では、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に割り当てられるラベル値が決定されていないので、経路管理部１１１は、出力ラベル１１３５に何も登録しない。
【０１２７】
また、経路管理部１１１は、中間パケット転送装置Ｂ２２のエントリの入力インタフェース１１３３に何も登録せず、パス経路に含まれるパケット転送装置Ｂ２２の出力インタフェースの一意な識別子（ＩＦ＿Ｂ３）を出力インタフェース１１３４に登録する。なお、ステップ９０１２の処理の段階では、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に割り当てられるラベル値が決定されていないので、入力ラベル１１３２には何も登録されない。また、パケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３に割り当てられるラベル値が決定されていないので、出力ラベル１１３５には何も登録されない。
【０１２８】
さらに、経路管理部１１１は、パスＰ１の終点となるパケット転送装置Ｄ２４のエントリの入力インタフェース１１３３及び出力ラベル１１３５に何も登録せず、パス開通条件に含まれる終点となるインタフェース部の一意な識別子（ＩＦ＿Ｄ８）を出力インタフェース１１３４に登録する。なお、パケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３に割り当てられるラベル値が決定されていないので、入力ラベル１１３２には何も登録されない。
【０１２９】
以上によって、クロスコネクトテーブル１１３が更新される。
【０１３０】
パスＰ１は、パケット転送装置Ａ２１、パケット転送装置Ｂ２２、及びパケット転送装置Ｄ２４を経由するため、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１、及びパケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３で転送されるパケットに含まれるラベルを決定する必要がある。
【０１３１】
例えばパケット転送装置Ａ２１とパケット転送装置Ｂ２２との間で転送されるパケットのラベルを決定する場合、パケット転送装置Ｂ２２の入力ラベルを決定すれば、パケット転送装置Ａ２１の出力ラベルは当該入力ラベルになるので、本実施形態では、受信側のパケット転送装置Ｂ２２の入力ラベルを決定することによって、リンク回線３３のラベルを決定する。
【０１３２】
まず、経路管理部１１１は、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に新たなラベルを割り当てる要求であるラベル割当要求を、パケット転送装置Ｂ２２に対応するラベル割当部Ｂ１１５に入力する（９０２）。
【０１３３】
ラベル割当部Ｂ１１５は、パケット転送装置Ｂ２２用のシステム規定パラメータテーブル５２のラベル範囲に登録された範囲のラベルのうち、パケット転送装置Ｂ２２用の割当済ラベルテーブル１１５２に登録されていないラベルであって、割当不可フラグが設定されていない割当可能ラベルを特定し、特定した割当可能ラベルから任意の一つのラベルを割当候補ラベルとして選択する（９０２１）。割当不可フラグは、ハッシュ値の衝突数が上限値よりも大きいと判定されたラベルに設定され、図１７に示すステップ８２８の処理で説明する。
【０１３４】
そして、ラベル割当部Ｂ１１５は、選択した割当候補ラベルのハッシュ値の衝突数の取得要求を衝突検出部Ｂ１１６に入力する（９０３）。
【０１３５】
衝突検出部Ｂ１１６は、衝突数の取得要求が入力された場合、入力された衝突数の取得要求の割当候補ラベルのハッシュ値をハッシュ生成部１１６１に算出させる（９０３１）。そして、衝突検出部Ｂ１１６は、ハッシュテーブル１１６２を参照し、算出したハッシュ値のエントリに登録された入力ラベルの数を衝突数として取得する（９０３２）。
【０１３６】
次に、衝突検出部Ｂ１１６は、ステップ９０３２の処理で取得した衝突数を、衝突数の取得要求の応答としてラベル割当部Ｂ１１５に入力する（９０４）。
【０１３７】
ラベル割当部Ｂ１１５は、衝突検出部Ｂ１１６から衝突数の取得要求に対する応答が入力された場合、入力された応答に含まれる衝突数と、パケット転送装置Ｂ２２用のシステム規定パラメータテーブル５２に登録された衝突上限数とを比較し、衝突数が衝突上限数よりも大きい場合、ステップ９０２１の処理に戻り、割当候補ラベルを再度選択する（９０４１及び９０５）。一方、ラベル割当部Ｂ１１５は、衝突数が衝突上限数以下である場合、割当候補ラベルを入力ラベルに割り当てることを決定し、当該ラベル値をラベル割当要求の応答として経路管理部１１１に入力する（９０６）。
【０１３８】
経路管理部１１１は、ラベル割当部Ｂ１１５からラベル値が入力された場合、入力されたラベル値を、クロスコネクトテーブル１１３のエントリのうちパケット転送装置Ａ２１のエントリ及びパケット転送装置Ｂ２２のエントリに登録する（９０６１）。
【０１３９】
具体的には、経路管理部１１１は、ステップ９０１２の処理で追加したエントリのうち、パケット転送装置Ａ２１のエントリの出力ラベル１１３５にラベル割当部１１５から入力されたラベル値を登録し、パケット転送装置Ｂ２２のエントリの入力ラベル１１３２にラベル割当部１１５から入力されたラベル値を登録する。
【０１４０】
次に、経路管理部１１１は、パケット転送装置Ｂ２２とパケット転送装置Ｄ２３との間に新たなラベルを割り当てる要求であるラベル割当要求を、パケット転送装置Ｄ２３に対応するラベル割当部Ｄ１１５に入力する（９０７）。
【０１４１】
なお、ステップ９０７１〜９１１１の処理は、ステップ９０２１〜９０６１の処理と同じであるので説明を省略する。
【０１４２】
これによって、監視制御装置１１側で、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間、及びパケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間で転送されるパケットに含まれるラベルを決定することができる。
【０１４３】
図１５Ｂは、本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置１１及びパケット転送装置の後半のシーケンス図である。
【０１４４】
経路管理部１１１は、追加要求をパケット転送装置Ａ２１に送信する（９２１）。追加要求は、ステップ９０６１の処理で更新されたパケット転送装置Ａ２１用のクロスコネクトテーブル１１３のエントリをパケット転送装置Ａ２１のクロスコネクトテーブル２２３２に追加する要求であり、パケット転送装置Ａ２１用のクロスコネクトテーブル１１３で更新されたエントリ（入力ラベル、入力インタフェース、出力インタフェース、出力ラベル）をクロスコネクト情報として含む。
【０１４５】
パケット転送装置Ａ２１は、追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報に基づいて、クロスコネクトテーブル２２３２にエントリを追加し（９２１１）、追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信する（９２２）。
【０１４６】
次に、経路管理部１１１は、パケット転送装置Ｂ２２用のクロスコネクトテーブル１１３のエントリのうちステップ９０６１及び９１１１の処理で更新したエントリを、パケット転送装置Ｂ２２のクロスコネクトテーブル２２３２に追加する追加要求をパケット転送装置Ｂ２２に送信する（９２３）。
【０１４７】
パケット転送装置Ｂ２２は、追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報に基づいて、クロスコネクト情報に含まれる入力ラベルのハッシュ値をハッシュ生成部２２３４に算出させる（９２３１）。
【０１４８】
次に、パケット転送装置Ｂ２２は、受信した追加要求に含まれるクロスコネクト情報をクロスコネクトテーブル２２３２にエントリを追加するとともに、ステップ９２３１の処理で算出したハッシュ値と、ステップ９２３１の処理でクロスコネクトテーブル２２３２に追加したエントリに含まれる入力ラベル、出力インタフェース、及び出力ラベルとを対応付けた情報をハッシュテーブル２２３３に登録する（９２３２）。
【０１４９】
そして、パケット転送装置Ｂ２２は、ステップ９２３の処理で送信された追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信する（９２４）。
【０１５０】
次に、経路管理部１１１は、ステップ９１１１の処理で更新されたパケット転送装置Ｄ２４用のクロスコネクトテーブル１１３のエントリを、パケット転送装置Ｄ２４のクロスコネクトテーブル２２３２に追加する追加要求をパケット転送装置Ｄ２４に送信する（９２５）。
【０１５１】
追加要求を受信したパケット転送装置Ｄ２４が実行するステップ９２５１〜９２６の処理は、パケット転送装置Ｂ２２が実行するステップ９２３１〜９２５の処理と同じであるので、説明を省略する。
【０１５２】
経路管理部１１１は、パケット転送装置Ｄ２４から結果応答を受信すると、ステップ９０１の処理で入力されたパス開通要求に対してパスが開通したことを応答する（９７２）。
【０１５３】
以上によって、パスＰ１が経由するパケット転送装置Ａ２１、Ｂ２２、及びＤ２４に対して、入力されるパケットに含まれる入力ラベルのハッシュ値と、当該パケットを出力する出力インタフェース及び当該パケットを出力する場合に含める出力ラベルとを対応付けることができる。これによって、パケット転送装置Ｂ２２、及びパケット転送装置Ｄ２４は、入力ラベルのハッシュ値に基づいて出力インタフェース及び出力ラベルを検索できる。
【０１５４】
図１６は、本発明の第１実施形態の新たなパスを確立する場合の経路管理部１１１によって実行される処理のフローチャートである。
【０１５５】
まず、経路管理部１１１は、通信路確立要求部１１７から入力されたパス開通要求に含まれるパス開通条件を取得する（８１１）。ステップ８１１の処理は図１５Ａに示すステップ９０１１の処理に相当する。
【０１５６】
次に、経路管理部１１１は、取得したパス開通条件の始点及び終点に基づいてパス経路を決定する（８１２）。ステップ８１２の処理は図１５Ａに示すステップ９０１２の処理に相当する。なお、パス経路を決定するアルゴリズムは任意のアルゴリズムでよく、例えば、ダイクストラ法を使用する。
【０１５７】
次に、経路管理部１１１は、ステップ８１２の処理で決定されたパス経路に含まれるパケット転送装置間のリンクに新たなラベルを割り当てるラベル割当要求を、各パケット転送装置に入力する（８１３）。ラベル割当要求は、ラベルを割り当てるリンクの始点となる出力インタフェースの識別子、及び、当該リンクの終点となる入力インタフェースの識別子からなるラベル割当条件を含む。ステップ８１３の処理は図１５Ａに示すステップ９０２及び９０７の処理に相当する。
【０１５８】
次に、経路管理部１１１は、ステップ８１３の処理でラベル割当要求を送信したラベル割当部１１５から各リンクに割り当てられるラベル値を受信する（８１４）。ステップ８１４の処理は図１５Ａに示すステップ９０６及び９１１の処理に相当する。
【０１５９】
次に、経路管理部１１１は、ステップ８１４の処理で受信したラベル値に基づいてクロスコネクトテーブル１１３を更新する（８１５）。ステップ８１５の処理は図１５Ａに示すステップ９０６１及び９１１１の処理に相当する。
【０１６０】
次に、経路管理部１１１は、ステップ８１２の処理で決定されたパス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられたか否かを判定する（８１６）。
【０１６１】
ステップ８１６の処理で、パス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられていないと判定された場合、ステップ８１３の処理に戻る。
【０１６２】
一方、ステップ８１６の処理で、パス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられたと判定された場合、経路管理部１１１は、当該パス経路上のすべてのパケット転送装置に対して、パケット転送装置のクロスコネクトテーブルに新たなエントリを追加する追加要求を送信し（８１７）、処理を終了する。ステップ８１７の処理は図１５Ｂに示すステップ９２１、９２３、及び９２５の処理に相当する。
【０１６３】
図１７は、本発明の第１実施形態の新たなパスを確立する場合のラベル割当部１１５によって実行される処理のフローチャートである。
【０１６４】
まず、ラベル割当部１１５は、経路管理部１１１によって入力されたラベル割当要求に含まれるラベル割当条件を取り出す（８２１）。
【０１６５】
次に、ラベル割当部１１５は、自身に対応するパケット転送装置用のシステム規定パラメータテーブル５２に登録されたラベル範囲から割当可能ラベルを特定し、特定した割当可能ラベルから任意の一つのラベルを割当候補ラベルとして選択する（８２２）。割当可能ラベルは、当該ラベル割当部１１５に対応するパケット転送装置用の割当済ラベルテーブル１１５２に登録されていないラベルであって、かつ割当不可フラグが設定されていないラベルである。ステップ８２２の処理は、図１５Ａに示すステップ９０２１及び９０７１の処理に相当する。
【０１６６】
次に、ラベル割当部１１５は、ステップ８２２の処理で選択した割当候補ラベルのハッシュ値の衝突数の取得要求を、自身の衝突検出部１１６に入力する（８２３）。ステップ８２３の処理は図１５Ａに示すステップ９０３及び９０８の処理に相当する。
【０１６７】
次に、ラベル割当部１１５には、衝突数の取得要求の応答として割当候補ラベルのハッシュ値の衝突数が衝突検出部１１６から入力される（８２４）。ステップ８２４の処理は図１５Ａに示す９０４及び９０９の処理に相当する。
【０１６８】
次に、ラベル割当部１１５は、ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が、自身に対応するパケット転送装置用のシステム規定パラメータテーブル５２に登録された衝突上限数以下であるか否かを判定する（８２５）。
【０１６９】
ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が衝突上限数よりも大きいと、ステップ８２５の処理で判定された場合、ラベル割当部１１５は、割当候補ラベルに割当不可フラグを設定し（８２８）、ステップ８２２の処理に戻る。この処理は図１５Ａに示すステップ９０４１の処理に相当する。
【０１７０】
一方、ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が衝突上限数以下であると、ステップ８２５の処理で判定された場合、ラベル割当部１１５は、割当候補ラベルのラベル値をリンクに割り当てることを決定し、当該ラベル値をラベル割当要求の応答として経路管理部１１１に入力する（８２６）。ステップ８２６の処理は図１５Ａに示すステップ９０６の処理に相当する。
【０１７１】
次に、ラベル割当部１１５は、ステップ８２８の処理で設定された割当不可フラグをクリアし、処理を終了する。
【０１７２】
図１８は、本発明の第１実施形態の新たなパスを確立する場合の衝突検出部１１６によって実行される処理のフローチャートである。
【０１７３】
まず、衝突検出部１１６は、ラベル割当部１１５から入力された衝突数取得要求から、衝突数を確認する割当候補ラベルのラベル値を取り出す（８３１）。
【０１７４】
次に、衝突検出部１１６は、ステップ８３１の処理で取り出されたラベル値からハッシュ値を算出する（８３２）。ステップ８３２の処理は図１５Ａに示すステップ９０３１及び９０８１の処理に相当する。
【０１７５】
次に、衝突検出部１１６は、ハッシュテーブル２２３３を参照し、ステップ８３２の処理で算出されたハッシュ値と一致するエントリに登録されている入力ラベルの数を衝突数として算出する（８３３）。ステップ８３３の処理は図１５Ａに示すステップ９０３２及び９０８２の処理に相当する。
【０１７６】
次に、衝突検出部１１６は、ステップ８３３の処理で算出された衝突数をラベル割当部１１５に入力し（８３４）、処理を終了する。
【０１７７】
図１９は、本発明の第１実施形態の新たなパスを確立する場合のパケット転送装置の転送宛先制御部２２３によって実行される処理のフローチャートである。
【０１７８】
まず、転送宛先制御部２２３は、監視制御装置１１の経路管理部１１１によって送信された追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報を取り出す（８４１）。クロスコネクト情報は、監視制御装置１１のクロスコネクトテーブル１１３のエントリのうち、新たなパスを確立させるための処理で追加されたエントリに登録された情報を含む。
【０１７９】
次に、転送宛先制御部２２３は、ステップ８４１の処理で取り出されたクロスコネクト情報に含まれる入力ラベルのハッシュ値を算出する（８４２）。ステップ８４２の処理は図１５Ｂに示すステップ９２３１の処理に相当する。
【０１８０】
次に、転送宛先制御部２２３は、ステップ８４１の処理で取り出されたクロスコネクト情報をクロスコネクトテーブル２２３２に新たなエントリとして追加するとともに、ステップ８４２の処理で算出したハッシュ値と、クロスコネクトテーブル２２３２に追加したエントリに含まれる入力ラベル、出力インタフェース、及び出力ラベルとを対応付けた情報を、ハッシュテーブル２２３３に登録する（８４３）。ステップ８４３の処理は図１５Ｂに示すステップ９２３２の処理に相当する。
【０１８１】
次に、転送宛先制御部２２３は、受信した追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信し（８４４）、処理を終了する。ステップ８４４の処理は図１５Ｂに示すステップ９２４の処理に相当する。
【０１８２】
次に、パケット転送装置がパケットを受信した場合に実行されるパケット転送処理を図２０を用いて説明する。
【０１８３】
図２０は、本発明の第１実施形態のパケット転送装置によるパケット転送処理のフローチャートである。
【０１８４】
図２０では、パケット転送装置Ｂ２２が入力ラベル「２０７」を含むパケットを受信した場合のパケット転送処理について説明する。
【０１８５】
入力ラベル「２０７」を含むパケットはパケット転送装置Ｂ２２のインタフェース部２２ｂを介して入力され、インタフェース部２２ｂは入力されたパケットを図４に示すスイッチ処理部２２２に渡す。
【０１８６】
受信パケット解析部２２４２は、スイッチ処理部２２２に渡されたパケットの図１３に示すヘッダ部５１１からラベル５１１１「２０７」を取り出す（８５１）。
【０１８７】
パケット転送制御部２２４１は、ステップ８５１の処理で取り出された入力ラベル「２０７」をハッシュ生成部２２３４に渡し、ハッシュ生成部２２３４は、入力ラベル「２０７」のハッシュ値「１」を算出する（８５２）。
【０１８８】
次に、管理部２２３１は、ハッシュテーブル２２３３及びクロスコネクトテーブル２２３２を参照し、ステップ８５２の処理で算出されたハッシュ値「１」に対応する一つ目のクロスコネクト情報を読み出す（８５３）。図１１に示すハッシュテーブル２２３３ではハッシュ値「１」に対応する一つ目の入力ラベル「２０１」は、クロスコネクトテーブル２２３２の入力ラベル「２０１」のクロスコネクト情報（図７参照）と対応付けられているので、管理部２２３１は、当該クロスコネクト情報を読み出す。
【０１８９】
そして、管理部２２３１は、ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致するか否かを判定する（８５４）。
【０１９０】
ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致しないと、ステップ８５４の処理で判定された場合、管理部２２３１は、ステップ８５３の処理に戻り、ステップ８５２の処理で算出されたハッシュ値に対応する次のクロスコネクト情報を読み出す。
【０１９１】
なお、ステップ８５３及び８５４の処理は、パケットに含まれる入力ラベルと一致する入力ラベルのクロスコネクト情報が読み出されるまで繰り返し実行される。
【０１９２】
最初にステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベル「２０１」とパケットから取り出された入力ラベル「２０７」とは一致しないので、ステップ８５３の処理に戻る。そして、ステップ８５３の処理では、管理部２２３１は、図１１に示すハッシュテーブル２２３３ではハッシュ値「１」に対応する二つ目の入力ラベル「２０７」に対応付けられるクロスコネクト情報を読み出す。ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベル「２０１」とパケットから取り出された入力ラベル「２０７」とが一致するので、ステップ８５５の処理が実行される。
【０１９３】
一方、ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致すると、ステップ８５４の処理で判定された場合、管理部２２３１は、パケットを出力するインタフェース部が当該クロスコネクト情報に含まれる出力インタフェース（ＩＦ＿Ｂ４：インタフェース部２２ｄ）となるように、パケットスイッチ部２２４３を設定する（８５５）。
【０１９４】
次に、送信パケット生成部２２４４は、パケットのヘッダ部５１１のラベル５１１１をクロスコネクト情報に含まれる出力ラベル「３０２」に書き換えて、当該パケットを出力インタフェースとなるインタフェース部２２ｄに出力し（８５６）、パケット転送処理を終了する。
【０１９５】
本発明を適用せずに、新たに確立させるパスの経路に含まれるパケット転送装置間のリンクに新たなラベルを割り当てた場合、各パケット転送装置内においてラベルのハッシュ値の衝突数の上限を保証できない。
【０１９６】
つまり、図２０に示すパケット転送処理において、ステップ８５３及び８５４のループ処理を何回実行するかが保証できないため、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまい、パケットの消失を招いてしまう可能性がある。
【０１９７】
本発明では、図１４に示すシステム規定パラメータテーブル５２に登録された衝突上限数以下となるようにラベルを決定するので、各パケット転送装置内においてラベルのハッシュ値の衝突数の上限を保証でき、ステップ８５３及び８５４のループ処理を何回実行するかが保証できる。このため、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまい、パケットの消失を招いてしまうことを防止できる。
【０１９８】
パスＰ１を確立させる場合には、リンク回線３１のラベルを決定する必要があるが、パケット転送装置Ｂ２２は、図２０に示すステップ８５３及び８５４の処理が２回実行されれば、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまうものとする。
【０１９９】
この場合、図１１及び図１２のように、パケット転送装置Ｂ２２の入力ラベルに「２０７」が割り当てられた場合、ハッシュ値「１」の衝突数が２回となり、図２０で説明したように、図２０に示すステップ８５３及び８５４の処理が２回実行されるので、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまう。
【０２００】
パケット転送装置Ｂ２２のシステム規定パラメータテーブル５２の衝突上限数に「１」を設定することによって、衝突数上限数が１回となり、割当候補に「２０７」が選択されたとしても、図１７に示すステップ８２５の処理で、「２０７」を入力ラベルとした場合、ハッシュ値「１」の衝突数が２回となるため、「２０７」以外のラベル値で、衝突上限数が１回以下となるラベル値が入力ラベルと決定される。ここで、「２０９」が入力ラベルとして決定された場合のハッシュテーブル１１６２及び２２３３、並びにクロスコネクトテーブル１１３について、図２１〜図２３を用いて説明する。
【０２０１】
図２１は、本発明の第１実施形態のパケット転送装置のハッシュテーブル２２３３の説明図である。
【０２０２】
図２２は、本発明の第１実施形態の衝突検出部１１６のハッシュテーブル１１６２の説明図である。
【０２０３】
上述したように、ラベル値「２０７」は、衝突上限数が１回以下となるラベル値「２０９」が入力ラベルとなるので、図２１及び図２２では、衝突数が１回よりも大きくなるハッシュ値は存在しない。
【０２０４】
図２３は、本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブル１１３の説明図である。
【０２０５】
図２１及び図２２と同じく、パケット転送装置Ｂ２２のエントリの入力ラベル「２０７」は、衝突上限数が１回以下となるラベル値「２０９」に変更されている。
【０２０６】
以上のように、本実施形態では、パケット転送装置の転送制御テーブルの検索時間の上限を保証できる。
【０２０７】
また、転送制御識別子の各パケット転送装置内におけるハッシュ値の衝突数に基づいて、割当候補となる転送制御識別子の割り当てを許可するので、ネットワーク内における転送制御識別子は一意でなくてもよいので割当可能な転送制御識別子空間を有効活用できる。
【０２０８】
特許文献２に記載された技術は、ハッシュ値の衝突が発生しないように、転送制御識別子（特許文献２ではＩＰアドレス）を割り当てるものであるが、割り当てられる転送制御識別子のハッシュ値の分布をネットワーク内で均一化するものであり、本実施形態のように、個々のパケット転送装置内での転送制御識別子のハッシュ値衝突をパケット転送装置ごとに個別に検出し、当該ハッシュ値の衝突数を制御するものではない。
【０２０９】
例えば、二つの転送制御識別子が同じハッシュ値であり、二つの転送制御識別子が同じパケット転送装置を通過しなければ、ハッシュ値が二つの転送制御識別子が割り当てられてもよいが、特許文献２に記載された技術では、このような転送制御識別子は互いに同時に（期間が重なって）割当てられることはない。このため、特許文献２に記載された技術では、結果として使用可能な転送制御識別子が減少してしまう。
【０２１０】
また、特許文献２に記載された技術はハッシュ値の衝突を一切許容しない。このため、ハッシュ値と転送制御識別子との関係をＣｈａｉｎｅｄ Ｈａｓｈ Ｍｅｔｈｏｄを用いて管理するパケット転送装置の転送制御識別子の検索時間が、パケット到着間隔よりも格段に短い場合であっても、ハッシュ値が同一となる複数の転送制御識別子は割り当てられない。
【０２１１】
このため、特許文献２に記載された技術では、転送制御識別子空間を有効に活用できない。これに対して、本実施形態によると、転送制御識別子の検索処理の効率の向上と、転送制御識別子空間の有効活用とを両立させることができる。
【０２１２】
また、特許文献２に記載の技術では、一つのネットワークで単一のハッシュ関数の使用を前提としているので、特許文献２に記載された技術は、一つのネットワークで複数のハッシュ関数が使用された場合には適用できない。例えば、パケット転送装置ごと又はパケット転送装置のモジュールごとにハッシュ関数が異なる場合には、特許文献２に記載された技術は適用できない。
【０２１３】
本実施形態では、パケット転送装置２２に備わるハッシュ生成部２２３４に対応して、監視制御装置１１はハッシュ生成部１１６１を備えるため、一つのネットワークで複数のハッシュ関数が使用された場合であっても適用できる。
【０２１４】
また、本実施形態では、システム規定パラメータテーブル５２の衝突上限数は管理者が変更可能であるので、管理者は、各パケット転送装置が転送するパケットのサイズ及び各パケット転送装置に要求される品質（例えば、通信品質等）に基づいて、衝突上限数を柔軟に変更できる。
【０２１５】
また、本実施形態では、転送制御識別子のハッシュ値の衝突数の上限を保証するので、パケット転送装置による転送方法の検索時間の最大値を保証することによって、パケット転送装置の最大処理負荷を保証する。これによって、パケット転送装置で転送方法の検索時間が長くなり、処理負荷が増大することがなくなるため、本実施形態のパケット転送装置の単位ハードウェア資源（ロジック規模及びメモリ量）当たりの処理可能なパケット数を増加させることができる。このため、ハードウェアが同一のパケット転送装置であっても、本実施形態を適用したパケット転送装置のほうが、多くのフローを制御でき、高速な通信インタフェースを実現できる。また、本実施形態を適用したパケット転送装置は、本実施形態を適用しないパケット転送装置と同じ数のフローを制御する場合、又は同じ速度の通信インタフェースを実現する場合であっても、使用するハードウェア資源を削減できるため、消費電力を低減できる。
【０２１６】
（第２実施形態）
本発明の第２実施形態について図２４を用いて説明する。
【０２１７】
本実施形態は、第１実施形態では監視制御装置１１に備わる衝突検出部１１６を各パケット転送装置２１に備わるようにした実施形態である。
【０２１８】
図２４は、本発明の第２実施形態のネットワークシステムの構成図である。
【０２１９】
監視制御装置１１のラベル割当部１１５は衝突検出部１１６を備えず、各パケット転送装置Ａ２１〜Ｄ２４が衝突検出部１１６ａ〜１１６ｄを備える。
【０２２０】
本実施形態の新たなパスを確立させるための処理は、第１実施形態の処理と同じであるので、説明を省略する。
【０２２１】
ただ、図１５Ａに示すステップ９０３及び９０８の処理では、ラベル割当部１１５が、自身に対応するパケット転送装置にハッシュ衝突数取得要求を送信する。
【０２２２】
（第３実施形態）
本発明の第３実施形態について図２５を用いて説明する。
【０２２３】
本実施形態は、第１実施形態では監視制御装置１１はラベル割当部１１５を備えず、各パケット転送装置Ａ２１〜Ｄ２４がラベル割当部１１５ａ〜１１５ｄを備える。
【０２２４】
図２５は、本発明の第３実施形態のネットワークシステムの構成図である。
【０２２５】
監視制御装置１１はラベル割当部１１５を備えず、各パケット転送装置Ａ２１〜Ｄ２４がラベル割当部１１５ａ〜１１５ｄを備える。なお、各パケット転送装置Ａ２１〜Ｄ２４のラベル割当部１１５ａ〜１１５ｄは、衝突検出部１１６ａ〜１１６ｄを備える。
【０２２６】
本実施形態の新たなパスを確立させるための処理は、第１実施形態の処理と同じであるので、説明を省略する。
【０２２７】
ただ、図１５Ａに示すステップ９０２及び９０７の処理では、経路管理部１１１が、ラベルを決定するラベル割当部１１５を備えるパケット転送装置にラベル割当要求を送信する。
【０２２８】
なお、第３実施形態では、いずれかのパケット転送装置が、例えばＭＰＬＳシグナリングを用いてパス経路を決定すれば、監視制御装置１１は不要となる。
【０２２９】
本発明では、各パケット転送装置がハッシュ値を算出するために使用するハッシュ関数は、各パケット転送装置間で異なっていてもよい。
【０２３０】
また、本発明では、図１、図２４及び図２５でパケットネットワーク１のトポロジーを図示したが、本トポロジーに限定されず、リングトポロジー、リニアトポロジー、メッシュトポロジー、及びＰ２Ｐトポロジー等、任意のトポロジーであってもよい。
【０２３１】
また、ハッシュ値の衝突上限数は、パケット転送装置のハードウェア性能、パケット容量（サイズ）、帯域、パケット到着頻度、及びサービス品質等に基づいて、管理者によって任意の値に設定されるものであるので、衝突上限数は「１」に限定されない。
【０２３２】
また、衝突上限数は動的に設定されてもよい。例えば、監視制御装置１１は、パケット転送装置が受信するパケット容量及び各パケット転送装置へのパケット到着頻度等を監視し、例えば、パケット容量がある時点よりも増加した場合、衝突上限数を増加させてもよいし、パケット到着頻度がある時点よりも増加した場合、衝突上限数を増加させてもよい。なお、第３実施形態のようにラベル割当部１１５が各パケット転送装置に備わる場合には、各パケット転送装置が衝突上限数を動的に設定する。
【０２３３】
また、第１〜第３実施形態では、転送制御テーブル（クロスコネクトテーブル）から転送方法を取得するためにハッシュ関数を用いる方法を説明したが、他の検索方法を用いてもよい。
【０２３４】
また、他の検索方法としては、Ｂｉｎａｒｙ Ｔｒｅｅ（２分木）等のツリー状データ構造に基づく検索アルゴリズムを用いることができる。当該検索処理に要する時間の最大値は、ツリーの深さと強い正の相関関係があるので、検索処理の負荷として、ツリーの深さを用いる事ができる。
【０２３５】
この検索処理を以下に具体的に説明する。
【０２３６】
例えば、ラベル割当部１１５及びパケット転送装置は、２分探索木によるデータ構造で転送制御識別子を転送方法と関連付けて管理しておき、２分探索木に用いる２分探索アルゴリズムを用いて、検索対象の転送制御識別子と一致する転送制御識別子を検索する方法がある。
【０２３７】
この方法について、図２６を用いて説明する。
【０２３８】
図２６は、本発明の転送制御識別子を管理するための２分探索木によるデータ構造の説明図である。
【０２３９】
図２６は、転送制御識別子としてラベル値「２００」、「２１０」、「２１５」、「２２０」、「２３０」、 「２４０」、及び 「２５０」が割り当てられている場合の２分探索木によるデータ構造を示す。
【０２４０】
ラベル割当部１１５及びパケット転送装置は、図２６に示す２分探索木によるデータ構造を、ハッシュテーブル１１６２及び２２３３の代わりに記憶する。
【０２４１】
なお、図２６に示すツリー状のデータ構造では、最上部のノード「２３０」から検索されるので、ツリーの深さ（図２６では４段）がラベル割当部１１５及びパケット転送装置にかかる検索処理負荷となるため、ツリーの深さが検索処理にかかる時間となる。
【０２４２】
パケット転送装置の検索処理にかかる時間の上限値を保証するため、管理者は、ツリーの深さの上限値をシステム規定パラメータテーブル５２に登録する。
【０２４３】
新たなラベルを割り当てる場合の処理について説明する。
【０２４４】
図１５Ａにおいて、ラベル割当部１１５は、ステップ９０２の処理で、ラベル割当要求を受け取った場合、ステップ９０２１の処理で、割当可能ラベルから任意のラベルを割当候補ラベルとして選択する。
【０２４５】
そして、衝突検出部１１６は、割当候補ラベル及び割当済のラベルのツリー深さが最短となるように、２分探索木によるデータ構造を生成する。そして、衝突検出部１１６は、生成した２分探索木によるデータ構造のツリー深さを、ラベル割当部１１５に通知する。
【０２４６】
ラベル割当部１１５は、通知されたツリーの深さがシステム規定パラメータテーブル５２に登録された上限値以下であれば、当該割当候補ラベルを経路管理部１１１に通知し、
通知されたツリーの深さがシステム規定パラメータテーブル５２に登録された上限値よりも大きければ、割当可能ラベルから他のラベルを割当候補ラベルとして選択し、上述の処理を再度実行する。
【０２４７】
例として、システム規定パラメータテーブル５２に登録された、ツリーの深さの上限値が４である場合を仮定した場合の処理を説明する。
【０２４８】
新たに割り当てようとするラベル値が２３５である場合、該ラベル値は図２６に示すラベル値２４０の左側の子として格納される為、ツリー上の深さは３となり、上限値４以下であるため当該割当候補ラベルを経路管理部１１１に通知する。
【０２４９】
新たに割り当てようとするラベル値が２１２である場合、該ラベル値は図２６に示すラベル値２１５の左側の子として格納される為、ツリー上の深さは４となり、上限値４以上となるため、割り当て可能ラベルから他のラベルを割当て候補ラベルとして選択し直す。
【０２５０】
以上のように、ツリー状のデータ構造により転送制御識別子を管理する場合には、ツリーの深さを検索処理の負荷として用いることができる。
【０２５１】
また更に、転送制御テーブルを検索する方法としては、上述したハッシュ関数及びツリー状のデータ構造に基づく検索方法以外の方法を用いることができる。例えば、IETF RFC4981, "Survey of Research towards Robust Peer-to-Peer Networks: Search Methods"に示される各種検索方法を用いることができ、これらの検索方法に応じた検索処理時間を検索処理の負荷に用いることができる。
【０２５２】
第１〜第３実施形態では、パケット転送装置に入力されたパケットを転送経路に関する識別子であるＭＰＬＳラベル値を転送制御識別子として用いた場合に説明したが、転送制御識別子は、各パケット転送装置内で一意であって、パケット転送装置に入力されたパケットの転送方法を決定するためのものであれば、他のものであってもよい。
【０２５３】
転送制御識別子の他の例としては、例えば、ＱｏＳに関する識別子、及び警報転送に関する識別子がある。
【０２５４】
ＱｏＳに関する識別子は、パケット転送装置に入力されたパケットの出力インタフェースにおける出力キューの優先度を決定するための識別子である。
【０２５５】
ＱｏＳに関する識別子は、ＱｏＳに関する転送制御識別子は、IETF, RFC2475, "An Architecture for Differentiated Services"の2.3節、"Traffic Classification and Conditioning"の処理において参照される識別子、IETF, RFC1633, "Integrated Services in the Internet Architecture: an Overview"の4.1節Basic Functionsの処理において参照される識別子等であり、フロー識別情報及び転送廃棄優先制御情報の少なくとも一方を含む。
【０２５６】
フロー識別情報は、ＭＡＣアドレス、Ｅｔｈｅｒｔｙｐｅ、ＩＰアドレス、ＴＣＰ／ＵＤＰのポート番号、ＩＰｖ６のフローラベルの少なくとも一つである。また、転送廃棄優先制御情報は、ＩＰヘッダ及びＭＰＬＳヘッダのＤＳＣＰ／ＴＯＳ、並びにＬ−ＬＳＰのラベル値の少なくとも一つである。
【０２５７】
警報転送に関する識別子は、パケット転送装置がイーサＯＡＭフレームを終端させるか否かを判定するために当該フレームに含まれるＭＥＧレベル等である。
【０２５８】
転送経路に関する識別子は、宛先情報、コネクション識別子、トレイル識別子、ネットワーク識別子、及び制御フラグ等である。
【０２５９】
宛先情報は、例えば、ＭＡＣアドレス及びＩＰアドレス等である。コネクション識別子は、ＡＴＭのＶＰＩ（Virtual Path Identifier）／ＶＣＩ（Virtual Channel Identifier）、及びフレームリレーのＤＬＣＩ（Data-Link Connection Identifier）である。
【０２６０】
ネットワーク識別子は、ＶＬＡＮ ＩＤ、ＰＢＢ（IEEE802.11ａｈ Provider Backbone Bridge）におけるＳ−ＴＡＧ／Ｃ−ＴＡＧ／Ｉ−ＳＩＤを含む拡張ＶＬＡＮ ＩＤ等である。
【０２６１】
制御フラグは、ＩＰヘッダのルータアラート、及びＭＰＬＳのルータアラートラベル等である。
【０２６２】
第１〜第３実施形態では、一つの種別（ＭＰＬＳラベル値）の転送制御識別子をネットワークシステムで用いる例について説明したが、複数の種別の転送制御識別子をネットワークシステムで用いてもよい。
【０２６３】
例えば、転送制御識別子として、ＭＰＬＳラベル値に代表される転送経路に関する転送識別子及びＱｏＳに関する転送制御識別子の２種類を用いる場合について説明する。
【０２６４】
この場合、ラベル割当部１１５及び転送宛先制御部２２３は、転送制御識別子の識別子ごとに、転送制御識別子に対応する転送方法の検索方法を異ならせてもよい。
【０２６５】
例えば、一方の種別の転送制御識別子にはハッシュ値を用いて転送方法を検索し、他方の種別の転送制御識別子にはツリー状のデータ構造を用いて転送方法を検索してもよい。
【０２６６】
また、一方の種別の転送制御識別子の転送方法の検索に用いるハッシュ関数と他方の種別の転送制御識別子の転送方法の検索に用いるハッシュ関数とを異ならせてもよい。
【０２６７】
また、ラベル割当部１１５及び転送宛先制御部２２３は、複数の種別の転送制御識別子で同じ転送方法の検索方式を用いてもよい。
【０２６８】
なお、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した意味ではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０２６９】
１ パケットネットワーク
１１ 監視制御装置
１１１ 経路管理部
１１２ 通信部
１１３ クロスコネクトテーブル
１１４ パス経路テーブル
１１５ ラベル割り当て部
１１５１ 管理部
１１５２ 割当済ラベルテーブル
１１６ 衝突検出部
１１６１ ハッシュ生成部
１１６２ ハッシュテーブル
１１７ 通信路確立要求部
２１〜２４ パケット転送装置
２１１、２２１、２３１、２４１ 制御部
２１２、２２２、２３２、２４２ ＳＷ処理部
２２３ 転送宛先制御部
２２３１ 管理部
２２３２ クロスコネクトテーブル
２２３３ ハッシュテーブル
２２３４ ハッシュ生成部
２２４ パケット転送部
２２４１ パケット転送制御部
２２４２ 受信パケット解析部
２２４３ パケットスイッチ部
２２４４ 送信パケット生成部
３１〜３５ リンク回線
４１〜４５ ルータ
５２ システム規定パラメータテーブル
【技術分野】
【０００１】
本発明は、複数のパケット転送装置を備えるネットワークシステムに関し、特に、パケット転送装置が転送方法を決定するための転送制御識別子を割り当てるネットワークシステムに関する。
【背景技術】
【０００２】
パケット転送装置は、自身に入力されたパケットからヘッダを取り出し、ヘッダに含まれる転送制御識別子をキーとして、転送制御テーブルを検索することによって、入力されたパケットの転送方法を決定する。
【０００３】
例えば、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ Ｌａｂｅｌ Ｓｗｉｔｃｈｉｎｇ）網におけるパケット転送装置は、パケットのヘッダに含まれるラベル値をキーとして、ＭＰＬＳクロスコネクトテーブルを検索する。これによって、パケット転送装置は、パケット転送先の方路及び新たなラベル値を決定し、決定したラベル値をヘッダに格納した上で、決定した方路に向けてパケットを送信する。パケット転送先の方路はパケット毎に異なるため、パケット転送装置は、パケットが入力されるたびに、入力されたパケットをキーとしてＭＰＬＳクロスコネクトテーブルを検索しなければならない。
【０００４】
ＭＰＬＳクロスコネクトテーブルのエントリ数は、当該ＭＰＬＳクロスコネクトテーブルを備えるパケット転送装置が収容するパスの本数が多いほど多くなる。また、パケット転送装置のＭＰＬＳクロスコネクトテーブルの検索頻度はパケットの到着頻度が高いほど高くなる。したがって、多くのパスを収容するパケット転送装置、又は、高速な通信インタフェースを備えるパケット転送装置では、転送制御テーブル（例えば、ＭＰＬＳクロスコネクトテーブル）の検索処理の効率化が必要である。
【０００５】
転送制御テーブルの検索処理の効率化する方法として、Ｂ−Ｔｒｅｅ等のツリー構造を用いて転送制御テーブルを検索する方法が知られている。このツリー構造を用いる検索方法による転送制御テーブルの検索時間は、理想的には転送制御テーブルの登録エントリ数の対数時間となるが、転送制御テーブルに登録されている転送制御識別子の分布によっては、リニアサーチによる検索時間と同等まで低下する。
【０００６】
ハッシュ関数を用いて転送制御テーブルを検索する方法では、ハッシュ値の衝突（Ｃｏｌｌｉｓｉｏｎ）の発生によって、検索処理の効率が低下したり、検索が失敗することが知られている。ハッシュ値が衝突した場合の問題を解決する技術が知られている（例えば、特許文献１及び特許文献２参照）。
【０００７】
特許文献１には、「複数個のハッシュ表を含み、その各々が異なった計算されたインデックスで同時にアクセスされる」ことによって、転送エントリの検索を実現するネットワークスイッチが開示されている。
【０００８】
特許文献２には、「ハッシュテーブル形式の各種プロトコルテーブルの検索時間を短縮できるＩＰアドレス動的割り当て装置」が開示されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特表２００３−５１０９６３号公報
【特許文献２】特開２０００−２７８３２２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したように、ハッシュ値を使用して転送制御テーブルを検索する場合において、ハッシュ値の衝突が発生した場合の対処方式がいくつか知られている。しかしながら、いずれの対処方式を用いても、転送制御テーブルの検索が失敗してしまうか、転送制御テーブルの検索効率が低下してしまうという問題があった。
【００１１】
例えば、Ｃｈａｉｎｅｄ Ｈａｓｈ Ｍｅｔｈｏｄでは、ハッシュ値が同じになるデータをリスト形式で管理するため、ハッシュ値が同じになるデータが多くなり、リスト長が長くなるにつれて、処理効率は低下する。
【００１２】
特許文献１に記載された技術では、ハッシュ値の衝突による処理効率の低下を防止することによって検索処理時間を短縮できるが、検索処理時間の上限値を保証できない。ここで、パケット転送装置は、検索処理時間がパケット到着間隔を超過してしまうと、自身に到着したパケットを処理できなくなり、パケットを消失してしまう。したがって、ネットワークの通信品質を保証するためには、パケット転送装置の検索処理時間の上限値を保証することが必要となる。
【００１３】
以上より、本発明は、パケット転送装置の転送制御テーブルの検索処理時間の上限値を保証し、転送制御識別子の検索処理の効率を向上させるネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の代表的な一例を示せば、複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、前記パケット転送装置は、前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索部と、前記転送制御テーブル検索手段によって検索された前記転送方法で前記パケットを転送するパケット転送部と、を備え、前記ネットワークシステムは、前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索部の検索負荷を算出する検索負荷算出部と、前記検索負荷算出部によって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とする。
【００１５】
なお、転送制御識別子は、パケットの転送経路に関する転送制御識別子、ＱｏＳに関する転送制御識別子、及び警報転送に関する転送制御識別子の少なくとも一つを含む。
【００１６】
転送経路に関する転送制御識別子には、宛先情報、コネクション識別子、トレイル識別子、ネットワーク識別子、及び制御フラグ等である。
【００１７】
宛先情報は、例えば、ＭＡＣアドレス及びＩＰアドレス等である。コネクション識別子は、ＡＴＭのＶＰＩ（Virtual Path Identifier）／ＶＣＩ（Virtual Channel Identifier）、及びフレームリレーのＤＬＣＩ（Data-Link Connection Identifier）である。
【００１８】
ネットワーク識別子は、ＶＬＡＮ ＩＤ、ＰＢＢ（IEEE802.11ａｈ Provider Backbone Bridge）におけるＳ−ＴＡＧ／Ｃ−ＴＡＧ／Ｉ−ＳＩＤを含む拡張ＶＬＡＮ ＩＤ等である。
【００１９】
制御フラグは、ＩＰヘッダのルータアラート、及びＭＰＬＳのルータアラートラベル等である。
【００２０】
ＱｏＳに関する識別子は、具体的には、フロー識別情報及び転送廃棄優先制御情報の少なくとも一方である。フロー識別情報は、ＭＡＣアドレス、Ｅｔｈｅｒｔｙｐｅ、ＩＰアドレス、ＴＣＰ／ＵＤＰのポート番号、ＩＰｖ６のフローラベルの少なくとも一つである。また、転送廃棄優先制御情報は、ＩＰヘッダ及びＭＰＬＳヘッダのＤＳＣＰ／ＴＯＳ、並びにＬ−ＬＳＰのラベル値の少なくとも一つである。
【００２１】
警報転送に関する転送制御識別子とは、イーサＯＡＭフレームに含まれるＯＡＭ種別等の情報を含む。
【００２２】
また、転送制御テーブル検索部の検索方法は、ハッシュ関数に依らず、ツリー状のデータ構造を用いてもよい。この場合、検索処理の負荷の度合いはツリーの深さである。
【発明の効果】
【００２３】
本発明によれば、パパケット転送装置の転送制御テーブルの検索処理時間の上限値を保証でき、転送制御識別子の検索処理の効率を向上させることができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１実施形態のネットワークシステムの構成図である。
【図２】本発明の第１実施形態のパケット転送装置のインタフェース部に付与されるインタフェース名称の説明図である。
【図３】本発明の第１実施形態のラベル割当部の構成を示すブロック図である。
【図４】本発明の第１実施形態のスイッチ処理部の構成を示すブロック図である。
【図５】本発明の第１実施形態の監視制御装置のハードウェア構成を示すブロック図である。
【図６】本発明の第１実施形態のパス経路テーブルの説明図である。
【図７Ａ】本発明の第１実施形態の監視制御装置に記憶されるクロスコネクトテーブルの説明図である。
【図７Ｂ】本発明の第１実施形態のパケット転送装置に記憶されるクロスコネクトテーブルの説明図である。
【図８】本発明の第１実施形態の割当済ラベルテーブルの説明図である。
【図９】本発明の第１実施形態のあるパケット転送装置のハッシュ生成部によるハッシュ演算例の説明図である。
【図１０】本発明の第１実施形態の監視制御装置の衝突検出部のハッシュ生成部によるハッシュ演算例の説明図である。
【図１１】本発明の第１実施形態のパケット転送装置のハッシュテーブルの説明図である。
【図１２】本発明の第１実施形態の衝突検出部のハッシュテーブルの説明図である。
【図１３】本発明の第１実施形態のパケットネットワークで通信されるＭＰＬＳパケットの説明図である。
【図１４】本発明の第１実施形態のシステム規定パラメータテーブルの説明図である。
【図１５Ａ】本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置及びパケット転送装置の前半のシーケンス図である。
【図１５Ｂ】本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置及びパケット転送装置の後半のシーケンス図である。
【図１６】本発明の第１実施形態の新たなパスを確立する場合の経路管理部によって実行される処理のフローチャートである。
【図１７】本発明の第１実施形態の新たなパスを確立する場合のラベル割当部によって実行される処理のフローチャートである。
【図１８】本発明の第１実施形態の新たなパスを確立する場合の衝突検出部によって実行される処理のフローチャートである。
【図１９】本発明の第１実施形態の新たなパスを確立する場合のパケット転送装置の転送宛先制御部２２３によって実行される処理のフローチャートである。
【図２０】本発明の第１実施形態のパケット転送装置によるパケット転送処理のフローチャートである。
【図２１】本発明の第１実施形態のパケット転送装置のハッシュテーブルの説明図である。
【図２２】本発明の第１実施形態の衝突検出部１１６のハッシュテーブルの説明図である。
【図２３】本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブルの説明図である。
【図２４】本発明の第２実施形態のネットワークシステムの構成図である。
【図２５】本発明の第３実施形態のネットワークシステムの構成図である。
【図２６】本発明の転送制御識別子を管理するための２分探索木によるデータ構造の説明図である。
【発明を実施するための形態】
【００２５】
（第１実施形態）
以下、本発明の第１実施形態を図１〜図２３を用いて説明する。
【００２６】
図１は、本発明の第１実施形態のネットワークシステムの構成図である。
【００２７】
ネットワークシステムは、パケット転送装置Ａ２１〜Ｄ２４（以下、総称する場合、パケット転送という）及びリンク回線３１〜３５によって構成されるパケットネットワーク１、及び、パケット転送装置を監視する監視制御装置１１を備える。
【００２８】
監視制御装置１１は、ルータ装置４１〜４５等によって構成される制御用ネットワーク回線によってパケット転送装置と接続される。
【００２９】
パケット転送装置は、パケットを入出力するインタフェース部（２１ａ〜２１ｈ、２２ａ〜２２ｄ、２３ａ〜２３ｄ、及び２４ａ〜２４ｈ）、自身に入力されたパケットの出力先となるインタフェース部を切り替えるスイッチ処理部（ＳＷ処理部）（２１２、２２２、２３２、及び２４２）、及び、パケット転送装置の各部を制御する制御部（２１１、２２１、２３１、及び２４１）を備える。
【００３０】
図１では、パケット転送装置Ａ２１のインタフェース部２１ａとパケット転送装置Ｂ２２のインタフェース部２２ａとがリンク回線３１によって接続される。パケット転送装置Ａ２１のインタフェース部２１ｂとパケット転送装置Ｃ２３のインタフェース部２３ｂとがリンク回線３２によって接続される。パケット転送装置Ｂ２２のインタフェース部２２ｃとパケット転送装置Ｄ２４のインタフェース部２４ａとがリンク回線３３によって接続される。パケット転送装置Ｄ２４のインタフェース部２４ｂとパケット転送装置Ｃ２３のインタフェース部２３ｃとがリンク回線３４によって接続される。パケット転送装置Ｂ２２のインタフェース部２２ｄとパケット転送装置Ｃ２３のインタフェース部２３ａとがリンク回線３５によって接続される。
【００３１】
監視制御装置１１は、通信路確立要求部１１７、経路管理部１１１、通信部１１２、クロスコネクトテーブル１１３、パス経路テーブル１１４、及びラベル割当部１１５を備える。
【００３２】
通信路確立要求部１１７は通信路（パス）の確立を要求する。経路管理部１１１は、パケットネットワーク１内の経路制御を管理する。通信部１１２は、パケット転送装置と通信する。
【００３３】
クロスコネクトテーブル１１３は、パケット転送装置に入力されたパケットの転送方法を管理する転送制御テーブルの一種であり、ここでは、パケット転送装置ごとのＭＰＬＳクロスコネクト状態を管理するテーブルである。なお、クロスコネクトテーブル１１３の詳細は、図７Ａで説明する。
【００３４】
パス経路テーブル１１４は、パケットネットワーク１内のパス経路を管理するテーブルであり、図６で詳細を説明する。
【００３５】
ラベル割当部１１５は、転送制御識別子となるＭＰＬＳラベル値を各パケット転送装置に割り当てる。ラベル割当部１１５は、ＭＰＬＳラベル値のハッシュ値の衝突度合いを検出する衝突検出部１１６を備える。ラベル割当部１１５の詳細は、図３で説明する。
【００３６】
図１に示すパケットネットワーク１にはパスＰ１及びパスＰ２が確立されている。
【００３７】
パスＰ１について説明する。
【００３８】
パケット転送装置Ａ２１のインタフェース部２１ｃから入力されたパケットがインタフェース部２１ａからリンク回線３１に出力される。このパケットは、パケット転送装置Ｂ２２のインタフェース部２２ａに入力され、インタフェース部２２ｃからリンク回線３３に出力される。そして、このパケットは、パケット転送装置Ｄ２４のインタフェース部２４ａに入力され、インタフェース部２４ｈから出力される。
【００３９】
次に、パスＰ２について説明する。
【００４０】
パケット転送装置Ａ２１のインタフェース部２１ｅから入力されたパケットがインタフェース部２１ａからリンク回線３１に出力される。このパケットは、パケット転送装置Ｂ２２のインタフェース部２２ａに入力され、インタフェース部２２ｄからリンク回線３５に出力される。そして、このパケットは、パケット転送装置Ｃ２３のインタフェース部２３ａに入力され、インタフェース部２３ｄからリンク回線３４に出力される。そして、このパケットは、パケット転送装置Ｄ２４のインタフェース部２４ｂに入力され、インタフェース部２４ｇから出力される。
【００４１】
ここで、監視制御装置１１とパケット転送装置との接続について説明する。
【００４２】
パケット転送装置Ａ２１の制御部２１１はルータ装置４１に接続され、パケット転送装置Ｂ２２の制御部２２１はルータ装置４２に接続され、パケット転送装置Ｃ２３の制御部２３１はルータ装置４３に接続され、パケット転送装置Ｄ２４の制御部２４１はルータ装置４４に接続される。これらのルータ装置４１〜４４はルータ装置４５に接続され、ルータ装置４５は監視制御装置１１の通信部１１２に接続される。
【００４３】
このように、監視制御装置１１と各パケット転送装置Ａ２１〜Ｄ２４とが接続される。
【００４４】
図２は、本発明の第１実施形態のパケット転送装置のインタフェース部に付与されるインタフェース名称の説明図である。
【００４５】
インタフェース符号はパケット転送装置のインタフェース部の図１に示す符号である。インタフェース名称は、説明を簡単にするために、各インタフェース部に付与した名称であり、例えば、インタフェース部２１ａのインタフェース名称はＩＦ＿Ａ１という。
【００４６】
図３は、本発明の第１実施形態のラベル割当部１１５の構成を示すブロック図である。
【００４７】
ラベル割当部１１５は、管理部１１５１、割当済ラベルテーブル１１５２、及び衝突検出部１１６を備える。
【００４８】
なお、監視制御装置１１は、監視するパケット転送装置の数だけラベル割当部１１５を備える。一つのラベル割当部１１５は一つのパケット転送装置に対応するものとする。
【００４９】
管理部１１５１は、ラベル割当部１１５を管理及び制御する。割当済ラベルテーブル１１５２は、すでに割り当てられたラベルをパケット転送装置ごとに管理するテーブルであり、図８で詳細を説明する。
【００５０】
衝突検出部１１６は、パケット転送装置ごとに転送制御識別子のハッシュ値の衝突度合いを検出するもので、ハッシュ生成部１１６１及びハッシュテーブル１１６２を備える。
【００５１】
ハッシュ生成部１１６１は、パケット転送装置に備わる図４に示すハッシュ生成部２２３４と同じハッシュ関数によってハッシュ値を生成する。すなわち、ハッシュ生成部１１６１は、パケット転送装置に備わる図４に示すハッシュ生成部２２３４が生成するハッシュ値の分布と同じハッシュ値の分布を生成する。
【００５２】
ハッシュテーブル１１６２は、パケット転送装置ごとに割り当てられたラベルと当該ラベルのハッシュ値との対応関係を管理するテーブルであり、図１２で詳細を説明する。
【００５３】
図４は、本発明の第１実施形態のスイッチ処理部２２２の構成を示すブロック図である。
【００５４】
スイッチ処理部２２２は、転送宛先制御部２２３、及びパケット転送部２２４を備える。
【００５５】
まず、転送宛先制御部２２３について説明する。
【００５６】
転送宛先制御部２２３は、パケット転送制御装置のインタフェース部に入力されたパケットを出力するインタフェース部及び当該パケットに付与するラベルを特定する。転送宛先制御部２２３は、管理部２２３１、クロスコネクトテーブル２２３２、ハッシュテーブル２２３３、及びハッシュ生成部２２３４を備える。
【００５７】
管理部２２３１は、クロスコネクトテーブル２２３２、ハッシュテーブル２２３３、及びハッシュ生成部２２３４を制御する。
【００５８】
クロスコネクトテーブル２２３２は、ＭＰＬＳクロスコネクト状態を管理するテーブルである。具体的には、クロスコネクトテーブル２２３２は、入力されたパケットに含まれる入力ラベル又はパケットが入力されたインタフェース部（入力インタフェース）と、当該パケットを出力するインタフェース（出力インタフェース）及び当該パケットに付与される出力ラベルとを対応付けて管理する。なお、クロスコネクトテーブル２２３２の詳細は、図７Ｂで説明する。
【００５９】
ハッシュテーブル２２３３は、ハッシュ生成部２２３４が生成した入力ラベルのハッシュ値をキーとしてクロスコネクトテーブル２２３２を検索するために用いられるテーブルであり、入力ラベルのクロスコネクト情報と当該入力ラベルのハッシュ値との対応関係を管理する。なお、ハッシュテーブル２２３３の詳細は、図１２で詳細を説明する。
【００６０】
ハッシュ生成部２２３４は、入力ラベルのハッシュ値を生成する。
【００６１】
次に、パケット転送部２２４について説明する。
【００６２】
パケット転送部２２４は、入力インタフェースに入力されたパケットを転送宛先制御部２２３に渡し、転送宛先制御部２２３によって特定された出力ラベルをパケットに付与し、当該パケットを転送宛先制御部２２３によって特定された出力インタフェース部から出力する。パケット転送部２２４は、パケット転送制御部２２４１、受信パケット解析部２２４２、パケットスイッチ部２２４３、及び送信パケット生成部２２４４を備える。
【００６３】
パケット転送制御部２２４１は、受信パケット解析部２２４２、パケットスイッチ部２２４３、及び送信パケット生成部２２４４を制御する。
【００６４】
受信パケット解析部２２４２は、入力インタフェースに入力されたパケットを解析し、解析したパケットの入力ラベル及び入力インタフェース識別子を少なくとも含む情報を転送宛先制御部２２３に渡すとともに、解析したパケットをパケットスイッチ部２２４３に渡す。
【００６５】
パケットスイッチ部２２４３はパケットのクロスコネクト処理を実行する。具体的には、パケットスイッチ部２２４３は、受信パケット解析部２２４２から渡されたパケットに、転送宛先制御部２２３によって特定された出力ラベルを付与し、送信パケット生成部２２４４に渡す。
【００６６】
送信パケット生成部２２４４は、パケットスイッチ部２２４３から渡されたパケットを転送宛先制御部２２３によって特定された出力インタフェースに渡す。
【００６７】
なお、図４では、パケット転送装置Ｂ２２のスイッチ処理部２２２について説明したが、他のパケット転送装置Ａ２１、Ｃ２３、及びＤ２４のスイッチ処理部も同じ構成である。
【００６８】
図５は、本発明の第１実施形態の監視制御装置１１のハードウェア構成を示すブロック図である。
【００６９】
監視制御装置１１は、メモリ１１ａ、ＣＰＵ１１ｂ、二次記憶装置１１ｃ、及び通信インタフェース１１ｄ等のハードウェアによって構成される。メモリ１１ａには、ＣＰＵ１１ｂが実行するプログラム１１ｅ、及びＣＰＵ１１ｂが利用するデータ１１ｆが必要に応じて格納される。
【００７０】
例えば、通信路確立要求部１１７、経路管理部１１１、通信部１１２、ラベル割当部１１５の機能は、監視制御装置１１のＣＰＵ１１ｂがこれらに対応するプログラムを実行することによって実現される。
【００７１】
図６は、本発明の第１実施形態のパス経路テーブル１１４の説明図である。
【００７２】
パス経路テーブル１１４は、パケットネットワーク１に確立されたパスを管理する。パス経路テーブル１１４は、パスＩＤ１１４１及びパス経路１１４２を含む。
【００７３】
パスＩＤ１１４１には、パケットネットワーク１に確立されたパスの一意な識別子が登録される。パス経路１１４２には、パスが通る順にパケット転送装置のインタフェース部のインタフェース名称が登録される。
【００７４】
図６に示すパス経路テーブル１１４には、図１で説明したパスＰ１及びＰ２が登録される。なお、パスＰ１及びＰ２の経路については図１で説明したので説明を省略する。
【００７５】
図７Ａは、本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブル１１３の説明図である。
【００７６】
クロスコネクトテーブル１１３は、パス経路テーブル１１４によって管理されるパスが経由するパケット転送装置における入力インタフェース及び入力ラベルと出力インタフェース及び出力ラベルとの対応関係を示すクロスコネクト情報を管理する。
【００７７】
クロスコネクトテーブル１１３は、装置１１３１、入力ラベル１１３２、入力インタフェース１１３３、出力インタフェース１１３４、及び出力ラベル１１３５を含む。
【００７８】
装置１１３１には、パスが経由する各パケット転送装置の一意な識別子が登録される。入力ラベル１１３２には、入力ラベルのラベル値が登録される。入力インタフェース１１３３には、データが入力されるインタフェースの一意な識別子が登録される。
【００７９】
出力インタフェース１１３４には、入力されたパケットの出力先となるインタフェース部の一意な識別子が登録される。出力ラベル１１３５には、入力されたパケットに付与されるラベル値が登録される。
【００８０】
なお、ＭＰＬＳパケットネットワークでは、転送制御識別子としてＭＰＬＳラベル値を用いるが、パスの始点となるパケット転送装置に入力されるパケットにＭＰＬＳラベルは付与されず、また、パスの終点となるパケット転送装置が出力するパケットにＭＰＬＳラベルは付与されない。このため、図７Ａでは、パスＰ１の始点となるパケット転送装置Ａ２１のエントリの入力ラベル１１３２にはラベル値が登録されず、パスＰ１の終点となるパケット転送装置Ｄ２４のエントリの出力ラベル１１３５にはラベル値が登録されない。
【００８１】
また、パスの始点となるパケット転送装置と終点となるパケット転送装置との間の中間パケット転送装置、及び終点となるパケット転送装置は、入力されたパケットの出力インタフェース及び出力ラベルを入力インタフェースではなく入力ラベルによって決定する。このため、図７Ａでは、パスの中間パケット転送装置となるパケット転送装置Ｂ２２及び終点となるパケット転送装置Ｄ２４のエントリの入力インタフェース１１３３にはインタフェース部の識別子が登録されない。
【００８２】
図７Ｂは、本発明の第１実施形態のパケット転送装置に記憶されるクロスコネクトテーブル２２３２の説明図である。
【００８３】
パケット転送装置に記憶されるクロスコネクトテーブル２２３２には、監視制御装置１１に記憶されるクロスコネクトテーブル１１３に登録されたクロスコネクト情報のうち、当該パケット転送装置に対応するクロスコネクト情報が登録される。パケット転送装置は、自身に記憶されたクロスコネクトテーブル２２３２を監視制御装置１１からの指示に基づいて更新する。これについては、図１５Ｂ及び図１９で詳細を説明する。
【００８４】
クロスコネクトテーブル２２３２は、入力ラベル２２３２１、入力インタフェース２２３２２、出力インタフェース２２３２３、及び出力ラベル２２３２４を含む。
【００８５】
図７Ｂは、パケット転送装置Ｂ２２のクロスコネクトテーブル２２３２を一例として示す。
【００８６】
入力ラベル２２３２１は図７Ａに示す入力ラベル１１３２と同じであり、入力インタフェース２２３２２は図７Ａに示す入力インタフェース１１３３と同じであり、出力インタフェース２２３２３は図７Ａに示す出力インタフェース１１３４、及び出力ラベル２２３２４は図７Ａに示す出力ラベル１１３５と同じであるので、説明を省略する。
【００８７】
図８は、本発明の第１実施形態の割当済ラベルテーブル１１５２の説明図である。
【００８８】
割当済ラベルテーブル１１５２は、図３で説明したように、すでに割り当てられた入力ラベルを管理するテーブルである。
【００８９】
割当済ラベルテーブル１１５２は、入力ラベル１１５２１及び割当状況１１５２２を含む。
【００９０】
入力ラベル１１５２１には、すでに割り当てられた入力ラベルの値が登録される。割当状況１１５２２にはすでに割り当てられたことを示す「済」が登録される。
【００９１】
図８に示す割当済ラベルテーブル１１５２は、入力ラベル「２０１」〜「２０７」がすでに割り当てられたことを示す。
【００９２】
次に、図９及び図１０を用いてハッシュ演算例について説明する。
【００９３】
図９は、本発明の第１実施形態のあるパケット転送装置のハッシュ生成部２２３４によるハッシュ演算例２２３４１の説明図である。
【００９４】
ハッシュ生成部２２３４は、入力ラベルを入力値２２３４２としてハッシュ演算することによって、入力ラベルをハッシュ値２２３４３に変換する。
【００９５】
パケット転送装置で使用されるハッシュ関数は種々の関数が知られているが、本実施形態のパケット転送装置はいずれのハッシュ関数を使用してもよい。本実施形態では、説明の簡単にするため、ハッシュ生成部２２３４は、入力値の剰余を用いてハッシュ値を計算するものとする。具体的には、ハッシュ生成部２２３４は、式１を計算することによって入力値をハッシュ値に変換するものとする。
【００９６】
＜ハッシュ値＞＝（＜入力値＞−２００）ｍｏｄ６＋１・・・（式１）
例えば、図９に示すハッシュ演算例２２３４１では、入力値２２３４２「２０１」のハッシュ値２２３４３は「１」となる。
【００９７】
なお、入力値の剰余を用いたハッシュ値の算出方法において、接続されるリンク回線が多いパケット転送装置ほど、入力値を割る数を大きく設定したほうがよい。これは、接続されるリンク回線が多いパケット転送装置ほど、多くの入力ラベルが設定されるため、剰余の数が多いほどハッシュ値の衝突を防止できるためである。
【００９８】
図１０は、本発明の第１実施形態の監視制御装置１１の衝突検出部１１６のハッシュ生成部１１６１によるハッシュ演算例１１６１１の説明図である。
【００９９】
図１０にハッシュ演算例１１６１１を示すハッシュ生成部１１６１は、図９で説明したパケット転送装置のハッシュ生成部２２３４に対応するものである。
【０１００】
ハッシュ生成部１１６１は、入力ラベルを入力値１１６１２としてハッシュ演算することによって、入力ラベルをハッシュ値１１６１３に変換する。
【０１０１】
衝突検出部１１６のハッシュ生成部１１６１が使用するハッシュ関数は、パケット転送装置のハッシュ生成部２２３４が使用するハッシュ関数と同じである必要はないが、ハッシュ生成部１１６１が算出したハッシュ値の分布傾向は、ハッシュ生成部２２３４が算出したハッシュ値の分布傾向と同じである必要がある。このため、入力値の剰余を用いてハッシュ値を算出する方法の場合、ハッシュ生成部１１６１における剰余を算出するために入力値を割る数と、ハッシュ生成部２２３４における剰余を算出するために入力値を割る数とが同じであればよい。
【０１０２】
ハッシュ生成部１１６１は、式２を計算することによって入力値をハッシュ値に変換するものとする。
【０１０３】
＜ハッシュ値＞＝（＜入力値＞−２００）ｍｏｄ６＋２・・・（式２）
例えば、図１０に示すハッシュ演算例１１６１１では、入力値１１６１２「２０１」のハッシュ値２２３４３は「２」となる。
【０１０４】
なお、衝突検出部１１６は、パケット転送装置のハッシュ生成部２２３４に対応するハッシュ生成部１１６１を、パケット転送装置のハッシュ生成部２２３４の数だけ備える。
【０１０５】
図１１は、本発明の第１実施形態のパケット転送装置のハッシュテーブル２２３３の説明図である。
【０１０６】
ハッシュテーブル２２３３には、ハッシュ生成部２２３４によって算出された入力ラベルのハッシュ値と当該入力ラベルとの対応関係が格納される。
【０１０７】
ハッシュテーブル２２３３は、ハッシュ値２２３３１、ラベルＡ２２３３２、ラベルＢ２２３３３、及び、ラベルＣ２２３３４を含む。
【０１０８】
ハッシュ値２２３３１には、ハッシュ生成部２２３４が式１を計算することによって算出し得るハッシュ値（１〜６）が登録される。
【０１０９】
ラベルＡ２２３３２〜ラベルＣ２２３３４には、ハッシュ値に対応する入力ラベルが登録される。
【０１１０】
例えば、入力ラベル「２０１」及び「２０７」のハッシュ値「１」となるため、ハッシュテーブル２２３３のハッシュ値２２３３１「１」のエントリのラベルＡ２２３３２には「２０１」が登録され、ラベルＢ２２３３３には「２０７」が登録される。
【０１１１】
図１２は、本発明の第１実施形態の衝突検出部１１６のハッシュテーブル１１６２の説明図である。
【０１１２】
ハッシュテーブル１１６２には、ハッシュ生成部１１６１によって算出された入力ラベルのハッシュ値と当該入力ラベルとの対応関係が格納される。
【０１１３】
ハッシュテーブル１１６２は、ハッシュ値１１６２１、ラベルＡ１１６２２、ラベルＢ１１６２３、及び、ラベルＣ１１６２４を含む。ハッシュ値１１６２１は、図１１で説明したハッシュ値２２３３１と同じであるので説明を省略する。ラベルＡ１１６２２〜ラベルＣ１１６２４は、図１１で説明したラベルＡ２２３３２〜ラベルＣ２２３３４と同じであるので説明を省略する。
【０１１４】
なお、図１１及び図１２に示すハッシュテーブル２２３３及びハッシュテーブル１１６２はラベルＡ〜ラベルＣを含むので同一のハッシュ値となる入力ラベルを三つまで登録できるが、ハッシュテーブル２２３３及びハッシュテーブル１１６２に登録可能な同一のハッシュ値となる入力ラベルの数は三つに限定するものではない。
【０１１５】
図１３は、本発明の第１実施形態のパケットネットワーク１で通信されるＭＰＬＳパケット５１の説明図である。
【０１１６】
ＭＰＬＳパケット５１は、ヘッダ部５１１及びデータ部５１２によって構成される。ヘッダ部５１１は転送制御識別子であるラベル５１１１を含む。
【０１１７】
図１４は、本発明の第１実施形態のシステム規定パラメータテーブル５２の説明図である。
【０１１８】
システム規定パラメータテーブル５２には、新たなラベルを割り当てる場合のパケット転送装置ごとのポリシーに関する情報が登録される。システム規定パラメータテーブル５２は、監視制御装置１１の管理者によって入力デバイスを介して監視制御装置１１に入力され、監視制御装置１１のメモリ１１ａに保持される。
【０１１９】
システム規定パラメータテーブル５２は項目５２１及び値５２２を含む。項目５２１には、衝突上限数を識別するための情報及びラベル範囲を識別するための情報が登録される。衝突上限数は同一のハッシュ値となる入力ラベル上限数であり、ラベル範囲は使用可能なラベル値の範囲である。衝突上限数のエントリの値５２２には「１」が登録され、ラベル範囲のエントリの値５２２には「１００−９９９」が登録される。
【０１２０】
次に、パスＰ１を新たに確立する場合の監視制御装置１１及びパケット転送装置のシーケンスについて、図１５Ａ及び図１５Ｂを説明する。
【０１２１】
図１５Ａは、本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置１１及びパケット転送装置の前半のシーケンス図である。
【０１２２】
通信路確立要求部１１７は、パケット転送装置間で通信路（パス）を確立する必要がある場合、パス開通要求を経路管理部１１１に入力する（９０１）。図１５Ａでは、通信路確立要求部１１７は、図１に示すパスＰ１を確立するためのパス開通要求を経路管理部１１１に入力する。当該パス開通要求には、始点となるパケット転送装置のインタフェース部、終点となるパケット転送装置のインタフェース部、及びパス種別等がパス開通条件として含まれる。
【０１２３】
経路管理部１１１は、パス開通要求が入力された場合、入力されたパス開通要求に含まれるパス開通条件を取得する（９０１１）。そして、経路管理部１１１は、取得した始点及び終点に基づいて任意のアルゴリズム（例えば、ダイクストラ法）を用いてパス経路を決定し、決定したパス経路をパス経路テーブル１１４に登録するとともに、決定したパス経路に基づいてクロスコネクトテーブル１１３を更新する（９０１２）。
【０１２４】
クロスコネクトテーブル１１３の更新方法について説明する。
【０１２５】
経路管理部１１１は、図７Ａに示すクロスコネクトテーブル１１３に装置１１３１にパスＰ１が経由するパケット転送装置Ａ２１、Ｂ２２及びＤ２４の識別子が登録される三つのエントリを新たに追加する。
【０１２６】
そして、経路管理部１１１は、パスＰ１の始点となるパケット転送装置Ａ２１のエントリの入力ラベル１１３２にラベル値を登録せず、入力インタフェース１１３３にパス開通条件に含まれる始点となるインタフェース部の一意な識別子（ＩＦ＿Ａ３）を登録し、出力インタフェース１１３４にパス経路に含まれるパケット転送装置Ａ２１の出力インタフェースの一意な識別子（ＩＦ＿Ａ１）を登録する。なお、ステップ９０１２の処理の段階では、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に割り当てられるラベル値が決定されていないので、経路管理部１１１は、出力ラベル１１３５に何も登録しない。
【０１２７】
また、経路管理部１１１は、中間パケット転送装置Ｂ２２のエントリの入力インタフェース１１３３に何も登録せず、パス経路に含まれるパケット転送装置Ｂ２２の出力インタフェースの一意な識別子（ＩＦ＿Ｂ３）を出力インタフェース１１３４に登録する。なお、ステップ９０１２の処理の段階では、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に割り当てられるラベル値が決定されていないので、入力ラベル１１３２には何も登録されない。また、パケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３に割り当てられるラベル値が決定されていないので、出力ラベル１１３５には何も登録されない。
【０１２８】
さらに、経路管理部１１１は、パスＰ１の終点となるパケット転送装置Ｄ２４のエントリの入力インタフェース１１３３及び出力ラベル１１３５に何も登録せず、パス開通条件に含まれる終点となるインタフェース部の一意な識別子（ＩＦ＿Ｄ８）を出力インタフェース１１３４に登録する。なお、パケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３に割り当てられるラベル値が決定されていないので、入力ラベル１１３２には何も登録されない。
【０１２９】
以上によって、クロスコネクトテーブル１１３が更新される。
【０１３０】
パスＰ１は、パケット転送装置Ａ２１、パケット転送装置Ｂ２２、及びパケット転送装置Ｄ２４を経由するため、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１、及びパケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間のリンク回線３３で転送されるパケットに含まれるラベルを決定する必要がある。
【０１３１】
例えばパケット転送装置Ａ２１とパケット転送装置Ｂ２２との間で転送されるパケットのラベルを決定する場合、パケット転送装置Ｂ２２の入力ラベルを決定すれば、パケット転送装置Ａ２１の出力ラベルは当該入力ラベルになるので、本実施形態では、受信側のパケット転送装置Ｂ２２の入力ラベルを決定することによって、リンク回線３３のラベルを決定する。
【０１３２】
まず、経路管理部１１１は、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間のリンク回線３１に新たなラベルを割り当てる要求であるラベル割当要求を、パケット転送装置Ｂ２２に対応するラベル割当部Ｂ１１５に入力する（９０２）。
【０１３３】
ラベル割当部Ｂ１１５は、パケット転送装置Ｂ２２用のシステム規定パラメータテーブル５２のラベル範囲に登録された範囲のラベルのうち、パケット転送装置Ｂ２２用の割当済ラベルテーブル１１５２に登録されていないラベルであって、割当不可フラグが設定されていない割当可能ラベルを特定し、特定した割当可能ラベルから任意の一つのラベルを割当候補ラベルとして選択する（９０２１）。割当不可フラグは、ハッシュ値の衝突数が上限値よりも大きいと判定されたラベルに設定され、図１７に示すステップ８２８の処理で説明する。
【０１３４】
そして、ラベル割当部Ｂ１１５は、選択した割当候補ラベルのハッシュ値の衝突数の取得要求を衝突検出部Ｂ１１６に入力する（９０３）。
【０１３５】
衝突検出部Ｂ１１６は、衝突数の取得要求が入力された場合、入力された衝突数の取得要求の割当候補ラベルのハッシュ値をハッシュ生成部１１６１に算出させる（９０３１）。そして、衝突検出部Ｂ１１６は、ハッシュテーブル１１６２を参照し、算出したハッシュ値のエントリに登録された入力ラベルの数を衝突数として取得する（９０３２）。
【０１３６】
次に、衝突検出部Ｂ１１６は、ステップ９０３２の処理で取得した衝突数を、衝突数の取得要求の応答としてラベル割当部Ｂ１１５に入力する（９０４）。
【０１３７】
ラベル割当部Ｂ１１５は、衝突検出部Ｂ１１６から衝突数の取得要求に対する応答が入力された場合、入力された応答に含まれる衝突数と、パケット転送装置Ｂ２２用のシステム規定パラメータテーブル５２に登録された衝突上限数とを比較し、衝突数が衝突上限数よりも大きい場合、ステップ９０２１の処理に戻り、割当候補ラベルを再度選択する（９０４１及び９０５）。一方、ラベル割当部Ｂ１１５は、衝突数が衝突上限数以下である場合、割当候補ラベルを入力ラベルに割り当てることを決定し、当該ラベル値をラベル割当要求の応答として経路管理部１１１に入力する（９０６）。
【０１３８】
経路管理部１１１は、ラベル割当部Ｂ１１５からラベル値が入力された場合、入力されたラベル値を、クロスコネクトテーブル１１３のエントリのうちパケット転送装置Ａ２１のエントリ及びパケット転送装置Ｂ２２のエントリに登録する（９０６１）。
【０１３９】
具体的には、経路管理部１１１は、ステップ９０１２の処理で追加したエントリのうち、パケット転送装置Ａ２１のエントリの出力ラベル１１３５にラベル割当部１１５から入力されたラベル値を登録し、パケット転送装置Ｂ２２のエントリの入力ラベル１１３２にラベル割当部１１５から入力されたラベル値を登録する。
【０１４０】
次に、経路管理部１１１は、パケット転送装置Ｂ２２とパケット転送装置Ｄ２３との間に新たなラベルを割り当てる要求であるラベル割当要求を、パケット転送装置Ｄ２３に対応するラベル割当部Ｄ１１５に入力する（９０７）。
【０１４１】
なお、ステップ９０７１〜９１１１の処理は、ステップ９０２１〜９０６１の処理と同じであるので説明を省略する。
【０１４２】
これによって、監視制御装置１１側で、パケット転送装置Ａ２１とパケット転送装置Ｂ２２との間、及びパケット転送装置Ｂ２２とパケット転送装置Ｄ２４との間で転送されるパケットに含まれるラベルを決定することができる。
【０１４３】
図１５Ｂは、本発明の第１実施形態の新たなパスＰ１を確立する場合の監視制御装置１１及びパケット転送装置の後半のシーケンス図である。
【０１４４】
経路管理部１１１は、追加要求をパケット転送装置Ａ２１に送信する（９２１）。追加要求は、ステップ９０６１の処理で更新されたパケット転送装置Ａ２１用のクロスコネクトテーブル１１３のエントリをパケット転送装置Ａ２１のクロスコネクトテーブル２２３２に追加する要求であり、パケット転送装置Ａ２１用のクロスコネクトテーブル１１３で更新されたエントリ（入力ラベル、入力インタフェース、出力インタフェース、出力ラベル）をクロスコネクト情報として含む。
【０１４５】
パケット転送装置Ａ２１は、追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報に基づいて、クロスコネクトテーブル２２３２にエントリを追加し（９２１１）、追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信する（９２２）。
【０１４６】
次に、経路管理部１１１は、パケット転送装置Ｂ２２用のクロスコネクトテーブル１１３のエントリのうちステップ９０６１及び９１１１の処理で更新したエントリを、パケット転送装置Ｂ２２のクロスコネクトテーブル２２３２に追加する追加要求をパケット転送装置Ｂ２２に送信する（９２３）。
【０１４７】
パケット転送装置Ｂ２２は、追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報に基づいて、クロスコネクト情報に含まれる入力ラベルのハッシュ値をハッシュ生成部２２３４に算出させる（９２３１）。
【０１４８】
次に、パケット転送装置Ｂ２２は、受信した追加要求に含まれるクロスコネクト情報をクロスコネクトテーブル２２３２にエントリを追加するとともに、ステップ９２３１の処理で算出したハッシュ値と、ステップ９２３１の処理でクロスコネクトテーブル２２３２に追加したエントリに含まれる入力ラベル、出力インタフェース、及び出力ラベルとを対応付けた情報をハッシュテーブル２２３３に登録する（９２３２）。
【０１４９】
そして、パケット転送装置Ｂ２２は、ステップ９２３の処理で送信された追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信する（９２４）。
【０１５０】
次に、経路管理部１１１は、ステップ９１１１の処理で更新されたパケット転送装置Ｄ２４用のクロスコネクトテーブル１１３のエントリを、パケット転送装置Ｄ２４のクロスコネクトテーブル２２３２に追加する追加要求をパケット転送装置Ｄ２４に送信する（９２５）。
【０１５１】
追加要求を受信したパケット転送装置Ｄ２４が実行するステップ９２５１〜９２６の処理は、パケット転送装置Ｂ２２が実行するステップ９２３１〜９２５の処理と同じであるので、説明を省略する。
【０１５２】
経路管理部１１１は、パケット転送装置Ｄ２４から結果応答を受信すると、ステップ９０１の処理で入力されたパス開通要求に対してパスが開通したことを応答する（９７２）。
【０１５３】
以上によって、パスＰ１が経由するパケット転送装置Ａ２１、Ｂ２２、及びＤ２４に対して、入力されるパケットに含まれる入力ラベルのハッシュ値と、当該パケットを出力する出力インタフェース及び当該パケットを出力する場合に含める出力ラベルとを対応付けることができる。これによって、パケット転送装置Ｂ２２、及びパケット転送装置Ｄ２４は、入力ラベルのハッシュ値に基づいて出力インタフェース及び出力ラベルを検索できる。
【０１５４】
図１６は、本発明の第１実施形態の新たなパスを確立する場合の経路管理部１１１によって実行される処理のフローチャートである。
【０１５５】
まず、経路管理部１１１は、通信路確立要求部１１７から入力されたパス開通要求に含まれるパス開通条件を取得する（８１１）。ステップ８１１の処理は図１５Ａに示すステップ９０１１の処理に相当する。
【０１５６】
次に、経路管理部１１１は、取得したパス開通条件の始点及び終点に基づいてパス経路を決定する（８１２）。ステップ８１２の処理は図１５Ａに示すステップ９０１２の処理に相当する。なお、パス経路を決定するアルゴリズムは任意のアルゴリズムでよく、例えば、ダイクストラ法を使用する。
【０１５７】
次に、経路管理部１１１は、ステップ８１２の処理で決定されたパス経路に含まれるパケット転送装置間のリンクに新たなラベルを割り当てるラベル割当要求を、各パケット転送装置に入力する（８１３）。ラベル割当要求は、ラベルを割り当てるリンクの始点となる出力インタフェースの識別子、及び、当該リンクの終点となる入力インタフェースの識別子からなるラベル割当条件を含む。ステップ８１３の処理は図１５Ａに示すステップ９０２及び９０７の処理に相当する。
【０１５８】
次に、経路管理部１１１は、ステップ８１３の処理でラベル割当要求を送信したラベル割当部１１５から各リンクに割り当てられるラベル値を受信する（８１４）。ステップ８１４の処理は図１５Ａに示すステップ９０６及び９１１の処理に相当する。
【０１５９】
次に、経路管理部１１１は、ステップ８１４の処理で受信したラベル値に基づいてクロスコネクトテーブル１１３を更新する（８１５）。ステップ８１５の処理は図１５Ａに示すステップ９０６１及び９１１１の処理に相当する。
【０１６０】
次に、経路管理部１１１は、ステップ８１２の処理で決定されたパス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられたか否かを判定する（８１６）。
【０１６１】
ステップ８１６の処理で、パス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられていないと判定された場合、ステップ８１３の処理に戻る。
【０１６２】
一方、ステップ８１６の処理で、パス経路に含まれるすべてのリンクに対して新たなラベルが割り当てられたと判定された場合、経路管理部１１１は、当該パス経路上のすべてのパケット転送装置に対して、パケット転送装置のクロスコネクトテーブルに新たなエントリを追加する追加要求を送信し（８１７）、処理を終了する。ステップ８１７の処理は図１５Ｂに示すステップ９２１、９２３、及び９２５の処理に相当する。
【０１６３】
図１７は、本発明の第１実施形態の新たなパスを確立する場合のラベル割当部１１５によって実行される処理のフローチャートである。
【０１６４】
まず、ラベル割当部１１５は、経路管理部１１１によって入力されたラベル割当要求に含まれるラベル割当条件を取り出す（８２１）。
【０１６５】
次に、ラベル割当部１１５は、自身に対応するパケット転送装置用のシステム規定パラメータテーブル５２に登録されたラベル範囲から割当可能ラベルを特定し、特定した割当可能ラベルから任意の一つのラベルを割当候補ラベルとして選択する（８２２）。割当可能ラベルは、当該ラベル割当部１１５に対応するパケット転送装置用の割当済ラベルテーブル１１５２に登録されていないラベルであって、かつ割当不可フラグが設定されていないラベルである。ステップ８２２の処理は、図１５Ａに示すステップ９０２１及び９０７１の処理に相当する。
【０１６６】
次に、ラベル割当部１１５は、ステップ８２２の処理で選択した割当候補ラベルのハッシュ値の衝突数の取得要求を、自身の衝突検出部１１６に入力する（８２３）。ステップ８２３の処理は図１５Ａに示すステップ９０３及び９０８の処理に相当する。
【０１６７】
次に、ラベル割当部１１５には、衝突数の取得要求の応答として割当候補ラベルのハッシュ値の衝突数が衝突検出部１１６から入力される（８２４）。ステップ８２４の処理は図１５Ａに示す９０４及び９０９の処理に相当する。
【０１６８】
次に、ラベル割当部１１５は、ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が、自身に対応するパケット転送装置用のシステム規定パラメータテーブル５２に登録された衝突上限数以下であるか否かを判定する（８２５）。
【０１６９】
ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が衝突上限数よりも大きいと、ステップ８２５の処理で判定された場合、ラベル割当部１１５は、割当候補ラベルに割当不可フラグを設定し（８２８）、ステップ８２２の処理に戻る。この処理は図１５Ａに示すステップ９０４１の処理に相当する。
【０１７０】
一方、ステップ８２４の処理で入力された割当候補ラベルのハッシュ値の衝突数が衝突上限数以下であると、ステップ８２５の処理で判定された場合、ラベル割当部１１５は、割当候補ラベルのラベル値をリンクに割り当てることを決定し、当該ラベル値をラベル割当要求の応答として経路管理部１１１に入力する（８２６）。ステップ８２６の処理は図１５Ａに示すステップ９０６の処理に相当する。
【０１７１】
次に、ラベル割当部１１５は、ステップ８２８の処理で設定された割当不可フラグをクリアし、処理を終了する。
【０１７２】
図１８は、本発明の第１実施形態の新たなパスを確立する場合の衝突検出部１１６によって実行される処理のフローチャートである。
【０１７３】
まず、衝突検出部１１６は、ラベル割当部１１５から入力された衝突数取得要求から、衝突数を確認する割当候補ラベルのラベル値を取り出す（８３１）。
【０１７４】
次に、衝突検出部１１６は、ステップ８３１の処理で取り出されたラベル値からハッシュ値を算出する（８３２）。ステップ８３２の処理は図１５Ａに示すステップ９０３１及び９０８１の処理に相当する。
【０１７５】
次に、衝突検出部１１６は、ハッシュテーブル２２３３を参照し、ステップ８３２の処理で算出されたハッシュ値と一致するエントリに登録されている入力ラベルの数を衝突数として算出する（８３３）。ステップ８３３の処理は図１５Ａに示すステップ９０３２及び９０８２の処理に相当する。
【０１７６】
次に、衝突検出部１１６は、ステップ８３３の処理で算出された衝突数をラベル割当部１１５に入力し（８３４）、処理を終了する。
【０１７７】
図１９は、本発明の第１実施形態の新たなパスを確立する場合のパケット転送装置の転送宛先制御部２２３によって実行される処理のフローチャートである。
【０１７８】
まず、転送宛先制御部２２３は、監視制御装置１１の経路管理部１１１によって送信された追加要求を受信した場合、受信した追加要求に含まれるクロスコネクト情報を取り出す（８４１）。クロスコネクト情報は、監視制御装置１１のクロスコネクトテーブル１１３のエントリのうち、新たなパスを確立させるための処理で追加されたエントリに登録された情報を含む。
【０１７９】
次に、転送宛先制御部２２３は、ステップ８４１の処理で取り出されたクロスコネクト情報に含まれる入力ラベルのハッシュ値を算出する（８４２）。ステップ８４２の処理は図１５Ｂに示すステップ９２３１の処理に相当する。
【０１８０】
次に、転送宛先制御部２２３は、ステップ８４１の処理で取り出されたクロスコネクト情報をクロスコネクトテーブル２２３２に新たなエントリとして追加するとともに、ステップ８４２の処理で算出したハッシュ値と、クロスコネクトテーブル２２３２に追加したエントリに含まれる入力ラベル、出力インタフェース、及び出力ラベルとを対応付けた情報を、ハッシュテーブル２２３３に登録する（８４３）。ステップ８４３の処理は図１５Ｂに示すステップ９２３２の処理に相当する。
【０１８１】
次に、転送宛先制御部２２３は、受信した追加要求に対する結果応答を監視制御装置１１の経路管理部１１１に送信し（８４４）、処理を終了する。ステップ８４４の処理は図１５Ｂに示すステップ９２４の処理に相当する。
【０１８２】
次に、パケット転送装置がパケットを受信した場合に実行されるパケット転送処理を図２０を用いて説明する。
【０１８３】
図２０は、本発明の第１実施形態のパケット転送装置によるパケット転送処理のフローチャートである。
【０１８４】
図２０では、パケット転送装置Ｂ２２が入力ラベル「２０７」を含むパケットを受信した場合のパケット転送処理について説明する。
【０１８５】
入力ラベル「２０７」を含むパケットはパケット転送装置Ｂ２２のインタフェース部２２ｂを介して入力され、インタフェース部２２ｂは入力されたパケットを図４に示すスイッチ処理部２２２に渡す。
【０１８６】
受信パケット解析部２２４２は、スイッチ処理部２２２に渡されたパケットの図１３に示すヘッダ部５１１からラベル５１１１「２０７」を取り出す（８５１）。
【０１８７】
パケット転送制御部２２４１は、ステップ８５１の処理で取り出された入力ラベル「２０７」をハッシュ生成部２２３４に渡し、ハッシュ生成部２２３４は、入力ラベル「２０７」のハッシュ値「１」を算出する（８５２）。
【０１８８】
次に、管理部２２３１は、ハッシュテーブル２２３３及びクロスコネクトテーブル２２３２を参照し、ステップ８５２の処理で算出されたハッシュ値「１」に対応する一つ目のクロスコネクト情報を読み出す（８５３）。図１１に示すハッシュテーブル２２３３ではハッシュ値「１」に対応する一つ目の入力ラベル「２０１」は、クロスコネクトテーブル２２３２の入力ラベル「２０１」のクロスコネクト情報（図７参照）と対応付けられているので、管理部２２３１は、当該クロスコネクト情報を読み出す。
【０１８９】
そして、管理部２２３１は、ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致するか否かを判定する（８５４）。
【０１９０】
ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致しないと、ステップ８５４の処理で判定された場合、管理部２２３１は、ステップ８５３の処理に戻り、ステップ８５２の処理で算出されたハッシュ値に対応する次のクロスコネクト情報を読み出す。
【０１９１】
なお、ステップ８５３及び８５４の処理は、パケットに含まれる入力ラベルと一致する入力ラベルのクロスコネクト情報が読み出されるまで繰り返し実行される。
【０１９２】
最初にステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベル「２０１」とパケットから取り出された入力ラベル「２０７」とは一致しないので、ステップ８５３の処理に戻る。そして、ステップ８５３の処理では、管理部２２３１は、図１１に示すハッシュテーブル２２３３ではハッシュ値「１」に対応する二つ目の入力ラベル「２０７」に対応付けられるクロスコネクト情報を読み出す。ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベル「２０１」とパケットから取り出された入力ラベル「２０７」とが一致するので、ステップ８５５の処理が実行される。
【０１９３】
一方、ステップ８５３の処理で読み出されたクロスコネクト情報に含まれる入力ラベルと、ステップ８５１の処理でパケットから取り出された入力ラベルとが一致すると、ステップ８５４の処理で判定された場合、管理部２２３１は、パケットを出力するインタフェース部が当該クロスコネクト情報に含まれる出力インタフェース（ＩＦ＿Ｂ４：インタフェース部２２ｄ）となるように、パケットスイッチ部２２４３を設定する（８５５）。
【０１９４】
次に、送信パケット生成部２２４４は、パケットのヘッダ部５１１のラベル５１１１をクロスコネクト情報に含まれる出力ラベル「３０２」に書き換えて、当該パケットを出力インタフェースとなるインタフェース部２２ｄに出力し（８５６）、パケット転送処理を終了する。
【０１９５】
本発明を適用せずに、新たに確立させるパスの経路に含まれるパケット転送装置間のリンクに新たなラベルを割り当てた場合、各パケット転送装置内においてラベルのハッシュ値の衝突数の上限を保証できない。
【０１９６】
つまり、図２０に示すパケット転送処理において、ステップ８５３及び８５４のループ処理を何回実行するかが保証できないため、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまい、パケットの消失を招いてしまう可能性がある。
【０１９７】
本発明では、図１４に示すシステム規定パラメータテーブル５２に登録された衝突上限数以下となるようにラベルを決定するので、各パケット転送装置内においてラベルのハッシュ値の衝突数の上限を保証でき、ステップ８５３及び８５４のループ処理を何回実行するかが保証できる。このため、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまい、パケットの消失を招いてしまうことを防止できる。
【０１９８】
パスＰ１を確立させる場合には、リンク回線３１のラベルを決定する必要があるが、パケット転送装置Ｂ２２は、図２０に示すステップ８５３及び８５４の処理が２回実行されれば、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまうものとする。
【０１９９】
この場合、図１１及び図１２のように、パケット転送装置Ｂ２２の入力ラベルに「２０７」が割り当てられた場合、ハッシュ値「１」の衝突数が２回となり、図２０で説明したように、図２０に示すステップ８５３及び８５４の処理が２回実行されるので、出力インタフェース及び出力ラベルを決定するまでの時間がパケット到着間隔を超過してしまう。
【０２００】
パケット転送装置Ｂ２２のシステム規定パラメータテーブル５２の衝突上限数に「１」を設定することによって、衝突数上限数が１回となり、割当候補に「２０７」が選択されたとしても、図１７に示すステップ８２５の処理で、「２０７」を入力ラベルとした場合、ハッシュ値「１」の衝突数が２回となるため、「２０７」以外のラベル値で、衝突上限数が１回以下となるラベル値が入力ラベルと決定される。ここで、「２０９」が入力ラベルとして決定された場合のハッシュテーブル１１６２及び２２３３、並びにクロスコネクトテーブル１１３について、図２１〜図２３を用いて説明する。
【０２０１】
図２１は、本発明の第１実施形態のパケット転送装置のハッシュテーブル２２３３の説明図である。
【０２０２】
図２２は、本発明の第１実施形態の衝突検出部１１６のハッシュテーブル１１６２の説明図である。
【０２０３】
上述したように、ラベル値「２０７」は、衝突上限数が１回以下となるラベル値「２０９」が入力ラベルとなるので、図２１及び図２２では、衝突数が１回よりも大きくなるハッシュ値は存在しない。
【０２０４】
図２３は、本発明の第１実施形態の監視制御装置１１に記憶されるクロスコネクトテーブル１１３の説明図である。
【０２０５】
図２１及び図２２と同じく、パケット転送装置Ｂ２２のエントリの入力ラベル「２０７」は、衝突上限数が１回以下となるラベル値「２０９」に変更されている。
【０２０６】
以上のように、本実施形態では、パケット転送装置の転送制御テーブルの検索時間の上限を保証できる。
【０２０７】
また、転送制御識別子の各パケット転送装置内におけるハッシュ値の衝突数に基づいて、割当候補となる転送制御識別子の割り当てを許可するので、ネットワーク内における転送制御識別子は一意でなくてもよいので割当可能な転送制御識別子空間を有効活用できる。
【０２０８】
特許文献２に記載された技術は、ハッシュ値の衝突が発生しないように、転送制御識別子（特許文献２ではＩＰアドレス）を割り当てるものであるが、割り当てられる転送制御識別子のハッシュ値の分布をネットワーク内で均一化するものであり、本実施形態のように、個々のパケット転送装置内での転送制御識別子のハッシュ値衝突をパケット転送装置ごとに個別に検出し、当該ハッシュ値の衝突数を制御するものではない。
【０２０９】
例えば、二つの転送制御識別子が同じハッシュ値であり、二つの転送制御識別子が同じパケット転送装置を通過しなければ、ハッシュ値が二つの転送制御識別子が割り当てられてもよいが、特許文献２に記載された技術では、このような転送制御識別子は互いに同時に（期間が重なって）割当てられることはない。このため、特許文献２に記載された技術では、結果として使用可能な転送制御識別子が減少してしまう。
【０２１０】
また、特許文献２に記載された技術はハッシュ値の衝突を一切許容しない。このため、ハッシュ値と転送制御識別子との関係をＣｈａｉｎｅｄ Ｈａｓｈ Ｍｅｔｈｏｄを用いて管理するパケット転送装置の転送制御識別子の検索時間が、パケット到着間隔よりも格段に短い場合であっても、ハッシュ値が同一となる複数の転送制御識別子は割り当てられない。
【０２１１】
このため、特許文献２に記載された技術では、転送制御識別子空間を有効に活用できない。これに対して、本実施形態によると、転送制御識別子の検索処理の効率の向上と、転送制御識別子空間の有効活用とを両立させることができる。
【０２１２】
また、特許文献２に記載の技術では、一つのネットワークで単一のハッシュ関数の使用を前提としているので、特許文献２に記載された技術は、一つのネットワークで複数のハッシュ関数が使用された場合には適用できない。例えば、パケット転送装置ごと又はパケット転送装置のモジュールごとにハッシュ関数が異なる場合には、特許文献２に記載された技術は適用できない。
【０２１３】
本実施形態では、パケット転送装置２２に備わるハッシュ生成部２２３４に対応して、監視制御装置１１はハッシュ生成部１１６１を備えるため、一つのネットワークで複数のハッシュ関数が使用された場合であっても適用できる。
【０２１４】
また、本実施形態では、システム規定パラメータテーブル５２の衝突上限数は管理者が変更可能であるので、管理者は、各パケット転送装置が転送するパケットのサイズ及び各パケット転送装置に要求される品質（例えば、通信品質等）に基づいて、衝突上限数を柔軟に変更できる。
【０２１５】
また、本実施形態では、転送制御識別子のハッシュ値の衝突数の上限を保証するので、パケット転送装置による転送方法の検索時間の最大値を保証することによって、パケット転送装置の最大処理負荷を保証する。これによって、パケット転送装置で転送方法の検索時間が長くなり、処理負荷が増大することがなくなるため、本実施形態のパケット転送装置の単位ハードウェア資源（ロジック規模及びメモリ量）当たりの処理可能なパケット数を増加させることができる。このため、ハードウェアが同一のパケット転送装置であっても、本実施形態を適用したパケット転送装置のほうが、多くのフローを制御でき、高速な通信インタフェースを実現できる。また、本実施形態を適用したパケット転送装置は、本実施形態を適用しないパケット転送装置と同じ数のフローを制御する場合、又は同じ速度の通信インタフェースを実現する場合であっても、使用するハードウェア資源を削減できるため、消費電力を低減できる。
【０２１６】
（第２実施形態）
本発明の第２実施形態について図２４を用いて説明する。
【０２１７】
本実施形態は、第１実施形態では監視制御装置１１に備わる衝突検出部１１６を各パケット転送装置２１に備わるようにした実施形態である。
【０２１８】
図２４は、本発明の第２実施形態のネットワークシステムの構成図である。
【０２１９】
監視制御装置１１のラベル割当部１１５は衝突検出部１１６を備えず、各パケット転送装置Ａ２１〜Ｄ２４が衝突検出部１１６ａ〜１１６ｄを備える。
【０２２０】
本実施形態の新たなパスを確立させるための処理は、第１実施形態の処理と同じであるので、説明を省略する。
【０２２１】
ただ、図１５Ａに示すステップ９０３及び９０８の処理では、ラベル割当部１１５が、自身に対応するパケット転送装置にハッシュ衝突数取得要求を送信する。
【０２２２】
（第３実施形態）
本発明の第３実施形態について図２５を用いて説明する。
【０２２３】
本実施形態は、第１実施形態では監視制御装置１１はラベル割当部１１５を備えず、各パケット転送装置Ａ２１〜Ｄ２４がラベル割当部１１５ａ〜１１５ｄを備える。
【０２２４】
図２５は、本発明の第３実施形態のネットワークシステムの構成図である。
【０２２５】
監視制御装置１１はラベル割当部１１５を備えず、各パケット転送装置Ａ２１〜Ｄ２４がラベル割当部１１５ａ〜１１５ｄを備える。なお、各パケット転送装置Ａ２１〜Ｄ２４のラベル割当部１１５ａ〜１１５ｄは、衝突検出部１１６ａ〜１１６ｄを備える。
【０２２６】
本実施形態の新たなパスを確立させるための処理は、第１実施形態の処理と同じであるので、説明を省略する。
【０２２７】
ただ、図１５Ａに示すステップ９０２及び９０７の処理では、経路管理部１１１が、ラベルを決定するラベル割当部１１５を備えるパケット転送装置にラベル割当要求を送信する。
【０２２８】
なお、第３実施形態では、いずれかのパケット転送装置が、例えばＭＰＬＳシグナリングを用いてパス経路を決定すれば、監視制御装置１１は不要となる。
【０２２９】
本発明では、各パケット転送装置がハッシュ値を算出するために使用するハッシュ関数は、各パケット転送装置間で異なっていてもよい。
【０２３０】
また、本発明では、図１、図２４及び図２５でパケットネットワーク１のトポロジーを図示したが、本トポロジーに限定されず、リングトポロジー、リニアトポロジー、メッシュトポロジー、及びＰ２Ｐトポロジー等、任意のトポロジーであってもよい。
【０２３１】
また、ハッシュ値の衝突上限数は、パケット転送装置のハードウェア性能、パケット容量（サイズ）、帯域、パケット到着頻度、及びサービス品質等に基づいて、管理者によって任意の値に設定されるものであるので、衝突上限数は「１」に限定されない。
【０２３２】
また、衝突上限数は動的に設定されてもよい。例えば、監視制御装置１１は、パケット転送装置が受信するパケット容量及び各パケット転送装置へのパケット到着頻度等を監視し、例えば、パケット容量がある時点よりも増加した場合、衝突上限数を増加させてもよいし、パケット到着頻度がある時点よりも増加した場合、衝突上限数を増加させてもよい。なお、第３実施形態のようにラベル割当部１１５が各パケット転送装置に備わる場合には、各パケット転送装置が衝突上限数を動的に設定する。
【０２３３】
また、第１〜第３実施形態では、転送制御テーブル（クロスコネクトテーブル）から転送方法を取得するためにハッシュ関数を用いる方法を説明したが、他の検索方法を用いてもよい。
【０２３４】
また、他の検索方法としては、Ｂｉｎａｒｙ Ｔｒｅｅ（２分木）等のツリー状データ構造に基づく検索アルゴリズムを用いることができる。当該検索処理に要する時間の最大値は、ツリーの深さと強い正の相関関係があるので、検索処理の負荷として、ツリーの深さを用いる事ができる。
【０２３５】
この検索処理を以下に具体的に説明する。
【０２３６】
例えば、ラベル割当部１１５及びパケット転送装置は、２分探索木によるデータ構造で転送制御識別子を転送方法と関連付けて管理しておき、２分探索木に用いる２分探索アルゴリズムを用いて、検索対象の転送制御識別子と一致する転送制御識別子を検索する方法がある。
【０２３７】
この方法について、図２６を用いて説明する。
【０２３８】
図２６は、本発明の転送制御識別子を管理するための２分探索木によるデータ構造の説明図である。
【０２３９】
図２６は、転送制御識別子としてラベル値「２００」、「２１０」、「２１５」、「２２０」、「２３０」、 「２４０」、及び 「２５０」が割り当てられている場合の２分探索木によるデータ構造を示す。
【０２４０】
ラベル割当部１１５及びパケット転送装置は、図２６に示す２分探索木によるデータ構造を、ハッシュテーブル１１６２及び２２３３の代わりに記憶する。
【０２４１】
なお、図２６に示すツリー状のデータ構造では、最上部のノード「２３０」から検索されるので、ツリーの深さ（図２６では４段）がラベル割当部１１５及びパケット転送装置にかかる検索処理負荷となるため、ツリーの深さが検索処理にかかる時間となる。
【０２４２】
パケット転送装置の検索処理にかかる時間の上限値を保証するため、管理者は、ツリーの深さの上限値をシステム規定パラメータテーブル５２に登録する。
【０２４３】
新たなラベルを割り当てる場合の処理について説明する。
【０２４４】
図１５Ａにおいて、ラベル割当部１１５は、ステップ９０２の処理で、ラベル割当要求を受け取った場合、ステップ９０２１の処理で、割当可能ラベルから任意のラベルを割当候補ラベルとして選択する。
【０２４５】
そして、衝突検出部１１６は、割当候補ラベル及び割当済のラベルのツリー深さが最短となるように、２分探索木によるデータ構造を生成する。そして、衝突検出部１１６は、生成した２分探索木によるデータ構造のツリー深さを、ラベル割当部１１５に通知する。
【０２４６】
ラベル割当部１１５は、通知されたツリーの深さがシステム規定パラメータテーブル５２に登録された上限値以下であれば、当該割当候補ラベルを経路管理部１１１に通知し、
通知されたツリーの深さがシステム規定パラメータテーブル５２に登録された上限値よりも大きければ、割当可能ラベルから他のラベルを割当候補ラベルとして選択し、上述の処理を再度実行する。
【０２４７】
例として、システム規定パラメータテーブル５２に登録された、ツリーの深さの上限値が４である場合を仮定した場合の処理を説明する。
【０２４８】
新たに割り当てようとするラベル値が２３５である場合、該ラベル値は図２６に示すラベル値２４０の左側の子として格納される為、ツリー上の深さは３となり、上限値４以下であるため当該割当候補ラベルを経路管理部１１１に通知する。
【０２４９】
新たに割り当てようとするラベル値が２１２である場合、該ラベル値は図２６に示すラベル値２１５の左側の子として格納される為、ツリー上の深さは４となり、上限値４以上となるため、割り当て可能ラベルから他のラベルを割当て候補ラベルとして選択し直す。
【０２５０】
以上のように、ツリー状のデータ構造により転送制御識別子を管理する場合には、ツリーの深さを検索処理の負荷として用いることができる。
【０２５１】
また更に、転送制御テーブルを検索する方法としては、上述したハッシュ関数及びツリー状のデータ構造に基づく検索方法以外の方法を用いることができる。例えば、IETF RFC4981, "Survey of Research towards Robust Peer-to-Peer Networks: Search Methods"に示される各種検索方法を用いることができ、これらの検索方法に応じた検索処理時間を検索処理の負荷に用いることができる。
【０２５２】
第１〜第３実施形態では、パケット転送装置に入力されたパケットを転送経路に関する識別子であるＭＰＬＳラベル値を転送制御識別子として用いた場合に説明したが、転送制御識別子は、各パケット転送装置内で一意であって、パケット転送装置に入力されたパケットの転送方法を決定するためのものであれば、他のものであってもよい。
【０２５３】
転送制御識別子の他の例としては、例えば、ＱｏＳに関する識別子、及び警報転送に関する識別子がある。
【０２５４】
ＱｏＳに関する識別子は、パケット転送装置に入力されたパケットの出力インタフェースにおける出力キューの優先度を決定するための識別子である。
【０２５５】
ＱｏＳに関する識別子は、ＱｏＳに関する転送制御識別子は、IETF, RFC2475, "An Architecture for Differentiated Services"の2.3節、"Traffic Classification and Conditioning"の処理において参照される識別子、IETF, RFC1633, "Integrated Services in the Internet Architecture: an Overview"の4.1節Basic Functionsの処理において参照される識別子等であり、フロー識別情報及び転送廃棄優先制御情報の少なくとも一方を含む。
【０２５６】
フロー識別情報は、ＭＡＣアドレス、Ｅｔｈｅｒｔｙｐｅ、ＩＰアドレス、ＴＣＰ／ＵＤＰのポート番号、ＩＰｖ６のフローラベルの少なくとも一つである。また、転送廃棄優先制御情報は、ＩＰヘッダ及びＭＰＬＳヘッダのＤＳＣＰ／ＴＯＳ、並びにＬ−ＬＳＰのラベル値の少なくとも一つである。
【０２５７】
警報転送に関する識別子は、パケット転送装置がイーサＯＡＭフレームを終端させるか否かを判定するために当該フレームに含まれるＭＥＧレベル等である。
【０２５８】
転送経路に関する識別子は、宛先情報、コネクション識別子、トレイル識別子、ネットワーク識別子、及び制御フラグ等である。
【０２５９】
宛先情報は、例えば、ＭＡＣアドレス及びＩＰアドレス等である。コネクション識別子は、ＡＴＭのＶＰＩ（Virtual Path Identifier）／ＶＣＩ（Virtual Channel Identifier）、及びフレームリレーのＤＬＣＩ（Data-Link Connection Identifier）である。
【０２６０】
ネットワーク識別子は、ＶＬＡＮ ＩＤ、ＰＢＢ（IEEE802.11ａｈ Provider Backbone Bridge）におけるＳ−ＴＡＧ／Ｃ−ＴＡＧ／Ｉ−ＳＩＤを含む拡張ＶＬＡＮ ＩＤ等である。
【０２６１】
制御フラグは、ＩＰヘッダのルータアラート、及びＭＰＬＳのルータアラートラベル等である。
【０２６２】
第１〜第３実施形態では、一つの種別（ＭＰＬＳラベル値）の転送制御識別子をネットワークシステムで用いる例について説明したが、複数の種別の転送制御識別子をネットワークシステムで用いてもよい。
【０２６３】
例えば、転送制御識別子として、ＭＰＬＳラベル値に代表される転送経路に関する転送識別子及びＱｏＳに関する転送制御識別子の２種類を用いる場合について説明する。
【０２６４】
この場合、ラベル割当部１１５及び転送宛先制御部２２３は、転送制御識別子の識別子ごとに、転送制御識別子に対応する転送方法の検索方法を異ならせてもよい。
【０２６５】
例えば、一方の種別の転送制御識別子にはハッシュ値を用いて転送方法を検索し、他方の種別の転送制御識別子にはツリー状のデータ構造を用いて転送方法を検索してもよい。
【０２６６】
また、一方の種別の転送制御識別子の転送方法の検索に用いるハッシュ関数と他方の種別の転送制御識別子の転送方法の検索に用いるハッシュ関数とを異ならせてもよい。
【０２６７】
また、ラベル割当部１１５及び転送宛先制御部２２３は、複数の種別の転送制御識別子で同じ転送方法の検索方式を用いてもよい。
【０２６８】
なお、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した意味ではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０２６９】
１ パケットネットワーク
１１ 監視制御装置
１１１ 経路管理部
１１２ 通信部
１１３ クロスコネクトテーブル
１１４ パス経路テーブル
１１５ ラベル割り当て部
１１５１ 管理部
１１５２ 割当済ラベルテーブル
１１６ 衝突検出部
１１６１ ハッシュ生成部
１１６２ ハッシュテーブル
１１７ 通信路確立要求部
２１〜２４ パケット転送装置
２１１、２２１、２３１、２４１ 制御部
２１２、２２２、２３２、２４２ ＳＷ処理部
２２３ 転送宛先制御部
２２３１ 管理部
２２３２ クロスコネクトテーブル
２２３３ ハッシュテーブル
２２３４ ハッシュ生成部
２２４ パケット転送部
２２４１ パケット転送制御部
２２４２ 受信パケット解析部
２２４３ パケットスイッチ部
２２４４ 送信パケット生成部
３１〜３５ リンク回線
４１〜４５ ルータ
５２ システム規定パラメータテーブル
【特許請求の範囲】
【請求項１】
複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、
前記パケット転送装置は、
前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、
パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索部と、
前記転送制御テーブル検索手段によって検索された前記転送方法で前記パケットを転送するパケット転送部と、を備え、
前記ネットワークシステムは、
前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索部の検索負荷を算出する検索負荷算出部と、
前記検索負荷算出部によって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とするネットワークシステム。
【請求項２】
前記ネットワークシステムは、
前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって計算し、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて記憶し、
前記転送制御テーブル検索部は、
パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出部は、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出することを特徴とする請求項１に記載のネットワークシステム。
【請求項３】
前記割当可否判定部は、前記割当候補の転送制御識別子を割り当てない場合、当該割当候補の転送制御識別子と異なる転送制御識別子を新たな割当候補として選択することを特徴する請求項１に記載のネットワークシステム。
【請求項４】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置は、前記検索負荷算出部、及び前記割当可否判定部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項５】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置は、前記割当可否判定部を備え、
前記パケット転送装置は、前記検索負荷算出部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項６】
前記パケット転送装置は、前記検索負荷算出部、及び前記割当可否判定部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項７】
前記転送制御テーブル検索部は、
前記転送制御テーブルに登録された転送制御識別子をツリー状のデータ構造によって管理し、
前記ツリー状のデータ構造を検索するための検索アルゴリズムを用いて、前記受信したパケットに含まれる前記転送制御識別子と一致する転送制御識別子を検索し、
前記検索負荷算出部は、
前記割当候補の転送制御識別子の前記ツリーの深さを前記転送制御テーブルの検索負荷として算出することを特徴とする請求項１に記載のネットワークシステム。
【請求項８】
前記転送制御識別子は、転送経路に関する識別子、ＱｏＳに関する識別子、及び警報転送に関する識別子の少なくとも一つを含むことを特徴とする請求項１に記載のネットワークシステム。
【請求項９】
前記転送経路に関する識別子はＭＰＬＳラベル値であることを特徴とする請求項８に記載のネットワークシステム。
【請求項１０】
前記転送制御識別子は、複数の種別の転送制御識別子を含み、
前記転送制御テーブル検索部は、前記パケット転送装置及び前記転送制御識別子の種別の少なくとも一方によって、前記転送方法の検索方法を異ならせることを特徴とする請求項１に記載のネットワークシステム。
【請求項１１】
前記転送制御テーブル検索部は、
前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって計算し、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて記憶し、
パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出部は、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出し、
前記ハッシュ関数を、前記パケット転送装置及び前記転送制御識別子の種別の少なくとも一方によって異ならせることを特徴とする請求項１０に記載のネットワークシステム。
【請求項１２】
複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムにおいて、前記パケットの転送方法を決定するための転送制御識別子の割当方法であって、
前記パケット転送装置は、前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、
前記方法は、
前記パケット転送装置が、パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索ステップと、
前記パケット転送装置が、前記転送制御テーブル検索ステップで検索された前記転送方法で前記パケットを転送するパケット転送ステップと、
前記ネットワークシステムが、前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索ステップにおける検索負荷を算出する検索負荷算出ステップと、
前記ネットワークシステムが、前記検索負荷算出ステップによって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出ステップによって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定ステップと、を含むことを特徴とする転送制御識別子の割当方法。
【請求項１３】
前記方法は、
前記ネットワークシステムが前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって予め計算しておくステップと、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて予め記憶しておくステップと、を含み、
前記転送制御テーブル検索ステップでは、前記パケット転送装置が、パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出ステップでは、前記ネットワークシステムが、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１４】
前記割当可否判定ステップでは、前記ネットワークシステムが、前記割当候補の転送制御識別子を割り当てない場合、当該割当候補の転送制御識別子と異なる転送制御識別子を新たな割当候補として選択することを特徴する請求項１２に記載の転送制御識別子の割当方法。
【請求項１５】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置が、前記検索負荷算出ステップ、及び前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１６】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記パケット転送装置が、前記検索負荷算出ステップを実行し、
前記監視制御装置が、前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１７】
前記パケット転送装置が、前記検索負荷算出ステップ、及び前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１８】
前記転送制御テーブル検索ステップでは、
前記ネットワークシステムが、前記転送制御テーブルに登録された転送制御識別子をツリー状のデータ構造によって管理し、
前記ネットワークシステムが、前記ツリー状のデータ構造を検索するための検索アルゴリズムを用いて、前記受信したパケットに含まれる前記転送制御識別子と一致する転送制御識別子を検索し、
前記検索負荷算出ステップでは、
前記割当候補の転送制御識別子の前記ツリーの深さを前記転送制御テーブルの検索負荷として算出することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１９】
前記転送制御識別子は、転送経路に関する識別子、ＱｏＳに関する識別子、及び警報転送に関する識別子の少なくとも一つを含むことを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項２０】
前記転送経路に関する識別子はＭＰＬＳラベル値であることを特徴とする請求項１９に記載の転送制御識別子の割当方法。
【請求項１】
複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムであって、
前記パケット転送装置は、
前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、
パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索部と、
前記転送制御テーブル検索手段によって検索された前記転送方法で前記パケットを転送するパケット転送部と、を備え、
前記ネットワークシステムは、
前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索部の検索負荷を算出する検索負荷算出部と、
前記検索負荷算出部によって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出部によって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定部と、を備えることを特徴とするネットワークシステム。
【請求項２】
前記ネットワークシステムは、
前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって計算し、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて記憶し、
前記転送制御テーブル検索部は、
パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出部は、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出することを特徴とする請求項１に記載のネットワークシステム。
【請求項３】
前記割当可否判定部は、前記割当候補の転送制御識別子を割り当てない場合、当該割当候補の転送制御識別子と異なる転送制御識別子を新たな割当候補として選択することを特徴する請求項１に記載のネットワークシステム。
【請求項４】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置は、前記検索負荷算出部、及び前記割当可否判定部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項５】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置は、前記割当可否判定部を備え、
前記パケット転送装置は、前記検索負荷算出部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項６】
前記パケット転送装置は、前記検索負荷算出部、及び前記割当可否判定部を備えることを特徴とする請求項１に記載のネットワークシステム。
【請求項７】
前記転送制御テーブル検索部は、
前記転送制御テーブルに登録された転送制御識別子をツリー状のデータ構造によって管理し、
前記ツリー状のデータ構造を検索するための検索アルゴリズムを用いて、前記受信したパケットに含まれる前記転送制御識別子と一致する転送制御識別子を検索し、
前記検索負荷算出部は、
前記割当候補の転送制御識別子の前記ツリーの深さを前記転送制御テーブルの検索負荷として算出することを特徴とする請求項１に記載のネットワークシステム。
【請求項８】
前記転送制御識別子は、転送経路に関する識別子、ＱｏＳに関する識別子、及び警報転送に関する識別子の少なくとも一つを含むことを特徴とする請求項１に記載のネットワークシステム。
【請求項９】
前記転送経路に関する識別子はＭＰＬＳラベル値であることを特徴とする請求項８に記載のネットワークシステム。
【請求項１０】
前記転送制御識別子は、複数の種別の転送制御識別子を含み、
前記転送制御テーブル検索部は、前記パケット転送装置及び前記転送制御識別子の種別の少なくとも一方によって、前記転送方法の検索方法を異ならせることを特徴とする請求項１に記載のネットワークシステム。
【請求項１１】
前記転送制御テーブル検索部は、
前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって計算し、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて記憶し、
パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出部は、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出し、
前記ハッシュ関数を、前記パケット転送装置及び前記転送制御識別子の種別の少なくとも一方によって異ならせることを特徴とする請求項１０に記載のネットワークシステム。
【請求項１２】
複数のパケット転送装置を備え、前記複数のパケット転送装置の間でパケットを転送するネットワークシステムにおいて、前記パケットの転送方法を決定するための転送制御識別子の割当方法であって、
前記パケット転送装置は、前記パケットに含まれる転送制御識別子に対応して、当該転送制御識別子を含むパケットの転送方法が登録された転送制御テーブルを記憶し、
前記方法は、
前記パケット転送装置が、パケットを受信した場合、前記転送制御テーブルを参照し、前記受信したパケットに含まれる前記転送制御識別子に対応する転送方法を検索する転送制御テーブル検索ステップと、
前記パケット転送装置が、前記転送制御テーブル検索ステップで検索された前記転送方法で前記パケットを転送するパケット転送ステップと、
前記ネットワークシステムが、前記転送制御識別子を新たに割り当てる場合、割当候補の転送制御識別子を割り当てた後の前記転送制御テーブル検索ステップにおける検索負荷を算出する検索負荷算出ステップと、
前記ネットワークシステムが、前記検索負荷算出ステップによって算出された検索負荷が所定値以下である場合、前記割当候補の転送制御識別子を割り当て、前記検索負荷算出ステップによって算出された検索負荷が所定値よりも大きい場合、前記割当候補の転送制御識別子を割り当てない割当可否判定ステップと、を含むことを特徴とする転送制御識別子の割当方法。
【請求項１３】
前記方法は、
前記ネットワークシステムが前記転送制御テーブルに登録された転送制御識別子のハッシュ値をハッシュ関数によって予め計算しておくステップと、
前記計算したハッシュ値と、当該ハッシュ値に対応する前記転送制御識別子の転送方法とを対応付けて予め記憶しておくステップと、を含み、
前記転送制御テーブル検索ステップでは、前記パケット転送装置が、パケットを受信した場合、前記受信したパケットに含まれる転送制御識別子のハッシュ値を前記ハッシュ関数によって計算し、前記計算したハッシュ値に対応する転送制御識別子の転送方法を検索し、
前記検索負荷算出ステップでは、前記ネットワークシステムが、前記割当候補の転送制御識別子のハッシュ値が前記転送制御テーブルに登録された転送制御識別子のハッシュ値と衝突する度合いを、前記転送制御テーブル検索部の検索負荷として算出することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１４】
前記割当可否判定ステップでは、前記ネットワークシステムが、前記割当候補の転送制御識別子を割り当てない場合、当該割当候補の転送制御識別子と異なる転送制御識別子を新たな割当候補として選択することを特徴する請求項１２に記載の転送制御識別子の割当方法。
【請求項１５】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記監視制御装置が、前記検索負荷算出ステップ、及び前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１６】
前記ネットワークシステムは、前記パケット転送装置を監視する監視制御装置を備え、
前記パケット転送装置が、前記検索負荷算出ステップを実行し、
前記監視制御装置が、前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１７】
前記パケット転送装置が、前記検索負荷算出ステップ、及び前記割当可否判定ステップを実行することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１８】
前記転送制御テーブル検索ステップでは、
前記ネットワークシステムが、前記転送制御テーブルに登録された転送制御識別子をツリー状のデータ構造によって管理し、
前記ネットワークシステムが、前記ツリー状のデータ構造を検索するための検索アルゴリズムを用いて、前記受信したパケットに含まれる前記転送制御識別子と一致する転送制御識別子を検索し、
前記検索負荷算出ステップでは、
前記割当候補の転送制御識別子の前記ツリーの深さを前記転送制御テーブルの検索負荷として算出することを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項１９】
前記転送制御識別子は、転送経路に関する識別子、ＱｏＳに関する識別子、及び警報転送に関する識別子の少なくとも一つを含むことを特徴とする請求項１２に記載の転送制御識別子の割当方法。
【請求項２０】
前記転送経路に関する識別子はＭＰＬＳラベル値であることを特徴とする請求項１９に記載の転送制御識別子の割当方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１３−４２３２０（Ｐ２０１３−４２３２０Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１１−１７７４１１（Ｐ２０１１−１７７４１１）
【出願日】平成２３年８月１５日（２０１１．８．１５）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２３年８月１５日（２０１１．８．１５）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]