(57)【特許請求の範囲】
【請求項１】
ラベル転送ネットワークでリスタートを行うリスタート方法であって、
リスタートを行うリスタートノードは、前記リスタートノードの処理能力に基づいたノード数の隣接ノードを選択してリスタートグループとし、前記リスタートグループの隣接ノードに対してリスタートを通知し、
前記リスタートノードは、前記リスタートグループの隣接ノードから通知されたパスのラベル値を基に、パスとラベルを対応付けるラベルテーブル内で前記通知されたパスに対応するエントリを復元し、
前記リスタートの通知と前記通知されたパスに対応するエントリの復元とを繰り返して前記ラベルテーブルの復元を行う
ことを特徴とするリスタート方法。
【請求項２】
請求項１記載のリスタート方法において、
前記リスタートノードに、優先度毎に、隣接ノードと、前記隣接ノードと自ノード間のパス数を登録したノード情報テーブルを設け、
前記ノード情報テーブルを優先度が高い順に検索して前記リスタートノードの処理能力に基づいたノード数の隣接ノードを選択する
ことを特徴とするリスタート方法。
【請求項３】
請求項２記載のリスタート方法において、
前記選択する隣接ノードは、前記ノード情報テーブルを優先度が高い順に検索して、前記隣接ノード毎に前記隣接ノードと自ノード間のパス数を加算し、合計値が前記リスタートを行うノード装置の処理能力に応じた所定値を超過する直前までに検索された隣接ノードである
ことを特徴とするリスタート方法。
【請求項４】
請求項３記載のリスタート方法において、
前記ノード情報テーブルは、隣接ノードから新たなパスが設定されたとき、前記新たなパスの優先度と、前記隣接ノードが既に登録されている前記ノード情報テーブルの優先度とを比較して前記新たなパスの優先度が高い場合には、前記隣接ノードを登録する前記ノード情報テーブルの優先度を前記新たなパスの優先度に変更する
ことを特徴とするリスタート方法。
【請求項５】
ラベル転送ネットワークでリスタートを行うノード装置であって、
自ノード装置の処理能力に基づいたノード数の隣接ノードを選択してリスタートグループとし、前記リスタートグループの隣接ノードに対してリスタートを通知する通知手段と、
前記リスタートグループの隣接ノードから通知されたパスのラベル値を基に、パスとラベルを対応付けるラベルテーブル内で前記通知されたパスに対応するエントリを復元する復元手段と、を有し、
前記通知手段による通知と前記復元手段による復元とを繰り返して前記ラベルテーブルの復元を行う
ことを特徴とするノード装置。
【請求項６】
請求項５記載のノード装置において、
優先度毎に、隣接ノードと、前記隣接ノードと自ノード間のパス数を登録したノード情報テーブルを有し、
前記通知手段は、前記ノード情報テーブルを優先度が高い順に検索して前記自ノード装置の処理能力に基づいたノード数の隣接ノードを選択する
ことを特徴とするノード装置。
【請求項７】
請求項６記載のノード装置において、
前記通知手段は、前記ノード情報テーブルを優先度が高い順に検索して、前記隣接ノード毎に前記隣接ノードと自ノード間のパス数を加算し、合計値が前記リスタートを行うノード装置の処理能力に応じた所定値を超過する直前までに検索された隣接ノードを選択する
ことを特徴とするノード装置。
【請求項８】
請求項７記載のノード装置において、
隣接ノードから新たなパスが設定されたとき、前記新たなパスの優先度と、前記隣接ノードが既に登録されている前記ノード情報テーブルの優先度とを比較して前記新たなパスの優先度が高い場合には、前記隣接ノードを登録する前記ノード情報テーブルの優先度を前記新たなパスの優先度に変更する変更手段を
有することを特徴とするノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベル転送ネットワークでリスタートを行うリスタート方法及びノード装置に関する。
【背景技術】
【０００２】
近年、パケットにラベルを付与してデータを転送するＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）を用いたラベル転送ネットワークが一般化している。
【０００３】
一方、ＲＳＶＰ（Ｒｅｓｏｕｒｃｅ  ｒｅＳｅｒＶａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）はネットワーク上で送信先までの帯域を予約し、通信品質を確保するプロトコルである。現在のインターネットではどのデータも平等に扱われているため、テレビ会議やリアルタイムの動画像配信など、即時性、連続性が求められるトラフィックを優先させる目的で開発されたものである。
【０００４】
技術標準文書ＲＦＣ（Ｒｅｑｕｅｓｔ  Ｆｏｒ  Ｃｏｍｍｅｎｔｓ）３２０９などで規定されたＲＳＶＰ−ＴＥ（ＲＳＶＰ−Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇ）はＲＳＶＰに対してＭＰＬＳで利用するラベルを予約できるように拡張したものであり、隣接装置故障やリンク故障の検出のためにハローメッセージが定義されている。
【０００５】
グレースフルリスタート（Ｇｒａｃｅｆｕｌ−Ｒｅｓｔａｒｔ）はＲＳＶＰ−ＴＥシグナリングを用いるＭＰＬＳ通信装置で用いられる。すなわち、コントロールプレンでハローメッセージやＰａｔｈメッセージやＲｅｓｖメッセージが途切れた場合であっても、データプレンの通信を継続させ、コントロールプレンの障害が復旧した後で状態情報（Ｐａｔｈ状態情報、Ｒｅｓｖ状態情報）を障害前の状態に復旧させるために用いられる。なお、ハローメッセージは障害検出などに使用され、Ｐａｔｈメッセージはパスの設定などに使用され、Ｒｅｓｖメッセージは受信応答などに使用される。
【０００６】
グレースフルリスタートは、リスタートしたときに隣接ノードからのメッセージを基にリスタート前の状態を復元する。このため、多数の隣接ノードとの間で多数のＬＳＰ（Ｌａｂｅｌ  Ｓｗｉｔｃｈｅｄ  Ｐａｔｈ）が設定されているときにリスタートすると、リスタートノードで大量の処理が発生する。
【０００７】
グレースフルリスタートではリスタートしたことを隣接ノードへ示すためにリスタートノードからハローメッセージを送信するが、このハローメッセージが予め設定されているリスタートタイム内で隣接ノードに受信されないと、新たなラベルを取得する処理が実施され、新たなラベルを取得する処理の間はデータプレンで通信断が発生する。
【０００８】
図１にグレースフルリスタートの一例のシーケンス図を示す。ここでは、隣接ノードをリスタートノードの上流、下流に各１ノードずつ接続した状態で記載しているが、実際にはリスタートノードの上流、下流それぞれに複数のノードが接続されている。
【０００９】
シーケンスＳＱ１：リスタートノードはハローメッセージ内で「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を送信し、隣接ノードに対しグレースフルリスタートであることを通知する。「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」で予めリスタートタイムを通知し、再起動にかかる最大時間を通知する。上流及び下流の隣接ノードは「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を受信すると、送信元ノードがグレースフルリスタート可能であることを認識する。
【００１０】
シーケンスＳＱ２：通常通りＬＳＰを作成する。そして、ＰａｔｈメッセージやＲｅｓｖメッセージでラベル交換を行う。
【００１１】
シーケンスＳＱ３：リスタートノードは再起動した後にラベルテーブルの全エントリの「ｓｔａｌｅ」にマーキングを行う。リスタートノードはハローメッセージ中の「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」でリカバリタイムを指定し、このリカバリタイム内でラベルテーブルをリフレッシュして復元するリカバリ処理を行うことを上流及び下流の隣接ノードに通知する。
【００１２】
シーケンスＳＱ４：上流及び下流の隣接ノードはハローメッセージの「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を受信すると、ラベルテーブルのうちリスタートノードに対応するエントリの「ｓｔａｌｅ」にマーキングを行う。
【００１３】
シーケンスＳＱ５：上流の隣接ノードはＰａｔｈメッセージの「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」を用い、リフレッシュを行うＬＳＰでリスタートノードが配布していたラベルをリスタートノードに通知する。
【００１４】
シーケンスＳＱ６：リスタートノードは通知されたＰａｔｈメッセージの「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」のラベル値を基にラベルテーブルを参照し、下流の隣接ノードから配布されていたラベル値を取得する。それを基にＬＳＰと上流のノードに配布したラベル値、下流のノードから配布されたラベル値を取得し、ＲＳＶＰ−ＴＥの状態を復旧し、かつ、ラベルテーブルの「ｓｔａｌｅ」を削除する。
【００１５】
図２にラベルテーブルの一例の構成図を示す。ラベルテーブルは、ＬＳＰ番号毎に、入力ラベル値（ｉｎ）と、出力ラベル値（ｏｕｔ）と、ネクストホップ（ＮＨ）と、ｓｔａｌｅとを有している。シーケンスＳＱ６では例えば上流隣接ノードから入力ラベル値＝２０のＰａｔｈメッセージがリスタートノードに供給される。リスタートノードでは入力ラベル値＝２０でラベルテーブルを参照して出力ラベル値＝１０とネクストホップ＝ＩＰａを得る。リスタートノードはラベルテーブルの当該エントリの「ｓｔａｌｅ」のマーキングを削除し、Ｐａｔｈメッセージのラベル値を出力ラベル値＝１０に変更し、ネクストホップ＝ＩＰａに対応する下流隣接ノードに向けて送信する。
【００１６】
シーケンスＳＱ７：リスタートノードはＰａｔｈメッセージの「Ｓｕｇｇｅｓｔｅｄ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」を用い、当該ＬＳＰで下流の隣接ノードが配布していたラベルを下流の隣接ノードに通知する。これを受信した下流の隣接ノードはラベルテーブルの「ｓｔａｌｅ」を削除する。この後、下流の隣接ノードからのＲｅｓｖメッセージがリスタートノードを経て上流の隣接ノードに通知されると、上流の隣接ノードはラベルテーブルの「ｓｔａｌｅ」のマーキングを削除する。
【００１７】
シーケンスＳＱ８：全ＬＳＰについてシーケンスＳＱ４〜ＳＱ７を繰り返すことにより、リスタートノードはラベルテーブルの全状態を復元する。リスタートノードはリカバリタイムが経過すると、リフレッシュされていないＬＳＰをラベルテーブルから削除するために、「ｓｔａｌｅ」にマーキングが残っているエントリを削除する。
【００１８】
シーケンスＳＱ９：隣接ノードはリスタートノードから受信したリカバリタイムが経過すると、リフレッシュされていないＬＳＰをラベルテーブルから削除するために、「ｓｔａｌｅ」にマーキングされたエントリを削除する。
【００１９】
ところで、通信ネットワーク内の回線上における障害の発生を検出した場合に、障害が発生した回線を通過する複数のトンネルの切断メッセージを集約して、障害の発生を回線単位で隣接ノードに通知するトンネル障害通知装置が提案されている（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００６−３３１２４号公報
【発明の概要】
【発明が解決しようとする課題】
【００２１】
図３にグレースフルリスタートのリカバリ処理の輻輳例のシーケンス図を示す。図１ではリスタートノードの隣接ノードは上流、下流に各１ノードずつで記載しているが、実際には複数のノードが接続されている。
【００２２】
この場合、再起動時にリスタートノードはシーケンスＳＱ４で全ての隣接ノードにハローメッセージを送信し、全ての隣接ノードよりハローメッセージを受信する。
【００２３】
シーケンスＳＱ５でリスタートノードは「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きのＰａｔｈメッセージによりラベルを受信する。
【００２４】
シーケンスＳＱ６でリスタートノードはＬＳＰのリカバリ処理を行ってラベルテーブルを復元する。
【００２５】
シーケンスＳＱ７でリスタートノードは下流隣接ノードがあればＰａｔｈメッセージを送信する。
【００２６】
上記のシーケンスＳＱ５において上流の全ての隣接ノードから「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きＰａｔｈメッセージを受信してシーケンスＳＱ６のリカバリ処理を行うので、リカバリ処理が輻輳する場合がある。
【００２７】
なお、技術標準文書ＲＦＣ３４７３では、上流の隣接ノードでの「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きのメッセージを分散して送信することなどが規定されているが、リスタートノードでの対処については言及されておらず、リスタートノードでは複数の上流隣接ノードから同時に「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きのＰａｔｈメッセージを受信する。
【００２８】
その結果、リカバリタイム内でラベルテーブルの全エントリの復元ができない場合があり、復元できなかったリスタートノードは再度ラベル取得処理を実行するため、データプレンにおける通信断が発生するという問題があった。
【００２９】
近年のネットワークでは、１つのノードに収容するＬＳＰ数が増加しているため、シーケンスＳＱ４のハローメッセージ送受後に、１つの隣接ノードからリスタートノードに返ってくるシーケンスＳＱ５の「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きＰａｔｈメッセージ数が増加している。また、各ノードの制御処理速度が上がったため、シーケンスＳＱ４のハローメッセージ送受後に、各隣接ノードからリスタートノードに返ってくるシーケンスＳＱ５の「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きＰａｔｈメッセージ受信までの遅延差が小さくなっている。また、ＬＳＰ別のＰａｔｈメッセージ送信間隔が短くなっている。
【００３０】
以上の状況から、各ノードが返すシーケンスＳＱ５の「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」付きＰａｔｈメッセージ受信によるシーケンスＳＱ６のＬＳＰ処理が短時間に集中し、リカバリ処理の輻輳が生じるという問題があった。
【００３１】
開示のリスタート方法は、リカバリ処理の輻輳を抑制することを目的とする。
【課題を解決するための手段】
【００３２】
開示の一実施形態によるリスタート方法は、ラベル転送ネットワークでリスタートを行うリスタート方法であって、
リスタートを行うリスタートノードは、前記リスタートノードの処理能力に基づいたノード数の隣接ノードを選択してリスタートグループとし、前記リスタートグループの隣接ノードに対してリスタートを通知し、
前記リスタートノードは、前記リスタートグループの隣接ノードから通知されたパスのラベル値を基に、パスとラベルを対応付けるラベルテーブル内で前記通知されたパスに対応するエントリを復元し、
前記リスタートの通知と前記通知されたパスに対応するエントリの復元とを繰り返して前記ラベルテーブルの復元を行う。
【発明の効果】
【００３３】
本実施形態によれば、リカバリ処理の輻輳を抑制することができる。
【図面の簡単な説明】
【００３４】
【図１】グレースフルリスタートの一例のシーケンス図である。
【図２】ラベルテーブルの一例の構成図である。
【図３】グレースフルリスタートのリカバリ処理の輻輳例のシーケンス図である。
【図４】ノード装置の一実施形態の構成図である。
【図５】グレースフルリスタートの一実施形態のシーケンス図である。
【図６】ラベルテーブルの一実施形態の構成図である。
【図７】ノード情報テーブルの一実施形態の構成図である。
【図８】テーブル更新処理の一実施形態のフローチャートである。
【図９】リスタート順決定処理の一実施形態のフローチャートである。
【図１０】グレースフルリスタートのリカバリ処理の一実施形態のシーケンス図である。
【図１１】Ｓｅｓｓｉｏｎ＿Ａｔｔｒｉｂｕｔｅオブジェクトのフォーマットを示す図である。
【発明を実施するための形態】
【００３５】
以下、図面に基づいて実施形態を説明する。
【００３６】
＜ノード装置の構成＞
図４にノード装置の一実施形態の構成図を示す。図４において、ノード装置は複数の入出力ユニット１１−１〜１１−Ｎと、スイッチ部１２と、制御部１３を有している。入出力ユニット１１−１〜１１−Ｎそれぞれはデータ受信部１５、テーブルメモリ１６、ルート＆フォワード制御部１７、データ送信部１８を有している。データ受信部１５は複数のポートから入力される入力データの入力データチェック、ラベルチェック、制御パケットの抽出などを行う。テーブルメモリ１６にはラベルテーブルが格納される。
【００３７】
データ受信部１５は入力パケットのラベルでラベルテーブルを参照して得たネクストホップ（ＮＨ）をルート＆フォワード制御部１７に供給し、当該パケットをスイッチ部１２に供給する。ルート＆フォワード制御部１７からの制御は制御部１３内のＣＰＵ２１に通知され、ＣＰＵ２１によってスイッチ部１７のスイッチングが制御されて、当該パケットはネクストホップに応じた入出力ユニット１１−１〜１１−Ｎのデータ送信部１８に供給される。また、データ受信部１５は抽出したハローメッセージやＰａｔｈメッセージ又はＲｅｓｖメッセージなどの制御パケットをルート＆フォワード制御部１７に供給する。
【００３８】
データ送信部１８はルート＆フォワード制御部１７の制御に応じて出力するパケットのラベルを変更し、また、ルート＆フォワード制御部１７で生成された制御パケットを挿入されて複数のポートから出力する。
【００３９】
制御部１３のＣＰＵ２１はメモリ２２に格納されている各種プログラムを実行することで、スイッチ部１７のスイッチング制御処理、グレースフルリスタート処理、テーブル更新処理、リスタート順決定処理などを実施する。なお、メモリ２２にはテーブル更新処理、リスタート順決定処理で使用されるノード情報テーブルが格納される。
【００４０】
＜グレースフルリスタートの一実施形態のシーケンス＞
図５にグレースフルリスタートの一実施形態のシーケンス図を示す。ここでは、隣接ノードを上流、下流に各１ノードずつで記載しているが、実際には複数のノードが接続されている。
【００４１】
シーケンスＳＱ１１：リスタートノードはハローメッセージ内で「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を送信し、隣接ノードに対し、グレースフルリスタートであることを通知する。「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」で予めリスタートタイムを通知し、再起動にかかる最大時間を通知する。上流及び下流の隣接ノードは「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を受信すると、送信元ノードがグレースフルリスタート可能であることを認識する。
【００４２】
シーケンスＳＱ１２：通常通りＬＳＰを作成する。そして、ＰａｔｈメッセージやＲｅｓｖメッセージでラベル交換を行う。なお、上流の隣接ノードは当該Ｐａｔｈメッセージに優先度（Ｐｒｉｏｒｉｔｙ）を含めてリスタートノードに送信する。
【００４３】
ここで、優先度の情報はＭＰＬＳのラベル配布プロトコルであるＬＤＰ（Ｌａｂｅｌ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）メッセージ内のＳｅｓｓｉｏｎ＿Ａｔｔｒｉｂｕｔｅのセットアッププライオリティ値や、ホールドプライオリティ値を使用して送信する。図１１にＳｅｓｓｉｏｎ＿Ａｔｔｒｉｂｕｔｅオブジェクトのフォーマットを示す。セットアッププライオリティ値はＬＳＰトンネルを確立する際の優先度を示す。ホールドプライオリティ値は他のＬＳＰトンネルによる経路使用の競合が発生した際に原稿のパスを保持する優先度を示す。この他に、ＰａｔｈメッセージやＲｅｓｖメッセージ等のＬＤＰメッセージにおける未使用ビットを使用して優先度の送信を行っても良い。
【００４４】
なお、ＬＳＰを設定する場合にはＰａｔｈメッセージのＴＩＭＥ＿ＶＡＬＵＥでリフレッシュ間隔が設定され、その後、上記リフレッシュ間隔内にＬＳＰを確認してリフレッシュする必要がある。このため、上記Ｐａｔｈメッセージで明示されたリフレッシュ間隔（ＴＩＭＥ＿ＶＡＬＵＥ）が短いＬＳＰを優先度の高いパスと判断することも可能である。即ちリフレッシュ間隔から優先度を設定しても良い。また、上記の方法を組み合わせて優先度を設定しても良い。
【００４５】
リスタートノードは従来通り上流、下流の隣接ノードとラベル交換を行い、ラベル情報（入力ラベル値（ｉｎ），出力ラベル値（ｏｕｔ））に加えて、上流ノード情報と、受信した当ＬＳＰの優先度をラベルテーブルに書き込む。そして、後述するテーブル更新処理を実行する。
【００４６】
図６にラベルテーブルの一実施形態の構成図を示す。ラベルテーブルは、ＬＳＰ番号をエントリとして、送信元のノード名と、入力ラベル値（ｉｎ）と、出力ラベル値（ｏｕｔ）と、ネクストホップ（ＮＨ）と、優先度（Ｐｒｉｏｒｉｔｙ）と、ｓｔａｌｅとを有している。
【００４７】
シーケンスＳＱ１３：リスタートノードは再起動した後にラベルテーブルの全エントリの「ｓｔａｌｅ」にマーキングを行う。
【００４８】
シーケンスＳＱ１４：リスタートノードはリスタート順決定処理を実行してリスタートを行う一又は複数の隣接ノードを選択する。リスタートノードはハローメッセージ中の「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」でリカバリタイムを指定し、このリカバリタイム内に、リスタート順決定処理で選択された一又は複数の隣接ノードである上流の隣接ノードと下流の隣接ノードに対し、ラベルテーブルをリフレッシュして復元するリカバリ処理を行うことを通知する。上流及び下流の隣接ノードはハローメッセージの「Ｒｅｓｔａｒｔ＿Ｃａｐオブジェクト」を受信すると、ラベルテーブルのうちリスタートノードに対応するエントリの「ｓｔａｌｅ」にマーキングを行う。
【００４９】
シーケンスＳＱ１５：上流の隣接ノードはＰａｔｈメッセージの「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」を用い、リフレッシュを行うＬＳＰでリスタートノードが配布していたラベルを通知する。
【００５０】
シーケンスＳＱ１６：リスタートノードは通知されたＰａｔｈメッセージの「Ｒｅｃｏｖｅｒｙ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」のラベル値を基にラベルテーブルを参照し、下流の隣接ノードから配布されていたラベル値を取得する。それを基にＬＳＰと上流のノードに配布したラベル値、下流のノードから配布されたラベル値を取得し、ＲＳＶＰ−ＴＥの状態を復旧し、かつ、ラベルテーブルの「ｓｔａｌｅ」を削除する。
【００５１】
例えば上流の隣接ノードＡから入力ラベル値＝２０のＰａｔｈメッセージがリスタートノードに供給されると、図６の第１行に示すように、リスタートノードでは入力ラベル値＝２０でラベルテーブルを参照して出力ラベル値＝１０とネクストホップ＝ＩＰａを得る。リスタートノードはラベルテーブルの当該エントリの「ｓｔａｌｅ」のマーキングを削除し、Ｐａｔｈメッセージのラベル値を出力ラベル値＝１０に変更し、ネクストホップ＝ＩＰａに対応する下流の隣接ノードに向けて送信する。
【００５２】
シーケンスＳＱ１７：リスタートノードはＰａｔｈメッセージの「Ｓｕｇｇｅｓｔｅｄ  Ｌａｂｅｌ  Ｏｂｊｅｃｔ」を用い、当該ＬＳＰで下流の隣接ノードが配布していたラベルを下流の隣接ノードに通知する。これを受信した下流の隣接ノードはラベルテーブルの「ｓｔａｌｅ」を削除する。この後、下流の隣接ノードからのＲｅｓｖメッセージがリスタートノードを経て上流の隣接ノードに通知されると、上流の隣接ノードはラベルテーブルの「ｓｔａｌｅ」のマーキングを削除する。
【００５３】
シーケンスＳＱ１８：全ＬＳＰについてシーケンスＳＱ１４〜ＳＱ１７を繰り返すことにより、リスタートノードは全状態を復旧する。リスタートノードはリカバリタイムが経過すると、リフレッシュされていないＬＳＰをラベルテーブルから削除するために、「ｓｔａｌｅ」にマーキングされたエントリを削除する。
【００５４】
シーケンスＳＱ１９：隣接ノードはリスタートノードから受信したリカバリタイムが経過すると、リフレッシュされていないＬＳＰをラベルテーブルから削除するために、「ｓｔａｌｅ」にマーキングされたエントリを削除する。
【００５５】
＜ノード情報テーブルの構成＞
図７にノード情報テーブルの一実施形態の構成図を示す。ノード情報テーブルはメモリ２２内に優先度毎に作成される。図７（Ａ）は優先度０のノード情報テーブルを示し、図７（Ｂ）は優先度１のノード情報テーブルを示し、図７（Ｃ）は優先度２のノード情報テーブルを示す。なお、優先度の値が小さいほど優先度が高い（優先される）ものとする。各優先度のノード情報テーブルは、上流の隣接ノード名をエントリとして、当該上流の隣接ノードと自ノード（つまりリスタートノード）間に作成されたＬＳＰ数を登録している。
【００５６】
例えば図７（Ａ）では、第１のエントリが上流の隣接ノードＡとの間にＮａ個のＬＳＰが作成され、上記Ｎａ個のＬＳＰのうち最も高い優先度が優先度０であることを表している。また、図７（Ｂ）では、第１のエントリが上流の隣接ノードＥとの間にＮｅ個のＬＳＰが作成され、上記Ｎａ個のＬＳＰのうち最も高い優先度が優先度１であることを表している。
【００５７】
＜テーブル更新処理＞
図８にテーブル更新処理の一実施形態のフローチャートを示す。このテーブル更新処理はシーケンスＳＱ１２で実行される。このテーブル更新処理は上流の隣接ノードからＬＳＰ作成要求が通知されると実行を開始する。
【００５８】
図８において、ステップＳ１でデータ受信部１５は上流の隣接ノードから受信したＬＳＰ作成要求に従ってテーブルメモリ１６内のラベルテーブルにＬＳＰを追加する。ここでは、例えば上流の隣接ノードｘから優先度ｙのＬＳＰを追加することにする。
【００５９】
次に、ステップＳ２でＣＰＵ２１はＬＳＰ作成要求を送信元である上流の隣接ノードｘを用いてメモリ２２内のノード情報テーブルを検索する。これにより、例えば優先度ｚのノード情報テーブルで上流の隣接ノードｘを検索できたものとする。なお、隣接ノードｘを検索できなかった場合には優先度ｚとして最大値（最も低い優先度）を設定する。
【００６０】
次に、ステップＳ３でＣＰＵ２１は検索で得たノード情報テーブルの優先度ｚとＬＳＰ作成要求の優先度ｙを比較して、ｚ＜ｙであればステップＳ４に進み、ｚ≧ｙであればステップＳ６に進む。ステップＳ４でＣＰＵ２１は優先度ｙのノード情報テーブルに隣接ノードｘのエントリを追加し、ステップＳ５でＣＰＵ２１は優先度ｚのノード情報テーブルから隣接ノードｘのエントリを削除する。
【００６１】
なお、上記ステップＳ４では優先度ｚのノード情報テーブルから隣接ノードｘのエントリをコピーして優先度ｙのノード情報テーブルに貼り付ける。つまり、隣接ノードｘからの新たに作成するＬＳＰの優先度が、それまでの隣接ノードｘからのＬＳＰの優先度より高い場合には隣接ノードｘの優先度を新たに作成するＬＳＰの優先度に更新する。
【００６２】
ステップＳ５の実行後、又は、ステップＳ３でｚ≧ｙであればステップＳ６に進む。ステップＳ６でＣＰＵ２１は優先度ｙ又はｚのノード情報テーブルで隣接ノードｘのエントリのＬＳＰ数Ｎｘに１を加算する。この結果、上流の隣接ノードは所持するＬＳＰのうち最も高い優先度に該当するテーブルに属することとなる。
【００６３】
＜リスタート順決定処理＞
図９にリスタート順決定処理の一実施形態のフローチャートを示す。リスタート順とはリスタート時にリスタートノードかあらハローメッセージを送信する隣接ノードの順番である。このリスタート順決定処理では隣接ノードの優先度に従い、自ノードのノード処理能力に合わせてリスタート順を決定して行く。ここで、ノード処理能力とは、リスタートノードがリカバリタイム内にリカバリ処理が可能なＬＳＰ数を表し、ノードの演算速度等によって決定される。自ノードのノード処理能力（ＬＳＰ数）についてはハードウェアによって決定される上限値以下であれば、対向装置などの処理能力に合わせて自由に設定してよい。
【００６４】
図９において、装置リスタート後、ステップＳ１１でＣＰＵ２１はノード情報テーブルを参照し、高優先度の優先度０のテーブルに属する隣接ノードから順々にＬＳＰ数を合計ＬＳＰ数に加算し、ステップＳ１２で合計ＬＳＰ数がノード処理能力のＬＳＰ数を超過したか否かを判別する。合計ＬＳＰ数が自ノード処理能力のＬＳＰ数未満であると、ステップＳ１３でＣＰＵ２１はノード情報テーブルにおける次の隣接ノードのＬＳＰ数を加算してステップＳ１２の判別を繰り返す。
【００６５】
ステップＳ１２で合計ＬＳＰ数がノード処理能力のＬＳＰ数を超過した場合は加算を中止し、ステップＳ１４でノード処理能力のＬＳＰ数を超過する直前の隣接ノードまでの複数の隣接ノードをリスタートグループとし、このリスタートグループの複数の隣接ノードに対しハローメッセージを送信する。そして、このリスタートグループの隣接ノードからの全てのＬＳＰのリフレッシュが行われる。
【００６６】
次に、ステップＳ１５でＣＰＵ２１は合計ＬＳＰ数をクリアつまりゼロリセットし、前回のＬＳＰ数の加算において、最後に加算した隣接ノードをＣＰＵ２１はノード情報テーブルにおける次の隣接ノードに設定してステップＳ１３に進む。そして、ステップＳ１３でＣＰＵ２１はノード情報テーブルにおける次の隣接ノードのＬＳＰ数を合計ＬＳＰ数に加算してステップＳ１２の判別を繰り返す。
【００６７】
例えば図７に示す例では、まず図７（Ａ）の優先度０のノード情報テーブルに属するＬＳＰ数Ｎａ，Ｎｂ，Ｎｃを加算して行く。合計ＬＳＰ数が自ノード処理能力を超過した場合は加算を中止し、処理能力範囲内までの例えば隣接ノードＡ，Ｂを第１リスタートグループとし、第１リスタートグループの隣接ノードＡ，Ｂに対してハローメッセージを送信し、リカバリ処理を実行する。その後、ＬＳＰ数をクリアし、前回計算時の最後に加算したノードＣから、再び同様の処理を実施する。
【００６８】
再計算により求められた第２リスタートグループについては、前回ハローメッセージを送信した第１リスタートグループについてのリカバリ処理が全て完了した後にハローメッセージを送信し、リカバリ処理を実行して行く。計算において優先度０のノード情報テーブルのノードを加算し終えたら、次は優先度１のノード情報テーブルに属するノードのＬＳＰ数Ｎｅ，Ｎｆ，…を加算して行く。これらの処理を全てのノード情報テーブルに記録された全てのノードに対して実行する。
【００６９】
図１０にグレースフルリスタートのリカバリ処理の一実施形態のシーケンス図を示す。図１０において、リスタートノードであるノード＃１は障害発生から再起動し（シーケンスＳＱ２３ａ）、ノード＃１から上流の隣接ノード＃２に対しハローメッセージを送信する（シーケンスＳＱ２４ａ）。
【００７０】
ノード＃１はノード＃２のリカバリ処理完了後（シーケンスＳＱ２５ａ〜ＳＱ２７ａ）、ノード＃３に対してハローメッセージを送信し（シーケンスＳＱ２４ｂ）、ノード＃２と同様にリカバリ処理を実施する（シーケンスＳＱ２５ｂ〜ＳＱ２７ｂ）。以降も同様にノード＃４，ノード＃５とリカバリ処理を繰り返す。
【００７１】
図１０ではノード＃２〜５は個別のノードとして表現しているが、ノード＃２〜５をリスタートグループとしても良く、ノード＃１からリスタートグループ＃２に対してリカバリ処理する。この時、リスタートグループ＃２に含まれるＬＳＰの数はノード＃１がリカバリタイム内にリカバリ処理を完了できる範囲の数である。その後、同様にリスタートグループ＃３，リスタートグループ＃４と処理を繰り返す。
【００７２】
また、ハローメッセージの送信順に関しては、ＬＳＰの優先度に基づいてノード情報テーブルから決定されたリスタート順に従う。ところで予め設定されるリスタートタイム内に復旧できないノード（又はリスタートグループ）＃３，＃４に対しては、図１０に示すように、新たにリスタートタイムの延長を行っても良い（シーケンスＳＱ２８ｂ，ＳＱ２９ｂ）。
【００７３】
本実施形態では、リスタートノードから隣接ノードに対するハローメッセージをリスタートノード自身が処理可能な数の上流の隣接ノードに対してのみ送信する。そのリカバリ処理完了後、同様のプロセスにて処理可能な数の別の上流の隣接ノードに対してハローメッセージを送信し、リカバリ処理を行う。以降、上記の操作を順次繰り返してリカバリ処理を実施することで、リカバリ処理の輻輳を回避することができ、円滑にリスタートすることができる。
【００７４】
ここで、ＭＰＬＳラベルには２０ビットのフィールドが割り当てられており、ラベル値は０〜１０４８５７５の間で付与される。仮に、リカバリ処理輻輳により１０４８５７５個全てのラベルについて新ラベルの取得処理が行われたとする。１ラベルの取得処理に要する時間を１ｍｓとすると、この場合の通信断時間は、１０４８５７５×１ｍｓ＝１０４８．６ｓ≒１７ｍｉｎとなるが、本実施形態により、上記の通信断時間を０にすることが可能となる。
（付記１）
ラベル転送ネットワークでリスタートを行うリスタート方法であって、
リスタートを行うリスタートノードは、前記リスタートノードの処理能力に基づいたノード数の隣接ノードを選択してリスタートグループとし、前記リスタートグループの隣接ノードに対してリスタートを通知し、
前記リスタートノードは、前記リスタートグループの隣接ノードから通知されたパスのラベル値を基に、パスとラベルを対応付けるラベルテーブル内で前記通知されたパスに対応するエントリを復元し、
前記リスタートの通知と前記通知されたパスに対応するエントリの復元とを繰り返して前記ラベルテーブルの復元を行う
ことを特徴とするリスタート方法。
（付記２）
付記１記載のリスタート方法において、
前記リスタートノードに、優先度毎に、隣接ノードと、前記隣接ノードと自ノード間のパス数を登録したノード情報テーブルを設け、
前記ノード情報テーブルを優先度が高い順に検索して前記リスタートを行うノード装置の処理能力に基づいたノード数の隣接ノードを選択する
ことを特徴とするリスタート方法。
（付記３）
付記２記載のリスタート方法において、
前記選択する隣接ノードは、前記ノード情報テーブルを優先度が高い順に検索して、前記隣接ノード毎に前記隣接ノードと自ノード間のパス数を加算し、合計値が前記リスタートを行うノード装置の処理能力に応じた所定値を超過する直前までに検索された隣接ノードである
ことを特徴とするリスタート方法。
（付記４）
付記３記載のリスタート方法において、
前記ノード情報テーブルは、隣接ノードから新たなパスが設定されたとき、前記新たなパスの優先度と、前記隣接ノードが既に登録されている前記ノード情報テーブルの優先度とを比較して前記新たなパスの優先度が高い場合には、前記隣接ノードを登録する前記ノード情報テーブルの優先度を前記新たなパスの優先度に変更する
ことを特徴とするリスタート方法。
（付記５）
付記２乃至４のいずれか１項記載のリスタート方法において、
前記優先度は、前記隣接ノードと自ノードの間で送受信されるメッセージに含まれる
ことを特徴とするリスタート方法。
（付記６）
付記２乃至４のいずれか１項記載のリスタート方法において、
前記優先度は、前記隣接ノードと自ノードの間で送受信されるメッセージに含まれるリフレッシュ間隔が短いパスほど高い値とする
ことを特徴とするリスタート方法。
（付記７）
ラベル転送ネットワークでリスタートを行うノード装置であって、
自ノード装置の処理能力に基づいたノード数の隣接ノードを選択してリスタートグループとし、前記リスタートグループの隣接ノードに対してリスタートを通知する通知手段と、
前記リスタートグループの隣接ノードから通知されたパスのラベル値を基に、パスとラベルを対応付けるラベルテーブル内で前記通知されたパスに対応するエントリを復元する復元手段と、を有し、
前記通知手段による通知と前記復元手段による復元とを繰り返して前記ラベルテーブルの復元を行う
ことを特徴とするノード装置。
（付記８）
付記７記載のノード装置において、
優先度毎に、隣接ノードと、前記隣接ノードと自ノード間のパス数を登録したノード情報テーブルを有し、
前記通知手段は、前記ノード情報テーブルを優先度が高い順に検索して前記自ノード装置の処理能力に基づいたノード数の隣接ノードを選択する
ことを特徴とするノード装置。
（付記９）
付記８記載のノード装置において、
前記通知手段は、前記ノード情報テーブルを優先度が高い順に検索して、前記隣接ノード毎に前記隣接ノードと自ノード間のパス数を加算し、合計値が前記リスタートを行うノード装置の処理能力に応じた所定値を超過する直前までに検索された隣接ノードを選択する
ことを特徴とするノード装置。
（付記１０）
付記９記載のノード装置において、
隣接ノードから新たなパスが設定されたとき、前記新たなパスの優先度と、前記隣接ノードが既に登録されている前記ノード情報テーブルの優先度とを比較して前記新たなパスの優先度が高い場合には、前記隣接ノードを登録する前記ノード情報テーブルの優先度を前記新たなパスの優先度に変更する変更手段を
有することを特徴とするノード装置。
（付記１１）
付記８乃至１０のいずれか１項記載のノード装置において、
前記優先度は、前記隣接ノードと自ノードの間で送受信されるメッセージに含まれる
ことを特徴とするノード装置。
（付記１２）
付記８乃至１０のいずれか１項記載のノード装置において、
前記優先度は、前記隣接ノードと自ノードの間で送受信されるメッセージに含まれるリフレッシュ間隔が短いパスほど高い値とする
ことを特徴とするノード装置。
【符号の説明】
【００７５】
１１−１〜１１−Ｎ  入出力ユニット
１２  スイッチ部
１３  制御部
１５  データ受信部
１６  テーブルメモリ
１７  ルート＆フォワード制御部
１８  データ送信部
２１  ＣＰＵ
２２  メモリ
【図１】
0005835043.tif 000002
【図２】
0005835043.tif 000003
【図３】
0005835043.tif 000004
【図４】
0005835043.tif 000005
【図５】
0005835043.tif 000006
【図６】
0005835043.tif 000007
【図７】
0005835043.tif 000008
【図８】
0005835043.tif 000009
【図９】
0005835043.tif 000010
【図１０】
0005835043.tif 000011
【図１１】
0005835043.tif 000012