Projecte

General

Perfil

Host autoassignment ipv6 » Historial » Revisió 4

Revisió 3 (Victor Oncins, 22-11-2012 11:01) → Revisió 4/7 (Victor Oncins, 22-11-2012 11:36)

h1. 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, as a mapping value, 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 Anyway, we 
 could calculate this probability and then estimate the maximum number of network interfaces that can be auto-addresses with  
 a probability collision probability less than certain value. 

 Let l as the last l LSB 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, 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 a network. If the network randomly includes two or more MAC with the same l-bit ending, ending from  
 different OUI 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) k interfaces (MAC addresses) from N OUI, we obtain  

   n! 
 ------ 
 m! n-m!  

 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 with different l-bits ending. These  
 combinations will generate /64 prefixes without collision. The number of such combinations with all different ending is 

   k! 
 ------- 

 k!/m!k-m! * p^m 
 m! k-m!  

 

 thus the non-collision probability is 

           k! n-m! 
 P_nc(m) 

 Pĉ(m) = -- ---- k!/n!*n-m!/k-m! * p ^m 
           n! k-m! p^m 

 If only one interface is present in the network P_nc(1) Pĉ(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 was less than certain value. The following table 
 shows this number for a maximum collision probability of 4%. 


 |_.Prefix size |_.l |_.M 

 Prefix  	 l 	 M for N=2 |_.M 	 M for N=20 |_.M 	 M for N=200 | 
 |/51 ---------------------------------------------------- 
 /51 	 |13 13  	 |27 27 		 |27 27 		 |27| 27 
 |/50 /50 	 |14 14  	 |38 38 		 |38 38 		 |38| 38 
 |/49 /49 	 |15 15  	 |53 53 		 |53 53 		 |53| 53 
 |/48 /48 	 |16 16  	 |74 74 		 |74 74 		 |74| 74 
 |/47 /47 	 |17 17  	 |105 105 		 |104 104 		 |104| 104 
 |/46 /46 	 |18 18  	 |148 148 		 |147 147 		 |147| 147 
 |/45 /45 	 |19 19  	 |210 210 		 |208 208 		 |208| 208 
 |/44 /44 	 |20 20  	 |298 298 		 |294 294 		 |294| 294 
 |/43 /43 	 |21 21  	 |428 428 		 |416 416 		 |415| 415 
 |/42 /42 	 |22 22  	 |627 627 		 |520 520 		 |587| 587 
 |/41 /41 	 |23 23  	 |957 957 		 |839 839 		 |830| 830 
 |/40 /40 	 |24 24  	 |1656 1656 		 |1202 1202 		 |1174| 1174 

 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 
 probability 4% is 74.