Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Marcos]

[Fwd from [linux-kernel], thought I'd follow the suggestion to post
this to netdev:]

After seeing some attention this idea generated in the linux press,
I'd like to re-visit this suggestion.  I'm a nobody on this list, but
do have some expertise in complex systems (i.e. complexity theory).

The Kademlia protocol is simple: it has four commands (and won't
likely grow more): PING, STORE, FIND_NODE, FIND_VALUE.
It is computationally effortless: it generates random node id's and
computes distance on a distributed hash table using an simple XOR
function.
It is (probably optimally) efficient:  O(log(n)) for n nodes.
Ultimately, it could increase security: by creating a system for
tracking trusted peers, a new topology of content-sharing can be
generated.

[From the (kademlia) wikipedia article]: "The first generation peer-to-peer file
sharing networks, such as Napster, relied on a central database to
co-ordinate look ups on the network. Second generation peer-to-peer
networks, such as Gnutella, used flooding to locate files, searching
every node on the network. Third generation peer-to-peer networks use
Distributed Hash Tables to look up files in the network. Distributed
hash tables store resource locations throughout the network. A major
criterion for these protocols is locating the desired nodes quickly."

Putting a simple, but robust p2p network layer in the kernel offers
several novel and very interesting possibilities.

1. Cutting-edge cool factor:  It would put linux way ahead of the
net's general evolution to an full-fledged "Internet Operating
System".  The world needs an open source solution over Google's,
Microsoft's (or any other's) attempt to create such a solution.
Dismiss any attempts to see such a request as warez-d00ds looking to
make a more efficient pirating network.

2. Lower maintenance:  Though unification, it would simplify the many
(currently disparate) linux solutions for large-scale aggregation of
computational and storage resources that are distributed across many
machines.  Additionally, NFS (the networking protocol that *IS* in the
kernel) is stale, has high administrative and operational overhead,
and is not made to scale to millions of shared nodes in a graph
topology.

3. Excite a new wave of Linux development:  90% of linux machines are
on the net, but don't utilize the real value of peer connectivity
(which can grow profoundly faster than Metcalf's N^2 "value of the
network" law).  Putting p2p in kernel space communicates to every
developer that linux is serious about creating a unified and complete
solution for creating such a infrastructure.  Let the cloud
applications and such be in user space, but keep the main
connection-tracking in the kernel.   Such a move would make for many
(unforeseeable) complex emergent behaviors and optimizations to arise
-- see Wikipedia on Reed's Law for a sense of it (to wit: "even if the
utility of groups available to be joined is very small on a peer-group
basis, eventually the network effect of potential group membership ...
dominate[s] the overall economics of the system").

Consider, for example, social networking: it is an inherently p2p
structure and is lying in wait to explode the next wave of internet
evolution and new-value generation.  There's no doubt that this is the
trend of the future -- best that open source be there first.  Users
are creating value on their machines *every day*, but there's little
infrastructure to take advantage of it.  Currently, it's either lost
or exploited.  Solution and vision trajectories:  Diaspora comes to
mind, mash-up applications like Photosynth aggregating the millions of
photos on people's computers (see the TED.com presentation), open
currencies and meritocratic market systems using such a "meta-linux"
as a backbone, etc. -- whole new governance models for sharing content
would undoubtedly arise.  HTTP/HTML is too much of an all-or-nothing
and coarse approach to organizing the world's content.  The net needs
a backbone for sharing personal content and grouping it to create new
abstractions and wealth.  See pangaia.sourceforge.net for some of
ideas I've personally been developing.

Anyway, I'm with hp_fk on this one.  Ignore at the peril and risk of
the future...  :)

marcos

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Eric Dumazet]

Le dimanche 14 novembre 2010 à 00:21 -0700, Marcos a écrit :
> [Fwd from [linux-kernel], thought I'd follow the suggestion to post
> this to netdev:]
> 
> After seeing some attention this idea generated in the linux press,
> I'd like to re-visit this suggestion.  I'm a nobody on this list, but
> do have some expertise in complex systems (i.e. complexity theory).
> 
> The Kademlia protocol is simple: it has four commands (and won't
> likely grow more): PING, STORE, FIND_NODE, FIND_VALUE.
> It is computationally effortless: it generates random node id's and
> computes distance on a distributed hash table using an simple XOR
> function.
> It is (probably optimally) efficient:  O(log(n)) for n nodes.
> Ultimately, it could increase security: by creating a system for
> tracking trusted peers, a new topology of content-sharing can be
> generated.
> 
> [From the (kademlia) wikipedia article]: "The first generation peer-to-peer file
> sharing networks, such as Napster, relied on a central database to
> co-ordinate look ups on the network. Second generation peer-to-peer
> networks, such as Gnutella, used flooding to locate files, searching
> every node on the network. Third generation peer-to-peer networks use
> Distributed Hash Tables to look up files in the network. Distributed
> hash tables store resource locations throughout the network. A major
> criterion for these protocols is locating the desired nodes quickly."
> 
> Putting a simple, but robust p2p network layer in the kernel offers
> several novel and very interesting possibilities.
> 
> 1. Cutting-edge cool factor:  It would put linux way ahead of the
> net's general evolution to an full-fledged "Internet Operating
> System".  The world needs an open source solution over Google's,
> Microsoft's (or any other's) attempt to create such a solution.
> Dismiss any attempts to see such a request as warez-d00ds looking to
> make a more efficient pirating network.
> 
> 2. Lower maintenance:  Though unification, it would simplify the many
> (currently disparate) linux solutions for large-scale aggregation of
> computational and storage resources that are distributed across many
> machines.  Additionally, NFS (the networking protocol that *IS* in the
> kernel) is stale, has high administrative and operational overhead,
> and is not made to scale to millions of shared nodes in a graph
> topology.
> 
> 3. Excite a new wave of Linux development:  90% of linux machines are
> on the net, but don't utilize the real value of peer connectivity
> (which can grow profoundly faster than Metcalf's N^2 "value of the
> network" law).  Putting p2p in kernel space communicates to every
> developer that linux is serious about creating a unified and complete
> solution for creating such a infrastructure.  Let the cloud
> applications and such be in user space, but keep the main
> connection-tracking in the kernel.   Such a move would make for many
> (unforeseeable) complex emergent behaviors and optimizations to arise
> -- see Wikipedia on Reed's Law for a sense of it (to wit: "even if the
> utility of groups available to be joined is very small on a peer-group
> basis, eventually the network effect of potential group membership ...
> dominate[s] the overall economics of the system").
> 
> Consider, for example, social networking: it is an inherently p2p
> structure and is lying in wait to explode the next wave of internet
> evolution and new-value generation.  There's no doubt that this is the
> trend of the future -- best that open source be there first.  Users
> are creating value on their machines *every day*, but there's little
> infrastructure to take advantage of it.  Currently, it's either lost
> or exploited.  Solution and vision trajectories:  Diaspora comes to
> mind, mash-up applications like Photosynth aggregating the millions of
> photos on people's computers (see the TED.com presentation), open
> currencies and meritocratic market systems using such a "meta-linux"
> as a backbone, etc. -- whole new governance models for sharing content
> would undoubtedly arise.  HTTP/HTML is too much of an all-or-nothing
> and coarse approach to organizing the world's content.  The net needs
> a backbone for sharing personal content and grouping it to create new
> abstractions and wealth.  See pangaia.sourceforge.net for some of
> ideas I've personally been developing.
> 
> Anyway, I'm with hp_fk on this one.  Ignore at the peril and risk of
> the future...  :)
> 

I have no idea why and how kademlia would be added to "linux kernel"

Its a protocol based on UDP, and probably already done on userland.

What am I missing ?

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Marcos]

> I have no idea why and how kademlia would be added to "linux kernel"
>
> Its a protocol based on UDP, and probably already done on userland.
>
> What am I missing ?

The idea is to tightly couple it to the operating system to create a
sort of "super operating system" that is seamless to the application
layers above.  Just like memory stores are tightly integrated as to be
unnoticeable....

marcos

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Eric Dumazet]

Le dimanche 14 novembre 2010 à 02:14 -0700, Marcos a écrit :
> > I have no idea why and how kademlia would be added to "linux kernel"
> >
> > Its a protocol based on UDP, and probably already done on userland.
> >
> > What am I missing ?
> 
> The idea is to tightly couple it to the operating system to create a
> sort of "super operating system" that is seamless to the application
> layers above.  Just like memory stores are tightly integrated as to be
> unnoticeable....
> 

But we dont want a "super operating system". We want a good one.

Memory stores done in userland are as fast as memory stores done in
kernel.

Once you need to access files, perform complex searches, timers,
logging, and all the stuff, you really want to do it from userland, in
high level language that many programmers master, or get something that
is too complex/buggy.

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Marcos]

[Eric Dumazet wrote:]
> But we dont want a "super operating system". We want a good one.

Yes, well you have that, I think, speaking at the kernel level.  But
the thing is, people are building tools that mimic such anyway, and
the next wave of new value will be found there.

> Memory stores done in userland are as fast as memory stores done in
> kernel.

Really? And how about the abstraction-level?  because that will either
make it lucrative or not for developers to build applications for
it.....

> Once you need to access files, perform complex searches, timers,
> logging, and all the stuff, you really want to do it from userland, in
> high level language that many programmers master, or get something that
> is too complex/buggy.

Yes, of course, all that will have to be considered.   But I'm
suggesting that such a move is an investment in the future, that the
the number of machines that will want or request peer-2-peer
connectivity will (or should) only increase.  Done right, such a move
should *simplify* things.  We're biased to think in centralized ways
because of the centuries-old history of *who* has the resources.  But
as networking, computation, and storage become commodified further,
whole new topologies for the *right* architecture become available.
The idea of "the OS" itself morphs.   And the *only* way maximize the
value of the network is to make it easy to connect and communicate
between peers -- what happens after that is so radical it can hardly
be speculated because it gets into the realm of emergent complexity.
Again, I refer you to Reed's law on the value of such networks.

marcos

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Honglei Cong]

On Tue, Nov 16, 2010 at 2:21 PM, Marcos <stalkingtime@gmail.com> wrote:
> [Eric Dumazet wrote:]
>> But we dont want a "super operating system". We want a good one.
>
> Yes, well you have that, I think, speaking at the kernel level.  But
> the thing is, people are building tools that mimic such anyway, and
> the next wave of new value will be found there.
>
>> Memory stores done in userland are as fast as memory stores done in
>> kernel.
>
> Really? And how about the abstraction-level?  because that will either
> make it lucrative or not for developers to build applications for
> it.....
>
>> Once you need to access files, perform complex searches, timers,
>> logging, and all the stuff, you really want to do it from userland, in
>> high level language that many programmers master, or get something that
>> is too complex/buggy.
>
> Yes, of course, all that will have to be considered.   But I'm
> suggesting that such a move is an investment in the future, that the
> the number of machines that will want or request peer-2-peer
> connectivity will (or should) only increase.  Done right, such a move
> should *simplify* things.  We're biased to think in centralized ways
> because of the centuries-old history of *who* has the resources.  But
> as networking, computation, and storage become commodified further,
> whole new topologies for the *right* architecture become available.
> The idea of "the OS" itself morphs.   And the *only* way maximize the
Agree with u.  But 'kernel' is not.

> value of the network is to make it easy to connect and communicate
> between peers -- what happens after that is so radical it can hardly
> be speculated because it gets into the realm of emergent complexity.
> Again, I refer you to Reed's law on the value of such networks.
>
> marcos
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Marcos]

>> Yes, of course, all that will have to be considered.   But I'm
>> suggesting that such a move is an investment in the future, that the
>> the number of machines that will want or request peer-2-peer
>> connectivity will (or should) only increase.  Done right, such a move
>> should *simplify* things.  We're biased to think in centralized ways
>> because of the centuries-old history of *who* has the resources.  But
>> as networking, computation, and storage become commodified further,
>> whole new topologies for the *right* architecture become available.
>> The idea of "the OS" itself morphs.   And the *only* way maximize the
> Agree with u.  But 'kernel' is not.

...Consider a unified model of two orthogonal resources: processor --
memory.  In theory such a unified model should be realizable.  For
example, if we fix the processor side (say the user's machine), then
you can move around the memory side, unify different memory stores:
cache, RAM, local HD, Networked file storage (naturally logarithmic
scaling).  There's no more need to "install applications":  it's all
installed out there somewhere (probably from the same place where it
was created), you just need to "page it in".  Create an abstract,
user-controlled, peer grouping model that allows arbitrary "trust (or
privacy) groups" where "node discovery" (say new annoucements) and
"shared memory" is allowed and watch the Social Linux Network Brain
evolve.  (I better not even mention an integrated voting model
yet....)

Too idealistic?

marcos
pangaia.sourceforge.net

Re: Fwd: a Great Idea - include Kademlia networking protocol in kernel -- REVISITED

[Chris Snook]

On Sun, Nov 14, 2010 at 4:14 AM, Marcos <stalkingtime@gmail.com> wrote:
>> I have no idea why and how kademlia would be added to "linux kernel"
>>
>> Its a protocol based on UDP, and probably already done on userland.
>>
>> What am I missing ?
>
> The idea is to tightly couple it to the operating system to create a
> sort of "super operating system" that is seamless to the application
> layers above.  Just like memory stores are tightly integrated as to be
> unnoticeable....

According to Google, you're not an experienced kernel developer, so
let me explain what happens when you take userspace code and implement
it in the kernel:

1) You restrict development of the feature to a specialized subset of C only.
2) You lose the simple filesystem interface enjoyed by userspace.
3) You lose the simple memory allocation enjoyed by userspace.
4) You lose the BSD network socket interface enjoyed by userspace.
5) You lose the ability to call recursive functions such as quicksort.
6) You lose the ability to call nearly every library ever written.
7) You freeze your ABI, making it much more difficult to fix your
mistakes without breaking huge amounts of userspace code, which pisses
off users, though they'll also be pissed if you *don't* fix your
mistakes.
8) You make debugging 10x harder.
9) You piss off your users 100x more when it breaks.
10) You make any security holes in your code 1000x worse.

There are plenty more drawbacks, but I think I've made the point.  We
don't put things in the kernel unless userspace is inadequate.  In
fact, we've done a lot of work over the years to provide kernel
infrastructure to allow us to move things *out* of the kernel and into
userspace.  If you think this feature would benefit from
filesystem-level integration, try implementing it as a FUSE module.
At least then you'll be able to use libraries and the language of your
choice.  None of the drawbacks of FUSE relative to the core kernel
apply in this case, so if it doesn't work with FUSE, it certainly
won't work in the kernel.

-- Chris