Ex Parte BanksDownload PDFPatent Trial and Appeal BoardJan 28, 201411562011 (P.T.A.B. Jan. 28, 2014) Copy Citation UNITED STATES PATENT AND TRADEMARK OFFICE ____________________ BEFORE THE PATENT TRIAL AND APPEAL BOARD ____________________ Ex parte ANDREW DAVID BANKS ____________________ Appeal 2011-001733 Application 11/562,011 Technology Center 2100 ____________________ Before JEFFREY S. SMITH, JUSTIN BUSCH, and CATHERINE SHIANG, Administrative Patent Judges. BUSCH, Administrative Patent Judge. DECISION ON APPEAL Appeal 2011-001733 Application 11/562,011 2 Appellant appeals under 35 U.S.C. § 134(a) from a final rejection of claims 1-19. We have jurisdiction under 35 U.S.C. § 6(b). We AFFIRM. Introduction According to Appellant, the invention relates to a method and system for concurrent processing of list items by multiple control threads using a reference list and sub-lists. Abstract. STATEMENT OF THE CASE Exemplary Claim Claim 1, reproduced below, is illustrative of the claimed subject matter: 1. A method for concurrent processing of items in a sequential queue by multiple control threads, comprising: referencing items in a sequential queue by a sequence number; distributing the items across a plurality of sub-queues; locking the reference queue when allocating or retrieving a sequence number for an item; and locking a sub-queue when adding or removing an item from the sub-queue. References Harchol-Balter US 6,223,205 B1 Apr. 24, 2001 Appeal 2011-001733 Application 11/562,011 3 Nagendra Nagarajayya, “Technical Articles & Tips, An SMP-Based High- Performance, Multi-Threaded Server Architecture for Applications in the Softswitch/Call Processing Domain,” January 2001 (available at http://web.archive.org/web/20030614221315/http://developers.sun.com/ solaris/articles/smp.html (as archived Jun 14th 2003)) (hereinafter “Nagarajayya”). Rejection Claims 1-19 stand rejected under 35 U.S.C. §103(a) as being unpatentable over Nagarajayya and Harchol-Balter. Ans. 3-11. ANALYSIS Appellant argues the combination of Harchol-Balter and Nagarajayya does not teach “distributing the items across a plurality of sub-queues” or “locking a sub-queue when adding or removing an item from the sub- queue,” as recited in independent claims 1, 9, and 19. Br. 10-11. Appellant further argues the combination of Harchol-Balter and Nagarajayya does not teach: “searching all sub-queues for items with highest available sequence number in response to the item not being found in the sub-queue,” as recited in dependent claim 4; “distributing comprises applying a distribution algorithm based on the sequence number,” as recited in dependent claim 5; or “determining the sub-queue in which an item is held comprises using the distribution algorithm,” as recited in dependent claim 7. Br. 12-15. Therefore, the issues before us are whether the combination of Harchol- Balter and Nagarajayya teach or suggest the identified limitations in claims 1, 4, 5, 7, 9, and 19. Appeal 2011-001733 Application 11/562,011 4 Independent Claims 1, 9, and 19 Appellant argues Harchol-Balter is a distributed server system that distributes tasks among a plurality of processors, whereas the claim recites distributing items across a plurality of sub-queues. Br. 11. Appellant argues Harchol-Balter’s processors are not the same as the claimed sub-queue structure. Id. Appellant asserts the recited sub-queue structure allows assignment of items to sub-queues using a distribution algorithm, enabling a list item to be located, whereas Harchol-Balter’s distribution does not create a data structure or simplify locating tasks in a list. Id. Appellant concedes “Nagarajayya describes locking a queue to add or delete items in a multi- thread system,” but argues Nagarajayya does not suggest creating or locking sub-queues. Id. The Examiner finds “Nagarajayya suggests using multiple sub-queues and Harc[h]ol-Balter specifically discloses using sub-queues.” Ans. 11. The Examiner explains that Nagarajayya creates sub-queues for each of the threads so that the threads can lock and process their own sub-queue independently of the other threads’ sub-queues. Ans. 12. The Examiner further finds Harchol-Balter discloses sub-queue structures, in particular with respect to queuing tasks with small execution times in a Size Interval Task Assignment with Equal Load (SITA-E) distribution system. Ans. 12 (citing Harchol-Balter col. 7 l. 50 – col. 8 l. 14). The Examiner finds that, in addition to locking “resources in a multithreaded environment which could cause conflict if simultaneously accessed” being “the most basic and common of practice in the art,” Nagarajayya discloses locking. Ans. 13. Appeal 2011-001733 Application 11/562,011 5 Appellant’s arguments against the references individually, when the rejection is based on a combination, are not persuasive. We agree with the Examiner’s finding that Harchol-Balter’s embodiment using the SITA-E distribution includes a sub-queue for each of its threads. The Examiner finds Nagarajayya suggested using a sub-queue for each of its threads, but relies on the combination of the suggestion in Nagarajayya and the explicit disclosure of sub-queues in Harchol-Balter for teaching “distributing the items across a plurality of sub-queues,” as recited in independent claims 1, 9, and 19. Appellant’s argument that Nagarajayya does not teach locking sub- queues because it does not create sub-queues and Harchol-Balter “does not provide what Nagarajayya lacks” is similarly unpersuasive. Br. 11. The Examiner relies on the combination of Nagarajayya and Harchol-Balter to show that sub-queues are created and relies on Nagarajayya to teach that it was well-known to lock queues in order to avoid conflicts while accessing queued items. Appellant has not presented sufficient evidence to persuade us the Examiner erred. Therefore, we agree with the Examiner’s findings and conclusions and sustain the rejection of claims 1, 9, and 19 for the reasons discussed above. Dependent Claims 4, 5, and 7 Appellant presents separate substantive arguments for dependent claims 4, 5, and 7. The Examiner finds “searching all sub-queues for items with highest available sequence number in response to the item not being found in the sub-queue,” as recited in dependent claim 4, reads on simple error checking of a queue tail, which would have been known to a skilled artisan. Ans. 6. Appeal 2011-001733 Application 11/562,011 6 The Examiner further finds “it would have been obvious to search for the next item for processing (i.e. highest sequence number) in a queue when no further item is found in a processor's sub-queue in order to provide further load balancing.” Ans. 14. Appellant presents various arguments regarding sample embodiments and goals of Appellant’s inventions. In particular, Appellant asserts “[c]hecking for the highest available sequence number in response to the (expected head) item not being found is error recovery, not error checking.” Br. 12-13. Appellant also argues “[i]n the claimed invention, instead of stopping processing, all sub-queues are searched for the highest available sequence number item, which is the effective head item. The processing can then continue with this effective head.” Br. 13. We find Appellant’s arguments are not commensurate with the scope of the claim language. Claim 4 merely recites “searching all sub-queues to identify an item with highest available sequence number in response to the item not being found in the sub-queue.” The Examiner has provided findings as to why such a step would have been obvious to an ordinarily skilled artisan at the time of the invention in view of the combination of Nagarajayya and Harchol-Balter. Appellant has not provided sufficient evidence to persuade us the Examiner erred in finding that “searching all sub-queues for items with highest available sequence number in response to the item not being found in the sub-queue,” as recited in dependent claim 4, was beyond the level of ordinary skill in the art. Therefore, we sustain the rejection of claim 4. The Examiner finds Harchol-Balter discloses round-robin distribution of tasks/items, which the Examiner finds meets “distributing comprises Appeal 2011-001733 Application 11/562,011 7 applying a distribution algorithm based on the sequence number,” as recited in dependent claim 5 and “determining the sub-queue in which an item is held comprises using the distribution algorithm,” as recited in dependent claim 7 because it is “a distribution based solely on incoming sequence.” Ans. 15. The Examiner also finds every distribution algorithm, including those disclosed in Harchol-Balter (e.g., round-robin, SITA-E, and First- Come-First-Served), “use their own distribution algorithm to determine sub- queues the items belong to.” Ans. 16. Appellant argues the Specification teaches that “using a distribution algorithm based on the sequence number of an item to distribute the item to a sub-queue makes it easier to predict which sub-queue the item will be in.” Br. 14-15. Appellant further argues Harchol-Balter does not teach a distribution algorithm for assigning items to sub-queues based on sequence numbers. Id. Appellant’s arguments have not provided sufficient evidence to persuade us the Examiner erred in rejecting dependent claims 5 and 7. Therefore, we sustain the rejection of claims 5 and 7. Appellant has not presented separate, substantive argument for claims 2, 3, 6, 8, and 10-18, each of which ultimately depends from one of claims 1 and 9. Therefore, for the same reasons as discussed above, we sustain the rejection of claims 2, 3, 6, 8, and 10-18. DECISION For the above reasons, the Examiner’s rejection of claims 1-19 is affirmed. Appeal 2011-001733 Application 11/562,011 8 No time period for taking any subsequent action in connection with this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv). AFFIRMED tj Copy with citationCopy as parenthetical citation