Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
MỤC LỤC
1
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
LỜI NÓI ĐẦU
Internet là một kho dữ liệu khổng lồ, mọi người có thể tìm được bất
kỳ thông tin nào về khoa học, sức khoẻ, đời sống, tin tức, và cả việc thông
tin liên lạc qua thư điện tử, chat,…Với những ưu điểm lớn của World Wide
Web, số lượng người sử dụng, máy chủ, các mạng con kết nối vào Internet
ngày tăng với tốc độ chóng mặt. Điều đó cũng đồng nghĩa với việc lưu
lượng lưu thông trên mạng ngày càng tăng lên và dường như quá tải. Để
giải quyết vấn đề đó, những nghiên cứu cả về phần cứng và phần mềm
không ngừng được nêu ra nhằm tăng tốc độ truyền tải trên mạng, tăng tốc
độ xử lý của các thiết bị mạng…Việc sử dụng mạng Internet ngày càng phổ
biến thì cũng càng đặt nhiều vấn đề mới hơn như vấn đề an ninh mạng, vấn
đề bảo mật thông tin trên mạng…
Bộ lọc Bloom do Burton Bloom đưa ra năm 1970 đã cho thấy được
hiệu quả của nó trong việc góp phần giải quyết một số vấn đề về tốc độ và
thời gian xử lý với cơ sở dữ liệu trên mạng. Chính vì thế bộ lọc Bloom
ngày càng được sử dụng rộng rãi trong rất nhiều ứng dụng mạng: định
tuyến IP, phân loại gói tin, chia sẽ bộ nhớ cache trong mạng per to per, IP
traceback, khai phá phần tử phổ biến trong luồng dữ liệu, phát hiện sự xâm
nhập trong hệ thống an ninh mạng Bộ lọc Bloom cũng rất hiệu quả trong
việc xử lý với cơ sở dữ liệu nói chung nên thực sự rất hữu ích trong rất
nhiều ứng dụng thực tế khác.
Trong đồ án tốt nghiệp của mình, em chọn đề tài là “Nghiên cứu bộ
lọc Bloom Filter và ứng dụng” gồm 3 nội dung chính:
- Lý thuyết về bộ lọc Bloom
- Tìm hiểu một số ứng dụng của bộ lọc Bloom: khớp tiền tố dài
nhất, phân loại gói tin và khai phá phần tử phổ biến sử dụng
ESBF theo mô hình Damped.

1
(x)], V[h
k
(x)]
được gán là 1.
Bộ lọc Bloom cơ bản là một vector bit có độ dài m, được sử dụng để
biểu diễn một cách khá hiệu quả một tập phần tử. Cho trước một tập X với
n phần tử, bộ lọc Bloom được khởi tạo như sau: mỗi phần tử x
i
trong X sẽ
được tính toán qua k hàm băm h
1
,…,h
k
để tạo ra k giá trị nằm trong khoảng
[1, m] là h
1
(x
i
), ,h
k
(x
i
) và các bit trong vector m–bit tương ứng có thứ tự là
h
1
(x
i
), ,h
k

(x)],…,V[h
k
(x)] đều
có giá trị là 1 thì x “có thể” có trong tập X với một xác suất nào đó, còn nếu
chỉ cần ít nhất 1 bit có giá trị là 0 thì khẳng định là x không thuộc tập X.
Chúng ta chỉ có thể khẳng định là x “có thể” thuộc tập X là bởi vì
trong vector bit, 1 bit có thể được gán giá trị là 1 nhiều lần bởi nhiều phần
tử trong X khi khởi tạo bộ lọc. Chỉ cần một bit 0 chúng ta có thể khẳng
V
m-1
01000 10100 00010
x
h
1
(x) h
2
(x) h
k
(x)
V
0
h
3
(x)
5
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
định x không thuộc X bởi vì nếu x thuộc X thì tất cả k bit tương ứng sẽ
được gán là 1 khi khởi tạo bộ lọc với phần tử x đó.
Hình 1.2: V[h
1

V
0
V
m-1
01010 10100
00010
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Hình 1.3: Minh hoạ lỗi false positive, các bit V[h
1
(x)], V[h
2
(x)],…,V[h
k
(x)]
được gán bằng 1 bởi các phần tử khác nhau a, b, c, d. Khi kiểm tra phần tử
x, chúng ta thấy tất cả các bit này bằng 1 nên khẳng định là x “có thể”
thuộc X.
Chúng ta sẽ xác định xác suất xảy ra lỗi false positive. Xác suất để
một bit ngẫu nhiên của vector m-bit được gán là 1 bởi 1 hàm băm là
m
1
. Và
xác để bit đó không được gán là 1 là
m
1
1−
. Bởi n phần tử của X là
n
m




−−
1
11
. Đối với mỗi phần
tử sau khi kiểm tra qua bộ lọc thấy rằng có thể thuộc tập X thì tất cả k bit
được xác định bởi k hàm băm phải là 1. Do đó xác suất để một phần tử
thuộc tập X:
01000 10100 00010
h
2
(x) h
k
(x)
V
0
V
m-1
h
3
(x)
a b c d
x
h
1
(x)
7
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
k




−≈
−
1
Vì xác suất này không phụ thuộc vào phần tử cần kiểm tra nên được
gọi là xác suất false positive. Xác suất false positive có thể giảm xuống nếu
chọn giá trị m và k, n thích hợp. Giá trị m–độ dài vector bit cần phải khá
lớn hơn so với n-kích thước tập phần tử. Với tỉ số
n
m
cho trước, xác suất
này có thể giảm xuống nếu tăng số hàm băm. Trong trường hợp tốt nhất,
khi xác xuất false positive được cực tiểu hoá theo k, chúng ta nhận được
mối liên hệ sau:
2ln
n
m
k
=
Xác suất false positive tại điểm tối ưu nhất được cho như sau:
k
f







,
V
m-4
trở lại là 0, điều này sẽ làm xáo trộn x
j
.
Để giải quyết vấn đề này, ý tưởng về một bộ lọc Bloom đếm đã được
đưa ra. Bộ lọc này có thêm một vector đếm có độ dài m tương ứng với mỗi
bit của vector m-bit. Khi một phần tử được thêm vào hoặc xoá đi trong bộ
lọc thì k giá trị tương ứng với k giá trị băm trong vector đếm sẽ tăng lên
hoặc giảm đi 1. Khi một giá trị trong vector đếm được tăng từ 0 lên 1 thì bit
tương ứng trong vector m-bit được thiết lập là 1 và ngược lại khi được
giảm trở về 0 thì bit tương ứng đó được thiết lập là 0.
V
m-1
01000 10100 01011
x
i
h
1
(x) h
2
(x) h
k
(x)
V
0
h
3
(x)

V
0
h
3
(x)
x
j
02010 10300 01011
C
0
C
m-1
x
k
10
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
- m không được là bội số của 10: với m=10p, giá trị h(k) sẽ là p bit
cuối cùng của k trong biểu diễn thập phân.
Với 2 trường hợp trên, h(k) không phụ thuộc đầy đủ vào khoá k mà
chỉ phụ thuộc vào p bit cuối cùng trong khoá k.
Cách chọn tốt nhất là sao cho h(k) phụ thuộc đầy đủ vào khoá k,
thường chọn m là số nguyên tố. Với m là số nguyên tố, sẽ đảm bảo cho một
phân bổ tương đối đều.
1.6.2 Hàm băm sử dụng 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

mạng. Để làm được điều đó nó phải tìm được đường đi tốt nhất trong mạng
dựa trên các thông tin đã có về mạng trên bảng định tuyến.
2.1.2 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. Nó so sánh địa chỉ đích với bảng định tuyến để tìm ra
12
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
một lối khớp, lối này sẽ cho Router biết gói tin sẽ được chuyển đi đâu tiếp.
Nếu Router không khớp một lối nào trong bảng định tuyến và không có
đường mặc định nào thì nó sẽ hủy gói tin.
Mỗi bảng định tuyến bao gồm rất nhiều thành phần. Trong phạm vi
của bài toán đang tìm hiểu, chúng ta giả sử đã có một bảng định tuyến như
bảng 1.1, bao gồm các trường sau:
Prefix: tiền tố được đưa ra bởi CIDR
1
.
Next Hop: bước truyền tiếp theo, đây là địa chỉ của các router kế tiếp.
Prefix Next Hop
* N1
0101* N2
100* N3
1001* N4
10111* N5
Bảng 2.1. Một bảng định tuyến với 5 quy tắc (W = 5)
2.2 Thuật toán khớp tiền tố cổ điển
Kỹ thuật khớp tiền tố dài nhất đã nhận được sự chú ý đáng kể trong
thời gian qua. Điều này đúng với vai trò chủ yếu của nó trong hoạt động
của router Internet. Theo sự phát triển vượt bậc của Internet, Classless
Inter-Domain Routing (CIDR) được chấp nhận rộng rãi nhằm kéo dài đời
sống của IPv4. CIDR yêu cầu Router tìm kiếm các tiền tố địa chỉ có độ dài

biểu diễn các tiền tố thành một đoạn thì 1101* trở thành {11010,11011} =
{26,27}, Giả sử một bảng định tuyến Router bao gồm các tiền tố P1=101*,
P2=10010*, P3=01*, P4=1* và P5=1010*. Địa chỉ đích d=1010100 khớp
với các tiền tố P1, P4, P5. Trong đó P5 là tiền tố dài nhất khớp với d.
Trong định tuyến tiền tố dài nhất, xác định Next Hop cho gói tin có
địa chỉ đích d là Next Hop của tiền tố khớp với d mà có độ dài lớn nhất.
14
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Như vậy với địa chỉ đích của gói tin là d chúng ta có đoạn mã giả mô tả
thuật toán khớp tiền tố dài nhất như sau:
KhopTienToDaiNhat(
d
)
1. for each length
i = [1, length(d)]
2.
x
= prefix(
d
,
i
)
3. {prefix, nexthop} ←
TimKiem
(
x, y
)
Trong đó chúng ta thấy x được gán bằng tiền tố của d có độ dài là i
và sau đó được tìm trong bảng định tuyến. Kết quả cuối cùng là tiền tố
khớp dài nhất x được gán cho y.

lọc được khởi tạo với một tập tiền tố có độ dài tiền tố tương ứng với bộ lọc
đó. Chú ý một điều quan trọng là trong khi các vector bit mà kết hợp với
mỗi bộ lọc Bloom được lưu trữ trong bộ nhớ nhúng thì các bộ đếm kết hợp
với mỗi bộ lọc được giữ bởi một bộ xử lý điều khiển riêng biệt để quản lý
việc cập nhật router. Các bộ xử lý điều khiển riêng biệt với bộ nhớ phong
phú là cấu hình chung của mọi router hoạt động với mức độ cao.
16
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Gom nhóm dữ liệu tiền tố thành các tập theo độ dài tiền tố. Mỗi bảng
băm dùng để lưu trữ tập dữ liệu có cùng độ dài tiền tố. Do đó địa chỉ IP có
W bit nên chúng ta 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]. Trong trường hợp này chúng ta chỉ xét
bảng chuyển tiếp chỉ có 2 trường song trong thực tế có nhiều trường khác
nữa như trường quy tắc, trường giao thức…
2.3.3 Hoạt động
Quá trình tìm kiếm diễn ra như sau: địa chỉ IP đầu vào được kiểm tra
song song qua W bộ lọc Bloom. Tiền tố 1-bit của địa chỉ được đưa qua bộ
lọc mà được khởi tạo bởi các tiền tố 1-bit, tiền tố 2-bit được đưa qua bộ lọc
mà được khởi tạo bởi các tiền tố 2-bit,… Mỗi bộ lọc chỉ đơn giản đưa ra
kết quả là khớp hay không khớp. Tập hợp tất cả các độ dài tiền tố mà kết
quả từ bộ lọc tương ứng là khớp chúng ta có một vectơ, gọi là vectơ khớp.
17
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Hình 2.2: Cấu trúc cơ bản và hoạt động của LPM sử dụng bộ lọc Bloom
Xét một IPv4 mà sau khi lọc qua các bộ lọc chúng ta thấy các độ dài
tiền tố khớp là 8, 17, 23 và 30, chúng ta có vector khớp là {8, 17, 23, 30}.
Nhớ rằng các bộ lọc Bloom có thể đưa ra lỗi false positive nhưng không
bao giờ có lỗi false negative, do đó nếu một tiền tố khớp tồn tại trong cơ sở
dữ liệu thì độ dài tiền tố tương ứng sẽ có trong vectơ khớp. Chú ý rằng số
lượng các độ dài tiền tố trong cơ sở dữ liệu tiền tố - W

khớp
V
k
For
i
=
length
(
V
k
) to
i
= 1
{prefix, nexthop} = BangBam[
V
k
[
i
]] ←
TimKiem
(
V
k
[
i
])
If (
TimKiem
(
V

100.5.5.01011*100.5.6.
0
PrefixNext
hop001010*100.5.2.0010101*100.5.
1.0110101*100.5.3.0111010*100.5.4
.0111101*100.5.5.0111110*100.5.6.
0111111*100.5.7.0
19
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Chương 3:
PHÂN LOẠI GÓI TIN SỬ DỤNG BỘ LỌC BLOOM
3.1 Khái niệm về phân loại gói tin
Phân loại gói tin là một hoạt động của router nhằm phân loại gói tin
dựa trên header thành các lớp tương đương gọi là các dòng (flow). Một
dòng được định nghĩa bởi một quy tắc, ví dụ tập các gói tin mà các địa chỉ
nguồn của nó bắt đầu với các bit tiền tố S và địa chỉ đích của là D, và nó sẽ
được gửi cho cổng máy chủ trên mạng. Mỗi dòng gắn tương ứng một hành
động gọi là xử lý thêm vào – ví dụ gửi tới một hàng đợi cụ thể, xoá bỏ gói
tin hay copy gói tin,… Do đó router phân loại gói tin sẽ có một cơ sở dữ
liệu gồm tập các quy tắc, mỗi quy tắc là tương ứng với một kiểu dòng mà
router muốn xử lý khác nhau. Khi một gói tin đến, router sẽ tìm một quy
tắc khớp với header gói tin để xác định xử lý thích hợp cho gói tin đó.
Tất cả gói tin của một dòng đều tuân theo một quy tắc được xác định
trước và router được xử lý như nhau. Ví dụ một dòng = (địa chỉ nguồn, điạ
chỉ đích) hay một dòng = (tiền tố địa chỉ đích, giao thức).
Xét ví dụ bảng quy tắc với k+1 trường như sau:
Giả sử gói tin đến có header (5.168.3.0, 152.133.171.71,…, TCP),
chúng ta thấy gói tin khớp với quy tức 2 và N, nhưng khi tìm kiếm chúng ta
có nhận được kết quả khớp với quy tắc 2 trước do đó chúng ta xử lý gói tin
này với hành động là A

đây, bộ lọc Bloom được sử dụng trước quá trình tìm kiếm một quy tắc
trong một tập quy tắc. Mỗi tập quy tắc sẽ được nạp vào trong bộ lọc Bloom
tương ứng và khi tìm kiếm một quy tắc thì sẽ tiến hành lọc qua bộ lọc
Bloom đó để kiểm tra xem quy tắc đó có thể có trong tập quy tắc hay
không rồi mới tiến hành tìm kiếm nếu có thể có. Bộ lọc Bloom được sử
dụng rất hiệu quả để tránh được tất cả các trường hợp không có quy tắc nào
khớp thì không cần phải thực hiện quá trình tìm kiếm nữa và kết luận là
không có quy tắc khớp.
21
Giáo viên hướng dẫn: Nguyễn Mạnh Hùng HVTH: Trương Thị Thu Hằng
Chúng ta sẽ lần lượt nghiên cứu các thuật toán phân loại gói tin cổ
điển và dần dần cải tiến nó để sử dụng bộ lọc Bloom sao cho hiệu quả nhất,
giảm thời gian tính toán đồng thời tiết kiệm bộ nhớ và giảm số lần truy cập
bộ nhớ.
3.3 Thuật toán tích chéo cổ điển
Với tập quy tắc ban đầu thì việc tìm kiếm diễn ra rất khó khăn do
mỗi quy tắc có nhiều trường và mỗi trường có tính chất khác nhau, các
trường địa chỉ thì có độ đài tiền tố khác nhau. Do vậy người ta đã đưa ra
phương pháp xây dựng bảng quy tắc đầy đủ bao gồm các quy tắc ban đầu
và quy tắc tích chéo thêm vào. Sau khi đã có bảng quy tắc đầy đủ quá trình
tìm kiếm một quy tắc khớp diễn ra như sau:
Giả sử chúng ta có một bảng có k trường. Đầu tiên thực hiện phép
LPM (khớp tiền tố dài nhất) trên mỗi trường. Đặt v
i
là tiền tố khớp dài nhất
của trường f
i
. Khi đó chúng ta nhận được v
1
, v

i
← LPM(
P.f
i
)
3. {
KetQuaKhop
, {
Id
}} ←
TimKiem
(‹
v
1
, . . . ,
v
k
›)
Chúng ta sẽ tìm hiểu phương pháp tích chéo sau đây để sinh ra các
quy tắc tích chéo. Ta xét ví dụ sau. Giả sử chỉ có 2 trường, f
1
và f
2
. Mỗi
trường có độ rộng 4-bit. Một tập qui tắc có 3 qui tắc r
1
: ‹1*,*›, r
2
‹1*,00*›,
r

và r
1
sẽ cùng được trả về. Tức là r
2
khớp với
cả r
2
và r
1
. Tương tự, r
3
khớp với cả r
3
và r
1
.
Giả sử có một gói tin đến và trường f
1
có tiền tố khớp dài nhất là
101*, trường f
2
là 00*. Không có qui tắc gốc ‹101*,00*›. Tuy nhiên, chú ý
rằng 1* là một tiền tố của 101*. Do đó, một kết quả khớp với tiền tố chi tiết
hơn 101* cũng là một kết quả khớp với các tiền tố có mức chi tiết thấp hơn
1*. Nên khoá ‹101*,00*› cũng khớp với quy tắc r
2
: ‹1*,00*›. Để quá trình
tìm kiếm thực hiện đúng, chúng ta thêm vào một qui tắc giả: p
2
: ‹101*,00*›

i
in field 2)
3. if <
u
i
,
v
i
> not in BangBam
4. then if CoQuyTacCha(<
u
i
,
v
i
>)
5. then ThemVaoBangBam(<
u
i
,
v
i
>)
6. End If
7. End if
8. End for
9. End for
Quá trình tìm kiếm thực hiện trên các trường riêng lẻ sẽ dừng khi tìm
thấy tiền tố khớp dài nhất, những tiền tố này là nguyên nhân tạo ra các qui
tắc được xây dựng bởi các tiền tố con của nó. Nếu một qui tắc được xây