(57)【要約】【課題】トラヒックの最適経路を、確実かつ少ないラベル数によって提供可能とする。【解決手段】経路変換制御装置２は、セグメントルーティングにおけるネットワークパスを演算する経路演算部２３と、このネットワークパスの基点ノードから最短経路を探索し、基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、基点ノードから次ノードへ最短経路で到達できないならば基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとしてラベルリストに設定する経路変換部２４と、を備える。【選択図】図１
2018037983.tif 000002
【特許請求の範囲】
【請求項１】
セグメントルーティングにおけるネットワークパスを演算する経路演算部と、
前記ネットワークパスの基点ノードから最短経路を探索し、前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定する経路変換部と、
を備えることを特徴とする経路変換制御装置。
【請求項２】
前記経路演算部は、要求されたトラヒックフロー条件とネットワーク資源とに基づき、前記ネットワークパスを演算する、
ことを特徴とする請求項１に記載の経路変換制御装置。
【請求項３】
前記経路変換部は、前記基点ノードから前記次ノードへ最短経路で到達できないならば、前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定したのち、前記次ノードを新たな基点ノードに設定し、前記ネットワークパスに対する最短経路の探索を繰り返してラベルリストを設定する、
ことを特徴とする請求項１に記載の経路変換制御装置。
【請求項４】
セグメントルーティングにおけるネットワークパスを演算するステップと、
前記ネットワークパスの基点ノードから最短経路を探索するステップと、
前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定するステップと、
を含むことを特徴とする経路変換制御方法。
【請求項５】
前記次ノードを新たな基点ノードに設定するステップと、
前記ネットワークパスに対する最短経路の探索を繰り返してラベルリストを設定するステップと、
を含むことを特徴とする請求項４に記載の経路変換制御方法。
【請求項６】
コンピュータを、
セグメントルーティングにおけるネットワークパスを演算する経路演算手段、
前記ネットワークパスの基点ノードから最短経路を探索し、前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定する経路変換手段、
として機能させるための経路変換制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、新規トラヒックフロー要求あるいは迂回要求が到着した際に、最適経路を通信機器へ通知する経路変換制御装置、経路変換制御方法および経路変換制御プログラムに関する。
【背景技術】
【０００２】
ネットワークパスを明示的に指示する技術として、非特許文献１には、セグメントルーティングのような、ラベルにNode-ID(通信ノード)、Adjacency-ID(インタフェース)の意味を持たせ、それらを組み合わせて通信パケットへスタックすることによって任意の経路を設定する技術が提案されている。
【０００３】
本技術では、所望の経路をセグメントリストによって表現する際に、そのセグメントリストを演算する必要がある。従来の演算方式には、Node-IDで経路を表現する方法と、Adjacency-IDで経路を表現する方法の２種類が存在する。
【０００４】
Node-IDのみで経路を表現しようとすると、ラベルで指定されたノード間をリンクコストに基づく最短経路で到達しようとする。そのため、すべての経由ノードを指定する必要がなくMTU(Maximum Transmission Unit)への影響が小さいというメリットがある（参考：非特許文献２）。また、loose指定となるためリンク障害時においても、サービス影響が小さいということが利点として挙げられる。一方で網のリンクコストによっては、どのようにノードを指定したとしても経由できない経路が存在する場合がある。
【０００５】
Adjacency-IDのみで経路を表現する場合は、strict指定に等しく、リンクコストを無視した指定が可能である。したがってNode-IDのみで経路を表現した場合と異なり、経由できない経路は存在しない。しかしながら網の構成・規模によっては膨大なラベルスタック数が要求される場合があり、MTUへの影響が大きいという問題がある。またstrict指定となるため、リンク障害時においてはパスの再計算をする必要があり、耐障害性の観点でAdjacency-IDのみでの指定は望ましくない。
【０００６】
Node-IDとAdjacency-IDを組み合わせて経路を表現する方法もあるが、リンクコストを考慮しつつloose指定、strict指定をする必要があるため、手作業で組み合わせて指定するのは困難である。またそれを演算する機能自体は具体的に定義されていない。
【０００７】
また近年では、仮想化技術の進展に伴い特定の物理ネットワークに対して複数面のネットワークを重畳させることが検討されている（参考：非特許文献３）。そのような場合においては、トラヒックの経路は自ずと迂回する機会が増え、指定が必要なホップ数も増えると考えられる。したがって、いずれの方式においても、ラベルスタック数はなるべく減らす必要がある上に耐障害性の観点でloose指定を優先するべきである。
【０００８】
なお、指定されたセグメントリストは、送信元ノードへ通知される。送信元ノードへの通知方法としてPCEP(Path computation element protocol)あるいは拡張PCEPなどがある（参考：非特許文献４）。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】“Segment Routing Architecture”,[online],January 5.2017,Network Working Group,［平成２８年８月１８日検索］,インターネット<URL:https://datatracker.ietf.org/doc/draft-ietf-spring-segment-routing/>
【非特許文献２】Alessio Giorgetti et al,“Path Encoding in Segment Routing”,Dec.2015,IEEE GLOBECOM, pp.1-6
【非特許文献３】Andreas Fischer et al,“Virtual Network Embedding: A Survey”,IEEE Communications Surveys & Tutorials,Feb. 2013,vol.15,issue: 4,pp.1888-1906
【非特許文献４】“PCEP Extensions for Segment Routing”,[online], September 22.2016,Network Working Group,［平成２８年８月１８日検索］,インターネット<URL:https://datatracker.ietf.org/doc/draft-ietf-pce-segment-routing/>
【発明の概要】
【発明が解決しようとする課題】
【００１０】
非特許文献１〜３に記載された技術では、経由できないパスが生じる可能性があることや、ラベルスタック数が増加するという課題がある。またラベルを構成する際には、耐障害性の観点でなるべくloose指定を優先的に選択する必要がある。
そこで、本発明は、トラヒックの最適経路を、確実かつ少ないラベル数によって提供可能とすることを課題とする。
【課題を解決するための手段】
【００１１】
前記した課題を解決するため、請求項１に記載の発明では、セグメントルーティングにおけるネットワークパスを演算する経路演算部と、前記ネットワークパスの基点ノードから最短経路を探索し、前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定する経路変換部と、を備えることを特徴とする経路変換制御装置とした。
【００１２】
このようにすることで、トラヒックの最適経路を、確実かつ少ないラベル数によって提供可能である。
【００１３】
請求項２に記載の発明では、前記経路演算部は、要求されたトラヒックフロー条件とネットワーク資源とに基づき、前記ネットワークパスを演算する、ことを特徴とする請求項１に記載の経路変換制御装置とした。
【００１４】
このようにすることで、トラヒックの最適経路を演算することができる。
【００１５】
請求項３に記載の発明では、前記経路変換部は、前記基点ノードから前記次ノードへ最短経路で到達できないならば、前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定したのち、前記次ノードを新たな基点ノードに設定し、前記ネットワークパスに対する最短経路の探索を繰り返してラベルリストを設定する、ことを特徴とする請求項１に記載の経路変換制御装置とした。
【００１６】
このようにすることで、演算したネットワークパスの部分をAdjacency-IDとしてラベルリストに設定することができる。
【００１７】
請求項４に記載の発明では、セグメントルーティングにおけるネットワークパスを演算するステップと、前記ネットワークパスの基点ノードから最短経路を探索するステップと、前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定するステップと、を含むことを特徴とする経路変換制御方法とした。
【００１８】
このようにすることで、演算したネットワークパスの部分をAdjacency-IDとしてラベルリストに設定するか、Node-IDをラベルリストに設定するかを選択可能である。
【００１９】
請求項５に記載の発明では、前記次ノードを新たな基点ノードに設定するステップと、前記ネットワークパスに対する最短経路の探索を繰り返してラベルリストを設定するステップと、を含むことを特徴とする請求項４に記載の経路変換制御方法とした。
【００２０】
このようにすることで、演算したネットワークパスの各部をラベルリストに登録した後、繰り返し基点ノードを再設定するので、全てのネットワークパスをラベルリストに設定できる。
【００２１】
請求項６に記載の発明では、コンピュータを、セグメントルーティングにおけるネットワークパスを演算する経路演算手段、前記ネットワークパスの基点ノードから最短経路を探索し、前記基点ノードから最短経路で到達可能な範囲のノードを示すNode-IDをラベルリストに設定し、前記基点ノードから次ノードへ最短経路で到達できないならば前記基点ノードと前記次ノードの間の所定リンクをAdjacency-IDとして前記ラベルリストに設定する経路変換手段、として機能させるための経路変換制御プログラムとした。
【００２２】
このようにすることで、トラヒックの最適経路を、確実かつ少ないラベル数によって提供可能である。
【発明の効果】
【００２３】
本発明によれば、トラヒックの最適経路を、確実かつ少ないラベル数によって提供可能となる。
【図面の簡単な説明】
【００２４】
【図１】本実施形態における経路変換制御システムの構成図である。
【図２】経路変換制御装置と通信ノード間のプロトコルを示す図である。
【図３】本実施形態の経路変換制御処理を説明するフローチャートである。
【図４】本実施形態におけるネットワーク構成例を示す図である。
【図５】ネットワーク上に実現したい経路を示す図である。
【図６】手順２を示す図である。
【図７】手順３を示す図である。
【図８】手順４を示す図である。
【発明を実施するための形態】
【００２５】
以降、本発明を実施するための形態を、各図を参照して詳細に説明する。
本発明の経路変換制御装置は、通信パケットへノードやインタフェースの意味を持つラベルをスタックすることで明示的なパスを指示する。その際、経路変換制御装置は、最適経路をより少ないラベル数かつなるべくloose指定となるようなラベルスタック構成のセグメントリスト(SL)へ変換する。
【００２６】
図１は、本実施形態における経路変換制御システム１の構成図である。
図１に示すように経路変換制御システム１は、或る物理ネットワーク上に外部コントローラである経路変換制御装置２が配備されている構成となっている。経路変換制御装置２は、要求受付インタフェース２１、情報取得部２２、経路演算部２３、経路変換部２４、ネットワークパス設定部２５を備えている。経路変換制御装置２が制御する物理ネットワークは、通信ノード３ａ〜３ｆを含んで構成される。
【００２７】
要求受付インタフェース２１は、トラヒック要求４を受け付けるためのインタフェースである。要求の受け方としては、例えばREST(REpresentational State Transfer) APIを用いて、トラヒックフロー情報（帯域情報、発着ノード情報、その他）を受け付ける方法が考えられる。
【００２８】
情報取得部２２は、網内の資源情報（トポロジ、リンク帯域、インタフェース数など）を取得する。図２に示す通り、情報取得部２２は、Border Gateway Protocol(BGP)などにより通信機器から通知を受ける形態や、Simple Network Management Protocol（SNMP）によりコントローラから定期的に取得する形態が考えられる。
【００２９】
ネットワークパス設定部２５は、経路変換部２４で得られたセグメントリストを送信元ノードへ通知する。セグメントルーティングでは、明示的に指示する方法としてPCEPまたは拡張PCEPなどが考えられている。
【００３０】
経路演算部２３では、要求されたトラヒックフロー情報と情報取得部２２で得られた資源情報に基づき、最適なパスを演算する。経路探索に用いる手法としてはk-th shortest pathアルゴリズムなどを用いて複数経路を探索する。その後、資源割当て問題を解くことにより、最適なパスを選出する。
【００３１】
経路変換部２４は、経路演算部２３によって得られた最適経路をセグメントリストへ変換する。経路変換部２４は、最適経路を入力情報として、Node-IDとAdjacency-IDの両方を用いて、最適経路を確実に実現すると共に、より少ないラベルスタック数かつloose指定となるようにセグメントリストを演算する。
ここで経路変換にあたってのポイントとしては、リンクコストに基づき最短経路で経由できる経路についてはNode-IDを指定し、コスト都合により、最短経路で経由できない経路についてのみAdjacency-IDを指定する。
【００３２】
図３は、本実施形態の経路変換制御処理を説明するフローチャートである。
図３より経路変換部２４は、所望のパス集合p_desと空のセグメントリストSLを入力情報とし（ステップＳ１０）、インデックスsrc,jjを０で初期化し、インデックスiiを１で初期化する（ステップＳ１１）。ここでsrcは、パス集合p_desの基点ノードを示している。iiは、基点ノードから最短経路で到達可能な範囲のノードを探索するためのインデックスである。jjは、セグメントリストSLへの書き込み先を示している。
【００３３】
経路変換部２４は、インデックスiiがパス集合p_desの最大インデックス(|p_des|-1)を超えておらず（ステップＳ１２→Ｎｏ）、かつ基点ノードp_des(src)からp_des(ii)までが唯一の最短経路(SPF:Shortest Path First)ならば（ステップＳ１３→Ｙｅｓ）、iiをインクリメントして（ステップＳ１４）、再びステップＳ１２の最短経路の判定に戻る。この繰り返しにより、基点ノードから最短経路で到達可能な範囲のノードを探索可能である。
なお、|p_des|は、パス集合p_desの要素数を示している。本実施形態では、パス集合p_desの最初の要素をインデックスii=0で示す。よってパス集合p_desの最大インデックスは、(|p_des|-1)となる。
【００３４】
経路変換部２４は、iiがパス集合p_desの最大インデックス(|p_des|-1)を超えたか（ステップＳ１２→Ｙｅｓ）、または基点ノードp_des(src)からp_dss(ii)までが唯一の最短経路でないならば（ステップＳ１３→Ｎｏ）、ステップＳ１５に進む。
経路変換部２４は、ステップＳ１５において、ii-srcが1であるか否かを判定する。ii-srcが1でなければ（Ｎｏ）、基点ノードから最短経路で到達可能な範囲のノードが存在する。このとき、経路変換部２４は、ステップＳ１６の処理に進み、セグメントリストSLに対して、p_des(ii-1)をNodeIDとして指定する。更に経路変換部２４は、書込インデックスjjをインクリメントし（ステップＳ１７）、基点インデックスsrcにii-1を設定する（ステップＳ１８）。これにより、p_des(ii-1)が新たな基点ノードとなる。インデックスiiは、新たな基点ノードの次のノードを指し示している。
【００３５】
ステップＳ１５においてii-srcが1ならば（Ｙｅｓ）、基点ノードから最短経路で到達可能な範囲のノードが存在しない。このとき、経路変換部２４は、ステップＳ１９の処理に進み、p_des(src)とp_des(ii)間のAdjacency-IDを、セグメントリストSL(jj)に格納する。
更に経路変換部２４は、書込インデックスjjをインクリメントし（ステップＳ２０）、基点インデックスsrcにiiを設定する（ステップＳ２１）。これにより、元の基点ノードの次のノードp_des(ii)が新たな基点ノードとなる。次に経路変換部２４は、インデックスiiをインクリメントする。これによりインデックスiiは、新たな基点ノードの次のノードを指し示す。
【００３６】
ステップＳ１８，Ｓ２２の後、経路変換部２４は、基点インデックスsrcがパス集合p_desの最大インデックス(|p_des|-1)と等しくないならば（ステップＳ２３→Ｎｏ）、ステップＳ１２の処理に戻る。基点インデックスsrcがパス集合p_desの最大インデックス(|p_des|-1)と等しいならば（ステップＳ２３→Ｙｅｓ）、経路変換部２４は、ステップＳ２４の処理に進み、セグメントリストSLを出力する。
このようにして、セグメントリストの演算を進め出力情報としてセグメントリストが得られることが分かる。経路変換部２４による演算後は、得られたセグメントリストSLを入力情報としてネットワークパス設定部２５へ通知する。
【００３７】
続いて経路変換部２４による動作の流れについて、図４に示すような構成を例として説明する。このネットワークは、通信ノード３ｇ，３ｈ，３ｊ，３ｋ，３ｍ，３ｎ，３ｐを含み、この通信ノード３ｐがインターネット５に接続されて構成される。
通信ノード３ｇ(ER1)は、通信ノード３ｍ，３ｊに１０本の１０Ｇｂ回線によるＬＡＧで接続される。通信ノード３ｇ(ER1)と通信ノード３ｍ(R2)間のリンクコストは１００である。通信ノード３ｇ(ER1)と通信ノード３ｊ(R1)間のリンクコストは１０である。
通信ノード３ｈ(ER2)は、通信ノード３ｍ，３ｊに１本の１０Ｇｂ回線で接続される。通信ノード３ｈ(ER2)と通信ノード３ｍ(R2)間のリンクコストは１００である。通信ノード３ｈ(ER2)と通信ノード３ｊ(R1)間のリンクコストは１０である。
【００３８】
通信ノード３ｊ(R1)は、上記回線に加えて、１００Ｇｂ回線で通信ノード３ｍ，３ｋに接続される。通信ノード３ｊ(R1)と通信ノード３ｍ(R2)間のリンクコストは５０である。通信ノード３ｊ(R1)と通信ノード３ｋ(R3)間のリンクコストは１００である。
通信ノード３ｍ(R2)は、上記回線に加えて、１００Ｇｂ回線で通信ノード３ｎに接続される。通信ノード３ｍ(R2)と通信ノード３ｎ(R4)間のリンクコストは１００である。
通信ノード３ｋ(R3)は、上記回線に加えて、１００Ｇｂ回線で通信ノード３ｎ，３ｐに接続される。通信ノード３ｋ(R3)と通信ノード３ｎ(R4)間のリンクコストは１００である。通信ノード３ｋ(R3)と通信ノード３ｐ(GWR)間のリンクコストは１０である。通信ノード３ｎ(R4)は、上記回線に加えて、１００Ｇｂ回線で通信ノード３ｐに接続される。通信ノード３ｎ(R4)と通信ノード３ｐ(GWR)間のリンクコストは１００である。
通信ノード３ｐ(GWR)は、１００Ｇｂ回線で通信ノード３ｋ，３ｎに接続されると共に、インターネット５に接続される。
【００３９】
本実施形態のトラヒックシナリオは、新たにER2→GWRに向けたトラヒックフローを追加する場合である。このトラヒックフローは、リンクコストからはER2→R1→R3→GWRが最適となる。しかし、ER1→GWR向けのトラヒックがすでにリンク帯域を占有しており、図５に示すようにER2→R2→R4→GWRへ明示的に経路を通したい場合について考える。
【００４０】
《手順１》
経路変換部２４に入力されるパス集合p_desは、{ER2,R2,R4,GWR}である。その後、経路変換部２４は、基点インデックスsrcと書込インデックスjjを0で初期化し、インデックスiiを1で初期化する。
【００４１】
《手順２》
図６は、この手順２を示す。
経路変換部２４は、基点ノードp_des(0)=ER2から、パス集合p_desに含まれるどのノードまでが一意な最短経路となるのかを判定する。図６に示した例では、基点ノードER2から、次ノードp_des(1)=R2の時点で経由不可であることが分かる。図では、経由不可を「×」マークで示している。そのため、ER2とR2間のAdjacency-IDを、セグメントリストSL(0)に格納する。これを、SL(0)=ER2-R2と表現する。ここでは、ER2とR2間のAdjacency-IDを、ER2とR2とをハイフンで接続して表現している。
更に経路変換部２４は、書込インデックスjjをインクリメントし、基点インデックスsrcにiiを設定する。これにより、p_des(1)=R2が新たな基点ノードとなる。
【００４２】
《手順３》
図７は、手順３を示す図である。
手順２により、R2までの経路は確保されている。よって経路変換部２４は、p_des(1)=R2を新たな基点として、パス集合p_desに含まれるどのノードまでが一意な最短経路となるのかを判定する。図７の例において、経路変換部２４は、R2→R4までは一意な最短経路と判定する。このとき、インデックスiiは2である。図では、一意な最短経路を「〇」マークで示している。
次に経路変換部２４は、R2→R4→GWRについて判定する。このとき、インデックスiiは３である。R2→GWR間のSPFはR2→R1→R3→GWRであるため、一意な最短経路ではないと判定する（「×」マークで記載）。したがって、R4までは一意なSPFであると判定ができたため、Node-IDを指定して、セグメントリストSL(1)に格納する。これを、SL(1)=R4と表現する。
更に経路変換部２４は、書込インデックスjjをインクリメントし、基点インデックスsrcにii-1を設定する。これにより、p_des(2)=R4が新たな基点ノードとなる。
【００４３】
《手順４》
図８は、手順４を示す図である。
手順３により、R4までの経路は確保されている。よって経路変換部２４は、p_des(2)=R4を新たな基点として、パス集合p_desに含まれるどのノードまでが一意な最短経路となるのかを判定する。その結果、経路変換部２４は、GWRまでが一意な最短経路であり、かつGWRが宛先ノードであると判定する（「〇」マークで記載）。GWRが宛先ノードであると判定する理由は、インデックスiiがパス集合p_desの最大インデックス(|p_des|-1)を超えるためである。経路変換部２４は、GWRをNode-IDとして指定して、セグメントリストSL(2)に格納する。これを、SL(2)=GWRと表現する。
更に経路変換部２４は、書込インデックスjjをインクリメントし、基点インデックスsrcにii-1を設定する。これにより、p_des(3)=GWRが新たな基点ノードとなる。基点インデックスsrcがパス集合p_desの最大インデックス(|p_des|-1)と等しくなるので、経路変換部２４は、探索を終了する。
【００４４】
以上より、経路変換部２４からセグメントリストSL={ER2-R2,R4,GWR}が出力される。
上記した例ではNode-ID指定のみでは経路を指定することは不可能である。またAdjacency-ID指定の場合は３段のstrict指定が必要である。上記した例のセグメントリストSLは、Adjacency-ID指定の場合とラベル数は変わらないが、strict指定の回数を1回に低減することができる。
【００４５】
《本実施形態の効果》
本実施形態により、トラヒック要求４が到着した際に、当該経路を確実かつ少ないラベル数によって最適経路を提供可能となる。これにより、複数VPN面を重畳した際の綿密な経路設計に対しても適切なセグメントリストSLを提供可能である。
【符号の説明】
【００４６】
１  経路変換制御システム
２  経路変換制御装置
２１  要求受付インタフェース
２２  情報取得部
２３  経路演算部
２４  経路変換部
２５  ネットワークパス設定部
３  通信ノード
４  トラヒック要求
【図１】
2018037983.tif 000003
【図２】
2018037983.tif 000004
【図３】
2018037983.tif 000005
【図４】
2018037983.tif 000006
【図５】
2018037983.tif 000007
【図６】
2018037983.tif 000008
【図７】
2018037983.tif 000009
【図８】
2018037983.tif 000010