## 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. |