use of patented algorithms in the kernel ok or not?

Hi,

Apologies for posting this OT question here, I didn't find this question answered in the FAQ.

There's a fast algorithm for longest-prefix match (as used in IPv4 routing table lookups) which I have implemented, and would like to submit for inclusion into the kernel (when 2.7 opens.)

However, I am aware that there is a patent on this algorithm, exclusively licensed to a major manufacturer of networking equipment.

What am I to do? Ignore the patent? Or should I refrain from submitting the patch I wrote, and look for an unencumbered algorithm instead?

thanks,
Lennert

Don't submit, and find an unencumbered algorithm. Unless you can get the patent holder to grant a license (it does happen).

Linus

If you are not the patent holder and are not licensed by them, then I don't think you have the right to be publishing code using it, anywhere, Linux kernel or elsewhere.

And I presume that if we found code in the kernel that used a patent that had not been released by its holder for use under the GPL, we would rip that code out.

And I am not a lawyer. You should ignore my advice above, and obtain the council of a qualified attorney, before continuing on the path you considering.

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

a patent in which country ?

Maybe we need a CONFIG_USA so that we can enhance the kernel for non-unitedstatians while keeping it safe to run in that one country with the patents as well.

On Fri, 2003-12-19 09:47:05 +0100, Arjan van de Ven <[email protected]> wrote in message <[email protected]>:

:-) So we're giving the most doggy style, worst case performer to USA? With any goodies ripped off? Sounds like fun...

MfG, JBG

   Jan-Benedict Glaw       [email protected]    . +49-172-7608481
   "Eine Freie Meinung in  einem Freien Kopf    | Gegen Zensur | Gegen Krieg
    fuer einen Freien Staat voll Freier Bürger" | im Internet! |   im Irak!
   ret = do_actions((curr | FREE_SPEECH) & ~(NEW_COPYRIGHT_LAW | DRM | TCPA));

Ask a lawyer first - ahm - unless you have CONFIG_GUANTANAMO_BAY enabled...

Raph Levien holds some GPL-friendly patents.
see: http://www.levien.com/patents.html.

Try to get a patent holder to make a statement like Raph did and it's suitable for Linux and other free software projects.

  ciao - 
    Stefan

Seriously, I am working on code which would potentially infringe a good number of patents in the USA, if it were used there, but I do not know which ones. It is a guess.

Where I live most of those patents are not relevant. So I do not make a point of studying them. I do not live or work in the USA, and my code is more useful to people in the rest of the world anyway. But I would still like to share it without bias to people in all countries.

One or two of the patents may be relevant due to a problem of ambiguity from allegedly illegally granted patents in the country where I live. Even if those patents in this country could be shown to be invalid (not the same as illegal), I am not large enough economically (i.e. I'm a small business, not a large business) to afford the risk or legal costs of assuming that. Therefore I must hope for some clarity in the law here regarding their illegality, which may come.

I know that equivalent code, which is covered by most if not all of the patents, is sold by some software companies to product developers _in the USA_ without prelicensed patents. The problem of acquiring suitable patent licenses is left to the purchasers.

Rationally I would expect that if someone is able to sell code and leave the problem of patent licensing to the purchaser, then one should be able to _give away_ code and leave the problem of patent licensing to the recipient.

Yet it is clear from a million threads like this one that giving away code freely is feared to be patent infringement even when selling it under restrictive licensing is not.

There is a horrible dichotomy in this picture, and I'm not sure what to do about it. Stopping innovating due to fear of potential patent litigation does not seem like a right thing to do. Switching to a closed-source model because that removes one from liability does not seem like a right thing either.

I would be really pleased if someone were able to show that distributing code in a disabled form, for example using something like CONFIG_USA which you mentioned, or something which requires more expertise to change, placed liabilities for enabling and using the code upon the person who does the enabling, and not the original author or distributor of the code.

Is there any USA-based precedent to that effect? Perhaps that's even the norm and I have not understood how things work there?

Thanks,
-- Jamie

Like copyright the onus of patent enforcement is on the patent holder. The key is to not do what would be reasonably expected to infringe on a patent. Reasonable that is in the assessment of the court.

If the patent holder believes something in the kernel to be infringing the holder has to decide what is in it's best interests. First the holder will need to try to mitigate harm by requesting the infringement be removed. I have no doubt anything reasonable assessed as infringing would be removed quickly. That would be the polite thing to do and only a SCO would jump straight to filing for injunctions and lawsuits. I don't think it can seek damages of anyone without first attempting to mitigate.

Whether they would file a lawsuit would have to be at least partly a PR decision. Is it good press to be suing people perceived as doing charity work? Then the bean counters have their say. How much money (shallow pockets) would they be able to recover compared to the costs of litigation although a un-enforced patent becomes an unenforcable patent (see mitigation). Finally, most patents are part of large portfolios used for the purpose of cross-licensing to keep small players out of the market. The last thing they ever want to have happen is to actually have their patents examined in court for validity.

With regards to going after the Linux kernel there would also be the risk that such a lawsuit would threaten other portfolio holders. I suspect Linux will soon be a no-man's land for patent suits even without the OSL's patent terms. IBM, SGI, and HP as well as consumer electronics manufacturers and others have a lot of their futures invested in Linux and that dependency will only grow with time. In a few years the US military and government as well as other governments will be addicted to Linux, when that happens the suits that show up at your office asking you not to pursue the matter will not just be grey but also brown, blue and black.

________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		[email protected]

		Remember Cernan and Schmitt

Hi!

As far as I can see, it is okay to ignore patents *if you are doing research*. So you should be able to offer it to US people for research purposes.

Pavel

Pavel,

According to recently passed legislation, this may no longer be true. It remains to be tested, but my understanding is that this "research" shield is now gone.

-chuck

Hi!

Time to move to Cuba?

[Well, I thought that explicit reason for patents is "to promote research", and it used to be okay to improve upon someone else's patent. If patents no longer serve that purpose (if you can't improve upon someone elses work, it is worse than he keeping it secret; and patents were made so that people would not keep stuff secret), perhaps its time to ask if they are still constitutional?]
Pavel

When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

According to current Patent Law in the United States;

FYI: Read

http://www4.law.cornell.edu/uscode/35/273.html

You infringe just by smelling like a patent. However, there are lots of defenses to infringement: prior art, prior reduction to practice, practically anything done in "good faith", i.e., use of a process that was not known to be patented. Good faith is required to show that infringement was stopped as soon as the inventor brought the infringement to the attention of the infringer, etc.

Basically, you do NOT have to check to see if your "process" or whatever has been previously invented. You do, however, need to stop infringing as soon as such infringement becomes known.

For that reason, it is my opinion (not the opinion of any court, or officer of the court) that a search for possible patent infringements can only lead to hardship. You might find an infringement that was never enforced or is not enforceable, forcing you to rewrite stuff that is "common public knowledge". Or you might find that everything is original and, therefore have a false sense of security (Santa Claus Operations ^M^MSCO^M^M might sue you anyway....)

For patents that have been secured by a company, but made secret by the government, you certainly have no way of knowing if an invention exists. For instance, it is common knowledge that the transistor was invented by Bill Shockley and John Bardeen at AT&T in 1948. However, arming mechanisms for torpedos, used in WWII, used transistors. The boards containing them had a US Navy Anchor stamp, marked 1945, 3 years before they were invented. This was my source of transistors, from Eli Hefferon's electronic scrap, as a boy!

Also, when I made a solid-state rate-gyro as a high school Science Fair project, I got a cease and desist order from a federal court in New York, because Sperry claimed that what I developed was their secret invention... Go figure.

It was many years later that I understood that the "acoustic gyro" I made as a kid used the same principles as the strap-down-laser-gyro that Sperry had developed for ICBMs. The government apparently thought that my project would make obvious to "the enemy" what was obvious to all my class-mates, --hardly an earth shaking invention.

Basically do what original thought, review of published documentation, and ordinary care lets you do. Don't waste time worrying about suits from the ass^M^Mrectums that exist. If they want to sue, they will. If they don't, they won't. They won't let facts get in the way.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.24 on an i686 machine (797.90 BogoMips).
Note 96.31% of all statistics are fiction.

The United States of America.

But can we still distribute it from the USA then?

--L

This whole thing seems strange to me.

Why do you even know the algorithm is patented? And if you knew it was, why implement it? If you implemented it and then did a search you poisoned yourself.

I've not poked around in the routing code but it seems to me that the kernel would need a longest-prefix match algorithm already so you shouldn't have to look far for one.

As for asking the patent holder for a license. If the patent were owned by a network hardware company i cannot see them licensing it because the speed of their equipment is their competitive advantage. But you indicated the the patent is not owned by the HW company but exclusively licensed. An existing exclusive license would preclude FLOSS being granted a license and a gratis sublicense would likely violate the existing license.

It would be completely OT to wonder at what point source code crossed the line of expressing information of public record into being a patent violation. <niggle>

________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		[email protected]

		Remember Cernan and Schmitt

I implemented the algorithm, and before submitting it, I asked the authors of the paper I used to implement the algorithm what the patent status of this algorithm is. The paper doesn't say anything about any patents (in retrospect, obviously it wouldn't.)

There is one already, and it's suboptimal, to say it mildly.

I asked this question on l-k because there seem to be many 'common' techniques in wide use which have US patents covering them.

Considering the circumstances, yes, licensing is probably out of the question.

I wouldn't be surprised if publishing source code implementing a patented algorithm would itself be considered as a patent violation (I'm not saying that it would make sense to me though.)

I think this l-k thread was sufficiently instructive for me to decide that I won't be publishing my implementation of this algorithm, and I'll just wait until another (free) LPM algorithm pops up.

--L