Помощь студентам в учебе
Построение оптимальных потоковых процессов в задачах распределения загрузки вычислительной сети
|
1 Введение 5
2 Оптимальные динамические процессы 8
3 Динамические потоковые процессы 12
4 Метод проталкивания предпотока для потоковых задач линейного
программирования 16
4.1 Общая классификация потоковых задач 16
4.2 Задача о максимальном потоке 17
4.3 Задача о параметрическом потоке 22
5 Потоковые процессы в условиях
неопределенностей 29
5.1 Класс усредняемых функций 30
5.2 Динамические потоковые процессы с
меняющимися во времени пропускными способностями 32
5.3 Подбор параметров алгоритма в стохастическом слу¬чае 38
6 Практические примеры 41
6.1 Задача балансирования нагрузки в
вычислительной сети 41
6.2 Обмен информацией групп БПЛА 44
7 Заключение 47
Литература 48
2 Оптимальные динамические процессы 8
3 Динамические потоковые процессы 12
4 Метод проталкивания предпотока для потоковых задач линейного
программирования 16
4.1 Общая классификация потоковых задач 16
4.2 Задача о максимальном потоке 17
4.3 Задача о параметрическом потоке 22
5 Потоковые процессы в условиях
неопределенностей 29
5.1 Класс усредняемых функций 30
5.2 Динамические потоковые процессы с
меняющимися во времени пропускными способностями 32
5.3 Подбор параметров алгоритма в стохастическом слу¬чае 38
6 Практические примеры 41
6.1 Задача балансирования нагрузки в
вычислительной сети 41
6.2 Обмен информацией групп БПЛА 44
7 Заключение 47
Литература 48
В последние десятилетия сетевые технологии обретают все большую актуальность, и уже сейчас возможность решать различные задачи, воз-никающие в сетевых системах, является одним из самых важных прило¬жений компьютерных и кибернетических наук. Как и для многих других крупных областей, существует огромное множество задач различных по своей структуре и возможным подходам к решению, в этой области ско¬рее всего даже не существует универсальных подходов к решению 95% всех возникающих задач. К хорошо изученным теоретическим моделям, которые чаще всего применимы в теории и практике, можно причислить только наиболее общие - теорию графов, теорию динамических систем, методы математической оптимизации и т. и.
Класс задач, рассматриваемый в этой работе, нацелен на изучение по-токовых процессов в сетях. Потоковый процесс заключается в движении частиц внутри некоторой замкнутой системы, при этом ни одна частица не покидает систему, и ни одна частица не проникает в систему извне. В этой работе будут рассматриваться сетевые системы, взаимодействие ко¬торых традиционно моделируется с помощью теории графов: вершины графа являются промежуточным местом для хранения потока, а дуги (ребра) являются средством циркуляции потока по графу (здесь и да¬лее при использовании термина “дуга” подразумевается, что движение возможно в одну сторону, а при использовании термина “ребро” - в обе стороны. В дальнейших разделах этот нюанс будет формализован бо¬лее строго, но стоит иметь в виду, что в потоковых задачах отсутствует качественное различие между ориентированным и неориентированным случаями). Другими словами, частицы потока могут перемещаться от од¬ной вершины до другой по ребру, соединяющей эти вершины. В качестве практических примеров потоковых процессов можно привести следую¬щие ситуации:
• Движение автомобилей по дорогам. Здесь частицами потока явля¬ются машины, ребра - дороги / улицы, узлы - пересечение дорог / улиц.
• Движение жидкости / газа по трубопроводу. Частицы потока - жидкость или газ, ребра - трубы, узлы - трубопроводные краны, распределительные станции.
• Движение данных в информационных сетях. Частицы потока - па¬кеты данных, ребра - каналы связи, вершины - логические и вы¬числительные устройства.
Длина, время перехода
Рис. 1: Параметры дуги в транспортной сети.
Свойства, ограничения и параметры движения потока по ребру могут варьироваться в зависимости от задачи, по в целом для потоковых задач приняты следующие характерные свойства движения потока:
1. Объем потока, который может пройти по ребру за единицу време¬ни (или за любой конечный интервал времени) ограничен, точную верхнюю границу этого объема принято называть пропускной спо¬собностью ребра.
2. Частицы потока проходят по ребру не мгновенно, а па протяжении некоторого интервала времени.
Как изображено па рис. 1, в случае транспортных потоков эти вели¬чины могут быть интерпретированы как ширина и длина дороги соот¬ветственно.
Ключевым аспектом этой работы является изучение динамических моделей потоковых процессов, т.е. таких моделей, которые учитывают временное измерение. Во многих случаях изучение протекающих во вре¬мени потоковых процессов может быть сведено к рассмотрению стаци¬онарных потоковых задач. Так, например, в [1-4] рассмотрены статиче¬ские методы моделирования транспортных потоков, в [5] (одна из наи¬более ранних работ па эту тему) и [6 рассмотрены динамические пото¬ковые процессы, задачи нахождения оптимального процесса со статиче¬скими пропускными способностями сведены к статическим потоковым задачам. Работы [5-7] имеют постановки, схожие с рассматриваемыми в этой работе, и, в том числе, показывают актуальность этих задач. Эти работы имеют прямое отношение к задаче о максимальном потоке и задаче потока минимальной стоимости, введенных в [8]. Несмотря на более полувека с момента появления, постановки этих задач, допус¬кающие неопределенности некоторых характеристик, появились относи¬тельно недавно (см. [9-11]). При этом, на данный момент отсутствуют работы, изучающие потоковые задачи в условиях динамически изменя¬ющихся параметров и внешних неконтролируемых возмущений. Анализ поведения потоковых процессов в таких ситуациях является основным теоретическим вкладом этой работы.
Работа организована следующим образом: в разделе 2 приведены об¬щие сведения о динамических системах, сформулирован общий вид задач без неопределенностей, рассматриваемых в работе, и получено сведение задачи нахождения оптимального процесса к задаче выпуклой оптими¬зации. В разделе 3 описана специфика параметров потоковых процессов в рассматриваемых задачах оптимального управления, подробнее описа¬ны оптимизационные задачи, которые необходимо решить для построе¬ния оптимального процесса. В разделе 4 подробно описаны потоковые задачи линейного программирования, возникающие при построении оп¬тимального процесса, и эффективные методы их решения. В разделе 5 сосредоточен основной вклад работы: показано, что если меняющиеся во времени пропускные способности принадлежат классу усредняемых функций (как функции по времени), то оптимальное время работы систе¬мы асимптотически эквивалентно оптимальному времени работы “усред-ненной” системы; приведены примеры построения субоптимальных ре¬шений в стохастических случаях. В разделе 6 приведены практические примеры динамических потоковых процессов с неопределенностями.
Класс задач, рассматриваемый в этой работе, нацелен на изучение по-токовых процессов в сетях. Потоковый процесс заключается в движении частиц внутри некоторой замкнутой системы, при этом ни одна частица не покидает систему, и ни одна частица не проникает в систему извне. В этой работе будут рассматриваться сетевые системы, взаимодействие ко¬торых традиционно моделируется с помощью теории графов: вершины графа являются промежуточным местом для хранения потока, а дуги (ребра) являются средством циркуляции потока по графу (здесь и да¬лее при использовании термина “дуга” подразумевается, что движение возможно в одну сторону, а при использовании термина “ребро” - в обе стороны. В дальнейших разделах этот нюанс будет формализован бо¬лее строго, но стоит иметь в виду, что в потоковых задачах отсутствует качественное различие между ориентированным и неориентированным случаями). Другими словами, частицы потока могут перемещаться от од¬ной вершины до другой по ребру, соединяющей эти вершины. В качестве практических примеров потоковых процессов можно привести следую¬щие ситуации:
• Движение автомобилей по дорогам. Здесь частицами потока явля¬ются машины, ребра - дороги / улицы, узлы - пересечение дорог / улиц.
• Движение жидкости / газа по трубопроводу. Частицы потока - жидкость или газ, ребра - трубы, узлы - трубопроводные краны, распределительные станции.
• Движение данных в информационных сетях. Частицы потока - па¬кеты данных, ребра - каналы связи, вершины - логические и вы¬числительные устройства.
Длина, время перехода
Рис. 1: Параметры дуги в транспортной сети.
Свойства, ограничения и параметры движения потока по ребру могут варьироваться в зависимости от задачи, по в целом для потоковых задач приняты следующие характерные свойства движения потока:
1. Объем потока, который может пройти по ребру за единицу време¬ни (или за любой конечный интервал времени) ограничен, точную верхнюю границу этого объема принято называть пропускной спо¬собностью ребра.
2. Частицы потока проходят по ребру не мгновенно, а па протяжении некоторого интервала времени.
Как изображено па рис. 1, в случае транспортных потоков эти вели¬чины могут быть интерпретированы как ширина и длина дороги соот¬ветственно.
Ключевым аспектом этой работы является изучение динамических моделей потоковых процессов, т.е. таких моделей, которые учитывают временное измерение. Во многих случаях изучение протекающих во вре¬мени потоковых процессов может быть сведено к рассмотрению стаци¬онарных потоковых задач. Так, например, в [1-4] рассмотрены статиче¬ские методы моделирования транспортных потоков, в [5] (одна из наи¬более ранних работ па эту тему) и [6 рассмотрены динамические пото¬ковые процессы, задачи нахождения оптимального процесса со статиче¬скими пропускными способностями сведены к статическим потоковым задачам. Работы [5-7] имеют постановки, схожие с рассматриваемыми в этой работе, и, в том числе, показывают актуальность этих задач. Эти работы имеют прямое отношение к задаче о максимальном потоке и задаче потока минимальной стоимости, введенных в [8]. Несмотря на более полувека с момента появления, постановки этих задач, допус¬кающие неопределенности некоторых характеристик, появились относи¬тельно недавно (см. [9-11]). При этом, на данный момент отсутствуют работы, изучающие потоковые задачи в условиях динамически изменя¬ющихся параметров и внешних неконтролируемых возмущений. Анализ поведения потоковых процессов в таких ситуациях является основным теоретическим вкладом этой работы.
Работа организована следующим образом: в разделе 2 приведены об¬щие сведения о динамических системах, сформулирован общий вид задач без неопределенностей, рассматриваемых в работе, и получено сведение задачи нахождения оптимального процесса к задаче выпуклой оптими¬зации. В разделе 3 описана специфика параметров потоковых процессов в рассматриваемых задачах оптимального управления, подробнее описа¬ны оптимизационные задачи, которые необходимо решить для построе¬ния оптимального процесса. В разделе 4 подробно описаны потоковые задачи линейного программирования, возникающие при построении оп¬тимального процесса, и эффективные методы их решения. В разделе 5 сосредоточен основной вклад работы: показано, что если меняющиеся во времени пропускные способности принадлежат классу усредняемых функций (как функции по времени), то оптимальное время работы систе¬мы асимптотически эквивалентно оптимальному времени работы “усред-ненной” системы; приведены примеры построения субоптимальных ре¬шений в стохастических случаях. В разделе 6 приведены практические примеры динамических потоковых процессов с неопределенностями.
В работе был рассмотрен класс динамических потоковых задач, по¬дробно проанализированы свойства этого класса задач в условиях неопре¬деленностей, приведены практические примеры, в которых возникает такой класс потоковых задач. Подытоживая ключевые аспекты работы можно выделить следующие выводы:
• Теоретические результаты, изложенные в разделе 5, показывают, что традиционные методы решения потоковых задач могут быть адаптированы для практических задач с неопределенностями. Ос¬новной результат раздела (теорема 5.2) показывает, такая адапта¬ция работает асимптотически оптимально. В практическом смысле это означает, что если есть система циркуляции потока с указан¬ным классом неопределенностей, которая работает неограниченное время, то адаптированное решение создаст некоторую задержку в работе системы по сравнению с оптимальным временем работы, но не больше, чем на величину, которая зависит от функций про¬пускных способностей и размера системы, но не от времени работы системы.
• Рассмотренные алгоритмы решения задач параметрического пото¬ка довольно эффективны и позволяют проводить вычисления для сетей с 105 узлами в течение пары секунд, собственная реализация этих методов соизмерима по производительности с “эталонной” ре¬ализацией [50].
• Чем меньше степень “регулярности” пропускных способностей, тем меньше оправдано применение описанных методов, особенно для маленьких сетей. Как пример, в задаче обмена информацией БП- ЛА можно построить более точное решение, если проводить дис¬кретизацию времени и решать несколько потоковых задач (или же одну потоковую задачу, но большего размера) на отдельных участ¬ках времени.
• Теоретические результаты, изложенные в разделе 5, показывают, что традиционные методы решения потоковых задач могут быть адаптированы для практических задач с неопределенностями. Ос¬новной результат раздела (теорема 5.2) показывает, такая адапта¬ция работает асимптотически оптимально. В практическом смысле это означает, что если есть система циркуляции потока с указан¬ным классом неопределенностей, которая работает неограниченное время, то адаптированное решение создаст некоторую задержку в работе системы по сравнению с оптимальным временем работы, но не больше, чем на величину, которая зависит от функций про¬пускных способностей и размера системы, но не от времени работы системы.
• Рассмотренные алгоритмы решения задач параметрического пото¬ка довольно эффективны и позволяют проводить вычисления для сетей с 105 узлами в течение пары секунд, собственная реализация этих методов соизмерима по производительности с “эталонной” ре¬ализацией [50].
• Чем меньше степень “регулярности” пропускных способностей, тем меньше оправдано применение описанных методов, особенно для маленьких сетей. Как пример, в задаче обмена информацией БП- ЛА можно построить более точное решение, если проводить дис¬кретизацию времени и решать несколько потоковых задач (или же одну потоковую задачу, но большего размера) на отдельных участ¬ках времени.
