Hi Luther,
Yes, we have a mechanism to do that. After association, the AP sends an action frame informing STA that it provided a duplicate. The STA then sends a new IRM.
Graham
Dan/Graham,
Just being of simple mind, could the AP check to see if the new IRM is not either currently in use or proposed as the future IRM by another non-AP STA and if so trigger the non-AP STA to
generate a new IRM?
Also, with this prediction of probabilities, in the current state of devices using RCM, isn’t the situation the same?
Just thinking,
Luther
Graham,
The ESS is saving 9000 random IRMs for the "next MAC address" of each of the 9000 associated STAs. So that is similar to 18,000 STAs associating at once
if you don't want to have a collision between any of the associated STAs and their "next MAC address". The number of associations per day doesn't matter because we're only concerned with the current MAC address and the next MAC address of each associated STA.
Again, if I associate 3 times per day, on my 3rd association the previous two MAC addresses I used are not being retained and any other STA's use of those MAC addresses would not constitute a collision. STAs could associate 20x per day and it's
still just "current MAC and next MAC".
Since there are 18,000 MAC addresses that need to be used the probability of collision is 0.0000023. And that's the number regardless of the number of
associations per day or the number of days that STAs are associating.
I'm not sure where 80,000 STAs came from. I believe the current record holder for associations to a single ESS is a tad more than 30,000. If all 30,000
STAs were doing 11bh that would be 60,000 MACs and the probability of collision for that is 0.0000255. Of course we should architect for the future but 80,000 seems somewhat excessive (and 160,000 MACs gives a probability of 0.0001818)
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Yes Dan, you are right, but that is not the probability we are dealing with here. If the ESS is saving 9000 random IRMs, yes they change each time a STA associates,
but 9000 STA are associating 3 times a day, i.e., 27000 associations a day, each with the same probability of a duplicate, i.e., chance of a random IRM matching one of 9000 random IRMs. Someone wins the lottery, and similarly, one of the 9000 STAs will be
unlucky at some point. The result I gave is that calculation, the average number of days between any duplicate, where the probability of the duplicate rises to 50% (similar to the birthday thingy).
However, as I discovered when I was working on this, we are not really interested in a duplication within the ESS, but how often each AP in the ESS would have to
send the duplicate message (it was to dispel the thought that this could jam up the ESS). Each AP only has 2000 STAs associating so the average time between duplicates is less.
Of course, at 9000 STAs it is not really a problem, that’s why I considered 80,000 which is a number I was given by another TGbh attendee.
Regards
Graham
Just to expand on the lottery analogy, if the lottery is held every day and I buy 1 ticket, and get a number, for each day's lottery
then if a losing number I got last week hits one day this week I do not win. That number was only good for the lottery it was bought for. Similarly for MACs. A MAC I used 3 associations ago might get randomly chosen, and used, by one of the 9000 other STAs
when I associate next but that's not a collision.
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Graham,
I don't think you can say "it takes eons before a duplicate actually occurs". It could occur immediately. And it might not occur
for eons. We're talking probability here. Furthermore, the calculations you are making concern any 2 STAs out of the 9000 STAs associating getting a duplicate so when you say how long it takes before a duplicate "for that STA" I think you're making a leap.
The probability is not "for that STA". It's for any 2 out of the 9000.
But I'm still not groking your statement that associating multiple times a day will make a duplicate occurrence more likely (and
in 44 days). If I have a 1 in a billion chance of winning a lottery my odds increase if I buy more tickets *for that one lottery*. But if the lottery occurs many times, lets say once a day, and I only buy 1 ticket for each drawing each day then my odds
with each ticket are still just 1 in a billion. And since the STA is not retaining its old MAC addresses, and it can only be associated once at a time, when it deassociates and associates anew there is no increase in the probability of 2 STAs randomly choosing
the same MAC. The old MAC goes back into the pool of unused MACs which, if randomly chosen by any one of the 9000 will not result in a collusion. Right?
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
As I explained in my contribution, the ESS maintains 9000 addresses (in this example), so each time a STA comes back and provides a new IRM, there is the same
probability of a duplicate. So it take eons before a duplicate actually occurs, for that STA. But if 2000 STAs associate 3 times a day, that time obviously reduces, for any one of the STAs to hit a duplicate, and any one AP in the ESS. That is what my contribution
analyzes.
Graham
I think Dan has a very good point here. That you only need to consider the current devices that are associated at the time the new randomized MAC is generated.
The probability is also contingent on the number of devices. Generating the same MAC with one other device in use does go up as the number of devices; however, that is only a small ripple in the chances of generating a conflicting MAC address.
Luther
Hi Graham,
I don't believe that associating 3x a day makes it 44 days for a 0.5 probability of collision. If these STAs are associating
3x per day that means they are disassociating as well. They do not maintain their old MAC addresses for any period of time and a MAC address that is used by a STA at some slice of time is not fixed such that other STAs in their 3x per day associating will
collide with it if they happen to choose it. We're talking about the probability of 2 STAs *simultaneously* choosing the same MAC address. If it's 9000 STAs then it doesn't matter if they associate once per day or 3x per day. If I chose a particular
MAC address, disassociated, and then you came along later in the day and randomly selected the same MAC address it's not a collision. The fact we chose the same MAC address *at different times* does not matter.
The odds are not 1 in 1747993 per association, they are 1 in 1747993 period.
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Dan is correct.
The relationship between probability and odds is “1 in (1-P)/P”, which in this k=9000 case, the odds of a duplicate is 1 in 1747993 per association. If we say
1 association per day then this probability means once every 137 years there is a 50% chance of a duplicate (401448 Associations).
But, as I tried to point out in my contribution (23/2148r1), this is not the whole story. Every time a STA associates to any AP in an ESS there is a chance of
a duplicate, so if the STA associates 3 times a day, it comes down to a only 44 days for a 50% chance of a duplicate in the ESS, but this is 200 days for each AP in the ESS (5 APs in the ESS). Hopefully all is explained in my contribution where I have tried
to explain all the formulas and their derivations.
Hope this helps,
Graham
Hi Bob,
I do not believe that means the 9001st will collide with one of the existing 9000. The probability for 9001 is basically
the same. What it's saying is that the probability of any 2 STAs out of those 9000 (or 9001) randomly choosing the same MAC address is 0.000000575. It is certainly not 1.
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Graham,
This is what I use in calculating the probability of a collision:
Calculating Collision Probabilities
The accepted formula for calculating the probability of a collision
is:
P = 1 - e^({-k^2/(2n)})
P: Collision Probability
n: Total possible population
k: Actual population
Example:
n=2^46
k=9000
P= 5.7*10^-7
That is that the 9001th will collide with one of the existing 9000.
And if n=2^44
Then it would be 4x as likely.
On 6/3/24 10:15, G Smith wrote:
Hi Jay,
I may not be the best person to answer this but basically the MAC address is made up of 48 bits. However, bit 0 in the 1st octet is the unicast/multicast
bit, set to 0 for unicast. Bit 1 in the first octet is the global unique/locally administered bit. As was agreed for 11aq and in the baseline, all random MAC address must have this bit set to 1 so as to distinguish it from the unique assigned MAC address.
Hence, we have 46 bits that IRM can set randomly.
Then along came SLAP which uses the next two bits, b2 and b3 in the 1st octet to specify four quadrants: extended local (ELI), standard assigned (SAE),
administratively assigned (AAI) and reserved. The proposal (by SA) is that the IRM should always be in the AAI quadrant so now we only have 44 bits that IRM can set to random.
I calculated the effect of having just 44 bits versus 46 on the probabilities of duplicates. The results seem to indicate that it is still rare, but the chance
of duplication is going to be at least 4 times worse with 44 bits than with 46 bits.
Not sure if I answered you question but I did my best :>)
Thanks
Graham
Hi Graham,
What's the exactly requirement to define 44 bits for IRM? Or do you propose to use totally 46-bit for MAC address? I'm not sure I get your
intention. If you want to refine the length of MAC address, we could discuss it in 802.11me group, but it's out of 11bh scope. I'm still confused on the gain of 46-bit MAC address compared with 48-bit MAC address, as SYSTEM always process information based
on unit of BYTE, but not BIT.
Thanks
Best Regards
Jay Yang (杨志杰)
Original
Subject: Re: [STDS-802-11-TGBH] 46 or 44 bit IRMs
Antonio,
I know it's "not for WLAN only." I said it's not being used in WLANs so the inference from that statement is that it must be
for something other than WLAN.
But without any advertisement of SLAP policy—remember, SLAP is not just "44 bits for random MACs", there are other policies enforced
in other quadrants—the STA can only assume there is no SLAP policy being enforced in the ESS and, hence, is free to use all 46 bits to create a random MAC address.
If we really want to bring SLAP into the TGbh draft we'll need to decide what IRM does for the 3 defined quadrants, not just
assume 44 bits are always available. For instance, if the quadrant is "administratively assigned" then the STA can't just decide to use 44 bits for randomization because it's MAC is going to be assigned to it in a fashion that is entirely up to the administrator
of the network. And in that case there is no need for IRM or Device ID, right? The STA is going to be identified by the MAC address it got administratively assigned. No need for TGbh!
This is what is known as a "can of worms", something you don't want to open up. I really don't think we want to bring SLAP into
the TGbh draft.
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Hi Dan, I do not want to go into endless discussions here but please remember SLAP is not for wlan only, it is to enable future
use of the local space in 802 technologies. So there maybe an application of SLAP in the wired part connecting your ESS, and by using the 46 bits you are not allowing other technologies to use it.
I think just going for 46 bits on the basis of wlan not using it right now, is a too wlan centric approach.
Antonio
—
Antonio de la Oliva
Associate Professor, UC3M
Skype: aolivadelgado
Phone: +34916248803
Hi Graham,
I get roughly the same numbers for "results" (slide 8) but I do not agree with your interpretation. There is a problem when two
STAs try to use the same MAC address. That probability is very remote. Even if, as you assume, 80,000 STAs associating (note, I believe the record for simultaneous associations in a single ESS is closer to 30,000 but let's plan for the future) and each one
associates 3 times per day that does not mean there will be 15.75 duplicates per day because these 80,000 STAs are not running through their random MACs simultaneously. The probability of 2 STAs using the same MAC at the same time if there are 80,000 STAs
associating is still 0.000045. It's not 1 (which 15 duplicates per day would imply).
And I agree with Mike. We can use all 46 bits for randomization. Nobody's doing the SLAP for 802.11 networks.
regards,
Dan.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Hi TGbh’s,
At the Interim last week we discussed CID 3085 which proposed to define IRM as follows
:
" A MAC address selected randomly from among the Administratively Assigned local identifiers specified in IEEE Std 802 and used by
a non-access point (non-AP) station (STA) to identify itself to a network."
Using the AA designation means that the IRM would comprise 44 random bits as against 46 bits if we kept to the present “constructed
from the locally administered address space”.
I had previously uploaded, but never presented, 23/2148r0 which looked at the theoretical probabilities of IRM duplicates for ESSs
up to 80,000 stations using IRMs of 46 random bits. I have now posted r1 where I have added the results for IRMs of 44 random bits.
https://mentor.ieee.org/802.11/dcn/23/11-23-2148-01-00bh-probability-of-irm-duplicates.pptx
The results are:
For a busy ESS (network), with each STA associating 3 x per day, storing a high number of IRMs (80,000)
For 46 random bits:
–
Each AP (40) in ESS has a duplicate every 2.54 days
–
Each STA only experiences a duplicate every
14 years.
(i.e., Action frame exchange to get new IRM is a small overhead)
Notes: Assumed 2000 STAs per AP
For S1G (8000 STAs per AP), each AP has 1.57 duplicates per day.
For 44 random bits:
•
Each AP in ESS has a duplicate 1.57 times per day (i.e., 4 times more frequently)
•
Each STA experiences a duplicate every 3.5 years.
Note: For S1G (8000 STAs per AP), each AP has 6.3 duplicates per day
I do not intend to ask Mark for time to present this as it would probably take up a lot of valuable time. I have included all
the formulas and derivations I used, so those interested can check my analysis and results, and of course, I welcome comments. The results are what matters as I have provided above. Of course if anyone feels that my assumptions of the maximum size (80,000)
ESS should be different, or each STA should on average associate more (or less) than 3x a day, please let me know and I will run the numbers accordingly.
I leave it to the group to decide if the effect of reducing the random bits from 46 to 44 is significant enough that we could use
it as a reason to stick with the “locally administered address space”, and not change to “selected randomly from among the Administratively Assigned local identifiers
specified in IEEE Std 802.”?
Thanks
Graham
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
--
Robert Moskowitz
Owner
HTT Consulting
C: 248-219-2059
F: 248-968-2824
E: rgm@xxxxxxxxxxxxxxxxxxxx
There's no limit to what can be accomplished if it doesn't matter who gets the credit
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1