JP5576831B2 - Route calculation method, route calculation device, and program - Google Patents
Route calculation method, route calculation device, and program Download PDFInfo
- Publication number
- JP5576831B2 JP5576831B2 JP2011132051A JP2011132051A JP5576831B2 JP 5576831 B2 JP5576831 B2 JP 5576831B2 JP 2011132051 A JP2011132051 A JP 2011132051A JP 2011132051 A JP2011132051 A JP 2011132051A JP 5576831 B2 JP5576831 B2 JP 5576831B2
- Authority
- JP
- Japan
- Prior art keywords
- node
- route
- search
- total cost
- receiving
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
本発明は、マルチキャスト通信において、最適な経路を選択するために、ネットワークのリンクに距離や帯域などに関連したコスト値を与え、その合計が最小となるマルチキャスト経路を計算する経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムに関する。 The present invention provides a route calculation method and route calculation for giving a cost value related to a distance, a bandwidth, and the like to a network link and calculating a multicast route that minimizes the sum in order to select an optimum route in multicast communication. The present invention relates to a device and a program to be executed by a computer.
近年、デジタル映像配信やグループビデオ会議など、マルチキャスト通信の需要が高まっている。このようなアプリケーションは、データサイズが大きいため、大量のトラフィックがネットワーク上を流れることになる。したがって、ネットワーク管理者は、アプリケーションが満たすべき品質や、データ量に応じて、マルチキャスト経路を決定し、管理する必要がある。リング型やスター型といった、シンプルなネットワークでは、マルチキャスト経路は一意に決まり、ネットワーク管理者は、経路の管理を容易に行うことができる。しかし、近年、ネットワークは複雑化しており、最適な経路を決定するためには、適したマルチキャスト経路計算アルゴリズムが必要である。最適なマルチキャスト経路の決定方法として、ネットワークのリンクにコスト値を与え、マルチキャスト経路全体の合計コストを最小化する方法がある。 In recent years, demand for multicast communication such as digital video distribution and group video conferencing is increasing. Since such an application has a large data size, a large amount of traffic flows on the network. Therefore, the network administrator needs to determine and manage the multicast route according to the quality to be satisfied by the application and the amount of data. In a simple network such as a ring type or a star type, a multicast route is uniquely determined, and the network administrator can easily manage the route. However, in recent years, networks have become complex, and a suitable multicast route calculation algorithm is required to determine an optimum route. As a method for determining an optimum multicast route, there is a method of giving a cost value to a link of a network and minimizing the total cost of the entire multicast route.
合計コストが最小となるマルチキャスト経路を求める問題は、最小シュタイナーツリー問題として、古くから解かれているが、ＮＰ（Nondeterministic Polynomial）完全問題であることが知られており、実時間で最適解を見つけることは困難である。 The problem of finding a multicast route with the lowest total cost has been solved for a long time as a minimum Steiner tree problem, but it is known to be an NP (Nondeterministic Polynomial) complete problem, and an optimal solution is found in real time. It is difficult.
近似解を求める手法として、非特許文献１には、送信ノードと受信ノードそれぞれを結ぶフルメッシュの最短路ネットワークを求め、求めたネットワークにおいて、最小全域木を求めることで、低コストマルチキャスト経路を計算する方法が開示されている。
As a method for obtaining an approximate solution, Non-Patent
また、非特許文献２には、送信ノードからダイクストラ法による最短経路計算を行い、経路探索中に受信ノードが発見されると、その受信ノードを経由して、他の受信ノードに向かう経路を優先的に選択することにより、一経路上に複数の受信ノードを乗せることで、低コストマルチキャスト経路を計算する方法が開示されている。
In
非特許文献１に開示された方法では、コストを低く抑えることが可能だが、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する必要があり、計算量が多くなってしまう。一方、非特許文献２に開示された方法では、計算量は少ないが、コストは非特許文献１より大きくなる傾向がある。
In the method disclosed in
本発明は上述したような技術が有する問題点を解決するためになされたものであり、マルチキャスト経路の合計コストと経路探索の計算量を抑えることを可能にした経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムを提供することを目的とする。 The present invention has been made in order to solve the problems of the above-described technology, a route calculation method, a route calculation device, and a route calculation method capable of suppressing the total cost of a multicast route and the amount of route search calculation, and It is an object to provide a program for causing a computer to execute.
上記目的を達成するための本発明の経路計算方法は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を取得し、
前記複数の受信ノードの経路計算の順位に関して、該複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの各経路のノード間のコスト値を合計した合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを最下位の受信ノードとして前記経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとし、
前記第２の探索ノードの前記隣接ノードの前記合計コストを求める際、該隣接ノードについて、他のノード経由で算出された合計コストが記憶されている場合、該他のノード経由で算出された合計コストと該第２の探索ノード経由で算出される合計コストとを比較し、小さい方を前記合計コストとして選択する。
In order to achieve the above object, the route calculation method of the present invention includes:
Obtaining an identifier corresponding to each node in the network, topology information including information on the path connecting adjacent nodes and the cost value of each path, and information on each identifier of the transmitting node and the plurality of receiving nodes,
Regarding the order of the route calculation of the plurality of receiving nodes, for each of the plurality of receiving nodes, the minimum value among the total costs obtained by summing the cost values between the nodes of each route from the transmitting node to the receiving node. A certain minimum total cost is calculated, the receiving node having the lowest minimum total cost is set as the highest receiving node, the receiving node having the highest minimum total cost is set as the lowest receiving node, and the order of the path calculation is determined.
Set the first search node in order from the highest receiving node of the determined order to the lowest receiving node,
For each set first search node, for the adjacent nodes of the first search node, the cost value between the first search node and the adjacent node is the total cost, and the adjacent node having the minimum total cost Until the second search node coincides with a node on the route set in the route calculation in the transmission node or the higher-order receiving node than the first search node. , By sequentially updating the adjacent node having the minimum total cost from the first search node to the adjacent node of the second search node via the second search node to the second search node. , Setting a route sequentially connecting the second search node updated from the first search node,
When calculating the total cost of the adjacent node for the second search node, if the second search node matches one of the plurality of reception nodes, the second search node The total cost up to zero is reset to zero, and the cost value of the route starting from the second search node is set as the total cost ,
When calculating the total cost of the adjacent node of the second search node, if the total cost calculated via another node is stored for the adjacent node, the total calculated via the other node The cost is compared with the total cost calculated via the second search node, and the smaller one is selected as the total cost .
また、本発明の経路計算装置は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を保存する記憶手段と、
前記複数の受信ノードの経路計算の順位に関して、該複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの各経路のノード間のコスト値を合計した合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを最下位の受信ノードとして前記経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとし、
前記経路パラメータ計算手段は、
前記第２の探索ノードの前記隣接ノードの前記合計コストを求める際、該隣接ノードについて、他のノード経由で算出された合計コストが記憶されている場合、該他のノード経由で算出された合計コストと該第２の探索ノード経由で算出される合計コストとを比較し、小さい方を前記合計コストとして選択する構成である。
The route calculation apparatus of the present invention
Storage means for storing an identifier corresponding to each node in the network, topology information including information on a path connecting adjacent nodes and a cost value of each path, and information on each identifier of the transmitting node and the plurality of receiving nodes When,
With respect to the path computation of the rank of the previous SL plurality of receiving nodes, for each of said plurality of receiving nodes, the minimum value of the total cost of the total cost value between the nodes of each path from the sending node until the said receiving node A calculation order for determining the order of the route calculation by obtaining the minimum total cost of which is the highest receiving node having the lowest minimum total cost and the lowest receiving node having the lowest minimum total cost. A determination means;
The first search node is set in order from the highest receiving node to the lowest receiving node in the order determined by the calculation order determining means, and the adjacent first search node is set for each set first search node. For a node, a cost value between the first search node and the adjacent node is defined as a total cost, an adjacent node having the minimum total cost is defined as a second search node, and the second search node to the second Path parameter calculation means for sequentially updating the adjacent node having the minimum total cost to the adjacent node of the second search node via the search node to the second search node;
When the second search node matches the node on the route set in the route calculation in the sending node or the higher-order receiving node than the first search node, the second search node is updated from the first search node Route parameter determination means for setting a route connecting the second search nodes in order,
The route parameter calculation means includes:
When calculating the total cost of the adjacent node for the second search node, if the second search node matches one of the plurality of reception nodes, the second search node The total cost up to zero is reset to zero, and the cost value of the route starting from the second search node is set as the total cost ,
The route parameter calculation means includes:
When calculating the total cost of the adjacent node of the second search node, if the total cost calculated via another node is stored for the adjacent node, the total calculated via the other node The cost is compared with the total cost calculated via the second search node, and the smaller one is selected as the total cost .
さらに、本発明のプログラムは、上記本発明の経路計算方法をコンピュータに実行させるものである。 Furthermore, a program of the present invention causes a computer to execute the above route calculation method of the present invention.
本発明によれば、マルチキャスト通信を行う際、経路探索の計算量を抑制し、経路全体の合計コストを抑制できる。 ADVANTAGE OF THE INVENTION According to this invention, when performing multicast communication, the computational complexity of a route search can be suppressed and the total cost of the whole route can be suppressed.
本発明のマルチキャスト経路計算装置は、ネットワークのリンクに距離や帯域などと関連付けられたコスト値を与え、コスト値の合計が最小となるマルチキャスト経路を計算する装置である。 The multicast route calculation device of the present invention is a device that gives a cost value associated with a distance, a bandwidth, and the like to a link of a network and calculates a multicast route that minimizes the total cost value.
本発明の一実施形態のマルチキャスト経路計算装置の構成を説明する。図１は本発明の一実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。 A configuration of a multicast route calculation apparatus according to an embodiment of the present invention will be described. FIG. 1 is a block diagram showing a configuration example of a multicast route calculation apparatus according to an embodiment of the present invention.
マルチキャスト経路計算装置１００は、要求取得手段１と、計算順序決定手段２と、計算受信ノード決定手段３と、探索ノード決定手段４と、経路パラメータ計算手段５と、経路パラメータ判定手段６と、経路保存手段７と、経路出力手段８とを有する。また、マルチキャスト経路計算装置１００は、マルチキャスト経路を計算する過程で情報を保存し、また、計算結果を保存するための記憶手段を備えている。記憶手段は、経路記憶手段１１と、訪問済みノード記憶手段１２と、ノード情報記憶手段１３とを有する。
The multicast
次に、図１に示したマルチキャスト経路計算装置１００による経路計算方法の動作を説明する。図２は本発明の一実施形態におけるマルチキャスト経路計算方法の手順を示すフローチャートである。
Next, the operation of the route calculation method by the multicast
要求取得手段１が、ネットワーク内の各ノードの接続関係を表した情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードの識別子を受け付けると（ステップ１０１）、送信ノードの識別子を経路記憶手段１１に格納する。続いて、計算順序決定手段２が、受信ノードの経路計算の順序である計算順序を決定する（ステップ１０２）。計算受信ノード決定手段３が、経路記憶手段１１に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ１０３）。
When the
次に、探索ノード決定手段４が、訪問済みノード記憶手段１２を参照し、経路計算が済んだノードである訪問済みノードが訪問済みノード記憶手段１２に保存されていない場合、ステップ１０３で決定された受信ノードを探索ノードとして決定する。一方、訪問済みノードが訪問済みノード記憶手段１２に保存されている場合、まだ経路計算が済んでいない（訪問済みとなっていない）ノードの中から、ノード情報記憶手段１３を参照して、合計コストが最小のノードを探索ノードとして決定し、探索ノードを訪問済みノード記憶手段１２に格納する（ステップ１０４）。
Next, if the visited
続いて、経路パラメータ計算手段５が、ステップ１０４で決定された探索ノードの隣接ノードについて、探索ノード経由の経路における合計コストを計算する（ステップ１０５）。その際、探索ノードが受信ノードである場合、経路パラメータ計算手段５は、探索ノードまでの合計コストをゼロにリセットし、探索ノードと隣接ノードとの間のコスト値を新たな合計コストとする。ステップ１０５で算出される合計コストを第１の合計コストと称する。なお、本実施形態では、ステップ１０５において、探索ノードが受信ノードであると、探索ノードまでの合計コストをゼロにリセットする場合で説明するが、その合計コストをゼロにリセットしなくてもよい。
Subsequently, the route parameter calculation means 5 calculates the total cost of the route via the search node for the adjacent node of the search node determined in step 104 (step 105). At that time, when the search node is a receiving node, the route parameter calculation means 5 resets the total cost to the search node to zero, and sets the cost value between the search node and the adjacent node as a new total cost. The total cost calculated in
経路パラメータ判定手段６は、隣接ノードについて、ノード情報記憶手段１３を参照し、合計コストが保存されていない場合、または、他のノード経由の経路で既に計算された合計コストである第２の合計コストが保存されているが、第1の合計コストの方が小さい場合（ステップ１０６）、第１の合計コストおよび上記探索ノード経由の経路を、ノード情報記憶手段１３に格納する（ステップ１０７）。第２の合計コストの方が第１の合計コストよりも小さい場合には、経路パラメータ判定手段６は、上記隣接ノードについて、ノード情報記憶手段１３の情報を更新しない。
The route
経路記憶手段１１を参照し、経路記憶手段１１に探索ノードの識別子が含まれていなければ、ステップ１０４の探索ノード決定ステップからステップ１０７の経路パラメータ判定ステップまでの処理を繰り返す（ステップ１０８）。ステップ１０８で探索ノードが経路記憶手段１１に含まれていると、経路保存手段７が、ノード情報記憶手段１３を参照し、探索ノードから受信ノードまでの経路の情報として、探索ノードから受信ノードまでの各ノードの識別子を順に並べた情報を経路記憶手段１１に格納する（ステップ１０９）。
Referring to the
経路記憶手段１１を参照して、ステップ１０１で取得した、受信ノードの識別子が経路記憶手段１１に全て格納されていなければ、ステップ１０３の計算受信ノード決定ステップからステップ１０９の経路保存ステップまでの処理を繰り返す（ステップ１１０）。ステップ１１０で、受信ノードの識別子が経路記憶手段１１に全て格納されていれば、経路出力手段８は、経路記憶手段１１に格納された経路の情報を出力する（ステップ１１１）。
If all the identifiers of the receiving nodes acquired in
以下に、本発明のマルチキャスト経路計算方法およびマルチキャスト経路計算装置についての実施形態を詳しく説明する。 Hereinafter, embodiments of a multicast route calculation method and a multicast route calculation device according to the present invention will be described in detail.
（第１の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。図３は本実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
(First embodiment)
The configuration of the multicast route calculation apparatus of this embodiment will be described. FIG. 3 is a block diagram illustrating a configuration example of the multicast route calculation apparatus according to the present embodiment.
図３に示すように、マルチキャスト経路計算装置２００は、制御部２０と、記憶部３０とを有する。制御部２０は、要求取得部２１と、計算順序決定部２２と、初期化部２３と、計算受信ノード決定部２４と、探索ノード決定部２５と、経路パラメータ計算部２６と、経路パラメータ判定部２７と、経路保存部２８と、経路出力部２９とを有する。記憶部３０は、トポロジ情報記憶部３１と、送信・受信ノード記憶部３２と、経路記憶部３３と、訪問済みノード記憶部３４と、ノード情報記憶部３５とを有する。
As illustrated in FIG. 3, the multicast
要求取得部２１は、外部からトポロジ情報と、ネットワーク内のノードのうち送信ノードおよび複数の受信ノードのそれぞれを特定するための情報とが入力装置（不図示）を介して入力され、または、これらの情報を記憶装置（不図示）から読み出す。ノードを特定するための情報とは、ネットワーク内のノード毎に異なる識別子である。トポロジ情報には、ネットワーク内に配置されている全てのノードの識別子の情報と、隣接するノード同士を接続する経路の情報と、各経路のコスト値の情報とが含まれている。
The
要求取得部２１は、上記のようにして、トポロジ情報と、送信ノードおよび受信ノードのそれぞれの識別子の情報とを取得すると、トポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードおよび受信ノードのそれぞれの識別子を送信・受信ノード記憶部３２に格納し、送信ノードの識別子を経路記憶部３３に格納する。
When the
計算順序決定部２２は、送信・受信ノード記憶部３２を参照し、受信ノードの計算順序を決定し、決定した計算順序を送信・受信ノード記憶部３２に格納する。
The calculation
初期化部２３は、訪問済みノード記憶部３４およびノード情報記憶部３５を初期化する。計算受信ノード決定部２４は、送信・受信ノード記憶部３２および経路記憶部３３を参照し、経路記憶部３３に格納されていない受信ノードの中で計算順序最上位の受信ノードを決定する。
The
探索ノード決定部２５は、訪問済みノード記憶部３４およびノード情報記憶部３５を参照し、探索ノードを決定し、決定した探索ノードを訪問済みノード記憶部３４に格納する。
The search
経路パラメータ計算部２６は、トポロジ情報記憶部３１を参照し、上記探索ノードの隣接ノードについて、探索ノード経由の経路における第１の合計コストを計算する。
The route
経路パラメータ判定部２７は、ノード情報記憶部３５を参照し、上記隣接ノードについて、既に算出された第２の合計コストがノード情報記憶部３５に格納されていると、第２の合計コストと第１の合計コストとを比較し、合計コストの小さい方を残すように、ノード情報記憶部３５の情報を更新する。ノード情報記憶部３５に上記隣接ノードの第２の合計コストが格納されていない場合、経路パラメータ判定部２７は、経路パラメータ計算部２６が算出した第１の合計コストを隣接ノードの識別子と組にしてノード情報記憶部３５に格納する。
The route
経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。経路出力部２９は、経路記憶部３３に格納された経路の情報を出力する。
The
なお、制御部２０には、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）（不図示）と、プログラムを格納するためのメモリ（不図示）とが設けられている。ＣＰＵがプログラムを実行することで、要求取得部２１、計算順序決定部２２、初期化部２３、計算受信ノード決定部２４、探索ノード決定部２５、経路パラメータ計算部２６、経路パラメータ判定部２７、経路保存部２８および経路出力部２９がマルチキャスト経路計算装置２００に仮想的に構成される。
The control unit 20 is provided with a CPU (Central Processing Unit) (not shown) for executing processing according to a program and a memory (not shown) for storing the program. When the CPU executes the program, the
次に、本実施形態のマルチキャスト経路計算装置２００の動作を説明する。図４および図５は本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
Next, the operation of the multicast
まず、ステップ２０１に示すように、要求取得部２１がネットワークの各ノードの接続関係を表したトポロジ情報と、送信ノードおよび受信ノードの識別子を取得する。トポロジ情報には、各ノードの接続関係の情報の他に、各リンクのコスト値の情報が含まれている。また、受信ノードは、ここでは、複数のノードとする。また、要求取得部２１は、取得したトポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードと受信ノードの識別子を送信・受信ノード記憶部３２に保存する。
First, as shown in
次に、要求取得部２１が、送信ノードの識別子を経路記憶部３３に保存する（ステップ２０２）。次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する（ステップ２０３）。
Next, the
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを比較し、最小合計コストが最も小さい受信ノードを計算順序最上位、最も大きい受信ノードを最下位とし、計算順序を送信・受信ノード記憶部３２の各受信ノードに対応して保存する（ステップ２０４）。次に、初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部の情報を削除する（ステップ２０５）。ただし、最初はデータが格納されていないため、この処理を行う必要はない。
Next, the calculation
次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ２０６）。ただし、最初は、経路記憶部３３には、送信ノードの情報しか保存されていないため、計算順序最上位の受信ノードが決定される。
Next, the calculation reception
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する（ステップ２０７）。訪問済みノード記憶部３４に何も保存されていない場合、探索ノード決定２５は、ステップ２０６で決定された受信ノードを探索ノードとして決定し、この受信ノードを訪問済みノード記憶部３４に保存する（ステップ２０８）。ここで設定される受信ノードが第１の探索ノードに相当する。
Next, the search
一方、ステップ２０７の判定で訪問済みノード記憶部３４に何らかのノードが保存されている場合、探索ノード決定部２５は、まだ訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照する。そして、探索ノード決定部２５は、合計コストが最小のノードを１つ選び、選んだノードを探索ノードとして決定し、訪問済みノード記憶部３４に保存する（ステップ２０９）。ここで設定される探索ノードは第２の探索ノードに相当し、第２の探索ノードは、送信ノードまたは上記計算順序が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで更新される。
On the other hand, if any node is stored in the visited
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１（第１の合計コストに相当）を計算する（ステップ２１０）。合計コストＣ１は、
Ｃ１＝Ｉｄ＊Ｃ（ｖ）＋ｗ（ｖ，ｕ）・・・（式１）
で求まる。
Next, the route
C1 = Id * C (v) + w (v, u) (Formula 1)
It is obtained by
（式１）において、Ｉｄは、探索ノードが受信ノードの１つであれば０であり、そうでなければ１である。Ｃ（ｖ）は、探索ノードｖの合計コストである。ｗ（ｖ，ｕ）は、探索ノードと隣接ノード間のリンクのコスト値である。Ｃ（ｖ）は、ノード情報記憶部３５に保存されている値を用いる。ノード情報記憶部３５に探索ノードｖが保存されていない場合、Ｃ（ｖ）は０である。
In (Expression 1), Id is 0 if the search node is one of the receiving nodes, and 1 otherwise. C (v) is the total cost of the search node v. w (v, u) is the cost value of the link between the search node and the adjacent node. A value stored in the node
次に、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣ（第２の合計コストに相当）が既に保存されているかどうかを判定する（ステップ２１１）。合計コストＣが保存されていない場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と、経路を示す情報として探索ノードの識別子とを一緒にして保存する。ステップ２１１の判定で既にＣが保存されている場合、経路パラメータ判定部２７は、Ｃ１＜Ｃかどうかを判定する（ステップ２１２）。Ｃ１＜Ｃである場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と経路（探索ノード）の識別子の情報を上書きする（ステップ２１３）。
Next, the route
経路パラメータ判定部２７は、探索ノードに対する隣接ノード全てに対し、Ｃ１の計算が行われるまで、ステップ２１０〜ステップ２１３の処理を繰り返す（ステップ２１４）。ステップ２１４で、Ｃ１の計算を行っていない隣接ノードがなければ、経路パラメータ判定部２７は、探索ノードが経路記憶部３３に保存されているか否かを判定し（ステップ２１５）、探索ノードが経路記憶部３３に保存されていなければ、ステップ２０７〜ステップ２１４の処理を繰り返す。
The route
ステップ２１５で探索ノードが経路記憶部３３に保存されているノードであれば、経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。つまり、経路保存部２８は、経路情報として、探索ノードから受信ノードまでの経路における各ノードの識別子を経路順に並べた情報を、経路記憶部３３に保存する。この経路は、ノード情報記憶部３５の各ノードに保存されている経路（ノード）をたどることで得られる。
If the search node is a node stored in the
このようにして、ステップ２０１で取得した識別子の全ての受信ノードの経路の情報が、経路記憶部３３に保存されるまで、初期化部２３が実行するステップ２０５〜経路保存部２８が実行するステップ２１６までの処理を繰り返す（ステップ２１７）。
In this way, steps 205 to 5 that are executed by the
全ての受信ノードの経路の情報が経路記憶部３３に保存されたら、最後に、経路出力部２９が、経路記憶部３３に保存されている経路の情報を出力することで（ステップ２１８）、処理が終了する。
When the route information of all the receiving nodes is stored in the
次に、上述した本実施形態のマルチキャスト経路計算方法の具体例を、図６を参照して説明する。図６はネットワークトポロジの一構成例を示す図である。 Next, a specific example of the multicast route calculation method of the present embodiment described above will be described with reference to FIG. FIG. 6 is a diagram illustrating a configuration example of a network topology.
図６に示す例では、ノードの識別子を１〜１６のノード番号としている。ノード間のリンク上の数値はコスト値を表している。
In the example illustrated in FIG. 6, the node identifiers are the
はじめに、要求取得部２１がトポロジ情報を外部から取得する。各ノードの接続関係、各リンクのコスト値は、図６に示すとおりである。次に、要求取得部２１は、送信ノードと複数の受信ノードの識別子を外部から取得する。本具体例では、送信ノードを図６に示すノード１とする。また、受信ノードの数は５個とし、受信ノードＡを図６に示すノード９とし、受信ノードＢをノード１０とし、受信ノードＣをノード１３とし、受信ノードＤをノード１２とし、受信ノードＥをノード１５とする。要求取得部２１は、トポロジ情報をトポロジ情報記憶部３１に保存し、送信ノードと受信ノードＡ〜Ｅの識別子を送信・受信ノード記憶部３２に保存する。さらに、要求取得部２１は、送信ノードの識別子を経路記憶部３３に保存する。
First, the
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する。本具体例において、各受信ノードの最小合計コストは、受信ノードＡが３、受信ノードＢが５、受信ノードＣが６、受信ノードＤが９、受信ノードＥが１０となる。計算順序決定部２２は、これらのコスト値を比較し、最小合計コストが小さい方から順に、以下に示すように、計算順序を決定する。
１位：受信ノードＡ
２位：受信ノードＢ
３位：受信ノードＣ
４位：受信ノードＤ
５位：受信ノードＥ
計算順序決定部２２は、これらの最小合計コストと順位の情報を送信・受信ノード記憶部３２における、それぞれの受信ノードの識別子の情報に関連付けて保存する。
Next, the calculation
1st place: Receiving node A
Second place: Receiving Node B
3rd place: Receiving node C
4th: Receiving node D
5th: Receiving node E
The calculation
図７Ａから図９Ｂは、第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。図７Ａから図８Ａに示す黒三角印は探索ノードを示し、図７Ａから図９Ｂにおいて、ノードの脇に記述された四角の中のＣとＲの情報は、ノード情報記憶部３５に保存される情報を示す。
7A to 9B are diagrams for explaining a specific example of the multicast route calculation method according to the first embodiment. Black triangles shown in FIG. 7A to FIG. 8A indicate search nodes. In FIG. 7A to FIG. 9B, information on C and R in squares written beside the nodes is stored in the node
初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。ただし、最初はデータが格納されていないため、この処理を行う必要はない。次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する。ただし、最初は、経路記憶部３３には、送信ノードの識別子しか保存されていないため、計算順序最上位の受信ノードが決定される。本具体例では、受信ノードＡが選択される。
The
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する。最初は何も保存されていないため、ステップ２０６で決定された受信ノードＡを探索ノードとして決定し、受信ノードＡを訪問済みノード記憶部３４に保存する（図７Ａ）。
Next, the search
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード９（受信ノードＡ）が探索ノードｖに相当し、ノード５、ノード６、ノード１０およびノード１３が隣接ノードｕに相当する。
Next, the route
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は、合計コストＣが保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する（図５に示したステップ２１３）。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｂ）。図７Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。また、図７Ａから図９Ｂの各図において、経路記憶部３３および訪問済みノード記憶部３４のそれぞれに保存される、ノードの識別子を破線枠の中に示す。
Further, the route
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
Subsequently, in
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード５が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図７Ｃ）。
Since the search
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード５が探索ノードｖに相当し、ノード１、ノード２、ノード６およびノード９が隣接ノードｕに相当する。
Next, the route
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードを保存する。一方、既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｄ）。図７Ｄに示すように、ノード１およびノード２については、Ｃ１と経路として探索ノード（ノード５）とが保存され、ノード６およびノード９については情報が更新されなかった。
Further, the route
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
Subsequently, in
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが３のノード１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図８Ａ）。ここで、合計コスト３のノードが複数あるが、そのような場合、ノード番号が最も小さいノードを選択することとした。
Since the search
ノード１の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＡまでの経路の情報が保存される（図８Ｂ）。ここで、探索ノードから受信ノードＡまでの経路の情報は、具体的には、送信ノード１、ノード５およびノード９の識別子が順に並んだ情報である。図８Ｂでは、保存された経路の情報に相当する経路を太線で示している。
Since the identifier of the
経路記憶部３３には全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する（図８Ｃ）。
Since the identifiers of all receiving nodes are not stored in the
次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＢを選択する。
Next, the calculation reception
受信ノードＢについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１０、ノード６、ノード１１、ノード１３、ノード９の順に決定される。
For the receiving node B, when the search node determination, route parameter calculation, and route parameter determination processing are repeated in the same manner as the reception node A, the search node is determined in the order of the
ノード９の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＢまでの経路が保存される（図８Ｄ）。ここで、ノード１３が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。また、このとき、探索ノードに相当するノード９から受信ノードＢに相当するノード１０までの経路情報として、ノード９、ノード１３およびノード１０が順に並んだ情報が経路記憶部３３に保存される。つまり、受信ノードＣの識別子が経路記憶部３３に保存される。
Since the identifier of the
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＤを選択する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われない。
Since the identifiers of all receiving nodes are not stored in the
受信ノードＤについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。
For the receiving node D, when the search node determination, the route parameter calculation, and the route parameter determination process are repeated in the same manner as the receiving node A, the search node is the
ノード１０の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図９Ａ）。
Since the identifier of the
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
Since the identifiers of all receiving nodes are not stored in the
受信ノードＥについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１５、ノード１４、ノード１６、ノード１２の順に決定される。
For the receiving node E, when the search node determination, the route parameter calculation, and the route parameter determination process are repeated in the same manner as the reception node A, the search nodes are determined in the order of the
ノード１２の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＥまでの経路が保存される（図９Ｂ）。
Since the identifier of the
経路記憶部３３に全ての受信ノードの識別子が保存されたため、最後に経路出力部２９が経路記憶部３３を参照し、マルチキャスト経路を、例えば以下のように出力し、処理を終了する。
受信ノードＡへの経路：１、５、９
受信ノードＢへの経路：１、５、９、１３、１０
受信ノードＣへの経路：１、５、９、１３
受信ノードＤへの経路：１、５、９、１３、１０、１１、１２
受信ノードＥへの経路：１、５、９、１３、１０、１１、１２、１６、１５
Since the identifiers of all receiving nodes are stored in the
Route to receiving node A: 1, 5, 9
Route to receiving node B: 1, 5, 9, 13, 10
Route to receiving node C: 1, 5, 9, 13
Route to receiving
Route to receiving node E: 1, 5, 9, 13, 10, 11, 12, 16, 15
本実施形態によれば、受信ノードから送信ノードへ、また、受信ノードから既に確定した経路へ、最小の合計コストで経路を接続させていくことで、１つの経路に複数の受信ノードが乗り、マルチキャスト経路全体の合計コストを低く抑えることができる。また、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する場合よりも計算量が少なく済む。 According to the present embodiment, a plurality of receiving nodes ride on one route by connecting the routes from the receiving node to the transmitting node and from the receiving node to the already determined route at the minimum total cost. The total cost of the entire multicast route can be kept low. In addition, the calculation amount is smaller than in the case of calculating full mesh paths of all combinations of the transmission node and the reception node.
また、本実施形態では、ある受信ノードからの経路探索の途中で他の受信ノードが発見されると、合計コストをゼロにリセットする場合を説明したが、必ずしもゼロにリセットしなくてもよい。このとき合計コストをゼロにリセットすることにより、他の受信ノードを経由する経路が優先的に選択されるため、さらにマルチキャスト経路全体の合計コストを最小限に抑えることが可能になる。 Further, in the present embodiment, a case has been described in which the total cost is reset to zero when another receiving node is found during a route search from a certain receiving node. However, the total cost may not necessarily be reset to zero. At this time, by resetting the total cost to zero, a route passing through another receiving node is preferentially selected, so that the total cost of the entire multicast route can be further minimized.
（第２の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。
(Second Embodiment)
The configuration of the multicast route calculation apparatus of this embodiment will be described.
図１０は、本実施形態のマルチキャスト経路計算装置の一構成例を示すブロック図である。なお、本実施形態では、第１の実施形態と異なる点を詳細に説明し、第１の実施形態と同様な構成についてはその詳細な説明を省略する。 FIG. 10 is a block diagram illustrating a configuration example of the multicast route calculation apparatus according to this embodiment. In the present embodiment, points different from the first embodiment will be described in detail, and detailed description of the same configurations as those of the first embodiment will be omitted.
本実施形態のマルチキャスト経路計算装置３００は、第１の実施形態で説明した初期化部２３と計算受信ノード決定部２４の処理が異なる。本実施形態では、図１０に示すように、第１の実施形態における初期化部２３と計算受信ノード決定部２４の処理順序が逆転し、初期化部２３の代わりに情報更新部４１が設けられている。
The multicast
情報更新部４１は、計算受信ノード決定部２４で決定された受信ノード（受信ノードｄとする）の１つ前の順位の受信ノード（受信ノードｄ’とする）からの経路探索において、受信ノードｄからの経路が計算されている場合に、その経路と合計コストの情報を含む経路探索情報を訪問済みノード記憶部３４とノード情報記憶部３５に残し、それ以外の情報を削除する。
The
図１１および図１２は、本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。 11 and 12 are flowcharts showing the operation procedure of the multicast route calculation method in this embodiment.
本実施形態におけるマルチキャスト経路計算方法は、図１０で示したマルチキャスト経路計算装置の構成に対応して、第１の実施形態で説明した初期化ステップ（ステップ２０５）と計算受信ノード決定ステップ（ステップ２０６）の順序が逆になり、初期化ステップ（ステップ２０５）の代わりに情報更新ステップ（ステップ３０６）を有する。 The multicast route calculation method in this embodiment corresponds to the configuration of the multicast route calculation apparatus shown in FIG. 10, and the initialization step (step 205) and the calculation receiving node determination step (step 206) described in the first embodiment. ) Is reversed, and an information update step (step 306) is provided instead of the initialization step (step 205).
図４に示したステップ２０６は図１１に示すステップ３０５に相当し、図４に示したステップ２０１〜２０４およびステップ２０７〜２０９のそれぞれは図１１に示すステップ３０１〜３０４およびステップ３０７〜３０９のそれぞれに相当しており、同様な処理についての詳細な説明を省略する。また、図５に示したステップ２１０〜ステップ２１８のそれぞれは図１１に示すステップ３１０〜ステップ３１８に相当し、同様な処理についての詳細な説明を省略する。
Step 206 shown in FIG. 4 corresponds to step 305 shown in FIG. 11, and steps 201 to 204 and
本実施形態のマルチキャスト経路計算装置３００の動作の具体例について、第１の実施の形態と異なる部分を詳しく説明する。ここでも、ネットワークトポロジの一例として、図６に示したトポロジを用いる。
A specific example of the operation of the multicast
第１の実施形態で説明した動作を例に説明する。受信ノードＡからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＢに決定する。受信ノードＡからの経路探索では、受信ノードＢからの経路は計算されていないため、図１１に示すステップ３０６において、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
The operation described in the first embodiment will be described as an example. After the route search from the reception node A is completed, the calculation reception
次に、受信ノードＢからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＤに決定する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われていない。したがって、この場合にも、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
Next, after the end of the route search from the receiving node B, the calculation receiving
受信ノードＤからの経路計算について、情報更新ステップ以降の処理を、具体的に説明する。図１３Ａから図１５Ｂは本実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。 Regarding the route calculation from the receiving node D, the processing after the information update step will be specifically described. FIG. 13A to FIG. 15B are diagrams for explaining a specific example of the multicast route calculation method in the present embodiment.
探索ノード決定部２５が、受信ノードＤを探索ノードとして決定し、受信ノードＤの識別子を訪問済みノード記憶部３４に保存する（図１３Ａ）。
The search
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｂ）。図１３Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。
Next, the route
探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図１１に示すステップ３０７）に戻る。
Since the search node is not stored in the
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード１１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図１３Ｃ）。
Since the search
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｄ）。
Next, the route
上記の探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である（図１４Ａ〜図１４Ｃ）。
When the above search node determination, route parameter calculation, and route parameter determination processes are repeated, the search nodes are determined in the order of
ノード１０の識別子が経路記憶部３３に保存されているため、図１１および図１２に示すステップ３０７からステップ３１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図１４Ｄ）。
Since the identifier of the
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、計算受信ノード決定部２４の処理に戻る。計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
Since the identifiers of all receiving nodes are not stored in the
次に、図１１に示したステップ３０６において、情報更新部４１が、受信ノードＤからの経路探索において、受信ノードＥからの経路が計算されているかを判定する。つまり、受信ノードＥの識別子が訪問済みノード記憶部３４に格納されており、受信ノードＥを経由して探索されたノードの識別子が訪問済みノード記憶部３４に格納されているかどうかを判定する。
Next, in
受信ノードＥの識別子が訪問済みノード記憶部３４に格納されている場合には、情報更新部４１は、受信ノードＥと受信ノードＥから探索された訪問済みノードの識別子を、訪問済みノード記憶部３４に残し、それ以外のノードの識別子を削除する。また、情報更新部４１は、受信ノードＥを経由して探索された訪問済みノードに関する情報をノード情報記憶部３５に残し、それ以外のノードに関する情報を削除する。本動作例では、ノード１５、ノード１４、ノード１６が訪問済みノード記憶部３４に残され、ノード１４とノード１６の情報がノード情報記憶部３５に残される（図１５Ａ）。経路パラメータ計算部２６は、ノード１５、ノード１４およびノード１６の経路探索情報を利用することが可能となる。
When the identifier of the receiving node E is stored in the visited
これ以降は、受信ノードＤと同様に、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２と決定され、経路計算が完了する（図１５Ｂ）。
Thereafter, as with the receiving node D, when the search node determination, route parameter calculation, and route parameter determination processing are repeated, the search node is determined as the
第１の実施形態では、受信ノードＥから新たに経路計算を行ったが、本実施形態では、ノード１４とノード１６への経路探索を行う必要がなく、計算量が少なくてすむ。経路出力部２９が出力する経路の情報は、第１の実施形態と同じになる。
In the first embodiment, a new route calculation is performed from the receiving node E. However, in this embodiment, it is not necessary to perform a route search to the
本実施形態によれば、第１の実施形態と同様にマルチキャスト経路全体の合計コストを最小限に抑えられるだけでなく、ある受信ノードからの経路計算において、並行して計算された、次の計算順位の受信ノードからの経路を、次の受信ノードからの経路計算時に流用することで、計算量の低減を図ることが可能である。 According to the present embodiment, as in the first embodiment, not only the total cost of the entire multicast route can be minimized, but also the following calculation calculated in parallel in the route calculation from a certain receiving node: The amount of calculation can be reduced by diverting the route from the receiving node of the rank when calculating the route from the next receiving node.
なお、上述した第１または第２の実施形態で説明した動作をプログラムとして構築し、そのプログラムをマルチキャスト経路計算装置として利用されるコンピュータにインストールして実行させる、または、そのプログラムをネットワークを介して流通させることが可能である。 The operation described in the first or second embodiment described above is constructed as a program, and the program is installed and executed on a computer used as a multicast route calculation device, or the program is executed via a network. It can be distributed.
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、ＣＤ−ＲＯＭ等の搬送可能な記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。 Further, the constructed program can be stored in a computer-readable disk device or a transportable storage medium such as a CD-ROM, installed in a computer, executed, or distributed.
本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。 The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.
１００、２００、３００ マルチキャスト経路計算装置
１ 要求取得手段
２ 計算順序決定手段
４ 探索ノード決定手段
５ 経路パラメータ計算手段
６ 経路パラメータ判定手段
７ 経路保存手段
８ 経路出力手段
１１ 経路記憶手段
１２ 訪問済みノード記憶手段
１３ ノード情報記憶手段
２０ 制御部
３０ 記憶部
100, 200, 300 Multicast
Claims (5)
前記複数の受信ノードの経路計算の順位に関して、該複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの各経路のノード間のコスト値を合計した合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを最下位の受信ノードとして前記経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとし、
前記第２の探索ノードの前記隣接ノードの前記合計コストを求める際、該隣接ノードについて、他のノード経由で算出された合計コストが記憶されている場合、該他のノード経由で算出された合計コストと該第２の探索ノード経由で算出される合計コストとを比較し、小さい方を前記合計コストとして選択する、経路計算方法。 Obtaining an identifier corresponding to each node in the network, topology information including information on the path connecting adjacent nodes and the cost value of each path, and information on each identifier of the transmitting node and the plurality of receiving nodes,
Regarding the order of the route calculation of the plurality of receiving nodes, for each of the plurality of receiving nodes, the minimum value among the total costs obtained by summing the cost values between the nodes of each route from the transmitting node to the receiving node. A certain minimum total cost is calculated, the receiving node having the lowest minimum total cost is set as the highest receiving node, the receiving node having the highest minimum total cost is set as the lowest receiving node, and the order of the path calculation is determined.
Set the first search node in order from the highest receiving node of the determined order to the lowest receiving node,
For each set first search node, for the adjacent nodes of the first search node, the cost value between the first search node and the adjacent node is the total cost, and the adjacent node having the minimum total cost Until the second search node coincides with a node on the route set in the route calculation in the transmission node or the higher-order receiving node than the first search node. , By sequentially updating the adjacent node having the minimum total cost from the first search node to the adjacent node of the second search node via the second search node to the second search node. , Setting a route sequentially connecting the second search node updated from the first search node,
When calculating the total cost of the adjacent node for the second search node, if the second search node matches one of the plurality of reception nodes, the second search node The total cost up to zero is reset to zero, and the cost value of the route starting from the second search node is set as the total cost ,
When calculating the total cost of the adjacent node of the second search node, if the total cost calculated via another node is stored for the adjacent node, the total calculated via the other node A route calculation method in which a cost is compared with a total cost calculated via the second search node, and a smaller one is selected as the total cost .
前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を保存し、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも順位が１つ上位の受信ノードの経路計算の過程で保存された前記経路探索情報のうち、該任意の順位の受信ノードに関する前記経路探索情報が保存されている場合、該経路探索情報を利用する、経路計算方法。 The route calculation method according to claim 1,
Storing route search information including information on the adjacent node and the total cost of the first search node, and information on the adjacent node and the total cost of the second search node;
Among the determined ranks, when performing route calculation of a receiving node of an arbitrary rank, the route search information stored in the route calculation process of the receiving node one rank higher than the arbitrary rank , A route calculation method using the route search information when the route search information related to receiving nodes of an arbitrary order is stored .
前記複数の受信ノードの経路計算の順位に関して、該複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの各経路のノード間のコスト値を合計した合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを最下位の受信ノードとして前記経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとし、
前記経路パラメータ計算手段は、
前記第２の探索ノードの前記隣接ノードの前記合計コストを求める際、該隣接ノードについて、他のノード経由で算出された合計コストが記憶されている場合、該他のノード経由で算出された合計コストと該第２の探索ノード経由で算出される合計コストとを比較し、小さい方を前記合計コストとして選択する、経路計算装置。 Storage means for storing an identifier corresponding to each node in the network, topology information including information on a path connecting adjacent nodes and a cost value of each path, and information on each identifier of the transmitting node and the plurality of receiving nodes When,
With respect to the path computation of the rank of the previous SL plurality of receiving nodes, for each of said plurality of receiving nodes, the minimum value of the total cost of the total cost value between the nodes of each path from the sending node until the said receiving node A calculation order for determining the order of the route calculation by obtaining the minimum total cost of which is the highest receiving node having the lowest minimum total cost and the lowest receiving node having the lowest minimum total cost. A determination means;
The first search node is set in order from the highest receiving node to the lowest receiving node in the order determined by the calculation order determining means, and the adjacent first search node is set for each set first search node. For a node, a cost value between the first search node and the adjacent node is defined as a total cost, an adjacent node having the minimum total cost is defined as a second search node, and the second search node to the second Path parameter calculation means for sequentially updating the adjacent node having the minimum total cost to the adjacent node of the second search node via the search node to the second search node;
When the second search node matches the node on the route set in the route calculation in the sending node or the higher-order receiving node than the first search node, the second search node is updated from the first search node Route parameter determination means for setting a route connecting the second search nodes in order,
The route parameter calculation means includes:
When calculating the total cost of the adjacent node for the second search node, if the second search node matches one of the plurality of reception nodes, the second search node The total cost up to zero is reset to zero, and the cost value of the route starting from the second search node is set as the total cost ,
The route parameter calculation means includes:
When calculating the total cost of the adjacent node of the second search node, if the total cost calculated via another node is stored for the adjacent node, the total calculated via the other node A route calculation device that compares a cost with a total cost calculated via the second search node and selects a smaller one as the total cost .
前記経路パラメータ判定手段は、
前記経路パラメータ計算手段が出力する、前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を前記記憶手段に保存し、
前記経路パラメータ計算手段は、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも順位が１つ上位の受信ノードの経路計算の過程で前記記憶手段に保存された前記経路探索情報のうち、該任意の順位の受信ノードに関する前記経路探索情報が保存されている場合、該経路探索情報を利用する、経路計算装置。 The route calculation apparatus according to claim 3 , wherein
The route parameter determination means includes
The route search information output by the route parameter calculation means includes information on the adjacent node and the total cost of the first search node, and information on the adjacent node and the total cost of the second search node. Save to
The route parameter calculation means includes:
The route search information stored in the storage means in the course of the route calculation of the receiving node one rank higher than the arbitrary rank when performing the route calculation of the receiving node of any rank among the determined ranks A route calculation device that uses the route search information when the route search information related to the receiving nodes in any order is stored .
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2011132051A JP5576831B2 (en) | 2011-06-14 | 2011-06-14 | Route calculation method, route calculation device, and program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2011132051A JP5576831B2 (en) | 2011-06-14 | 2011-06-14 | Route calculation method, route calculation device, and program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2013005079A JP2013005079A (en) | 2013-01-07 |
| JP5576831B2 true JP5576831B2 (en) | 2014-08-20 |
Family
ID=47673214
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2011132051A Expired - Fee Related JP5576831B2 (en) | 2011-06-14 | 2011-06-14 | Route calculation method, route calculation device, and program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP5576831B2 (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113190010B (en) * | 2021-05-08 | 2024-04-05 | 珠海一微半导体股份有限公司 | Edge obstacle detouring path planning method, chip and robot |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4536690B2 (en) * | 2006-08-28 | 2010-09-01 | 日本電信電話株式会社 | Route calculation method, apparatus and program |
| JP2011091495A (en) * | 2009-10-20 | 2011-05-06 | Nippon Telegr & Teleph Corp <Ntt> | Multicast route search device, method and program |
-
2011
- 2011-06-14 JP JP2011132051A patent/JP5576831B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2013005079A (en) | 2013-01-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111770019A (en) | A Q-learning Optical On-Chip Network Adaptive Routing Planning Method Based on Dijkstra's Algorithm | |
| JP3945656B2 (en) | Management node device, node device, network configuration management system, network configuration management method, node device control method, management node device control method | |
| JP2005086460A (en) | Route design apparatus, method and program | |
| CN109922004A (en) | The traffic engineering method and device of IPv6 network based on partial deployment Segment routing | |
| US10404576B2 (en) | Constrained shortest path determination in a network | |
| JP5391322B2 (en) | Route calculation method, program, and calculation device | |
| CN104506435B (en) | Shortest path in SDN controllers and SDN determines method | |
| CN113992259B (en) | Method for constructing time slot resource expansion graph | |
| WO2017045578A1 (en) | Topological graph optimal path algorithm with constraint conditions | |
| CN107196858A (en) | A kind of k solving the shortest path methods for considering polymorphic type constraint | |
| WO2017117951A1 (en) | Virtual mapping method and device | |
| US8085688B2 (en) | Methods and systems for determining a network data path | |
| CN105634974B (en) | Route determining methods and device in software defined network | |
| CN109511091A (en) | A kind of BLE MESH network routing algorithm based on location information | |
| JP5576831B2 (en) | Route calculation method, route calculation device, and program | |
| CN104753694A (en) | Method and device for automatic route selection of optical cable | |
| JP2013175913A (en) | Communication system, path determination device, path determination method, and path determination program | |
| CN107453997B (en) | An Optimal Routing Method Based on Double Cost | |
| JP5419740B2 (en) | Pass accommodation design method | |
| JP2010286978A (en) | Route search method, apparatus and program | |
| JP5001996B2 (en) | Route calculation apparatus, route calculation method and program | |
| JP2013009181A (en) | Plural route search method and device | |
| JP2017212492A (en) | Network route selection device, network topology display device, network route selection method, network topology display method, and program | |
| JP2008211656A (en) | Apparatus, method, and program for creating multicast tree | |
| CN108124294B (en) | A routing method under the constraint of identity recursive computation |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| RD01 | Notification of change of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7426 Effective date: 20130305 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20130723 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20140210 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20140218 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20140416 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20140701 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20140704 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 5576831 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |