JP5504449B2 - Network control method, control device, and network - Google Patents

Description

  The present invention relates to a technique for monitoring and controlling a communication network using IP (Internet Protocol), Ethernet (registered trademark), P2P (Peer-to-Peer), and the like.

  The topology and communication path of the communication network are designed so that the assumed traffic can be accommodated efficiently without causing quality degradation such as congestion. However, if traffic fluctuations occur and traffic with a tendency that is significantly different from the traffic assumed at the time of design flows, congestion may occur and communication quality may not be maintained.

  As a technique for avoiding congestion and appropriately accommodating traffic even when traffic fluctuations occur, traffic engineering (TE: TE) that dynamically reconfigures communication paths and the like in the network according to the traffic after fluctuations. A method called “Traffic Engineering” is regarded as important. Especially in recent years, as applications such as P2P and Video-on-Demand have become widespread, traffic fluctuations have increased, and in order to maintain communication quality even in situations where sudden traffic fluctuations occur frequently, Therefore, it becomes necessary to perform traffic engineering in a short cycle.

  Various techniques have been proposed as a technique for performing TE (for example, Non-Patent Documents 1, 2, and 4). Among them, Non-Patent Documents 1 and 2 propose a method based on optimization and a heuristic method for designing a virtual network that accommodates the traffic demand for a given traffic demand matrix. Has been. Here, the traffic demand matrix represents traffic demand between any two nodes in the network in a matrix format, and expresses traffic exchange of the entire network. Many of these conventional online TE controls assume that the traffic demand matrix at two certain times can be acquired, or that the traffic demand fluctuates periodically and gently. However, it is difficult to obtain an accurate traffic demand matrix in a large-scale communication network (see, for example, Non-Patent Document 3). Therefore, a method has been proposed in which only link usage rates that are easier to acquire are collected and a communication path that matches the link usage rates is designed (see, for example, Non-Patent Document 4).

B. Mukherjee, D. Banerjee, S. Ramamurthy, and A. Mukherjee, “Some principles for designing a wide-area WDM optical network”, IEEE / ACM Transactions on Networking, vol. 4, no. 5, pp. 684- 696, 1996. R. Ramaswami and K. N. Sivarajan, “Design of logical topologies for wavelength-routed optical networks”, IEEE Journal on Selected Areas in Communications, vol. 14, pp. 840-851, June 1996. N. Benameur and J. W. Roberts, “Traffic Matrix Inference in IP Networks”, NETWORKS AND SPATIAL ECONOMICS, VOL 4; NUMBER 1, pp. 103-114, 2004. I. Juva, “Robust load balancing”, in Proceedings of IEEE Globecom 2007, pp. 2708-2713, Nov 2007.

  However, this conventional method requires a long calculation time when designing an optimal communication path, and is difficult to apply to a large-scale network. In addition to the problem of calculation time, in a large-scale network, the processing load for collecting the traffic data of all links is high and difficult to realize.

  In a large-scale network, even if the frequency of link congestion and node failure is the same, the communication route by traffic engineering, etc. is much more frequent than in a small-scale network. Reconfiguration is performed. Therefore, if the entire network is reconfigured every time reconfiguration is necessary, there arises a problem that the network becomes unstable.

  The present invention has been made in view of the above-mentioned problems relating to traffic data collection load and network reconfiguration, and can be applied to any network topology, and can reduce control load and stability. It is an object of the present invention to provide a network control method that realizes improvement of the network.

  In order to solve the above-mentioned problem, the present invention monitors traffic in a network composed of a plurality of nodes and links for communication between the nodes so as to prevent the occurrence of congestion. A network control method for changing a route, wherein the entire network is geographically, physically, or logically divided into a plurality of control ranges, and a plurality of control ranges are combined to provide a higher control range. A network control device that is set hierarchically and is associated with each of the control ranges is associated with the control range, and the network control device that controls the control range of the lowest layer is within its own control range. Collect and acquire load information of each link connected to the node from each of the nodes, and If there is a lower level network control device that controls a control range that is one level lower than its own control range, for each traffic to be controlled that passes through the lower control range, the traffic is The load information of the bottleneck link in which the margin of the link load is the smallest among the links within the lower control range that is passed through is acquired from the lower network control device, and each of the network control devices When there is a higher-level network control device that controls a control range that is one level higher than its own control range, each traffic that flows out from a node within its own control range to the higher-level control range, and the higher-level control For each traffic that flows from a range to a node within its own control range, within the higher control range through which the traffic passes The load information of the bottleneck link having the smallest link load margin is acquired from the higher-level network control device, and each of the network control devices includes each of the acquired bottleneck links. When identifying a link within the control range of the own control range to prevent the occurrence of congestion within the control range based on the link load information and changing the communication route within the control range In addition, by solving a linear programming problem based on the load information of each link including the bottleneck link, the maximum link usage rate of each link after the route change is calculated, and any maximum link usage rate has a predetermined threshold value. It is characterized in that a route that does not exceed is determined.

  By doing so, the higher-level network control device can perform higher-level route control based on the aggregated information regarding the bottleneck link acquired from the lower-level network control device within its control range. Therefore, it is possible to realize path control that guarantees that no new congestion occurs throughout the entire network while reducing the control load of each network control device.

  In the network control method according to the present invention, in the network control method, the route change control according to the determined route is performed by the lower-layer network control among the network control devices that control the traffic that is the target of the route change. The apparatus is performed with priority.

  By doing this, when avoiding the occurrence of congestion, priority is given to the route change in the lower hierarchy and the local route change is performed as much as possible, so that the stability of the network can be improved. it can.

  In the network control method according to the present invention, a node positioned on a boundary line of a plurality of the control ranges in a certain hierarchy and a virtual logical link connecting the nodes are one level higher than the hierarchy. It is characterized by constructing the topology of the control range.

  By doing this, it is possible to simplify the topology structure of the next higher hierarchy while maintaining information related to the bottleneck link in the control range of a certain hierarchy, and it is possible to control at a granularity according to the level of the hierarchy Become.

  According to the present invention, it is possible to provide a network control method that can be applied to an arbitrary network topology and that realizes reduction in control load and improvement in stability.

It is a structural example of the network which concerns on embodiment of this invention. It is explanatory drawing about hierarchization of a network topology and a control range. It is explanatory drawing about the relationship between a low-order and a high-order control range, and a network topology. It is the block diagram which showed the function structure of the network control apparatus of the lowest layer. It is the block diagram which showed the function structure of the network control apparatus of the middle layer. This is the content of aggregated information exchanged between network control devices. It is explanatory drawing about the production | generation of the aggregate information passed from a low-order network control apparatus to a high-order network control apparatus. It is a data example of the production | generation result of the aggregate information passed from low order to high order. It is explanatory drawing about the production | generation of the aggregate information passed from a high-order network control apparatus to a low-order network control apparatus. It is an example of a data of the production | generation result of the aggregate information passed from upper level to lower level. It is a flowchart which shows the procedure of an information aggregation process. It is a flowchart which shows the procedure of a route calculation process. It is a sequence chart for demonstrating the cooperation of operation | movement between a low-order and a high-order network control apparatus. It is an example of route control for avoiding the occurrence of congestion. It is another example of the route control for avoiding the occurrence of congestion.

Hereinafter, embodiments for carrying out the present invention will be described in detail with reference to the drawings as appropriate.
FIG. 1 is a configuration example of a network according to an embodiment of the present invention. As shown in FIG. 1, the communication network 1 includes a large number of nodes N serving as traffic start points and end points, and links L for performing communication between these nodes. In addition, a plurality of network control devices 2 are installed to change the communication path so as to monitor the traffic of the communication network 1 and prevent the occurrence of congestion.

  FIG. 2 is an explanatory diagram of the hierarchy of the network topology and the control range. In FIG. 2, the control range 3 (3L, 3M, 3H) that each network control device 2 (2L, 2M, 2H) indicated by a thick broken line represents another control range with a boundary node BN (Boundary Node) as a boundary. And is hierarchically configured. The other nodes included in the control range are called local nodes LN (Local Node). Further, a node that is outside the control range of the traffic and in which traffic occurs with the control range of the node (indicated by a white circle in the figure) is called an external node EN (External Node).

  The control range 3L of the lowest layer is set by dividing the entire communication network into areas of an appropriate size. This division may be based on any conditions such as geographical conditions such as the location of nodes and links, physical conditions such as communication link bandwidth, and logical conditions such as facility management sources. In order to make the control load of each lower layer network control device 2L substantially equal, it is preferable to divide so that the number of nodes to be controlled and the number of links are substantially equal.

  As a division method, any division method can be applied. For example, the same number of nodes as the target number of the control range 3L of the lowest layer are randomly selected from the communication network 1 as representative nodes of each control range. Select, calculate the number of hops between each link L in the communication network 1 and each selected representative node, and include the link L in the same control range 3L as the representative node with the smallest number of hops. It is possible to do.

  In the example of FIG. 2, the control range 3M of the middle layer is set by collecting a plurality of control ranges 3L of the lowest layer, and all the control ranges 3M of the middle layer are collected to encompass the entire communication network. The control range 3H of the highest layer is set. In the example of FIG. 2, the control range of three layers is set. However, when the network size is small, two layers may be used. When the network size is large, the middle layer may be multi-staged to have four or more layers. Good.

  Note that such a hierarchical control range configuration is for determining the range to be controlled by each network control device 2, and the control target communication network itself does not need to be hierarchically configured. It can be applied to any network topology.

  Each control range 3 (3L, 3M, 3H) is associated with a network control device 2 (2L, 2M, 2H) that performs control within the control range. These network control devices 2 are configured by a computer having a communication function. If the processing performance of the computer is high, one network control device 2 may control a plurality of control ranges 3.

  FIG. 3 is an explanatory diagram regarding the relationship between the lower and upper control ranges and the network topology. The lower graph in FIG. 3 shows a topology structure corresponding to the control range 3 (3L in this example) on the lower layer side, and a thick broken line represents a boundary line of a certain control range 3L. Control target nodes within the control range indicated by black circles are classified into local nodes LN located inside the boundary line and boundary nodes BN located on the boundary line. All traffic transfers between the two control ranges are performed via the boundary node BN. For other control ranges, the boundary nodes BN of other control ranges in which traffic exists between the control ranges are included in the topology structure as external nodes EN indicated by white circles, and each external node EN and its own An external link EL, which is a virtual link, is set between the boundary node BN.

  The upper graph in FIG. 3 shows the topology structure corresponding to the upper-layer control range 3 (3M in this example), and the thick broken line represents the boundary of the control range 3M. In the upper layer side topology structure, the boundary node BN in each control range 3L on the lower layer side is included as a control target node, and the control corresponding to the boundary node BN included in the same control range 3L on the lower layer side is included. A logical link LL (Logical Link) that is a virtual link is set between the target nodes. For other control ranges, the boundary node BN of the other control range in which traffic exists between its own control ranges is included in the topology structure as an external node EN, and between each external node EN and its own boundary node BN. Sets the external link EL.

  In this way, by configuring the upper layer side topology structure to be limited only to the lower layer side boundary node BN, the upper layer side network control device 2 that controls the wider control range becomes the control target. The topology structure can be simplified.

  The thick broken-line arrows in FIG. 3 show examples of control target traffic that is traffic that is permitted to be changed in each network topology. Traffic that is inappropriate for route control is excluded from traffic to be controlled. In the traffic to be controlled, as illustrated in the lower graph of FIG. 3, the traffic from the external node EN to the other external node EN through its own control range as illustrated in the lower graph, or the upper graph of FIG. There is traffic between nodes in its own control range in addition to the traffic starting from one of the external node EN and one of the nodes within its own control range and the other as the end point.

  4 and 5 are block diagrams showing the functional configuration of the network control device 2. FIG. 4 shows the functional configuration of the lowest layer network control device 2L, and FIG. 5 shows the middle level network control device. 2M shows a functional configuration.

  As shown in FIG. 4, the lowest-layer network control device 2L includes a traffic information collection unit 21, an aggregate information generation unit 22L, a traffic information exchange unit 23L, a route calculation unit 24L, and a route control unit 25L. The These are realized by a CPU (Central Processing Unit) (not shown) included in the network control device 2L executing a predetermined program. The network control device 2L includes a topology DB (Database) 26 that holds information on the network topology, a traffic DB 27 that holds traffic information, and a route DB 28 that holds communication path information.

  The traffic information collection unit 21 periodically collects collected traffic information, which is information about the load (transfer traffic amount) of each link L included in its own control range 3L, from each node N. The link L to be collected includes an input link and an output link (not shown) having a terminal connected to each node N as a start point and an end point.

  The aggregate information generation unit 22L generates aggregate information to be passed to the upper network control device 2M or 2H. The method for generating the aggregate information will be described later. The traffic information exchange unit 23L transmits the aggregate information generated by the aggregate information generation unit 22L to the upper network control device 2M or 2H, and aggregates the load on the external link EL generated by the upper network control device 2M or 2H. Information is received as exchange traffic information.

  Based on the collected traffic information and the exchange traffic information, the route calculation unit 24L calculates an alternative communication route in the control range 3L so as to avoid the occurrence of congestion in the control range 3L. At this time, by referring to the exchange traffic information acquired from the host network control device 2M or 2H, a communication path that does not cause congestion in any external link EL is selected. The path control unit 25L performs a process of instructing each node in its control range 3L to actually change the communication path so that the communication path calculated by the path calculation unit 24L is obtained.

  As shown in FIG. 5, the middle-layer network control device 2M includes an aggregate information generation unit 22M, a traffic information exchange unit 23M, a route calculation unit 24M, and a route control unit 25M. These are realized by a CPU (not shown) included in the network control device 2M executing a predetermined program. The network control device 2M includes a topology DB 26 that holds information on the network topology, a traffic DB 27 that holds traffic information, and a route DB 28 that holds communication path information. Although illustration is omitted, the network control device 2H in the highest layer also has the same configuration.

  The aggregate information generation unit 22M generates aggregate information to be passed to the upper network control device 2M or 2H and aggregate information to be passed to the lower network control device 2L or 2M. The method for generating the aggregate information will be described later. The traffic information exchanging unit 23M transmits the respective aggregate information generated by the aggregate information generation unit 22M to the upper network control device 2M or 2H and the lower network control device 2L or 2M, respectively, and the lower network control device 2L or 2M. The aggregate information about the load on the logical link LL generated by the above and the aggregate information about the load on the external link EL generated by the higher-level network control device 2M or 2H are received as exchange traffic information.

  Based on the exchange traffic information, the route calculation unit 24M calculates an alternative communication route in the control range 3M so as to avoid the occurrence of congestion in the control range 3M. At this time, a communication path that does not cause congestion in any external link EL is selected by referring to the exchange traffic information acquired from the upper network control apparatus 2M or 2H. The route control unit 25M instructs the lower network control device 2L or 2M to actually change the communication route so that the communication route calculated by the route calculation unit 24M is obtained.

FIG. 6 shows the contents of aggregated information (exchange traffic information) exchanged between network control apparatuses. The aggregate information is composed of the following information about each bottleneck link that delivers the information.
-Link bandwidth: Maximum amount of traffic that can flow through the link-Link load: Current traffic amount of the link-Ratio of control target traffic via node pairs and links: Of the control target traffic of the network controller of the information transmission destination The ratio of the set of start / end node pairs passing through the link and the traffic between the node pairs via the link. Upper limit value and lower limit value of the traffic volume to be controlled: Information among the traffic flowing through the link. Upper and lower limits of the traffic volume to be controlled by the destination network controller

  FIG. 7 is an explanatory diagram for the generation of aggregate information to be passed from the lower-level network control device to the higher-level network control device. The lower graph in FIG. 7 represents the topology structure and traffic information held by the lower network control device 2L or 2M, and the upper graph in FIG. The topology structure and traffic information delivered to 2M or 2H are shown. Circles represent nodes N, and arrows represent links L. Each link L is represented by a combination of a node name on the transmission side and a node name on the reception side, for example, A → B. A value such as “100M” attached to each link is the link load of the link, and “M” means “megabit / second”.

  FIG. 8 is a data example of a generation result of aggregated information that is passed from lower to higher. The link load information shown in the upper left table of FIG. 8 represents the link load of each link in the lower graph of FIG. Further, the control target traffic and route information shown in the upper right table of FIG. 8 represent information on communication routes in the control range on the lower side of the control target traffic of the upper network control device 2M or 2H. In this example, the control target traffic passing through the upper node pair A → D passes through the lower A → B → C → D path and the upper node pair A → C at a rate of 100%. The control target traffic passes through the lower-order A → B → C path at a rate of 100%, and the control target traffic passing through the higher-order node pair C → D is 100% at the lower order C → D. The route is via.

  For the sake of simplicity, here, assuming that the bandwidth of each link on the lower side is the same, the margin of traffic until congestion occurs decreases as the link load increases. For the control target traffic passing through the node pair A → D, the link B → C having the largest link load among the three links A → B, link B → C, and link C → D via the traffic is the bottle. It becomes a neck link. Similarly, the link B → C is a bottleneck link for the control target traffic passing through the upper node pair A → C, and the link B → C is the link for the control target traffic passing through the upper node pair C → D. C → D is the bottleneck link.

  The aggregated information shown in the lower table of FIG. 8 is a table in which the information of the bottleneck links for the respective higher-level control target traffics identified in this way is tabulated. Note that the upper limit value and the lower limit value of the aggregated information will be described later. Further, the link identification information in the aggregate information is added for convenience in order to show correspondence with the link load information, and may not be included in the aggregate information delivered to the higher-level network control device 2M or 2H. . Further, the topology structure corresponding to the aggregate information shown in the lower table of FIG. 8 is such that each boundary node BN in the lower topology structure is controlled by the upper side as shown in the upper graph of FIG. It can be expressed as being connected by a logical link LL, which is a virtual link having an attribute of a bottleneck link corresponding to traffic.

  FIG. 9 is an explanatory diagram for the generation of aggregate information to be passed from the upper network control apparatus to the lower network control apparatus. The upper graph in FIG. 9 represents the topology structure and traffic information held by the upper network control device 2M or 2H, and the lower graph in FIG. It represents the topology structure and traffic information delivered to 2L or 2M.

  FIG. 10 is a data example of the information aggregation result of the aggregate information passed from the upper level to the lower level. The traffic information shown in the upper table of FIG. 10 represents the link load of each logical link LL in the upper graph of FIG. These pieces of information are generated by integrating the aggregate information delivered from each network control device 2L or 2M on the lower side.

  Here, a description will be given of a method for generating aggregate information to be transferred from the higher-level network control device 2M or 2H to the lower-level network control device 2L or 2M that handles the control range indicated by the broken line in FIG. The aggregate information delivered from the upper level to the lower level includes the bottleneck link information for the control target traffic whose destination is the node in the lower control range, and the bottleneck for the control target traffic whose starting point is the node in the lower control range. Link information.

  For example, in the traffic information shown in the upper table of FIG. 10, for the control target traffic flowing from the node G to the node A, the control target node pair G → A is included in the list of control target node pairs. The link H: A (link load: 100M) and the link H → A (link load: 400M) are routed. Of these, the link H → A with the higher link load is the bottleneck link. Similarly, for all controlled traffic that flows into node A, node C, and node D and all controlled traffic that flows out from node A, node C, and node D, the most link load among the links that the traffic passes through A link with a large is a bottleneck link.

  The aggregated information shown in the lower table of FIG. 10 is a table in which the information of the bottleneck links identified in this way is collected into a table. Note that the upper limit value and the lower limit value of the aggregated information will be described later. Further, the link identification information in the aggregate information is added for convenience in order to show the correspondence with the traffic information, and may not be included in the aggregate information delivered to the lower network control device 2L or 2M. Further, in the topology structure corresponding to the aggregate information shown in the lower table of FIG. 10, the nodes in the upper topology structure become the lower external nodes EN as shown in the lower graph of FIG. The node EN and each boundary node BN (node A, node C, node D) are connected by an external link EL which is a virtual link having a bottleneck link attribute corresponding to the higher-level control target traffic. Can be expressed as

  FIG. 11 is a flowchart illustrating a procedure of information aggregation processing. Hereinafter, the operation of the information aggregation process executed by the aggregation information generation unit 22 of each network control device 2 will be described in detail with reference to the flowchart of FIG.

  When the collection of periodic traffic information by the traffic information collecting unit 21 and the traffic information exchanging unit 23 is completed, this information aggregation process is activated for each network control device 2 that is the destination of the aggregate information.

  First, in step S11, a control target node pair that is a node pair corresponding to control target traffic to be aggregated is selected, and in step S12, it is determined whether or not all control target node pairs have been selected.

  If the selection of all control target node pairs is completed, that is, if there is no control target node pair that has not been selected (“Yes” in step S12), the process ends. When a control target node pair is selected, that is, when there is a control target node pair that has not yet been selected (“No” in step S12), traffic between the node pairs passes through its own control range in step S13. Among the communication paths to be performed, the bottleneck link, which is the link having the minimum traffic margin until congestion, is specified. At this time, a link whose utilization rate (= link load / link bandwidth) exceeds a predetermined threshold due to the smallest increase in traffic is determined to have a minimum margin.

  Next, in step S14, the ratio of the control target traffic passing through the identified bottleneck link passing through the link is extracted from the route information (route DB 28) and included in the aggregate information. Next, in step S15, an upper limit value and a lower limit value of the total traffic amount of the control target traffic are calculated and included in the aggregate information. At this time, when the transmission destination of the aggregate information is the higher-level network control device 2, out of the control range of the traffic to be controlled via the link becomes the start point and the end point (within the control range within the control range) The upper limit value and the lower limit value of the total traffic volume of the traffic that passes through are calculated by solving a linear programming problem with the traffic information acquired by itself as a constraint condition. In addition, when the transmission destination of the aggregate information is the lower network control apparatus 2, the nodes within the control range of the lower network control apparatus 2 among the control target traffic passing through the link are the start point and the end point, respectively. The upper limit value and the lower limit value of the total traffic amount of the traffic to be calculated are calculated by solving a linear programming problem with the traffic information acquired by itself as a constraint condition. After executing step S15, the process returns to step S11 to repeat the above processing.

  Here, a method of calculating the upper limit value and the lower limit value included in the aggregate information will be described. The upper limit value and the lower limit value indicate the range of the total amount of traffic that can be changed by the network control apparatus 2 that is the transmission destination of the aggregate information, among the traffic flowing through the respective bottleneck links. The upper limit value and the lower limit value can be calculated by solving the following linear programming problem.

  For each link included in its own control range, the traffic between each node pair of all start points and end points (a value greater than or equal to 0 and never negative) The total traffic amount obtained by summing the amount multiplied by the ratio of passing through the link is equal to the actually measured load (= traffic amount) of the link. Create an equation. Under the constraint that this simultaneous equation holds, the total amount of traffic that can be changed by the network control device 2 that is the destination of the aggregate information among the traffic flowing through the bottleneck link is the objective function. Then, two linear programming problems that maximize and minimize the objective function are solved. The maximum value and the minimum value of the total amount of traffic determined in this way are embedded in the aggregate information as the upper limit value and the lower limit value, respectively.

  As a result, the network control device 2L or 2M on the lower side specifies the bottleneck link in the path flowing in the control range for each control target traffic passing between the boundary nodes BN in the control range of the lower level. The upper limit value and the lower limit value of the total amount of the control target traffic including other control target traffic flowing through the bottleneck link are notified to the network control device 2M or 2H on the upper side. Further, the higher-level network control device 2M or 2H specifies the bottleneck link in the route flowing in its own control range for each traffic to be controlled having the node in the lower-side control range as the start point or the end point. An upper limit value and a lower limit value of the total amount of control target traffic including other control target traffic flowing through the bottleneck link are notified to the lower network control device 2L or 2M.

  Next, a route calculation process for changing the communication route while ensuring that no new congestion will occur based on the aggregated information will be described. In this route calculation process, each network control device 2 is based on the traffic information within its own control range, as well as the aggregated traffic information about the outside of its own control range acquired from the higher-level network control device 2. Then, an alternative communication path within the control range is calculated while ensuring that no new congestion occurs even outside the control range.

  FIG. 12 is a flowchart illustrating a procedure of route calculation processing. Hereinafter, the operation of the route calculation process executed by the route calculation unit 24 of each network control device 2 will be described in detail with reference to the flowchart of FIG.

  When the periodic traffic information collection by the traffic information collecting unit 21 and the traffic information exchanging unit 23 is completed, the route calculation process is started.

  First, in step S21, a link that needs congestion countermeasures is specified from the acquired traffic information within its own control range. At this time, it is determined that a link whose link usage rate exceeds a predetermined threshold (for example, 0.8) needs a countermeasure against congestion. Here, the description will be continued on the assumption that a link that needs congestion countermeasures has been identified.

  Next, in step S22, a node pair corresponding to the control target traffic passing through the identified link is selected, and in step S23, it is determined whether or not all control target node pairs have been selected. When selection of all control target node pairs is completed, that is, when there is no control target node pair that has not yet been selected (“Yes” in step S23), it is determined in step S29 that there is no alternative route, and the process ends. To do. When the control target node pair is selected, that is, when there is a control target node pair that has not been selected (“No” in step S23), the traffic between the node pairs is specified in step S21 in step S24. Other communication route candidates that do not pass through the selected link are selected by an arbitrary route selection method, and in step S25, it is determined whether or not selection of all route candidates has been completed.

  When selection of all the route candidates is completed, that is, when there is no route candidate that has not been selected yet (“Yes” in step S25), there is no suitable candidate route for traffic between the node pairs. Therefore, the process returns to step S22 to select the next control target node pair and repeat the above process. When another route candidate is selected, that is, when there is a route candidate that has not been selected yet (“No” in step S25), in step S26, all links for which the traffic information itself has traffic information. The maximum traffic amount after the route change is calculated, and it is determined in step S27 whether or not congestion occurs in any of the links, that is, whether or not there is a link whose link usage rate exceeds a predetermined threshold.

  At this time, in step S26, from the collected traffic information and aggregated information, the link that needs to be changed is specified, and the upper limit value and the lower limit value of the total amount of traffic that can be controlled by itself are acquired. In addition to the simultaneous equations for the total traffic volume of each link, the constraint that the total traffic volume to be controlled falls within the range between the upper limit value and the lower limit value is added. Is used as a variable to solve the linear programming problem of obtaining the maximum link usage rate among all links after the route change.

  If congestion occurs in any of the links (“Yes” in step S27), the process returns to step S24, selects another route candidate, and repeats the above processing. If congestion does not occur in any of the links (“No” in step S27), the selected candidate route is determined as an alternative route in step S28, and the process ends.

Here, the maximum traffic volume of each link after the route change is
(Maximum traffic volume of traffic other than controlled traffic via the link)
+ (Maximum amount of traffic to be controlled via the link)
It is. Of these, (the maximum traffic volume of traffic other than the control target traffic that passes through the link) is the link load of the link that it has and the total traffic volume of the control target traffic that passes through the link It can be determined from the upper limit value and the lower limit value. In addition, (the maximum traffic volume of the control target traffic via the link) is
(Traffic volume of each control target traffic)
× (Percentage of the controlled traffic passing through the link)
Is the total value for each control target traffic. This (traffic volume of each control target traffic) uses the traffic volume of each control target traffic as a variable, and includes the upper limit value of the total traffic volume of the control target traffic on each link included in the traffic information possessed by itself. It can be obtained by solving a linear programming problem with the lower limit as a constraint.

  Next, an operation in which a plurality of hierarchical network control devices cooperate to avoid the occurrence of congestion will be described. FIG. 13 is a sequence chart for explaining the linkage of operations between the lower and upper two network control devices. Here, a case will be described as an example where the lowest layer network control device 2L and the upper network control device 2M are linked.

  The lower network control device 2L periodically collects traffic information from each node within its control range (step S31), and generates aggregate information to be transmitted to the upper network control device 2M from the collected traffic information. (Step S32). Next, the generated aggregate information is transmitted to the host network control apparatus 2M (step S33: traffic information exchange), and the host network control apparatus 2M receives the aggregate information (step S41: traffic information exchange).

  The upper network control apparatus 2M acquires necessary aggregate information from the other lower network control apparatus 2L and its own upper network control apparatus 2M or 2H, and then transmits the aggregate information to be transmitted to the lower network control apparatus 2L. Is generated (step S42), and the generated aggregate information is transmitted to the lower network control device 2L (step S43: traffic information exchange).

  The lower network control device 2L receives the aggregated information (step S34: Traffic information exchange), and the traffic information within the control range collected by itself and the traffic included in the aggregated information acquired from the upper network control device 2M. Based on the information, a route calculation for preventing the occurrence of congestion is performed (step S35). If an appropriate alternative route is found within its own control range ("Yes" in step S36), the alternative is calculated. Route control for shifting to the route is executed (step S38).

  On the other hand, if an appropriate alternative route is not found within its own control range (“No” in step S36), it waits for new route setting information to be transmitted from the higher-level network control device 2M, and this information is stored. When received (step S37), the path control for switching to the path specified by the path setting information is executed (step S38).

  On the other hand, the upper network control device 2M also causes congestion due to a route change within its own control range based on the traffic information about the bottleneck link included in the aggregate information acquired from each lower network control device 2L. Route calculation to prevent occurrence is performed (step S44), and if an appropriate alternative route is found (“Yes” in step S45), route setting information for shifting to the alternative route is generated and applied. To the lower-level network control device 2L (step S46). If a suitable alternative route is not found (“No” in step S45), the illustration is omitted, but if there is a higher level network control device 2M or 2H, the instruction is waited, and if not, nothing is done.

  As described above, when the lower network control device 2L finds an appropriate alternative route, priority is given to the transition to the alternative route, and when the appropriate alternative route is not found, the upper network control device 2M finds it. By adopting alternative routes over a wide range, it is possible to localize the influence range of the route change as much as possible and improve the stability of the entire network.

  Finally, an example of path control for preventing the occurrence of congestion will be described. 14 and 15 are examples of path control for preventing the occurrence of congestion. Here, it is assumed that the bandwidth of each link is 1 gigabit / second, and a link whose link usage rate is 0.8 or more is subject to path control.

  In the upper graph of FIG. 14, in the state before the path change, the control target traffic of 400 Mbit / sec from the node E to the node F and the control target traffic of 400 Mbit / sec from the node A to the node C are as follows: Since both link A → D and link D → C, the link usage rate of these two links is 0.8. In this case, for example, if the route of the controlled traffic from node A to node C is changed as A → B → C, the link usage rate of all links is set to 0.4 as shown in the lower graph. be able to.

  In the upper graph of FIG. 15, the control target traffic of 400 Mbit / sec from the node G to the node H and the control target traffic of 400 Mbit / sec from the node D to the node I in the state before the path change are as follows: Since both link via the link D → C, the link usage rate of this link is 0.8. In this case, for example, if the route of the control target traffic from the node G to the node H is changed as G → A → B → H, the link usage rate of all the links is set to 0.4 as shown in the lower graph. It can be as follows.

  As described above, according to the present invention, the network control device in the lowest layer can collect information at high speed and frequently because the range of the traffic information to be collected is localized. In addition, since the host network control device that needs to grasp traffic information in a wider range only needs to collect a small amount of traffic information that is subordinate to itself or from the host network control device, the amount of information to be collected is reduced. High-speed and frequent information collection is possible. In addition, when preventing the occurrence of congestion, the network stability can be improved by giving priority to the local route change in the lower layer as much as possible.

  Although description of the form for implementing this invention is finished above, the aspect of this invention is not restricted to this, A various change is possible within the range which does not deviate from the meaning of this invention.

1 Communication Network 2 (2L, 2M, 2H) Network Controller 3 (3L, 3M, 3H) Control Range L Link N Node BN Boundary Node LN Local Node EN External Node LL Logical Link EL External Link 21 Traffic Information Collection Unit 22 ( 22L, 22M) Aggregation information generation unit 23 (23L, 23M) Traffic information exchange unit 24 (24L, 24M) Route calculation unit 25 (25L, 25M) Route control unit 26 Topology DB
27 Traffic DB
28 Route DB

Claims (7)

A network control method for monitoring traffic in a network composed of a plurality of nodes and a link for communicating between the nodes, and changing a communication path so as to prevent occurrence of congestion,
The entire network is divided into a plurality of control ranges geographically, physically, or logically, and a higher control range is set hierarchically by combining a plurality of control ranges. , Associated with a network control device for controlling the control range,
The network control device that controls the control range of the lowest layer collects and acquires load information of each link connected to the node from each of the nodes within its control range,
When there is a lower level network control device that controls a control range that is one level lower than its own control range, each of the network control devices is associated with each traffic to be controlled that passes through the lower level control range. The load information of the bottleneck link having the smallest link load margin among the links in the lower control range through which the traffic passes is acquired from the lower network control device,
Each of the network control devices, when there is an upper network control device that controls a control range that is one level higher than its own control range, flows out from a node within its own control range to the upper control range. For traffic and each traffic that flows from the upper control range to a node within its own control range, the link load margin is minimized among the links in the upper control range through which the traffic passes. The load information of the bottleneck link being
Each of the network control devices, based on the acquired load information of each link including the bottleneck link, in order to prevent the occurrence of congestion in its own control range in the control range of its own When the link is specified and the communication path within its own control range is changed, the maximum link of each link after the path change is solved by solving the linear programming problem based on the load information of each link including the bottleneck link A network control method characterized by calculating a usage rate and determining a route in which any maximum link usage rate does not exceed a predetermined threshold. The network control method according to claim 1,
Control of route change according to the determined route is performed by giving priority to the lower network control device among the network control devices that control traffic to be changed. Method. In the network control method according to claim 1 or 2,
A network comprising a node located on a boundary line of a plurality of control ranges in a hierarchy and a virtual logical link connecting these nodes to form a topology of a control range one level higher in the hierarchy Control method. A network control device that monitors traffic in a network composed of a plurality of nodes and a link for performing communication between the nodes, and changes a communication path so as to prevent occurrence of congestion,
The entire network is divided into a plurality of control ranges geographically, physically, or logically, and a higher control range is set hierarchically by combining a plurality of control ranges. , The network control device for controlling the control range is associated,
The network control device that controls the control range of the lowest layer includes information collection means that collects and acquires load information of each link connected to the node from each of the nodes within its control range. ,
Each of the network control devices
When there is a lower level network control apparatus that controls a control range that is one level lower than its own control range, for each traffic to be controlled that passes through the lower level control range, the lower level through which the traffic passes The load information of the bottleneck link that has the smallest link load margin among the links within the control range is acquired from the lower network control device,
When there is a higher-level network control device that controls a control range that is one level higher than its own control range, each traffic that flows out from a node within its own control range to the higher-level control range, and the higher-level control For each traffic that flows from a range to a node within its own control range, the load information of the bottleneck link that has the smallest link load margin among the links in the higher control range through which the traffic passes Information exchange means for obtaining the information from the higher-level network control device,
Based on the acquired load information of each link including the bottleneck link, in order to prevent the occurrence of congestion within its own control range, the link within its own control range should be identified and controlled by itself. When changing the communication route within the range, the maximum link usage rate of each link after the route change is calculated by solving the linear programming problem based on the load information of each link including the bottleneck link, A network control apparatus comprising: a route calculation unit that determines a route in which the maximum link usage rate does not exceed a predetermined threshold. The network control device according to claim 4,
Control of route change according to the determined route is performed by giving priority to the lower network control device among the network control devices that control traffic to be changed. apparatus. In the network control device according to claim 4 or 5,
A network comprising a node located on a boundary line of a plurality of control ranges in a hierarchy and a virtual logical link connecting these nodes to form a topology of a control range one level higher in the hierarchy Control device. A network comprising: a plurality of nodes; a link for performing communication between the nodes; and the network control device according to any one of claims 4 to 6.

Images