Hi Graham,
I think it is very unwise to impose any rules on APs/network to retain information for any period of time, certainly a year is outrageously long. We have traditionally not
made any retention requirements on APs and allow APs to delete information on a STA at any time for any reason or no reason at all. See PMK caching for an example. We should not impose any retention requirements in 11bh.
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 Jerome,
No we did not discuss a firm rule. I suppose an ESS could impose a number limit, then delete oldest in turn if limit exceeded? Or a simple time limit, say delete after 12 months
not used? That may be something WFA might discuss if it decided to take this up?
Of course, it should be an AP vendor answering this;>) But it could only be informative in the TGbh Amendment and probably would take forever to get an agreement as to what to say,
so I suspect there would not be much support to adding anything
Best regards
Graham
From: Jerome Henry <jhenry@xxxxxxxx>
Sent: Thursday, June 6, 2024 4:59 PM
To: G Smith <gsmith@xxxxxxxxxxxxxxxxxxx>
Cc: STDS-802-11-TGBH <STDS-802-11-TGBH@xxxxxxxxxxxxxxxxx>
Subject: RE: [STDS-802-11-TGBH] 46 or 44 bit IRMs
Apologies for not wording my question clearly enough: did we discuss how long the AP should (or is expected to) remember the IRM? (I seem to recall
we discussed this point, but can't find the conclusion we drew, if any).
In the scenario I was sketching below, the AP (or WLC) does not know when the STA may be returning next (tomorrow or in several months), with the obvious
consequence that the AP/WLC may keep on storing more and more IRMs in its memory (increasing the collision risk along the way).
Hi Jerome,
Please see my contribution 23/2148r1 for the answer to your first question of theoretical calculations for the time scales of collisions.
The AP can respond with a “not recognized” for an IRM (or device ID) and then it is up to the STA to either continue to connect or not and to provide a new IRM.
It was recognized that an AP may for any reason delete a saved IRM or device ID. At P35.41 in D4.0 there is text on an AP deleting a device ID. For IRM the relevant text is the paragraph at P39.7. I know there are changes to these texts in the SA Ballot
comments but the ideas remain the same.
AS you say, the more IRMs saved in the ESS, the higher the probability of a duplicate as new IRMs are provided. AS before, in 23/2148r1 I do provide the formulas
which hopefully do explain what happens and the theoretical results. My conclusion is that duplicates are not a problem and the action frame exchange to indicate a duplicate and get a new IRM is not a significant overhead in any way.
Thanks
Graham
Your answers help a lot. Your dialog on the 80K vs 9K changing 3 times a day also surfaces a question in my mind, for which the
answer may be implicit in the baseline, left to implementation or specified in 11bh (but I can't find it): do we have a notion of time for these collisions?
So far, the scenarios I read in the thread seem to assume 9K/80K STAs nicely rotating in unison. But suppose the following scenario:
I drive my soon the 80K students uni, my phone connects to the WiFi (coz I connected when I helped him move in last summer), and
sends the IRM for my next connection.
Then, I drive away happily in the sunset, not to return for weeks or months. The AP (or the WLC behind) keeps repeating in its tiny
head my IRM MAC not to forget it. As 80 K students parents (maybe x2) do the same thing on that back-to-school day, the ESS has all the students and all the parents IRMs. Surely the students will connect back next day, parents won't. Do we have the notion
of timeout for the IRM (I recall we discussed this, but can't find our conclusion)? Our collision probability will increase with the duration for which the IRMs are stored (as the number of IRMs will increase with time until each times out). And at the same
time I may drive back to the Uni the following week and the AP may tell me "IRM not recognized" (which my phone would respond with "wait, what? why? It's me, promised!" but will not understand why that IRM did not work)
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
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
|