Host autoassignment ipv6 » Historial » Versió 4
Victor Oncins, 22-11-2012 11:36
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 | |||
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 | 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 | 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 | ------ |
||
19 | 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 | ------- * p^m |
||
25 | m! k-m! |
||
26 | 3 | Victor Oncins | |
27 | thus the non-collision probability is |
||
28 | |||
29 | 4 | Victor Oncins | k! n-m! |
30 | P_nc(m) = -- ---- * p ^m |
||
31 | 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 | 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 | |||
37 | 4 | Victor Oncins | |
38 | |_.Prefix size |_.l |_.M for N=2 |_.M for N=20 |_.M for N=200 | |
||
39 | |/51 |13 |27 |27 |27| |
||
40 | |/50 |14 |38 |38 |38| |
||
41 | |/49 |15 |53 |53 |53| |
||
42 | |/48 |16 |74 |74 |74| |
||
43 | |/47 |17 |105 |104 |104| |
||
44 | |/46 |18 |148 |147 |147| |
||
45 | |/45 |19 |210 |208 |208| |
||
46 | |/44 |20 |298 |294 |294| |
||
47 | |/43 |21 |428 |416 |415| |
||
48 | |/42 |22 |627 |520 |587| |
||
49 | |/41 |23 |957 |839 |830| |
||
50 | |/40 |24 |1656 |1202 |1174| |
||
51 | 3 | Victor Oncins | |
52 | 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 | probability 4% is 74. |