RU2737702C1 - Method for dynamic routing of traffic in communication network - Google Patents

Abstract

FIELD: physics.

SUBSTANCE: proposed invention relates to network information technologies and can be used in development of new, as well as improvement of existing routing protocols used in packet switched communication networks. Method of dynamic routing of traffic in a communication network consists in the fact that beforehand on the sender node messages are received from the source node, dividing the message into packets, storing the number thereof and placing in the transmission queue, wherein prior to transmitting each of the received packets, on the sending node, reading and storing its parameters, forming a routing table with a dynamic metric, which is adapted to the given packet parameters, after which each packet is sent along the route determined by the generated routing table, then recalculating metric of involved routes and repeating actions until packet queue is released.

EFFECT: technical result consists in providing more efficient use of available routes bandwidth.

3 cl, 6 dwg

Description

The claimed method relates to the field of network information technologies and can be used in the development of new, as well as the improvement of existing routing protocols used in packet-switched communication networks.

The known method of hybrid switching and adaptive routing and a device for its implementation according to RF Patent No. 2305374, publ. August 27, 2007 bull. No. 24, in which the length of the message L is measured and compared with the threshold value L _n , if the length of the message exceeds the threshold value L> L _n , then a physical connection is established and transmission is carried out in circuit switching mode, and when the message length is L <L _{n, the} message is split into packets, are rewritten into the buffer memory and transmitted in the packet-switched mode over the channels with the maximum throughput in accordance with the routing table.

The disadvantage of the analogue is that it does not take into account the load of lines of different throughput when transmitting messages at a particular moment in time. With a stream of messages, the length of which exceeds the threshold value L> L _n , all messages will be sent over the line with the maximum bandwidth, without taking into account its transmission capabilities.

The known method of multidimensional hybrid switching and adaptive routing of message packets according to RF Patent No. 2416170, publ. 10.04.2011 bull. No. 10 consisting in the fact that they establish connections with the reception of information about the address of the called message and write the message into the RAM, while measuring the length of the message L and comparing it with the threshold value L _n , if the length of the message exceeds the threshold value L> L _n , then a physical connection is established and the transmission is carried out in circuit switching mode, and when the message length is L≤L _{n, the} message is split into packets, rewritten into the buffer memory and transmitted in packet switching mode over the channels with the maximum bandwidth in accordance with the routing table, in the connection establishment phase are analyzed according to a generalized criterion, including the data transfer rate, the maximum number of used communication channels and the reliability of message delivery, the existing physical connections by comparing them with other remote (N-dimensional) routers through which the message can be delivered, and transmit it taking into account the results of the comparative analysis on several parallel routes in the form of packets, the volumes of which are proportional to the transmission rates of the selected channels, indicating the addresses of intermediate routers, while for each transmission direction, the switching mode is selected in accordance with the message length L and the threshold value L _n .

The disadvantage of this method is that the data on the congestion of transit nodes at a particular point in time are not taken into account. The workload of transit nodes changes due to the arrival of messages from other directions, which can lead to an error in choosing the optimal route when transmitting messages.

The closest in technical essence to the claimed method is a method of dynamic routing in a communication network with multidimensional routes and packet transmission of messages according to RF patent No. 2457628, published on July 27, 2012, byul. No. 21.

The prototype method consists in the fact that in the communication node, which is the source of the message, the quality of the communication channels constituting the one-dimensional transmission routes is analyzed, the throughput of the communication channels is estimated, then, based on the throughput of the communication channels, the throughput of the one-dimensional transmission routes is obtained from the one-dimensional transmission routes form a multidimensional message transmission route, including first one-dimensional transmission routes with the highest throughput, then one-dimensional transmission routes with a lower throughput, then the probabilities of bringing packets along one-dimensional transmission routes are estimated, and the entire message - along a multidimensional transmission route, and with a probability value bringing a message along a multidimensional transmission route less than a specified value, redistribute packets along one-dimensional transmission routes, optimizing the probability of bringing the entire message along a multidimensional transmission route and then transmit the message along a multidimensional transmission y transmission route.

The disadvantage of the prototype method is the irrational use of the bandwidth of the available routes in which the loss of packets during transmission is possible, since when distributing packets along the generated multidimensional routes, the length of packets in the transmission queue is not taken into account.

The aim of the present invention is to provide more rational use of the bandwidth of available routes and reduce the probability of packet loss during transmission by routing packets with specified parameters based on the generated routing table with dynamic metric.

The claimed method for dynamic routing of traffic in a communication network provides a route selection that takes into account the characteristics of packets that make up the transmitted traffic (real-time (voice, video) or elastic (file transfer)). So for the transmission of real-time traffic, packets of a relatively small size are formed (from 70 to 200 bytes and to ensure one telephone conversation, a bandwidth of 6 to 85 kbps is required, depending on the codec used). The increase in bandwidth on the communication line does not affect the quality of the communication service provided. Relatively more bandwidth is required for video transmission (from 380 kbps to 2 Mbps depending on the codec used and video quality) and an increase in bandwidth on the communication line also does not affect the quality of the service provided.

When sending e-mail messages, that is, transferring large files. In this case, packets are formed with the maximum size that the technology used (1500 bytes) allows. The increase in throughput on the communication line is proportional to the reduction in the file transfer time.

Therefore, in the proposed method, by taking into account the parameters of packets when calculating the dynamic metric of the route, the problem of more rational use of the bandwidth of the routes is solved, the increase in the quality of communication when transferring large files (reduction of the message delivery time due to the selection of routes with higher bandwidth).

где

- текущая пропускная способность m-маршрута, BW_m - номинальная пропускная способность m-маршрута в отсутствии передачи,

- приращение объема входящего потока пакетов, сравнивают M_i, M_j, распределяют пакеты на маршрут с наименьшей метрикой, для адаптации таблицы маршрутизации к параметрам пакета, в качестве параметра выбирают значение размера пакетов, находящихся в очереди на передачу, формируют таблицу соответствия размера пакета и его номера в очереди, формируют таблицу соответствия номера маршрута и его динамической метрики.This goal is achieved by the fact that in the known method of dynamic routing of traffic in a communication network, which consists in the fact that, in advance, at the sending node, messages are received from the source node, the message is divided into packets, their number is stored, and they are placed in a queue for transmission, except In addition, a routing table is formed and packets are transmitted along several routes in accordance with the generated routing table, at the sending node, before transmitting each of the received packets, its parameters are read and stored, a routing table is formed with a dynamic metric, which is adapted to the specified parameters of the packet, and then sent each packet along the route defined by the generated routing table, then the metric of the involved routes is recalculated and the actions are repeated until the queue for packet transmission is released, the dynamic metric of the m-route is calculated by the formula:

Where

is the current capacity of the m-route, BW _m is the nominal capacity of the m-route in the absence of transmission,

- increment in the volume of the incoming packet flow, compare M _i , M _j , distribute the packets to the route with the smallest metric, to adapt the routing table to the packet parameters, select the value of the size of packets in the transmission queue as a parameter, form a packet size correspondence table and its numbers in the queue, form a table of correspondence between the route number and its dynamic metric.

Due to the new set of essential features in the claimed method, when forming the routing table, it is dynamically adapted to the given packet parameters to ensure the choice of the packet transmission route with the smallest among the calculated dynamic metrics, which achieves a more rational distribution of packets taking into account the current throughput of the routes and provides reducing the likelihood of data packet loss.

The claimed method is illustrated by drawings, which show:

FIG. 1 - Model of a packet messaging network

FIG. 2 - Implementation diagram of the adaptive routing table.

FIG. 3 - Data for modeling the transmission of streams over a packet data network

FIG. 4 - Graph of changes in the volume of the total flow distributed along the routes

FIG. 5 - Graph of changes in the calculated route metrics, with an increase in the flow volume

FIG. 6 - Schedule of changes in current route capacities

The proposed method is implemented as follows.

The transmission of messages between the sending node 1 (Fig. 1) and the receiving node 2 (Fig. 1) is carried out in the form of frames using Ethernet technology. The frame format is known and is described in detail in chapter 12 "Technologies of local area networks on a shared environment" of the book "Computer networks. Principles. Technologies, Protocols: A Textbook for Universities ", VG Olifer, NA Olifer. 4th edition - SPb .: Peter, 2010 pp. 361-362.

The sending node 1 (Fig. 1) contains message sources 1.1.1, 1.1.2, 1.1.3, packet switch 1.4, packet router 1.5.

The packet router 1.5 (Fig. 2) contains a packet buffer 1.5.1, a routing table 1.5.2, an arithmetic logic unit 1.5.3, including computing units 1.5.3.1, 1.5.3.2, 1.5.3.3, external interfaces 1.5 .4, 1.5.5, internal interface 1.5.6, data bus 1.5.7 (Fig. 1). The packet buffer 1.5.1 (Fig. 1) is intended for recording packets 111.1-131.c (see also Fig. 2) received from the sources into the memory of the packet router 1.5. The information bus 1.5.7 is intended for the exchange of control signals in the form of instructions between the components of the router 1.5.

Sources of messages 1.1, 1.2, 1.3 (Fig. 1) are connected to interfaces 1.4.1, 1.4.2, 1.4.3 of the packet switch 1.4. The packet router 1.5 is connected by its external interface 1.5.6 (Fig. 1) to the 1.4.4 interface of the packet switch 1.4. Router 1.5 (Fig. 1) is connected to the transport network 100 through external interfaces 1.5.4, 1.5.5. The router 2.5 of the receiving node 2 (Fig. 1) is connected to the transport network 100 by means of external interfaces 2.5.4, 2.5.5. At the receiving node 2 (Fig. 1), the packet router 2.5, the packet switch 2.4, the message sources 2.1, 2.2, 2.3 are connected to the local area network in the same way as the sending node 1.

In the transport network 100 (Fig. 1), routes 100.5, 100.10 are described between routers 1.5, 2.5 of the sending nodes 1, and recipients 2, respectively. Description of routes 100.5 and 100.10 (Fig. 1) is carried out by means of forming routing tables 1.5.2, 2.5.2, which are intended to describe the characteristics of available routes. The general principles, format and fields of the routing tables described in packet routers are known and are described in detail in the "Simplified Routing Table" section of Chapter 16 "Interworking Protocols" of the book "Computer Networks. Principles. Technologies, Protocols: Textbook for Universities ”Olifer V.G., Olifer N.A. 4th edition - SPb .: Peter, 2010, pp. 514-603.

When describing the routing table 1.5.2 (Fig. 2), in addition to the main fields, tables 1.5.2.1, 1.5.2.2 are formed. The generated tables are designed to adapt the routing table 1.5.2 to the specified parameters of the transmitted packets.

Table 1.5.2.1 sets the correspondence between the length of the p-th packet Sz _p , the number n _{p of} its entry in the packet buffer 1.5.1 (Fig. 2), the set of available routes n _m described in Table 1.5.2.2. (Fig. 2). The packet sizes are contained in the "total length" field of the packet header. The packets are given different values of the length Sz _k . The value of the packet length depends on the protocol that operates at the data link layer EMVOS - "Reference Model for Open Systems Interconnection", which is described in detail in Chapter 4 "Network Architecture and Standardization" of the book "Computer networks. Principles. Technologies, Protocols: Textbook for Universities ”Olifer V.G., Olifer N.A. 4th edition - SPb .: Peter, 2010, pp. 108-134.

Table 1.5.2.2. (Fig. 2) assign the correspondence of the sequence number of the route record n _{m to} its dynamic metric M _din .

Route characteristics are described by the value of their current throughput BW _{m_tec} in kilobits per second (kbps). In the absence of packet transmission, the current throughput is equal to the nominal throughput of the BWm_tec = BW _m route. The procedure for calculating the nominal bandwidth BW _m is known and is described in detail in the section "The ratio of bandwidth and bandwidth" chapter 8 "Communication lines" of the book "Computer networks. Principles. Technologies, Protocols: Textbook for Universities ”Olifer V.G., Olifer N.A. 4th edition - SPb .: Peter, 2010, pp. 246-254.

Description of the sequence of actions when implementing the method.

Packets 1.1.1, 1.2.1, 1.3.1 are sent from sources 1.1, 1.2, 1.3 (Fig. 1) to packet switch 1.4 through its interfaces 1.4.1, 1.4.2, 1.4.3, respectively. The sent streams of packets are combined on the interface 1.4.4 of the packet switch 1.4 into a common stream 1.4.5. The general stream 1.4.5 is transmitted through the internal interface 1.5.6 to the packet buffer 1.5.1 of the packet router 1.5 (Fig. 2).

Each packet is written into the memory of the buffer 1.5.1, at the same time it is assigned a sequence number in the buffer n _p (Fig. 2).

An instruction is sent from the arithmetic logic device 1.5.3 (Fig. 2) to the packet buffer 1.5.1 to read the value of the size Sz _{p of the} packet n _p from the buffer 1.5.1 and enter the fields n _p and Sz _{p of} Table 1.5.2.1 read from value packet buffer (Fig. 2).

Calculate in block 1.5.3.1 of the arithmetic logic device 1.5.3 (Fig. 2) the nominal values of the throughput BW ₅ and BW ₁₀ routes 100.5, 100.10, described in table 1.5.2.2 (Fig. 2). The procedure for calculating the nominal throughput of a route is known and is described in detail in the section "The ratio of bandwidth and bandwidth" Chapter 8 "Communication lines" of the book "Computer networks. Principles. Technologies, Protocols: Textbook for Universities ”Olifer V.G., Olifer N.A. 4th edition - SPb .: Peter, 2010, pp. 246-254).

Calculate in block 1.5.3.1 (Fig. 2) of the arithmetic logic device 1.5.3 the initial value of the dynamic metrics M ₅ , M ₁₀ routes 100.5, 100.10, described in Table 1.5.2.2 by the formulas:

The calculated initial values of the dynamic metrics of the routes M ₅ , M _{10 are} recorded in the M _din field of Table 1.5.2.2 in accordance with the ordinal number of the route n _m .

Based on the value of the field "recipient address" of the header of packets, the numbers of which are recorded in table 1.5.2.1, a set of routes available for each packet is formed and the generated set is written in the n _m field of table 1.5.2.1 for each packet, the number of which is written in the n field _{p of} Table 1.5.2.1 (Fig. 2).

The values are transmitted: n _p , Sz _p , n _m , M _din to the block 1.5.3.2 of the arithmetic-logic device 1.5.3 (Fig. 2).

The values of dynamic metrics M ₅ , M _{10 of} routes 100.5, 100.10 are compared in block 1.5.3.2 of the arithmetic-logic device and the smallest one is revealed.

An instruction is sent from the arithmetic logic device 1.5.3 to buffer 1.5.1 to send packet n _111.1 along the route with the lowest metric (Fig. 2).

Packet n _{111.1 is} sent from buffer 1.5.1 through interface 1.5.5 of router 1.5, which corresponds to the route with the lowest metric along the route.

An instruction is sent from buffer 1.5.1 to block 1.5.3.3 arithmetic-4 "" logical device 1.5.3 to recalculate the current metric of the involved route 100.10 (Fig. 2).

Calculate in block 1.5.3.3 of the arithmetic-logical device 1.5.3 (Fig. 2) the value of the total flow of packets sent along each route by the formula:

where N is the number of packets sent along the route 100.10, Sz _111.1 is the size of the packet n _111.1 .

Calculate in block 1.5.3.3 of the arithmetic logic device 1.5.3 the value of the changed current throughput of the involved route according to the formula:

The calculated value of the changed throughput of the enabled route BW ' _{10_tec is sent} from block 1.5.3.3 to block 1.5.3.1 of the arithmetic logic device 1.5.3.

Use the modified bandwidth value BW ' _{10_tec of the} involved route as input to recalculate its metric.

The described operations are repeated until the packet buffer 1.5.1 is completely emptied (Fig. 2).

The possibility of achieving the technical result is confirmed by the results of experimental verification (Fig. 3, Fig. 4, Fig. 5, Fig. 6)

The size of the total flow of sent packets FL _total (Fig. 3) at zero iteration is set equal to FL _total = 0 kbps (kbps is a value equal to the number of kilobits transmitted per second). At each subsequent iteration, it increases by a predetermined Δfl = 720 kbps (Fig. 3). In the absence of a packet flow, the values of the current throughputs of the routes BW _{i_tec} , BW _{j_tec} are equal to the nominal BW _{i_tec} = 10000 kbps and BW _{j_tec} = 5000 kbps, respectively.

Following formula (3), the values of route metrics M _i = 100, M _j = 200 are calculated. A comparison is made M _i <M _j , a result is obtained, based on which the stream is transmitted in the first iteration FL _total = 720 kbps along route 10. With the transmission of the first stream (Fig. 4), the router packet buffer is released and the route metrics are recalculated taking into account the change in the current throughput route ability 100.10, which is calculated by the formula (2). With the transmission of the next stream along the route, the value of its metric calculated by the formula (3) increases (Fig. 3, Fig. 5). Next, ΔFL is incremented iteratively.

At the seventh iteration (Fig. 3, Fig. 5), the inequality M _i > M _j is satisfied. When such a moment comes, the ratio of the route metrics is calculated (Fig. 3) according to the formula:

where M _i , M _j - metrics of available routes.

On the following iterations, based on the calculated ratio of metrics K _M , the total packet flow FL _{total is} split and the private flows FL _i , FL _{j are formed} (Fig. 3) based on the ratios:

Further, the generated streams FL _i , FL _j are transmitted simultaneously along the corresponding routes until the moment the buffer 400 (Fig. 2) of the router is emptied.

Packet losses (Fig. 3, Fig. 6) for this distribution begin only at the twenty-first iteration when the route capacity is completely exhausted and the inequality is satisfied:

where FL _total is the total flow of sent packets, and BW _i + BW _j is the sum of the throughput of available routes.

The results obtained confirm the claimed goal of the invention to provide more rational use of the bandwidth of available routes and reduce the probability of packet loss.

Claims (3)

1. A method for dynamic routing of traffic in a communication network, which consists in the fact that preliminarily at the sending node, messages from the source node are received, the message is divided into packets, their number is stored and placed in a queue for transmission, in addition, a routing table is formed and transmitted packets along several routes in accordance with the generated routing table, characterized in that at the sending node, before transmitting each of the received packets, its parameters are read and stored, a routing table with a dynamic metric is formed, which is adapted to the specified packet parameters, after which each packet is sent along the route defined by the generated routing table, then the metric of the involved routes is recalculated and the actions are repeated until the queue for packet transmission is released. 2. The method according to claim 1, characterized in that the dynamic metric of the m-route is calculated by the formula:

Where

is the current capacity of the m-route, BW_m is the nominal throughput of the m-route in the absence of transmission,

- the increment in the volume of the incoming packet flow, compare M_i, M_j, distribute packets to the route with the lowest metric. 3. The method according to claim 1, characterized in that in order to adapt the routing table to the parameters of the packet, the value of the size of packets in the queue for transmission is selected as a parameter, a table of correspondence between the size of the packet and its number in the queue is formed, a table of correspondence of the route number is formed, and its dynamic metrics.

Images