Patent Description:
A computer network is composed of a set of nodes and a set of links that connect one node to another. For instance, a computer network may be composed of a set of routers while the set of links may be cables between the routers. When a first node in the network sends a message to a second node in the network, the message may pass through many links and many nodes. The set of links and nodes that the message passes through while traveling from the first node to the second node is referred to as a path through the network. There may be more than one path between the first node and the second node.

Network traffic may travel along the paths, passing through the routers, which may perform one or more operations in addition to routing the network traffic along the path. One such operation may include general flow-specific information gathering. That is, a router may collect information concerning flows of network traffic. A flow may be identified by a so-called five-tuple that includes a source address, a source port, a destination address, a destination port, and a protocol. The flow information may include statistics regarding traffic loads, such as a number of packets per flow per minute or an amount of data per flow per minute. As one example, the router may collect the flow information to provide local insight into network traffic loads.

Using an export protocol, the router may export the flow information. An example of an export protocol includes the Internet protocol flow information export (IPFIX) protocol. Information regarding IPFIX is set forth in<NPL>), <NPL>). The router may export the flow information to allow for a number of different operations. For example, the router may export the flow information to a central managing device (such as a software defined network controller). The central managing device may then take various actions based, at least in part, on the exported flow information.

Document <CIT> describes a system, method, and associated apparatus for continuous measurement of transit latency in individual data switches and multi-device topologies. This document does not teach at least a flow data exporter configured to, create a flow data record specifying the packet arrival time and the packet departure time, and provide the flow data record in a field of a network flow measurement protocol message to a traffic flow data collector device physically separate from the network device.

In general, techniques for using packet flow monitoring to measure residency time for a packet are described. As described herein, the packet residency time of a packet refers to the time elapsed from when the packet ingresses to a network device, the network device applies one or more network services to the packet, and the packet egresses from the network device.

The disclosure sets forth techniques, devices, systems, and methods for measuring a packet residency time using existing protocols without requiring the implementation of a new protocol. According to the present invention, a network flow measurement protocol such as the IPFIX protocol is extended to include additional data fields in flow data records exported to a traffic collector, including a packet ingress time and a packet egress time. The additional data fields allow the calculation of the packet residency time within each network device, as well as the time required for the packet to traverse between two network devices in the network. In accordance with the techniques of the disclosure, a network flow measurement protocol such as the IPFIX protocol is extended to include at least a packet ingress time and a packet egress time.

Based on the traffic to be monitored, a filter can be installed on one or more network devices in the network. The filter has monitoring properties defined in a "monitoring instance. " When a network device receives a packet that matches the filter criteria, the network device records the time at which the packet enters the network device, the time at which the packet departs the network device, and, in some aspects, a packet residency time of the packet with the network device. The network device exports the flow data record pertaining to this packet to a traffic flow data collector. Exported flow data records can include values for a packet arrival time, packet departure time, packet residency time, and monitoring instance name, along with other attributes identifying the source and destination of the packet.

Using the techniques set forth herein, a traffic collector may derive information about how much time a packet resided in each network device along a path. Furthermore, by comparing the packet arrival time and packet departure time of different network devices, the traffic collector can derive the time taken by the packet to traverse between two network devices. Therefore, a traffic collector operating in accordance with the techniques of the disclosure may help to identify which network device or path between network devices is causing the most delay. With packet residency time reported in the flow data records, a traffic collector as described herein may derive information on which network device is causing delay or congestion, thereby helping to identify delay caused by particular services applied on the network device.

The techniques of the disclosure may provide one or more advantages. For example, the techniques of the disclosure obviate the need for network devices to support an additional protocol to monitor packet delay or packet residency time. Furthermore, the techniques of the disclosure enable a network device to measure end-to-end delay for transiting network traffic. The techniques of the disclosure may also enable a network device to measure packet residency time or delay within a network device where the network device applies one or more services to the packet. Furthermore, the techniques of the disclosure may be easily adopted due to the widespread support of network flow measurement protocols such as IPFIX by various customers and network devices. Therefore, the techniques of the disclosure may allow for enhanced packet delay monitoring without substantially impacting performance via the extension of existing network flow measurement protocols to include the data fields described above. Furthermore, in situations where network traffic is load-balanced across multiple paths, the techniques of the disclosure may allow for the identification of a fastest path through the network, thereby improving traffic engineering and path selection for network traffic within a network.

In general, the disclosure describes techniques for measuring a packet residency time of a packet in the network node as well as a travel time of the packet between network devices in a path through the network for a packet. Some network measurement protocols may measure only a round-trip delay between two network devices. An example of such a network measurement protocol is Two-Way Active Measurement Protocol (TWAMP). Additional information with respect to TWAMP is set forth in<NPL>). While protocols such as TWAMP can measure an end-to-end packet travel time along a network path between a source and destination node, such protocols are unable to measure travel time between network devices along the network path. Furthermore, protocols such as TWAMP are unable to measure the packet residency time of a packet within each network device along the network path and are thus unable to determine the impact of network services applied to packets on the network devices along the path between the source and destination. Additionally, TWAMP, and other types of real-time performance monitoring (RPM) require that both the source and destination devices support the protocol and may be limited by a number of probes that can be used to obtain performance metrics.

<FIG> is a block diagram illustrating an example network system <NUM> in accordance with techniques described herein. In some aspects, network system <NUM> can include a network traffic source <NUM> that communicates with one or more network traffic destinations 112A-112N (generically referred to as a network traffic destination <NUM>) via a network <NUM>, a traffic flow data collector <NUM>, and a monitoring control client <NUM>.

Network traffic source <NUM> can be any network device that acts as a source of network traffic. Examples of network traffic sources <NUM> include servers, Internet-of-Things (IoT) devices and any other device that generates and transmits network packets over network <NUM>. As an example, network traffic source <NUM> can be a streaming video server that transmits packets comprising video data to video clients executing on network traffic destinations 112A-112N via network <NUM>. Video monitoring services may measure parameters such as delay factors, jitter, loss rate. Packets generated by protocols such as Route Table Manager (RTM) or TWAMP do not go through services such as video monitoring, because the video monitoring service cannot recognize the TWAMP-type packets. For this reason, it may be difficult for RTM and TWAMP to measure the time it takes for service nodes to apply real-time services to video traffic.

Network <NUM> can include one or more network devices 102A-102D (generically referred to as a network device <NUM>). A network device <NUM> can be any type of device that can receive a network packet from a network traffic source <NUM> or another network device <NUM> and forward the network packet to another network device <NUM> or network traffic destination <NUM>. For example, network device <NUM> can be a router such as a provider edge or customer edge router, a core router, a gateway, a bridge, a hub, or other network device such as a switch.

During operation, a network device <NUM> may collect packet flow measurements with respect to some or all of the network packets that are received and forwarded by the network device <NUM>. In the example illustrated in <FIG>, packet flow measurements can be obtained at observation points labeled P1-P10 in <FIG>. Each of the observation points can measure aspects of network packet flow through a network device <NUM>. In the example illustrated in <FIG>, observation points P1, P2 and P7 can measure aspects of packet flow through network device 102A. Similarly, observation points P3 and P4 can measure aspects of packet flow through network device 102B, observation points P5, P6 and P10 can measure aspects of packet flow through network device 102C, and observation points P8 and P9 can measure aspects of packet flow through network device 102D. In some aspects, the observation points P1-P10 can measure a packet arrival time of a network packet at a network interface of a corresponding network device 102A-102D and can measure a packet departure time of the network packet after processing by the corresponding network device 102A-102D.

A network packet may take one of multiple paths through network <NUM>, depending on the network devices 102A-102D that receive the packets. In the example illustrated in <FIG>, two network paths exist for traffic between network traffic source <NUM> and a network traffic destination 112A-112N. A first path includes network device 102A, 102B and 102C. A second path includes network device 102A, 102D and 102C. A network interface receiving a network packet may be referred to as an ingress network interface with respect to the network packet. A network interface forwarding the network packet on to a next hop towards a network traffic destination 112A-112N may be referred to as an egress network interface with respect to the network packet. A network interface may be an ingress network interface with respect to network packets passing through the network device in one direction, and an egress network interface with respect to other network packets passing through the device in another direction. Thus, for network packets originating at network traffic source <NUM> that are transmitted to one or more of network traffic destinations 112A-112N and traverse network <NUM> via the first path, observation points P1, P3, and P5 may be associated with ingress network interfaces of network devices 102A, 102B and 102C respectively, and observation points P2, P4 and P6 may be associated with egress network interfaces of network devices 102A, 102B and 102C respectively. For packets originating at network traffic source <NUM> that are transmitted to one or more of network traffic destinations 112A-112N and traverse network <NUM> via the second path, observation points P1, P8, and P10 may be associated with ingress network interfaces of network devices 102A, 102D and 102C respectively, and observation points P7, P9 and P6 may be associated with egress network interfaces of network devices 102A, 102D and 102C respectively.

As noted above, a network device <NUM> can measure a packet arrival time and packet departure time of a network packet passing through the network device <NUM>. The network device <NUM> can store the packet arrival times and packet departure times of network packets in data flow records and transmit the data flow records to traffic flow data collector <NUM>. In some aspects, the network device <NUM> can determine the packet residency time and include the packet residency time in the data flow record.

Traffic flow data collector <NUM> can receive the data flow records from the network devices 102A-102D and store the data flow records in flow database <NUM> for analysis. In some aspects, traffic flow data collector <NUM> can use the packet arrival times and packet departure times to determine packet residency times for a network packet if the network device <NUM> does not determine a packet residency time. A packet residency time can represent the amount of time a network device <NUM> takes to process the network packet before forwarding the network packet to the next hop. The packet residency time can thus include the packet processing time to determine the next hop for the network packet along with the processing time associated with services executed on the network device <NUM> such as firewall services, filtering services, routing services, or other services provided on the network device <NUM>.

Traffic flow data collector <NUM> or an analysis application (not shown) can use the packet arrival times, packet departure times, and packet residency times to determine various aspects of network traffic flow through network <NUM>. For example, with respect to the first path of network packets originating from network traffic source <NUM> to network traffic destinations 112A-112N (e.g., the path including network devices 102A, 102B and 102C), a network path travel time can be determined using packet arrival times determined at observation points P1, P3 and P5 and packet departure times at observation points P2, P4 and P6. Additionally, packet residency times for each of the network devices 102A, 102B and 102C can be determined. Similarly, with respect to the second path of network packets originating from network traffic source <NUM> to network traffic destinations 112A-112N (e.g., the path including network devices 102A, 102D and 102C), a network path travel time using packet arrival times determined at observation points P1, P8 and P10 and packet departure times at observation points P7, P9 and P6 can be determined. Additionally, packet residency times for each of the network devices 102A, 102D and 102C can be determined. Traffic flow data collector <NUM> or an analysis application can use the network path travel times and packet residency times to determine the fastest paths through network <NUM>. Further, the packet residency times for the network devices can be used to determine network devices <NUM> (e.g., service nodes) that may be causing the most delay in packet throughput. Upon determining that a network device <NUM> is causing delay, the traffic flow data collector <NUM> or other network management application can make updated routing decisions to steer network traffic away from the network device or node causing the most delay. Further, a network administrator can determine whether services provided by a network device causing delay should be removed, modified or load balanced in order to improve network throughput.

Monitoring control client <NUM> can be used to control which packets are measured at observation points. For example, monitoring control client <NUM> can provide a user interface for use by a network administrator to determine which packets are selected for measurement. In some aspects, monitoring control client <NUM> can be used to select source addresses, destination addresses, protocols and sampling rates for filters applied by the network devices <NUM> that select network packets for measurement at observation points.

In the example illustrated in <FIG>, a single network traffic source <NUM> is shown. A network system <NUM> will typically have more than one network traffic source, and in fact, may have many network traffic sources <NUM>. Additionally, a network traffic source <NUM> may act as a network traffic destination <NUM> with respect to other network traffic sources <NUM>. Similarly, a network traffic destination <NUM> may act as a network traffic source <NUM> with respect to other network traffic destinations. Further, four network devices 102A - 102D are shown in the example illustrated in <FIG>. A network system <NUM> may have fewer or more than four network devices <NUM>.

Further details regarding aspects of the configuration and operation of a network device <NUM>, traffic flow data collector <NUM> and monitoring control client <NUM> will be provided with respect to <FIG>.

<FIG> is block diagram illustrating, in further detail, an example network device <NUM> configured in accordance with various aspects of the techniques described in this disclosure. Network device <NUM> can be any of the network devices 102A-102D illustrated in <FIG>. The network device <NUM> may be logically partitioned into a control plane <NUM> and a forwarding plane <NUM> (sometimes referred to as a data plane). As shown in <FIG>, control plane <NUM> of network device <NUM> includes a control unit <NUM> and forwarding plane <NUM> includes a forwarding unit <NUM> and at least two network interfaces (e.g., network interface <NUM> and network interface <NUM>). Network interfaces <NUM> and <NUM> may be network interfaces provided by a single unit such as a line card with multiple network interfaces, or may be provided as separate units (e.g., separate line cards).

Control unit <NUM> may provide capabilities related to determining a network topology and maintaining routing information for the network topology. In some aspects, control unit <NUM> includes a control processor <NUM>, protocols <NUM>, a flow data exporter <NUM> and a management interface <NUM>. Control processor <NUM> may include processing circuitry that executes software instructions, such as those used to define a software or computer program that executes as a process on the control processor to perform techniques described herein. For example, control processor <NUM> may execute instructions that implement protocols <NUM> and/or flow data exporter <NUM>. Alternatively, or in addition, control processor <NUM> may include dedicated hardware, such as one or more integrated circuits, one or more Application Specific Integrated Circuits (ASICs), one or more Application Specific Special Processors (ASSPs), one or more Field Programmable Gate Arrays (FPGAs), or any combination of one or more of the foregoing examples of dedicated hardware, for performing the techniques described herein. The software and data may be stored in a computer-readable storage medium (not shown in <FIG>), such as non-transitory computer-readable mediums including a storage device (e.g., a disk drive, or an optical drive) and/or a memory such as RAM (including various forms of DRAM, e.g., DDR2 SDRAM, or SRAM), Flash memory, another form of fixed or removable storage medium that can be used to carry or store desired program code and program data.

Control unit <NUM> may implement various routing protocols <NUM>. Examples of such protocols include Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), Routing Information Protocol (RIP), RIPv2, IGRP, Border Gateway Protocol (BGP), Path Vector Routing Protocol, Exterior Gateway Protocol (EGP), IGRP, and Enhanced Interior Gateway Routing Protocol (EIGRP). In some aspects, control unit <NUM> can receive one or more control messages via management interface <NUM> that include routing information in a format specified by one or more of protocols <NUM>. Control unit <NUM> can interpret the data in the message according to the protocol and update a routing information base (RIB) <NUM> with new routing information as specified by the message. Additionally, control processor <NUM> can update forwarding information base (FIB) <NUM> as appropriate based on information in the RIB <NUM>.

Forwarding unit <NUM> may provide capabilities related to processing network packets received at network interfaces of the network device <NUM>. In some aspects, forwarding unit <NUM> includes a forwarding processor <NUM> and a packet processor <NUM>. Forwarding unit <NUM> may receive an incoming packet (e.g., a packet at an ingress network interface <NUM>), process the packet, and select an egress network interface (e.g., network interface <NUM>) to send the packet to the next hop (e.g., the next network device in a path through a network from the source address of the packet to the destination address of the packet). The next hop may be determined according to FIB <NUM>.

Forwarding processor <NUM> comprises circuitry that executes software instructions, such as those used to define a software or computer program stored in a computer-readable storage medium (not shown in <FIG>), such as non-transitory computer-readable mediums including a storage device (e.g., a disk drive, or an optical drive) and/or a memory such as RAM (including various forms of DRAM, e.g., DDR2 SDRAM, or SRAM), Flash memory, another form of fixed or removable storage medium that can be used to carry or store desired program code and program data. Alternatively, or in addition, forwarding processor <NUM> may include dedicated hardware, such as one or more integrated circuits, one or more ASICs, one or more ASSPs, one or more FPGAs, or any combination of one or more of the foregoing examples of dedicated hardware, for performing the techniques described herein.

Packet processor <NUM> processes packets by performing a series of operations on each packet over respective internal packet forwarding paths as the packets traverse the internal architecture of network device <NUM>. Packet processor <NUM> may include one or more configurable hardware chips (e.g., a chipset) that, when configured by applications executing on control unit <NUM>, define the operations to be performed on packets received by packet processor <NUM>. Each chipset may in some examples represent a "packet forwarding engine" (PFE). Each chipset may include different chips each having a specialized function, such as queuing, buffering, interfacing, and lookup/packet processing. Each of the chips may represent application specific integrated circuit (ASIC)-based, field programmable gate array (FPGA)-based, or other programmable hardware logic.

Packet processor <NUM> may process packets to identify packet properties and perform actions based on the properties. Packet processor <NUM> may include forwarding path elements that, when executed, cause the packet processor <NUM> to examine the contents of each packet (or another packet property, e.g., incoming interface) and on that basis make forwarding decisions, apply filters, and/or perform accounting, management, traffic analysis, and load balancing, for example. The result of packet processing determines how a packet received on a network interface (e.g., ingress network interface <NUM>) is forwarded to another network interface (e.g., egress network interface <NUM>) or otherwise processed by packet processor <NUM> of forwarding unit <NUM>.

Packet filter <NUM> can obtain packet data and select packets for further processing according to match criterial. Packet filter <NUM>, when present, selects packets according to rules and/or data defined in monitoring instance <NUM>. As an example, monitoring instance <NUM> may include data ("monitoring instance data") specifying a <NUM>-tuple comprising a source address, a destination address, a source port, a destination port, and a protocol. If an incoming packet's <NUM>-tuple matches the <NUM>-tuple specified in monitoring instance <NUM>, the packet may be further processed as specified in monitoring instance <NUM>. In addition, a monitoring instance may define a sampling rate. For instance, a sampling rate of <NUM> would indicate that every <NUM>th incoming packet is selected and examined to determine if the selected packet matches the properties specified in monitoring instance <NUM> (e.g., the <NUM>-tuple). A sampling rate of one (<NUM>) would indicate that every packet is selected to be examined to determine if further processing is to be performed as specified in monitoring instance <NUM>. A monitoring instance may be identified by a monitoring instance name. More than one monitoring instance <NUM> may be active on a network device <NUM> at any given time. Further, placing the same monitoring instance on multiple network devices in a network can provide the capability to receive flow data that can be used to identify paths that a packet takes through the network.

The incoming packet may be processed by one or more packet services <NUM>. Examples of such services include access control services, statistical sampling services, traffic policing services, rate limiting services, firewall services and accounting services.

The monitoring instances <NUM> and services <NUM> that may be used to process an incoming packet may be specified by a monitoring control client <NUM> (<FIG>). For example, a monitoring control client can communicate one or more messages to a network device <NUM> via management interface <NUM> to specify one or more monitoring instances and/or one or more services that are to be configured on network device <NUM>. Control processor <NUM> can communicate with forwarding unit <NUM> to configure the monitoring instances and services <NUM> according to the information specified in the one or more messages. In some aspects, a Dynamic Tasking Control Protocol (DTCP) can be used for communications between a monitoring control client <NUM> and a network device <NUM> via management interface <NUM>.

The incoming packet can be processed by packet forwarder <NUM>. Packet forwarder <NUM>. Packet forwarder <NUM> examines the header of the incoming packet to determine a destination address for the packet. Packet forwarder <NUM> can consult FIB <NUM> to determine the next hop towards the destination device for the packet. Base on forwarding information obtained from FIB <NUM>, packet forwarder <NUM> can select an egress network interface <NUM> to transmit the packet to the next hop.

As discussed above, a network device such as network device <NUM> may determine a packet arrival time TA indicating a time that a packet arrives at a network interface of the network device (e.g., ingress network interface <NUM>) and a packet departure time TD indicating a time that a packet is forwarded via a network interface of the network device (e.g., egress network interface <NUM>). A packet filter <NUM> may select the packets for which a packet arrival time and packet departure time are determined and recorded. In some aspects, a monitoring instance <NUM> may specify that incoming packets that have header data that matches properties specified in monitoring instance <NUM> and that are selected according to the sampling rate are to be provided to metering process <NUM> by packet filter <NUM>.

Metering process <NUM> can record the packet arrival time TA of the selected packet and the packet departure time TD of the packet. Metering process <NUM> can provide the packet arrival time TA and packet departure time TD to a flow data exporter <NUM>. Flow data exporter <NUM> can store the packet arrival time TA and the packet departure time TD in a flow data record <NUM>. In some implementations, flow data exporter <NUM> may calculate a packet residency time TR that represents the time that a packet was resident in a network device. For example, the packet residency time can be the elapsed time used by the packet filter <NUM>, packet service(s) <NUM>, and packet forwarder <NUM> in processing the packet. In such implementations, flow data exporter <NUM> can store the packet residency time TR in the flow data record <NUM>.

Flow data exporter <NUM> can export (e.g., transmit) one or more flow data records <NUM> to traffic flow data collector <NUM> (<FIG>). Flow data exporter <NUM> can format the flow data records <NUM> according to a protocol and transmit the flow data records <NUM> to traffic flow data collector <NUM> according to the protocol. In some aspects, the protocol is the IPFIX protocol. In other aspects, the protocol can be the NetFlow protocol. Other protocols may be used in still other aspects.

In some aspects, as shown in <FIG>, packet filter monitor <NUM> and metering process <NUM> are provided in the forwarding plane <NUM> of network device <NUM>. This can be desirable, because the time values obtained by the metering process are close to the data link, resulting in highly accurate time values. Further, as shown in <FIG>, in some aspects flow data exporter <NUM> is provided in the control plane <NUM>. In some aspects, flow data exporter <NUM> may be provided in the data plane <NUM>.

<FIG> is a block diagram illustrating a data structure for an example flow data record <NUM> including elements used to measure packet residency in in accordance with various aspects of the techniques described in this disclosure. <FIG> illustrates an example flow data record <NUM> including data elements that are extensions to those specified by the IPFIX protocol. In some aspects, example flow data record <NUM> includes an observation domain identifier (ID) <NUM> that uniquely identifies the network device that generated the flow data record <NUM> within a group of network devices providing flow data records to a traffic flow data collector. Data elements <NUM>-<NUM> comprise extensions to the IPFIX protocol. Data elements <NUM>-<NUM> are associated with a packet arrival time TA of a packet. The packet arrival time includes a milliseconds portion <NUM>, a microseconds portion <NUM>, and a nanoseconds portion <NUM>. Data elements <NUM>-<NUM> are associated with a packet departure time TD of a packet. The packet departure time TD includes a milliseconds portion <NUM>, a microseconds portion <NUM>, and a nanoseconds portion <NUM>. A packet residency time <NUM> can be represented in nanoseconds. As noted above, in some implementations, the packet residency time <NUM> can be calculated by the flow data exporter <NUM>. In other implementations, the packet residency time <NUM> can be calculated by the traffic flow data collector <NUM> (<FIG>) based on the packet arrival time and the packet departure time in the flow data record <NUM>. In such implementations, packet residency time <NUM> may not be present in the data flow record <NUM>, or a value for the packet residency time <NUM> field of data flow record <NUM> may be provided by the data flow collector <NUM>.

<FIG> is a flowchart illustrating example operations of a network device <NUM>, <NUM> in accordance with various aspects of the techniques described in this disclosure. The operations begin with receiving a network packet at a network interface (<NUM>). For example, the network packet may be received at a router, switch, gateway or other device configured to receive and send network packets.

Processing of the incoming network packet may take two paths. A forwarding path of the flowchart includes operations associated with forwarding the network packet to the next hop towards the destination. A metering path of the flowchart includes operations associated with obtaining metrics related to processing the incoming network packet. For example, timing metrics may be obtained that indicate the amount of time spent processing the packet in the forwarding plane of the network device. This time may include time used by service processes (firewalls, accounting services, access control services etc.) and time used by packet forwarding processes in determining the next hop for the network packet.

Processing along the forwarding path begins with one or more services processing the incoming network packet, if any services are configured for the network device (<NUM>). For example, access control services, statistical sampling services, traffic policing services, rate limiting services, firewall services and accounting services may inspect packet headers and/or payload data and perform service related actions based on the packet data.

A packet processor can determine forwarding information for the network packet (<NUM>). For example, the packet processor may determine a packet destination address from packet header information. The packet processor can consult a FIB or forwarding table to determine a network address of the network device that is the next hop to the destination address. The packet can then be provided to an egress network interface that can be selected based on the next hop network device's network address (<NUM>). The forwarding path ends with the packet being transmitted via the selected network interface.

Operations along the metering path also begin when the packet is received on the ingress network interface. A filter can inspect packet data to determine if the packet has been selected for monitoring (<NUM>). For example, a monitoring instance includes criteria that can be used to select a packet for monitoring. The criteria can include some or all of a <NUM>-tuple (source address, source port, destination address, destination port, protocol) or other matching criteria. Additionally, a sampling rate may be defined by the monitoring instance. The sampling rate can specify a frequency that packets are selected for monitoring. For example, a sampling rate of <NUM> can indicate that one packet out of every <NUM> packets received are selected to determine if the packet data matches the filter criteria. If the packet has not been selected for monitoring ("NO" branch of <NUM>), no further operations are performed with respect to metering and the metering path ends.

If a packet has been selected for monitoring ("YES" branch of <NUM>), a metering process obtains a packet arrival time TA of the packet (<NUM>). In some aspects, the packet arrival time may be determined down to the nanosecond level. The metering process obtains a packet departure time TD of the packet when the packet has been transmitted from the egress network interface (<NUM>). In some aspects, the packet departure time may be determined down to the nanosecond level. The metering process can provide the packet arrival time and packet departure time to a flow data exporter.

In some aspects, the flow data exporter may determine a packet residency time TR, based on the packet arrival time and packet departure time received from the metering process, where TR = TD - TA (<NUM>). The packet residency time can represent the amount of time the packet was resident on the network device. This time can include time spent by services processing the packet and the time spent determining the next hop for the packet. The flow data exporter can create a data flow record and add the packet arrival time, packet departure time and packet residency to the data flow record (<NUM>). Other data elements may be included in the data record. For example, an observation domain identifier may be added to the data flow record. The observation domain identifier can be a network address, device identifier, Globally Unique Identifier (GUID), or other identifier that that can be used to distinguish the network device creating the data flow record from other network devices providing data flow records to a traffic collector. Additionally, a monitoring instance name is added to the data flow record. The monitoring instance name identifies a monitoring instance specifying the criteria that caused the network packet to be selected for metering. The metering process can export the data flow record to a traffic flow data collector (<NUM>) and the metering operations end. Other data elements may also be included with the data flow record.

<FIG> is a flowchart illustrating example operations to collect and analyze data flow records in accordance with various aspects of the techniques described in this disclosure. The traffic flow data collector receives a data flow record for a packet (<NUM>). In some aspects, the packet residency time TR discussed above is not determined at the network device and is instead determined by the traffic flow data collector (<NUM>). The traffic flow data collector can store the data flow record in a database for analysis (<NUM>), either by the traffic flow data collector or other application.

In some aspects, the analysis can include determining packet travel times for one or more paths between source and destination pairs (<NUM>). The packet arrival times and packet departure times for network devices in the path that a packet traveled from the source to the destination can be used to determine both a total time from source to destination and network connection travel times for network connections between the network devices in the path. Using the example network system <NUM> shown in <FIG>, the packet departure time of a packet from observation point P2 of network device 102A and the packet arrival time of the packet at observation point P3 of network device 102B can be used to determine a travel time for the network connection between network device 102A to 102B. Similarly, the packet arrival time of a packet at observation point P1 and the packet departure time of the packet at observation point P6 can be used to determine a total travel time through the network <NUM>.

Further, the analysis can include determining the network devices and paths (or network connections within a path) having the most delay (<NUM>). For example, travel times for network connections and total travel times through a network path can be used to determine paths and connections having the most delay. The packet residency times of each network device can be used to determine network devices causing the most delay in the network.

The results of the above-described analysis can be used to determine actions that may reduce delay in the network. For example, network devices having most delay (e.g., the highest packet residency times) can be analyzed to determine if any of the services executing on the network device can be removed, or reconfigured, or load balanced to a different network device in order to reduce the time spent processing a packet. Further, RIBs, FIBs and/or forwarding tables may be modified to steer network traffic away from network devices having high packet residency times and towards network devices having comparatively lower packet residency times.

The techniques described above have been discussed in the context of services provided by physical network devices. The techniques can be applied as well to virtual devices such as virtual routers, virtual switches etc..

In some examples, a method includes receiving, by at least one computing device, one or more flow data records from a plurality of network devices, each of the flow data records including a packet arrival time and a packet departure time, determining, by the at least one computing device from the one or more flow data records, one or more network paths from a source device to a destination device, the one or more network paths including two or more of the plurality of network devices, identifying, by the at least one computing device, a first network device along the one or more network paths having a highest packet residency time, the packet residency time based on the packet arrival time and the packet departure time, and determining, by the at least one computing device, a delay reduction action for the first network device.

In some examples, a method includes receiving, via a first network interface of a network device, a network packet of a packet flow; determining, by one or more processors of the network device, a packet arrival time of the network packet at the first network interface, providing, by the one or more processors, the network packet to a second network interface of the network device for transmission toward a destination, determining, by the one or more processors, a packet departure time for the network packet from the second network interface; creating, by the one or more processors, a flow data record specifying the packet arrival time and the packet departure time, and providing, by the one or more processors, the flow data record to a traffic flow data collector device physically separate from the network device.

If implemented in hardware, this disclosure may be directed to an apparatus such a processor, processing circuitry, or an integrated circuit device, such as an integrated circuit chip or chipset. Alternatively, or additionally, if implemented in software or firmware, the techniques may be realized at least in part by a computer-readable data storage medium comprising instructions that, when executed, cause a processor to perform one or more of the methods described above. For example, the computer-readable data storage medium may store such instructions for execution by a processor.

A computer-readable medium may form part of a computer program product, which may include packaging materials. A computer-readable medium may comprise a computer data storage medium such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), Flash memory, magnetic or optical data storage media, and the like. In some examples, an article of manufacture may comprise one or more computer-readable storage media.

In some examples, the computer-readable storage media may comprise non-transitory media. The term "non-transitory" may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in RAM or cache). Additionally, or alternatively, the techniques discussed herein may be realized at least in part by a computer readable communication medium that carries or communicates code in the form of instructions or data structures and that can be accessed, read, and/or executed by a computer. In other words, any suitable computer-readable medium may be used, which comprises instructions and which can for example be a transitory medium, such as a communication medium, or a non-transitory medium, such as a storage medium.

The code or instructions may be software and/or firmware executed by processing circuitry including one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), or other equivalent integrated or discrete logic circuitry. In addition, in some aspects, functionality described in this disclosure may be provided within software modules or hardware modules.

Thus, from one perspective, the present disclosure sets forth techniques, devices, systems, and methods for measuring a packet residency time in a network device. In the present disclosure, a network flow measurement protocol includes data fields in flow data records exported to a traffic collector, including a packet ingress time and a packet egress time. The data fields allow the calculation of the packet residency time within a network device, as well as the time required for the packet to traverse between two network devices in the network. A filter can be installed on one or more network devices in a network. For packets that match the filter criteria, the network device records the times of packet arrival and packet departure, and, in some aspects, a packet residency time of the packet with the network device. The network device exports the flow data record pertaining to this packet to a traffic flow data collector.

Claim 1:
A network device comprising:
a first network interface;
a second network interface;
a monitoring instance having a corresponding monitoring instance name and corresponding filter criteria;
a packet filter configured to select, based on the filter criteria, network packets;
a forwarding unit (<NUM>) configured to,
receive (<NUM>), via the first network interface, a network packet of a packet flow, in response to a determination that the network packet is a selected network packet, determine (<NUM>) a packet arrival time of the selected network packet at the first network interface,
provide the network packet to the second network interface for transmission toward a destination,
in response to a determination that the network packet is a selected network packet, determine (<NUM>) a packet departure time for the selected network packet from the second network interface; and
a flow data exporter configured to,
create (<NUM>) a flow data record specifying the monitoring instance name for the monitoring instance having the criteria that caused the network packet to be selected, the packet arrival time and the packet departure time, and
provide (<NUM>) the flow data record in a field of a network flow measurement protocol message to a traffic flow data collector device physically separate from the network device.