JP4417896B2

JP4417896B2 - Detour route calculation device, program, detour route calculation server, router, and detour route calculation method and system

Info

Publication number: JP4417896B2
Application number: JP2005258509A
Authority: JP
Inventors: 雅史清水; 賢高橋; 正昭高木; 正祥安川
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2005-09-06
Filing date: 2005-09-06
Publication date: 2010-02-17
Anticipated expiration: 2025-09-06
Also published as: JP2007074312A

Description

本発明は、迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムに係り、特に、Point-to-MultiPoint(P2MP)Trafic Engineering(TE)Label Switched Path(LSP)を設定可能なMPLSネットワーク技術における、P2MP TE LSPのIngress（ソース）ノードと複数Egress（リーフ）ノードを結ぶPrimaryパスに対して、End-End間でのP2MP迂回パスを設定するための迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムに関する。 The present invention relates to a detour path calculation device, a program, a detour path calculation server, a router, and a detour path calculation method and system, and in particular, sets a point-to-multipoint (P2MP) traffic engineering (TE) label switched path (LSP). Detour path calculation device for setting P2MP detour path between End-End for Primary path connecting Ingress (source) node and multiple Egress (leaf) nodes of P2MP TE LSP in possible MPLS network technology, and The present invention relates to a program, a detour route calculation server, a router, and a detour route calculation method and system.

P2MP TE LSPに対して、P2P TE LSPの迂回パスを設定する方式があるが、P2MP TE LSPに対して、P2MP TE LSPの迂回パスを設定する方式は今まで提案されておらず、Primary P2MP TE LSPを設定しているリンクが故障などを引き起こした場合に、迂回させる技術がない。 Although there is a method for setting a P2P TE LSP bypass path for P2MP TE LSP, a method for setting a P2MP TE LSP bypass path for P2MP TE LSP has not been proposed so far, and Primary P2MP TE There is no technology to detour when a link with LSP causes a failure.

なお、P2Pのパスを設定するためのプロトコル規定（例えば、非特許文献１参照）やP2MPのパスを設定するためのプロトコル規定（例えば、非特許文献２参照）がある。
http://www.ietf.org/rfc3209.txt?number=3209 http://ietf.org/internet-drafts/draft-ietf-mpls-rsvp-te-p2mp-02.txt Note that there are protocol specifications for setting a P2P path (for example, see Non-Patent Document 1) and protocol specifications for setting a P2MP path (for example, see Non-Patent Document 2).
http://www.ietf.org/rfc3209.txt?number=3209 http://ietf.org/internet-drafts/draft-ietf-mpls-rsvp-te-p2mp-02.txt

上記のように、P2MP TE LSPに対して、P2MP TE LSPの迂回パスを設定する方式がないため、仮に、P2MP TE LSPに対して、P2P TE LSPの迂回パスを設定すると、リンク使用効率が悪くなるという問題がある。 As described above, there is no method for setting a P2MP TE LSP bypass path for P2MP TE LSP. Therefore, if a P2P TE LSP bypass path is set for P2MP TE LSP, the link usage efficiency is poor. There is a problem of becoming.

また、従来の迂回パス計算では、迂回パスを求められない場合は、解無しとしてしまうため、それ以外の迂回パスを求められたそれ以外の多くのユーザに影響を及ぼしてしまうという問題がある。 Further, in the conventional bypass path calculation, if no bypass path can be obtained, there is no solution, so that there is a problem in that it affects many other users who have obtained other bypass paths.

本発明は、上記の点に鑑みなされたもので、P2MP TE LSPによるP2MP TE LSPのための迂回パスを設定することが可能で、かつ、迂回パスを求められないような状況においても必ず解を出すことが可能な迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムを提供することを目的とする。 The present invention has been made in view of the above points, and it is possible to set a detour path for P2MP TE LSP by P2MP TE LSP and always solve the problem even in a situation where a detour path cannot be obtained. It is an object of the present invention to provide a detour route calculation device and program, a detour route calculation server and router, and a detour route calculation method and system that can be issued.

図１は、本発明の原理構成図である。 FIG. 1 is a principle configuration diagram of the present invention.

本発明（請求項１）は、接続関係情報やリンクコスト情報を有し、P2MPパスを設定するための迂回経路計算を行う迂回経路計算装置であって、
経路設定の対象となるノード情報とリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSPに対して、リンク集合からP2MP プライマリパスを通る物理リンクと物理ノードを除いて、該入口ノードから該出口ノードまで、該P2MPプライマリパスと交わらないように残りのノードとリンクから、該入口ノードから該出口ノードまでのP2MP迂回パスを計算する迂回パス計算手段４０と、
迂回パス計算手段４０の結果を格納する記憶手段２０と、を有し、
迂回パス計算手段４０は、
迂回パスが必要となるプライマリパスに対して、リンク集合から該プライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する第１の迂回パス計算手段と、
第１の迂回パス計算手段で計算された経路に基づいて、P2MP迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
第１の迂回パス計算手段において、出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、第２の確認手段を、入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、を含む。 The present invention (Claim 1 ) is a detour route calculation apparatus that has connection relation information and link cost information and performs detour route calculation for setting a P2MP path,
When the node information and link set for route setting, and information on the entry node and multiple exit nodes of the P2MP path that requires a detour path, are input to the P2MP TE LSP that requires the detour path , Except for physical links and physical nodes passing through the P2MP primary path from the link set, from the ingress node to the egress node, from the remaining nodes and links so as not to intersect the P2MP primary path, from the ingress node to the egress node Detour path calculation means 40 for calculating the P2MP detour path up to
Storage means 20 for storing the result of the detour path calculation means 40,
Periphrastic Kai path calculation means 40,
For the primary path that requires a detour path, from the link set to the exit node to the exit node using the remaining links and nodes excluding the physical link and physical node through which the primary path passes. A first detour path calculation means for calculating a shortest path or a minimum path by a path calculation algorithm and calculating a P2MP detour path that does not intersect the primary path from the ingress node to the egress node;
First bypass path setting means for setting a P2MP bypass path to a node on the route based on the route calculated by the first bypass path calculating means;
In the first detour path calculation means, when the exit node that cannot reach the route exists in the exit node and the route is not calculated, the entry node determines the route of the exit node that cannot reach the route. A first checking means for calculating a shortest route or a minimum route again by a route calculation algorithm from a primary path that passes through to a node that is one hop upstream and an exit node that is reachable, and confirming whether the route is reachable; ,
The route calculation algorithm, when was paths reachable from the ingress node, the route from the primary path through the egress node was route unreachable to the exit node was possible one hop upstream node and path arrival Sets a P2MP detour path to a node on the route based on the route calculated by the route calculation algorithm, and for the route from the node upstream of k hops to the exit node, Second detour path setting means for setting a P2MP detour path to a node on the path so as to pass the same path as the primary path;
If the route cannot be reached by the route calculation algorithm, from the entry node to the node upstream of k (k = 2, 3,..., N) hops from the primary path through the exit node that was not reachable. On the other hand, a second confirmation means for performing route computation again by the route computation algorithm and confirming whether the route is reachable,
Further, if the route is not reachable , the second confirmation means repeats n hops until reaching the entry node, and
If the route is reachable in the repetitive means, the node and route upstream from the primary node by k (k = 2, 3 ,..., N) hops from the primary path through which the route is unreachable. For the route to the egress node that was reachable, a P2MP detour path is set for the node on the route based on the route calculated by the route calculation algorithm, and the unreachable from the node upstream of k hops. For the route to the exit node, a P2MP detour path is set in the node on the route so that it passes the same route as the primary path, and the route cannot be reached until it reaches the entry node (k = n) The same route as the primary path from the ingress node to the egress node is set in the node on the route as a route passing through the P2MP detour path. And a third alternative path setting means for, the.

本発明（請求項２）は、経路計算結果を格納する記憶手段を有するコンピュータを、
請求項１記載の迂回経路計算装置として機能させるプログラムである。 The present invention (Claim 2 ) provides a computer having storage means for storing a route calculation result.
A program to function as a bypass route calculation apparatus according to claim 1 Symbol placement.

本発明（請求項３）は、迂回パスが必要となるP2MP入口ノードと複数の出口ノードを有するネットワークにおいて、迂回パスを設定する迂回経路計算サーバであって、
請求項１記載の迂回経路計算装置と、
ネットワークのノードに対して迂回経路計算装置で求められた迂回P2MPパスの情報を送信する手段と、を有する。 The present invention (Claim 3 ) is a bypass route calculation server for setting a bypass path in a network having a P2MP entrance node and a plurality of exit nodes that require a bypass path,
The detour route calculation device according to claim 1 ,
Means for transmitting information on the detour P2MP path obtained by the detour route calculation apparatus to the nodes of the network.

本発明（請求項４）は、迂回パスが必要となるルータであって、
請求項１記載の迂回経路計算装置と、
迂回経路計算装置から取得した迂回経路情報を格納するデータベースと、を有する。 The present invention (Claim 4 ) is a router that requires a detour path,
The detour route calculation device according to claim 1 ,
And a database for storing detour route information acquired from the detour route calculation device.

図２は、本発明の原理説明図である。 FIG. 2 is a diagram illustrating the principle of the present invention.

本発明は、ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算方法であって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSPに対して、リンク集合からP2MP プライマリパスを通る物理リンクと物理ノードを除いて（ステップ２）、該入口ノードから該出口ノードまで、該P2MPプライマリパスと交わらないように残りのノードとリンクから、該入口ノードから該出口ノードまでのP2MP迂回パスを計算する迂回パス計算ステップ（ステップ３）と、
迂回パス計算ステップの結果を記憶手段に格納するステップ（ステップ４）と、を行う。 This onset Ming has a detour route calculation device capable of setting a point-to-multipoint (P2MP) path, in a network in which the device has a connection relation information and link cost information, in the detour route calculation method for performing a bypass route calculation There,
When the node and link set to be routed, and the information of the entry node and the plurality of exit nodes of the P2MP path that requires a detour path are input, for the P2MP TE LSP that requires the detour path, Excluding physical links and physical nodes that pass the P2MP primary path from the link set (step 2), from the ingress node to the egress node, from the remaining nodes and links so as not to intersect the P2MP primary path, from the ingress node A detour path calculating step (step 3) for calculating a P2MP detour path to the egress node;
A step (step 4) of storing the result of the bypass path calculation step in the storage means is performed.

本発明（請求項５）はポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算方法であって、
迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードが特定されると、
迂回パスが必要となるP2P TE LSPに対して、リンク集合からプライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する第１の迂回パス計算ステップと、
第１の迂回パス計算ステップで計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定する第１の迂回パス設定ステップと、
出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認ステップと、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定ステップと、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認ステップと、
さらに、経路到達不可能であれば、第２の確認ステップを、入口ノードに到達するまでｎホップ分繰り返す繰り返しステップと、
繰り返しステップにおいて、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定ステップと、を行う。 The present invention (Claim 5 ) has a detour route calculation device capable of setting a point-to-multipoint (P2MP) path, and a detour route for performing detour route calculation in a network in which the device has connection relation information and link cost information A calculation method,
When the ingress node and a plurality of egress nodes of the P2MP path periphrastic Kai path is required is identified,
For P2P TE LSPs that require detour paths, use the remaining links and nodes excluding the physical links and physical nodes through which the primary path passes from the link set, and from the ingress node where the primary path is set to the egress node Calculating a shortest path or a minimum path by a path calculation algorithm, and calculating a P2MP bypass path that does not intersect the primary path from the entry node to the exit node;
A first bypass path setting step for setting a P2MP bypass path to a node on the route based on the route calculated in the first bypass path calculation step;
If the exit node that cannot reach the route exists in the exit node and the route is not calculated, the node that is one hop upstream from the primary path through the exit node that has become unreachable from the entrance node And a first confirmation step of calculating the shortest route or the minimum route again by the route calculation algorithm and checking whether the route is reachable up to the exit node where the route was reachable,
The route calculation algorithm, when was paths reachable from the ingress node, the route from the primary path through the egress node was route unreachable to the exit node was possible one hop upstream node and path arrival Sets a P2MP detour path to a node on the route based on the route calculated by the route calculation algorithm, and for the route from the node upstream of k hops to the exit node, A second detour path setting step of setting a P2MP detour path to a node on the path so as to pass the same path as the primary path;
If the route cannot be reached by the route calculation algorithm, from the entry node to the node upstream of k (k = 2, 3,..., N) hops from the primary path through the exit node that was not reachable. On the other hand, a second confirmation step for performing route computation again by the route computation algorithm and confirming whether the route is reachable,
Furthermore, if the route is not reachable , the second confirmation step is repeated for n hops until reaching the ingress node; and
If the route is reachable in the repetition step, the node and route upstream from the primary node through the primary path through which the route is unreachable from the primary node by k (k = 2, 3 ,..., N) hops. For the route to the egress node that was reachable, a P2MP detour path is set for the node on the route based on the route calculated by the route calculation algorithm, and the unreachable from the node upstream of k hops. For the route to the exit node, a P2MP detour path is set in the node on the route so that it passes the same route as the primary path, and the route cannot be reached until it reaches the entry node (k = n) For the egress node that is, the same path as the primary path from the ingress node to the egress node is set as a path through the P2MP detour path. A third alternative path setting step of setting, the performing.

本発明（請求項６）は、ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算システムであって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、迂回パスが必要となるP2MP TE LSPに対して、リンク集合からプライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する迂回パス計算手段と、
迂回パス計算手段で計算された経路に基づいて、迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
迂回パス計算手段において、出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、第２の確認手段を、入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、を有する。 The present invention (Claim 6 ) has a detour route calculation device capable of setting a point-to-multipoint (P2MP) path, and performs detour route calculation in a network in which the device has connection relation information and link cost information. A route calculation system,
When the information about the node and link set for which the route is set, and the entry node and multiple exit nodes of the P2MP path that requires a detour path are input, a link is made to the P2MP TE LSP that requires a detour path. The shortest path or the minimum path is calculated by the path calculation algorithm from the entry node to the exit node where the primary path is set, using the physical link that the primary path passes from the set and the remaining links and nodes excluding the physical node. A detour path calculating means for calculating a P2MP detour path that does not intersect with the primary path from the ingress node to the egress node;
First bypass path setting means for setting a bypass path to a node on the route based on the route calculated by the bypass path calculation means;
In the detour path calculation means, when the exit node that cannot reach the route exists in the exit node and the route is not calculated, the primary path through the exit node that has become unreachable from the entrance node A first check means for calculating again the shortest route or the minimum route by the route calculation algorithm and checking whether the route is reachable from the node that is one hop upstream to the exit node that can reach the route;
The route calculation algorithm, when was paths reachable from the ingress node, the route from the primary path through the egress node was route unreachable to the exit node was possible one hop upstream node and path arrival Sets a P2MP detour path to a node on the route based on the route calculated by the route calculation algorithm, and for the route from the node upstream of k hops to the exit node, Second detour path setting means for setting a P2MP detour path to a node on the path so as to pass the same path as the primary path;
If the route cannot be reached by the route calculation algorithm, from the entry node to the node upstream of k (k = 2, 3,..., N) hops from the primary path through the exit node that was not reachable. On the other hand, a second confirmation means for performing route computation again by the route computation algorithm and confirming whether the route is reachable,
Further, if the route is not reachable , the second confirmation means repeats n hops until reaching the entry node, and
If the route is reachable in the repetitive means, the node and route upstream from the primary node by k (k = 2, 3 ,..., N) hops from the primary path through which the route is unreachable. For the route to the egress node that was reachable, a P2MP detour path is set for the node on the route based on the route calculated by the route calculation algorithm, and the unreachable from the node upstream of k hops. For the route to the exit node, a P2MP detour path is set in the node on the route so that it passes the same route as the primary path, and the route cannot be reached until it reaches the entry node (k = n) The same route as the primary path from the ingress node to the egress node is set in the node on the route as a route passing through the P2MP detour path. And a third alternative path setting means for, the.

上記のように本発明によれば、P2MP TE LSPで設定されたプライマリパスに対して、Ingress（入口ノード）から複数のEgressノード（出口ノード）に対して、P2MP TE LSPを迂回パスとして設定することにより、P2MP TE LSPの迂回経路を実現することができる。 As described above, according to the present invention, a P2MP TE LSP is set as a bypass path from an ingress (ingress node) to a plurality of egress nodes (egress nodes) with respect to the primary path set by the P2MP TE LSP. Thus, a detour path of P2MP TE LSP can be realized.

また、P2MP TE LSPのプライマリパス、迂回パスは、P2P TE LSPと比較して多くのリンクに分岐するため、ネットワーク状態によっては完全にプライマリパスと交わらない迂回パスを設計できないケースも考えられる。そこで、本発明は、ネットワーク状態によって最適なP2MP迂回パスを設定することにより、あらゆるネットワーク状態に応じてP2MP TE LSPの迂回経路を実現することができる。 In addition, since the primary path and detour path of P2MP TE LSP branch to many links compared to P2P TE LSP, there may be a case where a detour path that does not completely intersect with the primary path cannot be designed depending on the network state. Therefore, according to the present invention, by setting an optimal P2MP bypass path according to the network state, a P2MP TE LSP bypass path can be realized according to any network state.

さらに、本発明によれば、迂回パスを求められないような状況においても、条件緩和を施すことによって必ず解を出すことができる。これにより、P2MP TE LSPのような１ソースに対して複数の宛先が存在するパスにおいては、１つの宛先に対して迂回パスを求められなった場合に解無しとしてしまうと、それ以外の迂回パスを求められたそれ以外の多くのユーザに影響を及ぼしてしまうが、本発明の条件緩和による迂回パスの設定によって、必ず解を出すようにすることで、ユーザへの影響度を軽減させることができる。 Furthermore, according to the present invention, even in a situation where a detour path cannot be obtained, a solution can always be obtained by performing condition relaxation. As a result, in a path with multiple destinations for one source, such as P2MP TE LSP, if there is no solution when a bypass path is not required for one destination, other bypass paths However, it is possible to reduce the degree of influence on users by making sure that a solution is obtained by setting a detour path by relaxing the conditions of the present invention. it can.

また、上記の本発明の条件緩和のための方法をP2MP TE LSPにも適用することが可能である。 In addition, the above-described method for relaxing a condition of the present invention can be applied to P2MP TE LSP.

以下、図面と共に本発明の実施の形態を説明する。 Hereinafter, embodiments of the present invention will be described with reference to the drawings.

本実施の形態では、迂回経路を計算するための動作の概要を説明する。 In this embodiment, an outline of an operation for calculating a detour route will be described.

図３は、本発明の一実施の形態におけるP2MP 迂回パスのネットワークを示す。以下、同図の構成を例に説明する。 FIG. 3 shows a network of P2MP bypass paths according to an embodiment of the present invention. Hereinafter, the configuration shown in FIG.

図４は、本発明の一実施の形態における経路計算装置の構成図である。同図に示すように、経路計算装置１は、迂回パス計算部４０とデータベース２０から構成される。 FIG. 4 is a configuration diagram of a route calculation apparatus according to an embodiment of the present invention. As shown in the figure, the route calculation apparatus 1 includes a detour path calculation unit 40 and a database 20.

図５は、本発明の一実施の形態における動作の概要を示すフローチャートである。 FIG. 5 is a flowchart showing an outline of the operation according to the embodiment of the present invention.

ステップ１０１）最初に、経路設定対象のノード、リンク集合と共に、ソースノード、リーフノードが、オペレータから入力されることにより特定される。ここでは、図３に示すように、Ingressノード（ソースノード）をノードＡとし、Egressノード（リーフノード）をノードＬ，Ｍ，Ｎ，Ｏとする。なお、ここで入力されるノードやリンク集合は、データベースなどの記憶手段から読み込んで入力されるものとする。 Step 101) First, a source node and a leaf node together with a node and a link set to be set are specified by being input from an operator. Here, as shown in FIG. 3, the Ingress node (source node) is the node A, and the Egress node (leaf node) is the nodes L, M, N, and O. Note that the nodes and link sets input here are read from a storage means such as a database and are input.

ステップ１０２）まず、経路計算装置１の迂回パス計算部４０は、迂回パス（迂回経路）が必要となるP2MP TE LSPに対して、入力されたリンク集合からそのプライマリパスが通る物理リンクを除く。図６の例では、プライマリP2MP TE LSPを通るリンクＡ−Ｃ，Ｃ−Ｅ，Ｅ−Ｈ，Ｈ−Ｌ，Ｈ−Ｍ，Ｅ−Ｉ，Ｉ−Ｎ，Ｃ−Ｇ、Ｇ−Ｋ，Ｋ−０を除く。 Step 102) First, the detour path calculation unit 40 of the path calculation device 1 removes the physical link through which the primary path passes from the input link set for the P2MP TE LSP that requires a detour path (detour path). In the example of FIG. 6, the links A-C, CE, E-H, H-L, H-M, E-I, I-N, C-G, G-K, K passing through the primary P2MP TE LSP. Except for -0.

ステップ１０３）迂回パス計算部４０は、図７に示すような、プライマリパスが削除された残りのリンク（ソースノードからリーフノードまで）を用いて、経路計算アルゴリズムで迂回パスの通る経路を計算する。具体的には、Dijkstra経路計算アルゴリズムによって、最短パスを計算し、End-to-Endでプライマリパスと交わらないP2MP 迂回パスのための経路を計算する。 Step 103) The detour path calculation unit 40 uses the remaining link (from the source node to the leaf node) from which the primary path has been deleted as illustrated in FIG. . Specifically, the shortest path is calculated by the Dijkstra route calculation algorithm, and a path for a P2MP bypass path that does not intersect the primary path end-to-end is calculated.

ステップ１０４）迂回パス計算部４０は、経路計算アルゴリズム（Dijkstra経路計算アルゴリズム）によって経路が出力された場合（End-to-EndでP2MP 迂回パスが設定可能となった場合）は、ステップ１１０に移行する。一方、経路が出力されなかった場合には、ステップ１０５に移行する。

Step 104) When the route is output by the route calculation algorithm (Dijkstra route calculation algorithm) (when the P2MP bypass path can be set end-to-end), the detour path calculation unit 40 proceeds to Step 110. To do. On the other hand, if the route is not output, the process proceeds to step 105.

ステップ１０５）迂回パス計算部４０は、End-to-EndでP2MP 迂回パスを設定できない場合は、図８に示すように、ソースノードをＡ、リーフノードをＬ，Ｍ，Ｎ，Ｏとし、迂回パスが必要となるP2MP TE LSPに対して、そのプライマリパスが通る物理リンクを除く。その結果は、図９のようになる。図９の例では、P2MPプライマリパスを通るリンクＡ−Ｃ，Ｃ−Ｅ、Ｅ−Ｈ，Ｈ−Ｌ，Ｈ−Ｍ，Ｅ−Ｉ，Ｉ−Ｎ，Ｃ−Ｇ，Ｇ−Ｋ，Ｋ−Ｏを除く。 Step 105) When the detour path calculation unit 40 cannot set the P2MP detour path end-to-end, the detour path is set to A, the leaf nodes are L, M, N, and O as shown in FIG. For P2MP TE LSPs that require a path, the physical link through which the primary path passes is excluded. The result is as shown in FIG. In the example of FIG. 9, the links A, C, E, E, H, H, M, E, I, I, N, C, G, G, K, K— that pass through the P2MP primary path. O is excluded.

ステップ１０６）迂回パス計算部４０は、残りのリンクを用いて、プライマリパスが設定されたソースノードからリーフノードまでをDijkstra経路計算アルゴリズムによって最短パスを計算し、End-to-Endでプライマリパスと交わらないP2MP 迂回パスのための経路を計算する。 Step 106) The detour path calculation unit 40 uses the remaining links to calculate the shortest path from the source node to which the primary path is set to the leaf node using the Dijkstra route calculation algorithm, and determines the primary path as end-to-end. Calculate the route for the P2MP bypass path that does not intersect.

ステップ１０７）迂回パス計算部４０は、経路計算の経路が出力されたかを判断する。経路が出力された場合は、ステップ１１０に移行する。一方、経路が出力されなかった場合は、ステップ１０８に移行する。この例では、図１０に示すように、リーフノードＭへの経路が見つからなかった。 Step 107) The detour path calculation unit 40 determines whether a route for route calculation has been output. If the route is output, the process proceeds to step 110. On the other hand, if no route is output, the process proceeds to step 108. In this example, the route to the leaf node M was not found as shown in FIG.

ステップ１０８）経路が出力されない場合は、まず、次のノードがソースノードであるかを判定し、ソースノードである場合は処理を終了し、ソースノードでない場合はステップ１０９に移行する。 Step 108) When the route is not output, it is first determined whether or not the next node is a source node. If it is a source node, the process is terminated, and if it is not a source node, the process proceeds to Step 109.

ステップ１０９）リーフノードの中に経路到達不可能であったノードが存在することとなり、次は、ソースノードからその到達不可能であったリーフノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であったリーフノードまでを、再度Dijkstra経路計算を行い、ステップ１０７に移行し、経路到達可能か確認する。 Step 109) There is a node that cannot reach the path among the leaf nodes. Next, the path reaches the node one hop upstream from the primary path through the leaf node that cannot be reached from the source node. Dijkstra route calculation is performed again up to the leaf node that was possible, and the process proceeds to step 107 to check whether the route is reachable.

ステップ１１０）迂回パス計算部４０は、ステップ１０４及びステップ１０７において、経路が出力された場合には、経路計算の結果をデータベース２０に格納する。さらに、経路計算の結果、経路が出力された場合には、当該経路を元に、図１１に示すようにP2MP 迂回パスを設定する。なお、図１１において、点線はP2MP プライマリパスを示し、実線はP2MP 迂回パスを示す。 Step 110) When the route is output in Step 104 and Step 107, the detour path calculation unit 40 stores the result of the route calculation in the database 20. Further, when a route is output as a result of route calculation, a P2MP bypass path is set based on the route as shown in FIG. In FIG. 11, the dotted line indicates the P2MP primary path, and the solid line indicates the P2MP bypass path.

上記の処理において、Dijkstra経路計算アルゴリズムによって経路到達が不可能であった場合は、次は、ソースノードから、その到達不可能であったリーフノードの通るプライマリパスから２ホップ上流のノードに対して、再度、Dijkstra経路計算を行い、経路到達可能かを計算する。さらに、経路到達不可能であれば、図１２、図１３に示すように、これをソースノードに到達するまでｎホップ分繰り返す。 In the above processing, if the route cannot be reached by the Dijkstra route calculation algorithm, next, from the source node to the node that is 2 hops upstream from the primary path through which the leaf node was unreachable Again, Dijkstra route calculation is performed to calculate whether the route is reachable. Further, if the route is not reachable, as shown in FIGS. 12 and 13, this is repeated for n hops until the source node is reached.

この場合、リーフノードＭの通るプライマリパス上のリンクで１ホップ上流側のノードＨを検索し、再度ソースノードＡからリーフノードＬ，Ｎ，ＯとノードＨに対して、Dijkstraアルゴリズムによってプライマリパスと交わらない経路を計算する。（今度は、ノードＨに対してＡ−Ｄ−Ｇ−Ｆ−Ｈを通る経路が計算される）。 In this case, the node H on the one-hop upstream side is searched for on the link on the primary path through which the leaf node M passes, and the primary path is again determined from the source node A to the leaf nodes L, N, O and the node H by the Dijkstra algorithm. Calculate routes that do not intersect. (Now, a path through A-D-G-F-H is calculated for node H).

Dijkstra経路計算アルゴリズムによって出力された経路を元に、P2MP 迂回パスを設定する。ソースノードから経路到達不可能であったリーフノードの通るプライマリパスからｋ（ｋ＝１，２，…，ｎ）ホップ上流のノードと経路到達可能であったリーフノードまでの経路は、Dijkstraアルゴリズムによって計算された経路を元に、P2MP 迂回パスを設定する。ｋホップ上流のノードから到達不可能であったリーフノードまでの経路は、プライマリパスと同一の経路を通るように、迂回パスを設定する。ソースノードに至るまでの（ｋ＝ｎ）経路到達不可能であったリーフノードに対しては、ソースノードからリーフノードまでのプライマリパスと同一の経路をP2MP 迂回パスを通る経路として設定する。経路が設定された例を図１４に示す。なお、同図において、点線はP2MP プライマリパスを示し、実線はP2MP 迂回パスを示す。 A P2MP bypass path is set based on the route output by the Dijkstra route calculation algorithm. The path from the primary path through which the leaf node was unreachable from the source node to the node upstream of k (k = 1, 2,..., N) hops and the leaf node that was reachable by the route is determined by the Dijkstra algorithm. A P2MP bypass path is set based on the calculated route. The detour path is set so that the path from the k hop upstream node to the leaf node that cannot be reached passes the same path as the primary path. For a leaf node that cannot reach the path to the source node (k = n), the same path as the primary path from the source node to the leaf node is set as a path passing through the P2MP bypass path. An example in which a route is set is shown in FIG. In the figure, the dotted line indicates the P2MP primary path, and the solid line indicates the P2MP bypass path.

図１５は、本発明の一実施の形態におけるサーバの構成を示す。 FIG. 15 shows the configuration of a server according to an embodiment of the present invention.

同図に示すサーバ１００は、上記の図４に示す迂回パス計算部４０とネットワーク上の各ノードにP2MPパスの情報を送信するための送信部２を有する。 The server 100 shown in the figure includes the detour path calculation unit 40 shown in FIG. 4 and the transmission unit 2 for transmitting P2MP path information to each node on the network.

図１６は、本発明の一実施の形態におけるルータの構成図である。 FIG. 16 is a configuration diagram of a router according to an embodiment of the present invention.

同図に示すルータ２００は、上記の図４に示す迂回パス計算部４０と、迂回パス計算部４０から出力された経路計算結果を格納するデータベース３及び送受信部４を有する。 The router 200 shown in the figure includes the detour path calculation unit 40 shown in FIG. 4, the database 3 that stores the route calculation result output from the detour path calculation unit 40, and the transmission / reception unit 4.

上記の図１５、図１６に示すように、経路計算装置１の迂回パス計算部４０をサーバ１００または、ルータ２００のいずれかに設けることができる。 As shown in FIGS. 15 and 16, the detour path calculation unit 40 of the route calculation device 1 can be provided in either the server 100 or the router 200.

なお、上記の例では、経路計算アルゴリズムとして、Dijkstraアルゴリズムを用いたが、その他、Prim、ＫＭＢ，ＤＤＭＣ等のアルゴリズムを利用することも可能である。 In the above example, the Dijkstra algorithm is used as the route calculation algorithm, but other algorithms such as Prim, KMB, DDMC, etc. can also be used.

また、上記の迂回経路計算装置の動作をプログラムとして構築し、迂回経路計算装置として利用されるコンピュータ、サーバ、ノードにインストールして実行させることも可能である。 It is also possible to construct the operation of the detour route calculation device as a program and install it on a computer, server, or node used as the detour route calculation device.

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。 The present invention is not limited to the above-described embodiment, and various modifications and applications can be made within the scope of the claims.

本発明は、P2MP迂回経路を設定するための技術に適用可能である。 The present invention is applicable to a technique for setting a P2MP bypass route.

本発明の原理構成図である。It is a principle block diagram of this invention. 本発明の原理説明図である。It is a principle explanatory view of the present invention. 本発明の一実施の形態におけるP2MP迂回パス設定を行うネットワークを示す図である。It is a figure which shows the network which performs P2MP detour path setting in one embodiment of this invention. 本発明の一実施の形態における動作の概要を示すフローチャートである。It is a flowchart which shows the outline | summary of operation | movement in one embodiment of this invention. 本発明の一実施の形態におけるプライマリパスの削除を示す図である。It is a figure which shows deletion of the primary path in one embodiment of this invention. 本発明の一実施の形態におけるプライマリパスが削除されたネットワークを示す図である。It is a figure which shows the network from which the primary path in one embodiment of this invention was deleted. 本発明の一実施の形態におけるP2MP迂回パスが設定できなかった場合のネットワークを示す図である。It is a figure which shows a network when the P2MP detour path in one embodiment of this invention cannot be set. 本発明の一実施の形態におけるプライマリパスを削除した例である。It is the example which deleted the primary path in one embodiment of this invention. 本発明の一実施の形態における経路計算の結果を示す図である。It is a figure which shows the result of the route calculation in one embodiment of this invention. 本発明の一実施の形態における経路計算により経路が出力された場合のP2MP迂回パスの設定例である。It is a setting example of a P2MP detour path when a route is output by route calculation in an embodiment of the present invention. 本発明の一実施の形態における経路計算により経路が出力されなかった場合の動作を説明するための図（その１）である。It is FIG. (1) for demonstrating operation | movement when a path | route is not output by path | route calculation in one embodiment of this invention. 本発明の一実施の形態における経路計算により経路が出力されなかった場合の動作を説明するための図（その２）である。It is FIG. (2) for demonstrating operation | movement when a path | route is not output by path | route calculation in one embodiment of this invention. 本発明の一実施の形態における迂回パス設定の例である。It is an example of the detour path setting in one embodiment of this invention.

Explanation of symbols

Ａ〜Ｏノード
１迂回経路計算装置
２送信部
３データベース
４送受信部
１０ルータコンフィグ変換部
２０記憶手段、データベース
４０迂回パス計算手段、迂回パス計算部
１００サーバ
２００ルータ A to O node 1 detour path calculation device 2 transmission unit 3 database 4 transmission / reception unit 10 router configuration conversion unit 20 storage unit, database 40 detour path calculation unit, detour path calculation unit 100 server 200 router

Claims

A detour route calculation device that has connection relation information and link cost information and performs detour route calculation for setting a point-to-multipoint (P2MP) path,
When the node and link set to be routed, and information on the ingress node and multiple egress nodes of the P2MP path that requires a detour path are input, the P2MP TE LSP (P2MP Traffic Engineering) that requires the detour path is input. Label Switched Path), except for the physical links and physical nodes that pass the P2MP primary path from the link set, from the ingress node to the egress node, from the remaining links and nodes so as not to intersect the P2MP primary path A detour path calculating means for calculating a P2MP detour path from the ingress node to the egress node;
Storage means for storing the result of the detour path calculation means,
Before Symbol detour path calculation means,
For the P2MP TE LSP requiring the detour path, the ingress node in which the primary path is set using the remaining links and nodes excluding the physical link and physical node through which the primary path passes from the link set A first detour path calculation means for calculating a shortest path or a minimum path from the egress node to the egress node by a path calculation algorithm and calculating a P2MP detour path that does not intersect the primary path from the ingress node to the egress node; ,
First bypass path setting means for setting the P2MP bypass path to a node on the route based on the route calculated by the first bypass path calculating means;
In the first detour path calculation means, if the exit node that cannot reach the route exists in the exit node and the route is not calculated, the route cannot be reached from the entrance node. First to confirm whether the route is reachable by calculating the shortest route or the minimum route again from the primary path through which the exit node passes to the node one hop upstream and the exit node where the route was reachable by the route calculation algorithm. Confirmation means,
By the route calculation algorithm, when there was a route reachable from said ingress node was the primary path or al 1 hops upstream node and a route reachable through the said outlet node which was the path unreachable For the route to the egress node, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the egress node that was unreachable from the k-hop upstream node A second detour path setting means for setting a P2MP detour path to a node on the route so as to pass the same route as the primary path,
If the route cannot be reached by the route calculation algorithm, k (k = 2, 3,..., N) hops upstream from the primary path through the exit node that was not reachable from the ingress node. Second check means for performing a route calculation again on the node using the route calculation algorithm and checking whether the route is reachable;
Furthermore, a repeating unit if the route unreachable, the pre-Symbol second confirmation means, repeated n hops to reach the ingress node,
If the route is reachable in the repetitive means, a node upstream of k (k = 2, 3 ,..., N) hops from the primary path through the exit node from which the route was unreachable, and For the route to the exit node that was reachable, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the reachable node from the node upstream of k hops is not possible For the route to the egress node, a P2MP detour path is set in the node on the route so as to pass the same route as the primary path, and the route cannot reach until the ingress node is reached (k = n). For the egress node that was possible, the same path as the primary path from the ingress node to the egress node is used as a path through the P2MP detour path. A third bypass path setting means for setting,
A detour route calculation apparatus comprising:

A computer having storage means for storing a route calculation result;
A detour route calculation program that functions as the detour route calculation device according to claim 1 .

In a network having a P2MP entrance node and a plurality of exit nodes that require a bypass path, a bypass path calculation server that sets a bypass path,
The detour route calculation device according to claim 1 ,
Means for transmitting information on a detour P2MP path obtained by the detour path calculation device to a node on the network;
A detour route calculation server characterized by comprising:

A router that requires a detour path,
The detour route calculation device according to claim 1 ,
A database for storing detour route information acquired from the detour route calculation device;
A router characterized by comprising:

A detour route calculation method for performing a detour route calculation in a network having a detour route calculation device capable of setting a point-to-multipoint (P2MP) path, the device having connection relation information and link cost information,
For the primary path periphrastic Kai path is required, using the remaining links and nodes excluding the physical link and physical node to which the primary path through the link set, or input mouth node the primary path is set up RaIzuru port node, to calculate the shortest path or minimum path by the route calculation algorithm, and the detour path calculation step of calculating a P2MP bypass path disjoint with the primary path and the link from the inlet node to said outlet node,
A first bypass path setting step for setting a P2MP bypass path to a node on the route based on the route calculated in the bypass path calculation step;
In the detour path calculating step, if the exit node that cannot reach the route exists in the exit node and the route is not calculated, the entry node determines the route of the exit node that cannot reach the route. A first confirmation step of confirming whether the route is reachable by calculating the shortest route or the minimum route again from the primary path that passes through to the node that is route reachable with the node one hop upstream by the route calculation algorithm. When,
When a route is reachable by the route calculation algorithm, from the entry node to a node that is one hop upstream from the primary path through which the route is not reachable and an exit node that is reachable For the route of, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the route from the node upstream of k hops to the exit node that was unreachable A second bypass path setting step for setting a P2MP bypass path in a node on the route so as to pass the same route as the primary path;
If the route cannot be reached by the calculation algorithm, a node that is k (k = 2, 3,..., N) hops upstream from the primary path through the exit node that was not reachable from the entrance node. On the other hand, a second confirmation step for performing route computation again by the route computation algorithm and confirming whether the route is reachable,
Further, repeating steps if route unreachable, the pre-Symbol second verification step is repeated n hops to reach the ingress node,
If the route is reachable in the repetition step, a node upstream of k (k = 2, 3 ,..., N) hops from the primary path through the exit node where the route was unreachable from the ingress node and For the route to the exit node that was reachable, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the reachable node from the node upstream of k hops is not possible For the route to the egress node, a P2MP detour path is set in the node on the route so as to pass the same route as the primary path, and the route cannot reach until the ingress node is reached (k = n). For the egress node that was possible, the same path as the primary path from the ingress node to the egress node is used as a route through the P2MP detour path. A third alternative path setting step of setting a de,
A detour route calculation method characterized by :

A detour route calculation system having a detour route calculation device capable of setting a point-to-multipoint (P2MP) path, and performing detour route calculation in a network in which the device has connection relation information and link cost information,
When the node and link set to be routed, and the information of the entry node and the plurality of exit nodes of the P2MP path that requires a detour path are input, for the P2MP TE LSP that requires the detour path, using the remaining links and nodes excluding the physical link and physical nodes through which P2MP primary path from the link set, the shortest path or minimized by routing algorithms to the egress node from the primary path set inlet node A detour path calculating means for calculating a route and calculating a P2MP detour path that does not intersect the link with the primary path from the ingress node to the egress node;
First bypass path setting means for setting a P2MP bypass path to a node on the route based on the route calculated by the bypass path calculating means;
In the detour path calculation means, if the exit node that cannot reach the route is present in the exit node and the route is not calculated, the route of the exit node that has become unreachable from the entrance node. First confirmation means for calculating whether the route is reachable by calculating the shortest route or the minimum route again using the route calculation algorithm from the primary path passing through to the node one hop upstream and the exit node where the route was reachable. When,
When a route is reachable by the route calculation algorithm, from the entry node to a node that is one hop upstream from the primary path through which the route is not reachable and an exit node that is reachable For the route of, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the route from the node upstream of k hops to the exit node that was unreachable A second bypass path setting means for setting a P2MP bypass path in a node on the route so as to pass the same route as the primary path;
If the route cannot be reached by the route calculation algorithm, k (k = 2, 3,..., N) hops upstream from the primary path through the exit node that was not reachable from the ingress node. Second check means for performing a route calculation again on the node using the route calculation algorithm and checking whether the route is reachable;
Furthermore, a repeating unit if the route unreachable, the pre-Symbol second confirmation means, repeated n hops to reach the ingress node,
If the route is reachable in the repetitive means, a node upstream of k (k = 2, 3 ,..., N) hops from the primary path through the exit node from which the route was unreachable, and For the route to the exit node that was reachable, based on the route calculated by the route calculation algorithm, a P2MP detour path is set for the node on the route, and the reachable node from the node upstream of k hops is not possible For the route to the egress node, a P2MP detour path is set in the node on the route so as to pass the same route as the primary path, and the route cannot reach until the ingress node is reached (k = n). For the egress node that was possible, the same path as the primary path from the ingress node to the egress node is used as a path through the P2MP detour path. A third bypass path setting means for setting,
A detour route calculation system characterized by comprising: