модель

Все идеи, рассматривавшиеся до сих пор, соответствуют модели, показанной в листинге 6.1: клиент сообщает серверу имя файла, а тот в ответ возвращает файл.

В первые годы существования Всемирной паутины все ее содержимое и в самом деле было статическим (просто файлы). Однако в последние годы в Сети появля­ется все больше динамических объектов, то есть таких, которые создаются по тре­бованию, а не хранятся постоянно на диске. Автоматическое создание объектов может происходить как на стороне сервера, так и на стороне клиента. Рассмотрим оба случая по порядку.

Последовательность пакетов, передающихся от источника к приемнику, называ­ется потоком. При этом в сетях, ориентированных на соединение, все пакеты по­тока следуют по одному и тому же маршруту, а в сетях без установления соединения они могут идти разными путями. Каждому потоку требуются определенные усло­вия, которые можно охарактеризовать следующими четырьмя основными пара­метрами: надежность, задержка, флуктуация и пропускная способность. Все вме­сте они формируют то, что называется качеством обслуживания (QoS — Quality of Service), необходимым потоку. Некоторые общие приложения особенно строго подходят к вопросу качества обслуживания, как показано в табл. 5.3.

Первые четыре приложения предъявляют высокие требования к надежности. Некорректная доставка битов должна быть исключена. Обычно это достигается подсчетом контрольной суммы для каждого пакета и ее проверкой у получателя.

Если пакет во время передачи был испорчен, подтверждение о его доставке не высылается, и источник вынужден передавать его повторно. Такая стратегия обеспечивает высокую надежность. Четыре последних (аудио/видео) приложе­ния весьма толерантны к ошибкам, поэтому здесь нет никаких вычислений и про­верок контрольных сумм.

Приложения, занимающиеся передачей файлов, включая электронную почту и видео, не чувствительны к задержкам. Даже если все пакеты будут доставляться с задержкой в несколько секунд, ничего страшного не произойдет. Однако ин­терактивные приложения — например, обеспечивающие веб-доступ или удален­ный доступ, — к задержкам более критичны. Что касается приложений, работаю­щих в реальном масштабе времени, их требования к задержкам очень строги. Если при телефонном разговоре все слова собеседников будут приходить с задержкой ровно 2,000 с, пользователи сочтут такую связь неприемлемой. С другой сторо­ны, проигрывание видео- или аудиофайлов, хранящихся на сервере, допускает наличие некоторой задержки.

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

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

В сетях ATM принята следующая классификация потоков по требованиям к качеству обслуживания:

1. 
   Постоянная битовая скорость (например, телефония);
2. Переменная битовая скорость в реальном времени (например, сжатые видео­данные при проведении видеоконференций);
3. Переменная битовая скорость не в реальном времени (например, просмотр фильмов через Интернет);
   
4. Доступная битовая скорость (например, передача файлов).

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

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

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

Когда два или более маршрутизаторов объединены в локальную сеть, ситуа­ция несколько усложняется. На рис. 5.9, а изображена ЛВС, к которой напря­мую подключены три маршрутизатора — А, С и F. Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными мар­шрутизаторами.

Один из способов моделирования локальной сети состоит в том, что ЛВС рас­сматривается в виде узла графа, как и маршрутизаторы. Это показано на рис. 5.9, б. На рисунке сеть изображена в виде искусственного узла N, с которым соединены маршрутизаторы А, С и F. Возможность передачи пакетов от Л к С по локальной сети отражается здесь наличием пути ANC.

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

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

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

Предполагается, что у всех хостов есть постоянное домашнее местоположе­ние, которое никогда не меняется. Кроме того, у хостов есть постоянный домаш­ний адрес, которым можно воспользоваться для определения домашнего место­положения, аналогично тому, как телефонный номер 1-212-5551212 обозначает США (страна с кодом 1) и Манхэттен (212). Целью маршрутизации в системах с мобильными хостами является обеспечение возможности передачи пакетов мо­бильным пользователям с помощью их домашних адресов. При этом пакеты долж­ны эффективно достигать пользователей, независимо от их расположения. Са­мое сложное здесь, конечно, — найти пользователя.

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

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

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

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

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

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

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

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

Когда пакет посылается мобильному пользователю, он направляется в его до­машнюю локальную сеть на домашний адрес пользователя. На рис. 5,17 это дей­ствие показано как этап 1. Здесь отправитель из северо-западного города Сиэтла хочет отправить пакет хосту, который обычно находится по другую сторону США, в Нью-Йорке. Пакеты, посланные в домашнюю локальную сеть мобильного хос­та (Нью-Йорк), перехватываются внутренним агентом, который узнает новое (временное) расположение мобильной станции (например, Лос-Анджелес) и ад­рес внешнего агента локальной сети, в которой она в данный момент находится.

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

Затем внутренний агент сообщает отправителю, что в дальнейшем следует не посылать пакеты мобильному хосту на домашний адрес, а вкладывать их в поле данных пакетов, явно адресованных внешнему агенту (этап 3 на рис. 5.17). По­следующие пакеты теперь могут направляться напрямую пользователю через внеш­него агента (этап 4), полностью минуя домашний адрес мобильного пользователя.

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

В-четвертых, схемы различаются способами переадресации пакетов. Один из способов заключается в изменении поля адреса получателя в пакете и передаче измененного пакета. Есть системы, в которых весь пакет, включая домашний ад­рес, может быть помещен внутрь другого пакета, посылаемого по временному ад­ресу. В любом случае, когда хост или маршрутизатор получает сообщение вида «Начиная с этого момента, пожалуйста, пересылайте мне всю почту, адресуемую Стефани», у него могут возникнуть вопросы — например, с кем он разговаривал, соглашаться или нет на данное предложение. Несколько протоколов мобильных хостов обсуждаются и сравниваются в (Нас and Guo, 2000; Perkins, 1998а; Snoe- ren and Balakrishnah, 2000; Solomon, 1998; Wang and Chen, 2001).

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

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

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

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

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

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

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

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

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