[B.A.T.M.A.N.] IP from MAC

[B.A.T.M.A.N.] IP from MAC

[Lick A Prize]

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

In the ROBIN address allocation described here http://robin-mesh.wik.is/Documentation/Router_Configuring/Advanced_Configuration/Robin_IP_Space I'm curious how collisions are avoided.

If you generate IP 5.dd:ee:ff from aa:bb:cc:dd:ee:ff won't you get a collision if you other devices with MACs ending in dd:ee:ff like aa:aa:cc:dd:ee:ff, aa:aa:aa:dd:ee:ff, and so on.

[-- Attachment #2: Type: text/html, Size: 1127 bytes --]

Re: [B.A.T.M.A.N.] IP from MAC

[Gustavo Lindberg]

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

2009/9/16 Lick A Prize <lick.prize@gmail.com>

>  In the ROBIN address allocation described here
> http://robin-mesh.wik.is/Documentation/Router_Configuring/Advanced_Configuration/Robin_IP_SpaceI'm curious how collisions are avoided.
>
> If you generate IP 5.dd:ee:ff from aa:bb:cc:dd:ee:ff won't you get a
> collision if you other devices with MACs ending in dd:ee:ff like
> aa:aa:cc:dd:ee:ff, aa:aa:aa:dd:ee:ff, and so on.
>

What is the occurrence probability of "r"  MAC-Adress twon agree on their
last two bytes?

This is similar to the birthday paradox: At a meeting of r> 2 people which
is the number of people needed for the probability that two men have same
birthday sould be 99%? The solution is in many books and that can view at:

http://en.wikipedia.org/wiki/Birthday_problem

Then, At a meeting of 60 people there is the 99% probability  of the least
two men have a  birthday the same day. So,, Similarly to the case of
MAC-Adress is:

P(r)=1-65536!/(65536^r * (65536-r)!)

where *! is factorial operator, and "r" is the Mac-Adress.

Well if the calculations are not mistake, we obtain r = 13,107 MAC-Adress
minimun in the same site then 99% probability two matches in his last two
bytes.

Now a new MAC entering, which is the probability that given "n"
MAC-Adress,,, all with two last byte differents this new MAC  matches with
any MAC-Adress in its last two bytes? Well this is:

P(n)=1-(65535/65536)^n  then when n=13107 is  P(13107)=0.18 or 18%. That is
MAC-paradox...



>
> _______________________________________________
> B.A.T.M.A.N mailing list
> B.A.T.M.A.N@lists.open-mesh.net
> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
>
>

[-- Attachment #2: Type: text/html, Size: 2920 bytes --]

Re: [B.A.T.M.A.N.] IP from MAC

[Daniel Seither]

Gustavo Lindberg wrote:
> Then, At a meeting of 60 people there is the 99% probability  of the least
> two men have a  birthday the same day. So,, Similarly to the case of
> MAC-Adress is:
> 
> P(r)=1-65536!/(65536^r * (65536-r)!)

Robin uses 3 bytes of the MAC address to choose the IP address of the
mesh interface, not only 2 bytes = 65536 possibilities. This leads to
2^24 = 16777216 different addresses.

Expressed in PARI/GP syntax, you get the following formula:

p(n) = 1 - (factorial(2^24) / ((2^24)^n * factorial(2^24 - n)))

For a network of n=1000 nodes, PARI/GP calculates a probability of about
3 % for an address collision, which should pose no problem.

This is only valid if the NIC vendors randomly choose the MAC addresses
of their cards; chances are that they simply increment the address for
each NIC manufactured. This would increase the possibility of collisions.

However, as Marek already wrote, the focus of the batman development
moves to layer 2 where IP addresses are not used. On top of batman-adv,
you can use any IP address distribution scheme you like. For example,
you could simply run a DHCP server.

Regards,
Daniel

Re: [B.A.T.M.A.N.] IP from MAC

[Gustavo Lindberg]

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

2009/9/17 Daniel Seither <post@tiwoc.de>

> Gustavo Lindberg wrote:
> > Then, At a meeting of 60 people there is the 99% probability  of the
> least
> > two men have a  birthday the same day. So,, Similarly to the case of
> > MAC-Adress is:
> >
> > P(r)=1-65536!/(65536^r * (65536-r)!)
>
> Robin uses 3 bytes of the MAC address to choose the IP address of the
> mesh interface, not only 2 bytes = 65536 possibilities. This leads to
> 2^24 = 16777216 different addresses.
>

All IP addresses are derived by device's MAC address, if MAC is
aa:bb:cc:dd:ee:ff then ath0 IP (mesh iface) will be 5.dd:ee:ff while ath1 IP
and ath2 IP will be 101.ee:ff:1 and 102.ee:ff:1 (obviously in decimal
format).

[-- Attachment #2: Type: text/html, Size: 1040 bytes --]

Re: [B.A.T.M.A.N.] IP from MAC

[Daniel Seither]

Gustavo Lindberg schrieb:
> 2009/9/17 Daniel Seither <post@tiwoc.de>
> 
>> Gustavo Lindberg wrote:
>>> Then, At a meeting of 60 people there is the 99% probability  of the
>> least
>>> two men have a  birthday the same day. So,, Similarly to the case of
>>> MAC-Adress is:
>>>
>>> P(r)=1-65536!/(65536^r * (65536-r)!)
>> Robin uses 3 bytes of the MAC address to choose the IP address of the
>> mesh interface, not only 2 bytes = 65536 possibilities. This leads to
>> 2^24 = 16777216 different addresses.
>>
> 
> All IP addresses are derived by device's MAC address, if MAC is
> aa:bb:cc:dd:ee:ff then ath0 IP (mesh iface) will be 5.dd:ee:ff while ath1 IP
> and ath2 IP will be 101.ee:ff:1 and 102.ee:ff:1 (obviously in decimal
> format).

I read this before, but now I realize that colliding IP addresses of the
ath1/2 interfaces are a problem. This seriously limits the number of
nodes in the network for reasonably low collision probabilities. With
200 nodes, you already have a probability greater than 25%. Enter IPv6...

Regards,
Daniel

Re: [B.A.T.M.A.N.] IP from MAC

[Lick A Prize]

OK so IPs from MAC addresses is pretty good but not a perfect solution.

This comment is interesting...

> However, as Marek already wrote, the focus of the batman development
> moves to layer 2 where IP addresses are not used. On top of batman-adv,
> you can use any IP address distribution scheme you like. For example,
> you could simply run a DHCP server.
>
> Regards,
> Daniel

Batman-adv does indeed seem like the way forward. So, on top of batman-adv, 
what solutions are there for IP address distribution? What might you try in 
a situation where there is no obvious central coordinator to put a DHCP 
server on? 

Re: [B.A.T.M.A.N.] IP from MAC

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 659 bytes --]

> Batman-adv does indeed seem like the way forward. So, on top of batman-adv,
> what solutions are there for IP address distribution? What might you try in
> a situation where there is no obvious central coordinator to put a DHCP
> server on?
Just do a quick search for "ip autoconfiguration"/"address 
autoconfiguration"[1,2] and you will find different solutions like 
zeroconf[3]/APIPA[4]. These are of course only link-local/point-to-point 
solutions.

Best regards,
	Sven

[1] http://tools.ietf.org/html/rfc3927
[2] http://tools.ietf.org/html/rfc4862
[3] http://www.zeroconf.org/
[4] http://msdn.microsoft.com/en-us/library/aa505918.aspx

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

Re: [B.A.T.M.A.N.] IP from MAC

[Lick A Prize]

And for multi-hop networks, of the kind that BATMAN, OLSR, etc. are used 
for?

--------------------------------------------------
From: "Sven Eckelmann" <sven.eckelmann@gmx.de>
Sent: Friday, September 18, 2009 6:19 PM
To: "The list for a Better Approach To Mobile Ad-hoc Networking" 
<b.a.t.m.a.n@lists.open-mesh.net>
Subject: Re: [B.A.T.M.A.N.] IP from MAC

> _______________________________________________
> B.A.T.M.A.N mailing list
> B.A.T.M.A.N@lists.open-mesh.net
> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
> 

Re: [B.A.T.M.A.N.] IP from MAC

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 295 bytes --]

> And for multi-hop networks, of the kind that BATMAN, OLSR, etc. are used
> for?
Why multihop? On batman-adv it is like sending to a switch and thus like a 
single hop for everything above batman-adv. And you asked for batman-adv first 
and not that layer 3 stuff.

Best regards,
	Sven

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

Re: [B.A.T.M.A.N.] IP from MAC

[Simon Wunderlich]

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

Hey,

right, on batman-adv you can use a central DHCP server
or use decentralized link-local IP autoconfiguration tools as Sven suggested.

On Fri, Sep 18, 2009 at 06:42:18PM +1000, Lick A Prize wrote:
> And for multi-hop networks, of the kind that BATMAN, OLSR, etc. are used  
> for?
>
> --------------------------------------------------
> From: "Sven Eckelmann" <sven.eckelmann@gmx.de>
> Sent: Friday, September 18, 2009 6:19 PM
> To: "The list for a Better Approach To Mobile Ad-hoc Networking"  
> <b.a.t.m.a.n@lists.open-mesh.net>
> Subject: Re: [B.A.T.M.A.N.] IP from MAC
>
>> _______________________________________________
>> B.A.T.M.A.N mailing list
>> B.A.T.M.A.N@lists.open-mesh.net
>> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
>>
> _______________________________________________
> B.A.T.M.A.N mailing list
> B.A.T.M.A.N@lists.open-mesh.net
> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
>

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

Re: [B.A.T.M.A.N.] IP from MAC

[Gustavo Lindberg]

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

2009/9/18 Simon Wunderlich <simon.wunderlich@s2003.tu-chemnitz.de>

> Hey,
>
> right, on batman-adv you can use a central DHCP server
> or use decentralized link-local IP autoconfiguration tools as Sven
> suggested.
>

In this scenario, as would resolve the situation of having several internet
gw? L3 Batman announces gw nodes and the client chooses the most
appropriate. But in L2 ?


>
> On Fri, Sep 18, 2009 at 06:42:18PM +1000, Lick A Prize wrote:
> > And for multi-hop networks, of the kind that BATMAN, OLSR, etc. are used
> > for?
> >
> > --------------------------------------------------
> > From: "Sven Eckelmann" <sven.eckelmann@gmx.de>
> > Sent: Friday, September 18, 2009 6:19 PM
> > To: "The list for a Better Approach To Mobile Ad-hoc Networking"
> > <b.a.t.m.a.n@lists.open-mesh.net>
> > Subject: Re: [B.A.T.M.A.N.] IP from MAC
> >
> >> _______________________________________________
> >> B.A.T.M.A.N mailing list
> >> B.A.T.M.A.N@lists.open-mesh.net
> >> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
> >>
> > _______________________________________________
> > B.A.T.M.A.N mailing list
> > B.A.T.M.A.N@lists.open-mesh.net
> > https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
> >
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
>
> iEYEARECAAYFAkqzy8IACgkQrzg/fFk7axZddACguK3p2nbQfMgtfG6KnQ9i+V9r
> L5cAoMjtLEl9uLFoO+gC1Dp2vY37sjJw
> =Xo4P
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> B.A.T.M.A.N mailing list
> B.A.T.M.A.N@lists.open-mesh.net
> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
>
>

[-- Attachment #2: Type: text/html, Size: 2808 bytes --]

Re: [B.A.T.M.A.N.] IP from MAC

[Lick A Prize]

Will link local autoconfiguration/APIPA work in multi-hop ad hoc networks?

Say you have 5 nodes connected, in a line, in an ad hoc network as 
follows...

A <----> B <-----> C <-----> D <------> E

Will autoconfigure ensure that A and E have different addresses? Is there a 
chance that they will both end up with, say for example, 169.254.0.123?

--------------------------------------------------
From: "Simon Wunderlich" <simon.wunderlich@s2003.tu-chemnitz.de>
Sent: Saturday, September 19, 2009 4:04 AM
To: "The list for a Better Approach To Mobile Ad-hoc Networking" 
<b.a.t.m.a.n@lists.open-mesh.net>
Subject: Re: [B.A.T.M.A.N.] IP from MAC

> _______________________________________________
> B.A.T.M.A.N mailing list
> B.A.T.M.A.N@lists.open-mesh.net
> https://lists.open-mesh.net/mm/listinfo/b.a.t.m.a.n
>