WO2018176946A1

WO2018176946A1 - Route selection method and apparatus

Info

Publication number: WO2018176946A1
Application number: PCT/CN2017/119050
Authority: WO
Inventors: 林栋�; 邓榤生; 韩泽宇
Original assignee: 华为技术有限公司
Priority date: 2017-03-29
Filing date: 2017-12-27
Publication date: 2018-10-04
Also published as: CN108668334A; CN108668334B

Abstract

A route selection method and apparatus, which select a target route by means of combining a fault resistance capability of the route, thereby improving communication reliability. In the embodiments of the present application, an NMC value of a middle node is obtained according to the number of polygons constructed by the middle node, and the middle node serves as a vertex of the polygon constructed by the middle node, that is to say, an NMC value of one middle node can reflect the number of polygons, the construction of which the middle node participates in. Since the polygon is closed, and the middle node is the vertex of the polygon, the number of polygons constructed by the middle node may reflect a fault resistance capability of the middle node after a chain of the middle node fails, such that a target route selected based on the fault resistance capability of the middle node in the embodiments of the present application improves the communication reliability.

Description

Routing method and device

The present application claims the priority of the Chinese Patent Application, which is filed on March 29, 2017, filed on Jan. 29,,,,,,,,,,,,,,,,,,,,,, .

Technical field

The present application relates to the field of communications, and in particular, to a routing method and apparatus.

Background technique

Wireless Mesh network, also known as wireless mesh network or wireless mesh network, combines the advantages of Wireless Local Area Network (WLAN) technology and AdHoc network. It is a network with large capacity, high speed and wide coverage. Wireless Mesh networks are low-power multi-hop multihop systems that process messages by passing packets from one node to another until the packet reaches its destination. The nodes of each wireless Mesh network can serve as access terminals, and can also have routing and information forwarding functions, and have extremely high networking degrees of freedom.

A wireless mesh network provides multiple redundant routes from a source node to a destination node. If a node on a route stops working due to hardware failure or interference, the mesh automatically changes the routing of the packets and passes them through an alternate route. In the prior art, the route from the source node to the target node can be selected through Open Shortest Path First (OSPF). For example, the source node has five routes to the target node, and the route with the shortest path is selected from the five routes as the target route, and the source node and the target node communicate through the target route.

In the above solution, only the length of the route is considered, but in the actual communication process, the nodes in the route often fail. It can be seen that the shortest path as the only factor for selecting the target route does not improve the reliability of the communication.

Summary of the invention

The embodiment of the present application provides a routing method and device, which are used to select a target route in combination with the ability of a route to resist failure, thereby improving communication reliability.

In a first aspect, the embodiment of the present application provides a routing method, including acquiring at least two routes from a source node to a target node, and acquiring a micro-structure count NMC score of an intermediate node in at least two routes; wherein, the intermediate node The NMC score is obtained according to the number of polygons constructed by the intermediate node; wherein the intermediate node is a vertex of the polygon constructed by the intermediate node; according to the NMC score of the intermediate node in at least two routes, from at least two A destination route is selected in the route.

In the embodiment of the present application, the NMC score of the intermediate node is obtained according to the number of polygons constructed by the intermediate node, and the intermediate node is a vertex of the polygon constructed by the intermediate node, that is, an NMC score of an intermediate node. The number of polygons that the intermediate node participates in constructing may be reflected. Since the polygon is closed and the intermediate node is a vertex of the polygon, the number of polygons constructed by the intermediate node may reflect that the link of the intermediate node is faulty. The fault repairing capability of the intermediate node, and the target route is selected from the source node to the target node according to the NMC score of the intermediate node in the at least two routes in the embodiment of the present application, that is, the implementation of the present application In the example, the target route is selected based on the fault repair capability of the intermediate node. Therefore, the solution provided by the embodiment of the present application can improve the capability of the target route to resist the fault, thereby improving the reliability of the communication.

Optionally, the first route and the second route are equivalent to the at least two routes; wherein the first route and the second route are any two routes of the at least two routes; the first route and the second route meet the following content Any one of the following: the hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route; the transmission delay of the first route is the same as the transmission delay included in the second route; the first route The sum of the weights of the included links is the same as the sum of the weights of the links included in the second route; the sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route; the first route The sum of the weight of the included link and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node. It can be seen from the above that the target route selected in the embodiment of the present application considers the route repair capability of each intermediate node on the route, and thus the reliability of the route can be improved. Further, for the two equal-cost routes, the advantages of the method in the present application can be further improved. In this embodiment, the fault repair capability of the route in the two equal-cost routes is determined to be higher.

Optionally, the NMC score of the intermediate node is obtained according to the number of M-type polygons constructed by the intermediate node; wherein, M is an integer greater than or equal to 1, and if M is greater than or equal to 2, any two of the M-type polygons Class polygons have different numbers of sides. In this way, the M-type polygon can be reasonably set according to the actual situation and the specific application scenario, so that the NMC score more accurately reflects the fault repair capability of the intermediate node.

Optionally, the NMC score of the intermediate node is: performing weighting calculation on the number of each type of polygon in the M-type polygon constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon; wherein The NMC score of the intermediate node is used to indicate: the fault repair capability of the intermediate node. Thus, the weights of each type of polygon in the M-type polygon can be set according to actual conditions, for example, the weight of each type of polygon is the same, both are 1; or the polygons with more edges may have a larger routing delay after repairing, Therefore, the polygons with more edges may have smaller weights, etc., so that the NMC score is balanced between the fault repair capability of the intermediate node and the delay of the repaired route.

Optionally, selecting a target route from the at least two routes according to the NMC score of the intermediate node in the at least two routes, including: determining, according to the NMC score of the intermediate node in the at least two routes, at least two The NMC score of the route in the route; wherein the NMC score of the route is used to indicate the fault repair capability of the route; according to the NMC score of the route in at least two routes, the route with the strongest fault repair capability indicated The route corresponding to the NMC score is determined as the target route.

Optionally, determining, according to the NMC score of the intermediate node in the at least two routes, the NMC score of the route in the at least two routes, including the following manner: repairing the fault indicated in the route in the at least two routes The NMC score of the weakest intermediate node is determined as the NMC score of the route; the intermediate node NMC score in the route of at least two routes is mathematically calculated, and the result of the mathematical calculation is determined as the NMC score of the route.

Optionally, the NMC scores of the intermediate nodes in the at least two routes are obtained, and the NMC scores reported by each of the at least two routes are obtained by using a flooding or periodic information exchange mechanism. Optionally, the NMC score of the intermediate node may be obtained by receiving the NMC score reported by each of the at least two routes, or calculating the route of each of the at least two routes by directly calculating. The NMC score for each intermediate node in .

Optionally, obtaining at least two routes from the source node to the target node, and acquiring NMC scores of the intermediate nodes in the at least two routes, including: a broadcast routing request; wherein the routing request includes an identifier of the target node; and receiving the target The route response corresponding to the route request returned by the node, where the route response includes: at least two routes from the source node to the target node, and an NMC score of the intermediate node in the at least two routes. Alternatively, to be compatible with the prior art, the scheme can be performed by a routing device disposed on the source node.

In a second aspect, the embodiment of the present application provides a routing method, including: performing, for an intermediate node of at least two routes from a source node to a target node, determining, according to network topology information of the intermediate node, a polygon constructed by the intermediate node. The number of the vertices of the polygon constructed by the intermediate node; determining the NMC score of the microstructure of the intermediate node according to the number of polygons constructed by the intermediate node; reporting the NMC score of the intermediate node; The NMC score of the intermediate node in the at least two routes is used to: select a target route from the at least two routes according to the NMC score of the intermediate node in the at least two routes. In the embodiment of the present application, the target route is selected based on the fault repair capability of the intermediate node. Therefore, the solution provided by the embodiment of the present application can improve the capability of the target route to resist the fault, thereby improving the reliability of the communication.

Optionally, determining the number of polygons constructed by the intermediate node according to the network topology information of the intermediate node, including: determining, according to network topology information of the intermediate node, the number of M types of polygons constructed by the intermediate node; wherein, M is greater than An integer equal to 1, and if M is greater than or equal to 2, the number of sides of any two types of polygons in the M-type polygon is different; determining the NMC score of the intermediate node according to the number of polygons constructed by the intermediate node, including: according to the middle The number of M-type polygons constructed by the node determines the NMC score of the intermediate node. In this way, the M-type polygon can be reasonably set according to the actual situation and the specific application scenario, so that the NMC score more accurately reflects the fault repair capability of the intermediate node.

Optionally, determining the NMC score of the intermediate node according to the number of M types of polygons constructed by the intermediate node includes: determining a weight corresponding to each type of polygon in the M type polygon; and according to weights corresponding to each type of polygon in the M type polygon, Weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node; determining the result of weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node as the NMC score of the intermediate node . Thus, the weights of each type of polygon in the M-type polygon can be set according to actual conditions, for example, the weight of each type of polygon is the same, both are 1; or the polygons with more edges may have a larger routing delay after repairing, Therefore, the polygons with more edges may have smaller weights, etc., so that the NMC score is balanced between the fault repair capability of the intermediate node and the delay of the repaired route.

Optionally, the reporting the NMC score of the intermediate node includes: receiving a routing request; wherein the routing request includes an identifier of the target node; and determining, according to the identifier of the routing request, the identifier of the intermediate node after determining that the routing request is received for the first time The NMC score is added to the routing record of the routing request, and the routing request with the identifier of the intermediate node and the NMC score is forwarded. Alternatively, to be compatible with the prior art, the scheme can be performed by a routing device disposed on the intermediate node.

In a third aspect, the embodiment of the present application provides a routing device, where the routing device includes a memory, a transceiver, and a processor, where: the memory is used to store program instructions; the processor is configured to execute and send and receive according to program instructions for executing memory storage. The device performs signal reception and signal transmission, and when the processor executes the program instruction stored in the memory, the routing device is configured to perform the method of any of the above first aspect or the first aspect.

In a fourth aspect, an embodiment of the present application provides a routing device, where the routing device includes a memory, a transceiver, and a processor, where: the memory is used to store program instructions; the processor is configured to execute, according to a program instruction for executing the memory, and control the sending and receiving. The device performs signal reception and signal transmission, and when the processor executes the program instruction stored in the memory, the routing device is configured to perform the method of any of the above second aspect or the second aspect.

In a fifth aspect, the embodiment of the present application provides a routing device, which is used to implement any one of the foregoing first aspect or the first aspect, and includes a corresponding functional module, which is used to implement the steps in the foregoing method.

In a sixth aspect, the embodiment of the present application provides a routing apparatus, which is used to implement the method of any one of the foregoing second aspect or the second aspect, and includes a corresponding functional module, which is used to implement the steps in the foregoing method.

In a seventh aspect, an embodiment of the present application provides a computer storage medium, where a computer storage medium stores program instructions, when executed on a computer, causing the computer to perform the first aspect or any possible implementation manner of the first aspect. method.

In an eighth aspect, an embodiment of the present application provides a computer storage medium, where a computer storage medium stores program instructions, and when executed on a computer, causes the computer to perform the second aspect or any possible implementation manner of the second aspect. method.

In a ninth aspect, the embodiment of the present application provides a computer program product comprising program instructions, when executed on a computer, causing the computer to perform the method in the first aspect or any possible implementation manner of the first aspect.

In a tenth aspect, the embodiment of the present application provides a computer program product comprising program instructions, when executed on a computer, causing the computer to perform the method in any of the possible implementations of the second aspect or the second aspect.

DRAWINGS

1 is a schematic structural diagram of a communication system to which an embodiment of the present application is applied;

1a is a schematic structural diagram of another communication system to which the embodiment of the present application is applied;

2 is a schematic flowchart of a routing method according to an embodiment of the present application;

2a is a schematic diagram of two phase transitions of path expansion in a route repair process according to an embodiment of the present application;

2b is a schematic structural diagram of a system of routing according to an embodiment of the present application;

2c is a schematic structural view of a triangle constructed by the intermediate node 122 of FIG. 2b;

2d is a schematic structural view of a quadrangle constructed by the intermediate node 122 of FIG. 2b;

2 e is a schematic flowchart of a method for enabling a first routing device to acquire an NMC score of each intermediate node according to an embodiment of the present application;

FIG. 3 is a schematic structural diagram of a routing apparatus according to an embodiment of the present disclosure;

FIG. 4 is a schematic structural diagram of a routing apparatus according to an embodiment of the present disclosure;

FIG. 5 is a schematic structural diagram of a routing apparatus according to an embodiment of the present disclosure;

FIG. 6 is a schematic structural diagram of a routing apparatus according to an embodiment of the present disclosure.

detailed description

The embodiments of the present application are applicable to wired or wireless networks, such as wireless Mesh networks that combine the advantages of WLAN and AdHoc networks. Wireless Mesh networks are low-power multi-level hopping systems that process messages by passing packets from one node to another until the packet reaches its destination. The nodes of each wireless Mesh network can serve as access terminals, and can also have routing and information forwarding functions, and have extremely high networking degrees of freedom. The source node, the target node, and the intermediate node in the embodiment of the present application are all nodes in the network to which the embodiment of the present application applies, and each of the source node, the target node, and the intermediate node has a routing and information forwarding function.

In the embodiment of the present application, two parties of data transmission are respectively referred to as a source node and a target node, and a node through which a route between the source node and the target node passes is referred to as an intermediate node. The solution in the embodiment of the present application provides a routing scheme between the source node and the target node, and the source node may send data to the target node by using the selected route, and accordingly, the target node may also send the route to the source node by using the selected route. data. It should be noted that the source node and the target node defined in the embodiment of the present application may also become intermediate nodes in other data transmission schemes, and the intermediate node may also become a source node or a target node in other data transmission schemes.

FIG. 1 is a schematic diagram showing a structure of a communication system to which the embodiment of the present application is applied. As shown in FIG. 1, the source node 101 and the target node 102 are connected by a route including an intermediate node 111, an intermediate node 112, and Intermediate node 113. The routing device provided in the embodiment of the present application may include two parts, which may be respectively referred to as a first routing device and a second routing device, and the first routing device is configured to count the microstructures of each intermediate node according to the route ( The Node Motif Count (NMC) scores the target routing. The second routing device can be used to calculate the NMC score of each intermediate node, and report the calculated NMC score to the first routing device.

Based on the system architecture shown in FIG. 1, an alternative deployment scenario is to deploy the first routing device on the source node 101 and the second routing device on each intermediate node. Another alternative deployment scenario is to deploy the first routing device on the target node 102 and the second routing device on each intermediate node. Optionally, the first routing device and the second routing device are deployed on each of the source node, the target node, and the intermediate node, and the first route on the source node 101 and the target node 102 is routed. The selection means executes, which is performed by the second routing means on each intermediate node when calculating the NMC score for each intermediate node.

FIG. 1a is a schematic diagram showing another architecture of a communication system to which the embodiment of the present application is applied. As shown in FIG. 1a, the source node 101 and the target node 102 are connected by a route, and the route includes an intermediate node 111 and an intermediate node 112. And intermediate node 113. The source node 101, the target node 102, and each intermediate node are all connected to the routing device 141. The routing device 141 calculates the NMC score of each intermediate node, and then selects the destination route according to the NMC score, and sends the target route to the destination route. Source node 101 and target node 102.

The solution provided by the embodiment of the present application is performed by the routing device, and the routing device may be the routing device 141 shown in FIG. 1a, or may be the device including the first routing device and the second routing device in FIG. . The following description is separately described by the first routing device and the second routing device, but any of the following method steps may be performed by any one of the first routing device and the second routing device, the first routing device And the second routing device may be respectively deployed on different nodes or different devices, or may be integrated on one device, for example, the first routing device and the second routing device are integrated on the routing device 141 shown in FIG. 1a. .

Only one route is drawn between the source node 101 and the target node 102 shown in FIG. 1 and FIG. 1a, but in practical applications, the source node 101 and the target node 102 may have multiple redundant routes. If a route stops working due to hardware failure or interference, the network automatically changes the routing of the packets, passing them through an alternate path. The embodiment of the present application provides a solution for selecting a route with high reliability and strong resistance against faults from multiple redundant routes of a source node and a target node.

FIG. 2 is a schematic flowchart diagram of a routing method provided by an embodiment of the present application.

Based on the system architecture shown in FIG. 1 and FIG. 1a, a routing method implemented by the routing apparatus provided by the embodiment of the present application is provided. As shown in Figure 2, the method includes:

Step 201: The routing device acquires at least two routes from the source node to the target node, and obtains an NMC score of the intermediate node in the at least two routes. The NMC score of the intermediate node is a polygon constructed according to the intermediate node. The number obtained; wherein the intermediate node is a vertex of a polygon constructed by the intermediate node;

Step 202: The routing device selects a target route from the at least two routes according to the NMC score of the intermediate node in the at least two routes.

Optionally, the routing device in the foregoing

steps

201 and 202 may be the routing device 141 in the foregoing FIG. 1a, or may be the first routing device and the second routing device in the foregoing content.

Optionally, in the embodiment of the present application, if the communication system architecture shown in FIG. 1a is applied, the routing device determines, according to the network topology information of the intermediate node, the intermediate node in the at least two routes from the source node to the target node. The number of polygons constructed by the node; determining the NMC score of the intermediate node according to the number of polygons constructed according to the intermediate node; selecting one of the at least two routes according to the NMC score of the intermediate node in the at least two routes Target routing.

If the routing device includes the first routing device and the second routing device, optionally, the second routing device is configured for the intermediate node of the at least two routes from the source node to the target node, according to the intermediate node. The network topology information determines the number of polygons constructed by the intermediate node; determines the NMC score of the intermediate node according to the number of polygons constructed by the intermediate node; reports the NMC score of the intermediate node; wherein the intermediate node is the The vertices of the polygons constructed by the intermediate nodes; the NMC scores of the intermediate nodes in the at least two routes are used to: select a target route from the at least two routes according to the NMC score of the intermediate nodes in the at least two routes.

Correspondingly, the first routing device acquires at least two routes from the source node to the target node, and obtains an NMC score of the intermediate node in the at least two routes; wherein the NMC score of the intermediate node is constructed according to the intermediate node The number of polygons obtained; wherein the intermediate node is a vertex of the polygon constructed by the intermediate node; the first routing device selects one of the at least two routes according to the NMC score of the intermediate node in the at least two routes Target routing. Alternatively, any of the above method steps may be performed by the first routing device or the second routing device, and the above merely exemplarily shows a division scheme of the first routing device and the second routing device.

The polygon defined in the embodiment of the present application may include a closed figure having more sides than two sides, such as a triangle, a quadrangle, a pentagon, a hexagon, and the like. In the embodiment of the present application, a node (such as an intermediate node) participates in a constructed polygon, and a link between two nodes connected by wireless or wired is referred to as an edge in a polygon, and each node is referred to as a vertex in the polygon.

Based on simulation and mathematical derivation, in different types and scales of network topology, there are two phase transitions in path expansion in the process of route rerouting. The so-called route rerouting (exposure) path expansion, specifically refers to a given one. Routing, if any segment of the route is interrupted, the breakpoint is fixed with the shortest path, and the mathematical expectation of the length of the route path is expanded (D _new -D _old ). Where D _new refers to the path length (or routing cost) of the repaired new route; D _old refers to the path length (or routing cost) of the old route before the repair.

FIG. 2a is a schematic diagram showing two phase transitions of path expansion in a route repair process provided by an embodiment of the present application. As shown in FIG. 2a, curves under different topology types are slightly different, but both are worn. After saturation, it quickly saturates "two phase transitions. In a random network, this phenomenon can be mathematically proven. As shown in Fig. 2a, the horizontal axis "reroute path expansion hop count" relative to the vertical axis "route repair (reroute) successful cumulative probability" diagram, you can clearly see the two times after the penetration quickly saturated Phase change. Its physical interpretation and significance is that in such a network, if there is an open circuit, there is a great possibility to implement an end-to-end route repair given a small number of expanded route hops. In contrast, if a small range of laps cannot fix the breakpoint, the probability of repair is low even if a larger range is allowed to find a possible repair path. Based on this, optionally, the embodiment of the present application can evaluate the repair capability of the node after the fault according to the number of polygons that the node constructs in a small range. Therefore, the number of sides of the polygon may not be too large, such as a fifteen-sided shape. Correspondingly, the polygon in the embodiment of the present application, for example, a triangle or a quadrilateral, can satisfy the requirement. Thus, on the one hand, the intermediate node calculates the NMC score. The complexity of the value, on the other hand, also increases the rate at which the NMC score is calculated. In the third aspect, the embodiment of the present application also considers a scheme of repairing a route in a small range as much as possible, and avoids the problem that the repaired route delay is too long after the repaired route is excessively bypassed, that is, the route repairing capability of the selected target route is adopted. A comprehensive consideration has been made between the delay of the repaired route and the delay.

Optionally, in order to avoid loops and broadcast storms, a solution is provided in the embodiment of the present application, and the count value of the repair times is set. When the route is repaired once, the count value of the repair times is increased by 1, and when the repair count count exceeds the repair value. After the threshold is reached, even if the route is broken again, the route repair is no longer performed, and the route is interrupted. That is, the embodiment of the present application further includes a repair count value, for each intermediate node in the target route, if the intermediate node determines a route fault between the intermediate node and the next hop intermediate node in the target route, and When it is determined that the repair count value is not greater than the threshold, a route repair is performed and the repair count value is incremented by one. Performing a route repair specifically means that the intermediate node selects another alternate path to reach the next hop intermediate node of the target route. If the intermediate node determines a route fault between the intermediate node and the next hop intermediate node in the target route, and determines that the repair count count value is greater than the threshold, the route repair is not performed.

Optionally, the repair count value and the route may be attached to the packet header portion of the data packet, forwarded along the routing path, and modified along the way when modification is required. Based on the technology, the combination of route and forwarding can be implemented. In the case of a link-level route interruption, the forwarding is not interrupted, and the route at the service level is not interrupted.

It can be seen from the above that the target route selected in the embodiment of the present application considers the route repair capability of each intermediate node on the route, and thus the reliability of the route can be improved. Further, for the two equal-cost routes, the advantages of the method in the present application can be further improved. In the embodiment of the present application, it can be determined that the fault repair capability of the route in the two equal-cost routes is higher.

Optionally, the first route and the second route are equivalent to the at least two routes, where the first route and the second route are any two routes of the at least two routes; the first route and the second route are equivalently specific The first route and the second route may meet the preset condition, and the preset condition may include multiple types, such as the following first case to the fifth case:

In the first case, the number of hops between nodes included in the first route is the same as the number of hops between nodes included in the second route. The number of hops between nodes included in the route refers specifically to the number of hops in the route that the data needs to jump between the nodes. In some cases, the number of hops between nodes included in the route may be the same as the number of intermediate nodes included in the route. For example, if the route includes three intermediate nodes, the route may include 4 hops, but may also include 5 hops, 6 Jump and so on. In some cases, the first route and the second route are equivalently the same. The number of intermediate nodes included in the first route is the same as the number of intermediate nodes included in the second route.

In the second case, the transmission delay of the first route is the same as the transmission delay included in the second route. The transmission delay of the first route specifically refers to the time required for data to be transmitted from the source node to the destination node along the first route; or the time required for data to be transmitted from the target node to the source node along the first route. The transmission delay of the second route specifically refers to the time required for data to be transmitted from the source node to the destination node along the second route; or the time required for data to be transmitted from the target node to the source node along the second route. In this case, the number of hops between the nodes included in the first route may be different or the same as the number of hops between the nodes included in the second route.

A scheme is provided optionally for calculating the transmission delay of a route, each router maintains a distance vector (usually a delay is a variable) table, and then advertises the distance by a distance vector between adjacent nodes. The update of the vector table, for example, may be advertised between nodes by periodic or event-triggered forms, such as delay between the node and the neighboring node, link state information, and the like. The distance vector table may include a delay between nodes, and the delay of a route may be calculated based on the distance vector table.

In the third case, the sum of the weights of the links included in the first route is the same as the sum of the weights of the links included in the second route. The link included in each of the first route and the second route specifically refers to a link between any two nodes on the first route, and each link corresponds to one weight. The weight of the link may be related to delay, maximum bandwidth, delay jitter, unit bandwidth price, and so on.

In the fourth case, the sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route. Each intermediate node included in each of the first route and the second route corresponds to one weight. The weight corresponding to the intermediate node may be related to the maximum processing power of the intermediate node, the current load level, and the like. The intermediate node can be a router.

In the fifth case, the sum of the weight of the link included in the first route and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node.

FIG. 2b is a schematic diagram showing a system architecture of a route provided by an embodiment of the present application. As shown in FIG. 2b, the source node 101 and the target node 102 include multiple redundant routes, such as:

Route A: source node 101, intermediate node 111, intermediate node 112, intermediate node 113, and target node 102;

Route B: source node 101, intermediate node 121, intermediate node 122, intermediate node 123, and target node 102;

Route C: source node 101, intermediate node 131, intermediate node 132, and target node 102.

As can be seen from FIG. 2b, the source node 101 and the target node 102 further include other routes, such as the route D, including: the source node 101, the intermediate node 121, the intermediate node 151, the intermediate node 122, the intermediate node 123, and the target node 102; For example, the route E includes: the source node 101, the intermediate node including the intermediate node 121, the intermediate node 152, the intermediate node 123, and the target node 102. The route that can connect the source node 101 to the target node 102 also includes others, and details are not described herein again.

As shown in FIG. 2b, if the route-equivalent preset condition in the embodiment of the present application is the foregoing second case, and if the transmission delays of the route A and the route B are the same, and the transmission delays of the route A and the route B are It is the two routes with the smallest transmission delay among all the routes between the source node 101 and the target node 102. On the one hand, in the embodiment of the present application, the route with the smallest transmission delay can be selected as the target route, and the route with the strong transmission delay can be selected as the target route in the route with the smallest transmission delay.

Optionally, the embodiment of the present application is applicable to multiple networks, such as a random network and a power rate network, where the network topology in the WMN belongs to a typical random network, and the topology in the inter-domain routing scenario belongs to a typical power rate network.

In the embodiment of the present application, some polygons for calculating the NMC score may be predefined, and the polygons used by each intermediate node to calculate the NMC score are specifically notified, and may be notified by broadcast or one-by-one notification.

Each of the nodes in the network in the embodiment of the present application includes an intermediate node, a source node, and a target node. The method for calculating the NMC score is the same for each node. In the embodiment of the present application, an intermediate node calculates the NMC score as The example is introduced.

First, the number of polygons constructed by the intermediate nodes is determined according to the network topology information, and the intermediate nodes are the vertices of the polygons constructed by the intermediate nodes. The description is based on FIG. 2b, taking the intermediate node 122 in FIG. 2b as an example. FIG. 2c exemplarily shows the structural diagram of the triangle formed by the intermediate node 122 in FIG. 2b, and FIG. 2d exemplarily shows the figure. Schematic diagram of the quadrilateral constructed by the intermediate node 122 in 2b.

As shown in FIG. 2c, the intermediate node 122 constructs four triangles, which are a triangle composed of an intermediate node 122, an intermediate node 121, and an intermediate node 151; and an intermediate node 122, an intermediate node 151, and an intermediate node 123. A triangle formed by an intermediate node 122, an intermediate node 121, and an intermediate node 152; a triangulation composed of an intermediate node 122, an intermediate node 123, and an intermediate node 152.

As shown in FIG. 2d, the intermediate node 122 constructs four quadrilaterals, which are a quadrangle composed of an intermediate node 122, an intermediate node 152, an intermediate node 121, and an intermediate node 151; an intermediate node 122, an intermediate node 152, an intermediate node 123, and an intermediate node. A quadrangle composed of 151; a quadrangle composed of an intermediate node 122, an intermediate node 121, an intermediate node 151, and an intermediate node 123; a quadrangle formed by the intermediate node 122, the intermediate node 121, the intermediate node 152, and the intermediate node 123. In the embodiment of the present application, a node (such as an intermediate node) participates in a constructed polygon, and a link between two nodes connected by wireless or wired is referred to as an edge in a polygon, and each node is referred to as a vertex in the polygon.

The number of triangles and quadrilaterals constructed by the intermediate node 122 is calculated in the above, with four triangles and four quadrilaterals. As shown in FIG. 2b, the trigonometry and the quadrilateral constructed by the intermediate node 121 are respectively: a triangle formed by the intermediate node 121, the intermediate node 151, and the intermediate node 122; the intermediate node 121, the intermediate node 152, and the intermediate node 122 A triangle formed by the intermediate node 121, the intermediate node 152, the intermediate node 122, and the intermediate node 151. It can be seen that the intermediate node 121 constructs two triangles and one quad.

When calculating the number of polygons constructed by each intermediate node, it is necessary to know the N-hop network topology information of the intermediate node, and the N-hop network topology information can cover the M-type polygon. N is an integer, and N is greater than or equal to half the number of sides of a type of polygon having the largest number of sides in the defined polygon. For example, if the type of polygon with the largest number of edges in the M-type polygon is a hexagon, then N can be 3, that is, the network topology within the three-hop range of the intermediate node can be known. Specifically, the solution for obtaining the network topology of the intermediate node is obtained by broadcasting, for example, by knowing, by the intermediate node itself, flooding the N-hop topology of the neighboring area, and notifying the second routing device, if the second routing device is used. If the second routing device is directly deployed on the intermediate node, the second routing device can also query the N-hop topology around the intermediate node deployed by itself.

Alternatively, the predefined polygons may include M-type polygons, and any two types of polygons in the M-type polygon have different numbers of sides. Specifically, when M is one, the M-type polygon includes only one type of polygon with the same number of sides, such as a triangle; when M is two, the M-type polygon may include two types of polygons with different sides, such as a triangle and a quadrangle. . Optionally, the NMC score of the intermediate node is obtained according to the number of M-type polygons constructed by the intermediate node; if M is an integer greater than or equal to 1, and if M is greater than or equal to 2, any two of the M-type polygons The number of sides of the polygon is different. In this way, the M-type polygon can be reasonably set according to the actual situation and the specific application scenario, so that the NMC score more accurately reflects the fault repair capability of the intermediate node.

In a possible implementation, determining the number of polygons constructed by the intermediate node according to the network topology information of the intermediate node, the second routing device determining, according to the network topology information of the intermediate node, the M class constructed by the intermediate node The number of polygons; where M is an integer greater than or equal to 1, and if M is greater than or equal to 2, the number of sides of any two types of polygons in the M-type polygon is different; and the number of polygons constructed by the second routing device according to the intermediate node, Determining the NMC score of the intermediate node includes: determining an NMC score of the intermediate node according to the number of M-type polygons constructed by the intermediate node. Alternatively, this embodiment can also be implemented by a first routing device.

The NMC score of the intermediate node is determined by various calculation schemes, such as directly taking the sum of the number of M types of polygons as the NMC score of the intermediate node, or presetting some formulas, such as by a formula (log (NMC _triangle + NMC _{quadrilateral} )) The NMC score of the intermediate node is calculated, wherein the NMC _triangle is the number of _triangles constructed by the intermediate node, and the NMC _{quadrilateral} is the number of _{quadrilaterals} constructed by the intermediate node.

Optionally, the NMC score of the intermediate node is: performing weighting calculation on the number of each type of polygon in the M-type polygon constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon; wherein The NMC score of the intermediate node is used to indicate: the fault repair capability of the intermediate node.

In a possible implementation, determining the NMC score of the intermediate node according to the number of M-type polygons constructed by the intermediate node includes: determining, by the second routing device, a weight corresponding to each type of polygon in the M-type polygon; The routing device performs weighting calculation on the number of each type of polygon in the M-type polygon constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon; the second routing device constructs the M-type polygon in the intermediate node The result of the weighted calculation of each type of polygon is determined as the NMC score of the intermediate node. Alternatively, this embodiment can also be implemented by a first routing device. Thus, the weights of each type of polygon in the M-type polygon can be set according to actual conditions, for example, the weight of each type of polygon is the same, both are 1; or the polygons with more edges may have a larger routing delay after repairing, Therefore, the polygons with more edges may have smaller weights, etc., so that the NMC score is balanced between the fault repair capability of the intermediate node and the delay of the repaired route.

The weighting calculation in the above solution specifically refers to mathematically calculating the number of each type of polygon constructed by the intermediate node according to a preset formula and a weight corresponding to each type of polygon in the M-type polygon. There are many types of weighting calculations. For example, the weights corresponding to each type of polygon in the M-type polygon are multiplied by the number of such polygons, and the obtained M products are added, multiplied or subtracted, or other mathematical operations are performed. The result obtained is the NMC score of the intermediate node. For another example, the number of each type of polygon in the M-type polygon is reciprocal and then summed, and the obtained result is the NMC score of the intermediate node. For example, taking the average of the number of M-type polygons, the result is the NMC score of the intermediate node. For example, the minimum value of the number of M-type polygons is taken, and the minimum number of polygons is used as the NMC score of the intermediate node. In this example, other M-1 classes other than the smallest type of polygons may be used. The weight corresponding to the number of polygons is set to zero, and the weight of the number of polygons corresponding to the smallest number is set to 1.

The NMC score of the route is used to indicate the fault repair capability of the route. For example, the NMC score of the intermediate node is obtained by adding the number of polygons constructed by the intermediate node, or weighted and added, and the intermediate node is obtained. The higher the NMC score is, the stronger the fault repair capability of the intermediate node is; or the NMC score of the intermediate node is obtained by adding the reciprocal of the number of polygons constructed by the intermediate node, and the NMC score of the intermediate node is higher. The fault repair capability of the intermediate node is weaker.

Optionally, selecting a target route from the at least two routes according to the NMC score of the intermediate node in the at least two routes, including: the first routing device according to the NMC score of the intermediate node in the at least two routes Determining the NMC score of the route in the at least two routes; wherein the NMC score of the route is used to indicate the fault repair capability of the route; the first routing device according to the NMC score of the route in the at least two routes, The route corresponding to the NMC score of the indicated route with the strongest fault repair capability is determined as the target route. Alternatively, this embodiment can also be implemented by a second routing device.

Optionally, determining, according to the NMC score of the intermediate node in the at least two routes, the NMC score of the route in the at least two routes, including multiple manners. For example, the first method and the second method in the following content.

In a first manner, the first routing device determines, as the NMC score of the route, the NMC score of the intermediate node with the weakest fault repair capability indicated in the route in the at least two routes. For example, if the NMC score is larger, the fault repair capability is stronger; if the NMC score is smaller, the fault repair capability is weaker. Then, the NMC score of the smallest intermediate node in each route is determined as the NMC score of the route.

The first routing device determines the route corresponding to the NMC score of the route with the strongest fault repair capability as the target route according to the NMC score of the route in the at least two routes. For example, the scores of the intermediate nodes on the two routes are (route F: 3, 5, 6, 3, 2, 1), (route G: 2, 2, 2, 3, 2, 2). In this case, the NMC score on route F is the lowest, and the NMC score on route G is the lowest. Therefore, the route of route F has an NMC score of 1, and the route of route G has an NMC score of 2, because route G is routed. The NMC score is greater than the NMC score of the route of the route F. The larger the NMC score of the route is, the stronger the fault repair capability of the route is. Therefore, the route G is selected as the target route. The experimental results show that this equal-cost routing strategy can make "in the case of any link failure, more than 98% of end-to-end routes can be recovered, and the cost is less than 2 hops.

In the second manner, the first routing device performs a mathematical calculation on the intermediate node NMC in the route of at least two routes, and determines the result of the mathematical calculation as the NMC score of the route.

In the foregoing mode 2, for example, an average value of the NMC scores of the intermediate nodes of each route is calculated, and then mathematical calculation is performed, and the average value of the intermediate node NMC scores on the route is determined as the NMC score of the route.

The first routing device determines the route corresponding to the NMC score of the route with the strongest fault repair capability as the target route according to the NMC score of the route in the at least two routes. For example, the scores of the intermediate nodes on the two routes are (routes H: 0.61, 0.67, 0.65, 0.7, 0.6, 0.8), respectively (routes I: 0.65, 0.67, 0.7, 0.8, 0.65, 0.65). The NMC score of the route on the route H is the average of the NMC scores of the intermediate nodes, which is 0.6717. The NMC score on the route I is the average value of the NMC scores of the intermediate nodes, which is 0.6867. The NMC score of the route is greater than the NMC score of the route of route H. The larger the NMC score of the route is, the stronger the fault repair capability of the route is. Therefore, route I is selected as the target route. The experimental results show that this equal-cost routing strategy can make "in the case of any link failure, more than 90% of end-to-end routes can be recovered, and the cost is less than 3 hops.

In the above solution, if the first routing device is deployed at the source node, the second routing device is deployed at the intermediate node; or the first routing device is deployed in the routing device 141 as shown in FIG. 1a, Selecting the NMC scores of the intermediate nodes in the at least two routes, including: the first routing device acquires the NMC reported by each intermediate node in each of the at least two routes by using a flooding or periodic information exchange mechanism. Score. That is, in one embodiment, the NMC score for each intermediate node can be calculated by each intermediate node and then reported to the first routing device. Or the NMC score of each intermediate node may also be calculated by the first routing device or the second routing device or the routing device 141 as shown in Figure 1a.

Optionally, the NMC score reported by each intermediate node in each of the at least two routes is obtained by flooding. Flooding does not require maintaining the topology of the network and related routing calculations. It only requires that the node receiving the information forwards the packet in a broadcast manner. For example, the source node wants to send a piece of data to the target node. The source node first transmits a copy of the data to each of its neighbor nodes over the network, and each neighbor node transmits the data to the respective node other than the node from which the data was sent. This continues until the data is transferred to the target node or the data set lifetime (TTL) is zero. It can be seen that the NMC score of each intermediate node can be obtained through the scheme.

Optionally, the NMC score reported by each intermediate node in each of the at least two routes is obtained by using a periodic information exchange mechanism. The periodic information exchange mechanism can periodically broadcast its own NMC scores for the intermediate nodes, and so on.

In order to be compatible with the prior art, the embodiment of the present application provides a solution for the first routing device to obtain the NMC score of each intermediate node. Optionally, the first routing device is deployed at the source node, and the second The routing device is deployed in the intermediate node. FIG. 2e exemplarily shows a schematic flowchart of a method for the first routing device to obtain the NMC score of each intermediate node, as shown in FIG. 2 e. The method includes:

Step 251: The first routing device broadcasts a routing request. The routing request includes an identifier of the target node.

The first routing device can be deployed to the source node, and the source node can first broadcast a "Route Request" message to its node. In addition to the identifier of the target node, the message may include a field of "route record", a field of "identity of route request", and the like. The “Route Record” field is used to record the identifier of the intermediate node included in the route from the source node to the target node. The identifier of the intermediate node may also be the address of the intermediate node, and the intermediate node can be uniquely found.

Step 252, the second routing device receives the routing request. The routing request includes an identifier of the target node. Optionally, the second routing device is deployed on the intermediate node.

Step 253: After determining that the routing request is received for the first time, the second routing device adds the identifier of the intermediate node and the NMC score to the routing record of the routing request according to the identifier of the routing request, and forwards and adds the identifier of the intermediate node. Routing request for NMC scores. Specifically, the forwarding increases the identifier of the intermediate node and the routing request of the NMC score, and the routing request that adds the identifier of the intermediate node and the NMC score can be broadcasted in a broadcast manner.

In step 253, the second routing device determines, after receiving the routing request, whether there is a plurality of determining manners for receiving the routing request for the first time, for example, the method is: the intermediate node maintains a sequence pair list, where The source node identifier of the route request in the sequence pair list, the identifier of the route request>, when the route request is received, if the <source node identifier of the route request, the identifier of the route request> does not exist in the sequence pair list of the intermediate node , indicating that the routing request is received for the first time, and the routing request <source node identifier, the identifier of the routing request> is saved in the sequence pair list of the intermediate node; if the source node identifier of the routing request, the routing request The identifier> exists in the sequence pair list of the intermediate node, indicating that the route request has been received before, and this time it is not processed.

Another optional method for judging whether the route request is received for the first time is: determining whether the identifier of the intermediate node is included in the “Route Record” field in the route request, and if not, determining that it is received for the first time, and The identifier of the intermediate node and the NMC score are added to the field of the route record of the route request; if it is included, it indicates that the route request has been received before, and this time it is not processed.

In step 254, the target node receives the routing request and returns a routing response to the source node. The route response includes: at least two routes from the source node to the target node, and NMC scores of the intermediate nodes in the at least two routes.

Specifically, the sequence of the identifiers of the intermediate nodes in the route record in the route request constitutes a route, the target node attaches the route to the route response, and sends the route to the source node, and the NMC of each intermediate node in the route. Score.

Specifically, the target node may receive multiple routing requests, and there are different routes included in at least two routing requests. Optionally, the target node attaches at least the two routes to two routing responses or is attached to one route. The response is returned to the source node. Alternatively, the target node replies with a route response for each received route request, where each route response includes a route included in the route request.

Optionally, the target node may invert the sequence of the identifier of the intermediate node in the route record, that is, a route from the target node to the source node, and the target node may return a route response to the source node along the route. It is also possible that the channel is asymmetric, and the target node needs to initiate a routing request process to the source node, and at the same time, the routing response message is carried in the new routing request.

Step 255: The first routing device receives the routing response corresponding to the routing request returned by the target node, where the routing response includes: at least two routes from the source node to the target node, and NMC points of the intermediate nodes in the at least two routes. value.

Optionally, the first routing device is deployed on the source node, and after receiving the routing response, the first routing device reverses the sequence of the identifier of the intermediate node included in the routing response, that is, the source node to the target is obtained. The route of the node. After receiving the at least two routes, the source node selects the destination route according to the foregoing solution, and details are not described herein.

In the embodiment of the present application, only the NMC score of the route is calculated when the target route is selected, the calculation scheme is simple, the complexity is fast, and the route calculation speed is fast; and each node, such as an intermediate node, needs less state information to be maintained, for example, only It is sufficient to maintain the NMC score of the user. In the third embodiment, the information exchanged between the nodes in the embodiment of the present application is less, and the information exchanged between each node and the first routing device and the second routing device is less. The network load is alleviated; in the fourth aspect, the target route selected by the solution provided by the embodiment of the present application has strong ability to resist failure, fast self-healing speed, and low cost. Further, the solution provided by the embodiment of the present application is not only applicable to the WMN network, but also effective for the large-scale dynamic network robust routing problem, but the microstructure selection and routing formula in different networks may be different, and may be combined with specific After the scenario is analyzed offline, the relevant conclusions are obtained and then the specific configuration is performed.

FIG. 3 exemplarily shows a schematic structural diagram of a routing apparatus provided by the present application.

Based on the same concept, the present application provides a routing device 300 for performing the above method flow. The routing device 300 may include the first routing device in the above content, or may include the first routing device and the second routing device in the above content, or may be the routing device 141 in FIG. 1a in the above content. That is, the routing device 300 may be configured to perform any of the foregoing methods, that is, perform any one of the foregoing methods performed by the first routing device or the second routing device, or execute the first routing device. And any one of the schemes performed by the second routing device, or any of the schemes performed by the routing device 141 described above.

As shown in FIG. 3, the routing device 300 includes a processor 301, a transceiver 302, a memory 303, and a communication interface 304; wherein the processor 301, the transceiver 302, the memory 303, and the communication interface 304 are connected to one another via a bus 305.

The bus 305 can be a peripheral component interconnect (PCI) bus or an extended industry standard architecture (EISA) bus. The bus can be divided into an address bus, a data bus, a control bus, and the like. For ease of representation, only one thick line is shown in Figure 3, but it does not mean that there is only one bus or one type of bus.

The memory 303 may include a volatile memory such as a random-access memory (RAM); the memory may also include a non-volatile memory such as a flash memory. A hard disk drive (HDD) or a solid-state drive (SSD); the memory 303 may also include a combination of the above types of memories.

The communication interface 304 can be a wired communication access port, a wireless communication interface, or a combination thereof, wherein the wired communication interface can be, for example, an Ethernet interface. The Ethernet interface can be an optical interface, an electrical interface, or a combination thereof. The wireless communication interface can be a WLAN interface.

The processor 301 can be a central processing unit (CPU), a network processor (NP), or a combination of a CPU and an NP. The processor 301 may further include a hardware chip. The hardware chip may be an application-specific integrated circuit (ASIC), a programmable logic device (PLD), or a combination thereof. The PLD may be a complex programmable logic device (CPLD), a field-programmable gate array (FPGA), a general array logic (GAL), or any combination thereof.

Optionally, the memory 303 can also be used to store program instructions, and the processor 301 calls the program instructions stored in the memory 303 to perform one or more steps in the embodiment shown in FIG. 2 to FIG. 2e, or alternatively The embodiment enables the routing device 300 to implement the functions of the first routing device and/or the second routing device in the above method, and to cause the routing device 300 to implement the functions of the routing device 141 in the above method.

The processor 301 is configured to control the transceiver 302 to perform signal reception and signal transmission according to the instruction for executing the memory storage. When the processor 301 executes the memory storage instruction, the routing device is configured to: acquire at least two of the source node to the target node. And routing the NMC scores of the intermediate nodes of the at least two routes; and selecting a destination route from the at least two routes according to the NMC score of the intermediate nodes in the at least two routes; wherein, the middle The NMC score of the node is obtained according to the number of polygons constructed by the intermediate node; wherein the intermediate node is the vertex of the polygon constructed by the intermediate node.

Optionally, the processor 301 is configured to determine, according to an NMC score of the intermediate node in the at least two routes, an NMC score of the route in the at least two routes, where the NMC score of the route is used to indicate the The fault repairing capability of the route is determined by the NMC score of the route of the at least two routes, and the route corresponding to the NMC score of the route with the strongest fault repair capability is determined as the target route.

Optionally, the processor 301 is configured to determine, by using any one of the following methods, the NMC score of the route in the at least two routes: the NMC score of the intermediate node that has the weakest fault repair capability indicated in the route in the at least two routes. The NMC score is determined as a route; the intermediate node NMC score in the route of at least two routes is mathematically calculated, and the result of the mathematical calculation is determined as the NMC score of the route.

Optionally, the transceiver 302 is further configured to: obtain, by using a flooding or periodic information exchange mechanism, an NMC score reported by each of the at least two routes. Optionally, the processor 301 obtains the NMC score of the intermediate node, and the control transceiver 302 receives the NMC score reported by each of the at least two routes, and may also calculate at least two by the processor 301. The NMC score of each intermediate node in each route in the route.

Optionally, the transceiver 302 is configured to: broadcast a routing request; where the routing request includes an identifier of the target node; and receive a routing response corresponding to the routing request returned by the target node; where the routing response includes: the source node to the target node At least two routes, and NMC scores of intermediate nodes in at least two routes. In this example, routing device 300 can be integrated on the source node.

FIG. 4 exemplarily shows a schematic structural diagram of a routing apparatus provided by the present application.

Based on the same concept, the present application provides a routing device 400 for performing the above method flow. The routing device 400 may include the second routing device in the above content, or may include the first routing device and the second routing device in the above content, or may be the routing device 141 in FIG. 1a in the above content. That is, the routing device 400 can be configured to perform any of the foregoing methods, that is, perform any one of the foregoing methods performed by the first routing device or the second routing device, and execute the routing device 141. Any of the programs implemented.

As shown in FIG. 4, the routing device 400 includes a processor 401, a transceiver 402, a memory 403, and a communication interface 404; wherein the processor 401, the transceiver 402, the memory 403, and the communication interface 404 are connected to one another via a bus 405.

The bus 405 can be a peripheral component interconnect (PCI) bus or an extended industry standard architecture (EISA) bus. The bus can be divided into an address bus, a data bus, a control bus, and the like. For ease of representation, only one thick line is shown in Figure 4, but it does not mean that there is only one bus or one type of bus.

The memory 403 may include a volatile memory such as a random-access memory (RAM); the memory may also include a non-volatile memory such as a flash memory. A hard disk drive (HDD) or a solid-state drive (SSD); the memory 403 may also include a combination of the above types of memories.

The communication interface 404 can be a wired communication access port, a wireless communication interface, or a combination thereof, wherein the wired communication interface can be, for example, an Ethernet interface. The Ethernet interface can be an optical interface, an electrical interface, or a combination thereof. The wireless communication interface can be a WLAN interface.

The processor 401 may be a central processing unit (CPU), a network processor (NP), or a combination of a CPU and an NP. The processor 401 may further include a hardware chip. The hardware chip may be an application-specific integrated circuit (ASIC), a programmable logic device (PLD), or a combination thereof. The PLD may be a complex programmable logic device (CPLD), a field-programmable gate array (FPGA), a general array logic (GAL), or any combination thereof.

Optionally, the memory 403 can also be used to store program instructions, and the processor 401 calls the program instructions stored in the memory 403, and can perform one or more steps in the embodiment shown in FIG. 2 to FIG. 2e, or The embodiment enables the routing device 400 to implement the functions of the first routing device and/or the second routing device in the above method, or to cause the routing device 400 to implement the functions of the routing device 141 in the above method.

The processor 401 is configured to control the transceiver 402 to perform signal reception and signal transmission according to the instruction for executing the memory storage. When the processor 401 executes the memory storage instruction, the routing device is configured to: at least two for the source node to the target node. An intermediate node in the routing, performing: determining, according to network topology information of the intermediate node, a number of polygons constructed by the intermediate node; wherein the intermediate node is a vertex of a polygon constructed by the intermediate node; and a polygon constructed according to the intermediate node The NMC score of the intermediate node is determined by the quantity; the NMC score of the intermediate node is reported; wherein the NMC score of the intermediate node in the at least two routes is used: according to the intermediate node of the at least two routes The NMC score selects a destination route from at least two routes.

Optionally, the first route and the second route are equivalent to the at least two routes; wherein the first route and the second route are any two routes of the at least two routes; the first route and the second route meet the following content Any one of the following: the hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route; the transmission delay of the first route is the same as the transmission delay included in the second route; the first route The sum of the weights of the included links is the same as the sum of the weights of the links included in the second route; the sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route; the first route The sum of the weight of the included link and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node. It can be seen from the above that the target route selected in the embodiment of the present application considers the route repair capability of each intermediate node on the route, and thus the reliability of the route can be improved. Further, for the two equal-cost routes, the advantages of the present application can be further improved. In this embodiment, the fault repair capability of the route in the two equal-cost routes is determined to be higher.

Optionally, the processor 401 is configured to determine, according to network topology information of the intermediate node, the number of M types of polygons constructed by the intermediate node, where M is an integer greater than or equal to 1, and if M is greater than or equal to 2, The number of sides of any two types of polygons in the M-type polygon is different; according to the number of M-type polygons constructed by the intermediate node, the NMC score of the intermediate node is determined. In this way, the M-type polygon can be reasonably set according to the actual situation and the specific application scenario, so that the NMC score more accurately reflects the fault repair capability of the intermediate node.

Optionally, the processor 401 is configured to: determine a weight corresponding to each type of polygon in the M-type polygon; and, according to the weight corresponding to each type of polygon in the M-type polygon, each type of polygon in the M-type polygon constructed by the intermediate node The number is weighted; the result of weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node is determined as the NMC score of the intermediate node. Thus, the weights of each type of polygon in the M-type polygon can be set according to actual conditions, for example, the weight of each type of polygon is the same, both are 1; or the polygons with more edges may have a larger routing delay after repairing, Therefore, the polygons with more edges may have smaller weights, etc., so that the NMC score is balanced between the fault repair capability of the intermediate node and the delay of the repaired route.

Optionally, the transceiver 402 is further configured to: obtain, by using a flooding or periodic information exchange mechanism, an NMC score reported by each of the at least two routes. Optionally, the NMC score reported by each of the at least two routes may be received by the transceiver 402, and each of the at least two routes may be calculated by the processor 401. The NMC score of the node.

Optionally, the transceiver 402 is configured to: receive a routing request, where the routing request includes an identifier of the target node; and after determining that the routing request is received for the first time, the identifier of the intermediate node and the NMC score are determined according to the identifier of the routing request. Add to the routing record of the routing request, and forward the routing request with the identifier of the intermediate node and the NMC score. In this example, routing device 300 can be integrated on the intermediate node.

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

Based on the same concept, the embodiment of the present application provides a routing device for performing the foregoing method flow. The routing device 500 may include the first routing device in the above content, or may include the first routing device and the second routing device in the above content, or may be the routing device 141 in FIG. 1a in the above content. That is, the routing device 500 can be used to perform any of the above methods. As shown in FIG. 5, the routing device 500 includes a receiving unit 501, a processing unit 502, and a transmitting unit 503.

The processing unit 502 is configured to: obtain at least two routes from the source node to the target node, and obtain a micro structure count NMC score of the intermediate node in the at least two routes; according to the NMC score of the intermediate node in the at least two routes, A target route is selected from at least two routes; wherein the NMC score of the intermediate node is obtained according to the number of polygons constructed by the intermediate node; wherein the intermediate node is a vertex of the polygon constructed by the intermediate node.

Optionally, the processing unit 502 is configured to determine, according to an NMC score of the intermediate node in the at least two routes, an NMC score of the route in the at least two routes, where the NMC score of the route is used to indicate the The fault repairing capability of the route is determined by the NMC score of the route of the at least two routes, and the route corresponding to the NMC score of the route with the strongest fault repair capability is determined as the target route.

Optionally, the processing unit 502 is configured to determine, by using any one of the following methods, the NMC score of the route in the at least two routes: the NMC score of the intermediate node that has the weakest fault repair capability indicated in the route in the at least two routes. The NMC score is determined as a route; the intermediate node NMC score in the route of at least two routes is mathematically calculated, and the result of the mathematical calculation is determined as the NMC score of the route.

Optionally, the receiving unit 501 is further configured to: obtain, by using a flooding or periodic information exchange mechanism, an NMC score reported by each intermediate node in each of the at least two routes. Optionally, the processing unit obtains the NMC score of the intermediate node, and the control receiving unit receives the NMC score reported by each of the at least two routes in the at least two routes; or the at least two routes are calculated by the processing unit. The NMC score for each intermediate node in each route.

Optionally, the sending unit 503 is configured to: broadcast a routing request, where the routing request includes an identifier of the target node, and the receiving unit 501 is configured to receive a routing response corresponding to the routing request returned by the target node, where the routing response includes: At least two routes from the source node to the destination node, and NMC scores of intermediate nodes in at least two routes. In this example, routing device 500 can be integrated on the source node.

It should be understood that the division of each unit above is only a division of a logical function, and the actual implementation may be integrated into one physical entity in whole or in part, or may be physically separated. In the embodiment of the present application, the receiving unit 501 and the sending unit 503 may be implemented by the transceiver 302, and the processing unit 502 may be implemented by the processor 301. As shown in FIG. 3, routing device 300 can include a processor 301, a transceiver 302, and a memory 303. The memory 303 can be used to store the code when the processor 301 executes the solution, and the code can be a program/code pre-installed by the routing device 300 at the factory.

FIG. 6 is a schematic structural diagram of a routing apparatus provided by an embodiment of the present application.

Based on the same concept, the embodiment of the present application provides a routing device for performing the foregoing method flow. The routing device 600 may include the second routing device in the above content, or may include the first routing device and the second routing device in the above content, or may be the routing device 141 in FIG. 1a in the above content. That is, the routing device 600 can be used to perform any of the above methods. As shown in FIG. 6, the routing device 600 includes a receiving unit 601, a processing unit 602, and a transmitting unit 603.

The processing unit 602 is configured to: determine, according to the network topology information of the intermediate node, the number of polygons constructed by the intermediate node, where the intermediate node is the intermediate node, and the intermediate node of the at least two routes of the source node to the target node The vertices of the constructed polygons; determining the NMC score of the microstructure of the intermediate node according to the number of polygons constructed by the intermediate node; reporting the NMC score of the intermediate node; wherein, the NMC points of the intermediate nodes in at least two routes The value is used to: select a target route from at least two routes according to an NMC score of an intermediate node in at least two routes.

Optionally, the processing unit 602 is configured to: determine, according to network topology information of the intermediate node, the number of M types of polygons constructed by the intermediate node; where M is an integer greater than or equal to 1, and if M is greater than or equal to 2, The number of sides of any two types of polygons in the M-type polygon is different; according to the number of M-type polygons constructed by the intermediate node, the NMC score of the intermediate node is determined. In this way, the M-type polygon can be reasonably set according to the actual situation and the specific application scenario, so that the NMC score more accurately reflects the fault repair capability of the intermediate node.

Optionally, the processing unit 602 is configured to: determine weights corresponding to each type of polygon in the M type polygon; and perform weights of each type of polygon in the M type polygon constructed by the intermediate node according to weights corresponding to each type of polygon in the M type polygon The number is weighted; the result of weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node is determined as the NMC score of the intermediate node. Thus, the weights of each type of polygon in the M-type polygon can be set according to actual conditions, for example, the weight of each type of polygon is the same, both are 1; or the polygons with more edges may have a larger routing delay after repairing, Therefore, the polygons with more edges may have smaller weights, etc., so that the NMC score is balanced between the fault repair capability of the intermediate node and the delay of the repaired route.

Optionally, the receiving unit 601 is further configured to: obtain, by using a flooding or periodic information exchange mechanism, an NMC score reported by each of the at least two routes. Optionally, the receiving unit 601 can receive the NMC score reported by each of the at least two routes, and the processing unit 602 can calculate each middle of each of the at least two routes. The NMC score of the node.

Optionally, the receiving unit 601 is configured to: receive a routing request, where the routing request includes an identifier of the target node, and the processing unit 602 is configured to: after determining that the routing request is received for the first time, the intermediate node is determined according to the identifier of the routing request The identifier and the NMC score are added to the routing record of the routing request, and the routing request that adds the identity of the intermediate node and the NMC score is forwarded by the sending unit 603. In this example, routing device 600 can be integrated on the intermediate node.

It should be understood that the division of each unit above is only a division of a logical function, and the actual implementation may be integrated into one physical entity in whole or in part, or may be physically separated. In the embodiment of the present application, the receiving unit 601 and the sending unit 603 may be implemented by the transceiver 402, and the processing unit 602 may be implemented by the processor 401. As shown in FIG. 4, routing device 400 can include a processor 401, a transceiver 402, and a memory 403. The memory 403 can be used to store the code when the processor 401 executes the solution, and the code can be a program/code pre-installed by the routing device 400 at the factory.

The embodiment of the present application provides a computer storage medium for storing computer program instructions used by the routing device 300, including a program for executing the above routing method.

The computer storage medium can be any available media or data storage device accessible by the computer, including but not limited to magnetic memory (eg, floppy disk, hard disk, magnetic tape, magneto-optical disk (MO), etc.), optical storage (eg, CD, DVD, BD, HVD, etc.), and semiconductor memories (such as ROM, EPROM, EEPROM, non-volatile memory (NAND FLASH), solid-state hard disk (SSD)).

The embodiment of the present application further provides another computer storage medium for storing computer program instructions used by the routing device 400, including a program for executing the routing method described above.

Those skilled in the art will appreciate that embodiments of the present application can be provided as a method, system, or computer program product. Therefore, the embodiments of the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware. Moreover, embodiments of the present application can take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) including computer usable program code.

Embodiments of the present application are described with reference to flowchart illustrations and/or block diagrams of methods, devices (systems), and computer program products according to embodiments of the present application. It will be understood that each flow and/or block of the flowchart illustrations and/or FIG. These computer program instructions can be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing device to produce a machine for the execution of instructions for execution by a processor of a computer or other programmable data processing device. Means for implementing the functions specified in one or more of the flow or in a block or blocks of the flow chart.

The computer program instructions can also be stored in a computer readable memory that can direct a computer or other programmable data processing device to operate in a particular manner, such that the instructions stored in the computer readable memory produce an article of manufacture comprising the instruction device. The apparatus implements the functions specified in one or more blocks of a flow or a flow and/or block diagram of the flowchart.

These computer program instructions can also be loaded onto a computer or other programmable data processing device such that a series of operational steps are performed on a computer or other programmable device to produce computer-implemented processing for execution on a computer or other programmable device. The instructions provide steps for implementing the functions specified in one or more of the flow or in a block or blocks of a flow diagram.

It is apparent that those skilled in the art can make various modifications and variations to the embodiments of the present application without departing from the spirit and scope of the application. Thus, it is intended that the present invention cover the modifications and variations of the embodiments of the present invention.

Claims

A routing method, comprising:

Obtaining at least two routes from the source node to the target node, and acquiring a microstructure count NMC score of the intermediate node in the at least two routes; wherein, the NMC score of the intermediate node is the number of polygons constructed according to the intermediate node Obtained; wherein the intermediate node is a vertex of a polygon constructed by the intermediate node;

And selecting a target route from the at least two routes according to an NMC score of the intermediate node in the at least two routes.
The method according to claim 1, wherein the first route and the second route are equivalent to the at least two routes; wherein the first route and the second route are the at least two routes Any two routes in ;

The first route and the second route satisfy any of the following:

The hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route;

The transmission delay of the first route is the same as the transmission delay of the second route;

The sum of the weights of the links included in the first route is the same as the sum of the weights of the links included in the second route;

The sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route;

The sum of the weight of the link included in the first route and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node.
The method according to claim 1 or 2, wherein the NMC score of the intermediate node is obtained according to the number of M-type polygons constructed by the intermediate node;

Wherein, M is an integer greater than or equal to 1, and if M is greater than or equal to 2, the number of sides of any two types of polygons in the M-type polygon is different.
The method according to claim 3, wherein the NMC score of the intermediate node is: each of the M-type polygons to be constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon The number of polygons is weighted and calculated;

The NMC score of the intermediate node is used to indicate: the fault repair capability of the intermediate node.
The method according to any one of claims 1 to 4, wherein the selecting a destination route from the at least two routes according to an NMC score of an intermediate node of the at least two routes ,include:

Determining, according to the NMC score of the intermediate node of the at least two routes, an NMC score of the route in the at least two routes, where the NMC score of the route is used to indicate the fault repair capability of the route;

And determining, according to the NMC score of the route in the at least two routes, a route corresponding to the NMC score of the route with the strongest fault repair capability, as the target route.
The method according to claim 5, wherein the determining, according to the NMC score of the intermediate node of the at least two routes, the NMC score of the route in the at least two routes, including any of the following Ways:

Determining, by the NMC score of the intermediate node with the weakest fault repair capability indicated in the route in the at least two routes as the NMC score of the route;

The intermediate node NMC in the at least two routes is scored for mathematical calculation, and the result of the mathematical calculation is determined as the NMC score of the route.
The method according to any one of claims 1 to 6, wherein the acquiring the NMC score of the intermediate node in the at least two routes comprises:

The NMC score reported by each of the at least two routes is obtained by a flooding or periodic information exchange mechanism.
The method according to any one of claims 1 to 7, wherein the obtaining at least two routes from the source node to the target node, and acquiring the NMC scores of the intermediate nodes in the at least two routes, include:

Broadcasting a routing request; wherein the routing request includes an identifier of the target node;

And receiving, by the target node, a routing response corresponding to the routing request, where the routing response includes: the at least two routes from the source node to the target node, and the middle of the at least two routes The NMC score of the node.
A routing method, comprising:

For the intermediate nodes in the at least two routes from the source node to the destination node, perform:

Determining, according to network topology information of the intermediate node, a number of polygons constructed by the intermediate node; wherein the intermediate node is a vertex of a polygon constructed by the intermediate node;

Determining the microstructure count NMC score of the intermediate node according to the number of polygons constructed by the intermediate node;

And reporting an NMC score of the intermediate node, where the NMC score of the intermediate node in the at least two routes is used to: according to the NMC score of the intermediate node in the at least two routes, from the at least two A destination route is selected in the route.
The method according to claim 9, wherein the first route and the second route are equivalent to the at least two routes; wherein the first route and the second route are the at least two routes Any two routes in ;

The first route and the second route satisfy any of the following:

The hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route;

The transmission delay of the first route is the same as the transmission delay of the second route;

The sum of the weights of the links included in the first route is the same as the sum of the weights of the links included in the second route;

The sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route;

The sum of the weight of the link included in the first route and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node.
The method according to claim 9 or 10, wherein the determining the number of polygons constructed by the intermediate node according to the network topology information of the intermediate node comprises:

Determining, according to the network topology information of the intermediate node, the number of M-type polygons constructed by the intermediate node; wherein, M is an integer greater than or equal to 1, and if M is greater than or equal to 2, any two of the M-type polygons The number of sides of the polygon is different;

Determining the NMC score of the intermediate node according to the number of polygons constructed by the intermediate node, including:

The NMC score of the intermediate node is determined according to the number of M-type polygons constructed by the intermediate node.
The method according to claim 11, wherein the determining the NMC score of the intermediate node according to the number of M-type polygons constructed by the intermediate node comprises:

Determining a weight corresponding to each type of polygon in the M type polygon;

And weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon;

The result of weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node is determined as the NMC score of the intermediate node.
The method according to any one of claims 9 to 12, wherein the acquiring the NMC score of the intermediate node of the at least two routes comprises:

The NMC score reported by each of the at least two routes is obtained by a flooding or periodic information exchange mechanism.
The method according to any one of claims 9 to 13, wherein the reporting the NMC score of the intermediate node comprises:

Receiving a routing request; wherein the routing request includes an identifier of the target node;

And after determining that the routing request is received for the first time, adding the identifier of the intermediate node and the NMC score to the routing record of the routing request, and forwarding, adding the identifier of the intermediate node and Routing request for NMC scores.
A routing device, characterized in that the routing device comprises a processor, a transceiver and a memory;

The memory is configured to store program instructions, the processor is configured to control the transceiver to perform signal reception and signal transmission according to an instruction to execute the memory, and when the processor executes the instruction stored in the memory, The routing device is configured to: obtain at least two routes from the source node to the target node, and obtain a micro-structure count NMC score of the intermediate node in the at least two routes; according to the middle of the at least two routes An NMC score of the node, and selecting a target route from the at least two routes;

The NMC score of the intermediate node is obtained according to the number of polygons constructed by the intermediate node; wherein the intermediate node is a vertex of the polygon constructed by the intermediate node.
The apparatus according to claim 15, wherein the first route and the second route are equivalent in the at least two routes; wherein the first route and the second route are the at least two routes Any two routes in ;

The first route and the second route satisfy any of the following:

The hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route;

The transmission delay of the first route is the same as the transmission delay of the second route;

The sum of the weights of the links included in the first route is the same as the sum of the weights of the links included in the second route;

The sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route;

The sum of the weight of the link included in the first route and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node.
The apparatus according to claim 15 or 16, wherein the NMC score of the intermediate node is obtained according to the number of M-type polygons constructed by the intermediate node;

Wherein, M is an integer greater than or equal to 1, and if M is greater than or equal to 2, the number of sides of any two types of polygons in the M-type polygon is different.
The apparatus according to claim 17, wherein the NMC score of the intermediate node is: each of the M-type polygons to be constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon The number of polygons is weighted and calculated;

The NMC score of the intermediate node is used to indicate: the fault repair capability of the intermediate node.
The device according to any one of claims 15 to 18, wherein the processor is configured to:

Determining, according to the NMC score of the intermediate node of the at least two routes, an NMC score of the route in the at least two routes, where the NMC score of the route is used to indicate the fault repair capability of the route;

And determining, according to the NMC score of the route in the at least two routes, a route corresponding to the NMC score of the route with the strongest fault repair capability, as the target route.
The apparatus according to claim 19, wherein the processor is configured to determine an NMC score of the route in the at least two routes by any of the following methods:

Determining, by the NMC score of the intermediate node with the weakest fault repair capability indicated in the route in the at least two routes as the NMC score of the route;

The intermediate node NMC in the at least two routes is scored for mathematical calculation, and the result of the mathematical calculation is determined as the NMC score of the route.
The device according to any one of claims 15 to 20, wherein the transceiver is further configured to:

Obtaining an NMC score reported by each of the at least two routes in the flooding or periodic information exchange mechanism.
The device according to any one of claims 15 to 21, wherein the transceiver is configured to:

Broadcasting a routing request; wherein the routing request includes an identifier of the target node;

And receiving, by the target node, a routing response corresponding to the routing request, where the routing response includes: the at least two routes from the source node to the target node, and the middle of the at least two routes The NMC score of the node.
A routing device, characterized in that the routing device comprises a processor, a transceiver and a memory;

The memory is configured to store program instructions, the processor is configured to control the transceiver to perform signal reception and signal transmission according to an instruction to execute the memory, and when the processor executes the instruction stored in the memory, The routing device is configured to: determine, according to the network topology information of the intermediate node, the number of polygons constructed by the intermediate node, where the intermediate node is the intermediate node of the at least two routes from the source node to the target node; wherein the intermediate node is The vertices of the polygons constructed by the intermediate node; determining the microstructure count NMC score of the intermediate node according to the number of polygons constructed by the intermediate node; reporting the NMC score of the intermediate node;

The NMC score of the intermediate node in the at least two routes is used to: select a target route from the at least two routes according to an NMC score of the intermediate node in the at least two routes.
The apparatus according to claim 23, wherein the first route and the second route are equivalent in the at least two routes; wherein the first route and the second route are the at least two routes Any two routes in ;

The first route and the second route satisfy any of the following:

The hop count between the nodes included in the first route is the same as the hop count between the nodes included in the second route;

The transmission delay of the first route is the same as the transmission delay of the second route;

The sum of the weights of the links included in the first route is the same as the sum of the weights of the links included in the second route;

The sum of the weights of the intermediate nodes included in the first route is the same as the sum of the weights of the intermediate nodes included in the second route;

The sum of the weight of the link included in the first route and the weight of the intermediate node is the same as the sum of the weight of the link included in the second route and the weight of the intermediate node.
The device according to claim 23 or 24, wherein the processor is configured to:

Determining, according to the network topology information of the intermediate node, the number of M-type polygons constructed by the intermediate node; wherein, M is an integer greater than or equal to 1, and if M is greater than or equal to 2, any two of the M-type polygons The number of sides of the polygon is different;

The NMC score of the intermediate node is determined according to the number of M-type polygons constructed by the intermediate node.
The device according to claim 25, wherein said processor is configured to:

Determining a weight corresponding to each type of polygon in the M type polygon;

And weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node according to the weight corresponding to each type of polygon in the M-type polygon;

The result of weighting the number of each type of polygon in the M-type polygon constructed by the intermediate node is determined as the NMC score of the intermediate node.
The device according to any one of claims 23 to 26, wherein the transceiver is further configured to:

The NMC scores reported by each of the at least two routes are obtained by using a flooding or periodic information exchange mechanism.
The device according to any one of claims 23 to 27, wherein the transceiver is configured to:

Receiving a routing request; wherein the routing request includes an identifier of the target node;

And after determining that the routing request is received for the first time, adding the identifier of the intermediate node and the NMC score to the routing record of the routing request, and forwarding, adding the identifier of the intermediate node and Routing request for NMC scores.
A computer storage medium, characterized in that the computer storage medium stores computer executable instructions for causing the computer to perform the method of any of claims 1-8.
A computer storage medium, characterized in that the computer storage medium stores computer executable instructions for causing the computer to perform the method of any of claims 9 to 14.