Project

General

Profile

Host autoassignment ipv6 » History » Version 3

Victor Oncins, 11/22/2012 11:01 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 3 Victor Oncins
If we want to use MAC address numbering as a mapping value, we'll need a mapping function from 48 bits of MAC to 48 bits of IPv6 prefix.
6 3 Victor Oncins
7 3 Victor Oncins
According to this auto-configure addressing philosophy, we deduce that is impossible to avoid 
8 3 Victor Oncins
the election of the same prefix /64 (collision) by one or more network interfaces.
9 3 Victor Oncins
10 3 Victor Oncins
Thus the collision probability is greater than 0 if more than one network interface is auto-addressed. Anyway, we
11 3 Victor Oncins
could calculate this probability and then estimate the maximum number of network interfaces that can be auto-addresses with 
12 3 Victor Oncins
a probability collision less than certain value.
13 3 Victor Oncins
14 3 Victor Oncins
Let l as 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 
15 3 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 
16 3 Victor Oncins
total space of possible MAC present in a network. If the network randomly includes two or more MAC with the same l-bit ending from 
17 3 Victor Oncins
different OUI we'll have a collision, i.e. the same IPv6 /64 prefix will be auto-assigned on different network interfaces.
18 3 Victor Oncins
19 3 Victor Oncins
If we select randomly m < k interfaces (MAC addresses) from N OUI, we obtain 
20 3 Victor Oncins
21 3 Victor Oncins
n!/m!n-m!
22 3 Victor Oncins
23 3 Victor Oncins
different combinations without replacement. This set of m MAC addresses will contain all its MAC addresses with different l-bits ending. These 
24 3 Victor Oncins
combinations will generate /64 prefixes without collision. The number of combinations with all different ending is
25 3 Victor Oncins
26 3 Victor Oncins
k!/m!k-m! * p^m
27 3 Victor Oncins
28 3 Victor Oncins
thus the non-collision probability is
29 3 Victor Oncins
30 3 Victor Oncins
Pĉ(m) = k!/n!*n-m!/k-m! * p^m
31 3 Victor Oncins
32 3 Victor Oncins
If only one interface is present in the network Pĉ(1) = kp/n = 1, i.e. the collision is impossible.
33 3 Victor Oncins
We can now calculate the maximum number M of interfaces such that the probability of collision was less than certain value. The following table
34 3 Victor Oncins
shows this number for a maximum collision probability of 4%.
35 3 Victor Oncins
36 3 Victor Oncins
Prefix 	l	M for N=2	M for N=20	M for N=200
37 3 Victor Oncins
----------------------------------------------------
38 3 Victor Oncins
/51	13 	27		27		27
39 3 Victor Oncins
/50	14 	38		38		38
40 3 Victor Oncins
/49	15 	53		53		53
41 3 Victor Oncins
/48	16 	74		74		74
42 3 Victor Oncins
/47	17 	105		104		104
43 3 Victor Oncins
/46	18 	148		147		147
44 3 Victor Oncins
/45	19 	210		208		208
45 3 Victor Oncins
/44	20 	298		294		294
46 3 Victor Oncins
/43	21 	428		416		415
47 3 Victor Oncins
/42	22 	627		520		587
48 3 Victor Oncins
/41	23 	957		839		830
49 3 Victor Oncins
/40	24 	1656		1202		1174
50 3 Victor Oncins
51 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
52 3 Victor Oncins
probability 4% is 74.