Search

CN-115277432-B - Path determination method and device

CN115277432BCN 115277432 BCN115277432 BCN 115277432BCN-115277432-B

Abstract

The application provides a path determining method and a path determining device. The method is applied to an SDN controller, and comprises the steps of obtaining a corresponding network topology graph when a forwarding path of target service flow is required to be determined, calculating link quality evaluation factors of a corresponding forward link and a corresponding reverse link according to current delay, current jitter rate and current packet loss rate of the two links for each pair of adjacent network nodes in the network topology graph, calculating flow evaluation factors of the two links according to current bandwidth occupancy rate and flow priority value of the two links, calculating link cost evaluation factors of the two links according to current delay, current jitter rate, current packet loss rate, link cost value and link attribute information of the two links, calculating path weight values between the pair of adjacent network nodes according to the evaluation factors, and determining the corresponding forward forwarding path and the corresponding reverse forwarding path by using a Dijkstra algorithm. The application can improve the user experience.

Inventors

  • LI YUEGUANG

Assignees

  • 新华三技术有限公司

Dates

Publication Date
20260508
Application Date
20220628

Claims (10)

  1. 1. A method of path determination, wherein the method is applied to an SDN controller, the method comprising: when a forwarding path of a target service flow is required to be determined, acquiring a network topology diagram of a target network managed by the SDN controller; Calculating link quality assessment factors of a forward link and a reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate and the current packet loss rate of the forward link and the reverse link between the pair of adjacent network nodes aiming at each pair of adjacent network nodes in the obtained network topology map; Calculating traffic assessment factors of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current bandwidth occupancy rates and traffic priority values of the forward link and the reverse link between the pair of adjacent network nodes; calculating link overhead evaluation factors of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current time delay, the current jitter rate, the current packet loss rate, the link overhead value and the link attribute information of the forward link and the reverse link between the pair of adjacent network nodes; calculating path weight values between the pair of adjacent network nodes according to the calculated link quality evaluation factors, traffic evaluation factors and link overhead evaluation factors of the forward link and the reverse link between the pair of adjacent network nodes; determining the shortest path from the source node of the target traffic to the destination node of the target traffic in the network topology by using Dijkstra algorithm based on the calculated path weight values between all adjacent network nodes; and determining the determined path as a forward forwarding path of the target traffic, and determining a reverse path corresponding to the determined path as a reverse forwarding path of the target traffic.
  2. 2. The method of claim 1, wherein the link quality assessment factors for the forward link and the reverse link between the pair of adjacent network nodes are calculated by: The link quality assessment factor for the forward link between the pair of adjacent network nodes is calculated by the following equation: formula one, Q l ＝w 1 (1-aD l )+w 2 (1-bJ l )+w 3 (1-L l ); Wherein Q l is a link quality assessment factor for the forward link between the pair of adjacent network nodes; d l is the current delay of the forward link between the pair of adjacent network nodes acquired by the SDN controller; J l is the current jitter rate of the forward link between the pair of adjacent network nodes obtained by the SDN controller; L l is the current packet loss rate of the forward link between the pair of adjacent network nodes acquired by the SDN controller; a=1/1600,b=1/1600; When D l is more than 1/a, w 1 =0, and when D l is less than or equal to 1/a, w 1 =0.2; W 2 =0 when J l >1/b, w 2 ＝0.2;w 3 =0.6 when J l is less than or equal to 1/b; The link quality assessment factor for the reverse link between the pair of adjacent network nodes is calculated by equation two: Formula II, Q m ＝w 1 (1-aD m )+w 2 (1-bJ m )+w 3 (1-L m ); Wherein Q m is a link quality assessment factor for the reverse link between the pair of adjacent network nodes; d m is the current delay of the reverse link between the pair of adjacent network nodes acquired by the SDN controller; J m is the current jitter rate of the reverse link between the pair of adjacent network nodes obtained by the SDN controller; L m is the current packet loss rate of the reverse link between the pair of adjacent network nodes acquired by the SDN controller; a=1/1600,b=1/1600; When D m is more than 1/a, w 1 =0, and when D m is less than or equal to 1/a, w 1 =0.2; When J m is more than 1/b, w 2 =0, and when J m is less than or equal to 1/b, w 2 ＝0.2;w 3 =0.6.
  3. 3. The method of claim 2, wherein the traffic assessment factors for the forward link and the reverse link between the pair of adjacent network nodes are calculated by: The traffic assessment factor for the forward link between the pair of adjacent network nodes is calculated by the following equation three: Formula three, F s ＝w p B s ; Wherein F s is a traffic assessment factor for the forward link between the pair of adjacent network nodes; w p is a traffic priority value of a forward link between the pair of adjacent network nodes acquired by the SDN controller, wherein 0<w p is less than or equal to 1; B s is the bandwidth occupancy of the forward link between the pair of adjacent network nodes calculated by the SDN controller, B s =1 at the beginning and B s =the current bandwidth/the set minimum bandwidth of the forward link between the pair of adjacent network nodes at the non-beginning; The traffic assessment factor for the reverse link between the pair of adjacent network nodes is calculated by the following equation four: f r ＝w q B r ; Wherein F r is a traffic assessment factor for the reverse link between the pair of adjacent network nodes; w q is a traffic priority value of a reverse link between the pair of adjacent network nodes acquired by the SDN controller, 0<w q is less than or equal to 1; B r is the bandwidth occupancy of the reverse link between the pair of adjacent network nodes calculated by the SDN controller, B r =1 at the beginning and B r =the current bandwidth/the set minimum bandwidth of the reverse link between the pair of adjacent network nodes at the non-beginning.
  4. 4. A method according to claim 3, characterized in that the link overhead evaluation factors for the forward link and the reverse link between the pair of adjacent network nodes are calculated by: the link overhead evaluation factor for the forward link between the pair of adjacent network nodes is calculated by the following equation five: Formula five: Wherein C l is a link overhead evaluation factor for the forward link between the pair of adjacent network nodes; D T is a set delay threshold, J T is a set jitter rate threshold, and L T is a set delay threshold; Cost l is a link overhead value of a forward link between the pair of adjacent network nodes acquired by the SDN controller; l1 is an affinity attribute color of a path corresponding to a forward link between the pair of adjacent network nodes, which is acquired by the SDN controller; l2 is the evasive attribute color of the path corresponding to the forward link between the pair of adjacent network nodes obtained by the SDN controller; color is a set affinity attribute Color set, and Void is a set evasion attribute Color set; V color is the set affinity attribute coefficient, and V void is the set evasion attribute coefficient; l1 epsilon Color represents that at least one affinity attribute Color of a path corresponding to a forward link between the pair of adjacent network nodes obtained by the SDN controller is in a set affinity attribute Color set; all affinity attribute colors representing paths corresponding to forward links between the pair of adjacent network nodes acquired by the SDN controller are not in a set affinity attribute color set; l2 epsilon Void represents that at least one evasion attribute color of a path corresponding to a forward link between the pair of adjacent network nodes obtained by the SDN controller is in a set evasion attribute color set; All the evasion attribute colors representing paths corresponding to forward links between the pair of adjacent network nodes obtained by the SDN controller are not in the set evasion attribute color set; the link overhead evaluation factor for the reverse link between the pair of adjacent network nodes is calculated by equation six: Formula six: Wherein C m is a link overhead evaluation factor for the reverse link between the pair of adjacent network nodes; The values of D T 、J T and L T are the same as those of D T 、J T and L T in the fifth formula; cost m is a link overhead value of a reverse link between the pair of adjacent network nodes acquired by the SDN controller; l3 is the affinity attribute color of the path corresponding to the reverse link between the pair of adjacent network nodes obtained by the SDN controller; l4 is the evasive attribute color of the path corresponding to the reverse link between the pair of adjacent network nodes obtained by the SDN controller; color, void, V color and V void have the same meaning as Color, void, V color and V void in equation five; l3 e Color represents that at least one affinity attribute Color of a path corresponding to a reverse link between the pair of adjacent network nodes obtained by the SDN controller is in a set affinity attribute Color set; all affinity attribute colors representing paths corresponding to reverse links between the pair of adjacent network nodes acquired by the SDN controller are not in a set affinity attribute color set; l4 epsilon Void represents that at least one evasion attribute color of a path corresponding to a reverse link between the pair of adjacent network nodes obtained by the SDN controller is in a set evasion attribute color set; All the evasion attribute colors representing the paths corresponding to the reverse links between the pair of adjacent network nodes obtained by the SDN controller are not in the set evasion attribute color set; v color ＜V void ,V color ＞nCost l , and V color ＞n Cost m , n is a positive integer greater than 1.
  5. 5. The method of claim 4, wherein the path weight value between the pair of adjacent network nodes is calculated by: the path weight value between the pair of adjacent network nodes is calculated by the following formula seven: Formula seven: wherein M is a path weight value between the pair of adjacent network nodes; f s is a traffic assessment factor for the forward link between the pair of adjacent network nodes; c l is a link overhead evaluation factor of the forward link between the pair of adjacent network nodes; f r is a traffic assessment factor for the reverse link between the pair of adjacent network nodes; c m is a link overhead evaluation factor for the reverse link between the pair of adjacent network nodes; Q l is a link quality assessment factor for the forward link between the pair of adjacent network nodes; Q m is a link quality assessment factor for the reverse link between the pair of adjacent network nodes; c=0.2。
  6. 6. a path determining apparatus, wherein the apparatus is applied to an SDN controller, the apparatus comprising: An obtaining module, configured to obtain a network topology map of a target network managed by the SDN controller when a forwarding path of a target traffic needs to be determined; a first calculation module, configured to calculate, for each pair of adjacent network nodes in the obtained network topology graph, a link quality evaluation factor of a forward link and a reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate, and the current packet loss rate of the forward link and the reverse link between the pair of adjacent network nodes; a second calculation module, configured to calculate a traffic evaluation factor of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current bandwidth occupancy and traffic priority value of the forward link and the reverse link between the pair of adjacent network nodes; a third calculation module, configured to calculate a link overhead evaluation factor of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate, the current packet loss rate, the link overhead value, and the link attribute information of the forward link and the reverse link between the pair of adjacent network nodes; a fourth calculation module, configured to calculate a path weight value between the pair of adjacent network nodes according to the calculated link quality assessment factors, the traffic assessment factors, and the link overhead assessment factors of the forward link and the reverse link between the pair of adjacent network nodes; A first determining module, configured to determine, based on the calculated path weight values between all adjacent network nodes, a shortest path from a source node of the target traffic to a destination node of the target traffic in the network topology map by using Dijkstra algorithm; And the second determining module is used for determining the determined path as the forward forwarding path of the target service flow and determining the reverse path corresponding to the determined path as the reverse forwarding path of the target service flow.
  7. 7. The apparatus according to claim 6, wherein the first calculation module is configured to calculate the link quality assessment factors for the forward link and the reverse link between the pair of adjacent network nodes by: The link quality assessment factor for the forward link between the pair of adjacent network nodes is calculated by the following equation: formula one, Q l ＝w 1 (1-aD l )+w 2 (1-bJ l )+w 3 (1-L l ); Wherein Q l is a link quality assessment factor for the forward link between the pair of adjacent network nodes; d l is the current delay of the forward link between the pair of adjacent network nodes acquired by the SDN controller; J l is the current jitter rate of the forward link between the pair of adjacent network nodes obtained by the SDN controller; L l is the current packet loss rate of the forward link between the pair of adjacent network nodes acquired by the SDN controller; a=1/1600,b=1/1600; When D l is more than 1/a, w 1 =0, and when D l is less than or equal to 1/a, w 1 =0.2; W 2 =0 when J l >1/b, w 2 ＝0.2;w 3 =0.6 when J l is less than or equal to 1/b; The link quality assessment factor for the reverse link between the pair of adjacent network nodes is calculated by equation two: Formula II, Q m ＝w 1 (1-aD m )+w 2 (1-bJ m )+w 3 (1-L m ); Wherein Q m is a link quality assessment factor for the reverse link between the pair of adjacent network nodes; d m is the current delay of the reverse link between the pair of adjacent network nodes acquired by the SDN controller; J m is the current jitter rate of the reverse link between the pair of adjacent network nodes obtained by the SDN controller; L m is the current packet loss rate of the reverse link between the pair of adjacent network nodes acquired by the SDN controller; a=1/1600,b=1/1600; When D m is more than 1/a, w 1 =0, and when D m is less than or equal to 1/a, w 1 =0.2; When J m is more than 1/b, w 2 =0, and when J m is less than or equal to 1/b, w 2 ＝0.2;w 3 =0.6.
  8. 8. The apparatus according to claim 7, wherein the second calculation module is configured to calculate the traffic assessment factors for the forward link and the reverse link between the pair of adjacent network nodes by: The traffic assessment factor for the forward link between the pair of adjacent network nodes is calculated by the following equation three: Formula three, F s ＝w p B s ; Wherein F s is a traffic assessment factor for the forward link between the pair of adjacent network nodes; w p is a traffic priority value of a forward link between the pair of adjacent network nodes acquired by the SDN controller, wherein 0<w p is less than or equal to 1; B s is the bandwidth occupancy of the forward link between the pair of adjacent network nodes calculated by the SDN controller, B s =1 at the beginning and B s =the current bandwidth/the set minimum bandwidth of the forward link between the pair of adjacent network nodes at the non-beginning; The traffic assessment factor for the reverse link between the pair of adjacent network nodes is calculated by the following equation four: f r ＝w q B r ; Wherein F r is a traffic assessment factor for the reverse link between the pair of adjacent network nodes; w q is a traffic priority value of a reverse link between the pair of adjacent network nodes acquired by the SDN controller, 0<w q is less than or equal to 1; B r is the bandwidth occupancy of the reverse link between the pair of adjacent network nodes calculated by the SDN controller, B r =1 at the beginning and B r =the current bandwidth/the set minimum bandwidth of the reverse link between the pair of adjacent network nodes at the non-beginning.
  9. 9. The apparatus according to claim 8, wherein the third calculation module is configured to calculate the link overhead evaluation factors for the forward link and the reverse link between the pair of adjacent network nodes by: the link overhead evaluation factor for the forward link between the pair of adjacent network nodes is calculated by the following equation five: Formula five: Wherein C l is a link overhead evaluation factor for the forward link between the pair of adjacent network nodes; D T is a set delay threshold, J T is a set jitter rate threshold, and L T is a set delay threshold; Cost l is a link overhead value of a forward link between the pair of adjacent network nodes acquired by the SDN controller; l1 is an affinity attribute color of a path corresponding to a forward link between the pair of adjacent network nodes, which is acquired by the SDN controller; l2 is the evasive attribute color of the path corresponding to the forward link between the pair of adjacent network nodes obtained by the SDN controller; color is a set affinity attribute Color set, and Void is a set evasion attribute Color set; V color is the set affinity attribute coefficient, and V void is the set evasion attribute coefficient; l1 epsilon Color represents that at least one affinity attribute Color of a path corresponding to a forward link between the pair of adjacent network nodes obtained by the SDN controller is in a set affinity attribute Color set; all affinity attribute colors representing paths corresponding to forward links between the pair of adjacent network nodes acquired by the SDN controller are not in a set affinity attribute color set; l2 epsilon Void represents that at least one evasion attribute color of a path corresponding to a forward link between the pair of adjacent network nodes obtained by the SDN controller is in a set evasion attribute color set; All the evasion attribute colors representing paths corresponding to forward links between the pair of adjacent network nodes obtained by the SDN controller are not in the set evasion attribute color set; the link overhead evaluation factor for the reverse link between the pair of adjacent network nodes is calculated by equation six: Formula six: Wherein C m is a link overhead evaluation factor for the reverse link between the pair of adjacent network nodes; The values of D T 、J T and L T are the same as those of D T 、J T and L T in the fifth formula; cost m is a link overhead value of a reverse link between the pair of adjacent network nodes acquired by the SDN controller; l3 is the affinity attribute color of the path corresponding to the reverse link between the pair of adjacent network nodes obtained by the SDN controller; l4 is the evasive attribute color of the path corresponding to the reverse link between the pair of adjacent network nodes obtained by the SDN controller; color, void, V color and V void have the same meaning as Color, void, V color and V void in equation five; l3 e Color represents that at least one affinity attribute Color of a path corresponding to a reverse link between the pair of adjacent network nodes obtained by the SDN controller is in a set affinity attribute Color set; all affinity attribute colors representing paths corresponding to reverse links between the pair of adjacent network nodes acquired by the SDN controller are not in a set affinity attribute color set; l4 epsilon Void represents that at least one evasion attribute color of a path corresponding to a reverse link between the pair of adjacent network nodes obtained by the SDN controller is in a set evasion attribute color set; All the evasion attribute colors representing the paths corresponding to the reverse links between the pair of adjacent network nodes obtained by the SDN controller are not in the set evasion attribute color set; v color ＜V void ,V color ＞5Cost l , and V color ＞5Cost m .
  10. 10. The apparatus according to claim 9, wherein the fourth calculation module is configured to calculate the path weight value between the pair of adjacent network nodes by: the path weight value between the pair of adjacent network nodes is calculated by the following formula seven: Formula seven: wherein M is a path weight value between the pair of adjacent network nodes; f s is a traffic assessment factor for the forward link between the pair of adjacent network nodes; c l is a link overhead evaluation factor of the forward link between the pair of adjacent network nodes; f r is a traffic assessment factor for the reverse link between the pair of adjacent network nodes; c m is a link overhead evaluation factor for the reverse link between the pair of adjacent network nodes; Q l is a link quality assessment factor for the forward link between the pair of adjacent network nodes; Q m is a link quality assessment factor for the reverse link between the pair of adjacent network nodes; c=0.2。

Description

Path determination method and device Technical Field The present application relates to the field of communications technologies, and in particular, to a path determining method and apparatus. Background A software defined network (Software Defined Network, SDN) is a new network innovation architecture that enables flexible control of network traffic by separating the control plane and the data plane. Under a certain network scenario, some users may need to ensure both bandwidth and quality of service and that forward forwarding paths and reverse forwarding paths of related traffic are consistent by the SDN controller, so how to determine forwarding paths meeting these requirements is a problem that needs to be solved currently. Disclosure of Invention In order to overcome the problems in the related art, the application provides a path determining method and a path determining device. According to a first aspect of an embodiment of the present application, there is provided a path determining method, the method being applied to an SDN controller, the method including: when a forwarding path of a target service flow is required to be determined, acquiring a network topology diagram of a target network managed by the SDN controller; Calculating link quality assessment factors of a forward link and a reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate and the current packet loss rate of the forward link and the reverse link between the pair of adjacent network nodes aiming at each pair of adjacent network nodes in the obtained network topology map; Calculating traffic assessment factors of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current bandwidth occupancy rates and traffic priority values of the forward link and the reverse link between the pair of adjacent network nodes; calculating link overhead evaluation factors of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current time delay, the current jitter rate, the current packet loss rate, the link overhead value and the link attribute information of the forward link and the reverse link between the pair of adjacent network nodes; calculating path weight values between the pair of adjacent network nodes according to the calculated link quality evaluation factors, traffic evaluation factors and link overhead evaluation factors of the forward link and the reverse link between the pair of adjacent network nodes; determining a shortest path from a source node of the target traffic to a destination node of the target traffic in the network topology using a Dijkstra algorithm based on the calculated path weight values between all adjacent network nodes; and determining the determined path as a forward forwarding path of the target traffic, and determining a reverse path corresponding to the determined path as a reverse forwarding path of the target traffic. According to a second aspect of an embodiment of the present application, there is provided a path determining apparatus, the apparatus being applied to an SDN controller, the apparatus comprising: An obtaining module, configured to obtain a network topology map of a target network managed by the SDN controller when a forwarding path of a target traffic needs to be determined; a first calculation module, configured to calculate, for each pair of adjacent network nodes in the obtained network topology graph, a link quality evaluation factor of a forward link and a reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate, and the current packet loss rate of the forward link and the reverse link between the pair of adjacent network nodes; a second calculation module, configured to calculate a traffic evaluation factor of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current bandwidth occupancy and traffic priority value of the forward link and the reverse link between the pair of adjacent network nodes; a third calculation module, configured to calculate a link overhead evaluation factor of the forward link and the reverse link between the pair of adjacent network nodes according to the obtained current delay, the current jitter rate, the current packet loss rate, the link overhead value, and the link attribute information of the forward link and the reverse link between the pair of adjacent network nodes; a fourth calculation module, configured to calculate a path weight value between the pair of adjacent network nodes according to the calculated link quality assessment factors, the traffic assessment factors, and the link overhead assessment factors of the forward link and the reverse link between the pair of adjacent network nodes; A first determining module, configured to determine, based on the