Математическое моделирование в задачах маршрутизации сетей передачи данных: Многокритериальный подход тема диссертации и автореферата по ВАК РФ 05.13.16, доктор физико-математических наук Васильев, Николай Семенович

• Васильев, Николай Семенович
• доктор физико-математических наук
• 1999

Оглавление диссертации доктор физико-математических наук Васильев, Николай Семенович

Введение

Глава 1. Маршрутизация в сетях с виртуальными каналами

§1.1. Описание модели функционирования сети передачи данных

§1.2. Принцип оптимальности. Игровая модель маршрутизации в сети с виртуальными каналами передачи

§1.3. Свойства оптимальных решений отдельной задачи маршрутизации

§1.4. Эвристический алгоритм поиска оптимальной маршрутизации

Глава 2. Динамическая маршрутизация сети

§2.1. Игровая модель дейтаграммной сети передачи данных

§2.2. Свойства оптимальных маршрутов

§2.3. Являются ли оптимальные маршруты кратчайшими?

§2.4. Эвристический метод поиска оптимальной маршрутизации

Глава 3. Существование равновесной маршрутизации

§3.1. Агрегирование маршрутов в сетях передачи данных

§3.2. Пример недостижимости равновесия. Теорема существования равновесия в кольцевой сети маршрутизаций в моделях некольцевых сетей

Глава 4. Единственность равновесной маршрутизации

§4.1. О свойствах средних потоков

§4.2. О недополнительности равновесной маршрутизации в кольцевой сети 11£

§43 Теорема единственности равновесия в модели кольцевой сети 122,

§4.4. Об оптимальности по Парето равновесной маршрутизации кольцевой сети

Глава 5. Иерархические модели сетей

§5.1. Модель сети с приоритетами сообщений

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

§5.3. Игровой алгоритм поиска равновесной маршрутизации в модели кольцевой сети

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

§5.5. Модель управления входным потоком

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

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

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

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

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

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

1. О месте задачи маршрутизации в сетевой проблематике. Задачи о многопродуктовых потоках давно занимают видное место в теории исследования операций и имеют разнообразные приложения [2], [4], [10], [13]-[20], [29]-[33], [35], [36], [39]—[41], [46], [48]-[50], [52]-[57], [60], [69], [71], [72], [75], [77], [80], [81], [83]-[90], [94]- [96], [116], [122], [123], [133], [135]- [137], [144], [146], [148], [152], [155], [158]-[167], [171]. Из них к числу наиболее трудных и важных принадлежит проблема маршрутизации ( см. обзоры в [5], [93], [119], [121], а также [78], [79], [91]-[93], [97], [101]—[103], [107]—[ИЗ], [117]-[119], [121], [125]-[129], [131], [138]—[140], [142], [145], [150], [151], [153]-[156], [159]—[162], [168]—[174]). Она связана с изучением широкого круга вопросов, охватывающего разработку алгоритмов выбора маршрутов передачи продуктов по сети.

Проблему маршрутизации будем исследовать в применении к таким сложным системам, какими являются широкомасштабные пакетные сети (см. [4]-[8], [34], [40], [46], [47], [58], [59], [64], [66] - [68], [80], [96], [98], [110], [124]), которые служат для передачи данных различных типов (изображений, речи, документов, писем, файлов и т.д.). Усложняется управление в локальных сетях, в которых также возникает надобность внедрения новых служб, прежде характерных только для глобальных сетей [25]. Усложнение локальных сетей, их подсоединение к глобальным системам связи, увеличение объемов передаваемой по ним информации, является результатом интеграционных процессов, свойственных развитию крупных корпораций.

В современных системах связи используются распределенные алгоритмы управления маршрутами передачи (сетевые протоколы), обеспечивающие высокую пропускную способность и быстродействие сетей, а также их надежное и устойчивое функционирование. Сеть связи должна сохранять работоспособность даже при условии отказов некоторых ее линий и узлов передачи [124], а также в случае искажения (или потери) служебной информации, пересылаемой по той же самой сети и необходимой для работы алгоритмов управления передачей [5]. Отсюда наибольший интерес представляют собой динамические правила управления маршрутами, учитывающие текущее состояние сети и адекватно реагирующие на различного рода нестационарности в сети.

Метод маршрутизации учитывается при решении многих сетевых задач, например, выбора сетевой топологии ([5]), управления входной нагрузкой ([5], [55]) и избыточными потоками в сети (при перегрузках) ([78], [125], [127], [138], [169]) и других. От качества маршрутизации зависит эффективность использования сети [5], [31], [35], [48], [51], [52], ее пропускная способность, средняя задержка в передаче пакета [4], [39], [40], [71], [98], [105], [120], [130], [132], [159], процент потерянных пакетов [113], возникновение тупиковых ситуаций и перегрузок сети [5]. По принципу обратной связи алгоритм марш— рутизации обычно объединяют с алгоритмом управления входной нагрузкой, регулирующим доступ к передающей среде [5], [80], [98], [159]. О трудности и актуальности удовлетворительного решения проблемы оптимальной маршрутизации свидетельствует тот факт, что протоколы маршрутизации периодически модифицируются даже в действующих сетях передачи данных [5], [130], [135].

В качестве стандрата 150 (международная организация по стандартам) принята эталонная семиуровневая модель взаимодействия открытых систем, определяющая функциональную модульность проектируемой сети (см. [5], [6], [43], [44], [58]). В ней маршрутизация относится к сетевому уровню описания, являясь одной из сложнейших функций. Все паритетные процессы сетевого уровня должны обмениваться информацией для того, чтобы обеспечить согласованную работу сетевых узлов по управлению потоками в сети. Указанные процессы выполняются совместно (параллельно) и каждый из них развивается в своем сетевом узле. Для сравнения, на других уровнях модели паритетные процессы образуют всего лишь взаимодействующие пары.

В настоящее время надежды на существенное повышение быстродействия вычислительных сетей (а также отдельных компьютеров) связывают с выявлением и использованием параллеллизма в вычислениях [12], [15], [24], [64], [74]. Указанное соображение реализовано в современных системах связи, для ускорения передачи применяющих методы пакетной коммутации. Производительность мультипроцессорных систем, параллельных, векторно — конвейерных компьютеров, сетей ЭВМ существенно зависит от выбираемой маршрутизации потоков данных, которыми обмениваются процессорные единицы посредством локальной сети системы. Расписание работы устройств, составлящих эти системы, строится с учетом маршрутизации [15], [24],[74], [134], [158]. Более того, при проектировании спецпроцессоров выбор быстрого (параллельного) алгоритма определяет вид локальной сети вычислителя. Аппаратное воплощение этого алгоритма происходит с учетом возможностей по оптимизации накладных расходов, связанных с маршрутизацией (см., например, [15]). Во всех приведенных примерах управление маршрутами передачи может строиться на основе алгоритмов, разработанных с помощью математических моделей, учитывающих особенности изучаемой системы. Процесс маршрутизации необходимо моделировать для того, чтобы искать оптимальные решения указанной задачи управления. Для всякой сложной технической системы, в том числе сети передачи данных, построение эффективной системы управления является одной из главных проблем.

При исследовании потоковых задач не всегда удается найти такое математическое решение проблемы, которое допускает эффективную алгоритмическую реализацию. Например, выбор наилучшей сетевой топологии является (NP-) трудной комбинаторной задачей [5], [28], [29], [32], [35], [51], [114], [143]. Сложность изучаемой проблемы оправдывает широкое использование эвристических подходов к ее решению. Аналогично обстоит дело с проблемой маршрутизации, алгоритмы которой зачастую основаны не на решении явно поставленной задачи оптимального управления маршрутами передачи, а на разумных эвристических соображениях [79], [92], [97], [111], [139]. В любом случае создатели методов опираются на модельные представления о сети связи.

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

Изучению процессов в сетях посвящены всесторонние теоретические исследования, дополняемые вычислительными экспериментами, проводимыми на имитационных моделях [ 1 ], [ 3 ], [34], [35], [40], [51], [67], [69], [71], [76], [105], [115], [120], [130], [132], [145]. Накопление знаний о сетях происходит также в результате наблюдений за действующими системами [91], [168].

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

Существует два варианта пакетной коммутации с промежуточным накоплением [5], [58], [59]. В первом из них, называемом дейтаграммной (динамической) маршрутизацией, каждый пакет (дейтаграмма) следует своим собственным маршрутом. Например, этот метод применяется в сети ARPANET [5], [135]. Управление движением пакетов по сети осуществляется теми сетевыми узлами, через которые пролегают маршруты передачи. Для этого в каждом сетевом узле размещена маршрутная таблица, время от времени обновляемая алгоритмом маршрутизации (см. [79], [93], [97], [111]). Указанный метод передачи может приводить к тому, что части (пакеты) одного и того же сообщения следуют разными путями.

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

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

Оба метода передачи могут применяться в одной и той же сети. Так, в сети CODEX (см.[5],[157]) сообщения транспортируются по виртуальным каналам, а служебная информация — в виде дейтаграмм. По мнению создателей сети доставка служебных данных в виде дейтаграмм менее расточительна. Алгоритм управления передачей в сети CODEX децентрализован, как, впрочем, и новый вариант протоколов сети TYMNET [5]. Последнее обстоятельство свидетельствует о проявлении общей тенденции к созданию систем управления сетями, основанных на децентрализованных моделях принятия решений.

Оба подхода к маршрутизации, особенно дейтаграммный, обладают тенденцией к вызыванию колебаний потоков в сети. Это значительно снижает производительность системы связи, а порой даже приводит к ее полной неработоспособности [5], [85]. Главной причиной колебаний является следующее обстоятельство. Выбор маршрутов соединения некоторой пары абонентов сети, проходящих через какую—либо область, увеличивает нагрузку и, следовательно, длины соответствующих линий (равные задержке в передаче пакетов). Это вынуждает пересмотреть маршруты передачи для остальных пар абонентов. Тогда при следующей корректировке маршрутизации алгоритм выберет маршруты, проходящие через другие области сети, ставшие более привлекательными для передачи [5].

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

3. О математических постановках задачи маршрутизации. Наиболее распространенным подходом к построению алгоритмов маршрутизации является использование оптимизационных моделей в форме задачи математического программирования (см. [2], [5],

9], [10], [29]—[31], [35], [36], [41],[48], [49], [51], [60], [72],[76], [77],[83], [95], [96], [100], [104], [136], [171]).

Постановки в форме экстремальной задачи различаются видом целевой функции. Это может быть средняя задержка пакета в сети [5], стоимость передачи [49], надежность, живучесть [108], [151], стоимость сети [10],[33], [84], [86], [136], [171], средняя длина всех линий сети [41]. При этом алгоритм маршрутизации представляет собой градиентный метод решения соответствующей задачи математического программирования (см., например, [5],

10], [41], [85], [86], [95], [96], [104]).

Для оптимизационных моделей существенно облегчена разработка алгоритмов численного решения соответствующих экстремальных задач. Это связано с наличием хорошо развитой теории (см., например, [22], [38]). (Подобного нельзя сказать о решении игровых задач.) Метод маршрутизации может быть основан на алгоритме градиентного типа [5], [41], [77], [85] -[87], [95], [96], [147]. Для ускорения сходимости и распределения вычислений по сети хорошо подходит также метод Ньютона, применение которого предложено в работах [5], [87], [88].

Пусть критерий качества, выбранный в задаче об оптимальной маршрутизации, является гладкой выпуклой сепарабельной функцией вектора потоков в сети. Тогда оказывается, что оптимальные маршруты передачи являются кратчайшими в графе сети, весовые функции дуг которой равны первым производным целевой функции по потокам [5],[10]. Отсюда следует, что каждая итерация градиентного метода сводится к решению задачи нахождения кратчайшего пути [45], [114], [143]. Заметим, что поочередное (для всех пар абонентов сети) вычисление кратчайшего пути в подходящей метрике и использование его для передачи положено в основу многих сетевых протоколов [5].

Даже эта постановка проблемы оптимальной маршрутизации не позволяет полностью избавиться от трудностей, связанных с возникновением колебательных процессов в сети. Распределенная по сети (асинхронная) реализация градиентного метода [89], [90] может утратить свойство сходимости. Дело в том, что работа распределенного алгоритма происходит в условиях неопределенности, связанной с наличием запаздывания или искажений передаваемой служебной информации. Это приводит к тому, что фактически для каждой тяготеющей пары абонентов сети ("отправитель — адресат") приходится решать самостоятельную оптимизационную задачу. В каждой такой задаче присутствуют собственные цели и средства управления.

Отмеченную ситуацию хорошо описывает бескоалиционная игра [24], [26], [27], [ИЗ]. Отсюда не удивительно, что даже при условии постоянной входной нагрузки нужно применять (и это делается на практике) специальные меры для того, чтобы добиться устойчивого поведения потоков в сети (равновесия). К сказанному добавим, что даже выбор маршрутов передачи для отдельной пары абонентов сети все равно представляет собой сложную вычислительную проблему [14],[20],[21].

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

Рассмотрим подход, связанный с применением теории случайных процессов и массового обслуживания [4], [5] [39], [40], [119], [124]- [133], [152]. Теоретическому исследованию поддаются сравнительно "простые" математические модели, которые позволяют проводить качественный анализ сети передачи данных. Таковы стохастические модели, с помощью которых изучают управление потоками в сети [78], [125], [127], [138], [169], а также оценивают вероятностные характеристики качества обслуживания (например, вероятность потерь пакетов [113]) или производительность системы [91], [105], [120], [128], [139], [168]. Некоторые стохастические подходы к проблеме маршрутизации основаны на рассмотрении уравнения для неподвижной точки, которому удовлетворяют стационарные вероятности [93], [126], [128], [139], [140]. Например, в статье [41] осуществляется оптимальная адаптивная настройка маршрутных таблиц стохастической сети (см. также [113]), находящейся в квазистационарных условиях. Целевая функция - средняя длина всех линий сети. В [41] построен градиентный алгоритм маршрутизации, в котором использован аппарат теории марковских цепей (см. [150]).

Модели стохастических сетей позволяют оценивать среднюю задержку пакета в линии связи. Это необходимо для вычисления среднего времени доставки пакета через сеть по месту назначения. В рамках указанных моделей иногда удается получить явные формулы, учитывающие дисциплину обслуживания очередей, Задержка пакетов в линиях связи складывается из следующих компонент: времени обработки в узле, времени ожидания в очереди и собственно продолжительности передачи пакета по линии связи [5]. Эту важнейшую характеристику, выраженную в виде формулы, затем можно использовать в детерминированной модели сети для решения более сложных задач, например, задачи выбора оптимальной маршрутизации. Упрощение анализа в стохастической модели сети достигается за счет дополнительных, не всегда выполняемых предположений.

Таким образом, алгоритмы маршрутизации построены как в стохастической (см.[4], [5], [33], [39], [41]), так и в детерминированной постановках этой проблемы оптимального управления [5], [9]-[11], [13], [14], [17]-[21], [31], [32], [35], [52]- [57], [148].

В многопродуктовых сетях (в том числе в сетях передачи данных) наиболее естественны многокритериальные и игровые математические постановки задачи маршрутизации. Это объясняется наличием своего собственного критерия оптимальности передачи для каждого продукта в сети. Эти цели зачастую противоречивы. При распределении ресурсов сети не обойтись без компромиссных решений. Процесс управления потоками в сети дополнительно усложняется разного рода неопределенностями (отказами линий и узлов сети, запаздываниями в получении служебной информации и ее неточностью) [5], [54]-[58],[124], [132], [133], [144], [146], [152], [155].

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

Обеспечивая равновесность маршрутизации, необходимо дополнительно заботиться о "справедливом" распределении ресурсов сети среди ее абонентов [5], [55]. Это вместе с обеспечением устойчивости потоков составляет общесетевые цели управления.

Многокритериальные, лексикографические и игровые постановки ( см.[25]-[27], [63] ) потоковых задач изучались в работах [13] -[21], [33], [50], [52] - [56], [94], [137], [163] - [167]. Предложенный в работах [52], [55] метод нормативного анализа сети есть ни что иное, как применение принципа наилучшего гарантированного результата [26], [27], [70] (принципа минимакса).

Минимаксный подход из работ [52], [55] можно применять для решения задачи управления входным потоком.

Наличие конфликтов в управлении маршрутизацией свойственно протоколам сетей ARPANET, TYMNET, CODEX. Всякая пара абонентов сети (отправитель — адресат) стремится по возможности передавать сообщение по такому пути, который является кратчайшим в некоторой метрике. Эта метрика характеризует задержки пакетов в линиях связи. В сети SNA (см.[5], [80], [82], [107]) явно использован игровой принцип: пользователям частично разрешено выбирать маршрут передачи своих сообщений из некоторого множества предлагаемых маршрутов (меню) [5]. В параллельных системах обработки данных маршрутизация строится с учетом метрики в сети, выбираемой следующим образом. В каждый момент времени длина канала связи локальной сети полагается равной числу процессов, конкурирующих за его использование (см. [134]). Таким образом, игровые модели все чаще и чаще применяются при исследовании сетей.

4Постановка задачи в форме бескоалиционной игры (см. [24], [26], [27], [113]). Подробнее остановимся на игровой постановке задачи оптимальной маршрутизации, развиваемой в диссертации (см. [13], [14], [16], [17], [ 19]-[21 ]). В ней игроками являются тяготеющие пары абонентов сети (отправитель — адресат), платежные функции которых равны временам передачи пакетов по сети. Таким образом, каждый игрок решает задачу быстродействия. Он обладает самостоятельностью в принятии решений. Стратегиями игроков являются выборы маршрутов соединения и долевых распределений входных потоков среди них. За счет указанных управляющих воздействий тяготеющая пара абонентов сети стремится ускорить время передачи своих сообщений. Однако это далеко непросто сделать, так как стратегии остальных участников игры — это неконтролируемые факторы, которые, в свою очередь, влияют на ситуацию в игре и могут быть неблагоприятными для рассматриваемого игрока. Подобная модель отражает децентрализованный подход к управлению маршрутами передачи в сети. Под оптимальной (равновесной) маршрутизацией сети понимается игровое равновесие по Нэшу (см. [24], [26], [27], [113]). Решение игровой задачи, основанное на указанном принципе оптимальности, обладает устойчивостью: ни одному из игроков невыгодно отклоняться от своей оптимальной стратегии, если остальные их придерживаются.

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

5. Краткий обзор содержания диссертации. Изучение оптимальных (равновесных по Нэшу) маршрутизаций показало следующее. Пусть метрика в сети определена заданием функций задержек пакетов в линиях связи. Тогда оптимальные маршруты передачи для произвольной пары абонентов сети (в этой, изменяемой вместе с потоками в сети метрике), вообще говоря, не являются кратчайшими [20], [21], чего не следовало бы ожидать, ведь в оптимизационных моделях это не так [5]. Более того, они даже не обязательно имеют одинаковую длину для каждой, взятой в отдельности пары абонентов сети. В работе показано, что среди оптимальных решений задачи маршрутизации существуют такие, в которых совпадают длины маршрутов передачи [20], [21]. Последнее утверждение представляет собой проявление принципа уравнивания Ю. Б. Гермейера, известного в теории исследования операций [26].

Эвристический подход к численному решению задачи маршрутизации может опираться на применение принципа уравнивания [20], [21]. На его основе удается построить выпуклую задачу математического программирования, допускающую эффективное численное решение, например, методом проекций градиента. Вообще говоря, в этом алгоритме от итерации к итерации требуется модифицировать критерий оптимальности за счет отбрасывания неиспользуемых или неперспективных для передачи маршрутов [20], [21]. Указанный подход сохраняет все возможности по распределенной реализации, которыми обладают обсуждавшиеся выше градиентные методы.

В игровых моделях сетей одним из трудных теоретических вопросов является проблема существования равновесных потоков. В данном случае (см.[13], [14], [16], [17], [19], [21], [163]-[167]), это — проблема существования равновесной (в смысле Нэша [25]) маршрутизации. Существование решения игровой задачи доказано для кольцевых сетей [14] и некоторых других сетей сравнительно простой топологии [17], [20], [21]. За счет сужения классов стратегий игроков или с помощью введения иерархии игроков, удалось доказать достижимость равновесия в сетях общего вида.

Кольцевая сеть - одна из наиболее часто используемых конфигураций [5], [124]. Она также является фрагментом более сложных систем. Показано, что в кольцевой сети не только существует равновесие, но и то, что оно единственно [15], [163], [164]. В [19] построен пример агрегированной кольцевой сети, в которой нет равновесия. Это дает основания полагать, что в сетях произвольной топологии равновесие не всегда достижимо. Кроме того, пример показывает, что построение игровых агрегированных моделей нужно проводить так, чтобы в них "сохранялось" равновесие.

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

Иерархическая структура управления маршрутами передачи также позволяет согласовать действия игроков [22], [42], [166]. На верхнем уровне управления иерархической игровой модели находится игрок, называемый арбитром, представляющий интересы всей системы в целом. Арбитр назначает приоритеты передачи пакетов так, чтобы добиться достижения устойчивости потоков (выбора равновесной маршрутизации остальными игроками). Кроме того, арбитр стремится вводить, по возможности, меньшее число приоритетов, чтобы не ущемлять интересов игроков. В диссертации построен основанный на механизме приоритетов игровой алгоритм маршрутизации, сходящийся к равновесию.

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

Сообщениям, отвечающим игрокам, отнесенным к попарно различным классам, достаточно присвоить всего не более пяти приоритетов передачи. С помощью предложенного игрового алгоритма в этой иерархической игре достигается равновесие. Обсуждаемый подход допускает обобщение на случай некольцевых сетей [166]. Заметим, что механизм приоритетов достаточно универсален и применяется также для других целей, например, для борьбы с тупиковыми ситуациями [ 5 ].

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

Диссертация разбита на пять глав и три приложения. В главах 1,2,5 описаны модели сетей передачи данных, которые исследованы в работе. Они соответствуют известным методам пакетной коммутации — с виртуальными каналами (гл.1) и дейтаграммному (гл.2). Решению проблемы существования и единственности равновесия посвящены гл. 3, 4. Кроме того, в главе 4 исследовано соотношение принципов оптимальности по Парето и по Нэшу в задаче маршрутизации кольцевой сети. Понятие оптимальности по Парето может лежать в основе централизованного подхода к проблеме оптимального управления маршрутами передачи. Механизм приоритетов изучен в главе 5. Здесь рассмотрены модели сетей, в которых выбор маршрутизации напоминает процесс принятия решение в иерархических системах . Помимо эвристических алгоритмов поиска оптимального решения (гл. 1, 2) предложены точные игровые методы (гл.5). Более того, в главе 5 проведен сравнительный анализ оптимальных решений иерархических игровых задач маршрутизации, отвечающих заданию попарно различных систем приоритетов передачи.

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

В приложении Б подробно изложен и обоснован алгоритм маршрутизации некольцевой сети. Сходимость алгоритма обоснована с помощью применения принципа сжимающих отображений. Результаты проведенных вычислительных экспериментов подтвердили эффективность построенного алгоритма. Вычислительные эксперименты (см. [179], [184], [185]), проводились с моделями сетей произвольной топологии. Изучалась структура получаемого решения. Проводилось численное исследование сжимающих свойств алгоритма. В экспериментах варьировались исходные данные моделей (функции задержек, входные потоки, множества тяготеющих пар абонентов сети), параметры алгоритма, начальные точки.

Кроме того, алгоритм был успешно применен для оптимизации маршрутов передачи в сети UUNET - магистральной части сети INTERNET [ 177].

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

Список литературы диссертационного исследования доктор физико-математических наук Васильев, Николай Семенович, 1999 год

1.Авен О.И., Турин М.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. - М: Наука, 1981.

2. Башарин Г.П., Бочаров П.П., Коган ЯА. Анализ очередей в вычислительных сетях. Теория и методы расчета. М: Наука, 1989.

3. Бертсекас Д., Галлагер Р. Сети передачи данных. М: Мир, 1989.

4. Беслер Р., Дойч А. Проектирование сетей связи. М: Радио и связь, 1988.

5. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. -М.: Энергоатомиздат, 1984.

6. Бойченко Е.Б., Кальфа В., Овчинников В.В. Локальные вычислительные сети. М: Радио и связь, 1985.

7. Васильев Н.С. Численные методы для одного класса задач оптимального управления на графах// Ж. вычисл. матем. и матем. физ. 1983. т.23. №1. С.77-82.

8. Васильев Н.С. Об автоматическом построении оптимальных параллельных алгоритмов// Ж. Киберн. и Вычисл. Техника. 1991. №5. С. 243-260.

9. Васильев Н.С. О задаче управления маршрутизацией соединений в сетях передачи данных// Ж.вычисл. матем. и матем. физ. 1991. т.31. №4. С.605-607.

10. Васильев Н.С. Равновесная маршрутизация кольцевых сетей// Ж. вычисл. матем. и матем. физ. 1995. т.35. №3. С.452—459.

11. Васильев Н.С. О параллельном алгоритме быстрого вычисления матрицы инерции// Ж. вычисл. матем. и матем. физ. 1995. т.35. №1. С.135-139.

12. Васильев Н.С. О недополнительности равновесной маршрутизации кольцевых сетей //Ж. вычисл. матем. и матем. физ. 1995. т.35. №5. С.794-801.

13. Васильев Н.С. О существовании равновесной маршрутизации в некольцевых сетях передачи данных// Ж. теория и системы управления. 1996. №2. С. 163-167.

14. Васильев Н.С., Федоров В.В. О равновесной маршрутизации в сетях передачи данных// Вестник МГУ, сер. 15, Вычисл. матем. и киберн. 1996. №2. С. 47-52.

15. Васильев Н.С. О свойствах решений задачи маршрутизациисети с виртуальными каналами// Ж. вычисл. матем. и матем. физ. 1997. т.37. № % С. 78У-1-33 .

16. Васильев Н.С. О свойствах решений задачи динамической маршрутизации// Ж. вычисл. матем. и матем. физ. 199%. т.3%. № i . С. feU

17. Васильев Н.С. Иерархическая игровая модель управления маршрутизацией// Межвуз.сб. Проблемы управления. М: Ин-т Текст, и Легк. Пром. 1996. С. .

18. Васильев ФЛ.Численные методы решения экстремальных задач. М: Наука, 1988.

19. Воеводин В.В. Математические модели и методы в параллельных процессах. М: Наука, 1986.

20. Воробьев H.H. Основы теории игр. Бескоалиционные игры — М: Наука, 1984.

21. Виноградов Б. Периферийная маршрутизация в корпоративной сети// Compunity. 1995. № 1(2), С.88-92.

22. Гермейер Ю.Б. Игры с непротивоположными интересами— М: Наука, 1975.

23. Гермейер Ю.Б. Введение в теорию исследования операций. М: Наука, 1971.

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

25. Давыдова И.М, Романовский И.В. Многопродуктовая задача размещения (метод ветвей и границ)// Кибернетика. № 5. 1983. С.63-68.

26. Давыдов Э.Г. Игры, графы, ресурсы. М.: Радио и связь, 1981.

27. Демидович О.И., Малашенко Ю.Е. Синтез сети связи методами линейного программирования. Сообщ. по прикл. матем. М.: ВЦ АН СССР, 1986.

28. Демидович О.И. Методы решения задач синтеза потоковых сетей с вогнутыми целевыми функциями. Сообщ. по прикл. матем. М.: ВЦ АН СССР, 1991.

29. Демин В.К. О соотношении критериев стоимость живучесть при решении задач синтеза систем связи// Техн. средств связи. 1983. вып.1. С.22-27.34.3ахаров Г.П. Методы исследования сетей передачи данных — М: Радио и связь, 1982.

30. Злотов A.B., Хачатуров В.Р. Применение аппроксимационно — комбинаторного метода для решения задач построения оптимальных сетей с нелинейными функциями стоимости ребер. Сообщ. по прикл. матем. М.: ВЦ АН СССР, 1984.

31. Иенсен П., Барнес Д. Потоковое программирование. — М.: Радио и связь, 1984.

32. Канторович A.B., Акилов Г.П. Функциональный анализ. М: Наука, 1977

33. Карманов В.Г. Математическое программирование- М: Наука, 1986.

34. Клейнрок JI. Вычислительные системы с очередями. М: Мир,1979.

35. Клейнрок JI. Коммутационные сети. Стохастические потоки и задержки сообщений. М: Наука, 1970.

36. Коновалов М.Г. Распределенный алгоритм адаптивной маршрутизации градиентного типа для пакетных радиосетей// С6.ИПИ РАН. 1993. С.35-47.

37. Кононенко А.Ф. Принцип гарантированного результата и принятие решений в сложных системах, имеющих иерархическую структуру. Докт.диссер. М.: ВЦ АН СССР, 1978.

38. Краснощеков П.С., Морозов В.В., Федоров В.В. Последовательное агрегирование в задачах внутреннего проектирования технических систем// Известия АН СССР. Техн.киберн. 1979. №5. С.52-61.

39. Краснощеков П.С., Петров A.A. Принципы построения моделей- М: МГУ, 1983.

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

41. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. М: Радио и связь, 1983.

42. Лазарев В.Г. Сетевые протоколы и управление в распределенных вычислительных системах. — М: Наука, 1986.

43. Лозовану Д.Д. Обобщенная задача синтеза сети и некоторые ее свойства// Известия АН МССР. Сер. физико-техн. и матем. наук. 1984. №2. С.13-18.

44. Лозовану Д.Д. Свойства оптимальных решений сетевой транспортной задачи с нелинейными функциями стоимости от потока на дугах сети// Известия АН СССР. Техническая кибернетика. 1982,6. С.94-98.

45. Лочмелис Я.Я. Многокритериальные задачи оптимизации сетей связи// Радиоэлектроника и электросвязь. Исследование по электродинамике и теории цепей. Рига. 1981.С. 105-111.

46. Майника Э. Алгоритмы оптимизации на сетях и графах. — М: Мир, 1981.

47. Малашенко Ю.Е. Математические модели анализа потоковых систем. Сообщ. по прикл. матем. М.: ВЦ РАН, 1993.

48. Малашенко Ю.Е., Новикова Н.М. Многокритериальный и макси -минный анализ многопродуктовых сетей. Сообщ. по прикл. матем. — М: ВЦ АН СССР, 1988.

49. Малашенко Ю.Е., Новикова Н.М. Потоковые задачи анализа уязвимости многопродуктовых сетей// Сообщ. по прикл. матем. М.: ВЦ АН СССР, 1989.

50. Малашенко Ю.Е. Нормативный подход к анализу многопродуктовых сетей// Известия АН СССР. Техн. киберн. 1988. №3. С.117—122.

51. Малашенко Ю.Е. Гарантированные оценки живучести сетей//Известия АН СССР. Техн. киберн. 1988. №6. С.97-102.

52. Малашенко Ю.Е., Ушаков И.А. О построении математических моделей сложных технических систем (на примере сети связи) //Известия АН СССР. Техн. киберн. 1984. №1. С.18-25.

53. Мартин Дж. Вычислительные сети и распределенная обработка данных. М: Финансы и статистика, 1985.

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

55. Михалевич B.C., Трубин В.А, Шор Н.З. Оптимизационные задачи производственно- транспортного плоанирования: модели, методы, алгоритмы. М: Наука, 1986.

56. Моисеев H.H. Элементы теории оптимальных систем. М.: Наука, 1975.

57. Молодцов ДА. Устойчивость принципов оптимальности. М: Наука, 1987.

58. Подиновский В.В, Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М: Сов. радио, 1975.

59. Прангишвили И.В, Подлазов B.C., Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. М: Наука, 1985.

60. Рокафеллар Р. Выпуклый анализ. М: Мир, 1973.

61. Самойленко С.И. Сети ЭВМ. М: Наука, 1986.

62. Смелянский P.JL Модель функционирования распределенной вычислительной системы// Вестник МГУ, сер. 15. Вычислит, матем. и киберн. 1990. № 3. С.121-132.

63. Суздалев A.B., Чугреев О.С. Передача данных в локальных сетях связи. — М: Радио и связь, 1987.

64. Тизик А.П, Цурков В.И. Оптимальное распределение каналов на сети связи// Известия АН СССР. Техн. киберн. 1989. № 4. С.153-159.

65. Федоров В.В. Численные методы максимина. М: Наука, 1979,

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

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

68. Харари Ф. Теория графов. М: Мир, 1973.

69. Хокни Р, Джесхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М: Радио и связь, 1986.

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

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

72. Aashtiani H.Z, Magnanti T.L. Equilibria on a Congested Transportation Network// SLAM J. Algeb. Disc. Math. 1981. v.2. P.213-226.

73. Akinpelu J.M. The overload performance of engineering networks with nonhierarchical and hierarchical routing// AT&T Bell Labs. Tach. J. 1984. v. 63. P. 1261-1281.

74. Ash G.R, Chen J.-S, Frey A.E, Huang B.D. Real-time network routing in a dynamic class-of-service network// Proc. 13th ITC. Copenhagen. 1991.

75. Ahuja V. Routing and Flow Control in Systems Network Achitecture// IBM Syst. J. 1979. v.18. P. 298-314.

76. Assad A.A. Multicommodity network flows a survey // Networks. 1978. v.8. №1. P. 37-91.

77. Atkins J.D. Path Control. The transport Network of SNA//

78. EE Trans.Commun. 1980. Com-28. P.527-538.

79. Barr R.S., Glover F., Klingman D. A new optimization method for large scale fixed charge transportation problems// Operation Research. 1981. v.29. №3. P.448-463.

80. Benjamin R. Analysis of Connection Survivability in Complex Strategic Communications Networks// IEEE J. Select. Areas Commun. 1986. SAC-4. P. 243-253.

81. Bertsekas D.P. Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks// IEEE Trans. Auto. Contr. 1982. AC—27. P. 60-74.

82. Bertsekas D.P. A Unified Framework for Primal—Dual Methods in Minimum Cost Network Flow Problems// Math. Progr. 1985. v.32. P. 125-145.

83. Bertsekas D.P., Gafni E.M., Gallager R.G. Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks// IEEE Trans. Commun. 1984. Com-32. P. 911-919.

84. Bertsekas D.P., Gafni E.M. Projected Newton Methods and Optimization of Multicommodity Flows// IEEE Trans. Auto. Contr. 1983. AC—28. v. 12. P. 1090-1096.

85. Bertsekas D.P. Distributed Dynamic Programming // IEEE Trans. Auto. Contr. 1982. AC-27. P. 610-616.

86. Bertsekas D.P. Distributed Asynchronous Computation of Fixed Points// MathJProgr. 1983. v.27. P. 107-120.

87. Caron F. Results of the telecom Canada high performance routing trial// Proc. 12th ITC. Torino. 1988.

88. Chaudhary M., Krishnan K.R., Pack C.D. Implementing dynamic routing in the local telephone companies of the USA// Proc. 13th ITC. Copenhagen. 1991.

89. Chung S.-P., Kashper A., Ross K.W. Computing approximate blocking probabilities for large loss networks with state — dependent routing// IEEE ACM Commun. №1. 1993.

90. Current J.R., Revell C.S., Cohon J.L. An interactive approach for two objective shortest path problems// Computers Opern. Res. 1990. v.17. №2. P.187-198.

91. Dafermos S.C. Traffic Equilibrium and Variational Inequalities // Trans.Sci. 1980. v.14. P.42-54.

92. Dembo R.S., Klincewicz J.G. A Scaled Reduced Gradient Algorithm for Network Flow Problems with Convex Separable Costs// Math. Prog. Studies. 1981. v.15. P.125-147.

93. Denardo E.V., Park H. Efficient routing of telecommunications traffic// Yale Univ. Tech. Rep. 1991.

94. Dziong Z., Choquette J., Liao k.-Q., Mason L. Admission Control and Routing in ATM Networks//Computer Networks and ISDN Systems 1990. v.20. №1-5. P. 189-196.

95. Ephremides A. The Routing Problem in Computer Networks. F.Blake and H.BJPoor(Eds). Communications Networks. New York: Springer-Verlag, 1986, P. 299-324.

96. Erickson R.E., Monma C.L., Veinott A.F. Send — and — split method for minimum concave cost network flows// Mathematics of Operations Research. 1987. v.12. №4. P.634-664.

97. Filipiak J. Modelling and control of dynamic flows in communication networks. New York: Springer-Verlag, 1988.

98. Filipiak J. Real-time network management. New York: Elsevier, 1991.

99. Filipiak J. Analysis of automatic network management controls// IEEE Trans.Commun. 1991. v.39. №12.

100. Fratta L., Gerla M., Kleinrock L. The Flow Deviation Method, An Approach to Store-and-Forward Communication Network Design// Networks. 1973. v.3. P.97-133.

101. Gafir H.M., Silio C.B.,Jr. Performance Analysis of a Multiple Access Ring Network// IEEE Trans.on Commun. 1993. v.41. № 10. p. 1494-1511.

102. Gafni E.M., Bertsekas D.P. Two-Metric Projection Methods for Constrained Optimization// SLAM J. Contr. Optim. 1984. v.22. №6. P. 936-964.

103. Gavish B., Hantier S. An Algorithm for Optimal Route Selection in SNA Networks// IEEE Trns. Commun. 1983. Com-31. P. 1154-1161.

104. Gavish B., Neuman I. Routing in a network with unreliable components// IEEE Trans. Commun. 1992. v.40. №7.

105. Gersht A., Lee K.J. A bandwith management strategy in ATM networks// GTE LAB. Tech. Rep, 1990.

106. Gibbens RJ., Kelly P.B. Dynamic routing in fully connected networks// IMA J.Math. Contr. and Inform. 1990. v.7. P. 77-111.

107. Gibbens R.J., Kelly F.P., Key P.B. Dynamic alternativerouting modelling and behaviour// Proc 12th ITC. Torino. 1988. 3.4A. 3.1-3.4A. 3.7.

108. Girard A. Routing and dimensioning in circuit-switched networks. Reading, MA: Addison Wesley, 1990.

109. Girard A, Bell MA. Blocking evaluation for networks with residual capacity adaptive routing// IEEE Trans. Commun. 1990. v.37. P. 1372-1380.

110. Gondran M, Minoux M. Graphes et algorithmes. Paris: Ed. Eyrolles, 1979. Col.37.

111. Hayes J.F. Modeling and Analysis of Computer Communications Networks. New York: Plenum, 1984.

112. Hajec B, Ogier R.G. Optimal Dynamic Routing in Communication Networks with Continious Traffic // Networks. 1984. v.14. P.457—487.

113. Hunt PJ. Implied costs in loss networks// Adv. Appl. Prob. 1989. v.21. P. 661-680.118 .Hunt PJ, Kelly F.P. On critically loaded loss networks// Adv. Appl. Prob. 1989. v.21. P. 661-680.

114. Hurley B.R, Seidl CJ, Sewell W.F. A survey of dynamic routing methods for circuit — switching traffic// IEEE Commun. Mag. 1987. v.25. P. 13-21.

115. IEEE Journal on Selected Areas in Communications // Special issue on Networks Performance Evaluation. 1986. Sept. SAC—4.6.

116. Inone A, Mase V, Yamamoto H, Suyama M. A state andtime dependent dynamic routing scheme for telephone networks// Proc. 13th ITC. Copenhagen. 1991. June 19-26. P.195—200.

117. Jaffe J.M. A Decentralised "Optimal" Multiple-User Flow Control Algorithm// IEEE Trans. Commun. 1981. COM-29. P.954-962.

118. Kandlur D.D., Shin K.G. Traffic Routing for Multicomputer Networks with Virtual Cut—through Capability // Proc. of the 10th int'l Conf. on Distrib. Comput. Syst. 1990. P. 398-405.

119. Kajiyama Y., Tokura N, Kikuchi K. An ATM VP-Based Self—Healing Ring//IEEE J. on Selected Areas in Commun. 1994. v.12. №1. P.171-177.

120. Kelly F.P. Routing and capacity allocation in networks with trunk reservation// Math. Oper.Res. 1990. v.15. P.771-792.

121. F.P.Kelly. Loss networks// Ann. Appl. Prob. 1991. v.l. P. 319-378.

122. Key P.B. Optimal control and trunk reservation in loss networks// Prob. in Eng. and Inform. Sci. 1990. v. 4. P.203—242.

123. Krishnan K.R. Performance evaluation of networks under state — dependent routing// Proc. Bellcore Symp. Perform. Model. 1990. May. ORSA/TIMS Conf. Philadelphia. Pa. Oct.

124. Labourdette J.-F., Hart W. Blocking probabilities in multi- traffic loss systems: intensivity, asymptotic, behaviourand approximation// IEEE Trans. Commun. 1992. v.40. №8.

125. Lam Y.F, Li V.O.K. An Improved Algorithm for Performance Analysis Of Networks with Unreliable Components// IEEE Trans. Commun. 1986. COM-34. P.496-497.

126. Langlois F, Regnier J. Dynamic congestion control in circuit switched telecommunications networks// Proc. 13th ITC. Copenhagen. 1991.

127. Li V.O.K, Silvester J.A. Performance Analysis Of Networks with Unreliable Components// IEEE Trans. Commun. 1984. COM-32. P. 1105-1110.

128. Liew S.C, Lu K.W. A Framework for Characterising Disaster — Based Network Survivability// IEEE on Select. Areas in Commun. 1994. v.12. №1. p.52-57.

129. Lo V.M,Rajopadhye S, Gupta S,Keldsen D,Mohammed MA, Nitzberg B, Telle JA, Zhong X. OREGAMI: Tools for Mapping Parallel Computations to Parallel Achitectures// Intern Journ. of Parallel Programming. 1991. v.20. №3. P.237-270.

130. McQuillan J.M, Richer I, Rosen E.C. The New Routing Algorithm for the ARPANET//IEEE Trans.Commun. 1980. Com-28. P.711-719.

131. Martinec I, Stranadova V. An exact algorithm for a class of fixed-cost transportation problems// Economico -matematicky Obzor. 1983. v.19. №3. P.337-353.

132. Matula D.W. Concurrent flow and concurrent connectivity in graphs// Graph theory and its applications to Algorithms and Computer Sciences. N.Y.:J.Wiley, 1985, P. 543-559.

133. Mitra D., Gibbens RJ. State-dependent routing on symmetric loss networks with trunk reservation. Part II: asymptotics, optimal design// Ann. Oper. Res. 1992. v.35. P. 3-30.

134. Mitra D., Seery J.B. Comparative evaluations of randomized and dynamic routing strategies for circuit-switched networks // IEEE Trans. Commun. 1991. v.39. №.1.

135. Mitra D., Weiss A. The transient behaviour in Erlang's model for large trunc groups and various traffic conditions// Proc. 12th ITC. Torino. 1988.

136. Nash J.F. Non-cooperative Games//Annals of Math. 1951. 54. №2. P. 286-295.

137. Ott, T.J., Krishnan K.R. Separable routing: a scheme for state dependent routing of circuit switched traffic// Ann. Oper. Res. 1992. v. 35. P.43-68.

138. Papadimitriou C.H., Steiglitz K. Combinatorial Optimization, Algorithms and Complexity. Englewood Cliffs, NJ: Prentice Hall, 1982.

139. Perlman R. Fault-Tolerant Broadcast of Routing Information // Computer Networks. 1983. v.7. P.395-405.

140. Prindiville M., Rajasekaren M., Ross K.W. Efficient sequential simulation of large-scale loss networks. Tech. Rep., 1991, Dept. Comput. and Infor.Sci, Univ.Penn.

141. Provan J.S., Ball M.O. Computing Network Reliability inTime Polynomial in the Number of Cuts// Oper.Res. 1984. v.32. P.516—526.

142. Rockafellar R.T. Network flows and Monotropic Programming. New York: John Wiley & Sons, 1984.

143. Rosberg Z. Deterministic Routing in Buffered Channels// IEEE Trans. Commun. 1986. Com-34. P.504-507.

144. Rosen I.B. Existence and Uniqueness of Equilibrium Point for Concave N-Person Games// Econometrica. 1965. 33.3. P.520-534.

145. Ross K.W., Tsang D. Optimal circuit access policies in an ISDN environment: a Markov decision approach// IEEE Trans.Commun. 1989. v.37. P.934-939.

146. Sanso B., Soumis F., Gendreau M. On the evaluation of the telecommunications network reliability using routing models// IEEE Trans.Commun. 1991. v.39. №10.

147. Sarachik P.E. An effective Local Dynamic Strategy fo Clear Congested Multidestination Networks//IEEE Trans. Auto. Contr. 1982. AC—27. P.510-513.

148. Schwartz M., Stern T.E. Routing Techniques Used in Computer Communication Networks// IEEE Trans. Commun. 1980. Com—28. P.539-552.

149. Schwartz M. Telecommunications networks, protokols, modelling and analysis. — Reading, MA: Addison-Wesley, 1987.

150. Segall A. Advances in Verifiable Fail-Safe Routing Procedures// IEEE Trans. Commun. 1981. Com-29. P.491-497.

151. Smith R.L. Deferral strategies for a dynamic communications Network// Networks. 1979. v.9. №1. P.61-87.

152. Soloway S.A., Humblet PA. On distributed Network Protocols for Changing Topologies. Codex Corp., 1986.

153. Stone H.S. Multiprocessor Scheduling with the Aid of Network Flow Algorithms// IEEE Trans, on Software Engineering January 1977. SE-3(1). P. 85 93 .

154. Thaker G.H., Gain G.B. Interactions Between Routing and Flow Control Algorithms//IEEE Trans.Commun. 1986. Com-34. P.269-277.

155. Tow D.M. Network management recent advances and future trends// IEEE J. Select. Areas Commun. 1988. v.6. №.5. P. 732-741.

156. Towsley D. Queueing network models with state-dependent routing// J. ACM. 1980. v.27. №2. P.323-337.

157. Tsitsiklis J.N., Bertsekas D.P. Distributed Asynchronous Optimal Routing In Data Networks// IEEE Trans. Auto.Contr. 1986. AC—31. P.325-331.

158. Vasiliev N.S. Uniqueness of equilibrious routing of flows in ring networks// IF AC Simp. Large Scale Syst. Theory and Appl. London. July. 1995.

159. Vasiliev N.S. Routing's Control and equilibrium of flows in ring networks// 3-d.Europ. Cont. Conf.Rome. Sept. 1995.

160. Vasiliev N.S. Nash equilibrious routing in ring networksJ.Theory of Games and its Applications. 1997. v.? № 4. P. 221-234

161. Vasiliev N.S. Game theory algorithm for network's routing / / 4-th Int. Conf. Multicriteria and game problems under uncertainty. 1996. Orehovo-Zuevo. P. 127.

162. Vasiliev N.S, Fedorov V.V. Aggregation in networks. 1—st Moscow Intern. Conf. on Oper. Res. 1996. Moscow (BE( PAH), P.110-111.

163. Wanamaker D.M., Dorrance DA. Dynamically controlled routing field trial experience// Proc. Network Oper. Manag. Syst. Conf. New Orleans. LA. March. 1988.

164. Wang W, Saadawi T.N. Trunk congestion control in heterogeneous circuit switched networks// IEEE Trans. Commun. 1992. v.40. №7.

165. Wong E.W.M, Yum T.S. Maximum free circuit routing in circuit switched networks// Proc. IEEE INFOCOM. San Francisco. CA. 1990.

166. Yages B. Minimum cost routing for dynamic network models// Networks. 1973. v.9. №3. P.193-224.

167. Yum T.-K, Schwartz M. Comparison of routing procedures for circuit switched traffic in nonhierarchical networks// IEEE Trans. Commun. 1987. v.35. №5. P.535-544.

168. Zachary S. On blocking in loss networks// Adv. Appl. Prob. 1991. v.23. P.355—372.

169. Ziedins I.B, Kelly F.P. Limit theorems for loss networks with diverse routing// Adv. Appl. Prob. 1989. v.21. P.804-830.

170. Korilis,Y.A, Lazar A.A. and Orda A. Achitecting noncooperativC networks. -IEEE J. Select. Areas Commun., 1995, Vol. 13, No 7, pp. 1241-1251.

171. Korilis,Y.A, Lazar A.A. and Orda A. Capacity allocation under noncooperative routing. IEEE Trans. Automat. Contr., 1997, Vol. 42, No 3, pp. 309-325.

172. Пайк M. INTERNET в подлиннике (Энциклопедия инструментальных средств.) BHV, С.-Петербург, 1996.

173. Васильев Н.С. Об оптимальности по Парето равновесной маршрутизации кольцевой сети. Сб. трудов "Нелинейное моделирование сложных структур", ВЦ РАН, 1997, с.3-6.

174. Васильев Н.С., Федоров В.В. О задаче построения распределенного алгоритма маршрутизации некольцевой сети. Сб. трудов ИВВС РАН "Вычислит, машины с нетрадиц. архитект. Супер ВМ", 1997, №6, с.35-42.

175. Vasiliev N.S. Routing control under uncertainty in data networks. IF AC Symp. Large Scale Systems: Theory and Appl., Rion, Patras, 1998.

176. Васильев Н.С. О непротиворечивости принципов оптимальности по Парето и по Нэшу в задаче управления маршрутами передачи кольцевой сети. Ж. Вычисл. матем. и матем. физ., 1998, т.38, №4, с.592-597.

177. Vasiliev N.S. Nash equilibrious routing in ring networks. Intern. J. of Math. Game Theory and Algebra, 1998, v.7, 4, pp. 221-234.

178. Васильев H.C., Федоров В.В. Об одном подходе к построению распределенных алгоритмов маршрутизации некольцевых сетей. Сб. трудов ИВВС РАН "Вычислит, машины с нетрадиц. архитект. Супер ВМ", 1998, №7, с.69-87.

179. Васильев Н.С., Федоров В.В. О равновесных стратегиях маршрутизации в сетях передачи данных. Сб. трудов ф-та ВМиК МГУ "Числ. методы и вычисл. экспер.", 1998, с. 107-123.