где
— время прибытия,
— время окончания отправки, а
— длина
пакета. Нижняя очередь (рис. 5.28,
а) имеет вес 2, поэтому ее пакеты передаются быстрее. Это хорошо видно, если посмотреть на значения времени окончания отправки (см. рис. 5.28,
б). Еще один фактор, который необходимо учитывать, — это сложность реализации. Метод взвешенного справедливого обслуживания помещает пакеты в очередь, сортируя их по времени окончания отправки. Для
N потоков это требует по меньшей мере
операций для каждого пакета, что является трудновыпол
нимым при большом количестве потоков на высокоскоростных маршрутизаторах. Существует упрощенная схема DRR (deficit round robin), работающая гораздо эффективнее — всего за 0(1) операций для каждого пакета (Shreedhar и Varghese, 1995). Она широко применяется для алгоритма взвешенного справедливого обслуживания.
Существуют другие алгоритмы диспетчеризации. К ним относится, например, приоритетная диспетчеризация, при которой каждый пакет обладает приоритетом. Высокоприоритетные пакеты отправляются раньше, чем низкоприоритетные; последние помещаются в буфер. Пакеты с одинаковым приоритетом отправляются по принципу FIFO. Существенным недостатком этого алгоритма является то, что высокоприоритетные пакеты препятствует отправке низкоприоритетных, которые в результате могут ждать своей очереди бесконечно долго. С этой точки зрения взвешенное справедливое обслуживание — более удачный вариант. Если присвоить высокоприоритетной очереди большой вес (скажем, 3), высокоприоритетные пакеты будут в основном проходить по быстрой линии (так как пакетов с высоким приоритетом сравнительно немного), но одновременно с этим часть низкоприоритетных пакетов тоже будет передаваться.
Фактически бинарная приоритетная система представляет собой две очереди, одна из которых имеет бесконечный вес.
Наконец, существует алгоритм диспетчеризации, при котором у каждого пакета есть временной штамп, определяющий порядок отправки. В реализации, предложенной Clark и др. (1992), временной штамп регистрирует информацию о том, насколько пакет отстает от графика или опережает его, проходя через маршрутизаторы сети. Пакеты, ждущие отправки в очереди, обычно отстают от графика; пакеты, передаваемые в первую очередь, обычно опережают график. Передача пакетов в порядке временных штампов — эффективный способ ускорить отправку медленных пакетов и замедлить отправку быстрых. При такой диспетчеризации все пакеты доставляются с приблизительно равной задержкой.
5.4.4. Управление доступом
Теперь, когда мы познакомились с основными составляющими качества обслуживания (QoS), самое время собрать все это воедино. Гарантии качества обслуживания выполняются через управление доступом. До этого мы рассматривали управление доступом как средство борьбы с перегрузкой, что является гарантией производительности, пусть даже не очень эффективной. Здесь мы предъявляем к гарантиям более серьезные требования, но модель остается той же. Пользователь передает в сеть поток, предъявляя определенные требования к качеству обслуживания. Сеть принимает или отвергает этот поток в зависимости от своих возможностей и обязательств перед другими клиентами. Если сеть принимает поток, она должна заранее зарезервировать ресурсы, чтобы при передаче трафика по этому потоку клиент получил необходимое качество обслуживания.
Резервирование может производиться на всех маршрутизаторах, расположенных в узлах пути, по которому следуют пакеты. Если на каком-то из них ресурсы не зарезервированы, там может возникнуть затор, и гарантии качества обслуживания рискуют оказаться невыполненными. Многие алгоритмы маршрутизации выбирают наилучший путь от отправителя до получателя и направляют весь трафик по этому пути. Однако это может привести к тому, что часть потоков будут отвергнуты из-за недостатка ресурсов на узлах наилучшего пути. Тогда, чтобы выполнить свои обязательства перед клиентом, сеть выберет другой путь для отправки крупного потока. Это называется QoS-маршрутизацией (QoS routing). Описание этих методов можно найти в работе Chen и Nahrstedt (1998). Если заранее распределять трафик для одного и того же адреса по нескольким путям, найти дополнительные ресурсы будет гораздо проще. Маршрутизаторы могут выбирать пути с одинаковой стоимостью и использовать маршрутизацию, пропорциональную или эквивалентную емкостям исходящих связей. Однако существуют и более сложные алгоритмы (Nelakuditi и Zhang, 2002).
Для выбранного пути процесс принятия решения об обработке или игнорировании потока сложнее, нежели простое сравнение запрашиваемых потоком ресурсов (пропускной способности, буферной памяти, времени центрального процессора) с имеющимися. Во-первых, хотя многие приложения и знают свои требования по пропускной способности, они понятия не имеют, какой объем буферной памяти и сколько тактов работы процессора им требуется. Следовательно, нужен, по крайней мере, иной способ описания потоков и определения ресурсов, выделяемых маршрутизатором. Вскоре мы вернемся к этому вопросу.
Далее, приложения весьма отличаются по толерантности в отношении пропущенного предельного срока обработки. Поэтому приложение должно выбрать один из типов гарантий, предлагаемых сетью: от строгих до предельно лояльных. При прочих равных условиях строгие гарантии пользовались бы самой большой популярностью. Но проблема в том, что они стоят достаточно дорого, так как ограничивают поведение сети в наихудшем случае. Для приложений обычно достаточно тех же гарантий, что и для большинства пакетов; кроме того, эти гарантии позволяют добавить дополнительный поток, используя фиксированные мощности.
Наконец, некоторые приложения могут поторговаться за параметры пакетов, а некоторые не могут. Скажем, проигрыватель видео, предоставляющий обычно 30 кадров/с, может согласиться работать на 25 кадрах/с, если для 30 не хватает пропускной способности. Аналогично можно настраивать количество пикселов на кадр, полосу пропускания для аудиоданных и другие свойства потоков различных приложений.
Поскольку в спор по поводу того, что делать с потоком, вовлечено много сторон (отправитель, приемник и все маршрутизаторы на пути между ними), поток необходимо описывать крайне аккуратно с помощью параметров, о которых можно дискутировать. Набор таких параметров называется спецификацией потока (flow specification). В типичном случае отправитель (например, сервер видеоданных) создает спецификацию потока, указывая параметры, которые он хотел бы использовать для аргументации. По мере того как эта спецификация распространяется по пути следования потока, содержащаяся в нем информация анализируется всеми маршрутизаторами, которые модифицируют параметры так, как считают нужным. Эти модификации могут быть направлены только на уменьшение потока (например, указываемая в спецификации скорость передачи данных может быть понижена, но не повышена). Когда спецификация доходит до приемника, становятся понятны окончательные параметры.
В качестве содержимого спецификации потока рассмотрим пример (табл. 5.3), базирующийся на RFC 2210 и RFC 2211 для интегрального обслуживания — технологии QoS, о которой мы поговорим в следующем разделе. В спецификации содержится пять параметров. Первые два, скорость маркерного ведра и размер маркерного ведра, позволяют вычислить максимальную скорость, которую отправитель может поддерживать в течение длительного времени, усредненную по большому временному отрезку, а также максимальный объем пачки, передаваемой за короткий промежуток времени.
