DETAILED ACTION
Status of the Claims
Claims 33-45, 47-57, and 59-61 are pending. Claims 1-32, 46, and 58 have been canceled. Claims 33-43, 50, 51, 55-57, and 61 have been withdrawn. No claims are objected to. Claims 44, 49, 54, 59, and 60 have been amended. No claims are allowable. Claims 44, 45, 47-49, 52-54, 59, and 60 are rejected under 35 U.S.C. § 103. As an alternate ground, claims 44, 45, 47-49, 52-54, 59, and 60 are additionally rejected under 35 U.S.C. § 103.
Other Prior Art
Ma et al. (US 9,507,813 B1) discloses hardware-implemented AVL tree updates in which records representing the nodes of an AVL tree are read from memory during a search and written to an AVL tree rebalancing component implemented in hardware, which modifies the records of the nodes affected by an insertion or removal and writes the modified records back to memory (Abstract).
Choe (US 7,031,320 B2) discloses constructing routing/forwarding tables for an IP address lookup using a skip list, in which a prefix length range of an IP address is divided and a header node configured to manage every node in the skip list is created together with subnodes each keyed by a divided prefix length range (col. 5, lines 4-11).
Huang et al. (US 7,782,853 B2) discloses a multi-bit trie network search engine implemented by a number of pipeline logic units, each limited to one memory access, coupled by a meshed crossbar to a set of memory blocks that hold the prefix tables and form a set of virtual memory banks (Abstract).
Response to Arguments
The arguments of Applicant’s representative filed May 1, 2026 have been fully considered.
Rejection of Claims 44, 54, and 59 under 35 U.S.C. § 103 over Su, Galperin, and either Pepper or de Wit.
Claim 44 was amended to recite that the first search tree is organized in the form of a first table and the second search tree is organized in the form of a second table, and that the at least one apparatus further comprises a multiplexer device via which the hardware component selectively accesses the first table or the second table based on a control signal to perform the hardware-based search. Applicant’s representative argues that the combination of Su, Galperin, and either Pepper or de Wit relied upon in the previous Office action does not teach or suggest claim 44 as amended. Examiner agrees. Nonetheless, the combination of Su, Galperin, Johnson, and Walia teaches or suggests amended claim 44, as discussed in the rejection below.
Rejection of Claims 45, 47-49, and 53 under 35 U.S.C. § 103 over Su, Galperin, and either Pepper or de Wit.
Applicant’s representative argues that claim 45 overcomes the previously cited prior art for the reasons provided with respect to claim 44, from which claim 45 depends. However, this argument is not persuasive for the reasons provided above with respect to claim 44.
Rejection of Claim 52 under 35 U.S.C. § 103 over Su, Galperin, either Pepper or de Wit, and Zeng.
Applicant’s representative argues that claim 52 overcomes the previously cited prior art for the reasons provided with respect to claim 44, from which claim 52 depends, and that Zeng does not cure the asserted deficiencies. However, this argument is not persuasive for the reasons provided above with respect to claim 44.
Rejection of Claim 60 under 35 U.S.C. § 103 over Tokunaga, Galperin, and either Pepper or de Wit.
Claim 60 was amended to recite that the first search tree is organized in the form of a first table and the second search tree is organized in the form of a second table, and that the at least one apparatus further comprises a multiplexer device via which the hardware component selectively accesses the first table or the second table based on a control signal to perform the hardware-based search. Applicant’s representative argues that the combination of Tokunaga, Galperin, and either Pepper or de Wit relied upon in the previous Office action does not teach or suggest claim 60 as amended. Examiner agrees. Nonetheless, the combination of Su, Galperin, Johnson, Walia, and Sim teaches or suggests amended claim 60, as discussed in the rejection below.
Claim Rejections - 35 U.S.C. § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 44, 45, 47-49, 54, and 59 are rejected under 35 U.S.C. § 103 as being unpatentable over Su et al. (US 2017/0171039 A1; “Su”), in further view of the non-patent literature entitled “Scapegoat Trees” (“Galperin”), Johnson (US 2018/0062998 A1; “Johnson”), and Walia et al. (US 6,678,274 B1; “Walia”).
Regarding claims 54, 44, and 59, Su teaches or suggests a computer-implemented method for processing data units, for an apparatus including a first number of input interfaces configured to receive protocol data units, and a checking device configured to check at least one received protocol data unit, the method comprising:
receiving at least one protocol data unit. The data packet transceiver module receives a data packet ([0039]).
checking the received at least one protocol data unit using the checking device. The flow table matching module checks whether flow table space stores a flow entry that matches the received data packet ([0050]).
performing, by a processing device, based on a PDU identifier associated with the received protocol data unit … a search. The network flow statistics collection module generates the network flow identifier for the received data packet and uses that identifier in the storage-space search to determine whether storage space stores the network flow identifier ([0107], [0115]).
the search is performed in at least a first search tree. The storage space may be a binary tree in which the network flow identifier is the key of a node ([0117]-[0118]).
the … search can be performed before and/or after and/or with an at least partial time overlap with the check. The flow table matching module first matches and forwards the received packet according to the matching flow entry, after which the network flow statistics collection module generates the packet’s network flow identifier and searches the storage space using that identifier ([0107], [0115]). The Office action relies on the recited “after” alternative.
the first search tree includes an allocation of in each case one PDU identifier to a connection identifier characterizing at least one data connection. The binary-tree node uses the network flow identifier as its key and stores corresponding network flow information as its value ([0118]). The network flow information includes flow-specific packet quantities, packet sizes, packet intervals, forwarding rates, bandwidth, and similar information for the corresponding network flow ([0095]); the network flow identifier reads on the PDU identifier and the corresponding network flow information reads on the connection identifier characterizing that data connection.
the processing device ascertains … a connection identifier associated with the received protocol data unit. The storage-space search locates the node for the packet’s network flow identifier and obtains the corresponding network flow information ([0115], [0118]).
The ascertaining operation above is performed based on the PDU identifier. The storage-space search is keyed by the network flow identifier generated for the received data packet ([0107], [0115]).
However, Su does not teach or suggest, but Galperin teaches or suggests, the processing device generates … a second search tree. The nodes of the tree are traversed in-order and copied to an auxiliary array, and a new 1/2-weight-balanced tree is built from that array (pg. 170, section 6).
the second search tree is separate from the first search tree. The new tree is built from the copied nodes in the auxiliary array rather than from the original tree itself, so the new tree is formed separately from the original (pg. 170, section 6).
the second search tree is based on the first search tree. The new tree is built from the nodes of the original tree copied to the auxiliary array (pg. 170, section 6).
the processing device balances … the second search tree in relation to the first search tree. The tree built from the auxiliary array by the divide and conquer method is 1/2-weight-balanced (pg. 170, section 6).
the processing device transmits a content and/or a structure of the balanced second search tree to the first search tree to provide a balanced first search tree. After a scapegoat node is found, the original subtree is replaced with the rebuilt 1/2-weight-balanced subtree containing the same nodes (pg. 167, section 4.2). The Office action relies on transmission of structure: replacing the original subtree installs the new node arrangement in the first search tree.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su so that the nodes of the original subtree are copied to an auxiliary array, a new 1/2-weight-balanced tree is built from that array, and the original subtree is replaced with the rebuilt balanced subtree, because doing so provides O(log n) worst-case search time.
Galperin further teaches or suggests that the generation of the second search tree and the balancing of the second search tree above are performed via a software component of the processing device. The rebuilding traverses the tree using a stack of logarithmic size and builds the new tree by a divide and conquer method (pg. 170, section 6).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su and Galperin so that Galperin’s rebuilding code performs the generation and balancing operations, because doing so keeps tree maintenance in software while the network flow statistics collection module performs the storage-space search.
Further, the combination of Su and Galperin does not teach or suggest that the search above is performed as a hardware-based search, via a hardware component. Nonetheless, Johnson teaches or suggests a hardware packet filtering system that uses binary search trees to perform packet filtering ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su and Galperin so that Johnson’s hardware packet filtering system performs the binary-tree search, because doing so supports high-speed packet filtering in dedicated hardware.
Johnson further teaches or suggests the first search tree is organized in the form of a first table. A zero-based binary search tree may be implemented as a table in which node numbers represent offsets into the table ([0028]).
the second search tree is organized in the form of a second table. The packet filtering system may store a plurality of binary search trees ([0019]), and each zero-based binary search tree may be implemented as a table ([0028]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, and Johnson so that each binary search tree is stored as a node-offset table, because doing so allows the next-node address to be reached from the current node and comparison result.
Johnson further teaches or suggests that the ascertaining operation above is performed via the hardware component. The hardware binary-search-tree filter performs the node comparisons used for the lookup ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, and Johnson so that Johnson’s hardware binary-search-tree filter performs the lookup that returns the stored network flow information, because doing so keeps the lookup in dedicated hardware.
Additionally, the combination of Su, Galperin, and Johnson does not teach or suggest, but Walia teaches or suggests, the apparatus further includes a multiplexer device. Lookups are routed to one of two forwarding-table memories 26 and 28, so that lookup engine 22 accesses the memory currently identified as active; that routing of the lookup access between two table memories is the function the recited multiplexer device performs (col. 5, lines 1-7).
the multiplexer device is one via which the hardware component selective accesses the first table or the second table. The routing determines which forwarding-table memory the lookup engine accesses, and changing it redirects the lookup from one memory to the other, so the lookup reaches the first table or the second table and not both (col. 5, lines 1-7, 56-60).
The selective access above is performed based on a control signal to perform the hardware-based search. Which memory the lookup is routed to is determined by the state of forwarding table pointer 24, which may be implemented as a one-bit register whose switching redirects the lookup from one memory to the other; that state is the signal on which the routing depends (col. 5, lines 7-10, 56-60).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su, Galperin, and Johnson so that each of the two binary search trees is stored as a table in one of the two forwarding-table memories and the hardware lookup is routed to one of those memories according to the state of the forwarding table pointer, because doing so permits one table to remain active for lookups while the other is updated in the background.
The combination of Su, Galperin, and Johnson further teaches or suggests the processing device searches, via the hardware component, the balanced first search tree, based on the PDU identifier. Su’s network flow statistics collection module searches the storage space for the network flow identifier of the received data packet ([0115]), Galperin’s rebuilt 1/2-weight-balanced subtree replaces the original subtree so that the arrangement searched is the balanced one (pg. 167, section 4.2), and Johnson’s hardware binary-search-tree filter performs the node comparisons ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, Johnson, and Walia so that the hardware binary-search-tree filter runs the storage-space search, keyed by the network flow identifier, against the rebuilt balanced node arrangement installed in the first search tree, because doing so bounds the number of node comparisons per lookup to the depth of a balanced tree.
Regarding claim 45, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 44, and Su further teaches or suggests wherein the ascertainment of the connection identifier associated with the received protocol data unit can be performed before and/or after and/or after and/or with an at least partial time overlap with the check. The flow table matching module first matches the received packet and the network flow statistics collection module then identifies and collects the corresponding network flow information ([0094]); in the combined tree, the corresponding network flow information is returned after that check.
Regarding claim 47, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 44, and Su further teaches or suggests wherein the first search tree is a binary tree. The network flow identifier and corresponding per-flow information may be stored in the form of a binary tree ([0117]-[0118]).
Regarding claim 48, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 44, and Su further teaches or suggests wherein the software component is configured to perform at least one of the following elements: a) at least temporarily forming the first search tree, b) at least temporarily modifying the first search tree, c) receiving the at least one protocol data unit from the checking device, d) performing a software-based, attack detection. The software-based network flow statistics collection module inserts a new network flow identifier into the storage space when the identifier is not present, thereby modifying the stored tree ([0085], [0119]). Because the limitation is recited in the alternative, element (b) satisfies the requirement.
Regarding claim 49, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 48, and Su further teaches or suggests wherein the software component is configured to perform a specifiable response if no connection identifier associated with the received protocol data unit can be ascertained for the received protocol data unit because no connection identifier associated with the received protocol data unit is present for the received protocol data unit in the first search tree or the second search tree, wherein the specifiable response includes at least one of the following elements: a) discarding the received protocol data unit, b) assigning a configurable connection identifier to the received protocol data unit, c) setting or inserting a first item of information or a first item of control information for the received protocol data unit, wherein the first item of information and/or the first item of control information indicates that the received protocol data unit is to be subjected to a check. If storage space does not store the network flow identifier of the received data packet, the network flow identifier and corresponding network flow information are added to the storage space; stored network flow information is thereafter updated ([0115], [0119]). Because the network flow information reads on the connection identifier and is added for the packet-associated key when none is present, alternative (b) is satisfied; the corresponding information is configurable because Su updates the stored network flow information.
Claim 52 is rejected under 35 U.S.C. § 103 as being unpatentable over Su, Galperin, Johnson, and Walia, as applied to claim 44 above, in further view of Zeng et al. (US 2017/0339109 A1; “Zeng”).
Regarding claim 52, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 44, but does not teach or suggest wherein a node structure for the first search tree includes an attribute that indicates whether a security check is to be performed for a relevant protocol data unit or for protocol data units associated with a connection identifier. Nonetheless, the combination of Su and Zeng teaches or suggests the recited attribute: Su stores per-flow information in the value field of each binary-tree node ([0118]), and Zeng stores a security-control identifier F-control in flow-table information and, after a flow match, checks whether F-control is 1 to determine whether to invoke in-depth security processing ([0056]-[0059]). Adding Zeng’s F-control to Su’s per-flow node value provides the recited node attribute indicating whether the security check is to be performed.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su, Galperin, Johnson, and Walia so that the binary-tree node value includes Zeng’s F-control security-control identifier, because doing so allows the matched flow entry to indicate whether the packet is sent for in-depth security processing.
Claim 53 is rejected under 35 U.S.C. § 103 as being unpatentable over Su, Galperin, Johnson, and Walia, as applied to claim 44 above, in further view of Dobbins et al. (US 7,743,166 B2; “Dobbins”).
Regarding claim 53, the combination of Su, Galperin, Johnson, and Walia teaches or suggests the apparatus according to claim 44, but does not teach or suggest wherein the checking device is configured to use the connection identifier for ascertaining a service and/or an identification associated with the received protocol data unit. Nonetheless, Dobbins teaches or suggests a flow key formed from a received packet that indexes a flow table to locate a flow entry associating an action and a service profile, and the packet processor references that entry to determine how the packet should be serviced (col. 6, lines 25-32, 38-40).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su, Galperin, Johnson, and Walia so that Su’s network flow information includes the service profile taught by Dobbins and Su’s flow table matching module uses the returned network flow information to ascertain the service for the received packet, because doing so makes the service profile for the flow available with the network flow information returned from the search tree without reassessing service for each packet.
Claim 60 is rejected under 35 U.S.C. § 103 as being unpatentable over Su, in further view of Galperin, Johnson, Walia, and Sim (US 11,102,628 B2; “Sim”).
Regarding claim 60, Su teaches or suggests at least one apparatus for processing data units, including:
a first number of input interfaces configured to receive protocol data units. The data packet transceiver module receives a data packet ([0039]).
a checking device configured to check at least one received protocol data unit. The flow table matching module checks whether flow table space stores a flow entry that matches the received data packet ([0050]).
a processing device which is configured to perform … a search. The network flow statistics collection module searches whether storage space stores the network flow identifier of the received data packet ([0115]).
The search above is performed based on a PDU identifier associated with a received protocol data unit. The network flow statistics collection module generates the network flow identifier for the received packet and uses that identifier in the storage-space search ([0107], [0115]).
the search is performed in at least a first search tree. The storage space may be a binary tree in which the network flow identifier is the node key ([0117]-[0118]).
the … search can be performed before and/or after and/or with an at least partial time overlap with the check. The flow table matching module first matches and forwards the received packet according to the matching flow entry, after which the network flow statistics collection module generates the packet’s network flow identifier and searches the storage space using that identifier ([0107], [0115]). The Office action relies on the recited “after” alternative.
the first search tree includes an allocation of in each case one PDU identifier to a connection identifier characterizing at least one data connection. The binary-tree node uses the packet-associated network flow identifier as its key and stores corresponding network flow information as its value ([0118]). The network flow information includes flow-specific packet quantities, packet sizes, packet intervals, forwarding rates, bandwidth, and similar information for the corresponding network flow ([0095]); the network flow identifier reads on the PDU identifier and the corresponding network flow information reads on the connection identifier characterizing that data connection.
the processing device is configured to ascertain … a connection identifier associated with the received protocol data unit. The storage-space search locates the per-flow node and obtains the corresponding network flow information ([0115], [0118]).
The ascertaining operation above is performed based on the PDU identifier. The storage-space search is keyed by the packet’s network flow identifier ([0107], [0115]).
However, Su does not teach or suggest, but Galperin teaches or suggests, the processing device is configured to generate … a second search tree. The nodes of the tree are traversed in-order and copied to an auxiliary array, and a new 1/2-weight-balanced tree is built from that array (pg. 170, section 6).
the second search tree is separate from the first search tree. The new tree is built from the copied nodes in the auxiliary array rather than from the original tree itself, so the new tree is formed separately from the original (pg. 170, section 6).
the processing device is configured to generate the second search tree based on the first search tree. The new tree is built from the nodes of the original tree copied to the auxiliary array (pg. 170, section 6).
the processing device is further configured to balance … the second search tree in relation to the first search tree. The tree built from the auxiliary array by the divide and conquer method is 1/2-weight-balanced (pg. 170, section 6).
the processing device is further configured to transmit a content and/or a structure of the balanced second search tree to the first search tree to provide a balanced first search tree. After a scapegoat node is found, the original subtree is replaced with the rebuilt 1/2-weight-balanced subtree containing the same nodes (pg. 167, section 4.2). The Office action relies on transmission of structure: replacing the original subtree installs the new node arrangement in the first search tree.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su so that the nodes of the original subtree are copied to an auxiliary array, a new 1/2-weight-balanced tree is built from that array, and the original subtree is replaced with the rebuilt balanced subtree, because doing so provides O(log n) worst-case search time.
Galperin further teaches or suggests that the generation of the second search tree and the balancing of the second search tree above are performed via a software component of the processing device. The rebuilding traverses the tree using a stack of logarithmic size and builds the new tree by a divide and conquer method (pg. 170, section 6).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su and Galperin so that Galperin’s rebuilding code performs the generation and balancing operations, because doing so keeps tree maintenance in software while the network flow statistics collection module performs the storage-space search.
Further, the combination of Su and Galperin does not teach or suggest that the search above is performed as a hardware-based search, via a hardware component. Nonetheless, Johnson teaches or suggests a hardware packet filtering system that uses binary search trees to perform packet filtering ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su and Galperin so that Johnson’s hardware packet filtering system performs the binary-tree search, because doing so supports high-speed packet filtering in dedicated hardware.
Johnson further teaches or suggests the first search tree is organized in the form of a first table. A zero-based binary search tree may be implemented as a table in which node numbers represent offsets into the table ([0028]).
the second search tree is organized in the form of a second table. The packet filtering system may store a plurality of binary search trees ([0019]), and each zero-based binary search tree may be implemented as a table ([0028]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, and Johnson so that each binary search tree is stored as a node-offset table, because doing so allows the next-node address to be reached from the current node and comparison result.
Johnson further teaches or suggests that the ascertaining operation above is performed via the hardware component. The hardware binary-search-tree filter performs the node comparisons used for the lookup ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, and Johnson so that Johnson’s hardware binary-search-tree filter performs the lookup that returns the stored network flow information, because doing so keeps the lookup in dedicated hardware.
Additionally, the combination of Su, Galperin, and Johnson does not teach or suggest, but Walia teaches or suggests, the at least one apparatus further includes a multiplexer device. Lookups are routed to one of two forwarding-table memories 26 and 28, so that lookup engine 22 accesses the memory currently identified as active; that routing of the lookup access between two table memories is the function the recited multiplexer device performs (col. 5, lines 1-7).
the multiplexer device is one via which the hardware component selectively accesses the first table or the second table. The routing determines which forwarding-table memory the lookup engine accesses, and changing it redirects the lookup from one memory to the other, so the lookup reaches the first table or the second table and not both (col. 5, lines 1-7, 56-60).
The selective access above is performed based on a control signal to perform the hardware-bases search. Which memory the lookup is routed to is determined by the state of forwarding table pointer 24, which may be implemented as a one-bit register whose switching redirects the lookup from one memory to the other; that state is the signal on which the routing depends (col. 5, lines 7-10, 56-60).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su, Galperin, and Johnson so that each of the two binary search trees is stored as a table in one of the two forwarding-table memories and the hardware lookup is routed to one of those memories according to the state of the forwarding table pointer, because doing so permits one table to remain active for lookups while the other is updated in the background.
Moreover, the combination of Su, Galperin, Johnson, and Walia does not teach or suggest that the at least one apparatus is comprised within an automotive gateway. Nonetheless, Sim teaches or suggests gateway 10, which performs routing for exchanging CAN messages between the plurality of controllers 101, 201, 311, 321, 401, and 501 connected to the different CAN channels of the vehicle communication network, and which includes memory 11 and processor 12 (col. 5, lines 1-2, 14-16; col. 6, lines 12-13).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Su, Galperin, Johnson, and Walia so that the data packet transceiver module, the flow table matching module, and the network flow statistics collection module are included in the gateway that performs routing for exchanging CAN messages between the plurality of controllers connected to the different CAN channels, as taught by Sim, because doing so covers every message exchanged between the controllers with a single instance of the checking device rather than one at each controller.
The combination of Su, Galperin, and Johnson further teaches or suggests the processing device being configured to search, via the hardware component, the balanced first search tree, based on the PDU identifier. Su’s network flow statistics collection module searches the storage space for the network flow identifier of the received data packet ([0115]), Galperin’s rebuilt 1/2-weight-balanced subtree replaces the original subtree so that the arrangement searched is the balanced one (pg. 167, section 4.2), and Johnson’s hardware binary-search-tree filter performs the node comparisons ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Su, Galperin, Johnson, Walia, and Sim so that the hardware binary-search-tree filter runs the storage-space search, keyed by the network flow identifier, against the rebuilt balanced node arrangement installed in the first search tree, because doing so bounds the number of node comparisons per lookup to the depth of a balanced tree.
Alternatively, claims 44, 45, 47, 48, 54, and 59 are rejected under 35 U.S.C. § 103 as being unpatentable over Dravida et al. (US 2007/0230493 A1; “Dravida”), in further view of Johnson and Galperin.
Regarding claims 54, 44, and 59, Dravida teaches or suggests a computer-implemented method for processing data units, for an apparatus including a first number of input interfaces configured to receive protocol data units, and a checking device configured to check at least one received protocol data unit, the method comprising:
receiving at least one protocol data unit. Packets received from WLAN (120) arrive at MAC/PHY interface (545) and are delivered to disaggregation unit (2802) ([0224]).
checking the received at least one protocol data unit using the checking device. FCS and filtering block (2804) determines whether a received packet is addressed to the device and checks the frame check sequence before passing an acceptable packet to FIFO (2812) ([0225]).
performing, by a processing device … a search. RX search controller (2814) monitors packets entering FIFO (2812), and a binary search is performed to determine the flow ID for the packet ([0235], [0237]).
The search above is performed based on a PDU identifier associated with the received protocol data unit. The flow ID is retrieved from the received packet’s TA plus TID, which provide the identification information used by the search ([0238]).
The search above is performed as a hardware-based search, via a hardware component. The binary search is done in hardware on the current table ([0238]).
the search is performed in at least a first [data structure]. The binary search is performed on the current table ([0238]).
the first [data structure] includes an allocation of in each case one PDU identifier to a connection identifier characterizing at least one data connection. The hardware table stores transmit addresses (2912), TIDs (2914), and corresponding flow IDs (2916), with the flow ID retrieved from the TA plus TID and used to index the appropriate RX flow state table ([0238]).
the … search can be performed before and/or after and/or with an at least partial time overlap with the check. FCS and filtering block (2804) checks the packet before passing it to FIFO (2812), and RX search controller (2814) thereafter monitors packets entering FIFO (2812) to determine the flow ID, satisfying the recited “after” alternative ([0225], [0235]).
the apparatus further includes a multiplexer device. The hardware’s search is routed to one of a current table and a standby table held in a ping-pong cache, and the current table is switched to the standby table once the firmware has ordered it; that routing of the hardware’s access between two tables is the function the recited multiplexer device performs ([0237], [0238]).
the multiplexer device is one via which the hardware component selective accesses the first table or the second table. The binary search is done in hardware on the current table while the firmware orders the standby table, and switching the current table to the standby table changes the table the hardware searches ([0238]).
The selective access above is performed based on a control signal to perform the hardware-based search. Which of the two tables the binary search is done on is determined by the firmware’s direction of the hardware to one table or another and by the switching of the current table to the standby table; that firmware direction is the signal on which the routing depends ([0238]).
the processing device ascertains … a connection identifier associated with the received protocol data unit. RX search controller (2814) determines the flow ID for the packet ([0235]).
The ascertaining operation above is performed based on the PDU identifier. The packet’s TA plus TID are used to retrieve the corresponding flow ID ([0238]).
The ascertaining operation above is performed via the hardware component. The binary search that returns the flow ID is done in hardware on the current table ([0238]).
However, Dravida does not teach or suggest, but Johnson teaches or suggests, the first [data structure] is a search tree. A hardware packet filtering system uses linked zero-based binary search trees to filter received packet information ([0015]-[0016]).
the first search tree is organized in the form of a first table. A zero-based binary search tree may be implemented as a table in which node numbers represent offsets into the table ([0028]).
the second search tree is organized in the form of a second table. The packet filtering system may store a plurality of binary search trees ([0019]), and each zero-based binary search tree may be implemented as a table ([0028]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida so that the current table and the standby table each store one of Johnson’s linked zero-based binary search trees as a table of node offsets, because doing so supports high-speed packet filtering and direct calculation of next-node addresses in dedicated hardware.
Further, the combination of Dravida and Johnson does not teach or suggest, but Galperin teaches or suggests, the processing device generates … a second search tree. The nodes of the tree are traversed in-order and copied to an auxiliary array, and a new 1/2-weight-balanced tree is built from that array (pg. 170, section 6).
the second search tree is separate from the first search tree. The new tree is built from the copied nodes in the auxiliary array rather than from the original tree itself, so the new tree is formed separately from the original (pg. 170, section 6).
the second search tree is based on the first search tree. The new tree is built from the nodes of the original tree copied to the auxiliary array (pg. 170, section 6).
the processing device balances … the second search tree in relation to the first search tree. The tree built from the auxiliary array by the divide and conquer method is 1/2-weight-balanced (pg. 170, section 6).
the processing device transmits a content and/or a structure of the balanced second search tree to the first search tree to provide a balanced first search tree. The original subtree is replaced with the rebuilt 1/2-weight-balanced subtree containing the same nodes (pg. 167, section 4.2), thereby installing the rebuilt node arrangement in the first search tree.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida and Johnson so that the nodes of the original subtree are copied to an auxiliary array, a new 1/2-weight-balanced tree is built from that array, and the original subtree is replaced with the rebuilt balanced subtree, because doing so provides O(log n) worst-case search time.
Galperin further teaches or suggests that the generation of the second search tree and the balancing of the second search tree above are performed via a software component of the processing device. The rebuilding traverses the tree using a stack of logarithmic size and builds the new tree by a divide and conquer method (pg. 170, section 6).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, and Galperin so that Galperin’s rebuilding code performs the generation and balancing operations, because doing so keeps tree maintenance in software while Dravida’s hardware performs the packet lookup.
The combination of Dravida, Johnson, and Galperin further teaches or suggests the processing device searches, via the hardware component, the balanced first search tree, based on the PDU identifier. Dravida’s binary search is done in hardware on the current table using the flow ID retrieved from the packet’s TA plus TID ([0238]), Johnson’s zero-based binary search tree is implemented as the table that search is done on ([0028]), and Galperin’s rebuilt 1/2-weight-balanced subtree replaces the original subtree so that the arrangement searched is the balanced one (pg. 167, section 4.2).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, and Galperin so that the hardware binary search is done, keyed by the packet’s TA plus TID, on the current table holding the rebuilt balanced node arrangement, because doing so bounds the number of node comparisons per lookup to the depth of a balanced tree.
Regarding claim 45, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 44, and Dravida further teaches or suggests wherein the ascertainment of the connection identifier associated with the received protocol data unit can be performed before and/or after and/or after and/or with an at least partial time overlap with the check. FCS and filtering block (2804) checks the packet before it reaches RX search controller (2814), which then determines the flow ID, satisfying the recited “after” alternative ([0225], [0235]).
Regarding claim 47, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 44, and Johnson further teaches or suggests wherein the first search tree is a binary tree. The packet filtering system uses linked zero-based binary search trees ([0015]-[0016]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, and Galperin so that the current table stores Johnson’s linked zero-based binary search tree as the tree the hardware binary search is done on, because doing so bounds the number of node comparisons per lookup to the depth of the tree.
Regarding claim 48, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 44, and Galperin further teaches or suggests wherein the software component is configured to perform at least one of the following elements: a) at least temporarily forming the first search tree, b) at least temporarily modifying the first search tree, c) receiving the at least one protocol data unit from the checking device, d) performing a software-based, attack detection. The original subtree is replaced with the rebuilt balanced subtree, thereby modifying the first search tree; because the limitation is recited in the alternative, element (b) satisfies the requirement (pg. 167, section 4.2).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, and Galperin so that the original subtree is replaced with the rebuilt balanced subtree during firmware-maintained updates, because doing so restores the balanced search structure after an update.
Alternatively, claim 49 is rejected under 35 U.S.C. § 103 as being unpatentable over Dravida, Johnson, and Galperin, as applied to claim 48 above, in further view of Kamisetti et al. (US 2019/0372933 A1; “Kamisetti”).
Regarding claim 49, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 48, but does not teach or suggest wherein the software component is configured to perform a specifiable response if no connection identifier associated with the received protocol data unit can be ascertained for the received protocol data unit because no connection identifier associated with the received protocol data unit is present for the received protocol data unit in the first search tree or the second search tree, wherein the specifiable response includes at least one of the following elements: a) discarding the received protocol data unit, b) assigning a configurable connection identifier to the received protocol data unit, c) setting or inserting a first item of information or a first item of control information for the received protocol data unit, wherein the first item of information and/or the first item of control information indicates that the received protocol data unit is to be subjected to a check. Nonetheless, the combination of Dravida, Johnson, Galperin, and Kamisetti teaches or suggests the recited limitation. Dravida, Johnson, and Galperin supply the first and second search-tree tables and the software component, while Kamisetti’s session manager (301) looks up whether a received packet is associated with an existing session; when no existing session is found, the session manager performs an ACL-rule lookup and, if no applicable ACL rule exists, drops the received packet. Configuration interface (307) permits the ACL rules to be programmed and updated, so the drop is a specifiable response ([0030], [0034]). Because the response alternatives are recited in the alternative, element (a) satisfies the requirement.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida, Johnson, and Galperin so that, when no flow ID corresponding to the received packet is present in either search-tree table, Dravida’s firmware software component applies Kamisetti’s ACL-controlled miss response and discards the packet when no applicable ACL rule exists, as taught by Kamisetti, because doing so prevents packets lacking an established or permitted connection from proceeding.
Alternatively, claim 52 is rejected under 35 U.S.C. § 103 as being unpatentable over Dravida, Johnson, and Galperin, as applied to claim 44 above, in further view of Zeng.
Regarding claim 52, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 44, but does not teach or suggest wherein a node structure for the first search tree includes an attribute that indicates whether a security check is to be performed for a relevant protocol data unit or for protocol data units associated with a connection identifier. Nonetheless, the combination of Johnson and Zeng teaches or suggests the recited attribute: Johnson’s binary-search-tree node stores action information used on a node hit ([0040]), and Zeng stores a security-control identifier F-control in flow-table information and checks whether F-control is 1 to determine whether to invoke in-depth security processing ([0056]-[0059]). Adding Zeng’s F-control to Johnson’s node action information provides the recited node attribute indicating whether the security check is to be performed.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida, Johnson, and Galperin so that Johnson’s node action information includes Zeng’s F-control security-control identifier, because doing so allows the matched flow node to indicate whether the packet is sent for in-depth security processing.
Alternatively, claim 53 is rejected under 35 U.S.C. § 103 as being unpatentable over Dravida, Johnson, and Galperin, as applied to claim 44 above, in further view of Dobbins.
Regarding claim 53, the combination of Dravida, Johnson, and Galperin teaches or suggests the apparatus according to claim 44, but does not teach or suggest wherein the checking device is configured to use the connection identifier for ascertaining a service and/or an identification associated with the received protocol data unit. Nonetheless, the combination of Dravida and Dobbins teaches or suggests the recited operation: Dravida’s hardware lookup returns the flow ID for the received packet ([0238]), and Dobbins teaches or suggests a packet-derived flow key that locates a flow entry associating an action and a service profile, which the packet processor references to determine how the packet should be serviced (col. 6, lines 25-32, 38-40).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida, Johnson, and Galperin so that the flow ID returned for the received packet is used to obtain Dobbins’s associated service profile in the packet-checking path, because doing so makes the service for the flow available without reassessing the service independently for each packet.
Alternatively, claim 60 is rejected under 35 U.S.C. § 103 as being unpatentable over Dravida, in further view of Johnson, Galperin, and Sim.
Regarding claim 60, Dravida teaches or suggests at least one apparatus for processing data units, including:
a first number of input interfaces configured to receive protocol data units. Packets received from WLAN (120) arrive at MAC/PHY interface (545) and are delivered to disaggregation unit (2802) ([0224]).
a checking device configured to check at least one received protocol data unit. FCS and filtering block (2804) determines whether a received packet is addressed to the device and checks the frame check sequence before passing an acceptable packet to FIFO (2812) ([0225]).
a processing device which is configured to perform … a search. RX search controller (2814) monitors packets entering FIFO (2812), and a binary search is performed to determine the flow ID for the packet ([0235], [0237]).
The search above is performed based on a PDU identifier associated with a received protocol data unit. The flow ID is retrieved from the packet’s TA plus TID ([0238]).
The search above is performed as a hardware-based search, via a hardware component. The binary search is done in hardware on the current table ([0238]).
the search is performed in at least a first [data structure]. The binary search is performed on the current table ([0238]).
the first [data structure] includes an allocation of in each case one PDU identifier to a connection identifier characterizing at least one data connection. The hardware table stores transmit addresses (2912), TIDs (2914), and corresponding flow IDs (2916), with the flow ID retrieved from the TA plus TID ([0238]).
the … search can be performed before and/or after and/or with an at least partial time overlap with the check. FCS and filtering block (2804) checks the packet before RX search controller (2814) determines the flow ID, satisfying the recited “after” alternative ([0225], [0235]).
the at least one apparatus further includes a multiplexer device. The hardware’s search is routed to one of a current table and a standby table held in a ping-pong cache, and the current table is switched to the standby table once the firmware has ordered it; that routing of the hardware’s access between two tables is the function the recited multiplexer device performs ([0237], [0238]).
the multiplexer device is one via which the hardware component selectively accesses the first table or the second table. The binary search is done in hardware on the current table while the firmware orders the standby table, and switching the current table to the standby table changes the table the hardware searches ([0238]).
The selective access above is performed based on a control signal to perform the hardware-bases search. Which of the two tables the binary search is done on is determined by the firmware’s direction of the hardware to one table or another and by the switching of the current table to the standby table; that firmware direction is the signal on which the routing depends ([0238]).
the processing device is configured to ascertain … a connection identifier associated with the received protocol data unit. RX search controller (2814) determines the flow ID for the packet ([0235]).
The ascertaining operation above is performed based on the PDU identifier. The packet’s TA plus TID are used to retrieve the corresponding flow ID ([0238]).
The ascertaining operation above is performed via the hardware component. The binary search that returns the flow ID is done in hardware on the current table ([0238]).
However, Dravida does not teach or suggest, but Johnson teaches or suggests, the first [data structure] is a search tree. A hardware packet filtering system uses linked zero-based binary search trees to filter received packet information ([0015]-[0016]).
the first search tree is organized in the form of a first table. A zero-based binary search tree may be implemented as a table in which node numbers represent offsets into the table ([0028]).
the second search tree is organized in the form of a second table. The packet filtering system may store a plurality of binary search trees ([0019]), and each zero-based binary search tree may be implemented as a table ([0028]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida so that the current table and the standby table each store one of Johnson’s linked zero-based binary search trees as a table of node offsets, because doing so supports high-speed packet filtering and direct calculation of next-node addresses in dedicated hardware.
Further, the combination of Dravida and Johnson does not teach or suggest, but Galperin teaches or suggests, the processing device is configured to generate … a second search tree. The nodes of the tree are traversed in-order and copied to an auxiliary array, and a new 1/2-weight-balanced tree is built from that array (pg. 170, section 6).
the second search tree is separate from the first search tree. The new tree is built from the copied nodes in the auxiliary array rather than from the original tree itself, so the new tree is formed separately from the original (pg. 170, section 6).
the processing device is configured to generate the second search tree based on the first search tree. The new tree is built from the nodes of the original tree copied to the auxiliary array (pg. 170, section 6).
the processing device is further configured to balance … the second search tree in relation to the first search tree. The tree built from the auxiliary array by the divide and conquer method is 1/2-weight-balanced (pg. 170, section 6).
the processing device is further configured to transmit a content and/or a structure of the balanced second search tree to the first search tree to provide a balanced first search tree. The original subtree is replaced with the rebuilt 1/2-weight-balanced subtree containing the same nodes (pg. 167, section 4.2), thereby installing the rebuilt node arrangement in the first search tree.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida and Johnson so that the nodes of the original subtree are copied to an auxiliary array, a new 1/2-weight-balanced tree is built from that array, and the original subtree is replaced with the rebuilt balanced subtree, because doing so provides O(log n) worst-case search time.
Galperin further teaches or suggests that the generation of the second search tree and the balancing of the second search tree above are performed via a software component of the processing device. The rebuilding traverses the tree using a stack of logarithmic size and builds the new tree by a divide and conquer method (pg. 170, section 6).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, and Galperin so that Galperin’s rebuilding code performs the generation and balancing operations, because doing so keeps tree maintenance in software while Dravida’s hardware performs the packet lookup.
Additionally, the combination of Dravida, Johnson, and Galperin does not teach or suggest that the at least one apparatus is comprised within an automotive gateway. Nonetheless, Sim teaches or suggests gateway 10, which performs routing for exchanging CAN messages between the plurality of controllers 101, 201, 311, 321, 401, and 501 connected to the different CAN channels of the vehicle communication network, and which includes memory 11 and processor 12 (col. 5, lines 1-2, 14-16; col. 6, lines 12-13).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system of Dravida, Johnson, and Galperin so that the MAC/PHY interface, the FCS and filtering block, and the RX search controller are included in the gateway that performs routing for exchanging CAN messages between the plurality of controllers connected to the different CAN channels, as taught by Sim, because doing so covers every message exchanged between the controllers with a single instance of the checking device rather than one at each controller.
The combination of Dravida, Johnson, and Galperin further teaches or suggests the processing device being configured to search, via the hardware component, the balanced first search tree, based on the PDU identifier. Dravida’s binary search is done in hardware on the current table using the flow ID retrieved from the packet’s TA plus TID ([0238]), Johnson’s zero-based binary search tree is implemented as the table that search is done on ([0028]), and Galperin’s rebuilt 1/2-weight-balanced subtree replaces the original subtree so that the arrangement searched is the balanced one (pg. 167, section 4.2).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to further modify the system of Dravida, Johnson, Galperin, and Sim so that the hardware binary search is done, keyed by the packet’s TA plus TID, on the current table holding the rebuilt balanced node arrangement, because doing so bounds the number of node comparisons per lookup to the depth of a balanced tree.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Andrew Georgandellis whose telephone number is 571-270-3991. The examiner can normally be reached on Monday through Friday, 7:30-5:00 PM EST. If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Tonia Dollinger, can be reached on 571-272-4170. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding application status may be obtained from Patent Center; unpublished application information is available there to authorized users. Questions about access to the USPTO patent electronic filing system may be directed to the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
/ANDREW C GEORGANDELLIS/Primary Examiner, Art Unit 2459
Prosecution Insights