経路計算方法及び装置及びプログラム
【課題】 隣接行列の演算のメモリ量を抑えつつ、方向性の制約があるネットワークの経路探索を可能にする。
【解決手段】 本発明は、無向グラフの経路探索と方向制約のチェックを組み合わせたものであり、経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得し、隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見し、方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する。
【解決手段】 本発明は、無向グラフの経路探索と方向制約のチェックを組み合わせたものであり、経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得し、隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見し、方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計算方法及び装置及びプログラムに係り、特に、ネットワークにおける経路を探索するための経路計算方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
経路を計算する方法として、ダイクストラ法、ベルマン・フォード法や、特許文献1に示される方法等がある。
【０００３】
上記のダイクストラ法、ベルマン・フォード法や、特許文献1に示される方法は、始点から終点までの経路探索によって求まる経路候補と、終点から始点までの経路探索によって求まる経路候補とが一致する、という前提で経路を探索している。
【０００４】
また隣接行列や、接続行列では無向グラフを利用することにより、有向グラフよりも行列の表現に必要なデータを削減でき、計算に必要とされるメモリサイズが小さくなる。
【０００５】
例えば、有向グラフと無向グラフの違いは以下のようになる。1〜N個のノードで構成されるネットワークトポロジを隣接行列で表す場合、隣接行列はN×Nの行列になる。この際、たとえばノード"ｉ"から隣接のノード"ｊ"に経路探索を進める場合、データベース上の隣接行列の行"ｉ"と列"ｊ"の値を参照する。このとき、例えば値がゼロであれば接続しておらず、値が"１"であれば接続していることになる。無向グラフの場合、行"ｉ"と列"ｊ"の行列成分と、行"ｊ"と列"ｉ"の行列成分が同じになる。それゆえ、隣接行列の大きさはN×Nであっても、実際にデータベースに記憶しておくべき隣接行列の大きさはN×N÷2、すなわち本来の隣接行列の半分のサイズに相当する分だけを記憶すればよい。一方、有向グラフの場合、行"ｉ"と列"ｊ"の行列成分と行"ｊ"と列"ｉ"の行列成分が異なる。それゆえ、経路計算を実行する計算機のメモリ上に同隣接行列を記憶する場合、有向グラフを記憶するために必要なメモリサイズは、N×Nの隣接行列そのものを記憶する分だけ必要となる。すなわちあるネットワークトポロジを仮定すると、そのトポロジに沿った有向グラフを記憶するためのデータベースのメモリサイズは、同様の無向グラフを記憶するためのデータベースのメモリサイズの２倍となる。それゆえ計算機上において、無向グラフは、有向グラフよりも巨大なネットワークを表現でき、無向グラフを利用した経路計算方法は大規模ネットワークの経路探索に向いている。
【０００６】
ネットワークの伝送技術では、イーサネット（登録商標）や、SONET/SDH(Synchronous Optical Network/Synchronous Digital Hierarchy)、OTN(Optical Transport Network)など、双方向で同じ経路となるため、無向グラフでネットワークを十分に表現できている。それゆえ、ネットワークの経路探索には一般的に無向グラフが利用される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2008-301225号公報.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の前提に基づく経路計算方法は、図７のようなReconfigurable Optical Add-Drop Multiplexer （ROADM）などの通信装置がネットワーク内に存在する場合、始点から終点までの経路を正確に探索することはできない。なぜなら、ROADMは、図１８や図１９に示される通り、始点から終点への経路探索によって求まる経路候補と、終点から始点への経路探索によって求まる経路候補とが一致しないためである。図１８及び図１９に基づいてROADMの経路の考え方について説明する。図１８において、インターフェース部内のトランスポンダからROADMスイッチ部に入力された信号は、右方向に出力される。しかしながら、左方向には出力されない。一方、図１９において、ROADMスイッチ部から図１８と同じ上記のトランスポンダに入力された信号は、左方向からROADMスイッチ部に入力されてその後に上記トランスポンダに入力される。しかしながら、右方向からROADMスイッチ部に入力されることはない。すなわち、ROADMという通信装置の内部において、始点から終点への経路探索によって求まる経路候補と、終点から始点への経路探索によって求まる経路候補とは異なる。すなわち、図２０のようにROADMを有するネットワークでは、始点と終点の設定次第で図２１のように実現可能な経路が異なってしまう。
【０００９】
一方、隣接行列は単に物理的な接続のみを表現しており、隣接行列だけでは上記のような方向制約を表現できない。
【００１０】
ダイクストラ法、ベルマン-フォード法、及び特許文献１に示される方法などがROADMを有するネットワークにおいても正確に始点から終点までの経路を求めるためには、経路探索の方向性を管理して方向の制約に合う経路を探索する必要がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、隣接行列の演算のメモリ量を抑えつつ、方向性の制約があるネットワークの経路探索が可能な経路計算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明（請求項１）は、始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算方法であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有する装置において、
経路計算手段が、
経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索ステップと、
隣接行列データベースを参照して、点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索ステップと、
方向制約データベースを参照して、点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約の有無を判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を経路データベースに格納する方向制約チェックステップと、を行う。
【００１３】
また、本発明（請求項２）は、始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算装置であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有し、
経路計算手段は、
経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索手段と、
隣接行列データベースを参照して、点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索手段と、
方向制約データベースを参照して、点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約の有無を判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を経路データベースに格納する方向制約チェック手段と、
を有する。
【００１４】
また、本発明（請求項３）は、請求項２に記載経路計算装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【００１５】
これにより、ある点"Ｂ"において、点"Ｂ"に入力してきた方向、ならびに入力方向に基づいて制限される点"Ｂ"からの出力方向を管理することができる。
【発明の効果】
【００１６】
上記のように本発明は、一部方向制約のあるネットワークでの経路探索において、無向グラフに対応する隣接行列をベースに探索し、方向制約のチェックを付加したことにより、無向グラフをベースとしているため、隣接行列の演算のメモリ量を抑えたまま、方向性のあるネットワークの経路探索が可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施の形態における経路計算装置の構成図である。
【図２】ネットワークトポロジの例とその隣接行列の例である。
【図３】本発明の第１の実施の形態における経路データベースのイメージ例と記憶される経路情報の例である。
【図４】本発明の第１の実施の形態における方向制約データベースのデータ構成例である。
【図５】本発明の第１の実施の形態における方向制約データベースのデータ例である。
【図６】本発明の第１の実施の形態における経路計算装置の経路計算処理のフローチャートである。
【図７】特許文献１の図３に記載された経路探索装置（ＮＲＭ）の構成図である。
【図８】本発明の第２の実施の形態における経路探索装置（ＮＲＭ）の拡張例である。
【図９】特許文献１の図５に記載されたネットワーク構成リストの一例である。
【図１０】本発明の第２の実施の形態におけるネットワーク構成リストの拡張例である。
【図１１】特許文献１の図８に記載された利用可能資源リストの例である。
【図１２】本発明の第２の実施の形態における利用可能資源リストの拡張例である。
【図１３】特許文献１の図１０に記載された隣接行列の例である。
【図１４】本発明の第２の実施の形態における隣接行列の拡張例である。
【図１５】特許文献１の図１３に記載された経路探索方法である。
【図１６】本発明の第２の実施の形態における経路探索方法の拡張例である。
【図１７】方向制約付き既存装置ならびその搭載スイッチの例である。
【図１８】既存スイッチの方向制約の説明（アド（信号挿入時））である。
【図１９】既存スイッチの方向制約の説明（ドロップ（信号分岐時））である。
【図２０】トポロジの例である。
【図２１】トポロジ上での実現可能な経路の例である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
［第１の実施の形態］
本発明は、ダイクストラ法、ベルマン-フォード法、及び、特許文献１に示す方法などに、経路探索の方向性を管理する機能を付与し、方向の制約に合う経路を探索するものである。
【００２０】
図１は、本発明の第１の実施の形態における経路計算装置の構成を示す。
【００２１】
経路計算装置１０は、経路計算部１１、隣接行列データベース１２、経路データベース１３、方向制約データベース１４を有する。
【００２２】
隣接行列データベース１２は、図２に示す隣接行列が格納される。
【００２３】
経路データベース１３は、基点枝と評価枝の接続関係が格納される。図３は経路データベース１３の例、並びに、経路データベース１３上に記憶される経路の例である。始点が「点１」の例である。経路は行毎に記載され、始点から求められた枝が列記される。各行の右端にある枝は基本的に未探索の枝であり、今後の基点枝の候補である。但し、探索済の枝である場合もある。
【００２４】
方向制約データベース１４は、図４に示すように点の識別情報毎に入力点と出力点の組からなり、出力点の項目は１つの以上の出力先候補が格納される。具体的には図５に示すようなデータが格納される。方向制約データベース１４の見方について、識別情報「４」の点を例として説明する。「点５」から「点４」に入力した場合、「点４」は「点３」もしくは点６と接続できる。また、「点６」から「点４」に入力した場合、「点４」は「点３」と接続できる。
【００２５】
経路計算部１１は、隣接行列データベース１２を参照し、経路データベース１３ネットワークを隣接行列、接続行列、もしくはそれと同等の行列によって表現し、且つ前記行列に基づいてある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算アルゴリズムを有する。
【００２６】
図６は、本発明の第１の実施の形態における経路計算装置の経路計算処理のフローチャートである。
【００２７】
ステップ１０１） まず、経路計算部１１は経路データベース１３を参照し、これまでに探索された枝（探索済の枝）に接続しており、尚且つ未探索の枝のひとつを選択する。これを「基点枝」の確定とする。開始当初、これまでに探索された枝とは始点だけであり、始点を基点枝として探索を開始する。この時点において、基点枝は探索済みの枝として経路データベース１３で管理される。
【００２８】
但し、基点枝となる未探索の枝がひとつもない場合、探索失敗である。すなわち、始点から終点までを結ぶ経路は存在しないことになる。
【００２９】
ステップ１０２） 次に、ステップ１０１において基点枝がある場合は、当該基点枝をメモリ（図示せず）に格納し、経路計算部１１は隣接行列データベース１２を参照して基点枝からみた未探索の枝の探索を行う。基点枝からみた未探索の枝がない場合、ステップ１０１に戻って基点枝を探索する。
【００３０】
ステップ１０３） 一方、未探索の枝を発見した場合（評価枝の確定）、その枝をメモリ（図示せず）に評価枝として格納する。経路計算部１１は、方向制約チェック処理として、図４の方向制約データベース１４を参照し、メモリ（図示せず）内の基点枝と評価枝の関係を評価する。方向制約の観点から基点枝と評価枝が接続できない場合、経路計算部１１は、ステップ１０２に移行し、再び隣接行列データベース１２を参照し、基点枝からみた未探索の枝を探索する。
【００３１】
ステップ１０４） 経路計算部１１は、上記のステップ１０３において、基点枝から評価枝への方向制約の問題がない場合、次に評価枝が終点であるか否かを評価する。評価枝が終点ではない場合はステップ１０５に移行し、評価枝が終点である場合はステップ１０６に移行する。
【００３２】
ステップ１０５） 経路計算部１１は、基点枝と評価枝の接続関係を経路データベース１３に記憶する。
【００３３】
ステップ１０６） ステップ１０４において、評価枝が終点である場合、経路計算部１１は基点枝と評価枝の接続関係を経路データベース１３に記憶すると共に、その時点で始点から終点までの経路が求まる。
【００３４】
以上により、方向制約のあるネットワークにおいて始点から終点までの経路を求めることができる。
【００３５】
例えば、始点「１」かつ終点「６」の経路を探索する場合、方向制約並びに隣接行列の観点から１→５→４→６の経路以外に経路は存在しない。
【００３６】
一方、方向制約を考慮することなく隣接行列のみに基づいて経路を計算する場合、図２の隣接行列ＤＢ１２のトポロジの例から経路候補は以下の４つとなる。
【００３７】
・経路候補の例
１→５→４→６
１→２→５→４→６
１→２→３→４→６
１→５→２→３→４→６
以上のとおり、方向制約を考慮しない場合、本来は存在しないはずの経路が算出される可能性がある。
【００３８】
［第２の実施の形態］
本実施の形態は、特許文献1及び第１の実施の形態をベースとした方向制約チェック付き経路計算方法である。
【００３９】
図７は、特許文献１の図３に記載された経路探索装置（ＮＲＭ）の構成を示し、一方、図８は、本発明の第２の実施の形態における経路探索装置（ＮＲＭ）の拡張例を示す。図８に示すＮＲＭは、図７の構成に、前述の図６のステップ１０３に相当する機能を有する方向制約チェック部２１０を追加したものである。
【００４０】
図９は、特許文献１の図５のネットワーク構成リストの例を示している。一方、図１０は、本発明の第２の実施の形態におけるネットワーク構成リストの拡張例であり、図９のネットワーク構成リストに、第１の実施の形態の図４の方向制約データベース１３の部分を追加したものである。
【００４１】
図１１は、特許文献１の図８の利用可能資源リストの例を示している。一方、図１２は、本発明の第２の実施の形態における利用可能資源リストの例であり、図１１の利用可能資源リストに図１０に基づく方向制約データベース１３の部分を追加したものである。
【００４２】
図１３は、特許文献１の図１１の隣接行列の例を示している。一方、図１４は、本発明の第２の実施の形態における隣接行列の拡張例であり、図１３の隣接行列に図１２に基づく方向制約データベース１３の部分を追加したものである。
【００４３】
図１５は、特許文献１の図１４の経路探索方法の例を示している。一方、図１６は、本発明の第２の実施の形態における経路探索方法の拡張例であり、図１５の経路探索方法のフローに図６のステップ１０３の方向制約チェックステップ（ステップ３００）を追加したものである。
【００４４】
以上の追加を行うことにより、特許文献１の経路探索方法に方向制約チェックステップを追加することができる。
【００４５】
上記の第１の実施の形態における図１及び図８に示す構成要素の動作をプログラムとして構築し、経路計算装置、経路探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４６】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００４７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４８】
１０ 経路計算装置
１１ 経路計算部
１２ 隣接行列データベース
１３ 経路データベース
１４ 方向制約デーベース
１００ 経路探索装置（ＮＲＭ）
１１０ コア部
１２０ 経路探索部
１２５ 通信制御部
１３０ 接続行列作成部
１４０ 経路チェック部
１５０ コストチェック部
１６０ リミテーションチェック部
１７０ データ管理ＤＢ
１７５ 通信路制御ＤＢ
１８０ 算出経路ＤＢ
１９０ 確定経路ＤＢ
２１０ 方向制約チェック部
２２０ 方向制約ＤＢ
【技術分野】
【０００１】
本発明は、経路計算方法及び装置及びプログラムに係り、特に、ネットワークにおける経路を探索するための経路計算方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
経路を計算する方法として、ダイクストラ法、ベルマン・フォード法や、特許文献1に示される方法等がある。
【０００３】
上記のダイクストラ法、ベルマン・フォード法や、特許文献1に示される方法は、始点から終点までの経路探索によって求まる経路候補と、終点から始点までの経路探索によって求まる経路候補とが一致する、という前提で経路を探索している。
【０００４】
また隣接行列や、接続行列では無向グラフを利用することにより、有向グラフよりも行列の表現に必要なデータを削減でき、計算に必要とされるメモリサイズが小さくなる。
【０００５】
例えば、有向グラフと無向グラフの違いは以下のようになる。1〜N個のノードで構成されるネットワークトポロジを隣接行列で表す場合、隣接行列はN×Nの行列になる。この際、たとえばノード"ｉ"から隣接のノード"ｊ"に経路探索を進める場合、データベース上の隣接行列の行"ｉ"と列"ｊ"の値を参照する。このとき、例えば値がゼロであれば接続しておらず、値が"１"であれば接続していることになる。無向グラフの場合、行"ｉ"と列"ｊ"の行列成分と、行"ｊ"と列"ｉ"の行列成分が同じになる。それゆえ、隣接行列の大きさはN×Nであっても、実際にデータベースに記憶しておくべき隣接行列の大きさはN×N÷2、すなわち本来の隣接行列の半分のサイズに相当する分だけを記憶すればよい。一方、有向グラフの場合、行"ｉ"と列"ｊ"の行列成分と行"ｊ"と列"ｉ"の行列成分が異なる。それゆえ、経路計算を実行する計算機のメモリ上に同隣接行列を記憶する場合、有向グラフを記憶するために必要なメモリサイズは、N×Nの隣接行列そのものを記憶する分だけ必要となる。すなわちあるネットワークトポロジを仮定すると、そのトポロジに沿った有向グラフを記憶するためのデータベースのメモリサイズは、同様の無向グラフを記憶するためのデータベースのメモリサイズの２倍となる。それゆえ計算機上において、無向グラフは、有向グラフよりも巨大なネットワークを表現でき、無向グラフを利用した経路計算方法は大規模ネットワークの経路探索に向いている。
【０００６】
ネットワークの伝送技術では、イーサネット（登録商標）や、SONET/SDH(Synchronous Optical Network/Synchronous Digital Hierarchy)、OTN(Optical Transport Network)など、双方向で同じ経路となるため、無向グラフでネットワークを十分に表現できている。それゆえ、ネットワークの経路探索には一般的に無向グラフが利用される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2008-301225号公報.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の前提に基づく経路計算方法は、図７のようなReconfigurable Optical Add-Drop Multiplexer （ROADM）などの通信装置がネットワーク内に存在する場合、始点から終点までの経路を正確に探索することはできない。なぜなら、ROADMは、図１８や図１９に示される通り、始点から終点への経路探索によって求まる経路候補と、終点から始点への経路探索によって求まる経路候補とが一致しないためである。図１８及び図１９に基づいてROADMの経路の考え方について説明する。図１８において、インターフェース部内のトランスポンダからROADMスイッチ部に入力された信号は、右方向に出力される。しかしながら、左方向には出力されない。一方、図１９において、ROADMスイッチ部から図１８と同じ上記のトランスポンダに入力された信号は、左方向からROADMスイッチ部に入力されてその後に上記トランスポンダに入力される。しかしながら、右方向からROADMスイッチ部に入力されることはない。すなわち、ROADMという通信装置の内部において、始点から終点への経路探索によって求まる経路候補と、終点から始点への経路探索によって求まる経路候補とは異なる。すなわち、図２０のようにROADMを有するネットワークでは、始点と終点の設定次第で図２１のように実現可能な経路が異なってしまう。
【０００９】
一方、隣接行列は単に物理的な接続のみを表現しており、隣接行列だけでは上記のような方向制約を表現できない。
【００１０】
ダイクストラ法、ベルマン-フォード法、及び特許文献１に示される方法などがROADMを有するネットワークにおいても正確に始点から終点までの経路を求めるためには、経路探索の方向性を管理して方向の制約に合う経路を探索する必要がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、隣接行列の演算のメモリ量を抑えつつ、方向性の制約があるネットワークの経路探索が可能な経路計算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明（請求項１）は、始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算方法であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有する装置において、
経路計算手段が、
経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索ステップと、
隣接行列データベースを参照して、点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索ステップと、
方向制約データベースを参照して、点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約の有無を判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を経路データベースに格納する方向制約チェックステップと、を行う。
【００１３】
また、本発明（請求項２）は、始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算装置であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有し、
経路計算手段は、
経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索手段と、
隣接行列データベースを参照して、点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索手段と、
方向制約データベースを参照して、点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約の有無を判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を経路データベースに格納する方向制約チェック手段と、
を有する。
【００１４】
また、本発明（請求項３）は、請求項２に記載経路計算装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【００１５】
これにより、ある点"Ｂ"において、点"Ｂ"に入力してきた方向、ならびに入力方向に基づいて制限される点"Ｂ"からの出力方向を管理することができる。
【発明の効果】
【００１６】
上記のように本発明は、一部方向制約のあるネットワークでの経路探索において、無向グラフに対応する隣接行列をベースに探索し、方向制約のチェックを付加したことにより、無向グラフをベースとしているため、隣接行列の演算のメモリ量を抑えたまま、方向性のあるネットワークの経路探索が可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施の形態における経路計算装置の構成図である。
【図２】ネットワークトポロジの例とその隣接行列の例である。
【図３】本発明の第１の実施の形態における経路データベースのイメージ例と記憶される経路情報の例である。
【図４】本発明の第１の実施の形態における方向制約データベースのデータ構成例である。
【図５】本発明の第１の実施の形態における方向制約データベースのデータ例である。
【図６】本発明の第１の実施の形態における経路計算装置の経路計算処理のフローチャートである。
【図７】特許文献１の図３に記載された経路探索装置（ＮＲＭ）の構成図である。
【図８】本発明の第２の実施の形態における経路探索装置（ＮＲＭ）の拡張例である。
【図９】特許文献１の図５に記載されたネットワーク構成リストの一例である。
【図１０】本発明の第２の実施の形態におけるネットワーク構成リストの拡張例である。
【図１１】特許文献１の図８に記載された利用可能資源リストの例である。
【図１２】本発明の第２の実施の形態における利用可能資源リストの拡張例である。
【図１３】特許文献１の図１０に記載された隣接行列の例である。
【図１４】本発明の第２の実施の形態における隣接行列の拡張例である。
【図１５】特許文献１の図１３に記載された経路探索方法である。
【図１６】本発明の第２の実施の形態における経路探索方法の拡張例である。
【図１７】方向制約付き既存装置ならびその搭載スイッチの例である。
【図１８】既存スイッチの方向制約の説明（アド（信号挿入時））である。
【図１９】既存スイッチの方向制約の説明（ドロップ（信号分岐時））である。
【図２０】トポロジの例である。
【図２１】トポロジ上での実現可能な経路の例である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
［第１の実施の形態］
本発明は、ダイクストラ法、ベルマン-フォード法、及び、特許文献１に示す方法などに、経路探索の方向性を管理する機能を付与し、方向の制約に合う経路を探索するものである。
【００２０】
図１は、本発明の第１の実施の形態における経路計算装置の構成を示す。
【００２１】
経路計算装置１０は、経路計算部１１、隣接行列データベース１２、経路データベース１３、方向制約データベース１４を有する。
【００２２】
隣接行列データベース１２は、図２に示す隣接行列が格納される。
【００２３】
経路データベース１３は、基点枝と評価枝の接続関係が格納される。図３は経路データベース１３の例、並びに、経路データベース１３上に記憶される経路の例である。始点が「点１」の例である。経路は行毎に記載され、始点から求められた枝が列記される。各行の右端にある枝は基本的に未探索の枝であり、今後の基点枝の候補である。但し、探索済の枝である場合もある。
【００２４】
方向制約データベース１４は、図４に示すように点の識別情報毎に入力点と出力点の組からなり、出力点の項目は１つの以上の出力先候補が格納される。具体的には図５に示すようなデータが格納される。方向制約データベース１４の見方について、識別情報「４」の点を例として説明する。「点５」から「点４」に入力した場合、「点４」は「点３」もしくは点６と接続できる。また、「点６」から「点４」に入力した場合、「点４」は「点３」と接続できる。
【００２５】
経路計算部１１は、隣接行列データベース１２を参照し、経路データベース１３ネットワークを隣接行列、接続行列、もしくはそれと同等の行列によって表現し、且つ前記行列に基づいてある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算アルゴリズムを有する。
【００２６】
図６は、本発明の第１の実施の形態における経路計算装置の経路計算処理のフローチャートである。
【００２７】
ステップ１０１） まず、経路計算部１１は経路データベース１３を参照し、これまでに探索された枝（探索済の枝）に接続しており、尚且つ未探索の枝のひとつを選択する。これを「基点枝」の確定とする。開始当初、これまでに探索された枝とは始点だけであり、始点を基点枝として探索を開始する。この時点において、基点枝は探索済みの枝として経路データベース１３で管理される。
【００２８】
但し、基点枝となる未探索の枝がひとつもない場合、探索失敗である。すなわち、始点から終点までを結ぶ経路は存在しないことになる。
【００２９】
ステップ１０２） 次に、ステップ１０１において基点枝がある場合は、当該基点枝をメモリ（図示せず）に格納し、経路計算部１１は隣接行列データベース１２を参照して基点枝からみた未探索の枝の探索を行う。基点枝からみた未探索の枝がない場合、ステップ１０１に戻って基点枝を探索する。
【００３０】
ステップ１０３） 一方、未探索の枝を発見した場合（評価枝の確定）、その枝をメモリ（図示せず）に評価枝として格納する。経路計算部１１は、方向制約チェック処理として、図４の方向制約データベース１４を参照し、メモリ（図示せず）内の基点枝と評価枝の関係を評価する。方向制約の観点から基点枝と評価枝が接続できない場合、経路計算部１１は、ステップ１０２に移行し、再び隣接行列データベース１２を参照し、基点枝からみた未探索の枝を探索する。
【００３１】
ステップ１０４） 経路計算部１１は、上記のステップ１０３において、基点枝から評価枝への方向制約の問題がない場合、次に評価枝が終点であるか否かを評価する。評価枝が終点ではない場合はステップ１０５に移行し、評価枝が終点である場合はステップ１０６に移行する。
【００３２】
ステップ１０５） 経路計算部１１は、基点枝と評価枝の接続関係を経路データベース１３に記憶する。
【００３３】
ステップ１０６） ステップ１０４において、評価枝が終点である場合、経路計算部１１は基点枝と評価枝の接続関係を経路データベース１３に記憶すると共に、その時点で始点から終点までの経路が求まる。
【００３４】
以上により、方向制約のあるネットワークにおいて始点から終点までの経路を求めることができる。
【００３５】
例えば、始点「１」かつ終点「６」の経路を探索する場合、方向制約並びに隣接行列の観点から１→５→４→６の経路以外に経路は存在しない。
【００３６】
一方、方向制約を考慮することなく隣接行列のみに基づいて経路を計算する場合、図２の隣接行列ＤＢ１２のトポロジの例から経路候補は以下の４つとなる。
【００３７】
・経路候補の例
１→５→４→６
１→２→５→４→６
１→２→３→４→６
１→５→２→３→４→６
以上のとおり、方向制約を考慮しない場合、本来は存在しないはずの経路が算出される可能性がある。
【００３８】
［第２の実施の形態］
本実施の形態は、特許文献1及び第１の実施の形態をベースとした方向制約チェック付き経路計算方法である。
【００３９】
図７は、特許文献１の図３に記載された経路探索装置（ＮＲＭ）の構成を示し、一方、図８は、本発明の第２の実施の形態における経路探索装置（ＮＲＭ）の拡張例を示す。図８に示すＮＲＭは、図７の構成に、前述の図６のステップ１０３に相当する機能を有する方向制約チェック部２１０を追加したものである。
【００４０】
図９は、特許文献１の図５のネットワーク構成リストの例を示している。一方、図１０は、本発明の第２の実施の形態におけるネットワーク構成リストの拡張例であり、図９のネットワーク構成リストに、第１の実施の形態の図４の方向制約データベース１３の部分を追加したものである。
【００４１】
図１１は、特許文献１の図８の利用可能資源リストの例を示している。一方、図１２は、本発明の第２の実施の形態における利用可能資源リストの例であり、図１１の利用可能資源リストに図１０に基づく方向制約データベース１３の部分を追加したものである。
【００４２】
図１３は、特許文献１の図１１の隣接行列の例を示している。一方、図１４は、本発明の第２の実施の形態における隣接行列の拡張例であり、図１３の隣接行列に図１２に基づく方向制約データベース１３の部分を追加したものである。
【００４３】
図１５は、特許文献１の図１４の経路探索方法の例を示している。一方、図１６は、本発明の第２の実施の形態における経路探索方法の拡張例であり、図１５の経路探索方法のフローに図６のステップ１０３の方向制約チェックステップ（ステップ３００）を追加したものである。
【００４４】
以上の追加を行うことにより、特許文献１の経路探索方法に方向制約チェックステップを追加することができる。
【００４５】
上記の第１の実施の形態における図１及び図８に示す構成要素の動作をプログラムとして構築し、経路計算装置、経路探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４６】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００４７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４８】
１０ 経路計算装置
１１ 経路計算部
１２ 隣接行列データベース
１３ 経路データベース
１４ 方向制約デーベース
１００ 経路探索装置（ＮＲＭ）
１１０ コア部
１２０ 経路探索部
１２５ 通信制御部
１３０ 接続行列作成部
１４０ 経路チェック部
１５０ コストチェック部
１６０ リミテーションチェック部
１７０ データ管理ＤＢ
１７５ 通信路制御ＤＢ
１８０ 算出経路ＤＢ
１９０ 確定経路ＤＢ
２１０ 方向制約チェック部
２２０ 方向制約ＤＢ
【特許請求の範囲】
【請求項１】
始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算方法であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有する装置において、
前記経路計算手段が、
前記経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索ステップと、
前記隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索ステップと、
前記方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する方向制約チェックステップと、
を行うことを特徴とする経路計算方法。
【請求項２】
始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算装置であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有し、
前記経路計算手段は、
前記経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索手段と、
前記隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索手段と、
前記方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する方向制約チェック手段と、
を有することを特徴とする経路計算装置。
【請求項３】
請求項２に記載経路計算装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【請求項１】
始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算方法であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有する装置において、
前記経路計算手段が、
前記経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索ステップと、
前記隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索ステップと、
前記方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する方向制約チェックステップと、
を行うことを特徴とする経路計算方法。
【請求項２】
始点から終点までの経路上にある点"Ａ"から隣接する点を探索して点"Ｂ"を発見し、その後に該点"Ｂ"と隣接する点を探索する際、該点"Ｂ"の隣接点が点"Ａ"によって制限されるネットワークにおいて、ある点（始点）からある点（終点）までの０本以上の経路を探索する経路計算装置であって
基点枝と評価枝の接続関係を格納した経路データベースと、
ネットワークを隣接行列もしくはそれと同等の無向グラフの行列によって表現し、かつ、該行列を記憶した隣接行列データベースと、
経路の方向制約の条件を記録した方向制約データベースと、
経路計算手段と、
を有し、
前記経路計算手段は、
前記経路データベースを参照して始点から終点までの経路上の探索済みの枝に接続されている点"Ａ"（基点枝）を取得する基点枝探索手段と、
前記隣接行列データベースを参照して、前記点"Ａ"（基点枝）に隣接する点を探索して点"Ｂ"（評価枝）を発見する隣接点探索手段と、
前記方向制約データベースを参照して、前記点"Ａ"及び該点"Ａ"に基づく点"Ｂ"の隣接点候補に方向制約があるかないかを判定し、ない場合は、該点"Ａ"（基点枝）と該点"Ｂ"（評価枝）の接続関係を前記経路データベースに格納する方向制約チェック手段と、
を有することを特徴とする経路計算装置。
【請求項３】
請求項２に記載経路計算装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１１−２４９８８５（Ｐ２０１１−２４９８８５Ａ）
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願番号】特願２０１０−１１７８１８（Ｐ２０１０−１１７８１８）
【出願日】平成２２年５月２１日（２０１０．５．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願日】平成２２年５月２１日（２０１０．５．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]