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

Filing 347

MOTION to Stay by AOL Inc, Amazon.com Inc., Google Inc., Match.Com LLC, Match.com, Inc., MySpace Inc., Softlayer Technologies, Inc., Yahoo! Inc.. (Attachments: #1 Affidavit, #2 Exhibit 1A, #3 Exhibit 1B, #4 Exhibit 2, #5 Exhibit 3, #6 Exhibit 4, #7 Exhibit 5, #8 Exhibit 6, #9 Exhibit 7, #10 Exhibit 8, #11 Text of Proposed Order)(Briggs, Todd)

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

Doc. 347 Att. 10

EXHIBIT 8

Dockets.Justia.com

BEDROCK COMPUTER TECHS., LLC V. SOFTLAYER TECH. SOLUTIONS, LLC, ET. AL PLAINTIFF'S P.R. 3-6 INFRINGEMENT CONTENTIONS Claim Language 1. An information storage and retrieval system, the system comprising: Court's Construction Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 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.11, 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. (a)1 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, a linked list to store and provide access to records means a list, capable of containing two or more records, in which each record contains a pointer to the next record or information indicating there is no next record automatically expiring means becoming obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time 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.11, 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.11, the data structure rt_hash_table in module /net/ipv4/route.c2 anchors one or more linked list(s) to store and
1 2

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.11 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 1 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 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.11 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:
static struct rt_hash_bucket *rt_hash_table;

struct rt_hash_bucket { struct rtable *chain; spinlock_t lock; } __attribute__((__aligned__(8))); struct rtable { union { struct dst_entry struct rtable } u; struct in_device unsigned unsigned __u32 __u32 int *idev; rt_flags; rt_type; 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 */

Page 2 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
__u32 */ struct inet_peer }; *peer; /* long-living peer info */ rt_spec_dst; /* RFC1122 specific destination

Source: Linux kernel source code files /net/ipv4/route.c and /include/net/route.h In the above code, an entry in the Linux IPv4 routing cache (rt_hash_table) is a list, capable of containing two or more records, in which each record contains a pointer to the next record or information indicating there is no next record. In particular, a rt_hash_table entry contains a field named chain which is a pointer to the first record of the list. Records of the list are C structs of the type rtable. A record contains a field named u.rt_next which is a pointer to the next record in the list. If there is no next record, then the u.rt_next field contains a null pointer. In the Linux IPv4 routing cache, a record of a linked list of the routing cache automatically expires when it becomes obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time. More specifically, Linux IPv4 scores the desirability or need for records in the information storage system based on the following criteria: 1. The age of the routing cache record 2. The type of route (such as multicast, broadcast, and local) 3. If the route has been redirected The function rt_score is the function that scores the desirability or need for

Page 3 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 records in the information storage system:
static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

Source: Linux kernel source code file /net/ipv4/route.c At least some of the records--if not all of the records--automatically expire according to the criteria used by rt_score. The records are stored in memory of the information storage system. (b) a record search means utilizing a search key to access the linked list, function: utilizing a search key to access the linked list structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4 lines 22-48, programmed with software instructions as described in Boxes 31-36 and Boxes 39-41 of FIG. 3 and in col. 5 line 53-col. 6 line 4 and col. 6 lines 14-20, and/or 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.11, 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. The following code within route.c performs the function of utilizing a Page 4 of 49

Claim Language

Court's Construction programmed with software instructions as described in the pseudocode of Search Table Procedure (cols. 11 and 12) or Alternate Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 search key to access the linked list:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); if (!rt_intern_hash(hash, rt, &rt))

* or *
hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);

* or *
hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos); err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);

* or *
hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos); err = rt_intern_hash(hash, rth, rp); static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos) { return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd) & rt_hash_mask); }

rt_intern_hash accesses the linked list and searches for a record by comparing keys:
rthp = &rt_hash_table[hash].chain; spin_lock_bh(&rt_hash_table[hash].lock); while ((rth = *rthp) != NULL) { if (compare_keys(&rth->fl, &rt->fl)) { **** *rp = rth; return 0;

Page 5 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
} **** chain_length++; rthp = &rth->u.rt_next; } **** spin_unlock_bh(&rt_hash_table[hash].lock); *rp = rt; return 0; } static inline int compare_keys(struct flowi *fl1, struct flowi *fl2) { return memcmp(&fl1->nl_u.ip4_u, &fl2->nl_u.ip4_u, sizeof(fl1>nl_u.ip4_u)) == 0 && fl1->oif == fl2->oif && fl1->iif == fl2->iif; }

Source: Linux kernel source code file /net/ipv4/route.c Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term. (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 function: identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4 lines 22-48, programmed with software instructions as 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.11, 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. Page 6 of 49

Claim Language

Court's Construction described in Boxes 33-42 of FIG. 3 and in col. 5 line 53-col. 6 line 34, and/or programmed with software instructions as described in the pseudo-code of Search Table Procedure (cols. 11 and 12) or Alternate Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 Specifically, code contained within function rt_intern_hash 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 performs the function of identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed:
spin_lock_bh(&rt_hash_table[hash].lock); while ((rth = *rthp) != NULL) { if (compare_keys(&rth->fl, &rt->fl)) { **** *rp = rth; return 0; } **** 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.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;

Page 7 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
rt_free(cand); } } **** spin_unlock_bh(&rt_hash_table[hash].lock); *rp = rt; return 0; } static inline int compare_keys(struct flowi *fl1, struct flowi *fl2) { return memcmp(&fl1->nl_u.ip4_u, &fl2->nl_u.ip4_u, sizeof(fl1>nl_u.ip4_u)) == 0 && fl1->oif == fl2->oif && fl1->iif == fl2->iif; } static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

Source: Linux kernel source code file /net/ipv4/route.c Note that the record(s) identified as expired upon traversal of the linked list

Page 8 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 is not necessarily the record that rt_intern_hash was called to find. Both the identification and the removal are performed when the linked list is accessed, as is evidenced by the locking and unlocking of the linked list by rt_intern_hash. Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term.

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

function: utilizing the record search means, accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4, lines 22-48, programmed with software instructions that provide the insert, retrieve, or delete record capability as described in the flowchart of FIG. 5 and col. 7 line 65 ­ col. 8 line 32, FIG. 6 and col. 8 lines 33-44, or FIG. 7 and col. 8 lines 45-59, respectively, and/or programmed with software instructions that provide the insert, retrieve or delete record capability as described in the pseudocode of Insert Procedure (cols. 9 and 10), Retrieve Procedure (cols. 9, 10, 11, and 12), or Delete Procedure (cols. 11 and 12), respectively, or the equivalents thereof

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.11, 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. The code identified below collectively performs the function of utilizing the record search means, accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list. This function is parsed out below for convenience. The following calls to the hashing function and rt_intern_hash are all utilizations of the record search means:
unsigned hash = rt_hash_code(daddr,

Page 9 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
skeys[i] ^ (ikeys[k] << 5), tos); if (!rt_intern_hash(hash, rt, &rt))

* or *
hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);

* or *
hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos); err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);

* or *
hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos); err = rt_intern_hash(hash, rth, rp); static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos) { return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd) & rt_hash_mask); }

rt_intern_hash, inserts a record:
static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp) { struct rtable *rth, **rthp; unsigned long now; struct rtable *cand, **candp; u32 min_score; int chain_length; int attempts = !in_softirq(); **** rt->u.rt_next = rt_hash_table[hash].chain; #if RT_CACHE_DEBUG >= 2 if (rt->u.rt_next) { struct rtable *trt; printk(KERN_DEBUG "rt_cache @%02x: %u.%u.%u.%u", hash, NIPQUAD(rt->rt_dst));

Page 10 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
for (trt = rt->u.rt_next; trt; trt = trt->u.rt_next) printk(" . %u.%u.%u.%u", NIPQUAD(trt->rt_dst)); printk("\n"); } #endif rt_hash_table[hash].chain = rt; spin_unlock_bh(&rt_hash_table[hash].lock); *rp = rt; return 0; }

rt_intern_hash retrieves a record:
static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp) { struct rtable *rth, **rthp; unsigned long now; struct rtable *cand, **candp; u32 min_score; int chain_length; int attempts = !in_softirq(); **** /* Put it first */ *rthp = rth->u.rt_next; /* * Since lookup is lockfree, the deletion * must be visible to another weakly ordered CPU before * the insertion at the start of the hash chain. */ rcu_assign_pointer(rth->u.rt_next, rt_hash_table[hash].chain); /* * Since lookup is lockfree, the update writes * must be ordered for consistency on SMP. */ rcu_assign_pointer(rt_hash_table[hash].chain, rth); rth->u.dst.__use++; dst_hold(&rth->u.dst); rth->u.dst.lastuse = now; spin_unlock_bh(&rt_hash_table[hash].lock);

Page 11 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
rt_drop(rt); *rp = rth; return 0; }

rt_intern_hash is also invoked when deleting a record:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); rthp=&rt_hash_table[hash].chain; rcu_read_lock(); while ((rth = rcu_dereference(*rthp)) != NULL) { struct rtable *rt; if (rth->fl.fl4_dst != daddr || rth->fl.fl4_src != skeys[i] || rth->fl.fl4_tos != tos || rth->fl.oif != ikeys[k] || rth->fl.iif != 0) { rthp = &rth->u.rt_next; continue; } if (rth->rt_dst != daddr || rth->rt_src != saddr || rth->u.dst.error || rth->rt_gateway != old_gw || rth->u.dst.dev != dev) break; dst_hold(&rth->u.dst); rcu_read_unlock(); rt = dst_alloc(&ipv4_dst_ops); if (rt == NULL) { ip_rt_put(rth); in_dev_put(in_dev); return; } ****

Page 12 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
rt_del(hash, rth); if (!rt_intern_hash(hash, rt, &rt)) ip_rt_put(rt); goto do_next; }

Source: Linux kernel source code file /net/ipv4/route.c As explained above, code within rt_intern_hash performs the function of accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list. Bedrock contends that that this limitation is literally met both identically and by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term. 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. function: dynamically determining maximum number for the record search means to remove in the accessed linked list of records structure: CPU 10, and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4, lines 22-48, programmed with software instructions to dynamically determine a maximum number of records to remove by choosing a search strategy of removing all expired records from a linked list or removing some but not all of the expired records as described in col. 6 line 56 ­ col. 7 line 15 and/or programmed with software instructions to dynamically determine a maximum number of records to remove by 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.11, 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.11 includes means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records or its equivalent. Page 13 of 49

Claim Language

Court's Construction choosing between the pseudocode of the Search Table Procedure (cols. 11 and 12) or Alternative Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 The following code excerpt from the rt_intern_hash function performs the function of dynamically determining maximum number for the record search means to remove in the accessed linked list of records:
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); } }

chain_length is a variable that dynamically changes to accurately represent the length of a chain, which is a factor internal to the information storage system:
chain_length++;

Source: Linux kernel source code file /net/ipv4/route.c Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term.

Page 14 of 49

Claim Language 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:

Court's Construction a linked list to store and provide access to the records means a list, capable of containing two or more records, in which each record contains a pointer to the next record or information indicating there is no next record automatically expiring means becoming obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 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.11, 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.11 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. 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:
static struct rt_hash_bucket *rt_hash_table;

struct rt_hash_bucket { struct rtable *chain; spinlock_t lock; } __attribute__((__aligned__(8))); struct rtable { union { struct dst_entry struct rtable } u; dst; *rt_next;

Page 15 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
struct in_device unsigned unsigned __u32 __u32 int *idev; rt_flags; rt_type; rt_dst; /* Path destination rt_src; /* Path source rt_iif; */ */

/* 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 */

Source: Linux kernel source code files /net/ipv4/route.c and /include/net/route.h In the above code, an entry in the Linux IPv4 routing cache (rt_hash_table) is a list, capable of containing two or more records, in which each record contains a pointer to the next record or information indicating there is no next record. In particular, a rt_hash_table entry contains a field named chain which is a pointer to the first record of the list. Records of the list are C structs of the type rtable. A record contains a field named u.rt_next which is a pointer to the next record in the list. If there is no next record, then the u.rt_next field contains a null pointer. In the Linux IPv4 routing cache, a record of a linked list of the routing cache automatically expires when it becomes obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time. More specifically, Linux IPv4 scores the Page 16 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 desirability or need for records in the information storage system based on the following criteria: 1. The age of the routing cache record 2. The type of route (such as multicast, broadcast, and local) 3. If the route has been redirected The function rt_score is the function that scores the desirability or need for records in the information storage system:
static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

Source: Linux kernel source code file /net/ipv4/route.c At least some of the records--if not all of the records--automatically expire according to the criteria used by rt_score. The records are stored in memory of the information storage system.

Page 17 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 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.11, 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.11 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 excerpts within route.c performs the step of accessing a linked list of records:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); if (!rt_intern_hash(hash, rt, &rt))

(a)

accessing the linked list of records,

linked list means a list, capable of containing two or more records, in which each record contains a pointer to the next record or information indicating there is no next record

* or *
hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);

* or *
hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos); err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);

* or *
hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos);

Page 18 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
err = rt_intern_hash(hash, rth, rp); static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos) { return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd) & rt_hash_mask); }

rt_intern_hash accesses the linked list:
rthp = &rt_hash_table[hash].chain;

Source: Linux kernel source code file /net/ipv4/route.c (b) identifying at least some of the automatically expired ones of the records, and expired means obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time 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.11, 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.11 is especially adapted to identify at least some of the automatically expired ones of the records. In the Linux IPv4 routing cache, a record of a linked list of the routing cache automatically expires when it becomes obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time. More specifically, Linux IPv4 scores the desirability or need for records in the information storage system based on the following criteria:

Page 19 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 1. The age of the routing cache record 2. The type of route (such as multicast, broadcast, and local) 3. If the route has been redirected The function rt_score is the function that scores the desirability or need for records in the information storage system:
static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

Source: Linux kernel source code file /net/ipv4/route.c At least some of the records--if not all of the records--automatically expire according to the criteria used by rt_score. Code contained within or accessed by the function rt_intern_hash in module /net/ipv4/route.c uses rt_score to practice a method that includes the step of Page 20 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 identifying at least some of the automatically expired ones of the records. The following code excerpt from the rt_intern_hash function performs the step of identifying at least some of the automatically expired ones of the records:
spin_lock_bh(&rt_hash_table[hash].lock); while ((rth = *rthp) != NULL) { if (compare_keys(&rth->fl, &rt->fl)) { **** *rp = rth; return 0; } **** 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.rt_next; } if (cand) {

Source: Linux kernel source code file /net/ipv4/route.c (c) removing at least some of the automatically expired records from the linked list when the linked list is accessed. removing at least some of the automatically expired records from the linked list means adjusting the pointer in the linked list to bypass the previously identified expired records when the linked list is accessed means both identification 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.11, 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

Page 21 of 49

Claim Language

Court's Construction and removal of the automatically expired record(s) occurs during the same access of the linked list

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 on Linux kernel version 2.6.11 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.rt_next; rt_free(cand); } }

The line of code *candp = cand->u.rt_next; performs the step of adjusting the pointer in the linked list to bypass the previously identified expired records. Source: Linux kernel source code file /net/ipv4/route.c Both the identification and the removal are performed when the linked list is accessed, as is evidenced by the locking and unlocking of the linked list by Page 22 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 rt_intern_hash. As shown in the code below, the identifying step starts before the removal step:
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); } }

{ordering of the steps}

ordering of the steps: The identifying step must start before removal can begin. However, identification need not be completed before removal can begin. The identification step may overlap with the removal step.

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.

dynamically determining means making a decision based on factors internal or external to the information storage and retrieval system

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.11, 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.11 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.11 is especially adapted to dynamically determine maximum number of expired ones of the

Page 23 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 records to remove when the linked list is accessed. The following code excerpt from the rt_intern_hash function performs the step 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.rt_next; rt_free(cand); } }

chain_length is a variable that dynamically changes to accurately represent the length of a chain, which is a factor internal to the information storage system:
chain_length++;

The line of code if (chain_length > ip_rt_gc_elasticity) therefore makes a decision based on factors internal or external to the information storage and retrieval system. Source: Linux kernel source code file /net/ipv4/route.c 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

Page 24 of 49

Claim Language

Court's Construction

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

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

function: 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 structure: CPU 10, and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4, lines 22-48, programmed with software instructions to provide a hash table having a pointer to the head of a linked list of externally chained records as described in col. 5 lines 16-26 and/or programmed with software instructions as described in the pseudo-code of Definitions, definition number 4, or the equivalents thereof

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.11, 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:
static struct rt_hash_bucket *rt_hash_table;

Page 25 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
struct rt_hash_bucket { struct rtable *chain; spinlock_t lock; } __attribute__((__aligned__(8))); struct rtable { union { struct dst_entry struct rtable } u; struct in_device unsigned unsigned __u32 __u32 int *idev; rt_flags; rt_type; 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 }; ipv4_dst_ops.kmem_cachep = kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0, SLAB_HWCACHE_ALIGN, NULL, NULL); **** goal = num_physpages >> (26 - PAGE_SHIFT); if (rhash_entries) goal = (rhash_entries * sizeof(struct rt_hash_bucket)) >> PAGE_SHIFT; for (order = 0; (1UL << order) < goal; order++) /* NOTHING */; *peer; /* long-living peer info */

Page 26 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
do { rt_hash_mask = (1UL << order) * PAGE_SIZE / sizeof(struct rt_hash_bucket); while (rt_hash_mask & (rt_hash_mask - 1)) rt_hash_mask--; rt_hash_table = (struct rt_hash_bucket *) __get_free_pages(GFP_ATOMIC, order); } while (rt_hash_table == NULL && --order > 0); **** rt_hash_mask--; for (i = 0; i <= rt_hash_mask; i++) { spin_lock_init(&rt_hash_table[i].lock); rt_hash_table[i].chain = NULL;

Source: Linux kernel source code file /net/ipv4/route.c (b) a record search means utilizing a search key to access a linked list of records having the same hash address, function: utilizing a search key to access the linked list structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4 lines 22-48, programmed with software instructions as described in Boxes 31-36 and Boxes 39-41 of FIG. 3 and in col. 5 line 53-col. 6 line 4 and col. 6 lines 14-20, and/or programmed with software instructions as described in the pseudocode of Search Table Procedure (cols. 11 and 12) or Alternate Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof 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.11, 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. The following code within route.c performs the function of utilizing a search key to access the linked list:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); if (!rt_intern_hash(hash, rt, &rt))

* or *
hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos);

Page 27 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);

* or *
hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos); err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);

* or *
hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos); err = rt_intern_hash(hash, rth, rp); static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos) { return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd) & rt_hash_mask); }

rt_intern_hash accesses the linked list and searches for a record by comparing keys:
rthp = &rt_hash_table[hash].chain; spin_lock_bh(&rt_hash_table[hash].lock); while ((rth = *rthp) != NULL) { if (compare_keys(&rth->fl, &rt->fl)) { **** *rp = rth; return 0; } **** chain_length++; rthp = &rth->u.rt_next; } **** spin_unlock_bh(&rt_hash_table[hash].lock); *rp = rt; return 0; } static inline int compare_keys(struct flowi *fl1, struct flowi *fl2) {

Page 28 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
return memcmp(&fl1->nl_u.ip4_u, &fl2->nl_u.ip4_u, sizeof(fl1>nl_u.ip4_u)) == 0 && fl1->oif == fl2->oif && fl1->iif == fl2->iif; }

Source: Linux kernel source code file /net/ipv4/route.c Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term. (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 function: identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4 lines 22-48, programmed with software instructions as described in Boxes 33-42 of FIG. 3 and in col. 5 line 53-col. 6 line 34, and/or programmed with software instructions as described in the pseudo-code of Search Table Procedure (cols. 11 and 12) or Alternate Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof 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.11, 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 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 performs the function of identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed: Page 29 of 49

Claim Language

Court's Construction

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

spin_lock_bh(&rt_hash_table[hash].lock); while ((rth = *rthp) != NULL) { if (compare_keys(&rth->fl, &rt->fl)) { **** *rp = rth; return 0; } **** 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.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); } } **** spin_unlock_bh(&rt_hash_table[hash].lock); *rp = rt; return 0; } static inline int compare_keys(struct flowi *fl1, struct flowi *fl2)

Page 30 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
{ return memcmp(&fl1->nl_u.ip4_u, &fl2->nl_u.ip4_u, sizeof(fl1>nl_u.ip4_u)) == 0 && fl1->oif == fl2->oif && fl1->iif == fl2->iif; } static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

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. Both the identification and the removal are performed when the linked list is accessed, as is evidenced by the locking and unlocking of the linked list by rt_intern_hash. Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused

Page 31 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term. 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.11, 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. The code identified below collectively performs the function of utilizing the record search means, 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. This function is parsed out below for convenience. Specifically, the following calls to the hashing function and rt_intern_hash are all utilizations of the record search means:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); if (!rt_intern_hash(hash, rt, &rt))

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

function: utilizing the record search means, 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 structure: CPU 10 and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4, lines 22-48, programmed with software instructions that provide the insert, retrieve, and delete record capability as described in the flowchart of FIG. 5 and col. 7 line 65 ­ col. 8 line 32, FIG. 6 and col. 8 lines 33-44, or FIG. 7 and col. 8 lines 45-59, respectively, and/or programmed with software instructions that provide the insert, retrieve and delete record capability as described in the pseudo-code of Insert Procedure (cols. 9 and 10), Retrieve Procedure (cols. 9, 10, 11, and 12), and Delete Procedure (cols. 11 and 12), respectively, or the equivalents thereof

* or *
hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos); return rt_intern_hash(hash, rth, (struct rtable**) &skb->dst);

Page 32 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 * or *
hash = rt_hash_code(daddr, saddr ^ (fl.iif << 5), tos); err = rt_intern_hash(hash, rth, (struct rtable**)&skb->dst);

* or *
hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos); err = rt_intern_hash(hash, rth, rp); static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos) { return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd) & rt_hash_mask); }

rt_intern_hash, inserts a record:
static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp) { struct rtable *rth, **rthp; unsigned long now; struct rtable *cand, **candp; u32 min_score; int chain_length; int attempts = !in_softirq(); **** rt->u.rt_next = rt_hash_table[hash].chain; #if RT_CACHE_DEBUG >= 2 if (rt->u.rt_next) { struct rtable *trt; printk(KERN_DEBUG "rt_cache @%02x: %u.%u.%u.%u", hash, NIPQUAD(rt->rt_dst)); for (trt = rt->u.rt_next; trt; trt = trt->u.rt_next) printk(" . %u.%u.%u.%u", NIPQUAD(trt->rt_dst)); printk("\n"); } #endif rt_hash_table[hash].chain = rt; spin_unlock_bh(&rt_hash_table[hash].lock);

Page 33 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11
*rp = rt; return 0; }

rt_intern_hash retrieves a record:
static int rt_intern_hash(unsigned hash, struct rtable *rt, struct rtable **rp) { struct rtable *rth, **rthp; unsigned long now; struct rtable *cand, **candp; u32 min_score; int chain_length; int attempts = !in_softirq(); **** /* Put it first */ *rthp = rth->u.rt_next; /* * Since lookup is lockfree, the deletion * must be visible to another weakly ordered CPU before * the insertion at the start of the hash chain. */ rcu_assign_pointer(rth->u.rt_next, rt_hash_table[hash].chain); /* * Since lookup is lockfree, the update writes * must be ordered for consistency on SMP. */ rcu_assign_pointer(rt_hash_table[hash].chain, rth); rth->u.dst.__use++; dst_hold(&rth->u.dst); rth->u.dst.lastuse = now; spin_unlock_bh(&rt_hash_table[hash].lock); rt_drop(rt); *rp = rth; return 0; }

Page 34 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 rt_intern_hash is also invoked when deleting a record:
unsigned hash = rt_hash_code(daddr, skeys[i] ^ (ikeys[k] << 5), tos); rthp=&rt_hash_table[hash].chain; rcu_read_lock(); while ((rth = rcu_dereference(*rthp)) != NULL) { struct rtable *rt; if (rth->fl.fl4_dst != daddr || rth->fl.fl4_src != skeys[i] || rth->fl.fl4_tos != tos || rth->fl.oif != ikeys[k] || rth->fl.iif != 0) { rthp = &rth->u.rt_next; continue; } if (rth->rt_dst != daddr || rth->rt_src != saddr || rth->u.dst.error || rth->rt_gateway != old_gw || rth->u.dst.dev != dev) break; dst_hold(&rth->u.dst); rcu_read_unlock(); rt = dst_alloc(&ipv4_dst_ops); if (rt == NULL) { ip_rt_put(rth); in_dev_put(in_dev); return; } **** rt_del(hash, rth); if (!rt_intern_hash(hash, rt, &rt)) ip_rt_put(rt); goto do_next; }

Page 35 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 Source: Linux kernel source code file /net/ipv4/route.c As explained above, code within rt_intern_hash performs the function of removing at least some of the expired ones of the records in the linked list. Bedrock contends that that this limitation is literally met both identically and by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term.

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.

function: dynamically determining maximum number for the record search means to remove in the accessed linked list of records structure: CPU 10, and RAM 11 of FIG. 1 and col. 3 lines 52-56 and portions of the application software, user access software or operating system software, as described at col. 4, lines 22-48, programmed with software instructions to dynamically determine a maximum number of records to remove by choosing a search strategy of removing all expired records from a linked list or removing some but not all of the expired records as described in col. 6 line 56 ­ col. 7 line 15 and/or programmed with software instructions to dynamically determine a maximum number of records to remove by choosing between the pseudocode of the Search Table Procedure (cols. 11 and 12) or Alternative Version of Search Table Procedure (cols. 11, 12, 13, and 14), or the equivalents thereof

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.11, 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.11 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 function performs the function of dynamically determining maximum number for the record search means to remove in the accessed linked list of records:

Page 36 of 49

Claim Language

Court's Construction

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

chain_length is a variable that dynamically changes to accurately represent the length of a chain, which is a factor internal to the information storage system:
chain_length++;

Source: Linux kernel source code file /net/ipv4/route.c Bedrock contends that that this limitation is literally met by statutory equivalence per 35 U.S.C. § 112 ¶ 6, i.e., the code in the Accused Instrumentality performs the identical function as construed by the Court, in substantially the same way as the construed structure for this term, to achieve substantially the same result achieved by the construed structure for this term. 7. A method for storing and retrieving information records using a hashing technique to provide external chaining means a technique for resolving hash collisions using a linked list(s) 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.

Page 37 of 49

Claim Language 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:

Court's Construction automatically expiring means becoming obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 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.11, 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.11 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. The Linux IPv4 routing cache use external chaining, a technique for resolving hash collisions using linked lists. In particular, for each unique hash value, the routing cache table, rt_hash_table, contains an entry called a rt_hash_bucket. In turn, a bucket contains an entry named chain which is a pointer to the first record of a linked list of routing cache records.
static struct rt_hash_bucket *rt_hash_table; struct rt_hash_bucket { struct rtable *chain; spinlock_t lock; } __attribute__((__aligned__(8)));

Source: Linux kernel source code file /net/ipv4/route.c In the Linux IPv4 routing cache, a record of a linked list of the routing cache automatically expires when it becomes obsolete and therefore no longer needed or desired in the storage system because of some condition, event, or period of time. More specifically, Linux IPv4 scores the

Page 38 of 49

Claim Language

Court's Construction

Accused Instrumentalities: Computer equipment configured with or utilizing software based on Linux kernel version 2.6.11 desirability or need for records in the information storage system based on the following criteria: 1. The age of the routing cache record 2. The type of route (such as multicast, broadcast, and local) 3. If the route has been redirected The function rt_score is the function that scores the desirability or need for records in the information storage system:
static inline u32 rt_score(struct rtable *rt) { u32 score = jiffies - rt->u.dst.lastuse; score = ~score & ~(3<<30); if (rt_valuable(rt)) score |= (1<<31); if (!rt->fl.iif || !(rt->rt_flags & (RTCF_BROADCAST|RTCF_MULTICAST|RTCF_LOCAL))) score |= (1<<30); return score; } static __inline__ int rt_valuable(struct rtable *rth) { return (rth->rt_flags & (RTCF_REDIRECTED | RTCF_NOTIFY)) || rth->u.dst.expires; }

Source: Linux kernel source code file /net/ipv4/route.c (a) accessing a linke