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

Протоколы этого вида служат для сбора информации о топологии межсетевых соединений. Задача маршрутизации(подбора оптимального маршрута) решается на основе анализа таблиц маршрутизации, размещенных во всех маршрутизаторах и конечных узлах сети. Для автоматического построения таблиц маршрутизации маршрутизаторы обмениваются информацией о топологии составной сети в соответствии со специальным служебным протоколом. Протоколы этого типа называются протоколами маршрутизации (или маршрутизирующими протоколами). Протоколы маршрутизации (например, RIP, OSPF, NLSP) следует отличать от собственно сетевых протоколов (например, IP, IPX). И те и другие выполняют функции сетевого уровня модели OSI - участвуют в доставке пакетов адресату через разнородную составную сеть. Но в то время как первые собирают и передают по сети чисто служебную информацию, вторые предназначены для передачи пользовательских данных, как это делают протоколы канального уровня. Протоколы маршрутизации используют сетевые протоколы как транспортное средство. При обмене маршрутной информацией пакеты протокола маршрутизации помещаются в поле данных пакетов сетевого уровня или даже транспортного уровня, поэтому с точки зрения вложенности пакетов протоколы маршрутизации формально следовало бы отнести к более высокому уровню, чем сетевой. С помощью протоколов маршрутизации маршрутизаторы составляют карту связей сети той или иной степени подробности. На основании этой информации для каждого номера сети принимается решение о том, какому следующему маршрутизатору надо передавать пакеты, направляемые в эту сеть, чтобы маршрут оказался рациональным. Результаты этих решений заносятся в таблицу маршрутизации. При изменении конфигурации сети некоторые записи в таблице становятся недействительными. В таких случаях пакеты, отправленные по ложным маршрутам, могут зацикливаться и теряться. От того, насколько быстро протокол маршрутизации приводит в соответствие содержимое таблицы реальному состоянию сети, зависит качество работы всей сети. Протоколы маршрутизации могут быть построены на основе разных алгоритмов, отличающихся способами построения таблиц маршрутизации, способами выбора наилучшего маршрута и другими особенностями своей работы. Алгоритмы:

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

2. Существует и прямо противоположный, многошаговый подход - маршрутизация от источника (Source Routing). В соответствии с ним узел-источник задает в отправляемом в сеть пакете полный маршрут его следования через все промежуточные маршрутизаторы. При использовании многошаговой маршрутизации нет необходимости строить и анализировать таблицы маршрутизации. Это ускоряет прохождение пакета по сети, разгружает маршрутизаторы, но при этом большая нагрузка ложится на конечные узлы. Эта схема в вычислительных сетях применяется сегодня гораздо реже, чем схема распределенной одношаговой маршрутизации.

19. Методы доступа: СДПС, ССДПС, СДПН, эстафетный доступ.

1. Свободный доступ с проверкой столкновений (СДПС). Этот способ наиболее широко применяется в магистральных структурах. Система захватывает канал и начинает передачу в любой момент времени. Поскольку централизованное управление отсутствует, две и более системы могут вести передачу пакетов одновременно. В этом случае происходит столкновение – интерференция пакетов, передаваемых одновременно, в результате чего все передаваемые пакеты искажаются. Столкновения обнаруживаются путем приема каждой системой передаваемого ею пакета (рис. 6.8). При этом биты, передаваемые в канал, сравниваются с битами, принимаемыми из канала. Если регистрируется несовпадение переданного и принятого бита, это свидетельствует о столкновении пакетов в канале. При обнаружении столкновения система прекращает передачу пакета и повторяет передачу через некоторое время. Для того чтобы уменьшить вероятность повторных столкновений, каждая система начинает повторную передачу через случайный промежуток времени с достаточно большим средним значением t. Задержка передачи формируется как случайная величина, равномерно распределенная в интервале, где Тmax – максимальная задержка повторной передачи.

Из-за столкновений реальная пропускная способность моноканала оказывается меньше номинальной пропускной способности физического канала. В целях упрощения математических выражений пропускные способности оценивают числом пакетов, передаваемых за время Т, достаточное для передачи одного пакета по физическому каналу. Время передачи одного, пакета по физическому каналу Т называют окном,. Окно T=L[V, где L – длина пакета (точнее, кадра), бит, и V – пропускная способность физического канала, бит/с. С учетом сказанного пропускная способность моноканала S характеризуется средним числом пакетов, передаваемых в одном окне. Очевидно, что.

Пропускная способность моноканала при СДПС оценивается следующим образом. Столкновения исключаются, если в течение периода 2Т, называемого периодом уязвимости, передается только один пакет (рис. 6,9). Если в течение периода уязвимости будет передаваться еще один пакет, который начинается либо в первом окне, либо во втором, происходит столкновение. Для наиболее простой оценки предположим, что поток запросов на передачу создается бесконечным числом систем, работающих независимо друг от друга и в результате этого порождающих пуассоновский поток запросов с суммарной интенсивностью G запросов на одно окно. Вероятность передачи пакета без столкновения определяется вероятностью поступления в период уязвимости только одного пакета и равна. Следовательно, только g-я часть пакетов будет передана без искажений и интенсивность потока неискаженных пакетов.

Значение S характеризует пропускную способность моноканала, зависимость которой от интенсивности потока запросов G представлена на рис. 6.10 кривой СДПС. Максимум пропускной способности достигается при G=0,5 запросов на окно и составляет

пакета на одно окно.

Таким образом, СДПС позволяет использовать для передачи данных не более 18,4 % пропускной способности канала.

При конечном числе систем М пропускная способность моноканала:

2.Синхронный свободный доступ с проверкой столкновений.

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

3. Свободный доступ с проверкой несущей.

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

Если канал свободен, станция начинает передачу пакетов; если канал занят, передача откладывается и система ждет некоторое время (t=Т/2) затем снова слушает моноканал и т.д. В результате такого способа передачи, вероятность столкновения существенно ниже и увеличивается степень пропускной способности физического канала.

Увеличивая степень пропускной способности канала, которая стремится к пределу не превышающему 73,6%, при увеличении t и наоборот, но не исключает возможности столкновения из-за конечного времени столкновения.

4.Эстафетный доступ.

СА подключенные к каналу связаны друг с другом кольцевой связью, по которой между адаптерами передается эстафета в качестве которой выступает сигнал, разрешающий доступ к каналу связи. Эстафета передается в последующий адаптер по окончанию передачи пакета предыдущему. Если же пакета на передачу нет, то эстафета передается последующему адаптеру немедленно.

При эстафетном доступе почти полностью используется пропускная способность физического канала. Время доставки не превышает N*T, где N – число активных систем ЛС, T – время передачи кадра. В такой сети все системы находятся в одинаковых условия и получают разрешение на передачу кадров в моноканал с частотой не ниже 1/ N*T. В качестве эстафеты используется специальный маркер, передаваемый от одной СА к другому по кольцу.