Nghiên cứu bảng địa chỉ mạng (MAC table) cho thiết kế thiết bị chuyển mạch lớp 2 trên nền tảng FPGA

Công nghệ thông tin<br /> <br /> NGHIÊN CỨU BẢNG ĐỊA CHỈ MẠNG (MAC TABLE) CHO THIẾT<br /> KẾ THIẾT BỊ CHUYỂN MẠCH LỚP 2 TRÊN NỀN TẢNG FPGA<br /> Thái Trung Kiên1*, Hoàng Đình Thắng1, Đào Xuân Ước1, Nguyễn Văn Thành2<br /> Tóm tắt: Trong bài báo này tập trung nghiên cứu giới thiệu bảng địa chỉ mạng<br /> (MAC table), phương pháp xây dựng bảng địa chỉ mạng dựa trên bảng băm, phương<br /> pháp giảm xung đột và thực thi trên phần cứng FPGA. Bài báo đề xuất phương pháp<br /> giảm xung đột bảng MAC bằng cách sử dụng bảng phụ với kích thước bằng 1/16<br /> bảng chính, và bảng chính được chia thành 16 đoạn. Kết quả thử nghiệm mô phỏng<br /> cho thấy xung đột xảy ra dưới 1%. Trên cơ sở kết quả mô phỏng, phương pháp cũng<br /> được thực hiện trên phần cứng FPGA. Kết quả cho thấy rằng, với mỗi xung CLK độ<br /> trễ là 5ns trên chip Artix7 200 MHz cho chế độ tìm kiếm trong bảng địa chỉ mạng.<br /> Tốc độ này tương đương với tốc độ xử lý thiết bị mạng 100 Gbps với gói tin Ethenet<br /> có kích thước 64 byte.<br /> Từ khóa: Bảng MAC; Bảng băm; Hàm băm; Chuyển lớp 2.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Khi máy tính được nối mạng thông qua các thiết bị mạng như thiết bị chuyển<br /> mạch, hay định tuyến (switch, router), thì thông tin máy tính nối mạng được thu<br /> thập bởi các thiết bị đó. Các thông tin về máy tính được thu thập như địa chỉ mạng<br /> (MAC Address), địa chỉ IP, … Địa chỉ IP có thể được thay đổi thông qua các công<br /> cụ cấu hình địa chỉ IP. Còn địa chỉ mạng (MAC) không thể thay đổi đối với người<br /> sử dụng. Trừ các trường hợp các hacker chuyên nghiệp sử dụng vào các mục đích<br /> không trong sáng.<br /> Địa chỉ mạng được hình thành ở lớp thứ 2 trong mô hình 7 lớp OSI, được gán<br /> duy nhất cho thiết bị khi truy cập vào mạng. Thông thường trong mạng LAN, các<br /> máy tính được kết nối và chia sẻ tài nguyên với nhau thông qua thiết bị chuyển<br /> mạch (hình 1). Để máy A có thể trao đổi với máy B thì thiết bị chuyển mạch sẽ thu<br /> thập địa chỉ mạng của 2 máy. Địa chỉ mạng của máy kết nối vào thiết bị chuyển<br /> mạch sẽ được lưu trữ trong ở bảng địa chỉ mạng (hình 2).<br /> <br /> <br /> <br /> <br /> Hình 1. Sơ đồ kết nối mạng sử dụng thiết bị chuyển mạch [2].<br /> Quá trình bảng địa chỉ mạng được cập nhật thông qua quá trình gửi thông tin<br /> của máy A và máy B. Cụ thể khi gói tin từ máy A được gửi đi, địa chỉ mạng của<br /> máy A sẽ được lưu vào bảng MAC. Thông tin lưu giữ bao gồm địa chỉ MAC, và<br /> cổng kết nối mà máy A kết nối tới thiết bị chuyển mạch. Tương tự như vậy, thông<br /> tin địa chỉ của máy B sẽ được lưu trữ vào bảng MAC của thiết bị chuyển mạch.<br /> Khi thiết bị chuyển mạch mới bật lên, bảng MAC là trống rỗng, cho đến khi các<br /> thiết bị nối vào thiết bị chuyển mạch gửi thông tin tới. Khi máy A muốn gửi thông<br /> tin đến máy B thì thiết bị chuyển mạch sẽ phân tích gói tin, tìm ra địa chỉ của máy<br /> B và cổng kết nối đến thiết bị chuyển mạch để chuyển gói tín đến B. Trường hợp B<br /> không tồn tại thì switch sẽ chuyển gói tin đến tất cả các cổng trên thiết bị chuyển<br /> mạch trừ cổng gắn với máy A.<br /> <br /> <br /> 16 T. T. Kiên, …, N. V. Thành, “Nghiên cứu bảng địa chỉ mạng … trên nền tảng FPGA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Quá trình tìm kiếm địa chỉ B trong bảng địa chỉ là bài toán rất phức tạp, và sử<br /> dụng nhiều phương pháp, kỹ thuật khác nhau. Xây dựng bảng địa chỉ, và các<br /> phương pháp sử dụng để tìm kiếm là những xử lý căn bản đầu tiên của thiết bị<br /> chuyển mạch. Tốc độ xử lý tìm kiếm địa chỉ mạng trong bảng MAC là nhân tố<br /> quan trọng quyết định xử lý chuyển tiếp gói tin trong thiết bị chuyển mạch. Thông<br /> dụng với các thiết bị chuyển mạch lớp 2 sử dụng cho các mô hình tổ chức vừa và<br /> nhỏ, giá thành rẻ thì kỹ thuật bảng băm được sử dụng. Bởi vậy trong bài báo này,<br /> phần thứ 2 tập trung nghiên cứu và giới thiệu căn bản về bảng băm, hàm băm, kỹ<br /> thuật giải quyết xung đột khi xảy ra, đề xuất phương pháp và mô phỏng để tìm<br /> kiếm giải pháp tối ưu. Trong phần thứ 3, bài báo tập trung mô tả quá trình thực<br /> nghiệm trên FPGA, và đánh giá khả năng thực thi trên phần cứng. Và cuối cùng là<br /> các đánh giá nhận xét, kết luận.<br /> 2. BẢNG BĂM SỬ DỤNG TRONG BẢNG ĐỊA CHỈ MẠNG<br /> 2.1. Bảng băm, hàm băm<br /> Bảng băm, theo định nghĩa ở nhiều tài liệu [3, 4], là một cấu trúc dữ liệu lưu trữ<br /> một tập hợp sử dụng hàm băm (hash function) để ánh xạ từ một giá trị xác định<br /> (gọi là khóa) đến giá trị tương ứng trong đó. Các cấu trúc dữ liệu thường xuyên bắt<br /> gặp cho các bài toán tìm kiếm như là cây cây bằng, thì phép tìm kiếm được thực<br /> hiện trong thời gian là O(logn). Có nghĩa là thời gian tìm kiếm sẽ phụ thuộc vào độ<br /> lớn của tập dữ liệu. Đối với các bài toán tìm kiếm yêu cầu thời gian thực hiện là<br /> tức thời (chỉ tính vài nano giây) như bài toàn tìm kiếm địa chỉ mạng đích trong các<br /> thiết bị chuyển mạch, thì mong muốn thời gian tìm kiếm là O(1).<br /> Gọi A[0,1,…,n−1] là tập n phần tử được lưu trữ trong bảng băm. Các phần tử<br /> của tập hợp mà được lưu trữ thường từ một tập lớn hơn U được gọi là tập gốc. Tập<br /> gốc là tập phần tử hữu hạn nhưng rất lớn so với n và m (m là số phần tử của bảng<br /> băm). Ví dụ tập gốc đối với tập địa chỉ mạng là tất cả các thiết bị hỗ trợ kết nối<br /> mạng (hàng tỷ thiết bị). Nếu giả sử tập dữ liệu trong bảng băm là địa chỉ mạng có<br /> thể được lưu trữ trong thiết bị chuyển mạch, ví dụ như thiết bị Cisco 2960, thì<br /> lượng địa chỉ có thể lưu trữ là 8000.<br /> Bảng băm là một mảng T[0,1,…,m−1] có kích thước m. Để lưu trữ dữ liệu vào<br /> bảng băm, một hàm băm (hash function) sẽ được sử dụng, biểu diễn dưới dạng:<br /> h:U→{0,1,…,m−1} (1)<br /> là một ánh xạ gán cho mỗi phần tử của tập U một vị trí trong bảng T. Cụ thể, phần<br /> tử x sẽ được lưu tại ô T[h(x)] của bảng, nghĩa là x được băm vào vị<br /> trí h(x), và h(x) được gọi là mã băm (hash code) của x (hình 3).<br /> Hai thao tác chính của bảng băm đó là: đưa một phần tử mới vào bảng băm<br /> (learning) và tìm xem một phần tử có nằm ở trong bảng băm hay không (lookup).<br /> LEARNING(key x, h): LOOKUP(key x, h):<br /> T[h(x)]←x if T[h(x)]=x return YES else return<br /> NO<br /> Do U lớn hơn m, theo nguyên lí “nhốt chim”, một hoặc nhiều phần tử của<br /> tập U có thể sẽ được băm vào cùng một vị trí của bảng. Khi nhiều hơn một phần tử<br /> cùng bặm vào cùng một vị trí của bảng băm thì hiện tượng này được gọi là xung<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 17<br />  Công nghệ thông tin<br /> <br /> đột. Do xung đột làm quá trình tìm kiếm trở nên phức tạp hơn, nên sẽ cần có<br /> những phương pháp để đối phó được gọi là phương pháp giải quyết xung đột.<br /> 001D.70AB.5D60 Fa0/2<br /> 1<br /> Tập đia 2 001E.F724.A160 Fa0/3<br /> chỉ mạng 3<br /> Tập địa chỉ 4 ...<br /> mạng của tổ h(x) 5<br /> chức 6<br /> .<br /> .<br /> <br /> Hình 2. Minh họa bảng băm.<br /> Trước khi thảo luận các cách chiến lược này, ta sẽ thảo luận về cách chọn hàm<br /> băm trước vì xung đột nhiều hay ít đều phụ thuộc vào hăm băm mà ta chọn.<br /> Như đã mô tả ở ví dụ tập các thiết bị mạng trên thế giới, và số lượng thiết bị của<br /> một tổ chức thì việc xảy ra xung đột địa chỉ mạng là không thể tránh khỏi. Để giảm<br /> thiểu xung đột, phương pháp đầu tiên được sử dụng là lựa chọn hàm băm phù hợp<br /> với loại dữ liệu.<br /> Theo [5] khi nghiên cứu lựa chọn các hàm băm trong việc tìm kiếm địa chỉ<br /> mạng đã chỉ ra rằng, nếu dùng mã kiểm tra CRC cho kết quả rât tốt. Ngoài ra dùng<br /> phương pháp mã kiểm tra CRC thì việc thực hiện trên phần cứng cũng rất dễ dàng.<br /> Các nghiên cứu của hãng Broadcom [6, 7] đã nghiên cứu cũng đã sử dụng với<br /> CRC16 (CCITT) cho việc xây dựng cấu trúc lưu dữ liệu như địa chỉ MAC, địa chỉ<br /> internet.<br /> 2.2. Giải quyết xung đột<br /> Như đã nêu ở trên, việc xung đột địa chỉ là hoàn toàn có thể xảy ra bởi tính chất<br /> của hàm băm. Bởi vậy để giải quyết xung đột ngoài việc lựa chọn hàm băm thì có<br /> một số phương pháp chính đã được giới thiệu [4]. Các phương pháp bao gồm:<br /> phương pháp xích ngăn (separate chaining), địa chỉ mở (open addressing), và băm<br /> hoàn hảo (perfect hashing).<br /> Phương pháp xích ngăn là phương pháp trực quan và đơn giản. Đó là dùng một<br /> danh sách liên kết, gọi là xích ngăn để liên kết các phần tử có cùng mã băm h(x). Ở<br /> phương pháp này có định sử dụng thêm hệ số tải (α), và trường hợp xấu nhất sẽ<br /> phải trả giá cho một tìm kiếm là O(logn).<br /> Phương pháp thứ 2 được sử dụng để giảm xung đột là phương pháp địa chỉ mở<br /> (open addressing). Xuất phát từ việc sử dụng phương pháp xích ngăn sẽ tạo ra<br /> nhiều ô rỗng, trong khi các ô khác chưa nhiều phần tử. Bênh cạnh đó, trong kỹ<br /> thuật lập trình thì cần duy trì một danh sách các con trỏ để liên kết các phần tử với<br /> nhau, vì vậy phương pháp xích ngăn sẽ cần nhiều bộ nhớ. Từ đó phương pháp địa<br /> chỉ mở là mỗi ô chỉ lưu trữ duy nhất một phần tử.<br /> Phương pháp băm hoàn hảo sẽ sử dụng hai bàm băm tốt (h(x), g(x)), và bảng<br /> băm hai chiều: T[1,2,…,m][…]. Mỗi hàng của bảng băm T[i] sẽ được coi như một<br /> bảng băm phụ, có kích thước phụ thuộc vào đầu vào. Khi băm vào bảng, thực hiện<br /> băm theo 2 pha: Pha đầu tiên, sử dụng hàm h để băm x vào hàng h(x) của bảng T.<br /> Gọi C[i] là số lượng phần tử được băm cùng vào hàng thứ i sau pha đầu tiên.<br /> Trong pha thứ 2, với mỗi hàng i, cấp phát một bộ nhớ C[i]2 cho hàng T[i]. Sau đó,<br /> <br /> <br /> 18 T. T. Kiên, …, N. V. Thành, “Nghiên cứu bảng địa chỉ mạng … trên nền tảng FPGA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> coi hàng này như một bảng băm và dùng hàm g để băm các phần tử x có cùng mã<br /> băm i vào ô g(x) của hàng này. Đụng độ lần 2 này sẽ được giải quyết sử dụng xích<br /> ngăn cách.<br /> Ở phương pháp băm hoàn hảo, bảng băm phụ sẽ có kích thước bằng bình<br /> phương số phần tử được lưu trong hàng nên xung đột khi băm lần 2 sẽ là O(1). Do<br /> đó tìm kiếm sẽ thực hiện trong thời gian là O(1).<br /> Nghiên cứu [7] đã chia bảng băm dữ liệu ra thành hai bảng băm, gọi là bảng thứ<br /> nhất và bảng thứ 2. Bảng thứ nhất sử dụng mã kiểm tra CRC32, và bảng thứ 2<br /> dùng mã kiểm tra CRC16. Có thể xem phương pháp [7] là phương pháp băm hoàn<br /> hảo. CRC16-CCITT được định nghĩa [7]:<br /> x16+x12+x5+1 (2)<br /> 2.3. Đề xuất phương pháp giải quyết xung đột<br /> Dựa trên các nghiên cứu [4, 5, 6, 7], các giải pháp chống xung đột được xây<br /> dựng thử nghiệm trên Labview. Để đề xuất phương pháp chống xung đột địa chỉ<br /> mạng, thì bảng băm sẽ được lần lượt chia đoạn, với các kích thước khác nhau. Đây<br /> là ý tưởng được xuất phát từ phương pháp băm hoàn hảo. Đặc biệt phương pháp đề<br /> xuất chỉ sử dụng một loại hàm băm tốt, đó là hàm CRC16-CCITT, khác biệt với đề<br /> xuất ở [7].<br /> Tham số mô phỏng được dựa trên các tham số yêu cẩu đề tài mã số<br /> 18/2018/ĐTCT-KC.01/16-20 [8], với số phần tử địa chỉ mạng là 8000 (tương<br /> đương 213). Sơ thử nghiệm được thể hiện như hình 3.<br /> <br /> <br /> <br /> <br /> Hình 3. Sơ đồ thử nghiệm trên Labview.<br /> Sơ đồ cấu trúc trên Labview được thể hiện ở hình 3, sơ đồ thuật toán được<br /> thể hiện ở hình 4.<br /> Để thực hiện mô phỏng thuật toán, một số giải thiết sau được đưa ra:<br /> - Bảng băm bao gồm: bảng chính N đoạn, bảng phụ K đoạn.<br /> - Bảng băm chứa địa chỉ MAC tại địa chỉ tương ứng với giá trị băm trên<br /> RAM.<br /> Khi bắt đầu thiết bị chuyển mạch thêm địa chỉ MAC hoặc tìm kiếm địa chỉ<br /> MAC, hàm băm HASH sẽ thực hiện tính toán giá trị địa chỉ MAC để tính toán địa<br /> chỉ RAM tương ứng. Giá trị MAC được lưu trong địa chỉ RAM tương ứng được so<br /> sánh với địa chỉ MAC cần so sánh, va chạm xảy ra nếu hai giá trị khác nhau (trong<br /> trường hợp lookup) và đã tồn tại một giá trị tại địa chỉ trong trường hợp learning.<br /> Việc so sánh được thực hiện trên tất cả các đoạn trong bảng chính, nếu xảy ra va<br /> chạm trong bảng chính quá trình so sánh được thực hiện trong bảng phụ. Quá trình<br /> so sánh kết thúc khi tìm kiếm được giá trị bằng nhau (trong trường hợp lookup)<br /> hoặc tìm được vị trí để ghi (trong trường hợp learning). Sơ đồ thuật toán hình 4<br /> được sử dụng để thực thi trên phần cứng ở mục 3.<br /> Với dữ liệu kích thước bảng là 213, số địa chỉ mạng lần lượt được thử là 213 hoặc<br /> nhỏ hơn, số lần thử nghiệm 100 lần. Kích thước bản phụ được sử dụng lần lượt<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 19<br />  Công nghệ thông tin<br /> <br /> bằng 1/8 và 1/16 bảng chính. Các kịch bản thử nghiệm được thể hiện qua các<br /> bước:<br /> - Có phân đoạn nhưng không sử dụng bảng phụ;<br /> - Sử dụng bảng phụ có kích thước bằng 1/8 bảng chính, có phân đoạn;<br /> - Sử dụng bảng phu có kích thước bằng 1/16 bản chính, có phân đoạn.<br /> - Sử dụng các dữ liệu đầu vào khác nhau (8000 địa chỉ, 5000 địa chỉ, 4000<br /> địa chỉ).<br /> Kết quả thực nghiệm cho thấy phần trăm xung đột nhỏ hơn 1 khi sử dụng thêm<br /> bảng phụ có kích thước bằng 1/16 bảng chính, bảng chính và bảng băm được phân<br /> thành 2, 4, 8, 16, 32 đoạn. Địa chỉ đầu vào là 212.<br /> Bắt đầu<br /> <br /> <br /> <br /> <br /> Tính giá trị hàm HASH<br /> i = 0, j = 0 1 2 3<br /> <br /> <br /> <br /> <br /> Đọc và so sánh với giá trị Đọc và so sánh với giá trị<br /> MAC đã được lưu tương MAC đã được lưu tương Thông báo không có va<br /> Thông báo có va chạm.<br /> ứng trong Hashtable ở ứng trong Hashtable ở chạm.<br /> đoạn i của bảng chính. đoạn j của bảng phụ.<br /> <br /> <br /> <br /> <br /> NO NO<br /> Có va chạm? 2 Có va chạm? 2 Kết thúc<br /> <br /> <br /> <br /> YES YES<br /> <br /> <br /> <br /> i = i +1 j = j +1<br /> <br /> <br /> <br /> <br /> NO NO<br /> i=N-1 j=K-1<br /> <br /> <br /> <br /> YES YES<br /> <br /> <br /> 1 3<br /> <br /> <br /> <br /> Hình 4. Sơ đồ thuật toán đề xuất để giảm tránh xung đột.<br /> 3. THỰC NGHIỆM THAO TÁC BẢNG ĐỊA CHỈ MẠNG TRÊN FPGA<br /> Để đánh giá phương pháp đề xuất giải quyết xung đột, thuật toán hình 4 được<br /> thử nghiệm với MAC table trên chip Artix – 7 của hãng Xilinx, với tần số xung<br /> CLK là 200MHz. Bảng địa chỉ dùng để lưu trữ các thông tin liên quan cho thiết bị<br /> chuyển mạch lớp 2 với 72 bit thông tin như đưa ra trên bảng 2. Cách tổ chức bảng<br /> địa chỉ MAC để tiết kiệm tài nguyên là các block RAM nội của chip Xilinx FPGA<br /> (bao gồm các khối Block RAM có cấu tạo 72x512, 36x1024 hoặc 18x2048). Sơ đồ<br /> tổ chức bảng địa chỉ MAC được đưa ra trên bảng 1, sơ đồ máy trạng thái hoạt động<br /> được đưa ra trên hình 6.<br /> Mỗi địa chỉ MAC sau khi Learning sẽ được lưu trữ trong một khoảng thời gian<br /> nhất định trong các khối BRAMs (kiểu Dynamic). Khi có một địa chỉ MAC mới<br /> <br /> <br /> 20 T. T. Kiên, …, N. V. Thành, “Nghiên cứu bảng địa chỉ mạng … trên nền tảng FPGA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> được dựa vào để Learning, nếu nó đã có trong BRAMs từ trước thì thời gian lưu<br /> trữ sẽ được làm mới.<br /> Khi Lookup, nếu địa chỉ MAC đưa vào giống với một địa chỉ MAC đã được lưu<br /> trong BRAMs thì toàn bộ thông tin liên quan về địa chỉ MAC đó sẽ được lấy ra,<br /> cùng với đó là tín hiệu thông báo MATCH chuyển lên mức ‘1’.<br /> Hàm băm chuyển địa chỉ MAC thành một giá trị băm tương ứng làm địa chỉ lưu<br /> trữ trong BRAMs, sử dụng phép toán mod giữa giá trị địa chỉ MAC với CCITT-<br /> CRC-16.<br /> BRAMs<br /> WRITING<br /> POSITION<br /> <br /> <br /> FSM BRAMs<br /> WE<br /> Priority<br /> WE Encoder<br /> Tìm kiếm<br /> ADDR<br /> Địa chỉ ADDRESS DO<br /> Hàm băm DI DO<br /> MAC<br /> <br /> <br /> <br /> AGING<br /> S/D MUX<br /> BUS<br /> <br /> <br /> <br /> <br /> PORT DO DI<br /> <br /> VLAN<br /> Initiate<br /> MATCH<br /> aging DATAIN CHECKING<br /> propertiy<br /> <br /> MATCH<br /> <br /> <br /> <br /> <br /> Hình 5. Sơ đồ tổ chức MAC table. Hình 6. Sơ đồ máy trạng thái<br /> của MAC table.<br /> <br /> Các khối trong hình 5, bao gồm:<br /> - BRAMs - Bộ nhớ dùng để lưu trữ địa chỉ MAC và các thông số liên quan. Là<br /> các khối block RAM nội của Xilinx tổ chức theo cấu trúc 72x512.<br /> - Aging - Bộ cộng dùng để cập nhật thời gian lưu trữ của địa chỉ MAC (đối với<br /> kiểu Dynamic).<br /> - Match checking: So sánh địa chỉ MAC đầu vào với địa chỉ MAC được lưu trong<br /> RAM, nếu giống nhau thì sẽ đưa ra tín hiệu MATCH.<br /> - Các khối còn lại: Khối Initiate Aging Property dùng để khởi tạo giá trị thời gian<br /> đã lưu trữ đối với mỗi địa chỉ MAC.<br /> Việc sử dụng 16 khối RAM song song có tác dụng làm giảm hiện tượng trùng<br /> khoá (xung đột) giữa các địa chỉ MAC khác nhau xuống tỉ lệ rất thấp. Vì vậy cần<br /> sử dụng 16 khối Aging tương ứng và các khối hỗ trợ như BRAMs Writing Position<br /> để lựa chọn chính xác khối RAM dùng để lưu trữ, Priority Encoder để chọn lấy<br /> đầu ra phù hợp trong 16 đầu ra của các khối RAM song song, đồng thời khối<br /> Match Checking cũng sẽ đảm nhận thêm nhiệm vụ chỉ ra vị trí match để đưa vào<br /> bộ Priority Encoder. Ngoài ra, khối FSM cũng sử dụng thêm một bộ Timer để hỗ<br /> trợ việc tính thời gian timeout cho các địa chỉ MAC kiểu Dynamic.<br /> Bảng 1. Các bit trong một địa chỉ của RAM trong MACtable.<br /> MAC Reserved<br /> Static/Dynamic Port VLAN Aging Prop<br /> address bit<br /> 48 bit 1 bit 5 bit 12 bit 5 bit 1 bit<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 21<br />  Công nghệ thông tin<br /> <br /> Quá trình thêm địa chỉ mạng được đưa trên hình 7, learning mất 4 chu kì CLK,<br /> tính từ lúc WE chuyển từ mức 0 lên mức 1 (hình 7, 8).<br /> CLK CLK<br /> WE LOOKUP<br /> DATAIN MAC<br /> <br /> BUSY MATCH<br /> Hình 7. Quá trình Learning. Hình 8. Quá trình Lookup.<br /> BUSY : tín hiệu thông báo hệ thống bận khi Learning<br /> MATCH : tín hiệu thông báo MATCH khi Lookup<br /> Quá trình Loockup được đưa ra trên hình 8, cho ra kết quả chậm 1 chu kì CLK<br /> so với tín hiệu LOOKUP đầu vào, và có thể LOOKUP liên tục.<br /> <br /> Bảng 2. Tài nguyên được tính trên mạch Artix7, 213 phần tử.<br /> <br /> <br /> <br /> <br /> So sánh với kết quả đưa ra của hãng Xilinx trong [9] nhận thấy:<br /> - Tài nguyên sử dụng tương ứng ít hơn của Xilinx khoảng 10%.<br /> - Số chu kỳ để ghi (learning) nhỏ hơn Xilinx (4 chu kỳ so với 32 của Xilinx<br /> trong trường hợp bảng gần đầy).<br /> - Tốc độ hoạt động của hệ thống đáp ứng tương đương của Xilinx.<br /> 4. KẾT LUẬN<br /> Qua quá trình nghiên cứu, kết hợp giữa lý thuyết, mô phỏng, và thực thi trên<br /> phần cứng FPGA, kết quả nghiên cứu đã chỉ rõ sự kết hợp giữa hàm băm CRC16-<br /> CCITT và phân bảng băm ra 16 đoạn, với kích thước bằng 1/16 bảng chính cho kết<br /> quả rất tốt. Với số lượng 1000 địa chỉ MAC kết nối, với 100 lần thử thử thì số<br /> xung đột là bằng 0. Phương pháp sử dụng có thể được xem như phương pháp hàm<br /> băm hoàn hảo. Trong đó hàm CRC16-CCITT được sử dụng xuyên suốt trong các<br /> phân chia đoạn khác nhau của bảng băm. Kết quả cũng thể hiện được việc thực<br /> hiện thành công thuật toán trên phần cứng, từ đó tạo nền tảng để thiết kế chế tạo<br /> hoàn chình thiết bị chuyển mạch lớp 2. Kết quả thực nghiệm trên phần cứng khi so<br /> sánh với [9] của hãng Xilinx cho thấy thuật toán đề xuất có những ưu việt hơn về<br /> tài nguyên sử dụng cũng như số chu kỳ xung nhịp. Đây là một trong những kết quả<br /> ấn tượng khi thử nghiệm.<br /> Lời cảm ơn: Bài báo này là một phần kết quả nghiên cứu của đề tài 18/2018/ĐTCT-<br /> KC.01/16-20, ngày 15/11/2018 [3]. Chúng tôi trân trọng cảm ơn ban chủ nhiệm chương<br /> trình KC01/16-20, Văn phòng Các chương trình trọng điểm cấp nhà nước, Vụ Công nghệ<br /> cao, Vụ Kế hoạch tài chính Bộ Khoa học và Công nghệ, Viện CNTT/ Viện KHCNQS đã hỗ<br /> trợ đề tài này.<br /> <br /> <br /> <br /> 22 T. T. Kiên, …, N. V. Thành, “Nghiên cứu bảng địa chỉ mạng … trên nền tảng FPGA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> REFERENCES<br /> [1]. Cisco, Configuring the MAC Address Table, https://www.cisco.com/c/en/<br /> us/td/docs/switches/datacenter/nexus3000/sw/layer2/503_U2_1/b_Cisco_n3k_<br /> layer2_config_guide_503_U2_1/b_Cisco_n3k_layer2_config_gd_503_U2_1_<br /> chapter_01101.pdf, truy cập ngày 15/12/2018<br /> [2]. How switches learn MAC addresses, https://geek-university.com/ccna/how-<br /> switches-learn-mac-addresses/, truy cập ngày 15/12/2018<br /> [3]. Wikipedia, “Bảng băm”, https://vi.wikipedia.org/wiki/B%E1%BA%A3ng<br /> _b%C4%83m, truy cập ngày 15/1/2018.<br /> [4]. Brad Miller and David Ranum, "Problem Solving with Algorithms and Data<br /> Structures using Python", Luther College, truy cập ngày 15/1/2018.<br /> [5]. R. Jain, “A Comparison of Hashing Schemes for Address Lookup in Computer<br /> Networks”, IEEE Transactions on Communications, Vol. 40, No. 3, October<br /> 1992, pp. 1570-1573<br /> [6]. Brad Matthews, “Puneet Agarwal, Hash proposal, IEEE 802.1Qbp”,<br /> Broadcom, June 23, 2011.<br /> [7]. Broadcom Corp, Method and apparatus for dual-hashing tables, US patent<br /> US20080229056A1, 12-3-2007.<br /> [8]. Thái Trung Kiên và cộng sự, “Thuyết minh đề tài: Nghiên cứu thiết kế, chế tạo<br /> thiết bị chuyển mạch (Switch) có tính năng an toàn, bảo mật thông tin trên nền<br /> tảng FPGA và mã nguồn mở”, 18/2018/ĐTCT-KC.01/16-20, ngày<br /> 15/11/2018.<br /> [9]. Xilinx, SmartCORE IP Product Guide www.xilinx.com/support/documentation/<br /> ip_documentation/cam/pg189-cam.pdf, truy cập ngày 07/1/2019.<br /> ABSTRACT<br /> MAC TABLE IMPLEMENTATION AND ESTIMATION FOR DESIGNING<br /> SWITCH LAYER 2 DEVICE BASED ON FPGA<br /> The paper focuses on introduces a method for building an MAC address<br /> table based on a hash table, a method for reducing collision, and an<br /> implement on FPGA hardware. A new scheme of algorithm for reducing<br /> collision is proposed based on the perfect hashing method. In this method,<br /> the main hash table is devided into 16 segments, and combining with second<br /> hash table. The result of simulation on Labview shows that collision is<br /> bellow 1%. The proposed method is implemented on Artix7 200 Mhz FPGA<br /> of Xinlix to test performence for learning and lookuping. The result shows<br /> that the proposed method can be used to design a 100 Gbps layer 2 switch<br /> device whih packet size is 64 bytes (the minimized Ethernet packet).<br /> Keywords: MAC table; Hash table; Hash function; Switch layer 2.<br /> Nhận bài ngày 23 tháng 12 năm 2018<br /> Hoàn thiện ngày 10 tháng 3 năm 2019<br /> Chấp nhận đăng ngày 25 tháng 3 năm 2019<br /> 1<br /> Địa chỉ: Viện CNTT/Viện KHCNQS;<br /> 2<br /> Công ty TNHH Đầu tư Phát triển sản phẩm Công nghệ cao HTP.<br /> *<br /> Email: kienthaitrung@gmail.com.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 23<br />