JP7521585B2

JP7521585B2 - 経路計算装置、経路計算方法、および、経路計算プログラム

Info

Publication number: JP7521585B2
Application number: JP2022548329A
Authority: JP
Inventors: 和都豊鷲見; 賢高橋; 諭士中務
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2020-09-11
Filing date: 2020-09-11
Publication date: 2024-07-24
Anticipated expiration: 2040-09-11
Also published as: US20230379238A1; JPWO2022054217A1; WO2022054217A1

Description

本発明は、経路計算装置、経路計算方法、および、経路計算プログラムに関するものである。

ネットワークのパス（転送経路）として、送信元から宛先まで通過する中継装置を転送ラベルで明示的に指定するソースルーティング方式が検討されている。
非特許文献１には、ソースルーティング方式の代表的な技術として、SR（Segment Routing）が提案されている。SRでは、SID（セグメントID）リストと呼ばれる転送ラベルリストをパスとして生成し、そのパスに従う転送を行う。

同じ送信元から同じ宛先まで中継するパスは、途中の経路が分岐していることもあり、さまざまな候補が生成される。そこで、パスの候補から採用するパスを決定するためのTE（Traffic Engineering）指標としては、以下の情報が例示される。
・IGP（Interior Gateway Protocol）によるトポロジ情報
・BGP（Border Gateway Protocol）による経路情報
・TEリンク情報
・拡張TEリンク情報（遅延情報、損失情報）
遅延情報としては、双方向アクティブ測定プロトコル（TWAMP：Two-Way Active Measurement Protocol）など実測値を用いることで、宛先まで最小遅延となるパスを選択できる。

IETF RFC8402、"Segment Routing Architecture"、［online］、July 2018、［2020年9月2日検索］、インターネット〈URL：https://tools.ietf.org/html/rfc8402〉

SRにおけるルーティングでは、複数のパスをロードバランスさせて使用することで、トラヒックを複数方向に分散できる。複数のパスとは、同じ送信元から同じ宛先まで中継するが、途中の経路が互いに異なるパスである。

図８は、SRによる転送例を示す説明図である。
符号８０１に示すネットワークトポロジ図では、ホストH1からエッジノードPE1、各ルータR1-R6を介してエッジノードPE2に収容されているホストH2にデータが転送される。エッジノードPE1は、エッジノードPE2までのパスP11,P12を生成し、そのパスに沿ってデータを転送する。

符号８０２は、エッジノードPE1が保有する仮想ルーティングテーブルを示す。仮想ルーティングテーブルには、VPNユーザごとのVRF（Virtual Routing and Forwarding）が登録されている。
例えば、第1ユーザが使用するVRF1には、送信元のエッジノードPE1から、ルータR1,R2,R3を順に通過してエッジノードPE2まで届くパスP11が登録される。第2ユーザが使用するVRF2には、送信元のエッジノードPE1から、ルータR4,R5,R6を順に通過してエッジノードPE2まで届くパスP12が登録される。これにより、エッジノードPE1からエッジノードPE2へのトラヒックは、２つのパスP11,P12をロードバランスして使用することで、適切に分散される。

なお、図８の２つのパスP11,P12は、互いに同じルータを経由しないので、経路間の結合度が低く信頼性（耐障害性）が高い経路と言える。例えば、ルータR2が故障した場合、パスP11が不通でもパスP12からトラヒックを迂回できる。
しかし、従来技術で述べたパス生成手法を用いて複数経路を構築した場合、信頼性の低い経路が構築される場合がある。

図９は、信頼性の低い経路の転送例を示す説明図である。
符号８１１に示すネットワークトポロジ図では、図８のパスP11と、ルータR4,R1,R2,R3を順に通過する新たなパスP13とが形成される。符号８１２に示すエッジノードPE1の仮想ルーティングテーブルにも、パスP11,P13が登録されている。
なお、図８のパスP12は、ルータR4,R5,R6を順に通過するため、エッジノードPE1-PE2間の遅延は、1+1+3+1=6[ms]である。一方、図９のパスP13は、ルータR4,R1,R2,R3を順に通過するため、エッジノードPE1-PE2間の遅延は、1+1+1+1+1=5[ms]である。よって、遅延が最小となるパスを選択するＴＥ指標が指定された場合、パスP12ではなくパスP13が採用される。

しかし、パスP11,P13間では、中継区間の全6ノード中（ルータR1～R6）の3ノード（ルータR1,R2,R3）を共有しており、信頼性は低くなる。例えば、ルータR2が故障した場合、パスP11,P13がともに不通となってしまい、トラヒックが迂回できない。
このように、複数パスによるロードバランスを行う場合、単一のＴＥ指標では信頼性が考慮されない経路が構築されることがある。

そこで、本発明は、所望の指標を満たしつつ、信頼性が高い経路を構築することを主な課題とする。

前記課題を解決するために、本発明の経路計算装置は、以下の特徴を有する。
本発明は、通信システムに設定するパスを選択するためのパス単体を評価可能な複数の指標と、各指標の許容範囲とを含む入力パラメータを受け付ける入力部と、
前記指標をもとに基準パスを選択するとともに、前記基準パスとは別の経路を通過する１つ以上の他パスについて、前記他パスのうちの各指標の許容範囲を満たさないパスを除外した後、前記基準パスが通過するノードを別の経路として共有する度合いが低いほど、優先的に他パスを選択する経路計算部と、
前記経路計算部が選択した前記基準パスおよび前記他パスを、前記通信システムに設定する経路設定部とを有することを特徴とする。

本発明によれば、所望の指標を満たしつつ、信頼性が高い経路を構築することができる。

本実施形態に係わる経路計算装置および通信システムの構成図である。本実施形態に係わる経路計算装置のハードウェア構成図である。本実施形態に係わる経路計算装置のメイン処理を示すフローチャートである。本実施形態に係わる図３のパスの計算処理の詳細を示すフローチャートである。本実施形態に係わる第１ＴＥ指標（遅延）に着目した各パスの優先度テーブルを示す。本実施形態に係わる第１ＴＥ指標～第３ＴＥ指標それぞれの各パスの優先度テーブルを示す。本実施形態に係わる図６の優先度テーブルから優先度の合計を計算した結果である。 SRによる転送例を示す説明図である。信頼性の低い経路の転送例を示す説明図である。

図１は、経路計算装置１および通信システム２０の構成図である。
通信システム２０は、エッジノードPEと、ルータRとを有する。なお、図１の通信システム２０は、簡略して記載したものである。しかし、通信システム２０は、実際には、図８の符号８０１に示すネットワークトポロジ図のように、エッジノードPEに収容されるホストH1,H2も存在する。また、通信システム２０のエッジノードPE間のルータRを通過する経路は、１本道ではなく、複数に分岐させることもできる。

経路計算装置１は、通信システム２０内に設定するパスの経路を計算する装置である。そのため、経路計算装置１は、入力部１１と、経路計算部１２と、情報収集部１３と、経路格納部１４と、経路設定部１５とを有する。
情報収集部１３は、通信システム２０内のツールと連携して、パス計算に必要となるトポロジ等の情報を収集する。ツールとは、例えば、Cisco社が提供するSR-PCE（Segment Routing-Path Computation Engine）というアプリケーションである。SR-PCEは、SNMP（Simple Network Management Protocol）やBGP-LS（Border Gateway Protocol-Link State）を用いて、回線帯域、トポロジ情報等を収集する。

入力部１１は、パス計算のための入力パラメータをオペレータから受け付ける。
経路計算部１２は、入力部１１の入力パラメータおよび情報収集部１３のＮＷ情報をもとに、これから通信システム２０内に設定する予定のパスを計算して経路格納部１４に格納する。
経路設定部１５は、通信システム２０内のパスの起点となるエッジノードPEに、経路格納部１４に格納されたパスを設定する。

図２は、経路計算装置１のハードウェア構成図である。
経路計算装置１は、ＣＰＵ９０１と、ＲＡＭ９０２と、ＲＯＭ９０３と、ＨＤＤ９０４と、通信Ｉ／Ｆ９０５と、入出力Ｉ／Ｆ９０６と、メディアＩ／Ｆ９０７とを有するコンピュータ９００として構成される。
通信Ｉ／Ｆ９０５は、外部の通信装置９１５と接続される。入出力Ｉ／Ｆ９０６は、入出力装置９１６と接続される。メディアＩ／Ｆ９０７は、記録媒体９１７からデータを読み書きする。さらに、ＣＰＵ９０１は、ＲＡＭ９０２に読み込んだプログラム（アプリケーションや、その略のアプリとも呼ばれる）を実行することにより、各処理部を制御する。そして、このプログラムは、通信回線を介して配布したり、ＣＤ－ＲＯＭ等の記録媒体９１７に記録して配布したりすることも可能である。

図３は、経路計算装置１のメイン処理を示すフローチャートである。
入力部１１は、パス計算のための入力パラメータをオペレータから受け付ける（Ｓ１０１）。入力パラメータは、計算されるパスが満たすべきSLA（Service Level Agreement）などの要望を示す情報を含む。入力パラメータは、例えば、以下の情報である。
・１つ以上のＴＥ指標。例えば、第１ＴＥ指標＝遅延、第２ＴＥ指標＝ジッタ、第３ＴＥ指標＝帯域使用率。そして、第１ＴＥ指標が1位のパスを初回の基準パスとする。
・各ＴＥ指標において満たすべき許容範囲を示す目標値。例えば、遅延(10%)、ジッタ(10%)、帯域使用率(30%)。なお、遅延(10%)とは、基準パスの遅延が10msの場合、11ms以下の（100%+10%以下の）の遅延となるパスが許容範囲内である。
・各ＴＥ指標における重み。例えば重みa=1.2が指定された場合、第１ＴＥ指標の重み（aの0乗=1）、第２ＴＥ指標の重み（aの1乗=1.2）、第３ＴＥ指標の重み（aの2乗=1.44）が順に設定される。つまり、第NのＴＥ指標の重みは、aの(N-1)乗である。
・計算する経路数。例えば３つの経路を計算することで、３方向にトラヒックをロードバランスするなど。

経路計算部１２は、通信システム２０の状態を示すＮＷ（Network）情報の更新があるか否かを判定する（Ｓ１０２）。Ｓ１０２でYesならＳ１０３に進み、NoならＳ１０４に進む。Ｓ１０３では、情報収集部１３は、通信システム２０内のツールにＮＷ情報を要求し、その応答として更新されたＮＷ情報を取得する。ＮＷ情報は、例えば、以下の情報である。
・トポロジ情報
・メトリック情報
・遅延、ジッタ
・帯域使用率

経路計算部１２は、Ｓ１０１の入力パラメータおよびＳ１０３のＮＷ情報をもとに、これから通信システム２０内に設定する予定のパスを計算して経路格納部１４に格納する（Ｓ１０４、詳細は図４）。
経路計算部１２は、Ｓ１０４で計算したパスを経路格納部１４から読み取り、Ｓ１０１の入力パラメータで指定された条件（１つ以上のＴＥ指標の目標値）に適合するか否かを判定する（Ｓ１０５）。Ｓ１０５でYesならＳ１０６に進み、NoならＳ１０７に進む。
Ｓ１０６では、経路設定部１５は、計算したパスを通信システム２０内のパスの起点となるエッジノードPEに設定（インストール）し、処理をＳ１０２に戻す。

一方、Ｓ１０７では、今回のＳ１０４で計算したパスは採用できないので、次点のパスを計算する必要がある。例えば、第１ＴＥ指標の目標値と、第２ＴＥ指標の目標値との双方を満たす必要がある旨のSLAが、入力パラメータで指定されたとする。今回の基準パスは、第１ＴＥ指標では優先度１位であったが、第２ＴＥ指標では目標値を満たしておらず、結果として、指定された条件に適合しない（Ｓ１０５,No）。その場合、次点のパスとして、第１ＴＥ指標では優先度２位の新たな基準パスを設定し、再度Ｓ１０４を実行すればよい。

このような次点のパスとなる候補が存在しているうちは（Ｓ１０７,Yes）、経路計算部１２は、Ｓ１０４に戻って未計算の新たな基準パスを次々に試せばよい。
しかし、次点のパスとなる候補が存在しないとき（Ｓ１０７,No）、経路計算部１２は、今回の入力パラメータに適合するパスが見つからなかった旨をオペレータに通知する（Ｓ１０８）。

図４は、図３のパスの計算処理（Ｓ１０４）の詳細を示すフローチャートである。
以下、図５～図７の各テーブルを参照しつつ、図４に沿ってパスの計算処理（Ｓ１０４）を説明する。

経路計算部１２は、Ｓ１０１で与えられた第１ＴＥ指標（遅延）に基づき複数のパス生成を行う。このとき、経路計算部１２は、第１ＴＥ指標に最も適合するパスから順位をつけ、最も順位の高いパスを基準パスとする（Ｓ１１１）。
図５は、第１ＴＥ指標（遅延）に着目した各パスの優先度テーブルを示す。優先度テーブル内の数値（１～５）は、パス集合での相対的な順位（１位～５位）である。ここでは、遅延が少ない１位から順に、パスA,B,C,D,Eの順位となるので、１位の基準パスAが設定される。

図６は、第１ＴＥ指標～第３ＴＥ指標それぞれの各パスの優先度テーブルを示す。
各パスA,B,C,D,Eの第１ＴＥ指標における順位（１～５）は、図５で説明した通りである。
図６の優先度テーブルは、第１ＴＥ指標に加え、第２ＴＥ指標（ジッタ）と、第３ＴＥ指標（帯域使用率）と、基準パスから見た冗長度とを示す列が追加される。
図６の優先度テーブルは、基準パスAの優先度を示す行と、他パスB～Eの優先度を示す行とに加え、各ＴＥ指標における目標値（基準パスとの許容差分を示す値）の行と、各ＴＥ指標における重みの行とが追加される。

目標値の行では、Ｓ１０１の入力パラメータとして、以下が定義されている。
・基準パスAの遅延（例えば10ms）を100%とし、100+10%を超過する（>10%）遅延（例えば13msは130%）の他パスを目標値外とする。
・基準パスAのジッタを100%とし、100+10%を超過する（>10%）ジッタの他パスを目標値外とする。
・基準パスAの帯域使用率を100%とし、100+30%を超過する（>30%）帯域使用率の他パスを目標値外とする。
・基準パスAと他パスとで、通過するルータRが重複する割合を示す冗長度（通過するSIDの共有度）が25%以上の他パスを目標値外とする。例えば、基準パスが経由するルータRが4つあり、他パスが経由するルータRの内の1つのルータRが基準パスにも用いられる場合は、1/4で25%の冗長度となる。冗長度は低いほど基準パスからの独立性が高くなり、信頼性の高いパスである。

重みの行では、Ｓ１０１の入力パラメータとして、重みa=1.2が反映されている。
・第１ＴＥ指標には、重みを反映せず、５つのパスの順位の数値をそのまま優先度とする。なお、優先度は数値が小さいほど優先して採用されるパスを示す。
・第２ＴＥ指標には、５つのパスの順位の数値に、重みa=1.2を乗算した積を優先度とする。例えば、第２ＴＥ指標で２位のパスBは、２[位]×（重みa=1.2）＝2.4が優先度である。
・第３ＴＥ指標には、５つのパスの順位の数値に、重みaの2乗=1.44を乗算した積を優先度とする。例えば、第３ＴＥ指標で３位のパスDは、３[位]×（重みa^2=1.44）＝4.32が優先度である。

経路計算部１２は、第１ＴＥ指標の目標値を外れたパスを除外する（Ｓ１１２）。図６では、基準パスAの遅延（＝10ms）から110%（>10%）を超過する遅延の他パスは無いので、除外は行われない（図６の優先度のセルに「×」は記入されない）。

経路計算部１２は、Ｓ１０１で複数の（追加の）ＴＥ指標が与えられた場合（Ｓ１１３,Yes）、次のＴＥ指標（＝ジッタ）を第２ＴＥ指標とし、第２ＴＥ指標の順位に基づく他パスの優先度を設定する（Ｓ１１４）。なお、第２ＴＥ指標以降の優先度は、順位に重みづけを行った値とする。そして、経路計算部１２は、基準パスAの第２ＴＥ指標を100%とし、そこから目標値を外れたパスを除外する（Ｓ１１５）。
なお、図６では、ジッタの順位は、２位（パスC）、３位（パスD）、４位（パスB）、５位（パスE）となる。そして、５位（パスE）のジッタは、基準パスAのジッタから110%（>10%）を超過するので、除外される（優先度「×」）。

経路計算部１２は、第３ＴＥ指標（帯域使用率）以降についても同様の処理を行う（Ｓ１１３～Ｓ１１５）。
図６では、帯域使用率の順位は、１位（パスB）、２位（パスD）、３位（パスC）となる。そして、１～３位の各帯域使用率は、基準パスAの帯域使用率から130%（>30%）を超過しないので、除外は行われない（優先度「×」は記入されない）。なお、パスEは、前回のジッタですでに除外されたので、帯域使用率でも除外される（優先度「－」）。

経路計算部１２は、入力されたすべてのＴＥ指標で優先度を計算し終えた場合（Ｓ１１３,No）、基準パスと他パスとの冗長度に基づく優先度付けを行う（Ｓ１２１）。
経路計算部１２は、設定した冗長度の目標値を外れたパスを除外する（Ｓ１２２）。目標値を外れたパスの除外方法については、対象パスを削除する他、著しく優先度を下げるなどの方法が考えられる。
図６では、冗長度が低い順に、１位（パスE）、２位（パスC）、３位（パスD）、４位（パスB）となる。１位（パスE）はジッタですでに除外されたので、冗長度でも除外される。４位（パスB）は、基準パスAとの冗長度が25%を超過してしまったので、Ｓ１２２で除外されてしまう。

経路計算部１２は、算出した優先度の合計をパスごとに計算し、優先度の合計が小さい順に入力パラメータで指定された経路数（例えば３つの経路）を有効なパスとして選択する（Ｓ１２３）。経路計算部１２は、Ｓ１２３の有効なパスを経路格納部１４に格納する（Ｓ１３１）。

図７は、図６の優先度テーブルから優先度の合計を計算した結果である。
・基準パスAは、第１ＴＥ指標の１[位]がそのまま合計値となる。
・パスCは、3+2.4+5.76+2=13.16が合計値となる。
・パスDは、4+3.6+4.32+3=14.92が合計値となる。
よって、合計値が小さい順に、基準パスA、パスC、パスDの合計３つのパスが、有効なパスとして選択される（Ｓ１２３）。なお、第２ＴＥ指標で悪い順位のパスよりも、第３ＴＥ指標で悪い順位のパスのほうが、大きい重みが乗算されるので合計値も大きくなり、選ばれにくくなる。
これにより、各ＴＥ指標の順位を単純に合計しても同点になる場合でも、重みづけした優先度を合計すると同点にはならなくなり、有効なパスを一意に決定できる。

［効果］
本発明の経路計算装置１は、通信システム２０に設定するパスを選択するための指標を含む入力パラメータを受け付ける入力部１１と、
指標をもとに基準パスを選択するとともに、基準パスとは別の経路を通過する１つ以上の他パスについて、基準パスが通過するルータRを共有する度合いが低いほど優先的に選択する経路計算部１２と、
経路計算部１２が選択した基準パスおよび他パスを、通信システム２０に設定する経路設定部１５とを有することを特徴とする。

これにより、ＴＥ指標を用いたパス生成の利点を生かしつつ、複数経路への冗長度を考慮した信頼性の高いパスを生成できる。よって、例えばSRで複数のパスによりロードバランスを行う場合においても、信頼性の高い経路で分散できる。

本発明の経路計算装置１は、入力部１１が、入力パラメータとして、複数の前記指標と、各指標の許容範囲とを受け付け、
経路計算部１２が、他パスのうちの各指標の許容範囲を満たさないパスを除外することを特徴とする。
これにより、複数のＴＥ指標を経路選択に活用することで、複雑なユースケースに対応できる。

本発明の経路計算装置１は、経路計算部１２が、基準パスが各指標の許容範囲を満たさないときには、基準パスを変更することを特徴とする。
これにより、基準パスを選択したときに使用した指標とは別の指標で、所望の水準を満たさない基準パスを適切に除外できる。

本発明の経路計算装置１は、経路計算部１２が、各指標における他パスの順位と、各指標において互いに異なる重みづけ値とをもとに、各指標における他パスの優先度を計算し、計算した優先度をもとに、他パスを選択するときの優先順位を決定することを特徴とする。
これにより、指標が３つ以上指定されたときでも、他パスの優先順位が同点にならずに済む。

１経路計算装置
１１入力部
１２経路計算部
１３情報収集部
１４経路格納部
１５経路設定部
２０通信システム

Claims

通信システムに設定するパスを選択するためのパス単体を評価可能な複数の指標と、各指標の許容範囲とを含む入力パラメータを受け付ける入力部と、
前記指標をもとに基準パスを選択するとともに、前記基準パスとは別の経路を通過する１つ以上の他パスについて、前記他パスのうちの各指標の許容範囲を満たさないパスを除外した後、前記基準パスが通過するノードを別の経路として共有する度合いが低いほど、優先的に他パスを選択する経路計算部と、
前記経路計算部が選択した前記基準パスおよび前記他パスを、前記通信システムに設定する経路設定部とを有することを特徴とする
経路計算装置。
前記経路計算部は、前記基準パスが各指標の許容範囲を満たさないときには、前記基準パスを変更することを特徴とする
請求項１に記載の経路計算装置。
前記経路計算部は、各指標における前記他パスの順位と、各指標において互いに異なる重みづけ値とをもとに、各指標における前記他パスの優先度を計算し、計算した優先度をもとに、前記他パスを選択するときの優先順位を決定することを特徴とする
請求項１に記載の経路計算装置。
経路計算装置は、入力部と、経路計算部と、経路設定部とを有しており、
前記入力部は、通信システムに設定するパスを選択するためのパス単体を評価可能な複数の指標と、各指標の許容範囲とを含む入力パラメータを受け付け、
前記経路計算部は、前記指標をもとに基準パスを選択するとともに、前記基準パスとは別の経路を通過する１つ以上の他パスについて、前記他パスのうちの各指標の許容範囲を満たさないパスを除外した後、前記基準パスが通過するノードを別の経路として共有する度合いが低いほど、優先的に他パスを選択し、
前記経路設定部は、前記経路計算部が選択した前記基準パスおよび前記他パスを、前記通信システムに設定することを特徴とする
経路計算方法。
コンピュータを、請求項１ないし請求項３のいずれか１項に記載の経路計算装置として機能させるための経路計算プログラム。