Plural-routes search method and network system using the same

• US 7,219,159 B2
• Filed: 05/13/2002
• Issued: 05/15/2007
• 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
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Todd; Gregory G.
• Application Number:
  US10/144,400
• Publication Number:
  US 20030023751A1
• Time in Patent Office: 1,828 Days
• Field of Search: 709/224, 709/238, 709/241, 709/243, 709/244, 370/238, 370/395.31, 370/395.32, 370/400, 370/406, 370/241, 370/252, 370/253, 370/237, 370/232
• 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 an X direction, which is a section linking a certain node to an adjacent node in a right-hand direction, and defining a Y direction, which is a line linking the certain node to the adjacent node in a left-hand direction, while referencing the certain node;

specifying an initial node and a terminal node;

searching a first route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having only X directional elements and attributes, with the first route being set as an X group first route;

searching a second route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having X directional and Y directional elements and attributes, respectively, excepting the nodes on the X group first route, with the second route being set as an X group second route;

searching a third route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having only Y directional elements and attributes, with the third route being set as a Y group first route;

searching a fourth route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having X directional and Y directional elements and attributes, respectively, excepting the nodes on the Y group first route, with the fourth route being set as a Y group second route;

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

determining a 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 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.

5. The method according to claim 1, wherein each of the first through fourth routes of the shortest distance is searched by means of the Dijkstra method.

6. 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 mute, excluding the sections contained in the group, to acquire a roundabout route for the sections contained in the group.

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 of an X direction, which is a section linking a certain node to an adjacent node in a right-hand direction, and with definition of a Y direction, which is a line linking the certain node to the adjacent node in a left-hand direction, when referencing the certain node; and

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

an X directional mute searching module, which specifies the initial node and the terminal node, the X directional route searching module searching a first route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having only X directional elements and attributes to set the first route as an X group first route, and searching a second route of the shortest distance between the initial node and the terminal node connected via nodes to transmission lines having X directional and Y directional elements and attributes, respectively, excepting the nodes on the X group first route, to set the second route as an X group second route,

an Y directional route searching modules which searches a third route between the initial node and the terminal node connected via nodes to transmission lines having only Y directional elements and attributes to set the third route as a Y group first route, and searching a fourth route of the shortest distance between the initial node and the terminal connected via nodes to transmission lines having X directional and Y directional elements and attributes, respectively, excluding the nodes on the Y group first route, to set the fourth route as a Y group second route, and

an optimal route selection module which compares a sum of distances on the X group first route and on the X group second route with a sum of distances on the Y group first route and on the Y group 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 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.

9. 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.

10. The network searching apparatus according to claim 9, 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.

11. The network searching apparatus according to claim 10, 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.

12. The network searching apparatus according to claim 9, wherein each of the first trough fourth routes of the shortest distance is searched by means of the Dijkstra method.