In the ROBIN address allocation described here http://robin-mesh.wik.is/Documentation/Router_Configuring/Advanced_Configura... 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.
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_Configura... 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
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
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).
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
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?
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
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
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
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
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
b.a.t.m.a.n@lists.open-mesh.org
-
Daniel Seither -
Gustavo Lindberg -
Lick A Prize -
Simon Wunderlich -
Sven Eckelmann