High-speed replay of captured data packets

An embodiment may involve non-volatile memory configured to store chunks of data packets, wherein the chunks are associated with sequence numbers; a shared producer queue; one or more processors configured to transfer the chunks to the shared producer queue in order of the sequence numbers; an array of n sets of processors configured to: (i) read the chunks from the shared producer queue, (ii) re-write network addresses within the data packets to create modified chunks, and (iii) write the modified chunks to queues; and a field programmable gate array based network interface containing the queues and m physical ports, and configured to: (i) read the modified chunks in order of their sequence numbers, (ii) unpack the modified chunks into data packets, (iii) write updated checksums to the data packets, (iv) respectively select output ports for the data packets, and (v) transmit the data packets from the selected output ports.

BACKGROUND

Data packet capture devices have been used for many years to carry out network troubleshooting and testing. Such a device, which may be a general purpose computer, is configured to capture copies of some or all data packets traversing a network segment (e.g., Ethernet or Wifi) to which the device is connected. The captured data packets are either displayed in a user-readable fashion in real-time, or more commonly, stored in binary files.

SUMMARY

The embodiments herein provide a customized computing device specifically designed for replay of captured data packets. This device is particularly useful in testing and debugging situations, where one or more segments in a production network and/or devices thereon are experiencing problems (e.g., transactions not completing properly). Data packets traversing these segments may be captured and stored by a data packet capture device. The stored data packets may then be transferred or otherwise provided to a data packet replay device in accordance with the embodiments herein.

The data packet replay device may replay (transmit) these data packets in an order and with inter-packet timing that simulates the captured data packets and their transactions with high precision. This replay may take place in a laboratory environment, or some environment other than the production network. In some cases, the replayed data packets may have their medium access control (MAC) and/or Internet Protocol (IP) addresses rewritten to be topologically consistent with addresses assigned to ports as well as subnets defined for the network on which the replay occurs. Further, the speed of the replay may be slowed down or sped up.

In this fashion, faults in client devices, server devices, switches, routers, and the like can be more easily debugged and addressed. For instance, some faults may only be able to be reproduced under realistic workloads that would otherwise be difficult to simulate in the laboratory environment.

Furthermore, accurate replay of captured data packets at high speed (e.g., 10 gigabits per second, 40 gigabits per second, or 100 gigabits per second) may be challenging, if not impossible, using off-the-shelf or general purpose computing devices. Such devices have internal data transfer bottlenecks (e.g., from long-term storage to RAM or from RAM to network interfaces) that may result in significantly less than the target replay speed and precise inter-packet timing being achievable. These devices may also suffer from delays due to waiting on locks, semaphores, or other shared-memory protection mechanisms. The embodiments herein involve computing hardware that is purpose-built for both high-speed capture of data packets as well as high-speed playout of captured data packets.

Accordingly, a first example embodiment may involve non-volatile memory configured to store chunks of data packets, wherein the chunks contain pluralities of the data packets and are associated with sequence numbers. The first example embodiment may also involve volatile memory configured to store a shared producer queue. The first example embodiment may also involve one or more processors configured to read the chunks from the non-volatile memory and store the chunks in the shared producer queue in order of the sequence numbers. The first example embodiment may also involve an array of n sets of processors configured to: (i) read the chunks from the shared producer queue, (ii) re-write one or more network addresses contained within the data packets of the chunks to create modified chunks, and (iii) write the modified chunks to queues. The first example embodiment may also involve a field programmable gate array (FPGA) based network interface containing the queues and m physical ports, and configured to: (i) read the modified chunks in order of their sequence numbers into onboard volatile memory, (ii) unpack the modified chunks into the data packets contained therein, (iii) generate and write updated checksums to the data packets, (iv) respectively select output ports for each of the data packets, wherein the output ports are from the m physical ports, and (v) transmit the data packets from the output ports that were respectively selected.

A second example embodiment may involve carrying out, by one or more processors, (i) reading of chunks of data packets from non-volatile memory, wherein the chunks are associated with sequence numbers, and (ii) storing of the chunks in a shared producer queue of the non-volatile memory in order of the sequence numbers. The second example embodiment may also involve carrying out, by an array of n sets of processors, (i) reading of the chunks from the shared producer queue, (ii) re-writing one or more network addresses contained within the data packets of the chunks to create modified chunks, and (iii) writing the modified chunks to queues. The second example embodiment may also involve carrying out, by an FPGA-based network interface containing the queues and m physical ports, (i) reading of the modified chunks in order of their sequence numbers into onboard volatile memory, (ii) unpacking of the modified chunks into the data packets contained therein, (iii) generation and writing of updated checksums to the data packets, (iv) respective selection of output ports for each of the data packets, wherein the output ports are from the m physical ports, and (v) transmission of the data packets from the output ports that were respectively selected.

In a fourth example embodiment, a computing system may include at least one processor, as well as memory and program instructions. The program instructions may be stored in the memory, and upon execution by the processor(s), cause the computing system to perform operations in accordance with the first and/or second example embodiment.

In a fifth example embodiment, a system may include various means for carrying out each of the operations of the first and/or second example embodiment.

DETAILED DESCRIPTION

The following sections describe a high-speed data packet capture system. After that system is describe, standalone and integrated variations of a high-speed data packet generator are disclosed. Thus, data packet generator function and the data packet capture function may exist with or without one another across various embodiments.

I. Example Computing Device and Packet Capture Thereon

As noted above, packet capture on conventional computing devices is limited due to these devices not being optimized for processing a high sustained rate of incoming packets. This section reviews these devices for purposes of comparison, focusing on their bottlenecks. This section also introduces a popular file format for storing captured packets.

A. Example Computing Device

FIG. 1is a simplified block diagram exemplifying a computing device100, illustrating some of the components that could be included in such a computing device. Computing device100could be a client device (e.g., a device actively operated by a user), a server device (e.g., a device that provides computational services to client devices), or some other type of computational platform.

Processor102may represent one or more of any type of computer processing unit, such as a central processing unit (CPU), a co-processor (e.g., a mathematics, graphics, or encryption co-processor), a digital signal processor (DSP), a network processor, and/or a form of integrated circuit or controller that performs processor operations. In some cases, processor102may be a single-core processor, and in other cases, processor102may be a multi-core processor with multiple independent processing units. Processor102may also include register memory for temporarily storing instructions being executed and related data, as well as cache memory for temporarily storing recently-used instructions and data.

Memory104may be any form of computer-usable memory, including but not limited to register memory and cache memory (which may be incorporated into processor102), as well as random access memory (RAM), read-only memory (ROM), and non-volatile memory (e.g., flash memory, hard disk drives (HDDs), solid state drives (SSDs), compact discs (CDs), digital video discs (DVDs), and/or tape storage). Other types of memory may be used. In some embodiments, memory104may include remote memory, such as Internet Small Computer Systems Interface (iSCSI).

Memory104may store program instructions and/or data on which program instructions may operate. As shown inFIG. 1, memory may include firmware104A, kernel104B, and/or applications104C. Firmware104A may be program code used to boot or otherwise initiate some or all of computing device100. Kernel104B may be an operating system, including modules for memory management, scheduling and management of processes, input/output, and communication. Kernel104B may also include device drivers that allow the operating system to communicate with the hardware modules (e.g., memory units, networking interfaces, ports, and busses), of computing device100. Applications104C may be one or more user-space software programs, such as web browsers or email clients, as well as any software libraries used by these programs. Each of firmware104A, kernel104B, and applications104C may store associated data (not shown) in memory104.

Computing device100may be used for packet capture. In particular, modifications to kernel104B and applications104C may facilitate such capture. Computing device100may receive packets by way of network interface106, optionally filter these packets in kernel104B, and then provide the filtered packets to a packet capture application. The latter may be one of applications104C. In some cases, the filtering may take place in the packet capture application itself. Regardless, the packet capture application may obtain a series of packets for storage and/or display.

B. Example Protocol Stack

FIG. 2depicts a protocol stack of a general purpose computer, such as computing device100. Captured packets may traverse at least part of protocol stack200.

Protocol stack200is divided into two general sections—kernel space and user space. Kernel-space modules carry out operating system functions while user-space modules are end-user applications or services that may be designed to execute on computing devices that support a specific type of kernel. Thus, user-space modules may rely on memory management, communication, and input/output services provided by the kernel. Kernel space inFIG. 2may refer to part of kernel104B inFIG. 1, while user space inFIG. 2may refer to part of applications104C inFIG. 1.

In full generality, protocol stack200may include more or fewer software modules. Particularly, the kernel space may contain additional kernel-space software modules to carry out operating system operations, and the user space may include additional user-space software modules to carry out application operations.

Wifi driver module202may be a kernel-space software module that operates and/or controls one or more physical Wifi hardware components. In some embodiments, Wifi driver module202provides a software interface to Wifi hardware, enabling kernel104B of computing device100to access Wifi hardware functions without needing to know precise control mechanisms of the Wifi hardware being used. When data packets are transmitted or received by way of Wifi hardware, these packets may pass through Wifi driver module202.

Similarly, Ethernet driver module204is a kernel-space software module that operates and/or controls one or more physical Ethernet hardware components. In some embodiments, Ethernet driver module204provides a software interface to Ethernet hardware, enabling kernel104B of computing device100to access Ethernet hardware functions without needing to know precise control mechanisms of the Ethernet hardware being used. When data packets are transmitted or received by way of Ethernet hardware, these packets may pass through Ethernet driver module204.

Protocol stack200may also include other driver modules not shown inFIG. 2. For instance, BLUETOOTH®, cellular, and/or GPS driver modules may be incorporated into protocol stack200. Further, either or both of Wifi driver module202and Ethernet driver module204may be omitted.

Low-level networking module206routes inbound and outbound data packets between driver software modules and network layer software modules (e.g., IPv6 module210and IPv4 module212). Thus, low-level networking module206may serve as a software bus or switching mechanism, and may possibly provide application programming interfaces between driver software modules and network layer software modules. For instance, low-level networking module206may include one or more queues in which inbound data packets are placed so that they can be routed to one of IPv6 module210and IPv4 module212, and one or more queues in which outbound data packets can be placed so that they can be routed to one of Wifi driver module202and Ethernet driver module204. In some embodiments, low-level networking module206might not be present as a separate kernel-space software module, and its functionality may instead be incorporated into driver modules and/or network layer (e.g., IPv6 and/or IPv4) software modules.

IPv6 module210operates the Internet Protocol version 6 (IPv6). IPv6 is a version of the Internet Protocol that features an expanded address space, device auto-configuration, a simplified header, integrated security and mobility support, and improved multicast capabilities. IPv6 module210encapsulates outbound data packets received from higher-layer modules (including those of TCP module214and UDP module216) in an IPv6 header. Conversely, IPv6 module210also decapsulates inbound IPv6 data packets received from low-level networking module206. Although it is not shown inFIG. 2, IPv6 module210may be associated with an ICMPv6 module that provides support for error and informational messages related to IPv6, as well as multicasting and address resolution.

IPv4 module212operates the Internet Protocol version 4 (IPv4). IPv4 is a version of the Internet Protocol that features a smaller address space than IPv6. Similar to IPv6 module210, IPv4 module212encapsulates outbound data packets received from high-layer modules (including those of TCP module214, and UDP module216) in an IPv4 header. Conversely, IPv4 module212also decapsulates inbound data packets received from low-level networking module206. Although it is not shown inFIG. 2, IPv4 module212may be associated with an ICMPv4 module that provides support for simple error reporting, diagnostics, and limited configuration for devices, as well as messages that report when a destination is unreachable, a packet has been redirected from one router to another, or a packet was discarded due to experiencing too many forwarding hops.

As used herein, the terms “Internet Protocol” and “IP” may refer to either or both of IPv6 and IPv4.

TCP module214operates the Transport Control Protocol (TCP). TCP is a reliable, end-to-end protocol that operates on the transport layer of a networking protocol stack. TCP is connection-oriented, in the sense that TCP connections are explicitly established and torn down. TCP includes mechanisms in which it can detect likely packet loss between a sender and recipient, and resend potentially lost packets. TCP is also a modified sliding window protocol, in that only a limited amount of data may be transmitted by the sender before the sender receives an acknowledgement for at least some of this data from the recipient, and the sender may operate a congestion control mechanism to avoid flooding an intermediate network with an excessive amount of data.

UDP module216operates the User Datagram Protocol (UDP). UDP is a connectionless, unreliable transport-layer protocol. Unlike TCP, UDP maintains little state regarding a UDP session, and does not guarantee delivery of application data contained in UDP packets.

High-level networking module218routes inbound and outbound data packets between (i) user-space software modules and (ii) network-layer or transport-layer software modules (e.g., TCP module214and UDP module216). Thus, high-level networking module218may serve as a software bus or switching mechanism, and may possibly provide application programming interfaces between user-space software modules and transport layer software modules. For instance, high-level networking module218may include one or more queues in which inbound data packets are placed so that they can be routed to a user-space software module, and one or more queues in which outbound data packets can be placed so that they can be routed to one of TCP module214and UDP module216. In some embodiments, high-level networking module218may be implemented as a TCP/IP socket interface, which provides well-defined function calls that user-space software modules can use to transmit and receive data.

As noted above, user-space programs, such as application220and application222may operate in the user space of computing device100. These applications may be, for example, email applications, social networking applications, messaging applications, gaming applications, or some other type of application. Through interfaces into the kernel space (e.g., high-level networking module218and/or other interfaces), these applications may be able to carry out input and output operations.

The modules ofFIG. 2described so far represent software used for incoming (received) and outgoing (transmitted) packet-based communication. Examples of incoming and outgoing packet processing follows.

When the Ethernet hardware receives a packet addressed for computing device100, it may queue the packet in a hardware buffer and send an interrupt to Ethernet driver module204. In response to the interrupt, Ethernet driver module204may read the packet out of the hardware buffer, validate the packet (e.g., perform a checksum operation), determine the higher-layer protocol to which the packet should be delivered (e.g., IPv6 module210or IPv4 module212), strip off the Ethernet header and trailer bytes, and pass the packet to low-level networking module206with an indication of the higher-layer protocol.

Low-level networking module206may place the packet in a queue for the determined higher-layer protocol. Assuming for the moment that this protocol is IPv4, low-level networking module206may place the packet in a queue, from which it is read by IPv4 module212.

IPv4 module212may read the packet from the queue, validate the packet (e.g., perform a checksum operation and verify that the packet has not been forwarded more than a pre-determined number of times), combine it with other packets if the packet is a fragment, determine the higher-layer protocol to which the packet should be delivered (e.g., TCP module214or UDP module216), strip off the IPv4 header bytes, and pass the packet to the determined higher-layer protocol. Assuming for the moment that this protocol is TCP, IPv4 module212may provide the packet to TCP module214. In some cases, this may involve placing the packet in the queue, or IPv4 module212may provide TCP module214with a memory address at which the packet can be accessed.

TCP module214may read the packet from the queue, validate the packet, perform any necessary TCP congestion control and/or sliding window operations, determine the application “socket” to which the packet should be delivered, strip off the TCP header bytes, and pass the payload of the packet to the high-level networking module218along with an indication of the determined application. At this point, the “packet” does not contain any headers, and in most cases is just a block of application data.

High-level networking module218may include queues associated with the socket communication application programming interface. Each “socket” may represent a communication session and may be associated with one or more applications. Incoming data queued for a socket may eventually be read by the appropriate application. Assuming for the moment that the application data from the packet is for application220, high-level networking module218may hold the application data in a queue for a socket of application220.

Application220may read the application data from the socket and then process this data. At this point, the incoming packet processing has ended.

Outgoing packet processing may begin when an application, such as application220, writes application data to a socket. The socket may be, for instance, a TCP or UDP socket. Assuming that the application data is for a TCP socket, application220may provide the application data to high-level networking module218, which in turn may queue the application data for TCP module214.

TCP module214may read the application data from the queue, determine the content of a TCP header for the application data, and encapsulate the application data within the TCP header to form a packet. Values of fields in the TCP header may be determined by the status of the associated TCP session as well as content of the application data. TCP module214may then provide the packet to either IPv6 module210or IPv4 module212. This determination may be made based on the type of socket from which the application data was read. Assuming for the moment that the socket type indicates IPv4, TCP module214may provide the packet to IPv4 module212. In some cases, this may involve placing the packet in a queue, or TCP module214may provide IPv4 module212with a memory address at which the packet can be accessed.

IPv4 module212may determine the content of an IPv4 header for the packet, and encapsulate the packet within the IPv4 header. Values of fields in the IPv4 header may be determined by the socket from which the application data was read as well as content of the application data. IPv4 module212may then look up the destination of the packet (e.g., its destination IP address) in a forwarding table to determine the outbound hardware interface. Assuming for the moment that this interface is Ethernet hardware, IPv4 module212may provide the packet to low-level networking module206with an indication that the packet should be queued for Ethernet driver module204.

Low-level networking module206may receive the packet and place it in a queue for Ethernet driver module204. Alternatively, IPv4 module212may provide the packet directly to Ethernet driver module204.

Regardless, Ethernet driver module may encapsulate the packet in an Ethernet header and trailer, and then provide the packet to the Ethernet hardware. The Ethernet hardware may transmit the packet.

In some environments, the term “frame” is used to refer to framed data (i.e., application data with at least some header or trailer bytes appended to it) at the data-link layer, the term “packet” is used to refer to framed data at the network (IP) layer, and the term “segment” is used to refer to framed data at the transport (TCP or UDP) layer. For sake of simplicity, the nomenclature “packet” is used to represent framed application data regardless of layer.

Given protocol stack200and the operations performed by each of its modules, it is desirable for a packet capture architecture to be able to intercept and capture copies of both incoming (received) and outgoing (transmitted) packets. Packet capture module208exists in kernel space to facilitate this functionality.

One or more of Wifi driver module202, Ethernet driver module204, and low-level networking module206may have an interface to packet capture module208. This interface allows these modules to provide, to packet capture module208, copies of packets transmitted and received by computing device100. For instance, Wifi driver module202and Ethernet driver module204may provide copies of all packets they receive (including Wifi and Ethernet headers) to packet capture module208, even if those packets are not ultimately addressed to computing device100. Furthermore, Wifi driver module202and Ethernet driver module204may provide copies of all packets they transmit. This allows packets generated by computing device100to be captured as well.

Regarding the capture of received packets, network interface hardware components, such Wifi and/or Ethernet hardware, normally will discard any incoming packets without a destination Wifi or Ethernet address that matches an address used by computing device100. Thus, Wifi driver module202and Ethernet driver module204might only receive incoming packets with a Wifi or Ethernet destination address that matches an address used by computing device100, as well as any incoming packets with a multicast or broadcast Wifi or Ethernet destination address. However, the Wifi and/or Ethernet hardware may be placed in “promiscuous mode” so that these components do not discard any incoming packets. Instead, incoming packets that normally would be discarded by the hardware are provided to Wifi driver module202and Ethernet driver module204. These modules provide copies of the packets to packet capture module208.

In some embodiments, Wifi driver module202and Ethernet driver module204may provide incoming packets to low-level networking module206, and low-level networking module206may provide copies of these packets to packet capture module208. In the outgoing direction, low-level networking module206may also provide copies of packets to packet capture module208. In order to provide Wifi and Ethernet header and trailer information in these outgoing packets, low-level networking module206may perform Wifi and Ethernet encapsulation of the packets prior to providing them to packet capture module208. Low-level networking module206may also provide copies of these encapsulated packets to Wifi driver module202and/or Ethernet driver module204which in turn may refrain from adding any further encapsulation, and may instead provide the packets as received to their respective hardware interfaces.

Packet capture module208may operate in accordance with packet capture application224to capture packets. Particularly, packet capture application224may provide a user interface through which one or more packet filter expressions may be entered. The user interface may include a graphical user interface, a command line, or a file.

The packet filter expressions may specify the packets that are to be delivered to packet capture application224. For example, the packet filter expression “host 10.0.0.2 and tcp” may capture all TCP packets to and from the computing device with the IP address 10.0.0.2. As additional examples, the packet filter expression “port67or port68” may capture all Dynamic Host Configuration Protocol (DHCP) traffic, while the packet filter expression “not broadcast and not multicast” may capture only unicast traffic.

Packet filter expressions may include, as shown above, logical conjunctions such as “and”, “or”, and “not.” With these conjunctions, complex packet filters can be defined. Nonetheless, the packet filter expressions shown above are for purpose of example, and different packet filtering syntaxes may be used. For instance, some filters may include a bitstring and an offset, and may match any packet that includes the bitstring at the offset number of bytes into the packet.

After obtaining a packet filter expression, packet capture application224may provide a representation of this expression to packet capture module208. Packet capture application224and packet capture module208may communicate, for example, using raw sockets. Raw sockets are a special type of socket that allows communication of packets and commands between an application and a kernel module without protocol (e.g., IPv4, IPv6, TCP, or UDP) processing. Other types of sockets and APIs, however, may be used for packet capture instead of raw sockets.

In some embodiments, packet capture module208may compile the representation of the packet filter expression into bytecode or another format. Packet capture module208may then execute this bytecode for each packet it receives to determine whether the packet matches the specified filter. If the packet does not match the filter, the packet may be discarded. If the packet does match the filter, packet capture module208may provide the packet the packet capture application224. Thus, packet capture application224may provide the packet filter expression to packet capture module208at the beginning of a packet capture session, and may receive a stream of packets matching this filter.

D. Packet Capture Formats

Packet capture application may store the received packets in one of several possible formats. One such format is the PCAP (packet capture) format, illustrated inFIG. 3A. File300represents a series of N+1 captured packets in the PCAP format, stored in order of the time they were captured. PCAP header302is a data structure defined inFIG. 3B. Each of the N+1 captured packets may be preceded by a per-packet header, as well as all protocol header and payload bytes. An example per-packet header303is shown inFIG. 3C.

File300may be a binary file that can be stored within short-term storage (e.g., main memory) or long-term storage (e.g., a disk drive) of computing device100. In some cases, representations of the captured packets displayed in real-time on computing device100as packet capture occurs. Thus, later-captured packets may be added to file300while earlier-captured packets are read from file300for display. In other embodiments, file300may be written to long-term storage for later processing.

As noted above,FIG. 3Billustrates the contents of PCAP header302. There may be one instance of PCAP header302disposed at the beginning file300.

Magic number304may be a pre-defined marker of the beginning of a file with PCAP header302, and serves to indicate the byte-ordering of the computing device that performed the capture. For instance, magic number304may be defined to always have the hexadecimal value of 0xa1b2c3d4 in the native byte ordering of the capturing device. If the device that reads file300finds magic number304to have this value, then the byte-ordering of this device and the capturing device is the same. If the device that reads file300finds magic number304to have a value of 0xd4c3b2a1, then this device may have to swap the byte-ordering of the fields that follow magic number304.

Major version306and minor version308may define the version of the PCAP format used in file300. In most instances, major version306is 2 and minor version308is 4, which indicates that the version number is 2.4.

Time zone offset310may specify the difference, in seconds, between the local time zone of the capturing device and Coordinated Universal Time (UTC). In some cases, the capturing device will set this field to 0 regardless of its local time zone.

Timestamp accuracy312may specify the accuracy of any time stamps in file300. In practice, this field is often set to 0.

Capture length314may specify the maximum packet size, in bytes, that can be captured. In some embodiments, this value is set to 65536, but can be set to be smaller if the user is not interested in large-payload packets, for instance. If a packet larger than what is specified in this field is captured, it may be truncated to conform to the maximum packet size.

Datalink protocol316may specify the type of datalink interface on which the capture took place. For instance, this field may have a value of 1 for Ethernet, 105 for Wifi, and so on.

FIG. 3Cillustrates the contents of per-packet header303. As shown inFIG. 3A, there may be one instance of per-packet header303for each packet represented in file300. Each instance of per-packet header303may precede its associated packet.

Timestamp seconds320and timestamp microseconds322may represent the time at which the associated packet was captured. As noted above, this may be the local time of the capturing device or UTC time.

Captured packet length324may specify the number of bytes of packet data actually captured and saved in file300. Original packet length326may specify the number of bytes in the packet as the packet appeared on the network on which it was captured.

In general, captured packet length324is expected to be less than or equal to original packet length326. For example, if capture length314is 1000 bytes and a packet is 500 bytes, then captured packet length324and original packet length326may both be 500. However, if the packet is 1500 bytes, then captured packet length324may be 1000 while original packet length326may be 1500.

While the traditional system described in the context ofFIGS. 1 and 2may perform well in limited scenarios, it might not support high-speed packet capture in a robust fashion. For instance, modern Ethernet interface hardware support data rates of 10 gigabits per second, 40 gigabits per second, and 100 gigabits per second. Since traditional systems perform packet capture and filtering in software, the maximum speed of these systems is typically limited by the speed of processor102. If the hardware interfaces are receiving packets at line speed, processor102may be unable to process incoming packets quickly enough. Furthermore, processor102may be performing other tasks in parallel, such as various operating system tasks and tasks related to other application.

To that point, the number of processor cycles per packet may be insufficient even for fast processors. For example a 3.0 gigahertz multiprocessor with16cores only has about 322 cycles per packet when processing 64 byte packets at 100 gigabits per second. In more detail, the processor operates at an aggregate speed of 48,000,000,000 cycles/per second. The interface's 100 gigabits per second provides a maximum of 12,500,000,000 bytes per second. Assuming the worst case scenario of the smallest possible Ethernet packets (64 bytes each with a 12 byte inter-packet gap and an 8-byte preamble), there are about 148,809,523 packets per second arriving. Thus, the processor can use at most 322.56 cycles per packet. This is insufficient for sustained processing.

As a result, some packets may be dropped before they can be filtered or before they can be written to a file. Particularly, packets may be dropped if (i) the network interface hardware buffer fills up at a rate that is faster than its associated driver module can remove packets from it, (ii) any queue associated with packet capture module208fills up at a rate that is faster than packet capture module208can perform packet filtering operations, or (iii) any queue associated with packet capture application224fills up at a rate that is faster than packet capture application224can write the associate packets to a file system or display representations of these packets. Notably, writing to a file system on an HDD may involve significant overhead that slows the system's sustainable packet capture rate. Writing to an SSD is faster, but also can create a bottleneck if SSD speed is not taken into account.

This creates problems for applications that rely on accurate and complete packet capture. For instance, if packet capture application224is a network protocol analysis tool, missing packets may make debugging a network protocol to be difficult if not impossible. Further, if packet capture application224is an intrusion detection system, missing packets may effectively render this system unable to detect network attacks in a robust and timely fashion.

The next section describes the capture-direction procedures for an example high-speed packet capture system. This description follows the path of captured packets from the time they are received on a network interface until they are stored in non-volatile memory (e.g., an SSD without a traditional file system). The subsequent section describes how stored packets are read from non-volatile memory for further processing and/or display.

FIG. 4depicts an example computing device400customized for high-speed packet capture. In some embodiments, computing device400may include different components and/or its components may be arranged in a different fashion.

Host processors and dedicated system memory402may include one or more processors, each of which may be coupled to or associated with a dedicated unit of memory (e.g., several gigabytes of RAM). For instance, each processor and its associated unit of memory may be a non-uniform memory access (NUMA) node capable of accessing its own memory and memory in other NUMA nodes, as well as that of long-term packet storage404A and host operating system storage404B. A particular arrangement of NUMA nodes is depicted in the embodiment ofFIG. 7.

Notably, host processors and dedicated system memory402may have connections to system bus414and system bus416. System busses414and416may each be a peripheral component interconnect express (PCIe) bus, for example. InFIG. 4, system bus414communicatively couples host processors and dedicated system memory402to FPGA-based network interface406, management network interface410, and input/output unit412. Similarly, system bus416communicatively couples host processors and dedicated system memory402to long-term packet storage404A and host operating system storage404B. Nonetheless, other arrangement are possible, including one in which all of these components are connected by way of one system bus.

Long-term packet storage404A may include non-volatile storage, such as one or more SSDs. Notably, long-term packet storage404A may store captured packets in chunks thereof.

Host operating system storage404B may also include non-volatile storage, such as one or more solid state drives. Unlike long-term packet storage404A, host operating system storage404B may store the operating system and file system used by the processors of host processors and dedicated system memory402.

FPGA-based network interface406may be a custom hardware module that can house one or more 100 megabit per second, 1 gigabit per second, 10 gigabit per second, 25 gigabit per second, 40 gigabit per second, or 100 gigabit per second transceivers. FPGA-based network interface406may receive packets by way of these interfaces, and then capture and process these packets for storage. As suggested by its name, FPGA-based network interface406may be based on a field-programmable gate array or other digital hardware logic (i.e., an actual FPGA might not be used in all embodiments). Although Ethernet is used as the interface type for packet capture in the examples provided herein, other interface types may be possible.

Temporary packet storage memory408may include one or more units of RAM configured to hold packets captured by FPGA-based network interface406until these packets can eventually be written to a memory in host processors and dedicated system memory402. FPGA-based network interface406may connect to temporary packet storage memory408by way of one or more memory controllers.

Network management interface410may be one or more network interfaces used for connectivity and data transfer. For instance, while FPGA-based network interface406may house one or more high-speed Ethernet interfaces from which packets are captured, network management interface410may house one or more network interfaces that can be used for remote access, remote configuration, and transfer of files containing captured packets. For instance, a user may be able to log on to computing device400by way of network management interface410, and remotely start or stop a packet capture session.

Input/output unit412may be similar to input/output unit108, in that it may facilitate user and peripheral device interaction with computing device400. Thus, input/output unit412may include one or more types of input devices and one or more types of output devices.

In some embodiments, computing device400may include other components, peripheral devices, and/or connectivity. Accordingly, the illustration ofFIG. 4is intended to be for purpose of example and not limiting.

A. Example FPGA-Based Network Interface

FIG. 5depicts a more detailed view of FPGA-based network interface406and temporary packet storage memory408. Particularly, FPGA-based network interface406includes transceivers module500, physical ports module502, logical port module504, packer module506, external memory interface module508, and direct memory access (DMA) engine module510. Temporary packet storage memory408may include memory banks512, and may be coupled to external memory interface module508by one or more memory controllers. DMA engine module510may be coupled to system bus414, and may control the writing of packets (e.g., in the form of chunks of one or more packets) to this bus. InFIG. 5, captured packets generally flow from left to right, with possible temporary storage in temporary packet storage memory408.

FIG. 6Adepicts connectivity between transceivers module500, physical ports module502, and logical port module504, as well as components of physical ports module502.

Each transceiver600of transceivers module500may contain both a transmitter and a receiver that are combined and share common circuitry or a single housing. As noted previously, transceivers600may be 10 gigabit per second, 40 gigabit per second, or 100 gigabit per second Ethernet transceivers, for example. Each of transceiver600may also be coupled to a port602of physical ports502. This coupling may include a unit that performs Ethernet medium access control (MAC), forward error correction (FEC), and physical coding sublayer (PCS) functions (not shown).

Each port602may include delimiter604, cycle aligner606, expander608, reclocker610, NOP generator612, and first-in-first-out (FIFO) buffer614components. In some embodiments, ports602may include more or fewer components, and each port may be uniquely numbered (e.g., from 0 to n). Regardless, the flow of packets (and processing thereof) is generally from left to right.

Delimiter604may identify the beginning and end bits of an incoming Ethernet packet by detecting Ethernet preamble and epilogue delimiter bits. This sequence may be represented in hexadecimal as 0xFB 0x55 0x55 0x55 0x55 0x55 0x55 0xD5 (least-significant bit first ordering is used). The bit received immediately after this sequence may be the first of the Ethernet packet. Delimiter604may also record a nanosecond timestamp of when the first byte of each packet was received from a high accuracy clock source. This timestamp may be adjusted for propagation delay by a fixed offset.

Cycle aligner606may align arrange incoming packets so that there is a maximum of one packet per bus cycle (i.e., larger packets may require multiple cycles). As an example, 100 gigabit Ethernet may use four 128-bit busses from the MAC interface. These busses may be referred to as lanes0,1,2, and3. In some cases, there may be two packets (more precisely, parts of two packets) output from the MAC interface in a single bus cycle. For instance, lanes0-2may contain bits from packet n, while lane3contains bits from packet n+1. Cycle aligner606arranges these bits across two cycles. In a first cycle, lanes0-2contain bits from packet n, while lane3is null. In a second cycle, lanes0-2are null, while lane3contains bits from packet n+1.

Expander608aggregates and packs the bits aligned by cycle aligner606into a wider bus (e.g., a 2048-bit bus). Expander608does this so that the first bit of each packet begins in the same lane. Having a fixed location for the beginning of each packet makes downstream processing less complicated. In some embodiments, expander608may place each packet across sixteen 128-bit lanes, such that the first bit of the packet is disposed at the first bit-location of lane0.

Reclocker610may adjust the timing of packet processing from that of transceiver600to that of port602. In the case of 100 gigabit Ethernet, the reclocking is from 322 megahertz (Ethernet speed) to 250 megahertz (port speed). In the case of 10 gigabit Ethernet, the reclocking is from 156 megahertz (Ethernet speed) to 250 megahertz (port speed).

NOP generator612may generate bursts of single cycle full width packets, with a payload of 0x00 bytes (e.g., 240-byte synthetic null packets with a 16 byte header for a transfer size of 256 bytes) that can be used to flush the capture pipeline of FPGA-based network interface406all the way to long-term packet storage404A. NOP generator612may be triggered to do so either by inactivity (e.g., no packets being received for a pre-determined amount of time) or by way of an explicit request through software (such an interface not shown inFIG. 6A).

FIFO buffer614may hold a number of received packets in a queue until these packets can be read from port602by logical port module504.

FIG. 6Billustrates the components of logical port module504. These components are presented for purpose of example. More or fewer components may be present in such a logical port module. Similar to the previous drawings, the flow of packets (and processing thereof) is generally from left to right.

Port arbiter620is connected to FIFO buffer614for each of ports602. On each clock cycle, port arbiter620retrieves one or more packets from each of ports602—more precisely, from the respective instances of FIFO buffer614. If more than one of ports602has a packet ready in this fashion, port arbiter retrieves these packets in a pre-defined order (e.g., from the lowest port number to the highest port number).

Packet classifier622classifies each incoming packet based on pre-defined rules. The classifications may include two designations, drop and slice (explained below). The rules may include bit-wise logical “and” and “compare” operations on the first 64, 128, 256, or 512 bytes of the packet, for example. A total of 16-512 rules may be supported, and these rules may be software programmable. A packet may match multiple rules. As an example, if a packet matches one or more of the rules, it may be classified for slicing, but if the packet does not match any rules, it may be classified for dropping.

Packet dropper/slicer624may either drop or slice a packet based on the packet's classification. A dropped packet is effectively deleted and is no longer processed. A sliced packet is reduced in size—for instance, any bytes beyond the first 64, 128, 256, or 512 bytes of the packet may be removed. Doing so makes storage of packets more efficient when full packet payloads are not of interest.

Packet compressor626is an optional component that may compress a packet's header (e.g., Ethernet, IP, TCP, UDP headers) and/or payload, and replace that with the compressed version. When this occurs, packet compressor626may also set a flag bit in one of the packet's capture headers indicating that compression has been performed. In some embodiments, packet compressor626may use compression dictionary628. The latter may contain a list of common byte strings that are represented by shorter, unique encodings in compressed packets.

Back-pressure throttle630may apply back-pressure from downstream modules and/or components when those modules and/or components are unable to keep up with the incoming flow of packets. For instance, back-pressure may be applied when system bus414is temporarily congested and cannot transmit data at the requested rate. This back-pressure may be a signal from back-pressure throttle630to port arbiter620or one or more of FIFO buffers614to skip processing of incoming packets for one or more clock cycles. In the rare case where a packet is dropped, back-pressure throttle630may maintain counts of total dropped packets and counts per dropped packet for each back-pressure signal. These back-pressure signals are respectively received from DMA engine510(due to congestion on bus414), chunk aligner632, and padder636.

Chunk aligner632aligns a set of captured packets so that they can be packed into a chunk. Each chunk is 128 kilobytes to 32 megabytes in size, and holds such a set of captured packets such that no packet crosses a chunk boundary, and the first packet of a chunk begins at an offset of 0 within the chunk. Chunk aligner632may determine the amount of padding needed so that the last packet in a chunk fills any remaining space in that chunk.

Chunk statistics634collates statistics for the data within a chunk. These statistics include timestamps of the first and last packets within the chunk, the total number of packets within the chunk (possibly including separate counts of the total number of TCP packets and total number of UDP packets in the chunk), the total number of bytes within the chunk (not including padding), the total number of compressed bytes within the chunk, the number of packets classified to be dropped by packet classifier622, and various other internal performance metrics. These statistics are passed on to compressor statistics644(seeFIG. 6C).

Padder636adds the number of padding bytes specified by chunk aligner632to the last packet of a chunk. The padding bytes may be all 0's, and this padding may be applied after the last byte of the received packets.

Header addition638appends a custom header at the beginning of each packet. The contents of the custom header may be similar or the same as that of the PCAP per-packet header303. In alternative embodiments, the header may be 16 bytes in length and may consist of one or more of the following fields: a NOP field that may be set when the packet contains NOP data from NOP generator612, a frame check sequence (FCS) fail flag that may be set when the FCS the packet's Ethernet header indicates a corrupted packet, a pad flag that may be set when the chunk contains padding from padder636, a timestamp field that may contain the time (in nanoseconds and sourced from delimiter604) of when the packet was captured, a packet capture size field that may indicate the number of bytes of the packet that were actually captured, a packet wire size field that may indicate the actual size of the packet prior to capture, and a portID field that may identify the physical port on which the packet was received. Other fields are possible, and more or less fields may be present. The packet capture size may be less than the packet wire size when packet dropper/slicer624and/or compressor626is configured to reduce the size of captured packets.

FIG. 6Cillustrates the components of packer506. These components are presented for purpose of example. More or fewer components may be present in such a logical port module. Similar to the previous drawings, the flow of packets (and processing thereof) is generally from left to right.

Stream packer640may receive packets from header addition638. Stream packer640may arrange these packets into a packed byte stream that may be 512, 1024, 2048, or 4096 bits wide, for example, based on bus width. For instance, suppose that the bus is 2048 bits (256 bytes) wide. Data enters stream packer640at a rate of at most one packet per cycle. Suppose that an 80-byte packet n arrives during cycle0, an 80-byte packet n+1 arrives during cycle1, and a 128-byte packet n+2 arrives during cycle2. This sequence leaves at least half of the 2048-bit bus unused during each cycle.

Stream packer640arranges these packets so that the full bus is used, if possible, during each cycle. Thus, the first output cycle of stream packer640would include all of packet n, all of packet n+1, and the first 96 bytes of packet n+2, for a grand total of 2048 bits. The second output cycle of stream packer640would include the remaining 32 bytes of packet n+2, followed by any further packets. Stream packer640forms packets into chunks that are 128 kilobytes to 32 megabytes in size. Thus, each chunk may include multiple packets, perhaps hundreds or thousands of packets.

Compressor642may compress the packed byte stream from stream packer640. These compression operations are optional and may be omitted if compressor642is unable to compress packets into chunks at the incoming data rate. Instead, compressor642can, when it is overloaded, write the packets in a pass-through mode in order to maintain line-speed performance.

In some embodiments, a general compression scheme, such as Lempel-Ziv-Welch (LZW) may be used. While this scheme can increase the effective number of packets stored in long-term packet storage by a factor of 2 or 3, it may be too slow for line rate compression for data incoming from high-speed interfaces (e.g., 40 gigabits per second or 100 gigabits per second). A trigger for pass-thru mode may be when the input queue becomes full (or beyond a high water mark), then chunks bypass the compressor until the input queue reaches a low water mark.

Compressor statistics644receives information from chunk statistics634and provides further information from compressor642. This information may include the compressed payload size and a cyclic redundancy check (CRC) per chunk.

FIG. 6Dillustrates the components of external memory interface508. These components are presented for purpose of example. More or fewer components may be present in such a memory interface. Similar to the previous drawings, the flow of packets (and processing thereof) is generally from left to right (with a detour through memory banks512).

External memory interface508may serve to buffer incoming chunks in memory banks512. Doing so helps avoid congestion on system bus414that might otherwise cause these chunks to be dropped. System bus414may be too busy to transfer chunks due to usage by host processors and dedicated system memory402, input/output unit412, or other peripherals. This congestion may last anywhere from 10 microseconds to several milliseconds or longer.

External memory interface508may operate at the full-duplex line speed of the interface(s) through which packets are being captured. For example, if a 100 gigabit per second Ethernet interface is being used to capture packets, reading and writing between external memory interface508and memory banks512may take place at up to 200 gigabits per second (e.g., 100 gigabits per second reading and 100 gigabits per second writing).

Memory write module650may receive chunks from compressor642and write these chunks to memory banks512, by way of memory controllers652A,652B, and652C. Chunks may be written to memory in discrete blocks, the size of which may be based on the bus width between memory controllers652A,652B, and652C and external memory654A,654B, and654C. For each of these blocks, memory write module650may calculate a CRC, and store the respective CRCs with the blocks. In some embodiments, memory write module650may write these blocks across external memory654A,654B, and654C in a round robin fashion, or in some other way that roughly balances the load on each of external memory654A,654B, and654C.

Memory read module656may retrieve, by way of memory controllers652A,652B, and652C, the blocks from memory banks512, and reassemble these blocks into chunks. In doing so, memory read module656may re-calculate the CRC of each block and compare it to the block's stored CRC to determine whether the block has been corrupted during storage.

Although three memory controllers and three external memories are shown inFIG. 6D, more or fewer memory controllers and external memories may be used. Each memory controller may synchronize its refresh cycle so all external memory refresh cycles occur at the same time. This may improve memory throughput when multiple separate memory banks are used in unison.

FIG. 6Eillustrates the components of DMA engine510. These components are presented for purpose of example. More or fewer components may be present in a DMA engine. Similar to the previous drawings, the flow of packets (and processing thereof) is generally from left to right.

Chunk FIFO660is a buffer that receives chunks from memory read module656and temporarily stores these chunks for further processing by DMA engine510. Similarly, statistics FIFO662is another buffer that receives statistics from various units of FPGA-based network interface406for a particular chunk. These statistics may include, but are not limited to, data from chunk statistics634and compressor statistics644. This data may include, for example, first and last timestamps of packets within a chunk, a number of packets within a chunk, the compressed size of a chunk, and various FIFO levels and/or hardware performance metrics at the present clock cycle. Chunk FIFO660and Statistics FIFO662operate independently, although in practice (and by design) data in chunk FIFO660and statistics FIFO662usually refer to the same chunk.

Data from both chunk FIFO660and statistics FIFO662are read by DMA arbiter664. DMA arbiter664multiplexes this data from both FIFOs, as well as status updates from capture ring800(seeFIG. 8A). These status updates indicate the next memory location in capture ring800that is available for chunk storage. DMA arbiter664assigns the highest priority to processing status updates from capture ring800, the second highest priority to output from statistics FIFO662, and the lowest priority to chunks from chunk FIFO660.

System bus414may consist of multiple independent busses414A,414B, and414C. Although three busses are shown inFIG. 6E, more or fewer busses may be used. DMA output666schedules data from chunk FIFO660and statistics FIFO662to be written by way of PCIe interfaces668A,668B, and668C to busses414A,414B, and414C, respectively. For instance, DMA output666may multiplex and write this data as maximum sized bus packets (e.g., 256 bytes) to busses414A,414B, and414C according to a fair round-robin scheduler.

A DMA performance monitor (not shown) may be incorporated into either DMA arbiter664or DMA output666. For instance, if busses414A,414B, and414C are PCIe busses, this module may monitor their performance by determining the number of minimum credits, maximum credits, occupancies, stall durations, and so on for each bus. This includes the allocation of PCIe credits on each bus (for flow control on these busses) and the allocation of DMA credits for flow control related to capture ring buffer800of a NUMA node (seeFIG. 8A, below).

The latter mechanism may be based on a credit token system. For instance, one token may equate to a 256-byte write operation (a maximum sized PCIe write operation) to capture ring buffer800. DMA arbiter664maintains a number of DMA credits. This is initialized to be the number of entries in capture ring buffer800. Every time a full sized PCIe write operation is occurs, the DMA credit count is decremented. If the total number of DMA credits is zero, then back pressure is signaled which eventually leads to back pressure throttle630dropping packets. Also, when DMA credit is zero, no PCIe write operations are issued. Software operating on one of the NUMA nodes adds DMA credits after a chunk has been processed and removed from capture ring buffer800, essentially freeing that memory area so the hardware can write a new chunk into it.

B. Example Host Processor and Dedicated Memory Architecture

FPGA-based network interface406connects by way of system bus414to processor700. Processor700and memory702may be components of a first NUMA node. Similarly, processor704and memory706may be components of a second NUMA node which may be connected to the first NUMA node by way of a quick path interconnect (QPI) interface, or some other type of processor interconnect.

The second NUMA node may also be connected, by way of system bus416, to storage controller708. Like system bus414, system bus416may include multiple independent busses. This decoupling of the NUMA node communications further improves packet capture performance by separating the throughput and latency characteristics of writes from FPGA-based network interface406to memory702and writes from memory706to long-term packet storage404A.

In some embodiments, processor700may be referred to as a network interface processor (because processor700reads data packets from FPGA-based network interface406) and processor704may be referred to as a storage processor (because processor704writes data packets and/or chunks thereof to long-term packet storage404A). In various arrangements, processor700and processor704each may be able to read from and/or write to memory702and memory706.

Storage controller708may be a host bus adapter (HBA) controller, for example. Storage controller708may provide the second NUMA node with access to long-term packet storage404A. Long-term packet storage404A may include an array of n solid state drives, or some other form of non-volatile storage. In some embodiments, multiple storage controllers may be used to support a packet storage rate of 100 gigabits per second. The first and/or second NUMA node may further be connected to host operating system storage404B.

In summary, chunks of packets are written directly from FPGA-based network interface406to memory702. Processor700reads these chunks from memory702, and applies some additional processing such as generating CRCs and/or calculating chunk statistics. Processor700then writes the chunks to memory706. Processor700and/or processor704run input/output schedulers which instruct storage controller708to write, from memory706, the chunks to a specified location on one of the units of storage in long-term packet storage404A. Storage controller708responsively performs these writes. This sequence of operations is further illustrated inFIGS. 8A-8D.

FIG. 8Aillustrates example data structures for packet storage and management in memory702. Capture ring buffer800holds chunks transferred by DMA output666, and operates as a conventional ring buffer. Capture ring buffer may be 4 gigabytes in size in some embodiments, but can be of any size (e.g., 1, 2, 8, 16 gigabytes, etc.).

The ring buffers herein, such as capture ring buffer800, are usually implemented as fixed sized arrays of b entries, with pointers referring to the current head and tail locations. A producer writes a new entry to the current location of the tail, while a consumer removes the oldest entry from the head. These head and tail pointers are incremented modulo b for each read and write, so that the buffer logically wraps around on itself.

Chunk index buffer802may store information from statistics FIFO662(which ultimately originated at chunk statistics634and compressor statistics644among other possible sources) for each chunk in capture ring buffer800. Thus, this information may include timestamps of the first and last packets within the chunk, the total number of packets within the chunk, the total number of bytes within the chunk (not including padding), the total number of compressed bytes within the chunk, and so on.

Capture ring DMA status804A,804B, and804C memory locations respectively associated with busses414A,414B, and414C. Their contents can be used to control write access to capture ring buffer800, as described below.

Chunk processing queue806contains references to chunks in capture ring buffer800that are ready for writing to memory706. Use of this structure is also described below.

FIG. 8Billustrates example data structures for packet storage and management in memory706, as well as their relation to storage controller708and long-term packet storage404A. Capture write buffer810temporarily stores chunks transferred from capture ring buffer800. These chunks are then distributed across n units of non-volatile storage (SSD0-SSDn). In order to do so, each chunk is queued for writing to one of these units. This information is stored in I/O queue814. For each of the n units of non-volatile storage, I/O queue814contains a list of entries. These entries are populated to spread consecutive chunks over the available units. While only 3 units (SSDs) are shown inFIG. 8Bfor purpose of convenience, more units may be used. Chunk parity write buffer812queues redundancy data related to chunks.

For instance, SSD0entry0in SSD0write buffer816may refer to the first chunk (chunk0) in capture write buffer810, SSD1entry0in SSD1write buffer818may refer to the second chunk (chunk1) in capture write buffer810, and SSD2entry0in SSD2write buffer820may refer to the third chunk (chunk2) in capture write buffer810. Similarly, SSD0entry1in SSD0write buffer816may refer to the fourth chunk (chunk3) in capture write buffer810, SSD1entry1in SSD1write buffer818may refer to the fifth chunk (chunk4) in capture write buffer810, and SSD2entry1in SSD2write buffer820may refer to the sixth chunk (chunk5) in capture write buffer810. More entries per SSD may be used. According to this mapping of chunks to SSDs, for a system with d SSDs, chunk c maps to SSD s entry e, where s=c mod d and e=└s/d┘ or the FIFO producer index of SSD0write buffer816/SSD1write buffer818/SSD2write buffer820.

The processing of chunks and related data may take place according to the following description. DMA output666may write chunks from chunk FIFO660to respective locations in capture ring buffer800, while data from statistics FIFO662may be written to respective locations in chunk index buffer802. DMA output666may also broadcast updates to capture ring DMA status804A,804B, and804C by way of busses414A,414B, and414C. The data written may be pointers to the next available location in capture ring buffer800. Thus, the contents of capture ring DMA status804A,804B, and804C might not take on the same value when at least one of busses414A,414B, and414C is operating more slowly than the others (e.g., it is congested or stalled). This mechanism also serves to allow multiple simultaneous writes to capture ring buffer800and chunk index buffer802without using memory locking.

Processor700may repeatedly read capture ring DMA status804A,804B, and804C for the location of the oldest transferred chunk. The oldest transferred chunk may be the chunk in the location of capture ring buffer800pointed to by the “lowest” of any of capture ring DMA status804A,804B, and804C, taking into account the fact that these values wrap around from the end to the beginning of the ring buffer as they advance. This maintains the completion of all writes into capture ring buffer800for a specific chunk, regardless of any splitting or re-ordering by DMA output666or system busses414A,414B, or414C due to system congestion and stalling.

Once this chunk is identified, processor700may allocate an entry in I/O queue814(e.g., SSD0entry1, SSD1entry0, etc.) according to the mapping of chunks to SSDs described above. Further, processor700may allocate a new location in which to store the chunk on the selected SSD. Processor700may also place, into chunk processing queue806, the memory location of the chunk, the memory location of the associated chunk index, and an indication of the entry in I/O queue814.

For every set of j consecutive chunks processed in this manner (where j is anywhere from 2 to 100), r parity chunks (where r is anywhere from 1 to 5) may be generated for purposes of redundancy. For instance, when a non-overlapping set of j consecutive chunks have been processed for representation in chunk processing queue806, one of processor700or processor704may calculate one or more Reed-Solomon codes (or other error-correcting codes) based on these chunks. These codes form the parity chunks, and may be stored in one or more parity SSDs (not shown). The parity SSDs may be written to in a fashion similar to that ofFIG. 8Band described below. This redundancy procedure is akin to that of RAID5 or RAID6, but supports a higher level of recovery. In principle the system can recover from the failure of a greater number of SSDs.

Chunk parity write buffer812is where parity data is stored and queued for write operations to parity SSDs. This process is similar to that of writing chunks to SSDs, except the parity data is handled by the processor and is not used with capture ring buffer800or capture write buffer810.

Regardless, processor700, processor704, or both may perform the following set of operations in order to transfer chunks in capture ring buffer800of memory702to capture write buffer810in memory704. In some cases, multiple processors may operate in parallel on different chunks.

First, a processor reads the head of chunk processing queue806to obtain the location of the next chunk in capture ring buffer800, its associated index in chunk index buffer802, and its target entry in I/O queue814. Based on the target entry, the processor writes this chunk to the specified memory location in capture write buffer810.

Then, from the target entry in I/O queue814, the processor determines the SSD and the location therein at which the chunk is to be stored. The processor issues a command instructing storage controller708to write the chunk from its memory location in capture write buffer810to this location in the designated SSD. For instance, if the chunk is referred to by SSD0entry1of SSD0write buffer816, the chunk is written to SSD0.

Then, a CRC is calculated over the entire chunk. This CRC enables the integrity of the chunk's data in non-volatile memory to be validated at any time in the future. The value of the CRC, the location of the chunk as stored on the designated SSD, as well as the entry related to the chunk in chunk index buffer802, are written to host operating system storage404B. Notably, this allows the chunk to be found through a simple lookup in host operating system storage404B rather than having to search the SSDs for the chunk. Since entries in chunk index buffer802are much smaller than their associated chunks, this makes finding a particular chunk an inexpensive procedure. Other chunk statistics may also be written to host operating system storage404B.

When storage controller708completes writing the chunk (as well as possibly other chunks that are queued for writing) to an SSD, it writes an indication of such to an I/O queue completion buffer (not shown) associated with I/O queue814. One of processor700or704may monitor the I/O queue completion buffer to determine when the write completes. After write completion is detected, the processor may update the entry related to the chunk in host operating system storage404B to indicate that the chunk has been committed to storage.

FIG. 8Cdepicts relationships between the data structures ofFIGS. 8A and 8B. In particular,FIG. 8Cincludes example chunk822and example chunk index824. Chunk822contains T+1 captured packets, ordered from least-recently captured (packet0) to most-recently captured (packet T). Chunk index824is associated with chunk822, and contains (among other information) a timestamp representing when packet0was captured, a timestamp representing when packet T was captured, and the number of packets in chunk822(T+1).

As described above, chunk822and chunk index824may be transferred by way of DMA to capture ring buffer800and capture index buffer802, respectively. Any transfer or copying of data may be represented with a solid line inFIG. 8C. On the other hand, relationships between data may be represented with dotted lines.

An entry826is added to chunk processing queue806. This entry refers to the locations of both chunk822in capture ring buffer800and chunk index824in capture index buffer802, as well as a location in I/O queue814that is entry y in the queue for SSDx. A processor copies chunk822from capture ring buffer800to a location in capture write buffer810that is associated with entry y in the queue for SSDx. As part of processing the write queue for SSDx, the processor also instructs a storage controller to write chunk822to SSDx. The format used to store chunks in long-term storage, such as an SSD, may vary from the PCAP format described in reference toFIG. 3.

The processor further copies chunk index824and the CRC and SSD storage location of chunk822to host operating system storage404B. As steps of this procedure complete, locations in capture ring buffer800, capture index buffer802, and capture write buffer810used for temporarily storing chunk822and chunk index824may be freed for other uses.

This arrangement provides for high-speed capture and storage of data packets. Particularly, sustained rates of 100 gigabytes per second can be supported. The end to end storage system described herein does so by operating on chunks rather than individual packets, carefully aligning chunks as well as packets within chunks for ease of processing, pipelining chunk processing so that multiple chunks can be processed in parallel, copying each chunk only once (from memory702to memory706), writing chunks sequentially across an array of SSDs (or other storage units) to increase sequential write performance over writing sequentially to the same SSD, and prioritizing chunk writing operations over other operations.

Notably, when writing to a particular SSD, each chunk is written to a sequentially increasing location. This limits SSD stalls due to internal garbage collection and wear-leveling logic.

C. Example Packet Capture Operations

FIG. 8Dis a flow chart illustrating an example embodiment. The process illustrated byFIG. 8Dmay be carried out by one or more processors and memories coupled to a network interface and storage controller. The storage controller may, in turn, be coupled to long-term packet storage. The network interface may receive packets and arrange these packets into chunks.

The embodiments ofFIG. 8Dmay be simplified by the removal of any one or more of the features shown therein. Further, these embodiments may be combined with features, aspects, and/or implementations of any of the previous figures or otherwise described herein.

Block830may involve receiving, by a first memory and from a network interface, a chunk of packets and a chunk index. The chunk may contain a plurality of packets that were captured by the network interface, and the chunk index may contain timestamps of the first and last packets within the chunk as well as a count of packets in the chunk. The network interface unit may include one or more Ethernet interfaces, each with a line speed of at least 10 gigabits per second.

The count of packets in the associated chunk indexes may include counts of TCP packets in the associated chunks and/or counts of UDP packets in the associated chunks. In a more general case, the counts of packets in the associated chunk indexes may include a plurality of independent counters relating to user programmable packet classifiers in the associated chunks.

In some embodiments, the size of each of the chunks is fixed and identical. Each of the chunks may contain an integer number of packets, and unused space in any of the chunks may be filled with padding bytes.

Block832may involve storing the chunk in a first ring buffer of the first memory and storing the chunk index in an index buffer of the first memory.

Block834may involve allocating, by a first processor coupled to the first memory, an entry for the chunk in an I/O queue of a second memory and an entry for the chunk in a chunk processing queue of the first memory.

Block836may involve reading, by the first processor, the chunk processing queue to identify the chunk.

Block838may involve copying, by the first processor, the chunk from the first ring buffer to a location in a second ring buffer of the second memory. The location may be associated with the allocated entry in the I/O queue.

Block840may involve instructing, by a second processor coupled to the first processor, to the second memory, and to a storage controller, the storage controller to write the chunk to one of a plurality of non-volatile packet storage memory units coupled to the storage controller. The first processor and the first memory may be part of a first NUMA node, and the second processor and the second memory may be part of a second NUMA node. The plurality of non-volatile packet storage memory units may include a plurality of SSDs.

In some embodiments, the first processor and the first memory are communicatively coupled to the network interface unit by way of a first system bus, and the second processor and the second memory communicatively coupled to the plurality of non-volatile packet storage memory units by way of a second system bus. The network interface unit may include a DMA engine that writes chunks to the first memory by way of the first system bus. The network interface unit may also include a back-pressure throttle that causes delay or dropping of received packets when the DMA engine detects congestion on the first system bus.

Block842may involve writing, by the first processor or the second processor, the chunk index to a file system that is separate from the plurality of non-volatile packet storage memory units.

In some embodiments, the first processor or the second processor may also be configured to, for a group of the chunks that are consecutively placed in the chunk processing queue: calculate one or more parity chunks by applying an error-correcting code to the group of chunks, store the one or more parity chunks in a chunk parity write buffer of the second memory, and write the one or more parity chunks across one or more non-volatile parity storage memory units that are separate from the plurality of non-volatile packet storage memory units.

In addition to storing chunks of packets, computing device400may also be able to retrieve specific packets from particular stored chunks of packets. These retrieved packets may then be converted into a format, such as the PCAP format, that is compatible with available packet analysis tools.

For instance, a number of chunks of packets may be stored in long-term packet storage404A and associated chunk indexes may be stored in host operating system storage404B. A filter expression may be received. For instance, the filter expression may be provided by a user or read from a file. The filter expression may specify a time period.

Either one of processors700or704may look up matches to this filter in the chunk indexes stored in host operating system storage404B. For instance, if the filter specifies a particular time period (e.g., defined by a starting timestamp and an ending timestamp), the matched chunk indexes will be those associated with chunks that contain packets captured within the particular time period. A binary search over the ordered timestamps in the chunk index may be used to locate specific chunks.

Each matched chunk index contains a reference to a storage location, in long-term packet storage404A, of its associated chunk. Based on these locations, the processor can instruct storage controller708to retrieve these chunks. A CRC calculation may be run against each chunk and compared to the CRC calculation in the associated chunk index. If these values do not match, the chunk may be discarded and full chunk data may be re-calculated using the error correcting parity information.

After the CRC is validated, the chunks may be decompressed (if compression had been applied), and individual packets within the chunks that match the filter may be identified. These packets may be extracted from the chunks and stored in a format that is supported by packet analysis tools (e.g., the PCAP format).

FIG. 9is a flow chart illustrating an example embodiment. The process illustrated byFIG. 9may be carried out by one or more processors and memories coupled to a network interface and storage controller. The storage controller may, in turn, be coupled to long-term packet storage. The network interface may receive packets and arrange these packets into chunks.

Block900may involve obtaining a packet filter specification, wherein the packet filter specification contains representations of a time period and a protocol.

Block902may involve applying the packet filter specification to a plurality of chunk indexes stored in a file system. The plurality of chunk indexes may be respectively associated with chunks of captured packets stored in a plurality of non-volatile packet storage memory units separate from the file system. The plurality of chunk indexes may include representations of respective capture timestamps and protocols for the captured packets within the chunks. Application of the packet filter specification may identify a subset of chunk indexes from the plurality of chunk indexes that contain packets matching the packet filter specification.

Block904may involve, for the subset of chunk indexes, retrieving the associated chunks from the plurality of non-volatile packet storage memory units.

Block906may involve applying the packet filter specification to each packet within the associated chunks. Application of the packet filter specification may identify a subset of the packets that match the packet filter specification.

Block908may involve writing the subset of packets to the file system or output queue. This file system may be local or remote. In some cases, the output queue may be an operating system pipe to another application.

IV. High-Speed Replay of Captured Data Packets

In addition to reading packets from long-term storage404A (or magnetic long-term storage for which long-term storage404A acts as a cache), the data packets stored therein may be replayed on a network. For example, various devices on a production network may exhibit failures when attempting to carry out transactions. Thus, computing device400may be used to capture data packets comprising such transactions. As noted above, these data packets may be captured at very high speeds (e.g., 10 gigabits per second, 40 gigabits per second, or 100 gigabits per second) by the embodiments herein. Similar or the same hardware embodiments may be used to replay the captured data packets at their original speed, faster, or slower. The replay may take place on a different network, such as a laboratory or test network, in order to avoid unnecessary disruption of the production network.

FIGS. 10A, 10B, 10C, and 10Dillustrate a processing pipeline for data packet replay. These figures essentially depict the same or similar hardware as that ofFIG. 4, and focus on how data packets stored in long-term packet storage404A are provided to host processors and dedicated system memory402, FPGA-based network interface406, and then onto physical network links.

To that point, inFIG. 10A, long-term packet storage404A may store data packets in 256 kilobyte chunks, where each chunk contains some number of packets all of which are followed by padding up to the 256 kilobyte boundary. In general, however, chunks can be of other sizes, and 256 kilobytes is used herein as a point of reference. Chunks could be, for example, 64 kilobytes, 128 kilobytes, 512 kilobytes, or 1 megabyte.

Storage CPUs1000may read chunks from long-term packet storage404A into shared producer queue1002. This queue may be used in a FIFO fashion. Storage CPUs1000may be one or more processors dedicated or partially dedicated to this procedure. In some embodiments, storage CPUs1000are from host processors and dedicated system memory402, and shared producer queue1002is in memory (RAM) attached thereto. But other variations are possible.

Prior to or during writing chunks into shared producer queue1002, each chunk has a unique sequence number appended thereto. In examples, sequence numbers may begin at0and increment sequentially. As shown inFIG. 10A, sequence number0is associated with chunk0, sequence number1is associated with chunk1, and sequence number2is associated with chunk2. The sequence numbers may remain associated with their chunks until the chunks are serialized by FPGA-based network interface406.

A pool of n worker CPU sets (labelled0to n−1 inFIG. 10A) read chunks from shared producer queue1002. The chunks may be read individually and effectively in a random or semi-random fashion based on workload. For example, each CPU set may read the next available chunk on shared producer queue1002.FIGS. 10A-10Dassume round-robin assignments of chunks to CPU sets, but this need not be the case.

Each CPU set may be a pair of processors arranged as shown inFIG. 7—each a NUMA node associated with its own memory (e.g., RAM and/or processor cache). One of these nodes may be a storage node, the processor of which reads chunks from shared producer queue1002, and an interface node, the processor of which provides chunks to FPGA-based network interface406. But other arrangements are possible.

For example, the processor of storage node1004A may read a chunk from shared producer queue1002, and store the chunk in its memory. Similarly, the processors of storage nodes1004B and1004C may read further chunks from shared producer queue1002into their respective memories.

Once stored locally to a CPU set, the chunk may be processed, e.g., by processing steps1006A,1006B, or1006C. This processing may be carried out by either processor of the CPU set (e.g., the storage node processor or the interface node processor).

Some of this processing may include rewriting the MAC and/or IP addresses of the packets to be topologically correct for the network on which the data packets are being replayed. Control of mappings from existing MAC and/or IP addresses may be specified on a command line, a script, or in a configuration file, among other options. For example, the mapping “rewrite srcIP 192.168.1.* to 10.1.1.*” may change the source IP addresses of any data packets being replayed from the 192.168.1.0/24 subnet to the 10.1.1.0/24 subnet. The final octet may remain the same. Other mappings are possible. Source and destination MAC addresses, as well as source and destination IP addresses, may be mapped in this fashion. In some embodiments, MAC addresses in data packets may be mapped to MAC addresses assigned to the ports of FPGA-based network interface406.

Other processing may include rewriting the timestamps of the data packets (e.g., as appearing in the associated PCAP metadata). These timestamps control the inter-packet intervals that FPGA-based network interface406will use between transmissions of data packets. These timestamps may be converted from absolute to relative (e.g., how many nanoseconds to wait from transmission of the previous data packet before transmitting the current data packet). Further, a multiplicative factor may be applied to the relative timestamps. This multiplicative factor may effectively speed up or slow down the replay (e.g., a multiplicative factor of ½ doubles the replay speed, while a multiplicative factor of 2 halves the replay speed). Alternatively, a fixed inter-packet interval (e.g., 10 nanoseconds) can be written to the timestamps. In some embodiments, the inter-packet interval may be converted to a multiple of the clock cycle rate of FPGA-based network interface406. For instance, if the clock cycle is 3.2 nanoseconds and the inter-packet interval is 100 nanoseconds, the interval is 31.25 clock cycles. It may be rewritten as 31 clock cycles (99.2 nanoseconds in this case), which represents a rounding of 31.25 clock cycles to the nearest integer.

When processing completes, chunks are written to memory of the associated interface nodes. For example,FIG. 10Ashows chunks from storage node1004A undergoing processing1006A and then being stored at interface node1008A. Similarly, chunks from storage node1004B undergo processing1006B and are then stored at interface node1008B, and chunks from storage node1004C undergo processing1006C and are then stored at interface node1008C.

FIG. 10Bshows how these interface nodes write chunks to FPGA-based network interface406. In particular, FPGA-based network interface406may include a total of n queues. Thus, interface node1008A writes to queue1010A, interface node1008B writes to queue1010B, and interface node1008C writes to queue1010C, for example. These queues may also be operated in a FIFO fashion. Once a chunk is written to one of these queues, it may be processed exclusively by FPGA-based network interface406.

By having each CPU set write to its own chunk processing queue, load on the CPU-based processors is decreased—as FPGA-based network interface406performs the serialization of chunks, additional processing resources are not required. Further, having 2-16 CPU sets working on processing and/or modifying chunks helps to achieve high data rates (on the order of 100 gigabits per second and/or 148 million packets per second throughput). No locking or synchronization between the worker threads on the CPU sets is required, which reduces delays and increases throughput.

Serializer1012of FPGA-based network interface406checks each of the n queues for a chunk with the next sequence number. For example, serializer1012may begin by searching the queues for sequence number0, then sequence number1, and so on, incrementing by 1. Once a threshold number of the next sequential chunks are located in this fashion, serializer1012forms serialized address list1014, which contains the physical memory addresses (in the queues) of these chunks. Serializer1012then provides serialized address list1014to DMA fetch engine1016. DMA fetch engine1016conducts a DMA transfer of these chunks to onboard memory FIFO1018. This results in all chunks being arranged in order of their sequence numbers in onboard memory FIFO1018.

Notably, solid arrows onFIG. 10Brepresent data transfer paths while dashed arrows represent control paths. But other paths may be possible.

Turning toFIG. 10C, chunk unpacker1020reads chunks from onboard memory FIFO1018and unpacks these chunks into the individual data packets therein. As described previously, each chunk may be a fixed size (e.g., 256 kilobytes), contain a number of data packets, and contain padding at the end to align the chunk on the fixed size boundary. The fixed chunk size makes the DMA fetching fast and efficient.

In some embodiments, chunk unpacker1020may read packets using a different size bus than its uses to write packets. For example, the bus between onboard memory FIFO1018and chunk unpacker1020may be 512 bits wide, while the bus between chunk unpacker1020and FCS/CRC generator1022may be 2048 bits wide.

The data packets may contain metadata that was added during the capture process, such a timestamp, length of the data packet, length of the captured portion, and physical port number on which the data packet was captured.

Regardless, individual data packets are received by FCS/CRC generator1022. FCS/CRC generator1022performs optional updates of the MAC FCS and/or IP checksum of each packet when MAC and/or IP addresses have been rewritten. In some embodiments, only the MAC FCS is updated to save time—a valid MAC frame for each data packet is more important for most testing purposes than a valid IP checksum. FCS/CRC generator1022may use one or more flags in the respective metadata of data packets to determine whether to update the MAC FCS and/or IP checksum.

FCS/CRC generator1022provides the data packets to port selector1024. Port selector1024, in turn, determines one of m possible physical output ports to which the each data packet is routed. In some embodiments, m is 2, 4, or 8. Port selector1024uses the physical port number from the respective metadata to route the data packets to a physical output port. Thus, if the metadata of a data packet indicates that it was received on physical port0, port selector1024will route the data packet to physical output port0.

FIG. 10Ddepicts the paths for each of these m physical output ports. Each of these paths may be identical aside from the port on which the data packets traversing the path will exit.

Retimers1026A,1026B,1026C add integer clock cycle delays between packets as alluded to above. NOP removers1028A,1028B,1028C removes any NOP data packets from the output stream. NOP data packets may be indicated as such by a flag in the metadata. NOP generation is used to flush packets down the output port. It is a simple way to ensure data has been output on the physical port. The capture embodiment has the same mechanism except in the reverse direction.

Framers1030A,1030B,1030C convert the data packets into the native format of the PCS or MAC IP core in FPGA-based network interface406. This may involve converting the data packets to XGMII (10 G), XLGMII (40 G) or CGMII (100 G). PCS or MAC IP cores1032A,1032B,1032C convert the data packets to a high speed serial link, such as 10 Gbps, 4×10 Gbps (40 G), or 4×25 Gbps (100 Gbps). Transceivers1034A,1034B,1034C convert the high speed serial link to either copper or fiber optic signals. Physical output ports1036A,1036B,1036C serve to connect the FPGA-based network interface406to one or more wires or cables over which the data packets are transmitted. During any of these steps, metadata may be removed from the data packets so that the data packets only consist of the MAC frame and its payload.

FIG. 11is a flow chart illustrating an example embodiment. The process illustrated byFIG. 11may be carried out by one or more processors and memories coupled to a network interface as described herein. In some cases, all components involved in the process may be within a single computing device. In other cases, some components may be distributed across two or more computing devices.

Block1100may involve carrying out, by one or more processors, (i) reading of chunks of data packets from non-volatile memory, wherein the chunks are associated with sequence numbers, and (ii) storing of the chunks in a shared producer queue of the non-volatile memory in order of the sequence numbers.

Block1102may involve carrying out, by an array of n sets of processors, (i) reading of the chunks from the shared producer queue, (ii) re-writing one or more network addresses contained within the data packets of the chunks to create modified chunks, and (iii) writing the modified chunks to queues.

Block1104may involve carrying out, by an FPGA-based network interface containing the queues and m physical ports, (i) reading of the modified chunks in order of their sequence numbers into onboard volatile memory, (ii) unpacking of the modified chunks into the data packets contained therein, (iii) generation and writing of updated checksums to the data packets, (iv) respective selection of output ports for each of the data packets, wherein the output ports are from the m physical ports, and (v) transmission of the data packets from the output ports that were respectively selected.

In some embodiments, each of the n sets of processors contains a storage node and an interface node, the storage node comprising a storage processor and a first unit of volatile memory, the interface node comprising an interface processor and a second unit of volatile memory. The storage processor reads the chunks from the shared producer queue into the first unit of volatile memory, either the storage processor or the interface processor re-writes the one or more network addresses, and interface processor writes the modified chunks from the second unit of volatile memory to the queues.

In some embodiments, each data packet is associated with metadata including at least one of: a flag indicating whether the one or more network addresses in the data packet have been re-written, a number of a physical port through which the data packet was captured, or a timestamp indicating a time at which the data packet was captured.

In some embodiments, generating and writing updated frame check sequences occurs in response to determining that the flag indicates that the one or more network addresses in the data packet have been re-written.

In some embodiments, selecting output ports for each of the data packets comprises selecting, as output port for the data packet, the physical port associated with the number.

In some embodiments, the FPGA-based network interface is also configured to convert the timestamp from an absolute time to a relative time, wherein the relative time represents an inter-packet interval between capture of the data packet and capture of a most recently previous data packet on the same physical output interface port.

In some embodiments, the relative time is represented as a number of clock cycles of a component of the FPGA-based network interface.

In some embodiments, converting the timestamp from the absolute time to the relative time comprises applying a multiplicative factor to the relative time.

In some embodiments, transmitting the data packets from the output ports comprises delaying transmission the data packets in accordance with the relative time of each of the data packets.

In some embodiments, the array of n sets of processors has access to a mapping between pairs of MAC addresses or pairs of IP addresses, and re-writing the one or more network addresses occurs based on the mapping.

In some embodiments, the mapping is received by way of a command line interface or a configuration file.

In some embodiments, the non-volatile memory comprises SSDs, HDDs, or both.

In some embodiments, each of the queues is respectively dedicated to one of the n sets of processors.

The computer readable medium can also include non-transitory computer readable media such as computer readable media that store data for short periods of time like register memory and processor cache. The computer readable media can further include non-transitory computer readable media that store program code and/or data for longer periods of time. Thus, the computer readable media may include secondary or persistent long term storage, like ROM, optical or magnetic disks, compact-disc read only memory (CD-ROM), for example. The computer readable media can also be any other volatile or non-volatile storage systems. A computer readable medium can be considered a computer readable storage medium, for example, or a tangible storage device.