Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 186

NOTICE by Google Inc. re #133 MOTION to Compel Plaintiff to Comply with Patent Rule 3-1 and to Extend the Time to Serve Invalidity Contentions [Notice of Supplemental Facts] (Attachments: #1 Exhibit 1, #2 Exhibit 2, #3 Exhibit 3, #4 Exhibit 4, #5 Exhibit 5)(Jones, Michael)

Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Doc. 186 Att. 4

Exhibit 4

Dockets.Justia.com

BEDROCK COMPUTER TECHS., LLC V. SOFTLAYER TECH. SOLUTIONS, LLC, ET. AL PLAINTIFF'S P.R. 3-1 INFRINGEMENT CONTENTIONS1 Claim Language 1. An information storage and retrieval system, the system comprising: Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Bedrock Computer Technologies LLC ("Bedrock") does not express a position at this time as to whether the preamble of this claim limits the claim's scope. Nevertheless, Bedrock identifies below aspects of the Accused Instrumentalities that correspond to the claim preamble. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted for information storage and retrieval. In the event this preamble is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this preamble and the aforementioned features of the The contentions contained in this chart are based on functionality observable through the open source versions of Linux that are publicly available. All of the limitations of the asserted claims of the '120 patent include features that relate to software of the Accused Instrumentalities. The actual source code of Linux that is installed on Google servers and other device(s) is not publicly available and has not yet been produced for inspection. Bedrock reserves the right to supplement or modify these contentions once Google has produced this code and Bedrock has completed its review of the source code. Bedrock's identification of specific routines is not intended to identify all of the code necessary to satisfy the claim limitation at issue. Other source and/or object code components, such as routines, functions, methods, macros, classes, data structures, libraries etc. may be necessary. Furthermore, these identified code components may be called by or call other code components. Also, the code components identified are normally the first or the most relevant in a series of code components and are intended to reference the entire function path. Bedrock reserves its right to provide additional detail in its expert report according to the schedule set by the Court. Page 1 of 37
Dallas 296148v1 1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring. Within Linux kernel version 2.6.26, the data structure rt_hash_table in module /net/ipv4/route.c3 anchors one or more linked list(s) to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring. In this way, computer equipment configured with or utilizing software based on 2.6.26 includes a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring. The following code excerpts from the files /net/ipv4/route.c and /include/net/route.h show the C language definition for the data structure rt_hash_table and the rtable struct definition used by rt_hash_table:

(a)2 a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring,

2 3

While the limitations are not lettered in the actual claims of the patent, Bedrock provides them here for ease of reference.

The path names of the cited source code is provided for the defendants' convenience. If any version or customization of Linux kernel version 2.6.26 deviates from the path names that are cited in these charts, such deviations are insignificant because it is the routines, functions, methods, macros, classes, data structures, etc., as embodied on servers and other devices, that infringe. Page 2 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 struct rt_hash_bucket { struct rtable *chain; }; **** static struct rt_hash_bucket **** struct rtable { union { struct dst_entry } u; /* Cache lookup keys */ struct flowi fl; struct in_device int unsigned __u16 __be32 __be32 *idev; rt_genid; rt_flags; rt_type; rt_dst; /* Path destination rt_src; /* Path source */ */ Page 3 of 37 dst; *rt_hash_table __read_mostly;

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 int rt_iif; /* Info on neighbour */ __be32 rt_gateway; /* Miscellaneous cached information */ __be32 rt_spec_dst; /* RFC1122 specific destination */ struct inet_peer *peer; /* long-living peer info */ }; Source: Linux kernel source code files /net/ipv4/route.c and /include/net/route.h In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(b)

a record search means utilizing a search key to access the linked list,

When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include a record search means utilizing a search key to access the linked list or its equivalent. Specifically, code contained within functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c calls functions rt_hash and rt_intern_hash. In this way, computer Page 4 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 equipment configured with or utilizing software based on Linux kernel version 2.6.26 includes a record search means utilizing a search key to access the linked list or its equivalent. In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(c)

the record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed, and

When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include a record search means, the record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed or its equivalent. Specifically, code contained within function rt_intern_hash, as invoked by functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c, comprises record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed or its equivalent. The following code excerpt from the rt_intern_hash function is an example of a record search means which includes a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed or its Page 5 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 equivalent: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); while ((rth = *rthp) != NULL) {

if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) { **** if (!atomic_read(&rth->u.dst.__refcnt)) { u32 score = rt_score(rth); if (score <= min_score) { cand = rth; candp = rthp; min_score = score; } } **** chain_length++; rthp = &rth->u.dst.rt_next; } Page 6 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 **** if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c The following code excerpt from the rt_intern_hash function is a second example of a record search means which includes a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed or its equivalent: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); while ((rth = *rthp) != NULL) {

Page 7 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26

if (rth->rt_genid != atomic_read(&rt_genid)) { *rthp = rth->u.dst.rt_next; rt_free(rth); continue; } if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) { **** chain_length++; rthp = &rth->u.dst.rt_next; } **** Source: Linux kernel source code file /net/ipv4/route.c Note that the record(s) identified as expired upon traversal of the linked list is not necessarily the record that rt_intern_hash was called to find. In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Page 8 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list or its equivalent. Specifically, the functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c. include means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list or its equivalent. The following code excerpt is one example of the rt_hash and rt_intern_hash functions being called by the function ip_route_input_mc:
hash = rt_hash(daddr, saddr, dev->ifindex); return rt_intern_hash(hash, rth, &skb->rtable);

(d)

means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list.

Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Page 9 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent. Specifically, code contained within function rt_intern_hash, in module /net/ipv4/route.c, dynamically executes based upon comparison with variable ip_rt_gc_elasticity. In this way, computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 includes means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent. The following code excerpt from the rt_intern_hash functions is an example of the variable ip_rt_gc_elasticity being used for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows Page 10 of 37

2.

The information storage and retrieval system according to claim 1 further including means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records.

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

3.

A method for storing and retrieving information records using a linked list to store and provide access to the records, at least some of the records automatically expiring, the method comprising the steps of:

Bedrock does not express a position at this time as to whether the preamble of this claim limits the claim's scope. Nevertheless, Bedrock identifies below aspects of the Accused Instrumentalities that correspond to the claim preamble. When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method for storing and retrieving information records that uses a linked list to store and provide access to the records, where at least some of the records are automatically expiring. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to store and retrieve information records using a linked list to store and provide access to the records, where at least some of the records are automatically Page 11 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 expiring. In the event this preamble is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this preamble and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(a)

accessing the linked list of records,

When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of accessing the linked list of records. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to access a linked list of records. Specifically, the data structure rt_hash_table in module /net/ipv4/route.c is used to access the linked list of records. Additionally, code contained within the function rt_intern_hash in module /net/ipv4/route.c is also used to access the linked list of records. The following code excerpt from the rt_intern_hash function is an example of accessing the linked list of records: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); while ((rth = *rthp) != NULL) { Page 12 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 **** chain_length++; rthp = &rth->u.dst.rt_next; } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(b)

identifying at least some of the automatically expired ones of the records, and

When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of identifying at least some of the automatically expired ones of the records. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to identify at least some of the automatically expired ones of the records. Specifically, code contained within or accessed by the function rt_intern_hash in module /net/ipv4/route.c is used to practice a method that includes the step of identifying at least some of the automatically expired ones of the records. Page 13 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 The following code excerpt from the rt_intern_hash function is an example of identifying at least some of the automatically expired ones of the records: if (!atomic_read(&rth->u.dst.__refcnt)) { u32 score = rt_score(rth); if (score <= min_score) { cand = rth; candp = rthp; min_score = score; } } Source: Linux kernel source code file /net/ipv4/route.c The following code excerpt from the rt_intern_hash function is a second example of identifying at least some of the automatically expired ones of the records: if (rth->rt_genid != atomic_read(&rt_genid)) { Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited Page 14 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 limitation. When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of removing at least some of the automatically expired records from the linked list when the linked list is accessed. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to remove at least some of the automatically expired records from the linked list when the linked list is accessed. Specifically, code contained within the function rt_intern_hash in module /net/ipv4/route.c is used to practice a method that includes the step of removing at least some of the automatically expired records from the linked list when the linked list is accessed. The following code excerpt from the rt_intern_hash function is an example of removing at least some of the automatically expired records from the linked list when the linked list is accessed: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } Page 15 of 37

(c)

removing at least some of the automatically expired records from the linked list when the linked list is accessed.

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 } Source: Linux kernel source code file /net/ipv4/route.c The following code excerpt from the rt_intern_hash function is a second example of removing at least some of the automatically expired records from the linked list when the linked list is accessed: if (rth->rt_genid != atomic_read(&rt_genid)) { *rthp = rth->u.dst.rt_next; rt_free(rth); continue; } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

4.

The method according to claim 3 further including the step of dynamically determining maximum number of expired

When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of dynamically determining maximum number of expired ones of the records to remove Page 16 of 37

Dallas 296148v1

Claim Language ones of the records to remove when the linked list is accessed.

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 when the linked list is accessed. Specifically, code contained within function rt_intern_hash (in module /net/ipv4/route.c) that dynamically executes based upon comparison with variable ip_rt_gc_elasticity is used to perform the claimed act(s). In this way, computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 practices a method that includes the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to dynamically determine maximum number of expired ones of the records to remove when the linked list is accessed. The following code excerpt from the rt_intern_hash function is an example of dynamically determining the maximum number of expired ones of the records to remove when the linked list is accessed: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c Page 17 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

5.

An information storage and retrieval system, the system comprising:

Bedrock Computer Technologies LLC ("Bedrock") does not express a position at this time as to whether the preamble of this claim limits the claim's scope. Nevertheless, Bedrock identifies below aspects of the Accused Instrumentalities that correspond to the claim preamble. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted for information storage and retrieval. In the event this preamble is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this preamble and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(a)

a hashing means to provide

When Google makes, uses, sells, offers to sell or imports (or actively induces or Page 18 of 37

Dallas 296148v1

Claim Language access to records stored in a memory of the system and using an external chaining technique to store the records with same hash address, at least some of the records automatically expiring,

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include a hashing means to provide access to records stored in a memory of the system and using an external chaining technique to store the records with same hash address, where at least some of the records are automatically expiring or its equivalent. Specifically, data structure rt_hash_table in module /net/ipv4/route.c implements a hashing means to provide access to records stored in a memory of the system and using an external chaining technique to store the records with same hash address, where at least some of the records automatically are expiring or its equivalent. The following code excerpts from the files /net/ipv4/route.c and /include/net/route.h show the C language definition for the data structure rt_hash_table and the rtable struct definition used by rt_hash_table: struct rt_hash_bucket { struct rtable *chain; }; **** static struct rt_hash_bucket **** struct rtable { union { Page 19 of 37 *rt_hash_table __read_mostly;

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 struct dst_entry dst; } u; /* Cache lookup keys */ struct flowi fl; struct in_device int unsigned __u16 __be32 __be32 int *idev; rt_genid; rt_flags; rt_type; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */

/* Info on neighbour */ __be32 rt_gateway; /* Miscellaneous cached information */ __be32 rt_spec_dst; /* RFC1122 specific destination */ struct inet_peer *peer; /* long-living peer info */ }; Source: Linux kernel source code files /net/ipv4/route.c and /include/net/route.h Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because Page 20 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include a record search means utilizing a search key to access a linked list of records having the same hash address or its equivalent. Specifically, code contained within functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c calls functions rt_hash and rt_intern_hash. In this way, computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 includes a record search means utilizing a search key to access a linked list of records having the same hash address or its equivalent. The following code excerpt is one example of the rt_hash and rt_intern_hash functions being called by the function ip_route_input_mc: hash = rt_hash(daddr, saddr, dev->ifindex); return rt_intern_hash(hash, rth, &skb->rtable); Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Page 21 of 37

(b)

a record search means utilizing a search key to access a linked list of records having the same hash address,

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include the record search means including means for identifying and removing at least some expired ones of the records from the linked list of records when the linked list is accessed or its equivalent. Specifically, code contained within function rt_intern_hash, as invoked by functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c comprises record search means including means for identifying and removing at least some expired ones of the records from the linked list of records when the linked list is accessed or its equivalent. The following code excerpt from the rt_intern_hash function is an example of a record search means which includes a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); while ((rth = *rthp) != NULL) {

(c)

the record search means including means for identifying and removing at least some expired ones of the records from the linked list of records when the linked list is accessed, and

Page 22 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) { **** if (!atomic_read(&rth->u.dst.__refcnt)) { u32 score = rt_score(rth); if (score <= min_score) { cand = rth; candp = rthp; min_score = score; } } **** chain_length++; rthp = &rth->u.dst.rt_next; } **** if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. Page 23 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c The following code excerpt from the rt_intern_hash function is a second example of a record search means which includes a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); while ((rth = *rthp) != NULL) { if (rth->rt_genid != atomic_read(&rt_genid)) { *rthp = rth->u.dst.rt_next; rt_free(rth); continue; } if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) { **** chain_length++; Page 24 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 rthp = &rth->u.dst.rt_next; } **** Source: Linux kernel source code file /net/ipv4/route.c Note that the record(s) identified as expired upon traversal of the linked list is not necessarily the record that rt_intern_hash was called to find. In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(d)

mea[n]s, utilizing the record search means, for inserting, retrieving, and deleting records from the system and, at the same time, removing at least some expired ones of the records in the accessed linked list of records.

When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include means, utilizing the record search means, for inserting, retrieving, and deleting records from the system and, at the same time, removing at least some expired ones of the records in the accessed linked list of records or its equivalent. Specifically, the functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and/or ip_mkroute_output in module /net/ipv4/route.c include Page 25 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 means, utilizing the record search means, for inserting, retrieving, and deleting records from the system and, at the same time, removing at least some expired ones of the records in the accessed linked list of records or its equivalent. For example, the functions ip_rt_redirect, ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and ip_mkroute_output call rt_intern_hash to insert a new entry in rt_hash_table if the entry does not exist, the functions ip_route_input_mc, ip_mkroute_input, ip_route_input_slow, and ip_mkroute_output call rt_intern_hash to retrieve an existing entry from rt_hash_table, and the function ip_rt_redirect will delete one or more entries from rt_hash_table. In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

6.

The information storage and retrieval system according to claim 5 further including means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records.

When Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google makes, uses, sells, offers to sell or imports (or actively induces or contributes to same) a system that is especially adapted to include means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent. Specifically, code contained within function rt_intern_hash (in module /net/ipv4/route.c) dynamically executes based upon comparison with variable ip_rt_gc_elasticity. In this way, computer equipment configured with or utilizing software based on Linux kernel Page 26 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 version 2.6.26 includes means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent. The following code excerpt from the rt_intern_hash functions is an example of the variable ip_rt_gc_elasticity being used for dynamically determining the maximum number for the record search means to remove in the accessed linked list of records or its equivalent: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited Page 27 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 limitation. Bedrock does not express a position at this time as to whether the preamble of this claim limits the claim's scope. Nevertheless, Bedrock identifies below aspects of the Accused Instrumentalities that correspond to the claim preamble. When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method for storing and retrieving information records using a hashing technique to provide access to the records and using an external chaining technique to store the records with same hash address, at least some of the records automatically expiring. The Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to store and retrieve information records using a hashing technique to provide access to the records and using an external chaining technique to store the records with same hash address, where at least some of the records automatically expire. In the event this preamble is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this preamble and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

7.

A method for storing and retrieving information records using a hashing technique to provide access to the records and using an external chaining technique to store the records with same hash address, at least some of the records automatically expiring, the method comprising the steps of:

(a)

accessing a linked list of records having same hash address,

When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of accessing a linked list of records having same hash address. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially Page 28 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 adapted to access a linked list of records having same hash address. Specifically, data structure rt_hash_table in module /net/ipv4/route.c is used to access a linked list of records having the same hash address. Additionally, code contained within the function rt_intern_hash in module /net/ipv4/route.c is also used to access a linked list of records having the same hash address. In this way, computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 practices a method that includes the step of accessing a linked list of records having same hash address. The following code excerpts from the files /net/ipv4/route.c and /include/net/route.h show the C language definition for the data structure rt_hash_table and the rtable struct definition used by rt_hash_table: struct rt_hash_bucket { struct rtable *chain; }; **** static struct rt_hash_bucket **** struct rtable { union { struct dst_entry } u; dst; *rt_hash_table __read_mostly;

Page 29 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 /* Cache lookup keys */ struct flowi fl; struct in_device int unsigned __u16 __be32 __be32 int *idev; rt_genid; rt_flags; rt_type; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */

/* Info on neighbour */ __be32 rt_gateway; /* Miscellaneous cached information */ __be32 rt_spec_dst; /* RFC1122 specific destination */ struct inet_peer *peer; /* long-living peer info */ }; Source: Linux kernel source code files /net/ipv4/route.c and /include/net/route.h The following excerpt from the rt_intern_hash function is an example of code that practices a method that includes the step of accessing a linked list of records having same hash address: rthp = &rt_hash_table[hash].chain; spin_lock_bh(rt_hash_lock_addr(hash)); Page 30 of 37
Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 while ((rth = *rthp) != NULL) { **** chain_length++; rthp = &rth->u.dst.rt_next; } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(b)

identifying at least some of the automatically expired ones of the records,

When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of identifying at least some of the automatically expired ones of the records. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to identify at least some of the automatically expired ones of the records. Specifically, code contained within or accessed by the function rt_intern_hash in module /net/ipv4/route.c practices a method that includes the step of identifying at least some of Page 31 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 the automatically expired ones of the records. The following excerpt from the rt_intern_hash function is an example of code that practices a method of identifying at least some of the automatically expired ones of the records: if (!atomic_read(&rth->u.dst.__refcnt)) { u32 score = rt_score(rth); if (score <= min_score) { cand = rth; candp = rthp; min_score = score; } } Source: Linux kernel source code file /net/ipv4/route.c The following excerpt from the rt_intern_hash function is a second example of code that practices a method of identifying at least some of the automatically expired ones of the records: if (rth->rt_genid != atomic_read(&rt_genid)) { Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Page 32 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of removing at least some of the automatically expired records from the linked list when the linked list is accessed. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to remove at least some of the automatically expired records from the linked list when the linked list is accessed. Specifically, code contained within and/or called by the function rt_intern_hash in module /net/ipv4/route.c practices a method that includes the step of removing at least some of the automatically expired records from the linked list when the linked list is accessed. The following excerpt from the rt_intern_hash function is an example of code which practices a method of removing at least some of the automatically expired records from the linked list when the linked list is accessed: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { Page 33 of 37

(c)

removing at least some of the automatically expired records from the linked list when the linked list is accessed, and

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 *candp = cand->u.dst.rt_next; rt_free(cand); } } Source: Linux kernel source code file /net/ipv4/route.c The following excerpt from the rt_intern_hash function is a second example of code which practices a method of removing at least some of the automatically expired records from the linked list when the linked list is accessed: if (rth->rt_genid != atomic_read(&rt_genid)) { *rthp = rth->u.dst.rt_next; rt_free(rth); continue; } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

(d)

inserting, retrieving or deleting

When Google uses (or induces or contributes to others' use of) computer equipment Page 34 of 37

Dallas 296148v1

Claim Language one of the records from the system following the step of removing.

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of inserting, retrieving or deleting one of the records from the system following the step of removing. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to insert, retrieve or delete one of the records from the system following the step of removing. Specifically, code contained within the function rt_intern_hash in module /net/ipv4/route.c is used to practice a method that includes the step of inserting one of the records from the system following the step of removing. The following excerpt from the rt_intern_hash function is an example code which practices a method that includes the step of inserting one of the records from the system following the step of removing: rt->u.dst.rt_next = rt_hash_table[hash].chain; **** rt_hash_table[hash].chain = rt; Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation. Page 35 of 37

Dallas 296148v1

Claim Language 8. The method according to claim 7 further including the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed.

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 When Google uses (or induces or contributes to others' use of) computer equipment configured with or utilizing software based on Linux kernel version 2.6.26, Google practices (or induces or contributes to others' practice of) a method that includes the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed. Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 is especially adapted to dynamically determine maximum number of expired ones of the records to remove when the linked list is accessed. Specifically, code contained within function rt_intern_hash, in module /net/ipv4/route.c, dynamically executes based upon comparison with variable ip_rt_gc_elasticity. In this way, computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 practices a method that includes the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed. The following excerpt from the rt_intern_hash function is an example of code that practices a method that includes the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed: if (cand) { /* ip_rt_gc_elasticity used to be average length of chain * length, when exceeded gc becomes really aggressive. * * The second limit is less certain. At the moment it allows * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.dst.rt_next; rt_free(cand); Page 36 of 37

Dallas 296148v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.26 } } Source: Linux kernel source code file /net/ipv4/route.c In the event this limitation is construed so as to be not literally present in the Accused Instrumentalities, Bedrock would alternatively contend that the Accused Instrumentalities meet the recited limitation under the doctrine of equivalents, because any purported differences between this limitation and the aforementioned features of the Accused Instrumentalities would be insubstantial. For example, the aforementioned features of the Accused Instrumentalities would perform substantially the same function, in substantially the same way, to achieve substantially the same result, as the recited limitation.

Page 37 of 37
Dallas 296148v1