Patent Description:
Data can be transmitted through a network from a source to a destination in the form of a unidirectional data flow. The data flow may include multiple data packets that are propagated through the network from the source to the destination. The order at which the data packets are transmitted from the source may be an order in which the data packets are supposed to be consumed by the destination. For instance, a content server may transmit a data packets in a video stream in an order corresponding to the progression of the video, such that packets corresponding to the beginning of the video are transmitted first and packets corresponding to the end of the video are transmitted later.

Various modem network topologies may include a variety of nodes by which information can be transmitted. Individual nodes in a network can be connected to more than two other nodes in the network. Due to node interconnectivity, there may be multiple paths through the network between any two endpoints. Individual nodes can select appropriate paths based on various conditions of the network. For instance, a node can select between multiple paths based on load balancing, connectivity, or the like.

However, if data packets in the same data flow are transmitted along different paths through the network, the data packets may arrive at the destination in a different order than they were intended to be consumed. For instance, one packet may be transmitted through a node with high latency and another packet may be transmitted through a node with lower latency. Out-of-Order (OoO) data packets can negatively impact Quality of Service (QoS) for end-users. To avoid OoO data packets in a data flow, there is a need to identify whether packets in a particular data flow travel through different paths in the network.

In-situ Operations, Administration, and Management (IOAM) provides mechanisms by which each node transferring a data packet through a network can add metadata to the data packet. In some cases, this metadata can be used to derive the path through which the data packet travels through the network. However, IOAM metadata can significantly increase the size of a given data packet. IOAM metadata may add a significant level of data (e.g., <NUM> bytes) to a given data packet at each hop through the network. The size of <NUM> AM metadata can be unacceptable in various networks, particularly when the data packet traverses a large number of nodes on its way to a destination. For instance, in various networks, nodes may lack the hardware required to support IOAM as well as to support transferring data packets with <NUM> AM metadata. Some alternatives to IOAM, such as In-Network Telemetry (INT), Inband Flow Analyzer (IFA), and In-situ Flow Information Telemetry (IFIT), suffer from similar deficiencies.

<CIT> discloses a method for segment routing using a remote forwarding adjacency identifier. <CIT> discloses techniques for exposing maximum node and/or link segment identifier depth using IS-IS. <CIT> discloses a communication system that includes a path management server that generates a plurality of forwarding path information items each including a sequence of identifiers, each of which identifies a communication interface provided in each of a plurality of forwarding nodes on a forwarding path in a data forwarding network or a link established between the forwarding node and a neighboring node thereof.

This disclosure describes various techniques for generating and utilizing in-situ path signatures for data flows traversing networks. A path signature is generated by a network node for a particular data packet in a data flow that is traversing the network node. The path signature represents a unique path that the data packet has traversed to arrive at the network node. When the network node identifies that different data packets in the same data flow have different path signatures, the network node can trigger an alert indicating that the packets in the data flow may be out-of-order and/or there may be a problem with the network resulting in the out-of-order packets. The network node may be a physical device, server, switch, or the like.

In various implementations, the techniques described herein may be performed by a system and/or device having non-transitory computer-readable media storing computer-executable instructions that, when executed by one or more processors, performs the methods described herein.

Various implementations of the present disclosure relate to identifying a path through which a data packet is transferred through a network. Particular implementations provide a path signature data field in the data packet, which can be modified by individual nodes through which the data packet is transferred.

In some implementations, a node may receive a data packet with an existing path signature. The node may input the existing path signature, as well as other information based on the node itself, into a hash function that may return a revised path signature. The node may replace the existing path signature with the revised path signature in the data packet before forwarding the data packet to another node in the network. The revised path signature may represent the unique path that the data packet has traversed up to the node itself.

In particular cases, a node or some other device may track path signatures corresponding to data packets in the same data flow. If the node identifies a change in path signatures in the data flow, the node may transmit an alert to a collector. The collector may diagnose a problem in the network based on the alert and/or other alerts corresponding to the data flow from other nodes in the network. In some cases, the path signature may be tracked as part of an existing NetFlow functionality.

Unlike IOAM metadata, the path signature data field can have a fixed size regardless of the number of nodes through which the data packet is transferred. For instance, the path signature data field can be limited to <NUM>- or <NUM>-bits. Because the path signature can have a relatively small size, the path signature can be readily implemented in existing network node hardware.

Various implementations described herein provide particular improvements to the field of computer networking. The path signature can enable in-situ network path tracking for individual data flows as the data flows are being transmitted through the network. Accordingly, problems within the network can be efficiently diagnosed in real-time.

Various implementations of the present disclosure will be described in detail with reference to the drawings, wherein like reference numerals present like parts and assemblies throughout the several views. Additionally, any samples set forth in this specification are not intended to be limiting and merely set forth some of the many possible implementations.

<FIG> illustrates an example environment <NUM> in which packets of a flow are transmitted through different paths. In <FIG>, data plane transmissions are depicted with solid arrows and control plane transmissions are depicted with dotted arrows.

As illustrated in <FIG>, a source <NUM> may transmit data to a destination <NUM> via a network <NUM>. The source <NUM> and the destination <NUM> may each be examples of nodes. As used herein, the terms "node," "network node," and their equivalents, can refer to any entity within a network that can transmit packets to and/or receive packets from at least one other node. A node may be a device, a software instance, a Virtual Machine (VM), or the like. In some examples, a node can be a client, a server, or a combination thereof. In some cases, a node can be an endpoint of a flow, such as the source <NUM> or the destination <NUM>. The source <NUM> may be, for example, a content server. The destination <NUM>, for example, may be a User Equipment (UE).

The source <NUM> may transmit the data in a flow that includes in-order packets <NUM>. As used herein, the terms "flow," "data flow," "traffic flow," "packet flow," and their equivalents, can refer to multiple packets transmitted from a source to a destination. In some examples, a flow may include packets that share at least one of the same ingress interface (e.g., SNMP ifIndex), source (e.g., from the same IP address), destination (e.g., directed to the same IP address), protocol (e.g., IP protocol), source port (e.g., for UDP or TCP), destination port (e.g., for UDP, TCP, or ICMP), or type of service (e.g., IP Type of Service (ToS)). As used herein, the terms "packet," "data packet," and their equivalents, can refer to a unit of data that is transmitted between two nodes. In various examples, a packet may have a header, which may include control data, and a payload, which may include user data. The header may include information such as an identifier of the source of the packet, an identifier of the destination of the packet, an indication of the type of user data in the payload, or the like. In some cases, a packet can be defined by a particular networking protocol, such as IP, TCP, UDP, or another networking protocol.

As used herein, the term "port," and its equivalents, can refer to a component of a node configured to connect the rest of the node to an interface. A node may have a fixed set of ports that can be selectively connected to particular interfaces. Each port of a node may have a unique identity, which may be represented by a port number. As used herein, the terms "ingress port," "entry port," and their equivalents, can refer to a port at which a packet enters a node. As used herein, the terms "egress port," "exit port," and their equivalents, can refer to a port at which a packet exits a node.

As illustrated in <FIG>, the in-order packets <NUM> are labeled and transmitted from the source <NUM> in the order of "A," "B," and "C. " The in-order packets <NUM> may consecutively reach a first node <NUM> in the network <NUM>. The first node <NUM> may forward the packets along different paths through the network <NUM>, including a first path <NUM>, a second path <NUM>, and a third path <NUM>. The first node <NUM> may forward the packets along the different paths based on various factors. For instance, the first node <NUM> may include a load balancer than may identify that the first path <NUM> is the most uncongested path when packet "A" is received but may identify that the second path <NUM> is the most uncongested path when packet "B" is received. In some cases, the first node <NUM> may identify that the second path <NUM> is connected when packet "B" is received, but is disconnected when packet "C" is received, and may therefore select the third path <NUM> for packet "C" rather than the second path <NUM>. In particular implementations, a problem with the network (e.g., a problem causing the congestion or disconnection) may cause the first node <NUM> to forward the packets along the different paths.

As used herein, the terms "path," "network path," and their equivalents, can refer to a specific sequence of nodes and/or interfaces over which a packet can traverse. A path may be defined between two nodes. In some cases, a path of a packet transmitted from a first node to a second node may be defined according to an identity of the first node, an identity of the second node, as well as any sequence of intermediary nodes and/or interfaces over which the packet travels from the first node to the second node.

As used herein, the term "interface," and its equivalents, can refer to a connection between two nodes in a network. In some cases, an interface may directly connect the two nodes and/or may omit any intermediary nodes. An interface may be connected to a first port of a first device and to a second port of a second device. In some cases, an interface between two nodes can be a wired interface, such that a packet can be transmitted as a signal conducted through a solid medium (e.g., an Ethernet cable, a fiber-optic cable, etc.) connecting the two nodes. In some examples, an interface between nodes can be a wireless interface, such that a packet can be transmitted as a signal through a fluid medium (e.g., air, water, etc.) connecting the two nodes. A wireless interface may be defined according to a type of wave used to carry the signal (e.g., a sound wave, an electromagnetic wave, etc.) and a frequency of the wave (e.g., an ultrasonic frequency, a radio frequency, an infrared frequency, etc.). An interface may be further defined according to a particular communication protocol, which may indicate how data transmitted over the interface is modulated. Some examples of communication protocols applicable to this application include TCP/IP, Wi-Fi, Bluetooth, or the like.

As illustrated in <FIG>, the first path <NUM>, the second path <NUM>, and the third path <NUM> may converge to a second node <NUM>, which may forward the packets to the destination <NUM>. However, due to the differences between the first path <NUM>, the second path <NUM>, and the third path <NUM>, the second node <NUM> may forward the packets as Out-of-Order (OoO) packets <NUM> to the destination <NUM>. Even though the in-order packets <NUM> were transmitted in the order of "A," "B," and "C," the OoO packets <NUM> are received at the destination <NUM> in the order of "C," "A,' and "B.

In various implementations, the first node <NUM> and the second node <NUM> may generate path signatures for the packets and amend the packets with the path signatures. As used herein, the terms "signature," "path signature," and their equivalents, can refer to a unique identifier of a path that a packet has traversed or is traversing. A path signature can be generated by a node, such as the first node <NUM> or the second node <NUM>, for a given packet based at least one of an identifier of the node <NUM> or <NUM>, an ingress port at which the packet is received by the node <NUM> or <NUM>, or an egress packet at which the packet is forwarded from the node <NUM> or <NUM>. The node <NUM> or <NUM> can further include the generated path signature in the given packet and forward the packet with the generated path signature toward the destination <NUM>.

In some cases, a revised path signature can be further generated based on a previous path signature. For example, the second node <NUM> may receive a given packet with a path signature generated from the first node <NUM>, and/or any intermediary nodes through which the packet has traveled between the first node <NUM> and the second node <NUM> and may use the previous path signature to generate a revised path signature for the given packet. Accordingly, in some implementations, the path signature of a packet can be revised recursively as the path travels through the network <NUM>.

According to various implementations of the present disclosure, the first node <NUM> and the second node <NUM> may identify that the packets are being transmitted over different paths through the network <NUM>. For instance, the first node <NUM> may forward the packets from different ports and may generate different path signatures for the different packets based on the different ports. The first node <NUM> may identify that the path signatures are different, and in response, may transmit an alert <NUM> to a collector <NUM> indicating that the flow is being transmitted along different paths through the network <NUM>. In some examples, the second node <NUM> may receive the packets in different ports and may generate different path signatures for the packets due to the different ports. In certain implementations, the second node <NUM> may receive the packets with different previous path signatures and may generate revised path signatures based on the different previous path signatures. The second node <NUM> may identify that the path signatures (e.g., generated, received, or revised) corresponding to the packets are different.

In response to identifying that the path signatures for the different packets in the flow are different, the first node <NUM> may generate and transmit an alert <NUM> to a collector <NUM>. Similarly, in response to identifying that the path signatures for the different packets in the flow are different, the second node <NUM> may generate and transmit an alert <NUM> to the collector <NUM>.

In some examples, the second node <NUM> may receive the packets with different path signatures due to the first path <NUM>, the second path <NUM>, and the third path <NUM>. The second node <NUM> may receive the packets at different ports and may generate different path signatures for the packets due to the different existing path signatures and/or the different ports at which the packets are received. The second node <NUM> may identify that the path signatures of the as-received packets are different, and/or that the path signatures of the as-transmitted packets are different, and in response, transmit an alert <NUM> to the collector <NUM> indicating that the flow is being transmitted along different paths through the network <NUM>.

In particular implementations, the collector <NUM> may identify that there is a problem with the network <NUM> based on the alerts <NUM> and <NUM>. In some cases, the collector <NUM> may identify that the alert <NUM> is received from an upstream node (i.e., the first node <NUM>) and that the alert <NUM> is received from a downstream node (i.e., the second node <NUM>). The collector <NUM> may therefore identify that the problem is associated with the first node <NUM>, rather than the second node <NUM>. Once the problem is identified, the problem can be resolved by an administrator of the network <NUM>.

<FIG> illustrates an example environment <NUM> in which a packet of a flow is transmitted through a first path in a network without the network generating an alert.

A source <NUM> may be transmitting the flow through a network including a node A <NUM>-A, node B <NUM>-B, node C <NUM>-C, and node D <NUM>-D. A destination <NUM> may receive the flow after it has been transmitted through the network. The network may have multiple layers of nodes. For instance, Node A <NUM>-A is in a first layer, Node B <NUM>-B and Node C <NUM>-C are in a second layer, and Node D <NUM>-D is in a third layer.

As illustrated in <FIG>, the flow includes a first packet <NUM>. As illustrated in <FIG>, the first packet <NUM> may be transmitted from the source <NUM> to Node A <NUM>-A. Node A <NUM>-A may generate a path signature for the first packet <NUM> and may forward the first packet <NUM> with the path signature to Node B <NUM>-B. In examples in which the first packet <NUM> includes a previous path signature when it is received by Node A <NUM>-A, Node A <NUM>-A may generate a new path signature based, at least in part, on the previous path signature. In instances in which the first packet <NUM> does not include a previous path signature, Node A <NUM>-A may rely on other factors to generate the path signature. In various implementations, Node A <NUM>-A may generate the path signature based on any of various factors associated with Node A <NUM>-A and/or how the first packet <NUM> is routed through Node A <NUM>-A. In various implementations, the first packet <NUM> can carry a path signature as metadata encapsulated in a header. For instance, the first packet <NUM> may carry the path signature encapsulated in an IP (e.g., IPv4 or IPv6) header of the first packet <NUM>, for example, in an IP option (e.g., IPv4), an extension header (e.g., IPv6), or the like. In some cases, the first packet <NUM> may include an Ethernet frame, and the path signature may be included in a payload of the Ethernet frame and may be identified by an EtherType field of the Ethernet frame. In some examples, the path signature can be included in the first packet <NUM> in at least one of a Network Service Header (NSH), a Geneve header, a Virtual Extensible Local Area Network (VXLAN)-Generic Protocol Extension (GPE) header, a Segment Routing over IPv6 (SRv6) header, a Multiprotocol Label Switching (MPLS) header, or the like. In some examples, the path signature can be encapsulated in at least one of IOAM, INT, IFA, or IFIT metadata.

In various implementations, Node A <NUM>-A may identify that the flow has not changed paths based on the path signature that Node A <NUM>-A has generated for the first packet <NUM>. In some cases, the first packet <NUM> may be the initial packet that Node A <NUM>-A has received in the flow. In some situations, the path signature that Node A <NUM>-A has generated for the first packet <NUM> may be the same as a path signature that Node A <NUM>-A has previously generated for a previous packet that Node A <NUM>-A has received and forwarded in the flow. Because Node A <NUM>-A has not identified a path change in the flow, Node A <NUM>-A may refrain from generating an alert associated with the flow.

The first packet <NUM> with the path signature generated by Node A <NUM>-A may be transmitted from Node A <NUM>-A to Node B <NUM>-B. In some cases, Node B <NUM>-B may forward the first packet <NUM> to Node D <NUM>-D without modifying or updating the path signature in the first packet <NUM>. However, in some implementations, Node B <NUM>-B may generate its own path signature for the first packet <NUM> and may forward the first packet <NUM> with the path signature to Node B <NUM>-B. Node B <NUM>-B may generate its new path signature iteratively based, at least in part, on the previous path signature generated by Node A <NUM>-A. In various implementations, Node B <NUM>-B may generate its new path signature based on any of various factors associated with Node B <NUM>-B and/or how the first packet <NUM> is routed through Node B <NUM>-B.

In various implementations, Node B <NUM>-B may identify that the flow has not changed paths based on the path signature that Node A <NUM>-A has generated for the first packet <NUM> and/or the path signature that Node B <NUM>-B has generated for the first packet <NUM>. In some cases, the first packet <NUM> may be the initial packet that Node B <NUM>-B has received in the flow. In some situations, the path signature that Node B <NUM>-B has generated for the first packet <NUM> may be the same as a path signature that Node B <NUM>-B has previously generated for a previous packet that Node B <NUM>-B has received (from Node A <NUM>-A) and forwarded in the flow. Because Node B <NUM>-B has not identified a path change in the flow, Node B <NUM>-B may refrain from generating an alert associated with the flow.

The first packet <NUM> with the path signature generated by Node A <NUM>-A or Node B <NUM>-B may be transmitted from Node B <NUM>-B to Node D <NUM>-D. In various implementations, Node D <NUM>-D may generate its own path signature for the first packet <NUM> and may forward the first packet <NUM> with the path signature to the destination <NUM>. Node D <NUM>-D may generate its new path signature iteratively based, at least in part, on the previous path signature in the first packet <NUM> as-received by Node D <NUM>-D, which may be the path signature generated by Node A <NUM>-A or Node B <NUM>-B. In various implementations, Node D <NUM>-D may generate its new path signature based on any of various factors associated with Node D <NUM>-D and/or how the first packet <NUM> is routed through Node D <NUM>-D.

In various implementations, Node D <NUM>-D may identify that the flow has not changed paths based on the path signature that Node D <NUM>-D has generated for the first packet <NUM>. In some cases, the first packet <NUM> may be the initial packet that Node D <NUM>-D has received in the flow. In some situations, the path signature that Node D <NUM>-D has generated for the first packet <NUM> may be the same as a path signature that Node D <NUM>-D has previously generated for a previous packet that Node D <NUM>-D has received (from Node A <NUM>-A and Node B <NUM>-B) and forwarded in the flow. Because Node D <NUM>-D has not identified a path change in the flow, Node D <NUM>-D may refrain from generating an alert associated with the flow.

<FIG> illustrates an example environment <NUM> in which a subsequent packet of the flow is transmitted through a second path in the network. The flow discussed with reference to <FIG> may be the same flow discussed above with respect to <FIG>.

As illustrated in <FIG>, the flow includes a second packet <NUM>. Like the first packet <NUM>, the second packet <NUM> may be transmitted from the source <NUM> to node A <NUM>-A. Node A <NUM>-A may generate a path signature for the second packet <NUM>. However, unlike the first packet <NUM>, Node A <NUM>-A may forward the second packet <NUM> with the path signature to Node C <NUM>-C. In examples in which the second packet <NUM> includes a previous path signature when it is received by Node A <NUM>-A, Node A <NUM>-A may generate a new path signature based, at least in part, on the previous path signature. In instances in which the second packet <NUM> does not include a previous path signature, Node A <NUM>-A may rely on other factors to generate the path signature. In various implementations, Node A <NUM>-A may generate the path signature based on any of various factors associated with Node A <NUM>-A and/or how the second packet <NUM> is routed through Node A <NUM>-A.

In various implementations in which Node A <NUM>-A generates the path signature of the second packet <NUM> based on how the second packet <NUM> is routed through Node A <NUM>-A, the path signature that Node A <NUM>-A generates for the second packet <NUM> may be different than the path signature that Node A <NUM>-A generates for the first packet <NUM>. Specifically, Node A <NUM>-A may generate the path signature for the first packet <NUM> based on routing the first packet <NUM> to Node B <NUM>-B and may generate the path signature for the second packet <NUM> based on routing the second packet <NUM> to Node C <NUM>-C. Based on the different path signatures generated for the first packet <NUM> and the second packet <NUM>, Node A <NUM>-A may identify that the flow has changed paths. In response to identifying the path change, Node A <NUM>-A may generate an alert <NUM> and transmit the alert <NUM> to a collector <NUM>. The alert <NUM> may identify the flow that has changed paths, a time at which the flow has changed paths, Node A <NUM>-A, or the like.

In various implementations, the second packet <NUM> can carry a path signature as metadata encapsulated in a header. For instance, the second packet <NUM> may carry the path signature encapsulated in an IP (e.g., IPv4 or IPv6) header of the first packet <NUM>, for example, in an IP option (e.g., IPv4), an extension header (e.g., IPv6), or the like. In some cases, the second packet <NUM> may include an Ethernet frame, and the path signature may be included in a payload of the Ethernet frame and may be identified by an EtherType field of the Ethernet frame. In some examples, the path signature can be included in the second packet <NUM> in at least one of a Network Service Header (NSH), a Geneve header, a Virtual Extensible Local Area Network (VXLAN)-Generic Protocol Extension (GPE) header, a Segment Routing over IPv6 (SRv6) header, a Multiprotocol Label Switching (MPLS) header, or the like. In some examples, the path signature can be encapsulated in at least one of IOAM, INT, IFA, or IFIT metadata.

The second packet <NUM> with the path signature generated by Node A <NUM>-A may be transmitted from Node A <NUM>-A to Node C <NUM>-C. In some cases, Node C <NUM>-C may forward the second packet <NUM> to Node D <NUM>-D without modifying or updating the path signature in the second packet <NUM>. However, in some implementations, Node C <NUM>-C may generate its own path signature for the second packet <NUM> and may forward the second packet <NUM> with the path signature to Node D <NUM>-D. Node C <NUM>-C may generate its new path signature iteratively based, at least in part, on the previous path signature generated by Node A <NUM>-A. In various implementations, Node C <NUM>-C may generate its new path signature based on any of various factors associated with Node C <NUM>-C and/or how the second packet <NUM> is routed through Node C <NUM>-C.

In various implementations, Node C <NUM>-C may not identify that the flow has changed paths. For instance, the second packet <NUM> may be the first packet that Node C <NUM>-C has received in the flow. Because Node C <NUM>-C has not identified a path change in the flow, Node C <NUM>-C may refrain from generating an alert associated with the flow.

The second packet <NUM> with the path signature generated by Node A <NUM>-A or Node C <NUM>-C may be transmitted from Node C <NUM>-C to Node D <NUM>-D. In various implementations, Node C <NUM>-C may generate its own path signature for the second packet <NUM> and may forward the second packet <NUM> with the path signature to the destination <NUM>. Node D <NUM>-D may generate its new path signature iteratively based, at least in part, on the previous path signature in the second packet <NUM> as-received by Node D <NUM>-D, which may be the path signature generated by Node A <NUM>-A or Node C <NUM>-C. In various implementations, Node D <NUM>-D may generate its new path signature based on any of various factors associated with Node D <NUM>-D and/or how the second packet <NUM> is routed through Node D <NUM>-D. In various examples, the path signature generated by Node D <NUM>-D for the second packet <NUM> may be different than the path signature generated by Node D <NUM>-D for the first packet <NUM>.

In various implementations, Node D <NUM>-D may identify that the flow has changed paths based on the path signature that Node D <NUM>-D has generated for the first packet <NUM> and the path signature that Node D <NUM>-D has generated for the second packet <NUM>. In response to identifying the path change, Node D <NUM>-D may transmit an alert <NUM> to the collector <NUM>. The alert <NUM> may identify the flow that has changed paths, a time at which the flow has changed paths, Node D <NUM>-D, or the like.

The collector <NUM> may identify a problem with the network based on the alert <NUM> from Node A <NUM>-A and the alert <NUM> from Node D <NUM>-D. In some cases, the collector <NUM> may assume that any problem with a network causing a change in path signatures will result in a change in path signatures along all nodes downstream of the problem. Accordingly, despite receiving the alerts <NUM> and <NUM> from both Node A <NUM>-A and Node D <NUM>-D, the collector <NUM> may identify that the problem with the network is associated with Node A <NUM>-A, rather than Node D <NUM>-D.

In response to identifying the problem with the network, the collector <NUM> may transmit a report <NUM> to a central administrator <NUM>. The report <NUM> may identify information about the problem, such as the node (e.g., Node A <NUM>-A) associated with the problem, a time at which the problem is identified, or the like. The central administrator <NUM> may initiate a process by which the problem can be resolved.

<FIG> illustrates an example environment <NUM> of a node forwarding the first packet of the flow with a path signature. In particular, <FIG> illustrates an example of Node A <NUM>-A forwarding the first packet <NUM>.

As shown in <FIG>, Node A <NUM>-A receives the first packet <NUM>. In <FIG>, Node A <NUM>-A may receive the first packet <NUM> without a path signature. Node A <NUM>-A receives the first packet <NUM> at a first ingress port <NUM>-<NUM>. In particular implementations, Node A <NUM>-A includes multiple ingress ports, such as the first ingress port <NUM>-<NUM> and the second ingress port <NUM>-<NUM>. Each one of the ingress ports in Node A <NUM>-A (i.e., each of the first ingress port <NUM>-<NUM> and the second ingress port <NUM>-<NUM>) may be associated with a unique identifier that distinguishes the ingress port from the other ingress ports in Node A <NUM>-A. A port number is one example of an identifier of an ingress port.

In the example illustrated in <FIG>, a path signature updater <NUM> intercepts the first packet <NUM>. The path signature updater <NUM>, or some other component of Node A <NUM>-A, selects an appropriate egress port among a first egress port <NUM>-<NUM> and a second egress port <NUM>-<NUM>. Each one of the egress ports in Node A <NUM>-A (i.e., each of the first egress port <NUM>-<NUM> and the second egress port <NUM>-<NUM>) may be associated with a unique identifier that distinguishes the egress port from the other egress ports in Node A <NUM>-A. A port number is one example of an identifier of an egress port. In the example of <FIG>, the first egress port <NUM>-<NUM> has been selected.

Based on various information, such as at least one of an identifier of the first ingress port <NUM>-<NUM> at which the first packet <NUM> is received, an identifier of the first egress port <NUM>-<NUM> at which the first packet <NUM> will be forwarded, an identifier of Node A <NUM>-A itself, or the like, the path signature updater <NUM> generates a first path signature <NUM> for the first packet <NUM>. An example of an identifier of Node A <NUM>-A can include a unique identification number associated with Node A <NUM>-A.

In particular implementations, the path signature updater <NUM> uses a hash function to generate the first path signature <NUM>. The hash function may return a unique value in response to a unique input. Accordingly, as long as the input to the hash function is indicative of the unique path of a particular packet through a network, the hash function will return a value unique to the path. In some examples, the hash function used by the path signature updater <NUM> is a cryptographic hash function, an XOR function, CRC32, or the like. For instance, in various device-centric implementations, the path signature updater <NUM> can use the following Formula <NUM> to generate the first path signature <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, Pi is the identifier of an ingress port (e.g., the first ingress port <NUM>-<NUM>) at which the packet (e.g., the first packet <NUM>) is received, Pe is the identifier of the egress port (e.g., the first egress port <NUM>-<NUM>) from which the packet is forwarded, and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A). According to some examples, the path signature updater <NUM> may use the following Formula <NUM> to generate the first path signature <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, Pe is the identifier of the egress port (e.g., the first egress port <NUM>-<NUM>) from which the packet (e.g., the first packet <NUM>) is forwarded, and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A). In some lightweight implementations, the path signature updater <NUM> uses the following Formula <NUM> to generate the second path signature <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A).

In particular flow-centric implementations, the path signature updater <NUM> can use the following Formula <NUM> to generate a unique identifier of a flow: <MAT> wherein f is the identifier of the flow, Hash() is a hash function, IS is an identifier of a source of the flow (e.g., an IP address of the source of data packets in the flow), ID is an identifier of a destination of the flow (e.g., an IP address of the destination of data packets in the flow), PS is an identifier of a port of the source (e.g., a port number), PD is an identifier of a port of the destination (e.g., a port number), and Pro is an identifier of the protocol associated with the flow (e.g., a protocol indicating the type of data transferred in the flow). In some cases, various elements of the hash function of Formula <NUM> can be omitted. For instance, a <NUM>-tuple hash function utilizing IS, ID, and Pro as inputs could be used to uniquely identify the flow.

In various cases, the path signature updater <NUM> can use the identifier of the flow calculated in Formula <NUM> to generate the path signature using the following Formula <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, Pi is the identifier of an ingress port (e.g., the first ingress port <NUM>-<NUM>) at which the packet (e.g., the first packet <NUM>) is received, Pe is the identifier of the egress port (e.g., the first egress port <NUM>-<NUM>) from which the packet is forwarded, f is the identifier of the flow (e.g., generated using Formula <NUM>), and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A). According to some examples, the path signature updater <NUM> may use the following Formula <NUM> to generate the first path signature <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, Pe is the identifier of the egress port (e.g., the first egress port <NUM>-<NUM>) from which the packet (e.g., the first packet <NUM>) is forwarded, f is the identifier of the flow (e.g., generated using Formula <NUM>), and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A). In some lightweight implementations, the path signature updater <NUM> uses the following Formula <NUM> to generate the second path signature <NUM>: <MAT> wherein S<NUM> is the path signature (e.g., the first path signature <NUM> generated by Node A <NUM>-A), Hash() is a hash function, f is the identifier of the flow (e.g., generated using Formula <NUM>), and N<NUM> is the identifier of the node (e.g., Node A <NUM>-A).

Regardless of the formula used by the path signature updater <NUM>, the first path signature <NUM> may uniquely represent the path of the first packet <NUM> through Node A <NUM>-A. In examples in which the path signature updater <NUM> utilizes Formula <NUM>, <NUM>, <NUM>, or <NUM>, the first path signature <NUM> may further identify a path including Node B <NUM>-B, to which the first packet <NUM> is forwarded using the first egress port <NUM>-<NUM>.

The path signature updater <NUM> add the first path signature <NUM> to the first packet <NUM>. In some examples, the path signature updater <NUM> adds the first path signature <NUM> to a header of the first packet <NUM>. For instance, the path signature updater <NUM> may insert a Path Signature field into the first packet <NUM> and populate the Path Signature field with the first path signature <NUM>. In some cases, the Path Signature field is included in a header field (e.g., an IP header, an IPv4 option, an IPv6 extension header, an NSH header, a Geneve header, a VXLAN-GPE header, an SRv6 header, or an MPLS header) and/or included in a payload (e.g., as identified by an EtherType). In some examples, the Path Signature field is included in at least one of IOAM, INT, IFA, or IFIT metadata. According to particular implementations, the Path Signature field has a fixed size. For instance, the Path Signature field has a fixed size of <NUM> bits, <NUM> bits, or the like. Accordingly, in various implementations, every path signature generated by the path signature updater <NUM> (e.g., the first path signature <NUM>) will have the same fixed size as the Path Signature field.

The path signature updater <NUM> may further forward the first packet <NUM>, with the first path signature <NUM>, through the first egress port <NUM>-<NUM>. The first egress port <NUM>-<NUM> may be connected to an interface connected to another node in the same network as Node A <NUM>-A. For instance, as illustrated in <FIG>, the first packet <NUM> can be forwarded to Node B <NUM>-B from the first egress port <NUM>-<NUM>.

As illustrated in <FIG>, the path signature updater <NUM> further stores the first path signature <NUM> in a flow table <NUM>. In some cases, the flow table <NUM> includes multiple entries corresponding to different packets received and forwarded by Node A <NUM>-A. For instance, the flow table <NUM> may include an entry corresponding to the first packet <NUM> that includes the first path signature <NUM>. In some cases, the entries also identify the flows of the different packets received and forwarded by Node A <NUM>-A. For example, the entry corresponding to the first packet <NUM> may also include information identifying the flow that includes the first packet <NUM>.

Node A <NUM>-A further includes a path change identifier <NUM>, in various implementations. The path change identifier <NUM> may be configured to access the flow table <NUM> in order to determine whether packets in a particular flow have different paths. In some examples, the path change identifier <NUM> may determine that the first path signature <NUM> corresponds to the initial path signature generated by the path signature updater <NUM> for the flow and may therefore assume that no path change has occurred for the flow. In some instances, the path change identifier <NUM> may determine that the first path signature <NUM> matches a previous path signature generated by the path signature updater <NUM> for the flow and may therefore assume that no path change has occurred for the flow. When the path change identifier <NUM> determines that no path change has occurred, the path change identifier <NUM> may refrain from generating an alert.

<FIG> illustrates an example environment <NUM> of a node forwarding another packet of the flow with a path signature. In particular, <FIG> illustrates an example of Node A <NUM>-A forwarding the second packet <NUM>.

As shown in <FIG>, Node A <NUM>-A receives the second packet <NUM> without a path signature. Node A <NUM>-A receives the second packet <NUM> at the first ingress port <NUM>-<NUM>. The path signature updater <NUM> intercepts the second packet <NUM>.

The path signature updater <NUM>, or some other component of Node A <NUM>-A, can select an appropriate egress port among a first egress port <NUM>-<NUM> and a second egress port <NUM>-<NUM> for the second packet <NUM>. However, Node A <NUM>-A may select the second egress port <NUM>-<NUM> for the second packet <NUM>, in contrast to the first egress port <NUM>-<NUM> selected for the first packet <NUM>. Node A <NUM>-A may select the second egress port <NUM>-<NUM> for any of a variety of reasons. For instance, Node A <NUM>-A may identify that the interface connected to the first egress port <NUM>-<NUM>, or the node connected to the interface (i.e., Node B <NUM>-B) has been disconnected since the first packet <NUM> was forwarded. In some examples, Node A <NUM>-A may include a load balancer that identifies that a load associated with the first egress port <NUM>-<NUM> exceeds a load associated with the second egress port <NUM>-<NUM>. For instance, the node connected to the first egress port <NUM>-<NUM> (i.e., Node B <NUM>-B) may be more congested and/or associated with a higher latency than the node connected to the second egress port <NUM>-<NUM> (i.e., Node C <NUM>-C).

Based on various information, such as at least one of an identifier of the first ingress port <NUM>-<NUM> at which the second packet <NUM> is received, an identifier of the second egress port <NUM>-<NUM> at which the second packet <NUM> will be forwarded, an identifier of Node A <NUM>-A itself, or the like, the path signature updater <NUM> generates a second path signature <NUM> for the second packet <NUM>.

In particular implementations, the path signature updater <NUM> uses one of Formulas <NUM>, <NUM>, <NUM>, or <NUM> to generate the first path signature <NUM> and the second path signature <NUM>. Accordingly, the first path signature <NUM> may be generated based on the identifier of the first egress port <NUM>-<NUM> and the second path signature <NUM> may be generated based on the identifier of the second egress port <NUM>-<NUM>. For at least this reason, the second path signature <NUM> may be different than the first path signature <NUM>.

The path signature updater <NUM> add the second path signature <NUM> to the second packet <NUM>. In some examples, the path signature updater <NUM> adds the second path signature <NUM> to a header of the second packet <NUM>. For instance, the path signature updater <NUM> may insert a Path Signature field into the second packet <NUM> and populate the Path Signature field with the second path signature <NUM>. In some cases, the second path signature <NUM> may have the same size as the first path signature <NUM>.

The path signature updater <NUM> may further forward the second packet <NUM>, with the second path signature <NUM>, through the second egress port <NUM>-<NUM>. The second egress port <NUM>-<NUM> may be connected to an interface connected to another node in the same network as Node A <NUM>-A. For instance, as illustrated in <FIG>, the second packet <NUM> can be forwarded to Node C <NUM>-C from the second egress port <NUM>-<NUM>.

As illustrated in <FIG>, the path signature updater <NUM> further stores the second path signature <NUM> in the flow table <NUM>. In some cases, the flow table <NUM> may already have stored a first entry corresponding to the first packet <NUM> that includes the first path signature <NUM>. The flow table may further store a second entry corresponding to the second packet <NUM> that includes the second path signature <NUM>. In some cases, the first and second entries corresponding to the first packet <NUM> and the second packet <NUM> may also include information identifying the flow that includes the first packet <NUM> and the second packet <NUM>.

The path change identifier <NUM> may determine that the second path signature <NUM> stored in the second entry of the flow table <NUM>, is different than the first path signature <NUM>, which is stored in the first entry of the flow table <NUM>. Based on this difference, the path change identifier <NUM> may determine that there is a path change in the flow. In some cases, the path change identifier <NUM> may determine that greater than a threshold number of packets with the first path signature <NUM> and/or greater than the threshold number of packets with the second path signature <NUM> have been received, and in response, identify that there is a persistent path change in the flow. In response to determining that there is the path change, the path change identifier <NUM> may generate and transmit the alert <NUM> from Node A <NUM>-A. The alert <NUM> may indicate the path change in the flow. As illustrated in the example of <FIG>, the alert <NUM> includes a flow identifier <NUM>. The flow identifier <NUM> may indicate the flow including the first packet <NUM> and the second packet <NUM>. For instance, the flow identifier <NUM> may include at least one element of a <NUM>-tuple associated with the flow, such as a source (e.g., from the same IP address), destination (e.g., directed to the same IP address), protocol (e.g., IP protocol), source port (e.g., for UDP or TCP), destination port (e.g., for UDP, TCP, or ICMP), or type of service (e.g., IP Type of Service (ToS)) of the first packet <NUM> and the second packet <NUM>. In examples in which the alert <NUM> is transmitted to a collector (e.g., the collector <NUM>), the flow identifier <NUM> may be used to identify a problem in the network that has led to the path change.

<FIG> illustrates an example environment <NUM> of a node forwarding the first packet of the flow with a path signature. In particular, <FIG> illustrates an example of Node D <NUM>-D forwarding the first packet <NUM>.

As shown in <FIG>, Node D <NUM>-D receives the first packet <NUM> with a third path signature <NUM>. In some implementations, in which no node between Node A <NUM>-A and Node D <NUM>-D in the path of the first packet <NUM> has changed or updated the Path Signature field in the first packet <NUM>, the third path signature <NUM> may be the first path signature <NUM> generated by Node A <NUM>-A. In certain implementations in which the Path Signature field has been updated between Node A <NUM>-A and Node D <NUM>-D, the third path signature <NUM> may be based on the first path signature <NUM> generated by Node A <NUM>-A for the first packet <NUM>.

Node D <NUM>-D may receive the first packet <NUM> with the third path signature <NUM> at a first ingress port <NUM>-<NUM>, which may be connected to another node in the same network as Node D <NUM>-D (i.e., Node B <NUM>-B). In particular implementations, Node D <NUM>-D includes multiple ingress ports, such as the first ingress port <NUM>-<NUM> and the second ingress port <NUM>-<NUM>. Each one of the ingress ports in Node D <NUM>-D (i.e., each of the first ingress port <NUM>-<NUM> and the second ingress port <NUM>-<NUM>) may be associated with a unique identifier that distinguishes the ingress port from the other ingress ports in Node D <NUM>-D.

In the example illustrated in <FIG>, a path signature updater <NUM> intercepts the first packet <NUM>. The path signature updater <NUM>, or some other component of Node D <NUM>-D, selects an appropriate egress port among a first egress port <NUM>-<NUM> and a second egress port <NUM>-<NUM>. Each one of the egress ports in Node D <NUM>-D (i.e., each of the first egress port <NUM>-<NUM> and the second egress port <NUM>-<NUM>) may be associated with a unique identifier that distinguishes the egress port from the other egress ports in Node A <NUM>-A. In the example of <FIG>, the first egress port <NUM>-<NUM> has been selected.

Based on various information, such as at least one of an identifier of the first ingress port <NUM>-<NUM> at which the first packet <NUM> is received, an identifier of the first egress port <NUM>-<NUM> at which the first packet <NUM> will be forwarded, an identifier of Node D <NUM>-D itself, or the like, the path signature updater <NUM> generates a fourth path signature <NUM> for the first packet <NUM>. Further, the path signature updater <NUM> may generate the fourth path signature <NUM> using a recursive function that is based, at least in part, on the third path signature <NUM> in the first packet <NUM> as-received by Node D <NUM>-D.

In particular implementations, the path signature updater <NUM> uses a hash function to generate the fourth path signature <NUM> based on the third path signature <NUM>. The hash function may return a unique value in response to a unique input. Accordingly, as long as the input to the hash function is indicative of the unique path of a particular packet through a network, the hash function will return a value unique to the path. In some examples, the hash function used by the path signature updater <NUM> is a cryptographic hash function, an XOR function, CRC32, or the like. In particular implementations, the hash function utilized by the path signature updater <NUM> in Node D <NUM>-D may be different than the hash function utilized by the path signature updater <NUM> in Node A <NUM>-A. In some instances, the path signature updater <NUM> can use the following Formula <NUM> to generate the fourth path signature <NUM>: <MAT> wherein Sn is the new path signature (e.g., the fourth path signature <NUM>), Hash() is a hash function, Sn is the previous path signature (e.g., the third path signature <NUM>), Pi is the identifier of the ingress port at which the first packet (e.g., the identifier of the first ingress port <NUM>-<NUM>), Pe is the identifier of the egress port at which the packet is forwarded (e.g., the identifier of the first egress port <NUM>-<NUM>), and N<NUM> is the identifier of the node (e.g., the identifier of Node D <NUM>-D). According to some examples, the path signature updater <NUM> may use the following Formula <NUM> to generate the fourth path signature <NUM>: <MAT> wherein Sn is the new path signature (e.g., the fourth path signature <NUM>), Hash() is a hash function, Sn is the previous path signature (e.g., the third path signature <NUM>), Pi is the identifier of the ingress port at which the first packet (e.g., the identifier of the first ingress port <NUM>-<NUM>), and N<NUM> is the identifier of the node (e.g., the identifier of Node D <NUM>-D). According to some examples, the path signature updater <NUM> may use the following Formula <NUM> to generate the fourth path signature <NUM>: <MAT> wherein Sn is the new path signature (e.g., the fourth path signature <NUM>), Hash() is a hash function, Sn is the previous path signature (e.g., the third path signature <NUM>), and N<NUM> is the identifier of the node (e.g., the identifier of Node D <NUM>-D).

Regardless of the formula used by the path signature updater <NUM>, the fourth path signature <NUM> may uniquely represent the path of the first packet <NUM> from the source of the first packet <NUM> to Node D <NUM>-D.

The path signature updater <NUM> may replace the third path signature <NUM> with the fourth path signature <NUM> in the first packet <NUM>. In some examples, the path signature updater <NUM> deletes the third path signature <NUM> and adds the fourth path signature <NUM> to a header of the first packet <NUM>. For instance, the path signature updater <NUM> may delete the third path signature <NUM> from a Path Signature field into the first packet <NUM> and populate the Path Signature field with the fourth path signature <NUM>. In some cases, the Path Signature field is included in a header field (e.g., an IP header, an IPv4 option, an IPv6 extension header, an NSH header, a Geneve header, a VXLAN-GPE header, an SRv6 header, or an MPLS header) and/or included in a payload (e.g., as identified by an EtherType). In some examples, the Path Signature field is included in at least one of IOAM, INT, IFA, or IFIT metadata. According to particular implementations, the Path Signature field has a fixed size. For instance, the Path Signature field has a fixed size of <NUM> bits, <NUM> bits, or the like. Accordingly, the fourth path signature <NUM> may have the same size as the third path signature <NUM>. In various implementations, every path signature generated by the path signature updater <NUM> (e.g., the fourth path signature <NUM>) will have the same fixed size as the Path Signature field in the first packet <NUM>.

The path signature updater <NUM> may further forward the first packet <NUM>, with the fourth path signature <NUM>, through the first egress port <NUM>-<NUM>. The first egress port <NUM>-<NUM> may be connected to an interface connected to another node. For instance, as illustrated in <FIG>, the first packet <NUM> can be forwarded to the destination <NUM> from the first egress port <NUM>-<NUM>.

As illustrated in <FIG>, the path signature updater <NUM> further stores the fourth path signature <NUM> in a flow table <NUM>. In some cases, the flow table <NUM> includes multiple entries corresponding to different packets received and forwarded by Node D <NUM>-D. For instance, the flow table <NUM> may include an entry corresponding to the first packet <NUM> that includes the fourth path signature <NUM>. In some cases, the entry may further include the third path signature <NUM>. In particular implementations, the entries also identify the flows of the different packets received and forwarded by Node D <NUM>-D. For example, the entry in the flow table <NUM> corresponding to the first packet <NUM> may also include information identifying the flow that includes the first packet <NUM>.

Node D <NUM>-D further includes a path change identifier <NUM>, in various implementations. The path change identifier <NUM> may be configured to access the flow table <NUM> in order to determine whether packets in a particular flow have different paths. In some examples, the path change identifier <NUM> may determine that the fourth path signature <NUM> corresponds to the initial path signature generated by the path signature updater <NUM> for the flow and may therefore assume that no path change has occurred for the flow. In some instances, the path change identifier <NUM> may determine that the fourth path signature <NUM> matches a previous path signature generated by the path signature updater <NUM> for the flow and may therefore assume that no path change has occurred for the flow. When the path change identifier <NUM> determines that no path change has occurred, the path change identifier <NUM> may refrain from generating an alert.

<FIG> illustrates an example environment <NUM> of a node forwarding another packet of the flow with a path signature. In particular, <FIG> illustrates an example of Node D <NUM>-D forwarding the second packet <NUM>.

As shown in <FIG>, Node D <NUM>-D receives the second packet <NUM> with a fifth path signature <NUM>. In some implementations, in which no node between Node A <NUM>-A and Node D <NUM>-D in the path of the second packet <NUM> has changed or updated the Path Signature field in the second packet <NUM>, the fifth path signature <NUM> may be the second path signature <NUM> generated by Node A <NUM>-A. In certain implementations in which the Path Signature field has been updated between Node A <NUM>-A and Node D <NUM>-D, the fifth path signature <NUM> may be based on the second path signature <NUM> generated by Node A <NUM>-A for the first packet <NUM>.

Node D <NUM>-D receives the second packet <NUM> at the second ingress port <NUM>-<NUM>, rather than the first ingress port <NUM>-<NUM> at which the first packet <NUM> was received. This indicates that the second packet <NUM> has traveled a different path before arriving at Node D <NUM>-D than a path traveled by the first packet <NUM>. The path signature updater <NUM> intercepts the second packet <NUM>. Node D <NUM>-D may further select the first egress port <NUM>-<NUM> from which to forward the second packet <NUM> toward its destination.

Based on various information, such as at least one of an identifier of the second ingress port <NUM>-<NUM> at which the second packet <NUM> is received, an identifier of the first egress port <NUM>-<NUM> at which the second packet <NUM> will be forwarded, an identifier of Node D <NUM>-D itself, or the like, the path signature updater <NUM> generates a sixth path signature <NUM> for the second packet <NUM>.

In various implementations, the path signature updater <NUM> may generate the sixth path signature <NUM> based on the previous, fifth path signature <NUM> in the as-received second packet <NUM>. In some examples, the path signature updater <NUM> uses at least one of Formulas <NUM>-<NUM> to generate the fourth path signature <NUM> and the sixth path signature <NUM>. Based at least in part on a difference between the third path signature <NUM> and the fifth path signature <NUM>, and/or a difference between the first ingress port <NUM>-<NUM> at which the first packet <NUM> is received and the second ingress port <NUM>-<NUM> at which the second packet <NUM> is received, the sixth path signature <NUM> may be different than the third path signature <NUM>.

The path signature updater <NUM> may replace the fifth path signature <NUM> with the sixth path signature <NUM> in the second packet <NUM>. In some examples, the path signature updater <NUM> deletes the fifth path signature <NUM> and adds the sixth path signature <NUM> to a header of the second packet <NUM>. For instance, the path signature updater <NUM> may delete the fifth path signature <NUM> from a Path Signature field into the second packet <NUM> and populate the Path Signature field with the sixth path signature <NUM>. In some cases, the Path Signature field is included in a header field (e.g., an IP header, an IPv4 option, an IPv6 extension header, an NSH header, a Geneve header, a VXLAN-GPE header, an SRv6 header, or an MPLS header) and/or included in a payload (e.g., as identified by an EtherType). In some examples, the Path Signature field is included in at least one of IOAM, INT, IFA, or IFIT metadata. The Path Signature field may have a fixed size. Accordingly, the sixth path signature <NUM> may have the same size as the fifth path signature <NUM>. The path signature updater <NUM> may further forward the second packet <NUM>, with the sixth path signature <NUM>, through the first egress port <NUM>-<NUM>.

As illustrated in <FIG>, the path signature updater <NUM> further stores the sixth path signature <NUM> in the flow table <NUM>. In some cases, the flow table <NUM> may already have stored a first entry corresponding to the first packet <NUM> that includes the fourth path signature <NUM>. In some cases, the first entry may also include the third path signature <NUM>. The flow table <NUM> may further store a second entry corresponding to the second packet <NUM> that includes the sixth path signature <NUM>. The second entry may also include the fifth path signature <NUM>, in some example. In some cases, the first and second entries corresponding to the first packet <NUM> and the second packet <NUM> may also include information identifying the flow that includes the first packet <NUM> and the second packet <NUM>.

The path change identifier <NUM> may determine that the sixth path signature <NUM> stored in the second entry of the flow table <NUM>, is different than the fourth path signature <NUM>, which is stored in the first entry of the flow table <NUM>. Based on this difference, the path change identifier <NUM> may determine that there is a path change in the flow. In response to determining that there is the path change, the path change identifier <NUM> may generate and transmit the alert <NUM> from Node D <NUM>-D. The alert <NUM> may indicate the path change in the flow. As illustrated in the example of <FIG>, the alert <NUM> includes the flow identifier <NUM>. In examples in which the alert <NUM> is transmitted to a collector (e.g., the collector <NUM>), the flow identifier <NUM> may be used to identify a problem in the network that has led to the path change.

<FIG> illustrates an example of a flow table <NUM> with various entries corresponding to different flows through a particular node. In some examples, the flow table <NUM> can be used as the flow table <NUM> described above with reference to <FIG> and <FIG> or the flow table <NUM> described above with reference to <FIG> and <FIG>. In various implementations, the flow table <NUM> may be managed by a node receiving and forwarding multiple packets in multiple flows.

The flow table <NUM> includes multiple entries. Each one of the entries includes multiple fields. As illustrated in <FIG>, the fields include an entry number, a flow identifier, a count, a last packet time, and a path signature. In various implementations, the entries can include fewer or additional fields.

In some cases, the flow table <NUM> includes a fixed number of entries associated with a fixed number of flow identifiers. The fixed number may be an integer that is greater than <NUM>. As illustrated in <FIG>, the flow table <NUM> includes ten entries (entry #<NUM> - #<NUM>). The entries stored in the flow table <NUM> can correspond to ten flows whose packets have been recently received and forwarded by the node. If more than ten flows include packets that are received and forwarded by the node, only the ten entries corresponding to the ten most recent flows may be stored in the flow table <NUM>. Accordingly, the size of the flow table <NUM> can be restricted to conserve memory resources at the node.

The flow identifier field of an entry corresponding to a packet may indicate the flow corresponding to the entry. In some cases, the flow identifier field can include at least one of an ingress interface (e.g., SNMP ifIndex), source (e.g., from the same IP address), destination (e.g., directed to the same IP address), protocol (e.g., IP protocol), source port (e.g., for UDP or TCP), destination port (e.g., for UDP, TCP, or ICMP), or type of service (e.g., IP Type of Service (ToS)) associated with the flow. In certain implementations, the flow identifier field can be a string that can be used to identify the flow.

The count field of an entry corresponding to a flow may correspond to the number of packets received and/or forwarded in the flow by the node. In some cases, the count field may correspond to the number of packets of the flow that have been received and/or forwarded with a particular signature without the flow having experienced a path change. For example, "Count <NUM>" may correspond to the number of packets received by the node with "Flow Identifier <NUM>. " In some cases, "Count <NUM>" may correspond to the number of packets with "Signature <NUM>" that have been received since either the beginning of the flow, or the last path change of the flow.

The time field of an entry corresponding to a flow may indicate a time at which the most recent packet of the flow is received by the node, a time at which the most recent packet of the flow is forwarded by the node, or a combination thereof.

The path signature field of an entry corresponding to a flow may include the path signature generated by the node for a packet of that flow. In some cases, the path signature field may further include a previous path signature that was received by the node for that flow.

In particular implementations, the path signature field can be used to identify whether the flow is associated with a path change. For instance, in the example illustrated in <FIG>, "Signature <NUM>," corresponding to "Flow Identifier <NUM>," may be set as "Signature A. " When the node receives a packet corresponding to "Flow Identifier <NUM>" that includes a signature different than "Signature A, the node may identify a path change in the flow with "Flow Identifier <NUM>. " Accordingly, the node may generate and transmit an alert corresponding to "Flow Identifier <NUM>.

<FIG> illustrates an example of a flow table <NUM> illustrating a path change in a particular data flow. For instance, the flow table <NUM> can correspond to "Entry #<NUM>" in the flow table <NUM> described above with reference to <FIG>.

As illustrated, the flow table <NUM> can correspond to a single flow identifier, such as "Flow Identifier <NUM>. " The flow table <NUM> can track individual packets received and/or forwarded by the node in the flow that correspond to "Flow Identifier <NUM>. " In some cases, the flow table <NUM> may track a predetermined number of the most recent packets corresponding to "Flow Identifier <NUM>," such as the most recent ten packets received and/or forwarded in the flow corresponding to "Flow Identifier <NUM>.

Each of the individual packets may have its own timestamp (e.g., one of "Timestamp A" to "Timestamp J"). In some cases, a given timestamp may correspond to a time at which the individual packet was received by the node and/or a time at which the node forwarded the individual packet in the flow. With reference to <FIG>, "Timestamp <NUM>" can be the most recent one of "Timestamp A" to "Timestamp J.

The flow table <NUM> may also track the path signatures of the individual packets. A given path signature in the flow table <NUM> can correspond to the path signature in the packet as-received and/or the path signature in the packet as-forwarded by the node. For instance, five packets in the flow corresponding to "Flow Identifier <NUM>" can have a path signature of "Signature A," and five packets in the flow can have a path signature of "Signature B. " With reference to <FIG>, "Signature <NUM>" can be the most recent path signature observed in Flow Identifier <NUM> (e.g., either "Signature A" or "Signature B").

The flow table <NUM> can be utilized to identify a path change in the flow corresponding to "Flow Identifier <NUM>. " Assuming that flow table <NUM> is arranged in chronological order, wherein "Timestamp J" is the most recent timestamp, a path change can be observed between "Timestamp E" and "Timestamp F," wherein, packets of the flow change from "Signature A" to "Signature B. " Accordingly, the path change in the flow can be efficiently identified.

<FIG> and <FIG> illustrates example processes <NUM> and <NUM> for updating a path signature of a data packet. In some example implementations, the process <NUM> and/or the process <NUM> is performed by a network node, such as first node <NUM> or network node <NUM> described above with reference to <FIG>, or any of Nodes A to D <NUM>-A to <NUM>-D described above with reference to <FIG>.

Process <NUM> may be performed by a node receiving a data packet without an existing path signature. At <NUM>, a packet is received. The packet may be part of a flow through a network from a source to a destination. In some cases, the as-received packet may omit a path signature.

At <NUM>, a path signature based on one or more node details is generated. The one or more node details can include at least one of an identifier of the particular ingress port at which the packet is received, an identifier of an egress port at which the packet will be forwarded from, an identifier of the node at which the packet is received, or the like. In various implementations, the path signature can be generated using a hash function. For instance, any one of Formulas <NUM> to <NUM> or <NUM> to <NUM> described above can be used to generate the path signature. In some implementations, the path signature may have a limited size, such as <NUM> bits, <NUM> bits, or the like.

At <NUM>, the path signature is added to the packet. In some cases, the path signature is populated in a data field in a header (e.g., an IP header, an IPv4 option, an IPv6 extension header, an NSH header, a Geneve header, a VXLAN-GPE header, an SRv6 header, or an MPLS header) and/or a payload (e.g., as identified by an EtherType) of the packet. In some examples, the data field is included in at least one of IOAM, INT, IFA, or IFIT metadata within the packet. The data field may have a fixed size corresponding to the length of the path signature.

At <NUM>, the packet is forwarded with the path signature. In various implementations, the packet is forwarded from a selected egress port. The egress port can be selected based on at least one of the destination of the packet, a load associated with a node affiliated with the egress port, a load associated with a node attached to another egress port, or the like. For instance, the header of the packet may indicate the destination of the packet, and the egress port can be selected to forward the packet in the direction of the destination. In some cases, a load balancing functionality can be used to select an egress port attached to at least one node in the network that is relatively uncongested.

At <NUM>, a flow table is updated based on the path signature. In some cases, an entry of the flow table can be generated to include the path signature and at least one of an identifier of the flow, a timestamp at which the packet was received, a timestamp at which the packet was forwarded, or the like. In various examples, the path signature generated in the process <NUM> can be the same path signature utilized in a previous packet of the same flow. According to various implementations, an existing entry in the flow table corresponding to the path signature may be identified and updated at <NUM>. For instance, the entry may include at least one of a count corresponding to the number of packets of the flow with the path signature or a last packet time corresponding to a timestamp of the most recent packet with the path signature. The count and/or the last packet time may be updated based on the packet that is received, updated, and forwarded in process <NUM>.

Although not illustrated in <FIG>, the entity performing process <NUM> may additionally identify a path change of the flow based on the flow table. For instance, by adding a new entry to the flow table corresponding to a new path signature that does not otherwise appear in the flow table, the path change may be identified. In some cases, the entity performing process <NUM> may identify that more than a threshold number of packets with one or more path signatures in the flow have been received and/or forwarded, and may therefore identify that a path change has occurred. In some cases, the entity may generate and transmit an alert that identifies the path change.

Process <NUM> is performed by a node receiving a data path with an existing path signature. At <NUM>, a packet including a first path signature received. The packet may be part of a flow through a network from a source to a destination. In some cases, the first path signature may have been added to the packet and/or generated by a previous node in the network.

At <NUM>, a second path signature based on the first path signature and one or more node details is generated. The one or more node details include at least one of an identifier of the particular ingress port at which the packet is received, an identifier of an egress port at which the packet will be forwarded from, an identifier of the node at which the packet is received, or the like. In various implementations, the path signature is generated using a hash function. For instance, any one of Formulas <NUM> to <NUM> described above can be used to generate the path signature. In some implementations, the path signature may have a limited size, such as <NUM> bits, <NUM> bits, or the like. The second path signature may have the same size as the first path signature.

At <NUM>, the first path signature is replaced with the second path signature in the packet. In some cases, the first path signature is deleted from, and the second path signature is populated in, a data field in a header field (e.g., an IP header, an IPv4 option, an IPv6 extension header, an NSH header, a Geneve header, a VXLAN-GPE header, an SRv6 header, or an MPLS header) and/or in a payload (e.g., as identified by an EtherType) of the packet. In some examples, the data field is included in at least one of IOAM, INT, IFA, or IFIT metadata within the packet. The data field may have a fixed size corresponding to the length of the path signature.

At <NUM>, the packet is forwarded with the second path signature. In various implementations, the packet is forwarded from a selected egress port. The egress port can be selected based on at least one of the destination of the packet, a load associated with a node affiliated with the egress port, a load associated with a node attached to another egress port, or the like. For instance, the header of the packet may indicate the destination of the packet, and the egress port can be selected to forward the packet in the direction of the destination. In some cases, a load balancing functionality can be used to select an egress port attached to at least one node in the network that is relatively uncongested.

At <NUM>, a flow table is updated based on the first path signature and/or the second path signature. In some cases, an entry of the flow table can be generated to include the first path signature and/or the second path signature and at least one of an identifier of the flow, a timestamp at which the packet was received, a timestamp at which the packet was forwarded, or the like. In various examples, the first path signature and/or the second path signature can be the same path signature utilized in a previous packet of the same flow. According to various implementations, an existing entry in the flow table corresponding to first path signature and/or the second path signature may be identified and updated at <NUM>. For instance, the entry may include at least one of a count corresponding to the number of packets of the flow with first path signature and/or the second path signature or a last packet time corresponding to a timestamp of the most recent packet with the first path signature and/or the second path signature. The count and/or the last packet time may be updated based on the packet that is received, updated, and forwarded in process <NUM>.

Although not illustrated in <FIG>, the entity performing process <NUM> may additionally identify a path change of the flow based on the flow table. For instance, by adding a new entry to the flow table corresponding to a new path signature (e.g., the first path signature and/or the second path signature) that does not otherwise appear in the flow table, the path change may be identified. In some cases, the entity performing process <NUM> may identify that more than a threshold number of packets with one or more path signatures in the flow have been received and/or forwarded, and may therefore identify that a path change has occurred. In some cases, the entity may generate and transmit an alert that identifies the path change.

<FIG> illustrates an example process <NUM> for transmitting an alert based on data packets with different path signatures. In some example implementations, the process <NUM> is performed by a network node, such as first node <NUM> or network node <NUM> described above with reference to <FIG>, or any of Nodes A to D <NUM>-A to <NUM>-D described above with reference to <FIG>.

At <NUM>, a first path signature of a first packet in a flow is identified. In some implementations, the first path signature is in the first packet as-received from a previous node in the network. In some cases, the first path signature is in the first packet as-forwarded to a next node in the network. According to particular implementations, the first path signature may be generated by the device performing the process <NUM>.

At <NUM>, a second path signature of a second packet in the flow is identified. In some cases, the second path signature may originate from the same source as the first path signature. For instance, if the first path signature is generated by the node performing the process <NUM>, the second path signature is also generated by the node performing the process <NUM>. In various implementations, the second path signature may have an equivalent size to the first path signature. For instance, the first and second path signatures may each have a size of <NUM> bits, <NUM> bits, or the like.

At <NUM>, the first path signature is determined to be different than the second path signature. In some cases, the first path signature and the second path signature are stored in local memory, such as in a flow table. Accordingly, the first path signature and the second path signature can be compared even after one or both of the first and second packets has been forwarded to another node in the network. In some cases, the entity performing the process <NUM> may additionally determine that a number of packets in the flow with the first path signature and/or a number of packets in the flow with the second path signature exceeds a predetermined threshold. In various implementations, the first path signature and the second path signature can be compared before, as, or immediately after the first and second packets have been forwarded.

At <NUM>, an alert indicating the flow is transmitted to a collector. The collector may be a separate device that can receive other alerts from other nodes in the network. In various implementations, the alert may be a data packet that includes a flow indicator in a payload. The flow indicator can include at least one of a least one element of a <NUM>-tuple associated with the flow, such as a source (e.g., from the same IP address), destination (e.g., directed to the same IP address), protocol (e.g., IP protocol), source port (e.g., for UDP or TCP), destination port (e.g., for UDP, TCP, or ICMP), or type of service (e.g., IP Type of Service (ToS)) of the first packet and the second packet. In some cases, the alert may also indicate the device performing the process <NUM>. For instance, the alert may include a node identifier (e.g., an IP address) in a header or the payload.

<FIG> illustrates an example process <NUM> for reporting a problem to a central administrator based on a path change. In some example implementations, the process <NUM> is performed by a collector, such as the collector <NUM> described above with reference to <FIG> or the collector <NUM> described above with reference to <FIG>.

At <NUM>, an alert is received from a node. The alert may indicate a path change in a network to which the node belongs. In various implementations, the alert may be a data packet that includes a flow indicator in a payload. The flow indicator can include at least one of a least one element of a <NUM>-tuple associated with the flow, such as a source (e.g., from the same IP address), destination (e.g., directed to the same IP address), protocol (e.g., IP protocol), source port (e.g., for UDP or TCP), destination port (e.g., for UDP, TCP, or ICMP), or type of service (e.g., IP Type of Service (ToS)) of the first packet and the second packet. In some cases, the alert may also indicate the node itself. For instance, the alert may include a node identifier (e.g., an IP address) in a header or the payload.

At <NUM>, a problem associated with the node is identified. In some cases, another alert may be received from another node that is downstream of the node from which the alert is received at <NUM>. The path change at the downstream node may be determined to have originated at the node from which the alert is received at <NUM>. In some cases, the problem may be a problem associated with an interface between the node and a downstream node. For instance, the node may determine to forward a first packet in the flow to the downstream node, then determine that the interface has been interrupted, and may then determine to forward a second packet in the flow to a different node in the network. In some cases, the problem may be a problem associated with congestion in the network. For instance, the node may determine to forward a first packet in the flow to a downstream node, may determine that the downstream node is congested, and may then decide to forward a second packet in the flow to a different downstream node.

At <NUM>, the problem is reported to a central administrator. In some cases, the central administrator may initiate a process by which the problem can be solved. In various implementations, the central administrator can be a device that can output an alert to an individual or system that can address the problem. For instance, the central administrator my dispatch an individual to correct the problem in the network.

<FIG> shows an example computer architecture for a server computer <NUM> capable of executing program components for implementing the functionality described above. The computer architecture shown in <FIG> illustrates a conventional server computer, workstation, desktop computer, laptop, tablet, network appliance, e-reader, smartphone, or other computing device, and can be utilized to execute any of the software components presented herein. The server computer <NUM> may, in some examples, correspond to a network node <NUM> described herein.

The computer <NUM> includes a baseboard <NUM>, or "motherboard," which is a printed circuit board to which a multitude of components or devices can be connected by way of a system bus or other electrical communication paths. In one illustrative configuration, one or more central processing units ("CPUs") <NUM> operate in conjunction with a chipset <NUM>. The CPUs <NUM> can be standard programmable processors that perform arithmetic and logical operations necessary for the operation of the computer <NUM>.

The chipset <NUM> provides an interface between the CPUs <NUM> and the remainder of the components and devices on the baseboard <NUM>. The chipset <NUM> can provide an interface to a RAM <NUM>, used as the main memory in the computer <NUM>. The chipset <NUM> can further provide an interface to a computer-readable storage medium such as a read-only memory ("ROM") <NUM> or non-volatile RAM ("NVRAM") for storing basic routines that help to startup the computer <NUM> and to transfer information between the various components and devices. The ROM <NUM> or NVRAM can also store other software components necessary for the operation of the computer <NUM> in accordance with the configurations described herein.

The computer <NUM> can operate in a networked environment using logical connections to remote computing devices and computer systems through a network, such as the network <NUM>. The chipset <NUM> can include functionality for providing network connectivity through a Network Interface Controller (NIC) <NUM>, such as a gigabit Ethernet adapter. The NIC <NUM> is capable of connecting the computer <NUM> to other computing devices over the network <NUM>. It should be appreciated that multiple NICs <NUM> can be present in the computer <NUM>, connecting the computer to other types of networks and remote computer systems. In some instances, the NICs <NUM> may include at least on ingress port and/or at least one egress port.

The computer <NUM> can be connected to a storage device <NUM> that provides non-volatile storage for the computer. The storage device <NUM> can store an operating system <NUM>, programs <NUM>, and data, which have been described in greater detail herein. The storage device <NUM> can be connected to the computer <NUM> through a storage controller <NUM> connected to the chipset <NUM>. The storage device <NUM> can consist of one or more physical storage units. The storage controller <NUM> can interface with the physical storage units through a serial attached SCSI ("SAS") interface, a serial advanced technology attachment ("SATA") interface, a fiber channel ("FC") interface, or other type of interface for physically connecting and transferring data between computers and physical storage units.

The computer <NUM> can store data on the storage device <NUM> by transforming the physical state of the physical storage units to reflect the information being stored. The specific transformation of physical state can depend on various factors, in different embodiments of this description. Examples of such factors can include, but are not limited to, the technology used to implement the physical storage units, whether the storage device <NUM> is characterized as primary or secondary storage, and the like.

For example, the computer <NUM> can store information to the storage device <NUM> by issuing instructions through the storage controller <NUM> to alter the magnetic characteristics of a particular location within a magnetic disk drive unit, the reflective or refractive characteristics of a particular location in an optical storage unit, or the electrical characteristics of a particular capacitor, transistor, or other discrete component in a solid-state storage unit. Other transformations of physical media are possible without departing from the scope and spirit of the present description, with the foregoing examples provided only to facilitate this description. The computer <NUM> can further read information from the storage device <NUM> by detecting the physical states or characteristics of one or more particular locations within the physical storage units.

In addition to the mass storage device <NUM> described above, the computer <NUM> can have access to other computer-readable storage media to store and retrieve information, such as program modules, data structures, or other data. It should be appreciated by those skilled in the art that computer-readable storage media is any available media that provides for the non-transitory storage of data and that can be accessed by the computer <NUM>. In some examples, the operations performed by a network node (e.g., network node <NUM>), source (e.g., <NUM>), destination (e.g., <NUM>), collector (e.g., <NUM>), or central administrator (e.g., <NUM>), may be supported by one or more devices similar to computer <NUM>. Stated otherwise, some or all of the operations performed by a network node, collector, and/or central administrator, may be performed by one or more computer devices <NUM> operating in a cloud-based arrangement.

By way of example, and not limitation, computer-readable storage media can include volatile and non-volatile, removable and non-removable media implemented in any method or technology. Computer-readable storage media includes, but is not limited to, RAM, ROM, erasable programmable ROM ("EPROM"), electrically-erasable programmable ROM ("EEPROM"), flash memory or other solid-state memory technology, compact disc ROM ("CD-ROM"), digital versatile disk ("DVD"), high definition DVD ("HD-DVD"), BLU-RAY, or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information in a non-transitory fashion.

As mentioned briefly above, the storage device <NUM> can store an operating system <NUM> utilized to control the operation of the computer <NUM>. According to one embodiment, the operating system comprises the LINUX operating system. According to another embodiment, the operating system comprises the WINDOWS® SERVER operating system from MICROSOFT Corporation of Redmond, Washington. According to further embodiments, the operating system can comprise the UNIX operating system or one of its variants. It should be appreciated that other operating systems can also be utilized. The storage device <NUM> can store other system or application programs and data utilized by the computer <NUM>.

In one embodiment, the storage device <NUM> or other computer-readable storage media is encoded with computer-executable instructions which, when loaded into the computer <NUM>, transform the computer from a general-purpose computing system into a special-purpose computer capable of implementing the embodiments described herein. These computer-executable instructions transform the computer <NUM> by specifying how the CPUs <NUM> transition between states, as described above. According to one embodiment, the computer <NUM> has access to computer-readable storage media storing computer-executable instructions which, when executed by the computer <NUM>, perform the various processes described above with regard to <FIG>. The computer <NUM> can also include computer-readable storage media having instructions stored thereupon for performing any of the other computer-implemented operations described herein.

As illustrated in <FIG>, the storage device <NUM> stores a path signature updater <NUM>, a path change identifier <NUM>, and a flow table <NUM>. In some implementations, at least one of the path signature updater <NUM>, the path change identifier <NUM>, or the flow table <NUM> can be omitted. Using instructions stored in the path signature updater <NUM>, the CPU(s) <NUM> may be configured to generate and update path signatures for individual data packets in a data flow that are traversing the computer <NUM>. Using instructions stored in the path change identifier <NUM>, the CPU(s) <NUM> may be configured to identify whether a path change has occurred in a data flow by comparing path signatures of different data packets within the data flow. The flow table <NUM> may store past one or more path signatures associated with one or more data flows whose data packets are traversing the computer <NUM>.

In summary, this disclosure describes various methods, systems, and devices related to identifying path changes of data flows in a network. An example method includes receiving, at a node, a packet including a first path signature. The method further includes generating a second path signature by inputting the first path signature and one or more node details into a hash function. The method includes replacing the first path signature with the second path signature in the packet. The packet including the second path signature is forwarded by the node.

In some instances, one or more components may be referred to herein as "configured to," "configurable to," "operable/operative to," "adapted/adaptable," "able to," "conformable/conformed to," etc. Those skilled in the art will recognize that such terms (e.g., "configured to") can generally encompass active-state components and/or inactive-state components and/or standby-state components, unless context requires otherwise.

As used herein, the term "based on" can be used synonymously with "based, at least in part, on" and "based at least partly on.

As used herein, the terms "comprises/comprising/comprised" and "includes/including/included," and their equivalents, can be used interchangeably. An apparatus, system, or method that "comprises A, B, and C" includes A, B, and C, but also can include other components (e.g., D) as well. That is, the apparatus, system, or method is not limited to components A, B, and C.

While the invention is described with respect to the specific examples, it is to be understood that the scope of the invention is not limited to these specific examples. Since other modifications and changes varied to fit particular operating requirements and environments will be apparent to those skilled in the art, the invention is not considered limited to the example chosen for purposes of disclosure, and covers all changes and modifications which do not constitute departures from the scope of this invention as defined in the claims.

Claim 1:
A method, implemented in a network comprising a plurality of nodes including at least a first node and a second node, the method comprising:
receiving (<NUM>), at the first node, a packet including a first path signature, wherein a path signature represents a unique path that a packet has traversed through the network;
generating (<NUM>), by the first node, a second path signature by inputting the first path signature and an identifier of the first node into a hash function;
replacing (<NUM>), by the first node, the first path signature with the second path signature in the packet; and
forwarding (<NUM>), by the first node to the second node, the packet including the second path signature.