特許ウォッチ

公開番号2024140899
公報種別公開特許公報(A)
公開日2024-10-10
出願番号2023052264
出願日2023-03-28
発明の名称探索プログラムおよび探索方法
出願人富士通株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06N 99/00 20190101AFI20241003BHJP(計算;計数)
要約【課題】トポロジー構造の評価にかかる計算量を削減する。
【解決手段】実施形態の探索プログラムは、コンピュータに、変換する処理と、求める処理と、生成する処理と、評価する処理とを実行させる。変換する処理は、評価対象とするネットワークのトポロジー構造およびネットワークの制約条件をネットワークフロー問題に変換する。求める処理は、変換したネットワークフロー問題について最大流量とする解を求める。生成する処理は、最大流量とする解に基づき、ネットワークフロー問題における最小カットを生成する。評価する処理は、生成した最小カットに対応するトポロジー構造の構成が制約条件を満たすか否かを評価する。
【選択図】図3
特許請求の範囲【請求項１】
評価対象とするネットワークのトポロジー構造および当該ネットワークの制約条件をネットワークフロー問題に変換し、
変換した前記ネットワークフロー問題について最大流量とする解を求め、
前記最大流量とする解に基づき、前記ネットワークフロー問題における最小カットを生成し、
生成した前記最小カットに対応する前記トポロジー構造の構成が前記制約条件を満たすか否かを評価する、
処理をコンピュータに実行させることを特徴とする探索プログラム。
続きを表示（約 610 文字）【請求項２】
前記変換する処理は、前記ネットワークフロー問題への変換を行う際に、前記トポロジー構造に含まれるサーバに対応するノードに対しては、前記サーバへの入力に対応する入力ノードと、前記サーバからの出力に対応する出力ノードとを作成し、前記入力ノードをネットワークフローの始点とする始点ノードへ接続し、前記出力ノードをネットワークフローの終点とする終点ノードへ接続する、
ことを特徴とする請求項１に記載の探索プログラム。
【請求項３】
前記トポロジー構造の構成が前記制約条件を満たさない場合、当該構成部分を増設したネットワークのトポロジー構造を新たな評価対象とし、前記変換する処理、前記求める処理、前記生成する処理および前記評価する処理を繰り返す、
ことを特徴とする請求項１に記載の探索プログラム。
【請求項４】
評価対象とするネットワークのトポロジー構造および当該ネットワークの制約条件をネットワークフロー問題に変換し、
変換した前記ネットワークフロー問題について最大流量とする解を求め、
前記最大流量とする解に基づき、前記ネットワークフロー問題における最小カットを生成し、
生成した前記最小カットに対応する前記トポロジー構造の構成が前記制約条件を満たすか否かを評価する、
処理をコンピュータが実行することを特徴とする探索方法。

発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、探索プログラムおよび探索方法に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
ネットワーク通信において、サーバ、スイッチとその間を結ぶケーブルの接続構成はトポロジー構造と呼ばれ、効率的なネットワーク通信を行うためには、このトポロジー構造が重要となる。
【０００３】
このネットワーク通信におけるトポロジー構造については、通信量の見積もりを評価し、所定の制約条件下において通信量を最大とするトポロジー構造の探索を行う従来技術がある。
【先行技術文献】
【特許文献】
【０００４】
米国特許第７６８０６４１号明細書
特開２０００－３４８０７３号公報
特開２０１５－１３０５５１号公報
米国特許出願公開第２０１８／０３４３１９１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の従来技術では、トポロジー構造の評価がＮＰ困難問題であることから、単純に全探索するとトポロジー構造に含まれるノード数の増加に対して指数関数的に計算量が増加するという問題がある。
【０００６】
１つの側面では、トポロジー構造の評価にかかる計算量を削減できる探索プログラムおよび探索方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
１実施形態の探索プログラムは、コンピュータに、変換する処理と、求める処理と、生成する処理と、評価する処理とを実行させる。変換する処理は、評価対象とするネットワークのトポロジー構造およびネットワークの制約条件をネットワークフロー問題に変換する。求める処理は、変換したネットワークフロー問題について最大流量とする解を求める。生成する処理は、最大流量とする解に基づき、ネットワークフロー問題における最小カットを生成する。評価する処理は、生成した最小カットに対応するトポロジー構造の構成が制約条件を満たすか否かを評価する。
【発明の効果】
【０００８】
１実施態様によれば、トポロジー構造の評価にかかる計算量を削減できる。
【図面の簡単な説明】
【０００９】
図１は、ネットワークフローの一例を説明する説明図である。
図２は、トポロジー構造のネットワークフローへの変換を説明する説明図である。
図３は、最小カットの一例を説明する説明図である。
図４は、実施形態にかかる探索装置の機能構成例を示すブロック図である。
図５は、実施形態にかかる探索装置の動作例を示すフローチャートである。
図６は、トポロジー構造と制約の一例を示す説明図である。
図７は、実施形態にかかる探索装置の動作例を示すフローチャートである。
図８は、送信元、宛先が複数あるトポロジー構造の一例を示す説明図である。
図９Ａは、送信元、宛先が複数あるトポロジー構造における最大流の計算例を示す説明図である。
図９Ｂは、送信元、宛先が複数あるトポロジー構造における最大流の計算例を示す説明図である。
図１０は、コンピュータ構成の一例を説明する説明図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、実施形態にかかる探索プログラムおよび探索方法を説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明する探索プログラムおよび探索方法は、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組みあわせてもよい。
（【００１１】以降は省略されています）

関連特許