JP4533354B2 - Route calculation method, route calculation program, and route calculation device - Google Patents

Description

  The present invention relates to a route calculation technique when an inclusive route is designated.

  In recent years, audio / video streaming services have become widespread with the increase in network speed and capacity. Applications that provide these services need to be provided with QoS (Quality of Service) restrictions and sufficient bandwidth in order to prevent quality degradation due to delay and packet loss.

  Here, a server or router in the network is equipped with a Constrained Shortest Path First (CSPF) function in order to set up a route that can efficiently use a limited bandwidth and support the required QoS. . The CSPF function is a function that calculates a path of a path that satisfies a constraint based on a request from the outside such as a module that exchanges signaling information, and answers the path to the outside, that is, a shortest path with a constraint (link This is a function for calculating a route with the lowest cost. In addition, as a CSPF algorithm which implement | achieves such a CSPF function, there exists a dijkstra algorithm (refer nonpatent literature 1).

Here, for effective use of limited network resources, QoS control, or operational convenience of the operator, there are cases where a location that should always be passed at the time of path setting is specified (inclusive route specification). When performing route calculation in consideration of this inclusive route specification, the start node and specified node (node with inclusive route specification) 1, specified node 1 and specified node 2, and so on, specified node N and end node, and so on The route is calculated independently for each section, and the end-to-end route is obtained by adding the routes at the end.
Dijkstra's algorithm, [online], [searched August 20, 2006], Internet, <URL: http://en.wikipedia.org/wiki/Dijkstra's_algorithm>

  However, in the route calculation, when the above-mentioned inclusive route is specified, if an attempt is made to find the shortest route using only the dijkstra algorithm for each section, route overlap occurs from the start node to the end node. There is a case. This problem will be described with reference to FIG.

  Normally, a value called a metric is used in route calculation. The metric is a cost (link cost) given to each link in the network, and the basis of the CSPF is to find (calculate) a route that minimizes the sum of the link costs. In the network illustrated in FIG. 7, when the node 2C is selected as an inclusive node (relay node), the route calculation device 6 calculates (searches) the shortest route using only the dijkstra algorithm described above. A node 2A → node 2B → node 2C → node 2B → node 2D (solid line route) with a small sum is found. However, since the route from the node 2B to the node 2C and the route from the node 2C to the node 2B overlap in this route, the route calculation device 6 cannot set the path to this route.

  That is, in order for the route calculation device 6 to set a path, it is necessary to select a route having no route overlap, for example, a route of node 2A → node 2B → node 2C → node 2D in FIG. . Further, when there are a plurality of combinations of routes that do not have overlapping routes as in the network illustrated in FIG. 7, it is preferable in terms of route setting to select a route having a link cost as low as possible.

  Therefore, the present invention provides a means for solving the above-described problems and calculating a route that has no route overlap and has a link cost that is as small as possible when the inclusive route is specified. For the purpose.

  In order to solve the above-described problems, the invention according to claim 1 stores an input / output unit that controls input / output of various data, topology information of nodes constituting a network, and link cost information of links connecting the nodes. A route calculation device comprising: a storage unit that performs a route calculation with reference to the topology information and the link cost information, and a route from a start node to an end node in the network via the input / output unit A relay node input step that receives input of identification information of a relay node that is routed through, a section division step that divides a route from the start node to an end node by the relay node into a plurality of sections, and the link cost information is referred to Then, for each of the divided sections, calculate the shortest path that minimizes the link cost in the section, A route calculation step for storing the calculated shortest route for each section in the storage unit, a first route overlap determination step for determining whether or not there is a route overlap between the shortest routes, and the first route In the overlap determination step, when there is a route overlap between the shortest routes, the topology information is referred to, a possible route candidate for each section is calculated, and the calculated route candidate for each section is stored in the memory A route candidate calculation step to be stored in the section, and from the storage section, the route candidates in each of the sections where the route duplication is found are read, and among the read route candidates, the sections in which the route duplication is found, A combination of routes having no route overlap is searched, a combination of routes having the lowest link cost is selected from the combination of routes having no route overlap, and the route overlap is selected. There the path of the found segment, and a route computation method to perform a route combination search step of outputting by replacing the selected route.

  According to this route calculation method, the route calculation device can calculate a route that has no route overlap and has a minimum link cost when a relay node is specified by specifying an inclusive route.

  According to a second aspect of the present invention, in the route combination search step of the route calculation method according to the first aspect, a section in which the path candidate is replaced with a path from among sections in which the path duplication is found is provided. Selecting, reading out the route candidates in the selected section from the storage unit, selecting the read out route candidates in ascending order of the link cost, replacing the route in the section with the selected route candidate, and overlapping the route This is a route calculation method for searching for a combination of routes that does not overlap with other sections where is found.

  According to this route calculation method, the route calculation device first selects a section in which a route is to be replaced in a section where a route overlap is found. Then, the route calculation device replaces the route with the route candidate route in order from the one with the lowest link cost for the selected section, and searches for a route that does not overlap with another section in which route overlap is found. Therefore, when the relay node is designated by the inclusive route designation, the route calculation apparatus can calculate a route with a small calculation amount, no route duplication, and as low a link cost as possible.

  According to a third aspect of the present invention, in the route combination selection step of the route calculation method according to the second aspect of the present invention, the route replacement route is a route that is selected in order from the route with the largest number of route candidates in the route. The calculation method was used.

  According to this route calculation method, the route calculation device performs route replacement in order from the section with the largest number of route candidates, so that it is easy to find a route having no route overlap.

  According to a fourth aspect of the present invention, in the route combination search step of the route calculation method according to the second aspect, the sections to be replaced are selected in order from the section with the highest link cost of the shortest path in the section. The route calculation method is used.

  According to this route calculation method, since the route calculation device performs route replacement in order from the section with the highest link cost, it is easy to find a route without route overlap. For example, when this link cost is calculated using the number of hops in the section, there is a high possibility that a section with a high link cost is a section with a large number of hops. That is, there is a high possibility that the number of route candidates is large. Therefore, if the route calculation device performs route replacement in order from the section with the highest link cost in this way, it becomes easier to find a route with no route overlap.

  According to a fifth aspect of the present invention, in the route calculation method according to the second aspect, an input of a penalty cost for each section is received via the input / output unit, and the inputted penalty cost for each section is received. Further, a penalty cost input step is stored in the storage unit, and in the route combination selection step, the section in which the route is replaced is a route calculation method that selects in order from the section with the highest penalty cost in the section. .

  According to this route calculation method, an operator or the like of this route calculation device can input a penalty cost to cause the route calculation device to execute route replacement in order from the section desired by the operator.

  The invention described in claim 6 is a section other than the section in which the route replaced in the route combination search step of the route calculation method according to any one of claims 1 to 5 has found the route overlap. A second route duplication determination step for determining whether or not the route overlaps with a route in the second route duplication determination step, wherein in the second route duplication determination step, the replaced route is a section other than the section in which the route duplication is found. When it is determined that the route overlaps with a route in the section, the route combination searching method is performed again for the section in which the route is determined to overlap.

  According to this route calculation method, route overlap between sections where route overlap was found in the first calculation has been resolved, but if route overlap occurs with other sections, the route is re-routed to that section. Search for non-overlapping routes. Therefore, the route calculation apparatus can find a route having no route overlap in the entire section from the start node to the end node. This route calculation method is particularly effective when there are three or more sections delimited by the relay node.

  The invention according to claim 7 is a route calculation program that causes the route calculation apparatus, which is a computer, to execute the route calculation method according to any one of claims 1 to 6.

  According to this route calculation program, the computer can function as a route calculation device.

  According to an eighth aspect of the present invention, there is provided a storage unit that stores topology information of nodes constituting a network and link cost information of links connecting the nodes, and a route from a start point node to an end point node in the route in the network. The relay node input unit that receives input of identification information of the relay node that passes through, the section dividing unit that divides the route from the start node to the end node by the relay node into a plurality of sections, and the link cost information For each of the divided sections, the shortest path that minimizes the link cost in the section is calculated, and the shortest path for each calculated section is stored in the storage unit; and the shortest paths In the route overlap determination unit that determines whether there is route overlap, and in the route overlap determination unit, the shortest route When it is determined that there is a duplicate, referring to the topology information, a possible route candidate for each section is calculated, and the calculated route candidate for each section is stored in the storage unit; From the storage unit, route candidates in each of the sections where the route overlap is found are read, and a combination of routes having no route overlap is searched from the read route candidates in the sections where the route overlap is found. Then, the route combination that selects the route combination that minimizes the link cost from among the route combinations that do not have the route overlap, replaces the route of the section in which the route overlap is found with the selected route, and outputs the route combination. And a route calculation device including a search unit.

  According to this route calculation apparatus, when a relay node is designated by inclusive route designation, it is possible to calculate a route having no route overlap and having a minimum link cost.

  A ninth aspect of the present invention is the route calculation apparatus according to the eighth aspect, wherein the route combination search unit replaces the route candidate with a route in the route where the route overlap is found. The route candidate in the selected section is read from the storage unit, the read route candidates are selected in ascending order of the link cost, the route in the section is replaced with the selected route candidate, and the route is selected. It was set as the structure which searches the combination of the path | route which does not overlap with the other area where duplication was discovered.

  According to this route calculation apparatus, it is possible to find a route with a small calculation amount, no route overlap, and a link cost as low as possible.

  According to a tenth aspect of the present invention, in the route calculation device according to the eighth or ninth aspect, the route combination search unit converts the route candidate from the section where the route overlap is found to the route candidate route. The section to be replaced is selected, the route candidates in the selected section are read from the storage unit, the read route candidates are selected in ascending order of the link cost, and the route in the section is selected as the selected route candidate. The configuration is such that a combination of routes that do not overlap with other sections in which the route overlap is found is searched for.

  According to this route calculation device, it is possible to find a route having no route overlap in all sections from the start node to the end node. This route calculation method is particularly effective when there are three or more sections delimited by the relay node.

  According to the present invention, when a relay node is specified by specifying an inclusive route, it is possible to calculate a route that has no route overlap and that has a minimum link cost. Therefore, it becomes easy for a network administrator or the like to set a desired route.

  Hereinafter, the best mode for carrying out the present invention (hereinafter referred to as an “embodiment”) will be described by dividing it into a first embodiment and a second embodiment.

<< First Embodiment >>
First, the route calculation apparatus according to the first embodiment of the present invention will be described. This route calculation device searches for a combination of routes having no route overlap when a route overlap is found in the shortest route in the section delimited by the inclusive route designation. And among the searched route combinations, a route combination with the lowest link cost is output as a calculation result.

  FIG. 1 is a diagram illustrating a configuration example of a network including a route calculation apparatus according to an embodiment of the present invention. As shown in FIG. 1, the network includes a node 2 (2A, 2B, 2C, 2D) and a route calculation device 1 that performs route calculation of a path set between the node 2 and the network. The node 2 and the route calculation apparatus 1 are connected to be communicable. The route calculation device 1a will be described in the section of the second embodiment.

  In addition, this network is realized by circuit switching networks such as TDM (Time Division Multiplexing) and WDM (Wavelength Division Multiplexing), or by IP (Internet Protocol), Ethernet (registered trademark), MPLS (Multi-Protocol Label Switching). The The node 2 is realized by an MPLS router of an MPLS network, a router of a packet network, an optical cross-connect of an optical network, and the like, and has a function of setting a path based on a path setting command from the route calculation device 1.

<Overview of operation>
Here, an outline of the operation of the route calculation apparatus 1 will be described with reference to FIG. First, the route calculation device 1 inputs identification information of a node (node 2C) that becomes a relay node in a route from an origin node (node 2A) to an end node (node 2D) from an input device (not shown) or the like. Accept. In other words, it accepts an input of a node (inclusive node) to be routed in inclusive route specification.

  Receiving this input, the route calculation apparatus 1 divides the section from the node 2A to the node 2D into a section # 1 from the node 2A to the node 2C and a section # 2 from the node 2C to the node 2D.

  Then, when the route calculation device 1 calculates a route (shortest route) having a minimum sum of costs (link costs) among the routes that can be taken in each of the sections # 1 and # 2, the node 2A → the node 2B → the node 2C → Node 2B → node 2D (solid line route), but in this route, node 2B → node 2C and node 2C → node 2B overlap.

  Therefore, in the network illustrated in FIG. 1, the route calculation device 1 has (1) node 2A → node 2B → node 2C (link cost = 2) and (2) node 2A → node as route candidates in section # 1. Calculate that there is a 2C (link cost = 5) path. Also, it is calculated that there are (3) node 2C → node 2B → node 2D (link cost = 2) and (4) node 2C → node 2D (link cost = 3) as route candidates of section # 2. . Then, the route calculation apparatus 1 selects a combination having no link overlap and having the lowest link cost among the combinations of these routes. For example, a combination of routes having no route overlap from the node 2A to the node 2D and the sum of link costs in the combination are as shown in Table 1 below.

  In such a case, the route calculation device 1 sets the route with the smallest sum of link costs, that is, for the section # 1, (1) the route of node 2A → node 2B → node 2C, and for the section # 2, ( 4) Select a combination of paths such as the node 2C → node 2D. Then, the route calculation device 1 outputs this route as a route result. By doing in this way, the route calculation apparatus 1 can set a route with no link overlap and a link cost as low as possible in the route from the node 2A to the node 2D.

<Configuration of route calculation device>
Next, the configuration of the route calculation apparatus 1 will be described in detail with reference to FIG. FIG. 2 is a block diagram showing the configuration of the route calculation apparatus of FIG.

  As illustrated in FIG. 2, the route calculation device 1 includes an input / output unit 11, a processing unit 12, a storage unit 13, and a communication unit 14.

  The input / output unit 11 is an interface such as an input device (not shown) such as a keyboard and a mouse connected to the path calculation device 1 and an output device (not shown) such as a liquid crystal monitor. The input / output unit 11 outputs information input from the input device to the processing unit 12 and outputs information processed by the processing unit 12 to the output device. The input / output unit 11 includes a relay node input unit 111. The relay node input unit 111 receives input of identification information of a relay node (inclusive node). Note that the input of the identification information of the relay node is performed by, for example, the input device described above.

  The processing unit 12 controls the entire route calculation apparatus 1, and controls the input / output unit 11, the communication unit 14, and the storage unit 13, and processes input information.

  The processing unit 12 includes a section dividing unit 121 that divides a route from a start node to an end node by a relay node, a route calculation unit 122 that calculates (searches) a shortest route in each section, and a route overlap for each section. A route duplication determination unit 123 that determines whether or not there is a route, a route candidate calculation unit 124 that calculates a route candidate in each section, a route combination search unit 125 that searches for a combination of routes in each section, and the link cost of each node 2 A routing information acquisition unit 126 that acquires routing information such as topology information, and a path control unit 127 that outputs a path setting command based on the calculated route to the node 2.

  When the section dividing unit 121 receives a path setting command via the input / output unit 11 or the communication unit 14, the section dividing unit 121 divides the route from the start node to the end node at the relay node. For example, the section dividing unit 121 divides the route from the node 2A to the node 2D (see FIG. 1) into two sections, sections # 1 and # 2, with the node 2C as a relay node. The section division at this time is performed with reference to routing information stored in the routing information storage unit 131 described later.

  The route calculation unit 122 refers to the routing information and calculates a route (shortest route) that minimizes the link cost for each section. The shortest path calculation here uses the above-mentioned restricted dijkstra algorithm, k-shortest path algorithm, or the like.

  The route overlap determining unit 123 determines whether there is route overlap between the sections. The determination of the presence / absence of route overlap at this time is made when there is one or more routes (links) between the sections, and it is determined that there is a route overlap between the sections. That is, if the path of node 2B → node 2C (link B) is included in section # 1, and the path of node 2C → node 2B (link B) is also included in section # 2, the path duplication determination unit 123 determines that there is a route overlap in these sections. Note that the determination of route overlap at this time may be made based on whether or not the route of each section includes a pair of the same node 2 in each section when the route of each section is described by a combination of nodes 2.

  The route candidate calculation unit 124 refers to the routing information and calculates a route candidate for each section. The calculated route candidate is stored (stored) in the route information storage unit 133 for each section in association with the section ID or the like.

  The route combination search unit 125 reads out route candidates for each section from the route information storage unit 133 for each section, and searches for a combination of routes that do not have overlapping routes from the combinations of the route candidates. Then, a combination of routes having the lowest link cost is selected from the combination of routes having no route overlap, and this combination is output as a route calculation result.

  The routing information acquisition unit 126 acquires the link cost (remaining bandwidth in each link, etc.) of each node 2 via the communication unit 14 and stores (stores) it in the routing information storage unit 131.

  When the path control unit 127 receives a path setting command from the input / output unit 11 or the like, the path control unit 127 outputs the command to the section dividing unit 121. When the route calculation result output from the route combination search unit 125 is received, a path setting command based on the route calculation result is output to each node 2 via the communication unit 14. This path setting command is performed, for example, by a signaling protocol for path setting.

  The function of the processing unit 12 is realized by a predetermined program stored in the storage unit 13 by a CPU (Central Processing Unit) or the like.

  The storage unit 13 stores various data to be referred to when the processing unit 12 performs route calculation, in addition to a program for realizing the function of the route calculation device 1. The storage unit 13 stores a routing information storage unit 131 that stores routing information (link information and topology information), a path information storage unit 132 that stores a route from the start node to the end node, and a route candidate for each section. And a section-by-section path information storage unit 133. The storage unit 13 is realized by a storage device such as a RAM (Random Access Memory), a flash memory, and an HDD (Hard Disk Drive).

  The routing information storage unit 131 stores link information connecting each node 2 and network topology information. As illustrated in Table 2 below, this link information includes, for each link ID, the link cost (link cost information), A-end node ID, A-end node IF (interface) ID, Z-end node ID, This is information indicating the Z-end node IF ID and the like. For example, a value obtained from the remaining bandwidth of the link is used as the link cost value. The node ID and IF ID are described by an IP address, for example.

  The topology information is information indicating identification information of the node 2 installed in the network and how the nodes are connected to each other. This topology information is not shown here. Here, the topology information and the link information are separate, but the above-described link information may be included in the topology information.

  As described above, the path information storage unit 132 stores the route (path) information calculated by the route combination search unit 125. Table 3 below illustrates the path information.

Note that this path information may be prepared both for the route from the start node to the end node and for each section obtained by dividing the route with the inclusive route designation. In this case, the path information for each section is, for example, as shown in Table 4 below, for each path ID of the path (path), and for each section dividing the path, the start node ID and start node IF of the section
This is information indicating an ID, an end node ID, an end node IF ID, a via link ID list, a link cost, and the like. The route link ID list and the link cost in the path information for each section are rewritten when the path combination search unit 125 selects another path candidate from the path candidates in the section.

  The route information storage unit 133 for each section stores the route candidates for each section calculated by the route candidate calculation unit 124. This section-by-section path information is information indicating, for each section ID, the link ID of the link that passes through the section (routed link ID list) and the link cost of the section when the link is used. In addition, although the route candidate for each section is described as using the same for both uplink and downlink, separate route candidates may be prepared for uplink and downlink.

  The section-by-section route information illustrated in Table 5 is the section-by-section route information in the path ID “HH”. The path ID “HH” is divided into three sections with section IDs “1 to 3”, and the section with the section ID “1” indicates that there are five route candidates. The section with the section ID “2” has four route candidates, and the section with the section ID “3” has two route candidates.

  For example, in the route information for each section illustrated in Table 5, the route candidate with the route candidate ID “1” in the section ID “1” has a link ID “1” → link ID “2” → link ID “3”. This indicates a route to be followed, and the link cost is “2”.

  Then, as exemplified in Table 5, these route candidates may list the link IDs of the via links that pass through the route in the order of passage, or may list the node IDs of the nodes that pass through in the order of passage. . Further, the route candidates in each section are arranged, for example, in ascending order of link cost. That is, in the route information for each section illustrated in Table 5, the via link indicated by the route candidate ID “1” is the route with the lowest link cost (shortest route) among the route candidates in the section, and the route candidate ID “ The via link indicated by “2” is the route with the next lowest link cost. This route information for each section is referred to when the route combination search unit 125 searches (selects) a combination of route candidates. Note that the route information for each section may indicate the route candidate currently selected by the route combination search unit 125. Incidentally, in the route information for each section illustrated in Table 5, the route candidate with the route candidate ID “2” is selected for the section ID “1”, and the route candidate with the route candidate ID “2” is selected for the section ID “2”. The section ID “3” indicates that the route candidate with the route candidate ID “1” is selected.

  The communication unit 14 manages a communication interface with each node 2. The processing unit 12 acquires the routing information of each node 2 or outputs a path setting command to each node 2 via the communication unit 14.

<Operation of route calculation device>
Next, the operation of the route calculation apparatus 1 will be described with reference to FIG. FIG. 3 is a flowchart showing the operation of the route calculation apparatus of FIG. Note that the route calculation apparatus 1 acquires the routing information of each node 2 and stores it in the routing information storage unit 131 before starting the route calculation.

  First, the route calculation apparatus 1 receives an inclusive route designation input via the relay node input unit 111 (S301). That is, input of the IDs of the start node and the end node and the ID (identification information) of the relay node that passes between the nodes is accepted.

  Next, when the path control unit 125 receives a path setting command from the input / output unit 11 or the like, the section dividing unit 121 divides the route from the start point node to the end point node into a plurality of sections using this as a trigger. In other words, the section dividing unit 121 divides the route from the start node to the end node into a plurality of sections using a node designated as an inclusive route (S302).

  Next, the route calculation unit 122 calculates the shortest route for each section divided in S302 (S303). The calculated shortest path for each section is stored in the section-by-section path information storage unit 133.

  Then, the route overlap determination unit 123 determines whether or not there is a route overlap in the shortest route of each section calculated in S303 (S304). For example, the route duplication determination unit 123 refers to the route link ID list of the route candidate ID “1” of each section in the route information for each section as illustrated in Table 5, and overlaps the shortest route of each section. Judge whether there is. Here, when there is no route overlap (No in S304), the route calculation unit 122 outputs the shortest route of each section as a calculation result (S309), and ends the processing.

  On the other hand, when there is a route overlap in the shortest route in each section calculated in S303 (Yes in S304), the route candidate calculation unit 124 refers to the routing information, calculates a route candidate for each section, and Route information (see Table 5) is created (S305). This section-by-section route information is stored in the section-by-section route information storage unit 133.

  Then, the route combination search unit 125 reads out the route candidate for each section from the route information for each section created in S305 for the section having the route overlap, and the combination without the route overlap is selected from the combinations of the route candidates. Is searched (S306). Next, the route combination search unit 125 selects a combination of routes that minimizes the link cost from among combinations of routes that do not have route overlap (S307).

  Then, when the combination of the routes selected in S307 overlaps with the route in another section (Yes in S308), the route overlap determination unit 123 determines whether the route in which the corresponding route overlaps between S306 and S307. When the process is executed and there is no route overlap with the route of another section (No in S308), the calculation result is output to the path control unit 127 and the path information storage unit 132 (S309), and the process is terminated. . That is, the route of the section is replaced with the selected route candidate and output.

  For example, when the route combination search unit 124 first finds a route overlap between the section with the section ID “1” and the section with the section ID “2”, the section with the section ID “1” and the section ID A combination of route candidates that does not overlap with the section “2” and that minimizes the link cost is selected.

  Here, the route combination search unit 124 selects the route candidate with the route candidate ID “2” for the section with the section ID “1”, and the route candidate ID “2” with respect to the section with the section ID “2”. When a route candidate is selected, there is no route overlap between the sections. However, as illustrated in Table 5, there is a route overlap in the route with the route candidate ID “1” in the section with the section ID “3” which is another section. That is, the link ID “7” in the route candidate ID “2” of the section ID “2” overlaps with the link ID “7” in the route candidate ID “1” of the section ID “3”. Therefore, the route combination search unit 124 searches for a combination of route candidates having no route overlap between the section with the section ID “2” and the section with the section ID “3”. Then, the route combination search unit 124 selects a combination having the lowest link cost among them.

  Then, the combination search unit 124 repeats the above processing, and when a combination of routes having no route overlap is found in any section, the combination of the found routes is calculated as a calculation result, and the path control unit 127 and the path information storage unit 132. To output to the process.

  By doing in this way, the route calculation device 1 can find a route having no route overlap and a link cost as low as possible in the route from the start point node to the end point node when the inclusive route is designated.

  In the above-described embodiment, the route calculation apparatus 1 first calculates the shortest route of each section, calculates a route candidate when it is determined that there is a route overlap between the sections, and provides route information for each section ( However, the present invention is not limited to this. For example, when calculating the shortest route of each section, the route calculation apparatus 1 may calculate route candidates other than the shortest route, and create route information for each section based on this.

<< Second Embodiment >>
Next, a route calculation apparatus according to the second embodiment will be described. When a route overlap is found in the shortest route of the section delimited by the inclusive route designation, this route calculation apparatus selects one section from which the route is to be changed (replaced). The route calculation device is characterized in that the shortest route in the selected section is replaced in order from the route candidate with the lowest link cost, and a route candidate that eliminates route overlap with other sections is searched.

<Overview of operation>
Here, an outline of the operation of the route calculation apparatus 1a according to the second embodiment will be described with reference to FIG. Since the network configuration is the same as that of the first embodiment described above, the description thereof is omitted. Also in this case, the route calculation device 1a is a relay node (node 2C), and divides the route into sections # 1 and # 2, and when taking the shortest route of each section, the route of node 2B → node 2C and node 2C → The case where the route of the node 2B overlaps will be described as an example.

  Therefore, the path calculation device 1a first selects the shortest path (node 2A → node 2B → node 2C (link cost = 2)) in the section # 1, and next the path candidate (node 2A → node 2C (link) with the lowest link cost. Replace with cost = 5)). If the route of section # 1 after replacement does not overlap with the route of section # 2, the route calculation device 1a outputs this route as a route result.

  On the other hand, if the replaced route overlaps with the route of section # 2, the route calculation device 1a replaces the route of section # 1 with a route candidate with the next lowest link cost. Repeat until a route that does not overlap with the shortest route of # 2 is found. When the route calculation device 1a finds a route that does not overlap with the route of the section # 2, the route calculation device 1a outputs the route as a route result.

<Configuration of route calculation device>
Next, the configuration of the route calculation apparatus 1a will be described in detail with reference to FIG. FIG. 4 is a block diagram illustrating a configuration of the route calculation apparatus according to the second embodiment. Constituent elements similar to those in the first embodiment described above are denoted by the same reference numerals, and description thereof is omitted.

  The route calculation device 1 a includes a route matching search unit 125 a instead of the route combination search unit 125. The route combination search unit 125a searches for a route that eliminates the route overlap by sequentially replacing the shortest route in a section with route overlap from the route candidate with the lowest link cost. Details of the route matching search unit 125a will be described later using a flowchart.

<Operation of route calculation device>
Next, the operation of the route calculation apparatus 1a will be described with reference to FIG. FIG. 5 is a flowchart showing the operation of the route calculation apparatus of FIG. The route calculation device 1a also acquires the routing information of each node 2 and stores it in the routing information storage unit 131 before starting the route calculation.

  Since the processing from S501 to S505 is the same as the processing from S301 to S305 in FIG. 3, the description thereof will be omitted and the description will start from S506. In the following description, the route calculation device 1a will be described by taking as an example a case where the section from the start node to the end node is divided into three sections with section IDs “1 to 3” by inclusive route designation. Then, when the route calculation device 1a confirms whether or not there is a route overlap in each section, it is assumed that there is a route overlap in the section with the section ID “1” and the section with the section ID “2”.

  The route combination search unit 125a selects a section in which the route is changed from the sections in which the route overlap occurred in S504 (the route overlap was found) (S506). That is, the route combination search unit 125 selects a section in which a route candidate is replaced with a route. Here, the section is selected preferentially (in order) in descending order of the link cost of the shortest path in the section. For example, when the link cost of the shortest route of section # 1 where the route overlaps is “3” and the link cost of the shortest route of section # 2 is “2”, select section # 1 having a higher link cost To do.

  Then, the route combination search unit 125a refers to the route information for each section (see Table 5), selects the route candidate with the next lowest link cost among the route candidates in the section selected in S506, and selects the selected route. The candidate is replaced with a route (S507). For example, the route combination search unit 125a selects the route candidate with the next smallest link cost after the shortest route (route with the route candidate ID “1”) from the route candidate with the interval ID “1” of the route information for each interval illustrated in Table 5. The route candidate with ID “2” is selected. Then, the route combination search unit 125a replaces the route with the section ID “1” with the route with the route candidate ID “2”. The replaced route information is stored in the storage unit 13.

  Turning to the description of FIG. Next, the route overlap determination unit 123 refers to the route information for each section (see Table 5), and whether the route replaced in S507 in FIG. 5 has a route overlap with another section in which the route overlap is found. Is determined (S601). That is, it is determined whether or not there is an overlap with the route of the section that has not been replaced in S507 (for example, the section with the section ID “2”) among the sections in which the route overlap is found in S504. Here, when there is no route overlap (No in S601), the route overlap determination unit 123 determines whether or not there is a route overlap with a section other than the section where the current route overlap is found (S605). That is, the route duplication determination unit 123 determines the section in which the overlap is found in S504, for example, the section with the section ID “1” and the section with the section ID “2”, and other sections (for example, the section with the section ID “3”). It is determined whether or not there is a route overlap with (section). Here, when there is no route overlap with a section other than the section where the overlap is found this time (No in S605), that is, when a route having no route overlap is found in any other section, the route combination search unit 125a The route is output as a calculation result to the path control unit 127 and the path information storage unit 132 (S606), and the process ends. On the other hand, if there is a route overlap with a section other than the section where the overlap was found this time (for example, the section with the section ID “3”) (Yes in S605), The processing after S506 in FIG. 5 is executed to search for a route having no route overlap.

  If the route replaced in S507 overlaps with a route in another section in which route overlap is found (Yes in S601), and there is a route candidate that has not yet been selected in that section (Yes in S602), The process returns to S507 in FIG. Then, the route combination search unit 125a refers to the route information for each section (see Table 5), selects the route candidate with the next lowest link cost from the route candidates in the section selected in S506 of FIG. Perform replacement of. Then, when the route combination search unit 125a has found a route candidate without a route overlap (Yes in S601), the process proceeds to S605.

  Further, when the route combination search unit 125a determines that there is no route candidate that can be selected next for the section with reference to the section-specific route information (see Table 5) (No in S602), that is, in S506. When the replacement with all the route candidates in the selected section is completed, the following processing is performed. That is, the route combination search unit 125a returns the route of the section selected in S507 to the shortest route once if there is a section in which the route is not changed among the sections in which the route overlap is found (Yes in S603) ( S604). Then, the process proceeds to S506, and a section with the highest link cost is selected from the sections in which the route overlap has been found and the route has not been changed yet.

  For example, if the route combination search unit 125a replaces the route with the section ID “1” with any route candidate, the route combination search unit 125a determines that it overlaps with the shortest route with the section ID “2”. Return the route to the shortest route. Next, the route combination search unit 125a selects a section with the next highest link cost, that is, a section ID “2”, among the sections in which the route overlap is found, and executes route replacement in this section. A search is made for a combination having no route overlap with the shortest route of “1”.

  On the other hand, the route combination search unit 125a calculates that the route having no route overlap could not be searched when the change of the route of all the portions among the portions having the route overlap in S504 is completed (No in S603). The result is output (S607), and the process is terminated.

  By performing such processing, the route calculation device 1a can calculate a route that has no route overlap and that minimizes the link cost when an inclusive route is designated.

  In S506 of FIG. 5, the route combination search unit 125a selects the sections in which the route is changed in order from the section with the highest link cost of the shortest path in the section, but is not limited thereto. For example, you may make it select in an order from the largest route candidate number in the said area. By doing so, the route is changed (route replacement) from a section having a larger number of route candidates, so that it is easy to find a route without an overlapping route with a small amount of calculation.

  In addition, the route calculation device 1 a receives in advance an input of a penalty cost for each section (a value indicating which section is preferentially changed from the route) via the input / output unit 11 in advance, and this is stored in the storage unit 13. Remember it. Then, in S506 of FIG. 5, when the route combination search unit 125a selects a section in which a route is to be changed, it may be preferentially selected from a section having a high penalty cost in the section. In this way, the route calculation device 1a preferentially changes the route from the section desired by the operator of the route calculation device 1a.

  In each of the above-described embodiments, if the route combination search unit 125, 125a does not find a route with no route overlap even when trying to combine with any route candidate, the calculation is forcibly terminated. May be. At this time, the route combination search unit 125, 125a outputs a message notifying that the route having no route overlap could not be found to the output device connected to the route calculation device 1, 1a. A screen that prompts re-input or re-input of route setting conditions may be displayed.

  Further, the route calculation device 1a replaces the section selected in S506 of FIG. 5 (for example, section # 1) for any of the path candidates, and the other section (for example, section # 2) in which the route overlap is found is replaced. If it overlaps with the shortest path, it may be as follows.

  That is, the route combination search unit 125a first replaces the route in the section # 2 with a route candidate with the next lowest link cost after the shortest route (for example, a route candidate with the route candidate ID “2”). Then, the route candidates in the section # 1 are replaced with the route candidates in order from the shortest route, and a route combination that does not overlap with the route candidates in the section # 2 is searched. In this case, if any route candidate is replaced with respect to the route # 1, if it overlaps with the route candidate with the route candidate ID “2” of the interval # 2, the route of the interval # 2 is further linked to the next link cost. The same processing is executed by replacing with a small route candidate (for example, a route candidate with the route candidate ID “3”). The route combination search unit 125a may repeat such processing to search for a route that does not overlap in both sections.

  Furthermore, in the above-described embodiment, the route calculation devices 1 and 1a have been described as devices separate from the node 2. However, the node 2 may function as the route calculation devices 1 and 1a.

  Further, when the route calculation devices 1 and 1a are intended to calculate a route having the highest link cost as much as possible for the route from the start point node to the end point node, the following is performed. That is, in S307 of FIG. 3, the route combination search unit 125 (see FIG. 2) selects a combination of routes that maximizes the link cost. In S507 of FIG. 5, the route combination search unit 125a replaces the route candidates in order from the route candidate with the highest link cost. By doing in this way, the route calculation apparatuses 1 and 1a can find a route with no route overlap and a link cost as high as possible.

  The route calculation apparatuses 1 and 1a according to the present embodiment can be realized by a route calculation program for executing the processing as described above, and the program is stored in a computer-readable storage medium (CD-ROM or the like). Can be provided. It is also possible to provide the program through a network.

It is the figure which showed the structural example of the network containing the route calculation apparatus in embodiment of this invention. It is the block diagram which showed the structure of the route calculation apparatus of FIG. It is the flowchart which showed operation | movement of the route calculation apparatus of FIG. It is the block diagram which showed the structure of the route calculation apparatus of 2nd Embodiment. 5 is a flowchart showing the operation of the route calculation apparatus of FIG. 5 is a flowchart showing the operation of the route calculation apparatus of FIG. It is the figure quoted in order to demonstrate the subject of this invention.

Explanation of symbols

1, 1a, 6 Route calculation device 2 (2A, 2B, 2C, 2D) Node 11 Input / output unit 12 Processing unit 13 Storage unit 14 Communication unit 111 Relay node input unit 121 Section division unit 122 Path calculation unit 123 Path overlap determination unit 124 Route candidate calculation unit 125, 125a Route combination search unit 126 Routing information acquisition unit 127 Path control unit 131 Routing information storage unit 132 Path information storage unit 133 Route information storage unit for each section

Claims (10)

Refer to the input / output unit that controls the input / output of various data, the storage unit that stores the topology information of the nodes constituting the network and the link cost information of the link connecting the nodes, the topology information, and the link cost information A route calculation device including a processing unit that performs route calculation;
A relay node input step for receiving input of identification information of the relay node via the route from the start node to the end node in the network via the input / output unit;
A section dividing step of dividing the route from the start node to the end node into a plurality of sections by the relay node;
Referring to the link cost information, for each of the divided sections, calculate the shortest path that minimizes the link cost in the section, and store the calculated shortest path for each section in the storage unit Steps,
A first route overlap determination step for determining whether or not there is route overlap between the shortest routes;
In the first route overlap determination step, when there is a route overlap between the shortest routes,
A route candidate calculation step of calculating possible route candidates for each section with reference to the topology information, and storing the calculated route candidates for each section in the storage unit;
The route candidate in each section where the route overlap is found is read from the storage unit, and a combination of routes without route overlap is searched from the read route candidates in the sections where the route overlap is found. Then, a route combination search that selects a route combination that minimizes the link cost from among the route combinations that do not have the route overlap, replaces the route in the section where the route overlap is found, with the selected route, and outputs the route combination. Steps,
The path calculation method characterized by performing. In the route combination search step,
From the section in which the route overlap is found, select a section to replace the route candidate with the path, read the route candidate in the selected section from the storage unit, the read route candidate, The link cost is selected in ascending order, the route in the section is replaced with the selected route candidate, and a combination of routes that does not overlap with another section in which the route overlap is found is searched for. Route calculation method. In the route combination selection step,
The route calculation method according to claim 2, wherein a section in which the route is replaced is selected in order from a section having a large number of route candidates in the section. In the route combination search step,
The route calculation method according to claim 2, wherein a section in which the route is replaced is selected in order from a section having a highest link cost of the shortest path in the section. The input of the penalty cost for each section is received via the input / output unit, and the penalty cost input step of storing the inputted penalty cost for each section in the storage unit is further executed.
In the route combination selection step,
The route calculation method according to claim 2, wherein the sections for which the route is replaced are selected in order from the section with the highest penalty cost in the section. Further executing a second route duplication determination step of judging whether or not the route replaced in the route combination search step overlaps with a route in a section other than the section in which the route duplication is found,
In the second route overlap determination step, when it is determined that the replaced route overlaps with a route in a section other than the section where the route overlap is found,
The route calculation method according to any one of claims 1 to 5, wherein the route combination search step is executed again for a section in which the routes are determined to overlap.   A route calculation program that causes a route calculation device that is a computer to execute the route calculation method according to any one of claims 1 to 6. A storage unit for storing topology information of nodes constituting the network and link cost information of links connecting the nodes;
A relay node input unit that receives input of identification information of a relay node that passes through a route from a start node to an end node in a route in the network;
A section dividing unit that divides the route from the start node to the end node into a plurality of sections by the relay node;
Referring to the link cost information, for each of the divided sections, calculate the shortest path that minimizes the link cost in the section, and store the calculated shortest path for each section in the storage unit And
A route overlap determination unit for determining whether there is route overlap between the shortest routes; and
When it is determined that there is a route overlap between the shortest routes in the route overlap determination unit,
By referring to the topology information, a possible route candidate for each section is calculated, and the calculated route candidate for each section is stored in the storage unit;
The route candidate in each section where the route overlap is found is read from the storage unit, and a combination of routes without route overlap is searched from the read route candidates in the sections where the route overlap is found. The route combination search that selects the route combination that minimizes the link cost from the route combinations that do not have the route overlap, replaces the route in the section where the route overlap is found, with the selected route, and outputs the route combination. And
A route calculation apparatus comprising: The route combination search unit
From the section in which the route overlap is found, select a section to replace the route candidate with the path, read the route candidate in the selected section from the storage unit, the read route candidate, 9. The link cost is selected in ascending order, the route in the section is replaced with the selected route candidate, and a combination of routes that does not overlap with other sections in which the route overlap is found is searched for. Route calculator. The route combination search unit
When the replaced route overlaps with a route in a section other than the section where the route duplication is found,
The route calculation according to claim 8 or 9, wherein the search for the route combination and the replacement with the selected route are executed again for a section in which the routes are determined to overlap. apparatus.

Images