Probability of Random MAC Address Duplicates Study
This document discusses the probability of random MAC address duplicates using classic and alternative formulas, including the birthday and pairs formulas. It explores how to calculate these probabilities for large numbers in network scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Dec 2023 doc.: IEEE 802.11-23/2148r0 TG bh Probability of random MAC address (IRM) duplicates Date: 2023 Dec Authors: Name Company Address Phone email Graham Smith SRT Group Sunrise, FL gsmith@srtrl.com Submission Slide 1 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Intro The probability of IRM duplicates is studied and examples evaluated. This submission provides the derivations of the related formulas and then applies them to calculate the probabilities and timescales for Networks of various (large ) sizes. Submission Slide 2 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Classic formula for duplicates (aka birthday formula) Probability of picking 2 the same with N picks from a population of X, Pick the first Probability of not picking the same on the second pick is (? 1) ? Probability of not picking 2 the same on the third pick is (? 1)(? 2) ?.? Probability of not picking 2 the same on the (N+1) th pick is ? 1 ? 2 .(? ?) ?? ? 1 ! ? ? !?? = ? 1 ! ? ? !?? Probability of picking two the same, P = 1 - (1) Note: Calculating factorials for large numbers is not practical. e.g., X = 2 ^46 = 7.04 E+13 a very big number Submission Slide 3 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Approximating the birthday formula for large numbers (aka squared formula) ? 1 ? 2 .(? ?) (? ? 2)? if X >> N, ??(? ? 1 2)? From (1) P = 1 - ? 1 ?(? ? 2) P = 1 - ? 2?)? P = 1 (1 P = ?2 For ? 2? << 1, 2? (2) N = 2.?.? Or (3) Two simple formulas that can be used to calculate either the 1. Probability of duplicate for pick of N from X 2. Number of picks required for a fixed probability Submission Slide 4 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Alternative Duplicate probability formula, (aka pairs formula) Probability of duplicate with N picks from population of X p= ?(? 1) Number of ways of selecting 2 from N, i.e., number of pairs 2 Pick any pair, then probability of that pair not being the same is (? 1) ? ? (? 1) ? Hence, for p pairs, probability of each pair not being the same is ? (? 1) Probability of pair being the same P = 1 - (4) ? This formula can be used for Probability with large numbers Picks N for fixed X and P is given by 1+ 1+4? 2 ???(1 ?) (? 1) (5) ? = where c = 2 ??? ? Submission Slide 5 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Approximating the Pairs formula for large numbers ?= (1-1/X)p (? 1) ? ?= (1-p/X) = (1 ?(? 1) (? 1) ? If 1/X<<1, then ) 2? P = 1 - (1 ?(? 1) ) = ?(? 1) Hence 2? 2? ?2 P = ?(? 1) 2? i.e., equation (2) 2? Submission Slide 6 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Odds and Probability If we have a probability of P, Then Odds of this happening is 1 in (1-P)/P For example, for P = .01, Odds are 1 in 99 For very low P, Odds 1/P Submission Slide 7 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Results "Squared" formula bits 46 46 46 46 46 value X 7.03687E+13 7.04E+13 7.04E+13 7.04E+13 7.04E+13 #STAs N 5000 10000 20000 50000 80000 Prob of duplicate 1.77636E-07 7.11E-07 2.84E-06 1.78E-05 4.55E-05 ODDS 1 in 5629499 1407374 351843 56294 21989 "Pairs" formula bits 46 46 46 46 46 value X 7.03687E+13 7.04E+13 7.0369E+13 7.037E+13 7.03687E+13 #STAs N 5000 10000 20000 50000 80000 pairs 12497500 49995000 199990000 1.25E+09 3199960000 Chance per pair 1.00E+00 1.00E+00 1.00E+00 1.00E+00 1.00E+00 Prob of duplicate 1.78E-07 7.10E-07 2.84E-06 1.78E-05 4.55E-05 ODDS 1 in 5630625 1407515 351861 56296 21990 Submission Slide 8 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Calculation for duplications over multiple associations For an ESS that is storing N addresses (IRMs), each time a STA associates there is a probability PN that a duplicate occurs. Probability of duplication per association = PN Probability of no duplication per association = 1 PN Probability of no duplication per k associations = (1 PN)k Probability of duplication per k associations = 1 - (1 PN)k If PN <<1, then probability of duplication per k associations k PN If k associations per day, then probability of duplicate, per day, P = 1 - (1 PN)K If associations for d days, then 1- (1-P)d = 0.5 For 50% probability of duplication d LOG(1-P) = LOG (0.5) d = LOG(0.5) / LOG (1-P) Submission Slide 9 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Case 1 Duplications per ESS (storing N IRMs) Assume N STAs associate each day, K times. (full load every day) Probability of duplication per association = PN Probability of no duplication per association = 1 PN Probability of no duplication per Nk associations = (1 PN)NK Probability of duplication per k associations = 1 - (1 PN)NK If PN <<1, then probability of duplication per k associations N K PN Duplications per ESS bits value X IRMs stored N 46 46 46 46 46 7.04E+13 5000 7.04E+13 10000 7.04E+13 20000 7.04E+13 50000 7.04E+13 80000 Prob of duplicate PN Associations /day/STA Associations/day k Prob per day , P # days for 50% # duplicates per day 1.78E-07 7.11E-07 2.84E-06 1.78E-05 4.55E-05 3 3 3 3 3 15000 0.002661 260.14 30000 0.021091 32.52 60000 0.156783 150000 0.93037 0.26 3.84 240000 0.999982 15.75 duplicates per day 4.06 0.06 15.75 Submission Slide 10 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Case 2 Duplicates per AP (ESS storing N IRMs) Limit STAs per standard network AP = 2007 (AID) S1G AP = 8191 Assume 2000 STAs associate each day, K times per day. Probability of duplication per association = PN Probability of no duplication per association = 1 PN Probability of no duplication per 2000k associations = (1 PN)2000K Probability of duplication per k associations = 1 - (1 PN)2000K Duplications per AP bits 46 value X 7.04E+13 7.04E+13 IRMs stored N 5000 10000 46 46 46 46 7.04E+13 20000 7.04E+13 50000 7.04E+13 80000 Prob of duplicate PN Associations /day/STA # APs # STAs /AP Associations/day /AP Prob per day , P # days for 50% 1.78E-07 7.11E-07 2.84E-06 1.78E-05 4.55E-05 3 3 3 5 3 3 3 Duplicate every 2.5 days 10 25 40 2000 6000 2000 6000 2000 6000 2000 6000 2000 6000 0.001065 650.35 0.004254 162.59 0.016908 40.65 0.101099 0.238797 6.50 2.54 Submission Slide 11 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Case 3 Duplications per STA If STA associates* K times per day, then probability of duplicate, per day, P = 1 - (1 PN)K IF STA does this for d days, then 1- (1-P)d = 0.5 For 50% probability of duplication d LOG(1-P) = LOG (0.5) d = LOG(0.5) / LOG (1-P) Duplications per STA bits value X IRMs stored N Prob of duplicate PN Assocs/day K Prob per day , P # days for 50% Years 46 46 46 46 46 7.03687E+13 7.0369E+13 10000 7.1054E-07 7.037E+13 20000 2.842E-06 7.04E+13 50000 1.78E-05 7.04E+13 80000 4.55E-05 5000 1.776E-07 3 3 3 3 3 5.329E-07 130069.46 3563.54 2.1316E-06 325172.53 890.88 8.526E-06 81293.05 222.72 5.33E-05 13006.79 35.64 0.000136 5080.71 13.92 *Note: Reassociations use same IRM Submission Slide 12 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Results for busiest network Busy network, N = 80,000 IRMs with 80,000 STAs associating 3 times a day. ESS has average of 15.75 duplicates per day For each AP, average of 2.54 days, between duplicates Quick check 40 APs, so 40 / 15.75 = 2.54 days, so this agrees Each STA, average of 5080 days between duplicates (~14 years) Quick check 80,000/5080 = 15.74, so this agrees i.e., Each AP in ESS exchanges IRM Duplicate Action frames on average twice every 5 days. Submission Slide 13 Graham Smith, SR Technologies
Dec 2023 doc.: IEEE 802.11-23/2148r0 Conclusions A very busy network, storing a high number of IRMs (80,000) may have several duplicates per day (15.75) BUT Each AP (40+) in ESS only has a duplicate every 2.54 days Each STA only experiences a duplicate every 14 years. Therefore, Action frame exchange to get new IRM is a tiny overhead and effectively rare. No need to change anything Note: For S1G (8000 STAs per AP), each AP has 1.5 duplicates per day. Submission Slide 14 Graham Smith, SR Technologies
