DETAILED ACTION
Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
2. 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 (i.e., changing from AIA to pre-AIA ) 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.
3. 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.
4. The factual inquiries 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.
5. This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
6. Claims 1, 2, 6, 8, 10, 11 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Applicant’s Admitted Prior Art ( hereinafter “AAPA”) in view of Xu (CN 114844832 B).
Regarding claims 1 and 10, AAPA teaches a method for allocating entries of a summarization table to ranges of packet field values in entries of at least one hardware table of a network device (¶ [0003]-¶ [0005], ¶ [0006] In order to maximize the number of rules that can be stored in the hardware tables, a number of existing network devices support the use of port summarization tables. Where it is implicit that the network device comprises a processor), the method comprising: examining a plurality of rules to be stored in at least one hardware table, at least one of the rules specifying one or more corresponding packet field value ranges which are used to match packets as those packets are forwarded or routed by a network device (¶ [0004], a rule may include fields that specify a range of source ports and a range of destination ports, where the rule applies to packets that have source and destination ports that fall within the specified ranges. -¶ [0005]); for each packet field value range, determining a corresponding cost reduction that would result from replacing the packet field value range with a first entry in a summarization table (¶ [0006], A port summarization table has multiple entries, each of which summarizes a range of ports. A result-bitmap register associated with the port summarization table has a bit corresponding to each entry in the port summarization table, where the bit is set if a packet has a port that falls within the range specified in the table entry. A single bit corresponding to a single entry in the port summarization table can therefore represent and effectively replace a range of values in a rule. ¶ [0007], where the rule specifies ranges of three source ports and four destination ports, replacement of the range of three source ports by a single entry in the port summarization table would reduce the required number of entries for the rule in the hardware table from (3×4)=12 to (1×4)=4. The use of the port summarization table therefore significantly reduces the number of entries in the hardware table which are required to implement the rule); and assigning a first packet field value range to a first entry in the summarization table (¶ [0006] and ¶ [0007]).
AAPA does not explicitly teach identifying a first packet field value range corresponding to a greatest cost reduction.
Xu teaches identifying a first field value with most occurrence times and writing the field value in the combined table (Page 3: Selecting the field with the most occurrence times from the first software forwarding table item. Page 11: the preset key field may be the first software forwarding entry and the field with the largest number of occurrences in its associated entry, so that most of the associated software forwarding entries will include the key field, so In this way, most of the table items do not need to inquire other table items, and the table items are directly written in the combined table items based on the key fields included in the table items so as to reduce the table search times).
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, to identify a first packet field value range corresponding to a greatest cost reduction and assign the first packet field value range to a first entry in the summarization table to the maximize the entry reduction in the hardware table.
Regarding claim 17, AAPA teaches a computer device comprising one or more processors performing a method (¶ [0003]-¶ [0005], ¶ [0006]. Where it is implicit that the network device comprises a processor) comprising: examining a plurality of rules to be stored in at least one hardware table, at least one of the rules specifying one or more corresponding packet field value ranges which are used to match packets as those packets are forwarded or routed by a network device (¶ [0004], a rule may include fields that specify a range of source ports and a range of destination ports, where the rule applies to packets that have source and destination ports that fall within the specified ranges. -¶ [0005]); for each packet field value range, determining a corresponding cost reduction that would result from replacing the packet field value range with a first entry in a summarization table (¶ [0006], A port summarization table has multiple entries, each of which summarizes a range of ports. A result-bitmap register associated with the port summarization table has a bit corresponding to each entry in the port summarization table, where the bit is set if a packet has a port that falls within the range specified in the table entry. A single bit corresponding to a single entry in the port summarization table can therefore represent and effectively replace a range of values in a rule. ¶ [0007], where the rule specifies ranges of three source ports and four destination ports, replacement of the range of three source ports by a single entry in the port summarization table would reduce the required number of entries for the rule in the hardware table from (3×4)=12 to (1×4)=4. The use of the port summarization table therefore significantly reduces the number of entries in the hardware table which are required to implement the rule); and assigning the first packet field value range to a first entry in the summarization table (¶ [0006] and ¶ [0007]).
AAPA does not explicitly teach a computer program product comprising a non-transitory computer-readable medium storing instructions executable by one or more processors to identifying a first packet field value range corresponding to a greatest cost reduction.
Xu teaches a computer program product comprising a non-transitory computer-readable medium storing instructions executable by one or more processors (Page 15: “embodiments of the present disclosure include a computer program product comprising a computer program tangibly embodied on its readable medium,)identifying a first packet field value range corresponding to a greatest cost reduction” ) to identify a first field value with most occurrence times and writing the field value in the combine table (Page 3: Selecting the field with the most occurrence times from the first software forwarding table item. Page 11: the preset key field may be the first software forwarding entry and the field with the largest number of occurrences in its associated entry, so that most of the associated software forwarding entries will include the key field, so In this way, most of the table items do not need to inquire other table items, and the table items are directly written in the combined table items based on the key fields included in the table items so as to reduce the table search times).
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, implement a computer program product comprising a non-transitory computer-readable medium storing instructions executable by one or more processors to perform the method of AAPA and to identify a first packet field value range corresponding to a greatest cost reduction and assign the first packet field value range to a first entry in the summarization table to the maximize the entry reduction in the hardware table.
Regarding claims 2 and 11, AAPA in view of Xu teaches the method of claim 1, wherein the cost reduction comprises a difference between: a number of hardware table entries required to store the plurality of rules prior to assigning the first packet field value range to the first entry in the summarization table; and a number of hardware table entries that would be required to store the plurality of rules after assigning the first packet field value range to the first entry in the summarization table (AAPA: ¶ [0007], where the rule specifies ranges of three source ports and four destination ports, replacement of the range of three source ports by a single entry in the port summarization table would reduce the required number of entries for the rule in the hardware table from (3×4)=12 to (1×4)=4).
Regarding claim 6, AAPA in view of Xu teaches the method of claim 1, wherein the plurality of rules comprises a plurality of packet classification rules for classifying ingress and egress packets received by the network device (AAPA: ¶ [0002]-¶ [0004]).
Regarding claim 8, AAPA in view of Xu teaches the method of claim 1, wherein the plurality of rules define L4 source port ranges and L4 destination port ranges for classification of packets (AAPA: ¶ [0004]- ¶ [0006]).
7. Claims 3, 12 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over AAPA in view of Xu as applied to claim 1 above, and further in view of Kramer et al. (US 2007/0283144 A1, hereinafter “Kramer”).
Regarding claims 3, 12 and 18, AAPA in view of Xu teaches the method of claim 1.
AAPA does not explicitly teach further comprising: after assigning the first packet field value range to the first entry in the summarization table, iteratively performing for each of one or more additional entries in the summarization table: examining the plurality of rules, determining the cost reduction for each unallocated packet field value range, identifying a corresponding additional packet field value range corresponding to a greatest cost reduction, and assigning the corresponding additional packet field value range to the corresponding entry in the summarization table.
However, Kramer teaches an iterative table construction mechanism to reduce or eliminate duplicate entries within the table ( ¶ [0027], ¶ [0033]).
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, to utilize an iterative table construction mechanism (i.e., after assigning the first packet field value range to the first entry in the summarization table, iteratively perform for each of one or more additional entries in the summarization table: examining the plurality of rules, determine the cost reduction for each unallocated packet field value range, identify a corresponding additional packet field value range corresponding to a greatest cost reduction, and assign the corresponding additional packet field value range to the corresponding entry in the summarization table) in the system of AAPA in view of Xu to further enhance memory/storage utilization by significantly reducing the number of entries in the hardware table.
8. Claims 7, 9, 15 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over AAPA in view of Xu as applied to claim 6 above, and further in view of Duda (US 2017/0346790 A1).
Regarding claim 7, AAPA in view of Xu teaches the method of claim 6.
AAPA does not explicitly teach wherein the plurality of rules comprises all packet classification rules to be loaded on a forwarding ASIC of the network device.
However, it is well known in the art to load the packet classification rules on a forwarding ASIC of the network device, as evidenced by ¶ [0003] of Duda.
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, to load all packet classification rules on a forwarding ASIC of the network device in the system of AAPA in view of Xu to improve industrial applicability.
Regarding claims 9 and 16, AAPA in view of Xu teaches the method of claim 1.
AAPA does not explicitly teach wherein the at least one hardware table comprises a ternary content addressable memory (TCAM).
However, it is well known in the art to utilize TCAM hardware table, as evidenced by ¶ [0003] of Duda.
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, to utilize a TCAM in the system of AAPA in view of Xu to improve industrial applicability.
Regarding claim 15, AAPA in view of Xu teaches the optimizing rules compiler of claim 10, wherein the plurality of rules comprises a plurality of packet classification rules for classifying ingress and egress packets received by the network device (AAPA: ¶ [0002]-¶ [0004]).
AAPA does not explicitly teach wherein the plurality of rules comprises all packet classification rules to be loaded on a forwarding ASIC of the network device.
However, it is well known in the art that to load the packet classification rules on a forwarding ASIC of the network device, as evidenced by ¶ [0003] of Duda.
Thus, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the invention, to load all packet classification rules on a forwarding ASIC of the network device in the system of AAPA in view of Xu to improve industrial applicability.
Allowable Subject Matter
9. Claim 4, 5, 13, 14, 19 and 20 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
10. The following is a statement of reasons for the indication of allowable subject matter:
Regarding claims 4, 13 and 19, prior art of record fails to teach or fairly suggest “wherein for each remaining packet field value range in the plurality of rules, the cost reduction corresponding to the packet field value range that would result from replacing the packet field value range with a second entry in the summarization table is determined based on previously assigned packet field value ranges being replaced by corresponding entries in the summarization table” in combination of limitations specified in the base claim and the intervening claim(s).
Regarding claims 5, 14 and 20, prior art of record fails to teach or fairly suggest “wherein determining the cost reduction corresponding to each packet field value range comprises: for a rule that contains the packet field value range: determining a factor for each field in the rule, the factor comprising a number of possible values for the field, the packet field value range comprising two or more of the possible values; multiplying all of the factors for the rule to produce a first product; updating the factors to represent the packet field value range as a single possible value; multiplying all of the updated factors for the rule to produce a second product; and subtracting the second product from the first product to produce the cost reduction corresponding to the packet field value range” in combination of limitations specified in the base claim.
Conclusion
11. Any inquiry concerning this communication or earlier communications from the examiner should be directed to MANDISH RANDHAWA whose telephone number is (571)270-5650. The examiner can normally be reached Monday-Thursday (9 AM-7 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, Chirag Shah can be reached at 571-272-3144. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/MANDISH K RANDHAWA/Primary Examiner, Art Unit 2477
Prosecution Insights