Книги по разным темам Pages:     | 1 |   ...   | 24 | 25 | 26 | 27 | 28 |   ...   | 32 |

4.14.3. АЛГОРИТМ ДЛЯ МОДЕЛЕЙ СЕТЕВОГО ТРАФИКА ТИПА ФРАКТАЛЬНОГО БРОУНОВСКОГО ДВИЖЕНИЯ В современных компьютерных сетях соединение между пользователями осуществляется ТСР/IР протоколом. В соответствии с алгоритмом функционирования этого протокола пропускная способность со стороны источника в фазе медленного старта определяется текущим окном перегрузки, равным числу разрешенных к передаче пакетов до прихода пакетов подтверждения. На Рис. 4.4.

представлен процесс формирования и эволюции окна перегрузки размера Wi для выбранного виртуального соединения источникприемник по одному из вариантов реализации ТСР/IР протокола, где i - номер шага фазы медленного старта.

На первом шаге после отправки пакета с номером 1 разрешается передать еще W1-1 пакетов до получения пакета подтверждения на посланный пакет с номером 1. На втором и всех последующих шагах, если пакеты подтверждения поступают более или менее регулярно, величина окна каждый раз увеличивается в два раза. В результате достигается максимально возможная (но не более заявленного со стороны приемника окна перегрузка) для данного соединения и принятого протокола пропускная способность соединения. Алгоритм, формирующий окно перегрузки по сигналу обратной связи в виде пакетов подтверждения, называется алгоритмом скользящего окна, так как при очередном получении пакета подтверждения окно перемещается (и увеличивается на один пакет на каждый шаг алгоритма), захватывая очередные пакеты, которые разрешается передавать без подтверждения. Допустим, что из-за очередей в промежуточных узлах - маршрутизаторах, а также из-за переполнения буферов в этих узлах соединение сети не справляется с нагрузкой. Вследствие этого часть пакетов чрезмерно задерживаeтся в пути и даже, может быть, теряется (на Рис. 4.4 задерживается один пакет на i+1 шаге). В этом случае пакеты подтверждения не отсылаются и протоколом ТСР на стороне источника на шаге i+формируется окно уменьшенного размера, равное своему значению Wi на i-м шаге, и достоверность передачи обеспечивается через механизм повторения посылки пакетов. На этом заканчивается фаза медленного старта и начинается фаза управления перегрузкой, сопровождающая для налаживания и поддержания соединения локальными воздействиями и определением каждый раз текущего окна перегрузки.

tTi+TWi+1-Wi+W1-ti+W1 ty TTi+Ti Wi-Wi-ti ti+2 Wi Wi t t Рис. 4.4. Процесс формирования и эволюции окна перегрузки.

Интервал времени между моментами посылки пакета в направления приемника получения пакета подтверждения определяется RTT-задержкой (round trip time)*). Чтобы избежать длительных простоев из-за ожидания потерянных или задержавшихся пакетов вводится пороговое значение RTT-задержки (тайм-аут - y).

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

Во-первых, перегрузка не прогнозируется, а обнаруживается по самому факту отсутствия пакетов подтверждения после очередного перемещения окна, во-вторых, по этому факту нельзя судить о величине перегрузки и следующее состояние окна устанавливается методом проб и ошибок. Задача заключается в формировании заблаговременно, не заходя в критическую область обнаружения потерянных пакетов, оценок как месторасположения временного интервала возможного проявления перегрузки, так и величины самой перегрузки. Решение такой задачи можно получить в рамках методов идентификации процессов, использования при моделировании RTTзадержек фрактального броуновского движения и формирования оценок прогноза. Временной интервал RTT-задержки складывается из времени обработки и распространения, а также затрат времени на очереди вдоль маршрута прохождения пакетов. Для стационарного процесса RTT-задержку, которую обозначим через Ti, можно записать в виде (Рис. 4.5.) Ti=T1i+T2i+Tпр, где i=1,2,... номер задержки (шага), интервалы T1i и T2i соответствуют временам пересылки пакета от источника к приемнику и обратно, Tпр - время обработки информации в приемнике.

Совокупность интервалов {Ti} образует дискретную последовательность RTT-задержек. Интервалы T1i и T2i отражают задержки в обработке и передаче информации, а также наличие очередей в промежуточных узлах сети. Для известного маршрута движения пакета можно выделить постоянную минимальную обусловленную отсутствием очередей составляющую T0 и случайную составляющую из-за задержек в очередях и связанную со случайным поведением сетевого трафика Ti: Ti=T0+Ti.

ti T1i Tпр Ti T2i ti+t t Рис. 4.5. Процесс RTT-задержки.

Рассматривая выражение Ti-M{Ti}, где M{Ti}=T0+Tср, Tср - среднее значение приращений RTT-задержек, в качестве случайного приращения RTT-задержки, сформируем для момента времени tn фрактальный броуновский процесс [58].

n BH (tn) = [T - (T0 + Tср )].

i i Полагаем, что моменты времени ti (i=1,n) образуют регулярную последовательность дискретных временных отсчетов. Для определенности интервалы между отсчетами принимаем равными средней величине RTT-задержки =T0+Tср. В соотношении (2.132) отождествим текущие времена t2 и t1 с моментами времени tn+k и tn(tn+k-tn=k), где k - параметр смещения. Используя это выражение, запишем соотношение для корреляционной функции процесса 2H 2H k2H (tn,tn+k ) = M{BH (tn )BH (tn+k )} ~ [tn + tn+k - | tn+k - tn |2H ].

Из-за нестационарного характера фрактального броуновского движения коэффициент корреляции записывается в форме, зависящей от текущего времени tn источник приемник 2H 2H k2n(tn,tn+k ) tn + tn+k - | tn+k - tn |2H rn(k;) = = = 2H D(tn) 2tn (4.218) = [1+ Sn,H - | Sn,n+k -1|2H ], n+k где Sn,n+k=tn+k/tn.

Оптимальная в среднеквадратическом смысле оценка прогноза фрактального броуновского движения в момент времени tn+k при известном (измеренном точно) указанном процессе в момент tn на основании (4.165) равна Bn(tn+k ) = M{BH (tn+k ) | BH (tn)} = rn(k;)BH (tn)*) (4.219) Оптимальная оценка прогноза RTT-задержки для момента времени tn+k принимает вид Tn+k = BH (tn+k ) - BH (tn+k -1) + T0 + Tср = (4.220) = [rn(k;) - rn(k -1;)]BH (tn) + T0 + Tср.

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

На основании формулы (4.220) имеем T = B (tn+1)-BH(tn)+T0+Tср, (4.221) n+1 H где BH(tn+1)=rn(1;)BH(tn).

Для случая на рис.4.4 наличие возможной перегрузки на i+шаге могло быть обнаружено и тем самым с большой вероятностью предотвращено по результатам измерения RTT-задержек или фрактального броуновского движения к моменту времени ti, формированию согласно формуле (4.221) соответствующей оценки прогноза и сравнения ее с тайм-аутом. Кроме того, по величине спрогнозированной RTT-задержки на i+1 шаге можно судить об уровне перегрузки и по сигналу обратной связи соответственно уменьшить (перенастроить) величину окна.

*) Выражение (4.219) впервые было получено в работе [21].

Для рассматриваемого случая дисперсия ошибки прогноза задержки определяется выражением D=M{(T -Tn+1)2}, (4.222) n+ где T =[rn(1;)-1]BH(tn)+T0+Tcp, Tn+1=BH(tn+1)-BH(tn)+ T0+Tcp.

n+ После подстановки выражений T и Tn+1 в соотношение n+(4.222), последующих вычислений, получаем D = M{[rn(1;)BH (tn) - BH (tn+1)]2} = Dn+1 - rn2(1;)Dn, 2H 2H где Dn ~ tn, Dn+1 ~ tn+1, rn (1;) = [1+ Sn,n+1- | Sn,n+1 -1|2H ], Sn,n+1 = tn+1 / tn.

5. СТАТИСТИЧЕСКИЙ СИНТЕЗ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДИНАМИЧЕСКИХ СИСТЕМ 5.1. ВЕДЕНИЕ В ПРОБЛЕМУ СИНТЕЗА В задачах управления информационная система выполняет функции управляющей подсистемы, играющей ключевую роль в оптимизации системы управления. Эта подсистема формирует результатную информацию или в контексте рассматриваемой проблемы осуществляет синтез оптимального управления динамической системы - объекта управления.

В теории оптимального управления в зависимости от цели и средств оптимизации получили наиболее широкое распространение подходы, связанные с определением оптимального линейного оператора [41, 53, 59, 60], осуществляющие параметрический синтез [61, 62, 63, 64], а также аналитические методы решения задач [65, 66, 67, 68, 69]. В первом случае при известных оптимальном операторе системы управления и операторе объекта в рамках корреляционной теории определяется оператор управляющей подсистемы.

Использование этого метода не всегда приводит к физически реализуемым результатам. Кроме того, он довольно часто дает решения, критичные к небольшим вариациям параметров системы [70, 71]. При параметрическом синтезе для заданной структуры управляющей подсистемы предлагаются вычислительные алгоритмы определения параметров оптимального закона управления. К числу этих методов относятся процедуры, основанные на стохастической аппроксимации, случайного поиска, на градиентных и неградиентных способах оптимизации. Аналитические методы, которые, в основном, рассматриваются в пособии, позволяют найти структуру и закон оптимального управления для функционалов качества, имеющих аналитический вид. К этому направлению относятся задачи синтеза управления детерминированных динамических систем при воздействующих неслучайных сигналах, основанные на классическом вариационном исчислении. Однако, оптимизационные задачи, возникающие в теории управления, не всегда могут быть сведены к известным вариационным методам. Причиной этому могут служить ограничения на управление и фазовые координаты систем, использование функционалов качества не аналитического вида, случайный характер протекающих в динамической системе процессов, что приводит к функционалам качества стохастического вида. Для их решения были разработаны специальные методы синтеза, базирующиеся на принципе максимума А.С.Понтрягина и динамическом программировании Р.Беллмана, которые в дальнейшем были обобщены на стохастические задачи. Аналитические решения указанных задач достигаются современными методами теории статистических решений, опирающимися на байесовский критерий условного риска и вариационные методы оптимизации. Для получения конструктивных технически реализуемых решений используется математический аппарат теории условных марковских процессов. Указанное направление успешно развивается на основе описания объектов управления в пространстве состояний и разработки алгоритмов оптимального управления с использованием цифровой вычислительной техники. Все это послужило мощным стимулом к дальнейшему развитию современной теории управления динамических систем и формированию теории статистического синтеза этих систем как самостоятельной дисциплины [67, 72, 73].

Задачи синтеза, использующие вероятностные модели процессов, являются более сложными по сравнению с детерминированными задачами, так как используются вероятностные критерии, что потребовало применять дополнительные операции осреднения результатов измерения относительно плотностей вероятностей. Сложность решения указанной задачи заключается в том, что апостериорная плотность зависит от всех отсчетов вектора измерений, размерность которого увеличивается с возрастанием времени измерения. Существенное упрощение можно получить, если использовать вектор достаточных статистик вполне определенной размерности. Он является вектор-функцией последнего отсчета вектора измерений и некоторой статистики от всех предшествующих измерений. В качестве достаточных статистик рассматриваются условные марковские процессы - оценки фазовых координат динамической системы по результатам измерений. С введением достаточных координат задача стохастического синтеза оптимального управления упрощается и может быть условно разделена на две: задачу вычисления достаточных статистик на основании доступных для измерения координат объекта и задачу определения оптимального управления, как функции оптимизационных критериев и достаточных координат. В связи с этим управляющая подсистема распадается на два блока: блок обработки информации и блок оптимального управления. В общем случае обе задачи решаются совместно. Однако для линейных систем, гауссовских сигналов, аддитивной помехи и квадратичного функционала качества справедлива теорема разделения [74].

Согласно этой теореме задачу статистического синтеза можно свести к двум последовательно решаемым в аналитическом виде задачам:

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

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

Наиболее наглядно это может быть продемонстрировано на характере эволюции во времени компонент матрицы апостериорных дисперсий ошибок управления системы D = lim M{(xt - xtпр )(xt - xtпр )T | ytt } t при lim M{(xt - xtпр )} = 0.

t где xtпр - требуемый программный вектор фазовых координат системы.

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

В наиболее общем случае расчет оптимального управления состоит из следующих этапов:

- формирования функционала качества;

- выбора критерия оптимизации;

- установление оптимального закона управления;

- определение структуры оптимально-управляющей подсистемы.

Pages:     | 1 |   ...   | 24 | 25 | 26 | 27 | 28 |   ...   | 32 |    Книги по разным темам