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. 3

Exhibit 3

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.18 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.18, 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 34
Dallas 296153v1 1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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.18, 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.18 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: struct rt_hash_bucket {

(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.18 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 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 struct rtable *chain; }; **** static struct rt_hash_bucket **** struct rtable { union { struct dst_entry struct rtable } u; struct in_device unsigned __u16 __u16 __u32 __u32 int *idev; rt_flags; rt_type; rt_multipath_alg; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */ dst; *rt_next; *rt_hash_table;

/* Info on neighbour */ __u32 rt_gateway;

Page 3 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 /* Cache lookup keys */ struct flowi fl; /* Miscellaneous cached information */ __u32 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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect 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.18 includes a record search means Page 4 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect 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 equivalent: Page 5 of 34

Dallas 296153v1

Claim Language

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

#ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED if (!(rth->u.dst.flags & DST_BALANCED) && compare_keys(&rth->fl, &rt->fl)) { #else if (compare_keys(&rth->fl, &rt->fl)) { #endif **** 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++; Page 6 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 rthp = &rth->u.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. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.rt_next; rt_free(cand); } } 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, Page 7 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect 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_code(daddr, saddr ^ (dev->ifindex << 5)); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst); 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 Page 8 of 34

(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.

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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.18 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 * only 2 entries per bucket. We will see. */ if (chain_length > ip_rt_gc_elasticity) { Page 9 of 34

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 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 *candp = cand->u.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.18, 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.18 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 expiring. In the event this preamble is construed so as to be not literally present in the Accused Page 10 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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. 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.18, 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.18 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) { ****

(a)

accessing the linked list of records,

Page 11 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 chain_length++; rthp = &rth->u.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.18, 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.18 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. 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: Page 12 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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 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)

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

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.18, 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.18 is especially adapted to remove at least some of the automatically expired records from the linked list when the linked list is accessed.

Page 13 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.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, Page 14 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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. 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.18 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.18 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. */ Page 15 of 34

4.

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

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.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.

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.18, 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 Page 16 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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. 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.18, 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 *rt_hash_table; Page 17 of 34

(a)

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, at least some of the records automatically expiring,

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 **** struct rtable { union { struct dst_entry struct rtable } u; struct in_device unsigned __u16 __u16 __u32 __u32 int *idev; rt_flags; rt_type; rt_multipath_alg; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */ dst; *rt_next;

/* Info on neighbour */ __u32 rt_gateway; /* Cache lookup keys */ struct flowi fl; /* Miscellaneous cached information */ __u32 rt_spec_dst; /* RFC1122 specific destination */ struct inet_peer *peer; /* long-living peer info */ Page 18 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 }; 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 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 a linked list of records having the same hash address,

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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect 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.18 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 Page 19 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 being called by the function ip_route_input_mc: hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5)); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst); 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.

(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

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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect 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. Page 20 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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) { #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED if (!(rth->u.dst.flags & DST_BALANCED) && compare_keys(&rth->fl, &rt->fl)) { #else if (compare_keys(&rth->fl, &rt->fl)) { #endif **** if (!atomic_read(&rth->u.dst.__refcnt)) { u32 score = rt_score(rth); if (score <= min_score) { cand = rth; candp = rthp; min_score = score; } }

Page 21 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 **** chain_length++; rthp = &rth->u.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. */ if (chain_length > ip_rt_gc_elasticity) { *candp = cand->u.rt_next; rt_free(cand); } } 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 Page 22 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18, 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_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and/or ip_rt_redirect in module /net/ipv4/route.c 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. For example, the functions ip_route_input_mc, ip_mkroute_input_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, ip_mkroute_output, and ip_rt_redirect 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_def, ip_mkroute_input, ip_route_input_slow, ip_mkroute_output_def, 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 Page 23 of 34

(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.

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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. 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.18, 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.18 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. * Page 24 of 34

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.

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 * 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.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.

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:

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.18, 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.18 is especially adapted to Page 25 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.

(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.18, 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.18 is especially 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.18 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: Page 26 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 struct rt_hash_bucket { struct rtable *chain; }; **** static struct rt_hash_bucket **** struct rtable { union { struct dst_entry struct rtable } u; struct in_device unsigned __u16 __u16 __u32 __u32 int *idev; rt_flags; rt_type; rt_multipath_alg; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */ dst; *rt_next; *rt_hash_table;

/* Info on neighbour */ Page 27 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 __u32 rt_gateway; /* Cache lookup keys */ struct flowi fl; /* Miscellaneous cached information */ __u32 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)); while ((rth = *rthp) != NULL) { **** chain_length++; rthp = &rth->u.rt_next; } Source: Linux kernel source code file /net/ipv4/route.c

Page 28 of 34
Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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. 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.18, 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.18 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 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; Page 29 of 34

(b)

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

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 candp = rthp; min_score = score; } } 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.

(c)

removing at least some of the automatically expired records from the linked list when the linked list is accessed, 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.18, 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.18 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 Page 30 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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) { *candp = cand->u.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.

(d)

inserting, retrieving or deleting one of the records from the system following the step of

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.18, Google practices (or induces or contributes to others' practice of) a method that includes the step Page 31 of 34

Dallas 296153v1

Claim Language removing.

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 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.18 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.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 32 of 34
Dallas 296153v1

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.18 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.18, 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.18 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.18 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.rt_next; rt_free(cand); Page 33 of 34

Dallas 296153v1

Claim Language

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.18 } } 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 34 of 34
Dallas 296153v1