(57)【要約】［課題］より短い時間間隔でブロッキングが生じない通信が実施されるタイムスロット一覧を生成できる通信管理一覧生成装置を提供する。［解決手段］通信管理一覧生成装置２０は、所定の時刻に対応する時刻情報と所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置であって、通信情報に通信処理の情報を追加可能であるか否かに関して時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定手段２１と、追加可能であると判定手段２１が判定した段階で判定された通信管理情報の通信情報に通信処理の情報を追加する追加手段２２とを備える。
2017064833.tif 000002
【特許請求の範囲】
【請求項１】
所定の時刻に対応する時刻情報と前記所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置であって、
通信情報に通信処理の情報を追加可能であるか否かに関して前記時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定手段と、
追加可能であると前記判定手段が判定した段階で判定された通信管理情報の通信情報に前記通信処理の情報を追加する追加手段とを備える
ことを特徴とする通信管理一覧生成装置。
【請求項２】
判定手段は、複数の通信処理に対して使用する最短経路と他の通信処理で使用される最短経路との距離の和が大きい順に通信処理の情報を追加可能であるか否かを判定する
請求項１記載の通信管理一覧生成装置。
【請求項３】
追加対象の通信処理の情報が全て追加されることによって生成された通信管理一覧を用いて実施される通信処理全体の所要時間を計測する計測手段を備え、
前記計測手段は、前記追加対象の通信処理の情報を基に生成される通信管理一覧の全てのパターンのうち前記所要時間が最小の通信管理一覧を出力する
請求項１または請求項２記載の通信管理一覧生成装置。
【請求項４】
通信処理の情報は、前記通信処理で使用される最短経路の全てのパターンのうち他の通信処理で使用される最短経路との距離の和が最大である最短経路の情報である
請求項１から請求項３のうちのいずれか１項に記載の通信管理一覧生成装置。
【請求項５】
所定の時刻に対応する時刻情報と前記所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置において実施される通信管理一覧生成方法であって、
通信情報に通信処理の情報を追加可能であるか否かに関して前記時刻情報に対応する時刻の早い順に各通信管理情報を判定し、
追加可能であると判定された段階で判定された通信管理情報の通信情報に前記通信処理の情報を追加する
ことを特徴とする通信管理一覧生成方法。
【請求項６】
複数の通信処理に対して使用する最短経路と他の通信処理で使用される最短経路との距離の和が大きい順に通信処理の情報を追加可能であるか否かを判定する
請求項５記載の通信管理一覧生成方法。
【請求項７】
追加対象の通信処理の情報が全て追加されることによって生成された通信管理一覧を用いて実施される通信処理全体の所要時間を計測し、
前記追加対象の通信処理の情報を基に生成される通信管理一覧の全てのパターンのうち前記所要時間が最小の通信管理一覧を出力する
請求項５または請求項６記載の通信管理一覧生成方法。
【請求項８】
所定の時刻に対応する時刻情報と前記所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成するコンピュータにおいて実行される通信管理一覧生成プログラムが記憶された記憶媒体であって、
前記コンピュータに、
通信情報に通信処理の情報を追加可能であるか否かに関して前記時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定処理、および
前記判定処理で追加可能であると判定された段階で判定された通信管理情報の通信情報に前記通信処理の情報を追加する追加処理
を実行させるための通信管理一覧生成プログラムが記憶された記憶媒体。
【請求項９】
コンピュータに、
複数の通信処理に対して使用する最短経路と他の通信処理で使用される最短経路との距離の和が大きい順に通信処理の情報を追加可能であるか否かを判定する判定処理を実行させる
請求項８記載の通信管理一覧生成プログラムが記憶された記憶媒体。
【請求項１０】
コンピュータに、
追加対象の通信処理の情報が全て追加されることによって生成された通信管理一覧を用いて実施される通信処理全体の所要時間を計測する計測処理、および
前記追加対象の通信処理の情報を基に生成される通信管理一覧の全てのパターンのうち前記所要時間が最小の通信管理一覧を出力する出力処理を実行させる
請求項８または請求項９記載の通信管理一覧生成プログラムが記憶された記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信管理一覧生成装置、通信管理一覧生成方法、および通信管理一覧生成プログラムに関し、特にメッセージを送信するタイミングが事前に定められる時分割方式において効率的なメッセージ送信を可能にする時分割スケジュールを生成する通信管理一覧生成装置、通信管理一覧生成方法、および通信管理一覧生成プログラムに関する。
【背景技術】
【０００２】
並列計算機等において、ノード間でデータを転送する方式にワームホールルーティングと呼ばれる方式がある。例えば、特許文献１には、プロセッサ間通信方式にワームホールルーティングが使用されている通信制御装置が記載されている。また、特許文献２には、ワームホールルーティングを行うルータおよび転送方法が記載されている。【０００３】
ワームホールルーティングでは、スイッチの各ポートにパケット１個分のバッファが設けられる。または、転送されるブロック（フリットとも呼ばれる）１個分のバッファが設けられる。【０００４】
送信先ポートのバッファが空くと、次のパケットが送信先ポートに向けて転送される。
すなわち、ワームホールルーティングでは高々１つのパケットまたは１つのフリットしか、ポート同士を結ぶ１つのリンクを一度に通過できない。【０００５】
以下、ワームホールルーティングを用いて実施される通信処理を、図２２を参照して説明する。図２２は、ワームホールルーティングを用いて実施される通信処理の例を示す説明図である。なお、簡単のため１パケットを１フリットとして扱う。【０００６】
図２２に示す円はスイッチを、矩形は端末をそれぞれ意味する。各端末および各スイッチは、単数または複数のポートを有している。また、各端末および各スイッチは、ポート同士を結ぶリンクを介して他の端末、または他のスイッチと通信可能に接続されている。
図２２に示す円と矩形を結ぶ１つの直線、または円同士を結ぶ１つの直線が、１つのリンクに対応する。【０００７】
図２２に示す通信ネットワークは、スイッチ１〜スイッチ９と、端末１１〜端末１３および端末１７〜端末１９と、リンクとで構成されている。また、図２２に示すｐ１等の接頭辞がｐの数字は、各スイッチおよび各端末のポートのポート番号を意味する。【０００８】
図２２に示す通信ネットワークにおいて、端末１１が端末１７に、および端末１２が端末１８に、所定の開始タイミングでパケットをそれぞれ送信する場合を考える。簡単のため、各パケットの各リンクの通過に要する時間は全て同一とする。【０００９】
端末１２は、「端末１２→スイッチ２→スイッチ５→スイッチ８→端末１８」の経路を通過するようにパケットＡを送信する。図２２に示す破線の矢印が、パケットＡの移動を表している。同時に、端末１１は、「端末１１→スイッチ１→スイッチ２→スイッチ５→スイッチ７→端末１７」の経路を通過するようにパケットＢを送信する。図２２に示す実線の矢印が、パケットＢの移動を表している。【００１０】
各端末が図２２に示すようにパケットを送信した場合、パケットＡとパケットＢは、スイッチ２とスイッチ５の間のリンクを同時に通過しようとしたとする。しかし、上記のようにワームホールルーティングでは１つのパケットしか１つのリンクを一度に通過できないため、本例ではどちらかのパケットがスイッチ２で停止する。【００１１】
上記のように転送されているパケットが途中で停止する現象をブロッキングと呼ぶ。図２２には、スイッチ２とスイッチ５の間のリンクでブロッキングが発生したことが示されている。【００１２】
ブロッキングが発生すると、パケットが予定通り転送されないため、通信遅延が発生する。また、通信ネットワーク内の一部の箇所でブロッキングが発生すると、他のパケットもブロッキングにより停止したパケットの影響を受けて停止し、結果的に通信ネットワーク全体でブロッキングが連鎖的に発生する。【００１３】
ブロッキングの発生、およびブロッキングの連鎖的な発生は、組み込み系システム等の即時性が要求されるシステムにおいて致命的な問題である。例えば、人工衛星や車載制御装置で通信遅延が発生すると、重大な事故が引き起こされる可能性がある。【００１４】
ブロッキングの発生を防止するために、ワームホールルーティングが使用される通信処理を設計する時に、通信の順番を定めることが考えられる。以下、ワームホールルーティング機構を有する通信ネットワークにおいて、同じネットワークリンクをパケットが同時に通過できずにブロッキングが発生することを防止するために、タイムスロット一覧を生成する方式を説明する。【００１５】
図２３は、タイムスロット一覧の例を示す説明図である。図２３に示すタイムスロット一覧は、通信管理情報で構成される。通信管理情報は、タイムスロットと通信経路とで構成される。同一の通信管理情報に含まれるタイムスロットと通信経路は、通信経路に対応する通信が、タイムスロットに相当する時刻に開始されるという関係を有する。なお、通信経路内の各数字は、図２２に示すスイッチまたは端末に対応する。【００１６】
例えば、自身の内部に導入されているアプリケーション用の通信パケットを送信する場合、端末は、タイムスロット管理装置等に通信パケットが送信される通信の実施を要求する。他の端末からも通信の実施を要求されたタイムスロット管理装置は、図２３に示すようなタイムスロット一覧を作成することによって、通信を管理する。【００１７】
タイムスロット管理装置が管理する通信ネットワーク内では、タイムスロット管理装置が作成したタイムスロット一覧に基づいて通信が実施される。図２３に示すタイムスロット一覧の例では、「端末１２→スイッチ２→スイッチ５→スイッチ８→端末１８」の通信経路に対応する通信の実施が要求されていれば、タイムスロット０に相当する時刻に対応する通信が開始される。また、「端末１３→スイッチ３→スイッチ５→スイッチ７→端末１７」の通信経路に対応する通信の実施も要求されていれば、タイムスロット０に相当する時刻に対応する通信が開始される。【００１８】
タイムスロット０に相当する時刻が過ぎれば、次はタイムスロットが１の通信管理情報に基づいて通信が実施される。タイムスロット１〜タイムスロット３に相当する時刻になり、タイムスロット一覧が示す通信経路に対応する通信の実施が要求されていれば、各時刻に対応する通信がそれぞれ開始される。【００１９】
図２３に示すタイムスロット一覧が使用される場合、タイムスロット９に相当する時刻が過ぎれば、再度タイムスロットが０の通信管理情報に基づいて通信が実施される。このように、タイムスロット一覧には通信の実施の順番が定められている。【００２０】
なお、タイムスロットが４の通信管理情報からタイムスロットが９の通信管理情報には各タイムスロットに相当する時刻に開始される通信が割り当てられていないため、各通信管理情報の通信経路は空欄である。図２３に示すタイムスロット一覧以外のタイムスロット一覧においても通信経路が空欄の通信管理情報には、通信が割り当てられていない。【００２１】
図２３に示すタイムスロット一覧に基づいて実施される各通信によるリンクの使用タイミングを、図２４に示す。図２４は、図２３に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。【００２２】
図２４に示すタイムチャートの横軸は、タイムスロット、すなわち時刻に対応するタイムスロット軸である。また、図２４に示すタイムチャートの縦軸は、通信ネットワーク内のリンクに対応するリンク軸である。例えば、図２４に示すタイムチャートのリンク軸における「１→２」は、図２２に示す通信ネットワーク内の、スイッチ１とスイッチ２の間のリンクを示す。【００２３】
図２４に示すタイムチャート内の各折れ線は、図２３に示すタイムスロット一覧に基づいて実施される各通信に対応する。例えば、図２４に示す□の折れ線において、タイムスロット２とリンク「１→２」の交点に□が示されている。【００２４】
上記の□は、タイムスロット２に相当する時刻からタイムスロット３に相当する時刻の間に、□の折れ線に対応する通信がリンク「１→２」を使用することを示す。図２４のような図を、本明細書内でタイムチャートと呼ぶ。以上のように、タイムチャートは、通信リンクの使用状況を示す。【００２５】
他の折れ線も、□の折れ線と同様の内容を示す。タイムチャート内で２つ以上の印が同じ箇所に示されていなければ、タイムチャートが示す各通信は、同時に同じリンクを使用しない。すなわち、タイムチャートが示す各通信において、ブロッキングが生じない。【００２６】
図２３に示すタイムスロット一覧に基づいて実施される通信全体の終了時刻は、図２４に示すタイムチャートを参照すると、×で示されているリンク「スイッチ９→端末１９」を使用する通信の終了時刻であるタイムスロット９に相当する時刻である。【００２７】
タイムスロット一覧に基づいて実施される通信全体の完了までに要するタイムスロットの数を、タイムスロット一覧のタイムスロット数とする。よって、図２３に示すタイムスロット一覧のタイムスロット数は９である。【００２８】
図２３に示すようなタイムスロット一覧は、手動で設計されることが多い。しかし、ワームホールルーティングネットワークで使用されるタイムスロット一覧の生成方式も提案されている。例えば、非特許文献１には、装置に適用されるタイムスロット一覧生成方式が記載されている。【００２９】
図２５は、非特許文献１に記載されているタイムスロット一覧生成装置の構成例を示すブロック図である。図２５に示すように、タイムスロット一覧生成装置９００は、最短経路生成手段９１０と、セグメント分割手段９２０と、セグメント用タイムスロット割当手段９３０とを備える。【００３０】
最短経路生成手段９１０は、図２５に示すように、ネットワークトポロジ情報と、端点対リストとを入力とする。端点対リストは、端点対情報で構成される。端点対情報には、所定の通信で転送されるパケットの通信ネットワークへの流入ポートと、パケットの通信ネットワークからの流出ポートの組が指定されている。【００３１】
最短経路生成手段９１０は、ネットワークトポロジ情報と端点対リストとを用いて、各通信の流入ポートから流出ポートまでの最短経路を求める。次いで、最短経路生成手段９１０は、求められた最短経路で構成された経路リストを生成する。【００３２】
次いで、セグメント分割手段９２０は、最短経路生成手段９１０が生成した経路リスト内の経路を、同じリンクを全く経由しない経路ごとにグループ化する。セグメント分割手段９２０により生成された経路のグループをセグメントと呼ぶ。【００３３】
次いで、セグメント用タイムスロット割当手段９３０は、１つのセグメントの経路を１つの通信管理情報に割り当てる。タイムスロット一覧生成装置９００により生成されるタイムスロット一覧の例を図２６に示す。図２６は、タイムスロット一覧の他の例を示す説明図である。上記のように、図２６に示す同一の通信管理情報に割り当てられている各経路は、同時に同じリンクを経由しない。【００３４】
また、セグメント用タイムスロット割当手段９３０は、以下のように各セグメントの経路を割り当てる。まず、セグメント用タイムスロット割当手段９３０は、最初のセグメントの経路をタイムスロットが０の通信管理情報に割り当てる。図２６に示すように、タイムスロットが０の通信管理情報に割り当てられた経路は２つある。【００３５】
次いで、セグメント用タイムスロット割当手段９３０は、前に割り当てられたセグメントの経路に対応する通信が全て終了する時刻に相当するタイムスロットの、次のタイムスロットの通信管理情報に次のセグメントの経路を割り当てる。タイムスロットが０の通信管理情報に割り当てられた経路に対応する通信が全て終了する時刻は、タイムスロット５に相当する。【００３６】
よって、セグメント用タイムスロット割当手段９３０は、タイムスロットが６の通信管理情報に次のセグメントの経路を割り当てる。同様に、セグメント用タイムスロット割当手段９３０は、残り２つのセグメントの経路を、タイムスロットが１３の通信管理情報、タイムスロットが１８の通信管理情報にそれぞれ割り当てる。【００３７】
従って、図２６に示すタイムスロット一覧に基づいて実施される通信の場合、同じタイムスロットで開始される通信群は、同時に同じリンクを使用しない。かつ、開始された通信群が全て終了するまで、他の通信は開始されない。よって、非特許文献１に記載されているタイムスロット一覧生成装置が生成するタイムスロット一覧が用いられると、ブロッキングが発生しない通信が実施される。【００３８】
図２７は、図２６に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。図２６に示すタイムスロット一覧に基づいて実施される通信全体の終了時刻は、図２７に示すタイムチャートを参照すると、タイムスロット２３に相当する時刻である。タイムスロット２３に相当する時刻は、図２７に◆で示されているリンク「スイッチ９→端末１９」を使用する通信と、×で示されているリンク「スイッチ７→端末１７」を使用する通信の終了時刻である。すなわち、図２６に示すタイムスロット一覧のタイムスロット数は２３であり、図２３に示すタイムスロット一覧のタイムスロット数より大きい。
【先行技術文献】
【特許文献】
【００３９】
【特許文献１】特開平６−２４３１１６号公報
【特許文献２】特開２０１３−００５０８０号公報
【非特許文献】
【００４０】
【非特許文献１】高田光隆他. “SpaceWireのリアルタイム性を保証するソフトウェアプラットフォームの開発”第57回宇宙科学技術連合講演会講演集
【発明の概要】
【発明が解決しようとする課題】
【００４１】
ワームホールルーティングが用いられる通信ネットワークを構築する際、タイムスロット数の小さいタイムスロット一覧を設計することが重要である。その理由は、例えば図２３に示すタイムスロット一覧のタイムスロット数は９である。よって、端末が通信の実施を要求した場合、端末は、通信が実施されるまで最大９タイムスロット分待たされる可能性がある。【００４２】
また、図２６に示すタイムスロット一覧のタイムスロット数は２３である。よって、端末が通信の実施を要求した場合、端末は、通信が実施されるまで最大２３タイムスロット分待たされる可能性がある。すなわち、タイムスロット数が大きいタイムスロット一覧が使用されると平均待機時間が長くなり、通信の実施により多くの時間を要することが想定され、効率的に通信が実施されなくなると考えられるためである。【００４３】
作成元の通信経路はどちらも同じであるが、図２３に示すタイムスロット一覧のタイムスロット数と図２６に示すタイムスロット一覧のタイムスロット数は、それぞれ９と２３であり異なる。すなわち、非特許文献１に記載されている方式の問題点は、生成されるタイムスロット一覧のタイムスロット数が大きくなることである。【００４４】
その理由は、非特許文献１に記載されている方式では、通信経路がセグメントに分割される。同一のセグメントの経路は、同一の通信管理情報に割り当てられる。また、前のセグメントに対応する通信群が全て完了するまで、次のセグメントに対応する通信群が開始されないように、各セグメントの経路が各通信管理情報に割り当てられる。【００４５】
すなわち、１つのセグメントの経路に対応する通信が実施される時間帯に対応する通信管理情報に他のセグメントの経路は割り当てられず、複数のセグメントそれぞれに対応する通信が同じ時間帯に実施されることが許容されていないためである。【００４６】
図２７に示すように、各セグメントに対応する通信が実施されている間、通信パケットが通過していないリンクが通信ネットワーク内に多数存在する。従って、非特許文献１に記載されている方式で生成されたタイムスロット一覧が使用される場合、通信が非効率的に実施される可能性が高い。【００４７】
上記のように、ワームホールルーティングが用いられる通信処理におけるブロッキングを防止するために生成されるタイムスロット一覧の生成方式として、より短い時間間隔で通信が実施されるタイムスロット一覧の生成方式が求められている。【００４８】
そこで、本発明は、より短い時間間隔でブロッキングが生じない通信が実施されるタイムスロット一覧を生成できる通信管理一覧生成装置、通信管理一覧生成方法、および通信管理一覧生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００４９】
本発明による通信管理一覧生成装置は、所定の時刻に対応する時刻情報と所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置であって、通信情報に通信処理の情報を追加可能であるか否かに関して時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定手段と、追加可能であると判定手段が判定した段階で判定された通信管理情報の通信情報に通信処理の情報を追加する追加手段とを備えることを特徴とする。【００５０】
本発明による通信管理一覧生成方法は、所定の時刻に対応する時刻情報と所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置において実施される通信管理一覧生成方法であって、通信情報に通信処理の情報を追加可能であるか否かに関して時刻情報に対応する時刻の早い順に各通信管理情報を判定し、追加可能であると判定された段階で判定された通信管理情報の通信情報に通信処理の情報を追加することを特徴とする。【００５１】
本発明による通信管理一覧生成プログラムは、所定の時刻に対応する時刻情報と所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成するコンピュータにおいて実行される通信管理一覧生成プログラムであって、コンピュータに、通信情報に通信処理の情報を追加可能であるか否かに関して時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定処理、および判定処理で追加可能であると判定された段階で判定された通信管理情報の通信情報に通信処理の情報を追加する追加処理を実行させることを特徴とする。
【発明の効果】
【００５２】
本発明によれば、より短い時間間隔でブロッキングが生じない通信が実施されるタイムスロット一覧を生成できる。
【図面の簡単な説明】
【００５３】
【図１】本発明によるタイムスロット一覧生成装置１００の第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【図３】最短疎経路生成手段１１０による経路リスト生成処理の動作を示すフローチャートである。
【図４】始点と終点の組が同一である経路の集合の例を示す説明図である。
【図５】タイムスロット割当手段１２０によるタイムスロット一覧生成処理の動作を示すフローチャートである。
【図６】本発明によるタイムスロット一覧生成装置１００の第２の実施形態の構成例を示すブロック図である。
【図７】第２の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【図８】本発明によるタイムスロット一覧生成装置１００の第３の実施形態の構成例を示すブロック図である。
【図９】第３の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【図１０】網羅的タイムスロット割当手段１４０によるタイムスロット一覧生成処理の動作を示すフローチャートである。
【図１１】第４の実施形態の処理対象の通信が実施される範囲のネットワークトポロジの例を示す説明図である。
【図１２】第４の実施形態において最短疎経路生成手段１１０に入力される端点対リストの例を示す説明図である。
【図１３】第４の実施形態において最短疎経路生成手段１１０が生成する経路リストの例を示す説明図である。
【図１４】第４の実施形態においてタイムスロット割当手段１２０が生成するタイムスロット一覧の例を示す説明図である。
【図１５】図１４に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【図１６】第４の実施形態において降順距離経路並べ替え手段１３０が生成する並べ替えられた経路リストの例を示す説明図である。
【図１７】第４の実施形態においてタイムスロット割当手段１２０が生成するタイムスロット一覧の他の例を示す説明図である。
【図１８】図１７に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【図１９】第４の実施形態において網羅的タイムスロット割当手段１４０が生成するタイムスロット一覧の例を示す説明図である。
【図２０】図１９に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【図２１】本発明による通信管理一覧生成装置の概要を示すブロック図である。
【図２２】ワームホールルーティングを用いて実施される通信処理の例を示す説明図である。
【図２３】タイムスロット一覧の例を示す説明図である。
【図２４】図２３に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【図２５】非特許文献１に記載されているタイムスロット一覧生成装置の構成例を示すブロック図である。
【図２６】タイムスロット一覧の他の例を示す説明図である。
【図２７】図２６に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【発明を実施するための形態】
【００５４】
実施形態１． 
［構成の説明］
以下、本発明の実施形態を、図面を参照して説明する。図１は、本発明によるタイムスロット一覧生成装置１００の第１の実施形態の構成例を示すブロック図である。タイムスロット一覧生成装置１００は、例えば、ワームホールルーティングが用いられる通信の実施に使用されるタイムスロット一覧を通信においてブロッキングが発生しないように生成するタイムスロット一覧生成装置である。
【００５５】
図１に示すタイムスロット一覧生成装置１００は、最短疎経路生成手段１１０と、タイムスロット割当手段１２０とを備える。
【００５６】
最短疎経路生成手段１１０は、図１に示すようにネットワークトポロジ情報と、端点対リストとを入力とする。最短疎経路生成手段１１０は、端点対リストを構成する端点対情報が示す始点と終点を結ぶ通信ネットワーク内の最短経路を端点対情報ごとに算出する。
【００５７】
次いで、最短疎経路生成手段１１０は、算出された最短経路で構成された経路リストを生成する。経路リストに含まれる経路同士は、同じ時間帯に通信ネットワーク内の同じリンクをできる限り経由しない。
【００５８】
タイムスロット割当手段１２０は、経路リストを入力とし、経路リストに含まれる経路同士が重ならないようにタイムスロットが異なる通信管理情報それぞれに経路を割り当てる。なお、経路同士が重ならないとは、各経路が同じ時間帯に通信ネットワーク内の同じリンクを経由しないことを意味する。タイムスロット割当手段１２０は、割り当て可能な経路リスト内の経路が全て割り当てられたタイムスロット一覧を出力する。
【００５９】
［動作の説明］
以下、本実施形態のタイムスロット一覧生成装置１００の動作を図２を参照して説明する。図２は、第１の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【００６０】
最短疎経路生成手段１１０は、端点対リストとネットワークトポロジ情報とを入力とする。次いで、最短疎経路生成手段１１０は、各端点対情報に対応する最短経路で構成された経路リストを生成する（ステップＳ１１０）。
【００６１】
次いで、タイムスロット割当手段１２０は、同じ時間帯に同じリンクが経由されないように、経路リスト内の経路を通信管理情報に割り当てる（ステップＳ１２０）。タイムスロット割当手段１２０は、割り当て可能な経路リスト内の経路が全て割り当てられたタイムスロット一覧を出力する。タイムスロット一覧を出力した後、タイムスロット一覧生成装置１００は、生成処理を終了する。
【００６２】
以下、本実施形態の最短疎経路生成手段１１０の動作を図３を参照して説明する。図３は、最短疎経路生成手段１１０による経路リスト生成処理の動作を示すフローチャートである。すなわち、図３に示すステップＳ１１１〜ステップＳ１１８の処理は、図２に示すステップＳ１１０の処理に相当する。
【００６３】
最短疎経路生成手段１１０には、端点対リストとネットワークトポロジ情報とが入力される。すなわち、計算ループに入る（ステップＳ１１１）。
【００６４】
次いで、最短疎経路生成手段１１０は、入力された端点対リスト内の端点対情報が示す始点から終点までの最短経路を計算する。なお、最短経路は、例えば、既知の方法で計算され、複数算出され得る。最短疎経路生成手段１１０は、計算された最短経路を、作業領域に記憶されている最短経路一覧に追加する（ステップＳ１１２）。
【００６５】
最短疎経路生成手段１１０は、入力された端点対リストの中で最短経路が計算されていない端点対情報の始点が存在する間、ステップＳ１１２の処理を繰り返し行う。端点対リスト内の端点対情報の全ての始点からの最短経路が計算されたとき、最短疎経路生成手段１１０は、計算ループを抜ける（ステップＳ１１３）。
【００６６】
次いで、最短疎経路生成手段１１０には、端点対リストと最短経路一覧とが入力される。すなわち、追加ループに入る（ステップＳ１１４）。
【００６７】
最短疎経路生成手段１１０は、入力された最短経路一覧内の経路の中で、始点と終点の組が同一である経路の集合を探索する（ステップＳ１１５）。
【００６８】
図４は、始点と終点の組が同一である経路の集合の例を示す説明図である。図４に示す例では、集合に含まれる任意の経路の始点は全てｎ１であり、かつ任意の経路の終点は全てｎ２である。
【００６９】
次いで、最短疎経路生成手段１１０は、ステップＳ１１５で取得された経路の集合のうち、最短経路一覧内の他の経路との距離の和が最も大きな経路を求め、求められた経路を疎経路にする（ステップＳ１１６）。経路p1と経路p2の間の距離d(p1, p2)は、以下の式（１）に示すように定義される。
【００７０】
d(p1, p2) ::= max(|p1|, |p2|) − overlap(p1, p2)  ・・・式（１）
【００７１】
式（１）におけるpは経路であり、|p|は、経路pが経由するノード数、すなわち経路長を表す。また、式（１）におけるmax(|p1|, |p2|)は、|p1|の経路長と|p2|の経路長のうち、長い方の経路長を表す。また、式（１）におけるoverlap(p1, p2) は、p1とp2が、始点から同じ距離で経由する同じリンクの数を表し、以下の式（２）に示すように定義される。
【００７２】
overlap(p1, p2) ::= |{p1[i] = p2[i] | 0<= i < min(|p1|, |p2|)}|  ・・・式（２）
【００７３】
式（２）におけるp[i]は、経路pがi番目に経由するノードを表す。p[0]は始点ノードを表し、p[|p|-1]は終点ノードを表す。また、式（２）におけるmin(|p1|, |p2|)は、|p1|の経路長と|p2|の経路長のうち、短い方の経路長を表す。
【００７４】
例えば、経路p1と経路p2が、以下に示すように定義されている場合を考える。
【００７５】
p1 ::=  n1 → n2 → n3 → n5 → n6
p2 ::=  n1 → n2 → n4 → n3 → n5
【００７６】
上記の場合、経路p1と経路p2は、始点から距離０で同じリンク「n1→n2」を経由する。
他に経由される共通のリンクはないので、overlap(p1, p2) = 2になる。すなわち、{p1[i] = p2[i] | 0<= i < min(|p1|, |p2|)}は、始点から同じ距離iで経路p1および経路p2が経由する、共通の物理リンクの集合を表す。
【００７７】
ステップＳ１１６で算出される経路と最短経路一覧内の他の経路との距離の和は、例えば、Σd(p, pk)のように表される値である。最短疎経路生成手段１１０は、Σd(p, pk)が最大になる経路を求め、求められた経路を疎経路として経路リストに追加する（ステップＳ１１７）。
【００７８】
最短疎経路生成手段１１０は、入力された端点対リストの中で疎経路が追加されていない端点対情報が存在する間、ステップＳ１１５〜ステップＳ１１７の処理を繰り返し行う。端点対リスト内の全ての端点対情報の疎経路が追加されたとき、最短疎経路生成手段１１０は、追加ループを抜け（ステップＳ１１８）、経路リスト生成処理を終了する。
【００７９】
次に、本実施形態のタイムスロット割当手段１２０の動作を図５を参照して説明する。
図５は、タイムスロット割当手段１２０によるタイムスロット一覧生成処理の動作を示すフローチャートである。すなわち、図５に示すステップＳ１２１〜ステップＳ１３１の処理は、図２に示すステップＳ１２０の処理に相当する。
【００８０】
タイムスロット割当手段１２０には、最短疎経路生成手段１１０が生成した経路リストが入力される。すなわち、生成ループに入る（ステップＳ１２１）。
【００８１】
次いで、タイムスロット割当手段１２０は、タイムスロット割当時刻ｔを０に設定する（ステップＳ１２２）。タイムスロット割当時刻ｔは、通信管理情報のタイムスロットに対応する値である。次いで、タイムスロット割当手段１２０は、入力された経路リストから経路を１つ取り出す（ステップＳ１２３）。すなわち、割当ループに入る（ステップＳ１２４）。
【００８２】
タイムスロット割当手段１２０は、ステップＳ１２３で取り出された経路を、時刻ｔの通信管理情報に割り当て可能であるか否かを判定する（ステップＳ１２５）。取り出された経路がタイムスロット一覧内の時刻ｔの通信管理情報の通信経路と同じ時間帯に同じリンクを経由しない場合、タイムスロット割当手段１２０は、割り当て可能であると判定する。
【００８３】
割り当て可能でないと判定された場合（ステップＳ１２６におけるＮｏ）、タイムスロット割当手段１２０は、タイムスロット割当時刻ｔに１を加算する（ステップＳ１２７）。次いで、タイムスロット割当手段１２０は、再度ステップＳ１２５の処理を行う。
【００８４】
割り当て可能であると判定された場合（ステップＳ１２６におけるＹｅｓ）、タイムスロット割当手段１２０は、ステップＳ１２３で取り出された経路を、時刻ｔの通信管理情報に割り当てる（ステップＳ１３０）。次いで、タイムスロット割当手段１２０は、再度ステップＳ１２２の処理を行う。
【００８５】
タイムスロット割当手段１２０は、タイムスロット割当時刻ｔが上限値に達するまで、ステップＳ１２５〜ステップＳ１２７の処理を繰り返し行う。タイムスロット割当時刻ｔが上限値に達したとき、タイムスロット割当手段１２０は、割当ループを抜け（ステップＳ１２８）、ステップＳ１２３で取り出された経路を削除する（ステップＳ１２９）。
【００８６】
なお、タイムスロット割当手段１２０は、ステップＳ１２３で取り出された経路を削除せずに、作業領域で保管してもよい。削除した後、タイムスロット割当手段１２０は、再度ステップＳ１２２の処理を行う。
【００８７】
タイムスロット割当時刻ｔの上限値は、例えば、タイムスロット一覧生成装置１００の利用者から与えられる定数である。タイムスロット割当時刻ｔの上限値は、対象の通信ネットワークごとに決定される。
【００８８】
タイムスロット割当手段１２０は、入力された経路リストの中で処理されていない経路が存在する間、すなわち入力された経路リストが空になるまで、ステップＳ１２２〜ステップＳ１３０の処理を繰り返し行う。経路リスト内の全ての経路が処理されたとき、タイムスロット割当手段１２０は、生成ループを抜け（ステップＳ１３１）、タイムスロット一覧生成処理を終了する。
【００８９】
［効果の説明］
次に、本実施形態の効果を説明する。本実施形態のタイムスロット一覧生成装置は、最短疎経路生成手段が同一時間に同じリンクが２つ以上の通信にできる限り使用されないように経路群を生成し、タイムスロット割当手段が経路群のうち、同時に同じリンクを経由しない経路同士を同じ通信管理情報に割り当てる。
【００９０】
割り当てる際、タイムスロット割当手段は、タイムスロットが小さい通信管理情報から経路を割り当て、経路群ができる限り少ない通信管理情報に割り当てられるようにする。
よって、タイムスロット一覧生成装置は、より短い時間間隔で通信が実施されるタイムスロット一覧を生成できる。生成されたタイムスロット一覧が用いられると、より短時間でより多くの通信が実施される。
【００９１】
非特許文献１に記載されている方式で生成されたタイムスロット一覧が使用された場合、各セグメントの通信間で実施時間が重なる時間帯がないため、通信に使用されないリンクが多く存在する。
【００９２】
本実施形態のタイムスロット一覧生成装置は通信経路をセグメントに分割しない。また、本実施形態のタイムスロット割当手段は、各通信経路を、タイムスロット一覧内の通信経路が空データのままの通信管理情報にも割り当てることができる。よって、本実施形態で生成されたタイムスロット一覧が使用されると、通信間で実施時間が重なる時間帯が存在し、より短時間でより多くの通信が実施される。
【００９３】
実施形態２．
［構成の説明］
次に、本発明の第２の実施形態を、図面を参照して説明する。図６は、本発明によるタイムスロット一覧生成装置１００の第２の実施形態の構成例を示すブロック図である。
【００９４】
図６に示すタイムスロット一覧生成装置１００は、最短疎経路生成手段１１０と、タイムスロット割当手段１２０と、降順距離経路並べ替え手段１３０とを備える。本実施形態のタイムスロット一覧生成装置１００は、図１に示すタイムスロット一覧生成装置１００と異なり、降順距離経路並べ替え手段１３０を備える。
【００９５】
降順距離経路並べ替え手段１３０は、最短疎経路生成手段１１０が生成した経路リストを入力とする。降順距離経路並べ替え手段１３０は、経路リスト内の経路と他の経路との距離の和を計算する。次いで、降順距離経路並べ替え手段１３０は、距離の和が大きい順に経路リスト内の経路を並べ替え、経路が並べ替えられた新たな経路リストを生成する。
【００９６】
距離の和が大きい順に降順距離経路並べ替え手段１３０が経路リスト内の経路を並べ替えることによって、タイムスロット割当手段１２０は、他の経路との重なりが少ない経路から順に通信管理情報に経路を割り当てることができる。よって、他の経路との重なりが少ない経路同士が同じ通信管理情報に割り当てられやすくなり、生成されるタイムスロット一覧のタイムスロット数が第１の実施形態よりも削減される可能性が高まる。
【００９７】
［動作の説明］
以下、本実施形態のタイムスロット一覧生成装置１００の動作を図７を参照して説明する。図７は、第２の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【００９８】
最短疎経路生成手段１１０は、端点対リストとネットワークトポロジ情報とを入力とする。次いで、最短疎経路生成手段１１０は、端点対リスト内の端点対情報ごとに、端点同士を結ぶ最短経路であって、他の経路と同時に同じリンクをできるだけ経由しない経路を生成する。
【００９９】
次いで、最短疎経路生成手段１１０は、生成された経路で構成された経路リストを出力する（ステップＳ２１０）。なお、ステップＳ２１０の処理は、図２に示すステップＳ１１０の処理と同様である。
【０１００】
次いで、降順距離経路並べ替え手段１３０は、最短疎経路生成手段１１０が出力した経路リスト内の経路を、他の経路との距離の和が大きい順に並べ替える（ステップＳ２２０）。降順距離経路並べ替え手段１３０は、経路が並べ替えられた経路リストを出力する。
【０１０１】
次いで、タイムスロット割当手段１２０は、降順距離経路並べ替え手段１３０が出力した経路リスト内の経路を、同じ時間帯に同じリンクが経由されないように、通信管理情報に割り当てる（ステップＳ２３０）。当該経路リストでは、経路が、他の経路との距離の和が大きい順に並べ替えられているので、タイムスロット割当手段１２０は、他の経路との重なりが少ない経路から順に通信管理情報に経路を割り当てることができる。タイムスロット割当手段１２０は、割り当て可能な経路リスト内の経路が全て割り当てられたタイムスロット一覧を出力する。
【０１０２】
なお、ステップＳ２３０の処理は、図２に示すステップＳ１２０の処理と同様である。
タイムスロット一覧を出力した後、タイムスロット一覧生成装置１００は、生成処理を終了する。
【０１０３】
［効果の説明］
次に、本実施形態の効果を説明する。本実施形態の降順距離経路並べ替え手段は、経路リスト内の経路を、他の経路との距離の和が大きい順に並べ替える。よって、タイムスロット割当手段は、並べ替えられた経路リストを入力として、他の経路との重なりが少ない経路から割り当てることができる。他の経路との重なりが少ない経路は同じ通信管理情報に割り当てられやすくなるため、本実施形態のタイムスロット一覧生成装置は、第１の実施形態の効果に加えて、生成されるタイムスロット一覧のタイムスロット数をより削減できるという効果を奏する。
【０１０４】
実施形態３．
［構成の説明］
次に、本発明の第３の実施形態を、図面を参照して説明する。図８は、本発明によるタイムスロット一覧生成装置１００の第３の実施形態の構成例を示すブロック図である。
【０１０５】
図８に示すタイムスロット一覧生成装置１００は、最短疎経路生成手段１１０と、網羅的タイムスロット割当手段１４０とを備える。本実施形態のタイムスロット一覧生成装置１００は、図１に示すタイムスロット一覧生成装置１００と異なり、タイムスロット割当手段１２０の代わりに網羅的タイムスロット割当手段１４０を備える。
【０１０６】
網羅的タイムスロット割当手段１４０は、タイムスロット割当手段１２０の機能を有する。また、網羅的タイムスロット割当手段１４０は、生成される可能性がある全てのタイムスロット一覧の中で、タイムスロット数が最小のタイムスロット一覧を決定する機能も有する。
【０１０７】
［動作の説明］
以下、本実施形態のタイムスロット一覧生成装置１００の動作を図９を参照して説明する。図９は、第３の実施形態のタイムスロット一覧生成装置１００による生成処理の動作を示すフローチャートである。
【０１０８】
最短疎経路生成手段１１０は、端点対リストとネットワークトポロジ情報とを入力とする。次いで、最短疎経路生成手段１１０は、端点対リスト内の端点対情報ごとに、端点同士を結ぶ最短経路であって、他の経路と同時に同じリンクをできるだけ経由しない経路を生成する。
【０１０９】
最短疎経路生成手段１１０は、生成された経路で構成された経路リストを出力する（ステップＳ３１０）。なお、ステップＳ３１０の処理は、図２に示すステップＳ１１０の処理と同様である。
【０１１０】
次いで、網羅的タイムスロット割当手段１４０は、経路リスト内の経路を基に作成される可能性がある全てのタイムスロット一覧のタイムスロット数をそれぞれ算出し、タイムスロット数が最小のタイムスロット一覧を決定する（ステップＳ３２０）。
【０１１１】
次いで、網羅的タイムスロット割当手段１４０は、決定されたタイムスロット一覧を出力する。タイムスロット一覧を出力した後、タイムスロット一覧生成装置１００は、生成処理を終了する。
【０１１２】
次に、本実施形態の網羅的タイムスロット割当手段１４０の動作を図１０を参照して説明する。図１０は、網羅的タイムスロット割当手段１４０によるタイムスロット一覧生成処理の動作を示すフローチャートである。すなわち、図１０に示すステップＳ３２１〜ステップＳ３２９の処理は、図９に示すステップＳ３２０の処理に相当する。
【０１１３】
網羅的タイムスロット割当手段１４０には、経路リストが入力される。網羅的タイムスロット割当手段１４０は、経路リスト内の経路を並べ替えることによって、経路の順列の全パターンを生成する（ステップＳ３２１）。
【０１１４】
網羅的タイムスロット割当手段１４０は、経路の順列の全パターンを含む順列リストを生成する。次いで、網羅的タイムスロット割当手段１４０は、暫定最小タイムスロット数および暫定タイムスロット一覧を初期化する（ステップＳ３２２）。初期化した後、網羅的タイムスロット割当手段１４０は、生成ループに入る（ステップＳ３２３）。
【０１１５】
次いで、網羅的タイムスロット割当手段１４０は、順列リストから順列を１つ取り出す。網羅的タイムスロット割当手段１４０は、取り出された順列、すなわち並べ替えられた経路リスト内の経路を、同じ時間帯に同じリンクが経由されないように通信管理情報に割り当てる（ステップＳ３２４）。なお、ステップＳ３２４の処理は、図２に示すステップＳ１２０の処理と同様である。
【０１１６】
次いで、網羅的タイムスロット割当手段１４０は、ステップＳ３２４で生成されたタイムスロット一覧のタイムスロット数を算出する（ステップＳ３２５）。網羅的タイムスロット割当手段１４０は、算出されたタイムスロット数が暫定最小タイムスロット数よりも小さいか否かを確認する（ステップＳ３２６）。
【０１１７】
算出されたタイムスロット数が暫定最小タイムスロット数以上である場合（ステップＳ３２７におけるＮｏ）、網羅的タイムスロット割当手段１４０は、再度ステップＳ３２４の処理を行う。
【０１１８】
算出されたタイムスロット数が暫定最小タイムスロット数より小さい場合（ステップＳ３２７におけるＹｅｓ）、網羅的タイムスロット割当手段１４０は、暫定最小タイムスロット数を算出されたタイムスロット数に更新する。また、網羅的タイムスロット割当手段１４０は、暫定タイムスロット一覧をステップＳ３２４で生成されたタイムスロット一覧に更新する（ステップＳ３２８）。更新した後、網羅的タイムスロット割当手段１４０は、再度ステップＳ３２４の処理を行う。
【０１１９】
網羅的タイムスロット割当手段１４０は、順列リストの中で処理されていない経路リストが存在する間、すなわち順列リストが空になるまで、ステップＳ３２４〜ステップＳ３２８の処理を繰り返し行う。順列リスト内の全ての経路リストが処理されたとき、網羅的タイムスロット割当手段１４０は、生成ループを抜け（ステップＳ３２９）、タイムスロット一覧生成処理を終了する。
【０１２０】
なお、網羅的タイムスロット割当手段１４０は、図１０に示すような暫定最小タイムスロット数を用いる方法以外の方法で、タイムスロット数が最小のタイムスロット一覧を決定してもよい。
【０１２１】
［効果の説明］
次に、本実施形態の効果を説明する。本実施形態の網羅的タイムスロット割当手段は、経路リスト内の経路を基に生成される可能性がある全てのタイムスロット一覧のタイムスロット数を計算する。よって、タイムスロット数が最小のタイムスロット一覧を生成できるため、本実施形態のタイムスロット一覧生成装置は、第１の実施形態および第２の実施形態よりも、与えられた経路リスト内の経路をより適切に通信管理情報に割り当てることができる。
【０１２２】
実施形態４．
以下、本発明の第４の実施形態を、図面を参照して説明する。図１１は、本実施形態の処理対象の通信が実施される範囲のネットワークトポロジの例を示す説明図である。図１１に示すネットワークトポロジは、図２２に示すネットワークトポロジと同一である。本実施形態でも、簡単のため１パケットを１フリットとして扱う。
【０１２３】
図１２は、本実施形態において最短疎経路生成手段１１０に入力される端点対リストの例を示す説明図である。図１２に示す端点対リストは、端点対情報で構成される。端点対情報は、入力端末と、入力ポートと、出力端末と、出力ポートとで構成される。
【０１２４】
入力端末は、通信の始点になる端末を示す。入力ポートは、通信の始点になる入力端末のポートを示す。出力端末は、通信の終点になる端末を示す。出力ポートは、通信の終点になる出力端末のポートを示す。なお、簡単のため、本実施形態では入力ポートおよび出力ポートを考慮しない。
【０１２５】
［動作の説明］
以下、本実施形態のタイムスロット一覧生成装置１００の動作を図２、図７、および図９を参照して説明する。
【０１２６】
最短疎経路生成手段１１０は、図１２に示す端点対リストと、図１１に示すネットワークトポロジの情報とを入力とする。次いで、最短疎経路生成手段１１０は、入力された端点対リストを構成する各端点対情報に基づいて生成された最短経路で構成された経路リストを生成する（ステップＳ１１０、ステップＳ２１０、ステップＳ３１０）。
【０１２７】
図１３は、本実施形態において最短疎経路生成手段１１０が生成する経路リストの例を示す説明図である。経路リストは、経路情報で構成される。経路情報は、経路名と、ｎ番目のリンクとで構成される（ｎは自然数）。各リンクは、経路名に対応する経路が経由するリンクである。また、「ｎ番目のリンク」は、始点から終点にかけてｎ番目に経由されるリンクである。
【０１２８】
具体的には、path1の１番目のリンクである[V(13)->V(3)@d=1]は、「path1の１番目(d=1)のリンクは、端末１３(V(13))とスイッチ３(V(3))の間のリンク」であることを意味する。また、経路情報内の斜線で示された箇所は、該当するリンクが存在しないことを意味する。すなわち、斜線で示された箇所の１つ前のリンクが、最後に経由されるリンクである。なお、図１２に示す端点対情報の並び順と、図１３に示す経路情報の並び順は対応していない。
【０１２９】
第１の実施形態のタイムスロット割当手段１２０は、図１３に示す経路リストを入力とし、経路リスト内の経路が全て割り当てられたタイムスロット一覧を生成する（ステップＳ１２０）。
【０１３０】
図１４は、本実施形態においてタイムスロット割当手段１２０が生成するタイムスロット一覧の例を示す説明図である。また、図１５は、図１４に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【０１３１】
図１４に示すタイムスロット一覧に基づいて実施される通信全体の終了時刻は、図１５に示すタイムチャートを参照すると、×で示されているリンク「スイッチ９→端末１９」を使用する通信の終了時刻であるタイムスロット８に相当する時刻である。すなわち、図１４に示すタイムスロット一覧のタイムスロット数は８である。図２６に示すタイムスロット一覧のタイムスロット数である２３に比べて、図１４に示すタイムスロット一覧のタイムスロット数は８まで削減されている。
【０１３２】
次に、第２の実施形態のタイムスロット一覧生成装置１００の動作を説明する。第２の実施形態の降順距離経路並べ替え手段１３０は、図１３に示す経路リストを入力とし、経路リスト内の経路を他の経路との距離の和が大きい順に並べ替える（ステップＳ２２０）。
【０１３３】
図１６は、本実施形態において降順距離経路並べ替え手段１３０が生成する並べ替えられた経路リストの例を示す説明図である。図１３に示す経路リストと比べると、経路が「path9」、「path8」、「path7」、「path6」、「path5」、「path4」、「path3」、「path2」、「path1」の順に並べ替えられている。
【０１３４】
次いで、第２の実施形態のタイムスロット割当手段１２０は、図１６に示す経路リストを入力とし、経路リスト内の経路が全て割り当てられたタイムスロット一覧を生成する（ステップＳ２３０）。
【０１３５】
図１７は、本実施形態においてタイムスロット割当手段１２０が生成するタイムスロット一覧の他の例を示す説明図である。また、図１８は、図１７に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。
【０１３６】
図１７に示すタイムスロット一覧に基づいて実施される通信全体の終了時刻は、図１８に示すタイムチャートを参照すると、タイムスロット８に相当する時刻である。タイムスロット８に相当する時刻は、図１８に◆で示されているリンク「スイッチ９→端末１９」を使用する通信と、×で示されているリンク「スイッチ７→端末１７」を使用する通信の終了時刻である。
【０１３７】
すなわち、図１７に示すタイムスロット一覧のタイムスロット数は８である。図２６に示すタイムスロット一覧のタイムスロット数である２３に比べて、図１７に示すタイムスロット一覧のタイムスロット数は８まで削減されている。
【０１３８】
次に、第３の実施形態のタイムスロット一覧生成装置１００の動作を説明する。第３の実施形態の網羅的タイムスロット割当手段１４０は、図１３に示す経路リストを入力とする。網羅的タイムスロット割当手段１４０は、経路リスト内の経路を基に作成される可能性がある全てのタイムスロット一覧のタイムスロット数をそれぞれ算出し、タイムスロット数が最小のタイムスロット一覧を決定する（ステップＳ３２０）。
【０１３９】
図１９は、本実施形態において網羅的タイムスロット割当手段１４０が生成するタイムスロット一覧の例を示す説明図である。また、図２０は、図１９に示すタイムスロット一覧に基づいて実施される通信によるリンクの使用タイミングを示すタイムチャートである。なお、図１９には、タイムスロット０〜２の通信経路のみが例示されている。
【０１４０】
図１９に示すタイムスロット一覧に基づいて実施される通信全体の終了時刻は、図２０に示すタイムチャートを参照すると、タイムスロット７に相当する時刻である。タイムスロット７に相当する時刻は、図２０に◆で示されているリンク「スイッチ９→端末１９」を使用する通信と、×で示されているリンク「スイッチ８→端末１８」を使用する通信の終了時刻である。
【０１４１】
すなわち、図１９に示すタイムスロット一覧のタイムスロット数は７である。図１４および図１７に示すタイムスロット一覧のタイムスロット数である８に比べて、図１９に示すタイムスロット一覧のタイムスロット数は、さらに削減された７である。
【０１４２】
ただし、図１４および図１７に示すタイムスロット一覧の生成に要する時間は０．１秒程度であるが、図１９に示すタイムスロット一覧の生成に要する時間は約７秒である。すなわち、第１の実施形態および第２の実施形態に比べると、第３の実施形態のタイムスロット一覧生成装置１００による生成処理に係る時間は長い。
【０１４３】
また、通信が実施される通信ネットワークの規模が大きくなると、タイムスロット一覧の生成に要する計算時間がさらに増えることが予想される。よって、利用者は、通信が実施される通信ネットワークの規模に応じて利用するタイムスロット一覧生成装置１００の形態を選択することが好ましい。
【０１４４】
なお、各実施形態のタイムスロット一覧生成装置１００は、例えば、記憶媒体に格納されているプログラムに従って処理を実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）によって実現される。すなわち最短疎経路生成手段１１０、タイムスロット割当手段１２０、降順距離経路並べ替え手段１３０、および網羅的タイムスロット割当手段１４０は、例えば、プログラム制御に従って処理を実行するＣＰＵによって実現される。
【０１４５】
また、タイムスロット一覧生成装置１００における各部は、ハードウェア回路によって実現されてもよい。
【０１４６】
次に、本発明の概要を説明する。図２１は、本発明による通信管理一覧生成装置の概要を示すブロック図である。本発明による通信管理一覧生成装置２０は、所定の時刻に対応する時刻情報と所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成する通信管理一覧生成装置であって、通信情報に通信処理の情報を追加可能であるか否かに関して時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定手段２１（例えば、タイムスロット割当手段１２０）と、追加可能であると判定手段２１が判定した段階で判定された通信管理情報の通信情報に通信処理の情報を追加する追加手段２２（例えば、タイムスロット割当手段１２０）とを備える。
【０１４７】
そのような構成により、通信管理一覧生成装置は、より短い時間間隔でブロッキングが生じない通信が実施されるタイムスロット一覧を生成できる。
【０１４８】
また、判定手段２１は、複数の通信処理に対して使用する最短経路と他の通信処理で使用される最短経路との距離の和が大きい順に通信処理の情報を追加可能であるか否かを判定してもよい。
【０１４９】
そのような構成により、通信管理一覧生成装置は、生成されるタイムスロット一覧のタイムスロット数をより削減できる。
【０１５０】
また、通信管理一覧生成装置２０は、追加対象の通信処理の情報が全て追加されることによって生成された通信管理一覧を用いて実施される通信処理全体の所要時間を計測する計測手段（例えば、網羅的タイムスロット割当手段１４０）を備え、計測手段は、追加対象の通信処理の情報を基に生成される通信管理一覧の全てのパターンのうち所要時間が最小の通信管理一覧を出力してもよい。
【０１５１】
そのような構成により、通信管理一覧生成装置は、経路リスト内の経路をより適切に通信管理情報に割り当てることができる。
【０１５２】
また、通信処理の情報は、通信処理で使用される最短経路の全てのパターンのうち他の通信処理で使用される最短経路との距離の和が最大である最短経路の情報でもよい。
【０１５３】
そのような構成により、通信管理一覧生成装置は、経路リスト内の経路をより容易に通信管理情報に割り当てることができる。
【０１５４】
また、通信管理一覧生成装置２０は、ネットワークトポロジ情報と端点対リストとを入力とし、通信処理の情報として最短経路の情報を生成する最短疎経路生成手段（例えば、最短疎経路生成手段１１０）を備えてもよい。また、最短疎経路生成手段は、経由するリンク同士が重ならない最短経路の集合である経路リストを生成してもよい。
【０１５５】
そのような構成により、通信管理一覧生成装置は、できる限り同時に同一リンクを共有しない通信経路の情報を生成できる。
【０１５６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１５７】
この出願は、２０１５年１０月１３日に出願された日本出願特願２０１５−２０２２７６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１５８】
本発明は、信頼性の高い仮想通信網を構築する際、設計時に経路問題や帯域問題を検出する設計支援の用途に好適に適用可能である。また、本発明は、信頼性の高い仮想通信網を構築する際、誤設定により発生した経路問題や帯域問題を検出する設定検証の用途にも好適に適用可能である。
【符号の説明】
【０１５９】
１〜９  スイッチ
１１〜１３、１７〜１９  端末
２０  通信管理一覧生成装置
２１  判定手段
２２  追加手段
１００、９００  タイムスロット一覧生成装置
１１０  最短疎経路生成手段
１２０  タイムスロット割当手段
１３０  降順距離経路並べ替え手段
１４０  網羅的タイムスロット割当手段
９１０  最短経路生成手段
９２０  セグメント分割手段
９３０  セグメント用タイムスロット割当手段
【図１】
2017064833.tif 000003
【図２】
2017064833.tif 000004
【図３】
2017064833.tif 000005
【図４】
2017064833.tif 000006
【図５】
2017064833.tif 000007
【図６】
2017064833.tif 000008
【図７】
2017064833.tif 000009
【図８】
2017064833.tif 000010
【図９】
2017064833.tif 000011
【図１０】
2017064833.tif 000012
【図１１】
2017064833.tif 000013
【図１２】
2017064833.tif 000014
【図１３】
2017064833.tif 000015
【図１４】
2017064833.tif 000016
【図１５】
2017064833.tif 000017
【図１６】
2017064833.tif 000018
【図１７】
2017064833.tif 000019
【図１８】
2017064833.tif 000020
【図１９】
2017064833.tif 000021
【図２０】
2017064833.tif 000022
【図２１】
2017064833.tif 000023
【図２２】
2017064833.tif 000024
【図２３】
2017064833.tif 000025
【図２４】
2017064833.tif 000026
【図２５】
2017064833.tif 000027
【図２６】
2017064833.tif 000028
【図２７】
2017064833.tif 000029
【手続補正書】
【提出日】平成30年4月3日(2018.4.3)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
所定の時刻に対応する時刻情報と前記所定の時刻に開始され同時に同一経路を使用しない通信処理を示す通信情報とを含む通信管理情報で構成される通信管理一覧を生成するコンピュータにおいて実行される通信管理一覧生成プログラムであって、
前記コンピュータに、
通信情報に通信処理の情報を追加可能であるか否かに関して前記時刻情報に対応する時刻の早い順に各通信管理情報を判定する判定処理、および
前記判定処理で追加可能であると判定された段階で判定された通信管理情報の通信情報に前記通信処理の情報を追加する追加処理
を実行させるための通信管理一覧生成プログラム。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
コンピュータに、
複数の通信処理に対して使用する最短経路と他の通信処理で使用される最短経路との距離の和が大きい順に通信処理の情報を追加可能であるか否かを判定する判定処理を実行させる
請求項８記載の通信管理一覧生成プログラム。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
コンピュータに、
追加対象の通信処理の情報が全て追加されることによって生成された通信管理一覧を用いて実施される通信処理全体の所要時間を計測する計測処理、および
前記追加対象の通信処理の情報を基に生成される通信管理一覧の全てのパターンのうち前記所要時間が最小の通信管理一覧を出力する出力処理を実行させる
請求項８または請求項９記載の通信管理一覧生成プログラム。
【国際調査報告】
2017064833.tif 000030
2017064833.tif 000031