Литмир - Электронная Библиотека

Пока мы рассмотрели только один маршрут: от 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-е издание - _261.jpg

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

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

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

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

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

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

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

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

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

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

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

139
{"b":"639789","o":1}