график

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

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

Для таких приложений как аудио- и видеопередача, не так уж важно, 20 или 30 мс занимает доставка пакетов, до тех пор, пока время доставки постоянно. Колеба­ние (то есть, среднеквадратичное отклонение) времени доставки пакетов называет­ся флуктуацией. Если одни пакеты будут доставляться за 20 мс, а другие — за 30 мс,
изображение или звук начнет дрожать. В этом случае говорят о наличии сильных флуктуаций. На рис. 5.26 изображены примеры флуктуаций. Внутри системы, с другой стороны, может существовать договоренность о том, что 99 % пакетов должны быть доставлены с задержкой в диапазоне от 24,5 до 25,5 мс, и качество при этом будет вполне приемлемым.

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

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

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

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

Борьба с перегрузками представляет собой область активных исследований. Текущее положение дел отражено в книге (Gevros и др., 2001).

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

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

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

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

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

А вот другой пример. Рассмотрим сеть с промежуточным хранением, состоя­щую из 1000 больших компьютеров, соединенных линиями с пропускной спо­собностью 1 Мбит/с. Одна половина компьютеров пытается передавать файлы Другой половине со скоростью 100 Кбит/с. Здесь проблема заключается уже не в ТОМ, что медленные получатели не успевают принимать данные, посылаемые им быстрыми отправителями, а просто в неспособности сети пропустить весь пред­лагаемый трафик.

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

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