Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 113
Текст из файла (страница 113)
По мере распространения и установки пакетов маршрутизаторы, получившие первые пакеты, начинают изменять свои маршруты. Соответственно разные маршрутизаторы будут пользоваться разными версиями топологии, что может привести к противоречиям, появлению в маршрутах петель, недоступных машин, а также к другим проблемам. Сначала мы опишем основной алгоритм распространения. Затем расскажем о некоторых улучшениях.
Основная идея алгоритма распространения пакетов состояния линии состоит в использовании алгоритма заливки. Чтобы держать этот процесс под контролем, в каждый пакет помещают порядковый номер, увеличивающийся на единицу для каждого следующего пакета. Маршрутизаторы записывают все пары (источник, порядковый номер), которые им попадаются. Когда приходит новый пакет состояния линий, маршрутизатор ишет адрес его отправителя и порядковый номер пакета в своем списке.
Если это новый пакет, он рассылается дальше по всем линиям, кроме той, по которой он пришел. Если же это дубликат, он удаляется. Если порядковый номер прибывшего пакета меньше, чем номер уже полученного пакета от того же отправителя, то такой пакет также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть более свежие данные. С этим алгоритмом связано несколько проблем, но с ними можно справиться. Во-первых, если последовательный номер, достигнув максимально возможного значения, обнулится, возникнет путаница. Решение состоит в использовании 32-разрядных порядковых номеров.
Лаже если рассылать каждую секунду по пакету, то для переполнения 4-байтового целого числа понадобится 137 лет. Во-вторых, если маршрутизатор выйдет из строя, будет потерян его порядковый номер. Если он будет снова загружен с нулевым порядковым номером, его пакеты будут игнорироваться как устаревшие. В.третьих, может произойти искажение порядкового номера — например, вместо номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае пакеты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие. Решение этих проблем заключается в помешении в пакет после его порядкового номера возраста пакета и уменьшении его на единицу каждую секунду, Когда возраст уменьшается до нуля, информация от этого маршрутизатора удаляется.
В нормальной ситуации новый пакет приходит, например, каждые 10 секунд; таким образом, сведения о маршрутизаторе устаревают, только когда маршрутизатор выключен (или в случае потери шести пакетов подряд, что маловероятно). Поле возраста также уменьшается на единицу каждым маршрутизатором во время начального процесса заливки, чтобы гарантировать, что ни один пакет не потеряется и не будет жить вечно. Лля повышения надежности этого алгоритма используются некоторые усовершенствования. Когда пакет состояния линий приходит на маршрутизатор для заливки, он не ставится сразу в очередь на отправку, Вместо этого он сохраняет- 422 Глава 5. Сетевой уровень ся в течение некоторого периода времени в области промежуточного хранения, Если за это время от того же отправителя успевает прийти еше один пакет, маршрутизатор сравнивает их порядковые номера.
Более старый пакет удаляется. Если номера одинаковые, то удаляется дубликат. Для защиты от ошибок на линиях связи между маршрутизаторами получение всех пакетов состояния линий подтверждается. Когда линия освобождается, маршрутизатор сканирует область промежуточного хранения, из которой выбираются для передачи пакеты или подтверждения. Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рис.
5.11, а, показана на рис. 5.12. Каждый ряд здесь соответствует недавно полученному, но еше не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и Е соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.
Флапз Флвпз отсылки подтверждения Порядковый Источник номер Возраст Л С Р я С Двнныв Рис. В. т 2. Буфер пакетов маршрутизатора В с рисунка бд 1 Как видно из рис. 5.12, пакет состояния линий от маршрутизатора А пришел напрямую, поэтому он должен быть отправлен маршрутизаторам С и Г, а подтверждение о его получении следует направить маршрутизатору А, что и показывают флаговые биты. Аналогично, пакет от Е следует переслать маршрутизаторам А и С, а Е отослать подтверждение. Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отличается.
Он был получен дважды, по линиям ЕАВ и ЕЕВ. Следовательно, его нужно отослать только С, но подтверждения выслать и А, и Е, как указывают биты. Если в то время, когда оригинал еше находится в буфере, прибывает дубликат пакета, значение битов должно быть изменено. Например, если копия состояния маршрутизатора С прибудет от Е прежде, чем четвертая строка таблицы будет разослана, шесть флаговых битов примут значение 100011, и это будет означать, что следует подтвердить получение пакета от Е, но не пересылать его Е Алгоритмы маршрутизации 423 Вычисление новых маршрутов Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф подсети, так как он располагает данными обо всех линиях.
На самом деле, каждая линия представлена даже дважды, по одному значению для каждого направления. Эти два значения могут усредняться или использоваться по отдельности. Теперь для построения кратчайшего пути ко всем возможным адресатам может быть локально применен алгоритм Дейкстры. Результат вычислений может быть установлен в таблицах маршрутов, после чего можно возобновить нормальную работу маршрутизатора. В подсети, состоящей из п маршрутизаторов, у каждого из которых 2 соседей, количество памяти, необходимой для хранения входной информации, пропорционально 2и.
Кроме того, может потребоваться много времени на обработку информации. В больших подсетях зто может составлять проблему. Тем не менее, во многих практичсских ситуациях маршрутизация с учетом состояния линий работает вполне удовлетворительно. Однако неисправности оборудования или программного обеспечения могут привести к очень серьезным проблемам при использовании данного алгоритма (а также других алгоритмов).
Например, если маршрутизатор заявит о существовании линии, которой у него в действительности нет, или наоборот, забудет о сушествовании име1ощейся у него линии, граф подсети окажется неверным. Если маршрутизатор не сможет переслать пакеты или повредит их при пересылке, также возникнет проблема.
Наконец, если у маршрутизатора закончится свободная память или он ошибется в расчетах маршрутов, также возможны различные неприятности. При увеличении размера подсети до нескольких десятков или сотен тысяч маршрутизаторов вероятность выхода из строя одного из них перестает быть пренебрежимо малой. Все, что можно здесь сделать, — зто попытаться ограничить вред, наносимый практически неизбежным выходом из строя оборудования. Эти проблемы и методы их разрешения подробно обсуждаются в (Рег!шап, 2988).
Маршрутизация с учетом состояния линий широко применяется в современных сетях, поэтому следует сказать несколько слов о некоторых примерах протоколов, использующих данный алгоритм. Одним из таких протоколов является протокол ОМАРЕ, все чаще применяемый в Интернете, о котором будет рассказано в разделе «Протокол внутреннего шлюза ОБРЕ». Другим важным протоколом с учетом состояния линий является 15-1$ (1пгеппег2!аге Яузгещ го 1пгегшег2!асе Яузгещ — связь между промежуточными системами) — протокол, разработанный для сети ПЕСпег и принятый впоследствии Международной организацией по стандартизации 1ЯО для использования вместе с протоколом сетевого уровня С).ХР, не требующим соединений.
С тех пор ои был модифицирован для поддержки также и других протоколов, в частности 1Р. Протокол 1Б-1о используется в некоторых магистралях сети Интернет (включая старую магистраль ХИРЕЕТ) и в некоторых цифровых сотовых системах, например, в СПРВ. В сети Моче!! Не!Маге применяется разновидность протокола 19- 1Б (Н2.БР) для маршрутизации 1РХ-пакетов. 424 Главе б, Сетевой уровень В основе работы протокола 1Б-1Б лежит распространение картины топологии маршрутизаторов, по которой рассчитываются кратчайшие пути. Каждый маршрутизатор сообщает в информации о состоянии линий доступные ему напрямую адреса сетевого уровня.
Эти адреса могут быть адресами 1Р, 1РХ, АРР1еТай или другими. Протокол 1Б-1Б может даже осуществлять одновременную поддержку нескольких протоколов сетевого уровня. Многие новшеств~ разработанные для протокола 1Б-1Б, были приняты несколько лет спустя при разработке протокола ОБРГ. К ним относятся метод саморегуляции лавинного потока обновлений информации о состоянии линий, концепция выделенного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути и умножения метрик. Соответственно, между протоколами 1Б-1Б и ОБРГ нет почти никакой разницы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
