PATH SEARCH PROGRAM, PATH SEARCH APPARATUS AND PATH SEARCH METHOD

• US 20130003730A1
• Filed: 05/11/2012
• Published: 01/03/2013
• Est. Priority Date: 06/30/2011
• Status: Abandoned Application

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Takita, Yutaka, Tajima, Kazuyuki, Hashiguchi, Tomohiro
• Application Number:
  US13/469,237
• Publication Number:
  US 20130003730A1
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

A computer-readable recording medium having stored therein a program for causing a computer to execute a process includes accepting a start node and finish node that are both terminuses for a circuit that is to be accommodated in a transmission network that includes a plurality of transmission lines, selecting, from the plurality of transmission lines, a transmission line whose arrangement order of arranging a plurality of nodes on the transmission line in an order of an indicated direction determined for the transmission line is the same as an order of the plurality of nodes determined in accordance with a cost order of the shortest path from a node at a terminus of the circuit to the plurality of nodes, and searching for a path from the circuit'"'"'s start node to the circuit'"'"'s finish node via the selected transmission line in the order of the indicated direction.

Claims

1. A computer-readable recording medium having stored therein a program for causing a computer to execute a process comprising:

accepting a start node and finish node that are both terminuses for a circuit that is to be accommodated in a transmission network that includes a plurality of transmission lines;

selecting, from the plurality of transmission lines, a transmission line whose arrangement order of arranging a plurality of nodes on the transmission line in an order of an indicated direction determined for the transmission line is the same as an order of the plurality of nodes determined in accordance with a cost order of the shortest path from a node at a terminus of the circuit to the plurality of nodes; and

searching for a path from the circuit'"'"'s start node to the circuit'"'"'s finish node via the selected transmission line in the order of the indicated direction.

2. The computer-readable recording medium according to claim 1,

wherein on selecting a transmission line having an arrangement order, which involves arranging the plurality of nodes in order of the indicated direction, that is the same as an order of the plurality of nodes determined in accordance with the cost order, the process further comprises:

determining, in accordance with a cost order of the shortest path from the node at a terminus of the circuit to both end nodes of a link in the transmission network, the link'"'"'s direction, and

comparing the link'"'"'s direction in the transmission line with the indicated direction of the transmission line so as to determine whether an arrangement order of arranging both end nodes of the link in the order of the indicated direction is equal to an order of both end nodes of the link, which is determined in accordance with the cost order of the shortest path from the node at a terminus of the circuit to both end nodes of the link.

3. The computer-readable recording medium according to claim 2,

wherein when the cost of the shortest path from the node at a terminus of the circuit is the same for both end nodes of the link, a determination is made that the order of both end nodes of the link, which is determined in accordance with the cost order, is the same as the arrangement order of arranging both end nodes of the link in the order of the indicated direction.

4. The computer-readable recording medium according to claim 1,

wherein on selecting a transmission line whose arrangement order of arranging the plurality of nodes in order of the indicated direction is the same as the order of the plurality of nodes as determined in accordance with the cost order, the process further comprises:

comparing a shortest path cost from the node at a terminus of the circuit to a first node on the transmission line with a shortest path cost from the node at a terminus of the circuit to a second node adjacent to the first node so as to determine whether an arrangement order of arranging the first node and the second node in the order of the indicated direction is the same as an order of the first node and the second node determined in accordance with the cost order of the shortest path from the node at a terminus of the circuit.

5. The computer-readable recording medium according to claim 1,

wherein on selecting a transmission line whose arrangement order of arranging the plurality in order of the indicated direction is the same as the order of the plurality of nodes determined in accordance with the cost order, the process further comprises:

selecting, from nodes coupled by a link to a first node on the transmission line, a coupled node having a given magnitude relation between a cost of a shortest path from the node at a terminus of the circuit to the first node and a cost of a shortest path from the node at a terminus of the circuit to the coupled node, which is coupled to the first node by a link, and

determining whether a second node adjacent to the first node matches any one of the selected nodes so as to determine whether an arrangement order of arranging the first node and the second node in the order of the indicated direction is equal to order of the first node and the second node determined in accordance with the cost order of the shortest path from the node at a terminus of the circuit.

6. The computer-readable recording medium according to claim 1,

wherein on selecting a transmission line whose arrangement order of arranging the plurality of nodes in the order of the indicated direction is the same as the order of the plurality of nodes determined in accordance with cost order,

a cost of a shortest path from the node at a terminus of the circuit to the node at the other end of the circuit is set to a higher value than any node other than the nodes at both terminuses of the circuit.

7. The computer-readable recording medium according to claim 1,

wherein on selecting a transmission line whose arrangement order of arranging the plurality of nodes in order of the indicated direction is the same as the order of the plurality of nodes determined in accordance with the cost order,

only a transmission line having at least one of either a start point that is coupled to another transmission line or an end point that is coupled to another transmission line is determined to be a selection target.

8. A path search apparatus comprising:

a memory

to store a start node and a finish node that are both terminuses of a circuit that is to be accommodated in a transmission network that includes a plurality of transmission lines;

a processor

to select, from the plurality of transmission lines, a transmission line whose arrangement order of arranging a plurality of nodes on the transmission line in an order of an indicated direction determined for the transmission line is the same as an order of the plurality of nodes determined in accordance with a cost order of a shortest path from a node at a terminus of the circuit to the plurality of nodes, and

to search a path from the circuit'"'"'s start node to the circuit'"'"'s finish node via the selected transmission line in the order of the indicated direction.

9. The path search apparatus according to claim 8,

wherein the processor further to determine settings of a network apparatus on the transmission network.

10. The path search apparatus according to claim 8,

wherein the processor further to establish the circuit by controlling setting of a network apparatus on the transmission network in response to the input of the circuit'"'"'s start node and the circuit'"'"'s finish node.

11. A computer-implemented method of searching a path, the method comprising:

accepting input a start node and a finish node that are both ends of a circuit that is to be accommodated in a transmission network that includes a plurality of transmission lines;

selecting, by a processor, from the plurality of transmission lines, a transmission line whose arrangement order of arranging a plurality of nodes on the transmission line in an order of an indicated direction determined for the transmission line is the same as an order of the plurality of nodes determined in accordance with a cost order of a shortest path from a node at an end of the circuit to the plurality of nodes; and

searching, by a processor, a path from the circuit'"'"'s start node to the circuit'"'"'s finish node via the selected transmission line in the order of the indicated direction.