Ex Parte Hughes et al

Board of Patent Appeals and Interferences

Jul 11, 2012

10769941 (B.P.A.I. Jul. 11, 2012)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
10/769,941 02/02/2004 Martin W. Hughes 112025-0536 9590
24267 7590 07/11/2012
CESARI AND MCKENNA, LLP
88 BLACK FALCON AVENUE
BOSTON, MA 02210
EXAMINER
SAEED, USMAAN
ART UNIT PAPER NUMBER
2166
MAIL DATE DELIVERY MODE
07/11/2012 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________________

Ex parte MARTIN W. HUGHES, WILLIAM R. LEE, TREVOR GARNER,
and DENNIS BRIDDELL
____________________

Appeal 2010-003489
Application 10/769,941
Technology Center 2100
____________________

Before THU A. DANG, CARL W. WHITEHEAD, JR.,
and ANDREW J. DILLON, Administrative Patent Judges.

DANG, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2010-003489
Application 10/769,941

2
I. STATEMENT OF THE CASE
Appellants appeal under 35 U.S.C. § 134(a) from a Final Rejection of
claims 1-35. We have jurisdiction under 35 U.S.C. § 6(b).
We affirm.

A. INVENTION
Appellants’ invention is directed to a system and a method for
searching a hash table including a predetermined set of signature
information that is hashed to generate a hash-table index which is associated
with a corresponding linked list; wherein, each of the linked list entries are
partitioned into different groups and only a selected group of entries in the
indexed list is searched (Abstract).

B. ILLUSTRATIVE CLAIM
Claim 1 is exemplary:
1. A method for efficiently searching a hash table
configured to store at least one list containing one or more list
entries to locate signature information, the method comprising:

partitioning the one or more list entries into first and
second groups of list entries, wherein a first list entry is not
associated with either the first group or the second group;

arranging list entries in the first and second groups on
opposite sides of the first list entry within a list;

selecting either the first group or the second group within
the list based on the signature information;

searching list entries in the selected first or second group
within the list until a matching list entry is found containing the
signature information or the end of the list is reached; and
Appeal 2010-003489
Application 10/769,941

3
providing the matched list entry.

C. REJECTIONS
The prior art relied upon by the Examiner in rejecting the claims on
appeal is:
Wong US 6,389,419 Bl May 14, 2002
Yu US 2003/0061213 Al Mar. 27, 2003
Dietz US 6,651,099 Bl Nov. 18, 2003
Waldspurger US 6,789,156 Bl Sep. 07, 2004
(filed Jul. 24, 2001)

Claims 1-3, 6, and 15-26 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Yu in view of Wong.
Claims 9, 10, and 13 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Wong in view of Yu.
Claims 4, 5, 7, and 8 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Yu in view of Wong and Dietz.
Claims 11, 12, and 14 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Wong in view of Yu and Dietz.
Claims 27, 29-32, 34, and 35 stand rejected under 35 U.S.C. § 103(a)
as being unpatentable over Rochberger in view of Wong.
Claims 28 and 33 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Rochberger in view of Wong and Waldspurger.

II. ISSUES
The main issues before us are whether the Examiner has erred in
determining that
1. the combination of Yu and Wong teaches or would have suggested
“arranging list entries in the first and second groups on opposite sides of the
Appeal 2010-003489
Application 10/769,941

4
first list entry within a list,” “selecting either the first group or the second
group within the list based on the signature information,” and “searching list
entries in the selected first or second group within the list” (claim 1,
emphasis added);
2. the combination of Wong and Yu teaches or would have suggested
“generating a direction value” and “searching list entries, beginning with
the first list entry, in a logical direction within the list determined by the
value of the generated direction value” (claim 9, emphasis added);
3. the combination of Rochberger and Wong teaches or would have
suggested “the pointer pointing to a first linked list entry of the linked list, a
first group of linked list entries arranged to a first side of the first linked list
entry in the linked list, a second group of linked list entries arranged to a
second side of the first linked list entry in the linked list” and “selecting
either the first group of linked list entries or the second group of linked list
entries in response to one or more predetermined bits of the index, and
searching fields of linked list entries of only the selected group for the
signature information, and if a particular linked list entry is found that
contains the signature information, providing the particular linked list entry”
(claim 27, emphasis added); and
4. the combination of Rochberger, Wong, and Waldspurger teaches
or would have suggested “the linked list entries of the first group of linked
list entries are unsorted and the linked list entries of the second group of
linked list entries are unsorted” (claim 28, emphasis added).

Appeal 2010-003489
Application 10/769,941

5
III. FINDINGS OF FACT
The following Findings of Fact (FF) are shown by a preponderance of
the evidence.
Rochberger
1. Rochberger discloses Radix search trees which do not store
keys in the tree nodes but rather store the keys in external nodes of the tree.
Thus, there are two types of nodes: (1) nodes which contain links to other
nodes and (2) nodes which comprise keys and no links (col. 6, ll. 46-47).
2. A Practical Algorithm To Retrieve Information Coded In
Alphanumeric search algorithm, better known as the Patricia search trie
method; wherein, a single node 12 comprises an index14, a left pointer 16 to
address C and a right pointer 18 to address B (Fig. 1; col 7, ll. 36-38).
Yu
3. Yu discloses a hash table having a partition that is based on a
single attribute A and a value v that defines the splitting position; wherein,
the hash table is created which maps the record ids of those records that
satisfy A=v to the left child node and maps the rids of those records that do
not satisfy A=v to the right child node (¶ [0080]).
Wong
4. Wong discloses a connection finding processor is configured to
hash a packet identifier to obtain a packet hash and to determine a matching
entry in the bidirectional hash table that corresponds to the packet hash
(Abstract). A direction value/flag of a packet is used to signify the direction
(inbound or outbound) of the packet (Fig. 8).
5. A hash function is used to generate an index for pointing to the
hash table (Fig. 2B, step 224).
Appeal 2010-003489
Application 10/769,941

6
6. A process for searching for a connection object when a packet
is received includes hashing the packet source IP address and checking the
hash list for a matching IP address within the list (Fig. 2C, steps 240-244).
If the source IP address hash is found, then in step 246, it is determined that
the packet is an inbound packet (Fig. 2C, step 246).
Waldspurger
7. Waldspurger discloses sorted and unsorted linked lists (col. 21,
ll. 23-25).
Dictionary of Algorithms and Data Structures
8. Linked list (data structure) is a list implemented by each item
having a link to the next item (Paul E. Black, ed., U.S. National Institute of
Standards and Technology, © 2003).

IV. ANALYSIS
Claims 1-3, 6, and 15-26
Appellants contend that “[d]ivision of a single list into two separate
lists [as disclosed in Yu] may not fairly be interpreted as ‘arranging list
entries in the first and second groups on opposite sides of the first list entry
within a list’” (App. Br. 22) and “Wong does not suggest ‘searching list
entries in the selected first or second group within the list’” (id.).
However, the Examiner finds that Yu “teach[es] splitting/arranging
list entries/attribute list into two lists, a list on either right or left based on
attribute A which [the] [E]xaminer interprets as first entry” (Ans. 29). The
Examiner notes that “the hash as signature information … is being used to
determine either the first group or the second group should be selected” (id.).
Appeal 2010-003489
Application 10/769,941

7
We give the claim its broadest reasonable interpretation consistent
with the Specification. See In re Morris, 127 F.3d 1048, 1054 (Fed. Cir.
1997). However, we will not read limitations from the Specification into the
claims. In re Van Geuns, 988 F.2d 1181, 1184 (Fed. Cir. 1993).
Claim 1 does not place any limitation on what “signature information”
means, includes, or represents. Thus, we give “selecting either the first
group or the second group within the list based on the signature information”
its broadest reasonable interpretation as data, as consistent with the
Specification and as specifically defined in claim 1.
Yu discloses a hash table having a partition that is based on a single
attribute A and a value v that defines the splitting position; wherein, those
records that satisfy A=v are mapped to the left child node and those recodes
that do not are mapped to the right child node (FF 3). We find that
partitioning of the hash table comprises grouping records into two groups:
one in the left child node and one in the right child node. That is, we find
that “arranging list entries in the first and second groups on opposite sides of
the first list entry within a list” and “selecting either the first group or the
second group within the list based on the signature information” (claim 1)
read on Yu’s hash table partitioning.
In addition, Wong discloses a connection finding processor is
configured to hash a packet identifier to obtain a packet hash and to
determine a matching entry in the bidirectional hash table that corresponds
to the packet hash (FF 4). A process for searching for a connection object is
disclosed; wherein, the list is searched for a matching packet source IP
address (FF 6). We find that the determination of a matching entry in the
bidirectional hash table comprises searching the list entries. Therefore, we
Appeal 2010-003489
Application 10/769,941

8
find that “searching list entries” (claim 1) reads on Wong’s bidirectional
hash table search.
Accordingly, we find that Appellants have not shown that the
Examiner erred in rejecting claim 1 under 35 U.S.C. § 103(a) over Yu in
view of Wong. Similarly, independent claims 15, 23, and 24 having the
similar claim language and claims 2, 3, 6, 16-22, 25, and 26 (depending
from claims 1and 15), which have been argued separately, fall with claim 1.

Claims 9, 10, and 13
Appellants contend that “Wong lacks a direction value and makes no
mention of directed searching” because “Wong’s ‘inbound flag’ is not akin
to a ‘direction value’” ( App. Br. 23) and “Wong’s ‘bidirectional hash’ has
little to do with what the Applicant claims” (App. Br. 24).
However, the Examiner finds that Wong discloses a “direction
value/flag of a packet to determine the direction (inbound or outbound) of
the packet” (Ans. 32). The “Examiner interprets the incoming hash as a
logical direction and outgoing hash as another logical direction and they are
both contained within the hash list in the bidirectional hash table” (id.).
Claim 9 does not place any limitation on what “direction value”
means, includes, or represents, other than that it determines the logical
direction of the search of the list entries. Thus, we give “direction value” its
broadest reasonable interpretation as data that is indicative of motion, as
consistent with the Specification and as specifically defined in claim 9.
As noted supra, Wong discloses a bidirectional hash table (FF 4). A
direction value/flag of a packet is used to signify the direction (inbound or
outbound) of the packet (id.). We find that the direction value/flag
Appeal 2010-003489
Application 10/769,941

9
comprises a direction value. That is, we find that “generating a direction
value” (claim 9) reads on Wong’s direction value/flag for a packet.
In addition, as noted supra, Yu discloses a hash table that is
partitioned into two groups by searching the table and grouping records
based upon the attribute value (FF 3). We find that the searching of the table
comprises searching the list entries of the linked lists within the table.
Particularly, we find that “searching list entries, beginning with the first list
entry” (claim 9) reads on partitioning of Yu’s hash table.
In view of our claim construction above, we find that the combination
of Wong and Yu at least suggests providing “searching list entries,
beginning with the first list entry, in a logical direction within the list
determined by the value of the generated direction value” (claim 9), as
specifically required by claim 9.
Accordingly, we find that Appellants have not shown that the
Examiner erred in rejecting claim 9 under 35 U.S.C. § 103(a) over Wong in
view of Yu. Similarly, claims 10 and 13 (depending from claim 9), which
have been argued separately, fall with claim 9.

Claims 27, 29-32, 34, and 35
As to independent claim 27, Appellants contend that “Rochberger
makes no mention of pointing from a hash entry to a first linked list entry of
a linked list;” rather, Rochberger “suggests that one should use an entirely
different type of data structure than a linked list, namely that one should use
a tree data structure” (App. Br. 16-17). Appellants assert that “[a] linked list
may not fairly be equated to a tree” because “a tree is typically a branched,
hierarchical structure, a linked list is generally linear or circular structure”
Appeal 2010-003489
Application 10/769,941

10
(App. Br. 17). Appellants argue that “Wong teaches away from what the
Applicant claims” because “Wong discusses several configurations in which
a pointer is directed to [an] entry at one end of a list, not to a linked list entry
in the middle of a list” (App. Br. 19).
However, the Examiner finds that Rochberger teaches the claimed
linked list and that he interprets “a pointer pointing to the left … as a first
group of list entries and pointer pointing to the right as a second group of list
entries[;] and they are both being arranged on either side of the root node”
(Ans. 35). The Examiner finds further that Rochberger teaches “use … of
the index bit to determine which group should be selected” (Ans. 36).
Claim 27 does not place any limitation on what “hash table” and
“linked list” mean, include, or represent. The Specification is silent as to a
definition for either and merely discloses that a “hash table is typically
organized as a table of linked lists, where each list may be indexed by the
result of applying a conventional hash function to ‘signature’ information
(data)” (Spec. 3-4). The Dictionary of Algorithms and Data Structures
discloses that a linked list (data structure) is a list implemented by each item
having a link to the next item (FF 8). Thus, we give “hash table” its
broadest reasonable interpretation as a table that is indexed using data
associated with a hash function, as consistent with the Specification and as
specifically defined in claim 27. We also give “linked list” its broadest
reasonable interpretation as a list of items where each item has a link to the
next item, as consistent with the Specification and as specifically defined in
claim 27.
Rochberger discloses both Radix search trees and Patricia search
trees; wherein, keys are either stored in the node or in an external node (FF 1
App
App

and 2
node
singl
In pa
addr
does
poin
that
poin
the r
linke
to a
linke
linke
eal 2010-0
lication 10
). Both tr
s or other
Rochbe
Figure 1
e node (co

rticular, th
ess C and
not link to
ter 16 entr
the addres
ter 16 and
ight pointe
d list entry
first side o
d list entri
d list” (cla
03489
/769,941
ee types c
portions w
rger’s Figu
depicts a
l. 9, ll. 46
e single n
a right poi
another l
y. We ado
s C represe
that the ad
r 18. Tha
of the lin
f the first l
es arrange
im 27) rea
ontain nod
ithin the s
re 1 is rep
prior art P
-48).
ode 12 com
nter 18 to
ist, we find
pt the Exa
nts the fir
dress B re
t is, we fin
ked list, a
inked list
d to a seco
ds on Roc
11
es (lists of
ame node
roduced b
atricia sear
prises an
address B
that the f
miner’s p
st group th
presents th
d that “the
first group
entry in th
nd side of
hberger’s
items) ha
(FF 1 and
elow:
ch trie tre
index14,
(FF 2). Si
irst linked
osition not
at is point
e second
pointer p
of linked
e linked li
the first l
Patricia se
ving links
2).

e having a
a left point
nce the in
list entry
ed supra,
ed to by th
group poin
ointing to
list entrie
st, a secon
inked list e
arch trie t
to other
root and a
er 16 to
dex 14
is the left
finding
e left
ted to by
a first
s arranged
d group of
ntry in the
ree.

Appeal 2010-003489
Application 10/769,941

12
Though Appellants also contend that “Wong teaches away from what
the Applicant claims” (App. Br. 19), our reviewing court has held that “‘[a]
reference may be said to teach away when a person of ordinary skill, upon
[examining] the reference, would be discouraged from following the path set
out in the reference, or would be led in a direction divergent from the path
that was taken by the applicant.’” Para-Ordnance Mfg., Inc. v. SGS
Importers Int’l., Inc., 73 F.3d 1085, 1090 (Fed. Cir. 1995) (quoting In re
Gurley, 27 F.3d 551, 553 (Fed. Cir. 1994)).
Appellants have identified no express support for a direction divergent
from the claimed invention since the Examiner relies upon Rochberger to
teach “the pointer” (Ans. 22) and Wong to teach “generat[ing] an index”
from “hashing signature information” as cited in claim 27 (Ans. 24).
Accordingly, we find that Appellants have not shown that the
Examiner erred in rejecting claim 27 under 35 U.S.C. § 103(a) over
Rochberger in view of Wong. Similarly, independent claim 32 having the
similar claim language and claims 29-31, 34, and 35 (depending from claims
27 and 32), which have been argued separately, fall with claim 27.

Claims 28 and 33
Appellants contend that “[t]he combination of Rochberger, Wong and
Waldspurger does not teach or suggest the Applicant’s claimed ‘the linked
list entries of the first group of linked list entries are unsorted and the linked
list entries of the second group of linked list entries are unsorted’” (App. Br.
20). Appellants argue that “Rochberger makes clear that his techniques rely
on this sorting” and therefore “[a]ny attempt to replace Rochberger’s trees
Appeal 2010-003489
Application 10/769,941

13
with unsorted data structures would change the fundamental operation of
Rochberger, likely making it unsuitable for its intended purpose” (id.).
However, the Examiner finds that Waldspurger discloses that an
“alternative data structure would be the class of lists including linked lists
(sorted or unsorted), skip lists, or even simple arrays” (Ans. 27).
As noted supra, Rochberger discloses a first and a second group of list
entries that are linked (FF 1 and 2). We find these groups of list entries
comprise a first and a second group of list entries that are linked. That is, we
find that “the linked list entries of the first group of linked list entries … and
the linked list entries of the second group of linked list entries” (claim 28)
reads on Rochberger’s Patricia search trie tree
In addition, Waldspurger discloses sorted and unsorted linked lists (FF
7). We find that the unsorted linked lists comprise unsorted link list entries.
Accordingly, we find that “group of linked list entries are unsorted” (claim
28) reads on Waldspurger’s linked lists (unsorted).
Therefore, we find that the combination of Rochberger, Wong, and
Waldspurger at least suggests providing “the linked list entries of the first
group of linked list entries are unsorted and the linked list entries of the
second group of linked list entries are unsorted,” as specifically required by
claim 28.
Though Appellants also contend that “replac[ing] Rochberger’s trees
with unsorted data structures would change the fundamental operation of
Rochberger, likely making it unsuitable for its intended purpose” (App. Br.
20), the recited portion of Rochberger does not make clear that its
“techniques rely on sorting,” as Appellants claim (id.).
Appeal 2010-003489
Application 10/769,941

14
Since Rochberger discloses linked lists having a first and second
group, we conclude that the combination of one known element
(Rochberger’s linked lists having groups) with another (Waldspurger’s
unsorted linked lists) would have yielded predictable results to one of
ordinary skill in the art at the time of the invention. That is, we find that
linked lists as taught by Rochberger in addition to Waldspurger’s unsorted
linked lists are no more than a simple arrangement of old elements, with
each performing the same function it had been known to perform, yielding
no more than one would expect from such an arrangement. See KSR Int'l
Co. v. Teleflex Inc., 550 U.S. U.S. 398, 417 (2007).
Accordingly, we find that Appellants have not shown that the
Examiner erred in rejecting claim 28 under 35 U.S.C. § 103(a) over
Rochberger in view of Wong and Waldspurger. Similarly, claim 33
(depending from claim 32), having similar claim language, falls with claim
28.

Claims 4, 5, 7, 8, 11, 12, and 14
Appellants argue that claims 4, 5, 7, and 8 are patentable over the
cited prior art for the same reasons asserted with respect to claim 1 (App. Br.
24) and claims 11, 12, and 14 are patentable over the cited prior art for the
same reasons asserted with respect to claim 9 (App. Br. 25).
As noted supra, however, we find that the combination of Yu and
Wong at least suggests all the features of claims 1 and 9. We therefore
affirm the Examiner’s rejection of claims 4, 5, 7, 8, 11, 12, and 14 under 35
U.S.C. § 103 for the same reasons expressed with respect to respective
parent claims 1 and 9, supra.
Appeal 2010-003489
Application 10/769,941

15

V. CONCLUSION AND DECISION
The Examiner’s rejection of claims 1-35 under 35 U.S.C. § 103(a) is
affirmed.
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

peb