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

–
Tập X gồm n phần tử x
i
.
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ết quả kiểm tra qua bộ lọc: phần tử đó không
thuộc hoặc có khả năng thuộc bộ lọc.
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng8
Ướ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à:






−−=
−
11
1
11
/
2ln
n
m
k
=
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng10
Bộ lọc Bloom đếm
•
Một đặc điểm của bộ lọc Bloom cơ bản là không
thể xoá một phần tử khỏi bộ lọc vì như vậy sẽ
làm xáo trộn những phần tử khác.
•
Người ta đã cải tiến và đưa ra bộ lọc Bloom đếm
trong đó thêm vào một vectơ đếm có độ dài bằng
vectơ bit.
•
Khi thêm vào hoặc xoá một phần tử chỉ cần tăng
hoặc giảm bộ đếm tương ứng, và nếu khi bộ đếm

x
k
x
j
01010 00100
01010 00100
00000
00000
01011
02010 10300 01011
01010 10100
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng12
Lựa chọn hàm băm
1. Theo phương pháp nhân
h(k) = [m * (k * A mod 1)]
–
Trong đó:
–
k – là khoá
–
m – kích thước bảng
–
A - hằng số 0<A<1
–
m thường được chọn là m=2p, m=10p
2. Theo phương pháp chia
h(k) = k mod m
–
k là khoá; m – kích thước của bảng

-FP(%
)
So
sánh
TG
10000 5 72463 2500 334 82 96.76 3.24 1/7.81
50000 5 370000 12500 1532 266 97.87 2.13 1/13.7
100000 5 730000 25000 3197 712 97.15 2.95 1/11.9
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng14
2. Các ứng dụng của bộ lọc Bloom
Bài toán khớp tiền tố dài nhất
2.1
2.2
Bài toán khai phá phần tử phổ biến
2.3
Bài toán phân loại gói tin
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng15
2.1 Bài toán khớp tiền tố dài nhất
Bảng định tuyến trong router
a
Thuật toán khớp tiền tố cổ điển
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ằng16

•
CIDR sử dụng kỹ thuật mặt nạ mạng có chiều
dài thay đổi (VLSM-Variable Length Subnet
Masking) cho phép định vị trí các tiền tố có chiều
dài tùy ý.
•
Khối CIDR IPv4 (W = 32): A.B.C.D/N trong đó
A.B.C.D là địa chỉ IP (A, B, C, D có giá trị từ 0-
255), N chiều dài tiền tố (có giá trị 0-32).
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng18
b. Thuật toán khớp tiền tố cổ điển
•
Ví dụ một khối có địa chỉ bắt đầu là 220.78.168.0
có dạng nhị phân là
11011100.01001110.10101000.00000000;
•
Địa chỉ kết thúc là 220.78.175.0 hoặc
11011100.01001110.10101111.00000000.
•
21 bít (bôi đậm) của hai địa chỉ giống nhau, 3 bít
cuối cùng của octet thứ 3 có giá trị khác nhau từ
000 đến 111.
•
Do vậy đầu vào trong bảng định tuyến trở thành
220.78.168.0/21 hay
11011100.01001110.10101*. Trong đó 21 là
chiều dài tiền tố.
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng19

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ằng21
c. Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
•
Bộ lọc Bloom được sử dụng trong bài toán này
nhằm giúp tăng hiệu quả quá trình tìm kiếm.
•
Bảng định tuyến được chia thành các bảng nhỏ
theo độ dài tiền tố gọi là các bảng băm. Mỗi
bảng băm chỉ chứa tiền tố có cùng độ dài.
•
Mỗi bảng băm được khởi tạo với một bộ lọc
Bloom để hỗ trợ trước khi tìm kiếm.
•
Nếu địa chỉ IP có W bit thì cần dùng W bảng
băm. Mỗi bản ghi trong bảng băm là một cặp
[tiền tố, bước truyền tiếp theo].
GVHD: TS Nguyễn Mạnh Hùng
HVTH: Trương Thị Thu Hằng22
c. Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
•
Chia bảng định tuyến thành các bảng nhỏ theo
độ dài tiền tố gọi là các bảng băm. Mỗi bảng
băm chỉ chứa các tiền tố có cùng độ dài.
•
Giả sử địa chỉ IP có W bit. Cấu trúc bao gồm:
–

c. Khớp tiền tố dài nhất sử dụng bộ lọc Bloom
Prefix Next hop
1* 100.5.2.0
Prefix Next hop
00* 100.5.2.0
01* 100.5.1.0
10* 100.5.3.0
11* 100.5.5.0
Prefix Next hop
001* 100.5.2.0
010* 100.5.1.0
100* 100.5.5.0
111* 100.5.6.0
• Giả sử một gói tin đến với địa chỉ
đích là 1011
• 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ằng25
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