CN106878170B - Method and device for determining forwarding path - Google Patents
Method and device for determining forwarding path Download PDFInfo
- Publication number
- CN106878170B CN106878170B CN201611249143.1A CN201611249143A CN106878170B CN 106878170 B CN106878170 B CN 106878170B CN 201611249143 A CN201611249143 A CN 201611249143A CN 106878170 B CN106878170 B CN 106878170B
- Authority
- CN
- China
- Prior art keywords
- node
- path
- nodes
- determined
- delay
- 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 51
- 230000001934 delay Effects 0.000 claims description 23
- 238000004364 calculation method Methods 0.000 abstract description 10
- 238000010586 diagram Methods 0.000 description 9
- 230000005540 biological transmission Effects 0.000 description 3
- 230000006855 networking Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 239000013307 optical fiber Substances 0.000 description 1
- 230000000750 progressive effect Effects 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Images
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
- 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 present invention discloses a method and device for determining a forwarding path. In the process of determining two of the nodes according to multiple nodes, that is, the forwarding path from a first node to a second node, the multiple nodes can be pre-obtained. In order to identify the internal delay of the congestion situation, when calculating the to-be-determined path according to the shortest path algorithm, the total delay of the to-be-determined path not only includes the link delay, but also further includes the internal delay of each node in the to-be-determined path. delay, the forwarding path from the first node to the second node determined from this will be the minimum total delay path after considering the internal delay, and the internal delay that identifies the congestion situation is introduced into the calculation of the forwarding path In the process, the accuracy of calculating the forwarding path is improved, and the resource utilization rate of the network is increased.
Description
Technical Field
The present invention relates to the field of data processing, and in particular, to a method and an apparatus for determining a forwarding path.
Background
With the development of network technology, the accuracy requirement on forwarding is higher and higher, and possible network delay needs to be considered when calculating a network forwarding path.
For a network such as an IP network, the network delay mainly includes link delay, processing delay, and the like, where the link delay is related to an actual distance between forwarding devices, a transmission medium, and the like, for example, forwarding through an optical fiber of two hundred kilometers, the network delay may reach about 1 millisecond (ms), and the processing delay is related to a hardware processing capability of the forwarding devices themselves, and the two delays are relatively fixed, so that the network delay is mainly considered when a forwarding path is calculated in a conventional shortest path calculation manner.
Disclosure of Invention
Another type of network delay is not considered in the conventional manner, that is, congestion delay may occur in the actual working process of forwarding devices in a network, and such network delay is related to real-time service traffic and also related to a networking scheme of the network, and has a relatively large variation, sometimes even reaching a level of hundreds of ms. It can be seen that such network delay has a great effect on data forwarding, and if such network delay is not considered when determining a forwarding path, the actual network delay of the forwarding path may be much larger than the calculated network delay, and the obtained forwarding path with high network delay is contrary to the requirement for calculating the forwarding path, and the forwarding path with high network delay may greatly affect data forwarding, thereby reducing the resource utilization rate of the network.
It can be seen that, in order to improve the accuracy of calculating the forwarding path, various types of network delays need to be considered, especially such a time-varying congestion delay as described above.
In order to solve the above technical problem, embodiments of the present invention provide a method and an apparatus for determining a forwarding path, which can improve accuracy of calculating the forwarding path.
In a first aspect, the present invention provides a forwarding path determining method, applied to a plurality of nodes in a network, where the plurality of nodes includes a first node and a second node, and for determining a forwarding path from the first node to the second node, the method includes:
collecting the internal time delay of each of the plurality of nodes, wherein the internal time delay of one node is determined according to the congestion condition of the node caused by message processing;
in the process of determining a forwarding path from the first node to the second node according to the plurality of nodes, determining a path to be determined according to a shortest path algorithm from a node adjacent to the first node, wherein the path to be determined is a forwarding path which is a section of the forwarding path from the first node and comprises at least two nodes; taking the internal time delay of the node in the path to be determined as a part of the total time delay of the path to be determined;
and determining the path to be determined from the first node to the second node with the minimum total time delay as a forwarding path from the first node to the second node.
In a first possible implementation manner of the first aspect, in the plurality of nodes, the internal delay of one node is used to identify an average congestion condition of the node.
In a second possible implementation manner of the first aspect, in the plurality of nodes, the internal delay of one node is used to identify a congestion situation between the node from an ingress interface to an egress interface.
With reference to the second possible implementation manner of the first aspect, in a third possible implementation manner, the determining, for a forwarding path from the first node to the second node, specifically including determining, for a forwarding path from a target ingress interface of the first node to a target egress interface of the second node, taking an internal delay of each node in the path to be determined as a part of a total delay of the path to be determined includes:
for a node in the path to be determined, the internal delay of a node is used for identifying the congestion condition between an input interface and an output interface used by the node in the path to be determined;
and adding the link time delay of each link included in the path to be determined and the internal time delay of each node included in the path to be determined to obtain the total time delay of the path to be determined.
With reference to the third possible implementation manner of the first aspect, in a fourth possible implementation manner, for determining a forwarding path from the destination ingress interface of the first node to the destination egress interface of the second node, before determining a path to be determined according to a shortest path algorithm from a neighboring node to the first node, the method includes:
taking an input interface and an output interface of a node as virtual nodes;
and updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
With reference to the fourth possible implementation manner of the first aspect, in a fifth possible implementation manner, the taking an ingress interface and an egress interface of a node as virtual nodes includes:
and all outgoing interfaces and incoming interfaces of the plurality of nodes are used as virtual nodes.
In a second aspect, the present invention provides a forwarding path determining apparatus, applied to a plurality of nodes in a network, where the plurality of nodes includes a first node and a second node, and for determining a forwarding path from the first node to the second node, the apparatus includes a collecting unit and a determining unit:
the collecting unit is configured to collect respective internal delays of the plurality of nodes, where an internal delay of a node is determined according to a congestion condition of the node caused by processing a packet;
the determining unit is configured to determine, according to a shortest path algorithm, a path to be determined from a node adjacent to a first node in a process of determining a forwarding path from the first node to a second node according to the plurality of nodes, where the path to be determined is a forwarding path that starts from the first node and includes at least two nodes; taking the internal time delay of the node in the path to be determined as a part of the total time delay of the path to be determined;
the determining unit is further configured to determine that a minimum total delay in paths to be determined from the first node to the second node is a forwarding path from the first node to the second node.
In a first possible implementation manner of the second aspect, in the plurality of nodes, the internal delay of one node is used to identify an average congestion condition of the node.
In a second possible implementation manner of the second aspect, in the plurality of nodes, the internal delay of one node is used for identifying a congestion situation between the node from the incoming interface to the outgoing interface.
With reference to the second possible implementation manner of the second aspect, in a third possible implementation manner, the determining a forwarding path from the first node to the second node specifically includes determining a forwarding path from a target ingress interface of the first node to a target egress interface of the second node, and the determining unit includes an identifying subunit and an adding subunit:
the identifying subunit is configured to, for a node in the path to be determined, identify a congestion condition between an ingress interface and an egress interface used by the node in the path to be determined;
and the adding subunit is configured to add, according to the link time delay of each link included in the path to be determined and the internal time delay of each node included in the path to be determined, the total time delay of the path to be determined.
With reference to the third possible implementation manner of the second aspect, in a fourth possible implementation manner, the apparatus further includes a virtual unit and an update unit:
the virtual unit is used for taking an input interface and an output interface of the node as virtual nodes;
and the updating unit is used for updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
With reference to the fourth possible implementation manner of the second aspect, in a fifth possible implementation manner, the virtual unit is specifically configured to use all outgoing interfaces and incoming interfaces of the multiple nodes as virtual nodes.
According to the technical scheme, in the process of determining two nodes, namely the forwarding path from the first node to the second node, according to the plurality of nodes, the internal time delays of the plurality of nodes for identifying the congestion condition can be obtained in advance, so that when the path to be determined is calculated according to the shortest path algorithm, the total time delay of the path to be determined further comprises the internal time delay of each node in the path to be determined besides the link time delay, the determined forwarding path from the first node to the second node is the minimum total time delay path with the internal time delay taken into consideration, the internal time delay identifying the congestion condition is introduced into the process of calculating the forwarding path, the accuracy of calculating the forwarding path is improved, and the resource utilization rate of the network is increased.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to these drawings without creative efforts.
Fig. 1 is a flowchart of a forwarding path determining method according to an embodiment of the present invention;
fig. 2 is a directed connected graph formed by links among a plurality of nodes according to an embodiment of the present invention;
fig. 3a is a schematic diagram of a link composition between multiple nodes considering internal delay of the nodes according to an embodiment of the present invention;
fig. 3b is a schematic diagram of a forwarding path from a first node to a second node according to an embodiment of the present invention;
fig. 3c is a schematic diagram of a forwarding path from the first node to each other node according to an embodiment of the present invention;
fig. 4a is a schematic diagram illustrating a link composition between multiple nodes considering internal delay between different interfaces according to an embodiment of the present invention;
fig. 4b is a schematic diagram of a forwarding path from a target ingress interface to a target egress interface according to an embodiment of the present invention;
fig. 4c is a schematic diagram of a network topology between updated nodes according to an embodiment of the present invention;
fig. 4d is a schematic diagram of a forwarding path from a target ingress interface of a first node to target egress interfaces of other nodes according to an embodiment of the present invention;
fig. 5 is a device structure diagram of a forwarding path determining device according to an embodiment of the present invention.
Detailed Description
Embodiments of the present invention will be described below with reference to the accompanying drawings.
With the development of network technology, the requirement on forwarding accuracy is higher and higher, the network delay of a forwarding path is an important performance index of the forwarding accuracy, and how to calculate and select a forwarding path meeting the requirement on the network delay becomes a prominent problem. Network latency may be used to identify the time of transmission of data, such as a message, from a sender to a destination of a network. For a network, such as an IP network, the network latency mainly includes link latency, processing latency, and the like. The link delay is related to the actual distance between forwarding devices, a transmission medium and the like, the processing delay is related to the hardware processing capacity of the forwarding devices, the two delays are relatively fixed, the processing delay is generally microsecond level, and the influence of the processing delay on the network delay is small compared with the link delay.
In a conventional manner, when a forwarding path with the shortest network delay is determined, the forwarding path in the network may be abstracted into links between nodes, and when a packet is forwarded by a route, one forwarding device may serve as one node. A link between two directly connected nodes may be used as an edge, a forwarding path may be composed of one or more edges, each edge is assigned with a corresponding weight, and the weight may be determined according to a link delay, or the link delay of the link may be used as a weight. For such a link structure, a Shortest Path First (SPF) algorithm may be used to calculate a forwarding path with the Shortest network delay from a certain node to any other node. Conventionally, the network delay of a path is considered to be the link delay between nodes in the path, for example, a forwarding path with the shortest network delay from node V0 to node V3 is determined to be a path from node V0 to node V3 after passing through node V2, where the link delay between node V0 and node V2 is 10ms, the link delay between node V2 and node V3 is 15ms, and the network delay of the forwarding path thus calculated is 25 ms.
However, in the actual working process of the forwarding device, congestion delay may occur, such network delay is related to real-time traffic flow and also related to the networking scheme of the network, and the variation is relatively large, and sometimes may even reach the level of hundreds of ms. It can be seen that such network delay has a large actual impact on data forwarding, and if such network delay is not considered in determining the forwarding path, the actual network delay of the forwarding path may be much larger than the calculated network delay. For example, under the condition that congestion delay is not considered, a determined forwarding path with the shortest network delay from the node V0 to the node V3 is a path from the node V0 to the node V3 after passing through the node V2, where a link delay between the node V0 and the node V2 is 10ms, a link delay between the node V2 and the node V3 is 15ms, a processing delay is generally microsecond, and the processing delay is negligible, so that the calculated network delay is 25ms, but a congestion delay may occur in a node working process, taking the node V2 as an example, a congestion delay generated by the node V2 during processing a service is 100ms, and an actual network delay of the forwarding path is far higher than an originally calculated network delay. Therefore, the obtained forwarding path with high network delay is contrary to the requirement of calculating the forwarding path, and the forwarding path with high network delay can greatly influence data forwarding, thereby reducing the resource utilization rate of the network.
Therefore, in the process of determining a forwarding path between two nodes, that is, from a first node to a second node, according to a plurality of nodes, an internal delay used by the plurality of nodes to identify a congestion condition may be obtained in advance, so that when a path to be determined is calculated according to a shortest path algorithm, the total delay of the path to be determined includes not only a link delay but also an internal delay of each node in the path to be determined, and thus, the determined forwarding path from the first node to the second node is a minimum total delay path in which the internal delay is considered, and the internal delay identifying the congestion condition is introduced into the process of calculating the forwarding path, thereby improving the accuracy of calculating the forwarding path and increasing the resource utilization rate of the network.
Next, a forwarding path determining method provided by an embodiment of the present invention is described in detail. Fig. 1 is a flowchart of a forwarding path determining method provided in an embodiment of the present invention, which is applied to a plurality of nodes in a network, where the plurality of nodes include a first node and a second node, and for determining a forwarding path from the first node to the second node, the method includes:
s101: and collecting the internal time delay of each of the plurality of nodes.
In the embodiment of the present invention, when calculating the network delay, in order to make the calculated network delay closer to the actual network delay of the forwarding path, in addition to considering the link delay, it is also necessary to consider congestion delay that may occur in the actual working process of the forwarding device.
In the embodiment of the present invention, one node in the network may be a forwarding device with a message forwarding function in the network, and the forwarding device may include a router, a switch, and the like.
The internal delay of a node may be used to indicate the delay generated by the node due to the congestion condition caused by processing the packet, and the congestion delay generated when the node processes the packet may be used as the internal delay of the node. The congestion condition of the node generally changes with the processing condition of the node on the packet, that is, the congestion condition of the node may be different in different time periods, so that the internal delay of the node also changes, and it can be seen that the internal delay value of the node is not a fixed and unchangeable value.
The present invention does not limit the specific manner of collecting the internal delay of the node. The internal delays of the plurality of nodes may be collected periodically. It may also be that when there is a need to determine a forwarding path, the internal delays of the nodes are collected, for example, when a forwarding path with the minimum total delay from node 1 to node 2 needs to be calculated, the collection of the internal delays of each of a plurality of nodes may be performed, where the plurality of nodes may be all nodes related to the forwarding path determined from node 1 to node 2 in the network. The manner of selecting which to collect the internal time delay of the node may be related to the calculation accuracy or the calculation requirement.
In embodiments of the present invention, how to determine the range of the plurality of nodes may be related to the actual forwarding path computation requirements. If the computational requirements are to compute a forwarding path from one node to another, the plurality of nodes may be nodes that include both nodes and other nodes between which the forwarding path may be formed as part of, or otherwise associated with, the forwarding path. If the computational demand is to compute a forwarding path from one node in the network to other nodes in the network, the plurality of nodes may be all nodes in the network that may be used to form the forwarding path.
S102: in the process of determining a forwarding path from the first node to the second node according to the plurality of nodes, determining a path to be determined according to a shortest path algorithm from a node adjacent to the first node, wherein the path to be determined is a forwarding path which is a section of the forwarding path from the first node and comprises at least two nodes; and taking the internal time delay of the nodes in the path to be determined as a part of the total time delay of the path to be determined.
When a forwarding path from one node (an originating node) to another node (a destination node) in a network needs to be determined, the originating node may be used as a first node and the destination node may be used as a second node. And determining a plurality of paths to be determined from the first node to the second node according to the shortest path algorithm.
The path to be determined may be a path determined when a forwarding path is calculated using a shortest path algorithm. The form of the path to be determined is different according to the shortest path algorithm.
In the embodiment of the present invention, the path to be determined is a path from the first node. The path to be determined may be a path from the first node to the second node, and the path may include only the first node and the second node, or may include other nodes between the first node and the second node. A path to be determined may also be a path from the first node to a node other than the second node, where the other node may be one of the plurality of nodes between the first node and the second node in the process of calculating the shortest path. Therefore, the end point of the path to be determined may be different according to different shortest path algorithms or different calculation stages, except that the starting point is the first node.
The shortest path algorithm may be an algorithm for determining a forwarding path with the smallest total delay between nodes. The specific algorithm mode of the shortest path algorithm in the embodiment of the invention is not limited. Taking the first node as an example, when a forwarding path from the first node to the second node needs to be determined, then the corresponding shortest path algorithm may be an algorithm for determining a forwarding path with the minimum total delay between two nodes. When the forwarding paths from the first node to each of the other nodes need to be determined, the corresponding shortest path algorithm may be an algorithm for determining the forwarding path with the smallest total delay between one node and each of the other nodes, and may specifically be an SPF algorithm.
For example, as shown in fig. 2, there are 6 nodes in the network, nodes V0-V5, and it is assumed that node V0 is a first node and node V3 is a second node, and a directional connectivity graph formed by links between the nodes is as shown in fig. 2, node V0 is connected to nodes V1, V2, and V4, node V1 is connected to nodes V2, V3, and V4, node V2 is connected to node V3, node V3 is connected to nodes V4 and V5, and node V4 is connected to node V5. According to the shortest path algorithm, a path to be determined from node V to node V may be determined, where a path to be determined may go from node V to node V after passing through node V and then go to node V, and may be represented by [ V, V ], or a path to be determined may be [ V, V ], or [ V, V.
The shortest path algorithm different from the foregoing example is adopted to determine the path to be determined from the node V0, for example, the shortest path delay path between the node V0 and its neighboring node is searched for a node corresponding to the path, such as the node V1, starting from the node V0, and at this time, the determined path to be determined is a path from the node V0 to the node V1, that is, [ V0, V1 ]. Then, starting from the node V1, a node, for example, the node V2, corresponding to a path with the shortest path delay between the node V1 and its neighboring node is searched, at this time, the determined path to be determined is a path from the node V0 to the node V2 through the node V1, that is, [ V0, V1, V2], and so on, the determined next path to be determined may be a path from the node V0 to the node V3 through the node V2, and may be [ V0, V1, V2, V3 ].
Because the total time delay of the path to be determined is calculated, the internal time delay of the nodes in the path to be determined is also considered besides the link time delay among the nodes. The congestion condition of the node can be effectively reflected through the internal time delay, and particularly when the time for acquiring the internal time delay is closer to the time for calculating the forwarding path, the acquired internal time delay can more accurately reflect the current congestion condition of the node. Therefore, the total time delay of the path to be determined calculated by the method of the embodiment of the invention can be embodied more accurately, or is closer to the actual forwarding time delay of the path to be determined when the path to be determined forwards the message, thereby effectively improving the accuracy of calculating the forwarding path.
S103: and determining the path to be determined from the first node to the second node with the minimum total time delay as a forwarding path from the first node to the second node.
According to the operation of S102, all paths to be determined from the first node may be determined, and the total delay of one path to be determined may include a link delay between nodes in the path to be determined and an internal delay of the node.
When the total delay of a path to be determined is calculated, the internal delay as a part of the total delay may be the internal delays of all nodes included in the path to be determined, or may be the internal delays of other nodes except the first node in the path to be determined.
Since the link delay between the nodes in each path to be determined is different from the internal delay of the nodes, the total delay corresponding to each determined path from the first node to the second node is also different, and in the embodiment of the present invention, the path to be determined from the first node to the second node, which has the smallest total delay, can be used as the forwarding path from the first node to the second node. When the path to be determined from the first node to the second node, which has the minimum total delay, has a plurality of (at least two) paths, one of the paths can be arbitrarily selected as a forwarding path from the first node to the second node.
According to the technical scheme, in the process of determining two nodes, namely the forwarding path from the first node to the second node, according to the plurality of nodes, the internal time delays of the plurality of nodes for identifying the congestion condition can be obtained in advance, so that when the path to be determined is calculated according to the shortest path algorithm, the total time delay of the path to be determined further comprises the internal time delay of each node in the path to be determined besides the link time delay, the determined forwarding path from the first node to the second node is the minimum total time delay path with the internal time delay taken into consideration, the internal time delay identifying the congestion condition is introduced into the process of calculating the forwarding path, the accuracy of calculating the forwarding path is improved, and the resource utilization rate of the network is increased. Besides, the embodiment of the present invention may accurately calculate the forwarding path from the first node to the second node, and may also apply the embodiment of the present invention to calculate the forwarding paths from one node (for example, the first node) to other nodes (for example, other nodes except the first node in the plurality of nodes), so as to fully expand the application range of the embodiment of the present invention.
In the embodiment of the present invention, the internal delay of a node may be used to identify the congestion condition of the node, and in some cases where the requirement for calculation accuracy is not high, or in some cases where the number of interfaces for accessing the node is small, or in some cases where the congestion conditions between interfaces for accessing the node are relatively average, the internal delay of the node may be determined according to the average congestion condition of the node, for example, the congestion delays of the nodes in different time periods may be counted, and the average value of the obtained congestion delays is taken as the internal delay of the node. In this case, each node has its corresponding internal delay, which can be used to identify the average congestion condition of that node.
There may be at least one path to be determined from the first node to the second node, and taking a path to be determined as an example, the total delay of the path to be determined may be obtained by adding the link delay of one or more links from the first node to the end point of the path to be determined and the internal delay of the node in the path to be determined. When the internal delay of a node is determined according to the average congestion condition of the node, the total delay of a path to be determined is calculated, and the internal delay as a part of the total delay may be the internal delays of all nodes included in the path to be determined, or may be the internal delays of other nodes except the first node in the path to be determined.
The reason why the total time delay is calculated is that the internal time delay of the first node can be excluded is that all paths to be determined from the first node are paths formed from the first node, and since the internal time delay of the first node is a fixed value, whether the internal time delay of the first node is considered in calculating the total time delay does not affect the comparison result of the total time delay of each path to be determined, that is, the final determination of the forwarding path is not affected by not including the internal time delay of the first node in calculating the total time delay of the path to be determined. So in order to reduce the computational effort, the internal delay of the first node may not be taken into account when calculating the total delay. It should be noted that, when calculating the total delay of each path to be determined, the total delay of each path to be determined includes either the internal delay of the first node or neither the internal delay of the first node.
For example, as shown in fig. 3a, there are 6 nodes in the network, nodes V0-V5, and assuming that node V0 is a first node and node V3 is a second node, each node has its corresponding internal delay, the internal delay of node V0 is 10ms, the internal delay of node V1 is 15ms, the internal delay of node V2 is 100ms, the internal delay of node V3 is 5ms, the internal delay of node V4 is 5ms, the internal delay of node V5 is 10ms, a directed connectivity graph composed of links between nodes is shown in fig. 3a, node V0 is connected with nodes V1, V2 and V4, node V1 is connected with nodes V2, V3 and V4, node V2 and node V2 are connected with node V2, node V2 is connected with node V2, and node V2, the weight of the link between node V2 and node V2 is labeled as link 3650, 50 may be labeled on the link between node V0 and node V1. Taking an example of a path to be determined, for example, a path from the node V0 to the node V3 through the node V2, the path to be determined may be represented by [ V0, V2, V3], and taking an example of a total delay calculation method that does not include the internal delay of the first node, the total delay of the path to be determined may be a sum of a link delay from the node V0 to the node V3 and respective internal delays of the node V1 and the node V3, a link delay from the node V0 to the node V3 may be a sum of a link delay from the node V0 to the node V2 and a link delay from the node V2 to the node V3, that is, 10+15 ms to 25ms, and since the internal delay of the node V2 is 100ms and the internal delay of the node V3 is 5ms, the total delay may be calculated as 25+100+ 5ms to 130 ms.
By analogy, the total delay of each path to be determined from the node V0 to the node V3 can be calculated. Thus, the path to be determined with the minimum total latency may be selected as the forwarding path from the node V0 to the node V3, for example, as shown in fig. 3b, the path to be determined with the minimum total latency is determined as the forwarding path from the first node to the second node by comparing the total latency of each path to be determined, the path to be determined is the path to be determined from the node V0 to the node V3 through the node V4, and the total latency is 45+5+35+5 equals to 90 ms.
In analogy to the above method for determining a forwarding path from a first node to a second node, forwarding paths from the first node to other nodes can be determined.
In addition, when the forwarding paths from the first node to other nodes need to be determined, the shortest path algorithm may adopt an SPF algorithm, and the determination of the forwarding paths from the first node to other nodes may be implemented by using the SPF algorithm. Next, a description will be given of a determination manner of determining a forwarding path from the first node to each of the other nodes by the SPF algorithm.
When determining forwarding paths by using the SPF algorithm, a directed connectivity graph composed of forwarding paths to other nodes with a first node as a root (start node) may be referred to as a shortest delay path tree. Before determining the forwarding path by using the SPF algorithm, the nodes in the network may be divided into two sets, where the set a stores the nodes that have been selected into the shortest delay path tree, and the set B stores the other nodes remaining in the network. The paths can be divided into three sets, set 1 is used as a set of determined paths, the paths that have been selected into the shortest delay path tree are stored, and the paths finally stored in set 1 may include forwarding paths that need to be determined. The set 2 is used as a candidate path set, and stores the path of the next hop added to the shortest delay path tree, which may be the path to be determined. The set 3 is a set of remaining paths, and stores the remaining paths, which may be discarded paths or paths not yet considered.
First, a path with the shortest delay can be selected from the set 2, and put into the shortest delay path tree, i.e. the set 1, and correspondingly, the node (denoted as node X) corresponding to the end point of the path should be moved from the set B into the set a. The delay of a path may be the sum of the link delay between the nodes traversed by the path and the internal delay of each traversed node, or the sum of the link delay between the nodes traversed by the path and the internal delay of each traversed node, except the first node. For convenience of description, the following contents take a manner of not including the internal delay of the first node as an example of calculating the total delay.
For example, as shown in fig. 3a, it is assumed that a node V0 is a first node, at this time, a node V0 is stored in the set a, nodes adjacent to the node V0 (i.e., nodes directly connected to the node V0) are nodes V1, nodes V2, and nodes V4, a path between the node V0 and the node V1 may be denoted as [ V0, V1], and similarly, a path between the node V0 and the node V2 may be denoted as [ V0, V2], a path between the node V0 and the node V4 may be denoted as [ V0, V4], and at this time, the three candidate paths stored in the set 2 are these three candidate paths. Taking [ V0, V1] as an example, the delay of the path may be a link delay between node V0 and node V1, and a sum of internal delays of node V1, that is, 50+15 equals 65ms, and so on, the delay of the path of [ V0, V2] may be calculated to be 10+100 equals 110ms, and the delay of the path of [ V0, V4] may be 45+5 equals 50ms, so that the path of the shortest delay in set 2 is [ V0, V4], and then [ V0, V4] may be placed in set 1, node V4 is placed in set a, and node V4 is node X.
And secondly, searching the end point of the edge starting from the node X, namely the node (marked as the node Y) adjacent to the node X, wherein the node Y is the node which does not belong to the set A. For convenience of description, a path starting from the node V0, passing through the node X, and reaching the node Y may be denoted as (V0X) Y.
The delay of the path from node V0 through node X to node Y is calculated. The calculation method may be the sum of the delay of the path from the node V0 to the node X in the shortest path tree, the link delay of the edge from the node X to the node Y, and the internal delay of the node Y.
Next, it is necessary to examine whether there is a path to reach node Y among the candidate paths in set 2, and if there is a path, the delay of the path is compared with the delay of the (V0X) Y path. If the latency of the path is less than the latency of the (V0X) Y path, then the path remains in set 2 and the (V0X) Y path is placed in set 3; if the delay of the path is equal to the delay of the (V0X) Y path, one of the paths can be arbitrarily selected and stored in the set 2, and the rest path is put in the set 3; if the latency of the path is greater than the latency of the (V0X) Y path, (V0X) Y is saved in set 2 and the path is moved from set 2 to set 3.
For example, as shown in fig. 3a, in combination with the above example, [ V0, V4] has been put into set 1, and node V4 has been put into set a, at this time, node V4 is node X, and as can be seen from fig. 3a, the nodes adjacent to node X are node V1, node V3, and node V5, where node V0 is also a node adjacent to node V4, but node V0 has been put into set a, so node V0 is not considered, and it is known that node Y may be node V1, node V3, or node V5. Taking node V1 as an example of node Y, at this time, the path between node X and node Y is the path between node V4 and node V1, which can be denoted as [ V4, V1], the path from node V0 to node Y via node X is (V0V4) V1, and the delay of the path is the sum of the delay of the path between node V0 and node V4 in the shortest path tree, the link delay of the edge from node V4 to node V1, and the internal delay of node V1, that is, 50+10+15 equals 75 ms. Since there is already a path [ V0, V1] in set 2 to reach node V1 with a delay of 65ms, it can be seen that the delay of path [ V0, V1] is smaller than the delay of path (V0V4) V1, so that the path [ V0, V1] remains in set 2 and the path (V0V4) V1 is put in set 3.
When there are multiple edges starting from node X, there are multiple corresponding edge end points, i.e. nodes Y, and each node can be calculated and compared according to the method of the second step.
And repeating the two steps until the candidate path in the set 2 is empty and the node in the set B is empty, which indicates that the forwarding path from the first node to each other node is determined.
For example, as shown in fig. 3c, there are 6 nodes in the network, nodes V-V, assuming that node V is the first node, the forwarding path from node V to other nodes V-V can be determined by using the SPF algorithm, the forwarding path from node V to node V is the path formed from node V directly to node V, and can be denoted as [ V, V ], the forwarding path from node V to node V is the path formed from node V through node V to node V, and can be denoted as [ V, V ], the forwarding path from node V to node V is the path formed from node V directly to node V, and can be denoted as [ V, V ], the forwarding path from node V to node V is the path formed from node V through node V to node V, can be recorded as [ V0, V4, V5 ].
The internal time delay of the node is determined according to the average congestion condition of the node, and the internal time delay of the node is fully considered when the total time delay of the forwarding path is calculated, so that the calculated total time delay of the forwarding path is closer to the actual time delay of the forwarding path, and the accuracy of calculating the forwarding path is improved.
For a node, the node may have at least one interface, where any two interfaces in the node may be interconnected. The connection between two nodes may specifically be a connection made through a designated interface in the two nodes, that is, one node may be connected to a designated interface of another node through the designated interface of the node, for example, as shown in fig. 4a, assuming that node V0 is the first node, taking the connection of node V0 and node V1 as an example, node V0 has five interfaces, which are S, T, I, U and D respectively, node V1 has five interfaces, which are E, F, J, L and V respectively, and the connection of node V0 and node V1 may specifically be a connection established through interface D of node V0 and interface E of node V1.
In the above description, in some cases, the internal delay of a node may be determined according to the average congestion condition of the node. However, in the network operation, there may be a case where the congestion conditions between different interfaces in a node are far from each other, that is, the internal delays of the nodes are different due to the difference in the congestion conditions between different interfaces. For example, assuming that node V0 is the first node, node V0 has five interfaces, S, T, I, U and D respectively, the congestion delay between interface S and interface U is 5ms, and the congestion delay between interface S and interface T is 15ms, it can be seen that there is a significant difference in congestion delays generated by these two connection cases.
Therefore, in addition to the above-mentioned manner of determining the internal delay of the node according to the average congestion condition of the node, in order to more accurately represent the internal delay of each node on different paths for the case where the accuracy requirement for calculating the total delay of the forwarding path is high, the connection between the nodes may be refined into the connection between the ingress interface and the egress interface in each node, the internal delay of the node may be determined according to the congestion condition between the ingress interface and the egress interface in the node, and specifically, the congestion delay generated between the ingress interface and the egress interface in the node may be used as the internal delay of the node. The internal delay of a node may comprise a plurality of internal delays, each internal delay identifying a congestion condition between the node from an ingress interface to an egress interface. For a path, a node on the path uses a fixed access interface, so that the node has only one corresponding internal delay on the path, that is, the internal delay corresponding to the fixed access interface.
For example, as shown in fig. 4a, it is assumed that the node V0 is a first node, and a path starts from the interface S of the node V0 and passes through the interface T to reach the interface C of the node V2, where in the path, the interface S is an incoming interface of the node V0, and the interface T is an outgoing interface of the node V0.
When the internal delay of a node is determined according to the congestion condition between the ingress interface and the egress interface in the node, correspondingly, the determining of the forwarding path from the first node to the second node specifically includes: a determination of a forwarding path from a target ingress interface of the first node to a target egress interface of a second node.
For example, as shown in fig. 4a, there are 6 nodes in the network, nodes V0-V5, and assuming that node V0 is the first node and node V3 is the second node, when a forwarding path from interface S of V0 to interface Q of V3 needs to be determined, interface S of V0 is the target ingress interface, and interface Q of V3 is the target egress interface.
Taking a path to be determined as an example, for a node in the path to be determined, an internal delay of a node may be used to identify a congestion situation between an ingress interface and an egress interface used by the node in the path to be determined, and a total delay of the path to be determined may be obtained by adding a link delay of each link included in the path to be determined and an internal delay of each included node.
For example, as shown in fig. 4b, assuming that a node V0 is a first node, a node V3 is a second node, an interface S of a node V0 is a target input interface, an interface Q of a node V3 is a target output interface, and a path to be determined is a path starting from the interface S of the node V0, passing through an interface T, connecting to an interface C of a node V2, passing through an interface H of a node V2, connecting to an interface R of a node V3, and finally reaching the interface Q of the node V3, in the path to be determined, the interface S is an input interface of a node V0, and the interface T is an output interface of the node V0, the internal delay of the node V0 may be a congestion delay from the interface S to the interface T, and similarly, the interface C is an input interface of the node V2, the interface H is an output interface of the node V2, and the internal delay of the node V2 may be a congestion delay from the interface C to the interface H; interface R is the ingress interface of node V3, interface Q is the egress interface of node V3, and the internal delay of node V3 may be the congestion delay from interface R to interface Q. The total latency of the corresponding path to be determined may be the sum of the link latency of the node V0, the node V2, and the node V3 and the internal latency of each of the node V0, the node V2, and the node V3, where the link latency of the node V0 and the node V2 may specifically be the link latency from the interface T to the interface C, and similarly, the link latency of the node V2 and the node V3 may specifically be the link latency from the interface H to the interface R. Therefore, the total delay of the path to be determined may specifically be a sum of a congestion delay from the interface S to the interface T, a congestion delay from the interface C to the interface H, a congestion delay from the interface R to the interface Q, and a link delay from the interface T to the interface C and a link delay from the interface H to the interface R.
By analogy, the total delay of each path to be determined from the target ingress interface S of the first node (V0) to the target egress interface Q of the second node (V3) can be calculated, so that the path to be determined with the smallest total delay can be selected as the forwarding path from the target ingress interface S of the node V0 to the target egress interface Q of the node V3, for example, as shown in fig. 4b, by comparing the total delay of each path to be determined from the target ingress interface S of the node V0 to the target egress interface Q of the node V3, the determined forwarding path is a path from the interface S, through the interface T, through the interface C, through the interface H, through the interface R, and finally to the interface Q, and the total delay of the forwarding path is 15+10+10+15+10 ═ 60 ms.
In analogy to the method for determining the forwarding path from the target ingress interface of the first node to the target egress interface of the second node described above, the forwarding path from the target ingress interface of the first node to the target egress interface of each of the other nodes may be determined.
The internal time delay of the node is determined according to the congestion condition between the input interface and the output interface of the node, so that the internal time delay of the node can be reflected more accurately, the internal time delay of the node is fully considered when the total time delay of the forwarding path is calculated, the calculated total time delay of the forwarding path can be more accurate, and the accuracy of calculating the forwarding path is further improved.
In addition, in the embodiment of the present invention, when it is necessary to determine the forwarding paths from the target ingress interface of the first node to the target egress interfaces of other nodes, the shortest path algorithm may specifically be an SPF algorithm, and the determination of the forwarding paths from the target ingress interface of the first node to the target egress interfaces of other nodes may be implemented by using the shortest path algorithm.
When determining forwarding paths using the SPF algorithm, the forwarding paths in the network need to be abstracted into nodes and links between the nodes. In order that the determination of the forwarding path from the target ingress interface of the first node to the target egress interfaces of the other respective nodes may be performed using the SPF algorithm, the ingress and egress interfaces of the nodes may be considered as virtual nodes. Specifically, for determining a forwarding path from a destination ingress interface of the first node to a destination egress interface of the second node, before determining a path to be determined according to a shortest path algorithm from a neighboring node of the first node, the method includes:
taking an input interface and an output interface of a node as virtual nodes;
and updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
The entry interface and the exit interface of the node may be regarded as virtual nodes, that is, all the exit interfaces and the entry interfaces of the plurality of nodes may be regarded as virtual nodes, that is, all the interfaces included in one node may be regarded as virtual nodes, for example, the node V0 has five interfaces, respectively S, T, I, U and D, the interface S may be regarded as a virtual node S, the interface T may be regarded as a virtual node T, the interface I may be regarded as a virtual node I, the interface U may be regarded as a virtual node U, and the interface D may be regarded as a virtual node D.
For example, as shown in fig. 4c, the interfaces of each node are used as virtual nodes, the solid line in fig. 4c is the original topology information between the multiple nodes, the weight on each solid line may be the link delay between the interfaces, the dotted line in fig. 4c is the connection relationship between any two interfaces inside each node, the weight on each dotted line may be the congestion delay between the corresponding interfaces, and the updated topology information between the multiple nodes includes the solid line and the dotted line in the graph.
Next, a description will be given of a manner of determining a forwarding path from a target ingress interface of a first node to a target egress interface of each of other nodes by an SPF algorithm.
When the SPF algorithm is used for calculation, a directed connectivity graph composed of forwarding paths to other target egress interfaces with a target ingress interface (virtual node S) as a root may be referred to as a shortest delay path tree. Before determining the forwarding path by using the SPF algorithm, the virtual nodes in the network may be divided into two sets, where the set a stores the virtual nodes that have been selected into the shortest delay path tree, and the set B stores the other virtual nodes remaining in the network. The paths can be divided into three sets, the set 1 is used as a set of determined paths, the paths which are already selected into the shortest delay path tree are stored, and the paths finally stored in the set 1 are the forwarding paths which need to be determined. The set 2 is used as a candidate path set, and stores the path of the next hop added to the shortest delay path tree, which may be the path to be determined. The set 3 is a set of remaining paths, and stores the remaining paths, which may be discarded paths or paths not yet considered.
First, a path with the shortest delay can be selected from the set 2, and put into the shortest delay path tree, i.e. the set 1, and correspondingly, the virtual node (denoted as virtual node X) corresponding to the end point of the path should be moved from the set B to the set a. The delay of a path may be a link delay or a congestion delay between virtual nodes through which the path passes, the delay of the path between two virtual nodes may be a link delay generated between the two virtual nodes when the two virtual nodes belong to different two nodes, and the delay of the path between the two virtual nodes may be a congestion delay generated between the two virtual nodes when the two virtual nodes belong to an internal interface of a node.
It should be noted that, because forwarding does not occur inside the forwarding device, if a path newly added to the set I is a path connected between two virtual nodes in the same node, other paths inside the node are excluded when adding a candidate path to the set 2.
For example, as shown in fig. 4c, it is assumed that the interface S is a target input interface of the first node V0, at this time, the set a stores the virtual node S, the virtual nodes adjacent to the virtual node S (i.e., the virtual nodes directly connected to the virtual node S) are the virtual node U, the virtual node D, the virtual node I, and the virtual node T, and the path between the virtual node S and the virtual node U may be denoted as [ S, U ], and similarly, the path between the virtual node S and the virtual node D may be denoted as [ S, D ], the path between the virtual node S and the virtual node I may be denoted as [ S, I ], the path between the virtual node S and the virtual node T may be denoted as [ S, T ], and at this time, the four candidate paths are stored in the set 2. Taking S, T as an example, the delay of the path may be 5ms, which is the congestion delay from the virtual node S to the virtual node T, and so on, it can be obtained that the delay of the path of S, U is 5ms, the delay of the path of S, D is 5ms, and the delay of the path of S, I is 10ms, so it can be known that the paths with the shortest delay in the set 2 are S, U and S, D, and for the case where there are multiple paths with the shortest delay, one of them, for example, S, U, may be arbitrarily selected first and put in the set 1, and the virtual node U is the virtual node X.
And secondly, searching the end point of the edge starting from the virtual node X, namely the virtual node (marked as virtual node Y) adjacent to the virtual node X, wherein the virtual node Y is a virtual node which does not belong to the set A. For convenience of description, a path from the virtual node S to the virtual node Y via the virtual node X may be denoted as (SX) Y.
And calculating the time delay of a path from the virtual node S to the virtual node Y through the virtual node X. The calculation method may be the sum of the delay of the path from the virtual node S to the virtual node X in the shortest path tree and the delay of the path from the virtual node X to the virtual node Y.
Next, it is necessary to examine whether a path to the virtual node Y exists in the candidate paths in the set 2, and if so, the delay of the path is compared with the delay of the path in (SX) Y. If the delay of the path is less than the delay of the path of (SX) Y, the path is still retained in set 2, and the path of (SX) Y is put into set 3; if the time delay of the path is equal to the time delay of the (SX) Y path, one of the paths can be selected randomly and stored in the set 2, and the rest path is placed in the set 3; if the latency of the path is greater than the path latency of (SX) Y, (SX) Y is saved in set 2 and the path is moved from set 2 to set 3.
For example, as shown in fig. 4c, in combination with the above example, already putting [ S, U ] into the set 1, and putting the virtual node U into the set a, where the virtual node U is the virtual node X, because a case where a hop does not occur in forwarding inside the forwarding device, for example, a case where S- > U- > D does not occur in the same node, if a path newly added to the set I is a path connected by two virtual nodes in the same node, other paths inside the node are excluded when a candidate path is added to the set 2, and because [ S, U ] belongs to a path connected by two virtual nodes in the same node, other paths inside the node are not added to the set 2.
When there are multiple edges starting from the virtual node X, there are multiple corresponding edge end points, i.e., the virtual node Y, and each virtual node can be calculated and compared according to the method of the second step.
And repeating the two steps until the candidate path in the set 2 is empty and the virtual node in the set B is empty, which indicates that the forwarding path with the shortest delay from the virtual node S to each other virtual node is determined.
For example, as shown in fig. 4d, there are 22 virtual nodes in the network, and assuming that the virtual node S is the target ingress interface of the first node V0, the forwarding path from the virtual node S to each of the other virtual nodes can be determined by using the SPF algorithm. Taking a forwarding path from the virtual node S to the virtual node Q as an example, the forwarding path is a path which passes through the virtual node T, the virtual node C, the virtual node H, and the virtual node R from the virtual node S to the virtual node Q and finally reaches the virtual node Q, and the path is a forwarding path with the minimum total time delay in all paths to be determined from the virtual node S to the virtual node Q.
All outgoing interfaces and incoming interfaces of a plurality of nodes in the network are used as virtual nodes, so that the shortest total delay forwarding path from one virtual node to other virtual nodes can be quickly and accurately determined by using an SPF algorithm.
Apparatus embodiment of the invention
Fig. 5 is a device structure diagram of a forwarding path determining device according to an embodiment of the present invention, which is applied to a plurality of nodes in a network, where the plurality of nodes include a first node and a second node, and for determining a forwarding path from the first node to the second node, the forwarding path determining device 500 includes a collecting unit 501 and a determining unit 502:
the collecting unit 501 is configured to collect internal delays of the nodes, where the internal delay of a node is determined according to a congestion condition of the node caused by processing a packet.
The determining unit 502 is configured to, in a process of determining a forwarding path from the first node to the second node according to the plurality of nodes, determine a path to be determined according to a shortest path algorithm from a node adjacent to the first node, where the path to be determined is a forwarding path that starts from the first node and includes at least two nodes; and taking the internal time delay of the nodes in the path to be determined as a part of the total time delay of the path to be determined.
The determining unit 502 is further configured to determine a minimum total delay in paths to be determined from a first node to a second node as a forwarding path from the first node to the second node.
Optionally, in the plurality of nodes, the internal delay of one node is used to identify an average congestion condition of the node.
Optionally, in the plurality of nodes, the internal delay of one node is used to identify a congestion condition between the ingress interface and the egress interface of the node.
Optionally, the determining of the forwarding path from the first node to the second node specifically includes determining of the forwarding path from the target ingress interface of the first node to the target egress interface of the second node, and the determining unit includes an identifying subunit and an adding subunit:
the identifying subunit is configured to, for a node in the path to be determined, identify a congestion condition between an ingress interface and an egress interface used by the node in the path to be determined.
And the adding subunit is configured to add, according to the link time delay of each link included in the path to be determined and the internal time delay of each node included in the path to be determined, the total time delay of the path to be determined.
Optionally, the apparatus further includes a virtual unit and an update unit:
and the virtual unit is used for taking the input interface and the output interface of the node as virtual nodes.
And the updating unit is used for updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
Optionally, the virtual unit is specifically configured to use all outgoing interfaces and incoming interfaces of the multiple nodes as virtual nodes.
Fig. 5 is a device embodiment for describing the technical solution of the present invention from a network device side, and for description of features in the embodiment corresponding to fig. 5, reference may be made to related description of the embodiment corresponding to fig. 1, which is not repeated here.
According to the technical scheme, in the process of determining two nodes, namely the forwarding path from the first node to the second node, according to the plurality of nodes, the internal time delays of the plurality of nodes for identifying the congestion condition can be obtained in advance, so that when the path to be determined is calculated according to the shortest path algorithm, the total time delay of the path to be determined further comprises the internal time delay of each node in the path to be determined besides the link time delay, the determined forwarding path from the first node to the second node is the minimum total time delay path with the internal time delay taken into consideration, the internal time delay identifying the congestion condition is introduced into the process of calculating the forwarding path, the accuracy of calculating the forwarding path is improved, and the resource utilization rate of the network is increased.
The first node mentioned in the embodiments of the present invention is only used for name identification, and does not represent the first node in sequence. The rule applies equally to "second".
Those of ordinary skill in the art will understand that: all or part of the steps for realizing the method embodiments can be completed by hardware related to program instructions, the program can be stored in a computer readable storage medium, and the program executes the steps comprising the method embodiments when executed; and the aforementioned storage medium may be at least one of the following media: various media that can store program codes, such as read-only memory (ROM), RAM, magnetic disk, or optical disk.
It should be noted that, in the present specification, all the embodiments are described in a progressive manner, and the same and similar parts among the embodiments may be referred to each other, and each embodiment focuses on the differences from the other embodiments. In particular, for the apparatus and system embodiments, since they are substantially similar to the method embodiments, they are described in a relatively simple manner, and reference may be made to some of the descriptions of the method embodiments for related points. The above-described embodiments of the apparatus and system are merely illustrative, and the units described as separate parts may or may not be physically separate, and the parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution of the present embodiment. One of ordinary skill in the art can understand and implement it without inventive effort.
The above description is only for the specific embodiments of the present invention, but the scope of the present invention is not limited thereto, and any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope of the present invention are included in the scope of the present invention. Therefore, the protection scope of the present invention shall be subject to the protection scope of the claims.
Claims (12)
1. A forwarding path determination method applied to a plurality of nodes in a network, the plurality of nodes including a first node and a second node, the method comprising:
collecting the internal time delay of each of the plurality of nodes, wherein the internal time delay of one node is determined according to the congestion condition of the node caused by message processing;
in the process of determining a forwarding path from the first node to the second node according to the plurality of nodes, determining a path to be determined according to a shortest path algorithm from a node adjacent to the first node, wherein the path to be determined is a forwarding path which is a section of the forwarding path from the first node and comprises at least two nodes; taking the internal time delay of the node in the path to be determined as a part of the total time delay of the path to be determined;
and determining the path to be determined from the first node to the second node with the minimum total time delay as a forwarding path from the first node to the second node.
2. The method of claim 1, wherein the internal delay of a node in the plurality of nodes is used to identify an average congestion condition for the node.
3. The method of claim 1, wherein the internal delay of a node in the plurality of nodes is used to identify a congestion condition between the node from an ingress interface to an egress interface.
4. The method according to claim 3, wherein the determining the forwarding path from the first node to the second node specifically includes determining the forwarding path from a target ingress interface of the first node to a target egress interface of the second node, and then the taking the internal latency of each node in the path to be determined as a part of the total latency of the path to be determined includes:
for a node in the path to be determined, the internal delay of a node is used for identifying the congestion condition between an input interface and an output interface used by the node in the path to be determined;
and adding the link time delay of each link included in the path to be determined and the internal time delay of each node included in the path to be determined to obtain the total time delay of the path to be determined.
5. The method of claim 4, wherein determining a forwarding path from a destination ingress interface of the first node to a destination egress interface of a second node comprises, before determining a path to be determined according to a shortest path algorithm from a neighboring node to the first node:
taking an input interface and an output interface of a node as virtual nodes;
and updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
6. The method of claim 5, wherein using the ingress and egress interfaces of the node as virtual nodes comprises:
and all outgoing interfaces and incoming interfaces of the plurality of nodes are used as virtual nodes.
7. A forwarding path determination apparatus applied to a plurality of nodes in a network, the plurality of nodes including a first node and a second node, the apparatus comprising a collection unit and a determination unit for determining a forwarding path from the first node to the second node:
the collecting unit is configured to collect respective internal delays of the plurality of nodes, where an internal delay of a node is determined according to a congestion condition of the node caused by processing a packet;
the determining unit is configured to determine, according to a shortest path algorithm, a path to be determined from a node adjacent to a first node in a process of determining a forwarding path from the first node to a second node according to the plurality of nodes, where the path to be determined is a forwarding path that starts from the first node and includes at least two nodes; taking the internal time delay of the node in the path to be determined as a part of the total time delay of the path to be determined;
the determining unit is further configured to determine that a minimum total delay in paths to be determined from the first node to the second node is a forwarding path from the first node to the second node.
8. The apparatus of claim 7, wherein the internal delay of a node in the plurality of nodes is used to identify an average congestion condition for the node.
9. The apparatus of claim 7, wherein the internal delay of a node in the plurality of nodes is used to identify a congestion condition between the node from an ingress interface to an egress interface.
10. The apparatus according to claim 9, wherein the determining for the forwarding path from the first node to the second node specifically comprises determining for the forwarding path from the target ingress interface of the first node to the target egress interface of the second node, and wherein the determining unit comprises an identifying subunit and a summing subunit:
the identifying subunit is configured to, for a node in the path to be determined, identify a congestion condition between an ingress interface and an egress interface used by the node in the path to be determined;
and the adding subunit is configured to add, according to the link time delay of each link included in the path to be determined and the internal time delay of each node included in the path to be determined, the total time delay of the path to be determined.
11. The apparatus of claim 10, wherein the apparatus further comprises a virtual unit and an update unit:
the virtual unit is used for taking an input interface and an output interface of the node as virtual nodes;
and the updating unit is used for updating the topology information among the nodes according to the topology information among the nodes and the connection relation among the virtual nodes.
12. The apparatus of claim 11, wherein the virtual unit is specifically configured to treat all outbound interfaces and inbound interfaces of the plurality of nodes as virtual nodes.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201611249143.1A CN106878170B (en) | 2016-12-29 | 2016-12-29 | Method and device for determining forwarding path |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201611249143.1A CN106878170B (en) | 2016-12-29 | 2016-12-29 | Method and device for determining forwarding path |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106878170A CN106878170A (en) | 2017-06-20 |
| CN106878170B true CN106878170B (en) | 2020-04-21 |
Family
ID=59164399
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201611249143.1A Active CN106878170B (en) | 2016-12-29 | 2016-12-29 | Method and device for determining forwarding path |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106878170B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110858820A (en) | 2018-08-22 | 2020-03-03 | 中兴通讯股份有限公司 | Service operation method and device, storage medium and electronic device |
| CN109889446B (en) * | 2019-03-11 | 2021-03-23 | 西安电子科技大学 | SDN-based heterogeneous convergence network minimum delay path determination method |
| CN111770475B (en) * | 2019-03-31 | 2022-04-22 | 华为技术有限公司 | Time delay acquisition method and device, optimization method and device |
| CN114143004B (en) * | 2021-12-03 | 2023-07-28 | 网络通信与安全紫金山实验室 | Deployment method, device, equipment and storage medium of random forwarding network |
| CN116566892A (en) * | 2022-01-28 | 2023-08-08 | 中兴通讯股份有限公司 | Method of determining routing, electronic device, computer readable medium |
| CN118555658A (en) * | 2023-02-24 | 2024-08-27 | 中兴通讯股份有限公司 | Resource allocation method, communication node and storage medium |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1171420C (en) * | 2000-03-15 | 2004-10-13 | 英佛西莫信息技术股份有限公司 | Method and system for communication of data via optimum data path in network |
| KR100336282B1 (en) * | 2000-06-12 | 2002-05-13 | 안병엽 | Multicast guaranteening method |
| CN101119303B (en) * | 2007-08-30 | 2010-08-11 | 浙江工业大学 | Dynamic cluster based multi-objective programming wireless sensing network routing algorithm |
| US8611355B1 (en) * | 2013-09-03 | 2013-12-17 | tw telecom holdings inc. | Buffer-less virtual routing |
| CN105207906B (en) * | 2014-06-25 | 2019-02-19 | 华为技术有限公司 | Method and device for determining service path |
| CN104301214A (en) * | 2014-10-10 | 2015-01-21 | 北京邮电大学 | A method for overlay network routing |
| CN104270311A (en) * | 2014-10-29 | 2015-01-07 | 国家电网公司 | Radio network route recognizing method |
| JP6519162B2 (en) * | 2014-12-04 | 2019-05-29 | 富士通株式会社 | Transmission system, transmission time difference measurement method in transmission system, and node |
-
2016
- 2016-12-29 CN CN201611249143.1A patent/CN106878170B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN106878170A (en) | 2017-06-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106878170B (en) | Method and device for determining forwarding path | |
| US8897141B2 (en) | Network system and routing method | |
| US8862775B2 (en) | Network server and load balancing routing method for networks thereof | |
| CN104969518A (en) | Routing data | |
| JP5723334B2 (en) | Network topology estimation method and topology estimation apparatus | |
| US20180316599A1 (en) | Routing packets considering the propagation delay of routes | |
| CN108600103A (en) | The ant group algorithm of more QoS route restrictions of oriented multilayer grade network | |
| CN115022230B (en) | A communication path planning method and device | |
| CN112615780B (en) | Method and device for determining alternative path of data flow in SDN network | |
| CN101753462B (en) | Method and device for realizing multi-next hop routing | |
| CN109429117B (en) | Routing method and device | |
| CN109474506A (en) | Method and device for establishing virtual private network VPN service | |
| JP5894245B2 (en) | An estimation method for loss rate in packetized networks | |
| CN115103245B (en) | Optical network fault analysis method and device | |
| CN108270672A (en) | A kind of method and device for calculating circuit routing | |
| CN112995036A (en) | Network traffic scheduling method and device | |
| CN105264833B (en) | A kind of service path calculation method and device | |
| Li et al. | Load-balanced fixed routing for wavelength routed optical networks | |
| CN117354160A (en) | Path calculation method, controller, and computer-readable storage medium | |
| US20070140148A1 (en) | Fast simulated annealing for traffic matrix estimation | |
| EP3320657B1 (en) | Constrained disjoint path computation | |
| CN116566893B (en) | Method and device for establishing separation path | |
| CN107210930A (en) | Method and system for from the object assignment performance indicator to network | |
| Lai et al. | A segment list selection algorithm based on delay in segment routing | |
| EP3471351B1 (en) | Method and device for acquiring path information about data packet |
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 |