A communication network system in which a management server performs centralized management of a communication network including a plurality of nodes is known. The management server, when receiving a route setup request regarding a flow, determines a communication route of the flow in the communication network. Such the management server that determines the communication route of the flow is hereinafter also referred to as a “route setup server”.
As an algorithm for calculating a shortest route from a source node to a destination node, “Dijkstra's Algorithm” is commonly known. However, in a case where communications of a plurality of flows are performed between the source node and the destination node, to simply use the Dijkstra's Algorithm results in the same communication route (shortest route) being employed for the plurality of flows. This causes increase in load imposed on the communication route and thus reduction in communication efficiency.
In order to distribute load, it is preferable to set up different communication routes for different flows between the same pair of source node and destination node. To this end, it is considered to extract not only the shortest route but also other communication routes between the source node and the destination node. The followings are known as a technique for calculating a plurality of communication routes from a source node to a destination node.
Patent Literature 1 (Japanese Patent Publication JP-2003-233768) describes a method of calculating a plurality of communication routes from a start-point to an end-point by the use of the Dual Dijkstra's Algorithm. More specifically, regarding all intermediate nodes, respective shortest route trees from the start-point are created by the Dijkstra's Algorithm. Also, regarding all the intermediated nodes, respective shortest route trees from the end-point are created by the Dijkstra's Algorithm. Then, the two kinds of shortest route trees are combined to calculate a plurality of communication routes from the start-point to the end-point through the respectively different intermediate nodes. Besides, a method of calculating a plurality of routes by combining plural times of the Dijkstra's Algorithm is described also in Patent Literature 2 (Japanese Patent Publication JP-2003-23446).
Non-Patent Literature 1 (Jun Inagaki et al., “A method of Determining Various Solutions for Routing Application with a Genetic Algorithm”, The Transactions of the Institute of Electronics, Information and Communication Engineers, D-I, Vol. J82-D-I, No. 8 (19990825), pp. 1102-1111.) describes a method of simultaneously calculating a plurality of communication routes by the use of a genetic algorithm.
Patent Literature 3 (Japanese Patent Publication JP-2007-515906) describes a cost determining method in a multi-hop communication network. The cost determining method includes a step of determining a plurality of concurrently possible next hop nodes with regard to at least one of a plurality of nodes from a source node to a destination node in a network. The plurality of concurrently possible plurality of nodes optimizes a predetermined cost function. Furthermore, the cost determining method includes a step of determining an optimum cost of at least one of the plurality of nodes so as to be equal to the above-mentioned optimized value of the predetermined cost function.