JP3899095B2 - Route control apparatus and route selection method - Google Patents

Description

  The present invention relates to a packet communication technology, and more particularly to a route selection technology for selecting an optimum route used for packet communication.

  In recent years, the traffic volume of a large-scale backbone network in the center of the Internet has increased explosively due to the rapid increase in the number of users of the Internet and the rapid spread of applications that exchange large amounts of data. Therefore, there is a demand for improving the capacity of the backbone network to accommodate traffic.

In such a general routing protocol used on the Internet, for example, a route having the shortest total hop count is selected as an optimum route considering only the network topology without considering the traffic volume. For this reason, due to the increase and fluctuation of the traffic volume, the load concentrates on a specific link or node and the communication quality deteriorates.
On the other hand, it is conceivable to increase the amount of traffic that can be accommodated by making capital investment in the communication network. However, in such a method, the use efficiency of the network is reduced in proportion to the increase in traffic, and the cost is increased. Therefore, there is a possibility that the price competitiveness of the Internet service fee is reduced.

As a method for overcoming such a situation, a traffic engineering technique that dynamically distributes traffic according to the traffic situation in the network has been studied (see, for example, Non-Patent Document 1).
This type of traffic engineering technology uses technology such as MPLS (Multi-Protocol Label Switching), sets multiple routes for the same destination, and moves the links and nodes that make up each route according to the traffic situation. In this way, traffic is dynamically distributed in the network.

  Conventionally, the optimal route selection method used in such route control is based on the Dijkstra algorithm, and there is a MIN-MAX algorithm that holds the minimum value of the link cost on the route and selects the route having the largest value. In this algorithm, the link cost represented by the physical bandwidth of the link and the inverse of the load is used as the link evaluation value, and the optimum for evaluating the route based on the minimum value of the link cost of each link constituting the route. A path that can accommodate a large amount of packet communication traffic is selected by calculating an optimization parameter value and selecting a path that maximizes the optimization parameter value (see, for example, Patent Document 1) )

The applicant has not yet found prior art documents related to the present invention by the time of filing other than the prior art documents specified by the prior art document information described in this specification.
JP 2001-244974 A "Next Generation Internet and Traffic Engineering", IEICE Transactions VOL.J85-B No.6, pp875-889, IEICE, June 2002

  However, in such a conventional technique, when a new route to an arbitrary node is selected, the optimization parameter value of the node for which the route from the transmission source node has already been selected and confirmed is used to optimize the arbitrary node. Since the parameter values were calculated, in the network topology separated at the disconnection point, traffic concentrates on the specific link after the disconnection point, and there is a high possibility that the communication quality deteriorates and the network utilization efficiency decreases. There was a problem that the service quality of the backbone network was degraded.

  For example, when the MIN-MAX algorithm is used for route selection, the minimum value of the link cost from the transmission source node to an arbitrary node is held as an optimization parameter value, and the next parameter is transmitted to the next node using the optimization parameter value. A route is selected. For this reason, if there is a topology in which multiple route candidates must pass through a specific node as a cut point, and the minimum cost from the source node to the specific node is smaller than the minimum value after the specific node, specify After a node, the minimum link cost will not change regardless of which route candidate is selected. Therefore, after the specific node, any route candidate having the minimum cost to the specific node is always selected, and traffic concentrates on the specific link.

  In addition, this problem is caused by the influence of the cutting point multiple times on the route selection in a network separated by a plurality of cutting points. For example, in a network in which areas are connected by a small number of links, such as inter-regional connections in an ISP (Internet Service Provider) backbone network, a route for distributing and distributing traffic across the areas is defined as MIN-MAX. Prominent when selecting using an algorithm. For this reason, there is a practical problem that it is difficult to distribute routes between regions in an ISP backbone network across the country.

  The present invention is for solving such a problem, and it is possible to avoid the concentration of traffic after a specific node corresponding to the disconnection point of the network topology, and to increase the load distribution effect using the traffic engineering technique. An object is to provide an apparatus and a route selection method.

  In order to achieve such an object, a routing control device according to the present invention is provided in a packet communication network including a plurality of nodes connected in a network via a link, and the following is performed from a transmission source node that performs packet communication. A route control device that selects a route from a transmission source node to a desired destination node by sequentially selecting a route to a node from the network, and includes link information indicating a packet transfer status in each link. When selecting a link information collection unit that collects from a node and a route from a source node to an arbitrary node, based on the optimization parameter value that evaluates the route to the node, either of the routes to the node The route selection part to be selected as the route to the node, the link information collected by the link information collection part, and the nodes for which no route has been selected An optimization parameter value, a route to a node selected by the route selection unit, and a storage unit that stores an optimization parameter value of each node constituting the route, and the route selection unit optimizes an arbitrary node u When calculating the optimization parameter value, the optimization parameter value of the node v that has been selected from the storage unit and is adjacent to the node u via the link and the link of the link from the node v to the node u is read. A new optimization parameter value of the node u is calculated from the information and the optimization parameter value of the node u, and the optimization parameter value of each node constituting the route is selected as a reference for the route selected by the route selection unit. If there is no change between nodes over the number of hops, the optimization parameter value stored in the storage unit for the node for which no route has been selected is adjacent to the node. Initializing based on the link of the link information between the path selected node that.

  At this time, when the optimization parameter value of the node u is calculated by the route selection unit, the link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm. The minimum value is selected from the link cost indicating the link evaluation and the optimization parameter value of the node v stored in the storage unit, and the optimization parameter of the node u stored in the storage unit is stored in the minimum value Any of the maximum values may be calculated as a new optimization parameter value of the node u.

  Alternatively, when the route selection unit calculates the optimization parameter value of the node u, the link obtained from the link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm. The maximum value of the link cost indicating the evaluation of the node v and the optimization parameter value of the node v stored in the storage unit is selected, and this maximum value and the optimization parameter value of the node u stored in the storage unit May be calculated as a new optimization parameter value of the node u.

  The route selection method according to the present invention is a route control device provided in a packet communication network composed of a plurality of nodes connected in a network via a link, and sequentially selects the next node from a transmission source node that performs packet communication. A route selection method for selecting a route to a desired destination node by selecting, a link information collecting step for collecting link information indicating a packet transfer status in each link from each node, and an arbitrary from a source node When selecting a route to a node, a route selection step for selecting one of the routes to the node as a route to the node based on an optimization parameter value for evaluating each route to the node, and collecting link information The link information collected in the step, the optimization parameter value of the node for which no route is selected, and the route selection step And a storage step for storing the optimization parameter value of each node constituting the route in the storage unit, and the route selection step calculates the optimization parameter value of an arbitrary node u. Read from the storage unit, the optimization parameter value of the node v adjacent to the node u via the link, the link information of the link from the node v to the node u, the link information of the node u The parameter calculation step for calculating a new optimization parameter value of the node u from the optimization parameter value and the optimization parameter value of each node constituting the route for the route selected in the route selection step is the reference hop number. If there is no change between the nodes, the optimization parameter value of the node that has not been selected the route stored in the storage unit And a parameter initializing step of initializing based on the link information of the link between the Routed nodes adjacent to the node.

  At this time, when the optimization parameter value of the node u is calculated in the parameter calculation step, the obtained from the link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm. The minimum value is selected from the link cost indicating the link evaluation and the optimization parameter value of the node v stored in the storage unit, and the optimization parameter of the node u stored in the storage unit is stored in the minimum value Any of the maximum values may be calculated as a new optimization parameter value of the node u.

  Alternatively, when the optimization parameter value of the node u is calculated in the parameter calculation step, the link obtained from the link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm. The maximum value of the link cost indicating the evaluation of the node v and the optimization parameter value of the node v stored in the storage unit is selected, and this maximum value and the optimization parameter value of the node u stored in the storage unit May be calculated as a new optimization parameter value of the node u.

According to the present invention, when calculating the optimization parameter value of an arbitrary node u, the optimization parameter value of the node v, which has been read from the storage unit, has already been selected and is adjacent to the node u via the link A new optimization parameter value of the node u is calculated from the link information of the link from the node v to the node u and the optimization parameter value of the node u, and the route selected by the route selection unit If the optimization parameter value of each node constituting the node does not change between nodes over the number of reference hops, the optimization parameter value of the node for which the route is not selected stored in the storage unit is adjacent to the node. Since it is initialized based on the link information of the link with the route selected node to be routed, it is only after the specific node corresponding to the disconnection point of the network topology. Route can be avoided immobilization of optimization parameter values used in the selection that.
Therefore, traffic concentration after a specific node can be avoided, and the load distribution effect using the traffic engineering technique can be enhanced.

Next, embodiments of the present invention will be described with reference to the drawings.
[Network model]
First, a communication network to which a path control device according to an embodiment of the present invention is applied will be described with reference to FIG. FIG. 1 is a block diagram illustrating an example of a network model of a communication network to which a route control device according to an embodiment of the present invention is applied.
This communication network includes user accommodation devices 30 and 36, relay devices 31 to 35, and a route control device 20. Each user terminal 10 and 11 is connected via a link 100 and 101 in a user network 201 and 202, respectively. It is accommodated in user accommodation devices 30 and 36.

The user accommodation devices 30 and 36 are connected by links 102 to 109 and relay devices 31 to 35. The path control device 20 is connected to the user accommodation devices 30 and 36 and the relay devices 31 to 35 via the management network 300.
Hereinafter, a backbone network composed of the user accommodation devices 30 and 36, the relay devices 31 to 35, and the links 102 to 109 connecting the user accommodation devices 30 and 36 and the relay devices 31 to 35 is referred to as the core network 200. To do. The user accommodation devices 30 and 36 and the relay devices 31 to 35 are referred to as nodes constituting the core network 200.

[Route control device]
Next, a route control device according to an embodiment of the present invention will be described with reference to FIG. FIG. 2 is a block diagram showing the configuration of the path control device according to the embodiment of the present invention.
The route control device 20 is composed of an information processing device having a computer as a whole, and is provided with a link information collection unit 21, a route selection unit 22, a route control unit 23, and a storage unit 24. Among them, the link information collection unit 21, the route selection unit 22, and the route control unit 23 are arithmetic processing units (not shown) that realize the functional units by causing the CPU and the program to cooperate with each other by executing the programs. ), And a communication interface unit (not shown) that transmits and receives control packets via the management network 300.

  The link information collection unit 21 includes a functional unit realized by the arithmetic processing unit. From the communication interface unit via the management network 300, the user accommodation devices 30 and 36 and the relay devices 31 to 35 are connected to each link. A function of collecting link information indicating a packet transfer status, for example, traffic volume, and a function of updating a link cost table stored in the storage unit 24 based on a cost value obtained from the collected link information (for example, reciprocal of traffic volume). Have.

  The route selection unit 22 includes a functional unit realized by the arithmetic processing unit, and selects a route from a packet communication transmission source node (originating node) to a destination node (destination node) using the MIN-MAX algorithm. And a function of storing the route as a route selection result and the optimization parameter value of the node on the route in the optimization parameter table of the storage unit 24, and searching the optimization parameter table to optimize each node on the route If the optimization parameter value has not changed between the function to check the parameter value change status and the number of reference hops, the optimization parameter value of each node that is a selection candidate It has a function of continuing the route selection by initializing based on the link information of the link with the node.

  The optimization parameter value referred to in the present invention is a value used as a selection criterion when selecting a route from a packet communication source node to an arbitrary node u, and evaluates the route to the node u. It is an evaluation value. For example, in the MIN-MAX algorithm, when selecting a route to an arbitrary node u, an optimization parameter value is obtained for each route to the node u, and a route having the maximum optimization parameter value is selected. At this time, for the route to the node v that has already been route-selected and is adjacent to the node u via the link, for example, the minimum value of the cost of the link constituting the selected route from the source node to the node v, that is, The optimization parameter value of node u is used.

The route control unit 23 includes a functional unit realized by the arithmetic processing unit, and has a function of searching for a desired route from each route stored in the storage unit 24, and the searched route from the communication interface unit to the management network. And a function to be set in the user accommodation devices 30 and 36 and the relay devices 31 to 35 via 300.
The storage unit 24 includes a storage device such as a hard disk or a memory, and manages the link cost table 24A, the optimization parameter table 24B, and the MIN-MAX algorithm parameter table 24C in a database. The link information collection unit 21, the route selection unit 22 According to the access from the route control unit 23, it has a function of providing a managed value or changing and storing it.

3 is a configuration example of the link cost table 24A managed by the storage unit 24, and FIG. 4 is a configuration example of the optimization parameter table 24B managed by the storage unit 24. In either case, examples of values before the start of route selection are shown.
In the link cost table 24A, the link 102-109 connecting the user accommodation devices 30, 36 and the relay devices 31-35 is obtained from the link information collected by the link information collection unit 21 as the link evaluation value. Link cost is managed. In the optimization parameter table 24B, the route having the user accommodation devices 30 and 36 and the relay devices 31 to 35 as destination nodes and the optimization parameter value of each node constituting the route are managed. In the MIN-MAX algorithm parameter table 24C, as various parameters used in the MIN-MAX algorithm, for example, a route as a selection result and optimization parameter values of each node are managed.

  In the present embodiment, when the route selection unit 22 of the route control device 20 calculates the optimization parameter value of an arbitrary node u, the route read from the storage unit 24 has already been selected and is linked to the node u. A new optimization parameter value of the node u is calculated from the optimization parameter value of the adjacent node v via the link information of the link from the node v to the node u and the optimization parameter value of the node u, For the route selected by the route selection unit 22, if the optimization parameter value of each node constituting the route has not changed between the nodes over the reference hop count, the route stored in the storage unit 24 is selected. The optimization parameter value of a node that has not been initialized is initialized based on the link information of the link between the node adjacent to the node and the route selected.

As a result, while selecting the route from the transmission source node to the destination node, the change of the optimization parameter value of the node constituting the route to an arbitrary node is confirmed, and the optimization parameter value does not fluctuate over the reference hop number. In this case, it is possible to initialize the optimization parameter value and continue the route selection.
Therefore, it is possible to probabilistically determine the passage of a specific node corresponding to the disconnection point of the network topology, avoid traffic concentration after the specific node, and enhance the load distribution effect using the traffic engineering technique.

[Operation of route control device]
Next, the operation of the path control device according to the embodiment of the present invention will be described with reference to FIG. FIG. 5 is a flowchart showing route selection processing in the route control device according to the embodiment of the present invention.
In the communication network of FIG. 1 described above, the optimum route is determined based on the MIN-MAX algorithm from the routes from the user accommodation device 30 serving as the transmission source node to the user accommodation device 36 serving as the destination node of the packet. A case of selection will be described as an example.

  First, the route control device 20 uses the link information collection unit 21 to collect link information of the links 102 to 109 from the user accommodation devices 30 and 36 and the relay devices 31 to 35 via the management network 300, and the link information. The link cost obtained from the above, for example, consisting of the reciprocal of the traffic volume, is stored in the link cost table 24A of the storage unit 24 (step 500). In this example, it is assumed that the link costs having the contents shown in FIG. 3 are stored as the link cost table 24A in the initial state.

Next, the path control device 20 uses the MIN-MAX algorithm (see, for example, Patent Document 1) to sequentially select a path from the transmission source node to an arbitrary node from the network, thereby transmitting the transmission source. A route from a node to a desired destination node is selected. At this time, as a route from the transmission source node to an arbitrary node, a route from which the minimum value of the cost of each link constituting each route is maximized is selected from among the routes to the node.
FIG. 6 is an explanatory diagram showing definitions and notations relating to the MIN-MAX algorithm used in this case. In this notation, the device means a user accommodation device or a relay device.

At the start of processing of the MIN-MAX algorithm, each parameter is initialized. FIG. 7 shows the stored contents of the MIN-MAX algorithm parameter table 24C in the initial state. FIG. 8 shows the contents stored in the optimization parameter table 24B in the initial state.
At this time, the value of the MIN-MAX algorithm parameter in FIG. 7 is the same as the value of the parameter shown in the definition of FIG. Of these, the set V is a set of all devices that are subject to route selection. The set U is a set of devices whose paths are determined, and is Φ (empty set) in the initial state. Therefore, the set V-U is a set of devices that are undefined routes, that is, route selection candidates. The route is a route to an arbitrary device determined by the route selection process, and C is an optimization parameter value for each device. In the route selection operation of FIG. 5, the reference hop number for determining whether the optimization parameter value needs to be initialized is “3”.

[First step of MIN-MAX algorithm]
First, the route control device 20 performs a route selection process of the first step using the MIN-MAX algorithm. In the MIN-MAX algorithm parameter table 24C of FIG. 7, the cost C (30) = “∞ (infinite)” of the user accommodation device 30 among the devices included in the set VU is the largest, so the user accommodation. Device 30 is included in set U. As a result, “30 → 30” is obtained as a route from the user accommodation device 30 that is the transmission source node to the user accommodation device 30 that is one of the route selection target nodes (step 501). At this time, the route with the smallest link cost maximum is the route from the user accommodation device 30 to the user accommodation device 30, but since the link is not included, it has not been determined substantially.

  Subsequently, among the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the user accommodating device 30 via the link, that is, the optimization parameter value, is expressed as MIN-MAX. Based on the algorithm, the cost is updated to the minimum value of the link on the route to the device. In this case, the cost C (31) of the relay device 31 adjacent to the user accommodation device 30 is “3” from the link 102 of the link cost table 24A of FIG. Similarly, the cost C (32) of the relay device 32 adjacent to the user accommodation device 30 is “4” from the link 103 (step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 9 and 10, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 9 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, in the route to the user accommodation device 30, the portion where the optimization parameter value has not changed is the maximum of 0 hops of “30 (∞) → 30 (∞)” and the reference hop number “ Since it is smaller than 3 ”(step 503: NO), the routine proceeds to step 505. Here, since the route to the user accommodation device 36 which is the target destination node has not yet been selected (step 505: NO), the process returns to step 501.

[Second step of MIN-MAX algorithm]
Next, the route control device 20 performs route selection processing of the second step using the MIN-MAX algorithm. First, in the MIN-MAX algorithm parameter table 24C of FIG. 9, among the devices included in the set VU, the cost C (32) = “4” of the relay device 32 is the largest, so Included in U. Thereby, “30 → 32” is obtained as a route from the user accommodation device 30 to the relay device 32 (step 501).

  Subsequently, among the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the relay device 32 via the link, that is, the optimization parameter value, is calculated by the MIN-MAX algorithm. Based on the above, the cost is updated to the minimum cost of the link on the route to the device. In this case, the cost C (33) of the relay device 33 adjacent to the relay device 32 is calculated from the link cost table 24A of FIG. 3 with the cost “5” of the link 105 connecting the relay device 32 and the relay device 33, and the relay device. Among the link costs “4” on the route up to 32, the minimum value “4” is selected. At this time, no other route from the user accommodation device 30 to the relay device 33 is found, and the minimum value of the route via the relay device 32 is the maximum, and this value is the cost C (33) of the relay device 33, that is, the optimum value. (Step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 11 and 12, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 11 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, in the route to the relay device 32, the portion where the optimization parameter value does not change is a maximum of one hop of “30 (∞) → 32 (4)” and the reference hop number “3”. ”(Step 503: NO), the process proceeds to step 505. Here, since the route to the user accommodation device 36 which is the target destination node has not yet been selected (step 505: NO), the process returns to step 501.

[Third step of MIN-MAX algorithm]
Next, the route control device 20 performs route selection processing at the third step using the MIN-MAX algorithm. First, in the MIN-MAX algorithm parameter table 24C of FIG. 11, among the devices included in the set VU, the cost C (33) = “4” of the relay device 33 is the largest, so the relay device 33 Included in U. Thereby, “30 → 32 → 33” is obtained as a route from the user accommodation device 30 to the relay device 33 (step 501).

  Subsequently, among the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the relay device 33 via the link, that is, the optimization parameter value, is calculated using the MIN-MAX algorithm. Based on the above, the cost is updated to the minimum cost of the link on the route to the device. In this case, the cost C (31) of the relay device 31 adjacent to the relay device 33 is the cost “7” of the link 104 from the link cost table 24A of FIG. 3 and the link cost “4” on the route to the relay device 33. ", The minimum value" 4 "is selected.

At this time, the link 102 exists as a route from the user accommodating device 30 to the relay device 31, but the cost of the link 102 is “3” from the link cost table 24 </ b> A in FIG. 3, and when the relay device 32 is selected. The route of the link 102 is rejected. Therefore, the route via the relay devices 32 and 33 having the maximum value “4” is selected (step 501).
Similarly, the costs C (34) and C (35) of the relay apparatuses 34 and 35 adjacent to the relay apparatus 33 are calculated. In these cases as well, as described above, the route via the relay devices 32 and 33 is selected, and both costs are “4” (step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 13 and 14, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 13 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, the part where the optimization parameter value does not change in the route to the relay device 33 is a maximum of two hops of “30 (∞) → 32 (4) → 33 (4)”. Since it is smaller than the reference hop number “3” (step 503: NO), the routine proceeds to step 505. Here, since the route to the user accommodation device 36 which is the target destination node has not yet been selected (step 505: NO), the process returns to step 501.

[Fourth step of MIN-MAX algorithm]
Next, the route control device 20 performs route selection processing of the fourth step using the MIN-MAX algorithm. First, in the MIN-MAX algorithm parameter table 24C of FIG. 13, there are relay apparatuses 31, 34, and 35 having the same maximum cost “4” as apparatuses included in the set VU. In this way, if the costs are the same, an arbitrary node is selected based on the following criteria such as the order of identifiers of each node. In this example, the relay device 31 is selected from among the relay devices 31, 34, and 35, and the relay device 31 is included in the set U. Thereby, “30 → 32 → 33 → 31” is obtained as a route from the user accommodation device 30 to the relay device 31 (step 501).

  Subsequently, among the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the relay device 32 via the link, that is, the optimization parameter value, is calculated by the MIN-MAX algorithm. Based on the above, the cost is updated to the minimum cost of the link on the route to the device. In this case, since all the routes to the devices adjacent to the relay device 31 on the route, that is, the routes to the user accommodation device 30 and the relay device 33 are fixed, the optimization parameter value is not changed (step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 15 and 16, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 15 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, the location where the optimization parameter value does not change in the route to the relay device 31 is the maximum of “30 (∞) → 32 (4) → 33 (4) → 31 (4)”. There are 3 hops and the number of reference hops is “3” or more (step 503: NO).

[Initialization of optimization parameter values]
Therefore, in this case, in the MIN-MAX algorithm parameter table 24C in FIG. 15, the cost C (() of the unselected (unconfirmed) nodes included in the set V, here the relay devices 34 and 35 and the user accommodation device 36, 34), C (35), C (36), that is, the optimization parameter value is initialized with the link cost of the link to the route-selected node adjacent to each node (step 504).
For example, since the relay device 34 is adjacent to the route-selected relay device 33 via the link 106, the cost C (34) of the relay device 34, that is, the optimization parameter value is the link cost “6” of the link 106. It is initialized with. Similarly, the cost C (35) of the relay device 35 is initialized with the link cost “7” of the link 107.

Further, the user accommodation device 36 is not connected to the route-selected node, and is initialized to zero as it is. At this time, all the nodes that have not been selected may be initialized, or at least only the nodes for which the optimization parameter values have been calculated in the past, that is, the relay devices 34 and 35 may be initialized.
At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 17 and 18, respectively. Then, since the route to the user accommodation device 36 that is the target destination node has not yet been selected (step 505: NO), the process returns to step 501.

[Fifth step of MIN-MAX algorithm]
Next, the route control device 20 performs a route selection process of the fifth step using the MIN-MAX algorithm. First, in the MIN-MAX algorithm parameter table 24C in FIG. 17, among the devices included in the set V-U, the cost (35) = “7” of the relay device 35 is the maximum, so that the relay device 35 is set to the set U. Included in Thereby, “30 → 32 → 33 → 35” is obtained as a route from the user accommodation device 30 to the relay device 35 (step 501).

  Subsequently, out of the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the relay device 35 via the link, that is, the optimization parameter value, is calculated using the MIN-MAX algorithm. Based on the above, the cost is updated to the minimum cost of the link on the route to the device. In this case, the cost C (36) of the user accommodation device 36 adjacent to the relay device 35 is obtained from the link cost table 24A of FIG. 3 with the cost “8” of the link 109 connecting the relay device 35 and the user accommodation device 36, Among the link costs “7” on the route to the relay device 35, the minimum value “7” is selected. At this time, no other route from the user accommodation device 30 to the relay device 32 is found, and the minimum value of the route via the relay device 35 is the maximum, and this value is the cost C (36) of the user accommodation device 36, that is, It becomes an optimization parameter value (step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 19 and 20, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 19 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, the location where the optimization parameter value has not changed in the route to the relay device 35 is the maximum of “30 (∞) → 32 (4) → 33 (4) → 35 (7)”. Since it is 2 hops and smaller than the reference hop count “3” (step 503: NO), the process proceeds to step 505. Here, since the route to the user accommodation device 36 which is the target destination node has not yet been selected (step 505: NO), the process returns to step 501.

[6th step of MIN-MAX algorithm]
Next, the route control device 20 performs route selection processing at the sixth step using the MIN-MAX algorithm. First, in the MIN-MAX algorithm parameter table 24C of FIG. 19, among the devices included in the set V, the user accommodation device 36 is included in the collection U because the cost C (36) of the user accommodation device 36 is the largest. . As a result, “30 → 32 → 33 → 35 → 36” is obtained as a route from the user accommodation apparatus 30 as the transmission source node to the user accommodation apparatus 36 as the desired destination node (step 501).

  Subsequently, among the devices included in the set V-U, any device included in the set U, here the cost of the device adjacent to the user accommodating device 36 via the link, that is, the optimization parameter value, is expressed as MIN-MAX. Based on the algorithm, the cost is updated to the minimum value of the link on the route to the device. In this case, the cost C (34) of the relay device 34 adjacent to the user accommodation device 36 is calculated from the link cost table 24A of FIG. 3 with the cost “7” of the link 108 connecting the user accommodation device 36 and the relay device 34, Among the link costs “7” on the route to the user accommodation device 36, the minimum value “7” is selected. Here, the cost “6” on the route to the user accommodation device 36 that has already been found is compared, and the maximum value “7” on the route side via the user accommodation device 36 is the cost C (33) of the relay device 33, that is, It becomes an optimization parameter value (step 501).

  In this way, after performing the route selection process for one step by the MIN-MAX algorithm, the route obtained as a result of the selection is optimized together with the optimization parameter value of each device at the time point. Store in the parameter table 24B (step 502). At this time, the MIN-MAX algorithm parameter table 24C and the optimization parameter table 24B take the values shown in FIGS. 21 and 22, respectively.

  Subsequently, the optimization parameter table 24B of FIG. 21 is searched to check whether there is a portion where the optimization parameter value has not changed over the reference hop number for the route determined above (step 503). In the optimization parameter table 24B, the location where the optimization parameter value has not changed in the route to the user accommodation device 36 is “30 (∞) → 32 (4) → 33 (4) → 35 (7) → 36. Since (7) ”is the maximum of two hops and smaller than the reference hop number“ 3 ”(step 503: NO), the process proceeds to step 505. Here, since the route to the user accommodation device 36 which is the target destination node has been selected (step 505: YES), the series of route selection processing is terminated.

  As described above, in this embodiment, when the route selection unit 22 of the route control device 20 calculates the optimization parameter value of an arbitrary node u, the route read from the storage unit 24 has already been selected and From the optimization parameter value of the node v adjacent to the node u via the link, the link information of the link from the node v to the node u, and the optimization parameter value of the node u, a new optimization parameter value of the node u Is calculated and is stored in the storage unit 24 when the optimization parameter value of each node constituting the route does not change between the nodes over the reference hop number for the route selected by the route selection unit 22. The optimization parameter value of a node whose route has not been selected is initialized based on the link information of the link with the route-selected node adjacent to the node.

As a result, while selecting the route from the transmission source node to the destination node, the change of the optimization parameter value of the node constituting the route to an arbitrary node is confirmed, and the optimization parameter value does not vary over the reference hop number. In this case, the route selection can be continued by initializing the optimization parameter value.
Therefore, it is possible to probabilistically determine the passage of a specific node corresponding to the disconnection point of the network topology, avoid traffic concentration after the specific node, and enhance the load distribution effect using the traffic engineering technique.

  Temporarily, in the case of the conventional MIN-MAX algorithm that does not apply the route selection processing according to the present embodiment, at the time of the fourth step of the MIN-MAX algorithm described above, the node that is the target of route selection, here the relay device 34, Since the 35 optimization parameter values C (34) and C (35) are not initialized, both of these optimization parameter values become the link minimum value “4” in the path before the relay device 33. Therefore, in this example, any relay device is selected based on the next selection criterion of the optimization parameter value, for example, the value of the node identifier, and the route from the relay device 33 to the relay device 34 is determined.

As described above, in the conventional MIN-MAX algorithm, the route after the relay device 33 is based on a criterion that is not related to an appropriate evaluation value such as the traffic amount of each link constituting the route, such as the identifier value of the relay device. Since it is determined, there is a problem that traffic is concentrated on a specific node or link.
By applying this embodiment, it is possible to solve such a problem, select an optimum route based on an appropriate evaluation value, and avoid traffic concentration.

  In the above description, the case where the MIN-MAX algorithm is used as the route selection algorithm has been described as an example. However, the present invention is not limited to this, and the next node is sequentially set using the optimization parameter value for evaluating the route. As long as the algorithm is selected, the present invention can be applied in the same manner as described above, and the same effects as described above can be obtained.

  Further, in the above, as shown in FIG. 6, as the MIN-MAX algorithm, the minimum value of the link cost among the links constituting an arbitrary route is set as the optimization parameter value of the route, and the optimization parameter of each route is set. Although the case where the route having the maximum value is selected as the optimum route has been described, the present invention is not limited to this. By reversing the size of the criteria, the maximum link cost among the links that make up an arbitrary route is the optimization parameter value for that route, and the route with the smallest optimization parameter value among each route is the optimal route. Even when the MIN-MAX algorithm to be selected is used, the present invention can be applied in the same manner as described above, and the same effects as described above can be obtained.

It is a block diagram which shows the example of a network model of the communication network to which the route control apparatus concerning one embodiment of this invention is applied. It is a block diagram which shows the structure of the route control apparatus concerning one embodiment of this invention. It is a structural example of a link cost table. It is a structural example of an optimization parameter table. It is a flowchart which shows the route selection process in the route control apparatus concerning one embodiment of this invention. It is explanatory drawing which shows the definition and description regarding a MIN-MAX algorithm. It is an example of stored contents (initial state) of the MIN-MAX algorithm parameter table. It is a storage content example (initial state) of an optimization parameter table. It is an example of stored contents of the MIN-MAX algorithm parameter table (at the end of the first step). It is an example of contents stored in the optimization parameter table (at the end of the first step). It is an example of the stored contents of the MIN-MAX algorithm parameter table (at the end of the second step). It is an example of stored contents of the optimization parameter table (at the end of the second step). It is an example of stored contents of the MIN-MAX algorithm parameter table (at the end of the third step). It is an example of contents stored in the optimization parameter table (at the end of the third step). It is an example of the contents of a MIN-MAX algorithm parameter table (at the end of the fourth step). It is an example of stored contents of the optimization parameter table (at the end of the fourth step). It is an example of the stored contents of the MIN-MAX algorithm parameter table (fourth step: after initialization). It is an example of stored contents of the optimization parameter table (fourth step: after initialization). It is an example of the stored contents of the MIN-MAX algorithm parameter table (at the end of the fifth step). It is an example of stored contents of the optimization parameter table (at the end of the fifth step). It is an example of the stored contents of the MIN-MAX algorithm parameter table (at the end of the sixth step). It is an example of stored contents of the optimization parameter table (at the end of the sixth step).

Explanation of symbols

DESCRIPTION OF SYMBOLS 10,11 ... User terminal, 20 ... Path control apparatus, 21 ... Link information collection part, 22 ... Path selection part, 23 ... Path control part, 24 ... Memory | storage part, 24A ... Link cost table, 24B ... Optimization parameter table, 24C ... MIN-MAX algorithm parameter table, 30, 36 ... User accommodation device (node), 31-35 ... Relay device (node), 100-109 ... Link, 200 ... Core network, 201, 202 ... User network, 300 ... Management network.

Claims (6)

The transmission source is provided in a packet communication network including a plurality of nodes connected in a network via a link, and sequentially selects a route from the transmission source node for performing packet communication to the next node from the network. A route control device that selects a route from a node to a desired destination node,
A link information collection unit that collects link information indicating the packet transfer status in each link from each node;
When selecting a route from a source node to an arbitrary node, a route selection that selects one of the routes to the node as a route to the node based on an optimization parameter value that evaluates the route to the node. And
The link information collected by the link information collection unit, the optimization parameter value of a node for which no route is selected, and the route to the node selected by the route selection unit and the optimization of each node constituting the route A storage unit for storing parameter values;
When the route selection unit calculates the optimization parameter value of an arbitrary node u, the optimization of the node v that has been read from the storage unit and has already been selected and is adjacent to the node u via a link A new optimization parameter value of the node u is calculated from the parameter value, link information of the link from the node v to the node u, and the optimization parameter value of the node u;
For the route selected by the route selection unit, when the optimization parameter value of each node constituting the route has not changed between nodes over the number of reference hops, the route stored in the storage unit is A route control device, wherein an optimization parameter value of an unselected node is initialized based on link information of a link between a node adjacent to the node and a route already selected. The route control device according to claim 1,
The route selection unit
When calculating the optimization parameter value of the node u, an evaluation of the link obtained from the link information of the link from the node v to the node u stored in the storage unit is performed based on the MIN-MAX algorithm. The minimum value of the link cost indicated and the optimization parameter value of the node v stored in the storage unit is selected, and the optimization parameter of the node u stored in the storage unit is selected from this minimum value A route control device that calculates a maximum value of any of the values as a new optimization parameter value of the node u. The route control device according to claim 1,
The route selection unit
When calculating the optimization parameter value of the node u, an evaluation of the link obtained from the link information of the link from the node v to the node u stored in the storage unit is performed based on the MIN-MAX algorithm. The maximum value of the link cost indicated and the optimization parameter value of the node v stored in the storage unit is selected, and the optimization parameter of the node u stored in the storage unit is selected from this maximum value A path control device that calculates a minimum value of any of the values as a new optimization parameter value of the node u. A routing control device provided in a packet communication network composed of a plurality of nodes connected in a network via a link, by sequentially selecting the next node from a transmission source node that performs packet communication, to a desired destination node A route selection method for selecting a route,
A link information collecting step for collecting link information indicating a packet transfer status in each link from each of the nodes;
When selecting a route from a source node to an arbitrary node, a route selection that selects one of the routes to the node as a route to the node based on an optimization parameter value that evaluates the route to the node. Steps,
The link information collected in the link information collection step, the optimization parameter value of the node for which no route is selected, and the route to the node selected in the route selection step and the optimization of each node constituting the route A storage step of storing the parameter value in a storage unit,
In the route selection step, when calculating the optimization parameter value of an arbitrary node u, the optimization of the node v that has been read from the storage unit and has already been selected and is adjacent to the node u via a link A parameter calculation step of calculating a new optimization parameter value of the node u from the parameter value, link information of the link from the node v to the node u, and the optimization parameter value of the node u; For the route selected in the selection step, if the optimization parameter value of each node constituting the route does not change between nodes over the reference hop count, the optimization parameter value of each node constituting the route is the reference If there is no change between nodes over the number of hops, the node stored in the storage unit and the route is not selected. The optimization parameter value of de route selection method characterized by having a parameter initialization step for initializing based on the link information of the link between the Routed nodes adjacent to the node. The route selection method according to claim 4,
The parameter calculation step is obtained from link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm when calculating the optimization parameter value of the node u. A minimum value is selected from the link cost indicating the evaluation of the link and the optimization parameter value of the node v stored in the storage unit, and the minimum value and the node stored in the storage unit A route selection method characterized in that any one of the optimization parameter values of u is calculated as a new optimization parameter value of the node u. The route selection method according to claim 4,
The parameter calculating step obtains from the link information of the link from the node v to the node u stored in the storage unit based on the MIN-MAX algorithm when calculating the optimization parameter value of the node u. The maximum value is selected from the link cost indicating the evaluation of the link and the optimization parameter value of the node v stored in the storage unit, and the maximum value and the storage unit stored in the storage unit A route selection method, characterized in that any one of the optimization parameter values of the node u is calculated as a new optimization parameter value of the node u.

Images