(57)【特許請求の範囲】
【請求項１】
入力されるパケットフローを識別可能なラベル情報と少なくとも出力側インタフェースを特定する情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、
前段ノード装置から受信した、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージに基づいて、パケットフローをネットワークグローバルに識別可能なフロー識別子および該ラベルスイッチングパスの初段ノードに関する初段ノード情報を記憶する手段と、
前記ラベル割り当てメッセージと同一のフロー識別子および初段ノード情報を含むラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項２】
出力されるパケットフローを識別可能なラベル情報を使用して、ラベルスイッチングされるべきパケットを送信するノード装置であって、
ラベルスイッチングパスの設定を要求する、該ラベルスイッチングパスの初段ノードに関する初段ノード情報を少なくとも含むラベル割り当てメッセージであって、前記初段ノード情報が自ノードを指すものを受信した場合には、ラベルスイッチングパスのループが形成されるものと判断する手段を備えたことを特徴とするノード装置。
【請求項３】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、
パケットフローの経路上の隣接ノード装置との間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローをネットワークグローバルに識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、
既存のラベルスイッチングパスに対して、前記フロー識別子および前記初段ノード情報が一致するラベル割り当てメッセージを受信した場合に、前記入力側ラベル情報の内容に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項４】
前記ラベルスイッチングパスのループが形成されるものと判断された場合、受信した前記ラベル割当てメッセージに対するラベル割当てのための処理を行わないようにすることを特徴とする請求項１ないし３のいずれか１項に記載のノード装置。
【請求項５】
前記ラベルスイッチングパスのループが形成されるものと判断された場合、受信した前記ラベル割当てメッセージの送信元である前段ノード装置に対して、ラベル割当て失敗メッセージを送信することを特徴とする請求項１ないし３のいずれか１項に記載のノード装置。
【請求項６】
後段ノード装置からラベル割当て失敗メッセージを受信した場合、このラベル割当て失敗メッセージに関係するラベル割当てメッセージを自ノードに送信した前段ノード装置に対して、ラベル割当て成功メッセージを送信する手段を更に具備することを特徴とする請求項５に記載のノード装置。
【請求項７】
前記ラベル割り当てメッセージは、このラベル割り当てメッセージの送信元である前段ノード装置が割り当てた前記ラベル情報の一部または全部を構成するラベル、もしくは、ラベルスイッチングパスの一部を構成する隣接ノード間のコネクションを特定する識別子であって該ラベルを導出可能なものを含むことを特徴とする請求項１ないし６のいずれか１項に記載のノード装置。
【請求項８】
前記ラベル割り当てメッセージは、ラベルの割り当てを要求する識別子を含むものであり、
受信したラベル割り当てメッセージに対するラベル割当て処理を行っても良いと判断された場合、このラベル割り当てメッセージの送信元である前段ノード装置へ、自ノードが割り当てた前記ラベル情報の一部または全部を構成するラベル、もしくは、ラベルスイッチングパスの一部を構成する隣接ノード間のコネクションを特定する識別子であって該ラベルを導出可能なものを含む、ラベル割り当て成功メッセージを返信する手段を更に具備することを特徴とする請求項１ないし６のいずれか１項に記載のノード装置。
【請求項９】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な一つまたは複数の出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、
パケットフローの経路上の前段ノード装置との間、および、一つまたは複数の後段ノード装置それぞれとの間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、
以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項１０】
入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、
パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、
以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項１１】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであることを特徴とする請求項１０に記載のノード装置。
【請求項１２】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、
自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを後段ノード装置へ送信し、
前段ノード装置から照会メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであることを特徴とする請求項１０に記載のノード装置。
【請求項１３】
前記交換する手段は、
後段ノード装置からラベル割り当てメッセージを受信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、ラベル割り当て成功メッセージを後段ノード装置へ送信し、
前段ノード装置からラベル割り当て成功メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合にも、前記更新メッセージを後段ノード装置へ送信するものであることを特徴とする請求項１２に記載のノード装置。
【請求項１４】
後段ノード装置へ送信するメッセージ中にホップカウントをも含め、
初段ノードからのホップカウントがしきい値を越えた場合には、受信したメッセージに関するラベルスイッチングパスの設定を行わないように処理することを特徴とする請求項１ないし１３のいずれか１項に記載のノード装置。
【請求項１５】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするとともに、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置であって、
ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割当てメッセージを受信した場合、該ラベル割当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、マージした場合における初段ノード情報および更新されたホップカウント値を少なくとも含むホップカウント更新メッセージを送信する手段と、
以前に前段ノード装置から受信したラベル割り当てメッセージと同一のパケットフローにつき同一の初段ノード情報を含むホップカウント更新メッセージもしくはラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項１６】
ループが形成されると判断された場合には、ホップカウント更新もしくはラベル割り当てができないことを、ホップカウント更新もしくはラベル割り当てメッセージを自ノードに送信した前段ノード装置に通知する手段と、
ホップカウント更新ができないことを通知された場合には、ラベル割り当てができないことを、ラベル割り当てメッセージを自ノードに送信した前段ノード装置に通知する手段と、
ラベル割り当てができないことを通知された場合には、ホップカウントがしきい値を越えないならば、ホップカウント更新ができることを、ホップカウント更新メッセージを自ノードに送信した前段ノード装置に通知する手段と、
ホップカウント更新ができることを通知された場合には、設定を要求されたラベルスイッチングパスを既存のラベルスイッチングパスにマージすることにより設定する手段とを更に備えたことを特徴とする請求項１５に記載のノード装置。
【請求項１７】
ラベルスイッチングパスの設定を要求する、フロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割り当てメッセージを受信した場合、該ラベルメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものでないならば、設定を要求されたラベルスイッチングパスを既存のラベルスイッチングパスにマージすることにより設定する手段を更に備えたことを特徴とする請求項１５に記載のノード装置。
【請求項１８】
前記送信する手段は、
更新されたホップカウント値に対応する初段ノードに関する情報を、前記ホップカウント更新メッセージが含む、マージした場合における初段ノード情報とし、
マージされたラベルスイッチングパスの一部が解放されマージが行われなくなった場合に、解放されたパスに対応する初段ノード情報が前記ホップカウント更新メッセージに含まれていたならば、マージされなくなった場合における初段ノード情報とホップカウント値とを含むホップカウント更新メッセージを送信する手段を含むものであることを特徴とする請求項１５に記載のノード装置。
【請求項１９】
前記送信する手段は、
更新されたホップカウント値に対応する初段ノードもしくは既存のラベルスイッチングパスの初段ノードに関する情報を、前記ホップカウント更新メッセージが含む、マージした場合における初段ノード情報とし、
マージされたラベルスイッチングパスの一部が解放されマージが行われなくなった場合に、解放されたパスに対応する初段ノード情報が前記ホップカウント更新メッセージに含まれていたならば、マージされなくなった場合における初段ノード情報を含む更新メッセージを送信する手段を含むものであることを特徴とする請求項１５に記載のノード装置。
【請求項２０】
前記初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスを用いることを特徴とする請求項１ないし１９のいずれか１項に記載のノード装置。
【請求項２１】
前記初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスと初段ノードの出力インタフェースローカルに割り当てられる識別子とからなる組を用いることを特徴とする請求項１ないし１９のいずれか１項に記載のノード装置。
【請求項２２】
入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、
パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子を含むものを交換する手段と、
この交換されたメッセージに対応する返答メッセージを受信するまでは該メッセージに対応するラベルスイッチングパスの設定が未確定なものであることを示す情報を記憶する手段と、
新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、以前に交換したメッセージと同一のフロー識別子を含むものを受信した場合に、このフロー識別子に対応して前記未確定なものであることを示す情報が記憶されているならば、ラベルスイッチングパスのループが形成されるものと判断する手段とを備えたことを特徴とするノード装置。
【請求項２３】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであることを特徴とする請求項２２に記載のノード装置。
【請求項２４】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを前段ノード装置へ送信し、
後段ノード装置から照会メッセージを受信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを該上流のラベルスイッチングパスの前段ノード装置へ送信するものであることを特徴とする請求項２２に記載のノード装置。
【請求項２５】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、
自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流にあるべきラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを後段ノード装置へ送信し、
前段ノード装置から照会メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであることを特徴とする請求項２２に記載のノード装置。
【請求項２６】
前記交換する手段は、
自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、
自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流にあるべきラベルスイッチングパスが存在せずこれを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを該上流のラベルスイッチングパスの前段ノード装置へ送信するものであることを特徴とする請求項２２に記載のノード装置。
【請求項２７】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングすると共に、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置であって、
ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子とホップカウント値とを含むラベル割り当てメッセージを受信した場合、該ラベル割り当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、更新されたホップカウント値を含むホップカウント更新メッセージを送信する手段と、
受信した前記ラベル割り当てメッセージに基づいて前記フロー識別子及び前記対応関係を記憶すると共に、前記ホップカウント更新メッセージに対応する成功メッセージを受信するまでは、該対応関係の記憶が未確定なものであることを示す情報を記憶する手段と、
以前に受信したラベル割り当てメッセージに基づき前記未確定なものであることを示す情報が記憶されている対応関係もしくはフロー識別子を示すホップカウント更新メッセージもしくはラベル割り当てメッセージを受信したか否かに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とするノード装置。
【請求項２８】
入力されるパケットフローを識別可能なラベル情報と少なくとも出力側インタフェースを特定する情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、
前段ノード装置から受信した、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージに基づいて、パケットフローをネットワークグローバルに識別可能なフロー識別子および該ラベルスイッチングパスの初段ノードに関する初段ノード情報を記憶し、
前記ラベル割り当てメッセージと同一のフロー識別子および初段ノード情報を含むラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項２９】
出力されるパケットフローを識別可能なラベル情報を使用して、ラベルスイッチングされるべきパケットを送信するノード装置におけるラベルスイッチングパスのループ検出方法であって、
ラベルスイッチングパスの設定を要求する、該ラベルスイッチングパスの初段ノードに関する初段ノード情報を少なくとも含むラベル割り当てメッセージであって、前記初段ノード情報が自ノードを指すものを受信した場合には、ラベルスイッチングパスのループが形成されるものと判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３０】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、
パケットフローの経路上の隣接ノード装置との間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローをネットワークグローバルに識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、
既存のラベルスイッチングパスに対して、前記フロー識別子および前記初段ノード情報が一致するラベル割り当てメッセージを受信した場合に、前記入力側ラベル情報の内容に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３１】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な一つまたは複数の出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、
パケットフローの経路上の前段ノード装置との間、および、一つまたは複数の後段ノード装置それぞれとの間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、
以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３２】
入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、
パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、
以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３３】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするとともに、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置におけるラベルスイッチングパスのループ検出方法であって、
ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割当てメッセージを受信した場合、該ラベル割当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、マージした場合における初段ノード情報および更新されたホップカウント値を少なくとも含むホップカウント更新メッセージを送信し、
以前に前段ノード装置から受信したラベル割り当てメッセージと同一のパケットフローにつき同一の初段ノード情報を含むホップカウント更新メッセージもしくはラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３４】
入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、
パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子を含むものを交換し、
この交換されたメッセージに対応する返答メッセージを受信するまでは該メッセージに対応するラベルスイッチングパスの設定が未確定なものであることを示す情報を記憶し、
新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、以前に交換したメッセージと同一のフロー識別子を含むものを受信した場合に、このフロー識別子に対応して前記未確定なものであることを示す情報が記憶されているならば、ラベルスイッチングパスのループが形成されるものと判断することを特徴とするラベルスイッチングパスのループ検出方法。
【請求項３５】
入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングすると共に、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置におけるラベルスイッチングパスのループ検出方法であって、
ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子とホップカウント値とを含むラベル割り当てメッセージを受信した場合、該ラベル割り当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、更新されたホップカウント値を含むホップカウント更新メッセージを送信し、
受信した前記ラベル割り当てメッセージに基づいて前記フロー識別子及び前記対応関係を記憶すると共に、前記ホップカウント更新メッセージに対応する成功メッセージを受信するまでは、該対応関係の記憶が未確定なものであることを示す情報を記憶し、
以前に受信したラベル割り当てメッセージに基づき前記未確定なものであることを示す情報が記憶されている対応関係もしくはフロー識別子を示すホップカウント更新メッセージもしくはラベル割り当てメッセージを受信したか否かに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とするラベルスイッチングパスのループ検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ラベルスイッチングパスのループ検出機能を有するノード装置及びラベルスイッチングパスのループ検出方法に関する。
【０００２】
【従来の技術】
ＮＢＭＡ（Ｎｏｎ−Ｂｒｏａｄｃａｓｔ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）ネットワーク上でＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ノードが相互接続されるようなネットワークレイヤプロトコルにおいて、パケット転送を高速化するための手法として、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ
Ｓｗｉｔｃｈｉｎｇ）方式がある。
【０００３】
ＭＰＬＳは、ノード間で特定のパケットフローに特定の「ラベル」を割り当て、各ノードで入力側のラベルと出力側のラベルとを関連付けて記憶しておき、この情報を参照してラベルスイッチングを行うことにより、ＩＰ処理を省略し、高速なパケット転送が可能となる。例えば、リンクレイヤがＡＴＭの場合、ＶＰＩ（Ｖｉｒｔｕａｌ  Ｐａｔｈ  Ｉｄｅｎｔｉｆｉｅｒ）／ＶＣＩ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ  Ｉｄｅｎｔｉｆｉｅｒ）がラベルとして使用される。パケットフローがラベルスイッチングされる経路をラベルスイッチングパスと呼ぶ。
【０００４】
ラベルスイッチングパスを構成する場合には、ラベル割当てプロトコルが使用される。ラベル割当てプロトコルは、パケットフローの経路上のノード間で、ネットワークグローバルにパケットフローを識別するためのフロー識別子と、リンクローカルにパケットフローを識別するためのラベルとの対応付けを通知するために、ラベル割当てメッセージをやり取りする。
【０００５】
通常、ＩＰパケットは、ノードを経由する毎にそのパケットヘッダ内のＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールド（あるいはホップリミット・フィールドあるいはこれらに相当するもの）の値が１ずつデクリメントされ、ＴＴＬ等が０になると、ＩＰパケットはそれ以上にフォワーディングされない。これにより経路にループがあった場合もパケットがいつまでもネットワーク内に留まることを防止することができる。しかしながら、ラベルスイッチングパスで転送されるパケットに対しては途中ノードでＩＰ処理が行われないため、ＴＴＬ等をデクリメントすることができず、このため、ラベルスイッチングパスにループができると、そのラベルスイッチングパスからパケットが出ていかないようになってしまう。このため、ラベル割当てプロトコルには、ラベルスイッチングパスのループ検出機構、またはループ回避機構が必要である。
【０００６】
【発明が解決しようとする課題】
従来のラベル割当てプロトコルにおいては、（１）ラベル割当てメッセージの中に、そのパケットフローに対するラベル割当てメッセージを発信した初段ルータからのホップカウント情報を含め、ホップカウントがしきい値を越えるとループであると判断する方法、および（２）ラベル割当てメッセージをフォワードする各ノードが自分のアドレスをラベル割当てメッセージに追加して行き、受信したラベル割当てメッセージに自分のアドレスがすでに書き込んであればループであると判断する方法、がある。
【０００７】
しかしながら、上記の（１）の方法は、ホップカウントがしきい値を越えるまではループであることがわからないため、ループ検出までに時間がかかってしまうという問題があった。なお、この場合、実際にループが形成されたか否かはわからず、またループが形成されたときでも、どのノードにおいてループが形成されたかわからない。
【０００８】
また、上記の（２）の方法は、ラベル割当てメッセージのサイズが大きくなってしまう、という問題があった。
【０００９】
本発明は、上記事情を考慮してなされたもので、ＩＰパケットのＴＴＬ（Ｔｉｍ  Ｔｏ  Ｌｉｖｅ）フィールドを用いた経路のループ検出ができないようなラベルスイッチングパスを構成する場合に、効率的かつ早期にラベルスイッチングパスのループを検出可能なノード装置及びラベルスイッチングパスのループ検出方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
本発明の一つの発明は、ラベルスイッチングパスを設定するために上流から順に流すメッセージに、初段ノード情報を含ませ、ラベルスイッチングパスがループを形成する際には、同一のパケットフローについて初段ノード情報を同じくするメッセージを以前と異なる前段ノードから受信することになる、ということを利用する。
【００１１】
まず、本発明（請求項１）は、入力されるパケットフローを識別可能なラベル情報と少なくとも出力側インタフェースを特定する情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、前段ノード装置から受信した、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージに基づいて、パケットフローをネットワークグローバルに識別可能なフロー識別子および該ラベルスイッチングパスの初段ノードに関する初段ノード情報を記憶する手段と、前記ラベル割り当てメッセージと同一のフロー識別子および初段ノード情報を含むラベル割り当てメッセージをどのノ−ド装置から受信したかに基づいて（例えば、前記前段ノード装置とは異なるノード装置から受信したかに基づいて）、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００１２】
本発明（請求項２）は、出力されるパケットフローを識別可能なラベル情報を使用して、ラベルスイッチングされるべきパケットを送信するノード装置であって、ラベルスイッチングパスの設定を要求する、該ラベルスイッチングパスの初段ノードに関する初段ノード情報を少なくとも含むラベル割り当てメッセージであって、前記初段ノード情報が自ノードを指すものを受信した場合には、ラベルスイッチングパスのループが形成されるものと判断する手段を備えたことを特徴とする。
【００１３】
本発明（請求項３）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、パケットフローの経路上の隣接ノード装置との間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローをネットワークグローバルに識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、既存のラベルスイッチングパスに対して、前記フロー識別子および前記初段ノード情報が一致するラベル割当てメッセージを受信した場合に、前記入力側ラベル情報の内容に基づいて（例えば、前記入力側ラベル情報を異ならせるようなラベル割当てメッセージであるか否かに基づいて）、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００１４】
本発明によれば、ホップカウントを用いる場合に比べ、早期にループ検出が可能となる。
【００１５】
好ましくは、前記ラベルスイッチングパスのループが形成されるものと判断された場合、受信した前記ラベル割当てメッセージに対するラベル割当てのための処理を行わないようにしてもよい。
【００１６】
好ましくは、前記ラベルスイッチングパスのループが形成されるものと判断された場合、受信した前記ラベル割当てメッセージの送信元である前段ノード装置に対して、ラベル割当て失敗メッセージを送信するようにしてもよい。
【００１７】
好ましくは、後段ノード装置からラベル割当て失敗メッセージを受信した場合、このラベル割当て失敗メッセージに関係するラベル割当てメッセージを自ノードに送信した前段ノード装置に対して、ラベル割当て成功メッセージを送信する手段を更に具備するようにしてもよい。
【００１８】
好ましくは、前記ラベル割り当てメッセージは、このラベル割り当てメッセージの送信元である前段ノード装置が割り当てた前記ラベル情報の一部または全部を構成するラベル、もしくは、ラベルスイッチングパスの一部を構成する隣接ノード間のコネクションを特定する識別子であって該ラベルを導出可能なものを含むようにしてもよいし、あるいは、前記ラベル割り当てメッセージは、ラベルの割り当てを要求する識別子を含むものであり、受信したラベル割り当てメッセージに対するラベル割当て処理を行っても良いと判断された場合、このラベル割り当てメッセージの送信元である前段ノード装置へ、自ノードが割り当てた前記ラベル情報の一部または全部を構成するラベル、もしくは、ラベルスイッチングパスの一部を構成する隣接ノード間のコネクションを特定する識別子であって該ラベルを導出可能なものを含む、ラベル割り当て成功メッセージを返信する手段を更に具備するようにしてもよい。
【００１９】
本発明（請求項９）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な一つまたは複数の出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、パケットフローの経路上の前段ノード装置との間、および、一つまたは複数の後段ノード装置それぞれとの間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいてラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００２０】
これにより、マルチキャストのラベルスイッチングパスを設定する場合にも、ループ検出が可能となる。
【００２１】
本発明のもう一つの発明は、ラベルスイッチングパスを設定するためにメッセージを流す（初段から下流へ向けて流す初段ノード主導でも、終段から上流へ向けて流す終段ノード主導でもよい）際に、既に上流もしくは下流にそのパケットフロー用のラベルスイッチングパスが存在するノードに当たったならば、その既存のラベルスイッチングパス上を、例えば更新メッセージを流すことにより、フローと同方向もしくは逆方向に辿る。最後まで辿ってループが検出されなければ、ラベルスイッチングパスを設定する。
【００２２】
この辿るときに使うメッセージに初段ノード情報を含ませれば、ループが形成される際には同一のパケットフローについて初段ノード情報を同じくするメッセージを以前と異なる前段ノードから受信することになるため、これを利用してループが検出できる。あるいは、メッセージを送受信するときに状態が未確定であることを示すフラグを立てておくことにすれば、ループが形成される際には同一のパケットフローについてフラグが未確定を示しているノードにメッセージが到達するため、これを利用してループが検出できる。
【００２３】
すなわち、本発明（請求項１０）は、入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換する手段と、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいてラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００２４】
本発明によれば、ラベルのマージを行う場合にも早期にループ検出が可能となる。
【００２５】
初段ノード主導の場合には、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであるようにするとよい。
【００２６】
終段ノード主導の場合には、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを後段ノード装置へ送信し、前段ノード装置から照会メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであるようにするとよい。
【００２７】
終段ノード主導の場合には、さらに、前記交換する手段は、後段ノード装置からラベル割り当てメッセージを受信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、ラベル割り当て成功メッセージを後段ノード装置へ送信し、前段ノード装置からラベル割り当て成功メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合にも、前記更新メッセージを後段ノード装置へ送信するものであるようにしてもよい。
【００２８】
以上の各発明において、後段ノード装置へ送信するメッセージ（例えば、更新メッセージ、初段主導の場合のラベル割り当てメッセージ、終段主導の場合のラベル割り当て成功メッセージや照会メッセージ）中にホップカウントをも含め、初段ノードからのホップカウントがしきい値を越えた場合には、受信したメッセージに関するラベルスイッチングパスの設定を行わないように処理するようにしてもよい。
【００２９】
本発明（請求項１５）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするとともに、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置であって、ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割当てメッセージを受信した場合、該ラベル割当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、マージした場合における初段ノード情報および更新されたホップカウント値を少なくとも含むホップカウント更新メッセージを送信する手段と、以前に前段ノード装置から受信したラベル割り当てメッセージと同一のパケットフローにつき同一の初段ノード情報を含むホップカウント更新メッセージもしくはラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００３０】
このようにホップカウントをメッセージに含ませることで、例えば次に示すことも可能になる。
【００３１】
好ましくは、ループが形成されると判断された場合には、ホップカウント更新もしくはラベル割り当てができないことを、ホップカウント更新もしくはラベル割り当てメッセージを自ノードに送信した前段ノード装置に通知する手段と、ホップカウント更新ができないことを通知された場合には、ラベル割り当てができないことを、ラベル割り当てメッセージを自ノードに送信した前段ノード装置に通知する手段と、ラベル割り当てができないことを通知された場合には、ホップカウントがしきい値を越えないならば、ホップカウント更新ができることを、ホップカウント更新メッセージを自ノードに送信した前段ノード装置に通知する手段と、ホップカウント更新ができることを通知された場合には、設定を要求されたラベルスイッチングパスを既存のラベルスイッチングパスにマージすることにより設定する手段とを更に備えるようにしてもよい。
【００３２】
また、好ましくは、ラベルスイッチングパスの設定を要求する、フロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割り当てメッセージを受信した場合、該ラベルメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものでないならば、設定を要求されたラベルスイッチングパスを既存のラベルスイッチングパスにマージすることにより設定する手段を更に備えるようにしてもよい。
【００３３】
また、好ましくは、前記送信する手段は、更新されたホップカウント値に対応する初段ノードに関する情報を、前記ホップカウント更新メッセージが含む、マージした場合における初段ノード情報とし、マージされたラベルスイッチングパスの一部が解放されマージが行われなくなった場合に、解放されたパスに対応する初段ノード情報が前記ホップカウント更新メッセージに含まれていたならば、マージされなくなった場合における初段ノード情報とホップカウント値とを含むホップカウント更新メッセージを送信する手段を含むものであるようにしてもよい。
【００３４】
また、好ましくは、前記送信する手段は、更新されたホップカウント値に対応する初段ノードもしくは既存のラベルスイッチングパスの初段ノードに関する情報を、前記ホップカウント更新メッセージが含む、マージした場合における初段ノード情報とし、マージされたラベルスイッチングパスの一部が解放されマージが行われなくなった場合に、解放されたパスに対応する初段ノード情報が前記ホップカウント更新メッセージに含まれていたならば、マージされなくなった場合における初段ノード情報を含む更新メッセージを（たとえマージされなくなったことによってホップカウント値が変化しなくても）送信する手段を含むものであるようにしてもよい。
【００３５】
以上の各発明において、前記初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスを用いるようにしてもよいし、あるいは前記初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスと初段ノードの出力インタフェースローカルに割り当てられる識別子とからなる組を用いるようにしてもよい。前者によれば、初段ノードがネットワークグローバルに識別できるようになる。あるいは後者によれば、１つの初段ノードから同一フローに対して複数のラベル割り当て要求を送信することができるようになり、ラベル割当てプロトコルがフレキシブルになり、異なるラベル割当てプロトコルの間で相互接続やマルチパスに対応したラベルスイッチングパスの設定等が容易になる。
【００３６】
本発明（請求項２２）は、入力されるパケットフローを識別可能な一つまたは複数（複数の場合はラベルスイッチングパスのマージになる）の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置であって、パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子を含むものを交換する手段と、この交換されたメッセージに対応する返答（成功もしくは失敗）メッセージを受信するまでは該メッセージに対応するラベルスイッチングパスの設定が未確定なものであることを示す情報を記憶する手段と、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、以前に交換したメッセージと同一のフロー識別子を含むものを受信した場合に、このフロー識別子に対応して前記未確定なものであることを示す情報が記憶されているならば、ラベルスイッチングパスのループが形成されるものと判断する手段とを備えたことを特徴とする。
【００３７】
なお、何らかの原因で一定時間いずれのメッセージも返ってこない場合には、失敗メッセージを受信したとみなして動作することが好ましい。
【００３８】
この発明によっても、早期にループを検出することが可能となる。
【００３９】
初段ノード主導でラベルスイッチングパスを設定し、ループ検出のためのメッセージをフローと同方向に流す場合は、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであるようにすることができる。
【００４０】
初段ノード主導でラベルスイッチングパスを設定し、ループ検出のためのメッセージをフローと逆方向に流す場合は、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置へ送信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在し、自装置の上流に対応するラベルスイッチングパスを新たに設定しようとする場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを前段ノード装置へ送信し、後段ノード装置から照会メッセージを受信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを該上流のラベルスイッチングパスの前段ノード装置へ送信するものであるようにすることができる。
【００４１】
終段ノード主導でラベルスイッチングパスを設定し、ループ検出のためのメッセージをフローと同方向に流す場合は、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとして照会メッセージを後段ノード装置へ送信し、前段ノード装置から照会メッセージを受信し、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在する場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを後段ノード装置へ送信するものであるようにすることができる。
【００４２】
終段ノード主導でラベルスイッチングパスを設定し、ループ検出のためのメッセージをフローと逆方向に流す場合は、前記交換する手段は、自装置の下流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の上流に対応するラベルスイッチングパスが存在しない場合に、新たなラベルスイッチングパスを設定するためのメッセージとしてラベル割り当てメッセージを後段ノード装置以外のノード装置へ送信し、自装置の上流に前記パケットフロー用のラベルスイッチングパスが存在するが自装置の下流にあるべきラベルスイッチングパスが存在せずこれを新たに設定しようとする場合に、既存のラベルスイッチングパスを利用するためのメッセージとして更新メッセージを該上流のラベルスイッチングパスの前段ノード装置へ送信するものであるようにすることができる。
【００４３】
本発明（請求項２７）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングすると共に、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置であって、ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子とホップカウント値とを含むラベル割り当てメッセージを受信した場合、該ラベル割り当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、更新されたホップカウント値を含むホップカウント更新メッセージを送信する手段と、受信した前記ラベル割り当てメッセージに基づいて前記フロー識別子及び前記対応関係を記憶すると共に、前記ホップカウント更新メッセージに対応する成功メッセージを受信するまでは、該対応関係の記憶が未確定なものであることを示す情報を記憶する手段と、以前に受信したラベル割り当てメッセージに基づき前記未確定なものであることを示す情報が記憶されている対応関係もしくはフロー識別子を示すホップカウント更新メッセージもしくはラベル割り当てメッセージを受信したか否かに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断する手段とを備えたことを特徴とする。
【００４４】
なお、このようにホップカウントをメッセージに含ませることにより、ホップカウント値をより大きい値に更新させるものでない場合には、直ちにマージ（「確定」として対応関係を記憶）することも可能になる。
【００４５】
本発明（請求項２８）は、入力されるパケットフローを識別可能なラベル情報と少なくとも出力側インタフェースを特定する情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、前段ノード装置から受信した、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージに基づいて、パケットフローをネットワークグローバルに識別可能なフロー識別子および該ラベルスイッチングパスの初段ノードに関する初段ノード情報を記憶し、前記ラベル割り当てメッセージと同一のフロー識別子および初段ノード情報を含むラベル割り当てメッセージをどのノ−ド装置から受信したかに基づいて（例えば、前記前段ノード装置とは異なるノード装置から受信したかに基づいて）、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００４６】
本発明（請求項２９）は、出力されるパケットフローを識別可能なラベル情報を使用して、ラベルスイッチングされるべきパケットを送信するノード装置におけるラベルスイッチングパスのループ検出方法であって、ラベルスイッチングパスの設定を要求する、該ラベルスイッチングパスの初段ノードに関する初段ノード情報を少なくとも含むラベル割り当てメッセージであって、前記初段ノード情報が自ノードを指すものを受信した場合には、ラベルスイッチングパスのループが形成されるものと判断することを特徴とする。
【００４７】
本発明（請求項３０）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、パケットフローの経路上の隣接ノード装置との間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローをネットワークグローバルに識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、既存のラベルスイッチングパスに対して、前記フロー識別子および前記初段ノード情報が一致するラベル割当てメッセージを受信した場合に、前記入力側ラベル情報の内容に基づいて（例えば、前記入力側ラベル情報を異ならせるようなラベル割当てメッセージであるか否かに基づいて）、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００４８】
本発明（請求項３１）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な一つまたは複数の出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、パケットフローの経路上の前段ノード装置との間、および、一つまたは複数の後段ノード装置それぞれとの間で、ラベルスイッチングパスの設定を要求するラベル割り当てメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００４９】
本発明（請求項３２）は、入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子と該ラベルスイッチングパスの初段ノードに関する初段ノード情報とを含むものを交換し、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含むメッセージを以前とは異なる前段ノード装置から受信した場合、もしくは、以前に交換したメッセージと同一のフロー識別子及び初段ノード情報を含み前記入力側ラベル情報を異ならせるようなメッセージを受信した場合を検出し、この検出結果に基づいてラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００５０】
本発明（請求項３３）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするとともに、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置におけるラベルスイッチングパスのループ検出方法であって、ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子、該ラベルスイッチングパスの初段ノードに関する初段ノード情報およびホップカウント値を少なくとも含むラベル割当てメッセージを受信した場合、該ラベル割当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、マージした場合における初段ノード情報および更新されたホップカウント値を少なくとも含むホップカウント更新メッセージを送信し、以前に前段ノード装置から受信したラベル割り当てメッセージと同一のパケットフローにつき同一の初段ノード情報を含むホップカウント更新メッセージもしくはラベル割り当てメッセージをどのノード装置から受信したかに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００５１】
本発明（請求項３４）は、入力されるパケットフローを識別可能な一つまたは複数の入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングするノード装置におけるラベルスイッチングパスのループ検出方法であって、パケットフローの経路上の隣接ノード装置との間で、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、該パケットフローを識別可能なフロー識別子を含むものを交換し、この交換されたメッセージに対応する返答メッセージを受信するまでは該メッセージに対応するラベルスイッチングパスの設定が未確定なものであることを示す情報を記憶し、新たなラベルスイッチングパスを設定するためのメッセージもしくは既存のラベルスイッチングパスを利用するためのメッセージであって、以前に交換したメッセージと同一のフロー識別子を含むものを受信した場合に、このフロー識別子に対応して前記未確定なものであることを示す情報が記憶されているならば、ラベルスイッチングパスのループが形成されるものと判断することを特徴とする。
【００５２】
本発明（請求項３５）は、入力されるパケットフローを識別可能な入力側ラベル情報と出力されるパケットフローを識別可能な出力側ラベル情報との対応関係を参照して、入力されたパケットをラベルスイッチングすると共に、同じパケットフローに関し、一つの出力側ラベル情報と一つ又は複数の入力側ラベル情報との対応が既に存在する場合に、この出力側ラベル情報に更に新たな入力側ラベル情報を対応させるラベルスイッチングパスのマージを行うノード装置におけるラベルスイッチングパスのループ検出方法であって、ラベルスイッチングパスの設定を要求する、パケットフローを識別可能なフロー識別子とホップカウント値とを含むラベル割り当てメッセージを受信した場合、該ラベル割り当てメッセージが既存のラベルスイッチングパスへのマージを伴うものであり、かつ、前記ホップカウント値が既存のラベルスイッチングパスのホップカウント値をより大きい値に更新させるものであるならば、該既存のラベルスイッチングパスにおける後段ノード装置に、更新されたホップカウント値を含むホップカウント更新メッセージを送信し、受信した前記ラベル割り当てメッセージに基づいて前記フロー識別子及び前記対応関係を記憶すると共に、前記ホップカウント更新メッセージに対応する成功メッセージを受信するまでは、該対応関係の記憶が未確定なものであることを示す情報を記憶し、以前に受信したラベル割り当てメッセージに基づき前記未確定なものであることを示す情報が記憶されている対応関係もしくはフロー識別子を示すホップカウント更新メッセージもしくはラベル割り当てメッセージを受信したか否かに基づいて、ラベルスイッチングパスのループが形成されるか否かを判断することを特徴とする。
【００５３】
なお、ホップカウント値をより大きい値に更新させるものでない場合には、直ちにマージ（「確定」として対応関係を記憶）して構わない。
【００５４】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
【００５５】
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００５６】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００５７】
本発明は、（１）初段ノード主導でラベルスイッチングパスを生成する、すなわちラベル割り当てメッセージが初段ノードから後段ノードの方向に送信され、ラベル割り当て成功／失敗メッセージが終段ノードから前段ノードの方向に送信される場合（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌと呼ぶ）にも、（２）終段ノード主導でラベルスイッチングパスを生成する、すなわちラベル割り当てメッセージが終段ノードから前段ノードの方向に送信され、ラベル割り当て成功／失敗メッセージが初段ノードから後段ノードの方向に送信される場合（Ｅｇｒｅｓｓ  Ｃｏｎｔｒｏｌと呼ぶ）にも、適用可能である。
【００５８】
本実施形態では、ラベルスイッチングパスのループ検出のために、確定フラグを用いる手段と初段ノード情報を用いる手段を提供する。
【００５９】
確定フラグは、ループ検出の目的以外でも、ラベル割り当て要求メッセージまたは更新メッセージを後段ノード／前段ノードに送信後、メッセージに対するＡＣＫ待ちの状態の時に別のラベル割り当て要求メッセージまたは更新メッセージを上流ノード／下流ノードから受信した場合には受信したメッセージを受付けないようにすることにより、各ノードがもつラベルスイッチングパスの状態をネットワーク全体で一貫性を保つためにも使用できる。
【００６０】
初段ノード情報は、確定フラグを用いた場合よりも早期にループを検出するために使用できる。
【００６１】
初段ノード主導（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）の場合、ネットワークのノード全部がラベルのマージを行なう場合には、確定フラグのみを用いたループ検出が可能である。終段ノード主導（Ｅｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）の場合、ネットワークのノード全部がラベルのマージを行なう場合にも、ネットワークのノードの一部または全部がラベルのマージを行なわない場合にも、確定フラグのみを用いたループ検出が可能である。
【００６２】
初段ノード主導（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）の場合、ネットワークのノード全部がラベルのマージを行なわない場合あるいはネットワークがラベルのマージを行なうノードと行なわないノードとから構成される場合には、ループ検出に初段ノード情報を用いる方がよい。
【００６３】
本実施形態では、ホップカウントは、ループを検出するためでなく、パスのホップ数に上限を設けるために使用することができる。この結果、（１）ＩＰパケットのＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールドをラベルスイッチングパスの入口または出口でパスのホップ数の分だけデクリメントする制御、（２）ラベルのマージを行なわない場合には、ホップ数が増え続けるようなスパイラル状のループが構成されるのを防ぐ制御（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌの場合）、（３）ラベルのマージを行なう場合には、初段からの最大のホップ数が変化しないようなマージに対しては、後段ノードに状態の変化を通知するメッセージを送信することなくラベルのマージを行なう制御が可能になる。
【００６４】
なお、ラベルスイッチングパスのループ検出の手順としては、これに用いる情報としてホップカウントと初段ノード情報と確定フラグとを組み合わせて使用する種々の手順が可能である。
【００６５】
同一のパケットフローとする形態には、（１）宛先ＩＰアドレスが同じパケットを同一のパケットフローとする、（２）ネットワークマスクに対応する宛先ＩＰアドレスの部分（すなわち宛先ＩＰアドレスの上位の所定ビット）が同じパケットを同一のパケットフローとする、（３）送信元ＩＰアドレスと宛先ＩＰアドレスの組が同じパケットを同一のパケットフローとする、（４）第１のネットワークマスクに対応する送信元ＩＰアドレスの部分と第２のネットワークマスクに対応する宛先ＩＰアドレスの部分との組が同じパケットを同一のパケットフローとする、（５）あるＩＰアドレスを持つノードを通るパケットを同一のパケットフローとする、（６）上記の（１）〜（５）において、送信元および／または宛先のポート番号をも組にしたものが同一であるパケットを同一のパケットフローとする、などが種々のもの考えられる。本実施形態では、宛先ＩＰアドレスが同じパケットは同一のパケットフローであるものとする。
【００６６】
最初に、ラベル割り当てメッセージが初段ノードから後段ノードの方向に送信され、ラベル割り当て成功／失敗メッセージが終段ノードから前段ノードの方向に送信される場合（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）について説明する。
【００６７】
（第１の実施形態）
まず、本発明の第１の実施形態に係るラベル割り当てプロトコルおよびこのラベル割り当てプロトコルに従ってラベルスイッチングを行うノード装置について説明する。なお、ここでは、ノード装置が後段ノードにメッセージ送信後ＡＣＫ信号待ちのときに、前段ノードから状態の変更を伴うメッセージを受信しないような排他制御を別に行っているものとする。
【００６８】
図１に本実施形態に係るノード装置を接続して構成されたネットワークの一例を示す。
【００６９】
図１では、本実施形態に係るノード装置Ｒ１〜Ｒ５が接続されており、特にノード装置Ｒ２〜Ｒ５でループが形成されている。なお、図１は、ネットワークの一部を切り出したもので、ノード装置Ｒ１〜Ｒ５の全てまたは一部には図示しない他のノード装置が接続されている。
【００７０】
ノード装置Ｒ１〜Ｒ５は、それぞれ、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）処理を行う機能を持つとともに、本実施形態に係るラベル割り当てプロトコルに従ってラベルスイッチングを行う機能を持つ。また、末端に位置し中継を行わないノード装置以外のノード装置は、ルータ機能を持つ。例えば、図１において、ノード装置Ｒ２〜Ｒ５はルータ機能を持ち、ルータ装置Ｒ１についてはこれが末端に位置し中継を行わないものである場合にはルータ機能は不要である。
【００７１】
また、本実施形態では、ネットワークの各ノード装置ではラベルのマージは行わないものとする。
【００７２】
ラベルスイッチングパスは、初段ノード装置を起点として、次々と後段ノード装置にラベル割り当てメッセージを送信してゆくことで形成される。本実施形態では、このラベル割り当てメッセージには、少なくとも、初段ノード情報（Ｉｎｇｒｅｓｓ）、フローＩＤ（Ｆｌｏｗｉｄ）、および、リンクＩＤ（Ｌｉｎｋｉｄ）が含まれる。リンクＩＤとして、ラベル（Ｌａｂｅｌ）、レイヤ２コネクション識別子、ラベル割り当てメッセージの送信ノードのアドレス、または、ラベル割当てをラベル割り当てメッセージを受信した下流側ノードが行なう場合（Ｄｏｗｎｓｔｒｅａｍ  ｏｎ  ｄｅｍａｎｄ割当て）にはリクエスト識別子、またはこれらの２つ以上の組合せが使用される。
【００７３】
初段ノード情報としては、初段ノード装置の出力インターフェースに対して割り当てられたＩＰアドレスの一つを使用する。このＩＰアドレスは、ネットワークグローバルなアドレスである。
【００７４】
フローＩＤは、ネットワークグローバルにパケットフローを識別する情報である。
【００７５】
メッセージに含まれるラベルは、リンクローカルにパケットフローを識別する情報であるものとし、リクエスト識別子も同様とする。
【００７６】
実際にラベルスイッチングパスが確立するのは、上記のラベル割り当てメッセージに対応して、終段ノードから、次々と前段ノード装置にラベル割り当て成功メッセージが返信された場合である。なお、ここでは、ラベルスイッチングパスの終段ノードまでラベル割り当てメッセージが届いた後に、そこから順々にラベル割り当て成功メッセージが返ってくるラベル割り当てプロトコルの例を主に説明するが、ラベルスイッチングパスの経路上の途中のノードが、ラベル割り当てメッセージが終段ノードへ届き対応するラベル割り当て成功メッセージが返ってくるのを待たずに、前段ノード装置にラベル割り当て成功メッセージを返すようなラベル割り当てプロトコルを用いることも可能である。
【００７７】
本実施形態では、ラベル割当てをラベル割り当てメッセージを送信するノード（上流側ノード）が行なう場合（Ｕｐｓｔｒｅａｍ割当て）、すなわち、ラベル割り当てメッセージに「ラベル」が含まれる場合を例にとり説明するが、Ｄｏｗｎｓｔｒｅａｍ  ｏｎ  ｄｅｍａｎｄ割当ての場合には、ラベル割り当てメッセージには「リクエスト識別子」が含まれ、これに対応して返送されてくるラベル割り当て成功メッセージに「ラベル」もしくは「レイヤ２コネクション識別子」が含まれることになる。
【００７８】
各ノード装置は、隣接ノード装置に対する入出力インタフェースを識別するインタフェースＩＤの情報を持つ。あるパケットフローに対して自ノードの上流に割り当てられたラベルと上流側のインタフェースＩＤとの組を入力側ラベルと呼び、そのパケットフローに対して自ノードの下流に割り当てられたラベルと下流側のインタフェースＩＤとの組を出力側ラベルと呼ぶ。なお、インタフェースを一つしか持たないノードでは、インタフェースＩＤは用いなくても良い。ここで、説明のために、ノード装置Ｒ２のノード装置Ｒ１に対するインタフェースＩＤをｉ１、ノード装置Ｒ５に対するインタフェースＩＤをｉ５、ノード装置Ｒ３に対するインタフェースＩＤをｉ３とする。
【００７９】
そして、確立されたラベルスイッチングパスを用いて実際にパケット転送を行う場合には、パケットに含まれるラベルの情報に基づき、上記の入力側ラベルと出力側ラベルの対応関係を参照して、ＩＰ処理を省略したパケット転送（ラベルスイッチング）を行う。
【００８０】
前段ノードから送信されるラベル割り当てメッセージもしくは自ノードが返信するラベル割り当て成功メッセージに「ラベル」が含まれている場合には、これが入力側ラベルを構成するラベルとなる。自ノードが送信するラベル割り当てメッセージもしくは後段ノードから返信されるラベル割り当て成功メッセージに「ラベル」が含まれている場合には、これが出力側ラベルを構成するラベルとなる。
【００８１】
一方、ラベル割り当てメッセージもしくはラベル割り当て成功メッセージに含まれるのが「ラベル」ではなく、「レイヤ２コネクション識別子」の場合は、このレイヤ２コネクション識別子に対応して別途求められたラベルが、上記の入力側ラベルや出力側ラベルを構成するラベルとなる。具体的には、リンクレイヤがＡＴＭで、隣接ノード間にＡＴＭスイッチが挟まれるネットワーク構成の場合、「ラベル」として実際のスイッチングに使用されるのはＶＰＩ／ＶＣＩであるが、この値は途中のＡＴＭスイッチで書き換えられてしまうため、隣接ノード間のＡＴＭコネクションを両端のノードが一意に識別できるようにＶＣＩＤ（Ｖｉｒｔｕａｌ  Ｃｏｎｎｅｃｔｉｏｎ  ＩＤ）  と呼ばれる別の識別子を用いる。このＶＣＩＤがラベル割り当てプロトコルに含まれる「レイヤ２コネクション識別子」の一例である。
【００８２】
メッセージに含まれる上記の「リンクＩＤ」と、メッセージを受信したインタフェースＩＤとを組み合わせると、ラベル割り当てメッセージもしくは（ホップカウント）更新メッセージを受信したノードは、以前に同じフロー識別子、同じ初段ノード情報に対するラベル割り当てメッセージを受信した際とは異なる前段ノードからこれを受信したということを検出できる。そして、この場合にループと判断する。
【００８３】
なお、上流の隣接ノードが上記のループ検出機能を持たない場合、以前と同じフロー識別子、同じ初段ノード情報に対するラベル割り当てメッセージであって、異なるラベル（もしくはレイヤ２コネクション識別子またはリクエスト識別子）を含むものを、以前と同じ前段ノードから受信することがあり得る。その場合は、これを受信したノードが、上流の隣接ノードに代わって、ループ検出をすることになる。したがって、ループ検出機能を、同じフロー識別子及び初段ノード情報のメッセージを以前と異なる前段ノードから受信したか否かを陽に検出するのではなく、同じフロー識別子及び初段ノード情報と以前と異なるラベル（もしくはレイヤ２コネクション識別子またはリクエスト識別子）とを含むメッセージを受信したか否かを検出するように、構成してもよい。こうすれば、一つの判断基準で、上流の隣接ノードにループ検出機能が有れば、異なる前段ノードから受信したかどうかを検出していることになり、上流の隣接ノードにループ検出機能が無ければ、異なるラベルを受信したかどうかで上流で見落としたループをも検出していることになる。
【００８４】
以降の説明では、「ラベル」を「リンクＩＤ」として用いる場合について述べる。ラベル以外のものをリンクＩＤとして用いる場合には、以降の説明の「ラベル」の部分を「レイヤ２コネクション識別子」、「ラベル割り当てメッセージの送信ノードのアドレス」、または「リクエスト識別子」、または、これらと「ラベル」のうちの２つ以上の組合せに置き換えれば、同様にループ検出ができる。例えば、上流の隣接ノードから受信したメッセージに含まれる「レイヤ２コネクション識別子」、「ラベル割り当てメッセージの送信ノードのアドレス」、または「リクエスト識別子」と、上流側のインタフェースＩＤとの組を、入力側ラベルと呼ぶことになる。
【００８５】
但し、以降に説明する例においては、「入力側ラベル」を、同一フロー識別子、同一初段ノード情報に係るメッセージを以前と異なる前段ノードから受信したか否かの検出（異なるならばループと判断）だけではなく、同一フロー識別子に係るメッセージを以前と同一の前段ノードから異なる初段ノード情報に係るものとして受信したか否かの区別（異なるならば新たなラベルスイッチングパスの設定を続行）にも用いているため、上流の隣接ノードがラベルのマージを行なわない場合には、「ラベル」を「ラベル割り当てメッセージの送信ノードのアドレス」単独に置き換えるのではなく、「レイヤ２コネクション識別子」もしくは「リクエスト識別子」に置き換える（これらであれば単独でも構わない）か、「ラベル割り当てメッセージの送信ノードのアドレス」とその他のリンクＩＤとの組合せに置き換えるかすることが好ましい。
【００８６】
なお、上記及び以降の説明では、メッセージに含まれる「リンクＩＤ」を用いて、同じフロー識別子、同じ初段ノード情報に対するラベル割り当てメッセージを異なる前段ノードから受信したことを検出（ループと判断）するが、メッセージを受信した「インタフェースＩＤ」だけでもこの検出が行える場合がある。それは、隣接ノード同士が、図２のようなバス型接続でなく、図３のようなポイント−ポイントリンクで接続されている場合である。なお、このように入力側ラベルの代わりにインターフェースＩＤ単独を用いて（リンクＩＤには依らずに）ループ検出するのは、上流の隣接ノードがラベルのマージを行なう場合とすることが好ましい。
【００８７】
また、図２の場合には、リンクＩＤ（例えばラベル）を用いてループ検出するが、このラベルやリクエスト識別子は、下流側のノードから見て、異なる前段ノードからのものはその値が異なっているように、上流側のそれぞれのノードが割り当てる。
【００８８】
図１には、ノード装置Ｒ１からＲ２、Ｒ２からＲ３、Ｒ３からＲ４、Ｒ４からＲ５、Ｒ５からＲ２へそれぞれ送られるラベル割当てメッセージｍ１、ｍ２、ｍ３、ｍ４、ｍ５を示してある。
【００８９】
なお、ｍｉ＝（初段ノード（Ｉｎｇｒｅｓｓ）＝ｘ１，フロー識別子（Ｆｉｏｗｉｄ）＝ｘ２，ラベル（Ｌａｂｅｌ）＝ｘ３）は、ラベル割当てメッセージｍｉに、初段ノード情報としてｘ１、フローＩＤとしてｘ２、ラベルとしてｘ３が含まれることを示す。
【００９０】
ノード装置がラベル割当てメッセージを初段として送信する契機には、例えば、次のような形態がある。
（１）各々のノード装置が、宛先ｄｅｓｔに対するルーティングテーブルが生成されたときを契機に、ラベル割当てメッセージを送信する。
（２）各々のノード装置が、宛先ｄｅｓｔに対するルーティングテーブルが生成された後に宛先ｄｅｓｔに対するトラヒック量がしきい値を越えた場合を契機に、ラベル割当てメッセージを送信する。
（３）宛先ｄｅｓｔに対するルーティングテーブルが生成された後に、宛先ｄｅｓｔに対するトラヒック量がしきい値を越え、かつ、トラヒック（データグラム）の前段ノード装置が本実施形態に係るラベル割り当てプロトコルをサポートしない、という条件をみたすノード装置のみが、これを契機に自ノードを初段と判断してラベル割当てメッセージを送信する（例えばＩＮＴＥＲＮＥＴ−ＤＲＡＦＴ  ＜ｄｒａｆｔ−ｉｅｔｆ−ｒｏｌｃ−ｎｈｒｐ−ｌ１．ｔｘｔ＞  ＮＢＭＡ  Ｎｅｘｔ  Ｈｏｐ  Ｒｅｓｏｌｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ（ＮＨＲＰ）参照）。
【００９１】
次に、本実施形態のラベル割り当てプロトコルに従った動作について説明する。
【００９２】
ここでは、ノード装置Ｒ１から宛先アドレスｄｅｓｔ宛のパケットのルートが、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５，Ｒ２，Ｒ３，…とループしている場合を考える。
【００９３】
まず、ノード装置Ｒ１が、上記のように宛先ｄｅｓｔに対するルーティングテーブルが生成されたときなどを契機に、宛先ｄｅｓｔに対する自ノードの次ホップノードであるノード装置Ｒ２への出力インタフェースにおいて、新たなラベルａを割当て、ノード装置Ｒ２に、（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ａ）のラベル割当てメッセージｍ１を送信する。また、ノード装置Ｒ１は、少なくとも、フロー識別子、初段ノード情報、出力側ラベルを対応付けて記憶する。その際、保留を示す情報を付加しておく。
【００９４】
ノード装置Ｒ２は、ノード装置Ｒ１からのラベル割当てメッセージｍ１を受信すると、自ノードの次ホップノードであるノード装置Ｒ３への出力インタフェースにおいて新たなラベルｂを割当て、ノード装置Ｒ３に（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｂ）のラベル割当てメッセージｍ２を送信する。また、ラベルスイッチング情報、すなわち少なくともフロー識別子、初段ノード情報、入力側ラベル（受信したラベルとノード装置Ｒ１に対するリンク識別子）、出力側ラベル（割当てたそのラベルとノード装置Ｒ３に対するリンク識別子）を対応付けて記憶するとともに、これに保留を示す情報を付加する。この時点で、ノード装置Ｒ２内には、少なくともフロー識別子ｄｅｓｔ、初段ノード情報Ｒ１、入力側ラベル（ｉ１，ａ）、出力側ラベル（ｉ３，ｂ）が対応付けて記憶されていることになる。
【００９５】
なお、上記各情報は、例えば１つまたは複数のテーブル（例えば図１３に例示するフローテーブル）を用いて記憶する。また、上記各情報を記憶するタイミングについては、例えばラベル割当てメッセージｍ２を送信する前後にまとめて記憶してもよいし、また例えばラベル割当てメッセージｍ１を受信したときに、フロー識別子、初段ノード情報、入力側ラベルを記憶し、ラベルｂを割当てた後に出力側ラベルを記憶するようにしてもよい。
【００９６】
同様にして、ラベル割当てメッセージがノード装置Ｒ３からＲ４、ノード装置Ｒ４からＲ５、そしてノード装置Ｒ５からＲ２へとフォワードされていくとともに、各ノード装置Ｒ３〜Ｒ５において、出力インタフェースにおけるラベルの割当てやフロー識別子等の各情報の記憶と保留を示す情報の付加が行われる。
【００９７】
次に、ノード装置Ｒ２が、ノード装置Ｒ５から（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｅ）のラベル割当てメッセージｍ５を受信したとき、すでにノード装置Ｒ１から受信したラベル割当てメッセージｍ１の受信に応答して記憶したフロー識別子等の情報の組に対して、入力側ラベルが異なっており（前者が（ｉ１，ａ）であるのに対して後者が（ｉ５，ｅ））、かつ、初段ノード情報、フロー識別子ともに一致するため、ノード装置Ｒ２はループであると判断し、受信したラベル割当てメッセージｍ５を廃棄するか、ノード装置Ｒ５に対してラベル割当て失敗メッセージを返す。なお、ここでは、ループを検出したノード装置は、ラベル割当て失敗メッセージを返すものとする。
【００９８】
ノード装置Ｒ５は、上記のようにしてラベル割当て失敗メッセージを受信した場合、フロー識別子等の情報の組のうち、ラベル割当てメッセージｍ５を送信するにあたって記憶した出力側ラベルの情報をキャンセルし、保留を示す情報を、確定を示す情報に変更するとともに、前段ノード装置にラベル割当て成功メッセージを送信する。
【００９９】
また、後段ノード装置からラベル割当て成功メッセージを受信した初段以外のノード装置（ここではＲ４，Ｒ３，Ｒ２）は、前段ノード装置にラベル割当て成功メッセージを送信する。また、ラベル割当て成功メッセージを受信したノード装置（ここではＲ４，Ｒ３，Ｒ２，Ｒ１）は、ラベル割当てメッセージに応答して記憶したフロー識別子等の情報の組に付加した保留を示す情報を、確定を示す情報に変更する。
【０１００】
この結果、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスが形成される。また、ノード装置Ｒ５からはＩＰパケットのＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールドあるいはホップリミット・フィールドあるいはこれらに相当するものを用いた通常のＩＰ転送が行われる。
【０１０１】
なお、このような状態は過渡的な状態であり、一定時間経過すると、正常なルートに回復するようにルーティングプロトコルは動作し、これに伴い、ラベルスイッチングパスの変更も行われる。
【０１０２】
もし、ループ検出なしに終段ノードまでラベル割当てメッセージが到達した場合、この終段のノード装置は、前段ノード装置にラベル割当て成功メッセージを送信し、次々と前段ノード装置にラベル割当て成功メッセージが伝えられ、最終的に初段ノード装置までラベル割当て成功メッセージが到達し、ループのないラベルスイッチングパスが形成される。
【０１０３】
なお、上記実施形態において、従来のようにホップカウント（Ｈｏｐｃｏｕｎｔ）がしきい値を越えた場合にループ検出とみなす方法を併用してもよい。
【０１０４】
ところで、本ノード装置は、自ノードがラベルスイッチングパスの終点ノードになった場合、その後、適当なタイミングで繰り返しラベル割当てメッセージを送信するようにするのが好ましい。ラベル割当て失敗メッセージが送信される理由には、ループ検出や使用可能なラベルがないなどの種々のケースが考えられるが、ケースによっては、ルーティングテーブルが書き替えられたことにより先に検出されたループが解消されたり、あるいは使用中のラベルが解放されたことにより使用可能なラベルが確保できたりし、さらにラベルスイッチングパスを延ばすことができる可能性があるからである。ただし、しきい値を越えたことがラベル割当て失敗の理由であった場合には、適当なタイミングで繰り返しラベル割当て成功メッセージを送信することはしないものとする。なお、ラベル割当て失敗の理由については、ノード装置がラベル割当て失敗メッセージに書き込んで前段ノード装置に送信する方法が好ましい。
【０１０５】
ここで、ノード装置がループであると判断したときに受信したラベル割当てメッセージを廃棄する場合について説明する。
【０１０６】
ループを検出したノード装置（ここではＲ２）に、そのきっかけとなったラベル割当てメッセージを送信したノード装置（ここではＲ５）は、ラベル割当てメッセージを送信して一定時間経過後にラベル割当て成功メッセージが返ってこなかったならばラベル割当てメッセージを再送する手順を繰り返し行い、再送の繰り返し回数がしきい値を越えたら、ラベル割当て失敗メッセージが返されたものとみなすものとする。なお、この機能は、ノード装置がループであると判断したときにラベル割当て失敗メッセージを返すように構成する場合にも、備えるのが好ましい。
【０１０７】
ループを検出したノード装置（ここではＲ２）にそのきっかけとなったラベル割当てメッセージを送信したノード装置（ここではＲ５）の上流側の各ノード装置（ここではＲ４など）は、やはり、ラベル割当てメッセージを送信して一定時間経過後にラベル割当て成功メッセージが返ってこなかったので、ラベル割当てメッセージを再送することになる。ここで、ノード装置は、フロー識別子と入力側ラベルと初段ノード情報を同じとするラベル割り当てメッセージ（ホップカウントを併用する場合は、フロー識別子と入力側ラベルと初段ノード情報とホップカウントを同じとするラベル割り当てメッセージ）を受信したら、これに対してラベル割り当て成功メッセージを返すようにするものとする。したがって、例えば、ノード装置Ｒ４がラベル割当てメッセージをノード装置Ｒ５に再送することで、ノード装置Ｒ４はノード装置Ｒ５からラベル割当て成功メッセージを受信することになる。
【０１０８】
（第２の実施形態）
次に、本発明の第２の実施形態に係るラベル割り当てプロトコルおよびこのラベル割り当てプロトコルに従ってラベルスイッチングを行うノード装置について説明する。
【０１０９】
本実施形態は、第１の実施形態と基本的には同様であるので、以下では相違する部分を中心に説明する。
【０１１０】
本実施形態では、第１の実施形態と同様に、ノード装置は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）処理を行う機能を持つとともに、本実施形態に係るラベル割り当てプロトコルに従ってラベルスイッチングを行う機能（第１の実施形態のループ検出機能でホップカウントを併用するものをも含む）を持つ。また、末端に位置し中継を行わないノード装置以外のノード装置は、ルータ機能を持つ。また、ここでは、ノード装置が後段ノードにメッセージ送信後ＡＣＫ信号待ちのときに、前段ノードから状態の変更を伴うメッセージを受信しないような排他制御を別に行っているものとする。
【０１１１】
本実施形態が特に第１の実施形態と相違する点は、第１の実施形態においてはノード装置ではラベルのマージは行わないものとしたが、本実施形態のノード装置はフロー識別子が等しい複数の入力側ラベルに対して同一の出力側ラベルを対応させることによりラベルのマージを行う点である。すなわち、本実施形態のノード装置は、ラベルスイッチングを行う機能として、ラベルのマージに関する処理を行う機能を持つ。
【０１１２】
なお、全てのノード装置がラベルのマージを行うのではなく、ラベルのマージを行わないノード装置が混在していてもよい。ラベルのマージを行うノード装置は、ラベル割り当てメッセージに応答して、ラベルのマージに先だって、ホップカウント更新メッセージを送信し、ホップカウント更新成功メッセージが返ってきた場合にラベルのマージが成功となるような機能を持つ点が、ラベルのマージを行わないノード装置と相違する点である。
【０１１３】
本実施形態では、ノード装置は、ラベル割り当てメッセージを受信し、出力インタフェースにおいてラベルを割り当て、後段のノード装置にラベル割り当てメッセージを送信するにあたって、少なくとも初段ノード情報、フロー識別子、入力側ラベル、出力側ラベル、ホップカウント（すなわち初段からのホップ数）を対応付けて記憶しておく。そして、ラベル割り当てメッセージに応答してラベルをマージしようとするノード装置は、これからマージしようとする新たなパケットルートのホップカウントｈ１がすでにラベルスイッチングパスを設定したパケットルートのホップカウントｈ２以下である場合にはマージを行うが、ホップカウントｈ１がホップカウントｈ２を越える場合には、マージに先だって、少なくとも初段ノード情報、フロー識別子、ラベル、ホップカウントを含むホップカウント更新メッセージを次ホップノードに送信する。なお、当該ノード装置においてすでに他のパスのマージが行われており、異なる初段ノードに対するホップカウントが複数登録されている場合には、その中で最大のホップカウントをｈｍａｘとすると、これからマージしようとする新たなパケットルートのホップカウントｈ１がホップカウントｈｍａｘ以下である場合にはマージを行い、ホップカウントｈ１がホップカウントｈｍａｘを越える場合には、マージに先だって、ホップカウント更新メッセージを送信することになる。ホップカウント更新メッセージを受信したノード装置では、（第１の実施形態と同様の方法で）ループを検出せずかつホップカウントがしきい値以下の場合にはホップカウント更新メッセージを次ホップノードに送信するが、記憶しているフロー識別子等の情報の組に対して、フロー識別子と初段ノード情報が一致するが入力側ラベルが相違するようなホップカウント更新メッセージを受信した場合、またはホップカウントがしきい値を越える場合には、ループであると判断する。ただし、ラベルスイッチングパスの終点に位置するノード装置がホップカウント更新メッセージを受信し、ループを検出せずかつホップカウントがしきい値以下の場合には、ホップカウント更新メッセージの代わりにラベル割り当てメッセージを次ホップノードに送信する。
【０１１４】
ここでは、ホップカウントのしきい値を８に設定するものとする。
【０１１５】
第１の実施形態では、ノード装置間でやり取りされるメッセージには、ラベル割当てメッセージ、ラベル割当て成功メッセージ、ラベル割当て失敗メッセージの３つがあったが、本実施形態では、これらに加えて、マージのために用意されたホップカウント更新メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージの３つがある。また、各メッセージには、ホップカウントが書き込まれる。なお、前述したように、ラベルのマージを行わないノード装置は、ホップカウント更新メッセージを送信する起点とはならないが、ホップカウント更新メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージを受信したときの処理を行う機能は有するものである。
【０１１６】
本実施形態では、第１の実施形態と同様に、宛先ＩＰアドレスが同じパケットは同一のパケットフローであるものとする。
【０１１７】
初段ノード情報、フローＩＤ、ラベル、リンク識別子、入力側ラベル、出力側ラベルは、第１の実施形態と同様である。
【０１１８】
次に、図４〜図７を参照しながら本実施形態のラベル割り当てプロトコルに従った動作について説明する。
【０１１９】
ここでは、まず、第１の実施形態と同様に、ノード装置Ｒ１から宛先アドレスｄｅｓｔ宛のパケットのルートが、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５，Ｒ２，Ｒ３，…とループしている場合に、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスが形成され、その後、ノード装置Ｒ６，Ｒ７，Ｒ８からノード装置Ｒ３への接続ができ、ノード装置Ｒ３でラベルのマージが行われようとするケースについて説明する。なお、説明のために、ノード装置Ｒ３のノード装置Ｒ２に対するリンク識別子をｉ２、ノード装置Ｒ４に対するリンク識別子をｉ４、ノード装置Ｒ８に対するリンク識別子をｉ８とする。
【０１２０】
まず、図４において、ノード装置Ｒ１が、前述したように宛先ｄｅｓｔに対するルーティングテーブルが生成されたときなどを契機に、宛先ｄｅｓｔに対する自ノードの次ホップノードであるノード装置Ｒ２への出力インタフェースにおいて、新たなラベルａを割当て、ノード装置Ｒ２に、（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ａ，ホップカウント＝１）のラベル割当てメッセージｍ１を送信する。また、ノード装置Ｒ１は、少なくとも、フロー識別子、初段ノード情報、出力側ラベル、ホップカウント（＝０）を対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１２１】
ノード装置Ｒ２は、ノード装置Ｒ１からのラベル割当てメッセージｍ１を受信すると、自ノードの次ホップノードであるノード装置Ｒ３への出力インタフェースにおいて新たなラベルｂを割当て、受信したホップカウントをインクリメントし、ノード装置Ｒ３に（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｂ，ホップカウント＝２）のラベル割当てメッセージを送信する。また、適当なタイミングで、少なくともフロー識別子（＝ｄｅｓｔ）、初段ノード情報（＝Ｒ１）、入力側ラベル（＝（ｉ２，ｂ））、出力側ラベル（＝（ｉ４，ｃ））、受信したホップカウント（＝１）を対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１２２】
同様にして、ラベル割当てメッセージがノード装置Ｒ３からＲ４，ノード装置Ｒ４からＲ５，ノード装置Ｒ５からＲ２へとフォワードされていくとともに、各ノード装置Ｒ３〜Ｒ５において、出力インタフェースにおけるラベルの割当てやフロー識別子等の情報の組の記憶と保留を示す情報の付加が行われる。
【０１２３】
次に、ノード装置Ｒ２が、ノード装置Ｒ５から（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｅ，ホップカウント＝５）のラベル割当てメッセージｍ５を受信したとき、すでにノード装置Ｒ１から受信したラベル割当てメッセージｍ１の受信に応答して記憶した情報の組と、入力側ラベルが異なっており（前者が（ｉ１，ａ）であるのに対して後者が（ｉ５，ｅ））、かつ、初段ノード情報、フロー識別子ともに一致するため、ノード装置Ｒ２はループであると判断し、受信したラベル割当てメッセージｍ５を廃棄するか、ノード装置Ｒ５に対してラベル割当て失敗メッセージを返す。
【０１２４】
以降の処理は、第１の実施形態と同様である。
【０１２５】
この結果、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスが形成される。また、ノード装置Ｒ５からはＩＰパケットのＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールドあるいはホップリミット・フィールドあるいはこれらに相当するものを用いた通常のＩＰ転送が行われる。
【０１２６】
なお、前述したように、このような状態は過渡的な状態であり、一定時間経過すると、正常なルートに回復するようにルーティングプロトコルは動作し、これに伴い、ラベルスイッチングパスの変更も行われる。
【０１２７】
また、ホップカウントがしきい値を越える場合にもループ検出とみなされ、この場合にも、ノード装置は、受信したラベル割当てメッセージを廃棄するか、前段のノード装置に対してラベル割当て失敗メッセージを返す。
【０１２８】
次に、図４のようにノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスが形成された状態から、新たにノード装置Ｒ６，Ｒ７，Ｒ８が接続し、図５のようなトポロジーになり、ノード装置Ｒ６がラベル割り当てメッセージを送信した場合を例にとって、ラベルのマージを行う場合におけるループ検出とラベルスイッチングパスの形成について説明する。
【０１２９】
まず、ノード装置Ｒ６は、ノード装置Ｒ７への出力インタフェースにおいて、新たなラベルｆを割り当て、Ｒ７に（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｆ，ホップカウント＝１）のラベル割当てメッセージｍ６を送信する。また、ノード装置Ｒ６は、少なくとも、フロー識別子、初段ノード情報、出力側ラベル、ホップカウント（＝０）を対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１３０】
ノード装置Ｒ７は、ノード装置Ｒ６からのラベル割当てメッセージｍ６を受信すると、自ノードの次ホップノードであるノード装置Ｒ８への出力インタフェースにおいて新たなラベルｇを割当て、受信ホップカウントをインクリメントし、ノード装置Ｒ８に、（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｇ，ホップカウント＝２）のラベル割当てメッセージｍ７を送信する。また、適当なタイミングで、少なくともフロー識別子、初段ノード情報、入力側ラベル、出力側ラベル、受信したホップカウントを対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１３１】
ノード装置Ｒ８は、ノード装置Ｒ７からのラベル割当てメッセージｍ７を受信すると、自ノードの次ホップノードであるノード装置Ｒ３への出力インタフェースにおいて新たなラベルｈを割当て、受信ホップカウントをインクリメントし、ノード装置Ｒ３に、（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｈ，ホップカウント＝３）のラベル割当てメッセージｍ８を送信する。また、適当なタイミングで、少なくともフロー識別子、初段ノード情報、入力側ラベル、出力側ラベル、受信したホップカウントを対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１３２】
次に、ノード装置Ｒ３がノード装置Ｒ８からのラベル割当てメッセージｍ８を受信したとき、すでにノード装置Ｒ２から受信したラベル割当てメッセージｍ２に応答して記憶したフロー識別子等の情報の組（フロー識別子＝ｄｅｓｔ、初段ノード情報＝Ｒ１、入力側ラベル＝（ｉ２，ｂ）、出力側ラベル＝（ｉ４，ｃ）、ホップカウント＝２）があるが、フロー識別子が同一であり、入力側ラベルが異なっており、かつ、初段ノード情報が異なっているため、マージを行う対象となる。しかし、初段ノードからの最大のホップ数（ホップカウント）が、２から３に増えるため、新たに受信したラベルｈと、すでに割当てている出力側のラベルｃとの対応付けをすぐには行わず、下流ノードのノード装置Ｒ４に、初段ノード情報とホップカウントの更新のために、（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｃ，ホップカウント＝４）のホップカウント更新メッセージｍ９を送信する。また、ノード装置Ｒ３は、少なくともフロー識別子（＝ｄｅｓｔ）、初段ノード情報（＝Ｒ６）、入力側ラベル（＝（ｉ８，ｅ））、出力側ラベル（＝（ｉ４，ｃ））、受信したホップカウント（＝３）を対応付けて記憶する。その際、保留を示す情報を付加しておく。
【０１３３】
なお、本実施形態では、ホップカウント更新メッセージに書き込まれる初段ノード情報には、ホップカウント更新メッセージを送信するノードよりも上流にある初段ノードからのホップカウントが最大となるような初段ノードに関する初段ノード情報が設定されることになるが、共通の出力側ラベルを持つようなそのフローに対する任意のフローテーブルエントリ中の初段ノード情報をホップカウント更新メッセージに書き込んで送信してもループ検出が可能である。
【０１３４】
ノード装置Ｒ４は、ノード装置Ｒ３からのホップカウント更新メッセージｍ９を受信すると、自ノードの次ホップノードであるノード装置Ｒ５に、（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｄ，ホップカウント＝５）のホップカウント更新メッセージｍ１０を送信する。また、ノード装置Ｒ４は、フロー識別子等の情報の組を対応付けて記憶しこれに保留を示す情報を付加するとともに、先にラベル割当てメッセージｍ３に応答して記憶したフロー識別子等の情報の組について、初段ノード情報の更新後の内容Ｒ６とホップカウントの更新後の値４を保持し、更新保留を示す情報を付加しておく。
【０１３５】
ラベルスイッチングパスの終点にあたるノード装置Ｒ５は、ノード装置Ｒ４からのホップカウント更新メッセージｍ１０を受信すると、自ノードの次ホップノードであるノード装置Ｒ２に、（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｅ，ホップカウント＝６）のラベル割当てメッセージｍ１１を送信する。また、ノード装置Ｒ５は、フロー識別子等の情報の組を対応付けて記憶しこれに保留を示す情報を付加するとともに、先にラベル割当てメッセージｍ４に応答して記憶したフロー識別子等の情報の組について、初段ノード情報の更新後の内容Ｒ６とホップカウントの更新後の値５を保持し、更新保留を示す情報を付加しておく。
【０１３６】
ノード装置Ｒ２は、ノード装置Ｒ５からのラベル割当てメッセージｍ１１を受信すると、上記のノード装置Ｒ３と同様に、すでにノード装置Ｒ１から受信した同じフロー識別子に対する入力側ラベルａが存在するが、ホップカウント値がラベルａに対するホップカウント値よりも大きいため、受信したラベル＝ｅと出力側のラベル＝ｂとの対応はまだ行わず、自ノードの次ホップノードであるＲ３へ、受信したホップカウントをインクリメントした（初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔ，ラベル＝ｂ，ホップカウント＝７）のホップカウント更新メッセージｍ１２を送信する。また、ノード装置Ｒ２は、フロー識別子等の情報の組を対応付けて記憶しこれに保留を示す情報を付加しておく。
【０１３７】
ノード装置Ｒ２からこのホップカウント更新メッセージｍ１２を受信したノード装置Ｒ３は、初段ノード＝Ｒ６，フロー識別子＝ｄｅｓｔであるようなラベル割り当てメッセージを異なる入力側ラベル（ｉ２，ｂ）と（ｉ８，ｅ）で受信したことになるため、ループであると判断し、このホップカウント更新メッセージｍ１２を廃棄して、ノード装置Ｒ２に対してホップカウント更新失敗メッセージを送信する。
【０１３８】
ノード装置Ｒ３からホップカウント更新失敗メッセージを受信したノード装置Ｒ２は、自装置にホップカウントが更新されるようなラベル割当てメッセージｍ１１を送信したノード装置Ｒ５に対してラベル割当て失敗メッセージを送信するとともに、ラベル割当てメッセージｍ１１に応答して記憶したフロー識別子等の情報の組をキャンセルする。
【０１３９】
さて、以降、ノード装置Ｒ５からその上流のノード装置に次々とメッセージが伝えられていくわけであるが（Ｒ５→Ｒ４→Ｒ３→Ｒ８→Ｒ７→Ｒ６）、このための処理としてはいくつかのものが考えられる。以下では、（１）ラベル割り当て失敗メッセージを受信したノード装置（本例ではＲ５）が上流のノード装置（本例ではＲ４）に対してホップカウント更新失敗メッセージを送信するようにした場合（マージさせない場合）と、（２）ラベル割り当て失敗メッセージを受信したノード装置（本例ではＲ５）が上流のノード装置（本例ではＲ４）に対してホップカウント更新成功メッセージを送信するようにした場合（マージさせる場合）についてそれぞれ説明する。
【０１４０】
まず、上記の（１）のラベル割り当て失敗メッセージを受信したノード装置（本例ではＲ５）が上流のノード装置（本例ではＲ４）に対してホップカウント更新失敗メッセージを送信するようにした場合（マージさせない場合）について説明する。
【０１４１】
ノード装置Ｒ２からラベル割当て失敗メッセージを受信したノード装置Ｒ５は、自装置にホップカウント更新メッセージｍ１０を送信したノード装置Ｒ４に対してホップカウント更新失敗メッセージを送信するとともに、ホップカウント更新メッセージｍ１０に応答して記憶したフロー識別子等の情報の組をキャンセルし、またラベル割当てメッセージｍ４に応答して記憶したフロー識別子等の情報の組については初段ノード情報をもとの内容Ｒ１のままで、またホップカウントをもとの値４のままで、更新保留を示す情報をクリアする。
【０１４２】
ノード装置Ｒ５からホップカウント更新失敗メッセージを受信したノード装置Ｒ４は、自装置にホップカウント更新メッセージｍ９を送信したノード装置Ｒ３に対してホップカウント更新失敗メッセージを送信するとともに、ホップカウント更新メッセージｍ９に応答して記憶したフロー識別子等の情報の組をキャンセルし、またラベル割当てメッセージｍ３に応答して記憶したフロー識別子等の情報の組については初段ノード情報をもとの内容Ｒ１のままで、またホップカウントをもとの値３のままで、更新保留を示す情報をクリアする。
【０１４３】
ノード装置Ｒ４からホップカウント更新失敗メッセージを受信したノード装置Ｒ３は、自装置にホップカウントが更新されるようなラベル割当てメッセージｍ８を送信したノード装置Ｒ８に対してラベル割当て失敗メッセージを送信するとともに、ラベル割当てメッセージｍ８に応答して記憶したフロー識別子等の情報の組をキャンセルする。
【０１４４】
以降、第１の実施形態で説明した手順と同様に、ノード装置Ｒ３からラベル割当て失敗メッセージを受信したノード装置Ｒ８は、自装置にラベル割当てメッセージｍ７を送信したノード装置Ｒ７に対してラベル割当て成功メッセージを送信し、ノード装置Ｒ７は、自装置にラベル割当てメッセージｍ６を送信したノード装置Ｒ６に対してラベル割当て成功メッセージを送信する。また、ノード装置Ｒ７は、ラベル割当てメッセージｍ６を受信しラベル割当てメッセージｍ７を送信するにあたって記憶したフロー識別子等の情報の組のうち出力側ラベルの情報をキャンセルし、保留を示す情報を、確定を示す情報に変更する。ノード装置Ｒ６は、ラベル割当てメッセージｍ６を送信するにあたって記憶したフロー識別子等の情報の組に付加した保留を示す情報を確定を示す情報に変更する。
【０１４５】
この結果、図６の太線で示されるように、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスの他に、ノード装置Ｒ６，Ｒ７，Ｒ８というループのないラベルスイッチングパスが形成される。
【０１４６】
なお、すでに記憶してあるフロー識別子等の情報の組のうちホップカウントの更新を伴ってラベル割当てメッセージやホップカウント更新メッセージを送信したノード装置が、それに対するラベル割当て成功メッセージやホップカウント更新成功メッセージを受信した場合、自装置にホップカウントが更新されるようなラベル割当てメッセージやホップカウント更新メッセージを送信した前段のノード装置に対応するラベル割当て成功メッセージやホップカウント更新成功メッセージを送信するとともに、ホップカウントを更新後の値に更新して更新保留を示す情報をクリアし、その際に新たに記憶したフロー識別子等の情報に付加した保留を示す情報を、確定を示す情報に変更する。
【０１４７】
次に、前述の（２）のラベル割り当て失敗メッセージを受信したノード装置（本例ではＲ５）が上流のノード装置（本例ではＲ４）に対してホップカウント更新成功メッセージを送信するようにした場合（マージさせる場合）について説明する。
【０１４８】
ノード装置Ｒ２からラベル割り当て失敗メッセージを受信したノード装置Ｒ５は、自装置にホップカウント更新メッセージｍ１０を送信したノード装置Ｒ４に対してホップカウント更新成功メッセージを送信するとともに、ホップカウント更新メッセージｍ１０に応答して記憶したフロー識別子等の情報の組を確定する。
【０１４９】
ノード装置Ｒ５からホップカウント更新成功メッセージを受信したノード装置Ｒ４は、自装置にホップカウント更新メッセージｍ９を送信したノード装置Ｒ３に対してホップカウント更新成功メッセージを送信するとともに、ホップカウント更新メッセージｍ９に応答して記憶したフロー識別子等の情報の組に付加した保留を示す情報を、確定を示す情報に変更する。
【０１５０】
ノード装置Ｒ４からホップカウント更新成功メッセージを受信したノード装置Ｒ３は、自装置にホップカウントが更新されるようなラベル割り当てメッセージｍ８を送信したノード装置Ｒ８に対してラベル割り当て成功メッセージを送信するとともに、ラベル割り当てメッセージｍ８に応答して記憶したフロー識別子等の情報の組に付加した保留を示す情報を、確定を示す情報に変更する。
【０１５１】
以降、第１の実施形態で説明した手順と同様に、ノード装置Ｒ３からラベル割当て成功メッセージを受信したノードＲ８は、自装置にラベル割り当てメッセージｍ７を送信したノード装置Ｒ７に対してラベル割り当て成功メッセージを送信し、ノード装置Ｒ７は、自装置にラベル割り当てメッセージｍ６を送信したノード装置Ｒ６に対してラベル割り当て成功メッセージを送信する。また、ノード装置Ｒ８，Ｒ７，Ｒ６は、それぞれ、ラベル割り当てメッセージを受信しラベル割り当てメッセージを送信するにあたって記憶したフロー識別子等の情報の組に付加した保留を示す情報を、確定を示す情報に変更する。
【０１５２】
この結果、図７の太線に示されるように、ノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスと、ノード装置Ｒ６，Ｒ７，Ｒ８，Ｒ３，Ｒ４，Ｒ５というラベルスイッチングパスの２つのパスの共通部分であるＲ３，Ｒ４，Ｒ５の部分がマージされた１つのツリー上のラベルスイッチングパスが生成される。
【０１５３】
なお、すでに記憶してあるフロー識別子等の情報のうちホップカウントの更新を伴ってラベル割当てメッセージやホップカウント更新メッセージを送信したノード装置が、それに対するラベル割当て成功メッセージやホップカウント更新成功メッセージを受信した場合、自装置にホップカウントが更新されるようなラベル割当てメッセージやホップカウント更新メッセージを送信した前段のノード装置に対応するラベル割当て成功メッセージやホップカウント更新成功メッセージを送信するとともに、ホップカウントを更新後の値に更新して更新保留を示す情報をクリアし、その際に新たに記憶したフロー識別子等の情報に付加した保留を示す情報を、確定を示す情報に変更する。
【０１５４】
上記した例では、ホップカウントがしきい値８を越える前にループが検出されたが、ホップカウントのしきい値が小さい場合には、ループの検出よりも前にホップカウントがしきい値を越えたことにより更新失敗と判断される場合もある。
【０１５５】
さて、今まではホップカウントのしきい値を８とした場合の動作であるが、ホップカウントのしきい値が５以上の場合、すなわち、ノード装置Ｒ６の接続に伴ってノード装置Ｒ３で生成されたホップカウント更新メッセージのホップカウントが終段ノードであるノード装置Ｒ５までしきい値を越えることなくフォワードされ、かつ、ノード装置Ｒ５でもしきい値を越えない場合には、ノード装置Ｒ５がノード装置Ｒ２に対してただちにラベル割り当てメッセージを送信するかどうか、また、ただちにラベル割り当てメッセージを送信する場合にはその結果にかかわらず、ノード装置Ｒ５からノード装置Ｒ４に対してはホップカウント更新成功メッセージが返される。
【０１５６】
以下では、図５の状態でノード装置Ｒ６がラベル割り当てメッセージｍ６を送信した場合に、ホップカウントのしきい値が４の場合について述べる。
【０１５７】
ホップカウントのしきい値が４の場合にも、ホップカウントのしきい値が５以上の場合と同様、最初は、ラベルスイッチングパスＲ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５が生成される。
【０１５８】
次に、ノード装置Ｒ６，Ｒ７，Ｒ８が接続したときも、ホップカウントのしきい値が５以上の場合と同様、最初、ノード装置Ｒ６から初段ノード＝Ｒ６としたラベル割り当てメッセージが送信されると、このメッセージはホップカウントがインクリメントされながらノード装置Ｒ７，Ｒ８，Ｒ３へとフォワードされ、ノード装置Ｒ３から下流へは初段ノード＝Ｒ６としたホップカウント更新メッセージがホップカウントがインクリメントされながらフォワードされる。
【０１５９】
ホップカウント更新メッセージはホップカウントがしきい値を越えることなくノード装置Ｒ５までフォワードされる。ホップカウント更新メッセージを受信したノード装置Ｒ５は、受信したホップカウントがしきい値を越えるため、ループであると判断し、ホップカウント更新失敗メッセージをノード装置Ｒ４に返すとともに、ホップカウント更新メッセージに応答して記憶したフロー識別子等の情報の組をキャンセルする。
【０１６０】
ノード装置Ｒ５からホップカウント更新失敗メッセージを受信したノード装置Ｒ４は、自装置にホップカウント更新メッセージｍ９を送信したノード装置Ｒ３に対してホップカウント更新失敗メッセージを送信するとともに、ホップカウント更新メッセージｍ９に応答して記憶したフロー識別子等の情報の組に付加した保留を示す情報をキャンセルする。
【０１６１】
ノード装置Ｒ４からホップカウント更新失敗メッセージを受信したノード装置Ｒ３は、自装置にホップカウントが更新されるようなラベル割り当てメッセージｍ８を送信したノード装置Ｒ８に対してラベル割り当て失敗メッセージを送信するとともに、ラベル割り当てメッセージｍ８に応答して記憶したフロー識別子等の情報の組に付加した保留を示す情報をキャンセルする。
【０１６２】
以降、第１の実施形態で説明した手順と同様に、ノード装置Ｒ３からラベル割り当て失敗メッセージを受信したノードＲ８は、自装置にラベル割り当てメッセージｍ７を送信したノード装置Ｒ７に対してラベル割り当て成功メッセージを送信するとともに、ラベル割り当てメッセージｍ７を受信しラベル割り当てメッセージｍ８を送信するにあたって記憶したフロー識別子等の情報の組のうち、出力側ラベルの情報をキャンセルし、保留を示す情報を、確定を示す情報に変更する。また、ノード装置Ｒ７は、自装置にラベル割り当てメッセージｍ６を送信したノード装置Ｒ６に対してラベル割り当て成功メッセージを送信する。ノード装置Ｒ７，Ｒ６は、ラベル割り当てメッセージを受信しラベル割り当てメッセージを送信するにあたって記憶したフロー識別子等の情報の組に付加した保留を示す情報を、確定を示す情報に変更する。
【０１６３】
以上、第２の実施形態についていくつかの例を説明してきたが、以下ではいくつかの変形例について説明する。
【０１６４】
上記では、ノード装置Ｒ２からホップカウント更新メッセージｍ１２を受信したノード装置Ｒ３は、ループを検出し、ノード装置Ｒ２に対してホップカウント更新失敗メッセージを送信するものとしたが、ホップカウント更新メッセージの受信によりループを検出したノード装置は、ホップカウント更新メッセージを廃棄し、ホップカウント更新失敗メッセージを送信しないものとしてもよい。
【０１６５】
ところで、上記では、ノード装置Ｒ４からホップカウント更新失敗メッセージを受信したノード装置Ｒ３は、ノード装置Ｒ８にラベル割り当て失敗メッセージを送信するものとしたので、新たに形成されるラベルスイッチングパスは、ノード装置Ｒ６，Ｒ７，Ｒ８のルートにとどまった。その代わりに、ノード装置Ｒ３は、ラベルのマージは行わないが、ノード装置Ｒ８にラベル割り当て成功メッセージを送信するとともに、先にラベル割当てメッセージｍ８に応答して記憶したフロー識別子等の情報の組をすべてキャンセルしないで、出力側ラベルのみをキャンセルし、自ノードが終点ノードとなって、ノード装置Ｒ６，Ｒ７，Ｒ８，Ｒ３という新たなラベルスイッチングパスを形成するようにしてもよい。
【０１６６】
また、上記では、ラベルスイッチングパスの終点にあたるノード装置（ここではＲ５）は、ホップカウント更新メッセージを受信すると、自ノードの次ホップのノード装置に、ラベル割当てメッセージを送信した。
【０１６７】
前述したようにノード装置は自ノードがラベルスイッチングパスの終点ノードになったならば、その後、適当なタイミングで繰り返しラベル割当てメッセージを送信するように構成した場合には、Ｒ５がＲ４からホップカウント更新メッセージを受信したとき、所定の条件を満たす場合に、Ｒ５がＲ２に対してラベル割り当てメッセージを送信する代わりに、前段ノード装置にホップカウント更新メッセージを送信し、その後、適当なタイミングで繰り返しラベル割当てメッセージを送信するようにしてもよい。
【０１６８】
次に、図８を参照しながら、第１の実施形態や第２の実施形態において、本ラベル割り当てプロトコルにより実際には経路のループができていない状況でループと判断される例について説明する。
【０１６９】
図８に示すように、ノード装置Ｒ１から宛先ｄｅｓｔに対してノード装置Ｒ１，Ｒ２，Ｒ３，Ｒ４というラベルスイッチングパスが構成されていたところ、ある時刻において、ノード装置Ｒ３がダウンしてノード装置Ｒ１からｄｅｓｔへの経路が、ノード装置Ｒ１，Ｒ２，Ｒ５，Ｒ４に変わったものとする。このとき、ノード装置Ｒ２は、ｄｅｓｔへの次ホップノードであるノード装置Ｒ３に対するラベルｂの割り当てを解放するとともに、新たなｄｅｓｔへの次ホップノードであるノード装置Ｒ５に対して、（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｄ，ホップカウント＝２）のラベル割当てメッセージｍ１を送信する。また、前述と同様にフロー識別子等の情報の組の記憶を行う。
【０１７０】
ノード装置Ｒ５は、ノード装置Ｒ２からのラベル割り当てメッセージｍ１を受信すると、ノード装置Ｒ５の次ホップノードであるノード装置Ｒ４への出力インタフェースにおいて新たなラベルｄを割当て、受信したホップカウントをインクリメントし、ノード装置Ｒ４に（初段ノード＝Ｒ１，フロー識別子＝ｄｅｓｔ，ラベル＝ｅ，ホップカウント＝３）のラベル割当てメッセージｍ２を送信する。また、前述と同様にフロー識別子等の情報の組の記憶を行う。
【０１７１】
ノード装置Ｒ５からラベル割当てメッセージｍ２を受信したノード装置Ｒ４は、もし、ノード装置Ｒ３から割り当て要求されたラベルｃがまだ解放されていないか、または、初段ノードからのホップカウントがしきい値に達していれば、ラベルｅとフロー識別子、初段ノード情報等の対応を記憶せずに、ノード装置Ｒ５に対してラベル割り当て失敗メッセージを返す。このとき、ラベル割り当て失敗メッセージには、ラベル割り当て失敗の理由を書き込む。
【０１７２】
一方、ノード装置Ｒ５からラベル割り当てメッセージを受信したノード装置Ｒ４は、もし、ノード装置Ｒ３から割り当て要求されたラベルｃがすでに解放されており、かつ、初段ノードからのホップカウント値がしきい値に達していなければ、ノード装置Ｒ５からのラベルとフロー識別子、初段ノード情報等の対応を記憶するとともに、ノード装置Ｒ５に対してラベル割り当てメッセージに対するラベル割り当て成功メッセージを返す。
【０１７３】
ノード装置Ｒ５は、ラベル割り当て失敗メッセージを受信すると、ラベル割り当て失敗の理由がホップカウントがしきい値を越えたため以外であれば、ノード装置Ｒ４に対して定期的にラベル割り当てメッセージを再送する。この結果、ノード装置Ｒ３とノード装置Ｒ４の間のラベルｃが解放されてから再送されるラベル割り当てメッセージにより、ノード装置Ｒ１，Ｒ２，Ｒ５，Ｒ４のラベルスイッチングパスが構成される。
【０１７４】
このように、経路変更時には、実際にはループ構成されていなくてもループ検出となる場合がある。この場合には、特定の（初段ノード情報、フロー識別子）の組に対応するラベルは常に１つしか存在しないようにすることにより、ルーティングプロトコルの過渡状態において経路が頻繁に変わるような状況で一時的に不要なラベルスイッチングパスが幾つもできてしまう、という問題を解決することができる。
【０１７５】
（第３の実施形態）
次に、本発明の第３の実施形態に係るラベル割り当てプロトコルおよびこのラベル割り当てプロトコルに従ってラベルスイッチングを行うノード装置について説明する。
【０１７６】
本実施形態では、第１の実施形態や第２の実施形態において、初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスと、初段ノードの出力インタフェースローカルに割り当てられる識別子とを用いることができるようにしてある。
【０１７７】
以下、初段ノード情報として、初段ノードの出力インタフェースに対して割り当てられるネットワークレイヤアドレスと、初段ノードの出力インタフェースローカルに割り当てられる識別子とを用いて構成されたラベルスイッチングパスの例を示す。
【０１７８】
図９において、ノード装置Ｒ１，Ｒ２は、従来のラベル割当てプロトコルを使用してラベルスイッチングパスを設定するノード装置であり、ノード装置Ｒ４〜Ｒ６は、本ラベル割り当てプロトコルを使用してラベルスイッチングパスを設定するノード装置である。また、ノード装置Ｒ３は、従来のラベル割当てプロトコルと、本ラベル割り当てプロトコルの両方をサポートし、各々のプロトコルにより作られたラベルスイッチングパスを接続するノード装置である。
【０１７９】
図９では、初段のノード装置Ｒ１，Ｒ２から、宛先アドレスｄｅｓｔに対して２本のラベルスイッチングパス１´，２´が設定されている。このとき、ノード装置Ｒ３は、ラベルスイッチングパス１´，２´の終点ノードであるが、これらのラベルスイッチングパスを、本ラベル割り当てプロトコルを用いて延長する。このとき、ラベルスイッチングパス１´，２´は、初段ノード情報を持っていないため、ノード装置Ｒ３は、２つのパスを区別するために、ノード装置Ｒ３の出力インタフェースでローカルなＩＤ＝１，ＩＤ＝２をラベルスイッチングパス１´，２´に対してそれぞれ割り当て、これを用いてノード装置Ｒ３を本ラベル割り当てプロトコルによるラベルスイッチングパスの初段ノードとするラベルスイッチングパス１，２を設定し、設定が完了すると、ラベルスイッチングパス１´と１の間、およびラベルスイッチングパス２´と２の間でラベルスイッチングを行うことができる。
【０１８０】
初段ノードの出力インターフェースローカルに割り当てられる識別子を用いて構成されたラベルスイッチングパスのもう一つの例を図１０を用いて示す。
【０１８１】
図１０において、Ｒ１からＲ５への経路には、Ｒ１→Ｒ２→Ｒ３→Ｒ５という経路と、Ｒ１→Ｒ２→Ｒ４→Ｒ５という経路が存在する。Ｆｌｏｗｉｄ＝Ｒ５のフローに対してそれぞれの経路に対するラベルスイッチングパスを形成する場合には、初段ノードＲ１から、２つのラベルスイッチングパスが作られることになる。これらのパスを区別するために、同じＩｎｇｒｅｓｓ＝Ｒ１に対してＩｎｇｒｅｓｓ  ＬｏｃａｌＩＤ＝１、Ｉｎｇｒｅｓｓ  Ｌｏｃａｌ  ＩＤ＝２の２つの異なるＩｎｇｒｅｓｓ  Ｌｏｃａｌ  ＩＤが使用される。
【０１８２】
以下では、以上の各実施形態における、メッセージのフォーマットの例、フローテーブルのフォーマットの例、ノード装置の動作手順の例についてそれぞれ説明する。
【０１８３】
図１１、図１２に、各メッセージのフォーマットの一例を示す。
【０１８４】
図１１は、ラベル割り当てメッセージ、ラベル割り当て成功メッセージ、ホップカウント更新メッセージ、ホップカウント更新成功メッセージ、ラベル解放メッセージ、ラベル解放成功メッセージに使用し、図１２は、ラベル割り当て失敗メッセージ、ホップカウント更新失敗メッセージ、ラベル解放失敗メッセージに使用する。図１１と図１２とは、図１２のメッセージにエラーコードフィールドが付加されている点以外は同じである。
【０１８５】
なお、上流側ノードがラベルを割り当てる場合には、リクエストＩＤフィールドは省略してもよい。
【０１８６】
また、初段ノード情報を使用しない場合には、初段ノードアドレス、初段ノードローカルＩＤのフィールドを省略してもよい。また、ホップカウントを使用しない場合には、ホップカウントフィールドを省略してもよく、このとき、「ホップカウント更新メッセージ」は、単に「更新メッセージ」と呼ぶ。
【０１８７】
図１１、図１２において、メッセージタイプは、ラベル割り当てプロトコルで使用されるメッセージの種類（ラベル割当てメッセージ、ラベル割当て成功メッセージ、ラベル割当て失敗メッセージ、ホップカウント更新メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージ）を示す。
【０１８８】
第１の実施形態では、ラベル割当てメッセージ、ラベル割当て成功メッセージ、ラベル割当て失敗メッセージが使用され、第２の実施形態では、ラベル割当てメッセージ、ラベル割当て成功メッセージ、ラベル割当て失敗メッセージ、ホップカウント更新メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージが使用される。
【０１８９】
図１１、図１２において、メッセージｌｅｎｇｔｈは、メッセージ全体の長さを示す。
【０１９０】
送信ノードアドレス、受信ノードアドレスは、それぞれ、このメッセージの送信側、受信側ノードのネットワークアドレスである。
【０１９１】
初段ノードアドレスは、最初にラベル割り当てメッセージを生成したノードのアドレスである。また、初段ノードローカルＩＤは、同じ初段ノードから同一のフロー識別子に対するラベルスイッチングパスを設定するために必要な初段ノードローカルのＩＤである。
【０１９２】
第１および第２の実施形態では、初段ノードアドレスが初段ノード情報である。なお、この場合、初段ノードローカルＩＤのフィールドは不要である。第３の実施形態では、初段ノードアドレスと初段ノードローカルＩＤの組が初段ノード情報である。
【０１９３】
ホップカウントは、初段ノードからのホップカウントを表す。
【０１９４】
フロータイプは、フロー識別子の種類である。フローＩＤ  ｌｅｎｇｔｈは、フロー識別子のビット長である。フローＩＤは、フローＩＤ  ｌｅｎｇｔｈで指定されるビット長で表される、フローの識別子である。
【０１９５】
ラベルのフィールドには、上流側ノードがラベルを割り当てる場合には、上流側ノードが割り当てたラベルが入り、下流側ノードがラベルを割り当てる場合には、リクエストＩＤに対応して下流側ノードが割り当てたラベルが入る（上流側ノードが下流に送るラベル割り当てメッセージのラベルのフィールドは空欄とするかもしくはラベルフィールドがなくてもよい）。また、このラベルのフィールドには、レイヤ２コネクション識別子が入ることもある。
【０１９６】
図１２のラベル割り当て失敗メッセージには、ラベル割り当てメッセージに含まれるフィールドに加え、エラーコードフィールドが付加される。エラーコードには、ラベル割り当てに失敗した場合の理由を書き込む。ここでは、エラーコードとして、「リソース利用不可」、「無効なラベル」、「無効なフロータイプ」、「無効なフロー識別子」、「ポリシーによるラベル割り当て拒否」、「ホップカウントがしきい値を越えた」、「同じ初段ノード情報から同じフロー識別子に対して異なるラベルを受信」の７種類のコードを定義している。
【０１９７】
なお、ラベル割り当て失敗メッセージを受信したノードは、エラーコードの値により、適当なタイミングで繰り返しラベル割り当てメッセージを送信するようにするか、以降のラベル割り当てメッセージの送信をやめるかのいずれかの動作を選択するようにしてもよい。例えば、エラーコードが「ホップカウントがしきい値を越えた」である場合には、以降のラベル割り当てメッセージの送信をやめるようにし、その他の場合には適当なタイミングで繰り返しラベル割り当てメッセージを送信するようにしてもよい。
【０１９８】
次に、図１３に、本ラベル割当てプロトコルが動作するノード装置において使用されるフローテーブルのフォーマットの一例を示す。
【０１９９】
フローテーブルは、現在、ラベルスイッチングされているフローにおける、フロー識別子、初段ノード情報（初段ノードアドレス、または初段ノードアドレスと初段ノードローカルＩＤの組）、入力側ラベル（リンク識別子、ラベル）、出力側ラベル（リンク識別子、ラベル）、ホップカウント値、初段ノードかどうかを示す初段フラグ、終段ノードかかどうかを示す終段ノードフラグが書き込まれる。なお、図１３は、フロー識別子が１種類の場合の例である。
【０２００】
また、第１および第２の実施形態では、初段ノードローカルＩＤのフィールドは不要である。
【０２０１】
第１の実施形態で、ホップカウントを併用しない場合には、ホップカウント値のフィールドは不要である。
【０２０２】
また、初段ノードフラグは、初段ノード情報に該当するノード装置が、ラベル割り当てメッセージを送信するにあたって、セットする。
【０２０３】
終段ノードフラグは、自ノードがフロー識別子で指定されるフローの宛先であるノード装置、または次ホップノードが本ラベル割り当てプロトコルをサポートしていないようなノード装置が、例えばラベル割り当てメッセージを受信した際に、セットする。
【０２０４】
なお、各ノード装置は、隣接するノード装置が本ラベル割り当てプロトコルをサポートするか否かを、例えば予めまたは必要時に隣接ノード装置と通信することによって知ることができる。
【０２０５】
次に、図１４に、第１の実施形態、第２の実施形態においてラベル割り当てメッセージを受信したときのノード装置の動作の一例を示す。
【０２０６】
ラベル割り当てメッセージを受信すると、まず、ホップカウントの更新を示すフラグであるＵｐｄａｔｅフラグをクリアし（ステップＳ１）、フローテーブルの先頭から順番にエントリを検索してゆく（ステップＳ２，Ｓ３，Ｓ１０，Ｓ１１）。なお、フローテーブルにエントリがない場合には、ステップＳ１２に移る。
【０２０７】
初段ノードでなく（初段フラグがオフ）、かつ、エントリ中の入力側ラベルが受信メッセージ中のラベルと等しい場合には（ステップＳ４  ＹＥＳ）、受信メッセージ中のフロー識別子、初段ノード情報、ホップカウントがエントリ中の値と等しいかどうかをチェックし、すべて一致していれば、前段ノードにラベル割当て成功メッセージを返す（ステップＳ１９，Ｓ２０，Ｓ２１，Ｓ１８）。そうでなければ、前段ノードにラベル割当て失敗メッセージを返す（ステップＳ１９，Ｓ２０，Ｓ２１，Ｓ２２）。この場合、ラベル割当てメッセージ受信処理は終了する。
【０２０８】
一方、初段ノードである（初段フラグがオン）、または、エントリ中の入力側ラベルが受信メッセージ中のラベルと異なる場合には（ステップＳ３  ＮＯ）、フロー識別子をチェックする（ステップＳ５）。フロー識別子が異なる場合には、次のフローテーブルエントリを調べる。フロー識別子が等しい場合には、初段ノード情報が等しいかどうかをチェックし（ステップＳ６）、初段ノード情報が等しい場合には、前段ノードにラベル割り当て失敗メッセージを返す（ステップＳ２２）。初段ノード情報が異なる場合には、ラベルマージをサポートし、かつ、受信メッセージ中のホップカウントがエントリ中のホップカウントより大きい場合には、Ｕｐｄａｔｅフラグをセットし（ステップＳ７，Ｓ８，Ｓ９）、次のフローテーブルエントリを調べる（ステップＳ１０，Ｓ１１）。ラベルマージをサポートしない、または、受信メッセージ中のホップカウントがエントリ中のホップカウント以下の場合には（ステップＳ７，Ｓ８）、Ｕｐｄａｔｅフラグはそのままで次のフローテーブルエントリを調べる（ステップＳ１０，Ｓ１１）。
【０２０９】
フローテーブルの最後まで検索が終ると（ステップＳ１０）、受信メッセージ中のホップカウントをチェックする（ステップＳ１２）。ホップカウントがしきい値を越える場合には、前段ノードにラベル割当て失敗メッセージを返す（ステップＳ２２）。ホップカウントがしきい値以下の場合には、新たにフローテーブルエントリを作成し（ステップＳ１３）、終段ノードである（終段フラグがオンである）場合には、前段ノードにラベル割当て成功メッセージを返す（ステップＳ１８）。終段ノードでない（終段フラグがオフである）場合には、Ｕｐｄａｔｅフラグをチェックし（ステップＳ１５）、Ｕｐｄａｔｅフラグがオンの場合には、後段ノードにホップカウント更新メッセージを送信する（ステップＳ１７）。Ｕｐｄａｔｅフラグがオフの場合には、後段ノードにラベル割当てメッセージを送信する（ステップＳ１６）。なお、ステップＳ１６において、さらに前段ノードにラベル割り当て成功メッセージを送信するようにしてもよい。
【０２１０】
なお、ステップＳ１３のフローテーブルエントリの作成では、前述したように確定を保留しておき、ラベル割り当て成功メッセージが返されて始めて確定させる。
【０２１１】
また、ホップカウントを使用しない場合には、図１４のステップＳ７のＹｅｓの出力とステップＳ９の入力とを直結し、ステップＳ２のＮｏの出力およびステップＳ１０のＹｅｓの出力とステップＳ１３の入力とを直結し、ステップＳ２０のＹｅｓの出力とステップＳ１８の入力とを直結すればよい。この場合には、終段ノードでなければマージ点から常に後段ノードに対して更新メッセージが送信されることになるため、ホップカウントを用いる場合に比べて送信されるメッセージの数が増加する。
【０２１２】
次に、図１５に、第２の実施形態においてホップカウント更新メッセージを受信したときのノード装置の動作の一例を示す。
【０２１３】
ホップカウント更新メッセージを受信すると、Ｆｉｎｄフラグ、Ｕｐｄａｔｅフラグを０に設定し（ステップＳ３１）、フローテーブルの先頭から順番にエントリを検索してゆく（ステップＳ３２，Ｓ３３，Ｓ３７，Ｓ３８）。なお、フローテーブルにエントリがない場合には、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ３２，Ｓ４５）。
【０２１４】
初段ノードでなく（初期フラグがオフ）、かつ、エントリ中の入力側ラベルが受信メッセージ中のラベルと等しい場合には（ステップＳ３４）、Ｆｉｎｄフラグを１に設定し（ステップＳ３９）、受信メッセージ中のフロー識別子がエントリ中の値と等しいかどうかをチェックし（ステップＳ４０）、一致していなければ、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ４５）。一致していれば、ホップカウントがエントリ中の値と等しいかどうかをチェックし（ステップＳ４１）、ホップカウントが異なれば、Ｕｐｄａｔｅフラグを１に設定し（ステップＳ４２）、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。
【０２１５】
一方、初段ノードである（初段フラグがオン）、または、エントリ中の入力側ラベルが受信メッセージ中のラベルと異なる場合には（ステップＳ３４）、受信メッセージ中のフロー識別子がエントリ中の値と等しいかどうかをチェックし（ステップＳ３５）、一致していなければ、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ８）。一致していれば、受信メッセージ中の初段ノード情報がエントリ中の値と等しいかどうかをチェックし（ステップＳ３６）、一致していれば、前段ノードにホップカウント更新失敗メッセージを渡す（ステップＳ４５）。一致していなければ、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。
【０２１６】
すべてのフローテーブルエントリを調べ終ったときに（ステップＳ３７）、Ｆｉｎｄフラグが０のままであれば（ステップＳ４３）、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ４５）。Ｆｉｎｄフラグが１であれば（ステップＳ４３）、受信メッセージ中のホップカウントがしきい値以下であるかどうかをチェックし（ステップＳ４４）、しきい値を越えていれば、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ４５）。ホップカウントがしきい値以下である場合には次にＵｐｄａｔｅフラグを調べる（ステップＳ４６）。Ｕｐｄａｔｅフラグが０のままであれば、前段ノードにホップカウント更新成功メッセージを送信する（ステップＳ４９）。Ｕｐｄａｔｅフラグが１になっていれば、フローテーブルエントリの初段ノード情報とホップカウントを更新するための処理を行い（ステップＳ４７）、終段ノードかどうかを調べる（ステップＳ４８）。終段ノードであれば、前段ノードにホップカウント更新成功メッセージを送信する（ステップＳ４９）。終段ノードでなければ、出力側ラベルが存在するかどうかを調べ（ステップＳ５０）、存在する場合には、後段ノードにホップカウント更新メッセージを送信し（ステップＳ５２）、存在しない場合には、後段ノードにラベル割り当てメッセージを送信する（ステップＳ５１）。
【０２１７】
なお、ステップＳ４７のフローテーブルエントリの初段ノード情報とホップカウントを更新するための処理では、前述したように確定を保留しておき、ホップカウント更新成功メッセージが返されて始めて確定させる。
【０２１８】
また、ホップカウントを使用しない場合には、図１５のステップＳ４３のＹｅｓの出力とステップＳ４６の入力とを直結し、ステップＳ４０のＹｅｓの出力とステップＳ４２の入力とを直結すればよい。この場合には、Ｆｉｎｄ＝１かつ終段ノードでなければ常に後段ノードに対してラベル割り当てメッセージまたは更新メッセージが送信されることになるため、ホップカウントを用いる場合に比べて送信されるメッセージの数が増加する。
【０２１９】
ラベル割り当て成功メッセージ、ラベル割り当て失敗メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージを受信したときのノード装置の処理手順、初段のノード装置がラベル割り当てメッセージを送信するときの処理手順等は、前述した通りである。
【０２２０】
次に、図１６に、第１の実施形態、第２の実施形態においてラベル割り当てメッセージを受信したときのノード装置の動作の一例を示す。
【０２２１】
図１６は、ホップカウントを併用するプロトコルに対応するものであり、ホップカウントを併用しない場合、図１６においてステップＳ１２を省き、ステップＳ２とＳ１０をステップＳ１３に直結すればよい。
【０２２２】
ただし、この例では、ホップカウントを使用しない場合には、ループ検出に初段ノード情報を必ず使用する。
【０２２３】
なお、図１５のような手順を持つ第２の実施形態のノード装置を常にマージしないように設定することにより、第１の実施形態のノード装置（ホップカウントを併用するもの）として使用することができる。
【０２２４】
ラベル割り当て成功メッセージ、ラベル割り当て失敗メッセージを受信したときのノード装置の処理手順、初段のノード装置がラベル割り当てメッセージを送信するときの処理手順等は、前述した通りである。
【０２２５】
これまでのノード装置の動作手順の例では、ノード装置が後段ノードにメッセージ送信後ＡＣＫ信号待ちの状態のときに前段ノードから状態の変更を伴うメッセージを受信しないような排他制御を別に行う場合について述べたが、以降の例では、ＡＣＫ待ちの状態のときに前段ノードから状態の変更を伴うメッセージを受信するような場合にラベルスイッチングパス全体の状態の一貫性を保ような排他制御も行うような場合について述べる。これから述べる例では、ノードがラベルのマージを行うならば、初段ノード情報を用いなくてもループ検出が可能である。
【０２２６】
以下の例で用いるメッセージのフォーマットについては、図１１、図１２を参照しながら説明したものと同様である。
【０２２７】
図１７に、本ラベル割当てプロトコルが動作するノード装置において使用されるフローテーブルのフォーマットの一例を示す。
【０２２８】
フローテーブルは、現在、ラベルスイッチングされているフローにおける、フロー識別子、初段ノード情報（初段ノードアドレス、または初段ノードアドレスと初段ノードローカルＩＤの組）、入力側ラベル（リンク識別子、ラベル）、出力側ラベル（リンク識別子、ラベル）、ホップカウント値、初段ノードかどうかを示す初段フラグ、終段ノードかどうかを示す終段ノードフラグ、エントリが確定したかを示す確定フラグが書き込まれる。なお、図１７は、フロー識別子が１種類の場合の例である。
【０２２９】
ループ検出に初段ノード情報を用いない場合には、初段ノード情報用のフィールドはなくてもよいが、ループ検出に初段ノード情報を用いる場合に比べ、ループ検出をするためにラベル割り当てメッセージおよびホップカウント更新メッセージがより多くのノードを経由する可能性がある。
【０２３０】
また、第１および第２の実施形態では、初段ノードローカルＩＤのフィールドは不要である。
【０２３１】
第１の実施形態で、ホップカウントを併用しない場合には、ホップカウント値のフィールドは不要である。
【０２３２】
また、初段ノードフラグは、初段ノード情報に該当するノード装置が、ラベル割り当てメッセージを送信するにあたって、セットする。
【０２３３】
終段ノードフラグは、自ノードがフロー識別子で指定されるフローの宛先であるノード装置、または次ホップノードが本ラベル割り当てプロトコルをサポートしていないようなノード装置が、例えばラベル割り当てメッセージを受信した際に、セットする。
【０２３４】
なお、各ノード装置は、隣接するノード装置が本ラベル割り当てプロトコルをサポートするか否かを、例えば予めまたは必要時に隣接ノード装置と通信することによって知ることができる。
【０２３５】
次に、図１８に、第１の実施形態、第２の実施形態においてラベル割り当てメッセージを受信したときのノード装置の動作の一例を示す。本例は、図１４の手順において、ラベル割り当てメッセージを受信した時に常に１個のメッセージしか処理しないように修正したものである。
【０２３６】
ラベル割り当てメッセージを受信すると、まず、ホップカウントの更新を示すフラグであるＵｐｄａｔｅフラグをクリアするとともに、自ノードでマージされたフローの本数を示すカウンタＣｎｔを０にリセットし（ステップＳ１−１）、フローテーブルの先頭から順番に検索してゆく（ステップＳ２，Ｓ３，Ｓ１０，Ｓ１１）。なお、フローテーブルにエントリがない場合には、ステップ１２に移る。
【０２３７】
初段ノードでなく（初段フラグがオフ）、かつ、エントリ中の入力側ラベルが受信メッセージ中のラベルと等しい場合には（ステップＳ４）、受信メッセージ中のフロー識別子、初段ノード情報、ホップカウントがエントリ中の値と等しいかどうかをチェックし、いずれかが一致していなければ、前段ノードにラベル割り当て失敗メッセージを送信し、処理を終了する（ステップＳ１９〜Ｓ２２）。
【０２３８】
一方、すべて一致していれば、エントリ中の確定フラグをチェックし、確定フラグがオンであれば前段ノードにラベル割り当て成功メッセージを送信し（ステップＳ１９，Ｓ２０，Ｓ２１，Ｓ２３，Ｓ２８）、確定フラグがオフであれば、受信したラベル割り当てメッセージを廃棄するか、前段ノードにラベル割り当て失敗メッセージを送信する（ステップＳ１９，Ｓ２０，Ｓ２１，Ｓ２３，Ｓ２４）。後者の場合、ラベル割り当てメッセージ受信処理は終了する。
【０２３９】
一方、初段ノードである（初段フラグがオン）、または、エントリ中の入力側ラベルが受信メッセージ中のラベルと異なる場合には（ステップＳ４）、フロー識別子をチェックする（ステップＳ５）。フロー識別子が異なる場合には、次のフローテーブルエントリを調べる。フロー識別子が等しい場合には、初段ノード情報が等しいかどうかをチェックし（ステップＳ６）、初段ノード情報が等しい場合には、前段ノードにラベル割り当て失敗メッセージを返す（ステップＳ２２）。初段ノード情報が異なる場合には、ラベルマージをサポートする場合には、Ｃｎｔを１だけインクリメントし（ステップＳ７，Ｓ１−２）、さらに受信メッセージ中のホップカウントがエントリ中のホップカウントより大きい場合には（ステップＳ８）、確定フラグがオンか否か調べ（ステップＳ２００）、確定フラグがオンならば、Ｕｐｄａｔｅフラグをセットし（ステップＳ９）、次のフローテーブルエントリを調べる（ステップＳ１０，Ｓ１１）。ステップＳ２００で確定フラグがオフならば、前段ノードにラベル割り当てメッセージを送信し、処理を終了する（ステップＳ２２）。なお、ラベルマージをサポートしない場合、または受信メッセージ中のホップカウントがエントリ中のホップカウント以下の場合には（ステップＳ７，Ｓ８）、Ｕｐｄａｔｅフラグはそのままで次のフローテーブルエントリを調べる（ステップＳ１０，Ｓ１１）。
【０２４０】
フローテーブルの最後まで検索が終ると（ステップＳ１０）、受信メッセージ中のホップカウントをチェックする（ステップＳ１２）。ホップカウントがしきい値を越える場合には、前段ノードにラベル割り当て失敗メッセージを返す（ステップＳ２２）。ホップカウントがしきい値以下の場合には、新たにフローテーブルエントリを作成し（ステップＳ１３）、終段ノードである（終段フラグがオン）場合には、確定フラグをオンにするとともに前段ノードにラベル割り当て成功メッセージを送信する（ステップＳ１８）。終段ノードでない（終段フラグがオフ）場合には、Ｕｐｄａｔｅフラグをチェックし（ステップＳ１５）、Ｕｐｄａｔｅフラグがオンである場合には、確定フラグをオフにするとともに後段ノードにホップカウント更新メッセージを送信する（ステップＳ２７）。Ｕｐｄａｔｅフラグがオフの場合には、Ｃｎｔ＝０（自ノードがマージポイントでない）ならば、確定フラグをオフにするとともに後段ノードにラベル割り当てメッセージを送信し（ステップＳ２５，Ｓ２６）、Ｃｎｔ＞０（自ノードがマージポイントである）ならば、確定フラグをオンにする（マージの設定をする）とともに前段ノードにラベル割り当て成功メッセージを送信する（ステップＳ２５，Ｓ２８）。なお、Ｕｐｄａｔｅフラグがオフの場合には、Ｃｎｔ＝０ならば、ステップＳ２６において、上記に加えてさらに前段ノードにラベル割り当て成功メッセージを送信するようにしてもよい。
【０２４１】
なお、ステップＳ１３のフローテーブルエントリの作成では、前述したように確定を保留しておき（確定フラグをオフに設定）、ラベル割り当て成功メッセージが返されて始めて確定させる（確定フラグをオンに設定）。
【０２４２】
また、ループ検出に初段ノード情報を用いない場合には、図１８のステップＳ５のＹｅｓの出力とステップＳ７の入力とを直結し、ステップＳ１９のＹｅｓの出力とステップＳ２１の入力とを直結すればよい。この場合には、ループ検出に初段ノード情報を用いる場合に比べ、ループ検出をするためにラベル割り当てメッセージおよびホップカウント更新メッセージがより多くのノードを経由することになる。
【０２４３】
また、ホップカウントを使用しない場合には、図１８のステップＳ１−２のＹｅｓの出力とステップＳ２００の入力とを直結し、ステップＳ２のＮｏの出力およびステップＳ１０のＹｅｓの出力とステップＳ１３の入力とを直結し、ステップＳ２０のＹｅｓの出力とステップＳ２３の入力とを直結すればよい。この場合には、終段ノードでなければマージ点から常に後段ノードに対してホップカウント更新メッセージが送信されることになるため、ホップカウントを用いる場合に比べて送信されるメッセージの数が増加する。
【０２４４】
また、ネットワーク内の全ノードがラベルマージをサポートする場合には初段ノード情報、ホップカウント両方使用しないことも可能である。この場合のフローチャートは、ループ検出に初段ノード情報を用いない場合のフローチャートと、ホップカウントを使用しない場合のフローチャートの共通部分になる。この場合のフローチャートを図１９に示す。
【０２４５】
次に、図２０に、第２の実施形態においてホップカウント更新メッセージを受信したときのノード装置の動作の一例を示す。本例は、図１５の手順において、ホップカウント更新メッセージを受信した時に常に１個のメッセージしか処理しないように修正したものである。
【０２４６】
ホップカウント更新メッセージを受信すると、Ｆｉｎｄフラグを０に、Ｕｐｄａｔｅフラグを１にそれぞれ設定し（ステップＳ３１−１）、フローテーブルの先頭から順番にエントリを検索してゆく（ステップＳ３２，Ｓ３３，Ｓ３７，Ｓ３８）。なお、フローテーブルにエントリがない場合には、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ３２，Ｓ６５−２）。
【０２４７】
初段ノードでなく（初段フラグがオフ）、かつ、エントリ中の入力側ラベルが受信メッセージ中のラベルと等しい場合には（ステップＳ３４）、Ｆｉｎｄフラグを１に設定し（ステップＳ３９）、受信メッセージ中のフロー識別子がエントリ中の値と等しいかどうかをチェックし（ステップＳ４０）、一致していなければ、前段ノードにホップカウント更新失敗メッセージを返して処理を終了する（ステップＳ６５−２）。一致していれば、ホップカウントがエントリ中の値と等しいかどうかをチェックし（ステップＳ４１）、ホップカウントが等しければ、初段ノード情報が同じか否かチェックし（ステップＳ６３）、初段ノード情報が同じであれば、確定フラグをオンにするとともに、前段ノードにホップカウント更新成功メッセージを送信する（ステップＳ６９）。ホップカウントが異なるか、または初段ノード情報が同じでなければ、エントリ中の確定フラグをチェックする（ステップＳ６４）。確定フラグがオンであれば、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。確定フラグがオフであれば、受信メッセージを廃棄するか前段ノードにホップカウント更新失敗メッセージを送信し、処理を終了する（ステップＳ６５−１）。
【０２４８】
一方、初段ノードである（初段フラグがオン）、または、エントリ中の入力側ラベルが受信メッセージ中のラベルと異なる場合には（ステップＳ３４）、受信メッセージ中のフロー識別子がエントリ中の値と等しいかどうかをチェックし（ステップＳ３５）、一致していなければ、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。一致していれば、受信メッセージ中の初段ノード情報がエントリ中の値と等しいかどうかをチェックし（ステップＳ３６）、一致していれば、前段ノードにホップカウント更新失敗メッセージを渡す（ステップＳ６５−２）。ステップＳ３６で一致していなければ、確定フラグがオフか否か調べ（ステップＳ２０１）、確定フラグがオフならば、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。また、ステップＳ２０１で確定フラグがオンならば、Ｕｐｄａｔｅフラグを０にクリアしてから（ステップＳ２０２）、次のフローテーブルエントリを調べる（ステップＳ３７，Ｓ３８）。
【０２４９】
すべてのフローテーブルエントリを調べ終ったときに（ステップＳ３７）、Ｆｉｎｄフラグが０のままであれば（ステップＳ４３）、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ６５−２）。Ｆｉｎｄフラグが１であれば（ステップＳ４３）、受信メッセージ中のホップカウントがしきい値以下であるかどうかをチェックし（ステップＳ４４）、しきい値を越えていれば、前段ノードにホップカウント更新失敗メッセージを返す（ステップＳ６５−２）。ホップカウントがしきい値以下である場合には次にＵｐｄａｔｅフラグを調べる（ステップＳ４６）。Ｕｐｄａｔｅフラグが０のままであれば、確定フラグをオンにするとともに、前段ノードにホップカウント更新成功メッセージを送信する（ステップＳ６９）。Ｕｐｄａｔｅフラグが１になっていれば、フローテーブルエントリの初段ノード情報とホップカウントを更新するための処理を行ない（ステップＳ６７）、終段ノードかどうかを調べる（ステップＳ４８）。終段ノードであれば、確定フラグをオンにするとともに前段ノードにホップカウント更新成功メッセージを送信する（ステップＳ６９）。終段ノードでなければ、出力側ラベルが存在するかどうかを調べ（ステップＳ５０）、存在する場合には、確定フラグをオフにするとともに後段ノードにホップカウント更新メッセージを送信し（ステップＳ７２）、存在しない場合には、確定フラグをオフにするとともに後段ノードにラベル割り当てメッセージを送信する（ステップＳ７１）。
【０２５０】
ここで、終段ノード以外のノードは、更新後のホップカウント値が更新前よりも小さくなるような場合には、ステップＳ７１またはＳ７２を実行するとともに、前段ノードにホップカウント更新成功メッセージを送信してもよい。
【０２５１】
なお、ステップＳ６７のフローテーブルエントリの初段ノード情報とホップカウントを更新するための処理では、前述したように確定を保留しておき、ホップカウント更新成功メッセージが返されて始めて確定させる。
【０２５２】
また、ループ検出に初段ノード情報を用いない場合には、図２０のステップＳ３５のＹｅｓの出力とステップＳ２０１の入力とを直結し、ステップＳ４１のＹｅｓの出力とステップＳ６９の入力とを直結すればよい。この場合には、ループ検出に初段ノード情報を用いる場合に比べ、ループ検出をするためにラベル割り当てメッセージおよびホップカウント更新メッセージがより多くのノードを経由することになる。
【０２５３】
また、ホップカウントを使用しない場合には、図２０のステップＳ４３のＹｅｓの出力とステップＳ４６の入力とを直結し、ステップＳ４０のＹｅｓの出力とステップＳ６４の入力とを直結すればよい（この結果、ステップＳ６３の処理は省かれることになる）。また、マージポイント以降の既にラベルスイッチングパスが存在する部分を転送されるメッセージはホップカウントを含まない「更新メッセージ」とすることができる。この場合には、Ｆｉｎｄ＝１かつ終段ノードでなければ常に後段ノードに対してラベル割り当てメッセージまたはホップカウント更新メッセージが送信されることになるため、ホップカウントを用いる場合に比べて送信されるメッセージの数が増加する。
【０２５４】
また、ネットワーク内の全ノードがラベルマージをサポートする場合には初段ノード情報、ホップカウント両方使用しないことも可能である。この場合のフローチャートは、ループ検出に初段ノード情報を用いない場合のフローチャートと、ホップカウントを使用しない場合のフローチャートの共通部分になる。この場合のフローチャートを図２１に示す。
【０２５５】
ラベル割り当て成功メッセージ、ラベル割り当て失敗メッセージ、ホップカウント更新成功メッセージ、ホップカウント更新失敗メッセージを受信したときのノード装置の処理手順、初段のノード装置がラベル割り当てメッセージを送信するときの処理手順等は、前述した通りである。
【０２５６】
次に、図２２に、第１の実施形態、第２の実施形態においてラベル割り当てメッセージを受信したときのノード装置の動作の一例を示す。本例は、図１６の手順において、ラベル割り当てメッセージを受信した時に常に１個のメッセージしか処理しないように修正したものである。
【０２５７】
図２２は、ホップカウントを併用するプロトコルに対応するものであり、ホップカウントを併用しない場合、図２２においてステップＳ１２を省き、ステップＳ２とＳ１０をステップＳ１３に直結すればよい。
【０２５８】
ただし、この例では、ホップカウントを使用しない場合には、ループ検出に初段ノード情報を必ず使用する。
【０２５９】
なお、図２０のような手順を持つ第２の実施形態のノード装置を常にマージしないように設定することにより、第１の実施形態のノード装置（ホップカウントを併用するもの）として使用することができる。
【０２６０】
ラベル割り当て成功メッセージ、ラベル割り当て失敗メッセージを受信したときのノード装置の処理手順、初段のノード装置がラベル割り当てメッセージを送信するときの処理手順等は、前述した通りである。
【０２６１】
次に、マージ可能な場合にラベルスイッチングパスを解放する場合のノード装置の動作について説明する。ノード装置は、ラベルスイッチングパスを解放する場合には、後段ノードに対して「ラベル解放メッセージ」を送信する。「ラベル解放メッセージ」を送信したノードは、後段ノードから「ラベル解放成功メッセージ」受信すると、該当するフローテーブルエントリを削除するものとする。
【０２６２】
図２３に、第１の実施形態、第２の実施形態においてラベル解放メッセージを受信したときのノード装置の動作の一例を示す。
【０２６３】
図２３において、Ｅｄは、受信したラベル解放メッセージに対応するフローテーブルエントリを記憶するための変数、Ｅｕは、エントリＥｄを削除した後の初段ノードからの最大のホップカウントを与えるフローテーブルのエントリを記憶するための変数、ｈｍａｘは、エントリＥｄを削除した後の初段ノードからの最大のホップカウント値を記憶する変数である。
【０２６４】
ラベル解放メッセージを受信したノード装置は、ＥｄおよびＥｕをＮＩＬに、ｈｍａｘを０に初期化し（ステップＳ１０１）、次に、フローテーブルエントリの先頭から順番にエントリを検索してゆく（ステップＳ１０２，Ｓ１０３，Ｓ１１０，Ｓ１１１）。なお、フローテーブルエントリが存在しない場合には、前段ノードにラベル解放成功メッセージを返す（ステップＳ１１６）。
【０２６５】
各フローテーブルエントリの検索では以下の処理を行なう。
【０２６６】
まず、入力側ラベルが受信メッセージ中のラベル値と等しいかどうかをチェックし（ステップＳ１０４）、等しい場合には、メッセージ中のフロー識別子および初段ノード情報がエントリ中の値と同じかどうかをチェックし（ステップＳ１１９，Ｓ１２０）、どちらか一方が同じでない場合には、前段ノードにラベル解放失敗メッセージを送信して処理を終了する（ステップＳ１２２）。フロー識別子および初段ノード情報ともにエントリ中の値と同じ場合には、Ｅｄにこのエントリを設定し（ステップＳ１２１）、次のエントリについて調べる（ステップＳ１１０，Ｓ１１１）。
【０２６７】
入力側ラベルが受信メッセージ中のラベル値と異なる場合には、メッセージ中のフロー識別子がエントリ中の値と同じかどうかをチェックし（ステップＳ１０５）、異なる場合には次のエントリについて調べる（ステップＳ１１０，Ｓ１１１）。フロー識別子が同じ場合には、メッセージ中の初段ノード情報がエントリ中の値と同じかどうかをチェックし（ステップＳ１０６）、同じ場合には前段ノードにラベル解放失敗メッセージを送信して処理を終了する（ステップＳ１２２）。初段ノード情報が異なる場合には、このノードがマージをサポートするかどうかを調べ（ステップＳ１０７）、サポートしない場合には、次のエントリについて調べる（ステップＳ１１０，Ｓ１１１）。
【０２６８】
マージをサポートする場合には、ｈｍａｘ＞このエントリ中のホップカウントならば次のエントリについて調べ（ステップＳ１０８，Ｓ１１０，Ｓ１１１）、ｈｍａｘ≦このエントリ中のホップカウントならば、Ｅｕにこのエントリを設定し、ｈｍａｘにはこのエントリ中のホップカウントを設定してから次のエントリについて調べる（ステップＳ１０８，Ｓ１０９，Ｓ１１０，Ｓ１１１）。
【０２６９】
フローテーブルエントリの検索が終了すると、前段ノードにラベル解放成功メッセージを送信する（ステップＳ１２８）。次に、ＥｄがＮＩＬなら処理を終了し（ステップＳ１１６）、そうでなければ、ＥｕがＮＩＬかどうかをチェックする（ステップＳ１１６，Ｓ１１７）。ＥｕがＮＩＬであれば、Ｅｄの確定フラグをオフにして、後段ノードにラベル解放メッセージを送信して処理を終了する（ステップＳ１２６）。ＥｕがＮＩＬでない場合には（ステップＳ１１８）、ｈｍａｘ＞Ｅｄ中のホップカウントならば処理を終了し、ｈｍａｘ≦Ｅｄ中のホップカウントならば（ステップＳ１１８）、Ｅｕの確定フラグをオフにするとともに、後段ノードにホップカウント更新メッセージを送信し（ステップＳ１１８，Ｓ１２７）、処理を終了する。
【０２７０】
ここで、送信するホップカウント更新メッセージ中のホップカウントおよび初段ノード情報には、エントリＥｕ中の値を書き込むようにする。
【０２７１】
なお、ある出力側ラベルに対するラベル解放成功メッセージ（ラベル解放失敗メッセージ）を受信したノードは、その出力側ラベルに対するフローテーブルエントリ中の確定フラグがオフである場合には、そのエントリを削除する。
【０２７２】
以上の処理により、各ノードでラベル解放後に、上流ノードの中で最大のホップカウント値を与える初段ノードが変わる場合にも更新後の初段ノード情報およびホップカウント値を正しく保持することができ、ラベルスイッチングパスの生成と解放が非同期に起こるような場合にもループの検出を行なうことができる。
【０２７３】
なお、ループ検出に初段ノード情報を用いない場合には、図２３のステップＳ１０５のＹｅｓの出力とステップＳ１０７の入力を直結し、ステップＳ１１９のＹｅｓの出力とステップＳ１２１の入力を直結すればよい。
【０２７４】
また、ホップカウントを使用しない場合には、図２３のステップＳ１０９における「Ｅｕにこのエントリを設定し、ｈｍａｘにはこのエントリ中のホップカウントを設定する」処理から「ｈｍａｘにはこのエントリ中のホップカウントを設定する」部分を省いて「Ｅｕにこのエントリを設定する」処理に修正するとともに（すなわち、「Ｅｕ：＝このエントリ、ｈｍａｘ＝このエントリ中のホップカウント」を「Ｅｕ：＝このエントリ」に変更する：この変更した処理をステップＳ１０９−１とする）、ステップＳ１０７のＹｅｓの出力とステップＳ１０９−１の入力を直結し、ステップＳ１１７のＮｏの出力とステップＳ１２７の入力を直結すればよい。この場合には、ホップカウントを用いる場合に比べて送信されるメッセージの数が増加する。
【０２７５】
なお、共通の出力側ラベルを持つようなそのフローに対する任意のフローテーブルエントリ中の初段ノード情報をホップカウント更新メッセージに書き込んで送信しループ検出する場合のラベルスイッチングパスの解放手続は、このホップカウントを使用しない場合と同様にすればよい。
【０２７６】
また、ネットワーク内の全ノードがラベルマージをサポートする場合には初段ノード情報、ホップカウント両方使用しないことも可能である。この場合のフローチャートは、ループ検出に初段ノード情報を用いない場合のフローチャートと、ホップカウントを使用しない場合のフローチャートの共通部分になる。この場合のフローチャートを図２４に示す。
【０２７７】
なお、図１８、図２０、図２２の手順に対して確定フラグを用いないような修正を施したものが、それぞれ、図１４、図１５、図１６の手順であるが、同様に、図２３の手順に対して確定フラグを用いないような修正を施すことも可能である。また、図２３においてホップカウントを使用しないようにした手順に対して確定フラグを用いないような修正を施すことも可能である。
【０２７８】
次に、以上の実施形態において、マルチキャストのラベルスイッチングパスのループ検出を行なう場合の例を示す。マルチキャストの場合には、ラベルのマージは行なわず、また、初段ノード主導でラベルスイッチングパスを設定する。パケットフォーマットは、ユニキャストの場合と同じであり、ラベルを上流側、下流側どちらのノードで割り当ててもよい。
【０２７９】
フロー識別子には、マルチキャストルーチングテーブルのエントリがマルチキャストグループアドレス毎に存在する場合には、マルチキャストグループアドレスが使用され、マルチキャストルーチングテーブルのエントリがソースアドレスとマルチキャストグループアドレスの組毎に存在する場合には、ソースアドレスとマルチキャストグループアドレスの組が使用される。
【０２８０】
確定フラグを使用しない場合のフローテーブルのフォーマットは、図１３において、出力側ラベルフィールドが、自ノードのマルチキャストの各々の出力の枝に対する１つ以上の出力側ラベルフィールドに置き換わる。
【０２８１】
また、確定フラグを使用する場合のフローテーブルのフォーマットは、図１７において、出力側ラベルフィールドが、自ノードのマルチキャストの各々の出力の枝に対する１つ以上の出力側ラベルフィールドに置き換わる。
【０２８２】
次に、マルチキャストの場合のラベルスイッチングパス生成時の動作について述べる。
【０２８３】
まず、初段ノードは、ラベルスイッチングパスの生成を起動する時に、自ノードのマルチキャストの各々の出力の枝に対してラベル割り当てメッセージを送信する。
【０２８４】
確定フラグを用いない場合には、ラベル割り当てメッセージを受信したノードは、図１６のフローチャートにしたがって、ユニキャストの場合と同様に動作する。ただし、図１６のステップＳ１６が、「自ノードのマルチキャストの各々の出力の枝に対してラベル割り当てメッセージを送信する」に書き換わる。
【０２８５】
確定フラグを用いる場合には、ラベル割り当てメッセージを受信したノードは、図２２のフローチャートにしたがって、ユニキャストの場合と同様に動作する。ただし、図２２のステップＳ２６が、「確定フラグオフ＆自ノードのマルチキャストの各々の出力の枝に対してラベル割り当てメッセージを送信する」に書き換わる。
【０２８６】
また、自ノードのマルチキャストの各々の枝の下流隣接ノードからラベル割り当て成功メッセージまたはラベル割り当て失敗メッセージを受信したノードは、以下のいずれかの動作を行なう。
（１）すべての枝の下流隣接ノードからラベル割り当て成功メッセージを受信すると、上流隣接ノードにラベル割り当て成功メッセージを返し、少なくとも１つの枝の下流隣接ノードからラベル割り当て失敗メッセージを受信すると、上流隣接ノードにラベル割り当て失敗メッセージを返す（すべての枝に対してエンド−エンドでラベルスイッチングパスが形成できるならば送信者から全てのマルチキャスト受信者までのラベルスイッチングパスを設定）。
（２）常に上流隣接ノードにラベル割り当て成功メッセージを返す（下流がどうあれ、送信者から自ノードまでのラベルスイッチングパスは設定）。
（３）少なくとも１つの枝の下流隣接ノードからラベル割り当て成功メッセージを受信すると、上流隣接ノードにラベル割り当て成功メッセージを返し、すべての枝の下流隣接ノードからラベル割り当て失敗メッセージを受信すると、上流隣接ノードにラベル割り当て失敗メッセージを返す（ある枝に対してエンド−エンドでラベルスイッチングパスが形成できるならば送信者からその受信者までのラベルスイッチングパスは設定）。
【０２８７】
次に、マルチキャストの場合のラベルスイッチングパス解放時の動作について述べる。
【０２８８】
まず、ラベルスイッチングパスの解放を起動するノードは、自ノードのマルチキャストの各々の出力の枝に対してラベル解放メッセージを送信する。
【０２８９】
ホップカウントを用いる場合には、ラベル解放メッセージを受信したノードは、図２３のフローチャートにしたがって、ユニキャストの場合と同様に動作する。ただし、図２３のステップＳ１２６が、「Ｅｄの確定フラグオフ＆自ノードのマルチキャストの各々の出力の枝に対してラベル解放メッセージを送信する」に書き換わる。また、この場合には、ステップＳ１１７でＮｏ分岐に入ることはない。
【０２９０】
ホップカウントを用いない場合には、ラベル解放メッセージを受信したノードは、図２４のフローチャートにしたがって、ユニキャストの場合と同様に動作する。ただし、図２４のステップＳ１２６が、「Ｅｄの確定フラグオフ＆自ノードのマルチキャストの各々の出力の枝に対してラベル解放メッセージを送信する」に書き換わる。また、この場合には、ステップＳ１１７でＮｏ分岐に入ることはない。
【０２９１】
また、自ノードのマルチキャストのすべての枝の下流隣接ノードからラベル解放成功メッセージを受信したノードは、フローテーブルエントリを削除する。
【０２９２】
以上の実施形態では、ラベル割り当てメッセージが初段ノードから後段ノードの方向に送信され、ラベル割り当て成功／失敗メッセージが終段ノードから前段ノードの方向に送信される場合（Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）を示したが、本発明は、ラベル割り当てメッセージが終段ノードから前段ノードの方向に送信され、ラベル割り当て成功／失敗メッセージが初段ノードから後段ノードの方向に送信される場合（Ｅｇｒｅｓｓ  Ｃｏｎｔｒｏｌ）にも、適用可能である。
【０２９３】
なお、Ｉｎｇｒｅｓｓ  Ｃｏｎｔｒｏｌ方式の第１、第２の実施形態等で、ループ検出のための更新メッセージをパスの向きと逆方向に流してもループ検出は可能である。
【０２９４】
この場合には、ラベル割り当てメッセージ受信を契機として更新メッセージを送信することになっているノードは、下流側隣接ノードに更新メッセージを送信する代わりに、ラベル割り当てメッセージを送信したノードに対して「照会メッセージ」を送信するとともに、確定フラグをオフにする。
【０２９５】
照会メッセージを受信したノードは、入力側ラベルが存在する上流側隣接ノードのそれぞれに更新メッセージを送信し、確定フラグをオフにする。更新メッセージは、入力側ラベルが存在する上流隣接ノードに次々にフォワードされ、確定フラグがオフであるノードが更新メッセージを受信した場合には、ループであると判断し、更新失敗メッセージを返す。そうでなく、初段ノードが更新メッセージを受信したときに確定フラグがオンである場合には、更新成功メッセージを返す。少なくとも一つの上流隣接ノードから更新失敗メッセージを受信した場合には、下流隣接ノードに更新失敗メッセージを返し、そうでない場合には、更新成功メッセージを返す。いずれの場合も確定フラグをオンにする。
【０２９６】
更新メッセージを最初に送信したノードが更新失敗メッセージを受信すると、照会失敗メッセージを下流隣接ノードに送信し、更新成功メッセージを受信すると照会成功メッセージを下流隣接ノードに送信する。いずれの場合も確定フラグをオンにする。照会成功メッセージを受信したノードは、ラベルスイッチングが可能となり、照会失敗メッセージを受信したノードは、入力側ラベルを削除する。いずれの場合にも確定フラグをオンにする。
【０２９７】
例えば、図５において、ノード装置Ｒ５がノード装置Ｒ２にラベル割り当てメッセージを送信した場合には、ノード装置Ｒ２は、ノード装置Ｒ５に照会メッセージを送信し、確定フラグをオフにする。ノード装置Ｒ５は、ノード装置Ｒ２から照会メッセージを受信すると、ノード装置Ｒ４に更新メッセージを送信し、確定フラグをオフにする。更新メッセージは、ノード装置Ｒ４からノード装置Ｒ３、ノード装置Ｒ３からノード装置Ｒ２とＲ８、ノード装置Ｒ８からノード装置Ｒ７、ノード装置Ｒ７からノード装置Ｒ６へとフォワードされる。ノード装置Ｒ２が更新メッセージを受信すると、確定フラグがすでにオフであるため、ループであると判断し、更新失敗メッセージをノード装置Ｒ３に返す。ノード装置Ｒ６は、更新成功メッセージを送信し、これはノード装置Ｒ３までフォワードされる。ノード装置Ｒ３は、ノード装置Ｒ４に対して更新失敗メッセージを送信し、これはノード装置Ｒ５までフォワードされる。ノード装置Ｒ５は、更新失敗メッセージを受信すると、ノード装置Ｒ２に照会失敗メッセージを返し、ノード装置Ｒ２とノード装置Ｒ５との間ではラベルスイッチングは行なわれない。
【０２９８】
照会メッセージ、照会成功メッセージは図１１で示した例と同じで、照会失敗メッセージは、図１２で示した例と同じである。ただし、これらのメッセージにはラベルの値を指定する。
【０２９９】
なお、これまでの説明では、一旦、ラベルが割り当てられたパスに対しては、ラベル割り当てメッセージは送信しないようなハードステート型のプロトコルを前提にしていたが、本発明は、いったんラベルが割り当てられたパスに対しても、定期的にラベル割り当てメッセージを送信するようなソフトステート型のプロトコルに関しても有効である。ソフトステート型の場合には、一定期間ラベル割り当てメッセージを受信しない場合にはラベルが解放される。
【０３００】
さて、これまでは、初段ノード主導でラベルスイッチングパスを生成する場合のループ検出方法について説明してきたが、次に、終段ノード主導でラベルスイッチングパスを設定する場合のループ検出方法について説明する。
【０３０１】
終段ノード主導でラベルスイッチングパスを設定する方法は、基本的に、文献「Ｎ．Ｆｅｌｄｍａｎ  ａｎｄ  Ａ．Ｖｉｓｗａｎａｔｈａｎ，“ＡＲＩＳ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ”，Ｉｎｔｅｒｎｅｔ  Ｄｒａｆｔ  （ｗｏｒｋ  ｉｎ  ｐｒｏｇｒｅｓｓ），ｄｒａｆｔ−ｆｅｌｄｍａｎ−ａｒｉｓ−ｓｐｅｃ−００．ｔｘｔ，Ｍａｒ．，１９９７」にある方法を使用するが、ループ検出の方法が上記文献とは異なり、パス上のノードのリストであるパスベクトルを使用しないため、パスベクトルを使用する場合に比べ、メッセージ長を短くできる。
【０３０２】
以下の説明において、ノード装置に関連する基本的な事項は、例えば、ノード装置がＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）処理を行なう機能を持つとともに本実施形態に係るラベル割り当てプロトコルに従ってラベルスイッチングを行なう機能を持つ点、初段ノード情報、フローＩＤ、リンクＩＤ、インタフェースＩＤ、入力側ラベル、出力側ラベルなどの語句もしくはその定義に関する点などについては、第１の実施形態や第２の実施形態などで説明したものと基本的には同様である。
【０３０３】
なお、ノード装置がラベル割当てメッセージを終段として送信する契機には、例えば、次のような形態がある。
（１）終段として登録された各々のノード装置が起動した時を契機に、ラベル割当てメッセージを送信する。
（２）終段として登録された各々のノード装置においてフロー（終段として登録されたノードを通過するパケット流）の通過トラヒック量がしきい値を越えた場合を契機に、ラベル割当てメッセージを送信する。
（３）フロー（終段として登録されたノードを通過するパケット流）に対するトラヒック量がしきい値を越え、かつ、フローの次ホップノードが本実施形態に係るラベル割り当てプロトコルをサポートしない、という条件を満たすノードのみが、これを契機に自ノードを終段と判断してラベル割当てメッセージを送信する。
【０３０４】
終段として登録されるノードの一例として、ＯＳＰＦのエリアボーダールータやドメイン境界ルータ、隣接ＢＧＰルータなどがある。
【０３０５】
なお、上記の（３）の場合には、終段として登録されたノードと実際のラベルスイッチングパスの終段となるノードは異なる。
【０３０６】
さて、ラベルスイッチングパスを終段ノード主導で生成する場合（Ｅｇｒｅｓｓ  ｃｏｎｔｒｏｌ）には、終段ノードから、すべての上流隣接ノードに対してラベル割り当てのための手順を起動し、終段以外の各ノードはフローの次ホップノードからラベル割り当てのための手順が起動されると、さらに上流隣接ノード（次ホップ以外の隣接ノード）に対してラベル割り当てのための手順を起動する。最終的に初段ノードでラベル割り当てのための手順が起動されると、初段ノードから終段ノードまでのラベルスイッチングパスができる。これを初期生成手順と呼ぶ。このとき、ラベルスイッチングパスは、初段ノードを葉、終段ノードを根とするツリー状になる。
【０３０７】
なお、初期生成手順中にラベル割り当てのための手順を実行中のノードで経路変更が起こらない場合には、パスの出口から順にパスを作ってゆくため、上記手順によりループができないことが保証される（パスの出口の存在が保証されるため）。
【０３０８】
ただし、経路変更などにより、存在する出力側のラベル割り当てを解放して、新たな次ホップノードとの間でラベル割り当てを行う場合、すなわち、入力側のラベルが存在する場合に新たに出力側のラベルを割り当てる場合には、もし、新たな次ホップノードの下流に自ノードが位置する場合にはループができてしまうため、新たな次ホップノードとの間でラベル割り当てを行う前に、その次ホップノードの下流に自ノードが位置しないことを確認する必要がある。
【０３０９】
このため、あるノードで入力側のラベルが存在する場合に出力側ラベルを新たに割り当てる場合には、確定フラグをオフにしながらループ検出のためのメッセージを下流ノードに流し、確定フラグがオフである場合にこのメッセージを上流ノードから受信した場合にはループがあると判断される。そうでなく、このメッセージが終段ノードまで到達すると、ループがないと判断される。初段ノード情報と、初段ノードからのホップカウントをループ検出に用いる場合には、ループ検出のためのメッセージが、ループ上を１周する前にループ検出することが可能である。
【０３１０】
ループ検出のためのメッセージには、更新メッセージが使用される。更新メッセージはループ検出のためだけではなく、パスの状態が変わったことを下流ノードに通知するためにも使用される。
【０３１１】
本実施形態では、ホップカウントとして、終段ノードからのホップ数を用いる場合を示すが、ホップカウントは省略可能である。ここでの例は、すべてあるＦｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］（Ｒ１を終段ノードとするパケットストリーム）のフローに関する動作であるとする。
【０３１２】
なお、本実施形態では、フローを識別するために使うノードのアドレス（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］という表記におけるＲ１）と、実際のラベルスイッチングパスの終段となっているノードは一致するが、一般にフローを識別するために使うノードのアドレス、実際のラベルスイッチングパスの終段ノードは一致していなくてもよい。例えば、図２５において、ノードＲ１の次ホップノードとして、終段として登録されたノードＲ０が存在してもよく、このとき、Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ０］となるが、実際のラベルスイッチングパスの終段ノードはＲ１になる。
【０３１３】
以下、終段ノード主導でラベルスイッチングパスを設定する場合のいくつかの例について説明する。
【０３１４】
（第４の実施形態）
最初に、初段ノード情報を使わない方法について説明する。簡単のために、すべてのノードはラベルのマージが可能であるとする。ラベルのマージを行なわない場合については後述する。また、各ノードは下流側主導のラベル割り当て（Ｄｏｗｎｓｔｒｅａｍラベル割り当て）を行なうものとするが、上流側主導のラベル割り当て（Ｕｐｓｔｒｅａｍラベル割り当て）も可能である。
【０３１５】
まず、すべてのノードは確定フラグをオンに初期化する。
【０３１６】
終段ノードは、ホップカウント＝１が指定されたラベル割り当てメッセージをフローのすべての上流隣接ノード（次ホップ以外の隣接ノード）に送信する。
【０３１７】
終段以外のノードは、そのフローに対する出力側ラベルが設定されると、終段ノードからのホップカウントを１だけインクリメントした値をホップカウントに指定したラベル割り当てメッセージをフローのすべての上流隣接ノード（次ホップ以外の隣接ノード）に送信する。入力側ラベルが存在しない上流隣接ノードに対しては、ラベル割り当てメッセージが定期的に送信される。
【０３１８】
ラベル割り当てメッセージを受信したノード（Ｕとする）は、メッセージの送信ノード（Ｄとする）がそのフローに対する次ホップノードでない、または、受信ホップカウントがしきい値を越える、または、確定フラグがオフである、または、終段ノードであれば、ラベル割り当て失敗メッセージを返す。そうでなく、もし、入力側ラベルが存在するのに出力側ラベルが存在しないならば、確定フラグをオフにして、「照会メッセージ」をノードＤに送信する。そうでなければ、ノードＤにラベル割り当て成功メッセージを送信する。このとき、出力側ラベルが存在しなければ、出力側ラベルの割り当てを行ない、メッセージ中のホップカウントを終段ノードからのホップカウントとして記憶する。
【０３１９】
上流隣接ノードからラベル割り当て成功メッセージを受信したノードは、終段ノードでなければ、以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングが可能となる。
【０３２０】
ラベル割り当て失敗メッセージを受信したノードは、入力側ラベルの登録をやめる。
【０３２１】
パス上のノード（Ｕとする）で経路変更、または経路の削除が起こった場合には、ノードＵは、古い経路の次ホップノード（Ｄｏｌｄとする）に対して、ラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０３２２】
ラベル解放メッセージを受信したノードＤｏｌｄは、ノードＵに対してラベル解放成功メッセージを送信し、ラベルを解放する。
【０３２３】
ラベル解放成功メッセージを受信したノードＵは、確定フラグをオンにし、新しい経路に対する次ホップノードＤｎｅｗが存在すれば、ノードＤｎｅｗに対し、ラベル割り当てトリガメッセージを送信する。ラベル割り当てトリガメッセージは、ノードＤｎｅｗからラベル割り当てメッセージを受信するまで定期的に再送される。
【０３２４】
ラベル割り当てトリガメッセージを受信したノードＤｎｅｗは、確定フラグがオンであり、かつ、自身が終段ノードであるかまたは出力側ラベルが存在するならば、ノードＵに対して終段ノードから自ノードまでのホップカウントを１だけインクリメントした値をホップカウントに指定したラベル割り当てメッセージを返す。
【０３２５】
ノードＵから照会メッセージを受信したノードＤは、確定フラグがオフであれば、ノードＵに照会失敗メッセージを返し、入力側ラベルの登録を行なわない。そうでなく、もし、出力側ラベルが存在すれば、下流隣接ノードに更新メッセージを送信し、確定フラグをオフにする。そうでなければ、ノードＵに照会成功メッセージを送信する。
【０３２６】
上流隣接ノードから更新メッセージを受信したノードは、確定フラグがオフであれば、更新失敗メッセージを返す。そうでなく、もし、出力側ラベルが存在すれば、下流隣接ノードに更新メッセージを送信し、確定フラグをオフにする。そうでなければ、更新成功メッセージを返す。
【０３２７】
下流隣接ノードから更新成功メッセージを受信したノードは、確定フラグをオンにし、更新メッセージを送信した上流隣接ノードに対しては、更新成功メッセージを返し、照会メッセージを送信した上流隣接ノードに対しては、照会成功メッセージを送信する。
【０３２８】
下流隣接ノードから更新失敗メッセージを受信したノードは、確定フラグをオンにし、更新メッセージを送信した上流隣接ノードに対しては、更新失敗メッセージを返し、照会メッセージを送信した上流隣接ノードに対しては、照会失敗メッセージを送信する。
【０３２９】
ノードＤから照会成功メッセージを受信したノードＵは、出力側ラベルを登録し、確定フラグをオンにする。以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングが可能となる。
【０３３０】
ノードＤから照会失敗メッセージを受信したノードＵは、確定フラグをオンにする。以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングは行なわれない。
【０３３１】
次に、図２５を参照しながら、ラベルスイッチングパス生成時の動作例を説明する。図２５において、Ｒ１は終段ノードとする。また、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６の次ホップノードは、それぞれ、Ｒ１、Ｒ２、Ｒ３、Ｒ２、Ｒ２とする。
【０３３２】
ノード装置Ｒ１は、ノード装置Ｒ２に対して（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ａ、Ｈｏｐｃｏｕｎｔ＝１）のラベル割り当てメッセージｍ１を送信する。
【０３３３】
ノード装置Ｒ２は、ノード装置Ｒ１からラベル割り当てメッセージｍ１を受信すると、ノード装置Ｒ１はこのフローの次ホップノードであり、確定フラグはオンであるため、Ｌａｂｅｌ＝ａを記憶し、ノード装置Ｒ１にラベル割り当て成功メッセージを返す。次に、ノード装置Ｒ２は、次ホップノード以外の隣接ノードであるノード装置Ｒ５、Ｒ３、Ｒ６に対して、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｂ、Ｈｏｐｃｏｕｎｔ＝２）、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｃ、Ｈｏｐｃｏｕｎｔ＝２）、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｄ、Ｈｏｐｃｏｕｎｔ＝２）のラベル割り当てメッセージｍ２、ｍ３、ｍ４をそれぞれ送信する。
【０３３４】
ノード装置Ｒ５は、ノード装置Ｒ２からラベル割り当てメッセージｍ２を受信すると、ノード装置Ｒ２はこのフローの次ホップノードであり、確定フラグはオンであるため、Ｌａｂｅｌ＝ｂを記憶し、ノード装置Ｒ２にラベル割り当て成功メッセージを送信する。次に、ノード装置Ｒ５は、次ホップノード以外の隣接ノードＲ４に対して、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｇ、Ｈｏｐｃｏｕｎｔ＝３）のラベル割り当てメッセージｍ７を送信する。
【０３３５】
ノード装置Ｒ３は、ノード装置Ｒ２からラベル割り当てメッセージｍ３を受信すると、ノード装置Ｒ２はこのフローの次ホップノードであり、確定フラグはオンであるため、Ｌａｂｅｌ＝ｃを記憶し、ノード装置Ｒ２にラベル割り当て成功メッセージを送信する。次に、ノード装置Ｒ３は、次ホップノード以外の隣接ノードＲ４に対して、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｅ、Ｈｏｐｃｏｕｎｔ＝３）のラベル割り当てメッセージｍ５を送信する。
【０３３６】
ノード装置Ｒ６は、ノード装置Ｒ２からラベル割り当てメッセージｍ４を受信すると、ノード装置Ｒ２はこのフローの次ホップノードであり、確定フラグはオンであるため、Ｌａｂｅｌ＝ｄを記憶し、ノード装置Ｒ２にラベル割り当て成功メッセージを送信する。
【０３３７】
ノード装置Ｒ４は、ノード装置Ｒ３からラベル割り当てメッセージｍ５を受信すると、ノード装置Ｒ３はこのフローの次ホップノードであり、確定フラグはオンであるため、Ｌａｂｅｌ＝ｅを記憶し、ノード装置Ｒ３にラベル割り当て成功メッセージを送信する。次に、ノード装置Ｒ４は、次ホップノード以外の隣接ノードＲ５に対して、（Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］、Ｌａｂｅｌ＝ｆ、Ｈｏｐｃｏｕｎｔ＝４）のラベル割り当てメッセージｍ６を送信する。
【０３３８】
ノード装置Ｒ４は、ノード装置Ｒ５からラベル割り当てメッセージｍ７を受信すると、ノード装置Ｒ５はこのフローの次ホップノードでないため、ノード装置Ｒ５に対してラベル割り当て失敗メッセージを返す。
【０３３９】
ノード装置Ｒ５は、ノード装置Ｒ４からラベル割り当てメッセージｍ６を受信すると、ノード装置Ｒ４はこのフローの次ホップノードでないため、ノード装置Ｒ４に対してラベル割り当て失敗メッセージを返す。
【０３４０】
ノード装置Ｒ３は、ノード装置Ｒ４からラベル割り当て成功メッセージを受信すると、入力側ラベルＬａｂｅｌ＝ｅを登録し、以降、入力側ラベルＬａｂｅｌ＝ｅと出力側ラベルＬａｂｅｌ＝ｃの間のスイッチングが可能になる。
【０３４１】
ノード装置Ｒ２は、ノード装置Ｒ５、Ｒ３、およびＲ６からラベル割り当て成功メッセージを受信すると、それぞれ、入力側ラベルＬａｂｅｌ＝ｂ，Ｌａｂｅｌ＝ｃ，Ｌａｂｅｌ＝ｄを登録し、以降、これらの入力側ラベルと出力側ラベルＬａｂｅｌ＝ａの間のスイッチングが可能になる。
【０３４２】
ノード装置Ｒ１は、ノード装置Ｒ２からラベル割り当て成功メッセージを受信すると、入力側ラベルＬａｂｅｌ＝ａを登録する。
【０３４３】
この結果、図２６のようなマージされたラベルスイッチングパスができる。
【０３４４】
次に、経路変更時の動作例を示す。図２６において、ノードＲ５において、経路変更が起こり、Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］に対する次ホップノードがＲ２からＲ４に変わったとする。
【０３４５】
このとき、経路変更に伴って図２７に示すようなパケットのやりとりが行なわれる。図２７において、ＲＥＬはラベル解放メッセージ、ＲＥＬ＿ＡＣＫはラベル解放成功メッセージ、ＴＲＧはラベル割り当てトリガメッセージ、ＳＥＴＵＰはラベル割り当てメッセージ、ＳＥＴＵＰ＿ＡＣＫはラベル割り当て成功メッセージである。
【０３４６】
まず、ノード装置Ｒ５は、経路変更前の次ホップノードＲ２に対してラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０３４７】
ノード装置Ｒ２は、ノード装置Ｒ５からラベル解放メッセージを受信すると、ノード装置Ｒ５との間のラベル割り当てを解放し、ラベル解放成功メッセージをノード装置Ｒ５に返す。
【０３４８】
ノード装置Ｒ５は、ノード装置Ｒ２からラベル解放成功メッセージを受信すると、確定フラグをオンにし、新しい経路上の次ホップノードＲ４に対してラベル割り当てトリガメッセージを送信する。
【０３４９】
ノード装置Ｒ４は、ノード装置Ｒ５からラベル割り当てトリガメッセージを受信すると、ノード装置Ｒ５に対し、ラベル割り当てメッセージを返す。
【０３５０】
ノード装置Ｒ５は、ノード装置Ｒ４からラベル割り当てメッセージを受信すると、ノード装置Ｒ４はこのフローの次ホップノードであり、受信ホップカウントがしきい値を越えず、確定フラグがオンであり、かつ、終段ノードでなく、かつ、入力側ラベルが存在しないため、ノード装置Ｒ４との間に出力側ラベルを割り当て、ノード装置Ｒ４にラベル割り当て成功メッセージを送信する。
【０３５１】
ノード装置Ｒ４は、ノード装置Ｒ５からラベル割り当て成功メッセージを受信すると、ラベル割り当て成功メッセージの応答待ちの状態を解除し、確定フラグをオンにする。以降、ノード装置Ｒ４ではラベルスイッチングが可能となる。
【０３５２】
この結果、図２８のようなラベルスイッチングパスができる。
【０３５３】
次に、図２８の状態から、さらに経路変更が起こり、ノードＲ２の次ホップノードがＲ１からＲ５に変わったとする。このとき、Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］に対しては、Ｒ２→Ｒ５→Ｒ４→Ｒ３→Ｒ２というループした経路となっている。
【０３５４】
このとき、経路変更に伴って図２９に示すようなパケットのやりとりが行なわれる。図２９において、ＲＥＬはラベル解放メッセージ、ＲＥＬ＿ＡＣＫはラベル解放成功メッセージ、ＴＲＧはラベル割り当てトリガメッセージ、ＳＥＴＵＰはラベル割り当てメッセージ、ＱＲＹは照会メッセージ、ＵＰＤ＿ＮＡＣＫは更新失敗メッセージ、ＱＲＹ＿ＮＡＣＫは照会成功メッセージである。
【０３５５】
まず、ノード装置Ｒ２は、経路変更前の次ホップノードＲ１に対してラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０３５６】
ノード装置Ｒ１は、ノード装置Ｒ２からラベル解放メッセージを受信すると、ノード装置Ｒ２との間のラベル割り当てを解放し、ラベル解放成功メッセージをノード装置Ｒ２に返す。
【０３５７】
ノード装置Ｒ２は、ノード装置Ｒ１からラベル解放成功メッセージを受信すると、確定フラグをオンにし、新しい経路上の次ホップノードＲ５に対してラベル割り当てトリガメッセージを送信する。
【０３５８】
ノード装置Ｒ５は、ノード装置Ｒ２からラベル割り当てトリガメッセージを受信すると、ノード装置Ｒ２に対し、ラベル割り当てメッセージを返す。
【０３５９】
ノード装置Ｒ２は、ノード装置Ｒ５からラベル割り当てメッセージを受信すると、ノード装置Ｒ５はこのフローに対する次ホップノードであり、受信ホップカウントがしきい値を越えず、確定フラグがオンであり、かつ、終段ノードでないが、入力側ラベルが存在するのに出力側ラベルが存在しないため、ノード装置Ｒ５に照会メッセージを送信し、確定フラグをオフにする。
【０３６０】
ノード装置Ｒ２から照会メッセージを受信したノード装置Ｒ５は、確定フラグをオフにし、出力側ラベルが存在する隣接ノードＲ４に更新メッセージを送信する。
【０３６１】
ノード装置Ｒ５から更新メッセージを受信したノード装置Ｒ４は、確定フラグをオフにし、出力側ラベルが存在する隣接ノードＲ３に更新メッセージを送信する。
【０３６２】
ノード装置Ｒ４から更新メッセージを受信したノード装置Ｒ３は、ノード装置Ｒ２に更新メッセージを送信する。
【０３６３】
ノード装置Ｒ３から更新メッセージを受信したノード装置Ｒ２は、確定フラグがオフであるため、ノード装置Ｒ３に更新失敗メッセージを返す。
【０３６４】
ノード装置Ｒ２から更新失敗メッセージを受信したノード装置Ｒ３は、ノード装置Ｒ４に更新失敗メッセージを返し、確定フラグをオンにする。
【０３６５】
ノード装置Ｒ３から更新失敗メッセージを受信したノード装置Ｒ４は、ノード装置Ｒ５に更新失敗メッセージを返し、確定フラグをオンにする。
【０３６６】
ノード装置Ｒ４から更新失敗メッセージを受信したノード装置Ｒ５は、ノード装置Ｒ２に照会失敗メッセージを返し、確定フラグをオンにする。
【０３６７】
ノード装置Ｒ５から照会失敗メッセージを受信したノード装置Ｒ２は、ノード装置Ｒ５にラベル割り当て失敗メッセージを返すとともに、確定フラグをオンにする。
【０３６８】
ノード装置Ｒ２からラベル割り当て失敗メッセージを受信したノード装置Ｒ５は、ノード装置Ｒ２との間の入力側ラベルを解放する。
【０３６９】
この結果、経路がループしているにもかかわらず、図３０のようなループのないラベルスイッチングパスができる。
【０３７０】
次に、図３１に、ラベル割り当てメッセージを受信したノードの処理手順を表したフローチャートを示す。
【０３７１】
受信メッセージ中のフロー識別子をＦとする（ステップＳ３０１）。
【０３７２】
まず、Ｆで識別されるパケットフローの次ホップノードがラベル割り当てメッセージの送信ノードと異なるか、受信ホップカウントがしきい値を越えているか、自身が終段ノードであれば、ラベル割り当てメッセージの送信ノードにラベル割り当て失敗メッセージを返す（ステップＳ３０２，Ｓ３０３，Ｓ３０４，Ｓ３０５）。
【０３７３】
そうでなく、もし、フロー識別子＝Ｆで、かつ、出力側ラベルが割り当てられているようなフローテーブルエントリが存在する場合には、確定フラグがオフであれば、ラベル割り当てメッセージの送信ノードにラベル割り当て失敗メッセージを返し（ステップＳ３０６，Ｓ３０７，Ｓ３０５）、オンであれば、ラベル割り当てメッセージの送信ノードにラベル割り当て成功メッセージを返す（ステップＳ３０６，Ｓ３０７，Ｓ３０９）。
【０３７４】
そうでなく、もし、フロー識別子＝Ｆで、かつ、入力側ラベルが割り当てられているようなフローテーブルエントリが存在する場合には、フロー識別子＝Ｆで、かつ、入力側ラベルが割り当てられているようなフローテーブルエントリのそれぞれに対し、出力側ラベルを割り当て、照会メッセージを送信し、確定フラグをオフにする（ステップＳ３０６，Ｓ３０８，Ｓ３１０）。もし、フロー識別子＝Ｆで、かつ、入力側ラベルが割り当てられているようなフローテーブルエントリが存在するものでない場合には、ラベル割り当てメッセージの送信ノードにラベル割り当て成功メッセージを返す（ステップＳ３０６，Ｓ３０８，Ｓ３０９）。
【０３７５】
（第５の実施形態）
次に、Ｅｇｒｅｓｓ  Ｃｏｎｔｒｏｌの場合に、確定フラグに加え、初段ノード情報と初段ノードからのホップカウントを用いてループ検出する場合の例を示す。
【０３７６】
まず、すべてのノードは確定フラグをオンに初期化する。
【０３７７】
終段ノードは、ホップカウント＝１が指定されたラベル割り当てメッセージをフローのすべての上流隣接ノード（次ホップ以外の隣接ノード）に送信する。
【０３７８】
終段以外のノードは、そのフローに対する出力側ラベルが設定されると、終段ノードからのホップカウントを１だけインクリメントした値をホップカウントに指定したラベル割り当てメッセージをフローのすべての上流隣接ノード（次ホップ以外の隣接ノード）に送信する。入力側ラベルが存在しない上流隣接ノードに対しては、ラベル割り当てメッセージが定期的に送信される。
【０３７９】
ラベル割り当てメッセージを受信したノード（Ｕとする）は、メッセージの送信ノード（Ｄとする）がそのフローに対する次ホップノードでない、または、受信ホップカウントがしきい値を越える、または、確定フラグがオフである、または、終段ノードであれば、ラベル割り当て失敗メッセージを返す。そうでなく、もし、入力側ラベルが存在するのに出力側ラベルが存在しないならば、確定フラグをオフにして、ノードＵが持つ初段ノード情報、初段ノードからのホップカウントを１だけインクリメントしたホップカウントを含む「照会メッセージ」をノードＤに対して送信する。そうでなければ、ノードＤにラベル割り当て成功メッセージ送信する。このとき、出力側ラベルが存在しなければ、出力側ラベルの割り当てを行ない、メッセージ中のホップカウントを終段ノードからのホップカウントとして記憶する。ただし、初段ノードがラベル割り当て成功メッセージを送信する場合には、自ノードのルータＩＤまたは出力インタフェースのネットワークアドレスを初段ノードアドレス、新たに割り当てた初段ノードローカルＩＤを初段ノードとし、ホップカウント＝１を指定する（初段ノード情報の発信）。初段ノードでない場合には、どちらも指定しない。
【０３８０】
上流隣接ノードからラベル割り当て成功メッセージを受信したノードは、終段ノードでなければ、以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングが可能となる。受信メッセージに初段ノード情報とホップカウントが指定されていれば、それらを入力側ラベルと対応付けるとともに、もし、受信したホップカウントが現在の全入力側ラベルに対応するホップカウントよりも大きく、かつ、自身が終段ノードでなければ、次ホップノードに受信した初段ノード情報、および受信ホップカウントを１だけインクリメントしたホップカウントを含む更新メッセージを送信し、確定フラグをオフにする（初段ノード情報のフォワード）。
【０３８１】
ラベル割り当て失敗メッセージを受信したノードは、入力側ラベルの登録をやめる。
【０３８２】
パス上のノード（Ｕとする）で経路変更、または経路の削除が起こった場合には、ノードＵは、古い経路の次ホップノード（Ｄｏｌｄとする）に対して、ラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０３８３】
ラベル解放メッセージを受信したノードＤｏｌｄは、確定フラグがオフであれば、ラベル解放失敗メッセージを返す。確定フラグがオンであれば、ノードＵに対してラベル解放成功メッセージを送信し、ラベルを解放する。さらに、ラベル解放後、最大のホップカウントを持つ初段ノードが変わった場合には、確定フラグをオフにするとともに、変更後の（初段ノード情報、ホップカウント）を指定した更新メッセージを下流ノードに送信する。
【０３８４】
ラベル解放成功メッセージを受信したノードＵは、確定フラグをオンにし、新しい経路上の下流ノードＤｎｅｗが存在すれば、ノードＤｎｅｗにラベル割り当てトリガメッセージを送信する。ラベル割り当てトリガメッセージは、ノードＤｎｅｗからラベル割り当てメッセージを受信するまで定期的に再送される。
【０３８５】
ラベル割り当てトリガメッセージを受信したノードＤｎｅｗは、確定フラグがオンであり、かつ、自身が終段ノードであるかまたは出力側ラベルが存在するならば、ノードＵに対して終段ノードから自ノードまでのホップカウントを１だけインクリメントした値をホップカウントに指定したラベル割り当てメッセージを返す。
【０３８６】
ノードＵから照会メッセージを受信したノードＤは、受信した初段ノード情報がすでに他の入力側ラベルと対応しているか、または、ノードＤが受信した初段ノード情報に関する初段ノードであるか、または、まだ初段ノード情報が設定されていない入力側ラベルが存在するか、または、確定フラグがオフであれば、ノードＵに照会失敗メッセージを返し、入力側ラベルの登録を行なわない。そうでなく、もし、受信したホップカウントが現在の全入力側ラベルに対応するホップカウントよりも大きく、かつ、終段ノードでなければ、下流隣接ノードに受信した初段ノード情報、および受信ホップカウントを１だけインクリメントしたホップカウントを含む更新メッセージを送信し、確定フラグをオフにする。そうでなければ、ノードＵに照会成功メッセージを送信する。
【０３８７】
上流隣接ノードから更新メッセージを受信したノードは、受信した初段ノード情報がすでに他の入力側ラベルと対応しているか、または、まだ初段ノード情報が設定されていない入力側ラベルが存在するか、または、確定フラグがオフであれば、更新失敗メッセージを返す。そうでなく、もし、受信したホップカウントが現在の全入力側ラベルに対応するホップカウントよりも大きく、かつ、終段ノードでなければ、下流隣接ノードに受信した初段ノード情報、および受信ホップカウントを１だけインクリメントしたホップカウントを含む更新メッセージを送信し、確定フラグをオフにする。そうでなければ、更新成功メッセージを返し、初段ノード情報、およびホップカウントの更新を行なう。
【０３８８】
下流隣接ノードから更新成功メッセージを受信したノードは、確定フラグをオンにし、初段ノード情報、およびホップカウントの更新を確定する。次に、更新メッセージの応答待ちの上流隣接ノードがあれば更新成功メッセージを返し、照会メッセージを送信した上流隣接ノードがあれば照会成功メッセージを返す。
【０３８９】
下流隣接ノードから更新失敗メッセージを受信したノードは、確定フラグをオンにし、初段ノード情報、およびホップカウントの更新をやめる。次に、更新メッセージの応答待ちの上流隣接ノードがあれば更新失敗メッセージを返し、照会メッセージを送信した上流隣接ノードがあれば照会失メッセージを返す。
【０３９０】
ノードＤから照会成功メッセージを受信したノードＵは、出力側ラベルを登録し、確定フラグをオンにする。以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングが可能となる。
【０３９１】
ノードＤから照会失敗メッセージを受信したノードＵは、確定フラグをオンにする。以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングは行なわれない。
【０３９２】
次に、ラベルスイッチングパス生成時の動作例を示す。ここでは、初段ノード情報として、ノードのルータＩＤを使用するものとする。
【０３９３】
図３２において、Ｒ１は終段ノードとする。また、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６、Ｒ７、Ｒ８の次ホップノードは、それぞれ、Ｒ１、Ｒ２、Ｒ３、Ｒ２、Ｒ３、Ｒ６、Ｒ７とする。図３２は、まず、Ｅｇｒｅｓｓ  Ｃｏｎｔｒｏｌの第４の実施形態と同様の初期生成手順を経た後のパスの状態を表す。
【０３９４】
なお、初段ノードＲ５、Ｒ４、Ｒ８は、初段ノード情報とホップカウントをラベル割り当て成功メッセージに指定し、各ノードでは、上流隣接ノードから受信したラベル割り当て成功メッセージの中で最大のホップカウントを与える初段ノード情報とそれに対するホップカウントを１だけインクリメントしたホップカウントを指定したラベル割り当て成功メッセージを下流隣接ノードにフォワードする。この結果、Ｒ５、Ｒ４、Ｒ８、Ｒ７、Ｒ６、Ｒ３、Ｒ２が下流隣接ノードに通知する（初段ノード情報、ホップカウント）は、それぞれ、（Ｒ５，１）、（Ｒ４，１）、（Ｒ８，１）、（Ｒ８，２）、（Ｒ８，３）、（Ｒ８，４）、（Ｒ８，５）となる。
【０３９５】
次に、経路変更時の動作例を示す。図３２において、ノードＲ５において、経路変更が起こり、Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］に対する次ホップノードがＲ２からＲ４に変わったとする。
【０３９６】
このとき、経路変更に伴って図３３に示すようなパケットのやりとりが行なわれる。図３３において、ＲＥＬはラベル解放メッセージ、ＲＥＬ＿ＡＣＫはラベル解放成功メッセージ、ＴＲＧはラベル割り当てトリガメッセージ、ＳＥＴＵＰはラベル割り当てメッセージ、ＵＰＤは更新メッセージ、ＵＰＤ＿ＡＣＫは更新成功メッセージ、ＳＥＴＵＰ＿ＡＣＫはラベル割り当て成功メッセージである。
【０３９７】
まず、ノード装置Ｒ５は、経路変更前の次ホップノードＲ２に対してラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０３９８】
ノード装置Ｒ２は、ノード装置Ｒ５からラベル解放メッセージを受信すると、ノード装置Ｒ５との間のラベル割り当てを解放し、ラベル解放成功メッセージをノード装置Ｒ５に返す。
【０３９９】
ノード装置Ｒ５は、ノード装置Ｒ２からラベル解放成功メッセージを受信すると、確定フラグをオンにし、新しい経路上の次ホップノードＲ４に対してラベル割り当てトリガメッセージを送信する。
【０４００】
ノード装置Ｒ４は、ノード装置Ｒ５からラベル割り当てトリガメッセージを受信すると、ノード装置Ｒ５に対し、ラベル割り当てメッセージを返す。
【０４０１】
ノード装置Ｒ５は、ノード装置Ｒ４からラベル割り当てメッセージを受信すると、ノード装置Ｒ４はそのフローに対する次ホップノードであり、かつ、受信ホップカウントがしきい値以下であり、かつ、確定フラグがオンであり、かつ、終段ノードでなく、かつ、入力側ラベルが存在しないため、ノード装置Ｒ４にラベル割り当て成功メッセージを送信する。ラベル割り当て成功メッセージには、（初段ノード情報、ホップカウント）＝（Ｒ５、１）を指定する。
【０４０２】
ノード装置Ｒ４は、ノード装置Ｒ５からラベル割り当て成功メッセージを受信すると、（初段ノード情報、ホップカウント）＝（Ｒ５、２）を指定した更新メッセージを次ホップノードＲ３に送信し、確定フラグをオフにする。
【０４０３】
ノード装置Ｒ３は、ノード装置Ｒ４から更新メッセージを受信すると、最大のホップカウントを与える初段ノードはＲ８であるため、受信した（初段ノード情報、ホップカウント）＝（Ｒ５、２）を入力側ラベルＬａｂｅｌ＝ｄと対応付けるとともに、ノード装置Ｒ４に更新成功メッセージを返す。
【０４０４】
ノード装置Ｒ４は、ノード装置Ｒ３から更新成功メッセージを受信すると、確定フラグをオンにし、以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングが可能となる。
【０４０５】
この結果、図３４のようなラベルスイッチングパスができる。
【０４０６】
次に、図３４の状態から、さらに経路変更が起こり、ノードＲ２の次ホップノードがＲ１からＲ５に変わったとする。このとき、Ｆｌｏｗｉｄ＝Ｅｇｒｅｓｓ［Ｒ１］に対しては、Ｒ２→Ｒ５→Ｒ４→Ｒ３→Ｒ２というループした経路となっている。
【０４０７】
このとき、経路変更に伴って図３５に示すようなパケットのやりとりが行なわれる。図３５において、ＲＥＬはラベル解放メッセージ、ＲＥＬ＿ＡＣＫはラベル解放成功メッセージ、ＴＲＧはラベル割り当てトリガメッセージ、ＳＥＴＵＰはラベル割り当てメッセージ、ＱＲＹは照会メッセージ、ＱＲＹ＿ＮＡＣＫは照会失敗メッセージ、ＵＰＤは更新メッセージ、ＵＰＤ＿ＡＣＫは更新成功メッセージ、である。
【０４０８】
まず、ノード装置Ｒ２は、経路変更前の次ホップノードＲ１に対してラベル解放メッセージを送信するとともに、確定フラグをオフにする。
【０４０９】
ノード装置Ｒ１は、ノード装置Ｒ２からラベル解放メッセージを受信すると、ノード装置Ｒ２との間のラベル割り当てを解放し、ラベル解放成功メッセージをノード装置Ｒ２に返す。
【０４１０】
ノード装置Ｒ２は、ノード装置Ｒ１からラベル解放成功メッセージを受信すると、確定フラグをオンにし、新しい経路上の次ホップノードＲ５に対してラベル割り当てトリガメッセージを送信する。
【０４１１】
ノード装置Ｒ５は、ノード装置Ｒ２からラベル割り当てトリガメッセージを受信すると、ノード装置Ｒ２に対し、ラベル割り当てメッセージを返す。
【０４１２】
ノード装置Ｒ２は、ノード装置Ｒ５からラベル割り当てメッセージを受信すると、ノード装置Ｒ５に、照会メッセージを送信するとともに、確定フラグをオフにする。照会メッセージには、（初段ノード情報、ホップカウント）＝（Ｒ８、５）を指定する。
【０４１３】
ノード装置Ｒ５は、ノード装置Ｒ２から照会メッセージを受信すると、次ホップノードＲ４に更新メッセージを送信し、確定フラグをオフにする。更新メッセージには、（初段ノード情報、ホップカウント）＝（Ｒ８、６）を指定する。
【０４１４】
ノード装置Ｒ４は、ノード装置Ｒ５から更新メッセージを受信すると、次ホップノードＲ３に更新メッセージを送信し、確定フラグをオフにする。更新メッセージには、（初段ノード情報、ホップカウント）＝（Ｒ８、７）を指定する。
【０４１５】
ノード装置Ｒ３は、ノード装置Ｒ４から更新メッセージを受信すると、受信した初段ノード情報Ｒ８は、すでにノード装置Ｒ６との間で割り当てた出力側ラベルＬａｂｅｌ＝ｅに対応しているため、ループであると判断し、ノード装置Ｒ４に更新失敗メッセージを返す。
【０４１６】
ノード装置Ｒ４は、ノード装置Ｒ３から更新失敗メッセージを受信すると、ノード装置Ｒ５に更新失敗メッセージを返し、確定フラグをオンにする。
【０４１７】
ノード装置Ｒ５は、ノード装置Ｒ４から更新失敗メッセージを受信すると、ノード装置Ｒ２に照会失敗メッセージを返し、確定フラグをオンにする。
【０４１８】
ノード装置Ｒ２は、ノード装置Ｒ５から照会失敗メッセージを受信すると、確定フラグをオンにする。以降、入力側ラベルと出力側ラベルとの間でラベルスイッチングは行なわれない。
【０４１９】
この結果、経路がループしているにもかかわらず、図３６のようなループのないラベルスイッチングパスができる。
【０４２０】
なお、本実施形態では、確定フラグに加え、初段ノード情報と、初段ノードからのホップカウントを用いた場合について述べたが、第１、第２の実施形態と同様にして、初段ノード情報と、ホップカウントのいずれかを使用しないでループ検出を行なうことが可能である。
【０４２１】
次に、図３７に、ラベル割り当てメッセージを受信したノードの処理手順を現したフローチャートを示す。
【０４２２】
受信メッセージ中のフロー識別子をＦとする（ステップＳ３１１）。
【０４２３】
まず、フロー識別子＝Ｆのフローテーブルエントリで入力側ラベルが受信ラベルとマッチするエントリＥを探す。これが見つからなければ、更新メッセージの送信ノードに更新失敗メッセージを送信する（ステップＳ３１２，Ｓ３１５）。そうでなく、もし、フロー識別子＝Ｆのフローテーブルエントリで初段ノード情報が設定されていないエントリが存在すれば、更新メッセージの送信ノードに更新失敗メッセージを送信する（ステップＳ３１３，Ｓ３１５）。そうでなく、エントリＥの確定フラグがオフであれば、更新メッセージの送信ノードに更新失敗メッセージを送信する（ステップＳ３１４，Ｓ３１５）。
【０４２４】
そうでない場合には、受信した初段ノード情報および初段からのホップカウントをエントリＥに登録する（ステップＳ３１６）。
【０４２５】
次に、受信ホップカウントがフロー識別子＝Ｆを持つような（エントリＥ以外の）全フローテーブルエントリ中の初段からのホップカウントよりも大きく、かつ、終段ノードでなければ、確定フラグをオフにして後段ノードに更新メッセージを送信する（ステップＳ３１７，Ｓ３１８，Ｓ３２０）。そうでなければ、更新メッセージの送信ノードに更新成功メッセージを返す（ステップＳ３１７，Ｓ３１８，Ｓ３１９）。
【０４２６】
次に、第４、第５の実施形態において、ループ検出のための更新メッセージをパスの向きと逆方向に流す場合について説明する。
【０４２７】
この場合には、ラベル割り当てメッセージを送信したノードは、確定フラグをオフにし、照会メッセージを送信することになっているノードは、照会メッセージを送信する代わりに、更新メッセージを入力側ラベルが存在する上流側隣接ノードに送信して確定フラグをオフにする。更新メッセージは、入力側ラベルが存在する上流側隣接ノードに次々にフォワードされ、確定フラグがオフであるノードが更新メッセージを受信した場合には、ループであると判断し、更新失敗メッセージを返す。そうでなく、初段ノードが更新メッセージを受信した時に確定フラグがオンである場合には、更新成功メッセージを返す。少なくとも一つの上流側隣接ノードから更新失敗メッセージを受信した場合には、下流側隣接ノードに更新失敗メッセージを返し、そうでない場合には、更新成功メッセージを返す。いずれの場合も確定フラグをオンにする。更新メッセージを最初に送信ノードが更新失敗メッセージを受信すると、ラベル割り当て失敗メッセージを下流隣接ノードに送信し、更新成功メッセージを受信するとラベル割り当て成功メッセージを下流隣接ノードに送信する。いずれの場合も確定フラグをオンにする。ラベル割り当て成功メッセージを受信したノードはラベルスイッチングが可能となり、ラベル割り当て失敗メッセージを受信したノードは、入力側ラベルを削除する。いずれの場合にも確定フラグをオンにする。
【０４２８】
例えば、図３６において、ノード装置Ｒ５は、確定フラグをオフにしてノード装置Ｒ５にラベル割り当てメッセージを送信する。ノード装置Ｒ２は、ノード装置Ｒ５からラベル割り当てメッセージを受信すると、確定フラグをオフにしてノード装置Ｒ３に更新メッセージを送信する。この更新メッセージは、ノード装置Ｒ３からノード装置Ｒ４とノード装置Ｒ６、ノード装置Ｒ４からノード装置Ｒ５、ノード装置Ｒ６からノード装置Ｒ７、ノード装置Ｒ７からノード装置Ｒ８へとフォワードされ、ノード装置Ｒ５が更新メッセージを受信した時、確定フラグがすでにオフであるため、ループであると判断し、更新失敗メッセージをノード装置Ｒ４に返す。ノード装置Ｒ４はノード装置Ｒ３に更新失敗メッセージを返す。ノード装置Ｒ８からノード装置Ｒ３へは更新成功メッセージがフォワードされる。ノード装置Ｒ３は、ノード装置Ｒ２に更新失敗メッセージを返す。ノード装置Ｒ２は更新失敗メッセージを受信すると、ノード装置Ｒ５にラベル割り当て失敗メッセージを返す。
【０４２９】
次に、第４、第５の実施形態において、ラベルのマージを行なわないノードが存在する場合の動作について説明する。
【０４３０】
この場合には、各ノードでラベルフィールドをフロー識別フィールドと、初段識別用フィールドの２つのフィールドに分割する。フロー識別用フィールドは、フローを識別するために使用し、初段識別用フィールドは、フロー毎に初段ノードを識別するために使用する。
【０４３１】
ラベルスイッチングパスの生成手順は、第４、第５の実施形態で説明したアルゴリズムとほぼ同じである。ただし、ラベルのマージを行なわないノードでは、ラベル割り当てメッセージには、ラベルのフロー識別用フィールドのみ値を指定し、初段識別用フィールドには値を指定しないでおく。このようなラベルを「半割り当てラベル」と呼ぶ。ラベルのマージを行なうノードでは、ラベル割り当てメッセージには、ラベルのフロー識別用フィールドと初段識別用フィールド両方の値を指定する。このようなラベルを「全割り当てラベル」と呼ぶ。半割り当てラベルと全割り当てラベルの識別には、ラベルの１ビットを使用する。
【０４３２】
半割当てラベルが指定されたラベル割り当てメッセージが初段ノードに到達すると、全割り当てラベルの割り当てを行ない、割り当てられたラベルが初段ノードから終段ノードに向けて通知される。通知には、更新メッセージを使用する。更新メッセージを受信したとき、メッセージ中の全割り当てラベルがまだ登録されていない場合には、受信した全割り当てラベルを入力側ラベルとして登録し、さらに、入力側ラベルに対応する出力側の全割り当てラベルの割り当てを行なった後、出力側の全割り当てラベルを含んだ更新メッセージを下流隣接ノードに送信するようにする。
【０４３３】
さらに、半割り当てラベルが指定されたラベル割り当てメッセージを受信したノードが次ホップノードに照会メッセージを送信する場合には、フローに対して割り当てられた全割り当ての入力側ラベルのそれぞれに対応して、メッセージ中のフロー識別用フィールドをフロー識別用フィールドに使用した出力側の全割り当てラベルを割り当て、割り当てた出力側ラベル毎にこれを含んだ照会メッセージを送信する。
【０４３４】
また、更新メッセージが上流から下流に流れる場合で、照会メッセージを受信したノードが更新メッセージを送信する場合には、照会メッセージに記入された全割り当てラベルに対応して、メッセージ中のフロー識別用フィールドをフロー識別用フィールドに使用した出力側の全割り当てラベルを割り当て、これを更新メッセージに記入する。また、更新メッセージを受信したノードが更新メッセージを送信する場合には、更新メッセージに記入された全割り当てラベルに対応して、メッセージ中のフロー識別用フィールドをフロー識別用フィールドに使用した出力側の全割り当てラベルを割り当て、これを更新メッセージに記入する。
【０４３５】
例えば、図２９において、全ノードがラベルのマージを行なわないとすると、ノード装置Ｒ２はノード装置Ｒ５に対して、ノード装置Ｒ２とノード装置Ｒ５の間で初段ノードがノード装置Ｒ６のパス用に割り当てた全割り当てラベルを含んだ照会メッセージと、ノード装置Ｒ２とノード装置Ｒ５の間で初段ノードがノード装置Ｒ５のパス用に割り当てた全割り当てラベルを含んだ照会メッセージの２個の照会メッセージを送信する。また、ノード装置Ｒ５、Ｒ４、Ｒ３は、それぞれ、ノード装置Ｒ４、Ｒ３、Ｒ２に対して、隣接ノード間で初段ノードがノード装置Ｒ６のパス用に割り当てた全割り当てラベルを含んだ更新メッセージと、隣接ノード間で初段ノードがノード装置Ｒ５のパス用に割り当てた全割り当てラベルを含んだ更新メッセージを送信する。
【０４３６】
一方、更新メッセージが下流から上流に流れる場合で、ノードが更新メッセージを送信する場合には、更新メッセージにはすでに割り当てた半割り当てラベルを記入する。
【０４３７】
なお、半割り当てラベルは、Ｕｐｓｔｅａｍラベル割り当て、Ｄｏｗｎｓｔｒｅａｍラベル割り当ての両方が可能であり、全割り当てラベルは、Ｕｐｓｔｒｅａｍラベル割り当てが望ましい。
【０４３８】
また、ラベルとして、ＶＣＩ／ＶＰＩを用いる場合には、ＶＰＩまたはＶＣＩをフロー識別用フィールドまたは初段識別用フィールドとして使用する。
【０４３９】
次に、Ｅｇｒｅｓｓ  ｃｏｎｔｒｏｌにおいて、マルチパスに対するラベルスイッチングパスを生成する場合について説明する。
【０４４０】
マルチパスに対するラベルスイッチングパスを生成する場合には、マルチパスの分岐ノードにおいて、マルチパスのそれぞれの下流隣接ノードからのラベル割り当てメッセージに対して、別々のラベルを登録し、各々の上流隣接ノードに別々のラベル割り当てメッセージを送信するようにする。
【０４４１】
また、マルチパスの１つの経路が削除された場合には、各々の上流隣接ノードに削除された経路に対応するラベルスイッチングパスを解放するためのラベル解放メッセージを送信するようにする。このラベル解放メッセージは初段ノードまでフォワードされる。
【０４４２】
次に、以上の第４、５の実施形態における、メッセージのフォーマットの例について説明する。
【０４４３】
ラベル割り当てメッセージ、ラベル割り当て成功メッセージ、ラベル割り当て失敗メッセージ、ラベル解放メッセージ、ラベル解放成功メッセージ、ラベル解放失敗メッセージ、更新メッセージ、更新成功メッセージ、更新失敗メッセージのフォーマットは、図１１、または図１２で示した例と同じである。ただし、更新メッセージ、更新成功メッセージ、更新失敗メッセージにはラベルの値を指定する。また、照会メッセージ、照会成功メッセージは、図１１で示した例と同じで、照会失敗メッセージは、図１２で示した例と同じである。ただし、これらのメッセージにはラベルの値を指定する。さらに、上記メッセージにおいて、初段ノード情報、または、ホップカウントを使用しない場合にはこれらのフィールドは省略してもよい。
【０４４４】
また、ラベル割り当てトリガメッセージのフォーマットは、図１１において、初段ノードアドレス、初段ノードローカルＩＤ、ホップカウント、ラベル、および、リクエスト識別子フィールドを省略したものとなる。
【０４４５】
なお、これまでの説明では、一旦、ラベルが割り当てられたパスに対しては、ラベル割り当てメッセージは送信しないようなハードステート型のプロトコルを前提にしていたが、本発明は、いったんラベルが割り当てられたパスに対しても、定期的にラベル割り当てメッセージを送信するようなソフトステート型のプロトコルに関しても有効である。ソフトステート型の場合には、一定期間ラベル割り当てメッセージを受信しない場合にはラベルが解放される。
【０４４６】
なお、以上の各手順、手段、機能は、ハードウェアとしてもソフトウェアとしても実現可能である。また、ソフトウェアとして実現する場合、コンピュータに上記各手順を実行させるための（あるいはコンピュータを上記各手段として機能させるための、あるいはコンピュータに上記各機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０４４７】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０４４８】
【発明の効果】
本発明によれば、ホップカウントを用いる場合に比べ早期にループを検出することが可能となる。また、本発明によれば、ラベルのマージを行う場合にも、早期にループを検出することが可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係るノード装置を説明するための図
【図２】隣接ノード同士がバス型接続されている場合について説明するための図
【図３】隣接ノード同士がポイント−ポイントリンク接続されている場合について説明するための図
【図４】本発明の第２の実施形態に係るノード装置を説明するための図
【図５】同実施形態に係るノード装置を説明するための図
【図６】同実施形態に係るノード装置を説明するための図
【図７】同実施形態に係るノード装置を説明するための図
【図８】本発明の第１および第２の実施形態に係るノード装置を説明するための図
【図９】本発明の第３の実施形態に係るノード装置を説明するための図
【図１０】本発明の第３の実施形態に係る他のノード装置を説明するための図
【図１１】ラベル割り当てメッセージのフォーマットの一例を示す図
【図１２】ラベル割り当て失敗メッセージのフォーマットの一例を示す図
【図１３】フローテーブルのフォーマットの一例を示す図
【図１４】ラベル割り当てメッセージ受信時のノード装置の動作の一例を示すフローチャート
【図１５】ホップカウント更新メッセージ受信時のノード装置の動作の一例を示すフローチャート
【図１６】ラベル割り当てメッセージ受信時のノード装置の動作の他の例を示すフローチャート
【図１７】フローテーブルのフォーマットの他の例を示す図
【図１８】ラベル割り当てメッセージ受信時のノード装置の動作のさらに他の例を示すフローチャート
【図１９】ラベル割り当てメッセージ受信時のノード装置の動作のさらに他の例を示すフローチャート
【図２０】ホップカウント更新メッセージ受信時のノード装置の動作の他の例を示すフローチャート
【図２１】ホップカウント更新メッセージ受信時のノード装置の動作のさらに他の例を示すフローチャート
【図２２】ラベル割り当てメッセージ受信時のノード装置の動作のさらに他の例を示すフローチャート
【図２３】ラベル解放メッセージ受信時のノード装置の動作の一例を示すフローチャート
【図２４】ラベル解放メッセージ受信時のノード装置の動作の他の例を示すフローチャート
【図２５】本発明の第４の実施形態に係るノード装置を説明するための図
【図２６】同実施形態に係るノード装置を説明するための図
【図２７】同実施形態に係るノード装置を説明するための図
【図２８】同実施形態に係るノード装置を説明するための図
【図２９】同実施形態に係るノード装置を説明するための図
【図３０】同実施形態に係るノード装置を説明するための図
【図３１】同実施形態に係るラベル割り当てメッセージ受信時のノード装置の動作の一例を示すフローチャート
【図３２】本発明の第５の実施形態に係るノード装置を説明するための図
【図３３】同実施形態に係るノード装置を説明するための図
【図３４】同実施形態に係るノード装置を説明するための図
【図３５】同実施形態に係るノード装置を説明するための図
【図３６】同実施形態に係るノード装置を説明するための図
【図３７】同実施形態に係るラベル割り当てメッセージ受信時のノード装置の動作の一例を示すフローチャート
【符号の説明】
Ｒ１〜Ｒ８…ノード装置
【図１】
0003688877.tif 000002
【図２】
0003688877.tif 000003
【図３】
0003688877.tif 000004
【図４】
0003688877.tif 000005
【図５】
0003688877.tif 000006
【図６】
0003688877.tif 000007
【図７】
0003688877.tif 000008
【図８】
0003688877.tif 000009
【図９】
0003688877.tif 000010
【図１０】
0003688877.tif 000011
【図１１】
0003688877.tif 000012
【図１２】
0003688877.tif 000013
【図１３】
0003688877.tif 000014
【図１４】
0003688877.tif 000015
【図１５】
0003688877.tif 000016
【図１６】
0003688877.tif 000017
【図１７】
0003688877.tif 000018
【図１８】
0003688877.tif 000019
【図１９】
0003688877.tif 000020
【図２０】
0003688877.tif 000021
【図２１】
0003688877.tif 000022
【図２２】
0003688877.tif 000023
【図２３】
0003688877.tif 000024
【図２４】
0003688877.tif 000025
【図２５】
0003688877.tif 000026
【図２６】
0003688877.tif 000027
【図２７】
0003688877.tif 000028
【図２８】
0003688877.tif 000029
【図２９】
0003688877.tif 000030
【図３０】
0003688877.tif 000031
【図３１】
0003688877.tif 000032
【図３２】
0003688877.tif 000033
【図３３】
0003688877.tif 000034
【図３４】
0003688877.tif 000035
【図３５】
0003688877.tif 000036
【図３６】
0003688877.tif 000037
【図３７】
0003688877.tif 000038