JP4479602B2 - Multicast route calculation method and apparatus, program, and storage medium storing multicast route calculation program - Google Patents

Description

  The present invention relates to a multicast path calculation method and apparatus, a program, and a storage medium storing a multicast path calculation program. In particular, in a communication network in which a multicast transfer apparatus and a unicast transmission apparatus are mixed, from a transmission transmission apparatus to a reception transmission apparatus. The present invention relates to a multicast route calculation method and apparatus and program used for obtaining a route that minimizes the transfer cost up to and a storage medium storing the multicast route calculation program.

  Conventionally, in a communication network, as shown in FIG. 14, the multicast route is calculated from the topology information 10 collected by the topology information collecting mechanism and the route setting restriction conditions 11 such as the transmission transmission device, the reception transmission device, and the necessary bandwidth. A multicast route calculation device 12 that outputs the calculation result to the route setting mechanism 13 is used.

  Here, a multicast route calculation apparatus using the Dijkstra multicast route calculation method according to the prior art will be described with reference to FIG.

  When the topology information including the connection relation and the link cost as shown in FIG. 15A and the conditions of the transmission transmission device / reception transmission device are input, the link cost from the transmission transmission device to the reception transmission device is minimized. Calculate a multicast route such that

  Next, as shown in FIG. 5B, the link cost from the transmission transmission apparatus A to the adjacent transmission apparatuses (B, I) is calculated and set as a candidate apparatus. Next, the one with the lowest link cost from the transmission transmission device is selected from the candidate devices. In this topology, B having a link cost of “2” is selected, and a route from the transmission transmission apparatus A to B is determined. B is removed from the candidate devices, and is a visited device. The transmission apparatus adjacent to the determined transmission apparatus is searched. At that time, the device A immediately before the determined transmission device is not included in the adjacent devices. As shown in FIG. 6C, the link cost from the transmission transmission apparatus via the determined transmission apparatus is calculated for each adjacent transmission apparatus, and is set as a candidate apparatus.

  Similarly, as shown in FIG. 16D, I is a visited device, and transmission devices E and H adjacent to I are candidate devices.

  Next, from the candidate devices, the one with the lowest link cost from the transmission transmission device is selected. If there are a plurality of candidate devices, one is selected using other route setting restriction conditions. In this example, G is selected and G is the visited device. Further, when a route adjacent to the transmission device G is selected as a candidate, if the adjacent device is already a candidate device or a visited transmission device, the link cost from the transmission transmission device already calculated, The link cost from the transmission transmission apparatus via the determined transmission apparatus G is compared, and the smaller one is set as a route to the adjacent apparatus. Accordingly, in FIG. 16E, H is a candidate device from I, but by comparing the link costs from the transmission transmission device (comparison of (d) and (e) in FIG. 16), H is Candidate device from G. F is a candidate device from B because the link cost from the transmission transmission device via G is large.

  Subsequently, as shown in FIG. 16 (f), F is removed from the candidate devices in the route to F as in the previous case, and is set as a visited device. Further, the route to E is determined, E is removed from the candidate devices, and the visited device is set. As shown in FIG. 17 (g), an adjacent device of E is a candidate device D.

  After searching for all devices, the route is determined from the candidate devices in ascending order of link cost from the transmission transmission device.

  As a result, as shown in FIG. 17 (h), a multicast route including all the reception transmission devices input from the transmission transmission device has been found. As shown in FIG. 17 (i), an unnecessary route that does not reach the receiving transmission device is deleted from the route, and is output to the route setting mechanism 13.

In this output result, a branch has occurred in B which is a unicast transmission apparatus. In this way, in the prior art, a plurality of candidate devices are determined from the search target device using only the link cost without considering the difference between the multicast transmission device and the unicast transmission device. A route that branches in the transmission device is output (for example, see Non-Patent Document 1).
WIDE 2002 Internet Architecture 6th Lecture Materials http://www.soi.wide.ad.jp/class/20020022/materials_for_student/06/na-06.pdf (10 pages, 11 pages)

  In the technology shown above, a multicast route that minimizes the link cost from the transmitting transmission device to each receiving transmission device is calculated from the input topology information and route setting restriction conditions, and is output to the route setting mechanism. Can do.

  However, in the existing technology, in a communication network in which a multicast transmission device and a unicast transmission device are mixed, route calculation is performed without considering the difference between them. There is a problem that such a multicast route is output. As a result, the route setting mechanism cannot set the route normally and cannot communicate.

  The present invention has been made in view of the above points. Even in a communication network in which a multicast transmission apparatus and a unicast transmission apparatus are mixed, the link cost from the transmission transmission apparatus to each reception transmission apparatus is reduced, and the unicast transmission apparatus is reduced. An object of the present invention is to provide a multicast route calculation method and apparatus and program capable of outputting a multicast route that does not cause a branch in the cast transmission device, and a storage medium storing the multicast route calculation program.

  FIG. 1 is a diagram for explaining the principle of the present invention.

According to the present invention (Claim 1), in a communication network in which multicast transmission apparatuses and unicast transmission apparatuses are mixed, the Dijkstra multicast path calculation method is applied using the topology information and path setting constraint conditions of the input communication network. A multicast route calculation method for calculating a route,
An initial setting step (step 1) for storing information on the transmission transmission device in a visited device storage means for setting the already searched device as visited.
A multicast determination step (step 2) for determining whether the device to be searched is a multicast transmission device or a unicast transmission device with reference to topology information storage means storing topology information including connection relation and link cost;
In the multicast determination step, when the multicast determination means determines that the device is a unicast transmission device, the neighboring device is extracted based on the topology information, given a priority based on a predetermined condition, and the priority is the highest Unicast device candidate device determination step (step 3), in which the adjacent device is stored as a candidate device in the candidate device storage means, and the route from the transmission transmission device to the candidate device and the link cost are stored in the search route storage means;
When it is determined as a multicast transmission device in the multicast determination step,
When the neighboring device is extracted by the Dijkstra multicast route calculation method and the candidate device selected by referring to the candidate device storage means from among the neighboring devices is the candidate device already determined in the candidate device determining step for unicast device A multicast device that re-selects candidate devices from neighboring devices of the unicast transmission device, stores them in the candidate device storage means, and stores the route from the transmission transmission device to the candidate devices and the link cost in the search route storage means Candidate device determination step (step 4),
Search target device determination step for searching candidate devices with the lowest link cost from the transmission transmission device of each candidate device stored in the candidate device storage means from the candidate device storage means and storing in the visited storage means (step 5) When,
When the route from the transmission transmission device to all the reception transmission devices has been found with reference to the search route storage means (step 6, Yes), the transmission device stored in the search route storage means is read and output. (Step 7), and if not found (Step 6, No), perform a route completion determination step that repeats the steps after the multicast determination step,
In the unicast device candidate determination step (step 3),
Extracting neighboring devices based on the topology information, prioritizing from among the neighboring devices according to priority conditions, and setting the neighboring device that is the highest in the prioritization as a candidate device;
When the candidate device is a candidate device from another device or a searched device, the calculated link cost is compared with the link cost via the searched device, and the calculated link cost is small For the unicast transmission device, the process of reselecting the next higher device according to the priority condition is searched for a device that is not a searched device or a candidate device or a link cost that has already been calculated. Repeating until a device larger than the target device is found;
The selected device is stored in the candidate device storage means, and the route from the candidate device to the transmission transmission device and the link cost are stored in the search route storage means.

  FIG. 2 is a principle configuration diagram of the present invention.

According to the present invention (Claim 2), in a communication network in which a multicast transmission device and a unicast transmission device are mixed, the Dijkstra multicast route calculation method is applied to the multicast using the topology information and route setting constraint conditions of the input communication network. A multicast route calculation device for calculating a route,
Topology information storage means 112 storing topology information including the connection relationship and link cost of each device;
Constraint storage means 114 for storing route constraint conditions;
Visited device storage means 119 for storing already searched devices as visited devices;
Candidate device storage means 122 for storing candidate devices;
A search route storage means 120 for storing a route to each transmission transmission device and a link cost of each device;
Initial setting means 115 for storing information of the transmission device in the visiting device storage means;
Multicast determination means 116 for referring to the topology information in the topology information storage means and determining whether the search target device is a multicast transmission device or a unicast transmission device;
When the multicast determination means 116 determines that the device is a unicast transmission device, the neighboring device is extracted based on the topology information, given priority based on a predetermined condition, and the neighboring device with the highest priority is selected as a candidate. A candidate device determining unit 118 for a unicast device that stores the route from the transmission transmission device to the candidate device and the link cost in the search route storage unit 120 as a device stored in the candidate device storage unit 122;
When the multicast judging unit 116 judges that the device is a multicast transmission device, a neighboring device is extracted by the Dijkstra multicast route calculation method, and the candidate device selected by referring to the candidate device storage unit from the neighboring device is already a unicast device. If the candidate device is determined by the candidate device determining unit, the candidate device is reselected from the neighboring devices of the unicast transmission device, stored in the candidate device storage unit 122, and transmitted from the candidate device to the transmission transmission device. Multicast device candidate device determining means for storing the route and link cost to the search route storage means 120;
Search target device determination in which the candidate device with the lowest link cost from the transmission transmission device of each candidate device stored in the candidate device storage unit 122 is extracted from the candidate device storage unit 122 and stored in the visited device storage unit 119 Means,
If the route to all the receiving transmission devices is found with reference to the searched route storage means 120, the candidate device stored in the searched route storage means 120 is read out and output, and if not found, In a device having a multicast determination unit 116, a unicast device candidate device determination unit 118, a multicast device candidate device determination unit 117, and a route completion determination unit 123 that repeats the processing of the search target device determination unit 123.
A prioritization condition storage unit 141 that holds priority conditions based on the number of physical links, multicast transmission capability, and link cost;
Unicast device candidate device decision means 118
Extract neighboring devices based on the topology information, prioritize among the neighboring devices according to priority conditions, and determine the neighboring device that is the highest in the prioritization as a candidate device,
When the candidate device is a candidate device from another device or a searched device, the calculated link cost is compared with the link cost via the searched device, and the calculated link cost is small For the unicast transmission device, the process of reselecting the next higher device according to the priority condition is searched for a device that is not a searched device or a candidate device or a link cost that has already been calculated. Repeat until a device larger than the target device is found,
Means for storing the selected device in the candidate device storage means;
Have

According to the present invention (Claim 3), a computer having route restriction condition storage means, visited device storage means, candidate device storage means, and searched route storage means is provided.
A multicast route calculation program that functions as a multicast route calculation device having each means according to claim 2.

According to the present invention (Claim 4), a computer having route restriction condition storage means, visited device storage means, candidate device storage means, and searched route storage means is provided.
A storage medium storing a program that functions as a multicast route calculation apparatus having each means according to claim 2.

  As described above, according to the present invention, when a search is started from a transmission transmission device, and there is a unicast transmission device in the middle of the search, the branch is suppressed, the link cost is reduced, and the desired multicast is obtained. One route is determined by giving specific priorities so as to approach the solution of the route. As a result, the link cost from the transmission device to each reception device can be reduced, and a multicast route that does not branch at the unicast transmission device can be obtained.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 3 shows a configuration of a multicast route calculation apparatus according to an embodiment of the present invention.

  The multicast route calculation apparatus shown in the figure includes a topology information input unit 111, a topology information storage unit 112, a route constraint condition input unit 113, a constraint condition setting unit 114, an initial setting unit 115, a multicast determination unit 116, and a multicast device candidate device. Determination unit 117, unicast device candidate device determination unit 118, visited device storage unit 119, search route storage unit 120, route output unit 121, candidate device storage unit 122, search target device determination unit 123, multicast route completion determination unit 124, a prioritized condition storage unit 141. The topology information storage unit 112, the visited device storage unit 119, the searched route storage unit 120, the candidate device storage unit 122, and the prioritized condition storage unit 141 are storage media such as a hard disk device.

  The topology information input unit 111 inputs topology information including a connection relation of devices in the communication network and a link cost collected by a topology information collection mechanism (not shown) to the topology information storage unit 112.

  The route constraint condition input unit 113 inputs route setting constraint conditions such as a transmission transmission device, a reception transmission device, and a necessary band to the constraint condition setting unit 114.

  The constraint condition setting unit 114 sets the constraint conditions in the initial setting unit 115 and the multicast route completion determination unit 124.

  The initial setting unit 115 acquires information on the transmission transmission device from the route constraint condition input unit 113, sets it as a visited device in the visited transmission device storage unit 119, and passes it to the multicast determination unit 116.

  The multicast determination unit 116 refers to the topology information in the topology information storage unit 112 and determines whether the input device (search target device) is a multicast transmission device or a unicast transmission device. When it is determined that it is a unicast transmission device, it notifies the unicast device candidate determination unit 118, and when it is determined that it is a multicast transmission device, it notifies the multicast device candidate device determination unit 117.

  Candidate device determination unit 117 for multicast devices and candidate device determination unit 118 for unicast cast devices determine candidate devices by referring to information in visited device storage unit 119, searched route storage unit 120, and candidate device storage unit 122, respectively. Then, the determined candidate device is notified to the search route storage unit 120 and the candidate device storage unit 122.

  The visited device storage unit 119 stores the identifier of the search target device determined by the search target device determination unit 123 as visited.

  The search route storage unit 120 stores the route and link cost to the transmission transmission device of each device determined by the multicast device candidate device determination unit 117 or the unicast device candidate device determination unit 118.

  The candidate device storage unit 122 stores the identifier of the candidate device extracted by the multicast device candidate device determination unit 117 or the unicast device candidate device determination unit 118.

  The prioritization condition storage unit 141 stores prioritization conditions for minimizing the transfer link cost when the search target device is a unicast transmission device. The prioritization conditions are shown below.

1) A transmission apparatus having one physical link and a receiving transmission apparatus;
2) Transmission equipment with the smallest number of physical links;
3) Multicast transmission device among the above devices;
4) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus;
5) Unicast transmission device among the transmission devices of 2);
6) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus;
When the search target device is determined to be a unicast transmission device by the multicast determination unit 116, the candidate device determination unit 118 for the unicast device extracts an adjacent device of the search target device with reference to the topology information and is extracted. The adjacent devices are prioritized from among the adjacent devices by referring to the above-described priority conditions in the prioritized condition storage unit 141. One of the neighboring devices that is at the top in the priority order is set as a candidate device. Furthermore, when the candidate device is a candidate device from another device or a searched device, the calculated link cost is compared with the link cost via the search target device, and the already calculated link cost is small. Then, the next higher-level device is reselected according to the condition of the prioritization condition storage unit 141. The selected device is stored in the candidate device storage unit 122. Further, the search route storage unit 120 stores the route from the transmission transmission device to the candidate device and the link cost.

  When the multicast determination unit 116 determines that the multicast device candidate device determination unit 117 is a multicast transmission device, the multicast device candidate device determination unit 117 extracts neighboring devices by the Dijkstra multicast route calculation method, and searches the candidate device storage unit 122 from the adjacent devices. If the candidate device selected with reference to the path storage unit 120 is already a candidate device determined by the unicast device candidate device determination unit 118, the candidate device is reselected from the neighboring devices of the unicast transmission device. The identifier is stored in the candidate device storage unit 122. Further, the search route storage unit 120 stores the route from the transmission transmission device to the candidate device and the link cost.

  The search target device determination unit 123 examines the link cost from the transmission transmission device of each candidate device stored in the search path storage unit 120, and sets one of the candidate devices having the smallest link cost as the search target device. The device identifier is set in the visited device storage unit 119 and deleted from the candidate device storage unit 122.

  The multicast route completion determination unit 124 refers to the visited storage unit 119 based on the route stored in the searched route storage unit 120 based on the reception transmission device acquired from the constraint condition setting unit 114, and sets all reception transmission devices. It is determined whether or not a route to has been found. When the route is determined, the route output unit 121 is notified. Further, when the route is not found and the search target device is determined by the search target device determination unit 123, information on the device is passed to the multicast determination unit 116.

  The route output unit 121 outputs the route stored in the searched route storage unit 120 when notified from the multicast route completion determination unit 124 that routes to all the receiving transmission devices have been found.

  Next, the operation in the above configuration will be described.

  FIG. 4 is a flowchart of the operation in one embodiment of the present invention.

  Step 101) The topology information input unit 111 receives topology information and stores it in the topology information storage unit 112.

  Step 102) The route constraint condition input unit 113 sets the route constraint condition in the route condition setting unit 114.

  Step 103) The constraint condition setting unit 114 sets the transmission apparatus to the initial setting unit 115. Specifically, the visited transmission device is set as a visited device in the visited device storage unit 119. In addition, the transmission transmission device is set in the search route storage unit 120 as a search target device.

  Step 104) The multicast determination unit 116 refers to the topology information to determine whether the search target device is a multicast transmission device or a unicast transmission device. In the case of a multicast transmission apparatus, the process proceeds to step 105, and in the case of a unicast transmission apparatus, the process proceeds to step 108.

  Step 105) The multicast device candidate device determination unit 117 extracts neighboring devices from the topology information storage unit 112.

  Step 106) The multicast device candidate device determination unit 117 determines a candidate device from the neighboring devices acquired in Step 105 by the Dijkstra multicast route calculation method, and stores it in the candidate device storage unit 122. Further, the search route storage unit 120 stores the route from the transmission transmission device to the candidate device and the link cost.

  Step 107) The search path storage unit 120 determines where the candidate device is from, and refers to the candidate device storage unit 122 to determine whether the original device is unicast or multicast. Then, if the acquired candidate device is already a candidate device determined by the unicast device candidate device determination unit 118, the process proceeds to step 108; otherwise, the process proceeds to step 111.

  Step 108) When it is determined in Step 104 that the search target device is a unicast transmission device, or when the device is already determined by the unicast device candidate device determination unit 118 in Step 107 The candidate device determination unit 118 for unicast devices extracts the neighboring device of the device with reference to the topology information and stores it in the memory.

  Step 109) The candidate device determining unit 118 for the unicast device gives a priority to the adjacent device stored in the memory based on a predetermined condition of the prioritization condition storage unit 141.

  Step 110) The candidate device determination unit 118 for the unicast device stores the neighboring device having the highest priority in the candidate device storage unit 122 as a candidate device. Further, the route from the transmission transmission device to the candidate device and the link cost are stored in the searched route storage unit 120.

  Step 111) It is determined whether the candidate device determined in Step 110 is a candidate device from another unicast transmission device with reference to the candidate device storage unit 122 and the search route storage unit 120. 108. Otherwise, the process proceeds to step 112.

  Step 112) In the search target device determination unit 123, the candidate device is read from the candidate device storage unit 122, and one of the candidate devices having the lowest link cost from the transmission transmission device of each candidate device stored in the search path storage unit 120. The search target device is stored in the visited device storage unit 119 and deleted from the candidate device storage unit 122.

  Step 113) The multicast route completion determination unit 124 refers to the visited storage unit 119 based on the route stored in the searched route storage unit 120 based on the reception transmission device acquired from the constraint condition setting unit 114, It is determined whether a route to the receiving transmission device has been found. When the route is determined, the route output unit 121 is notified. As a result, the route output unit 121 outputs the route stored in the searched route storage unit 120 when notified from the multicast route completion determination unit 124 that the route to all the receiving transmission devices has been found. . Further, when the route is not found and the search target device is determined by the search target device determination unit 123, information on the device is passed to the multicast determination unit 116.

  Next, the processing after step 104 will be described in detail.

  5 to 10 are flowcharts of detailed operations in one embodiment of the present invention.

  Step 201) The initial setting unit 115 sets the transmission transmission device (s) as a visited device in the visited device storage unit 119 and sets it as a search target transmission device (v). Here, the search target transmission apparatus usually refers to a transmission apparatus whose path has just been determined.

  Step 202) The multicast determination unit 116 determines whether the search target transmission device is a multicast transmission device. If the transmission target device is a multicast transmission device, the multicast determination unit 116 proceeds to Step 203, and if it is a unicast transmission device, proceeds to Step 214. To do.

  Step 203) The multicast device candidate device determination unit 117 sets the transmission device f as a transmission device that is adjacent to the search target transmission device and is not the transmission device immediately preceding the search target transmission device on the determined path. If there is no candidate device, it is not executed.

[Process 1: Step 204]
Step 204) The multicast device candidate device determination unit 117 calculates a link cost between the transmission device (s) to be transmitted via the search target transmission device (v) and the determined candidate device (f), and sets it as df.

  Step 205) The multicast device candidate device determination unit 117 refers to the visited device storage unit 119 and the candidate device storage unit 122, and the candidate device (f) is a visited device or a candidate device of another device. If it is neither a visited apparatus nor a candidate apparatus of another apparatus, the process proceeds to step 206. If it is a visited apparatus or a candidate apparatus of another apparatus, the process proceeds to step 207. .

[Process 2: Step 206]
Step 206) The route and link cost via the search target transmission device (v) from the transmission transmission device (s) to the transmission device (f) are stored in the search route storage unit 120, and the transmission device (f) is set as a candidate device. Control goes to step 213.

  Step 207) It is determined whether the already calculated link cost is greater than the df obtained in Step 204. If it is larger, the process proceeds to Step 208. Otherwise, the process proceeds to Step 213.

  Step 208) Let p be the transmission apparatus immediately preceding the candidate apparatus (f) in the stored path.

  Step 209) The same processing [processing 2] as step 206 is performed.

  Step 210) The multicast determination unit 116 determines whether p is a multicast transmission apparatus. If the multicast transmission apparatus 116 is a multicast transmission apparatus, the process proceeds to step 213. If not, the process proceeds to step 211.

  Step 211) The candidate device determining unit 118 for the unicast device sets p as the search target transmission device (v).

  Step 212) The processing from Step 214 to Step 221 [Process 3] is performed, and the routine proceeds to Step 213.

  Step 213) Steps 203 to 213 are executed for all f.

[Process 3: Step 214 to Step 217]
Step 214) The candidate device determining unit 118 for the unicast device sets (f) as a transmission device adjacent to the search target transmission device (v).

  Step 215) The candidate device determining unit 118 for the unicast device determines whether or not there is a plurality of f. If there are f, the process proceeds to Step 216. If not, the process proceeds to Step 219.

  Step 216) The unicast candidate device determining unit 118 uses the priority condition of the next priority condition storage unit 141 to set one of the transmission devices with the highest priority as f.

1) A transmission apparatus having one physical link and a receiving transmission apparatus;
2) Transmission equipment with the smallest number of physical links;
3) Multicast transmission device among the above devices;
4) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus (s);
5) Unicast transmission device among the transmission devices of 2);
6) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus (s);
In the above priority condition, when there are a plurality of highest-level transmission devices, the number is limited to one using another route setting restriction condition set by the restriction condition setting unit 114.

  Step 217) The process [Process 4] (Step 301 to Step 310) shown in FIG. 9 is performed.

  Step 218) In step 215, if there is not a plurality of f and one f exists, the process proceeds to step 219. Otherwise (zero f), the process proceeds to step 221.

  Step 219) The above-mentioned step 204 [Process 1] is performed.

  Step 220) The process of Step 206 [Process 2] is performed, and the process proceeds to Step 221.

  Step 221) The search target device determination unit 123 determines whether there is a candidate device in the candidate device storage unit 122. If there is a candidate device, the search target device determination unit 123 proceeds to Step 222. Force termination.

  Step 222) The search target device determination unit 123 sets i as a candidate device that minimizes the link cost from the transmission device (s). When there are a plurality of conditions, one is selected using the other conditions set from the constraint condition setting unit 114. A route to the i is determined, i is deleted from the candidate device storage unit 122, and i is set in the visited device storage unit 119.

  Step 223) Let i be the search target transmission device (v).

  Step 224) The multicast route completion determination unit 124 refers to the searched route storage unit 120 to determine whether all the receiving transmission devices are included in the determined route. If included, the process proceeds to Step 225. If not included, the process proceeds to step 202.

  Step 225) The route that does not communicate with the receiving device in the searched route storage unit 120 is deleted, and the determined route is output from the route output unit 121.

[Process 4: Step 301 to Step 310]
Step 301) Step 204 [Process 1] is performed.

  Step 302) It is determined whether the candidate device f is a visited device or a candidate device of another device with reference to the visited device storage unit 119 and the candidate device storage unit 122, and not the visited device. If it is not a candidate device of another device, the process proceeds to step 303. If it is a visited device or a candidate device of another device, the process proceeds to step 304.

  Step 303) Step 206 [Process 2] is performed, and the routine proceeds to Step 221.

  Step 304) It is determined whether the already calculated link cost is greater than the df obtained in Step 204. If so, the process proceeds to Step 306. Otherwise, the process proceeds to Step 305.

  Step 305) Reselect another neighboring device according to the priority order, and proceed to Step 216.

  Step 306) Let p be the previous transmission device of f in the route stored in the candidate device storage unit 122.

  Step 307) Step 206 [Process 2] is performed.

  Step 308) The multicast determination unit 116 determines whether the transmission device p is a multicast transmission device. If the transmission device p is a multicast transmission device, the process proceeds to step 221, and if it is a unicast transmission device, the process proceeds to step 309.

  Step 309) The transmission device p is set as a search target device v.

  Step 310) The processing of Step 214 to Step 217 [Process 3] is performed, and the routine proceeds to Step 221.

  Embodiments of the present invention will be described below with reference to the drawings.

  11-13 is a figure for demonstrating the Example of this invention.

  The topology information including the connection relationship and link cost shown in FIG. 11A and the path constraint conditions such as the transmission transmission device and the reception transmission device are received and stored in the topology information storage unit 112 and the constraint condition storage unit 114. Shall.

In addition, the prioritized condition storage unit 141 includes:
1) A transmission apparatus having one physical link and a receiving transmission apparatus;
2) Transmission equipment with the smallest number of physical links;
3) Among the above devices, a multicast transmission device;
4) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus;
5) Unicast transmission device among the transmission devices of 2);
6) Among the above transmission apparatuses, the transmission apparatus with the lowest link cost from the transmission transmission apparatus;
It is assumed that the condition is set.

  (1) The initial setting unit 115 sets the transmission transmission device A as a visited device and sets it in the visited device storage unit 119. The multicast determination unit 117 determines whether the transmission transmission device is a multicast transmission device or a unicast transmission device. Judging.

  (2) In this topology, since the transmission transmission device is a multicast transmission device, the multicast device candidate device determination unit 117 calculates the link cost to the adjacent transmission devices B and I with reference to the topology information, The route and the link cost are stored in the search route storage unit 120, and B and I are set as candidate devices and set in the candidate device storage unit 122 (FIG. 11B).

  (3) The search target device determination unit 123 refers to the information on the link cost of the topology information, and selects one candidate device with the lowest link cost from the transmission transmission device from among the candidate devices in the candidate device storage unit 122. The selected device is deleted from the candidate device storage unit 122 and set in the visited storage unit 119. At this time, if there are a plurality of candidate devices having the lowest link cost, one is selected using other route setting restriction conditions. In this topology, B having a link cost of “2” is selected, deleted from the candidate device storage unit 122, a route from the transmission transmission device to B is determined, and the route is set in the search route storage unit 120. The device B is set in the visited device storage unit 119.

  (4) The multicast determination unit 116 determines whether the determined transmission device B is a multicast transmission device or a unicast transmission device. In FIG. 11, since the transmission device B is a multicast device, the multicast device candidate device determination unit 117 calculates the link cost to the adjacent transmission devices C, F, and G and sets it as a candidate device (FIG. 14 ( c)).

  (5) The multicast device candidate device determination unit 117 selects the candidate device with the lowest link cost from the transmission transmission device A and deletes it from the candidate device storage unit 122. As a result, a route to the transmission device I is determined and set in the searched route storage unit 120, and I is set as a search target device and stored as a visited device in the visited device storage unit 119.

  (6) The multicast determination unit 116 determines whether the search target device I is a multicast transmission device or a unicast transmission device. In FIG. 11, since I is a unicast transmission device, from among transmission devices adjacent to each other (however, when referring to an adjacent transmission device, the previous transmission device in the searched route is not included), Using the priority condition stored in the prioritized condition storage unit 141, the transmission apparatus with the highest priority is set as a candidate apparatus (FIG. 12 (d)).

  In addition, in the priority condition of the prioritized condition storage unit 141, when there are a plurality of highest-level transmission apparatuses, the number is limited to one using other route setting restriction conditions. In this topology, there are two transmission apparatuses E and H adjacent to the transmission apparatus I, but there is no transmission apparatus that satisfies the above-mentioned priority condition 1), and the transmission apparatus that satisfies the condition 2) is H. Therefore, H is a candidate device.

  (7) G is selected as a search target device from among candidate devices, a route to G is determined, set in the search route storage unit 120, and G is deleted from the candidate device storage unit 122. Also, G is a visited device, and is stored in the visited device storage unit 119.

  (8) Since the transmission device G is a multicast transmission device, the multicast device candidate device determination unit 117 calculates the link cost to the adjacent transmission devices (H, F) and is smaller than the already calculated link cost. H is a candidate device.

  (9) Since the transmission apparatus H is a candidate apparatus from the transmission apparatus I and the transmission apparatus I is a unicast transmission apparatus, the candidate apparatus is reselected for I. As a result, the transmission device E is set as a candidate device (FIG. 12 (e)).

  (10) Among the candidate devices, the transmission device F is set as a search target device, a route to F is determined, set in the search route storage unit 120, and the transmission device F is deleted from the candidate device storage unit 122. Further, the transmission device is stored in the visited device storage unit 119 as a visited device.

  (11) Since the transmission apparatus F is a unicast transmission apparatus, the unicast apparatus candidate apparatus determination unit 118 selects one candidate apparatus according to the prioritization condition of the prioritization condition storage unit 141. G is selected according to the above condition 2), but since the link cost increases, E, which is the next order, is selected. Since E has a low link cost, E is a candidate device.

  (12) Since E is a candidate device from I and I is a multicast transmission device, the candidate device for I is reselected. However, no candidate device for I is selected because the link cost does not decrease (FIG. 12 (f)).

  (13) H is selected as a search target device from among candidate devices, a route to H is determined, stored in the search route storage unit 120, and deleted from the candidate device storage unit 122. Further, H is stored in the visited device storage unit 119 (FIG. 13 (g)).

  (14) Similarly, C and D routes are determined and stored in the searched route storage unit 120 (FIG. 13 (h)).

  (15) From the calculated routes, unnecessary routes that do not reach the receiving transmission devices C, D, and G are deleted from the searched route storage unit 120. The route output unit 121 outputs the contents of the searched route storage unit 120 to a route setting mechanism (not shown) (FIG. 13 (i)).

  Note that the initial setting unit 115, multicast determination unit 116, multicast device candidate device determination unit 117, unicast device candidate device determination unit 118, search target device determination unit 123, multicast path completion determination unit 124, path output unit It is also possible to construct the operation 121 as a program, install it on a computer used as a multicast route calculation apparatus, execute it, or distribute it via a network.

  In addition, the constructed program can be stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM, and can be installed in a computer or distributed.

  The present invention is not limited to the above-described embodiments and examples, and various modifications and applications can be made within the scope of the claims.

  The present invention is applicable to a technique for setting a multicast route for a communication network in which a multicast transmission apparatus and a unicast transmission apparatus are mixed, such as the MPLS technique.

It is a figure for demonstrating the principle of this invention. It is a principle block diagram of this invention. It is a block diagram of the multicast route calculation apparatus in one embodiment of this invention. It is a flowchart of the multicast route calculation method in one embodiment of this invention. It is a flowchart (the 1) of the detailed operation | movement in one embodiment of this invention. It is a flowchart (the 2) of the detailed operation | movement in one embodiment of this invention. It is a flowchart (the 3) of the detailed operation | movement in one embodiment of this invention. It is a flowchart (the 4) of the detailed operation | movement in one embodiment of this invention. It is a flowchart (the 5) of the detailed operation | movement in one embodiment of this invention. It is a flowchart (the 6) of the detailed operation | movement in one embodiment of this invention. It is FIG. (1) for demonstrating one Example of this invention. It is FIG. (2) for demonstrating one Example of this invention. It is FIG. (3) for demonstrating one Example of this invention. It is a figure for demonstrating the conventional multicast route calculation apparatus. It is FIG. (1) for demonstrating a prior art. It is FIG. (2) for demonstrating a prior art. It is FIG. (3) for demonstrating a prior art.

Explanation of symbols

111 Topology Information Input Unit 112 Topology Information Storage Unit, Topology Information Storage Unit 113 Path Restriction Condition Input Unit 114 Restriction Condition Storage Unit, Restriction Condition Setting Unit 115 Initial Setting Unit, Initial Setting Unit 116 Multicast Determination Unit, Multicast Determination Unit 117 Multicast Device Candidate apparatus determining means, multicast apparatus candidate apparatus determining section 118 Unicast apparatus candidate apparatus determining means, unicast apparatus candidate apparatus determining section 119 Visited apparatus storage means, visited apparatus storage section 120 Search path storage means, search Route storage unit 121 Route output unit 122 Candidate device storage unit, candidate device storage unit 123 Search target device determination unit, search target device determination unit 124 Route completion determination unit, multicast route completion determination unit 141 Prioritizing condition storage unit, prioritization condition Memory

Claims (4)

A multicast route calculation method that calculates a multicast route by applying the Dijkstra multicast route calculation method using the topology information and route setting constraint conditions of the input communication network in a communication network in which multicast transmission devices and unicast transmission devices are mixed. There,
An initial setting step of storing information on the transmission transmission device in a visited device storage means for setting the already searched device as visited.
A multicast determination step for determining whether the device to be searched is a multicast transmission device or a unicast transmission device with reference to topology information storage means storing topology information including connection relation and link cost;
In the multicast determination step, when the multicast determination unit determines that the device is a unicast transmission device, an adjacent device is extracted based on the topology information, a priority is assigned based on a predetermined condition, and the priority is Unicast device candidate device determination step of storing the highest-level neighboring device as a candidate device in the candidate device storage means, and storing the path and link cost from the transmission transmission device to the candidate device in the search route storage means;
When it is determined as a multicast transmission device in the multicast determination step,
The candidate device extracted by the Dijkstra multicast route calculation method and selected from the neighboring devices by referring to the candidate device storage means is a candidate device that has already been determined in the candidate device determination step for the unicast device. If there is, the candidate device is reselected from the neighboring devices of the unicast transmission device, stored in the candidate device storage means, and the path and link cost from the transmission transmission device to the candidate device are stored in the search route storage. A candidate device determination step for multicast device to be stored in the means;
A search target device determination step of searching the candidate device storage means for a candidate device having a minimum link cost from the transmission transmission device of each candidate device stored in the candidate device storage means, and storing the searched candidate device in the visited storage means;
When the route from the transmission transmission device to all reception transmission devices is found with reference to the searched route storage means, the transmission device stored in the search route storage means is read out and output, and found. If not, a route completion determination step that repeats the steps after the multicast determination step is performed,
In the unicast device candidate determination step,
Extracting neighboring devices based on the topology information, prioritizing the neighboring devices from the neighboring devices according to the priority conditions, and setting the neighboring device that is the highest in the prioritization as a candidate device;
When the candidate device is a candidate device from another device or a searched device, the calculated link cost is compared with the link cost via the searched device, and the calculated link cost is small For the unicast transmission device, the process of reselecting the next higher device according to the priority condition is searched for a device that is not a searched device or a candidate device or a link cost that has already been calculated. Repeating until a device larger than the target device is found;
Storing the selected device in the candidate device storage means, and storing the route from the candidate device to the transmission transmission device and the link cost in the search route storage means. A multicast route calculation device that calculates a multicast route by applying a Dijkstra multicast route calculation method using topology information and route setting constraint conditions of the input communication network in a communication network in which a multicast transmission device and a unicast transmission device are mixed. There,
Topology information storage means storing topology information including the connection relationship and link cost of each device;
Constraint storage means for storing route constraint conditions;
Visited device storage means for storing already searched devices as visited devices;
Candidate device storage means for storing candidate devices;
Search route storage means for storing the route and link cost to the transmission transmission device of each device,
Initial setting means for storing information on the transmission device in the visiting device storage means;
Multicast determination means for referring to the topology information in the topology information storage means and determining whether the search target device is a multicast transmission device or a unicast transmission device;
When the multicast determination means determines that the device is a unicast transmission device, it extracts neighboring devices based on the topology information, assigns priority based on a predetermined condition, and selects the neighboring device with the highest priority. Unicast device candidate device determining means for storing in the candidate device storage means as a candidate device, and storing the route from the transmission transmission device to the candidate device and the link cost in the search route storage means;
When the multicast determination unit determines that the device is a multicast transmission device, an adjacent device is extracted by the Dijkstra multicast route calculation method, and the candidate device selected by referring to the candidate device storage unit from the adjacent device is already If the candidate device is determined by the unicast device candidate device determining means, the candidate device is reselected from the adjacent devices of the unicast transmission device, stored in the candidate device storage means, and the candidate device. A candidate device determining unit for multicast device that stores the route from the transmission device to the transmission device and the link cost in the searched route storage unit;
Search target device determination for extracting a candidate device having the lowest link cost from the transmission transmission device of each candidate device stored in the candidate device storage means from the candidate device storage means and storing it in the visited device storage means Means,
If the route to all the receiving transmission devices is found with reference to the searched route storage means, the candidate device stored in the searched route storage means is read and output, and if not found, In a device having multicast determination means, unicast device candidate device determination means, multicast device candidate device determination means, and route completion determination means for repeating the search target device determination means,
Prioritization condition storage means for holding priority conditions based on the number of physical links, multicast transmission capability, and link cost,
The unicast device candidate device determining means includes:
Extract neighboring devices based on the topology information, prioritize among the neighboring devices according to the priority condition, and the neighboring device that is the highest in the prioritization as a candidate device,
When the candidate device is a candidate device from another device or a searched device, the calculated link cost is compared with the link cost via the searched device, and the calculated link cost is small For the unicast transmission device, the process of reselecting the next higher device according to the priority condition is searched for a device that is not a searched device or a candidate device or a link cost that has already been calculated. Repeat until a device larger than the target device is found,
Means for storing the selected device in the candidate device storage means;
A multicast route calculation apparatus characterized by comprising: A computer having route restriction condition storage means, visited device storage means, candidate device storage means, and searched route storage means,
A multicast route calculation program that functions as a multicast route calculation device having each means according to claim 2. A computer having route restriction condition storage means, visited device storage means, candidate device storage means, and searched route storage means,
A storage medium storing a multicast route calculation program characterized by storing a program that functions as a multicast route calculation device having each means according to claim 2.

Images