Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях Эдиториал УРСС, Москва, 1999 Работа поддержана РФФИ, проект N.98-01-14090

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

Проведенные исследования и издание книги были поддержаны грантами РФФИ по проектам NN. 95-01-00232, 96-01-00786, 98-01-00233, 98-01-14090.

Введение (136kb).
Глава 1. Задача анализа многопродуктовой потоковой сети в случае неточно известного вектора требований.
1. Описание модели ``МП-сеть" (110kb).
2. Обобщенные постановки задачи анализа допустимости для неточно известных требований (105kb).
2.1. Гарантированный подход.
2.2. Слабая постановка.
2.3. Смешанные постановки.
3. Обеспеченность потоковых требований как мера допустимости МП-сети. Оценки для обобщенных постановок (140kb).
3.1. Конкурентное распределение потоков и максиминная обеспеченность потоковых требований (о.п.т.).
3.2. Верхняя оценка максиминной о.п.т. для неточно известных требований.
3.3. Гарантированное значение максиминной о.п.т.
Глава 2. Задача анализа предельных возможностей сети по обеспечению требований пользователей.
1. Суперконкурентное (нормативное) распределение потоков (137kb).
1.1. Постановка задачи.
1.2. Сверхконкурентное распределение потоков.
1.3. Лексикография уровней о.п.т. сверхконкурентных распределений потоков.
1.4. Свойства суперконкурентного решения.
2, 3. Об оценках уровней максиминной обеспеченности в случае неточно известных требований. Устойчивость суперконкурентного решения (223kb).
4. Методы поиска суперконкурентного решения (110kb).
Глава 3. Задача анализа многопродуктовой потоковой сети в случае неизвестного вектора требований.
1. Многокритериальная постановка задачи анализа (154kb).
2. Методы аппроксимации множества эффективных мультипотоков с помощью обратной логической свертки (167kb).
Глава 4. Задача анализа многопродуктовой потоковой сети для случайного вектора требований.
1. Вероятностные формулировки задачи анализа МП-сети (170kb).
2. Стохастические формулировки задачи анализа МП-сети (197kb).
Глава 5. Задача анализа многопродуктовой потоковой сети со случайной пропускной способностью.
1. Вероятностные формулировки задачи анализа МП-сети для случайной пропускной способности ребер (205kb).
2. Стохастические формулировки задачи анализа МП-сети для случайной пропускной способности ребер (133kb).
Глава 6. Задача анализа многопродуктовой потоковой сети при неслучайных потерях пропускной способности.
1, 2. Специфика неслучайных потерь пропускной способности. Гарантированный уровень обеспеченности требований как скалярная характеристика уязвимости МП-сети (122kb).
3. Задача анализа уязвимости МП-сети в случае неизвестного вектора требований (135kb).
4. Методы решения линейной многокритериальной задачи анализа уязвимости (140kb).
Глава 7. Задача нормативного анализа уязвимости многопродуктовой потоковой сети.
1. Постановка задачи (129kb).
2. Некоторые примеры решения задачи (86kb).
3. Теоретико-графовые характеристики уязвимости и живучести многопользовательских сетевых систем (143kb).
Заключение.
Список литературы (141kb).

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

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

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

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