A victory for the trolls
The patent in question is #5,893,120 - "Methods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired data." The independent claims from the patent are short and simple; #3 reads like this:
- accessing the linked list of records,
- identifying at least some of the automatically expired ones of the records, and
- removing at least some of the automatically expired records from the linked list when the linked list is accessed.
Needless to say, numerous people who are "skilled in the art" have concluded that there is little that is original or non-obvious in this claim. In its defense, Google argued that the technique is, indeed, obvious (to the point that it should be invalidated under the Bilski ruling), that the patent is invalid due to prior art, and that Linux did not infringe upon the patent in any case. All of those arguments were pushed aside by the jury, which found Google guilty and granted an award of $5 million, a small fraction of the $183 million requested by Bedrock.
The full set of docket entries - almost 800 of them - are listed on the net. Many of the interesting ones are sealed, though, and unavailable to the public. We are all affected by this ruling, but we are unable to read most of testimony that led up to it. Instead, the bulk of the publicly-available information has to do with the various bits of legal jousting which set timetables and which control the evidence that can be presented. Thus, for example, we learn that a late attempt to bring in Alan Cox to testify on his early routing table work was pushed back and eventually abandoned. Still, there are some interesting things to be learned by plowing through these documents.
The code
The code in question is that which maintains the networking stack's routing cache - some of the oldest code in the kernel; it can be found in .../net/ipv4/route.c. This code maintains a hash table of linked lists containing routing entries; as the world changes, entries must be added or deleted. Bedrock claims that its patent is infringed by this code, though even Bedrock has, more or less, admitted [PDF] that any infringement will have been done inadvertently, with no knowledge that the patent existed. The various defendants (Google is only one of the companies targeted) have made various arguments, starting with the claim that the code does not use the algorithm described in the patent at all; see this brief [PDF] for a summary of that argument:
What one learns early on is that how terms like "when the linked list is accessed" are defined is crucial in a decision regarding infringement. That is where the "claim construction" process comes into play; for the full, gory details of how it was done in this case, see docket #369 [PDF]. There was a big fight, for example, over whether "removing from the linked list" required deallocation of the entry that was removed; Bedrock won that one and got a ruling that deallocation is a separate operation. The biggest fight seemed to be over whether removal "when the linked list is accessed" meant that the structure needed to be removed during the traversal of the list; Bedrock seemed to think that removal at some later time qualified, but the court disagreed. That should have been a decisive victory for the defense, but it appears to not have been enough.
Invalidation attempts
There was also a determined effort to have the patent ruled invalid due to prior art. It is interesting to note that, in early 2010, a separate challenge to this patent was raised at the US Patent and Trade Office, citing four other patents as prior art; the patent was, in fact, invalidated by the PTO last July. But Bedrock was then allowed to tweak the wording of the claims until the PTO agreed that the modified patent was, once again, valid. This history shows why attempts to kill patents so rarely achieve the desired results: patents can never truly be killed this way. Instead, the owner is allowed to make changes, resulting in zombie patents that return from the dead to terrorize again and again. A second challenge to the patent was filed in January of this year; it cites two more patents as prior art; a ruling has not yet been made in this case.
The defendants' attempt to invalidate the patent does not depend on that prior art at all, interestingly; instead, this challenge [PDF] is based on the Linux code itself. They claim that the code in route.c has not changed materially since the 1.3.x days and that, in particular, the 2.0.1 version was quite close to what we have now. These prior versions, it is claimed, include all of the claims of Bedrock's patents, and thus serve as prior art invalidating the patent. One might find some amusing irony in the claim that older code implemented the patented technique while current code - said to be about the same - does not. The point is, of course, that if the current code is said to infringe, the older code should be said to implement the patent in the same way. Either both versions implement the patented algorithm (in which case it's invalid due to prior art) or neither does.
The argument seems strong enough. We cannot know how Bedrock argued against this reasoning, though - its response is sealed and inaccessible. It is also worth noting that the US PTO has not considered older Linux releases as prior art when reevaluating this patent; it would appear that the challengers have not asked it to.
In the midst of all this, Red Hat has filed a suit of its own against Bedrock. It seems that some Red Hat customers have been getting nervous about Bedrock's activity and asked for help; Red Hat responded by filing a preemptive suit asking that the patent be ruled invalid and that Red Hat's products be deemed to be non-infringing. That case is still in the works; Red Hat also tried to jump into the Google et al. case [PDF], but that attempt was denied by the judge. In reading the filings, one also learns the Match.com (another defendant in the suit) made a deal with Bedrock and was allowed to drop out.
Now what?
This verdict has been widely publicized as a big defeat for Linux. Perhaps it is, but not for the reasons being cited - this particular patent is not a huge problem, but the fact that patent trolls can win judgments against Linux is problematic indeed. If need be, the kernel's routing table code can be tweaked to avoid infringing Bedrock's patent; indeed, Docket #445 [PDF] lets slip the fact that Google has already changed its kernels to that effect. There could be a case for past infringement, but there need be no real fear that Bedrock will be out there collecting rents from Linux users in the future, even if the ruling stands.
We can hope that the ruling will, in fact, not stand. If Red Hat prevails in its separate case, the verdict against Google will have to be reevaluated. Even in the absence of a victory there, Google's defense was strong enough to warrant an appeal. Google is just one of a number of companies which cannot let it be thought that Linux is an easy target for shakedowns by patent trolls; there is a strong incentive for the company to keep on fighting, even if that fight is likely to cost more than the (relatively small) $5 million it has been told to pay Bedrock. For all of our sake, we must hope that all of the companies involved in this case find it worth their while to get the ruling reversed.
If Bedrock loses in the end, other potential trolls will hopefully be
deterred from jumping in with suits of their own. But there can be no
doubt that more of these cases will come along; that is really just the
nature of the software patent system. Until we can get some sort of
high-level reform, we will always have to fear trolls wielding patents on
elementary techniques.
