Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00051
PHÂN LOẠI GÓI TIN IPV6 DỰA TRÊN CÂY KẾT HỢP
Nguyễn Mạnh Hùng1, Vũ Duy Nhất2, Thái Trung Kiên3
1
Phòng Sau Đại học, Học viện Kỹ thuật Quân sự
2
Cục Cơ yếu, Bộ Tổng Tham mưu
3
Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Quân sự
Manhhungk12@mta.edu.vn, nhatbest@gmail.com
TÓM TẮT: Các thiết bị mạng như tường lửa, định tuyến, IPS, IDS,… đều phải thực hiện việc phân loại gói tin trước khi có các
hành động cụ thể tùy theo tính năng của thiết bị đối với các gói tin đó. Các thuật toán phân loại gói tin đã và đang được nghiên cứu
phát triển với mục đích làm tăng tốc độ phân loại hay tiết kiệm không gian lưu trữ. Mỗi thuật toán đề xuất đều hướng tới đạt được
kết quả tối ưu trong các điều kiện cụ thể về tính chất dữ liệu đi qua hay tính chất của tập luật phân loại. Các thuật toán phân loại đề
xuất cho gói tin IPv4 có thể không còn hiệu quả khi áp dụng cho gói tin IPv6. Chính vì vậy, nghiên cứu các thuật toán phân loại đối
với gói tin IPv6 sẽ tiếp tục được quan tâm. Trong bài báo này chúng tôi dựa trên cấu trúc cây Đa bit và cây Ưu tiên để đề xuất cấu
trúc cây kết hợp sử dụng để phân loại gói tin IPv6 theo một chiều nhằm tận dụng được các ưu điểm về tốc độ và không gian lưu trữ
trong quá trình phân loại.
Từ khóa: Tưởng lửa, phân loại gói tin, định tuyến, tiền tố, tiền tố khớp dài nhất, bộ lọc.
I. GIỚI THIỆU
Phân loại gói tin là việc mà các thiết bị mạng như thiết bị định tuyến, tường lửa, IPS, IDS, mã hóa đường
truyền,… phải thực hiện trước khi thực hiện một chức năng cụ thể phù hợp với chức năng của nó. Sự gia tăng nhanh
chóng về lưu lượng dữ liệu trao đổi trên mạng đặt ra yêu cầu về thông lượng của các thiết bị mạng phải được nâng cao
và điều này càng trở nên cấp bách khi các thiết bị này được đặt trong các mạng lõi hay các cổng thông tin có lượng truy
cập lớn. Chính vì lý do đó, bài toán nâng cao tốc độ phân loại gói tin trên thiết bị mạng đã, đang và sẽ được nhiều nhà
khoa học quan tâm nghiên cứu.
Việc phân loại chủ yếu được thực hiện dựa trên các thông tin giao thức IP của gói tin. Hiện nay giao thức IPv6
đang được sử dụng để thay thế cho IPv4 nhằm mở rộng không gian địa chỉ mạng khả dụng. Tuy nhiên, việc chuyển đổi
này làm nảy sinh một vấn đề trong bài toán phân loại gói tin: Các thuật toán phân loại gói tin IPv4 không phù hợp khi
áp dụng với các gói tin IPv6 do độ dài địa chỉ IP tăng từ 32 bit lên 128 bit, điều này ảnh hưởng tới tốc độ phân loại và
yêu cầu bộ nhớ lưu trữ. Trong bài toán phân loại gói tin theo địa chỉ IP vấn đề tìm kiếm tiền tố khớp dài nhất - LPM
(Longest Prefix Matching) được quan tâm khá lớn do tính phổ biến của nó trên tất cả các thiết bị mạng nói chung và
thiết bị định tuyến nói riêng. Vấn đề tìm kiếm LPM cũng được đặt ra khi chuyển đổi từ IPv4 sang IPv6, điều này đặc
biệt cần thiết cho việc phát triển các thiết bị mạng ở thế hệ tiếp theo (Next Generation Network - NGN).
Trong bài bào này, chúng tôi sẽ đề xuất cấu trúc cây MIXT (Mixtrure Trie) là sự kết hợp giữa cây Đa bit với cây
Ưu tiên nhằm lưu trữ và tìm kiếm tiền tố khớp dài nhất với một địa chỉ IPv6 một cách hiệu quả. MIXT được xây dựng
dựa trên kết hợp về thế mạnh về tốc độ tìm kiếm của cây Đa bit [1] và thế mạnh về lưu trữ của cây Ưu tiên [2] từ đó
làm giảm dung lượng bộ nhớ và tăng tốc độ phân loại gói tin IPV6.
Phần sau của bài báo được tổ chức như sau: Phần II giới thiệu về các kỹ thuật tìm kiếm LPM trên IPv4 và IPv6
phổ biến hiện nay, trong đó đi sâu phân tích hai cấu trúc cây Đa bit - MT (Multibit Trie) và cây Ưu tiên - PT (Priority
Trie) để làm cơ sở cho đề xuất mới của bài báo. Phần III trình bày về đề xuất cây kết hợp MIXT dựa trên MT và PT,
trong đó gồm các mục mô tả về cấu trúc cây MIXT và các thao tác như xây dựng và phân loại trên cây. Phần IV trình
bày về kết quả thử nghiệm và đánh giá cấu trúc MIXT. Trong phần này nhóm nghiên cứu có thử nghiệm để đánh giá về
tính chính xác của cấu trúc MIXT trong quá trình phân loại cũng như so sánh cấu trúc MIXT với các cấu trúc khác về
tốc độ phân loại cũng như bộ lưu trữ. Phần V là phần kết luận và định hướng nghiên cứu tiếp theo của bài báo.
II. CÁC KIẾN THỨC LIÊN QUAN
2.1. Các kỹ thuật tìm kiếm LPM phổ biến
Các kỹ thuật tìm kiếm LPM phổ biến hiện hiện nay có thể được chia thành các dạng cơ bản sau: Dạng cây
(tree), Dạng trie, bảng băm (Hash table) và dạng mô hình bộ lọc Bloom (Bloom filter).
Các kỹ thuật ở dạng cây có thể kể đến cây tìm kiếm nhị phân - BST (Binary search tree) cây B [3] hay cây nhị
phân tự hiệu chỉnh Splay Tree [4], trong cấu trúc này mỗi tiền tố được lưu trữ tại một nút của cây điều này sẽ dẫn đến
khi số lượng tiền tố nhiều thì chiều cao của cây lớn và chi phí cho bộ nhớ lưu trữ lớn. Trong dạng cây tìm kiếm nhị
phân có cây ưu tiên (Priority tree) [2] được xây dựng nhằm tìm kiếm được LPM một cách nhanh nhất với quy tắc các
tiền tố có độ dài lớn hơn được ưu tiên lưu ở mức thấp hơn tiền tố có chiều dài nhở hơn nó. Các dạng cây khác được đề
xuất là dạng cây quyết định (Decision tree) tiêu biểu là HiCuts [5]. Cấu trúc này tác giả đề xuất nhằm cân bằng giữa bộ
- Vũ Duy Nhất, Nguyễn Manh Hùng, Thái Trung Kiên 387
nhớ lưu trữ và số lần truy cập bộ nhớ trong quá trình tìm kiếm. Nhìn chung các cấu trúc dạng cây này được đề xuất cho
việc phân loại gói tin IPv4, khi áp dụng cho gói tin IPv6 thì chiều cao của cây sẽ tăng đáng kể và điều này sẽ làm giảm
tốc độ tìm kiếm.
Ở dạng thứ hai -Trie, cấu trúc phổ biến được nhắc tới là Radix trie [6], JA-trie[7], Multibit Trie [1]. Nhìn chung
cấu trúc trie thường có hiệu năng tốt về tốc độ tuy nhiên có một đặc điểm chung là chi phí về bộ nhớ khá cao do phải
tạo thêm các dữ liệu trung gian và điều này sẽ càng trầm trọng khi áp dụng trên gói tin IPv6 với độ dài tiền tố và địa chỉ
tăng lên đáng kể.
Các thuật toán dạng bảng băm phổ biến có thể kể đến [8], [9] được đề xuất để tìm kiếm LPM của một địa chỉ IP
đầu vào. Trong [9], các tác giả đề xuất việc thiết lập các bảng băm chứa tiền tố với chiều dài khác nhau và thứ tự tìm
kiếm trong mỗi bảng được định nghĩa dựa trên cấu trúc cây tìm kiếm nhị phân. Các thuật toán dạng bảng băm được đề
xuất sử dụng để tận dụng ưu thế về tốc độ tìm kiếm O(1) và yêu cầu lưu trữ là O(N), tuy nhiên trong cấu trúc dạng này
thường phát sinh thêm các bảng băm trung gian và việc tìm kiếm thực hiện không chỉ ở một bảng.
Mô hình bộ lọc Bloom [10], [11], mô hình này có ưu điểm là số lượng thông tin lưu trữ về các tiền tố nhỏ (dưới
dạng các giá trị băm) nên cải tiến được tốc độ tìm kiếm trung bình. Tuy nhiên một điểm hạn chế của mô hình này là
khả năng sai số có thể xảy ra trong quá trình tìm kiếm, nếu muốn hạn chế sai số thì phải sử dụng các hàm băm có độ
phức tạp tính toán cao nhưng điều này lại chi phí về mặt thời gian tìm kiếm.
Các công bố mới nhất cho việc tìm kiếm LPM trên IPv6 được triển khai trên cơ sở phân tích đặc tính của tập
tiền tố trong việc đinh tuyến gói tin IPv6 qua đó xây dựng các cấu trúc dữ liệu và thuật toán riêng. Tác giả
M. M. VijayaD, Shalini Punithavathani trong [12] sử dụng mô hình bộ nhớ dạng ống (pipeline) song song hóa các
pipeline tuyến tinh trên nền tảng phần cứng Altera Quartus Stratix II device kết hợp với cấu trúc cây B. Giải pháp này
sẽ gặp phải vấn đề là nhu cầu bộ nhớ tăng theo cấp số nhân khi số lượng các tầng pipeline lớn đặc biệt cho dữ liệu đầu
vào là tiền tố IPv6. Các tác giả trong [13], sử dụng mô hình bộ lọc Bloom được bổ sung thêm tính năng phân phối và
cân bằng tải nhằm hạn chế sai số của mô hình Bloom thông thường, tuy nhiên mô hình cũng chưa giải quyết triệt để
được vấn đề này. Trong khi đó các tác giả của [14] sử dụng thuật toán RFC cho việc phân loại gói tin nên sẽ phải đối
mặt với chi phí lớn trong quá trình xây dựng các bảng trạng thái gắn với các pha của thuật toán RFC. Bài báo [15] tìm
kiếm hiệu quả của việc tìm kiếm LPM của gói tin IPv6 trên nền tảng phần cứng FPGA dựa vào tối ưu hóa quá trình
đánh chỉ số và truy xuất bộ nhớ trên nền phần cứng lựa chọn. Các tác giả [16] đề xuất mô hình SHIP đề tìm kiếm LPM
cho gói tin IPv6 bằng cách phân cụm các tiền tố ra thành cách nhóm nhỏ khác nhau dựa vào đặc tính của chúng, trên cơ
sở phân loại đó tác giả đề xuất mô hình lai trie-tree để lưu trữ và tìm kiếm LPM cho gói tin đến. Tuy nhiên mô hình
này chỉ được đánh giá cao bộ nhớ lưu trữ mà chưa có đánh giá về thời gian tìm kiếm.
2.2. Đặc điểm của định tuyến gói tin IPv6
Internet Protocol Version 6 (IPv6) là các công nghệ hỗ trợ chủ yếu của mạng máy tính thế hệ mới. Theo Ủy ban
Kiến trúc Internet (IAB). Một địa chỉ unicast IPv6 bao gồm 2 thành phần: 64 bit network/sub-network ID và 64 bit
hostID.
Phân bố về độ dài các tiền tố được sử dụng trong việc định tuyến gói tin IPv6 tại [17] ngày 25/6/2018, được thể
hiện trong Hình 1.
Phân bố theo độ dài các tiền tố IPv6 của giao thức BGP
50%
40%
30%
20%
10%
0%
19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 63 124
Hình 1. Phân bố theo độ dài tiền tố của giao thức BGP toàn cầu
Một số đặc điểm của địa chỉ IPv6:
- Số lượng các tiền tố có độ dài khác nhau phân bố không đều.
- Các tiền tố có độ dài phổ biến là 32 và 48. Trong đó, tiền có độ dài là 32 chiếm19,96 %, 48 chiếm 46,01 %.
- Số lượng các tiền tố có độ dài lớn hơn 48 là không đáng kể (0,7 %).
- 388 PHÂN LOẠI GÓI TIN IPV6 DỰA TRÊN CÂY KẾT HỢP
2.3. Cây Đa bit
Cây Đa bit MultiBit Trie [1], là cấu trúc cây được đề xuất bởi Srinivasan and Varghese. Cây đa bit là cấu trúc
đon giản dẽ cài đặt và sử dụng cho việc tìm kiếm các giá trị LPM trong quá trình phân loại gói tin một cách hiệu quả.
Cây này có ưu điểm là cải thiện tốc độ tìm kiếm từ O(W) xuống O(W/k) với k là độ dài của bước nhảy. Để có được ưu
thế về tốc độ tìm kiếm thì phải trả giá về bộ nhớ lưu trữ là O(2kNW/k) với việc mở rộng các tiền tố. Tuy nhiên việc mở
rộng giá trị k cũng không phải là vô hạn vì việc quản lý và truy xuất đến 2k nút con tại một nút cũng là vấn đề phức tạp.
Hình 2 thể hiện cây Đa bit với bước nhảy k=2 của bộ lọc gồm 5 tiền tố.
P1=0* ROOT
P2=10* 00 01 10 11
P3=110*
P4=001* P1 P1 P2 P5
P5=11*
01 10 11 00 01 10 11
P4 P4 P3 P3
Hình 2. Ví dụ cây Đa bit bước nhảy k =2
Để hạn chế việc phát sinh bộ nhớ do việc mở rộng các tiền tố, thì cây đa bit với bước nhảy động [18] được đề
xuất. Trong đó, các tác giả xác định các bước nhảy khác nhau với các tầng khác nhau và các nút khác nhau nhằm tối ưu
hóa về mặt lưu trữ (hạn chế việc mở rộng các tiền tố). Tuy nhiên, giải pháp này vẫn không giải quyết triệt để việc phải
mở rộng các tiền tố và đặc biệt chi phí cho việc xây dựng cây là lớn.
2.4. Cây Ưu tiên
Sử dụng cây Ưu tiên cho việc phân loại gói tin được nhóm tác giả [2] đề xuất việc sử dụng cấu trúc cây tìm
kiếm nhị phân nhằm tìm tiền tố dài nhất khớp với một địa chỉ đầu vào. Ý tưởng chính của cây Ưu tiên là: Trong cây
tìm kiếm nhị phân các tiền tố có độ dài lớn hơn luôn nằm ở nút có vị trí cao hơn các tiền tố có độ dài ngắn hơn, điều
này dẫn đến quá trình tìm kiếm sẽ kết thúc ngay khi xác định được một tiền tố phù hợp mà không cần phải tiếp tục để
tìm được tiền tố tốt nhất như các thuật toán tìm kiếm trên cây nhị phân thông thường.
Các tiền tố được sắp xếp theo thứ tự không tăng theo độ dài của nó. Bắt đầu từ một tiền tố với độ dài lớn nhất,
tiền tố được lưu trữ vào nút gốc và được đánh dấu là nút ưu tiên. Tại mức thứ j, tiền tố P được lưu trữ trên nút con trái
hoặc con phải của gốc phụ thuộc vào bit thứ j của tiền tố và đánh dấu như một nút ưu tiên: Nếu nút thứ j của P là „1‟ thì
tiền tố được lưu tại nút con phải, ngược lại sẽ nó sẽ được lưu vào nút con trái. Quá trình này được lặp lại cho mỗi tiền
tố. Tiền tố với độ dài ni được lưu trữ tại một nút ở mức L nhỏ hơn hoặc bằng ni, nếu L= ni nút được đánh dấu như một
nút không ưu tiên.
Cấu trúc cây Ưu tiên PT có các nhược điểm sau:
- PT không phải là cây nhị phân cân bằng nên trong một số trường hợp việc tìm kiếm sẽ không đạt hiệu quả
cao nhất.
- Việc lưu trữ tiền tố trên các nút chưa tối ưu trong trường hợp nếu tiền tố P là tiền tố của Q, thì vẫn cần một
nút để lưu trữ P và việc tìm kiếm sẽ phải thưc hiện thêm một số thao tác không cần thiết.
Hình 3 thể hiện cây Ưu tiên với bộ lọc gồm 5 tiền tố.
P1=0* P4
P2=10*
P3=110*
P4=001* P1 P3
P5=11*
P2 P5
Nút ưu tiên Nút không ưu tiên
Hình 3. Ví dụ cây Ưu tiên
III. ĐỀ XUẤT CẤU TRÚC CÂY KẾT HỢP MIXT DỰA TRÊN CÂY ĐA BIT VÀ CÂY ƯU TIÊN
3.1. Mục tiêu và ý tưởng đề xuất
3.1.1. Mục tiêu
Cây MIXT được xây dựng nhằm tận dụng các ưu điểm của cây Đa bit - MBT và cây Ưu tiên - PT trong khi hạn
chế các nhược điểm của chúng. Mục tiêu đề ra khi xây dựng cây MIXT là cải thiện về thời gian tìm kiếm LPM và chi
phí bộ nhớ lưu trữ.
- Vũ Duy Nhất, Nguyễn Manh Hùng, Thái Trung Kiên 389
3.1.2. Ý tưởng đề xuất
Qua ví dụ về cây Đa bit và cây Ưu tiên với cùng một tập gồm 5 tiền tố đầu vào, chúng ta có các nhận xét sau:
- Cùng với một bộ lọc thì độ cao của cây Đa bit (không bao gồm nút gốc) thấp hơn độ cao của cây Ưu tiên, điều
này càng thể hiện rõ khi bước nhảy k của cây Đa bit tăng lên.
- Số nút trên cây Đa bit (9) lớn hơn số nút trên cây Ưu tiên (5).
- Trong cấu trúc cây Đa bit việc mở rộng chỉ phải thực hiện đối với các tiền tố tại các vị trí khi chiều dài còn lại
của tiền tố nhỏ hơn bước nhảy phải thực hiện (trường hợp đối với P1, P3 và P4).
- Cấu trúc cây Ưu tiên hoàn toàn không phát sinh các nút trung gian.
Từ các nhận xét trên chúng tối đề xuất ý tưởng xây dựng cây kết hợp MIXT dựa trên cây Đa bit và cây ưu tiên
nhằm khắc phục các điểm hạn chế của cây Đa bit và cây Ưu tiên, trong khi vẫn phát huy được các ưu điểm của chúng.
Ý tưởng của đề xuất là: Tại một nút đang xét N, các phần dư của tiền tố sẽ được lưu và tìm kiếm trên cây Ưu tiên gắn
với nút N mà không tiến hành mở rộng các tiền tố đó, với số ít các phần dư thì chiều cao của cây Ưu tiên này là nhỏ.
3.2. Cấu trúc cây hỗn hợp
3.2.1. Đặc điểm cây MIXT
Cây MIXT được xây dựng dựa trên cây Đa bit và cây Ưu tiên có các đặc điểm sau:
- Mỗi cây có bước nhảy k, giá trị này bản chất gống như bước nhảy của cây Đa bit.
- Mỗi nút cây sẽ có 2k nút con, gắn với giá trị của k bit.
- Mỗi nút có một nút con đặc biệt có cấu trúc là cây Ưu tiên để lưu trữ và tìm kiếm đối với các tiền tố phải mở
rộng. Với độ dài bước nhảy k thì số tiền tố phải mở rộng tối đa là 2(k-1) vì vậy số nút con của cây Ưu tiên này
không vượt quá 2(k-1) nút.
3.2.2. Cấu trúc nút trên cây MIXT
Với đặc điểm như trên, mỗi nút trên cây MIXT có cấu trúc như Hình 4 dưới đây.
[PrefixID]
[Backtrack]
Childs
PT-Child
Danh sách các nút con
Nút con đặc biệt chứa các
tiền tố có độ dài còn lại nhỏ
hơn bước nhảy
Chỉ số tiền tố khớp với nút Giá trị đánh dấu tránh phải
tính từ nút gốc quay lui
Hình 4. Cấu trúc nút trên cây MIXT
Trong đó:
- PrefixID: Chỉ số tiền tố khớp tính từ nút gốc.
- Childs: Các nút con từ 0 đến 2k-1 tương ứng với 2k giá trị của k bit được sử dụng.
- Pt-Child: Là cấu trúc cây Ưu tiên, nút này chứa các phần tiền tố còn lại có chiều dài nhở hơn k bit để tránh
việc phải mở rộng tiền tố.
- Backtrack: Giá trị đánh dấu tiền tố khớp dài nhất có thể tính đến nút đang xét, sử dụng để tránh việc phải
quay lui khi quá trình tìm kiếm di chuyển đến nút lá mà không tìm được LMP tương ứng.
Cấu trúc của mỗi nút trong cây Pt-Child là nút của cây Ưu tiên [2] và được thể hiện trong Hình 5.
[Prefix-remain]
PrefixID
Nút con trái Nút con phải
Hình 5. Cấu trúc nút trên cây ưu tiên sử dụng trong cây MIXT
- 390 PHÂN LOẠI GÓI TIN IPV6 DỰA TRÊN CÂY KẾT HỢP
Trong đó:
- Prefix-remain: phần còn lại của tiền tố, đây chính là khóa tìm kiếm.
- PrefixID: chỉ số tiền tố khớp.
Hình dạng tổng quát của một nút của cây MIXT thể hiện trong Hình 6.
[PrefixID] PT-Child
[Backtrack]
[PrefixID -1] PT-Child [PrefixID-2] PT-Child
[PrefixID -2k] PT-Child
[Backtrack -1] [Backtrack -2] [Backtrack-2k]
Hình 6. Cây MIXT tổng quát
3.3. Các thao tác trên cây MIXT
3.3.1. Chèn một tiền tố vào nút
Thuật toán chèn tiền tố Prefix vào nút Node được thể hiện trong Hình 7. Tham số đầu vào của gồm tiền tố
Prefix, chỉ số tiền tố, nút node cần chèn.
Bắt đầu
Cập nhật giá trị Backtrack cho các
- cây con của Node;
Node=NULL
Chèn Prefix vào Node.PT-Child;
+
Khởi tạo Node
- -
Prefix.Len k Prefix.Len =0
+ +
Branch := Value(Prefix.left(k))
Prefix:= Prefix.mid(k); Node.PrefixID=PrefixID
Chèn Prefix vào cây con số Branch của Node;
Kết thúc
Hình 7. Quá trình chèn tiền tố vào nút trên cây MIXT
Việc cập nhật giá trị Backtrack cho các cây con của Node được thực hiện khi độ dài của tiền tố nhỏ hơn bước
nhảy k. Mục đích của việc việc sử dụng Backtrack là tránh việc phải quay lui trong quá trình tìm kiếm. Ý tưởng cơ bản
của việc này là trong quá trình tìm kiếm LPM của một IP đầu vào, đến vị trí nào IP khớp với một tiền tố (chưa xác định
là LPM) thì đánh dấu lại. Quá trình cập nhật giá trị Backtrack cho cây thứ m như sau: Nếu tiền tố Prefix là tiền tố của
chuỗi k bit nhận dạng của cây m và chiều dài của chuỗi Prefix lớn hơn giá trị Backtrack hiện thời thì gán Backtrack
bằng độ dài của chuỗi Prefix.
Thủ tục chèn Prefix vào cây con PT-Child giống như thủ tục chèn chuỗi vào cây Uu tiên.
3.3.2. Xây dựng cây
Quá trình xây dựng cây MIXT được thực hiện bằng việc sử dụng thủ tục chèn tiền tố vào nút. Đầu vào cho quá
trình xây dựng cây là tập P chứa các tiền tố. Quá trình xây dựng cây được thực hiện bằng việc chèn các Pi∊ P vào nút
gốc ROOT của cây MIXT.
- Vũ Duy Nhất, Nguyễn Manh Hùng, Thái Trung Kiên 391
Hình 8 thể hiện cây MIXT với bộ lọc gồm 5 tiền tố.
P1=0*
P2=10* ROOT 0*, P1
P3=110*
P4=001*
P5=11* 00 11
01 10
Backtrack = 1 1*, P4 P2 P5 0*, P3
Hình 8. Ví dụ cây MIXT của 5 tiền tố
3.3.3. Tìm kiếm LPM trên cây MIXT
Thuật toán tìm kiếm LPM trên cây MIXT được thực hiện bắt đầu từ nút gốc - ROOT. Quá trình di chuyển trên
cây giống như cây Đa bit, căn cứ vào giá trị của k bit được cắt ra từ IP đầu vào để xác định nhánh rẽ phù hợp. Điểm
khác biệt so quá trình này trên cây MIXT là:
- Trong trường hợp không tìm được nút để tiếp tục duy chuyển xuống thì quá trình tìm kiếm thực hiện trên
nút PT-Child của nút hiện thời trước khi kết thúc.
- Sử dụng giá trị Backtrack đánh dấu vị trí mà địa chỉ IP đầu vào đã thỏa mãn.
- Thủ tục phân loại trên nút PT-Child là thủ tục tìm kiếm trên cây Ưu tiên.
Thuật toán tìm kiếm LPM trên cây MIXT được thể hiện trong Hình 9.
Bắt đầu
Node = ROOT;
LPM=0;
Offset = 0;
Node=NULL
+
-
IP:=IP.Mid(k);
Branch=Value(IP.Left(k));
Offset:=Offset + k;
Offset > IPLEN
+
-
- -
Node.PrefixID > 0 Node.Backtrack > 0
+ +
LPM = Offset LPM = Offset - k + Node.Backtrack
+ -
LPM = LPM + Node.PT-Child.Search(IP) Node.Child[Branch]=NULL
IP đầu vào khớp với
tiền tố có độ dài LPM
Kết thúc
Hình 9. Thuật toán tìm kiếm LPM trên cây MIXT
IV. THỬ NGHIỆM VÀ ĐÁNH GIÁ
Để đảm bảo sát với ứng dụng thực tế, chương trình sử dụng các bộ dữ liệu được tạo bằng bộ công cụ
ClassBench do David E. Taylor, Jonathan S. Turner thuộc Phòng Nghiên cứu ứng dụng, Khoa Khoa học máy tính, Đại
- 392 PHÂN LOẠI GÓI TIN IPV6 DỰA TRÊN CÂY KẾT HỢP
học Washington, Saint Louis tạo ra [http://www.arl.wustl.edu/classbench]. Bộ dữ liệu bao gồm các tập luật và các tập
tham số gói tin được sinh bởi bộ công cụ trên có dữ liệu đầu vào là những bộ dữ liệu thực của các nhà cung cấp dịch vụ
Internet. Đây là bộ công cụ được cộng đồng nghiên cứu sử dụng để đánh giá các thuật toán và các thiết bị phân loại
gói tin.
Việc thử nghiệm được thực hiện trên nền tảng hệ điều hành Windows10-64bit với cấu hình phần cứng CPU
Intel i5-6200U, 2401MHz; RAM 4Gb. Các cấu trúc cây được xây dựng ngôn ngữ lập trình C# (Visual Studio 2013).
Dữ liệu tập luật (các tiền tố) được nạp trực tiếp vào các cấu trúc cây, dữ liệu gói tin được đọc và lưu vào mảng trước
khi sử dụng cho quá trình phân loại.
4.1. So sánh về sử dụng bộ nhớ
Quá trình thử nghiệm được thực hiện trên 10 bộ dữ liệu, trong đó mỗi bộ dữ liệu bao gồm một tập luật phân loại
và một tập dữ liệu gói tin được tạo với tập luật tương ứng. Thông tin về bộ các dữ liệu được thể hiện trong Bảng 1.
Bảng 1. Các tập dữ liệu thử nghiệm
Tên tập dữ liệu Số tiền tố Số gói tin
ACL1 2996 847.205
ACL2 7068 1.141.601
ACL3 9594 475.662
ACL4 9730 313.385
ACL5 10.000 311.461
FW1 5398 589.408
FW2 9127 357.208
FW3 4273 595.238
FW4 5320 526.691
Quá trình thử nghiệm được tiến hành với cây trên các cấu trúc cây Đã bit - MBT (bước nhảy k=8), cây Ưu tiên -
PT và cây Kết hợp - MIXT (bước nhảy k =8). Kết quả thử nghiệm tại Hình 10 cho thấy: Mức độ sử dụng bộ nhớ trên
MIXT cải thiện đáng kể so với cấu trúc cây Đa bit (MBT). Theo tính toán của chúng tôi, so với cấu trúc cây Đa bit tỉ lệ
bộ nhớ giảm từ 10 % đến 92 % do không phải mở rộng các tiền tố. Nhìn chung, so với cấu trúc cây Ưu tiên thì cấu trúc
MIXT không có ưu điểm về bộ nhớ vì việc không phải lưu một số tiền tố là tiền tố của nhau nhưng phải thêm chi phí
lưu trữ cho trường Backtrack.
Bộ nhớ sử dụng (Kb)
250
200
150
100
50
0
ACL1 ACl2 ACl3 ACL4 ACL5 FW1 FW2 FW3 FW4 FW5
PT MBT MIXT
Hình 10. So sánh nhu cầu sử dụng bộ nhớ giữa MIXT với các cấu trúc khác
4.2. So sánh về thời gian phân loại
Hình 11 là đồ thị thể hiện thời gian phân loại trên các bộ dữ liệu với số lượng tiền tố và số lượng gói tin tương
ứng. Quá trình thử nghiệm cho thấy:
- So với cây Đa bit: Ngoại trừ trường hợp với bộ dữ liệu ACL2 (MBT tốt hơn MIXT) và các FW1, FW3, FW4
(MBT bằng với MIXT) thì cấu trúc MIXT có thời gian phân loại nhỏ hơn cấu trúc MBT. Điều này đã được
nhóm nghiên cứu kiểm tra và phân tích tìm ra nguyên nhân là số lượng các nút trên cây PT-Child của mỗi nút
cây MIXT với bộ dữ liệu ACL2 là khá lớn nên chi phí thời gian tìm kiếm trên các cây con này cao hơn so với
trên cây MBT. Tuy nhiên, chúng ta có thể xem xét cân bằng lợi thế về mặt bộ nhớ của cấu trúc MIXT đối với
MBT trong các trường hợp cụ thể trên.
- Vũ Duy Nhất, Nguyễn Manh Hùng, Thái Trung Kiên 393
- So với cây Ưu tiên: MIXT có hiệu quả hơn về mặt thời gian phân loại điều này phù hợp với phân tích là chiều
cao của cây Ưu tiên luôn lớn hơn chiều cao của cây Đa bit và cây MIXT.
Thời gian phân loại (ms)
250
200
150
100
50
0
ACL1 ACl2 ACl3 ACL4 ACL5 FW1 FW2 FW3 FW4 FW5
PT MBT MIXT
Hình 11. So sánh về thời gian phân loại giữa MIXT với các cấu trúc khác
V. KẾT LUẬN
Phân loại gói tin IPv6 là một vấn đề đang và sẽ cần được quan tâm nghiên cứu. Nâng hiệu quả của quá trình
phân loại chính là mục tiêu của các nghiên cứu đã công bố. Tiêu chí đánh giá hiệu quả của quá trình cải tiến có thể là
một trong hai hoặc cả hai tham số chính: Tốc độ phân loại và dung lượng bộ nhớ sử dụng. Bài báo này đã có đánh giá
tổng quan về các nghiên cứu mới nhất trong việc phân loại gói tin IPv6 hiện nay, trên cơ sở đánh giá đó chúng tôi đã đề
xuất được cấu trúc cây kết hợp giữa cấy Đa bit và cây Ưu tiên nhằm cải thiện cả hai tiêu chí trên. Thử nghiệm cho thấy
cấu trúc MIXT có ưu thế về bộ nhớ rõ rệt đối với hai cấu trúc cây Đa bit và cây Ưu tiên. Bên cạnh đó, trong đa số các
thử nghiệm thì tốc độ phân loại trên cây MIXT cũng tốt hơn hai cấu trúc cây trên. Cây MIXT có cấu trúc đơn giản,
mềm dẻo có thể được áp dụng trực tiếp cho việc phân loại gói tin trên các thiết bị định tuyến và có thể được triển khai
trên thực tế và với các nền tảng phần cứng tiên tiến như FPGA hay ASIC để đạt được tốc độ cao hơn.
VI. TÀI LIỆU THAM KHẢO
[1] V. Srinivasan and G. Varghese. “Faster IP Lookups using Controlled Prefix Expansion”. ACM Transactions on
Computer Systems, Feb:1-40, 1999.
[2] Lim, H., Yim, C., & Swartzlander, E. E. (2010). Priority Tries for IP Address Lookup. IEEE Transactions on
computers, 59(6), 784-794.
[3] H. Le and V. K. Prasanna. “Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning”. IEEE
Transactions on Computers, vol. 61, no. 7, pp. 1026-1039, July 2012.
[4] T. Srinivasan, M. Nivedita, V. Mahadevan. “Efficient Packet Classification Using Splay Tree Models”. IJCSNS
International Journal of Computer Science and Network Security, 6(5), 2006, pp. 28-35.
[5] P. Gupta and N. McKeown. “Packet Classification Using Hierarchical Intelligent Cuttings”. Proc. Hot
Interconnects, 1999.
[6] W. Eatherton, G. Varghese, and Z. Dittia. “Tree bitmap: hardware/software IP lookups with incremental updates”.
SIGCOMM Comput. Commun. Rev., vol. 34, no. 2, pp. 97-122, Apr. 2004.
[7] Gianni Antichi, Christian Callegari, Andrew W. Moore, Stefano Giordano, Enrico Anastasi. “JA-trie: Entropy-
Based Packet Classification”. 2014 IEEE 15th International Conference on High Performance Switching and
Routing (HPSR).
[8] H. Lim, J. H. Seo, and Y. J. Jung. “High Speed IP Address Lookup Architecture Using Hashing”. IEEE Comm.
Letters, vol. 7, no. 10, pp. 502-504, Oct. 2003.
[9] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner. “Scalable High Speed IP Routing Lookups”. Proc. ACM
SIGCOMM, pp. 25-35, 1997.
[10] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor. “Longest Prefix Matching Using Bloom Filters”.
IEEE/ACM Trans. Networking, vol. 14, no. 2, pp. 397-409, Apr. 2006.
[11] K. Lim, K. Park, and H. Lim. “Binary Search on Levels Using a Bloom Filter for IPv6 Address Lookup”. Proc.
ACM/IEEE Symp. Architectures for Networking and Comm. Systems (ANCS), pp. 185-186, 2009.
[12] M. M. VijayaD, ShaliniPunithavathanitrong, Implementation of memory-efficient linear pipelined IPv6 lookup
and its significance in smart cities, Computers & Electrical Engineering, Vol 67, Pages 1-14, 2018.
- 394 PHÂN LOẠI GÓI TIN IPV6 DỰA TRÊN CÂY KẾT HỢP
[13] Haoyu Song, Fang Hao, Murali Kodialam, T. V. Lakshman. IPv6 Lookups using Distributed and Load Balanced
Bloom Filters for 100Gbps Core Router Line Cards, INFOCOM 2009, IEEE.
[14] Zhenqiang, Li Xiaohong, Deng Hongxiao, Ma Yan Ma, Divide-and-Conquer: A Scheme for IPv6 Address Longest
Prefix Matching, IEEE, High Performance Switching and Routing, 2006.
[15] Hiroki NAKAHARA, Tsutomu SASAO, Munehiro MATSUURA, Hisashi IWAMOTO, Yasuhiro TERAO. A
Memory-Based IPv6 lookup architecture using pararrel Index generation Units, IEICE TRANS, INF, Vol E98D,
2015.
[16] Thibaut Stimpfling, Normand Bélanger, J. M. Pierre Langlois, Yvon Savaria. SHIP: A Scalable High-performance
IPv6 Lookup Algorithm that Exploits Prefix Characteristics, EEE/ACM Transactions on Networking, 2017.
[17] http://bgp.potaroo.net/v6/as2.0/index.html.
[18] Sartaj Sahni & Kun Suk Ki. Efficient Construction Of Variable-Stride Multibit Tries For IP Lookup, Symposium
on Applications and the Internet, IEEE 2002.
CLASSIFICATION IPV6 PACKET BASED ON COMBINATION TRIE
Vu Duy Nhat, Nguyen Manh Hung, Thai Trung Kien
ABSTRACT: Network devices as firewall, routing, IPS, IDS… will be execute the calssification packets before decide what is action
according to the those packets. The classification algorithms have found in the development with the target for rapid speed or the
archive space memory. Output output algorithm are direction to obtain the maximum result in the specific specific about the data
through the data or the quality of the package type. The proposed classification algorithms for IPv4 packets may no longer be
effective when applied to IPv6 packets. Therefore, studying the classification algorithms for IPv6 packets will continue to be of
interest. In this paper we rely on the Tree and Priority tree structure to propose the tree structure used to classification IPv6 packet
to take advantage of the advantages of speed and storage space memory in the classification process.
nguon tai.lieu . vn
