Auto-assignment of IPv6 host-oriented prefixes and collision estimation¶
One of the desired features is qmp nodes are able to offer native IPv6 addressing to final hosts. IPv6 based networks usually assign /64 prefix to each host-oriented interface, subnetted from a bigger /48. This implies the nodes have 2^16 possible /64 prefixes to auto-assign.
If we want to use MAC address numbering and grant the non-coincidence of auto-generated prefixes, we'll need a mapping function from 48 bits of MAC to 48 bits of IPv6 prefix. According to this auto-configure addressing philosophy, we deduce that is impossible to avoid the election of the same prefix /64 (collision) by one or more network interfaces.
Thus the collision probability is greater than 0 if more than one network interface is auto-addressed. We
could calculate this probability and then estimate the maximum number of network interfaces that can be auto-addresses with
a collision probability less than certain value.
Let the last l LSB of a MAC address, where 1<=l<=24. We left the first 24 bits from OUI. Thus we have a k=2^l possible endings. If
we have in the network N different OUI, we'll have p=N*2^(24-l) possible MAC addresses for each possible ending. Obviously n=k*p is the
total space of possible MAC present in that network. If the network randomly includes two or more MAC with the same l-bit ending, we'll have a collision, i.e. the same IPv6 /64 prefix will be auto-assigned on different network interfaces.
If we select randomly m (m < k) interfaces (MAC addresses) from N OUI, we obtain
n! / m! n-m!
different combinations without replacement. This set of m MAC addresses will contain a subset of combinations where all its MAC addresses have different l-bits ending. These combinations will generate /64 prefixes without collision. The number of such combinations is
p^m * k! / m! k-m!
thus the non-collision probability is
P_nc(m) = p ^m * k! n-m! / n! k-m!
If only one interface is present in the network P_nc(1) = kp/n = 1, i.e. the collision is impossible.
We can now calculate the maximum number M of interfaces such that the probability of collision is less than certain value. The following table
shows this number for a maximum collision probability of 4%. We note that the variation of M with the number of OUI is very small.
Prefix size | l | M for N=2 | M for N=20 | M for N=200 |
---|---|---|---|---|
/51 | 13 | 27 | 27 | 27 |
/50 | 14 | 38 | 38 | 38 |
/49 | 15 | 53 | 53 | 53 |
/48 | 16 | 74 | 74 | 74 |
/47 | 17 | 105 | 104 | 104 |
/46 | 18 | 148 | 147 | 147 |
/45 | 19 | 210 | 208 | 208 |
/44 | 20 | 298 | 294 | 294 |
/43 | 21 | 428 | 416 | 415 |
/42 | 22 | 627 | 520 | 587 |
/41 | 23 | 957 | 839 | 830 |
/40 | 24 | 1656 | 1202 | 1174 |
Thus the maximum number of interfaces in a /48 network with a collision
probability of 4% is 74.
Actualitzat per Victor Oncins fa aproximadament 12 anys · 7 revisions