Пока мы рассмотрели только один маршрут: от A до I. Для большей экономии ресурсов построение и обслуживание пересекающихся маршрутов производится совместно. К примеру, если B тоже захочет отправлять пакеты в I, он выполнит вычисление маршрута. Но в таком случае запрос сначала достигнет узла D, который уже знает о существовании маршрута, ведущего к I. И тогда узел D может отправить B ответ, содержащий нужный маршрут, тем самым избежав лишних вычислений.

Существует множество других схем маршрутизации в произвольных сетях. Еще один известный алгоритм «по требованию» называется DSR (Dynamic Source Routing — динамическая маршрутизация от источника) ( Johnson и др., 2001). Другая стратегия, основанная на географии, используется в GPSR (Greedy Perimeter Stateless Routing — «жадный» протокол маршрутизации по периметру без учета состояний). Если все узлы знают свое географическое местоположение, доставка пакета получателю может происходить без вычисления маршрута: пакет можно каждый раз отправлять в правильном направлении, возвращаясь назад в случае, если иначе путь приведет в тупик. Выбор протокола зависит в первую очередь от характеристик данной произвольной сети.

5.3. Алгоритмы борьбы с перегрузкой

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

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

Рис. 5.19. При слишком высоком уровне трафика начинается перегрузка, и производительность сети резко снижается

Если сеть устроена не идеально, в ней может произойти затор (congestion collapse), при котором производительность падает с ростом нагрузки на сеть (если нагрузка превышает пропускную способность). Это может произойти, если пакеты настолько задерживаются в сети, что в момент доставки они уже не нужны. Например, на ранних этапах работы сети Интернет время, которое пакет проводил в очереди, ожидая отправки непереданных пакетов (при скорости 56 Кбит/с), зачастую превышало то время, которое пакет мог находиться в сети. В результате его приходилось удалять. Еще один неприятный сценарий — ситуация, когда отправители повторно передают пакеты, которые сильно задерживаются, полагая, что они утеряны. В таком случае пропускная способность сети используется неэффективно, поскольку по сети передаются копии одного и того же пакета. Чтобы наглядно продемонстрировать влияние этих факторов на производительность, мы отобразили на оси у (см. рис. 5.19) полезную нагрузку (goodput), то есть скорость, с которой по сети передаются полезные пакеты.

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

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

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

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

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

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

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

5.3.1. Подходы к борьбе с перегрузкой

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