Построение маршрута при групповой рассылке сетевых пакетов данных

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Государственный университет информатики и искусственного интеллекта

Д080403.1.01.03/056.НР

Кафедра программного обеспечения

интеллектуальных систем

ОТЧЕТ О НИРС

Тема: «Построение маршрута при групповой рассылке сетевых пакетов данных»

Руководитель:

___________ доц. А.И. Ольшевский

(дата, подпись)

Нормоконтроль:

___________ асс. Е.В. Курило

(дата, подпись)

Разработал:

___________ ст.гр. ПО-03м Л.В. Карпенко

(дата, подпись)

2008

РЕФЕРАТ

Отчет о НИРС: 39 с., 3 таблицы, 14 рисунков, 6 источников.

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

Цель – разработка алгоритма построения маршрута для дальнейшего теоретического и практического его применения, а также написание программного продукта как реализации алгоритма.

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

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

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

СЕТЬ, РЕГИОНАЛЬНЫЕ ЦЕНТРЫ, ДЕРЕВЬЯ ШТЕЙНЕРА, ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ, СТРУКТУРЫ ДАННЫХ

ВВЕДЕНИЕ

В настоящее время наиболее эффективным и перспективным методом обучения является дистанционное обучение (ДО). Широкое распространение персональных компьютеров и активное развитие глобальных сетей (ГС) вывело этот процесс на принципиально новый уровень. Теперь получить образование можно независимо от места жительства и физических возможностей. Дистанционное образование позволяет получить диплом любого ВУЗа, любой специальности.

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

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

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

Для постоянного пересчета путей ищут алгоритмы их построения. Одним из способов построения является использование деревьев Штейнера (ДШ). Эта задача имеет множество способов решения. В данной работе предлагается решать ее с помощью генетических алгоритмов (ГА).

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

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

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

1 ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

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

Разрабатываемый алгоритм делится на две части. На первом этапе построения сеть разбивается на подсети по числу региональных учебных филиалов. Это позволит снизить нагрузку по рассылке с центрального учебного центра. Каждая подсеть объединятся вокруг своего регионального центра (РЦ). Этот процесс сродни задаче разделения объектов на классы. Абонент приписывается к определенному центру на основании экономической целесообразности (стоимости его связи с данным центром).

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

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

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

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

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

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

2 МЕТОДЫ СИНТЕЗА СТРУКТУРЫ СЕТИ

 

2.1 Размещение центров и синтез абонентских СДО в классе радиальных структур

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

2.1.1 Метод ветвей и границ

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

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

где к — номер итерации.

Каждое из подмножеств  характеризуется следующими множествами: — множество пунктов, где РЦ уже построены;  — множество пунктов, где еще можно строить РЦ;  — множество пунктов, где наложен запрет на строительство РЦ, при этом

где Y — исходное множество пунктов, в которых допускается строительство РЦ, Y Є Х.

Обозначим через Xyi множество абонентов, подключенных к РЦ уi (у Є Р) по критерию минимума затрат на связь, т. е. х Є Хуi, если . Каждое из множеств  характеризуется величиной нижней границы критерия  для всех структур (решений), определяемых данным множеством. Величина ξ задается следующим соотношением:

где .

Допустим, что каким-то приближенным методом (например, R-структур) удается построить структуру Х0 на множестве . При этом в решение должны войти все РЦ уi Є  и не должно быть ни одного РЦ уi Є .

Обозначим величину критерия для структуры Х0 через W(Х0). Справедлив следующий признак оптимальности: если W(Х0) = , то вершина дерева решений  является конечной и дальнейшему разбиению не подлежит; если W(Х0) ≤ min  для всех висячих вершин  построенных на k-й итерации, то Х0 — искомое оптимальное решение (структура). Предположим, что уже проведено k итераций и еще не найдено оптимальное решение. Опишем произвольную (k + 1)-ю итерацию:

1.Среди всех множеств , построенных в результате k-й итерации, выбираем наиболее перспективное множество , т. е. такое, что

.

2.Ветвление. Выбираем некоторый РЦ yr Є  и разбиваем на два подмножества  и  так, что на подмножестве  РЦ yr, переводится в разряд действующих, а на подмножестве  накладывается запрет на строительство РЦ в пункте уr. Таким образом,

Будем выбирать уr так, чтобы подмножество  с наибольшей вероятностью содержало искомое решение, а не содержало. Тогда

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

4.На каждом из подмножеств  и  находим допустимое решение, которое обозначим  и  соответственно.

5. Проверка признака оптимальности. Пусть  ≤ . Если

где {} — множество висячих вершин на k-й итерации, то  — искомое решение и конец работы алгоритма. В противном случае переходим на (k+2)-ю итерацию, переобозначив для всех висячих вершин

Весь процесс решения реализуется в виде некоторого дерева вариантов.

Как показывают проведенные исследования, реализация метода ветвей и границ для структурного синтеза сетей ЭВМ требует больших вычислительных затрат уже при числе возможных пунктов размещения РЦ т ≥ 40. Поэтому основная область применения точных методов для структурного синтеза и оптимизации — это проверка асимптотической эффективности приближенных методов и степени близости получаемых решений к оптимальным. В связи с этим основное внимание в книге уделено приближенным инженерным методам проектирования структур сетей ЭВМ и систем передачи данных, представляющих наибольший интерес для проектировщиков.

2.1.2 Алгоритм R-структур для синтеза абонентских СДО

Пусть необходимо решить задачу при определенных ограничениях. Следует определить пункты размещения РЦ и множество абонентов Хy , привязанных к РЦ.

Рассмотрим эвристический алгоритм решения указанной задачи (алгоритм R-структур), позволяющий за сравнительно небольшое число шагов найти субоптимальное решение. Алгоритм состоит из предварительного этапа и не более, чем N — 1 итераций, где N — число узлов.

Предварительный этап. 1. Находим для каждого yi множество абонентов Хyi, подключенных к нему радиальными КС по критерию минимума затрат на связь: х Є Хуi если

2. Определяем суммарный объем ИВР, выполняемых ВЦy

Рис 2.1 – Дерево решений при синтезе структуры методом ветвей и границ

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

Рассмотрим (k+1)-ю итерацию. Пусть в результате k итераций определено множество наиболее целесообразных мест размещения ВЦ у (k) и найдены привязки , а соответствующее этому решению значение критерия Wk определяется формулой.