PHÂN LOẠI CÁC GÓI IP

Chia sẻ: Thanh Tuấn | Ngày: | Loại File: DOC | Số trang:60

Thêm vào BST

Báo xấu

167
lượt xem 51
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Theo truyền thống, các bộ định tuyến Internet chỉ cung cấp dịch vụ tốt nhất bằng cách xử lý mỗi gói tin gửi đến theo cách tương tự. Với sự xuất hiện của các ứng dụng mới, nhà cung cấp dịch vụ internet (ISP) sẽ giống như các bộ định tuyến để cung cấp QoS cấp độ khác nhau cho các ứng dụng khác nhau. Để đáp ứng các yêu cầu, QoS, router cần phải thực hiện cơ chế mới, chẳng hạn như kiểm soát nhập liệu, dự phòng tài nguyên, sắp xếp mỗi luồng và lập lịch biểu công...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: PHÂN LOẠI CÁC GÓI IP

̣ ́ ́ PHÂN LOAI CAC GOI IP 1
1.1.Giới thiệu: Theo truyền thống, các bộ định tuyến Internet chỉ cung cấp dịch vụ tốt nhất bằng cách xử lý mỗi gói tin gửi đến theo cách t ương t ự. V ới s ự xu ất hi ện của các ứng dụng mới, nhà cung cấp dịch vụ internet (ISP) sẽ giống như các bộ định tuyến để cung cấp QoS cấp độ khác nhau cho các ứng d ụng khác nhau. Đ ể đáp ứng các yêu cầu, QoS, router cần phải thực hiện cơ ch ế mới, chẳng h ạn như kiểm soát nhập liêu, dự phòng tài nguyên, săp xêp mỗi luông và lập lịch biêu ̣ ́ ́ ̀ ̉ công bằng. Tuy nhiên, một điều kiện tiên quyết để triển khai các cơ ch ế này là các router có thể phân biệt và phân loại các luồng dữ liêu trong cac lưu lượng ̣ ́ khác nhau. Chúng ta gọi các bộ định tuyến như dòng thiết bị định tuyến nhận thức được. Một bộ định tuyến lưu lượng được phân biệt từ một bộ định tuyến truyền thống ở chỗ nó có khả năng theo dõi các luồng đi ngang qua và áp dụng các lớp khác nhau của dịch vụ cho mỗi luông. ̀ Lưu lượng được quy định bởi cac quy tăc và mỗi quy tắc bao gồm các ́ ́ hoạt động so sánh các trường gói tin có giá trị nh ất đ ịnh. Chúng ta g ọi m ột phân loại cua một bộ quy tắc, được hình thành dựa trên tiêu chuẩn đ ược áp d ụng đ ể ̉ phân loại các gói dữ liệu đối với một ứng dụng mạng cung cấp. Cho m ột phân loại các thuộc tính xác định gói tin hoặc nội dung, gói phân lo ại là quá trình xác định các quy tắc, quy định này mà một gói tin phù hợp ho ặc thich nghi . Để minh ́ họa cho các loại dịch vụ có thể được cung cấp bởi một bộ định tuy ến flow- aware với khả năng phân loại gói tin, chúng ta sử dụng môt ví dụ phân loai chỉ ra ̣ ̣ trong Bảng 1.1. Giả sử phân loại này được lưu trữ trong các bộ đinh tuyên R ̣ ́ trong mạng , ví dụ chỉ ra trong hình 1.1. Bang 1.1. Ví dụ về phân loai: ̉ ̣ Lớp mang ̣ Lớp truyên tai ̀̉ Lớp thủ tuc ̣ 2
́ ́ ̀ Giao thưc ́ Đich Ứng dung ́ ̣ ̣ ̣ Quy tăc Đich Nguôn Hoat đông Từ chôi ́ R1 128.238/16 * TCP =Telnet * Gửi tới công số 3 ̉ R2 176.110/16 196.27.43/24 UDP * RTP Ngăt lưu lượng ́ R3 196.27.43/24 134.65/16 TCP * * nêu tôc độ > 10Mbps ́ ́ ́ R4 * * * * * Cho phep Hinh 1.1: Ví dụ về phân loai mang ̀ ̣ ̣ Chỉ với bốn quy tắc trong ví dụ phân loại, các router X cung cấp các dịch vụ sau: Loc goi. Quy tắc R1 khóa tất cả các kết nối telnet từ bên ngoài vào ̣ ́ mạng A, trong đó có thể là một mạng tim kiêm riêng. ̀ ́ Đinh tuyên lưu lượng. Quy tắc R2 cho phép các router chuyển tiếp tất ̣ ́ cả lưu lượng truy cập thời gian thực sử dụng giao thức vận chuy ển th ời gian thực (RTP) trong lớp ứng dụng từ Net B tới Net D thông qua mạng lưới máy ATM ở dưới cùng của hình 3.1. Lưu lượng hoat đông. Quy tắc R3 giới hạn tổng số kiểm soát giao ̣ ̣ thức truyền tải (TCP) tỷ lệ lưu lượng truy cập từ C sang B lên đến 10 Mbps. 3
Một mô tả chính thức của các phân loại, quy tắc, và phân loại gói tin được đưa ra trong cach lam của Lakshman và Stiliadis. Chúng t a sẽ sử dụng ́ ̀ những ký hiệu và thuật ngữ trong suốt chương này. H E A D E R Incoming packet Matching the packet header to the rules in the classifier ̀ ̣ ́ Hinh 1.2: Phân loai goi 1. Một phân loại C bao gồm N quy định, RJ, 1 ≤ j ≤ N, nơi RJ gồm có ba thực thể: (a) Một xuât hiện thường thây RJ [i], 1 ≤ i ≤ d, trên từng trường đầu d ́ ́ của gói. (b) Một số lượng, Pri (RJ), chỉ ra các ưu tiên của các quy tắc trong phân loại này. (c) Một hoat động, được gọi là hoat động (RJ). ̣ ̣ 2. Một gói tin gửi đến P với tiêu đề coi như là d-tuple (P1, P2,..., Pd) được cho là phù hợp RJ, nếu và chỉ nếu, Pi chăn RJ [i], với 1 ≤ i ≤ d. ̣ 4
3. Với một gói P đi vào và do đó các d-tuple, các chiều d phân loai gói ̣ tin là tìm các quy tắc R m với ưu tiên cao nhất trong số tất cả các quy tắc RJ phù hợp với d tuple. Như được thể hiện trong hinh 1.2, một phần đầu gói, bao gồm ̀ địa chỉ nguồn IP (32 bit), địa chỉ đích (32 bit), s ố c ổng ngu ồn (16 bit), đên số ́ cổng đich (16 bit), và các loại giao thức (8 bit) 1, đ ược s ử d ụng đ ể phù h ợp v ới ́ quy tắc (s) trong phân loại này. Việc với môt ưu tiên cao nhất là lựa chọn và ̣ hành động của nó tương ứng được áp dụng cho gói. Trong phân loại như thể hiện trong Bảng 1.1, từng có 5 nguyên tắc biểu thức thông thường trên 5 trường tiêu đề gói từ lớp mang tới lớp ứng dụng. ̣ Mỗi biểu hiện có thể là một tiền tố đơn giản/chiều dài hoặc phân loai điều ̣ hành /hệ số. Các phân loai tiền tố / chiều dài có đich đên như trong tra cứu IP, ̣ ́ ́ trong khi các nhà điều hành/hệ số có thể được tổng quát hơn, ch ẳng hạn nh ư băng 23, phạm vi trong 256-1023, và lớn hơn 1023. Hơn nữa, ký t ự đ ại di ện cho ̀ phép sẽ được chèn vào để phù hợp với bất kỳ giá trị nao. Lưu ý rằng R4 trong ̀ Bảng 1.1 phù hợp với bất kỳ gói tin nao gửi đến do đặc điểm kỹ thuật “tất cả ̀ các ký tự tiêu chuân"của nó, có nghĩa là những ưu tiên c ủa quy đ ịnh này có hi ệu ̉ lực khi một gói tin phù hợp với cả hai R4 và các quy định khác. Giả sử có một bộ quy tắc C = RJ (1 ≤ j ≤ N) và quy tắc m ỗi c ổng RJ có d trường. Các trường được dán nhãn là Fi (1 ≤ i ≤ d) và RJ đ ược ký hi ệu là Rj1, Rj2,. . . , Rjd. Bảng 1.2 cho thấy một ví dụ phân loại với bảy nguyên tắc trong bốn trường. Hai trường đâu tiên, F1 và F2, được quy định trong các tiền tố và hai ̀ trường cuôi cung, F3 và F4, được quy định trong phạm vi. Cột cuối cùng cho thấy ́̀ các hành động kết hợp với các quy tắc. F1 và F2 có thể được xử lý hiệu quả hơn bằng cách sử dụng thử TCAM như trong Chương 2. Mặt khác, F 3 và F4 có thể được xử lý hiệu quả hơn bởi chiếu các số vào phạm vi khác nhau và sau đó thực hiện phạm vi tra cứu, được mô tả trong phần sau của ch ương này. B ảy nguyên 5
tắc được liệt kê theo thứ tự ưu tiên giảm dần, có nghĩa là, R1 có ưu tiên cao nhất. Điều này đặt quy tắc sẽ được sử dụng để minh họa cho một s ố các thu ật toán được mô tả sau đó. Bang 1.2: Ví dụ về bay nguyên tăc trong 4 trường: ̉ ̉ ́ ́ ̀ ̣ Nguyên tăc F1 F2 F3 F4 Hanh đông R1 00* 110* 6 (10, 12) Act0 R2 00* 11* (4, 8) 15 Act1 R3 10* 1* 7 9 Act2 R4 0* 01* 10 (10, 12) Act1 R5 0* 10* (4, 8) 15 Act0 R6 01* 10 (10, 12) Act3 R7 * 00* 7 15 Act1 Một vài số liệu hiệu suất [3] được sử dụng để so sánh và phân tích các thuật toán phân loại gói tin: Tốc độ tìm kiếm. Liên kết tốc độ cao yêu cầu phân loại nhanh. Ví dụ, giả sử một 40-byte cỡ tối thiểu các gói IP, liên kết hoạt động ở 10 Gbps có th ể mang 31.250.000 gói / giây (mpps). Thời gian phân loại được giới hạn đến 32 ns. Yêu cầu bao quan. Lưu trữ có nghĩa là bộ nhớ nhỏ tốc độ truy cập ̉ ̉ nhanh và tiêu thụ điện năng thấp, mà là quan trọng cho phần mềm dựa trên thuật toán-phần cứng dựa trên bộ nhớ cache và các thuật toán-SRAM. Khả năng mở rộng trong phân loai Kích thước. Kích thước của phân ̣ loại phụ thuộc vào các ứng dụng. Đối với môt bộ đinh tuyên metro / edge th ực ̣ ̣ ́ hiên viêc nhận biêt lưu lượng là rât nho, số lượng các dòng chảy là từ 128k tới 1 ̣ ̣ ́ ́ ̉ triệu. Rõ ràng, con số này tăng lên khi tốc độ liên kết tăng. 6
Khả năng mở rộng trong trường Header. Khi có thêm các dịch vụ phức tạp được cung cấp, cac trường Header cân phai được thêm vao. ́ ̀ ̉ ̀ Thời gian câp nhât. Khi các phân loai được thay đôi, chẳng hạn như ̣ ̣ ̣ ̉ một xóa hoặc chèn vào, cấu trúc dữ liệu cần được cập nhật. Một s ố ứng d ụng như ﬂow-recognition đòi hỏi thời gian cập nhật ngắn. Nếu không, vi ệc th ực hiện phân loại bị huy. ̉ Tính linh hoạt trong Đặc điểm kỹ thu ật . Khả năng của một thuật toán để xử lý một loạt các chi tiết kỹ thuật quy định, ch ẳng h ạn như ti ền t ố / chiều dài, nhà điều hành /hệ số, và ký tự đại diện, cho phép nó được áp dụng cho cac trường hợp khác nhau. ́ Tìm kiếm tuyên tinh là các thuật toán đơn giản nhất để phân loại gói ́́ tin. Các bộ quy tắc có thể được tổ chức thành một mảng hoặc liên kết một danh sách theo thứ tự tăng chi phí. Với một tiêu đề gói tin g ửi đ ến, các quy t ắc đ ược kiểm tra từng cái một cho đến khi môt cai phù hợp được tìm thấy. Đối với một ̣́ quy tắc phân loại N, cả thời gian lưu trữ và truy v ấn ph ức t ạp là O (N), làm cho kế hoạch này không khả thi đối với các bộ quy tắc lớn. Nhiều gói tin hệ thống phân loại hiệu quả đã được đề xuất và được mô tả trong các phần sau. ̣ ́ 1.2: Phân loai trie gôc. ́ 1.2.1- Trie phân câp Trie phân câp là một phần mở rộng đơn giản của một chiều trie đến ́ một kích thước đa trie , mỗi chiều đại diện cho một trường. Nó còn đ ược g ọi là đa cấp trie, trie quay lui, tìm kiếm, hoặc đơn trie tới đa trie. Nguyên tăc tổ chức lưu trữ. Một chiều phân cấp trie kep đại diện cho ́ ́ hai trường đầu tiên của bộ quy tắc C trong Bảng 1.2 th ể hi ện trong hình 1.3. Ở đây, chúng tôi chỉ tính F 1 và F2, vì chung là tiền tố và có thể dễ dàng xử lý bằng ́ 7
cách sử dụng nhiêu trie. Các nút ellipse thuộc về các nút F 1 đơn trie và vòng ̀ thuộc về F2 đa trie. Các mũi tên cong đậm biểu thị con trỏ trie tiếp theo. Lưu ý rằng có bốn F1 đa trie bởi vì chúng ta có bốn tiền tố khác biệt trong trường F 1 của C. Mỗi nút màu xám có dán nhãn với một quy tắc RJ, có nghĩa là n ếu nút này đạt được trong quá trình tìm kiếm, RJ được tương quan. Nhìn chung, các trie phân cấp có thể được xây dựng như sau: môt trie cơ s ố nhị phân, đ ược g ọi là F 1 ̣ trie đầu tiên được xây dựng cho các thiết lập của ti ền t ố {Rj1} thu ộc F 1 của tất cả các quy tắc. Thứ hai, đối với mỗi tiền tố p trong trie F 1, một (d - 1) chiều dọc là trie đệ quy Tp xây dựng đối với những quy t ắc xác đ ịnh chính xác p trong F 1, đó là các bộ quy tắc {RJ | Rj1 = p} . Trie Tp đ ược k ết n ối v ới p b ởi m ột con tr ỏ trie tiếp theo được lưu trữ tại nút p. Phân loai. Phân loại cho một gói tin đến với các tiêu đề (v 2, v1,vd) nên ̣ được thực hiện trong các thủ tục sau đây: Các thuật toán truy v ấn đi qua các trie F1 dựa trên v1, nếu một con trỏ trie tiếp theo được găp nhau, các thuật toán sẽ ̣ diễn ra với con trỏ và truy vấn (d - 1) phân cấp trie chiều đệ quy. Đối với các quy tắc trên tập C, được đưa ra một gói tin đ ến (001, 110), quá trình tìm kiếm bắt đầu từ F 1 trie để tìm ra phù hợp với tiền tố tốt nh ất c ủa '001 '. Sau khi nút "D" trong trie F 1 đạt được, các con trỏ trie tiếp theo được sử dụng để hướng dẫn việc tìm kiếm vào trong trie F 2 để tìm tất cả các tiền tố phù hợp của '110 '. Rõ ràng, cả hai nut R 2 và nút R1 là đạt, tuy nhiên, chỉ R1 được ghi ́ do ưu tiên cao hơn của nó. Bây giờ quá trình tìm kiếm cac track trước t ới nút 'B', ́ là mức sơ khởi thấp nhất của nút "D" trong trie F 1. Một lần nữa, chúng ta sử dụng con trỏ trie kế tiếp ở đây để tìm kiếm các F2 trie. 8
Hinh 1.3: Phân câp cấu trúc dữ liệu trie cho F 1 và F2 của các quy tắc ̀ ́ trong Bảng 1.2. Thủ tục này được lặp đi lặp lại cho đến khi không có nút kh ởi đâu c ủa ̀ nút "D" có sẵn để được tìm kiếm. Trong ví dụ này, quá trình tìm ki ếm k ết thúc tại nút x và toàn bộ đường đi được mô tả bằng đường nét đứt trong hình 1.3. Trong chỗ giao nhau này, ba nut được tìm thấy, R1, R2, và R6. R1 được trở lại như ́ nguyên tắc ưu tiên cao nhất xuất hiện. Quá trình quay lai là cần thiết vì '001 'của ̣ các gói đi vào có thể phù hợp với một số tiền tố trong trường đ ầu tiên và chúng ta không biêt trước đó trie F2 có chứa tiền tố (es) phù hợp với '110'. Hơn nữa, tất ́ cả cac nut phải được tìm thấy để đảm bảo rằng một trong nh ững ưu tiên cao ́ ́ nhất được trả về. Chú thich. Cấu trúc trie là một trong hầu hết các thuật toán l ưu trữ tôi ́ ́ ưu. Đối với một bộ quy tắc N, mỗi trong số đó là với trường phụ d và độ dài tối đa của mỗi trường là W, sau đó lưu trữ phức tạp là O (dW). Các cấu trúc dữ liệu là đơn giản và dễ dàng để duy trì mức sử dung của m ột th ời gian dài tìm ki ếm. ̣ Trie giao nhau mang track trở lai trong một nỗ lực để tìm tất cả các quy định phù ̣ hợp do mức độ ưu tiên không thể hiệu quả bằng cách này đê ̉ ph ản ánh c ấu trúc dữ liệu. Thời gian tìm kiếm truy xuât là O (W d).Trie Fd có độ rông c ủa W và do ́ ̣ đó mất O (W) để tìm kiếm.Trie Fd cũng có một chi ều rông W, trong đó m ỗi nút ̣ 9
có một trie Fd. Thời gian tìm kiếm trường hợp xấu nhất cho các Fd-trie là nh ư vậy, O (W2). Với cảm ứng, thời gian truy vân trở thành O (W d). C ập nhật tac ́ ́ hợp có thể được thực hiện trong O (d 2 W) vì mỗi trường quy luật cập nh ật được lưu trữ trong một vị trí chính xác ở F độ rông tối đa O(dW). ̣ 1.2.2- Trie sơ lược Các trie sơ lược là một phiên bản sửa đổi của trie phân c ấp. Phan hôi là ̉ ̀ để tránh trong quá trình truy vấn cho một trie sơ lược. Nguyên tăc tổ chức lưu trữ. Trong một trie sơ lược, mỗi node trie (với ́ một tiền tố hợp lệ) sao chep tất cả các quy định trong quy luât thiêt đăt ban đâu ́ ̣ ́ ̣ ̀ vào bộ quy tắc riêng của chinh nó và sau đó xây dựng các kich th ước trie kê ́ tiêp ́ ́ ́ dựa trên các bộ quy tắc mới. Một ví dụ về các trie sơ lược 2 đường biểu thị trường F 1 và F2 của các quy tắc C (Bảng 1.2) được thể hiện trong hình 3.4. Lưu ý rằng trong Hình 1.3 quan lý bộ trie node F1-A, B, và D là R7 {}, {R4, R5, R6}, và {R1, R2}, tương ̉ ứng. Trong khi trong hình 1.4, chúng được R7 {}, {R4, R5, R6, R7}, và {R1, R2, R4, R5, R6, R7}, nơi mà các quy tắc đã được nhân đôi. Phân loai. Quá trình tìm kiếm cho môt tuple-d bao gồm các kết hợp tiền ̣ ̣ tố d liên tiếp dài nhất trên mỗi chiều của trie sơ lược. Cho m ột tuple 2 (001, 110), đường truy vấn được miêu tả bằng đường nét đứt trong hình 1.4. R1 đ ược trở lại như nguyên tắc ưu tiên cao nhất xuất hiện. Nhiều quy tắc có th ể g ặp phải doc theo đường dân và ưu tiên cao nhất được ghi lại. Các nút R 2 trên đường ̣ ̃ dân được cho là bao gồm các quy tắc R2 và R6, nhưng chỉ được giữ R2 do ưu ̃ tiên cao hơn của nó. Chú thich. Cấu trúc trie cần được phan hôi vì các quy luât thiêt đăt ́ ̉ ̀ ̣ ́ ̣ được kêt hợp với các node F1 trie là rời rạc với nhau. Trie sơ lược loai bỏ nhu ́ ̣ cầu này và giảm độ phức tạp thời gian truy vấn để chỉ O (dW) tại các chi phí 10
lưu trữ phức tạp tăng lên, O (N d dW), vì một nguyên tắc có th ể c ần ph ải đ ược nhân đôi lên đến N d lần . Sự phức tạp cập nhật cũng là O (N d). Hình 1.4- Cấu trúc dữ liệu trie sơ lược cho các nguyên t ắc quy đ ịnh t ại Bảng 1.2. 1.2.3-Trie lưới Srinivansan et al đề xuất cấu trúc dữ liệu trie lưới cho phân loại 2D (2- chiều), làm giảm sự phức tạp lưu trữ tới O (NdW) trong trie phân câp, trong khi ́ vẫn giữ sự phức tạp thời gian truy vấn tại (O dW) bởi trước khi tính toán và lưu trữ được gọi là cac điêm chuyển đổi trong một vai node F 2-trie. Nó được đề cập ́ ̉ ̀ ở trên mà các node trie-F1 cua cac trie sơ lược đặt các quy tắc lăp lai thuộc mức ̉ ́ ̣ ̣ sơ khai. Thủ tục này cũng có thể được hiểu rằng các node F 1-trie kết hợp các node F2-trie sơ khai của nó vào F2-trie chinh nó. Ví dụ R7 trong F2-trie của nút A ́ trong Hình 1.4 được lăp lai ba lần. Giả sử rằng F 2-trie thuộc nút B được ký hiệu ̣̣ là F2-trie-B, sự khác biệt duy nhất giữa hai F2-trie-B trong hình 1.3 và 1.4 là nút R7 được lăp lai trong trie sơ lược. Bây giờ thay vì lăp lai node, một con trỏ ̣ ̣ ̣ ̣ chuyển mạch nhãn với "0" được kết hợp ở nút x và điểm nút R 7 trong trie F2-A như trong hình 1.5. Các con trỏ chuyển đổi được mô tả bởi các mũi tên cong đứt. Trong thực tế, con trỏ chuyển mạch nhãn "0" ở nút x’ thay thế các con tr ỏ 0 trong trie sơ lược. 11
Nếu trie phân cấp và trie sơ lược đã được xây dựng để cho phân loai C, ̣ câu truc các trie lưới của C có thể được xây dựng bằng cách thêm các con trỏ tới ́ ́ cac trie-F2 của trie phân cấp so sanh với các trie sơ lược. Một con trỏ chuy ển ́ ́ đổi, ps, dán nhãn với 0/1 được đưa vào node y bất cứ khi nào trie sơ lược chứa một điêm 0/1 đến một nút z khac trong khi y thì không. Node z có thể có một số ̉ ́ đối tác trong trie phân cấp, nhưng cac điêm ps cua nó được chứa trong trie-F2 đó ́ ̉ ̉ là 'điêm gần nhât' cho trie có chứa node-F 2 y. Ví dụ, node x và node x’ trong hình ̉ ́ 1,4 và 1,5 đêu là đối tác của node x’’ trong hình 1.4. Tuy nhiên, con trỏ chuyển ̀ đổi tại các node điêm y tới node x’ từ node B là gần node D hơn so với node A. ̉ Nếu các con trỏ chuyển đổi được xem giống như cac điêm 0/1, thủ t ục truy vấn ́ ̉ giống hệt như trong trie sơ lược. Câu truc cac trie lưới hoạt động tốt trên cả thời gian truy vấn và lưu trữ ́ ́ ́ phức tạp, nhưng thông tin cập nhật gia tăng rất phức tạp vì một số con trỏ có thể trỏ đến một node duy nhất. Nếu node này được gỡ bỏ, một node mới cần phải được tạo ra và các con trỏ cần phải được cập nhật để trỏ đến các node mới. Hình 1.5 Ví dụ về câu truc cac trie lưới cho các nguyên tắc quy đ ịnh t ại ́ ́ ́ Bảng 1.2 1.2.4- Đề an mở rông hai chiêu ́ ̣ ̀ 12
Baboescu et al đã giới thiệu một phương pháp phân loại mới EGT-PC cho bộ định tuyến lõi. Ý tưởng chính là sử dụng các đặc điểm quy định của cơ sở dữ liệu, chung được phát triên trong các bộ định tuyến lõi để giảm sự phức ́ ̉ tạp của tìm kiếm đa chiều giông như của một tìm kiếm 2D. B ằng cách quan sát ́ thống kê phân loại trong các bộ định tuyến lõi của ISP 1 Tier, h ọ th ấy r ằng môi ̃ goi phù hợp tại ít nhất một điểm đến cặp tiền tố nguồn khác nhau (SIP, DIP) đã ́ trình bày trong quy tăc thiêt lâp. Nói cách khác, nếu chúng ta d ự thao quy t ắc ́ ̣́ ̉ thiết lập để chỉ các trường nguồn và đích, gói tin không phù h ợp v ới nhi ều h ơn một số lượng nhỏ các quy tắc trong tập mới của quy tăc. Lưu ý rằng đây là ́ điêm nhân không đung cho những trường đơn lẻ vì những ký tự đại diện: một ̉ ́ ́ gói duy nhất có thể phù hợp với hàng trăm quy tắc khi xem xét bất kỳ môt ̣ trường biêt lâp nao. Dựa trên những ký tự này, họ thể hiện ý tưởng về một ̣̣ ̀ phương pháp phân loại 2D đơn giản, như thể hiện trong hình 1.6. Ý tưởng đó là ban đâu sử dụng môt vai hiêu ứng 2D kêt hợp để tìm tất cả các cặp khác biệt ̀ ̣ ̀ ̣ ́ nguồn tiền tố đích (S1, D1),. . . , (St, Dt) phù hợp với một header. Đối với mỗi cặp khác nhau (Si, Di) có một mảng tuyến tính hoặc danh sách t ất c ả các quy tắc có chứa (Si, Di) trong mã nguồn và các trường đích. Hinh 1.6- Chinh sach mở rông tim kiêm 2D ̀ ́ ́ ̣ ̀ ́ Như trong hình 1.6 (S1, D1) có chứa các quy tắc, R5, R6, R2, và R4. Lưu ý rằng quy luật chỉ có thể được liên kết với một căp tiên tô ́ nguôn-đich. ̣ ̀ ̀ ́ 13
Mặt khác, người ta có thể muốn sao chép các quy tắc để giảm số l ượng các điểm đến cặp tiền tố nguồn xem xét trong tìm kiếm để giảm th ời gian tìm kiếm. Khi tìm kiếm một quy tắc cho một khóa nào đó, nhi ều c ặp ti ền t ố ngu ồn- đích có thể tương thich với phím. Ví dụ: (*, 000) và (1 *, 0 *) phù hợp với một ́ phím tiền tố (111, 000). Kết quả là, các quy tắc trong mỗi căp t ương thich(S, D) ̣ ́ sẽ được tiếp tục tìm kiếm lân nữa với phần còn lại của khoá. Ví dụ, nếu (S1, ̀ D1) tương thich, tất cả các quy tắc, R5, R6, R2, và R4, được tìm ki ếm lân nữa, ́ ̀ ví dụ, các số cổng của khoá. 1.2.5- Trường phân loai mức trie(FLTC) ̣ Một trường phân loai mức trie (FLTC) sử dụng một cấu trúc trường ̣ mức trie (FLT) được tổ chức trong một trường câu truc phân cấp. Các cấu trúc ́ ́ dữ liệu phân loại đã được tối ưu cho TCAM tìm kiếm đa đường được phat triên ́ ̉ cho cac pham vi tiên tố và trường tương ứng. Quá trình truy vấn (tìm kiếm) cũng ́ ̣ ̀ được thực hiện bởi trường. Với việc thực thi chinh xac, mỗi truy vấn chỉ cần ́ ́ yêu câu nhớ môt vai bộ nhớ truy cập trung bình, và do đó phân loại tốc độ cao ̀ ̣ ̀ rất có thể đạt được. Các yêu cầu lưu trữ của FLTC có thể là ly ́ do chia s ẻ thuôc ̣ tinh của các node FLT. Mặc dù nút chia sẻ làm cho các quá trình cập nhật (chèn ́ và xóa bỏ) đơn gian hơn, sự phức tạp của các hoạt động cập nh ật vẫn còn th ấp ̉ vì mỗi hoạt động chỉ ảnh hưởng một phần nhỏ của cấu trúc dữ liệu. Các FLTC dễ dàng có thể hỗ trợ phân loại lớn, ví dụ, với 100.000 đến 1.000.000 quy tắc, mà không làm giảm hiệu suất truy vấn. Cac chỉ tiêu phân loại câu truc FLT với nhiều lĩnh vực, mỗi một trong ́ ́ ́ số đó được quy định ở định dạng tiền tố hoặc định dạng băng. Hình 1.7 cho thấy FLT xây dựng từ các phân loại trong Bảng 1.2. FLT được xác định để có các thuộc tính sau đây: 14
1. Nó được tổ chức trong một pham vi cấu trúc phân cấp của trường. ̣ Độ sâu của FLT một bằng với số trường, d. Trong hình 1.7, có bốn cấp độ của các nút, tổ chức từ F1 đến F4 0,2. 2. Mỗi node trong FLT có chứa một bộ quy tắc, nó cũng là m ột t ập h ợp con của bộ quy tắc node. Các node gốc của FLT được xác định để chứa tất cả các quy tắc trong phân loại này. 3. Node a trong các mưc 3 thứ i tạo ra nút con của nó trong mức(i + 1) ́ dựa trên các giá trị Fi của tất cả các quy tắc có trong nút a. Tùy thuộc vào đặc điểm kỹ thuật của Fi, có hai thủ tục khác nhau cho thế hệ node con: Nếu Fi được quy định trong định dạng tiền tố, số lượng các nút con của a bằng với số tiền tố khác nhau trong trường Fi của các quy tắc của a. Mỗi nút con được kết hợp với một tiền tố khác nhau. Giả sử node con b được kết hợp với tiền tố p, giá trị Fi cua quy tắc r có trong bộ quy tắc của b hoặc tương ̉ tự hoặc là tiền tố của p. Ví dụ, các nút gốc trong hình 1.7 có tất cả bảy nguyên tắc và có bốn tiền tố khác nhau, *, 0*, 00*, và *10, trong trường F1, do đó, bốn node con được tạo ra. Node x liên kết với tiền tố *0 chứa bốn quy tắc, R 4-R7. Giá trị F1 của R4-R6 là 0*, đó là tiền tố liên quan, các giá trị F1 của R7 là *, là một tiền tố cua 0*. ̉ R1 – R7 R4 – R7 R7 R1, R2,R4 – R7 R3, R7 15
a) b) c) d) Hình 1.7 Ví dụ về các FLT bốn chiều. (A) C ấp 1, (b) C ấp 2; (c) C ấp 3, (d) Cấp 4 16
Nếu Fi được quy định trong định dạng băng, đôi tượng ban đâu đ ưa tất ́ ̀ cả các băng (được lấy từ các trường Fi của bộ quy tắc a) vào một số dòng và có được một tập các khoảng cach. Đối với mỗi khoảng cach I, một node con b ́ ́ được tạo ra. Một giá trị r được chứa trong quy tắc thiết lập b nếu và chỉ nếu, phạm vi quy định bởi trường Fi của r bao gồm I. Ví dụ, node y tạo ra ba nút con, node y’ với khoảng [10, 10], mà là một điểm duy nhất, node y’’’ với khoảng [6, 6], và node y’’ với khoảng thời gian [4, 5] và [7, 8] (trong th ực t ế, có c ả hai con trỏ trỏ đến y), như được chỉ ra trong hình 3.7. 4. Quy tắc thiêt lâp của một node a trong các mức độ thứ i là duy nhất ̣́ trong cac thiêt đăt của tất cả các node ở mức thứ i. Nếu hai nút trong mức(i - 1), ́ ̣́ b, c, có một node con a chung, sau đó chỉ có một node, là node a, được tạo ra và chia sẻ nó. Hình 1.7 cho thấy node chia sẻ diên ra khi node được tr ỏ đ ến b ởi ̃ nhiêu con trỏ. ̀ Cac trường trong mâu tiên tô. Vì mỗi trường thường được quy định ́ ̃ ̀ ́ tại một trong hai hoặc nhiều hình thức tiền tố và đặc đi ểm k ỹ thu ật đ ều có c ấu trúc riêng của mình ủng hộ dữ liệu và thuật toán tìm kiếm, chúng tôi nhóm các lĩnh vực với các thông số kỹ thuật tương tự nhau. Trong hầu h ết cac tr ường ́ hợp, môt phân loại của các trường có hai nhóm; nhóm đầu tiên ở dạng tiền tố và ̣ nhóm thứ hai ở dang băng. Trong Bảng 1.2, F1 và F2 nằm trong nhóm đầu tiên ̣ và F3 và F4 được trong nhom thứ hai. FLT đ ược t ổ ch ức đ ể các tr ường c ủa các ́ nhóm đầu tiên xuất hiện ở các cấp trên và các trường thứ hai xuất hiện ở các cấp thấp hơn. Đối với nhóm đầu tiên mà chỉ có trường tiền tố tồn tại, TCAM có thể được sử dụng để lưu trữ các tiền tố và tìm kiếm trong số đó. T ừ TCAM có thể phục vụ cùng một lúc nhiều trường, các truy vấn của nhóm đầu tiên c ủa trường có thể được thực hiện trong một truy cập TCAM duy nh ất. Hình 1.8 cho thấy FLT nén bắt nguồn từ các phân loại trong Bảng 1.2 và trie cấu trúc trong 17
hình 1.7. Bây giờ chỉ có một cấp độ hiện tại cho các trường F1 và F2. Các node gốc có bảy node con đầu tiên nằm trong cấp độ thứ ba trong hình 1.7. Mỗi cấp nút thứ hai có một cặp tiền tố F1/F2 liên kết với nó. Mỗi cặp tiền tố đó là n ội dung của một mục trong TCAM này. Hình 1.8 Ví dụ về các FLT nen bốn chiều. ́ BẢNG 1.3- Nội dung TCAM cho các FLT nén Căp tiên tố ̣ ̀ Tổng chiều dài từ căp ̣ Entry Tên node Tiền tố 1 */00* a 2 2 0*/1* b 2 3 0*/10* c 3 4 0*/01* d 3 5 10*/1* g 3 6 00*/11* e 4 7 00*/110** f 5 Các cặp tiền tố bắt nguồn từ cấu trúc trie trong hình 1.7. Đối với mỗi node a trong cấp độ thứ ba trong hình 1.7, tương ứng với các nút trong cấp độ thứ hai trong hình 1.8, chúng tôi tìm thấy một đường dân t ừ node g ốc đ ến a với ̃ 18
tổng chiều dài tiền tố nhỏ nhất. Các tiền tố dọc theo đường dân này tạo thành ̃ cặp tiền tố liên kết với a trong hình 1.8. Tất cả các cặp tiền tố được sắp xếp theo thứ tự giảm dần của độ dài tiền tố (tổng của độ dài của hai ti ền t ố) trong TCAM này. Đối với cặp tiền tố có cùng độ dài, trật tự tương đ ối c ủa h ọ có th ể được tùy tiện. Nội dung của TCAM cho FLT nén trong hình 3.8 được trình bày trong Bảng 1.3. Bằng cách sắp xếp các cặp tiền tố thứ tự tăng dần trong TCAM (nghĩa là dài nhất phù hợp với cặp tiền tố sẽ được tìm thấy), chúng tôi có thể đảm bảo kết quả tìm kiếm từ TCAM để được chính xác, ví dụ, các nút thích h ợp ở cấp độ thứ hai được xác định tiếp tục quá trình truy vấn toàn bộ. Một bằng ch ứng ngắn sau: Khi tìm kiếm các TCAM với một khoá A/ B, nếu hai mục với ti ền tố cặp A1/B1 và A2/B2 là lần xuất hiện, sẽ có hai kịch bản. Không m ất tính t ổng quát, chúng tôi giả đinh A1 ≺ A2, có nghĩa là A1 là một tiền tố của A2. ̣ Trong kịch bản đầu tiên, nơi B1 ≺ B2, độ dài của A2/B2 là lớn hơn so với các A1/B1,. Do đó, danh muc B2/A2 là đầu ra giông nh ư k ết qu ả. Đó là m ột ̣ ́ kết quả chính xác vì tất cả các quy tắc trong node a (tương ứng với A1/B1) cũng có trong node b (tương ứng với A2/B2), được đảm bảo bằng thuôc tinh ̣́ của FLT, và node b được chọn. Trong kịch bản thứ hai, nơi B1≺ B2, một mục với cặp tiền tố A2/B1 phải tồn tại, đó là bảo đảm quá trình phat sinh của FLT này. Vì độ dài c ủa ́ A2/B1 lớn hơn của cả hai A2/B2 và A1/B1, mục với A2/B1 là đ ầu ra nh ư k ết quả. Đó là một kết quả đúng bởi vì tất cả các quy tắc trong nút cả và node b được chứa trong node c (tương ứng với A2/B1). Kết luận trên có thể dễ dàng mở rộng cho các trường tiền tố nhiều hơn hai. Cho một gói tin header được phân loại, các trường thu ộc nhóm đ ầu tiên 19
được chiết xuất và trình bày cho TCAM để tìm kiếm. Đâu ra t ừ TCAM biêu thi ̣ ̀ ̉ một node ở mức thứ hai để được truy cập tiếp theo. Từ TCAM đã cung cấp chỗ ở cho tất cả các trường tiền tố, phần còn lại của quá trình truy vấn d ựa trên nhiều lĩnh vực. Trường phân loai băng. Đối với các nút hiện có trong mức thứ hai ̣ hoặc thấp hơn, chúng tôi đề xuất sử dụng một cây tìm ki ếm đa đ ường (cây tim ̀ kiêm k-đường) để tổ chức cấu trúc dữ liệu tại mỗi nút. ́ E1 E2 E3 P E4 E5 E6 E7 E8 I1 I2 I3 I4 I5 I6 I7 a) cac điêm tới cac node ́ ̉ ́ trong mức kế tiêp ́ b) Hình 1.9 Ví dụ về cơ cấu tổ chức node trong cây tìm kiếm ba chiều. (A) Có nguồn gốc trong khoảng thời gian bằng cách bảo vệ phạm vi, (b) cơ c ấu Node cho một cây tìm kiếm ba đường. Ví dụ, có một node a trong các mức độ thứ i (i> 1) của FLT được nen. ́ Sau kế hoach các trường Fi của bộ quy tắc a trên một số dòng, bảy khoảng, I 1 ̣ để I7, thu được với tám điểm cuối cùng, E1 để E8, như trong hình 1.9a. Nếu chúng ta sử dụng một cây tìm kiếm ba đường để tổ chức những khoảng thời gian, kết quả được thể hiện trong hình 3.9b. Nó là một cây hai l ớp v ới b ốn kh ối 20