Способ динамической маршрутизации трафика в сети связи

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

 

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

Известен способ гибридной коммутации и адаптивной маршрутизации и устройство для его осуществления по Патенту РФ №2305374, опубл. 27.08.2007 г. бюл. №24, при котором измеряют длину сообщения L и сравнивают с пороговым значением L_n, если длина сообщения превышает пороговое значение L>L_n, то устанавливают физическое соединение и передачу осуществляют в режиме коммутации каналов, а при длине сообщения L<L_n сообщение разбивают на пакеты, переписывают в буферную память и передают в режиме коммутации пакетов по каналам с максимальной пропускной способностью в соответствии с маршрутной таблицей.

Недостатком аналога является то, что в нем не учитывается загруженность линий разной пропускной способности при передаче сообщений в конкретный момент времени. При потоке сообщений, длина которых превышает пороговое значение L>L_n, все сообщения будут отправляться по линии с максимальной пропускной способностью, без учета ее возможностей по передаче.

Известен способ многомерной гибридной коммутации и адаптивной маршрутизации пакетов сообщений по Патенту РФ №2416170, опубл. 10.04.2011 г. бюл. №10 заключающийся в том, что устанавливают соединения с приемом информации об адресе вызываемого сообщения и записывают сообщение в оперативную память, при этом измеряют длину сообщения L и сравнивают ее с пороговым значением L_n, если длина сообщения превышает пороговое значение L>L_n, то устанавливают физическое соединение и передачу осуществляют в режиме коммутации каналов, а при длине сообщения L≤L_n сообщение разбивают на пакеты, переписывают в буферную память и передают в режиме коммутации пакетов по каналам с максимальной пропускной способностью в соответствии с маршрутной таблицей, в фазе установления соединения анализируют по обобщенному критерию, включающему скорость передачи данных, максимальное число использованных каналов связи и надежность доставки сообщения, существующие физические соединения путем сравнения их с другими удаленными (N-мерными) маршрутизаторами, через которые может быть доставлено сообщение, и передают его с учетом результатов сравнительного анализа по нескольким параллельным маршрутам в виде пакетов, объемы которых пропорциональны скоростям передачи выбранных каналов с указанием адресов промежуточных маршрутизаторов, при этом по каждому направлению передачи производят выбор режима коммутации в соответствии с длиной сообщения L и порогового значения L_n.

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

Наиболее близким по своей технической сущности к заявленному способу является способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений по патенту РФ №2457628, опубликованный 27.07.2012 г. бюл. №21.

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

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

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

Заявленный способ динамической маршрутизации трафика в сети связи обеспечивает выбор маршрута, который учитывает характеристики пакетов, составляющих передаваемый трафик (реального времени (речь, видео) или эластичного (передача файлов)). Так для передачи трафика реального времени формируются пакеты относительного небольшого размера (от 70 до 200 байт и для обеспечения одного телефонного разговора требуется пропускная способность от 6 до 85 кбит/с, в зависимости от используемого кодека). Увеличение пропускной способности на линии связи на качество предоставляемой услуги связи не влияет. Относительно больше пропускной способности требуется для передачи видео (от 380 кбит/с до 2 мбит/с в зависимости от используемого кодека и качества видео) и увеличение пропускной способности на линии связи также не влияет на качество предоставляемой услуги.

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

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

Поставленная цель достигается тем, что в известном способе динамической маршрутизации трафика в сети связи, заключающемся в том, что предварительно на узле-отправителе, принимают сообщения от узла-источника, разделяют сообщение на пакеты, запоминают их количество и помещают в очередь на передачу, кроме того формируют таблицу маршрутизации и передают пакеты по нескольким маршрутам в соответствии со сформированной таблицей маршрутизации, на узле-отправителе перед передачей каждого из полученных пакетов считывают и запоминают его параметры, формируют таблицу маршрутизации с динамической метрикой, которую адаптируют к заданным параметрам пакета, после чего отправляют каждый пакет по маршруту, определенному сформированной таблицей маршрутизации, далее пересчитывают метрику задействованных маршрутов и повторяют действия до момента освобождения очереди на передачу пакетов, динамическую метрику m-маршрута рассчитывают по формуле: где - текущая пропускная способность m-маршрута, BW_m - номинальная пропускная способность m-маршрута в отсутствии передачи, - приращение объема входящего потока пакетов, сравнивают M_i, M_j, распределяют пакеты на маршрут с наименьшей метрикой, для адаптации таблицы маршрутизации к параметрам пакета, в качестве параметра выбирают значение размера пакетов, находящихся в очереди на передачу, формируют таблицу соответствия размера пакета и его номера в очереди, формируют таблицу соответствия номера маршрута и его динамической метрики.

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

Заявленный способ поясняется чертежами, на которых представлены:

Фиг. 1 - Модель сети пакетной передачи сообщений

Фиг. 2 - Схема реализации адаптивной таблицы маршрутизации.

Фиг. 3 - Данные для моделирования передачи потоков по пакетной сети передачи данных

Фиг. 4 - График изменения объема общего потока, распределенного по маршрутам

Фиг. 5 - График изменения рассчитанных метрик маршрутов, с приращением объема потока

Фиг. 6 - График изменения текущих пропускных способностей маршрутов

Предлагаемый способ реализуют следующим образом.

Передачу сообщений между узлом-отправителем 1 (Фиг. 1) и узлом-получателем 2 (Фиг. 1), осуществляют в виде кадров по технологии Ethernet. Формат кадра известен и подробно описан в главе 12 «Технологии локальных сетей на разделяемой среде» книги «Компьютерные сети. Принципы. Технологии, протоколы: Учебник для ВУЗов», Олифер В.Г., Олифер Н.А. 4-е издание - СПб.: Питер, 2010 стр. 361-362.

Узел-отправитель 1 (Фиг. 1) содержит в своем составе источники сообщений 1.1.1, 1.1.2, 1.1.3, коммутатор пакетов 1.4, маршрутизатор пакетов 1.5.

Маршрутизатор пакетов 1.5 (Фиг. 2) содержит в своем составе буфер пакетов 1.5.1, таблицу маршрутизации 1.5.2, арифметико-логическое устройство 1.5.3, включающее вычислительные блоки 1.5.3.1, 1.5.3.2, 1.5.3.3, внешние интерфейсы 1.5.4, 1.5.5, внутренний интерфейс 1.5.6, информационная шина 1.5.7 (Фиг. 1). Буфер пакетов 1.5.1 (Фиг. 1) предназначен для записи поступивших от источников пакетов 111.1-131.с (см. также Фиг. 2) в память пакетного маршрутизатора 1.5. Информационная шина 1.5.7 предназначена для обмена управляющими сигналами в форме инструкций между составными частями маршрутизатора 1.5.

Источники сообщений 1.1, 1.2, 1.3 (Фиг. 1) подключены к интерфейсам 1.4.1, 1.4.2, 1.4.3 коммутатора пакетов 1.4. Маршрутизатор пакетов 1.5 подключен своим внешним интерфейсом 1.5.6 (Фиг. 1) к интерфейсу 1.4.4 коммутатора пакетов 1.4. Маршрутизатор 1.5 (Фиг. 1) подключен к транспортной сети 100 посредствам внешних интерфейсов 1.5.4, 1.5.5. Маршрутизатор 2.5 узла-получателя 2 (Фиг. 1) подключен к транспортной сети 100 посредствам внешних интерфейсов 2.5.4, 2.5.5. На узле-получателе 2 (Фиг. 1) осуществляют подключение маршрутизатора пакетов 2.5, коммутатора пакетов 2.4, источников сообщений 2.1, 2.2, 2.3 в локальную вычислительную сеть аналогичным с узлом-отправителем 1 образом.

В транспортной сети 100 (Фиг. 1) описывают маршруты 100.5, 100.10 между маршрутизаторами 1.5, 2.5 узлов-отправителей 1, и получателей 2 соответственно. Описание маршрутов 100.5 и 100.10 (Фиг. 1) осуществляют посредствам формирования таблиц маршрутизации 1.5.2, 2.5.2, которые предназначены для описания характеристик доступных маршрутов. Общие принципы, формат и поля таблиц маршрутизации, описываемых в пакетных маршрутизаторах известны и подробно описаны в разделе «Упрощенная таблица маршрутизации» главы 16 «Протоколы межсетевого взаимодействия» книги «Компьютерные сети. Принципы. Технологии, протоколы: Учебник для вузов» Олифер В.Г., Олифер Н.А. 4-е издание - СПб.: Питер, 2010, стр. 514-603.

При описании таблицы маршрутизации 1.5.2 (Фиг. 2) помимо основных полей, формируют таблицы 1.5.2.1, 1.5.2.2. Формируемые таблицы предназначены для адаптации таблицы маршрутизации 1.5.2 к заданным параметрам передаваемых пакетов.

В таблице 1.5.2.1 задают соответствие длины р-го пакета Sz_p, номера n_p его записи в буфере пакетов 1.5.1 (Фиг. 2), множества из доступных маршрутов n_m, описанных в таблице 1.5.2.2. (Фиг. 2). Значения размеров пакетов содержатся в поле «total length» заголовка пакета. Пакетам задают различные значения длины Sz_k. Значение длины пакета зависит от протокола, который работает на канальном уровне ЭМВОС - «Эталонной модели взаимодействия открытых систем», которая подробна описана в главе 4 «Архитектура и стандартизация сетей» книги «Компьютерные сети. Принципы. Технологии, протоколы: Учебник для вузов» Олифер В.Г., Олифер Н.А. 4-е издание - СПб.: Питер, 2010, стр. 108-134.

В таблице 1.5.2.2. (Фиг. 2) задают соответствие порядкового номера записи маршрута n_m его динамической метрике M_din.

Характеристики маршрутов описывают значением их текущей пропускной способности BW_{m_tec} в килобит за секунду (kbps). В отсутствии передачи пакетов текущая пропускная способность равна номинальной пропускной способности маршрута BWm_tec=BW_m. Порядок расчета номинальной пропускной способности BW_m известен и подробно описан в разделе «Соотношение полосы пропускания и пропускной способности» главы 8 «Линии связи» книги «Компьютерные сети. Принципы. Технологии, протоколы: Учебник для вузов» Олифер В.Г., Олифер Н.А. 4-е издание - СПб.: Питер, 2010, стр. 246-254.

Описание последовательности действий при реализации способа.

Отправляют потоки пакетов 1.1.1, 1.2.1, 1.3.1 от источников 1.1, 1.2, 1.3 (Фиг. 1) в пакетный коммутатор 1.4 через его интерфейсы 1.4.1, 1.4.2, 1.4.3 соответственно. Отправленные потоки пакетов объединяют на интерфейсе 1.4.4 коммутатора пакетов 1.4 в общий поток 1.4.5. Общий поток 1.4.5 передают через внутренний интерфейс 1.5.6 в буфер пакетов 1.5.1 маршрутизатора пакетов 1.5 (Фиг. 2).

Записывают каждый пакет в память буфера 1.5.1, одновременно присваивают ему порядковый номер в буфере n_p (Фиг. 2).

Отправляют инструкцию от арифметико-логического устройства 1.5.3 (Фиг. 2) в буфер пакетов 1.5.1 на считывание значения размера Sz_p пакета n_p из буфера 1.5.1 и внесения в поля n_p и Sz_p таблицы 1.5.2.1 считанных из буфера пакетов значений (Фиг. 2).

Рассчитывают в блоке 1.5.3.1 арифметико-логического устройства 1.5.3 (Фиг. 2) номинальные значения пропускных способностей BW₅ и BW₁₀ маршрутов 100.5, 100.10, описанных в таблице 1.5.2.2 (Фиг. 2). Порядок расчета номинальной пропускной способности маршрута известен и подробно описан в разделе «Соотношение полосы пропускания и пропускной способности» главы 8 «Линии связи» книги «Компьютерные сети. Принципы. Технологии, протоколы: Учебник для вузов» Олифер В.Г., Олифер Н.А. 4-е издание - СПб.: Питер, 2010, стр. 246-254).

Рассчитывают в блоке 1.5.3.1 (Фиг. 2) арифметико-логического устройства 1.5.3 начальное значение динамических метрик М₅, М₁₀ маршрутов 100.5, 100.10, описанных в таблице 1.5.2.2 по формулам:

Записывают рассчитанные начальные значения динамических метрик маршрутов М₅, М₁₀ в поле M_din таблицы 1.5.2.2 в соответствии с порядковым номером маршрута n_m.

Формируют, исходя из значения поля «адрес получателя» заголовка пакетов, номера которых записаны в таблице 1.5.2.1, набор доступных для каждого пакета маршрутов и записывают сформированный набор в поле n_m таблицы 1.5.2.1 для каждого пакета, номер которого записан в поле n_p таблицы 1.5.2.1 (Фиг. 2).

Передают значения: n_p, Sz_p, n_m, M_din в блок 1.5.3.2 арифметико-логического устройства 1.5.3 (Фиг. 2).

Сравнивают в блоке 1.5.3.2 арифметико-логического устройства значения динамических метрик М₅, М₁₀ маршрутов 100.5, 100.10 и выявляют наименьшую.

Отправляют инструкцию от арифметико-логического устройства 1.5.3 в буфер 1.5.1 на отправку пакета n_111.1 по маршруту с наименьшей метрикой (Фиг. 2).

Отправляют пакет n_111.1 из буфера 1.5.1 через интерфейс 1.5.5 маршрутизатора 1.5, которому соответствует маршрут с наименьшей из рассчитанных метрик по маршруту.

Отправляют инструкцию от буфера 1.5.1 в блок 1.5.3.3 арифметико- 4"" логического устройства 1.5.3 на пересчет текущей метрики задействованного маршрута 100.10 (Фиг. 2).

Вычисляют в блоке 1.5.3.3 арифметико-логического устройства 1.5.3 (Фиг. 2) значение суммарного потока отправляемых по каждому маршруту пакетов по формуле:

где N - количество отправленных пакетов по маршруту 100.10, Sz_111.1 - размер пакета n_111.1.

Вычисляют в блоке 1.5.3.3 арифметико-логического устройства 1.5.3 значение измененной текущей пропускной способности задействованного маршрута по формуле:

Отправляют рассчитанные значение измененной пропускной способности задействованного маршрута BW'_{10_tec} из блока 1.5.3.3 в блок 1.5.3.1 арифметико-логического устройства 1.5.3.

Используют значение измененной пропускной способности BW'_{10_tec} задействованного маршрута в качестве исходных данных для пересчета его метрики.

Повторяют описанные операции до полного освобождения буфера пакетов 1.5.1 (Фиг. 2).

Возможность достижения технического результата подтверждается результатами экспериментальной проверки (Фиг. З, Фиг. 4, Фиг. 5, Фиг. 6)

Размер суммарного потока отправляемых пакетов FL_общ (Фиг. 3) при нулевой итерации задается равным FL_общ=0 kbps (kbps - величина равная количеству килобит переданных за одну секунду). При каждой следующей итерации он увеличивается на заданную Δfl=720 kbps (Фиг. 3). В отсутствии потока пакетов значения текущих пропускных способностей маршрутов BW_{i_tec}, BW_{j_tec} равны номинальным BW_{i_tec}=10000 kbps и BW_{j_tec}=5000 kbps соответственно.

Следуя формуле (3) рассчитывают значения метрик маршрутов M_i=100, M_j=200. Проводят сравнение M_i<M_j, получают результат, исходя из которого передают поток в первой итерации FL_общ=720 kbps по маршруту 10. С передачей первого потока (Фиг. 4) освобождают буфер пакетов маршрутизатора и пересчитывают метрики маршрутов с учетом изменения текущей пропускной способности маршрута 100.10, которую высчитывают по формуле (2). С передачей очередного потока по маршруту значение его метрики, рассчитанной по формуле (3), увеличивается (Фиг. 3, Фиг. 5). Далее итерационно производят приращение ΔFL.

На седьмой итерации (Фиг. 3, Фиг. 5) выполняется неравенство M_i>M_j. При наступлении такого момента рассчитывают коэффициент соотношения метрик маршрутов (Фиг. 3) по формуле:

где M_i, M_j - метрики доступных маршрутов.

На следующих за этой итерациях, исходя из рассчитанного коэффициента соотношения метрик K_M, разбивают общий поток пакетов FL_общ и формируют частные потоки FL_i, FL_j (Фиг. 3) исходя и соотношений:

Далее сформированные потоки FL_i, FL_j передают одновременно по соответствующим маршрутам до момента освобождения буфера 400 (Фиг. 2) маршрутизатора.

Потери пакетов (Фиг. 3, Фиг. 6) при данном распределении начинаются только при двадцать первой итерации при полном исчерпании пропускных способностей маршрутов и выполнении неравенства:

где FL_общ - суммарный поток отправляемых пакетов, a BW_i+BW_j - сумма пропускных способностей доступных маршрутов.

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

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

2. Способ по п. 1, отличающийся тем, что динамическую метрику m-маршрута рассчитывают по формуле: где - текущая пропускная способность m-маршрута, BW_m - номинальная пропускная способность m-маршрута в отсутствии передачи, - приращение объема входящего потока пакетов, сравнивают M_i, M_j, распределяют пакеты на маршрут с наименьшей метрикой.

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