Ex Parte Banks

Patent Trial and Appeal Board

Jan 28, 2014

11562011 (P.T.A.B. Jan. 28, 2014)

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