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 - Thái Trung Kiên

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