Содержание к диссертации
Введение
1 Определение оптимального момента времени обращения к системе обслуживания 15
1.1 Постановка задачи 15
1.2 Модель для системы с двумя игроками 19
1.3 Равновесное по Нэшу решение задачи с двумя игроками . 21
1.3.1 Решение для экспоненциальной функции "комфортности" 25
1.3.2 Решение для параболической функции "комфортности" . 26
1.4 Модель для системы с числом игроков 31
1.4.1 Вид функции "комфортности" в случае равномерных стратегий игроков 32
1.4.2 Вид функции "комфортности" в случае экспоненциальных стратегий игроков 34
1.5 Результаты . 37
2 Оптимальная маршрутизация трафика в сети передачи данных 38
2.1 Задача оптимальной маршрутизации в вероятностной постановке 38
2.1.1 Равновесие в чистых стратегиях 40
2.1.2 Полностью смешанное равновесие в задаче с различными пользователями и одинаковыми каналами 42
2.1.3 Полностью смешанное равновесие в задаче с одинаковыми пользователями и различными каналами 43
2.1.4 Полностью смешанное равновесие в общем случае . 49
2.2 Задача оптимальной маршрутизации с разделяемым трафиком 52
2.2.1 Равновесие по Нэшу 53
2.2.2 Модель для системы с функциями задержки трафика на канале вида 58
2.2.3 Оптимальность равновесия по Нэшу для системы т параллельных каналов с функциями задержки трафика на канале вида -^ 60
2.3 Результаты 64
3 Справедливое разделение пропускной способности каналов сети 66
3.1 Критерий справедливости в задачах разделения пропускной способности 66
3.2 Маршрутизация и разделение пропускной способности каналов в открытой сети 69
3.2.1 Постановка задачи 69
3.2.2 Математическая модель 71
3.2.3 Сокращение размерности задачи 73
3.2.4 Схема численного решения задачи 74
3.2.5 Особенности реализации алгоритма решения 75
3.2.6 Численные эксперименты 76
3.3 Разделение пропускной способности каналов в линейной сети . 81
3.3.1 Постановка задачи 81
3.3.2 Случай параллельной передачи данных 86
3.3.3 Случай последовательной передачи данных 89
3.3.4 Схема приближенного решения задач 91
3.3.5 Численные эксперименты 92
3.4 Результаты 95
Заключение 97
Литература 100
- Решение для экспоненциальной функции "комфортности"
- Вид функции "комфортности" в случае экспоненциальных стратегий игроков
- Полностью смешанное равновесие в задаче с одинаковыми пользователями и различными каналами
- Критерий справедливости в задачах разделения пропускной способности
Введение к работе
Актуальность темы. В настоящее время в связи с повсеместным внедрением, ростом и объединением вычислительных сетей стали актуальными задачи повышения их производительности. С ростом числа пользователей и увеличением объема обрабатываемой и передаваемой в сетях информации все чаще возникают проблемы, обусловленные высоким уровнем загруженности узлов и каналов связи. Более того, если на первых этапах своего развития вычислительные сети предназначались преимущественно для обеспечения совместного доступа пользователей к ресурсам сети (файлам, принтерам и т.п.), где отсутствовали жесткие требования на ограничение задержки передачи данных, то сейчас по сети передается также и мультимедийная информация в виде потоков, требующих синхронизации (видеоизображение, аудиопоток), что делает неприемлемым возникновение задержек, приводящих к искажению получаемой информации. Один из примеров - срыв Интернет-трансляции солнечного затмения 29 марта 2006 г., подготавливаемой коллективом САО РАН [1]. За время трансляции было зарегистрировано 1 200 000 подключений (до 3000 в секунду, при норме в 250 подключений в секунду). Это привело к сбоям в работе сервера, десинхронизации и большим задержкам в передаче кадров. [2]
Один из путей решения таких проблем - наращивание мощности используемого оборудования, использование новых каналов связи с более высокой пропускной способностью, своевременное обновление оборудования с
развитием новых более эффективных технологий. Но такая стратегия развития, связанная с постоянным наращиванием ресурсов, требует соответствующих финансовых затрат и не всегда приносит ожидаемые результаты. [3] Поэтому важно также обеспечение более высокой производительности за счет эффективного использования вычислительных сетей путем решения задач оптимального распределения ресурсов сетей между пользователями.
В области прикладной теории вероятностей новый импульс получила теория систем массового обслуживания, в котором исторически исследования велись в контексте управления загрузкой телефонных линий связи [4]. С развитием информационных технологий активно разрабатываются такие направления, как теория очередей (queuing theory) и теория транспортной загрузки (traffic theory) в применении к анализу работы вычислительных сетей.
При решении задач оптимизации работы вычислительных сетей возникает ряд проблем, как практических, так и при построении математических моделей и разработке методик решения. Эти проблемы связаны с отсутствием возможности централизованного управления компонентами вычислительных сетей. Протоколы передачи данных в разных узлах сети не могут взамодей-ствовать друг с другом для поддержания определенного уровня общего потока. Более того, на практике они ведут себя "эгоистично" по отношению к свободным ресурсам каналов связи. [3] Пользователи вычислительных сетей также действуют в своих собственных интересах самостоятельно и несогласованно. Поэтому в задачах распределения ресурсов сети применение методов глобальной оптимизации часто оказывается неприемлемым, так как обычно нет возможности обеспечить выполнение получаемых оптимальных планов
использования ресурсов сетей (расписаний обращений к серверам, норм занимаемой пропускной способности каналов передачи данных и т.п.).
В последнее время в исследованиях, связанных с оптимизацией работы вычислительных сетей, стали применяться методы некооперативной теории игр п лиц [5, б, 7, 8, 9]. Это направление получило название "сетевые игры" (Networking Games, Noncooperative Networks) [10, 11, 12, 13, 14]. При этом каждый пользователь сети или узел, входящий в сеть, трактуется как некоторый игрок, а задача распределения ресурсов сети рассматривается как игра, в которой игроки, действуя оптимально, могут достигать равновесия -ситуации, в которой никому из игроков не выгодно отклоняться от своей стратегии.
Один из классов задач данного направления связан с управлением загруженностью серверов - узлов сети, обрабатывающих запросы клиентов и отвечающих на них. Здесь сервер рассматривается как система массового обслуживания, обрабатывающая поток пользовательских заявок. В зависимости от назначения и условий работы сервера-прототипа в рассматриваемой модели система может обрабатывать одновременно одну или несколько заявок, может иметь одну или несколько очередей, или же в случае занятости системы заявка получает отказ в обслуживании. В работах [15,16] исследуются модели, в которых дисциплина поступления заявок в систему определяется стратегиями игроков, стремящихся минимизировать время ожидания своих заявок в очереди на обслуживание. В моделях [17, 18, 19, 20] дисциплина поступления заявок задается сверху, а в качестве сратегии рассматривается схема выбора одной из очередей. В работах [21, 22] рассматриваются модели, в которых пользователь, зная длину очереди на обслуживание на мощном
сервере общего доступа, решает, отправлять ли свою заявку в очередь или выполнить ее на своей рабочей станции, стремясь минимизировать временные затраты.
Другой класс задач данного направления составляют задачи маршрутизации трафика, где пользователи, действуя в собственных интересах, самостоятельно выбирают свои маршруты, стремясь минимизировать задержку своего пересылаемого трафика. Здесь рассматриваются две базовые модели: модель Вардропа (Wardrop model) с произвольно разделяемым трафиком [23, 24, 25] и КР-модель (Koutsoupias, Papadimitriou) [23, 26, 27, 28, 29, ЗО, 31, 32, 33] с неделимым трафиком. В первой модели пользователи определяют количество трафика, посылаемого по каждому из маршрутов, а во второй - вероятности, с которыми может быть выбран каждый из маршрутов для отправки всего своего трафика. В работах, посвященных решению таких задач при задаваемом виде функций задержки трафика (например, линейных [24, 26, 33], квадратичных [32], полиномиальных [26, 29], произвольных выпуклых [34]), исследуется основной вопрос - насколько отказ от централизованного управления ухудшает систему, то есть насколько равновесные затраты всей системы в целом больше затрат в ситуации глобального оптимума.
К другому подклассу можно отнести задачи оптимальной маршрутизации трафика в сети. В отдельный подкласс таких задач можно выделить задачи определения схемы статической маршрутизации с справедливым разделением номинальной пропускной способности каналов сети между соединениями [35, 36, 37, 38]. В работе [39] схема статической маршрутизации в сети считается известной, и строится протокол контроля перегрузок, управ-
ляющий размером окна (TCPWindowSize) - количества пакетов, отправляемых до получения подтверждения о доставке при передаче по протоколу TCP [3, 40]. В перечисленных работах данного подкласса в качестве критерия оптимальности используется обобщенный критерий справедливости Валран-да (Walrand) [35], дающий, в зависимости от выбора задаваемого значения параметра справедливости, решение, близкое к глобально оптимальному, пропорционально или гармонически справедливому решению или к равновесию по Нэшу.
Во многих моделях, связанных с оптимизацией работы вычислительной сети, отдельного изучения требует вопрос возможного ухудшения качества работы сети при физическом наращивании мощности отдельных ее компонент. Этот вопрос в литературе получил название парадокса Браесса [41]. В частности, в задачах маршрутизации при добавлении нового канала могут увеличиться пользовательские затраты при отправке трафика [14,42,43]. Ряд ' работ [14, 44] направлен на нахождение характеристик добавляемого канала, таких чтобы гарантированно избежать возникновения парадокса Браесса. В работах [45, 46, 47] исследуется вопрос проявления и обнаружения данного парадокса в равновесных ситуациях в рамках модели Вардропа.
Цель диссертационной работы заключается в построении и исследовании математических моделей задач повышения производительности вычислительных сетей с помощью методов некооперативной теории игр. В основе исследуемых моделей лежит эффективное распределение ресурсов сетей между пользователями в условиях, когда пользователи действуют самостоятельно в собственных интересах по отношению к используемым ресурсам рабочего времени обслуживающих узлов сети и пропускной способности ка-
налов связи. В работе исследуются следующие основные задачи:
задача выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности";
задача оптимальной маршрутизации трафика в сети в вероятностной постановке с неделимым трафиком (КР-модель) и в постановке на основе модели Вардропа с разделяемым трафиком.
задача справедливого разделения пропускной способности каналов сети с применением обобщенного критерия справедливости Валранда;
Научная новизна работы заключается в применении методов некооперативной теории игр п лиц к решению задач оптимального распределения ресурсов сетей для повышения их производительности.
В постановке задачи выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 введено понятие функции "комфортности", для данной модели получен аналитический вид равновесного решения для для случая двух игроков. Для случая п + 1 > 3 игроков построен общий вид функции выигрыша и решены задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проведен анализ поведения системы при бесконечно большом количестве игроков.
В КР-модели задачи оптимальной маршрутизации трафика в сети для случая одинаковых каналов найдены линейные и квадратичные затраты системы в полностью смешанном равновесии. В этой же модели для случаев
различных каналов найдены линейные и квадратичные затраты системы в полностью смешанном равновесии, а также условия ухудшения такого равновесия при добавлении в систему нового канала. Для модели Вардропа доказана в общем виде связь равновесия по Нэшу с равновесием по Вардропу. Для случая с заданным видом функций задержки трафика /(^(х) = Yle&Ri с -fix) доказана равносильность определений равновесия по Нэшу и по Вардропу. Для частного случая с параллельными каналами доказана глобальная оптимальность равновесных по Нэшу ситуаций и для случая общедоступных каналов найдено равновесие.
Для задач справедливого разделения пропускной способности каналов сети предложены модели с применением обобщенного критерия справедливости Валранда. Разработано программное обеспечение для численного решения таких задач при задаваемых значениях параметра справедливости.
Практическую ценность в работе представляют предлагаемые математические методы анализа и повышения производительности используемых на практике вычислительных сетей путем эффективного распределения между пользователями ресурсов рабочего времени обслуживающих узлов сети и пропускной способности каналов связи.
Положения, выносимые на защиту. На защиту выносятся следующие положения.
Найдены равновесия в задачах выбора оптимального момента обращения игроков к системе массового обслуживания t/M/l/Q с учетом заданной функции "комфортности".
Найдены условия, при которых введение в параллельную сеть новых каналов связи ухудшает характеристики сети в полностью смешанном
равновесии по Нэшу. Получены условия, при которых равновесие по Вардропу совпадает с равновесием по Нэшу. Для модели Вардропа с параллельными каналами доказана глобальная оптимальность функции затрат системы в равновесии по Нэшу.
3. Построена и исследована модель справедливого разделения ресурсов пропускной способности в сетях передачи данных. Разработан комплекс программ для нахождения и визуализации оптимальных решений.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:
VI Международная петрозаводская конференция "Вероятностные методы в дискретной математике", Петрозаводск, 10-16 июня 2004 г., ИПМИ КарНЦ РАН.
Международный семинар "Optimal Stopping and Stochastic Control" (Петрозаводск, 22-26 августа 2005 г., ИПМИ КарНЦ РАН);
Российско-финская летняя школа "Dynamic Games and Multicriteria Optimiza 2-7 сентября 2006, Петрозаводск.
Всероссийская научная конференция "Научный сервис в сети Интернет: технологии параллельного программирования" (18-23 сентября 2006 г., г. Новороссийск).
По материалам диссертации опубликовано 9 работ, из них 4 статьи [48, 49, 50, 51] и тезисы 5 докладов [52, 53, 54, 55, 56].
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Во введении отражена
актуальность работы, приведен краткий обзор литературы по теме диссертации, поставлена цель исследования, обоснована новизна работы, сформулированы положения, выносимые на защиту, показана практическая ценность полученных результатов.
В первой главе рассматривается задача выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности". Для модели с двумя игроками находится аналитический вид равновесного решения и условия его допустимости. Рассматриваются частные случаи задачи с экспоненциальной и параболической функциями "комфортности", для которых проводится анализ существования допустимого равновесного решения. Для случая п + 1 > 3 игроков строится общий вид функции выигрыша и решаются задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проводится анализ поведения системы при бесконечно большом количестве игроков.
Во второй главе исследуется задача оптимальной маршрутизации трафика в сети в двух вариантах постановки: вероятностная модель задачи маршрутизации с неделимым трафиком, основанная на КР-модели, и модель с разделяемым трафиком, основанная на модели Вардропа. В рамках КР-модели рассматривается два случая равновесия по Нэшу: в чистых стратегиях и полностью смешанное равновесие. Для них находятся затраты системы и анализируются случаи ухудшения такого равновесия при добавлении в систему нового канала. В рамках модели Вардропа в общем виде доказывается связь равновесия по Нэшу с равновесием по Вардропу и анализируется модель с
заданным видом функций задержки трафика /гщ(х) = Y^eeRi с -Их)> для которой проверяется равносильность определений равновесия по Нэшу и по Вардропу. Для частного случая данной модели с параллельными каналами доказывается глобальная оптимальность равновесных по Нэшу ситуаций и для случая общедоступных каналов находится аналитический вид равновесия.
Третья глава посвящена исследованию модели задачи справедливого разделения пропускной способности каналов сети в двух вариантах постановки. Для задачи построения справедливой схемы распределения в сети потоков трафика от пользовательских узлов к узлам доступа к внешнему сетевому пространству приводится математическая модель и алгоритм численного решения методом допустимых направлений, а также результаты численных экспериментов по решению задач маршрутизации и разделения пропускной способности каналов для реальных примеров сетей. Также рассматривается математическая модель задачи разделения пропускной способности каналов линейной сети, учитывающая получаемую пользователями прибыль и затраты в результате использования сети для передачи данных. Для частных случаев данной модели с параллельной и последовательной схемами передачи данных аналитически строятся системы уравнений, решение которых дает решение поставленной задачи, и приводится алгоритм их численного решения и результаты вычислительных экспериментов, которые показывают, как равновесное решение задачи зависит от значения параметра справедливости.
В заключении представлен свод результатов, полученных в ходе исследований в рамках диссертационной работы. Общий объем диссертации составляет 107 страниц. Список литературы включает 64 наименования.
Решение для экспоненциальной функции "комфортности"
В данной главе рассматривается задача выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности".
В задаче рассматривается система массового обслуживания 7/М/1/0 со следующими характеристиками: дисциплина поступления заявок в систему не задана; время обслуживания очередной заявки является экспоненциально распределенной случайной величиной с параметром 1//І (/І 0); в каждый момент времени система способна обслуживать не более одной заявки; в системе отсутствует очередь: если на момент поступления очередной заявки в системе уже обслуживается заявка, то поступившая заявка получает отказ в обслуживании; для поступающих заявок задана функция "комфортности" С(), отражающая для заявки степень желательности начала обслуживания в системе в момент t. В качестве примеров таких систем можно привести используемые во многих организациях сервисы общего доступа сотрудников к ресурсам Internet и Intranet: dial-up сервера удаленного доступа, терминалы для работы с электронной почтой и т.д. Другой пример - это различные сетевые сервисы бронирования мест (транспорт, гостиницы и т.п.) для которых важна гарантия того, что одно и то же место не будет забронировано одновременно двумя клиентами. Один из вариантов решения - установление разрешения на обслуживание не более одного соединения, в данном случае - оформление одновременно не более одного заказа. Аналогичная задача, в которой игроки выбирают момент обращения в системе, обслуживающей в каждый момент времени не более одной заявки, была рассмотрена в [15]. Авторы решают задачу оптимизации работы системы обслуживания с одной очередью, где критерием оптимальности является минимизация ожидаемого времени ожидания заявки в очереди, а искомой стратегией - вероятностное распределение моментов поступления заявок на временном отрезке работы системы. В [19] также минимизируется ожидаемое время ожидания заявки в очереди, но дисциплина поступления заявок считается заданной и представляет собой пуассоновский поток, а в качестве стратегии рассматривается схема выбора одной из двух очередей в системе для каждой из поступающих заявок. К похожим задачам относятся задачи угадывания одного из значений в последовательности случайных величин [57, 58].
В модели, рассматриваемой в данной работе, введена функция "комфортности". "Комфортность" работы пользователей зависит от времени суток и может выражать прибыль или потери пользователя от выполнения заявки в момент t. В качестве примера возможной интерпретации функции "комфортности" можно рассмотреть систему доступа пользователей в сеть Internet через один общий dial-up сервер удаленного доступа с одним модемом, обслуживающий одновременно не более одного пользователя. При этом пользователь оплачивает только время использования телефонной линии. Для простоты будем считать, что все пользователи работают с одним и тем же Internet-узлом, например, загружают на свои компьютеры обновления программного обеспечения с официального Web-сервера производителя. Степень загруженности каналов связи и узлов Internet в течение суток изменяется, соответственно меняется пропускная способность каналов и время отклика узлов. Это влияет на время выполнения заявок пользователя. В данном случае это время загрузки файлов с Internet-узла на компьютер пользователя, которое пропорционально его затратам на оплату услуг телефонной компании. Если рассматривать снижение этих затрат как критерий "комфортности", то в качестве функции "комфортности" можно взять функцию, оценивающую скорость передачи информации между dial-up сервером удаленного доступа и используемым Internet-узлом в каждый момент времени. В численном виде приближение такой функции можно получить, фиксируя значения оценок скорости прохождения пакета информации через равные промежутки времени в течение суток. При этом значение скорости можно оценить как l/tansw(t), где tansw(t) - время отклика в миллисекундах Internet-узла, которое выводит программа ping, запускаемая на dial-up сервере удаленного доступа в момент времени t. Тогда такая оценка представляет собой число пакетов в миллисекунду, которые могут быть переданы от Internet-узла до dial-up сервера удаленного доступа. Пример графика такой функции представлен на рис. 1.1. Значения данной функции "комфортности" отражают результаты измерений через каждые 20 минут в течение суток скорости передачи данных от узла download.com к dial-up серверу удаленного доступа КарНЦ РАН.
Вид функции "комфортности" в случае экспоненциальных стратегий игроков
В данной главе рассмотрена задача выбора оптимального момента обращения игроков к системе массового обслуживания /Af/l/0 с учетом заданной функции "комфортности". Для случая двух игроков построена математическая модель, найден аналитический вид равновесного решения и условия его допустимости. Для частных случаев задачи с экспоненциальной и параболической функциями "комфортности" проведен анализ существования допустимого равновесного решения.
Для случая п +1 3 игроков построен общий вид функции выигрыша и решены задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проведен анализ поведения системы при бесконечно большом количестве игроков.
Результаты данной главы были представлены на Международном семинаре "Optimal Stopping and Stochastic Control"(Петрозаводск, 22-26 августа 2005 г., ИПМИ КарНЦ РАН).
В данной главе исследуется вопрос оптимальной маршрутизации трафика в сети передачи данных в условиях, когда пользователи, действуя в собственных интересах, самостоятельно выбирают свои маршруты. Рассматриваемая в данном параграфе схема маршрутизации основана на КР-модели (Koutsoupias, Papadimitriou) [23, 26, 27, 28, 29, ЗО, 31, 32, 33] с неделимым трафиком. Критерием оптимальности является минимизация ожидаемой задержки пересылаемого трафика.
Рассматривается система п пользователей и т параллельных каналов. Каждый пользователь і = 1,..., п собирается отправить трафик объемом Wi по одному из каналов. Для каждого канала I = 1,...,т задана пропускная способность с\. При отправке трафика объемом w по каналу с пропускной способностью с задержка на канале определяется как w/c.
Каждый пользователь действует в своих собственных интересах и стремится занять тот канал, на котором задержка его трафика будет наименьшей. Чистой стратегией для пользователя і является выбор канала /, по которому он собирается отправить свой трафик. Тогда вектор L = (li,..., ln) представляет собой профиль чистых стратегий пользователей, где /г- - номер канала, выбранного пользователем і. Смешанной стратегией для него является вероятностное распределение pi = (pj,... ,pf), где р\ - вероятность, с которой пользователь і выбирает і Матрица Р, образованная векторами р;, представляет профиль смешанных стратегий пользователей. В случае чистых стратегий для пользователя г задержка трафика на используемом им канале /j определяется как Аг- = k k=ti—.Определение 2.1 Профиль чистых стратегий (/i,..., ln) называется равновесием по Нэшу, если для каждого пользователя г \ = min ——fc i: =J—.
Для смешанных стратегий определяется ожидаемая задержка трафикапользователя і в случае использования им канала /, равная А = — =м .
Минимальная ожидаемая задержка пользователя і равна Aj = min \\. Определение 2.2 Профиль Р называется равновесием по Нэшу, если для каждого пользователя і для любого из используемых им каналов справедливо: А- = \ если р\ О, и \\ Aj если р\ — 0.
Определение 2.3 Смешанное равновесие Р называется полностью смешанным равновесием, если каждый пользователь выбирает каждый канал с положительной вероятностью, то есть для любого г = 1,...,п и для любого I = 1,..., т р\ 0.
А; определяет минимальные возможные индивидуальные затраты каждого пользователя і от пересылки своего трафика, который, действуя в своих личных интересах, выбирает стратегии, обеспечивающие ему такое значение ожидаемой задержки. Затраты системы (social costs) характеризуют общие затраты, которые несет система в целом в результате эксплуатации каналов. В качестве функции затрат системы SC(w, с, L) для чистого профиля могут быть рассмотрены следующие варианты:
Полностью смешанное равновесие в задаче с одинаковыми пользователями и различными каналами
Исследуем возможность проявления парадокса Браесса в данной модели, то есть возможность возникновения такой ситуации, когда добавление в систему дополнительного канала ухудшает полностью смешанное равновесие, то есть увеличивает затраты системы для полностью смешанного равновесия. Будем считать, что в исходной системе полностью смешанное равновесие существует, то есть выполнено с\{т + п — 1) С. Добавление нового канала не должно нарушать существование полностью смешанного равновесия, то есть будем рассматривать добавление такого канала CQ, что выполнено Со(т + п) С + со и ci(m + п) С + CQ.
Теорема 2.1 В модели с п одинаковыми пользователями и т различными параллельными каналами линейные затраты системы в полностью смешанном равновесии увеличиваются при добавлении нового канала с пропускной способностью т+„_1 со такого, что выполнено со(т+п) С+со и с\(т + п) С + CQ.
Доказательство. Пусть F - ситуация полностью смешанного равновесия в модели с п одинаковыми пользователями и т различными параллельными каналами. Пусть добавили канал с пропускной способностью CQ, И пусть FQ -полностью смешанное равновесие в полученной системе.
Тогда для линейной функции изменение затрат системы: Данная разность положительна, если Ссо(2т+п— 1) —С2—mcl(m+n—1) 0. Левая часть данного неравенства представляет собой параболическую функцию по со с отрицательным коэффициентом при с2,, поэтому положительные значения данной функции будут находиться между ее двумя корнями ( _1 и . Тогда при добавлении канала с пропускной способностью m?n_l CQ линейные затраты системы увеличатся.
Пример 3.5 Рассмотрим систему с 4 пользователями и 2 параллельными каналами с пропускной способностью 1. Полностью смешанное равновесие - ситуация, в которой все равновесные вероятности равны 0.5. Равновесные линейные затраты системы равны 4. При добавлении канала с пропускной способностью со 1 полностью смешанное равновесие существует и равновесные вероятности равны 3 +2). Равновесные линейные затраты системы в новой системе равны -3 "7 Z 4.
Теорема 2.2 В модели с п одинаковыми пользователями и т различными параллельными каналами добавление нового канала либо не увеличивает квадратичные затраты системы для полностью смешанного равновесия, либо делает невозможным существование полностью смешанного равновесия.
Доказательство. Пусть F - ситуация полностью смешанного равновесия в модели с п одинаковыми пользователями и т различными параллельными каналами. Пусть добавили канал с пропускной способностью Со, и пусть FQ -полностью смешанное равновесие в полученной системе. Для квадратичной функции изменение затрат системы:
Данная разность будет положительной при добавлении канала Со mFn_v При этом для допустимости полностью смешанного равновесия FQ необходимо и достаточно выполнения со(т + п) С + CQ И с\{т + п) С + (. Для проявления парадокса Браесса добавляемый канал должен иметь пропускную способность co(m+n—1) С, откуда co(m+n) С+со co(m+n), что приводит к противоречию.
Рассмотрим общий случай модели, в которой пользователи могут отправлять трафик различного объема по каналам с различной пропускной способностью. В качестве затрат системы будем рассматривать функции линейных затрат системы. Пусть W = YA=I wi общий объем пользовательского трафика, С = YA=\ CI суммарная пропускная способность системы каналов.
Для этого случая справедлива следующая теорема, дающая условие существования полностью смешанного равновесия и значения равновесных вероятностей.
Критерий справедливости в задачах разделения пропускной способности
В данной главе рассмотрены две модели маршрутизации и справедливого разделения пропускных способностей каналов сети между пользователями. В качестве критерия оптимальности используется обобщенный критерий справедливости Валранда (Walrand).
Параграф 3.2 данной главы посвящен задаче маршрутизации и разделения пропускной способности каналов в открытой сети. Практическим примером такой задачи является назначение владельцами крупных локальных или региональных сетей своим клиентам (организациям, населенным пунктам) гарантированной величины пропускной способности (скорости) доступа по каналам своей сети к внешнему сетевому пространству. В данной модели пользователи сети из своих узлов получают доступ к внешнему сетевому пространству через узлы внешнего доступа данной сети. Задача заключается в составлении оптимальной схемы маршрутизации соединений внутри сети и выделения соединениям части пропускной способности используемых ими каналов. Критерием полезности для каждого пользователя является выделяемая ему суммарная пропускная способность для его соединений к узлам внешнего доступа. В параграфе 3.3 в задаче разделения пропускной способности каналов сети между внутрисетевыми соединениями критерием полезности для каждого пользователя является чистая прибыль, получаемая пользователем от использования сети. Если в первой модели осуществляется формальное разделение ресурсов каналов между пользователями, то в данной модели строится схема оптимального использования данных ресурсов. Здесь учитывается влияние уровня загрузки канала на время прохождения данных по нему и, следовательно, на плату за его использование. Данная модель рассматривается для упрощенного варианта топологии сети - изолированной сети с общей шиной (линейной сети) с известной заранее схемой внутрисетевых соединений. Задача заключается в оптимальном определении пользовательских квот на объем отправляемых данных.
В обеих моделях в качестве критерия оптимальности используется обобщенный критерий справедливости Валранда, предложенный в работах [36, 37, 38, 39]. Рассматривается игра Г = (N,X,f), в которой N игроков определяют значения вектора х = (xi,.. .,х ) из допустимого выпуклого множества X С RN. Для каждого из игроков задана fo(x) - вогнутая и возрастающая по ХІ функция полезности і игрока, значение которой он хочет максимизировать.
Определение 3.1 [36, 37, 38] При заданном значении а справедливым решением в игре Г называется решение задачи где а - параметр справедливости.
При этом в [39] показано, что при а — 0 решение стремится к глобально оптимальному; при а -» со решение приближается к равновесию по Нэшу; решение, получаемое при о —» 1, называется пропорционально справедливым, а при а —» 2 - гармонически справедливым. То есть данный обобщенный критерий позволяет применять один и тот же метод для решения задач с различными критериями оптимальности. Рассмотрим открытую сеть передачи данных, состоящих из следующих компонентов. Набор узлов, в которых находятся пользователи сети. Каждому узлу соответствует один пользователь. Набор узлов, предоставляющих доступ к внешнему сетевому пространству. Набор переходных узлов, которые служат точками объединения/разветвления каналов связи. Набор каналов связи с ограниченной пропускной способностью, передающих данные в обоих направлениях. Будем считать, что внутрисетевые соединения (передача данных между пользователями только в пределах сети) отсутствуют. Пользователи стремятся получить доступ из своей сети к внешнему сетевому пространству. В сети для каждого пользователя образуются виртуальные соединения между данным пользователем и узлами доступа во внешнее сетевое пространство, по которым идет передача его исходящего и входящего трафика. Каждое такое соединение представляет собой объединение всех сеансов связи между узлом пользователя и узлами внешнего доступа по некоторым маршрутам через каналы связи и другие узлы. Будем считать, что такие сеансы возникают постоянно и их суммарные требования к ресурсам пропускной способности сети остаются неизменными. Для определенности считаем каждое соединение ориентированным от пользователя к узлам внешнего доступа. Тогда соединения могут быть представлены как потоки по сети от пользователей к узлам внешнего доступа. Размер потока определяется как часть ресурсов пропускной способности сети, которая выделяется пользователю. Пользователи генерируют потоки, проходящие через цепи каналов связи к поглощающим их узлам внешнего доступа. При этом для потоков каждого пользователя все промежуточные узлы на маршрутах от узла-источника к поглощающим узлам являются транзитными. Такими узлами могут быть как переходные узлы, так и узлы-источники других пользователей. Каждый поток считаем бесконечно разделяемым. Это означает, что входящие в транзитный узел по разным каналам потоки от одного пользователя могут быть объединены и перераспределены в любых пропорциях в новый набор исходящих потоков.
