Принципы маршрутизации. Алгоритмы маршрутизации. Протоколы маршрутизации.

      В архитектуре TCP/IP сети соединяются друг с другом коммутаторами IP-пакетов, которые называются шлюзами или IP-маршрутизаторами.       Основная задача IP-маршрутизатора — определение по специальному алгоритму адреса следующего IP-маршрутизатора.       Для решения этой задачи каждый IP-маршрутизатор должен располагать матрицей маршрутов (специальной базой данных, обеспечивающей маршрутизацию), которую необходимо регулярно обновлять.

      Алгоритм маршрутизации является тем фундаментом, на котором строится вся работа базовой сети с архитектурой TCP/IP Существует ряд требований, которые следует учитывать при выборе приемлемого алгоритма маршрутизации:    · алгоритм маршрутизации должен распознавать отказ и восстановление каналов связи или других IP-маршрутизаторов и переключаться на другие, подходящие маршруты.

   · алгоритм должен исключать образование циклов, петель в назначаемых маршрутах как между соседними IP-маршрутизаторами, так и для удалённых IP-маршрутизаторов.    · нагрузка, создаваемая управляющими сообщениями, которые необходимы для работы алгоритма маршрутизации, не должна ухудшать или нарушать нормальную работу сети.

   · поскольку размеры сети постоянно увеличиваются, необходимо обеспечить эффективное использование сетевых ресурсов

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

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

      Кроме перечисленных выше задач IP-маршрутизатор должен обеспечивать эффективное распределение собственных ресурсов как по пропускной способности каналов, так и по объёму буферных ЗУ, используемых для хранения пакетов, ожидающих передачу. Самая очевидная стратегия «первым пришёл — первым обслужен» (FCFS — First Come First Served) может оказаться неприемлемой в условиях перегрузки сети.

Алгоритм маршрутизации должен обеспечивать надёжный алгоритм определения состояния каждого канала связи и узла в базовой сети и, если требуется, состояние хост-ЭВМ.       Для этого нужен, по крайней мере, протокол канального уровня, предполагающий периодический обмен кадрами через каждый канал связи.       Однако этого часто оказывается недостаточно, поэтому дополнительно требуется специальный механизм в алгоритмах маршрутизации.       По техническим, административным, географическим, а также иногда и политическим соображениям IP-маршрутизаторы группируются в так называемые «автономные системы».       IP-маршрутизаторы, входящие в одну автономную систему, контролируются одной организацией, обеспечивающей их сопровождение, и используют общие для данной автономной системы алгоритмы маршрутизации.

      Конкретный вариант протокола маршрутизации, действующий внутри одной автономной системы, называется внутренним протоколом маршрутизации (IGP).

. Протокол для обмена служебной информацией между автономными системами называется внешним протоколом маршрутизации (EGP).

      Каждый IP-маршрутизатор должен обеспечить реализацию протоколов физического, канального, межсетевого уровней, а также протоколы доступа к сети. В качестве последних используются протоколы Ethernet, Frame Relay, ATM, SLIP, PPP и ряд других, а для сетей с архитектурой ISO протокол Х.25/2 (LAP-B).             Процедура выбора пути заложена в протоколе IP, причём IP-уровень не знает всего пути, а владеет лишь информацией о том, какому IP-маршрутизатору передать IP-пакет с конкретным адресом места назначения.

      Просмотр таблицы маршрутизации происходит в три этапа:    - ищется соответствие адреса, записанного в IP-пакете, адресу места назначения в маршрутной таблице. Связи “точка-точка” выявляются именно на этом этапе;    - ищется соответствие адреса, записанного в IP-пакете, адресу некоторой региональной сети места назначения.

   - ищется маршрут «по умолчанию», дейтаграмма посылается в соответствующий маршрутизатор.

      Существуют статические и динамические алгоритмы обновления таблицы.

      Статический алгоритм есть способ маршрутизации, не изменяющийся при изменении топологии и состояния сети. Примерами являются алгоритмы случайной и лавинной маршрутизации.       Случайная маршрутизация — передача данных из узла в любом, случайным образом выбранном направлении, кроме направления, по которому данные поступили в узел. Данные, совершая «блуждания» по сети с конечной вероятностью когда-либо достигают адресата.       Лавинная маршрутизация — передача данных из узла во всех направлениях, кроме того, по которому поступили данные. Очевидно, что хотя бы одно направление обеспечит доставку пакета за минимальное время, т.е. лавинная маршрутизация гарантирует малое время доставки.

      Шлюзы, входящие в состав одной автономной системы, могут выполнять алгоритм динамической маршрутизации — протоколы на основе алгоритма Беллмана-Форда и протоколы на основе алгоритма Дейкстры.

      Шлюзы, работающие по алгоритму Беллмана-Форда, хранят вектор длин кратчайших маршрутов до всех сетей, входящих в состав объединённой сети.       Периодически каждый шлюз передаёт свой вектор соседним шлюзам автономной системы, а элементы вектора, принятого от соседнего шлюза, складываются с длинами исходящих линий связи.       На основе полученной таблицы строится новый вектор длин кратчайших маршрутов — алгоритм Беллмана-Форда (DV).       Протоколы на основе DV-алгоритма достаточно просто реализуются, требуют мало памяти и процессорного времени, однако они обладают рядом общих недостатков. При увеличении количества сетей, входящих в состав автономной системы, резко возрастает количество передаваемой информации, т.к. DV-алгоритм требует, чтобы все шлюзы периодически передавали свои векторы длин маршрутов.

      Шлюзы, работающие по алгоритму Дейкстры (SPF-алгоритм), сначала определяют кратчайшие маршруты по всем сетям автономной системы. Для этого в каждом шлюзе строится полное дерево кратчайших путей с корнем в данном шлюзе.       Процедура построения дерева кратчайших путей использует принцип, согласно которому в дерево кратчайших путей первой включается дуга с наименьшей длиной, поэтому алгоритм Дейкстры часто называют первым кратчайшим путем.

      В целом, алгоритм Дейкстры, по сравнению с алгоритмом Беллмана-Форда, обеспечивает более реальную оценку ситуации в сети, более быструю реакцию на важные изменения в сети (такие, как включение новой линии связи) и уменьшает зацикливание пакетов; однако алгоритм Дейкстры сложнее в реализации и требует в несколько раз больше памяти.