Размещено на http://www.allbest.ru/

О возможностях применения традиционных механизмов обеспечения качества обслуживания в современных распределенных информационных системах

система распределенный информационный обслуживание

ФРОЛОВ А.И.

The prerequisites for Quality of Service (QoS) perfection in the modern distributed information systems are concerned. The review of the basic queuing algorithms using in the networking is given. Disadvantages of them are discovered and the requirements for QoS model in modern distributed information systems are formulated.

ВВЕДЕНИЕ

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

Отсюда следует, что одной из необходимых составляющих современной распределенной информационной системы является подсистема контроля и управления производительностью, которая должна реализовывать функции обеспечения качества обслуживания (QoS - Quality of Service).

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

Активные исследования в области обеспечения качества обслуживания начались с середины 80-х годов. Потребность в них проявилась с началом бурного роста сети Internet и приобретением ею коммерческих черт. Это обусловило привязку исследований в области QoS только к задачам передачи данных через сеть. Поэтому рассмотрим основные дисциплины и алгоритмы управления очередями, используемые в сетях.

ОСНОВНЫЕ ДИСЦИПЛИНЫ ОБСЛУЖИВАНИЯ ОЧЕРЕДЕЙ С ПОДДЕРЖКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ

Приоритетное обслуживание. Схема приоритетного обслуживания (PQ - Priority Queuing) реализует правило «обслуживание менее приоритетных очередей начинается только после полного освобождения более приоритетных». Поэтому ее часто называют схемой обработки очередей с абсолютным приоритетом.

Приоритетное обслуживание пакетов востребовано в сетях, где передача трафика, необходимого для решения критически важных задач, должна быть осуществлена даже при условии полного доминирования высокоприоритетного трафика в моменты перегрузки сети [1, 2].

Максиминная схема равномерного распределения ресурсов. Данная схема является обобщенной и рассматривается как базис для приведенных ниже. Предполагается, что разные пользователи предъявляют различные требования к ресурсам и существует возможность их классификации в порядке возрастания требований. Ниже дано определение максиминной схемы равномерного распределения ресурсов (max-min fair-share allocation scheme) [3].

1. Ресурсы распределяются в порядке возрастания требований.

2. Пользователь не может получить превышающий его потребности объем ресурсов.

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

4. Объем ресурсов, предоставляемых пользователю i, рассчитывается по следующей формуле:

, (1)

где Vsum - весь объем ресурсов;

Vdistr - объем распределенных на предыдущих проходах ресурсов;

N - количество пользователей, которым все еще требуются ресурсы.

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

Модификация данной схемы, где каждому пользователю назначается определенный вес, получила название взвешенной максиминной схемы равномерного распределения ресурсов (weighted max-min fair-share allocation scheme). В соответствии этой схемой каждому пользователю выделяется равномерная доля ресурсов, пропорциональная его весу.

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

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

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

Несмотря на то, что GPS является идеальным воплощением максиминной схемы равномерного распределения ресурсов, подобная модель не может быть реализована на практике, так как пакеты имеют конечный и, в общем случае, различный размер. Однако ее теоретическое значение заключается в том, что считается, что к алгоритму обслуживания очередей, пригодному для практического использования, выдвигаются два требования [1, 2]: он должен быть как можно более близкой аппроксимацией схемы GPS и должен быть реализуемым на практике.

Дисциплина управления очередями на основе кривых обслуживания. Впервые кривые обслуживания были описаны и применены Рене Крузом (Rene L. Cruz) в работах [5] и [6].

Говорится, что потоку i гарантирована кривая обслуживания , где - неубывающая функция, если для некоторого момента времени t2, когда поток i имеет непустую очередь, найдется момент времени t1 < t2, в который начался период простоя i-го потока (необязательно включающий t2), такой что выполняется следующее условие:

, (2)

где - количество ресурса, выделенное потоку i в течение интервала времени .

Если кривая обслуживания (Service Curves) в какой либо дисциплине является невогнутой, то дисциплина работает по принципу «первым выбирается элемент, имеющий ранний предельный срок» (Earliest Deadline first), - SCED [7].

Предельный срок вычисляется для каждого пакета на основании кривой предельного срока Di. Пакеты отправляются в порядке возрастания их предельных сроков. Кривая предельного срока вычисляется таким образом, чтобы в идеальной потоковой системе кривая обслуживания потока i гарантировалась, если в любой момент времени t, когда очередь потока i активна, по крайней мере Di(t) ресурса было предоставлено

потоку i. Исходя из (2), это дает:

, (3)

где Bi(t) - множество моментов времени, меньших или равных t, в которых поток i начинал простаивать;

- общее количество ресурса, полученное потоком i ко времени t1.

Для вычисления Di используется следующая итеративная процедура. Когда у потока i появляется непустая очередь в первый раз, Di присваивается значение . Затем, когда поток i начинает простаивать снова в момент времени (начало k-го периода простоя потока i) после периода незанятости потока, Di обновляется в соответствии со следующим выражением:

, . (4)

Гарантии, определяемые на основе кривых обслуживания являются достаточно общими. Например, приведенный ниже алгоритм равномерного обслуживания может быть представлен линейной кривой обслуживания с точкой в начале координат. На самом деле потоковая схема GPS может поддерживать кривые обслуживания более общего вида. Однако на практике существует ряд ограничений, связанных со сложностью реализации [8].

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

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

ОСНОВНЫЕ АЛГОРИТМЫ УПРАВЛЕНИЯ ОЧЕРЕДЯМИ С ПОДДЕРЖКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ

Взвешенный алгоритм равномерного обслуживания очередей. Взвешенный алгоритм равномерного обслуживания очередей (Weighted Fair Queuing - WFQ) представляет собой аппроксимацию схемы GPS, поскольку он моделирует поведение планировщика GPS без нереализуемого на практике предположения о бесконечно малом объеме обрабатываемых данных [9, 10]. Основой алгоритма WFQ является алгоритм FQ (Fair Queuing), в соответствии с которым все потоки трафика рассматриваются как равные между собой, т.е. как потоки с одинаковым весом.

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

Для представления механизма моделирования схемы GPS, вводится переменная, называемая «счетчиком циклов» (round number). Значение счетчика циклов R(t) определяет количество выполненных циклов побайтового планировщика кругового обслуживания в заданный момент времени t. Обозначим и как значения R(t) в моменты поступления i-го пакета, принадлежащего потоку , в систему и завершения его обслуживания соответственно:

, (5)

, (6)

где - размер i-го пакета, принадлежащего потоку , в битах;

- время поступления в систему i-го пакета, принадлежащего потоку .

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

Если каждому потоку назначается вес , определяющий его приоритет, то поток будет обслуживаться пропорционально этому весу, и формула (6) приобретает вид:

, (7)

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

Такое расширение алгоритма равномерного обслуживания очередей получило название взвешенного алгоритма равномерного обслуживания очередей (WFQ).

Управление очередями, основанное на классах. Этот подход, позднее названный Classed-based queuing (CBQ), был предложен Ван Якобсоном в 1991 году [11]. Основными его отличиями являются возможность распределения пакетов не только по потокам, но и по классам, иерархическая структура классов, предоставление дополнительных гарантий различным видам трафика по величине задержки.

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

Справедливое в наихудшем случае взвешенное равномерное обслуживание очередей. Пакетная аппроксимация взвешенной обобщенной схемы распределения процессорного времени на основе алгоритма WFQ обладает рядом недостатков. Одним из них является значительное отличие уровня обслуживания от идеального распределения во взвешенной схеме GPS при определенной конфигурации входных потоков [13]. Второй недостаток пакетной аппроксимации GPS - периодическое колебание величины задержки в случае изменения интенсивности потока.

С целью минимизации различия между пакетной системой и идеальной GPS-системой был предложен новый алгоритм управления очередями с поддержкой качества обслуживания, названный алгоритмом справедливого в наихудшем случае взвешенного равномерного обслуживания очередей (Worst-case fair weighted fair queuing - WF2Q).

Также, как и в алгоритме WFQ, осуществляется выбор пакета с минимальным (виртуальным) временем завершения обслуживания . Отличие заключается в том, что выбор производится не среди всех пакетов, находящихся в головах активных очередей, а среди так называемых «пригодных» (eligible) на текущий момент времени пакетов. Пригодными на момент времени t называются пакеты, которые уже начали обслуживание в идеальной схеме GPS, т.е. виртуальное время начала обслуживания меньше или равно текущему виртуальному времени.

Пакетный алгоритм иерархического равномерного обслуживания очередей. Алгоритм WF2Q, несмотря на значительные преимущества, является неэффективным по времени (также как и WFQ имеет сложность O(N) по количеству активных классов) и поддерживает лишь одноуровневое распределение ресурсов. С целью использования в качестве блока многоуровневой модели качества обслуживания этот алгоритм был модифицирован и получил название WF2Q+. Сохраняя все свойства алгоритма WF2Q, он имеет сложность по времени O(logN) [13]. Алгоритм, реализующий многоуровневую модель с приведенной выше сложностью получил название пакетного алгоритма иерархического равномерного обслуживания очередей (Hierarchical packet fair queuing -H-PFQ).

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

– одновременно будет обеспечено качество обслуживания для всех классов иерархии в соответствии с их кривыми обслуживания;

– неиспользуемая полоса пропускания будет распределяться между активными классами равномерно (справедливо).

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

С целью аппроксимации модели был разработан иерархический алгоритм на базе кривых обслуживания (Hierarchical Fair Service Curve - HFSC), который направлен на достижение трех целей [8]:

– гарантировать кривые обслуживания для всех листовых классов;

– минимизировать кратковременные несоответствия между требуемым внутренним классом количеством сервиса и количеством, определяемым HFSC-моделью;

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

Для достижения поставленных целей выделяются два правила: правило реального времени (real-time criterion), обеспечивающее кривые обслуживания для листовых классов, и правило распределения (link-sharing criterion), используемое для удовлетворения кривых обслуживания внутренних классов иерархии и распределения неиспользованного ресурса. Правило реального времени вступает в силу только в случае потенциальной опасности нарушения гарантий кривой обслуживания в листовом классе. В иных случаях применяется привило распределения. С целью определения правила, которое должно вступить в силу, для каждого листового класса вводится дополнительная кривая «пригодности» (eligible curve). В этом случае на обслуживание выбирается пакет активного листового класса, имеющий наименьше значение предельного срока и текущее значение кривой пригодности меньшее или равное текущему виртуальному времени. Если такой класс существует, то обслуживание осуществляется в соответствии с правилом реального времени, если не существует, - в соответствии с правилом распределения.

Алгоритм имеет небольшую сложность по времени - O(logN), где N - количество активных классов.

Алгоритм на основе виртуальных часов. Алгоритм на основе виртуальных часов (Virtual clock) является еще одной аппроксимацией схемы GPS. Под виртуальным временем потока понимается взвешенное количество переданной потоком информации [14]. Критерием выбора очередного пакета на обслуживания является минимизация разницы между показаниями виртуальных часов различных потоков (т.е. выбирается поток с минимальным значением виртуального времени).

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

ВЫВОДЫ

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

1. Элементарным объектом управления в существующих подходах является пакет, а не заявка пользователя (приложения) на обслуживание.

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

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

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

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

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

– элементарным объектом управления модели обеспечения качества обслуживания является заявка;

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

– основной характеристикой качества обслуживания конкретной заявки является задержка в очереди при ожидании освобождения обслуживающего устройства;

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

ЛИТЕРАТУРА

1. Вегешна, Ш. Качество обслуживания в сетях IP [Текст] / Ш. Вегешна. - М.: Издательский дом «Вильямс», 2003. - 368 с.

2. Олифер, В.Г. Новые технологии и оборудование IP-сетей [Текст] / В.Г. Олифер, Н.А. Олифер. - СПб.: БХВ-Петербург, 2001. - 512 с.

3. Kesliav, S. An Engineering Approach to Computer Networking [Text] / S. Kesliav. - Massachusetts: AddisonWesley Publishing Company, 1997. - 688 p.

4. Parekh, A. A generalized processor sharing approach to flow control in integrated services networks: The single node case [Text] / A. Parekh, R. Gallager // IEEE/ACM Transaction on Networking, 1993. - №3. - V1. - P. 344-357.

5. Cruz, R. Service burstiness and dynamic burstiness measures: A framework [Text] / R. Cruz // Journal of High Speed Networks, 1992. - №2. - V1. - Р. 105-127.

6. Cruz, R. Quality of service guaranteed in virtual circuit switched network [Text] / R. Cruz // IEEE Journal on Selected Areas in Communications, 1995. - №6. - V13. - Р. 1048-1056.

7. Cruz, R. Scheduling for quality of service guarantees via service curves [Text] / R. Cruz, G. Polyzos // In the Proceedings of the International Conference on Computer Communications and Networks (ICCCN), 1995. - Р. 512-520.

8. Stoica, I. A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services [Text] / I. Stoica, H. Zhang // In Proceedings of the ACM-SIGCOMM97, 1997. - Р. 249-262.

9. Demers, A. Analysis and simulation of a fair queuing algorithm [Text] / A. Demers, S. Keshav, S. Shenker // Internetworking: Research and Experience, 1990. - V1. - Р. 3-26.

10. Demers, A. A classical self-locked WFQ algorithm [Text] / A. Demers, S. Keshav, S. Shenker // SIGCOMM 1989, 1989. - Р. 51-67.

11. Floyd, S. Link-sharing and resource management models for packet networks [Text] / S. Floyd, V. Jacobson // IEEE/ACM Transactions on Networking, 1995. - №4. - V3. - Р. 365-386.

12. Bennett, J.C. WF2Q: Worst-case fair weighted fair queuing [Text] / J.C.R. Bennett, H. Zhang // In Proceedings of IEEE INFOCOM'96, 1996. - Р. 120-128.

13. Bennett, J.C. Hierarchical packet fair queuing algorithms [Text] / J.C.R. Bennett, H. Zhang // In Proceedings of the ACM-SIGCOMM96, 1996. - Р. 143-156.

14. Zhang, L. Virtual clock: A new traffic control algorithm for packet switched networks [Text] / L. Zhang // IEEE/ACM Transactions on Computer Systems, 1990. - №2. - V9. - Р. 10-24.

Размещено на Allbest.ru