таблица

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

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

В очень больших сетях двухуровневой иерархии может оказаться недостаточ­но. Может потребоваться группировать регионы в кластеры, кластеры в зоны, зоны в группы, и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим марш­рутизацию пакета, пересылаемого из университета Беркли (Berkeley), штат Ка­лифорния, в Малинди (Malindi) в Кении. Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы шта­та, он посылает маршрутизатору в Лос-Анджелесе. Маршрутизатор в Лос-Анд­желесе может выбрать маршрут для трафика в пределах США, но все пакеты, на­правляемые за рубеж, переправляет в Нью-Йорк. Нью-йоркский маршрутизатор направит трафик на маршрутизатор страны назначения, ответственный за прием
трафика из-за границы. Он может располагаться, например, в Найроби. Нако­нец, направляясь вниз по дереву иерархии уже в пределах Кении, пакет попадет в Малинди.

На рис. 5.13 приведен количественный пример маршрутизации в двухуровне­вой иерархии с пятью регионами. Полная таблица маршрутизатора 1А, как пока­зано на рис. 5.13, б, состоит из 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.13, в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регион по-прежнему пойдет по линии 1В — 2А, а во все остальные ре­гионы — по линии 1С — ЗВ. При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк. Чем крупнее выбираются регионы, тем больше экономится места в таблице.

К сожалению, этот выигрыш памяти не достается бесплатно. Платой за умень­шение размеров таблицы маршрутов является увеличение длины пути. Напри- Мер, наилучший маршрут от 1А до 5С проходит через регион 2, однако при ис­пользовании иерархической маршрутизации весь трафик в регион 5 направляет­ся через регион 3, поскольку так лучше для большинства адресатов в регионе 5.

димо поддерживать таблицу из 720 строк. Если подсеть разбить на 24 региона по 30 маршрутизаторов в каждом регионе, тогда каждому маршрутизатору потребу­ется 30 локальных записей плюс 23 записи об удаленных регионах, итого 53 за­писи. При выборе трехуровневой иерархии, состоящей из 8 кластеров по 9 ре­гионов из 10 маршрутизаторов, каждому маршрутизатору понадобится 10 строк в таблице для локальных маршрутизаторов, 8 строк для маршрутизации в дру­гие регионы в пределах своего кластера, плюс 7 строк для удаленных кластеров, итого 25 строк. Камоун (Kamoun) и Кляйнрок (Kleinrock) в 1979 году показа­ли, что оптимальное количество уровней иерархии для подсети, состоящей из N маршрутизаторов, равно In N. При этом потребуется е In Дозаписей для каждо­го маршрутизатора. Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым.

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

Сначала мы опишем основной алгоритм распространения. Затем расскажем о некоторых улучшениях. Основная идея алгоритма распространения пакетов со­стояния линии состоит в использовании алгоритма заливки. Чтобы держать этот процесс под контролем, в каждый пакет помещают порядковый номер, увеличи­вающийся на единицу для каждого следующего пакета. Маршрутизаторы запи­сывают все пары (источник, порядковый номер), которые им попадаются. Когда приходит новый пакет состояния линий, маршрутизатор ищет адрес его отпра­вителя и порядковый номер пакета в своем списке. Если это новый пакет, он рас­сылается дальше по всем линиям, кроме той, по которой он пришел. Если же это дубликат, он удаляется. Если порядковый номер прибывшего пакета меньше, чем номер уже полученного пакета от того же отправителя, то такой пакет также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть бо­лее свежие данные.

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

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

В-третьих, может произойти искажение порядкового номера — например, вмес­то номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае паке­ты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие.

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

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

Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рис. 5.11, а, показана на рис. 5.12. Каждый ряд здесь соответству­ет недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и F соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.

Как видно из рис. 5.12, пакет состояния линий от маршрутизатора А пришел напрямую, поэтому он должен быть отправлен маршрутизаторам С и F, а под­тверждение о его получении следует направить маршрутизатору А, что и пока­зывают флаговые биты. Аналогично, пакет от F следует переслать маршрутиза­торам А и С, a F отослать подтверждение.

Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отли­чается. Он был получен дважды, по линиям ЕАВ и EFB, Следовательно, его нуж­но отослать только С, но подтверждения выслать и А, и jF, как указывают биты.

Если в то время, когда оригинал еще находится в буфере, прибывает дуб­ликат пакета, значение битов должно быть изменено. Например, если копия со­стояния маршрутизатора С прибудет от F прежде, чем четвертая строка таблицы будет разослана, шесть флаговых битов примут значение 100011, и это будет оз­начать, что следует подтвердить получение пакета от F, но не пересылать его F.

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

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

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

Однако неисправности оборудования или программного обеспечения могут привести к очень серьезным проблемам при использовании данного алгоритма (а также других алгоритмов). Например, если маршрутизатор заявит о существо­вании линии, которой у него в действительности нет, или наоборот, забудет о су­ществовании имеющейся у него линии, граф подсети окажется неверным. Если маршрутизатор не сможет переслать пакеты или повредит их при пересылке, так­же возникнет проблема. Наконец, если у маршрутизатора закончится свободная память или он ошибется в расчетах маршрутов, также возможны различные не­приятности. При увеличении размера подсети до нескольких десятков или сотен тысяч маршрутизаторов вероятность выхода из строя одного из них перестает быть пренебрежимо малой. Все, что можно здесь сделать, — это попытаться огра­ничить вред, наносимый практически неизбежным выходом из строя оборудова­ния. Эти проблемы и методы их разрешения подробно обсуждаются в (Perlman, 1988).

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

Другим важным протоколом с учетом состояния линий является IS-IS (Intermediate System to Intermediate System — связь между промежуточными сис­темами) — протокол, разработанный для сети DECnet и принятый впоследствии Международной организацией по стандартизации ISO для использования вме­сте с протоколом сетевого уровня CLNP, не требующим соединений. С тех пор он был модифицирован для поддержки также и других протоколов, в частности IP. Протокол IS-IS используется в некоторых магистралях сети Интернет (включая старую магистраль NSFNET) и в некоторых цифровых сотовых системах, напри­мер, в CDPD. В сети Novell NetWare применяется разновидность протокола IS­IS (NLSP) для маршрутизации IPX-пакетов.

В основе работы протокола IS-IS лежит распространение картины топологии маршрутизаторов, по которой рассчитываются кратчайшие пути. Каждый мар­шрутизатор сообщает в информации о состоянии линий доступные ему напря­мую адреса сетевого уровня. Эти адреса могут быть адресами IP, IPX, AppleTalk или другими. Протокол IS-IS может даже осуществлять одновременную поддерж­ку нескольких протоколов сетевого уровня.

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

Процесс принятия решения об обработке или игнорировании потока сложнее, нежели простое сравнение запрашиваемых потоком параметров (пропускной спо­собности, буферной памяти, времени центрального процессора) с имеющимися. Во-первых, хотя многие приложения и знают свои требования к пропускной способности, они понятия не имеют, какой объем буферной памяти и сколько тактов работы процессора им требуется. Следовательно, нужен, по крайней мере, иной способ описания потоков. Далее, приложения весьма различаются по толе­рантности в отношении пропущенного предельного срока обработки. Наконец, некоторые приложения могут поторговаться за параметры пакетов, а некоторые не могут. Скажем, проигрыватель видео, предоставляющий обычно 30 кадров/с, хожет согласиться работать на 25 кадрах/с, если для 30 не хватает пропускной способности. Аналогично, можно настраивать количество пикселов на кадр, по­лосу пропускания для аудиоданных и другие свойства потоков различных при­ложений.

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

В качестве содержимого спецификации потока рассмотрим пример, базирую­щийся на RFC 2210 и RFC 2211 (табл. 5.4). В спецификации содержится пять параметров, первый из которых, Скорость маркерного ведра, хранит число бай­тов, поступающих в «ведро» за секунду. Это максимум, который отправитель мо­жет поддерживать в течение длительного времени, усредненный по большому временному отрезку.Второй параметр — размер маркерного ведра в байтах. Если, к примеру, Ско­рость маркерного ведра составляет 1 Мбит/с, а размер ведра равен 500 Кбайт, то его можно будет наполнять данными в течение 4 с. Все, что будет посылаться по­сле этого, будет теряться.

Третий параметр, Пиковая скорость передачи данных, — это максимальная до­пустимая скорость даже для коротких промежутков времени. Отправитель ни в коем случае не должен превышать это значение.

Наконец, последние два параметра определяют минимальный и максималь­ный размеры пакетов, включая заголовки транспортного и сетевого уровней (на­пример, TCP и IP). Минимальный размер важен, поскольку обработка каждого пакета занимает какое-то, пусть даже очень малое, время. Маршрутизатор, мо­жет быть, готов принимать 10 000 пакетов в секунду по 1 Кбайт каждый, но не готов обрабатывать 100 ООО пакетов по 50 байт в секунду несмотря на то, что во втором случае скорость передачи данных меньше, чем в первом. Максимальный размер пакета не менее важен, но уже по другой причине. Дело в том, что сущест­вуют определенные внутрисетевые ограничения, которые ни в коем случае не должны быть превышены. Например, если путь потока лежит через Ethernet, то максимальный размер пакета будет ограничен 1500 байтами независимо от того, какого размера пакеты могут поддерживать другие части сети.

Интересно, каким образом маршрутизатор преобразует спецификацию пото­ка в набор определенных резервируемых ресурсов? Это отображение является специфическим и не стандартизованным действием. Допустим, маршрутизатор может обрабатывать 100 000 пакетов/с. Если ему предлагается пропустить через себя поток со скоростью 1 Мбайт/с с максимальным размером пакета, состав­ляющим 512 байт, он может легко посчитать, что такой поток дает 2048 паке­тов/с, значит, под него необходимо отвести 2 % времени работы процессора, а лучше немного больше, чтобы избежать больших задержек обслуживания. Ес­ли политика маршрутизатора не позволяет ему резервировать более 50 % про­цессорного времени (что подразумевает половинную задержку) и если 49 % уже зарезервировано, то поток будет отвергнут. Подобные вычисления необходимо производить для всех резервируемых ресурсов.

Чем строже спецификация потока, тем лучше для маршрутизаторов. Если же в спецификации говорится, что Скорость маркерного ведра составляет 5 Мбайт/с, однако пакеты могут быть размером от 50 до 1500 байт, значит, скорость переда­чи пакетов может колебаться от 3500 до 105 000 пакетов/с. Маршрутизатор, ужаснувшись при виде последнего числа, может отвергнуть такой поток. При ми­нимальном размере пакета, равном 1000 байт, 5-мегабайтный поток тем же са­мым маршрутизатором мог бы быть принят.

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

Возникает интересный вопрос: надо ли учитывать нагрузку на линию во вре­мя измерения задержки? Чтобы учесть загруженность линии, таймер должен включаться при отправке пакета ECHO. Чтобы игнорировать загрузку, таймер сле­дует включать, когда пакет ECHO достигает начала очереди.

Оба способа могут быть аргументированы. Учет трафика в линии при изме­рении задержки означает, что когда у маршрутизатора есть выбор между двумя линиями с одинаковой пропускной способностью, маршрут по менее загружен­ной линии рассматривается как более короткий. Такой выбор приведет к более сбалансированному использованию линий связи и, следовательно, к более эф­фективной работе системы.

К сожалению, можно привести аргумент и против учета загруженности ли­нии при расчете задержек. Рассмотрим подсеть, показанную на рис. 5.10. Ока разделена на две части — восточную и западную, которые соединены двумя ли­ниями, CF и EI.

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

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

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

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

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

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

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

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

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

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

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

Для описания алгоритма воспользуемся рис. 5.18, на котором изображен про­цесс, запущенный на узле А, которому необходимо отправить пакет на узел I. Алго­ритм AODV на каждом узле ведет таблицу, доступ к которой осуществляется с помощью поля адреса. Таблица содержит информацию об адресате, в том числе адрес ближайшего соседа, которому необходимо переслать пакет, чтобы он мог достичь пункта назначения. Допустим, А просматривает эту таблицу и не нахо­дит записи для I. Значит, нужно найти маршрут, ведущий к этому узлу. Итак, ал­горитм начинает заниматься поисками маршрутов только тогда, когда они реаль­но требуются. Это и делает его алгоритмом «по требованию».

Для поиска I узел А генерирует специальный пакет запроса маршрута ROUTE REQUEST и распространяет его по сети широковещательным способом. На рис. 5.18, а показано, что этот пакет достигает узлов В и D. На самом деле, при­чиной установления именно узлами В и D соединения с А является то, что они могут получать пакеты от А. Например, F не соединен дугой с А, потому что он не может принимать радиосигнал от этого узла. То есть F не соединен с А.

Формат пакета запроса маршрута показан на рис. 5.19. В нем, как видно из Этого рисунка, содержатся адреса источника и приемника (обычно IP-адреса), с помощью которых можно понять, кто кого ищет. Также содержится поле Иденти­фикатор запроса, которое представляет собой локальный счетчик, обновляемый каждым узлом независимо и инкрементирующийся всякий раз, когда распро­страняется пакет запроса маршрута. Поля Адрес источника и Идентификатор запроса вместе единственным образом идентифицируют пакет ROUTE REQUEST, что позволяет узлам обнаруживать и отвергать любые дубликаты.

В дополнение к счетчику Идентификатор запроса каждый узел имеет второй счетчик, который инкрементируется всякий раз при отправке пакета для запроса маршрута или ответе на такой пакет. Его работа напоминает часы, и используется он для того, чтобы можно было отличить новые маршруты от старых, Четвертое поле, показанное на рис. 5.19, это счетчик узла А\ пятое — последнее значение порядкового номера пакета, полученного от / (оно равно 0, если такого пакета не было). Вскоре мы более подробно раскроем назначение этих полей Наконец, по­следнее поле — Счетчик переходов — запоминает количество пересылок, совер­шенных пакетом. В начале работы алгоритма оно равно нулю.

Когда пакет запроса маршрута прибывает на узел (например, на узлы В и D), с ним происходит следующее:

1. Пара значений полей Адрес источника и Идентификатор запроса ищется в таблице локальной истории. С их помощью можно выяснить, приходил ли уже этот запрос и обрабатывался ли он. Если обнаруживается, что пакет яв­ляется дубликатом, он отвергается и его обработка прекращается. В против­ном случае указанная пара значений заносится в таблицу истории, чтобы в будущем можно было обнаружить дубликаты. Обработка запроса продолжа­ется.
2. Приемник ищет адрес назначения в таблице маршрутов. Если известен доста­точно свежий маршрут, отправителю посылается пакет наличия маршрута ROUTE REPLY, сообщающий ему о том, как можно достичь получателя (в двух словах: «Используй меня»). Что значит «свежий маршрут»? Имеется в виду, что поле Порядковый номер получателя в таблице маршрутизации имеет зна­чение большее или равное Порядковому номеру получателя из пакета запроса маршрута. Если оно меньше, значит, хранящийся в таблице маршрут явля­ется более старым, нежели предыдущий маршрут, имевшийся у отправителя к тому же пункту назначения. В этом случае выполняется пункт 3.
3. Поскольку у приемника отсутствует свежий маршрут к адресату, он инкре- ментирует поле Счетчик переходов и вновь широковещательным образом рас­пространяет пакет запроса маршрута. Из пакета извлекаются данные и сохраня­ются в виде новой записи в таблице обратных маршрутов. Эти данные будут использоваться для построения обратного пути, по которому впоследствии необходимо будет послать ответный пакет отправителю. Стрелки на рис. 5.18 как раз показывают процесс построения обратного пути. Для записи о только чтй созданном обратном пути запускается таймер. При наступлении тайм- аута запись удаляется.

Ни В, ни D не знают, где находится узел I, поэтому каждый из них создает об­ратный путь к А, как показано стрелками на рис. 5.18, и широковещательным способом распространяет пакет со Счетчиком переходов, установленным в еди­ницу. Этот пакет от В достигает С и D. Узел С делает запись в таблице обратных путей и, в свою очередь, тоже широковещательным способом распространяет па­кет далее. Что касается Д то он отвергает пакет: для него это дубликат. Разуме­ется, и В отвергает пакеты, полученные от D. Тем не менее, F и G принимают ши­роковещательное сообщение от D и сохраняют его, как показано на рис. 5.18, в. После того как Е, Н и I получают широковещательный пакет, запрос маршрута наконец достигает узла назначения (Г). Этот счастливый миг запечатлен на рис. 5.18, г. Обратите внимание: несмотря на то, что мы показали распростране­ние широковещательного пакета в виде трех стадий, на самом деле рассылка это­го пакета разными узлами никак не координируется.

В ответ на пришедший запрос узел I генерирует пакет наличия маршрута ROUTE REPLY, показанный на рис. 5.20. Поля Адрес отправителя, Адрес получателя и Счетчик переходов копируются из ROUTE REQUEST, а Порядковый номер получателя берется из собственного счетчика, хранящегося в памяти. Поле Счетчик перехо­дов устанавливается в 0. Поле Время существования используется для управле­ния реализуемостью маршрута. Данный пакет распространяется методом одно­адресной передачи на тот узел, с которого пришел запрос маршрута. В данном случае он уходит на узел G. Затем, в соответствии с установленным обратным путем, он попадет на D и наконец на А. При проходе каждого узла Счетчик пере­ходов инкрементируется, так что узел-отправитель может увидеть, насколько да­леко от него находится узел-получатель (7).

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

1. Не известен ни один маршрут.
2. Последовательный номер для I в пакете ROUTE REPLY больше, чем значение в таблице маршрутизации.
3. Последовательные номера равны, но новый путь короче.

Таким образом, все узлы, стоящие на обратном пути к А, совершенно бес­платно получают информацию о маршруте к узлу I. Это как бы побочный про­дукт построения маршрута для А. Узлы, получившие исходный пакет запроса маршрута, но не стоящие на обратном пути (узлы В, С, Е, Fn Н в данном примере) удаляют запись в таблице обратных маршрутов, когда ассоциированный с ней таймер достигает тайм-аута.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подобное резервирование может выполняться как в виде постоянной стан­дартной процедуры, так и в виде действия, выполняемого только при возникно­вении перегрузки. Недостаток постоянного резервирования заключается в том, что на эту процедуру расходуются вычислительные ресурсы. Если шесть вирту­альных каналов, которым разрешено использовать по 1 Мбит/с, проходят по од­ной и той же физической линии с пропускной способностью 6 Мбит/с, линия должна быть помечена как полная, хотя маловероятно, что все шесть виртуаль­ных каналов передают данные одновременно, да еще и используют всю доступ­ную пропускную способность. Следовательно, платой за резервирование будет неиспользованная пропускная способность.

Поскольку узлы могут перемещаться и выключаться, топология сети может из­меняться совершенно спонтанно. Например, если на рис. 5.18 узел G выключит­ся, А не поймет, что путь к I (ADGI) больше не может быть реализован. Алгорит­му нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Hello. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия и больше не связан с данным узлом. Аналогичным образом, если он пытается по­слать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна.

Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел Охранит историю о том, какие соседи снаб­жали узел пакетами для данных адресатов в течение последних ДГ секунд. Такие соседи называются активными соседями узла N для данного адресата. Узел N осуществляет сбор подобных сведений с помощью таблицы маршрутизации, ко­торая, как известно, в качестве индекса использует адрес назначения. В этой таб­лице указан тот узел, на который нужно переслать пакет, чтобы он мог дойти до адресата. Кроме того, в ней имеются сведения об оставшемся числе переходов, последнем порядковом номере получателя, а также об активных соседях данного адресата. Вид возможной таблицы маршрутизации для узла D при топологии, рассматриваемой в нашем примере, показан на рис. 5.21, а.

Рассмотрим наш предыдущий пример, предположив, что G внезапно вык­лючился. Образовавшаяся в результате этого события топология показана на рис. 5.21, б. Когда D обнаруживает, что G ушел из сети, он просматривает свою таблицу маршрутизации и видит, что G стоял на пути к Е, G и I. Объединением активных соседей для данных адресатов является множество {А, В}. Другими словами, А и В содержат записи о маршрутах, проходящих через G, поэтому их нужно проинформировать о том, что эти маршруты больше не работают. D сооб­щает им об этом, посылая специальные пакеты, заставляющие их обновить свои таблицы соответствующим образом. Сам узел D удаляет записи для адресатов Е, G и / из таблицы маршрутизации.

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

AODV, впрочем, может также заниматься широковещательной и групповой маршрутизацией. Детали см. в (Perkins and Royer, 2001). Маршрутизация в спе­циализированных сетях — чрезвычайно популярная сегодня область исследова­ний. Вопросам, связанным с ней, посвящено большое количество материалов. Например, (Chen и др., 2002; Ни and Johnson, 2001; Li и др., 2001; Raju and Garcia-Luna-Aceves, 2001; Ramanathan and Redi, 2002; Royer and Toh, 1999; Spohn and Garcia-Luna-Aceves, 2001; Tseng и др., 2001; Zadeh и др., 2002).