Математические проблемы управления потоковыми переключательными сетями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На нравах рукописи

Феоктистова Варвара Николаевна

Математические проблемы управления потоковыми переключательными сетями

01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

I

1 7 МАЙ 2072

1ллОАВ Санкт-Петербург

2012

Работа выполнена на кафедре теоретической кибернетики математи механического факультета Санкт-Петербургского государствен»

университета.

Научный руководитель:

доктор физико-математических наук, профессор Матвеев Алексей Серафимович

Официальные оппоненты:

Петров Никсйгай Николаевич, доктор физико-математических наук, проф© (Санкт-Петербургский государственный университет, профессор)

Андриевский Борис Ростиславич, доктор технических наук, доцент, (Институт проблем машиноведения Российской академии наук (ИПМаш РАН), ведущий научный сотрудник )

Ведущая организация:

Санкт-Петербургский национальный исследовательский университет информацио технологий, механики и оптики.

Защита состоится "30" мал*. 2012 года в_часов на заседании дисс

тационного совета Д 212.232.29 при Санкт-Петербургском государствен! университете по адресу: 199034, Санкт-Петербург, Университетская наб., 1 ауд. 133.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горь го Санкт-Петербургского государственного университета по адресу: 199С Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан " сцлргл.^ 2012 года.

Ученый секретарь диссертационного совета ^М1^/^ В.М. Нежинск

Общая характеристика работы

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

Диссертация посвящена исследованию математических проблем управления потоковыми переключательными сетями, то есть сетями, в которых несколько серверов обслуживает ряд потоков, регулярно переключаясь между ними, н для которых переключение является существенной частью управляющего воздействия. Как математический объект такие сети традиционно используют для моделирования определенных аспектов функционирования гибких производственных систем, коммуникационных, информационных, компьютерных и платежных сетей, транспортных систем, процессов химической кинетики и др. Диссертация сфокусирована на жидкостных (детерминированных) моделях рассматриваемых сетей. Они представляют одни из основных используемых в обсуждаемой области типов математических моделей; их изучению посвящены работы многих авторов, в том числе М. Bramsoii, S. Gershwin, J.G. Dai, P.R. Kumar, T.I. Seidman, H. Chen, R. Herman, S.P. Mcyn, B. Hajck, D.N. Nicol, L. Prcsti, J. Hespanha и др. Жидкостные модели дополняют н аппроксимируют стохастические модели теории систем массового обслуживания. Интерес к жидкостным моделям заметно активизировался в последние два десятилетия. Причины этого включают назревшую потребность в целостном исследовании больших сетей. Для них жидкостная модель в силу своей "локалы1ой"отпосптелыюй простоты предоставляет практическую возможность содержательного анализа эффектов, связанных с взаимодействием и координацией множества агентов в большой системе.

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

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

Системный подход к преодолению упомянутого разрыва был недавно предложен Е. Lefebcr и J.E. Rooda. В качестве цели он ставит развитие общего метода синтеза протокола управления, превращающего априори заданный периодический процесс в глобальный аттрактор замкнутой системы. При этом особый интерес представляет случай, когда этот процесс оптимален нли суб-оптнмален. Упомянутыми авторами был предложен специальный метод такого рода, связанный с построением функции Ляпунова. Однако его известные применения ограничены простейшими примерами сетей невысокой сложности. Типичное для рассматриваемых сетей "проклятие размерности "быстро трансформирует необходимое для реализации метода вычисление функции Ляпунова в трудно, а подчас и вовсе невыполнимую задачу но мерс увеличения числа элементов сети. Однако даже после вычисления этой функции построение протокола не гарантировано, не подкреплено общей методикой и рассматривается как индивидуальная для каждого приложения задача.

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

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

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

Основные положения и результаты, выносимые на защиту.

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались па всемирном конгрессе Международной Федерации Автоматического Управления «18th IFAC World Congress» (Milan, Italy, 2011), на международной конференции по физике н уиранленшо «5th International Scientific Conference on Physics and Control: PHYSCON 2011»(Leon, Spain, 2011), на международном симпозиуме по проблемам управления потоками информации в производственных системах «13th IFAC Symposium on Information Control Problems in Manufacturing» (Moscow, Russia, 2009), на международном симпозиуме по интеллектуальным производственным системам «lOtli IFAC Workshop on Intelligent Manufacturing Systems» (Lisbon, Portugal, 2010), на научном семинаре кафедры исследования операций СПбГУ под руководством зав.каф., д.ф.-м.н., профессора H.H. Петрова (в 2012 г.), на научном семинаре лаборатории «Управление сложными снстсмами»Института Проблем Машиноведения РАН иод руководством зав. лаб., д.т.н., профессора А.Л. Фрадкова (в 2011 г.), а также па научном семинаре кафедры теоретической кибернетики СПбГУ под руководством зав. каф., чл.корр. РАН, д.ф.-м.н.,

профсссора В.А. Якубовича (с 2008—2011 гг.).

Результаты диссертации были частично использованы в исследованиях но грантам РФФИ 11-08-01218-а, 12-01-00808 и ФЦП «Научные и научно-иедагогичеекпе кадры инновационной России»(проект 1.1-111-128-033).

Публикации. Основные результаты диссертации отражены в публикациях |1]-[7]. В совместных работах [1], [4]—[6] диссертанту принадлежат формулировки и доказательства теорем, а соавторам — постановка задачи, выбор методов решения и — применительно к работам [5] н [6] — частичное вычисление оптимального процесса. В работах [3] и [7] диссертанту принадлежит доказательство оптимальности протокола управления, а соавторами обоснована устойчивость управляемой этим протоколом производственной лнини.

Статьи [1-3] опубликованы в изданиях, входящих в перечень рецензируемых научных журналов и изданий; публикации [4,6] имеют признаки соответствия этому перечню.

Структура и объем работы. Диссертация состоит из введения, восьми глав и списка литературы, содержащего 101 наименование. Текст диссертации изложен на 165 страницах и содержит 20 рисунков.

Содержание работы

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

Первая глава посвящена математической постановке основной задачи и описанию предложенного метода ее решения. Рассматривается система, состоящая из s серверов и N буферов и получающая извне / потоков, интерпретируемых как потоки жидкости. Поток из г-го источника поступает на постоянной скорости А* в буфер bi, затем перемещается серверами нз буфера в буфер и в конечном счете выводится из системы. Пути потоков по буферам неизменны и представлены ориентированным графом с множеством вершин {1,..., N, ©1, ...,©/, ©out}- Здесь — источник г-ого потока, ©out — внешний сток, вершины п € [1 : N] соответствуют буферам, а ребра графа указывают пути перемещения содержимого буферов, именуемого работой. Источники ®j не имеют входящих ребер, сток — находящих ребер, каждый буфер имеет входящие ребра и одно исходящее ребро, в графе пет циклов.

Перемещение работы из буферов по ребрам графа осуществляют сервера. Сервер извлекает содержимое буфера п со скоростью 0 < un(t) < iin, где fjtn > 0 задано, a u„(t) — управляющая переменная. В зоне обслуживания 1„ С [1 : Аг] сервера а находится несколько буферов, причем 1„> 0/^=0 при а' ф а" и Ii U ... U Is = [1 : А7"]. В каждый момент сервер способен обслуживать не более одного буфера и вынужден переключаться между ними; переключение нз буфера п' в п" занимает фиксированное время > 0.

Управление системой состоит в выборе для каждого сервера скорости извлечения содержимого »„(£) из обслуживаемого буфера п, момента прекращения обслуживания и следующего буфера. Во многих случаях оптимальна максимальная доступная скорость ип. Тогда задача управления сводится к выбору моментов и порядка переключения, а алгоритм переключения оказывается ключевым инструментом обеспечения требуемого поведения системы.

Текущее состояние (ЛЛ, С/) системы включает непрерывную X = (х\,...,1\\г) и дискретную ф = ((/1,..., д.,) компоненты, где х„ -содержимое буфера п и (¡а б 1„ := и {©} — состояние сервера сг: оп обслуживает буфер сели (¡а ^ ©, и переключается, если = ©. Прогрессом назовем пару функций [Х(£), времени описывающую возможный

вариант развития событий в системе. Это означает, что для любого сервера а активные п € [1 : Лт] и переключательные 0 значения кусочно-постоянной функции да(1) е 1а чередуются, соблюдается требуемое время экспозиции переключательного значения, а для любого п € [1 : Лг] функция :г„(-) абсолютно непрерывна, хпЦ) > 0 и ¿„(<) = Е^п-ветвь графа 4/(0 ~ ««(0. где иф,(*) ее Л,; и 0 < щ(г) < (А- ф с1а{1) => = 0) для к 6 [1 : Щ.

Протоколом (алгоритмом) управления называется система правил, определяющих для каждого сервера скорость и„(1) извлечения содержимого из обслуживаемого буфера п, время прекращения обслуживания и следующий обслуживаемый буфер. Соответствующие решения принимаются следуя принципу обратной связи на основе данных о времени £ и состоянии системы до текущего момента Л'|[о,/], (3|[о,/] (где 0 — начальное время).

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

Рассматривается следующая задача:

¡Р) По заданному периодическому процессу л° требуется построить протокол управления, который превращает 7г" в глобальный аттрактор.

Другими словами, любой процесс в системе, управляемой этим протоколом, сходится к 7г". Это особенно ценно, если процесс 7Г° обладает какими-либо полезным свойством, например, оптимален или суб-оптпмален. Тогда протокол обеспечивает автоматическое выведение сетевой системы в оптимальный режим, его устойчивое поддержание и компенсацию отклонений от оптимума.

В диссертации предложен следующий подход к решению задачи ¡Р, во многом мотивированный стремлением к преодолению "проклятия размерности "н созвучный идеям метода сечений Пуанкаре. Вначале процесс тг°, рассматриваемый на периоде, делится на простые части —- фазы

с = Фо,ФъФ2,...,Фг-1; (1)

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

состоит в принудительном прохождении через периодически повторяемый цикл фаз (1) с примененном внутри каждой из них индивидуального правила управления. Оно определяет скорости работы серверов, время окончания фазы и моменты скачкообразной эволюции состояния С] вдоль требуемой цепочки значений. Выбор такого правила порождает динамический оператор Тфазы , который переводит непрерывное состояние системы X в начале фазы в аналогичное состояние в конце этой фазы. Оператором моиодромии назовем композицию операторов Т^1 в соответствии с циклом (1)

М = Г4*'-1 о о • • • о Г^1 о Тфо. (2)

Состояния X, рассматриваемые в моменты начала циклов, эволюционируют посредством итераций этого оператора. Основная задача, решаемая при выборе правил управления фазами, — обеспечить, чтобы все траектории, порождаемые этой рекурсией Х(к + 1) = Л/[Х(А;)], сходились к положению равновесия Лг°, отвечающему требуемому периодическому процессу тг°. Кроме того каждое правило должно порождать соответствующую часть тг°.

В типнчпом случае операторы Т^3' и М кусочно-аффинпы, то есть аффипны па элементах полиэдрального разбиеипя фазового пространства. Обычно число элементов разбиения невелико для операторов Т^1', но быстро нарастает при последовательном формировании композиции (2), в итоге достигая астрономических значений, особенно при большом числе серверов, буферов, и фаз. В итоге "явнос"описанне оператора М трудоёмко и часто практически невозможно, что наряду с узкой номенклатурой управляющих воздействий (в основном, переключения серверов) препятствует прнмснепшо известных критериев устойчивости и методов стабилизации дискретных динамических систем. Дело осложняется тем, что на этапе синтеза оператор моиодромии М еще не существует, а задача состоит в обнаружении и использовании зависимостей между М и правилами управления фазами.

Для преодоления указанной проблемы в диссертации найден и обоснован новый критерий глобальной асимптотической устойчивости положения равновесия стационарной нелинейной дискретной динамической системы Х(к + 1) = М[Х(к)}. Его принципиальная особенность — возможность ио-фазовой проверки: критерий указывает список свойств, наличие которых у оператора моиодромии гарантирует устойчивость и которые наследуются композицией операторов, обладающих этими свойствами. В результате построение правил управления фазами освобождается от проклятия размерности за счет локализации цели построения: обеспечить наличие упомянутых свойств у динамического оператора каждой отдельной фазы.

Вторая глава посвящена проблеме устойчивости положений равновесия стационарных нелинейных дискретных динамических систем

х(к + 1) =Т[ж(Л)]. к = 0,1,2,

(3)

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

В р. 2.1 изложены основные определения. В частности, указано, что неравенства между векторами х, у € понимаются покомпонентно, и введены следующие понятия.

Определение 2.1 Оператор Т : := {х е Ш1': х > 0} —Кг+ назовём:

а) кусочно-аффинным если Л'+ можно покрыть К+ = С\ U ... U Си конечным числом выпуклых многогранных множеств С; с К+ (называемых ячейками,), на каждом из которых Т является аффинньш,, т.е. Т(.г) = AiX + си Ух € С,-, где Ai — линейный оператор и £ Е'г;

б) доминантным (строго доминантным) кусочно аффинным, если дополнительно ai > 0 (соответственно n, > 0J для любой ячейки;

в) монотонным, если Т(:г) < 0~(г/) Ух < у.

Далее КАМН = "нусочпо-аффшшый монотонный непрерывный". В р. 2.2 представлен следующий основной результат главы.

Теорема 2.1 Предположим., что КАМН оператор Т[-] : К1^ —> КJ имеет неподвижную точку Т[з"„] = х, е и некоторая его итещция 7т строго доминантна. Тогда неподвижная точка единственна и притягивает x(k) х, любую траекторию системы (3) (где ж(0) е К+)-

Возможность по-фазовой проверки условий Теоремой 2.1 обоснована в р. 2.3.

Оставшаяся часть главы 2 посвящена общей теории, из которой вытекает Теорема 2.1 и которая может быть использована для нахождения других аналогичных критериев устойчивости. Так как эта теория нацелена на результаты в духе теоремы Ляпунова об устойчивости по первому приближению, в ней центральное значение приобретает исследование спектральных свойств нелинейной производной негладкого динамического оператора 7 из (3), которая для КАМН операторов 7 является (положительно) однородным КАМН оператором Т, т.е. Т[6>.г] = вТ[х] Ув е [0, +оо), х > 0.

Р. 2.4 посвящен изучению собственные чисел и векторов однородных кусочно-аффинных монотонных непрерывных (ОКАМН) операторов Т.

Определение 2.2 Если Т[е] = ре для р € R и е > 0, е ф 0, число р и вектор е назовем собственным числом и собственным вектором ОКАМН оператора Т, соответственно. Собственный вектор назовем неустойчивым, если существует такое £ > 0, что любой ОКАМН-оператор 7. из доминантной е-окрестности Шг := {Т* : 0"(х) < Ух > 0,х ф 0; \7„(х) - 7(:с)| <еУх> 0, = 1} оператора 7 не имеет собственных векторов в е-окрестности е; и устойчивым в противном случае. Если собственное число имеет хотя бы один устойчивый собственный вектор, оно называется устойчивым.

Теорема 2.2 ОКАМНоперагпор 7 имеет одно и только одно устойчивое собственное число р = Оно неотрицательно, доминирует р > о прочие собственные числа д и зависит от оператора монотонно и непрерывно: Цх) < Т*(х) Ух € 1<1 => р{О] < />[7.] и 7, € 5»е Л £ 0 => р[7\ -> рЩ.

В р. 2.5 вводится и изучается однородное ядро К АМН оператора 7, представляющее собой аппроксимацию 7 однородным оператором вблизи бесконечно удаленной точки. Направление, заданное вектором е, назовем рецессивным для выпуклого множества С С если I + (е 6 С > 0 для некоторого х € С; совокупность всех таких векторов обозначим через Ех[С].

Теорема 2.3 Пусть С\,..., Ск - ячейки К АМН-оператора Т. Тогда преобразование х > 0 н> Т°°(х) := AiX для х € Ех{С{) является корректно определенным ОКАМН-оператором и + = Ех[С\] и ... и Ех[Си\-

Это преобразование называется однородным ядром оператора 7. Следующая лемма демонстрирует его аппроксимирующие свойства.

Лемма 2.1 |х|-1Т(х) - |ж|"1Тэо(ж) -»• 0 при |х| -юо, х > 0.

Теорема 2.4 Если /э[Т°°] < 1 для КАМН-оператора Т, то он имеет такие две неподвижные точки х~ < х+, что любая траектория системы, (3) притягивается к 7-инвариант,ному множеству Е := {х 6 К+ : х~ < х < .г+}.

В р. 2.6 введены основные понятия, связанные с дифференцированием КАМН-операторов. Вектор е € К'' назовем допустимым для выпуклого множества С С Р/ в точке х е С, если х + ве 6 С для всех () > 0,0 и 0; совокупность всех таких е обозначим через ТХ(С). В диссертации показано, что для КАМН-оператора 0*: —» К'1 и х* € Л+, преобразование

ее ТХ.(Ю ^ Дш/"1 + Щ - Т[х,]}

является корректно определенным ОКАМН-онсратором. Его сужение := 7'х,\к+ назовем правым дифференциалом оператора Т в точке х„, а оператор : с 6 Л'^х.) := {е > 0 : е,- = 0 если = 0} ь-» —7'х\—е] — левым дифференциал,ом. Неподвижную точку х„ назовем устойчивой по первому приближению, если устойчивое собственное число как правого, так н левого дифференциала в точке х» меньше 1.

В р. 2.7 обоснована следующая теорема, которая в качестве источника Теоремы 2.1 демонстрирует се родство с теоремой Ляпунова об устойчивости по первому приближению и может служить базой для других критериев глобальной устойчивости систем с К АМН динамическим оператором.

Теорема 2.5 Если устойчивое собственное число однородного ядра К АМН-оператора 7 : К+ —> К+ меньше 1, то этот оператор имеет неподвижную точку. Если дополнительно известно, что любая неподвижная точка оператора Т устойчива по первому приближению, то неподвижная точка единственна и притягивает все траектории системы (3).

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

Третья глава изучает сеть, состоящую из нескольких непрерывно растущих очередей и одного сервера и являющуюся частным случаем сети из гл. 1. В каждый момент сервер способен обслуживать не более одной очереди; переключение между очередями занимает фиксированное время. Для такой сети известны простые необходимые условия оптимальности процесса: буфер обслуживается на максимальной доступной скорости, что при пустом буфере означает па скорости входящего потока (W.M. Lan, T.L. Olsen, J. van Eckclcn и др.). Имеется ряд работ, в которых найдено оптимальное или субон-тимальное решение (J.B. Kmskal, 1969; O.J. Boxma, H. Levy, J.A. Wcststrate, 1991; В. Gaujal, A. Hordijk, D. van der Laan, 2007 и др.) при специальных предположениях либо о системе, либо о допустимых алгоритмах управления.

В главе 3 решена задача синтеза протокола управления общей системой указанного тина. Протокол обеспечивает сходимость всех процессов к априори заданному периодическому процессу 7Г°, который удовлетворяет упомянутому необходимому условию оптимальности и в остальном произволен. Использовано разбиение (1) процесса 7Г° на простейшие фазы, в течение которых дискретное состояние Q постоянно. Для активных фаз предложенное правило управления предписывает обслуживать буфер п на максимальной скорости пока отношение конечного и начального (для данной фазы) объема буфера не сравняется с отношением, наблюдаемым для тг°. Затем буфер обслуживается на скорости входящего потока столько времени, сколько такое обслуживание производилось для 7Г°.

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

В главе 4 дано решение задачи синтеза протокола управления потоковой переключательной сетью с одним сервером и разделением его ресурсов. Рассматриваемая система состоит из N буферов и одного сервера; работа поступает в м-ый буфер с постоянной скоростью А„ > 0 и после обработки сервером покидает систему. Сервер имеет конечное число рабочих режимов (мод) m € M. В моде m он одновременно обслуживает фиксированный набор Ат С [1 : Аг] буферов, извлекая содержимое xn(t) буфера п 6 Аш со

скоростыо u.n(t), варьируемой в заданных границах un{t) € [0,/д„|ш]. Пер^ ключепнс между модами т' —> т" е М, т' ф т" требует ёт'->т" > 0 единиц времени. Множества Ат необязательно дизъюнктны; \JmeMAm = [1 : N]. Скорости un{t) обслуживания, а также момент отключения текущей моды и следующая за ней мода определяются протоколом управления.

Определение 4.1 Процесс назовем интенсивным маргинальным, если в любой моде q(t) = ш. t, (Е каждый буфер п Е Atn обслулсивастся на некотором начальном отрезке с максимальной скоростью u„(t) = цп\т, t € [t-,t™], а на некотором заключительном — с нулевой u„(t) = 0,i G с возможным средним отрезком, где буфер пуст xn(t) = 0, t € и каждый буфер п € А]п := {п € Ат : цп|т < Л,,} постоянно обслуживается на макслшальной скорости un{t) = fj,n|т.

Лемма 4.1 Для любого периодического процесса тг = [Х(-),д(-)] с]]ществу-ет. интенсивный маргинальный периодический прогресс ift = pft(-), qt(-)] с лучшим качеством обслуживания %l(t) < xn(t) \/t,n, для которого любой буфер опустошается хотя бы раз за период.

Лемма 4.1 дает основание ограничиться рассмотрением интенсивного маргинального периодического процесса тг° = [Х°(-), <j°(-)]. В главе 4 предложен протокол управления, предписывающий серверу пробегать циклически повторяемую последовательность мод т^... ,nu-, наблюдаемую в течение периода 7г°. В моде ш; буферы п € А}п. обслуживаются на скорости ип = /(„|„7;, причем при А^п := А„, \ А]п = 0 время обслуживания в моде пг,- то же, что и для 7г°. Если А\п. ф 0, каждый буфер п е А^ сначала обслуживается на скорости /in|m. до тех пор, пока отношение его текущего и начального (для данной моды) объема не достигнет того же значения, что и для 7г°. Затем он последовательно обслуживается на скорости ип = \п и и„ = 0, причем длительности соответствующих интервалов времени те же, что и для тг0. В момент завершения предыдущей задачи сервер записывает end(n|a') = 1 и переходит к обслуживанию буфера на скорости ип = А„, поддерживая его уровень неизменным. Мода завершается, как только end(n|/) = 1 Vra 6 Л^., после чего end(»|i) := 0 н сервер начинает переключение в следующую моду. Таким образом, обслуживание буфера опирается на данные только о нем самом, а "межбуферная"координация — на однобитовые сообщения end(n|i).

Теорема 4.1 Предложенный протокол порождает единственный периодический процесс, этот процесс равен априори заданному 7Г° и к нему сходятся все процессы в рассмат.ривае.мой системе.

В пятой главе рассматривается популярная в качестве тестового примера производственная сеть Кумара-Сейдмана. Этот частный случай сети нз главы 1 состоит из четырех буферов и двух серверов и обслуживает один

Рис. 1: Потоковая переключательная сеть Кумара-Сейдмана

(а) (Ь)

Рис. 2: Оптимальный периодический процесс.

поток, см. Рис. 1. Периодический процесс в системе назовем простым, если каждый сервер обслуживает каждый ассоциированный с ним буфер только один раз за минимальный период. Рассмотрим задачу минимизации среднего по времени количества работы в системе:

_ I [Т 4

У ГДС «-'(*):= X] с„1„(4). (4)

" 11— 1

Здесь с„ > 0 — заданный коэффициент, причем сл > С2 > сз > с4 > 0.

Теорема 5.1 Оптимальный простой периодический процесс существует и имеет структуру, изображенную на одном из Рис. 2 (а), (Ь), причем буферы обслуживаются на максимальной возможной скорости. Вариант структуры зависит от параметров системы и коэффициентов с„ из (4).

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

Рсшсна задача синтеза протокола, асимптотически выводящего снеток из любого начального состояния в оптимальный режим 7Г° из Теоремы 5.1 Охарактеризуем протокол и соответствующий результат в случае (Ь).

Процесс делится на две фазы Р\ и А в соответствии с Рис. 2(Ь); буфера обслуживаются па максимальной скорости. В течение фазы Г\ сервер < обслуживает буфер 3 до опустошения, затем переключается в буфер 2 и об служнвает его до опустошения, п, наконец, возможно простаивает, ожидая когда сервер 1 завершит свою миссию па этой фазе. Тем временем сервер 1 опустошает буфер 4, затем проходит первую масть переключения в буфер 1 в течение времени, которое эта часть длилась для 7г°, а затем возможно простаивает, ожидая пока сервер 2 опустошит буфер 2. Фаза завершается, ка* только буфер 2 опустошен, а сервер 1 завершил требуемую часть переключения 4 —> 1. В фазе Р2 сервер 1 завершает переключение 4 —» 1, затеи опустошает буфер 1 и обслуживает его па скорости входящего потока в течение времени, которое такое обслуживание наблюдалось для 7Г°, и возможне дольше для того, чтобы покинуть буфер 1 не раньше, чем пройдет 01-+-

единиц времени с начала фазы, и наконец переключается в буфер 4 — время переключения из буфера г в ]). Тем временем сервер 2 переключаете? из буфера 2 в 3, а затем простаивает, ожидая пока сервер 1 завершит свок миссию. Фаза завершается в момент окончания переключения 1 —> 4.

Теорема 5.2 В сети Кумара-Сейдмана, управляемой предложенным протоколом,, все процессы сходятся к оптимальному периодическому процессу.

Для случая (а) с Рис. 2 получен аналогичный результат.

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

Доказана теорема, показывающая, что при определенных условиях оптимальна максимально возможная скорость обслуживания буферов. Прн построении протокола рассматривается процесс 7Г° с указанным свойством и применяется его деление (1) на простые фазы в течение которых дискретное состояние постоянно С} = Переключательная фаза С}= (0,.... О) поддерживается столько времени, сколько она поддерживалась для 7Г°. Для прочих фаз = (»!,.... пя) ф (0,..., О) каждый обслуживаемый на этой фазе буфер п = п„ ф 0 вначале обслуживается со скоростью /(„ до момента г, когда его содержимое начинает уменьшаться, и далее до момента, когда отношение текущего объема буфера к его объему в момент "перегиба"т не сравняется с отношением, наблюдавшимся на 7Г°. После этого объем буфера поддерживается постоянным до конца фазы, но не менее времени, в течение которого он поддерживался постоянным для процесса 7Г°. Фаза прекращается как только задание выполнено для всех обслуживаемых на фазе буферов.

Буфер, непосредственно принимающий поток из некоторого внешнего источника, назовем входным, а их множество обозначим через IN.

Теорема 6.1 Пусть у периодического процесса 7г° с вышеуказанным свойством суи^ествуст чисто переключательная фаза Qi = (0, ...,©) и более того, такая фаза щзделяет любую фазу, завершающуюся опустошением буфера п е IN, и любую последующую фазу, на которой этот буфер обслуживается. Тогда предложенный протокол управления порождает процесс 7Г° и обеспечивает сходимость к нему вссх процессов при i —» оо.

Седьмая глава диссертации содержит доказательство Теоремы G.I.

Восьмая глава диссертации посвящена анализу специального, но широко применяемого на практике класса протоколов управления производственными линиями, в которых реализован принцип обратной связи от текущего запроса (pull-type, pull-controlled). Единая математическая модель этого класса протоколов предложена К.К. Старковым и А.Ю. Погромскнм. В главе 8 впервые обоснована оптимальность этих протоколов.

Модель производственного процесса в системе с одним производственным сервером задана уравнением

где у(к) еК- суммарный выход сервера в момент к, и(к) 6Й- управляющий сигнал п /(к) е М - неизвестное внешнее возмущение, влияющее на скорость работы сервера. Целыо управления является отслеживание неубывающего запроса у,{(к) € М на продукцию, удовлетворяющего соотношению

где ум > 0 — начальный запрос, v,^ — средняя скорость приращения запроса п <р(к) 6 К — се ограниченное колебание. В каждый момент времени к управление и может принимать только два значения: 1 или 0 ("вкл"пли "выкл"). Требуется минимизировать ошибку отслеживания запроса е(к) = у,1{к) — у(к) в классе всех стратегий управления, основанных па доступных данных:

Предполагаем, что 0 < £(к) := гу + А<р(к) - ¡(к) < 1 Ук, а также отсутствие данных, позволяющих уточнить значение £(к) € (0,1).

В главе 8 исследованы следующие две оптимизационные задачи:

у(к + 1) = у(к) + и(к) + f(lc), к = 0,1,..

y,i(k) = ум + vdk + <р{к),

и(к) = £%(0),...,y(k),yd(0),...,ytI(k)} е {0,1} .

т

Jt = sup

Joe. = lini sup|c(&)| mill.

k—loe U

к—too

Здссь р > 1 - заданная константа, sup берется по всем £(к) € (0,1) и U {£4(-)} - множество всех допустимых стратегий управления.

Теорема 8.2 Стратегия управления и(к) = б[е(/с)] оптимальна как для критерия (5) при любых Т и р € [1, +оо), так и для критерия (6). Здесь 6(e) := 1 при £ > 0, 6(e) := 0 при £ < 0, и 6(e) := 0,1 при £ = 0.

Публикации автора по теме диссертации. Статьи в рецензируемых журналах и изданиях:

[1] Феоктистова В.Н., Матвеев А.С. Динамическая интерактивная стабилизация переключательной системы Кумара-Сейдмана. // Вестник СПбГУ , 2009. Серия 1, выи. 3, стр. 86-97.'

[2| Феоктистова В.Н. Динамическая интерактивная стабилизация потоковых систем с разделением процессора. // Вестник СПбГУ, 2011. Серия 1. вып. 3, стр. 75-80.

[3] К.К. Starkov, V. Feoktistova, A.Y. Pogromsky, A. Matveev, J.E. Rooda. Performance analysis of a manufacturing line operated under optimal surplus-based production control. /'/' Mathematical Problems in Engineering, 1-2G, 2012, doi: 10.1155/2012/602094, online.

Другие публикации:

[4] V. Feoktistova, A. Matveev. Generation of production cycles in multiple server system,s with setup times: The case study. / Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, Russia, 2009, pp. 568-573.

[5] V. Feoktistova, A. Matveev, E. Lefeber, J.E. Rooda. Designs of optimal switching feedback decentralized control policies for re-entrant queueinc, networks: A case study. / Proceedings of the 10th IFAC Workshop on Intelligent Manufacturing Systems, 2010, pp. 187-193.

[6] V. Feoktistova, A. Matveev, E. Lefeber, J.E. Rooda. On Optimal Switching Interactive Decentralized Control of Networked Manufacturing Systems. / Proceedings of the 18th IFAC World Congress, Milan, Italy, 2011, pp. 1404814054.

[7] K.K. Starkov, V. Feoktistova, A.Y. Pogromsky, A. Matveev, J.E. Rooda. Optimal production contol method for tandem manufacturing lines. / Proceedings of the PHYSCON 2011, Leon, Spain, 2011.

Публикации [4,6] имеют признаки соответствия перечню рецензируемых журналов н изданий: они опубликованы в изданиях, которые охвачены системой цитирования Scopus и содержание которых включено в журнал IFAC papers online издательства Elsevier.

Подписано в печать 21 апреля 2012 года. Формат 60x84 1/16.

Усл.Печ.Л. 1,0. Тираж 100 экз. Заказ № 1755. Отпечатано в цифровом копировальном центре «Средний-28» 199004, Санкт-Петербург, В.О., Средний пр., 28. Тел.: (812) 323-40-44

61 12-1/1082

Санкт-Петербургский Государственный Университет

На правах рукописи

Феоктистова Варвара Николаевна

Математические проблемы управления потоковыми переключательными сетями

специальность 01.01.09 — Дискретная математика и математическая

кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук.

профессор Матвеев Алексей Серафимович

Санкт-Петербург 2012 г.

- 2 -Содержание

Содержание ..................................................2

Введение........................................................5

Глава 1. Математическая Постановка Проблемы и Предлагаемый Подход к ее Решению........................................27

1.1. Жидкостная модель потоковой переключательной сети и поста-

новка задачи . ............................27

1.2. Предлагаемый метод трансформации периодического процесса

в протокол управления .......................39

Глава 2. Глобальная Устойчивость Кусочно-Аффинных Систем 44

2.1. Определения ..............................45

2.2. Основной Результат . ..........................46

2.3. Наследование основных свойств при композиции.........47

2.4. Собственные числа и векторы однородных КАМН - операторов . 50

2.5. Однородное ядро КАМН оператора.................54

2.6. Дифференциал КАМН-оператора..................58

2.7. Глобальная устойчивость неподвижных точек

КАМН-операторов..........................59

2.8. Доказательство Теоремы 2.1 .....................62

Глава 3. Односерверная переключательная сеть: система "пол-

линга" .............................................................66

3.1. Введение . . ..............................66

3.2. Описание системы и протокола управления ............67

3.3. Основной результат..........................70

3.4. Заключение ..............................71

Глава 4. Потоковая Сеть с Разделением Процессора............73

4.1. Введение................................73

4.2. Описание системы и генерируемого периодического процесса . . 74

4.3. Глобальная Стабилизация Процесса .................77

4.4. Основной результат ..........................79

4.5. Доказательство Леммы 4.2 ......................80

4.6. Заключение ..............................80

Глава 5. Производственная сеть Кумара-Сейдмана....... 82

5.1. Введение и Описание Системы ............ ........82

5.2. Оптимальный периодический процесс в системе Кумара-Сейдмана 84

5.3. Параметры, характеризующие оптимальный периодический про-

цесс...................................88

5.4. Доказательство Теоремы 5.2.....................91

5.5. Оптимальный протокол переключения...............94

5.6. Доказательство Теоремы 5.3.....................103

5.7. Заключение ...............................105

Глава 6. Общая сеть..........................107

6.1. Периодические процессы с интенсивным обслуживаем буферов . 107

6.2. Доказательство Утверждения 6.1..................110

6.3. Глобальная стабилизация производственного цикла протоколом

переключения .............................115

6.3.1 Чисто переключательная фаза (^[ф] = (Э, О) . . . .116

6.3.2 Фазаф с активными буферами ф := = (пь • • • • пз) ф-(©, ...,©)............................116

6.3.3 Протокол управления.....................120

6.4. Заключение ..............................121

Глава 7. Доказательство Теоремы 6.1...............122

7.1. Чисто переключательная фаза = (0,. .■■, 0).........122

7.2. Фаза с активными буферами

Q:=Q№] = (ni,...,ne)^( 0,...,0)...............122

7.3. Функция чувствительности фазы ф с активными буферами . . . 128

7.4. Строгая доминантность и завершение доказательства Теоремы 6.1134

Глава 8. Оптимальный метод отслеживания производственного запроса................................138

8.1. Введение................................138

8.2. Математическая модель односерверной производственной системы 142

8.3. Оптимальная стратегия управления.................144

8.4. Доказательство Теоремы 8.1.....................146

8.5. Заключение ..............................150

Список литературы..........................154

Введение

Общая характеристика проблемной ситуации, на разрешение которой нацелена работа

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

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

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

Хотя на практике многие из обсуждаемых сетевых систем были внедрены сравнительно недавно, на уровне математической абстракции связанные с ними проблемы исследовались и ранее. Это в частности касается эффективного распределения сетевых ресурсов, буферирования и управления буферами. Ряд возникающих здесь вопросов сводим к проблемам, составляющим предмет традиционной теории расписаний (the theory of scheduling and sequencing). К ним относится проблема нахождения оптимального (субоптимального) распределения ресурсов при наличии ограничений. Хотя обширная литература1 на эту тему предлагает ряд проработанных подходов к проблеме, в целом они ориентированы на оптимизацию статических алгоритмов, реализуемых централизованно и как правило в виде временной программы на основе полной информации о текущем состоянии системы и для неизменной и априори известной обстановки. Это противоречит реалиям многих совре-

ее обзором можно ознакомиться в [8,20,25,28,38,43,48,62,63,78].

менных сетевых систем (производственных, информационных, транспортных и др.), которые функционируют в динамичной и непредсказуемой среде и в которых решения принимаются децентрализованно. Следствием является констатируемый в настоящее время принципиальный разрыв между теорией и практикой [29,71,92], квалифицируемый как один из основных тормозов на пути повышения эффективности многих практических сетевых систем. Суть разрыва состоит в том, что для парирования неопределенностей и адаптации к изменчивым условиям на практике применяют алгоритмы управления типа обратной связи (так называемые, интерактивные протоколы управления сетями [6,69]). Однако в настоящее время большинство из них основано на эвристике, что отражает пока все еще скромные возможности теории синтеза таких алгоритмов, которая является хотя и бурно развивающейся, но весьма молодой дисциплиной; с ее обзором можно ознакомиться в [77]. Вместе с тем потребность в такой теории была неоднократно подчеркнута анализом основанных на эвристике алгоритмов, в результате которого обнаруживалось, что эти алгоритмы могут порождать контр-интуитивное и сложное поведение замкнутой системы, не соответствующее первоначальным ожиданиям и часто неприемлемое.

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

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

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

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

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

1. Определение текущей скорости изъятия содержимого из обслуживаемого буфера;

2. Выбор момента прекращения обслуживания;

3. Выбор следующего буфера.

Перечисленные решения должны быть приняты для каждого сервера. Во многих случаях решение задачи 1 находится сравнительно просто и заключается в обслуживании на максимально возможной скорости. На этом фоне проблема фокусируется на решении задач 2 и 3, то есть на управлении системой за счет переключений серверов. Так как при этом та часть состояния системы, которая характеризует текущие объемы буферов, изменяется с течением времени непрерывно, задача демонстрирует признаки переключательного (дискретного) управления непрерывной динамической системой. Соответствующие алгоритмы относятся к сфере интересов молодой и бурно развиваемой в последнее десятилетие дисциплине — теории управляемых гибридных динамических систем [75].

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

проксимации в определенной ситуации, см., например, [17,18,22,30,31,44-46] и литературу оттуда. Во многих из перечисленных приложений потоки в системе являются дискретными и стохастические модели дают их более адекватное (хотя и приближенное) описание. Вместе с тем такие модели сложнее анализировать, что в случае больших систем, каковыми и является большинство современных сетевых систем, делает получение законченных и содержательных результатов проблематичным. В этом случае жидкостная модель интересна как "первое"приближение, которое делает реалистичным содержательный анализ эффектов, связанных с взаимодействием и координацией множества агентов в большой системе. Вместе с тем достигается это за счет огрубления в описании "локальных"эффектов.

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

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

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

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

Текущее состояние вопроса. Проблеме синтеза протоколов посвящена обширная литература. В основном она касается поиска расписаний, то есть временных программ действий, часто оптимальных или субоптимальных (см., например, [8,37,38,43,53,82,100], и литературу о