Phân loại gói tin IPV6 dựa trên cây kết hợp

Nội dung text: Phân loại gói tin IPV6 dựa trên cây kết hợp

1. 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 3Việ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ộ
2. 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 %).
3. 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ữ.
4. 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
5. 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] [PrefixID-2] [PrefixID -2k] PT-Child PT-Child 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 Node=NULL cây con của Node; 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.
6. 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
7. 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 [ ]. 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.
8. 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.
9. 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] [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.