About MAC tables in switches

Hello, Habr!
It so happens that sometimes you want to move away from a mean theory and move on to practice. Now this is just the case. The desire arose against the backdrop of memories of how we made the switch . It is a rather simple thing, business something - forward packets from port to port, and keep statistics. Everything turned out to be a little more complicated.




Have you ever thought about how switching occurs? The courses say that the packet from port (A) is analyzed and forwarded according to the correspondence table to the destination port (B), or to all ports except (A) the source, if the record is not found. Let us dwell on the table and analyze how its filling occurs.
The easiest way is to write the addresses in one column, and the corresponding ports in another, i.e. a linear search algorithm is used, the asymptotic complexity of which is O (n). The worst case for the algorithm is the lack of the required key, because you need to view all the keys, and it is very common in switching: turning on a new client, turning on or rebooting the device. In fact, all kinds of optimizations and tricky algorithms used in the chips of network devices are sharpened either to save the memory of the chip, or to satisfy the requirements for processing speed.
The method used by most manufacturers is a hash table. The point is that when calculating the hash function from the MAC address at the output, we immediately have the memory address (index), by which we subtract the port number. If you didn’t subtract anything, then write the current port to this address. The complexity of the search algorithm is O (1). True, there is a problem of collisions , but with a correctly selected hash function, it is minimized. It remains only to check the collision resistance of the device. A good example of such a table and partial collision:
For most records, the hash indexes do not match, resulting in instant reads on the index, but Jack and Andrew have the case that the hash is the same and there is a collision. In this case, to resolve the conflict, a linear search is performed on the nested list, which increases the delay, but this happens in isolated cases.
Checking can be done by adding new entries to the hash table. Records can be sequential or random, and also belong to special types.
Special types of MAC addresses:

• broadcast (FF: FF: FF: FF: FF: FF)
• multicast (the least significant bit of the first octet is 1)

Not all addresses must be written to the table. For example, broadcast and multicast addresses do not get there. As a result, I wrote a small raw-packet generator that receives parameters:

send_pkt -i  -n 
-i   interface for packet sending
-n     number of MAC's
-s work in slow mode
-r generate random Src MAC for each new packet
-a set random for all octets 

In normal mode, packets with sequential MAC addresses are generated, the last two octets are changed, which gives 65,536 combinations and is more than enough for most switches (you can always increase it). The first octet is set to 0x00, i.e. Unicast addresses. Random addresses are generated in two modes:

• the first octet is 0x00, the rest are random
• all octets are random

It can be run in slow mode, for example, for testing aging-time.
It is interesting how the equipment will react to the flood: we will check in two modes (sequential and random) how many addresses will be in the table. I have 5 switches in the test rack:

• cisco 3750G-16TD-S (12288 MAC)
• zyxel gs-3012f (16384 MAC)
• d-link dgs-3426 (8192 MAC)
• metrotek x10-24 (16368 MAC)

No one specially selected them - they are simply used for various purposes, such as testing for STP compatibility (you can write a separate article about this in general). Let's go in order.

cisco 3750G-16TD-S

Platform Information:

cisco-01-TEST # sh ver
Cisco IOS Software, C3750 Software (C3750-ADVIPSERVICESK9-M), Version 12.2 (46) SE, RELEASE SOFTWARE (fc2)
Copyright 1986-2008 by Cisco Systems, Inc.
Compiled Thu 21-Aug-08 15:43 by nachen
Image text-base: 0x00003000, data-base: 0x01940000

ROM: Bootstrap program is C3750 boot loader
BOOTLDR: C3750 Boot Loader (C3750-HBOOT-M) Version 12.2 (18) SE1 , RELEASE SOFTWARE (fc2)

cisco-01-TEST uptime is 4 weeks, 5 days, 1 hour, 11 minutes
System returned to ROM by power-on
System image file is "flash: c3750-advipservicesk9-mz.122-46.SE »

This product contains cryptographic features and is subject to United
States and local country laws governing import, export, transfer and
use. Delivery of Cisco cryptographic products does not imply
third-party authority to import, export, distribute or use encryption.
Importers, exporters, distributors and users are responsible for
compliance with US and local country laws. By using this product you
agree to comply with applicable laws and regulations. If you are unable
to comply with US and local laws, return this product immediately.

A summary of US laws governing Cisco cryptographic products may be found at:
www.cisco.com/wwl/export/crypto/tool/stqrg.html

If you require further assistance please contact us by sending email to
export@cisco.com.

cisco WS-C3750G-16TD (PowerPC405) processor (revision F0) with 118784K / 12280K bytes of memory.
Processor board ID CSG0921P0EB
Last reset from power-on
1 Virtual Ethernet interface
16 Gigabit Ethernet interfaces
1 Ten Gigabit Ethernet interface
The password-recovery mechanism is enabled.

512K bytes of flash-simulated non-volatile configuration memory.
Base ethernet MAC Address: 00: 14: 1C: D7: 33: 80
Motherboard assembly number: 73-9143-08
Power supply part number: 341-0045-01
Motherboard serial number: CAT091916AM
Power supply serial number: LIT09130942
Model revision number: F0
Motherboard revision number: A0
Model number: WS-C3750G-16TD-S
System serial number: CSG0921P0EB
Top Assembly Part Number: 800-24591-04
Top Assembly Revision Number: A0
CLEI Code Number: COM1D10ARB
Hardware Board Revision Number: 0x01

Switch Ports Model SW Version SW Image
- - - - -
* 1 17 WS-C3750G -16TD 12.2 (46) SE C3750-ADVIPSERVICESK9-M

Configuration register is 0xF

Strange, but writes that she has only 5507 memory addresses:

cisco-01-TEST # show mac address-table count

Total Mac Address Space Available: 5507

Test port settings:

interface GigabitEthernet1 / 0/1
switchport access vlan 20
switchport mode access
end

Empty address table for test vlan:

cisco-01-TEST # sh mac- vl 20
Mac Address Table
- Vlan Mac Address Type Ports
- - - -----

After the trial test ( ./send_pkt -i eth0 -n 10 ) we observe the following:

cisco-01-TEST # show mac address-table count

Mac Entries for Vlan 20:
- Dynamic Address Count: 11
Static Address Count: 0
Total Mac Addresses: 11

Total Mac Address Space Available: 5496

cisco-01-TEST # sh mac- vl 20
Mac Address Table
- Vlan Mac Address Type Ports
- - - - 20 0001.0203.0001 DYNAMIC Gi1 /
0/1 20 0001.0203.0002 DYNAMIC Gi1 /
0/1 20 0001.0203.0003 DYNAMIC Gi1 /
0/1 20 0001.0203.0004 DYNAMIC Gi1 / 0/1
20 0001.0203.0005 DYNAMIC Gi1 / 0/1
20 0001.0203.0006 DYNAMIC Gi1 /
0/1 20 0001.0203.0007 DYNAMIC Gi1 /
0/1 20 0001.0203.0008 DYNAMIC Gi1 /
0/1 20 0001.0203.0009 DYNAMIC Gi1 / 0/1
20 0001.0203.000a DYNAMIC Gi1 / 0/1
20 50af.7312.8435 DYNAMIC Gi1 / 0/1

The eleventh address is the address of the netbook from which the test was run. Available space for addresses has decreased.
We will generate obviously more than the stated number of addresses (12288), I indicated 13000:

cisco-01-TEST # show mac address-table count

Mac Entries for Vlan 20:
- Dynamic Address Count: 4281
Static Address Count: 0
Total Mac Addresses: 4281

Total Mac Address Space Available: 1219

As you can see, it was not possible to fill out the entire table immediately and far from all the addresses, here you have the colosity. I try again:

cisco-01-TEST # show mac address-table count

Mac Entries for Vlan 20:
- Dynamic Address Count: 5724
Static Address Count: 0
Total Mac Addresses: 5724

Total Mac Address Space Available: 192

And slow mode (maximum that managed to accommodate):

Mac Entries for Vlan 20:
- Dynamic Address Count: 5945
Static Address Count: 0
Total Mac Addresses: 5945

Total Mac Address Space Available: 3

cisco-01-TEST # show mac address-table count

Random Test:
cisco-01-TEST # sh mac address-table count

Mac Entries for Vlan 20:
- Dynamic Address Count: 4417
Static Address Count: 0
Total Mac Addresses: 4417

Total Mac Address Space Available: 1499

Random Slow Test:

cisco-01-TEST # sh mac address-table count

Mac Entries for Vlan 20:
- Dynamic Address Count: 5947
Static Address Count: 0
Total Mac Addresses: 5947

Total Mac Address Space Available: 1

Result
It turns out that the characteristic declared by the manufacturer is not true (if I'm wrong, for example, IOS affects and there are special notes for it, let me know with proof). The difference is almost twice. Even if you rely on the information displayed by the system itself (5507), you should not believe it either: in fast mode, the table was underfilled with 1219 addresses, and in slow mode it was constantly rebuilt and the total counter readings changed, it does not depend on the generation mode (sequentially / randomly) .

ZyXEL GS-3012F

Platform Information:

zyxel-01-T # show version
Current ZyNOS version: V3.80 (LR.2) | 03/04/2008

zyxel-01 # show T-system-information
System Name: zyxel-01 TEST-
System Contact:
System Location:
Ethernet Address: 00: 19: cb: 2d: d8: 49
ZyNOS F / W Version: V3 .80 (LR.2) | 03/04/2008
RomRasSize: 3234952
System up Time: 837: 37: 39 (11f939d5 ticks)
Bootbase the Version: V3.00 | 14/01/2005
ZyNOS CODE: RAS Mar 4 2008 11:51:18
Product Model: GS-3012F

We generate with an excess of 17000 (16384 is supported):

zyxel-01-T # show mac-count
No: 16312

Slow mode was not used, because even in a fast table, it’s almost full.
Random Test:

zyxel-01-T # show mac-count
No: 14331

Bottom line
Overall, good results. The switch does not “lose” addresses generated at the port speed. The size of the table and its filling corresponds to the declared.

D-Link DGS-3426

Platform Information:

DGS-3426: admin # show tech_support
Command: show tech_support

# ------------------------------------- ------------------------------------------
# DGS-3426 Gigabit Ethernet Switch
# Technical Support Information
#
# Firmware: Build 2.70.B56
# Copyright 2010 D-Link Corporation. All rights reserved.
# ------------------------------------------------- ------------------------------

********************* Basic System Information ********************

[SYS 2000-1-1 00:07:51]

Boot Time: 31 Dec 1999 23:59:59
RTC Time: 2000/01/01 00:07:51
Boot PROM Version: Build 1.00-B13
Firmware Version: Build 2.70.B56
Hardware Version: 2A1
MAC Address: 00-17-9A-10-CD-AA
[STACKING 2000-1-1 00:07:51]

We generate with excess of 9000 (8192 is supported):

DGS-3426: admin # show fdb vlan TEST
Command: show fdb vlan TEST

VID VLAN Name MAC Address Port Type
- - - - - 20 TEST 00-01-02-03-00-01 1 Dynamic
20 TEST 00-01-02 -03-00-02 1 Dynamic
20 TEST 00-01-02-03-00-03 1 Dynamic
20 TEST 00-01-02-03-00-04 1 Dynamic
20 TEST 00-01-02-03-00- 05 1 Dynamic
20 TEST 00-01-02-03-00-06 1 Dynamic
20 TEST 00-01-02-03-00-07 1 Dynamic
20 TEST 00-01-02-03-00-08 1 Dynamic
20 TEST 00-01-02-03-00-09 1 Dynamic
20 TEST 00-01-02-03-00-0A 1 Dynamic
20 TEST 00-01-02-03-00-0B 1 Dynamic
20 TEST 00-01-02 -03-00-0C 1 Dynamic
20 TEST 00-01-02-03-00-0D 1 Dynamic

...

Total Entries: 8147

Slow mode, as in the previous test, was not used, since the table is almost full.
Random Test:

DGS-3426: admin # show fdb vlan TEST
Command: show fdb vlan TEST

VID VLAN Name MAC Address Port Type
- - - - - 20 TEST 00-00-01-33-82-27 1 Dynamic
20 TEST 00-00-03 -43-5A-66 1 Dynamic
20 TEST 00-00-03-66-C4-5D 1 Dynamic
20 TEST 00-00-05-32-86-B1 1 Dynamic
20 TEST 00-00-07-6D-3A- 40 1 Dynamic
20 TEST 00-00-0A-0F-E0-AE 1 Dynamic
20 TEST 00-00-22-3A-81-2B 1 Dynamic
20 TEST 00-00-24-68-E9-70 1 Dynamic
20 TEST 00-00-35-00-B0-93 1 Dynamic
20 TEST 00-00-3F-04-BE-95 1 Dynamic
20 TEST 00-00-43-01-A4-A4 1 Dynamic
20 TEST 00-00-71 -27-41-8A 1 Dynamic
20 TEST 00-00-92-3C-2A-5A 1 Dynamic
20 TEST 00-00-92-5B-94-62 1 Dynamic
20 TEST 00-00-95-26-49-3D 1 Dynamic
20 TEST 00-00-9F-2E-45-DF 1 Dynamic
20 TEST 00-00-9F-6D-BE-1E 1 Dynamic
20 TEST 00-00 -A7-75-72-4F 1 Dynamic
20 TEST 00-00-A9-17-38-DD 1 Dynamic
20 TEST 00-00-AF-5A-8C-54 1 Dynamic

...

Total Entries: 7327

Summary
This switch is also fine. The table is filled as stated, on random data indicators are slightly worse. And as a “chip”, the table of poppies is sorted when viewed (possibly because there is no string processor, for example, like cisco).

Metrotek X10-24

This switch, or rather its development, is the reason for the article. It uses an ASIC matrix from the Japanese company Fujitsu. Studying the documentation, we can conclude that they saved resources very seriously, therefore independent tests were performed.
Platform Information:

x10-00002 # show version report
Origin: Metrotek
Label: Metrotek
Codename: oxygen
Version: 1.0.1
Date: Wed, 4 Mar 2015 11:04:37 UTC
Architectures: armel i386
Components: contrib non-free
Description: Metrotek X10-24 Gigabit ethernet switch

We generate with an excess of 17000 (supported by 16368):

root @ x10-00002: ~ # show-mac-table -v 20 | wc -l
16368

Slow mode not used.
Random test:

root @ x10-00002: ~ # show-mac-table -v 20 | wc -l
14429

Summary
For incremental addresses, the table is fully consistent with the declared, but for random indicators worsen, although they lie quite close to the declared range.

Conclusion

If your network is built in such a way that the L2 domain includes many devices, then you can expect trouble. It was strange that the most powerful vendor showed the worst results. Hence the moral - trust only your own eyes and test, and not marketing statements with a small print in a footnote.
I was so surprised by the state of things that I decided to write about it. If it is possible to conduct the same test, then please post the results in the comments.

Thanks for attention.