数据流的路径签名的制作方法

数据流的路径签名
1.相关申请的交叉引用
2.本技术要求美国申请第16/661,540号的优先权，该美国申请递交于2019年10月23日并且其全部内容被通过引用并入在此。
技术领域
3.本公开概括而言涉及为通过网络的数据流生成路径签名以及基于路径签名来诊断网络的问题。


背景技术：

4.数据可以通过网络以单向数据流的形式被从源传输到目的地。数据流可包括多个数据封包，这些数据封包通过网络被从源传播到目的地。数据封包被从源传输的顺序可能是数据封包应当被目的地消费的顺序。例如，内容服务器可以按照与视频的进展相对应的顺序来传输视频流中的数据封包，从而，与视频的开头相对应的数据封包被首先传输，并且与视频的末尾相对应的数据封包被随后传输。
5.各种现代网络拓扑结构可包括各种节点，通过这些节点可以传输信息。网络中的个体节点可以与网络中的多于两个其他节点连接。由于节点的互连性，任何两个端点之间可能有多条路径通过网络。个体节点可以基于网络的各种条件来选择适当的路径。例如，节点可以基于负载平衡、连通性之类的在多条路径之间进行选择。
6.然而，如果同一数据流中的数据封包通过网络沿着不同路径被传输，则数据封包到达目的地的顺序可能与它们打算被消耗的顺序不同。例如，一个封包可能通过高时延的节点被传输，而另一个数据封包可能通过较低时延的节点被传输。无序(out-of-order，ooo)数据封包会对终端用户的服务质量(quality of service，qos)产生负面影响。为了避免数据流中的ooo数据封包，有必要识别特定数据流中的封包是否行经网络中的不同路径。
7.原位操作、施行和管理(in-situ operations,administration,and management，ioam)提供了一些机制，通过这些机制，通过网络传送数据封包的每个节点可以向数据封包添加元数据。在一些情况下，这种元数据可用于得出数据封包在网络中行经的路径。然而，ioam元数据可显著增大给定数据封包的大小。在通过网络的每一跳处，ioam元数据可能会向给定的数据封包添加大量的数据(例如，100字节)。在各种网络中，ioam元数据的大小可能是不可接受的，尤其是当数据封包在前往目的地的途中穿越大量节点时。例如，在各种网络中，节点可能缺乏支持ioam以及支持传送带有ioam元数据的数据封包所需要的硬件。ioam的一些替换方案，例如网络内遥测(in-network telemetry，int)、带内流分析器(inband flow analyzer，ifa)和原位流信息遥测(in-situ flow information telemetry，ifit)，也存在类似的缺陷。
附图说明
8.下面将参考附图记载详细描述。在附图中，标号的最左边的(一个或多个)数字指
示该标号首次出现的附图。在不同的附图中使用相同的标号来指示相似或相同的项目。附图中描绘的系统不是按比例的，并且附图中的组件相互之间可能不是按比例描绘的。
9.图1图示了一种示例环境，其中流的封包通过网络中的不同路径被传输。
10.图2图示了一种示例环境，其中流的第一封包通过网络中的第一路径被传输。
11.图3图示了一种示例环境，其中流的第二封包通过网络中的第二路径被传输。
12.图4a和图4b图示了节点转发带有路径签名的流的封包的示例环境。
13.图5a和图5b图示了节点转发带有经修订的路径签名的流的封包的示例环境。
14.图6a图示了流表的示例，其中带有与通过特定节点的不同流相对应的各种条目。
15.图6b图示了流表的示例，其中带有与流中的封包的不同路径签名相对应的各种条目，这些路径签名对应于该流的封包所采取的不同路径。
16.图7a图示了用于向数据封包添加路径签名的示例过程。
17.图7b图示了用于更新数据封包的路径签名的示例过程。
18.图8图示了用于基于带有不同路径签名的数据封包来发送警报的示例过程。
19.图9图示了用于基于路径变化来向中央管理员报告问题的示例过程。
20.图10示出了能够执行用于实现本文描述的功能的程序组件的计算机的示例计算机体系结构。
具体实施方式
21.概述
22.在独立权利要求中记载了本发明的各方面并且在从属权利要求中记载了优选特征。一个方面的特征可被单独应用到任何方面或者与其他方面组合应用。
23.本公开描述了用于为穿越网络的数据流生成和利用原位路径签名的各种技术。网络节点可以为正在穿越网络节点的数据流中的特定数据封包生成路径签名。路径签名可以表示该数据封包为了到达该网络节点已穿越的唯一路径。当网络节点识别出同一数据流中的不同数据封包具有不同的路径签名时，网络节点可以触发警报，表明数据流中的封包可能是无序的，并且/或者网络可能有问题，导致了无序的封包。网络节点可以是物理设备、服务器、交换机，等等。
24.在各种实现方式中，本文描述的技术可由具有存储计算机可执行指令的非暂态计算机可读介质的系统和/或设备执行，这些指令在被一个或多个处理器执行时，执行本文描述的方法。
25.示例实施例
26.本公开的各种实现方式涉及识别通过网络传送数据封包的路径。特定实现方式在数据封包中提供了路径签名数据字段，该字段可被数据封包被传送通过的个体节点修改。
27.在一些实现方式中，节点可以接收带有现有路径签名的数据封包。节点可以将现有路径签名以及基于节点本身的其他信息输入到散列函数中，该散列函数可以返回经修订的路径签名。节点可以在将数据封包转发到网络中的另一个节点之前，在数据封包中用经修订的路径签名替换现有路径签名。经修订的路径签名可以表示数据封包到该节点本身为止已穿越的唯一路径。
28.在特定情况下，节点或者某个其他设备可以跟踪与同一数据流中的数据封包相对
应的路径签名。如果节点识别出数据流中的路径签名的变化，则节点可以向收集器发送警报。收集器可以基于该警报和/或来自网络中的其他节点的与该数据流相对应的其他警报，来诊断网络中的问题。在一些情况下，路径签名可以作为现有netflow功能的一部分被跟踪。
29.与ioam元数据不同，路径签名数据字段可具有固定的大小，而不考虑数据封包被传送经过的节点的数目。例如，路径签名数据字段可限于32比特或者64比特。因为路径签名可具有相对较小的大小，所以路径签名可以很容易地在现有的网络节点硬件中实现。
30.本文描述的各种实现方式为计算机联网领域提供了特定的改进。随着数据流被通过网络传输，路径签名可以为个体数据流实现原位网络路径跟踪。因此，网络内的问题可以被高效地实时诊断出来。
31.将参考附图详细描述本公开的各种实现方式，附图中相似的标号在几个视图中表示相似的部件和组件。此外，本说明书中记载的任何样本并不打算是限制性的，而只是记载了许多可能的实现方式中的一些。
32.图1图示了一种示例环境100，其中流的封包通过不同路径被传输。在图1中，用实线箭头来描绘数据平面传输，并且用虚线箭头来描绘控制平面传输。
33.如图1中所示，源102可以经由网络106向目的地104发送数据。源102和目的地104可以各自是节点的示例。就本文使用的而言，术语“节点”、“网络节点”和它们的等同物，可以指网络内的任何如下实体：该实体可以向至少一个其他节点发送封包和/或从至少一个其他节点接收封包。节点可以是设备、软件实例、虚拟机(virtual machine，vm)之类的。在一些示例中，节点可以是客户端、服务器或者其组合。在一些情况下，节点可以是流的端点，例如源102或目的地104。源102可以是例如内容服务器。目的地104例如可以是用户设备(user equipment，ue)。
34.源102可以在包括有序封包108的流中发送数据。就本文使用的而言，术语“流”、“数据流”、“流量流”、“封包流”以及它们的等同物，可以指从源发送到目的地的多个封包。在一些示例中，流可包括共享以下各项中的至少一项的封包：相同入口接口(例如，snmp ifindex)、源(例如，来自相同的ip地址)、目的地(例如，指向相同的ip地址)、协议(例如，ip协议)、源端口(例如，对于udp或者tcp)、目的地端口(例如，对于udp、tcp或icmp)、或者服务类型(例如，ip服务类型(type of service，tos))。就本文使用的而言，术语“封包”、“数据封包”及其等同物可以指在两个节点之间传输的数据的单元。在各种示例中，封包可具有头部和有效载荷，该头部可包括控制数据，该有效载荷可包括用户数据。头部可包括信息，例如封包的源的标识符、封包的目的地的标识符、有效载荷中的用户数据类型的指示，等等。在一些情况下，封包可以由特定的联网协议来定义，例如ip、tcp、udp或者其他联网协议。
35.就本文使用的而言，术语“端口”及其等同物可以指节点的组件，该组件被配置为将节点的其余部分连接到接口。节点可具有固定的一组端口，这些端口可以选择地连接到特定的接口。节点的每个端口可具有唯一的身份，这可以用端口号来表示。就本文使用的而言，术语“入口端口”、“进入端口”及其等同物，可以指数据封包进入节点的端口。就本文使用的而言，术语“出口端口”、“离开端口”及其等同物，可以指封包离开节点的端口。
36.如图1中所示，有序封包108按“a”、“b”和“c”的顺序被标记并且从源102发送。有序封包108可以相继到达网络106中的第一节点110。第一节点110可以沿着通过网络106的不
同路径转发封包，这些路径包括第一路径112、第二路径114和第三路径116。第一节点110可以基于各种因素来沿着不同的路径转发封包。例如，第一节点110可包括负载平衡器，该负载平衡器可以在接收到封包“a”时识别出第一路径112是最不拥塞的路径，但可以在接收到封包“b”时识别出第二路径114是最不拥塞的路径。在一些情况下，第一节点110可以在接收到封包“b”时识别出第二路径114是连接的，但是在接收到封包“c”时识别出第二路径114是断开的，并且因此可以为封包“c”选择第三路径116而不是第二路径114。在特定的实现方式中，网络的问题(例如，导致拥塞或断开连接的问题)可能使得第一节点110沿着不同的路径转发封包。
37.就本文使用的而言，术语“路径”、“网络路径”及其等同物，可以指封包可以穿越的节点和/或接口的具体序列。可以在两个节点之间定义路径。在一些情况下，从第一节点传输到第二节点的封包的路径可以根据第一节点的身份、第二节点的身份以及封包从第一节点到第二节点所行经的中间节点和/或接口的任何序列来定义。
38.就本文使用的而言，术语“接口”及其等同物可以指网络中的两个节点之间的连接。在一些情况下，接口可以直接连接两个节点和/或可以省略任何中间节点。接口可以连接到第一设备的第一端口和第二设备的第二端口。在一些情况下，两个节点之间的接口可以是有线接口，从而，封包可以作为通过连接两个节点的固体介质(例如，以太网线缆、光缆，等等)传导的信号来传输。在一些示例中，节点之间的接口可以是无线接口，从而，封包可以作为信号通过连接两个节点的流体介质(例如，空气、水，等等)来传输。可以根据用于携带信号的波的类型(例如，声波、电磁波，等等)和波的频率(例如，超声频率、无线电频率、红外频率，等等)来定义无线接口。可以根据特定的通信协议来进一步定义接口，该协议可以指示出通过接口传输的数据是如何被调制的。适用于本技术的通信协议的一些示例包括tcp/ip、wi-fi、蓝牙之类的。
39.如图1中所示，第一路径112、第二路径114和第三路径116可以汇聚到第二节点118，该第二节点可以将封包转发到目的地104。然而，由于第一路径112、第二路径114和第三路径116之间的差异，第二节点118可能将封包作为无序(ooo)封包120转发到目的地104。即使有序封包108是以“a”、“b”和“c”的顺序被发送的，ooo数据封包120在目的地104处却是以“c”、“a”和“b”的顺序被接收的。
40.在各种实现方式中，第一节点110和第二节点118可以为封包生成路径签名，并且用路径签名修改封包。就本文使用的而言，术语“签名”、“路径签名”及其等同物可以指封包已经穿越或者正在穿越的路径的唯一标识符。路径签名可以由节点，例如第一节点110或者第二节点118，基于节点110或118的标识符、节点110或118接收封包的入口端口或者从节点110或118转发封包的出口封包中的至少一者，为给定的封包生成。节点110或118可以进一步将生成的路径签名包括在给定的封包中，并且将带有生成的路径签名的封包向目的地104转发。
41.在一些情况下，可以基于先前的路径签名来进一步生成经修订的路径签名。例如，第二节点118可以接收带有从第一节点110和/或封包在第一节点110和第二节点118之间已行经的任何中间节点生成的路径签名的给定封包，并且可以使用先前的路径签名来为给定封包生成经修订的路径签名。因此，在一些实现方式中，随着路径行经网络106，封包的路径签名可以被递归地修订。
42.根据本公开的各种实现方式，第一节点110和第二节点118可以识别出封包正通过网络106的不同路径被传输。例如，第一节点110可以从不同的端口转发封包，并且可以基于不同的端口为不同的封包生成不同的路径签名。第一节点110可以识别出路径签名是不同的，并且作为响应，可以向收集器124发送警报122，表明该流正沿着通过网络106的不同路径被传输。在一些示例中，第二节点118可以在不同的端口中接收封包，并且可以由于不同的端口而为封包生成不同的路径签名。在某些实现方式中，第二节点118可以接收带有不同的先前路径签名的封包，并且可以基于不同的先前路径签名生成经修订的路径签名。第二节点118可以识别出与封包相对应的路径签名(例如，生成的、接收的或者修订的)是不同的。
43.响应于识别出流中的不同封包的路径签名不同，第一节点110可以生成警报122并且将其发送到收集器124。类似地，响应于识别出流中的不同封包的路径签名不同，第二节点118可以生成警报126并且将其发送到收集器124。
44.在一些示例中，第二节点118可以接收由于第一路径112、第二路径114和第三路径116而带有不同路径签名的封包。第二节点118可以在不同的端口接收封包，并且可以由于不同的现有路径签名和/或接收到封包的不同端口而为封包生成不同的路径签名。第二节点118可以识别出接收到的封包的路径签名是不同的，和/或所发送的封包的路径签名是不同的，并且作为响应，向收集器124发送警报126，表明流正沿着通过网络106的不同路径被传输。
45.在特定的实现方式中，收集器124可以基于警报122和126来识别出网络106有问题。在一些情况下，收集器124可以识别出警报122是从上游节点(即，第一节点110)接收的，并且警报126是从下游节点(即，第二节点118)接收的。因此，收集器124可以识别出问题与第一节点110相关联，而不是第二节点118。一旦识别了问题，该问题就可以由网络106的管理员来解决。
46.图2图示了示例环境200，其中流的封包通过网络中的第一路径被传输，而网络没有生成警报。
47.源202可以通过包括节点a 204-a、节点b 204-b、节点c 204-c和节点d 204-d的网络发送该流。目的地206可以在流通过网络被传输之后接收该流。网络可具有多层节点。例如，节点a 204-a在第一层中，节点b 204-b和节点c 204-c在第二层中，并且节点d 204-d在第三层中。
48.如图2中所示，该流包括第一封包208。如图2中所示，第一封包208可以被从源202发送到节点a 204-a。节点a 204-a可以为第一封包208生成路径签名，并且可以将带有路径签名的第一封包208转发到节点b 204-b。在第一封包208在其被节点a 204-a接收时包括先前路径签名的示例中，节点a 204-a可以至少部分基于先前路径签名而生成新的路径签名。在第一封包208不包括先前路径签名的情况下，节点a 204-a可以依靠其他因素来生成路径签名。在各种实现方式中，节点a 204-a可以基于与节点a 204-a相关联的各种因素中的任何一者和/或第一封包208如何通过节点a 204-a被路由来生成路径签名。在各种实现方式中，第一封包208可以将路径签名作为封装在头部中的元数据来携带。例如，第一封包208可以携带封装在第一封包208的ip(例如，ipv4或ipv6)头部中的路径签名，例如，封装在ip选项(例如，ipv4)、扩展头部(例如，ipv6)等等中。在一些情况下，第一封包208可包括以太网
帧，并且路径签名可被包括在以太网帧的有效载荷中，并且可以由以太网帧的ethertype字段识别。在一些示例中，路径签名可被包括在第一封包208中的以下各项中的至少一项中：网络服务头部(network service header，nsh)、geneve头部、虚拟可扩展局域网(virtual extensible local area network，vxlan)-通用协议扩展(generic protocol extension，gpe)头部、ipv6分段路由(segment routing over ipv6，srv6)头部、多协议标签交换(multiprotocol label switching，mpls)头部，等等。在一些示例中，路径签名可以被封装在ioam、int、ifa或者ifit元数据中的至少一者中。
49.在各种实现方式中，节点a 204-a可以基于节点a 204-a为第一封包208生成的路径签名来识别该流没有改变路径。在一些情况下，第一封包208可能是节点a 204-a在该流中接收到的初始封包。在一些情形中，节点a 204-a为第一封包208生成的路径签名可能与节点a 204-a先前为节点a 204-a在该流中接收和转发的先前封包生成的路径签名相同。因为节点a 204-a没有识别出流中的路径变化，所以节点a 204-a可以不生成与该流相关联的警报。
50.带有由节点a 204-a生成的路径签名的第一封包208可以从节点a 204-a被发送到节点b 204-b。在一些情况下，节点b 204-b可以将第一封包208转发到节点d 204-d，而不修改或更新第一封包208中的路径签名。然而，在一些实现方式中，节点b 204-b可以为第一封包208生成其自己的路径签名，并且可以将带有路径签名的第一封包208转发到节点b 204-b。节点b 204-b可以至少部分基于由节点a 204-a生成的先前路径签名而迭代地生成其新的路径签名。在各种实现方式中，节点b 204-b可以基于与节点b 204-b相关联的各种因素中的任何一者和/或第一封包208如何通过节点b 204-b被路由来生成其新的路径签名。
51.在各种实现方式中，节点b 204-b可以基于节点a 204-a为第一封包208生成的路径签名和/或节点b 204-b为第一封包208生成的路径签名来识别该流没有改变路径。在一些情况下，第一封包208可能是节点b 204-b在该流中接收到的初始封包。在一些情形中，节点b 204-b为第一封包208生成的路径签名可能与节点b 204-b先前为节点b 204-b在该流中(从节点a 204-a)接收和转发的先前封包生成的路径签名相同。因为节点b 204-b没有识别出流中的路径变化，所以节点b 204-b可以不生成与该流相关联的警报。
52.带有由节点a 204-a或节点b 204-b生成的路径签名的第一封包208可以从节点b 204-b被发送到节点d 204-d。在各种实现方式中，节点d 204-d可以为第一封包208生成它自己的路径签名，并且可以将带有路径签名的第一封包208转发到目的地206。节点d 204-d可以至少部分基于节点d 204-d接收到的第一封包208中的先前路径签名来迭代地生成其新的路径签名，该先前路径签名可以是由节点a 204-a或节点b 204-b生成的路径签名。在各种实现方式中，节点d 204-d可以基于与节点d 204-d相关联的各种因素中的任何一者和/或第一封包208如何通过节点d 204-d被路由来生成其新的路径签名。
53.在各种实现方式中，节点d 204-d可以基于节点d 204-d为第一封包208生成的路径签名来识别该流没有改变路径。在一些情况下，第一封包208可能是节点d 204-d在该流中接收到的初始封包。在一些情形中，节点d 204-d为第一封包208生成的路径签名可能与节点d 204-d先前为节点d 204-d在该流中(从节点a 204-a和节点b 204-b)接收和转发的先前封包生成的路径签名相同。因为节点d 204-d没有识别出流中的路径变化，所以节点d 204-d可以不生成与该流相关联的警报。
54.图3图示了一种示例环境300，其中流的后续封包通过网络中的第二路径被传输。参考图3论述的流可以是与上文对于图2论述的流相同的流。
55.如图3中所示，该流包括第二封包302。与第一封包208一样，第二封包302可以被从源202发送到节点a 204-a。节点a 204-a可以为第二封包302生成路径签名。然而，与第一封包208不同，节点a 204-a可以将带有路径签名的第二封包302转发到节点c 204-c。在第二封包302在其被节点a 204-a接收时包括先前路径签名的示例中，节点a 204-a可以至少部分基于先前路径签名而生成新的路径签名。在第二封包302不包括先前路径签名的情况下，节点a 204-a可以依靠其他因素来生成路径签名。在各种实现方式中，节点a 204-a可以基于与节点a 204-a相关联的各种因素中的任何一者和/或第二封包302如何通过节点a 204-a被路由来生成路径签名。
56.在节点a 204-a基于第二封包302如何通过节点a 204-a被路由而生成第二封包302的路径签名的各种实现方式中，节点a 204-a为第二封包302生成的路径签名可不同于节点a 204-a为第一封包209生成的路径签名。具体而言，节点a 204-a可以基于将第一封包208路由到节点b 204-b而为第一封包208生成路径签名，并且可以基于将第二封包302路由到节点c 204-c而为第二封包302生成路径签名。基于为第一封包208和第二封包302生成的不同路径签名，节点a 204-a可以识别出该流已改变了路径。响应于识别出路径变化，节点a 204-a可以生成警报304并且将警报304发送到收集器308。警报304可以识别已改变了路径的流、流改变路径的时间、节点a 204-a，等等。
57.在各种实现方式中，第二封包302可以将路径签名作为封装在头部中的元数据来携带。例如，第二封包302可以携带封装在第一封包208的ip(例如，ipv4或ipv6)头部中的路径签名，例如，封装在ip选项(例如，ipv4)、扩展头部(例如，ipv6)等等中。在一些情况下，第二封包302可包括以太网帧，并且路径签名可被包括在以太网帧的有效载荷中，并且可以由以太网帧的ethertype字段识别。在一些示例中，路径签名可被包括在第二封包302中的以下各项中的至少一项中：网络服务头部(nsh)、geneve头部、虚拟可扩展局域网(vxlan)-通用协议扩展(gpe)头部、ipv6分段路由(srv6)头部、多协议标签交换(mpls)头部，等等。在一些示例中，路径签名可以被封装在ioam、int、ifa或者ifit元数据中的至少一者中。
58.带有由节点a 204-a生成的路径签名的第二封包302可以从节点a 204-a被发送到节点c 204-c。在一些情况下，节点c 204-c可以将第二封包302转发到节点d 204-d，而不修改或更新第二封包302中的路径签名。然而，在一些实现方式中，节点c 204-c可以为第二封包302生成其自己的路径签名，并且可以将带有路径签名的第二封包302转发到节点d 204-d。节点c 204-c可以至少部分基于由节点a 204-a生成的先前路径签名而迭代地生成其新的路径签名。在各种实现方式中，节点c 204-c可以基于与节点c 204-c相关联的各种因素中的任何一者和/或第二封包302如何通过节点c 204-c被路由来生成其新的路径签名。
59.在各种实现方式中，节点c 204-c可能没有识别出流改变了路径。例如，第二封包302可能是节点c 204-c在该流中接收到的第一个封包。因为节点c 204-c没有识别出流中的路径变化，所以节点c 204-c可以不生成与该流相关联的警报。
60.带有由节点a 204-a或节点c 204-c生成的路径签名的第二封包302可以从节点c 204-c被发送到节点d 204-d。在各种实现方式中，节点c 204-c可以为第二封包302生成它自己的路径签名，并且可以将带有路径签名的第二封包302转发到目的地206。节点d 204-d
可以至少部分基于节点d 204-d接收到的第二封包302中的先前路径签名来迭代地生成其新的路径签名，该先前路径签名可以是由节点a 204-a或节点c 204-c生成的路径签名。在各种实现方式中，节点d 204-d可以基于与节点d 204-d相关联的各种因素中的任何一者和/或第二封包302如何通过节点d 204-d被路由来生成其新的路径签名。在各种示例中，由节点d 204-d为第二封包302生成的路径签名可不同于由节点d 204-d为第一封包208生成的路径签名。
61.在各种实现方式中，节点d 204-d可以基于节点d 204-d为第一封包208生成的路径签名和节点d 204-d为第二封包302生成的路径签名来识别流已改变路径。响应于识别出路径变化，节点d 204-d可以向收集器308发送警报306。警报306可以识别已改变了路径的流、流改变路径的时间、节点d 204-d，等等。
62.收集器308可以基于来自节点a 204-a的警报304和来自节点d 204-d的警报306来识别网络的问题。在一些情况下，收集器308可以假定，网络的导致路径签名的变化的任何问题将沿着该问题下游的所有节点导致路径签名的变化。因此，尽管从节点a 204-a和节点d 204-d都接收到警报304和306，但收集器308可以识别出网络的问题与节点a 204-a相关联，而不是节点d 204-d。
63.响应于识别出网络的问题，收集器308可以向中央管理员312发送报告310。报告310可以识别关于该问题的信息，例如与该问题相关联的节点(例如，节点a 304-a)、识别该问题的时间，等等。中央管理员312可以启动一过程，通过该过程可以解决该问题。
64.图4a图示了节点转发带有路径签名的流的第一封包的示例环境400。具体地，图4a图示了节点a 204-a转发第一封包208的示例。
65.如图4a所示，节点a 204-a接收第一封包208。在图4a中，节点a 204-a可以接收没有路径签名的第一封包208。节点a 204-a在第一入口端口402-1处接收第一封包208。在特定实现方式中，节点a 204-a包括多个入口端口，例如第一入口端口402-1和第二入口端口402-2。节点a 204-a中的每个入口端口(即，第一入口端口402-1和第二入口端口402-2中的每一者)可以与唯一标识符相关联，该标识符将该入口端口与节点a 204-a中的其他入口端口区分开来。端口号是入口端口的标识符的一个示例。
66.在图4a中所示的示例中，路径签名更新器404拦截第一封包208。路径签名更新器404，或者节点a 204-a的某个其他组件，在第一出口端口406-1和第二出口端口406-2之中选择适当的出口端口。节点a 204-a中的每个出口端口(即，第一出口端口406-1和第二出口端口406-2中的每一者)可以与唯一标识符相关联，该标识符将该出口端口与节点a 204-a中的其他出口端口区分开来。端口号是出口端口的标识符的一个示例。在图4的示例中，第一出口端口406-1已被选择。
67.基于各种信息，例如接收第一封包208的第一入口端口402-1的标识符、将转发第一封包208的第一出口端口406-1的标识符、节点a 204-a本身的标识符等等中的至少一者，路径签名更新器404为第一封包208生成第一路径签名408。节点a 204-a的标识符的示例可包括与节点a 204-a相关联的唯一标识号。
68.在特定实现方式中，路径签名更新器404使用散列函数来生成第一路径签名408。该散列函数可以响应于唯一输入而返回唯一值。因此，只要对散列函数的输入指示出特定封包通过网络的唯一路径，散列函数就将返回对该路径唯一的值。在一些示例中，路径签名
更新器404使用的散列函数是加密散列函数、异或函数、crc32之类的。例如，在各种以设备为中心的实现方式中，路径签名更新器404可以使用以下公式1来生成第一路径签名408：
69.公式1 s0＝hash(pi,pe,n1)
70.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，pi是接收封包(例如，第一封包208)的入口端口(例如，第一入口端口402-1)的标识符，pe是从其转发封包的出口端口(例如，第一出口端口406-1)的标识符，并且n1是节点(例如，节点a 204-a)的标识符。根据一些示例，路径签名更新器404可以使用以下公式2来生成第一路径签名408：
71.公式2 s0＝hash(pe,n1)
72.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，pe是从其转发封包(例如，第一封包208)的出口端口(例如，第一出口端口406-1)的标识符，并且n1是节点(例如，节点a 204-a)的标识符。在一些轻量级实现方式中，路径签名更新器406使用以下公式3来生成第二路径签名410：
73.公式3 s0＝hash(n1)
74.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，并且n1是节点(例如，节点a 204-a)的标识符。
75.在特定的以流为中心的实现方式中，路径签名更新器404可以使用以下公式4来生成流的唯一标识符：
76.公式4 f＝hash(is,id,ps,pd,pro)
77.其中，f是流的标识符，hash()是散列函数，is是流的源的标识符(例如，流中的数据封包的源的ip地址)，id是流的目的地的标识符(例如，流中的数据封包的目的地的ip地址)，ps是源的端口的标识符(例如，端口号)，pd是目的地的端口的标识符(例如，端口号)，并且pro是与流相关联的协议的标识符(例如，指示出流中传送的数据的类型的协议)。在一些情况下，公式4的散列函数的各种元素可以被省略。例如，利用is、id和pro作为输入的3元组散列函数可被用来唯一地识别流。
78.在各种情况下，路径签名更新器404可以使用在公式4中计算的流的标识符，来使用以下公式5生成路径签名：
79.公式5 s0＝hash(pi,pe,f,n1)
80.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，pi是接收封包(例如，第一封包208)的入口端口(例如，第一入口端口402-1)的标识符，pe是从其转发封包的出口端口(例如，第一出口端口406-1)的标识符，f是(例如，利用公式4生成的)流的标识符，并且n1是节点(例如，节点a 204-a)的标识符。根据一些示例，路径签名更新器404可以使用以下公式6来生成第一路径签名408：
81.公式6 s0＝hash(pe,f,n1)
82.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，pe是从其转发封包(例如，第一封包208)的出口端口(例如，第一出口端口406-1)的标识符，f是(例如，利用公式4生成的)流的标识符，并且n1是节点(例如，节点a 204-a)的标识符。在一些轻量级实现方式中，路径签名更新器406使用以下公式7来生成第二路径签名410：
83.公式7 s0＝hash(f,n1)
84.其中，s0是路径签名(例如，由节点a 204-a生成的第一路径签名408)，hash()是散列函数，f是(例如，利用公式4生成的)流的标识符，并且n1是节点(例如，节点a 204-a)的标识符。
85.无论路径签名更新器404使用的公式是什么，第一路径签名408都可以唯一地表示第一封包208通过节点a 204-a的路径。在路径签名更新器404利用公式1、2、6或7的示例中，第一路径签名408可以进一步识别包括节点b 204-b的路径，第一封包208被使用第一出口端口406-1转发到该节点b 204-b。
86.路径签名更新器404将第一路径签名408添加到第一封包208。在一些示例中，路径签名更新器404将第一路径签名408添加到第一封包208的头部。例如，路径签名更新器404可以向第一封包208中插入路径签名字段，并且用第一路径签名408来填充路径签名字段。在一些情况下，路径签名字段被包括在头部字段中(例如，ip头部、ipv4选项、ipv6扩展头部、nsh头部、geneve头部、vxlan-gpe头部、srv6头部、或者mpls头部)和/或被包括在有效载荷中(例如，由ethertype识别的)。在一些示例中，路径签名字段被包括在ioam、int、ifa或者ifit元数据中的至少一者中。根据特定实现方式，路径签名字段具有固定大小。例如，路径签名字段具有32比特、64比特或者类似的固定大小。因此，在各种实现方式中，由路径签名更新器404生成的每个路径签名(例如，第一个路径签名408)将具有与路径签名字段相同的固定大小。
87.路径签名更新器404可以进一步通过第一出口端口406-1转发带有第一路径签名408的第一封包208。第一出口端口406-1可以连接到一接口，该接口连接到与节点a 204-a在同一网络中的另一节点。例如，如图2中所示，第一封包208可以从第一出口端口406-1被转发到节点b 204-b。
88.如图4a中所示，路径签名更新器404进一步将第一路径签名408存储在流表410中。在一些情况下，流表410包括与由节点a 204-a接收和转发的不同封包相对应的多个条目。例如，流表410可包括与包括第一路径签名408的第一封包208相对应的条目。在一些情况下，这些条目还识别由节点a 204-a接收和转发的不同封包的流。例如，与第一封包208相对应的条目还可包括识别包括第一封包208的流的信息。
89.节点a 204-a在各种实现方式中还包括路径变化识别器412。路径变化识别器412可被配置为访问流表410，以确定特定流中的封包是否具有不同的路径。在一些示例中，路径变化识别器412可以确定第一路径签名408对应于由路径签名更新器404为该流生成的初始路径签名，因此可以假定对于该流没有发生路径变化。在一些情况中，路径变化识别器412可以确定第一路径签名408匹配由路径签名更新器404为该流生成的先前路径签名，因此可以假定该流没有发生路径变化。当路径变化识别器412确定没有发生路径变化时，路径变化识别器412可以不生成警报。
90.图4b图示了节点转发带有路径签名的流的另一封包的示例环境414。具体地，图4b图示了节点a 204-a转发第二封包302的示例。
91.如图4b所示，节点a 204-a接收没有路径签名的第二封包302。节点a 204-a在第一入口端口402-1处接收第二封包302。路径签名更新器404拦截第二封包302。
92.路径签名更新器404，或者节点a 204-a的某个其他组件，可以在第一出口端口
406-1和第二出口端口406-2之中为第二封包302选择适当的出口端口。然而，节点a 204-a可以为第二封包302选择第二出口端口406-2，与为第一封包208选择的第一出口端口406-1不同。节点a 204-a可以出于各种原因中的任何一种而选择第二出口端口406-2。例如，节点a 204-a可以识别出与第一出口端口406-1相连接的接口，或者与该接口相连接的节点(即，节点b 204-b)，自第一封包208被转发以来已断开。在一些示例中，节点a 204-a可包括负载平衡器，该负载平衡器识别与第一出口端口406-1相关联的负载超过了与第二出口端口406-2相关联的负载。例如，与第一出口端口406-1(即，节点b 204-b)相连接的节点可能比与第二出口端口406-2(即，节点c 204-c)相连接的节点更拥塞和/或与更高的时延相关联。
93.基于各种信息，例如接收第二封包302的第一入口端口402-1的标识符、将转发第二封包302的第二出口端口408-2的标识符、节点a 204-a本身的标识符等等中的至少一者，路径签名更新器404为第二封包302生成第二路径签名416。
94.在特定实现方式中，路径签名更新器404使用公式1、2、5或者6之一来生成第一路径签名408和第二路径签名416。因此，可以基于第一出口端口406-1的标识符生成第一路径签名408，并且可以基于第二出口端口406-2的标识符生成第二路径签名416。至少由于这个原因，第二路径签名416可能与第一路径签名408不同。
95.路径签名更新器404将第二路径签名416添加到第二封包302。在一些示例中，路径签名更新器404将第二路径签名416添加到第二封包302的头部。例如，路径签名更新器404可以向第二封包302中插入路径签名字段，并且用第二路径签名416来填充路径签名字段。在一些情况下，第二路径签名416可具有与第一路径签名408相同的大小。
96.路径签名更新器404可以进一步通过第二出口端口406-2转发带有第二路径签名416的第二封包302。第二出口端口406-2可以连接到一接口，该接口连接到与节点a 204-a在同一网络中的另一节点。例如，如图3中所示，第二封包302可以从第二出口端口406-2被转发到节点c 204-c。
97.如图4b中所示，路径签名更新器404进一步将第二路径签名416存储在流表410中。在一些情况下，流表410可能已经存储了与包括第一路径签名408的第一封包208相对应的第一条目。流表可以进一步存储与包括第二路径签名416的第二封包302相对应的第二条目。在一些情况下，与第一封包208和第二封包302相对应的第一和第二条目也可包括识别包括第一封包208和第二封包302的流的信息。
98.路径变化识别器412可以确定，存储在流表410的第二条目中的第二路径签名416，与存储在流表410的第一条目中的第一路径签名408不同。基于这种差异，路径变化识别器412可以确定在流中存在路径变化。在一些情况下，路径变化识别器412可以确定已经接收到大于阈值数目的带有第一路径签名408的封包和/或大于阈值数目的带有第二路径签名416的封包，并且作为响应，识别出流中存在持续的路径变化。响应于确定存在路径变化，路径变化识别器412可以从节点a 204-a生成并且发送警报304。警报304可以指示出流中的路径变化。如图4b的示例中所示，警报304包括流标识符418。流标识符418可以指示出包括第一封包208和第二封包302的流。例如，流标识符418可包括与该流相关联的5元组的至少一个元素，例如源(例如，来自同一ip地址)、目的地(例如，指向同一ip地址)、协议(例如，ip协议)、源端口(例如，对于udp或tcp)、目的地端口(例如，对于udp、tcp或icmp)，或者第一封包208和第二封包302的服务的类型(例如，ip服务类型(tos))。在警报304被发送到收集器(例
如，收集器310)的示例中，流标识符418可用于识别网络中导致路径变化的问题。
99.图5a图示了节点转发带有路径签名的流的第一封包的示例环境500。具体地，图5a图示了节点d 204-d转发第一封包208的示例。
100.如图5a所示，节点d 204-d接收带有第三路径签名502的第一封包208。在在第一封包208的路径中在节点a 204-a和节点d 204-d之间没有节点改变或更新了第一封包208中的路径签名字段的一些实现方式中，第三路径签名502可以是由节点a 204-a生成的第一路径签名408。在路径签名字段在节点a 204-a和节点d 204-d之间已被更新的某些实现方式中，第三路径签名502可以基于由节点a 204-a为第一封包208生成的第一路径签名408。
101.节点d 204-d可以在第一入口端口502-1处接收带有第三路径签名502的第一封包208，该端口可以连接到与节点d 204-d在相同网络中的另一个节点(即，节点b 204-b)。在特定实现方式中，节点d 204-d包括多个入口端口，例如第一入口端口502-1和第二入口端口502-2。节点d 204-d中的每个入口端口(即，第一入口端口502-1和第二入口端口502-2中的每一者)可以与唯一标识符相关联，该标识符将该入口端口与节点d 204-d中的其他入口端口区分开来。
102.在图5a中所示的示例中，路径签名更新器504拦截第一封包208。路径签名更新器504，或者节点d 204-d的某个其他组件，在第一出口端口506-1和第二出口端口506-2之中选择适当的出口端口。节点d 204-d中的每个出口端口(即，第一出口端口506-1和第二出口端口506-2中的每一者)可以与唯一标识符相关联，该标识符将该出口端口与节点a 204-a中的其他出口端口区分开来。在图5a的示例中，第一出口端口506-1已被选择。
103.基于各种信息，例如接收第一封包208的第一入口端口502-1的标识符、将转发第一封包508的第一出口端口508-1的标识符、节点d 204-d本身的标识符等等中的至少一者，路径签名更新器504为第一封包208生成第四路径签名508。另外，路径签名更新器504可以使用递归函数生成第四路径签名508，该递归函数至少部分基于节点d 204-d接收到的第一封包208中的第三路径签名502。
104.在特定实现方式中，路径签名更新器504使用散列函数来基于第三路径签名502生成第四路径签名508。该散列函数可以响应于唯一输入而返回唯一值。因此，只要对散列函数的输入指示出特定封包通过网络的唯一路径，散列函数就将返回对该路径唯一的值。在一些示例中，路径签名更新器404使用的散列函数是加密散列函数、异或函数、crc32之类的。在特定实现方式中，节点d 204-d中的路径签名更新器504利用的散列函数可能不同于节点a 204-a中的路径签名更新器404利用的散列函数。在一些情况下，路径签名更新器504可以使用以下公式8来生成第四路径签名508：
105.公式8 sn＝hash(s
n-1
,pi,pe,n1)
106.其中，sn是新的路径签名(例如，第四路径签名508)，hash()是散列函数，sn是先前路径签名(例如，第三路径签名502)，pi是接收到第一封包的入口端口的标识符(例如，第一入口端口502-1的标识符)，pe是转发封包的出口端口的标识符(例如，第一出口端口506-1的标识符)，并且n1是节点的标识符(例如，节点d 204-d的标识符)。根据一些示例，路径签名更新器504可以使用以下公式9来生成第一路径签名508：
107.公式9 sn＝hash(s
n-1
,pi,n1)
108.其中，sn是新的路径签名(例如，第四路径签名508)，hash()是散列函数，sn是先前
路径签名(例如，第三路径签名502)，pi是接收到第一封包的入口端口的标识符(例如，第一入口端口502-1的标识符)，并且n1是节点的标识符(例如，节点d 204-d的标识符)。根据一些示例，路径签名更新器504可以使用以下公式10来生成第四路径签名508：
109.公式10 sn＝hash(s
n-1
,n1)
110.其中，sn是新的路径签名(例如，第四路径签名508)，hash()是散列函数，sn是先前路径签名(例如，第三路径签名502)，并且n1是节点的标识符(例如，节点d 204-d的标识符)。
111.无论路径签名更新器504使用的公式是什么，第四路径签名508都可以唯一地表示第一封包208从第一封包208的源到节点d 204-d的路径。
112.路径签名更新器504可以在第一封包208中用第四路径签名508替换第三路径签名502。在一些示例中，路径签名更新器504删除第三路径签名502并且将第四路径签名508添加到第一封包208的头部。例如，路径签名更新器504可以从第一封包208中的路径签名字段中删除第三路径签名502，并且用第四路径签名508填充路径签名字段。在一些情况下，路径签名字段被包括在头部字段中(例如，ip头部、ipv4选项、ipv6扩展头部、nsh头部、geneve头部、vxlan-gpe头部、srv6头部、或者mpls头部)和/或被包括在有效载荷中(例如，由ethertype识别的)。在一些示例中，路径签名字段被包括在ioam、int、ifa或者ifit元数据中的至少一者中。根据特定实现方式，路径签名字段具有固定大小。例如，路径签名字段具有32比特、64比特或者类似的固定大小。因此，第四路径签名508可具有与第三路径签名502相同的大小。在各种实现方式中，由路径签名更新器504生成的每个路径签名(例如，第四路径签名508)将具有与第一封包208中的路径签名字段相同的固定大小。
113.路径签名更新器504可以进一步通过第一出口端口506-1转发带有第四路径签名508的第一封包208。第一出口端口506-1可以连接到与另一节点相连接的接口。例如，如图2中所示，第一封包208可以从第一出口端口506-1被转发到目的地206。
114.如图5a中所示，路径签名更新器504进一步将第四路径签名508存储在流表510中。在一些情况下，流表510包括与由节点d 204-d接收和转发的不同封包相对应的多个条目。例如，流表510可包括与包括第四路径签名508的第一封包208相对应的条目。在一些情况下，该条目还可包括第三路径签名502。在特定实现方式中，该条目还识别由节点d 204-d接收和转发的不同封包的流。例如，流表510中的与第一封包208相对应的条目还可包括识别包括第一封包208的流的信息。
115.节点d 204-d在各种实现方式中还包括路径变化识别器512。路径变化识别器512可被配置为访问流表510，以确定特定流中的封包是否具有不同的路径。在一些示例中，路径变化识别器512可以确定第四路径签名508对应于由路径签名更新器504为该流生成的初始路径签名，因此可以假定对于该流没有发生路径变化。在一些情况中，路径变化识别器512可以确定第四路径签名508匹配由路径签名更新器504为该流生成的先前路径签名，因此可以假定对于该流没有发生路径变化。当路径变化识别器512确定没有发生路径变化时，路径变化识别器512可以不生成警报。
116.图5b图示了节点转发带有路径签名的流的另一封包的示例环境514。具体地，图5b图示了节点d 204-d转发第二封包302的示例。
117.如图5b所示，节点d 204-d接收带有第五路径签名516的第二封包302。在在第二封
包302的路径中在节点a 204-a和节点d 204-d之间没有节点改变或更新了第二封包302中的路径签名字段的一些实现方式中，第五路径签名516可以是由节点a 204-a生成的第二路径签名416。在路径签名字段在节点a 204-a和节点d 204-d之间已被更新的某些实现方式中，第五路径签名516可以基于由节点a 204-a为第一封包208生成的第二路径签名416。
118.节点d 204-d在第二入口端口502-2处接收第二封包302，而不是在接收第一封包208的第一入口端口502-1处接收。这表明第二封包302在到达节点d 204-d之前行经的路径与第一封包208行经的路径不同。路径签名更新器504拦截第二封包302。节点d 204-d可以进一步选择第一出口端口506-1，从该出口端口向其目的地转发第二封包302。
119.基于各种信息，例如接收第二封包302的第二入口端口502-2的标识符、将转发第二封包302的第一出口端口508-1的标识符、节点d 204-d本身的标识符等等中的至少一者，路径签名更新器504为第二封包302生成第六路径签名518。
120.在各种实现方式中，路径签名更新器504可以基于接收到的第二封包302中先前的第五路径签名516来生成第六路径签名518。在一些示例中，路径签名更新器404使用公式8-10中的至少一者来生成第四路径签名508和第六路径签名518。至少部分基于第三路径签名502和第五路径签名516之间的差异，和/或接收到第一封包208的第一入口端口502-1和接收到第二封包302的第二入口端口502-2之间的差异，第六路径签名516可以与第三路径签名502不同。
121.路径签名更新器504可以在第二封包302中用第六路径签名518替换第五路径签名516。在一些示例中，路径签名更新器504删除第五路径签名516并且将第六路径签名518添加到第二封包302的头部。例如，路径签名更新器504可以从第二封包302中的路径签名字段中删除第五路径签名516，并且用第六路径签名518填充路径签名字段。在一些情况下，路径签名字段被包括在头部字段中(例如，ip头部、ipv4选项、ipv6扩展头部、nsh头部、geneve头部、vxlan-gpe头部、srv6头部、或者mpls头部)和/或被包括在有效载荷中(例如，由ethertype识别的)。在一些示例中，路径签名字段被包括在ioam、int、ifa或者ifit元数据中的至少一者中。路径签名字段可具有固定大小。因此，第六路径签名518可具有与第五路径签名516相同的大小。路径签名更新器504可以进一步通过第一出口端口506-1转发带有第六路径签名518的第二封包302。
122.如图5b中所示，路径签名更新器504进一步将第六路径签名518存储在流表410中。在一些情况下，流表510可能已经存储了与包括第四路径签名508的第一封包208相对应的第一条目。在一些情况下，第一条目还可包括第三路径签名502。流表510可以进一步存储与包括第六路径签名518的第二封包302相对应的第二条目。在一些示例中，第二条目还可包括第五路径签名516。在一些情况下，与第一封包208和第二封包302相对应的第一和第二条目也可包括识别包括第一封包208和第二封包302的流的信息。
123.路径变化识别器512可以确定，存储在流表510的第二条目中的第六路径签名518，与存储在流表510的第一条目中的第四路径签名508不同。基于这种差异，路径变化识别器512可以确定在流中存在路径变化。响应于确定存在路径变化，路径变化识别器512可以从节点d 204-d生成并且发送警报306。警报306可以指示出流中的路径变化。如图5b的示例中所示，警报306包括流标识符418。在警报306被发送到收集器(例如，收集器308)的示例中，流标识符518可用于识别网络中导致路径变化的问题。
124.图6a图示了流表600的示例，其中带有与通过特定节点的不同流相对应的各种条目。在一些示例中，流表600可以被用作上文参考图4a和图4b描述的流表410或者上文参考图5a和图5b描述的流表510。在各种实现方式中，流表600可以由接收和转发多个流中的多个封包的节点所管理。
125.流表600包括多个条目。每一个条目包括多个字段。如图6a中所示，这些字段包括条目编号、流标识符、计数、最后封包时间、以及路径签名。在各种实现方式中，条目可包括更少的或者额外的字段。
126.在一些情况下，流表600包括与固定数目的流标识符相关联的固定数目的条目。该固定数目可以是大于1的整数。如图6a中所示，流表600包括十个条目(条目#1-#10)。存储在流表600中的条目可对应于其封包最近被节点接收和转发的十个流。如果超过十个流包括被节点接收和转发的封包，则可以在流表600中只存储与十个最近的流相对应的十个条目。因此，流表600的大小可以被限制以节约节点处的存储器资源。
127.与封包相对应的条目的流标识符字段可以指示出与该条目相对应的流。在一些情况下，流标识符字段可包括以下各项中的至少一项：入口接口(例如，snmp ifindex)、源(例如，来自相同的ip地址)、目的地(例如，指向相同的ip地址)、协议(例如，ip协议)、源端口(例如，对于udp或者tcp)、目的地端口(例如，对于udp、tcp或icmp)、或者与该流相关联的服务的类型(例如，ip服务类型(tos))。在某些实现方式中，流标识符字段可以是可用于识别流的字符串。
128.与流相对应的条目的计数字段可以对应于节点在流中接收和/或转发的封包的数目。在一些情况下，计数字段可以对应于流的如下封包的数目：这些封包在带有特定签名的情况下被接收和/或转发，而流没有经历路径变化。例如，“计数1”可对应于节点接收到的带有“流标识符1”的封包的数目。在一些情况下，“计数1”可对应于自从流开始或者流的最后一次路径变化以来接收到的带有“签名1”的封包的数目。
129.与流相对应的条目的时间字段可以指示出该流的最新近封包被节点接收到的时间、该流的最新近封包被节点转发的时间、或者其组合。
130.与流相对应的条目的路径签名字段可包括由节点为该流的封包生成的路径签名。在一些情况下，路径签名字段还可包括节点为该流接收到的先前路径签名。
131.在特定实现方式中，路径签名字段可用于识别该流是否与路径变化相关联。例如，在图6a中所示的示例中，与“流标识符1”相对应的“签名1”可以被设置为“签名a”。当节点接收到与“流标识符1”相对应的包括不同于“签名a”的签名的封包时，节点可以识别出带有“流标识符1”的流中的路径变化。因此，该节点可以生成并且发送与“流标识符1”相对应的警报。
132.图6b图示了流表602的示例，其中图示了特定数据流中的路径变化。例如，流表602可以对应于上文参考图6a描述的流表600中的“条目#1”。
133.如图所示，流表602可以对应于单个流标识符，例如“流标识符1”。流表602可以跟踪在与“流标识符1”相对应的流中由节点接收和/或转发的个体封包。在一些情况下，流表602可以跟踪与“流标识符1”相对应的预定数目的最新近封包，例如在与“流标识符1”相对应的流中接收和/或转发的最新近的十个封包。
134.每个个体封包可具有其自己的时间戳(例如，“时间戳a”到“时间戳j”中的一个)。
在一些情况下，给定的时间戳可以对应于节点接收到个体封包的时间和/或节点转发该流中的个体封包的时间。参考图6a，“时间戳1”可以是“时间戳a”至“时间戳j”中最新近的一个。
135.流表602也可以跟踪个体封包的路径签名。流表602中的给定路径签名可以对应于接收到的封包中的路径签名和/或由节点转发的封包中的路径签名。例如，与“流标识符1”相对应的流中的五个封包可具有“签名a”的路径签名，而流中的五个封包可具有“签名b”的路径签名。参考图6a，“签名1”可以是在流标识符1中观察到的最新近的路径签名(例如，“签名a”或者“签名b”)。
136.可以利用流表602来识别与“流标识符1”相对应的流中的路径变化。假定流表602是按时间先后顺序排列的，其中“时间戳j”是最新近的时间戳，则在“时间戳e”和“时间戳f”之间可以观察到路径变化，其中，流的封包从“签名a”变化到“签名b”。因此，可以高效地识别出流中的路径变化。
137.图7a和图7b图示了用于更新数据封包的路径签名的示例过程700和712。在一些示例实现方式中，过程700和/或过程712由网络节点执行，例如上文参考图1描述的第一节点110或网络节点118，或者上文参考图2-图5b描述的节点a至d 204-a至204-d中的任何一者。
138.过程700可以由接收到没有现有路径签名的数据封包的节点执行。在702，接收到封包。该封包可能是通过网络从源到目的地的流的一部分。在一些情况下，接收到的封包可以省略路径签名。
139.在704，基于一个或多个节点细节的路径签名被生成。该一个或多个节点细节可包括接收到封包的特定入口端口的标识符、将从其转发封包的出口端口的标识符、接收到封包的节点的标识符等等中的至少一者。在各种实现方式中，可以使用散列函数来生成路径签名。例如，上述公式1至3或者5至7中的任何一者可以用来生成路径签名。在一些实现方式中，路径签名可具有有限的大小，例如32比特、64比特，或者类似的大小。
140.在706，路径签名被添加到封包。在一些情况下，路径签名被填充在封包的头部(例如，ip头部、ipv4选项、ipv6扩展头部、nsh头部、geneve头部、vxlan-gpe头部、srv6头部、或者mpls头部)中的数据字段中和/或有效载荷(例如，由ethertype识别的)中。在一些示例中，数据字段被包括在封包内的ioam、int、ifa或者ifit元数据中的至少一者中。数据字段可具有与路径签名的长度相对应的固定大小。
141.在708，封包与路径签名一起被转发。在各种实现方式中，封包被从所选择的出口端口转发。可以基于封包的目的地、与隶属于出口端口的节点相关联的负载、与附接到另一出口端口的节点相关联的负载等等中的至少一者来选择出口端口。例如，封包的头部可以指示出封包的目的地，并且可以选择出口端口以在目的地的方向上转发封包。在一些情况下，可以使用负载平衡功能来选择附接到网络中的相对不拥塞的至少一个节点的出口端口。
142.在710，基于路径签名来更新流表。在一些情况下，可以生成流表的条目以包括路径签名和流的标识符、封包被接收的时间戳、封包被转发的时间戳等等中的至少一者。在各种示例中，在过程700中生成的路径签名可以是在同一流的先前封包中利用的相同路径签名。根据各种实现方式，可以在710处识别和更新与路径签名相对应的流表中的现有条目。例如，该条目可包括与带有路径签名的流的封包的数目相对应的计数或者与带有路径签名
的最新近封包的时间戳相对应的最后封包时间中的至少一者。可以基于在过程700中接收、更新和转发的封包来更新该计数和/或最后封包时间。
143.虽然在图7a中没有图示，但执行过程700的实体可以额外地基于流表来识别流的路径变化。例如，通过向流表添加与否则没有出现在该流表中的新路径签名相对应的新条目，可以识别路径变化。在一些情况下，执行过程700的实体可以识别出已接收和/或转发了流中的超过阈值数目的带有一个或多个路径签名的封包，并且因此可以识别出路径变化已发生。在一些情况下，该实体可以生成并且发送识别路径变化的警报。
144.过程712可由接收带有现有路径签名的数据路径的节点执行。在714，接收到包括第一路径签名的封包。该封包可能是通过网络从源到目的地的流的一部分。在一些情况下，第一路径签名可能已由网络中的先前节点生成和/或添加到封包。
145.在716，基于第一路径签名和一个或多个节点细节的第二路径签名被生成。该一个或多个节点细节可包括接收到封包的特定入口端口的标识符、将从其转发封包的出口端口的标识符、接收到封包的节点的标识符等等中的至少一者。在各种实现方式中，可以使用散列函数来生成路径签名。例如，上述公式8至10中的任何一者可以用来生成路径签名。在一些实现方式中，路径签名可具有有限的大小，例如32比特、64比特，或者类似的大小。第二路径签名可具有与第一路径签名相同的大小。
146.在718，在封包中用第二路径签名来替换第一路径签名。在一些情况下，第一路径签名被从封包的头部字段(例如，ip头部、ipv4选项、ipv6扩展头部、nsh头部、geneve头部、vxlan-gpe头部、srv6头部、或者mpls头部)中的数据字段和/或有效载荷(例如，由ethertype识别的)中删除，并且第二路径签名被填充在其中。在一些示例中，数据字段被包括在封包内的ioam、int、ifa或者ifit元数据中的至少一者中。数据字段可具有与路径签名的长度相对应的固定大小。
147.在720，封包与第二路径签名一起被转发。在各种实现方式中，封包被从所选择的出口端口转发。可以基于封包的目的地、与隶属于出口端口的节点相关联的负载、与附接到另一出口端口的节点相关联的负载等等中的至少一者来选择出口端口。例如，封包的头部可以指示出封包的目的地，并且可以选择出口端口以在目的地的方向上转发封包。在一些情况下，可以使用负载平衡功能来选择附接到网络中的相对不拥塞的至少一个节点的出口端口。
148.在722，基于第一路径签名和/或第二路径签名来更新流表。在一些情况下，可以生成流表的条目以包括第一路径签名和/或第二路径签名以及流的标识符、封包被接收的时间戳、封包被转发的时间戳等等中的至少一者。在各种示例中，第一路径签名和/或第二路径签名可以是在同一流的先前封包中利用的相同路径签名。根据各种实现方式，可以在722处识别和更新与第一路径签名和/或第二路径签名相对应的流表中的现有条目。例如，该条目可包括与带有第一路径签名和/或第二路径签名的流的封包的数目相对应的计数或者与带有第一路径签名和/或第二路径签名的最新近封包的时间戳相对应的最后封包时间中的至少一者。可以基于在过程712中接收、更新和转发的封包来更新该计数和/或最后封包时间。
149.虽然在图7b中没有图示，但执行过程712的实体可以额外地基于流表来识别流的路径变化。例如，通过向流表添加与否则没有出现在该流表中的新路径签名(例如，第一路
径签名和/或第二路径签名)相对应的新条目，可以识别路径变化。在一些情况下，执行过程712的实体可以识别出已接收和/或转发了流中的超过阈值数目的带有一个或多个路径签名的封包，并且因此可以识别出路径变化已发生。在一些情况下，该实体可以生成并且发送识别路径变化的警报。
150.图8图示了用于基于带有不同路径签名的数据封包来发送警报的示例过程800。在一些示例实现方式中，过程800由网络节点执行，例如上文参考图1描述的第一节点110或网络节点118，或者上文参考图2-图5b描述的节点a至d 204-a至204-d中的任何一者。
151.在802，识别流中的第一封包的第一路径签名。在一些实现方式中，第一路径签名在从网络中的先前节点接收到的第一封包中。在一些情况下，第一路径签名在转发到网络中的下一节点的第一封包中。根据特定实现方式，第一路径签名可以由执行过程800的设备生成。
152.在804，识别流中的第二封包的第二路径签名。在一些情况下，第二路径签名可来自与第一路径签名相同的源。例如，如果第一路径签名由执行过程800的节点生成，则第二路径签名也由执行过程800的节点生成。在各种实现方式中，第二路径签名可具有与第一路径签名等同的大小。例如，第一和第二路径签名可各自具有32比特、64比特或者类似的大小。
153.在806，第一路径签名被确定为与第二路径签名不同。在一些情况下，第一路径签名和第二路径签名被存储在本地存储器中，例如存储在流表中。因此，即使在第一和第二封包中的一者或两者被转发到网络中的另一节点之后，也可以比较第一路径签名和第二路径签名。在一些情况下，执行过程800的实体可以额外地确定流中的带有第一路径签名的封包的数目和/或流中的带有第二路径签名的封包的数目超过预定的阈值。在各种实现方式中，第一路径签名和第二路径签名可以在第一和第二封包被转发之前被比较、在转发之时被比较或者在转发之后立即被比较。
154.在808，指示出该流的警报被发送到收集器。收集器可以是单独的设备，它可以从网络中的其他节点接收其他警报。在各种实现方式中，警报可以是在有效载荷中包括流指示符的数据封包。流指示符可包括与流相关联的5元组的至少一个元素中的至少一者，例如源(例如，来自同一ip地址)、目的地(例如，指向同一ip地址)、协议(例如，ip协议)、源端口(例如，对于udp或tcp)、目的地端口(例如，对于udp、tcp或icmp)，或者第一封包和第二封包的服务的类型(例如，ip服务类型(tos))。在一些情况下，警报还可以指示出执行过程800的设备。例如，警报可包括头部或有效载荷中的节点标识符(例如，ip地址)。
155.图9图示了用于基于路径变化来向中央管理员报告问题的示例过程900。在一些示例实现方式中，过程900由收集器执行，例如上文参考图1描述的收集器124或者上文参考图3描述的收集器308。
156.在902，从节点接收到警报。警报可以指示出该节点所属的网络中的路径变化。在各种实现方式中，警报可以是在有效载荷中包括流指示符的数据封包。流指示符可包括与流相关联的5元组的至少一个元素中的至少一者，例如源(例如，来自同一ip地址)、目的地(例如，指向同一ip地址)、协议(例如，ip协议)、源端口(例如，对于udp或tcp)、目的地端口(例如，对于udp、tcp或icmp)，或者第一封包和第二封包的服务的类型(例如，ip服务类型(tos))。在一些情况下，警报还可以指示出节点本身。例如，警报可包括头部或有效载荷中
的节点标识符(例如，ip地址)。
157.在904，识别与该节点相关联的问题。在一些情况下，可以从另一节点接收到另一警报，该另一节点是在902处从其接收到警报的节点的下游。下游节点处的路径变化可以被确定为起源于在902处从其接收到警报的节点。在一些情况下，该问题可能是与节点和下游节点之间的接口相关联的问题。例如，该节点可以确定将流中的第一封包转发到下游节点，然后确定该接口已被中断，然后可以确定将流中的第二封包转发到网络中的不同节点。在一些情况下，该问题可能是与网络中的拥塞相关联的问题。例如，该节点可以确定将流中的第一封包转发到下游节点，可以确定下游节点是拥塞的，然后可以决定将流中的第二封包转发到不同的下游节点。
158.在906，该问题被报告给中央管理员。在一些情况下，中央管理员可以启动一个过程，通过该过程可以解决该问题。在各种实现方式中，中央管理员可以是一设备，该设备可以向可以解决该问题的个人或系统输出警报。例如，中央管理员可以派遣某个人去纠正网络中的问题。
159.图10示出了能够执行用于实现上文描述的功能的程序组件的服务器计算机1000的示例计算机体系结构。图10所示的计算机体系结构图示了传统的服务器计算机、工作站、桌面型计算机、膝上型电脑、平板设备、网络设备、电子阅读器、智能电话或者其他计算设备，并且可被利用来执行本文提出的任何软件组件。在一些示例中，服务器计算机1000可以对应于本文描述的网络节点204。
160.计算机1000包括基板1002，或者“主板”，它是印刷电路板，许多组件或设备可以通过系统总线或者其他电气通信路径的方式连接到它。在一个说明性配置中，一个或多个中央处理单元(central processing unit，“cpu”)1004结合芯片组1006一起操作。cpu 1004可以是标准的可编程处理器，它执行计算机1000的操作所必需的算术和逻辑操作。
161.cpu 1004通过从一个离散的物理状态转变到下一个状态来执行操作，其中状态转变是通过对区分和改变这些状态的切换元件的操纵来实现的。切换元件一般包括维持两个二进制状态之一的电子电路，例如触发器，以及基于一个或多个其他切换元件的状态的逻辑组合来提供输出状态的电子电路，例如逻辑门。这些基本的切换元件可以被组合以创建更复杂的逻辑电路，包括寄存器、加减器、算术逻辑单元、浮点单元，等等。
162.芯片组1006在cpu 1004和基板1002上的其余组件和设备之间提供了接口。芯片组1006可以提供与ram 1008的接口，该ram被用作计算机1000中的主存储器。芯片组1006可以进一步提供与计算机可读存储介质的接口，所述介质例如是只读存储器(read-only memory，“rom”)1010或者非易失性ram(non-volatile ram，“nvram”)，用于存储有助于启动计算机1000和在各种组件和设备之间传送信息的基本例程。rom 1010或nvram还可以存储根据本文描述的配置进行的计算机1000的操作所必需的其他软件组件。
163.计算机1000可以在联网环境中操作，使用通过网络(例如，网络1008)与远程计算设备和计算机系统的逻辑连接。芯片组1006可包括用于通过网络接口控制器(network interface controller，nic)1012(例如千兆以太网适配器)来提供网络连通性的功能。nic 1012能够通过网络1008将计算机1000连接到其他计算设备。应当明白，计算机1000中可以存在多个nic 1012，将计算机连接到其他类型的网络和远程计算机系统。在一些情况下，nic 1012可包括至少一个入口端口和/或至少一个出口端口。
164.计算机1000可以连接到为计算机提供非易失性存储的存储设备1018。存储设备1018可以存储操作系统1020、程序1022和数据，这些在本文中已被更详细地描述。存储设备1018可以通过与芯片组1006相连接的存储控制器1014来连接到计算机1000。存储设备1018可以由一个或多个物理存储单元组成。存储控制器1014可以通过串行附接scsi(serial attached scsi，“sas”)接口、串行先进技术附件(serial advanced technology attachment，“sata”)接口、光纤通道(fiber channel，“fc”)接口或者其他类型的用于在计算机和物理存储单元之间物理连接和传送数据的接口与物理存储单元相对接。
165.计算机1000可以通过变换物理存储单元的物理状态以反映被存储的信息，从而在存储设备1018上存储数据。在本说明书的不同实施例中，物理状态的具体变换可以取决于各种因素。这种因素的示例可包括但不限于用于实现物理存储单元的技术、存储设备1018是被表征为主存储还是次存储，等等。
166.例如，计算机1000可以通过如下方式来将信息存储到存储设备1018：通过存储控制器1014发出指令以更改磁盘驱动单元内的特定位置的磁特性、光学存储单元中的特定位置的反射或折射特性、或者固态存储单元中的特定电容器、晶体管或者其他分立组件的电特性。在不偏离本说明书的范围和精神的情况下，物理介质的其他变换是可能的，提供前述示例只是为了方便本说明书。计算机1000可以通过检测物理存储单元内的一个或多个特定位置的物理状态或者特性，进一步从存储设备1018读取信息。
167.除了上述的大容量存储设备1018以外，计算机1000还可以访问其他计算机可读存储介质以存储和取回信息，例如程序模块、数据结构或者其他数据。本领域的技术人员应当明白，计算机可读存储介质是提供数据的非暂态存储并且可由计算机1000访问的任何可用介质。在一些示例中，由网络节点(例如，网络节点204)、源(例如，202)、目的地(例如，206)、收集器(例如，308)或者中央管理员(例如，312)执行的操作可以由与计算机1000类似的一个或多个设备支持。换句话说，由网络节点、收集器和/或中央管理员执行的操作中的一些或全部，可以由在基于云的布置中操作的一个或多个计算机设备1000执行。
168.作为示例，而不是限制，计算机可读存储介质可包括以任何方法或技术实现的易失性和非易失性、可移除和不可移除的介质。计算机可读存储介质包括但不限于ram、rom、可擦除可编程rom(erasable programmable rom，“eprom”)、电可擦除可编程rom(electrically-erasable programmable rom，“eeprom”)、闪存或者其他固态存储器技术、致密盘rom(compact disc rom，“cd-rom”)、数字多功能光盘(digital versatile disk，“dvd”)、高清晰度dvd(high definition dvd，“hd-dvd”)、blu-ray或者其他光学存储设备、盒式磁带、磁带、磁盘存储设备或者其他磁性存储设备、或者任何其他可用于以非暂态方式存储所需信息的介质。
169.如上文简要提及的，存储设备1018可以存储被利用来控制计算机1000的操作的操作系统1020。根据一个实施例，该操作系统包括linux操作系统。根据另一实施例，该操作系统包括来自华盛顿州雷德蒙的microsoft公司的server操作系统。根据另外的实施例，该操作系统可包括unix操作系统或者其变体之一。应当明白，也可以利用其他操作系统。存储设备1018可以存储由计算机1000利用的其他系统或者应用程序和数据。
170.在一个实施例中，存储设备1018或者其他计算机可读存储介质被编码有计算机可执行指令，这些指令在被加载到计算机1000中时，将计算机从通用计算系统变换为能够实
现本文描述的实施例的专用计算机。如上所述，这些计算机可执行指令通过指定cpu 1004如何在状态之间转变来变换计算机1000。根据一个实施例，计算机1000能够访问存储计算机可执行指令的计算机可读存储介质，这些指令在被计算机1000执行时，执行上文关于图1-图9描述的各种过程。计算机1000还可包括计算机可读存储介质，该介质上存储有用于执行本文描述的任何其他由计算机实现的操作的指令。
171.如图10中所示，存储设备1018存储路径签名更新器1024、路径变化识别器1026、以及流表1028。在一些实现方式中，路径签名更新器1024、路径变化识别器1026或者流表1028中的至少一者可以被省略。使用存储在路径签名更新器1024中的指令，(一个或多个)cpu 1004可以被配置为为正在穿越计算机1000的数据流中的个体数据封包生成和更新路径签名。使用存储在路径变化识别器1026中的指令，(一个或多个)cpu 1004可被配置为通过比较数据流内的不同数据封包的路径签名来识别数据流中是否发生了路径变化。流表1026可以存储与其数据封包正在穿越计算机1000的一个或多个数据流相关联的过去的一个或多个路径签名。
172.计算机1000还可包括一个或多个输入/输出控制器1016，用于接收和处理来自若干个输入设备的输入，例如键盘、鼠标、触摸板、触摸屏、电子手写笔、或者其他类型的输入设备。类似地，输入/输出控制器1016可以向显示器提供输出，例如计算机监视器、平板显示器、数字投影仪、打印机、或者其他类型的输出设备。将会明白，计算机1000可能不包括图10所示的所有组件，可包括图10中没有明确示出的其他组件，或者可能利用与图10所示完全不同的体系结构。
173.综上所述，本公开描述了与识别网络中的数据流的路径变化有关的各种方法、系统和设备。一种示例方法包括在一节点处接收包括第一路径签名的封包。该方法还包括通过将第一路径签名和一个或多个节点细节输入到散列函数中来生成第二路径签名。该方法包括在封包中用第二路径签名替换第一路径签名。包括第二路径签名的封包被节点转发。
174.在一些情况中，一个或多个组件在此可被称为“被配置为”、“可配置为”、“可操作/可操作来”、“适合于/可适合于”、“能够”、“可符合/符合”，等等。本领域技术人员将会认识到，除非上下文另有要求，否则这样的术语(例如，“被配置为”)一般可涵盖活跃状态组件和/或非活跃状态组件和/或待机状态组件。
175.就本文使用的而言，术语“基于”可与“至少部分基于”和“至少部分地基于”被同义地使用。
176.就本文使用的而言，术语“包括”和“包含”及其等同物可以被互换使用。“包括a、b和c”的装置、系统或方法包括a、b和c，但也可包括其他组件(例如，d)。也就是说，该装置、系统或方法不限于组件a、b和c。
177.虽然是针对具体示例来描述本发明的，但要理解，本发明的范围并不限于这些具体示例。由于为适应特定的操作要求和环境而进行的其他修改和变化对于本领域的技术人员而言是显而易见的，因此本发明不被认为限于为公开目的而选择的示例，并且覆盖了所有不构成偏离本发明的真正精神和范围的变化和修改。
178.虽然本技术描述了具有具体结构特征和/或方法动作的实施例，但要理解，权利要求书不一定限于所描述的具体特征或动作。更确切地说，具体特征和动作只是说明了属于本技术的权利要求的范围内的一些实施例。