CN115701049B

CN115701049B - Communication delay estimation method and related device

Info

Publication number: CN115701049B
Application number: CN202110864757.5A
Authority: CN
Inventors: 徐明伟; 席照炜; 王旸旸; 周禹; 付洁; 缪丽华
Original assignee: Tsinghua University; Huawei Technologies Co Ltd
Current assignee: Tsinghua University; Huawei Technologies Co Ltd
Priority date: 2021-07-29
Filing date: 2021-07-29
Publication date: 2025-08-08
Anticipated expiration: 2041-07-29
Also published as: CN115701049A

Abstract

An embodiment of the present application provides a communication delay estimation method and related devices, the method comprising: a network device obtains flow information from a received first data packet, the flow information being identification information of a first flow to which the first data packet belongs; then, determining a first recording unit for mapping the first flow based on the flow information; the first recording unit includes the maximum delay of a single data packet of the target flow passing through the target device, and the number of data packets of the target flow received by the network device; the target flow includes a flow mapped to the first recording unit; then, updating the number of packets, and when the delay of the first data packet passing through the target device is greater than the first delay, updating the first delay to the delay of the first data packet passing through the target device; when the number of packets is less than a threshold, the first delay is used to estimate the tail delay of the first flow passing through the target device. The present application can save storage and processing resources for each flow, so that the tail delay of the full flow can be estimated on existing resources.

Description

Communication delay estimation method and related device

Technical Field

The present invention relates to the field of communications network measurement technologies, and in particular, to a communications delay estimation method and a related device.

Background

Network performance detection has been an important sub-issue in the network field where network measurement is of great application value. The measurement of time delay is always a hot spot of academic research, and is also a field in which industry is continuously pursuing innovation. Traditional tools (such as internet packet explorer ping, route tracking) that use sampling or transmitting probes to measure end-to-end delay have been widely deployed and applied, playing a significant role over long periods of time. Currently, with the rapid expansion of network scale and the continuous improvement of network equipment capability, users and products have made finer demands on network operation and maintenance. Network administrators want to improve the ability of the network to quickly detect and locate anomalies, such as a quick discovery distributed denial of service attack (distributed denial of service, DDos) attack, or to be able to detect potential micro-bursts (micro-bursts) in a data center, etc. These more challenging problems rely on more fine-grained measurements of the flow performance metrics, such as the measurement of the tail delay of the flow.

The current measurement technology of tail delay of the stream commonly used in the industry can be mainly divided into two types, namely an in-network measurement technology represented by network flow, a technology supporting screening, sampling and copying of relevant message data in network equipment, and then uploading the message data to a controller for tail delay measurement, and an in-band operation management maintenance (in-situ operation administration AND MAINTENANCE, iOAM) technology represented by in-band network telemetry (inband network telemetry, INT) technology. Such techniques encapsulate the required Operation Administration and Maintenance (OAM) information (e.g., delayed measurement data) directly in packets, and forward OAM data removal to the controller for tail delay measurement at the last hop of the monitoring domain, i.e., the edge node. However, the NetFlow technology supports that related information of a data packet acquired by a network device is sent to a controller, but causes larger extra load and resource consumption, so that sampling or stream selection is often needed in actual use, tail delay measurement of all streams passing through the network device is difficult to cover, the iOAM technology represented by INT carries required information at the head of the data packet, and information is collected and uploaded to the controller in the last hop, so that uploading cost is reduced, but link bandwidth is occupied, stream completion time is increased, throughput is reduced and the like, and therefore, the phenomena of packet-by-packet deployment is often not realized, and the tail delay measurement of all streams is difficult to realize.

In summary, how to reduce the resource overhead of the network device in the tail delay measurement process of each flow is a technical problem that needs to be solved by those skilled in the art.

Disclosure of Invention

The embodiment of the application provides a communication delay estimation method and a related device, which can reduce the resource overhead of network equipment in the tail delay measurement process of each stream, so that the network equipment can measure and estimate the tail delay of all streams passing through the network equipment based on the existing storage and processing resources.

In a first aspect, the application provides a communication delay estimation method, which comprises the steps that network equipment obtains stream information from received first data packets, the stream information is identification information of a first stream to which the first data packets belong, the network equipment determines a first recording unit of a first stream map based on the stream information, the first recording unit comprises first delay and packet number, the first delay is the maximum delay of a single data packet of a target stream passing through target equipment, the packet number is the number of data packets of the target stream received by the network equipment, the target stream comprises a stream mapped to the first recording unit, the network equipment updates the packet number, and updates the first delay to be the delay of the first data packets passing through the target equipment when the delay of the first data packets passing through the target equipment is larger than the first delay, and the first delay is used for estimating the delay tail of the first stream passing through the target equipment when the packet number is smaller than a threshold value.

Optionally, the target device is the network device, or the network device is a device on a data plane in a network, the network device is a last hop device of the target stream in the data plane, and the target device comprises a plurality of devices through which the single data packet passes in the data plane.

In the embodiment of the present application, the network device is any network device in a data plane for forwarding data, and the first recording unit is configured in the network device for each stream received by the network device, so as to record the maximum delay of the data packet in each stream passing through the target device, so as to estimate the tail delay of each stream passing through the target device when the number of packets in each stream is less than a threshold value. In the embodiment of the application, each stream is mapped to the corresponding first recording unit, and only the maximum time delay of the data packet passing through the target device is recorded in the first recording unit instead of the time delay of all the data packets, so that storage resources are saved. In addition, in the embodiment of the application, resources required by tail delay measurement and estimation of a single stream are saved, so that screening and sampling of streams are not required during tail delay measurement of the stream, that is, compared with the existing scheme, the method and the device can measure and estimate the tail delay of all streams passing through the network device based on the existing storage and processing resources of the network device.

In a possible implementation manner, the network device is a device on a data plane in a network, the network device is a last hop device of a data packet of the target flow in the data plane, the target device includes a plurality of devices through which the single data packet passes in the data plane, a delay of the first data packet passing through the target device is a delay of the first data packet passing through the plurality of devices, the first data packet includes a delay of the first data packet passing through other devices, and the other devices are other network devices except the network device in the plurality of devices.

In the embodiment of the present application, a delay obtaining module may be disposed on all network devices through which the first stream passes in the data plane, so as to obtain a delay of each data packet of the first stream passing through each network device, and then carry the delays in the data packets to send the data packets to the last hop device, where the last hop device also obtains a delay of each data packet passing through itself, then counts a total delay of each data packet passing through all network devices, and takes a maximum delay to record in the first recording unit. The implementation mode can enable the information such as time delay and the like to be recorded and processed only at the last hop device, and each network device through which the first stream passes is not required to be recorded, so that the storage and processing resources of the network device can be saved.

In a possible implementation manner, the network device is a device on a data plane in a network, the network device is a last hop device of a data packet of the target flow in the data plane, the target device comprises a plurality of devices through which the single data packet passes in the data plane, the time delay of the first data packet passing through the target device is the time delay of the first data packet passing through the plurality of devices, and the first data packet comprises a time stamp of an entry of the first hop device through which the first data packet passes in the data plane, and the time stamp is used for calculating the time delay of the first data packet passing through the plurality of devices.

In the embodiment of the application, the entry time stamp of the data packet of the stream can be acquired on the first device through which the first stream passes in the data plane, the time stamp is carried in the data packet and sent to the last-hop device, after the last-hop device receives the data packet, the time stamp sent by the data packet from the last-hop device can be acquired, the time stamp after the last time stamp is subtracted from the previous time stamp, which is the time delay of the data packet passing through the target device, and then the maximum time delay of the data packet passing through the target device in the stream is acquired and recorded in the first recording unit. Similarly, the implementation manner can enable the recording and processing of information such as time delay and the like to be only needed in the last hop device, and each network device through which the first stream passes is not needed to be recorded, so that the storage and processing resources of the network device can be saved.

In a possible implementation manner, the data packet of the target flow received by the network device is a data packet received by the network device in an estimation window, where the estimation window is a time window used for estimating the tail delay of the first flow passing through the target device, and the first delay is the maximum delay of a single data packet of the target flow passing through the target device, including the maximum delay of the single data packet of the first delay passing through the target device in the time window, and the tail delay of the first flow passing through the target device is the tail delay of the first flow passing through the target device in the time window.

In the embodiment of the application, the feasibility and operability of the network equipment can be improved by dividing the transmission process of the stream into one or more time windows and estimating the tail delay of the stream in each time window.

In one possible implementation, the first recording unit of the first stream map is multiple, the method further comprises the step that when the number of the packets recorded by at least one unit of the multiple first recording units is smaller than the threshold value after the estimation window is finished, the network device determines that the first delay recorded in the first unit is a tail delay estimated value of the first stream passing through the target device in the estimation window, and sends the first delay recorded in the first unit to the controller, wherein the first unit is the unit with the minimum first delay recorded in the multiple first recording units.

In the embodiment of the application, under the condition that the data packet of the target stream received by the network equipment in the estimation window is smaller than the threshold value, the tail delay of the first stream passing through the target equipment can be estimated by using the minimum first delay recorded in the plurality of first recording units, so that the realization is simple and the operability is higher. This is because in the case where the number of packets is small, the tail delay is small from the maximum delay of the data packet recorded in the first recording unit through the target device, so the tail delay of the stream can be estimated with the maximum delay.

In a possible implementation manner, the first recording units of the first stream map are multiple, and the method further comprises that the network device sends information recorded in the multiple first recording units to the controller when the estimation window ends.

In the embodiment of the application, the network equipment can send the information recorded by the first recording unit to the controller, and the controller carries out the estimation calculation of the tail time delay, thereby reducing the processing burden of the network equipment.

In a possible implementation manner, in the case that the number of the packets recorded in the first recording unit is greater than or equal to the threshold value, the method further comprises that the network device allocates a second recording unit to the first recording unit, wherein the second recording unit is used for recording the time delay of each data packet in n data packets passing through the target device, the n data packets are data packets in the data packets of the target stream received by the network device after the first data packet, n is an integer greater than 1, and the n time delays are used for estimating the tail time delay of the first stream passing through the target device.

In the embodiment of the present application, when the number of packets is greater than the threshold, the tail delay is greater than the maximum delay of the data packet recorded in the first recording unit passing through the target device, so that additional recording of delay is required to estimate the tail delay of the stream, so that the second recording unit is configured to record the delay of a part of the data packet of the subsequent received stream passing through the target device, and then estimate the tail delay of the stream based on the delay information recorded by the second recording unit, so as to improve the accuracy of estimation.

In a possible implementation manner, the method further comprises the steps that the network device receives a second data packet, the second data packet is a data packet of the target flow, the network device obtains a second time delay in n time delays of the second recording unit according to a polling mode, and the network device updates the second time delay in the second recording unit to the time delay of the second data packet passing through the target device under the condition that the time delay of the second data packet passing through the target device is larger than the second time delay.

In the embodiment of the present application, the time delay in the second recording unit may be updated by a polling manner, so as to ensure that the n time delays are the largest n time delays.

In a possible implementation manner, the method further includes that the network device receives a third data packet, the third data packet is a data packet of the target stream, before the third data packet and after the second data packet, the network device receives m data packets of the target stream, where m is an integer greater than 1, the network device randomly acquires a third delay in n delays of the second recording unit, and in the case that the delay of the third data packet passing through the target device is smaller than the third delay, the network device updates the third delay in the second recording unit to the delay of the third data packet passing through the target device.

In the case where the number of packets of a stream received in the estimation window is very large, there is a large error in estimating the tail delay of the stream by using the maximum n delays. For example, assuming that the number of packets reaches 10000, the number n is 10, if the 100 delays are the largest 10 delays, in estimating the 99% tail-biting delay, the 9900 delays of the 10000 data packets passing through the target device from small to large are accurate 99% tail-biting delays, and each of the 10 largest delays is different from the 9900 delays by a large amount, so that the 99% tail-biting delay cannot be estimated by using the 10 delays. Therefore, in the embodiment of the present application, in the process of updating the second recording unit, based on the updating manner of the polling, one of the n delays in the second recording unit is randomly selected to update to a smaller delay every a certain number of data packets, so that the n delays recorded in the second recording unit are not the largest delay, but as many other quantised delay information as possible are recorded in the second recording unit according to a certain probability, thereby reducing the estimation error of the tail delay.

In a possible implementation, the method further comprises estimating, by the network device, a tail delay of the first stream passing through the target device within the estimation window based on the n delays in the second recording unit, in case the estimation window ends.

Optionally, the tail delay of the first stream passing through the target device is p-bit tail delay, wherein p is greater than 80 and less than 100, and the network device estimates the tail delay of the first stream passing through the target device based on n delays in the second recording unit, and the network device determines the w-th delay of the n delays as a tail delay estimated value of the first stream passing through the target device in the estimation window, wherein the w-th delay is a delay which is sequenced as w in the n delays sequenced from small to large, and the w is an integer greater than 0 and less than or equal to n.

In the embodiment of the present application, based on the manner of updating the second recording unit, the p-bit tail delay may be estimated by using the delay among n delays in the second recording unit, and the w may be determined by calculating a mathematical expectation of the number of delays greater than the p-bit tail delay among the n delays.

In a possible embodiment, the method further comprises the network device sending information recorded in the first recording unit and the second recording unit to a controller in case the estimation window ends.

In the embodiment of the application, the network equipment can send the information recorded by the first recording unit and the second recording unit to the controller, and the controller carries out the estimation calculation of the tail delay, thereby reducing the processing burden of the network equipment.

In one possible implementation, the network device determines a first recording unit of the first stream map based on the stream information, including the network device mapping the stream information to a plurality of bits in a bitmap via a plurality of hash functions, one bit in the bitmap being associated with one of the first recording units, and the network device determining the first recording unit of the first stream map based on the plurality of bits.

In the embodiment of the application, the stream is mapped to the corresponding first recording unit through hash calculation, so that the method and the device are simple in calculation and convenient to process, and can save storage resources.

In one possible implementation manner, the first recording unit further includes an exclusive-or result of the number of streams and stream information, where the number of streams is the number of the target streams, and the exclusive-or result of the stream information is a result obtained by exclusive-or operation of the stream information of the target streams.

In the embodiment of the application, the exclusive or result of the number of streams and the stream information is recorded in the first recording unit, and can be used for marking the recording unit with hash collision and can be used for subsequently decoding the stream information with hash collision.

In a second aspect, the application provides a communication delay estimation method, which comprises the steps that network equipment obtains stream information from received first data packets, wherein the stream information is used for indicating the first data packets to be data packets in a first stream, the network equipment determines a first recording unit mapped by the first stream based on the stream information, the first recording unit is used for recording first delay and packet number, the first delay is the maximum delay of single data packets passing through target equipment, the first delay is the maximum delay of single data packets passing through the target equipment, the packet number is the number of data packets of the target stream, received by the network equipment, the target stream comprises a stream mapped to the first recording unit, the network equipment updates the packet number, and updates the first delay to be the delay of the first data packets passing through the target equipment when the delay of the first data packets passing through the target equipment is larger than the first delay, the network equipment allocates a second recording unit to the first recording unit when the packet number is larger than or equal to a threshold value, the second recording unit is used for recording n data packets in the second recording n data packets passing through the target equipment, and the n data packets in the second recording unit is the delay is the integer n data packets after the n data packets passing through the target equipment pass through the first delay is estimated to be the target packet.

In a third aspect, the present application provides a communication delay estimation method, the method including a controller receiving information recorded in a plurality of first recording units, the information recorded in each of the first recording units including a first delay and a packet number, the first delay being a maximum delay of a single packet of a target stream passing through a target device, the packet number being a number of packets of the target stream received by the network device, the target stream including a stream mapped to the first recording unit, the target stream including a first stream, and the controller estimating a tail delay of the first stream passing through the target device based on the first delay recorded in the plurality of first recording units in a case that the packet number is less than a threshold.

In the embodiment of the application, the controller can perform the estimation calculation of the tail delay, and under the condition that the data packet of the target stream received by the network equipment in the estimation window is smaller than the threshold value, the tail delay of the first stream passing through the target equipment can be estimated by using the first delays recorded in the plurality of first recording units, so that the implementation is simple and the operability is higher. This is because in the case where the number of packets is small, the tail delay is small from the maximum delay of the data packet recorded in the first recording unit through the target device, so the tail delay of the stream can be estimated with the maximum delay.

In a possible implementation manner, the method further comprises the step that the controller further receives an identifier of an estimation window, wherein the identifier indicates that information recorded in the plurality of first recording units is recorded in the estimation window, the estimation window is a time window for estimating the tail delay of the first stream passing through the target device, the step that the controller estimates the tail delay of the first stream passing through the target device based on the first delay recorded in the plurality of first recording units comprises the step that the controller determines that the first delay recorded in the first unit is the tail delay estimated value of the first stream passing through the target device in the estimation window, and the first unit is the unit with the minimum first delay recorded in the plurality of first recording units.

In the embodiment of the application, the feasibility and operability of the network equipment can be improved by dividing the transmission process of the stream into one or more time windows and estimating the tail delay of the stream in each time window. On the basis, the tail delay of the first stream passing through the target device can be estimated by using the minimum first delay recorded in the plurality of first recording units, because if the first delays in the plurality of first recording units are different, hash collision occurs in the recording units, and only the delay larger than the recorded first delay can be updated into the first recording unit, therefore, the minimum first delay in the plurality of first recording units mapped by the first stream is the more accurate tail delay estimation of the first stream, and therefore, the tail delay of the first stream is estimated by adopting the minimum first delay, so that the estimation accuracy can be improved.

In a fourth aspect, the application provides a communication delay estimation method, comprising the steps of receiving information recorded in a first recording unit and a second recording unit by a controller, wherein the information recorded in the first recording unit comprises a first delay and a packet number, the first delay is the maximum delay of a single data packet of a first stream passing through a target device, the packet number is the number of the data packets of the first stream received by the network device, the second recording unit is associated with the first recording unit, the information recorded in the second recording unit comprises the delay of each data packet of n data packets of the first stream passing through the target device, n is an integer greater than 1, and estimating the tail delay of the first stream passing through the target device by the controller based on the n delays.

In the embodiment of the present application, when the number of packets of the target stream received by the network device in the estimation window is greater than the threshold, the recorded information may also be sent to the controller, where the controller performs the estimation calculation of the tail delay.

In a possible implementation manner, the method further comprises the step that the controller further receives an identifier of an estimation window, wherein the identifier indicates that the information recorded in the first recording unit and the second recording unit is recorded in the estimation window, and the estimation window is a time window for estimating the tail delay of the first stream passing through the target device;

The tail delay of the first stream passing through the target device is p-bit tail delay, wherein p is more than 80% and less than 100%, and the controller estimates the tail delay of the first stream passing through the target device based on the n delays, and the method comprises the following steps:

the controller determines a w-th delay of the n delays as an estimated value of a tail delay of the first stream passing through the target device in the estimation window, wherein the w-th delay is a delay which is ordered as w in the n delays ordered from small to large, and w is an integer which is greater than 0 and less than or equal to n.

In the embodiment of the present application, the p-bit tail delay may be estimated by using the delay among n delays in the second recording unit, and the w may be determined by calculating a mathematical expectation of the number of delays greater than the p-bit tail delay among the n delays.

In a fifth aspect, the present application provides a network device comprising a processing unit configured to:

acquiring stream information from a received first data packet, wherein the stream information is identification information of a first stream to which the first data packet belongs;

determining a first recording unit of the first stream map based on the stream information, wherein the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of a target stream passing through target equipment, and the packet number is the number of the data packets of the target stream received by the network equipment;

Updating the number of the packets, and updating the first delay to be the delay of the first data packet passing through the target device when the delay of the first data packet passing through the target device is larger than the first delay, wherein the first delay is used for estimating the tail delay of the first stream passing through the target device when the number of the packets is smaller than a threshold value.

In a possible implementation manner, the first recording units of the first stream map are multiple, the processing unit is further configured to determine that the first delay recorded in the first unit is a tail delay estimated value of the first stream passing through the target device in the estimation window and send the first delay recorded in the first unit to the controller when the number of packets recorded in at least one unit of the multiple first recording units is smaller than the threshold after the estimation window is over, and the first unit is a unit with the minimum first delay recorded in the multiple first recording units.

In a possible implementation manner, the network device further comprises a sending unit, configured to send, to the controller, information recorded in the plurality of first recording units when the estimation window ends.

In a possible embodiment, in case the number of packets recorded in the first recording unit is greater than or equal to the threshold value, the processing unit is further configured to:

The method comprises the steps of distributing a second recording unit for the first recording unit, wherein the second recording unit is used for recording the time delay of each data packet in n data packets passing through the target device, the n data packets are data packets in the data packets of the target stream received by the network device after the first data packet, n is an integer larger than 1, and the n time delays are used for estimating the tail time delay of the first stream passing through the target device.

In a possible implementation manner, the network device further includes a receiving unit, configured to receive a second data packet, where the second data packet is a data packet of the target flow;

The processing unit is further configured to obtain a second delay of the n delays of the second recording unit according to a polling manner, and update the second delay of the second recording unit to a delay of the second data packet passing through the target device when the delay of the second data packet passing through the target device is greater than the second delay.

In a possible implementation manner, the receiving unit is further configured to receive a third packet, where the third packet is a packet of the target flow, and before the third packet and after the second packet, the receiving unit receives m packets of the target flow, where m is an integer greater than 1;

the processing unit is further configured to randomly acquire a third delay from the n delays of the second recording unit, and update the third delay in the second recording unit to a delay of the third data packet passing through the target device when the delay of the third data packet passing through the target device is smaller than the third delay.

In a possible implementation manner, the processing unit is further configured to estimate a tail delay of the first stream passing through the target device in the estimation window based on the n delays in the second recording unit, when the estimation window ends.

Optionally, the tail delay of the first stream passing through the target device is p-bit tail delay, wherein p is greater than 80 and less than 100, and the processing unit estimates the tail delay of the first stream passing through the target device based on n delays in the second recording unit, and the processing unit determines a w-th delay of the n delays as a tail delay estimated value of the first stream passing through the target device in the estimation window, wherein the w-th delay is a delay ordered as w in the n delays ordered from small to large, and the w is an integer greater than 0 and less than or equal to n.

In a possible implementation manner, the network device further includes a sending unit, configured to send, to the controller, the information recorded in the first recording unit and the second recording unit when the estimation window ends.

In a possible implementation manner, the processing unit determines the first recording unit of the first stream map based on the stream information, and the network device determines the first recording unit of the first stream map based on a plurality of bits of a bitmap, wherein the first recording unit of the first stream map is mapped to a plurality of bits of the bitmap through a plurality of hash functions.

In a sixth aspect, the present application provides a network device, the network device comprising a processing unit configured to:

Acquiring stream information from the received first data packet, wherein the stream information is used for indicating that the first data packet is a data packet in a first stream;

the first recording unit is used for recording a first time delay and a packet number, wherein the first time delay is the maximum time delay of a single data packet of a target stream passing through target equipment, and the packet number is the number of the data packets of the target stream received by the network equipment;

updating the number of the packets, and updating the first delay to be the delay of the first data packet passing through the target device when the delay of the first data packet passing through the target device is larger than the first delay;

and under the condition that the number of the packets is greater than or equal to a threshold value, a second recording unit is allocated to the first recording unit, wherein the second recording unit is used for recording the time delay of each data packet in n data packets passing through the target device, the n data packets are partial data packets in the data packets of the target stream received by the network device after the first data packet, the n is an integer greater than 1, and the n time delays are used for estimating the tail time delay of the first stream passing through the target device.

In a seventh aspect, the present application provides a controller comprising:

A receiving unit configured to receive information recorded in a plurality of first recording units, where the information recorded in each first recording unit includes a first delay and a packet number, where the first delay is a maximum delay of a single packet of a target stream passing through a target device, and the packet number is a number of packets of the target stream received by the network device;

and the processing unit is used for estimating the tail delay of the first flow passing through the target equipment based on the first delay recorded in the plurality of first recording units when the number of the packets is smaller than a threshold value.

In a possible implementation manner, the receiving unit is further configured to receive an identifier of an estimation window, where the identifier indicates that the information recorded in the plurality of first recording units is recorded in the estimation window, and the estimation window is a time window for estimating a tail delay of the first stream passing through the target device;

The processing unit estimates the tail delay of the first stream passing through the target device based on the first delay recorded in the plurality of first recording units, and the processing unit comprises determining the first delay recorded in the first unit as a tail delay estimated value of the first stream passing through the target device in the estimation window, wherein the first unit is the unit with the minimum first delay recorded in the plurality of first recording units.

In an eighth aspect, the present application provides a controller comprising:

The network equipment comprises a first recording unit, a receiving unit, a second recording unit and a processing unit, wherein the information recorded in the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of a first stream passing through target equipment, the packet number is the number of the data packets of the first stream received by the network equipment;

and the processing unit is used for estimating the tail delay of the first flow passing through the target equipment based on the n delays.

In a possible implementation manner, the receiving unit is further configured to receive an identifier of an estimation window, where the identifier indicates that the information recorded in the first recording unit and the second recording unit is recorded in the estimation window, and the estimation window is a time window for estimating a tail delay of the first flow passing through the target device;

The tail delay of the first stream passing through the target device is p-bit tail delay, wherein p is more than 80% and less than 100%, and the processing unit estimates the tail delay of the first stream passing through the target device based on the n delays, and the processing unit comprises:

And determining the w-th time delay in the n time delays as an estimated value of the tail time delay of the first stream passing through the target equipment in the estimated window, wherein the w-th time delay is the time delay which is sequenced to w in the n time delays sequenced from small to large, and the w is an integer which is more than 0 and less than or equal to n.

In a ninth aspect, an embodiment of the present application provides a network device that may include a memory and a processor, a transmit interface, and a receive interface coupled to the memory. The sending interface is configured to support the network device to perform the step of sending a message and/or a data packet in the communication delay estimation method provided in the first aspect. The receiving interface is configured to support the network device to perform the step of receiving a message and/or a data packet in the communication delay estimation method provided in the first aspect. Wherein the transmitting interface and the receiving interface may be integrated as a transceiver. The processor is configured to support the network device to perform other processing operations except transmission and reception of the network device in the communication method provided in the first aspect.

It should be noted that, in the embodiment of the present application, the transmitting interface and the receiving interface may be integrated together, or may be coupled through a coupler. The memory is used for storing a computer program of the communication delay estimation method described in the first aspect, and the processor is used for executing the computer program stored in the memory. The memory and processor may be integrated or coupled via a coupler.

In the present application, the computer program in the memory may be stored in advance or may be downloaded from the internet and then stored when the device is used, and the source of the computer program in the memory is not particularly limited. The coupling in the embodiments of the present application is an indirect coupling or connection between devices, units, or modules, which may be in electrical, mechanical, or other form for the exchange of information between the devices, units, or modules.

In a possible implementation manner, the processor is configured to execute program instructions stored in the memory, so that the network device performs the following operations:

The method comprises the steps of obtaining stream information from a received first data packet, wherein the stream information is identification information of a first stream to which the first data packet belongs, determining a first recording unit mapped by the first stream based on the stream information, wherein the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of a target stream passing through target equipment, the packet number is the number of data packets of the target stream received by network equipment, the target stream comprises a stream mapped to the first recording unit, updating the packet number, updating the first time delay to the time delay of the first data packet passing through the target equipment when the time delay of the first data packet passing through the target equipment is larger than the first time delay, and estimating the tail time delay of the first stream passing through the target equipment when the packet number is smaller than a threshold value.

In a tenth aspect, embodiments of the present application provide a network device that may include a memory and a processor, a transmit interface, and a receive interface coupled to the memory. Wherein the transmitting interface is configured to support the network device to perform the step of transmitting a message and/or a data packet in the communication delay estimation method provided in the second aspect. The receiving interface is configured to support the network device to perform the step of receiving a message and/or a data packet in the communication delay estimation method provided in the second aspect. Wherein the transmitting interface and the receiving interface may be integrated as a transceiver. The processor is configured to support the network device to perform processing operations of the network device other than transmission and reception in the communication method provided in the second aspect.

It should be noted that, in the embodiment of the present application, the transmitting interface and the receiving interface may be integrated together, or may be coupled through a coupler. The memory is used for storing a computer program of the communication delay estimation method described in the second aspect, and the processor is used for executing the computer program stored in the memory. The memory and processor may be integrated or coupled via a coupler.

The method comprises the steps of receiving a first data packet of a target stream, obtaining stream information from the received first data packet, wherein the stream information is used for indicating the first data packet to be a data packet in the first stream, determining a first recording unit mapped by the first stream based on the stream information, wherein the first recording unit is used for recording a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of the target stream passing through a target device, the packet number is the number of data packets of the target stream received by the network device, the target stream comprises a stream mapped to the first recording unit, updating the packet number, and updating the first time delay to be the time delay of the first data packet passing through the target device when the time delay of the first data packet passing through the target device is larger than the first time delay, distributing a second recording unit to the first recording unit when the packet number is larger than or equal to a threshold value, wherein the second recording unit is used for recording the time delay of each data packet of n data packets passing through the target device, the n data packets are the time delay of the network device, the n data packets are the time delay of the target device, and the n data packets are the whole numbers of the time delay of the data packets of the target stream received by the network device after the first data packet passing through the target device, and the n data packets of the target device pass through the target device, and n data packets are used for estimating the data 1.

In an eleventh aspect, embodiments of the present application provide a controller that may include a memory and a processor, a transmit interface, and a receive interface coupled to the memory. The sending interface is configured to support the controller to perform the step of sending a message and/or a data packet in the communication delay estimation method provided in the third aspect. The receiving interface is configured to support the controller to perform the step of receiving a message and/or a data packet in the communication delay estimation method provided in the third aspect. Wherein the transmitting interface and the receiving interface may be integrated as a transceiver. The processor is configured to support the controller to perform processing operations other than transmission and reception by the controller in the communication method provided in the third aspect.

It should be noted that, in the embodiment of the present application, the transmitting interface and the receiving interface may be integrated together, or may be coupled through a coupler. The memory is for storing a computer program of the communication delay estimation method described in the third aspect, and the processor is for executing the computer program stored in the memory. The memory and processor may be integrated or coupled via a coupler.

In a possible implementation manner, the processor is configured to execute program instructions stored in the memory, so that the controller performs the following operations:

The method comprises the steps of receiving information recorded in a plurality of first recording units, wherein the information recorded in each first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of a target stream passing through target equipment, the packet number is the number of the data packets of the target stream received by the network equipment, the target stream comprises a stream mapped to the first recording unit, the target stream comprises a first stream, and the tail time delay of the first stream passing through the target equipment is estimated based on the first time delay recorded in the plurality of first recording units under the condition that the packet number is smaller than a threshold value.

In a twelfth aspect, embodiments of the present application provide a controller that may include a memory and a processor, a transmit interface, and a receive interface coupled to the memory. The sending interface is configured to support the controller to perform the step of sending a message and/or a data packet in the communication delay estimation method provided in the fourth aspect. The receiving interface is configured to support the controller to perform the step of receiving a message and/or a data packet in the communication delay estimation method provided in the fourth aspect. Wherein the transmitting interface and the receiving interface may be integrated as a transceiver. The processor is configured to support the controller to perform processing operations other than transmission and reception by the controller in the communication method provided in the fourth aspect.

It should be noted that, in the embodiment of the present application, the transmitting interface and the receiving interface may be integrated together, or may be coupled through a coupler. The memory is configured to store a computer program of the communication delay estimation method described in the fourth aspect, and the processor is configured to execute the computer program stored in the memory. The memory and processor may be integrated or coupled via a coupler.

The method comprises the steps of receiving information recorded in a first recording unit and a second recording unit, wherein the information recorded in the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of single data packets of a first stream passing through target equipment, the packet number is the number of data packets of the first stream received by network equipment, the second recording unit is associated with the first recording unit, the information recorded in the second recording unit comprises the time delay of each data packet of n data packets of the first stream passing through the target equipment, n is an integer larger than 1, and the tail time delay of the first stream passing through the target equipment is estimated based on the n time delays.

In a thirteenth aspect, an embodiment of the present application provides a system, where the system includes a network device and a controller, where the network device is a network device according to the fifth aspect, the controller is a controller according to the seventh aspect or the eighth aspect, or the network device is a network device according to the sixth aspect, the controller is a controller according to the eighth aspect, or the network device is a network device according to the ninth aspect, the controller is a controller according to the eleventh aspect or the twelfth aspect, or the network device is a network device according to the tenth aspect, and the controller is a controller according to the twelfth aspect.

In a fourteenth aspect, embodiments of the present application provide a computer readable storage medium storing a computer program for execution by a processor to implement the method of any one of the first aspects, or for execution by a processor to implement the method of any one of the second aspects.

In a fifteenth aspect, embodiments of the present application provide a computer-readable storage medium storing a computer program that is executed by a processor to implement the method according to any one of the third aspect, or that is executed by a processor to implement the method according to any one of the fourth aspect.

In a sixteenth aspect, embodiments of the application provide a computer program product for causing a computer to carry out the method according to any one of the first aspects or causing a computer to carry out the method according to any one of the second aspects when the computer program product is run on the computer.

In a seventeenth aspect, embodiments of the application provide a computer program product for causing a computer to carry out the method according to any of the third aspect or causing a computer to carry out the method according to any of the fourth aspect when the computer program product is run on the computer.

It will be appreciated that the network device, controller, system, computer storage medium, and computer program product provided above are each for performing the method provided in any one of the first to fourth aspects. Therefore, the advantages achieved by the method can be referred to as the advantages of the corresponding method, and will not be described herein.

Drawings

The drawings that are required to be used in the embodiments of the present application will be described below.

FIGS. 1 and 2 are schematic diagrams of a system architecture according to an embodiment of the present application;

FIG. 3 is a schematic flow chart of a method according to an embodiment of the present application;

Fig. 4 and 5 are schematic diagrams of information carried in a data packet during transmission;

fig. 6 is a schematic diagram of a network device processing flow architecture according to an embodiment of the present application;

Fig. 7 is a schematic diagram of information flow direction in a network according to an embodiment of the present application;

fig. 8 is a schematic diagram of contents included in a data packet according to an embodiment of the present application;

FIG. 9 is a schematic diagram of simulation results provided by an embodiment of the present application;

fig. 10 to 13 are schematic logic structure diagrams of an apparatus according to an embodiment of the present application;

fig. 14 to 17 are schematic hardware structures of an apparatus according to an embodiment of the present application.

Detailed Description

Embodiments of the present application are described below with reference to the accompanying drawings.

First, terms related to embodiments of the present application will be described:

1. The data plane refers to a forwarding plane in a network, and is characterized by forwarding chips and forwarding storage systems and capabilities of devices in the network, and corresponds to a control plane with universal computing capability.

2. The time delay used in the embodiment of the application is the transmission time of the data packet in the network, which is calculated based on the hardware clock time stamp provided by the network equipment. In an actual deployment scenario, this may be a single-hop delay (e.g., the processing time within the device of a packet provided by the network device), or an end-to-end delay in the network (e.g., the time from the ingress of the first-hop network device to the egress of the last-hop network device).

3. Full traffic flow-full traffic flow refers to all flows in the network, and full traffic flow delay refers to delay information of each flow in the all flows.

4. The tail delay is that the delay of p% of data packets in one stream is smaller than a certain delay, and the certain delay is called p-bit delay. In the present application, when p% is between 80% and 100%, the certain delay is called tail delay or p-bit tail delay. For example, if 95% of the packets in a stream have a delay less than a certain delay, then the certain delay is referred to as a 95-bit tail delay.

An application scenario of the embodiment of the present application is described below.

Referring to fig. 1, fig. 1 is a schematic diagram of a system architecture of an application scenario according to an embodiment of the present application. As can be seen in fig. 1, the system architecture includes a control plane 110 and a data plane 120. The control plane 110 includes a controller 111, and the controller 111 may be a software defined network (software defined network, SDN) controller or an operation and maintenance center (ope ration AND MAINTENANCE CENTER, OMC) or the like. The controller 111 may be deployed in one or more servers, which may constitute a server cluster.

The data plane 120 includes g network devices 121, where g is an integer greater than 1. The network device 1 and the network device g shown in fig. 1 may further include a plurality of network devices, and the plurality of network devices may be connected in any topology. The network device 121 is used to relay data in the data plane. The network device 121 may be, for example, a forwarding device such as a switch, a router, or an access device, which may be a base station or a wireless access point, etc.

In a possible implementation, referring to fig. 2, resources and processing power in the network device in the data plane are strong, and besides logic for implementing data forwarding, own control logic may be implemented, so the capability for implementing own control logic may also be referred to as a device control plane, where the device control plane may also belong to the capability in the control plane 110. In the embodiment of the application, the device control plane can be used for processing the time delay information of the acquired data packet to estimate the tail time delay of the corresponding stream.

It should be noted that the system architecture shown in fig. 1 and fig. 2 is only an example, and the system architecture to which the embodiments of the present application are applicable is not limited to the system architecture described above.

The current measurement technology of tail delay of the stream commonly used in the industry can be mainly divided into two types, namely an in-network measurement technology represented by network flow, a technology supporting screening, sampling and copying of relevant message data in network equipment, and then uploading the message data to a controller for tail delay measurement, and an in-band operation management maintenance (in-situ operation administration AND MAINTENANCE, iOAM) technology represented by in-band network telemetry (inband network telemetry, INT) technology. Through analysis of the existing schemes, the main challenge of the full-volume flow delay measurement task is that the storage resources and logic capacity of the network equipment in a data plane are insufficient, or more storage resources and processing resources are required to be consumed for full-volume flow delay measurement in the existing schemes, and the resource cost is very high. The specific expression is as follows:

On the one hand, the throughput of the current network is extremely high, if the full-scale tape casting measurement task is realized on the control plane, huge extra bandwidth load (copy) is often brought or coverage rate is reduced and cannot be achieved (sampling/screening), and the number of concurrent streams in the current network is extremely high, and 100K-1M-level concurrent streams are often simultaneously present in the data center, so that if the aim of recording the information of each stream is achieved, the storage space available for each stream is extremely limited with the current limited data plane storage capacity.

On the other hand, the logic resources and supported operations of the network device are limited compared with the general purpose computer, so, although the current algorithm theory research has better research conclusion on the stream model split estimation, how to apply and deploy becomes difficult, so that the existing method has stronger assumption on the device capability and is difficult to deploy in practice, either discards the precision and adopts the estimation with coarser granularity, or uses more resources to realize the compromise version of the existing algorithm, abandons the expansibility, and therefore, is difficult to support the stream-by-stream delay measurement.

Therefore, the scheme of the application focuses on realizing the goal of high-precision measurement of the low-cost full-volume stream tail delay of the data plane in network equipment with limited resources and capabilities, namely focuses on reducing the resource cost of the network equipment in the tail delay measurement process of the stream. The following are specific embodiments.

Referring to fig. 3, a communication delay estimation method provided by an embodiment of the present application is shown, and the method is used to solve the above technical problems. The method may be applied to the system architecture shown in fig. 1 or fig. 2 described above. The method may include, but is not limited to, the steps of:

301. The first network device obtains flow information from the received first data packet, where the flow information is a flow identifier of a first flow to which the first data packet belongs.

In a specific embodiment, the first network device may be any one of the network devices in the data plane 120 in fig. 1 or fig. 2. The first network device may be configured to forward data packets of one or more flows.

Specifically, after receiving a data packet (for convenience of description, hereinafter referred to as a first data packet), the first network device may parse the first data packet to obtain flow information in the first data packet. The stream information may be, for example, a four-tuple, five-tuple, seven-tuple, or the like, as examples. The four-tuple comprises a source internet protocol (internet protocol, IP) address, a destination IP address, a source port, and a destination port of the flow, the five-tuple comprises a source IP address, a destination IP address, a protocol number, a source port, and a destination port, and the seven-tuple comprises a source IP address, a destination IP address, a protocol number, a source port, a destination port, a service type, and an interface index. After obtaining the flow information in the first data packet, the first network device may learn a flow to which the first data packet belongs (for convenience of description, the flow will be referred to as a first flow hereinafter).

In a possible implementation manner, the first network device may encode the obtained stream information. For example, the flow information may be represented by a symbol or value that may uniquely identify the first flow within the first network device.

302. The first network device determines a first recording unit mapped by the first stream based on the stream information, wherein the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet mapped to the stream in the first recording unit passing through the target device, and the packet number is the number of the data packets mapped to the stream in the first recording unit and received by the first network device.

In a specific embodiment, the first network device includes a data structure bitmap (bitmap), where the bitmap includes a plurality of bits, and in an embodiment of the present application, the bitmap may be used to determine whether a stream is a new stream. Specifically, after the first network device obtains the flow information of one flow, hash calculation can be performed on the flow information through a plurality of hash functions to obtain a plurality of hash values, where the plurality of hash values correspond to position serial numbers of a plurality of bits in the bitmap, so that the plurality of hash values can map the flow corresponding to the flow information into the plurality of bits. The plurality of hash functions may be two or more hash functions.

The initial value of each bit in the bitmap may be a first value, and after mapping the stream to a plurality of bits based on the calculated plurality of hash values, the value of the plurality of bits may be set to a second value. For example, alternatively, assuming that an initial value of each bit in the bitmap is 0, after mapping the stream to a plurality of bits based on the calculated plurality of hash values, a value of 1 in the plurality of bits may be set. Or alternatively, assuming that the initial value of each bit in the bitmap is 1, after mapping the stream to a plurality of bits based on the calculated plurality of hash values, the value in the plurality of bits may be set to 0.

Based on the logic, the first network device performs hash calculation on the flow information of the first flow through the hash functions to obtain hash values, maps the first flow into a plurality of bits in a bitmap based on the hash values, and if a value in at least one bit in the plurality of bits is the first value, it can be determined that the first flow is a new flow, and then the first data packet is a data packet in the first flow received by the first network device. The new flow refers to a flow that has not been mapped into the bitmap. If the value in each of the plurality of bits is the second value, it indicates that the first stream is not a new stream, and the first packet is a packet in the first stream received again by the first network device.

In the embodiment of the present application, each bit in the bitmap is associated with a first recording unit, and then the first recording unit associated with a bit is also a unit mapped to the stream of bits. The first recording unit may be configured to record the number of packets and the first delay.

The number of packets is the number of data packets received by the first network device mapped to the stream in the first recording unit. Optionally, for a certain first recording unit, if the stream mapped to the first recording unit is one, the number of packets in the first recording unit is the number of data packets of the one stream received by the first network device. Optionally, for the certain first recording unit, if the number of the streams mapped to the first recording unit is multiple, that is, a hash collision occurs, the number of the packets in the first recording unit is the sum of the numbers of the data packets of the multiple streams received by the first network device.

The first delay is the maximum delay of a single packet mapped to the stream in the first recording unit passing through the target device.

In a possible implementation manner, the target device is the first network device. Or in another possible implementation manner, the first network device is a last hop device in the data plane mapped to the stream in the first recording unit, and the target device includes a plurality of devices, where the plurality of devices are devices through which a single data packet in the stream mapped to the first recording unit passes in the data plane.

Alternatively, in the case where the target device is the first network device or in the case where the target device includes a plurality of devices, the processing delay on the network device, especially the queuing delay waiting to be processed in the network device, is a main factor causing delay fluctuation, compared to the substantially fixed link delay, so in the embodiment of the present application, the processing time of the network device may be used as the delay, where the processing time is the time between receiving a data packet from the network device and sending the data packet from the network device, that is, the processing time is the delay of the data packet passing through the network device. For the case that the target device is the first network device, the first delay is the maximum delay of the single data packet passing through the first network device. For the case where the target device includes a plurality of devices, the first delay is a maximum value of a sum of delays of the single packet passing through each of the plurality of devices. For example, assuming that the plurality of devices are device 1 and device 2, device 2 receives the first packet and the second packet in the first stream, where the first packet has a delay of 1 ms and 0.9 ms through device 1 and device 2, respectively, and the second packet has a delay of 1.1 ms and 1 ms through device 1 and device 2, respectively, then the first delay in the first recording unit mapped by the first stream in device 2 is 2.1 ms. Based on the foregoing description, the sum of the processing time of the data packet by all the network devices passing through the data plane is the time delay of the whole transmission process of the data packet in the data plane. How the delay is obtained is described in the following and will not be described in detail here.

Or alternatively, in the case that the target device includes a plurality of devices, a transmission delay of a data packet on a transmission path in a data plane may be taken as a delay of an entire transmission process of the data packet in the data plane, where the transmission delay includes a link delay in the transmission path and a delay caused by processing time in the plurality of devices in the transmission path. That is, in this case, the first delay may be the maximum value of the delay of the single packet in the stream mapped to the first recording unit during the entire transmission. For example, assuming that the first network device receives the first packet and the second packet in the first stream, the first packet has a delay of 2.5 ms during the entire transmission process, and the second packet has a delay of 2.8 ms during the entire transmission process, the first delay in the first recording unit mapped by the first stream in the first network device is 2.8 ms. The transmission delay is the delay between the time the ingress network device receives the data packet and the time the egress network device sends the data packet. The ingress network device is the first hop device to forward the data packet in the data plane and the egress network device is the last hop device to forward the data packet in the data plane. How the delay is obtained is described in the following and will not be described in detail here.

In a possible implementation manner, the first recording unit may be further configured to record an exclusive or result of the stream information and the number of streams. The number of streams is the number of streams mapped to the first recording unit, and the exclusive-or result of the stream information is the exclusive-or result of the stream information of the stream mapped to the first recording unit. Specifically, if the number of streams is 1, the exclusive or result of the stream information is the stream information itself, or, when the number of streams mapped to the first recording unit is one, the position in the first recording unit where the exclusive or result of the stream information is recorded is the stream information itself. If the number of the streams is greater than 1, that is, a plurality of streams are mapped to the same first recording unit, the exclusive or result of the stream information is the result obtained by exclusive or operation of the plurality of streams. In a computer, all information is represented by binary data consisting of 0 and 1, and therefore, the result of exclusive or of the stream information is also binary data consisting of 0 and 1.

Based on the description, the first network device maps the first stream into a plurality of bits in the bitmap, from which a plurality of first recording units of the first stream map can be determined.

By mapping the stream into the bitmap, the storage resource can be saved for the first network device, and the calculation difficulty can be reduced so as to save the calculation resource.

303. The first network device updates the number of packets and updates the first delay to a delay of the first data packet passing through the target device if the delay of the first data packet passing through the target device is greater than the first delay.

In a specific embodiment, after the first network device determines the plurality of first recording units of the first stream map, information in the plurality of first recording units may be updated adaptively, which is described in the following case.

In the first case, the first stream is a new stream and no hash collision occurs in the bits of the first stream map. In this case, the first network device may set the value of the position of the number of packets recorded in the plurality of first recording units to 1 if no information is recorded in the plurality of first recording units of the first stream map or if the recorded information is the original default value. In addition, for the first delay in the plurality of first recording units, the first network device may acquire the delay of the first packet passing through the target device, and then record the delay to a position in the plurality of first recording units where the first delay is recorded.

Specifically, a delay acquisition module may be disposed in the first network device, where the delay acquisition module may acquire a delay of the first data packet passing through the target device.

Optionally, for the case that the target device is the first network device, the delay obtaining module may obtain, by measurement and calculation, a processing time of the first data packet in the first network device, where the processing time is a delay of the first data packet passing through the first network device. Specifically, the first network device may measure a time stamp of arrival of the first data packet at the first network device, estimate a time stamp of the first data packet sent from the first network device, and subtract the previous time stamp from the subsequent time stamp to obtain a time amount, where the time amount is a processing time, i.e. a time delay, of the first data packet in the first network device. The first network device then records the calculated delay to a location in the plurality of first recording units where the first delay was recorded.

It should be noted that, the timestamp sent by the first data packet from the network device is a timestamp calculated according to the condition of the data packet sending queue, in this embodiment of the present application, the delay obtained by calculation of the delay obtaining module allows an acceptable error to exist, or in this embodiment of the present application, a delay obtained by calculation of the delay obtaining module may be used as the correct delay of a single data packet passing through the network device. Alternatively, the time delay acquisition module may estimate time accurate to nanoseconds, thereby improving the accuracy of time delay estimation.

Alternatively, in the case where the target device includes a plurality of devices, in a possible implementation manner, the processing time of the network device may be used as the delay. Then, for the first data packet, processing logic is provided on the network device that needs to forward the first data packet in the data plane, to calculate the processing time of the first data packet in the network device.

Specifically, for the ingress network device, after the time delay of the first data packet passing through the ingress network device is calculated, the time delay is added to the packet header of the first data packet, and the first data packet is sent to the next hop network device together with the first data packet. Alternatively, the packet header may be a custom-added packet header dedicated to carrying delays. After the next hop network device receives the first data packet carrying the time delay, the processing time of the first data packet in the next hop network device is calculated as well according to the logic, namely the time delay, then the calculated time delay is added with the time delay in the received packet header of the first data packet to obtain a new time delay, and the new time delay is updated into the packet header of the first data packet and is sent to the next hop device. And the first network equipment acquires the time delay in the packet head of the first data packet until the first data packet reaches the last hop equipment in the data plane, calculates the time delay of the first data packet in the first network equipment, and adds the two time delays to obtain the total time delay, wherein the total time delay is the time delay of the first data packet passing through the plurality of equipment. After obtaining the total delay, the first network device may remove a packet header dedicated to carrying the delay from the first data packet. This operation of adding delay to the existing delay in the data packet and transmitting in each hop network device may be implemented, for example, using the INT technique described above. The first network device then records the total delay to a location of the plurality of first recording units where the first delay was recorded. To facilitate an understanding of this embodiment, reference may be made to fig. 4 by way of example.

Fig. 4 shows a schematic topology of a network device in a simple data plane and shows information carried by a data packet during transmission, assuming that the transmission path of the first data packet in the data plane is network device 1-network device 2-network device 5-network device 6. The delay carried in the first data packet sent by the network device 1 is the delay a of the first data packet passing through the network device 1. Then, the first data packet is sent to the network device 2, and the network device 2 acquires the delay b of the first data packet after the first data packet passes through itself, and encapsulates the delay a+b into the first data packet. Then, the first data packet is sent to the network device 5, and the network device 5 acquires the time delay c of the first data packet after the first data packet passes through the time delay c, and encapsulates the time delay a+b+c into the first data packet. Then, the first data packet carrying the time delay a+b+c is sent to the network device 6, the network device 6 obtains the time delay d of the first data packet passing through itself, adds d to the time delay a+b+c to obtain the time delay a+b+c+d, and then records the time delay a+b+c+d to the positions of the plurality of first recording units where the first time delay is recorded.

It should be noted that, in the embodiment of the present application, although the time delays carried in the first packets forwarded in the different network devices are different, as long as the load (payload) in the first packets is unchanged, the packets carrying the time delay information are still referred to as the first packets.

Alternatively, in the case that the target device includes multiple devices, in a possible implementation manner, a transmission delay of a data packet on a transmission path in a data plane may be used as a delay of an entire transmission process of the data packet in the data plane. Then, for the first data packet, on the ingress network device forwarding the first data packet in the data plane, the ingress network device may measure a time stamp of arrival of the first data packet at the ingress network device, and then add the time stamp to the first data packet header, and forward the first data packet along with the egress network device of the data plane, i.e., the first network device. Alternatively, the header may be a custom-added header dedicated to carrying a timestamp. The first network device may obtain a time stamp in the first data packet, then estimate a time stamp sent by the first data packet from the first network device, and subtract the previous time stamp from the subsequent time stamp to obtain a time amount, where the time amount is a time delay of the first data packet passing through the target device. After obtaining the amount of time, the first network device may remove a header of the first data packet that is dedicated to carrying the timestamp. The operation of adding a time stamp to the data packet in the ingress network device and transmitting the data packet to the egress network device may be implemented, for example, using the INT technique described above. The first network device then records the time delay to a location in the plurality of first recording units where the first time delay was recorded. In such an implementation, clock synchronization of the network devices in the data plane is required, so that the calculated delay is accurate. To facilitate an understanding of this embodiment, reference may be made to fig. 5 by way of example.

Fig. 5 shows a schematic topology of a network device in a simple data plane and shows information carried by a data packet during transmission, assuming that the transmission path of the first data packet in the data plane is network device 1-network device 2-network device 5-network device 6. The first data packet sent out by the network device 1 carries the time stamp when the first data packet arrives at the network device 1, i.e. the first time stamp shown in fig. 5, in the case that the network device 1 is the ingress network device. Then, the first data packet carrying the first timestamp is sent to the network device 6 through the network device 2 and the network device 5, the network device 6 estimates the timestamp sent by the first data packet from the network device 6, and subtracts the previous timestamp from the subsequent timestamp to obtain a time amount, where the time amount is the time delay of the first data packet passing through the target device. The network device 6 records the amount of time to the position of the first recording unit where the first time delay is recorded.

In a possible implementation manner, the first recording unit may be further configured to record an exclusive or result of the stream information and the number of streams. If the first recording unit includes the exclusive-or result of the stream information, the first network device may save the stream information of the first stream to the location of the exclusive-or result of the stream information recorded in the first recording unit of the first stream map, because no hash collision occurs in the plurality of bits of the first stream map. If the number of streams is included in the first recording unit, the first network device may set the number of streams recorded in the first recording unit of the first stream map to 1.

In a second case, the first stream is a new stream and a hash collision occurs in at least one bit of the plurality of bits mapped by the first stream.

In this case, for the first recording unit of the bit map having no hash collision among the plurality of bits, the number of packets and the update of the first delay may refer to the corresponding descriptions in the first case, which are not described herein. For the at least one first recording unit of the at least one bit map where the hash collision occurs, the first network device may increase the number of packets in the at least one first recording unit by 1 count, i.e. replace the number of packets obtained after increasing the number of packets by 1 count by the original number of packets. For the first delay in the at least one first recording unit, the first network device may obtain the delay of the first data packet passing through the target device according to the method described in the first case, then compare the obtained delay with the first delay recorded in each unit of the at least one first recording unit, and if the obtained delay is greater than the minimum first delay in the at least one first recording unit, replace the minimum first delay in the at least one first recording unit with the obtained delay.

In a possible implementation manner, the first recording unit may be further configured to record an exclusive or result of the stream information and the number of streams.

If the first recording unit includes an exclusive or result of the stream information, the first network device may save the stream information of the first stream to a location of the exclusive or result of the stream information recorded in the first recording unit for the first recording unit having no bit map with hash collision among the plurality of bits. For the at least one first recording unit of the at least one bit map where the hash collision occurs, the first network device may perform an exclusive-or operation on the stream information of the first stream and information (may be information of one stream or may be a result of exclusive-or of stream information of a plurality of streams) in a position where an exclusive-or result of the stream information is recorded in the first recording unit, to obtain an exclusive-or result, and then store the calculated exclusive-or result in the position of the exclusive-or result of the stream information recorded in the first recording unit.

If the number of streams is included in the first recording unit, the first network device may set the number of streams recorded in the first recording unit of the first stream map to 1 for the first recording unit of the bit map having no hash collision among the plurality of bits. For the at least one first recording unit mapped by the at least one bit with the hash collision, the first network device may increase the number of streams in the at least one first recording unit by 1 count, i.e. replace the number of streams obtained after the increase of 1 count with the original number of streams.

In a third case, the first stream is not a new stream and no hash collision occurs in the bits mapped by the first stream.

In this case, it is indicated that the first packet is a packet in the first stream received again by the first network device, and the number of packets and the first delay of the packet of the first stream received before are recorded in the plurality of first recording units of the first stream map. The first network device may increment the number of packets in the first recording unit of the first stream map by 1 count, i.e. replace the number of packets obtained after incrementing by 1 count by the original number of packets. In addition, for the first delay in the plurality of first recording units, the first network device may acquire the delay of the first packet passing through the target device, then compare the acquired delay with the first delay recorded in the first recording unit, and if the acquired delay is greater than the first delay recorded in the first recording unit, update the first delay in the plurality of first recording units to the acquired delay by the first network device. If the acquired time delay is not greater than the first time delay recorded in the first recording unit, the first time delay in the plurality of first recording units is kept unchanged.

In a possible implementation manner, the first recording unit may be further configured to record an exclusive or result of the stream information and the number of streams. If the first recording unit includes the exclusive or result of the stream information, since hash collision does not occur in the plurality of bits of the first stream map, the stream information of the first stream is still recorded in the position of the exclusive or result of the stream information recorded in the plurality of first recording units of the first stream map, and remains unchanged. If the number of streams is included in the first recording unit, since hash collision does not occur in the bits mapped by the first stream, only the first stream is mapped in the corresponding first recording units, and thus the number of streams recorded in the first recording units mapped by the first stream is maintained to be 1.

In a fourth case, the first stream is not a new stream and at least one bit of the plurality of bits mapped by the first stream has a hash collision.

In this case, for the first recording unit of the bit map having no hash collision among the plurality of bits, the number of packets and the update of the first delay may refer to the corresponding descriptions in the third case, which are not described herein. For at least one first recording unit of the at least one bit map in which the hash collision occurs, the number of packets and the update of the first delay may refer to the corresponding descriptions in the second case, which are not described herein again.

In a possible implementation manner, the first recording unit may be further configured to record an exclusive or result of the stream information and the number of streams. Since the above-described first stream is not a new stream, the exclusive or result of stream information and the number of streams in the plurality of first recording units of the first stream map are kept unchanged, and a corresponding description in the above-described third case can be seen in particular.

In a possible implementation manner, the first data packet is a data packet received by the first network device in a preset time window, where the preset time window may have a size between 10 ms and 100 ms, and in this case, the first network device uses the time window as an estimated duration segment to estimate a delay of the first flow, and then the first delay is a maximum delay of a single data packet mapped to the flow in the first recording unit passing through the target device in the time window.

Or in another possible implementation manner, the first data packet is any data packet in the first stream received by the first network device, where the first network device estimates the delay of the first stream by using the overall transmission time of the first stream as an estimated duration, and then the first delay is the maximum delay of a single data packet of the stream passing through the target device within the overall transmission time of the stream mapped to the first recording unit.

In the embodiment of the present application, the preset time window or the overall transmission time of the stream may be collectively referred to as an estimation window, that is, the estimation window is a time window for estimating the delay of the stream. In the embodiment of the application, the purpose is to estimate the tail delay of the stream, and then the estimation window can also be said to be a time window for estimating the tail delay of the stream. The information recorded in the first recording unit is also estimated in the estimation window.

In the embodiment of the present application, the estimation of the tail delay of the first flow passing through the target device includes two different processing modes, and a specific processing mode may be determined by determining whether the number of data packets of the first flow received by the first network device in the estimation window is greater than a threshold. Specifically, after the first network device updates the plurality of first recording units of the first flow map, it may be determined whether the number of packets recorded in the plurality of first recording units is greater than a threshold, where, of course, the data packets corresponding to the number of packets are received by the first network device within the estimation window. The threshold may be, for example, 100, 1000, 10000, etc., and may be set according to the desired measurement split and the desired accuracy, etc., which is not limited by the present application.

In a possible implementation manner, if the number of packets recorded in the plurality of first recording units is smaller than the threshold, if the estimation window has not yet ended, the first network device continues to receive the data packets of the first stream, and then updates the information in the plurality of first recording units of the first stream map, where a specific update may be referred to as the description corresponding to step 303. After the estimation window is finished, the first network device can find a plurality of first recording units of the first stream map according to the hash value of the stream information of the first stream, the first network device obtains a plurality of first time delays recorded in the plurality of first recording units of the first stream map, and then the minimum value in the plurality of first time delays is taken as an estimated value of the tail time delay of the first stream passing through the target device in the estimation window.

In this processing manner, since the number of data packets of the first stream in the estimation window is smaller than the threshold, the number of data packets is relatively smaller, and then, the tail delay difference between the 80-bit tail delay and the 100-bit tail delay of the first stream in the estimation window is smaller, and the first delay recorded in the first recording unit of the first stream map is the maximum delay of the single data packet passing through the target device in the estimation window, therefore, the first delay recorded in the first recording unit of the first stream map can be used to estimate any tail delay between the 80-bit tail delay and the 100-bit tail delay of the first stream in the estimation window, and the estimation error is smaller and is within an acceptable range. Also, because there may be a hash collision, if the first delay of the unit record with the hash collision among the plurality of first record units of the first stream map is different from the first delay of the unit record without the hash collision, based on the principle of replacing the smaller delay with the larger delay, the first delay of the unit record with the hash collision is not smaller than the first delay of the unit record without the hash collision, and therefore, the smallest first delay among the plurality of first record units of the first stream map is selected as the estimated value of the tail delay of the first stream passing through the target device in the estimated window.

In a possible implementation manner, for at least one first recording unit of the bit map, where a hash collision exists in bits of the first stream map, after the end of the estimation window, the first network device may perform an exclusive-or operation on an exclusive-or result of the stream information in the at least one first recording unit and the stream information of the first stream again in a process of decoding the information in the first recording unit, and record the result of the exclusive-or operation in the at least one first recording unit, so that the stream information of the first stream may be deleted from the at least one first recording unit. Meanwhile, the first network device may subtract the number of streams in the at least one first recording unit by 1, and subtract the number of packets from the number of data packets of the first stream received in the estimation window, but the first delay is not changed. By these processes, the relevant information of the first stream can be deleted from the at least one first recording unit, which can be prepared for recording the relevant information of the first stream within the next estimation window in case of a plurality of estimation windows.

For the first recording units of the bit map, where there is no hash collision in the bits of the first stream map, after the end of the estimation window, the first network device may clear all the information recorded in the first recording units, and for the case where there are multiple estimation windows, the first recording units may prepare related information for recording the first stream in the next estimation window.

In a possible implementation manner, if the number of packets recorded in the plurality of first recording units is greater than or equal to the threshold, when the number of packets is equal to the threshold, if the estimation window is not finished yet, the first network device configures an associated second recording unit for each of the plurality of first recording units, and the first recording units and the second recording units are associated by indexes, and the first network device may configure a plurality of index recording units for exclusively recording index information between the first recording units and the second recording units, and each index recording unit records index information between one first recording unit and one second recording unit. N time delays may be recorded in the second recording unit, n being an integer greater than 1. The n time delays are time delays when n data packets in a target stream received by the first network device pass through the target device after the number of the packets is equal to the threshold value. If the number of packets recorded in the first recording unit just reaches the threshold after the first network device receives the first data packet, the n data packets are n data packets in the data packets of the target stream, which are received by the first network device after the first data packet. The target stream is the stream mapped to the first recording unit, and is the first stream if the stream mapped to the first recording unit is only the first stream, and is the plurality of streams if the stream mapped to the first recording unit is the plurality of streams including the first stream.

Specifically, when the second recording unit is configured, initial values of n delays may be configured by default in the second recording unit, or the second recording unit may be initially empty. In the embodiment of the application, the n time delays in the second recording unit can be updated in a polling mode. After the number of packets recorded in the first recording unit is equal to the threshold, the delays, corresponding to the first n packets of the target stream received by the first network device, passing through the target device may be sequentially recorded in the positions where the n delays are recorded in the second recording unit. Then, after the n packets, each time the first network device receives a packet of the target flow, a delay in the second recording unit may be determined by polling, and then, in a case where the delay is smaller than a delay of the received packet passing through the target device, the delay in the second recording unit is replaced by a delay of the received packet passing through the target device.

The polling mode refers to sequentially and one by one inquiring each time delay from a certain time delay in the n time delays according to a preset sequence until the inquiring of the n time delays is completed, sequentially and one by one inquiring each time delay according to the preset sequence again from the certain time delay until the inquiring of the n time delays is completed again, and circularly executing the inquiring operation. For ease of understanding, the following is illustrative. See table 1.

TABLE 1

Position of time delay	1	2	3	4	5
						Value of time delay	0.3 Ms	0.35 Ms	0.28 Ms	0.32 Ms	0.26 Ms

Table 1 exemplarily shows the time delays recorded in one second recording unit. It is assumed that the second recording unit may record the delays of the data packets of 5 target streams passing through the target device, and the delays at the corresponding positions are referred to in table 1. It is assumed that the 5 delays recorded in table 1 are delays of the first 5 data packets of the first stream received by the first network device passing through the target device after the number of packets recorded in the first recording unit is equal to the threshold. In addition, it is assumed that the polling method is to sequentially inquire about the time delay of the position 5 from the time delay of the position 1, then to repeatedly inquire about the time delay of the position 1, and then to sequentially inquire about the time delay of the position 5, and then to circulate.

Based on table 1, the first network device receives the 1 st packet of the target flow after the number of packets is equal to the threshold, and obtains the delay of the 1 st packet passing through the target device, which is 0.32 ms. The first network device then first queries for a delay in position 1 in the second recording unit, which is 0.3 ms, based on the polling scheme. Since 0.32 ms is greater than 0.3 ms, the first network device replaces the time delay 0.3 ms in this location 1 with 0.32 ms. After a round of operation, i.e. after the first network device receives 5 first stream data packets after the number of packets equals the threshold, and polls the second recording unit for 5 delays in the second recording unit, see table 2.

TABLE 2

Position of time delay	1	2	3	4	5
						Value of time delay	0.32 Ms	0.35 Ms	0.3 Ms	0.32 Ms	0.28 Ms

Based on table 2, the first network device receives the 6 th packet of the target flow after the number of packets is equal to the threshold, and obtains the delay of the 6 th packet passing through the target device, which is 0.25 ms. The first network device then queries for a delay in location 1 in the second recording unit, which is 0.32 ms, based on the manner of the poll. Since 0.25 ms is less than 0.32 ms, then the first network device will keep the delay 0.32 ms in this location 2 unchanged, i.e. the delay in this location 1 is not updated this time.

Optionally, since the tail delay of the target stream passing through the target device in the estimation window is estimated based on the n delay recorded in the second recording unit, if the number of packets of the target stream is very large, and the n delay in the second recording unit is updated in the polling manner, the n tail delay obtained finally is the largest n tail delay, and the n tail delay can be used for more accurately estimating the tail delay approaching 100 minutes, but is used for estimating the tail delay such as 80 minutes, 85 minutes, 90 minutes or 95 minutes, even 99 minutes, and the error is large, and the estimated tail delay is inaccurate. To solve this problem, the embodiment of the present application provides the following operations:

On the basis of updating the second recording unit in the polling mode, after the number of the packets is equal to the threshold value, the first network device receives a data packet of the target flow again after receiving a preset number of data packets of the target flow, can randomly inquire a time delay in the second recording unit, and then compares the time delay of the data packet passing through the target device with the value of the inquired time delay. When the time delay of the data packet passing through the target device is smaller than one time delay of the query, replacing one time delay of the query with the time delay of the data packet passing through the target device, and recording in the second recording unit, otherwise, not updating one time delay of the query.

The preset number can be 10, 50 or 100, etc., and the specific value of the preset number is not limited in the application. For ease of understanding, the following is illustrative.

Still further described based on the above table 1 as an example, assuming that the preset number is 8, after the number of packets is equal to the above threshold, the first network device receives the data packets of 8 target flows, and polls the second recording unit for 5 delays in the second recording unit, see table 3.

TABLE 3 Table 3

Position of time delay	1	2	3	4	5
						Value of time delay	0.32 Ms	0.35 Ms	0.31 Ms	0.32 Ms	0.28 Ms

Based on table 3, the first network device receives the 9 th packet of the target flow after the number of packets is equal to the threshold, and obtains the delay of the 9 th packet passing through the target device, which is 0.27 ms. The first network device then randomly queries for a time delay in the time delays of 5 locations of the second recording unit, assuming that the time delay of location 5 was randomly queried for 0.28 milliseconds. Since 0.27 ms is less than 0.28 ms, the first network device replaces the time delay of 0.28 ms in this location 5 with 0.27 ms, see in particular table 4.

TABLE 4 Table 4

Position of time delay	1	2	3	4	5
						Value of time delay	0.32 Ms	0.35 Ms	0.31 Ms	0.32 Ms	0.27 Ms

It should be noted that, since there is a hash collision, the number of packets of the bit map unit having the hash collision is larger than the number of packets of the bit map unit having no hash collision among the plurality of first recording units. For the unit with hash collision bit mapping, a second recording unit may be configured for the unit as long as the number of packets reaches the threshold, then the second recording unit is used to record the time delay of the part of the data packets received by the first network device passing through the target device after the number of packets is greater than the threshold in the multiple streams mapped to the unit, and then the operation of updating the second recording unit is described above, which is not repeated herein.

Based on the updating manner of the second recording unit, after the estimation window is ended, the first network device searches for the associated second recording unit based on the plurality of first recording units of the first stream map, and specifically, the second recording unit associated with the first recording unit can be searched for through the index information recorded in the index recording unit. Then, the first network device acquires n delays recorded in the second recording unit, and estimates a tail delay of the first stream passing through the target device within the estimation window based on the n delays. Specifically, assuming that the n delays are ordered from small to large, the p-bit tail delay of the first stream in the estimation window can be estimated by using the delay ordered as w in the n delays, where the delay ordered before w is less than or equal to the p-bit tail delay, and w is an integer greater than 0 and less than or equal to n.

In a possible implementation, in order to avoid data confusion caused by hash collision, n delays in the second recording unit associated with the first recording unit with the number of streams being 1 or the number of streams being the smallest may be selected to estimate the tail delay of the first stream passing through the target device within the estimation window.

In a possible implementation manner, it is assumed that N number of data packets of the first flow received by the first network device in the estimation window are N, where N is an integer greater than or equal to N. Then, the w may be N (1-1/N) ^N(1-p), that is, the p-th tail delay of the first stream in the estimation window may be estimated by using the N (1-1/N) ^N(1-p) -large delays of the N delays, where the N (1-1/N) ^N(1-p) -large delay is an estimated value of the N-th major delay of the N delays of the N packets in the first stream passing through the target device. Specific estimation procedures can be exemplified by the following calculation formulas:

Wherein a _K represents the K-th large delay among the N delays passing through the target device, a _j represents the j-th large delay among the N delays, C represents a set of N delays in the second recording unit, C _i represents the delay of the i-th position record in the second recording unit, P (a _K e C) represents the probability that a _K is recorded by any position of the second recording unit, a _K meet c_i represents the comparison of a _K with the delay of the i-th position record in the second recording unit in polling, Λ represents "and", a _K＝max(a_j|a_j meet c_i) represents a _K equal to the maximum value of all delays compared with the delay of the i-th position record. The formula calculates the probability that a _K is recorded.

Assuming that the probability of a _K meet c_i is 1/n, i.e. that the probability of a _K encountering each of the numbers C is the same, the difference between the number of times that the delays of different positions are actually encountered in the polling manner described above is at most 1, and therefore, here, it is assumed that the probability of a _K meet c_i is 1/n, the error is small. Based on this assumption, then:

Then

Wherein, c _i＞a_N*p represents that the delay of the ith position record is larger than the delay of the p-branch bit tail. E (Num (c _i＞a_N*p)) represents the mathematical expectation of the number of delays greater than the p-bit tail delay in the n delays, E (Num (c _i≤a_N*p)) represents the mathematical expectation of the number of delays not greater than the p-bit tail delay, that is, theoretically, the expectation of the p-bit tail delay is the nth delayThe large recording delay, therefore w may be n (1-1/n) ^N(1-p).

In a possible implementation manner, when the number of packets of the first stream is very large, the n delays in the second recording unit are recorded correspondingly in a manner that small delays are randomly replaced by large delays at regular intervals so as to reduce the final estimation error. Then, the matched tail delay estimation processing mode can be referred to as the following description:

It is assumed that N number of data packets of the first flow received by the first network device in the estimation window are N, where N is an integer greater than or equal to N. Then, the w may be N (1-q/N) ^N(1-p), that is, the p-th tail delay of the first stream in the estimation window may be estimated by using the delay with the order of N (1-q/N) ^N(1-p) in the N delays, where the N (1-q/N) ^N(1-p) large delay is an estimated value of the N-th large delay of the N delays passing through the target device corresponding to the N data packets in the first stream, and q is a real number greater than 0 and less than 1. Specific estimation procedures can be exemplified by the following calculation formulas:

the meaning of the related character expression can be referred to the related description in the above formula (1), and will not be repeated here.

Similarly, assuming that the probability of a _K meet c_i is 1/n, that is, that the probability of a _K encountering each of C is the same, the difference between the number of times that delays of different positions are actually encountered in the polling manner described above is at most 1, and therefore, the error of assuming that the probability of a _K meet c_i is 1/n is small here. The accurate analysis of the problem is related to the time sequence of the arrival of the time delay, the solution is complex and difficult to solve accurately, so that the mode of replacing the original large time delay with the small time delay at random at regular intervals of packet numbers can be assumed to be mutually independent from the default recording mode of the second recording unit, namely, the default recording mode of the second recording unit is assumed to be executed with the probability of q when polling comparison is carried out each time, the mode of replacing the original large time delay with the random small time delay with the probability of 1-q is assumed, and q is a real number which is set to be larger than 0 and smaller than 1. Based on this assumption, then:

Then

Wherein, q represents a default recording manner of the second recording unit performed with a probability of q, q is a real number set to be greater than 0 and less than 1, and the meaning of the related character representation may be referred to the description related to the above formula (1), which is not repeated here.

In a possible embodiment, regarding the processing of the information recorded in the plurality of first recording units of the first stream map after the end of the above estimation window, reference may be made to the corresponding description in the case where the above number of packets is smaller than the threshold value. Regarding the plurality of second recording units with which the plurality of first recording units are associated, for the second recording units for which there is no hash collision, the first network device may free up the storage space of these second recording units for recording storage of subsequent other information.

Based on the method for estimating the tail delay, the first network device may estimate the tail delay of the first stream passing through the target device in the estimation window. For the case that the estimation window is the preset time window, the transmission process of the first stream may include a plurality of preset time windows, the first network device may estimate, in each window of the plurality of preset time windows, a tail delay of the first stream passing through the target device in the window, and a specific estimation process may refer to the foregoing description. The first network device may send the tail delay of the first stream passing through the target device to the controller for subsequent summary analysis and processing every time the tail delay is estimated within a predetermined time window. Or the first network device may send the plurality of tail delays to the controller together for subsequent summary analysis and processing after estimating the tail delays of the first stream passing through the target device in the plurality of preset time windows. For the case that the estimation window is the overall transmission time of the stream, the first network device may send the estimated tail delay of the first stream passing through the target device to the controller after estimating the tail delay of the first stream passing through the target device, and the controller further performs summary analysis and processing according to the tail delay information.

The controller may receive, in addition to the tail delay information of the first stream passing through the target device from the first network device, tail delay information of the first stream passing through the target device from other network devices through which the first stream passes in the data plane, where the estimating and processing operations of each of the other network devices with respect to the tail delay of the first stream passing through the target device are the same as those of the first network device, and will not be described again.

After the controller receives the tail delay information of the first stream sent by the first network device and the other network devices passing through the target device, the tail delay information can be summarized in the time sequence, for example, the tail delay estimation data under a longer time window (until the life cycle of the stream) can be obtained by adopting a weighting and bit-solving mode with the number of packets as the weight. Then, based on the tail delay estimation data, tail delay mutation early warning can be performed according to the network operation and maintenance requirements, so that congestion and other anomalies are detected, tail delay network space drawing can be performed, and delay-based network slice analysis and network bottleneck detection are obtained. According to the obtained full-volume stream tail delay data, various network measuring tools oriented to users and operation and maintenance personnel can be deployed.

In a possible implementation manner, the operation of estimating the tail delay of the first stream in the corresponding estimation window based on the information recorded in the first recording unit or the first recording unit and the second recording unit may be implemented by a controller. Specifically, the first network device records relevant information in the first recording unit of the first stream map or the first recording unit and the second recording unit in the estimation window, and the specific recorded information refers to the foregoing description and is not repeated herein. Then, after the end of the estimation window, the first network device transmits the information recorded in the first recording unit, or the first recording unit and the second recording unit, to the controller, and optionally, the information in the index recording unit that records the index information between the first recording unit and the second recording unit is also transmitted to the controller together. The controller estimates the tail delay of the first stream passing through the target device in the corresponding estimation window based on the information, and the specific estimation mode can be referred to the estimation mode of the first network device, which is not described herein.

Alternatively, for the case where only the above first delay and the number of packets are recorded in the first recording unit, when the first network device sends the information in the first recording unit to the controller, the stream information of the stream mapped to the first recording unit may be sent to the controller together, so that the controller associates the information recorded in the first recording unit with the corresponding stream.

For a better understanding of the communication delay estimation method described above, the following is further illustrated with reference to the accompanying drawings.

Referring to fig. 6, fig. 6 illustrates a schematic diagram of a processing flow architecture of the first network device. In fig. 6, the whole process involves a bloom filter, a stream encoder, a long stream checking unit, a long stream delay recording unit, and an information recording unit.

Specifically, the first network device hashes the stream information of the first stream into a plurality of bits in the bitmap through the bloom filter, and can determine a plurality of first recording units of the information recording units mapped by the first stream through the plurality of bits.

The first network device performs the exclusive-or operation of the above-described introduction stream information by the above-described stream encoder, records the result of the exclusive-or operation in the first recording unit, or may record the stream information of the first stream in the first recording unit, and may record delay information, the number of packets, and the number of streams in a plurality of first recording units of the first stream map, and returns the number of packets recorded in each of the plurality of first recording units.

The first network device checks whether the number of packets returned by the stream encoder is equal to the threshold value by the long stream checking unit, and if so, allocates a second recording unit to the first recording unit corresponding to the number of packets equal to the threshold value, and allocates an index recording unit for recording index information between the first recording unit and the second recording unit, and in addition, returns information of a specific position of the second recording unit in the information recording unit.

And when the number of the packets recorded in the first recording unit corresponding to the number of the packets equal to the threshold value is larger than the threshold value, the first network device records the time delay of the larger data packet passing through the target device into the second recording unit through the long-stream time delay recording unit according to the polling mode. Optionally, the first network device may further randomly select, by the long-stream delay recording unit, one delay to be replaced by a smaller delay from the delays recorded by the second recording unit according to the foregoing description of every certain number of data packets.

The specific implementation of the operations performed by the first network device through the bloom filter, the stream encoder, the long stream checking unit and the long stream delay recording unit may refer to the foregoing related description, which is not repeated herein.

In fig. 6, it can also be seen that the total storage size allocated to all the first recording units in the information recording units is k x (9+x) bytes (B), k being the number of bits in the bitmap, since each bit maps one first recording unit, k being an integer greater than 1. In addition, four pieces of information of exclusive or result of stream information, stream number, packet number, and first delay may be included in each first recording unit, and for example, the stream number may be recorded with 1 byte, the packet number may be recorded with 4 bytes, the first delay may be recorded with 4 bytes, and the exclusive or result of stream information may be recorded with x bytes, which may be configured as needed. From this, the total memory size allocated to all first recording units can be calculated as k x (9+x) bytes. In addition, the total memory size allocated to all index recording units in the information recording units is k×log2 (M)/8 bytes, and the total memory size allocated to all second recording units is m×n×4 bytes. Wherein, M is the number of second recording units, which can be estimated according to the number of concurrent streams that may exceed a threshold, and in particular, can be estimated depending on the existing stream size distribution and the network slicing result, n is the number of delay information that can be recorded at most by each second recording unit, and the size of each second recording unit is n×4 bytes, and each delay information is recorded by 4 bytes.

It should be noted that the specific number of bytes given here is only an example, and does not limit the embodiments of the present application, and the specific implementation may be to record these information by using other byte numbers.

Referring to fig. 7, in fig. 7, each network device may be the first network device described above, and then each network device may implement the operations implemented by the first network device described above, or the first network device may be any one of the network devices shown in fig. 7. Specifically, a control information channel is firstly established between each network device and the controller, the controller sets controller information such as an estimation window, a quantile, a monitoring threshold value and the like, and then the control information is sent to each network device through the control information channel. The controller then sends the data signal of the tail delay measurement of the stream to the each network device. And each network device starts recording the related information of the time delay of the received stream according to the data signal, wherein the recorded information is recorded in the first recording unit and the second recording unit.

After the relevant information is recorded in the first recording unit or the first recording unit and the second recording unit, in a possible implementation manner, each network device sends the information recorded by the recording unit to the controller through a device control surface of the network device, the controller estimates the tail delay of the flow based on the information, and then the controller performs summary analysis on the estimated tail delay and uses the analyzed data for relevant processing needs such as operation and maintenance. Specific estimation processes and summary analysis can be referred to the related description, and are not repeated here. As for the process of transmitting the information recorded in the recording unit to the controller, fig. 8 may be exemplarily referred to.

Referring to fig. 8, in fig. 8, each network device in the data plane may perform the operation performed by the first network device, and thus each network device records information about the delay of the data packet. Also taking the first network device as an example, after the corresponding estimation window ends, the first network device transfers the information recorded by the recording units to its own device control plane, specifically, the device control plane may acquire the information in the recording units through pull operation, or the first network device may push a register group formed by the recording units to its own device control plane. Specifically, the recording units may include the information recorded in the first recording unit, the index recording unit, and the second recording unit of the first stream map, and in fig. 8, three first recording units of the first stream map are used, and three corresponding second recording units are also used as examples, but the number of the first recording unit and the number of the second recording unit are not limited in specific implementation.

In addition, in fig. 8, assuming that the tail delay estimation of the first stream passing through the target device is performed by the controller, the device control plane of the first network device may send the acquired information of the recording unit to the controller in the form of a data packet through the established data transmission channel. The format of a specific transmitted data packet including the network device identification (sid), the estimation window identifier (tw), the data type (type), and the information recorded by the recording unit can be referred to as the format shown in fig. 8. Wherein the network device identifier is used for identifying the network device transmitting the data packet, the estimated window identifier is used for identifying which estimated window the information in the transmitted recording unit is the information recorded in, and the data type is used for identifying whether the load data in the data packet is the information in the first recording unit, the information in the index recording unit or the information in the second recording unit. In fig. 8, the data type is 1, which indicates that the load data in the data packet is information in the first recording unit, the data type is 2, which indicates that the load data in the data packet is information in the index recording unit, and the data type is 3, which indicates that the load data in the data packet is information in the second recording unit.

In another possible implementation manner, after the corresponding estimation window is finished, the recorded information may be sent to the device control plane of the first network device to perform corresponding tail delay estimation, and the specific estimation may refer to the description of estimating the tail delay of the first flow passing through the target device by the first network device. And then, each network device sends the estimated tail delay information of the flow to the controller, the controller gathers and analyzes the tail delay information, and the analyzed data is used for relevant processing requirements such as operation and maintenance. For example, also taking the first network device as an example, the specific manner in which the first network device transfers the information recorded by the recording unit to the device control plane of the first network device may refer to the corresponding description in fig. 8, which is not repeated herein. After the device control plane of the first network device obtains the information, the device control plane of the first network device estimates a tail delay of the first stream passing through the target device in the corresponding estimation window, and then the tail delay can be sent to the controller through the established data transmission channel. Specifically, the tail delay is also sent in a packet, in order to identify that the data in the packet is a packet with tail delay, a special value of a TCP reserved field may be set in a packet header of the packet, so that after the controller receives the data, it finds that the special value of the TCP reserved field exists in the packet header, and then it may be determined that the packet is a packet with tail delay including a stream. In addition, the data packet also includes the network device identifier (sid), the estimation window identifier (tw), and the data type (type), and may further include information such as flow information of the first flow and the number of packets of the first flow received in the corresponding estimation window.

Optionally, for the case that the number of packets of the target flow received by the first network device in the estimation window is smaller than the threshold, since the first recording unit mapped by the target flow has no associated second recording unit, the information transferred from the first network device to the device control plane of the first network device does not include the information of the second recording unit and the index recording unit, and the rest of the information is still transmitted, which can be specifically seen from the above description.

In the above-described embodiments, the first stream and the first data packet are mostly described as examples, but the first network device may record information of each stream passing through itself in the manner described above, so as to implement estimation of tail delay of each stream, that is, implement tail delay estimation of a full-volume stream.

In summary, in the embodiment of the application, the measurement of the tail delay information of the per-flow can be realized, and the tail delay information of the per-flow of the full-volume flow under the fine granularity can be obtained. And, measurement of the 99 quantile delay of a 1M stream can be supported without exceeding 30 MB. Meanwhile, the data plane logic of the embodiment of the application can be deployed in a programmable data plane, for example, can be deployed on Barefoot Tofino switches, belongs to preset capability of network equipment, and has better deployment property. In addition, under the condition that the number of the packets is larger than the threshold value, the information of the second recording unit is updated by the polling mode and the mode that the time delay in the second recording unit is replaced by smaller time delay at regular intervals, and compared with a random joint algorithm with the same space overhead, the measurement accuracy of the tail time delay of the stream is remarkably improved. For example, the simulation experiment uses an NS3 simulation platform, the network topology is Fat Tree Fat-Tree topology common to data centers, the stream distribution data uses open source data of a large data center, the network load is set at 50%, and the streams at the same end meet poisson arrival. The random look algorithm uses the same memory space as the embodiment of the application under this condition for tape-casting sampling and storage, n=10 of the second recording unit. The estimation window is set to 100ms, other network settings are reasonable values, and the simulation result shown in fig. 9 can be obtained in the experimental environment. In the simulation result, the measurement error is reduced by 96.5% for the 99-bit tail delay and 80.7% for the 95-bit tail delay.

Compared with the existing tail delay measurement scheme, in the embodiment of the application, the method and the device can reduce the recording of unnecessary information by collecting the relevant information of the tail delay of the flow in the estimation window and adopting the various recording units to record the information, so that the effective information is finally obtained, thereby effectively reducing repeated or invalid information reporting and greatly reducing the generated bandwidth extra load.

In summary, the embodiment of the application can reduce the resource expense of the network equipment in the tail delay measurement process of each stream, so that the network equipment can support the flow-by-flow tail delay measurement tasks of a large number of concurrent streams of a large-scale network in limited storage resources, and simultaneously, huge extra load is not generated, thereby obtaining good measurement precision.

The above description mainly describes the communication delay estimation method provided by the embodiment of the application. It will be appreciated that each device, in order to implement the corresponding functions described above, includes corresponding hardware structures and/or software modules that perform each function. The elements and steps of the examples described in connection with the embodiments disclosed herein may be embodied in hardware or a combination of hardware and computer software. Whether a function is implemented as hardware or computer software driven hardware depends upon the particular application and design constraints imposed on the solution. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the embodiments of the present application.

The embodiment of the application can divide the functional modules of the device according to the method example, for example, each functional module can be divided corresponding to each function, and two or more functions can be integrated in one module. The integrated modules may be implemented in hardware or in software functional modules. It should be noted that, the division of the modules in the embodiment of the present application is illustrative, and is merely a logic function division, and there may be another division manner in actual implementation.

Fig. 10 shows a schematic diagram of a possible logic structure of an apparatus in the case of dividing the respective functional modules into respective functions, where the apparatus may be the first network device described in the above-mentioned method embodiment, or may be a chip in the first network device, or may be a processing system in the first network device, or the like. The apparatus 1000 comprises a processing unit 1001 and optionally a transmitting unit 1002 and/or a receiving unit 1003. Wherein:

a processing unit 1001 for:

Acquiring stream information from a received first data packet, wherein the stream information is identification information of a first stream to which the first data packet belongs; the processing unit 1001 may be configured to implement the operation of acquiring stream information in step 301 in fig. 3;

determining a first recording unit of the first stream map based on the stream information, wherein the first recording unit comprises a first time delay and a packet number, the first time delay is the maximum time delay of a single data packet of a target stream passing through a target device, and the packet number is the number of the data packets of the target stream received by the network device;

updating the number of packets and updating the first delay to be the delay of the first data packet passing through the target device if the delay of the first data packet passing through the target device is greater than the first delay, the processing unit 1001 may be configured to implement the updating operation in step 303 in fig. 3, and the first delay is configured to estimate the tail delay of the first stream passing through the target device if the number of packets is less than a threshold.

In a possible implementation manner, the first recording units of the first stream map are multiple, the processing unit 1001 is further configured to determine that the first delay recorded in a first unit is a tail delay estimated value of the first stream passing through the target device in the estimation window and send the first delay recorded in the first unit to the controller when the number of packets recorded in at least one unit of the multiple first recording units is smaller than the threshold after the estimation window is over, and the first unit is a unit with the minimum first delay recorded in the multiple first recording units.

In a possible implementation manner, the network device further includes a sending unit 1002, configured to send, to the controller, information recorded in the plurality of first recording units when the estimation window ends.

In a possible implementation manner, in a case where the number of packets recorded in the first recording unit is greater than or equal to the threshold value, the processing unit 1001 is further configured to:

In a possible implementation manner, the network device further includes a receiving unit 1003, configured to receive a second data packet, where the second data packet is a data packet of the target flow;

the processing unit 1001 is further configured to obtain a second delay of the n delays of the second recording unit according to a polling manner, and update the second delay of the second recording unit to a delay of the second data packet passing through the target device when the delay of the second data packet passing through the target device is greater than the second delay.

In a possible embodiment, the receiving unit 1003 is further configured to receive a third packet, where the third packet is a packet of the target stream, and the receiving unit 1003 receives m packets of the target stream before the third packet and after the second packet, where m is an integer greater than 1;

The processing unit 1001 is further configured to randomly obtain a third delay from the n delays of the second recording unit, and update the third delay in the second recording unit to a delay of the third data packet passing through the target device when the delay of the third data packet passing through the target device is smaller than the third delay.

In a possible implementation manner, the processing unit 1001 is further configured to estimate, in a case where the estimation window ends, a tail delay of the first stream passing through the target device in the estimation window based on the n delays in the second recording unit.

Optionally, the tail delay of the first stream passing through the target device is p-bit tail delay, where p is greater than 80 and less than 100, and the processing unit 1001 estimates the tail delay of the first stream passing through the target device based on n delays in the second recording unit, where w is an integer greater than 0 and less than or equal to n, where w is a tail delay estimated value of the first stream passing through the target device in the estimation window.

In a possible implementation manner, the network device further includes a sending unit 1002, configured to send, to the controller, the information recorded in the first recording unit and the second recording unit, in a case where the estimation window ends.

In a possible implementation manner, the processing unit 1001 determines the first recording unit of the first stream map based on the stream information, where the processing unit includes mapping the stream information to a plurality of bits in a bitmap through a plurality of hash functions, one bit in the bitmap is associated with one of the first recording units, and the network device determines the first recording unit of the first stream map based on the plurality of bits.

The specific operation and beneficial effects of each unit in the apparatus 1000 shown in fig. 10 can be referred to the corresponding description in fig. 3 and the possible method embodiments thereof, and will not be repeated here.

Fig. 11 shows a schematic diagram of a possible logic structure of an apparatus in the case of dividing the respective functional modules into respective functions, where the apparatus may be the first network device described in the above-mentioned method embodiment, or may be a chip in the first network device, or may be a processing system in the first network device, or the like. The apparatus 1100 comprises a processing unit 1101 and a receiving unit 1102. Wherein:

a processing unit 1101 for:

the processing unit 1001 may be configured to perform the operation of acquiring the flow information in step 301 in fig. 3, where the flow information is acquired from the first packet received by the receiving unit 1102, where the flow information is identification information of a first flow to which the first packet belongs;

Updating the number of packets, and updating the first delay to the delay of the first data packet passing through the target device if the delay of the first data packet passing through the target device is greater than the first delay;

Fig. 12 shows a schematic diagram of a possible logic structure of an apparatus in the case of dividing the respective functional modules into respective functions, which may be the controller described in the above-described method embodiment, or may be a chip in the controller, or may be a processing system in the controller, or the like. The apparatus 1200 comprises a receiving unit 1201 and a processing unit 1202. Wherein:

A receiving unit 1201 configured to receive information recorded in a plurality of first recording units, where the information recorded in each first recording unit includes a first delay and a packet number, where the first delay is a maximum delay of a single packet of a target stream passing through a target device, and the packet number is a number of packets of the target stream received by the network device;

a processing unit 1202, configured to estimate a tail delay of the first stream passing through the target device based on the first delays recorded in the plurality of first recording units when the number of packets is less than a threshold.

In a possible implementation manner, the receiving unit 1201 is further configured to receive an identifier of an estimation window, where the identifier indicates that the information recorded in the plurality of first recording units is recorded in the estimation window, and the estimation window is a time window for estimating a tail delay of the first flow passing through the target device;

The processing unit 1202 estimates a tail delay of the first stream passing through the target device based on the first delays recorded in the plurality of first recording units, where the first delay recorded in the first unit is determined to be a tail delay estimated value of the first stream passing through the target device in the estimation window, and the first unit is a unit with the minimum first delay recorded in the plurality of first recording units.

Fig. 13 shows a schematic diagram of a possible logic structure of an apparatus in the case of dividing the respective functional modules into respective functions, which may be the controller described in the above-described method embodiment, or may be a chip in the controller, or may be a processing system in the controller, or the like. The apparatus 1300 includes a receiving unit 1301 and a processing unit 1302. Wherein:

A receiving unit 1301, configured to receive information recorded in a first recording unit and a second recording unit, where the information recorded in the first recording unit includes a first delay and a packet number, where the first delay is a maximum delay of a single packet of a first stream passing through a target device, and the packet number is a number of packets of the first stream received by the network device;

a processing unit 1302, configured to estimate a tail delay of the first stream passing through the target device based on the n delays.

In a possible implementation manner, the receiving unit 1301 is further configured to receive an identifier of an estimation window, where the identifier indicates that the information recorded in the first recording unit and the second recording unit is recorded in the estimation window, and the estimation window is a time window used for estimating a tail delay of the first flow passing through the target device;

The tail delay of the first stream passing through the target device is p-bit tail delay, where p is greater than 80% and less than 100%, and the processing unit 1302 estimates the tail delay of the first stream passing through the target device based on the n delays, including:

Fig. 14 is a schematic diagram of a possible hardware structure of an apparatus according to an embodiment of the present application, where the apparatus may be the first network device described in the foregoing embodiment, or may be a chip in the first network device, or may be a processing system in the first network device, or the like. The apparatus 1400 includes a processor 1401, a memory 1402, and a communication interface 1403. The processor 1401, the communication interface 1403, and the memory 1402 may be connected to each other or connected to each other through a bus 1404.

By way of example, memory 1402 is used to store computer programs and data for device 1400 and memory 1402 may include, but is not limited to, random access memory (random access memory, RAM), read-only memory (ROM), erasable programmable read-only memory (erasable programmable read only memory, EPROM), or portable read-only memory (compact disc read-only memory, CD-ROM), etc.

The communication interface 1403 includes a transmission interface and a reception interface, and the number of the communication interfaces 1403 may be plural, for supporting the apparatus 1400 to perform communication, such as receiving or transmitting data or messages.

By way of example, the processor 1401 may be a central processor unit, a general purpose processor, a digital signal processor, an application specific integrated circuit, a field programmable gate array or other programmable logic device, a transistor logic device, a hardware component, or any combination thereof. A processor may also be a combination that performs a computational function, such as a combination comprising one or more microprocessors, a combination of a digital signal processor and a microprocessor, and so forth. Processor 1401 may be configured to read the program stored in memory 1402, and cause apparatus 1400 to perform operations performed by the first network device in any of the communication delay estimation methods described above in fig. 3 and its possible embodiments.

In a possible implementation, the processor 1401 may be configured to obtain, from a received first data packet, stream information, where the stream information is identification information of a first stream to which the first data packet belongs, determine a first recording unit mapped by the first stream based on the stream information, where the first recording unit includes a first delay and a packet number, where the first delay is a maximum delay of a single data packet of a target stream passing through a target device, where the packet number is a number of data packets of the target stream received by the network device, where the target stream includes a stream mapped to the first recording unit, update the packet number, and update the first delay to be a delay of the first data packet passing through the target device if the delay of the first data packet passing through the target device is greater than the first delay, and where the packet number is less than a threshold, where the first delay is used to estimate a tail delay of the first stream passing through the target device.

The specific operation and advantages of each unit in the apparatus 1400 shown in fig. 14 can be seen from the corresponding description in fig. 3 and the possible method embodiments thereof, and will not be repeated here.

Fig. 15 is a schematic diagram of a possible hardware structure of an apparatus according to an embodiment of the present application, where the apparatus may be the first network device described in the foregoing embodiment, or may be a chip in the first network device, or may be a processing system in the first network device, or the like. The apparatus 1500 includes a processor 1501, a memory 1502 and a communication interface 1503. The processor 1501, the communication interface 1503, and the memory 1502 may be connected to each other or to each other through the bus 1504.

By way of example, memory 1502 is used to store computer programs and data for apparatus 1500, and memory 1502 may include, but is not limited to, random access memory (random access memory, RAM), read-only memory (ROM), erasable programmable read-only memory (erasable programmable read only memory, EPROM), or portable read-only memory (compact disc read-only memory, CD-ROM), among others.

The communication interface 1503 includes a transmitting interface and a receiving interface, and the number of the communication interfaces 1503 may be plural, for supporting the apparatus 1500 to communicate, for example, receive or transmit data or messages.

By way of example, the processor 1501 may be a central processor unit, a general purpose processor, a digital signal processor, an application specific integrated circuit, a field programmable gate array or other programmable logic device, a transistor logic device, a hardware component, or any combination thereof. A processor may also be a combination that performs a computational function, such as a combination comprising one or more microprocessors, a combination of a digital signal processor and a microprocessor, and so forth. The processor 1501 may be configured to read the program stored in the memory 1502, so that the apparatus 1500 performs the operation performed by the first network device in any of the communication delay estimation methods described in fig. 3 and the possible embodiments thereof.

In a possible implementation, the processor 1501 may be configured to obtain stream information from the received first data packet, where the stream information is used to indicate that the first data packet is a data packet in a first stream, determine a first recording unit of the first stream map based on the stream information, where the first recording unit is configured to record a first delay and a number of packets, where the first delay is a maximum delay of a single data packet passing through a destination device of a target stream, where the number of packets is a number of data packets of the target stream received by the network device, where the target stream includes a stream mapped to the first recording unit, update the number of packets, where the first delay is updated to a delay of the first data packet passing through the destination device if the delay of the first data packet passing through the destination device is greater than the first delay, where the number of packets is greater than or equal to a threshold, allocate a second recording unit to record a maximum delay of each data packet in n data packets passing through the destination device, where the delay of each data packet in the n data packets is an integer number of the n data packets passing through the destination device, where the delay of the n data packets in the n data packets passing through the destination device is greater than the estimated to be the delay of the n data packets in the network device.

The specific operation and advantages of each unit in the apparatus 1500 shown in fig. 15 can be seen from the corresponding description in fig. 3 and the possible method embodiments thereof, and will not be repeated here.

Fig. 16 is a schematic diagram of a possible hardware structure of an apparatus according to an embodiment of the present application, where the apparatus may be a controller as described in the foregoing embodiment, or may be a chip in the controller, or may be a processing system in the controller, or the like. The apparatus 1600 includes a processor 1601, a memory 1602 and a communication interface 1603. The processor 1601, the communication interface 1603, and the memory 1602 may be interconnected or interconnected by a bus 1604.

By way of example, memory 1602 is used to store computer programs and data for device 1600, and memory 1602 may include, but is not limited to, random access memory (random access memory, RAM), read-only memory (ROM), erasable programmable read-only memory (erasable programmable read only memory, EPROM), or portable read-only memory (compact disc read-only memory, CD-ROM), among others.

The communication interface 1603 includes a transmitting interface and a receiving interface, and the number of the communication interfaces 1603 may be plural, for supporting the apparatus 1600 to communicate, such as to receive or transmit data or messages, etc.

By way of example, the processor 1601 may be a central processor unit, a general purpose processor, a digital signal processor, an application specific integrated circuit, a field programmable gate array or other programmable logic device, a transistor logic device, a hardware component, or any combination thereof. A processor may also be a combination that performs a computational function, such as a combination comprising one or more microprocessors, a combination of a digital signal processor and a microprocessor, and so forth. The processor 1601 may be configured to read a program stored in the memory 1602, so that the apparatus 1600 performs operations performed by the controller in any of the communication delay estimation methods described in fig. 3 and its possible embodiments.

In a possible implementation, the processor 1601 may be configured to receive information recorded in a plurality of first recording units, where the information recorded in each first recording unit includes a first delay and a packet number, where the first delay is a maximum delay for a single packet of a target stream to pass through a target device, and the packet number is a number of packets of the target stream received by the network device, where the target stream includes a stream mapped to the first recording unit, where the target stream includes a first stream, and where the packet number is less than a threshold, estimate a tail delay for the first stream to pass through the target device based on recording the first delay in the plurality of first recording units.

The specific operation and advantages of each unit in the apparatus 1600 shown in fig. 16 can be seen from the corresponding description in fig. 3 and the possible method embodiments thereof, and will not be repeated here.

Fig. 17 is a schematic diagram of a possible hardware structure of an apparatus according to an embodiment of the present application, where the apparatus may be a controller as described in the foregoing embodiment, or may be a chip in the controller, or may be a processing system in the controller, or the like. The apparatus 1700 includes a processor 1701, a memory 1702, and a communication interface 1703. The processor 1701, the communication interface 1703, and the memory 1702 may be interconnected or interconnected via a bus 1704.

By way of example, memory 1702 may be used to store computer programs and data for device 1700, and memory 1702 may include, but is not limited to, random access memory (random access memory, RAM), read-only memory (ROM), erasable programmable read-only memory (erasable programmable read only memory, EPROM), or portable read-only memory (compact disc read-only memory, CD-ROM), among others.

The communication interface 1703 includes a transmitting interface and a receiving interface, and the number of the communication interfaces 1703 may be plural, for supporting the apparatus 1700 to perform communication, such as receiving or transmitting data or messages, or the like.

The processor 1701 may be, for example, a central processing unit, a general purpose processor, a digital signal processor, an application specific integrated circuit, a field programmable gate array or other programmable logic device, a transistor logic device, a hardware component, or any combination thereof. A processor may also be a combination that performs a computational function, such as a combination comprising one or more microprocessors, a combination of a digital signal processor and a microprocessor, and so forth. The processor 1701 may be configured to read the program stored in the memory 1702, so that the apparatus 1700 performs the operations performed by the controller in any of the communication delay estimation methods described in fig. 3 and its possible embodiments.

In a possible implementation, the processor 1701 may be configured to receive information recorded in a first recording unit and a second recording unit, where the information recorded in the first recording unit includes a first delay and a packet number, the first delay is a maximum delay for a single packet of a first stream passing through a target device, the packet number is a number of packets of the first stream received by the network device, the second recording unit is associated with the first recording unit, the information recorded in the second recording unit includes a delay for each of n packets of the first stream passing through the target device, where n is an integer greater than 1, and estimate a tail delay for the first stream passing through the target device based on the n delays.

The specific operation and advantages of each unit in the apparatus 1700 shown in fig. 17 can be seen from the corresponding description in fig. 3 and the possible method embodiments thereof, and will not be repeated here.

Embodiments of the present application also provide a computer readable storage medium storing a computer program for execution by a processor to perform the operations performed by the first network device in the method of any of the above-described fig. 3 and possible method embodiments thereof.

Embodiments of the present application also provide a computer readable storage medium storing a computer program for execution by a processor to perform the operations performed by the controller in the method of any of the above-described fig. 3 and possible method embodiments thereof.

The present application also provides a computer program product, which when read and executed by a computer, performs the operations performed by the first network device in the method described in any of the above-mentioned fig. 3 and possible method embodiments thereof.

Embodiments of the present application also provide a computer program product, which when read and executed by a computer, performs the operations performed by the controller in the method described in any of the above-described fig. 3 and its possible method embodiments.

In summary, the embodiment of the application can reduce the resource overhead of the network device in the tail delay measurement process of each stream, so that the network device can measure and estimate the tail delay of all streams passing through the network device based on the existing storage and processing resources.

The terms "first," "second," and the like in this disclosure are used for distinguishing between similar elements or items having substantially the same function and function, and it should be understood that there is no logical or chronological dependency between the terms "first," "second," and "n," and that there is no limitation on the amount and order of execution. It will be further understood that, although the following description uses the terms first, second, etc. to describe various elements, these elements should not be limited by the terms. These terms are only used to distinguish one element from another element. For example, the first time delay may be referred to as a second time delay, and similarly, the second time delay may be referred to as a first time delay, without departing from the scope of the various described examples. Both the first delay and the second delay may be delays, and in some cases may be separate and distinct delays.

It should be further understood that, in the embodiments of the present application, the sequence number of each process does not mean that the execution sequence of each process should be determined by the function and the internal logic of each process, and should not constitute any limitation on the implementation process of the embodiments of the present application.

It will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

It should be further understood that reference throughout this specification to "one embodiment," "an embodiment," "one possible implementation," means that a particular feature, structure, or characteristic described in connection with the embodiment or implementation is included in at least one embodiment of the present application. Thus, the appearances of the phrases "in one embodiment" or "in an embodiment," "one possible implementation" in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.

It should be noted that the above embodiments are merely for illustrating the technical solution of the present application and not for limiting the same, and although the present application has been described in detail with reference to the above embodiments, it should be understood by those skilled in the art that the technical solution described in the above embodiments may be modified or some or all of the technical features may be equivalently replaced, and these modifications or substitutions do not make the essence of the corresponding technical solution deviate from the scope of the technical solution of the embodiments of the present application.

Claims

1. A method for estimating communication delay, characterized in that the method comprises:

The network device obtains flow information from the received first data packet, where the flow information is identification information of a first flow to which the first data packet belongs;

The network device determines a first recording unit of the first flow mapping based on the flow information; the first recording unit includes a first delay and a number of packets, the first delay being a maximum delay for a single data packet of the target flow to pass through the target device, and the number of packets being the number of data packets of the target flow received by the network device; the target flow includes the flow mapped to the first recording unit;

The network device updates the number of packets and, if a delay of the first data packet passing through the target device is greater than the first delay, updates the first delay to a delay of the first data packet passing through the target device;

When the number of packets is smaller than a threshold, the first delay is used to estimate a tail delay of the first flow passing through the target device.

2. The method according to claim 1, wherein the target device is the network device; or

The network device is a device on a data plane in a network, the network device is a last-hop device of the target flow in the data plane, and the target device includes multiple devices that the single data packet passes through in the data plane.

3. The method according to claim 1 or 2, wherein the network device is a device on a data plane in a network, the network device is the last hop device of the data packet of the target flow in the data plane, and the target device includes multiple devices that the single data packet passes through in the data plane;

The delay of the first data packet passing through the target device is the delay of the first data packet passing through the multiple devices;

The first data packet includes a time delay of the first data packet passing through other devices, and the other devices are other network devices among the multiple devices except the network device.

4. The method according to claim 1 or 2, wherein the network device is a device on a data plane in a network, the network device is the last hop device of the data packet of the target flow in the data plane, and the target device includes multiple devices that the single data packet passes through in the data plane;

The first data packet includes a timestamp of an entry of a first-hop device that the first data packet passes through in the data plane, and the timestamp is used to calculate a delay of the first data packet passing through the multiple devices.

5. The method according to claim 1 or 2, wherein the data packets of the target flow received by the network device are data packets received by the network device within an estimation window, and the estimation window is a time window for estimating the tail delay of the first flow passing through the target device;

The first delay is the maximum delay of a single data packet of the target flow passing through the target device, including: the first delay is the maximum delay of a single data packet of the target flow passing through the target device within the time window;

The tail delay of the first flow passing through the target device is the tail delay of the first flow passing through the target device within the time window.

6. The method according to claim 5, wherein the first recording unit of the first stream mapping is multiple; the method further comprises:

After the estimation window ends, if the number of packets recorded by at least one of the multiple first recording units is less than the threshold, the network device determines that the first delay recorded in the first unit is the estimated value of the tail delay of the first flow passing through the target device within the estimation window, and sends the first delay recorded in the first unit to the controller; the first unit is the unit with the smallest first delay recorded among the multiple first recording units.

7. The method according to claim 5, wherein the first recording unit of the first stream mapping is multiple; the method further comprises:

When the estimation window ends, the network device sends the information recorded in the plurality of first recording units to a controller.

8. The method according to claim 5, wherein, when the number of packets recorded in the first recording unit is greater than or equal to the threshold, the method further comprises:

The network device allocates a second recording unit to the first recording unit; the second recording unit is used to record the delay of each of n data packets passing through the target device, the n data packets are data packets in the data packets of the target flow received by the network device after the first data packet, and n is an integer greater than 1; the n delays are used to estimate the tail delay of the first flow passing through the target device.

9. The method according to claim 8, further comprising:

The network device receives a second data packet, where the second data packet is a data packet of the target flow;

The network device obtains the second delay among the n delays of the second recording unit in a polling manner;

In a case where the delay of the second data packet passing through the target device is greater than the second delay, the network device updates the second delay in the second recording unit to the delay of the second data packet passing through the target device.

10. The method according to claim 8, further comprising:

The network device receives a third data packet, where the third data packet is a data packet of the target flow. Before the third data packet and after the second data packet, the network device receives m data packets of the target flow, where m is an integer greater than 1.

The network device randomly obtains a third delay from the n delays in the second recording unit;

In a case where the delay of the third data packet passing through the target device is less than the third delay, the network device updates the third delay in the second recording unit to the delay of the third data packet passing through the target device.

11. The method according to claim 9 or 10, further comprising:

When the estimation window ends, the network device estimates a tail delay of the first flow passing through the target device within the estimation window based on the n delays in the second recording unit.

12. The method according to claim 11, wherein the tail delay of the first flow passing through the target device is p percentile tail delay, where p is greater than 80 and less than 100;

The network device estimating the tail delay of the first flow passing through the target device based on the n delays in the second recording unit, including:

The network device determines the wth delay among the n delays as the estimated tail delay of the first flow passing through the target device within the estimation window, the wth delay being the delay ranked w among the n delays sorted from small to large, and w being an integer greater than 0 and less than or equal to n.

13. The method according to claim 9 or 10, further comprising:

When the estimation window ends, the network device sends the information recorded in the first recording unit and the second recording unit to a controller.

14. The method according to claim 1 or 2, wherein the network device determines the first recording unit of the first flow mapping based on the flow information, comprising:

The network device maps the flow information into a plurality of bits in a bitmap using a plurality of hash functions; a bit in the bitmap is associated with a first recording unit;

The network device determines the first recording unit of the first stream map based on the plurality of bits.

15. The method according to claim 1 or 2 is characterized in that the first recording unit also includes the number of streams and the XOR result of the stream information, the number of streams is the number of the target streams, and the XOR result of the stream information is the result obtained after the XOR operation is performed on the stream information of the target stream.

16. A method for estimating communication delay, characterized in that the method comprises:

The network device obtains flow information from the received first data packet, where the flow information is used to indicate that the first data packet is a data packet in a first flow;

The network device determines a first recording unit of the first flow mapping based on the flow information; the first recording unit is used to record a first delay and a number of packets, the first delay being a maximum delay for a single data packet of the target flow to pass through the target device, and the number of packets being the number of data packets of the target flow received by the network device; the target flow includes the flow mapped to the first recording unit;

When the number of packets is greater than or equal to a threshold, the network device allocates a second recording unit to the first recording unit; the second recording unit is used to record the delay of each of n data packets passing through the target device, where the n data packets are part of the data packets of the target flow received by the network device after the first data packet, and n is an integer greater than 1; the n delays are used to estimate the tail delay of the first flow passing through the target device.

17. A method for estimating communication delay, characterized in that the method comprises:

The controller receives information recorded in a plurality of first recording units from a network device, wherein the information recorded in each of the first recording units includes a first delay and a number of packets, wherein the first delay is a maximum delay for a single data packet of a target flow to pass through a target device, and the number of packets is a number of data packets of the target flow received by the network device; the target flow includes a flow mapped to the first recording unit, and the target flow includes a first flow;

When the number of packets is smaller than a threshold, the controller estimates a tail delay of the first flow passing through the target device based on the first delays recorded in the plurality of first recording units.

18. The method according to claim 17, characterized in that

The method further includes: the controller further receiving an identifier of an estimation window, the identifier indicating that the information recorded in the plurality of first recording units is recorded within the estimation window, the estimation window being a time window for estimating a tail delay of the first flow passing through the target device;

The controller estimates the tail delay of the first flow passing through the target device based on the first delay recorded in the multiple first recording units, including: the controller determines that the first delay recorded in the first unit is the estimated tail delay value of the first flow passing through the target device within the estimation window; the first unit is the unit with the smallest first delay recorded in the multiple first recording units.

19. A method for estimating communication delay, comprising:

The controller receives information recorded in a first recording unit and a second recording unit from a network device, where the information recorded in the first recording unit includes a first delay and a number of packets, where the first delay is a maximum delay for a single data packet of a first flow to pass through a target device, and the number of packets is the number of data packets of the first flow received by the network device;

The second recording unit is associated with the first recording unit, and information recorded in the second recording unit includes a delay of each of n data packets in the first flow passing through the target device, where n is an integer greater than 1;

The controller estimates a tail delay of the first flow passing through the target device based on the n delays.

20. The method according to claim 19, further comprising: the controller further receiving an identifier of an estimation window, the identifier indicating that the information recorded in the first recording unit and the second recording unit is recorded within the estimation window, the estimation window being a time window for estimating the tail delay of the first flow passing through the target device;

The tail delay of the first flow passing through the target device is a p-percentile tail delay, where p is greater than 80% and less than 100%. The controller estimates the tail delay of the first flow passing through the target device based on the n delays, including:

The controller determines the wth delay among the n delays as the estimated tail delay of the first flow passing through the target device within the estimation window, the wth delay is the delay ranked w among the n delays sorted from small to large, the delays ranked before w are less than or equal to the p-percentile tail delay, and w is an integer greater than 0 and less than or equal to n.

21. The method according to any one of claims 19-20, characterized in that

The target device is the network device; or,

22. A network device, characterized in that the network device comprises a unit for executing the method according to any one of claims 1 to 15.

23. A network device, characterized in that the network device comprises a unit for executing the method according to claim 16.

24. A controller, characterized in that the controller comprises a unit for executing the method according to claim 17 or 18.

25. A controller, characterized in that the controller comprises a unit for executing the method according to claim 19 or 20.

26. A network device, characterized in that the network device includes a processor and a memory; wherein the memory is used to store a computer program, and the processor is used to execute the computer program stored in the memory, so that the network device executes the method according to any one of claims 1 to 15; or, the network device executes the method according to claim 16.

27. A controller, characterized in that the controller includes a processor and a memory; wherein the memory is used to store a computer program, and the processor is used to execute the computer program stored in the memory, so that the controller executes the method according to claim 17 or 18; or, the network device executes the method according to claim 19 or 20.

28. A computer-readable storage medium, characterized in that the computer-readable storage medium stores a computer program, and the computer program is executed by a processor to implement the method according to any one of claims 1 to 15; or the computer program is executed by a processor to implement the method according to claim 16.

29. A computer-readable storage medium, characterized in that the computer-readable storage medium stores a computer program, and the computer program is executed by a processor to implement the method according to claim 17 or 18; or, the computer program is executed by a processor to implement the method according to claim 19 or 20.

30. A system, characterized in that the system includes a network device and a controller, the network device is the network device according to claim 22, and the controller is the controller according to claim 24 or 25; or, the network device is the network device according to claim 23, and the controller is the controller according to claim 25; or, the network device is the network device according to claim 26, and the controller is the controller according to claim 27.