Алгоритм маршрутизации
Целевые функции и анализ существующих алгоритмов маршрутизации. Борьба с перегрузкой и постановка задачи маршрутизации. Разработка алгоритма маршрутизации трафика в MPLS-сети. Разработка алгоритма динамической маршрутизации на базе протокола OSPF.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 12.12.2014 |
| Размер файла | 517,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство Образования и Науки Кыргызской Республики
Кыргызский Государственный Технический Университет им.И.Раззакова
Факультет Информационных Технологий
Кафедра ИВТ
Пояснительная записка к курсовому проекту
На тему: Алгоритм маршрутизации
Выполнил: Тимурбаев Р.Т.
Проверила: Токмергенова А.З.
Содержание
Введение
1. Обзор и анализ алгоритмов маршрутизации
1.1 Обзор целевых функций алгоритмов маршрутизации
1.2 Анализ существующих алгоритмов маршрутизации
1.3 Общие принципы борьбы с перегрузкой
1.4 Постановка задачи маршрутизации
2. Разработка алгоритма маршрутизации
2.1 Разработка алгоритма маршрутизации трафика в MPLS-сети
2.2 Разработка алгоритма динамической маршрутизации на базе протокола OSPF
2.3 Разработка алгоритма дырявого ведра
2.4 Алгоритм выбора маршрута
2.5 Сравнительный анализ
Заключение
Список использованной литературы
Приложение
маршрутизация алгоритм перегрузка трафик
Введение
Целью данного курсового проекта является ознакомление с основными алгоритмами, необходимыми для разработки сетевого уровня. При разработке необходимо учесть, что существуют две принципиально различные философии организации подсети, одна с использованием соединений, а другая- без соединения. В контексте внутреннего устройства подсети соединение обычно называют виртуальным каналом, по аналогии с физическими каналами, устанавливаемым телефонной системой. Независимые пакеты в системе без установления соединений называются дейтаграммами, по аналогии с телеграммами.
Основная функция сетевого уровня заключается в выборе маршрута для пакетов от начальной до конечной точки. В большинстве сетей пакетам приходится проходить через несколько маршрутизаторов. Единственным исключением являются широковещательные сети, но даже в них маршрутизация является важным вопросом, если отправитель и получатель находятся в разных сетях. Алгоритмы выбора маршрутов и используемые ими структуры данных являются главной целью при проектировании сетевого уровня.
Алгоритм маршрутизации реализуется той частью программного обеспечения сетевого уровня, которая отвечает за выбор выходной линии для отправки пришедшего пакета. Если подсеть использует дейтаграммную службу, выбор маршрута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, маршрут выбирается только при создании нового виртуального канала. После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса связи с пользователем (например, сеанса регистрации на терминале или передачи файла).
Полезно понимать разницу между маршрутизацией, при которой системе приходится делать выбор определенного маршрута следования, и пересылкой --действием, происходящим при получении пакета. Можно представить себе маршрутизатор как устройство, в котором функционируют два процесса. Один из них обрабатывает приходящие пакеты и выбирает для них по таблице маршрутизации исходящую линию. Такой процесс называется пересылкой. Второй процесс отвечает за заполнение и обновление таблиц маршрутизации. Именно здесь в игру вступает алгоритм маршрутизации.
Вне зависимости от того, отдельно ли выбираются маршруты для каждого пакета или же только один раз для соединения, желательно, чтобы алгоритм выбора маршрута обладал определенными свойствами -- корректностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Правильность и простота вряд ли требуют комментариев, а вот потребность в надежности не столь очевидна с первого взгляда. Во время работы большой сети постоянно происходят какие-то отказы аппаратуры и изменения топологии. Алгоритм маршрутизации должен уметь справляться с изменениями топологии и трафика без необходимости прекращения всех задач на всех хостах и перезагрузки сети при каждой поломке маршрутизатора.
Алгоритм маршрутизации должен также обладать устойчивостью. Существуют алгоритмы выбора маршрута, никогда не приходящие в состояние равновесия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными -- вряд ли кто-нибудь станет возражать против них, -- однако они зачастую оказываются взаимоисключающими.
1. Обзор и анализ алгоритма маршрутизации
1.1 Обзор целевых функций алгоритмов маршрутизации
Основная работа сетевого уровня заключается в выборе маршрута для пакетов от отправителя до получателя. В большинстве сетей пакетам приходится пройти через несколько маршрутизаторов. Единственным исключением являются широковещательные сети, но даже в них маршрутизация является важным вопросом, если отправитель и получатель находятся в разных сетях.
Алгоритмы, выбирающие маршруты, и используемые ими структуры данных являются главной задачей проектирования сетевого уровня.
Алгоритм выбора маршрута является частью программного обеспечения сетевого уровня, ответственной за выбор выходной линии, по которой следует отправить пришедший пакет. Если подсеть использует дейтаграммную службу, выбор маршрута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, маршрут выбирается только при создании нового виртуального канала После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса пользователя.
Однако в обоих случаях алгоритм выбора маршрута должен обладать определенными свойствами: правильностью, простой, надежностью, устойчивостью, справедливостью и оптимальностью. Правильность и простота вряд ли требуют комментариев, но потребность в надежности не столь очевидна с первого взгляда. За период работы большой сети постоянно происходят различные отказы аппаратуры н изменения топологии. Алгоритм маршрутизации должен уметь справляться с изменениями топологии н трафика без необходимости прекращения всех задач на всех хостах и перезагрузки сети при каждой поломке маршрутизатора.
Алгоритм выбора маршрута должен также обладать устойчивостью. Существуют алгоритмы выбора маршрута, никогда не приходящие в состояние равновесия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными - вряд ли кто-нибудь станет возражать против них, однако эти цели часто оказываются взаимоисключающими. Прежде чем попытаться найти приемлемое соотношение справедливости и оптимальности, следует решить, что именно мы будем оптимизировать. Можно попытаться минимизировать среднее время задержки или увеличить общую пропускную способность сети. Однако обе эти цели также противоречат друг другу, поскольку работа любой системы с очередями вблизи максимума производительности предполагает долгое стояние в очередях. В качестве компромисса многие сети стараются минимизировать количество пересылок для каждого пакета, поскольку при этом снижается время прохождения пакета по сети, а также снижается время прохождения пакета по сети, а также снижается нагрузка на сеть, в результате чего улучшается пропускная способность.Алгоритмы выбора маршрута можно разбить на два основных класса: адаптивные и неадаптнвные. Неадаптивные алгоритмы не учитывают при выборе маршрута топологии и текущего состояния сети, не измеряют трафик в линиях. Вместо этого выбор маршрута для каждой пары станций производится заранее, в автономном режиме, и список маршрутов загружается в маршрутизаторы во время загрузки сети. Такая процедура иногда называется статической маршрутизацией.
1.2 Анализ существующих алгоритмов маршрутизации
Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:
1. Статическими или динамическими
2. Одномаршрутными или многомаршрутными
3. Одноуровневыми или иерархическими
4. С интеллектом в главной вычислительной машине или в роутере
5. Внутридоменными и междоменными
6. Алгоритмами состояния канала или вектора расстояний
Статические или динамические алгоритмы
Статические алгоритмы маршрутизации вообще вряд ли являются алгоритмами. Распределение статических таблиц маршрутизации устанавливется администратором сети до начала маршрутизации. Оно не меняется, если только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в окружениях, где трафик сети относительно предсказуем, а схема сети относительно проста.
Т.к. статические системы маршрутизации не могут реагировать на изменения в сети, они, как правило, считаются непригодными для современных крупных, постоянно изменяющихся сетей. Большинство доминирующих алгоритмов маршрутизации 1990гг. - динамические.
Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Такие сообщения пронизывают сеть, стимулируя роутеры заново прогонять свои алгоритмы и соответствующим образом изменять таблицы маршрутизации. Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно разработать "роутер последнего обращения" (т.е. роутер, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой роутер выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут хотя бы определенным образом обработаны.
Одномаршрутные или многомаршрутные алгоритмы
Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого. Преимущества многомаршрутных алгоритмов очевидны - они могут обеспечить заначительно большую пропускную способность и надежность.
Одноуровневые или иерархические алгоритмы
Некоторые алгоритмы маршрутизации оперируют в плоском пространстве, в то время как другие используют иерархиии маршрутизации. В одноуровневой системе маршрутизации все роутеры равны по отношению друг к другу. В иерархической системе маршрутизации некоторые роутеры формируют то, что составляет основу (backbone - базу) маршрутизации. Пакеты из небазовых роутеров перемещаются к базовыи роутерам и пропускаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового роутера через один или несколько небазовых роутеров до конечного пункта назначения.
Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или областями. В иерархических системах одни роутеры какого-либо домена могут сообщаться с роутерами других доменов, в то время как другие роутеры этого домена могут поддерживать связь с роутеры только в пределах своего домена. В очень крупных сетях могут существовать дополнительные иерархические уровни. Роутеры наивысшего иерархического уровня образуют базу маршрутизации.
Основным преимуществом иерархической маршрутизации является то, что она имитирует организацию большинства компаний и следовательно, очень хорошо поддерживает их схемы трафика. Большая часть сетевой связи имеет место в пределах групп небольших компаний (доменов). Внутридоменным роутерам необходимо знать только о других роутерах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно может быть уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации.
Алгоритмы с игнтеллектом в главной вычислительной машине или в роутере
Некоторые алгоритмы маршрутизации предполагают, что конечный узел источника определяет весь маршрут. Обычно это называют маршрутизацией от источника. В системах маршрутизации от источника роутеры действуют просто как устойства хранения и пересылки пакета, без всякий раздумий отсылая его к следующей остановке.
Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов роутеры определяют маршрут через об'единенную сеть, базируясь на своих собственных расчетах. В первой системе, рассмотренной выше, интеллект маршрутизации находится в главной вычислительной машине. В системе, рассмотренной во втором случае, интеллектом маршрутизации наделены роутеры.
Компромисс между маршрутизацией с интеллектом в главной вычислительной машине и маршрутизацией с интеллектом в роутере достигается путем сопоставления оптимальности маршрута с непроизводительными затратами трафика. Системы с интеллектом в главной вычислительной машине чаще выбирают наилучшие маршруты, т.к. они, как правило, находят все возможные маршруты к пункту назначения, прежде чем пакет будет действительно отослан. Затем они выбирают наилучший мааршрут, основываясь на определении оптимальности данной конкретной системы. Однако акт определения всех маршрутов часто требует значительного трафика поиска и большого об'ема времени.
Одной из основных причин перегрузки является неравномерность трафика Бели бы хосты можно было заставить передавать все время с постоянной скоростью, перегрузки случались бы значительно реже.
Если оставшееся количество байт меньше размера следующего пакета, следующий пакет должен ждать следующего интервала времени. Представьте себе ведро с маленькой дырочкой в днище, как показано на рис. 5.28, а. Независимо от скорости, с которой вода наливается в ведро, выходной поток обладает постоянной скоростью, когда в ведре есть вода, и нулевой скоростью, когда ведро пустое. Кроме того, когда ведро наполняется, вся лишняя вода выливается через край и теряется (то есть не попадает в выходной поток под дырочкой).
Определение маршрута может базироваться на различных показателях (величинах, результирующих из алгоритмических вычислений по отдельной переменной - например, длина маршрута) или комбинациях показателей. Программные реализации алгоритмов маршрутизации высчитывают показатели маршрута для определения оптимальных маршрутов к пункту назначения.
Для облегчения процесса определения маршрута, алгоритмы маршрутизации инициализируют и поддерживают таблицы маршрутизации, в которых содержится маршрутная информация. Маршрутная информация изменяется в зависимости от используемого алгоритма маршрутизации.
Алгоритмы маршрутизации заполняют маршрутные таблицы неким множеством информации. Ассоциации "Пункт назначения/следующая пересылка" сообщают роутеру, что определенный пункт назначения может быть оптимально достигнут путем отправки пакета в определенный роутер, представляющий "следующую пересылку" на пути к конечному пункту назначения. При приеме поступающего пакета роутер проверяет адрес пункта назначения и пытается ассоциировать этот адрес со следующей пересылкой. На рис. 2-1 приведен пример маршрутной таблицы "место назначения/следующая пересылка". В маршрутных таблицах может содержаться также и другая информация. "Показатели" обеспечивают информацию о желательности какого-либо канала или тракта. Роутеры сравнивают показатели, чтобы определить оптамальные маршруты. Показатели отличаются друг oт друга в зависимости от использованной схемы алгоритма маршрутизации. Далее в этой главе будет представлен и описан ряд общих показателей.
Роутеры сообщаются друг с другом (и поддерживают свои маршрутные таблицы) путем передачи различных сообщений. Одним из видов таких сообщений является сообщение об "обновлении маршрутизации". Обновления маршрутизации обычно включают всю маршрутную таблицу или ее часть. Анализируя информацию об обновлении маршрутизации, поступающую ото всех роутеров, любой из них может построить детальную картину топологии сети. Другим примером сообщений, которыми обмениваются роутеры, является "об'явление о состоянии канала". Об'явление о состоянии канала информирует другие роутеры о состоянии кааналов отправителя. Канальная информация также может быть использована для построения полной картины топологии сети. После того, как топология сети становится понятной, роутеры могут определить оптимальные маршруты к пунктам назначения.
В зависимости от способа формирования таблиц маршрутизации одношаговые алгоритмы делятся на три класса:
алгоритмы фиксированной (или статической) маршрутизации;
алгоритмы простой маршрутизации;
алгоритмы адаптивной (или динамической) маршрутизации.
В первом случае все записи в таблице маршрутизации статические. Администратор сети сам решает, на какие маршрутизаторы надо передавать пакеты с теми или иными адресами, и заносит соответствующие записи в таблицу маршрутизации вручную (например, с помощью утилиты route ОС UNIX или Windows NT).
Таблица, как правило, создается в процессе загрузки и редактируется по мере необходимости. Такие исправления могут понадобиться, в частности, если в сети отказывает какой-либо маршрутизатор, и его функции передаются другому.
Таблицы делят на одномаршрутные, в которых для каждого адресата задан один путь, и многомаршрутные, когда предлагается несколько альтернативных путей. В случае многомаршрутных таблиц должно быть задано правило выбора одного из маршрутов. Чаще всего один путь является основным, а остальные -- резервными.
Очевидно, что алгоритм фиксированной маршрутизации с его способом формирования таблиц маршрутизации вручную приемлем только в небольших сетях с простой топологией. Однако он может быть эффективно использован и на магистралях крупных сетей с простой структурой и очевидными наилучшими путями следования пакетов в подсети.
В алгоритмах простой маршрутизации таблица маршрутизации либо вовсе не используется, либо строится без участия протоколов маршрутизации.
1.3 Общие принципы борьбы с перегрузкой
Многие проблемы, возникающие в сложных системах, таких как компьютерные сети, следует рассматривать с точки зрения теории управления. При таком подходе все решения делятся на 2 группы: без обратной связи и с обратной связью. Решения без обратной связи заключается в попытках решить проблему с помощью улучшения дизайна системы, пытаясь, таким образом, в первую очередь предотвратить возникновение самой ситуации не предпринимается.
К методам управления без обратной связи относятся решения о том, когда разрешать новый трафик, когда отвергать пакеты, и какие именно, а также составление расписаний для различных участков сети. Общее в этих решениях то, что они не учитывают текущего состояния сети.
Решения с обратной связью, напротив, основываются на учете текущего состояния системы Этот подход состоит из трех следующих частей:
Наблюдения за системой, с целью определить, где и когда произойдет перегрузка.
Передачи информации о перегрузке в е места, где могут быть предприняты соответствующие действия.
Принятия необходимых мер для устранения перегрузки.
При наблюдении за состоянием подсети с целью обнаружения перегрузки могут измеряться различные параметры. Главным являются процент пакетов, отвергаемых из-за отсутствия свободного места в буфере, средняя длина очереди, процент пакетов, переданных повторно, так как срок ожидания подтверждения их получения истек, среднее время задержки пакетов и среднеквадратичное отклонение задержки пакетов. Во всех случаях увеличивающиеся значения параметров являются сигналами о растущей перегрузке.
Второй этап борьбы с перегрузкой состоит в передаче информации о перегрузке от мета ее обнаружения в место, где могут быть предприняты действия по ее устранению. Очевидное решение заключается в пересыпке маршрутизатором, обнаружившим перегрузку, пакета источнику или источникам трафика с извещением о наличии проблемы. Эти пакеты окажут дополнительную нагрузку на четь как раз в тот момент, когда нагрузку необходимо снизить.
Существую, однако, и другие решения Например, можно зарезервировать в каждом пакете один или несколько бит, которые будут заполняться маршрутизаторами при достижении перегрузки порогового уровня Таким образом, соседи этого маршрутизатора узнают о том, что в данном участке сети наблюдается перегрузка.
Еще один метод состоит в том, что хосты или маршрутизаторы периодически посыпают пробные пакеты, явно спрашивая друг друга о перегрузке. Собранная таким образом информация может затем использоваться для выбора маршрутов в обход участков в сета, в которых возникла проблема с перегрузкой. Так, некоторые радиостанции обзавелись вертолетами, летающими над городами и сообщающими слушателям на дорогах, в надежде, что слушающие их водители выберут другие маршруты.
Известны различные алгоритмы борьбы с перегрузкой. Янг и Редан разработали метод систематизации этих алгоритмов. Они начали с того, что разделили все методы на алгоритмы с обратной связью и без нее. Затем они разделили алгоритмы без обратной связи на работающие у отправителя и получателя Алгоритмы с обратной связью также были разделены на две категории: с явной и неявной обратной связью. В алгоритмах с явной обратной сеязью от точки возникновения перегрузки в обратной направлении посылаются пакеты, предупреждающие о заторе. В алгоритмах с неявной обратной связью источник приходит к выводу о наличии перегрузки, основываясь на локальных наблюдениях, например по значению интервала времени, требующегося для получения подтверждения.
Наличие перегрузки означает, что нагрузка (временно) превысила возможности ресурсов данной части системы Возможны два решения данной проблемы: увеличить ресурсы системы или снизить нагрузку. Например, подсеть может использовать телефонные линии с модемами, чтобы увеличить пропускную способность между определенными точками. В системах типа 5МО5 можно запросить у оператора связи временную дополнительную пропускную способность. В спутниковых системах большую пропускную способность часто дает увеличение мощности передатчика Разбиение трафика на несколько маршрутов также может позволить ликвидировать местную перегрузку. Для увеличения пропускной способности сети могут быть задействованы запасные маршрутизаторы.
Однако иногда увеличить пропускную способность бывает невозможно, либо она уже увеличена до предела. В таком случае единственный способ борьбы с перегрузкой состоит в уменьшении нагрузки. Для этого существует несколько способов, включая отказ в обслуживании или снижения уровня обслуживания некоторых или всех пользователей, а также составлении более четкого расписания потребностей пользовал елей в обслуживании.
1.4 Постановка задачи маршрутизации
В качестве примера математической модели задачи принятия решения, целесообразно рассмотреть постановку одной из самых распространенных оптимизационных задач - задачи маршрутизации. Основной базовой моделью задач маршрутизации можно вполне обосновано считать задачу о коммивояжере, ставшей известной в отечественной литературе в 1960-1970 годах как задача о бродячем торговце. Ее некоторая универсальность связана с необходимостью определения оптимальных в некотором смысле маршрутов для нескольких коммивояжеров.
Первоначально задача коммивояжера была сформулирована для сферы маркетинга. Позднее она нашла применение в других областях управленческой деятельности, особенно там, где имела место значительная территориальная рассредоточенность объектов на местности. Примерами практического использования данного класса задач может служить определение оптимальных маршрутов:
- обслуживания территориально рассредоточенных технических объектов в газовой и нефтяной промышленности;
- облета экспедиций и сброса соответствующих грузов;
- обслуживания технических объектов военного назначения;
- поражения боевыми блоками точечных целей вероятных противников и другие.
Значительное место принадлежит задачам маршрутизации в деятельности правоохранительных органов. Так по сути своей подразделения милиции общественной безопасности (МОБ) при выполнении целого ряда служебных задач связаны с посещением отдельных граждан по месту их жительства (деятельность участкового инспектора). Кроме того, оптимизация маршрутов патрульной службы всецело определяет эффективность такой службы на каждом из участков, поскольку оптимизируется продолжительность переходов (переездов) между узловыми точками маршрута. Существуют и другие области применения данного класса задач.
Постановка задачи. Пусть M - множество населенных пунктов, необходимых для посещения коммивояжерами, m - их численность. Множество и численность коммивояжеров H и h соответственно. Кроме того, можно считать известной инфраструктуру рассредоточения населенных пунктов, представленной в виде матрицы L=Ѕ lijЅ, i=, j=. При этомi=0 - пункт дислокации коммивояжеров (пункт начала движения). Требуется оптимальным образом разбить M на подмножества Ml и в каждом из них определить оптимальную перестановку Ul элементов Ml, l=, ml - численность Ml,M1M2...Ml...=M, еml=m. Другими словами, из множества населенных пунктов каждому коммивояжеру необходимо определить перечень населенных пунктов и оптимальный маршрут их посещения. В такой модели может быть принято множество ограничений и допущений, связанных с наличием и видами транспортных средств, с общим видом матрицы L, с учетом возврата коммивояжеров в исходный пункт и другие.
В общем случае, точное решение этой задачи зависит от ее размерности, определяемой, прежде всего, величиной m и некоторыми вспомогательными возможностями, связанными, прежде всего, с эффективностью разработанных алгоритмов и ЭВТ.
2. Разработка алгоритма маршрутизации
2.1 Разработка алгоритма маршрутизации трафика в MPLS-сети
Таблица маршрутизации может составляться двумя способами: статическим и динамическим. При статическом способе записи в таблице вводятся и изменяются вручную, это требует вмешательства администратора каждый раз, когда происходят изменения в топологии сети. Этот является наиболее стабильным и требующим минимум аппаратных ресурсов маршрутизатора для обслуживания таблицы. При динамической маршрутизации записи в таблице обновляются автоматически при помощи протоколов маршрутизации. При этом маршрутизатор строит таблицу оптимальных путей к сетям назначения на основе различных критериев. Критерии вычисления оптимальных маршрутов чаще всего зависят от протокола маршрутизации, а также задаются конфигурацией маршрутизатора. Однако, динамическая маршрутизацияоказывает дополнительную нагрузку на устройства, а высокая нестабильность сети может приводить к ситуациям, когда маршрутизаторы не успевают синхронизировать свои таблицы, что проводит к противоречивым сведениям о топологии сети в различных её частях и потере передаваемых данных. Сеть MPLS делится на две функционально различные области ? ядро и граничную область. Маршрутизаторы ядра занимаются только коммутацией. Все функции классификации пакетов, а также реализацию таких дополнительных сервисов, как фильтрация, явная маршрутизация, выравнивание нагрузки и управление трафиком, берут на себя граничные маршрутизаторы (LER, Label Edge Router). В результате интенсивные вычисления приходятся на граничную область, а высокопроизводительная коммутация выполняется в ядре, что позволяет оптимизировать конфигурацию устройств MPLS в зависимости от их местоположения в сети. Как и во всех технологиях, где используется концепция виртуального канала, в MPLS старое значение метки заменяется новым на каждом промежуточном узле.
Продвижение пакета вдоль пути коммутации меток происходит не на основе адреса назначения пакета IP и таблицы маршрутизации, а на основе значения метки и таблицы коммутации. Классом эквивалентного обслуживания (FEC, Forwarding Equivalency Class) ? называется группа пакетов третьего уровня, которые одинаково обслуживаются и пересылаются. Все пакеты, которые принадлежат определенному FEC, и которые отправлены из конкретного узла будут следовать одним и тем же путем (или в случае многомаршрутного протокола, они будут следовать через один и тот же набор путей, ассоциированный с FEC). При этом присвоение пакету определенного FEC делается только раз, когда пакет входит в сеть. В процессе вычисления маршрутов могут преследоваться различные цели, например предоставление требуемого качества услуг, в частности гарантированной ширины полосы пропускания. Численный анализ выявил недостатки алгоритмов, преследующих отдельно взятые цели и необходимость в глобальном решении, которое бы их объединяло. В данной работе предложено решение, объединяющее следующие цели: сокращение вероятности блокировки, минимизация стоимости сети и балансировка нагрузки.
При разработке алгоритмов маршрутизации часто преследуют одну или несколько из перечисленных ниже целей:
1. Оптимальность
2. Простота и низкие непроизводительные затраты
3. Живучесть и стабильность
4. Быстрая сходимость
5. Гибкость
Оптимальность
Оптимальность, вероятно, является самой общей целью разработки. Она характеризует способность алгоритма маршрутизации выбирать "наилучший" маршрут. Наилучший маршрут зависит от показателей и от "веса" этих показателей, используемых при проведении расчета. Например, алгоритм маршрутизации мог бы использовать несколько пересылок с определенной задержкой, но при расчете "вес" задержки может быть им оценен как очень значительный. Естественно, что протоколы маршрутизации дожны строгo определять свои алгоритмы расчета показателей.
Простота и низкие непроизводительные затраты
Алгоритмы маршрутизации разрабатываются как можно более простыми. Другими словами, алгоритм маршрутизации должен эффективно обеспечивать свои функциональные возможности, с мимимальными затратами программного обеспечения и коэффициентом использования. Особенно важна эффективность в том случае, когда программа, реализующая алгоритм маршрутизации, должна работать в компьютере с ограниченными физическими ресурсами.
Живучесть и стабильность
Алгоритмы маршрутизации должны обладать живучестью. Другими словми, они должны четко функционировать в случае неординарных или непредвиденных обстоятельств, таких как отказы аппаратуры, условия высокой нагрузки и некорректные реализации. Т.к. роутеры расположены в узловых точках сети, их отказ может вызвать значительные проблемы.
Часто наилучшими алгоритмами маршрутизации оказываются те, которые выдержали испытание временем и доказали свою надежность в различных условиях работы сети.
Быстрая сходимость
Алгоритмы маршрутизации должны быстро сходиться. Сходимость - это процесс соглашения между всеми роутерами по оптимальным маршрутам. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или ставновятся доступными, роутеры рассылают сообщения об обновлении маршрутизации. Сообщения об обновлении маршрутизации пронизывают сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая все роутеры придти к соглашению по этим маршрутам. Алгоритмы мааршрутизации, которые сходятся медленно, могут привести к образованию петель маршрутизации или выходам из строя сети.
На Рис. 2-3 изображена петля маршрутизации. В данном случае, в момент времени t1 к роутеру 1 прибывает пакет. Роутер 1 уже был обновлен и поэтому он знает, что оптимальный маршрут к пункту назначения требует, чтобы следующей остановкой был роутер 2. Поэтому роутер 1 пересылает пакет в роутер 2. Роутер 2 еще не был обновлен, поэтому он полагает, что следующей оптимальной пересылкой должен быть роутер 1.
Поэтому роутер 2 пересылает пакет обратно в роутер 1. Пакет будет продолжать скакать взад и вперед между двумя роутерами до тех пор, пока роутер 2 не получит корректировку маршрутизации, или пока число коммутаций данного пакета не превысит допустимого максимального числа.
Гибкость
Алгоритмы маршрутизации должны быть также гибкими. Другими словами, алгоритмы маршрутизации должны быстро и точно адаптироваться к разнообразным обстоятельствам в сети. Например, предположим, что сегмент сети отвергнут. Многие алгоритмы маршрутизации, после того как они узнают об этой проблеме, быстро выбирают следующий наилучший путь для всех маршрутов, которые обычно используют этот сегмент. Алгоритмы маршрутизации могут быть запрограммированы таким образом, чтобы они могли адаптироваться к изменениям полосы пропускания сети, размеров очереди к роутеру, величины задержки сети и других переменных.
При запуске приложения загружается главное окно с меню. Окно имеет следующий вид:
Рис. 2.1
Листинг программы «Меню»:Option Explicit
Данный алгоритм относится не к расчету маршрутов., а к методам борьбы с перегрузкой в памяти. Суть его заключается в том, что в виртуальный момент времени (такт) виртуально посылается первый байт пакета с линии А. Затем идет первый байт пакета линии В и т.д. Данная программа представляет собой моделирование работы алгоритма Блок-схема представлена под №2.1. Внешний вид программы следующий:
Рис. 2.2
От пользователя требуется ввести число байт для каждого пакета При нажатии кнопки «Расчет» будет выведено время завершения передачи для каждого пакета Рассмотрим код программы. Первоначально переменной ко1 целого типа присваивается сумма всех байт. Это необходимо сделать для организации цикла, т.е. эта переменная в дальнейшем будет служить счетчиком. Затем мы проверяем каждую линию, и если в ней имеется часть пакета, поочередно уменьшаем счетчики байтов соответствующих линий. В конце концов будет выведен результат, представляющий собой количество тактов, через которое пакет был полностью передан. Листинг программы представлен в приложении.
Блок-схема 2.1 Разработка алгоритма
Данный алгоритм представлен в программе в виде моделирования его работы.
2.2 Разработка алгоритма динамической маршрутизации на базе протокола OSPF
При рассмотрении принципов MPLS обсуждалась необходимость заполнения в маршрутизаторах LSR таблиц меток, используемых при маршрутизации пакетов по сети MPLS. Для этого в каждом из узлов сети с использованием протокола маршрутизации создается база топологической информации о сетевых маршрутах. Наряду с рассматриваемыми протоколами BGP4 и IS-IS, для этой цели может быть применен протокол маршрутизации по состояниям каналов OSPF (Open Shortest Path First -- "первым выбирается кратчайший путь"). Поскольку OSPF используется наиболее часто, рассмотрение протоколов маршрутизации для MPLS в начинается именно с него.
Протокол OSPF относится к протоколам внутреннего шлюза IGP (Interior Gateway Protocol). К этой категории принадлежат протоколы маршрутизации, обеспечивающие обмен информацией в пределах автономной системы AS (Autonomous Systemпредставляет собой сеть, находящуюся под единым административным управлением).
Метрики OSPF
В OSPF используется принцип контроля состояния канала (link-state protocol), а метрика представляет собой оценку эффективности связи в этом канале: чем меньше метрика, тем эффективнее организация связи. В простейшем случае метрика маршрута может равняться его длине в пересылках (hops), как это происходит в протоколе RIP. Но в общем случае значения метрики могут определяться в гораздо более широком диапазоне.
Метрика, оценивающая пропускную способность канала, определяется, например, компанией CISCO, как количество секунд, нужное для передачи 100 Мбит. Имеется следующая формула для вычисления метрики доставки информации через каналы сети OSPF:метрика = 108/скорость передачи в битах в секунду.
По этой формуле вычислены, например, следующие метрики:
· канал со скоростью 100 Мбит/с соответствует метрике 1;
· сеть Ethernet / 802.3 соответствует метрике 10;
· тракт Е1 2,048 Мбит/с соответствует метрике 48;
· тракт Т1 1,544 Мбит/с соответствует метрике 65;
· канал 64 Кбит/с соответствует метрике 1562;
· канал 56 Кбит/с соответствует метрике 1785;
· канал 19,2 Кбит/с соответствует метрике 5208;
· канал 9,6 Кбит/с соответствует метрике 10416.
Кроме того, протокол OSPF позволяет определить для любой сети значения метрики в зависимости от типа услуги ToS (Type ofService). Для каждой из метрик протокол OSPF строит отдельную таблицу маршрутизации. Чаще всего OSPF выбирает маршрут на основании полосы пропускания канала.
Загрузка канала представляет собой величину, которая изменяется в зависимости от использования канала, причем интенсивнаяэксплуатация канала повышает его загрузку, и поэтому при маршрутизации бывает целесообразно выбирать менее нагруженные каналы. Еще одна возможная метрика - задержка - определяет время в микросекундах, которое требуется маршрутизатору для обработки, установки в очередь и передачи пакетов.
В случае, когда имеется несколько маршрутов с одинаковым значением метрики, маршрутизаторы могут использовать для передачи пакетов все эти маршруты, обеспечивая балансировку нагрузки. Маршрутизатор OSPF помещает в таблицу маршрутизации все маршруты с одинаковыми значениями метрики, и балансировка нагрузки между маршрутами происходит автоматически. Стандартизованный порядок расчета метрик, оценивающих надежность, задержку и стоимость, пока не определен. Эти вопросы решаются администратором сети.
Итак, OSPF представляет собой протокол, основанный на контроле состояния каналов, распространяющий эту информацию и определяющий на ее основе маршруты наименьшей стоимости в заданной метрике. Именно с его помощью LSR отображает видимый ему граф домена сети MPLS, где для каждой пары смежных вершин графа (маршрутизаторов) указано ребро (канал), их соединяющее, и метрика этого ребра. Граф считается ориентированным, т.е. ребро, соединяющее LSR1 с LSR2, и ребро, соединяющее LSR2 с LSR1, могут быть разными, или это может быть одно и то же ребро, но с разными метриками.
Маршрутизатор, работающий по протоколу OSPF, выполняет последовательно три операции: определяет отношения соседства и смежности с другими маршрутизаторами, обменивается с ними OSPF -пакетами извещений LSA, формируя таким образом полную топологическую карту сети, а затем вычисляет дерево маршрутов, используя алгоритм "первым выбирается кратчайший путь" SPF(Shortest Path First), известный также по имени его создателя как алгоритм Дейкстры.
Для сети MPLS с помощью этого алгоритма протокол OSPF, основываясь на базе данных об условиях использования возможных связей, вычисляет кратчайшие пути между заданным LSR - вершиной графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершины графа сети MPLS указан список ребер, соединяющих ее со всеми другими вершинами этого графа по кратчайшему пути.
Быстрый рост числа компьютерных сетей, успехи в развитии оптоволоконных и беспроводных средств связи, сопровождаются непрерывной сменой сетевых технологий, направленной на повышения быстродействия и надежности сетей, возможности интегрированной передачи данных, голоса и видеоинформации. Реализация способов взаимодействия абонентов в компьютерной сети осуществляется с помощью строго формализованных правил и систем специальных процедур, называемых протоколам. Иерархически организованную совокупность протоколов называют стеком протоколов. В современных компьютерных сетях наибольшую популярность получил стек протоколов TCP/IP. Постановка задачи. В настоящее время наибольшее распространение получили алгоритмы динамической маршрутизации. Они обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации сети. Используя протоколы адаптивных алгоритмов, маршрутизаторы могут собирать информацию о топологии связей в сети и оперативно реагировать на все изменения конфигурации связей [1]. Целью данной статьи является разработка алгоритма динамической маршрутизации на базе протокола OSPF в корпоративных вычислительных сетях.
Современные адаптивные протоколы обмена информацией о маршрутах, в свою очередь, делятся на две группы, каждая из которых связана с одним из следующих типов алгоритмов:
- дистанционно-векторные алгоритмы (Distance Vector Algorithm, DVA);
- алгоритмы состояния каналов (Link State Algorithm, LSA). Протоколом, основанным на алгоритме состояния связей стека TCP/IP является протокол
OSPF (Open Shortest Path First) [2]. Протокол OSPF реализован в домене маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Выбор оптимального маршрута определяется по алгоритму Дейкстры. OSPF является протоколом внутреннегошлюза, используемым для маршрутизации внутри группы маршрутизаторов.
2.3 Разработка алгоритма дырявого ведра
Рис. 2.3
Та же самая идея применима к пакетам. Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро, то есть конечную внутреннюю очередь. Если пакет появляется в очереди, когда очередь полная, пакет игнорируется. Другими словами, если несколько процессов хоста пытаются послать пакеты, когда в очереди уже стоит максимально допустимое число пакетов, новый пакет игнорируется. Такой интерфейс может быть реализован как аппаратно, так и программно операционной системой хоста. Он был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра. По сути это не что иное, как однолинейная система массового обслуживания с постоянным временем обслуживания. Хосту разрешается посылать в сеть один пакет за один такт. Опять же, это может быть реализовано интерфейсной картой либо операционной системой. Этот механизм преобразует неравномерный поток пакетов от процессов пользователя в равномерный поток пакетов в сети, сглаживая пики и значительно снижая вероятность перегрузки. Когда размер всех пакетов одинаков (например, в ячейках ATM), этот алгоритм может применяться, как описано ранее. Однако при использовании пакетов переменного размера часто бывает лучше ограничивать количество байтов, переданных в сеть за такт, нежели передавать один пакет за такт. Так, если правилом установлена передача 1024 байт за тактовый интервал, то за этот период могут быть переданы в сеть либо один пакет размером 1024 байта, либо два пакета по 512 байт, либо четыре пакета по 256 байт и т. д. Если оставшееся количество байт меньше размера следующего пакета, следующий пакет должен ждать начала следующего такта.
Реализация исходного алгоритма дырявого ведра проста. Дырявое ведро состоит из конечной очереди. Когда прибывает пакет и в очереди есть место, пакет добавляется к очереди, в противном случае пакет игнорируется. Если очередь не пуста, то в течение каждого тактового интервала в сеть передается по одному пакету.
Алгоритм дырявого ведра со счетчиком байтов реализуется почти также. В каждом тактовом интервале значение счетчика устанавливается равным п. Если размер первого пакета в очереди меньше текущего значения счетчика, он передается, а значение счетчика уменьшается на его размер. Если значение счетчика еще достаточно велико, могут быть посланы и другие пакеты. Когда значение счетчика становится меньше размера следующего пакета в очереди, передача прекращается до следующего такта, после чего все начинается сначала, а остаток счетчика обнуляется. В качестве примера представьте, что компьютер может производить данные со скоростью 25 млн. байт в секунду (200 Мбит/с) и что сеть также работает на этой скорости. Однако маршрутизаторы могут поддерживать эту скорость передачи данных лишь на коротких интервалах (пока не заполнится их буферная память). В течение больших интервалов времени они могут обеспечить не более 2 млн. байт в секунду. Теперь предположим, что данные поступают пачками по 1 млн. байт, одна пачка продолжительностью 40 мс в каждую секунду. Чтобы уменьшить среднюю скорость до 2 Мбайт/с, можно воспользоваться алгоритмом дырявого ведра с выходной скоростью р = 2 Мбайт/с и емкостью С = 1 Мбайт. Это означает, что пачки до 1 Мбайта могут обрабатываться без потерь и что такие пачки будут передаваться в сеть за 500 мс независимо от того, как быстро они приходят. На рис. 5.29, а показан вход дырявого ведра, на который со скоростью 25 Мбайт/с поступает пачка в течение 40 мс. На рис. 5.29, б показан выход, через который данные проходят с постоянной скоростью 2 Мбайт/с в течение 500 мс.
Блок-схема алгоритма под №2 Рис. 2.4
Пользователю необходимо ввести следующие значения:
А) Число циклов моделирования - величина, необходимая для формирования циклов, т.е. счетчик.
Б) Интервалы появления пакетов - требуется ввести максимальное и минимальное значения интервалов времени между появлениями пакетов. Эти значения используются для генерирования случайного разброса значений в этих пределах.
В) Емкость маршрутизатора- иначе емкость ведра, максимальное число пакетов, которое может уместиться в буфере маршрутизатора
Г) Интервал передачи пакетов в сеть - с каким интервалом будут выходить пакеты.
В результате моделирования мы получаем:
А) Время моделирования - число виртуальных тактов, прошедших во время моделирования.
Б) Количество входных пакетов - сколько пакетов было сгенерировано.
В) Количество отправленных пакетов - сколько пакетов прошло через маршрутизатор.
Г) Количество не принятых пакетов - сколько пакетов маршрутизатор проигнорировал.
В программе была использована процедура СuntTimeе(). В ней производится подсчет времена. Затем проверяем, прошел интервал времени.
Блок-схема 2.2 Разработка алгоритма
2.4 Алгоритм выбора маршрута
Далее рассматриваемый алгоритм широко применяется в различных формах благодаря его простоте и понятности. Идея заключается в построении графа подсети, в котором каждый узел будет соответствовать маршрутизатору, а каждая дуга - линии связи (часто называемая связью). При выборе маршрута между двумя маршрутизаторами алгоритм просто находит кратчайший путь между ними на графе.
Концепция кратчайшего пути заслуживает некоторого пояснения Один из способов измерения длины пути состоит в подсчете количества транзитных участков. Однако помимо учета количества транзитных участков и физической длины линий, возможен учет и других параметров. Например, каждой дуге графа можно поставить в соответствие среднюю длину очереди и время задержки пересылки, определяемые каждый час с помощью передачи специального тестового пакета В таком графе кратчайший путь определяется как самый быстрый путь, а не путь с самого короткого длиной кабеля или путь, состоящий из минимального числа отдельных отрезков кабеля.
В наиболее общем случае параметры дуг графа являются функциями расстояния, пропускной способности, средней загруженности, стоимости связи, средней длины очереди, измеренной величины задержки и других факторов. Изменяя весовую функцию, алгоритм может вычислять кратчайший путь с учетом любого количества критериев в различных комбинациях.
Суть алгоритма заключается в следующем. Каждый узел помечается расстоянием до него от узла отправителя по лучшему известному пути. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, отражая лучшие пути. Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориентировочными Когда выясняется, что отметка соответствует кратчайшему возможному пути, она становится постоянной и в дальнейшем не изменяется.
Интернете под названием RIР, а также в ранних версиях сетей DECnet и сети IРХ корпорации Novе11. Маршрутизаторы сетей Арр1еТа1к и Cisсо используют улучшенные дистанционно-векторные протоколы.
Таблицы, с которыми работают маршрутизаторы, содержат записи о каждом маршрутизаторе подсети. Каждая запись состоит из двух частей: номера оптимальной линии для данного получателя и оценки расстояния или времени прохождения пакета.
Основная работа сетевого уровня заключается в выборе маршрута для пакетов от отправителя до получателя. В большинстве сетей пакетам приходится пройти через несколько маршрутизаторов. Единственным исключением являются широковещательные сети, но даже в них маршрутизация является важным вопросом, если отправитель и получатель находятся в разных сетях.
Алгоритмы, выбирающие маршруты, и используемые ими структуры данных являются главной задачей проектирования сетевого уровня.
Алгоритм выбора маршрута является частью программного обеспечения сетевого уровня, ответственной за выбор выходной линии, по которой следует отправить пришедший пакет. Если подсеть использует дейтаграммную службу, выбор маршрута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, маршрут выбирается только при создании нового виртуального канала После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса пользователя.
Подобные документы
Основные положения, связанные с маршрутизацией компьютерных сетей и её видами, протоколами маршрутизации и их разновидностями, алгоритмами маршрутизации, их классификацией, типами и свойствами. Разработка программы и моделирование компьютерной сети.
курсовая работа [1,8 M], добавлен 04.11.2012Разработка и использование протокола маршрутизации RIP в небольших и сравнительно однородных сетях. Причины неустойчивой работы по протоколу, их устранение. Применения протокола Hello для обнаружения соседей и установления с ними отношений смежности.
курсовая работа [264,0 K], добавлен 06.06.2009Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Построение алгоритмов поиска кратчайшего пути маршрутизации, расчёт пути с минимальным количеством переходов. Характеристики протокола RIP и построение маршрутных таблиц.
курсовая работа [74,1 K], добавлен 26.08.2010Описание систем управления процессами маршрутизации пакетов, передаваемых через компьютерную сеть. Изучение методов теории выбора кратчайших путей. Разработка программы маршрутизации данных и определение кратчайших путей их маршрутов методом Дейкстры.
курсовая работа [495,7 K], добавлен 24.06.2013Анализ проблемы обеспечения информационной безопасности при работе в сетях; обоснование необходимости разработки алгоритмов безопасной маршрутизации пакетов сообщений в глобальной информационной сети. Алгоритмизация задач безопасной маршрутизации пакетов.
дипломная работа [1,0 M], добавлен 21.12.2012Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ.
курсовая работа [1,2 M], добавлен 16.05.2015Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.
курсовая работа [334,1 K], добавлен 20.01.2013Описание широкополосных сетей интегрального обслуживания, классификация алгоритмов маршрутизации. Реализация логического способа формирования плана распределения информации в схеме маршрутизатора. Математическая модель и метод анализа маршрутизации.
дипломная работа [1,1 M], добавлен 31.10.2010Рассмотрение понятия обмена информацией в сети. Изучение протоколов динамической маршрутизации различных комбинаций соединений Ethernet и Serial. Определение зависимости прохождения сигнала от типа порта и кабеля. Применение данных типов маршрутизации.
курсовая работа [1,3 M], добавлен 28.05.2014Установка VirtualBox. Создание двух виртуальных машин с операционной системой CentOS. Настройка сетевых интерфейсов в режиме bridgeс и хоста как маршрутизатора для сети. Установка www-сервера. Настройка динамической маршрутизации по протоколу RIP.
курсовая работа [807,5 K], добавлен 14.07.2012
