1
Nghiên cứu bộ lọc Bloom và ứng dụng
Giáo viên hướng dẫn:
ĐỒ ÁN TỐT NGHIỆP
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng2
Giới thiệu bộ lọc Bloom
•
Được Burton H.Bloom đưa ra năm 1970
•
Bộ lọc Bloom là một cấu trúc dữ liệu rất hiệu quả về
không gian cho việc truy vấn thành viên nhóm, cho
phép bỏ qua các trường hợp không cần thiết phải
tìm kiếm.
•
Các ứng dụng của Bloom:
–
Được sử dụng rộng rãi trong các ứng dụng phân loại gói
tin trên mạng theo dữ liệu của header/nội dung gói tin.
–
Gần đây bộ lọc Bloom còn được sử dụng trong các ứng
dụng mạng: web caching, IP traceback,…
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng3
Nội dung
Lý thuyết về bộ lọc Bloom
1
Các ứng dụng của bộ lọc Bloom:
2
Một số ứng dụng khác
3

GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng6
Cơ chế hoạt động của bộ lọc Bloom
•
Chèn một phần tử vào bộ lọc: Mỗi phần tử x thuộc tập X
được nạp vào trong bộ lọc Bloom theo phương pháp như
sau:
–
Tính toán x qua k hàm băm ta có k giá trị: h
1
(x),…,h
k
(x).
–
K bit có vị trí tương ứng với h
1
(x),…,h
k
(x) trong vectơ bit V
sẽ được gán là 1.
x
h
1
(x) h
2
(x) h
k
(x)h
3
(x)

Ước lượng sai số
•
False Negative: kiểm tra qua bộ lọc là không có
nhưng tìm kiếm thực thì lại có.
•
False Positive: kiểm tra qua bộ lọc là có nhưng
tìm kiếm thực thì không có.
•
Bộ lọc Bloom: không bao giờ xảy ra lỗi false
negative. Chỉ xảy ra lỗi false positive với xác
suất rất nhỏ.
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng9
Ước lượng sai số - False positive
•
Xác suất để một bit được gán là 0 bởi tất cả các
hàm băm là:
•
Đặt p=e
-kn/m
, xác suất của một false positive là:
•
Giả sử cho trước m và n thì giá trị k tối ưu là:
( )
m
nk
eem
mkn
kn
==≈−

11
1
11
/
2ln
n
m
k
=
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng10
Kết quả sử dụng bộ lọc trong bài toán tìm kiếm
Số
phần tử
Số
hàm
băm
Độ dài
vectơ
bit
Số
phần
tử so
sánh
Số
PT
lọc
qua
là có
Số PT

b
Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
c
Chương trình demo
d
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng13
a. Bảng định tuyến router
•
Chuyển tiếp các gói tin
dựa trên địa chỉ IP đích
trong phần Header của
gói tin.
Prefix Next Hop
* N1
0101* N2
100* N3
1001* N4
10111* N5
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng14
b. Thuật toán khớp tiền tố cổ điển
•
LongestPrefixMatching(d )
1. for each length i = [1, length(d)]
2. x = prefix(d, i)
3. {prefix, nexthop} ← Lookup(x, y)
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng15
c. Khớp tiền tố dài nhất sử dụng bộ lọc Bloom

• Lọc qua các bộ lọc giả sử ta có vectơ
khớp (1, 2, 3)
• Tìm kiếm trực tiếp trong các bảng
theo thứ tự: từ 3 đến 2 đến 1
– Bảng HT(3): không có 101
–
Bảng HT(2): có 10 ứng với
nexthop là 100.5.3.0, tìm kiếm
dừng.
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng17
c. Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
–
Địa chỉ IP đầu vào được
kiểm tra song song qua W
bộ lọc Bloom.
–
Mỗi bộ lọc chỉ đơn giản
đưa ra kết quả là khớp hay
không khớp.
–
Vector khớp là tập hợp tất
cả các độ dài tiền tố có
khớp .
–
Tìm kiếm trong các bảng
băm với thứ tự từ tiền tố
dài nhất đến ngắn nhất.
–
Quá trình tìm kiếm dừng

(5.168.3.0,152.133.171.71,…,TCP.
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng20
•
Xây dựng bảng
quy tắc đầy đủ
bằng cách thêm
vào các quy tắc
tích chéo.
•
Bởi vì với tập quy
tắc ban đầu thì
việc tìm kiếm gặp
khó khăn do độ
dài tiền tố của
các quy tắc khác
nhau.
b. Thuật toán tích chéo cổ điển
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng21
•
Bảng quy tắc tích chéo gồm các quy tắc giả
thêm vào, khi đó ta có thuật toán phân loại gói
tin đơn giản như sau:
ClassifyPacket(P )
1. for each field i
2. vi ← LPM(P.fi)
3. {match, {Id}} ← HashLookup(‹v1, . . . , vk›)
•
Tìm tiền tố khớp dài nhất trên mỗi trường, kết

GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng24
•
Chia tập quy tắc thành các
tập con.
•
Tập G1 sinh thêm 1, tập
G2 sinh p2, tập G3 không
sinh thêm.
•
Với mỗi trường ta xây
dựng một bảng LPM xác
định độ dài tiền tố dài nhất
của một tiền tố trong các
tập con.
c. Thuật toán tích chéo đa tập con
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng25
•
ClassifyPacket(P)
•
for each field i
•
t
i
← LPM (P.f
i
)
•
for each subset j