Информационно-техническая служба    Программы
Лицензионное
ПО
 Услуги
Наши
услуги
 Контакты
Контактная
информация
 Новости
Новости
в тему
 В начало
Начальная
страница
 Поиск
Форма для
поиска
  Логин: Пароль:

1С Комплексная автоматизация 8 Система 1С:Предприятие версии 8 - лучшее средство автоматизации предприятия!
  Поиск:  
· Главная
· Программы
· О компании
· Личный кабинет
· Обратная связь
· Наши форумы

·Вышел в свет номер 8 (август 2017 года) бухгалтерского ежемесячника "БУХ.1С"...
·Повышение цен на некоторые домашние продукты...
·Фирма "1С" поддержала хакатон по машинному обучению DeepHack.Turing ...
·Информационно-рекламная листовка "1С:Предприятие 8. ТОИР Управление ремонтами и обслуживанием о...
·Казахстан. Открытие нового сертифицированного экзаменационного центра (1С:СЭЦ) в городе Костанай...

Читать далее...


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


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

Классификация


Алгоритмы маршрутизации можно разделить на:



  • адаптивные и неадаптивные



  • глобальные и децентрализованные



  • статические и динамические


Требования: точность, простота, надежность, стабильность, справедливость, оптимальность.

Типы алгоритмов

Адаптивные алгоритмы. Описание: принимают во внимание актуальное состояние линии

Плюсы и минусы:

+ возможность адаптации к актуальному состоянию сети

- необходимо постоянно пересчитывать таблицы маршрутизации



Адаптивный централизированный алгоритм (англ. adaptive centralized routing). Описание: В сети существует так называемый Routing Control Center (RCC), который получает информацию от всех узлов об их соседних узлах, актуальную длину очереди и загрузки линии. В функции RCC входит сбор информации, подсчет оптимальных маршрутов для каждого узла, составление таблиц маршрутизации и рассылка их узлaм.

Плюсы и минусы

+ RCC обладает всей информацией и может создавать «идеальные» маршруты

+ узлы освобождены от необходимости расчета таблиц маршрутизации

- низкая надежность

- время от времени требуется перерасчет таблиц маршрутизации

- некорректная работа при разделенных сетях

- IS получают информации в различное время

- концентрация трафика возле RCC



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

Плюсы и минусы

+ легкость реализации

+ нет перегрузок

- проблемы при изменении топологии и нагрузки

- не происходит обмен данными о маршрутизации между узлами

- медленная адаптация к актуальному состоянию сети (время конвергенции)



Распределенный (Дистанционно-векторный алгоритм) (англ. distance vector routing). Описание: Также известен как Distributed Bellman-Ford Routing или Ford Fulkerson Algorithm. Данный алгоритм является распределенным, итерационным и асинхронным. Его можно представить как: «расскажи своим соседям, как выглядит мир». Каждый узел ведет таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию (количество хопов, задержку или длину очереди) до каждого соседа и рассылает ее своим соседям, которые в свою очередь выполняют то же самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.

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

Плюсы и минусы

+ самоорганизация

+ относительно простая реализация

- плохая конвергенция

- сложности при расширении сети

Пример: При использовании алгоритма возникают проблемы при отключении одного из узлов от сети — проблема «Count to Infinity» (счет до бесконечности).

Предотвращение: Split Horizon Algorithm — «не говори мне то, что я сказал тебе».



Алгоритм состояния канала (англ. Link state routing) Описание: Алгоритм, относящийся к адаптивным алгоритмам и основанный на состоянии связей. Его можно представить как: «расскажи миру о том, кто твои соседи». Сначала узел знает только своих соседей и стоимости связей, соединяющих его с ними. В процессе обмена информацией с соседними узлами узел получает информацию о топологии сети, при этом обменивается только информация о происшедших изменениях. В результате каждый узел знает всю топологию сети. Впервые был применен в ARPANET в 1979 году и пришел на смену дистанционно-векторному алгоритму. Причинами перехода служили:

* рост пропускной способности каналов и отсутствие ее учета в дистанционно-векторном алгоритме

* медленность дистанционно-векторного алгоритма, вызванная «счетом до бесконечности»

Алгоритм:

1. Определение адресов соседних узлов: новые узлы рассылают приветствие (HELLO-сообщения), соседние узлы сообщают свои адреса происходит при помощи рассылки HELLO-запросов

2. измерение стоимости линий или времeни передачи данных до соседних узлов происходит в результате рассылки эхо-сообщений

3. организация собранных данных в пакет, содержащий личный адрес, sequence number (для избежания повторений), age (для отброса устаревшей информации), дистанцию

4. рассылка пакетов всем узлам сети (flooding)

5. подсчет маршрутов на основе полученной от других узлов информации



Широковещательная маршрутизация (англ. broadcast routing).

Терминология: unicast — 1:1, multicast — 1:n, broadcast — 1:всем



Простые методы

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

* flooding: слишком много повторяющихся пакетов

Multidestatination Routing

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



Многоадресная рассылка

Алгоритм связующего дерева (англ. spanning tree) Описание: Связующее дерево (Spanning tree): дерево, не содержащее петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов.



Reverse path forwarding (Reverse path flooding). Описание: Алгоритм является самым простым и неадаптивным вариантом. Каждый полученный пакет пересылается по всем линиям, за исключением той, через которую он был получен. При этом только отправитель должен знать все связующее дерево. Алгоритм: Каждый маршрутизатор знает путь, который он должен использовать для unicast-пакетов. При получении пакета проверяется, был ли пакет получен по линии, которая обычно используется и пересылается по всем линиям, за исключением той, через которую он был получен. В противном случае пакет отбрасывается.



Reverse path broadcast. Описание: В отличии от Reverse path forwarding пакеты отправляются только по линиям, по которым другие узлы принимают данные



Неадаптивные алгоритмы. Описание: не принимают во внимание актуальное состояние сети, все маршруты рассчитываются до начала использования сети. Они в свою очередь подразделяются на алгоритмы, учитывающие топологию сети (spanning tree, flow based routing) и не учитывающие (flooding).

Плюсы и минусы

+ простота

+ хорошие результаты при неизменной топологии и нагрузке

- невозможность реагирования на изменения

- низкая скорость в неоднородных сетях



Неадаптивные: Shortest Path Routing. Описание: Данный алгоритм подсчитывает наименьший маршрут от корня дерева до узлов. Смысл заключается в создании пучка узлов Q, для которых уже был определен оптимальный маршрут. Оператор генерирует таблицы маршрутизации, которые загружаются при его инициализации и более не изменяются. Основывается на алгоритме Дейкстры.

Алгоритм: Наименьшее расстояние от A до D

1. узел A помечается как рассматриваемый

2. присвоить всем соседним узлам значение с дистанцией до рассматриваемого узла B(2,A), G(6,A) и добавить их в список кандидатов

3. выбрать из списка кандидатов узел с наименьшей дистанцией B(2,A)

4. пометить этот узел как рассматриваемый и добавить его в дерево

5. перейти к пункту 2

Плюсы и минусы

+ простота

+ хорошие результаты при постоянной топологии сети и нагрузке



Flow-Based Routing. Описание: Данный алгоритм является одним из неадаптивных алгоритмов. Он учитывает не только дистанцию между маршрутизаторами, но и загрузку сети. Полезен для нахождения маршрута для больших дистанций с большими задержками в доставке пакетов

Пример:

Дан граф для capacity и матрица трафика






  • Подсчет загрузки каждой линии




  1. взять одно из ребер графа


  2. найти, где оно встречается в таблице


  3. сложить все скорости из таблицы для этого ребра



Line
λi (packts/sec)















































































AB 3(AB) + 7(ABC) + 7(BAD) + 4(BAF) + 3(BADG) =24
AD 4(AD) + 2(ADE) + 2(ADG) + 5(ADEH) + 7(BAD) + 3(BADG) = 23
AF 5(AF) + 4(BAF) = 9
BC 7(ABC) + 3(BC) + 4(BCH) = 14
BE 3(BE) = 3
CE 7(CED) + 5(CE) + 3(CEDF) = 15
CH 4(BCH) + 5(CHG) + 3(CH) = 12
DE 2(ADE) + 5(ADEH) + 7(CED) + 3(CEDF) + 2(DE)+ 9(DEH) + 3(EDF)+ 9(FDEH) = 40
DF 3(CEDF)+ 9(DF) + 3(EDF)+ 9(FDEH) = 24
EH 5(ADEH)+ 9(DEH)+ 1(EHG)+ 2(EH) + 9(FDEH) = 26
FG 1(FG) = 1
GH 1(GH) + 1(EHG) + 5(CHG) = 7
DG 2(ADG) + 3(BADG) + 2(DG) = 7



  • подсчет задержки для каждого графа по формуле Ti = 1/(μCii).





Line
λi (packts/sec)
μCi (packts/sec)
Ti (msec)



































































































































AB 24 50 38.46
AD 23 50 37.04
AF 9 37.5 35.09
BC 14 25 90.91
BE 3 50 21.28
CE 15 75 16.67
CH 12 50 26.32
DE 40 50 100
DF 24 25 1000
EH 26 50 41.67
FG 1 100 10.1
GH 7 62.5 18.02
DG 7 62.5 18.02



  • Подсчет стоимости каждого ребра по формуле: Wi = λi/∑λi.





Line
λi (packts/sec)
μCi (packts/sec)
Ti (msec)
Wi




























































































































































AB 24 50 38.46 0.117
AD 23 50 37.04 0.112
AF 9 37.5 35.09 0.044
BC 14 25 90.91 0.068
BE 3 50 21.28 0.015
CE 15 75 16.67 0.073
CH 12 50 26.32 0.059
DE 40 50 100 0.195
DF 24 25 1000 0.117
EH 26 50 41.67 0.127
FG 1 100 10.1 0.005
GH 7 62.5 18.02 0.034
DG 7 62.5 18.02 0.034



  • подсчет общей задержки Toverall = ∑Ti•Wi Получаем: Toverall=162.531msec.


Так как полученное значение слишком велико, то его можно уменьшить за счет замены пути с самой большой задержкой DF(Ti, max = 1000msec) на путь D->G->F







[ Вернуться назад ]

Энциклопедия CISCO

Copyright © от 1С:Предприятие (Консалтинг, Разработка ПО, Обслуживание). Настройка оборудования Cisco Systems. - (936 Прочтено)

Encyclopedia ©

Архив статей  ::  Добавить новость ::  Контакт с автором ::  Рекомендовать Нас

Информационно-техническая служба
Использование материалов с этого сайта допускается только с письменного разрешения ООО "Информационно-Техническая Служба".
PHP-Nuke Copyright © 2005 by Francisco Burzi. This is free software, and you may redistribute it under the GPL. PHP-Nuke comes with absolutely no warranty, for details, see the license.
The Russian localization - project Rus-PhpNuke.com
Открытие страницы: 0.67 секунды
Rambler's Top100