CN115208837A - Message scheduling method and system - Google Patents

Abstract

The invention relates to the technical field of communication, and provides a message scheduling method and a message scheduling system. Wherein the method comprises: when a message is sent, carrying a preset sending period and an actual sending period of the message in the message; when a message is received, judging whether the received message is a delay message or not according to a preset sending period and an actual sending period of the message; if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message. The invention is used for judging whether the message is a delay message or not when receiving the message by carrying the preset sending period in the message, and carrying out fault-tolerant forwarding on the delay message after the receiving is finished so as to realize fault-tolerant scheduling of the message, ensure normal transmission of data stream and ensure end-to-end deterministic scheduling.

Description

Message scheduling method and system

[ technical field ] A

The present invention relates to the field of communications technologies, and in particular, to a method and a system for scheduling packets.

[ background ] A method for producing a semiconductor device

The deterministic network technology has become one of the research and attention hotspots in academic and industrial circles nowadays, and has a wide research space in the academic field and a huge market prospect in the industrialization aspect. The core of a deterministic network is to guarantee end-to-end bandwidth, delay and jitter of the traffic flow. An IETF (Internet Engineering Task Force) established a DetNet (Deterministic Network) working group 10 months in 2015, and is dedicated to extending a TSN (Time sensitive Network) from a local area Network to a wide area Network to implement a determined transmission path in an L2/L3 Network, so as to provide worst case bounds of delay, packet loss and jitter or a determined delay.

DetNet proposes a standard draft applicable to LDN (Large-scale Deterministic Network) deployment. On the basis of keeping the advantage of statistical multiplexing of the traditional IP (Internet Protocol) forwarding technology, the LDN technology can realize strict guarantee of the end-to-end delay upper bound and the jitter upper bound, and provides network service support for future application scenes such as 5G slices, industrial Internet and the like.

The core idea of DetNet is to control the forwarding behavior of each data packet at each hop of equipment, and once the time of a given packet entering a certain hop of equipment is determined, the time of the packet exiting the certain hop of equipment can be determined. The data packet only needs to carry the current cycle number of the sending device before each hop is sent. After receiving the data message, the downstream node can determine in which local period the received message needs to be forwarded again according to the period mapping relation table. Each pair of adjacent LDN routers guides the data packet forwarding behavior of the subsequent LDN routers through a stable periodic mapping relation. For example: the data packet is forwarded from the node a to the node C through the node B, the node a sends the data packet P to the node B within the cycle number X, and the node B has received all the data packets P with the cycle number X from the node a before the end time of the cycle number Y, so that the node B can forward the data packet to the node C within the cycle number Y + 1. The period number X of the node A and the period number Y +1 of the node B form a period mapping relation. On the forwarding layer, the message carrying the cycle number X received by the ingress interface of the node B is replaced by Y +1 at the egress interface and sent out. The cycle number X is the cycle number inside the node A, and the cycle numbers Y and Y +1 are the cycle numbers inside the node B.

In the prior art, the traffic of a deterministic data stream in a period cannot be forwarded across multiple periods on a certain network device, but in an actual network, situations such as inconsistent upstream and downstream node capabilities, unexpected delay in transmission between nodes, timeout retransmission of a node on a packet, and the like may occur, which may cause periodic crossing or delay of the data stream in the forwarding process, and how to ensure end-to-end deterministic scheduling needs to be studied when the periodic crossing or delay occurs in the data stream. Such as the following:

in case one, if the sending rate of the node B is 100M and the sending rate of the upstream node a is 1000M, the node B may not completely send all X packets marked by the node a in one period within one period T, and the node B may need to send across multiple periods.

In case two, the node B fails to receive all the X packets marked by the node a within the expected period Y, i.e. the period Y is already exceeded when part of the packets marked by X are received by the node B.

And in the third case, the opposite end of the message sent by the node A does not receive the message, the node A retransmits the message, and if the retransmitted message is still in the expected time delay and jitter, the requirement of deterministic scheduling is still met.

In view of this, overcoming the drawbacks of the prior art is a problem to be solved urgently in the art.

[ summary of the invention ]

The technical problem to be solved by the invention is that in the prior art, when the data flow has period crossing or delay in the forwarding process, the deterministic scheduling from end to end cannot be ensured.

The invention further aims to solve the technical problem of providing a fault-tolerant processing method and a fault-tolerant processing system for message deterministic scheduling.

The invention adopts the following technical scheme:

in a first aspect, the present invention provides a packet scheduling method, including:

when a message is sent, carrying a preset sending period and an actual sending period of the message in the message;

when a message is received, judging whether the received message is a delay message or not according to a preset sending period and an actual sending period of the message;

if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message.

Preferably, the determining whether the received packet is a delayed packet according to the preset sending period and the actual sending period of the packet specifically includes:

if the preset sending period of the message is different from the actual sending period, the message is a delay message;

otherwise, obtaining a preset arrival period of the message according to a preset period mapping relation and a preset sending period carried in the message, and judging whether the received message is a delay message or not according to the preset arrival period of the message.

Preferably, the determining, according to the preset arrival period of the packet, whether the received packet is a delayed packet specifically includes:

when the actual arrival period of the message is less than or equal to the preset arrival period, the message is not a delay message;

when the actual arrival period of the message is greater than the preset arrival period, judging according to the actual arrival period of a first message of the data stream to which the message belongs, and if the actual arrival period of the first message is greater than the preset arrival period and the difference between the actual arrival period of the first message and the preset arrival period is greater than or equal to a preset difference, judging that the message is not a delay message;

otherwise, the message is a delay message.

Preferably, after the receiving of the packet is finished, the fault-tolerant forwarding of the packet specifically includes:

if the reserved bandwidth of the corresponding outgoing interface of the node in the first sending period is larger than the total bandwidth of all the messages waiting for normal forwarding, after all the messages waiting for normal forwarding are forwarded, the messages waiting for fault-tolerant forwarding are sequentially forwarded in the first sending period according to the receiving sequence of the messages waiting for fault-tolerant forwarding until the reserved bandwidth of the corresponding outgoing interface is exhausted, or all the messages waiting for fault-tolerant forwarding are forwarded to be finished;

if the message waiting for fault-tolerant forwarding still exists after the first sending period, taking the next sending period of the first sending period as a new first sending period, and carrying out fault-tolerant forwarding on the message waiting for fault-tolerant forwarding in the new first sending period, wherein when carrying out fault-tolerant forwarding for the first time, the first sending period after the message is received is taken as the first sending period.

Preferably, after the receiving of the packet is finished, the fault-tolerant forwarding of the packet is performed, further including:

and carrying a delay tolerance value in the message, and reducing the delay tolerance value according to the number of cycles delayed in fault-tolerant forwarding every time the message is subjected to fault-tolerant forwarding until the message reaches a destination node or the message is not forwarded until the delay tolerance value carried in the message is less than or equal to a preset minimum value.

Preferably, when the node needs to retransmit the packet, the method further includes:

and determining a new delay tolerance value according to the delay tolerance value carried in the message sent last time and the overtime period of the message, wherein the new delay tolerance value is carried in the retransmitted message and is used for fault-tolerant forwarding judgment in the subsequent forwarding process.

Preferably, the method further comprises:

each forwarding node is provided with a fault-tolerant receiving queue and a fault-tolerant sending queue for realizing scheduling and forwarding of delay messages;

when a delay message is received, the message is added into a fault-tolerant receiving queue, and in the next sending period of the received delay message, the message is moved from the fault-tolerant receiving queue to a fault-tolerant sending queue so as to carry out fault-tolerant forwarding on the message.

Preferably, the message includes one or more of a source address, a destination address, a sending period, a size of the data flow and a deterministic path of the message.

Preferably, before forwarding the packet, the method further includes:

configuring clock synchronization of each node required in the message forwarding process; determining basic properties of the data stream; determining the delay tolerance value of each message in the data stream; and calculating a deterministic path of the data flow according to the source address and the destination address of the data flow so as to forward the message carrying the data flow.

In a second aspect, the present invention further provides a packet scheduling system, including an upstream node and a downstream node, where:

when the upstream node sends the message, the message carries a preset sending period and an actual sending period of the message;

when receiving a message, the downstream node judges whether the received message is a delay message according to a preset sending period and an actual sending period of the message; if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message.

In a third aspect, the present invention further provides a packet scheduling apparatus, configured to implement the fault-tolerant processing method for packet deterministic scheduling in the first aspect, where the apparatus includes:

at least one processor; and a memory communicatively coupled to the at least one processor; wherein the memory stores instructions executable by the at least one processor, the instructions being executable by the processor for performing the fault-tolerant processing method for packet deterministic scheduling according to the first aspect.

In a fourth aspect, the present invention further provides a non-volatile computer storage medium storing computer-executable instructions, which are executed by one or more processors, for implementing the fault-tolerant processing method for packet deterministic scheduling according to the first aspect.

The invention is used for judging whether the message is a delay message or not when receiving the message by carrying the preset sending period in the message, and carrying out fault-tolerant forwarding on the delay message after the receiving is finished so as to realize fault-tolerant scheduling of the message, ensure normal transmission of data stream and ensure end-to-end deterministic scheduling.

[ description of the drawings ]

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings required to be used in the embodiments of the present invention will be briefly described below. It is obvious that the drawings described below are only some embodiments of the invention, and that for a person skilled in the art, other drawings can be derived from them without inventive effort.

Fig. 1 is a first message scheduling method in the prior art according to an embodiment of the present invention;

fig. 2 is a second message scheduling method in the prior art according to an embodiment of the present invention;

fig. 3 is a schematic flowchart of a message scheduling method according to an embodiment of the present invention;

fig. 4 is a flowchart illustrating a message scheduling method according to an embodiment of the present invention;

fig. 5 is a flowchart illustrating a message scheduling method according to an embodiment of the present invention;

fig. 6 is a schematic view of a scene link to which a message scheduling method according to an embodiment of the present invention is applied;

fig. 7 is a flowchart illustrating a message scheduling method according to an embodiment of the present invention;

fig. 8 is a flowchart illustrating a message scheduling method according to an embodiment of the present invention;

fig. 9 is a flowchart illustrating a message scheduling method according to an embodiment of the present invention;

fig. 10 is a schematic diagram illustrating queue conversion in a process of a message scheduling method according to an embodiment of the present invention;

fig. 11 is a process diagram of a message scheduling method according to an embodiment of the present invention;

fig. 12 is a schematic structural diagram of a message scheduling system according to an embodiment of the present invention;

fig. 13 is a schematic diagram of an architecture of a packet scheduling system according to an embodiment of the present invention;

fig. 14 is a schematic structural diagram of a message scheduling apparatus according to an embodiment of the present invention.

[ detailed description ] embodiments

In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.

For the understanding of the embodiments, the packet scheduling in the prior art is described herein, and there are two manners of LDN scheduling and CQF scheduling in the prior art, where the CQF scheduling model is shown in fig. 1, a global time is divided into equal-length time slots, that is, periods, and data transmission needs to follow the following rules:

the time slot of the message transmitted by the upstream node is the same as the time slot of the message received by the downstream neighbor node;

the message received by each node in a certain time slot is transmitted in the next time slot;

the network nodes are time-synchronized, and the link delay is less than 1 cycle.

The LDN scheduling method is expanded on the basis of CQF so as to support large-scale deterministic networks. In the LDN model, as shown in fig. 2, the global time is still divided into equal-length time slots, i.e. periods, and the data transmission needs to follow the following rules:

all data packets sent by the upstream node in the period X are received in the period Y of the downstream node and are sent out in the period Y +1 to form a period mapping X- > Y +1;

when the upstream node sends, the sending period X is marked in the message, and after the downstream node receives the message, the period Y +1 is marked in the message and sent out similarly to label switching.

The network node clocks are synchronous, the periods are equal, and the period is marked as T in the invention.

When the upstream node continuously sends the data stream to the downstream node in the period X, the downstream node continuously receives the data stream in a period range and finishes receiving in the period Y of the downstream node.

In addition, the technical features involved in the respective embodiments of the present invention described below may be combined with each other as long as they do not conflict with each other.

Example 1:

embodiment 1 of the present invention provides a packet scheduling method, as shown in fig. 3, including:

instep 201, when sending a message, the message carries a preset sending period and an actual sending period of the message.

The preset sending period carrying the message may be a period carrying an exact time, or may be carried in the message in the form of a period number, a period mark, or the like, so as to reduce the bit size occupied by the period in the message.

The preset sending period is obtained by analyzing the sending period of the data stream to which the message belongs and the message forwarding path by a person skilled in the art. One specific implementation is provided herein as follows: when the source node sends a message, the actual sending period of the message is taken as a preset sending period to be carried in the message, and a technical person in the art analyzes and formulates the message together according to the forwarding capability of each node and the transmission rate of the sublink, or establishes a preset sending period mapping relation of each node through a controller or a network self-learning mode. And according to the preset period mapping relation, sequentially mapping to obtain the preset sending period of the message at each node.

Wherein a data stream is sent by one or more packet bearers.

Instep 202, when a message is received, it is determined whether the received message is a delayed message according to a preset sending period and an actual sending period of the message.

The delay packet is usually caused by inconsistent forwarding capabilities of upstream and downstream nodes, unexpected delay of the network, or retransmission of the packet, so that the packet cannot be sent at a preset time or arrive at the preset time.

Instep 203, if the message is a delay message, after the message is received, the fault-tolerant forwarding is performed on the message.

The fault-tolerant forwarding is a distinctive expression distinguished from a normal message forwarding process, and is still a message forwarding process.

One implementation of the fault-tolerant forwarding is as follows: and scheduling and forwarding the delay message in the first period after the message is received.

The embodiment of the invention is used for judging whether the message is a delay message or not when receiving the message by carrying the preset sending period and the actual sending period in the message, and carrying out fault-tolerant forwarding on the delay message after the receiving is finished so as to realize the fault-tolerant scheduling of the message, ensure the normal transmission of data stream and ensure the deterministic scheduling from end to end.

The delay of the message generally includes a sending delay and a receiving delay, and in the above embodiment, one implementation manner of determining whether the received message is a delayed message according to the preset sending period of the message is as follows:

comparing a preset sending period carried in a message with an actual sending period, if the preset sending period and the actual sending period are different, the message is considered to be a delayed message, the method is to perform judgment according to the sending period of the message, although the judgment method can identify the message with delayed sending, the method cannot accurately judge the condition of receiving delay, in an actual condition, there may be no delay of the sending period when the message is sent, but the message receiving delay is caused by delay in a link transmission process, and in this case, fault-tolerant scheduling needs to be performed on the message, for this problem, in combination with the above-mentioned embodiment, there is a following preferred embodiment, namely, judging whether the received message is a delayed message according to the preset sending period and the actual sending period of the message, as shown in fig. 4, specifically including:

in step 301, if the preset sending period of the message is different from the actual sending period, the message is a delayed message.

Instep 302, otherwise, according to a preset period mapping relationship and a preset sending period carried in the packet, obtaining a preset arrival period of the packet at the node.

Instep 303, it is determined whether the received packet is a delayed packet according to the preset arrival period of the packet.

The preset period mapping relationship is analyzed and formulated by a person skilled in the art according to the forwarding capability of each node and the transmission rate of the sublink together, or is established in a controller or network self-learning manner. In an actual situation, although there is a transmission delay in a packet, due to different transmission rates of links, the packet can be received in a preset arrival period, that is, the packet only has a transmission delay and does not have a reception delay, which is also generally referred to as packet jitter. The preferred embodiment also ensures the accuracy of the judgment of the delayed arrival of the message by comparing the preset arrival period of the message with the actual arrival period of the message, so as to ensure the correct proceeding of the subsequent message fault-tolerant forwarding. In the preferred embodiment, the preset arrival period of the next node is obtained through the preset sending period of the previous node, and the preset arrival period of the packet is associated with the passed node, so that a more accurate preset arrival period is obtained, and the accuracy of the delayed arrival judgment of the packet is further ensured.

In practical situations, forwarding of deterministic data streams is usually implemented in a circular queue manner, that is, clock synchronization is maintained for each node required for forwarding data streams, and the same clock length is used as a period value, when a packet is transmitted, a period carried in the packet is obtained by circularly numbering a timeline with the period value as an interval, and if T is used as the period value, the timeline of each node is circularly numbered with n periods, the method is represented as: within the period T to nT there are n cycles, each with a length of T, numbered inturn 1 to n, while within the period nT +1 to 2nT there are also n cycles, each with a length of T, numbered inturn 1 to n.

In the case of cyclic cycle of the cycle number, how to judge the delayed sending of the packet, in combination with the above embodiment, there is the following preferred embodiment, where judging whether the received packet is a delayed packet according to the preset arrival cycle of the packet, as shown in fig. 5, specifically includes:

instep 401, when the actual arrival period of the packet is less than or equal to the preset arrival period, the packet is not a delayed packet.

Instep 402, when the actual arrival period of the packet is greater than the preset arrival period, determining according to the actual arrival period of the first packet of the data stream to which the packet belongs, and if the actual arrival period of the first packet is greater than the preset arrival period and a difference between the actual arrival period of the first packet and the preset arrival period is greater than or equal to a preset difference, determining that the packet is not a delay packet.

Instep 403, otherwise, the message is a delay message.

When the period is not numbered circularly, the effect of judging delayed sending can be achieved only by judging whether the actual arrival period is less than or equal to the preset arrival period.

The preset difference is analyzed by a person skilled in the art according to the cycle number.

But the period number does not increase indefinitely due to the period cycle number, and the timeline will subsequently return to the start of the period when the maximum number of periods is reached. In this embodiment, an actual arrival period of a first packet of a data stream is taken into consideration, an overall time period of arrival of the data stream is established and obtained through a currently received packet and the first packet of the data stream, and when the overall time period is much longer than a preset arrival period, the packet is considered not to be a delayed packet. Therefore, the message delay judgment under the condition of periodic cycle is realized.

In the above embodiment, the fault-tolerant forwarding is performed on the delayed packet in the first sending period after the packet reception is finished, which can maximally reduce the transmission delay of the data stream, but in an actual situation, the egress interface of the node usually has a bandwidth limitation in a single sending period, and cannot forward the packet indefinitely. That is, the forwarding time of the packet also needs to be determined according to the bandwidth capability of the node, and for this situation, in combination with the above embodiment, there is the following preferred embodiment, that is, after the end of receiving the packet, the fault-tolerant forwarding is performed on the packet, which specifically includes:

if the reserved bandwidth of the corresponding outgoing interface of the node in the first sending period is larger than the total bandwidth of all the messages waiting for normal forwarding, after all the messages waiting for normal forwarding are forwarded, the messages waiting for fault-tolerant forwarding are sequentially forwarded in the first sending period according to the receiving sequence of the messages waiting for fault-tolerant forwarding until the reserved bandwidth of the corresponding outgoing interface is exhausted, or the forwarding of all the messages waiting for fault-tolerant forwarding is finished.

And if the message waiting for fault-tolerant forwarding still exists after the first sending period, taking the next sending period of the first sending period as a new first sending period, and carrying out fault-tolerant forwarding on the message waiting for fault-tolerant forwarding in the new first sending period, wherein when carrying out fault-tolerant forwarding for the first time, the first sending period after the message is received is taken as the first sending period.

The term "first" is not intended to be limited in any way, and thus, is used in a descriptive sense only to facilitate the identification of different individuals within a class of objects and should not be interpreted in a sequential or other manner with a special limitation.

In the preferred embodiment, the number of the messages capable of fault-tolerant forwarding is determined according to the reserved bandwidth of the outgoing interface of the node, and the messages are forwarded after the reception is finished. The method and the device have the advantages that the message which is delayed and sent by the previous node is forwarded as soon as possible within a tolerable range of bandwidth, so that the normal forwarding of the message is guaranteed, and the end-to-end time delay is reduced. Meanwhile, the preferred embodiment schedules and forwards the delay message after the normal message is scheduled preferentially, so that when the jittered message is received, the forwarding of the normal message is preferentially ensured, and the delay message is forwarded according to the forwarding capability of the node.

In an actual situation, a time delay that can be reduced by performing fault-tolerant forwarding on a packet still depends on an arrival period of the packet, and when a delay time of the packet is too long, even if the delay time is subjected to fault-tolerant forwarding, the end-to-end time delay still cannot be maintained within a normal range, and for this situation, in combination with the above embodiment, the following implementation manner is provided, which specifically includes:

according to the network condition and the requirement, a uniform delay tolerance value is preset for all messages in a single data stream by a person skilled in the art, when the delay period of the message exceeds the delay tolerance value, the message is not forwarded, otherwise, the message is subjected to fault-tolerant forwarding.

In another implementation, the delay tolerance value may also be preset by a person skilled in the art according to network conditions and requirements, and different delay tolerance values are preset for the sub-links between each segment of adjacent nodes, when receiving the packet, if the delay of the packet exceeds the corresponding delay tolerance value, the packet is not forwarded, otherwise, the packet is forwarded in a fault-tolerant manner.

The above two implementation manners are mainly implemented by determining a delay tolerance value of a single node, but in an actual situation, when a delay time of a packet at a single node is short, but nodes with delay are many, the transmission efficiency of the packet is also affected, and an end-to-end delay is increased, and in view of this problem, in combination with the above embodiment, there is the following preferred embodiment, that is, after receiving the packet is ended, performing fault-tolerant forwarding on the packet, further including:

carrying a delay tolerance value in the message, and reducing the delay tolerance value according to the number of cycles delayed in fault-tolerant forwarding each time the message is subjected to fault-tolerant forwarding until the message reaches a destination node or the message is not forwarded until the delay tolerance value carried in the message is less than or equal to a preset minimum value; and the source node carries an initial delay tolerance value in the message.

The initial delay tolerance value and the preset minimum value are obtained by analyzing together according to the data stream to which the message belongs and the end-to-end delay requirement in the network by the technicians in the field.

When the message jitters, namely the message is transmitted in a delayed manner at the last node, but the delay tolerance value is determined according to the number of the delayed periods in the fault-tolerant forwarding under the condition that the message is transmitted in the preset transmission period, and when the message is transmitted in the preset transmission period, the delay tolerance value is not changed if no delay period exists.

In the preferred embodiment, the delay tolerance value is carried in the message and is processed during each forwarding, so that the delay tolerance value in the message changes in real time along with the number of delayed forwarding times and the delay period, thereby taking the whole delay in the message transmission process into consideration, making the fault-tolerant scheduling of the message more accurate, and ensuring that the end-to-end delay does not exceed the range.

In practical situations, there are not only delay and jitter of the packet, but also retransmission of the packet, and in view of this problem, in combination with the above embodiments, there are the following preferred embodiments, that is, when a node needs to retransmit the packet, the method further includes:

and determining a new delay tolerance value according to the delay tolerance value carried in the message sent last time and the overtime period of the message, wherein the new delay tolerance value is carried in the retransmitted message and is used for fault-tolerant forwarding judgment in the subsequent forwarding process.

In this embodiment, when a message is retransmitted, the delay tolerance value of the message is updated, so that when the message is retransmitted, the fault-tolerant scheduling of the message can also be implemented.

To facilitate scheduling, the following preferred implementations also exist:

each forwarding node is provided with a fault-tolerant receiving queue and a fault-tolerant sending queue for realizing scheduling and forwarding of delay messages.

When a delay message is received, the message is added into a fault-tolerant receiving queue, and in the next sending period of the received delay message, the message is moved from the fault-tolerant receiving queue to a fault-tolerant sending queue so as to carry out fault-tolerant forwarding on the message.

The implementation mode realizes the fault-tolerant forwarding scheduling of the messages through the fault-tolerant receiving queue and the fault-tolerant sending queue, thereby ensuring the orderly forwarding of the messages.

In order to further ensure the stability of message forwarding, one or more items of a source address, a destination address, a sending period, the size of the data flow to which the message belongs, and a deterministic path of the message are also included in the message.

The message carries the information to ensure the stable transmission of the message.

Before forwarding the message, the method further includes:

configuring clock synchronization of each node required in the forwarding process; basic properties of the data stream are determined. Determining the delay tolerance value of each message in the data stream; and calculating a deterministic path of the data flow according to the source address and the destination address of the data flow so as to forward the message carrying the data flow.

The basic attributes of the data stream include a source address, a destination address, a sending period of the message, and the size of the data stream is equal to information carried in the message or required to be used for forwarding the message, and the delay tolerance value of each message in the data stream is obtained by decomposing the delay upper limit of the data stream.

One implementation way of calculating the deterministic path by the source address and the destination address of the data stream is as follows: and establishing a corresponding target function and a corresponding constraint function, and obtaining a deterministic path through mathematical model planning calculation, wherein the deterministic path of the data flow is the deterministic path for carrying each message of the data flow.

Example 2:

based on the method described inembodiment 1, the invention combines with a specific application scenario and uses technical expressions in a related scenario to describe an implementation process in a characteristic scenario.

In this embodiment, a link shown in fig. 6 in a CQF (Cyclic Queuing and Forwarding) scheduling scenario is taken as an example, where a node a is a source node for Forwarding a packet, and a node D is a destination node for Forwarding the packet.

Before forwarding a packet, that is, at an initialization stage of a network, the following steps are performed, as shown in fig. 7, which specifically include:

instep 501, clock synchronization of each network node is configured.

Instep 502, the data flow f is determined_i Including the data flow f_i The source address, the destination address, the sending period, the size and the time delay upper limit, and the data flow f in a single period T is calculated_i Transmitted data flow f_i .band。

Instep 503, the path of the data stream is determined and the upper delay bound f is decomposed_i Latency. The controller calculates a deterministic path according to the source address and the destination address of the data stream and the corresponding constraint parameters, and decomposes the upper limit of the time delay to obtain a time delay tolerance value. Decomposing the delay ceiling of the data stream according to the deterministic path to the expected delay f_i Latency. Exp and delay tolerance value f_i Et, wherein the delay tolerance value obtained by the decomposition is the initial delay tolerance value.

Instep 504, network node attributes are set, and the controller determines and issues the bandwidth that each node needs to reserve for deterministic forwarding. And initializing each CQF queue, fault-tolerant receiving queue and fault-tolerant sending queue of the network node. And the CQF queues are queues in original CQF scheduling and are used for normal message forwarding scheduling.

Instep 505, a periodic mapping relationship between network nodes is established. And establishing a periodic mapping relation in a controller or network self-learning mode.

And after the network initialization is finished, forwarding the message of the data stream. Aiming at a source node, before sending a message of a data stream, carrying a message mark (S, C) and a delay tolerance value f in the message_i And et, setting the delay tolerance value carried by the source node as an initial delay tolerance value, adopting the same value for the S mark and the C mark, putting the message into a CQF queue with the corresponding number, and waiting for the forwarding time of the message to arrive. In the message marks (S, C), S is a preset sending period mark of the corresponding message, and C is an actual sending period mark of the corresponding message.

In each period, each node needs to perform message transmission scheduling on each CQF queue, fault-tolerant receive queue, and fault-tolerant transmit queue under the node, as shown in fig. 8, specifically including:

instep 601, the bandwidth accumulation value BW is initialized to 0, and the process proceeds to step 602.

Instep 602, sequentially accessing the packets in the CQF send queue, and accumulating the bandwidth i.band required for sending the packet i into the BW each time one packet i is accessed, that is, making BW = BW + i.band;step 603 is entered.

Instep 603, it is determined whether BW is less than or equal to a bandwidth v.band reserved by a corresponding egress interface of the node, if BW is less than or equal to v.band,step 604 is entered, otherwise,step 606 is entered.

Instep 604, the accessed message i is sent normally in the sending period; the normal sending is to move the message out of the CQF sending queue and send the message directly; step 605 is entered.

In step 605, determining whether all the messages in the CQF transmission queue have been normally transmitted, if so, enteringstep 607 to perform fault-tolerant scheduling of the messages in the fault-tolerant transmission queue; otherwise,step 602 is entered, and the access to the packet in the CQF transmission queue is continued.

Instep 606, the message i is not sent, and the C in the (S, C) flags in all the messages in the CQF send queue is marked as a reserved value, and is put into the fault-tolerant send queue, waiting for the next week to perform scheduling sending, and ending the scheduling sending process of this period.

Instep 607, sequentially accessing the packets in the fault-tolerant transmission queue, and accumulating the bandwidth i.band required for transmitting the packet i into the BW every time one packet i is accessed, that is, making BW = BW + i.band;step 608 is entered.

Instep 608, it is determined whether BW is less than or equal to a bandwidth v.band reserved by a corresponding egress interface of the node, and if BW is less than or equal to v.band,step 609 is entered; otherwise, go to step 610.

Instep 609, in the sending period, marking C in (S, C) marks in the message as the current period number and taking the surplus of N, and moving the message out of the fault-tolerant sending queue and directly sending the message; wherein, N is a fixed value set by a person skilled in the art according to the requirement of a message sending period and is used for circularly numbering the period;step 610 is entered.

Instep 610, it is determined whether all messages in the fault-tolerant transmission queue have been transmitted, and if all messages have been transmitted, the scheduling transmission process of this period is ended; otherwise,step 607 is entered to continue accessing the message in the fault-tolerant transmission queue.

Instep 611, the message i and the subsequent messages in the fault-tolerant transmission queue are not transmitted, the scheduling transmission process of the period is ended, and the message is reserved to the next transmission period and then scheduled.

In each period, each node also needs to perform message receiving scheduling on each CQF queue, fault-tolerant receive queue, and fault-tolerant transmit queue under the node, as shown in fig. 9, which specifically includes:

instep 701, according to the period mapping relationship of the interface, mapping the S tag of the message tag (S, C) in the received message to obtain a preset sending period S ', and then obtaining a preset arrival period S' -1.

Instep 702, the tag (S, C) carried by the message is checked, and the arrival period t of the first message with the same S tag in each message is recorded_f 。

Instep 703, it is determined whether the packet is a delay packet according to the arrival period of the packet. The method for judging the message sending is specifically that if the S and the C in the message mark are different, the message is a delay message, otherwise, the judgment is carried out according to the arrival period of the message, and specifically: when the arrival period t of the message_curr Less than S' and t_curr Greater than t_f Or t is_curr Is greater than S' and (t)_f -S') is greater than or equal to a preset difference, then said message is not a delayed message, otherwise said message is a delayed message. If the message is a delay message, go to step 704; otherwise step 706 is entered.

Instep 704, the delay tolerance value is modified. Calculating the number of delayed cycles, when t_curr Greater than S', the number of cycles of delay is t_curr - (S' -1), when t_curr Less than S', the number of delayed cycles is t_curr + N- (S' -1), reducing the delay tolerance value by the number of delayed cycles, judging whether the delay tolerance value is less than or equal to a preset minimum value, if the delay tolerance value is less than or equal to the preset minimum value, enteringstep 707, otherwise, enteringstep 705; wherein, N is a fixed value set by a person skilled in the art according to a message sending period requirement, and is used for circularly numbering periods.

Instep 705, the message tag is replaced, the corresponding (S, C) tag is replaced with (S ', X'), where X 'is a reserved value, and X' is filled when the message is to be sent, and is put into a fault-tolerant receiving queue, and waits for a sending period to arrive and performs fault-tolerant forwarding.

In step 706, the message flag is replaced, the corresponding message flag is modified to (S ', S'), and the message flag is placed in the corresponding CQF queue to wait for normal scheduling transmission of the message.

Instep 707, the transmission fails, the message is discarded, the message is not forwarded any more, and the transmission scheduling of the message is ended.

In the receiving and sending scheduling of the node packet, role switching of each CQF queue is also involved, which specifically includes:

when entering the period from the previous period, the CQF queue used for receiving the message in the previous period is converted into a CQF sending queue, and other CQF queues are used as receiving queues.

Fig. 10 is a schematic diagram of CQF queues, fault-tolerant receive queues, and fault-tolerant receive queues in the process of sending and receiving a message by an intermediate node, such as node B in fig. 10, wherequeue 1,queue 2, andqueue 3 are CQF queues, and there are also fault-tolerant receive queues and fault-tolerant send queues.

In the first period (i.e. t period), of the 3 CQF packet queues corresponding to the egress port of the node B,queue 1 andqueue 2 are packet receiving queues, andqueue 3 is a packet sending queue. In the corresponding 2 fault-tolerant queues, the fault-tolerant message receiving queue stores node B judgment delay messages, such as delay messages M1 and M2, and the fault-tolerant message sending queue is empty.

In the second period (i.e., t +1 period), of the 3 CQF packet queues corresponding to the egress port of the node B, thequeue 2 and thequeue 3 are packet receiving queues, and thequeue 1 is a packet sending queue. That is,queue 1 is converted from the receive queue of the last cycle (t cycles) to the transmit queue, andqueue 3 is converted from the message transmit queue to the message receive queue. The fault-tolerant message receiving queue stores the abnormal message M3 received in the period. M1 and M2 messages received in a period (t period) on the fault-tolerant message receiving queue are linked to the fault-tolerant message sending queue to wait for scheduling and forwarding.

In the third period (i.e., t +2 period), of the 3 CQF packet queues corresponding to the egress port of the node B, thequeue 1 and thequeue 3 are packet receiving queues, and thequeue 2 is a packet sending queue. That is,queue 2 is converted from the receive queue of the last cycle (t +1 cycle) to the transmit queue, andqueue 1 is converted from the message transmit queue to the message receive queue. In this period, the fault-tolerant message receiving queue is empty when the abnormal message is not received. M3 messages received in a period (t +1 period) on the fault-tolerant message receiving queue are linked to the fault-tolerant message sending queue to wait for scheduling and forwarding.

When the source node performs the timeout retransmission of the packet, this embodiment further includes: the source node is according to f in the message_i Let et value and message timeout timestamp new delay tolerance value, new delay tolerance value is f_i The value obtained by subtracting the message timeout time from latency. And generating message marks (S, C) by taking the actual sending period when the source node retransmits the message as S and C, and carrying the message marks in the message. And the node A marks a new delay tolerance value according to the delay tolerance value carried in the last message and the overtime time of the message. In general: the delay tolerance value subtracts the number of message timeout periods. And the message is put into a corresponding CQF queue to wait for the arrival of the retransmission time of the message.

The effect of the fault-tolerant scheduling according to the embodiment of the present invention will be demonstrated by the transmission process of the data stream in fig. 6, specifically, as shown in fig. 11, the data stream f_A From node A to node C via node B, data flow f_A Carried by multiple packets. And the node A, the node B and the node C adopt the same period value T and keep clock synchronization.

The cycle numbers of the cycles of the node A are respectively t_A ，t_A +1，t_A +2，…，t_A + n; the cycle numbers of the respective cycles of the node B are t_B ，t_B +1，t_B +2，…，t_B + n; the cycle numbers of the cycles of the node C are respectively t_C ，t_C +1，t_C +2，…，t_C +n。

Data flow f for node A_A Data flow f to node C, node A via node B_A At cycle number t_A Is sent out in the period of (A), the corresponding message mark (S, C) is (X)_A ，X_A ) The period numbers of the nodes are sequentially numbered, the message marks are circularly numbered according to the period numbers, namely the message marks are made to be the period numbers and the surplus is obtained according to N, namely X_Ａ ＝t_A mod (N), N being the maximum value of the numbers in the cycle period numbers.

Data flow f_A The transmission time range at node A is T_A I.e., the rectangular box filled with diagonal lines on node a in fig. 11. T is a unit of_A A time less than one period T, the period being numbered T_A In general, the transmission time range of the node A is T_A Data stream f of_A The carried message is marked as X_A ，X_A The message tag can be carried in a message tag, a VLAN ID, reserved bytes or other positions, and the position of the message tag in the message is not limited by the invention.

The invention adopts a mode of two layers of message marks (S, C) to mark the sending period of the message, wherein the S mark represents the preset sending period sent by the node, namely the mark corresponding to the expected period mapping relation, for example, the sending period mapping relation between the node A and the node B is X_A →X_B Wherein X is_A Is a preset transmission period mark, X, sent by the message from the node A_B Is a preset transmission period marker sent by the message from the node B. The C flag represents an actual transmission cycle flag when the message is actually transmitted. Normally, the S flag and the C flag have the same value, and when an abnormal condition such as a delay occurs, a difference may occur between the two.

With a data stream f_A For example, source node A is issuing a bearerData carrying stream f_A When the message(s) is (are) being sent, the message(s) carry a label (X)_A ，X_A ). As shown in FIG. 11, when node A is at T_A When continuously transmitting data stream to node B in time range, node B receives data stream f due to network delay in transmission process_A In the time range of T_A ' time period

Node B is at T_A ' continuously receiving a data stream f in a time frame_A . According to the preset period mapping relation X of the node A and the node B_A →X_B Mapping to obtain X_A Is t_A When, X_B Has a period number of t_B +2, i.e. data stream f_A It is expected that the number should be t in the period_B The reception is completed in the period of + 1. And, in fact, the data stream f_A At t_B The +1 cycle is received and a portion of the message is received at t_B The reception is completed within +2 cycles. I.e. the label received by node B is (X)_A ，X_A ) Of the data stream f_A According to the expected periodic mapping relation X_A →X_B Is divided into two parts, one part is a normally arrived message, namely the message is numbered as t in the period_B The period of +1 and the previous period are received and preset at t_B Message sent in +2 period; the other part of the message is numbered as t in the period_B Receive in +2 period, so it can't be according to preset sending period t_B +2 period transmission, so in period t_B +3 or period t_B After +3, the number of the cycle is t_B And +2, carrying out fault-tolerant forwarding on the received message.

If the t is judged to be the allowable t according to the delay tolerance value in the message and the preset bandwidth of the output interface of the node B_B Messages received in +2 period are at t_B +3 period is forwarded, node B is transmitting data flow f_A When the message is received, the message which arrives normally, namely at t_B +1 message mark in received message is replaced by (X)_B ，X_B ) And at t_B Transmitting in +2 period; will delay the message, i.e. at t_B +2 message tag in received message is replaced by (X)_B ，X_B ') and at t_B Period +3And forwarding is carried out. Corresponding to X_B ＝(t_B + 2) mod (N), and X_B ′＝(t_B +3)mod(N)。

As shown in fig. 11, node C continues to receive data stream f_A In the time range of T_B ’。T_B ' period number t falling at node C_C +4 and t_C +5. Where node C receives the label (X)_B ，X_B ) The corresponding cycle number of the message is t_C +4 and t_C +5, receive flag (X)_B ，X_B ') the corresponding cycle number is t_C +5. The expected periodic mapping relation received by the node C from the corresponding interface of the node B is X_B →X_C Wherein X is_C ＝(t_C + 6) mod (N). That is, according to the mapping relationship, the node C should be at t_C The message is received in the +5 period and is finished at t_C And +6 period for message forwarding. Due to the label (X)_B ，X_B ) Message and label (X) of_B ，X_B ') all at t_C The message reception is finished in the +5 period, so that both the two types of messages can be carried out at t_C And +6 period for normal message forwarding.

I.e. in the data stream f_A Data flow f in the process of being sent from node A to node C via node B_A The delay occurs in the transmission process from the node A to the node B, but after the delay message is subjected to fault-tolerant forwarding, when the delayed message reaches the node C, the delayed message and the normally arrived message can still be forwarded in the same sending period, so that the fault tolerance can be carried out on the time delay in the transmission process of the message, and the end-to-end time delay is ensured not to exceed the normal range through the time delay tolerance value.

Example 3:

as shown in fig. 12, which is a schematic diagram of an architecture of a packet scheduling system according to an embodiment of the present invention, the packet scheduling system according to the embodiment includes an upstream node and a downstream node, where:

when the upstream node sends the message, the message carries a preset sending period and an actual sending period of the message;

when receiving a message, the downstream node judges whether the received message is a delay message according to a preset sending period and an actual sending period of the message; if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message.

In order to implement forwarding scheduling of a packet, the packet scheduling system may be further divided into the following modules according to functions, as shown in fig. 13, specifically including a clock synchronization module, a preprocessing module, and a timing processing module, where:

the clock synchronization module is used for performing clock synchronization or frequency synchronization on each node.

The preprocessing module is used for configuring the network nodes before the message is forwarded and comprises a data stream attribute setting module, a network node setting module and a periodic mapping relation generating module. The data stream attribute setting module is used for setting data stream attributes including a source address, a destination address, a period, a size, a deterministic path, an end-to-end expected delay and the like, and setting a delay tolerance value of a message carrying the data stream. The network node setting module is used for determining the reserved bandwidth of the output interface corresponding to the network node, and establishing a CQF queue, a fault-tolerant receiving queue and a fault-tolerant sending queue at the beginning. The period mapping relation generation module is used for establishing a period mapping table of a connected interface between network nodes through a controller or a self-learning mode.

The timing processing module is used for processing role transformation of a CQF queue, message migration from a fault-tolerant receiving queue to a fault-tolerant sending queue, delay tolerance value processing in a message, message overtime notification of a source node and the like in each period, and comprises a sending processing module and a receiving processing module. The sending processing module is used for scheduling and sending the messages in the CQF queue and the fault-tolerant sending queue according to the reserved flow of the output interface in each period, and the receiving processing module is used for judging the delay delivery of the received messages in each period, putting the delay messages into the fault-tolerant receiving queue and waiting for scheduling.

Example 4:

fig. 14 is a schematic structural diagram of a fault-tolerant processing apparatus for deterministic scheduling of packets according to an embodiment of the present invention. The fault-tolerant processing device for deterministic scheduling of messages of the present embodiment includes one ormore processors 21 and amemory 22. In fig. 14, oneprocessor 21 is taken as an example.

Theprocessor 21 and thememory 22 may be connected by a bus or other means, and fig. 14 illustrates the connection by a bus as an example.

Thememory 22, which is a non-volatile computer-readable storage medium, can be used to store a non-volatile software program and a non-volatile computer-executable program, such as the fault-tolerant processing method for deterministic scheduling of messages inembodiment 1. Theprocessor 21 performs a fault-tolerant processing method of deterministic scheduling of messages by running non-volatile software programs and instructions stored in thememory 22.

Thememory 22 may include high speed random access memory and may also include non-volatile memory, such as at least one magnetic disk storage device, flash memory device, or other non-volatile solid state storage device. In some embodiments, thememory 22 may optionally include memory located remotely from theprocessor 21, and these remote memories may be connected to theprocessor 21 via a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.

The program instructions/modules are stored in thememory 22, and when executed by the one ormore processors 21, perform the fault-tolerant processing method for packet deterministic scheduling in theabove embodiment 1, for example, perform the steps shown in fig. 3 to 5 and fig. 7 to 9 described above.

It should be noted that, for the information interaction, execution process and other contents between the modules and units in the apparatus and system, the specific contents may refer to the description in the embodiment of the method of the present invention because the same concept is used as the embodiment of the processing method of the present invention, and are not described herein again.

Those of ordinary skill in the art will appreciate that all or part of the steps of the various methods of the embodiments may be performed by associated hardware as instructed by a program, which may be stored on a computer-readable storage medium, which may include: a Read Only Memory (ROM), a Random Access Memory (RAM), a magnetic or optical disk, and the like.

The above description is only for the purpose of illustrating the preferred embodiments of the present invention and is not to be construed as limiting the invention, and any modifications, equivalents and improvements made within the spirit and principle of the present invention are intended to be included within the scope of the present invention.

Claims (10)

1. A method for scheduling a packet, comprising:

when a message is sent, carrying a preset sending period and an actual sending period of the message in the message;

when a message is received, judging whether the received message is a delay message or not according to a preset sending period and an actual sending period of the message;

if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message.

2. The method according to claim 1, wherein the determining whether the received packet is a delayed packet according to a preset transmission cycle and an actual transmission cycle of the packet specifically includes:

if the preset sending period of the message is different from the actual sending period, the message is a delay message;

otherwise, obtaining a preset arrival period of the message according to a preset period mapping relation and a preset sending period carried in the message, and judging whether the received message is a delay message or not according to the preset arrival period of the message.

3. The method according to claim 2, wherein the determining whether the received packet is a delayed packet according to the preset arrival period of the packet specifically comprises:

when the actual arrival period of the message is less than or equal to the preset arrival period, the message is not a delay message;

when the actual arrival period of the message is greater than the preset arrival period, judging according to the actual arrival period of a first message of the data stream to which the message belongs, and if the actual arrival period of the first message is greater than the preset arrival period and the difference between the actual arrival period of the first message and the preset arrival period is greater than or equal to a preset difference, judging that the message is not a delay message;

otherwise, the message is a delay message.

4. The method according to claim 1, wherein the fault-tolerant forwarding the packet after the packet reception is finished specifically includes:

if the reserved bandwidth of the corresponding outgoing interface of the node in the first sending period is larger than the total bandwidth of all the messages waiting for normal forwarding, after all the messages waiting for normal forwarding are forwarded, the messages waiting for fault-tolerant forwarding are sequentially forwarded in the first sending period according to the receiving sequence of the messages waiting for fault-tolerant forwarding until the reserved bandwidth of the corresponding outgoing interface is exhausted, or all the messages waiting for fault-tolerant forwarding are forwarded to be finished;

if the message waiting for fault-tolerant forwarding still exists after the first sending period, taking the next sending period of the first sending period as a new first sending period, and carrying out fault-tolerant forwarding on the message waiting for fault-tolerant forwarding in the new first sending period, wherein when carrying out fault-tolerant forwarding for the first time, the first sending period after the message is received is taken as the first sending period.

5. The message scheduling method according to claim 4, wherein the fault-tolerant forwarding is performed on the message after the message reception is finished, further comprising:

and carrying a delay tolerance value in the message, and reducing the delay tolerance value according to the number of cycles delayed in fault-tolerant forwarding every time the message is subjected to fault-tolerant forwarding until the message reaches a destination node or the message is not forwarded until the delay tolerance value carried in the message is less than or equal to a preset minimum value.

6. The packet scheduling method according to claim 5, wherein when the node needs to retransmit the packet, the method further comprises:

and determining a new delay tolerance value according to the delay tolerance value carried in the message sent last time and the overtime period of the message, wherein the new delay tolerance value is carried in the retransmitted message and is used for fault-tolerant forwarding judgment in the subsequent forwarding process.

7. The message scheduling method according to claim 1, wherein the method further comprises:

each forwarding node is provided with a fault-tolerant receiving queue and a fault-tolerant sending queue for realizing scheduling and forwarding of delay messages;

when a delay message is received, the message is added into a fault-tolerant receiving queue, and in the next sending period of the received delay message, the message is moved from the fault-tolerant receiving queue to the fault-tolerant sending queue so as to carry out fault-tolerant forwarding on the message.

8. The message scheduling method according to any of claims 1-7, wherein one or more of a source address, a destination address, a sending period, a size of the data flow and a deterministic path of the message are included in the message.

9. The packet scheduling method according to any of claims 1 to 7, wherein before the packet forwarding, the method further comprises:

configuring clock synchronization of each node required in the message forwarding process; determining basic properties of the data stream; determining the delay tolerance value of each message in the data stream; and calculating a deterministic path of the data flow according to the source address and the destination address of the data flow so as to forward the message carrying the data flow.

10. A message scheduling system comprising an upstream node and a downstream node, wherein:

when the upstream node sends the message, the message carries a preset sending period and an actual sending period of the message;

when receiving a message, the downstream node judges whether the received message is a delay message according to a preset sending period and an actual sending period of the message; if the message is a delay message, after the message is received, carrying out fault-tolerant forwarding on the message.

Images