Route selection method

The present invention relates to a route selection method for selecting a route satisfying a desired QoS condition from a plurality of routes connecting a start point and an end point, and in particular, an error in advance regarding cost. When a range is specified, the present invention relates to a route selection method in which a plurality of QoS conditions are all satisfied at low cost and a route whose cost is within the error range is selected as the optimum route.

PROBLEM TO BE SOLVED: To select a route which simultaneously satisfies a desired condition with respect to a plurality of QoS (Quality of Service) such as a bandwidth of a communication path, a transmission delay, and an error rate in order to achieve advanced use of a network at a low cost. Technology is indispensable. Further, in ATM (Asynchronous Transfer Mode), which has become popular in recent years, a plurality of QoSs such as a cell allowable delay, a cell transfer maximum delay, and a cell loss rate are defined, and the desired conditions are satisfied with respect to these multiple QoSs. The importance of the communication route selection technology to be obtained is increasing. Here, QoS can be roughly classified into the following three types according to their properties. (1) The QoS value of the additive route is the sum of the QoS values of each link constituting the route, and for example, the transmission delay and the maximum cell transfer delay are applicable. (2) Multiplicative route The QoS value of the route is a function of the product of the QoS values of each link that composes the route. For example, the error rate and the cell loss rate apply. (3) The QoS value of the concave path is the property that becomes the minimum value of the QoS value of each link that constitutes the route, and for example, the bandwidth is applicable.

[0003] Here, a "rule-based route selection method" will be described with reference to the flowchart of FIG. 8 as a conventional technique for selecting a low-cost route in consideration of a plurality of QoSs. Here, as shown in FIG. 9, on a network with 10 nodes (A to J), the lowest cost route that satisfies all the desired QoS conditions from node A (start point) to node J (end point) is selected. Consider the case of selection. It is assumed that the link cost, bandwidth, transmission delay and error rate between each node are as shown in FIG. 10, and the QoS conditions that should be satisfied are the following three conditions. QoS condition 1 ... Bandwidth is 3 or more QoS condition 2 ... Transmission delay is 16 or less QoS condition 3 ... Error rate<u style="single">0.05</u>In step S1, links that do not meet the desired conditions for the concave QoS bandwidth are excluded from the route selection. In the present embodiment, since the bandwidth between DJs is 2 and the QoS condition 1 is not satisfied, the route DJ is excluded from the target of route selection. In step S2, the other QoS conditions that are satisfactory are prioritized and the maximum number of attempts N, which will be described in detail later, is determined. In the present embodiment, it is assumed that the QoS condition 2 (transmission delay) takes precedence over the QoS condition 3 (error rate), and the maximum number of trials N is set to 2.

[0004] In step S3, a cost function or any QoS condition is selected, but the cost function is always selected initially. In step S4, the condition selected in step S3, that is, the path P0 that initially minimizes the cost function, is selected ignoring other QoS conditions. In the example shown in FIG. 10, the route P0 of the start point A G H I end point J is selected. In step S5, it is determined whether the route P0 satisfies all the QoS conditions. In the above-mentioned path P0, the transmission delay becomes 28 and the QoS condition 2 is not satisfied, so the process proceeds to step S8.

[0005] In step S8, it is determined whether or not the number of trials n exceeds the maximum number of trials N, and since it has not yet been exceeded, the process proceeds to step S7, and the number of trials n is incremented by 1 to step S3. Return. In step S3, the high-priority QoS condition 2 (transmission delay) is selected, and in step S4, the route P1 that minimizes the transmission delay is selected ignoring other QoS conditions.

[0006] In the present embodiment, the route P1 of the start point A E H I end point J is selected. In step S5, it is determined whether path P1 satisfies all other QoS conditions at the same time. In this embodiment, the error rate on the above-mentioned route P1 is<u style="single">0.05</u>Since the above-mentioned QoS condition 3 is satisfied as follows, the process proceeds to step S6 assuming that all the QoS conditions are satisfied. In step S6, the relevant route P1 is output as the optimum route.

[0007] If the determination in step S5 is repeatedly denied and the number of trials n exceeds the maximum number of trials N in step S8, information indicating that there is no route that matches the condition is output in step S9.

[Problem to be Solved by the Invention] The above-mentioned prior art has the following problems. (1) Approximation accuracy depends on empirical rules.

[0009] In step S2, a priority order is set for each QoS condition based on the user's empirical rule, and the presence or absence of a route satisfying each QoS condition is sequentially determined according to this priority order. Therefore, without knowledge of the types and properties of each QoS condition, it is not possible to select the optimum or highly accurate route.

[0010] For example, if the QoS condition 3 (error rate) is specified to take precedence over the QoS condition 2 (transmission delay) in step S2, contrary to the above, the start point A B C F is specified in step S3. The end point J is selected as the path P2 with the minimum error rate. The transmission delay of this path P2 is 14, which satisfies all the QoS conditions. The sum of the link costs of the route P2 is 26, which is smaller than the cost of the route P1 32.

[0011] As described above, since the selection path differs depending on the setting of the priority order of QoS, the approximation accuracy depends on the empirical rule. If the number r of QoS conditions increases, the method of assigning the priority order for QoS becomes r! = R × (r-1) × 2 × 1, so the approximation accuracy further depends on the rule of thumb. Become. (2) The approximation accuracy is fixed.

[0012] The approximate ratio is fixedly determined by the number of nodes and links, or the network configuration such as cost, bandwidth, transmission delay, and error rate. For this reason, it may not be possible to flexibly allocate network resources that satisfy the QoS conditions desired by network providers and network users.

[0013] For example, in the above-mentioned conventional method, the route = A E H I J that minimizes the transmission delay is selected regardless of the cost, but the sum of the link costs of this route is 32. On the other hand, the sum of the link costs of the optimum solution is 14, and the approximation ratio is 32/14, which is about 2.3. Therefore, the maximum value of the approximation ratio in any network, that is, the approximation ratio is at least 2.3.

[0014] As described above, in the above-mentioned conventional technique, the approximation ratio is fixedly determined by the network configuration such as the link cost. Therefore, for example, the approximation ratio is made smaller than 2.3, and a route with higher approximation accuracy is arbitrarily selected. There was a problem that even if we tried to request it in our network, we could not meet such a request.

[0015] An object of the present invention is to solve the above-mentioned problems of the prior art, and if an arbitrary approximation error ε is specified at the time of execution without depending on the user's empirical rule, it is desired regardless of the network configuration. It is an object of the present invention to provide a route selection method capable of selecting an optimum route satisfying an approximate ratio (1 + ε).

[Means for Solving the Problems] In order to achieve the above object, in the present invention, among a plurality of routes connecting a start point and an end point, a route that satisfies a plurality of QoS conditions at low cost is selected. In the route selection method to be selected, multiple QoS conditions are set respectively, an acceptable error range is input for the cost of the unknown optimum route, and at least the cost range including the cost of the optimum route is tentatively set. It is determined whether or not the cost range is reduced to the reference range which is a function of the error range, and if it is determined that the cost range is not reduced, the starting point is the cost in order from the lowest cost within the current cost range. A plurality of QoSs from to each node are obtained based on each QoS of the node for which the QoS has already been obtained, and the path from the start point to the end point satisfying all the plurality of QoS conditions is a function of the error range. The cost range was reduced based on whether or not the cost range was found by the reference cost given as, and the optimum route was searched for the reduced cost range.

[0017] According to the above-mentioned route selection method, it becomes possible to select a substantially optimum route within a predetermined error range without being influenced by the operator's knowledge and experience regarding QoS conditions.

BEST MODE FOR CARRYING OUT THE INVENTION The present invention will be described in detail below with reference to the drawings. Here, the basic concept of the present invention will be briefly described first, and then will be described in detail with reference to specific examples.

FIG. 1 is a flowchart showing a schematic operation of a route selection method according to an embodiment of the present invention. Here, as shown in FIG. 10, the optimum route that simultaneously satisfies a plurality of QoS conditions at low cost is selected from a plurality of routes connecting the start point A and the end point J via a plurality of relay nodes. This will be described by taking the case of doing so as an example.

[0020] In step S1, desired conditions related to QoS such as bandwidth, transmission delay, and error rate are set as a plurality of satisfactory QoS conditions. In step S2, an acceptable approximation error ε is input for the cost (optimal cost) of the unknown optimum path that minimizes the cost among the paths that satisfy all of the plurality of QoS conditions. That is, if a route that requires a cost burden up to 1.5 times the optimum cost (that is, the approximation ratio is 1.5) is allowed, 0.5 is input as the approximation error ε.

[0021] In step S3, the cost range for searching for the optimum route (hereinafter, simply referred to as the cost range) is tentatively set by appropriately setting the upper limit value CUB and the lower limit value CLB including the optimum cost. To do. That is, if the optimum cost is predicted to be in the range of, for example, 30 ± 20, 10 (30-20) is set as the upper limit CUB and 50 (30 + 20) is set as the lower limit CLB of the search cost range, and the cost is set. The range is narrowed down to the range of 10 to 50.

[0022] In step S4, the optimal solution cost approximation procedure described in detail later is executed. The optimal solution cost approximation procedure is a preprocessing for narrowing the cost range to be searched in the optimal solution procedure that is executed later in step S6 in advance, and is executed for the purpose of shortening the search time spent in the optimal solution procedure. To.

FIG. 2 is a diagram schematically showing the relationship between the optimum solution cost approximation procedure and the optimum solution solution procedure. For example, if costs 1 to 100 can be taken as the sum of the link costs from the start point A to the end point J, and the optimum cost is to be obtained only by the optimum solution procedure, the start point A and the end point J are first costed. It is necessary to search the entire cost range (1 to 100), such as determining the presence or absence of a route connecting with 1, and then determining the presence or absence of a route connecting with cost 2 if not. Therefore, in the optimum solution procedure, the optimum route and the optimum cost can be obtained, but there is a problem that it takes a long time until then.

[0024] In order to solve such a problem, in the present invention, in step S3 of FIG. 1, the upper limit value CUB and the lower limit value CLB regarding the cost range to be searched are set and the cost range is narrowed in advance. If the cost range is still wide, in order to further narrow the cost range, the optimal solution cost approximation procedure is repeatedly executed prior to the optimal solution procedure to narrow the cost range, and the optimal solution procedure is narrow. It is made to be executed only for.

[0025] More specifically, in the optimum solution cost approximation procedure in step S4, it is determined whether or not the route of the arbitrary cost V satisfies all the plurality of QoS conditions (step S4a). If the route satisfies all the QoS conditions, it is found that the optimum cost is less than or equal to the arbitrary cost V. On the contrary, if there is even one unsatisfied QoS condition, it turns out that the optimum cost is equal to or greater than the arbitrary cost V. Therefore, the cost range can be narrowed based on the determination result (step S4b).

[0026] In step S5, it is determined whether or not the narrowed cost range is sufficiently narrowed, and if the narrowed cost range is still too wide, the process returns to step S4 and the optimum solution cost approximation procedure is repeated. If the cost range is already narrow enough, the optimal solution procedure in step S6 is executed.

[0027] In step S6, a plurality of QoS values for each route are obtained in order from the route having the lowest link cost within the narrowed cost range (step S6a), and the route in which all the QoS conditions are satisfied first is substantially selected. It is regarded as an optimal route (step S6b).

[0028] FIG. 3 is a diagram for explaining the contents of the optimum solution procedure, and FIG. 11 is a flowchart showing the operation thereof.

[0029] In step S51, the cost variable c is set to the initial value 1 in order to obtain each QoS value from the start point A to each node in order from the minimum cost (= 1) for each cost. In step S52, the node variable i is set to the initial value 2 in order to obtain all the QoS from the start point A (first) to the i-th node for each cost.

[0030] In step S53, all QoS from the start point A to the i-th node (here, the second node B) for the route whose cost matches the cost variable c (here, 1). Ask for.

[0031] In step S54, it is determined whether or not the node variable i is n, that is, whether or not the processing has progressed to the end point J for the route whose cost variable is c (= 1). Since it is initially n or less, the process proceeds to step S56. move on. In step S56, the node variable i is incremented by 1 to return to step S53.

Similarly, in the case where the cost variable c is 1, the processes of steps S53, S54, and S56 are repeated every time the node variable i is incremented until the node variable i reaches n. However, in the present embodiment, the costs between the start point A and the nodes B, E, and G are 2, 26, and 2, respectively, as shown in FIG. 10, and the cost variable c (= 1) has already been exceeded. Therefore, as shown in FIG. 3, the QoS value is not registered in each QoS column (1, B) to (1, J) regarding the cost variable c (= 1).

After that, when it is determined in step S54 that the node variable i matches n, the process proceeds to step S55. In step S55, it is determined whether or not the route from the start point A to the end point J satisfies all the QoS conditions. In the present embodiment, there is no route in which the cost variable c is 1, and the QoS value is not registered in each QoS column. Therefore, the determination in step S55 is negative and the process proceeds to step S58. In step S58, the cost variable c is incremented by 1, and then returns to step S52.

Next, for the route in which the cost variable c is 2, the processes of steps S52 to S56 are repeated in the same manner as described above until the node variable i reaches n. In the present embodiment, the cost variable c of the route to the node B and the node G is 2, so as shown in FIG. 3, the QoS columns (2, B) are related to the bandwidth, the transmission delay, and the error rate. (3,2,0.005) is stored as QoS.

However, in the present embodiment, the cost of the route from node A to node B is already 2, and the cost 2 cannot proceed from node B to the next node. Therefore, the QoS column (2, C) The QoS value is not registered in ~ (2, J). Similarly, since node B cannot proceed to the next node even at cost "3", the QoS value (3,2,0.005) is registered in the QoS column (3, B) in the same manner as above, but the QoS column (3, B0.005) QoS values are registered in 3, C) to (3, J).

[0036] Since the process proceeds from node B to node C at the cost 4, the QoS value (3,2,0.005) is registered in the QoS column (4, B) in the same manner as described above, and the QoS column (4, C) is registered. The QoS value (3,4,0.00975) is registered in).

[0037] Similarly, the QoS value up to each node is obtained for each cost variable, and if there is a route to node J, each QoS value at that time is compared with the reference value. As a result, if even one QoS value does not satisfy the reference condition, the process returns from step S55 to step S58, increments the cost variable, and repeats the above process. Then, when all the QoS values of the route to the node J satisfy the reference condition in any of the cost variables, the process proceeds from step S55 to step S57, and the route is determined to be the optimum solution.

[0038] As schematically shown in FIG. 12, as a route to the node X (transit point) between the start point A and the end point J, the route 1 via the node V and the route W via the node W are routed. In the presence of route 2, if one route is superior to the other for all QoS, the QoS of the route to the end point J is the QoS of the route to the end point J via the one route. You will be asked.

[0039] However, when path 1 is superior in terms of bandwidth and transmission delay, but path 2 is superior in terms of error rate, and the superiority or inferiority of both is not uniquely determined in terms of QoS. The problem is which route to obtain the QoS of the route to the end point J.

[0040] In the present embodiment, in order to solve such a problem, there are a plurality of routes that reach the passing node at the same cost, and the superiority or inferiority of QoS in each route leading to the node is not uniquely determined. In this case, among the plurality of routes, it is first determined whether or not the route reaching the end point via any one route satisfies all the QoS conditions, and even one of the plurality of QoS conditions is satisfied. If not, it is determined whether or not the route to the end point via the other one route satisfies all the QoS conditions, and if all the QoS conditions are satisfied, the route is determined to be the optimum route.

[0041] As a result, even if there are a plurality of routes in which the superiority or inferiority of QoS is not uniquely determined at the same cost in the process of reaching the end point, and the route includes all the routes that do not satisfy all the QoS conditions at the end point. If the end point includes at least one route that can satisfy all the QoS conditions, the route can be selected.

[0042] Then, the figure<u style="single">5、6</u>The operation of the route selection method according to the embodiment of the present invention will be described in detail with reference to the flowchart of FIG. 9 and 10, using the network described with reference to FIGS. 9 and 10 as an example. Figure<u style="single">6</u>Is a flowchart showing the main operation of the route selection method to which the present invention is applied.

[0043] In step S11, an allowable approximation error ε is set for a plurality of satisfactory QoS conditions and a cost OPT of an unknown optimum route having the lowest cost among the routes satisfying all the QoS conditions. Will be done. This approximation error ε is preset to a value that can be recognized as a substantially optimum route when the cost of the obtained route is OPT (1 + ε) or less.

[0044] In the present embodiment, 0.5 is set as the approximation error ε, and conditions (reference values) related to QoS of bandwidth, transmission delay, and error rate are set as a plurality of QoS conditions. In this embodiment, it is assumed that the bandwidth is set to 3 or more, the transmission delay is set to 16 or less, and the error rate is set to 0.05 or less.

[0045] In step S12, with respect to the bandwidth showing concaveness in QoS, the link between DJs (bandwidth = 2) that does not satisfy the QoS condition [ 3] is excluded from the target of route selection. In step S13, 1 is tentatively set as the lower limit CLB of the cost range.

[0046] In step S14, the sum from the maximum cost to n (number of nodes) -1 the largest cost is set as the upper limit CUB of the cost range. Since the number of nodes is 10 (A to J) in this embodiment, the sum of the maximum cost 26 (between AE) to the 9th cost is 78 (between 26 [AE] +20 [between CD] +20 [between FJ]]. +2 [between AB] +2 [between AG] +2 [between BC] +2 [between CF] +2 [between EF] = 78) is set as the upper limit CUB.

In step S15, it is determined whether or not the cost range of the search target is sufficiently reduced based on the lower limit CLB and the upper limit CUB, and the lower limit CLB and the upper limit CUB are calculated by the following equation (1). If is satisfied, it is determined that the cost range of the search target has been sufficiently reduced, and the process proceeds to step S51. CUB (1 + ε) CLB (1) Here, the lower limit CLB is 1, the upper limit CUB is 78, the approximation error ε is 0.5, and the above equation (1) does not hold. Proceed to step S16 to further narrow the target cost range. In step S16, the variable V that satisfies the following equation (2) is obtained as a tentative predicted value of the optimum cost.

[0048] In the present embodiment, in order to obtain the predicted value V that satisfies the following equation (2), a is given to the sequence ai represented by the following equation._k&gt; Find the minimum k that satisfies CUB / CLB.

[0049] [Number 1]<img file="JP3662097B2_D0001.tif" />Then V ́ = a_k-2V ́ is obtained, and the predicted value V such that V = V ́ CLB is obtained. In this embodiment, "4" is required as the predicted value V. (CLB^3/4 CUB^1/4) &lt;V (CLB^1/2 CUB^1/2(2) In step S17, the optimum solution cost approximation procedure for narrowing the cost range of the search target is executed with the predicted value V = 4 and the approximation ratio ε = 0.5.

[0050] FIG. 5 is a flowchart showing the operation of the optimum solution cost approximation procedure. In step S31, each link between AE, CD, and FJ is excluded from the target of route selection as a link whose link cost is the predicted value V or more. In step S32, the link cost Cxy between each node XY is replaced with the approximate value C1xy based on the following equation (3). As a result, link costs with small differences can be grouped into the same cost, and the types of values that each link cost can take can be reduced. C1xy = [(n-1) Cxy / (V ε)] (3) However, [...] means that the decimal point of ... is truncated. Here, since the number of nodes n is 10, the predicted value V is 4, and the approximation error ε is 0.5, for example, the cost 2 is replaced with the cost 9, and the cost 3 is the cost 13. Is replaced by.

In step S33, an initial value 0 is set in the cost variable c in order to obtain each QoS value from the start point A to each node in order from the minimum cost (= 0) for each cost. In step S34, it is determined whether or not the following equation (4) is satisfied, and if it is satisfied, the figure<u style="single">6</u>In step S18 of the above, the lower limit CLB of the cost range of the search target is updated from the previous 1 to the predicted value V (= 4), and the cost range of the search target is narrowed. If not, proceed to step S35. c (n-1) / ε (4) In this embodiment, since the right side of Eq. (4) is 18, the process proceeds to step S35. In step S35, the initial value 2 is set in the node variable i in order to obtain all the QoS from the start point A (first) to the i-th node for each cost.

[0052] In the following steps S36 to S38, the QoS is required for the route from the node A to each node whose sum of the link costs is c. That is, in step S36, QoS of the route from the start point A to each node i, in which the sum of the link costs is c (= 0), is obtained. In step S37, the node variable i is compared with the number of nodes n, and if the node variable i does not match the number of nodes n, the node variable i is incremented by 1 in step S38 and the process returns to step S36.

After that, in step S37, when the node variable i matches the number of nodes n, in other words, QoS is required for the route from node A to the end point node J where the sum of the link costs is c. Proceed to S39. In step S39, it is determined whether or not the obtained QoS satisfies all the QoS conditions. Here, the sum of the link costs is 0 and all the QoS conditions are satisfied from the start point A to the end point. Since there is no route to J, the cost variable c is incremented by 1 in step S40 and then returned to step S34. In the present embodiment, the processes of steps S34 to S40 are repeated 17 times and the cost variable c becomes . When it reaches 18 , the judgment of step S34 becomes true before step S39.<u style="single">6</u>Proceed to step S18.

[0054] Figure again<u style="single">6</u>In step S18, the predicted value V (= 4) is set in the lower limit CLB, and then the process returns to step S15. In step S15, it is determined whether or not the space between the upper limit value CUB and the lower limit value CLB is sufficiently narrowed in the same manner as described above. In the present embodiment, the upper limit value CUB is 78 and the lower limit value CLB is 4, and the above equation (1) does not hold. Therefore, it is determined that the cost range is still too wide, and the process proceeds to step S16. In step S16, the predicted value V is calculated based on the equation (2) in the same manner as described above, and this time, 16 is obtained.

In step S17, the optimum solution cost approximation procedure (FIG. 5) is executed in the same manner as described above with the predicted value V = 16 and the approximation error = 0.5, and this time, the determination in step S39 is performed before step S34. Is true<u style="single">6</u>Proceed to step S19. In step S19, the upper limit CUB is updated to 24 according to the following equation (5). Upper limit CUB = (1 + ε) V (5) In the following step S15, it is determined whether or not the space between the upper limit CUB and the lower limit CLB is sufficiently narrowed in the same manner as described above. In the present embodiment, the upper limit CUB is 24, the lower limit CLB is 4, and the above equation (1) is still false. Therefore, the processing after step S16 is repeated again, and the upper limit CUB is 4. 12 2^1/2, The lower limit CLB is "8.2^1/2When the above equation (1) becomes true, it is determined that the cost range of the search target is sufficiently narrowed, and the process proceeds to step S51. In step S51, the upper limit value CUB = 12.2^1/2= 16.97 is recognized as the sum of the link costs of the optimal solution.

[0056] Regarding the method of narrowing the cost range based on the numerical replacement in step S32 in FIG. 5 and the magnitude determination result in step S34, Vol17, No. of "Mathematics of Operations Research" published in February 1992. 1 (MATHEMATICS OF OPERATIONS RESEARCH Vol17, No.1, February 1992) , which is discussed in detail under the title of APPROXIMATION SCHEMES FOR THE RESTRICTED SHORTEST PATH PROBLEM , and the content of this paper is used here.

[0058] In step S61, the route in which the sum of the link costs is below the lower limit CLB and the route in which the sum of the link costs is greater than the upper limit CUB are excluded from the search target. In step S62, the optimum route is obtained for all the remaining routes.

[0059] FIG. 7 shows the first aspect of the present invention.<u style="single">2</u>It is a flowchart which showed the main operation of the route selection method which is an embodiment, and since the same or equivalent process is executed in the step which gave the same code | symbol as above, the description is omitted.

[0060] In the present embodiment, when the determination in step S15 becomes true and the cost range is sufficiently narrowed, in step S71, the optimum solution procedure described with respect to FIGS. Executed on the target. That is, the optimum route is obtained for all routes starting from the lower limit CLB.

[Effects of the Invention] According to the present invention, the following effects are achieved. (1) Since the cost range is narrowed down in advance and the presence or absence of a route from the start point to the end point is determined for each cost only in the narrowed range, the time required to derive the optimum solution is shortened. (2) It becomes possible to derive the optimum solution that satisfies the approximation error specified in advance. (3) If there are multiple routes from the start point to each node at the same cost, and if there is an unsatisfactory QoS condition when reaching the end point via one route, the case where the route is routed through another route. If all the QoS conditions are satisfied when the route is obtained and all the QoS conditions are satisfied, the route is set as the optimum solution. Therefore, if there is even one route that can reach the end point, the route can be selected. Will be.

BRIEF DESCRIPTION OF THE DRAWINGS [FIG. 1] FIG. 1 is a schematic flowchart of a route selection method of the present invention.

FIG. 2 is a diagram schematically expressing the basic concept of the present invention.

FIG. 3 is a diagram for explaining an optimal solution procedure.

[Figure<u style="single">4</u>] It is a flowchart of the optimum solution cost approximation procedure.

[Figure<u style="single">5</u>It is a flowchart of 1st Embodiment of this invention.

[Figure<u style="single">6</u>It is a flowchart of the 2nd Embodiment of this invention.

[Figure<u style="single">7</u>] It is a flowchart of the prior art.

[Figure<u style="single">8</u>] It is a figure which showed the configuration example of a network.

[Figure<u style="single">9</u>] It is the figure which listed the characteristic of each link.

[Figure<u style="single">10</u>] It is a flowchart of the optimum solution procedure.

[Figure<u style="single">11</u>] It is a figure for demonstrating the problem in the route selection.