CN113507413B - Route optimization method and device and computing equipment - Google Patents

Abstract

The present application discloses a route optimization method, device and computing device, and relates to the technical field of communications. The method specifically includes, after the computing device obtains the transmission durations corresponding to the N candidate link costs of the M links, and, based on a heuristic algorithm, obtains the shortest transmission duration among the transmission durations corresponding to the N candidate link costs. Further, the computing device takes the candidate link overhead corresponding to the shortest transmission duration as the link overhead of the M links. The link overhead of at least one link included in any two candidate link overheads among the N kinds of candidate link overheads is different, and both N and M are integers greater than or equal to 2.

Description

A route optimization method, device and computing device

technical field

The present application relates to the field of communication technologies, and in particular, to a route optimization method, apparatus, and computing device.

Background technique

Currently, in an operator's network architecture, an Internet Protocol (Internet Protocol, IP) bearer network carries a large number of operators' services (eg, private line services, content distribution network services, etc.). With the continuous upgrading of network architecture and service requirements, there are more and more communication lines between networks, the traffic of communication transmission is increasing, the network architecture is becoming more and more complex, and the IP bearer network needs to carry more and more services. The bearer network presents higher requirements and challenges. In order to ensure the high efficiency of the network, routing optimization for the IP layer is very important. In the IP layer, the routing parameter for datagram forwarding is mainly link cost (metric), and the link cost is used to indicate the best path for the router to forward the datagram to the destination. Since the router selects the route according to the design of the link cost, and selects the path with the smallest path cost, the path cost includes multiple link costs. Therefore, the design of the link overhead should be in line with the requirements of the existing network, so that the resources of the existing network can be fully utilized on the premise of ensuring the service requirements.

Currently, the link overhead is usually designed by the operation and maintenance personnel based on experience. In the scenario where the router transmits datagrams according to the manually designed link overhead, the utilization rate of network resources is low, and the transmission time of the datagrams is long. Therefore, how to design the link overhead, improve the utilization rate of network resources, and reduce the transmission duration of the datagram is an urgent problem to be solved.

SUMMARY OF THE INVENTION

In the route optimization method, device and computing device provided by the present application, the designed link overhead can improve the utilization rate of network resources and reduce the transmission time of datagrams.

In order to achieve the above object, the application adopts the following technical solutions:

In a first aspect, the present application provides a route optimization method, which is performed by a computing device. The method includes: a computing device obtains transmission durations corresponding to N kinds of candidate link overheads of M links, and further obtains the shortest transmission duration among the transmission durations corresponding to N kinds of candidate link overheads based on a heuristic algorithm, and assigns the shortest transmission duration to The corresponding candidate link costs are taken as link costs of the M links. Wherein, the candidate link costs of at least one link included in any two kinds of candidate link costs in the N kinds of candidate link costs are different, and both N and M are integers greater than or equal to 2.

In this way, based on the heuristic algorithm, the computing device selects the candidate link cost corresponding to the shortest transmission duration from the N kinds of candidate link costs preconfigured for the M links, and uses the candidate link cost as the cost of the M links. link cost. There is no need for operation and maintenance personnel to manually design the link overhead based on experience, which realizes the intelligentization of the link overhead design process, and ensures that the designed link overhead is the link overhead with the shortest average transmission time in the entire network, which effectively improves the utilization of network resources. utilization, and reduces the transmission time of datagrams.

In a second aspect, the present application provides a route optimization device, which includes: a communication unit and a processing unit.

The above communication unit is configured to obtain the transmission duration corresponding to N kinds of candidate link overheads of the M links, and the candidate link overhead of at least one link included in any two kinds of candidate link overheads in the N kinds of candidate link overheads Differently, both N and M are integers greater than or equal to 2. The above processing unit is configured to obtain, based on a heuristic algorithm, the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link overheads. The above processing unit is further configured to use the candidate link overhead corresponding to the shortest transmission duration as the link overhead of the M links.

In a possible design, the N kinds of candidate link overheads include the initial link overhead and the update link overhead, and the transmission duration corresponding to the N kinds of candidate link overheads includes the initial transmission duration and the update transmission duration.

In one possible design, the heuristic algorithm includes particle swarm optimization.

In a possible design, the processing unit is specifically configured to compare the first transmission duration with the second transmission duration; if the first transmission duration is less than the second transmission duration, determine the first transmission duration as the transmission duration of the first link group and the transmission duration of the link group set; compare the third transmission duration with the fourth transmission duration; if the third transmission duration is less than the fourth transmission duration, determine the third transmission duration as the transmission duration of the second link group; compare the third transmission duration The transmission duration and the first transmission duration; if the third transmission duration is smaller than the first transmission duration, the third transmission duration is determined as the transmission duration of the link group set. Among them, the N types of candidate link overheads include the first type of candidate link overhead, the second type of candidate link overhead, the third type of candidate link overhead, and the fourth type of candidate link overhead. The first transmission duration of a link group is associated, the second candidate link overhead is associated with the second transmission duration of the first link group, and the third candidate link overhead is associated with the third transmission duration of the second link group , the fourth candidate link overhead is associated with the fourth transmission duration of the second link group; the link group set includes the first link group and the second link group, the first link group includes M links, and the first link group includes M links. A two-link group contains M links.

In a possible design, the communication unit is further configured to obtain the link information of the M links, the link information of each link, before obtaining the transmission durations corresponding to the multiple candidate link costs of the M links. Including the initial link overhead, and at least one of the longitude and latitude of the sender, the route type of the sender, the longitude and latitude of the receiver, the route type of the receiver, the link transmission duration and the link bandwidth; The link information of the links determines the link overhead value range, and the various candidate link costs of the M links belong to the link overhead value range.

In a possible design, the processing unit is specifically configured to classify the M links based on the clustering algorithm and the link information of the M links, to obtain S-type links, and each type of link in the S-type links includes: At least one link, S is an integer greater than or equal to 2; the range of link overhead of each type of link is determined according to the maximum link overhead and minimum link overhead of each type of link, and any link among M links The candidate link cost of the road belongs to a type of link cost value range in the S-type link cost value range.

In a third aspect, the present application provides a computing device including a memory and a processor. The memory and the processor are coupled. The memory is used to store computer program code comprising computer instructions. When the processor executes the computer instructions, the computing device executes the routing optimization method described in the first aspect and any possible design manners thereof.

In a fourth aspect, the present application provides a computer-readable storage medium, where instructions are stored in the computer-readable storage medium, when the computer-readable storage medium is run on a computer, the device is made to perform the first aspect and its The route optimization method described in any possible design manner.

In a fifth aspect, the present application provides a computer program product, the computer program product comprising computer instructions, when the computer instructions are run on a computer, the computer is made to execute the first aspect and any possible design methods thereof The described route optimization method.

For specific descriptions of the second to fifth aspects and their various implementations in this application, reference may be made to the detailed descriptions of the first aspect and their various implementations; and, for the second to fifth aspects and their various implementations For the beneficial effect of the method, reference may be made to the analysis of the beneficial effect in the first aspect and its various implementation manners, which will not be repeated here.

These and other aspects of the present application will be more clearly understood from the following description.

Description of drawings

In order to illustrate the technical solutions of the embodiments of the present application more clearly, the following briefly introduces the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the drawings in the following description are only some of the drawings in the present application. In the embodiments, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without any creative effort.

1 is a schematic structural diagram of an IP bearer network according to an embodiment of the present application;

2 is a schematic flowchart of a route optimization method provided by an embodiment of the present application;

FIG. 3 is a schematic flowchart of applying a particle swarm algorithm provided by an embodiment of the present application to an embodiment of the present application;

FIG. 4 is a schematic structural diagram of a computing device according to an embodiment of the present application;

FIG. 5 is a schematic structural diagram of a route optimization apparatus provided by an embodiment of the present application.

Detailed ways

The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application. Obviously, the described embodiments are only a part of the embodiments of the present application, but not all of the embodiments. Based on the embodiments in the present application, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present application.

In the embodiments of the present application, in order to clearly describe the technical solutions of the embodiments of the present application, words such as "first" and "second" are used to distinguish the same or similar items with basically the same functions and functions. Those skilled in the art can understand that the words "first", "second" and the like do not limit the quantity and execution order, and the words "first", "second" and the like are not necessarily different. The technical features described in the "first" and second" have no sequence or order of magnitude.

In the embodiments of the present application, words such as "exemplary" or "for example" are used to represent examples, illustrations or illustrations. Any embodiments or designs described in the embodiments of the present application as "exemplary" or "such as" should not be construed as preferred or advantageous over other embodiments or designs. Rather, the use of words such as "exemplary" or "such as" is intended to present the related concepts in a specific manner to facilitate understanding.

In the description of this application, unless otherwise stated, "/" indicates that the object associated with it is an "or" relationship, for example, A/B can indicate A or B; "and/or" in this application is only It is an association relationship that describes an associated object, which means that there can be three kinds of relationships, for example, A and/or B, which can be expressed as: A alone exists, A and B exist at the same time, and B exists alone, among which A, B Can be singular or plural. Also, in the description of the present application, unless stated otherwise, "plurality" means two or more than two. "At least one item(s) below" or similar expressions thereof refer to any combination of these items, including any combination of single item(s) or plural items(s). For example, at least one (a) of a, b, or c can represent: a, b, c, a-b, a-c, b-c, or a-b-c, where a, b, c may be single or multiple .

In the embodiments of the present application, at least one may also be described as one or more, and the multiple may be two, three, four or more, which is not limited in this application.

The topology of the Internet Protocol (IP) bearer network can be a three-layer network topology or a two-layer network topology. The three-layer network topology can be divided into the core layer, the aggregation layer and the access layer. It is the core layer (also known as the backbone spine layer) and the access layer (also known as the leaf layer).

The core layer is the high-speed switching backbone layer of the IP bearer network, and is used to connect the IP bearer network with devices outside the IP bearer network (eg, external operator equipment). The core layer may include routers. The core layer has at least one of the following characteristics: reliability, high efficiency, redundancy, fault tolerance, manageability, adaptability, and low latency. The routing connection at the core layer plays a very critical role in the IP bearer network. Generally, the reliability of the IP bearer network can be achieved through redundant connections of multiple devices.

The convergence layer is an "intermediary" between the access layer and the core layer, and is used to aggregate data before data sent by a workstation (such as a terminal device or server) enters the core layer, so as to reduce the load of the core layer. The aggregation layer may include routers.

The access layer is connected to workstations and is used to provide workstation access to the local network segment. The access layer may include routers.

Exemplarily, FIG. 1 is a schematic structural diagram of an IP bearer network to which an embodiment of the present application is applied. The IP bearer network is composed of access devices at the access layer, aggregation devices at the aggregation layer, and core devices at the core layer. The access device connects the workstation, and the workstation includes the server and the terminal device. As shown in FIG. 1 , the IP bearer network 100 includes a core layer 110 , a convergence layer 120 and an access layer 130 . The core layer 110 includes a router 111 and a router 112 . The aggregation layer 120 includes a router 121 , a router 122 , a router 123 and a router 124 . The access layer 130 includes a router 131 , a router 132 , a router 133 and a router 134 .

The router 111 and the router 112 are both connected to the Internet (Internet). Router 121 , router 122 , router 123 , and router 124 are all connected to router 111 . Router 121 , router 122 , router 123 , and router 124 are all connected to router 112 . The router 131 is connected to the router 121 and the router 122, respectively. The router 132 is connected to the router 121 and the router 122, respectively. The router 133 is connected to the router 123 and the router 124, respectively. The router 134 is connected to the router 123 and the router 124, respectively. The workstation 141 and the workstation 142 are connected to the router 131, respectively. Workstation 143 and workstation 144 are connected to router 132, respectively. Workstation 145 and workstation 146 are connected to router 133, respectively. Workstation 147 and workstation 148 are connected to router 134, respectively. The workstation can be a server or a terminal device, which is not limited.

FIG. 1 is just a schematic diagram, and the IP bearer network may also include other devices, such as a device management server. These servers are used to manage all routers to ensure they are working properly and are not shown in Figure 1. The embodiments of the present application do not limit the number of routers and workstations included in the IP bearer network. In addition, the connection mode between the router and the workstation shown in FIG. 1 is only a schematic illustration. In practical applications, the router and the workstation may also be connected in other ways, which are not limited in this application.

Each device in the IP bearer network can either send data as a sender or receive data as a receiver. The physical path through which the sender device sends the datagram to the receiver device includes multiple links. A link is a physical line from one device to another without any other devices in between. Generally, devices in the IP bearer network select a route to transmit datagrams according to the link overhead of the link. The link cost is designed by the operation and maintenance personnel based on experience. The manually designed link cost cannot guarantee the accuracy of the route optimization effect, resulting in a waste of network resources.

In order to solve the above problems, an embodiment of the present application provides a route optimization method. The computing device obtains the link overhead design scheme with the shortest average transmission duration of the entire network according to the obtained link information of M links and combined with a heuristic algorithm. It ensures the accuracy of the IP layer routing optimization effect. Compared with the manually designed link overhead scheme, it can intelligently obtain the link overhead design scheme with the shortest average transmission time of the entire network, reduce the overall service transmission time, and effectively improve the entire network. speed of business.

The route optimization method provided by the present application will be described in detail below with reference to the accompanying drawings.

As shown in FIG. 2 , a route optimization method provided by an embodiment of the present application includes the following steps.

S201. The computing device acquires link information of M links.

The link information of the link includes the initial link cost, and at least one of the longitude and latitude of the sender, the route type of the sender, the longitude and latitude of the receiver, the route type of the receiver, the link transmission duration and the link bandwidth.

The initial link cost of the link can be manually configured by the operation and maintenance personnel.

Optionally, the M pieces of link information may be network data of an area covered by one base station, or may be network data of an area covered by multiple base stations. The area may be a residential area, or may be a city or a country, and the scope of obtaining link information is not limited in this embodiment of the present application.

Routing types include access routers (AR), aggregation routers (border routers, BR), and core routers (core routers, CR). In this embodiment of the present application, the sending end device may be any one of the access router AR, the aggregation router BR, and the core router CR. The receiving end device may also be any one of the access router AR, the aggregation router BR and the core router CR. With reference to FIG. 1 , the sending end device can be any one of router 111 and router 112 in core layer 110 , or any one of router 121 , router 122 , router 123 and router 124 in aggregation layer 120 , or an access layer. Any one of router 131 , router 132 , router 133 and router 134 in 130 . The receiving end device can be router 111 and router 112 in the core layer 110, or any one of router 121, router 122, router 123, and router 124 in the aggregation layer, or router 131, router 132, and router 132 in the access layer 130. Either router 133 or router 134.

The transmission duration of a link refers to the time required for a datagram to travel from the link sender to the link receiver.

Link bandwidth refers to the amount of data that the link can transmit in unit time. The unit time is, for example, 1 second. Link bandwidth can refer to the amount of data transferred per second.

S202. The computing device determines a link overhead value range according to the link information of the M links.

In a possible example, the computing device classifies the M links based on a clustering algorithm and link information of the M links, to obtain S-type links. Each of the S-type links includes at least one link, and S is an integer greater than or equal to 2. The link cost range of each type of link is determined by the maximum link cost and the minimum link cost in each type of link.

As an example, it is assumed that M links are divided into two types, the link cost of the first link in the first type of link is the largest among the links in the first type of link, and the link cost of the first link is the largest. The link cost of the path is taken as the maximum link cost of the type 1 link. The link cost of the third link in the type 1 link is the link cost of the link in the type 1 link with the smallest link cost. Take the link cost of the third link as the minimum link cost of the first link, and determine the link cost of the first link according to the maximum link cost and the minimum link cost of the first link. scope.

For another example, the link cost of the second link in the type 2 link is the largest among the links in the type 2 link, and the link cost of the second link is regarded as the type 2 link. maximum link cost. The link cost of the fifth link in the type 2 link is the link cost of the link in the type 2 link with the smallest link cost, and the link cost of the fifth link is regarded as the minimum link cost of the type 2 link. The link overhead of the type 2 link is determined according to the maximum link overhead and the minimum link overhead of the type 2 link.

It is ensured that the candidate link cost of any one of the M links belongs to the link cost range of a class in the S-type link cost range. The various candidate link costs of the M links belong to the range of link costs.

Specifically, after acquiring the link information of the M links, the computing device first classifies the M links according to a clustering algorithm.

Optionally, the clustering algorithm includes any one of a k-means clustering algorithm, a mean-shift clustering algorithm, and a hierarchical clustering algorithm, and the k-means clustering algorithm is used as an example for description in this embodiment of the present application.

The k-means clustering algorithm is an indirect clustering method based on the similarity measure between samples, which belongs to the unsupervised learning method. This algorithm takes k as a parameter and divides n objects into k clusters, so that the similarity within the cluster is high and the similarity between clusters is low. Similarity is calculated based on the average of objects in a cluster (considered as the center of the cluster). Assuming that the sample data is to be divided into k categories, the algorithm flow is as follows:

(1) Appropriately select the initial center values of k classes from the sample data, generally randomly.

(2) In each iteration, for any sample data, the Euclidean distances from the sample data to k centers are obtained respectively, and the sample data are classified into the class of the center value with the shortest distance.

(3) Use the mean method to update the center value of k classes.

(4) Repeat steps (2) and (3) for the center values of the k classes. When the moving distance of the center values of the k classes satisfies a certain condition, the iteration ends and the classification is completed.

In the k-means algorithm, k is preset. In this embodiment of the present application, k may be 10, that is, the M links need to be divided into 10 categories. The initial center values of 10 classes are randomly selected. In the iterative process, the longitude and latitude of the sender, the route type of the sender, the longitude and latitude of the receiver, the route type of the receiver, and the link information of the M links are respectively used. Calculate the Euclidean distance from the initial link cost of the link in the link information of the M links to 10 initial center values, and classify the initial link cost of the link information of the M links to The class where the center with the shortest distance is located. Use the mean method to update the center value of 10 classes, until the initial link cost in each class has a high similarity, and the similarity between classes is low, and the iteration ends.

Specifically, in the embodiment of the present application, the M links are firstly divided into 10 categories according to the k-means algorithm, and each category includes the initial link costs of the links with similar degrees of similarity. Set the link cost value range for each type. Assuming that the minimum link cost of the i-th link is min and the maximum link cost is max, the range of the link cost of the i-th link is [min_i, max_i]. Wherein, the minimum link overhead min and the link overhead value range min_i satisfy the following formula (1).

min_i=min*0.7 Formula (1)

The maximum link overhead max and the link overhead max_i satisfy the following formula (2).

max_i=max*1.3 Formula (2)

For example, if the initial link cost set of the first type of link is (100, 200, 300, 400), then the link cost of this type of link ranges from [70, 520], the updated link cost is a positive integer, and It is divisible by 100, that is, the link cost in the candidate link cost is a positive integer and can be divisible by 100.

Repeat this step to define the link cost range of 10 types of links.

The computing device divides the M links into 10 categories based on the similarity based on the k-means algorithm, and each category is set with a link cost value range to ensure the candidate link cost of any one of the M links. Within the range of the link cost, it is beneficial to narrow the update range of the candidate link cost of the M links.

S203. The computing device acquires the transmission durations corresponding to the N candidate link costs of the M links.

Typically, a link can be configured with a link cost. The N kinds of candidate link costs represent the candidate link costs of N different configurations of M links. Each candidate link overhead includes the candidate link overhead for each of the M links. Wherein, the candidate link costs of at least one link included in any two candidate link costs of the N kinds of candidate link costs are different, and both N and M are integers greater than or equal to 2.

For example, assuming that N=3 and M=3, each of the three candidate link overheads includes link overheads of three links. The link cost of the three links included in the first candidate link cost is different from the link cost of at least one link in the link cost of the three links included in the second candidate link cost. For example, the link cost of the first link included in the first type of candidate link cost is different from the link cost of the first link included in the second type of candidate link cost. For another example, the link overhead of the first link included in the overhead of the first candidate link is different from the link overhead of the first link included in the overhead of the second candidate link; and, the first candidate link The link cost of the second link included in the overhead is different from the link cost of the second link included in the second candidate link cost. For another example, the link overhead of the second link included in the second candidate link overhead is different from the link overhead of the second link included in the third candidate link overhead; and, the first candidate link The link cost of the third link included in the overhead is different from the link cost of the third link included in the third candidate link cost.

In some embodiments, the N candidate link costs may include initial link costs and update link costs. The M links are configured with M initial link overheads, and at least one initial link overhead in the M initial link overheads is updated to obtain the updated link overhead.

Exemplarily, assuming M=3, the first type of candidate link overhead includes the initial link overheads of 3 links.

If the initial link costs of some links in the three links are updated, the second candidate link costs are obtained, and the second candidate link costs include the initial link costs and the update link costs. For example, update the initial link cost of the first link and the initial link cost of the second link among the three links, and the initial link cost of the third link is not updated, then the second candidate link The overhead includes the updated link overhead of the first link, the updated link overhead of the second link, and the initial link overhead of the third link.

If the initial link costs of the three links are updated, the third candidate link costs are obtained, and the third candidate link costs include the update link costs. For example, if the initial link cost of three links is updated, the third candidate link cost includes the updated link cost of the first link, the updated link cost of the second link, and the updated link cost of the third link. Update link cost.

Since the link can be configured with different link costs, the sending end device can use different link costs to select a route to transmit datagrams, so that the transmission durations of the datagrams are different. The transmission duration corresponding to the N kinds of candidate link overheads includes the initial transmission duration and the updated transmission duration.

When all links in a candidate link overhead are configured as initial link overheads, the transmission duration corresponding to the candidate link overhead may be the initial transmission duration. If the initial link overhead of at least one link in the candidate link overhead is updated, the transmission duration corresponding to the candidate link overhead may be the updated transmission duration. Understandably, the transmission duration corresponding to the candidate link overhead may refer to the duration used by the transmitting end device to send the datagram to the receiving end device based on the candidate link overhead. In this embodiment of the present application, the transmission duration may be an average transmission duration of the entire network for datagram transmission under a link overhead scheme. It can be understood that the average transmission duration of the entire network may refer to the average value of transmission durations after at least one datagram is transmitted through M links.

S204. The computing device obtains, based on a heuristic algorithm, the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link costs.

Optionally, the heuristic algorithm includes any one of particle swarm algorithm, simulated annealing algorithm, genetic algorithm, artificial neural network algorithm, and the like. In the embodiments of the present application, the particle swarm algorithm is used as an example for description.

Particle swarm optimization (PSO) algorithm, also known as particle swarm optimization (PSO) algorithm, is a global random search algorithm based on swarm intelligence, which is proposed by simulating the migration and flocking behavior of birds in the foraging process. Like other evolutionary algorithms, it is also based on the concepts of "population" and "evolution", and realizes the search for the optimal solution in complex space through cooperation and competition among individuals. The particle swarm algorithm simulates birds in a flock by designing a massless particle. The particle has two properties: position and speed. The position represents the direction of the particle's movement, and the speed represents the speed of the particle's movement.

The PSO algorithm is initialized as a group of random particles (random solutions), and then iteratively finds the optimal solution. In each iteration, the particle updates itself by tracking two extremums; the first extremum is the optimal solution found by the particle itself, which is called the individual extremum (pbest _i ); the other extremum is the entire The optimal solution that the population has found so far, this extremum is the global extremum (gbest _i ).

All particles in the particle swarm adjust their position and speed according to the current individual extremum found and the global extremum in the entire particle swarm, and the fitness value (FitNum _i ) of the particle can be obtained by substituting the position into the objective function. The size of the fitness value determines the quality of the position.

Suppose that in a D-dimensional target search space, there are N particles forming a community, and the i-th particle is represented as a D-dimensional vector, denoted as:

x _i =(x ₁ , x ₂ , x ₃ ,...,x _N ), i=1,2,3,...,N.

The velocity of the ith particle is also a D-dimensional vector, denoted as:

v _i =(v ₁ , v ₂ , v ₃ ,...,v _N ), i=1,2,3,...,N.

The optimal position searched by the ith particle so far is called the individual extremum, which is recorded as:

pbest _i =(p ₁ ,p ₂ ,p ₃ ,...,p _N ),i=1,2,3,...,N.

The optimal position searched by the entire particle swarm so far is called the global extremum, which is recorded as:

gbest _i =(g ₁ ,g ₂ ,g ₃ ,...,g _N ),i=1,2,3,...,N.

When finding this optimal value, the particle updates its velocity and position through the following formulas (3) and (4).

v _i =ω ^(t) ×v _i-1 +c ₁ ×rand( )×(pbest _i-1 -x _i-1 )+c ₂ ×rand( )×(gbest _i-1 -x _i-1 ) Formula (3)

x _i =x _i-1 +v _i Formula (4)

Among them, c ₁ and c ₂ are learning factors, which are also called acceleration constants. In general, c ₁ =c ₂ =2. rand( ) is a uniform random number in the range of [0,1], _xi is the position of the particle in this iteration, that is, the current position of the particle, and _xi-1 is the position of the previous iteration of the particle. v _i is the velocity of the particle in this iteration, that is, the current velocity of the particle, and v _i-1 is the velocity of the particle in the previous iteration. pbest _i-1 is the individual extreme value of the particle in the last iteration, and gbest _i-1 is the global extreme value of the particle swarm in the previous iteration.

ω ^(t) is the inertia factor, which has a great influence on the convergence of particle swarm optimization. ω ^(t) can be a random number in the [0,1] interval, or it can be a fixed value.

The process of particle swarm optimization is as follows:

1), initialize the particle swarm, including the swarm size N, the position x _i and velocity v _i of each particle;

2), calculate the fitness value FitNum _i of each particle;

3) For each particle, compare the fitness value FitNum _i of each particle with the individual extreme value pbest _i of each particle, if FitNum _i is less than pbest _i , replace pbest _{i with FitNum i ,} otherwise pbest _i is not updated , do this for each particle, updating each particle's pbest _i .

4) For each particle, compare the particle fitness value FitNum _i with the global extreme value gbest i of this particle. If FitNum _i is less than gbest _i , replace gbest _i with _{FitNum i} , otherwise gbest _i is not updated. Do this for each particle, updating the global gbest _i .

5), according to formula (3) (4) update the position x _i and velocity v _i of particle;

6), if the end condition is met (the fitness value is small enough or the maximum number of cycles is reached), exit, otherwise return to 2).

The iteration termination condition is generally selected according to the specific problem as reaching the maximum number of iterations and the optimal position searched by the particle swarm so far satisfies the preset minimum adaptation threshold. Referring to FIG. 3 , it is a schematic flowchart of applying the particle swarm algorithm to the embodiment of the present application.

Specifically, the particle swarm is initialized, including the number of particles, the number of dimensions, the value range of each dimension, and the position and speed of each particle.

In this embodiment of the present application, each particle represents an optimized link overhead design solution, including M links, that is, a link group. The particle swarm represents a set of several link groups, that is, a link group set.

The number of particles can be represented by N, and N can be set to 40, representing 40 different link cost design schemes, that is, 40 link groups. The number of iterations can be represented by t, and t can be set to 500. There is a one-to-one correspondence between the dimension and the number of links, and the number of links and the dimension are equal. The value range of the link cost corresponding to each link is the value range of each dimension.

For example, the first link of the M links may be the first dimension, and the second link may be the second dimension. After the classification of the k-means algorithm, the first link of the M links is classified into the first category, and the second link is classified into the third category, then the value range of the first dimension adopts the first The value range of the link cost of the class, and the value range of the second dimension adopts the value range of the link cost of the third class.

In the embodiment of the present application, the position of the particle represents the link cost design scheme of the link group at the gth iteration of the link group set, and the speed of the particle represents the change of the link cost of at least one link in the link group update process quantity. Set the speed coefficient c ₁ =c ₂ =0.5, the speed coefficient is mainly used to control the update speed of the particles. In the embodiment of the present application, the inertia factor ω satisfies the following formula (5).

ω ^(t) = (ω _ini -ω _end )(G _k -g)/G _k +ω _end Formula (5)

G _k is the maximum number of iterations, which is set to 500, g is the current number of iterations, and ω _ini is the initial inertia weight, which is set to 0.9. ω _end is the inertia weight when iterating to the maximum evolution algebra, which is set to 0.4.

In some embodiments, the computing device may calculate the network-wide average transmission duration of each link group, and use the calculated network-wide average transmission duration as the fitness value of the link group.

In other embodiments, the average transmission duration of the entire network under each link group scheme may be calculated by other devices, and then the calculation results may be transmitted by other devices to the computing device.

It can be understood that the link group set has not been updated after initialization, and the current average transmission duration of each link group in the entire network is the link group extremum of each link group. Compare the network-wide average transmission durations of multiple link groups in the link group set, determine the shortest network-wide average transmission duration among the network-wide average transmission durations of multiple link groups, and use the shortest network-wide average transmission duration as the link group set extremum. It should be understood that the extremum of the link group set is the global extremum, and the extremum of the link group is the individual extremum.

Further, each link group is updated, and the link cost of each link in the link group is updated within the value range corresponding to each dimension.

Optionally, if the computing power of the computing device or other devices is sufficient, the 40 link groups can be updated at the same time. The average transmission time of the entire network.

Optionally, if the computing power of the computing device or other devices is insufficient, the 40 types of link groups can be updated in sequence. The average transmission time of the entire network.

When the calculation of the network-wide average transmission duration after updating all link groups is completed, compare the updated network-wide average transmission duration of each link group with the link group extreme value of each link group. If the average transmission duration of the entire network is less than the extreme value of the link group, the updated average transmission duration of the entire network will be taken as the extreme value of the link group. If the average transmission duration of the entire network after the update is greater than or equal to the extreme value of the link group, the extreme value of the link group has not changed.

Further, the average transmission duration of the entire network after each link group update is compared with the link group set extremum. Then the average transmission duration of the entire network after the update of the link group is taken as the extreme value of the link group set. If the average transmission duration of the entire network after any link group is updated is still greater than or equal to the extremum of the link group set, the extremum of the link group set has not changed. The extreme value of the link group set refers to the shortest average transmission time of the entire network in the link group set at the gth iteration in the link group set iteration process.

For example, if the link group set includes the first link group, the computing device calculates the initial transmission duration of the first link group as the first transmission duration, and the initial link cost of the first link group is the first candidate link. overhead. The updated link overhead after the updated first candidate link overhead is the second candidate link overhead, and the updated transmission duration after the updated first transmission duration is the second transmission duration. If the first transmission duration is shorter than the second transmission duration, it means that the overhead of the first candidate link is better than the overhead of the second candidate link. The first transmission duration is taken as the transmission duration of the first link group and the link group set transmission duration, that is, the first transmission duration is the first link group extremum and the link group set extremum.

If the link group set includes the first link group and the second link group, the computing device calculates the initial transmission duration of the second link group as the third transmission duration, and the initial link cost of the second link group as the third candidate link cost. The updated link overhead after the third candidate link overhead is updated is the fourth candidate link overhead, and the updated transmission duration after the third transmission duration is updated is the fourth transmission duration. If the third transmission duration is less than the fourth transmission duration, it means that the overhead of the third candidate link is better than the overhead of the fourth candidate link. Then, the third transmission duration is taken as the transmission duration of the second link group, that is, the third transmission duration is the extreme value of the second link group.

Compare the first transmission duration with the third transmission duration, if the third transmission duration is less than the first transmission duration, it means that the third candidate link overhead is better than the first candidate link overhead, and the third candidate link overhead corresponds to the third transmission The duration is the shortest transmission duration of the link group set, that is, the extreme value of the link group set.

S205. The computing device uses the candidate link overhead corresponding to the shortest transmission duration as the link overhead of the M links.

It can be understood that the transmission duration of the candidate link overhead corresponding to the extreme value of the link group set is the shortest transmission duration. In the embodiment of the present application, the termination condition of the particle swarm optimization algorithm may be that after the update times of 40 link groups reaches the maximum number of iterations of 500, the candidate of the link group corresponding to the shortest transmission duration in the link group set at the 500th iteration The link overhead is taken as the link overhead of M links.

Optionally, in this embodiment of the present application, the termination condition of the particle swarm algorithm may also be that, in the 40 kinds of link group update processes, the extreme value of the link group set determined in a certain update, after continuing to update 10 times, the The link group set extremum is unchanged. Then, the candidate link cost of the link group corresponding to the extreme value of the link group set is used as the link cost of the M links.

In the embodiment of the present application, the computing device classifies the link information of the M links through a clustering algorithm, and sets the link cost value range according to the classification result, ensuring that the link costs of the M links have corresponding link costs Value range and update within the value range to speed up the convergence speed of particle swarm optimization. Through the particle swarm algorithm, a variety of link overhead design schemes are determined, and the average transmission time of the entire network under each scheme is calculated, and the link overhead of the links in each design scheme is continuously updated until the overall network average The link overhead design scheme with the shortest transmission duration. Compared with the prior art, the operation and maintenance personnel manually design the link overhead according to the relevant experience, which realizes the intelligent acquisition of the link overhead design scheme with the shortest average transmission time of the whole network, improves the accuracy of the link overhead design scheme, and reduces the cost of the link overhead design scheme. The link overhead scheme designed by the operation and maintenance personnel due to misjudgment is not a waste of resources caused by the scheme with the shortest average transmission time of the whole network. It can reduce the overall service transmission time and effectively improve the speed of the whole network service.

The solutions provided by the embodiments of the present application are described above mainly from the perspective of methods. In order to realize the above-mentioned functions, it includes corresponding hardware structures and/or software modules for executing each function. Those skilled in the art should easily realize that the present application can be implemented in hardware or a combination of hardware and computer software with the units and algorithm steps of each example described in conjunction with the embodiments disclosed herein. Whether a function is performed by hardware or computer software driving hardware depends on the specific application and design constraints of the technical solution. Skilled artisans may implement the described functionality using different methods for each particular application, but such implementations should not be considered beyond the scope of this application.

As shown in FIG. 4 , an embodiment of the present application provides a computing device 400 . The computing device may include at least one processor 401 , communication lines 402 , memory 403 and communication interface 404 .

Specifically, the processor 401 is configured to execute the computer-executed instructions stored in the memory 403, thereby implementing steps or actions of the computing device. In this embodiment of the present application, the processor 401 may be configured to determine multiple link overhead design schemes and calculate the transmission duration under each link overhead scheme.

The processor 401 may be a chip. For example, it can be a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), a system on chip (SoC), or a central processing unit. A central processor unit (CPU), a network processor (NP), a digital signal processor (DSP), or a micro controller unit (MCU), It can also be a programmable logic device (PLD) or other integrated chips.

The communication line 402 is used to transmit information between the above-mentioned processor 401 and the memory 403 . In this embodiment of the present application, the communication line 402 may be used to transmit multiple link overhead design schemes determined by the processor 401 and transmission durations corresponding to the multiple link overhead design schemes to the memory 403 .

The memory 403 is used for storing and executing computer execution instructions, and the execution is controlled by the processor 401 . In this embodiment of the present application, the memory 403 may be used to store various link overhead design solutions and corresponding transmission durations.

The memory 403 may exist independently and be connected to the processor through the communication line 402 . Memory 403 may be volatile memory or non-volatile memory, or may include both volatile and non-volatile memory. The non-volatile memory may be read-only memory (ROM), programmable read-only memory (PROM), erasable programmable read-only memory (EPROM), electrically erasable memory Except programmable read-only memory (electrically EPRO M, EEPROM) or flash memory. Volatile memory may be random access memory (RAM), which acts as an external cache. By way of example and not limitation, many forms of RAM are available, such as static random access memory (SRAM), dynamic random access memory (DRAM), synchron ous DRAM, SDRAM), double data rate synchronous dynamic random access memory (double data rate SDRAM, DDR SDRAM), enhanced synchronous dynamic random access memory (enhanced SD RAM, ESDRAM). It should be noted that the memory of the systems and devices described herein is intended to include, but not be limited to, these and any other suitable types of memory.

A communication interface 404 for communicating with other devices or a communication network. The communication network may be an Ethernet network, a radio access network (RAN), or a wireless local area network (wireless local area networks, WLAN). In this embodiment of the present application, the communication interface 404 may be used for the computing device 400 to communicate with other devices.

It should be pointed out that the structure shown in FIG. 4 does not constitute a limitation on the computing device. In addition to the components shown in FIG. 4 , the computing device may include more or less components than those shown in the figure, or a combination of certain components may be included. some components, or a different arrangement of components.

As shown in FIG. 5 , an embodiment of the present application provides a route optimization apparatus 50 . The apparatus may include a communication unit 51 and a processing unit 52 .

The communication unit 51 is configured to obtain the transmission duration corresponding to the N candidate link overheads of the M links, where the candidate link overheads of at least one link included in any two candidate link overheads in the N candidate link overheads are different, Both N and M are integers greater than or equal to 2.

The processing unit 52 is configured to obtain, based on a heuristic algorithm, the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link overheads. It is also used to use the candidate link overhead corresponding to the shortest transmission duration as the link overhead of the M links.

It should be understood that, in various embodiments of the present application, the size of the sequence numbers of the above-mentioned processes does not mean the sequence of execution, and the execution sequence of each process should be determined by its functions and internal logic, and should not be dealt with in the embodiments of the present application. implementation constitutes any limitation.

In actual implementation, the communication unit 51 and the processing unit 52 may be implemented by the processor 401 shown in FIG. 4 calling the program code in the memory 403 , which will not be repeated here.

Another embodiment of the present application further provides a computer-readable storage medium, where computer instructions are stored in the computer-readable storage medium, and when the computer instructions are executed on the computer, the computer is made to execute the method processes shown in the above method embodiments. of the various steps.

In another embodiment of the present application, a computer program product is also provided, the computer program product includes instructions, when the instructions are run on a computer, the computer is made to execute each step in the method flow shown in the above method embodiments.

Those of ordinary skill in the art can realize that the units and algorithm steps of each example described in conjunction with the embodiments disclosed herein can be implemented in electronic hardware, or a combination of computer software and electronic hardware. Whether these functions are performed in hardware or software depends on the specific application and design constraints of the technical solution. Skilled artisans may implement the described functionality using different methods for each particular application, but such implementations should not be considered beyond the scope of this application.

Those skilled in the art can clearly understand that, for the convenience and brevity of description, the specific working process of the above-described systems, devices and units may refer to the corresponding processes in the foregoing method embodiments, which will not be repeated here.

In the several embodiments provided in this application, it should be understood that the disclosed systems, devices and methods may be implemented in other manners. For example, the device embodiments described above are only illustrative. For example, the division of units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be combined or integrated. to another system, or some features can be ignored, or not implemented. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be through some interfaces, indirect coupling or communication connection of devices or units, and may be in electrical, mechanical or other forms.

Units described as separate components may or may not be physically separated, and components shown as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution in this embodiment.

In addition, each functional unit in each embodiment of the present application may be integrated into one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit.

The above are only specific embodiments of the present application, but the protection scope of the present application is not limited to this, and any changes or substitutions within the technical scope disclosed in the present application should be covered within the protection scope of the present application. . Therefore, the protection scope of the present application should be subject to the protection scope of the claims.

Claims (9)

1. A route optimization method, wherein the method is executed by a computing device, and the method comprises: Obtain transmission durations corresponding to N kinds of candidate link overheads of the M links. The candidate link overheads of at least one link included in any two candidate link overheads of the N kinds of candidate link overheads are different, and both N and M are different. is an integer greater than or equal to 2; Based on a heuristic algorithm, obtain the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link overheads; The candidate link overhead corresponding to the shortest transmission duration is used as the link overhead of the M links. 2 . The method according to claim 1 , wherein the N types of candidate link overheads include initial link overheads and update link overheads, and transmission durations corresponding to the N types of candidate link overheads include initial transmission durations. 3 . and update transfer duration. 3. The method of claim 2, wherein the heuristic algorithm comprises a particle swarm algorithm. 4 . The method according to claim 3 , wherein the N types of candidate link overheads comprise a first type of candidate link overhead, a second type of candidate link overhead, a third type of candidate link overhead and a fourth type of candidate link overhead candidate link overheads, the first candidate link overhead is associated with the first transmission duration of the first link group, the second candidate link overhead is associated with the second transmission duration of the first link group, and the third candidate link overhead is associated with the first transmission duration of the first link group. One candidate link overhead is associated with the third transmission duration of the second link group, and the fourth candidate link overhead is associated with the fourth transmission duration of the second link group; the link group set includes the first link a road group and the second link group, the first link group includes the M links, and the second link group includes the M links; The acquisition of the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link overheads based on the heuristic algorithm includes: comparing the first transmission duration with the second transmission duration; If the first transmission duration is less than the second transmission duration, determining the first transmission duration as the transmission duration of the first link group and the transmission duration of the link group set; comparing the third transmission duration with the fourth transmission duration; If the third transmission duration is less than the fourth transmission duration, determining the third transmission duration as the transmission duration of the second link group; comparing the third transmission duration with the first transmission duration; If the third transmission duration is less than the first transmission duration, the third transmission duration is determined as the transmission duration of the link group set. 5. The method according to any one of claims 1 to 4, wherein before the acquiring the transmission duration corresponding to the multiple candidate link overheads of the M links, the method further comprises: Acquire link information of the M links, where the link information of each of the links includes the initial link overhead, as well as the longitude and latitude of the sender, the route type of the sender, the longitude and latitude of the receiver, and the route type of the receiver , at least one of link transmission duration and link bandwidth; The link overhead value range is determined according to the link information of the M links, and the multiple candidate link costs of the M links belong to the link overhead value range. 6. The method according to claim 5, wherein the determining a link overhead value range according to the link information of the M links comprises: The M links are classified based on the clustering algorithm and the link information of the M links to obtain S-type links, each of which includes at least one link, and S is an integer greater than or equal to 2; The value range of the link cost of each type of link is determined according to the maximum link cost and the minimum link cost of each type of link, and the candidate link cost of any link in the M links belongs to S The value range of a class of link costs in the value range of class link costs. 7. A route optimization device, wherein the device comprises: A communication unit, configured to obtain transmission durations corresponding to N kinds of candidate link overheads of the M links, where the candidate link overheads of at least one link included in any two kinds of candidate link overheads in the N kinds of candidate link overheads are different , N and M are integers greater than or equal to 2; a processing unit, configured to obtain the shortest transmission duration among the transmission durations corresponding to the N kinds of candidate link overheads based on a heuristic algorithm; The processing unit is further configured to use the candidate link overhead corresponding to the shortest transmission duration as the link overhead of the M links. 8. A computing device comprising one or more processors and one or more memories; The one or more memories are coupled to the one or more processors, the one or more memories for storing computer program code, the computer program code comprising computer instructions, when the one or more processors When executing the computer instructions, the computing device executes the route optimization method of any one of claims 1-6. 9. A computer storage medium, characterized in that it comprises computer instructions that, when the computer instructions are executed on a computing device, cause the computing device to execute the routing optimization method according to any one of claims 1-6 .

Images