JP6510992B2 - Route aggregation device and route aggregation method - Google Patents

Description

  The present invention relates to a route aggregation device and a route aggregation method used in a network in which a plurality of slices are formed.

Conventionally, in order to reduce the number of routes circulating in an IP network, route aggregation technology is known in which a plurality of routes are aggregated and replaced with one route. When performing route aggregation, a route is designed so that aggregation can be performed efficiently, and setting for performing route aggregation on communication devices such as a router is performed in advance.
FIG. 5 is an explanatory view schematically showing route aggregation according to the prior art.
The network 50 comprises an edge router E1 (edge 1), an edge router E2 (edge 2), an edge router E3 (edge 3) and a core router C1.
The edge router E1 is connected to the network A (NW A). In the network A, an edge router EA (edge A) is provided, and terminals to which IP addresses 10.1.1.0/24 to 10.1.100.0/24 are allocated are connected.
The edge router E2 is connected to the network B (NW B). In the network B, an edge router EB (edge B) is provided, and terminals to which IP addresses 10.2.1.0/24 to 10.2.100.0/24 are allocated are connected.
The edge router E3 is connected to the network C (NW C). In the network C, an edge router EC (edge C) is provided, and terminals to which IP addresses 10.3.1.0/24 to 10.3.100.0/24 are allocated are connected.

In the route tables of the edge routers E1 to E3, correspondence relationships between data transmission destination IP addresses and other edge routers serving as transfer destinations are recorded.
Each of the edge routers E1 to E3 aggregates the IP address of the external network to which it is connected, and shares the aggregation result with other edge routers.
For example, the edge router E1 aggregates the IP addresses 10.1.1.0/24 to 10.1.100.0/24 of the network A to which it is connected as 10.1.0.0/16, and so on. Advertise on the edge router of. Other edge routers update their route table with the advertised aggregate route. That is, the transfer destination of data whose transmission destination is 10.1.0.0/16 is set as the edge router E1.

Here, since general route aggregation as shown in FIG. 5 needs to be set in advance in the communication apparatus, a route is advertised from the outside as in a VPN (Virtual Private Network) and can not be grasped in advance. There is a problem that it can not be consolidated.
On the other hand, Non-Patent Document 1 proposes a method of collecting an inflowing external route with a controller provided outside, dynamically calculating an aggregated route and advertising it in the network.

Toshihiro Yokoi et al., "A Study on Automatic Route Aggregation System in IP Network", IEICE, September 2015, 2015 Society Conference B-6-61

In recent years, a technology for constructing a plurality of independent virtual networks (slices) on a common infrastructure using virtualization technology has been studied.
In a network in which a plurality of slices are formed, the number of holding paths of each node is a total value of the number of paths of all slices formed in the node. Therefore, if an appropriate route aggregation scheme is not selected for each slice, routes may be concentrated on a specific node. For example, when the number of paths concentrates on a particular node in each slice, the number of paths retained by the node becomes extremely large, which may cause problems such as overflow of the path table and impossibility of packet transfer.
The above-described prior art does not verify a network having a plurality of slices, and there is room for improvement.

  The present invention has been made in view of such circumstances, and it is an object of the present invention to appropriately manage the number of holding paths of each node in a network in which a plurality of slices are formed.

In order to achieve the above object, the invention according to claim 1 is a path aggregation device used in a network in which a plurality of slices are constructed, and each edge node in the network uses a path table. Data transmitted from an external terminal is transferred to another edge node, and the route aggregation device aggregates a route information acquisition unit for acquiring the route table from each of the edge nodes, and routes in the route table An aggregate route calculation unit for updating the route table, and a route setting unit for setting the updated route table in each of the edge nodes, wherein the aggregate route calculation unit is provided for each of the edge nodes; The total value of the number of paths held by the edge node on each of the slices is calculated, and each of the total values satisfies a predetermined condition. And so, to select for each of the slice from the plurality of paths aggregation scheme route summarization method using the aggregate of the paths, and a path aggregation device, characterized in that.

The invention according to claim 5 is a route aggregation method of a route aggregation device used in a network in which a plurality of slices are formed, wherein each edge node in the network is an external terminal using a route table. Transferring the data transmitted from the other edge node to another edge node, and the path aggregation device aggregates path information in the path information acquisition step of acquiring the path table from each of the edge nodes; Performing an integrated route calculation step of updating the route table and a route setting step of setting the updated route table in each of the edge nodes, wherein the integrated route calculation step includes, for each of the edge nodes A total value of the number of paths that an edge node holds on each of the slices is calculated, and each of the total values is a predetermined condition Sure to meet, to select for each of the slice from the plurality of paths aggregation scheme route summarization method using the aggregate of the paths, and a path aggregate wherein the.

This is advantageous in changing the route aggregation method for each slice and improving the convenience at the time of route aggregation.
In addition, route aggregation can be performed in consideration of the total processing load of each edge node, which is advantageous in appropriately managing the load of the nodes on the network.

Also, the invention according to claim 2 is characterized in that the aggregated route calculation unit selects the path aggregation method for each slice so that all the total values become equal to or less than a predetermined upper limit value. It is a route aggregation device.

  By doing this, it is advantageous to prevent the network failure due to the overload by preventing the number of holding paths of a specific edge node from becoming extremely large.

Also, in the invention according to claim 3 , the aggregated route calculation unit selects the route aggregation method for each slice such that the variance of the total value is equal to or less than a predetermined value. It was an apparatus.

  By doing this, it is advantageous to distribute the holding paths evenly to edge nodes on the network and to make the processing load uniform.

The invention according to claim 4 is a route aggregation device used in a network in which a plurality of slices are constructed, and each edge node in the network is transmitted from an external terminal using a route table. Data is transferred to another edge node, the route aggregation device aggregates a route information acquisition unit for acquiring the route table from each of the edge nodes, and routes in the route table, and the route table The integrated route calculation unit to be updated, and a route setting unit to set the updated route table to each of the edge nodes, the integrated route calculation unit is configured as the route aggregation method used for aggregating the routes. Total path number priority method for reducing the total value of the number of paths in a slice, and the edge with the largest number of paths in the slice Either the maximum number of routes priority scheme to reduce the number of paths over data, selecting for each of said slice and a route aggregation and wherein the.
The invention according to claim 6 is a route aggregation method of a route aggregation device used in a network in which a plurality of slices are formed, wherein each edge node in the network is an external terminal using a route table. Transferring the data transmitted from the other edge node to another edge node, and the path aggregation device aggregates path information in the path information acquisition step of acquiring the path table from each of the edge nodes; Performing an aggregate route calculation step of updating the route table and a route setting step of setting the updated route table in each of the edge nodes, and in the aggregate route calculation step, a route used to aggregate the routes As an aggregation method, a total path number priority method for reducing the total value of the number of paths in the slice, and a path in the slice There either the maximum number of routes priority scheme that reduces the number of routes of the edge router as the maximum, selects for each of the slices, and a route aggregation method characterized by.

This is advantageous in changing the route aggregation method for each slice and improving the convenience at the time of route aggregation.
In addition, it is advantageous in selecting an appropriate combination of route aggregation methods in accordance with various networks.

  According to the present invention, in a network in which a plurality of slices are formed, it is advantageous to appropriately manage the number of holding paths of each node.

FIG. 1 is an explanatory view showing a network configuration including a route aggregation device according to an embodiment. It is a flowchart which shows the procedure of the intensive route calculation process by an intensive route calculation part. It is an explanatory view showing typically a route intensive result by a route intensive device. It is an explanatory view showing typically a route intensive result by a route intensive device. It is an explanatory view showing route concentration concerning a prior art typically.

Embodiment
Hereinafter, a route aggregation device and a route aggregation method according to the present invention will be described in detail with reference to the attached drawings.
FIG. 1 is an explanatory view showing a network configuration including the route aggregation device 10 according to the embodiment.
The network 20 includes edge routers E1 to E3 which are a plurality of edge nodes and a core router C1 which is a core node, and functions as a VPN for connecting between external bases (external terminals).
In FIG. 1, the edge router E1 is connected to the site 1-1 (IP address: 10.1.1.0/24) to the site 1-100 (IP address: 10.1.100.0/24). There is. The edge router E2 is connected to the site 2-1 (IP address: 10.2.1. 0/24) to the site 2-100 (IP address: 10.2.100.0/24). Further, the edge router E3 is connected to the site 3-1 (IP address: 10.3.1.0/24) to the site 3-100 (IP address: 10.3.100.0/24).

Each of the edge routers E1 to E3 transfers data transmitted from an external terminal (base) to another edge router using a routing table. The routes recorded in each route table are routes advertised from the external terminal. Since the route flowing into the network 20 is a route of the user using the VPN service, the route to be advertised can not be known in advance or designed freely.
Also, as shown in FIGS. 3 and 4, on the resources forming the network 20, a plurality of slices separated from one another are formed. In the present embodiment, it is assumed that three independent slices (slice 1, slice 2, slice 3) are formed in the network 20.

The route aggregation device 10 is disposed outside the network 20. The route aggregation device 10 collects routes advertised in the network 20, designs an appropriate aggregated route, and distributes it to the respective edge routers E1 to E3.
The route aggregation device 10 includes a route information acquisition unit 102, an aggregated route calculation unit 104, and a route setting unit 106.

The path information acquisition unit 102 acquires a path table from each of the edge routers E1 to E3. The route information acquisition unit 102 periodically collects, for example, Management Information Base (RFC 2578) of each of the edge routers E1 to E3 and acquires a route table.
The aggregated route calculation unit 104 includes an aggregation operation unit 104A and an aggregation mode selection unit 104B. The aggregated route calculation unit 104 aggregates routes in the route table acquired from the edge routers E1 to E3 and updates the route table. Although the details will be described later, the aggregated route calculation unit 104 selects, for each slice, a route aggregation scheme to be used for route aggregation from among a plurality of route aggregation schemes.
The route setting unit 106 sets the updated route table in each of the edge routers E1 to E3. The route setting unit 106 inputs the setting from the outside using, for example, Netconf (RFC 6241) which is a protocol for updating the settings of the edge routers E1 to E3.

Below, the detail of the intensive route calculation process by the intensive route calculation part 104 is demonstrated.
The aggregation operation unit 104A calculates an aggregation route. Calculation of the aggregated route is performed, for example, by the following steps.
Step 1: Route grouping process Routes (route information in the route table) collected from each edge router E1 to E3 are grouped for each route that creates the same aggregated route, that is, a combination of advertised edge routers is the same route .
Step 2: Primary aggregation calculation processing Create an aggregated route that does not include another group of routes. A temporary aggregated route is created in each group, and if the aggregated route does not include another group of routes, it is output as a primary aggregated route.
Step 3: Second-order aggregation calculation processing Although another group of routes is included, an aggregate route that can be forwarded appropriately according to the long guest match rule is created. A temporary aggregation route is created by aggregating the primary aggregation routes obtained in step 2. If the aggregation route does not affect the traffic transferred according to the secondary aggregation routes of the other groups, it is output as a secondary aggregation route.
As described above, in the secondary aggregation calculation, it is necessary to determine the group selection order because different aggregation results are output depending on the order of the groups to be processed. The difference in the method of determining the group selection order is the difference in the route aggregation method described below.

The aggregation mode selection unit 104B calculates, for each of the edge routers E1 to E3, a total value of the number of paths that the edge router holds on each slice, and slices such that each total value satisfies a predetermined condition. Select the route aggregation method for each.
In the following description, it is assumed that the predetermined condition is that the total value of all (the total value of the number of holding paths of all edge routers) is equal to or less than a predetermined upper limit value k0. That is, the route aggregation method for each slice is selected so that a large load is not applied to a specific edge router.
The predetermined condition is not limited to the above, and, for example, the variance of the total value may be equal to or less than a predetermined value. In this case, the aggregation mode selection unit 104B calculates the variance of the total value of the holding paths of each edge router, and the distribution is less than a predetermined value, that is, the total value of the holding paths of each edge router is as uniform as possible. The route aggregation method of will be changed.

Further, in the following description, as the route aggregation method, the aggregated route calculation unit 104 has a “total number of routes priority method” which further reduces the total value of the number of routes in the network (in this embodiment, in each slice). It is possible to select a "maximum number of paths first method" which further reduces the number of paths of the edge router having the largest number of paths in the network.
Note that the route aggregation method in the aggregation route calculation unit 104 is not limited to the above two, and may be, for example, a specific node priority method or the like that reduces the route of a specific edge router. Three or more types of route aggregation methods can be selected It may be

FIG. 2 is a flowchart showing the procedure of the integrated route calculation process by the integrated route calculation unit 104.
In the following description, the set of all edge routers is X, the elements in the set X (individual edge routers) are x (1, 2,... A), the set of all slices is Y, the elements in the set Y ( Let y (1, 2... B) be an individual slice).

First, the aggregated route calculation unit 104 sets the upper limit value k0 of the number of retained routes in each edge router (step S200). The upper limit value k0 may be set by the administrator of the network 20.
Next, the aggregation operation unit 104A calculates the number of holding routes for each slice of each edge router in the case of route aggregation using the total route number priority method, and each edge router in the case of route aggregation using the maximum path number priority method. The number of holding paths for each slice is calculated (step S202).
Assuming that the aggregation result in the total path number priority system is S and the aggregation result in the maximum path number priority system is M, these results are represented as S (y, x), M (y, x). For example, the number of retained paths in slice 1 of edge router E1 in the case of using the total path number prioritization scheme is expressed as S (1,1), and in slice 2 of edge router E2 in the case of using the maximum path number prioritization scheme. The number of holding paths is expressed as M (2, 2).

  Subsequently, the aggregation mode selection unit 104B calculates a total value (the following formula (1)) of the number of holding paths of each edge router when the total path number priority method is selected for all slices (step S204).

Next, the total value is compared, and an edge router (maximum number of routes router) having the largest total value of the number of holding paths among all the edge routers is n, and a total value of the number of holding paths is kn.
Aggregation mode selection unit 104B determines whether total value kn is equal to or less than upper limit value k0 (step S206). If the total value kn is equal to or less than the upper limit value k0 (kn ≦ k0, step S206: Yes), the above condition is satisfied, and the route aggregation method of each slice is determined as the currently selected route aggregation method (step S220). ). For example, in the case of the first loop, the total path number priority scheme is selected for all slices.

On the other hand, when the total value kn exceeds the upper limit value k0 (kn> k0, step S206: No), when changing the route aggregation method for each slice, the total value kn of the number of holding routes of the maximum number of routers n. It is determined whether or not there is the case before the route aggregation scheme change (step S208).
For example, in the case of the first loop, the route aggregation method is changed to the maximum number of routes priority method for each slice y, and the total route number priority method among all slices calculated earlier among the total values of holding routes in that case. It is determined whether or not there is a value that is equal to or less than the total value kn of the number of holding paths when.

More specifically, assuming that the total number of slices is 3 and the maximum number of routes router is n, the total number of holding routes of the maximum number of routers n when the total number of routes priority method is selected for all slices is S (1 , N) + S (2, n) + S (3, n).
In addition, when the maximum number of paths priority method is selected for each slice, the total value of the number of held paths of the maximum number of paths router n is M (1, n) + S (2, n) + S (3, n) (slice 1) S (1, n) + M (2, n) + S (3, n) (when slice 2 is the maximum path number priority method), S (1, n) + S There are three patterns of (2, n) + M (3, n) (when slice 3 is set to the maximum number of paths prioritizing method).
In step S208, these difference values, that is, S (1, n) + S (2, n) + S (3, n)-(M (1, n) + S (2, n) + S (3, n)), S (1, n) + S (2, n) + S (3, n)-(S (1, n) + M (2, n) + S (3, n)), S (1, n) + S (2, n) n) It is determined whether or not some of S (3, n)-(S (1, n) + S (2, n) + M (3, n)) is 0 or more.

  If none of the total values after changing the route aggregation method is less than or equal to before changing the route aggregation method (step S208: No), that is, if all of the above difference values are negative, change the route aggregation method of any slice Since the number of holding paths of the maximum number of paths router n can not be reduced, the path aggregation method of each slice is determined to be the currently selected path aggregation method (step S220). For example, in the case of the first loop, the total path number priority scheme is selected for all slices.

In addition, when there is a total value after the route aggregation scheme change that is equal to or less than that before the route aggregation scheme change (step S208: Yes), when changing the route aggregation scheme among all slices Y, the maximum number of routes Let p be a slice that can most reduce the total value kn of the number of holding paths of n. The slice p is, for example, a slice in which the route aggregation method is changed in the pattern having the largest difference value calculated in step S208.
Then, the route aggregation method of slice p is changed (step S210). For example, in the case of the first loop, slice p selects the maximum path number priority method, and the remaining slices select the total path number priority method.

Then, it is determined whether or not all the number of holding paths kx (x = 1, 2... A) of each edge router are equal to or less than k0 (kx ≦ k0) (step S212).
If the number kx of retained paths of all edge routers is k0 or less (step S212: Yes), the above condition is satisfied, so the path aggregation method of each slice is determined to be the currently selected path aggregation method (step S220). ).
If there is an edge router n ′ where the number of holding paths kx exceeds k 0 (step S 212: No), it is determined whether the edge router n ′ matches the maximum number of routes router n in step S 206 (step S 212) Step S214).
If the edge router n 'matches the maximum number of routes router n (step S214: Yes), that is, if the maximum number of routes router n has not been changed, the process returns to step S206 and holds the maximum number of routes router n. Consider a route aggregation method that can further reduce the number of routes.

If the edge router n 'does not match the maximum number of routes router n (step S214: No), that is, if the maximum number of routes router n is changed, the maximum route before change from the set X of all edge routers The element of the number router is deleted (step S216). As a result, it is possible to prevent an infinite loop of processing without the maximum route number router before change appearing in the processing in the subsequent processing.
After the deletion of the maximum number of routes router until the element of the set X of all edge routers becomes 0 (step S218: No), the process returns to step S206 and repeats the subsequent processing.
If the element of the set X of all edge routers becomes 0 (step S218: Yes), the path aggregation method of each slice is determined to be the currently selected path aggregation method (step S220), and processing according to this flowchart Finish.

FIG. 3 and FIG. 4 are explanatory views schematically showing the route aggregation result by the route aggregation device 10. As shown in FIG.
FIG. 3 shows the number of holding paths of each of the edge routers E1 to E3 when the total path number priority method is applied to all slices without applying the aggregation mode selection unit 104B. In the example of FIG. 3, although the number of paths is optimized in each slice, the number of holding routes of the edge router E2 is larger than that of other edge routers when viewed through all slices, and the processing of the edge router E2 is performed. Performance may not catch up with demand.

On the other hand, FIG. 4 shows the number of holding paths when the aggregation mode selection unit 104B is applied and the path aggregation method of each slice is selected so that the load of a specific edge router does not increase when viewed through all slices. In the example of FIG. 4, the maximum path number prioritizing method is applied to slice 1 and slice 3 in which the number of holding paths is biased to the edge router E 2 in FIG. 4, and the total path number prioritizing method is applied to slice 2.
As a result, in slice 1 and slice 3, a part of the holding path of the edge router E2 is allocated to the edge routers E1 and E3, and the edge router E2 is not overloaded as a whole.

As described above, the path aggregation device 10 according to the embodiment selects, for each slice, a path aggregation method used for path aggregation from among a plurality of path aggregation methods. This is advantageous in changing the route aggregation method for each slice and improving the convenience at the time of route aggregation.
In addition, the route aggregation device 10 calculates the total value of the number of routes held by each of the edge routers E1 to E3 on each slice, and the route aggregation method for each slice so that each total value satisfies a predetermined condition. Choose By doing so, route aggregation can be performed in consideration of the processing load on all slices of each of the edge routers E1 to E3, which is advantageous in appropriately managing the load of the router on the network 20.

In addition, the route aggregation device 10 selects the route aggregation method for each slice so that the total value of the holding routes of all the edge routers E1 to E3 is equal to or less than a predetermined upper limit value. By doing this, it is advantageous to prevent the network failure due to the overload by preventing the number of holding paths of a specific edge router from becoming extremely large.
Also, if the route aggregation device 10 selects the route aggregation method for each slice so that the variance of the total value of the holding routes of the edge routers E1 to E3 becomes equal to or less than a predetermined value, the edge router on the network 20 This is advantageous in distributing the holding paths evenly to E1 to E3 and making the processing load uniform.

  Also, the route aggregation device 10 reduces the number of routes of the edge router with the maximum number of routes in the slice and the total number of routes priority method of reducing the total value of the number of routes in the slice as the route aggregation method. Select one of the maximum number of routes and the priority scheme. By doing this, it is advantageous to select an appropriate combination of route aggregation schemes in accordance with various networks.

DESCRIPTION OF REFERENCE NUMERALS 10 route aggregation device 102 route information acquisition unit 104 aggregate route calculation unit 104A aggregation operation unit 104B aggregation mode selection unit 106 route setting unit 20 network E1-E3 edge router C1 core router

Claims (6)

A route aggregation device used in a network in which a plurality of slices are constructed,
Each edge node in the network is forwarding data transmitted from an external terminal to another edge node using a routing table,
The route aggregation device
A path information acquisition unit for acquiring the path table from each of the edge nodes;
An aggregated route calculation unit that aggregates routes in the route table and updates the route table;
A path setting unit configured to set the updated path table in each of the edge nodes;
The aggregated path calculation unit calculates, for each of the edge nodes, a total value of the number of paths that the edge node holds on each of the slices, so that each of the total values satisfies a predetermined condition. The path aggregation method used for path aggregation is selected for each slice from among a plurality of path aggregation methods.
A route aggregation device characterized by The aggregation path calculation unit selects the path aggregation method for each slice such that all the sums become equal to or less than a predetermined upper limit value.
Route summarization apparatus according to claim 1, characterized in that. The aggregation path calculation unit selects the path aggregation method for each slice such that the variance of the total value is equal to or less than a predetermined value.
Route summarization apparatus according to claim 1, characterized in that. A route aggregation device used in a network in which a plurality of slices are constructed,
Each edge node in the network is forwarding data transmitted from an external terminal to another edge node using a routing table,
The route aggregation device
A path information acquisition unit for acquiring the path table from each of the edge nodes;
An aggregated route calculation unit that aggregates routes in the route table and updates the route table;
A path setting unit configured to set the updated path table in each of the edge nodes;
The aggregation path calculation unit is a total path number prioritization method that reduces a total value of the number of paths in the slice as a path aggregation method used for aggregation of the paths, and an edge with the maximum number of paths in the slice Select any one of the maximum number of routes priority scheme for reducing the number of routes of the router for each slice
A route aggregation device characterized by A route aggregation method of a route aggregation device used in a network in which a plurality of slices are formed, comprising:
Each edge node in the network is forwarding data transmitted from an external terminal to another edge node using a routing table,
The route aggregation device
A path information acquisition step of acquiring the path table from each of the edge nodes;
Aggregated route calculating step of aggregating routes in the route table and updating the route table;
Performing a path setting step of setting the updated path table in each of the edge nodes;
In the aggregated route calculation step, for each of the edge nodes, a total value of the number of routes that the edge node holds on each slice is calculated, and each of the total values satisfies a predetermined condition. The path aggregation method used for path aggregation is selected for each slice from among a plurality of path aggregation methods.
A route aggregation method characterized by A route aggregation method of a route aggregation device used in a network in which a plurality of slices are formed, comprising:
Each edge node in the network is forwarding data transmitted from an external terminal to another edge node using a routing table,
The route aggregation device
A path information acquisition step of acquiring the path table from each of the edge nodes;
Aggregated route calculating step of aggregating routes in the route table and updating the route table;
Performing a path setting step of setting the updated path table in each of the edge nodes;
In the aggregation path calculation step, a total path number prioritization method for reducing the total value of the number of paths in the slice and an edge with the maximum number of paths in the slice as a path aggregation method used for aggregation of the paths Select any one of the maximum number of routes priority scheme for reducing the number of routes of the router for each slice
A route aggregation method characterized by

Images