DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Information Disclosure Statement
The information disclosure statements (IDS) submitted on November 21st, 2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
This office action is responsive to application filed on June 7th, 2024. In this office action:
Claims 1-20 are pending.
Claims 1-20 are rejected.
Drawings
The drawings submitted on June 7th, 2024 have been considered and accepted.
Claim Objections
Claim 1 is objected to because of the following informality:
“performing, the network device, a first-stage search in a first-stage memory …” should read (Examiner’s suggestion) “performing, by the network device, a first-stage search in a first-stage memory.”
Claims 2, 12, and 14 are objected to because of the following informality:
“...possible values including only values that are used by the nodes in the network” should read (Examiner’s suggestion) “... the subset of possible values including only values that are used by the network nodes ” Examiner’s suggestion is for consistency.
Claim 13 is objected to because of the following informality:
“wherein the search engine is configured to search the first-stage TCAM based on a particular search key …” should read (Examiner’s suggestion) “wherein the search engine is configured to search the first-stage TCAM based on [[ the particular search key ...”
Appropriate correction(s) is/are required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) ELEMENT IN CLAIM FOR A COMBINATION.—An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as "configured to" or "so that"; and
the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that use the words “processor” and “generator.” Such claim limitations are: Claim 11 recites a “packet processor” configured to process packets; a “key generator” configured to generate one or more search keys. Claim 18 recites the “packet processor” configured to perform the first-stage search. Claim 19 recites the “packet processor” configured to perform the first-stage search.
As the specification doesn’t seem to explicitly describe the structure of both the “packet processor” and the “key generator,” the Examiner interprets both “packet processor” and “key generator,” as software components.
Because these claim limitations are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, they are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have these limitations interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections – 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(B) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of pre-AIA 35 U.S.C. 112, second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 18-19 are rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112,
second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, or for pre-AIA the applicant regards as the invention.
Claim 18 recites the limitation “wherein the packet processor is configured to perform the first-stage search to map one or both of ...”
Independent claim 11 recites “the search engine configured to: perform a first-stage search in a first-stage memory to map the one or more search keys to one or more search key identifiers ...” According to base claim 11, the first-stage search is performed by the “search engine” and not the “packet processor.” Therefore, the Examiner is unable to determine the metes and the bounds of the claim language.
For examination purposes, the Examiner interprets the limitation as “wherein the [[search engine is configured to perform the first-stage search to map one or both of ...”
Claim 19 recites the limitation “wherein the packet processor is configured to perform the first-stage search to map one or both of ...”
Independent claim 11 recites “the search engine configured to: perform a first-stage search in a first-stage memory to map the one or more search keys to one or more search key identifiers ...” According to base claim 11, the first-stage search is performed by the “search engine” and not the “packet processor.” Therefore, the Examiner is unable to determine the metes and the bounds of the claim language.
For examination purposes, the Examiner interprets the limitation as “wherein the [[search engine is configured to perform the first-stage search to map one or both of ...”
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-9 and 11-19 are rejected under 35 U.S.C. 103 as being unpatentable over Katzri et al. (Pub. No. US 2023/0052252), hereinafter Katzri; in view of Bosshart et al. (Pub. No. US 2019/0236103), hereinafter Bosshart.
Claim 1. Katzri discloses [a] method for processing packets by a network device operating in a network having network nodes, the method comprising:
generating, by the network device (See Fig. 1 and Parag. [0007]; “Network Device 100”), one or more search keys to include information retrieved from one or more fields in a header of a packet being processed by the network device (See Parag. [0007]; a network device comprises: a packet processor configured to process packets communicated over a network, the processing including generating a search key representative of a packet, the search key including header information retrieved from the packet);
performing, the network device, a first-stage search in a first-stage memory to map the one or more search keys to one or more search key identifiers (See Parag. [0007]; network device comprises: ... a lookup engine coupled to the processing processor. The lookup engine includes: a ternary content addressable memory (TCAM) (a first-stage memory) configured to store a plurality of search patterns (one or more search key identifiers) ... See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key. At block 212, the TCAM outputs a respective index corresponding to each search pattern stored in the TCAM that match the search key. For example, the TCAM 124 outputs a respective index corresponding to each search pattern in a respective entry 128 of the TCAM 124 that match the search key. See also Parag. [0014] [0023] [0037]),
performing, by the network device, a second-stage search in a second-stage memory based on a combination of the one or more search key identifiers to identify an entry, in the second-stage memory, that matches the combination of the one or more search key identifiers, the entry indicating a rule, among a set of rules defined for processing packets by the network device, matched by the packet (See Parag. [0038-0039] and Fig. 2; At block 220, when the TCAM outputs multiple indices at block 212, the lookup engine analyzes priority information retrieved from a memory at block 216 to select one of the indices. For example, the lookup engine selects one of the indices that has a highest priority level ... At block 224, the lookup engine retrieves rule information from a second memory (a second-stage memory) that corresponds to the index selected at block 220, the second memory being separate from the TCAM ... the controller 160 retrieves from the RAM 140 (i.e., second memory) rule information from an entry 144 that corresponds to an index from the TCAM 124 that was selected by the controller 160. See Parag. [0023]; The RAM 140 includes a plurality of entries 144 that store rules associated with the search patterns stored in the TCAM 124. The rules in the RAM 140 indicate processing actions to be performed on packets that match respective search patterns stored in the TCAM 12. See also Parag. [0030] [0041]); and
performing, with respect to the packet, an action associated with the rule (See Parag. [0008]; determining, by the network device, one or more actions to be performed on the packet by the network device, the one or more actions corresponding to the selected one search pattern. See Parag. [0023]; The rules in the RAM 140 indicate processing actions to be performed on packets that match respective search patterns stored in the TCAM 124. See also Parag. [0085]).
Katzri doesn’t explicitly disclose respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys.
However, Bosshart discloses respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys (See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from the RAM 140 that correspond to the indices. See Parag. [0043] and Fig. 7-8; receives (at 705) an unmasked input key (one or more search keys) to match an entry in the ternary lookup table (which is divided into several sub-tables). The input key can, for example, be a field in an incoming packet received at a router that specifies the destination IP address for the packet ... See Parag. [0047]; ... the destination IP address is 11111010 (the one or more search keys). The destination address is used by TCAM hardware to search in table 605, which is stored in TCAM. The search produces two matches, sub-table key 633 with value of 1111* (one or more search key identifiers) and sub-table key 634 with value of *... See Parag. [0040]; table 605 stores the sub-table keys and the associated masks (conceptually shown together as a numeric value followed by a *). Table 605 is a ternary sub-table keys table, which is stored in TCAM 610. See also Parag. [0041] [0007]. Examiner’s interpretation: The Examiner notes that by comparing the unmasked input key (i.e., search key) with the masks (numeric values) (i.e., one or more search key identifiers), the masks (e.g., 1111*) is shorter than corresponding unmasked input key (e.g., 11111010). The masks are reduced in size).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teaching of Katzri, to include respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys, as taught by Bosshart. This would be convenient such that storing only the sub-table indexes and the associated masks in TCAM reduces the need to store all search entries in TCAM (Bosshart, Parag. [0009]).
Claim 2. Katzri in view of Bosshart discloses [t]he method of claim 1,
Katzri further discloses wherein performing the first-stage search in the first-stage memory includes performing the first-stage search based on a particular search key among the one or more search keys in a first-stage ternary content accessible memory (TCAM) that includes a plurality of entries storing only a subset of possible values of a header field corresponding to the particular search key, the subset of possible values including only values that are used by the nodes in the network (See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key. At block 212, the TCAM outputs a respective index corresponding to each search pattern stored in the TCAM that match the search key. For example, the TCAM 124 outputs a respective index corresponding to each search pattern in a respective entry 128 of the TCAM 124 that match the search key).
Claim 3. Katzri in view of Bosshart discloses [t]he method of claim 2,
Katzri further discloses wherein performing the first-stage search in the first-stage TCAM based on the particular search key includes searching the first-stage TCAM to find an entry that matches the particular search key, wherein an index of the entry that matches the particular search key corresponds to a search key identifier that maps to the particular search key (See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key. At block 212, the TCAM outputs a respective index corresponding to each search pattern stored in the TCAM that match the search key. For example, the TCAM 124 outputs a respective index corresponding to each search pattern in a respective entry 128 of the TCAM 124 that match the search key).
Claim 4. Katzri in view of Bosshart discloses [t]he method of claim 2,
Katzri further discloses wherein performing the first-stage search in the first-stage memory includes performing respective searches in respective ones of multiple first-stage TCAMs based on respective ones of the one or more search keys to find respective entries that match respective ones of the one or more search keys, wherein respective indexes of the entries that match the respective ones of the one or more search keys correspond to respective search key identifiers that map to the respective search keys (See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key. At block 212, the TCAM outputs a respective index corresponding to each search pattern stored in the TCAM that match the search key. For example, the TCAM 124 outputs a respective index corresponding to each search pattern in a respective entry 128 of the TCAM 124 that match the search key. See Parag. [0003]; Network devices such as network switches, routers, bridges, etc., often use ternary content addressable memories (TCAMs) to recognize known patterns within header information of packets being processed by the network device. See also Parag. [0014]).
Claim 5. Katzri in view of Bosshart discloses [t]he method of claim 1,
Katzri further discloses wherein performing the second-stage search comprises performing the second-stage search in a second-stage ternary content accessible memory (TCAM) that includes a plurality of entries storing search patterns corresponding to different combinations of the one or more search key identifiers (See Parag. [0038-0039] and Fig. 2; At block 220, when the TCAM outputs multiple indices at block 212, the lookup engine analyzes priority information retrieved from a memory at block 216 to select one of the indices. For example, the lookup engine selects one of the indices that has a highest priority level ... At block 224, the lookup engine retrieves rule information from a second memory (second-stage memory) that corresponds to the index selected at block 220, the second memory being separate from the TCAM (i.e., in the first stage search). See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from the RAM 140 that correspond to the indices).
Katzri doesn’t explicitly disclose the one or more search key identifiers that are shorter than the corresponding ones of the one or more search keys.
However, Bosshart discloses the one or more search key identifiers that are shorter than the corresponding ones of the one or more search keys (See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from the RAM 140 that correspond to the indices. See Parag. [0043] and Fig. 7-8; receives (at 705) an unmasked input key (one or more search keys) to match an entry in the ternary lookup table (which is divided into several sub-tables). The input key can, for example, be a field in an incoming packet received at a router that specifies the destination IP address for the packet ... See Parag. [0047]; ... the destination IP address is 11111010 (the one or more search keys). The destination address is used by TCAM hardware to search in table 605, which is stored in TCAM. The search produces two matches, sub-table key 633 with value of 1111* (one or more search key identifiers) and sub-table key 634 with value of *... See Parag. [0040]; table 605 stores the sub-table keys and the associated masks (conceptually shown together as a numeric value followed by a *). Table 605 is a ternary sub-table keys table, which is stored in TCAM 610. See also Parag. [0041] [0007]. Examiner’s interpretation: The Examiner notes that by comparing the unmasked input key (i.e., search key) with the masks (numeric values) (i.e., one or more search key identifiers), the masks (e.g., 1111*) is shorter than corresponding unmasked input key (e.g., 11111010). The masks are reduced in size).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teaching of Katzri, to include the one or more search key identifiers that are shorter than the corresponding ones of the one or more search keys, as taught by Bosshart. This would be convenient such that storing only the sub-table indexes and the associated masks in TCAM reduces the need to store all search entries in TCAM (Bosshart, Parag. [0009]).
Claim 6. Katzri in view of Bosshart discloses [t]he method of claim 5,
Katzri doesn’t explicitly disclose wherein: the set of rules defined for processing packets by the network device includes one or more rules that include ranges of port numbers; and performing the first-stage search includes identifying an entry in the first-stage memory that includes a masked value that maps any value within a given range of port numbers to a same search key identifier.
However, Bosshart discloses the set of rules defined for processing packets by the network device includes one or more rules that include ranges of port numbers; and performing the first-stage search includes identifying an entry in the first-stage memory that includes a masked value that maps any value within a given range of port numbers to a same search key identifier (See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from from the RAM 140 that correspond to the indices. See Parag. [0043] and Fig. 7-8; receives (at 705) an unmasked input key to match an entry in the ternary lookup table (which is divided into several sub-tables) ... See Parag. [0040]; table 605 stores the sub-table keys and the associated masks (conceptually shown together as a numeric value followed by a *). See Parag. [0050]; the ternary sub-table keys table 605 includes the port label for the network switch port that has received the packet. For instance, the network switch may have 16 ports. The 16 ports in the example of FIG. 9 are divided into 5 groups (or port labels) 931-935. Switch port label 1 931 may include switch ports 1, 8, and 12 while switch port label 2 932 may include switch ports 2, 9, 11, and 13).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teaching of Katzri, to include the set of rules defined for processing packets by the network device includes one or more rules that include ranges of port numbers, and performing the first-stage search includes identifying an entry in the first-stage memory that includes a masked value that maps any value within a given range of port numbers to a same search key identifier, as taught by Bosshart. This would be convenient such that storing only the sub-table indexes and the associated masks in TCAM reduces the need to store all search entries in TCAM (Bosshart, Parag. [0009]).
Claim 7. Katzri in view of Bosshart discloses [t]he method of claim 5,
Katzri doesn’t explicitly disclose wherein: the set of rules defined for processing packets by the network device includes a first rule that includes a port number range and a second rule that includes a port number that is within the port number range; performing the first-stage search includes identifying a first entry in the first-stage memory that includes a masked value and that maps any value within the port number range to a first search key identifier or a second entry that includes the port number that is within the port number range and that maps the port number that is within the port number range to a second search key identifier different from the first search key identifier; and performing the second-stage search includes identifying an entry in the second-stage memory that matches both the first search key identifier and the second search key identifier.
However, Bosshart discloses the set of rules defined for processing packets by the network device includes a first rule that includes a port number range and a second rule that includes a port number that is within the port number range; performing the first-stage search includes identifying a first entry in the first-stage memory that includes a masked value and that maps any value within the port number range to a first search key identifier or a second entry that includes the port number that is within the port number range and that maps the port number that is within the port number range to a second search key identifier different from the first search key identifier; and performing the second-stage search includes identifying an entry in the second-stage memory that matches both the first search key identifier and the second search key identifier (See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from from the RAM 140 that correspond to the indices. See Parag. [0043] and Fig. 7-8; receives (at 705) an unmasked input key to match an entry in the ternary lookup table (which is divided into several sub-tables) ... See Parag. [0040]; table 605 stores the sub-table keys and the associated masks (conceptually shown together as a numeric value followed by a *). See Parag. [0050]; the ternary sub-table keys table 605 includes the port label for the network switch port that has received the packet. For instance, the network switch may have 16 ports. The 16 ports in the example of FIG. 9 are divided into 5 groups (or port labels) 931-935. Switch port label 1 931 may include switch ports 1, 8, and 12 while switch port label 2 932 may include switch ports 2, 9, 11, and 13).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teaching of Katzri, to include the set of rules defined for processing packets by the network device includes a first rule that includes a port number range and a second rule that includes a port number that is within the port number range; performing the first-stage search includes identifying a first entry in the first-stage memory that includes a masked value and that maps any value within the port number range to a first search key identifier or a second entry that includes the port number that is within the port number range and that maps the port number that is within the port number range to a second search key identifier different from the first search key identifier; and performing the second-stage search includes identifying an entry in the second-stage memory that matches both the first search key identifier and the second search key identifier, as taught by Bosshart. This would be convenient to match and an action to perform if there is a match (Bosshart, Parag. [0055]).
Claim 8. Katzri in view of Bosshart discloses [t]he method of claim 1,
Katzri further discloses wherein performing the first-stage search in the first memory includes performing the first-stage search (See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key) to map one or both of i) layer 3 information included in the one or more search keys to one or more search key identifiers, the layer 3 information extracted from a layer 3 header of the packet (See Parag. [0030]; the processing engine 116 is configured to generate the search key to include at least a destination IP address) and ii) layer 4 information included in the one or more search keys to one or more search key identifiers, the layer 3 information extracted from a layer 4 header of the packet (See Parag. [0021]; The processing engine 116 is configured to generate, for each of at least some packets received by the network device 100, a search key that includes header information from the packet, such as one or more fields from one or more headers of the packet. Optionally, the processing engine 116 is configured to generate the search key to also include metadata regarding the packet, such as an identifier of a port of the network device that received the packet).
Claim 9. Katzri in view of Bosshart discloses [t]he method of claim 1,
Katzri further discloses performing the first-stage search in the first memory includes performing the first-stage search (See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key) to map one or more of i) a first search key that includes an internet protocol version four (IPv4) or an internet protocol version six (IPv6) source address extracted from the header of the packet to a first search key identifier, ii) a second search key that includes an IPv4 or an IPv6 destination address extracted from the header of the packet to a second search key identifier (See Parag. [0031]; The processing engine 116 is configured to generate the search key to include network address information (e.g., one of, or any suitable combination of two or more of, a destination address, such as a destination media access control (MAC) address, a destination IP address, etc.; a source address, e.g., a source MAC address, a source IP address, etc.). See also Parag. [0030]. Examiner’s note: IP addresses are either IPv4 or IPv6), iii) a third search key that includes a transmission control protocol (TCP) or a user datagram protocol (UDP) source port number extracted from the header of the packet to a third search key identifier, or iv) a fourth search key to include a TCP or a UDP destination port number extracted from the header of the packet to a fourth search key identifier (See Parag. [0021]; The processing engine 116 is configured to generate, for each of at least some packets received by the network device 100, a search key that includes header information from the packet, such as one or more fields from one or more headers of the packet. Optionally, the processing engine 116 is configured to generate the search key to also include metadata regarding the packet, such as an identifier of a port of the network device that received the packet. See Parag. [0031]; the processing engine 116 is configured to generate the search key to also include transmission control protocol (TCP) port information and/or user datagram protocol (UDP) port information (e.g., one of or any suitable combination of two or more of a TCP source port, a TCP destination port, a UDP source port, a UDP destination port)).
Claim 11. Katzri discloses [a] network device (See Fig. 1 and Parag. [0007]; “Network Device 100”), comprising:
a packet processor configured to process packets communicated over a network having network nodes, the packet processor including a key generator configured to generate one or more search keys based on one or more header fields in a header of a packet being processed by the network device (See Parag. [0007]; a network device comprises: a packet processor configured to process packets communicated over a network, the processing including generating a search key representative of a packet, the search key including header information retrieved from the packet); and
a search engine configured to determine an action to be performed with respect to the packet based on the one or more search keys, the search engine configured to:
perform a first-stage search in a first-stage memory to map the one or more search keys to one or more search key identifiers (See Parag. [0007]; network device comprises: ... a lookup engine coupled to the processing processor. The lookup engine includes: a ternary content addressable memory (TCAM) (a first-stage memory) configured to store a plurality of search patterns (one or more search key identifiers) ... See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key. For example, the TCAM 124 searches for all search patterns in entries 128 of the TCAM 124 that match the search key. At block 212, the TCAM outputs a respective index corresponding to each search pattern stored in the TCAM that match the search key. For example, the TCAM 124 outputs a respective index corresponding to each search pattern in a respective entry 128 of the TCAM 124 that match the search key. See also Parag. [0014] [0023] [0037]),
perform a second-stage search in a second-stage memory based on a combination of the one or more search key identifiers to identify an entry that matches the combination of the one or more search key identifiers, the entry indicating a rule matched by the packet (See Parag. [0038-0039] and Fig. 2; At block 220, when the TCAM outputs multiple indices at block 212, the lookup engine analyzes priority information retrieved from a memory at block 216 to select one of the indices. For example, the lookup engine selects one of the indices that has a highest priority level ... At block 224, the lookup engine retrieves rule information from a second memory (a second-stage memory) that corresponds to the index selected at block 220, the second memory being separate from the TCAM ... the controller 160 retrieves from the RAM 140 (i.e., second memory) rule information from an entry 144 that corresponds to an index from the TCAM 124 that was selected by the controller 160. See Parag. [0023]; The RAM 140 includes a plurality of entries 144 that store rules associated with the search patterns stored in the TCAM 124. The rules in the RAM 140 indicate processing actions to be performed on packets that match respective search patterns stored in the TCAM 12. See also Parag. [0030] [0041]),
identify an action to be performed with respect to the packet based on the rule matched by the packet, and provide an indication of the action to the packet processor to perform the action with respect to the packet, based on the rule (See Parag. [0008]; determining, by the network device, one or more actions to be performed on the packet by the network device, the one or more actions corresponding to the selected one search pattern. See Parag. [0023]; The rules in the RAM 140 indicate processing actions to be performed on packets that match respective search patterns stored in the TCAM 124. See also Parag. [0085]).
Katzri doesn’t explicitly disclose respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys.
However, Bosshart discloses respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys (See Parag. [0028]; The lookup engine 120 is configured to use the indices output by the TCAM 124 to retrieve the entries 144 from the RAM 140 that correspond to the indices. See Parag. [0043] and Fig. 7-8; receives (at 705) an unmasked input key (one or more search keys) to match an entry in the ternary lookup table (which is divided into several sub-tables). The input key can, for example, be a field in an incoming packet received at a router that specifies the destination IP address for the packet ... See Parag. [0047]; ... the destination IP address is 11111010 (the one or more search keys). The destination address is used by TCAM hardware to search in table 605, which is stored in TCAM. The search produces two matches, sub-table key 633 with value of 1111* (one or more search key identifiers) and sub-table key 634 with value of *... See Parag. [0040]; table 605 stores the sub-table keys and the associated masks (conceptually shown together as a numeric value followed by a *). Table 605 is a ternary sub-table keys table, which is stored in TCAM 610. See also Parag. [0041] [0007]. Examiner’s interpretation: The Examiner notes that by comparing the unmasked input key (i.e., search key) with the masks (numeric values) (i.e., one or more search key identifiers), the masks (e.g., 1111*) is shorter than corresponding unmasked input key (e.g., 11111010). The masks are reduced in size).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teaching of Katzri, to include respective ones of the one or more search key identifiers being shorter than corresponding ones of the one or more search keys, as taught by Bosshart. This would be convenient such that storing only the sub-table indexes and the associated masks in TCAM reduces the need to store all search entries in TCAM (Bosshart, Parag. [0009]).
Claim 12 is taught by Katzri in view of Bosshart as described for claim 2.
Claim 13 is taught by Katzri in view of Bosshart as described for claim 3.
Claim 14. Katzri in view of Bosshart discloses [t]he network device of claim 12,
Katzri further discloses wherein the first-stage TCAM includes multiple TCAMs that include respective entries storing respective subsets of possible values of respective header fields corresponding to respective search keys among the one or more search keys, the respective subsets of possible values including only values that are used by the nodes in the network (See Parag. [0003]; Network devices such as network switches, routers, bridges, etc., often use ternary content addressable memories (TCAMs) to recognize known patterns within header information of packets being processed by the network device. See Parag. [0034-0036] and Fig. 2; a lookup engine receives a search key. For example, the lookup engine 120 receives a search key from the processing engine 116. At block 208, the TCAM compares the search key to all search patterns stored in the TCAM to find stored search patterns that match the search key ...).
Claim 15 is taught by Katzri in view of Bosshart as described for claim 5.
Claim 16 is taught by Katzri in view of Bosshart as described for claim 6.
Claim 17 is taught by Katzri in view of Bosshart as described for claim 7.
Claim 18 is taught by Katzri in view of Bosshart as described for claim 8.
Claim 19 is taught by Katzri in view of Bosshart as described for claim 9.
Claims 10 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Katzri et al. (Pub. No. US 2023/0052252), hereinafter Katzri; in view of Bosshart et al. (Pub. No. US 2019/0236103), hereinafter Bosshart; and further in view of Atad et al. (Pub. No. US 2018/0262466), hereinafter Atad.
Claim 10. Katzri in view of Bosshart discloses [t]he method of claim 1,
Katzri in view of Bosshart doesn’t explicitly disclose wherein: the network is an automotive Ethernet network in a vehicle; and performing the action associated with the rule with respect to the packet includes transmitting the packet to another device in the vehicle via the automotive Ethernet network.
However, Atad discloses the network is an automotive Ethernet network in a vehicle; and performing the action associated with the rule with respect to the packet includes transmitting the packet to another device in the vehicle via the automotive Ethernet network (See Parag. [0048]; a security layer inside an in-vehicle Ethernet network. In some embodiments, Ethernet packets may be passed through a set of security filters, and these filters may be implemented using an Ethernet switch's ternary content-addressable memory (TCAM) table or a TCAM table in a Gateway. As known in the art, a TCAM is a specialized type of high-speed memory that searches its entire contents in a single clock cycle. See Parag. [0065]; in deployments in which an embodiment can control or influence an Ethernet switch forwarding decisions an embodiment may cause the switch to drop or discard anomalous packets by, for example, including rules or signatures in a TCAM included in the switch).
It would be obvious to one of ordinary skill in the art at the time before the effective filling date of the claimed invention to modify the teachings of Katzri in view of Bosshart, to include the network is an automotive Ethernet network in a vehicle; and performing the action associated with the rule with respect to the packet includes transmitting the packet to another device in the vehicle via the automotive Ethernet network, as taught by Atad. This would be convenient to enable protecting an in-vehicle network from cyber-attacks (Atad, Parag. [0002]).
Claim 20 is taught by Katzri in view of Bosshart and Atad as described for claim 10.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Zifroni et al. (Pub. No. US 2019/0220401) – Related art in the area of a search system architecture for an electronic device, such as a network device, that performs lookup operations, (Abstract; Aspects of the disclosure provide a network device. The network device includes a search engine, a ternary content addressable memory (TCAM) cache engine, a search key generation unit and an output controller. The search engine stores a lookup table of entries for rules of packet processing, and searches the lookup table in response to packets received from a network interface of the network device. The TCAM cache engine caches a subset of the entries in the lookup table based on hit statistics of the entries. The search key generation unit generates a search key based on a received packet and provides the search key to the search engine and to the TCAM cache engine. The output controller outputs a search result from the TCAM cache engine when the TCAM cache engine has a matching entry to the search key).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ABDELBASST TALIOUA whose telephone number is (571)272-4061. The examiner can normally be reached on Monday-Thursday 7:30 am - 5:30 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Oscar Louie can be reached on 571-270-1684. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see https://ppair-my.uspto.gov/pair/PrivatePair. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Abdelbasst Talioua/Examiner, Art Unit 2445