idnits 2.17.1 draft-soto-mobileip-random-iids-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 59: '... 2462 [2] states that "Duplicate Address Detection MUST take place on...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 140 has weird spacing: '... then consi...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 29, 2002) is 8117 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2374 (ref. '1') (Obsoleted by RFC 3587) ** Obsolete normative reference: RFC 2462 (ref. '2') (Obsoleted by RFC 4862) -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Downref: Normative reference to an Informational RFC: RFC 1998 (ref. '5') -- Possible downref: Non-RFC (?) normative reference: ref. '6' Summary: 7 errors (**), 0 flaws (~~), 5 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Bagnulo 3 Internet-Draft I. Soto 4 Expires: July 30, 2002 A. Garcia-Martinez 5 A. Azcorra 6 UC3M 7 January 29, 2002 9 Random generation of interface identifiers 10 draft-soto-mobileip-random-iids-00.txt 12 Status of this Memo 14 This document is an Internet-Draft and is in full conformance with 15 all provisions of Section 10 of RFC2026. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at http:// 28 www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on July 30, 2002. 35 Copyright Notice 37 Copyright (C) The Internet Society (2002). All Rights Reserved. 39 Abstract 41 This document evaluates the use of random numbers to generate the 42 interface identifier part of an IPv6 address on mobile environments, 43 where Duplicate Address Detection (DAD) mechanisms are expensive. We 44 have estimated the probability of having an address duplication using 45 this mechanism and we conclude that the IPv6 addresses created in 46 this way could be used without previously doing DAD to test the 47 uniqueness of the address in a link. 49 1. Introduction 51 In the IPv6 aggregatable address format defined in [1] , the last 64 52 bits are assigned to the interface identifier. According to [1], in 53 many cases, a link-layer address is used to create the interface 54 identifier part of the IPv6 address, although some other mechanisms 55 are possible when there is no MAC address available. Because there 56 are not guarantees of having a unique link local address, after 57 configuring an interface with an IPv6 address, DAD mechanism must be 58 performed to ensure that the IPv6 address is unique in the link. RFC 59 2462 [2] states that "Duplicate Address Detection MUST take place on 60 all unicast addresses, regardless of whether they are obtained 61 through stateful, stateless or manual configuration". DAD is a time 62 consuming process, that usually do not represent a problem for a 63 desktop computer that is initialising. 65 Mobility support in IPv6 networks will be provided by Mobile IPv6 66 [3]. Using this protocol, a Mobile Node (MN) that enters a subnet 67 must configure an on-link address in that subnet (the Care-of 68 Address, CoA) before being able to communicate. According to [2], 69 before using the CoA, the MN must perform DAD for that address. But 70 in this case, the time required for DAD is a critical matter because 71 during this time the MN can not communicate and additionally, active 72 communications of the MN are interrupted during this period. This is 73 specially unsuitable for real-time communications. [3] recognizes 74 this problem and states that a MN can decide not to perform DAD, 75 being this is a trade-off between safety and the time needed for the 76 DAD procedure. This document evaluates the use of random numbers to 77 create the interface identifier of the IPv6 addresses, and assesses 78 the risk of using these addresses without previously performing DAD. 80 Using mechanisms such as fast handovers [4] it is possible to perform 81 DAD in advance, before the MN arrives to the subnet. The Access 82 Router (AR) in the subnet is instructed to perform DAD on behalf of 83 the MN before it enters the subnet. But then, the MN has to wait for 84 the time needed to perform DAD before it can accomplish the handover. 85 This can be a problem in many situations in which the handover is 86 required because the previous layer-2 connection is experimenting 87 difficulties. So we will again benefit for avoiding the previous DAD 88 procedure. 90 Summarizing, for handover situations the importance of the time 91 required for DAD can not be underestimated. In this document we 92 study the possibility of using random generated interface identifiers 93 to autoconfigure IPv6 addresses. We also reason that DAD can be 94 performed after the node has joined the link because the probability 95 that an address duplication happens is very low. 97 2. Creation of interface identifiers. 99 We will study the possibility that the interface identifiers are 100 created randomly, meaning that the host will use a randomly generated 101 64 bit number as the interface identifier. Actually, only 62 bits of 102 the interface identifier will be generated randomly since, as it is 103 defined in [5], the u bit must be set to "local" and the g bit must 104 be set to "individual". We will now evaluate the probability of 105 collision of two or more randomly generated address identifiers. 107 The problem: The Address identifiers I1, I2, I3, ..., Ik are a 108 sequence of 62 bit long random variables. Ii are randomly generated. 109 We would like to obtain the probability that two or more Iis collide, 110 i.e. Ii=Ij. This is a very well known mathematical problem that is 111 called the "birthday problem". The solution is: 113 I1,I2,...,Ik random variables, integer and with uniform distribution 114 between 1 and n (k<=n) 116 P(n,k)(at least one repeated)=1-(n!)/[(n-k)!.n^k] 118 (This result is explained in Appendix A) 120 In our case n=2^62, so the calculation of n! may be more than what a 121 simple calculator can handle. In order to overcome this, we will try 122 to find an upper bound to P(n,k). 124 P(n,k)= 1-(n!)/[(n-k)!.n^k] 126 = 1-[(n).(n-1)...(n-k+1)/n^k] 128 = 1-[(n/n).((n-1)/n)...((n-k+1)/n)] 130 = 1-[ 1 .(1-1/n)...(1-(k-1)/n)] 132 It should be noted that: 134 i/n =< (k-1)/n when i=1...k-1 136 then -i/n >= -(k-1)/n when i=1...k-1 138 then 1-i/n >= 1-(k-1)/n when i=1...k-1 140 then considering that k0 when i=1...k-1 142 (1-1/n)(1-2/n)...(1-(k-1)/n)>=(1-(k-1)/n)^(k-1) 144 then -(1-1/n)(1-2/n)...(1-(k-1)/n)=<-[(1-(k-1)/n)^(k-1)] 145 then 1-(1-1/n)(1-2/n)...(1-(k-1)/n)=<1-[(1-(k-1)/n)^(k-1)] 147 then P(n,k)=< 1-[(1-(k-1)/n)^(k-1)] = 1-[(n-k+1)/n]^(k-1) 149 then P(n,k)=< [n^(k-1)-(n-k+1)^(k-1)]/[n^(k-1)]=B 151 n! is not present in this bound so B is easier to calculate. 153 In order to quantify the result we will make a few calculations: 154 Remembering that n is the number of possible addresses an k is the 155 number of interfaces in the same link, we will evaluate the upper 156 bound the following values of k 158 P(2^62,20)=< 7.8 e-17 160 P(2^62,100)=< 2.1 e-15 162 P(2^62,500)=< 5.4 e-14 164 P(2^62,1000)=< 2.2 e-13 166 P(2^62,5000)=< 5.4 e-12 168 In order to fully understand the magnitude of the probabilities 169 above, we could compare them with other probabilities. 171 For instance, according to Table 1.1 of [6], the probability of being 172 killed by a lightning (per day) is about 1.1 e-10. Then, a mobile 173 phone user should be more worried about being killed by a lightning 174 than to have an interface identifier repeated. 176 We would also like to compare the probabilities above with some 177 issues that affect communication in a similar fashion that address 178 collision such as the probability of failure of the network 179 equipment. 181 In case a network equipment fails, communication will be lost until 182 it is replaced, having a similar effect to the one of having a 183 repeated interface identifier. In order to quantify the probability 184 of a network equipment failure, we will estimate it as: 186 P(NE failure)=MTTR/(MTBF+MTTR) 188 Being MTTR: Meat Time To Repair and MTBF: Mean Time Between Failures 190 Network equipment can have an MTBF of 300,000 hours and let's suppose 191 that some backup equipment is available and that MTTR is 0,1 hour (6 192 minutes). 194 So P(NE failure)= 3,3e-7. 196 We can see that P(NE failure) is much more higher than P(n,k). 198 Besides hardware malfunctioning, network connectivity can be affected 199 by operation errors. Usually, this type of problems are much more 200 frequent than hardware outages, but we do not have any hard data 201 available. 203 We think that it also interesting to estimate the probability of 204 collision over a year of usage of the system. As we stated above, 205 P(n,k) is the probability of a collision of two or more Interface 206 identifiers when there are k interfaces in the same link. In order 207 to quantify the probability of collision of a user during a year 208 using the system, we will calculate the probability of one or more 209 collision when a user joins m different networks. 211 The probability of NOT having a collision is Pnot(n,k)=1-P(n,k) 213 Then the probability of not having a collision after joining m 214 different networks is Pnot(n,k,m)=[1-P(n,k)]^m. 216 Then the probability of having a collision after joining m different 217 networks is: P(n,k,m)=1-[[1-P(n,k)]^m] 219 According to the bound found earlier: 221 P(n,k)==-B 225 Then 1-P(n,k)>=1-B 227 As P(n,k)and B are less than 1, (1-P(n,k))^m>=(1-B)^m 229 Then 1-[(1-P(n,k))^m]=<1-[(1-B)^m] 231 Then P(n,k,m)=<1-[(1-B)^m] 233 If we consider m=50.000, this means about 140 handovers per day, 235 P(2^62,500,50000)=< 2,7e-9 237 P(2^62,5000,50000)=< 2,7e-7 239 Considering that each time there is a collision, there are two users 240 affected (not considering collision of 3 or more for this 241 estimation), this means that in the case users make 140 handovers per 242 day in networks containing 500 interfaces, there will be 6 users out 243 of 1.000.000.000 that will have a problem with the communication 244 during this year. In the case users make 140 handovers per day in 245 networks containing 5000 interfaces, there will be 6 users out of 246 10.000.000 that will have a problem with the communication during 247 this year. 249 3. Random generation of Interface identifiers.. 251 Another relevant issue is how to generate a 62 bit long random 252 number. In some cases, such as laptops, a random number generator 253 can be available on the system, but in other cases, such as mobile 254 phones, it may not. In such cases, it should be noted that because 255 of the randomness of the identifier, it is not necessary to create 256 the identifier in real time, i.e. when the node joins the network, 257 but the identifier can be already created (such as the day of birth 258 in the birthday problem). What is more, this random number can be 259 pre-configured in the interface driver and the node can use always 260 the same number without changing the probabilities calculations made 261 above. This reduces the needed complexity in the nodes. 263 4. Conclusions. 265 In this draft, we have studied the possibility of using random 266 generated numbers for the interface identifier part of the IPv6 267 addresses. We have also calculated the probability of address 268 collision when interface identifiers are generated this way. After 269 evaluating this probability in several different scenarios, we have 270 found that collision probability with random generated Interface 271 Identifiers is lower enough to consider this mechanism as a possible 272 option. Considering that DAD mechanism is time consuming when time 273 is critical i.e. mobile communications, we think random generation 274 of Interface identifier part of IPv6 addresses is an attractive 275 option because it can be used without previously doing DAD. Whether 276 DAD should be performed after or it can be avoided, needs further 277 study. For now, we think that performing DAD after joining the link 278 is needed. 280 5. Security Considerations. 282 This draft does no introduce new security risks. What's more, random 283 generation of interface identifiers can enable improved anonymity 284 features by allowing interface identifier generation each time a node 285 joins a new link, what can prevents tracing. 287 6. Acknowledgments. 289 This work has been done under IST projects LONG and Moby Dick 291 7. Appendix A: The Birthday Problem 293 The problem: we want to calculate the probability that in a group of 294 k people, al least two of them have the same birthday. 296 We model the birthday as a integer random variable, with uniform 297 distribution between 1 and 365 (we forget about the 29th of February, 298 sorry about that :-( 300 The solution: Let's find out the number N of ways that we can have k 301 values with no duplicates. We can choose 365 values the first time, 302 364 the second time,.... 304 So, N=365*364*...*(365-k+1) 306 If we remove the restriction that there are no duplicates, the number 307 of possibilities is 365^k. 309 So the probability of not having a collision is: 311 Pnot= 365!/[(365-k)!*365^k 313 Then the probability of having at least one duplicate is: 315 P=1-Pnot=1-365!/[(365-k)!*365^k 317 The general case it would be: 319 P(n,k)= 1-n!/[(n-k)!*n^k with n>k 321 References 323 [1] Hinden, R., O�Dell, M. and S. Deering, "An IPv6 Aggregatable 324 Global Unicast Address Format", RFC 2374, July 1998. 326 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 327 Autoconfiguration", RFC 2462, December 1998. 329 [3] Johnson, D. and C. Perkins, "Mobility Support in IPv6", Internet 330 draft Work in progress, July 2001. 332 [4] Dommety, G., "Fast Handovers for Mobile IPv6", Internet draft 333 Work in progress, July 2001. 335 [5] Hinden, R. and S. Deering, "IP Version 6 Addressing 336 Architecture", RFC 1998, 1998. 338 [6] Schneier, B., "Applied cryptography", Wiley ISBN 0-471-12845-7, 339 1996. 341 Authors' Addresses 343 Marcelo Bagnulo 344 Universidad Carlos III de Madrid 345 Av. Universidad 30 346 Leganes, Madrid 28911 347 SPAIN 349 Phone: 34 91 6249500 350 EMail: marcelo@it.uc3m.es 351 URI: http://www.it.uc3m.es 353 Ignacio Soto 354 Universidad Carlos III de Madrid 355 Av. Universidad 30 356 Leganes, Madrid 28911 357 SPAIN 359 Phone: 34 91 6249500 360 EMail: isoto@it.uc3m.es 361 URI: http://www.it.uc3m.es 362 Alberto Garcia-Martinez 363 Universidad Carlos III de Madrid 364 Av. Universidad 30 365 Leganes, Madrid 28911 366 SPAIN 368 Phone: 34 91 6249500 369 EMail: alberto@it.uc3m.es 370 URI: http://www.it.uc3m.es 372 Arturo Azcorra 373 Universidad Carlos III de Madrid 374 Av. Universidad 30 375 Leganes, Madrid 28911 376 SPAIN 378 Phone: 34 91 6249500 379 EMail: azcorra@it.uc3m.es 380 URI: http://www.it.uc3m.es 382 Full Copyright Statement 384 Copyright (C) The Internet Society (2002). All Rights Reserved. 386 This document and translations of it may be copied and furnished to 387 others, and derivative works that comment on or otherwise explain it 388 or assist in its implementation may be prepared, copied, published 389 and distributed, in whole or in part, without restriction of any 390 kind, provided that the above copyright notice and this paragraph are 391 included on all such copies and derivative works. However, this 392 document itself may not be modified in any way, such as by removing 393 the copyright notice or references to the Internet Society or other 394 Internet organizations, except as needed for the purpose of 395 developing Internet standards in which case the procedures for 396 copyrights defined in the Internet Standards process must be 397 followed, or as required to translate it into languages other than 398 English. 400 The limited permissions granted above are perpetual and will not be 401 revoked by the Internet Society or its successors or assigns. 403 This document and the information contained herein is provided on an 404 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 405 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 406 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 407 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 408 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 410 Acknowledgement 412 Funding for the RFC Editor function is currently provided by the 413 Internet Society.