Реклама маршрута разделенного горизонта
В компьютерных сетях объявление маршрута с разделенным горизонтом — это метод предотвращения петель маршрутизации в протоколах маршрутизации с вектором расстояния путем запрета маршрутизатору объявлять маршрут обратно на интерфейс, из которого он был получен.
Концепция была предложена в 1974 году Торстеном Цегрелом и первоначально реализована в шведской сети TIDAS, вдохновленной ARPANET . [1] [2] [3]
Терминология
[ редактировать ]Вот некоторая основная терминология:
- Отравление маршрута : если узел N узнает, что его маршрут к пункту назначения D недоступен, сообщите об этом всем узлам в сети, отправив им сообщение о том, что расстояние от N до D, как воспринимает N, бесконечно.
- Правило разделения горизонта: если узел N использует интерфейс I для передачи в заданный пункт назначения D, то N не должен отправлять через I новую информацию о D.
- Правило обратного отравления: если узел N использует интерфейс I для передачи в заданный пункт назначения D, N отправляет через I информацию о том, что его стоимость перехода к D бесконечна.
В то время как при разделенном горизонте N не отправляет никакой информации через I, при отравленном обратном узле N говорит невинную ложь.
Пример
[ редактировать ]В этом примере сетевой узел A направляет пакеты узлу B, достичь узла C. чтобы Ссылки между узлами представляют собой отдельные каналы «точка-точка».
Согласно правилу «расщепления горизонта», узел A не объявляет свой маршрут для C (а именно от A до B и до C обратно в B. ) На первый взгляд это кажется излишним, поскольку B никогда не будет маршрутизировать через узел A поскольку этот маршрут стоит дороже, чем прямой маршрут от B к C. , Однако, если соединение между B и C прервется, и получил маршрут от A до C , B может в конечном итоге использовать этот маршрут через A. B A отправит пакет обратно в B , создав петлю. Это задача счета до бесконечности . При наличии правила «расщепления горизонта» этот конкретный сценарий цикла не может произойти, что сокращает время конвергенции в сложных средах с высокой избыточностью.
Маршрутизация с «расщеплением горизонта» и «ядовитым реверсом» [4] — это вариант объявления маршрутов с разделенным горизонтом, при котором маршрутизатор активно объявляет маршруты как недоступные через интерфейс, по которому они были изучены, устанавливая бесконечную метрику маршрута (16 для RIP ). Результатом такого объявления является немедленное удаление большинства закольцованных маршрутов до того, как они смогут распространиться по сети.
Основным недостатком обратного отравления является то, что он может значительно увеличить размер объявлений о маршрутизации в некоторых довольно распространенных сетевых топологиях, но позволяет повысить общую эффективность сети в случае сбоев. Разделение горизонта означает, что если соседний маршрутизатор отправляет маршрут маршрутизатору, принимающий маршрутизатор не будет распространять этот маршрут обратно на рекламный маршрутизатор на том же интерфейсе.
При отравлении маршрута, когда маршрутизатор обнаруживает, что один из подключенных маршрутов вышел из строя, он отравляет маршрут, назначая ему бесконечную метрику и объявляя о ней соседям. Когда маршрутизатор объявляет своим соседям отравленный маршрут, его соседи нарушают правило разделения горизонта и отправляют обратно отправителю тот же отравленный маршрут, который называется обратным отравлением. Чтобы дать маршрутизатору достаточно времени для распространения отравленного маршрута и гарантировать отсутствие петель маршрутизации во время распространения, маршрутизаторы реализуют механизм удержания.
Ядовитый реверс
[ редактировать ]Poison Reverse часто используется в маршрутизации векторов расстояний для решения проблемы счета до бесконечности . На практике яд-реверс можно рассматривать как альтернативу расщеплению горизонта. При использовании «ядовитого реверса» реклама маршрутов, которая была бы подавлена разделенным горизонтом, вместо этого рекламируется на расстоянии бесконечности.
Основная идея обратного отравления состоит в том, чтобы гарантировать, что путь не вернется обратно в тот же узел, если стоимость изменилась внутри сети. Примером этого может быть: Узел Z маршрутизируется через узел Y к пункту назначения X. Если стоимость между Y и X увеличивается, возникнет проблема счета до бесконечности. Чтобы этого избежать, мы реализуем токсичное обращение. Пока Z проходит через узел Y, чтобы добраться до X, Z будет лгать Y: Z объявит Y о бесконечной стоимости до пункта назначения X.
Цифры по краям — это стоимость ссылок.
Следуя этой топологии, строим векторы расстояний всех узлов сети:
| Место назначения | это З | к Y | до Х |
| от Я | 0 | 1 | 3 |
| от Y | 1 | 0 | 2 |
| от Х | 3 | 2 | 0 |
Первая, вторая и третья строки соответствуют векторам расстояний узла Z, узла Y и узла X соответственно.
Следующая матрица содержит оценки расстояний от Z до всех остальных узлов сети через каждого из ее соседей.
| Место назначения | через Z | через Y | через Х |
| это З | 0 | Х | Х |
| к Y | Х | 1 | 32 |
| до Х | Х | 3 | 30 |
Поскольку Z проходит через Y, чтобы добраться до X, стоимость пути от Z до X равна 3. Ядовитый обратный эффект срабатывает, когда узел передает свой вектор расстояния своим соседям. Векторы расстояний, передаваемые Z:
К Y: узел Z объявляет свой вектор расстояния, заменяя последний элемент на ∞, т. е. отправляет [0, 1, ∞]
К X: узел Z объявляет свой вектор расстояния без каких-либо замен, т. е. он отправляет [0, 1, 3]
Как мы видим в векторе расстояния, который передается узлу Y, конечный пункт назначения X имеет значение бесконечности.
Poison Reverse решает проблему счета до бесконечности, поскольку если стоимость связи между Y и X увеличится, скажем, до 70, то Y и Z не будут прыгать между собой, а вместо этого напрямую попробуют другой путь. В качестве альтернативы, если не используется обратное отравление, когда стоимость связи между Y и X увеличивается, Y сообщит об этой новости Z. Однако, прежде чем объявить, Y может использовать тот факт, что Z может связаться с X со стоимостью 3, чтобы решить, что Y может достичь X со стоимостью 4. Затем Z обновляет свою стоимость перехода до X через Y, как 5. После этого Y обновляет свою стоимость перехода до X, через Z, как 6. и так далее, пока стоимость перехода от Z до X не достигнет 30. В этот момент, после 30 итераций, алгоритм сходится.
Обратное действие яда не всегда работает. Например:
Если связь между C и D выйдет из строя, узел C все равно может попытаться пройти через B, чтобы добраться до пункта назначения. B уже маршрутизировался через A и будет продолжать это делать. Теперь A не может маршрутизироваться через B из-за обратного отравления, но в этот момент A в конечном итоге получит сообщение от C, объявляющее, что у C есть маршрут со стоимостью 7 до D, где c(C,B)+distance(B,D )=3+(3+1)=7. Затем A будет полагаться на C для маршрутизации к D. Таким образом, после сбоя CD обновится C, а затем A, B, C, A, B, C и так далее. Отсюда у нас есть петля, которую мы не можем решить с помощью реверса яда. [5]
Однако это можно сделать с помощью реализации протокола вектора расстояния, называемого RIP .
Реализации
[ редактировать ]Метод расщепления горизонта эффективен и прост в реализации и поэтому используется большинством протоколов вектора расстояния. В частности, его используют:
- РВАТЬ
- IGRP
- EIGRP
- VPLS , который использует технику разделения горизонта, чтобы избежать петель в плоскости пересылки.
- Babel , который применяет разделенный горизонт только к проводным каналам связи.
См. также
[ редактировать ]- DNS с разделенным горизонтом , аналогичная концепция DNS, обеспечивающая выборочную публикацию информации.
- Отравление маршрута
Ссылки
[ редактировать ]- ^ Процедура маршрутизации для сети коммутации сообщений TIDAS , Транзакции IEEE при связи, 1975 г.
- ↑ Письмо Торстена Цегрела профессору Леонарду Кляйнроху , 19 августа 1974 г.
- ↑ Торстен Цегрелль — швед, «починивший» Интернет , Internetmuseum.se, дата обращения 9 ноября 2017 г.
- ^ Протоколы IP-маршрутизации Уилесс Д. Блэк
- ^ https://people.mpi-sws.org/~gummadi/teaching/sp07/datanets/homework/homework2solution.pdf [ только URL-адрес PDF ]
Джеймс Ф. Куроуз; Кейт В. Росс (2017). Компьютерные сети: нисходящий подход, седьмое издание . Харлоу, Англия: Пирсон. п. 418.
Внешние ссылки
[ редактировать ]- «Разделение горизонта» и «Разделение горизонта с помощью Poison Reverse» в книге « Конвергенция в RIP Internetworks » от Microsoft TechNet.