Plural-routes search method and network system using the same

• US 20030023751A1
• Filed: 05/13/2002
• Published: 01/30/2003
• Est. Priority Date: 07/11/2001
• Status: Active Grant

• Current Assignee: Fujitsu Limited, NTT Communications Corporation (Nippon Telegraph and Telephone Corporation)
• Original Assignee: Fujitsu Limited, NTT Communications Corporation (Nippon Telegraph and Telephone Corporation)
• Inventors: Saito, Hiroyuki, Nakazawa, Osamu, Yamada, Hirotoshi, Shinozaki, Akihito, Mouri, Tsunehito, Hirata, Sadayo
• Granted Patent: US 7,219,159 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A searching method of a plurality of routes includes the steps of defining, as an X direction, one direction of a bidirectional transmission line connected to each of the plurality of nodes, and another direction as a Y direction; respecifying an initial node and a terminal node; searching a first shortest route extending from the specified initial node to the specified terminal node; searching a second shortest route for nodes connected to another transmission line in the X direction; searching a third shortest route extending from the specified initial node to the specified terminal node; searching a fourth shortest route for nodes connected to another transmission line in the Y direction; comparing the sum of the X group first route and second route with the sum of the Y group first route and second route; and determining the group having a smaller sum as an optimal route in the comparison.

Claims

1. A method of searching a plurality of routes linking from an initial node to a terminal node in a network linking a plurality of nodes, comprising the steps of:

defining, as an X direction, one direction of a bidirectional transmission line connected to each of the plurality of nodes, and defining another direction as a Y direction;

specifying an initial node and a terminal node;

searching a first shortest route extending from the specified initial node to the specified terminal node, connected by nodes connected to a transmission line in the X direction, with the first shortest route being set as an X group first route;

searching a second shortest route for nodes connected to another transmission line in the X direction, excepting the nodes on the X-direction first route, with the second shortest route being set as an X group second route;

searching a third shortest route extending from the specified initial node to the specified terminal node, connected by nodes connected to a transmission line in the Y direction, with the third shortest route being set as a Y group first route;

searching a fourth shortest route for nodes connected to another transmission line in the Y direction, excepting the nodes on the Y direction first route, with the fourth shortest route being set as a Y group second route;

comparing the sum of the X group first route and second route with the sum of the Y group first route and second route; and

determining the group having a smaller sum as an optimal route in the comparison.

2. The method according to claim 1,

wherein respective searches of the X group first route, the X group second route, the Y group first route, and the Y group second route are carried out by means of the Dijkstra method.

3. The method according to claim 2,

wherein the search of the X group second route and the search of the Y group second route are repeatedly carried out by means of the Dijkstra method.

4. The method according to claim 1,

wherein the shortest route having a shortest distance is searched by means of the Dijkstra method.

5. The method according to claim 1, further comprising the steps of:

grouping all sections connected to any node; and

again carrying out the respective searches of the X group first route, the X group second route, the Y group first route, and the Y group second route, excluding the sections contained in the group, to acquire a roundabout route for the sections contained in the group.

6. The plural-routes search method according to claim 3, wherein

with respect to a plurality of routes of the searched X group second route and Y group second route, the number of times of use or a use time is registered as an attribute, to judge whether the plurality of routes are to be selected.

7. A network searching apparatus for searching a plurality of routes linking from an initial node to a terminal node in a network, which links a plurality of nodes, the apparatus comprising:

a data base for storing information data on the plurality of nodes and on sections linking adjacent nodes, with definition, as an X direction, of one direction of a bidirectional transmission line connected to each of the plurality of nodes and with definition of another direction as a Y direction; and

a plural-routes search operation system having a route search processing function, the route search processing function including,

an X directional route searching module, which specifies the initial node and the terminal node, the module searching a shortest route extending from the initial node to the terminal node, connected by nodes connected to a transmission line in the X direction, to set this route as an X group first route, the module searching a shortest route for nodes connected to another transmission line in the X direction, excepting the nodes on the X direction first route, to set this route as an X group second route,

an Y directional route searching module which searches a shortest route extending from the initial node to the final node, connected by nodes connected to a transmission line in the Y direction, to set this route as a Y group first route, the module searching a shortest route for nodes connected to another transmission line in the Y direction, excluding the nodes on the Y direction first route, to set this route as a Y group second route, and

an optimal route selection module which compares the sum of the X group first route and second route with the sum of the Y group first route and second route, to determine a group having a smaller sum in the comparison as an optimal route.

8. The network searching apparatus according to claim 7,

wherein respective searches of the X group first route, the X group second route, the Y group first route, and the Y group second route are carried out by means of the Dijkstra method.

9. The network searching apparatus according to claim 8,

wherein the search of the X group second route and the search of the Y group second route are repeatedly carried out by means of the Dijkstra method.

10. The network searching apparatus according to claim 8,

wherein the shortest route having a shortest distance is searched by means of the Dijkstra method.

11. The network searching apparatus according to claim 7,

wherein all sections connected to any node are grouped, and the respective searches of the X group first route, the X group second route, the Y group first route, and the Y group second route are searched excluding the sections contained in the group, to acquire a roundabout route for the sections contained in the group.

12. The network searching apparatus according to claim 9,

wherein with respect to a plurality of routes of the searched X group second route and Y group second route, the number of times of use or a use time is registered as an attribute, to judge whether the plurality of routes are to be selected.