Optimum route calculation method and storage medium which stores optimum route calculation program

• US 7,403,483 B2
• Filed: 06/12/2003
• Issued: 07/22/2008
• Est. Priority Date: 06/17/2002
• Status: Active Grant

• Current Assignee: Rakuten Group, Inc.
• Original Assignee: NEC Corporation
• Inventors: Umezawa, Yohei
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): WONG, XAVIER S
• Application Number:
  US10/459,599
• Publication Number:
  US 20030231599A1
• Time in Patent Office: 1,867 Days
• Field of Search: 370/255, 370/238, 370/252
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops

Abstract

In an optimum route calculation method of calculating an optimum route in a network which has a plurality of nodes and a plurality of transmission paths, and in which a cost is defined for each transmission path, an evaluation value is obtained on the basis of the maximum cost of each transmission path included in a determined route and a route to be evaluated and the number of hops from the determined route to the route to be evaluated. A route is determined on the basis of the evaluation value. A storage medium which stores the optimum route calculation program is also disclosed.

Claims

1. An optimum route calculation method of calculating an optimum route in a network which has a plurality of nodes and a plurality of transmission paths that connect the nodes, and in which a cost is defined for each transmission path, comprising the steps of:

obtaining an evaluation value on a basis of a maximum value of the cost of each transmission path included in a determined route and a route to be evaluated and a number of hops from the determined route to the route to be evaluated; and

determining a route on a basis of the evaluation value, wherein the evaluation value obtaining step comprises a step of multiplying the maximum value of the cost by the number of hops.

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

selecting an apparatus v having a minimum evaluation value C(u) from apparatuses for which routes are undetermined;

determining a route from apparatuses with determined routes to the apparatus v;

registering the apparatus v with the determined route in the apparatuses with the determined routes; and

calculating the evaluation value C(u) for an apparatus u, which is a neighboring apparatus of the apparatus v and is connected to the apparatus v by a direct transmission path, of the apparatuses for which the routes are undetermined,

wherein the multiplying step comprises the steps of;

comparing a value of a maximum cost in links in a route from a starting point to the apparatus v with a cost of a link between the apparatus v and the apparatus u and defining the higher cost as the maximum cost in the route from the starting point to the apparatus u;

multiplying the maximum cost by a value of the number of hops in the route from the starting point to the apparatus u to thereby calculate the evaluation value of the apparatus u; and

in case the evaluation value of the apparatus u has already been calculated, comparing the evaluation value with the evaluation value obtained in the calculation step, and if the evaluation value obtained in the calculation step is smaller, then updating the evaluation value as a new evaluation value C(u) of the apparatus u.

2. An optimum calculation method of calculating an optimum route in a network which has a plurality of nodes and a plurality of transmission paths that connect the nodes, and in which a cost is defined for each transmission path, comprising the steps of:

obtaining an evaluation value on a basis of a maximum value of the cost of each transmission path included in a determined route and a route to be evaluated and a number of hops from the determined route to the route to be evaluated; and

determining a route on a basis of the evaluation value, wherein the evaluation value obtaining step comprises a step of adding a value obtained by multiplying the maximum value of the cost by a coefficient α

(α

is an arbitrary positive value (α

≧

1)) to a value obtained by multiplying the number of hops by a coefficient β

(β

is an arbitrary positive value (β

≧

1)).

4. The method according to claim 2, further comprising the steps of:

selecting an apparatus v having a minimum evaluation value C(u) from apparatuses for which routes are undetermined;

determining a route from apparatuses with determined routes to the apparatus v;

registering the apparatus v with the determined route in the apparatuses with the determined routes; and

calculating the evaluation value C(u) for an apparatus u, which is a neighboring apparatus of the apparatus v and is connected to the apparatus v by a direct transmission path, of the apparatuses for which the routes are undetermined,

wherein the multiplying step comprises the steps of;

comparing a value of a maximum cost in links in a route from a starting point to the apparatus v with a cost of a link between the apparatus v and the apparatus u, and defining a higher cost as the maximum cost in the route from the starting point to the apparatus u;

adding a value obtained by multiplying the maximum cost by a coefficient α

(α

is an arbitrary positive value (α

≧

1)) to a value obtained by multiplying a number of hops in the route from the starting point to the apparatus u by a coefficient β

((β

is an arbitrary positive value (β

≧

1)) to calculate the evaluation value of the apparatus u; and

in case the evaluation value of the apparatus u has already been calculated, comparing the evaluation value with the evaluation value obtained in the calculation step, and if the evaluation value obtained in the calculation step is smaller, then updating the evaluation value as the new evaluation value C(u) of the apparatus u.

5. A computer-readable recording medium on which is tangibly recorded a program of machine-readable instructions that, when executed, cause a computer to execute processing for calculating an optimum route in a network which has a plurality of nodes and a plurality of transmission paths that connect the nodes, and in which a cost is defined for each transmission path, wherein the program comprises a program which causes the computer to execute the steps of:

obtaining an evaluation value on a basis of a maximum value of the cost of each transmission path included in a determined route and a route to be evaluated and a number of hops from the determined route to the route to be evaluated; and

determining a route on a basis of the evaluation value, wherein the program comprises a program which causes a computer to execute a step of multiplying the maximum value of the cost by the number of hops.

7. A computer-readable recording medium according to claim 5, wherein the program comprises a program which causes a computer to execute the steps of:

selecting an apparatus v having a minimum evaluation value C(u) from apparatuses for which routes are undetermined;

determining a route from apparatuses with determined routes to the apparatus v;

registering the apparatus v with the determined route in the apparatuses with the determined routes;

calculating the evaluation value C(u) for an apparatus u, which is a neighboring apparatus of the apparatus v and is connected to the apparatus v by a direct transmission path, of the apparatuses for which the routes are undetermined;

comparing a value of a maximum cost in links in a route from a starting point to the apparatus v with a cost of a link between the apparatus v and the apparatus u and defining a higher cost as the maximum cost in the route from the starting point to the apparatus u;

multiplying the maximum cost by a value of a number of hops in the route from the starting point to the apparatus u to calculate the evaluation value of the apparatus u; and

in case the evaluation value of the apparatus u has already been calculated, comparing the evaluation value with the evaluation value obtained in the calculation step, and if the evaluation value obtained in the calculation step is smaller, then updating the evaluation value as the new evaluation value C(u) of the apparatus u.

6. A computer-readable medium on which is tangibly recorded a program of machine-readable instruction that, when executed, causes a computer to execute processing for calculating an optimum route in a network which has a plurality of nodes and a plurality of transmission paths that connect the nodes, and in which a cost is defined for each transmission path, wherein the program comprises a program which causes the computer to execute the steps of:

obtaining an evaluation value on a basis of a maximum value of the cost of each transmission path included in a determined route and a route to be evaluated and a number of hops from the determined route to the route to be evaluated; and

determining a route on a basis of the evaluation value, wherein the program comprises a program which causes a computer to execute a step of adding a value obtained by multiplying the maximum value of the cost by a coefficient α

(α

is an arbitrary positive value (α

≧

1)) to a value obtained by multiplying the number of hops by a coefficient β

(β

is an arbitrary positive value (β

≧

1)).

8. A computer-readable recording medium according to claim 6, wherein the program comprises a program which causes a computer to execute the steps of:

selecting an apparatus v having a minimum evaluation value C(u) from apparatuses for which mutes are undetermined;

determining a route from apparatuses with determined routes to the apparatus v;

registering the apparatus v with the determined route in the apparatuses with the determined routes;

calculating the evaluation value C(u) for an apparatus u, which is a neighboring apparatus of the apparatus v and is connected to the apparatus v by a direct transmission path, of the apparatuses for which the routes are undetermined;

comparing a value of a maximum cost in links in a route from a starting point to the apparatus v with a cost of a link between the apparatus v and the apparatus u and defining a higher cast as the maximum cost in the route from the starting point to the apparatus u;

adding a value obtained by multiplying the maximum cost by a coefficient α

(α

is an arbitrary positive value (α

≧

1)) to a value obtained by multiplying a number of hops in the route from the starting point to the apparatus u by a coefficient β

(β

is an arbitrary positive value (β

≧

1)) to calculate the evaluation value of the apparatus u; and

in case the evaluation value of the apparatus u has already been calculated, comparing the evaluation value with the evaluation value obtained in the calculation step, and if the evaluation value obtained in the calculation step is smaller, then updating the evaluation value as the new evaluation value C(u) of the apparatus u.

9. An optimum route calculation system comprising:

a plurality of nodes;

a plurality of transmission paths that connect the nodes; and

an optimum route calculation apparatus which calculates an optimum route in a network in which a cost is defined for each transmission path,

wherein said optimum route calculation apparatus comprises;

an evaluation value calculation means for obtaining an evaluation value on a basis of a maximum value of the cost of each transmission path included in a determined route and a route to be evaluated and a number of hops from the determined route to the route to be evaluated; and

a route determination means for determining a route on a basis of the evaluation value, wherein the evaluation value obtaining step comprises a step of multiplying the maximum value of the cost by the number of hops.