초록 ▼

A calculating apparatus calculates a shortest path connecting two nodes of a network. A shortest-path group, which is a set of shortest paths having node Y as their starting points, can be calculated at once by having calculated a shortest path having node Y as its starting point for each of other n

A calculating apparatus calculates a shortest path connecting two nodes of a network. A shortest-path group, which is a set of shortest paths having node Y as their starting points, can be calculated at once by having calculated a shortest path having node Y as its starting point for each of other nodes. When the shortest-path group having node Y as the starting point is calculated and further if a group of shortest paths having node X as their starting points is stored beforehand in a storing unit, then path portions, which belong to the group of shortest paths having node X as the starting points and further which are paths extending from node Y to the nodes located downstream from node Y, are utilized as part of a result of calculation of the shortest path group having node Y as the starting point.

대표청구항 ▼

1. A calculating apparatus which calculates the shortest path connecting two nodes in a network, comprising: a storage unit that is configured to store therein information including information on a shortest path group which is a set of the shortest paths between the nodes, each of the shortest path

1. A calculating apparatus which calculates the shortest path connecting two nodes in a network, comprising: a storage unit that is configured to store therein information including information on a shortest path group which is a set of the shortest paths between the nodes, each of the shortest paths having the same node as a starting point;a control unit that is configured to, based on a triggering event which is a topological change including addition of a link or deletion of a link: calculate a shortest path group which is a set of shortest paths having a node Y as a starting point at once, by calculating the shortest path having the node Y as the starting point for each of nodes other than the node Y, and calculate a shortest path group of a first node which is any one of the nodes other than the node Y, using path information, the path information including a piece of information on a second node that is adjacent to the first node on a given path which goes through the first node and is located upstream of the first node in one hop and including multiple pieces of information on third nodes that are each adjacent to the first node on the given path which goes through the first node and are each located downstream of the first node in one hop; wherein paths between given nodes are represented in a tree structure by tracing an upstream or downstream relation between the first, second, and third nodes, andperform a first processing in which, in calculating the shortest path group having the node Y as the starting point, if the storage unit previously stores therein a shortest path group having a node X that is located upstream of the node Y in one hop, as a starting point, the shortest path group having the node X as the starting point having already been calculated after the topological change, the control unit takes, from among the shortest path group having the node X as the starting point, a path from the node Y to a node located downstream of the node Y as the shortest path of the shortest path group having the node Y as the starting point which is currently being calculated, that is, an intermediate calculation result of the shortest path group. 2. The calculating apparatus according to claim 1, wherein the control unit is further configured to: perform a second processing in which the control unit searches for a node “a” from nodes not going through any portion of the intermediate calculation result of the shortest path group having the node Y as the starting point, the node “a” being reachable by a link in one hop from a node passing through a portion of the intermediate calculation result, and, from paths from the node Y to the node “a”, the control unit takes a path R1 which goes through both the link in one hop and a path going through the intermediate calculation result from the node Y to a node going through a portion of the intermediate calculation result out of extreme points of the link, as a candidate shortest path from the node Y to the node “a”, andperform a third processing in which, if the candidate shortest path from the node Y to the node “a” is present, the control unit selects a candidate shortest path having the shortest distance as R2, compares a distance of the selected shortest path R2 to an other path having been already found by the time of the selection of the shortest path R2 as a path from the node Y to the node “a”, and, if the selected shortest path R2 is determined to be the shortest, takes the selected shortest path R2 as the shortest path from the node Y to the node “a” and also as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 3. The calculating apparatus according to claim 2, wherein, if a candidate shortest path having the node Y as the starting point and connecting any other node is present in the third processing, the control unit is further configured to select a candidate shortest path having the shortest distance as R2, compares a distance of the selected shortest path R2 to other path having been already found by the time of the selection of the shortest path R2 as a path from the node Y to the node “a”, and, if the selected shortest path R2 is determined to be the shortest, takes the selected shortest path R2 as the shortest path from the node Y to the node “a” and also as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 4. The calculating apparatus according to claim 3, wherein the control unit is further configured to perform a fourth processing in which the control unit changes a distance from the node Y to a node located downstream of the node “a”, to a distance which goes through both the selected shortest path from the node Y to the node a and a path reached in accordance with a path tree from the node a to the node located downstream of the node a, and takes the path tree located downstream of the node “a” as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 5. The calculating apparatus according to claim 4, wherein the control unit is further configured to: perform a fifth processing in which the control unit searches for a node a′ which is reachable by a link in one hop from a node located downstream of the node “a”;find, as a path from the node Y to the node a′, a path R3 which reaches the node a′ from the node Y in accordance with a path tree, and a path R4 which goes through the link in one hop, the selected shortest path from the node Y to the node “a”, and a path from the node “a” to an extreme point of the link in one hop;and, if a distance of the path R4 is shorter, take the path R4 as a candidate shortest path from the node Y to the node a′, andwherein, returning back to the third processing, the control unit is further configured to determine the shortest path from the node Y to the node a′. 6. A path calculating method of calculating a shortest path connecting two nodes in a network, the method comprising:a storing step of storing information including information on a shortest path group which is a set of the shortest paths between the nodes, each of the shortest paths having the same node as a starting point; and a controlling and calculating step, based on a triggering event which is a topological change including addition of a link or deletion of a link, of calculating a shortest path group which is a set of shortest paths having a node Y as a starting point at once, by calculating the shortest path having the node Y as the starting point for each of nodes other than the node Y, and calculating a shortest path group of a first node which is any one of the nodes other than the node Y, using path information, the path information including a piece of information on a second node that is adjacent to the first node on a given path which goes through the first node and is located upstream of the first node in one hop and including multiple pieces of information on third nodes that are each adjacent to the first node on the given path which goes through the first node and are each located downstream of the first node in one hop; wherein paths between given nodes are represented in a tree structure by tracing an upstream or downstream relation between the first, second, and third nodes, andwherein the calculation performed by the controlling and calculating step includes a first processing in which, in calculating the shortest path group having the node Y as the starting point, if a shortest path group having a node X that is located upstream of the node Y in one hop, as a starting point, is previously stored by the storing step, the shortest path group having the node X as the starting point having already been calculated after the topological change, in the controlling and calculating step, from among the shortest path group having the node X as the starting point, a path from the node Y to a node located downstream of the node Y is taken as the shortest path of the shortest path group having the node Y as the starting point which is currently being calculated, that is, an intermediate calculation result of the shortest path group. 7. The path calculating method according to claim 6, wherein the calculation performed by the controlling and calculating step includes: a second processing in which: a node “a” is searched for from nodes not going through any portion of the intermediate calculation result of the shortest path group having the node Y as the starting point, the node “a” being reachable by a link in one hop from a node passing through a portion of the intermediate calculation result; and, from paths from the node Y to the node “a”, a path R1 which goes through both the link in one hop and a path going through the intermediate calculation result from the node Y to a node going through a portion of the intermediate calculation result out of extreme points of the link is taken as a candidate shortest path from the node Y to the node “a”; anda third processing in which: if the candidate shortest path from the node Y to the node “a” is present, a candidate shortest path having the shortest distance is selected as R2; a distance of the selected shortest path R2 is compared to an other path having been already found by the time of the selection of the shortest path R2 as a path from the node Y to the node “a”; and, if the selected shortest path R2 is determined to be the shortest, takes the selected shortest path R2 as the shortest path from the node Y to the node “a” and also as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 8. The path calculating method according to claim 7, wherein, in the calculation performed by the controlling and calculating step includes:selecting a candidate shortest path having the shortest distance as R2 if a candidate shortest path having the node Y as the starting point and connecting any other node is present in the third processing;comparing a distance of the selected shortest path R2 to an other path having been already found by the time of the selection of the shortest path R2 as a path from the node Y to the node “a”; and,if the selected shortest path R2 is determined to be the shortest, taking the selected shortest path R2 as the shortest path from the node Y to the node “a” and also as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 9. The path calculating method according to claim 8, wherein the calculation performed by the controlling and calculating step includes a fourth processing in which: a distance from the node Y to a node located downstream of the node “a” is changed to a distance which goes through both the selected shortest path from the node Y to the node “a” and a path reached in accordance with a path tree from the node “a” to the node located downstream of the node “a”; and the path tree located downstream of the node “a” is taken as a portion of an intermediate calculation result of the shortest path group having the node Y as the starting point. 10. The path calculating method according to claim 9, wherein the calculation performed by the controlling and calculating step includes a fifth processing in which: a node a′ which is reachable by a link in one hop from a node located downstream of the node “a” is searched for; a path R3 which reaches the node a′ from the node Y in accordance with a path tree, and a path R4 which goes through the link in one hop, the selected shortest path from the node Y to the node “a”, and a path from the node “a” to an extreme point of the link in one hop are found as a path from the node Y to the node a; and, if a distance of the path R4 is shorter, the path R4 is taken as a candidate shortest path from the node Y to the node a′, andwherein, returning back to the third processing determines the shortest path from the node Y to the node a′. 11. A system including a processor and a non-transitory computer readable medium storing instructions for causing the processor to perform the path calculating method according to claim 6. 12. A system including a processor and a non-transitory computer readable medium storing instructions for causing the processor to perform the path calculating method according to claim 7. 13. A system including a processor and a non-transitory computer readable medium storing instructions for causing the processor to perform the path calculating method according to claim 8. 14. A system including a processor and a non-transitory computer readable medium storing instructions for causing the processor to perform the path calculating method according to claim 9. 15. A system including a processor and a non-transitory computer readable medium storing instructions for causing the processor to perform the path calculating method according to claim 10.