Другие статьи

Цель нашей работы - изучение аминокислотного и минерального состава травы чертополоха поникшего
2010

Слово «этика» произошло от греческого «ethos», что в переводе означает обычай, нрав. Нравы и обычаи наших предков и составляли их нравственность, общепринятые нормы поведения.
2010

Артериальная гипертензия (АГ) является важнейшей медико-социальной проблемой. У 30% взрослого населения развитых стран мира определяется повышенный уровень артериального давления (АД) и у 12-15 % - наблюдается стойкая артериальная гипертензия
2010

Целью нашего исследования явилось определение эффективности применения препарата «Гинолакт» для лечения ВД у беременных.
2010

Целью нашего исследования явилось изучение эффективности и безопасности препарата лазолван 30мг у амбулаторных больных с ХОБЛ.
2010

Деформирующий остеоартроз (ДОА) в настоящее время является наиболее распространенным дегенеративно-дистрофическим заболеванием суставов, которым страдают не менее 20% населения земного шара.
2010

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

Для более объективного подтверждения мембранно-стабилизирующего влияния карбамезапина и ламиктала нами оценивались перекисная и механическая стойкости эритроцитов у больных эпилепсией
2010

Нами было проведено клинико-нейропсихологическое обследование 250 больных с ХИСФ (работающих в фосфорном производстве Каратау-Жамбылской биогеохимической провинции)
2010


C использованием разработанных алгоритмов и моделей был произведен анализ ситуации в системе здравоохранения биогеохимической провинции. Рассчитаны интегрированные показатели здоровья
2010

Специфические особенности Каратау-Жамбылской биогеохимической провинции связаны с производством фосфорных минеральных удобрений.
2010

Некоторый анализ алгоритмов маршрутизации

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

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

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

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

Общая постановка задачи маршрутизации. Маршрутизация может быть представлена в следующем виде. Пусть дан направленный взвешенный граф G=(V,E), в котором каждый узел из множества представляет собой устройство, обрабатывающее и передающее данные, а каждое ребро из множества является линией связи. Основной задачей алгоритмов маршрутизации является передача данных из узла источника в узел приемник, максимизируя при этом производительность сети. При моделировании алгоритмов маршрутизации возникают две проблемы, затрудняющие процесс создания системы. Во-первых, поток данных не является статическим, вовторых, он имеет стохастический характер.

Алгоритмы маршрутизации должны выполнять следующие функции:

  1. сбор, организация и распределение информации о созданном пользователем трафике и состояниях сети;
  2. использование собранной информации для создания подходящих маршрутов, максимизирующих производительность объектов;
  3. направление трафика пользователя по выбранному маршруту.

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

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

Основные характеристики задачи маршрутизации

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

Маршрутизация взаимодействует с управлением потоками в определении характеристик посредством механизма обратной связи, представленном на рис. 1.

Рис. 1. Взаимодействие между маршрутизацией и управлением потока с помощью механизма обратной связи

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

Рис. 2. Кривые зависимости задержки от пропускной способности для хорошей и плохой маршрутизации

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

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

Проектировщик выбирает алгоритм маршрутизации по критерию оптимальности. Оптимальность включает в себе следующие свойства:

  • Простота – алгоритмы маршрутизации должны быть как можно более простыми;
  • Надежность – алгоритм маршрутизации должен уметь справляться с изменениями сети без необходимости прекращения всех задач на всех хостах и перезагрузки сети при выходе из строя аппаратуры;
  • Стабильность и устойчивость – алгоритмы маршрутизации должны четко функционировать в случае неординарных и непредвиденных обстоятельств, таких, как отказы аппаратуры, высокие уровни загруженности узлов и каналов связи;
  • Быстрая сходимость – под этим свойством понимаем процесс соглашения между оптимальным маршрутом и всеми маршрутизаторами. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, маршрутизаторы рассылают сообщения об обновлении маршрутизации. Это сообщения пронизывает сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая всех маршрутизаторов принять определенный маршрут. Алгоритмы маршрутизации при низкой сходимости могут привести к образованию петель маршрутизации или выходам из строя сети;
  • Гибкость – алгоритмы маршрутизации должны быстро и точно адаптироваться к разнобразным обстоятельствам в сети;
  • Справедливость – алгоритмы маршрутизации должны равномерно распределять трафики, это поможет снизить среднее время задержки в сети.

Алгоритмы маршрутизации можно классифицировать следующим образом [2]:

  • централизованные и распределенные;
  • статические и динамические (адаптивные).

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

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

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

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

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

Другой способ классификации алгоритмов маршрутизации имеет вид [2]:

  • минимальная маршрутизация и неминимальная маршрутизация;
  • оптимальная маршрутизация и маршрутизация, определяющая кратчайший путь.

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

Оптимальная маршрутизация имеет доступ ко всей сети и ко всем ее объектам для оптимизации функции всех отдельных потоков линий связи (обычно эта функция является суммой стоимостей путей назначенных в соответствии со средними задержками пакетов).

Маршрутизация, определяющая кратчайшие пути, объективно определяет кратчайший путь (минимальную стоимость) между двумя узлами. Учитывая содержание в таблицах маршрутизации различной информации, алгоритмы нахождения кратчайших путей могут быть поделены на два класса: дистанционно-векторные и алгоритмы состояния связи.

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

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

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

 

ЛИТЕРАТУРА

  1. Столлингс В. Современные компьютерные сети. СПб: Питер, 2003.
  2. Таненбаум Э. Компьютерные сети. - СПб.Питер, 2003.
  3. Бертсекас Д.Галлагер Р. Сети передачи данных: Пер. с англ. М.: Мир, 1989.
  4. Амато В. Основы организации сетей Cisco, том 2. М., 2004.

Разделы знаний

Архитектура

Научные статьи по Архитектуре

Биология

Научные статьи по биологии 

Военное дело

Научные статьи по военному делу

Востоковедение

Научные статьи по востоковедению

География

Научные статьи по географии

Журналистика

Научные статьи по журналистике

Инженерное дело

Научные статьи по инженерному делу

Информатика

Научные статьи по информатике

История

Научные статьи по истории, историографии, источниковедению, международным отношениям и пр.

Культурология

Научные статьи по культурологии

Литература

Литература. Литературоведение. Анализ произведений русской, казахской и зарубежной литературы. В данном разделе вы можете найти анализ рассказов Мухтара Ауэзова, описание творческой деятельности Уильяма Шекспира, анализ взглядов исследователей детского фольклора.  

Математика

Научные статьи о математике

Медицина

Научные статьи о медицине Казахстана

Международные отношения

Научные статьи посвященные международным отношениям

Педагогика

Научные статьи по педагогике, воспитанию, образованию

Политика

Научные статьи посвященные политике

Политология

Научные статьи по дисциплине Политология опубликованные в Казахстанских научных журналах

Психология

В разделе "Психология" вы найдете публикации, статьи и доклады по научной и практической психологии, опубликованные в научных журналах и сборниках статей Казахстана. В своих работах авторы делают обзоры теорий различных психологических направлений и школ, описывают результаты исследований, приводят примеры методик и техник диагностики, а также дают свои рекомендации в различных вопросах психологии человека. Этот раздел подойдет для тех, кто интересуется последними исследованиями в области научной психологии. Здесь вы найдете материалы по психологии личности, психологии разивития, социальной и возрастной психологии и другим отраслям психологии.  

Религиоведение

Научные статьи по дисциплине Религиоведение опубликованные в Казахстанских научных журналах

Сельское хозяйство

Научные статьи по дисциплине Сельское хозяйство опубликованные в Казахстанских научных журналах

Социология

Научные статьи по дисциплине Социология опубликованные в Казахстанских научных журналах

Технические науки

Научные статьи по техническим наукам опубликованные в Казахстанских научных журналах

Физика

Научные статьи по дисциплине Физика опубликованные в Казахстанских научных журналах

Физическая культура

Научные статьи по дисциплине Физическая культура опубликованные в Казахстанских научных журналах

Филология

Научные статьи по дисциплине Филология опубликованные в Казахстанских научных журналах

Философия

Научные статьи по дисциплине Философия опубликованные в Казахстанских научных журналах

Химия

Научные статьи по дисциплине Химия опубликованные в Казахстанских научных журналах

Экология

Данный раздел посвящен экологии человека. Здесь вы найдете статьи и доклады об экологических проблемах в Казахстане, охране природы и защите окружающей среды, опубликованные в научных журналах и сборниках статей Казахстана. Авторы рассматривают такие вопросы экологии, как последствия испытаний на Чернобыльском и Семипалатинском полигонах, "зеленая экономика", экологическая безопасность продуктов питания, питьевая вода и природные ресурсы Казахстана. Раздел будет полезен тем, кто интересуется современным состоянием экологии Казахстана, а также последними разработками ученых в данном направлении науки.  

Экономика

Научные статьи по экономике, менеджменту, маркетингу, бухгалтерскому учету, аудиту, оценке недвижимости и пр.

Этнология

Научные статьи по Этнологии опубликованные в Казахстане

Юриспруденция

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