CN112769696B - Routing method, network controller, system and storage medium - Google Patents
Routing method, network controller, system and storage medium Download PDFInfo
- Publication number
- CN112769696B CN112769696B CN201911077082.9A CN201911077082A CN112769696B CN 112769696 B CN112769696 B CN 112769696B CN 201911077082 A CN201911077082 A CN 201911077082A CN 112769696 B CN112769696 B CN 112769696B
- Authority
- CN
- China
- Prior art keywords
- node
- nodes
- network
- delay
- cost
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 54
- 238000004364 calculation method Methods 0.000 claims description 21
- 238000012216 screening Methods 0.000 claims description 19
- 238000001914 filtration Methods 0.000 claims 1
- 238000013138 pruning Methods 0.000 description 13
- 238000010586 diagram Methods 0.000 description 12
- 230000008569 process Effects 0.000 description 12
- 230000005540 biological transmission Effects 0.000 description 11
- 238000004422 calculation algorithm Methods 0.000 description 11
- 238000004891 communication Methods 0.000 description 9
- 238000007726 management method Methods 0.000 description 6
- 230000001934 delay Effects 0.000 description 5
- 238000012545 processing Methods 0.000 description 5
- 238000004590 computer program Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 3
- 230000006870 function Effects 0.000 description 2
- 238000013473 artificial intelligence Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000007774 longterm Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000010187 selection method Methods 0.000 description 1
- 239000000126 substance Substances 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
- 230000007723 transport mechanism Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
- H04L45/121—Shortest path evaluation by minimising delays
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
- H04L45/123—Evaluation of link metrics
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The embodiment of the invention discloses a routing method, a network controller, a system and a storage medium. The method comprises the following steps: according to the delay value between every two nodes collected in the network, the forwarding nodes between the source node and the destination node are screened from the network to screen out the forwarding nodes meeting the preset delay requirement; calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node and the screened forwarding nodes; the least costly path is selected as the routing path from the source node to the destination node.
Description
Technical Field
The embodiment of the invention relates to the technical field of communication, in particular to a routing method, a network controller, a system and a storage medium.
Background
With the development of the internet of things and artificial intelligence technology, services required to be served by a future network are more and more numerous, for example, unmanned services, telemedicine services and the like have higher and higher requirements on network performance, and the traditional network is more and more difficult to meet network requirements of users.
The software defined network (Software Defined Networking, SDN for short) breaks through the limitation of the traditional network structure, separates the data plane from the control plane, forwards data by a plurality of switches on the data plane, grasps global network information by the controller on the control plane and takes charge of controlling the routing strategy between any two switches in the data plane.
A path selection algorithm may be used to determine, for a performance indicator in the network, a route in the network for which the performance indicator meets the user's requirements. However, in the process of collecting network information and pruning nodes and links in the network, the path selection algorithm cannot consider more constraint conditions meeting the network performance requirements of users.
Disclosure of Invention
The embodiment of the invention provides a routing method, a network controller, a system and a storage medium, which can perform path selection by combining with the minimum cost of a link on the basis of meeting the time delay requirement of a user.
In a first aspect, an embodiment of the present invention provides a routing method, including: according to the delay value between every two nodes collected in the network, the forwarding nodes between the source node and the destination node are screened from the network to screen out the forwarding nodes meeting the preset delay requirement; calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node and the screened forwarding nodes; the least costly path is selected as the routing path from the source node to the destination node.
In a second aspect, an embodiment of the present invention provides a network controller, including: the node screening module is used for screening forwarding nodes between a source node and a destination node from the network according to the delay value between every two nodes collected in the network so as to screen the forwarding nodes meeting the preset delay requirement; a cost calculation module for calculating a cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node and the selected forwarding nodes; and the path selection module is used for selecting the path with the minimum cost as the routing path from the source node to the destination node.
In a third aspect, an embodiment of the present invention provides a routing system, including: a memory and a processor; the memory is used for storing programs; the processor is configured to read executable program code stored in the memory to perform the routing method described above.
In a fourth aspect, embodiments of the present invention provide a computer-readable storage medium having instructions stored therein, which when executed on a computer, cause the computer to perform the routing method of the above aspects.
According to the routing method, the network controller, the system and the storage medium of the embodiment of the invention, after the forwarding nodes which comprise the source node and the destination node and meet the preset time delay requirement are screened out from the network, the path with the minimum cost is selected as the routing path from the source node to the destination node by combining the cost of the link between every two nodes. The routing method can quickly realize the routing under the premise of comprehensively considering the time delay of the link and the user certainty requirement of the cost of the link, and can reduce the complexity of the routing process.
Drawings
The accompanying drawings are included to provide a further understanding of the invention, and are incorporated in and constitute a part of this specification, illustrate the invention and together with the description serve to explain, without limitation, the invention.
FIG. 1 is a diagram illustrating a routing network architecture according to an embodiment of the present invention.
Fig. 2 is a flow chart of a routing method according to an embodiment of the present invention.
Fig. 3 shows a network topology structure diagram of an embodiment of the present invention.
Fig. 4 shows a flow chart of a routing method according to another embodiment of the present invention.
Fig. 5 shows a specific flow diagram of the collection of network routes in fig. 4.
Fig. 6 shows a schematic diagram of a specific flow of pruning the network in fig. 4.
Fig. 7 shows a schematic flow chart of the routing in fig. 4 based on the least cost manner.
Fig. 8 is a schematic diagram of a network controller according to an embodiment of the present invention.
FIG. 9 illustrates a block diagram of an exemplary hardware architecture of a computing device in which methods and apparatus according to embodiments of the invention may be implemented.
Detailed Description
The following describes specific embodiments of the present invention in detail with reference to the drawings. It should be understood that the detailed description and specific examples, while indicating and illustrating the invention, are not intended to limit the invention. It will be apparent to one skilled in the art that the present invention may be practiced without some of these specific details. The following description of the embodiments is merely intended to provide a better understanding of the invention by showing examples of the invention.
It should be noted that, in this document, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises an element.
For a better understanding of the present invention, a routing method, apparatus, system, and storage medium according to embodiments of the present invention will be described in detail below with reference to the accompanying drawings. It should be noted that these examples are not intended to limit the scope of the present disclosure.
FIG. 1 is a diagram illustrating a routing network architecture according to an embodiment of the present invention. As shown in fig. 1, the architecture may include: an SDN controller 10 and one or more switches 20, the SDN controller 10 and each switch 20 may communicate via an OpenFlow protocol.
Wherein the SDN controller is a controller of a control plane in an SDN network architecture, the SDN controller 10 may include: a route calculation module 11 and a network information management library 12.
In the embodiment of the invention, the software defined network SDN breaks through the limitation of the traditional network structure and separates the data plane from the control plane. In the control plane, the SDN controller 10 may master global network information through the network information management library 12; the route calculation module 11 may calculate, according to the network information, a route selection between any two switches in the data plane, determine a route selection scheme according to a route calculation result, and issue the route selection scheme to the switches. In the data plane, the switches forward data according to the received routing scheme.
By way of example, the information collected in the network may include, for example: the topology structure of the whole network, the available bandwidth of each node and link in the network, the packet loss rate, the time delay between every two nodes in the network under the condition of the worst network quality, the source node, the destination node and the like.
In an SDN network architecture, the nodes in the embodiments of the present invention may be communication nodes of the SDN network architecture, and each communication node may correspond to a switch located at a data plane in the SDN network architecture.
It should be understood that the routing method of the embodiment of the present invention may try out a traditional network structure unexpected to the SDN network architecture. In other network structures, the communication node may be a communication node such as a router, a switch, a server, or a base station. Moreover, the number of switch devices in fig. 1 is merely illustrative, and may be flexibly adjusted according to practical application requirements. The content is not limited in this respect.
Fig. 2 is a flow chart of a routing method according to an embodiment of the present invention.
As shown in fig. 2, the routing method according to the embodiment of the present invention may include steps S110 to S130.
S110, according to the time delay value between every two nodes collected in the network, the forwarding nodes between the source node and the destination node are screened from the network, so that the forwarding nodes meeting the preset time delay requirement are screened.
S120, calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node and the screened forwarding nodes.
S130, selecting the path with the minimum cost as a routing path from the source node to the destination node.
According to the routing method provided by the embodiment of the invention, on the basis of meeting the deterministic time delay requirement of the user, factors such as node link cost and the like are further comprehensively considered, and the minimum cost path selection of the end-to-end time delay guarantee is realized.
In the step S110, the delay value between every two nodes is the sum of the transmission delay, the link delay, the receiving delay and the queuing delay required when the quality of the network satisfies the preset condition of the worst network quality.
In one embodiment, the quality of the network may be measured by the speed of communication in the network and the degree of network stability. The communication speed may be represented, for example, by the network transmission rate, i.e., the number of bits of a binary number transmitted per second; the network stability degree means that the network system can improve the performance of meeting index bandwidth for a long term and reliably, namely the network system must work normally within a specified duration, for example, faults such as downtime, restarting and the like do not occur; under the condition of full load, the device works normally and cannot collapse, and the processing efficiency is kept within the specified processing efficiency threshold range. Metrics of network stability may include, for example: average no-break interval duration (Mean Time Between Failures), maximum stable bandwidth, maximum number of concurrent flows, etc.
In this embodiment, the preset network quality worst condition may include at least one of the following, for example: the network transmission rate is smaller than or equal to a transmission rate threshold, the network system cannot work normally within a specified duration, such as downtime fault and/or restarting fault, the average fault-free interval time is smaller than a preset duration threshold, the maximum stable bandwidth is smaller than a bandwidth threshold, and the maximum concurrent flow number is smaller than a concurrent flow number threshold. In the following description of the embodiments, the worst network quality is represented by: the quality of the network meets the preset network quality worst condition.
In one embodiment, latency refers to the time required for data to be transferred from one end of a network (or link) to the other. Delays in the network or link may include transmit delays, link delays, receive delays, and queuing delays.
The transmission delay is the time required for transmitting the data frame, that is, the time required from the first bit of the data frame to the end of the transmission of the last bit of the data frame, and may also be referred to as the forwarding delay.
Link delay is the time it takes for a data frame to travel a certain distance in a transmission channel.
The reception delay, which is the time it takes to process a received data frame, may also be referred to as the processing delay, for example, analyzing the header of the packet, extracting the data portion from the packet, performing error checking or finding the appropriate route, etc.
Queuing delay is delay generated by queuing data in an input queue for waiting processing after entering a router after the data is transmitted through a network and queuing data in an output queue for waiting for forwarding after the router determines a forwarding interface.
In this embodiment, the sum of the delay formed by the transmission delay, the link delay, the reception delay, and the queuing delay required for data transmission in the case of the worst quality of the network between two nodes is taken as the delay between the two nodes.
In one embodiment, step S110 may include S111-S113, in particular.
S111, setting a time delay weight between every two nodes based on the time delay value between every two nodes.
In step S111, if there is a direct link between every two nodes, setting a delay weight as a delay value between every two nodes; if no directly connected link exists between every two nodes, setting the time delay weight value to be positive infinity.
As an example, if the node u and the node v are directly connected, the delay weight value is equal to the delay between the node u and the node v under the condition of the worst network quality, that is, the forwarding delay of the node u, the link delay of u to v, and the sum of the receiving delay of v and the delay of queuing delay in v under the condition of the worst network quality, and if u is not an adjacent contact of v, the delay weight value is positive infinity.
S112, calculating a forward minimum delay weight and a reverse minimum delay weight of any node in the network according to the delay weights between every two nodes, wherein the forward minimum delay weight is the minimum value of the delay weights from any node to the destination node, and the reverse minimum delay weight is the minimum value of the delay weights from any node to the source node.
In step S112, a shortest path algorithm may be used to calculate a minimum delay weight from any node to the source node and a minimum delay weight from any node to the destination node according to the delay weight between every two nodes.
In one embodiment, the shortest path algorithm may be understood as: when the number of paths from the source node to the destination node is more than one, each path may include a plurality of nodes and links between two adjacent nodes. The shortest path algorithm calculates the shortest path from the source node to the destination node, i.e. finds a path with the smallest sum of the weights formed by the weights of the links contained in more than one path from the source node to the destination node.
In one embodiment, the shortest path algorithm includes, but is not limited to: dijkstra's algorithm, floyd's algorithm, belman-Ford's algorithm, and shortest path fast algorithm (Shortest Path Faster Algorithm, SPFA).
In the embodiment of the invention, the minimum time delay weight of the direction from any node to the source node is determined by finding the shortest path from any node to the source node by utilizing the time delay weight of the link; and determining the minimum time delay weight from any node to the destination node by finding the shortest path from any node to the destination node. That is, the time delay of the routing node in the network under the condition of the worst network quality can be collected from the forward direction and the backward direction to the source node and the destination node.
S113, calculating the sum of the forward minimum time delay weight and the reverse minimum time delay weight, and taking the node in the network with the sum of the time delay weights smaller than the preset time delay upper limit value as the forwarding node meeting the preset time delay requirement.
In step S113, the preset delay upper limit value is a preset delay upper limit that meets the user requirement. According to the time delay upper limit value, the nodes which cannot meet the time delay requirement in the network can be pruned, and the end-to-end time delay guarantee is realized between the source node and the destination node.
In one embodiment, step S120 may include S121-S123, in particular.
S121, screening each link formed by the source node, the destination node and the screened forwarding nodes to obtain links with available bandwidths larger than or equal to a preset bandwidth demand threshold and/or with packet loss rate smaller than a preset packet loss rate threshold.
In step S121, the bandwidth consumed by one link in the network affects the bandwidth resources available to other links in the network. To ensure data carrying capacity and network performance of the network path. Links between nodes in a network may be screened using the available bandwidth of the links.
In this step, the packet loss rate is the ratio of the number of lost packets to the total number of packets transmitted during data transmission between two nodes. The packet loss rate of links in the network during normal transmission should be controlled within a certain range. To ensure network stability, links in the network may be screened according to the packet loss rate.
S122, calculating the cost of each path from the source node to the destination node according to the cost of each link formed by the forwarding node, the source node and the destination node contained in the screened links.
In this embodiment, the least expensive path may be selected as the routing path from the source node to the destination node. According to the route selection method provided by the embodiment of the invention, the nodes and links in the network can be screened by the upper time delay limit of the user demand, constraint conditions such as performance indexes of bandwidth, packet loss rate and the like are comprehensively considered, and the minimum spending path between the source node and the target node in the network is selected after the routes which do not meet the conditions are rapidly discarded.
In one embodiment, in the step S120 or S122, the step of calculating the cost of each path from the source node to the destination node may specifically include the following steps S21 to S22.
And S21, taking the sum of the cost of using each link and the cost of using the receiving node in each link, which is collected from the network, as the total cost of using each link.
In this step, when there is a directly connected link between every two nodes, the total cost is equal to the sum of the cost of the link between every two nodes and the cost of the receiving node in the link; when there is no direct-connected link between every two nodes, the total cost is equal to plus infinity.
S22, in each path from the source node to the destination node, determining links contained in each path, and calculating the cost of each path according to the total cost of each contained links.
In this embodiment, the link cost is the cost of the network that the link uses in the data transfer process. From the network information management library, the cost of using a certain node and the cost of using a certain link collected in the network can be obtained.
According to the routing method provided by the embodiment of the invention, the nodes and links in the network can be pruned based on the time delay characteristic under the condition of the worst network quality, and the routing is performed in a mode of integrating time delay and minimum cost, so that the routing is realized rapidly, and the complexity of the routing is reduced.
Fig. 3 shows a network topology structure diagram of an embodiment of the present invention. In fig. 3, the nodes in the network topology include: source node a and destination node E, and forwarding nodes such as node B, node C, and node D between source node a and destination node E.
In the following, in connection with the network topology in fig. 3, how to perform routing between the source node a and the destination node E in the embodiment of the present invention is described in detail.
Table 1 shows network topology and link related information in the network collected from the network in one embodiment.
Table 1 network topology and link related information
Links with direct connection relationships are shown in table 1 above, along with link delay weights, link packet loss rates, and link available bandwidth. Because the illustrated links have a direct association relationship, the link delay weight shown in table 1 takes the value of the delay between two nodes in the link.
In the embodiment of the invention, the deterministic network under the SDN architecture is a network capable of providing deterministic service assurance capability for the loaded service, wherein the deterministic service assurance capability comprises network performance indexes such as time delay, bandwidth, packet loss rate and the like.
According to the network performance index, the deterministic network under the SDN architecture can meet the performance index threshold of the user requirement under the condition of the worst network quality from end to end by setting the performance index threshold, and the performance index threshold can include: and the time delay upper limit value, the packet loss rate upper limit threshold value, the bandwidth requirement threshold value and the like of the user requirement are met.
As an example, performance indexes meeting user requirements in the embodiment of the present invention may include: the upper limit of the user demand delay is 7, the upper limit of the packet loss rate is 5, and at least 1 unit of bandwidth is required, for example, 1 unit of bandwidth is 1 megabit per second (Mbps). It should be understood that the above-mentioned performance index values are merely illustrative, and the above-mentioned performance index can be flexibly adjusted according to the requirements of the network performance in practical applications. The content is not limited in this respect.
Fig. 4 shows a flow chart of a routing method according to another embodiment of the present invention. As shown in fig. 4, in one embodiment, the routing method may include steps S31-S33.
S31, forward and reverse collection is carried out on the time delay of the links between the nodes in the network.
In step S31, forward collecting is performed on the delay, which means that the delay weight from each node to the destination node is collected; and reversely collecting the time delay, namely collecting the time delay weight from each node to the source node.
In the collecting stage of the routing method described in step S31, the topology structure of the entire network may be collected, including the available bandwidth and packet loss rate of each node and link in the network, and the worst case delay between every two nodes in the network and the delay upper limit of the user demand, and the collected information may be stored in the network information management library;
and S32, pruning the network based on time delay between nodes under the condition of the worst network quality.
In the pruning stage of the routing method described in step S32, nodes in the network that cannot meet the delay requirement may be pruned, i.e., nodes that cannot meet the delay requirement may be removed.
S33, based on the minimum cost mode, routing and finding the route of the node obtained after the network pruning.
The routing stage of the routing method described in the above step S33 may refer to the comprehensive cost and the delay weight for routing.
Fig. 5 shows a specific flow diagram of the collection of network routes in fig. 4. In fig. 5, the step S31 may specifically include S311 and S312.
S311, forward collecting is carried out on the time delay weight between the nodes under the condition of the worst network quality, and the minimum time delay weight from each node to the destination node E is obtained.
S312, reversely collecting the time delay weight between the nodes under the condition of the worst network quality, and obtaining the minimum time delay weight from each node to the source node A.
Table 2 schematically shows the minimum delay weights obtained from each node to the destination node E according to the link delay weights collected in table 1 in the worst case of the network; table 3 schematically shows the minimum delay weights obtained from each node to the destination node E based on the link delay weights collected in table 1 for the worst case of the network.
Table 2 minimum delay weight of each node to destination node E
| Node | Minimum delay weight to destination node E |
| A | 7 |
| B | 6 |
| C | 4 |
| D | 3 |
| E | 0 |
Table 3 minimum delay weight of nodes to source node a
In this embodiment, the forward direction collection and the reverse direction collection are performed on the delay under the condition that the network quality is the worst in the network, so as to be used for pruning the nodes in the network later.
Fig. 6 shows a schematic diagram of a specific flow of pruning the network in fig. 4. In fig. 6, the step S32 may specifically include S321 and S323.
S321, adding all nodes in the network into a set H, wherein the nodes in the set H, which are not traversed in the pruning stage, are stored.
S322, sequentially selecting nodes which are not traversed from the set H, calculating the sum of the minimum time delay weight from a certain node to a destination node and the minimum time delay weight from the node to a source node, marking the node as an unavailable node if the sum of the minimum time delay weights is larger than the upper time delay limit required by a user, and reserving the node and marking the node as an available node if the sum of the minimum time delay weights is smaller than or equal to the upper time delay limit required by the user.
By way of example, node A is selected from set H, meaning that A is traversed, and node A is deleted from set H. And respectively taking out the minimum time delay weight from the node A to the destination node E from the table 2 and the table 3, wherein the minimum time delay weight from the node A to the source node A is 7, and calculating to obtain the time delay 7 under the worst condition that the sum 7 of the time delay weights is less than or equal to (not more than) the user requirement, so that the node A is reserved.
S323, checking whether the set H is empty, if not, executing step S322, and if so, ending the pruning stage. As an example, node a may be deleted from the set H if it is traversed.
Table 4 shows the pruning results of the embodiments of the present invention.
TABLE 4 pruning results
As can be seen from table 4 above, after the pruning stage is completed, the D node is marked as unavailable. Nodes and links which do not meet the time delay requirement are removed in the pruning stage, and then final route finding can be conducted based on minimum cost under the condition that the time delay meets the user requirement.
In this embodiment, according to whether the sum of the time delay formed by the time delay weight from a certain node to a destination node and the time delay weight from the node to a source node is smaller than the time delay upper limit of the user requirement under the condition of the worst network quality, the nodes in the network are screened, so as to ensure that the screened nodes meet the determined time delay of the user requirement.
Fig. 7 shows a schematic flow chart of the routing in fig. 4 based on the least cost manner. As shown in fig. 7, the step S33 may specifically include S331 to S333.
S331, screening out links with available bandwidths larger than the bandwidth requirements of users.
S332, screening out links with the packet loss rate smaller than a preset packet loss rate threshold from links with the available bandwidth larger than the bandwidth requirement of the user.
In one embodiment, links with packet loss rates smaller than a preset packet loss rate threshold may be screened out first, and then links with available bandwidths larger than the bandwidth requirement of the user may be screened out from links with packet loss rates smaller than the preset packet loss rate threshold.
S333, selecting a path with the minimum cost as a routing path from a source node to a destination node from links with available bandwidths larger than the user bandwidth requirement and packet loss rates smaller than a preset packet loss rate threshold.
In the above step S333, the cost of using a certain link or using a certain node may be obtained from the network information management module, and if the node a and the node B are directly connected, the weight of the link from the node a to the node B in the path-finding stage is the sum of the cost of using the node B and the cost of using the links a to B, and the meanings of the cost of using these resources include the cost and the cost of using these resources, and so on. For ease of understanding, table 5 shows the cost of each link for the seek phase.
TABLE 5 calculation of costs for links at the seek stage
In table 5, the node cost is the cost of the second hop node in the link, i.e., the receiving node in the link. As an example, in link a→b, B is the second hop node of the link, and is also the receiving node of the link. As can be seen from fig. 5, the calculated total cost of the link is used as the weight of each link in the path-finding stage, and the path-finding calculation is performed between the source node and the target node, so as to obtain the path with the minimum cost.
In this embodiment, on the basis of satisfying the determined delay of the user demand, the bandwidth demand of the user on the link, the limit of the packet loss rate of the link, and the link cost are comprehensively considered, and the minimum cost path from the source node to the destination node, which satisfies the above conditions, is found.
Fig. 8 is a schematic diagram of a network controller according to an embodiment of the present invention.
In fig. 8, the network controller may include a node screening module 410, a cost calculation module 420, and a path selection module 430.
The node screening module 410 is configured to screen forwarding nodes between the source node and the destination node from the network according to the delay value between every two nodes collected in the network, so as to screen the forwarding nodes meeting the predetermined delay requirement.
And a cost calculation module 420, configured to calculate a cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node, and the selected forwarding nodes.
The path selection module 430 is configured to select a path with minimum cost as a routing path from the source node to the destination node.
In one embodiment, the node screening module 410 may specifically include: and the time delay weight determining unit and the minimum time delay weight calculating unit.
The time delay weight setting unit is used for setting the time delay weight between every two nodes based on the time delay value between every two nodes; the minimum delay weight calculation unit is used for calculating a forward minimum delay weight and a reverse minimum delay weight of any node in the network according to the delay weight between every two nodes, wherein the forward minimum delay weight is the minimum value of the delay weight from any node to the destination node, and the reverse minimum delay weight is the minimum value of the delay weight from any node to the source node.
In this embodiment, the node screening module 410 is specifically further configured to calculate a sum of the forward minimum delay weight and the reverse minimum delay weight, and use a node in the network where the sum of the delay weights is smaller than the preset delay upper limit value as a forwarding node that meets the preset delay requirement.
In an embodiment, the delay weight setting unit is specifically further configured to: when a direct connection link exists between every two nodes, setting a time delay weight as a time delay value between every two nodes; when no directly connected link exists between every two nodes, the time delay weight is set to be positive infinity.
In one embodiment, the delay value between every two nodes is the sum of the delay formed by the required sending delay, the link delay, the receiving delay and the queuing delay under the condition that the quality of the network is the worst when the signal is sent from one node to the other node between every two nodes.
In one embodiment, the spending calculation module 420 may also include a link screening unit and a path determination unit.
The link screening unit is used for screening each link formed by the source node, the destination node and the screened forwarding nodes to obtain links with available bandwidths greater than or equal to a preset bandwidth demand threshold and/or with packet loss rates smaller than a preset packet loss rate threshold.
In this embodiment, the cost calculation module 420 is further configured to calculate a cost for each path from the source node to the destination node based on the cost for each link formed by the forwarding node, the source node, and the destination node included in the screened links.
In one embodiment, the cost calculation module 420 may further include a link total cost calculation unit and a path cost calculation unit.
Wherein the link total cost calculation unit is configured to take, as the total cost of using each link, a sum of costs collected from the network and formed by costs of using each link and a receiving node in each link.
And the path cost calculation unit is used for determining links contained in each path from the source node to the destination node, and calculating the cost of each path according to the total cost of each contained link.
In this embodiment, the path selection module 430 is further configured to select a path that costs least as a routing path from the source node to the destination node.
In one embodiment, when there is a directly connected link between every two nodes, the total cost is equal to the sum of the cost of the link between every two nodes and the cost of the receiving node in the link; when there is no direct-connected link between every two nodes, the total cost is equal to plus infinity.
According to the routing device provided by the embodiment of the invention, on the basis of guaranteeing that nodes and links in a network meet the upper limit of time delay required by users, the cost of the links and the nodes is comprehensively considered, and the path selection with the minimum cost ensured by the end-to-end time delay is realized.
It should be clear that the invention is not limited to the specific arrangements and processes described in the foregoing embodiments and shown in the drawings. For convenience and brevity of description, detailed descriptions of known methods are omitted herein, and specific working processes of the systems, modules and units described above may refer to corresponding processes in the foregoing method embodiments, which are not repeated herein.
Fig. 9 is a block diagram illustrating an exemplary hardware architecture of a computing device capable of implementing routing methods and apparatus according to embodiments of the present invention.
As shown in fig. 9, the computing device 900 includes an input device 901, an input interface 902, a central processor 903, a memory 904, an output interface 905, and an output device 906. The input interface 902, the central processor 903, the memory 904, and the output interface 905 are connected to each other through a bus 910, and the input device 901 and the output device 906 are connected to the bus 910 through the input interface 902 and the output interface 905, respectively, and further connected to other components of the computing device 900.
Specifically, the input device 901 receives input information from outside (e.g., a network information management library), and transmits the input information to the central processor 903 through the input interface 902; the central processor 903 processes the input information based on computer-executable instructions stored in the memory 904 to generate output information, temporarily or permanently stores the output information in the memory 904, and then transmits the output information to the output device 906 through the output interface 905; output device 906 outputs the output information to the outside of computing device 900 for use by a user.
In one embodiment, the computing device 900 shown in fig. 9 may be implemented as a routing system that may include: a memory configured to store a program; and a processor configured to run a program stored in the memory to perform the routing method described in the above embodiment.
In one embodiment, the routing system has the same or equivalent structure as the route calculation module 11 in fig. 1.
The processes described above with reference to flowcharts may be implemented as computer software programs according to embodiments of the present invention. For example, embodiments of the invention include a computer program product comprising a computer program tangibly embodied on a machine-readable medium, the computer program comprising program code for performing the method shown in the flowchart. In such embodiments, the computer program may be downloaded and installed from a network, and/or installed from a removable storage medium.
Those of ordinary skill in the art will appreciate that all or some of the steps, systems, functional modules/units in the apparatus, and methods disclosed above may be implemented as software, firmware, hardware, and suitable combinations thereof. In a hardware implementation, the division between the functional modules/units mentioned in the above description does not necessarily correspond to the division of physical components; for example, one physical component may have multiple functions, or one function or step may be performed cooperatively by several physical components. Some or all of the physical components may be implemented as software executed by a processor, such as a central processing unit, digital signal processor, or microprocessor, or as hardware, or as an integrated circuit, such as an application specific integrated circuit. Such software may be distributed on computer readable media, which may include computer storage media (or non-transitory media) and communication media (or transitory media). The term computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data, as known to those skilled in the art. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital Versatile Disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer. Furthermore, as is well known to those of ordinary skill in the art, communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media.
It is to be understood that the above embodiments are merely illustrative of the application of the principles of the present invention, but not in limitation thereof. Various modifications and improvements may be made by those skilled in the art without departing from the spirit and substance of the invention, and are also considered to be within the scope of the invention.
Claims (9)
1. A routing method, comprising:
according to the time delay value between every two nodes collected in the network, the forwarding nodes between the source node and the destination node are screened from the network so as to screen the forwarding nodes meeting the preset time delay requirement;
calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node and the screened forwarding nodes;
selecting a path with the least cost as a routing path from the source node to the destination node;
wherein the filtering, according to the delay value between every two nodes collected in the network, the forwarding node between the source node and the destination node from the network to filter the forwarding node meeting the predetermined delay requirement includes:
setting a time delay weight between every two nodes based on the time delay value between every two nodes;
according to the time delay weight between every two nodes, calculating a forward minimum time delay weight and a reverse minimum time delay weight of any node in the network, wherein the forward minimum time delay weight is the minimum value of the time delay weight from any node to the target node, and the reverse minimum time delay weight is the minimum value of the time delay weight from any node to the source node;
and calculating the sum of the time delay weights of the forward minimum time delay weight and the reverse minimum time delay weight, and taking the node in the network, of which the sum of the time delay weights is smaller than a preset time delay upper limit value, as a forwarding node meeting the preset time delay requirement.
2. The method of claim 1, wherein the setting the latency weight between each two nodes based on the latency value between each two nodes comprises:
when a direct connection link exists between every two nodes, setting the time delay weight as the time delay value between every two nodes;
and when no directly connected link exists between every two nodes, setting the time delay weight value to be positive infinity.
3. The method of claim 1, wherein,
the delay value between every two nodes is the sum of the delay formed by the required sending delay, the link delay, the receiving delay and the queuing delay when the quality of the network meets the preset condition of the worst network quality.
4. The method of claim 1, wherein the calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node, and the screened forwarding nodes comprises:
screening each link formed by the source node, the destination node and the screened forwarding nodes to obtain links with available bandwidths larger than or equal to a preset bandwidth demand threshold and/or with packet loss rate smaller than a preset packet loss rate threshold;
and calculating the cost of each path from the source node to the destination node according to the cost of each link formed by the forwarding node, the source node and the destination node contained in the screened links.
5. The method of claim 1 or 4, wherein the calculating the cost of each path from the source node to the destination node based on the cost of each link formed by the source node, the destination node, and the screened forwarding nodes comprises:
taking the sum of the costs of said each link collected from said network and the costs of the receiving nodes in said each link as the total cost of using said each link;
and determining links contained in each path from the source node to the destination node, and calculating the cost of each path according to the total cost of each contained link.
6. A network controller, comprising:
the node screening module is used for screening forwarding nodes between a source node and a destination node from the network according to the delay value between every two nodes collected in the network so as to screen the forwarding nodes meeting the preset delay requirement;
a cost calculation module, configured to calculate a cost of each path from the source node to the destination node based on a cost of each link formed by the source node, the destination node, and the screened forwarding nodes;
a path selection module, configured to select a path with minimum cost as a routing path from the source node to the destination node;
the node screening module comprises a time delay weight determining unit and a minimum time delay weight calculating unit;
the delay weight setting unit is used for setting the delay weight between every two nodes based on the delay value between every two nodes;
the minimum delay weight calculation unit is configured to calculate a forward minimum delay weight and a reverse minimum delay weight of any node in the network according to the delay weight between every two nodes, where the forward minimum delay weight is a minimum value of delay weights from the any node to the destination node, and the reverse minimum delay weight is a minimum value of delay weights from the any node to the source node;
the node screening module is further configured to calculate a sum of the forward minimum delay weight and the reverse minimum delay weight, and use a node in the network, where the sum of the delay weights is smaller than a preset delay upper limit value, as a forwarding node that meets a preset delay requirement.
7. The network controller of claim 6, wherein the spending calculation module further comprises:
the link screening unit is used for screening each link formed by the source node, the destination node and the screened forwarding nodes to obtain links with available bandwidths larger than or equal to a preset bandwidth demand threshold and/or with packet loss rate smaller than a preset packet loss rate threshold;
the cost calculation module is further configured to calculate a cost of each path from the source node to the destination node according to a cost of each link formed by the forwarding node, the source node, and the destination node included in the screened links.
8. A routing system comprising a memory and a processor;
the memory is used for storing executable program codes;
the processor is configured to read executable program code stored in the memory to perform the routing method of any one of claims 1 to 5.
9. A computer readable storage medium comprising instructions which, when run on a computer, cause the computer to perform the routing method of any of claims 1 to 5.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911077082.9A CN112769696B (en) | 2019-11-06 | 2019-11-06 | Routing method, network controller, system and storage medium |
| PCT/CN2020/126157 WO2021088801A1 (en) | 2019-11-06 | 2020-11-03 | Routing method, network controller, system, and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911077082.9A CN112769696B (en) | 2019-11-06 | 2019-11-06 | Routing method, network controller, system and storage medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112769696A CN112769696A (en) | 2021-05-07 |
| CN112769696B true CN112769696B (en) | 2023-09-26 |
Family
ID=75692742
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201911077082.9A Active CN112769696B (en) | 2019-11-06 | 2019-11-06 | Routing method, network controller, system and storage medium |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN112769696B (en) |
| WO (1) | WO2021088801A1 (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114024975B (en) * | 2021-11-26 | 2024-11-15 | 中国电力科学研究院有限公司 | Service load balancing path calculation method, system, device and storage medium |
| CN114697363A (en) * | 2022-03-31 | 2022-07-01 | 广东美的厨房电器制造有限公司 | Network system and its control method, control device, and readable storage medium |
| CN115086202B (en) * | 2022-04-14 | 2023-06-20 | 安世亚太科技股份有限公司 | Time delay analysis method and system based on network digital twin |
| CN115987876B (en) * | 2022-12-22 | 2025-08-12 | 中盈优创资讯科技有限公司 | Method and device for opening computing capacity of cloud private network |
| CN117278466B (en) * | 2023-09-14 | 2024-08-20 | 清华大学 | Candidate path selection method for fault-tolerant traffic engineering scene |
| CN117978719B (en) * | 2024-03-13 | 2024-08-27 | 武汉软件工程职业学院(武汉开放大学) | Minimum cost difference routing method and device for guaranteeing service quality |
Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1731762A (en) * | 2005-08-05 | 2006-02-08 | 武汉理工大学 | A Method of Multicast Routing Based on Steiner's QoS Constraint |
| CN101001102A (en) * | 2007-01-10 | 2007-07-18 | 北京航空航天大学 | Route device and method for raising service quality of space information network |
| CN101267450A (en) * | 2008-03-18 | 2008-09-17 | 上海大学 | Application Layer Multicast Routing Method for Distributed Networks Based on Network Coding |
| WO2010118578A1 (en) * | 2009-04-16 | 2010-10-21 | 华为技术有限公司 | Route method, equipment and system |
| CN104270283A (en) * | 2014-09-15 | 2015-01-07 | 电子科技大学 | A Network Topology Estimation Method Based on Higher Order Cumulants |
| CN107046501A (en) * | 2017-05-16 | 2017-08-15 | 北京邮电大学 | Path determination method, device, computer equipment and storage medium for SDN |
| CN107070794A (en) * | 2016-12-08 | 2017-08-18 | 航天东方红卫星有限公司 | A kind of low rail information network optimal network benefit delay constraint method for routing |
| CN108521375A (en) * | 2018-04-17 | 2018-09-11 | 中国矿业大学 | A method for transmission and scheduling of network multi-service traffic QoS based on SDN |
| CN108881009A (en) * | 2018-06-21 | 2018-11-23 | 北京航空航天大学 | Based on the delay constraint method for routing and device for facing sky Information Network |
| WO2019011338A1 (en) * | 2017-07-13 | 2019-01-17 | 华为技术有限公司 | Method for determining shortest path and controller |
| CN110139319A (en) * | 2019-05-25 | 2019-08-16 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | High dynamic time-delay network propagation delay time minimizes method for routing |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7072304B2 (en) * | 2002-02-27 | 2006-07-04 | Nortel Networks Limited | Network path selection based on bandwidth |
| KR100912820B1 (en) * | 2007-11-01 | 2009-08-18 | 한국전자통신연구원 | Multipath Routing Method in Wireless Sensor Networks |
| CN101715225B (en) * | 2009-11-20 | 2012-12-05 | 西安电子科技大学 | Routing method of self-adapting self-organized network in cognitive network |
| KR102233371B1 (en) * | 2014-06-24 | 2021-03-29 | 삼성전자주식회사 | Method and apparatus for relaying in multicast network |
| CN107547393B (en) * | 2016-06-29 | 2021-06-01 | 华为技术有限公司 | Method and network device for calculating forwarding path |
-
2019
- 2019-11-06 CN CN201911077082.9A patent/CN112769696B/en active Active
-
2020
- 2020-11-03 WO PCT/CN2020/126157 patent/WO2021088801A1/en active Application Filing
Patent Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1731762A (en) * | 2005-08-05 | 2006-02-08 | 武汉理工大学 | A Method of Multicast Routing Based on Steiner's QoS Constraint |
| CN101001102A (en) * | 2007-01-10 | 2007-07-18 | 北京航空航天大学 | Route device and method for raising service quality of space information network |
| CN101267450A (en) * | 2008-03-18 | 2008-09-17 | 上海大学 | Application Layer Multicast Routing Method for Distributed Networks Based on Network Coding |
| WO2010118578A1 (en) * | 2009-04-16 | 2010-10-21 | 华为技术有限公司 | Route method, equipment and system |
| CN104270283A (en) * | 2014-09-15 | 2015-01-07 | 电子科技大学 | A Network Topology Estimation Method Based on Higher Order Cumulants |
| CN107070794A (en) * | 2016-12-08 | 2017-08-18 | 航天东方红卫星有限公司 | A kind of low rail information network optimal network benefit delay constraint method for routing |
| CN107046501A (en) * | 2017-05-16 | 2017-08-15 | 北京邮电大学 | Path determination method, device, computer equipment and storage medium for SDN |
| WO2019011338A1 (en) * | 2017-07-13 | 2019-01-17 | 华为技术有限公司 | Method for determining shortest path and controller |
| CN108521375A (en) * | 2018-04-17 | 2018-09-11 | 中国矿业大学 | A method for transmission and scheduling of network multi-service traffic QoS based on SDN |
| CN108881009A (en) * | 2018-06-21 | 2018-11-23 | 北京航空航天大学 | Based on the delay constraint method for routing and device for facing sky Information Network |
| CN110139319A (en) * | 2019-05-25 | 2019-08-16 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | High dynamic time-delay network propagation delay time minimizes method for routing |
Non-Patent Citations (2)
| Title |
|---|
| Liquan Chen ; Dong Yang ; Zhezhuang Xu ; Cailian Chen.An adaptive routing strategy for cluster-based wireless sensor networks.《The 27th Chinese Control and Decision Conference (2015 CCDC)》.2015,全文. * |
| 考虑排队时延的系统保护通信网络路由选择算法;刘川;黄在朝;陶静;贾惠彬;;电信科学(第10期);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112769696A (en) | 2021-05-07 |
| WO2021088801A1 (en) | 2021-05-14 |
| WO2021088801A9 (en) | 2021-10-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112769696B (en) | Routing method, network controller, system and storage medium | |
| US7346056B2 (en) | Optimizing path selection for multiple service classes in a network | |
| KR101390095B1 (en) | Dynamic route branching system, dynamic route branching method, and non-transitory computer-readable storage medium | |
| US8897141B2 (en) | Network system and routing method | |
| JP5600215B2 (en) | Method and system for determining a route in an LEO satellite network using bandwidth and priority awareness and adaptive routing | |
| US6778531B1 (en) | Multicast routing with service-level guarantees between ingress egress-points in a packet network | |
| US8081566B1 (en) | Method and apparatus for indicating congestion in a source routed network | |
| CN100596102C (en) | Method for establishing label switched path of minimized path preemption cost | |
| CN112313910A (en) | Multipathing system and method for data center centric metro network | |
| US20120030150A1 (en) | Hybrid Learning Component for Link State Routing Protocols | |
| US8547850B2 (en) | Transport control server, network system and aggregated path setting method | |
| US11876705B2 (en) | Methods and systems for adaptive stochastic-based load balancing | |
| US7496039B2 (en) | Delay guarantee path setting system | |
| CN116055415B (en) | Data packet transmission control method and device | |
| US20210306267A1 (en) | Optimized network latency using in-band telemetry | |
| CA2410137C (en) | Optical dynamic burst switch | |
| CN109257282B (en) | Data transmission method and device | |
| CN116319549A (en) | Distributed flow scheduling method and device | |
| US20040233850A1 (en) | Device and a method for determining routing paths in a communication network in the presence of selection attributes | |
| Iosifidis et al. | The impact of storage capacity on end-to-end delay in time varying networks | |
| WO2024001210A1 (en) | Path calculation method, controller, and computer readable storage medium | |
| US20040190490A1 (en) | Device for determining switching paths in a label switched communication network in the presence of selection attributes | |
| CN118945116A (en) | A method and system for implementing load balancing in a data center network | |
| CN101753417A (en) | Method for calculating and determining routing, path calculating unit and system for determining routing | |
| US11757762B2 (en) | Service operation method and device, and storage medium and electronic device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |