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

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

Шиготаров Андрей Владимирович

МЕТОД УМЕНЬШЕНИЯ РАЗМЕРА ТАБЛИЦ МАРШРУТИЗАЦИИ В

1Р-СЕТЯХ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ульяновск -2010

1 5 АПР 20)0

004600892

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

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

Смагин Алексей Аркадьевич

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

Ишмухаметов Шамиль Талгатович кандидат технических наук Угаров Владимир Васильевич

Ведущая организация: ГОУ ВПО Ульяновский государственный

технический университет

Защита состоится 5 мая 2010 года в Ю00 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: Набережная р. Свияги, 106, корпус 1, ауд. 703.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, с авторефератом на сайте ВУЗа www.uni.ulsu.ru.

Автореферат разослан « 3 » апреля 2010 года.

Просим прислать отзыв на автореферат по адресу: 432000, г. Ульяновск, ул. Л. Толстого, д. 42, УлГУ, Управление научных исследований.

Ученый секретарь М. А. Волков

диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность исследования. Неотъемлемой частью процесса построения быстродействующих сетей является разработка эффективных схем хранения и поиска записей в таблицах маршрутизации (ТМ). Одним из следствий быстрого роста Internet стало значительное увеличение размера таблиц маршрутизации. Данный факт, а также ограниченность ресурсов программного и аппаратного обеспечения, существенно затрудняют возможность их эффективной обработки. Исследователями было предложено большое количество схем для увеличения скорости поиска в таблицах маршрутизации. Алгоритмические методы включают в себя: локальный поиск, двоичный поиск, использование специальных структур данных (бинарные деревья, трие), хеширование и ряд других. Основным недостатком данных подходов является то, что они требуют нескольких обращений к памяти. Требования к производительности современных сетей являются очень высокими, в то время как время отклика современных архитектур памяти ограничивают возможное количество обращений к памяти. Одним из наиболее распространенных и перспективных аппаратных решений является тернарная ассоциативная память (ТСАМ). Главной особенностью ТСАМ является то, что адресация осуществляется на основе содержания данных, поиск нужной записи, при этом, может быть осуществлен за одно обращение к памяти. Значительное число исследований, посвященных проблеме повышения эффективности обработки таблиц маршрутизации, ориентировано на использование данной аппаратной реализации и основано на методах сжатия таблиц маршрутизации1. Уменьшение таблиц маршрутизации позволяет повысить скорость поиска нужной записи, использовать память меньшего размера, а также снизить энергопотребление маршрутизатора. Современное состояние дел в данной области знаний во многом основано на работах С. CTepraoy(S.Stergiou)2, В. Равикумара (V. Ravikumar)3, Р. Гуо (R.Guo) и Ж. Дельгадо-Фриаса (J. Delgado-Frias)4. Отечественные авторы, например, В. Г. Олифер и Н. А. Олифер5, внесли вклад в развитие теоретических основ проблем эффективной маршрутизации.

1 Wu W. Packet Forwarding Technologies. - Auerbach Publications, 2007, 446 p.

2 Stergiou S., Jain J. Optimizing Routing Tables on Systems-on-Chip with Content-Addressable Memories //Proc. IEEE International System-on-Chip Symposium, 2008, pp 1-6.

3 Ravikumar V. C., Bhuyan L. N., Mahapatra R. N., EaseCAM: An Energy and Storage Efficient TCAM-Based Router Architecture for IP Lookup // IEEE Transactions on Computers, vol. 54,2005,521-533.

R. Guo, J. G. Deigado-Frias. IP Kouting table compaction and sampling schemes to enhance TCAM cache

performance II Journal of Systems Architecture, vol. 55,2009, pp. 61-69 Олифер В.Г., Олифер H. А. Компьютерные сети: принципы, технологии, протоколы. - Спб Питеп 2001 -672 с.

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

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

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

• анализ существующих методов сокращения таблиц маршрутизации;

• построение математической модели таблиц маршрутизации;

• разработка быстродействующих методов сокращения таблиц маршрутизации;

• экспериментальное исследование эффективности предлагаемых алгоритмов.

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

• двоичных диаграмм решения для совместной обработки импликант,

• метода ветвей и границ для ограничения перебора в пространстве возможных решений,

- двухуровневого представления импликант для повышения скорости поиска в множестве всех исходных импликант,

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

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

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

Основные положения, выносимые на защиту

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

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

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

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

быть использованы в системах автоматизации проектирования интегральных схем.

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

Личный вклад автора. Постановка задач исследования осуществлена совместно с научным руководителем А.А.Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.

Апробация работы проведена на шестой всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2009) и ежегодных научно-технических семинарах кафедры

«Телекоммуникационные технологии и сети» УлГУ.

Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 - в изданиях из перечня ВАК.

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

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

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

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

- применимость к различным типам аппаратной реализации таблиц маршрутизации;

- способ реализации;

- используемые математические методы;

- соответствие исходной и сокращенной таблиц маршрутизации.

Задача сокращения таблиц маршрутизации значительно осложняется

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

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

Вторая глава посвящена разработке метода уменьшения размера таблиц маршрутизации в 1Р-сетях. Каждому узлу 1Р-сети соответствует идентификатор - 1Р-адрес. 1Р-адрес представляет собой двоичное число а = а1..мк , a¡ е {0,1} для 1 < / < кшх, длиной кшх, которая зависит от

используемой версии протокола 1Р - для версии 1Ру4 кШУ =32, для 1Ру6 -^шх = 128. Согласно технологии бесклассовой междоменной маршрутизации (СГОИ), введенной в 1993 г., записи таблиц маршрутизации содержат так называемые 1Р-префиксы, которым может соответствовать не только отдельный узел, но и целая сеть. Пусть дан произвольный 1Р-префикс

Р = Р\Рг—Рп кшх, р1 е{0,1,*} для 1</</, символом \р\ будем

обозначать длину 1Р-префикса. При этом "*" соответствует неактивным разрядам. Введем следующие обозначения 5 = {0,1,*}, 5, ={0,1,*}' для

кшх

1 <1< кшх, Бай = и - множество всех возможных 1Р-префиксов, <=1

А = 3Кшх \ {5 6 = *} - множество всех ТР-адресов.

Введем также функции

(1)

Л(0) = {0}, Л0) = {1}, ЛИ = {0,1}

и

МаКН: А, БаП -» {0,1,..., ккш}, (2)

[0,3/ 1</<|р|/5(а,.)П/5(А) = 0

1Р-адрес а соответствует 1Р-префиксу р, если МшЛци, р) > 0, 1Р-префикс р содержится вр\ если \р\=\р'\ и V; 1 <; <|/?| ).

Базовым методом маршрутизации в IP-сетях является сопоставление по наиболее длинному префиксу. При этом для отправки трафика выбирается запись, IP-префикс которой дает наибольшее совпадение разрядов с адресом назначения входящего пакета. В приведенной выше нотации для некоторого IP-адреса а е А сопоставление по наиболее длинному префиксу эквивалентно нахождению argma\{Match(a, р)).

PtSall

Таблица маршрутизации представляет собой в общем случае отображение Sall -> U, где U - множество всех возможных следующих узлов. Таблица маршрутизации может быть представлена следующим образом RT={{s\u\..,{sm,um)}, sl е Sall,и' eU.

Пусть дан алфавит {х1,...хкшх}. Произвольному IP-префиксу s еSal! можно сопоставить конъюнкцию Ks = кх &....&.к^,

х., если s, = 1, к, =jx,, earns, = 0,

1, если si = * \<i<\s\.

Аналогично можно определить и обратное преобразование: произвольной элементарной конъюнкции К и длине IP-префикса / будет соответствовать IP-префикс 5 = 5] ...Sj,

*, если К не содержит ни хп ни

1, если К содержит^, ^

0, если К содержи т х; 1 </</.

Разработанный метод уменьшения ТМ основан на идее X. Лиу6 и использует для представления IP-префиксов, имеющих одинаковую длину / и следующий узел и, отдельные булевы функции fut в дизъюнктивной нормальной форме. Сокращение ТМ достигается путем минимизации соответствующих ДНФ.

Произвольному множеству IP-префиксов Р = {Р\,Р2,—Рт}. Pi 6 Sall, \Pi\=\P2\=---\Pm\ Для 1 <i<m, сопоставляется булева функция

FP=KpivKp2v...vKPm (5)

6 Liu Н. Routing Table Compaction in Ternary-CAM II IEEE Micro, Jan/Feb 2002, pp. 58-64.

8

Рассмотрим фрагмент таблицы маршрутизации, который приведен в таблице 1. 1Р-префиксам из данного примера будут соответствовать следующие функции: /¡,28 ~ 0*11*12*1 З^4-^13-*!8*1 д-^гО-*^ 1-*'22-*:23х24х25*26л:27-х:28

/2,16 = *|*2*3*4*5*б*7*8*9х10*11*12*13*14*15*16 у

х\ *2*3*4*5*б*7*8*9*10* 11*12*13*14*15*1 б /з,16 = *1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16

Таблица 1. Фрагмент таблицы маршрутизации

1Р-Префикс Узел

172.68.20.16/24 I

172.68.0.0/16 2

67.118.0.0/16 2

128.116.0.0/16 3

Введем функцию Шт: и {!,..., | и |}, сопоставляющую каждому элементу и порядковый номер.

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

1. Исходная ТМ ^{(л'У),...,О"',м'н)}, е 5й//)М'' еи разбивается на совокупность ТМ

ЯТк = {(«,«) | {я,и) е ЯТ,Ыит(и) = £}для 1 < & <| £/|

2. Каждая из 'ГМ ЯТ1,...,КТг;. разбивается на совокупность

<->Щкшх . 1 2 / <| С/1. ЯТу = {(«,и) I (*,И) 6 ЯТ;,15 |= Л для

3. Для каждой подтаблицы ПТи] 1 < г <| (У ], 1 < у < кАШ, строится соответствующая ей булева функция, заданная ДНФ ¿) ^.

4. Для каждой построенной ДНФ Д у запускается процедура минимизации, результатом которой является минимальная ДНФ

, реализующая £>,■ •.

5. Для каждой ДНФ строится соответствующая ТМ ЛТ^т

6. Производится объединение построенных ТМ ЯТ,М-М

Таким образом, основу метода составляет использование булевых функций в качестве математических моделей таблиц маршрутизации и алгоритмов минимизации ДНФ как моделей процесса сокращения числа записей в ТМ. При этом основные затраты вычислительных ресурсов происходят именно на этапе построения минимальных ДНФ. Преобразования 1-6, очевидно, не влияют на результат маршрутизации, т.е. выбор узла, на который необходимо пересылать трафик. Действительно, любая запись (р, и) из исходной ТМ Щ в сокращенной ТМ заменяется записью (р',и), содержащей 1Р-префикс такой же длины и тот же следующий узел, при этом р содержится в р'. Данный факт обусловливает эквивалентность результатов поиска в ТМ на основе сопоставления по наиболее длинному префиксу.

Метод может быть реализован с помощью использования тернарной ассоциативной памяти. Помимо индекса, являющегося побитовой записью 1Р-префикса, ТСАМ хранят также отдельную маску для каждой записи. Маска определяет, какие из битов индекса являются активными (см. таблицу 2). Заметим, что записи 1 и 2 отличаются только значением 4-го бита и могут быть скомбинированы в запись (10100000,11100000, 1).

Таблица 2. Таблица 1Р-префиксов, хранящаяся в ТСАМ

Запи 1Р-Префикс Маска Следующ

сь ии узел

1 10100000 11110000 1

2 10110000 11110000 1

3 11011000 11111000 2

4 10001000 11111000 3

5 10111000 11111000 2

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

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

меньше количества записей в исходной ТМ. Схема алгоритма приведена на рисунке 1.

^ Ппчалч ^

Огргилггк длияу кЫ \C.VHCMklV

tl0CT l>t»HlU И1К1Ж1Ч.1Ж» Ч

пстх уиика.11.иы<

ПЧ11ЛИКЛЧ1 ил Т

Алгоритм использует двухуровневое представление импликант минимизируемой функции, основанное на выделении у импликант префиксов длиной к и последующей группировке по ним. Под префиксом (постфиксом) длиной к произвольной импликанты

/ = х?&...&х/'т'(а, е{0,1}, х°" — х, еслиег;=1 и х/ = ~х, если ст1 = О, i = 1,...,/) здесь и далее понимается конъюнкция сомножителей 1~ х"', таких что 1 <i<k{l-k<i<l). Пусть Н = {А,,...hm} - множество всех уникальных префиксов импликант из исходной ДНФ Т. Каждому элементу h, еН, 1 < i < m сопоставляется множество постфиксов В, длиной 1-к импликант из Т, содержащих h.. Процесс минимизации осуществляется для каждого такого

множества отдельно, обозначим полученные минимальные ДНФ DB ,...,DB . Тогда ДНФ DH, реализующая все исходные импликанты образуется следующим образом: DH ■= /i, DB v .4hmDB . Для увеличения качества сжатия ТМ запускается аналогичная процедура для сгруппированных по постфиксам длиной l-к импликант из D,,. Таким образом, на первом этапе производится уменьшение числа импликант путем расширения постфиксных частей, на втором - префиксных. Число уникальных префиксов/постфиксов значительно меньше количества импликант в исходном представлении и, в связи с этим, они могут эффективно храниться и обрабатываться, в данной работе для этого было использовано хеширование. Уменьшение размерности также позволяет использовать кэширование результатов минимизации: если два множества импликант 11 и /2 имеют не пустое пересечение /'= /, П12 и /' содержится в кэше, то импликанты из Г будут обрабатываться лишь один раз. В качестве длины выделяемых префиксов выбиралось значение к, дающее наименьшее значение + к2, где к, ,к2 - количества уникальных префиксов и постфиксов, соответственно. Данная эвристика позволяет строить компактное представление исходного множества импликант к, в тоже время, имеет простую реализацию. Для выполнения возникающих задач минимизации был использован стандартный "жадный" алгоритм, выбирающий на каждом шаге простую импликанту, покрывающую наибольшее количество еще не покрытых импликант.

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

1. Генерация всех простых импликант функции;

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

минимизации (рисунок 2) использует для представления булевых функций упрощенные упорядоченные двоичные диаграммы решения (ROBDD), а для покрытий - двоичные диаграммы с отбрасыванием незначащих нулей (ZDD)8. Двоичные диаграммы решения (BDD) были выбраны в связи с тем, что сложность алгоритмов их обработки зависит от количества узлов в

7 Самофалов К.Г, Романкевич А.М. Прикладная теория цифровых автоматов. - Киев "Вища школа",1987 -375 с.

8 Meinei С, Theobald T. Algorithms and data structures in VLSI design, Springer-Verlag NY, 1998. - 267 p.

12

дииаграмме, которое может быть намного меньше количества представляемых дискретных объектов, число последних, в свою очередь, может достигать значительных величин, например, верхняя граница количества всех простых импликант 0(3" \ -Тп)9 (п - количество переменных).

Рисунок 2, Схема точного алгоритма минимизации ШЗВОО- и гОО-представления отличаются от обычных двоичных диаграмм решения наличием заданного порядка переменных и набора ограничений на их структуру, которые позволяют реализовать компактное и каноничное представление соответствующего множества дискретных объектов. КОВОБ-представление должно удовлетворять следующим требованиям:

1. отсутствие изоморфных подграфов;

2. отсутствие узлов, оба исходящих ребра которых указывают на один и тот лее узел.

' Chandra А.К., Markowsky G. On the number of prime implicants// Discrete Mathematics 24(1978), pp 7-11.

13

В случае двоичных диаграмм с отбрасыванием незначащих нулей (2ТЮ), первое требование сохраняется, а вместо удаления вершин, исходящие ветви которых указывают на один узел, удаляются узлы с единичным выходом, указывающим на терминальный узел 0. Данная разновидность диаграмм решения более эффективна, по сравнению с ЯОВОО, для представления разреженных множеств, в частности, покрытий булевых функций.

Задача построения минимальной ДНФ рассматривается как задача о покрытии. Пусть М обозначает множество всех точек {т],тгв которых заданная функция/принимает значение 1, а Р = {р1,р2,...,рк) -множество всех простых импликант/ Матрицей покрытия будем называть бинарную матрицу А размерности / х к такую, что 1 (при этом будем говорить, что у-й столбец покрывает йю строку), !</</, 1 < / < к, если т1 6 рг в противном случае А^=0. Требуется найти минимальное количество

столбцов, покрывающих все строки матрицы А. В диссертации использованы методы, позволяющие уменьшить размерность решаемой задачи о покрытии за счет удаления доминируемых элементов множеств М и Р, а также выделения существенных простых импликант. Генерация простых импликант, а также удаление доминируемых строк и столбцов осуществлялись с помощью методов, предложенных Коудертом и Мадре10.

Процесс построения минимального покрытия основан на применении метода ветвей и границ (МВГ). Основными факторами, влияющими на эффективность метода ветвей и границ, являются: выбор столбца для ветвления, способ получения нижних и верхних границ.

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

р = агёшах -Т7 ■ (6)

10 Coudert 0., Madre J. C. Implicit and incremental computation of primes and essential primes of Boolean functions // Proc.of the Design Automation Conf. (Anaheim, CA, 1992), pp 36-39.

'' Coudert 0. On Solving Covering Problems //Proc. of 33rd DAC, Las Vegas, 1996. - pp. 197-202.

Для вычисления нижних границ, задача построения минимального покрытия рассматривается, как задача целочисленного линейного программирования:

к

min xj

к

^AijXj>l / = 1,2,...,/

(7)

Xj s {0,1} j = l,...,k

Очевидно, что решение релаксированной задачи

min{x| Ах >= Ь),

(8)

где b - единичный вектор, дает нижнюю границу для (7).

Для решения релаксированной задачи был использован двойственный симплекс-метод. Необходимо заметить, что в процессе работы алгоритма ветвей и границ, не нужно решать (8) для каждой новой вершины заново. Вместо этого к симплекс-таблице, соответствующей родительскому узлу, добавляется ограничение х~1, либо х/= 0, а двойственный симплекс-метод применяется к обновленной таблице.

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

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

12 Liao S., Devadas S. Solving covering problems using Ipr-based lower bounds // Proc. of the 34th Design

13 Li X.Y., Brglez F., Stallmann M.F. Effective Bounding Techniques For Solving Unate and Binate Covering Problems И Proceedings of the 42nd annual Design Automation Conference, 2005 - pp 385-390.

14 Схрейвер А. Теория линейного и целочисленного программирования : в 2-х т. - М.: Мир, 1991

данном факте, был разработан модифицированный метод ветвей и границ. На первом шаге вычисляется нижняя граница задачи к и запускается метод ветвей и границ с установленной верхней границей, равной к. Если будет найдено решение, то оно является оптимальным и алгоритм останавливается, в противном случае, снова запускается метод ветвей и границ с верхней границей, равной £+1 и т.д. Таким образом, МВГ используется для проверки - существует ли решение стоимости к.

Наиболее важными отличительными особенностями алгоритма построения точного решения являются: новая схема получения верхних границ при решении задачи о покрытии с помощью МВГ, а также комбинирование известных подходов - использование двоичных диаграмм решения для генерации простых импликант и упрощения матрицы покрытия, и применение метода линейной релаксации для построения нижних границ стоимости решений.

В третьей главе рассматриваются вопросы программной реализации разработанных алгоритмов, а также полученные экспериментальные оценки их качества. Приведено описание разработанного программного комплекса, его основные характеристики. Первый раздел третьей главы посвящен логическому моделированию программной системы уменьшения таблиц маршрутизации. Построение модели позволяет выявить основные требования, желаемую структуру и поведение системы, не вдаваясь, при этом, в детали реализации. В качестве средства графического моделирования был выбран язык UML, являющийся в настоящее время одним из наиболее эффективных средств визуального проектирования. В диссертационной работе были использованы следующие диаграммы UML, отражающие основные аспекты проектируемой системы: диаграмма вариантов использования (Use Case Diagram), диаграмма классов (Class Diagram) и диаграмма последовательности действий (Sequences Diagram).

Программная реализация была выполнена на языке С++ и скомпилирована gcc версии 3. Корректность программы обеспечивается достоверным тестированием, которое контролировалось с помощью использования утилит gcov и lcov, позволяющих определить степень покрытия кода.

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

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

Экспериментальные исследования проводились на рабочей станции с процессором Intel Pentium D 1.8 Ггц, оперативной памятью 1 Гб и операционной системой openSuse 10.3.

В качестве тестовых данных были использованы таблицы маршрутизации из нескольких крупных точек обмена интернет-трафиком -PAIX и Мае-West, полученные в рамках проекта RouteViews, а также таблица маршрутизации и файлы трассировки пакетов, предоставленные провайдером "АйПи Телеком" (г. Ульяновск).

Основные характеристики исследованных тестовых наборов приведены в таблице 3.

Таблица 3. Характеристики таблиц маршрутизации

Название Количество записей Количество функций Максимальное количество конъюнкций в отдельной ДНФ

Paix 343465 51 75532

Mae-west 308730 36 63616

Iptelecom 289490 27 78056

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

В таблицах 4 и 5 приведены результаты сравнения времени работы предлагаемых методов MINDNF_E (точный), МШО№'_Л(приближенный) и классического метода Espresso-Exact, который использовался в большинстве работ по сокращению таблиц маршрутизации. Также для сравнения был использован один из наиболее эффективных минимизаторов, использующих неявные методы обработки дискретных объектов - Rondo.

Таблица 4. Сокращение ТМ с помощью тонных алгоритмов мишшшации

Название Количество записей в сжатой ТМ Время,с

MINDNFE ESPRESSO RONDO

Paix 156348 12800 Т Т

Mae-West 148902 92.3 Т 137.5

Iptelecom 118223 6570 Т Т

Таблица 5. Время работы приближенных алгоритмов минимизации при сокращении ТМ

Название Время,с

MINDNFA ESPRESSO RONDO

Paix 14.3 Т Т

Мае-West 9.6 Т 119.2

Iptelecom 7.7 Т 98.1

При этом было введено ограничение на время работы алгоритмов, точных -8 часов, приближенных - 2 минуты, символ "Т" обозначает, что с помощью соответствующего алгоритма не было найдено решение за отведенное время. Предлагаемые точный и приближенный алгоритм позволяют существенно уменьшить время обработки ТМ по сравнению с Espresso и Rondo. Приближенный алгоритм может быть использован для обработки ТМ, обновляющихся в режиме реального времени (каждые 30-60 секунд). Отличия в качестве решения, полученного с помощью MINDNF_A от остальных приближенных алгоритмов - не более 1.5%. Количество записей в сокращенных ТМ составило для таблиц Paix, Мае-West, Iptelecom -169458, 160919, 129127 записей, соответственно.

Были смоделированы две системы маршрутизации - использующая и не использующая кэширование результатов поиска. В качестве входных данных были использованы таблица маршрутизации и файл трассировки, полученные от провайдера "АйПи Телеком" (г. Ульяновск). Суммарное количество пакетов в файлах трассировки составляло порядка 20 млн, количество уникальных IP-адресов - около 60 тыс.

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

Обобщенная схема поиска в таблице маршрутизации с использованием кэширования приведена на рисунке 3. Среднее время поиска в таблице маршрутизации TAV может быть найдено с помощью следующего соотношения

Т .„ = пТ„ 4- (1 - ■

- лу • г )-1 » У'!

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

Рисунок 3. Модель поиска с использованием кэша

Производительность маршрутизатора, использующего кэширование зависит не только от свойств таблицы маршрутизации и характеристик трафика, но и от параметров кэша, основными из которых являются: размер, ассоциативность, метод замещения записей. Для моделирования воздействия сжатия таблицы маршрутизации на количество успешных обращений к кэшу была разработана программа на языке С++, имитирующая поиск записей. Программа моделирует только полностью ассоциативный кэш - это связано, прежде всего, с тем, что данная схема кэширования дает значительное увеличение скорости поиска при обработке IP-трафика, по сравнению с технологией «-канальной ассоциативности, которая используется в микропроцессорах общего назначения15. Размер кэша в процессе эксперимента варьировался от 64 до 4096 записей. Были реализованы наиболее распространенные методы замещения записей в кэше - LRU (Least Recently Used) и LFU (Least Frequently Used).

IS Liu H. Reducing cache miss ratio for routing prefix cache // Globecom, Jan/Feb 2002, pp. 58-64.

19

Нужно отметить, что оценить увеличение скорости поиска достаточно сложно, т.к. оно зависит от используемого оборудования (скорости доступа к памяти кэша и ТМ, используемых алгоритмов поиска). В связи с этим, как правило, рассматривают упрощенную ситуацию, считая, что для кэша и таблицы маршрутизации используются одинаковые память и алгоритм поиска (бинарный поиск). При этом верхняя граница количества выполняемых операций может быть найдена с помощью следующего соотношения:

KN = plog2 с + (1 - />)log2 п, (10)

где с и п - количество записей в кэше и основной таблице маршрутизации, соответственно.

В таблице 6 приведены результаты моделирования поиска для различных размеров кэша и техник замещения элементов для исходной/сжатой таблицы маршрутизации. Наибольшее увеличение скорости поиска достигается на небольших размерах кэша (не превышающих 2048 записей). При увеличении количества записей в кэше, значительно возрастает число успешных обращений к кэшу и отличия в скорости поиска постепенно нивелируются. Среднее увеличение доли успешных обращений к кэшу составляет 0.052 и 0.058 для методов LRU и LFU, соответственно.

Таблица б. Скорость поиска при использовании кэша

Размер кэша Доля успешных обращений к кэшу (LRU) Увеличение скорости поиска(%) Доля успешных обращений к кэшу (LFU) Увеличение скорости поиска(%)

64 0.852 / 0.900 8.97 0.854 / 0.921 11.65

128 0.856 / 0.913 8.56 0.856 / 0.922 9.60

256 0.860 1 0.921 7.55 0.861 / 0.924 7.73

512 0.872 / 0.931 6.09 0.873 / 0.936 6.40

1024 0.892 / 0.949 4.81 0.892 / 0.955 5.20

2048 0.926 / 0.976 3.34 0.927 / 0.982 3.59

4096 0.963 / 0.994 1.61 0.964 / 0.993 1.52

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

пакетов построены на базе программного пакета Click Modular Router 1.7.0. Средняя скорость поиска для исходной таблицы составила 721015 пакет/с, а для сжатой - 762230 пакет/с. Таким образом, увеличение скорости поиска в результате сокращения размера таблицы маршрутизации составило 5.7 %.

Построена оценка изменения энергопотребления тернарной ассоциативной памяти в результате сокращения таблицы маршрутизации на основе модели, предложенной и программно реализованной ArpaBanoM(Agrawal) и Шервудом (Sherwood)16. Основными входными параметрами модели являются: количество битов в хранимых записях, количество записей, количество сегментов ТСАМ. Расчеты проводились для односегментной конфигурации, количество бит устанавливалось равным 32. Результаты моделирования показали, что энергопотребление модуля ТСАМ линейно зависит от количества записей; уменьшение количества записей для таблиц маршрутизации Paix, Mae-west и Iptelecom с помощью предложенного алгоритма приводит к уменьшению энергопотребления на 51%, 48% и 55.6%, соответственно. Отличие энергопотребления, вычисленного с помощью данной модели от реального энергопотребления схемы с идентичными параметрами составляет не более 10%. В качестве оценки сокращения энергопотребления целесообразно использовать нижние границы, которые составляют 38%, 41%, 45.6%, соответственно.

Заметим, что разработанный точный метод может быть использован и в задачах логического синтеза цифровых устройств. Проведено сравнение предлагаемого метода минимизации булевых функций в классе ДНФ с двумя известными минимизаторами - Espresso и Rondo. В качестве входных данных был использован набор MCNC (Microelectronics Center of North Carolina) Benchmarks, являющийся стандартом де-факто для исследования алгоритмов оптимизации цифровых устройств. Данный набор состоит из булевых функций, реализуемых реальными цифровыми схемами.

Результаты экспериментов для задач из набора MCNC Benchmarks приведены в таблице 7. Были исследованы две версии предлагаемого алгоритма MINDNF_E, отличающиеся процедурой вычисления верхних границ - в таблице им соответствуют столбцы ТСР1 (метод последовательного увеличения верхней границы) и ТСР2 (получение верхней границы на основе локального поиска ). При этом было установлено ограничение на время работы - 1 час. С помощью espresso за данное время

16 Agrawal B., Sherwood T. Ternary CAM Power and Delay Model: Extensions and Uses H IEEE Transactions on very large scale integration (VLSI) Systems, 2008, vol. 16, № 5, pp. 554-564.

не удалось найти решение ни для одной из задач. Программа Rondo не нашла решения для 4 задач, отмеченных *. Оба варианта MINDNF_E нашли решения для всех приведенных задач, при этом суммарное время, затраченное алгоритмом, использующим метод последовательного увеличения верхней границы в 1.7 раз меньше, чем у традиционного подхода.

Полученные результаты показали, что с помощью использования двоичных диаграмм решения можно компактно хранить и эффективно обрабатывать задачи большой размерности. Так, например, количество простых импликант для задачи soar составляет 330477287437440, размер же соттветствующего ZDD-представления - лишь 19541 узел. Наибольшее количество узлов в ROBDD- и ZDD-представлениях из рассмотренных примеров было достигнуто на задачах signet и mainpla, и составило 7114 и 185081 узлов, соответственно.

Таблица 7. Сравнение алгоритмов минимизации ДНФ на наборе MCNC Benchmarks

Название I О Количество простых импликант Количество Rondo MINDNF_E

строк;столбцов в матрице покрытия ТСС, с TCP,с ТСС,с ТСР1,с ТСР2,с

ех5» 8 63 2532 686;974 6.3 Т 9.3 76.55 90.94

ibm 48 17 1047948792 0;0 0.53 0 0.72 0 0

jbp 36 57 2496809 324;209 3 0.08 2.17 0.08 0.06

mainpla 27 54 87692 0;0 83.9 0 176.41 0 0

max1024* 10 6 1278 916;904 0.7 Т 0.84 216.41 400.2

misg 56 23 6499491840 0;0 0.27 0 0.34 0 0

misj 35 14 139103 0,0 0.145 0 0.17 0 0

pdc 16 40 28231 1498;1141 4.15 2.1 4.14 2.06 2.58

prom2* 9 21 2635 1524;1813 14.5 Т 17.72 10.58 54

shift 19 16 165133 0;0 1.54 0 0.53 0 0

signet 39 8 78735 0;0 6.48 0 6.41 0 0

soar* 83 94 330477287437440 22540;8927 30.8 Т 15.2 49.5 58.73

ti 47 72 836287 874;430 3.2 0.4 3.83 0.34 0.33

tslO 22 16 524281 0;0 0.5 0 0.58 0 0

x7dn 66 15 566698632 1968;664 19.2 2.3 8.55 4.72 4.63

xparc 41 73 15039 224;149 5.3 0.01 4.2 0.11 0.09

I - число входных переменных, О - число выходных переменных, 'ГСС - время построения упрощенной матрицы, TCP - время поиска минимального покрытия

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

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

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

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

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

5. Результаты компьютерного моделирования показали, что применение на практике разработанного подхода позволяет уменьшить размер реальных таблиц маршрутизации более чем в 1.9 раз, что приводит к снижению энергопотребления модулей памяти на 38-45%, а также к увеличению скорости поиска в среднем на 5.7%. Показано, что сокращение таблиц маршрутизации в маршрутизаторах, использующих кэширование, позволяет увеличить долю успешных обращений к кэшу в среднем на 5%.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях из перечня ВАК:

1. Смагин A.A., Шиготаров A.B. Метод оптимизации таблиц маршрутизации // Инфокоммуникационные технологии, Самара, 2009. -т. 7, № 3. - с. 59-62.

2. Смагин A.A., Шиготаров A.B. Применение методов минимизации булевых функций в классе дизъюнктивных нормальных форм для оптимизации цифровых устройств // Известия Самарского научного центра РАН. Самара. Изд-во Самарского научного центра РАН, 2009. -т. 11, №3(2).-с. 343-349.

В других изданиях:

3. Шиготаров A.B., Кукин Е.С. Об одном алгоритме минимизации дизъюнктивных нормальных форм // Автоматизация процессов управления - Ульяновск. ФНПЦ ОАО «НПО МАРС», 2008 №4(14) - с. 12-16.

4. Шиготаров A.B. Алгоритмы минимизации ДНФ // Ученые записки УлГУ. Серия Математика и информационные технологии / под ред. Смагина A.A. Выпуск 1. - Ульяновск, 2007. - с. 43-46.

5. Шиготаров A.B. Анализ и классификация методов сжатия таблиц маршрутизации // Техника и Технология-Москва. Изд-во Спутник-Плюс, 2009.- № 5.-е. 31-33.

6. Шиготаров A.B. Неявные алгоритмы минимизации булевых функций в классе дизъюнктивных нормальных форм // Техника и Технология,-Москва. Изд-во Спутник-Плюс, 2009. - № 5.-е. 34-36.

7. Шиготаров А. В. О некоторых методах сокращения перебора в задаче минимизации булевых функций в классе дизъюнктивных нормальных форм // Материалы Шестой Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем». - Ульяновск, 2009.-е. 91-93.

Подписано в печать 02.04.2010. Формат 60x84/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № Л&1

Отпечатано с оригинал-макета в типографии издательского центра Ульяновского государственного университета 432970, г. Ульяновск, ул. Л. Толстого, 42

Содержание.

Список сокращений.

Введение.

Глава 1. Обзор и анализ существующих методов уменьшения размера таблиц маршрутизации.

§1.1. Маршрутизация, архитектура маршрутизаторов.

§ 1.2. Обзор методов оптимизации поиска в таблицах маршрутизации.

§1.3. Методы уменьшения размера таблиц маршрутизации.

§1.4. Методы минимизации булевых функций большой размерности.

1.4.1 Классификация алгоритмов минимизации булевых функций.

1.4.2 Алгоритмические сложности решения задачи минимизации ДНФ

1.4.3 Точные алгоритмы минимизации ДНФ.

1.4.4 Приближенные алгоритмы.

Выводы.

Глава 2. Разработка метода уменьшения таблиц маршрутизации в IP-сетях.

§2.1. Метод уменьшения размера таблиц маршрутизации.

§ 2.2 Точный алгоритм минимизации булевых функций в классе ДНФ.

2.2.1 Двоичные диаграммы решения.

2.2.2 Генерация всех простых импликант булевой функции.

2.2.3 Упрощение матрицы покрытия.

2.2.4 Построение минимального покрытия.

§2.3 Приближенный алгоритм минимизации ДНФ.

Выводы.

Глава 3. Компьютерное моделирование и экспериментальная оценка разработанного метода уменьшения таблиц маршрутизации.

§3.1. Выбор средств разработки программного пакета.

§3.2 Программная реализация разработанного метода уменьшения таблиц маршрутизации.

3.2.2 Описание программного продукта.

§ 3.3 Применение разработанных методов минимизации ДНФ для уменьшения размера таблиц маршрутизации.

§ 3.4. Оценка зависимости производительности маршрутизатора от размера таблицы маршрутизации.

§ 3.5 Экспериментальная оценка эффективности предложенных алгоритмов для задач из набора MCNC Benchmarks.

Выводы.

Актуальность исследования. Неотъемлемой частью процесса построения быстродействующих сетей является разработка эффективных схем хранения и поиска записей в таблицах маршрутизации (ТМ). Одним из следствий быстрого роста Internet стало значительное увеличение размера таблиц маршрутизации. Данный факт, а также ограниченность ресурсов программного и аппаратного обеспечения, существенно затрудняют возможность их эффективной обработки. Исследователями было предложено большое количество схем для увеличения скорости поиска в таблицах маршрутизации. Алгоритмические методы включают в себя: локальный поиск, двоичный поиск, использование специальных структур данных (бинарные деревья, трие), хеширование и ряд других. Основным недостатком данных подходов является то, что они требуют нескольких обращений к памяти. Требования к производительности современных сетей являются очень высокими, в то время как время отклика современных архитектур памяти ограничивают возможное количество обращений к памяти. Одним из наиболее распространенных и перспективных аппаратных решений является тернарная ассоциативная память (ТСАМ). Главной особенностью ТСАМ является то, что адресация осуществляется на основе содержания данных, поиск нужной записи, при этом, может быть осуществлен за одно обращение к памяти. Значительное число исследований, посвященных проблеме повышения эффективности обработки таблиц маршрутизации, ориентировано на использование данной аппаратной реализации и основано на методах сжатия таблиц маршрутизации [87]. Уменьшение таблиц маршрутизации позволяет повысить скорость поиска нужной записи, использовать память меньшего размера, а также снизить энергопотребление маршрутизатора. Современное состояние дел в данной области знаний во многом основано на работах Х.Лиу (Н. Liu)[56], С. Стергиоу(S.Stergiou)[83], В. Равикумара (V. Ravikumar)[74], Р. Гуо (R.Guo) и Ж. Дельгадо-Фриаса (J.

Delgado-Frias)[45]. Отечественные авторы, например, В. Г. Олифер и Н. А. Олифер[9], внесли вклад в развитие теоретических основ проблем эффективной маршрутизации. Большинство существующих методов сжатия таблиц маршрутизации основано на сведении данной проблемы к задаче минимизации булевых функций в классе дизъюнктивных нормальных форм. При этом используются алгоритмы минимизации, которые были разработаны в первую очередь для оптимизации интегральных схем и не учитывают специфику данной задачи. В связи с этим, возможность их практического применения ограничена задачами небольшой размерности.

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

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

• анализ существующих методов сокращения таблиц маршрутизации;

• построение математической модели таблиц маршрутизации;

• разработка быстродействующих методов сокращения таблиц маршрутизации;

• экспериментальное исследование эффективности предлагаемых алгоритмов.

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

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

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

• двоичных диаграмм решения для совместной обработки импликант,

• метода ветвей и границ для ограничения перебора в пространстве возможных решений,

• двухуровневого представления импликант для повышения скорости поиска в множестве всех исходных импликант,

• эвристического алгоритма выборочной генерации простых импликант булевых функций.

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

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

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

Основные положения, выносимые на защиту

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

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

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

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

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

Личный вклад автора. Постановка задач исследования осуществлена совместно с научным руководителем А.А.Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.

Апробация работы проведена на шестой всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2009) и ежегодных научно-технических семинарах кафедры

Телекоммуникационные технологии и сети» УлГУ.

Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 - в изданиях из перечня ВАК.

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

Выводы

1. Построена логическая модель программного пакета, основанная на использовании диаграмм языка UML — диаграммы прецедентов, диаграммы классов, диаграммы последовательности действий.

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

3. Показано, что в среднем коэффициент уменьшения размера таблиц маршрутизации составляет 1.9. Сокращение таблиц маршрутизации позволяет снизить энергопотребление модулей памяти на 38-45%, а также увеличить скорость поиска в среднем на 5.7%.

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

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

Заключение

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

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

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

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

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

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

5. Результаты компьютерного моделирования показали, что применение на практике разработанного подхода позволяет уменьшить размер реальных таблиц маршрутизации более чем в 1.9 раз, что приводит к снижению энергопотребления модулей памяти на 38-45%, а также к увеличению скорости поиска в среднем на 5.7%. Показано, что сокращение таблиц маршрутизации в маршрутизаторах, использующих кэширование, позволяет увеличить долю успешных обращений к кэшу в среднем на 5%.

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

1. Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь, 1987 - 136 с.

2. Буч Г., Рамбо Д., Джекобсон И. UML. Руководство пользователя. -М.:ДМК, 2001-432 с.

3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981-366 с.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982 - 416 с.

5. Журавлев Ю.И. О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логик в одном классе алгоритмов // Докл. АН СССР, 1960, 132, № 3, с. 504—506 (РЖМат, 1961, 4А84).

6. Закревский А.Д. Логический синтез каскадных схем. Москва: Наука. 1981. 416 с.

7. Куроуз Дж., Росс К. Компьютерные сети. СПб.:Питер, 2004 - 765 с.

8. Нигматуллин Р.Г. Сложность булевых функций. М.:Наука, 1991. - 208 с.

9. Олифер В.Г., Олифер Н. А. Компьютерные сети: принципы, технологии, протоколы. СПб.:Питер, 2001 - 672 с.

10. Самофалов К.Г, Романкевич A.M. Прикладная теория цифровых автоматов. Киев "Вища школа", 1987 - 375 с.

11. П.Сапоженко А.А, Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм. // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет., М., 1987 — 68—116 с.

12. Смагин А.А., Шиготаров А.В. Метод оптимизации таблиц маршрутизации // Инфокоммуникационные технологии, Самара, 2009. -т. 7, № 3. с. 5962.

13. Страуструп Б. Дизайн и эволюция языка С++. -М.: ДМК, 2000 448 с.

14. Страуструп Б. Язык программирования С++. —СПб.:Невский диалект, 2001 -1099 с.

15. Схрейвер А. Теория линейного и целочисленного программирования : в 2-х т. — М.: Мир, 1991

16. Таненбаум Э. Компьютерные сети. СПб.:Питер, 2007 - 992 с.

17. Шиготаров А.В. Неявные алгоритмы минимизации булевых функций в классе дизъюнктивных нормальных форм // Техника и Технология-Москва. Изд-во Спутник-Плюс, 2009. № 5. - с. 34-36.

18. Шиготаров А.В. Об одном алгоритме минимизации дизъюнктивных нормальных форм // Автоматизация процессов управления — Ульяновск. ФНПЦ ОАО «НПО МАРС», 2008 №4(14) с. 12-16.

19. Яблонский С.В. Введение в дискретную математику. М.:"Высшая школа", 2003 - 384 с.

20. Ahmad S, Mahapatra R. An Efficient Approach to On-Chip Logic Minimization // IEEE Transactions on very large scale integration (VLSI) Systems, 2007, vol. 15, № 9, pp. 1040-1050.

21. Agrawal В., Sherwood T. Ternary CAM Power and Delay Model: Extensions and Uses // IEEE Transactions on very large scale integration (VLSI) Systems, 2008, vol. 16, № 5, pp. 554-564.

22. BGP Routing Table Analysis Reports, http://bgp.potaroo.net/ 25.03.2010

23. Brayton R. K. et al. Logic Minimization Algorithms for VLSI Synthesis. -Kluwer Academic Publishers, 1984 193 p.

24. The Click modular router, http://read.cs.ucla.edu/click/ 25.03.2010

25. Bryant R. A graph-based algorithms for Boolean functions manipulation // IEEE Trans.on Computers, №8 ,1986 -pp.677-691

26. Bryant R., Meinel C. Ordered Binary Decision Diagrams In Electronic Design Automation: Foundations, Applications and Innovations, www.mathematik.uni-trier.de/tf702 20.ps 25.03.2010

27. Chandra A.K., Markowsky G. On the number of prime implicants Discrete Mathematics 24(1978), pp 7-11

28. Chao H. Next generation routers // Proceedings of the IEEE, 2002, 90 (9), pp. 1518-1558.

29. Coudert O. Doing Two-Level Logic Minimization 100 Times Faster // Proc. of Symposium on Discrete Algorithms (SODA), San Francisco CA, 1995, pp. 112 -121.

30. Coudert O., Madre J. C. Implicit and incremental computation of primes and essential primes of Boolean functions // Proc.of the Design Automation Conf. (Anaheim, CA, 1992), pp 36-39.

31. Coudert O., Madre J. C. New ideas for solving covering problems // In Proc. ofthe Design Automation Conference, 1995, pp 641-645.

32. Coudert O. On Solving Covering Problems //Proc. of 33rd DAC, Las Vegas, 1996-pp. 197-202

33. Coudert O, Madre J. C., Fraisse H. A New Viewpoint on Two-Level Logic Minimization // Proc. of 30th DAC, Dallas TX, USA, 1993 pp. 625-630

34. Coudert O., Sasao T. Two-Level Logic Minimization // Logic Synthesis and Verification, S. Hassoun & T. Sasao Editors, Kluwer Academic Publishers, Chapter 1,2001 pp. 167-196

35. Czort S. The complexity of minimizing disjunctive normal form formulas. Master thesis, 1999 53 p.

36. С++ Википедия. http://ru.wikIPedia.org/wiki/C%2B%2B 25.03.2010

37. Feldmeier D. Improving gateway performance with a routing-table cache // in:Proceedings of INFOCOM, 1988, pp. 298-307.

38. Fiser P., Hlavicka J. BOOM A Heuristic Boolean Minimizer // Proc. ICCAD-2001, San Jose(USA) - pp 439-442.

39. GLPK (GNU Linear Programming Kit), http://www.gnu.org/software/glpk/ 25.03.2010

40. Goldberg E.I., Carloni L.P., Villa Т., Brayton R.K., Sangiovanni-Vincentelli A.L. Negative thinking in branch-and-bound: the case of unate covering IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000-pp. 1-16.

41. Guo R., Delgado-Frias J. G. IP Routing table compaction and sampling schemes to enhance TCAM cache performance // Journal of Systems Architecture, vol. 55,2009, pp. 61-69

42. Gupta P., Lin S., McKeown N. Routing lookups in hardware at memory access speeds // in Proceedings of InfoCom'98, San Francisco, 1998, pp. 1240-1247.

43. Hayashi Т., Miyazaki T. High-Speed Table Lookup Engine for IPv6 Longest Prefix Match // Proc. IEEE Globecom, vol. 2, IEEE Press, Piscataway, N. J.,1999.- pp. 1576-1581.

44. Kohler E. The Click modular router. PhD thesis, 2001, 127p. http://pdos.csail. mit.edu/papers/click:kohler-phd/thesis.pdf25.03.201051.1psolve project, lpsolve.sourceforge.net 25.03.2010

45. Li X.Y., Brglez F., Stallmann M.F. Effective Bounding Techniques For Solving Unate and Binate Covering Problems // Proceedings of the 42nd annual Design Automation Conference, 2005 pp 385-290.

46. Liao S., Devadas S. Solving covering problems using lpr-based lower bounds // Proc. of the 34th Design Automation Conference, 1997 pp. 117-120.

47. Liu H. Reducing Cache Miss Ratio For Routing Prefix Cache // In proc. GLOBECOM, 2002, vol. 3, pp. 2323- 2327

48. Liu H. Routing Prefix Caching in Network Processor Design // in Tenth International Conference on Computer Communications and Networks, 2001, pp. 18-23.

49. Liu H. Routing Table Compaction in Ternary-CAM // IEEE Micro, Jan/Feb 2002, pp. 58-64.

50. Lysecky R., Vahid F. On-chip logic minimization//Proc. ACM IEEE Design Automation Conference, 2003 — pp. 334-337.

51. McAuley A., Francis P. Fast Routing Table Lookup Using CAMs // Proc. IEEE Infocom, vol. 3, IEEE CS Press, Los Alamitos, Calif., 1993, pp. 13821391.

52. Meinel C., Theobald T. Algorithms and data structures in VLSI design, Springer-Verlag NY, 1998. 267 p.

53. Minato S. Calculation of Unate Cube Set Algebra Using Zero-Suppressed

54. BDDs. // Proc. of DAC , 1994, pp. 420-424.

55. Minato S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems // Proc. of 30th ACM/IEEE Design Automation Conference (DAC'93), 1993 pp. 272-277

56. Mishchenko A. EXTRA Library of the DD procedures. http://www.ee.pdx.edu/~alanmi/research/extra.htm 25.03.2010

57. Mishchenko A. An introduction to zero-suppressed binary decision diagrams // Technical report, Portland State University, June 2001 http://www.eecs.berkelev.edu/~alanmi/publications/2001/techO 1 zdd.pdf 25.03.2010

58. Mishchenko A., Perkowski M. Fast heuristic minimization of exclusive-sums-of-products // Proc. Reed-Muller Workshop, 2001, pp. 242-250.

59. Mishchenko A., Sasao T. Large-scale SOP minimization using decomposition and functional properties // Proc. DAC , 2003, pp. 149-154

60. McCluskey E. J. Minimization of Boolean functions // The Bell System Technical Journal, 1956, 35, №5, pp. 1417-1444.

61. McGeer P. et al. ESPRESSO-SIGNATURE: a new exact minimizer for logic functions // Proc. DAC, 1993 pp. 618-624

62. Nilsson S., Karlsson G. IP-Address Lookup Using LC-tries // IEEE J. Selected Areas Comm., vol. 17, no. 6, June 1999. pp. 1083-1092.

63. Null L., Lobur L. The Essentials of Computer Organization and Architecture, Second Edition, Jones and Barlett, 2006, 799 p.

64. PostgreSql Википедия. http://ru.wikIPedia.org/wiki/PostgreSOL 25.03.2010

65. Quine W. V., The problem of simplifying truth functions // Am. Math. Month. 1952, 59, pp. 521-531.

66. Quine W. V. On cores and prime implicants of truth functions. Amer. Math Monthly, 66, №9,1959. - pp. 755-760.

67. Qt- Википедия. http://ru.wikIPedia.org/wiki/Qt 25.03.2010

68. Ravikumar V. С., Bhuyan L. N., Mahapatra R. N., EaseCAM: An Energy and Storage Efficient TCAM-Based Router Architecture for IP Lookup // IEEE Transactions on Computers, vol. 54, 2005, 521-533.

69. RONDO: Two Level Sum-of-Product Minimization, http://web.cecs. pdx.edu/~alanmi/researcIx/min/rondo.exe 25.03.2010

70. Rooney, J.J. Delgado-Frias, J.G. Summerville, D.H. Associative ternary cache for IP routing // IEE Proc., Comput. Digit. Tech., 2004 vol. 151, Issue 6, pp. 409—416.

71. RouteViews Project, http://www.routeviews.org/ 25.03.2010

72. Rudell R. Multiple-valued minimization for PLA synthesis. UCB technical report M86/65, 1986.

73. Sapra S., Theobald M., Clarke E. SAT-Based Algorithms for Logic Minimization // IEEE International Conference on Computer Design, 2003, p. 510.

74. Sasao Т., Matsuura M., Iguchi Y., Nagayama S. Compact BDD Representations for MultlPle-Output Functions // VLSI-SOC, Montpellier, France, 2001, pp. 406-411.

75. Somenzi F. CUDD Package, Release 2.3.1. http://vlsi.Colorado.EDU/ -fabio/CUDD/cuddlntro.html 25.03.2010

76. Srinivasan V. and Varghese G. Fast Address Lookups Using Controlled Prefix Expansion // ACM Trans. Computer Systems, vol. 17, no. 1, Oct. 1999. pp. 1-40.

77. Stergiou S., Jain J. Optimizing Routing Tables on Systems-on-ChIP with Content-Addressable Memories //Proc. IEEE International System-on-Chip Symposium, 2008, pp 1-6.

78. Talbot В., Sherwood Т., and Lin B. Ip caching for terabit speed routers // In proc. Globecom, 1999, vol. 2, pp. 1565-1569

79. Umans C., Villa Т., Sangiovanni-Vincentelli A. Complexity of two-level logicminimization // IEEE Transactions on Computer-Aided design, 2006, pp 12301246.

80. Waldvogel M. Fast Longest Prefix Matching: Algorithms, Analysis, and Applications. PhD thesis number 13266, ETH Zurich, 2000 - 154 p.

81. Wu W. Packet Forwarding Technologies. Auerbach Publications, 2007, 4461. P

82. Zane F., Narlikar G., Basu A. CoolCAMs: Power-Efficient TCAMs for Forwarding Engines // IEEE Infocom, 2003, vol. 1, pp. 42-52.

83. Zheng К., Ни C., Liu H., Liu B. An ultra high throughput and power efficient TCAM-based IP lookup engine // INFOCOM, 2004, vol. 3., pp. 19841994.