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

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

КОЛОСОВ Дмитрий Эдуардович

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

специальность 05.13.13 - Телекоммуникационные системы и компьютерные сети

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

Москва, 2005

Работа выполнена в Федеральном государственном учреждении «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций» (ГНИИ ИТТ «Информика»), г Москва

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

Иванников Александр Дмитриевич

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

Саксонов Евгений Александрович кандидат технических наук, доцент Старых Владимир Александрович

Ведущая организация - Санкт-Петербургский государственный институт точной механики и оптики (технический университет, СПбГИТМО)

Защита диссертации состоится 22 ноября 2005 года в 10 часов на заседании диссертационного совета Д 212 133 03 в Московском государственном институте электроники и математики (техническом университете) по адресу 109028, Москва, Б Трехсвятительский пер , д.1-3/12, стр 8

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технического университета)

Автореферат разослан 12 октября 2005 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

Ю Л. Леохин

15Ы2

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Основными российскими некоммерческими 1Р-сетями, специализирующихся на обслуживании организаций науки, образования, культуры и здравоохранения, являются сети 1Ш>ШЕТ, ШЗпй, ЯЕЬАКМ-1Р, МЯШе! и ряд других. Существующая межведомственная опорная сетевая структура обеспечивает техническую интеграцию всех научно-образовательных сетей, вне зависимости от их ведомственной принадлежности и предметной ориентации, в единую национальную компьютерную сеть науки и высшей школы Данная инфраструктура в настоящее время имеет точки присутствия в 55 субъектах Российской Федерации, использует ряд общих магистральных каналов, и интегрирована в глобальной Интернет-системе международных каналов, общая емкость которых в настоящий момент превышает 2 Гбит/с.

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

Для повышения

научно-

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

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

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

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

В решение задачи анализа и синтеза сетей значительный вклад внесли отечественные и зарубежные ученые Альнах И.Н., Артамонов Г.Т., Брехов О.М., Васильев В Н., Вишневский В.М., Гарсиа-Диас А., Зайченко Ю.П., Захаров Г.П., Ижванов Ю.Л., Клейнрок Л., Куракин Д.В., Мизин. И.А., Саксонов Е.А., Самойленко С.И., Тихонов А.Н., Филлипс Д., Ху Т., Янбых Г.Ф. и др.

Объект исследования. Объектом исследования являются научно-образовательные ЕР-сети.

. • 1 м» -

♦ Ч < . ' ' ..

•и 1 4

»Я» -¡I г-

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

Цель исследования. Целью диссертационной работы является:

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

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

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

1) исследование существующих способов описания и построения топологий телекоммуникационных сетей, способов выбора мест размещения на них информационных ресурсов;

2) обоснование использования суммарного потока как критерия при оптимизации размещения информационных ресурсов;

3) размещение одного и множества информационных ресурсов в сети по критерию минимума суммарного потока без ограничений и при существовании количественных и структурных ограничений;

4) размещение информационных ресурсов при возможности их копирования;

5) размещение информационных ресурсов, минимизирующее суммарный поток на заданном подмножестве линий связи;

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

Научная новизна и положения, выносимые на защиту Научная новизна состоит в следующем:

1) предложены модели и алгоритмы размещения информационных ресурсов в телекоммуникационных сетях по критерию минимума суммарного потока в линиях связи;

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

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

4) разработан алгоритм поиска оптимальных маршрутов в условиях изменяющейся метрики графа;

3) разработан алгоритм уменьшения разрядности задачи поиска

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

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

б

работы на ряде международных и всероссийских конференций.

Апробация результатов диссертации. Результаты данной работы докладывались на всероссийской научно - методической конференции «Телематика-2005» (Санкт-Петербург, 2005 г.), на всероссийских семинарах «Интернет-порталы: содержание и технологии» (Москва, 20032005 г г.), международных конференциях по дистанционному образованию (Москва, 1998-1999 г.г.).

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

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

Результаты работы внедрены в ГНИИИТТ «Информика» (г.Москва) с целью повышения эффективности функционирования сети RUNNet.

Структура и объём диссертации. Диссертация состоит из введения, пяти глав и заключения и списка литературы. Диссертация содержит 155 страниц, список литературы состоит из 103 наименований.

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

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

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

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

Проведен анализ алгоритмов маршрутизации по способу определения

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

На основании проведенного анализа сформулирована постановка задачи диссертации.

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

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

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

• Второй подход, применяемый для проектирования топологий телекоммуникационных и вычислительных сетей, основан на анализе мест расположения узлов и информационных потоков между узлами. Такой подход реализован в известных методах Майеды-Цзяня, Гомори-Ху, Клейнрока.

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

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

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

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

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

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

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

2) узел, содержащий ресурс, не является соседом потребителя. В этом случае поток создается в каждой линии связи пути, соединяющим

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

Если 1 вершина возбуждает при доступе к информационному ресурсу поток С,, то определить сумму потоков на всех ребрах пути от ¡-вершины до места нахождения ресурса можно как Л, = ЯС,, где Б, - длина пути (расстояние) между ¡-вершиной и местом расположения ресурса. Очевидно, что является функцией матрицы смежности графа топологии сети.

Вектор суммарных потоков сети в зависимости от места расположения информационного ресурса определится как

512 .. ..

^21 $22 " • ^2N

>N1 $N2 ■■ ■■

СН

с21

С* л

где N1- количество узлов в сети.

Таким образом, задача поиска узла для расположения информационного ресурса по критерию минимума суммарного в сети сводится к определению номера минимального элемента вектора Р. Описанный алгоритм имеет сложность 0(Ы3).

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

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

0(Ы3Т).

(

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

Ю

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

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

Эта задача сводится к задаче о размещении множества ресурсов следующим образом. Будем рассматривать каждую копию ресурса как самостоятельный ресурс. В этом случае количество столбцов Ь матрицы V определяется как Т 1=1

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

• количественные ограничения. Такого вида ограничения возникают из необходимости учета технических особенностей узлов, таких как максимальный объем ресурсов, размещаемых на них;

• структурные ограничения. Эти ограничения возникают из-за необходимости получения решений по распределению ресурсов, обладающих определенными структурными свойствами. Например, необходимо, чтобы каждый из \ ресурсов размещался ровно на М узлах (из соображений отказоустойчивости и живучести) и на каждом N узлов размещалось ровно И, ресурсов.

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

11

которой разработаны эффективные методы, в частности алгоритм Балаша.

Для решения задачи со структурными ограничениями сформулирована и решена частная задача о назначениях.

Пусть отношение таково, что каждому элементу ai еА необходимо сопоставить ровно S, элементов множества В, а каждый Ь, еВ должен быть сопоставлен ровно г, элементам из А и при этом минимизируется линейная форма N М

F = £ Z4*11 V« => min, где v-стоимость , установления отношения i=ij=i

между i элементом из А и j элементом из В , а Ту 6 {0,1}определяет

матрицу отношения (1-i элемент А поставлен в соответствие j элементу из В и 0 - в противном случае).

Эта задача обобщает задачу о назначениях, поскольку при s, = г, =1 получаем задачу о назначениях.

Показано, что бинарные матрицы, имеющие требуемую структуру , составляют Um,n(R,S) класс Райзера. На основании известных теорем неотрицательных матриц разработан алгоритм проверки непустоты Um'n(R,S) класса Райзера и алгоритм решения обобщенной задачи о назначениях, использующий свойства операции замены на матрицах класса Райзера.

Процесс создания любой сети имеет собственную историю. Как

правило, сеть создается не целиком, а отдельными фрагментами, часто

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

информации возникает ситуация, когда отдельные фрагменты сети

существенно ограничивают ее производительность из-за низкой

пропускной способности каналов связи, причем их замена оказывается

невозможной по экономическим соображениям. В такой ситуации

нежелательные последствия можно снизить за счет перераспределения

информационных ресурсов в сети с целью минимизации потока на

12

некотором ребре или множестве ребер (множестве линий связи).

На основании теоремы Радо-Эдмонса показано, что существует жадный алгоритм решения этой задачи.

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

Матрицей путей для Сребра назовем квадратную матрицу XV размерности К, где N - число узлов сети, такую что

1, если путь из вершины г в вершину у происходит через ребро / О-в противном случае.

Примем по определению, что =0.

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

Если V - матрица потоков между информационными ресурсами и вершинами сети, то F=WV содержит потоки в I - ребре сети возникающие при размещении 1 ресурса в j вершину. В случае отсутствия дополнительных ограничений решение задачи сводится к определению минимального элемента в каждой строке матрицы Б и составлению вектора решения Я из индексов минимальных элементов строк. Координата ъ этого вектора дает номер вершины, в которую необходимо поместить информационный ресурс г. В том случае, если минимальному значению соответствуют несколько индексов, координата вектора является множеством, включающим все такие индексы. Тогда получим множество решений, состоящее из всех возможных комбинаций

*

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

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

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

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

Представим сеть в виде неориентированного взвешенного связного графа где V - множество вершин, ||У||=п,Е - множество ребер,

XV — множество весов ребер. Элементы множества Е будем обозначать через еч при условии, что это ребро инцидентно вершинам V, и у. Для у5,у1 е V положим сКУ3,у() равным весу наименьшего по весу пути из V, в V,. Пусть тг81 есть путь из у8 в у4 с весом ¿(у8,у() при условии, что такой путь

существует. Полагаем длину пути равной сумме весов ребер, его образующих. Для А^З с У(/\В)- задача отыскания кратчайшего пути заключается в определении самого короткого маршрута из V, в у( для

каждой вершины уг е В и у, е А. Задача считается хорошо определенной, *

если выполняются следующие предположения:

1) Для каждой вершины у,еАиу(еВ существует путь из у3 в у^.

2) Никакой путь из у, в V,, не содержит контур отрицательной длины.

Обозначим — вес ребра, соединяющего вершины у, и V]; п\Уд — новое значение веса, полученное в результате изменения значения метрики

линии связи Вершина V) располагается ниже по иерархии дерева кратчайших путей относительно V,.

Будем называть путем Як совокупность подмножества У<ук) вершин, через которые проходит кратчайший путь до вершины V|l из исходной вершины у3 и подмножества Е^' сЕ ребер, составляющих этот путь.

Назовем - деревом Т^ совокупность подмножества

е V состоящего из всех вершин, кратчайшие пути до которых из

исходной вершины содержат вершину V* и подмножества Е^^сЕ ребер, составляющих зги пути после ук при движении от вершины у*

Множество ребер дерева Ет - множество ребер дерева Та для графа в. Для заданного графа в, согласно свойству дерева, мощность

| Ет1 множества Ег определяется как I Е}= I VI - 1.

Множество ребер замены для дерева Ей - множество ребер графа в, не вошедших в дерево Та.

Для решения поставленной задачи сформулированы следующие теоремы.

Теорема 4 1. Если пм/1р>м>ч и еч е Ег, то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин .

Теорема 4.2. Если и еыеЕт, то без изменения останутся

кратчайшие пути для вершин множества уерУ®а для вершин множества У^0 неизменными останутся и оценки длин кратчайших путей.

Теорема 4.3. Если ли^и^ и еы$.Ет, то исходное дерево кратчайших путей и оценки длин путей всех вершин не изменятся.

Теорема 4.4. Если и е,^Ет, то без изменения останутся

кратчайшие пути и оценки их длин для вершин множества У^'К

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

15

Верхняя оценка трудоемкости разработанного алгоритма равна соответствующей оценке алгоритма Беллмана-Форда. Нижняя оценка не зависит от размерности задачи.

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

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

Будем называть такие переходы парными переходами и обозначать е — е.. .

Маршрутная степень вершины число неповторяющихся ребер

еч еЕ, инцидентных вершине V,, через каждое из которых можно построить простой путь между вершинами V, и V,.

Теорема 4.5. Для любого ребра ечеЕт , инцидентного некоторым вершинам V, и V, маршрутные степени которых больше единицы, при заданной конфигурации графа, неизменных весах других ребер существует такое значение веса что при м>и > ребро еК1 становится ребром замены и переходит во множество £/?. Величину будем называть точкой вхождения в дерево для ребра е1].

Отношение парного перехода г,— отношение соответствия элемента еы множества Ет элементу екр множества Е& такое, что при увеличении веса ребра е^ так, что > я',) имеет место парный переход е,1 - е„р.

Теорема 4.6. Для любого ребра г^еЕт, находящегося в отношении

парного перехода с некоторым ребром е^ еЕт с заданной точкой вхождения

16

в дерево , существует такое значение веса р, что при и^ р < ребро вк,р становится веткой дерева Т& и переходит во множество Ет-

Теорема 4.7. Для элементов парного отношения г„ е,у еЕ, и е^реЕг при известной точке вхождения в дерево и м>'кр справедливо, что

Следствие 4.1. Если для элементов парного отношения г„ е^еЕт и екр еЕц, соответствующих весов мгч и м>^р при известной точке вхождения в дерево \»[р изменился вес ребра еч до значения то и

Следствие 4.2. Если для элементов парного отношения г„ еч е£> и вк,р еЕц, соответствующих весов и м>кр при известной точке вхождения в дерево и>1Р изменился вес ребра екр на значения «ъ, то

Теорема 4.8. Ребра еыеЕт и е^еЕя, находящиеся в одном отношении г, еЯ, инцидентны одной и той же вершине v, при условии, что v, является листом дерева кратчайших путей.

Во множестве Яд можно выделить 2 подмножества.

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

Множество непарных ребер Ер- это такое подмножество множества Ер, элементы-ребра которого не участвуют ни в одном отношении из множества Я. 4

В общем случае множество ЕР может быть пустым ^^О. Множество Е, будет пустым только при условии, что исходный связный граф С является деревом, и задача поиска кратчайших путей в этом случае лишена смысла.

Теорема 4.9 Для любого ребра еи еЕ$, инцидентного некоторым

вершинам v, и v,, маршрутные степени которых больше двух, при заданной конфигурации графа, неизменных весах других ребер существует такое значение веса wf j, что при w > w^ ребро еч становится непарным ребром и переходит во множество Ер.

Величину wkp будем называть точкой вхождения во множество замены для ребра е^

Теорема 4.10 Для любого ребра eveEs, инцидентного некоторым вершинам vi и vj, маршрутные степени которых больше двух, при заданной конфигурации графа, неизменных весах других ребер существует такое ребро екр еЕр и такое значение его веса wkp, что при wkp < wskp

ребро екр становится ребром замены и переходит во множество Е$-

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

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

На имитационной модели исследовано поведение сети с наилучшим и наихудшим местами размещения. В качестве среды моделирования использовался язык GPSS/PC (General Purpose Simulation System).

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

оптимального размещения информационного ресурса.

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

2 1

О

О 5 10 15 20 25 30 35

Коэффициент увеличения потока к

Рис. 1 Зависимость среднего времени задержки от коэффициента увеличения потока.

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

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

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

При этом решены следующие задачи:

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

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

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

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

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

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

1 Д.Э Колосов "К вопросу оптимизации географического размещения информационных ресурсов", всероссийская научно-методическая конференция «Телематика-2005», том 1, с 268-269, 2005.

2 М А. Шахраманьян, Э.Г. Мирмович, Д.Э. Колосов, В.Л. Рыжов «Концепция отраслевой системы дистанционного обучения МЧС России», Международный симпозиум «Комплексная безопасность России -исследования, управление, опыт», с.222-224., М.: ИИЦ ВНИИ ГОЧС, 2002.

3 Д.Э Колосов «Электронные учебники и библиотеки в федеральной целевой программе «Развитие единой образовательной информационной среды (2001-2005 годы)», «Материалы 2-ой Всероссийской конференции «Электронные учебники и электронные библиотеки в открытом образовании», с. 245-249, М.: МЭСИ, 2001.

4 В А. Каймин, Д Э. Колосов «О международных стандартах образования в области информатики» «Материалы 7-ой Международной конференции по дистанционному образованию», с. 149-152 М: МЭСИ, 1999.

5 В.А. Каймин, Д Э. Колосов «О международных и национальных стандартах образования в области информатики» «Материалы 4-ой Международной конференции по дистанционному образованию», с. 94-98, М.: МЭСИ, 1997.

Отпечатано в типографии ГУ ЦИСН Минобрнауки России Адрес: 125009, Москва, Брюсов пер., 21, стр. 1 Формат 60x84/16 Объем 1,25 печ. л. Тираж 90 экз. Заказ № 7835

#18388

РНБ Русский фон

2006-4 15072

стр.

Введение

Глава 1. Проблемы размещения информации и маршрутизации в научно-образовательных сетях

1.1. Российские научно-образовательные сети

1.2. Проблема оптимального размещения информационных ресурсов в научно-образовательных сетях

1.3. Принципы маршрутизации в телекоммуникационных сетях

1.4. Постановка задачи

Глава 2 Анализ методов описаний топологий телекоммуникационных сетей с точки зрения их использования для оптимального размещения информационных ресурсов

2.1 Основные топологические характеристики сетей

2.2 Характеристики типовых топологий сетей

2.3 Методы построения топологий

2.4 Методы размещения информационных ресурсов

2.5 Выводы

Глава 3 Методы размещения информационных ресурсов в телекоммуникационных образовательных сетях

3.1 Оптимальное размещение информационных ресурсов в сети

3.2 Выбор критерия оптимизации

3.3 Оптимальное размещение информационного ресурса в сети

3.4 Оптимальное размещение множества информационных ресурсов в сети

3.5 Оптимальное размещение информационных ресурсов с копированием

3.6 Обобщение задачи о назначениях

3.7 Минимизация суммарного потока на заданном множестве ребер сети за счет размещения информационных ресурсов

3.8 Определение пропускных способностей каналов связи сбалансированных сетей 82 3.9. Выводы

Глава 4. Методы корректировки маршрутов в телекоммуникационных сетях

4.1. Задача поиска кратчайших маршрутов

4.2.Алгоритм уменьшения размерности задачи поиска кратчайших путей

4.3. Алгоритм парных переходов

4.4. Выводы

Глава 5 Экспериментальная проверка предлагаемых решений

5.1. Алгоритмы размещения информационных ресурсов

5.2. Имитационная система для проверки алгоритмов поиска кратчайших путей в графе 140 Заключение 146 Список использованных источников

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

Основными российскими некоммерческими 1Р-сетями, специализирующихся на обслуживании организаций науки, образования, культуры и здравоохранения, являются сети КЦЫЫЕТ, ИВпе!, ЯЕЬАШчМР, МБШег и ряд других. Существующая межведомственная опорная сетевая структура обеспечивает техническую интеграцию всех научно-образовательных сетей, вне зависимости от их ведомственной принадлежности и предметной ориентации, в единую национальную компьютерную сеть науки и высшей школы. Данная инфраструктура в настоящее время имеет точки присутствия в 55 субъектах Российской Федерации, использует ряд общих магистральных каналов, и интегрирована в глобальной Интернет-системе международных каналов, общая емкость которых в настоящий момент превышает 2 Гбит/с.

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

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

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

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

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

В решение задачи анализа и синтеза сетей значительный вклад внесли отечественные и зарубежные ученые Альнах И.Н., Артамонов Г.Т., Брехов О.М., Васильев В.Н., Вишневский В.М., Гарсиа-Диас А., Зайченко Ю.П., Захаров Г.П., Ижванов Ю.Л., Клейнрок Л., Куракин Д.В., Мизин И.А., Саксонов Е.А., Самойленко С.И., Тихонов А.Н., Филлипс Д., Ху Т., Янбых Г.Ф. и др.

Объект исследования. Объектом исследования являются научно-образовательные 1Р-сети.

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

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

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

1) исследование существующих способов описания и построения топологий телекоммуникационных сетей, способов выбора мест размещения на них информационных ресурсов;

2) обоснование использования суммарного потока как критерия при оптимизации размещения информационных ресурсов;

3) размещение одного и множества информационных ресурсов в сети по критерию минимума суммарного потока без ограничений и при существовании количественных и структурных ограничений;

4) размещение информационных ресурсов при возможности их копирования;

5) размещение информационных ресурсов, минимизирующее суммарный поток на заданном подмножестве линий связи;

6) поиск оптимальных маршрутов при изменении значения метрики линий связи, с учетом ее использования в дереве кратчайших путей.

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

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

Научная новизна состоит в следующем:

• предложены модели и алгоритмы размещения информационных ресурсов в телекоммуникационных сетях по критерию минимума суммарного потока в линиях связи; * i

• предложены модели и алгоритмы размещения информационных ресурсов в сетях по критерию минимума суммарного потока на произвольном подмножестве линий связи;

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

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

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

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

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

Апробация результатов диссертации. Результаты данной работы докладывались на всероссийской научно - методической конференции «Телематика-2005» (Санкт-Петербург, 2005 г.), на всероссийских семинарах

Интернет-порталы: содержание и технологии» (Москва, 2003-2005 г.г.), международных конференциях по дистанционному образованию (Москва, 1998-1999 г.г.).

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

Структура и объём диссертации. Диссертация состоит из введения, пяти глав и заключения и списка литературы. Диссертация содержит 155 страниц, список литературы состоит из 103 наименований.

Результаты работы внедрены в ГНИИИТТ «Информика» (г.Москва) с целью повышения эффективности функционирования сети Я1ЛЧЫе1.

Заключение

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

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

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

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

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

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

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

1. Абасов A.M. Оптимизация размещения информационных баз с копиями в сети ЭВМ //Автоматика и вычислительная техника. 1988. - №4. - С. 71-75.

2. Александров П.С. Введение в теорию множеств и общую топологию. -М.: Наука, 1977.-367 с.

3. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред. М.: Радио и связь, 1985. 192 с.

4. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. - 248 с.

5. Балаш Э. Аддитивный алгоритм для решения задач линейного программирования с переменными, принимающими значения 0 или 1. /Кибернетический сборник. Новая серия. М.: Мир, 1969, выпуск 6. - С. 217263.

6. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. - 366 с.

7. Бернер Л.И., Гармаш В.Б., Левин М.Ш., Антропов М.В. Формирование допустимых вариантов иерархической системы управления на стадии проектирования // Проблемы и методы принятия решений: Сб. трудов. -М.: ВНИИСИ, 1985.-С. 62-72.

8. Бернер Л.И., Собкин Б.Л. Автоматизированное распределение ресурсов многомашинных вычислительных систем //Приборы и системы управления. -1992. -№5.-С. 5-8.

9. Видименко В.П. О критериальной оценке сетевых топологий //Автоматика и вычислительная техника. 1988. - №4. - С. 31-37.

10. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

11. Вишняков В.А., Герман О.В. Модель распределения информационно-связанных задач в системах проектирования и управления //Автоматика и вычислительная техника. 1983. - №5. - С. 14-18.

12. Горбатов В.А. Фундаментальные основы дискретной математики. -М.: физматлит., 1999. 544с.

13. Егоров A.B. Оптимизация сетей передачи дискретной информации на основе графовых и автоматных имитационных моделей: Автореф. дис. канд. тех. наук.- Таганрог, 1983. 16 с.

14. Зайченко Ю.П., Гонда Ю.В. Структурная оптимизация сетей ЭВМ. -Киев: Техника, 1986. 167 с.

15. Ильин A.C., Скориков Г.Я. Эффективность структур вычислительных систем //Электронное моделирование. 1988. - №6. - С. 37-42.

16. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.600с.

17. Клейнрок Л. Коммуникационные сети. М.: Наука, 1970.- 256 с.

18. Кристофидес Н. Теория графов, алгоритмический подход. М.: Мир, 1978.-432 с.

19. Кузнецов Н.Ю., Шумская A.A., Горлач С.П. Об одном подходе к построению оценок эффективности работы многопроцессорных систем //Кибернетика. 1983. - №6. - С. 45-49.

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

21. Майеда В. Матрицы заключительных мощностей и матрицы пропускных способностей ветвей //Кибернетический сборник, №9. М.: Мир, 1964. -С. 142- 166.

22. Маркин М.П. Сравнительный анализ основных технико-экономических показателей коммуникационных сред, применяемых при построении многопроцессорных систем //Вопросы радиоэлектроники, Серия ЭВТ. вып. 6. - 1990. - С. 19-24.

23. Мартин Д. Системный анализ передачи данных. Т.2. Проектирование систем передачи данных. М.: Мир, 1975. - 432 с.

24. Мельников О.В., Ремесленников В.А., Романьков В.А. и др. Общая алгебра. Т. 1. М.: Наука, 1990. - 592 с.

25. Мизин И.А., Уринсон Л.С., Хроменшин Г.К. Передача информации с коммутацией сообщений. М.: Связь, 1972- 319с.

26. Новиков С.А. Дискретная математика для программистов. СПб: Питер, 2000.-304с.

27. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд. МГТУ им. Н.Э. Баумана, 2002. - 744с.

28. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир. 1974.-520с.

29. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж,1999.

30. Корнеев В.В., Монахов О.Г. Графы межмашинных связей однородных вычислительных систем // Изв. А.Н. СССР, Техн. кибернетика, 1980, №2, с. 195.

31. Монахов О.Г. Параметрическое описание структур однородных вычислительных систем //Вычислительные системы: Сб. научн. тр. Новосибирск: институт математики СО АН СССР. - 1979. - Вып. 80. - С. 3.

32. Монахов О.Г., Монахова Э.А. Исследование топологических свойств регулярных параметрически описываемых структур вычислительных систем // Автометрия. 2000. - №2. - С. 70-82.

33. Назарук А.И., Путятин В.Б. Об оценке эффективности архитектуры специальной вычислительной системы //Электронное моделирование. -1985.-т. 7.- №2.-С. 26-27.

34. Нечепуренко М.И. Модели структурного резервирования систем/ Прикладные задачи на графах и сетях: Сб. научн. тр. Новосибирск, 1981. - С. 57-86.

35. Нильсон Н. Искусственный интеллект. М.: Мир, 1973. - 270 с.

36. Пархоменко П.П. Размещение копий ресурсов вычислительных систем на графах общего вида //Автоматика и телемеханика. 1999. - №6. - С. 158-167.

37. Пархоменко П.П. Размещение копий ресурсов на графах, моделирующих структуры вычислительных систем //Автоматика и телемеханика. -1997.-№5.-С. 181-194.

38. Петерсон Э.Я., Плоткина T.JI. Симметрия и энтропия в задачи оптимизации распределения файлов //Автоматика и вычислительная техника. -1983.-№5.-С. 7-13.

39. Печурин Н.К., Печеник Н.В., Кондратова Л.П. Анализ устойчивости регулярной топологии базовой сети передачи данных // Проблемы управления и информатики. 2000. - №2. С. 126-129.

40. Методы оптимизации структур зоновых сетей связи/ Попков В.К., Кауль С.Б., Нечепуренко М.И. и др.; отв. ред. Алексеев A.C. Новосибирск, 1983.-181 с.

41. Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. -М.:ТВП,2000.-448с.

42. Сергиенко И.В., Каспишская М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981. - 287 с.

43. Систолические структуры/ Под ред. У.Мура, Э.Маккейба, Р.Уркхарта. -М.: Радио и связь, 1993. 416 с.

44. Скибенко И.Т., Селимов Н.М. Исследование структур вычислительных систем комбинаторно-групповыми методами //Однородные вычислительные системы из микро-ЭВМ: Сб. научн. тр. Новосибирск: Институт математики СО АН СССР. - 1983. - Вып. 97. - С. 143-153.

45. Сравнение различных одномашинных микропроцессорных архитектур по их производительности //Экспресс-информация. Серия Вычислительная техника. - М.: ВИНИТИ. - 1983. - №40. - с. 10-16.

46. Торопов В.Н. Оптимизация размещения программных модулей и их копий в вычислительной системе/ /Известия вузов. Приборостроение. -1993.-№2.- С. 63-67.

47. Цвиркун А.Д. Основы синтеза сложных систем. М.: Наука, 1982.200с.

48. Цзянь Р.Т. Синтез сетей связи // Кибернетический сборник. №9. -1964.-С. 167-189.

49. Эффективность коммуникационных устройств многопроцессорных вычислительных систем // Экспресс-информация. Серия Вычислительная техника. - М.: ВИНИТИ. - 1983. - №35. - С. 6-12.

50. Янбых Г.Ф., Столяров Б.А. Оптимизация информационно-вычислительных сетей. М.: Радио и связь, 1987. - 231 с.

51. Янбых Г.Ф., Эттингер Б.Я. Методы анализа и синтеза сетей ЭВМ. Л.: Энергия, 1980.-96 с.

52. Banerjee P., Peerce М. Design and evaluation of hardware strategies for reconfiguring hypercubes and meshes under faults// Trans, on Сотр. July 1994. V. 43. №7. P. 841-848.

53. Chen H.-L., Tzeng N.-F. Efficient resource placement in hypercubes using multiple-adjacency codes// IEEE Trans, on Сотр. Jan. 1994. V. 43. № 1. P.23.

54. Reddy A.N., Banerjee P., Abraham S.G. I/O embedding in hypercubes //Proc. 17th Int. Conf. Parallel Processing, St. Charles, IL. Ang. 15-19. 1988. P. 331338.

55. Bermond J.C., Cornelias F., Distributed loop computer network: a survey // Journ. Parallel Distributed Comput/ 1995, 24, p.2.

56. Preparata F.P., Vnillemin J. The cube connected cycles: a versatile network for parallel computation // Commun. ACT. 1981. p. 300.

57. Arden B.W., Lee H. Analysis of chordal ring network // IEEE Trans. Comput. 1981, c-30, p. 291.

58. Интернет порталы: содержание и технологии. Сб. научных статей. Вып. 1. - М.: Просвещение, 2003. -72 с.

59. Интернет порталы: содержание и технологии. Сб. научных статей. Вып. 2. - М.: Просвещение, 2004. - 499 с.

60. Ахо А. и др. Построение и анализ вычислительных алгоритмов/А.Ахо, Дж. Хопкрофт, Дж.Ульман: пер. с англ.-М.:Мир, 1979.-356с.

61. Иванов Б.Н. Дискретная математика. Алгоритмы и программы/Техн.ун-т.- М.: Лаборатория базовых знаний, 2001, 288с.

62. Олифер В.Г., Олифер H.A. Новые технологии и оборудование IP-сетей. СПб.: БХВ-Санкт-Петербург, 2001.-512с.: ил.

63. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Центр непрер. матем. Образования, 2000. - 960с.: ил.

64. Марков A.A., Нагорный Н.М. Теория алгоритмов. М.: Наука. Гл. ред. физ.-мат.лит., 1984.-432с.

65. Свами М., Тхуласирамон К. Графы, сети и алгоритмы: Пер.с англ. -М.: Мир, 1984.-455с., ил.

66. Трауб Д., Вожняховский X. Общая теория оптимальных алгоритмов/ Пер. с англ. А.Г.Сухарева; под ред.Н.С. Бахвалова.- М.: Мир, 1983. 382с.

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

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

69. Касьянов В.Н., Евстигнеев В.Г. Графы в программировании: Обработка, визуализация и применение СПб .: БХВ-Петербург, 2003.-1104с.: ил.

70. Успенский В.А., Семенов А.Л. Теория алгоритмов: Основные открытия и приложения. М.: Наука, 1987. - 288с. : ил.

71. Кнут Д.Э. Искусство программирования, т.1. Основные алгоритмы: Пер. с англ.- М.: Издательский дом «Вильяме», 2001. 720с.: ил.

72. Кнут Д.Э. Искусство программирования, т.З. Сортировка и поиск: Пер. с англ.- М.: Издательский дом «Вильяме», 2000. 822с.: ил.

73. Куракин Д.В. Маршрутизаторы для глобальных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии 1996, N2.

74. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. М.: Компьютер Пресс. 1998. - 320с.

75. Афенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. М., Изд. МГТУ им. Баумана, 2000, - 248с.

76. Кравец О.Я., Пономарев А.В., Подерский И.С. Повышение эффективности маршрутизации в переходных режимах функционирования вычислительных сетей. //Системы управления и информационные технологии. -2003.- № 1-2, с. 73-77.

77. Ванг Ж. Маршрутизация обретает интеллектуальность. // Журнал сетевых решений/ LAN. 2002.- №6, с. 73-77.

78. Новиков А.Б. Маршрутизация трафика в IP-сетях с применением генетических алгоритмов. // Система управления и информационные технологии. -2003. № 1-2., с. 78-81.

79. Фарадал Р. Как повысить производительность IP- магистрали. // Сети. -1998.-№5, с. 24-25.

80. Крейнес А. От Москвы до самых до окраин: маршрутами PNN I // Сети. Глобальные сети и телекоммуникации. 1988 - № 1, с. 16-19.

81. Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации: Учебник для вузов. ФИС, 1998.

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

83. Танненбаум Э. Компьютерные сети. СПб.: Питер, 2002.

84. RFC 1058, - Routing Information Protocol. C.L. Hedrick. 1988.

85. Блэк Ю. Сети ЭВМ: пространство, стандарты, интерфейсы. Перев. с англ. М.: Мир, 1990. - 506 с.

86. Кульгин Н.В. Технологии корпоративных сетей: Энциклопедия. -СПб.: Питер, 2000. 699 с.

87. Енюков И.С., Ретинская И.В. Скуратов А.К. Статистический анализ и мониторинг научно-образовательных интернет-сетей. М.: «Финансы и статистика», 2004, 318 с.

88. Герасимов В.В., Гугель Ю.В., Курмышев Н.В., Сигалов А.В. Система образовательных порталов России: анализ телекоммуникационнойинфраструктуры. // Образовательные порталы России Вып. 1, М.: Технопечать, 2004, с. 4-66.

89. Архангельский А.Я. Приемы программирования в Delhhi. — М.: БИНОМ, 2003.-784с.

90. Архангельский А.Я. Delphi 5. Справочное пособие. М.: ЗАО «Издательство БИНОМ», 2001.- 768с.

91. Баженова И.Ю. Delphi 5. Самоучитель программиста. М.: КУДИЦ-ОБРАЗ, 2000. -335с.

92. Бобровский С.И. Delphi 5. Начальный курс. М.: DECC, 1999. - 271с.

93. Гофман В.К., Хомоненко A.B. Delphi 5. СПб.: М.: Минск: Питер, 2001,-560 с.

94. Кэнту М. Delphi 5 для профессионалов. СПб.: Питер, 2001. 244с.

95. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник. М.: СПб.: Питер, 2003. - 640с.

96. Буч Г., Якобсон А. и др. Унифицированный процесс разработки программного обеспечения для профессионалов — М.: СПб.: Киев: Минск: Питер, 2003.-496с.

97. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2003.-368с.

98. Эдди С. XML: Справочник. СПб.: Питер, 1999. - 477с.

99. Д.Э.Колосов "К вопросу оптимизации географического размещения информационных ресурсов", Международная конференция «Телематика-2005», том 1, с.268-269, 2005.

100. В.А. Каймин, Д.Э. Колосов «О международных стандартах образования в области информатики» «Материалы 7-ой Международной конференции по дистанционному образованию», с. 149-152 М.: МЭСИ, 1999.

101. В.А. Каймин, Д.Э. Колосов «О международных и национальных стандартах образования в области информатики» «Материалы 4-ой Международной конференции по дистанционному образованию», с. 94-98, М.: МЭСИ, 1997.