経路制御装置
【課題】比較的少ない枚数の経路表を用いて、ノードやリンクの故障時に適切に迂回するネットワークを構成できる経路制御装置を提供する。
【解決手段】ノードｕ５が故障しているときに、ノードｕ１が宛先ｄのＩＰパケットを受信すると、ｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄという経路でＩＰパケットを転送する。特に、iラベルが付加されたｕ２、ｏラベルが付加されたｕ３、ｓラベルが付加されたｕ４がそれぞれＩＰパケットに含まれる状態を書き換えることで、第２経路表を使う迂回の経路（ｕ１→ｕ２→ｕ３）を経て、第１経路表を使って最短路を通るトンネルに入り（ｕ３→ｕ４）、トンネルを出た後は第２経路表を使い（ｕ４→ｗ１）、その後、また第１経路表を使う（ｗ１→ｗ２→ｄ）という経路となる。
【解決手段】ノードｕ５が故障しているときに、ノードｕ１が宛先ｄのＩＰパケットを受信すると、ｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄという経路でＩＰパケットを転送する。特に、iラベルが付加されたｕ２、ｏラベルが付加されたｕ３、ｓラベルが付加されたｕ４がそれぞれＩＰパケットに含まれる状態を書き換えることで、第２経路表を使う迂回の経路（ｕ１→ｕ２→ｕ３）を経て、第１経路表を使って最短路を通るトンネルに入り（ｕ３→ｕ４）、トンネルを出た後は第２経路表を使い（ｕ４→ｗ１）、その後、また第１経路表を使う（ｗ１→ｗ２→ｄ）という経路となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの経路上において故障などの異常状態が発生した場合に、迂回路を設定する経路制御装置に関する。
【背景技術】
【０００２】
従来から、ルータなどの経路制御装置はネットワーク上の宛先とこの宛先に至るための次の転送先との対応を示す経路表（ルーティング・テーブル）を備えており、やってきたＩＰパケットの宛先を上記ルーティング・テーブルと照合して次の転送先を決定することが行われている。そして、次の転送先のルータへの経路上に故障などが発生して転送が行えないことがあるため、予備の経路表を予め用意しておく技術が知られている。
【０００３】
経路上の故障には大別して２種類ある。リンクの故障（link failure）とノードの故障（node failure）である。
そして、宛先への経路上に存する任意の１リンクが故障したとしても、そのリンクの故障に対して適切な迂回路を設定することを、「リンクプロテクション」という。また、任意の１ノードが故障したとしても、そのノードの故障に対しても適切な迂回路を設定することを「ノードプロテクション」という。
【０００４】
このリンクプロテクションやノードプロテクションを実現するためのひとつの方策として、経路表の枚数を増やして対応する技術が知られている（非特許文献１〜５参照）。例えば、非特許文献１では、各ノードにおいて、そのノードが持つインターフェイス（ポート）毎の経路表を用意しておくことで、リンクプロテクションの実現を試みている。
また、非特許文献２では、同様の手法を用いてリンクプロテクションを実現する経路表の計算方法を提案している。
【０００５】
また、非特許文献４では、リンクプロテクションやノードプロテクションを保証するために、幾枚かの経路表を要するとしており、ネットワークの規模などにも依存するものの一般に3枚から5枚の追加テーブルが必要としている。
さらに、非特許文献５では、様々な故障に対応するための必要な追加テーブルの枚数は2枚から3枚としており、上記非特許文献４よりは少ない枚数であるが、一般的なケースにおいて何枚の経路表を要するかに関しては開示されていない。
【０００６】
その一方で、経路表をむやみに増やすと各ノードの処理負荷が重くなることがある。このため、非特許文献６では、パケットヘッダに埋め込んだ状態を迂回に利用することで、経路表の枚数を増加を回避しつつ適切な迂回路の設定を試みている。
非特許文献６に開示された技術について説明する。図１４に示すように、ネットワーク１００は、ノードｕ１〜ｕ５，ｗ１，ｗ２，ｄから構成される。
【０００７】
各ノードには、宛先であるノードｄとノードｄに至るための次の転送先のノード（次ホップ）を示す経路表、すなわち通常用の第１経路表（1st）と予備用の第２経路表（2nd）が備えられている。なお、図１４において、第１経路表，第２経路表の次ホップへの経路をそれぞれ「第１経路」，「第２経路」と矢印で示している。
ここで図１４におけるネットワークのルールは、次の通りである。
【０００８】
（ルール１）ＩＰパケットには、第１と第２経路表のいずれを使うべきかを示す状態ラベルが付加されており、状態０が第１経路表、状態１が第２経路表を使うべきことを示す。
（ルール２）第１経路表の次ホップへにつながるリンクの故障を検出するなどして、ＩＰパケットを転送できないノードは、ＩＰパケットをデフォルトの状態０から状態１へと変更し、第２経路表の次ホップに転送する。
【０００９】
（ルール３）ｓフラグが関連付けられているノードは、状態１のＩＰパケットを受信したときに、状態１から状態０へと状態を変更する。状態０への変更によりこのノード以降のノードは第１経路表を使うこととなる。
なお、非特許文献６では、ＩＰパケットのループ防止のためにさらに状態を変更する仕組みが紹介されているが本論と密接には関係しないので説明を省略する。
【００１０】
このルール下における具体的な動作例を説明すると、例えば、ノードｕ１が宛先ｄのＩＰパケットを受信した場合でリンクの故障を検出をしないときには、ノードｕ１は第１経路表の次ホップｕ５へとＩＰパケットを転送し、ノードｕ５もノードｕ５の第１経路表の次ホップｄへ転送とする。つまりＩＰパケットは、ｕ１→ｕ５→ｄと転送されることとなる。
【００１１】
また、図１５に示すように、同じくノードｕ１が宛先ｄのＩＰパケットを受信した場合で、ｕ５とｄとの間のリンク故障を検出すると、ｕ１→ｕ５→ｕ４→ｗ１→ｗ２→ｄという流れになる。
すなわち、
（１）ノードｕ１：第１経路表の次ホップｕ５へとＩＰパケットを転送する
（２）ノードｕ５：ｕ５−ｄ間のリンク故障を検出したのでＩＰパケットの状態を状態０から状態１へと変更、そして第１経路表ではなく第２経路表の次ホップｕ４へとＩＰパケットを転送する
（３）ノードｕ４：ＩＰパケットの状態は状態１であるので第２経路表の次ホップｗ１へとＩＰパケットを転送。ただし、ｓフラグが関連付けられているので、転送前に状態１から状態０へと変更しておく
（４）ノードｗ１：ＩＰパケットの状態は状態０であるので第１経路表の次ホップｗ２へとＩＰパケットを転送する
（５）ノードｗ２：ＩＰパケットの状態は状態０であるので第１経路表の次ホップｄへとＩＰパケットを転送する
、という流れとなる。
【００１２】
このように、非特許文献６によると、宛先のノードへの経路上に存する任意の１リンクが故障したとしても、そのリンクの故障に対して適切な迂回路を設定できる（リンクプロテクション）。また、予め計算しておいた経路表を利用するので、故障検出後に瞬時に迂回路を設定することができるとしている。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】S. Lee, Y. Yu, S. Nelakuditi, Z.L. Zhang, and C-N. Chuah,"Proactive vs. Reactive Approaches to Failure Resilient Routing," In Proceings of IEEE INFOCOM '04, Mar.2004.
【非特許文献２】Z. Zhong, S. Nelakuditi, Y. Yu, S. Lee,J. Wang,and C.N. Chuah,"Failure Inferencing Based Fast Rerouting for Handling Transient Link and Node Failures," In Proceings of IEEE Global Internet, Mar.2005.
【非特許文献３】J. Wang and S. Nelakuditi,"IP Fast Reroute with Failure Inferencing," In Proceedings of SIGCOMM workshop (INM) 2007,pp.268-273,2007.
【非特許文献４】A. Kvalbein, A.F. Hansen, T.Cicic, S. Gjessing, and O. Lysne, "Multiple routing configurations for fast IP network recovery," IEEE/ACM Transactions on Networking, Vol.17, Issue.2,pp.473-486, 2009.
【非特許文献５】T.Cicic, A.F. Hansen,A. Kvalbein, M, Hartmann, R. Martin and M. Menth,"Relaxed multiple routing configurations for IP fast reroute," In Proceings of NOMS2008,pp.457-464, 2008.
【非特許文献６】Takuya Yoshihiro，"A Single Backup-Table Rerouting Scheme for Fast Failure Protection in OSPF"，IEICE Transactions on Communications, Vol. E91-B, No. 9, pp. 2838-2847, 2008.9. (IEICE/IEEE Joint Special Section on Autonomous Decentralized Systems Theories and Application Deployments)
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、ネットワーク技術においては、上記リンクプロテクションも重要であるが、ノード故障の発生率も無視できないほどに高い。このため、ノードプロテクションをも実現することが重要課題となっている。
しかしながら、このノードプロテクションに対しては、上記した非特許文献６の技術では有効に機能しないことがある。
【００１５】
具体的には図１６に示すように、ネットワーク１０２においては、ノードｕ１が宛先ｄであるＩＰパケットを受信した場合で、ノードｕ５が故障しているときには、ＩＰパケットは、ｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄと転送されるので迂回できる。もっとも、ノードｕ３は第１経路表の次ホップおよび第２経路表の次ホップが同じｕ４になっている。このため、ノードｕ３が宛先ｄのＩＰパケットを受信した場合にｕ４との間のリンク故障を検出すると、ノードｕ３は次の適切な転送先を決定することができず迂回できず（図１７参照）、ＩＰパケット損失を招くこととなる。
【００１６】
これに対しては、リンク故障やノード故障などに応じて経路表を用意するなど経路表の枚数を増やすことで対応することも考えられるが、上述のように経路表の枚数の増加は各ノードにおける処理負荷の増大などを招くのでの避けたい。
本発明はこのような背景の下になされたものであって、比較的少ない枚数の経路表を用いて、ノードやリンクの故障時に適切に迂回するネットワークを構成できる経路制御装置を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記ラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記ラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、前記第１ノードへと前記パケットを転送して、前記ラベル情報が第３ラベルの付加を示していれば転送前に前記状態２から前記状態１へと書き換え、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、を備えることを特徴とする。
【００１８】
また、本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と転送先の決定に係る状態を示す情報とを格納するパケットを受信し、自ノード宛のカプセル化されたパケットを受信すると、カプセル化の解除後のパケットを、受信したパケットとして扱う受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、当該パケットを、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示すノードからみて第１ノードであるノードを宛先として状態が状態０であるパケットに内包させるようカプセル化し、カプセル化したパケットを前記第１ノードへと前記パケットを転送し、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、を備えることを特徴とする。
【００１９】
また、本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、受信されたパケットに前記第１経路表に対応する経路であることを識別するＭＰＬＳラベルを付加した後、当該ＭＰＬＳラベルにより識別されるノードへと転送し、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備えることを特徴としている。
【００２０】
また、本発明に係る経路制御システムにおける方法は、ネットワークを構成する複数のノードから構成される経路制御システムにおける方法であって、各ノードにおいて、宛先ノードに至る第１経路と、前記宛先ノードに至り第１経路とは異なる迂回路である第２経路とを記憶する記憶ステップと、各ノードにおいて、第１経路を用いたパケットの転送が可能でないならば、パケットに迂回途中である旨を示す情報を付加した後で第２経路を用いてパケットを転送する迂回開始ステップと、各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信すると、第２経路を用いてパケットを転送する迂回中ステップと、各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信したにも関わらず、自ノードに関して宛先ノードに至るための経路に係る所定の条件を満足していれば、前記迂回中ステップで用いる第２経路に代えて、第１経路表を用いてパケットを転送する迂回中トンネルステップと、を備えることを特徴としている。
【発明の効果】
【００２１】
本発明に係る経路制御装置によれば、第１から第３ラベルにより状態０から状態４を状態を書き換えることにより、第１経路表か第２経路表のどちらを用いて転送先とするかを柔軟に決定することができ、ノードやリンクの故障時に適切に迂回路を設定することができる。
【図面の簡単な説明】
【００２２】
【図１】ネットワークの概要を示す図
【図２】ノードｕ２の機能ブロック図
【図３】アルゴリズム"CreateBackupTable-NP"に係る変数の定義を示す図
【図４】アルゴリズム"CreateBackupTable-NP"を示す図
【図５】プロシージャ"findBackupPath"を示す図
【図６】プロシージャ"setBackupNextHops"を示す図
【図７】ＩＰパケット受信に係る処理の流れを示すフローチャート
【図８】各ノードにおける第１および第２経路表、さらに各ラベルのtrue／falseを示す図
【図９】ノードｕ５が故障した際の各ノードにおける処理の流れを示すシーケンス図
【図１０】変形例に係るネットワーク構成などを示す図
【図１１】カプセル化を利用した変形例に係るネットワーク構成などを示す図
【図１２】ＭＰＬＳを利用した変形例に係るネットワーク構成などを示す図
【図１３】（ａ）ＩＰパケットのヘッダ部分の内容を示す図、（ｂ）迂回後（状態３）への変更に関するフローチャート
【図１４】非特許文献６にならったネットワーク構成を示す図
【図１５】図１４のネットワークにおいて、ｕ５−ｄ間のリンク故障を示す図
【図１６】非特許文献６でノードプロテクションを行おうとしたときのネットワーク構成を示す図
【図１７】図１６のネットワークにおいて、ｕ３−ｕ４間のリンク故障を示す図
【発明を実施するための形態】
【００２３】
以下、図面を参照しながら実施の形態について説明する。
＜構成＞
図１に示すように、ネットワーク１は８個のノードｕ１〜ｕ５，ｗ１，ｗ２，ｄから構成される。各ノードはルータから構成され、ネットワーク層においてＩＰプロトコルに従って通信を行う。各ノードはＯＳＰＦ（Open Shortest Path First）のルーティング・プロトコルに従って動作するものとする。
【００２４】
また、ネットワークを流れるＩＰパケットのヘッダ部分には、宛先ＩＰアドレスとＴＯＳ（Type Of Service）フィールドが含まれており、このＴＯＳは状態（状態０から状態３までの４種類がある。）の格納領域として用いられている。
図２にノードｕ２の機能ブロック図を示す。各ノードは基本的に同様な構成であるのでノードｕ２だけを代表させて説明する。
【００２５】
ノードｕ２は、インターフェイス部１０、トポロジ部１２、受信部１４、転送部１６、転送先決定部１８、故障検出部２０、状態制御部２２、各部を制御する制御部２４、計算部３０、記憶部４０を備える。
インターフェイス部１０は、他のノードと接続するための回線インターフェイス（ポート）から構成されており、他のノードとの間でのデータ授受を実現する。
【００２６】
トポロジ部１２は、他のノードに対して、自ノードに接続されたノード（隣接ノード）のＩＤやインターフェイスのコストを含むLSA（Link State Advertisement）と呼ばれるトポロジ情報を送信する。また他のノードから集めたトポロジ情報に基づいてトポロジ・マップを作成する。
受信部１４は、インターフェイス部１０を介してＩＰパケットなどを受信する。
【００２７】
転送部１６は、インターフェイス部１０を介してＩＰパケットなどを、転送先決定部１８に決定された転送先へと転送する。
故障検出部２０は、定期的に隣接ノードとの間でやりとりされるメッセ−ジなどを利用して隣接ノードの故障を検出する。
状態制御部２２は、受信部１４が受信したＩＰパケットのヘッダ部分のＴＯＳ（Type Of Service）フィールド含まれる状態の読み取りや書き換えを行う。この書き換えは、故障検出部２０の故障検出の有無や記憶部４０内のラベル表４６に基づいて行われる。
【００２８】
状態には、最短路転送中であることを示す「状態０」、迂回路転送中であることを示す「状態１」、トンネル転送中であることを示す「状態２」、迂回後であることを示す「状態３」の４種類がある。各状態の機能や書き換え条件については後述する。
計算部３０は、第１経路表計算部３２、第２経路表計算部３４、ラベル計算部３６から構成される。計算部３０のアルゴリズムについては後述する。この計算部３０の計算結果は、記憶部４０内に第１経路表４２、第２経路表４４、ラベル表４６として設定され記憶される。
【００２９】
第１経路表４２は、通常用（プライマリー）の経路表であり、宛先ノードを示す「宛先」４２ａと宛先ノードに至るための「次ホップ」４２ｂとを対応付けた表である。図２中では、「宛先」がノードｄについてのみ記述して他の宛先（ノードｕ１，ｕ３，ｕ４，ｕ５，ｗ１，ｗ２）に関しては省略している。第２経路表４４は、予備用（バックアップ）の経路表であり、第１経路表４２同様、宛先ノードを示す「宛先」４４ａと宛先ノードに至るための「次ホップ」４４ｂとを対応付けた表である。
【００３０】
ラベル表４６は、「宛先」４６ａと、３つのラベル「ｓ」４６ｂ，「ｉ」４６ｃ，「ｏ」４６ｄの各ラベルについてtrue/falseを示す表である。図２のラベル表４６の例では、宛先ノードｄに関してｉ-ラベルがtrueで、ｓ-ラベル，ｏ-ラベルがfalseあることを示している。
＜アルゴリズム＞
次に、計算部３０の処理内容を定めるアルゴリズムについて説明する。
【００３１】
まず、第１経路表４２は、ＯＳＰＦにおいて一般的に用いられている手法により計算を行う。つまり、トポロジ部１２において作成したトポロジ・マップを基に、ダイクストラの最短路計算アルゴリズムを用いて最短経路を求めることにより、宛先ノードに至るための次ホップを決定する。
次に、第２経路表４４とラベル表４６を求めるアルゴリズムについて、以下説明する。
【００３２】
まず図３を用いて変数の定義について説明する。Ｇ（Ｖ，Ｅ）は、ネットワークを表す有向グラフである。Ｖはノードの集合、Ｅは有向リンクの集合である。関数ｆ：ｅ（∈Ｅ）→Ｒは、各リンクの重みを表す。ｐｄ（ｖ）はノードｖの第１経路表における宛先ｄへの次ホップを表し、ｂｄ［ｖ］は、ノードｖの第２経路表における宛先ｄへの次ホップを表す。ｐｄ（ｖ）が表す宛先ｄへの最短経路木を転送木Ｔｄと呼ぶ。Ｔｄにおいて、ｖ（∈Ｖ）の親ノードをｐ（ｖ）とし、ｖ（∈Ｖ）の子孫ノードの集合をＤｄ（ｖ）と表す。またｖ（∈Ｖ）の子ノードの集合をＣｄ（ｖ）と表す。また、Ｔｄに対して、ノードｖ（∈Ｖ）を根として導出される部分木をＴｄｖと表す。
【００３３】
ノードｖの宛先ｄに対するｓ−ラベル、ｉ−ラベル、ｏ−ラベルをｓｄ［ｖ］，ｉｄ［ｖ］，ｏｄ［ｖ］と表す。同様にノードｖの宛先ｄに対するｔ−ラベルを定義しｔｄ［ｖ］と表す。ｔ−ラベルは迂回路中の最短路によるトンネルを構成するノード、即ちｉ−ラベルとｏ−ラベルとの間のノード（正確には、ｉ−ラベルノードの次ノードからｏ−ラベルノードまでに含まれるノードで両端を含む）に一時的に設定されるラベルである。
【００３４】
また、各ラベルがｔｒｕｅであるノードを、それぞれｓ−ラベルノード、ｉ−ラベルノード、ｏ−ラベルノード、ｔ−ラベルノードと呼ぶ。
本アルゴリズムの方式では、ＩＰパケットがノードｕ∈Ｖにおいて第２経路表の次ホップに転送され、その後、迂回後状態（状態３）になるまでの経路を、ｕの「迂回路」と定義する。
【００３５】
つまり、迂回路ｐ＝（ｕ（＝ｖ１），ｖ２，．．．，ｖｎ）上の各ノード及び１≦ｋ＜ｎに対して、ｐｄ（ｖｋ）＝ｖｋ＋１であれば、ｖｋはｔ−ラベルノードでなければならず、ｔｄ［ｖｋ］＝falseかつｔｄ［ｖｋ＋１］＝trueであればｖｋはｉ−ラベルノード、ｔｄ［ｖｋ］＝trueかつｔｄ［ｖｋ＋１］＝falseであればｖｋはｏ−ラベルノード、さらに、ｖｎ−１はｓ−ラベルノードでなければならない。
【００３６】
ノード故障に対応する場合には、ｖの迂回路ｐはｐ（ｖ）を通らずにＩＰパケットをｄまで転送できる必要がある。このためには、ｐの終点ノードでＴｄｐ（ｖ）の外部にあるノードｗがＤｄ（ｐ（ｖ））に属さない関係であればよい。ｖ∈Ｖに対してＴｄｐ（ｖ）を「ＮＰ回避領域」と呼び、始点がｖ、終点がＴｄｐ（ｖ）の外部のノードであるｗ、である迂回路ｐをｖの「ＮＰ迂回路」と呼ぶ。
【００３７】
一方、リンク故障に対応する場合には、ｖの迂回路ｐはリンク（ｖ，ｐ（ｖ））を通らずにＩＰパケットをｄまで転送できる必要がある。このためには、ｐの終点ノードｗがＴｄｖの外部あればよい。よって、ｖ∈Ｖに対して、Ｔｄｖを「ＬＰ回避領域」と呼び、始点がｖ、終点がｗ（Ｔｄｖの外部のノード）である迂回路ｐをｖの「ＬＰ迂回路」と呼ぶ。
【００３８】
迂回路ｐに対して、ｔ−ラベルノードのみから構成される極大な部分路ｑ∈ｐをｐの「トンネル区間」と呼ぶ。逆に、ｔ−ラベルノードｖに対して、そのノードにｔ−ラベルが付加された時に設定された迂回路ｐがただ一つ定まり、ｐのトンネル区間の一つでｖを含むものを「ｖのトンネル区間」と呼ぶ。ｔ−ラベルノードｖに対して、ｖのトンネル区間をｐとは逆向きに辿り、ｔ−ラベルノードでないノードに辿りつくまでの経路を「ｖの逆流経路」と呼ぶ。ｔ−ラベルノードｖから最短路トンネルに合流してパケットが転送される迂回路（即ち「状態２」のパケットがｖから転送される迂回路）をｖの「トンネル迂回路」と呼ぶ。また、経路ｐとｑに対して、これらを連結した経路をｐ＋ｑのように表す。
【００３９】
図４〜図６を参照しながら、第２経路表を求めるアルゴリズム"CreateBackupTable-NP"について説明する。図５，図６は、図４のアルゴリズムで用いられるプロシージャとなっている。
本アルゴリズムでは宛先ｄ毎に動作するため、入力として宛先ｄと、この宛先ｄへの最短路木の一つＴｄをとる。このため、各ノードｕにおいて、ｕがｄ∈Ｖ−｛ｕ｝であるｄのそれぞれに対してアルゴリズムを実行し、出力である宛先ｄに関する第２経路表のエントリとｓ，ｉ，ｏのラベルからｕ（自分自身のノード）に関するものを取り出してＩＰパケット転送に用いることとなる。
【００４０】
図４に示すアルゴリズムにおいては、１〜８行目の初期化処理を行う。そして、Ｔｄの幅優先探索順にノードｖを訪問し（９行目）、ｖの子ノードそれぞれについて、もし第２経路表が設定されていなければＮＰ迂回路を探索し（１０−１２行目）、発見されればこれを設定する（１３−１５行目）。その後、さらにｖの子ノードそれぞれについて、もし第２経路表が設定されていなければＬＰ迂回路を探索し（１８−２０行目）、発見されればこれを設定する（２１−２３行目）。迂回路の探索と設定をこのような順序で行うのは、探索される迂回路の回避領域の根ノードがＴｄの根に近い順になることを保証するためである。この手順により、宛先ｄに対する第２経路表とｓ，ｉ，ｏのラベルを計算する。
【００４１】
本アルゴリズムの１２，２０行目で用いられる"findBackupPath"（迂回路の探索）は、ＬＰ迂回路とＮＰ迂回路ともに図５に示すプロシージャ"findBackupPath"により行われる。このプロシージャ"findBackupPath"は迂回路の始点ノードｕ、宛先ノードｄ、回避領域の根ノードｒを入力にとる。ＮＰ迂回路を探索する場合はｒとしてＮＰ回避領域の根ｐ（ｕ）を入力し、ＬＰ迂回路を探索する場合はｕを用いる。
【００４２】
図５のプロシージャ"findBackupPath"は基本的には、ダイクストラの最短路計算アルゴリズムを少し変更して繰り返し実行することで迂回路を探索する。動作の骨組みとしては、迂回すべきノード（またはリンク）をＧから取り除いたグラフを作成し、その上でｕを始点としてダイクストラのアルゴリズムを実行し、Ｑから取り出した各ノードｖのトンネル区間に迂回路の終点となるノードｗ∈Ｓ１∪Ｓ２∪Ｓ３（Ｓ１は回避領域の外部ノードの集合、Ｓ２はＳ１に含まれないノードの中で第２経路表が定義されていないノード集合、Ｓ３はＳ１∪Ｓ２に含まれないｔ−ラベルノードの集合である。）を発見すると、ｕからｖまでの経路とｖからｗまでＴｄに沿った経路を連結した経路を迂回路ｐとして返す。（正確にはｐは迂回路の部分路であるが、便宜上迂回路と呼ぶことにする。）この際に、Ｓ１∪Ｓ２∪Ｓ３に属するノードｗを終点とするリンク（ｘ，ｗ）の重みとして、ｆ（ｘ，ｗ）の重みに、迂回路を通ってｗに着いたとして以後ｄに至るまでの距離を加えた値を用いる。つまり、ｗ∈Ｓ１の場合には、ｗからｄへの最短経路の距離を加え、ｗ∈Ｓ２の場合にはｗから迂回路を通った場合（即ち、「状態１」で第二経路表を用いて転送された場合）のｗからｄへの距離を加え、ｗ∈Ｓ３の場合には、ｗのトンネル区間が回避領域の根ｒを含む場合にはｗの逆流経路を通った場合のｗからｄへの距離、ｒを含まない場合にはｗのトンネル経路を通った場合のｗからｄへの距離を加える。こうすることで、宛先ｄまでできるだけ最短でたどり着けるｖ∈Ｓ１∪Ｓ２∪Ｓ３を探索できる。
【００４３】
処理の例外として、Ｓ３に属するノードｗを発見し、ｗのトンネル区間が回避領域の根ｒを含む場合には、上記のｐとは異なる経路を返す。即ち、ｕからｖまでの経路とｖからｗまでＴｄに沿った経路、そしてｗの逆流経路の３経路を連結したものをｐとして返す。上記のように、このプロシージャは設定すべき迂回路ｐを返す。この迂回路に基づいて第二経路表とｓ，ｉ，ｏのラベルを設定することで、ｕからｄへの迂回路を設定できる。
【００４４】
このプロシージャ"findBackupPath"を図５を用いて説明すると、１−２７行目で変数の初期化を行う。１−５行目では、迂回路を計算するためのグラフＧ’＝（Ｖ’，Ｅ’）を生成する。ｕ＝ｒの場合はＬＰ迂回路を探索するので２行目でＧからリンク（ｒ，ｐ（ｒ））を除いたものをＧ’としている。そうでない場合はＮＰ迂回路を探索するので、４行目でＧからノードｒを除いたものをＧ’としている。６―８行目は迂回路探索時に迂回路の終端となるノード集合Ｓ１、Ｓ２及びＳ３を初期化している。９−２５行目で各ノードｖ∈Ｖ’ に対してdistｕ［ｖ］及びbdistｕ［ｖ］の値を初期化している。いずれもプロシージャ中で一時的に用いられる変数であり、それぞれｕからｖへの距離、及び、（前述の）ｕからｖを経由する迂回路を通ってｄに至る時のｖからｄへの距離を表す。１３−１５行目はＳ１に属するノードｖ∈Ｓ１に対して、１６−１８行目はＳ２に属するノードｖ∈Ｓ２に対して、また１９−２５行目はＳ３に属するノードｖ∈Ｓ３に対して、それぞれbdistｕ［ｖ］の値を与えている。２６行目ではダイクストラのアルゴリズムの始点としてｕを集合Ｑ（ダイクストラのアルゴリズム実行に用いられるノード集合）に入れ、２７行目はｕの距離を０で初期化する。
【００４５】
２８行目以降は迂回路を発見するためのループである。２９−３０行目でＱの中から最小距離のノードｖを取り出し、３１−３２行目では、Ｔｄ上のｕからｖまでの経路上（ｕ、ｖも含む）にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるようなｗが含まれるならば、その中でｖに最も近いものをｗとする。３３−３５行目では、ｗ∈Ｓ１∪Ｓ２の場合に前述の迂回路ｐ（即ちｕからｖまでの発見された経路とｖからｗまでのＴｄに沿った経路を連結したもの）を返し、３６−４２行目ではｗ∈Ｓ３の場合に対応する迂回路ｐを返す。４４−５２行目はダイクストラのアルゴリズムを動作させる部分であり、前述の通りリンク（ｖ,ｗ）に対しては、bdistｄ［ｗ］で表される重みを加算して動作させている。４８行目の２番目の条件はダイクストラのアルゴリズムには存在しない部分であるが、これは、等距離の迂回路が複数あった場合に、できるだけＴｄに沿うような迂回路を選択するための条件である。最後まで迂回路が見つからなければnullを返す（５４行目）。
【００４６】
次に、本アルゴリズムの１４，２２行目（図４）で呼び出される"setBackupNextHops"（次ホップの設定）について説明する。図６に示すプロシージャ"setBackupNextHops"は、"findBackupPath"などで発見された迂回路ｐを第２経路表およびｓ，ｉ，ｏ，ｔ-ラベルとして設定し、ｐの始点ｕから宛先ｄまでＩＰパケットを転送できるようにする処理を行う。このプロシージャは入力として宛先ノードｄ、設定する迂回路ｐ＝（ｕ１，ｕ２，．．．，ｕｎ）、および回避領域の根ノードｒをとる。１行目では迂回路の終端から順に第２経路表を設定するようにループさせ、第２経路表のエントリやラベルを設定する。８−１４行目はｋ＜ｎ−１、即ちｕｋ＋１がｐの終端ノードではない場合の処理、１５−２３行目はｕｋ＋１がｐの終端ノードである場合の処理であり、２−７行目は両方の場合に共通する処理を行う。２−７行目では、両方の場合に共通する処理として、ｔ−ラベルの付加と第二経路表の設定を行う。２−４行目はｕｋの第１経路表のエントリと第２経路表のエントリが等しいとき（つまり、ＩＰパケットがトンネルを通るとき）の処理であり、３行目ではｔ-ラベルを付加し、ｐｈｄｔにこの迂回路を逆向きにたどる（つまり、逆流経路を示す）ための前ホップを記憶しておく。それ以外の場合には、６行目で第２経路表を設定する。以降はｉ，ｏ，ｓ-ラベルの設定である。９−１０行目は、ｕｋでは第１と第２の経路表エントリが異なり、かつｕｋ＋１では同一であるときに、ｕｋにｉ-ラベルを付加し、ｕｋ＋１から第１経路表によるトンネルを用いてＩＰパケット転送するように設定する。１１−１２行目は、ｕｋでは第１と第２の経路表エントリが同一で、かつｕｋ＋１では異なる場合に、ｕｋにｏ-ラベルを付加してＩＰパケットがトンネルから抜けるよう処理をする。１６−１７行目は、ｐの終端が回避領域の外部にあるとき、ｓ-ラベルを付加している。１８−１９行目は、ｐの終端がｔ-ラベルノードで（終端ノードは、第二経路表が設定されていない場合は必ずｔ−ラベルノードである）、ここからトンネルに入るときには、その前のノードにｉ-ラベルを付加する。２０−２１行目は、ｐの終端でトンネルを抜けて別の迂回路に転送する場合には、その前のノードにｏ-ラベルを付加する。
【００４７】
以上が第２経路表と各ラベルを求めるアルゴリズムであり、発見されたどのようなｐに対しても、ＩＰパケットがｐを通るような第２経路表と各ラベルの設定ができる。
＜アルゴリズムに関する理論的結果＞
本アルゴリズムは、全ての双方向ネットワークに対して、任意の１ノード故障に対応できるような第二経路表と３つのラベル（ｓ、ｉ、ｏ−ラベル）を計算できることを保証する。より厳密には、任意のノードｖに対して、もしｖのＮＰ迂回路が存在するならばそのうち一つを設定でき、ＮＰ迂回路が存在しない場合にも、もしｖのＬＰ迂回路が存在するならばそのうち一つを設定できることが保証される。即ち、ノード故障を迂回できることはリンク故障をも迂回できることを考慮すると、本アルゴリズムは迂回可能な全ての１ノード故障、及び１リンク故障に対応可能である。
【００４８】
これよりそのことを証明する。まず、証明にあたり必要な次の定義及び補題を示す。
定義１：経路ｐに対して、任意の２ノードｖ、ｗ∈ｐを選ぶ。もしｐ上でｖがｗの上流に位置し、ｗがＴｄ上でｖの祖先である場合、ｖを始点、ｗを終点とするｐの部分路をスロープ区間と呼ぶ。ｐ上の全てのスロープ区間がＴｄ上にあるとき、ｐを適切経路と呼ぶ。
【００４９】
補題１：ｑをノードｕの迂回路、ｐをｕを始点とするｑの部分路の一つとする。もしｐが適切経路ならば、ｐ上の全てのｔ−ラベルノードｖはＮＰ迂回路を持ち、それはｖの逆流経路である。
証明：もしｐがスロープ区間を持たないならば、補題は満たされる。よって、ｐ上にスロープ区間が存在し、その始点がｖ、終点がｗであるとする（このスロープ区間を以後［ｖ，ｗ］と表す）。ｘをｐ上でｗの直前ノード、ｖ’をｐ上でｖの直前ノードとする。ｐは適切経路なので、そのスロープ区間上の全てのノードはｔ−ラベルノードである。即ち、ｐが設定された時にはこれらのノードの第二経路表は設定されておらず、その迂回路として逆流経路を設定することが可能である。もしｖ’がＴｄ上でｗの子孫であれば、ｐ上の区間［ｖ’，ｗ］は再びスロープ区間であり、上記と同様の議論が可能である。ｕは明らかにｗの子孫ではないので、このようにスロープ区間を広げていくことで、必ずｗの子孫でないｖ’を発見できる。ｖ’がｗの子孫でない場合、ｖ’はＴｄｗの外部にあり、区間［ｖ’，ｘ］内の全ノードに対して、ＮＰ回避領域の外部である。よって、区間［ｖ’，ｘ］内の全てのノードにとって、その逆流経路はＮＰ迂回路となっている。（証明終）
補題１は、設定される迂回路ｐが適切経路であれば、ｐ上の（ｐがＬＰ迂回路であれば始点ノードを除く）全てのノードはＮＰ迂回路を持つことができることを示している。実際に、アルゴリズムCreateBackupTables-NPは迂回路として常に適切経路を計算し設定することで、全ノードに対して（迂回路が存在する場合に限るが）迂回路を保証する。このことを以下の補題と定理により示す。
【００５０】
補題２：プロシージャfindBackupPathは常に適切経路を返す。
証明：プロシージャfindBackupPath内ではｕを始点としてダイクストラの最短路計算アルゴリズムが動作しており、プロシージャにより返される経路は原則として２つの部分に分割できる。つまり、ダイクストラのアルゴリズムにより計算されたｕからｖまでの経路ｐと、ｖからｗ（∈Ｓ１∪Ｓ２∪Ｓ３）までＴｄに沿った経路ｑに分割できる。（例外があるが、これに関しては後述する。また、ｖ＝ｗの場合もあり得る。）ここで、一般にダイクストラのアルゴリズムで用いられるリンクの重みとは異なる重みbdistｄ［］を加えているにもかかわらず、ｐはｕからｖへの重み関数ｆの下での最短路である。なぜなら、bdistｄ［］はｐ上で終端ノードにつながるリンクのみに加算され、かつ、同じ終端ノードにつながる全てのリンクには同じ値が加算されるからである。また、プロシージャfindBackupPathの２９行目と４８行目では、等距離の経路が複数ある場合にはＴｄに沿った経路が優先的に選ばれる仕組みを実現している。従って、ｐは適切経路であり、これにＴｄに沿った最短路ｑを加えた経路ｐ＋ｑも適切経路である。（証明終）
ところで、上記の例外として、findBackupPathはｐ＋ｑにｗの逆流経路を連結した経路を返す場合がある。この場合は、逆流経路上の（終端を除く）ノードが全てｔ−ラベルノードであり、アルゴリズムはＱから取り出したノードｖの祖先にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるノードｗを発見するとすぐに終了するため、ｐ上のｖ以外のどのノードも、逆流経路上のノードをその（Ｔｄ上の）祖先に持たない。よって、ｐ＋ｑに逆流経路をつなげた経路も適切経路である。
【００５１】
定理１：アルゴリズムCreateBackupTable-NPは、任意のノード対（ｓ，ｄ）に対して次の条件を満たすような第二経路表とラベルを計算できる。条件：ｓから宛先ｄへのＮＰ迂回路が存在するならば、ｓはその中で適切経路であるものを迂回路として利用できる。もしＮＰ迂回路が存在せず、ＬＰ迂回路が存在するならば、ｓはその中で適切経路であるものを迂回路として利用できる。
【００５２】
証明：アルゴリズムCreateBackupTable-NPは、Ｔｄの幅優先探索順にノードｖを訪問し、その子ノードｕの迂回路を計算・設定することを繰り返す。迂回路計算の各繰り返し処理において、第二経路表が設定された全てのノードが定理の条件を満たす迂回路を持ち、その迂回路が常に適切経路であることを、数学的帰納法により証明する。
最初に迂回路が計算されるノードｕを考える。ｒをこの時の回避領域の根ノードとする。初回はＳ２∪Ｓ３に含まれるノードは存在しないので、ｕから回避領域Ｔｄｒの外部に到達する迂回路が存在するならば、アルゴリズムがその終端ノードの一つｘ∈Ｓ１を発見できることは明らかである。ここで、発見された経路ｐはｕからｘへのｆの下での最短路の一つであり、２９行目と４８行目の処理で等コスト経路が複数ある場合にはＴｄに沿った経路が優先的に選択されるので、ｕの迂回路ｐは適切経路である。ここで、ｕの迂回路を設定すると、ｐ上のｔ−ラベルノードと終端ノードを除く全てのノードの迂回路も設定されることになる。これらのノードはＴｄ上でｒの子孫であるため、ｘはこれらのＮＰ回避領域の外部にある。即ち、ｐは第二経路表が設定された全てのノードに対してＮＰ迂回路である。
【００５３】
次にｋ回目の繰り返しまで条件が満たされたと仮定し、ｋ＋１回目の処理により計算・設定された迂回路も条件が満たされることを示す。もし、始点ノードｕからＴｄｒの外部に至る経路が存在するならば、アルゴリズムは必ずｗ∈Ｓ１∪Ｓ２∪Ｓ３を発見できる。もし
ｗ∈Ｓ１が発見されたならば、上記の議論から条件は満たされる。
【００５４】
ｗ∈Ｓ２が発見された場合、ｐを発見されたｕからｖまでの経路とし、ｐ’をｖからｗまでのＴｄに沿った経路とし、ｑをｗの（既に設定された）迂回路とする。ｑは仮定より適切経路であり、ｖ∈Ｄｄ（ｒ）よりｑはｒを含まない。また、アルゴリズムは回避領域が広い順番に（つまり回避領域の根が宛先ｄに近い順番に）迂回路を計算するため、ｑはＴｄｒの外部に到達できる。よって、経路ｐ＋ｐ’＋ｑはｕの迂回路である。一方、補題２より、このｕの迂回路は２本の適切経路ｐ＋ｐ’とｑの連結である。アルゴリズムはＱからノードを取り出し、その祖先にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるノードｗを発見するとすぐに迂回路を決定する。よって、全てのｘ１∈（ｐ＋ｐ’）、ｘ２∈ｑの組に対して、ｘ１がｘ２のＴｄ上の子孫であれば、ｐ＋ｐ’＋ｑ上の区間［ｘ１，ｘ２］はＴｄに含まれる。即ち経路ｐ＋ｐ’＋ｑは適切経路である。また、このとき第二経路表が設定された全てのノードは、前述の議論によりＮＰ迂回路を持つ。
【００５５】
最後に、ｗ∈Ｓ３である場合は、ｐを発見されたｕからｖまでの経路とし、ｐ’をｖからｗまでのＴｄに沿った経路とし、ｑ１をｗのトンネル迂回路とし、ｑ２をｗの逆流経路とする。もしｑ１がｒを含まない場合、上記ｗ∈Ｓ２の場合と同様の議論により、ｐ＋ｐ’＋ｑ１はＴｄｒの外部に到達できる迂回路であり、適切経路である。一方、ｑ１がｒを含む場合、ｑ１が適切経路であることからｗとｒはいずれもｗのトンネル区間内にある。よって、補題１より、ｗの逆流経路はＴｄｒの外部に到達でき、ｐ＋ｐ’＋ｑ２はｕの迂回路である。また、補題２より、ｐ＋ｐ’＋ｑ２は適切経路である。また、このとき第二経路表が設定された全てのノードは、前述の議論によりＮＰ迂回路を持つ。
【００５６】
以上により、ｋ＋１回目の繰り返し処理で第二経路表が設定される（ｕを除く）全てのノードは定理の条件を満たす迂回路を持つ。（証明終）
＜動作＞
次にノードｕ２における、ＩＰパケット受信からＩＰパケット転送までの処理の流れについて図７を用いて説明する。なお、図１で示したノードｕ２以外の各ノード（ノードｕ１，ｕ３，ｕ４，ｕ５，ｗ１，ｗ２）も同様な動作を行う。
【００５７】
まず、受信部１４がＩＰパケットを受信すると（Ｓ１０）、状態制御部２２は受信したＩＰパケットのヘッダに含まれる状態を読み取る（Ｓ１１）。
状態が０であり（Ｓ１２：Ｙｅｓ）、故障検出部２０が第１経路表４２の次ホップの故障を検出していなければ（Ｓ１３：Ｎｏ）、転送部１６は第１経路表４２の次ホップにＩＰパケットを転送する（Ｓ１４）。このように、第１経路表４２の次ホップに故障がない限りは、状態が０のままでこの第１経路表４２の次ホップに転送されることとなる。
【００５８】
故障検出部２０が次ホップの故障を検出を検出していれば（Ｓ１３：Ｙｅｓ）、転送部１６は第２経路表４４の次ホップにＩＰパケットを転送する（Ｓ１８）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｓ-ラベルがtrueでなければ（Ｓ１５：Ｎｏ、Ｓ１６）状態０から状態１へと書き換え（Ｓ１６）、ｓ-ラベルtrueであれば（Ｓ１５：Ｙｅｓ）状態０から状態３へと書き換える（Ｓ１７）。
【００５９】
状態が０でなく１であれば（Ｓ１２：Ｎｏ、Ｓ２１：Ｙｅｓ）、転送部１６は第２経路表４４の次ホップにＩＰパケット転送する（Ｓ２６）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｉ-ラベルtrueであれば状態１から状態２へと書き換え（Ｓ２２：Ｙｅｓ，Ｓ２３）、ｉ-ラベルtrueでなくｓ-ラベルtrueであれば状態１から状態３へと書き換える（Ｓ２２：Ｎｏ，Ｓ２４：Ｙｅｓ，Ｓ２５）。
【００６０】
状態が１でなく２であれば（Ｓ２１：Ｎｏ、Ｓ３１：Ｙｅｓ）、転送部１６は第１経路表４２の次ホップにＩＰパケット転送する（Ｓ３４）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｏ-ラベルtrueであれば状態２から状態１へと書き換える（Ｓ３２：Ｙｅｓ，Ｓ３３）。
状態が２でなく３であれば（Ｓ３１：Ｎｏ、Ｓ４１）、転送部１６は第１経路表４２の次ホップにＩＰパケット転送する（Ｓ４２）。
【００６１】
図１のネットワーク１において、第１および第２経路表、各ラベルについて、上述のアルゴリズムに従って計算した結果を図８に示す。
図８においては、各ノードｕ１〜ｕ５，ｗ１，ｗ２の傍らに、第１経路表および第２経路表、さらに各ラベルがtrue／falseを示している。例えば、ノードｕ２は、第１経路表に示される次ホップがｕ１であり、第２経路表に示される次ホップがｕ３であり、ｉラベルがtrue、ｏ-ラベル，ｓ-ラベルはfalseとなっている。
【００６２】
例えば、ノードｕ１が宛先ｄのＩＰパケットを受信した場合で、ノードｕ５が故障した際の各ノードの動作については、次の（１）〜（６）の通りである（図９参照）。
（１）ノードｕ１は、状態０のＩＰパケットを受信すると（Ｓ１２：Ｙｅｓ）、第１経路表の次ホップｕ５の故障を検出し（Ｓ１３：Ｙｅｓ）、状態を０から１へと書き換え（Ｓ１６）、第２経路表に示される次ホップのｕ２へと転送する（Ｓ１８）。
【００６３】
（２）ノードｕ２は、状態１のＩＰパケットを受信すると（Ｓ２１：Ｙｅｓ）、ｉ-ラベルtrueなので状態を１から２へと書き換え（Ｓ２２：Ｙｅｓ，Ｓ２３）、第２経路表に示される次ホップのｕ３へと転送する（Ｓ２６）。
（３）ノードｕ３は、状態２のＩＰパケットを受信すると（Ｓ３１：Ｙｅｓ）、ｏ-ラベルtrueなので状態を２から１へと書き換え（Ｓ３２：Ｙｅｓ，Ｓ３３）、第１経路表の次ホップｕ４へと転送する（Ｓ３４）。
【００６４】
（４）ノードｕ４は、状態１のＩＰパケットを受信すると（Ｓ２１：Ｙｅｓ）、ｓ-ラベルtrueなので状態を１から３へと書き換え（Ｓ２２：Ｎｏ，Ｓ２４：Ｙｅｓ，Ｓ２５）、第２経路表の次ホップｗ１へと転送する（Ｓ２６）。
（５）ノードｗ１は、状態３のＩＰパケットを受信すると（Ｓ４１）、第１経路表の次ホップｗ２へと転送する（Ｓ４２）。
【００６５】
（６）ノードｗ２は、状態３のＩＰパケットを受信すると（Ｓ４１）、第１経路表の次ホップｄへと転送する（Ｓ４２）。
このようにノードｕ５が故障した際においても、ノードｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄという迂回路を通ってＩＰパケットを無事宛先ノードｄへと届けることができる。
【００６６】
以上説明したように、本実施の形態によれば、ＩＰパケットの宛先に関連付けられたｓ，ｉ，ｏの各ラベルを利用してＩＰパケットの状態を書き換えて、第１経路表と第２経路表のいずれの表を使うべきかを多様に設定することが可能となる。特に、ノード故障の検出後の迂回において、一旦迂回路に入ったにも関わらず（ｕ１→ｕ２→ｕ３）、途中で第１経路表を使って最短路を通るトンネルに入り（ｕ３→ｕ４）、トンネルを出た後は第２経路表を使い（ｕ４→ｗ１）、その後、また第１経路表を使う（ｗ１→ｗ２→ｄ）というように柔軟に適切な迂回路を設定することができる。
【００６７】
このように第１経路表と第２経路表というわずか２枚の経路表によりノードプロテクションを実現することができる。また、４つの状態はＩＰパケットヘッダのＴＯＳフィールドに2ビットという軽い情報量で入れ込むので、ネットワークへの影響も軽微である。
＜補足＞
以上、本発明の実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連または付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であってもよい。
【００６８】
１．実施の形態においては、ノードｕ５が故障した際における例（図８）についてのみ説明したが、実施の形態によれば、ｕ１〜ｕ５，ｗ１，ｗ２のうちの任意のノードが宛先ｄのＩＰパケットを受信した際に、他のノードが故障していたとしても、適切に迂回路を保証することができる、つまりノードプロテクションを実現することができる。
また、任意のリンクが故障していたとしても適切に迂回路を保証することができる、つまりリンクプロテクションを実現することができる。
【００６９】
２．図１（図８）とは、異なる形態のネットワークに実施の形態を適用した場合の例について変形例として以下説明する。図１０は変形例に係るネットワーク構成などを示す図である。図１０（ａ）はネットワーク構成（トポロジ）を示し、図１０（ｂ）は第１経路表とｏ-ラベル、図１０（ｃ）は第２経路表とｉ-ラベル，ｓ-ラベルを示す。
図１０のネットワークにおいても実施の形態の同様にノードプロテクションを実現できる。例えば、宛先がノード６であるＩＰパケットをノード２が受信した場合で、ノード３が故障している際には、
（１）ノード２は、ノード３の故障を検出すると、ＩＰパケットの状態を０から１へと書き換え、第２経路表に示される次ホップのノード７へとＩＰパケットを転送する。
【００７０】
（２）ノード７は、ＩＰパケットの状態が１であるため第２経路表に示される次ホップのノード９へとＩＰパケットを転送する。また、ｉ-ラベルtrueなので転送前に状態を１から２へと書き換える。
（３）ノード９は、ＩＰパケットの状態が２であるため第１経路表に示される次ホップのノード４へとＩＰパケットを転送する。また、ｏ-ラベルtrueなので転送前に状態を２から１へと書き換える。
【００７１】
（４）ノード４は、ＩＰパケットの状態が１であるため第２経路表に示される次ホップのノード５へとＩＰパケットを転送する。また、ｓ-ラベルtrueなので転送前に状態を１から３へと書き換える。
（５）ノード５は、ＩＰパケットの状態が３であるため第１経路表に示される次ホップのノード８へとＩＰパケットを転送する。
【００７２】
（６）ノード８は、ＩＰパケットの状態が３であるため第１経路表に示される次ホップのノード６へとＩＰパケットを転送する。
このように本変形例においても、ノードプロテクションを行うことができる。
３．迂回路の途中で第１経路表を使う方法としては、カプセル化の技術や、ＭＰＬＳ（Multi Protocol Label Switching）やＡＴＭ（Asynchronous Transfer Mode）などを含むラベルスイッチング技術と組み合わせることもできる。
【００７３】
カプセル化については、RFC2003に規定されているIPパケット中にIPパケットをカプセル化するトンネリング技術が代表的あるが、RFC1701に規定されているような異なるプロトコル間でのトンネリングや、RFC3931に規定されているようなレイヤ２フレーム(Ethernet（登録商標）など)をIPの中にカプセル化する技術などを適宜用いることができる。
カプセル化を利用した場合の具体例を図１１に示す。なお、図１１においても図８、図１４などと同様に、第１経路表，第２経路表の次ホップへの経路をそれぞれ「第１経路」，「第２経路」と矢印で示している。
【００７４】
ノードｕ１のノードが故障した際には、ｕ１→ｕ２→ｕ３→ｕ４→ｕ５→ｕ６→ｕ７→ｄという経路でパケットが転送される。実施の形態の図８，図９などと挙動が異なるのは基本的にノードｕ３からノードｕ５に至る間だけであるので、この間の詳細のみを以下説明する。
（１）ノードｕ３においてＩＰパケット（状態１，宛先ｄ）をペイロード部分に入れてヘッダ部分に宛先ｕ５、状態０（デフォルトの状態）を内包させた入れたパケットを新たに作成し（カプセル化）、第１経路のノードｕ４へと送る。カプセル化されたパケットには、ＩＰパケット（状態１，宛先ｄ）が内包されることとなる。
【００７５】
（２）ノードｕ４は、受信したＩＰパケットの状態が０であるため、第１経路表に示されるノードｕ５へとＩＰパケットを送る。
（３）ノードｕ５は、受信したＩＰパケットの宛先が自ノードであるため、パケットのカプセル化を解除して、中身（ペイロード部分）からＩＰパケット（状態１，宛先ｄ）を取り出す。そして、取り出したＩＰパケット（状態１，宛先ｄ）は、状態１であるため、第２経路表のノードｕ６へと送る。
【００７６】
なお、カプセル化を行った「ｕ３」は、ｉ-ラベルが付加されたノードｕ２からみて第１経路にあるノード（状態２のパケットを最初に受信するノード）であり、そして、カプセル化したパケットの宛先「ｕ５」はｏ-ラベルが付加されたノードｕ４からみて第１経路にあるノードである。このようにカプセル化の開始ノードと宛先ノードとを設定することで迂回路中に第１経路（最短路）を通るトンネル区間（ｕ３からｕ５までの区間）を設定することができる。
【００７７】
なお、カプセル化の開始ノードを「ｕ３」に代えて、例えば「ｕ２」など適宜変更することができる。
次に、ラベルスイッチング技術と組み合わせた一例としてＭＰＬＳを用いて説明する。ＭＰＬＳはパケットにＭＰＬＳラベルを付加することで、ＭＰＬＳラベルが付加されているパケットはそのＭＰＬＳラベルに対応した既設定経路を用いて転送する技術であり、ＭＰＬＳラベルは、経路制御中に付加したり削除したり操作が可能である。ＭＰＬＳは、従来の最短経路による経路制御よりも柔軟な経路設定が可能であるため、負荷分散等にも利用されている。
【００７８】
ＭＰＬＳを利用した場合の具体例を図１２に示す。本例もノードｕ３からノードｕ５に至る間の詳細のみを以下説明する。
（１）ノードｕ３においてＩＰパケット（状態１，宛先ｄ）にＭＰＬＳラベルであるラベル"7"を付加する。ＭＰＬＳのネットワーク内では、ＩＰヘッダの宛先ではなくラベルのみに基づいて転送先が決定される。このため、ラベル"7"に対応したＬＳＰ（Label Switch Path）を用いてパケットが転送される。ここで、ラベル"7"は終点（宛先）がノードｕ５でｕ３→ｕ４→ｕ５と第１経路（最短路）を通る経路に設定されているものとする。
【００７９】
（２）ノードｕ４は、受信したＩＰパケットに付加されたラベル"7"に従って、ノードｕ５へとＩＰパケットを送る。
（３）ノードｕ４は、受信したＩＰパケットに付加されたラベル"7"が自ノードを宛先としているので、このＩＰパケットからラベル"7”を外す。そして、ラベル"7”を外したＩＰパケットは状態１であるため、第２経路表に示されるノードｕ６へとＩＰパケットを送る。
【００８０】
なお、ラベル"7"を付加した「ｕ３」は、ｉ-ラベルが付加されたノードｕ２からみて第１経路にあるノード（状態２のパケットを最初に受信するノード）であり、そして、ラベル"7"に従う経路は第１経路（最短路）を通り経路の終点は「ｕ５」となっている。ＭＰＬＳを利用した場合も上のカプセル化の場合と同様、迂回路中に第１経路（最短路）を通るトンネル区間（ｕ３からｕ５までの区間）を設定することができる。
【００８１】
また、図１２では、ラベル"7"は第１経路（最短路）を通るように設定されているとして説明したが、効率を考慮すると最短路であることが望ましいが、これに限らず第２経路（迂回路）と異なる経路であればよく、必ずしも最短路である必要はない。
４．実施の形態では、ＯＳＰＦ（Open Shortest Path First）のルーティング・プロトコルに適用した例について説明している。ＯＳＰＦは、中規模のネットワークにおいて、非常に効率的な運用を可能にできるという利点がある。
【００８２】
実施の形態で説明した手法は、ＯＳＰＦだけではなくＩＳ−ＩＳ（Intermediate System to Intermediate System）のようなリンク状態型ルーティングにも適用することができる。
さらには、スタティック・ルーティング、つまり各ノードに第１および第２経路表や各ラベルなどを手動で設定するとしてもよい。
【００８３】
５．実施の形態では、各ノードの計算部３０において個別に表やラベルの計算をするとしてが、これに代えて、上記計算は処理能力に優れたサーバで行い、各ノードは計算結果をサーバから受け取って、表やラベルを設定するとしてもよい。
６．実施の形態では、最短路計算アルゴリズムの例として、ダイクストラを例に挙げたが、これに限られず、例えば、ワーシャル−フロイド法など他の最短路計算アルゴリズムを適用することができる。
【００８４】
７．実施の形態では、第１経路表における次ホップは宛先ノードｄに至るための最短経路上に存在する隣接ノード（最短ノード）であり、第２経路表における次ホップは宛先ノードｄに至るための迂回の経路上に存在する隣接ノード（迂回ノード）であるとして説明したが、第１経路表の次ホップの導出方法はこれに限られない。例えば、効率を重視しない（あるいは無視できる）ネットワーク設計であれば上記最短ノードではないノードを第１経路表に設定するとしても構わない。
【００８５】
８．実施の形態においては、故障検出部２０の故障を検出した場合に状態を状態０から状態１へと書き換えるとして説明したが、このような故障検出に限らず例えば輻輳を検出するなど第１経路表の次ホップへの転送が円滑に行えないことを条件としてもよい。また、隣接ノードとの間でやりとりされるメッセージやリンクを流れる電流、光信号などを定期的な検出対象として、検出結果に基づいて状態０から状態１への書き換えを行うとしてもよい。
【００８６】
９．図７のフローチャートにおいて、第２経路表の次ホップに転送しようとしたとき、第２経路表の計算が未完了であるなど第２経路表の次ホップが存在しない場合には、状態３に書き換えて第１経路表の次ホップに転送するとしてもよい。
１０．本実施の形態は、無線アドホックネットワーク、無線メッシュネットワーク、センサーネットワーク、その他経路制御を必要とする種々のネットワークに適用可能である。
【００８７】
１１．実施の形態において説明した第１および第２経路表、さらには各ラベルを計算するアルゴリズムについては、あくまでも一例でありこれに限定されるものではない。
１２．実施の形態では、ＩＰｖ４のＩＰパケットのＴＯＳフィールドに状態を含ませるとして説明したが、ＩＰｖ６においても例えばヘッダ部分の拡張されたフィールドなどに状態を含ませることで実施することができる。
【００８８】
１３．実施の形態では、ＩＰパケットを例に挙げて説明したが、本発明は、ＩＰパケットのみの適用には限定されず、経路表を用いてパケットを転送するスキームのすべてに適用可能である。ＩＰ以外にも、例えばＩＰＸ（Internetwork Packet eXchange）といったプロトコルにも適用できる。また、その他無線通信で独自仕様の通信プロトコルに適用できる。
【００８９】
１４．実施の形態では、ｓ-ラベルのノードを過ぎると直ちに迂回後の状態３に変更しているので（図９，図７：Ｓ２４：Ｙｅｓ，Ｓ２５）、迂回後のさらなる迂回はできない構成であったが、もっともこれに限らず、状態３へ変更する代わりにデフォルトの状態０へと変更することで、複数回の迂回を許容するようにしてもよい。
具体的には、図１３（ａ）に示すように、ＩＰパケットのヘッダ部分に迂回回数を格納する領域を設定しておく。
【００９０】
そして、図１３（ｂ）に示すように、ｓ-ラベルがtrueであれば（Ｓ２４：Ｙｅｓ）、ＩＰパケットに格納された迂回領域を参照して、迂回回数が例えば３以下であれば（Ｓ５１：Ｙｅｓ）、迂回回数をインクリメントし（Ｓ５２）、状態を状態１から状態０へと変更する（Ｓ５３）。迂回回数が３以下でなければ（Ｓ５１：Ｎｏ）、状態を状態１から状態３へと変更する（Ｓ２５）。
【００９１】
なお、図１３（ｂ）においては、図７と同様なステップに同じステップ番号を付している。
このようにすることで、ＩＰパケットに３回までの迂回を許容することができ、パケット損失の低減に寄与できる。
【産業上の利用可能性】
【００９２】
本発明に係る経路制御装置はルータなどのネットワーク機器として有用である。
【符号の説明】
【００９３】
１ ネットワーク
１４ 受信部
１６ 転送部
２０ 故障検出部
２２ 状態制御部
３０ 計算部
３２ 第１経路表計算部
３４ 第２経路表計算部
３６ ラベル計算部
４２ 第１経路表
４４ 第２経路表
４６ ラベル表
ｕ１〜ｕ５，ｗ１，ｗ２ ノード（ルータ）
ｄ 宛先ノード（宛先ルータ）
【技術分野】
【０００１】
本発明は、ネットワークの経路上において故障などの異常状態が発生した場合に、迂回路を設定する経路制御装置に関する。
【背景技術】
【０００２】
従来から、ルータなどの経路制御装置はネットワーク上の宛先とこの宛先に至るための次の転送先との対応を示す経路表（ルーティング・テーブル）を備えており、やってきたＩＰパケットの宛先を上記ルーティング・テーブルと照合して次の転送先を決定することが行われている。そして、次の転送先のルータへの経路上に故障などが発生して転送が行えないことがあるため、予備の経路表を予め用意しておく技術が知られている。
【０００３】
経路上の故障には大別して２種類ある。リンクの故障（link failure）とノードの故障（node failure）である。
そして、宛先への経路上に存する任意の１リンクが故障したとしても、そのリンクの故障に対して適切な迂回路を設定することを、「リンクプロテクション」という。また、任意の１ノードが故障したとしても、そのノードの故障に対しても適切な迂回路を設定することを「ノードプロテクション」という。
【０００４】
このリンクプロテクションやノードプロテクションを実現するためのひとつの方策として、経路表の枚数を増やして対応する技術が知られている（非特許文献１〜５参照）。例えば、非特許文献１では、各ノードにおいて、そのノードが持つインターフェイス（ポート）毎の経路表を用意しておくことで、リンクプロテクションの実現を試みている。
また、非特許文献２では、同様の手法を用いてリンクプロテクションを実現する経路表の計算方法を提案している。
【０００５】
また、非特許文献４では、リンクプロテクションやノードプロテクションを保証するために、幾枚かの経路表を要するとしており、ネットワークの規模などにも依存するものの一般に3枚から5枚の追加テーブルが必要としている。
さらに、非特許文献５では、様々な故障に対応するための必要な追加テーブルの枚数は2枚から3枚としており、上記非特許文献４よりは少ない枚数であるが、一般的なケースにおいて何枚の経路表を要するかに関しては開示されていない。
【０００６】
その一方で、経路表をむやみに増やすと各ノードの処理負荷が重くなることがある。このため、非特許文献６では、パケットヘッダに埋め込んだ状態を迂回に利用することで、経路表の枚数を増加を回避しつつ適切な迂回路の設定を試みている。
非特許文献６に開示された技術について説明する。図１４に示すように、ネットワーク１００は、ノードｕ１〜ｕ５，ｗ１，ｗ２，ｄから構成される。
【０００７】
各ノードには、宛先であるノードｄとノードｄに至るための次の転送先のノード（次ホップ）を示す経路表、すなわち通常用の第１経路表（1st）と予備用の第２経路表（2nd）が備えられている。なお、図１４において、第１経路表，第２経路表の次ホップへの経路をそれぞれ「第１経路」，「第２経路」と矢印で示している。
ここで図１４におけるネットワークのルールは、次の通りである。
【０００８】
（ルール１）ＩＰパケットには、第１と第２経路表のいずれを使うべきかを示す状態ラベルが付加されており、状態０が第１経路表、状態１が第２経路表を使うべきことを示す。
（ルール２）第１経路表の次ホップへにつながるリンクの故障を検出するなどして、ＩＰパケットを転送できないノードは、ＩＰパケットをデフォルトの状態０から状態１へと変更し、第２経路表の次ホップに転送する。
【０００９】
（ルール３）ｓフラグが関連付けられているノードは、状態１のＩＰパケットを受信したときに、状態１から状態０へと状態を変更する。状態０への変更によりこのノード以降のノードは第１経路表を使うこととなる。
なお、非特許文献６では、ＩＰパケットのループ防止のためにさらに状態を変更する仕組みが紹介されているが本論と密接には関係しないので説明を省略する。
【００１０】
このルール下における具体的な動作例を説明すると、例えば、ノードｕ１が宛先ｄのＩＰパケットを受信した場合でリンクの故障を検出をしないときには、ノードｕ１は第１経路表の次ホップｕ５へとＩＰパケットを転送し、ノードｕ５もノードｕ５の第１経路表の次ホップｄへ転送とする。つまりＩＰパケットは、ｕ１→ｕ５→ｄと転送されることとなる。
【００１１】
また、図１５に示すように、同じくノードｕ１が宛先ｄのＩＰパケットを受信した場合で、ｕ５とｄとの間のリンク故障を検出すると、ｕ１→ｕ５→ｕ４→ｗ１→ｗ２→ｄという流れになる。
すなわち、
（１）ノードｕ１：第１経路表の次ホップｕ５へとＩＰパケットを転送する
（２）ノードｕ５：ｕ５−ｄ間のリンク故障を検出したのでＩＰパケットの状態を状態０から状態１へと変更、そして第１経路表ではなく第２経路表の次ホップｕ４へとＩＰパケットを転送する
（３）ノードｕ４：ＩＰパケットの状態は状態１であるので第２経路表の次ホップｗ１へとＩＰパケットを転送。ただし、ｓフラグが関連付けられているので、転送前に状態１から状態０へと変更しておく
（４）ノードｗ１：ＩＰパケットの状態は状態０であるので第１経路表の次ホップｗ２へとＩＰパケットを転送する
（５）ノードｗ２：ＩＰパケットの状態は状態０であるので第１経路表の次ホップｄへとＩＰパケットを転送する
、という流れとなる。
【００１２】
このように、非特許文献６によると、宛先のノードへの経路上に存する任意の１リンクが故障したとしても、そのリンクの故障に対して適切な迂回路を設定できる（リンクプロテクション）。また、予め計算しておいた経路表を利用するので、故障検出後に瞬時に迂回路を設定することができるとしている。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】S. Lee, Y. Yu, S. Nelakuditi, Z.L. Zhang, and C-N. Chuah,"Proactive vs. Reactive Approaches to Failure Resilient Routing," In Proceings of IEEE INFOCOM '04, Mar.2004.
【非特許文献２】Z. Zhong, S. Nelakuditi, Y. Yu, S. Lee,J. Wang,and C.N. Chuah,"Failure Inferencing Based Fast Rerouting for Handling Transient Link and Node Failures," In Proceings of IEEE Global Internet, Mar.2005.
【非特許文献３】J. Wang and S. Nelakuditi,"IP Fast Reroute with Failure Inferencing," In Proceedings of SIGCOMM workshop (INM) 2007,pp.268-273,2007.
【非特許文献４】A. Kvalbein, A.F. Hansen, T.Cicic, S. Gjessing, and O. Lysne, "Multiple routing configurations for fast IP network recovery," IEEE/ACM Transactions on Networking, Vol.17, Issue.2,pp.473-486, 2009.
【非特許文献５】T.Cicic, A.F. Hansen,A. Kvalbein, M, Hartmann, R. Martin and M. Menth,"Relaxed multiple routing configurations for IP fast reroute," In Proceings of NOMS2008,pp.457-464, 2008.
【非特許文献６】Takuya Yoshihiro，"A Single Backup-Table Rerouting Scheme for Fast Failure Protection in OSPF"，IEICE Transactions on Communications, Vol. E91-B, No. 9, pp. 2838-2847, 2008.9. (IEICE/IEEE Joint Special Section on Autonomous Decentralized Systems Theories and Application Deployments)
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、ネットワーク技術においては、上記リンクプロテクションも重要であるが、ノード故障の発生率も無視できないほどに高い。このため、ノードプロテクションをも実現することが重要課題となっている。
しかしながら、このノードプロテクションに対しては、上記した非特許文献６の技術では有効に機能しないことがある。
【００１５】
具体的には図１６に示すように、ネットワーク１０２においては、ノードｕ１が宛先ｄであるＩＰパケットを受信した場合で、ノードｕ５が故障しているときには、ＩＰパケットは、ｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄと転送されるので迂回できる。もっとも、ノードｕ３は第１経路表の次ホップおよび第２経路表の次ホップが同じｕ４になっている。このため、ノードｕ３が宛先ｄのＩＰパケットを受信した場合にｕ４との間のリンク故障を検出すると、ノードｕ３は次の適切な転送先を決定することができず迂回できず（図１７参照）、ＩＰパケット損失を招くこととなる。
【００１６】
これに対しては、リンク故障やノード故障などに応じて経路表を用意するなど経路表の枚数を増やすことで対応することも考えられるが、上述のように経路表の枚数の増加は各ノードにおける処理負荷の増大などを招くのでの避けたい。
本発明はこのような背景の下になされたものであって、比較的少ない枚数の経路表を用いて、ノードやリンクの故障時に適切に迂回するネットワークを構成できる経路制御装置を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記ラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記ラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、前記第１ノードへと前記パケットを転送して、前記ラベル情報が第３ラベルの付加を示していれば転送前に前記状態２から前記状態１へと書き換え、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、を備えることを特徴とする。
【００１８】
また、本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と転送先の決定に係る状態を示す情報とを格納するパケットを受信し、自ノード宛のカプセル化されたパケットを受信すると、カプセル化の解除後のパケットを、受信したパケットとして扱う受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、当該パケットを、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示すノードからみて第１ノードであるノードを宛先として状態が状態０であるパケットに内包させるようカプセル化し、カプセル化したパケットを前記第１ノードへと前記パケットを転送し、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、を備えることを特徴とする。
【００１９】
また、本発明に係る経路制御装置は、ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、を記憶する記憶部と、前記受信部により受信されたパケットに格納された情報に示される状態が、状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、受信されたパケットに前記第１経路表に対応する経路であることを識別するＭＰＬＳラベルを付加した後、当該ＭＰＬＳラベルにより識別されるノードへと転送し、状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備えることを特徴としている。
【００２０】
また、本発明に係る経路制御システムにおける方法は、ネットワークを構成する複数のノードから構成される経路制御システムにおける方法であって、各ノードにおいて、宛先ノードに至る第１経路と、前記宛先ノードに至り第１経路とは異なる迂回路である第２経路とを記憶する記憶ステップと、各ノードにおいて、第１経路を用いたパケットの転送が可能でないならば、パケットに迂回途中である旨を示す情報を付加した後で第２経路を用いてパケットを転送する迂回開始ステップと、各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信すると、第２経路を用いてパケットを転送する迂回中ステップと、各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信したにも関わらず、自ノードに関して宛先ノードに至るための経路に係る所定の条件を満足していれば、前記迂回中ステップで用いる第２経路に代えて、第１経路表を用いてパケットを転送する迂回中トンネルステップと、を備えることを特徴としている。
【発明の効果】
【００２１】
本発明に係る経路制御装置によれば、第１から第３ラベルにより状態０から状態４を状態を書き換えることにより、第１経路表か第２経路表のどちらを用いて転送先とするかを柔軟に決定することができ、ノードやリンクの故障時に適切に迂回路を設定することができる。
【図面の簡単な説明】
【００２２】
【図１】ネットワークの概要を示す図
【図２】ノードｕ２の機能ブロック図
【図３】アルゴリズム"CreateBackupTable-NP"に係る変数の定義を示す図
【図４】アルゴリズム"CreateBackupTable-NP"を示す図
【図５】プロシージャ"findBackupPath"を示す図
【図６】プロシージャ"setBackupNextHops"を示す図
【図７】ＩＰパケット受信に係る処理の流れを示すフローチャート
【図８】各ノードにおける第１および第２経路表、さらに各ラベルのtrue／falseを示す図
【図９】ノードｕ５が故障した際の各ノードにおける処理の流れを示すシーケンス図
【図１０】変形例に係るネットワーク構成などを示す図
【図１１】カプセル化を利用した変形例に係るネットワーク構成などを示す図
【図１２】ＭＰＬＳを利用した変形例に係るネットワーク構成などを示す図
【図１３】（ａ）ＩＰパケットのヘッダ部分の内容を示す図、（ｂ）迂回後（状態３）への変更に関するフローチャート
【図１４】非特許文献６にならったネットワーク構成を示す図
【図１５】図１４のネットワークにおいて、ｕ５−ｄ間のリンク故障を示す図
【図１６】非特許文献６でノードプロテクションを行おうとしたときのネットワーク構成を示す図
【図１７】図１６のネットワークにおいて、ｕ３−ｕ４間のリンク故障を示す図
【発明を実施するための形態】
【００２３】
以下、図面を参照しながら実施の形態について説明する。
＜構成＞
図１に示すように、ネットワーク１は８個のノードｕ１〜ｕ５，ｗ１，ｗ２，ｄから構成される。各ノードはルータから構成され、ネットワーク層においてＩＰプロトコルに従って通信を行う。各ノードはＯＳＰＦ（Open Shortest Path First）のルーティング・プロトコルに従って動作するものとする。
【００２４】
また、ネットワークを流れるＩＰパケットのヘッダ部分には、宛先ＩＰアドレスとＴＯＳ（Type Of Service）フィールドが含まれており、このＴＯＳは状態（状態０から状態３までの４種類がある。）の格納領域として用いられている。
図２にノードｕ２の機能ブロック図を示す。各ノードは基本的に同様な構成であるのでノードｕ２だけを代表させて説明する。
【００２５】
ノードｕ２は、インターフェイス部１０、トポロジ部１２、受信部１４、転送部１６、転送先決定部１８、故障検出部２０、状態制御部２２、各部を制御する制御部２４、計算部３０、記憶部４０を備える。
インターフェイス部１０は、他のノードと接続するための回線インターフェイス（ポート）から構成されており、他のノードとの間でのデータ授受を実現する。
【００２６】
トポロジ部１２は、他のノードに対して、自ノードに接続されたノード（隣接ノード）のＩＤやインターフェイスのコストを含むLSA（Link State Advertisement）と呼ばれるトポロジ情報を送信する。また他のノードから集めたトポロジ情報に基づいてトポロジ・マップを作成する。
受信部１４は、インターフェイス部１０を介してＩＰパケットなどを受信する。
【００２７】
転送部１６は、インターフェイス部１０を介してＩＰパケットなどを、転送先決定部１８に決定された転送先へと転送する。
故障検出部２０は、定期的に隣接ノードとの間でやりとりされるメッセ−ジなどを利用して隣接ノードの故障を検出する。
状態制御部２２は、受信部１４が受信したＩＰパケットのヘッダ部分のＴＯＳ（Type Of Service）フィールド含まれる状態の読み取りや書き換えを行う。この書き換えは、故障検出部２０の故障検出の有無や記憶部４０内のラベル表４６に基づいて行われる。
【００２８】
状態には、最短路転送中であることを示す「状態０」、迂回路転送中であることを示す「状態１」、トンネル転送中であることを示す「状態２」、迂回後であることを示す「状態３」の４種類がある。各状態の機能や書き換え条件については後述する。
計算部３０は、第１経路表計算部３２、第２経路表計算部３４、ラベル計算部３６から構成される。計算部３０のアルゴリズムについては後述する。この計算部３０の計算結果は、記憶部４０内に第１経路表４２、第２経路表４４、ラベル表４６として設定され記憶される。
【００２９】
第１経路表４２は、通常用（プライマリー）の経路表であり、宛先ノードを示す「宛先」４２ａと宛先ノードに至るための「次ホップ」４２ｂとを対応付けた表である。図２中では、「宛先」がノードｄについてのみ記述して他の宛先（ノードｕ１，ｕ３，ｕ４，ｕ５，ｗ１，ｗ２）に関しては省略している。第２経路表４４は、予備用（バックアップ）の経路表であり、第１経路表４２同様、宛先ノードを示す「宛先」４４ａと宛先ノードに至るための「次ホップ」４４ｂとを対応付けた表である。
【００３０】
ラベル表４６は、「宛先」４６ａと、３つのラベル「ｓ」４６ｂ，「ｉ」４６ｃ，「ｏ」４６ｄの各ラベルについてtrue/falseを示す表である。図２のラベル表４６の例では、宛先ノードｄに関してｉ-ラベルがtrueで、ｓ-ラベル，ｏ-ラベルがfalseあることを示している。
＜アルゴリズム＞
次に、計算部３０の処理内容を定めるアルゴリズムについて説明する。
【００３１】
まず、第１経路表４２は、ＯＳＰＦにおいて一般的に用いられている手法により計算を行う。つまり、トポロジ部１２において作成したトポロジ・マップを基に、ダイクストラの最短路計算アルゴリズムを用いて最短経路を求めることにより、宛先ノードに至るための次ホップを決定する。
次に、第２経路表４４とラベル表４６を求めるアルゴリズムについて、以下説明する。
【００３２】
まず図３を用いて変数の定義について説明する。Ｇ（Ｖ，Ｅ）は、ネットワークを表す有向グラフである。Ｖはノードの集合、Ｅは有向リンクの集合である。関数ｆ：ｅ（∈Ｅ）→Ｒは、各リンクの重みを表す。ｐｄ（ｖ）はノードｖの第１経路表における宛先ｄへの次ホップを表し、ｂｄ［ｖ］は、ノードｖの第２経路表における宛先ｄへの次ホップを表す。ｐｄ（ｖ）が表す宛先ｄへの最短経路木を転送木Ｔｄと呼ぶ。Ｔｄにおいて、ｖ（∈Ｖ）の親ノードをｐ（ｖ）とし、ｖ（∈Ｖ）の子孫ノードの集合をＤｄ（ｖ）と表す。またｖ（∈Ｖ）の子ノードの集合をＣｄ（ｖ）と表す。また、Ｔｄに対して、ノードｖ（∈Ｖ）を根として導出される部分木をＴｄｖと表す。
【００３３】
ノードｖの宛先ｄに対するｓ−ラベル、ｉ−ラベル、ｏ−ラベルをｓｄ［ｖ］，ｉｄ［ｖ］，ｏｄ［ｖ］と表す。同様にノードｖの宛先ｄに対するｔ−ラベルを定義しｔｄ［ｖ］と表す。ｔ−ラベルは迂回路中の最短路によるトンネルを構成するノード、即ちｉ−ラベルとｏ−ラベルとの間のノード（正確には、ｉ−ラベルノードの次ノードからｏ−ラベルノードまでに含まれるノードで両端を含む）に一時的に設定されるラベルである。
【００３４】
また、各ラベルがｔｒｕｅであるノードを、それぞれｓ−ラベルノード、ｉ−ラベルノード、ｏ−ラベルノード、ｔ−ラベルノードと呼ぶ。
本アルゴリズムの方式では、ＩＰパケットがノードｕ∈Ｖにおいて第２経路表の次ホップに転送され、その後、迂回後状態（状態３）になるまでの経路を、ｕの「迂回路」と定義する。
【００３５】
つまり、迂回路ｐ＝（ｕ（＝ｖ１），ｖ２，．．．，ｖｎ）上の各ノード及び１≦ｋ＜ｎに対して、ｐｄ（ｖｋ）＝ｖｋ＋１であれば、ｖｋはｔ−ラベルノードでなければならず、ｔｄ［ｖｋ］＝falseかつｔｄ［ｖｋ＋１］＝trueであればｖｋはｉ−ラベルノード、ｔｄ［ｖｋ］＝trueかつｔｄ［ｖｋ＋１］＝falseであればｖｋはｏ−ラベルノード、さらに、ｖｎ−１はｓ−ラベルノードでなければならない。
【００３６】
ノード故障に対応する場合には、ｖの迂回路ｐはｐ（ｖ）を通らずにＩＰパケットをｄまで転送できる必要がある。このためには、ｐの終点ノードでＴｄｐ（ｖ）の外部にあるノードｗがＤｄ（ｐ（ｖ））に属さない関係であればよい。ｖ∈Ｖに対してＴｄｐ（ｖ）を「ＮＰ回避領域」と呼び、始点がｖ、終点がＴｄｐ（ｖ）の外部のノードであるｗ、である迂回路ｐをｖの「ＮＰ迂回路」と呼ぶ。
【００３７】
一方、リンク故障に対応する場合には、ｖの迂回路ｐはリンク（ｖ，ｐ（ｖ））を通らずにＩＰパケットをｄまで転送できる必要がある。このためには、ｐの終点ノードｗがＴｄｖの外部あればよい。よって、ｖ∈Ｖに対して、Ｔｄｖを「ＬＰ回避領域」と呼び、始点がｖ、終点がｗ（Ｔｄｖの外部のノード）である迂回路ｐをｖの「ＬＰ迂回路」と呼ぶ。
【００３８】
迂回路ｐに対して、ｔ−ラベルノードのみから構成される極大な部分路ｑ∈ｐをｐの「トンネル区間」と呼ぶ。逆に、ｔ−ラベルノードｖに対して、そのノードにｔ−ラベルが付加された時に設定された迂回路ｐがただ一つ定まり、ｐのトンネル区間の一つでｖを含むものを「ｖのトンネル区間」と呼ぶ。ｔ−ラベルノードｖに対して、ｖのトンネル区間をｐとは逆向きに辿り、ｔ−ラベルノードでないノードに辿りつくまでの経路を「ｖの逆流経路」と呼ぶ。ｔ−ラベルノードｖから最短路トンネルに合流してパケットが転送される迂回路（即ち「状態２」のパケットがｖから転送される迂回路）をｖの「トンネル迂回路」と呼ぶ。また、経路ｐとｑに対して、これらを連結した経路をｐ＋ｑのように表す。
【００３９】
図４〜図６を参照しながら、第２経路表を求めるアルゴリズム"CreateBackupTable-NP"について説明する。図５，図６は、図４のアルゴリズムで用いられるプロシージャとなっている。
本アルゴリズムでは宛先ｄ毎に動作するため、入力として宛先ｄと、この宛先ｄへの最短路木の一つＴｄをとる。このため、各ノードｕにおいて、ｕがｄ∈Ｖ−｛ｕ｝であるｄのそれぞれに対してアルゴリズムを実行し、出力である宛先ｄに関する第２経路表のエントリとｓ，ｉ，ｏのラベルからｕ（自分自身のノード）に関するものを取り出してＩＰパケット転送に用いることとなる。
【００４０】
図４に示すアルゴリズムにおいては、１〜８行目の初期化処理を行う。そして、Ｔｄの幅優先探索順にノードｖを訪問し（９行目）、ｖの子ノードそれぞれについて、もし第２経路表が設定されていなければＮＰ迂回路を探索し（１０−１２行目）、発見されればこれを設定する（１３−１５行目）。その後、さらにｖの子ノードそれぞれについて、もし第２経路表が設定されていなければＬＰ迂回路を探索し（１８−２０行目）、発見されればこれを設定する（２１−２３行目）。迂回路の探索と設定をこのような順序で行うのは、探索される迂回路の回避領域の根ノードがＴｄの根に近い順になることを保証するためである。この手順により、宛先ｄに対する第２経路表とｓ，ｉ，ｏのラベルを計算する。
【００４１】
本アルゴリズムの１２，２０行目で用いられる"findBackupPath"（迂回路の探索）は、ＬＰ迂回路とＮＰ迂回路ともに図５に示すプロシージャ"findBackupPath"により行われる。このプロシージャ"findBackupPath"は迂回路の始点ノードｕ、宛先ノードｄ、回避領域の根ノードｒを入力にとる。ＮＰ迂回路を探索する場合はｒとしてＮＰ回避領域の根ｐ（ｕ）を入力し、ＬＰ迂回路を探索する場合はｕを用いる。
【００４２】
図５のプロシージャ"findBackupPath"は基本的には、ダイクストラの最短路計算アルゴリズムを少し変更して繰り返し実行することで迂回路を探索する。動作の骨組みとしては、迂回すべきノード（またはリンク）をＧから取り除いたグラフを作成し、その上でｕを始点としてダイクストラのアルゴリズムを実行し、Ｑから取り出した各ノードｖのトンネル区間に迂回路の終点となるノードｗ∈Ｓ１∪Ｓ２∪Ｓ３（Ｓ１は回避領域の外部ノードの集合、Ｓ２はＳ１に含まれないノードの中で第２経路表が定義されていないノード集合、Ｓ３はＳ１∪Ｓ２に含まれないｔ−ラベルノードの集合である。）を発見すると、ｕからｖまでの経路とｖからｗまでＴｄに沿った経路を連結した経路を迂回路ｐとして返す。（正確にはｐは迂回路の部分路であるが、便宜上迂回路と呼ぶことにする。）この際に、Ｓ１∪Ｓ２∪Ｓ３に属するノードｗを終点とするリンク（ｘ，ｗ）の重みとして、ｆ（ｘ，ｗ）の重みに、迂回路を通ってｗに着いたとして以後ｄに至るまでの距離を加えた値を用いる。つまり、ｗ∈Ｓ１の場合には、ｗからｄへの最短経路の距離を加え、ｗ∈Ｓ２の場合にはｗから迂回路を通った場合（即ち、「状態１」で第二経路表を用いて転送された場合）のｗからｄへの距離を加え、ｗ∈Ｓ３の場合には、ｗのトンネル区間が回避領域の根ｒを含む場合にはｗの逆流経路を通った場合のｗからｄへの距離、ｒを含まない場合にはｗのトンネル経路を通った場合のｗからｄへの距離を加える。こうすることで、宛先ｄまでできるだけ最短でたどり着けるｖ∈Ｓ１∪Ｓ２∪Ｓ３を探索できる。
【００４３】
処理の例外として、Ｓ３に属するノードｗを発見し、ｗのトンネル区間が回避領域の根ｒを含む場合には、上記のｐとは異なる経路を返す。即ち、ｕからｖまでの経路とｖからｗまでＴｄに沿った経路、そしてｗの逆流経路の３経路を連結したものをｐとして返す。上記のように、このプロシージャは設定すべき迂回路ｐを返す。この迂回路に基づいて第二経路表とｓ，ｉ，ｏのラベルを設定することで、ｕからｄへの迂回路を設定できる。
【００４４】
このプロシージャ"findBackupPath"を図５を用いて説明すると、１−２７行目で変数の初期化を行う。１−５行目では、迂回路を計算するためのグラフＧ’＝（Ｖ’，Ｅ’）を生成する。ｕ＝ｒの場合はＬＰ迂回路を探索するので２行目でＧからリンク（ｒ，ｐ（ｒ））を除いたものをＧ’としている。そうでない場合はＮＰ迂回路を探索するので、４行目でＧからノードｒを除いたものをＧ’としている。６―８行目は迂回路探索時に迂回路の終端となるノード集合Ｓ１、Ｓ２及びＳ３を初期化している。９−２５行目で各ノードｖ∈Ｖ’ に対してdistｕ［ｖ］及びbdistｕ［ｖ］の値を初期化している。いずれもプロシージャ中で一時的に用いられる変数であり、それぞれｕからｖへの距離、及び、（前述の）ｕからｖを経由する迂回路を通ってｄに至る時のｖからｄへの距離を表す。１３−１５行目はＳ１に属するノードｖ∈Ｓ１に対して、１６−１８行目はＳ２に属するノードｖ∈Ｓ２に対して、また１９−２５行目はＳ３に属するノードｖ∈Ｓ３に対して、それぞれbdistｕ［ｖ］の値を与えている。２６行目ではダイクストラのアルゴリズムの始点としてｕを集合Ｑ（ダイクストラのアルゴリズム実行に用いられるノード集合）に入れ、２７行目はｕの距離を０で初期化する。
【００４５】
２８行目以降は迂回路を発見するためのループである。２９−３０行目でＱの中から最小距離のノードｖを取り出し、３１−３２行目では、Ｔｄ上のｕからｖまでの経路上（ｕ、ｖも含む）にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるようなｗが含まれるならば、その中でｖに最も近いものをｗとする。３３−３５行目では、ｗ∈Ｓ１∪Ｓ２の場合に前述の迂回路ｐ（即ちｕからｖまでの発見された経路とｖからｗまでのＴｄに沿った経路を連結したもの）を返し、３６−４２行目ではｗ∈Ｓ３の場合に対応する迂回路ｐを返す。４４−５２行目はダイクストラのアルゴリズムを動作させる部分であり、前述の通りリンク（ｖ,ｗ）に対しては、bdistｄ［ｗ］で表される重みを加算して動作させている。４８行目の２番目の条件はダイクストラのアルゴリズムには存在しない部分であるが、これは、等距離の迂回路が複数あった場合に、できるだけＴｄに沿うような迂回路を選択するための条件である。最後まで迂回路が見つからなければnullを返す（５４行目）。
【００４６】
次に、本アルゴリズムの１４，２２行目（図４）で呼び出される"setBackupNextHops"（次ホップの設定）について説明する。図６に示すプロシージャ"setBackupNextHops"は、"findBackupPath"などで発見された迂回路ｐを第２経路表およびｓ，ｉ，ｏ，ｔ-ラベルとして設定し、ｐの始点ｕから宛先ｄまでＩＰパケットを転送できるようにする処理を行う。このプロシージャは入力として宛先ノードｄ、設定する迂回路ｐ＝（ｕ１，ｕ２，．．．，ｕｎ）、および回避領域の根ノードｒをとる。１行目では迂回路の終端から順に第２経路表を設定するようにループさせ、第２経路表のエントリやラベルを設定する。８−１４行目はｋ＜ｎ−１、即ちｕｋ＋１がｐの終端ノードではない場合の処理、１５−２３行目はｕｋ＋１がｐの終端ノードである場合の処理であり、２−７行目は両方の場合に共通する処理を行う。２−７行目では、両方の場合に共通する処理として、ｔ−ラベルの付加と第二経路表の設定を行う。２−４行目はｕｋの第１経路表のエントリと第２経路表のエントリが等しいとき（つまり、ＩＰパケットがトンネルを通るとき）の処理であり、３行目ではｔ-ラベルを付加し、ｐｈｄｔにこの迂回路を逆向きにたどる（つまり、逆流経路を示す）ための前ホップを記憶しておく。それ以外の場合には、６行目で第２経路表を設定する。以降はｉ，ｏ，ｓ-ラベルの設定である。９−１０行目は、ｕｋでは第１と第２の経路表エントリが異なり、かつｕｋ＋１では同一であるときに、ｕｋにｉ-ラベルを付加し、ｕｋ＋１から第１経路表によるトンネルを用いてＩＰパケット転送するように設定する。１１−１２行目は、ｕｋでは第１と第２の経路表エントリが同一で、かつｕｋ＋１では異なる場合に、ｕｋにｏ-ラベルを付加してＩＰパケットがトンネルから抜けるよう処理をする。１６−１７行目は、ｐの終端が回避領域の外部にあるとき、ｓ-ラベルを付加している。１８−１９行目は、ｐの終端がｔ-ラベルノードで（終端ノードは、第二経路表が設定されていない場合は必ずｔ−ラベルノードである）、ここからトンネルに入るときには、その前のノードにｉ-ラベルを付加する。２０−２１行目は、ｐの終端でトンネルを抜けて別の迂回路に転送する場合には、その前のノードにｏ-ラベルを付加する。
【００４７】
以上が第２経路表と各ラベルを求めるアルゴリズムであり、発見されたどのようなｐに対しても、ＩＰパケットがｐを通るような第２経路表と各ラベルの設定ができる。
＜アルゴリズムに関する理論的結果＞
本アルゴリズムは、全ての双方向ネットワークに対して、任意の１ノード故障に対応できるような第二経路表と３つのラベル（ｓ、ｉ、ｏ−ラベル）を計算できることを保証する。より厳密には、任意のノードｖに対して、もしｖのＮＰ迂回路が存在するならばそのうち一つを設定でき、ＮＰ迂回路が存在しない場合にも、もしｖのＬＰ迂回路が存在するならばそのうち一つを設定できることが保証される。即ち、ノード故障を迂回できることはリンク故障をも迂回できることを考慮すると、本アルゴリズムは迂回可能な全ての１ノード故障、及び１リンク故障に対応可能である。
【００４８】
これよりそのことを証明する。まず、証明にあたり必要な次の定義及び補題を示す。
定義１：経路ｐに対して、任意の２ノードｖ、ｗ∈ｐを選ぶ。もしｐ上でｖがｗの上流に位置し、ｗがＴｄ上でｖの祖先である場合、ｖを始点、ｗを終点とするｐの部分路をスロープ区間と呼ぶ。ｐ上の全てのスロープ区間がＴｄ上にあるとき、ｐを適切経路と呼ぶ。
【００４９】
補題１：ｑをノードｕの迂回路、ｐをｕを始点とするｑの部分路の一つとする。もしｐが適切経路ならば、ｐ上の全てのｔ−ラベルノードｖはＮＰ迂回路を持ち、それはｖの逆流経路である。
証明：もしｐがスロープ区間を持たないならば、補題は満たされる。よって、ｐ上にスロープ区間が存在し、その始点がｖ、終点がｗであるとする（このスロープ区間を以後［ｖ，ｗ］と表す）。ｘをｐ上でｗの直前ノード、ｖ’をｐ上でｖの直前ノードとする。ｐは適切経路なので、そのスロープ区間上の全てのノードはｔ−ラベルノードである。即ち、ｐが設定された時にはこれらのノードの第二経路表は設定されておらず、その迂回路として逆流経路を設定することが可能である。もしｖ’がＴｄ上でｗの子孫であれば、ｐ上の区間［ｖ’，ｗ］は再びスロープ区間であり、上記と同様の議論が可能である。ｕは明らかにｗの子孫ではないので、このようにスロープ区間を広げていくことで、必ずｗの子孫でないｖ’を発見できる。ｖ’がｗの子孫でない場合、ｖ’はＴｄｗの外部にあり、区間［ｖ’，ｘ］内の全ノードに対して、ＮＰ回避領域の外部である。よって、区間［ｖ’，ｘ］内の全てのノードにとって、その逆流経路はＮＰ迂回路となっている。（証明終）
補題１は、設定される迂回路ｐが適切経路であれば、ｐ上の（ｐがＬＰ迂回路であれば始点ノードを除く）全てのノードはＮＰ迂回路を持つことができることを示している。実際に、アルゴリズムCreateBackupTables-NPは迂回路として常に適切経路を計算し設定することで、全ノードに対して（迂回路が存在する場合に限るが）迂回路を保証する。このことを以下の補題と定理により示す。
【００５０】
補題２：プロシージャfindBackupPathは常に適切経路を返す。
証明：プロシージャfindBackupPath内ではｕを始点としてダイクストラの最短路計算アルゴリズムが動作しており、プロシージャにより返される経路は原則として２つの部分に分割できる。つまり、ダイクストラのアルゴリズムにより計算されたｕからｖまでの経路ｐと、ｖからｗ（∈Ｓ１∪Ｓ２∪Ｓ３）までＴｄに沿った経路ｑに分割できる。（例外があるが、これに関しては後述する。また、ｖ＝ｗの場合もあり得る。）ここで、一般にダイクストラのアルゴリズムで用いられるリンクの重みとは異なる重みbdistｄ［］を加えているにもかかわらず、ｐはｕからｖへの重み関数ｆの下での最短路である。なぜなら、bdistｄ［］はｐ上で終端ノードにつながるリンクのみに加算され、かつ、同じ終端ノードにつながる全てのリンクには同じ値が加算されるからである。また、プロシージャfindBackupPathの２９行目と４８行目では、等距離の経路が複数ある場合にはＴｄに沿った経路が優先的に選ばれる仕組みを実現している。従って、ｐは適切経路であり、これにＴｄに沿った最短路ｑを加えた経路ｐ＋ｑも適切経路である。（証明終）
ところで、上記の例外として、findBackupPathはｐ＋ｑにｗの逆流経路を連結した経路を返す場合がある。この場合は、逆流経路上の（終端を除く）ノードが全てｔ−ラベルノードであり、アルゴリズムはＱから取り出したノードｖの祖先にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるノードｗを発見するとすぐに終了するため、ｐ上のｖ以外のどのノードも、逆流経路上のノードをその（Ｔｄ上の）祖先に持たない。よって、ｐ＋ｑに逆流経路をつなげた経路も適切経路である。
【００５１】
定理１：アルゴリズムCreateBackupTable-NPは、任意のノード対（ｓ，ｄ）に対して次の条件を満たすような第二経路表とラベルを計算できる。条件：ｓから宛先ｄへのＮＰ迂回路が存在するならば、ｓはその中で適切経路であるものを迂回路として利用できる。もしＮＰ迂回路が存在せず、ＬＰ迂回路が存在するならば、ｓはその中で適切経路であるものを迂回路として利用できる。
【００５２】
証明：アルゴリズムCreateBackupTable-NPは、Ｔｄの幅優先探索順にノードｖを訪問し、その子ノードｕの迂回路を計算・設定することを繰り返す。迂回路計算の各繰り返し処理において、第二経路表が設定された全てのノードが定理の条件を満たす迂回路を持ち、その迂回路が常に適切経路であることを、数学的帰納法により証明する。
最初に迂回路が計算されるノードｕを考える。ｒをこの時の回避領域の根ノードとする。初回はＳ２∪Ｓ３に含まれるノードは存在しないので、ｕから回避領域Ｔｄｒの外部に到達する迂回路が存在するならば、アルゴリズムがその終端ノードの一つｘ∈Ｓ１を発見できることは明らかである。ここで、発見された経路ｐはｕからｘへのｆの下での最短路の一つであり、２９行目と４８行目の処理で等コスト経路が複数ある場合にはＴｄに沿った経路が優先的に選択されるので、ｕの迂回路ｐは適切経路である。ここで、ｕの迂回路を設定すると、ｐ上のｔ−ラベルノードと終端ノードを除く全てのノードの迂回路も設定されることになる。これらのノードはＴｄ上でｒの子孫であるため、ｘはこれらのＮＰ回避領域の外部にある。即ち、ｐは第二経路表が設定された全てのノードに対してＮＰ迂回路である。
【００５３】
次にｋ回目の繰り返しまで条件が満たされたと仮定し、ｋ＋１回目の処理により計算・設定された迂回路も条件が満たされることを示す。もし、始点ノードｕからＴｄｒの外部に至る経路が存在するならば、アルゴリズムは必ずｗ∈Ｓ１∪Ｓ２∪Ｓ３を発見できる。もし
ｗ∈Ｓ１が発見されたならば、上記の議論から条件は満たされる。
【００５４】
ｗ∈Ｓ２が発見された場合、ｐを発見されたｕからｖまでの経路とし、ｐ’をｖからｗまでのＴｄに沿った経路とし、ｑをｗの（既に設定された）迂回路とする。ｑは仮定より適切経路であり、ｖ∈Ｄｄ（ｒ）よりｑはｒを含まない。また、アルゴリズムは回避領域が広い順番に（つまり回避領域の根が宛先ｄに近い順番に）迂回路を計算するため、ｑはＴｄｒの外部に到達できる。よって、経路ｐ＋ｐ’＋ｑはｕの迂回路である。一方、補題２より、このｕの迂回路は２本の適切経路ｐ＋ｐ’とｑの連結である。アルゴリズムはＱからノードを取り出し、その祖先にｗ∈Ｓ１∪Ｓ２∪Ｓ３であるノードｗを発見するとすぐに迂回路を決定する。よって、全てのｘ１∈（ｐ＋ｐ’）、ｘ２∈ｑの組に対して、ｘ１がｘ２のＴｄ上の子孫であれば、ｐ＋ｐ’＋ｑ上の区間［ｘ１，ｘ２］はＴｄに含まれる。即ち経路ｐ＋ｐ’＋ｑは適切経路である。また、このとき第二経路表が設定された全てのノードは、前述の議論によりＮＰ迂回路を持つ。
【００５５】
最後に、ｗ∈Ｓ３である場合は、ｐを発見されたｕからｖまでの経路とし、ｐ’をｖからｗまでのＴｄに沿った経路とし、ｑ１をｗのトンネル迂回路とし、ｑ２をｗの逆流経路とする。もしｑ１がｒを含まない場合、上記ｗ∈Ｓ２の場合と同様の議論により、ｐ＋ｐ’＋ｑ１はＴｄｒの外部に到達できる迂回路であり、適切経路である。一方、ｑ１がｒを含む場合、ｑ１が適切経路であることからｗとｒはいずれもｗのトンネル区間内にある。よって、補題１より、ｗの逆流経路はＴｄｒの外部に到達でき、ｐ＋ｐ’＋ｑ２はｕの迂回路である。また、補題２より、ｐ＋ｐ’＋ｑ２は適切経路である。また、このとき第二経路表が設定された全てのノードは、前述の議論によりＮＰ迂回路を持つ。
【００５６】
以上により、ｋ＋１回目の繰り返し処理で第二経路表が設定される（ｕを除く）全てのノードは定理の条件を満たす迂回路を持つ。（証明終）
＜動作＞
次にノードｕ２における、ＩＰパケット受信からＩＰパケット転送までの処理の流れについて図７を用いて説明する。なお、図１で示したノードｕ２以外の各ノード（ノードｕ１，ｕ３，ｕ４，ｕ５，ｗ１，ｗ２）も同様な動作を行う。
【００５７】
まず、受信部１４がＩＰパケットを受信すると（Ｓ１０）、状態制御部２２は受信したＩＰパケットのヘッダに含まれる状態を読み取る（Ｓ１１）。
状態が０であり（Ｓ１２：Ｙｅｓ）、故障検出部２０が第１経路表４２の次ホップの故障を検出していなければ（Ｓ１３：Ｎｏ）、転送部１６は第１経路表４２の次ホップにＩＰパケットを転送する（Ｓ１４）。このように、第１経路表４２の次ホップに故障がない限りは、状態が０のままでこの第１経路表４２の次ホップに転送されることとなる。
【００５８】
故障検出部２０が次ホップの故障を検出を検出していれば（Ｓ１３：Ｙｅｓ）、転送部１６は第２経路表４４の次ホップにＩＰパケットを転送する（Ｓ１８）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｓ-ラベルがtrueでなければ（Ｓ１５：Ｎｏ、Ｓ１６）状態０から状態１へと書き換え（Ｓ１６）、ｓ-ラベルtrueであれば（Ｓ１５：Ｙｅｓ）状態０から状態３へと書き換える（Ｓ１７）。
【００５９】
状態が０でなく１であれば（Ｓ１２：Ｎｏ、Ｓ２１：Ｙｅｓ）、転送部１６は第２経路表４４の次ホップにＩＰパケット転送する（Ｓ２６）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｉ-ラベルtrueであれば状態１から状態２へと書き換え（Ｓ２２：Ｙｅｓ，Ｓ２３）、ｉ-ラベルtrueでなくｓ-ラベルtrueであれば状態１から状態３へと書き換える（Ｓ２２：Ｎｏ，Ｓ２４：Ｙｅｓ，Ｓ２５）。
【００６０】
状態が１でなく２であれば（Ｓ２１：Ｎｏ、Ｓ３１：Ｙｅｓ）、転送部１６は第１経路表４２の次ホップにＩＰパケット転送する（Ｓ３４）。そして、転送前に、状態制御部２２はラベル表４６を参照して、ｏ-ラベルtrueであれば状態２から状態１へと書き換える（Ｓ３２：Ｙｅｓ，Ｓ３３）。
状態が２でなく３であれば（Ｓ３１：Ｎｏ、Ｓ４１）、転送部１６は第１経路表４２の次ホップにＩＰパケット転送する（Ｓ４２）。
【００６１】
図１のネットワーク１において、第１および第２経路表、各ラベルについて、上述のアルゴリズムに従って計算した結果を図８に示す。
図８においては、各ノードｕ１〜ｕ５，ｗ１，ｗ２の傍らに、第１経路表および第２経路表、さらに各ラベルがtrue／falseを示している。例えば、ノードｕ２は、第１経路表に示される次ホップがｕ１であり、第２経路表に示される次ホップがｕ３であり、ｉラベルがtrue、ｏ-ラベル，ｓ-ラベルはfalseとなっている。
【００６２】
例えば、ノードｕ１が宛先ｄのＩＰパケットを受信した場合で、ノードｕ５が故障した際の各ノードの動作については、次の（１）〜（６）の通りである（図９参照）。
（１）ノードｕ１は、状態０のＩＰパケットを受信すると（Ｓ１２：Ｙｅｓ）、第１経路表の次ホップｕ５の故障を検出し（Ｓ１３：Ｙｅｓ）、状態を０から１へと書き換え（Ｓ１６）、第２経路表に示される次ホップのｕ２へと転送する（Ｓ１８）。
【００６３】
（２）ノードｕ２は、状態１のＩＰパケットを受信すると（Ｓ２１：Ｙｅｓ）、ｉ-ラベルtrueなので状態を１から２へと書き換え（Ｓ２２：Ｙｅｓ，Ｓ２３）、第２経路表に示される次ホップのｕ３へと転送する（Ｓ２６）。
（３）ノードｕ３は、状態２のＩＰパケットを受信すると（Ｓ３１：Ｙｅｓ）、ｏ-ラベルtrueなので状態を２から１へと書き換え（Ｓ３２：Ｙｅｓ，Ｓ３３）、第１経路表の次ホップｕ４へと転送する（Ｓ３４）。
【００６４】
（４）ノードｕ４は、状態１のＩＰパケットを受信すると（Ｓ２１：Ｙｅｓ）、ｓ-ラベルtrueなので状態を１から３へと書き換え（Ｓ２２：Ｎｏ，Ｓ２４：Ｙｅｓ，Ｓ２５）、第２経路表の次ホップｗ１へと転送する（Ｓ２６）。
（５）ノードｗ１は、状態３のＩＰパケットを受信すると（Ｓ４１）、第１経路表の次ホップｗ２へと転送する（Ｓ４２）。
【００６５】
（６）ノードｗ２は、状態３のＩＰパケットを受信すると（Ｓ４１）、第１経路表の次ホップｄへと転送する（Ｓ４２）。
このようにノードｕ５が故障した際においても、ノードｕ１→ｕ２→ｕ３→ｕ４→ｗ１→ｗ２→ｄという迂回路を通ってＩＰパケットを無事宛先ノードｄへと届けることができる。
【００６６】
以上説明したように、本実施の形態によれば、ＩＰパケットの宛先に関連付けられたｓ，ｉ，ｏの各ラベルを利用してＩＰパケットの状態を書き換えて、第１経路表と第２経路表のいずれの表を使うべきかを多様に設定することが可能となる。特に、ノード故障の検出後の迂回において、一旦迂回路に入ったにも関わらず（ｕ１→ｕ２→ｕ３）、途中で第１経路表を使って最短路を通るトンネルに入り（ｕ３→ｕ４）、トンネルを出た後は第２経路表を使い（ｕ４→ｗ１）、その後、また第１経路表を使う（ｗ１→ｗ２→ｄ）というように柔軟に適切な迂回路を設定することができる。
【００６７】
このように第１経路表と第２経路表というわずか２枚の経路表によりノードプロテクションを実現することができる。また、４つの状態はＩＰパケットヘッダのＴＯＳフィールドに2ビットという軽い情報量で入れ込むので、ネットワークへの影響も軽微である。
＜補足＞
以上、本発明の実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連または付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であってもよい。
【００６８】
１．実施の形態においては、ノードｕ５が故障した際における例（図８）についてのみ説明したが、実施の形態によれば、ｕ１〜ｕ５，ｗ１，ｗ２のうちの任意のノードが宛先ｄのＩＰパケットを受信した際に、他のノードが故障していたとしても、適切に迂回路を保証することができる、つまりノードプロテクションを実現することができる。
また、任意のリンクが故障していたとしても適切に迂回路を保証することができる、つまりリンクプロテクションを実現することができる。
【００６９】
２．図１（図８）とは、異なる形態のネットワークに実施の形態を適用した場合の例について変形例として以下説明する。図１０は変形例に係るネットワーク構成などを示す図である。図１０（ａ）はネットワーク構成（トポロジ）を示し、図１０（ｂ）は第１経路表とｏ-ラベル、図１０（ｃ）は第２経路表とｉ-ラベル，ｓ-ラベルを示す。
図１０のネットワークにおいても実施の形態の同様にノードプロテクションを実現できる。例えば、宛先がノード６であるＩＰパケットをノード２が受信した場合で、ノード３が故障している際には、
（１）ノード２は、ノード３の故障を検出すると、ＩＰパケットの状態を０から１へと書き換え、第２経路表に示される次ホップのノード７へとＩＰパケットを転送する。
【００７０】
（２）ノード７は、ＩＰパケットの状態が１であるため第２経路表に示される次ホップのノード９へとＩＰパケットを転送する。また、ｉ-ラベルtrueなので転送前に状態を１から２へと書き換える。
（３）ノード９は、ＩＰパケットの状態が２であるため第１経路表に示される次ホップのノード４へとＩＰパケットを転送する。また、ｏ-ラベルtrueなので転送前に状態を２から１へと書き換える。
【００７１】
（４）ノード４は、ＩＰパケットの状態が１であるため第２経路表に示される次ホップのノード５へとＩＰパケットを転送する。また、ｓ-ラベルtrueなので転送前に状態を１から３へと書き換える。
（５）ノード５は、ＩＰパケットの状態が３であるため第１経路表に示される次ホップのノード８へとＩＰパケットを転送する。
【００７２】
（６）ノード８は、ＩＰパケットの状態が３であるため第１経路表に示される次ホップのノード６へとＩＰパケットを転送する。
このように本変形例においても、ノードプロテクションを行うことができる。
３．迂回路の途中で第１経路表を使う方法としては、カプセル化の技術や、ＭＰＬＳ（Multi Protocol Label Switching）やＡＴＭ（Asynchronous Transfer Mode）などを含むラベルスイッチング技術と組み合わせることもできる。
【００７３】
カプセル化については、RFC2003に規定されているIPパケット中にIPパケットをカプセル化するトンネリング技術が代表的あるが、RFC1701に規定されているような異なるプロトコル間でのトンネリングや、RFC3931に規定されているようなレイヤ２フレーム(Ethernet（登録商標）など)をIPの中にカプセル化する技術などを適宜用いることができる。
カプセル化を利用した場合の具体例を図１１に示す。なお、図１１においても図８、図１４などと同様に、第１経路表，第２経路表の次ホップへの経路をそれぞれ「第１経路」，「第２経路」と矢印で示している。
【００７４】
ノードｕ１のノードが故障した際には、ｕ１→ｕ２→ｕ３→ｕ４→ｕ５→ｕ６→ｕ７→ｄという経路でパケットが転送される。実施の形態の図８，図９などと挙動が異なるのは基本的にノードｕ３からノードｕ５に至る間だけであるので、この間の詳細のみを以下説明する。
（１）ノードｕ３においてＩＰパケット（状態１，宛先ｄ）をペイロード部分に入れてヘッダ部分に宛先ｕ５、状態０（デフォルトの状態）を内包させた入れたパケットを新たに作成し（カプセル化）、第１経路のノードｕ４へと送る。カプセル化されたパケットには、ＩＰパケット（状態１，宛先ｄ）が内包されることとなる。
【００７５】
（２）ノードｕ４は、受信したＩＰパケットの状態が０であるため、第１経路表に示されるノードｕ５へとＩＰパケットを送る。
（３）ノードｕ５は、受信したＩＰパケットの宛先が自ノードであるため、パケットのカプセル化を解除して、中身（ペイロード部分）からＩＰパケット（状態１，宛先ｄ）を取り出す。そして、取り出したＩＰパケット（状態１，宛先ｄ）は、状態１であるため、第２経路表のノードｕ６へと送る。
【００７６】
なお、カプセル化を行った「ｕ３」は、ｉ-ラベルが付加されたノードｕ２からみて第１経路にあるノード（状態２のパケットを最初に受信するノード）であり、そして、カプセル化したパケットの宛先「ｕ５」はｏ-ラベルが付加されたノードｕ４からみて第１経路にあるノードである。このようにカプセル化の開始ノードと宛先ノードとを設定することで迂回路中に第１経路（最短路）を通るトンネル区間（ｕ３からｕ５までの区間）を設定することができる。
【００７７】
なお、カプセル化の開始ノードを「ｕ３」に代えて、例えば「ｕ２」など適宜変更することができる。
次に、ラベルスイッチング技術と組み合わせた一例としてＭＰＬＳを用いて説明する。ＭＰＬＳはパケットにＭＰＬＳラベルを付加することで、ＭＰＬＳラベルが付加されているパケットはそのＭＰＬＳラベルに対応した既設定経路を用いて転送する技術であり、ＭＰＬＳラベルは、経路制御中に付加したり削除したり操作が可能である。ＭＰＬＳは、従来の最短経路による経路制御よりも柔軟な経路設定が可能であるため、負荷分散等にも利用されている。
【００７８】
ＭＰＬＳを利用した場合の具体例を図１２に示す。本例もノードｕ３からノードｕ５に至る間の詳細のみを以下説明する。
（１）ノードｕ３においてＩＰパケット（状態１，宛先ｄ）にＭＰＬＳラベルであるラベル"7"を付加する。ＭＰＬＳのネットワーク内では、ＩＰヘッダの宛先ではなくラベルのみに基づいて転送先が決定される。このため、ラベル"7"に対応したＬＳＰ（Label Switch Path）を用いてパケットが転送される。ここで、ラベル"7"は終点（宛先）がノードｕ５でｕ３→ｕ４→ｕ５と第１経路（最短路）を通る経路に設定されているものとする。
【００７９】
（２）ノードｕ４は、受信したＩＰパケットに付加されたラベル"7"に従って、ノードｕ５へとＩＰパケットを送る。
（３）ノードｕ４は、受信したＩＰパケットに付加されたラベル"7"が自ノードを宛先としているので、このＩＰパケットからラベル"7”を外す。そして、ラベル"7”を外したＩＰパケットは状態１であるため、第２経路表に示されるノードｕ６へとＩＰパケットを送る。
【００８０】
なお、ラベル"7"を付加した「ｕ３」は、ｉ-ラベルが付加されたノードｕ２からみて第１経路にあるノード（状態２のパケットを最初に受信するノード）であり、そして、ラベル"7"に従う経路は第１経路（最短路）を通り経路の終点は「ｕ５」となっている。ＭＰＬＳを利用した場合も上のカプセル化の場合と同様、迂回路中に第１経路（最短路）を通るトンネル区間（ｕ３からｕ５までの区間）を設定することができる。
【００８１】
また、図１２では、ラベル"7"は第１経路（最短路）を通るように設定されているとして説明したが、効率を考慮すると最短路であることが望ましいが、これに限らず第２経路（迂回路）と異なる経路であればよく、必ずしも最短路である必要はない。
４．実施の形態では、ＯＳＰＦ（Open Shortest Path First）のルーティング・プロトコルに適用した例について説明している。ＯＳＰＦは、中規模のネットワークにおいて、非常に効率的な運用を可能にできるという利点がある。
【００８２】
実施の形態で説明した手法は、ＯＳＰＦだけではなくＩＳ−ＩＳ（Intermediate System to Intermediate System）のようなリンク状態型ルーティングにも適用することができる。
さらには、スタティック・ルーティング、つまり各ノードに第１および第２経路表や各ラベルなどを手動で設定するとしてもよい。
【００８３】
５．実施の形態では、各ノードの計算部３０において個別に表やラベルの計算をするとしてが、これに代えて、上記計算は処理能力に優れたサーバで行い、各ノードは計算結果をサーバから受け取って、表やラベルを設定するとしてもよい。
６．実施の形態では、最短路計算アルゴリズムの例として、ダイクストラを例に挙げたが、これに限られず、例えば、ワーシャル−フロイド法など他の最短路計算アルゴリズムを適用することができる。
【００８４】
７．実施の形態では、第１経路表における次ホップは宛先ノードｄに至るための最短経路上に存在する隣接ノード（最短ノード）であり、第２経路表における次ホップは宛先ノードｄに至るための迂回の経路上に存在する隣接ノード（迂回ノード）であるとして説明したが、第１経路表の次ホップの導出方法はこれに限られない。例えば、効率を重視しない（あるいは無視できる）ネットワーク設計であれば上記最短ノードではないノードを第１経路表に設定するとしても構わない。
【００８５】
８．実施の形態においては、故障検出部２０の故障を検出した場合に状態を状態０から状態１へと書き換えるとして説明したが、このような故障検出に限らず例えば輻輳を検出するなど第１経路表の次ホップへの転送が円滑に行えないことを条件としてもよい。また、隣接ノードとの間でやりとりされるメッセージやリンクを流れる電流、光信号などを定期的な検出対象として、検出結果に基づいて状態０から状態１への書き換えを行うとしてもよい。
【００８６】
９．図７のフローチャートにおいて、第２経路表の次ホップに転送しようとしたとき、第２経路表の計算が未完了であるなど第２経路表の次ホップが存在しない場合には、状態３に書き換えて第１経路表の次ホップに転送するとしてもよい。
１０．本実施の形態は、無線アドホックネットワーク、無線メッシュネットワーク、センサーネットワーク、その他経路制御を必要とする種々のネットワークに適用可能である。
【００８７】
１１．実施の形態において説明した第１および第２経路表、さらには各ラベルを計算するアルゴリズムについては、あくまでも一例でありこれに限定されるものではない。
１２．実施の形態では、ＩＰｖ４のＩＰパケットのＴＯＳフィールドに状態を含ませるとして説明したが、ＩＰｖ６においても例えばヘッダ部分の拡張されたフィールドなどに状態を含ませることで実施することができる。
【００８８】
１３．実施の形態では、ＩＰパケットを例に挙げて説明したが、本発明は、ＩＰパケットのみの適用には限定されず、経路表を用いてパケットを転送するスキームのすべてに適用可能である。ＩＰ以外にも、例えばＩＰＸ（Internetwork Packet eXchange）といったプロトコルにも適用できる。また、その他無線通信で独自仕様の通信プロトコルに適用できる。
【００８９】
１４．実施の形態では、ｓ-ラベルのノードを過ぎると直ちに迂回後の状態３に変更しているので（図９，図７：Ｓ２４：Ｙｅｓ，Ｓ２５）、迂回後のさらなる迂回はできない構成であったが、もっともこれに限らず、状態３へ変更する代わりにデフォルトの状態０へと変更することで、複数回の迂回を許容するようにしてもよい。
具体的には、図１３（ａ）に示すように、ＩＰパケットのヘッダ部分に迂回回数を格納する領域を設定しておく。
【００９０】
そして、図１３（ｂ）に示すように、ｓ-ラベルがtrueであれば（Ｓ２４：Ｙｅｓ）、ＩＰパケットに格納された迂回領域を参照して、迂回回数が例えば３以下であれば（Ｓ５１：Ｙｅｓ）、迂回回数をインクリメントし（Ｓ５２）、状態を状態１から状態０へと変更する（Ｓ５３）。迂回回数が３以下でなければ（Ｓ５１：Ｎｏ）、状態を状態１から状態３へと変更する（Ｓ２５）。
【００９１】
なお、図１３（ｂ）においては、図７と同様なステップに同じステップ番号を付している。
このようにすることで、ＩＰパケットに３回までの迂回を許容することができ、パケット損失の低減に寄与できる。
【産業上の利用可能性】
【００９２】
本発明に係る経路制御装置はルータなどのネットワーク機器として有用である。
【符号の説明】
【００９３】
１ ネットワーク
１４ 受信部
１６ 転送部
２０ 故障検出部
２２ 状態制御部
３０ 計算部
３２ 第１経路表計算部
３４ 第２経路表計算部
３６ ラベル計算部
４２ 第１経路表
４４ 第２経路表
４６ ラベル表
ｕ１〜ｕ５，ｗ１，ｗ２ ノード（ルータ）
ｄ 宛先ノード（宛先ルータ）
【特許請求の範囲】
【請求項１】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と、転送先の決定に係る状態を示す情報とを格納するパケットを受信する受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、前記第１ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示していれば転送前に前記状態２から前記状態１へと書き換え、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項２】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と転送先の決定に係る状態を示す情報とを格納するパケットを受信し、
自ノード宛のカプセル化されたパケットを受信すると、カプセル化の解除後のパケットを、受信したパケットとして扱う受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、当該パケットを、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示すノードからみて第１ノードであるノードを宛先として状態が状態０であるパケットに内包させるようカプセル化し、カプセル化したパケットを前記第１ノードへと前記パケットを転送し、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項３】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、受信されたパケットに前記第１経路表に対応する経路であることを識別するＭＰＬＳラベルを付加した後、当該ＭＰＬＳラベルにより識別されるノードへと転送し、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項４】
ネットワークを構成する複数のノードから構成される経路制御システムにおける方法であって、
各ノードにおいて、宛先ノードに至る第１経路と、前記宛先ノードに至り第１経路とは異なる迂回路である第２経路とを記憶する記憶ステップと、
各ノードにおいて、第１経路を用いたパケットの転送が可能でないならば、パケットに迂回途中である旨を示す情報を付加した後で第２経路を用いてパケットを転送する迂回開始ステップと、
各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信すると、第２経路を用いてパケットを転送する迂回中ステップと、
各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信したにも関わらず、自ノードに関して宛先ノードに至るための経路に係る所定の条件を満足していれば、前記迂回中ステップで用いる第２経路に代えて、第１経路表を用いてパケットを転送する迂回中トンネルステップと、
を備えることを特徴とする経路制御システムにおける方法。
【請求項１】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と、転送先の決定に係る状態を示す情報とを格納するパケットを受信する受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、前記第１ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示していれば転送前に前記状態２から前記状態１へと書き換え、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項２】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と転送先の決定に係る状態を示す情報とを格納するパケットを受信し、
自ノード宛のカプセル化されたパケットを受信すると、カプセル化の解除後のパケットを、受信したパケットとして扱う受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、当該パケットを、前記パケットの宛先に対応するラベル情報が第３ラベルの付加を示すノードからみて第１ノードであるノードを宛先として状態が状態０であるパケットに内包させるようカプセル化し、カプセル化したパケットを前記第１ノードへと前記パケットを転送し、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項３】
ネットワークを構成するノードであり、パケットの転送先を制御する経路制御装置であって、
宛先と、転送先の決定に係る状態を示す情報を格納するパケットを受信する受信部と、
宛先ノードと、当該宛先ノードに至る第１経路上に存する第１ノードと、を対応付けた第１経路表と、
宛先ノードと、当該宛先ノードに至る第２経路上に存する第２ノードと、を対応付けた第２経路表と、
宛先ノード毎に、前記パケットに格納された状態の書き換え内容を表すラベル情報と、
を記憶する記憶部と、
前記受信部により受信されたパケットに格納された情報に示される状態が、
状態０であり、前記第１ノードへの転送が可能ならば、当該第１ノードへと前記パケットを転送し、
状態０であり、前記第１ノードへの転送が可能でないならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第１ラベルの付加を示していれば転送前に前記状態０から状態３へと書き換え、第１ラベルの付加を示していなければ転送前に状態０から状態１へと書き換え、
状態１であるならば、前記第２ノードへと前記パケットを転送して、前記パケットの宛先に対応するラベル情報が第２ラベルの付加を示していれば転送前に状態１から状態２へと書き換え、第２ラベルの付加を示しておらず第１ラベルの付加を示していれば転送前に状態１から状態３へと書き換え、
状態２であるならば、受信されたパケットの状態を前記状態２から前記状態１へと書き換えて、受信されたパケットに前記第１経路表に対応する経路であることを識別するＭＰＬＳラベルを付加した後、当該ＭＰＬＳラベルにより識別されるノードへと転送し、
状態３であるならば、前記第１ノードへと前記パケットを転送する転送制御部と、
を備える
ことを特徴とする経路制御装置。
【請求項４】
ネットワークを構成する複数のノードから構成される経路制御システムにおける方法であって、
各ノードにおいて、宛先ノードに至る第１経路と、前記宛先ノードに至り第１経路とは異なる迂回路である第２経路とを記憶する記憶ステップと、
各ノードにおいて、第１経路を用いたパケットの転送が可能でないならば、パケットに迂回途中である旨を示す情報を付加した後で第２経路を用いてパケットを転送する迂回開始ステップと、
各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信すると、第２経路を用いてパケットを転送する迂回中ステップと、
各ノードにおいて、迂回途中である旨を示す情報が付加されたパケットを受信したにも関わらず、自ノードに関して宛先ノードに至るための経路に係る所定の条件を満足していれば、前記迂回中ステップで用いる第２経路に代えて、第１経路表を用いてパケットを転送する迂回中トンネルステップと、
を備えることを特徴とする経路制御システムにおける方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−６６５３６（Ｐ２０１１−６６５３６Ａ）
【公開日】平成２３年３月３１日（２０１１．３．３１）
【国際特許分類】
【出願番号】特願２００９−２１３６０６（Ｐ２００９−２１３６０６）
【出願日】平成２１年９月１５日（２００９．９．１５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発行者名：社団法人情報処理学会 湖東 俊彦 刊行物名：情報処理学会シンポジウムシリーズ〔マルチメディア，分散，協調とモバイル（ＤＩＣＯＭＯ２００９）シンポジウム論文集〕 巻数、号数： Ｖｏｌ．２００９，Ｎｏ．１ 発行年月日：２００９年７月１日
【出願人】（５０４１４５２８３）国立大学法人 和歌山大学 (62)
【Ｆターム（参考）】
【公開日】平成２３年３月３１日（２０１１．３．３１）
【国際特許分類】
【出願日】平成２１年９月１５日（２００９．９．１５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発行者名：社団法人情報処理学会 湖東 俊彦 刊行物名：情報処理学会シンポジウムシリーズ〔マルチメディア，分散，協調とモバイル（ＤＩＣＯＭＯ２００９）シンポジウム論文集〕 巻数、号数： Ｖｏｌ．２００９，Ｎｏ．１ 発行年月日：２００９年７月１日
【出願人】（５０４１４５２８３）国立大学法人 和歌山大学 (62)
【Ｆターム（参考）】
[ Back to top ]