Про MAC-таблицы в коммутаторах
Привет, Хабр! Случается так, что иногда хочется отойти от скупой теории и перейти к практике. Сейчас как раз такой случай. Желание возникло на фоне воспоминаний того, как мы делали коммутатор. Он — вещь довольно простая, делов-то — пересылай пакеты с порта на порт, да статистику веди. Все оказалось немного сложнее.Вы когда нибудь задумывались над тем, как происходит коммутация? На курсах говорят, что пакет из порта (А) анализируется и пересылается согласно таблице соответствия в порт (Б) назначения, или во все порты, кроме (А) источника, если запись не найдена. Остановимся на таблице и разберем как происходит ее заполнение.Самый простой способ — записывать адреса в один столбец, а соответствующие порты в другой, т.е. используется линейный алгоритм поиска, асимптотическая сложность которого O (n). Худший случай для алгоритма — отсутствие искомого ключа, поскольку требуется просмотреть все ключи, и в коммутации встречается очень часто: включение нового клиента, включение или перезагрузка устройства. На самом деле, всевозможные оптимизации и хитрые алгоритмы, применяемые в чипах сетевых устройств, заточены либо для экономии памяти чипа, либо для удовлетворения требований по скорости обработки.Используемый же большинством производителей способ — хеш-таблица. Смысл в том, что при вычислении хеш-функции от MAC-адреса на выходе имеем сразу адрес в памяти (индекс), обратившись по которому вычитываем номер порта. Если ничего не вычитали, то пишем по этому адресу текущий порт. Сложность алгоритма поиска O (1). Правда существует проблема коллизий, но при правильно подобранной хеш-функции она минимизируется. Остается лишь проверить коллизионную стойкость устройства. Наглядный пример такой таблицы и частичной коллизии: 
У большинства записей хеш-индексы не совпадают, что в результате дает мгновенное чтение по индексу, но у Jack и Andrew случилось так, что хеш совпал и проявилась коллизия. В этом случае для разрешения коллизии производится линейный поиск по вложенному списку, что увеличивает задержку, но происходит это в единичных случаях.Проверку можно провести, пополняя хеш-таблицу новыми записями. Записи могут быть последовательными или случайным, а так же принадлежать специальным типам.Специальные типы MAC-адресов:
broadcast (FF: FF: FF: FF: FF: FF)
mulicast (младший бит первого октета равен 1)
Не все адреса должны записываться в таблицу. Например туда не попадают широковещательный и мультикаст адреса. В результате я написал небольшой генератор raw-пакетов, которому передаются параметры:
send_pkt -i 
Специально никто их не отбирал — просто используются для различных целей, вроде проверки на совместимость STP (про это вообще можно отдельную статью написать). Пойдем по порядку.cisco 3750G-16TD-S
Информация о платформе:
cisco-01-TEST#sh verCisco 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 nachenImage text-base: 0×00003000, data-base: 0×01940000
ROM: Bootstrap program is C3750 boot loaderBOOTLDR: 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 minutesSystem returned to ROM by power-onSystem image file is «flash: c3750-advipservicesk9-mz.122–46.SE»
This product contains cryptographic features and is subject to UnitedStates and local country laws governing import, export, transfer anduse. Delivery of Cisco cryptographic products does not implythird-party authority to import, export, distribute or use encryption.Importers, exporters, distributors and users are responsible forcompliance with U.S. and local country laws. By using this product youagree to comply with applicable laws and regulations. If you are unableto 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 toexport@cisco.com.
cisco WS-C3750G-16TD (PowerPC405) processor (revision F0) with 118784K/12280K bytes of memory.Processor board ID CSG0921P0EBLast reset from power-on1 Virtual Ethernet interface16 Gigabit Ethernet interfaces1 Ten Gigabit Ethernet interfaceThe password-recovery mechanism is enabled.
512K bytes of flash-simulated non-volatile configuration memory.Base ethernet MAC Address: 00:14:1C: D7:33:80Motherboard assembly number: 73–9143–08Power supply part number: 341–0045–01Motherboard serial number: CAT091916AMPower supply serial number: LIT09130942Model revision number: F0Motherboard revision number: A0Model number: WS-C3750G-16TD-SSystem serial number: CSG0921P0EBTop Assembly Part Number: 800–24591–04Top Assembly Revision Number: A0CLEI Code Number: COM1D10ARBHardware Board Revision Number: 0×01
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/1switchport access vlan 20switchport mode accessend
Пустая таблица адресов для тестового vlan: cisco-01-TEST#sh mac- vl 20Mac 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: 11Static Address Count: 0Total Mac Addresses: 11
Total Mac Address Space Available: 5496
cisco-01-TEST#sh mac- vl 20Mac Address Table— Vlan Mac Address Type Ports— — — — 20 0001.0203.0001 DYNAMIC Gi1/0/120 0001.0203.0002 DYNAMIC Gi1/0/120 0001.0203.0003 DYNAMIC Gi1/0/120 0001.0203.0004 DYNAMIC Gi1/0/120 0001.0203.0005 DYNAMIC Gi1/0/120 0001.0203.0006 DYNAMIC Gi1/0/120 0001.0203.0007 DYNAMIC Gi1/0/120 0001.0203.0008 DYNAMIC Gi1/0/120 0001.0203.0009 DYNAMIC Gi1/0/120 0001.0203.000a DYNAMIC Gi1/0/120 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: 4281Static Address Count: 0Total 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: 5724Static Address Count: 0Total Mac Addresses: 5724
Total Mac Address Space Available: 192
И медленный режим (максимум, что удалось вместить): Mac Entries for Vlan 20: — Dynamic Address Count: 5945Static Address Count: 0Total 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: 4417Static Address Count: 0Total 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: 5947Static Address Count: 0Total Mac Addresses: 5947
Total Mac Address Space Available: 1
ИтогПолучается, что заявленная производителем характеристика не соответствует действительности (если я не прав, например влияет IOS и для него есть особые заметки, дайте знать с пруфом). Разница почти в два раза. Даже если опираться на сведения, выводимые самой системой (5507), то им тоже не стоит верить: в быстром режиме таблица недозаполнилась на 1219 адресов, а в медленном постоянно перестраивалась и показания суммарного счетчика менялись, от режима генерации (последовательно/случайно) не зависит.
ZyXEL GS-3012F Информация о платформе: zyxel-01-T# show versionCurrent ZyNOS version: V3.80(LR.2) | 03/04/2008
zyxel-01-T# show system-informationSystem Name: zyxel-01-TESTSystem Contact: System Location: Ethernet Address: 00:19: cb:2d: d8:49ZyNOS F/W Version: V3.80(LR.2) | 03/04/2008RomRasSize: 3234952System up Time: 837:37:39 (11f939d5 ticks)Bootbase Version: V3.00×01/14/2005ZyNOS CODE: RAS Mar 4 2008 11:51:18Product Model: GS-3012F
Генерируем с превышением 17000 (поддерживается 16384): zyxel-01-T# show mac-countNo: 16312
Медленный режим не использовался, т.к. даже в быстром таблица заполнена практически полностью.Рандомный тест: zyxel-01-T# show mac-countNo: 14331
ИтогВ целом, хорошие результаты. Коммутатор не «теряет» адреса, генерируемые на скорости порта. Размер таблицы и ее заполнение соответствует заявленному.
D-Link DGS-3426 Информация о платформе: DGS-3426: admin#show tech_supportCommand: 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:59RTC Time: 2000/01/01 00:07:51Boot PROM Version: Build 1.00-B13Firmware Version: Build 2.70.B56Hardware Version: 2A1MAC Address: 00–17–9A-10-CD-AA[STACKING 2000–1–1 00:07:51]
Генерируем с превышением 9000 (поддерживается 8192): DGS-3426: admin#show fdb vlan TESTCommand: show fdb vlan TEST
VID VLAN Name MAC Address Port Type— — — — — 20 TEST 00–01–02–03–00–01 1 Dynamic20 TEST 00–01–02–03–00–02 1 Dynamic20 TEST 00–01–02–03–00–03 1 Dynamic20 TEST 00–01–02–03–00–04 1 Dynamic20 TEST 00–01–02–03–00–05 1 Dynamic20 TEST 00–01–02–03–00–06 1 Dynamic20 TEST 00–01–02–03–00–07 1 Dynamic20 TEST 00–01–02–03–00–08 1 Dynamic20 TEST 00–01–02–03–00–09 1 Dynamic20 TEST 00–01–02–03–00–0A 1 Dynamic20 TEST 00–01–02–03–00–0B 1 Dynamic20 TEST 00–01–02–03–00–0C 1 Dynamic20 TEST 00–01–02–03–00–0D 1 Dynamic
…
Total Entries: 8147
Медленный режим, как и в предыдущем тесте не использовался, поскольку таблица заполнена почти полностью.Рандомный тест: DGS-3426: admin#show fdb vlan TESTCommand: show fdb vlan TEST
VID VLAN Name MAC Address Port Type— — — — — 20 TEST 00–00–01–33–82–27 1 Dynamic20 TEST 00–00–03–43–5A-66 1 Dynamic20 TEST 00–00–03–66-C4–5D 1 Dynamic20 TEST 00–00–05–32–86-B1 1 Dynamic20 TEST 00–00–07–6D-3A-40 1 Dynamic20 TEST 00–00–0A-0F-E0-AE 1 Dynamic20 TEST 00–00–22–3A-81–2B 1 Dynamic20 TEST 00–00–24–68-E9–70 1 Dynamic20 TEST 00–00–35–00-B0–93 1 Dynamic20 TEST 00–00–3F-04-BE-95 1 Dynamic20 TEST 00–00–43–01-A4-A4 1 Dynamic20 TEST 00–00–71–27–41–8A 1 Dynamic20 TEST 00–00–92–3C-2A-5A 1 Dynamic20 TEST 00–00–92–5B-94–62 1 Dynamic20 TEST 00–00–95–26–49–3D 1 Dynamic20 TEST 00–00–9F-2E-45-DF 1 Dynamic20 TEST 00–00–9F-6D-BE-1E 1 Dynamic20 TEST 00–00-A7–75–72–4F 1 Dynamic20 TEST 00–00-A9–17–38-DD 1 Dynamic20 TEST 00–00-AF-5A-8C-54 1 Dynamic
…
Total Entries: 7327
ИтогУ этого коммутатора тоже все в порядке. Таблица заполняется как заявлено, на случайных данных показатели незначительно хуже. А в качестве «фишки» таблица маков при просмотре сортируется (возможно потому, что никакого строкового процессора нет, например как у cisco).
Metrotek X10–24 Этот коммутатор, точнее его разработка — причина статьи. В нем используется ASIC матрица от японской компании Fujitsu. Изучая документацию, можно сделать вывод, что экономили ресурсы очень серьезно, поэтому и были выполнены независимые тесты.Информация о платформе: x10–00002# show version reportOrigin: MetrotekLabel: MetrotekCodename: oxygenVersion: 1.0.1Date: Wed, 4 Mar 2015 11:04:37 UTCArchitectures: armel i386Components: contrib non-freeDescription: Metrotek X10–24 Gigabit Ethernet Switch
Генерируем с превышением 17000 (поддерживается 16368): root@x10–00002:~# show-mac-table -v 20 | wc -l16368
Медленный режим не использовалсяРандомный тест: root@x10–00002:~# show-mac-table -v 20 | wc -l14429
ИтогДля инкрементарных адресов таблица полностью соответствует заявленной, а вот для случайных показатели ухудшаются, хотя и лежат в довольно близком к заявленному диапазоне.
Вывод Если ваша сеть построена таким образом, что домен L2 включает множество устройств, то можно ждать беды. Странным оказалось то, что самый весомый вендор показал худшие результаты. Отсюда мораль — доверяй только собственным глазам и тесту, а не маркетинговым заявлениям с мелким шрифтом в сноске.Я был так удивлен положением вещей, что решил об этом написать. Если есть возможность провести такой же тест, то прошу опубликовать результаты в комментариях.Спасибо за внимание.
