CN110868388A - System and method for operating a networked device - Google Patents

Abstract

Described are methods and systems for compressing a tree structure that associates network packet signatures with network packet metadata, the tree structure including a plurality of leaf nodes containing network packet metadata and a plurality of non-leaf nodes of single-bit test nodes, The method includes determining whether to compress sub-portions of the tree structure. If a determination is made that a sub-portion of the tree structure is to be compressed, a compressed node data structure is generated, the compressed node data structure including a path to the sub-portion of the tree structure, the path including a path consisting of consecutive non-subsections with the sub-portion of the tree structure A bit sequence formed by concatenation of single bits associated with each leaf node, the number of bits in the sequence is equal to or greater than the compression threshold.

Description

System and method for operating networked devices

cross reference

This application claims priority from European Patent Application No. 1 831 5022.6 filed on August 27, 2018.

technical field

Embodiments described herein relate generally to systems and methods for operating networked devices, and more particularly, to systems and methods for generating and/or manipulating data structures that associate network data signatures with network packet metadata.

Background technique

Internet-connected infrastructure, such as data centers, may be subject to attacks aimed at infiltrating or compromising their operations. For example, a botnet comprising a large number of bots can be used to cause a distributed denial of service (DDoS) attack on a data center. DDoS attacks can flood a data center with too many requests. Under such an attack, data center processing and communication capabilities can become so overloaded that legitimate users and clients cannot be served temporarily. In at least one event, the attack can impose a load of one (1) terabit per second on the data center.

Therefore, mitigation measures are required to reduce the negative impact of potential attacks. Such mitigations may include filtering illegal network packets while granting legitimate network packets access to the data center's network. Given the large number of network packets routed from the Internet to the data center, even at relatively small data centers, filtering illegal network packets from legitimate network packets can require significant processing resources and can affect the ability of data to be presented to legitimate users and data Quality of service for clients at the center (eg, latency in providing a given service hosted at the data center).

While methods to reduce the negative impact of mitigation measures have been investigated, improvements are still needed.

The subject matter discussed in the Background section should not be admitted to be prior art merely because it is mentioned in the Background section. Similarly, problems mentioned in the Background section or problems associated with the subject matter of the Background section should not be considered to have been previously recognized in the prior art. The topics in the Background section are merely indicative of different approaches.

SUMMARY OF THE INVENTION

The following summary is for illustrative purposes only and is not intended to limit or restrict the detailed description. The following summary merely presents the various described aspects in a simplified form as a prelude to the more detailed description provided below.

In some instances, filtering and/or classifying network packets may require access to data structures that associate network packet signatures with network packet metadata.

In some instances, the network packet signature may be a network address associated with the sending host or the destination host. By way of example and not limitation, the network packet signature may be an Internet Protocol (IP) address associated with the network packet, such as an Internet Protocol version 4 (IPv4) address or an Internet Protocol version 6 (IPv6) address. In another example, the network packet signature may be part of the IP address (eg, the network portion or the host portion of the IP address). In other examples, network packet signatures can be generated based on IP addresses. In some implementations, the network packet signature may include one or more elements from a list including source IP address, destination IP address, IP protocol (eg, TCP or UDP), source TCP or UDP port, destination local TCP or UDP port. In some other implementations, the network packet signature may include a source IP address and/or a destination IP address associated with some metadata (eg, a profile identifier and/or a counter identifier). Variations on what a network packet signature may contain will become apparent to those skilled in the art and should not be construed as limiting.

In some instances, network packet metadata may be information associated with or to be associated with one or more network packet signatures. As an example, network packet metadata may establish data packet classification and/or filtering rules. Such data packet classification may enable a determination of whether a network packet associated with a network packet signature is legitimate. Classification and/or filtering rules may determine how data packets should be handled and/or what services should be performed. For example, filtering rules can be used to test network packets entering the data center's network from external computing devices to ensure that attempts to enter the data center's network can be blocked. Alternative filtering rules can also be used to transmit traffic based on priority. The network packets from the first host can be transmitted even though the network packets from the second host may be dropped because the network packets from the first host have higher priority. In some embodiments, network packet metadata may also be referred to as a network packet profile tag. In some implementations, network packet metadata may also be referred to as a network packet label (or label). Variations on what the network packet metadata may contain will become apparent to those skilled in the art and should not be construed as limiting.

In some instances, the data structure associating network packet signatures with network packet metadata may be implemented as a tree structure. The tree structure can include non-leaf nodes and leaf nodes. Non-leaf nodes and leaf nodes may include network packet metadata (eg, labels). A path extending from the root of the tree structure to the leaves of the tree structure (while traversing one or more non-leaf nodes) may define a prefix. Filtering and/or sorting of network packets may be performed by comparing the network packet signatures to one or more prefixes from the tree structure. Then, the network packet metadata associated with the longest prefix corresponding to the network packet signature may be determined to be associated with the network packet data signature.

Under certain approaches, the tree structure is a binary tree, where each bit of the network packet signature (eg, each bit of an IP address) is tested one by one. Under such a naive approach, up to 32 steps may be required to filter and/or classify IPv4 addresses (ie, 32-bit addresses), and up to 128 steps may be required to filter and/or classify IPv6 addresses (ie, 128-bit addresses) the address of). Each step requires memory access, enabling maximum filtering and/or sorting debits. As a result, the tree structure needs to be compressed to reduce the number of memory accesses required.

In one aspect, various implementations of the present technology provide a method of analyzing network packets for preventing attacks on a network by filtering illegal network packets while granting legitimate network packets access to the network, filtering based on network address and data packet classification The association is implemented as a tree structure, the data packet classification enables to determine whether the network packet is legitimate, the method is performed by the computing device, and the method includes:

Compressing a tree structure that associates network addresses with data packet classification, the tree structure includes a plurality of leaf nodes of the data packet classification and a plurality of non-leaf nodes of a single-bit test node, and the step of compressing includes:

determining, based on the number of consecutive non-leaf nodes with a single child node and a compression threshold, whether to compress a sub-portion of the tree structure that includes consecutive non-leaf nodes with a single child node;

If a determination is made to compress subsections of the tree structure, then:

Spanning a compressed subsection of a tree structure comprising a sequence of bits formed by a concatenation of single bits associated with each of the consecutive non-leaf nodes of the subsection of the tree structure, the bits of the sequence is equal to or greater than the compression threshold; and

The compressed sub-portions of the tree structure are stored in non-transitory computer readable memory.

In one aspect, various implementations of the present technology provide a method of compressing a tree structure associating a network packet signature with network packet metadata, the tree structure including a plurality of leaf nodes and a single bit containing network packet metadata Test multiple non-leaf nodes of a node, the method includes:

For subsections of the tree structure, establish the number of consecutive non-leaf nodes with a single child node;

based on the number of consecutive non-leaf nodes with a single child node and a compression threshold, determine whether to compress subsections of the tree structure;

If a determination is made to compress subsections of the tree structure, then:

generating a compressed node data structure that includes a path of subsections of the tree structure including a concatenation of single bits associated with each of the consecutive non-leaf nodes of the subsection of the tree structure a sequence of bits formed, the number of bits in the sequence being equal to or greater than the compression threshold; and

The compressed node data structures are stored in non-transitory computer readable memory.

In some embodiments, the number of bits of the sequence of the compressed node data structure is determined by the presence of (1) one of the consecutive non-leaf nodes having a cotyledon node, (2) one of the consecutive non-leaf nodes having more than one child node is determined by the presence of or (3) the predefined maximum size of the sequence.

In some embodiments, if a determination is made not to compress a subsection of the tree structure, then:

Generating an uncompressed node data structure that includes a path to a subsection of the tree structure, the path including a path consisting of one or more single-bit nodes associated with at least one non-leaf node of the subsection of the tree structure a bit sequence formed by concatenation, the at least one non-leaf node has more than one child node, and the number of bits of the sequence is less than the compression threshold; and

The uncompressed node data structures are stored in non-transitory computer readable memory.

In some embodiments, the compression threshold is 5 bits. In some embodiments, the predefined maximum size of the sequence is 30 bits.

In some implementations, the non-transitory computer-readable memory includes a first non-transitory computer-readable memory and a second non-transitory computer-readable memory. In some embodiments, (1) the compressed node data structure is a first compressed node data structure, and (2) the uncompressed node data structure is a first uncompressed node data structure, wherein the first node The data structure includes one of a first compressed node data structure and a first uncompressed node data structure, and the second node data structure includes one of a second compressed node data structure and a second uncompressed data structure.

In some embodiments, the first node data structure is stored in the first non-transitory computer readable memory and points to a memory address of the second non-transitory computer readable memory where the second node data structure is stored.

In some embodiments, the first node data structure can be accessed from the first non-transitory computer readable memory through a first single memory access, and the first node data structure can be accessed from the second non-transitory computer readable memory through a second single memory access Access the second node data structure.

In some embodiments, the first non-transitory computer readable memory is a first bank of a first QDR SRAM memory and the second non-transitory computer readable memory is a second bank of a second QDR SRAM memory.

In some implementations, the compressed node data structure is a first compressed node data structure, and the uncompressed node data structure is a first uncompressed node data structure, and wherein the non-transitory computer-readable memory includes The first part, the second part and the third part, the first part stores one of the first compressed node data structure and the first uncompressed node data structure, the first compressed node data structure and the first uncompressed node data one of the structures points to one of the second compressed node data structure and the second uncompressed node data structure stored in the second portion, and wherein:

When updating the tree structure, one of the third compressed node data structure and the third uncompressed node data structure is stored in the third portion, and the first compressed node data structure and the first uncompressed node are modified One of the data structures such that one of the first compressed node data structure and the first uncompressed node data structure points to one of the third compressed node data structure and the third uncompressed node data structure.

In some embodiments, the method further comprises at least one operation of: (1) transmitting the network packet based on a priority established by the network packet metadata, (2) identifying a service to be performed on the network packet based on the network packet metadata, ( 3) Test the network packet based on the network packet metadata to establish that the network packet is part of a network attack and/or (4) create a measure of the traffic of the network packet based on the network packet metadata.

In another aspect, various implementations of the present technology provide a computer-implemented system configured to perform the method described in the preceding paragraphs.

In another aspect, various implementations of the present technology provide a non-transitory computer-readable medium comprising computer-executable instructions that cause a system to perform the method described in the preceding paragraphs.

In the context of this specification, unless expressly stated otherwise, networked devices may refer to, but are not limited to, "routers," "switches," "gateways," "systems," "computer-based systems," and/or their appropriate Any combination of related tasks.

In the context of this specification, unless expressly stated otherwise, the expressions "computer-readable medium" and "memory" are intended to include media of any nature and kind, non-limiting examples of which include RAM, ROM, disk (CD-ROM) , DVDs, floppy disks, hard drives, etc.), USB keys, flash memory cards, solid state drives, and tape drives. Still in the context of this specification, "a" computer-readable medium and "the" computer-readable medium should not be construed as being the same computer-readable medium. In contrast, "a" computer-readable medium and "the" computer-readable medium can also be construed as a first computer-readable medium and a second computer-readable medium, whenever appropriate.

In the context of this specification, unless expressly stated otherwise, the words "first", "second", "third", etc. are used as adjectives only for the purpose of enabling the nouns they modify to be distinguished from each other, and Not for the purpose of describing any particular relationship between these nouns.

Implementations of the present technology each have at least one, but not necessarily all, of the objects and/or aspects described above. It should be appreciated that some aspects of the technology resulting from an attempt to achieve the above-mentioned objective may not satisfy this objective and/or may satisfy other objectives not specifically recited herein.

Additional and/or alternative features, aspects and advantages of implementations of the present technology will become apparent from the following description, drawings, and appended claims.

Description of drawings

These and other features, aspects and advantages of the present disclosure will be better understood with reference to the following description, claims and drawings. The present disclosure is shown by way of example and not by way of limitation in the accompanying drawings, in which like reference numerals refer to like elements.

1A and 1B illustrate example networked devices that can be used to implement any of the methods described herein;

Figure 2 shows a diagram of a networked device and its networked environment in accordance with an embodiment of the present technology;

3 shows a diagram of an alternative networked device and its networked environment in accordance with an embodiment of the present technology;

4 to 7 illustrate diagrams of tree structures according to embodiments of the present technology;

8 shows a diagram of a node data structure according to an embodiment of the present technology;

FIG. 9 shows a diagram of a data structure stored in multiple banks of a memory in accordance with an embodiment of the present technology; and

FIG. 10 shows a first flowchart of a method of compressing a tree structure according to an embodiment of the present technology.

Detailed ways

In the following description of various illustrative embodiments, reference is made to the accompanying drawings, which form a part hereof, and in which are shown by way of illustration various embodiments in which aspects of the present disclosure may be practiced. It is to be understood that other embodiments may be utilized and structural or functional changes may be made without departing from the scope of the present disclosure.

A network of devices, such as a network housed in a data center, may include a variety of different networking hardware, such as routers, switches, multilayer switches, cables, and/or other networking hardware. Networked devices can serve various computing devices, such as servers. Networked devices may operate upon data structures that filter and/or classify network packets.

FIG. 1A shows a diagram of a computing environment 100 in accordance with an embodiment of the present technology. In some embodiments, computing environment 100 may consist of any of conventional personal computers, servers, routers, switches, controllers, and/or electronic devices (eg, servers, controller units, control devices, monitoring devices, etc.) and and/or any combination that is appropriate for the task at hand. In some embodiments, computing environment 100 includes various hardware components including one or more single-core or multi-core processors, collectively represented by processor 110 , solid state drive 120 , random access memory (RAM) Memory 130 , dedicated memory 170 and input/output interface 150 . Computing environment 100 may be a computer specifically designed to operate in a data center environment. Computing environment 100 may be a general-purpose computer system.

In some implementations, computing environment 100 may also be a subsystem of one of the systems listed above. In some other implementations, computing environment 100 may be an "off-the-shelf" general-purpose computer system. In some embodiments, computing environment 100 may also be distributed among multiple systems. Computing environment 100 may also be specialized for implementing the present technology. As can be appreciated by those skilled in the art, numerous variations on how computing environment 100 may be implemented may be envisaged without departing from the scope of the present technology.

Communication between the various components of computing environment 100 may be through one or more internal and/or external buses 160 (eg, PCI bus, Universal Serial Bus, IEEE 1394 "Firewire") electrically coupled to the various hardware components. ” bus, SCSI bus, Serial ATA bus, ARINC bus, etc.) implementation.

Input/output interface 150 may provide networking capabilities such as wired or wireless access. As an example, input/output interface 150 may include a networking interface such as, but not limited to, one or more network ports, one or more network sockets, one or more network interface controllers, and the like. Numerous examples of how networking interfaces may be implemented will become apparent to those skilled in the art. For example and without limitation, networking interfaces may implement specific physical layer and data link layer standards, such as Ethernet, Fibre Channel, Wi-Fi, or Token Ring. Certain physical and data link layers can provide the basis for a complete network protocol stack, enabling communication between groups of computers on the same local area network (LAN) and large-scale network communications over routable protocols such as Internet Protocol (IP) .

According to implementations of the present technology, solid state drive 120 stores program instructions suitable for being loaded into random access memory 130 and executed by processor 110 . For example, program instructions may be part of a library or application. Although shown as solid state drive 120, any type of memory may be used in place of solid state drive 120, such as hard disks, optical disks, and/or removable storage media.

In some embodiments of the present technology, the processor 110 may be a general purpose processor such as a central processing unit (CPU), or a special purpose processor such as a digital signal processor (DSP). In some implementations, the processor 110 may also rely on an accelerator 112 dedicated to certain given tasks, such as performing the method 1000 set forth in the following paragraphs. In some embodiments, processor 110 or accelerator 112 may be implemented as one or more field programmable gate arrays (FPGAs). Furthermore, explicit use of the term "processor" should not be construed as an exclusive reference to hardware capable of executing software, and may implicitly include, but is not limited to, application specific integrated circuits (ASICs), read-only memories for storing software ( ROM), random access memory (RAM), and nonvolatile storage devices. Other conventional and/or custom hardware may also be included.

In some embodiments of the present technology, RAM 130 may include high performance memory such as, but not limited to, quad data rate (QDR) SRAM memory. In some implementations, RAM 130 may include multiple QDR SRAM memories. Additionally, in some embodiments, dedicated memory 170 may also be relied upon. Such dedicated memory 170 may be a different memory unit or integrated into another component. In some implementations, the dedicated memory 170 is part of the FPGA processing unit (eg, registers of the FPGA). In some implementations, dedicated memory 170 is implemented as a dedicated portion of RAM 130 . Other variations can also be envisaged without departing from the scope of the present technology.

FIG. 1B shows a diagram of an alternative computing environment 190 in accordance with an embodiment of the present technology. In some implementations, computing environment 190 and computing environment 100 may be implemented by similar components (similar components are designated by the same reference numerals). Computing environment 190 includes a dedicated FPGA card 180 that may be connected to other components of the computing environment through input/output interface 150 or directly through internal and/or external bus 160 . In some embodiments, the FPGA card 180 includes an FPGA chipset 182 (which may include registers, also referred to as "dedicated memory") and dedicated RAM memory, such as four different QDR SRAM memories collectively referred to as QDR SRAM memory 184. In some embodiments, the FPGA card may also include one or more input/output interfaces that enable connections to the network.

Software modules, or modules merely implied to be software, may be represented herein as any combination of flowchart elements or other elements that indicate the execution of process steps and/or textual descriptions. Such modules may be executed by hardware shown explicitly or implicitly. Furthermore, it should be understood that a module may include, for example, but not limited to, computer program logic, computer program instructions, software, stacks, firmware, hardware circuits, or combinations thereof, to provide the desired capabilities.

2 shows a diagram of a networked device and its networked environment in accordance with an embodiment of the present technology. Networks 10 and 20 may be connected to the Internet. Networks 10 and/or 20 may define a network associated with, controlled and operated by a data center. Each network 10 and 20 may include hosts 12, 14 and 16 and 22 and 24, respectively. Each network 10 and 20 may also include switches 18 and 26, respectively, and may include one or more servers, such as servers 17, 19, and 28, respectively. Each network 10 and 20 may also include one or more gateways 13 and 25, respectively, to the Internet 30. Not explicitly shown are routers and other parts of networks 10 and 20 that may also control traffic through networks 10 and 20 and will be considered to be inherently depicted by switches 18 and 26 and networks 10 and 20 as a whole, respectively . Switches 18 and 26 , gateways 13 and 25 , and routers may generally be referred to as a network of devices that may be implemented as computing devices similar to computing environment 100 . Switches 18 and 26, gateways 13 and 25, and routers may implement a tree structure that associates network packet signatures with network packet metadata in accordance with embodiments of the present technology.

3 shows a diagram of an alternative networking device and its networking environment in accordance with an embodiment of the present technology. The depicted environment is the infrastructure that operates the data center 300 connected to the Internet 30 . Data center 300 includes a first set of routers 301 and a second set of routers 302 . The first set of routers 301 may be referred to as backbone routers that manage a number of different networks operated by the data center 300 . The second set of routers 302 may be referred to as data center routers that each manage the network connections of the plurality of servers 303 operated by the data center 300 . The data center 300 also includes an anti-DDoS system 304 also known as a vacuum system VAC. In some embodiments, the anti-DDoS system 304 may be connected to the first set of routers 301 and/or the second set of routers 304 to filter network packets received from the Internet 30 . In some embodiments, anti-DDoS system 304 implements mitigations that include filtering illegal network packets while granting legitimate network packets access to the data center's network (eg, access server 303 ). In some embodiments, anti-DDoS system 304 may include multiple subsystems, such as subsystems 305-308, that may be dedicated to certain given tasks.

By way of example and not limitation, the first sub-system 305, also referred to as a pre-firewall, may operate control logic intended to segment network packets, control the size of network packets, and/or to Certain network packets (eg, TCP, UDP, ICMP, GRE protocols) authorize while other network packets (eg, protocols other than TCP, UDP, ICMP, GRE protocols) are blocked. As another example and not limitation, the second subsystem 306, also referred to as a firewall network, may operate control logic designed to authorize/block IP addresses, authorize/block protocols (eg, IP, TCP, UDP , ICMP, GRE protocols), authorize/block one or more network ports (eg, TCP or UDP ports), authorize/block SYN/TCP, authorize/block network packets other than SYN/TCP. As another example and not limitation, a third subsystem 307, also referred to as a shield, may operate control logic aimed at analyzing network packets (eg, to check headers, checksums, etc.). As another example and not limitation, the fourth subsystem 308, also referred to as Armor, may operate control logic aimed at analyzing network packets and/or performing detection of invalid TCP flags, invalid sequence numbers, Detection of botnet grouping, TCP SYN authentication, DNS authentication, DNS restriction, etc.

In some embodiments, the fourth subsystem 308 generates and/or implements a tree structure that associates network packet signatures with network packet metadata in accordance with embodiments of the present technology. As can be appreciated, tree structures may be generated and/or implemented equally on different networked devices, or even operated on multiple networked devices in a distributed fashion (eg, by one or more of subsystems 305-308). multiple implementations). In some embodiments, a networking device that generates and/or implements a tree structure associating network packet signatures with network packet metadata in accordance with embodiments of the present technology may include one or more virtual routers (vRouters) including FPGA cards. ). Examples of configurations suitable for networked devices may be, but are not limited to, the following:

processor 2x1697v4 RAM 64GB DD4 ECC network card 2x ConnectX-4 2x 100Gbps FPGA XUPP3R, 4x 100Gbps

Other configurations may also be used and will be readily apparent to those skilled in the art.

Turning now to FIGS. 4-7 , diagrams of a tree structure 400 are shown in accordance with embodiments of the present technology. The tree structure includes subsections 402 , 502 , 504 , 602 , 604 and 700 . The number of levels and/or subsections of the tree structure is exemplary and should not be construed as a limitation of the present technology. The tree structure includes non-leaf nodes (eg, P2/L2, P5, P6/L5) and leaf nodes (eg, P1/L1, P3/L3, P4/L4). In some embodiments, such as those depicted in Figures 4-9, non-leaf nodes may be associated with network packet metadata (eg, labels). As an example, non-leaf node P6/L5 is associated with label "5".

Each non-leaf node is a single-bit test node that enables direct browsing of the entire tree structure. A non-leaf node can be associated with one child node or two child nodes. In the instance where a non-leaf node is associated with two child nodes, the bit value may determine which of the two child nodes should be considered at the next level in the tree structure. As an example, if the tested bit value is 1, non-leaf node P10 may point to P12/L8, and if the tested bit value is 0, non-leaf node P10 may point to P11/L9. In some implementations, the bit value is tested even if the non-leaf node has only one child node. In some implementations, the presence of a bit value determines whether a lookup traversing the entire tree structure should continue.

Each leaf node is associated with network packet metadata (eg, a label), eg, leaf nodes P3/L3, P1/L1, P11/19. When browsing the entire tree structure from a root (eg, root P0/L0), reaching a leaf node causes the browsing to end and determines that a network packet signature can be associated with the leaf node's metadata. In some embodiments where leaf nodes are associated with labels, the selected label is one of the last matching nodes, thereby avoiding having to generate a leaf for every possible termination.

As an example, a path traversing tree structure 400 from root P0/L0 to leaf node P3/L3 includes non-leaf node 410 having a single child non-leaf node 412, which in turn serves as two child non-leaf nodes 414 and 416 . Non-leaf node 414 has two child nodes, non-leaf node 418 and leaf node P3/L3. A path traversing the tree structure 400 from root P0/L0 to leaf node P3/L3 may be defined by the following bit sequence "0011". As another example, a path traversing tree structure 400 from root P0/L0 to leaf node P2/L2 may be defined by the following bit sequence "00100".

As shown in Figures 4-7, non-leaf node P5 leads to subsection 502, which itself leads to non-leaf node P12/L8 and leaf node P11/L9. Non-leaf node P2/L2 leads to subsection 504, which itself leads to non-leaf node P6/L5. Non-leaf node P12/L8 leads to subsection 602, which itself leads to non-leaf node P13/L8. Non-leaf node P13/L8 leads to subsection 604, which itself leads to leaf node P14/L10. Non-leaf node P6/L5 leads to subsection 700, which itself leads to leaf node P7/L6 and leaf node P9/L7.

In various aspects, the present technology provides a method of compressing a tree structure, such as tree structure 400 . A method of compressing a tree structure establishes, for a given subsection of the tree structure, the number of consecutive non-leaf nodes with a single child node. In some implementations, a non-leaf node with a single child node may be referred to as a non-leaf node with no fork, in other words, it has only one branch. As an example, as shown in subsections 402, 502, 504, 602, 604, and 700, the subsections may be defined by levels of a tree structure. A subsection can be a single branch or a combination of branches that define a subtree structure. In an embodiment, the number of stages may be defined by the number of bits. In some embodiments, the number of levels may be defined as the number of non-leaf nodes and/or leaf nodes. As an example, a subsection may be defined as 30 levels (ie, 30 bits) of the tree structure. Variations are envisaged without departing from the scope of the present technology, as an example, the number of stages may be more or less than 30 and may depend on certain constraints (eg, memory structure).

In some embodiments, the method of compressing the tree structure determines whether to compress sub-portions of the tree structure. In some embodiments, the determination is based on the number of consecutive non-leaf nodes that have a single child node. In some embodiments, the compression threshold may be 6 bits, such that subsections comprising more than 5 consecutive non-leaf nodes with a single subnode are determined to be compressed. Variations are envisaged without departing from the scope of the present technology, as an example, the compression threshold may be greater or less than 5 and may depend on certain constraints (eg, memory structure). As an example, subsection 402 includes a plurality of non-leaf nodes and a plurality of leaf nodes, however, subsection 402 does not include at least 5 consecutive non-leaf nodes having only one child node (eg, non-leaf nodes 412 and 414 each have two child nodes). As a result, the subsection is determined not to be compressed. As another example, where subsection 504 includes 10 consecutive non-leaf nodes with only one child node (ie, 0011111100), a determination may be made that subsection 504 can be compressed.

Following similar logic, a determination can be made that subsection 502 will not be compressed, subsection 602 will be compressed (although not shown, subsection 602 includes 32 consecutive non-leaf nodes with only one child), will not be compressed Subsection 604 (only 3 non-leaf nodes with only one child) and subsection 700 (one non-leaf node with two children) are compressed. In some implementations, a maximum size of a sequence of consecutive non-leaf nodes with only one child node may be defined. In the above example, the maximum size of the sequence is 30 (eg, 30 bits). The result is that even though the combined subsections 602 and 604 would result in 35 consecutive non-leaf nodes with only one child, the subsection 602 is cut off at 30, leaving the subsection 604 uncompressed (because the subsection 604 is not compressed). 604 only includes 5 non-leaf nodes). As can be appreciated by those skilled in the art, many variations of the compression threshold and/or the maximum size of the sequence can be envisaged without departing from the scope of the present technology.

If the method determines that a given subsection of the determined tree structure is to be compressed, a compressed node data structure is generated. If the method determines not to compress a given subsection of the determined tree structure, an uncompressed node data structure is generated.

An example of a node data structure 800 is shown in FIG. 8, showing an example of a compressed node data structure 810 and an example of a non-compressed data structure 820 including common data structure portions 802, 804, and 806 . The total size of the node data structure 800 is 72 bits. In some implementations, 72 bits is the width of the memory cell in which the node data structure 800 is stored. The node data structure 800 includes a first block 802 "compressed" that includes 1 bit that indicates whether the node data structure 800 is compressed. The node data structure 800 also includes a second block 804 "label" that includes a label value (also known as 16 bits of network packet metadata). The node data structure 800 also includes a third block 806 "pointer to next node" which includes an indication that the node data structure 800 is associated (eg, parent-child association) 20 bits of the memory address of another node data structure.

For the instance in which the node data structure contains the compressed node data structure 810, the node data structure also includes a fourth block 812 "Branch Length" which includes a fourth block 812 "Branch Length" that includes a value indicating consecutive non-leaf nodes that have only one child node. number of 5 bits. In some embodiments, the maximum number of consecutive non-leaf nodes is 30. The node data structure also includes a fifth block 814, "Branch Path," which includes 30 bits that indicate the path to follow from the current node to the next node. In some embodiments, the path includes a bit sequence formed by a concatenation of single bits associated with each of the contiguous non-leaf nodes of the compressed sub-portion of the tree structure (eg, "10111100001000001"). In some embodiments, the compression threshold is 5, meaning that the number of bits of the sequence is equal to or greater than 6. If the number of bits is equal to or less than 5, an uncompressed node data structure is generated. In some other embodiments, the compression threshold is 3, meaning that the number of bits of the sequence is equal to or greater than 4. If the number of bits is equal to or less than 3, an uncompressed node data structure is generated. Accordingly, multiple values for the compression threshold may be envisaged without departing from the scope of the present technology.

In some implementations, the number of bits of the sequence of the compressed node data structure is determined by the presence of non-leaf nodes with cotyledon nodes (eg, the tree structure ends at the cotyledon nodes). In some embodiments, the number of bits of the sequence of compressed node data structures is determined by the presence of non-leaf nodes that have more than one child node (eg, two child nodes), thereby identifying the need to create additional node data structures (which can be compressed or uncompressed) forks in a tree structure. In some embodiments, the number of bits of the sequence of the compressed node data structure is a predefined maximum size of the sequence (eg, 30, to meet the format constraints of the node data structure).

For the instance where the node data structure contains the uncompressed node data structure 820, the node data structure also includes a sixth block 822 "padding bits" which includes 3 bits that may be garbage in this configuration ( That is, they "pad" the data structure to have a constant size (eg, 72 bits). The node data structure also includes a seventh block 824 "stop value" which includes 32 bits that can indicate whether the node is a non-leaf node (eg, not the end of the tree) or a leaf node (eg, the end of the tree) . In some implementations, the seventh block 824 indicates a path to a subsection of the tree structure. The path includes a bit sequence formed by a concatenation of one or more single bits associated with at least one non-leaf node of a subsection of the tree structure, the at least one non-leaf node having more than one child node, the sequence of The number of bits is less than the compression threshold (eg, "1011"). In some embodiments, the compression threshold is 5, meaning that the number of bits in the sequence is not greater than 5. If the number of bits is greater than 5, a compressed node data structure is generated.

In some embodiments, a non-compressed node can check a 5-bit signature, which means that there may be 2^5 possible paths of 5 bits (00000, 00001, 00010, 00011, 00100, ...). For each possible path, there may be a "stop" bit: bit 0 is zero if and only if path 00000 corresponds to a child node, and 1 otherwise. Bit 1 is zero if and only if path 00001 corresponds to a child node, and 1 otherwise. This yields 32 bit values. Each bit corresponds to a possible path and possible child node. In some implementations, a non-compressed node may have up to 32 child nodes. The pointer (806) can point to the first child, and the next child can be stored contiguously in memory (so the first child is at the address in 806, the second child is at address+1, and the third child at address +2...). Uncompressed nodes can have 0 to 32 children. In contrast, in some embodiments, a compressed node may have exactly one child node. Uncompressed nodes can support up to 32 5-bit paths, and compressed nodes can support only one 30-bit path.

Returning to a method of compressing a tree structure, if the method determines that a given subsection of the tree structure is to be compressed, a compressed node data structure (eg, compressed node data structure 810) is generated. If the method determines not to compress a given sub-portion of the determined tree structure, an uncompressed node data structure (eg, uncompressed node data structure 820) is generated. In accordance with the present technique, subsection 504 of tree structure 400 may be represented by a compressed node data structure P2/L2 that includes a path defined by the 10-bit sequence "0011111100".

Turning now to FIG. 9, an example of a non-transitory computer readable memory including four memory banks ("Bank 0", "Bank 1", "Bank 2", and "Bank 3") is shown. In some embodiments, all four memories are part of the same non-transitory computer readable memory. In some other implementations, each of the four memories defines a different non-transitory computer readable memory. In some implementations, the four memory banks may be referred to as a first non-transitory computer-readable memory, a second non-transitory computer-readable memory, a third non-transitory computer-readable memory, and a fourth non-transitory computer-readable memory computer readable memory. In some implementations, each of the first non-transitory computer-readable memory, the second non-transitory computer-readable memory, the third non-transitory computer-readable memory, and the fourth non-transitory computer-readable memory are Implemented as different QDR SRAM memories. In such an embodiment, bank 0 would be associated with the first QDR SRAM memory, bank 1 would be associated with the second QDR SRAM memory, bank 2 would be associated with the third QDR SRAM memory, and bank 3 will be associated with the fourth QDR SRAM memory.

8 in conjunction with FIGS. 4-7, a plurality of node data structures modeling tree structure 400 are stored across Bank 0, Bank 1, Bank 2, and Bank 3, in accordance with embodiments of the present technology. The plurality of node data structures include compressed node data structures and uncompressed data structures. The method for storing a plurality of node data structures includes: storing a first node data structure in a first memory bank in a memory bank, and storing a second node data structure (to which the first node data structure points) in a first memory bank in the memory bank. two memory banks, thereby avoiding accessing the same memory bank twice in a row when browsing the representation of the tree structure. As an example, the compressed node data structure P2/L2 is stored in bank 2 and points (eg, based on the "pointing address" stored in the compressed node data structure) to the uncompressed node stored in bank 0 Data structure P6/L5, uncompressed node data structure P6/L5 itself points to uncompressed node data structures P7/L6 and P8/L7 both stored in bank 1 (ie, P7/L6 and P8/L7 are stored in in the same bank as they represent two leaf nodes associated with non-leaf nodes P6/L5). As another example, uncompressed node data structure P5 stored in bank 3 points to an uncompressed node data structure stored in bank 2 associated with compressed data structure P12 stored in bank 2 P9/L8 and P11/L9, the compressed data structure P12 points to the uncompressed node data structure P13 stored in bank 0, and the uncompressed node data structure P13 in turn points to the uncompressed node stored in bank 1 Data structure P14/L10. As a result, browsing the tree structure can be accomplished by accessing different ones of the four banks from one node to another. The distribution of node data structures across banks may be such that, for each new node data structure to be introduced, the selected bank is the bank that has the smallest number of stored node data structures. For a given branch of the tree structure, all banks need to be used before looping back to used banks. As a result, in certain embodiments, the present techniques may enable optimization of the number of accesses to and use of a memory bank. As an example, associating a network packet signature associated with an IPv6 address with a network packet label and including a tree structure of compressed node data structures and uncompressed node data structures generated in accordance with the present technique may not require no more than eight steps to return the associated network packet label. As a result, the present technique may enable a reduction in the amount of memory to be used (which is more commonly beneficial where high performance memory such as QDR SRAM is used), while improving debiting, relative to conventional methods.

In some embodiments, each bank is divided into three sections. The first part stores the nodes of the first step of the tree, the second part stores the nodes of the subsequent steps of the tree, and the third part remains unused. When the tree structure needs to be updated, a new node data structure is introduced in the third part of the memory bank, then the memory address contained in the node data structure stored in the first part is updated so that it now points to the node data structure stored in the third part The newly created node data structure. If an additional update is required, introduce a new node data structure in the second part of one of the banks, then update the memory address contained in the node data structure stored in the first part so that it now points to the The newly created node data structure in the second part. Therefore, the method can create a new node data structure by alternately creating in the second and third parts. The method may enable the tree structure to be updated while providing continuous access to the tree structure.

In some implementations, if a non-leaf node points to a dead leaf node to be removed, the label (eg, network packet metadata) may be stored directly in the same directory with the value associated with the label by replacing the pointer to the leaf node with the value associated with the label. In the node data structure associated with non-leaf nodes. This method may enable access to the value of the label without the additional step of accessing another node data structure to which a non-leaf node would point.

Turning now to FIG. 10, a flowchart of a method 1000 for compressing a tree structure associating network packet signatures with network packet metadata is disclosed in accordance with one or more illustrative aspects of the present technology. In one or more embodiments, method 1000, or one or more steps thereof, may be performed by one or more computing devices or entities. Portions of method 1000 may be performed by components of networked device 100 or 190, for example. Method 1000, or one or more steps thereof, may be implemented as computer-executable instructions stored in a computer-readable medium, such as a non-transitory computer-readable medium. Some steps or part of the steps in the flowcharts may be omitted or changed in sequence.

In one or more embodiments, the tree structure associating network packet signatures with network packet metadata includes a plurality of leaf nodes containing the network packet metadata and a plurality of non-leaf nodes including single-bit test nodes.

At step 1002, for a subsection of the tree structure, the method establishes the number of consecutive non-leaf nodes that have a single child node. Then at step 1004, the method 1000 determines whether to compress the sub-portions of the tree structure based on the number of consecutive non-leaf nodes with a single child node and the compression threshold. If a determination is made to compress the sub-portion of the tree structure, the method 1000 proceeds to step 1006 . If a determination is made not to compress the sub-portions of the tree structure, the method 1000 proceeds to step 1008 .

At step 1006, a compressed node data structure is generated. The compressed node data structure includes a path of subsections of the tree structure, the path including a bit sequence formed by concatenation of single bits associated with each of the consecutive non-leaf nodes of the subsection of the tree structure, the sequence of which is The number of bits is equal to or greater than the compression threshold. In some embodiments, the number of bits of the sequence of the compressed node data structure is determined by the presence of (1) one of the consecutive non-leaf nodes having a cotyledon node, (2) one of the consecutive non-leaf nodes having more than one child node is determined by the presence of or (3) the predefined maximum size of the sequence. In some embodiments, the compression threshold is 5 bits. In some embodiments, the predefined maximum size of the sequence is 30 bits.

At step 1008, an uncompressed node data structure is generated. The uncompressed node data structure includes a path of a subsection of the tree structure, the path including a bit sequence formed by the concatenation of one or more single bits associated with at least one non-leaf node of the subsection of the tree structure, so that The at least one non-leaf node has more than one child node, and the number of bits of the sequence is less than the compression threshold. In some implementations, the path includes multiple paths that are sub-portions of the tree structure.

At step 1010, method 1000 may store the compressed node data structure or the uncompressed node data structure in a non-transitory computer readable memory.

In some implementations, the non-transitory computer-readable memory includes a first non-transitory computer-readable memory and a second non-transitory computer-readable memory. In some embodiments, the first non-transitory computer readable memory is a first bank of a first QDR SRAM memory and the second non-transitory computer readable memory is a second bank of a second QDR SRAM memory.

In some embodiments, the compressed node data structure is a first compressed node data structure, and (2) the uncompressed node data structure is a first uncompressed node data structure, wherein the first node data structure includes One of the first compressed node data structure and the first uncompressed node data structure, and the second node data structure includes one of the second compressed node data structure and the second uncompressed data structure. In some embodiments, the first node data structure is stored in the first non-transitory computer readable memory and points to a memory address of the second non-transitory computer readable memory where the second node data structure is stored. In some embodiments, the first node data structure can be accessed from the first non-transitory computer readable memory through a first single memory access, and the first node data structure can be accessed from the second non-transitory computer readable memory through a second single memory access Access the second node data structure.

In some implementations, the compressed node data structure is a first compressed node data structure, and the uncompressed node data structure is a first uncompressed node data structure, and wherein the non-transitory computer-readable memory includes The first part, the second part and the third part, the first part stores one of the first compressed node data structure and the first uncompressed node data structure, the first compressed node data structure and the first uncompressed node data One of the structures points to one of the second compressed node data structure and the second uncompressed node data structure stored in the second portion, and wherein, when updating the tree structure, the third compressed node data structure and One of the third uncompressed node data structures is stored in the third portion, and one of the first compressed node data structure and the first uncompressed node data structure is modified such that the first compressed node data structure and the first One of an uncompressed node data structure points to one of a third compressed node data structure and a third uncompressed node data structure.

In some embodiments, method 1000 further comprises at least one operation of: (1) transmitting the network packet based on a priority established through the network packet metadata, (2) identifying a service to perform on the network packet based on the network packet metadata, ( 3) Test the network packet based on the network packet metadata to establish that the network packet is part of a network attack and/or (4) create a measure of the traffic of the network packet based on the network packet metadata.

Although example embodiments are described above, the various features and steps may be combined, divided, omitted, rearranged, modified, or augmented in any desired manner, depending on the particular effect or application. Various changes, modifications, and improvements will readily occur to those skilled in the art. Although not expressly stated herein, such changes, modifications, and improvements apparent from the present disclosure are intended to be part of this specification, and are intended to be within the spirit and scope of the present disclosure. Accordingly, the foregoing description is by way of example only, and not limitation. This patent is limited only as defined in the following claims and their equivalents.

Claims (20)

1. A method of analyzing network packets for preventing attacks on a network by filtering illegitimate network packets while granting legitimate network packet access to the network, the filtering being based on associations between network addresses and data packet classifications, the associations being implemented as a tree structure, the data packet classifications enabling a determination of whether a network packet is legitimate, the method being performed by a computing device, the method comprising:

compressing the tree structure associating the network address with the data packet classification, the tree structure including a plurality of leaf nodes including a plurality of data packet classifications and a plurality of non-leaf nodes including a single bit test node, the step of compressing including:

determining whether to compress a sub-portion of the tree structure that includes a consecutive non-leaf node having a single child node based on a number of consecutive non-leaf nodes having a single child node and a compression threshold;

if a determination is made to compress the sub-portion of the tree structure, then:

generating a compressed sub-portion of the tree structure, the compressed sub-portion of the tree structure comprising a sequence of bits formed by a concatenation of a single bit associated with each of the consecutive non-leaf nodes of the sub-portion of the tree structure, the number of bits of the sequence being equal to or greater than the compression threshold; and

storing the compressed sub-portion of the tree structure in a non-transitory computer-readable memory.

2. The method of claim 1, wherein the number of bits of said sequence of said compressed subparts of said tree structure is determined by: (1) the presence of one of the consecutive non-leaf nodes having a child leaf node, (2) the presence of one of the consecutive non-leaf nodes having more than one child node, or (3) a predefined maximum size of the sequence.

3. The method of claim 1, further comprising:

if a determination is made to not compress the sub-portion of the tree structure, then:

generating an uncompressed subsection of the tree structure, the uncompressed subsection of the tree structure comprising a sequence of bits formed by a concatenation of one or more single bits associated with at least one non-leaf node of the subsection of the tree structure having more than one child node, the number of bits of the sequence being less than the compression threshold; and

storing the non-compressed sub-portion of the tree structure in the non-transitory computer readable memory.

4. The method of claim 1, wherein the compression threshold is 5 bits.

5. The method of claim 1, wherein the predefined maximum size of the sequence is 30 bits.

6. The method of claim 1, wherein the non-transitory computer readable memory comprises a first non-transitory computer readable memory and a second non-transitory computer readable memory.

7. The method of claim 6, wherein (1) the compressed subpart of the tree structure is a first compressed subpart of the tree structure and (2) the uncompressed subpart of the tree structure is a first uncompressed subpart of the tree structure, wherein a first subpart of the tree structure comprises one of the first compressed subpart of the tree structure and the first uncompressed subpart of the tree structure and a second subpart of the tree structure comprises one of a second compressed subpart of the tree structure and a second uncompressed subpart of the tree structure.

8. The method of claim 7, wherein the first sub-portion of the tree structure is stored in the first non-transitory computer readable memory and points to a memory address of the second non-transitory computer readable memory at which the second sub-portion of the tree structure is stored.

9. The method of claim 8, wherein the first sub-portion of the tree structure is accessible from the first non-transitory computer readable memory through a first single memory access and the second sub-portion of the tree structure is accessible from the second non-transitory computer readable memory through a second single memory access.

10. The method of claim 6, wherein the first non-transitory computer readable memory is a first bank of a first QDR SRAM memory and the second non-transitory computer readable memory is a second bank of a second QDR SRAM memory.

11. The method of claim 3, wherein the compressed subpart of the tree structure is a first compressed subpart of the tree structure and the non-compressed subpart of the tree structure is a first non-compressed subpart of the tree structure, and wherein the non-transitory computer readable memory comprises a first portion, a second portion, and a third portion, the first portion storing one of the first compressed subpart of the tree structure and the first non-compressed subpart of the tree structure, one of the first compressed subpart of the tree structure and the first non-compressed subpart of the tree structure pointing to one of a second compressed subpart of the tree structure and a second non-compressed subpart of the tree structure stored in the second portion, and wherein:

upon updating the tree structure, storing one of a third compressed subpart of the tree structure and a third non-compressed subpart of the tree structure in the third portion, and modifying one of the first compressed subpart of the tree structure and the first non-compressed subpart of the tree structure such that one of the first compressed subpart of the tree structure and the first non-compressed subpart of the tree structure points to one of the third compressed subpart of the tree structure and the third non-compressed node data structure.

12. The method of claim 1, further comprising at least one operation of: (1) transmit a network packet based on a priority established by the data packet classification, (2) identify a service to perform on the network packet based on the data packet classification, (3) test the network packet based on the data packet classification to establish that the network packet is part of a network attack and/or (4) create a metric of traffic for the network packet based on the data packet classification.

13. A method of compressing a tree structure that associates network packet signatures with network packet metadata, the tree structure including a plurality of leaf nodes that contain network packet metadata and a plurality of non-leaf nodes that contain single-bit test nodes, the method comprising:

for a sub-portion of the tree structure, establishing a number of consecutive non-leaf nodes having a single child node;

determining whether to compress the sub-portion of the tree structure based on the number of consecutive non-leaf nodes having a single child node and a compression threshold;

if a determination is made to compress the sub-portion of the tree structure, then:

generating a compressed node data structure comprising a path of the sub-portion of the tree structure, the path comprising a sequence of bits formed by a concatenation of single bits associated with each of the consecutive non-leaf nodes of the sub-portion of the tree structure, the number of bits of the sequence being equal to or greater than the compression threshold; and

storing the compressed node data structure in a non-transitory computer readable memory.

14. A system for analyzing network packets for preventing attacks on a network by filtering illegitimate network packets while granting legitimate network packet access to the network, the filtering being based on associations between network addresses and data packet classifications, the associations being implemented as a tree structure, the data packet classifications enabling a determination of whether a network packet is legitimate, the system comprising:

a processor;

a non-transitory computer readable medium comprising control logic that when executed by the processor causes:

compressing the tree structure associating the network address with the data packet classification, the tree structure including a plurality of leaf nodes including a plurality of data packet classifications and a plurality of non-leaf nodes including a single bit test node, the step of compressing including:

determining whether to compress a sub-portion of the tree structure that includes a consecutive non-leaf node having a single child node based on a number of consecutive non-leaf nodes having a single child node and a compression threshold;

if a determination is made to compress the sub-portion of the tree structure, then:

generating a compressed sub-portion of the tree structure, the compressed sub-portion of the tree structure comprising a sequence of bits formed by a concatenation of a single bit associated with each of the consecutive non-leaf nodes of the sub-portion of the tree structure, the number of bits of the sequence being equal to or greater than the compression threshold; and

storing the compressed sub-portion of the tree structure.

15. The system of claim 14, wherein a number of bits of the sequence of the compressed subpart of the tree structure is determined by (1) a presence of one of the consecutive non-leaf nodes having child leaf nodes, (2) a presence of one of the consecutive non-leaf nodes having more than one child node, or (3) a predefined maximum size of the sequence.

16. The system of claim 14, wherein the step of compressing further comprises:

if a determination is made to not compress the sub-portion of the tree structure, then:

generating an uncompressed subsection of the tree structure, the uncompressed subsection of the tree structure comprising a sequence of bits formed by a concatenation of one or more single bits associated with at least one non-leaf node of the subsection of the tree structure having more than one child node, the number of bits of the sequence being less than the compression threshold; and

storing the uncompressed subparts of the tree structure.

17. The system of claim 14, wherein the compression threshold is 5 bits.

18. The system of claim 14, wherein the predefined maximum size of the sequence is 30 bits.

19. The system of claim 14, wherein the non-transitory computer readable memory comprises a first non-transitory computer readable memory and a second non-transitory computer readable memory.

20. The system of claim 19, wherein (1) the compressed subpart of the tree structure is a first compressed subpart of the tree structure and (2) the uncompressed subpart of the tree structure is a first uncompressed subpart of the tree structure, wherein a first subpart of the tree structure comprises one of the first compressed subpart of the tree structure and the first uncompressed subpart of the tree structure and a second subpart of the tree structure comprises one of a second compressed subpart of the tree structure and a second uncompressed subpart of the tree structure.

Images