Project

General

Profile

Host autoassignment ipv6 » History » Version 4

Victor Oncins, 11/22/2012 11:36 AM

1 3 Victor Oncins
h1. Auto-assignment of IPv6 host-oriented prefixes and collision estimation
2 1 Victor Oncins
3 3 Victor Oncins
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.
4 3 Victor Oncins
5 4 Victor Oncins
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.
6 1 Victor Oncins
7 4 Victor Oncins
Thus the collision probability is greater than 0 if more than one network interface is auto-addressed. We
8 1 Victor Oncins
could calculate this probability and then estimate the maximum number of network interfaces that can be auto-addresses with 
9 4 Victor Oncins
a collision probability less than certain value.
10 3 Victor Oncins
11 4 Victor Oncins
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 
12 4 Victor Oncins
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 
13 4 Victor Oncins
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.
14 1 Victor Oncins
15 4 Victor Oncins
If we select randomly m (m < k) interfaces (MAC addresses) from N OUI, we obtain 
16 1 Victor Oncins
17 4 Victor Oncins
  n!
18 4 Victor Oncins
------
19 4 Victor Oncins
m! n-m!
20 3 Victor Oncins
21 4 Victor Oncins
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
22 3 Victor Oncins
23 4 Victor Oncins
  k!
24 4 Victor Oncins
------- * p^m
25 4 Victor Oncins
m! k-m! 
26 3 Victor Oncins
27 3 Victor Oncins
thus the non-collision probability is
28 3 Victor Oncins
29 4 Victor Oncins
          k! n-m!
30 4 Victor Oncins
P_nc(m) = -- ---- * p ^m
31 4 Victor Oncins
          n! k-m!
32 3 Victor Oncins
33 4 Victor Oncins
If only one interface is present in the network P_nc(1) = kp/n = 1, i.e. the collision is impossible.
34 4 Victor Oncins
We can now calculate the maximum number M of interfaces such that the probability of collision is less than certain value. The following table
35 3 Victor Oncins
shows this number for a maximum collision probability of 4%.
36 3 Victor Oncins
37 4 Victor Oncins
38 4 Victor Oncins
|_.Prefix size |_.l |_.M for N=2 |_.M for N=20 |_.M for N=200 |
39 4 Victor Oncins
|/51	|13 	|27		|27		|27|
40 4 Victor Oncins
|/50	|14 	|38		|38		|38|
41 4 Victor Oncins
|/49	|15 	|53		|53		|53|
42 4 Victor Oncins
|/48	|16 	|74		|74		|74|
43 4 Victor Oncins
|/47	|17 	|105		|104		|104|
44 4 Victor Oncins
|/46	|18 	|148		|147		|147|
45 4 Victor Oncins
|/45	|19 	|210		|208		|208|
46 4 Victor Oncins
|/44	|20 	|298		|294		|294|
47 4 Victor Oncins
|/43	|21 	|428		|416		|415|
48 4 Victor Oncins
|/42	|22 	|627		|520		|587|
49 4 Victor Oncins
|/41	|23 	|957		|839		|830|
50 4 Victor Oncins
|/40	|24 	|1656		|1202		|1174|
51 3 Victor Oncins
52 3 Victor Oncins
We note that the variation of M with the number of OUI is very small. Thus the maximum number of interfaces in a /48 network with a collision
53 3 Victor Oncins
probability 4% is 74.