Search

JP-2026076826-A - 情報処理装置、経路設計方法、及びプログラム

JP2026076826AJP 2026076826 AJP2026076826 AJP 2026076826AJP-2026076826-A

Abstract

【課題】複数パス間の制約を考慮してパスの経路を設計する。 【解決手段】複数のノードと複数のリンクとを有するネットワークにおいて、ノード間を接続する対象パスの経路を算出する情報処理装置であって、前記ネットワークの情報と、前記対象パスについての制約とを入力する入力部と、複数パスについての制約を含む複数の制約の下で、前記対象パスの経路を算出する制約ソルバを有する演算部と、前記演算部により算出された前記対象パスの経路を出力する出力部と、を備える。 【選択図】図２

Inventors

  • 田島 照久
  • 竹中 幹
  • 田辺 和輝
  • 藤原 達弥
  • 吉田 晴信

Assignees

  • ＮＴＴドコモビジネス株式会社

Dates

Publication Date
20260512
Application Date
20241024

Claims (8)

  1. 複数のノードと複数のリンクとを有するネットワークにおいて、ノード間を接続する対象パスの経路を算出する情報処理装置であって、 前記ネットワークの情報と、前記対象パスについての制約とを入力する入力部と、 複数パスについての制約を含む複数の制約の下で、前記対象パスの経路を算出する制約ソルバを有する演算部と、 前記演算部により算出された前記対象パスの経路を出力する出力部と を備える情報処理装置。
  2. 前記演算部は、前記対象パスの経路として、複数の候補経路を算出し、前記制約ソルバは、前記複数の候補経路の中から解となる経路を探索する 請求項１に記載の情報処理装置。
  3. 前記制約ソルバは、ＳＡＴソルバである 請求項１に記載の情報処理装置。
  4. 前記複数パスについての制約は、前記対象パスが冗長パスであること、前記対象パスが往復パスであること、前記対象パスが対称往復パスであること、又は、前記対象パスがＰ２ＭＰパスであることである 請求項１に記載の情報処理装置。
  5. 前記複数の制約は、 各リンクについて、リンクを通過するパスの合計帯域が当該リンクの帯域を超過しないという制約と、 種別の異なる複数パスが同じリンクを通らないという制約と、 を含む請求項１に記載の情報処理装置。
  6. 前記制約ソルバは、前記複数の制約の下で、解の良し悪しを示す目的関数が最良になるように前記対象パスの経路を算出する 請求項１に記載の情報処理装置。
  7. 複数のノードと複数のリンクとを有するネットワークにおいて、ノード間を接続する対象パスの経路を算出する情報処理装置が実行する経路設計方法であって、 前記ネットワークの情報と、前記対象パスについての制約とを入力するステップと、 制約ソルバを用いて、複数パスについての制約を含む複数の制約の下で、前記対象パスの経路を算出するステップと、 算出された前記対象パスの経路を出力するステップと を備える経路設計方法。
  8. コンピュータを、請求項１ないし６のうちいずれか１項に記載の情報処理装置における各部として機能させるためのプログラム。

Description

本発明は、ネットワークにおけるパスの経路を設計する技術に関連するものである。 現在、ＩＳＰ（Internet Service Provider）等が運用する商用のネットワークによるネットワークサービスが広く普及している。 ネットワークの運用者にとって、ＳＬＡ（Service Level Agreement、顧客が通信パス（以降、パスと呼ぶ）に求める制約）を保証することが重要である。ＳＬＡを保証するためには、パスの経路設計を適切に行うことが必要である。 井上 克巳, 田村 直之,"SATソルバーの基礎", 人工知能学会誌 2010 年 25 巻 1 号 p. 57-67、https://www.jstage.jst.go.jp/article/jjsai/25/1/25_57/_article/-char/ja/ 情報処理装置１００の構成例を示す図である。演算部１２０の機能構成例を示す図である。情報処理装置１００の動作を説明するためのフローチャートである。ネットワーク情報の例を示す図である。制約と出力の例を示す図である。情報処理装置１００のハードウェア構成例を示す図である。 以下、図面を参照して本発明の実施の形態（本実施の形態）を説明する。以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。以下ではまず、課題についてより詳細に説明し、その後に、本実施の形態に係る技術について説明する。 （一般的な課題について） 現在、ISP等が運用する商用のネットワークによるネットワークサービスが広く提供されている。ネットワークの運用者の抱える一般的な課題として、顧客の通信品質を担保することが難しいという課題がある。具体的には下記のとおりである。 ネットワークには一般に、ＳＬＡを保証する通信（ＳＬＡ保証型）と、ベストエフォートな通信（ベストエフォート型）が混在している。ＳＬＡの対象としては、例えば、遅延、ジッタ、帯域、稼働率、MTBF（Mean Time Between Failure）等がある。 ネットワークの運用者にとって、ＳＬＡを保証することが重要であり、特に要求制約の厳しいミッションクリティカルなサービスのパスの経路設計がＳＬＡを保証するにあたっての最優先事項となる。 上記の経路設計に関して、ネットワークの制御が適切に行われていない場合、リンク帯域に余裕を持った網設計であっても複数種別（型）のトラフィックが混在し、輻輳によりＳＬＡを満足できない可能性がある。また、ベストエフォート型であっても、通信品質の悪化は顧客のサービス満足度低下に繋がる。 従って、ミッションクリティカルなＳＬＡを担保しつつ、ベストエフォートな通信品質も向上できることが望ましい。 （具体的な課題について） 続いて、より具体的な課題について説明する。通信品質を担保するためのパス設計における課題として、複数パス間の制約を考慮することが難しいという点がある。 すなわち、ミッションクリティカルなサービスのＳＬＡでは、各パスの独立した制約に加えて複数のパス間に跨る制約の考慮が要求されるケースがある。複数パス間の制約が要求されるパスの例としては、例えば、「冗長パス(RedundantPath)」、「往復パス(RoundTripPath)」、「対称往復パス(SymmetricalRoundTripPath)」、「P2MP（point-to-multipoint）パス」等がある。 ネットワークにおける通信のルーティングプロトコルとして、一般にメトリックに基づくルーティングプロトコルが使用される。しかし、メトリックに基づく既存のルーティングプロトコルでは、パス間に依存関係を持つ制約を考慮することができない。すなわち、従来技術では、既存のルーティングプロトコルに基づくツールにより、メトリック最小となる経路設計を行い、パス間制約を満足するための各経路の設計については、試行錯誤しながら人手により行っている。このような状況では、工数的負担が大きくなり、また、属人的経路設計となることから、最適な解を得ることが難しい。 （技術的な課題について） 上記の課題に関連する技術的な課題について説明する。既存のPCE（Path Computation Element）の計算機構で利用されている経路計算手法において、パス計算部分の実装は、P2P（Point-to-Point）のパス計算(CSPF: constrained shortest path first)をベースに制約が考えられており、特にパス間の関係を考慮したMP2MP（Multipoint-to-Multipoint）のパス計算の種類に限りがある。なお、上記の制約の種類としては、例えば、「単一メトリック(IGP, TE, delay)を最小化する計算」、「帯域の空いているところを通る計算」等等がある。 上記のように、既存のツールには制限があることから、達成したい目標を既存ツールでカバーしきれない。ＳＬＡ要件の担保やネットワークリソースの効率的な利用には、既存ツールでは考慮できない複数パス間の依存関係に関する制約が重要となる。しかし、従来技術では、人手で試行錯誤して制約を満たす解を探索している。 以下、上記の課題を解決するための本実施の形態に係る装置構成と装置動作について説明する。 （実施の形態の概要） 本実施の形態では、後述する情報処理装置１００が、複数パス間の制約を考慮して、対象とするパスに対する経路設計を行う。具体的には、情報処理装置１００が、グラフ理論によりネットワークのトポロジをモデル化し、また、経路設計を最適化問題（例：充足性判定問題（ＳＡＴ））として定式化する。情報処理装置１００は、制約ソルバ（例：ＳＡＴソルバ）を利用して、制約を満足しつつ全体のメトリックが最良（例えば最小）となる経路を導出する。これにより複数パス間の制約を満たす経路を解として得ることができる。 なお、制約ソルバ自体は既存技術であり、例えば非特許文献１には制約ソルバの１つであるＳＡＴソルバが開示されている。ＳＡＴソルバは充足性判定問題（ＳＡＴ）を解く計算機のプログラムである。ＳＡＴソルバへの入力は変数を含む論理式の集合であり、ＳＡＴソルバからの出力はそれらの論理式を全て真にする変数の組み合わせである。 （情報処理装置１００の構成） 図１に、情報処理装置１００の構成例を示す。図１に示すように、情報処理装置１００は、入力部１１０、演算部１２０、及び出力部１３０を備える。 入力部１１０から、経路設計のための計算に必要となる情報を入力する。演算部１２０は、入力部１１０からの入力データに基づいて、経路設計の演算を実行する。出力部１３０は、演算部１２０による演算結果を出力する。 （入出力情報と演算部１２０の機能構成の例） 図２に、入出力情報と演算部１２０の機能構成例を示す。図２に示すように、演算部１２０は、変換部１２１、制約作成部１２２、候補経路作成部１２３、制約ソルバ１２４、及び解釈部１２５を有する。 演算部１２０には、ネットワーク情報、及び、「経路が記載されていないパス（始点と終点のみを指定したパス）と制約一覧」が入力される。なお、入力は、ネットワーク情報と、「経路が記載されていないパスと制約一覧」とに分かれている必要はなく、例えば、これらが一体となった情報が入力されてもよい。 変換部１２１は、入力情報から、グラフ表現のデータ構造を作成する。制約作成部１２２は、制約条件のコード化を行う。候補経路作成部１２３は、候補経路の作成を行う。制約ソルバ１２４は、変換部１２１、制約作成部１２２、及び候補経路作成部１２３により得られた情報に基づいて、最適化問題（例：充足性判定問題）を解くことにより論理値を出力する。解釈部１２５は、論理値をパスとして解釈し、経路が記載されたパス及び制約一覧を出力する。 （処理フロー） 図３のフローチャートを参照して、情報処理装置１００の動作例を説明する。 ＜Ｓ１（ステップ１）：入力、変換＞ Ｓ１において、入力部１１０から、ネットワーク情報とパス情報（例：経路が記載されていないパスと制約一覧）を入力し、変換部１２１が、入力情報を、グラフ表現のデータ構造として内部構造に変換する。変換された情報は制約ソルバ１２４に入力される。 図４に、入力されるネットワーク情報の一例を示す。図４に示すように、ネットワークは、複数のノードがリンクで接続された構成を有する。ノードは例えばルータ（ｒｔ）であるが、ルータに限定されない。図４に示すネットワーク情報は、リンクとノードの接続情報に加えて、例えば、各リンクの帯域幅の情報、及び各リンクの遅延の情報を含む。リンク上の数字は遅延を表している。 経路が記載されていないパスとは、例えば、始点と終点を指定したパスである。当該パスの制約とは、例えば、帯域を保証すること（例：１０Ｇｂｐｓ保証）、遅延差制約を持つ双方向パスであること、同一ホップかつ遅延差最小の双方向パスであること、等である。また、前述した「冗長パス(RedundantPath)」、「往復パス(RoundTripPath)」、「対称往復パス(SymmetricalRoundTripPath)」、「P2MP（point-to-multipoint）パス」等はいずれも制約の例である。「べストエフォート型パス」が制約であってもよい。 なお、実際の入力は例えばｊｓｏｎ形式で行われるが、ｊｓｏｎ形式に限定されるわけではなく、どのような形式を入力に用いてもよい。 ＜Ｓ２：候補経路作成＞ Ｓ２において、候補経路作成部１２３は、ネットワーク情報とパス情報とに基づき、経路算出の対象となる各パスの経路の候補（候補経路）の集合を作成する。具体的には、パス単体で満たされるべきＳＬＡが存在し、それを考慮した候補経路を事前に計算する。 例えば、候補経路作成部１２３は、パス単体（例：往復パスを構成する２つの単体パスのうちの１つ）のエンドポイント間（始点と終点との間）の複数経路のうち、当該パスの制約（例えば、遅延等のメトリックが閾値以下という制約）を満たす経路を探索し、良いメトリックを持つ経路から、１以上の経路を選択し、それを候補経路とする。 本実施の形態では、Ｓ２において、目的のパスの候補経路として、予め複数の候補経路を絞り込んでおき、制約ソルバ１２４により、複数の候補経路から、制約を満たし、かつ、目的関数が最良となるような経路を決定することとしている。これにより、探索空間を狭めることができ、迅速な処理が可能となる。 簡単な例で説明すると、例えば、１０００個のノードからなるネットワークにおいて、ノード１からノード１００へのパスＡの経路であって、制約を満たす経路を探索により決定する場合、探索すべき経路数は膨大になる。これに対し、パスＡの候補経路を例えば１０経路だけ事前に選択しておくことで、制約を満たすかどうかの探索を１０経路だけ行えばよいので、迅速な処理が可能となる。 ＜Ｓ３：制約作成＞ Ｓ３において、制約作成部１２２が、制約ソルバ１２４への入力となる制約である論理式を作成する。具体的には、下記のとおりである。 制約作成部１２２は、Ｓ１で入力された各パスについての制約に対応する条件文を論理式として作成する。この論理式が制約ソルバ１２４への入力となる。 一例として、複数パス間の制約に関して、制約作成部１２２は、冗長を目的としたパスであることを示す論理式、別の種別のパスにおいて同じリンクを共有しないことを示す論理式を作成する。 例えば、ノード１からノード３へのパスに関して、このパスは、「２本のパスからなる冗長パスであって、２本のパスの遅延差がｘ以下でなければならない」という制約が入力として与えられたとすると、制約作成部１２２は、この条件文に対応する論理式を作成する。なお、作成するものは論理式に限定されず、