[B.A.T.M.A.N.] global mesh

[B.A.T.M.A.N.] global mesh

[Kosta Grammatis]

Hi Friends-
We're working on a rather ambitious initiative to build a
de-centralized network for the whole of humanity. We're collaborating
with NASA Ames, Deutsche Telekom, and others.  Our latest campaign is
to buy a satellite: http://buythissatellite.org

All that aside, the work of B.A.T.M.A.N. is incredible, from what I
read you've tackled some big problems and your technology is being
implemented in many places (our friends at Village Telco seem to be
using B.A.T.M.A.N.).

We'd like to build a satellite network that serves as a backhaul to
local de-centralized mesh networks.  Local data transactions can move
within the mesh, if data needs to be accessed from further away, they
switch to the satellite network. An ambitious addition to this idea is
to allow each device on the mesh to act as a piece of a phase array
antenna.

I personally understand how challenging this may be, and my expertise
is (very) limited.  Is this technically possible with technology
available today?  What would you recommend to get this done and what
can we expect in terms of an end user experience?
I appreciate your time and expertise. I believe this is the ultimate
end goal of B.A.T.M.A.N, perhaps we can work on this together.

-Kosta
--
http://iamkosta.org

Re: [B.A.T.M.A.N.] global mesh

[Marek Lindner]

Hi,

> We'd like to build a satellite network that serves as a backhaul to
> local de-centralized mesh networks.  Local data transactions can move
> within the mesh, if data needs to be accessed from further away, they
> switch to the satellite network. An ambitious addition to this idea is
> to allow each device on the mesh to act as a piece of a phase array
> antenna.
> 
> I personally understand how challenging this may be, and my expertise
> is (very) limited.  Is this technically possible with technology
> available today?  What would you recommend to get this done and what
> can we expect in terms of an end user experience?

building decentralized local networks with a shared internet connection is the 
primary use case of batman today, therefore I don't really get your question.
Can you provide specific info on what you have in mind ?

Cheers,
Marek

Re: [B.A.T.M.A.N.] global mesh

[Kosta -- A Human Right]

Thanks for the response-

Can B.A.T.M.A.N. scale to millions of users? What are the limitations
of B.A.T.M.A.N. in this regard? Where does it excel?



On Mon, Nov 29, 2010 at 1:58 PM, Marek Lindner <lindner_marek@yahoo.de> wrote:
>
> Hi,
>
>> We'd like to build a satellite network that serves as a backhaul to
>> local de-centralized mesh networks.  Local data transactions can move
>> within the mesh, if data needs to be accessed from further away, they
>> switch to the satellite network. An ambitious addition to this idea is
>> to allow each device on the mesh to act as a piece of a phase array
>> antenna.
>>
>> I personally understand how challenging this may be, and my expertise
>> is (very) limited.  Is this technically possible with technology
>> available today?  What would you recommend to get this done and what
>> can we expect in terms of an end user experience?
>
> building decentralized local networks with a shared internet connection is the
> primary use case of batman today, therefore I don't really get your question.
> Can you provide specific info on what you have in mind ?
>
> Cheers,
> Marek
>



-- 
http://iamkosta.org

Re: [B.A.T.M.A.N.] global mesh

[Michael van der Kolff]

The answer to "millions of users" simply depends on the stability of
those networks.  It is perfectly possible to have different "BATMAN
networks" and perform routing between those - that's what I stated in
the answer to your first email.

Of course, those it is perfectly possible to set up obvious cases
where BATMAN scales to "millions of users" - half of them are behind
one BATMAN router, and the other half are behind another - then there
are only two routing nodes, and very little work :P  Of course, that
might not be useful in practice...  Seriously, I suggest you do some
of your own reading into how BATMAN works, and how other mesh/P2P
routing schemes work, and why they have different scalability
profiles.  From a scalability perspective, the interesting number
isn't the number of users, but rather the number of nodes involved in
routing decisions, and how mobile they are.  In the most widely
deployed networking schemes (current mobile phone networks), we have
static network elements, with an explicit handover procedure between
different stations for end-user equipment.  End-user equipment under
those schemes doesn't get involved in routing decisions - that's why
it is not a mesh network (along with the fact that those towers
typically have a very explicit idea of where they route calls & data
sessions to).

Just go and type "mesh routing scalability" into Google Scholar and
you should be much better informed on the subject.

Cheers,

Michael

On Tue, Nov 30, 2010 at 5:12 PM, Kosta -- A Human Right
<kosta@ahumanright.org> wrote:
> Thanks for the response-
>
> Can B.A.T.M.A.N. scale to millions of users? What are the limitations
> of B.A.T.M.A.N. in this regard? Where does it excel?
>
>
>
> On Mon, Nov 29, 2010 at 1:58 PM, Marek Lindner <lindner_marek@yahoo.de> wrote:
>>
>> Hi,
>>
>>> We'd like to build a satellite network that serves as a backhaul to
>>> local de-centralized mesh networks.  Local data transactions can move
>>> within the mesh, if data needs to be accessed from further away, they
>>> switch to the satellite network. An ambitious addition to this idea is
>>> to allow each device on the mesh to act as a piece of a phase array
>>> antenna.
>>>
>>> I personally understand how challenging this may be, and my expertise
>>> is (very) limited.  Is this technically possible with technology
>>> available today?  What would you recommend to get this done and what
>>> can we expect in terms of an end user experience?
>>
>> building decentralized local networks with a shared internet connection is the
>> primary use case of batman today, therefore I don't really get your question.
>> Can you provide specific info on what you have in mind ?
>>
>> Cheers,
>> Marek
>>
>
>
>
> --
> http://iamkosta.org
>

Re: [B.A.T.M.A.N.] global mesh

[Marek Lindner]

On Tuesday 30 November 2010 07:12:21 Kosta -- A Human Right wrote:
> Can B.A.T.M.A.N. scale to millions of users? What are the limitations
> of B.A.T.M.A.N. in this regard? Where does it excel?

A single mesh cloud consisting of millions of mesh nodes is neither feasible 
nor desirable. Each mesh node is announcing itself and routing information 
about the nodes "behind it". Obviously, the protocol overhead grows up to a 
point where the protocol traffic eats up all available bandwidth.
On the other hand, mesh protocols inherently rely on trust. Each node trusts 
its neighbor nodes that they send reliable routing information. As in real 
life this trust does not scale either. 

Can mesh technology be used to build local inexpensive networks connected to a 
"backbone link" (e.g. satellite) to serve millions of users ? Certainly! That 
is what villagetelco / Freifunk / open-mesh.com / etc are working on.

Regards,
Marek

Re: [B.A.T.M.A.N.] global mesh

[Michael van der Kolff]

It is in fact feasible to have thousands of mesh nodes -
http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing gives
a real model for something like that.  Linyphi gives a real model for
that - embed a MAC address into subnet address, and get routes to your
immediate successor, 2nd node, 4th node, etc, and forward packets to
the node closest numerically to the destination while still being
under it.  Of course, Linyphi is hardly production ready - more a
proof of concept.

Cheers,

Michael

On Wed, Dec 1, 2010 at 1:42 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> On Tuesday 30 November 2010 07:12:21 Kosta -- A Human Right wrote:
>> Can B.A.T.M.A.N. scale to millions of users? What are the limitations
>> of B.A.T.M.A.N. in this regard? Where does it excel?
>
> A single mesh cloud consisting of millions of mesh nodes is neither feasible
> nor desirable. Each mesh node is announcing itself and routing information
> about the nodes "behind it". Obviously, the protocol overhead grows up to a
> point where the protocol traffic eats up all available bandwidth.
> On the other hand, mesh protocols inherently rely on trust. Each node trusts
> its neighbor nodes that they send reliable routing information. As in real
> life this trust does not scale either.
>
> Can mesh technology be used to build local inexpensive networks connected to a
> "backbone link" (e.g. satellite) to serve millions of users ? Certainly! That
> is what villagetelco / Freifunk / open-mesh.com / etc are working on.
>
> Regards,
> Marek
>

Re: [B.A.T.M.A.N.] global mesh

[Marek Lindner]

On Tuesday 30 November 2010 15:55:16 Michael van der Kolff wrote:
> It is in fact feasible to have thousands of mesh nodes -
> http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing gives
> a real model for something like that.  Linyphi gives a real model for
> that - embed a MAC address into subnet address, and get routes to your
> immediate successor, 2nd node, 4th node, etc, and forward packets to
> the node closest numerically to the destination while still being
> under it.  Of course, Linyphi is hardly production ready - more a
> proof of concept.

Let me rephrase then: I don't know of any mesh protocol that is being used in 
real world deployments and scales up to millions of nodes.

If we leave the realm of working implementations I'd like to add Netsukuku to 
the list of endlessly scalable mesh protocols. I quote from their FAQ:

It [Netsukuku] can be used to build a world-wide distributed, fault-tolerant, 
anonymous, and censorship-immune network, fully independent from the Internet. 
[..]
The number of interconnected nodes can grow endlessly.

Cheers,
Marek

Re: [B.A.T.M.A.N.] global mesh

[Kosta -- A Human Right]

Are those protocols simply theoretical? Or could they work if someone
tried them?

-K

On Tue, Nov 30, 2010 at 7:10 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> On Tuesday 30 November 2010 15:55:16 Michael van der Kolff wrote:
>> It is in fact feasible to have thousands of mesh nodes -
>> http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing gives
>> a real model for something like that.  Linyphi gives a real model for
>> that - embed a MAC address into subnet address, and get routes to your
>> immediate successor, 2nd node, 4th node, etc, and forward packets to
>> the node closest numerically to the destination while still being
>> under it.  Of course, Linyphi is hardly production ready - more a
>> proof of concept.
>
> Let me rephrase then: I don't know of any mesh protocol that is being used in
> real world deployments and scales up to millions of nodes.
>
> If we leave the realm of working implementations I'd like to add Netsukuku to
> the list of endlessly scalable mesh protocols. I quote from their FAQ:
>
> It [Netsukuku] can be used to build a world-wide distributed, fault-tolerant,
> anonymous, and censorship-immune network, fully independent from the Internet.
> [..]
> The number of interconnected nodes can grow endlessly.
>
> Cheers,
> Marek
>



-- 
http://iamkosta.org

Re: [B.A.T.M.A.N.] global mesh

[Michael van der Kolff]

They are not theoretical, just not as production hardened as BATMAN.
Which is to say, finding small-time implementations of them isn't too
hard - they do have working code.  But their code runs on top of the
Click routing system, which will never find much acceptance within the
Linux kernel community due to its use of C++ (albeit with exceptions &
other things stripped).  In short, they have working code, but it is a
proof of concept.  No one has actually got a real 125,000 node system
working, but the simulations of the routing protocol do make that
prediction, yes.

"Real world deployments" is always a tricky and nebulous concept.
BATMAN has real world deployments due to Freifunk & other initiatives,
who naturally favour code that has a real chance of being accepted
into the kernel.  Not using C++ is good for kernel acceptance.

But yes, there have been some honours theses written around
small-scale deployments with extensions to do things like hash-based
lookup of names (compute the hash and make the routing protocol stop
when its successor is greater than the hash value, instead of the IPv6
behaviour which is an ICMPv6 response...)

For more information, google Linyphi.  Or, indeed, netsukuku.  But
seriously, the point is mesh networks are an open research topic, and
I should imagine that many more PhDs will come out of this field - but
BATMAN is very much focussed on reduction to practice - making the
current ideas work as best as they can - which is why it is suitable
for the networks it has been deployed into.

Cheers,

Michael

On Wed, Dec 1, 2010 at 2:18 AM, Kosta -- A Human Right
<kosta@ahumanright.org> wrote:
> Are those protocols simply theoretical? Or could they work if someone
> tried them?
>
> -K
>
> On Tue, Nov 30, 2010 at 7:10 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
>> On Tuesday 30 November 2010 15:55:16 Michael van der Kolff wrote:
>>> It is in fact feasible to have thousands of mesh nodes -
>>> http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing gives
>>> a real model for something like that.  Linyphi gives a real model for
>>> that - embed a MAC address into subnet address, and get routes to your
>>> immediate successor, 2nd node, 4th node, etc, and forward packets to
>>> the node closest numerically to the destination while still being
>>> under it.  Of course, Linyphi is hardly production ready - more a
>>> proof of concept.
>>
>> Let me rephrase then: I don't know of any mesh protocol that is being used in
>> real world deployments and scales up to millions of nodes.
>>
>> If we leave the realm of working implementations I'd like to add Netsukuku to
>> the list of endlessly scalable mesh protocols. I quote from their FAQ:
>>
>> It [Netsukuku] can be used to build a world-wide distributed, fault-tolerant,
>> anonymous, and censorship-immune network, fully independent from the Internet.
>> [..]
>> The number of interconnected nodes can grow endlessly.
>>
>> Cheers,
>> Marek
>>
>
>
>
> --
> http://iamkosta.org
>

Re: [B.A.T.M.A.N.] global mesh

[Michael van der Kolff]

And just reiterating:  BATMAN works just fine for larger networks,
just so long as you're happy to use BGP between disparate BATMAN
islands.  But first, ask yourself whether you really need a network
with 500 routers involved in decision making on that little piece of
paradise...

Cheers,

Michael

On Wed, Dec 1, 2010 at 2:52 AM, Michael van der Kolff
<mvanderkolff@gmail.com> wrote:
> They are not theoretical, just not as production hardened as BATMAN.
> Which is to say, finding small-time implementations of them isn't too
> hard - they do have working code.  But their code runs on top of the
> Click routing system, which will never find much acceptance within the
> Linux kernel community due to its use of C++ (albeit with exceptions &
> other things stripped).  In short, they have working code, but it is a
> proof of concept.  No one has actually got a real 125,000 node system
> working, but the simulations of the routing protocol do make that
> prediction, yes.
>
> "Real world deployments" is always a tricky and nebulous concept.
> BATMAN has real world deployments due to Freifunk & other initiatives,
> who naturally favour code that has a real chance of being accepted
> into the kernel.  Not using C++ is good for kernel acceptance.
>
> But yes, there have been some honours theses written around
> small-scale deployments with extensions to do things like hash-based
> lookup of names (compute the hash and make the routing protocol stop
> when its successor is greater than the hash value, instead of the IPv6
> behaviour which is an ICMPv6 response...)
>
> For more information, google Linyphi.  Or, indeed, netsukuku.  But
> seriously, the point is mesh networks are an open research topic, and
> I should imagine that many more PhDs will come out of this field - but
> BATMAN is very much focussed on reduction to practice - making the
> current ideas work as best as they can - which is why it is suitable
> for the networks it has been deployed into.
>
> Cheers,
>
> Michael
>
> On Wed, Dec 1, 2010 at 2:18 AM, Kosta -- A Human Right
> <kosta@ahumanright.org> wrote:
>> Are those protocols simply theoretical? Or could they work if someone
>> tried them?
>>
>> -K
>>
>> On Tue, Nov 30, 2010 at 7:10 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
>>> On Tuesday 30 November 2010 15:55:16 Michael van der Kolff wrote:
>>>> It is in fact feasible to have thousands of mesh nodes -
>>>> http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing gives
>>>> a real model for something like that.  Linyphi gives a real model for
>>>> that - embed a MAC address into subnet address, and get routes to your
>>>> immediate successor, 2nd node, 4th node, etc, and forward packets to
>>>> the node closest numerically to the destination while still being
>>>> under it.  Of course, Linyphi is hardly production ready - more a
>>>> proof of concept.
>>>
>>> Let me rephrase then: I don't know of any mesh protocol that is being used in
>>> real world deployments and scales up to millions of nodes.
>>>
>>> If we leave the realm of working implementations I'd like to add Netsukuku to
>>> the list of endlessly scalable mesh protocols. I quote from their FAQ:
>>>
>>> It [Netsukuku] can be used to build a world-wide distributed, fault-tolerant,
>>> anonymous, and censorship-immune network, fully independent from the Internet.
>>> [..]
>>> The number of interconnected nodes can grow endlessly.
>>>
>>> Cheers,
>>> Marek
>>>
>>
>>
>>
>> --
>> http://iamkosta.org
>>
>

Re: [B.A.T.M.A.N.] global mesh

[L. Aaron Kaplan]

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



Kosta, some remarks upfront:

There *are* alredy mesh networks on satellites in place. 
http://en.wikipedia.org/wiki/Iridium_satellite_constellation
http://en.wikipedia.org/wiki/Wireless_mesh_network
 ("been there, done that, let's move to the next topic" ;-))


On Nov 30, 2010, at 4:55 PM, Michael van der Kolff wrote:

> And just reiterating:  BATMAN works just fine for larger networks,
> just so long as you're happy to use BGP between disparate BATMAN
> islands.  But first, ask yourself whether you really need a network
> with 500 routers involved in decision making on that little piece of
> paradise...
> 

500 nodes can be easily achieved. Even the "small" Freifunk networks (and Funkfeuer.at networks) 
get bigger than 500 nodes (and yes, they run OLSR and that provably scales up to n * 1000 nodes on 200Mhz devices).
So, yes, IMHO it definitely makes sense for a MANET protocol to support more than 500 nodes in a single mesh cloud.
AWMN and Guifi.net have 5000+ and 10000+ nodes, so... it is a real issue.


If you want, you can then *always* make a two layered approach (BGP + {OLSR,OSPF,MANET-OSPF,BATMAN,TORA,BABEL,HSLR, even RIPv2,... you name it, there are hundreds of MANET protocols out there}) and in fact this is the usual best practice approach to networking. Almost all ISPs that I know do it this way. Interior routing protocol and exterior (BGP). No problem with that.

I even know of one WISP who uses no routing protocol at all, he just uses a pure switched Wi-Fi network for his customers.  And you won't believe it - he is perfectly happy. But he spends a great deal of time to optimize layer 1 (the actual links). Also a possibility - maybe even a pretty good solution ;-))
(ok, but this guy does not have more than 1000 customers for sure)

a.

PS: My gut feeling says netsukkuku always talks about endless scalability but they never actually showed something which works in practice, or did they? can you update me on any real world netsukkuku deployment?




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

Re: [B.A.T.M.A.N.] global mesh

[RHS Linux User]

Hi,

   VillageTelco is interesting to watch grow. More like Linux and
the Bazaar :).

   A boss of mine put it nicely: "I must hurry for there go my people!"

   Wiz


On Fri, 3 Dec 2010, L. Aaron Kaplan wrote:

> 
> 
> Kosta, some remarks upfront:
> 
> There *are* alredy mesh networks on satellites in place. 
> http://en.wikipedia.org/wiki/Iridium_satellite_constellation
> http://en.wikipedia.org/wiki/Wireless_mesh_network
>  ("been there, done that, let's move to the next topic" ;-))
> 
> 
> On Nov 30, 2010, at 4:55 PM, Michael van der Kolff wrote:
> 
> > And just reiterating:  BATMAN works just fine for larger networks,
> > just so long as you're happy to use BGP between disparate BATMAN
> > islands.  But first, ask yourself whether you really need a network
> > with 500 routers involved in decision making on that little piece of
> > paradise...
> > 
> 
> 500 nodes can be easily achieved. Even the "small" Freifunk networks (and Funkfeuer.at networks) 
> get bigger than 500 nodes (and yes, they run OLSR and that provably scales up to n * 1000 nodes on 200Mhz devices).
> So, yes, IMHO it definitely makes sense for a MANET protocol to support more than 500 nodes in a single mesh cloud.
> AWMN and Guifi.net have 5000+ and 10000+ nodes, so... it is a real issue.
> 
> 
> If you want, you can then *always* make a two layered approach (BGP + {OLSR,OSPF,MANET-OSPF,BATMAN,TORA,BABEL,HSLR, even RIPv2,... you name it, there are hundreds of MANET protocols out there}) and in fact this is the usual best practice approach to networking. Almost all ISPs that I know do it this way. Interior routing protocol and exterior (BGP). No problem with that.
> 
> I even know of one WISP who uses no routing protocol at all, he just uses a pure switched Wi-Fi network for his customers.  And you won't believe it - he is perfectly happy. But he spends a great deal of time to optimize layer 1 (the actual links). Also a possibility - maybe even a pretty good solution ;-))
> (ok, but this guy does not have more than 1000 customers for sure)
> 
> a.
> 
> PS: My gut feeling says netsukkuku always talks about endless scalability but they never actually showed something which works in practice, or did they? can you update me on any real world netsukkuku deployment?
> 
> 
> 
> 

Re: [B.A.T.M.A.N.] global mesh

[Michael van der Kolff]

On Tue, Nov 30, 2010 at 3:54 AM, Kosta Grammatis <kosta@iamkosta.org> wrote:
> Hi Friends-
> We're working on a rather ambitious initiative to build a
> de-centralized network for the whole of humanity. We're collaborating
> with NASA Ames, Deutsche Telekom, and others.  Our latest campaign is
> to buy a satellite: http://buythissatellite.org
>
> All that aside, the work of B.A.T.M.A.N. is incredible, from what I
> read you've tackled some big problems and your technology is being
> implemented in many places (our friends at Village Telco seem to be
> using B.A.T.M.A.N.).
>
> We'd like to build a satellite network that serves as a backhaul to
> local de-centralized mesh networks.  Local data transactions can move
> within the mesh, if data needs to be accessed from further away, they
> switch to the satellite network. An ambitious addition to this idea is
> to allow each device on the mesh to act as a piece of a phase array
> antenna.
>
A phase array antenna requires that each of the pieces of the array
have very low-latency, low jitter communications.  BATMAN is unlikely
to supply that.

BATMAN's approach to routing is not suitable for very large networks
(more than 10^3 routing nodes).  That said, if the backhaul network
setup is stable, you could use BGP between individual BATMAN islands.
If you need a very large network with moving nodes, you may need an
approach like SSR, or other approaches - but they are very much the
subject of research.

> I personally understand how challenging this may be, and my expertise
> is (very) limited.  Is this technically possible with technology
> available today?  What would you recommend to get this done and what
> can we expect in terms of an end user experience?
> I appreciate your time and expertise. I believe this is the ultimate
> end goal of B.A.T.M.A.N, perhaps we can work on this together.
>
> -Kosta
> --
> http://iamkosta.org
>