Асимптотические и численные методы в исследовании моделей сетей связи тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Введенская, Наталия-Никита Дмитриевна

• Введенская, Наталия-Никита Дмитриевна
• доктор физико-математических наук
• 2001

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

Введение

Актуальность темы исследования

Краткий обзор работ по тематике исследования

Цель исследования

Методы исследования

Научная новизна

Теоретическая и практическая ценность

Апробация работы

Публикации

Структура и объем

Краткое содержание работы

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

Экспоненциальная длина обслуживания сообщения

1.1. Описание задачи

1.2. Схема доказательств, обозначения, формулировка теорем

1.3. Свойства решений некоторых дифференциально-разностных уравнений

1.4. Доказательство Теоремы 1.

1.5. Доказательство Теорем 1.3-1.

Глава 2. Неэкспоненциальное распределение длин сообщений

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

2.2. Дискретный случай, формулировка теорем

2.3. Доказательства Теорем 2.1 - 2.

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

2.5. Доказательства Теорем 2.6 - 2.

Глава 3. Система с прерыванием источников сообщений

3.1. Описание задачи

3.2. Обозначения, формулировка теорем

3.3. Доказательство Теоремы 3.

3.4. Доказательства Теорем 3.2, 3.3, 3.

3.5. Численная оценка о^

3.6. Несколько групп приборов

Глава 4. Модель с несколькими станциями.

Сети типа быстрых сетей Джексона

4.1. Модель с несколькими станциями. Описание задачи

4.2. Формулировка теорем

4.3. Доказательство Теорем 4.1-4.

4.4. Численная оценка а^

4.5. Модель сети типа быстрых сетей Джексона

4.6. Достаточные условия существования единственного стационарного решения задачи (4.20), (4.19)

Глава 5. Большая система обслуживания с передачей многопакетных сообщений

5.1. Система с параллельными приборами

5.2. Передача закодированных сообщений

5.3. Численные результаты

5.4. Расчеты для системы

5.5. Ненадежная передача

5.6. Системы с небольшим числом приборов

5.7. Полный граф. Модель сети

5.8. Примеры расчетов

Глава 6. Стек алгоритм множественного доступа

6.1. Модель системы

6.2. Простейшие варианты стек алгоритма

6.3. Другие модели системы

6.4. Задержка пакетов

6.5. Исследование решений уравнений для длин сеансов и задержек

6.6. Закритическая область входных потоков

6.7. Результаты численных расчетов для закритических значений Л

6.8. Метод вычислений в закритической области

6.9. Два канала. Передача приоритетных сообщений 161 Список литературы

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

Актуальность темы исследования

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

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

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

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

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

Краткий обзор работ по тематике исследования.

Гипотеза о независимости приборов или более сильная гипотеза о пуассо-новском характере потоков в сети рассматривалась и доказывалась во многих работах, начиная с работ Клейнрока [57, 58] где предполагается, что при передаче сообщений от прибора к прибору времена обслуживания каждый раз независимы и экспоненциально распределены. Упомянем некоторые из работ, где проводилось асимптотическое рассмотрение больших сетей, обширная литература приведена, в частности, в этих работах.

Звездообразные системы были рассмотрены в работах Р.Л. Добрушина и Ю.М. Сухова, [36, 37] и М.Я. Кельберта и Ю.М. Сухова [55]. В этих работах доказана асимптотическая независимость очередей. Отметим также обзоры, относящиеся к 80-ым годам [38, 55]. В работах Ф.П. Келли [53] и Ф.П. Келли и И.Б. Зидинса [54], а также в работе М.Ю. Крадинова [59] асимптотический подход использовался при изучении сетей с потерями. В работе А.Л. Столяра [78] рассматривалась модель замкнутой сети Джексона. Связь задач теории массового обслуживания и статистической физики обсуждалась в докладе Р.Л. Добрушина [35]. Аналогия между задачами статистической физики и сетями связи использовалась в работах [4, 48]. Близкие идеи (гипотеза о хаосе) разрабатывались в работе [34]. Большие сети Джексона с произвольным распределением времени обслуживания изучаются в работе Ф.И. Карпелевича, и Ф.Н. Рыбко [50].

Надо специально отметить, что постановка многих новых задач в теории массового обслуживания навеяна быстрым развитием техники связи. В настоящее время большой интерес приобрели вопросы динамической маршрутизации dynamic routing), т.е. вопросы о выборе такого, зависящего от состояния сети на данный момент, маршрута сообщения в сети, который минимизирует время доставки сообщения или загрузку буфера прибора. При этом полной информации о состоянии сети может и не предполагаться , т.к. сбор и использование полной информации мало реальны (впрочем, "из практики" известно, что даже ограниченный объем знаний о состоянии системы может помочь существенно улучшить ее работу). Другой подход к этим вопросам - стремление к равномерной, сбалансированной нагрузке на приборы (load balance).

Некоторые из задач о динамической маршрутизации рассматривались ранее. Назовем работу Л. Флатто и Ч.П. МкКина [86] о двух приборах, на которые направлен пуассоновский поток заявок с независимыми и экспоненциально распределенными временами облуживания, причем при поступлении в систему сообщение направляется на прибор с меньшей очередью . Известна работы В.А. Малышева (см. [85, 84]), в которой задачи об очередях соотнесены с задачами о случайном блуждании. В недавней работе Р. Фоли и Д. МкДоналда [87] решена задача о выборе кратчайшей очереди в случае, когда в системе имеется J приборов и несколько потоков, направленных на различные группы приборов. Обобщение этой задачи на сеть из двух приборов дано в работе И.Курковой [60]. Здесь после обслуживания сообщение с некоторой вероятностью остается в сети и снова посылается на обслуживание, при этом оно всегда посылается на наименее загруженный прибор Приводятся условия неперегруженности такой сети В работе Дж. Мартина и Ю. Сухова [65], которая явилась развитием некоторых из представленных в настоящей работе результатов, рассмотрены сети связи, названные авторами "быстрыми сетями Джексона". А именно, рассмотрена открытая сеть Джексона, в которой в каждом из J узлов - станций -имеется N приборов. Поступающее (по обычным правилам сети Джексона) на станцию j, j = 1,., J, сообщение выбирает rj, rj > 1, приборов и направляется в тот из них, где очередь короче. Показывается, что условия неперегруженности сети совпадают с условиями для обычной сети Джексона, но в быстрой сети при N У оо вероятности длинных очередей убывают сверхэкспоненциально.

Гипотеза о пуассоновском характере потоков в системе часто используется для рассчетов параметров работы системы. Так, эта гипотеза позволила Г.А. Кабатянскому и Е.А. Круку [46] рассмотреть достоинства по-пакетной - дейта-грамной - передачи многопакетного сообщения в системе со многими путями. В частности, в [46] показано, что при справедливости гипотезы закодированное сообщение может быть доставлено быстрее незакодированного, если сообщение восстанавливается по нескольким пакетам, пришедшим быстрее других.

На примере достаточно большой сети этот эффект был проверен с помощью компьютерного моделирования [75,76,77]. Ю.М. Сухов и Д. Розе [79] показали справедливость пуассоновской гипотезы для большой сети - полнодоступного графа - в которой передаются многопакетные сообщения.

С развитием современных быстрых сетей связи, а также в связи с развитием беспроволочных, например, сотовых сетей, стали важны вопросы доступа пользователей в сеть. Эти вопросы привлекают большое внимание теоретиков. В частности, много работ посвящено случайному доступу в сеть большого числа пользователей. Наряду с разработкой алгоритмов доступа типа обобщенного алгоритма ALOHA [1] все большую привлекательность приобретают стек-алгоритмы множественного доступа [88, 91]. Основы их изложены, например, в обзоре Б.С. Цыбакова [89], в статьях Г. Файоля, П. Флайолета, М. Хофри [83], Ф. Жакэ [41].

Цель исследования.

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

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

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

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

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

Методы исследования.

Рассматриваемые нами модели систем массового обслуживания с конечным числом N приборов и с экспоненциальным или эрланговским распределением времени обслуживания описываются цепями Маркова со счетным числом состояний. При условии неперегруженности эти цепи являются эргодическими цепями. Сходимость марковских процессов к предельной динамической системе ^ —>■ оо) на любом конечном отрезке времени выводится из известных теорем о том что сходимость марковских процессов следует из сходимости соответствующих производящих операторов [40]. Для доказательства сходимости последовательности стационарных распределений к неподвижной точке предельной динамической системы доказывается равномерная по N компактность допредельных стационарных распределений. В этих доказательствах ис-пользуюся свойства допредельных цепей Маркова и свойства предельной динамической системы. Доказательствам сходимости стационарных распределений предшествует изучение свойств предельной динамической системы, которая задается нелинейной системой дифференциально-разностных или функциональных уравнений. В этой части используются методы теории дифференциальных уравнений.

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

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

Научная новизна.

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

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

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

Кроме того рассмотрена система с непуассоновским потоком сообщений; с помощью подобных потоков нередко моделируется самоподобный поток [90, 42].

2. Рассмотрена система обслуживания, в которой имеется 3 групп по N приборов в каждой (эти группы называются станциями), на систему поступает пуассоновский поток сообщений; время обслуживания сообщений распределено экспоненциально. При поступлении сообщения случайно выбирается несколько приборов (может быть из различных станций) и заявка направляется в тот из них, где очередь меньше. Приводятся условия неперегруженности системы и показывается, что при выполнении этих условий, в пределе, при N —> со, вероятности длинных очередей на приборах убывают сверхэкспоненциально.

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

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

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

5. Исследуется стек алгоритм свободного случайного множественного доступа в широковещательный канал. Рассматривается как случай неперегру-женной системы, когда интенсивность входного потока меньше критической, так и случай закритической нагрузки. Отметим, что протокол стек алгоритма осуществляет доступ в канал в порядке "первым пришел - последним обслуживаешься" (LIFO) с некоторой рандомизацией. Показывается, что применение рассмотренных методов может ускорить успешную передачу сообщения. Так, использование нескольких каналов приоритетными сообщениями ускоряет их передачу.

Теоретическая и практическая ценность.

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

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

Интересны справедливость гипотезы о (предельной) независимости приборов в системе с динамической маршрутизацией и справедливость пуассоновской гипотезы в системе с дейтаграмной передачей сообщений.

Выделен новый класс дифференциальных и функциональных уравнений, для которых рассматривается предельное (при t —У оо) поведение решений начально-краевой задачи.

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

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

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

Апробация работы

Результаты работы докладывались и обсуждались на семинарах лаборатории P.JI. Добрушина и лаборатории Б.С. Цыбакова в ИППИ РАН в 1990-2000 гг., на семинарах лаборатории сетей связи Дельфтского технологического университета (Нидерланды) в 1994-1996 гг., на семинарах Дублинского института высших исследаваний (Ирландия) в 19961999 гг., на семинарах Статистической лаборатории Кэмбриджского университета (Великобритания) в 1996-1999 гг., на семинарах в Национальном институте исследований по информатике и автоматике в Рокконкуре (Франция) в 1997-1999 гг., на семинаре кафедры параллельных вычислений Паденборгского университета (Германия) в 1999 г., на VI международном симпозиуме по теории информации в Ташкенте, 1984 г., на Всесоюзном семинаре по вычислительным сетям в Риге в 1986 г., на I Всесоюзной конференции по информации и связи в Минске в 1989 г., на 5-ом Советско-Шведском международном воркшопе "Сверточные коды, связь с многими пользователями" в Москве в 1990 г. на Всесоюзной конференции "Системы множественного доступа" в Минске в 1991 г., на V совещании по распределенным вычислительным сетям (CDS-92), Москва, 1991. на 6-ом Шведско-Советском международном воркшопе "Сверточные коды, связь с многими пользователями" в Молле (Швеция)" в 1993 г., на международном семинаре " Digital Communications" в Цюрихе (Швейцария) в 1994 г., на 5-ом международном симпозиуме " Fifth IEEE Internat. Symposium on PIMRC'94" в Нидерландах в 1994 г., на 16-ом Симпозиуме по теории информации стран Бенелюкса в Нидерландах в 1995 г., на 7-ом Российско-Шведском международном воркшопе "Сверточные коды, связь с многими пользователями" в Петербурге в 1995 г., на международном семинаре "Digital Communications" в Цюрихе (Швейцария) в 1996 г., на 17-ом Симпозиуме по теории информации стран Бенелюкса в Нидерландах в 1996 г., на воркшопе " Statistical Mechanics of Large Networks" в Национальном институте исследований по информатике и автоматике в Рокконкуре (Франция) в 1996 г., на международной конференции "Distributed Computer Communication Networks" в Тель-Авиве (Израиль) в 1996 г., на Симпозиуме "1997 IEEE Int. Symp. on Information Theory" в Ульме (Германия^ 1997 г., на международной конференции по дифференциальным и функциональным уравнениям в Москве в 1999 г., на Европейской конференции TMR network "Нелинейные параболические уравнения" в Тель-Авиве (Израиль) в 2000 г.

Публикации. По материалам диссертации опубликовано 37 работ.

Структура и объем.

Диссертация состоит из оглавления, введения, шести глав и библиографии, текст содержит 30 рисунков и 15 таблиц, общий объем 171 страница.

Краткое содержание работы

В главе 1 рассматривается несколько задач о динамичаской маршрутизации в системе с простой топологией. Доказательства этой главы лежат в основе доказательств глав 2-5 и поэтому мы остановимся на главе 1 подробнее. До недавнего времени строгих математических публикаций, в которых рассматривалась бы динамическая маршрутизация в большой системе массового обслуживания не было. По-видимому, первой была совместная работа [24], ей предшествовали предварительные сообщения [21, 23].

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

А 1

Рис. 0.1

Эту модель мы будем называть основной модель или моделью А). Ей и ее обобщениям посвящены первые главы настоящей работы. Отметим, что несколько позже работы [24], та же модель без строгого доказательства была рассмотрена в [68].

Оказывается, что если Л < 1, то система описывается эргодической цепью Маркова, и что можно исследовать асимптотическое распределение длин очередей при N —¥ оо. В пределе, при N оо, в стационарном состоянии с ростом длин очередей их вероятности убывают сверхэкспоненциально. Если выбор делается из двух приборов, то в пределе вероятность того, что в стационарном состоянии очередь не короче чем к стремится к величине а*, которая задается явной формулой: а* — л

Условие Л < 1 естественно: чтобы система не была перегружена нагрузка на прибор в среднем не должна превышать 1. А сверхэкспоненциальное убывание хвоста распределения вероятностей длин очередей в асимптотической задаче, при числе приборов N —> оо, кажется на первый взгляд неожиданным. В самом деле, здесь выбор делается всего из двух приборов, и это дает сверхэкспоненциальное убывание, тогда как если каждое сообшение посылается на случайно выбранный прибор (и все приборы равновероятны), то, как хорошо известно, в такой системе в стационарном состоянии с ростом длин очередей их вероятности убывают экспоненциально (такая система эквивалентна системе, в которой имеется N пуассоновских потоков интенсивности Л, и каждый из них обслуживается своим прибором. Рассмотрение этой системы эквивалентно рассмотрению системы Si с одним прибором). Здесь вероятность ак того, что очередь не короче чем к, задается формулой: ак = \к.

Сверхэкспоненциальное убывание вероятностей больших очередей при выборе всего из двух очередей в некотором смысле аналогично росту числа шаров в урнах, рассмотренному в [3]. В этой работе показано, что если при последовательном размещении N шаров в N урнах (здесь N велико, N —> оо) каждый раз случайно выбирается две урны и шар кладется в ту, где шаров меньше, то с большой вероятностью (1 — о(1)) в наиболее заполненной урне окажется In In N/ In 2+0(1) шаров. Напомним, что если каждый шар кладется в случайно выбранную урну, то с вероятностью 1 — 0(1/N) в наиболее заполненной урне окажется In iV/ In In N(1 + o(l)) шаров.

Пространство состояний цепи Маркова, описывающей работу системы Spj есть ZN, это - множество длин очередей на приборах ( Ъ -множество неотрицательных целых чисел).

Пусть тк, к ~ 0,1,., - число приборов, длина очереди в которых равна к (сообщение, которое обслуживается прибором также учитывается). Положим оо fk = mk/N, uk = Yl Ii, i=k т.е. здесь ик — uk(t) - доля приборов в момент t, длина очереди в которых не меньше, чем к. Очевидно, что

1 = Uo(t) > iii(i) > . > 0. (0.1)

Трактуя u = {wiJ^Q как функцию от первоначальной цепи Маркова, мы получаем новую цепь Маркова с пространством состояний Un- Мы назовем эту новую цепь Маркова фактор-цепью.

Пусть ~EjNuk - среднее значение случайной величины ик относительно стационарного распределения в системе SПусть выбор делается из г приборов. Верна следующая асимптотическая формула: если Л < 1, то при t —> оо lim Едгщ = А --1 = ак.

В случае основной модели фактор-цепь задается производящим оператором оо

АкЯи) = ЛК - иш)(/(и - - /(и)) оо

К-1)г - Мг)(/(и + - /(и)). к=1

Наглядное объяснение этой формулы состоит в следующем: слагаемые первой суммы соответствуют уменьшению длин очередей при окончании обслуживания сообщения; слагаемые второй суммы соответствуют увеличению длин очередей при поступлении нового сообшения (вероятность того, что г выбранных приборов имеют очереди не короче, чем к — 1, равна (гхАх)г). Разность (ик^)г — (и¡¡У ~ это вероятность того, что хотя бы на одном из выбранных приборов очередь равна к — 1, что приведет к возрастанию величины ик.

Соображения типа "закона больших чисел" подсказывают, что в пределе, при N —оо, эволюция значений ик становится детерминированной, и фактор-цепь асимптотически сходится к динамической системе, эволюция которой описывается бесконечной системой дифференциально-разностных уравнений = иш{Ь)-ик{1) + Х({ик^)У-{ик^)У)у к = 1,2,.; «„(*) = 1- (0-2)

Стационарное решение уравнений (0.2) имеет вид Л >■-* = ак.

Примеры нескольких задач, обобщающих задачу А) ( [30]).

Б). Случайно выбирается г приборов, и сообщение направляется в я-ую из очередей (очереди нумеруются в порядке возрастания). При 5 = 1 задача совпадает с предыдущей.

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

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

Д). Выбор идет так же, как в случае Г), с той разницей, что после т попыток сообшение направляется на последний из выбранных приборов.

Во всех этих задачах в случае нескольких очередей равной длины выбор между ними производится случайно. Эффекта от неравновероятного выбора, обнаруженного недавно Митценмахером и Фекингом, [69], мы не рассматриваем.

В этих задачах мы не можем выписать явные формулы для стационарной вероятности длины очереди при N —> оо. Но мы показываем, что в случаях Б)-Г) в пределе эти вероятности убывают сверхэкпоненциально с ростом длины,а в случае Д) убывание экспоненциально.

Так например, в случае Б), если система не перегружена , то вероятности очередей длины к с ростом к при г > s убывает как с0(А)С1(г~^\

В случае Д) при п = 0, т = 2, когда с первой попытки сообщение направляется только на свободный прибор, и делается не более двух попыток, lim Е^. - (А)2*-1. n-> оо т.е. А как бы заменяется на А2.

Модели А)- В) описываются марковской цепью, фактор-цепь которой задается производящим оператором

00

AnHu) = NЕ К - «*+i)(/(u - - Ди))+ к=1 оо

Aiv£ - h(uk))(f(u + - /(u)). k=1

Функция h(x) равна, соответственно, xT в модели А) h(x) = { £ (р (1 - x)lxr~l в модели Б) (0.3)

I Е^хЕ^Чра-®)1^-' в модели В)

Во всех случаях в пределе, при N -У оо, эволюция значений ик становится детерминированной, и фактор-цепь асимптотически сходится к динамической системе, эволюция которой описывается системой дифференциально-разностных уравнений = uk+l(t) - uk(t) + A(h(uk^(t)) - h(uk(t))), к — 1,2,., (0.4) с начально-краевыми условиями 9к, Щ(t) = д0 = 1, lim ик = lim дк = 0. (0.5) к—> оо к—>оо

В дальнейшем предполагается, что выполнены условия в0 = зир{к(х)/х : 0 < х < 1} < оо,

6>1 = 8ир{/г'(ж) : 0 < х < 1} < оо, в2 = 8ир{к"(х) : 0 < х < 1} < оо, к(х) < о(ж), х ->• О, и что Л удовлетворяет условию р = в0А < 1. (0.6)

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

Обозначим через Ы пространство всех последовательностей и = удовлетворяющих соотношениям (0.1) с метрикой и,и/) = зир|ц"7^1, и е ¿7, V! ей. (0.7) к> о к

В метрике (0.7) пространство ТА компактно, а сходимость эквивалентна покоординатной сходимости. Обозначим

Ы СИ, Ы = {и еЫ : £ Щ < г=1

Метрика в Ы индуцируется метрикой (0.7). Пусть

ЫМСЫ, 11ц = {и е Ы : щ = гк/И}, где г к-целые числа, 0 < гк < n. Обозначим «*(и) = £ щ, х{и) = К(и)}~0, (0.8) где и £ Ы. Отметим, что если и £ Ы^, то МУ1(и) равно суммарному числу сообшений, стоящих в очередях в системе

Сформулируем некоторые из доказанных теорем.

Теорема 1.1 Пусть g еЫ. Тогда а) в U существует единственное решение u{t,g) задачи (0.4) — (0.5). Если g G U, то u(i, g) £ U при всех t < оо; б) если р = 6qX < 1, то в Ы существует единственное стационарное по t решение а = задачи (0.4), если h(x) < о(х9) , q > 1, х -» 0, то ак, к —> оо, сходятся к 0 сверхэкспоненциалъно; в) если g G U, и р < 1 то решение u(i, g) сходится при t —> оо к стационарному решению, т.е. щ —а^, k = 1, 2,.

Отображение g —> u(t, g), где u(i, g) - решение задачи (0.4)-(0.5), задает в пространстве Ы динамическую систему, которой отвечает полугруппа Т = T(t), действующая в пространстве L = C{U) непрерывных функций / : U —> М. Пусть

T(f)/(g)=/(u(i,g))> gей.

Система обслуживания Sn определяет марковский процесс Un = U^(t) с пространством состояний UN, заданный оператором Адг. Процессу Ujm соответствует полугруппа Tn — TN(t) в пространстве функций на UN. Именно, если / : UN —> К, то

TN(t)f(u) = E(/(£^(i)) | UN(0) = g), g G UN.

Теорема 1.2. Пусть f - произвольная непрерывная функцгля f : U —>■ к. Тогда при всяком t> 0 справедливо соотношение lim sup №(i)/(g)-/(u(i,g))|=0.

Ng euN

Сходимость равномерна no t на любом конечном интервале изменения t.

Теорема 1.3. Пусть g &U, и последовательности gN = {{g^^JLo £ ^v, N = 1,2,., таковы, что gN —у g при N оо, и ряды Vi(gN) = Y^^L^g^k сходятся равномерно по N. Тогда при любом t > 0 lim TN(t)Vl(g*) = f/i(u(i,g))- (0.9)

Л/-юо

Сходимость равномерна по t на любом конечном интервале изменения t. Теорема 1.5. Пусть р < 1. Тогда а) процесс II¿у эргодичен, т.е. существует единственная стационарная вероятностная мера, к которой при Ь —> оо сходятся распределения в момент £ для любого начального распределения. Пусть Еуу - математическое ожидание по стационарной мере процесса [/Тогда < оо, ./V = 1, 2,. б) на множестве Ы существует единственная вероятностная мера, инвариантная относительно динамической системы g —> € Ы. Эта мера сосредоточена в неподвижной точке а динамической системы. в) справедливы соотношения

Пт Едгик = ак, к = 0,1,.

Л^—>оо

Схема доказательств

1). Сначала рассматривается предельный процесс - т.е. предельная динамическая система (0.4). Точнее: для задач А)-В) рассматривается решение начально-краевой задачи вида (0.4)-(0.5). Предполагается, что }г(х), 0 < х < 1, - гладкая, возрастающая по х функция, /г(0) = 0. Изучаются свойства этого решения.

В частности, показывается, что решения задачи (0.4)-(0.5) монотонны по к и по начальным условиям, а если g е Ы, то и —>■ а при I —>• оо, где а = стационарное решение системы (0.4).

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

2). Далее доказывается, что переходные вероятности фактор-цепи сходятся при N ^ оо к переходным вероятностям предельного процесса равномерно на любом конечном временном интервале.

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

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

Здесь используется равномерная по N компактность стационарных распределений допредельных цепей.

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

Асимптотические результаты сравниваются с результатами моделирования для конечных систем 5дг. Например, в Таблицах 1-2 для случая А) приводятся результаты моделирования когда из двух приборов (г = 2) выбирается прибор с наименьшей очередью.

В главе 2 рассматриваются задачи аналогичные задачам А)-В) главы 1, т.е. рассматривается система из n приборов, на которую поступает пуассо-новский поток сообщений интенсивности ТУА, но теперь предполагается, что длины сообщений имеют не пуассоновское распределение, [30]. А именно, каждое сообщение состоит из I, I — 1,2,., мини-пакетов (число мини-пакетов в различных сообщениях, вообще говоря, разное). Время обслуживания каждого мини-пакета распределено экспоненциально, его среднее равно 1 ¡Ь. Все мини-пакеты одного сообщения посылаются на один и тот же прибор и обслуживаются друг за другом. Вероятность того, что сообщение состоит из I мини-пакетов равна Ьг, = 1- При поступлении сообщения в систему случайно выбирается несколько приборов и то, куда направляется сообщение, определяется числом мини-пакетов на приборах (а не числом сообщений). Правила выбора те же, что выше.

Такую систему обслуживания мы обозначим через

Средняя нагрузка на прибор равна при этом р = ае ьi. I

Предполагается, что выполнено следующее условие неперегруженности системы: вор = б0Х £ Щ < 1, (0.10) I здесь в0 то же, что выше). Число значений I может быть и неограниченным, но при этом предполагается, что второй момент распределения длин сообщений (числа мини-пакетов) ограничен: I\ < оо (0.11). I

Мы снова интересуемся предельным случаем, когда n —у оо.

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

00

АмПи) =ла£ (ик - и*+г)(/(и - е4) - /(и))+

I ,

Aiv£ £ МЛН-О - %))(/(u+6t + - + eH'"') - /(u)). fc=i г

Функции h(x) здесь те же, что в (0.3). При N —» оо, эволюция значений становится детерминированной, и фактор-цепь асимптотически сходится к динамической системе, эволюция которой описывается системой дифференциально-разностных уравнений L(uk+1(t) - uk(t)) + Л£ bi{h(uk-i{t)) - h(uk(t))), (0.12)

1,2,. с начально-краевыми условиями щ(0) = дк, к > 1, uk(t) - д0 = 1, к < 0, lim ик - lim дк = 0. (0.13)

->оо к-^оо

Для системы sffl доказываются теоремы, аналогичные теоремам Главы 1, но тут для доказательств эргодичности марковской цепи при конечном N и существования глобально устойчивого стационарного решения предельной задачи (0.12),(0.13) используется условие (0.12) конечности второго момента функции распределения времени обслуживания сообщения. Кроме того, даже в случае задачи А) стационарное решение (0.12)-(0.13) не выписывается явно, а только показывается его суперэкспоненциальное убывание.

Рассматривается предельный случай, когда L оо, N —> оо. В пределе от сравнения числа мини-пакетов в очереди мы переходим к сравнению времен, которые нужны для обслуживания стоящих в очереди сообщений.

Вводится пространство V невозрастающих функций д(х), д(х) = 1, х < О, д(х) > 0, х > 0. Метрика в пространстве V определяется как

Cl\9V{z)-gW{z)\dz sup —-. г>0 Х+1

При конечном L среднее время обслуживания сообщения, состоящего из I мини-пакетов равно 1/L (время обслуживания сообщения случайно), а при L->oonl/L = s = const время обслуживания сообщения стремится к фиксированному значению s. Предполагается, что

12/Ь lim b(l)/L= dB(s)ds, Vh,l2,

-*00 h JhH и распределение начального состояния сходится к ¿-образному распределению, сосредоточенному на {<?(я), х > 0}, где д(х) - невозрастающая функция, д(х) = 1, х < 0, д(х) -)■ 0, х —У оо.

Показывается, что при ./V, Ь —>• оо имеет место сходимость к динамической системе, заданной функциональным уравнением.

В главе 3 рассматривается модель системы типа системы но с непуас-соновским входным потоком, который генерируется прерывающимися время от времени источниками. Система состоит из N приборов, на которые поступают сообщения от N источников, причем каждый прибор связан с одним определенным источником, [44].

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

Каждый из источников может находится в активном состоянии 'on' или в пассивном состоянии 'off. В активном состоянии источник генерирует пуас-соновский поток сообщений, в пассивном состоянии источник не генерирует сообщений. Интенсивность пуассоновского потока в активном состоянии у всех источников одинакова и равна А, времена обслуживания сообщений независимы и распределены экспоненциально со средним единица.

Переход из состояния в состояние у каждого источника марковский, источник переходит из состояния 'on' в состояние 'off' с интенсивностью т~, и переходит из состояния 'off' в состояние 'on' с интенсивностью т+.

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

Рис. 0.2

Мы снова имеем дело с системой, которая описывается цепью Маркова со счетным числом состояний.

Обозначим u=(u+,ir), и = {«£}£„, uk = u¿ + u;, где и~1 - доля приборов в состоянии 'on', длина очереди в которых не меньше, чем к, a - доля приборов в состоянии 'off, длина очереди в которых не меньше, чем к. Не приводя здесь производящего оператора для цепи Маркова, выпишем предельные (N = оо) уравнения, которые действуют в пространствах пар последовательностей

U = {u+,u~, uf>uf+1,i= 0,1,.,}, U = {и eU, иг < оо}. i

Уравнения имеют вид: juf(t) = Л(uUit) - ti+(í))[«£i(f) + uf(t) + u^(t) + щЦ)}/2

-uf(t) +T+u~(t) -r~uf(t), i > 1, (0.14) ju.(t) = X(u^(t) - uimuUit) +uf(t))/2 + Ur+1{t) - u~(t) - r+u~ + т-uf, Начально-краевые условия: d d

-ui(t) = T+uñ(t) - r-u0+(í), Jtuñ{t) = -T+Uo{t) + T~u+(t), (0.15) W(O)=0?, 9t>gf+ V * > o, <70+ + <?о~ = 1-Условие неперегруженности системы: p = X—<1. r+ + T

Для этой системы доказываются утверждения, аналогичные утверждениям предыдущих глав. Показывается, что при условии неперегруженности конечной системы описывающая ее марковская цепь эргодична, а для решения задачи (0.14)-(0.15) Hindoo uf = af, где af - решение соответствующей стационарной задачи, которое убывает по г сверхэкспоненциально.

Моделирование показывает, что даже при небольших N значения a¿ = af + а~ быстро убывают по г.

Далее мы переходим к системе, в которой имеется 3 групп источников, в у ой группе Щ приборов, и т* = е^т*, £$ > так что итервалы между переходами из состояния 'оп' в состояние 'о//' (и назад) удлиняются с ростом j. Здесь снова приводятся достаточные условия для эргодичности конечной системы, в которой сообщение выбирает между прибором, на которое оно было первоначально направлено и другим - случайно выбранным. При n —оо, 3 —»• оо, предельная система описывается детерминированной динамической системой, и вероятности длинных очередей в этой системе убывают сверхэкспоненциально. Однако, как показывает пример из работы [44] в системе, где не делается выбора второго прибора вероятности длинных очередей могут убывать не экспоненциально, а всего лишь показательно (за счет того, что на приборах с очень длинными интервалами в состоянии 'оп' при интенсивности входного потока > 1 могут накапливаться длинные очереди).

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

В главе 4 от системы главы 1с n приборами, мы переходим к 3 станциям, на каждой из которых имеется n приборов, [81, 32]. На систему поступает несколько пуассоновских потоков Нт интенсивности МХт. Каждому потоку ет соответствует непустое подмножество станций кт С {1,2,.,3} (см. Рис. 0.2), здесь = {1,2} , К% — {2,3,4} , )С3 = {4}). Заявка из потока Ега выбирает на каждой станции г, г £ /Ст. гш(г) приборов и направляется в кратчайшую из очередей. Время обслуживания сообщений распределено экспоненциально. Подчеркнем, что приборы, из которых приходится выбирать, могут принадлежать разным станциям. Приводятся необходимые и достаточные условия неперегруженности системы (как при конечном, так и при бесконечном значении Щ (эти условия аналогичны условиям из работы ![87], где, напомним, на каждой станции имеется один прибор.

Рис. 0.3

Чтобы выписать условия неперегруженности введем определение. Назовем входной поток Ет направленным на К,т потоком. Система неперегружена, если для любого набора станций К сумма всех потоков, направленных на все подмножества Кт С К (включая само К) не превосходит число станций в /С, Ат<#/С V/С с {1,.,,/}. (0.16)

771, К>т С/С

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

Например, в системе на Рис. 3 условие неперегруженности имеет вид Ах < 2, Л2 <3, А3 < 1, Ах + А2 + А3 < 4.

Показывается, что при выполнении условия (0.16) конечная система (/У < оо) эргодична, а при N —>■ оо предельная динамическая система имеет единственное и сверхэкспоненциально убывающее стационарное решение.

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

Описанная выше ситуация обобщается на более общую систему: на сеть типа быстрой сети Джексона. Быстрая сеть Джексона впервые рассматривалась в работе [65]; это система, в которой поступающее (по обычным правилам сети Джексона) на станцию ] = 1,., «/, сообщение выбирает на этой станции > 1, приборов и направляется в тот из них, где очередь короче. Условия неперегруженности быстрой сети Джексона совпадают с условиями для "обычной" сети Джексона, но в быстрой сети при N —> оо вероятности длинных очередей убывают сверхэкспоненциально.

В настоящей работе понятие быстрой сети обобщается. А именно, рассмо-тривается открытая сеть, в которой в каждом узле - станции - имеется N приборов (Рис. 0.4, 0.5). На сеть снова поступают пуассоновские потоки Ет интенсивностей МХт. Каждому потоку Ет соответствует непустое подмножество станций Кт С {1,2,.,/}. Заявка из потока Ет выбирает на каждой станции г, г 6 1Ст, гт(г) приборов и направляется в кратчайшую из очередей.

По окончанию обслуживания на станции г сообшение покидает сеть с вероятностью 1 — р*, а с вероятростью р* остается в сети и с вероятностью Рг> т направляется в поток Ет, где снова выбирает приборы, и т.д.

Рис. 0.4

• Нетрудно видеть, что такая сеть описывается цепью Маркова со счетным числом состояний.

Нам не удалось получить необходимых и достаточных условий эргодичности этой цепи Маркова,но мы можем дать достаточные (при всех N, 1 < N < оо) условия эргодичности, которые имеют вид (ср. с (0.16) ): з (Ат + Е Р)РЗ, т) V К С {1,., 3}. (0.17) т, КтСК ^'=1

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

В пределе N = 00 эволюция системы описывается динамической системой, заданной на последовательностях и = (щ^, .,) 1 < ^ < ■/, 1 = Щ,з > Щ,з > ••• > 0, иПд 6 К1. В общем случае мы не приводим здесь ни производящего оператора сети, ни уравнений для предельной динамической системы ввиду их громоздкости. Приведем, однако, уравнения для предельной динамической системы в случая двух станций (см. Рис. 0.5), при г^1) = 2, 7*2(2) = 2, гь (1) = 1 г2(2) = 1, т.е. когда всегда выбор делается из двух приборов. Эти уравнения имеют вид: ик+и(г) - щ^) + + Е - «£,-(*))

1,2 (А12 + Е Р> м(Фмг) ~ «*«,'(*)) + «*,/(*)) (0.18) г=1,2

U0j(t) = 1, mjfcj(o) = 9k,j, 1 > gk,j > 9k+i,j > 0, j = 1,2, 1фз, k = 1,2,.

0.19) ai. Al2 a2.

Рис. 0.5

Для системы дифференциальных уравнений (0.18) с начально-граничными условиями (0.19) мы даем необходимые и достаточные условия того, что при t —> оо решения (0.18)-(0.19) сходятся к единственному стационарному решению а = {dkjYj^i fc=o°> и убывают сверхэкспоненциально по к. Подчеркнем, что для соответствуещего Марковского процесса даются только достаточные условия эргодичности (0.17).

В главе 5 рассматривается модель системы, для которой справедлива пуас-соновская гипотеза. Нас снова интересует система с большим числом маршрутов между входом в сеть и выходом из нее, [80, 16, 31].

Начнем с системы с простейшей топологией (см. Рис. 0.5), где на систему с N приборами поступает пуассоновский поток сообщений интенсивности NX. Поступившее сообщение разбивается на п пакетов, каждый из которых независимо от остальных посылается на случайно выбранный прибор (дейтаграмная передачей сообщений). Время обслуживания пакета распределено экспоненциально со средним значением единица. Показывается, что если р — An < 1, то при N —оо длины очередей на приборах становятся независимыми и распределение длин стремится к распределению длин очередей в системе М\М\1 с входным потоком интенсивности р. Дисциплина обслуживания: первым пришел - первым передался (FCFS, first come-first served).

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

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

Эта модели интересна тем, что дает возможность исследовать не только время задержки (в очередях) отдельных пакетов, но и время задержки многопакетного сообщения, что является важной характеристикой сети связи.

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

Здесь сравниваются средняя задержки последнего из прошедших через систему к пакетов ^-пакетного сообщения и средняя задержка к-го по времени из прошедших через систему пакетов гг-пакетного сообщения, п > к. Оказывается, что хотя во втором случае суммарная интенсивность потока пакетов р в п/к раз больше, чем интенсивность в первом случае, при достаточно малом р средняя задержка к-то по времени пакета во втором случае меньше. Отсюда следует, что если /с-пакетное сообщение закодировано п-пакетным сообщением так, что оно восстанавливается по любым к пакетам, то пересылка закодированных сообщений может уменьшить задержку (дешифрованного) сообщения. Заметим, что если кодируется только некоторая доля сообщений (скажем, приоритетные сообщения), то ускорение их доставки тем более заметно, чем меньшую долю от всех сообщений они составляют.

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

Моделируется работа более сложной системы, состоящей из нескольких последовательных станций, каждая из которых имеет N приборов (см. Рис. 0.7). Хотя число маршрутов достаточно велико (много больше, чем число пакетов в сообщении), а каждый из пакетов выбирает свой маршрут случайно и независимо от остальных пакетов своего сообщения, задержки пакетов не неза1 Л

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

Результаты моделирования показывают как с ростом объема и разветвлен-ности сети характеристики задержек сходятся к характеристикам задержек в предельной ^ = оо) сети с независимыми пакетами.

Отметим, что для других моделей сетей связи экспериментальные результаты в случае, когда время обслуживания пакета распределено экспоненциально были получены в работах [75, 76, 77].

Далее в главе 6 рассматриваетя задача о большой сети передачи данных, для которой справедлива пуассоновская гипотеза —с^еК8У1Д8У4,811. Здесь оптимизируется маршрут передачи сообщения. Система является полносвязным графом с N вершинами - узлами, связи между парами узлов двусторонние. На каждую пару узлов (г,^) поступает пуассоновский поток интенсивности А, состоящий из ¿-пакетных сообщений.

Передающие приборы (с неограниченными буферами) расположены на ребрах. При поступлении во входной узел г сообщение из (г, ^-потока мгновенно разбивается на пакеты и каждый пакет независимо от остальных пакетов с вероятностью р передается на узел ] по ребру (г, у) , а с дополнительной вероятностью передается сначала на узел ]*, ]* ф у, по ребру (г, а затем на узел 3 по ребру {з*,з). Промежуточрый узел з* выбирается случайно, вероятность каждого промежуточного узла равна 1/(Аг - 2). Дисциплина обслуживания пакетов ГСГБ, время обслуживания пакета равно единице. А

Рис. 0.7

Рис. 0.8

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

Задача исследовалась нами численно: для небольших значений N проводилось моделирование, для асимптотического случая N = сю численно решалось уравнение Колмогорова, определяющее длину очереди на приборе. Оказывается, существует зависящее от N а числа пакетов в сообщениях пороговое значение Асг такое, что при Л < Хст сообщение в среднем быстрее достигает узел назначения, когда пакеты посылаются по различным двухреберным путям, а при А > Асг, наоборот, сообщение доставляется быстрее, когда всё пакеты передаются по однореберному пути.

В главе 6 рассматривается система доступа многих пользователей в сеть т.е. система множественного доступа. Мы исследуем стек алгоритм множественного доступа (точнее - две из его модификаций). Стек алгоритм имеет ряд преимуществ перед другими алгоритмами доступа в сеть. Например, задержка сообщения не зависит от того, что происходило в сети до появления этого сообщения (свойство, характерное для дисциплины обслуживания ЬСЕЭ). Если интенсивность входного потока невелика, то средняя задержка сообщения конечна. При этом не предполагается, что число пользователей конечно. Стек-алгоритму множественного доступа посвящено много работ (см., например, [83, ?, 89, 41]) и сейчас он вызывает большой интерес у практиков. Стек-алгоритм со свободным доступом был исследован впервые в работе [91].

О—

Рис. 0.9

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

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

Упомянем, что если входной поток пуассоновской, то для рассматриваемых нами моделей стек алгоритма средняя задержка пакета конечна, если интенсивность входного потока не превосходит Асг ~ 0.33 — 0.36 (за единицу времени принята длина окна). Стек алгоритм реализует дисциплину обслуживания "последним пришел - первым передался" (ЬСЕБ) с рандомизацией .

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

Когда часть пакетов имеет приоритетный характер, то простейшее кодирование - дублирование приоритетных пакетов может ускорить доставку этих пакетов. Здесь предполагается, что имеется несколько параллельных каналов, по которым передаются пакеты (это предположение согласуется с реальными возможностями передачи). Например, не приоритетные пакеты передаются по одному из каналов, а приоритетные передаются по двум каналам. Система исследуется с помощью моделирования, которое показывает, что как величина средней задержки приоритетного сообщения, так и вероятность его большой задержки меньше, чем соответствующие значения величин для не приоритетных сообщений. (Вероятности больших задержек интересуют нас потому, что в системах с дисциплиной обслуживания LIFO они значительно больше, чем в системах с дисциплиной FIFO, [33]). Таким образом, для ускорения доступа в канал можно использовать метод, который обсуждался в Главе 5.

Если в системе имеется два параллельных канала, то, как показывает численное моделирование, можно ускорить доступ пакетов в канал, посылая каждый пакет в менее загруженный канал (т.е. используя тот же метод, который обсуждался в Главе 1).

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

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

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

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

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

1. N. Abramson, The ALOHA system - another alternative for computer communication, Proc. 1970 Fall Joint Computer Conf./ AF1.S Press, v. 37, 281-285 (1970).

2. I.J.Adan, J. Wessels, W.H.M. Zijm, Analysis of the asymmetric shortest queue problem, Queueing Systems, v. 8, 1-58, (1998).

3. Y. Azar, A. Broder, A. Karlin, E. Upfal, Balanced Allocation, Proc. 26th ACM Symposium on the Theory of Computating (1994).

4. F. Baccelli, F.I. Karpelevich, M.Ya. Kelbert, A.A. Puhalskii, A.N. Rybko, Yu.M. Suhov, A mean-field limit for a class of queueing networks, Journal of Statistical Phisics, v.66, 803-825 (1992).

5. S.A. Berezner, D.M. Rose, Y.M. Suhov, Starlike networks with sinchronization constrains, in Stochastic Networks, Springer-Verlag, NY (1995).

6. K.A. Боровков, Распространение хаоса в сетях обслуживания, Теория Вер. и Прилож., т. 42, N 3, 449-460 (1997).

7. Н.Д.Введенская,Решение задачи Коши для нелинейного уравнения с разрывными начальными данными методом конечных разностей, ДАН, т.111, 517-520 (1956).

8. Н.Д.Введенская, B.C. Цыбаков, Случайный множественный доступ пакетов в канал с ошибками, Проблемы передачи информации, т. 19, N 2, 52-68 (1983).

9. Н.Д.Введенская, B.C. Цыбаков, Случайный множественный доступ нетерпеливых пакетов в широковещательный канал, Проблемы передачи информации, т.19, N 4, 72-83, (1983).

10. Н.Д.Введенская, B.C. Цыбаков, Задержка пакета при стек-алгоритме множественного доступа, Проблемы передачи информации, т.20, N 2,7797, 77-97 (1984).

11. Н.Д.Введенская, Поведение решений некоторых уравнений, возникающих в задачах случайного множественного доступа, Тез. VI Межд.симп. по теории информации, Ташкент, 4.II, 39-40 (1984).

12. Н.Д.Введенская, B.C. Цыбаков, Вычисление задержки пакета для различных стек-алгоритмов случайного множественного доступа, Проблемы передачи информации, т.24, N 3, 94-101 (1988).

13. Н.Д.Введенская, Б.С. Цыбаков, Стек-алгоритм в широковещательном канале с захватами, Проблемы передачи информации, Т. 27, N 2, 25-31 (1991).

14. Н.Д.Введенская, Б.С. Цыбаков, Различные модификации стек-алгоритма множественного доступа в канале с захватами, Тр. Всесоюзной конф. Системы множественного доступа, Минск, ч.1, 39-42 (1991).

15. N.D. Vvedenskaya, The Delay of a Message in a Packet-Switching Network, Тез. V совещания по распределенным вычислительным сетям (CDS-92), Москва, 193-195 (1991).

16. Н.Д. Введенская, Передача сообщений по разветвленной сети связи, Итоговый отчет по проекту "Разработка методов синтеза интегрированных коммуникационных систем", рук. чл.-корр РАН Н.А. Кузнецов, РАН, ИППИ, Москва, 243-262 (1992).

17. N.D. Vvedenskaya, The Delay of a message in Packet-Switched Network with Unreliable Elements, Proc. of Vl-th Joint Swedish-Russian Workshop on Information Theory, Molle, Sweden, 76-80 (1993).

18. N.D. Vvedenskaya, J.P.M.G. Linnartz, Efect of CDMA Transmission on Performance of wireless Networks with Stack Algorithm for Collision Resolution, Tr. of Fifth IEEE Internat. Symposium on PIMRC'94, Ed. J.H. Weber etc, v. IV, 1129-1132 (1994).

19. Н.Д. Введенская, Ф. Жаке, B.C. Цыбаков, Задержка пакета при использовании стек алгоритма в закритической области входных потоков, Проблемы передачи информации, Т. 30, No 4, 76-89 (1994).

20. N.D. Vvedenskaya, Distribution of Message Delay in a Network with multiple Routs, Proc. of 16-th Symposium on Information Theary in Benelux, Netherlands, 49-51 (1995).

21. N.D. Vvedenskaya, J.P.M.G. Linnartz, Performance of Stack Algorithm in Case of mutually Interfering Transmission in two Cells, Proc. of 16-th Symposium on Information Theary in Benelux, Netherlands, 159-164 (1995).

22. N.D. Vvedenskaya, Message Delay in a Network with many multiple Routs and Feedback, Proc. of VII-th Joint Russian-Swedish Workshop on Information Theory, S.Peterburg, 243-245 (1995).

23. Н.Д. Введенская, P.JI. Добрушин, Ф.И. Карпелевич, Система обслуживания с выбором наименьшей из двух очередей асимптотический подход, Проблемы передачи информации, Т. 32, N 1, 20-34 (1996).

24. N.D. Vvedenskaya, An Example of Optimal Message Routing in a Complete-Graph Network Model, Proc. of 17-th Symposium on Information Theary in Benelux, Netherlands, 65-71 (1996).

25. N.D. Vvedenskaya, Large Queueing Systems where the Selection of the shortest of several Queues is Allowed, Proc. of Workshop on Statistical Mechanics of Large Networks', INRIA Recquencourt, 19-21 (1996).

26. N.D. Vvedenskaya, J.H. Weber, Transmission of Messages using few Parallel Servers, Proc. of Internat. Conference on Distributed Computer Communication Networks, Tel Aviv, 241-245 (1996).

27. N.D. Vvedenskaya, Transmission of Messages using parallel Servers: Asymptotic Approach, Proc. 1997 IEEE Int. Symp. on Inf. Theory, Ulm, 32 (1997).

28. N.D. Vvedenskaya, Y.M. Suhov, Dobrushin's Mean-Field Approximation for a Queue with Dynamic Routing, Marlov Processes and Related Fields, v.3, N 4, 493-526 (1997).

29. Н.Д. Введенская, Большая система обслуживания с передачей сообщения по нескольким путям, Проблемы передачи информации, т. 34, No 2, 98-108 (1998).

30. N.D. Vvedenskaya , Differential equations arising in queueing theory, Proc. of Intern. Conference on Differential and Functional Equations, Moscow State Aviation Inst., Moscow, 119-120 (1999).

31. Н.Д. Введенская, Е.А.Печерский, Ю.М.Сухов, Большие уклонения в некоторых системах с очередями, Проблемы передачи информации, Т.36, N 1, 48-58 (2000).

32. С. Graham, S. Meleard, Dynamic asymptotic results for a generalized star-shaped network, Annals of Applied Probability, v. 5 (1995).

33. R.L. Dobrushin, Switching networks, Gibbson fields interconnections, Proc. 1st World Congress of the Bernoulli Society, Tashkent, 1986, VNS sci. press, Utrecht, v. 1 (1987).

34. P.JI. Добрушин, Ю.М. Сухов, Асимптотическое исследование звездообразных сетей коммутации сообщений с большим числом радиальных лучей, Проблемы передачи информации, т.12, N 1, 70-94 (1976).

35. R.L. Dobrushin, Asymptotical investigation of large queueing computer networks, Int. coll. on inform, theory, Budapest, Hungary (1981).

36. R.L. Dobrushin, V.Ya. Kelbert, A.N. Rybko, Yu.M. Suhov, Stochastic cellular systems: ergodisity, memory, morphogenesis, 183-224, Manchester University Press, Manchester (1988).

37. Г. Дейвид, Порядковые статистики, M., Наука, 1978.

38. S. Ethier and Т. Kurtz, Markov Processes: Characterization and Convergence. New York, Wiley, (1986).

39. P. Jacquet, Random infinite trees and supercritical behavior of collision resolution algorithm, IEEE Tr. Inform. Theory, v. IT-39 (1993).

40. P. Jacquet, Analytic information theory in service of queueing with aggregated exponential on/off arrivals, Proc. 35th annual Allerton Conf. on Communication, Control and Computing (1997).

41. P. Jacquet, Long term dependences and heavy tails in traffics and queues generated by memoriless on/off sources in series, INRIA Research Report, RR 3516 (1998).

42. P. Jacquet, N.D. Vvedenskaya, ON/OFF Sources in an Interconnection Network: Performance Analysis when Packets are Routed to the Shortest Queue of two Randomly Selected Nodes, Rapport de Recherche No 3570, INRIA, 1-35, December 1998.

43. P. Jacquet, Yuri Suhov, N.D. Vvedenskaya , Dynamic routing in the mean-field approximation, Rapport de Recherche, INRIA, 1-21, December 1999.

44. Г.А. Кабатянский, E.A. Круг, Об избыточном кодировании на транспортном уровне сети передачи данных, Помехоустойчевое кодирование и надежность ЭВМ, М., "Наука", 143-150, 1987

45. Г.А. Каменский, А.Л. Скубачевский, Линейные краевые задачи для дифференциально-разностных уравнений, М., Из-во МАИ (1992).

46. F.I. Karpelevich, M.Ya. Kelbert, Yu.M. Suhov Higher-order Lindley equation, Stochastic Processes and there Applications, v. 53, (1994).

47. F.I. Karpelevich, E.A. Pechersky and Yu.M. Suhov, Dobrushin's approach to queueing network theory, J. Appl. Math. Stoch. Anal., v. 9 (1996).

48. Ф.И. Карпелевич, A.H. Рыбко,Асимптотическое поведение симметричной замкнутой сети массового обслуживания в термодинамическом пределе, Проблемы передачи информации, т.36, 69-95 (2000).

49. Г.П. Климов Стохастические системы обслуживания, "Наука", М. (1966).

50. F.P. Kelly, Blocking probabilities in large circuit-switched networks, Advances in Applied Probability, v. 18 (1986).

51. F.P. Kelly, Loss networks, Ann. Appl. Probability, v.l (1991)

52. F.P. Kelly, I.B. Ziedins, Limit theorems for loss networks with diverse routinf Advances in Applied Probability, v.21 (1989).

53. М.Я. Кельберт, Ю.М. Сухов Об одном классе звезднообразных сетей связи с пакетной коммутацией, Проблемы передачи информации, т.15, N 4, 5342 (1979).

54. М.Я.Кельберт, Ю.М. Сухов, Математические вопросы теории сетей с очередями, Теория вероятностей. Математическая статистика, Теоретическая кибернетика. Итоги науки и техники, т. 26, М., 3-36 (1988)

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

56. L.Kleinrock, Queueing Systems, v.2: Computer Applications, Wiley, New York, 1976.

57. М.Ю. Крадинов, Обоснование пуассоновской гипотезы для сетей с коммутацией каналов и потерями, Проблемы передачи информации, т.28, N 4, 86-95 (1992).

58. Kurkova, A load-balanced network with two servers, Preprint, EURANDOM, 5600 MB Eindhoven, 1999.

59. М.А.Лаврентьев, Л.А. Люстерник, Курс вариационного исчисления, МЛ1950).

60. Л.А. Люстерник, В.И. Соболев, Элементы функционального анализа, МЛ1951).

61. В.В. Марбух, Асимптотическое исследование полной сети связи с большим числом узлов и обходными маршрутами, Пробл. Передачи Информ., т.17, N 3, 89-95 (1981);

62. В.В. Марбух, Исследование полносвязной сети коммутации сообщений с большим числом узлов, обходными маршрутами и ограниченным числом мест для ожидания в узлах, Пробл. Передачи Информ., т.21, N 2, 90-98 (1985).

63. J.B. Martin, Yu.M. Suhov, Fast Jackson networks, Ann. Appl. Probab.,v.9 1999.

64. P. Mathis, B.S. Tsybakov, N.D. Vvedenskaya, User-oriented quantities in random-access. Packet delay and collision probability, II Joint Swedish-Soviet Internet. Workshop on Inform. Theory, Granna, Sweden, pp 166-171, 1985.

65. P. Mathys, N.D. Vvedenskaya, Random-Access System for mixed Voice and Data Packets, Proc. of Internat. Symposium on Information Theory, Trond-haim, Norway, p 293, 1994.

66. M. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, PhD Thesis, University of California, Berkeley, 1996.

67. M.Mitzenmacher, В. Voecking, The asymptotics of selectintg the shortest of two, improved Technical Report, Harvard University, (1999).

68. O.A. Олейник, Н.Д. Введенская, Решение задачи Коши и первой краевой задачи для нелинейных уравнений в классе разрывных функций, ДАН, т.113, (1957).

69. D.M. Rose, Y.M. Suhov,N.D. Vvedenskaya, Application of the Poisson-Independence Hypothesis to a Communication Network Routing Problem, Proc. of Workshop on Statistical Mechanics of Large Networks', INRIA Recquencourt, 34-35 (1996).

70. D.M. Rose, Y.M. Suhov,N.D. Vvedenskaya, The Poisson Independence Hypothesis: Early Developments and some Recent Results, Proc. of Internat. Conference on Distributed Computer Communication Networks, Tel Aviv, 67-76 (1996).

71. D.M. Rose, Y.M. Suhov,N.D. Vvedenskaya, Waiting Times in the M/Dm/1 Queue, Research Report 96-35, Statistical Laboratory, University of Cambridge, UK (1996).

72. D.M.Rose, Y.M. Suhov, N.D. Vvedenskaya, An Optimal Probabilistic Routing policy for a Large Packet-Switching Network, Stochasyic Models, v. 15, No 5, pp 1027-1050, 1998.

73. C.B. Семенов, E.A. Крук, К вопросу эфективности кодирования на транспортном уровне сети передачи данных, IX Симп. по пороблеме избыточности в информационных системах, Тез., JIrp (1986).

74. С.В. Семенов, А.В. Семенов, Моделирование сетей передачи данных с коммутацией пакетов в условиях сетевого кодирования, Проблемы передачи и обработки информации, СПБ, с.80-94 (1991).

75. С.В. Семенов, Использование кодирования в сети передачи данных для уменьшения задержки сообщения, Автореф., СПБ (1992).

76. А.Л. Столяр, Асимптотика стационарного распределения для одной замкнутой системы обслуживания, Пробл. Пер. Информ.,т.25, N 4, 80-92 (1989).

77. Yu.M. Suhov, D.Rose, ThePoisson -independence hypothesis for infinitely growing fully-connected packet-switching networks, Stochastic Networks, Theory and Applications, Oxford Sci. Pub. (1996).

78. Yu.M. Suhov, N.D. Vvedenskaya, Fast Jackson Networks with Dynamic Routing, Preprint, Dublin Inst, for Advanced Studies, 1-32, April 2000.

79. S.R.E. Turner, The Effect of Increasing Routing Choice on Resource Pooling, Probability in the Engineering and Informational Sciences, v.12, 109-124 (1998).

80. G. Fayolle, P. Flajolet, M. Hofri, On a functional equation in the analsis of a protocol for a multi-access broadcast channel, Advances in Appl. Probab., v. 18 (1986).

81. G. Fayolle, Iasnogorodski, V. Malyshev Random walks in the quater plane, boundary value problems and applications, Cambridge University Press (1999).

82. G. Fayolle, V. Malyshev, M. Menshikov, Topics in the Constructive Theory of Countable Markov Chains, Cambridge University Press (1995).

83. L. Flatto, H.P. McKean, Two Queues in Parallel, Commun. Pure and Appl. Math., v.30, 1977.

84. R.Foley, D. McDonald, Join the shortest queue: stability and exact asymptotics, Preprint, Georgian Inst, of Technology and Univ. of Ottawa (1999).

85. B.C. Цыбаков, В.А. Михайлов, Свободный синхронный доступ пакетов в широковещательный канал с обратной связью, Проблемы передачи информации, т.14, N 4, 32-19 (1978).

86. B.S.Tsybakov, Survay of USSR contribution to random algorithms for multi access channels, IEEE TV. Inform. Theory,v. IT-31, N 2, 143-146 (1985);