(57)【要約】【課題】経路情報を伝搬するときに、伝搬漏れを無くしつつ、伝搬のメッセージ量を適切に削減すること。【解決手段】経路伝搬システムは、リーフ側に属するリーフ２１が、新しい経路情報を含む伝搬メッセージとしてそれぞれ作成したＬＦ−ＬＳＡと、ＳＦ−ＬＳＡとを、スパイン側に属する別々のネイバに送信し、ＬＦ−ＬＳＡを受信したスパイン１２が、リーフ２１とは別のリーフ側に属するリーフ２２にＬＦ−ＬＳＡを転送することで、リーフ２２に対してスパイン側に向けてＬＦ−ＬＳＡをフラッディングさせ、ＳＦ−ＬＳＡを受信したスパイン１３が、自身からリーフ側に向けてＳＦ−ＬＳＡをフラッディングさせる。【選択図】図１
2018032894.tif 000002
【特許請求の範囲】
【請求項１】
第１ノード集合と第２ノード集合とで、各集合に属するノードが、別の集合に属するノードに対してネイバとして接続される経路伝搬システムであって、
前記第１ノード集合に属する所定のノードは、新しい経路情報を含む伝搬メッセージとしてそれぞれ作成した第１メッセージと、第２メッセージとを、前記第２ノード集合に属する別々のネイバに送信し、
前記第１メッセージを受信した前記第２ノード集合に属する第１ネイバは、前記所定のノードとは別の前記第１ノード集合に属するノードに前記第１メッセージを転送することで、その転送先のノードに対して前記第２ノード集合に向けて前記第１メッセージをフラッディングさせ、
前記第２メッセージを受信した前記第２ノード集合に属する第２ネイバは、自身から前記第１ノード集合に向けて前記第２メッセージをフラッディングさせることを特徴とする
経路伝搬システム。
【請求項２】
前記第１ノード集合に属する前記所定のノードは、新しい経路情報を含む前記伝搬メッセージを作成するときに、フラッディングをさせない経路伝搬範囲を示す第１ＴＴＬ値と、フラッディングをさせる経路伝搬範囲を示す第２ＴＴＬ値とをそれぞれ含めた前記伝搬メッセージを作成し、
各前記伝搬メッセージを受信したノードは、前記第１ＴＴＬ値と前記第２ＴＴＬ値とをそれぞれ減算した後、前記第１ＴＴＬ値と前記第２ＴＴＬ値との値に応じて、フラッディングをさせずに前記伝搬メッセージを転送するか、前記伝搬メッセージをフラッディングするか、受信した前記伝搬メッセージを破棄するかを決定することを特徴とする
請求項１に記載の経路伝搬システム。
【請求項３】
前記第１ノード集合に属する前記所定のノードは、あらかじめ設定されている冗長度に応じて、前記第１メッセージと、前記第２メッセージとをそれぞれ複数個作成し、それらの作成した前記伝搬メッセージを別々のネイバに送信することを特徴とする
請求項１または請求項２に記載の経路伝搬システム。
【請求項４】
第１ノード集合と第２ノード集合とで、各集合に属するノードが、別の集合に属するノードに対してネイバとして接続される経路伝搬システムの経路伝搬方法であって、
前記第１ノード集合に属する所定のノードは、新しい経路情報を含む伝搬メッセージとしてそれぞれ作成した第１メッセージと、第２メッセージとを、前記第２ノード集合に属する別々のネイバに送信し、
前記第１メッセージを受信した前記第２ノード集合に属する第１ネイバは、前記所定のノードとは別の前記第１ノード集合に属するノードに前記第１メッセージを転送することで、その転送先のノードに対して前記第２ノード集合に向けて前記第１メッセージをフラッディングさせ、
前記第２メッセージを受信した前記第２ノード集合に属する第２ネイバは、自身から前記第１ノード集合に向けて前記第２メッセージをフラッディングさせることを特徴とする
経路伝搬方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路伝搬システム、および、経路伝搬方法の技術に関する。
【背景技術】
【０００２】
CLOS型ネットワークは、多段階の回路交換システムとして知られている。その中でも、入力→中段→出力という３段階の3-stage-CLOS型ネットワークトポロジは、よく利用されている（非特許文献１の図１など）。このアーキテクチャは単一の装置内のアーキテクチャとして採用される場合と、複数の装置を組み合わせてネットワークとして構成される場合がある。複数の装置を組み合わせる場合、その装置は、リーフ（Leaf）とスパイン（Spine）に分類される。
リーフ（葉）とは、ネットワークにおいてネットワーク外部からの入力またはネットワーク外部への出力を行うノード装置である。
スパイン（幹）とは、リーフ間の通信を折り返すノード装置である。
【０００３】
非特許文献２（図３など）に示されるように、CLOS型ネットワークはＩＰを用いて構成されることが一般的である。ＩＰネットワークにおいて、ネットワークが保持するインタフェースのＩＰアドレス情報を経路広告する方法としていくつかの方法がある。
例えば、非特許文献３に示されるＯＳＰＦの経路広告を使うことで、ネットワーク仮想化としてＬ３ＶＰＮなどをサポートするためにＭＰＬＳを利用することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】CHARLES CLOS,"A study of non-blocking switching networks" (PDF). Bell System Technical Journal 32 (2): 406-424. doi:10.1002/j.1538-7305.1953.tb01433.x. ISSN 0005-8580
【非特許文献２】Mohammad Alizadeh, et al. "pFabric: Minimal Near-Optimal Datacenter Transport"、［online］、2013年8月、SIGCOMM’13,Hong Kong, China. ［平成28年8月8日検索］、インターネット〈URL：http://conferences.sigcomm.org/sigcomm/2013/papers/sigcomm/p435.pdf〉
【非特許文献３】J. Moy、"OSPF Version 2"、［online］、1998年4月、［平成28年8月8日検索］、インターネット〈URL：https://www.ietf.org/rfc/rfc2328.txt〉
【発明の概要】
【発明が解決しようとする課題】
【０００５】
リンクステート型プロトコルではフラッディング（Flooding）を用いて経路情報（リンクステート）を情報伝搬する。この情報伝搬のメッセージ量が多いと、ネットワークの通信資源を圧迫してしまう。
図８の符号９０１は、Ｓ台のスパイン（スパイン１１〜１Ｓ）と、Ｌ台のリーフ（リーフ２１〜リーフ２Ｌ）を接続するネットワーク構成の一例である。
全てのノードがフラッディングした場合、メッセージ総数＝Ｌ×（Ｓ−１）＋Ｓ×（Ｌ−１）である。このように、重複も含めたメッセージ総数が多すぎるので、リンクステート型プロトコルを利用したCLOS型ネットワークのＩＰアドレス経路広告において、フラッディングを抑制する必要がある。
【０００６】
図８の符号９０２は、リーフ２１とスパイン１１との間でリンクが切断されたことにより、リンク情報が更新された状況を示す。障害を検知したリーフ２１およびスパイン１１は、それぞれの装置内で更新されたリンク情報をＬＳＡ（Link-State Advertisement）に含めて伝搬する。
ここでリーフ２１が送信したＬＳＡに着目する。
１ホップ目：リーフ２１→スパイン１２、スパイン１３
２ホップ目：スパイン１２→リーフ２２、リーフ２３。スパイン１３→リーフ２２、リーフ２３
【０００７】
この２ホップ目でリーフ２２とリーフ２３はそれぞれスパイン１２とスパイン１３からリーフ２１発の情報を重複して受信する。重複して受信した場合、先に処理されたものが優先されて後から到着した情報は破棄される。以上のようにCLOS型ネットワークにおいてフラッディングを行うと重複した情報が何回も受信され、破棄されるという無駄な処理が繰り返される（符号９０２では必要な伝搬は実線矢印、不要な伝搬は破線矢印）。
このように、全ノードがフラッディングしていた従来のリンクステート型プロトコルでは、情報伝搬の漏れが無いことだけが考慮されていたため、メッセージ量が多くなってしまう。
【０００８】
そこで、本発明は、経路情報を伝搬するときに、伝搬漏れを無くしつつ、伝搬のメッセージ量を適切に削減することを、主な課題とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明の経路伝搬システムは、以下の特徴を有する。
つまり、本発明は、第１ノード集合と第２ノード集合とで、各集合に属するノードが、別の集合に属するノードに対してネイバとして接続される経路伝搬システムであって、
前記第１ノード集合に属する所定のノードが、新しい経路情報を含む伝搬メッセージとしてそれぞれ作成した第１メッセージと、第２メッセージとを、前記第２ノード集合に属する別々のネイバに送信し、
前記第１メッセージを受信した前記第２ノード集合に属する第１ネイバが、前記所定のノードとは別の前記第１ノード集合に属するノードに前記第１メッセージを転送することで、その転送先のノードに対して前記第２ノード集合に向けて前記第１メッセージをフラッディングさせ、
前記第２メッセージを受信した前記第２ノード集合に属する第２ネイバが、自身から前記第１ノード集合に向けて前記第２メッセージをフラッディングさせることを特徴とする。
【００１０】
これにより、第１ノード集合と第２ノード集合との両側でそれぞれ伝搬メッセージをフラッディングさせることにより、伝搬漏れを無くしつつ、伝搬のメッセージ量を適切に削減することができる。
【００１１】
本発明は、前記第１ノード集合に属する前記所定のノードが、新しい経路情報を含む前記伝搬メッセージを作成するときに、フラッディングをさせない経路伝搬範囲を示す第１ＴＴＬ値と、フラッディングをさせる経路伝搬範囲を示す第２ＴＴＬ値とをそれぞれ含めた前記伝搬メッセージを作成し、
各前記伝搬メッセージを受信したノードが、前記第１ＴＴＬ値と前記第２ＴＴＬ値とをそれぞれ減算した後、前記第１ＴＴＬ値と前記第２ＴＴＬ値との値に応じて、フラッディングをさせずに前記伝搬メッセージを転送するか、前記伝搬メッセージをフラッディングするか、受信した前記伝搬メッセージを破棄するかを決定することを特徴とする。
【００１２】
これにより、リンクステート型プロトコルのフラッディングを抑制するためにフラッディングを用いない伝搬範囲と、フラッディングを用いる伝搬範囲を指定することで、不要な経路伝搬のメッセージを抑制できる。
【００１３】
本発明は、前記第１ノード集合に属する前記所定のノードが、あらかじめ設定されている冗長度に応じて、前記第１メッセージと、前記第２メッセージとをそれぞれ複数個作成し、それらの作成した前記伝搬メッセージを別々のネイバに送信することを特徴とする。
【００１４】
これにより、メッセージの損失に向けてメッセージの冗長度を指定できるようにすることで、同時に複数箇所で障害が発生してしまう多重障害にも対処することができる。
【発明の効果】
【００１５】
本発明によれば、経路情報を伝搬するときに、伝搬漏れを無くしつつ、伝搬のメッセージ量を適切に削減することができる。
【図面の簡単な説明】
【００１６】
【図１】本実施形態に係わるリーフからスパインにＬＦ−ＬＳＡを送信する例を示す。
【図２】本実施形態に係わるリーフからスパインにＳＦ−ＬＳＡを送信する例を示す。
【図３】本実施形態に係わる経路伝搬システムの各ノード（リーフ、スパイン）の構成図である。
【図４】本実施形態に係わる各ノードの物理インタフェースの設定情報の一例である。
【図５】本実施形態に係わるＬＳＡのパケットフォーマットの一例である。
【図６】本実施形態に係わるＬＳＡを最初に送信するノードの処理例である。
【図７】本実施形態に係わるＬＳＡを受信したノードの処理例である。
【図８】3-stage-CLOS型ネットワークトポロジにおけるＬＳＡの送信の様子を示す。
【発明を実施するための形態】
【００１７】
以下、本発明の一実施形態について、図面を参照して詳細に説明する。
【００１８】
まず、本実施形態の概要説明として、新たに導入したＬＳＡのフラッディングの主な特徴を３つ説明する。
（特徴１）リンクステート型プロトコルにおけるＬＳＡとして、以下の２種類のＬＳＡを別々のネイバに送信すること。
第１メッセージ：ＬＳＡの送信元と同じ側でフラッディングを行うＬＦ−ＬＳＡ（Long Flooding LSA）。なお、（ＬＳＡの送信元）→（送信元とは別の側のノード）→（送信元と同じ側のノードでフラッディング）のように、長く（２ホップ）転送されるＬＳＡなので、「Long Flooding LSA」という名称にした。
第２メッセージ：ＬＳＡの送信元と別の側でフラッディングを行うＳＦ−ＬＳＡ（Short Flooding LSA）。なお、（ＬＳＡの送信元）→（送信元とは別の側のノードでフラッディング）のように、短く（１ホップ）転送されるＬＳＡなので、「Short Flooding LSA」という名称にした。
【００１９】
まず、第１ノード集合（リーフ集合）のリーフ（所定のノード）が障害を検知し、そのリーフがＬＳＡを作成して、第２ノード集合（スパイン集合）にＬＳＡを送信する場合、以下の通りである。
・ＬＦ−ＬＳＡは、「リーフ集合（所定のノード）→スパイン集合→リーフ集合」にユニキャストで転送され、その転送先のリーフ集合からフラッディングされる。
・ＳＦ−ＬＳＡは、「リーフ集合（所定のノード）→スパイン集合」にユニキャストで転送され、その転送先のスパイン集合からフラッディングされる。
【００２０】
一方、第１ノード集合（スパイン集合）のスパイン（所定のノード）が障害を検知し、そのスパインがＬＳＡを作成して、第２ノード集合（リーフ集合）にＬＳＡを送信する場合、以下の通りである。
・ＬＦ−ＬＳＡは、「スパイン集合（所定のノード）→リーフ集合→スパイン集合」にユニキャストで転送され、その転送先のスパイン集合からフラッディングされる。
・ＳＦ−ＬＳＡは、「スパイン集合（所定のノード）→リーフ集合」にユニキャストで転送され、その転送先のリーフ集合からフラッディングされる。
【００２１】
（特徴２）２種類のＬＳＡ（ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡ）は、それぞれ内部に第１ＴＴＬ値＝ＮＦ−ＴＴＬ（Non Flooding TTL）、第２ＴＴＬ値＝Ｆ−ＴＴＬ（Flooding TTL）という２種類のＴＴＬ（Time to Live）値を保持すること。（特徴１）の２種類のＬＳＡの違いは、このＴＴＬ値の初期値の違いである。
ＬＦ−ＬＳＡのＴＴＬ値初期値＝「ＮＦ−ＴＴＬ＝２、Ｆ−ＴＴＬ＝３」（２ホップをユニキャストで転送し、その後の３ホップ目でフラッディングを行う、の意味）
ＳＦ−ＬＳＡのＴＴＬ値初期値＝「ＮＦ−ＴＴＬ＝１、Ｆ−ＴＴＬ＝２」（１ホップをユニキャストで転送し、その後の２ホップ目でフラッディングを行う、の意味）
【００２２】
（特徴３）経路伝搬システムの各ノード（リーフ、スパイン）は、ネイバからＬＳＡを受信したときに、ＴＴＬ値をもとにした以下のルールに従うこと。このルールの詳細は、図７のフローチャートで説明する。
（ルール１）受信したＬＳＡのＮＦ−ＴＴＬの値とＦ−ＴＴＬの値とをそれぞれ１つずつ減らす。以下のルール２以降は減らした後のＴＴＬ値で判断する。
（ルール２）ＮＦ−ＴＴＬ＞０なら、１台の他ネイバ（ルータＩＤが最小であるネイバＮ１）にユニキャストで転送する。
（ルール３）ＮＦ−ＴＴＬ＝０かつＦ−ＴＴＬ＞０なら、受信元以外の他ネイバの集合に対して、通常のフラッディングで伝搬する。
（ルール４）ＮＦ−ＴＴＬ＝０かつＦ−ＴＴＬ＝０なら、受信したＬＳＡの転送を行わない。
【００２３】
以下、図１，図２では、図８の符号９０１、９０２に例示したような、３台のリーフと３台のスパインとが接続されるCLOS型ネットワークの経路伝搬システムにおいて、リーフ２１とスパイン１１の間に障害があった場合を例示する。
なお、経路伝搬システムの各装置（リーフまたはスパインである各ノード）は、それぞれＣＰＵ（Central Processing Unit）と、メモリと、ハードディスクなどの記憶手段（記憶部）と、ネットワークインタフェースとを有するコンピュータとして構成される。
このコンピュータは、ＣＰＵが、メモリ上に読み込んだプログラム（アプリケーションや、その略のアプリとも呼ばれる）を実行することにより、各処理部により構成される制御部（制御手段）を動作させる。
【００２４】
以下では、あくまでリーフ２１（所定のノード）が障害を検知し、そのリーフ２１がＬＳＡを作成して送信する例を示す。実際は、スパイン１１発の情報もあるが、そのスパイン１１発の情報については記載を省略する。
図１では、リーフ２１からスパイン１２にＬＦ−ＬＳＡを送信する例を示す。
図２では、リーフ２１からスパイン１３にＳＦ−ＬＳＡを送信する例を示す。
【００２５】
図１のＬＦ−ＬＳＡは、リーフ２１→スパイン１２→リーフ２２のように２ホップ分ユニキャストとして送信し（図１の符号１０１の破線矢印）、その後リーフ２２側で１ホップ分フラッディングする（図１の符号１０１の太線実線矢印）ＬＳＡである。このように、リーフ２１発のＬＦ−ＬＳＡは、リーフ２２の側でフラッディングする。
【００２６】
以下、テーブル１０２を参照して、１ホップずつの詳細説明を行う。
テーブル１０２の１行目に示すように、リーフ２１から送信されるＬＦ−ＬＳＡには「ＮＦ−ＴＴＬ＝２、Ｆ−ＴＴＬ＝３」が設定されている。ＮＦ−ＴＴＬ＞０なので、ここではフラッディングされずに（Flooding＝×）、スパイン１２に向けてユニキャストされる（ルール２）。
【００２７】
テーブル１０２の２行目に示すように、スパイン１２から送信されるＬＦ−ＬＳＡでは、受信時のＮＦ−ＴＴＬおよびＦ−ＴＴＬからそれぞれＴＴＬ値が１ずつ減算された結果（ルール１）、「ＮＦ−ＴＴＬ＝１、Ｆ−ＴＴＬ＝２」となる。ＮＦ−ＴＴＬ＞０なので、ここでもフラッディングされずに（Flooding＝×）、リーフ２２に向けてユニキャストされる（ルール２）。なお、送信先のリーフ２２は、スパイン１２からみた送信元以外の最小のルータＩＤを持つネイバである。
【００２８】
テーブル１０２の３，４行目に示すように、リーフ２２から送信されるＬＦ−ＬＳＡでは、受信時のＮＦ−ＴＴＬおよびＦ−ＴＴＬからそれぞれＴＴＬ値が１ずつ減算された結果、「ＮＦ−ＴＴＬ＝０、Ｆ−ＴＴＬ＝１」となる。ＮＦ−ＴＴＬ＝０かつＦ−ＴＴＬ＞０なので、ここで送信元以外の各ネイバ（スパイン１１、スパイン１３）に対してフラッディング（Flooding＝○）される（ルール３）。
なお、スパイン１１、スパイン１３は、受信時のＮＦ−ＴＴＬおよびＦ−ＴＴＬからそれぞれＴＴＬ値が１ずつ減算された結果、「ＮＦ−ＴＴＬ＝０（０からの減算不可）、Ｆ−ＴＴＬ＝０」となり、これ以上転送しない（ルール４）。
【００２９】
図２のＳＦ−ＬＳＡは、図１のＬＦ−ＬＳＡが送信された後に送信されるＬＳＡである。ＳＦ−ＬＳＡは、リーフ２１→スパイン１３のように１ホップ分ユニキャストとして送信し（図２の符号１１１の破線矢印）、その後スパイン１３側で１ホップ分フラッディングする（図２の符号１１１の太線実線矢印）ＬＳＡである。このように、リーフ２１発のＳＦ−ＬＳＡは、スパイン１３の側でフラッディングする。
【００３０】
以下、テーブル１１２を参照して、１ホップずつの詳細説明を行う。
テーブル１１２の１行目に示すように、リーフ２１から送信されるＳＦ−ＬＳＡには「ＮＦ−ＴＴＬ＝１、Ｆ−ＴＴＬ＝２」が設定されている。ＮＦ−ＴＴＬ＞０なので、ここではフラッディングされずに（Flooding＝×）、スパイン１３に向けてユニキャストされる（ルール２）。
【００３１】
テーブル１１２の２，３行目に示すように、スパイン１３から送信されるＳＦ−ＬＳＡでは、受信時のＮＦ−ＴＴＬおよびＦ−ＴＴＬからそれぞれＴＴＬ値が１ずつ減算された結果、「ＮＦ−ＴＴＬ＝０、Ｆ−ＴＴＬ＝１」となる。ＮＦ−ＴＴＬ＝０かつＦ−ＴＴＬ＞０なので、ここで送信元以外の各ネイバ（リーフ２２、リーフ２３）に対してフラッディング（Flooding＝○）される（ルール３）。
なお、リーフ２２、リーフ２３は、受信時のＮＦ−ＴＴＬおよびＦ−ＴＴＬからそれぞれＴＴＬ値が１ずつ減算された結果、「ＮＦ−ＴＴＬ＝０（０からの減算不可）、Ｆ−ＴＴＬ＝０」となり、これ以上転送しない（ルール４）。
【００３２】
図３は、経路伝搬システムの各ノード（リーフ、スパイン）の構成図である。
各ノードは、コマンド入力部５１と、情報保持部５２と、ＯＳＰＦ処理部５３と、物理インタフェース６１と、パケット送信部６２と、パケット受信部６３とを有する。
コマンド入力部５１は、ＣＬＩ（Command Line Interface）などで物理インタフェース６１の設定情報などの入力を受け付ける。
情報保持部５２は、コマンド入力部５１が受け付けた物理インタフェース６１の設定情報などを保持する。
ＯＳＰＦ処理部５３は、既存の方法のＯＳＰＦ処理に加えて、前記（ルール１）〜（ルール４）に示したＬＳＡの受信処理（詳細は図７）と、そのＬＳＡの生成元での送信処理（詳細は図６）とを実行する。なお、ＯＳＰＦはあくまでリンクステート型のプロトコルの一例であり、他のプロトコルを用いてもよい。
【００３３】
物理インタフェース６１は、ＬＳＡなどを含むパケットを送受信するためのインタフェースである。
パケット送信部６２は、ＯＳＰＦ処理部５３によるＬＳＡの送信処理（詳細は図６）により送信されるＬＳＡが通知されると、そのＬＳＡを物理インタフェース６１経由でネイバのノードに送信させる。
パケット受信部６３は、物理インタフェース６１からＬＳＡを受信すると、その受信したＬＳＡをＯＳＰＦ処理部５３に通知することで、ＬＳＡの受信処理（詳細は図７）を起動させる。
【００３４】
図４のテーブル１２１は、図１に例示したリーフが３台、スパインが３台のＣＬＯＳトポロジにおける、各ノードの物理インタフェース６１の設定情報の一例である。
第１列「装置」は、どのノードの設定情報なのかを示す。
第２列「ＲＩＤ」は、「装置」に割り当てられたルータＩＤである。以下、ネイバ数をｎとしてルータＩＤが最小のネイバをＮ１、その次に大きいネイバをＮ２として、ルータＩＤが最大のネイバをＮｎとする。
第３列「ＩＦ名」は、「装置」が有するインタフェースごとの名称である。以下、第３列〜第５列は、インタフェースごとに（１台で３つごとに）別々である。
第４列「ＩＦアドレス」は、「／３０」のネットマスクを持つリンクのＩＰアドレスである。各リンクに記載されている”．ｘｘ”はＩＰアドレスの第４オクテットである。第１〜第３オクテットは記載を省略している。従って各リンクは／３０の独立したＬａｙｅｒ３のリンクであり異なったサブネットになっている。ＯＳＰＦにおいてPoint-to-PointのLink TypeとすればＤＲ（Designated Router）／ＢＤＲ（Backup Designated Router）の選出を行わないようになる。
第５列「ＩＦ接続先」は、インタフェースの接続先となる装置を示す。この「ＩＦ接続先」は説明をわかりやすくするために記載したが、ノードの設定ファイルには記載しなくてもよい。
【００３５】
図４のテーブル１２２に物理インタフェース６１の設定情報を示す。ＯＳＰＦであれば様々な設定項目が考えられる。
第１列「ＩＦ名」は、テーブル１２１の第３列と同じである。
第２列「ＯＳＰＦ」は、ＯＳＰＦを動作させるインタフェースか（○有効）、否か（×無効）を示す。
第３列「Metric」は、ＯＳＰＦの設定パラメータであり、リンクのコストを示す。
第４列「伝搬範囲抑制」は、図１，２で前記したように、２種類のＬＳＡを使い分けてＬＳＡの伝搬範囲を抑制する機能を使用するか（○）否か（×）を示す。
【００３６】
図５の符号１３１は、ＬＳＡのパケットフォーマットを示す。「VEB」と「# Links」との間に位置する未使用（常に０）となっている８ｂｉｔのフィールドを、前記した２種類のＴＴＬ値の格納場所に使用する。
符号１３２は、未使用の８ｂｉｔのフィールドの利用方法の一例を示す。
上位２ｂｉｔ「フラグ（Ｆｌａｇ）」とは、８ｂｉｔのフィールドを伝搬範囲情報として利用するか（Ｆｌａｇ＝１）、利用せずにこれまでの利用方法とするか（Ｆｌａｇ＝０）を示す。
次に続く３ｂｉｔ「ＮＦ−ＴＴＬ（Non Flooding TTL）」は、フラッディングを行わない伝搬範囲のホップ数を示す。
最後の下位３ｂｉｔ「Ｆ−ＴＴＬ（Flooding TTL）」は、従来と同じようにフラッディングを行う伝搬範囲のホップ数を示す。
なお、前記した未使用の８ｂｉｔのフィールドの利用方法以外にも、他に常に０になっているフィールドやオプションのフィールドを新設して用いてもよい。また、ＮＦ−ＴＴＬ、Ｆ−ＴＴＬのｂｉｔ数も３ｂｉｔずつに限定されず、より多いｂｉｔ数を採用してもよい。
【００３７】
図６は、ＬＳＡの送信契機においてＬＳＡを最初に送信するノードの処理例である。例えば、図１，図２では、リーフ２１がこの図６の処理を実行するノードに該当する。なお、ＬＳＡの送信契機は、例えば、リンク切断・接続などリンク状態に変更があったときや、ネットワークが安定している場合においてもLSRefreshTimeを迎えたときなどである。
【００３８】
なお、この図６の処理に使用される各パラメータは、以下の意味である。
定数ｎは、自身のノードからみたネイバ数を示す。図１ではｎ＝３である。
カウンタ変数ｘは、現在作成しているＬＳＡが、何番目のネイバ（Ｎｘ）に送信されるＬＳＡかを示す。よって、１≦ｘ≦ｎの範囲でｘが推移する。
ここで、ネイバ（Ｎｘ）について、リンク状態に変更があったときは、その変更後のネットワークトポロジをもとに再割り当てされる。例えば、リーフ２１からみて、図８の障害前の状態では、ネイバが以下の状態であったとする。
ネイバＮ１＝スパイン１１
ネイバＮ２＝スパイン１２
ネイバＮ３＝スパイン１３（合計ｎ＝３）
そして、図１に示すように、スパイン１１と接続するリンクが切断されてしまった後は、以下のようにネイバの集合が変化する。換言すると、図６の各処理において、通信不可となったネイバは、スキップされる。
ネイバＮ１＝スパイン１２
ネイバＮ２＝スパイン１３（合計ｎ＝２）
【００３９】
カウンタ変数ｙは、現在作成しているＬＳＡが、何番目のＬＦ−ＬＳＡかを示す。
カウンタ変数ｚは、現在作成しているＬＳＡが、何番目のＳＦ−ＬＳＡかを示す。
冗長度Ｒは、コマンド入力部５１から情報保持部５２に事前登録された定数であり、２種類のＬＳＡをいくつずつ（何台のネイバに対して）送信するかを示す。Ｒは自然数（０を含まない正の整数）かつＲ≦ｎとする。図１では、冗長度Ｒ＝１とした例を示し、最小のネイバに対してのみＬＳＡ送信している。
【００４０】
Ｓ１０１において、ＯＳＰＦ処理部５３は、LSRequestを伴わない自生成ＬＳＡのLSUpdateを生成する。
Ｓ１０２において、ＯＳＰＦ処理部５３は、カウンタ変数の初期化（ｘ＝１、ｙ＝０、ｚ＝０）を行う。
Ｓ１１１において、ＯＳＰＦ処理部５３は、ｘ≦ｎではないときは、つまり送信対象のネイバが無くなったときには、処理を終了する。
【００４１】
Ｓ１１２において、ＯＳＰＦ処理部５３は、Ｎｘのインタフェースに対して、図４のテーブル１２２の第４列「伝搬範囲抑制」が指定されていない（×）ときには、ネイバＮｘに対して、ＬＦ−ＬＳＡでもＳＦ−ＬＳＡでもない、既存の方法（通常のフラッディング）でＬＳＡを伝搬し（Ｓ１２１）、処理をＳ１１５に進める。
Ｓ１１３において、ＯＳＰＦ処理部５３は、ｙ＜Ｒなら、ネイバＮｘに対してＬＦ−ＬＳＡを送信した後（Ｓ１２２）、ｙの値を１つ増加し（Ｓ１２３）、処理をＳ１１５に進める。
Ｓ１１４において、ＯＳＰＦ処理部５３は、ｚ＜Ｒなら、ネイバＮｘに対してＳＦ−ＬＳＡを送信した後（Ｓ１２４）、ｚの値を１つ増加し（Ｓ１２５）、処理をＳ１１５に進める。
Ｓ１１５において、ＯＳＰＦ処理部５３は、ｘの値を１つ増加し、処理をＳ１１１に戻す。
【００４２】
例えば、ネイバ数ｎ＝５で冗長度Ｒ＝２の場合、前記の図６で示したように、以下の順序で各ＬＳＡが送信される。
ｘ＝１：ＬＦ−ＬＳＡをネイバＮ１に送信
ｘ＝２：ＬＦ−ＬＳＡをネイバＮ２に送信
ｘ＝３：ＳＦ−ＬＳＡをネイバＮ３に送信
ｘ＝４：ＳＦ−ＬＳＡをネイバＮ４に送信
つまり、冗長度Ｒ＝２なので、ＬＦ−ＬＳＡが２つ分冗長化されるとともに、ＳＦ−ＬＳＡも２つ分冗長化される。
【００４３】
一方、ネイバ数ｎ＝５で冗長度Ｒ＝３の場合（２×冗長度Ｒ＞ｎ）、ＬＦ−ＬＳＡの送信が優先され、ＳＦ−ＬＳＡの送信数が冗長度Ｒ＝３よりも少なくなる。
ｘ＝１：ＬＦ−ＬＳＡをネイバＮ１に送信
ｘ＝２：ＬＦ−ＬＳＡをネイバＮ２に送信
ｘ＝３：ＬＦ−ＬＳＡをネイバＮ３に送信
ｘ＝４：ＳＦ−ＬＳＡをネイバＮ４に送信
ｘ＝５：ＳＦ−ＬＳＡをネイバＮ５に送信
【００４４】
さらに、ネイバ数ｎ＝５であるのに冗長度Ｒ＝６が設定されてしまった場合（冗長度Ｒ＞ｎ）、各ＬＳＡが全ネイバに送信される。
ｘ＝１：ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡをネイバＮ１に送信
ｘ＝２：ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡをネイバＮ２に送信
ｘ＝３：ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡをネイバＮ３に送信
ｘ＝４：ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡをネイバＮ４に送信
ｘ＝５：ＬＦ−ＬＳＡ、ＳＦ−ＬＳＡをネイバＮ５に送信
【００４５】
図７は、図６で送信されたＬＳＡまたは図７で転送されたＬＳＡを受信したノードの処理例である。
Ｓ２０１において、ＯＳＰＦ処理部５３は、ＬＳＡのパケットを受信する。
Ｓ２０２において、ＯＳＰＦ処理部５３は、Ｓ２０１で受信したパケットの伝搬範囲を示すフラグ（Ｆｌａｇ）が有効（Ｆｌａｇ＝１）ではないときには、Ｓ１１２と同様に、通常のフラッディングで受信したＬＳＡを伝搬（転送）する（Ｓ２１１）。
Ｓ２０３において、ＯＳＰＦ処理部５３は、Ｓ２０１で受信したＬＳＡ内のＮＦ−ＴＴＬの値と、Ｆ−ＴＴＬの値とをそれぞれ１つずつ減少させる（ルール１）。
Ｓ２０４において、ＯＳＰＦ処理部５３は、ＮＦ−ＴＴＬ＞０なら、前記のルール２に従い、Ｓ２０３でＴＴＬ値を減少させたＬＳＡを１台の他ネイバにユニキャストで転送する。この転送先の他ネイバについて、以下に示すように、Ｓ２０１のＬＳＡの送信元をスキップする。Ｓ２０１のＬＳＡの送信元がＮ１であるなら（Ｓ２１２ａでＹｅｓ）、転送先をネイバＮ２とする（Ｓ２１２ｃ）。送信元がＮ１でないなら、転送先をルータＩＤが最小であるネイバＮ１とする（Ｓ２１２ｂ）。
【００４６】
なお、転送先をネイバＮ１またはＮ２とする代わりに、ＬＳＡの送信元が図６のＬＳＡ送信処理時（Ｓ１２２，Ｓ１２４）にＬＳＡに含めておいたカウンタ変数ｙをもとに、以下の計算式などで転送先を決めてもよい。
ＬＳＡの転送先＝ネイバＮ（１＋ｙ）。ただし、Ｎ１〜ＮｙのうちにＬＳＡの送信元が存在するときは、転送先を１つ繰り下げてネイバＮ（２＋ｙ）とする。
これにより、ＬＳＡの転送先が冗長度Ｒに応じて別々のネイバにばらけるので、局所的な障害を迂回できる。
【００４７】
Ｓ２０５において、ＯＳＰＦ処理部５３は、Ｆ−ＴＴＬ＞０なら、前記のルール３に従い、Ｓ２０３でＴＴＬ値を減少させたＬＳＡを、Ｓ２１１と同様に、通常のフラッディングで伝搬（転送）する（Ｓ２１３）。
【００４８】
以上説明した本実施形態では、経路交換技術であるリンクステート型プロトコルにおけるＬＳＡの伝搬機能を保ちつつ、その伝搬メッセージを適切に減らすためのＯＳＰＦ処理部５３を示した。このＯＳＰＦ処理部５３は、ＬＳＡの発側でフラッディングを行うＬＦ−ＬＳＡと、ＬＳＡの発側とは別の側でフラッディングを行うＳＦ−ＬＳＡとを別々のネイバに併送する。このように２種類のＬＳＡを使い分けることにより、両方の側でフラッディングを発生させることができ、ＬＳＡの送信漏れを抑制することができる上、重複したＬＳＡの送信も抑制できる。
さらに、ノードへの設定項目として、冗長度Ｒを設けることにより、同時に複数箇所で障害が発生してしまう多重障害にも対処することができる。
【符号の説明】
【００４９】
１１〜１３  スパイン
２１〜２３  リーフ
５１    コマンド入力部
５２    情報保持部
５３    ＯＳＰＦ処理部
６１    物理インタフェース
６２    パケット送信部
６３    パケット受信部
【図１】
2018032894.tif 000003
【図２】
2018032894.tif 000004
【図３】
2018032894.tif 000005
【図４】
2018032894.tif 000006
【図５】
2018032894.tif 000007
【図６】
2018032894.tif 000008
【図７】
2018032894.tif 000009
【図８】
2018032894.tif 000010