Способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений
Владельцы патента RU 2457628:
Открытое акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" (RU)
Настоящее изобретение относится к области сетевых информационных технологий. Технический результат изобретения заключается в более эффективном использовании ресурсов каналов связи сети связи, сокращении времени передачи сообщений. Отличием способа динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений является то, что в узле связи, являющимся источником сообщения, анализируют качество каналов связи, составляющих одномерные маршруты передачи, оценивают пропускную способность каналов связи, затем на основании пропускной способности каналов связи получают пропускную способность одномерных маршрутов передачи, из одномерных маршрутов передачи формируют многомерный маршрут передачи сообщения, включая в него сначала одномерные маршруты передачи с наибольшей пропускной способностью, затем одномерные маршруты передачи с меньшей пропускной способностью, далее оценивают вероятности доведения пакетов по одномерным маршрутам передачи, а всего сообщения - по многомерному маршруту передачи, и при величине вероятности доведения сообщения по многомерному маршруту передачи менее заданного значения, перераспределяют пакеты по одномерным маршрутам передачи, оптимизируя вероятность доведения всего сообщения по многомерному маршруту передачи и далее передают сообщение по многомерному маршруту передачи. 3 з.п. ф-лы.
Изобретение относится к области сетевых информационных технологий и может быть использовано для динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений.
В нестационарной сети связи качество каналов связи может изменяться, что обусловлено динамикой помеховой обстановки, условиями распространения сигнала, дальностью передачи в случае мобильных узлов сети связи и многими другими причинами. Причем вероятность доведения сообщения в некоторых каналах связи может стать менее предельно допустимой величины. В этом случае для обеспечения заданной вероятности доведения сообщений изменяют параметры передачи в каналах сети связи: мощность передачи, скорость передачи, вид модуляции, сигнально-кодовую конструкцию. Одним из эффективных способов повышения вероятности доведения сообщений в сети связи также является перераспределение информационной нагрузки каналов сети связи или сетевого графика путем динамической или адаптивной маршрутизации в зависимости от качества каналов связи. При этом суммарный трафик сетевого обмена во многих случаях может оставаться неизменным, а уменьшение графика сетевого обмена в каналах связи низкого качества осуществляют за счет увеличения графика в других каналах связи более высокого качества. Такой способ не меняет структуру данных, передаваемых в сети связи, является наиболее простым и экономичным для обеспечения заданной вероятности доведения сообщений и реализуется в многомерной пакетной сети связи на уровне устройств маршрутизации и коммутации пакетов.
Будем считать одномерным маршрутом передачи совокупность последовательно соединенных виртуальных каналов связи в соединении точка-точка между узлом связи, являющимся источником и узлом связи - получателем сообщений. Множество параллельно соединенных независимых одномерных маршрутов, по которым передают пакеты, составляющие сообщение, называют многомерным маршрутом передачи сообщения. Вслед за изменением качества одномерного маршрута устанавливают информационную нагрузку этого маршрута. Качество одномерного маршрута определяют по качеству входящих в одномерный маршрут каналов связи, например по качеству наихудшего канала связи одномерного маршрута передачи. В случае ухудшения качества одномерного маршрута число пакетов, направляемых устройством маршрутизации для передачи по одномерному маршруту, уменьшается до величины, обеспечивающей заданную вероятность доведения сообщений. При улучшении качества одномерного маршрута количество пакетов, передаваемых по одномерному каналу, может быть увеличено. Предлагаемый способ перераспределяет информационную нагрузку между наиболее «быстрыми» одномерными маршрутами передачи пакетов сообщения и обеспечивает тем самым наименьшее время передачи сообщения в многомерном маршруте передачи сети связи при вероятности доведения сообщений не менее заданной величины. Кроме того, сообщения могут иметь различную длину, и для обеспечения требуемой вероятности доведения всего сообщения пакеты различных по длине сообщений должны доводиться с различной вероятностью, что учитывают при выборе одномерных маршрутов передачи.
Известен способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений, в соответствии с которым в каждом из узлов связи осуществляют контроль за наличием или выходом из строя каналов сети связи и величиной их информационной загрузки. При отказе каналов или при информационной загрузке каналов, составляющих одномерный маршрут передачи, выше предельно допустимой величины, обеспечивающей доведение сообщений с заданной вероятностью, выполняют коррекцию таблиц маршрутизации узла связи, и пакеты, которые должны передаваться по этим одномерным маршрутам, направляются узлом связи для передачи по другим одномерным маршрутам согласно таблице маршрутизации. При восстановлении каналов или уменьшении их информационной загрузки осуществляют коррекцию таблицы маршрутизации узла связи, и пакеты, передаваемые по другим одномерным маршрутам, направляются узлом связи для передачи по восстановленным, одномерным маршрутам согласно таблицам маршрутизации (Протоколы информационно-вычислительных сетей. Справочник. Под ред. И.А.Мизина, А.П.Кулешова. - М. Радио и связь, 1990, стр.197-203).
Недостатком этого способа является чрезмерно большое время доведения сообщений, обусловленное тем, что в узле связи, представляющем собой источник сообщения, при выборе многомерного маршрута передачи сообщения учитывают только наличие или выход из строя одномерных маршрутов передачи, но не учитывают величину их качества.
Известен также способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений, в соответствии с которым в каждом из узлов связи осуществляют контроль за качеством каналов сети связи и величиной их сетевого графика. При качестве каналов ниже допустимой величины или при сетевом графике выше предельно допустимой величины осуществляют коррекцию таблиц маршрутизации узла связи, и пакеты, которые должны передаваться по одномерным маршрутам передачи, направляются узлом связи для передачи по другим одномерным маршрутам передачи согласно таблице маршрутизации. При улучшении качества каналов или при снижении их сетевого графика осуществляют коррекцию таблиц маршрутизации узла связи, и пакеты, передаваемые по другим одномерным маршрутам передачи, направляются узлом связи для передачи по восстановленным одномерным маршрутам передачи согласно таблицам маршрутизации (Стен Шатт. Мир компьютерных сетей: Пер. с англ. - К.: BHV, 1996, стр.95-98).
Недостатком этого способа также является большое время доведения сообщения при невысокой вероятности доведения сообщения, обусловленное тем, что в узле связи при выборе маршрута передачи не учитывают длину сообщений и то, что пакеты различных по длине сообщений должны доводиться с различной вероятностью.
Наиболее близким к предлагаемому способу (прототип) является способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений, в соответствии с которым в фазе установления соединения в узле связи, являющимся источником сообщения, измеряют длину сообщения, разбивают сообщение на пакеты, подсчитывают число полученных пакетов, анализируют пропускную способность одномерных маршрутов передачи, входящих в многомерный маршрут передачи, соединяющий источник и получателя сообщения, полученные пакеты передают по нескольким параллельным одномерным маршрутам передачи, имеющим максимальную пропускную способность в соответствии с таблицей маршрутизации с указанием промежуточных маршрутизаторов, и по каждому одномерному маршруту передачи осуществляют оптимальный режим коммутации в соответствии с длиной передаваемого сообщения (Орехов С.Е., Кузнецов Г.В., Анисимова Е.Г. и другие. Способ многомерной гибридной коммутации коммутации и адаптивной маршрутизации пакетов сообщений. Патент РФ №2416170, МПК H04L 12/64, опубл. 10.04.2011).
Недостаток этого способа заключается в увеличении времени передачи сообщения и снижении вероятности доведения сообщения из-за того, что не учитывают качество многомерного маршрута передачи сообщения в зависимости от качества составляющих одномерных маршрутов передачи, а также не учитывают влияние длины сообщения на вероятность доведения сообщения.
Цель изобретения - сокращение времени передачи сообщения при вероятности доведения сообщений в сети связи, не превышающей заданного значения, за счет того, что при выборе многомерных маршрутов передачи пакетов сообщения учитывают не только пропускную способность, но и качество одномерных маршрутов передачи, а также учитывают, что пакеты более длинных сообщений должны доводиться с большей вероятностью, чем пакеты коротких сообщений.
Для достижения цели предложен способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений, в соответствии с которым в фазе установления соединения в узле связи, являющимся источником сообщения, измеряют длину сообщения, разбивают сообщение на пакеты, подсчитывают число полученных пакетов, анализируют пропускную способность одномерных маршрутов передачи, входящих в многомерный маршрут передачи, соединяющий источник и получателя сообщения, полученные пакеты передают по нескольким параллельным одномерным маршрутам передачи, имеющим максимальную пропускную способность в соответствии с таблицей маршрутизации с указанием промежуточных маршрутизаторов и по каждому одномерному маршруту передачи осуществляют оптимальный режим коммутации в соответствии с длиной передаваемого сообщения. Новым является то, что в узле связи, являющимся источником сообщения, анализируют качество каналов связи, составляющих одномерные маршруты передачи, в зависимости от качества каналов связи и использованной для передачи сообщения полосы частот оценивают пропускную способность каналов связи, затем на основании пропускной способности каналов связи определяют пропускную способность одномерных маршрутов передачи, из одномерных маршрутов передачи формируют многомерный маршрут передачи всего сообщения, включая в него сначала одномерные маршруты передачи с наибольшей пропускной способностью, затем - одномерные маршруты передачи с меньшей, но следующей по величине пропускной способностью и так до тех пор, пока пропускная способность многомерного маршрута передачи не обеспечит передачу всего сообщения заданной длины, с учетом минимизации общего времени доведения сообщения путем последовательной передачи нескольких пакетов по одномерным маршрутам передачи с наибольшей пропускной способностью, далее оценивают вероятности доведения пакетов по одномерным маршрутам передачи, а всего сообщения - по многомерному маршруту передачи, и при величине доведения сообщения по многомерному маршруту передачи менее заданного значения перераспределяют пакеты по одномерным маршрутам передачи, оптимизируя отклонение вероятности доведения сообщения по многомерному маршруту передачи от заданной величины, и далее передают сообщение по многомерному маршруту передачи. Причем качество каналов связи сети связи определяют по результатам передачи пакетов с учетом квитирования, пропускную способность одномерных маршрутов передачи вычисляют для независимых последовательно соединенных каналов связи, образующих одномерный маршрут передачи в соединении точка-точка от узла связи, являющегося источником, и до узла связи, который является получателем сообщения, общее число которых ограничено предельно допустимым временем доведения сообщения. При этом пропускную способность многомерного маршрута передачи оценивают для независимых параллельно соединенных одномерных маршрутов передачи сообщений, которые упорядочивают в таблице маршрутизации узла связи по величине пропускной способности, начиная с одномерных маршрутов передачи, свободных от передачи сообщений с наибольшей пропускной способностью, и заканчивая одномерным маршрутом передачи, занятым передачей сообщений с наименьшей пропускной способностью. Причем вероятность доведения пакета по одномерному маршруту передачи определяется для последовательно соединенных независимых каналов связи, составляющих данный одномерный маршрут передачи.
Предлагаемый способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений реализуется следующим образом.
В сети связи узлы связи осуществляют непрерывный контроль качества каналов связи, связанных с данным узлом. Контроль качества канала связи выполняют по результатам передачи и приема пакетов сообщений с учетом их квитирования. При приеме пакетов сообщений узел связи, являющийся получателем этого пакета, вычисляет контрольную сумму пакета. В случае определения правильной контрольной суммы на передающий узел связи отправляется квитанция. По результатам получения квитанций на переданные по данному каналу связи пакеты в узле связи определяется частота правильного приема пакетов q, равная отношению числа правильно принятых пакетов m к общему числу переданных пакетов n
Эта величина позволяет приближенно оценить среднюю вероятность ошибки на бит в канале связи p
где k - длина пакета, выраженная в битах.
Средняя вероятность ошибки на бит в канале связи или коэффициент ошибок является основной характеристикой, определяющей качество канала связи. Затем в узлах связи в зависимости от качества каналов связи и полосы пропускания канала оценивают пропускную способность каналов связи. Для этого сначала определяют отношение сигнал/шум канала связи, которое соответствует качеству каналу связи. Средняя вероятность ошибки на бит в зависимости от отношения сигнал-шум для канала с АБГШ (аддитивным белым гауссовским шумом) при ОФМ-2 (однократной относительной фазовой модуляции) записывают в виде
где 
- отношение сигнал-шум в дБ,
а 
- интеграл вероятности.
Обращение формулы (3) позволяет определить зависимость отношения сигнал/шум от средней вероятности ошибки на бит в канале связи. К сожалению, получить явное выражение для отношения сигнал/шум в зависимости от средней вероятности ошибки на бит в канале связи из формулы (3) сложно. Однако расчет отношения сигнал/шум от средней вероятности ошибки на бит в канале связи в численном виде, например в виде таблицы, не представляет труда. Необходимые для расчета таблицы интеграла вероятностей можно найти в математическом справочнике (Справочник по специальным функциям. Под редакцией М.Абрамовица, И.Стиган, М., Из-во Физ.-мат. литературы, 1979, стр.131-136).
Оценку пропускной способности канала связи С теперь можно получить по формуле Шеннона. Пропускная способность канала зависит от ширины полосы пропускания канала Fn и отношение сигнал/шум и выражается в виде
Пропускная способность канала связи определяет время передачи (оперативность) и вероятность доведения сообщений. Таким образом, в узлах связи сети связи будет информация о пропускных способностях каналов сети связи. В узлах связи сети связи составляется таблица маршрутизации, содержащая сведения об одномерных маршрутах передачи до остальных узлов связи сети связи.
Начальное заполнение таблицы маршрутизации может выполняться, например, по протоколу маршрутизации Беллмана-Форда, который для стационарной сети связи позволяет формировать таблицу маршрутизации с кратчайшими путями, то есть с минимальным числом переприемов пакетов сообщений в каждом одномерном маршруте передачи [Кульгин М.В. Коммутация и маршрутизация IP/IPX-трафика. - М.: КомпьютерПресс, 1998. с 150-166]. Начальное заполнение таблицы маршрутизации, так же как полный ее перерасчет, выполняют только при вводе сети в эксплуатацию или при смене режимов работы сети связи, сопровождающейся существенным изменением состояния сети связи. В остальных случаях выполняют дополнительную итеративную коррекцию таблиц маршрутизации, которая требует существенно меньшего объема вычислений и передачи меньшего объема служебной информации по каналам связи.
В таблице маршрутизации узла связи хранится информация об одномерных маршрутах доведения пакета сообщения от данного узла связи - источника пакета до узла связи - получателя пакета. Пропускную способность одномерных маршрутов передачи вычисляют для независимых последовательно соединенных каналов связи, образующих одномерный маршрут в соединении точка-точка от узла связи, являющегося источником и до узла связи, который является получателем сообщения, общее число которых ограничено предельно допустимым временем доведения сообщения. Пропускная способность одномерного маршрута равна минимальной пропускной способности входящих в этот маршрут каналов связи. Таблица маршрутизации по каждому одномерному маршруту передачи содержит следующие поля:
1) адрес узла связи-получателя пакета,
2) количество переходов к узлу связи - получателю пакета и последовательность адресов промежуточных узлов связи,
3) метрика одномерного маршрута передачи, определяемая пропускной способностью этого маршрута,
4) таймер времени высвобождения канала связи до первого узла связи на пути к узлу связи - получателю пакета.
В узле связи известно текущее состояние канала связи, соединенного с первым узлом связи на пути к узлу - получателю пакета: занят он или свободен. Таймер времени показывает время высвобождения канала связи, если он занят. Одномерные маршруты передачи в таблице маршрутизации узла связи упорядочивают по пропускной способности, с учетом занятости маршрутов, то есть по пунктам 3 и 4 таблицы маршрутизации узла связи.
Пропускная способность одномерного маршрута определяется наименьшей пропускной способностью канала связи, который входит в данный одномерный маршрут. При формировании многомерных маршрутов сначала выбирают одномерные маршруты передачи, свободные от передачи сообщений, с наибольшей пропускной способностью, а заканчивают одномерными маршрутами передачи, занятыми передачей сообщений с наименьшей пропускной способностью.
Многомерный маршрут передачи пакетов сообщения формируют в фазе установления соединения. Сначала разбивают сообщение на пакеты определенной длины и подсчитывают число полученных пакетов. Затем, согласно таблице маршрутизации, для каждого пакета сообщения определяют одномерные маршруты передачи в последовательности их расположения в таблице маршрутизации узла связи, начиная с одномерных маршрутов передачи с наибольшей пропускной способностью. В результате получают многомерный маршрут передачи пакетов сообщения. Пропускную способность передачи многомерного маршрута передачи оценивают для независимых параллельно соединенных одномерных маршрутов передачи в виде суммы пропускных способностей для выбранных одномерных маршрутов передачи. Передачу пакета сопровождают служебной информацией об адресе узла - получателя пакета, который позволяет каждому узлу связи одномерного маршрута передачи, получив пакет сообщения, определить дальнейший маршрут передачи пакета согласно таблице маршрутизации данного узла связи. От длины сообщения, то есть количества пакетов в сообщении, зависит количество одномерных маршрутов передачи, первоначально выбранных для формирования многомерного маршрута передачи.
Основным вероятностно-временным требованием к передаче сообщений является доведение сообщения в минимальное время с вероятностью доведения не менее заданной величины. Таким образом, решается задача двухмерной оптимизации: минимизация по времени доведения и по отклонению вероятности доведения от заданной величины.
Сначала будем выполнять оптимизацию полученного многомерного маршрута передачи с точки зрения минимизации времени передачи сообщения. Время передачи T по многомерному маршруту передачи обратно пропорционально пропускной способности С этого маршрута передачи
где γ - некоторая постоянная величина.
Оценим время передачи всего сообщения по многомерному маршруту передачи в предположении, что пакет, передаваемый по одномерному маршруту передачи с наименьшей пропускной способностью, передают по маршруту с наибольшей пропускной способностью. Если время передачи сообщения, согласно формуле (5), при данном предположении сократилось, то одномерный маршрут передачи с наименьшей пропускной способностью исключают из многомерного маршрута передачи, иначе при увеличении времени передачи сообщения процедура оптимизации завершается. Затем делают попытку исключения следующего одномерного маршрута передачи с наименьшей пропускной способностью и так далее. Формирование многомерного маршрута заканчивают, когда время передачи сообщения перестанет сокращаться и все пакеты будут распределены между одномерными маршрутами передачи.
Теперь будем оптимизировать отклонение, вероятности доведения от заданной величины. Для этого сначала оценивают вероятности доведения пакетов по одномерным маршрутам передачи, а всего сообщения - по многомерному маршруту передачи. Вероятность доведения пакетов Qi по i-му одномерному маршруту равна
где r - количество пакетов, передаваемых i-му одномерному маршруту.
Вероятность доведения сообщения Q по многомерному маршруту передачи
Если вероятность доведения сообщения по многомерному маршруту передачи менее заданного значения, перераспределяют пакеты по одномерным маршрутам передачи, оптимизируя вероятность доведения всего сообщения по многомерному маршруту передачи. Оптимизацию выполняют следующим образом. Сначала исключают из многомерного маршрута передачи одномерный маршрут передачи с минимальной величиной вероятности доведения сообщения, а его пакет передают по одномерному маршруту с максимальной величиной вероятности доведения сообщения. Оценивают вероятность доведения сообщения, с использованием формул (6) и (7), по сформированному многомерному маршруту передачи. Если получившаяся вероятность доведения сообщения по многомерному маршруту передачи увеличилась, но осталась менее заданного значения, процедура оптимизации продолжается для следующего одномерного маршрута с максимальной величиной вероятности доведения сообщения, иначе при уменьшении вероятности доведения сообщения по многомерному маршруту передачи процедура заканчивается. Если в результате процедуры оптимизации не удалось достигнуть заданной вероятности доведения сообщения, передача сообщения по каналам этой сети связи с заданными вероятностно-временными характеристиками становится невозможной.
В предлагаемом изобретении за счет формирования многомерного маршрута передачи сообщения на основании одномерных маршрутов передачи пакетов, пропускные способности и качество которых имеют максимальное значение, обеспечивается минимальное время передачи всего сообщения при обеспечении вероятности доведения сообщения не менее заданной величины. Это позволяет своевременно передавать сообщения с заданной вероятностью доведения, независимо от их длины. Упорядочивание одномерных маршрутов передачи в таблице маршрутизации узла связи по пропускной способности позволяет существенно сократить количество операций при формировании многомерных маршрутов передачи сообщения и уменьшить сложность реализации способа.
Достигаемым техническим результатом способа динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений является более эффективное использование ресурсов каналов связи сети связи, сокращение времени доведения сообщения при вероятности доведения сообщения не менее заданной величины и уменьшение сложности его реализации.
1. Способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений, заключающийся в том, что в фазе установления соединения в узле связи, являющимся источником сообщения, измеряют длину сообщения, разбивают сообщение на пакеты, подсчитывают число полученных пакетов, анализируют пропускную способность одномерных маршрутов передачи, входящих в многомерный маршрут передачи, соединяющий источник и получателя сообщения, полученные пакеты передают по нескольким параллельным одномерным маршрутам передачи, имеющим максимальную пропускную способность в соответствии с таблицей маршрутизации с указанием промежуточных маршрутизаторов, и по каждому одномерному маршруту передачи осуществляют оптимальный режим коммутации в соответствии с длиной передаваемого сообщения, отличающийся тем, что в узле связи, являющимся источником сообщения, анализируют качество каналов связи, составляющих одномерные маршруты передачи, в зависимости от качества каналов связи и использованной для передачи сообщения полосы частот, оценивают пропускную способность каналов связи, затем на основании пропускной способности каналов связи, получают пропускную способность одномерных маршрутов передачи, из одномерных маршрутов передачи формируют многомерный маршрут передачи сообщения, включая в него сначала одномерные маршруты передачи с наибольшей пропускной способностью, затем - одномерные маршруты передачи с меньшей следующей по величине пропускной способностью и так до тех пор, пока пропускная способность многомерного маршрута передачи не обеспечит передачу всего сообщения заданной длины, с учетом минимизации общего времени доведения сообщения при последовательной передаче нескольких пакетов по одномерным маршрутам передачи с наибольшей пропускной способностью, далее оценивают вероятности доведения пакетов по одномерным маршрутам передачи, а всего сообщения - по многомерному маршруту передачи, и при величине вероятности доведения сообщения по многомерному маршруту передачи менее заданного значения, перераспределяют пакеты по одномерным маршрутам передачи, оптимизируя вероятность доведения сообщения по многомерному маршруту передачи, и далее передают сообщение по многомерному маршруту передачи.
2. Способ по п.1, отличающийся тем, что качество каналов связи определяют по результатам передачи пакетов с учетом их квитирования, пропускную способность одномерных маршрутов передачи вычисляют для независимых последовательно соединенных каналов связи, образующих одномерный маршрут передачи в соединении точка-точка от узла связи, являющегося источником, и до узла связи, который является получателем сообщения, общее число которых ограничено предельно допустимым временем доведения сообщения.
3. Способ по п.1, отличающийся тем, что пропускную способность многомерного маршрута передачи оценивают для независимых параллельно соединенных одномерных маршрутов передачи, которые упорядочивают в таблице маршрутизации узла связи по величине пропускной способности, начиная с одномерных маршрутов передачи, свободных от передачи сообщений с наибольшей пропускной способностью и заканчивая одномерным маршрутом передачи, занятым передачей сообщений с наименьшей пропускной способностью.
4. Способ по п.1, отличающийся тем, что вероятность доведения пакета по одномерному маршруту передачи определяется для последовательно соединенных независимых каналов связи, составляющих данный одномерный маршрут передачи.
