JP6826486B2 - Network design equipment and network design method - Google Patents

Description

The present invention relates to a network design device and a network design method.

Network operators need to properly design the network topologies that make up communication networks in order to efficiently accommodate traffic while satisfying various carrier-specific reliability and quality policies. Generally, a physical topology consisting of physical nodes (set in the station building) and physical links (eg pipelines, fibers) is set, and the transmission layer path (wavelength path, ODU (wavelength path)) is set there. By establishing an Optical channel Data Unit) and an MPaS-TP (Multi-Protocol Label Switching-Transport Profile) path), a logical topology for the upper packet layer is provided. That is, the network topology design problem is defined as a problem of designing a physical topology and a logical topology that optimizes objective function values such as equipment cost when AC traffic between physical nodes is given. Note that nodes on the logical topology (IP (Internet Protocol) routers, etc.) are usually housed in the station building and have a one-to-one relationship with physical nodes. Therefore, the problem of designing the logical topology is to design the path of the transmission layer. It can also be seen as a problem.

Many studies have been conducted on the design problem of the logical topology for a long time, and the typical method is described in Non-Patent Documents 1 and 2.

D. Banerjee and B. Mukherjee, "Wavelength-Routed Optical Networks: Linear Formulation, Resource Budgeting Tradeoffs, and a Reconfiguration Study," IEEE / ACM Transactions on Networking (TON), Vol. 8, no. 5, pp. 598- 607, Oct. 2000. (IEEE is a registered trademark) Y. Koizumi, T. Miyamura, S. Arakawa, E. Oki, K. Shiomoto, and M. Murata, "Adaptive Virtual Network Topology Control Based on Attractor Selection," IEEE / OSA Journal of Lightwave Technology, Vol. 28, no . 11, pp. 1720-1731, Jun. 2010.

Conventional algorithms for designing logical topologies aim only at traffic accommodation efficiencies such as equipment cost, wavelength efficiency, and maximum link utilization under physical network constraints such as avoidance of wavelength collisions and upper limits on the number of physical ports. The optimization is done. However, existing carriers have established carrier policies regarding reliability, quality conditions, suppression of the effects of (failure) signal propagation due to the protocol characteristics of the packet layer, etc., which are peculiar to carrier networks, but conventional algorithms. However, there is no network topology design that reflects such carrier policies. The technologies of Non-Patent Documents 1 and 2 also do not design the network topology after reflecting the carrier policy.

In view of such circumstances, it is an object of the present invention to realize a design of a network topology that reflects a carrier policy.

In order to solve the above-mentioned problems, the invention according to claim 1 is a network design device that designs a logical topology based on a physical topology and AC traffic, and divides the physical topology into a plurality of partitions and divides the physical topology into a plurality of partitions. A virtual physical topology is created by combining the above partitions, the amount of traffic flowing between each of the partitions is calculated, and the virtual AC traffic generated in the virtual physical topology is calculated based on the calculated traffic amount. The virtual logic topology is output by the optimization operation with the virtual physical topology and the virtual AC traffic as inputs, and with respect to the virtual logic topology, the station building in the partition is geographically divided. the logical topology based on the carrier policy distributed design, with respect to the virtual logical topology, with respect to the inter-section of the compartment, Bei give a logical topology designing unit, for designing the logical topology based on the optimizing operation, the logic In the ring-shaped physical network in the partition, the topology design unit is an act standby system in which two physical nodes isolated by a predetermined distance or more among the physical nodes in the partition are used as relay nodes and the rest are edge nodes. It is characterized by designing a logical topology .

The invention according to claim 3 is a network design method in a network design device for designing a logical topology based on a physical topology and AC traffic. The network design device divides the physical topology into a plurality of partitions. Then, the step of combining the divided partitions to calculate the virtual physical topology and the amount of traffic flowing between each of the partitions are calculated, and the virtual generated in the virtual physical topology is calculated based on the calculated traffic amount. With respect to the step of creating the AC traffic, the step of outputting the virtual logical topology by the optimization operation with the virtual physical topology and the virtual AC traffic as the input, and the partition of the partition with respect to the virtual logical topology. A step of designing a logical topology based on a carrier policy that geographically distributes station buildings in the partition, and a logical topology based on the optimization operation are designed between the partitions of the partition with respect to the virtual logical topology. a step of, by the execution, the in the step of designing the logical topology in a ring-shaped physical network of the compartment, relay two physical nodes isolated a predetermined distance or more of the physical node of said compartment node The feature is to design the logical topology of the act standby system with the rest as edge nodes .

According to the inventions of claims 1 and 3 , a logical topology that uniformly satisfies the carrier policy can be designed within the partition, and an optimized logical topology can be designed between the partitions. Therefore, it is possible to easily introduce a mechanism that satisfies the carrier policy in the design problem of the network topology related to the optimization for the purpose of traffic accommodation efficiency.
Therefore, it is possible to realize the design of the network topology that reflects the carrier policy.
As a result, it is possible to provide traceability of packet layer routing in normal times and in the event of a failure, to provide a reliability design by securing an act standby system in the partition, and to geographically distribute the station buildings in the partition (for example, which could not be realized in the past. It is possible to provide design results according to the carrier policy, such as providing a severe countermeasure design by isolating 50 km) and providing localization of the fault signal propagation range within the section.

The invention according to claim 2 is the network design apparatus according to claim 1, and the logical topology design unit determines the connection relationship of the logical topology when designing the logical topology between the partitions. It is characterized by designing a logical topology based on a control matrix that changes.

Further, the invention according to claim 4 is the network design method according to claim 3, and when executing the step of designing a logical topology with respect to the partitions, the network design apparatus uses the logical topology. It is characterized by designing a logical topology based on a control matrix that changes the connection relationship of.

According to the inventions of claims 2 and 4 , the carrier policy can be reflected even between the compartments by using the control matrix .

According to the present invention, it is possible to realize the design of the network topology that reflects the carrier policy.

This is an example of a configuration diagram of the entire system including the network design device of the present embodiment. This is an example of the functional configuration diagram of the network design device. It is a flowchart which shows the topology design process in a network design apparatus. (A) is a diagram showing an example of a physical topology, (b) is a diagram showing an example of division of a physical topology, and (c) is a diagram showing an example of a created virtual physical topology. It is a figure which shows the example of the design in a partition, (a) is the figure which shows the example of a ring type physical cluster, (b) is a figure which shows the example of the 2nd floor act standby logical topology, (c) is the figure which shows the node for convenience It is a figure which shows the example of the 2nd floor act standby logical topology arranged in an easy-to-see manner. It is an explanatory diagram of a control matrix, (a) is an explanatory diagram of a definition of a control row example operator, and (b) is an explanatory diagram of an example when a control matrix is applied to an adjacency matrix.

Embodiments of the present invention will be described in detail with reference to the drawings.

≪Overall composition≫
As shown in FIG. 1, the system of this embodiment includes a network design device 1, a network operation device 2, and a communication NW (network).
The communication NW is a physical topology having a large number of physical nodes N and a physical link L connecting each physical node N. The physical node N is, for example, a communication facility provided in a station building, and accommodates a packet node such as a router or an optical transmission device inside the physical node N. The physical link L is, for example, a pipeline or an optical fiber.

The network design device 1 is a device that solves a network topology design problem for a communication NW.
The network operation device 2 is a device that monitors the communication NW. As the monitoring result of the communication NW, the network operation device 2 transmits, for example, information on the traffic occurrence state (traffic amount) to the network design device 1 or another device (not shown).

The network design device 1 and the network operation device 2 are computers provided with hardware such as a storage unit, a control unit, a communication unit, an input unit, and an output unit. For example, the control unit can execute each of the following processes by expanding the program stored in the storage unit into the storage area of the storage unit and executing the program.

<Functional configuration of network design device 1>
The functional configuration of the network design device 1 will be described.
As shown in FIG. 2, the network design device 1 includes a route design unit 11, a logical topology design unit 12, another device IF13, a packet route management DB 14, a logical network configuration information DB 15, and a physical network configuration information DB 16. , A functional unit such as a traffic information DB17 is provided.

The route design unit 11 calculates the route of the packet layer based on the information stored in the logical network configuration information DB 15.
The logical topology design unit 12 calculates the logical topology for the communication NW based on the information of the physical network configuration information DB 16 and the information of the traffic information DB 17.
The other device IF13 is an interface with the network operating device 2 or an interface with another device. The other device is, for example, a management console used by a network operator.

The packet route management DB 14 stores route information for each ground in the packet layer of the communication NW. The route information is acquired as a calculation result of the route design unit 11 or is acquired by input from a network operator.

The logical network configuration information DB 15 stores the logical topology information indicating the contents of the logical topology of the communication NW and the transmission path information indicating the transmission path in the transmission layer of the communication NW. The contents of the logical topology include, for example, the connection relationship between the logical node and the logical link. The transmission path indicated by the transmission path information is, for example, a ground or a route. The logical topology information and the transmission path information are output results from the logical topology design unit 12. Since the substance of the logical link is a transmission path (corresponding to the physical link L in FIG. 1), it is preferable to manage the logical topology information and the transmission path information in the same DB. However, the logical topology information and the transmission path information may be managed in different DBs.

The physical network configuration information DB 16 stores physical topology information indicating the contents of the physical topology as a communication NW. The contents of the physical topology include, for example, the connection relationship between the physical node N and the physical link L. The network design device 1 can acquire the physical topology information from, for example, the network operation device 2 or by inputting from the network operator.

The traffic information DB 17 stores traffic information indicating the traffic for each logical link and AC traffic information between physical nodes N (or logical nodes) based on the traffic information. The network design device 1 can acquire traffic information and AC traffic information from, for example, the network operation device 2.

<Processing of network design device 1>
The topology design process for solving the network topology design problem for the communication NW (FIG. 1) in the network design device 1 will be described.

As shown in FIG. 3, first, the network design apparatus 1 executes the creation of the virtual physical topology as the first pre-processing by the logical topology design unit 12 (step S1). Specifically, the network design device 1 divides the physical topology to be designed into partitions (clusters) having a certain regularity (eg, the geographical position between physical nodes is within a predetermined distance: geographical characteristics). ), And join each cluster after the division. The combined cluster group is called a virtual physical topology.

For the division of physical topology, for example, see References (Kamamura et al., “Network Topology Principal Component Analysis Method by High-Speed Graph Mining,” in IEICE IEICE Technical Report, October 13, 2016, NS2016-99, pp.57. The technical content described in -62) can be used. Details of the technical contents of the references will be omitted. According to the reference, the cluster is a subgraph (a subgraph that is a subset of the target graph), and in the present embodiment, it is a ring graph (described later).

As shown in FIG. 4A, a physical topology consisting of a set of physical nodes and physical links arranged at geographically different positions is divided by reference. Then, a plurality of ring graphs (graphs in which at least two physical links are connected to each physical node) as shown in FIG. 4B are created. Each cluster that becomes a ring graph is registered as a node of the virtual physical topology. FIG. 4C illustrates a virtual physical topology in which clusters represented by circled numbers 0 to 7 are connected by a link (shown by a solid line). Regarding the link connecting the clusters, for example, when the physical node l belonging to the cluster i and the physical node m belonging to the cluster j (i, j, l, m are all combinations) are connected, the cluster It is possible, but not limited to, that a link is added between i and j.

With respect to a plurality of partitions after division, for example, routing by OSPF (Open Shortest Path First) may be executed within the partition, and routing by BGP (Border Gateway Protocol) may be executed between partitions. it can.

When the routing design is performed for one large-scale physical topology without dividing as a partition as in the conventional case, the routing design is indirect based on the traffic accommodation efficiency such as the link cost, which is desirable. There was a high possibility that the routing could not be realized. On the other hand, by dividing the physical topology into a plurality of partitions as in the present embodiment, it is possible to realize a uniform routing design within the partition, and it becomes possible to easily realize a desired routing. ..

In addition, as in the past, in a physical topology that does not divide as a partition, there is generally no regularity in visiting routes, and route traceability is low. On the other hand, according to the present embodiment, it is possible to execute the division so as to be able to provide high route traceability. Further, if it is divided as a partition, fault propagation can be suppressed in one partition, and a highly reliable network topology design can be realized.

Returning to FIG. 3, the network design device 1 then executes the calculation of the virtual AC traffic as the second pre-processing by the logical topology design unit 12 (step S2). Specifically, the network design device 1 calculates the AC traffic generated in the virtual physical topology created in the first preprocessing as the virtual AC traffic based on the traffic information DB 17. When calculating virtual AC traffic, for example, for all clusters that make up a virtual physical topology, the amount of traffic that flows from cluster i to cluster j is distributed from each physical node that belongs to cluster i to each physical that belongs to cluster j. It is the sum of the traffic amount flowing to the node.

Next, the network design device 1 performs an optimization operation related to the design problem of the logical topology by the logical topology design unit 12 as the main process (step S3). Specifically, the network design device 1 performs an optimization operation by inputting the virtual physical topology created in the first preprocessing and the virtual AC traffic created in the second preprocessing, and virtualizes the operation result. Output as a logical topology. The method of the optimization operation may be an existing method, and for example, the I-MLTDA method proposed in Non-Patent Document 1 can be used.

Next, the network design device 1 executes the design in the partition for the virtual logic topology output in step S3 as the first post-processing by the logic topology design unit 12 (step S4). The design in the compartment is a manual design based on the carrier policy. In the present embodiment, since the physical network in Ward picture becomes ring, selects two of the physical nodes in the picture as a relay node, by the remaining edge node, physically exclusive also It is possible to design a logical topology that forms an act-standby system in which various routes can be selected.

For example, with respect to the section C shown in FIG. 5A (corresponding to the section C shown in FIG. 4B and corresponding to the cluster represented by the circled number 7 shown in FIG. 4C), FIG. As shown in (b), two relay nodes r1 and r2 and six edge nodes e1 to e6 are selected. Further, in FIG. 5B, the logical nodes L1 to L8 and the logical links (shown by thick lines) constituting the virtual logical topology corresponding to the partition C are set by the optimization operation (step S3). The logical nodes L1 to L8 are prepared for the relay nodes r1 and r2 and the edge nodes e1 to e6, respectively. Further, in FIG. 5B, a pair of a logical node serving as an act system and a logical node serving as a standby system is represented by a two-point chain line (example: a logical node L3 serving as an act system and a standby system). Logical node L4), the second-order act standby logical topology is shown.

FIG. 5C shows the relationship between the relay node and the edge node by changing the arrangement of the logical nodes L1 and L2 of the relay nodes r1 and r2 and the logical nodes L3 to L8 of the edge nodes e1 to e6. , The relationship of the act standby system is easy to see. The logical node L1 is an act system, and the logical node L2 is a standby system.

When designing the logical topology according to step S4, by selecting two relay nodes isolated by a predetermined distance or more, it is possible to prevent a failure due to a catastrophic disaster from occurring in only one relay node. It is possible to take measures against catastrophic disasters.
The logical topology design unit 12 stores the logical topology, which is the final output of the first post-processing, in the logical network configuration information DB 15 as the logical topology information. In addition, the logical topology design unit 12 also outputs transmission path information in the transmission layer for the output partition for the virtual topology, and stores it in the logical network configuration information DB 15. This transmission path information represents a connection relationship regarding logical nodes and logical links in the partition.

Returning to FIG. 3, the network design apparatus 1 then executes the inter-partition design for the virtual logical topology output in step S3 as the second post-processing by the logical topology design unit 12 (step S5). .. Specifically, the network design device 1 calculates the connection between clusters and designs a logical topology based on the optimization operation in step S3. At the time of the calculation, in each cluster, one of the physical nodes constituting the cluster is selected as the representative node. The representative node is given as a pre-parameter by input from the network operator, for example.

By connecting a link between the representative node belonging to cluster i and the representative node belonging to cluster j, a virtual link can be set between clusters i and j (i and j are all combinations). , it is possible to realize the design of inter-district image. Required to design between ward image, connection of the primary node between different clusters, according to the result of the optimization calculation of step S3.

Further, a plurality of representative nodes can be defined for one cluster, and in this case, for example, the representative nodes connected by the round robin method can be sequentially changed.
Logical topology designing unit 12, the final output of the second post-processing, and stores the virtual links representing connections between wards picture, the logical network configuration information DB15 as the logical topology information.

Next, the network design device 1 executes a design using the control matrix as a third post-processing by the logical topology design unit 12 (step S6). The processing up to the second post-processing for the Ku image designed logical topology connection relationship according to the carrier policy is determined, for inter Ward picture logical topology connection relationship is determined based on optimization calculation Designed. If you want to apply the carrier policy, including connections between Gu image, that is, when it is desired to determine the connections between partitions based on the carrier policy, as the third post-processing, the design using the control matrix ..

The control matrix has the function of forcibly changing the connection relationship of the logical topology to the desired connection relationship. As shown in FIG. 6A, the control matrix has a control matrix operator that is summed to any matrix "A". The control matrix operator takes three types of values: "-1", "1", and "0".

The control matrix operator "-1" represents don't care and does not change the matrix "A".
The control matrix operator "1" represents that there is a connection between the nodes, and among the components of the matrix "A", the component that represents no connection between the nodes is changed to a component that has a connection between the nodes.
The control matrix operator "0" represents no connection between nodes, and among the components of the matrix "A", the component representing the connection between nodes is changed to the component without connection between nodes.

The connection relationship of the logical topology can be expressed as an adjacency matrix having a value of "1" between nodes with a connection and "0" between nodes without a connection. By adding the control matrix to this adjacency matrix, the shape of the logical topology can be forcibly changed.

As shown in FIG. 6B, a case where the control matrix is added to the adjacency matrix representing the connection relationship of the node groups having the label values of Osaka (a0), Tokyo (a1), and Nagoya (a2) will be described. Since there is a connection between the nodes between Osaka (a0) and Nagoya (a2) and between the nodes between Tokyo (a1) and Nagoya (a2), the corresponding component of the adjacency matrix is "1" and Osaka (a0). ) And Tokyo (a1) have no connection, so the corresponding component of the adjacency matrix is "0". The diagonal component of the adjacency matrix represents the connection with its own node and is a meaningless component, so it is set to "0" for convenience.

When the values of the components of the control matrix are "1" and "0", these values overwrite the values of the components of the adjacency matrix as shown in FIG. 6A. As a result, when the control matrix shown in FIG. 6B was added to the adjacency matrix related to Osaka (a0), Tokyo (a1), and Nagoya (a2), the values of each component of the adjacency matrix were overwritten and corrected. The adjacency matrix is calculated. As a result, the connection between the nodes between Osaka (a0) and Nagoya (a2) is changed to no, and the connection between the nodes between Osaka (a0) and Tokyo (a1) is changed to yes. In this way, the network design device 1 regulates that the node having the label value of Osaka (a0) and Nagoya (a2) is connected to the node having the label value of Tokyo (a1) by using the control matrix. Can be written.

This completes the topology design process in the network design device 1 shown in FIG.
After the topology design process shown in FIG. 3, the network design device 1 calculates the packet layer route by the route design unit 11. The calculation result by the route design unit 11 is stored in the packet route management DB 14.

(Summary)
According to the present embodiment, it is possible to design a logical topology that uniformly satisfies the carrier policy within the partition, and to design an optimized logical topology between the partitions. Therefore, it is possible to easily introduce a mechanism that satisfies the carrier policy in the design problem of the network topology related to the optimization for the purpose of traffic accommodation efficiency.
Therefore, it is possible to realize the design of the network topology that reflects the carrier policy.

As a result, it is possible to provide traceability of packet layer routing in normal times and in the event of a failure, to provide a reliability design by securing an act standby system in the partition, and to geographically distribute the station buildings in the partition (for example, which could not be realized in the past. It is possible to provide design results according to the carrier policy, such as providing a severe countermeasure design by isolating 50 km) and providing localization of the fault signal propagation range within the section.

Further, by using the control matrix, the carrier policy can be reflected even between the sections.

≪Modification example≫
The present invention is not limited to the above-described embodiment, and can be modified without departing from the spirit of the present invention. For example, different carriers are used for each of a plurality of partitions when the physical topology is divided. The policy can be applied.

Further, it is also possible to realize a technique in which various techniques described in the present embodiment are appropriately combined.
Further, the software described in the present embodiment can be realized as hardware, and the hardware can be realized as software.
In addition, the hardware, software, processing procedure, and the like can be appropriately changed without departing from the spirit of the present invention.

1 Network design equipment 11 Route design department 12 Logical topology design department 13 Other equipment IF
14 Packet route management DB
15 Logical network configuration information DB
16 Physical network configuration information DB
17 Traffic Information DB

Claims (4)

A network design device that designs a logical topology based on physical topology and AC traffic.
The physical topology is divided into a plurality of partitions, and the divided partitions are combined to create a virtual physical topology.
The amount of traffic flowing between each of the compartments is calculated, and the virtual AC traffic generated in the virtual physical topology is calculated based on the calculated traffic amount.
The virtual logic topology is output by the optimization operation with the virtual physical topology and the virtual AC traffic as inputs.
For the virtual logic topology, with respect to the inside of the section, a logic topology based on a carrier policy that geographically distributes the station buildings in the section is designed.
The relative virtual logical topology, with respect to the inter-section of the compartment, Bei give a logical topology designing unit, for designing the logical topology based on the optimization operation,
In the ring-shaped physical network in the partition, the logical topology design unit uses two physical nodes isolated by a predetermined distance or more as relay nodes and the rest as edge nodes in the act standby. A network design device characterized by designing the logical topology of a system. When designing the logical topology between the partitions, the logical topology design unit
Design a logical topology based on a control matrix that changes the connection relationship of the logical topology.
The network design apparatus according to claim 1. A network design method in a network design device that designs a logical topology based on physical topology and AC traffic.
The network design device is
A step of dividing the physical topology into a plurality of partitions and combining the divided partitions to create a virtual physical topology.
A step of calculating the amount of traffic flowing between each of the compartments and calculating the virtual AC traffic generated in the virtual physical topology based on the calculated traffic amount.
A step of outputting a virtual logic topology by an optimization operation using the virtual physical topology and the virtual AC traffic as inputs, and
With respect to the virtual logic topology, with respect to the inside of the section, a step of designing a logic topology based on a carrier policy that geographically distributes the station buildings in the section,
To the virtual logical topology, the terms Between Lot, perform the steps of: designing a logical topology based on the optimization operation,
In the step of designing the logical topology, in the ring-shaped physical network in the partition, two physical nodes isolated by a predetermined distance or more among the physical nodes in the partition are set as relay nodes, and the rest are set as edge nodes. A network design method characterized by designing an act-standby logical topology . When the network design device performs the steps of designing a logical topology for the partitions of the partition,
Design a logical topology based on a control matrix that changes the connection relationship of the logical topology.
The network design method according to claim 3 , characterized in that.

Images