Traffic engineering method and node equipment using it

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a traffic engineering method and a node device using the same, and relates to a traffic engineering method in a network and a node device using the same.

【0002】

On the current Internet, a wide variety of information has come to be exchanged not only in conventional data communication but also in real-time services such as voice and video. As a result, traffic on the Internet is increasing rapidly year by year, and it is essential to solve the congestion problem.

【0003】

[Conventional technology]

In a network consisting of multiple nodes, RIP (Routing Information Protocol), OSPF (Open Shortest Path First), and BGP4 (Border Gateway) are the routing protocols that autonomously determine the optimum route for forwarding packets from the source to the destination. Protocol Version 4), IS-IS (Intermediate System to Intermediate System), etc. exist. Today's networks use these protocols to find the optimal route and perform packet forwarding on this route.

【0004】

When a node forwards a packet, each node 10, 11 and 12 generally refers to the destination address of the packet as shown in FIG.

【0005】

A cut-through method represented by MPLS (Multi Protocol Label Switching) is attracting attention as a technology for performing packet forwarding at a higher speed than this. In MPLS, as shown in Fig. 2, LSP (Label Switched Path) is set on the optimum route calculated by the routing protocol. Here, the nodes 15 and 17 located at both ends of the LSP are called edge nodes, and each node 16 on the LSP located between the edge nodes (within the MPLS domain) is called a core node.

【0006】

Next, using LDP (Label Distribution Protocol), labels are distributed for each node on the LSP to determine the transfer destination. In this way, for packets transferred from outside the MPLS domain, the originating edge node first attaches a label, then the packet is placed on the LSP and transferred, and finally the label is removed at the arriving edge node. Until it is transferred to the outside of the MPLS domain, it is only necessary to perform layer 2 transfer with reference to only the label at the core node in the middle, so high-speed transfer processing is possible.

【0007】

By using the routing protocol and MPLS technology in this way, high-speed forwarding using the optimum route can be realized, but when the traffic increases explosively due to the increase in subscribers as in the Internet today, congestion and packets Loss will occur. MPLS has the advantage of being able to perform high-speed forwarding in this way, but it also has the disadvantage of causing congestion and packet loss because software such as IP routing cannot flexibly control routes when traffic is concentrated. In order to prevent the occurrence of this congestion and packet loss, traffic engineering (TE), which is a control that automatically optimizes resources of the entire network, can be used.

【0008】

Although the traffic engineering function itself does not depend on a specific Layer 2 medium, it is most effective when used on a network such as MPLS mentioned above in which LSPs are set between originating and arriving nodes. The load distribution method for traffic engineering is described in, for example, Japanese Patent Application No. 12-12195. In this method, as shown in FIG. 3, a plurality of multipaths LSP1, LSP2, and LPS3 are set from the originating node 20 to the arriving edge node 21, and traffic is distributed by this multipath to distribute the traffic in the entire network. We are averaging traffic.

【0009】

In this technology, in order to recognize the current load of traffic, as shown in FIG. 4, each node calculates the average usage rate for each link and periodically advertises (Flooding) to all the nodes. The originating node 20 calculates the actual traffic (effective load) for each LSP based on the average usage rate for each link of each node received by the advertisement so that the effective load of all LSPs approaches the same value. , Traffic is moved for each microflow to achieve averaging. A microflow refers to a flow used between a certain end user, and a group of microflows having a common destination is called an aggregate flow.

【0010】

The selection of which LSP to map the microflow to is performed using the LSP determination table shown in Fig. 5 (A), and each time a new multipath is added, the number of regions divided in this LSP determination table is also selected. It will increase. First, the originating node 20 calculates the normalized value using the address information in the packet as a key. The LSP determination table is indexed by the normalized value, and the LSP to be mapped is determined. At this time, in order to average the traffic, as shown in Fig. 5 (B), the LSP to be mapped is switched by moving the boundary of the LSP in the LSP determination table from the state shown in Fig. 5 (A). By doing so, traffic distribution is realized. [Problems to be Solved by the Invention]

In conventional traffic engineering technology, the originating node collects the average usage rate for each link sent from all nodes on a regular basis, calculates the effective load for each LSP based on that, and then collectively traffic. Was performing distributed processing. Therefore, load balancing was possible in a small network, but in a large network that accommodates multiple areas such as the OSPF routing protocol, the load on the originating node is too heavy, so load balancing cannot be applied. It was possible.

【0011】

In addition, if one of the multiple routes fails, conventional traffic engineering can only detect the originating node by changing the network topology or using the LDP refresh function, so there are multiple routes including the failed route during that time. Since load distribution was continued on the path, it was not possible to remedy traffic at high speed, and it was impossible to remedy microflow such as TCP connections.

【0012】

The present invention has been made in view of the above points, and traffic that can perform load balancing at high speed even in a large-scale network and can relieve traffic loss of a failed route at high speed even in the event of a failure. An object of the present invention is to provide an engineering method and a router device using the engineering method.

【0013】

[Means for solving problems]

According to the first aspect of the present invention, the entire network is divided into areas which are an aggregate of a plurality of nodes, and in the method of performing traffic engineering of the network, load balancing closed in the area is executed for each area. Therefore, even in a large-scale network, the memory capacity required by the load balancing execution node can be significantly reduced, and load balancing can be executed at high speed.

【0014】

The invention according to claim 2 is an area for each area in a node device that is divided into areas that are an aggregate of a plurality of nodes and that constitutes a network in which the optimization of the entire resources is performed by traffic engineering. Since it has an in-area destination determination means for determining an in-area destination for performing closed load balancing within the area, it is possible to execute closed load balancing in the area, and load balancing is executed even in a large-scale network. The memory capacity required by the node can be significantly reduced and load balancing can be performed at high speed.

【0015】

According to the third aspect of the present invention, in the node apparatus according to the second aspect, the node apparatus constituting the inlet node to which the packet is supplied from the outside performs load balancing based on the address information of the packet supplied from the outside. Since it has a switching information generating means for calculating the normalized value for the purpose and adding the normalized value to the switching information of the packet, it is possible to notify the area boundary node of the normalized value.

【0016】

According to the invention of claim 4, in the node apparatus of claim 2, the node apparatus constituting the area boundary node at the boundary of the area is closed within the own area from the switching information of the packet supplied from the adjacent area. Since it has a normalized value extraction means that extracts the normalized value for executing load balancing, load balancing can be performed using the extracted normalized value at the area boundary node, such as protocol identification and header check. High-speed load balancing can be performed without the need to perform.

【0017】

The invention according to claim 5 is when a failure is detected in a node device that is divided into an area that is an aggregate of a plurality of nodes and that constitutes a network in which the optimization of the entire resources is performed by traffic engineering. Since it has a failure notification means for notifying the nearest upstream node that is executing load balancing, it is possible to distribute traffic at high speed to the node that is executing load balancing.

【0018】

According to the invention described in Appendix 6, in the node device according to claim 2, the entrance node or the area boundary node that has received the failure notification re-distributes the traffic flowing to the failed route to other routes. Since it has a distribution means, it is possible to quickly relieve the traffic loss in the traffic flowing on the failed route.

【0019】

According to the invention described in Appendix 7, in the node device described in Appendix 6, when the entrance node or the area boundary node that has received the failure notification re-distributes the traffic flowing to the failed route to another route. Since it has a failure notification receiving means for determining whether or not a traffic loss occurs, it is possible to recognize whether or not the traffic flowing to the failed route can be distributed to other routes.

【0020】

According to the invention described in Appendix 8, in the node device described in Appendix 7, when the traffic distribution means determines that the failure notification receiving means causes a traffic loss, the traffic flowing to the route where the failure has occurred is newly added. Since the route is switched to the route set to, even if the route other than the failed route has high traffic, the traffic flowing to the failed route can be relieved.

BEST MODE FOR CARRYING OUT THE INVENTION

FIG. 6 shows a configuration diagram of an embodiment of a network system to which the traffic engineering method of the present invention is applied.

【0021】

This network uses OSPF as the routing protocol. In OSPF, the entire network is divided into areas that are a collection of multiple nodes. In FIG. 6, the network is composed of areas 25, 26, 27, area 25 is composed of nodes 25a to 25e, area 26 is composed of nodes 25d, 25e, 26a to 26c, and area 27 is composed of nodes 26c. , 27a ~ 27c. Assuming that node 25a is an entrance node (Ingress node) and node 27c is a destination node (Egress node), the entrance area 25 and the destination area 27 have a two-layer topology structure connected by the backbone area 26. Here, each of the nodes 25d, 25e, and 26c located at the boundary of each area recognizes its own node as an area boundary node (ABR) by the function of OSPF. In addition, MPLS is used as a cut-through method for high-speed switching in this network.

【0022】

FIG. 7 shows a block configuration diagram of an embodiment of the originating edge node applied to the method of the present invention. In this embodiment, the entrance node 25a in FIG. 6 corresponds.

【0023】

In the figure, the L3 interface unit 31 performs layer 3 acceptance processing of IP packets and the like sent from the external network. The buffer unit 32 holds the packet information of the layer 3 packet received by each node until the switching information is added and transmitted to the next node. The L2 interface unit 33 transmits a layer 3 packet reflecting information that identifies the microflow, such as layer 3 header information, from the designated output port to the next node.

【0024】

The normalized value calculation unit 34 calculates a normalized value for executing load balancing from the packet information based on the characteristics (source address and destination address) of the actual traffic. The traffic distribution unit 35 determines to which route in the TE path group the traffic is allocated according to the calculated normalized value. In addition, when a failure occurs on a route, if it is recognized that no traffic loss will occur after receiving the judgment result of whether or not traffic loss will occur by executing load balancing by all routes other than the failed route, the relevant route is concerned. Redistribute the traffic that was flowing to the failed route to multiple other routes. On the contrary, when it is recognized that a traffic loss occurs, a new route is set and the traffic flowing to the failed route is switched to the newly set route to perform load balancing.

【0025】

The output port / switching information determination unit 36 determines the packet output port corresponding to the specified destination and path at each node, and determines each parameter required for generating the switching information. The routing control unit 37 searches the routing information of its own node from the destination address, and selects which destination node the route to which load balancing is to be executed. The intra-area destination determination unit 38 determines the destination in a closed range within the area, not the destination in the entire network, which is necessary when performing load balancing.

【0026】

The switching information generation unit 39 generates switching information for the next node, and adds a normalized calculation value calculated based on the source address and the destination address to the information. The failure notification receiving unit 40 receives the failure occurrence notification notified from the failure detection node, and determines whether or not traffic loss occurs by executing load balancing by all routes other than the failure route. The traffic management unit 41 holds the traffic information advertised from all the nodes in the area. The path setting / release unit 43 sets and deletes the paths that make up the TE path group.

【0027】

The destination address lookup table 44 is a search table for obtaining destination node information from the destination address. The in-area destination determination table 45 is a search table for determining the range from the destination node information to which destination in the area to perform load balancing. The threshold table 46 is a search table for finding the distribution destination (TE path group and LSP) of traffic in order to perform load balancing within the area. The switching information determination table 47 is a search table for obtaining the output destination of the packet and the switching information based on the information regarding the destination in the area and the distribution destination of the traffic.

【0028】

The parts newly added in the present invention are the in-area destination determination unit 38 and the failure notification receiving unit 40, and the in-area destination determination table 45 is also added as necessary data. The parts to which the function is added are the traffic distribution unit 35 and the switching information generation unit 39.

【0029】

The processing at the node 25a, which is the edge node on the entrance side, will be described. The L3 interface unit 31 receives a layer 3 packet from an external network such as a company or an ISP, notifies the address information in the packet to the normalized value calculation unit 34 and the L3 routing control unit 37, respectively, and then buffers the packet information. Hold at 32.

【0030】

Upon receiving the address information, the L3 routing control unit 37 searches the destination address lookup table 44 based on the destination address to identify the destination node at the end of the path, and notifies the destination determination unit 38 in the area of the result. To do. Conventionally, load balancing is performed in a range up to the destination node, but in the present invention, load balancing is performed in a range closed to each area. Therefore, in the area destination determination unit 38, the L3 routing control unit 37 obtains the load balancing. The in-area destination determination table 45 is searched based on the destination node information to determine the destination (area boundary node) in the area, and the result is notified to the output port / switching information determination unit 36 and the traffic distribution unit 35. ..

【0031】

On the other hand, the normalized value calculation unit 34, which receives the address information from the L3 interface unit 31, applies the information to the normalization function, calculates the normalized value for executing load balancing, and uses that value as the traffic distribution unit 35. Is notified to the switching information generation unit 39.

【0032】

Next, the traffic distribution unit 35 refers to the threshold table 46 based on the destination in the area obtained by the destination determination unit 38 in the area and the normalized value calculated by the normalized value calculation unit 34, and transfers the traffic. It determines which route in the TE path group to allocate, and notifies the output port / switching information determination unit 36 of the result. Further, the traffic management unit 41 receives and manages the traffic information periodically advertised from all the nodes in the own area from the L2 interface unit 33, and notifies the traffic distribution unit 35 of the traffic information.

【0033】

Based on the information notified from the traffic distribution unit 35 and the in-area destination determination unit 38, the output port / switching information determination unit 36 searches the switching information determination table 47, and the output port for forwarding the packet to the next node. After determining the switching information to be set in the packet, the switching information generation unit 39 is notified.

【0034】

Here, conventionally, the switching information generation unit generates switching information to the next node based on the notification information from the output port / switching information determination unit and passes it to the L2 interface unit. After adding the normalized value calculated by the normalized value calculation unit 34 to the switching information of, the L2 interface unit 33 is notified. After that, the L2 interface unit 33 that has received the switching information reflects the contents in the packet held by the buffer unit 32, and then transmits from the output port to the next node.

【0035】

FIG. 8 shows a block configuration diagram of an embodiment of a core node applied to the method of the present invention. In this embodiment, the nodes 25b, 25c, 25d, 25e in the area 25, the nodes 26a, 26b, 26c in the area 26, and the nodes 27a, 27b, 27c in the area 27 correspond to each other in FIG.

【0036】

In the figure, the L2 interface unit (upstream side) 51 processes the reception of packets transmitted from the nodes on the upstream side of the traffic. If the local node detects a failure on the route, a failure notification is sent to the nearest node that executes load balancing. The buffer unit 52 holds the packet received by each node until the switching information is edited and transmitted to the next node. The L2 interface unit (downstream side) 53 transmits a packet reflecting the switching information on the downstream side of the traffic from the designated output port to the next node.

【0037】

The normalized value extraction unit 54 extracts the normalized value for executing the load balancing set in the switching information. The traffic distribution unit 55 determines which route in the TE path group to allocate the traffic according to the extracted normalized value. In addition, when a failure occurs on a route, if it is recognized that no traffic loss will occur after receiving the judgment result of whether or not traffic loss will occur by executing load balancing by all routes other than the failed route, the relevant route is concerned. Redistribute the traffic that was flowing to the failed route to multiple other routes. On the contrary, when it is recognized that a traffic loss occurs, a new route is set, and the traffic flowing to the failed route is switched to the newly set route to perform load balancing.

【0038】

The output port / switching information determination unit 56 determines the packet output port corresponding to the specified destination and path at each node, and sets each parameter required for generating the switching information. The L2 routing control unit 57 searches the routing information of its own node from the destination address, and selects which destination node the route to which load balancing is to be executed. The intra-area destination determination unit 58 determines the destination in a closed range within the area, not the destination in the entire network, which is necessary when performing load balancing.

【0039】

The switching information generation unit 59 generates switching information for the next node, and adds a normalized calculation value calculated based on the source address and the destination address to the information. The failure notification receiving unit 60 receives the failure occurrence notification notified from the failure detection node, and determines whether or not traffic loss occurs by executing load balancing by all routes other than the failure route. The traffic management unit 61 holds the traffic information advertised from all the nodes in the area. When a failure occurs on a certain route, the failure notification unit 62 notifies the occurrence of the failure to the nearest upstream node that is executing load balancing from the node that detected the failure. The path setting / release unit 63 sets and deletes the paths that make up the TE path group.

【0040】

The destination address lookup table 64 is a search table for obtaining destination node information from the destination address. The in-area destination determination table 65 is a search table for determining the range from the destination node information to which destination in the area to perform load balancing. The threshold table 66 is a search table for finding the distribution destination (TE path group and LSP) of traffic in order to perform load balancing within the area. The switching information determination table 67 is a search table for obtaining packet output destinations and switching information based on information on destinations in the area and distribution destinations of traffic.

【0041】

The parts newly added in the present invention are the normalization extraction unit 54, the area destination determination unit 58, the failure notification reception unit 60, and the failure notification unit 62, and the area destination determination table 65 is also added as necessary data. There is. The part to which the function is added is the traffic distribution part 55. Although the explanation has been given separately for the core node and the edge node, the function of each node can be realized by making different settings on the same device.

【0042】

The processing in the core node will be described. The L2 interface unit 51 receives the packet transferred from the previous node, notifies the normalized value extraction unit 54 and the L2 routing control unit 57 of the switching information in the packet, and then causes the buffer unit 52 to hold the packet information.

【0043】

If the local node is a node set to perform load balancing and is an area boundary node on the path, the L2 routing control unit 57 uses the destination address based on the switching information notified by the L2 interface unit 51. The lookup table 64 is searched to identify the destination node at the end of the path, and the result is notified to the destination determination unit 58 in the area. Similar to the edge node, the in-area destination determination unit 58 searches the in-area destination determination table 65 based on the destination node information obtained by the L2 routing control unit 57, and searches for the destination in the area (area boundary node or destination). The node) is determined, and the result is notified to the output port / switching information determination unit 56 and the traffic distribution unit 55.

【0044】

In the past, it was necessary for only the entry node to obtain the normalized value for load balancing, but in the present invention, in order to perform closed load balancing within the area, the normalized value extraction unit 54 uses the L2 interface unit. From the in-packet information received from 51, the normalized value required to close in the own area and execute load balancing is extracted, and the result is notified to the traffic distribution unit 55.

【0045】

Next, the traffic distribution unit 55 refers to the threshold table 66 based on the destination in the area obtained by the destination determination unit 58 in the area and the normalized value extracted by the normalized value extraction unit 54, and transfers the traffic. It determines which route in the TE path group to allocate, and notifies the output port / switching information determination unit 56 of the result. Further, the traffic management unit 61 receives and manages the traffic information periodically advertised from all the nodes in the own area from the L2 interface unit 53, and notifies the traffic distribution unit 55 of the traffic information.

【0046】

On the other hand, if the local node is not a load balancing execution node, the above-mentioned processes of the normalized value extraction unit 54 and the traffic distribution unit 55 are not required. Subsequent processing of the output port / switching information determination unit 56, switching information generation unit 59, and L2 interface unit 53 is the same as that of the edge node. The description of the destination node 27c is omitted because it is not directly related to load balancing. By the way, the load balancing execution node is an area boundary node that executes load balancing within the core node. Even if it is an area boundary node, load balancing is not executed if it is a node that is not located on the LSP.

【0047】

This makes it possible to carry out closed load balancing within the area, and optimal traffic engineering can be performed even in a large-scale network. Further, by putting the normalized value calculated in the edge node into a packet and notifying the area boundary node, load balancing can be executed by high-speed forwarding while taking advantage of the cut-through packet forwarding method.

【0048】

Next, failure handling at the upstream edge node will be described. When a failure occurs on a certain route, the failure notification receiving unit 40 receives a failure notification transmitted from the core node that has detected the failure from the L2 interface unit 33. Then, it is determined based on the traffic information of each node that has been advertised whether or not traffic loss occurs when the traffic flowing to the failed route is re-distributed to a plurality of routes other than the failed route. Then, the determination result is notified to the traffic distribution unit 35.

【0049】

When the traffic distribution unit 35 that has received the notification determines that no traffic loss occurs, the traffic of the failed route is redistributed to all other routes. On the contrary, when the judgment result that the traffic loss occurs is received, another route is newly set and the traffic flowing to the faulty route is switched to the new route to perform load balancing.

【0050】

Next, failure handling at the core node will be described. The failure notification unit 62 receives a notification from the L2 interface unit 53 about the occurrence of a failure on the route that is performing load balancing, and the nearest upstream node that is executing load balancing, that is, the entrance node or the area boundary on the path. A failure notification is sent from the L2 interface unit 51 to the node.

【0051】

On the other hand, when the local node is a load balancing execution node and the above-mentioned failure notification is received from the failure detection node, the processing is the same as that of the edge node. As a result, even if a failure occurs on the route, the node that detects the failure notifies the node performing load balancing of the failure and re-distributes the traffic on multiple routes other than the failure. , High-speed traffic loss relief is possible.

【0052】

In addition, if it is determined that traffic loss will occur if traffic is re-distributed to routes other than the faulty route, traffic relief for the faulty route is possible by setting a new route and switching the traffic of the faulty route to the new route. Will be.

【0053】

A more specific embodiment will be described.

【0054】

First, set the LSP (default path) according to the optimum route calculated by OSPF. Several methods such as LDP and RSVP-LSP-Tunnel (MPLS extended version of RSVP) have been proposed as protocols for LSP setting, but RSVP-LSP-Tunnel should be used, and the default path in that case. FIG. 9 shows a flowchart of an embodiment of the setting process.

【0055】

In FIG. 9, the path setting / release units 43 and 63 that recognize the path setting request calculate the optimum route between the edge nodes in OSPF in step S10. In step S12, as shown in FIG. 10, the Path message along the calculated optimum route is transmitted from the entrance node 25a to the destination node 27c from the L2 interface units 33 and 53. In response, the destination node 27c sends a received message (Resv message) by the reverse route, and the entry node 25a finally receives this received message, and the default path for packet forwarding is set.

【0056】

When traffic starts to flow along this default path, each node 25a, 25d, 26a, 26c, 27a, 27c on the LSP will be aware of the current load status of the traffic on its own node, as shown in Figure 11. In addition, the number of packets transferred and the number of packets discarded for each physical link (physical channel) of the outgoing port are periodically collected as statistical information by hardware, and the usage rate for each physical link is calculated based on them for statistics. Add to information.

【0057】

Each node advertises the statistical information (including the average usage rate) for each physical link obtained above to all other nodes in its own area using OpaqueLSA of OSPF. Opaque LSA is an extension of LSA (link state advertisement) included in the message packet when exchanging the state between each node by the OSPF message so that the user can use it for general purposes according to the purpose. .. Figure 12 shows the OSPF Opaque LSA format. In OSPF OpaqueLSA, statistical information for each card is stored as many as the number of cards after the OSPF packet header and OpaqueLSA.

【0058】

Figure 13 shows the state of the advertisement. In the figure, node A in area # 10 advertises OpaqueLSA to all adjacent nodes B, C, D, and OpaqueLSA received by nodes B, C, D also advertises to all adjacent nodes, but it has been received. The node discards when it receives the same Opaque LSA.

【0059】

Conventionally, only the entrance node collects and manages this advertisement information, but in the present invention, not only the entrance node but also the node that recognizes itself as an area boundary node on the LSP is load balanced. Therefore, the traffic management units 41 and 61 of those nodes also collect and manage the advertisement information.

【0060】

Next, the processing of the load balancing execution node will be described. FIG. 14 shows a flowchart of the first embodiment of the load balancing process. In the figure, it is determined in step S20 whether or not it is a load balancing execution node, and the process proceeds to step S22 only when it is a load balancing execution node. In step S22, the traffic distribution unit 35,55 of the load balancing execution node receives the average usage rate for each link of each node in the area received by the advertisement from the traffic management unit 41,61, and based on this, TE (traffic engineering). ) Calculate the traffic for the path group.

【0061】

The TE path group referred to here means a group in which the default path and all TE multipaths for the default path are combined into one group, which is a conventional concept. As an example of calculating the TE path group, as shown in Fig. 15, when a certain LSP1 (default path) is composed of multiple links (Link1, 2, ... i ... n), it is obtained by advertisement. The effective load of LSP1 is calculated based on the traffic information of each link, and the usage rate as a TE path group (LSP1, 2, ... i ... n) including LSP1 is calculated.

【0062】

In step S24, the traffic distribution units 41 and 61 periodically calculate the usage rate of the TE path group as shown in FIG. 16, and if the effective load exceeds a certain upper limit threshold value continuously for a certain period of time, the default path is set. Judge that it is congested. If it is determined to be congested, an instruction is sent to the path setting / release units 43 and 63 in step S26, and TE multipath is additionally set.

【0063】

The processing up to this point differs from the conventional one in that the setting range of the conventional TE multipath is from the entrance node to the destination node as in the default path, whereas in the present invention, each area is shown in FIG. The point is to set TE multipath in each of 25, 26, and 27 closed ranges. In Fig. 17, the solid line shows the default path LSP, the alternate long and short dash line shows the existing multipath LSP, the broken line shows the newly added multipath LSP, and the nodes 25a, 25d, 26c are load balancing. It is an execution node.

【0064】

In this way, the load balancing execution node repeats the above processing according to the congestion situation, and every time it is determined that the traffic increases further and the TE path group is congested, a new TE multipath is added, and conversely, for a certain period of time. If the traffic falls below the lower threshold, it is determined that the congestion has been cleared, and TE multipath is deleted in step S28.

【0065】

Next, FIG. 18 shows a flowchart of a second embodiment of the load balancing process. This process is executed when the entry node 25a receives a packet from outside the MPLS domain via the L3 interface unit 31.

【0066】

In the figure, in step S30, it is determined whether or not the own node is an entrance node, and if it is an entrance node, the process proceeds to step S32, and based on the destination address (destination address) extracted from the packet by the L3 routing control unit 37. , The destination address lookup table 44 having the configuration shown in FIG. 19 is searched to determine the identifier (Associate Pointer) corresponding to the destination node at the end of the path. Then, based on the obtained identifier, the in-area destination determination unit 38 searches the in-area destination determination table 45 having the structure shown in FIG. 20, and determines the identifier (LB Table Pointer) corresponding to the load balancing destination. The destination referred to here is not a destination to the conventional destination node, but a destination for load balancing within the area. After that, in step S34, based on the IP source address and IP destination address in the received packet, the normalized value calculation unit 34 obtains the normalized value (0 to 65535) using the hash function (CRC16), and in step S42. move on.

【0067】

On the other hand, if it is not an entrance node, the process proceeds to step S36 to determine whether or not the local node is a load balancing execution node. In the case of a load balancing execution node, that is, if it is an area boundary node, the process proceeds to step S38, and the L2 routing control unit 57 searches the destination address lookup table based on the value of the label attached to the packet by MPLS. Get a similar identifier. Note that the search may be accelerated by using hardware having a special memory such as CAM. Then, the in-area destination determination unit 58 searches the in-area destination determination table 65 based on the obtained identifier, and determines the identifier (LB Table Pointer) corresponding to the load balancing destination. After that, the normalized value added to the switching information is extracted in step S40, and the process proceeds to step S42.

【0068】

In step S42, the area to which the traffic distribution unit 35,55 searches the threshold table 46,66 having the structure shown in FIG. 21 based on the identifier corresponding to the destination in the above area is within the corresponding TE path group. For each LSP in the above, a threshold value is set indicating the ratio of load balancing to be performed. For example, when a TE path group consisting of one default path and two TE multipaths is load balancing, as shown in Fig. 23 (A), the area to which the threshold tables 46 and 66 are searched is 2. It is divided into 3 areas corresponding to LSP1, LSP2, and LSP3 by one load balancing boundary value.

【0069】

Here, since the total area of LSP1, LSP2, and LSP3 obtained above is allocated in the range of the normalized value (0 to 65535), the traffic distribution unit 33,35 has the normalized value and the threshold table 46,66. By comparing the areas within, it is uniquely determined to which LSP in the TE path group the traffic is load-distributed. Further, each time TE multipath is added or deleted in the flowchart of FIG. 14, the number of load distribution boundaries in this area also increases or decreases, so that the area is reset accordingly.

【0070】

In step S44, the output port / switching information determination unit 36,56 receives the load balancing execution destination in the area from the in-area destination determination unit 38,58, and which LSP from the traffic distribution unit 35,55 is the traffic distribution destination. After receiving the information, the switching information determination tables 47 and 67 having the structure shown in FIG. 22 are searched, and the label information to be added when the packet is output to the next node and the output port of the packet are obtained. ..

【0071】

The switching information of the packet to be sent to the next node is generated by the switching information generators 39 and 59. In step S45, it is determined whether or not the own node is an entry node, and only in the case of the entry node, the process proceeds to step S46, and FIG. As shown in (B), in addition to the normal switching information, the normalized value calculated by the hash operation is also added. This is a difference from the conventional method.

【0072】

This is because in the present invention, the area boundary node also performs load balancing, so that the normalization extraction unit 54 of the area boundary node that received the packet normalizes the packet by the entry node as shown in FIG. 23 (C). By referring to the packetization value, the area boundary node can perform the same additional distribution processing as the entrance node. In other words, if the load balancing node is an area boundary node, there is no need to newly calculate the normalized value from the destination address, and only the value calculated at the entrance node can be used, so faster forwarding is realized. it can.

【0073】

Assuming that load balancing by multiple paths is executed by the above method, the situation where a failure occurs on the paths will be described.

【0074】

As shown in Fig. 24, when a link or node failure occurs on a multipath during load balancing, the Hello protocol of OSPF that sends out between adjacent nodes with a relatively long cycle of 30 seconds by default is used in the past. In contrast to the above, the failure was detected by recognizing the topology change, in the present invention, the failure notification is triggered by the detection of LOS (Loss of signal) or LOF (Loss of frame) for each link, which is an existing hardware function. By doing, the failure is recognized at an earlier stage. In FIG. 24, the core node 26a recognizes the failure.

【0075】

FIG. 25 shows a flowchart of an embodiment of the failure detection process executed by the failure notification unit 62 of the node that detected the failure. In the figure, in step S50, it is determined whether or not the local node is a load balancing execution node, and if it is a load balancing execution node, it is not necessary to notify, so the failure notification reception process described later is executed. If it is not a balancing execution node, in step S54, the occurrence of a failure is notified to the nearest upstream node (entrance node or area boundary node) that is performing load balancing. In FIG. 26, the core node 26a that recognizes the failure notifies the area boundary node 25d of the occurrence of the failure.

【0076】

As a failure notification method, it is possible to send a Resv Tear message of RSVP-LSP-Tunnel having the structure shown in FIG. 27 from the L2 interface unit 51. In addition, hop-by-hop notification on a link-by-link basis or setting an LSP for failure notification in the opposite direction to traffic can be considered. As an example when using the Resv Tear message, set the address of the load balancing execution node in the SESSION object of the Path message sent when setting the path. The address of this load balancing execution node is sequentially replaced each time the Path message passes through the load balancing execution node as shown in FIG. 28. Each node on the path saves this address in its own node when the Path message is passed, and when a failure is detected, it can notify the failure by sending a Resv Tear message to the saved address of the load balancing execution node. ..

【0077】

FIG. 29 shows a flowchart of an embodiment of the failure notification reception process executed by the load balancing execution node that has received the failure notification.

【0078】

In the figure, in step S60, it is determined whether or not the local node is a load balancing execution node, and if it is a load balancing execution node, the failure that was sent to the failure route by the failure notification receiver 60 in step S62 is the failure. Determine whether load balancing is feasible for all routes except routes. As this determination method, the usage rate of each LSP collected at the time of load balancing is used.

【0079】

For example, as shown in Fig. 30 (A), each LSP1 (using 6 Mbps in 10 Mbps), LSP2 (using 25 Mbps in 30 Mbps), and LSP3 (using 4 Mbps in 10 Mbps) in the TE path group are shown in the figure. Suppose a failure occurs on LSP1 while performing load balancing at utilization. In this case, the result of subtracting the free bandwidth (4 Mbps) of LSP1 from the free bandwidth (15 Mbps) of the entire TE path group is compared with the execution load of LSP1 (6 Mbps). In this case, since the subtracted result is larger than the effective load of the faulty route (LSP1), it is determined in step S62 that no traffic loss will occur even if redistribution is performed, and the traffic distribution unit 35 determines in step S64. Traffic is redistributed to all routes LSP2 and LSP3 other than the failed route. At this time, for the threshold table 46, as shown in FIG. 31 (A), the number of load distribution boundaries is reduced by one (because the area of the faulty LSP1 is deleted), and the area is redistributed by the remaining LSP2 and LSP3. I do. This situation is schematically shown in FIG. 32 (A).

【0080】

On the contrary, as shown in FIG. 30 (B) in step S62, when it is determined that traffic loss will occur if redispersion occurs, a new area is created from the traffic distribution unit 35 to the path setting / release unit 43 in step S66. You will be instructed to additionally configure the closed TE multipath inside. The method of adding a new TE multipath is the same as the process of adding a TE multipath in normal load balancing. After adding the TE multipath, the traffic flowing to the faulty route in step S68 is switched by the traffic distribution unit 35 to the newly set LSP route. The area of the threshold table at this time is changed as shown in FIG. 31 (B). This situation is schematically shown in FIG. 32 (B).

【0081】

Through the above processing, it is possible to quickly relieve traffic loss when a failure occurs on the path where load balancing is performed. In other words, for example, if a failure occurs on the route while a service using TCP (Telnet, etc.) is being executed between users via the OSPF network, Ack cannot normally be received until the failure is detected and recovered. There is a possibility that the connection will be disconnected, but this can be avoided by implementing high-speed failure detection traffic relief.

【0082】

In this way, in a large-scale routing protocol network that uses the concept of layering such as OSPF areas, by performing closed load balancing within the area, each node only has all the traffic data in the area. Often, it is not necessary to hold data for all areas used for traffic engineering, which can significantly reduce the memory capacity required by load balancing execution nodes, making it ideal for large networks that were not possible with existing technology. Traffic engineering becomes possible.

【0083】

In addition, the edge node calculates the normalization value for load balancing based on the source address, destination address, etc., notifies the normalization value to the area boundary node, and the area boundary node uses the normalization value. By executing load balancing, it is not necessary to identify protocols such as IP and IPX and check headers such as IP protocols at the area boundary node, so the advantage of the cut-through packet transfer method is utilized. Load balancing is possible with high-speed forwarding as it is.

【0084】

In addition, when load balancing is performed using multiple routes and a failure occurs in one route, the node that detects the failure notifies the node that is executing load balancing of the failure. By distributing the traffic that the load balancing execution node that received the failure notification to the other multiple routes, it is possible to quickly relieve the traffic loss in the traffic that was flowing on the failure route. It becomes. In addition, until now, it was necessary to wait for a change and reestablish a user-triggered connection, but since traffic loss can be relieved at high speed, it is also possible to relieve microflows such as aggregated TCP connections.

【0085】

Furthermore, if it is determined that traffic loss will occur if the load balancing execution node that received the failure notification distributes the traffic that was flowing to the failure route to multiple other routes, a new route is set and the failure route is set. By switching the traffic that was flowing to the newly set route, even if the route other than the failure route is high traffic, the traffic that was flowing to the failure route can be relieved, and a more reliable connection can be made. It becomes possible to provide a less packet transfer service.

【0086】

The in-area destination determination units 38 and 58 correspond to the in-area destination determination means described in the claims, the switching information generation means corresponds to the switching information generation unit 39, and the normalized value extraction unit 54 corresponds to the normalized value extraction means. The failure notification unit 62 corresponds to the failure notification means, and the failure notification receiving unit 40 corresponds to the failure notification receiving means.

【0087】

(Appendix 1) The entire network is divided into areas that are an aggregate of a plurality of nodes, and the method of performing traffic engineering of the network is characterized in that each area is subjected to closed load balancing within the area. Traffic engineering method.

【0088】

(Appendix 2) In a node device that is divided into areas that are a collection of multiple nodes and that constitutes a network in which the optimization of the entire resources is performed by traffic engineering, the load that is closed within the area for each area. A node device comprising an in-area destination determining means for determining an in-area destination for balancing.

【0089】

(Appendix 3) In the node device described in Appendix 2, the node device that constitutes the entry node to which packets are supplied from the outside sets a normalized value for load balancing based on the address information of the packet supplied from the outside. A node device including a switching information generating means that calculates and adds the normalized value to the switching information of the packet.

【0090】

(Appendix 4) In the node apparatus described in Appendix 2, the node apparatus constituting the area boundary node at the boundary of the area executes closed load balancing within its own area from the switching information of the packets supplied from the adjacent area. A node device characterized by having a normalized value extracting means for extracting a normalized value for the purpose.

【0091】

(Appendix 5) Load balancing is executed when a failure is detected in a node device that is divided into an area that is an aggregate of multiple nodes and whose entire resources are optimized by traffic engineering. A node device characterized by having a failure notification means for notifying a failure to the nearest upstream node.

【0092】

(Appendix 6) In the node device described in Appendix 2, the entrance node or area boundary node that has received the failure notification has a traffic distribution means for redistribution of the traffic flowing to the failed route to other routes. A node device characterized by.

【0093】

(Appendix 7) In the node device described in Appendix 6, the entrance node or area boundary node that received the failure notification causes a traffic loss when the traffic flowing to the failed route is re-distributed to other routes. A node device having a failure notification receiving means for determining whether or not to do so.

【0094】

(Appendix 8) In the node device described in Appendix 7, when the traffic distribution means determines that a traffic loss occurs in the failure notification receiving means, a route in which the traffic flowing to the failed route is newly set is set. A node device characterized by switching to.

【0095】

[Effect of the invention]

As described above, since the invention according to claim 1 executes closed load balancing in each area, the memory capacity required by the load balancing execution node is significantly reduced even in a large-scale network. Load balancing can be performed at high speed.

【0096】

The invention according to claim 2 has an in-area destination determination means for determining an in-area destination for performing closed load balancing in the area for each area, and therefore, performs closed load balancing in the area. This makes it possible to significantly reduce the memory capacity required by the load balancing execution node even in a large-scale network, and load balancing can be executed at high speed.

【0097】

The invention according to claim 3 is a normalization in which a node device constituting an inlet node to which a packet is supplied from the outside calculates a normalized value for load balancing based on the address information of the packet supplied from the outside. Since it has a normalized value calculation means and a switching information generating means for adding the normalized value to the switching information of the packet, it is possible to notify the normalized value to the area boundary node.

【0098】

According to the invention of claim 4, the node apparatus constituting the area boundary node at the boundary of the area is normal for performing closed load balancing within its own area from the switching information of the packets supplied from the adjacent area. Since it has a normalized value extraction means that extracts the normalized value, load balancing can be performed using the extracted normalized value at the area boundary node, and there is no need to perform protocol identification or header check, etc., and high-speed load balancing is performed. It can be performed.

【0099】

The invention according to claim 5 has a failure notification means for notifying the nearest upstream node that is executing load balancing when a failure is detected, so that the traffic is transmitted by the node that is performing load balancing. It is possible to perform distribution at high speed.

【0100】

In the invention described in Appendix 6, the entrance node or the area boundary node that received the failure notification has a traffic distribution means for redistribution of the traffic that was flowing to the failed route to other routes, so that the failed route flows. It is possible to relieve the traffic loss in the existing traffic at high speed.

【0101】

The invention described in Appendix 7 determines whether the entrance node or area boundary node that receives the failure notification causes traffic loss when the traffic that was flowing to the failed route is re-distributed to other routes. Since it has a failure notification receiving means for determining, it is possible to recognize whether or not the traffic flowing to the failed route can be distributed to other routes.

【0102】

In the invention described in Appendix 8, when the traffic distribution means determines that the failure notification receiving means causes a traffic loss, the traffic flowing to the failed route is switched to the newly set route, so that the route other than the failed route is used. Even if the route is high traffic, the traffic that was flowing to the failed route can be relieved.

[Simple explanation of drawings]

[Figure 1]

It is a figure which shows the conventional general IP packet forwarding processing.

[Figure 2]

It is a figure which shows the IP packet forwarding processing by the conventional MPLS.

[Fig. 3]

It is a figure for demonstrating the conventional traffic engineering method.

[Fig. 4]

It is a figure for demonstrating the conventional traffic distribution method.

[Fig. 5]

It is a figure for demonstrating the movement of the boundary of LSP of the LSP determination table.

[Fig. 6]

It is a block diagram of an Example of a network system to which the traffic engineering method of this invention is applied.

[Fig. 7]

It is a block block diagram of one Example of the origin side edge node applied to the method of this invention.

[Fig. 8]

It is a block block diagram of an Example of a core node applied to the method of this invention.

[Fig. 9]

It is a flowchart of one Example of the default path setting process.

[Fig. 10]

It is a figure for demonstrating the default path setting.

[Fig. 11]

It is a figure which shows the traffic information collection by hardware.

[Fig. 12]

It is a figure which shows the format of Opaque LSA of OSPF.

[Fig. 13]

It is a figure which shows the state of an advertisement.

[Fig. 14]

It is a flowchart of 1st Example of a load balancing process.

[Fig. 15]

It is a figure for demonstrating the usage rate calculation of a TE pass group.

[Fig. 16]

It is a figure for demonstrating the monitoring and determination of a congestion situation.

[Fig. 17]

It is a figure which shows the setting of TE multipath for each area.

[Fig. 18]

It is a flowchart of 2nd Example of a load balancing process.

[Fig. 19]

It is a figure which shows the structure of the destination address lookup table 44.

[Fig. 20]

It is a figure which shows the structure of the destination determination table 45 in an area.

[Fig. 21]

It is a figure which shows the structure of the threshold table 46, 66 of the structure.

[Fig. 22]

It is a figure which shows the structure of the switching information determination table 47,67.

[Fig. 23]

It is a figure for demonstrating the implementation of additional dispersion.

[Fig. 24]

It is a figure for demonstrating failure detection in load balancing.

[Fig. 25]

It is a flowchart of one Example of the failure detection process executed by the failure notification unit 62 of the node which detected the failure.

[Fig. 26]

It is a figure for demonstrating the failure notification to a load balancing execution node.

[Fig. 27]

It is a figure which shows the structure of the Resv Tear message of RSVP-LSP-Tunnel.

[Fig. 28]

It is a figure for demonstrating the failure notification to each node.

[Fig. 29]

It is a flowchart of one Example of the failure notification reception processing executed by the load balancing execution node which received the failure notification.

[Fig. 30]

It is a figure for demonstrating the traffic loss occurrence determination by redistribution.

[Fig. 31]

It is a figure for demonstrating the change of the threshold table by redispersion.

[Fig. 32]

It is a figure for demonstrating load distribution after failure detection.

[Explanation of symbols]

31 L3 interface section 32,52 Buffer part 33,51,53 L2 interface section 34 Normalized value calculation unit 35,55 Traffic distribution section 36,56 Output port / switching information determination unit 37,57 Routing control unit 38,58 Area destination determination unit 39,59 Switching information generator 40,60 Failure notification receiver 41,61 Traffic Management Department 43,63 Path setting / release section 44,64 Destination address lookup table 45,65 Area destination determination table 46,66 Threshold table 47,67 Switching information determination table 54 Normalized value extractor 62 Failure notification section