Разработка и исследование эффективности методов построения таблиц фильтрации кадров в мостах и коммутаторах вычислительной техники
На правах рукописи
МАКОВ СЕРГЕЙ ВЛАДИМИРОВИЧ РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДОВ ПОСТРОЕНИЯ ТАБЛИЦ ФИЛЬТРАЦИИ КАДРОВ В МОСТАХ И КОММУТАТОРАХ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ Специальность: 05.13.05 – «Элементы и устройства вычислительной техники и систем управления»
АВТОРЕФЕРАТ
Диссертации на соискание учёной степени кандидата технических наук
Шахты 2011г.
Работа выполнена на кафедре «Радиоэлектронные системы» Южно-Российского государственного университета экономики и сервиса в г. Шахты.
Научный консультант: доктор технических наук, профессор Литюк Виктор Игнатьевич (ТТИ ЮФУ, г. Таганрог)
Официальные оппоненты: доктор технических наук, профессор Крутчинский Сергей Георгиевич (ТТИ ЮФУ, г. Таганрог) кандидат технических наук Забродин Роман Александрович («РТИСТ» ГОУ ВПО «ЮРГУЭС»,г. Ростов-на-Дону)
Ведущая организация: Федеральное Государственное унитарное предприятие Всероссийский НИИ «Градиент», г. Ростов-на-Дону
Защита состоится 23 декабря 2011 г., в 14:20, в ауд. Д 406 на заседании диссертационного совета Д 212.208.21 при Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» по адресу: 347928 Ростовская обл., г. Таганрог, ГСП-17А, пер.
Некрасовский, 44, ТТИ ЮФУ.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета.
Отзыв на автореферат, заверенный гербовой печатью организации, просим направлять ученому секретарю диссертационного совета Д 212.208.21 по адресу: Ростовская обл., г. Таганрог, ГСП-17А, пер. Некрасовский, 44.
Автореферат разослан «19» ноября 2011 г.
Ученый секретарь диссертационного совета Д 212.208.21 Н.И. Чернов доктор технических наук, доцент
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы.
В настоящее время, большую и растущую долю трафика составляет потоковая информация в виде передачи голоса по IP-сетям (VoIP) и видеоконференции. Всё это накладывает ограничения на время задержки кадров в мостах и коммутаторах, составляющих существенную долю оборудования, используемого в сетях.
Коммутаторы и межсетевые мосты в последнее время уже используются не только как отдельные устройства, но и как составные части сложных вычислительных, телекоммуникационных устройств или систем управления, что предъявляет повышенные требования к снижению их энергопотребления и уменьшению требуемых для их реализации вычислительных ресурсов.
Основным показателем производительности мостов и коммутаторов является количество обработанных кадров в единицу времени и время задержки кадра.
Кадры, поступающие на один порт моста должны передаваться на другой порт только в том случае, если они предназначены для сети подключенной к другому порту. Локальный трафик, т.е. кадры, предназначенные для сети, подключенной к первому порту, должны быть отфильтрованы. Таким образом, время задержки кадров зависит от скорости принятия решения вычислительным устройством о необходимости передачи кадра или его фильтрации. Время на принятие решение особенно сильно влияет на задержку кадров в межсетевых мостах и коммутаторах, работающих по принципу прямой коммутации или «на лету». Это связанно с тем, что передача кадра на второй порт в таких устройствах начинается сразу после приёма адресов источника и назначения, и принятия решения о необходимости передачи.
В межсетевых мостах с различной скоростью передачи данных на разных портах и в коммутаторах, работающих с буферизацией по принципу «store and forward», принимаемый кадр целиком записывается во внутренний буфер и уже из него передается на нужный порт. Это позволяет принимать решение о необходимости передачи кадра параллельно с его приемом. В устройствах, использующих такую организацию передачи данных, также существуют ограничения на время принятия решения. Решение о необходимости фильтрации или ретрансляции принятого кадра должно быть принято до начала приема следующего кадра. В противном случае будет происходить переполнение премного буфера моста и, как следствие, потери кадров.
Проведение исследований направленных на оптимизацию алгоритма фильтрации кадров, может позволить уменьшить время на принятие решения о необходимости фильтрации, уменьшить вероятность переполнения таблицы фильтрации и снизить требования к аппаратным и вычислительным ресурсам, необходимым для реализации алгоритма. Это позволит увеличить производительность и уменьшить стоимость и потребление энергии таких устройств как межсетевые мосты и коммутаторы.
Таким образом, развитие методов и алгоритмов фильтрации трафика в межсетевых мостах и коммутаторах является актуальной как с практической, так и с теоретической точки зрения.
Объектом исследования являются способы реализации алгоритма фильтрации трафика в мостах и коммутаторах, работающих в устройствах вычислительной техники, требующих минимизации временных задержек кадров или передающим данные, преимущественно состоящие из коротких кадров.
Предметом исследований являются способы организации таблиц фильтрации в мостах и коммутаторах в устройствах вычислительной техники.
Целью диссертационной работы является разработка и исследование эффективности методов построения таблиц для фильтрации кадров данных на канальном уровне через мосты и коммутаторы в устройствах вычислительной техники.
Для достижения поставленной цели необходимо решить следующие основные задачи:
1. Провести анализ имеющихся методов организации таблиц фильтрации межсетевых мостов и коммутаторов.
2. Разработать метод организации таблицы фильтрации кадров «без хранения адресов» в межсетевых мостах и коммутаторах.
3. Разработать адаптивный метод организации таблицы фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах.
4. Разработать метод организации таблиц фильтрации с параллельным хешированием «без хранения адресов» в межсетевых мостах и коммутаторах.
5. Провести анализ эффективности имеющихся методов организации таблиц фильтрации кадров в межсетевых мостах и коммутаторах с точки зрения вероятности переполнения таблицы фильтрации.
6. Исследовать эффективность разработанных методов в сравнении с имеющимися методами организации таблиц фильтрации кадров с точки зрения вероятности переполнения таблиц фильтрации, использования памяти и вычислительных затрат, в сравнении с имеющимися методами организации таблиц фильтрации.
7. Разработать структурную схему и на ее основе синтезировать интегральную схему, реализующую разработанный метод организации таблицы фильтрации.
8. Провести сравнительные натурные испытания разработанного устройства и имеющихся аналогов.
Научная новизна.
В рамках диссертационной работы получены следующие новые научные результаты:
1. Разработан метод организации таблиц фильтрации кадров «без хранения адреса» в межсетевых мостах и коммутаторах.
2. Разработан адаптивный метод организации таблицы фильтрации кадров «без хранения адреса» в межсетевых мостах и коммутаторах.
3. Разработан метод организации таблиц фильтрации с параллельным хешированием «без хранения адресов» в межсетевых мостах и коммутаторах.
4. Предложена математическая модель для расчёта эффективности известных методов организации таблиц фильтрации, основанная на определении вероятности переполнения таблицы фильтрации кадров.
5. На основании полученных аналитических выражений проведена оценка эффективности метода организации таблиц фильтрации «без хранения адресов» с точки зрения вероятности переполнения таблицы фильтрации.
6. Получены результаты статистических исследований вероятности переполнения таблиц фильтрации, позволяющие оценить эффективность адаптивного метода организации таблицы фильтрации «без хранения адреса» и метода с параллельным хешированием.
Практическая значимость 1. Не менее чем в 4 раза сокращено время принятия решения о необходимости фильтрации или ретрансляции кадров между портами моста по сравнению с существующими методами при использовании разработанных методов организации таблицы фильтрации «без хранения адресов».
2. Более чем на порядок уменьшен требуемый объём памяти для хранения таблицы фильтрации в случае использования разработанного адаптивного метода организации таблиц фильтрации «без хранения адресов», при сопоставимой вероятности переполнения таблицы фильтрации по сравнению с существующими методами.
3. Почти на два порядка уменьшен требуемый объём памяти для хранения таблицы фильтрации использующей разработанный метод организации таблиц фильтрации «без хранения адреса» с параллельным хешированием, при сопоставимой вероятности переполнения таблицы фильтрации по сравнению с существующими методами.
4. По результатам проведенных исследований изготовлена интегральная схема межсетевого моста на базе программируемой логической интегральной схемы (ПЛИС) для объединения вычислительных устройств с различными канальными форматами передачи данных (IEEE 802.3, HDLC, G.704), что подтверждается актом внедрения и сертификатами соответствия Минсвязи РФ.
5. Предложенные в работе технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяют в несколько раз снизить собственный ток потребления линейного стабилизатора напряжения и значительно уменьшить уровень статического входного тока повторителя напряжения, что приводит к общему снижению потребления энергии в системах управления и повышает статическую точность аналоговых интерфейсов.
6. Мощность, потребляемая разработанным мостом, использующем предложенный метод организации таблицы фильтрации «без хранения адресов» с параллельным хешированием, более чем в 2 раза меньше мощности потребляемой аналогом, использующем известный метод организации таблицы фильтрации.
Методы исследования основываются на использовании теории вероятностей, комбинаторики, математической статистики и машинного эксперимента на персональной электронной вычислительной машине (ПЭВМ). Проверка теоретических расчетов и выводов проводилась в пакете MatLab и с использованием методов статистического анализа.
Достоверность и обоснованность результатов обеспечивается результатами машинного моделирования и натурных испытаний, а также их теоретическим обоснованием. Новизна технических предложений подтверждается экспертизой технических решений в виде патентов на предлагаемые устройства.
Реализация результатов работы.
Диссертационная работа выполнялась в рамках проектов № 2.1.2/ (2.1.2/1127) «Теоретические основы проектирования нелинейных и управляемых СФ-блоков СВЧ систем связи и телекоммуникаций нового поколения» и № 2.1.2/9537 (2.1.2/7267) «Теоретические проблемы обеспечения радиационной стойкости аналоговых интегральных микросхем» аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009 2011годы)» Результаты диссертационной работы внедрены в виде интегральной микросхемы, при разработке следующих устройств, серийно выпускаемых ООО «НПФ Сельсофт», о чем свидетельствует акт внедрения (приложение А), а именно:
мультиплексоры и системы передачи серии МЦ-115Т;
формирователи, концентраторы и коммутаторы потоков Е1 и ОЦК серии МК. Указанные выше устройства прошли сертификацию Минсвязи РФ, что подтверждается сертификатами соответствия (приложение Б).
Апробация работы Основные положения диссертационной работы докладывались и прошли апробацию на международных научно-технических конференциях и опубликованы в сборниках трудов:
12-я Международная конференция «Цифровая обработка сигналов – DSPA 2010», Москва, 2010;
3-я Международная конференция проблемы «Современные радиоэлектроники», Ростов-на-Дону, 2010;
Всероссийская заочная научно-практическая конференция «Информационные системы сервиса», 2011;
1-я Международная заочная научно-техническая конференция «Информационные технологии. Радиоэлектроника. Телекоммуникации (ITRT 2011)», 2011.
Публикации По результатам выполненных исследований опубликовано 9 работ, в том числе 4 статьи в центральных рецензируемых журналах, из перечня рекомендованного ВАК для публикаций основных научных результатов диссертаций, 3 статьи в сборниках трудов и докладов Международных конференций, получено 2 патента РФ на изобретения.
Результаты, выносимые на защиту
.
1. Результаты аналитических исследований, позволяющие определить вероятность переполнения таблицы фильтрации при использовании существующих методов построения таблиц фильтрации.
2. Метод организации таблиц фильтрации «без хранения адресов».
3. Метод организации таблиц фильтрации с адаптивным вычислением хеш функции «без хранения адресов».
4. Метод организации таблиц фильтрации с параллельным хешированием «без хранения адресов».
5. Результаты аналитических и статистических исследований вероятности переполнения таблицы фильтрации, при использовании предложенных методов организации таблиц фильтрации.
6. Результаты сопоставительных исследований предложенных методов для определения структуры нестандартных аппаратных средств межсетевых мостов.
7. Результаты сравнительных натурных испытаний моста, реализованного на основании предложенного метода организации таблицы фильтрации «без хранения адресов» и имеющегося аналога, реализующего известный метод организации таблицы фильтрации.
Структура и объем работы.
Диссертационная работа состоит из введения, пяти глав с выводами, заключения, списка литературы, включающего 70 наименований и 8 приложений.
Основной текст работы изложен на 134 страницах машинописного текста, поясняется 41 рисунком и 6 таблицами.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность работы, сформулированы цель и основные задачи исследования, определены научная новизна, практическая значимость и основные положения, выносимые на защиту. Приводятся сведения об апробации и внедрении результатов работы.
В первой главе проводится анализ известных методов организации таблиц фильтрации в межсетевых мостах и коммутаторах. Эффективность метода организации таблиц фильтрации определяет такие характеристики моста, как:
скорость принятия решения о фильтрации и ретрансляции кадра, вероятность ретрансляции нежелательных кадров, объем памяти, занимаемый таблицей фильтрации, вычислительные ресурсы, требуемые для реализации метода.
Заданные стандартом формат кадров и алгоритм принятия решения о необходимости ретрансляции или фильтрации, а так же алгоритм заполнения таблицы фильтрации, накладывает определенные ограничения на минимальные размеры таблицы и минимальное время поиска значения в таблице фильтрации.
Проведенный в главе анализ методов организации таблиц поиска, к классу ко торых относится таблица фильтрации, показал целесообразность использования хешированных таблиц для организации таблиц фильтрации. Детально рассмотрен, наиболее широко используемый в межсетевых мостах и коммутаторах, метод по строения таблиц фильтрации использующий хешированные таблицы с разреше нием коллизий способом блоков. В главе определено количество памяти, требуемое для хранения хешированной таблицы фильтрации с разрешением коллизий спосо бом блоков. Сформулированы условия, приводящие к возникновению переполне ния таблицы фильтрации моста, организованной описанным методом.
На основании анализа недостатков, существующих методов организации таблиц фильтрации, в главе формулируется цель диссертационной работы и задачи, которые необходимо решить для её достижения.
Во второй главе представлен разработанный метод организации таблиц фильтрации с использованием хешированных таблиц «без хранения адресов», позволяющий упростить алгоритм поиска в таблице фильтрации по сравнению с алгоритмом, используемым в имеющихся методах. Показано, что для предложенного метода на любую операцию с таблицей гарантированно будет затрачено только одно обращение к таблице. В главе определено количество памяти, требуемое для хранения таблицы фильтрации, организованной по методу «без хранения адресов». Сформулированы условия, приводящие к возникновению переполнения таблицы фильтрации моста, организованной предложенным методом. Так как при вычислении хеш-функции для адресов из множеств адресов узлов B и C, можно составить списки получаемых значений хеш-функций, которым L = { i r : B I Ai }, будут соответствовать множества M = { i r : C I Ai }, = L, µ = M, где r–возможное количество значений хеш-функции.
В соответствии с логикой работы метода, условие переполнения таблицы фильтрации «без хранения адресов» определяется следующим выражением:
LIM. (1) Исходя из сформулированных условий, необходимых для появления переполнений таблицы фильтрации организованной по методу «без хранения адресов», сформулирована комбинаторная задача, решение которой позволило получить аналитическое выражение для определения вероятности переполнения таблицы фильтрации в зависимости от количества узлов подключенных к портам моста и от разрядности хеш-функции.
+µ (r ( + µ ) + ) m n = PП.Т. = 1 m+n (rl (m + n) + ) =1 µ = = m n (( i + 1)l m + ) (( µ j + 1)l n + ) µ =1 = (1) i + j, (2) (i 1)!( i + 1)! ( j 1)!(µ j + 1)!
i =1 j = где r l – количество возможных адресов, r – количество возможных значений хеш функции, m – количество узлов в сети, подключенной к внешнему порту моста, n – количество узлов в сети, подключенной к внутреннему порту моста.
Для увеличения эффективности рассмотренного метода, с точки зрения вероятности переполнения таблицы фильтрации, в главе предложен новый метод – адаптивный метод организации таблиц фильтрации «без хранения адресов».
Структурная схема блока проверки для данного метода представлена на рисунке 1.
Для данного метода также определено количество необходимой памяти для размещения таблицы фильтрации и сформулированы условия возникновения неустранимого переполнения таблицы фильтрации кадров.
При смене способа вычисления хеш-функции, составляются новые списки значений хеш-функций, которым соответствуют множества L j = { i r : B I Ai }, M j = { i r : C I Ai }, j = 1,2,..., t, где t – количество 1 вариантов вычисления хеш-функции, r – возможное количество значений хеш функции.
В соответствии с логикой работы адаптивного метода организации таблицы фильтрации «без хранения адресов», условие неустранимого переполнения таблицы фильтрации определяется следующим выражением:
{1 j t : L j I M j } = t. (3) Предложены способы адаптивного вычисления хеш-функций для указанного метода.
Рисунок 1 – Структурная схема блока проверки для адаптивного метода «без хранения адресов» Разработанный и рассмотренный в главе метод организации таблиц фильтрации «без хранения адресов» с параллельным хешированием, структурная схема блока проверки которого приведена на рисунке 2, также позволяет исключить необходимость повторного вычисления хеш-функций. Для метода параллельного хеширования предложен способ организации поиска и добавления записей в таблицу фильтрации, определены условия возникновения переполнения таблицы. При вычислении каждой хеш-функции для адресов из множеств адресов узлов B и C, можно составить списки получаемых значений хеш-функций, которым L j = { i r : B I Ai }, будут соответствовать множества M j = { i r : C I Ai }, j = 1,2,..., t, где t – количество параллельных хешированных таблиц, r – возможное количество значений хеш-функции.
С учетом использования «суммарных» бит принадлежности к порту (схема их вычисления представлена на рисунке 3) для принятия решения о необходимости ретрансляции кадра через мост и в соответствии с логикой работы рассматриваемого метода, условие переполнения таблицы фильтрации определяется следующим выражением:
t ILj I M j. (4) j = Рисунок 2 – Структурная схема блока проверки для метода «без хранения адресов» с параллельным хешированием Рисунок 3 – Вычисление «суммарных» бит принадлежности к портам блока проверки В третьей главе, в соответствии с определенным в первой главе условием, необходимым для появления переполнений таблицы фильтрации, организованной методом хешированных таблиц с разрешением коллизий способом блоков, проведена постановка комбинаторной задачи. Решение поставленной комбинаторной задачи позволило получить аналитическое выражение (4) для определения вероятности переполнения таблицы фильтрации в зависимости от количества узлов подключенных к мосту, разрядности хеш-функции и количества ячеек в блоке.
m,,l PП.Т. = r, (5) m C rl причем значения вида il определяются рекуррентным выражением (6) jp m k Crs (Clk ) msksl, k 1, s mk = (6) rl r, s = max( 0;
m r ( k 1)) где r l – количество возможных адресов, r – количество возможных значений хеш функции, m – количество узлов во всех сетях, подключенных к мосту или коммутатору, k – количество ячеек в таблице фильтрации, выделенных под блок.
По аналитическим выражениям проведен численный расчет для рассматривае мых примеров организации таблиц фильтрации и получены графики зависимости вероятности переполнения для различных условий, представленные на рисунке 4.
При расчете rl = 2 48, что соответствует количеству возможных адресов в сети Ethernet, а r = 212 для k = 1 ;
r = 211 для k = 2 и r = 210 для k = 4.
Получены численные значения вероятности переполнения таблицы для малых значений числа узлов в двух сетях, подключенных к портам моста. Для большого количества узлов, подключенных к мосту, проведено приближенное ста тистическое иссле дование вероятности переполнения табли цы фильтрации для метода «без хранения адресов». Проведен расчет количества требуемых экспери ментов в статисти ческом исследовании Рисунок 4 – Вероятность переполнения хешированной для обеспечения таблицы с разрешением коллизий способом блоков заданного довери для таблицы размером 256 кБит.
тельного интервала.
Анализ результатов расчетов и статистического исследования вероятности пе реполнения таблицы фильтрации, приведенных на рисунке 5, показал, что при не которых определенных условиях использование метода организации таблиц фильт рации «без хранения адресов» дает меньшую вероятность переполнения таблицы фильтрации по сравнению с используемым методом при равном количестве памяти, выделяемом для таблицы.
На рисунке 5: линия 1 – вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока k = 1 ;
линия 2 – вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока k = 2 ;
линия 3 – вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока k = 4 ;
линия 4 – оценка вероятности переполнения таблицы фильтрации «без хранения адресов»;
линия 5 – оценка вероятности переполнения таблицы фильтрации «без хранения адресов», при условии, что в одной из сетей подключенных к мосту только восемь узлов;
линия 6 – оценка вероятности переполнения таблицы фильтрации «без хранения адресов», при условии, что в одной из сетей подключенных к мосту только два узла.
Проведены статистические исследования вероятности перепол нения таблицы фильтрации органи зованной в соответствии с адаптив ным методом «без хранения адресов» при изменяющемся суммарном коли честве узлов в сетях, подключенных к портам моста и изменяющемся количестве перебираемых хеш функций и их разрядности.
Результаты статистического исследования, представленные на Рисунок 5 – Вероятности переполнения рисунке 6, позволили установить, что таблицы фильтрации при определенном количестве пере для метода «без хранения адресов» бираемых вариантов расчета хеш в зависимости от суммарного количества функции, предложенный адаптивный узлов подключенных к портам моста метод организации таблицы фильтра для таблицы размером 256 кБит ции «без хранения адресов» более эффективен с точки зрения вероятности переполнения таблицы фильтрации, по сравнению с методом хешированных таблиц с разрешением коллизий способом блоков, при равных размерах памяти, используемой таблицей.
Пунктирными линиями 4, 5, 6 на графике показаны оценки зависимости вероят ности от суммарного коли чества узлов s при различном количестве перебираемых вариантов вычисления хеш функций t=2, t=8 и t= соответственно. Для сравне ния на графике также изображены линии 1, 2 и 3, соответствующие вероят Рисунок 6 – Вероятность переполнения таблицы ности переполнения таблицы фильтрации, для адаптивного метода «без хранения фильтрации для метода с адресов» в зависимости от суммарного количества разрешением коллизий при узлов для таблицы размером 256 кБит длине блока k = 1, k = 2 и k = 4 соответственно.
Показано, что при заданной максимальной вероятности переполнения таблицы фильтрации для определенного суммарного числа узлов в сетях, использование адаптивного метода организации таблицы «без хранения адресов» позволяет использовать как минимум в 36 раз меньше памяти, чем для метода с разрешением коллизий способом блоков.
Проведено статистическое исследование вероятности переполнения таблицы фильтрации для метода параллельного хеширования «без хранения адресов».
Очевидно, что в одном и то же объеме памяти можно разместить различное число параллельных таблиц. Так, используя 128 кБит памяти можно организовать одну таблицу размером 128 кБит или две таблицы размером 64 кБит, или 4 таблицы размером 32 кБита каждая, и так далее до 32768 таблиц по одной 4-х битной ячейке в каждой. На рисунке 7 приведены зависимости вероятности переполнения таблицы фильтрации от количества параллельных хешированных таблиц t при суммарном количестве узлов в сетях s=1000 для общего объема памяти отводимого под таблицы M=32, M=64 и M=128 кБит (линии 1, 2 и 3 соответственно).
Анализ результатов ста тистических исследований, приведенных на рисунке 7, показывает, что при фикси рованном объеме памяти, выделяемом для организации параллельных хешированных таблиц, существует такое число параллельных таблиц, при котором вероятность Рисунок 7 – Зависимость вероятности переполнения минимальна.
переполнения таблицы фильтрации На рисунке 8 приведены от количества параллельных таблиц результаты проведенных статистических исследований вероятности переполнения таблиц фильтрации с параллельным хешированием, занимающих 32 кБита (линия 3) в зависимости от суммарного количества узлов в s объединяемых сетях. Для сравнения, на этом же графике изображена зависи мость вероятности перепол нения таблицы фильтрации размером 256 кБит, при использовании метода разре шения коллизий с длинной Рисунок 8 – Вероятность переполнения таблицы блока k=4 (линия 1). Также фильтрации для метода с параллельным на графике представлена хешированием «без хранения адресов» зависимость вероятности переполнения таблицы фильтрации размером 256 кБит для адаптивного метода «без хранения адресов» с количеством перебираемых вариантов вычисления хеш функций t=32 (линия 2).
Результат статистического исследования вероятности переполнения таблицы фильтрации с параллельным хешированием, при использовании 24 параллельных 4 кБитных таблиц (96 кБит), показал, что вероятность переполнения таблицы фильтрации для s=1000 составила 2 10 6. Это значение меньше, чем вероятность переполнения таблицы размером 9 Мбит, организованной известным методом с длинной блока k=4 и 15-битной хеш-функцией, которая составила 7 10 6. При этом размер памяти, требуемый для организации таблицы фильтрации рассматриваемым способом, в 96 раз меньше.
В четвертой главе обоснованны повышенные требования к уровню потребления энергии мостов в территориально разнесенных системах управления.
Синтезирована интегральная микросхема на базе программируемой логической интегральной схемы (ПЛИС), выполняющая функции межсетевого моста, реализующая метод организации таблицы фильтрации «без хранения адресов» с параллельным хешированием. Приведены описания интерфейсов и функций разработанной цифровой интегральной схемы.
С целью обеспечения повышенной энергетической эффективности, предложены технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяющие снизить потребление энергии распределенной системы управления.
Схемы предложенных технических решений приведены на рисунке 9 и на рисунке 10. Данные технические решения позволяют значительно уменьшить уровень статического входного тока повторителя напряжения, что приводит к общему снижению потребления энергии в системах управления и повышает статическую точность аналоговых интерфейсов.
Рисунок 10 – Повторитель Рисунок 9 – Стабилизатор напряжения напряжения Описаны серийно выпускаемые устройства, созданные на базе разработанной интегральной схемы, о чем свидетельствует акт внедрения (приложение А).
Созданные устройства применяются для объединения сетей с различными канальными форматами передачи данных (IEEE 802.3, HDLC, G.704, RS-232, RS 485). На рисунке 11 представлена фотография модуля моста, реализованного с применением синтезированной микросхемы.
Рисунок 11 – Модуль моста Ethernet – HDLC Приведены результаты натурных испытаний, подтверждающие снижение потребляемой энергии мостом в 2,2 раза по сравнению с существующим аналогом.
В заключении сформулированы основные научные и практические результаты работы, полученные в рамках проведенных исследований.
В приложениях приведены копии акта внедрения разработанного метода и сертификатов соответствия на устройства, разработанные с применением предлагаемого адаптивного метода организации таблицы фильтрации «без хранения адресов». Также приведены тексты программ, используемых для осуществления численных расчетов по аналитическим выражениям, полученным в работе, и проведения статистического исследования вероятности переполнения таблиц фильтрации. Приведена таблица распределения адресов по узлам сети.
Приведено описание приемника Ethernet на языке AHDL. Приведены фотографии разработанных устройств.
Основные положения диссертации опубликованы в следующих работах:
Публикации в изданиях, рекомендованных ВАК 1. Маков С.В., Шрайфель И.С., Литюк В.И. Метод фильтрации трафика в Ethernet мостах и условия его применения // Электротехнические и информационные комплексы и системы. научно-технический и теоретический журнал. – М.: Изд-во РГУТиС - №4, т. 6.– 2010. – С. 22- 2. Попов А.Э., Манжула В.Г., Маков С.В. Формализация процедур синтеза принципиальных электрических схем // Изв. вузов. Сев.-Кавк. регион. Техн. науки.
– Ростов, 1999.— Вып. 3.— С. 75 – 3. Маков С.В., Шрайфель И.С. Оценка эффективности фильтрации трафика в межсетевых мостах и коммутаторах [Электронный ресурс] // Сервис в России и за рубежом. – Вып.5(24). – 2011г. URL: http:// www.mgus.ru/ files/ electronic_journal/ number24/ 5.doc 4. Маков С.В., Литюк В.И. Организация фильтрации «Без хранения адресов» в межсетевых мостах и коммутаторах методом параллельного хеширования [Электронный ресурс] // Сервис в России и за рубежом. – Вып.5(24). – 2011г.
URL: http:// www.mgus.ru/ files/ electronic_journal/ number24/ 6.doc Статьи и материалы конференций 5. Маков С.В. Метод фильтрации кадров для Ethernet мостов и коммутаторов / С.В.
Маков // Цифровая обработка сигналов и её применение: Материалы 12-й международной конференции. – М.: НТОРЭС – 2010. – № XII-1. – С. 237-239.
6. Маков С.В. Быстрая фильтрация кадров в мостах Ethernet с адаптивным вычислением хеш-функции // Современные проблемы радиоэлектроники: Сборник научных трудов. – Ростов-на-Дону.: РТИСТ ГОУ ВПО «ЮРГУЭС». – 2010. – С. 80 7. Маков С.В. Адаптивный метод организации таблиц фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах // Информационные технологии.
Радиоэлектроника. Телекоммуникации : сб. статей I международной заочной научно-технической конференции / Поволжский гос. ун-т сервиса. – Тольятти: Изд во ПВГУС, 2011. – С.225- Патенты 8. Патент РФ 2119241, МКИ 6H03F 3/21. Повторитель напряжения / А.Э. Попов, С.В. Маков. /РФ/. - №97112773/09;
заявл. 29.07.97.;
опубл. 20.09.98 Бюл.№26. -3с.:
ил.
9. Патент РФ 2211477, МКИ G05F 1/56. Стабилизатор постоянного напряжения / С.В. Маков., А.Э. Попов /РФ/. - №2002100748/09;
заявл. 08.01.2002.;
опубл.
27.08.2003 Бюл.№25. -5с.:ил.
Личный вклад в опубликованные в соавторстве работы.
[1, 4] – разработка и аналитическое описание метода;
[2] – разработка подходов к формализации процедур синтеза принципиальных схем;
[3] – постановка задачи и проведение расчетов;
[8,9] – разработка, описание и расчет схем.
Подписано в печать 15.11.2011г. Формат 60х84/16.
Бумага офсетная. Ризография. Усл.п.л. 1,0.
Тираж 100 экз. Зак. 161.
Отпечатано в типографии:
ИП Бурыхин Б.М., Ростовская область, г.Шахты, ул. Шавченко, 143.