Разработка и анализ методов последовательной прокладки путей в сетях передачи данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Курочкин, Илья Ильич

• Курочкин, Илья Ильич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Курочкин, Илья Ильич

ВВ БДЕНИЕ.

ГЛАВА 1.£

ТЕЛЕКОММУНИКАЦИОННЫЕ СЕТИ.£ локальные и глобальные сети.

ТРЕБОВАНИЯ К СЕТЯМ.

ВЫНУЖДЕННЫЕ УЛУЧШЕНИЯ.

МАРШРУТИЗАЦИЯ.

ПРИНЦИПЫ IP-МАРШРУТИЗАЦИИ.

ОСНОВНЫЕ ПРОТОКОЛЫ МАРШРУТИЗАЦИИ.

ОБ ОСНОВНЫХ ПРИНЦИПАХ ПРОТОКОЛОВ СОСТОЯНИЯ КАНАЛА.

ПРОБЛЕМЫ СОВРЕМЕННЫХ ПРОТОКОЛОВ МАРШРУТИЗАЦИИ.

СЕТИ SDH/SONET.

ОСОБЕННОСТИ ТЕХНОЛОГИИ SDH/SONET.

ВЫВОДЫ.

ГЛАВА 2.

ПОСТАНОВКА ЗАДАЧИ. РАЗЛИЧНЫЕ ВАРИАНТЫ АЛГОРИТМОВ РЕШЕНИЯ.

АЛГОРИТМЫ ПОСЛЕДОВАТЕЛЬНОГО ЗАПОЛНЕНИЯ.

ПРОСТОЙ АЛГОРИТМ.

СУБОПТИМАЛЬНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

РАВНОМЕРНЫЙ ПО МИНИМАЛЬНЫМРАЗРЕЗАМ АЛГОРИТМ.

РАВНОМЕРНЫЙ ПО ДУГАМ АЛГОРИТМ.

СУБОПТИМАЛЬНЫЙ ДУГОВОЙ АЛГОРИТМ.

ОПТИМАЛЬНЫЙ АЛГОРИТМ.

АДДИТИВНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

ГИБРИДНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

ГРУППИРОВКА АЛГОРИТМОВ ПОСЛЕДОВАТЕЛЬНОГО ЗАПОЛНЕНИЯ.

ВЕРОЯТНОСТНАЯ МОДЕЛЬ ПОТОКА ЭЛЕМЕНТАРНЫХ ТРЕБОВАНИЙ.

АЛГОРИТМЫ ПОИСКА НА ГРАФЕ.

ПОИСК В ШИРИНУ.

ПОИСК В ГЛУБИНУ.

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ.

РЕЛАКСАЦИЯ.

АЛГОРИТМ ДЕЙКСГРЫ.

АЛГОРИТМ БЕЛЛМАНА-ФОРДА.

АЛГОРИТМЫ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА.

МЕТОД ФОРДА-ФАЛКЕРСОНА.

АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА.

АЛГОРИТМ ЭДМОНДСА-КАРПА.

ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА

ВЫВОДЫ.

ГЛАВ A3.

МОДЕЛЬ СЕТИ.

ГЕНЕРАЦИЯ СЕТЕЙ С ЗАДАННЫМИ ПАРАМЕТРАМИ.

Приближенные схемы вычислений.

СТРУКТУРА ХРАНЕНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.

ВЫВОДЫ.

ГЛАВА 4.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

ХАРАКТЕРИСТИКА ВЫБРАННЫХ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ. ДИНАМИКА ЗАПОЛНЕНИЯ СЕТЕЙ.

РЕЗУЛЬТАТЫ ЗАПОЛНЕНИЯ СЕТЕЙ.

ВЫВОДЫ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ С ТОПОЛОГИЕЙ КОЛЕСО.

М ОДЕ ЛИР ОВ АНИ Е.

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА. простое колесо (1). результаты.

КОЛЕСО С ХОРДАМИ (2). РЕЗУЛЬТАТЫ.

ДВОЙНОЕ КОЛЕСО (3). РЕЗУЛЬТАТЫ.

ДВОЙНОЕ КОЛЕСО С ХОРДАМИ (4). РЕЗУЛЬТАТЫ.

ПЕРИФЕРИЧЕСКОЕ ДВОЙНОЕ КОЛЕСО (5). РЕЗУЛЬТАТЫ.

СИЛЬНОСВЯЗНОЕ ДВОЙНОЕ КОЛЕСО (6). РЕЗУЛЬТАТЫ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ С ТОПОЛОГИЕЙ СВЯЗНЫЕ КЛАСТЕРЫ.

РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ.

ПЕРВОЕ МНОЖЕСТВО СЕТЕЙ.11 б

ВТОРОЕ МНОЖЕСТВО СЕТЕЙ.

ДИНАМИЧЕСКОЕ ЗАПОЛНЕНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ.

ДИНАМИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

РЕЗУЛЬТАТЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ.

ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Разработка и анализ методов последовательной прокладки путей в сетях передачи данных»

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

Описаны основные протоколы IP-маршрутизации а также приведено строение глобальных и локальных сетей, освещены некоторые вопросы мониторинга и анализа локальных сетей. Сделана попытка систематизировать и обобщить знания связанные с маршрутизацией в телекоммуникационных сетях (не ограничиваясь IP-сетями). [4, 16, 26, 33, 64, 65]

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

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

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

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

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

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

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

В процессе исследования заполнения сети мпогопродуктовым потоком были выдвинуты несколько гипотез и предположений относительно прокладки путей по дугам минимальных разрезов.[3, 5, 6] Эти предположения базировались на значимости дуг минимальных разрезов с точки зрения прокладки новых путей. Первое предположение заключается в том, что при заполнении сети будет удовлетворено больше заявок, если в процессе заполнения будет минимизировано приращение критерия неравномерности сети. Второе предположение заключается в порядке использования дуг при прокладке путей. При удовлетворении новой заявки приоритет должен быть у пути, в котором присутствует минимальное количество дуг, принадлежащих минимальным разрезам. Третье предположение основывается на подсчете количества минимальных разрезов, которым принадлежит дуга. То есть использование дуги в прокладываемом пути зависит от количества минимальных разрезов, к которым она принадлежит. При этом учитываются минимальные разрезы, принадлежащие всем парам полюсов сети.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Курочкин, Илья Ильич

Выводы

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

При создании программного инструментария были использованы современные средства разработки, такие как математический пакет Matlab, среда разработки MS Visual Studio, СУБД MS SQL Server.

Научная новизна диссертационной работы складывается из следующих результатов:

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

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

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

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

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

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

• Управление потоками в распределенных системах хранения и передачи данных;

• Задача минимизации заторов и пробок в дорожной сети города;

• Задача планирования развития дорожной сети города;

• Маршрутизация и проектирование в IP-сетях для автономной системы или ее сегментов при использовании MPLS и туннелирования;

• Маршрутизация в SDH/SONET-сетях;

• Канальная маршрутизация с централизованным управлением.

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

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

Обобщить результаты и выводы можно следующими пунктами:

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

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

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

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

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

• субоптимальный минимально-разрезный алгоритм (PC);

• гибридный минимально-разрезный алгоритм (РГ).

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

• равномерный по дугам алгоритм (Д);

• аддитивный минимально-разрезный алгоритм (РА), так как они не позволяют достичь увеличения полного потока в сети при заполнении до полного отказа.

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

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

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

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

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

Заключение

На рисунках 5.1. и 5.2. представлены графики относительного превышения потока по разным алгоритмам по сравнению с простым алгоритмом по критерию завершения №1.

По результатам заполнения сетей до первого отказа (критерий завершения №1) можно сделать следующие выводы:

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

• Для сетей с 'большими значениями МНМР разные алгоритмы заполнения почти во всех случаях дают одинаковый результат,

• Существуют сети, для которых превышение потока составляет 50%.

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

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

2.500

-40% bN

2.000

1.500

1.000

0.500 2 та В I а 1 л г л

I X X X

О с X

-г 5 т

0.000

Рисунок 5.1, Процент превышения потока для критерия 1-ого отказа.

-40%

2.000 e> а. п (С а. s 2 X л

1.000

0.000

Рисунок.5.2. Процент превышения потока для критерия 1-ого отказа. Сортировка по убыванию процента превышения.

На рисунке 5.3. показаны графики превышения потока в процентах до полного отказа (критерий завершения №2) для всех алгоритмов заполнения сетей. Значения отсортированы по убыванию процента превышения для гибридного алгоритма.

Рисунок 5.3. Процент превышения потока для критерия полного отказа

Arc. Criteria 2

Subopt. Criteria 2

Рисунок 5.4. Гистограммы процента превышения по каждому алгоритму. Критерий №2 до полного отказа

Hybrid. Criteria 2

Addopt. Criteria 2

По этим результатам можно сделать следующие выводы.

• Алгоритмы второй группы (минимально-разрезные) создавались для увеличения потока по критерию завершения №1, но, тем не менее, эксперимент показал, что и по критерию завершения №2 они дают преимущество над простым алгоритмом

• Существуют сети, для которых превышение потока составляет почти 20%.

• Наилучшие результаты, по представленным графикам, демонстрирует субоптимальный(РС) алгоритм.

• Дуговой алгоритм (группа 1) в подавляющем большинстве случаев не дает превышения потока по сравнению с простым алгоритмом.

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

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

Нижняя кривая представляет отношение полного количества проведенных заявок к общему количеству заявок. Поскольку внешний поток заявок равномерно распределен между всеми парами полюсов, то чем более неравномерна начальная сеть, тем большее количество заявок не будет удовлетворено, что и демонстрирует в среднем нижняя кривая. criteria 1/goodOrders g ood О rd ers/a IЮ rde rs steady Value at 1-st step

0 20 40 60 80 100 120 140

Рисунок 5.5. Заполнение 131 сетей с помощью 1 алгоритма (простой)

Список литературы диссертационного исследования кандидат технических наук Курочкин, Илья Ильич, 2010 год

1. Абросимов Л.И., Лукьянчиков А.В. Анализ вероятностно-временных характеристик ЛВС.

2. Басакер Р., Саати Т. Конечные графы и сети. Пер.с англ. М. Наука, 1974. 368 с.

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

4. Борисов М. Новые стандарты высокоскоростных сетей // Открытые системы. 1994. вып.З. С. 20-31.

5. Вишневский В., Гузаков Н., Лаконцев Д. Система "Рапира" базис для отечественных широкополосных беспроводных сетей. - ЭЛЕКТРОНИКА: НТБ,2005, № 1, с.30-34.

6. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-cera: в ожидании стандарта IEEE 802.1 Is. ЭЛЕКТРОНИКА.: НТБ, 2008, №3, с.98-106.

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

8. Волкова В. Н., Воронков В. А., Денисов А. А. Теория систем и методы системного анализа в управлении и связи / М.: Радио и связь, 1983. 248 с.

9. Герасимов А.И. Аналитические методы исследования и оптимизации вычислительных систем и сетей на основе сетевых моделей массового обслуживания. Москва: Радио и связь, 2001.

10. Труды Института Системного Анализа Российской Академии Наук (ИСА РАН). -Москва: КомКнига, 2006, 224с.

11. Дженнингс Ф., Практическая передача данных: Модемы, сети и протоколы.; перев. с англ. М.: Мир, 1989.

12. Ефимова М.Р., Петрова Е.В., Румянцев В.Н. Общая теория статистики. Учебник. Второе издание, исправленное и дополненное. — Москва: Инфра-М, 2006.

13. Келли-Бутл С. Введение в UNIX / Пер. с англ. М.: Лори, 1995.

14. Корпоративные информационные сети./ Под ред. М.Б.Купермана. Информсвязь, вып. 3, 1997.

15. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. Санкт-Петербург: БХВ-Петербург, 2005.

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

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

18. Локальные вычислительные сети: Справочник / Под ред. С.В.Назарова. М.: Финансы и статистика, 1994.

19. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.:Радио и связь, 1986.-408 с.

20. Нанс Б. Компьютерные сети / Пер с англ. М.: Бином, 1995.

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

22. Остерлох Х„ Маршрутизация в IP-сетях. Принципы, протоколы, настройка. -СПб.: ООО «ДиаСофтЮП», 2002. 512 с.

23. Петраков А.В. Введение в электронную почту. М.: Финансы и статистика, 1993.

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

25. Савельев А. Современные протоколы маршрутизации. LAN/ЖУРНАЛ СЕТЕВЫХ РЕШЕНИЙ #12/98, 2000 (www.citforum.ru)

26. Семенов А. Б., Волоконная оптика в локальных и корпоративных сетях связи., АйТи. М.: Компьютер-пресс, 1998.

27. Семёнов Ю.А. (ГНЦ ИТЭФ). Бесклассовая интердоменная маршрутизация (CIDR), book.itep.ru

28. Семенов Ю.А. Протоколы и ресурсы Internet. М.: Радио и связь, 1996.

29. Слепов Н. Н., Синхронные цифровые сети SDH. Н. Н. Слепов. Эко-Трендз, 1998.

30. Спортак Марк А. и др.Высокопроизводительные сети. Энциклопедия пользователя.; перев. с англ. Киев, ДиаСофт, 1998.

31. Таненбаум Э. Компьютерные сети Изд. 3-е. Пер. с англ. — СПб. Питер, 2007. 992 с.

32. ТахаХ. Введение в исследование операций: В 2 кн.: Пер. с англ. М.: Мир, 1985.

33. Тернер Д. Вероятность, статистика и исследование операций: Пер. с англ. М.: Статистика, 1976. 431 с.

34. Томас X. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION ТО ALGORITHMS. — 2-е изд. — М.: «Вильяме», 2006. — С. 1296. — ISBN 0-07013151-1

35. Уилсон Р. Введение в теорию графов: Пер. с англ. М.: Мир, 1977. 207 с.

36. Фейт С. TCP/IP: Архитектура, протоколы, реализация (включая IP версии 6 и IP Securing) 2-е изд. - М.: Лорри, 2000.

37. Филимонов А.Ю. Сети ЭВМ и терекоммуникации. (курс лекций)

38. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984. 496 с.

39. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1966.

40. Фролов А.В., Фролов Г.В. Глобальные сети компьютеров. М.: Диалог-МИФИ, 1996.

41. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1973.

42. Челлис Дж., Перкинс Ч., Стриб М., Основы построения сетей. Учебное руководство для специалистов MCSE.; перевод с англ. Лори, 1997.

43. Шапорев С. Д. Дискретная математика. Курс лекций и практических занятий. Изд.: БХВ-Петербург, ISBN: 5941577036, 2005.

44. Шатт С. Мир компьютерных сетей / Пер. с англ. Киев: BHV, 1996.

45. Шеннон Р. Имитационное моделирование систем искусство и наука: Пер. с англ. М.: Мир, 1978.418 с.

46. Шмалько А.В. Цифровые сети связи: основы планирования и построения. — М.: Эко-Трендз, 2001.

47. Шпилев С. А. Проактивная маршрутизация в IEEE 802.1 Is mesh-сетях. — Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008), 2008.

48. Эндрюс Дж., Математическое моделирование: Пер. с англ. / Под ред. Дж. Эндрюса и Р. Мак-Лоуна. М.: Мир, 1979. 278 с.54. www.citforum.ru. Материалы по маршрутизации в IP-сетях и описанию Ethernet.

49. Cheriyan J., Mehlhorn К. An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm.

50. Comer Duglas E., Internetworking with TCP/IP: Principles, Protocols, and Architecture, Prentice Hall, 1995.

51. Cormen Т.Н., Leiserson C.E., Rivest R.L. Introduction to algorithms. 1990.

52. Edmunds. K., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 1972, 19, s. 248-264.

53. Fong С. O, Rao M. R. Accelerated labeling algorithms for the maximal flow problem with applications to transportation and assignment problems Working Paper No. 7222, Graduate School of Management, U. of Rochester, Rochester, N Y , 1972.

54. Galil Z., Naamad A. Network flow and generalized path compression. 1979.

55. Goldberg A. V. Combinatorial Optimization Lecture Notes for CS363/OR349.

56. Goldberg A. V., Rao S. Length functions for flow computations. Technical report #97055, NEC Research Institute, 1997.

57. Goldberg A. V., Tarjan R. E. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921-940, 1988.

58. Halsall F. Data Communications, Computer Networks and Open Systems. Addison-Wesley Publ., 1992.

59. Halsall Fred, Data Communications, Computer Networks and Open Systems, Adisson-Wesley, 1996.

60. Hein M., Kemmler W. Bay Networks. Gigabit Ethernet Guide. FOSSIL Verlag GmbH, 1998.

61. Hunt Craig, TCP/IP Network Administration, 2/e, O'Reilly & Associates, 1998.

62. Johnson E L. Networks and basic solutions. Oper. Res. 14 (1966), 619-623.

63. Kurt Mehlhorn, Christian Uhrig. The minimum cut algorithm of Stoer and Wagner 1995.

64. Lin P. M., Leon B. J. Improving the efficiency of labeling algorithms for maximum flow In networks Proc IEEE Int Syrup on Circuits and Systems, 1974, pp 162-166.

65. Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm 1997.

66. Sleator D. D., Tarjan R. E. A Data Structure for Dynamic Trees. J. Comput. System Sci.,26:362-391, 1983.

67. Srinivasan V., Thompson G.L. Accelerated algorithms for labeling and relabeling trees, with applications to distribution problems. J. ACM 19, 4 (Oct. 1972), 712-726.

68. Stallings William, Data and Computer Communications, 5/e,, Prentice Hall, 1997.

69. Stallings William, ISDN and Broadband ISDN with Frame Relay and ATM, 3/e, Prentice Hall, 1995.

70. Wilf B. S. Algorithms and Complexity. Internet edition, summer 1994. http://www/cis.upenn.edu/wilf.

71. IEEE P802.1 ls/D1.08. Amendment: Mesh Networking. IEEE, January 2008.

72. Perkins C., Belding-Royer E., Das S. Ad hoc On-Demand Distance Vector (AODV) Routing. IETF RFC 3561, July 2003.

73. IEEE P802.1 ls/D1.00. Amendment: Mesh Networking. IEEE, November 2006.

74. IEEE P802.1 Is/ D1.06. Amendment: Mesh Networking. IEEE, July 2007.

75. Clausen Т., Jacquet P. Optimized Link State Routing Protocol (OLSR). IETF RFC 3626, October 2003.

76. Qayyum, Laouiti A., Viennot L. Multipoint relaying technique for flooding broad-cast messages in mobile wireless networks. HICSS: Hawai Int. Conference on System Sciences, January 2002.

77. IEEE P802.11s/D1.07. Amendment: Mesh Networking. IEEE, September 2007.

78. Reconsidering RA-OLSR IEEE P802.1 l-07.2547r2, September 2007.

79. Mesh Meeting Agenda September 2007. IEEE P802.1 l-07.2290rl 1, September 2007.

80. Vishnevsky V.M., Gorodov P.V., Shpilev S.A. Performance analisys of RA-OLSR in IEEE 802.1 Is mesh networks. International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007), 2007, Vol. 1.

81. Schriber T.J. Simulation using GPSS. John Wiley & Sons, 1974.