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

Trong bài viết 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 viết đề 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.
Nội dung trích xuất từ tài liệu:
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 FPGACông nghệ thông tinNGHIÊ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ên1*, Hoàng Đình Thắng1, Đào Xuân Ước1, Nguyễn Văn Thành2 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ểnmạch, hay định tuyến (switch, router), thì thông tin máy tính nối mạng được thuthậ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ôngcụ cấu hình địa chỉ IP. Còn địa chỉ mạng (MAC) không thể thay đổi đối với ngườisử 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 đíchkhô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ánduy nhất cho thiết bị khi truy cập vào mạng. Thông thường trong mạng LAN, cácmá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ểnmạ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ẽ thuthậ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ểnmạ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 tincủ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ủamá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ôngtin đị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ácthiế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ôngtin đế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áyB 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 Bkhô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ểnmạch trừ cổng gắn với máy A.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.”Nghiên cứu khoa học công nghệ 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ácphươ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ôngdụ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ìmkiế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ựcnghiệ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ẠNG2.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ắtgặ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ựchiệ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ácthiế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ậpgố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ảngbă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ốimạ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àobả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ầntử 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): ...