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

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

背景技术：

2.网络性能检测一直是网络测量这一极具应用价值的网络领域中的重要子议题。其中，针对时延的测量一直是学术界研究的热点，也是工业界不断追求革新的领域。利用采样或发送探针来测量端到端时延的传统工具(如因特网包探索器ping，路由跟踪traceroute)等得到了大量的部署和应用，在很长一段时间里起到了很大的作用。当前，随着网络规模的迅速扩大和网络设备能力的不断提高，用户和产品对于网络运维提出了更加精细的要求。网络管理者希望提高网络的快速检测和定位异常的能力，比如快速发现分布式拒绝服务攻击(distributeddenial of service，ddos)攻击，或是能够检测出数据中心中潜在的微突发(micro-burst)等。而这些更具挑战性的问题，依赖于对于流性能指标更加细粒度的测量，例如流的尾时延的测量。
3.当前业界常用的流的尾时延的测量技术主要可以分为两类：一类是以网络流netflow为代表的网内测量技术，此类技术支持在网络设备中筛选、采样和拷贝相关的报文数据，然后将报文数据上传到控制器进行尾时延测量；另一类是以带内网络遥测(inband network telemetry， int)技术为代表的带内操作管理维护(in-situ operation administration and maintenance，ioam) 技术。此类技术将所需要的操作管理维护(oam)信息(例如时延的测量数据)直接封装在数据包中，在监测域的最后一跳，即边缘节点将oam数据移除转发给控制器进行尾时延测量。但是，netflow技术，支持由网络设备获取数据包的相关信息发送给控制器，但会带来较大的额外负载和资源消耗，使得实际使用中经常需要进行采样或是选流，难以覆盖经过网络设备的全部流的尾时延测量；以int为代表的ioam技术，将所需的信息携带在数据包头部，在最后一跳将收集信息上传控制器，减少了上传的成本，但也因此占用了链路带宽，造成流完成时间增加，吞吐下降等现象，因此往往也不能逐包部署，这也导致了难以实现所有流的尾时延测量。
4.综上所述，如何在每个流的尾时延测量过程中降低网络设备的资源开销是本领域技术人员急需解决的技术问题。

技术实现要素：

5.本技术实施例提供了一种通信时延估计方法及相关装置，能够在每个流的尾时延测量过程中降低网络设备的资源开销，从而使得网络设备基于现有的存储和处理资源可以对经过该网络设备的全部流的尾时延进行测量和估计。
6.第一方面，本技术提供一种通信时延估计方法，该方法包括：网络设备从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息；该网络设备基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包
数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该网络设备更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该第一时延用于估计该第一流经过上述目标设备的尾时延。
7.可选的，上述目标设备为上述网络设备；或者，该网络设备为网络中数据平面上的设备，该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备。
8.在本技术实施例中，上述网络设备为数据平面内用于转发数据的任意网络设备，通过在网络设备中，为网络设备接收到的每个流配置上述第一记录单元用于记录该每个流中的数据包经过上述目标设备的最大时延，以用于在该每个流的包数目小于阈值的情况下估计该每个流经过该目标设备的尾时延。由于本技术实施例中，将每个流映射到对应的第一记录单元中，该第一记录单元中只记录流中数据包经过该目标设备的最大时延，而不是记录所有数据包的时延，从而节省了存储资源，相比于现有的netflow和int的技术方案，本技术实施例无需将大量的数据包或者大量的测量数据发送给控制器，从而可以节省额外的链路带宽资源。另外，由于在本技术实施例中，节省了单个流的尾时延测量和估计所需的资源，从而可以在流的尾时延测量时无需进行对流进行筛选和采样，即相比现有的方案，本技术可以基于网络设备现有的存储和处理资源对经过该网络设备的全部流的尾时延进行测量和估计。
9.一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的时延；该第一数据包中包括该第一数据包经过其它设备的时延，该其它设备为该多个设备中除了该网络设备之外的其它网络设备。
10.在本技术实施例中，可以在数据平面中该第一流经过的所有网络设备上都部署时延获取模块，用于获取该第一流的每个数据包经过每个网络设备的时延，然后将这些时延携带在数据包中发送给上述最后一跳的设备，该最后一跳设备也获取该每个数据包经过自身的时延，然后统计该每个数据包经过该所有网络设备的总的时延，取最大的时延记录到上述第一记录单元中。这种实现方式可以使得只需要在该最后一跳设备进行时延等信息的记录和处理，无需该第一流经过的每个网络设备都有记录，从而可以节省网络设备的存储和处理资源。
11.一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的时延；该第一数据包中包括该第一数据包在该数据平面中经过的第一跳设备的入口的时间戳，该时间戳用于计算该第一数据包经过该多个设备的时延。
12.在本技术实施例中，可以在数据平面中该第一流经过的第一条设备上获取流的数据包的入口时间戳，并将该时间戳携带在数据包中发送到上述最后一跳设备，该最后一跳设备接收到该数据包后，可以获取该数据包从自身发出的时间戳，后面的时间戳减去前面
的时间戳即为该数据包经过上述目标设备的时延，然后取流中经过上述目标设备的最大时延记录到上述第一记录单元中。同理，这种实现方式可以使得只需要在该最后一跳设备进行时延等信息的记录和处理，无需该第一流经过的每个网络设备都有记录，从而可以节省网络设备的存储和处理资源。
13.一种可能的实施方式中，上述网络设备接收到的该目标流的数据包为该网络设备在估计窗口内接收的数据包，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；该第一时延为目标流的单个数据包经过目标设备的最大时延，包括：该第一时延为该目标流的单个数据包在该时间窗口内经过该目标设备的最大时延；该第一流经过上述目标设备的尾时延为该第一流在该时间窗口内经过目标设备的尾时延。
14.在本技术实施例中，通过将流的传输过程切分成一个或多个时间窗口，在每个时间窗口内进行流的尾时延的估计，可以提高网络设备的可实施性和可操作性。
15.一种可能的实施方式中，该第一流映射的该第一记录单元为多个；该方法还包括：在该估计窗口结束后，该多个第一记录单元中的至少一个单元记录的该包数目小于该阈值的情况下，该网络设备确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备的尾时延估计值，并将该第一单元中记录的该第一时延发送给控制器；该第一单元为该多个第一记录单元中记录的该第一时延最小的单元。
16.在本技术实施例中，在估计窗口内网络设备接收到的上述目标流的数据包小于阈值的情况下，可以用上述多个第一记录单元中记录的最小的第一时延来估计该第一流经过上述目标设备的尾时延，实现简单，可操作性较强。这是因为在包数目较小的情况下，尾时延与该第一记录单元中记录的数据包经过目标设备的最大的时延差别较小，所以可以用该最大的时延来估计流的尾时延。
17.一种可能的实施方式中，上述第一流映射的该第一记录单元为多个；该方法还包括：在该估计窗口结束的情况下，该网络设备向控制器发送该多个第一记录单元中记录的信息。
18.在本技术实施例中，网络设备可以将上述第一记录单元记录的信息发送给控制器，由控制器来进行尾时延的估计计算，从而减轻网络设备的处理负担。
19.一种可能的实施方式中，在该第一记录单元中记录的该包数目大于或等于该阈值的情况下，该方法还包括：该网络设备为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。
20.在本技术实施例中，在包数目大于上述阈值的情况下，尾时延与上述第一记录单元中记录的数据包经过目标设备的最大的时延差别较大，所以需要另外记录时延来进行流的尾时延的估计，所以配置了上述第二记录单元，用于记录后续的接收到的流的部分数据包经过上述目标设备的时延，然后基于第二记录单元记录的时延信息估计流的尾时延，以提高估计的准确度。
21.一种可能的实施方式中，该方法还包括：该网络设备接收第二数据包，该第二数据包为该目标流的数据包；该网络设备根据轮询的方式获取该第二记录单元的n个时延中的第二时延；在该第二数据包经过该目标设备的时延大于该第二时延的情况下，该网络设备
将该第二记录单元中的该第二时延更新为该第二数据包经过该目标设备的时延。
22.在本技术实施例中，可以通过轮询的方式更新上述第二记录单元中的时延，以保证上述 n个时延为最大的n个时延。
23.一种可能的实施方式中，该方法还包括：该网络设备接收第三数据包，该第三数据包为该目标流的数据包，在该第三数据包之前，并在该第二数据包之后，该网络设备接收了m个该目标流的数据包，该m为大于1的整数；该网络设备在该第二记录单元的n个时延中随机获取第三时延；在该第三数据包经过该目标设备的时延小于该第三时延的情况下，该网络设备将该第二记录单元中的该第三时延更新为该第三数据包经过该目标设备的时延。
24.当在上述估计窗口内接收到的流的包数目非常多的情况下，用上述最大的n个时延来估计该流的尾时延也存在较大的误差。例如，假设该包数目达到10000个，上述n为10个，若该100个时延为最大的10个时延，在估计99％分位尾时延时，该10000个数据包经过上述目标设备的时延按从小到大排序的第9900个时延才是准确的99％分位尾时延，而该10个最大的时延中每个时延都与该第9900个时延相差较大，所以无法用该10个时延来估计该99％分位尾时延。因此，本技术实施例中，在更新上述第二记录单元的过程中，基于上述轮询的更新方式的基础上，每隔一定数目的数据包，就随机在第二记录单元中的n个时延中选择一个更新为较小的时延，从而使得该第二记录单元中记录的n个时延不再是最大的时延，而是按照一定的概率将尽可能多的其它分位的时延信息记录到第二记录单元中，从而减少尾时延的估计误差。
25.一种可能的实施方式中，该方法还包括：在该估计窗口结束的情况下，该网络设备基于该第二记录单元中的n个时延估计该第一流在该估计窗口内经过目标设备的尾时延。
26.可选的，该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80且小于100；该网络设备基于该第二记录单元中的n个时延估计该第一流经过上述目标设备的尾时延，包括：该网络设备将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小于或等于n的整数。
27.在本技术实施例中，基于上述更新上述第二记录单元中的方式，可以用该第二记录单元中的n个时延中的时延来估计上述p分位尾时延，可以通过计算上述n个时延中大于p分位尾时延的时延个数的数学期望来确定上述w。
28.一种可能的实施方式中，该方法还包括：在该估计窗口结束的情况下，该网络设备向控制器发送该第一记录单元和该第二记录单元中记录的信息。
29.在本技术实施例中，网络设备可以将上述第一记录单元和第二记录单元记录的信息发送给控制器，由控制器来进行尾时延的估计计算，从而减轻网络设备的处理负担。
30.一种可能的实施方式中，该网络设备基于该流信息确定该第一流映射的第一记录单元，包括：该网络设备通过多个哈希函数将该流信息映射到位图中的多个比特位；该位图中的一个比特位与一个该第一记录单元关联；该网络设备基于该多个比特位确定该第一流映射的该第一记录单元。
31.在本技术实施例中，通过哈希计算将流映射到对应的第一记录单元，计算简单，处理方便，还可以节省存储资源。
32.一种可能的实施方式中，该第一记录单元中还包括流数目和流信息的异或结果，该流数目为该目标流的数量，该流信息的异或结果为该目标流的流信息做异或操作后得到的结果。
33.在本技术实施例中，在第一记录单元中记录流数目和流信息的异或结果，可以用于标记出现哈希冲突的记录单元，并可以用于后续解码出哈希冲突的流信息。
34.第二方面，本技术提供一种通信时延估计方法，该方法包括：网络设备从接收的该第一数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数据包；该网络设备基于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；该网络设备更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目大于或等于阈值的情况下，该网络设备为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。
35.在本技术实施例中，基于上述更新上述第二记录单元中的方式，可以用该第二记录单元中的n个时延中的时延来估计上述p分位尾时延，可以通过计算上述n个时延中大于p分位尾时延的时延个数的数学期望来确定上述w。
36.第三方面，本技术提供一种通信时延估计方法，该方法包括：控制器接收多个第一记录单元中记录的信息，每个该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流，该目标流包括第一流；在该包数目小于阈值的情况下，该控制器基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设备的尾时延。
37.可选的，该目标设备为该网络设备；或者，该网络设备为网络中数据平面上的设备，该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备。
38.在本技术实施例中，可以在控制器上述进行尾时延的估计计算，在估计窗口内网络设备接收到的上述目标流的数据包小于阈值的情况下，可以用上述多个第一记录单元中记录的第一时延来估计该第一流经过上述目标设备的尾时延，实现简单，可操作性较强。这是因为在包数目较小的情况下，尾时延与该第一记录单元中记录的数据包经过目标设备的最大的时延差别较小，所以可以用该最大的时延来估计流的尾时延。
39.一种可能的实施方式中，该方法还包括：该控制器还接收估计窗口的标识符，该标识符指示该多个第一记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；该控制器基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设备的尾时延，包括：该控制器确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备的尾时延估计值；该第一单元为该多个第一记录单元中记录的该第一时延最小的单元。
40.在本技术实施例中，通过将流的传输过程切分成一个或多个时间窗口，在每个时间窗口内进行流的尾时延的估计，可以提高网络设备的可实施性和可操作性。并在此基础上，可以用上述多个第一记录单元中记录的最小的第一时延来估计该第一流经过上述目标设备的尾时延，这是因为若该多个第一记录单元中的第一时延出现了不同，那么说明有记录单元出现了哈希冲突，又只有大于记录的第一时延的时延才可以更新到第一记录单元中，因此，第一流映射的多个第一记录单元中最小的第一时延才是比较准确的第一流的尾时延估计，因此采用该最小的第一时延来估计第一流的尾时延，可以提高估计的准确度。
41.第四方面，本技术提供一种通信时延估计方法，该方法包括：控制器接收第一记录单元和第二记录单元中记录的信息，该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第一记录单元关联，该第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包经过该目标设备的时延，该n为大于1的整数；该控制器基于该n个时延估计该第一流经过上述目标设备的尾时延。
42.在本技术实施例中，对于在上述估计窗口中网络设备接收到的目标流的包数目大于阈值的情况下，也可以将记录的信息发送给控制器，在控制器上述进行尾时延的估计计算。
43.一种可能的实施方式中，该方法还包括：该控制器还接收估计窗口的标识符，该标识符指示该第一记录单元和该第二记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；
44.该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80％且小于100％；该控制器基于该n个时延估计该第一流经过上述目标设备的尾时延，包括：
45.该控制器将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小于或等于n的整数。
46.在本技术实施例中，可以用该第二记录单元中的n个时延中的时延来估计上述p分位尾时延，可以通过计算上述n个时延中大于p分位尾时延的时延个数的数学期望来确定上述w。
47.第五方面，本技术提供一种网络设备，该网络设备包括处理单元，用于：
48.从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息；
49.基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；
50.更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该第一时延用于估计该第一流经过上述目标设备的尾时延。
51.可选的，上述目标设备为上述网络设备；或者，该网络设备为网络中数据平面上的设备，该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数
据包在该数据平面中经过的多个设备。
52.一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的时延；该第一数据包中包括该第一数据包经过其它设备的时延，该其它设备为该多个设备中除了该网络设备之外的其它网络设备。
53.一种可能的实施方式中，上述网络设备为网络中数据平面上的设备，该网络设备为该目标流的数据包在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备；该第一数据包经过该目标设备的时延为该第一数据包经过该多个设备的时延；该第一数据包中包括该第一数据包在该数据平面中经过的第一跳设备的入口的时间戳，该时间戳用于计算该第一数据包经过该多个设备的时延。
54.一种可能的实施方式中，上述网络设备接收到的该目标流的数据包为该网络设备在估计窗口内接收的数据包，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；该第一时延为目标流的单个数据包经过目标设备的最大时延，包括：该第一时延为该目标流的单个数据包在该时间窗口内经过该目标设备的最大时延；该第一流经过上述目标设备的尾时延为该第一流在该时间窗口内经过目标设备的尾时延。
55.一种可能的实施方式中，该第一流映射的该第一记录单元为多个；上述处理单元还用于：在该估计窗口结束后，该多个第一记录单元中的至少一个单元记录的该包数目小于该阈值的情况下，确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备的尾时延估计值，并将该第一单元中记录的该第一时延发送给控制器；该第一单元为该多个第一记录单元中记录的该第一时延最小的单元。
56.一种可能的实施方式中，上述第一流映射的该第一记录单元为多个；该网络设备还包括发送单元，用于在该估计窗口结束的情况下，向控制器发送该多个第一记录单元中记录的信息。
57.一种可能的实施方式中，在该第一记录单元中记录的该包数目大于或等于该阈值的情况下，上述处理单元还用于：
58.为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。
59.一种可能的实施方式中，该网络设备还包括接收单元，用于接收第二数据包，该第二数据包为该目标流的数据包；
60.上述处理单元，还用于根据轮询的方式获取该第二记录单元的n个时延中的第二时延；在该第二数据包经过该目标设备的时延大于该第二时延的情况下，将该第二记录单元中的该第二时延更新为该第二数据包经过该目标设备的时延。
61.一种可能的实施方式中，上述接收单元，还用于接收第三数据包，该第三数据包为该目标流的数据包，在该第三数据包之前，并在该第二数据包之后，该接收单元接收了m个该目标流的数据包，该m为大于1的整数；
62.上述处理单元，还用于在该第二记录单元的n个时延中随机获取第三时延；在该第
三数据包经过该目标设备的时延小于该第三时延的情况下，将该第二记录单元中的该第三时延更新为该第三数据包经过该目标设备的时延。
63.一种可能的实施方式中，上述处理单元还用于：在该估计窗口结束的情况下，基于该第二记录单元中的n个时延估计该第一流在该估计窗口内经过目标设备的尾时延。
64.可选的，该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80且小于100；上述处理单元基于该第二记录单元中的n个时延估计该第一流经过上述目标设备的尾时延，包括：将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小于或等于n的整数。
65.一种可能的实施方式中，该网络设备还包括发送单元，用于在该估计窗口结束的情况下，向控制器发送该第一记录单元和该第二记录单元中记录的信息。
66.一种可能的实施方式中，上述处理单元基于该流信息确定该第一流映射的第一记录单元，包括：通过多个哈希函数将该流信息映射到位图中的多个比特位；该位图中的一个比特位与一个该第一记录单元关联；该网络设备基于该多个比特位确定该第一流映射的该第一记录单元。
67.一种可能的实施方式中，该第一记录单元中还包括流数目和流信息的异或结果，该流数目为该目标流的数量，该流信息的异或结果为该目标流的流信息做异或操作后得到的结果。
68.第六方面，本技术提供一种网络设备，该网络设备包括处理单元，用于：
69.从接收的该第一数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数据包；
70.基于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；
71.更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；
72.在该包数目大于或等于阈值的情况下，为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。
73.第七方面，本技术提供一种控制器，该控制器包括：
74.接收单元，用于接收多个第一记录单元中记录的信息，每个该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流，该目标流包括第一流；
75.处理单元，用于在该包数目小于阈值的情况下，基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设备的尾时延。
76.可选的，该目标设备为该网络设备；或者，该网络设备为网络中数据平面上的设
备，该网络设备为该目标流在该数据平面中的最后一跳设备，该目标设备包括该单个数据包在该数据平面中经过的多个设备。
77.一种可能的实施方式中，上述接收单元，还用于接收估计窗口的标识符，该标识符指示该多个第一记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；
78.上述处理单元基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设备的尾时延，包括：确定第一单元中记录的该第一时延为该第一流在该估计窗口内经过目标设备的尾时延估计值；该第一单元为该多个第一记录单元中记录的该第一时延最小的单元。
79.第八方面，本技术提供一种控制器，该控制器包括：
80.接收单元，用于接收第一记录单元和第二记录单元中记录的信息，该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第一记录单元关联，该第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包经过该目标设备的时延，该n为大于1的整数；
81.处理单元，用于基于该n个时延估计该第一流经过上述目标设备的尾时延。
82.一种可能的实施方式中，上述接收单元，还用于接收估计窗口的标识符，该标识符指示该第一记录单元和该第二记录单元中记录的信息是在该估计窗口内记录的，该估计窗口为用于估计该第一流经过上述目标设备的尾时延的时间窗口；
83.该第一流经过上述目标设备的尾时延为p分位尾时延，该p大于80％且小于100％；上述处理单元基于该n个时延估计该第一流经过上述目标设备的尾时延，包括：
84.将该n个时延中的第w个时延确定为该第一流在该估计窗口内经过目标设备的尾时延估计值，该第w个时延为从小到大排序的该n个时延中排序为w的时延，该w为大于0且小于或等于n的整数。
85.第九方面，本技术实施例提供一种网络设备，该网络设备可以包括：存储器以及与该存储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该网络设备执行上述第一方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该网络设备执行上述第一方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送接口和接收接口可以集成为一收发器。处理器用于支持网络设备执行上述第一方面所提供的通信方法中网络设备除发送以及接收以外的其他处理操作。
86.需要说明的是，本技术实施例中的发送接口和接收接口可以集成在一起，也可以通过耦合器耦合。所述存储器用于存储第一方面描述的通信时延估计方法的计算机程序，所述处理器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过耦合器耦合。
87.另外，本技术中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载后存储，本技术对于存储器中计算机程序的来源不进行具体限定。本技术实施例中的耦合是装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、单元或模块之间的信息交互。
88.一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使
得所述网络设备执行如下操作：
89.从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的标识信息；基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目小于阈值的情况下，该第一时延用于估计该第一流经过上述目标设备的尾时延。
90.第十方面，本技术实施例提供一种网络设备，该网络设备可以包括：存储器以及与该存储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该网络设备执行上述第二方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该网络设备执行上述第二方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送接口和接收接口可以集成为一收发器。处理器用于支持网络设备执行上述第二方面所提供的通信方法中网络设备除发送以及接收以外的其他处理操作。
91.需要说明的是，本技术实施例中的发送接口和接收接口可以集成在一起，也可以通过耦合器耦合。所述存储器用于存储第二方面描述的通信时延估计方法的计算机程序，所述处理器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过耦合器耦合。
92.另外，本技术中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载后存储，本技术对于存储器中计算机程序的来源不进行具体限定。本技术实施例中的耦合是装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、单元或模块之间的信息交互。
93.一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述网络设备执行如下操作：
94.从接收的该第一数据包中获取流信息，该流信息用于指示该第一数据包为第一流中的数据包；基于该流信息确定该第一流映射的第一记录单元；该第一记录单元用于记录第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流；更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延；在该包数目大于或等于阈值的情况下，为该第一记录单元分配一个第二记录单元；该第二记录单元用于记录n个数据包中每个数据包经过该目标设备的时延，该n个数据包为该网络设备在该第一数据包之后接收的该目标流的数据包中的部分数据包，该n为大于1的整数；该n个时延用于估计该第一流经过上述目标设备的尾时延。
95.第十一方面，本技术实施例提供一种控制器，该控制器可以包括：存储器以及与该存储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该控制器执行上述第三方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该控制器执行上述第三方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送接口和接收接口可以集成为一收发器。处理器用于支持控制器执行上述第
三方面所提供的通信方法中控制器除发送以及接收以外的其他处理操作。
96.需要说明的是，本技术实施例中的发送接口和接收接口可以集成在一起，也可以通过耦合器耦合。所述存储器用于存储第三方面描述的通信时延估计方法的计算机程序，所述处理器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过耦合器耦合。
97.另外，本技术中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载后存储，本技术对于存储器中计算机程序的来源不进行具体限定。本技术实施例中的耦合是装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、单元或模块之间的信息交互。
98.一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述控制器执行如下操作：
99.接收多个第一记录单元中记录的信息，每个该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为目标流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该目标流的数据包的个数；该目标流包括映射到该第一记录单元的流，该目标流包括第一流；在该包数目小于阈值的情况下，基于该多个第一记录单元中记录该第一时延估计该第一流经过上述目标设备的尾时延。
100.第十二方面，本技术实施例提供一种控制器，该控制器可以包括：存储器以及与该存储器耦合的处理器、发送接口、接收接口。其中，该发送接口用于支持该控制器执行上述第四方面所提供的通信时延估计方法中发送消息和/或数据包的步骤。该接收接口用于支持该控制器执行上述第四方面所提供的通信时延估计方法中接收消息和/或数据包的步骤。其中，发送接口和接收接口可以集成为一收发器。处理器用于支持控制器执行上述第四方面所提供的通信方法中控制器除发送以及接收以外的其他处理操作。
101.需要说明的是，本技术实施例中的发送接口和接收接口可以集成在一起，也可以通过耦合器耦合。所述存储器用于存储第四方面描述的通信时延估计方法的计算机程序，所述处理器用于执行所述存储器中存储的计算机程序。存储器和处理器可以集成在一起，也可以通过耦合器耦合。
102.另外，本技术中存储器中的计算机程序可以预先存储也可以使用该装置时从互联网下载后存储，本技术对于存储器中计算机程序的来源不进行具体限定。本技术实施例中的耦合是装置、单元或模块之间的间接耦合或连接，其可以是电性，机械或其它的形式，用于装置、单元或模块之间的信息交互。
103.一种可能的实施方式中，所述处理器用于执行所述存储器中存储的程序指令，使得所述控制器执行如下操作：
104.接收第一记录单元和第二记录单元中记录的信息，该第一记录单元中记录的信息包括第一时延和包数目，该第一时延为第一流的单个数据包经过目标设备的最大时延，该包数目为该网络设备接收到的该第一流的数据包的个数；该第二记录单元与该第一记录单元关联，该第二记录单元中记录的信息包括该第一流中的n个数据包中每个数据包经过该目标设备的时延，该n为大于1的整数；基于该n个时延估计该第一流经过上述目标设备的尾时延。
105.第十三方面，本技术实施例提供一种系统，该系统包括网络设备和控制器，该网络
设备为上述第五方面所述的网络设备，该控制器为上述第七方面或者第八方面所述的控制器；或者，该网络设备为上述第六方面所述的网络设备，该控制器为上述第八方面所述的控制器；或者，该网络设备为上述第九方面所述的网络设备，该控制器为上述第十一方面或者第十二方面所述的控制器；或者，该网络设备为上述第十方面所述的网络设备，该控制器为上述第十二方面所述的控制器。
106.第十四方面，本技术实施例一种计算机可读存储介质，该计算机可读存储介质存储有计算机程序，该计算机程序被处理器执行以实现上述第一方面任意一项所述的方法；或者，该计算机程序被处理器执行以实现上述第二方面任意一项所述的方法。
107.第十五方面，本技术实施例一种计算机可读存储介质，该计算机可读存储介质存储有计算机程序，该计算机程序被处理器执行以实现上述第三方面任意一项所述的方法；或者，该计算机程序被处理器执行以实现上述第四方面任意一项所述的方法。
108.第十六方面，本技术实施例一种计算机程序产品，当计算机程序产品在计算机上运行时，使得该计算机执行如上述第一方面任意一项所述的方法；或者，使得该计算机执行如上述第二方面任意一项所述的方法。
109.第十七方面，本技术实施例一种计算机程序产品，当计算机程序产品在计算机上运行时，使得该计算机执行如上述第三方面任意一项所述的方法；或者，使得该计算机执行如上述第四方面任意一项所述的方法。
110.可以理解地，上述提供的网络设备、控制器、系统、计算机存储介质以及计算机程序产品均用于执行第一方面至第四方面中任一项所提供的方法。因此，其所能达到的有益效果可参考对应方法中的有益效果，此处不再赘述。
附图说明
111.下面将对本技术实施例中所需要使用的附图作介绍。
112.图1和图2所示为本技术实施例中的一种系统架构示意图；
113.图3所示为本技术实施例提供的一种方法流程示意图；
114.图4和图5所示为一种数据包在传输过程中携带的信息的示意图；
115.图6所示为本技术实施提供的一种网络设备处理流程架构示意图；
116.图7所示为本技术实施例提供的一种网络中信息流走向示意图；
117.图8所示为本技术实施例提供的一种数据包包括的内容示意图；
118.图9所示为本技术实施例提供的仿真结果示意图；
119.图10至图13所示为本技术实施例提供的一种装置的逻辑结构示意图；
120.图14至图17所示为本技术实施例提供的一种装置的硬件结构示意图。
具体实施方式
121.下面结合附图对本技术的实施例进行描述。
122.首先介绍一下本技术实施例涉及的术语：
123.1、数据平面：数据平面指网络中的转发面，刻画的是网络内设备的转发芯片和转发存储的体系和能力，与拥有普适计算能力的控制平面相对应。
124.2、时延：本技术实施例中所使用的时延，是基于网络设备所提供的硬件时钟时间
戳所计算得到的数据包在网络内传输时间。实际部署方案中，可以是单跳时延(例如可以是由网络设备提供的数据包在设备内的处理时间)；或者，也可以是网络中端到端时延(例如从第一跳网络设备入口处到最后一跳网络设备出口处之间的时间)。
125.3、全量流：全量流指的是网络中的全部流，全量流时延指的是该全部流中每一条流的时延信息。
126.4、尾时延：一个流中p％的数据包的时延小于某一个时延，则该某一个时延称为p分位时延。在本技术中，在p％的取值在80％至100％之间时，该某一个时延称为尾时延，或者称为p分位尾时延。例如，一个流中95％的数据包的时延小于某一个时延，则该某一个时延称为95分位尾时延。
127.下面介绍本技术实施例的一种应用场景。
128.参见图1，图1所示为本技术实施例的一种应用场景的系统架构示意图。图1中可以看到，该系统架构包括控制平面110和数据平面120。该控制平面110中包括控制器111，该控制器111可以是软件定义网络(software defined network，sdn)控制器或者操作维护中心(operation and maintenance center，omc)等。控制器111可以部署在一个或多个服务器中，多个服务器可以组成服务器集。
129.数据平面120包括g个网络设备121，该g为大于1的整数。图1中所示的网络设备1 和网络设备g之间还可以包括多个网络设备，该多个网络设备之间可以按任意拓扑连接。网络设备121用于在数据平面中转发数据。网络设备121例如可以是交换机、路由器或者接入设备等转发设备，该接入设备可以是或者无线接入点等。
130.一种可能的实施方式中，参见图2，数据平面中的网络设备中的资源和处理能力较强，除了实现数据转发的逻辑之外，还可以实现自身的控制逻辑，因此，该用于实现自身控制逻辑的能力也可以称为设备控制面，该设备控制面也可以属于控制平面110中的能力。在本申请实施例中，设备控制面可以用于处理采集到的数据包的时延信息以估计对应流的尾时延。
131.需要说明的是，上述图1和图2所示系统架构仅为一个示例，本技术实施例适用的系统架构不限于上述描述的系统架构。
132.当前业界常用的流的尾时延的测量技术主要可以分为两类：一类是以网络流netflow为代表的网内测量技术，此类技术支持在网络设备中筛选、采样和拷贝相关的报文数据，然后将报文数据上传到控制器进行尾时延测量；另一类是以带内网络遥测(inband network telemetry， int)技术为代表的带内操作管理维护(in-situ operation administration and maintenance，ioam) 技术。通过对这些现有方案的分析，可以得出全量流时延测量任务的主要挑战为网络设备在数据平面的存储资源和逻辑能力不足，或者说现有的方案中进行全量流时延测量需要消耗较多的存储资源和处理资源，资源开销非常大。具体表现在：
133.一方面，当前网络的吞吐极大，如果在控制平面实现全量流时延测量任务，往往会带来庞大的额外带宽负载(拷贝)或导致覆盖率下降无法做到全量(采样/筛选)，而且当前网络中并发流数目极多，数据中心中往往同时存在100k-1m级的并发流，这就导致如果想要记录逐流的信息，以目前有限的数据平面存储能力，每个流所能利用的存储空间是极其有限的。
134.另一方面，网络设备的逻辑资源和支持的操作相较一般通用计算机较为有限，因此，尽管当前算法理论研究对于流模型分位估测已经有了较好的研究结论，如何应用和部署成为难题，因此导致已有方法要么对设备能力有较强假设，实际难以部署；要么舍弃精度，采用更粗粒度的估测；要么使用较多资源来实现已有算法的折衷版本，放弃了可拓展性，因而难以支持逐流时延测量。
135.因此本技术方案聚焦于在资源和能力有限的网络设备内，实现在数据平面低开销全量流尾时延高精度测量的目标，即聚焦于在流的尾时延测量过程中降低网络设备的资源开销。以下是具体实现的实施例。
136.参见图3，示出了本技术实施例提供的一种通信时延估计方法，该方法用于解决以上的技术问题。该方法可以应用于上述图1或图2所示的系统架构。该方法可以包括但不限于如下步骤：
137.301、第一网络设备从接收的第一数据包中获取流信息，该流信息为该第一数据包所属的第一流的流标识。
138.具体实施例中，该第一网络设备可以是上述图1或图2中数据平面120内的任意一个网络设备。该第一网络设备可以用于转发一个或多个流的数据包。
139.具体的，第一网络设备接收到一个数据包(为了便于描述，后续称为第一数据包)后，可以解析该第一数据包，获取该第一数据包中的流信息。示例性地，该流信息例如可以是四元组、五元组或者七元组等等。该四元组包括流的源网际互联协议(internet protocol，ip)地址、目的ip地址、源端口和目的端口；该五元组包括源ip地址、目的ip地址、协议号、源端口和目的端口；该七元组包括源ip地址、目的ip地址、协议号、源端口、目的端口、服务类型以及接口索引。第一网络设备获得上述第一数据包内的流信息后，可以获知该第一数据包所属的流(为了便于描述，后续将该流称为第一流)。
140.一种可能的实施方式中，第一网络设备可以对上述获得的流信息进行编码。示例性地，可以将流信息用一个符号或者数值表示，该符号或者数值可以在该第一网络设备内唯一标识该第一流。
141.302、该第一网络设备基于该流信息确定该第一流映射的第一记录单元；该第一记录单元中包括第一时延和包数目，该第一时延为映射到该第一记录单元中的流的单个数据包经过目标设备的最大时延，该包数目为该第一网络设备接收到的映射到该第一记录单元中的流的数据包的个数。
142.在具体实施例中，第一网络设备中包括数据结构位图(bitmap)，该位图包括多个比特位，在本技术实施例中，该位图可以用于判断一个流是否是新的流。具体的，第一网络设备获得一个流的流信息后，可以通过多个哈希函数分别对该流信息进行哈希计算得到多个哈希值，该多个哈希值对应位图中多个比特位的位置序号，因此，该多个哈希值可以将该流信息对应的流映射到该多个比特位中。该多个哈希函数可以是两个或两个以上的哈希函数。
143.位图中每个比特位的初始值可以为第一数值，在基于计算得到的多个哈希值将流映射到多个比特位后，可以将该多个比特位中的值设置为第二数值。例如，可选的，假设位图中每个比特位的初始值为0，在基于计算得到的多个哈希值将流映射到多个比特位后，可以将该多个比特位中的值置1。或者，可选的，假设位图中每个比特位的初始值为1，在基
于计算得到的多个哈希值将流映射到多个比特位后，可以将该多个比特位中的值置0。
144.基于上述逻辑，第一网络设备通过上述多个哈希函数分别对上述第一流的流信息进行哈希计算得到多个哈希值，基于该多个哈希值将该第一流映射到位图中的多个比特位中，若该多个比特位中至少有一个比特位中的数值为上述第一数值，则可以确定该第一流为一个新的流，那么上述第一数据包是第一网络设备接收到的第一个该第一流中的数据包。该新的流指的是还未映射到该位图中的流。若该多个比特位中每个比特位中的数值为上述第二数值，则表明该第一流不是新的流，那么上述第一数据包是第一网络设备再次接收到的该第一流中的数据包。
145.在本技术实施例中，上述位图中的每一个比特位都关联有一个第一记录单元，那么，一个比特位关联的第一记录单元也是映射到该比特位的流映射的单元。该第一记录单元可以用于记录包数目和第一时延。
146.上述包数目为该第一网络设备接收到的映射到该第一记录单元中的流的数据包的个数。可选的，对于某一个第一记录单元，若映射到该第一记录单元的流为一个，那么，该第一记录单元中的包数目为第一网络设备接收到的该一个流的数据包的个数。可选的，对于该某一个第一记录单元，若映射到该第一记录单元的流为多个，即出现了哈希冲突，那么，该第一记录单元中的包数目为第一网络设备接收到的该多个流的数据包的个数和。
147.上述第一时延为映射到该第一记录单元中的流的单个数据包经过目标设备的最大时延。
148.一种可能的实施方式中，该目标设备为上述第一网络设备。或者，另一种可能的实施方式中，上述第一网络设备为映射到上述第一记录单元中的流在上述数据平面中的最后一跳设备，该目标设备包括多个设备，该多个设备为映射到该第一记录单元的流中的单个数据包在该数据平面中经过的设备。
149.可选的，不管是对于上述目标设备为上述第一网络设备的情况，还是对于上述目标设备包括多个设备的情况，相较基本固定的链路时延，网络设备上的处理时延，尤其是在网络设备中等待处理的排队时延是造成时延波动的主要因素，因此在本技术实施例中，可以采用网络设备的处理时间作为时延，该处理时间为一个数据包从该网络设备接收至从该网络设备发出之间的时间，即该处理时间即为该数据包经过该网络设备的时延。对于上述目标设备为上述第一网络设备的情况，上述第一时延为上述单个数据包经过该第一网络设备的最大时延。对于上述目标设备包括多个设备的情况，上述第一时延为上述单个数据包经过该多个设备中每一个设备的时延的和的最大值。例如，假设该多个设备为设备1和设备2，设备2接收了上述第一流中的第一数据包和第二数据包，第一个数据包经过设备1和设备2的时延分别为 1毫秒和0.9毫秒，第二个数据包经过设备1和设备2的时延分别为1.1毫秒和1毫秒，那么，设备2中该第一流映射的第一记录单元中的第一时延为2.1毫秒。基于前述描述，上述数据包在上述数据平面中经过的所有网络设备对该数据包的处理时间的和，即为该数据包在该数据平面中整个传输过程的时延。关于如何获取时延，后面介绍，此处暂不详述。
150.或者，可选的，对于上述目标设备包括多个设备的情况，可以将数据包在数据平面中的传输路径上的传输时延作为数据包在该数据平面中整个传输过程的时延，该传输时延包括该传输路径中的链路时延和该传输路径中的多个设备中的处理时间造成的时延，
本技术中将该传输时延也称为经过该多个设备的时延，由于该多个设备为上述目标设备，那么，该传输时延即为经过目标设备的时延。即这种情况下，上述第一时延可以为上述映射到第一记录单元的流中单个数据包在该整个传输过程的时延的最大值。例如，假设上述第一网络设备接收了上述第一流中的第一数据包和第二数据包，第一个数据包在该整个传输过程的时延为2.5毫秒，第二个数据包在该整个传输过程的时延为2.8毫秒，那么，第一网络设备中该第一流映射的第一记录单元中的第一时延为2.8毫秒。该传输时延为入口网络设备接收到该数据包到出口网络设备发出该数据包之间的时延。该入口网络设备为在该数据平面中转发该数据包的第一跳设备，该出口网络设备为在该数据平面中转发该数据包的最后一跳设备。关于如何获取时延，后面介绍，此处暂不详述。
151.一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。该流数目为映射到该第一记录单元的流的数量，该流信息的异或结果为映射到该第一记录单元的流的流信息的异或结果。具体的，若该流数目为1，则该流信息的异或结果为该流信息本身，或者说，在映射到该第一记录单元的流的数量为一个时，该第一记录单元中记录流信息的异或结果的位置记录的是该流信息本身。若该流数目大于1，即有多个流映射到同一个第一记录单元，则该流信息的异或结果为该多个流信息做异或操作后得到的结果。在计算机中，所有的信息都是用0和1的组成的二进制数据来表示，因此，该流信息的异或的结果也是由0和1组成的二进制数据。
152.基于上述的描述，第一网络设备将上述第一流映射到位图中的多个比特位中，通过该多个比特位可以确定该第一流映射的多个第一记录单元。
153.上述通过将流映射到位图中，可以为第一网络设备节省存储资源和降低计算难度以节省计算资源。
154.303、该第一网络设备更新该包数目，并在该第一数据包经过该目标设备的时延大于该第一时延的情况下，将该第一时延更新为该第一数据包经过该目标设备的时延。
155.在具体实施例中，上述第一网络设备确定该第一流映射的多个第一记录单元后，可以适应性地更新该多个第一记录单元中的信息，下面分情况介绍。
156.第一种情况，该第一流是新的流，且该第一流映射的多个比特位中没有出现哈希冲突。这种情况下，该第一流映射的多个第一记录单元中还未记录有信息或者记录的信息为原始默认值，那么，上述第一网络设备可以将该多个第一记录单元中记录包数目的位置的值设置为 1。另外，对于该多个第一记录单元中的第一时延，第一网络设备可以获取上述第一数据包经过上述目标设备的时延，然后将该时延记录到该多个第一记录单元中记录第一时延的位置。
157.具体的，第一网络设备中可以部署一个时延获取模块，时延获取模块可以获取上述第一数据包经过上述目标设备的时延。
158.可选的，对于上述目标设备为上述第一网络设备的情况，该时延获取模块通过测量和计算可以获取得到第一数据包在该第一网络设备中的处理时间，该处理时间即为该第一数据包经过第一网络设备的时延。具体的，该第一网络设备可以测量第一数据包到达该第一网络设备的时间戳，并估计第一数据包从第一网络设备发出的时间戳，用后面的时间戳减去前面的时间戳得到一个时间量，该时间量即为第一数据包在该第一网络设备中的处理时间即时延。那么，第一网络设备将该计算得到的时延记录到上述多个第一记录单
元中记录第一时延的位置。
159.需要说明的是，该第一数据包从网络设备发出的时间戳是根据数据包发送队列的情况计算得到的一个时间戳，在本技术实施例中，该时延获取模块计算得到的时延允许存在可接受的误差，或者说，在本技术实施例中，可以将该时延获取模块计算得到的一个时延作为正确的单个数据包经过网络设备的时延。可选的，该时延获取模块可以估计精确到纳秒的时间，从而提高了时延的估计精度。
160.可选的，对于上述目标设备包括多个设备的情况，一种可能的实施方式中，可以采用网络设备的处理时间作为时延。那么，对于上述第一数据包，需要在数据平面中转发该第一数据包的网络设备上，都设置计算该第一数据包在网络设备中的处理时间的处理逻辑。
161.具体的，对于入口网络设备，计算得到该第一数据包经过该入口网络设备的时延后，将该时延添加到该第一数据包的包头中，随同第一数据包一起发送给下一跳网络设备。可选的，该包头可以是自定义添加的专门用于携带时延的包头。该下一跳网络设备接收到携带时延的该第一数据包后，按照前述逻辑同样地计算该第一数据包在自身中的处理时间即时延，然后将计算得到的时延与接收的第一数据包包头中的时延相加得到新的时延，并将该新的时延更新到第一数据包的包头中继续发给下一跳设备。直到该第一数据包到达该数据平面中的最后一跳设备即上述第一网络设备，该第一网络设备获取该第一数据包包头中的时延，并计算该第一数据包在自身中的时延，然后将该两个时延相加得到的总的时延，该总的时延即为该第一数据包经过上述多个设备的时延。获得该总的时延后，第一网络设备可以将该第一数据包中专门用于携带时延的包头去掉。示例性地，该在每一跳网络设备中将时延加到数据包中已有时延上并发送的操作可以采用前述介绍过的int技术来实现。然后，第一网络设备将该总的时延记录到上述多个第一记录单元中记录第一时延的位置。为了便于理解该实施方式，可以示例性地参见图4。
162.图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记录到上述多个第一记录单元中记录第一时延的位置。
163.需要说明的是，在本技术实施例中，虽然上述在不同网络设备中转发的第一数据包中携带的时延不同，但只要第一数据包中的负载(payload)不变，那么，该携带的时延信息不同数据包仍然称为第一数据包。
164.可选的，对于上述目标设备包括多个设备的情况，一种可能的实施方式中，可以采用数据包在数据平面中的传输路径上的传输时延作为数据包在该数据平面中整个传输过程的时延。那么，对于上述第一数据包，在数据平面中转发该第一数据包的入口网络设备上，该入口网络设备可以测量该第一数据包到达该入口网络设备的时间戳，然后，将该时
间戳添加到该第一数据包包头中，随该第一数据包一直转发到数据平面的出口网络设备即上述第一网络设备上。可选的，该包头可以是自定义添加的专门用于携带时间戳的包头。该第一网络设备可以获取该第一数据包中的时间戳，然后，估测该第一数据包从第一网络设备发出的时间戳，用后面的时间戳减去前面的时间戳得到一个时间量，该时间量即为该第一数据包经过上述目标设备的时延。获得该时间量后，第一网络设备可以将该第一数据包中专门用于携带时间戳的包头去掉。示例性地，该在入口网络设备中将时间戳添加到数据包中，并随数据包传输到出口网络设备的操作可以采用前述介绍过的int技术来实现。然后，第一网络设备将该时延记录到上述多个第一记录单元中记录第一时延的位置。这种实现方式中，需要数据平面内的网络设备的时钟同步，这样计算得到的时延才准确。为了便于理解该实施方式，可以示例性地参见图5。
165.图5示出了一个简单的数据平面中的网络设备的拓扑示意图，并示出了数据包在传输过程中携带的信息，假设上述第一数据包在该数据平面中的传输路径为：网络设备1-网络设备 2-网络设备5-网络设备6。则在网络设备1为上述入口网路设备，则网络设备1中发出的该第一数据包中，携带该第一数据包到达该网络设备1时的时间戳，即图5中所示的第一时间戳。然后，该携带第一时间戳的第一数据包经网络设备2和网络设备5发送到网络设备6，网络设备6估测该第一数据包从网络设备6发出的时间戳，用后面的时间戳减去前面的时间戳得到一个时间量，该时间量即为该第一数据包经过上述目标设备的时延。网络设备6将该时间量记录到上述多个第一记录单元中记录第一时延的位置。
166.一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。若该第一记录单元中包括流信息的异或结果，由于上述第一流映射的多个比特位中没有出现哈希冲突，因此，第一网络设备可以将该第一流的流信息保存到该第一流映射的第一记录单元中记录的流信息的异或结果的位置。若该第一记录单元中包括流数目，那么，第一网络设备可以将该第一流映射的第一记录单元中记录的流数目设置为1。
167.第二种情况，该第一流是新的流，且该第一流映射的多个比特位中至少有一个比特位出现哈希冲突。
168.这种情况下，对于该多个比特位中没有哈希冲突的比特位映射的第一记录单元，其中的包数目和第一时延的更新可以参考上述第一种情况中对应的描述，此处不再赘述。对于该出现哈希冲突的至少一个比特位映射的至少一个第一记录单元，第一网络设备可以将该至少一个第一记录单元中的包数目增加1个计数，即将增加1个计数后得到的包数目替换掉原来的包数目。对于该至少一个第一记录单元中的第一时延，第一网络设备可以根据上述第一种情况描述的方法获取上述第一数据包经过上述目标设备的时延，然后，将该获取的时延与该至少一个第一记录单元中每个单元记录的第一时延比较，如果该获取的时延大于该至少一个第一记录单元中最小的第一时延，将该至少一个第一记录单元中最小的第一时延替换为该获取的时延。
169.一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。
170.若该第一记录单元中包括流信息的异或结果，对于上述多个比特位中没有哈希冲突的比特位映射的第一记录单元，第一网络设备可以将该第一流的流信息保存到该第一记录单元中记录的流信息的异或结果的位置。对于上述出现哈希冲突的至少一个比特位
映射的至少一个第一记录单元，第一网络设备可以将该第一流的流信息和第一记录单元中，记录流信息的异或结果的位置中的信息(可以是一个流的信息，或者可以是多个流的流信息异或的结果)进行异或操作，得到异或结果，然后，将该计算得到的异或结果保存到该第一记录单元中记录的流信息的异或结果的位置中。
171.若该第一记录单元中包括流数目，那么，对于上述多个比特位中没有哈希冲突的比特位映射的第一记录单元，第一网络设备可以将该第一流映射的第一记录单元中记录的流数目设置为1。对于上述出现哈希冲突的至少一个比特位映射的至少一个第一记录单元，第一网络设备可以将该至少一个第一记录单元中的流数目增加1个计数，即将增加1个计数后得到的流数目替换掉原来的流数目。
172.第三种情况，该第一流不是新的流，且该第一流映射的多个比特位中没有出现哈希冲突。
173.这种情况下，表明上述第一数据包是第一网络设备再次接收到的该第一流中的数据包，该第一流映射的多个第一记录单元中记录了之前接收到的第一流的数据包的包数目和第一时延。第一网络设备可以将该第一流映射的第一记录单元中的包数目增加1个计数，即将增加 1个计数后得到的包数目替换掉原来的包数目。另外，对于该多个第一记录单元中的第一时延，第一网络设备可以获取上述第一数据包经过上述目标设备的时延，然后，将获取的时延和第一记录单元中记录的第一时延比较，若获取的时延大于该第一记录单元中记录的第一时延，则第一网络设备将该多个第一记录单元中的第一时延更新为该获取的时延。若获取的时延不大于该第一记录单元中记录的第一时延，则该多个第一记录单元中的第一时延保持不变。
174.一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。若该第一记录单元中包括流信息的异或结果，由于该第一流映射的多个比特位中没有出现哈希冲突，因此，该第一流映射的多个第一记录单元中记录流信息的异或结果的位置中仍然记录第一流的流信息，保持不变。若该第一记录单元中包括流数目，由于该第一流映射的多个比特位中没有出现哈希冲突，那么对应的多个第一记录单元中映射的流只有上述第一流，因此，该第一流映射的多个第一记录单元中记录的流数目保持为1。
175.第四种情况，该第一流不是新的流，且该第一流映射的多个比特位中至少有一个比特位出现哈希冲突。
176.这种情况下，对于该多个比特位中没有哈希冲突的比特位映射的第一记录单元，其中的包数目和第一时延的更新可以参考上述第三种情况中对应的描述，此处不再赘述。对于该出现哈希冲突的至少一个比特位映射的至少一个第一记录单元，其中的包数目和第一时延的更新可以参考上述第二种情况中对应的描述，此处不再赘述。
177.一种可能的实施方式中，上述第一记录单元还可以用于记录流信息的异或结果和流数目。由于上述第一流不是新流，因此，该第一流映射的多个第一记录单元中的流信息的异或结果和流数目保持不变，具体可以参见上述第三种情况中对应的描述。
178.一种可能的实施方式中，上述第一数据包为第一网络设备在预设的时间窗口内接收的数据包，该预设的时间窗口的大小可以是10毫秒-100毫秒之间的任意大小；这种情况下，第一网络设备是以该时间窗口为估计时长分段估计上述第一流的时延，那么，上述第一时延为在该时间窗口内，映射到第一记录单元中的流的单个数据包经过上述目标设备
的最大时延。
179.或者，另一种可能的实施方式中，上述第一数据包为第一网络设备接收到的该第一流中的任一个数据包，这种情况下，第一网络设备是以该第一流的整体传输时间为估计时长估计该第一流的时延，那么，上述第一时延为在映射到第一记录单元中的流的整体传输时间内，该流的单个数据包经过该目标设备的最大时延。
180.在本技术实施例中，上述预设的时间窗口或者上述流的整体传输时间可以统称为估计窗口，即该估计窗口即为用于估计流的时延的时间窗口。在本技术实施例中，目的是为了估计流的尾时延，那么，该估计窗口也可以说是用于估计流的尾时延的时间窗口。并且，上述第一记录单元中记录的信息也是在该估计窗口内估计得到的。
181.在本技术实施例中，对于上述第一流经过上述目标设备的尾时延的估计，包括两种不同的处理方式，可以通过判断第一网络设备在上述估计窗口内接收的第一流的数据包的个数是否大于阈值来确定具体的处理方式。具体的，上述第一网络设备更新第一流映射的多个第一记录单元之后，可以判断该多个第一记录单元中记录的包数目是否大于阈值，当然，该包数目对应的数据包是第一网络设备在该估计窗口内接收到的。该阈值例如可以是100、1000或者10000等等，可以根据希望的测量分位与希望的准确率等情况设定，本技术对此不做限制。
182.一种可能的实施方式中，如果上述多个第一记录单元中记录的包数目小于上述阈值，那么，若该估计窗口还未结束，则第一网络设备继续接收第一流的数据包，然后，更新第一流映射的多个第一记录单元中的信息，具体的更新可以参见上述步骤303中对应的描述。在该估计窗口结束之后，第一网络设备可以根据第一流的流信息的哈希值到该第一流映射的多个第一记录单元，第一网络设备获取该第一流映射的多个第一记录单元中记录的多个第一时延，然后，取该多个第一时延中的最小值作为该估计窗口内该第一流经过上述目标设备的尾时延的估计值。
183.上述这种处理方式中，由于在上述估计窗口内第一流的数据包个数小于上述阈值，则表明该数据包的个数相对较少，那么，在该估计窗口内第一流的80分位尾时延至100分位尾时延之间的尾时延相差较小，且该第一流映射的第一记录单元中记录的第一时延为估计窗口内单个数据包经过该目标设备的最大时延，因此，可以用第一流映射的第一记录单元中记录的第一时延，来估计该第一流在该估计窗口内的80分位尾时延至100分位尾时延之间的任一个尾时延，这种估计误差较小，在可接受的范围内。又因为可能存在哈希冲突，如果第一流映射的多个第一记录单元中存在哈希冲突的单元记录的第一时延，与没有哈希冲突的单元记录的第一时延不同，那么，基于上述取较大的时延替换较小的时延的原则，该存在哈希冲突的单元记录的第一时延不小于该没有哈希冲突的单元记录的第一时延，因此，选择该第一流映射的多个第一记录单元中最小的第一时延作为该估计窗口内该第一流经过上述目标设备的尾时延的估计值更准确。
184.一种可能的实施方式中，对于上述第一流映射的比特位中存在哈希冲突的比特位映射的至少一个第一记录单元，在上述估计窗口结束之后，第一网络设备在对第一记录单元中的信息解码的过程中，可以将该至少一个第一记录单元中的流信息的异或结果与第一流的流信息再进行一次异或操作，并将该异或操作的结果记录到该至少一个第一记录单元中，这样可以将第一流的流信息从该至少一个第一记录单元中删除。同时，第一网络
设备可以将该至少一个第一记录单元中的流数目减1，且包数目减去该估计窗口内接收到的第一流的数据包的个数，但是第一时延不做改动。通过这些处理，可以将第一流的相关信息从该至少一个第一记录单元中删除，对于有多个估计窗口的情况下，该至少一个第一记录单元可以准备用于记录下一个估计窗口内第一流的相关信息。
185.而对于上述第一流映射的比特位中不存在哈希冲突的比特位映射的第一记录单元，在上述估计窗口结束之后，第一网络设备可以将这些第一记录单元中记录的信息全部清除，对于有多个估计窗口的情况下，这些第一记录单元可以准备用于记录下一个估计窗口内第一流的相关信息。
186.一种可能的实施方式中，如果上述多个第一记录单元中记录的包数目大于或等于上述阈值，那么，在该包数目等于该阈值时，若该估计窗口还未结束，第一网络设备为该多个第一记录单元中每个单元配置一个关联的第二记录单元，第一记录单元和第二记录单元之间通过索引关联，第一网络设备可以配置多个索引记录单元用于专门记录第一记录单元和第二记录单元之间的索引信息，每个索引记录单元记录一个第一记录单元和一个第二记录单元之间的索引信息。该第二记录单元中可以记录n个时延，该n为大于1的整数。该n个时延为包数目等于上述阈值后第一网络设备接收的目标流中的n个数据包经过上述目标设备的时延。若第一网络设备接收上述第一数据包后，第一记录单元中记录的包数目刚好达到该阈值，那么，该n个数据包为第一网络设备在该第一数据包之后接收的该目标流的数据包中的n个数据包。该目标流即为上述映射到第一记录单元中的流，若映射到第一记录单元中的流只有上述第一流，则该目标流即为该第一流；若映射到第一记录单元中的流有包括上述第一流的多个流，则该目标流即为该多个流。
187.具体的，在配置上述第二记录单元时，该第二记录单元中可以默认配置n个时延的初始值，或者该第二记录单元中一开始为空。本技术实施例中，可以通过轮询的方式更新该第二记录单元中的n个时延。在上述第一记录单元中记录的包数目等于上述阈值之后，第一网络设备接收的目标流的前n个数据包对应的经过上述目标设备的时延，可以依次记录到该第二记录单元中记录n个时延的位置中。然后，在该n个数据包之后，第一网络设备每接收到目标流的一个数据包，可以通过轮询的方式确定第二记录单元中的一个时延，然后，在该时延小于该接收到的数据包经过上述目标设备的时延的情况下，用该接收到的数据包经过上述目标设备的时延替换掉该第二记录单元中的一个时延。
188.上述轮询的方式指的是从上述n个时延中的某一个时延开始，按预设顺序依次逐一查询各个时延，直到完成该n个时延的查询后，再次从该某一个时延开始，并按该预设顺序依次逐一查询各个时延，直到再次完成该n个时延的查询，循环执行该查询的操作。为了便于理解，下面举例说明。参见表1。
189.表1
190.时延的位置12345时延的值0.3毫秒0.35毫秒0.28毫秒0.32毫秒0.26毫秒
191.表1示例性示出了一个第二记录单元中记录的时延。假设该第二记录单元中可以记录5 个目标流的数据包经过上述目标设备的时延，对应位置上的时延参见上述表1。假设该表1 中记录的5个时延，是在上述第一记录单元中记录的包数目等于上述阈值之后，第一网络设备接收的第一流的前5个数据包经过上述目标设备的时延。另外，假设上述轮询的
方式是从位置1的时延开始依次查询到位置5的时延，然后，轮回查询位置1的时延，再依次查询到位置5的时延，如此循环。
192.基于表1，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第1个数据包，并获取了该第1个数据包经过上述目标设备的时延，为0.32毫秒。然后，第一网络设备基于该轮询的方式，首先查询第二记录单元中位置1中的时延，该时延为0.3毫秒。由于0.32毫秒大于0.3毫秒，那么，第一网络设备将该位置1中的时延0.3毫秒替换为0.32毫秒。经过一轮的操作之后，即第一网络设备在上述包数目等于上述阈值之后接收了5个第一流的数据包，并轮询更新了该第二记录单元之后，该第二记录单元中的5个时延参见表2。
193.表2
194.时延的位置12345时延的值0.32毫秒0.35毫秒0.3毫秒0.32毫秒0.28毫秒
195.基于表2，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第6个数据包，并获取了该第6个数据包经过上述目标设备的时延，为0.25毫秒。然后，第一网络设备基于该轮询的方式，查询第二记录单元中位置1中的时延，该时延为0.32毫秒。由于0.25毫秒小于0.32毫秒，那么，第一网络设备将该位置2中的时延0.32毫秒保持不变，即此次不更新该位置1中的时延。
196.可选的，因为后续是基于该第二记录单元中记录的n个时延来估计目标流在估计窗口内经过目标设备的尾时延，若目标流的包数目非常多，此时按照上述轮询的方式更新上述第二记录单元中的n个时延，那么，最后得到的该n个尾时延为最大的n个尾时延，这时该n个尾时延可以用于较准确地估计接近100分位尾时延，但是用于估计80分位尾时延、85分位尾时延、90分位尾时延或者95分位尾时延，甚至99分位尾时延等尾时延，其误差较大，估计出来的尾时延不准确。为了解决该问题，本技术实施例提供了如下操作：
197.在上述轮询的方式更新上述第二记录单元的基础上，在上述包数目等于上述阈值之后，第一网络设备每接收预设个数的目标流的数据包后，再次接收到目标流的一个数据包，可以在该第二记录单元中随机查询一个时延，然后，比较该数据包经过上述目标设备的时延与该查询到的一个时延的大小。在该数据包经过上述目标设备的时延小于该查询的一个时延时，用该数据包经过上述目标设备的时延替换该查询的一个时延记录在该第二记录单元中，否则不更新该查询的一个时延。
198.上述预设个数可以是10个、50个或者100个等等，本技术对预设个数的具体取值不做限制。为了便于理解，下面举例说明。
199.还是基于上述表1为例进一步描述，假设该预设个数为8个，那么，在上述包数目等于上述阈值之后，第一网络设备接收了8个目标流的数据包，并轮询更新了该第二记录单元之后，该第二记录单元中的5个时延参见表3。
200.表3
201.时延的位置12345时延的值0.32毫秒0.35毫秒0.31毫秒0.32毫秒0.28毫秒
202.基于表3，第一网络设备接收到了上述包数目等于上述阈值之后目标流的第9个数据包，并获取了该第9个数据包经过上述目标设备的时延，为0.27毫秒。然后，第一网络设备在该第二记录单元的5个位置的时延中随机查询一个时延，假设随机查询到了位置5的
时延0.28 毫秒。由于0.27毫秒小于0.28毫秒，那么，第一网络设备将该位置5中的时延0.28毫秒替换为0.27毫秒，具体的可以参见表4。
203.表4
204.时延的位置12345时延的值0.32毫秒0.35毫秒0.31毫秒0.32毫秒0.27毫秒
205.需要说明的是，由于存在哈希冲突，那么上述多个第一记录单元中，存在哈希冲突的比特位映射的单元的包数目大于没有哈希冲突的比特位映射的单元的包数目。对于该存在哈希冲突的比特位映射的单元，只要其包数目达到阈值后，也可以为该单元配置一个第二记录单元，然后，用该第二记录单元记录映射到该单元的多个流中，包数目大于上述阈值后第一网络设备接收的部分数据包经过上述目标设备的时延，之后更新第二记录单元的操作可以参见上述的描述，此处不再赘述。
206.基于上述对第二记录单元的更新方式，在上述估计窗口结束之后，第一网络设备基于该第一流映射的多个第一记录单元查到关联的第二记录单元，具体的，可以通过上述索引记录单元中记录的索引信息查到该第一记录单元关联的第二记录单元。然后，第一网络设备获取该第二记录单元中记录的n个时延，基于该n个时延估计第一流在该估计窗口内经过目标设备的尾时延。具体的，假设该n个时延从小到大排序，可以用该n个时延中排序为w的时延来估计该第一流在该估计窗口内的p分位尾时延，排序在该w之前的时延小于或等于该 p分位尾时延，该w为大于0且小于或等于n的整数。
207.一种可能的实施方式中，为了避免哈希冲突导致的数据错乱，可以选择流数目为1或者流数目最小的第一记录单元关联的第二记录单元中的n个时延来估计第一流在该估计窗口内经过目标设备的尾时延。
208.一种可能的实施方式中，假设上述估计窗口内第一网络设备接收到的第一流的数据包为 n个，该n为大于或等于n的整数。那么，上述w可以是n(1-1/n)
n(1-p)
，即可以用上述n 个时延中的排序为n(1-1/n)
n(1-p)
大的时延来估计该第一流在该估计窗口内的p分位尾时延，该第n(1-1/n)
n(1-p)
大的时延为该第一流中n个数据包对应的n个经过上述目标设备的时延中第n*p大的时延的估计值。具体的估计过程可以示例性地参见下面的计算公式：
[0209][0210]
其中，ak表示上述n个经过上述目标设备的时延中第k大的时延，aj表示上述n个时延中第 j大的时延，c表示第二记录单元中的n个时延的集合，ci表示第二记录单元中第i个位置记录的时延，p(ak∈c)表示ak被第二记录单元任一位置记录的概率，a
k meet ci表示ak在轮询中与第二记录单元中第i个位置记录的时延比较，∧表示“且”，ak＝max(aj|ajmeet ci)表示ak等于所有与该第i个位置记录的时延比较的时延中的最大值。公式计算ak被记录的概率。
[0211]
假设a
k meet ci的概率为1/n，即ak遇到c中的每个数的概率相同，实际在上述轮询的方式中遇到不同位置的时延的次数之间的差至多为1，因此，这里假设a
k meet ci的概率为1/n 的误差较小。基于该假设，那么：
[0212][0213]
则
[0214][0215]
则
[0216][0217]
其中，表示ci》a
n*p
表示上述第i个位置记录的时延大于p分位尾时延。e(num(ci》a
n*p
))表示上述n个时延中大于p分位尾时延的时延个数的数学期望，e(num(ci≤a
n*p
))表示该n个时延不大于p分位尾时延的时延个数的数学期望，即在理论上，p分位尾时延的期望为该n 个时延中第大的记录时延，因此w可以是n(1-1/n)
n(1-p)
。
[0218]
一种可能的实施方式中，对于第一流的包数目非常多的情况，上述记录第二记录单元中的n个时延时对应采用了每隔一定的包数目就随机用小的时延替换原来大的时延的方式，以降低最后的估计误差。那么，配套的尾时延估计处理方式可以参见如下描述：
[0219]
假设上述估计窗口内第一网络设备接收到的第一流的数据包为n个，该n为大于或等于 n的整数。那么，上述w可以是n(1-q/n)
n(1-p)
，即可以用上述n个时延中的排序为 n(1-q/n)
n(1-p)
大的时延来估计该第一流在该估计窗口内的p分位尾时延，该第n(1
‑ꢀ
q/n)
n(1-p)
大的时延为该第一流中n个数据包对应的n个经过上述目标设备的时延中第n*p 大的时延的估计值，该q为大于0且小于1的实数。具体的估计过程可以示例性地参见下面的计算公式：
[0220][0221]
其中相关字符表示的含义可以参见上述公式(1)中相关的描述，此处不再赘述。
[0222]
同理，假设a
k meet ci的概率为1/n，即ak遇到c中的每个数的概率相同，实际在上述轮询的方式中遇到不同位置的时延的次数之间的差至多为1，因此，这里假设a
k 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]
最后应说明的是：以上各实施例仅用以说明本技术的技术方案，而非对其限制；尽管参照前述各实施例对本技术进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征
进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本技术各实施例技术方案的范围。

技术特征：

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所述的控制器。

技术总结

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