Разработка и исследование эффективности методов построения таблиц фильтрации кадров в мостах и коммутаторах вычислительной техники

• Автор: Маков, Сергей Владимирович
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Шахты
• Количество страниц: 170 с. : ил.

1.1. Вводные замечания.

1.2. Требования к таблицам фильтрации кадров в межсетевых мостах

и коммутаторах

1.3. Методы построения таблиц фильтрации.

1.3.1. Классификация и обозначения

1.3.2. Просматриваемые таблицы

1.3.3. Связные списки.

1.3.4. Упорядоченные таблицы

1.3.5. Таблицы с прямой адресацией

1.3.6. Хешированные таблицы.

1.4. Способы разрешения коллизий в хешированных таблицах.

1.4.1. Способ цепочек или блоков
1.4.2. Способ открытой адресации
1.4.3. Адаптивное хеширование.
1.5. Сводные результаты анализа методов организации таблиц поиска
1.6. Метод хешированных таблиц для организации таблиц
фильтрации
1.7. Выводы но главе.
Глава 2. Методы организации таблиц фильтрации без хранения
адресов
2.1. Вводные замечания.
2.2. Метод организации таблицы фильтрации без хранения адресов
2.2.1. Описание метода
2.2.2. Математическая модель метода без хранения адресов
2.2.3. Определение вероятности переполнения таблицы фильтрации без хранения адресов
2.3. Адаптивный метод организации таблицы фильтрации без хранения адресов
2.3.1. Описание адаптивного метода
2.3.2. Математическая модель адаптивного метода организации таблицы фильтрации без хранения адресов
2.3.3. Определение вероятности переполнения таблицы фильтрации для адаптивного метода без хранения адресов
2.4. Метод организации таблиц фильтрации с параллельным хешированием без хранения адресов
2.4.1. Математическая модель метода с параллельным хешированием
2.5. Выводы по главе.
Глава 3. Сравнение эффективности используемых и разработанных
методов организации таблицы фильтрации.
3.1. Вводные замечания.
3.2. Эффективность метода хешированных таблиц с разрешением коллизий способом блоков.
3.2.1. Постановка задачи
3.2.2. Определение вероятности переполнения хешированной таблицы с разрешением коллизий способом блоков.
3.2.3. Результаты численных расчетов вероятности переполнения хешированной таблицы фильтрации с разрешением коллизий способом блоков
3.3. Эффективность метода организации таблицы фильтрации без хранения адресов
3.3.1. Особенности численного расчета вероятности переполнения таблицы фильтрации без хранения адресов
3.3.2. Статистическое исследование вероятности переполнения таблицы фильтрации без хранения адресов
3.3.3. Результаты вычисления и статистического исследования вероятности переполнения таблицы фильтрации без хранения адресов
3.4. Эффективность адаптивного метода организации таблицы фильтрации без хранения адресов.
3.5. Эффективность метода организации таблицы фильтрации без хранения адресов с параллельным хешированием.
3.6. Выводы по главе.
Глава 4. Особенности практической реализации метода построения
таблиц фильтрации Без хранения адресов в вычислительных устройствах.
4.1. Вводные замечания.
4.2. Требования к мостам в распределенных системах управления
4.3. Синтез схемы моста, реализующей разработанный метод
организации таблицы фильтрации.
4.4. Энергетическая эффективность моста.
4.5. Сравнительные результаты натурных испытаний.
4.6. Выводы по главе.
Заключение.
Список литературы


Во введении обоснована актуальность работы, сформулированы цель и основные задачи исследования, определены научная новизна, практическая значимость и основные положения, выносимые на защиту. Приводятся сведения об апробации и внедрении результатов работы. В первой главе проводится анализ известных методов организации таблиц фильтрации в межсетевых мостах и коммутаторах. Проведенный в главе анализ методов организации таблиц поиска, к классу которых относится таблица фильтрации, показал целесообразность использования хешированныхтаблиц для организации таблиц фильтрации. Детально рассмотрен, наиболее широко используемый в межсетевых мостах и коммутаторах, метод построения таблиц фильтрации использующий хешированные таблицы с разрешением коллизий способом блоков. Сформулированы условия, приводящие к возникновению переполнения таблицы фильтрации моста, организованной описанным методом. На основании анализа недостатков, существующих методов организации таблиц фильтрации, в главе формулируется цель диссертационной работы и задачи, которые необходимо решить для е достижения. Во второй главе представлен разработанный метод организации таблиц фильтрации с использованием хешированных таблиц без хранения адресов, позволяющий упростить алгоритм поиска в таблице фильтрации по сравнению с алгоритмом, используемым в имеющихся1 методах. Показано, что для предложенного метода на любую операцию с таблицей гарантированно будет затрачено только одно обращение к таблице. В главе определено количество памяти, требуемое для хранения таблицы фильтрации, организованной по методу без хранения адресов. Сформулированы условия, приводящие к возникновению переполнения таблицы фильтрации моста, организованной предложенным методом. Исходя, из сформулированных условий, необходимых для появления переполнений таблицы фильтрации организованной по методу без хранения адресов, сформулирована комбинаторная задача, решение которой позволило получить аналитическое выражение для определения вероятности переполнения таблицы фильтрации в зависимости от количества узлов подключенных к портам моста и от разрядности хешфункции. Для увеличения эффективности рассмотренного метода, в соответствии с предложенным критерием в виде вероятности переполнения таблицы фильтрации, в главе предложена его модификация адаптивный метод организации таблиц фильтрации без хранения адресов. Предложены способы адаптивного вычисления хешфункций для указанного метода. Разработанный и рассмотренный в главе метод организации таблиц фильтрации без хранения адресов с параллельным хешированием также позволяет исключить необходимость повторного вычисления хешфункций. Для метода параллельного хеширования предложен способ организации поиска и добавления записей в таблицу фильтрации, определены условия возникновения переполнения таблицы и определен объем памяти, необходимой для размещения таблицы фильтрации. В третьей главе, в соответствии с определенным в первой главе условием, необходимым для появления переполнений таблицы фильтрации, организованной методом хешированных таблиц с разрешением коллизий способом блоков, проведена постановка, комбинаторной задачи. Решение поставленной комбинаторной задачи позволило получить аналитическое выражение для определения численных значений величин вероятности переполнения, таблицы фильтрации в зависимости от количества узлов подключенных к мосту, разрядности хешфункции и количества ячеек в блоке. По аналитическим выражениям проведен численный расчет для рассматриваемых примеров организации таблиц фильтрации и получены графики зависимости вероятности переполнения для различных условий. Получены численные значения вероятности переполнения таблицы для малых значений числа узлов в двух сетях, подключенных к портам моста. Для большого количества узлов, подключенных к мосту, проведено приближенное статистическое исследование вероятности переполнения таблицы фильтрации для метода без хранения адресов. Проведен расчет количества требуемых экспериментов в статистическом, исследовании для обеспечения заданного доверительного интервала.