Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Чтобы обеспечить быструю конвергенцию, маршрутам присваиваются порядковые номера, контролируемые получателем. Порядковый номер получателя — своего рода логические часы. Получатель увеличивает этот номер каждый раз при отправке нового пакетаROUTE REPLY . Чтобы запросить новый маршрут, отправитель добавляет в пакетROUTE REQUEST порядковый номер получателя для последнего использовавшегося маршрута: это может быть или порядковый номер только что удаленного маршрута, или 0, то есть исходное значение. Запрос будет передаваться широковещательным способом до тех пор, пока не будет найден маршрут с большим порядковым номером. Промежуточные узлы сохраняют маршруты, имеющие больший порядковый номер или меньшее число промежуточных узлов для текущего порядкового номера.

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

Пока мы рассмотрели только один маршрут: от 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 году показал, что даже если у маршрутизаторов будет бесконечное количество памяти, ситуация с перегрузкой не улучшится, а, наоборот, ухудшится. Причина в том, что к тому времени, когда пакеты доберутся до начала очереди, они уже запоздают настолько, что источником будут высланы их дубликаты. В результате ситуация не улучшится, а ухудшится: в сети возникнет затор.

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