Оценка эффективности фильтрации трафика в межсетевых мостах и коммутаторах Сергей Владимирович Маков
Скачать 82.95 Kb.
|
стр. из 9 УДК 004.71 Оценка эффективности фильтрации трафика в межсетевых мостах и коммутаторах Сергей Владимирович Маков, аспирант, каф. «Радиоэлектронные системы», е-mail: makovs@rambler.ru Игорь Семенович Шрайфель, к.ф-м.н, доцент, каф. «Математика», е-mail: mail@sssu.ru ФГОУ ВПО «Южно-Российский государственный университет экономики и сервиса», г. Шахты, Ростовская обл. Authors propose a method for evaluation of the efficiency of local traffic filtering for interconnection bridges and switches, which operated at hashed tables filtering with a resolution of collisions way of blocks or chains; it is shown that this method allows to assess the effectiveness of the bridge or switch for a known number merged network nodes and required maximum probability of overflow table filtering, as well as to determine the parameters of this table, which are sufficient to ensure given probability of its overflow in certain conditions of bridge or switch using. Предложен способ оценки эффективности фильтрации локального трафика для межсетевых мостов и коммутаторов, в которых применяются хешированные таблицы фильтрации с разрешением коллизий способом блоков или цепочек; показано, что данный способ позволяет оценить эффективность работы моста или коммутатора при заданном числе объединяемых узлов сети и требуемой максимальной вероятности переполнения таблицы фильтрации, а также определить параметры этой таблицы, достаточные для обеспечения заданной вероятности ее переполнения в определенных условиях применения моста или коммутатора. Keywords: interconnection bridges and switches, the hash function, the probability of an overflow table filtering. Ключевые слова: межсетевые мосты и коммутаторы, хеш-функция, вероятность переполнения таблицы фильтрации. В большинстве систем связи, использующих принцип пакетной коммутации, применяются межсетевые мосты и коммутаторы [1, 2, 15 – 17]. Основной их функцией является фильтрация локального трафика. Кадры, адресованные узлам в пределах сегмента сети, подключенной к одному порту моста или коммутатора, не должны передаваться на другие его порты. Кроме того, нежелательной является передача трафика в те сегменты сети, где не будет получателя для него, так как это приводит к увеличению нагрузки на всю сеть. Принцип работы межсетевых мостов и коммутаторов описан в стандарте IEEE802.1D [3]. Для фильтрации локального трафика и правильной ретрансляции трафика в мостах и коммутаторах применяются так называемые таблицы фильтрации (lookup table). Мост составляет таблицу фильтрации, считывая адреса источников кадров, приходящих с разных портов. В ней каждому адресу узла соответствует номер порта, к которому он подключен. Для каждого принятого кадра принимается решение о необходимости его фильтрации или ретрансляции. Если адрес назначения принятого кадра есть в таблице фильтрации и номер порта не совпадает с номером порта, через который был принят кадр, то происходит его передача на порт с номером, найденным в таблице фильтрации. Кадр передается на все порты, кроме приемного, если в таблице фильтрации нет адреса, совпадающего с адресом назначения принятого кадра [4, 5]. В настоящее время на практике для организации таблиц фильтрации применяют хешированные таблицы с разрешением коллизий способом блоков [12 – 14]. Отличительной особенностью таблиц с хешированием [10, 11] является гарантированное максимальное число операций на поиск и на добавление данных в таблицу. Для каждого значения адреса назначения кадра по определенному закону вычисляется хеш-функция, имеющая разрядность меньше, чем разрядность адреса. Полученное значение является индексом в таблице фильтрации, и по нему происходит чтение адреса и соответствующего номера порта. Очевидно, что для одного значения хеш-функции может существовать несколько порождающих его значений адреса. То есть может появиться ситуация, когда для разных узлов в сети будет вычислена одинаковая хеш-функция. Такая ситуация называется коллизией, или переполнением таблицы. Для уменьшения вероятности переполнения таблицы фильтрации на одно значение хеш-функции выделяют блок из нескольких записей. В настоящее время на практике применяются таблицы фильтрации с выделением четырех записей для одного значения хеш-функции [12 – 14]. Применение такого алгоритма построения таблиц не исключает возможности их переполнения. То есть существует вероятность того, что для нескольких узлов в сети, подключенной к мосту, окажутся равными значения вычисленных хеш-функции. Это может привести к передаче кадра на порты, для которых он не предназначен. Такая ситуация носит название «размножение кадра», при этом снижается эффективность фильтрации нежелательного трафика. Таким образом, для оценки эффективности алгоритма фильтрации нежелательного трафика необходимо знать вероятность переполнения таблицы фильтрации. Введем следующие обозначения:  – число элементов конечного множества  ;  – целая часть действительного числа  ; для всех целых  справедливо равенство  .Зададим произвольные целые неотрицательные числа  и  . Эти числа будут описывать способ организации хешированной таблицы фильтрации следующим образом:  – число возможных адресов; r – число возможных значений хеш-функции; m – число узлов во всех сетях, подключенных к мосту или коммутатору; k – число ячеек в таблице фильтрации, выделенных под одно значение хеш-функции.Хеширование приведет к разбиению всего множества возможных адресов на r непересекающихся l-элементных подмножеств, для которых значение хеш-функции одинаковое. Рассмотрим  попарно не пересекающихся множеств  и положим  (в случае  ,  ). При этом  -элементное подмножество  множества  назовем  k-допустимым (чаще будем говорить коротко: допустимым), если при каждом  множеству  принадлежит не более  элементов множества . Для числа всех допустимых множеств выведем формулу .Очевидно, что величина  положительна тогда и только тогда, когда  . (1)Далее будем считать неравенство (1) выполненным. При  из него следует равенство нулю и . Тогда единственным допустимым множеством является  и при всех  справедливо соотношение . (2)Рассмотрим случай  . Для всякого допустимого множества положим  ,  . Найдем диапазон возможных значений величины  . Любое допустимое множество  удовлетворяет двум условиям: , Эти условия сводятся к системе неравенств  Данную систему неравенств можно записать в виде интервала  .Поскольку s – целое неотрицательное число, то интервал будет иметь вид  . (3)Справедливо обратное утверждение, т.е. для каждого целого  из промежутка (3) найдется допустимое множество , удовлетворяющее условию  . Для построения такого множества нужно выполнить следующую последовательность действий:
Первое из указанных действий можно осуществить  способами, второе, согласно комбинаторному принципу умножения, –  способами; наконец, третье –  способами. Вновь применив принцип умножения, найдем общее число k-допустимых множеств: . (4)Следует заметить, что неравенства (1) и (3) влекут положительность всех величин вида  , фигурирующих в правой части формулы (4), а значит, применимость к ним этой же формулы при соответствующих значениях  . Используя полученное рекуррентное соотношение, выведем формулы для вычисления при  .Подставив в (4)  и с учетом равенства (2), найдем: ; .При  получаем: ; .При  :   ;  .Наконец, при k = 4:    ;  .Пусть из множества всех возможных адресов наудачу выбирается m-элементное подмножество адресов узлов в сетях, подключенных к мосту (в данном случае слово «наудачу» означает равные вероятности попадания в выбираемое множество для всех элементов множества ). Общее число способов, которыми можно из элементов множества выделить элементов множества , равно  .Согласно классическому определению, вероятность извлечения из множества  допустимого множества , т. е. вероятность непереполнения таблицы фильтрации, равна .Вероятность обратного события – переполнения таблицы фильтрации – можно вычислить по формуле  .Ниже на рисунке представлены графики зависимостей вероятности (P) переполнения таблицы фильтрации от числа узлов в сетях (m), подключенных к мосту или коммутатору, для различного числа записей на одну хеш-функцию. Для расчетов было взято  и  [13], что соответствует 10-битной хеш-функции и 48-разрядному адресу узла в сети. Рис. 1. Вероятности переполнения таблицы фильтрации Анализ результатов вычислений, изображенных на приведенных графиках, показывает, что c увеличением числа ячеек на одно значение хеш-функции возрастает число узлов в сети, при котором вероятность переполнения таблицы фильтрации не будет выше заданной. _____________________________________________________________________________ Таким образом, полученные в данной статье аналитические выражения позволяют оценивать эффективность алгоритма фильтрации в мостах и коммутаторах исходя из предполагаемого числа объединяемых узлов сети и заданной максимальной вероятности переполнения таблицы фильтрации. Литература
Поступила 25.04.2011 г. |
множества 
;
при каждом 
из множества 
выбрать 
-элементное множество 
;
-элементном множестве 
выделить 
- допустимое множество 
;
.Похожие:
 | Мультифрактальные свойства речевого трафика В последних работах публикуются результаты, доказывающие мультифрактальную природу трафика телекоммуникационных сетей [3, 4]. Разработаны... | | I. Оценка эффективности pr – историческая перспектива Именно поэтому, оценка эффективности pr-кампании, не должна оставаться неформальной и ненаучной. Необходимы объективные методы, предоставляющие... |
| «Сравнительный анализ межсетевых экранов» В реферате на основе анализа российского рынка рассмотрены особенности и возможности использования наиболее эффективного в настоящее... | | Лабораторная работа №12 оценка эффективности устройства Оценка эффективности устройства защитного отключения (узо), реагирующего на ток нулевой последовательности (дифференциальный ток)... |
| Московский Гуманитарный Университет Оценка эффективности рекламной кампании Смирнова О. О. «Оценка эффективности рекламной кампании». Учебно-методические материалы | | Свидетельство о государственной регистрации программы для ЭВМ регистрационный номер: 2012612880 ( 23. 0 201 2 ) Авторы: Дерюгин Юрий Николаевич, Козелков Андрей Сергеевич, Зеленский Дмитрий Константинович, Глазунов Виктор Алексеевич, Полищук... |
| Теоретической части курсовой работы По дисциплине «экономическая оценка инвестиций» на тему: «оценка эффективности инвестиционного проекта» |  | Математика и естественные науки Председатель – Русаков Сергей Владимирович,профессор кафедры прикладной математики, д ф м н., Пгу |
| Лабораторная работа №3 оценка эффективности защитного заземления Оценка эффективности защитного заземления в трехфазной сети с изолированной нейтралью и в трехфазной четырехпроводной сети с глухозаземленной... | | В сфере строительства и жкх Тишкин Сергей Владимирович, Генеральный директор «Финансово-промышленной Группы «Технологии Энергосбережения», к э н |