通信时延估计方法及相关装置

摘要

本申请实施例提供一种通信时延估计方法及相关装置，方法包括：网络设备从接收的第一数据包中获取流信息，流信息为第一数据包所属的第一流的标识信息；然后，基于流信息确定第一流映射的第一记录单元；第一记录单元中包括目标流的单个数据包经过目标设备的最大时延，以及包括网络设备接收到的目标流的数据包的个数；目标流包括映射到第一记录单元的流；然后，更新包数目，并在第一数据包经过目标设备的时延大于第一时延的情况下，将第一时延更新为第一数据包经过目标设备的时延；在包数目小于阈值的情况下，第一时延用于估计第一流经过目标设备的尾时延。本申请能够节省每个流的存储和处理资源，使得可以在现有的资源上进行全量流的尾时延估计。

权利要求

1.一种通信时延估计方法，其特征在于，所述方法包括：

网络设备从接收的第一数据包中获取流信息，所述流信息为所述第一数据包所属的第一流的标识信息；

所述网络设备基于所述流信息确定所述第一流映射的第一记录单元；所述第一记录单元中包括第一时延和包数目，所述第一时延为目标流的单个数据包经过目标设备的最大时延，所述包数目为所述网络设备接收到的所述目标流的数据包的个数；所述目标流包括映射到所述第一记录单元的流；

所述网络设备更新所述包数目，并在所述第一数据包经过所述目标设备的时延大于所述第一时延的情况下，将所述第一时延更新为所述第一数据包经过所述目标设备的时延；

在所述包数目小于阈值的情况下，所述第一时延用于估计所述第一流经过所述目标设备的尾时延。

2.根据权利要求1所述的方法，其特征在于，所述目标设备为所述网络设备；或者，所述网络设备为网络中数据平面上的设备，所述网络设备为所述目标流在所述数据平面中的最后一跳设备，所述目标设备包括所述单个数据包在所述数据平面中经过的多个设备。

3.根据权利要求1或2所述的方法，其特征在于，所述网络设备为网络中数据平面上的设备，所述网络设备为所述目标流的数据包在所述数据平面中的最后一跳设备，所述目标设备包括所述单个数据包在所述数据平面中经过的多个设备；

所述第一数据包经过所述目标设备的时延为所述第一数据包经过所述多个设备的时延；

所述第一数据包中包括所述第一数据包经过其它设备的时延，所述其它设备为所述多个设备中除了所述网络设备之外的其它网络设备。

4.根据权利要求1或2所述的方法，其特征在于，所述网络设备为网络中数据平面上的设备，所述网络设备为所述目标流的数据包在所述数据平面中的最后一跳设备，所述目标设备包括所述单个数据包在所述数据平面中经过的多个设备；

所述第一数据包经过所述目标设备的时延为所述第一数据包经过所述多个设备的时延；

所述第一数据包中包括所述第一数据包在所述数据平面中经过的第一跳设备的入口的时间戳，所述时间戳用于计算所述第一数据包经过所述多个设备的时延。

5.根据权利要求1‑4任一项所述的方法，其特征在于，所述网络设备接收到的所述目标流的数据包为所述网络设备在估计窗口内接收的数据包，所述估计窗口为用于估计所述第一流经过所述目标设备的尾时延的时间窗口；

所述第一时延为目标流的单个数据包经过目标设备的最大时延，包括：所述第一时延为所述目标流的单个数据包在所述时间窗口内经过所述目标设备的最大时延；

所述第一流经过所述目标设备的尾时延为所述第一流在所述时间窗口内经过所述目标设备的尾时延。

6.根据权利要求5所述的方法，其特征在于，所述第一流映射的所述第一记录单元为多个；所述方法还包括：在所述估计窗口结束后，所述多个第一记录单元中的至少一个单元记录的所述包数目小于所述阈值的情况下，所述网络设备确定第一单元中记录的所述第一时延为所述第一流在所述估计窗口内经过所述目标设备的尾时延估计值，并将所述第一单元中记录的所述第一时延发送给控制器；所述第一单元为所述多个第一记录单元中记录的所述第一时延最小的单元。

7.根据权利要求5所述的方法，其特征在于，所述第一流映射的所述第一记录单元为多个；所述方法还包括：在所述估计窗口结束的情况下，所述网络设备向控制器发送所述多个第一记录单元中记录的信息。

8.根据权利要求5所述的方法，其特征在于，在所述第一记录单元中记录的所述包数目大于或等于所述阈值的情况下，所述方法还包括：所述网络设备为所述第一记录单元分配一个第二记录单元；所述第二记录单元用于记录n个数据包中每个数据包经过所述目标设备的时延，所述n个数据包为所述网络设备在所述第一数据包之后接收的所述目标流的数据包中的数据包，所述n为大于1的整数；所述n个时延用于估计所述第一流经过所述目标设备的尾时延。

9.根据权利要求8所述的方法，其特征在于，所述方法还包括：

所述网络设备接收第二数据包，所述第二数据包为所述目标流的数据包；

所述网络设备根据轮询的方式获取所述第二记录单元的n个时延中的第二时延；

在所述第二数据包经过所述目标设备的时延大于所述第二时延的情况下，所述网络设备将所述第二记录单元中的所述第二时延更新为所述第二数据包经过所述目标设备的时延。

10.根据权利要求8所述的方法，其特征在于，所述方法还包括：

所述网络设备接收第三数据包，所述第三数据包为所述目标流的数据包，在所述第三数据包之前，并在所述第二数据包之后，所述网络设备接收了m个所述目标流的数据包，所述m为大于1的整数；

所述网络设备在所述第二记录单元的n个时延中随机获取第三时延；

在所述第三数据包经过所述目标设备的时延小于所述第三时延的情况下，所述网络设备将所述第二记录单元中的所述第三时延更新为所述第三数据包经过所述目标设备的时延。

11.根据权利要求9或10所述的方法，其特征在于，所述方法还包括：

在所述估计窗口结束的情况下，所述网络设备基于所述第二记录单元中的n个时延估计所述第一流在所述估计窗口内经过所述目标设备的尾时延。

12.根据权利要求11所述的方法，其特征在于，所述第一流经过所述目标设备的尾时延为p分位尾时延，所述p大于80且小于100；

所述网络设备基于所述第二记录单元中的n个时延估计所述第一流经过所述目标设备的尾时延，包括：所述网络设备将所述n个时延中的第w个时延确定为所述第一流在所述估计窗口内经过所述目标设备的尾时延估计值，所述第w个时延为从小到大排序的所述n个时延中排序为w的时延，所述w为大于0且小于或等于n的整数。

13.根据权利要求9或10所述的方法，其特征在于，所述方法还包括：

在所述估计窗口结束的情况下，所述网络设备向控制器发送所述第一记录单元和所述第二记录单元中记录的信息。

14.根据权利要求1‑11任一项所述的方法，其特征在于，所述网络设备基于所述流信息确定所述第一流映射的第一记录单元，包括：所述网络设备通过多个哈希函数将所述流信息映射到位图中的多个比特位；所述位图中的一个比特位与一个所述第一记录单元关联；

所述网络设备基于所述多个比特位确定所述第一流映射的所述第一记录单元。

15.根据权利要求1‑14任一项所述的方法，其特征在于，所述第一记录单元中还包括流数目和流信息的异或结果，所述流数目为所述目标流的数量，所述流信息的异或结果为所述目标流的流信息做异或操作后得到的结果。

16.一种通信时延估计方法，其特征在于，所述方法包括：

网络设备从接收的所述第一数据包中获取流信息，所述流信息用于指示所述第一数据包为第一流中的数据包；

所述网络设备基于所述流信息确定所述第一流映射的第一记录单元；所述第一记录单元用于记录第一时延和包数目，所述第一时延为目标流的单个数据包经过目标设备的最大时延，所述包数目为所述网络设备接收到的所述目标流的数据包的个数；所述目标流包括映射到所述第一记录单元的流；

所述网络设备更新所述包数目，并在所述第一数据包经过所述目标设备的时延大于所述第一时延的情况下，将所述第一时延更新为所述第一数据包经过所述目标设备的时延；

在所述包数目大于或等于阈值的情况下，所述网络设备为所述第一记录单元分配一个第二记录单元；所述第二记录单元用于记录n个数据包中每个数据包经过所述目标设备的时延，所述n个数据包为所述网络设备在所述第一数据包之后接收的所述目标流的数据包中的部分数据包，所述n为大于1的整数；所述n个时延用于估计所述第一流经过所述目标设备的尾时延。

17.一种通信时延估计方法，其特征在于，所述方法包括：

控制器接收多个第一记录单元中记录的信息，每个所述第一记录单元中记录的信息包括第一时延和包数目，所述第一时延为目标流的单个数据包经过目标设备的最大时延，所述包数目为所述网络设备接收到的所述目标流的数据包的个数；所述目标流包括映射到所述第一记录单元的流，所述目标流包括第一流；

在所述包数目小于阈值的情况下，所述控制器基于所述多个第一记录单元中记录所述第一时延估计所述第一流经过所述目标设备的尾时延。

18.根据权利要求17所述的方法，其特征在于，

所述方法还包括：所述控制器还接收估计窗口的标识符，所述标识符指示所述多个第一记录单元中记录的信息是在所述估计窗口内记录的，所述估计窗口为用于估计所述第一流经过所述目标设备的尾时延的时间窗口；

所述控制器基于所述多个第一记录单元中记录所述第一时延估计所述第一流经过所述目标设备的尾时延，包括：所述控制器确定第一单元中记录的所述第一时延为所述第一流在所述估计窗口内经过所述目标设备的尾时延估计值；所述第一单元为所述多个第一记录单元中记录的所述第一时延最小的单元。

19.一种通信时延估计方法，其特征在于，所述方法包括：

控制器接收第一记录单元和第二记录单元中记录的信息，所述第一记录单元中记录的信息包括第一时延和包数目，所述第一时延为第一流的单个数据包经过目标设备的最大时延，所述包数目为所述网络设备接收到的所述第一流的数据包的个数；

所述第二记录单元与所述第一记录单元关联，所述第二记录单元中记录的信息包括所述第一流中的n个数据包中每个数据包经过所述目标设备的时延，所述n为大于1的整数；

所述控制器基于所述n个时延估计所述第一流经过所述目标设备的尾时延。

20.根据权利要求19所述的方法，其特征在于，所述方法还包括：所述控制器还接收估计窗口的标识符，所述标识符指示所述第一记录单元和所述第二记录单元中记录的信息是在所述估计窗口内记录的，所述估计窗口为用于估计所述第一流经过所述目标设备的尾时延的时间窗口；

所述第一流经过所述目标设备的尾时延为p分位尾时延，所述p大于80％且小于100％；

所述控制器基于所述n个时延估计所述第一流经过所述目标设备的尾时延，包括：所述控制器将所述n个时延中的第w个时延确定为所述第一流在所述估计窗口内经过所述目标设备的尾时延估计值，所述第w个时延为从小到大排序的所述n个时延中排序为w的时延，排序在所述w之前的时延小于或等于所述p分位尾时延，所述w为大于0且小于或等于n的整数。

21.根据权利要求17‑20任一项所述的方法，其特征在于，

所述目标设备为所述网络设备；或者，

所述网络设备为网络中数据平面上的设备，所述网络设备为所述目标流在所述数据平面中的最后一跳设备，所述目标设备包括所述单个数据包在所述数据平面中经过的多个设备。

22.一种网络设备，其特征在于，所述网络设备包括用于执行如权利要求1‑15任一项所述的方法的单元。

23.一种网络设备，其特征在于，所述网络设备包括用于执行如权利要求16所述的方法的单元。

24.一种控制器，其特征在于，所述控制器包括用于执行如权利要求17或18所述的方法的单元。

25.一种控制器，其特征在于，所述控制器包括用于执行如权利要求19或20所述的方法的单元。

26.一种网络设备，其特征在于，所述网络设备包括处理器和存储器；其中，所述存储器用于存储计算机程序，所述处理器用于执行所述存储器中存储的计算机程序，使得所述网络设备执行如权利要求1‑15任一项所述的方法；或者，使得所述网络设备执行如权利要求

16所述的方法。

27.一种控制器，其特征在于，所述控制器包括处理器和存储器；其中，所述存储器用于存储计算机程序，所述处理器用于执行所述存储器中存储的计算机程序，使得所述控制器执行如权利要求17或18所述的方法；或者，使得所述网络设备执行如权利要求19或20所述的方法。

28.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行以实现权利要求1至15任意一项所述的方法；或者，所述计算机程序被处理器执行以实现权利要求16所述的方法。

29.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行以实现权利要求17或18所述的方法；或者，所述计算机程序被处理器执行以实现权利要求19或20所述的方法。

30.一种系统，其特征在于，所述系统包括网络设备和控制器，所述网络设备为权利要求22所述的网络设备，所述控制器为权利要求24或25所述的控制器；或者，所述网络设备为权利要求23所述的网络设备，所述控制器为权利要求25所述的控制器；或者，所述网络设备为权利要求26所述的网络设备，所述控制器为权利要求27所述的控制器。

说明书

通信时延估计方法及相关装置

技术领域

[0001] 本发明涉及通信网络测量技术领域，尤其涉及一种通信时延估计方法及相关装置。

背景技术

[0002] 网络性能检测一直是网络测量这一极具应用价值的网络领域中的重要子议题。其中，针 对时延的测量一直是学术界研究的热点，也是工业界不断追求革新的领域。利用采样或发送  探针来测量端到端时延的传统工具(如因特网包探索器ping，路由跟踪traceroute)等得到了 大量的部署和应用，在很长一段时间里起到了很大的作用。当前，随着网络规模的迅速扩大 和网络设备能力的不断提高，用户和产品对于网络运维提出了更加精细的要求。网络管理者 希望提高网络的快速检测和定位异常的能力，比如快速发现分布式拒绝服务攻击(distributed denial of service，DDos)攻击，或是能够检测出数据中心中潜在的微突发(micro‑burst)等。 而这些更具挑战性的问题，依赖于对于流性能指标更加细粒度的测量，例如流的尾时延的测 量。

[0003] 当前业界常用的流的尾时延的测量技术主要可以分为两类：一类是以网络流NetFlow为 代表的网内测量技术，此类技术支持在网络设备中筛选、采样和拷贝相关的报文数据，然后 将报文数据上传到控制器进行尾时延测量；另一类是以带内网络遥测(inband network telemetry， INT)技术为代表的带内操作管理维护(in‑situ operation administration and maintenance，iOAM) 技术。此类技术将所需要的操作管理维护(OAM)信息(例如时延的测量数据)直接封装在数 据包中，在监测域的最后一跳，即边缘节点将OAM数据移除转发给控制器进行尾时延测量。 但是，NetFlow技术，支持由网络设备获取数据包的相关信息发送给控制器，但会带来较大 的额外负载和资源消耗，使得实际使用中经常需要进行采样或是选流，难以覆盖经过网络设 备的全部流的尾时延测量；以INT为代表的iOAM技术，将所需的信息携带在数据包头部， 在最后一跳将收集信息上传控制器，减少了上传的成本，但也因此占用了链路带宽，造成流 完成时间增加，吞吐下降等现象，因此往往也不能逐包部署，这也导致了难以实现所有流的 尾时延测量。

[0004] 综上所述，如何在每个流的尾时延测量过程中降低网络设备的资源开销是本领域技术人 员急需解决的技术问题。

发明内容

[0005] 本申请实施例提供了一种通信时延估计方法及相关装置，能够在每个流的尾时延测量过 程中降低网络设备的资源开销，从而使得网络设备基于现有的存储和处理资源可以对经过该 网络设备的全部流的尾时延进行测量和估计。

[0006] 第一方面，本申请提供一种通信时延估计方法，该方法包括：网络设备从接收的第一数 据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息；该网络设备基于该 流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包数目，该第 一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该 目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该网络设备更新该包数 目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新 为该第一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该第一时延用于估 计该第一流经过上述目标设备的尾时延。

[0007] 可选的，上述目标设备为上述网络设备；或者，该网络设备为网络中数据平面上的设备， 该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该 数据平面中经过的多个设备。

[0008] 在本申请实施例中，上述网络设备为数据平面内用于转发数据的任意网络设备，通过在 网络设备中，为网络设备接收到的每个流配置上述第一记录单元用于记录该每个流中的数据 包经过上述目标设备的最大时延，以用于在该每个流的包数目小于阈值的情况下估计该每个 流经过该目标设备的尾时延。由于本申请实施例中，将每个流映射到对应的第一记录单元中， 该第一记录单元中只记录流中数据包经过该目标设备的最大时延，而不是记录所有数据包的 时延，从而节省了存储资源，相比于现有的NetFlow和INT的技术方案，本申请实施例无需 将大量的数据包或者大量的测量数据发送给控制器，从而可以节省额外的链路带宽资源。另 外，由于在本申请实施例中，节省了单个流的尾时延测量和估计所需的资源，从而可以在流 的尾时延测量时无需进行对流进行筛选和采样，即相比现有的方案，本申请可以基于网络设 备现有的存储和处理资源对经过该网络设备的全部流的尾时延进行测量和估计。

[0009] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包经过其它设备的时延，该其它设备为该多个设备中 除了该网络设备之外的其它网络设备。

[0010] 在本申请实施例中，可以在数据平面中该第一流经过的所有网络设备上都部署时延获取 模块，用于获取该第一流的每个数据包经过每个网络设备的时延，然后将这些时延携带在数 据包中发送给上述最后一跳的设备，该最后一跳设备也获取该每个数据包经过自身的时延， 然后统计该每个数据包经过该所有网络设备的总的时延，取最大的时延记录到上述第一记录 单元中。这种实现方式可以使得只需要在该最后一跳设备进行时延等信息的记录和处理，无 需该第一流经过的每个网络设备都有记录，从而可以节省网络设备的存储和处理资源。

[0011] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包在该数据平面中经过的第一跳设备的入口的时间戳， 该时间戳用于计算该第一数据包经过该多个设备的时延。

[0012] 在本申请实施例中，可以在数据平面中该第一流经过的第一条设备上获取流的数据包的 入口时间戳，并将该时间戳携带在数据包中发送到上述最后一跳设备，该最后一跳设备接收 到该数据包后，可以获取该数据包从自身发出的时间戳，后面的时间戳减去前面的时间戳即 为该数据包经过上述目标设备的时延，然后取流中经过上述目标设备的最大时延记录到上述 第一记录单元中。同理，这种实现方式可以使得只需要在该最后一跳设备进行时延等信息的 记录和处理，无需该第一流经过的每个网络设备都有记录，从而可以节省网络设备的存储和 处理资源。

[0013] 一种可能的实施方式中，上述网络设备接收到的该目标流的数据包为该网络设备在估计 窗口内接收的数据包，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗 口；该第一时延为目标流的单个数据包经过目标设备的最大时延，包括：该第一时延为该目 标流的单个数据包在该时间窗口内经过该目标设备的最大时延；该第一流经过上述目标设备 的尾时延为该第一流在该时间窗口内经过目标设备的尾时延。

[0014] 在本申请实施例中，通过将流的传输过程切分成一个或多个时间窗口，在每个时间窗口 内进行流的尾时延的估计，可以提高网络设备的可实施性和可操作性。

[0015] 一种可能的实施方式中，该第一流映射的该第一记录单元为多个；该方法还包括：在该 估计窗口结束后，该多个第一记录单元中的至少一个单元记录的该包数目小于该阈值的情况 下，该网络设备确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备 的尾时延估计值，并将该第一单元中记录的该第一时延发送给控制器；该第一单元为该多个 第一记录单元中记录的该第一时延最小的单元。

[0016] 在本申请实施例中，在估计窗口内网络设备接收到的上述目标流的数据包小于阈值的情 况下，可以用上述多个第一记录单元中记录的最小的第一时延来估计该第一流经过上述目标 设备的尾时延，实现简单，可操作性较强。这是因为在包数目较小的情况下，尾时延与该第 一记录单元中记录的数据包经过目标设备的最大的时延差别较小，所以可以用该最大的时延 来估计流的尾时延。

[0017] 一种可能的实施方式中，上述第一流映射的该第一记录单元为多个；该方法还包括：在 该估计窗口结束的情况下，该网络设备向控制器发送该多个第一记录单元中记录的信息。

[0018] 在本申请实施例中，网络设备可以将上述第一记录单元记录的信息发送给控制器，由控 制器来进行尾时延的估计计算，从而减轻网络设备的处理负担。

[0019] 一种可能的实施方式中，在该第一记录单元中记录的该包数目大于或等于该阈值的情况 下，该方法还包括：该网络设备为该第一记录单元分配一个第二记录单元；该第二记录单元 用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该 第一数据包之后接收的该目标流的数据包中的数据包，该n为大于1的整数；该n个时延用 于估计该第一流经过上述目标设备的尾时延。

[0020] 在本申请实施例中，在包数目大于上述阈值的情况下，尾时延与上述第一记录单元中记 录的数据包经过目标设备的最大的时延差别较大，所以需要另外记录时延来进行流的尾时延 的估计，所以配置了上述第二记录单元，用于记录后续的接收到的流的部分数据包经过上述 目标设备的时延，然后基于第二记录单元记录的时延信息估计流的尾时延，以提高估计的准 确度。

[0021] 一种可能的实施方式中，该方法还包括：该网络设备接收第二数据包，该第二数据包为 该目标流的数据包；该网络设备根据轮询的方式获取该第二记录单元的n个时延中的第二时 延；在该第二数据包经过该目标设备的时延大于该第二时延的情况下，该网络设备将该第二 记录单元中的该第二时延更新为该第二数据包经过该目标设备的时延。

[0022] 在本申请实施例中，可以通过轮询的方式更新上述第二记录单元中的时延，以保证上述 n个时延为最大的n个时延。

[0023] 一种可能的实施方式中，该方法还包括：该网络设备接收第三数据包，该第三数据包为 该目标流的数据包，在该第三数据包之前，并在该第二数据包之后，该网络设备接收了m个 该目标流的数据包，该m为大于1的整数；该网络设备在该第二记录单元的n个时延中随机 获取第三时延；在该第三数据包经过该目标设备的时延小于该第三时延的情况下，该网络设 备将该第二记录单元中的该第三时延更新为该第三数据包经过该目标设备的时延。

[0024] 当在上述估计窗口内接收到的流的包数目非常多的情况下，用上述最大的n个时延来估 计该流的尾时延也存在较大的误差。例如，假设该包数目达到10000个，上述n为10个，若 该100个时延为最大的10个时延，在估计99％分位尾时延时，该10000个数据包经过上述目 标设备的时延按从小到大排序的第9900个时延才是准确的99％分位尾时延，而该10个最大 的时延中每个时延都与该第9900个时延相差较大，所以无法用该10个时延来估计该99％分 位尾时延。因此，本申请实施例中，在更新上述第二记录单元的过程中，基于上述轮询的更 新方式的基础上，每隔一定数目的数据包，就随机在第二记录单元中的n个时延中选择一个 更新为较小的时延，从而使得该第二记录单元中记录的n个时延不再是最大的时延，而是按 照一定的概率将尽可能多的其它分位的时延信息记录到第二记录单元中，从而减少尾时延的 估计误差。

[0025] 一种可能的实施方式中，该方法还包括：在该估计窗口结束的情况下，该网络设备基于 该第二记录单元中的n个时延估计该第一流在该估计窗口内经过目标设备的尾时延。

[0026] 可选的，该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80且小于100； 该网络设备基于该第二记录单元中的n个时延估计该第一流经过上述目标设备的尾时延，包 括：该网络设备将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备 的尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为 大于0且小于或等于n的整数。

[0027] 在本申请实施例中，基于上述更新上述第二记录单元中的方式，可以用该第二记录单元 中的n个时延中的时延来估计上述p分位尾时延，可以通过计算上述n个时延中大于p分位 尾时延的时延个数的数学期望来确定上述w。

[0028] 一种可能的实施方式中，该方法还包括：在该估计窗口结束的情况下，该网络设备向控 制器发送该第一记录单元和该第二记录单元中记录的信息。

[0029] 在本申请实施例中，网络设备可以将上述第一记录单元和第二记录单元记录的信息发送 给控制器，由控制器来进行尾时延的估计计算，从而减轻网络设备的处理负担。

[0030] 一种可能的实施方式中，该网络设备基于该流信息确定该第一流映射的第一记录单元， 包括：该网络设备通过多个哈希函数将该流信息映射到位图中的多个比特位；该位图中的一 个比特位与一个该第一记录单元关联；该网络设备基于该多个比特位确定该第一流映射的该 第一记录单元。

[0031] 在本申请实施例中，通过哈希计算将流映射到对应的第一记录单元，计算简单，处理方 便，还可以节省存储资源。

[0032] 一种可能的实施方式中，该第一记录单元中还包括流数目和流信息的异或结果，该流数 目为该目标流的数量，该流信息的异或结果为该目标流的流信息做异或操作后得到的结果。

[0033] 在本申请实施例中，在第一记录单元中记录流数目和流信息的异或结果，可以用于标记 出现哈希冲突的记录单元，并可以用于后续解码出哈希冲突的流信息。

[0034] 第二方面，本申请提供一种通信时延估计方法，该方法包括：网络设备从接收的该第一 数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数据包；该网络设备基 于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延和包数目， 该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到 的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该网络设备更新该 包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延 更新为该第一数据包经过该目标设备的时延；在该包数目大于或等于阈值的情况下，该网络 设备为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个 数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目 标流的数据包中的部分数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上 述目标设备的尾时延。

[0035] 在本申请实施例中，基于上述更新上述第二记录单元中的方式，可以用该第二记录单元 中的n个时延中的时延来估计上述p分位尾时延，可以通过计算上述n个时延中大于p分位 尾时延的时延个数的数学期望来确定上述w。

[0036] 第三方面，本申请提供一种通信时延估计方法，该方法包括：控制器接收多个第一记录 单元中记录的信息，每个该第一记录单元中记录的信息包括第一时延和包数目，该第一时延 为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流 的数据包的个数；该目标流包括映射到该第一记录单元的流，该目标流包括第一流；在该包 数目小于阈值的情况下，该控制器基于该多个第一记录单元中记录该第一时延估计该第一流 经过上述目标设备的尾时延。

[0037] 可选的，该目标设备为该网络设备；或者，该网络设备为网络中数据平面上的设备，该 网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数 据平面中经过的多个设备。

[0038] 在本申请实施例中，可以在控制器上述进行尾时延的估计计算，在估计窗口内网络设备 接收到的上述目标流的数据包小于阈值的情况下，可以用上述多个第一记录单元中记录的第 一时延来估计该第一流经过上述目标设备的尾时延，实现简单，可操作性较强。这是因为在 包数目较小的情况下，尾时延与该第一记录单元中记录的数据包经过目标设备的最大的时延 差别较小，所以可以用该最大的时延来估计流的尾时延。

[0039] 一种可能的实施方式中，该方法还包括：该控制器还接收估计窗口的标识符，该标识符 指示该多个第一记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该 第一流经过上述目标设备的尾时延的时间窗口；该控制器基于该多个第一记录单元中记录该 第一时延估计该第一流经过上述目标设备的尾时延，包括：该控制器确定第一单元中记录的 该第一时延为该第一流在该估计窗口内经过目标设备的尾时延估计值；该第一单元为该多个 第一记录单元中记录的该第一时延最小的单元。

[0040] 在本申请实施例中，通过将流的传输过程切分成一个或多个时间窗口，在每个时间窗口 内进行流的尾时延的估计，可以提高网络设备的可实施性和可操作性。并在此基础上，可以 用上述多个第一记录单元中记录的最小的第一时延来估计该第一流经过上述目标设备的尾时 延，这是因为若该多个第一记录单元中的第一时延出现了不同，那么说明有记录单元出现了 哈希冲突，又只有大于记录的第一时延的时延才可以更新到第一记录单元中，因此，第一流 映射的多个第一记录单元中最小的第一时延才是比较准确的第一流的尾时延估计，因此采用 该最小的第一时延来估计第一流的尾时延，可以提高估计的准确度。

[0041] 第四方面，本申请提供一种通信时延估计方法，该方法包括：控制器接收第一记录单元 和第二记录单元中记录的信息，该第一记录单元中记录的信息包括第一时延和包数目，该第 一时延为第一流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该 第一流的数据包的个数；该第二记录单元与该第一记录单元关联，该第二记录单元中记录的 信息包括该第一流中的n个数据包中每个数据包经过该目标设备的时延，该n为大于1的整 数；该控制器基于该n个时延估计该第一流经过上述目标设备的尾时延。

[0042] 在本申请实施例中，对于在上述估计窗口中网络设备接收到的目标流的包数目大于阈值 的情况下，也可以将记录的信息发送给控制器，在控制器上述进行尾时延的估计计算。

[0043] 一种可能的实施方式中，该方法还包括：该控制器还接收估计窗口的标识符，该标识符 指示该第一记录单元和该第二记录单元中记录的信息是在该估计窗口内记录的，该估计窗口 为用于估计该第一流经过上述目标设备的尾时延的时间窗口；

[0044] 该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80％且小于100％；该 控制器基于该n个时延估计该第一流经过上述目标设备的尾时延，包括：

[0045] 该控制器将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的 尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大 于0且小于或等于n的整数。

[0046] 在本申请实施例中，可以用该第二记录单元中的n个时延中的时延来估计上述p分位尾 时延，可以通过计算上述n个时延中大于p分位尾时延的时延个数的数学期望来确定上述w。

[0047] 第五方面，本申请提供一种网络设备，该网络设备包括处理单元，用于：

[0048] 从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息；

[0049] 基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包 数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备 接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；

[0050] 更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将 该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该 第一时延用于估计该第一流经过上述目标设备的尾时延。

[0051] 可选的，上述目标设备为上述网络设备；或者，该网络设备为网络中数据平面上的设备， 该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该 数据平面中经过的多个设备。

[0052] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包经过其它设备的时延，该其它设备为该多个设备中 除了该网络设备之外的其它网络设备。

[0053] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包在该数据平面中经过的第一跳设备的入口的时间戳， 该时间戳用于计算该第一数据包经过该多个设备的时延。

[0054] 一种可能的实施方式中，上述网络设备接收到的该目标流的数据包为该网络设备在估计 窗口内接收的数据包，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗 口；该第一时延为目标流的单个数据包经过目标设备的最大时延，包括：该第一时延为该目 标流的单个数据包在该时间窗口内经过该目标设备的最大时延；该第一流经过上述目标设备 的尾时延为该第一流在该时间窗口内经过目标设备的尾时延。

[0055] 一种可能的实施方式中，该第一流映射的该第一记录单元为多个；上述处理单元还用于： 在该估计窗口结束后，该多个第一记录单元中的至少一个单元记录的该包数目小于该阈值的 情况下，确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备的尾时 延估计值，并将该第一单元中记录的该第一时延发送给控制器；该第一单元为该多个第一记 录单元中记录的该第一时延最小的单元。

[0056] 一种可能的实施方式中，上述第一流映射的该第一记录单元为多个；该网络设备还包括 发送单元，用于在该估计窗口结束的情况下，向控制器发送该多个第一记录单元中记录的信 息。

[0057] 一种可能的实施方式中，在该第一记录单元中记录的该包数目大于或等于该阈值的情况 下，上述处理单元还用于：

[0058] 为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个 数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目 标流的数据包中的数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目 标设备的尾时延。

[0059] 一种可能的实施方式中，该网络设备还包括接收单元，用于接收第二数据包，该第二数 据包为该目标流的数据包；

[0060] 上述处理单元，还用于根据轮询的方式获取该第二记录单元的n个时延中的第二时延； 在该第二数据包经过该目标设备的时延大于该第二时延的情况下，将该第二记录单元中的该 第二时延更新为该第二数据包经过该目标设备的时延。

[0061] 一种可能的实施方式中，上述接收单元，还用于接收第三数据包，该第三数据包为该目 标流的数据包，在该第三数据包之前，并在该第二数据包之后，该接收单元接收了m个该目 标流的数据包，该m为大于1的整数；

[0062] 上述处理单元，还用于在该第二记录单元的n个时延中随机获取第三时延；在该第三数 据包经过该目标设备的时延小于该第三时延的情况下，将该第二记录单元中的该第三时延更 新为该第三数据包经过该目标设备的时延。

[0063] 一种可能的实施方式中，上述处理单元还用于：在该估计窗口结束的情况下，基于该第 二记录单元中的n个时延估计该第一流在该估计窗口内经过目标设备的尾时延。

[0064] 可选的，该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80且小于100； 上述处理单元基于该第二记录单元中的n个时延估计该第一流经过上述目标设备的尾时延， 包括：将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延 估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于
0且 小于或等于n的整数。

[0065] 一种可能的实施方式中，该网络设备还包括发送单元，用于在该估计窗口结束的情况下， 向控制器发送该第一记录单元和该第二记录单元中记录的信息。

[0066] 一种可能的实施方式中，上述处理单元基于该流信息确定该第一流映射的第一记录单元， 包括：通过多个哈希函数将该流信息映射到位图中的多个比特位；该位图中的一个比特位与 一个该第一记录单元关联；该网络设备基于该多个比特位确定该第一流映射的该第一记录单 元。

[0067] 一种可能的实施方式中，该第一记录单元中还包括流数目和流信息的异或结果，该流数 目为该目标流的数量，该流信息的异或结果为该目标流的流信息做异或操作后得到的结果。

[0068] 第六方面，本申请提供一种网络设备，该网络设备包括处理单元，用于：

[0069] 从接收的该第一数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数 据包；

[0070] 基于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延和 包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设 备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；

[0071] 更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将 该第一时延更新为该第一数据包经过该目标设备的时延；

[0072] 在该包数目大于或等于阈值的情况下，为该第一记录单元分配一个第二记录单元；该第 二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网 络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大于1的整数； 该n个时延用于估计该第一流经过上述目标设备的尾时延。

[0073] 第七方面，本申请提供一种控制器，该控制器包括：

[0074] 接收单元，用于接收多个第一记录单元中记录的信息，每个该第一记录单元中记录的信 息包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该 包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单 元的流，该目标流包括第一流；

[0075] 处理单元，用于在该包数目小于阈值的情况下，基于该多个第一记录单元中记录该第一 时延估计该第一流经过上述目标设备的尾时延。

[0076] 可选的，该目标设备为该网络设备；或者，该网络设备为网络中数据平面上的设备，该 网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数 据平面中经过的多个设备。

[0077] 一种可能的实施方式中，上述接收单元，还用于接收估计窗口的标识符，该标识符指示 该多个第一记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该第一 流经过上述目标设备的尾时延的时间窗口；

[0078] 上述处理单元基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设 备的尾时延，包括：确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标 设备的尾时延估计值；该第一单元为该多个第一记录单元中记录的该第一时延最小的单元。

[0079] 第八方面，本申请提供一种控制器，该控制器包括：

[0080] 接收单元，用于接收第一记录单元和第二记录单元中记录的信息，该第一记录单元中记 录的信息包括第一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最大时 延，该包数目为该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第一记 录单元关联，该第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包经过 该目标设备的时延，该n为大于1的整数；

[0081] 处理单元，用于基于该n个时延估计该第一流经过上述目标设备的尾时延。

[0082] 一种可能的实施方式中，上述接收单元，还用于接收估计窗口的标识符，该标识符指示 该第一记录单元和该第二记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用 于估计该第一流经过上述目标设备的尾时延的时间窗口；

[0083] 该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80％且小于100％；上 述处理单元基于该n个时延估计该第一流经过上述目标设备的尾时延，包括：

[0084] 将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估 计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小 于或等于n的整数。

[0085] 第九方面，本申请实施例提供一种网络设备，该网络设备可以包括：存储器以及与该存 储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该网络设备执行上述 第一方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该 网络设备执行上述第一方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中， 发送接口和接收接口可以集成为一收发器。处理器用于支持网络设备执行上述第一方面所提 供的通信方法中网络设备除发送以及接收以外的其他处理操作。

[0086] 需要说明的是，本申请实施例中的发送接口和接收接口可以集成在一起，也可以通过耦 合器耦合。所述存储器用于存储第一方面描述的通信时延估计方法的计算机程序，所述处理 器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过 耦合器耦合。

[0087] 另外，本申请中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载 后存储，本申请对于存储器中计算机程序的来源不进行具体限定。本申请实施例中的耦合是 装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、 单元或模块之间的信息交互。

[0088] 一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述 网络设备执行如下操作：

[0089] 从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息； 基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包数目， 该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到 的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；更新该包数目，并 在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第 一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该第一时延用于估计该第 一流经过上述目标设备的尾时延。

[0090] 第十方面，本申请实施例提供一种网络设备，该网络设备可以包括：存储器以及与该存 储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该网络设备执行上述 第二方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该 网络设备执行上述第二方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中， 发送接口和接收接口可以集成为一收发器。处理器用于支持网络设备执行上述第二方面所提 供的通信方法中网络设备除发送以及接收以外的其他处理操作。

[0091] 需要说明的是，本申请实施例中的发送接口和接收接口可以集成在一起，也可以通过耦 合器耦合。所述存储器用于存储第二方面描述的通信时延估计方法的计算机程序，所述处理 器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过 耦合器耦合。

[0092] 另外，本申请中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载 后存储，本申请对于存储器中计算机程序的来源不进行具体限定。本申请实施例中的耦合是 装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、 单元或模块之间的信息交互。

[0093] 一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述 网络设备执行如下操作：

[0094] 从接收的该第一数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数 据包；基于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延 和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络 设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；更新该 包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延 更新为该第一数据包经过该目标设备的时延；在该包数目大于或等于阈值的情况下，为该第 一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过 该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据 包中的部分数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备 的尾时延。

[0095] 第十一方面，本申请实施例提供一种控制器，该控制器可以包括：存储器以及与该存储 器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该控制器执行上述第三 方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该控制 器执行上述第三方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送 接口和接收接口可以集成为一收发器。处理器用于支持控制器执行上述第三方面所提供的通 信方法中控制器除发送以及接收以外的其他处理操作。

[0096] 需要说明的是，本申请实施例中的发送接口和接收接口可以集成在一起，也可以通过耦 合器耦合。所述存储器用于存储第三方面描述的通信时延估计方法的计算机程序，所述处理 器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过 耦合器耦合。

[0097] 另外，本申请中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载 后存储，本申请对于存储器中计算机程序的来源不进行具体限定。本申请实施例中的耦合是 装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、 单元或模块之间的信息交互。

[0098] 一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述 控制器执行如下操作：

[0099] 接收多个第一记录单元中记录的信息，每个该第一记录单元中记录的信息包括第一时延 和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络 设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流，该目标 流包括第一流；在该包数目小于阈值的情况下，基于该多个第一记录单元中记录该第一时延 估计该第一流经过上述目标设备的尾时延。

[0100] 第十二方面，本申请实施例提供一种控制器，该控制器可以包括：存储器以及与该存储 器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该控制器执行上述第四 方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该控制 器执行上述第四方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送 接口和接收接口可以集成为一收发器。处理器用于支持控制器执行上述第四方面所提供的通 信方法中控制器除发送以及接收以外的其他处理操作。

[0101] 需要说明的是，本申请实施例中的发送接口和接收接口可以集成在一起，也可以通过耦 合器耦合。所述存储器用于存储第四方面描述的通信时延估计方法的计算机程序，所述处理 器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过 耦合器耦合。

[0102] 另外，本申请中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载 后存储，本申请对于存储器中计算机程序的来源不进行具体限定。本申请实施例中的耦合是 装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、 单元或模块之间的信息交互。

[0103] 一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述 控制器执行如下操作：

[0104] 接收第一记录单元和第二记录单元中记录的信息，该第一记录单元中记录的信息包括第 一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最大时延，该包数目为 该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第一记录单元关联，该 第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包经过该目标设备的时 延，该n为大于1的整数；基于该n个时延估计该第一流经过上述目标设备的尾时延。

[0105] 第十三方面，本申请实施例提供一种系统，该系统包括网络设备和控制器，该网络设备 为上述第五方面所述的网络设备，该控制器为上述第七方面或者第八方面所述的控制器；或 者，该网络设备为上述第六方面所述的网络设备，该控制器为上述第八方面所述的控制器； 或者，该网络设备为上述第九方面所述的网络设备，该控制器为上述第十一方面或者第十二 方面所述的控制器；或者，该网络设备为上述第十方面所述的网络设备，该控制器为上述第 十二方面所述的控制器。

[0106] 第十四方面，本申请实施例一种计算机可读存储介质，该计算机可读存储介质存储有计 算机程序，该计算机程序被处理器执行以实现上述第一方面任意一项所述的方法；或者，该 计算机程序被处理器执行以实现上述第二方面任意一项所述的方法。

[0107] 第十五方面，本申请实施例一种计算机可读存储介质，该计算机可读存储介质存储有计 算机程序，该计算机程序被处理器执行以实现上述第三方面任意一项所述的方法；或者，该 计算机程序被处理器执行以实现上述第四方面任意一项所述的方法。

[0108] 第十六方面，本申请实施例一种计算机程序产品，当计算机程序产品在计算机上运行时， 使得该计算机执行如上述第一方面任意一项所述的方法；或者，使得该计算机执行如上述第 二方面任意一项所述的方法。

[0109] 第十七方面，本申请实施例一种计算机程序产品，当计算机程序产品在计算机上运行时， 使得该计算机执行如上述第三方面任意一项所述的方法；或者，使得该计算机执行如上述第 四方面任意一项所述的方法。

[0110] 可以理解地，上述提供的网络设备、控制器、系统、计算机存储介质以及计算机程序产 品均用于执行第一方面至第四方面中任一项所提供的方法。因此，其所能达到的有益效果可 参考对应方法中的有益效果，此处不再赘述。

附图说明

[0111] 下面将对本申请实施例中所需要使用的附图作介绍。

[0112] 图1和图2所示为本申请实施例中的一种系统架构示意图；

[0113] 图3所示为本申请实施例提供的一种方法流程示意图；

[0114] 图4和图5所示为一种数据包在传输过程中携带的信息的示意图；

[0115] 图6所示为本申请实施提供的一种网络设备处理流程架构示意图；

[0116] 图7所示为本申请实施例提供的一种网络中信息流走向示意图；

[0117] 图8所示为本申请实施例提供的一种数据包包括的内容示意图；

[0118] 图9所示为本申请实施例提供的仿真结果示意图；

[0119] 图10至图13所示为本申请实施例提供的一种装置的逻辑结构示意图；

[0120] 图14至图17所示为本申请实施例提供的一种装置的硬件结构示意图。

具体实施方式

[0121] 下面结合附图对本申请的实施例进行描述。

[0122] 首先介绍一下本申请实施例涉及的术语：

[0123] 1、数据平面：数据平面指网络中的转发面，刻画的是网络内设备的转发芯片和转发存储 的体系和能力，与拥有普适计算能力的控制平面相对应。

[0124] 2、时延：本申请实施例中所使用的时延，是基于网络设备所提供的硬件时钟时间戳所计 算得到的数据包在网络内传输时间。实际部署方案中，可以是单跳时延(例如可以是由网络 设备提供的数据包在设备内的处理时间)；或者，也可以是网络中端到端时延(例如从第一 跳网络设备入口处到最后一跳网络设备出口处之间的时间)。

[0125] 3、全量流：全量流指的是网络中的全部流，全量流时延指的是该全部流中每一条流的时 延信息。

[0126] 4、尾时延：一个流中p％的数据包的时延小于某一个时延，则该某一个时延称为p分位 时延。在本申请中，在p％的取值在80％至100％之间时，该某一个时延称为尾时延，或者称 为p分位尾时延。例如，一个流中95％的数据包的时延小于某一个时延，则该某一个时延称 为95分位尾时延。

[0127] 下面介绍本申请实施例的一种应用场景。

[0128] 参见图1，图1所示为本申请实施例的一种应用场景的系统架构示意图。图1中可以看 到，该系统架构包括控制平面110和数据平面120。该控制平面110中包括控制器111，该控 制器111可以是软件定义网络(software defined network，SDN)控制器或者操作维护中心(ope ration and maintenance center，OMC)等。控制器111可以部署在一个或多个服务器中，多个 服务器可以组成服务器集群。

[0129] 数据平面120包括g个网络设备121，该g为大于1的整数。图1中所示的网络设备1 和网络设备g之间还可以包括多个网络设备，该多个网络设备之间可以按任意拓扑连接。网 络设备121用于在数据平面中转发数据。网络设备121例如可以是交换机、路由器或者接入 设备等转发设备，该接入设备可以是基站或者无线接入点等。

[0130] 一种可能的实施方式中，参见图2，数据平面中的网络设备中的资源和处理能力较强， 除了实现数据转发的逻辑之外，还可以实现自身的控制逻辑，因此，该用于实现自身控制逻 辑的能力也可以称为设备控制面，该设备控制面也可以属于控制平面110中的能力。在本申 请实施例中，设备控制面可以用于处理采集到的数据包的时延信息以估计对应流的尾时延。

[0131] 需要说明的是，上述图1和图2所示系统架构仅为一个示例，本申请实施例适用的系统 架构不限于上述描述的系统架构。

[0132] 当前业界常用的流的尾时延的测量技术主要可以分为两类：一类是以网络流NetFlow为 代表的网内测量技术，此类技术支持在网络设备中筛选、采样和拷贝相关的报文数据，然后 将报文数据上传到控制器进行尾时延测量；另一类是以带内网络遥测(inband network telemetry， INT)技术为代表的带内操作管理维护(in‑situ operation administration and maintenance，iOAM) 技术。通过对这些现有方案的分析，可以得出全量流时延测量任务的主要挑战为网络设备在 数据平面的存储资源和逻辑能力不足，或者说现有的方案中进行全量流时延测量需要消耗较 多的存储资源和处理资源，资源开销非常大。具体表现在：

[0133] 一方面，当前网络的吞吐极大，如果在控制平面实现全量流时延测量任务，往往会带来 庞大的额外带宽负载(拷贝)或导致覆盖率下降无法做到全量(采样/筛选)，而且当前网络 中并发流数目极多，数据中心中往往同时存在100K‑1M级的并发流，这就导致如果想要记录 逐流的信息，以目前有限的数据平面存储能力，每个流所能利用的存储空间是极其有限的。

[0134] 另一方面，网络设备的逻辑资源和支持的操作相较一般通用计算机较为有限，因此，尽 管当前算法理论研究对于流模型分位估测已经有了较好的研究结论，如何应用和部署成为难 题，因此导致已有方法要么对设备能力有较强假设，实际难以部署；要么舍弃精度，采用更 粗粒度的估测；要么使用较多资源来实现已有算法的折衷版本，放弃了可拓展性，因而难以 支持逐流时延测量。

[0135] 因此本申请方案聚焦于在资源和能力有限的网络设备内，实现在数据平面低开销全量流 尾时延高精度测量的目标，即聚焦于在流的尾时延测量过程中降低网络设备的资源开销。以 下是具体实现的实施例。

[0136] 参见图3，示出了本申请实施例提供的一种通信时延估计方法，该方法用于解决以上的 技术问题。该方法可以应用于上述图1或图2所示的系统架构。该方法可以包括但不限于如 下步骤：

[0137] 301、第一网络设备从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的 第一流的流标识。

[0138] 具体实施例中，该第一网络设备可以是上述图1或图2中数据平面120内的任意一个网 络设备。该第一网络设备可以用于转发一个或多个流的数据包。

[0139] 具体的，第一网络设备接收到一个数据包(为了便于描述，后续称为第一数据包)后，可 以解析该第一数据包，获取该第一数据包中的流信息。示例性地，该流信息例如可以是四元 组、五元组或者七元组等等。该四元组包括流的源网际互联协议(internet protocol，IP)地址、 目的IP地址、源端口和目的端口；该五元组包括源IP地址、目的IP地址、协议号、源端口 和目的端口；该七元组包括源IP地址、目的IP地址、协议号、源端口、目的端口、服务类 型以及接口索引。第一网络设备获得上述第一数据包内的流信息后，可以获知该第一数据包 所属的流(为了便于描述，后续将该流称为第一流)。

[0140] 一种可能的实施方式中，第一网络设备可以对上述获得的流信息进行编码。示例性地， 可以将流信息用一个符号或者数值表示，该符号或者数值可以在该第一网络设备内唯一标识 该第一流。

[0141] 302、该第一网络设备基于该流信息确定该第一流映射的第一记录单元；该第一记录单元 中包括第一时延和包数目，该第一时延为映射到该第一记录单元中的流的单个数据包经过目 标设备的最大时延，该包数目为该第一网络设备接收到的映射到该第一记录单元中的流的数 据包的个数。

[0142] 在具体实施例中，第一网络设备中包括数据结构位图(bitmap)，该位图包括多个比特位， 在本申请实施例中，该位图可以用于判断一个流是否是新的流。具体的，第一网络设备获得 一个流的流信息后，可以通过多个哈希函数分别对该流信息进行哈希计算得到多个哈希值， 该多个哈希值对应位图中多个比特位的位置序号，因此，该多个哈希值可以将该流信息对应 的流映射到该多个比特位中。该多个哈希函数可以是两个或两个以上的哈希函数。

[0143] 位图中每个比特位的初始值可以为第一数值，在基于计算得到的多个哈希值将流映射到 多个比特位后，可以将该多个比特位中的值设置为第二数值。例如，可选的，假设位图中每 个比特位的初始值为0，在基于计算得到的多个哈希值将流映射到多个比特位后，可以将该 多个比特位中的值置1。或者，可选的，假设位图中每个比特位的初始值为1，在基于计算得 到的多个哈希值将流映射到多个比特位后，可以将该多个比特位中的值置0。

[0144] 基于上述逻辑，第一网络设备通过上述多个哈希函数分别对上述第一流的流信息进行哈 希计算得到多个哈希值，基于该多个哈希值将该第一流映射到位图中的多个比特位中，若该 多个比特位中至少有一个比特位中的数值为上述第一数值，则可以确定该第一流为一个新的 流，那么上述第一数据包是第一网络设备接收到的第一个该第一流中的数据包。该新的流指 的是还未映射到该位图中的流。若该多个比特位中每个比特位中的数值为上述第二数值，则 表明该第一流不是新的流，那么上述第一数据包是第一网络设备再次接收到的该第一流中的 数据包。

[0145] 在本申请实施例中，上述位图中的每一个比特位都关联有一个第一记录单元，那么，一 个比特位关联的第一记录单元也是映射到该比特位的流映射的单元。该第一记录单元可以用 于记录包数目和第一时延。

[0146] 上述包数目为该第一网络设备接收到的映射到该第一记录单元中的流的数据包的个数。 可选的，对于某一个第一记录单元，若映射到该第一记录单元的流为一个，那么，该第一记 录单元中的包数目为第一网络设备接收到的该一个流的数据包的个数。可选的，对于该某一 个第一记录单元，若映射到该第一记录单元的流为多个，即出现了哈希冲突，那么，该第一 记录单元中的包数目为第一网络设备接收到的该多个流的数据包的个数和。

[0147] 上述第一时延为映射到该第一记录单元中的流的单个数据包经过目标设备的最大时延。

[0148] 一种可能的实施方式中，该目标设备为上述第一网络设备。或者，另一种可能的实施方 式中，上述第一网络设备为映射到上述第一记录单元中的流在上述数据平面中的最后一跳设 备，该目标设备包括多个设备，该多个设备为映射到该第一记录单元的流中的单个数据包在 该数据平面中经过的设备。

[0149] 可选的，不管是对于上述目标设备为上述第一网络设备的情况，还是对于上述目标设备 包括多个设备的情况，相较基本固定的链路时延，网络设备上的处理时延，尤其是在网络设 备中等待处理的排队时延是造成时延波动的主要因素，因此在本申请实施例中，可以采用网 络设备的处理时间作为时延，该处理时间为一个数据包从该网络设备接收至从该网络设备发 出之间的时间，即该处理时间即为该数据包经过该网络设备的时延。对于上述目标设备为上 述第一网络设备的情况，上述第一时延为上述单个数据包经过该第一网络设备的最大时延。 对于上述目标设备包括多个设备的情况，上述第一时延为上述单个数据包经过该多个设备中 每一个设备的时延的和的最大值。例如，假设该多个设备为设备1和设备2，设备2接收了 上述第一流中的第一数据包和第二数据包，第一个数据包经过设备1和设备2的时延分别为 1毫秒和0.9毫秒，第二个数据包经过设备1和设备2的时延分别为1.1毫秒和1毫秒，那么， 设备2中该第一流映射的第一记录单元中的第一时延为2.1毫秒。基于前述描述，上述数据 包在上述数据平面中经过的所有网络设备对该数据包的处理时间的和，即为该数据包在该数 据平面中整个传输过程的时延。关于如何获取时延，后面介绍，此处暂不详述。

[0150] 或者，可选的，对于上述目标设备包括多个设备的情况，可以将数据包在数据平面中的 传输路径上的传输时延作为数据包在该数据平面中整个传输过程的时延，该传输时延包括该 传输路径中的链路时延和该传输路径中的多个设备中的处理时间造成的时延，本申请中将该 传输时延也称为经过该多个设备的时延，由于该多个设备为上述目标设备，那么，该传输时 延即为经过目标设备的时延。即这种情况下，上述第一时延可以为上述映射到第一记录单元 的流中单个数据包在该整个传输过程的时延的最大值。例如，假设上述第一网络设备接收了 上述第一流中的第一数据包和第二数据包，第一个数据包在该整个传输过程的时延为2.5毫 秒，第二个数据包在该整个传输过程的时延为2.8毫秒，那么，第一网络设备中该第一流映 射的第一记录单元中的第一时延为2.8毫秒。该传输时延为入口网络设备接收到该数据包到 出口网络设备发出该数据包之间的时延。该入口网络设备为在该数据平面中转发该数据包的 第一跳设备，该出口网络设备为在该数据平面中转发该数据包的最后一跳设备。关于如何获 取时延，后面介绍，此处暂不详述。

[0151] 一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。 该流数目为映射到该第一记录单元的流的数量，该流信息的异或结果为映射到该第一记录单 元的流的流信息的异或结果。具体的，若该流数目为1，则该流信息的异或结果为该流信息 本身，或者说，在映射到该第一记录单元的流的数量为一个时，该第一记录单元中记录流信 息的异或结果的位置记录的是该流信息本身。若该流数目大于1，即有多个流映射到同一个 第一记录单元，则该流信息的异或结果为该多个流信息做异或操作后得到的结果。在计算机 中，所有的信息都是用0和1的组成的二进制数据来表示，因此，该流信息的异或的结果也 是由0和1组成的二进制数据。

[0152] 基于上述的描述，第一网络设备将上述第一流映射到位图中的多个比特位中，通过该多 个比特位可以确定该第一流映射的多个第一记录单元。

[0153] 上述通过将流映射到位图中，可以为第一网络设备节省存储资源和降低计算难度以节省 计算资源。

[0154] 303、该第一网络设备更新该包数目，并在该第一数据包经过该目标设备的时延大于该第 一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延。

[0155] 在具体实施例中，上述第一网络设备确定该第一流映射的多个第一记录单元后，可以适 应性地更新该多个第一记录单元中的信息，下面分情况介绍。

[0156] 第一种情况，该第一流是新的流，且该第一流映射的多个比特位中没有出现哈希冲突。 这种情况下，该第一流映射的多个第一记录单元中还未记录有信息或者记录的信息为原始默 认值，那么，上述第一网络设备可以将该多个第一记录单元中记录包数目的位置的值设置为 1。另外，对于该多个第一记录单元中的第一时延，第一网络设备可以获取上述第一数据包经 过上述目标设备的时延，然后将该时延记录到该多个第一记录单元中记录第一时延的位置。

[0157] 具体的，第一网络设备中可以部署一个时延获取模块，时延获取模块可以获取上述第一 数据包经过上述目标设备的时延。

[0158] 可选的，对于上述目标设备为上述第一网络设备的情况，该时延获取模块通过测量和计 算可以获取得到第一数据包在该第一网络设备中的处理时间，该处理时间即为该第一数据包 经过第一网络设备的时延。具体的，该第一网络设备可以测量第一数据包到达该第一网络设 备的时间戳，并估计第一数据包从第一网络设备发出的时间戳，用后面的时间戳减去前面的 时间戳得到一个时间量，该时间量即为第一数据包在该第一网络设备中的处理时间即时延。 那么，第一网络设备将该计算得到的时延记录到上述多个第一记录单元中记录第一时延的位 置。

[0159] 需要说明的是，该第一数据包从网络设备发出的时间戳是根据数据包发送队列的情况计 算得到的一个时间戳，在本申请实施例中，该时延获取模块计算得到的时延允许存在可接受 的误差，或者说，在本申请实施例中，可以将该时延获取模块计算得到的一个时延作为正确 的单个数据包经过网络设备的时延。可选的，该时延获取模块可以估计精确到纳秒的时间， 从而提高了时延的估计精度。

[0160] 可选的，对于上述目标设备包括多个设备的情况，一种可能的实施方式中，可以采用网 络设备的处理时间作为时延。那么，对于上述第一数据包，需要在数据平面中转发该第一数 据包的网络设备上，都设置计算该第一数据包在网络设备中的处理时间的处理逻辑。

[0161] 具体的，对于入口网络设备，计算得到该第一数据包经过该入口网络设备的时延后，将 该时延添加到该第一数据包的包头中，随同第一数据包一起发送给下一跳网络设备。可选的， 该包头可以是自定义添加的专门用于携带时延的包头。该下一跳网络设备接收到携带时延的 该第一数据包后，按照前述逻辑同样地计算该第一数据包在自身中的处理时间即时延，然后 将计算得到的时延与接收的第一数据包包头中的时延相加得到新的时延，并将该新的时延更 新到第一数据包的包头中继续发给下一跳设备。直到该第一数据包到达该数据平面中的最后 一跳设备即上述第一网络设备，该第一网络设备获取该第一数据包包头中的时延，并计算该 第一数据包在自身中的时延，然后将该两个时延相加得到的总的时延，该总的时延即为该第 一数据包经过上述多个设备的时延。获得该总的时延后，第一网络设备可以将该第一数据包 中专门用于携带时延的包头去掉。示例性地，该在每一跳网络设备中将时延加到数据包中已 有时延上并发送的操作可以采用前述介绍过的INT技术来实现。然后，第一网络设备将该总 的时延记录到上述多个第一记录单元中记录第一时延的位置。为了便于理解该实施方式，可 以示例性地参见图4。

[0162] 图4示出了一个简单的数据平面中的网络设备的拓扑示意图，并示出了数据包在传输过 程中携带的信息，假设上述第一数据包在该数据平面中的传输路径为：网络设备1‑网络设备 2‑网络设备5‑网络设备6。则在网络设备1发出的该第一数据包中，携带的时延为该第一数 据包经过该网络设备1的时延a。然后，该第一数据包发送到网络设备2，网络设备2获取该 第一数据包经过自身的时延b，然后，将时延a+b封装到该第一数据包中。然后，该第一数 据包发送到网络设备5，网络设备5获取该第一数据包经过自身的时延c，然后，将时延a+b+c 封装到该第一数据包中。接着，该携带时延a+b+c的第一数据包发送到网络设备6，网络设 备6获取该第一数据包经过自身的时延d，并将d加到时延a+b+c上得到时延a+b+c+d，然后， 将该时延a+b+c+d记录到上述多个第一记录单元中记录第一时延的位置。

[0163] 需要说明的是，在本申请实施例中，虽然上述在不同网络设备中转发的第一数据包中携 带的时延不同，但只要第一数据包中的负载(payload)不变，那么，该携带的时延信息不同数 据包仍然称为第一数据包。

[0164] 可选的，对于上述目标设备包括多个设备的情况，一种可能的实施方式中，可以采用数 据包在数据平面中的传输路径上的传输时延作为数据包在该数据平面中整个传输过程的时延。 那么，对于上述第一数据包，在数据平面中转发该第一数据包的入口网络设备上，该入口网 络设备可以测量该第一数据包到达该入口网络设备的时间戳，然后，将该时间戳添加到该第 一数据包包头中，随该第一数据包一直转发到数据平面的出口网络设备即上述第一网络设备 上。可选的，该包头可以是自定义添加的专门用于携带时间戳的包头。该第一网络设备可以 获取该第一数据包中的时间戳，然后，估测该第一数据包从第一网络设备发出的时间戳，用 后面的时间戳减去前面的时间戳得到一个时间量，该时间量即为该第一数据包经过上述目标 设备的时延。获得该时间量后，第一网络设备可以将该第一数据包中专门用于携带时间戳的 包头去掉。示例性地，该在入口网络设备中将时间戳添加到数据包中，并随数据包传输到出 口网络设备的操作可以采用前述介绍过的INT技术来实现。然后，第一网络设备将该时延记 录到上述多个第一记录单元中记录第一时延的位置。这种实现方式中，需要数据平面内的网 络设备的时钟同步，这样计算得到的时延才准确。
为了便于理解该实施方式，可以示例性地 参见图5。

[0165] 图5示出了一个简单的数据平面中的网络设备的拓扑示意图，并示出了数据包在传输过 程中携带的信息，假设上述第一数据包在该数据平面中的传输路径为：网络设备1‑网络设备 2‑网络设备5‑网络设备6。则在网络设备1为上述入口网路设备，则网络设备1中发出的该 第一数据包中，携带该第一数据包到达该网络设备1时的时间戳，即图5中所示的第一时间 戳。然后，该携带第一时间戳的第一数据包经网络设备2和网络设备5发送到网络设备6， 网络设备6估测该第一数据包从网络设备6发出的时间戳，用后面的时间戳减去前面的时间 戳得到一个时间量，该时间量即为该第一数据包经过上述目标设备的时延。网络设备6将该 时间量记录到上述多个第一记录单元中记录第一时延的位置。

[0166] 一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。 若该第一记录单元中包括流信息的异或结果，由于上述第一流映射的多个比特位中没有出现 哈希冲突，因此，第一网络设备可以将该第一流的流信息保存到该第一流映射的第一记录单 元中记录的流信息的异或结果的位置。若该第一记录单元中包括流数目，那么，第一网络设 备可以将该第一流映射的第一记录单元中记录的流数目设置为1。

[0167] 第二种情况，该第一流是新的流，且该第一流映射的多个比特位中至少有一个比特位出 现哈希冲突。

[0168] 这种情况下，对于该多个比特位中没有哈希冲突的比特位映射的第一记录单元，其中的 包数目和第一时延的更新可以参考上述第一种情况中对应的描述，此处不再赘述。对于该出 现哈希冲突的至少一个比特位映射的至少一个第一记录单元，第一网络设备可以将该至少一 个第一记录单元中的包数目增加1个计数，即将增加1个计数后得到的包数目替换掉原来的 包数目。对于该至少一个第一记录单元中的第一时延，第一网络设备可以根据上述第一种情 况描述的方法获取上述第一数据包经过上述目标设备的时延，然后，将该获取的时延与该至 少一个第一记录单元中每个单元记录的第一时延比较，如果该获取的时延大于该至少一个第 一记录单元中最小的第一时延，将该至少一个第一记录单元中最小的第一时延替换为该获取 的时延。

[0169] 一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。

[0170] 若该第一记录单元中包括流信息的异或结果，对于上述多个比特位中没有哈希冲突的比 特位映射的第一记录单元，第一网络设备可以将该第一流的流信息保存到该第一记录单元中 记录的流信息的异或结果的位置。对于上述出现哈希冲突的至少一个比特位映射的至少一个 第一记录单元，第一网络设备可以将该第一流的流信息和第一记录单元中，记录流信息的异 或结果的位置中的信息(可以是一个流的信息，或者可以是多个流的流信息异或的结果)进行 异或操作，得到异或结果，然后，将该计算得到的异或结果保存到该第一记录单元中记录的 流信息的异或结果的位置中。

[0171] 若该第一记录单元中包括流数目，那么，对于上述多个比特位中没有哈希冲突的比特位 映射的第一记录单元，第一网络设备可以将该第一流映射的第一记录单元中记录的流数目设 置为1。对于上述出现哈希冲突的至少一个比特位映射的至少一个第一记录单元，第一网络 设备可以将该至少一个第一记录单元中的流数目增加1个计数，即将增加1个计数后得到的 流数目替换掉原来的流数目。

[0172] 第三种情况，该第一流不是新的流，且该第一流映射的多个比特位中没有出现哈希冲突。

[0173] 这种情况下，表明上述第一数据包是第一网络设备再次接收到的该第一流中的数据包， 该第一流映射的多个第一记录单元中记录了之前接收到的第一流的数据包的包数目和第一时 延。第一网络设备可以将该第一流映射的第一记录单元中的包数目增加1个计数，即将增加 1个计数后得到的包数目替换掉原来的包数目。另外，对于该多个第一记录单元中的第一时 延，第一网络设备可以获取上述第一数据包经过上述目标设备的时延，然后，将获取的时延 和第一记录单元中记录的第一时延比较，若获取的时延大于该第一记录单元中记录的第一时 延，则第一网络设备将该多个第一记录单元中的第一时延更新为该获取的时延。若获取的时 延不大于该第一记录单元中记录的第一时延，则该多个第一记录单元中的第一时延保持不变。

[0174] 一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。 若该第一记录单元中包括流信息的异或结果，由于该第一流映射的多个比特位中没有出现哈 希冲突，因此，该第一流映射的多个第一记录单元中记录流信息的异或结果的位置中仍然记 录第一流的流信息，保持不变。若该第一记录单元中包括流数目，由于该第一流映射的多个 比特位中没有出现哈希冲突，那么对应的多个第一记录单元中映射的流只有上述第一流，因 此，该第一流映射的多个第一记录单元中记录的流数目保持为1。

[0175] 第四种情况，该第一流不是新的流，且该第一流映射的多个比特位中至少有一个比特位 出现哈希冲突。

[0176] 这种情况下，对于该多个比特位中没有哈希冲突的比特位映射的第一记录单元，其中的 包数目和第一时延的更新可以参考上述第三种情况中对应的描述，此处不再赘述。对于该出 现哈希冲突的至少一个比特位映射的至少一个第一记录单元，其中的包数目和第一时延的更 新可以参考上述第二种情况中对应的描述，此处不再赘述。

[0177] 一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。 由于上述第一流不是新流，因此，该第一流映射的多个第一记录单元中的流信息的异或结果 和流数目保持不变，具体可以参见上述第三种情况中对应的描述。

[0178] 一种可能的实施方式中，上述第一数据包为第一网络设备在预设的时间窗口内接收的数 据包，该预设的时间窗口的大小可以是10毫秒‑100毫秒之间的任意大小；这种情况下，第一 网络设备是以该时间窗口为估计时长分段估计上述第一流的时延，那么，上述第一时延为在 该时间窗口内，映射到第一记录单元中的流的单个数据包经过上述目标设备的最大时延。

[0179] 或者，另一种可能的实施方式中，上述第一数据包为第一网络设备接收到的该第一流中 的任一个数据包，这种情况下，第一网络设备是以该第一流的整体传输时间为估计时长估计 该第一流的时延，那么，上述第一时延为在映射到第一记录单元中的流的整体传输时间内， 该流的单个数据包经过该目标设备的最大时延。

[0180] 在本申请实施例中，上述预设的时间窗口或者上述流的整体传输时间可以统称为估计窗 口，即该估计窗口即为用于估计流的时延的时间窗口。在本申请实施例中，目的是为了估计 流的尾时延，那么，该估计窗口也可以说是用于估计流的尾时延的时间窗口。并且，上述第 一记录单元中记录的信息也是在该估计窗口内估计得到的。

[0181] 在本申请实施例中，对于上述第一流经过上述目标设备的尾时延的估计，包括两种不同 的处理方式，可以通过判断第一网络设备在上述估计窗口内接收的第一流的数据包的个数是 否大于阈值来确定具体的处理方式。具体的，上述第一网络设备更新第一流映射的多个第一 记录单元之后，可以判断该多个第一记录单元中记录的包数目是否大于阈值，当然，该包数 目对应的数据包是第一网络设备在该估计窗口内接收到的。该阈值例如可以是100、1000或 者10000等等，可以根据希望的测量分位与希望的准确率等情况设定，本申请对此不做限制。

[0182] 一种可能的实施方式中，如果上述多个第一记录单元中记录的包数目小于上述阈值，那 么，若该估计窗口还未结束，则第一网络设备继续接收第一流的数据包，然后，更新第一流 映射的多个第一记录单元中的信息，具体的更新可以参见上述步骤303中对应的描述。在该 估计窗口结束之后，第一网络设备可以根据第一流的流信息的哈希值找到该第一流映射的多 个第一记录单元，第一网络设备获取该第一流映射的多个第一记录单元中记录的多个第一时 延，然后，取该多个第一时延中的最小值作为该估计窗口内该第一流经过上述目标设备的尾 时延的估计值。

[0183] 上述这种处理方式中，由于在上述估计窗口内第一流的数据包个数小于上述阈值，则表 明该数据包的个数相对较少，那么，在该估计窗口内第一流的80分位尾时延至100分位尾时 延之间的尾时延相差较小，且该第一流映射的第一记录单元中记录的第一时延为估计窗口内 单个数据包经过该目标设备的最大时延，因此，可以用第一流映射的第一记录单元中记录的 第一时延，来估计该第一流在该估计窗口内的80分位尾时延至100分位尾时延之间的任一个 尾时延，这种估计误差较小，在可接受的范围内。又因为可能存在哈希冲突，如果第一流映 射的多个第一记录单元中存在哈希冲突的单元记录的第一时延，与没有哈希冲突的单元记录 的第一时延不同，那么，基于上述取较大的时延替换较小的时延的原则，该存在哈希冲突的 单元记录的第一时延不小于该没有哈希冲突的单元记录的第一时延，因此，选择该第一流映 射的多个第一记录单元中最小的第一时延作为该估计窗口内该第一流经过上述目标设备的尾 时延的估计值更准确。

[0184] 一种可能的实施方式中，对于上述第一流映射的比特位中存在哈希冲突的比特位映射的 至少一个第一记录单元，在上述估计窗口结束之后，第一网络设备在对第一记录单元中的信 息解码的过程中，可以将该至少一个第一记录单元中的流信息的异或结果与第一流的流信息 再进行一次异或操作，并将该异或操作的结果记录到该至少一个第一记录单元中，这样可以 将第一流的流信息从该至少一个第一记录单元中删除。同时，第一网络设备可以将该至少一 个第一记录单元中的流数目减1，且包数目减去该估计窗口内接收到的第一流的数据包的个 数，但是第一时延不做改动。通过这些处理，可以将第一流的相关信息从该至少一个第一记 录单元中删除，对于有多个估计窗口的情况下，该至少一个第一记录单元可以准备用于记录 下一个估计窗口内第一流的相关信息。

[0185] 而对于上述第一流映射的比特位中不存在哈希冲突的比特位映射的第一记录单元，在上 述估计窗口结束之后，第一网络设备可以将这些第一记录单元中记录的信息全部清除，对于 有多个估计窗口的情况下，这些第一记录单元可以准备用于记录下一个估计窗口内第一流的 相关信息。

[0186] 一种可能的实施方式中，如果上述多个第一记录单元中记录的包数目大于或等于上述阈 值，那么，在该包数目等于该阈值时，若该估计窗口还未结束，第一网络设备为该多个第一 记录单元中每个单元配置一个关联的第二记录单元，第一记录单元和第二记录单元之间通过 索引关联，第一网络设备可以配置多个索引记录单元用于专门记录第一记录单元和第二记录 单元之间的索引信息，每个索引记录单元记录一个第一记录单元和一个第二记录单元之间的 索引信息。该第二记录单元中可以记录n个时延，该n为大于1的整数。该n个时延为包数 目等于上述阈值后第一网络设备接收的目标流中的n个数据包经过上述目标设备的时延。若 第一网络设备接收上述第一数据包后，第一记录单元中记录的包数目刚好达到该阈值，那么， 该n个数据包为第一网络设备在该第一数据包之后接收的该目标流的数据包中的n个数据包。 该目标流即为上述映射到第一记录单元中的流，若映射到第一记录单元中的流只有上述第一 流，则该目标流即为该第一流；若映射到第一记录单元中的流有包括上述第一流的多个流， 则该目标流即为该多个流。

[0187] 具体的，在配置上述第二记录单元时，该第二记录单元中可以默认配置n个时延的初始 值，或者该第二记录单元中一开始为空。本申请实施例中，可以通过轮询的方式更新该第二 记录单元中的n个时延。在上述第一记录单元中记录的包数目等于上述阈值之后，第一网络 设备接收的目标流的前n个数据包对应的经过上述目标设备的时延，可以依次记录到该第二 记录单元中记录n个时延的位置中。然后，在该n个数据包之后，第一网络设备每接收到目 标流的一个数据包，可以通过轮询的方式确定第二记录单元中的一个时延，然后，在该时延 小于该接收到的数据包经过上述目标设备的时延的情况下，用该接收到的数据包经过上述目 标设备的时延替换掉该第二记录单元中的一个时延。

[0188] 上述轮询的方式指的是从上述n个时延中的某一个时延开始，按预设顺序依次逐一查询 各个时延，直到完成该n个时延的查询后，再次从该某一个时延开始，并按该预设顺序依次 逐一查询各个时延，直到再次完成该n个时延的查询，循环执行该查询的操作。为了便于理 解，下面举例说明。参见表1。

[0189] 表1

[0190]时延的位置 1 2 3 4 5
时延的值 0.3毫秒 0.35毫秒 0.28毫秒 0.32毫秒 0.26毫秒

[0191] 表1示例性示出了一个第二记录单元中记录的时延。假设该第二记录单元中可以记录5 个目标流的数据包经过上述目标设备的时延，对应位置上的时延参见上述表1。假设该表1 中记录的5个时延，是在上述第一记录单元中记录的包数目等于上述阈值之后，第一网络设 备接收的第一流的前5个数据包经过上述目标设备的时延。另外，假设上述轮询的方式是从 位置1的时延开始依次查询到位置5的时延，然后，轮回查询位置1的时延，再依次查询到 位置5的时延，如此循环。

[0192] 基于表1，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第1个数据包， 并获取了该第1个数据包经过上述目标设备的时延，为0.32毫秒。然后，第一网络设备基于 该轮询的方式，首先查询第二记录单元中位置1中的时延，该时延为0.3毫秒。由于0.32毫 秒大于0.3毫秒，那么，第一网络设备将该位置1中的时延0.3毫秒替换为0.32毫秒。
经过 一轮的操作之后，即第一网络设备在上述包数目等于上述阈值之后接收了5个第一流的数据 包，并轮询更新了该第二记录单元之后，该第二记录单元中的5个时延参见表2。

[0193] 表2

[0194] 时延的位置 1 2 3 4 5时延的值 0.32毫秒 0.35毫秒 0.3毫秒 0.32毫秒 0.28毫秒

[0195] 基于表2，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第6个数据包， 并获取了该第6个数据包经过上述目标设备的时延，为0.25毫秒。然后，第一网络设备基于 该轮询的方式，查询第二记录单元中位置1中的时延，该时延为0.32毫秒。由于0.25毫秒小 于0.32毫秒，那么，第一网络设备将该位置2中的时延0.32毫秒保持不变，即此次不更新该 位置1中的时延。

[0196] 可选的，因为后续是基于该第二记录单元中记录的n个时延来估计目标流在估计窗口内 经过目标设备的尾时延，若目标流的包数目非常多，此时按照上述轮询的方式更新上述第二 记录单元中的n个时延，那么，最后得到的该n个尾时延为最大的n个尾时延，这时该n个 尾时延可以用于较准确地估计接近100分位尾时延，但是用于估计80分位尾时延、85分位 尾时延、90分位尾时延或者95分位尾时延，甚至99分位尾时延等尾时延，其误差较大，估 计出来的尾时延不准确。为了解决该问题，本申请实施例提供了如下操作：

[0197] 在上述轮询的方式更新上述第二记录单元的基础上，在上述包数目等于上述阈值之后， 第一网络设备每接收预设个数的目标流的数据包后，再次接收到目标流的一个数据包，可以 在该第二记录单元中随机查询一个时延，然后，比较该数据包经过上述目标设备的时延与该 查询到的一个时延的大小。在该数据包经过上述目标设备的时延小于该查询的一个时延时， 用该数据包经过上述目标设备的时延替换该查询的一个时延记录在该第二记录单元中，否则 不更新该查询的一个时延。

[0198] 上述预设个数可以是10个、50个或者100个等等，本申请对预设个数的具体取值不做 限制。为了便于理解，下面举例说明。

[0199] 还是基于上述表1为例进一步描述，假设该预设个数为8个，那么，在上述包数目等于 上述阈值之后，第一网络设备接收了8个目标流的数据包，并轮询更新了该第二记录单元之 后，该第二记录单元中的5个时延参见表3。

[0200] 表3

[0201]时延的位置 1 2 3 4 5
时延的值 0.32毫秒 0.35毫秒 0.31毫秒 0.32毫秒 0.28毫秒

[0202] 基于表3，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第9个数据包， 并获取了该第9个数据包经过上述目标设备的时延，为0.27毫秒。然后，第一网络设备在该 第二记录单元的5个位置的时延中随机查询一个时延，假设随机查询到了位置5的时延0.28 毫秒。由于0.27毫秒小于0.28毫秒，那么，第一网络设备将该位置5中的时延0.28毫秒替 换为0.27毫秒，具体的可以参见表4。

[0203] 表4

[0204]时延的位置 1 2 3 4 5
时延的值 0.32毫秒 0.35毫秒 0.31毫秒 0.32毫秒 0.27毫秒

[0205] 需要说明的是，由于存在哈希冲突，那么上述多个第一记录单元中，存在哈希冲突的比 特位映射的单元的包数目大于没有哈希冲突的比特位映射的单元的包数目。对于该存在哈希 冲突的比特位映射的单元，只要其包数目达到阈值后，也可以为该单元配置一个第二记录单 元，然后，用该第二记录单元记录映射到该单元的多个流中，包数目大于上述阈值后第一网 络设备接收的部分数据包经过上述目标设备的时延，之后更新第二记录单元的操作可以参见 上述的描述，此处不再赘述。

[0206] 基于上述对第二记录单元的更新方式，在上述估计窗口结束之后，第一网络设备基于该 第一流映射的多个第一记录单元查找到关联的第二记录单元，具体的，可以通过上述索引记 录单元中记录的索引信息查找到该第一记录单元关联的第二记录单元。然后，第一网络设备 获取该第二记录单元中记录的n个时延，基于该n个时延估计第一流在该估计窗口内经过目 标设备的尾时延。具体的，假设该n个时延从小到大排序，可以用该n个时延中排序为w的 时延来估计该第一流在该估计窗口内的p分位尾时延，排序在该w之前的时延小于或等于该 p分位尾时延，该w为大于0且小于或等于n的整数。

[0207] 一种可能的实施方式中，为了避免哈希冲突导致的数据错乱，可以选择流数目为1或者 流数目最小的第一记录单元关联的第二记录单元中的n个时延来估计第一流在该估计窗口内 经过目标设备的尾时延。

[0208] 一种可能的实施方式中，假设上述估计窗口内第一网络设备接收到的第一流的数N(1‑p)据包为 N个，该N为大于或等于n的整数。那么，上述w可以是n(1‑1/n) ，即可以用上述n N(1‑p)
个时延中的排序为n(1‑1/n) 大的时延来估计该第一流在该估计窗口内的p分位尾时N(1‑p)
延， 该第n(1‑1/n) 大的时延为该第一流中N个数据包对应的N个经过上述目标设备的时 延中第N*p大的时延的估计值。具体的估计过程可以示例性地参见下面的计算公式：

[0209]

[0210] 其中，aK表示上述N个经过上述目标设备的时延中第K大的时延，aj表示上述n个时延中第 j大的时延，C表示第二记录单元中的n个时延的集合，ci表示第二记录单元中第i个位置记 录的时延，P(aK∈C)表示aK被第二记录单元任一位置记录的概率，aK meet ci表示aK在轮询中 与第二记录单元中第i个位置记录的时延比较，∧表示“且”，aK＝max(aj|ajmeet ci)表示aK等 于所有与该第i个位置记录的时延比较的时延中的最大值。公式计算aK被记录的概率。

[0211] 假设aK meet ci的概率为1/n，即aK遇到C中的每个数的概率相同，实际在上述轮询的方 式中遇到不同位置的时延的次数之间的差至多为1，因此，这里假设aK meet ci的概率为1/n 的误差较小。基于该假设，那么：

[0212]

[0213] 则

[0214]

[0215] 则

[0216]

[0217] 其中，表示ci>aN*p表示上述第i个位置记录的时延大于p分位尾时延。E(Num(ci>aN*p))表 示上述n个时延中大于p分位尾时延的时延个数的数学期望，E(Num(ci≤aN*p))表示该n个 时延不大于p分位尾时延的时延个数的数学期望，即在理论上，p分位尾时延的期N(1‑p)望为该n 个时延中第 大的记录时延，因此w可以是n(1‑1/n) 。

[0218] 一种可能的实施方式中，对于第一流的包数目非常多的情况，上述记录第二记录单元中 的n个时延时对应采用了每隔一定的包数目就随机用小的时延替换原来大的时延的方式，以 降低最后的估计误差。那么，配套的尾时延估计处理方式可以参见如下描述：

[0219] 假设上述估计窗口内第一网络设备接收到的第一流的数据包为N个，该N为大于或N(1‑p)等于 n的整数。那么，上述w可以是n(1‑q/n) ，即可以用上述n个时延中的排序为 n(1‑N(1‑p) N(1‑p)
q/n) 大的时延来估计该第一流在该估计窗口内的p分位尾时延，该第n(1‑ q/n) 大的时延为该第一流中N个数据包对应的N个经过上述目标设备的时延中第N*p 大的时延的估计值，该q为大于0且小于1的实数。具体的估计过程可以示例性地参见下面 的计算公式：

[0220]

[0221] 其中相关字符表示的含义可以参见上述公式(1)中相关的描述，此处不再赘述。

[0222] 同理，假设aK meet ci的概率为1/n，即aK遇到C中的每个数的概率相同，实际在上述轮 询的方式中遇到不同位置的时延的次数之间的差至多为1，因此，这里假设aK meet ci的概率 为1/n的误差较小。该问题的精确分析与时延到达的时序相关，解决方法复杂，难以精确求 解，因此，可以假设每隔一定的包数目就随机用小的时延替换原来大的时延的方式与第二记 录单元的默认记录方式互相独立，即假设在每次进行轮询比较时以q的概率执行第二记录单 元的默认记录方式，以1‑q的概率执行随机小的时延替换原来大的时延的方式，q是设定好的 大于0小于1的实数。基于该假设，那么：

[0223]

[0224] 则

[0225]

[0226] 则

[0227]

[0228] 其中，表示q表示以q的概率执行第二记录单元的默认记录方式，q是设定好的大于0小于 1的实数，相关字符表示的含义可以参见上述公式(1)中相关的描述，此处不再赘述。

[0229] 一种可能的实施方式中，关于在上述估计窗口结束之后对第一流映射的多个第一记录单 元中记录的信息的处理，可以参见上述包数目小于阈值的情况中对应的描述。关于该多个第 一记录单元关联的多个第二记录单元，对于不存在哈希冲突的第二记录单元，第一网络设备 可以将这些第二记录单元的存储空间释放，以用于后续其它信息的记录存储。

[0230] 基于上述介绍的尾时延估计的方法，第一网络设备可以估计出上述第一流在上述估计窗 口内经过目标设备的尾时延的大小。对于估计窗口为上述预设的时间窗口的情况，上述第一 流的传输过程中可以包括多个该预设的时间窗口，第一网络设备可以在该多个预设的时间窗 口中的每个窗口中，估计出第一流在该窗口内经过目标设备的尾时延，具体的估计过程可以 参见前述的描述。第一网络设备可以每估计出一个预设的时间窗口内第一流经过上述目标设 备的尾时延，就将该尾时延发送给控制器用于后续的汇总分析和处理。或者第一网络设备可 以在估计出该多个预设的时间窗口内第一流经过上述目标设备的尾时延后，一起将多个尾时 延发送给控制器进行后续的汇总分析和处理。对于估计窗口为上述流的整体传输时间的情况， 第一网络设备可以在估计得到第一流经过上述目标设备的尾时延后将该估计得到的第一流经 过上述目标设备的尾时延发送给控制器，由控制器进一步根据这些尾时延信息进行汇总分析 和处理。

[0231] 控制器除了接收来自第一网络设备的第一流经过上述目标设备的尾时延信息，还可以接 收来自第一流在数据平面中经过的其它网络设备的第一流经过上述目标设备的尾时延信息， 该其它网络设备中的每个网络设备关于该第一流经过上述目标设备的尾时延的估计和处理操 作与第一网络设备相同，则不再赘述。

[0232] 控制器接收到上述第一网络设备和上述其它网络设备发送的第一流经过上述目标设备的 尾时延信息之后，可以现在时序上进行汇总，例如可以采用以包数目为权重，通过加权求分 位的方式得到更长时间窗口(直至流生命周期)下的尾时延估计数据。然后，可以基于这些 尾时延估计数据，根据网络运维的需要，可以进行尾时延突变预警，从而检测拥塞等异常， 可以进行尾时延的网络空间绘制，得到基于时延的网络切片分析和网络瓶颈检测。根据得到 的全量流尾时延数据，可以部署面向用户和运维人员的多种网络测量工具。

[0233] 一种可能的实施方式中，上述基于上述第一记录单元，或者第一记录单元和第二记录单 元中记录的信息来估计第一流在对应估计窗口中的尾时延的操作，可以是由控制器来实现的。 具体的，第一网络设备在估计窗口内在第一流映射的第一记录单元，或者第一记录单元和第 二记录单元中记录好相关的信息，具体记录的信息参见前述的描述，此处不再赘述。然后， 第一网络设备在估计窗口结束之后，将该第一记录单元，或者第一记录单元和第二记录单元 中记录的信息发送给控制器，可选的，记录第一记录单元和第二记录单元之间的索引信息的 索引记录单元中的信息也一起发送给控制器。由控制器基于这些信息来估计第一流在对应估 计窗口内经过目标设备的尾时延，具体的估计方式可以参见上述第一网络设备的估计方式， 此处不再赘述。

[0234] 可选的，对于第一记录单元中只记录了上述第一时延和包数目的情况，第一网络设备在 将第一记录单元中的信息发送给控制器时，可以将映射到该第一记录单元的流的流信息一起 发送给控制器，以便于控制器将第一记录单元中记录的信息与对应的流关联。

[0235] 为了更好地理解上述介绍的通信时延估计方法，下面结合附图进一步举例说明。

[0236] 参见图6，图6示例性示出了上述第一网络设备处理流程架构示意图。在图6中，整个 过程涉及到布隆过滤器、流编码器、长流检查单元、长流时延记录单元和信息记录单元。

[0237] 具体的，第一网络设备通过布隆过滤器将上述第一流的流信息哈希到位图中的多个比特 位中，通过该多个比特位可以确定第一流映射的在信息记录单元中的多个第一记录单元。

[0238] 第一网络设备通过上述流编码器执行前述介绍流信息的异或操作，将异或操作的结果记 录到第一记录单元中，或者可以将第一流的流信息记录到第一记录单元中，另外还可以将时 延信息、包数目和流数目记录到第一流映射的多个第一记录单元中，并返回该多个第一记录 单元中每个单元记录的包数目。

[0239] 第一网络设备通过上述长流检查单元检查由流编码器返回的多个包数目中是否有等于上 述阈值的数目，若有，那么，为等于阈值的包数目对应的第一记录单元分配一个第二记录单 元，并分配一个索引记录单元用于记录该第一记录单元和该第二记录单元之间的索引信息， 另外，返回该第二记录单元在信息记录单元中的具体位置的信息。

[0240] 在上述等于阈值的包数目对应的第一记录单元中记录的包数目大于该阈值的情况下，第 一网络设备通过上述长流时延记录单元按照前述介绍的轮询的方式将较大的数据包经过上述 目标设备的时延记录到该第二记录单元中。可选的，第一网络设备通过该长流时延记录单元 还可以按照前述介绍的每隔一定数目的数据包，就在该第二记录单元记录的时延中随机选择 一个时延替换为较小的时延。

[0241] 上述第一网络设备通过布隆过滤器、流编码器、长流检查单元和长流时延记录单元执行 的操作的具体实现，可以参考前述的相关描述，此处不再赘述。

[0242] 在图6中，还可以看到，信息记录单元中分配给所有第一记录单元的总存储大小为k*(9+x) 字节(B)，该k为位图中比特位的个数，因为每个比特位映射有一个第一记录单元，该k为大 于1的整数。另外，每个第一记录单元中可以包括流信息的异或结果、流数目、包数目和第 一时延这四项信息，示例性地，可以用1个字节记录流数目，用4个字节记录包数目，用4 个字节记录第一时延，用x字节记录流信息的异或结果，该x可以根据需要配置。由此可以 计算得到分配给所有第一记录单元的总存储大小为k*(9+x)字节。另外，信息记录单元中分配 给所有索引记录单元的总存储大小为k*log2(M)/8字节，分配给所有第二记录单元的总存储大 小为M*n*4个字节。其中，该M为第二记录单元的个数，可以根据对于可能超过阈值的并 发流数目进行估算，具体的，可以依赖已有的流大小分布和网络切片的结果来估算，该n为 每个第二记录单元可以最多记录的时延信息个数，每个第二记录单元的大小为n*4个字节， 每个时延信息用4个字节来记录。

[0243] 需要说明的是，这里给出的具体的字节数只是一个示例，不构成对本申请实施例的限制， 具体实现时可以是采用其它大小的字节数来记录这些信息。

[0244] 参见图7，在图7中，每个网络设备均可以是上述的第一网络设备，那么，每个网络设 备可以实现上述第一网络设备实现的操作，或者说第一网络设备为该图7中所示的网络设备 中的任一个。具体的，该每个网络设备和控制器之间首先建立控制信息通道，控制器设置估 计窗口、分位点和监控阈值等控制器信息，然后，将这些控制信息通过该控制信息通道发送 给该每个网络设备。然后，该每个网络设备和控制器建立数据传送通道，控制器向该每个网 络设备发送流的尾时延测量的数据信号。该每个网络设备根据该数据信号，开始对接收到的 流的时延的相关信息进行记录，具体记录的信息参见上述第一记录单元和第二记录单元中记 录的信息。

[0245] 该每个网络设备在上述第一记录单元，或者上述第一记录单元和上述第二记录单元中记 录好相关的信息后，一种可能的实施方式中，该每个网络设备通过自身的设备控制面将上述 记录单元记录的信息发送给控制器，由控制器基于这些信息进行流的尾时延估计，然后，控 制器对估计得到的尾时延进行汇总分析，并将分析之后的数据用于运维等相关处理需要。具 体的估计过程和汇总分析可以参见前述的相关描述，此处不再赘述。关于记录单元中记录的 信息发送到控制器的过程，可以示例性地参见图8。

[0246] 参见图8，图8所示中，数据平面中的每个网络设备都可以执行上述第一网络设备执行 的操作，因此，每个网路设备都记录了数据包时延的相关信息。还是以第一网络设备为例， 在对应的估计窗口结束之后，第一网络设备将记录单元记录的信息转到自身的设备控制面， 具体的，可以是该设备控制面通过pull操作获取这些记录单元中的信息，或者，可以是第一 网络设备将这些记录单元所组成的寄存器组push到自身的设备控制面。具体的，这些记录单 元可以包括上述第一流映射的第一记录单元、索引记录单元和第二记录单元中记录的信息， 图8中以第一流映射的第一记录单元为三个，且对应的第二记录单元也为三个为例示出，但 具体实现中不限制该第一和第二记录单元的个数。

[0247] 另外，图8所示中，假设第一流经过上述目标设备的尾时延估计是由控制器来执行估计 的，那么，第一网络设备的设备控制面可以将获取的上述记录单元的信息以数据包的形式通 过上述建立的数据传送通道发送给控制器。具体发送的数据包的格式可以参见图8中所示的 格式，该数据包中包括网络设备标识(sid)、估计窗口标识符(tw)、数据类型(type)和记录单元 记录的信息。其中，网络设备标识用于识别发送数据包的网络设备，估计窗口标识符用于识 别发送的记录单元中的信息是哪个估计窗口中记录的信息，数据类型用于识别数据包中的负 载数据是第一记录单元中的信息，还是索引记录单元中的信息，或者是第二记录单元中的信 息。在图8中示例性地，数据类型为1，则表明数据包中的负载数据是第一记录单元中的信 息，数据类型为2，则表明数据包中的负载数据是索引记录单元中的信息，数据类型为3，则 表明数据包中的负载数据是第二记录单元中的信息。

[0248] 另一种可能的实施方式中，在对应的估计窗口结束后，可以将记录的信息发送到自身的 设备控制面进行对应的尾时延估计，具体的估计可以参见上述第一网络设备估计第一流经过 上述目标设备的尾时延的描述。然后，该每个网络设备将估计得到的流的尾时延信息发送给 控制器，由控制器汇总分析，并将分析之后的数据用于运维等相关处理需要。示例性地，还 是以第一网络设备为例，第一网络设备将记录单元记录的信息转到自身的设备控制面的具体 方式可以参见上述对图8中的对应描述，此处不再赘述。第一网络设备的设备控制面获得这 些信息之后，估计得到对应估计窗口内第一流经过上述目标设备的尾时延后，可以通过上述 建立的数据传送通道将该尾时延发送给控制器。具体的，该尾时延也是封装在数据包中发送 的，为了识别该数据包中的数据为尾时延的数据包，可以在该数据包的包头中的设置TCP预 留字段特殊值，这样控制器收到数据后，发现数据包头中存在该TCP预留字段特殊值，则可 确定该数据包为包括流的尾时延的数据包。另外，该数据包中同样包括上述网络设备标识(sid)、 估计窗口标识符(tw)和数据类型(type)，并且还可以包括第一流的流信息和在对应估计窗口内 接收的第一流的包数目等信息。

[0249] 可选的，对于估计窗口内第一网络设备接收到的目标流的包数目小于上述阈值的情况， 由于目标流映射的第一记录单元没有关联的第二记录单元，所以第一网络设备向自身的设备 控制面转过去的信息不包括第二记录单元和索引记录单元的信息，其余的信息仍然发送，具 体可以参见上述描述的内容。

[0250] 上述介绍的实施例中，虽然大部分是以第一流和第一数据包为例介绍，但是，上述第一 网络设备可以通过上述介绍的方式记录每一个经过自身的流的信息，从而可以实现每一个流 的尾时延的估计，即实现全量流的尾时延估计。

[0251] 综上所述，本申请实施例中，可以实现逐流的尾时延信息测量，获得细粒度下全量流的 逐流尾时延信息。并且，可以在不超过30MB的情况下支持1M流的99分位时延的测量。同 时，本申请实施例的数据平面逻辑可部署在可编程数据平面内，例如可部署在Barefoot Tofino 交换机上，属于网络设备的预设能力，具备较好的可部署性。另外，对于包数目大于阈值的 情况下，通过上述轮询的方式和每隔一定的包数目就随机选择第二记录单元中的时延替换为 较小的时延的方式更新第二记录单元的信息，相较同等空间开销的随机sketch算法，流的尾 时延的测量精度有显著提升。例如，仿真实验使用NS3仿真平台，网络拓扑为数据中心常见 的胖树Fat‑Tree拓扑，流分布数据使用大型数据中心的开源数据，网络负载设置在50％，同 一个端的流满足泊松到达。第二记录单元的n＝10，随机sketch算法使用在此条件下本申请实 施例相同的存储空间进行流时延的采样和存储。估计窗口设置为100ms，其他网络设置也为 合理值，在此实验环境下可以得到图9所示的仿真结果。在仿真结果中，对于99分位尾时延， 测量误差降低96.5％；而对于95分位尾时延，测量误差降低
80.7％。

[0252] 相比于现有的尾时延测量方案，本申请实施例中，通过将在估计窗口内采集流的尾时延 的相关信息，并采用上述各种记录单元来记录信息，减少不必要信息的记录，使得最终获取 到有效的信息，从而可以有效地减少了重复或者无效的信息上报，大大减少了产生的带宽额 外负载。

[0253] 综上，本申请实施例能够在每个流的尾时延测量过程中降低网络设备的资源开销，使得 网络设备可以在有限的存储资源内支持大规模网络大量并发流的逐流尾时延测量任务，同时 不产生庞大的额外负载，取得良好的测量精度。

[0254] 上述主要对本申请实施例提供的通信时延估计方法进行了介绍。可以理解的是，各个设 备为了实现上述对应的功能，其包含了执行各个功能相应的硬件结构和/或软件模块。结合本 文中所公开的实施例描述的各示例的单元及步骤，本申请能够以硬件或硬件和计算机软件的 结合形式来实现。某个功能究竟以硬件还是计算机软件驱动硬件的方式来执行，取决于技术 方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用使用不同方法来实现 所描述的功能，但这种实现不应认为超出本申请实施例的范围。

[0255] 本申请实施例可以根据上述方法示例对设备进行功能模块的划分，例如，可以对应各个 功能划分各个功能模块，也可以将两个或两个以上的功能集成在一个模块中。上述集成的模 块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。需要说明的是，本申 请实施例对模块的划分是示意性的，仅仅为一种逻辑功能划分，实际实现时可以有另外的划 分方式。

[0256] 在采用对应各个功能划分各个功能模块的情况下，图10示出了装置的一种可能的逻辑结 构示意图，该装置可以是上述方法实施例中所述的第一网络设备，或者可以是该第一网络设 备中的芯片，或者可以是该第一网络设备中的处理系统等。该装置1000包括处理单元1001， 可选的，还可以包括发送单元1002和/或接收单元1003。其中：

[0257] 处理单元1001，用于：

[0258] 从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息； 该处理单元1001可以用于实现上述图3中步骤301中获取流信息的操作；

[0259] 基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包 数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备 接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该处理单元 1001可以用于实现上述图3中步骤302中确定第一流映射的第一记录单元的操作；

[0260] 更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将 该第一时延更新为该第一数据包经过该目标设备的时延；该处理单元1001可以用于实现上述 图3中步骤303中更新的操作；在该包数目小于阈值的情况下，该第一时延用于估计该第一 流经过上述目标设备的尾时延。

[0261] 可选的，上述目标设备为上述网络设备；或者，该网络设备为网络中数据平面上的设备， 该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该 数据平面中经过的多个设备。

[0262] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包经过其它设备的时延，该其它设备为该多个设备中 除了该网络设备之外的其它网络设备。

[0263] 一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目 标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面 中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的 时延；该第一数据包中包括该第一数据包在该数据平面中经过的第一跳设备的入口的时间戳， 该时间戳用于计算该第一数据包经过该多个设备的时延。

[0264] 一种可能的实施方式中，上述网络设备接收到的该目标流的数据包为该网络设备在估计 窗口内接收的数据包，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗 口；该第一时延为目标流的单个数据包经过目标设备的最大时延，包括：该第一时延为该目 标流的单个数据包在该时间窗口内经过该目标设备的最大时延；该第一流经过上述目标设备 的尾时延为该第一流在该时间窗口内经过目标设备的尾时延。

[0265] 一种可能的实施方式中，该第一流映射的该第一记录单元为多个；上述处理单元1001还 用于：在该估计窗口结束后，该多个第一记录单元中的至少一个单元记录的该包数目小于该 阈值的情况下，确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备 的尾时延估计值，并将该第一单元中记录的该第一时延发送给控制器；该第一单元为该多个 第一记录单元中记录的该第一时延最小的单元。

[0266] 一种可能的实施方式中，上述第一流映射的该第一记录单元为多个；该网络设备还包括 发送单元1002，用于在该估计窗口结束的情况下，向控制器发送该多个第一记录单元中记录 的信息。

[0267] 一种可能的实施方式中，在该第一记录单元中记录的该包数目大于或等于该阈值的情况 下，上述处理单元1001还用于：

[0268] 为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个 数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目 标流的数据包中的数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目 标设备的尾时延。

[0269] 一种可能的实施方式中，该网络设备还包括接收单元1003，用于接收第二数据包，该第 二数据包为该目标流的数据包；

[0270] 上述处理单元1001，还用于根据轮询的方式获取该第二记录单元的n个时延中的第二时 延；在该第二数据包经过该目标设备的时延大于该第二时延的情况下，将该第二记录单元中 的该第二时延更新为该第二数据包经过该目标设备的时延。

[0271] 一种可能的实施方式中，上述接收单元1003，还用于接收第三数据包，该第三数据包为 该目标流的数据包，在该第三数据包之前，并在该第二数据包之后，该接收单元1003接收了 m个该目标流的数据包，该m为大于1的整数；

[0272] 上述处理单元1001，还用于在该第二记录单元的n个时延中随机获取第三时延；在该第 三数据包经过该目标设备的时延小于该第三时延的情况下，将该第二记录单元中的该第三时 延更新为该第三数据包经过该目标设备的时延。

[0273] 一种可能的实施方式中，上述处理单元1001还用于：在该估计窗口结束的情况下，基于 该第二记录单元中的n个时延估计该第一流在该估计窗口内经过目标设备的尾时延。

[0274] 可选的，该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80且小于100； 上述处理单元1001基于该第二记录单元中的n个时延估计该第一流经过上述目标设备的尾时 延，包括：将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾 时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0 且小于或等于n的整数。

[0275] 一种可能的实施方式中，该网络设备还包括发送单元1002，用于在该估计窗口结束的情 况下，向控制器发送该第一记录单元和该第二记录单元中记录的信息。

[0276] 一种可能的实施方式中，上述处理单元1001基于该流信息确定该第一流映射的第一记录 单元，包括：通过多个哈希函数将该流信息映射到位图中的多个比特位；该位图中的一个比 特位与一个该第一记录单元关联；该网络设备基于该多个比特位确定该第一流映射的该第一 记录单元。

[0277] 一种可能的实施方式中，该第一记录单元中还包括流数目和流信息的异或结果，该流数 目为该目标流的数量，该流信息的异或结果为该目标流的流信息做异或操作后得到的结果。

[0278] 图10所示装置1000中各个单元的具体操作以及有益效果可以参见上述图3及其可能的 方法实施例中对应的描述，此处不再赘述。

[0279] 在采用对应各个功能划分各个功能模块的情况下，图11示出了装置的一种可能的逻辑结 构示意图，该装置可以是上述方法实施例中所述的第一网络设备，或者可以是该第一网络设 备中的芯片，或者可以是该第一网络设备中的处理系统等。该装置1100包括处理单元1101 和接收单元1102。其中：

[0280] 处理单元1101，用于：

[0281] 从通过接收单元1102接收的第一数据包中获取流信息，该流信息为该第一数据包所属的 第一流的标识信息；该处理单元1001可以用于实现上述图3中步骤301中获取流信息的操作；

[0282] 基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包 数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备 接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该处理单元1001可以用于实现上述图3中步骤302中确定第一流映射的第一记录单元的操作；

[0283] 更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将 该第一时延更新为该第一数据包经过该目标设备的时延；该处理单元1001可以用于实现上述 图3中步骤303中更新的操作；

[0284] 在该包数目大于或等于阈值的情况下，为该第一记录单元分配一个第二记录单元；该第 二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网 络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大于1的整数； 该n个时延用于估计该第一流经过上述目标设备的尾时延。

[0285] 在采用对应各个功能划分各个功能模块的情况下，图12示出了装置的一种可能的逻辑结 构示意图，该装置可以是上述方法实施例中所述的控制器，或者可以是该控制器中的芯片， 或者可以是该控制器中的处理系统等。该装置1200包括接收单元1201和处理单元1202。其 中：

[0286] 接收单元1201，用于接收多个第一记录单元中记录的信息，每个该第一记录单元中记录 的信息包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延， 该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录 单元的流，该目标流包括第一流；

[0287] 处理单元1202，用于在该包数目小于阈值的情况下，基于该多个第一记录单元中记录该 第一时延估计该第一流经过上述目标设备的尾时延。

[0288] 可选的，该目标设备为该网络设备；或者，该网络设备为网络中数据平面上的设备，该 网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数 据平面中经过的多个设备。

[0289] 一种可能的实施方式中，上述接收单元1201，还用于接收估计窗口的标识符，该标识符 指示该多个第一记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该 第一流经过上述目标设备的尾时延的时间窗口；

[0290] 上述处理单元1202基于该多个第一记录单元中记录该第一时延估计该第一流经过上述 目标设备的尾时延，包括：确定第一单元中记录的该第一时延为该第一流在该估计窗口内经 过目标设备的尾时延估计值；该第一单元为该多个第一记录单元中记录的该第一时延最小的 单元。

[0291] 在采用对应各个功能划分各个功能模块的情况下，图13示出了装置的一种可能的逻辑结 构示意图，该装置可以是上述方法实施例中所述的控制器，或者可以是该控制器中的芯片， 或者可以是该控制器中的处理系统等。该装置1300包括接收单元1301和处理单元1302。其 中：

[0292] 接收单元1301，用于接收第一记录单元和第二记录单元中记录的信息，该第一记录单元 中记录的信息包括第一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最 大时延，该包数目为该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第 一记录单元关联，该第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包 经过该目标设备的时延，该n为大于1的整数；

[0293] 处理单元1302，用于基于该n个时延估计该第一流经过上述目标设备的尾时延。

[0294] 一种可能的实施方式中，上述接收单元1301，还用于接收估计窗口的标识符，该标识符 指示该第一记录单元和该第二记录单元中记录的信息是在该估计窗口内记录的，该估计窗口 为用于估计该第一流经过上述目标设备的尾时延的时间窗口；

[0295] 该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80％且小于100％；上 述处理单元1302基于该n个时延估计该第一流经过上述目标设备的尾时延，包括：

[0296] 将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估 计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小 于或等于n的整数。

[0297] 图14所示为本申请实施例的装置的一种可能的硬件结构示意图，该装置可以是上述实施 例所述的第一网络设备，或者可以是第一网络设备中的芯片，或者可以是第一网络设备中的 处理系统等。该装置1400包括：处理器1401、存储器1402和通信接口1403。处理器1401、 通信接口1403以及存储器1402可以相互连接或者通过总线1404相互连接。

[0298] 示例性的，存储器1402用于存储装置1400的计算机程序和数据，存储器1402可以包括 但不限于是随机存储记忆体(random access memory，RAM)、只读存储器(read‑only memory， ROM)、可擦除可编程只读存储器(erasable programmable read only memory，EPROM)或 便携式只读存储器(compact disc read‑only memory，CD‑ROM)等。

[0299] 通信接口1403包括发送接口和接收接口，通信接口1403的个数可以为多个，用于支持 装置1400进行通信，例如接收或发送数据或消息等。

[0300] 示例性的，处理器1401可以是中央处理器单元、通用处理器、数字信号处理器、专用集 成电路、现场可编程门阵列或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任 意组合。处理器也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，数字信 号处理器和微处理器的组合等等。处理器1401可以用于读取上述存储器1402中存储的程序， 使得装置1400执行如上述图3及其可能的实施例中所述的任一种通信时延估计方法中第一网 络设备所做的操作。

[0301] 一种可能的实施方式中，处理器1401可以用于执行如下操作：从接收的第一数据包中获 取流信息，该流信息为该第一数据包所属的第一流的标识信息；基于该流信息确定该第一流 映射的第一记录单元；该第一记录单元中包括第一时延和包数目，该第一时延为目标流的单 个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个 数；该目标流包括映射到该第一记录单元的流；更新该包数目，并在该第一数据包经过该目 标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备 的时延；在该包数目小于阈值的情况下，该第一时延用于估计该第一流经过上述目标设备的 尾时延。

[0302] 图14所示装置1400中各个单元的具体操作以及有益效果可以参见上述图3及其可能的 方法实施例中对应的描述，此处不再赘述。

[0303] 图15所示为本申请实施例的装置的一种可能的硬件结构示意图，该装置可以是上述实施 例所述的第一网络设备，或者可以是第一网络设备中的芯片，或者可以是第一网络设备中的 处理系统等。该装置1500包括：处理器1501、存储器1502和通信接口1503。处理器1501、 通信接口1503以及存储器1502可以相互连接或者通过总线1504相互连接。

[0304] 示例性的，存储器1502用于存储装置1500的计算机程序和数据，存储器1502可以包括 但不限于是随机存储记忆体(random access memory，RAM)、只读存储器(read‑only memory， ROM)、可擦除可编程只读存储器(erasable programmable read only memory，EPROM)或 便携式只读存储器(compact disc read‑only memory，CD‑ROM)等。

[0305] 通信接口1503包括发送接口和接收接口，通信接口1503的个数可以为多个，用于支持 装置1500进行通信，例如接收或发送数据或消息等。

[0306] 示例性的，处理器1501可以是中央处理器单元、通用处理器、数字信号处理器、专用集 成电路、现场可编程门阵列或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任 意组合。处理器也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，数字信 号处理器和微处理器的组合等等。处理器1501可以用于读取上述存储器1502中存储的程序， 使得装置1500执行如上述图3及其可能的实施例中所述的任一种通信时延估计方法中第一网 络设备所做的操作。

[0307] 一种可能的实施方式中，处理器1501可以用于执行如下操作：从接收的该第一数据包中 获取流信息，该流信息用于指示该第一数据包为第一流中的数据包；基于该流信息确定该第 一流映射的第一记录单元；该第一记录单元用于记录第一时延和包数目，该第一时延为目标 流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据 包的个数；该目标流包括映射到该第一记录单元的流；更新该包数目，并在该第一数据包经 过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目 标设备的时延；在该包数目大于或等于阈值的情况下，为该第一记录单元分配一个第二记录 单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数 据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大 于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。

[0308] 图15所示装置1500中各个单元的具体操作以及有益效果可以参见上述图3及其可能的 方法实施例中对应的描述，此处不再赘述。

[0309] 图16所示为本申请实施例的装置的一种可能的硬件结构示意图，该装置可以是上述实施 例所述的控制器，或者可以是控制器中的芯片，或者可以是控制器中的处理系统等。该装置 1600包括：处理器1601、存储器1602和通信接口1603。处理器1601、通信接口1603以及 存储器1602可以相互连接或者通过总线1604相互连接。

[0310] 示例性的，存储器1602用于存储装置1600的计算机程序和数据，存储器1602可以包括 但不限于是随机存储记忆体(random access memory，RAM)、只读存储器(read‑only memory， ROM)、可擦除可编程只读存储器(erasable programmable read only memory，EPROM)或 便携式只读存储器(compact disc read‑only memory，CD‑ROM)等。

[0311] 通信接口1603包括发送接口和接收接口，通信接口1603的个数可以为多个，用于支持 装置1600进行通信，例如接收或发送数据或消息等。

[0312] 示例性的，处理器1601可以是中央处理器单元、通用处理器、数字信号处理器、专用集 成电路、现场可编程门阵列或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任 意组合。处理器也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，数字信 号处理器和微处理器的组合等等。处理器1601可以用于读取上述存储器1602中存储的程序， 使得装置1600执行如上述图3及其可能的实施例中所述的任一种通信时延估计方法中控制器 所做的操作。

[0313] 一种可能的实施方式中，处理器1601可以用于执行如下操作：接收多个第一记录单元中 记录的信息，每个该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为目标 流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据 包的个数；该目标流包括映射到该第一记录单元的流，该目标流包括第一流；在该包数目小 于阈值的情况下，基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设 备的尾时延。

[0314] 图16所示装置1600中各个单元的具体操作以及有益效果可以参见上述图3及其可能的 方法实施例中对应的描述，此处不再赘述。

[0315] 图17所示为本申请实施例的装置的一种可能的硬件结构示意图，该装置可以是上述实施 例所述的控制器，或者可以是控制器中的芯片，或者可以是控制器中的处理系统等。该装置 1700包括：处理器1701、存储器1702和通信接口1703。处理器1701、通信接口1703以及 存储器1702可以相互连接或者通过总线1704相互连接。

[0316] 示例性的，存储器1702用于存储装置1700的计算机程序和数据，存储器1702可以包括 但不限于是随机存储记忆体(random access memory，RAM)、只读存储器(read‑only memory， ROM)、可擦除可编程只读存储器(erasable programmable read only memory，EPROM)或 便携式只读存储器(compact disc read‑only memory，CD‑ROM)等。

[0317] 通信接口1703包括发送接口和接收接口，通信接口1703的个数可以为多个，用于支持 装置1700进行通信，例如接收或发送数据或消息等。

[0318] 示例性的，处理器1701可以是中央处理器单元、通用处理器、数字信号处理器、专用集 成电路、现场可编程门阵列或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任 意组合。处理器也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，数字信 号处理器和微处理器的组合等等。处理器1701可以用于读取上述存储器1702中存储的程序， 使得装置1700执行如上述图3及其可能的实施例中所述的任一种通信时延估计方法中控制器 所做的操作。

[0319] 一种可能的实施方式中，处理器1701可以用于执行如下操作：接收第一记录单元和第二 记录单元中记录的信息，该第一记录单元中记录的信息包括第一时延和包数目，该第一时延 为第一流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该第一流 的数据包的个数；该第二记录单元与该第一记录单元关联，该第二记录单元中记录的信息包 括该第一流中的n个数据包中每个数据包经过该目标设备的时延，该n为大于1的整数；基 于该n个时延估计该第一流经过上述目标设备的尾时延。

[0320] 图17所示装置1700中各个单元的具体操作以及有益效果可以参见上述图3及其可能的 方法实施例中对应的描述，此处不再赘述。

[0321] 本申请实施例还提供一种计算机可读存储介质，该计算机可读存储介质存储有计算机程 序，该计算机程序被处理器执行以实现上述图3及其可能的方法实施例中任一实施例所述方 法中第一网络设备所做的操作。

[0322] 本申请实施例还提供一种计算机可读存储介质，该计算机可读存储介质存储有计算机程 序，该计算机程序被处理器执行以实现上述图3及其可能的方法实施例中任一实施例所述方 法中控制器所做的操作。

[0323] 本申请实施例还提供一种计算机程序产品，当该计算机程序产品被计算机读取并执行时， 上述图3及其可能的方法实施例中任一实施例所述方法中第一网络设备所做的操作将被执行。

[0324] 本申请实施例还提供一种计算机程序产品，当该计算机程序产品被计算机读取并执行时， 上述图3及其可能的方法实施例中任一实施例所述方法中控制器所做的操作将被执行。

[0325] 综上所述，本申请实施例能够在每个流的尾时延测量过程中降低网络设备的资源开销， 从而使得网络设备基于现有的存储和处理资源可以对经过该网络设备的全部流的尾时延进行 测量和估计。

[0326] 本申请中术语“第一”“第二”等字样用于对作用和功能基本相同的相同项或相似项进 行区分，应理解，“第一”、“第二”、“第n”之间不具有逻辑或时序上的依赖关系，也 不对数量和执行顺序进行限定。还应理解，尽管以下描述使用术语第一、第二等来描述各种 元素，但这些元素不应受术语的限制。这些术语只是用于将一元素与另一元素区别分开。例 如，在不脱离各种所述示例的范围的情况下，第一时延可以被称为第二时延，并且类似地， 第二时延可以被称为第一时延。第一时延和第二时延都可以是时延，并且在某些情况下，可 以是单独且不同的时延。

[0327] 还应理解，在本申请实施例的各个实施例中，各个过程的序号的大小并不意味着执行顺 序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本申请实施例的实施过 程构成任何限定。

[0328] 还应理解，术语“包括”(也称“includes”、“including”、“comprises”和/或“comprising”) 当在本说明书中使用时指定存在所陈述的特征、整数、步骤、操作、元素、和/或部件，但是 并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元素、部件、和/或其分组。

[0329] 还应理解，说明书通篇中提到的“一个实施例”、“一实施例”、“一种可能的实现方 式”意味着与实施例或实现方式有关的特定特征、结构或特性包括在本申请实施例的至少一 个实施例中。因此，在整个说明书各处出现的“在一个实施例中”或“在一实施例中”、“一 种可能的实现方式”未必一定指相同的实施例。此外，这些特定的特征、结构或特性可以任 意适合的方式结合在一个或多个实施例中。

[0330] 最后应说明的是：以上各实施例仅用以说明本申请的技术方案，而非对其限制；尽管参 照前述各实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以 对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替 换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的范围。