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

На правах рукописи

005004020

МАКОВ СЕРГЕЙ ВЛАДИМИРОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДОВ ПОСТРОЕНИЯ ТАБЛИЦ ФИЛЬТРАЦИИ КАДРОВ В МОСТАХ И КОММУТАТОРАХ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Специальность: 05.13.05 - «Элементы и устройства вычислительной техники

и систем управления»

АВТОРЕФЕРАТ

Диссертации на соискание учёной степени кандидата технических наук

- 8 ДЕК 2011

Шахты 2011г.

005004020

Работа выполнена на кафедре «Радиоэлектронные системы» Южно-Российского государственного университета экономики и сервиса в г. Шахты.

Научный руководитель:

доктор технических наук, профессор Литюк Виктор Игнатьевич (ТТИ ЮФУ, г. Таганрог)

Официальные оппоненты: доктор технических наук, профессор

Крутчинский Сергей Георгиевич (ТТИ ЮФУ, г. Таганрог)

кандидат технических наук

Забродин Роман Александрович

(«РТИСТ» ГОУ ВПО «ЮРГУЭС»,г. Ростов-на-Дону)

Ведущая организация:

Федеральное Государственное унитарное предприятие Всероссийский НИИ «Градиент», г. Ростов-на-Дону

Защита состоится 23 декабря 2011г., в 14:20, в ауд. Д 406 на заседании диссертационного совета Д 212.208.21 при Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» по адресу: 347928 Ростовская обл., г. Таганрог, ГСП-17А, пер. Некрасовский, 44, ТТИ ЮФУ.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета.

Отзыв на автореферат, заверенный гербовой печатью организации, просим направлять ученому секретарю диссертационного совета Д 212.208.21 по адресу: 347928 Ростовская обл., г. Таганрог, ГСП-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. По результатам проведенных исследований изготовлена интегральная схема межсетевого моста на базе программируемой логической интегральной схемы (ПЛИС) для объединения вычислительных устройств с различными канальными форматами передачи данных (ШЕЕ 802.3, HDLC, G.704), что подтверждается актом внедрения и сертификатами соответствия Минсвязи РФ.

5. Предложенные в работе технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяют в несколько раз снизить собственный ток потребления линейного стабилизатора напряжения и значительно уменьшить уровень статического входного тока повторителя напряжения, что приводит к общему снижению потребления энергии в системах управления и повышает статическую точность аналоговых интерфейсов.

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

Методы исследования основываются на использовании теории вероятностей, комбинаторики, математической статистики и машинного эксперимента на персональной электронной вычислительной машине (ПЭВМ). Проверка теоретических расчетов и выводов проводилась в пакете MatLab и с использованием методов статистического анализа.

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

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

Диссертационная работа выполнялась в рамках проектов №2.1.2/9532 (2.1.2/1127) «Теоретические основы проектирования нелинейных и управляемых СФ-блоков СВЧ систем связи и телекоммуникаций нового поколения» и №2.1.2/9537 (2.1.2/7267) «Теоретические проблемы обеспечения радиационной стойкости аналоговых интегральных микросхем» аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (20092011 годы)»

Результаты диссертационной работы внедрены в виде интегральной микросхемы, при разработке следующих устройств, серийно выпускаемых ООО «НПФ Сельсофт», о чем свидетельствует акт внедрения (приложение А), а именно: мультиплексоры и системы передачи серии МЦ-115Т; формирователи, концентраторы и коммутаторы потоков Е1 и ОЦК серии МК. Указанные выше устройства прошли сертификацию Минсвязи РФ, что подтверждается сертификатами соответствия (приложение Б).

Апробация работы

Основные положения диссертационной работы докладывались и прошли апробацию на международных научно-технических конференциях и опубликованы в сборниках трудов:

- 12-я Международная конференция «Цифровая обработка сигналов - ОБРА-2010», Москва, 2010;

- 3-я Международная конференция «Современные проблемы радиоэлектроники», Ростов-на-Дону, 2010;

- Всероссийская заочная научно-практическая конференция «Информационные системы сервиса», 2011;

- 1-я Международная заочная научно-техническая конференция «Информационные технологии. Радиоэлектроника. Телекоммуникации (1П1Т-2011)», 2011.

Публикации

По результатам выполненных исследований опубликовано 9 работ, в том числе 4 статьи в центральных рецензируемых журналах, из перечня рекомендованного ВАК для публикаций основных научных результатов диссертаций, 3 статьи в сборниках трудов и докладов Международных конференций, получено 2 патента РФ на изобретения.

Результаты, выносимые на защиту.

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

2. Метод организации таблиц фильтрации «без хранения адресов».

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

4. Метод организации таблиц фильтрации с параллельным хешированием «без хранения адресов».'

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

6. Результаты сопоставительных исследований предложенных методов для определения структуры нестандартных аппаратных средств межсетевых мостов.

7. Результаты сравнительных натурных испытаний моста, реализованного на основании предложенного метода организации таблицы фильтрации «без хранения адресов» и имеющегося аналога, реализующего известный метод организации таблицы фильтрации.

Структура и объем работы.

Диссертационная работа состоит из введения, пяти глав с выводами, заключения, списка литературы, включающего 70 наименований и 8 приложений. Основной текст работы изложен на 134 страницах машинописного текста, поясняется 41 рисунком и 6 таблицами.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, сформулированы цель и основные задачи исследования, определены научная новизна, практическая значимость и основные положения, выносимые на защиту. Приводятся сведения об апробации и внедрении результатов работы.

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

- скорость принятия решения о фильтрации и ретрансляции кадра,

- вероятность ретрансляции нежелательных кадров,

- объем памяти, занимаемый таблицей фильтрации,

- вычислительные ресурсы, требуемые для реализации метода.

Заданные стандартом формат кадров и алгоритм принятия решения о необходимости ретрансляции или фильтрации, а так же алгоритм заполнения таблицы фильтрации, накладывает определенные ограничения на минимальные размеры таблицы и минимальное^время поиска значения в таблице фильтрации.

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

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

Во второй главе представлен разработанный метод организации таблиц фильтрации с использованием хешированных таблиц «без хранения адресов»,

позволяющий упростить алгоритм поиска в таблице фильтрации по сравнению с алгоритмом, используемым в имеющихся методах. Показано, что для предложенного метода на любую операцию с таблицей гарантированно будет затрачено только одно обращение к таблице. В главе определено количество памяти, требуемое для хранения таблицы фильтрации, организованной по методу «без хранения адресов». Сформулированы условия, приводящие к возникновению переполнения таблицы фильтрации моста, организованной предложенным методом. Так как при вычислении хеш-функции для адресов из множеств адресов узлов В и С, можно составить списки получаемых значений хеш-функций, которым будут соответствовать множества L = {\<i<r:Bf\Aj^ 0},

М = {l < i < г: С П Aj Ф 0}, Л = |Z,|, fi = \М\, где r-возможное количество значений хеш-функции.

В соответствии с логикой работы метода, условие переполнения таблицы фильтрации «без хранения адресов» определяется следующим выражением:

LDM*0, (1)

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

Л+д

Y[(r-(Ä+fi)+p)

т п

Рп.Т. — 1 2 m+n Х

л=1А=1 Y\(rl-(m + ri) + a)

а=\

m п

хß'\i-m-i+D. 'ViM/w+D ' (2)

где г-1 - количество возможных адресов, г - количество возможных значений хеш-функции, m - количество узлов в сети, подключенной к внешнему порту моста, п -количество узлов в сети, подключенной к внутреннему порту моста.

Для увеличения эффективности рассмотренного метода, с точки зрения вероятности переполнения таблицы фильтрации, в главе предложен новый метод -адаптивный метод организации таблиц фильтрации «без хранения адресов». Структурная схема блока проверки для данного метода представлена на рисунке 1.

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

При смене способа вычисления хеш-функции, составляются новые списки значений хеш-функций, которым соответствуют множества Lj ={\<1<г-.ВГ\Л,ф 0}, Mj - {l < i < г: С П А,-Ф 0}, j = 1,2,...,/, где t - количество вариантов вычисления хеш-функции, г - возможное количество значений хеш-

функции.

В соответствии с логикой работы адаптивного метода организации таблицы фильтрации «без хранения адресов», условие неустранимого переполнения таблицы фильтрации определяется следующим выражением:

\{\<]<1-.Ь1Г[М1*<2\ = 1. (3)

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

1

Рисунок 1 - Структурная схема блока проверки для адаптивного метода «без хранения адресов»

Разработанный и рассмотренный в главе метод организации таблиц фильтрации «без хранения адресов» с параллельным хешированием, структурная схема блока проверки которого приведена на рисунке 2, также позволяет исключить необходимость повторного вычисления хеш-функций. Для метода параллельного хеширования предложен способ организации поиска и добавления записей в таблицу фильтрации, определены условия возникновения переполнения таблицы. При вычислении каждой хеш-функции для адресов из множеств адресов узлов В и С, можно составить списки получаемых значений хеш-функций, которым будут соответствовать множества Ь]• = {1 < г < г: В П ^ ф 0},

= {1 <г<д-:СГМ,'у = 1,2,...,/, где ? - количество параллельных хешированных таблиц, г - возможное количество значений хеш-функции.

С учетом использования «суммарных» бит принадлежности к порту (схема их вычисления представлена на рисунке 3) для принятия решения о необходимости

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

f)LJ(]MJФ0. (4)

/=1

1

Рисунок 2 - Структурная схема блока проверки для метода «без хранения адресов»

с параллельным хешированием

Внутр. #1 & Внеш. #1 &

Внутр. #2^ Внутр. Внеш'#2, Внеш.

Внутр. Ш Внеш. #1

Рисунок 3 - Вычисление «суммарных» бит принадлежности к портам блока проверки

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

X"'}

рп.т= (5)

г/

причем значения вида A/f определяются рекуррентным выражением (6)

[т]

# = (6)

i=max(0;m-r(i-l))

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

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

до

При расчете rl = 2 , что соответствует количеству возможных адресов в сети _

Ethernet, а г = 212 для к = 1; г = 2й для к = 2 и г = 210 для к - 4.

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

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

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

На рисунке 5: линия 1 - вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока к = 1; линия 2 -вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока к = 2; линия 3 - вероятность переполнения таблицы фильтрации с разрешением коллизий способом блоков с длиной блока к = 4; линия 4 - оценка вероятности переполнения таблицы фильтрации «без хранения адресов»; линия 5 - оценка вероятности переполнения таблицы фильтрации «без

Рисунок 4 - Вероятность переполнения хешированной таблицы с разрешением коллизий способом блоков для таблицы размером 256 кБит.

хранения адресов», при условии, что в одной из сетей подключенных к мосту только восемь узлов; линия 6 - оценка вероятности переполнения таблицы фильтрации «без хранения адресов», при условии, что в одной из сетей

подключенных к мосту только два узла.

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

перебираемых хеш-функций и их разрядности.

Результаты статистического исследования, представленные на рисунке 6, позволили установить, что при определенном количестве перебираемых вариантов расчета хеш-функции, предложенный

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

Пунктирными линиями 4, 5, 6 на графике показаны оценки зависимости вероятности от суммарного количества узлов 5 при различном количестве перебираемых вариантов вычисления хеш-функций /=2, ¿=8 и <=32 соответственно. Для сравнения на графике также изображены линии 1, 2 и 3, соответствующие вероятности переполнения таблицы фильтрации для метода с разрешением коллизий при

Рисунок 5 - Вероятности переполнения таблицы фильтрации для метода «без хранения адресов» в зависимости от суммарного количества узлов подключенных к портам моста для таблицы размером 256 кБит

адресов» более эффективен фильтрации, по сравнению

; Л .........••

/ / / 7 / А ......./........................

1 ' ....................... У / | / /' у / /

4/ X А / /5 /6

............. / ух 1 ......„--"''" ......- / и и'

Рисунок 6 - Вероятность переполнения таблицы фильтрации, для адаптивного метода «без хранения адресов» в зависимости от суммарного количества узлов для таблицы размером 256 кБит

длине блока к = 1, к = 2 и к- 4 соответственно.

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

Проведено статистическое исследование вероятности переполнения таблицы фильтрации для метода параллельного хеширования «без хранения адресов». Очевидно, что в одном и то же объеме памяти можно разместить различное число параллельных таблиц. Так, используя 128 кБит памяти можно организовать одну таблицу размером 128 кБит или две таблицы размером 64 кБит, или 4 таблицы размером 32 кБита каждая, и так далее до 32768 таблиц по одной 4-х битной ячейке в каждой. На рисунке 7 приведены зависимости вероятности переполнения таблицы фильтрации от количества параллельных хешированных таблиц / при суммарном ' количестве узлов в сетях 5=1000 для общего объема памяти отводимого под таблицы М~32, М=64 и А/=128 кБит (линии 1, 2 и 3 соответственно).

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

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

параллельным хешированием, занимающих 32 кБита (линия 3) в зависимости от суммарного количества узлов 5 в объединяемых сетях. Для сравнения, на этом же графике изображена зависимость вероятности переполнения таблицы фильтрации размером 256 кБит, при использовании метода разрешения коллизий с длинной блока /с=4 (линия 1). Также на графике представлена зависимость вероятности

256 /

Рисунок 7 - Зависимость вероятности переполнения таблицы фильтрации от количества параллельных таблиц

1 /

у; /

! | | /

/ / / /3

- , .. 1 „-:---1

Рисунок 8 - Вероятность переполнения таблицы фильтрации для метода с параллельным хешированием «без хранения адресов»

переполнения таблицы фильтрации размером 256 кБит для адаптивного метода «без хранения адресов» с количеством перебираемых вариантов вычисления хеш-функций Г=32 (линия 2).

Результат статистического исследования вероятности переполнения таблицы фильтрации с параллельным хешированием, при использовании 24 параллельных 4 кБитных таблиц (96 кБит), показал, что вероятность переполнения таблицы фильтрации для л=1000 составила 2'КГ6. Это значение меньше, чем вероятность переполнения таблицы размером 9 Мбит, организованной известным методом с длинной блока к= 4 и 15-битной хеш-функцией, которая составила 7-10~б. При этом размер памяти, требуемый для организации таблицы фильтрации рассматриваемым способом, в 96 раз меньше.

В четвертой главе обоснованны повышенные требования к уровню потребления энергии мостов в территориально разнесенных системах управления.

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

С целью обеспечения повышенной энергетической эффективности, предложены технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяющие снизить потребление энергии распределенной системы управления. Схемы предложенных технических решений приведены на рисунке 9 и на рисунке 10. Данные технические решения позволяют значительно уменьшить уровень статического входного тока повторителя напряжения, что приводит к общему снижению потребления энергии в системах управления и повышает статическую точность аналоговых интерфейсов.

Общ.

Вых.

Рисунок 9 - Стабилизатор напряжения

Вход.

Вх о

Вых

Рисунок 10 - Повторитель напряжения

Описаны серийно выпускаемые устройства, созданные на базе разработанной интегральной схемы, о чем свидетельствует акт внедрения (приложение А).

Созданные устройства применяются для объединения сетей с различными канальными форматами передачи данных (ШЕЕ 802.3, HDLC, G.704, RS-232, RS-485). На рисунке 11 представлена фотография модуля моста, реализованного с применением синтезированной микросхемы.

Драйвер Ethernet

Рисунок 11 - Модуль моста Ethernet - HDLC

Приведены результаты натурных испытаний, подтверждающие снижение потребляемой энергии мостом в 2,2 раза по сравнению с существующим аналогом.

В заключении сформулированы основные научные и практические результаты работы, полученные в рамках проведенных исследований.

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

Основные положения диссертации опубликованы в следующих работах: Публикации в изданиях, рекомендованных ВАК

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

2. Попов А.Э., Манжула В.Г., Маков C.B. Формализация процедур синтеза принципиальных электрических схем // Изв. вузов. Сев.-Кавк. регион. Техн. науки. - Ростов, 1999.— Вып. 3 — С. 75 - 78

3. Маков C.B., Шрайфель И.С. Оценка эффективности фильтрации трафика в

межсетевых мостах и коммутаторах [Электронный ресурс] // Сервис в России и за рубежом. - Вып.5(24). - 2011г. URL: http:// www.mgus.ru/ files/ electronicjournal/ number24/ 5.doc

4. Маков C.B., Липок В.И. Организация фильтрации «Без хранения адресов» в межсетевых мостах и коммутаторах методом параллельного хеширования [Электронный ресурс] // Сервис в России и за рубежом. - Вып.5(24). - 2011г. URL: http:// www.mgus.ru/ files/ electronicjournal/ number24/ 6.doc

Статьи и материалы конференций

5. Маков C.B. Метод фильтрации кадров для Ethernet мостов и коммутаторов / C.B. Маков // Цифровая обработка сигналов и её применение: Материалы 12-й международной конференции. - М.: НТОРЭС - 2010. - № ХП-1. - С. 237-239.

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

7. Маков C.B. Адаптивный метод организации таблиц фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах // Информационные технологии. Радиоэлектроника. Телекоммуникации : сб. статей I международной заочной научно-технической конференции / Поволжский гос. ун-т сервиса. - Тольятти: Изд-во ПВГУС, 2011. - С.225-232

Патенты

8. Патент РФ 2119241, МКИ 6H03F 3/21. Повторитель напряжения / А.Э. Попов, C.B. Маков. /РФ/. - №97112773/09; заявл. 29.07.97.; опубл. 20.09.98 Бюл.№26. -Зс.: ил.

9. Патент РФ 2211477, МКИ G05F 1/56. Стабилизатор постоянного напряжения / C.B. Маков., А.Э. Попов /РФ/. - №2002100748/09; заявл. 08.01.2002.; опубл. 27.08.2003 Бюл.№25. -5с.:ил.

Личный вклад в опубликованные в соавторстве работы.

[1, 4] - разработка и аналитическое описание метода; [2] - разработка подходов к формализации процедур синтеза принципиальных схем; [3] -постановка задачи и проведение расчетов; [8,9] - разработка, описание и расчет схем.

Подписано в печать 15.11.2011г. Формат 60x84/16. Бумага офсетная. Ризография. Усл.п.л.1,0. Тираж 100 экз. Зак.161.

Отпечатано в типографии: ИП Бурыхин Б.М., Ростовская область, г.Шахты, ул.Шевченко, 143.

Введение.

Глава 1. Анализ методов огранизации таблиц для,фильтрации кадров в мостах и коммутаторах.

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. Выводы по главе.

Актуальность работы. Начиная с 60-х годов 20-го столетия, ведутся работы по организации обмена информацией между вычислительными устройствами. Эти работы привели к созданию в 1975г. сети Ethernet, способной объединять множество вычислительных устройств. Основные идеи изложены в работе Роберта Меткалфа и Дэвида Боггса [1]. В этой работе были предложены основные принципы пакетной коммутации и адресации пакетов данных, которые практически без изменений используются в настоящее время. В> заголовке каждого пакета располагаются поля с адресами источника и назначения, по которым происходит однозначная коммутация пакетов между узлами в сети.

В феврале 1980г. «Институт инженеров по электротехнике и электронике» (Institute of Electrical and Electronics Engineers) (IEEE) создал группу «802» по разработке стандартов для локальных сетей (Local Area Network) Hi сетей масштабов города (Metropolitan Area Network). В результате было создано целое семейство стандартов описывающих работу сетей и сетевых устройств. Из-за открытости этих стандартов и в связи с технологическим прорывом 80-х годов ХХ-го столетия они стали общепринятыми и используются практически во всех вычислительных и во многих телекоммуникационных устройствах. Наибольшее распространение получил стандарт IEEE 802.3 (Ethernet). В телекоммуникациях также широко используется стандарт IEEE 802.6 (FDDI). Также получили распространение стандарты IEEE 802.4 (Token Bus), IEEE 802.5 (Token Ring). [2, 3, 4]

С течением времени в сети стали объединять всё большее количество устройств, причем не только ЭВМ, но и телекоммуникационных устройств, i датчиков, бытовых приборов и других устройств с цифровым интерфейсом [5,6,7,8,9,10]. Пакетная коммутация данных стала вытеснять непосредственную коммутацию также и в телекоммуникационных сетях.

В' силу четкой^ и стройной иерархии, стандарты группы . 802 используются во многих областях: в промышленности, в бытовой электронике, на транспорте и т.д. Беспроводные технологии с использованием пакетной коммутации (GSM, WiFi, GPRS;, WiMAX и пр.) стали завоевывать всё большее признание, способствуя всё большему распространению; среди потребителей:, устройств, использующих, в своей работе принципы, описанные в стандартах группы 802:[2, 13, 14].

Стремительно; растет не. только количество устройств,. объединяемых в сети, но и количество передаваемой'информации; Согласно ежегодному исследованию Cisco, к 2014 году объем глобального интернет-трафика: вырастет более чем в четыре раза и достигнет 767-1018 байт [12]. Это на . 100-1018 байт больше уровня, прогнозируемого на 2013 год, и в 10 раз превышает общий объем трафика в IP-сетях в 2008 году.

Меняется и характер трафика. Большую и растущую долю трафика составляет потоковая информация в виде передачи голоса по IP-сетям (VoIP) и видеоконференции [3, 12, 5, 8,, 9, 10]. Всё это накладывает ограничения на время задержки кадров в мостах и коммутаторах [10; 18], составляющих существенную долю оборудования, используемого в. сетях. Термины «кадр» и «пакет» в*, настоящей.1 работе являются! равнозначными: В: большей части зарубежной? литературы, применяется термин «кадр» (frame)' по»отношению к низким уровням модели OSI (Open System Interconnection) и термин «пакет» (packet) для высоких уровней [3]. В. российских источниках довольно часто пользуются термином «пакет» и для низких уровней модели OSI [4, 11].

Коммутаторы и межсетевые мосты, в последнее время уже используются не только как отдельные устройства, но и как составные части сложных вычислительных, телекоммуникационных устройств или систем управлениям [19], что предъявляет повышенные требования к снижению их энергопотребления^ уменьшению требуемых вычислительных ресурсов.

Основным показателем производительности мостов и коммутаторов [4, 15, 16; 17,20] является количество обработанных кадров в единицу 6 времени и время задержки кадра. Кадры, поступающие на один порт моста должны передаваться на другой порт только в том случае, если они предназначены для сети подключенной к другому порту. Локальный трафик, т.е. кадры, предназначенные для сети, подключенной к первому порту, должны быть отфильтрованы. Таким образом, время задержки кадров зависит от скорости принятия решения о необходимости передачи кадра или его фильтрации. Время на принятие решение особенно сильно влияет на задержку кадров в межсетевых мостах и коммутаторах, работающих по принципу прямой коммутации или «на лету» [3, 15, 16, 17]. Это связанно с тем,' что передача кадра на второй порт в таких устройствах начинается сразу после приёма адресов источника и назначения; и- принятия решения о необходимости передачи.

В межсетевых мостах с различной' скоростью передачи данных на разных портах и в коммутаторах, работающих с буферизацией по принципу «store and forward», принимаемый кадр целиком.записывается во внутренний буфер и уже из него передается на нужный порт [3,4]. Это позволяет принимать решение с необходимости передачи' кадра параллельно с его приемом. В' устройствах, использующих такую организацию передачи данных, также существуют ограничения на время принятия решения. Решение о необходимости фильтрации или ретрансляции принятого кадра должно- быть принято до начала приема следующего кадра. В противном случае будет происходить переполнение премного- буфера моста и, как следствие, потери кадров.

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие основные задачи:

1. Провести анализ имеющихся методов организации, таблиц фильтрации межсетевых мостов и коммутаторов.

2. Разработать метод1 организации таблицы фильтрации кадров «без хранения адресов» в межсетевых мостах и коммутаторах.

3. Разработать адаптивный метод организации таблицы фильтрации «без хранения адресов» в межсетевых мостах и коммутаторах.

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

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

6. Исследовать эффективность разработанных методов в; сравнении с имеющимися методами организации таблиц фильтрации кадров с точки зрения вероятности переполнения таблиц фильтрации, использования памяти и вычислительных затрат, в сравнении с имеющимися методами организации^ таблиц фильтрации.

7. Разработать структурную1 схему и на ее основе синтезировать, интегральную схему, реализующую разработанный метод организации таблицы фильтрации;

8. Провести? сравнительные натурные испытания разработанного устройства и имеющихся аналогов.

Научная новизна. :

В рамках; диссертационной работы получены следующие новые научные результаты: • ■ . ■

1. Разработан, метод; организации'! таблиц; фильтрации кадров «без хранения адреса» в межсетевых мостах и коммутаторах.

2. Разработан адаптивный* метод организации таблицы фильтрации кадров «без хранения адреса» в:межсетевых мостах и коммутаторах.

3. Разработан метод организации таблиц фильтрации,'с параллельным; хешированием «без хранения адресов» в>межсетевых мостах шкоммутаторах.

4. Предложена математическая модель, для расчёта эффективности; известных методов организации таблиц фильтрации, основанная? на определении вероятности переполнения таблицы фильтрации кадров. ' •

5. На основании полученных аналитических выражений, проведена оценка , эффективности метода организации таблиц, фильтрации, «без хранения адресов» с точки зрения вероятности' переполнения таблицы фильтрации.

6. Получены результаты статистических исследований; вероятности переполнения таблиц фильтрации^ позволяющие оценить эффективность адаптивного метода^ организации таблицы фильтрации «без хранения адреса» и метода с параллельным хешированием.

Практическая значимость

1. Не менее чем в 4 раза сокращено время принятия решения о необходимости фильтрации или ретрансляции кадров.между портами моста по сравнению с существующими методами при использовании разработанных методов организации таблицы фильтрации «без хранения адресов».

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

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

4. По результатам проведенных исследований изготовлена интегральная схема межсетевого моста на базе программируемой логической интегральной схемы (ПЛИС) для; объединения вычислительных устройств с различньши канальными форматами передачи данных (IEEE 802.3, IIDLC, G.704), что подтверждается , актом внедрения и сертификатами соответствия; Минсвязи РФ.

5. Предложенные в работе технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяют в несколько раз снизить собственный ток потребления линейного стабилизатора напряжения и значительно уменьшить уровень статического входного тока повторителя напряжения, что приводит к общему снижению потребления энергии в системах управления и повышает статическую точность аналоговых интерфейсов.

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

Методы исследования основываются на использовании теории вероятностей, комбинаторики, математической статистики и машинного эксперимента на персональной электронной вычислительной машине (ПЭВМ). Проверка теоретических расчетов и выводов проводилась в пакете МаИ,аЬ и с использованием методов статистического анализа.

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

Реализация результатов работы.

Диссертационная работа выполнялась, в рамках проектов.№ 2.1.2/9532 (2.1.2/1127) «Теоретические основы проектирования нелинейных и управляемых СФ-блоков СВЧ систем связи и телекоммуникаций нового поколения» и № 2.1.2/9537 (2.1.2/7267) «Теоретические проблемы обеспечения радиационной стойкости аналоговых интегральных микросхем» аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2011 годы)».

Результаты диссертационной работы внедрены в виде интегральной микросхемы, при» разработке следующих устройств, серийно выпускаемых ООО «НПФ Сельсофт», о чем свидетельствует акт внедрения (приложение А), а именно: мультиплексоры и системы передачи серии МЦ-115Т; формирователи, концентраторы и коммутаторы потоков Е1 и ОЦК серии МК. Указанные выше устройства прошли сертификацию Минсвязи РФ, что подтверждается сертификатами соответствия (приложение Б).

Апробация работы

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

- 12-я Международная конференция «Цифровая обработка сигналов — Б8РА-2010», Москва, 2010;

- 3-я Международная конференция «Современные проблемы радиоэлектроники», Ростов-на-Дону, 2010;

Всероссийская заочная научно-практическая конференция «Информационные системы сервиса», 2011;

- 1-я Международная заочная научно-техническая конференция «Информационные технологии. Радиоэлектроника. Телекоммуникации (ГГЯТ-2011)», 2011.

Публикации»

По результатам выполненных исследований опубликовано 9 работ, в том числе 4 статьи в центральных рецензируемых журналах, из перечня рекомендованного ВАК для публикаций основных научных результатов диссертаций, 3 статьи в сборниках трудов и докладов Международных конференций, получено 2 патента РФ на изобретения.

Результаты; выносимые на защиту

1. Метод организации таблицы фильтрации «без хранения адреса».

2. Адаптивный метод организации таблиц фильтрации «без хранения адресов». ' : \

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

4. Результаты аналитических исследований, позволяющие определить вероятность переполнения таблицы, фильтрации- при? использовании имеющихся методов построения таблиц фильтрации.

5. Результаты. аналитических и статистических исследований; позволяющих определить вероятности переполнения таблицы фильтрации при использовании метода организации таблиц «без хранения адресов».

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

7. Результаты сравнительных натурных испытаний моста, реализованного на основании предложенного метода организации таблицы фильтрации «без хранения адресов» и имеющегося аналога, реализующего известный метод организации таблицьт фильтрации.

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав с выводами, заключения, списка литературы, включающего 70наименований и 8 приложений. Основной текст работы изложен на 134 страницах машинописного текста, поясняется 41 рисунком и 6 таблицами.

4.6. Выводы по главе

1. Сформулированы основные требования к мостам, применяющимся в территориально разнесённых системах управления. Обоснованна необходимость применения разработанного метода организации таблиц, фильтрации «без хранения адресов» с параллельным? хешированием.

2. Приведена; структура разработанной, микросхемы, реализующей предложенный метод организации таблиц; фильтрации. Описаны,устройства, созданные с применением разработанной микросхемы.

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

4'. Синтезирована интегральная схема на базе ПЛИС, выполняющая функции моста; реализующая метод организации*: таблицы фильтрации «без хранения адресов» с параллельным хешированием:

5: Предложено; усовершенствование, линейного стабилизатора« напряжения (Патент РФ , 2211477): Показано, что; применение усовершенствованного стабилизатора напряжения позволяет снизить ток его потребления в разы.

6. Предложено усовершенствование повторителя напряжения? с нулевым' напряжением смещения (Патент РФ' 2119241), позволяющее приблизить к нулю уровень входного тока порта, подключенного к датчику.

7. Приведены результаты сравнительных испытаний, разработанного < моста и имеющегося аналога. Результаты: испытаний) показали, что разработанный мост,.использующий метод организации таблиц фильтрации «безхранения адресов» с параллельным хешированием, потребляет в 2,2 раза меньшую мощность, чем имеющийся аналог.

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Разработан метод организации таблиц фильтрации «без хранения адресов» с параллельным хешированием, позволяющий уменьшить вероятность переполнения таблицы фильтрации в сравнении с известным методом и методом «без хранения адресов».

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

6. Получены аналитические выражения и проведены статистические исследования для определения вероятности переполнения таблицы фильтрации при использовании метода «без хранения адреса»,

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

7. Проведены статистические исследования вероятности переполнения таблицы фильтрации при использовании метода «без хранения адресов» с адаптивным хешированием. Анализ результатов исследования показал, что при* определенном количестве , перебираемых вариантов вычисления хеш-функции возможно ^уменьшение количества требуемой для таблицы фильтрации памяти в Зб разш более по сравнению с используемым методом, при равной вероятности переполнения таблицы фильтрации.

8. Проведено* статистическое исследование вероятности переполнения таблицы фильтрации; организованной методом «без.хранения адресов» с использованием:параллельного хеширования. Анализ результатов исследования позволил сделать, вывод,, что данный-метод эффективнее всех рассмотренных, методов по критерию • вероятности переполнения таблицы фильтрации при равных размерах памяти, необходимых для размещения таблицы. При проведении исследования установлено, что применение метода «без хранения адресов» с параллельным- хешированием, позволяет уменьшить объем памяти для размещения таблицы фильтрации в 72 раза и более по сравнению с известным методом.

9. По результатам проведенных исследований на базе ПЛИС была синтезирована интегральная схема межсетевого-моста, реализующая* метод организации^ таблицы фильтрации «без хранения адресов» с параллельным хешированием, для объединения сетей'с различными канальными форматами передачи данных (IEEE 802.3, HDLC, G.704), о чем свидетельствует акт внедрения (приложение А). На основе созданной интегральной^ схемы были разработаны серийные устройства, прошедшие сертификацию Минсвязи (приложение Б).

10. Предложены технические решения (Патент РФ 2119241, Патент РФ 2211477), позволяющие значительно уменьшить уровень входного тока портов, к которым подключаются датчики и собственный ток потребления линейного стабилизатора напряжения.

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

1. Robert M. Metcalfe, David R. Boggs. Ethernet: Distributed packet switching for local computer networks. // Communications of the ACM, vol. 19 no. 7, July 1976-P. 395-404

2. Современные компьютерные сети. 2-е изд. / В. Соллингс. — СПб.: Питер, 2003.-783с.

3. Лаем Куин, Ричард Рассел. Fast Ethernet. : пер. с англ., под ред. К. Королькова Киев.: Издательская группа BHV, 1998г. — 448с.

4. Кох Р., Яновский Г.Г. Эволюция и конвергенция в электросвязи // М.: Радио и связь, 2001

5. Соколов H.A. Телекоммуникационные сети. — М.: Альварес Паблишинг, 2004

6. Бакланов И.Г. NGN: принципы построения и организации. М.: Эко-Трендз, 2008

7. Гольдштейн Б.С., Пинчук A.B., Суховицкий А.Л. 1Р-телефония. 3-е изд. М.: Радио и связь, 2006. - 336с.

8. Тюхтин М.Ф. Системы Интернет-телевидения. —М.: Горячая линия-Телеком, 2008. 320с. '

9. Джонатан Д., Бхатия Д.П.М., Калидинди С., Мукхержи С. Основы передачи голосовых данных по сетям IP. M.: Издательский дом «Вильяме», 2007. - 400с.

10. IEEE Std 802.3, 2000 Edition, Part 3: Carrier sense multiple access with collision detection (CSMA/CD) access method and physical layer specifications.

11. Cisco VNI2009-2014 Индекс развития визуальных сетевых технологийза 2009-2014 гг. URL: http://www.cisco.com/en /US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/whitepapercll481360.pdf

12. Тихвинский В.О., Володина Е.Е. Подвижная связь третьего поколения. Экономика и качество услуг. М.: Радио и связь, 2005. - 240 с.

13. Попов В.И. Основы сотовой связи стандарта GSM. М.: Эко-Трэндз, 2005.

14. Тененбаум Э. Компьютерные сети. 4-е изд. — СПб.: Питер, 2005. 992с.

15. Семенов? Ю.А. Протоколы Интернет. — М.: Горячая линия-Телеком, 2001.- 1100с.

16. Гольдштейн А.Б., Гольдштейн Б.С. SOFTSWITCH. СПб.: БХВ - 2007.I

17. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. — М.: Техносфера, 2003. — 512с.

18. Пушкарев О. Процессорный модуль RCM5700 для систем безопасности и управления // Новости Электроники № 8 2009. URL: http://ns2.gete.ru/literature/compeljournal/2009/200908/p4.html

19. Гольдштейн Б.С., Соколов H.A., Яновский Г.Г. Сети связи: Учебник для ВУЗов. СПб.: БВХ-Петербург, 2010. - 400с.

20. IEEE Std 802.ID, 1998 Edition, Part 3: Media Access Control (MAC) Bridges.

21. Кормен Т. X., Лейзерсон Ч. И., Ривест P. JL, Штайн К. Алгоритмы:8построение и анализ, 2-е издание.: Пер. с англ., Под ред. И. В. Красикова. — М.: Издательский дом «Вильяме», 2005. — 1296 с.

22. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск: Пер. с англ., М.: Мир, 1978, 845 с.4

23. Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. — М.: Вильяме, 2000. — С. 384

24. Олифер В.Г., Олифер Н.А. Компьютерные сети: Принципы, технологии, протоколы. 3-е изд. — СПб.: Питер, 2008. 958 с.

25. Патент США №4627052 Interconnection of communications networks, 02.12.1986

26. Патент США №US6678269B1 Network switching device with disparate database formats, 13.01.2004

27. Патент CILLA №4215402 Hash index table hash generator apparatus, 29.07.1980

28. Патент США №US20070071015 Using CRC-15 as hash function for MAC bridge filter design, 29.03.2007 r.

29. Патент США №6279097 Method' and apparatus for adaptive address lookup table generator for networking application, 21.08.2001 r.

30. Чмора А.П. Современная прикладная криптография. 2-е изд., стер. — Mí: Гелиос АРВ, 2002. — 256 с.

31. Dumey A. Indexing for Rapid Random Access, Memory Systems // Computers and Automation. (1956). 4, no. 12. P. 6-9.

32. Ершов.А.П., Избранные труды Новосибирск: «Наука», 1994.

33. Патент США №US6697873B1 High speed MAC address search engine, 24.02.2004

34. Патент США №US6990102B1 Parallel lookup tables for locating information in a packet switched network, 24.01.2006

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

36. Патент CILIA №US7418505B2 IP Address lookup using either a hashing table or multiple hash functions, 26.08.2008

37. Патент США №5914938 MAC address table search unit, 22.06.1999

38. IEEE Std. 802.1 Q, 1998 Edition, Standards for local and metropolitan area networks: virtual bridged local area networks.

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

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

41. Маков C.B., Липок В.И. Организация фильтрации «Без хранения адресов» в межсетевых мостах .и коммутаторах методом параллельногохеширования Электронный ресурс. // Сервис в России и; за рубежом: i

42. Вып.5(24). 2011г. URL: http:// www.mgus.ru/ files/ electronicjournal/ number24Z6.doc

43. Корн Г., Корн Т. Справочник nos математике (для научных работников и инженеров). М.: Наука, 1974г. - 832 с.

44. Стенли Р. Перечислительная комбинаторика: Пер. с англ. — М.: «Мир», 1990г.—440 с.

45. Липский В. Комбинаторика для программистов. — М.: Мир, 1988г. -213 с.

46. А. Н. Колмогоров, Теория вероятностей и математическая статистика. — М.: Наука, 1986.-534с.

47. Кнут Дональд Э. Искусство программирования, том 4, выпуск 3: генерация всех сочетаний и разбиений.: Пер. с англ. -М.: ООО «И.Д. Вильяме», 2007г. 208с.50: Козлов М.В. Элементы теории вероятностей в примерах и задачах. М.: МГУ, 1990г.-344 с.

48. Секей Г. Парадоксы в теории вероятностей и математической статистике: Пер. с англ. М.: Мир, 1990г. 272 с.

49. Ширяев А.Н. Вероятность. В 2-х кн. 3-е изд., перераб. и доп. - М.: МЦНМО, 2004. - 520с.

50. Маков С.В., Шрайфель И.С. Оценка эффективности фильтрации трафика в межсетевых мостах и коммутаторах Электронный ресурс. // Сервис в России и за рубежом. Вып.5(24). - 2011г. URL: http:// www.mgus.ru/ files/ electronicjournal/ number24/ 5.doc

51. Ерош И. JI. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. —37с.

52. IEEE Std. 754, 1985 Edition, Standard for Binary Floating-Point Arithmetic.

53. Боровков Л.Л. Математическая статистика. — Учебник. — М.: Наука., 1984г.-472 с.

54. Большее Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука. 1983г.-416 с.

55. Грэхем Р., Кнут Д., Паташник О., Конкретная математика. Основание информатики: Пер. с англ. М.: Мир, 1998. - 703с.

56. Программно-информационные комплексы автоматизированных производственных систем: учеб.- пособие для сред. спец. учеб. заведений / Клейменов С. А. М. : Высшая школа, 1990. - 224 с.

57. Лазарев В.Г. Интеллектуальные цифровые сети: Справочник / Под ред. Академика Н.А.Кузнецова. — М.: Финансы и статистика, 1996. — 224 с.

58. Попов А.Э., Манжула В.Г., Маков C.B. Формализация процедур синтеза принципиальных электрических схем // Изв. вузов. Сев.-Кавк. регион. Техн. науки. Ростов, 1999.— Вып. 3.— С. 75 - 78

59. Попов А.Э., Маков C.B. Информационное обеспечение системы поискового конструирования в области схемотехники. // Информационные технологии в науке и образовании: Сб. науч. тр. / Под ред. В.В. Медведева.— Шахты: ДГАС, 1998.— Вып. 26.— С. 69 74

60. Cyclone II Device Handbook. Vol.1 / ALTERA Электронный ресурс. URL: http://www.altera.com/literature/hb/cyc2/cyc2cii5v 1 .pdf

61. Блэк Ю. Сети ЭВМ: протоколы, стандарты, интерфейсы. М., Мир, 1990.

62. Протоколы информационно-вычислительных сетей: Справочник/ С.А.Аничкин,. С.А.Белов, А.В.Берштейн и др.; Под. ред. И.А Мизина, А.П.Кулешова. М.: Радио и связь, 1990. - 504с.:ил.

63. Пататент РФ 2211477, МКИ G05F 1/56. Стабилизатор постоянного напряжения / C.B. Маков., А.Э. Попов /РФ/. №2002100748/09; Заявл. 08.01.2002.; Оубл. 27.08.2003 Бюл.№25. -5с.:ил.

64. National Semiconductors Data Book 1984, p243, F 145

65. Патент США № 4322691 Cyrcuitry for generating electric signals with proportional, opposite-sencse rates of chang. 30.03.1982

66. Патент РФ 2119241, МКИ 6H03F 3/21. Повторитель напряжения / А.Э. Попов, C.B. Маков. /РФ/. №97112773/09; Заявл. 29.07.97.; Опубл. 20.09.98 Бюл.№26. -Зс.: ил.

67. ADM6993/X HDLC to Fast Ethernet converter: data sheet Rev 1.11, Nov. 2005 Электронный ресурс. URL: http:// img.chipfind.ru/ pdf/ infmeon/ adm6993xdsgreenversionl.pdf