RU2608678C1 - Method for multi-dimensional dynamic routing in communication network with packet transmission of messages - Google Patents
Method for multi-dimensional dynamic routing in communication network with packet transmission of messages Download PDFInfo
- Publication number
- RU2608678C1 RU2608678C1 RU2015149360A RU2015149360A RU2608678C1 RU 2608678 C1 RU2608678 C1 RU 2608678C1 RU 2015149360 A RU2015149360 A RU 2015149360A RU 2015149360 A RU2015149360 A RU 2015149360A RU 2608678 C1 RU2608678 C1 RU 2608678C1
- Authority
- RU
- Russia
- Prior art keywords
- multidimensional
- routes
- communication channels
- communication
- dimensional
- Prior art date
Links
- 238000004891 communication Methods 0.000 title claims abstract description 131
- 230000005540 biological transmission Effects 0.000 title claims abstract description 63
- 238000000034 method Methods 0.000 title claims abstract description 19
- 238000003908 quality control method Methods 0.000 claims abstract description 14
- 238000012937 correction Methods 0.000 claims abstract description 7
- 238000012546 transfer Methods 0.000 claims description 17
- 230000000694 effects Effects 0.000 abstract description 2
- 238000005516 engineering process Methods 0.000 abstract description 2
- 239000000126 substance Substances 0.000 abstract 1
- 238000004458 analytical method Methods 0.000 description 3
- 230000015572 biosynthetic process Effects 0.000 description 3
- 244000309464 bull Species 0.000 description 3
- 239000011159 matrix material Substances 0.000 description 3
- 230000003044 adaptive effect Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 239000000470 constituent Substances 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/64—Hybrid switching systems
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Description
Изобретение относится к области сетевых информационных технологий и может быть использовано для многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений и внутрисистемными помехами.The invention relates to the field of network information technology and can be used for multidimensional dynamic routing in a communication network with packet messaging and intra-system interference.
Известен способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, в соответствии с которым в каждом из узлов связи осуществляют контроль качества входящих в узел связи каналов связи. Результаты контроля качества каналов связи передают на узлы связи сети связи. В зависимости от качества каналов связи оценивают пропускную способность каналов связи, затем определяют пропускную способность одномерных маршрутов в зависимости от пропускной способности входящих в этот одномерный маршрут каналов связи. Далее формируют многомерный маршрут передачи сообщения, причем вначале в многомерный маршрут включают одномерные маршруты передачи с наибольшей пропускной способностью, затем - одномерные маршруты передачи с меньшей, но следующей по величине пропускной способностью и так далее, до тех пор, пока пропускная способность многомерного маршрута передачи не обеспечит передачу сообщения в заданное время, и далее передают сообщение по этому многомерному маршруту передачи (Квашенников В.В., Шабанов А.К. Способ адаптивной маршрутизации в сети связи с многомерными маршрутами передачи сообщений. Патент РФ №2431945. Опубл. 20.10.2011. Бюл. №29).A known method of multidimensional dynamic routing in a communication network with packet messaging, according to which in each of the communication nodes carry out quality control of the communication channels included in the communication node. The quality control results of communication channels are transmitted to communication nodes of a communication network. Depending on the quality of the communication channels, the throughput of the communication channels is estimated, then the throughput of the one-dimensional routes is determined depending on the throughput of the communication channels included in this one-dimensional route. Then, a multidimensional message transmission route is formed, first, in the multidimensional route, one-dimensional transmission routes with the highest throughput are included, then one-dimensional transmission routes with less but the next largest transmission capacity, and so on, until the throughput of the multidimensional transmission route will ensure the transmission of the message at a specified time, and then transmit the message along this multidimensional transmission route (V.V. Kvashennikov, A.K. Shabanov. Adaptive routing method in a communication network zi with multidimensional message transmission routes. Patent of the Russian Federation No. 2431945. Publish. 20.10.2011. Bull. No. 29).
Недостаток этого способа заключается в снижении производительности сети связи из-за того, что при формировании многомерного маршрута не учитывается взаимное влияние каналов связи сети связи из-за воздействия внутрисистемных помех, вероятности доставки пакетов по составляющим одномерным маршрутам, а также из-за того, что необходимо передавать большой трафик служебной информации о качестве каналов связи на узлы сети связи.The disadvantage of this method is to reduce the performance of the communication network due to the fact that the formation of a multidimensional route does not take into account the mutual influence of the communication channels of the communication network due to the effects of intra-system interference, the probability of packet delivery along components of one-dimensional routes, and also due to the fact that it is necessary to transmit a large traffic of service information about the quality of communication channels to the nodes of the communication network.
Известен также способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающийся в том, что в узлах связи осуществляют контроль качества входящих каналов связи. Результаты контроля качества каналов связи передают на другие узлы связи и в зависимости от качества каналов связи формируют одномерные маршруты передачи. Далее из одномерных маршрутов передачи формируют многомерный маршрут передачи сообщения, включая в него сначала одномерные маршруты передачи с каналами связи лучшего качества, затем - одномерные маршруты передачи с меньшим, но следующим по величине качеством каналов связи, и так до тех пор, пока качество многомерного маршрута передачи не обеспечит передачу всего сообщения. Затем оценивают вероятность доведения сообщения по многомерному маршруту передачи, и при величине вероятности доведения сообщения по многомерному маршруту передачи менее заданного значения перераспределяют пакеты по одномерным маршрутам передачи и далее передают сообщение по многомерному маршруту передачи (Квашенников В.В., Солдатенко Э.Н. Способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений. Патент РФ №2457628. Приор. 14.06.2011, опубл. 27.07.2012, Бюл. №21).There is also known a method of multidimensional dynamic routing in a communication network with packet messaging, which consists in the fact that the nodes of the communication monitor the quality of incoming communication channels. The quality control results of communication channels are transmitted to other communication nodes and, depending on the quality of communication channels, form one-dimensional transmission routes. Then, from a one-dimensional transmission route, a multidimensional message transmission route is formed, including first one-dimensional transmission routes with better quality communication channels, then one-dimensional transmission routes with lower, but the next highest quality communication channels, and so on, until the quality of the multidimensional route transmission will not ensure the transmission of the entire message. Then, the probability of bringing the message along the multidimensional transmission route is estimated, and if the probability of bringing the message along the multidimensional transmission route of less than a specified value is redistributed, the packets are distributed along the one-dimensional transmission routes and then the message is transmitted along the multidimensional transmission route (V.V. Kvashennikov, E.N. Soldatenko. Method dynamic routing in a communication network with multidimensional routes and packet messaging. Patent of the Russian Federation No. 2457628. Prior. 06/14/2011, published on July 27, 2012, Bull. No. 21).
Недостаток этого способа заключается в снижении производительности сети связи из-за того, что формирование многомерных маршрутов проводится без учета взаимного влияния каналов связи и вероятности доставки пакетов по одномерным маршрутам.The disadvantage of this method is to reduce the performance of the communication network due to the fact that the formation of multidimensional routes is carried out without taking into account the mutual influence of communication channels and the probability of packet delivery on one-dimensional routes.
Наиболее близким к предлагаемому способу (прототип) является способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающийся в том, что по результатам контроля качества входящих в узлы связи каналов связи вычисляют целевые функции каналов связи, которые учитывают вероятность и время доведения сообщения, затем на основании целевых функций каналов связи формируют одномерные маршруты и многомерный маршрут передачи и вычисляют их целевые функции, при формировании одномерных маршрутов передачи выполняют оптимизацию целевой функции этих маршрутов передачи, при формировании многомерных маршрутов передачи выполняют оптимизацию целевой функции этого маршрута передачи, выбирая сначала одномерный маршрут передачи с наибольшим значением целевой функцией, затем одномерный маршрут передачи с меньшим, но следующим по величине значением целевой функции и так до тех пор, пока многомерный маршрут передачи не обеспечит передачу всех пакетов сообщения в заданное время и с заданной вероятностью доведения сообщения, при этом значения целевых функций входящих в узлы связи каналов связи передают на смежные узлы связи, которые далее передают значения целевой функции на другие смежные узлы связи, исключая узлы, от которых были получены значения целевой функции (Квашенников В.В. Способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений. Патент РФ №2526755. Приор. 08.04.2013, опубл. 27.08.2014, Бюл. №24).Closest to the proposed method (prototype) is a method of multidimensional dynamic routing in a communication network with packet messaging, which consists in the fact that according to the quality control results of the communication channels included in the communication nodes, the target functions of the communication channels are calculated, which take into account the probability and time of message delivery, then, on the basis of the objective functions of the communication channels, one-dimensional routes and a multidimensional transmission route are formed and their objective functions are calculated, when forming one-dimensional transmission routes, They perform optimization of the objective function of these transmission routes; when generating multidimensional transmission routes, they optimize the objective function of this transmission route by first selecting a one-dimensional transmission route with the highest value of the objective function, then a one-dimensional transmission route with a smaller but next largest value of the objective function, and so on as long as the multidimensional transmission route does not ensure the transmission of all message packets at a given time and with a given probability of bringing the message, the values are x the functions of the communication channels of the communication channels are transferred to adjacent communication nodes, which then transmit the values of the objective function to other adjacent communication nodes, excluding the nodes from which the values of the objective function were obtained (V.V. Kvashennikov A method of multidimensional dynamic routing in a communication network with packet messaging. RF patent No. 2526755. Prior. 04/08/2013, publ. 08/27/2014, Bull. No. 24).
Недостаток этого способа заключается в снижении производительности сети связи из-за того, что формирование многомерных маршрутов проводится без учета взаимного влияния входящих в него каналов связи.The disadvantage of this method is to reduce the performance of the communication network due to the fact that the formation of multidimensional routes is carried out without taking into account the mutual influence of its constituent communication channels.
Технический результат предлагаемого способа многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений заключается в повышении производительности сети связи за счет оптимального выбора многомерных маршрутов и кратностей их использования на основе скоростей передачи информации каналов связи, определяемых с учетом их взаимного влияния, для всех возможных вариантов многомерных маршрутов передачи, обеспечивающих минимизацию времени доставки сообщений при условии доставки всех пакетов сообщений с заданной вероятностью.The technical result of the proposed method of multidimensional dynamic routing in a communication network with packet messaging is to increase the performance of the communication network due to the optimal choice of multidimensional routes and the frequency of their use based on the transmission speeds of information of communication channels, determined taking into account their mutual influence, for all possible multidimensional options transmission routes that minimize message delivery time while delivering all message packets with a given charity.
Технический результат в предлагаемом способе многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающемся в том, что в узлах связи осуществляют контроль качества входящих в них каналов связи, результаты контроля качества каналов связи передают на другие узлы связи, формируют одномерные маршруты передачи, далее из одномерных маршрутов формируют многомерные маршруты передачи, определяют целевые функции многомерных маршрутов передачи, достигается тем, что в сети связи при формировании одномерных и многомерных маршрутов формируют все их возможные варианты, по результатам контроля качества каналов связи корректируют скорости передачи информации в каналах связи с учетом взаимного влияния всех каналов связи, задействованных в каждом многомерном маршруте, определение целевых функций многомерных маршрутов передачи осуществляют по результатам коррекции скоростей передачи информации в каналах связи, далее осуществляют оптимальный выбор многомерных маршрутов и кратности их использования по критерию минимизации времени доставки.The technical result in the proposed method of multidimensional dynamic routing in a communication network with packet messaging, which consists in the fact that the communication nodes monitor the quality of their communication channels, the quality control results of the communication channels are transmitted to other communication nodes, form one-dimensional transmission routes, then multidimensional transmission routes are formed from one-dimensional routes, target functions of multidimensional transmission routes are determined, it is achieved by the fact that in the communication network when forming one-dimensional and leg-length routes form all their possible options, according to the results of quality control of communication channels, the information transfer speeds in communication channels are adjusted taking into account the mutual influence of all communication channels involved in each multidimensional route, the target functions of multidimensional transmission routes are determined according to the results of correction of information transfer speeds in channels communications, then carry out the optimal choice of multidimensional routes and the frequency of their use according to the criterion of minimizing delivery time.
Рассмотрим осуществление предлагаемого способа многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений.Consider the implementation of the proposed method of multidimensional dynamic routing in a communication network with packet messaging.
Во многих существующих и перспективных сетях связи передачу сообщений осуществляют небольшими блоками или пакетами. Пакеты передают одновременно, каждый по своему маршруту передачи, что существенно сокращает время доставки сообщения.In many existing and promising communication networks, messaging is carried out in small blocks or packets. Packets transmit simultaneously, each in its own transmission route, which significantly reduces the time of message delivery.
Одномерным маршрутом передачи называют совокупность последовательно соединенных каналов связи в соединении точка-точка между узлом связи, являющимся источником сообщений, и узлом связи - получателем сообщений. Множество параллельно соединенных одномерных маршрутов передачи, по которым передают пакеты, называют многомерным маршрутом передачи.A one-dimensional transmission route is a set of series-connected communication channels in a point-to-point connection between a communication node that is a message source and a communication node - a receiver of messages. A plurality of parallelly connected one-dimensional transmission routes along which packets are transmitted is called a multidimensional transmission route.
Способ заключается в том, что в узлах связи сети связи осуществляют контроль качества входящих в них каналов связи. Качество каналов связи определяют по результатам приема пакетов, с учетом скорости передачи информации каналов связи. При приеме пакета сообщения узел связи, являющийся получателем пакета, вычисляет контрольную сумму пакета. В случае совпадения вычисленной контрольной суммы и принятой контрольной суммы пакета с вероятностью, достаточно близкой к 1, считают, что пакет принят правильно, и оценивают частоту правильного приема пакетов или вероятность доставки пакета сообщения Р, равную отношению числа правильно принятых пакетов m к общему числу переданных пакетов n:The method consists in the fact that in the communication nodes of the communication network, quality control of the communication channels included in them is carried out. The quality of communication channels is determined by the results of packet reception, taking into account the transmission speed of information of communication channels. Upon receipt of a message packet, the communication node that is the recipient of the packet calculates a checksum of the packet. If the calculated checksum and the received checksum of the packet coincide with a probability close to 1, it is considered that the packet was received correctly and the frequency of the correct packet reception or the probability of message packet delivery P is estimated to be equal to the ratio of the number of correctly received packets m to the total number of transmitted packages n:
Результаты контроля качества каналов связи передают на другие узлы связи. Для снижения объема служебной информации передачу сообщений об изменении скоростей передачи информации в каналах связи выполняют только при достижении вероятности доставки пакетов пороговых значений (минимального и максимального).The quality control results of communication channels are transmitted to other communication nodes. To reduce the amount of overhead information, messages about changes in the information transfer rates in communication channels are transmitted only when the probability of delivery of threshold packets (minimum and maximum) is reached.
Анализ вероятностей целесообразно проводить через промежутки времени, длительность которых привязана к длительности квазистационарных состояний каналов связи, которая определяется параметрами сигнально-помеховой обстановки. Излишне частый анализ вероятностей доставки пакетов до узлов связи может приводить к ее некорректной оценке. С другой стороны, недостаточная частота анализа вероятности доставки пакетов до узлов связи приведет к тому, что не будет оперативно отслеживаться состояние сети связи и вероятностные характеристики доставки сообщений могут уменьшиться. Если по истечении некоторого времени (обычно 3-5 минут) вероятностные характеристики каналов связи выйдут за пределы установленных ограничений, целесообразно изменить скорости передачи информации по каналам связи. Пороговое значение для вероятности доставки Рзад зависит от важности сообщений, требований качества обслуживания, и может составлять, например, величину 0.99. Это позволяет сократить объем служебной маршрутной информации и число вычислений при выборе маршрутов передачи.It is advisable to conduct a probability analysis at time intervals, the duration of which is tied to the duration of the quasi-stationary states of the communication channels, which is determined by the parameters of the signal-noise environment. An overly frequent analysis of the probabilities of packet delivery to communication nodes can lead to its incorrect assessment. On the other hand, insufficient frequency analysis of the probability of packet delivery to communication nodes will lead to the fact that the status of the communication network will not be monitored promptly and the probability characteristics of message delivery may decrease. If after some time (usually 3-5 minutes) the probabilistic characteristics of the communication channels go beyond the established limits, it is advisable to change the transmission speed of information over the communication channels. The threshold value for the probability of delivery P ass depends on the importance of messages, quality of service requirements, and may be, for example, 0.99. This reduces the amount of overhead routing information and the number of calculations when choosing transmission routes.
Далее формируют одномерные маршруты передачи, из одномерных маршрутов формируют многомерные маршруты передачи, причем при формировании одномерных и многомерных маршрутов формируют все их возможные варианты.Next, one-dimensional transmission routes are formed, multidimensional transmission routes are formed from one-dimensional routes, and when forming one-dimensional and multidimensional routes, all their possible variants are formed.
По результатам контроля качества каналов связи корректируют скорости передачи информации в каналах связи с учетом взаимного влияния всех каналов связи, задействованных в каждом многомерном маршруте из условия обеспечения заданной вероятности доставки пакетов.According to the results of quality control of communication channels, the information transfer rates in communication channels are adjusted taking into account the mutual influence of all communication channels involved in each multidimensional route from the condition of ensuring a given probability of packet delivery.
Если вероятность доставки пакетов по каналу связи удовлетворяет условиюIf the probability of packet delivery over the communication channel satisfies the condition
то считается, что скорость выбрана правильно и коррекция скорости передачи информации в канале связи не производится. Если Рзад>Р, то принимается решение о необходимости снижения скорости передачи информации в канале связи. Если Р=1, то принимается решение о необходимости повышении скорости передачи информации в канале связи.it is believed that the speed is selected correctly and the correction of the information transfer speed in the communication channel is not performed. If P ass > P, then a decision is made about the need to reduce the speed of information transfer in the communication channel. If P = 1, then a decision is made about the need to increase the speed of information transfer in the communication channel.
Скорость передачи информации канала связи зависит от ширины полосы пропускания канала связи и сигнально-помеховой обстановки в канале связи. Ширина полосы пропускания, как правило, является постоянной величиной, выбираемой при проектировании данного канала связи, в то время как сигнально-помеховая обстановка меняется в процессе работы канала связи в зависимости от влияния межсистемных и внутрисистемных помех. Поэтому при выборе скоростей передачи информации в каналах связи учитывается их взаимное влияние.The communication channel information rate depends on the bandwidth of the communication channel and the signal-noise situation in the communication channel. The bandwidth, as a rule, is a constant value selected during the design of a given communication channel, while the signal-noise situation changes during the operation of the communication channel depending on the influence of intersystem and intra-system interference. Therefore, when choosing information transfer rates in communication channels, their mutual influence is taken into account.
Пусть для доставки всех сообщений до каждого из узлов 
Обозначим за 
где Ckb – коэффициенты, равные 1, если пакеты доставляются до k-го узла по многомерному маршруту b и 0 в противном случае.where C kb are coefficients equal to 1 if packets are delivered to the k-th node along the multidimensional route b and 0 otherwise.
Время доставки пакета Tkb по одномерному маршруту, осуществляющему доставку информации до k-го узла в многомерном маршруте b, равно сумме времен доставки пакета по всем каналам связи, входящим в этот одномерный маршрут, каждое из которых определяется как отношение длины пакета сообщения L к скорости передачи информации Vrkb в r-ом канале связи:The packet delivery time T kb along a one-dimensional route that delivers information to the k-th node in multidimensional route b is equal to the sum of packet delivery times for all communication channels included in this one-dimensional route, each of which is defined as the ratio of the message packet length L to the speed information transfer V rkb in the r-th communication channel:
где Rkb - количество каналов связи, входящих в указанный одномерный маршрут.where R kb is the number of communication channels included in the specified one-dimensional route.
Далее определяют целевые функции многомерных маршрутов по результатам коррекции скоростей передачи информации в каналах связи, как:Next, the target functions of the multidimensional routes are determined by the results of the correction of information transfer rates in communication channels, such as:
Далее осуществляют оптимальный выбор многомерных маршрутов и кратности их использования по критерию минимизации времени доставки, обеспечивающих передачу всех сообщений с заданной вероятностью:Next, they carry out the optimal choice of multidimensional routes and the frequency of their use according to the criterion of minimizing delivery time, ensuring the transmission of all messages with a given probability:
Адресация в сети связи осуществляется с помощью таблиц маршрутизации узлов связи, содержащих перечень всех многомерных маршрутов доставки пакетов сообщений от данного узла связи до получателя сообщения. Таблица маршрутизации узлов связи по каждому многомерному маршруту передачи содержит следующие поля:Addressing in the communication network is carried out using routing tables of communication nodes containing a list of all multidimensional routes for delivering message packets from this communication node to the message recipient. The routing table of the communication nodes for each multidimensional transmission route contains the following fields:
1) адреса узлов связи - получателей пакетов сообщений;1) addresses of communication nodes - recipients of message packets;
2) последовательность адресов промежуточных узлов связи при переходе от данного узла связи к узлу связи - получателю пакета;2) the sequence of addresses of intermediate communication nodes during the transition from a given communication node to a communication node - the recipient of the packet;
3) метрику многомерного маршрута передачи, определяемую значением его целевой функции.3) the metric of the multidimensional transmission route, determined by the value of its objective function.
На фиг. 1 приведен алгоритм работы вычислителя маршрутизатора, определяющий оптимальные многомерные маршруты и кратности их использования, обеспечивающие передачу всех сообщений с заданной вероятностью и с наименьшим временем доставки.In FIG. Figure 1 shows the algorithm of the router calculator, which determines the optimal multidimensional routes and the frequency of their use, ensuring the transmission of all messages with a given probability and with the least delivery time.
Начальное заполнение таблицы маршрутизации выполняют при вводе сети в эксплуатацию или при смене режимов работы сети связи, сопровождающейся существенным изменением состояния сети связи. В остальных случаях выполняют дополнительную итеративную коррекцию таблиц маршрутизации, которая требует существенно меньшего объема вычислений и передачи меньшего объема служебной маршрутной информации по каналам связи.The initial filling of the routing table is performed when the network is put into operation or when the operating modes of the communication network change, accompanied by a significant change in the state of the communication network. In other cases, an additional iterative correction of routing tables is performed, which requires significantly less computation and transmission of less routing information over the communication channels.
При вводе сети в эксплуатацию проводят анализ сети, в результате которого определяют количество многомерных маршрутов, все их варианты, коэффициенты Ckb. На основе полученной информации, согласно приведенному алгоритму, формируется матрица А (фиг. 2). Далее при анализе сети связи оценивают скорости передачи информации каналов связи для каждого из многомерных маршрутов с учетом их взаимного влияния и время доставки пакетов. На основе полученных результатов формируют начальные значения целевых функций F, которые вводятся в алгоритм работы вычислителя маршрутизатора.When the network is put into operation, the network is analyzed, as a result of which the number of multidimensional routes, all their options, and the coefficients C kb are determined. Based on the information received, according to the above algorithm, matrix A is formed (Fig. 2). Further, when analyzing the communication network, the information transfer rates of the communication channels for each of the multidimensional routes are estimated taking into account their mutual influence and the time of packet delivery. Based on the results obtained, initial values of the objective functions F are generated, which are introduced into the algorithm of the router calculator.
Далее по результатам контроля качества каналов связи корректируют скорости передачи информации в каналах связи с учетом взаимного влияния всех каналов связи, задействованных в каждом многомерном маршруте, определяют целевые функции многомерных маршрутов (фиг. 3). Для этого в алгоритме осуществляется ввод вероятностей доставки Р по всем узлам - получателям и номерам многомерных маршрутов b. Если для некоторого r-го канала связи Рзад>Prkb, то принимается решение о необходимости снижения скорости передачи информации по этому каналу связи, а если Prkb=1, то о необходимости повышении скорости передачи информации по нему. Далее определяют времена доставки пакетов и целевые функции многомерных маршрутов передачи, на основе которых корректируется матрица А.Further, according to the results of quality control of communication channels, the information transfer rates in communication channels are adjusted taking into account the mutual influence of all communication channels involved in each multidimensional route, the target functions of multidimensional routes are determined (Fig. 3). For this purpose, the delivery probabilities P are entered in the algorithm for all nodes — recipients and numbers of multidimensional routes b. If for some rth communication channel Pass> Prkb, then a decision is made about the need to reduce the speed of information transfer on this communication channel, and if Prkb= 1, then about the need to increase the speed of information transfer on it. Next, packet delivery times and target functions of multidimensional transmission routes are determined, based on which matrix A is adjusted.
Коррекция скоростей передачи информации не создает новых маршрутов, а только меняет метрики ранее построенных маршрутов таблицы маршрутизации в зависимости от изменения их целевой функции.The correction of information transfer speeds does not create new routes, but only changes the metrics of previously constructed routes of the routing table depending on the change in their target function.
Далее в матрицу А вводят количество пакетов Npk длиной L, которые необходимо доставить до каждого из узлов, являющихся получателями сообщений.Next, in the matrix A, enter the number of packets Np k of length L, which must be delivered to each of the nodes that are recipients of messages.
Далее осуществляют оптимальный выбор многомерных маршрутов и кратности их использования по критерию минимизации времени доставки (6) согласно алгоритму процедуры нахождения оптимальных многомерных маршрутов, приведенному в приложении. Алгоритм является реализацией задачи целочисленного линейного программирования в виде полностью целочисленного алгоритма Гомори (Шевченко В.Н., Золотых Н.Ю. Линейное и целочисленное программирование. Нижний Новгород, Издательство Нижегородского госуниверситета им. Н.И. Лобачевского, 2004, 154 с.).Next, they carry out the optimal choice of multidimensional routes and the frequency of their use according to the criterion of minimizing delivery time (6) according to the algorithm of the procedure for finding optimal multidimensional routes given in the appendix. The algorithm is an implementation of the integer linear programming problem in the form of a completely integer Gomori algorithm (Shevchenko VN, Zolotykh N.Yu. Linear and integer programming. Nizhny Novgorod, Publishing House of the Nizhny Novgorod State University named after N.I. Lobachevsky, 2004, 154 pp.) .
Приведенный алгоритм может быть реализован на стандартных программных и программно-аппаратных маршрутизаторах, базирующихся на операционной системе Linux или IOS (для маршрутизаторов фирмы CISCO).The above algorithm can be implemented on standard software and hardware-software routers based on the Linux or IOS operating system (for routers from CISCO).
Технический результат в предлагаемом способе многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающийся в повышении производительности сети связи, достигается за счет оптимального выбора многомерных маршрутов и кратностей их использования на основе скоростей передачи информации каналов связи, определяемых с учетом их взаимного влияния, для всех возможных вариантов многомерных маршрутов передачи, обеспечивающих минимизацию времени доставки сообщений при условии доставки всех пакетов сообщений с заданной вероятностью.The technical result in the proposed method of multidimensional dynamic routing in a communication network with packet messaging, which consists in increasing the performance of the communication network, is achieved due to the optimal choice of multidimensional routes and the frequency of their use based on the transmission speeds of information of communication channels, determined taking into account their mutual influence, for of all possible options for multidimensional transmission routes that minimize message delivery time provided that all packets are delivered minutes with a given probability.
Claims (1)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2015149360A RU2608678C1 (en) | 2015-11-17 | 2015-11-17 | Method for multi-dimensional dynamic routing in communication network with packet transmission of messages |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| RU2015149360A RU2608678C1 (en) | 2015-11-17 | 2015-11-17 | Method for multi-dimensional dynamic routing in communication network with packet transmission of messages |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| RU2608678C1 true RU2608678C1 (en) | 2017-01-23 |
Family
ID=58456915
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2015149360A RU2608678C1 (en) | 2015-11-17 | 2015-11-17 | Method for multi-dimensional dynamic routing in communication network with packet transmission of messages |
Country Status (1)
| Country | Link |
|---|---|
| RU (1) | RU2608678C1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2737702C1 (en) * | 2020-03-05 | 2020-12-02 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for dynamic routing of traffic in communication network |
| RU2783344C1 (en) * | 2022-01-10 | 2022-11-11 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for multiparametric reconfiguration of a fiber-optic communication network |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6856598B1 (en) * | 1997-08-15 | 2005-02-15 | David Stanfield | Communications system |
| RU2313187C1 (en) * | 2006-02-14 | 2007-12-20 | Федеральное государственное унитарное предприятие "Калужский научно-исследовательский институт телемеханических устройств" | Method for packet transmission of messages in communication networks with multidimensional routing |
| US7660320B2 (en) * | 2005-07-28 | 2010-02-09 | Technische Universitat Berlin | Communication network, a method of routing data packets in such communication network and a method of locating and securing data of a desired resource in such communication network |
| RU2526755C1 (en) * | 2013-04-08 | 2014-08-27 | Открытое акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" | Method for multi-dimensional dynamic routing in message batch transmission communication network |
-
2015
- 2015-11-17 RU RU2015149360A patent/RU2608678C1/en not_active IP Right Cessation
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6856598B1 (en) * | 1997-08-15 | 2005-02-15 | David Stanfield | Communications system |
| US7660320B2 (en) * | 2005-07-28 | 2010-02-09 | Technische Universitat Berlin | Communication network, a method of routing data packets in such communication network and a method of locating and securing data of a desired resource in such communication network |
| RU2313187C1 (en) * | 2006-02-14 | 2007-12-20 | Федеральное государственное унитарное предприятие "Калужский научно-исследовательский институт телемеханических устройств" | Method for packet transmission of messages in communication networks with multidimensional routing |
| RU2526755C1 (en) * | 2013-04-08 | 2014-08-27 | Открытое акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" | Method for multi-dimensional dynamic routing in message batch transmission communication network |
Non-Patent Citations (3)
| Title |
|---|
| 1. * |
| 1. US 6856598 B1, 15.02.2005 * |
| US 7660320 B2, 09.02.2010 * |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| RU2737702C1 (en) * | 2020-03-05 | 2020-12-02 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for dynamic routing of traffic in communication network |
| RU2783344C1 (en) * | 2022-01-10 | 2022-11-11 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for multiparametric reconfiguration of a fiber-optic communication network |
| RU2794918C1 (en) * | 2022-01-10 | 2023-04-25 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for dynamic reconfiguration of fiber-optical communication network with spectral complexing systems |
| RU2799769C1 (en) * | 2022-10-28 | 2023-07-11 | Федеральное государственное казенное военное образовательное учреждение высшего образования Федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Минис | Method for configuring fiber-optical communication network with wavelength-division multiplexing systems |
| RU2815819C1 (en) * | 2023-01-10 | 2024-03-22 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Communication network dynamic reconfiguration method |
| RU2806055C1 (en) * | 2023-02-14 | 2023-10-25 | федеральное государственное казенное военное образовательное учреждение высшего образования "Военная орденов Жукова и Ленина Краснознаменная академия связи имени Маршала Советского Союза С.М. Буденного" Министерства обороны Российской Федерации | Method for dynamic reconfiguration of fiber-optical communication network |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US9667536B2 (en) | Network traffic shaping for Low power and Lossy Networks | |
| Galinina et al. | Stabilizing multi-channel slotted aloha for machine-type communications | |
| JP4782832B2 (en) | Link control and routing adapted to end-to-end conditions in multi-hop networks | |
| EP3523903B1 (en) | Collaborative communications | |
| Lou et al. | AoI and throughput tradeoffs in routing-aware multi-hop wireless networks | |
| CN112217723A (en) | Method for establishing routing table, electronic equipment and network | |
| EP3248323B1 (en) | Method and system for rate adaptation for data traffic | |
| Mohajer et al. | QoSCM: QoS-aware coded multicast approach for wireless networks | |
| CN111512600A (en) | Method, apparatus and computer program for distributing traffic in a telecommunications network | |
| RU2457628C1 (en) | Method for dynamic routing in multidimensional route and batched messaging communication network | |
| Juan et al. | Data-centric clustering for data gathering in machine-to-machine wireless networks | |
| RU2608678C1 (en) | Method for multi-dimensional dynamic routing in communication network with packet transmission of messages | |
| Venkatasubramanian et al. | Multi-path qos routing protocol for load balancing in manet | |
| Tehrani et al. | Opportunistic routing under unknown stochastic models | |
| Hanemann et al. | Reducing Packet Transmissions in Ad Hoc Routing Protocols by Adaptive Neighbor Discovery. | |
| RU2526755C1 (en) | Method for multi-dimensional dynamic routing in message batch transmission communication network | |
| Zhang et al. | P2P caching schemes for jointly minimizing memory cost and transmission delay over information-centric networks | |
| Li et al. | Random network coding based on adaptive sliding window in wireless multicast networks | |
| Wang et al. | A load-balancing routing algorithm for multi-channel wireless mesh networks | |
| Hohmann et al. | Optimal resource allocation policy for multi-rate opportunistic forwarding | |
| JP6121586B1 (en) | Radio scheduling apparatus and method | |
| Wei et al. | Deployment of a reinforcement backbone network with constraints of connection and resources | |
| Gupta et al. | Performance enhancement of DYMO routing protocol with ant colony optimization | |
| KR101435190B1 (en) | Resource allocation apparatus and method for multichannel multisession wireless network | |
| Girici et al. | Minimum-outage broadcast in wireless networks with fading channels |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| MM4A | The patent is invalid due to non-payment of fees |
Effective date: 20181118 |