Detailed Description
In the embodiment of the invention, a first request is received, and effective cross-subnet routing is determined according to the first request; sending a second request to the effective sub-network passed by the effective cross-sub-network route to acquire the topology information of the effective sub-network; and determining end-to-end routing information according to the effective cross-subnet route and the topology information, and selecting the route represented by the end-to-end routing information as the end-to-end route.
Before further details of the embodiments of the present invention are described, terms used in the embodiments of the present invention will be described first.
And service, providing the signal transmission capability for the user.
Routing: the set of nodes through which traffic passes.
Side: refers to a certain specific relationship between the objects under study. And when calculating the route, the method refers to the connection relation of 2 researched objects.
And (4) routing constraint: the resources are entered by the user, requiring that the results calculated by the routing computation must (or must not) be passed through.
End point: the start or end of a service.
A network control system: the system may be a network manager, an Automatic Switch Optical Network (ASON), a Software Defined Network (SDN) controller, or other similar systems. The network control system comprises an upper-level subnet controller and a lower-level subnet controller.
It should be noted that the method and apparatus provided in the embodiment of the present invention can be applied to the network structure shown in fig. 1, where the network controller of the upper subnet shown in fig. 1 is an upper subnet controller, the subnets (sn, subnet)1, sn2, sn3, sn4, and sn5 are lower subnets below the upper subnet, each lower subnet is provided with its own network controller, and the network controller of the lower subnet is a lower subnet controller. Here, one upper subnet may include a plurality of lower subnets.
The invention is further described in detail below with reference to the drawings and the specific embodiments.
Fig. 2 is a method for determining an end-to-end route according to an embodiment of the present invention, where the method is applied to an upper-level subnet controller, and as shown in fig. 2, the method includes the following steps:
step 201, when receiving a first request, determining an effective cross-subnet route according to the first request;
specifically, when the upper subnet controller receives a first request triggered by a user for calculating an end-to-end route, the upper subnet controller determines, according to a specified starting end point and a specified terminating end point carried by the first request, a lower subnet to which the starting end point belongs as a starting subnet, determines the lower subnet to which the terminating end point belongs as a terminating subnet, calculates, by using a shortest route policy, a shortest route across subnets between the starting subnet and the terminating subnet, and determines the shortest route across subnets as the effective route across subnets.
Here, the shortest route policy is the cross-subnet route with the lowest route cost.
Here, after determining the valid inter-subnet route, the lower subnet through which the valid inter-subnet route passes is identified as a valid subnet, and the lower subnet through which the valid inter-subnet route does not pass is identified as an invalid subnet.
Step 202, sending a second request to the effective subnet passed by the effective cross-subnet route to obtain the topology information of the effective subnet;
specifically, after determining the effective cross-subnet route, sending a second request to subordinate subnet controllers of all subordinate subnets through which the effective cross-subnet route passes, where all the subordinate subnets through which the effective cross-subnet route passes are effective subnets; after sending the second request, receiving topology information reported by the effective subnet, wherein the topology information includes: the shortest route of the effective subnet and the edge node corresponding to the shortest route.
Before sending the second request to the active subnet through which the active cross-subnet route passes, the method further comprises: acquiring boundary points of the effective subnets; calculating an abstract topology of the effective cross-subnet route according to the boundary points; obtaining an effective abstract route according to the effective cross-subnet route and the abstract topology; wherein, the abstract topology is concretely as follows: and taking the effective subnet as the route calculated by the full-crossover object.
Step 203, determining end-to-end routing information according to the effective cross-subnet route and the topology information, and selecting the route represented by the end-to-end routing information as an end-to-end route;
specifically, the effective route in the subnet of the effective subnet is calculated according to the boundary node of the effective abstract route on the effective subnet; and generating the end-to-end routing information according to the effective abstract routing and the effective routing in the subnet. The route characterized by the end-to-end route information is an end-to-end route.
The method further comprises the following steps: selecting at least two end-to-end routes, setting one end-to-end route of the at least two end-to-end routes as a working route, and setting the end-to-end routes except the working route as protection routes.
As shown in fig. 3, the method for determining end-to-end routing is illustrated by taking the networking in which one upper subnet shown in fig. 1 includes 5 subnets, wherein the 5 subnets included in the upper subnet are sn1, sn2, sn3, sn4, and sn5, where the starting endpoint of the first request received by the upper subnet controller is node a and the terminating endpoint thereof is node M. The method comprises the following steps:
step 301, calculating the shortest route across the sub-networks according to the first request;
after receiving a first request with a starting end point being a node a and a terminating end point being a node M, the upper-level subnet controller acquires a topology connection across lower-level subnets in a database, stores the acquired topology connection and uses the topology connection as an edge for calculating an end-to-end route, and the acquired network topology connection is a network structure as shown in fig. 1. And determining that the subordinate subnet to which the node A belongs is sn1 according to the obtained topological connection, namely sn1 is an initial subnet, and the subordinate subnet to which the termination endpoint M belongs is sn4, namely sn4 is a termination subnet. At this time, assuming each lower subnet as one node, the shortest route from sn1 to sn4 is calculated according to the shortest route policy with the topology across subnets as edges. As shown in FIG. 4, the shortest route across the sub-networks from sn1 to sn4 is a path B-G, N-J shown by a thick line between sn1-sn2-sn4 in the figure, the route between B-G is a link2 with the cost of 100, and the route between N-J is a link6 with the cost of 100. The routing cost of the shortest route across the subnets is the lowest relative to the routing cost of other routes from sn1 to sn4, where the routing cost of each route is derived from the cost of the path between the subordinate subnets through which the route passes, and the weights of the edges through which the route passes are summed, where the summed weight may be the corresponding routing cost of each link.
Step 302, determining an effective subnet according to the shortest route;
here, the shortest route determined in step 301 is a path B-G, N-J, the upper subnet controller reads the shortest route across subnets, and it can be seen that the lower subnets through which the shortest route across subnets passes include: sn1, sn2, sn4, the upper subnet controller sets sn1, sn2, sn4 as valid subnets, and sets sn3, sn5 as invalid subnets, as shown in fig. 5, the invalid subnets are deleted from the saved network topology connection to the saved valid subnets.
Step 303, determining boundary nodes of the effective sub-network;
specifically, the superordinate subnet controller traverses the topology across the active subnets, as shown in fig. 6, the topology across subnets between the active subnets sn1, sn2, sn4 includes: link2, link3, link6 and link7, wherein link represents the link identifier of topology i. The A and M end points of the topologies are respectively the starting point and the end point of the end-to-end route to be calculated, and meanwhile, the boundary points of the routes among the sn1, the sn2 and the sn4 comprise B, C, G, H, N, I, J, K. That is, the border nodes of sn1 include: a (starting endpoint), B, C; the border nodes of sn2 include: g, H, N, I; the border nodes of sn3 include: j, K, M (termination end points).
Step 304, calculating an abstract topology among the boundary nodes of the effective subnet;
here, at this time, the upper subnet controller issues the second request to sn1, sn2, sn4, and requests sn1, sn2, and sn4 to calculate the respective abstract topologies. As shown in fig. 7, the abstract topology of the sn1 is the topology between a, B and C; the abstract topology of the sn2 is the topology among G, H, N and I, and the abstract topology of the sn4 is the topology among J, K and M. After the subnet controllers of sn1, sn2 and sn4 respectively calculate their own abstract topologies according to the shortest path policy, report the calculated topology information to the upper subnet controller of the upper subnet, wherein the topology information is the topology information of the abstract topology. The abstract topology carries a weight, and the weight is a routing cost corresponding to a link between nodes. The shortest path policy is a shortest path algorithm, which is the prior art and is not described herein again.
Step 305, calculating a network element level route;
the upper-level subnet controller combines the subnet-crossing routes between the effective subnets of the shortest subnet-crossing routes calculated in step 301 and the topology information calculated in step 304 to generate a networking graph of the network element-level routes, wherein the effective subnets are regarded as full-crossing objects to determine the network element-level routes, and the boundary nodes of the sn1 as the full-crossing objects are a, B and C; the boundary node of the sn2 as a full cross object is G, H, N, I; the boundary nodes of sn4 as a full-crossover object are J, K, M. The determined network element level route is as shown in fig. 8, where a bold line is an effective abstract route determined according to the shortest sub-network-crossing route, and nodes passed by the effective abstract route sequentially are: A. b, G, I, K, M are provided.
Step 306, sending a second request, calculating end-to-end routing information from the starting endpoint to the terminating endpoint.
Here, each active subnet is treated as a full crossover object in step 305. At this time, the shortest route in the sub-network inside each effective sub-network is calculated according to the shortest route at the network element level, taking Sn2 as an example, the shortest route from node G to node I exists at the boundary node G of Sn2 at the network element level, and in Sn2, a plurality of different routes exist from node G to node I, and the optimal route from node G to node I is calculated according to the shortest route strategy. Similarly, the optimal routes in the subnets sn1 and sn4 are calculated, and the calculated optimal routes in each active subnet replace the abstract topology of the active abstract route, as shown in fig. 9, so as to obtain a complete piece of end-to-end route information from the starting endpoint a to the terminating endpoint M.
It should be noted that, in the embodiment of the present invention, the "path" and the "route" have the same meaning, and the "cross-subnet route" and the "inter-subnet route" have the same meaning. If the "upper subnet" is not described, both the "subnet" and the "lower subnet" are referred to as "lower subnet".
Fig. 9 illustrates an example of service provisioning of a bearer network, and implements a cross-subnet end-to-end route calculation method.
Step 901, receiving a first request;
the upper subnet network controller receives a first request, where the first request carries information of a start point and an end point of a working interval for creating a service, which are A, M and a start point and an end point of a protection interval, respectively, and the information is input by a user. Here, the start point and the end point of the working interval and the guard interval coincide with each other.
Step 902, calculating an end-to-end route as a working route;
here, the method for calculating the work route is consistent with steps 201 to 203, specifically:
9021, calculating the shortest route across subnets by the superior subnet controller;
the upper subnet controller regards the lower subnet managed by itself as a full crossover object, and assumes that the routing cost in the subnet is zero, that is, the upper subnet controller regards the lower subnet managed by itself as a node for route calculation. The upper subnet acquires the topology connection across the lower subnet from its own database, and uses the acquired topology connection across the lower subnet as the edge of the route calculation, and forms a networking map in the memory, as shown in fig. 1, and calculates the shortest route across the subnets, and the specific calculation method is the same as step 301.
9022, the upper subnet controller determines an effective lower subnet;
and the superior subnet controller sets the passed subordinate subnet as the effective subnet according to the calculated shortest routing across the subnets. Other sub-subnets in the networking map that do not pass through the shortest route across subnets are not valid subnets, are set as invalid subnets, and delete the invalid subnets, in step 302, so that the invalid subnets are not calculated in the network element level shortest route calculation of step 305. Meanwhile, the topology among the effective subnetworks is regarded as effective topology resources, and other topology resources are regarded as ineffective topology resources. The network element level shortest route calculation at step 305 will not participate in the calculation.
Step 9023, the superior subnet controller determines the boundary node of the effective subnet;
the upper subnet controller regards the starting subnet and the terminating subnet where the a and M end points of the effective topology connection of the effective subnet are located as the boundary nodes of the lower subnets, and at this time, all the lower subnets are regarded as nodes by the upper subnet.
In step 9024, the upper-level subnet controller requests the lower-level subnet controller to calculate the abstract topology between its boundary nodes.
And the upper-level subnet controller transmits the boundary point of each subnet to the subnet controllers of all the lower-level effective subnets. The abstract topology between the boundary nodes calculated by the subordinate subnet controller is specifically: and after receiving the boundary nodes, each effective lower-level sub-network controller parallelly calculates the communicable capacity among the boundary nodes of each sub-network, and the communicable capacity among the boundary nodes is regarded as abstract topological connection. These "abstract topologies" can be derived by solving for a minimum spanning tree starting from the border nodes. In addition, the abstract topologies have topological weight values, express the communication cost between the boundary nodes, and can be used as the basis for network element level routing calculation. The subordinate subnet controller returns the abstract topology calculated by itself to the superior subnet controller.
9025, the upper-level subnet controller calculates the shortest route at the network element level
And the superior subnet controller takes the abstract topology calculated by each subnet and the effective topology of the effective cross-subnet in the database as the most edges, takes the A and M network elements of the edges as nodes to form a networking graph, and calculates the shortest route at the network element level again.
9026, the superordinate subnet controller calculates the concrete routing information of the abstract topology
And the superior subnet controller respectively transmits the abstract topology in the calculated shortest path to each subordinate subnet, and calculates the concrete routing information of the abstract topology. The lower subnet calculates the shortest route of points A and Z of the abstract topology by using a shortest path algorithm, and returns the settlement result to the upper subnet. The superior subnet controller forms a complete cross-subnet route, specifically: and the superior subnet controller replaces the corresponding abstract topology in the 'network element level shortest path route' with the routing information of the abstract topology returned by each subordinate subnet. A complete route from a to Z is formed.
At this time, the calculated end-to-end route is set as the working route.
Step 903, calculating a protection route;
firstly, the weight of the topological connection of the network element through which the working route passes is increased. A protection route is calculated in the same manner as in step 902. Here, determining the degree of separation of the calculated protection route from the working route according to the specific route information of the protection route and the working route includes: the routes are completely the same, the routes are completely separated, and the routes are partially separated.
The route is completely separated into nodes which are completely different from the nodes passed by the protection route except for an initial end point and a termination end point; the route is completely the same as the node passed by the working route and the protection route; the routing part is separated into nodes which are passed by the working route and the protection route, wherein one part of the nodes is the same as the other part of the nodes, and the other part of the nodes is different from the other part of the nodes.
Here, the shortest path algorithm may select the edge with the smallest weight as possible so as to minimize the sum of the weights of the edges, and increase the weight, so that the protection route and the working route do not pass through the same node as much as possible, thereby realizing separation of the protection route and the working route.
Here, it should be noted that the routing information includes nodes through which the route passes and paths between the nodes.
The error report can be triggered when the separation relation between the working route and the protection route is not consistent with the separation degree between the working route and the protection route input by a user or not by checking whether the separation relation between the working route and the protection route meets the separation degree between the working route and the protection route input by the user.
In practical application, the calculated working route and protection route can be displayed to the user, and the user selects whether to continue configuring the service.
When an instruction that the user is satisfied with the calculation result is received, performing operation 904;
if the user is not satisfied with the calculation result, the required route calculation result is obtained by resetting the route constraint and recalculating.
And 904, generating configuration data to enable the service to be created.
The superior network controller generates configuration data of the network element equipment of each node of the service by using a routing calculation result and relevant data read from a database of the superior network controller network or the network element equipment of each node; the configuration data of the service is sent to the network element equipment of each node; the network element equipment of each node validates the service configuration data, thereby enabling the service to be created by the user.
The method for determining the end-to-end route provided by the embodiment of the invention can improve the network scale which can be managed by a network control system in large-scale bearing network management, reduce the time of route calculation and improve the precision of route calculation.
In order to implement the foregoing method, an embodiment of the present invention further provides an apparatus for determining an end-to-end route, as shown in fig. 10, where the apparatus includes: a receiving module 1001, an obtaining module 1002 and a selecting module 1003; wherein,
a receiving module 1001, configured to determine an effective cross-subnet route according to a first request when the first request is received;
specifically, a first request carrying a starting endpoint and a terminating endpoint is received; determining the subordinate subnet to which the starting endpoint belongs as a starting subnet, determining the subordinate subnet to which the ending endpoint belongs as an ending subnet, calculating the shortest cross-subnet route between the starting subnet and the ending subnet by adopting a shortest route strategy, and determining the shortest cross-subnet route as the effective cross-subnet route.
An obtaining module 1002, configured to send a second request to the effective subnet through which the effective cross-subnet route passes, and obtain topology information of the effective subnet;
specifically, the obtaining module receives topology information reported by the effective subnet after sending the second request to the effective subnet, where the topology information includes: the shortest route of the effective sub-network and the edge node corresponding to the shortest route.
A selecting module 1003, configured to determine end-to-end routing information according to the effective cross-subnet route and the topology information, and select a route represented by the end-to-end routing information as an end-to-end route.
Specifically, the end-to-end routing information is generated according to the starting endpoint, the terminating endpoint, the shortest cross-subnet route, the shortest effective subnet route, and the edge node corresponding to the shortest route, and the route represented by the end-to-end routing information is selected as the end-to-end route.
As shown in fig. 11, the apparatus further includes: a setup module 1004;
a setting module 1004, configured to set the lower subnet passed by the valid inter-subnet route as a valid subnet, and set the lower subnet not passed by the valid inter-subnet route as an invalid subnet.
As shown in fig. 11, the apparatus further includes: an abstract routing module 1005; an abstract routing module 1005, configured to obtain boundary points of the effective subnet; calculating an abstract topology of the effective cross-subnet route according to the boundary points; obtaining an effective abstract route according to the effective cross-subnet route and the abstract topology; wherein, the abstract topology is concretely as follows: and taking the effective subnet as the route calculated by the full-crossover object.
As shown in fig. 11, the apparatus further includes: a protection module 1006, configured to select at least two end-to-end routes, set an end-to-end route of the at least two end-to-end routes as a working route, and set the end-to-end route other than the working route as a protection route.
In practical applications, the method, the device and the system provided by the embodiment of the invention are not only suitable for browsing the page of the webpage, but also suitable for browsing various applications with the picture display function.
In practical applications, the apparatus provided in the embodiment of the present invention may be a single system, or may add logic units that perform different functions in an existing network element device, such as a network controller.
If a logic unit is added to the network controller, the receiving module 1001, the obtaining module 1002, the selecting module 1003, the setting module 1004, the abstract routing module 1005 and the protecting module 1006 may be implemented by a Central Processing Unit (CPU), a Digital Signal Processor (DSP), or a programmable gate array (FPGA) located in the mobile phone.
The above description is only exemplary of the present invention and should not be taken as limiting the scope of the present invention, and any modifications, equivalents, improvements, etc. that are within the spirit and principle of the present invention should be included in the present invention.