NETWORK SYSTEM, PATH CALCULATION METHOD, AND PATH CALCULATION PROGRAM

• US 20100208722A1
• Filed: 10/17/2008
• Published: 08/19/2010
• Est. Priority Date: 10/18/2007
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iizawa, Yohei, Nishioka, Itaru
• Application Number:
  US12/738,720
• Publication Number:
  US 20100208722A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A route decision system is arranged in each domain of a multi-domain network. The route decision system comprises a topology information collecting unit which collects topology information, a route calculation request responding unit which receives a route calculation request requesting route calculation of a redundant path from a start node to an end node, and a route calculating unit which performs route calculation in response to the route calculation request using the topology information in consideration of a restriction. After a domain from a starting point domain where the start node is present to an end point domain where the end node is present is set, route calculation of the redundant path is sequentially performed at each domain from the end point domain toward the starting point domain through an intermediate domain.

Claims

1. A network system comprising:

a plurality of route decision systems which are distributed and arranged in a multi-domain network divided into a plurality of route calculation domains, and wherein

each route decision system comprises a topology information collecting unit which collects topology information, a route calculation request responding unit which receives a route calculation request requesting route calculations of a redundant path from a start node to an end node, and a route calculating unit which performs route calculation in response to the route calculation request using the topology information in consideration of a restriction, and

after a route calculation domain to be passed through from a route calculation domain where the start node is present to a route calculation domain where the end node is present is set, a route of the redundant path between the start node and the end node is calculated by causing the route calculating unit to sequentially perform route calculation of the redundant path in each route decision system from the route calculation domain where the end node is present toward the route calculation domain where the start node is present, and by combining routes of the redundant path calculated by respective route decision systems together.

2. The network system according to claim 1, wherein the route calculation request from an originator which has issued a request is sequentially transmitted from a route decision system belonging to the route calculation domain where the start node is present to a route decision system belonging to the route calculation domain where the end node is present, and a route calculation domain where a route decision system to which the route calculation request has been transmitted belongs is set as a route calculation domain to be used for the route calculation.

3. The network system according to claim 2, wherein when performing route calculation of the redundant path, each of the route decision systems issues a route calculation request including a result of the route calculation of the redundant path to a transmission originator of the route calculation request.

4. The network system according to claim 3, wherein each of the route decision systems further comprises a route calculation domain managing unit which creates adjacency information including information to specify a route calculation domain adjoining a local route calculation domain to which each of the route decision systems belongs based on reachability information from another route decision system and collected by the topology information collecting unit, and a route-decision-system selecting unit which selects a route calculation domain where a route decision system to which the route calculation request received by the route calculation request responding unit is to be transmitted belongs using the adjacency information.

5. The network system according to claim 4, wherein the route calculation domain managing unit analyzes reachability information from the another route decision system and from the end node, and stores, as a reachability information table, a boundary node between the local route calculation domain to which the route calculation domain managing unit belongs and another route calculation domain in association with costs when each boundary node is used from the route calculation domain managing unit to a route decision system belonging to another route calculation domain and to the end node, and the route-decision-system selecting unit selects, as a route decision system to which the route calculation request is to be transmitted, a route calculation domain adjoining through a boundary node which can reach the end node among route calculation domains adjoining a local route calculation domain to which the route-decision-system selecting unit belongs by referring to the reachability information table and the adjacency information.

6. The network system according to claim 5, wherein in selection of the route decision system to which the route calculation request is to be transmitted, a boundary node with a minimum cost is specified among the boundary nodes which can reach the end node, and a route decision system with a minimum cost among route calculation domains adjoining through the specified boundary node is selected as a route decision system to which the route calculation request is to be transmitted.

7. The network system according to claim 4, wherein the route-decision-system selecting unit sets a route calculation domain adjoining the local route calculation domain to which the route-decision-system selecting unit belongs as a transmission destination of the route calculation request, and when there are a plurality of transmission destinations, the route-decision-system selecting unit replicates the route calculation request, and transmits the route calculation requests to respective route decision systems belonging to respective route calculation domains each of which is set as the transmission destination.

8. The network system according to claim 7, wherein when receiving the route calculation responses from the plurality of route decision systems, the route calculating unit of the route decision system belonging to the route calculation domain where the start node is present performs route calculation using the received respective route calculation responses, compares route calculation results, and sets a route to be included in a route calculation response to be transmitted to the start node.

9. The network system according to claim 4, wherein when the route calculation request response receives the route calculation request, the route calculating unit determines whether or not the end node is present in a local route calculation domain to which the route calculating unit belongs, and requests the route-decision-system selecting unit to select a route calculation domain of a transmission destination of the route calculation request when determining that the end node is not present.

10. The network system according to claim 9, wherein when determining that the end node is present in the local route calculation domain to which the route calculating unit belongs, the route calculating unit calculates a route candidate of a redundant path between a boundary node which is between the local route calculation domain to which the route calculating unit belongs and a route calculation domain to which a route calculation system that is a transmission originator of the route calculation request belongs, and the end node using the topology information, and issues a route calculation response including the calculated route candidate of the redundant path to the transmission originator of the route calculation request through the route calculation request responding unit.

11. The network system according to claim 10, wherein when the route calculation request responding unit receives a route calculation result from a route decision system of the route calculation request transmission destination, the route calculating unit determines whether or not the start node is present in the local route calculation domain to which the route calculating unit belongs, and when determining that the start node is not present, calculates a route candidate of a redundant path in the local route calculation domain to which the route calculating unit belongs using such topology information that is obtained by adding a topology having an abstracted route candidate of a redundant path calculated in a route decision system of the route calculation request transmission destination to the aforementioned topology information, and issues a route calculation response including the calculated route candidate of the redundant path to a route decision system of a transmission originator of the route calculation request through the route calculation request responding unit.

12. The network system according to claim 11, wherein when determining that the start node is present in the local route calculation domain to which the route calculating unit belongs, the route calculating unit calculates a route candidate of a redundant path in the local route calculation domain to which the route calculating unit belongs using such topology information that is obtained by adding a topology having an abstracted route candidate of the redundant path calculated in the route decision system of the route calculation request transmission destination to the aforementioned topology information, selects a route candidate from the acquired route candidates, and issues a route calculation response, including a route that routes of the redundant path in respective route calculation domains calculated by respective route decision systems are combined together, to a request originator of the route calculation request through the route calculation request responding unit.

13. The network system according to claim 11, wherein in abstraction of the route candidate, a route candidate of a redundant path acquired from another route decision system is registered in topology information as a link with a restriction connected to a virtual end node.

14. The network system according to claim 4, wherein the reachability information is acquired by an IGP (Interior Gateway Protocol).

15. The network system according to claim 4, wherein the reachability information is acquired by an SNMP (Simple Network management Protocol).

16. A route decision system arranged correspondingly to at least one of a plurality of route calculation domains in a multi-domain network, the route decision system comprising:

a topology information collecting unit which collects topology information;

a route calculation request responding unit which receives a route calculation request requesting route calculation of a redundant path from a start node to an end node;

a route-decision-system selecting unit which selects a route calculation domain where a route decision system to which the route calculation request is to be transmitted belongs when the end node is not present in a local route calculation domain to which the route-decision-system selecting unit belongs; and

a route calculating unit which performs route calculation of the redundant path using the topology information in consideration of a restriction when the end node is present in a local route calculation domain to which the route calculating unit belongs, and issues a route calculation response including a result of the route calculation to a transmission originator of the route calculation request.

17. The route decision system according to claim 16, further comprising an interval path abstracting unit which abstracts a route calculation result included in the route calculation response, and adds the abstracted route calculation result to topology information, and wherein when the route calculation request responding unit receives the route calculation response from another route decision system, the route calculating unit causes the interval path abstracting unit to calculate a route of the redundant path using topology information that the route calculation result included in the route calculation response is abstracted and added, and issues a route calculation response including a result of the route calculation to the transmission originator of the route calculation request.

18. A method of calculating a route of a redundant path across route calculation domains from a start node to an end node by a plurality of route decision systems which are distributed and arranged in a multi-domain network and which work together, the method comprising:

a step of setting a route calculation domain through which a route from the start node to the end node passes using adjacency information retained by each route decision system; and

a step of causing a route decision system belonging to the set route calculation domain to recursively perform path calculation from a route decision system belonging to a route calculation domain where the end node is present toward a route decision system belonging to a route calculation domain where the start node is present.

19. The route calculation method according to claim 18, wherein in the step of setting a route calculation domain, a route calculation domain which can reach the route calculation domain where the end node is present among adjoining route calculation domains is sequentially selected from the route calculation domain where the start node is present.

20. The route calculation method according to claim 18, wherein in the step of setting a route calculation domain, all route calculation domains which can be passed through from the route calculation domain where the start node is present to the route calculation domain where the end node is present are selected, the step of performing path calculation is executed for each selected route calculation domain, and the route between the start node and the end node is set by comparing costs of routes of a redundant path acquired by the path calculation.

21. The route calculation method according to claim 18, wherein in the step of performing path calculation, a calculation result of a redundant path calculated in a route calculation domain which is closer to the end node than a local route calculation domain is received, and route calculation is performed using a topology in a route calculation domain that a link with a restriction to a virtual end node maintaining information on a redundant restriction is added.

22. The route calculation method according to claim 21, wherein routes from a virtual end node to each boundary node are collectively calculated as shortest tree routes for a topology to which a link with a restriction to a virtual end node is added.

23. The route calculation method according to claim 21, wherein in the step of performing path calculation, in selection of a route candidate of a redundant path, a route that a sum of a cost of a current path of the redundant path and a cost of a backup path of the redundant path becomes minimum is selected.

24. The route calculation method according to claim 21, wherein in the step of performing path calculation, in selection of a route candidate of a redundant path, a route that a cost of a current path of the redundant path is minimum is selected.

25. A non-transitory computer-readable medium storing a program that allows a computer to execute a process of calculating a route of a redundant path across route calculation domains from a start node to an end node in a multi-domain network, the program allowing the computer to execute:

a process of receiving a route calculation request requesting route calculation of the redundant path;

a process of selecting a route calculation domain where a route decision system to which the route calculation request is to be transmitted belongs when the end node is not present in a local route calculation domain to which a route decision system belongs; and

a process of performing route calculation of the redundant path in consideration of a restriction using topology information when the end node is present in the local route calculation domain to which the route decision system belongs, and of issuing a route calculation response including a result of the route calculation to a transmission originator of the route calculation request.