Про MAC-таблицы в коммутаторах

Привет!
Случается так, что иногда хочется отойти от скупой теории и перейти к практике. Сейчас как раз такой случай. Желание возникло на фоне воспоминаний того, как мы делали коммутатор. Он — вещь довольно простая, делов-то — пересылай пакеты с порта на порт, да статистику веди. Все оказалось немного сложнее.

Вы когда нибудь задумывались над тем, как происходит коммутация? На курсах говорят, что пакет из порта (А) анализируется и пересылается согласно таблице соответствия в порт (Б) назначения, или во все порты, кроме (А) источника, если запись не найдена. Остановимся на таблице и разберем как происходит ее заполнение.
Самый простой способ — записывать адреса в один столбец, а соответствующие порты в другой, т.е. используется линейный алгоритм поиска, асимптотическая сложность которого O(n). Худший случай для алгоритма — отсутствие искомого ключа, поскольку требуется просмотреть все ключи, и в коммутации встречается очень часто: включение нового клиента, включение или перезагрузка устройства. На самом деле, всевозможные оптимизации и хитрые алгоритмы, применяемые в чипах сетевых устройств, заточены либо для экономии памяти чипа, либо для удовлетворения требований по скорости обработки.
Используемый же большинством производителей способ — хеш-таблица. Смысл в том, что при вычислении хеш-функции от MAC-адреса на выходе имеем сразу адрес в памяти (индекс), обратившись по которому вычитываем номер порта. Если ничего не вычитали, то пишем по этому адресу текущий порт. Сложность алгоритма поиска O(1). Правда существует проблема коллизий, но при правильно подобранной хеш-функции она минимизируется. Остается лишь проверить коллизионную стойкость устройства. Наглядный пример такой таблицы и частичной коллизии:
У большинства записей хеш-индексы не совпадают, что в результате дает мгновенное чтение по индексу, но у Jack и Andrew случилось так, что хеш совпал и проявилась коллизия. В этом случае для разрешения коллизии производится линейный поиск по вложенному списку, что увеличивает задержку, но происходит это в единичных случаях.
Проверку можно провести, пополняя хеш-таблицу новыми записями. Записи могут быть последовательными или случайным, а так же принадлежать специальным типам.
Специальные типы MAC-адресов:

• broadcast (FF:FF:FF:FF:FF:FF)
• mulicast (младший бит первого октета равен 1)

Не все адреса должны записываться в таблицу. Например туда не попадают широковещательный и мультикаст адреса. В результате я написал небольшой генератор raw-пакетов, которому передаются параметры:

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

В обычном режиме генерируются пакеты с последовательными MAC-адресами, изменяются последние два октета, что дает 65536 комбинаций и для большинства коммутаторов более чем достаточно (всегда можно увеличить). Первый октет выставлен в 0x00, т.е. адреса юникастовые. Случайные адреса генерируются в двух режимах:

• первый октет 0x00, остальные случайны
• все октеты случайны

Предусмотрен запуск в медленном режиме, например для тестирования aging-time.
Интересно как на флуд отреагирует оборудование: проверим в двух режимах (последовательном и случайном) сколько адресов попадут в таблицу. У меня в тестовой стойке 5 коммутаторов:

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

Специально никто их не отбирал — просто используются для различных целей, вроде проверки на совместимость STP (про это вообще можно отдельную статью написать). Пойдем по порядку.

cisco 3750G-16TD-S

Информация о платформе:

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 U.S. and local country laws. By using this product you
agree to comply with applicable laws and regulations. If you are unable
to comply with U.S. and local laws, return this product immediately.

A summary of U.S. 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

Странно, но пишет, что у нее памяти всего на 5507 адресов:

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

Total Mac Address Space Available: 5507

Настройки тестового порта:

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

Пустая таблица адресов для тестового vlan:

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

После пробного теста (./send_pkt -i eth0 -n 10) наблюдаем следующее:

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

Одиннадцатый адрес — это адрес нетбука, с которого запускался тест. Доступное место для адресов уменьшился.
Сгенерируем заведомо большее, чем заявлено, количество адресов (12288), я указал 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

Как видно, заполнить всю таблицу удалось не сразу и попали далеко не все адреса, вот вам и колизионность. Пробую еще раз:

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

И медленный режим (максимум, что удалось вместить):

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

Рандомный тест:
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

Рандомный медленный тест:

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

Итог
Получается, что заявленная производителем характеристика не соответствует действительности (если я не прав, например влияет IOS и для него есть особые заметки, дайте знать с пруфом). Разница почти в два раза. Даже если опираться на сведения, выводимые самой системой (5507), то им тоже не стоит верить: в быстром режиме таблица недозаполнилась на 1219 адресов, а в медленном постоянно перестраивалась и показания суммарного счетчика менялись, от режима генерации (последовательно/случайно) не зависит.

ZyXEL GS-3012F

Информация о платформе:

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

zyxel-01-T# show 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 Version: V3.00 | 01/14/2005
ZyNOS CODE: RAS Mar 4 2008 11:51:18
Product Model: GS-3012F

Генерируем с превышением 17000 (поддерживается 16384):

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

Медленный режим не использовался, т.к. даже в быстром таблица заполнена практически полностью.
Рандомный тест:

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

Итог
В целом, хорошие результаты. Коммутатор не “теряет” адреса, генерируемые на скорости порта. Размер таблицы и ее заполнение соответствует заявленному.

D-Link DGS-3426

Информация о платформе:

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]

Генерируем с превышением 9000 (поддерживается 8192):

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

Медленный режим, как и в предыдущем тесте не использовался, поскольку таблица заполнена почти полностью.
Рандомный тест:

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

Итог
У этого коммутатора тоже все в порядке. Таблица заполняется как заявлено, на случайных данных показатели незначительно хуже. А в качестве “фишки” таблица маков при просмотре сортируется (возможно потому, что никакого строкового процессора нет, например как у cisco).

Metrotek X10-24

Этот коммутатор, точнее его разработка — причина статьи. В нем используется ASIC матрица от японской компании Fujitsu. Изучая документацию, можно сделать вывод, что экономили ресурсы очень серьезно, поэтому и были выполнены независимые тесты.
Информация о платформе:

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

Генерируем с превышением 17000 (поддерживается 16368):

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

Медленный режим не использовался
Рандомный тест:

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

Итог
Для инкрементарных адресов таблица полностью соответствует заявленной, а вот для случайных показатели ухудшаются, хотя и лежат в довольно близком к заявленному диапазоне.

Вывод

Если ваша сеть построена таким образом, что домен L2 включает множество устройств, то можно ждать беды. Странным оказалось то, что самый весомый вендор показал худшие результаты. Отсюда мораль — доверяй только собственным глазам и тесту, а не маркетинговым заявлениям с мелким шрифтом в сноске.
Я был так удивлен положением вещей, что решил об этом написать. Если есть возможность провести такой же тест, то прошу опубликовать результаты в комментариях.

Спасибо за внимание.

Автор: abehterev

Источник