Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 119
Текст из файла (страница 119)
Сетевой уровень проблемы у его предшественника, поскольку он не знает, кто является его последователем. Решение данной проблемы состоит в том, что узлы запоминают не только своего прямого последователя, но и еше з последователей. Получается, что без тяжких последствий для окружающих из сети могут выпасть з — 1 последовательных узлов, и круг при этом не разорвется. Метод хорд используется для создания распределенных файловых систем (?)аЪек и др., 2001Ъ) и других приложений; научные изыскания в этой области идут и сейчас. Одна из разноранговых систем, Разггу, и ее приложения описаны в (Котузгоп апд ВгазсЪе1, 2001а; Котузгоп апт( 1ЭгизсЪс1, 2001Ъ).
Еще одна система, Ргеепес, обсуждается в (С1агке и др., 2002). Наконец, четвертая система этого типа описана в (Кагпазашу и др., 2001). Алгоритмы борьбы с перегрузкой Когда количество пакетов, передаваемых одновременно по подсети (или ее части), превышает некий пороговый уровень, производительность сети начинает снижаться. Такая ситуация называется перегрузкой. График на рис. 5.23 изображает симптомы этого явления.
Когда число пакетов, посылаемых хостами в сеть, не превышает ее пропускной способности, все они доставляются адресатам (кроме небольшого процента поврежденных ошибками передачи), При этом количество доставленных пакетов пропорционально количеству посланных. Однако по мере роста трафика маршрутизаторы перестают успевать обрабатывать все пакеты и начинают их терять. При дальнейшем увеличении числа отправляемых пакетов ситуация продолжает ухудшаться. Когда число пакетов достигает максимального уровня, производительность сети начинает снижаться.
При очень высоком уровне графика производительность сети падает до совсем низкого уровня и практически никакие пакеты не доставляются. Посланные пакеты рис. В.23. При слишком высоком уровне трафика начинается перегрузка, и производительность сети резко снижается Алгоритмы борьбы о перегрузкой 446 Перегрузка может быть вызвана несколькими факторами. Если вдруг потоки пакетов начинают прибывать на маршрутизатор сразу по трем или четырем входным линиям и всем им нужна одна и та же выходная линия, то образуется очередь„Когда у маршрутизатора закончится свободная память для буферизации всех прибывающих пакетов, их негде будет сохранять и они начнут теряться. Увеличение объема памяти маршрутизаторов может в какой-то степени помочь, но Нэгл (Над1е) в 1987 году показал, что даже если у маршрутизаторов будет бесконечное количество памяти, ситуация с перегрузкой не улучшится, а, наоборот, ухудшится, так как к тому времени, когда пакеты доберутся до начала очереди, они уже запоздают настолько, что источником будут высланы их дубликаты, Все эти пакеты будут посланы следуюшему маршрутизатору, еше более увеличивая нагрузку на всем протяжении маршрута к получателю, Медленные процессоры также могут служить причиной заторов.
Если центральные процессоры маршрутизаторов слишком медленно выполняют свои задачи, связанные с учетом, управлением очередями, обновлением таблиц и т. д., то очереди будут появляться даже при достаточно высокой пропускной способности линий. Аналогично, линии с низкой пропускной способностью также могут вызывать заторы в сети. Если заменить линии более совершенными, но оставить старые процессоры, или наоборот, такие действия обычно немного помогают, но часто просто приводят к сдвигу узкого места, вызванного несоответствием производительности разных частей системы.
Проблема узкого места сохраняется до тех пор, пока компоненты системы не будут должным образом сбалансированы. Необходимо пояснить, в чем состоит разница между борьбой с перегрузкой и управлением потоком. Предотвращение перегрузки гарантирует, что подсеть срравится с предлагаемым ей трафиком. Это глобальный вопрос, вкл|очаюший поведение всех хостов и маршрутизаторов, процессов хранения и пересылки на маршрутизаторах, а также множество других факторов, снижа1оших пропускную способность подсети.
Управление потоком, напротив, относится к графику между двумя конкретными станциями — отправителем и получателем. Задача управления потоком срстоит в согласовании скорости передачи отправителя со скоростью, с которой получатель способен принимать поток пакетов. Управление потоком обычно реализуется при помощи обратной связи между получателем и отправителем. Чтобы разница между этими двумя проблемами стала яснее, представьте себе оптоволоконную сеть с пропускной способностью 1000 Гбит/с, по которой суперкомпьютер пытается передать персональному компьютеру файл со скоростью 1 Гбит/с. Хотя перегрузки сети в данной ситуации не наблюдается, алгоРитм управления потоком довольно часто заставляет суперкомпьютер приостанавливать передачу, чтобы персональный компьютер мог успевать принимать файл.
А вот другой пример. Рассмотрим сеть с промежуточным хранением, состояШую из 1000 болыпих компьютеров, соединенных линиями с пропускной способностью 1 Мбит/с. Одна половина компьютеров пытается передавать файлы другой половине со скоростью 100 Кбит/с. Здесь проблема заключается уже не в том, что медленные получатели не успевают принимать данные, посылаемые им 446 Глава 5. Сетевой уровень быстрыми отправителями, а просто в неспособности сети пропустить весь предлагаемый трафик. Причина, по которой управление потоком и борьбу с перегрузкой часто путают, заключается в том, что алгоритмы борьбы с перегрузкой также используют обратную связь в виде специальных сообщений, посылаемых различным отправителям, с просьбой передавать данные помедленнее, когда в сети появляются заторы.
Таким образом, хост может получить просьбу замедлить передачу в двух случаях: когда с передаваемым потоком не справляется получатель или когда с ним не справляется вся сеть. В дальнейшем мы еше будем рассматривать этот вопрос. Мы начнем изучение алгоритмов борьбы с перегрузкой с рассмотрения обшей модели. Затем мы познакомимся с общим подходом к предотвращению перегрузки, а также с различными динамическими алгоритмами борьбы с перегрузкой, которую не удалось предотвратить. Общие принципы борьбы с перегрузкой Многие проблемы, возникающие в сложных системах, таких как компьютерные сети, следует рассматривать с точки зрения теории управления.
При таком подходе все решения делятся на две группы,' без обратной связи и с обратной связью, Решения без обратной связи заключаются в попытках решить проблему с помощью улучшения дизайна системы, пытаясь, таким образом, в первую очередь предотвратить возникновение самой ситуации перегрузки. Никаких корректируюших действий во время работы системы не предпринимается. К методам управления без обратной связи относятся решения о том, когда разрешать новый трафик, когда отвергать пакеты и какие именно, а также составление расписаний для различных участков сети. Общее в этих решениях то, что они не учитывают текущего состояния сети.
Решения с обратной связью, напротив, основываются на учете текущего состояния системы. Этот подход состоит из трех следующих частей: 1. Наблюдения за системой с целью определить, где и когда произойдет перегрузка. 2. Передачи информации о перегрузке в те места, где могут быть предприняты соответствующие действия. 3.
Принятия необходимых мер при работе системы для устранения перегрузки При наблюдении за состоянием подсети с целью обнаружения перегрузки могут измеряться различные параметры, Среди них следует выделить следующие: процент пакетов, отвергаемых из-за отсутствия свободного места в буфере; средняя длина очереди; процент пакетов, переданных повторно по причине истекшего времени ожндания подтверждения; среднее время задержки пакетов и среднеквадратичное отклонение задержки пакетов. Во всех случаях увеличивающиеся значения параметров являются сигналами о растушей перегрузке. Второй этап борьбы с перегрузкой состоит в передаче информации о перегрузке от места ее обнаружения туда, где могут быть приняты какие-то меры по Алгоритмы борьбы с перегрузкой 447 ее устранению.
Очевидное решение заключается в том, чтобы маршрутизатор, обнаруживший перегрузку, пересылал источнику или источникам трафика пакет с извещением о наличии проблемы. Такие пакеты, конечно, окажут дополнительную нагрузку на сеть как раз в тот момент, когда нагрузку необходимо снизить. Существуют, однако, и другие решения. Например, можно зарезервировать в каждом пакете бит илн поле, которые будут заполняться маршрутизаторами при достижении перегрузкой порогового уровня. Таким образом, соседи этого маршрутизатора будут предупреждены о том, что на данном участке сети наблюдается перегрузка. Еще один метод состоит в том, что хосты или маршрутизаторы периодически посылают пробные пакеты, явно спрашивая друг друга о перегрузке. Собранная ~аким образом информация может затем использоваться для выбора маршрутов в обход участков сети, в которых возникла проблема с перегрузкой.
Так, некотоРые радиостанции обзавелись вертолетами, летающими над городами и сообщающими слушателям о заторах на дорогах в надежде, что слушающие их водители выберут маршруты для своих пакетов (то есть машин) в обход пробок. Все системы с обратной связью предполагают, что получившие информацию о перегрузке в сети хосты и маршрутизаторы предпримут какие-нибудь действия для устранения перегрузки. Чтобы данная схема работала, необходимо тщательно настроить временные параметры.
Если каждый рзз, когда два пакета приходят одновременно, какой-нибудь нервный маршрутизатор будет кричать ~СтопЬ, в'простояв без работы 20 мкс, он же будет давать команду «ДавайЬ, система будет находиться в состоянии постоянных незатухающих колебаний. С другой стороны, если маршрутизатор будет спокоен, как слон, и для большей надежности бтвнет ждать 30 минут, прежде чем что-либо сообщить, то механизм борьбы с перегрузкой будет реагировать слишком медленно, чтобы приносить вообще какую-либо пользу. Для правильной работы необходимо некоторое усреднение, однако правильный выбор значения постоянной времени является нетривиальной задачей.
Известны различные алгоритмы борьбы с перегрузкой. Янг (Уапй) и реяли (Веберу) (1995) даже разработали специальный метод классификации этих алгоритмов. Они начали с того, что разделили все методы на алгоритмы с обратной связью и без нее, как уже описывалось ранее. Затем они разделили алгоритмы без обратной связи на работающие у отправителя н у получателя. Алгоритмы с обратной связью также были разделены на две подкатегории: с явной и неявной обратной связью. В алгоритмах с явной обратной связью от точки возникновения перегрузки в обратном направлении посылаются пакеты, предупреждающие о затоРе. В алгоритмах с неявной обратной связью источник приходит к выводу о наличии перегрузки, основываясь на локальных наблюдениях, — например, по значению интервала времени, требующегося для получения подтверждения. Наличие перегрузки означает, что нагрузка временно превысила возможности Ресурсов данной части системы. Есть два решения данной проблемы: увеличить Ресурсы системы или снизить нагрузку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
