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 
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.