[OT] use of patented algorithms in the kernel ok or not?

[OT] use of patented algorithms in the kernel ok or not?

[Lennert Buytenhek]

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Linus Torvalds]

On Thu, 18 Dec 2003, Lennert Buytenhek wrote:
> 
> 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?

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

		Linus

Re: [OT] use of patented algorithms in the kernel ok or not?

[Paul Jackson]

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 <pj@sgi.com> 1.650.933.1373

Re: [OT] use of patented algorithms in the kernel ok or not?

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 390 bytes --]

On Fri, 2003-12-19 at 00:11, Lennert Buytenhek wrote:

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

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.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Jan-Benedict Glaw]

[-- Attachment #1: Type: text/plain, Size: 955 bytes --]

On Fri, 2003-12-19 09:47:05 +0100, Arjan van de Ven <arjanv@redhat.com>
wrote in message <1071823624.5223.1.camel@laptop.fenrus.com>:
> On Fri, 2003-12-19 at 00:11, Lennert Buytenhek wrote:
> 
> > However, I am aware that there is a patent on this algorithm, exclusively
> > licensed to a major manufacturer of networking equipment.
> 
> 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.

:-) 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       jbglaw@lug-owl.de    . +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));

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Stefan Traby]

On Fri, Dec 19, 2003 at 09:47:05AM +0100, Arjan van de Ven wrote:
> On Fri, 2003-12-19 at 00:11, Lennert Buytenhek wrote:
> 
> > However, I am aware that there is a patent on this algorithm, exclusively
> > licensed to a major manufacturer of networking equipment.
> 
> 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.

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Jamie Lokier]

Arjan van de Ven wrote:
> On Fri, 2003-12-19 at 00:11, Lennert Buytenhek wrote:
> > However, I am aware that there is a patent on this algorithm, exclusively
> > licensed to a major manufacturer of networking equipment.
> 
> 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.

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Pavel Machek]

Hi!

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

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Chuck Campbell]

On Sun, Dec 21, 2003 at 11:57:55AM -0500, Pavel Machek wrote:
> Hi!
> 
> > 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.
> 
> 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,

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Pavel Machek]

Hi!

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

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?]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Richard B. Johnson]

On Tue, 13 Jan 2004, Pavel Machek wrote:

> Hi!
>
> > > > 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.
> > >
> > > 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.
> >
> > 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.
>
> 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
>

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.

Re: [OT] use of patented algorithms in the kernel ok or not?

[jw schultz]

On Sun, Dec 21, 2003 at 10:33:08AM +0000, Jamie Lokier wrote:
> 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.

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:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [OT] use of patented algorithms in the kernel ok or not?

[Lennert Buytenhek]

On Fri, Dec 19, 2003 at 09:47:05AM +0100, Arjan van de Ven wrote:

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

The United States of America.


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

But can we still distribute it from the USA then?


--L

Re: [OT] use of patented algorithms in the kernel ok or not?

[jw schultz]

On Thu, Dec 18, 2003 at 06:11:37PM -0500, Lennert Buytenhek wrote:
> 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?

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:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [OT] use of patented algorithms in the kernel ok or not?

[Lennert Buytenhek]

On Sat, Dec 20, 2003 at 05:25:04PM -0800, jw schultz wrote:

> > 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?
> 
> 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 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.)


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

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


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

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.


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

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

Re: [OT] use of patented algorithms in the kernel ok or not?

[Albert Cahalan]

Linus writes:
> On Thu, 18 Dec 2003, Lennert Buytenhek wrote:

>> 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?
>
> Don't submit, and find an unencumbered algorithm.
> Unless you can get the patent holder to grant a
> license (it does happen).

What about the obvious Kconfig option?

config PATENT_1234567890
        bool "Patent 1234567890"
        default n
        help
          Say Y here if you have the right to use
          patent 1234567890 (the foo patent). Some
          countries do not recognise this patent, an
          educational or research exemption may apply,
          you may be the patent holder, the patent
          may have expired, or you may have aquired
          rights via licensing. Seek legal help if you
          need advice concerning your rights. If unsure,
          say N.

This assumes that the patented algorithm is
important enough to bother with, and we'd all
hope a non-patented alternative is available
for those of us without rights to the patent.

Re: [OT] use of patented algorithms in the kernel ok or not?

[Jamie Lokier]

Albert Cahalan wrote:
> What about the obvious Kconfig option?
> 
> config PATENT_1234567890
>         bool "Patent 1234567890"
>         default n
>         help
>           Say Y here if you have the right to use
>           patent 1234567890 (the foo patent). Some
>           countries do not recognise this patent, an
>           educational or research exemption may apply,
>           you may be the patent holder, the patent
>           may have expired, or you may have aquired
>           rights via licensing. Seek legal help if you
>           need advice concerning your rights. If unsure,
>           say N.

I expect this was said in jest, but it would be delightful to see this
done for real.  To the best of my knowlege it's uncharted territory,
so perhaps what you suggest _would_ be upheld in a court of law as
permissible?

    1. You seggragate code using the feature so that if it is not
       explicitly activated, then the patented method will not be used.

    2. You are clearly informing the recipient of the software of their
       need to determine for themselves whether they are permitted to
       use the feature, and suggest how they can go about this.

    3. Using the patented method requires a clear, explicit step by
       the recipient of the software, with no potential for
       misunderstanding.  It is just as clear as those disclaimer
       buttons, ensuring that a user knows their rights and duties and
       agrees to them before they are allowed access to something.


Closed source commercial software already does this sort of thing.
Was it not the case that if you purchased the appropriate license from
Unisys, you were then permitted to activate the GIF writing support of
Photoshop or some similar product, and that was done with an
activation code that you typed in to the program.

CONFIG_PATENT_nnnnnnnnn is the same thing, yet we are wary of
distributing open source software like that.  Is the significant
difference that it's too easy to enable without a license?  That may
well prove to be the determining factor in clarifying the legal
boundary of of who is liable - the sender of disabled code, or the
recipient who enables it without permission.

Certainly it cannot be justified under law that, even as closed source
implementations are distributed using activation code methods, the
open source implementations are not distributable solely because they
can be read by anyone.  Patent holders do not have the power, at least
not in law, to prevent sharing written explanations of a method, do
they?  I thought it had something to do with _using_ the methods,
although it continues to be a bit ambiguous what a patent holder may
restrict and what they have no legal right to restrict in this field.

-- Jamie

Re: [OT] use of patented algorithms in the kernel ok or not?

[James Morris]

On Sun, 21 Dec 2003, Jamie Lokier wrote:

> Albert Cahalan wrote:
> > What about the obvious Kconfig option?
> > 
> > config PATENT_1234567890
> >         bool "Patent 1234567890"
> >         default n
> >         help
> >           Say Y here if you have the right to use
> >           patent 1234567890 (the foo patent). Some
> >           countries do not recognise this patent, an
> >           educational or research exemption may apply,
> >           you may be the patent holder, the patent
> >           may have expired, or you may have aquired
> >           rights via licensing. Seek legal help if you
> >           need advice concerning your rights. If unsure,
> >           say N.
> 
> I expect this was said in jest, but it would be delightful to see this
> done for real.  To the best of my knowlege it's uncharted territory,
> so perhaps what you suggest _would_ be upheld in a court of law as
> permissible?
> 

This approach would turn Linux into proprietary software.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [OT] use of patented algorithms in the kernel ok or not?

[Jamie Lokier]

James Morris wrote:
> This approach would turn Linux into proprietary software.

You're saying a Linux kernel with _more_ capabilities that I and
everyone else outside the USA can use, learn from, modify and
distribute freely is proprietary, whereas denying me access to those
capabilities is more free?

I guess it is more free for people living within the patented economic
zones, and less free for people outside them.

To put it into perspective: I'd love for Mandrake or SuSE or Polish or
Red Flag Linux to come with a full suite of modem, DSL and wireless
drivers, and support for VFAT and Longhorn filesystems.

There's two ways to go about it:

    1. First way is we develop a common Linux kernel which everyone in
       the USA may use, even if it contains things like encryption
       which are not so legal in some other parts of the world.

       This is obviously how it's done right now.

       Mandrake, SuSE, Polish, Red Flag and everyone else outside the
       USA must apply the Big Linux Patch to build kernels which
       support all the extra devices and filesystems.

    2. Second way is to include all those extra wireless drivers
       etc. in the common kernel, but disable them somehow for USA
       users.  Note that the USA users have not lost anything.

       Distributing the code in disabled form _may_ not be legal in
       practice, I simply do not know, so maybe the second way is not
       permissible.  But if there is a chance it is permissible, don't
       you think it should be explored?

-- Jamie

Re: [OT] use of patented algorithms in the kernel ok or not?

[Xavier Bestel]

Le dim 21/12/2003 à 15:30, Jamie Lokier a écrit :
>     2. Second way is to include all those extra wireless drivers
>        etc. in the common kernel, but disable them somehow for USA
>        users.  Note that the USA users have not lost anything.

As long as no critical functionality is unaccessible to our American
friends, I'd love that.

Re: [OT] use of patented algorithms in the kernel ok or not?

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 970 bytes --]


> > I expect this was said in jest, but it would be delightful to see this
> > done for real.  To the best of my knowlege it's uncharted territory,
> > so perhaps what you suggest _would_ be upheld in a court of law as
> > permissible?
> > 
> 
> This approach would turn Linux into proprietary software.

how so?
How is adding speed improvements to the code that may not be allowed in
ONE country make linux proprietary? We can't just rip out each and every
feature that ANY goverment or country in the world declares illegal/not
allowed to be used. CONFIG_USA and the like only provide a hint/helper
for those who want to use it in geographies where certain restrictions
are imposed by law on what software is allowed to do (without paying
third parties that is).  Now of course it's a problem if the kernel
wouldn't function at all with CONFIG_USA is set (although perfectly ok
within the gpl afaics), but for additional performance improvements ?

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Stan Bubrouski]

[-- Attachment #1: Type: text/plain, Size: 1560 bytes --]

On Sun, 2003-12-21 at 09:56, Arjan van de Ven wrote:
> > > I expect this was said in jest, but it would be delightful to see this
> > > done for real.  To the best of my knowlege it's uncharted territory,
> > > so perhaps what you suggest _would_ be upheld in a court of law as
> > > permissible?
> > > 
> > 
> > This approach would turn Linux into proprietary software.
> 
> how so?
> How is adding speed improvements to the code that may not be allowed in
> ONE country make linux proprietary? We can't just rip out each and every
> feature that ANY goverment or country in the world declares illegal/not
> allowed to be used. CONFIG_USA and the like only provide a hint/helper
> for those who want to use it in geographies where certain restrictions
> are imposed by law on what software is allowed to do (without paying
> third parties that is).  Now of course it's a problem if the kernel
> wouldn't function at all with CONFIG_USA is set (although perfectly ok
> within the gpl afaics), but for additional performance improvements ?

What about the legal ramifications in the US of distributing code using
an algorithm that is covered by a patent without permission.  What are
we gonna just not distribute the kernel in the US at all?  Cause that's
the only way to safely do what you all keep blathering about without a
license.  By putting the code in the kernel you are putting us in the US
at risk, someone could argue you are giving people a means to violate a
patent in the US...not something you want to be doing!

-sb

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Helge Hafting]

On Sun, Dec 21, 2003 at 02:33:38PM -0500, Stan Bubrouski wrote:
> 
> What about the legal ramifications in the US of distributing code using
> an algorithm that is covered by a patent without permission.  What are
> we gonna just not distribute the kernel in the US at all?  Cause that's
> the only way to safely do what you all keep blathering about without a
> license.  By putting the code in the kernel you are putting us in the US
> at risk, someone could argue you are giving people a means to violate a
> patent in the US...not something you want to be doing!
> 
Hard to say, but consider this:
Something patented is _not_ a secret, and therefore not a trade secret.
Anything patented can be looked up in the patent databases by anybody.
So there cannot be any problem with distributing this patented knowledge.

Using it is another matter, but it is up to the user not to disable
CONFIG_USA within us jurisdiction.

Helge Hafting

Re: [OT] use of patented algorithms in the kernel ok or not?

[Stan Bubrouski]

[-- Attachment #1: Type: text/plain, Size: 1652 bytes --]

On Sun, 2003-12-21 at 05:53, Jamie Lokier wrote:
> Albert Cahalan wrote:
> > What about the obvious Kconfig option?
> > 
> > config PATENT_1234567890
> >         bool "Patent 1234567890"
> >         default n
> >         help
> >           Say Y here if you have the right to use
> >           patent 1234567890 (the foo patent). Some
> >           countries do not recognise this patent, an
> >           educational or research exemption may apply,
> >           you may be the patent holder, the patent
> >           may have expired, or you may have aquired
> >           rights via licensing. Seek legal help if you
> >           need advice concerning your rights. If unsure,
> >           say N.
> 
> I expect this was said in jest, but it would be delightful to see this
> done for real.  To the best of my knowlege it's uncharted territory,
> so perhaps what you suggest _would_ be upheld in a court of law as
> permissible?
<SNIP>

No No No No No...do you really think including code for a patented
algorithm(s) is a good idea?  You are still distributing the code and
allowing people to illegally use it in countries where they are not
allowed to.  In essence you are providing a catalyst for them to violate
a patent and making yourself and other liable along the way.  US law is
sick and fucked up, and if someone sues you for patent infringement
you're most likely fucked, because you can never have enough money to
defend yourself...for the sake of us stuck in this so-called free
country (though we can be arrested and jailed without trial?) please do
not include patented algoriths in Linux...

-sb

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Matthias Schniedermeyer]

On Sun, Dec 21, 2003 at 02:29:27PM -0500, Stan Bubrouski wrote:
> On Sun, 2003-12-21 at 05:53, Jamie Lokier wrote:
> > Albert Cahalan wrote:
> > > What about the obvious Kconfig option?
> > > 
> > > config PATENT_1234567890
> > >         bool "Patent 1234567890"
> > >         default n
> > >         help
> > >           Say Y here if you have the right to use
> > >           patent 1234567890 (the foo patent). Some
> > >           countries do not recognise this patent, an
> > >           educational or research exemption may apply,
> > >           you may be the patent holder, the patent
> > >           may have expired, or you may have aquired
> > >           rights via licensing. Seek legal help if you
> > >           need advice concerning your rights. If unsure,
> > >           say N.
> > 
> > I expect this was said in jest, but it would be delightful to see this
> > done for real.  To the best of my knowlege it's uncharted territory,
> > so perhaps what you suggest _would_ be upheld in a court of law as
> > permissible?
> <SNIP>
> 
> No No No No No...do you really think including code for a patented
> algorithm(s) is a good idea?  You are still distributing the code and
> allowing people to illegally use it in countries where they are not
> allowed to.  In essence you are providing a catalyst for them to violate
> a patent and making yourself and other liable along the way.  US law is
> sick and fucked up, and if someone sues you for patent infringement
> you're most likely fucked, because you can never have enough money to
> defend yourself...for the sake of us stuck in this so-called free
> country (though we can be arrested and jailed without trial?) please do
> not include patented algoriths in Linux...

The question is "What toes are OK to step onto".

e.g.
To the best of my knowledge it should be illegal to distribute 2.6
kernel in France because AFAIK it is illegal to use encryption there.
(If not France, there are other countries that fit)
(And you remember that this same problem was only resolved a few years
ago for the U.S.! Otherwise the crypto-stuff would have been in kernel
for years!)

So the only question is "Is it OK to step on the U.S. toe?".
I guess there are other countries on this small planet (>200 IIRC) where
the current linux kernel has it's "problems(tm)" here and there.





Bis denn

-- 
Real Programmers consider "what you see is what you get" to be just as 
bad a concept in Text Editors as it is in women. No, the Real Programmer
wants a "you asked for it, you got it" text editor -- complicated, 
cryptic, powerful, unforgiving, dangerous.

Re: [OT] use of patented algorithms in the kernel ok or not?

[Stan Bubrouski]

[-- Attachment #1: Type: text/plain, Size: 1555 bytes --]

On Sun, 2003-12-21 at 14:55, Matthias Schniedermeyer wrote:
> The question is "What toes are OK to step onto".
> 

I totally understand this.  To a point.

> e.g.
> To the best of my knowledge it should be illegal to distribute 2.6
> kernel in France because AFAIK it is illegal to use encryption there.
> (If not France, there are other countries that fit)

True, but that has always been the case.

> (And you remember that this same problem was only resolved a few years
> ago for the U.S.! Otherwise the crypto-stuff would have been in kernel
> for years!)
> 

This really isn't a crypto question though, and this has financial
ramifications here as well.  Violating a French law isn't as scary to me
as having to hire a patent lawyer here in the US...

> So the only question is "Is it OK to step on the U.S. toe?".
> I guess there are other countries on this small planet (>200 IIRC) where
> the current linux kernel has it's "problems(tm)" here and there.
> 

Hey I'm all for allowing the use of patented algorithms in the kernel,
but I think they should be separate trees or patches that can be applied
and hosted elsewhere, the same way crypto was afor a long time.  I think
the idea should be to step on as few toes as possible, not knowingly do
it because it can be done...that's all.  You have to remember, patents
here are frightening, and you damned well better have a lot of money if
you are going to need a patent lawyer, that is a commodity most of us
can't afford.

-sb

> 
> 
> 
> 
> Bis denn

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [OT] use of patented algorithms in the kernel ok or not?

[Francois Romieu]

Matthias Schniedermeyer <ms@citd.de> :
[...]
> e.g.
> To the best of my knowledge it should be illegal to distribute 2.6
> kernel in France because AFAIK it is illegal to use encryption there.

Bzzzt

<URL:http://www.ssi.gouv.fr/fr/reglementation/liste_entr/f28.html>

--
Ueimor

Re: [OT] use of patented algorithms in the kernel ok or not?

[Jamie Lokier]

Stan Bubrouski wrote:
> > I expect this was said in jest, but it would be delightful to see this
> > done for real.  To the best of my knowlege it's uncharted territory,
> > so perhaps what you suggest _would_ be upheld in a court of law as
> > permissible?
> 
> No No No No No...do you really think including code for a patented
> algorithm(s) is a good idea?  You are still distributing the code and
> allowing people to illegally use it in countries where they are not
> allowed to.  In essence you are providing a catalyst for them to violate
> a patent and making yourself and other liable along the way.

That is equally true if I publish a book explaining the algorithm in
great detail - enough detail that you could practically copy working
code from the book.  Yet, publishing books seems to be fine.

That's why I said it's uncharted territory.  We don't know how safe it
is to publish code that *doesn't do anything* but does embody a
patented technique *only if the recipient deliberately modifies the
code*.

Please explain the difference between publishing a book that doesn't
do anything itself, but might "catalyse" a person to using a patented
technique, and publishing source text that doesn't do anything, but
might "catalyse" a person to using a patented technique *if they
deliberately decide to infring the patent themselves*.

If anything, the book is more irresponsible because usually books
don't tell the reader about patents on the methods they describe.  On
the other hand, we are very responsible and propose to tell the reader
_exactly_ what their responsibilities are and the consequences of
their actions if they choose to modify the work.  We give them the
knowledge and the choice.

> US law is sick and fucked up, and if someone sues you for patent
> infringement you're most likely fucked, because you can never have
> enough money to defend yourself...

That's true.  And they can sue you _even if you didn't do anything
wrong_ and you're most likely fucked too.  Innocence is no excuse.

So it has little to do with obeying the law, which is totally
ambiguous in this area anyway, and a lot to do with being an
undesirable target, doesn't it?

> for the sake of us stuck in this so-called free
> country (though we can be arrested and jailed without trial?)

You can be arrested and jailed even if you _don't_ infringe any
patents, too.

You have to be pragmatic, but if you are totally ruled by fear of what
they _might_ do, you'll never do anything interesting.  So we push the
envelope a little bit and see how it works out.  See if people find it
acceptable practice, or if it's not a good time to encode that much
personal freedom and responsibility.

It's not at all clear that !CONFIG_USA || CONFIG_PATENT_nnnnnnnnnn
would be "illegal" in the USA.  As you saw from the help text, there
are many people and organisations _in the USA_ which would be permitted
to enable the options.

It's a lot like the binary modules question, only this time it's the
companies with patent portfolios that like to keep the status quo
ambiguous, because it suits their position.  We can recoil from the
ambiguity, or we can take advantage of it to produce better software.

-- Jamie

Re: [OT] use of patented algorithms in the kernel ok or not?

[John Bradford]

Quote from Jamie Lokier <jamie@shareable.org>:

> That's why I said it's uncharted territory.  We don't know how safe it
> is to publish code that *doesn't do anything* but does embody a
> patented technique *only if the recipient deliberately modifies the
> code*.

Look at the MTD code.

John.

Re: [OT] use of patented algorithms in the kernel ok or not?

[Adrian Cox]

On Mon, 2003-12-22 at 09:50, John Bradford wrote:
> Quote from Jamie Lokier <jamie@shareable.org>:
> 
> > That's why I said it's uncharted territory.  We don't know how safe it
> > is to publish code that *doesn't do anything* but does embody a
> > patented technique *only if the recipient deliberately modifies the
> > code*.
> 
> Look at the MTD code.

For examples of source code distribution in a patented area, look at
MPEG4 projects, particularly MPEG4IP.

http://mpeg4ip.sourceforge.net/ has source code under a variety of
licenses including GPL, and the front page has the following disclaimer:
"This code is not intended for end users, and does not contain
executables. Please read all the legal information to determine if it is
suitable for you."

The project was started by Cisco, who likely did some legal research
first. Cisco, however, have the resources to see off frivolous lawsuits,
while individual developers do not.

- Adrian Cox
http://www.humboldt.co.uk/

Re: [OT] use of patented algorithms in the kernel ok or not?

[James Lamanna]

On Sun, 21 Dec 2003 14:40:40 -0500 Lennert Buytenhek wrote:
> There is one already, and it's suboptimal, to say it mildly.

What algorithm does the kernel currently use for prefix-matching? I'm 
interested now...
And when you say suboptimal, what kind of difference are we talking?
O(n) vs. O(1) lookups?

James Lamanna

Re: [OT] use of patented algorithms in the kernel ok or not?

[Matti Aarnio]

On Sun, Dec 21, 2003 at 05:43:51PM -0800, James Lamanna wrote:
> On Sun, 21 Dec 2003 14:40:40 -0500 Lennert Buytenhek wrote:
> >There is one already, and it's suboptimal, to say it mildly.
> 
> What algorithm does the kernel currently use for prefix-matching? I'm 
> interested now...
> And when you say suboptimal, what kind of difference are we talking?
> O(n) vs. O(1) lookups?

(I am reading 2.6.0 kernel source)

It used to be PATRICIA -- where you have binary-searchable sub-tables,
and you look from longest mask table first to see matches. If longer
mask table does not have a match, you move up to larger entries entries.

Now things are somewhat different, and murky underneath FIB-rules.
( net/ipv4/fib_*.c )   The lowest level has fib_hash.c doing lookups
thru  fn_hash_lookup()  function.

It does use hashes, which can, perhaps, do things in speedier, if not
all that cache friendly way.   Still, when you have multiple different
size prefixes, they are all processed the same way as PATRICIA does.

Original question was aiming to run with _full_ internet routing tables
in Linux kernel.  Now _that_ can be somewhat slow, and the patented
algorithm in question is able to handle it under 12 memory lookups in
all cases, while present hash-patricia chunks away a lot more time in
pessimal case.

In normal single interface IPv4 end-node usage we have 4 route entries.
(eth0, loopback, multicast, and default -routes.)  Those should be very
quick to go thru in linear search order and be processor cache friendly.

Even with a handfull of routes (and interfaces), but relying on default-
route to handle most things, I do claim that linear (ordered by mask
specifity!) search table is fastest.(*)

*) It depends on your machine hardware details, but CPU and its associated
   caches are these days factor 100 faster, than main memory random access.
   (And the gap is growing...)

> James Lamanna

/Matti Aarnio