(57)【特許請求の範囲】
【請求項１】
終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際のパスのアグリゲート方法であって、
（ａ）第１のパスの識別子と、第１のパスの始点ノードから第２のパスとの共通経路の終点のノードまでのホップ数とを含むパケットを、第１のパスの始点ノードから送出し、
（ｂ）第２のパスとの共通経路において、第２のパスの転送情報を使ってパケットを転送し、
（ｃ）ノードを通過するごとにパケットに含まれるホップ数をデクリメントし、それによって第２のパスとの共通経路の終点のノードにパケットが到達したと認識されるとき、第２のパスから別かれて第１のパスへパケットを転送するステップを具備するパスのアグリゲート方法。
【請求項２】
（ｄ）共通経路内において、第２のパスに割り当てられたラベルを第１のパスの第１のレイヤのラベルとして第１のパスにも割り当て、かつ、第１のパスを識別するラベルを第１のパスの第２のレイヤのラベルとして第１のパスにさらに割り当てるステップをさらに具備し、
ステップ（ｂ）は、該第１のレイヤのラベルを用いてパケットを転送するサブステップを含み、
ステップ（ｃ）は、該第２のレイヤのラベルを用いてパケットを転送することにより、第２のパスから別かれて第１のパスへパケットを転送するサブステップを含む請求項１記載の方法。
【請求項３】
ステップ（ｄ）は、第１のパスのラベル要求メッセージに第２のパスに割り当てられたラベルを格納して要求することにより、第２のパスに割り当てられたラベルを第１のパスにも割り当てるサブステップを含む請求項２記載の方法。
【請求項４】
終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、
第１のパスに関連付けて自ノードから第２のパスとの共通経路の終点のノードまでのホップ数を記憶する手段と、
第１のパスの識別子と、該ホップ数とを含むパケットを送出する手段とを具備するノード装置。
【請求項５】
終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、
第１のパスの識別子と、第１のパスの始点ノードから第２のパスとの共通経路の終点のノードまでのホップ数であってノードを通過するごとにデクリメントされるものとを含み、第２のパスとの共通経路において、第２のパスの転送情報を使って転送されたパケットを受信する手段と、
受信されたパケット内に含まれるホップ数に基づき、自ノードが第２のパスとの共通経路の終点のノードであると認識されるとき、第２のパスから別かれて第１のパスへパケットを転送する手段とを具備するノード装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ラベルスイッチ機能を有するネットワークにおいてラベルスイッチドパスをアグリケートすることによってラベルテーブルのエントリ数を削減する方法およびそれを実現するノード装置に関する。
【０００２】
【従来の技術】
ラベルスイッチ機能を有するネットワーク、例えば、ＭＰＬＳ（Ｍｕｔｉｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）網では、パケットに付与されているパケットの転送単位を示したラベルを基に、各ノードにおける、パケットの振る舞いを決定し、転送処理を行なう。そのためには、まず、ラベル値と、そのラベル値を持つ転送単位に属するパケットの、各ノードにおける処理方法を対応付けた、ラベルテーブルを各ノードに構築する必要である。そのために、ＭＰＬＳでは、ラベル配布プロトコル（ＬＤＰ）によるラベルスイッチドパス（ＬＳＰ）確立時に、ラベルの配布、および、ラベルテーブルの作成を行なっている。
【０００３】
このラベルテーブルのエントリーは、確立されたＬＳＰごとに存在することになるので、ＬＳＰの数が増加するに従って、ラベルテーブルのエントリー数も増加し、ラベルのスイッチ処理が複雑になる。しかしながら、ラベルのマージや、階層化技術を用いることによって、テーブルのエントリーを削減することが可能である。
【０００４】
図１に、ＭＰＬＳにおけるＬＳＰの例を示す。図１において、ＬＳＰ１０に対してノード１−２間にラベル“ａ”が、ノード２−３間にラベル“ｂ”が、ノード３−４間にラベル“ｃ”が、ノード４−５間にラベル“ｄ”が割り当てられている。ＬＳＰ１２に対しては、ノード６−２間、ノード２−３間、ノード３−４間およびノード４−５間にそれぞれラベル“ｅ”，“ｆ”，“ｇ”および“ｈ”が割り当てられている。したがって、ノード２にはラベルテーブル１４が、ノード３にはラベルテーブル１６が、ノード３にはラベルテーブル１８が格納される。
【０００５】
パケットをノード１からＬＳＰ１０に沿ってノード５まで転送する際には、ラベル“ａ”が付されたパケットが送出される。ノード２では、ノード１との入力インターフェース“１”とラベル“ａ”でラベルテーブル１４が引かれ、出力インターフェース“３”およびラベル“ｂ”が読み出され、出力インターフェース“３”からラベル“ｂ”を付したパケットが送出される。このようにして、パケットのラベルが書き替えられながら、パケットがノード５に到達する。
【０００６】
図２にラベルマージ技術を用いた場合を示す。図２のように複数のノードから、ある特定の宛先ノードに向かう複数のＬＳＰがある場合、マージによって、ＬＳＰの合流ノード（ノード２）において、複数の入力ラベルを、単一のラベルに置きかえることができる。これにより、図２に示すように、ＬＳＰの中間ノード３，４におけるラベルテーブル２０，２２のエントリーを削減することができる。
【０００７】
しかしながら、マージが適用できるのは、同じ宛先ノードを持つＬＳＰ、すなわち、マージを開始するポイントから宛先ノードまで、全く同じ経路を持つＬＳＰのみである。従って、異なる宛先ノードを持つＬＳＰに対しては適用できない。
ＬＳＰの階層化とは、予め設定された第１のＬＳＰの入口（Ｉｎｇｒｅｓｓ）と出口（Ｅｇｒｅｓｓ）を通過する第２のＬＳＰを設定する場合に、第１のＬＳＰをトンネルとみなし、そのトンネルの出口ノードを入口ノードに隣接するノードとみなして、第２のＬＳＰを設定するものである（ここで、第１のＬＳＰをレベル１のＬＳＰ、第２のＬＳＰをレベル２のＬＳＰと呼ぶ。）。これにより、トンネル内では複数のレベル２のＬＳＰを１つのレベル１のラベルでルーティングできるので、ラベルテーブルのエントリーを削減することができる。
【０００８】
しかしながら、階層化においては、あらかじめアグリゲートされる範囲が決まっており、その範囲を経路として持つＬＳＰのみ、これを適用することができる。従って、設定された共通範囲と一部でも異なる共通経路を持つＬＳＰに対しては、これを適用することはできない。
【０００９】
【発明が解決しようとする課題】
したがって本発明の目的は、共通経路を持ち宛先の異なる複数のＬＳＰを、流動的、且つ柔軟にアグリゲートする方法およびそれを実現するノード装置を提供することにある。
【００１０】
【課題を解決するための手段】
本発明によれば終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際のパスのアグリゲート方法であって、第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含むパケットを、第１のパスの始点ノードから送出し、第２のパスとの共通経路において、第２のパスのルーティング情報を使ってパケットをルーティングし、パケットに指定された、第２のパスとの共通経路の終点のノードに到達したとき、第２のパスから別かれて第１のパスへパケットをルーティングするステップを具備するパスのアグリゲート方法が提供される。
【００１１】
本発明によれば、終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、第１のパスに関連付けて第２のパスとの共通経路の終点のノードの位置を記憶する手段と、第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含むパケットを送出する手段とを具備するノード装置もまた提供される。
【００１２】
本発明によれば、終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含み、第２のパスとの共通経路において、第２のパスのルーティング情報を使ってルーティングされたパケットを受信する手段と、受信されたパケット内の指定に基づき、自ノードが第２のパスとの共通経路の終点のノードであるとき、第２のパスから別かれて第１のパスへパケットをルーティングする手段とを具備するノード装置もまた提供される。
【００１３】
【発明の実施の形態】
図３に示すように、ＬＳＲ（Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ  Ｒｏｕｔｅｒ）１→２→３→４→５の経路でＬＳＰ３０が既に存在し、ＬＳＲ６→２→３→４→７の経路のＬＳＰ３２を設定する際にＬＳＲ２−４間でＬＳＰ３２をＬＳＰ３０とアグリゲートする場合を例にとって本発明を説明する。
【００１４】
まず、ＬＳＲ１−５間にＬＳＰ３０を設定する際のラベル配布手順を図４に示す。ラベル配布プロトコル（ＬＤＰ）の送信ノードであるＬＳＲ１は、ＬＳＰ３０上の次の下流ノードであるＬＳＲ２に対し、ラベル要求メッセージ３４を送信する、それを受け取ったＬＳＲ２は、それを次の下流ノードであるＬＳＲ３に転送する。これを繰り返して、終端ノードであるＬＳＲ５がラベル要求メッセージ３６を受けとると、ＬＳＲ５は、前段のＬＳＲ４に対し、ラベル割り当てメッセージ３８を送信し、ラベル“ｄ”を配布する。同様にＬＳＲ４もＬＳＲ３に対し、ラベル“ｃ”を配布するためのラベル割り当てメッセージ４０を送信する、これを送信ノードに達するまで、繰り返す。これにより、ＬＳＲ１→５に対するラベルの配布が完了し、各ノードのラベルテーブルにエントリが追加されてＬＳＰ３０が設定される。
【００１５】
次にＬＳＲ６−７間にＬＳＰ３２（図３）を設定する際のラベル配布手順を図５に示す。ここで、経路２，３，４はＬＳＲ１→５と共通なので、下記の手順でアグリゲーションを行なうためのラベル配布を行なう。
１．ＬＳＲ６，２間には、既存のラベルが存在しないので、ＬＳＲ６はＬＳＲ２に、ラベル要求メッセージ４２により、新規ラベルを要求する。
２．ＬＳＲ２，３間には、既存のラベル“ｂ”が存在するので、ＬＳＲ２は、ＬＳＲ３に対し、ラベル要求メッセージ４４により、ラベル“ｂ”を要求する。
３．ＬＳＲ３もＬＳＲ２と同様に、ＬＳＲ４に対し、ラベル要求メッセージ４６により、ＬＳＲ３，４間の既存ラベル“ｃ”を要求する。
４．ＬＳＲ４，７間には、既存ラベルが存在しないので、ＬＳＲ４はＬＳＲ７に、ラベル要求メッセージ４８により、新規ラベルを要求する。
５．ＬＳＲ６→７の終端ノードであるＬＳＲ７は、ラベル割り当てメッセージ５０により、新規ラベル“ｆ”をＬＳＲ４に返す。
６．新規ラベル“ｆ”を受け取ったＬＳＲ４は、ＬＳＲ３に対し、ＬＳＲ３から要求された既存ラベル“ｃ”を返す。また、ＬＳＲ４はアグリゲート範囲の終端であるので、アグリゲート範囲において、ＬＳＰ３２を一意に識別するために、ラベル“Ａ”を発行し、その情報をラベル割り当てメッセージ５２でＬＳＲ３に渡す。また、アグリゲートの終端を示すために、ホップカウンターに“１”を入れ、ＬＳＲ３に渡す。
７．既存ラベル“ｃ”とアグリゲート範囲において各ＬＳＰを一意に識別するためのラベル“Ａ”を受け取ったＬＳＲ３は、ＬＳＲ２に対し、ＬＳＲ２から要求された既存ラベル“ｂ”を返す。また、手順６で受け取った、ホップカウントをインクリメントして“２”とし、ラベル“Ａ”とともに、ＬＳＲ２に渡す。
８．既存ラベル“ｂ”とアグリゲート範囲において各ＬＳＰを一意に識別するためのラベル“Ａ”を受け取ったＬＳＲ２は、新規ラベル“ｅ”を発行し、ＬＳＲ６に返すとともに、ホップカウントをインクリメントして“３”とし、ＬＳＲ６に返す。ＬＳＲ６はラベルとともにこのホップカウンタの値を、設定したＬＳＰに関連付けて記憶する。
【００１６】
ここで、図６を用いて、ＬＳＲ６からＬＳＲ７へのパケットの転送処理の流れを説明する。
１．送信ノードであるＬＳＲ６は、パケットに付されるｓｈｉｍヘッダにＬＳＲ６→７へのＬＳＰに割り当てられたラベル“ｅ”を格納する。更に、パス設定時に記憶したアグリゲートの終端ノードを示す数値“３”を格納し、ＬＳＲ２に転送する。終端ノードを示す数値“３”は例えばｓｈｉｍヘッダ内のＥＸＰの領域に格納される。
２．ＬＳＲ２は、ホップカウントをデクリメントして“２”とする。また、入力インターフェース番号２とラベル“ｅ”によりラベルテーブル６０を参照して、ラベル“ｅ”の代わりに、共通経路においてＬＳＰ６→７を一意に識別するためのラベル“Ａ”と、ＬＳＲ２，３間の転送処理を示すラベル“ｂ”をパケットに付加し、ＬＳＲ３に転送する。これにより、経路２，３，４におけるＬＳＰ１→５とＬＳＰ６→７のアグリゲートを実現する。
３．ＬＳＲ３は、ホップカウントをデクリメントして“１”とする。また、ラベルテーブル６２を参照してラベル“ｂ”をＬＳＲ３，４間の転送処理を示す“ｃ”に張り替え、ＬＳＲ４に転送する。
４．ＬＳＲ４は、ホップカウントをデクリメントする。ここでホップカウントが“０”となるため、ＬＳＲ４は共通経路の終端であると認識し、ラベル“ｃ”をはずし、そして、ラベルテーブル６４を参照してアグリゲーション範囲における転送処理を示すラベル“Ａ”をラベル“ｆ”に張り替え、転送する。これによってＬＳＰ６→７のセグリゲートを実現する。
【００１７】
本発明におけるラベル要求メッセージオブジェクトの一例を図７に示す。Ｌａｂｅｌ  ＴＬＶの内容としてのＬａｂｅｌに新規ラベルを要求する場合、ＮＵＬＬが、既存のラベルを指定する場合はそのラベルが格納される。
本発明におけるラベル割り当てメッセージオブジェクトの一例を図８に示す。Ａｇｇｒｅｇａｔｅ  Ｌａｂｅｌ  ＴＬＶのＬａｂｅｌには、アグリゲート範囲においてＬＳＰに配布されるラベル値が、アグリゲートしない場合はＮＵＬＬが入る。また、ホップカウンターには、デフォルト（アグリゲートしない場合）でＮＵＬＬ、アグリゲートする場合には、１以上の数字が入る。
【００１８】
本発明のアグリゲート方法を用いれば、図９に示すようにホップ（リンク）単位での柔軟なアグリゲートが可能となる。図９において、ＬＳＰ７０はＬＳＲ１−２間でＬＳＰ７２とアグリゲートされており、ＬＳＲ２−３間ではＬＳＰ７２およびＬＳＰ７４とアグリゲートされている。またＬＳＰ７４はＬＳＰ７２とＬＳＲ２−４間でアグリゲートされている。
【００１９】
（付記１）終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケット転送する際のパスのアグリゲート方法であって、
（ａ）第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含むパケットを、第１のパスの始点ノードから送出し、
（ｂ）第２のパスとの共通経路において、第２のパスのルーティング情報を使ってパケットをルーティングし、
（ｃ）パケットに指定された、第２のパスとの共通経路の終点のノードに到達したとき、第２のパスから別かれて第１のパスへパケットをルーティングするステップを具備するパスのアグリゲート方法。                          （１）
（付記２）前記共通経路の終点のノードの位置は、第１のパスの始点ノードから共通経路の終点のノードまでのホップ数を含み、
（ｄ）ノードを通過するごとにパケットに含まれるホップ数をデクリメントし、それによって共通経路の終点のノードにパケットが到達したことを認識するステップをさらに具備する付記１記載の方法。
【００２０】
（付記３）（ｅ）共通経路内において、第２のパスに割り当てられたラベルを第１のパスの第１のレイヤのラベルとして第１のパスにも割り当て、かつ、第１のパスを識別するラベルを第１のパスの第２のレイヤのラベルとして第１のパスにさらに割り当てるステップをさらに具備し、
ステップ（ｂ）は、該第１のレイヤのラベルを用いてパケットをルーティングするサブステップを含み、
ステップ（ｃ）は、該第２のレイヤのラベルを用いてパケットをルーティングすることにより、第２のパスから別かれて第１のパスへパケットをルーティングするサブステップを含む付記１記載の方法。                          （２）
（付記４）ステップ（ｅ）は、第１のパスのラベル要求メッセージに第２のパスに割り当てられたラベルを格納して要求することにより、第２のパスに割り当てられたラベルを第１のパスにも割り当てるサブステップを含む付記３記載の方法。                                                              （３）
（付記５）終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、
第１のパスに関連付けて第２のパスとの共通経路の終点のノードの位置を記憶する手段と、
第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含むパケットを送出する手段とを具備するノード装置。
【００２１】
（付記６）前記共通経路の終点のノードの位置は、自ノードから共通経路の終点のノードまでのホップ数を含む付記５記載のノード装置。            （４）
（付記７）終点ノードを含まない範囲で第２のパスとの共通経路を有する第１のパスに沿ってパケットを転送する際にパスをアグリゲートすることの可能なノード装置であって、
第１のパスの識別子と、第２のパスとの共通経路の終点のノードの位置とを含み、第２のパスとの共通経路において、第２のパスのルーティング情報を使ってルーティングされたパケットを受信する手段と、
受信されたパケット内の指定に基づき、自ノードが第２のパスとの共通経路の終点のノードであるとき、第２のパスから別かれて第１のパスへパケットをルーティングする手段とを具備するノード装置。                          （５）
（付記８）前記共通経路の終点のノードの位置は、第１のパスの始点ノードから共通経路の終点のノードまでのホップ数を含み、パケットに含まれるホップ数をデクリメントし、それによって自ノードが共通経路の終点のノードであることを認識する手段をさらに具備する付記７記載のノード装置。
【００２２】
【発明の効果】
以上述べたように本発明によれば、どんな経路をとるＬＳＰに対しても、他のＬＳＰと少なくとも１ホップ以上の共通経路を持っていれば、それをアグリゲート範囲として設定することができ、その共通経路に基づいた、柔軟なアグリゲート、およびセグリゲートが可能となる。
【図面の簡単な説明】
【図１】ＭＰＬＳにおけるＬＳＰの例を示す図である。
【図２】従来技術としてのラベルマージを説明する図である。
【図３】本発明が適用されるＬＳＰの例を示す図である。
【図４】ＬＳＰ３０を設定するためのラベル配布プロトコルを説明する図である。
【図５】ＬＳＰ３２を設定するためのラベル配布プロトコルを説明する図である。
【図６】本発明によるパスのアグリケート結果を示す図である。
【図７】本発明におけるラベル要求メッセージオブジェクトの一例を示す図である。
【図８】本発明におけるラベル割り当てメッセージオブジェクトの一例を示す図である。
【図９】本発明による柔軟なアグリゲートを説明する図である。
【符号の説明】
１０，１２，３０，３２…ＬＳＰ（ラベルスイッチドパス）
１４，１６，１８，２０，２２，６０，６２，６４…ラベルテーブル
３４，３６，４２，４４，４８…ラベル要求メッセージ
３８，４０，５０，５２…ラベル割り当てメッセージ
【図１】
0004169493.tif 000002
【図２】
0004169493.tif 000003
【図３】
0004169493.tif 000004
【図４】
0004169493.tif 000005
【図５】
0004169493.tif 000006
【図６】
0004169493.tif 000007
【図７】
0004169493.tif 000008
【図８】
0004169493.tif 000009
【図９】
0004169493.tif 000010