Организация таблиц фильтрации "без хранения адресов" в межсетевых мостах и коммутаторах методов параллельного хеширования

Размещено на http://www.allbest.ru/

11

организАция таблиц фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах Методом параллельного хеширования

Сергей Владимирович Маков, аспирант, каф. «Радиоэлектронные системы»,

Виктор Игнатьевич Литюк, проф., каф. «Радиоэлектронные системы»,

ФГОУ ВПО «Южно-Российский государственный университет экономики и сервиса», г. Шахты, Ростовская область

Authors present a method of organization of the tables filtering frames in the interconnection bridges and switches of Ethernet, based on the use of parallel computing hash-functions and working without a full comparison of MAC addresses, which allows to reduce time of recording and search in the table, as well as significantly reduce the size of memory required for its storage; provide an assessment of probability of overflow table filtering frames; carry out a comparative analysis of the method with other existing methods.

Keywords: interconnection bridges and switches, hashing, filtering table.

Представлен метод организации таблиц фильтрации кадров в межсетевых мостах и коммутаторах Ethernet, основанный на использовании параллельного вычисления хеш-функций и работающий без полного сравнения MAC-адресов, который позволяет сократить время записи и поиска в таблице, а также значительно уменьшить размер памяти, необходимой для ее хранения; приведена оценка вероятности переполнения таблицы фильтрации кадров; осуществлен сравнительный анализ данного метода с другими существующими методами.

Ключевые слова: межсетевые мосты и коммутаторы, хеширование, таблица фильтрации.

фильтрация кадр межсетевой мост коммутатор

В настоящее время во многих областях техники (в промышленности, в бытовой электронике, на транспорте и т.д.) при передаче данных широко применяется пакетная коммутация. Беспроводные технологии с использованием пакетной коммутации (GSM, WiFi, GPRS, WiMAX и пр.) стали завоевывать все большее признание [1] пользователей вычислительных устройств, имеющих возможность обмениваться информацией. Стремительно растет не только количество устройств, объединяемых в сети, но и объемы передаваемой информации [2].

Основными показателями производительности межсетевых мостов и коммутаторов являются число обработанных кадров в единицу времени и время задержки кадра. Принцип работы мостов и коммутаторов предусматривает фильтрацию кадров, которая состоит в том, что через мост или коммутатор должны передаваться только кадры, предназначенные для узлов сетей, подключенных к другим портам моста. Время принятия решения о необходимости фильтрации или ретрансляции кадра определяется временем задержки передаваемого через мост кадра. Фильтрация или ретрансляция кадров осуществляются на основании информации, накопленной в самообучающихся таблицах - таблицах фильтрации [3]. Решение о необходимости фильтрации или ретрансляции принятого кадра должно быть принято до начала приема следующего кадра. В противном случае будет происходить переполнение буфера моста и, как следствие, потеря кадров.

Другим немаловажным показателем эффективности межсетевых мостов и коммутаторов является вероятность переполнения таблицы фильтрации. Для организации этих таблиц в настоящее время широко применяется метод, основанный на использовании хеширования с разрешением коллизий способом блоков (цепочек) [7, 8, 9]. При использовании этого метода вся таблица разбивается на блоки, адреса которых определяются значением хеш-функции, вычисленным по ключу поиска (обычно из MAC-адреса кадра и поля VLAN ID). Это требует дополнительных затрат вычислительных ресурсов и, следовательно, замедляет процесс принятия решения о необходимости фильтрации.

Переполнение таблицы фильтрации происходит в том случае, когда количества ячеек в блоке не достаточно для хранения записей с одинаковым значением хеш-функций. Однако, несмотря на применение способа блоков для разрешения коллизий, в большинстве случаев его реализаций вероятность переполнения таблицы фильтрации для моста, подключенного к большому числу узлов, остается достаточно высокой при небольших размерах таблицы фильтрации. При переполнении таблицы фильтрации невозможно однозначно идентифицировать принадлежность узла, отправившего кадр, к какой-либо из сетей, подключенных к мосту. При этом кадр передается во все сети, подключенные к портам моста, с целью избежать потерь информации. Такая ситуация приводит к возможной передаче нежелательных кадров через мост.

В работах [4, 5, 6] предлагается способ организации таблицы фильтрации «без хранения адресов», когда в ней не хранятся ключи поиска. Это позволяет гарантировать поиск и добавление записей в таблицу за одно обращение. При такой организации таблицы фильтрации предлагается использовать адаптивное хеширование [5, 10], при котором достигаются малые вероятности переполнения таблицы при большом количестве узлов в сетях, подключенных к портам моста или коммутатора. Недостатком адаптивного хеширования является необходимость повторного заполнения таблицы фильтрации при смене способа вычисления хеш-функции.

Предлагаемый в данной статье метод организации таблицы фильтрации позволяет устранить указанные недостатки и обеспечить низкую вероятность ее переполнения.

Рассмотрим структурную схему 4-портового моста (рис. 1), где кадры с каждого порта моста поступают на внешний порт блоков проверки.

Рис. 1. Структурная схема межсетевого моста

Блок проверки выделяет из кадра адрес источника кадра и адрес его назначения и, в соответствии с информацией, накопленной в таблице фильтрации данного блока проверки, передает или не передает кадр на внутренний порт блока проверки - фильтрует. Из внутренних портов блоков проверки кадры поступают в «эластичное кольцо» - буферную память, хранящую принятые кадры для последующей передачи. Кадры, находящиеся в «эластичном кольце», поступают на внутренние порты блоков проверки и, в случае положительного результата проверки, передаются на внешний порт.

Для предлагаемого метода формат записи в таблице фильтрации следующий: два первых бита - признак принадлежности к внутреннему или внешнему порту блока проверки; два последующих - поле «время жизни» записи. Сама таблица фильтрации состоит из n параллельных хешированных таблиц с различными хеш-функциями для каждой.

Структурная схема блока проверки представлена на рис. 2.

Рис. 2. Структурная схема блока проверки

Из поступившего на блок проверки целостности кадра выделяется адрес источника. По адресу источника вычисляется n значений различных хеш-функций. В n таблицах по адресу, соответствующему значению вычисленной хеш-функции, производится установка бита соответствия тому порту, с которого кадр поступил на блок проверки. В результате происходит «обучение» моста или коммутатора.

Поиск информации в таблице фильтрации происходит следующим образом. По адресу назначения кадра, поступившего на блок проверки, вычисляются n хеш-функций, значения которых являются адресами в соответствующих таблицах. Таким образом, сам поиск в таблице фильтрации осуществляется за одно обращение к таблице. Из всех параллельных таблиц считываются значения битов принадлежности портам блока проверки, и вычисляется суммарный результат по схеме, приведенной на рис. 3. Суммарный бит принадлежности внутреннему порту блока проверки есть результат операции логического «И» от всех битов принадлежности внутреннему порту блока проверки из всех n параллельных таблиц. Аналогично вычисляется суммарный бит принадлежности внешнему порту блока проверки.

Рис. 3. Схема вычисления суммарного значения битов принадлежности к портам блока проверки

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

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

Для оценки вероятности переполнения таблицы фильтрации, организованной описанным методом, было проведено статистическое исследование по методу Монте-Карло. При этом использовалась следующая модель: разрядность хеш-функций - 12 бит; число параллельных таблиц - 8; длина записи - 4 бита (формат описан выше); общий размер таблицы фильтрации - 128 кбит.

Для сравнения эффективности предлагаемого метода с другими методами, используемыми в настоящее время, также были проведены исследования вероятности переполнения таблицы фильтрации с разрешением коллизий методом блоков с размером блока 4 ячейки [8, 9]. Для сравнения были выбраны таблицы размером 256 кбит (разрядность хеш-функции составила 10 бит) и 8 Мбит (разрядность хеш-функции составила 15 бит) [11]. Такие объемы памяти в рассматриваемых примерах используются из-за того, что размер записи в используемых в настоящее время методах обычно составляет 64 бита.

Для 8-мегабитной таблицы фильтрации вероятность переполнения при подключении 1 000 узлов к мосту не превысила , т. е. практически равна нулю.

На рис. 4 приведены зависимости вероятности переполнения таблиц фильтрации для различных методов их организации от суммарного числа узлов в сетях, подключенных к портам моста: кривая 1 соответствует методу хешированных таблиц с разрешением коллизий способом блоков при длине блока в 4 ячейки, длине записи 64 бита и 10-разрядной хеш-функции (общий объем таблицы 256 кбит); кривая 2 - методу параллельного хеширования «без хранения адресов» при использовании двух параллельных таблиц, длине записи 4 бита и 12-битных хеш-функциях (общий объем таблицы 32 кбит); кривая 3 - методу параллельного хеширования «без хранения адресов» при использовании четырех параллельных таблиц, длине записи 4 бита и 12-битных хеш-функциях (общий объем таблицы 64 кбит); кривая 4 соответствует методу параллельного хеширования «без хранения адресов» при использовании восьми параллельных таблиц, длине записи 4 бита и 12-битных хеш-функциях (общий объем таблицы 128 кбит).

Рис. 4. Вероятности переполнения таблиц фильтрации для различных методов

Из приведенных графиков видно, что уже при четырех параллельных таблицах вероятность переполнения таблицы фильтрации для предлагаемого метода значительно меньше, чем для метода с разрешением коллизий способом блоков. При этом размер таблицы для нового метода будет составлять 64 кбит, а для таблицы с разрешением коллизий способом блоков - 256 кбит, что в 4 раза больше.

При увеличении числа параллельных таблиц до 8 (при этом размер таблицы будет 128 кбит) вероятность переполнения становится практически равной нулю, как и для таблицы размером 8 Мбит с разрешением коллизий способом блоков. При этом памяти потребовалось в 64 раза меньше.

Таким образом, предложенный в статье метод организации таблиц фильтрации межсетевых мостов и коммутаторов «без хранения адресов» с применением параллельного хеширования позволяет добиться высокой скорости принятия решения о необходимости фильтрации или ретрансляции кадров в межсетевых мостах и коммутаторах, уменьшения размеров памяти, необходимой для размещения таблицы фильтрации, а также малой вероятности переполнения таблицы фильтрации при большом числе узлов в сетях, объединяемых мостом или коммутатором.

Литература

1.Артюшенко В.М., Корчагин В.А. Анализ беспроводных технологий обмена данными в системах автоматизации жизнеобеспечения производственных и офисных помещений // Электротехнические и информационные комплексы и системы. 2010. Т. 6. №2. С. 10 - 17.

2.Cisco VNI 2009-2014 - Индекс развития визуальных сетевых технологий за 2009-2014 гг. URL: http://www.cisco.com/ en / US/ solutions/ collateral/ ns341/ ns525/ ns537/ ns705/ ns827/ white_paper_c11-481360.pdf (дата обращения 03.03.2011).

3.IEEE Std 802.1D, 1998 Edition, Part 3: Media Access Control (MAC) Bridges.

4.Маков С.В., Шрайфель И.С., Литюк В.И. Метод фильтрации трафика в Ethernet-мостах и условия его применения // Электротехнические и информационные комплексы и системы. 2010. Т. 6. №4. С. 22 - 27.

5.Маков С.В. Быстрая фильтрация кадров в мостах Ethernet с адаптивным вычислением хеш-функции // Современные проблемы радиоэлектроники. Ростов-на-Дону.: РТИСТ ГОУ ВПО «ЮРГУЭС». 2010. С. 80 - 82.

6.Маков С.В. Метод фильтрации кадров для Ethernet мостов и коммутаторов // Мат. 12-й Междунар. конф. «Цифровая обработка сигналов и ее применение». М.: НТОРЭС. 2010. № XII-1. С. 237 - 239.

7.Пат. США №6279097. Method and apparatus for adaptive address lookup table generator for networking application. 21.08.2001.

8.Пат. США №US6697873B1. High speed MAC address search engine. 24.02.2004.

9.Пат. США №US6266705B1. Look up mechanism and associated hash table for a network switch. 24.07.2001.

10.Пат. США №5914938. MAC address table search unit. 22.06.1999.

11.Пат. США № US20070071015. Using CRC-15 as hash function for MAC Bridge filter design. 29.03.2007.

Размещено на Allbest.ru