Patent Description:
Packet-based data networks continue to grow in importance, and it is often desirable to monitor network traffic associated with these packet-based networks. For certain network packet communication systems, packet flow statistics are collected and reported for network packet flows. IPFIX (IP Flow Information eXport) is a protocol standard associated with such collection and reporting of statistics for network packet flows. IPFIX is based upon a prior protocol called NetFlow that was developed by Cisco Systems.

<FIG> (Prior Art) is a block diagram of an example embodiment <NUM> for a network communication system where packet flow statistics are collected and reported using the IPFIX protocol standard. A network <NUM> includes a number of different network connected devices that are communicating with each other using a number of different packet flows. At least a portion of these packet flows are routed by the network router <NUM>, which can include a number of different input/output (I/O) ports that are used to receive and send packets. For the embodiment <NUM>, packets received by the network router <NUM> are represented by input packets <NUM>, and packets sent by the network router <NUM> are represented by output packets <NUM>. A switch <NUM> within the network router <NUM> receives the input packets <NUM> from network sources and routes them to the appropriate network destinations through output packets <NUM>. These input and output packets <NUM>/<NUM> are assumed to include packets within a number of different packet flows for the network <NUM>.

The IPFIX engine <NUM> also receives the input packets <NUM> and processes the packets to collect flow statistics associated with packet flows represented within the input packets <NUM>. These packet flow statistics are stored in a flow table <NUM>. When the termination of a particular packet flow is detected by the IPFIX engine <NUM>, the IPFIX engine <NUM> sends a packet reporting the data record for the packet flow that was stored in the flow table <NUM>. These IPFIX report packets <NUM> are sent to an IPFIX collection server <NUM> where the flow data statistics provided by the IPFIX report packets <NUM> are aggregated and stored in a flow statistics database <NUM>. The IPFIX collection server <NUM> can also include an IPFIX controller that controls operation of the IPFIX collection server <NUM>. A user interface <NUM> can also be included within the collection server <NUM> and allows external uses, such as network managers, to access, view and analyze the data within the flow statistics database <NUM>.

<FIG> (Prior Art) is a diagram of an example embodiment for the flow table <NUM> that is used by the IPFIX engine <NUM> to collect and store flow data associated with the packet flows <NUM> within the input packets <NUM> as represented by FLOW1, FLOW2,. For each of the packet flows <NUM>, a five-tuple flow identifier <NUM> is stored that includes a source address (SIP), a destination address (DIP), a protocol type (TYPE), a source port (S-PORT), and a destination port (D-PORT). For each of the packet flows <NUM>, flow data is also collected and stored. This collected data <NUM> includes a start time (START), an end time (END), number of bytes (#BYTES), and a number of packets (#PACKETS). It is noted that the source and destination addresses (SIP/DIP) can be, for example, source and destination IP (Internet Protocol) addresses. The protocol type represents the communication protocol used for the packet flow such as TCP (Transmission Control Protocol), UDP (User Datagram Protocol), SCTP (Stream Control Transmission Protocol), and/or other communication protocols. The source and destination ports (S-PORT/D-PORT) can be, for example, communication ports used at the packet source and destination for the packet flow. When the IPFIX engine <NUM> determines that a packet flow has ended, the flow record for that packet flow is sent in a report packet to the collection server as indicated by arrow <NUM>.

Disadvantages to implementing IPFIX processing within the network router <NUM>, however, include the memory space required for the flow table <NUM> and the additional processing resources required for the IPFIX engine <NUM>. The main performance bottleneck is the memory bandwidth and size required for the flow table <NUM>.

The European Patent Application <CIT> discloses a lookup scheme in which a tuple representing a plurality of flow properties is parsed into multiple subtuples for application in recursive lookups. A first subtuple including a first subset of bits from the tuple is applied to the flow information database and returns a result including a nickname having a smaller bit count than the first subtuple. A second subtuple including a second subset of bits from the tuple and the nickname are combined and applied to the flow information database.

United States Patent <CIT> discloses load balanced transport of best efforts traffic together with delay-bounded traffic over a multilink bundle combining fragmentation and fragment distribution for best efforts packets with per-flow balancing for delay-bounded traffic.

The invention is carried out as described in the appended claims, namely: method claim <NUM>, system claim <NUM> and related claims <NUM>-<NUM> and <NUM>-<NUM>.

It is noted that the appended drawings illustrate only example embodiments of the invention and are, therefore, not to be considered limiting of its scope, for the invention may admit to other embodiments, as far as they fall within the scope of the appended claims.

Network packet forwarding system and method are disclosed for hash-based selection of network packets for packet flow sampling in network communication systems. System and method are disclosed for hash-based selection of network packets for packet flow sampling in network communication systems. For the disclosed embodiments, input packets associated with packet flows within a network communication system are received by a hash-based sampler. The hash-based sampler then generates hash values for the input packets based upon fields within the input packets. These fields are selected to identify packet flows for the input packets. The hash values for the input packets are then compared to a mask. The mask is configured to determine a subset of packet flows for which to forward packets. Based upon this comparison, certain input packets are selected to be forwarded for further processing, and non-selected packets are discarded. For certain embodiments, the further processing includes processing the selected input packets from the subset of packet flows to generate flow statistics data for the selected input packets. The flow statistics data can include data collected according to the IPFIX (IP Flow Information eXport) protocol. As indicated above, IPFIX is based upon a prior protocol called NetFlow that was developed by Cisco Systems. While the discussions herein refer primarily to the IPFIX protocol, it is understood that the disclosed embodiments are also useful for other protocols for the collection of packet flow statistics data including, but not limited to, NetFlow Version <NUM>, other NetFlow versions, and/or other protocols. Different features and variations can be implemented, as desired, and related systems and methods can be utilized, as well.

As described herein, processing and memory resources become strained when network connected devices process network packets within packet flows, for example, when processing network packets to collect packet flow statistics. One way to reduce processing in generating packet flow statistics, for example using the IPFIX (IP Flow Information eXport) protocol standard, is to use packet sampling. Instead of processing every packet, only one out of every "N" number of packets is randomly selected to be processed for packet flow statistics. If pure random sampling were used, however, the random sampling would be expected to affect all packet flows equally, and in most cases the number of packet flows detected and tracked in a flow table would still be the same. Further, if an attempt is made to ignore all packets within selected flows to reduce the number of flows to be tracked, details for these selected flows must still be stored in a flow table or a separate state table so that future packets can be matched to these selected flows and then subsequently ignored if matches are found. Thus, memory resources are still required to keep track of the details for these selected flows for which later packets will be ignored.

For the embodiments described herein, hash-based packet flow sampling is implemented to provide a stateless technique for ignoring packets within a subset of packet flows without requiring the maintenance of flow information for ignored flows in a flow table or a separate state table. Further, the percentage of flows ignored can be adjusted by using a mask to select which packet flows are ignored and which packet flows are processed for packet flow statistics. In particular, the ratio of the number of bits required in this mask to the number of bits set as "don't care" bits is used to determine the percentage of ignored packets flows within the network traffic being monitored. The bit length of the generated hash values and mask can also be used to adjust the available granularity of this packet flow selection. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems.

<FIG> is a block diagram of an example embodiment <NUM> for a hash-based sampler <NUM> that selects network packets from a subset of packet flows to be forwarded for further processing within a network communication system. As described herein, the hash-based sampler <NUM> operates to forward packets for further processing only if they fall within a subset of packet flows within the input packets <NUM> being collected and monitored for flow statistics. For example embodiment <NUM>, input packets <NUM> are received by an input packet buffer <NUM> and then forwarded as packets <NUM> to the hash generator <NUM> and to the packet processor <NUM>. The hash generator <NUM> performs one or more hash functions on a plurality of fields within each of the input packets <NUM>. The plurality of fields is selected to provide a unique flow identifier. For example, the selected fields within the input packets <NUM> that are used by the hash generator <NUM> to generate hash values <NUM> can be the five-tuple described above that includes the source address (SIP), the destination address (DIP), the protocol type (TYPE), the source port (S-PORT), and the destination port (D-PORT). Although this five-tuple is commonly used to identify the packet flow for a received packet, other selected fields (e.g., tuples) could be used to identify packet flows for the input packets <NUM> if desired.

It is also noted that packet flows typically identify a packet stream in one direction. However, many communication events and data transfers are bi-directional including one upstream flow and one downstream flow. These related upstream/downstream flows will typically use the same IP addresses and port numbers, except in the reverse order. Considering the <NUM>-tuple above, the two upstream/downstream packet flows would be: {ip1, ip2, type, port1, port2} and {ip2, ip1, type, port2, port1}, respectively. Without modification to these <NUM>-tuples, the hash algorithm would generate different hash values for each of these two related packet flows. However, it can be desirable to monitor these related packet flows in pairs. As such, for circumstances where pair-wise processing of upstream/downstream packet flows is desired, the hash-based sampling described herein can be modified to generate the same hash for each of the flows in a related upstream/downstream pair. One technique that can be used for this pair-wise processing is to perform an XOR (exclusive OR) operation on the SIP and DIP addresses and perform an XOR operation on the S-PORT and D-PORT numbers before generating the hash values. Further to the example above, "ip1" XOR "ip2" will yield the same value as "ip2" XOR "ip1," and "port1" XOR "port2" will yield the same value as "port2" XOR "port1. " When the hash algorithm is them applied using the resulting XOR'ed values, the same hash value will be generated for both flows. Another technique that can be used to achieve this result is to sort the fields for the <NUM>-tuple (e.g., SIP/DIP addresses, protocol type, S-PORT/D-PORT port numbers) in some numerical order before applying the hash (e.g., increasing value, decreasing value, etc.). This numerical sorting prior to applying the hash algorithm will also result in the same hash value for both flows. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

The packet processor <NUM> receives the hash values <NUM> from the hash generator <NUM> and uses these hash values <NUM> in combination with mask <NUM> to select which packets are output for further processing, such as to the flow statistics engine <NUM>. For one example embodiment, the hash values <NUM> are compared to the mask <NUM>, and packets matching the mask <NUM> are selected to be forwarded to the flow statistics engine <NUM>. For another example embodiment, the hash values <NUM> are compared to the mask <NUM>, and packets not matching the mask <NUM> are selected to be forwarded to the flow statistics engine <NUM>. Non-selected packets are discarded. As such, the mask <NUM> selects packets <NUM> from a subset of packet flows for further processing, such as by the statistics engine <NUM>. The mask <NUM> can be programmable and can be determined by one or more selection control signals <NUM>. As described further below, the mask <NUM> can also be adjusted overtime to change the relative percentage of packet flows that are selected for processing by the statistics engine <NUM>.

For the example embodiment <NUM>, the statistics engine <NUM> processes the output packets <NUM> and collects flow statistics that are stored in the flow table <NUM> for the selected packet flows. Once the flow statistics engine <NUM> detects that a packet flow has ended, a report packet is sent as one of the report packets <NUM>, and these report packets <NUM> include information only for the selected packet flows. As described above, a collection server can receive these report packets <NUM> and aggregate the packet flow statistics for further processing and/or access and review by network managers. It is also noted that the packet flow statistics processing and collection can be implemented according to the IPFIX protocol standard and/or other desired packet flow statistics protocols. Although further processing of the selected packets <NUM> is shown to be performed by the flow statistics engine <NUM>, the selected packets <NUM> can be forwarded to one or more different network components for further processing, such as for example, a network packet broker and/or other desired network component. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a diagram of an example embodiment for the flow table <NUM> that is used by the flow statistics engine <NUM>, such as an IPFIX flow statistics engine, to collect and store flow data associated with packets <NUM> from the subset of selected packet flows <NUM> as represented by FLOW3, FLOW7, FLOW9, and so on. For each of the selected packet flows <NUM>, a five-tuple flow identifier <NUM> is stored that includes a source address (SIP), a destination address (DIP), a protocol type (TYPE), a source port (S-PORT), and a destination port (D-PORT). For each of the packet flows <NUM>, flow data is also collected and stored. This collected data <NUM> includes a start time (START), an end time (END), number of bytes (#BYTES), and a number of packets (#PACKETS). It is noted that the source and destination addresses (SIP/DIP) can be, for example, source and destination IP (Internet Protocol) addresses. The protocol type represents the communication protocol used for the packet flow such as TCP (Transmission Control Protocol), UDP (User Datagram Protocol), SCTP (Stream Control Transmission Protocol), and/or other communication protocols. The source and destination ports (S-PORT/D-PORT) can be, for example, communication ports used by the source and destination for the packet flow. When the flow statistics engine <NUM> determines that a packet flow has ended for selected packet flow, the flow record is sent in a report packet to the collection server as represented by arrow <NUM>. In comparison to <FIG> (Prior Art) it is seen that fewer flow records are stored within the flow table <NUM> as compared to the flow table <NUM> thereby reducing processing and memory resource requirements.

For the hash-based sampling of packet flows, it is assumed that packets within each packet flow can be uniquely identified using a selected number (N) of keys extracted from fields within every packet to form an N-tuple value. For one example as described above, the keys can be data extracted from the following fields in every packet: source IP address (SIP), the destination address (DIP), the protocol type (TYPE), the source port (S-PORT), and the destination port (D-PORT). These fields are used to form a five-tuple value that uniquely identifies the packet flow for a given packet. The hash generator <NUM> then applies one or more hash algorithms to the selected keys to hash the N-tuple value generated from these selected keys into a smaller hash value. Each packet flow will have a different resulting hash value since the N-tuple is designed to uniquely identify the packet flow. For example, for the five-tuple described above, the source/destination IP (Internet Protocol) addresses and the source/destination port numbers are expected to be different for each packet flow. Further, all packets in a given packet flow are expected to have the same hash value because they will have the same N-tuple value that is being hashed. Sampling to select packet flows to further process can then be done by selecting only packets having hash values that match (or do not match) certain hash values determined by the mask <NUM>.

For example, consider for one embodiment selecting only packets with a hash value where the three least significant bits are "<NUM>. " Such a mask and packet selection allows only packets within one out of every eight packet flows to be output as packets <NUM> for further processing. Further, by selecting more or fewer required bits for the mask <NUM> and by adjusting the bit length of the hash value <NUM> and mask <NUM>, different desired sampling ratios can be achieved for the number of packet flows selected among the total number of packets flows to have their packets passed along and output as packets <NUM>. The hash-based sampler <NUM>, therefore, is applied on a per-packet basis to select network packets from a subset of packet flows without requiring flow data to be stored in a state table or in a flow table, and all packets in a particular packet flow will either be selected and passed on for further processing or be ignored and dropped from further processing.

For one example embodiment, consider a network monitoring system according to the disclosed embodiments that is collecting and monitoring input packets from a large number of different packet flows (e.g., <NUM> or more). A hashing function is implemented by the hash generator <NUM>, for example in FPGA (field programmable gate array) logic, that looks at an N-tuple value generated from fields within each packet from the different packet flows and that outputs a <NUM>-bit hash value. It is also assumed that the hash function is designed to evenly spread the input hash values across the different possible hash output values. Thus for this <NUM>-bit hash example, each N-tuple that identifies each different packet flows will be resolved into one of sixteen different hash values that are possible using the <NUM>-bit hash, and the packet flows will preferably be spread evenly across the sixteen different hash values. For example, if <NUM> packet flows are being monitored, the hash function would split the packet flows into <NUM> different groups of <NUM> different packet flows. The same <NUM>-bit hash value will be generated for each packet flow within a given group of <NUM> packet flows. The mask is then set to a selected value from <NUM> to <NUM> (e.g., <NUM> to <NUM>) and "don't care" values can also be included. In other words, each bit within the multiple-bit mask can be set to a logic "<NUM>" or a logic "<NUM>" or a "don't care" designation. For the "don't care" designation, a corresponding bit in a hash value will always match the mask whether it is a logic "<NUM>" or a logic "<NUM>. " This use of "don't care" bits within the mask for the hash value matching allows for different subsets of packet flows within the total number of packet flows to be selected to have their related packets passed for further processing. The following TABLE gives an example of these percentages and different selections assuming a <NUM>-bit hash value and various numbers of "don't care" bits and related selection bits. The "don't care" bits are represented by an "x" within this TABLE.

Along with the use of "don't care" bits, it is again noted that the bit length of the hash value <NUM> and corresponding mask <NUM> can be adjusted to increase or decrease the level of granularity provided in the packet flow selection. Larger bit lengths provide for increased granularity, and shorter bit lengths provide for decreased granularity. Still further, to provide additional granularity for the packet flow selection, the mask <NUM> can include a Boolean combination of a plurality of sets of multiple bits. For example, packets can be selected where the hash values match one or more Boolean combinations of bit values, which can also include logic "<NUM>" bits, logic "<NUM>" bits, and "don't care" bits. Boolean operations such as OR, NOR, and/or other desired Boolean operations can also be used for these Boolean combinations. As one example for such a Boolean combination using <NUM>-bit values, packets can be selected that match a mask value of <NUM> OR <NUM> OR <NUM>, which can also be expressed as 000x OR <NUM>. This example Boolean combination would provide a selection of <NUM> out of every <NUM> flows (e.g., <NUM>% of the flows). Using such Boolean expressions where <NUM>-bit hash values are used, flow selections from <NUM>/<NUM> (e.g., <NUM>%) to <NUM>/<NUM> (e.g., <NUM>%) can be obtained. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems.

It is noted that the hash generator <NUM> can be implemented as a single hash generator or can be implemented as multiple hash generators. The hash generator <NUM> can also be configured to generate hash values based upon one or more hash algorithms that are applied to all or a portion of the contents of each packet. The hash generators <NUM> are preferably configured to apply hash algorithm(s) having uniform distribution characteristics such that resulting hash values are generated with even distributions across a range of possible hash values. Further, it is desirable that the hash algorithms generate different hash values for data strings that are different but similar so that similar but different data strings can be distinguished. Other considerations can also be used to select the hash algorithms. It is further noted that SHA-<NUM>, MD5, FNV (Fowler-Noll-Vo), and MurmurHash are known algorithms for generating hash values based upon selected input parameters. It is further noted that large cryptographic hash algorithms, such as MD5, may be difficult to utilize for the embodiments described herein because they tend to be complex and slow algorithms. It is also noted that PRBS (pseudo-random binary sequence), CRC (cyclic redundancy check), and other cyclical polynomial computations (e.g., Reed Solomon) could also be utilized to generate hash values. While these cyclical polynomial computations can be easier to implement in hardware, they typically provide worse performance with respect to desirable hash parameters. Non-cryptographic hash algorithms can also be used to provide hash values. If desired, a non-cryptographic MurmurHash-type hash algorithm can be used and can be split into multiple <NUM>-bit hash processes that execute in parallel followed by a final series of mixing steps. Other variations, hash algorithms, and combinations of has algorithms can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

It is also noted that the hash-based sampler <NUM> can be implemented in a variety of difference devices or components within a network communication system include physical and/or virtual processing environments. It is further noted that the hash-based sampler <NUM> as well as the flow statistics engine <NUM> and the collection server <NUM> can be implemented using one or more programmable integrated circuits programmed to perform the operations and functions described herein, and the programmable integrated circuits can include one or more processors (e.g., central processing units (CPUs), controllers, microcontrollers, microprocessors, hardware accelerators, ASICs (application specific integrated circuit), and/or other integrated processing devices) and/or one or more programmable logic devices (e.g., CPLDs (complex programmable logic devices), FPGAs (field programmable gate arrays), PLAs (programmable logic array), reconfigurable logic circuits, and/or other integrated logic devices). In addition, the flow table <NUM> and buffers <NUM>/<NUM> as well as the flow statistics database <NUM> can be implemented as one or more data structures stored in any desired non-transitory tangible computer-readable medium including, for example, one or more data storage devices, flash memories, random access memories, read only memories, programmable memory devices, reprogrammable storage devices, hard drives, floppy disks, DVDs, CD-ROMs, and/or any other non-transitory tangible computer-readable data storage mediums. Other implementations could also be used while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a block diagram of an example embodiment <NUM> for processing packets from selected packet flows based upon hash-base sampling. In block <NUM>, a packet is received. In block <NUM>, a hash value is generated based upon selected fields from the packet that are configured to identify the packet flow for the packet. In block <NUM>, the hash value is compared to a mask. In decision block <NUM>, a determination is made based upon the comparison to either ignore the packet or forward the packet for further processing. For the example embodiment shown, the determination is whether the hash value matches the mask. If "NO," then flow passes to block <NUM> where the packet is ignored, and flow then proceeds back to block <NUM> where the next packet is received. If "YES," then flow passes to block <NUM> where the packet is forwarded for further processing as a packet from a selected packet flow. For an alternative embodiment, the determination in block <NUM> can be whether the hash value does not match the mask. If "YES," then flow still passes to block <NUM>; and if "NO," the flow still passes to block <NUM>. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a block diagram of an example embodiment for the packet processor <NUM>. Each input packet <NUM> is initially stored in packet buffer <NUM>. A comparator <NUM> compares the hash value <NUM> generated for this packet to the mask <NUM>. Based upon this comparison, a drop control signal <NUM> or a pass control signal <NUM> is applied to the packet buffer <NUM>. For example, the pass control signal <NUM> can be provided to the packet buffer <NUM> if the hash value <NUM> matches the mask <NUM>, and the drop control signal <NUM> can be provided to the packet buffer <NUM> if the hash value <NUM> does not match the mask <NUM>. Alternatively, the pass control signal <NUM> can be provided to the packet buffer <NUM> if the hash value <NUM> does not match the mask <NUM>, and the drop control signal <NUM> can be provided to the packet buffer <NUM> if the hash value <NUM> does match the mask <NUM>. If the drop control signal <NUM> is received for the packet by the packet buffer <NUM>, the packet is discarded as indicated by arrow <NUM>. If the pass control signal <NUM> is received for the packet by the packet buffer <NUM>, the packet is passed as part of the packets <NUM> output for further processing. As indicated above, the mask <NUM> determines the number of packet flows that are selected for further processing, and the mask <NUM> can be programmed or adjusted over time through selection control signals <NUM>. It is noted that the selection control signals <NUM> can be generated by one or more different network components within the network communication system, and these selection control signals <NUM> can then be applied by the hash-based sampler <NUM> to set the mask <NUM> and/or otherwise adjust the operation of the comparator <NUM>. It is also noted that the comparator <NUM> can be implemented in in FPGA logic if desired. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

It is noted that that the discarded packets <NUM> can also be forwarded by the packet processor <NUM> to another network destination for further analysis. For example, the discarded packets <NUM> can be forwarded to a network tool such as one of the network tools <NUM> described below. The network tool can the perform additional analysis on the discarded packets <NUM> as desired. With respect to embodiment <NUM> of <FIG>, for example, even though flow statistics are not generated for these discarded packets <NUM> by the flow statistics engine <NUM>, these discarded packets <NUM> can still be forwarded to a network tool for further processing and analysis. Other variations could also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a block diagram of an example embodiment <NUM> of a network communication system showing various possible locations for a hash-based packet flow processor <NUM> within various components of the network communication system. For the embodiment <NUM>, a network <NUM> includes a number of different network connected devices that are communicating with each other using a number of different packet flows. At least a portion of these packet flows are routed by the network router <NUM>, which can include a number of different input/output (I/O) ports that are used to receive and send packets. For the embodiment <NUM>, packets received by the network router <NUM> are represented by input packets <NUM>, and packets sent by the network router <NUM> are represented by output packets <NUM>. A switch <NUM> within the network router <NUM> receives the input packets <NUM> from network sources and routes them to the appropriate network destinations through output packets <NUM>. These input and output packets <NUM>/<NUM> are assumed to include packets within a number of different packet flows for the network <NUM>.

Also as shown, it is assumed that different packet collection devices are used to collect packets to be monitored such as tap (test access port) device <NUM>, tap device <NUM>, and/or SPAN (switched port analyzer) <NUM>. The tap device <NUM> collects packet copies from the router input packets <NUM> and forwards them as packets <NUM> to a network packet broker (NPB) <NUM>. The tap device <NUM> collects packet copies from the router output packets <NUM> and forwards them as packets <NUM> to the NPB <NUM>. The SPAN port <NUM> collects packet copies for packets processed by the network router <NUM> and forwards them as packets <NUM> to the NPB <NUM>. The NPB <NUM> receives packets <NUM> from various collection sources and forwards them to one or more network tools <NUM> based upon one or more internally defined filters. It is noted that packet collection devices <NUM>/<NUM>/<NUM>, NPB <NUM>, and network tools <NUM> are provided only as example network components. Additional and/or different network components could also be provided within the network communication system. It is also noted that one or more of these network components could be implemented as virtual platforms within virtual processing environments hosted by one or more host servers. It is further noted that the network <NUM> can include any of a wide variety of network connected systems including server systems, data storage systems, desktop computer systems, portable computer systems, network routers, broadband routers, and/or any other desired network connected systems or devices that communicate network packets. It is further noted that network tools <NUM> can be any of a wide variety of network related security tools including traffic monitors, packet sniffers, data recorders, voice-over-IP monitors, intrusion detection systems, network security systems, application monitors and/or any other desired network security tool.

As shown for embodiment <NUM>, a hash-based packet flow processor <NUM> including a hash-based sampler <NUM> can be implemented within one or more network components within the network communication system. For example, a hash-based packet flow processor 200A can be implemented within the tap device <NUM>, can receive selection control signals 212A, and can output report packets 218A. A hash-based packet flow processor 200B can be implemented within the tap device <NUM>, can receive selection control signals 212A, and can output report packets 218A. A hash-based packet flow processor 200C can be implemented within the network router <NUM>, can receive selection control signals 212C, and can output report packets 218C. A hash-based packet flow processor 200D can be included within the NPB <NUM>, can receive selection control signals 212D, and can output report packets 218D. A collection server <NUM> can also operate within the network communication system, can control operations of the hash-based packet flow processors 200A-D through control signals 212A-D, and can collect and aggregate information from the report packets 218A-D. It is further noted that the collection server <NUM> can be implemented within one or more different network connected device. For example, the collection server <NUM> can be implemented in full or in part within the NPB <NUM>, for example, the NPB <NUM> can be used to generate one or more of the control signals 218A-D. Other variations could also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a swim lane diagram of an example embodiment <NUM> for operation of a hash-based sampler <NUM> to sample packets within selected packet flows for further processing. For the embodiment shown, a collection server <NUM> sends the control signals <NUM> to the hash-based sampler <NUM>, for example, to set the mask <NUM> as described above. The hash-based sampler <NUM> then receives input packets <NUM> associated with packet flows <NUM>. As indicated by block <NUM>, the hash-based sampler <NUM> generates hash values <NUM> for the received packets <NUM>. As indicated by block <NUM>, the hash-based sampler <NUM> selects packets based upon the hash values <NUM>, for example, by comparing the hash values <NUM> to the mask <NUM> as described above. The hash-based sampler <NUM> then outputs the selected packets <NUM> for further processing, such as to the flow statistics engine <NUM>. These selected packets represent packets within a subset of packet flows based upon the hash-based sampling. As indicated by block <NUM>, the flow statistics engine <NUM> then generates flow data for the selected packets, for example, according to a flow statistics protocol such as IPFIX. The flow data is then collected and stored in a flow record for the packet flow within flow table <NUM> as indicated by arrow <NUM>. As indicated by block <NUM>, the end of a flow is identified by the flow statistics engine <NUM>, and the flow record is then retrieved by the flow statistics engine <NUM> from the flow table <NUM> as indicated by arrow <NUM>. The flow statistics engine <NUM> then reports the flow record to the collection server <NUM> as indicated by arrow <NUM> where the flow statistics data can be aggregated as described above. As such, the flow table <NUM> as well as the flow statistics data collected and aggregated by the collection server <NUM> include only a subset of the original packet flows <NUM> as selected by the hash-based sampler <NUM>.

<FIG> is a block diagram of an example embodiment for a computing platform <NUM> that can be used to implement one or more of the components described herein including the hash-based sampler <NUM>, the flow statistics engine <NUM>, NPB <NUM>, network tools <NUM>, the collection server <NUM>, and/or other components of the network communication system. The computing platform <NUM> includes one or more processors <NUM> or other programmable integrated circuit(s) that are programmed with code or logic instructions to perform the operations and functions described herein. In addition to processors <NUM> or other programmable integrated circuits, the computing platform <NUM> can also include one or more input/output (I/O) ports <NUM>, one or more network interface cards (NICs) <NUM>, one or more data storage systems <NUM>, and memory <NUM> coupled to communicate with each other through a system bus interconnect <NUM>. The memory <NUM> can include one or more memory devices that store instructions <NUM> and/or data <NUM> during operation of the computing platform <NUM>. For example during operation, one or more of the processors <NUM> or other programmable integrated circuits can load software or program instructions stored in the data storage systems <NUM> into the memory <NUM> and then execute the software or program instructions to perform the operations and functions described herein. It is noted that the memory <NUM> and the data storage system(s) <NUM> can be implemented using any desired non-transitory tangible computer-readable medium, such as for example, one or more data storage devices, flash memories, random access memories, read only memories, programmable memory devices, reprogrammable storage devices, hard drives, floppy disks, DVDs, CD-ROMs, and/or any other non-transitory tangible computer-readable data storage mediums. It is further noted that the programmable integrated circuits can include one or more processors (e.g., central processing units (CPUs), controllers, microcontrollers, microprocessors, hardware accelerators, ASICs (application specific integrated circuit), and/or other integrated processing devices) and/or one or more programmable logic devices (e.g., CPLDs (complex programmable logic devices), FPGAs (field programmable gate arrays), PLAs (programmable logic array), reconfigurable logic circuits, and/or other integrated logic devices). Other variations and processing platforms can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

<FIG> is a block diagram of an example embodiment <NUM> for a host server that can provide a virtual processing environment for virtual instances of one or more components described herein including the hash-based sampler <NUM>, the flow statistics engine <NUM>, NPB <NUM>, network tools <NUM>, the collection server <NUM>, and/or other components within the network communication system. For the example embodiment depicted, the host server <NUM> includes one or more processors <NUM> or other programmable integrated circuits that are programmed to provide a virtualization layer <NUM> for one or more virtual platforms <NUM>, <NUM>,. <NUM> that can implement one or more of the components described herein. The processors <NUM> or other programmable integrated circuit(s) can be programmed with code or logic instructions stored in the data storage systems <NUM> to perform the operations and functions described herein. In addition to the processors <NUM> or other programmable integrated circuits, the host server <NUM> also includes one or more network interface cards (NICs) <NUM>, one or more input/output (I/O) ports <NUM>, one or more data storage systems <NUM>, and memory <NUM> coupled to communicate with each other through a system bus interconnect <NUM>. In operation, virtualization layer <NUM> and the virtual platforms <NUM>, <NUM>,. <NUM> run on top of a host operating system (OS) <NUM>. For example, the host operating system <NUM>, the virtualization layer <NUM>, and the virtual platforms <NUM>, <NUM>,. <NUM> can be initialized, controlled, and operated by the processors or programmable integrated circuits <NUM> which load and execute software code and/or programming instructions stored in the data storage systems <NUM> to perform the functions described herein.

It is noted that the memory <NUM> can include one or more memory devices that store program instructions and/or data used for operation of the host server <NUM>. For example during operation, one or more of the processors <NUM> or other programmable integrated circuits can load software or program instructions stored in the data storage systems <NUM> into the memory <NUM> and then execute the software or program instructions to perform the operations and functions described herein. It is further noted that the data storage system(s) <NUM> and the memory <NUM> can be implemented using one or more non-transitory tangible computer-readable mediums, such as for example, data storage devices, FLASH memory devices, random access memory (RAM) devices, read only memory (ROM) devices, other programmable memory devices, reprogrammable storage devices, hard drives, floppy disks, DVDs, CD-ROMs, and/or other non-transitory data storage mediums. It is further noted that the programmable integrated circuits can include one or more processors (e.g., central processing units (CPUs), controllers, microcontrollers, microprocessors, hardware accelerators, ASICs (application specific integrated circuit), and/or other integrated processing devices) and/or one or more programmable logic devices (e.g., CPLDs (complex programmable logic devices), FPGAs (field programmable gate arrays), PLAs (programmable logic array), reconfigurable logic circuits, and/or other integrated logic devices). Other variations and processing or computing platforms can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

The virtualization layer <NUM> for the virtual platforms can be implemented using any desired virtualization layer, such as a hypervisor or a container engine, that provides a virtual processing environment for the virtual platforms such as virtual machines (VMs) or application instances. For one embodiment, the container engine can be implemented as a DOCKER container for a Linux operating system configured to execute DOCKER containers, which are software components that are designed to be compatible with a Linux-based DOCKER container engine. Other variations could also be implemented, as far as these variations fall within the scope of the appended claims.

It is further noted that the functional blocks, components, systems, devices, and/or circuitry described herein can be implemented using hardware, software, or a combination of hardware and software. For example, the disclosed embodiments can be implemented using one or more programmable integrated circuits that are programmed to perform the functions, tasks, methods, actions, and/or other operational features described herein for the disclosed embodiments. The one or more programmable integrated circuits can include, for example, one or more processors and/or PLDs (programmable logic devices). The one or more processors can be, for example, one or more central processing units (CPUs), controllers, microcontrollers, microprocessors, hardware accelerators, ASICs (application specific integrated circuit), and/or other integrated processing devices. The one or more PLDs can be, for example, one or more CPLDs (complex programmable logic devices), FPGAs (field programmable gate arrays), PLAs (programmable logic array), reconfigurable logic circuits, and/or other integrated logic devices. Further, the programmable integrated circuits, including the one or more processors, can be configured to execute software, firmware, code, and/or other program instructions that are embodied in one or more non-transitory tangible computer-readable mediums to perform the functions, tasks, methods, actions, and/or other operational features described herein for the disclosed embodiments. The programmable integrated circuits, including the one or more PLDs, can also be programmed using logic code, logic definitions, hardware description languages, configuration files, and/or other logic instructions that are embodied in one or more non-transitory tangible computer-readable mediums to perform the functions, tasks, methods, actions, and/or other operational features described herein for the disclosed embodiments. In addition, the one or more non-transitory tangible computer-readable mediums can include, for example, one or more data storage devices, memory devices, flash memories, random access memories, read only memories, programmable memory devices, reprogrammable storage devices, hard drives, floppy disks, DVDs, CD-ROMs, and/or any other non-transitory tangible computer-readable mediums. Other variations can also be implemented while still taking advantage of the hash-based selection of network packets for packet flow sampling in network communication systems, as far as these variations fall within the scope of the appended claims.

Claim 1:
A method to forward selected packets based upon packet flows within a network communication system, comprising:
receiving, at an input packet buffer (<NUM>), input packets associated with packet flows within a network communication system;
generating, by a hash generator (<NUM>), hash values for the input packets based upon fields within the input packets, the fields identifying packet flows for the input packets, wherein all packets in a given flow have the same hash value;
receiving, by a packet processor (<NUM>), the hash values from the hash generator (<NUM>);
selecting, by the packet processor (<NUM>), packets from the input packets, the selecting being based upon a comparison of the hash values to a mask, the mask determining a subset of the packet flows;
forwarding, by the packet processor (<NUM>), said selected packets for further processing; and
discarding, by the packet processor (<NUM>), non-selected packets.