Service Identifiers and Bloom Filters

This presentation provides an update on IEEE 802.11-14/1262.r03, focusing on suggested changes to P802.11aq/D1.2 for addressing specific CIDs and proposing more efficient sets of hashes and Bloom Filters. It aims to enhance the representation of services with a significant improvement in efficiency.

• IEEE
• Update
• Service Identifiers
• Bloom Filters
• Efficiency

graelynnp Follow

Uploaded on Feb 15, 2025 | 0 Views

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.

Presentation Transcript

1. May 2015 doc.: IEEE 802.11-14/1262 r03 Service Identifiers and Bloom Filters Date: 2015-5-13 Authors: Name Paul A. Lambert Lei Wang Affiliations Marvell Semiconductor, Inc. Marvell Semiconductor, Inc. Address 5488 Marvell Lane, Santa Clara, CA, 95054 5488 Marvell Lane, Santa Clara, CA, 95054 Phone +1 408 222 8341 +1 858 205 7286 email Paulat Marvelldotcom leileiw@marvell.com Submission Slide 1 Paul A. Lambert, Marvell Semiconductor

2. May 2015 doc.: IEEE 802.11-14/1262 r03 Overview This presentation is an update to 11-14-1262-02 with specific suggested changes to P802.11aq/D1.2 to address CIDs: 1800, 1801 A more very simple and more efficient set of hashes are proposed A more efficient usage of Bloom Filters are proposed to provide a factor of 4 or more improvement in the number of services represented for the same probability Submission Slide 2 Paul Lambert, Marvell

3. May 2015 doc.: IEEE 802.11-14/1262 r03 Current 11aq/D1.0 Bloom Filter Probability For 1000 services (n) the Bloom Filter should be about 1200 octets for a 1% error probability Submission Slide 3 Paul Lambert, Marvell

4. May 2015 doc.: IEEE 802.11-14/1262 r03 Service Hint Field Limits Bloom filter to 254 octets. Calculations would be more efficient if powers of 2 Confusing, why not in Octets to match length. Submission Slide 4 Paul Lambert, Marvell

5. May 2015 doc.: IEEE 802.11-14/1262 r03 Bloom Filter Information Field Not required or useful if this is the maximum number of services Confusing, where is k defined. Submission Slide 5 Paul Lambert, Marvell

6. May 2015 doc.: IEEE 802.11-14/1262 r03 Bloom Filters for Discovery Service Name A UTF8 string value that uniquely identifies a service. This can be a Bonjour, DLNA or other types of identifiers. Example -> service.name.example1 Universal Service Id (USID) A 16 octet unique identifier for a Service Name based on a hash of the Service Name. Example -> 0xa5caec4b28fb241de6ad99a845ee3a82 Hash Value (or Service Id) A 6 octet identifier for a Service Name based on a hash of the Service Name. Example -> 0xa5caec4b28fb Bloom Id An M octet (M<256) identifier for a service that has bits set to one based on k hash calculations. Example -> Bloom Filter An M octet (M<256) string that represents up to n services and is formed by XORing multiple Bloom Id strings together to represent the set of services. Example -> Submission Slide 6 Paul Lambert, Marvell

7. May 2015 doc.: IEEE 802.11-14/1262 r03 Bloom Filter Parameters Bloom Filters represent a set of services detection of a service is by checking by validating that each bit in a service s Bloom ID is contained in the Bloom Filter False postive s indicating service is contained but is not occurs with probability p Parameters M - the size of the Bloom Filter in octets n - the maximum number of expected services in the filter p target probability of false positive detection k number of hash functions used to set bits in a Bloom Id Submission Slide 7 Paul Lambert, Marvell

8. May 2015 doc.: IEEE 802.11-14/1262 r03 Scaling of Filters For M = 254 octets 450.00 For a maximal length filter (per 1.2 draft) the useable size of the set of services is limited for useable probabilities. 400.00 350.00 300.00 N Maximum Services 250.00 200.00 150.00 100.00 A 254 octet filter can represent well roughly 200 services 50.00 0.00 0.000001 0.00001 0.0001 0.001 0.01 0.1 1 P Probability Submission Slide 8 Paul Lambert, Marvell

9. May 2015 doc.: IEEE 802.11-14/1262 r03 Adjusting Bloom Filters Only two parameters fully define a Bloom Filter: The length of the filter M in octets (M=m*8) The number of bits per service k The optimal max number of services and the probability can be calculated from M and k Probability p 0.00001 0.0001 0.001 0.002 0.005 0.01 0.02 0.05 0.1 0.2 0.5 Ratio m/n 23.96 19.17 14.38 12.93 11.03 9.59 8.14 6.24 4.79 3.35 1.44 Calculated k opt 16.61 13.29 9.97 8.97 7.64 6.64 5.64 4.32 3.32 2.32 1.00 Likewise, for n services and a desired probability p, M and k can be calculated Submission Slide 9 Paul Lambert, Marvell

10. May 2015 doc.: IEEE 802.11-14/1262 r03 Bloom Filter Information Number of Services is not required since there are two other parameters available k and m Submission Slide 10 Paul Lambert, Marvell

11. May 2015 doc.: IEEE 802.11-14/1262 r03 Draft 11aq/D1.2 Hash Note that X is already formed from a SHA256 hash Full CRC32 required for each hash value, only 2 bytes used Submission Slide 11 Paul Lambert, Marvell

12. May 2015 doc.: IEEE 802.11-14/1262 r03 More Efficient Hashing Observations 2 byte CRC32 is calculated k times for each service and then mapped mod m SHA256 is already performed and must be created for each service Recommendation Reuse octets from the SHA256 that serve as a unique identifier Each k-th hash could would simply XOR selected octets from the existing hash calculation Very high entropy and quality hash Very simple calculation per new service in filter O(k) XORs Useful since filter changes each time length changes Submission Slide 12 Paul Lambert, Marvell

13. May 2015 doc.: IEEE 802.11-14/1262 r03 Hash Calculation A Bloom Id is formed by setting k bit positions in in the Service Hint Map using k hash functions. for i in range(k): set bit H(i,Ui ,M) The hash functionH(i,U,M) is computed as follows: Let U[ i : i+2 ] represent 2 sequential octets in the octet string U Step 1: Compute A(i,U) = U[ i mod 8, (i mod 8)+2] XOR U[ (int(i/8)+8, int(i/8)+10) Step 2:H(i,U,M) = A(i,U) mod M*8 The hash function H(i,U,M) supports up Bloom Ids with Number of Hash Functions (k) up to 54. Submission Slide 13 Paul Lambert, Marvell

14. Nov 2014 doc.: IEEE 802.11-14/1262 r03 Sequential Bloom Filters Shorter Bloom Filters are possible with the same probability ... If we send multiple different filters Define r filters of length l where sum of length of the r filters is m Effectively trading time (multiple filters in beacons for length) Example: Rather than one 512 octet filter, send 4 128 octet filters Each filter processed separately If desired service is not found in any filter part search can stop Probability incrementally increases with each filter part processed. Possible to have very low false positive probability and shorter transmitted frames Submission Slide 14 Paul Lambert, Marvell

15. May 2015 doc.: IEEE 802.11-14/1262 r03 Sequential Bloom Filters The Bloom Filters sent in successive beacons do NOT need to be the same. A different, but similarly calculated Bloom Filter can be send on successive beacons In observing a transmitted filter, a STA would be able to quickly get a lower probability answer, but could then observe again if result is positive and higher probability desired. Almost identical functionality to current draft Many more services would be able to be represented Would also benefit from simpler hash function to calculate each sequential hash Submission Slide 15 Paul Lambert, Marvell

16. May 2015 doc.: IEEE 802.11-14/1262 r03 Details of Sequential Bloom Filters R filters would be sent sequentially ( r = 0 to R-1) Hash would become H(r,i,U,M) Each shorter Bloom Filter would be processed as per draft with H(r,i,U,M) = H( (i+k*r) ,U,M) Processing multiple different sequential filters would improve the probability on each observation and would would have the full probability of false detection p after all r filters. Processing could stop early if any of the Bloom Filters indicate that a service is not supported (since non- membership is definitive). Submission Slide 16 Paul Lambert, Marvell

17. May 2015 doc.: IEEE 802.11-14/1262 r03 Sequential Bloom Filters Bloom Filter Information field would change to only contain : Number of Hash Functions (k) Number of Sequential Filters (R) Filter Number (r, range 0 to R-1) Submission Slide 17 Paul Lambert, Marvell