WO2024061114A1 - 报文调度方法、电子设备和计算机可读存储介质 - Google Patents

报文调度方法、电子设备和计算机可读存储介质 Download PDF

Info

Publication number
WO2024061114A1
WO2024061114A1 PCT/CN2023/119005 CN2023119005W WO2024061114A1 WO 2024061114 A1 WO2024061114 A1 WO 2024061114A1 CN 2023119005 W CN2023119005 W CN 2023119005W WO 2024061114 A1 WO2024061114 A1 WO 2024061114A1
Authority
WO
WIPO (PCT)
Prior art keywords
message
countdown
queue
time
compensation variable
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2023/119005
Other languages
English (en)
French (fr)
Inventor
彭少富
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
ZTE Corp
Original Assignee
ZTE Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by ZTE Corp filed Critical ZTE Corp
Priority to EP23867403.0A priority Critical patent/EP4576726A4/en
Publication of WO2024061114A1 publication Critical patent/WO2024061114A1/zh
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H04L47/564—Attaching a deadline to packets, e.g. earliest due date first
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/28—Flow control; Congestion control in relation to timing considerations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/28—Flow control; Congestion control in relation to timing considerations
    • H04L47/283—Flow control; Congestion control in relation to timing considerations in response to processing delays, e.g. caused by jitter or round trip time [RTT]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H04L47/562—Attaching a time tag to queues
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/6215—Individual queue per QOS, rate or priority
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/625—Queue scheduling characterised by scheduling criteria for service slots or service orders
    • H04L47/6275—Queue scheduling characterised by scheduling criteria for service slots or service orders based on priority

Definitions

  • the present disclosure relates to the field of communications, and in particular to message scheduling methods, electronic devices and computer-readable storage media.
  • QoS Quality of Service
  • deterministic forwarding the minimum delay and maximum delay from the source to the destination, and bounded delay jitter. ;Allowable packet loss rate; upper bound for out-of-order packet delivery.
  • QoS Quality of Service
  • deterministic networks use resource reservation, explicit routing, service protection and other means.
  • current methods often have problems such as complex solutions and out-of-order messages.
  • the present disclosure provides a message scheduling method, including: adding the message to multiple countdown queues according to the allowed queuing delay of the message.
  • the current queuing time range can cover the message.
  • the present disclosure provides an electronic device, including: at least one processor; and a memory having at least one computer program stored thereon, and when the at least one program is executed by the at least one processor, the memory At least one processor implements a method according to the first aspect The message scheduling method described above.
  • the present disclosure provides a computer-readable storage medium storing a computer program.
  • the computer program is executed by a processor, the message scheduling method according to the first aspect is implemented.
  • Figure 1 is a flow chart of a packet scheduling method provided by an embodiment of the present disclosure.
  • FIG. 2 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • FIG. 3 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • Figure 4 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • Figure 5 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • Figure 6 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • Figure 7 is another flowchart of the message scheduling method provided by an embodiment of the present disclosure.
  • Figure 8 is a schematic diagram of a countdown queue of an egress port provided by an embodiment of the present disclosure.
  • Figure 9 is a schematic diagram of the deterministic forwarding timeline based on the local deadline mechanism in the example provided by the embodiment of the present disclosure.
  • Figure 10 is a schematic diagram of the deterministic forwarding timeline based on the local deadline mechanism in the multi-fan-in scenario in the example provided by the embodiment of the present disclosure.
  • FIG. 11 is a schematic diagram of the forwarding timeline of messages with multiple different allowed queuing delays received within a single timing step in an example provided in an embodiment of the present disclosure.
  • FIG. 12 is a schematic diagram of an electronic device provided by an embodiment of the present disclosure.
  • Figure 13 is a schematic diagram of a computer-readable storage medium provided by an embodiment of the present disclosure.
  • the controller pre-calculates the local deadline (Deadline) of each router it experiences for the traffic to be transmitted, which is a system absolute time value, and adds these local deadlines A stack is formed and then carried along with the forwarded data packets.
  • Each router prioritizes the packets according to its own local deadline to achieve deterministic delay requirements.
  • the plan did not discuss the specific implementation of forwarding. Current technology only mentions that the forwarding plane cannot use a first-in-first-out (FIFO, First In First Out) queue to implement this function. However, if the messages in the queue are not sorted according to first-in-first-out, a specific data structure needs to be used.
  • FIFO First In First Out
  • the messages in this data structure will be automatically sorted from nearest to furthest according to the deadline. It is not difficult to create such a data structure in software, but the hardware implementation of the forwarding side is difficult. In addition, this solution needs to carry a local deadline stack in the message, which also increases the complexity of the implementation.
  • a message scheduling scheme based on deadlines is proposed.
  • the basic idea is that only a single deadline needs to be specified for the message to control the message scheduling of all nodes along the path.
  • the single deadline is An offset time, indicating the planned residence time of packets allowed in the node.
  • the accumulated planned dwell time, accumulated actual dwell time, and accumulated dwell time deviation can also be carried in the message.
  • the allowed residence time of packets in the node is dynamically adjusted to obtain lower end-to-end delay jitter. Messages will be selected into queues with corresponding remaining time to live (TTL, Time To Live) based on their allowed residence time.
  • TTL Time To Live
  • multiple messages received at the same time may be queued in different queues due to reasons such as the timing steps of the sending node and the receiving node being out of sync.
  • the order in which messages are received adds messages received later to the queue sent later, which may cause messages to be out of order.
  • This disclosure proposes an idea of scheduling messages based on deadlines, using the queuing time length as the basis for dividing queues.
  • the upper limit coverage range and the lower limit coverage range of the queuing time of different queues are different.
  • the received message is added to the corresponding queue according to the planned dwell time and dwell time deviation carried in the message.
  • Both the upper and lower limits of the queuing time range will count down and gradually decrease as time passes, thereby ensuring that each queue can send according to the length of the queuing time.
  • an embodiment of the present disclosure provides a message scheduling method, as shown in Figure 1, including the following steps S100 and S200.
  • step S100 according to the allowed queuing delay of the message, the message is added to multiple countdown queues whose current queuing time range can cover the allowed queuing delay of the message.
  • step S200 messages are sent in a time sequence determined by queuing time ranges corresponding to multiple countdown queues.
  • a node When a node receives a forwarded message or generates a message to be forwarded, it first obtains the allowed queuing delay of the message, and then selects the corresponding countdown queue to store the message.
  • the current queuing time range of the selected countdown queue must be able to Covers the allowed queuing delay of packets.
  • the countdown queue includes the following features 1) to 4).
  • the authorization time of a countdown queue is the duration during which the queue can send packets when scheduled.
  • the range [CT1, CT2-I] between the first remaining time and the second remaining time in each countdown queue is the queuing time range.
  • CT1 and CT2 will decrease over time at the same time. When CT1 decreases to 0, the scheduling priority of the countdown queue is the highest.
  • the messages stored in the countdown queue are immediately sent to the egress port and can be sent continuously. The time is the authorized time.
  • CT1 will be restored to the preset maximum initial value, and CT2 will be reassigned to (CT1+AT).
  • CT1+AT the priority of the countdown queue is not the highest, and it will continue to enter the next round of CT1 and CT2 as time goes by. Decrement operation. It can be seen from the above description that CT1 is the countdown to the transmission start time, and CT2 is the countdown to the transmission end time.
  • a circular timer can be set on the node to decrement the countdowns of all countdown queues, that is, whenever the timer times out, the values of CT1 and CT2 of all countdown queues will be subtracted by the time interval I of the timer, that is, this timer
  • the time interval I is the decreasing step size of the countdown of the countdown queue.
  • the time interval I of the timer should be precise enough to sense the difference in delay requirements between packets. For example, if the difference in delay requirements between packets is only a few microseconds, the time interval of the timer can be set to 1 microsecond. .
  • the queuing time ranges of the multiple countdown queues are adjacent and do not overlap.
  • the initial first remaining time CT1 values of each countdown queue are staggered, so that at any time, only one countdown queue's first remaining time CT1 decreases to 0.
  • the scheduling priority of the countdown queue is the highest. It will prohibit caching of new messages, and the cached messages in the countdown queue will be sent to the countdown queue immediately. Sent on the egress port, the maximum duration allowed for the countdown queue to send the message is The duration is the preset authorization time AT. In principle, all messages cached in the countdown queue must be sent within this authorized time. If the countdown queue has finished sending all messages and there is still free time during the authorization time, the scheduling engine can continue to schedule other countdown queues with the next highest priority.
  • the authorization time of the countdown queue is divided into N equal parts by the time interval I of the timer, it is equivalent to the countdown queue being physically divided into N equal small panes.
  • the first time interval I will The message in the first small window at the head of the queue is sent, and the message in the Nth small window at the end of the queue is sent within the Nth time interval I. Therefore, the first remaining time CT1 of the countdown queue is actually the sending countdown of the first small pane, while the second remaining time CT2-I is the sending countdown of the Nth small pane, recorded as [CT1,CT2- I].
  • CT2 For the countdown queue whose CT1 has been reduced to 0, after the authorization time AT, CT2 also decreases to 0, and its CT1 will be restored to the preset initial value and also updated to (CT1+AT), allowing caching again. New packets continue to enter the next round of operations in which CT1 and CT2 decrease as time goes by.
  • the allowed queuing delay Q of the message in the node It can be obtained based on the planned residence time of the message in the node, plus the accumulated delay deviation, and then deducting the forwarding delay of the message in the node. For example, if the queuing delay of a packet on the current node is greater than the allowed queuing delay Q, the packet will have a smaller allowed queuing delay on the downstream node. If a packet has a smaller allowed queuing delay on the current node, If the queuing delay is less than the allowed queuing delay Q, then the packet will have a larger allowed queuing delay on the downstream node.
  • a node When a node receives a message, it will determine the allowed queuing delay of the message through a predetermined calculation method based on the planned residence time and accumulated delay deviation carried in the message. The calculated allowable queuing delay will be The message is added to a specific countdown queue that can be covered by the current queuing time range [CT1, CT2-I], thus ensuring that even if multiple messages are received due to a burst, messages in the same countdown queue will be There is a sequence, and even if they are not in the same countdown queue, messages received later will only be added to the queue with a longer countdown, thus avoiding the occurrence of message out-of-order.
  • the node that sends the message and the node that receives the message may be inconsistent in the starting time of each timing step, or the length of the timing step may be inconsistent.
  • the delay deviations carried in the packets are different.
  • the node receiving the message receives it at the same time Among a large number of packets, different allowable queuing delays are calculated based on different delay deviations, and the packets received later may have a smaller allowable queuing delay due to the delay deviation, resulting in Messages are added to the queue with a shorter countdown time, causing messages to appear out of order. Therefore, a variable can be added to compensate for the problem that packets in a burst carry different delay deviations due to special scenarios.
  • the current queuing time range of adding the message to multiple countdown queues can cover the allowed queuing time of the message.
  • the extended countdown queue ie, step S100
  • steps S110 and S120 are examples of steps S110 and S120.
  • step S110 the compensation variable V corresponding to the message is determined.
  • step S120 when the target sum of the message is greater than or equal to the first remaining time of one of the countdown queues and less than the second remaining time of the countdown queue, the message is After joining the countdown queue, the target sum of the message is the sum of the allowed queuing delay of the message and the compensation variable V corresponding to the message.
  • a compensation variable V is added, and the target and (Q+V) values are used to match the current queuing time range [CT1, CT2-I) of each countdown queue. If a countdown queue is matched, the message is added to the countdown queue.
  • the current queuing time range of adding the message to multiple countdown queues can cover the countdown queue of the allowed queuing delay of the message ( That is, step S100) also includes: when the target of the message is the same as the second remaining time of one of the multiple countdown queues, adding the message to the second remaining time and the permission of the message. The countdown queue after the countdown queue with the same queuing delay.
  • the countdown queue is not added, but the second remaining time CT2-I whose countdown duration is longer than the countdown queue is added.
  • the corresponding countdown queue with a longer duration is in the countdown queue after the countdown queue.
  • determining the compensation variable V corresponding to the message includes steps S111 to S114 .
  • step S111 the current compensation variable V corresponding to the message is obtained.
  • step S112 the allowed queuing delay of the message is added to the current compensation variable V corresponding to the message to obtain the current target sum of the message.
  • step S113 when the current target of the message is different from the second remaining time of any one of the multiple countdown queues, the current compensation variable V is determined as the message The corresponding compensation variable V.
  • step S114 when the current target of the message is the same as the second remaining time of one of the multiple countdown queues, the current compensation variable V is incremented and decremented by the step size I, An updated compensation variable V is obtained, and the updated compensation variable V is determined as the compensation variable V corresponding to the message.
  • a large number of messages are sent in a burst. These messages may be sent in different steps in the upstream node, and the delay deviation carried in the messages sent later may The delay deviation carried in the message sent first is smaller than that in the message sent first. Since the step sizes on different nodes are likely to be out of sync, the two messages are received in the same step size at the current node, so The allowed queuing time Q of the packet received later may be smaller than the allowed queuing time Q of the packet received first by a decreasing step size I, and the packet will enter a countdown queue with a shorter countdown time. Therefore, the message scheduling method provided by this disclosure sets a compensation variable V to address similar problems caused by special timing, and uses the target and Q+V to match the coverage of each countdown queue to determine the countdown queues that messages can enter.
  • the following examples illustrate the principle.
  • CT2 CT1 + AT
  • the queuing time range of the previous countdown queue is [CT1, CT2-I]
  • the queuing time range of the adjacent countdown queue is [CT2, (CT2 +AT)-I].
  • the allowed queuing time Q of the former message among the two messages is CT2, and the delay deviation of the latter message is smaller due to the step size of the upstream node.
  • CT2-I will hit the range covered by the previous countdown queue.
  • the adjustment of the target and Q+V is achieved by increasing the compensation variable V.
  • the compensation variable V is triggered to increase and decrease by step I before compensation.
  • the target and Q+V are no longer the second remaining time CT2-I, but CT2, which also enters the next countdown queue, and the two messages before and after The sequence will not change when entering the same countdown queue, thus avoiding packet out-of-order.
  • the compensation variable V On the current node, every time the compensation variable V is incremented, subsequent messages in the same burst will be compensated according to the value of this compensation variable V, and the target and Q+V are used to match the coverage of each countdown queue. to determine the countdown queue that the packet can enter. If sent again If the target sum Q+V is exactly equal to the second remaining time CT2-I of a certain countdown queue, then the compensation variable V will increase and decrease again by the step size I, and subsequent messages will also increase according to the value of the compensation variable V after this increase. value to compensate. And so on, until the burst is sent, the compensation variable V is reset.
  • the countdown information of the above countdown queue can be an explicitly set attribute of the countdown queue, and the attribute is presented to the outside during hardware implementation; however, the countdown information of the above countdown queue can also be passed through other attributes of the countdown queue.
  • Information (such as number, name, etc.) is combined with the necessary number of time ticks (such as the number of timer intervals experienced within a single authorization time) to implicitly derive it, and this attribute does not have to be externally presented during hardware implementation. Regardless of whether the attribute is explicit or implicit, there is no essential difference in the processing based on the attribute described in this disclosure.
  • Figure 8 depicts an example of a countdown queue.
  • Queues queue-1 to queue-7 are countdown queues, and other queues are traditional non-countdown queues.
  • the authorization time AT of each countdown queue is 10 ⁇ s, and all have countdown information, and a timer interval (I) of 1 ⁇ s is used to decrement the countdown value.
  • the preset maximum countdown initial value (MAX_CT) is 60 ⁇ s. At the initial time (T0 time), the countdown values of all countdown queues are staggered from each other.
  • CT1, CT2-I [40,49] ⁇ s
  • the first remaining time CT1 of the countdown queue queue-7 is -1 (or, an implementation can be that when the first remaining time CT1 of the countdown queue becomes 0, the first remaining time CT1 will be used for a period of authorization time thereafter. time CT1 is frozen to 0), it still has the highest scheduling priority.
  • the first remaining time CT1 of countdown queue queue-7 will be restored to the maximum initial countdown value (MAX_CT), which is 60 ⁇ s. It no longer has the highest scheduling priority and will be allowed to receive new messages again.
  • the first remaining time CT1 of countdown queue queue-6 is 0. It has the highest scheduling priority and will no longer receive calls. Receive new messages and immediately send the messages stored in countdown queue queue-6.
  • the node receives a message P1 that needs to be forwarded based on the local deadline mechanism.
  • a separate compensation variable V can be maintained at the granularity of the data flow.
  • the setting of the compensation variable V satisfies the following rules a) and b) to achieve further optimization measures to avoid packet disorder.
  • the initial value of the compensation variable V is 0, and whenever a node receives a new burst of messages for a specific deterministic flow, the compensation variable V corresponding to the deterministic flow is reset to 0.
  • the source end that generates deterministic flows generally sends messages regularly, for example, a burst is generated every time interval of a specific length, and a burst contains some ordered messages.
  • related technologies generally support carrying a message sequence number in a message, this disclosure also assumes that the message contains a burst sequence number, that is, the node can determine whether the message belongs to New burst.
  • the message scheduling method further includes: calculating the allowed queuing delay of the message according to the planned residence time and delay deviation carried in the message.
  • the most basic algorithm is to directly add the planned residence time to the delay deviation, and then subtract the forwarding delay of the message in the node to obtain the allowed queuing time Q.
  • a node receives a message, it adds the message to the corresponding countdown queue, and then sends it out after queuing.
  • the actual queuing time of the message on the node may not be exactly equal to the allowed queuing time. Therefore, there will be a delay deviation when the message is forwarded through each node, and the accumulated delay deviation will be carried to the next node.
  • the planned residence time is 20 ⁇ s, and there is no delay deviation at the first node.
  • the allowed queuing time Q is 20 ⁇ s.
  • the allowed queuing delay is equal to the sum of the planned residence time 20 ⁇ s and the delay deviation (-6) ⁇ s, that is, 14 ⁇ s, and so on.
  • the calculation method can also be determined based on the specific influencing factors to obtain a more accurate allowable queuing delay.
  • the embodiment of the present disclosure sets a compensation variable V.
  • the creation granularity of the compensation variable V includes at least one of the following granularities: taking the data stream as the granularity, creating the compensation variable V for the data stream to which the message belongs, as the value corresponding to the message.
  • the compensation variable V with the ingress port as the granularity, a compensation variable V is created for the ingress port that received the message as the compensation variable V corresponding to the message; with the combination of the inlet port and the data flow as the granularity, for Create a compensation variable V for the data flow to which the message belongs under the ingress port that receives the message, as the compensation variable V corresponding to the message; with the planned residence time as the granularity, for the data flow with the same content as the message
  • the compensation variable V is created for the data flow of the planned dwell time as the compensation variable V corresponding to the message; using the combination of the inlet port, the planned dwell time and the data flow as the granularity, for the data flow that receives the message
  • the creation granularity of the compensation variable V can be based on a single data stream, a node inlet port, the same planned residence time and other factors, or even a combination of several factors, which will not be discussed here. List them one by one.
  • the message scheduling method further includes: when the compensation variable V corresponding to the message does not exist, create the compensation variable V corresponding to the message, and set an initial value for the compensation variable V. value.
  • the compensation variable V of the data stream to which the message belongs is directly used to compensate the allowed queuing delay Q.
  • the initial value of the compensation variable V can be set to 0, or other initial values can be set for the compensation variable V as needed.
  • the packet scheduling method further includes steps S131 and S132.
  • step S131 the difference between the arrival time of the message and the latest updated time of the compensation variable V corresponding to the message is checked.
  • step S132 when the difference exceeds the first threshold, the compensation variable V corresponding to the message is reset to the initial value, and the latest value of the compensation variable V corresponding to the message is The updated time is changed to the current system time.
  • the current system time may be used as the time of the most recent update of the compensation variable V.
  • Each subsequent change may use the system time at the time of the change as the time of the most recent update of the compensation variable V.
  • the compensation variable V also needs to have a recycling mechanism. If the compensation variable V is not recycled, the number of compensation variables V will increase, causing unnecessary burden on the system. It may also cause the compensation variable V to be incremented by I and executed multiple times. The last value is too large and cannot be matched to the countdown queue.
  • the message scheduling method further includes: regularly executing the recovery process of the compensation variable V.
  • the recycling process includes: steps S141 and S142.
  • step S141 the difference between the current system time and the latest updated time of the compensation variable V is checked.
  • step S142 if the difference exceeds the second threshold, the compensation variable V is deleted.
  • the first remaining time in each countdown queue is inversely proportional to the scheduling priority of the countdown queue.
  • Sending messages in time sequence determined by the corresponding queuing time range includes: steps S210 and S220.
  • step S210 the countdown queue with the highest scheduling priority among the plurality of countdown queues is determined based on the first remaining time of each countdown queue.
  • step S220 the message in the countdown queue with the highest scheduling priority is sent.
  • the sending of the message in the countdown queue with the highest scheduling priority includes steps S221 and S222 .
  • step S221 when the first remaining time of the countdown queue decreases to 0, the message in the countdown queue is sent.
  • step S222 if there is no countdown queue with a first remaining time of 0 among the plurality of countdown queues, the message of the countdown queue with the smallest first remaining time and that meets the sending conditions is sent.
  • Each countdown queue in the embodiment of the present disclosure can be reused cyclically after completing the release of messages in the queue.
  • the message scheduling method further includes: when the first remaining time of the countdown queue decrements to 0, after a time slice whose length is the queue authorization time AT, the countdown queue is The first remaining time and the second remaining time are reset, the first remaining time of the countdown queue is reset to the preset initial maximum value, and the second remaining time of the countdown queue is reset to the preset The sum of the initial maximum value and the queue authorization time AT minus the decrement step I.
  • a new countdown queue whose first remaining time is the preset initial maximum value can also be created by deleting the old countdown queue that has completed sending, which is essentially the same as the above embodiment.
  • the message scheduling method proposed in the present invention divides queues according to time ranges, calculates the allowed queuing delay of each message separately, and adds the messages to the queues of the corresponding time ranges, so that adjacent messages of the same flow can be added to the same queue or a later queue even if there is a situation where the allowed queuing delay of a message received later is smaller, and will not enter a queue with an earlier remaining time, thereby avoiding the occurrence of message disorder.
  • a burst sent by the source node (src) contains 10 ordered messages and is forwarded based on the local deadline mechanism.
  • the mechanism causes packets to be out of order.
  • the planned residence time of each message in each node is 20 ⁇ s.
  • other delay types within the node are not considered in this example, that is, the residence time is only determined by the queuing delay. contribute.
  • the implementation method is also similar.
  • the transmission time required for each packet to be sent to the egress port is 1 ⁇ s. This time is related to the bandwidth of the egress port. For packets of the same size, the greater the bandwidth of the egress port, the greater the required The less transmission time.
  • the authorization time of the countdown queue maintained by each node is 10 ⁇ s, and a timer interval of 1 ⁇ s is used to decrement the countdown information of each queue.
  • the compensation variable V is initially 0.
  • node R1 receives the first message P1.
  • the allowed queuing delay of this message is 20 ⁇ s (see the number in brackets, other messages are similar), then the message enters the countdown queue Queue-A.
  • node R1 receives the second message P2.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the third message P3.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the fourth message P4.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the fifth message P5.
  • the allowed queuing delay of this message is 20 ⁇ s, and the message enters the countdown queue Queue-B. This is because the allowed queuing delay of this message is exactly It is equal to CT2-I of countdown queue Queue-A, which is 20, so the compensation variable V increases to 1, and the packet enters the adjacent countdown queue with a larger value of the first remaining time CT1.
  • node R1 receives the seventh message P7.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the eighth message P8.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the ninth message P9.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • node R1 receives the tenth message P10.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • Node R1 will send message P1 at T0+15 ⁇ s.
  • the transmission time of message P1 is 1 ⁇ s
  • the actual residence time of message P1 at node R1 is 16 ⁇ s, which is consistent with the plan.
  • the delay deviation is 4 ⁇ s.
  • Node R1 will send message P2 at T0+16 ⁇ s.
  • the transmission time of message P2 is 1 ⁇ s
  • the actual residence time of message P2 at node R1 is 16 ⁇ s.
  • the delay deviation is 4 ⁇ s.
  • Node R1 will send message P3 at T0+17 ⁇ s.
  • the transmission time of message P3 is 1 ⁇ s
  • the actual residence time of message P3 at node R1 is 16 ⁇ s.
  • the delay deviation is 4 ⁇ s.
  • Node R1 will send message P4 at T0+18 ⁇ s.
  • the transmission time of message P4 is 1 ⁇ s
  • the actual residence time of message P4 at node R1 is 16 ⁇ s.
  • the delay deviation is 4 ⁇ s.
  • Node R1 will send message P5 at T0+25 ⁇ s.
  • the transmission time of message P5 is 1 ⁇ s
  • the actual residence time of message P5 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • Node R1 will send message P6 at T0+26 ⁇ s.
  • the transmission time of message P6 is 1 ⁇ s
  • the actual residence time of message P6 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • Node R1 will send message P7 at T0+27 ⁇ s.
  • the transmission time of message P7 is 1 ⁇ s
  • the actual residence time of message P7 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • Node R1 will send message P8 at T0+28 ⁇ s.
  • the transmission time of message P8 is 1 ⁇ s
  • the actual residence time of message P8 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • Node R1 will send message P9 at T0+29 ⁇ s.
  • the transmission time of message P9 is 1 ⁇ s
  • the actual residence time of message P9 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • Node R1 will send message P10 at T0+30 ⁇ s.
  • the transmission time of message P10 is 1 ⁇ s
  • the actual residence time of message P10 at node R1 is 22 ⁇ s.
  • the delay deviation is -2 ⁇ s.
  • the countdown queue maintained on node R2 has the following countdown information:
  • the compensation variable V is initially 0.
  • node R2 receives the first message P1.
  • node R2 receives the second message P2.
  • node R2 receives the third message P3.
  • node R2 receives the fourth message P4, and the message is allowed to be queued.
  • node R2 receives the fifth message P5.
  • node R2 receives the sixth message P6.
  • node R2 receives the seventh message P7.
  • node R2 receives the eighth message P8.
  • the processing process of further downstream nodes is similar to the above process.
  • a burst of src1 contains 10 ordered packets, which are forwarded based on the local deadline mechanism. However, it is hoped that when forwarding in the network, packets cannot be out of order due to the delay adjustment mechanism of the local deadline. There are the following assumptions a) to e).
  • the planned residence time of each message in each node is 20 ⁇ s.
  • other delay types within the node are not considered in this example, that is, the residence time is only contributed by the queuing delay.
  • the implementation methods are similar.
  • the transmission time required for each packet to be sent to the egress port is 0.01 ⁇ s. This time is related to the bandwidth of the egress port. For packets of the same size, the greater the bandwidth of the egress port, the longer the transmission time required. few.
  • the authorization time of the countdown queue maintained by each node is 10 ⁇ s, and a timer interval of 1 ⁇ s is used to decrement the countdown information of each queue.
  • the network edge node R1 received 10 messages from src1 within 0.1 ⁇ s, these messages were evenly interfered by messages received from other sources, resulting in these 10 messages within the node as one message every 1 ⁇ s.
  • the packet rate reaches the egress port from the ingress port and enters the corresponding countdown queue. Therefore, the key difference between this example and the previous example is that the allowed queuing delays of these packets are different.
  • the compensation variable V is initially 0.
  • node R1 received messages P1 to P10 from src1, but these messages arrived at the egress port every 1 ⁇ s and entered the countdown queue, as follows:
  • the first packet P1 arrives at the egress port.
  • the allowed queuing delay of the packet is 20 ⁇ s (see the number in brackets, and other packets are similar).
  • the second packet P2 arrives at the egress port.
  • the third packet P3 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the fourth packet P4 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the fifth packet P5 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s, and the packet enters the countdown queue Queue-B. This is because the allowed queuing delay of this packet is exactly equal to
  • the sixth packet P6 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the seventh packet P7 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the eighth packet P8 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the ninth packet P9 arrives at the egress port.
  • the allowed queuing delay of this packet is 20 ⁇ s.
  • the tenth message P10 arrives at the egress port.
  • the allowed queuing delay of this message is 20 ⁇ s.
  • Node R1 will send message P1 at T0+15 ⁇ s. Considering that the transmission time of message P1 is only 0.01 ⁇ s, the actual residence time of message P1 at node R1 (compared to the reception time T0 of message P1) is 15 ⁇ s. Compared with the planned dwell time of 20 ⁇ s, the delay deviation of message P1 is 5 ⁇ s.
  • Node R1 will send message P2 at T0+16 ⁇ s.
  • the transmission time of message P2 is only 0.01 ⁇ s
  • the actual residence time of message P2 at node R1 (compare the reception time T0 of message P2. Pay attention to the reception time The actual value is T0+0.01 ⁇ s, but since it is very close to the reception time T0, the approximate value is taken (similar to other messages)) is 16 ⁇ s.
  • the delay deviation of message P2 is 4 ⁇ s.
  • Node R1 will send message P3 at T0+17 ⁇ s.
  • the transmission time of message P3 is only 0.01 ⁇ s
  • the actual residence time of message P3 at node R1 is 17 ⁇ s.
  • the delay deviation of message P3 is 3 ⁇ s.
  • Node R1 will send message P4 at T0+18 ⁇ s.
  • the transmission time of message P4 is only 0.01 ⁇ s
  • the actual residence time of message P4 at node R1 is 18 ⁇ s.
  • the delay deviation of message P4 is 2 ⁇ s.
  • Node R1 will send message P5 at T0+19 ⁇ s. Considering that the transmission time of message P5 is only 0.01 ⁇ s, the actual residence time of message P5 at node R1 (compared to the reception time T0 of message P5) is 19 ⁇ s. Compared with the planned dwell time of 20 ⁇ s, the delay deviation of message P5 is 1 ⁇ s.
  • Node R1 will send message P6 at T0+25 ⁇ s. Considering that the transmission time of message P6 is only 0.01 ⁇ s, the actual residence time of message P6 at node R1 (compared to the reception time T0 of message P6) is 25 ⁇ s. Compared with the planned dwell time of 20 ⁇ s, the delay deviation of message P6 is -5 ⁇ s.
  • Node R1 will send message P7 at T0+26 ⁇ s. Considering that the transmission time of message P7 is only 0.01 ⁇ s, the actual residence time of message P7 at node R1 (compared to the reception time T0 of message P7) is 26 ⁇ s. Compared with the planned dwell time of 20 ⁇ s, the delay deviation of message P7 is -6 ⁇ s.
  • Node R1 will send message P8 at T0+27 ⁇ s.
  • the transmission time of message P8 is only 0.01 ⁇ s
  • the actual residence time of message P8 at node R1 is 27 ⁇ s.
  • the delay deviation of message P8 is -7 ⁇ s.
  • Node R1 will send message P9 at T0+28 ⁇ s.
  • the transmission time of message P9 is only 0.01 ⁇ s
  • the actual residence time of message P9 at node R1 is 28 ⁇ s.
  • the delay deviation of P9 is -8 ⁇ s.
  • Node R1 will send message P10 at T0+29 ⁇ s. Considering that the transmission time of message P10 is only 0.01 ⁇ s, the actual residence time of message P10 at node R1 (compared with the receiving time T0 of message P10) is 29 ⁇ s. Compared with the planned residence time of 20 ⁇ s, the delay deviation of message P10 is -9 ⁇ s.
  • the countdown queue maintained on node R2 has the following countdown information:
  • the compensation variable V is initially 0.
  • node R2 receives the first message P1.
  • node R2 receives the third message P3.
  • node R2 receives the fourth message P4.
  • node R2 receives the fifth message P5.
  • node R2 receives the sixth message P6.
  • node R2 receives the seventh message P7.
  • node R2 receives the eighth message P8.
  • node R2 receives the ninth message P9.
  • the processing process of further downstream nodes is similar to the above process.
  • this example further discusses a scenario where message disorder is likely to occur, that is, the countdown jump time of the countdown queue is not aligned with the allowed queuing delay jump time of the message.
  • Figure 11 describes the countdown jump information of the countdown queue when node R2 receives five messages including messages P1 to P5 and performs the enqueue operation.
  • the countdown information of each countdown queue is as follows:
  • the implementation is as follows:
  • messages P4 and P5 will also enter countdown queue A in sequence.
  • node R2 will still send these messages in order.
  • an embodiment of the present disclosure provides an electronic device, as shown in Figure 12, including: at least one processor 501; and a memory 502 on which at least one computer program is stored.
  • the processor 501 executes, so that at least one processor 501 implements the packet scheduling method described in the first aspect.
  • the electronic device further includes at least one I/O interface 503, connected between the processor 501 and the memory 502, and configured to implement information exchange between the processor 501 and the memory 502.
  • the processor 501 is a device with data processing capabilities, including but not limited to a central processing unit (CPU), etc.;
  • the memory 502 is a device with data storage capabilities, including but not limited to random access memory (RAM, more specifically such as SDRAM, DDR etc.), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory (FLASH);
  • the I/O interface (read-write interface) 503 is connected between the processor 501 and the memory 502, and can realize processing
  • the information exchange between the device 501 and the memory 502 includes but is not limited to a data bus (Bus), etc.
  • processor 501, memory 502, and I/O interface 503 are connected to each other and, in turn, to other components of the computing device via bus 504.
  • embodiments of the present disclosure provide a computer-readable storage medium. As shown in Figure 13, a computer program is stored on the computer-readable storage medium. When the computer program is executed by a processor, the reporting described in the first aspect is implemented. Text scheduling method.
  • the division between functional modules/units mentioned in the above description does not necessarily correspond to the division of physical components; for example, one physical component may have multiple functions, Or a function or step can be performed by several physical components cooperating.
  • Some or all of the physical components may be implemented as software executed by a processor, such as a central processing unit, a digital signal processor, or a microprocessor, or as hardware, or as an integrated circuit, such as an application specific integrated circuit. circuit.
  • a processor such as a central processing unit, a digital signal processor, or a microprocessor
  • Such software may be distributed on computer-readable media, which may include computer storage media (or non-transitory media) and communication media (or transitory media).
  • computer storage media includes volatile and nonvolatile media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. removable, removable and non-removable media.
  • Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, Digital Versatile Disk (DVD) or other optical disk storage, magnetic cassettes, tapes, disk storage or other magnetic storage devices, or may Any other medium used to store the desired information and that can be accessed by a computer.
  • communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism, and may include any information delivery media .

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本公开提供一种报文调度方法、一种电子设备和一种计算机可读存储介质。所述报文调度方法包括：根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中；根据多个所述倒计时队列对应的排队时间范围所确定的时间顺序发送报文；所述倒计时队列的排队时间范围为[CT1,CT2-I]，CT1为所述倒计时队列的第一剩余时间，CT2-I为所述倒计时队列的第二剩余时间，且CT1和CT2满足以下关系：CT2＝CT1+AT，AT为队列授权时间，所述队列授权时间为所述倒计时队列被允许发送报文的持续时长；所述倒计时队列的第一剩余时间与第二剩余时间随着时间的经过而递减，I为递减步长。

Description

报文调度方法、电子设备和计算机可读存储介质
相关申请的交叉引用
本申请要求于2022年9月19日提交的中国专利申请NO.202211136390.6的优先权，该中国专利申请的内容通过引用的方式整体合并于此。
技术领域
本公开涉及通信领域，尤其涉及报文调度方法、电子设备和计算机可读存储介质。
背景技术
在确定性网络的架构中，相关技术将确定性转发的服务质量(QoS，Quality of Service)目标定义为：从源端到目的地的最小时延和最大时延、以及有界的时延抖动；允许的报文丢失率；无序报文传递的上界。为了达到QoS目标，确定性网络采用资源预留、显式路由、业务保护等手段。但是，目前的手段中普遍存在方案复杂、报文乱序等问题。
公开内容
第一方面，本公开提供了一种报文调度方法，包括：根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中；以及根据多个所述倒计时队列对应的排队时间范围所确定的时间顺序发送报文；所述倒计时队列的排队时间范围为[CT1,CT2-I]，CT1为所述倒计时队列的第一剩余时间，CT2-I为所述倒计时队列的第二剩余时间，且CT1和CT2满足以下关系：CT2＝CT1+AT，AT为队列授权时间，所述队列授权时间为所述倒计时队列被允许发送报文的持续时长，所述倒计时队列的第一剩余时间与第二剩余时间随着时间的经过而递减，I为倒计时的递减步长。
第二方面，本公开提供了一种电子设备，包括：至少一个处理器；以及存储器，其上存储有至少一个计算机程序，当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现根据第一方面中所 述的报文调度方法。
第三方面，本公开提供了一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时实现根据第一方面中所述的报文调度方法。
附图说明
图1是本公开实施例提供的报文调度方法的流程图。
图2是本公开实施例提供的报文调度方法的又一流程图。
图3是本公开实施例提供的报文调度方法的又一流程图。
图4是本公开实施例提供的报文调度方法的又一流程图。
图5是本公开实施例提供的报文调度方法的又一流程图。
图6是本公开实施例提供的报文调度方法的又一流程图。
图7是本公开实施例提供的报文调度方法的又一流程图。
图8是本公开实施例提供的出端口的倒计时队列的示意图。
图9是本公开实施例提供的示例中基于本地截止时间机制的确定性转发时间轴示意图。
图10是本公开实施例提供的示例中多扇入场景下的基于本地截止时间机制的确定性转发时间轴示意图。
图11是本公开实施例提供的示例中单个计时步长内收到多个不同允许排队时延的报文的转发时间轴示意图。
图12是本公开实施例提供的一种电子设备的示意图。
图13是本公开实施例提供的一种计算机可读存储介质的示意图。
具体实施方式
应当理解，此处所描述的具体实施例仅仅用以解释本公开，并不用于限定本公开。
在后续的描述中，使用用于表示元件的诸如“模块”、“部件”或“单元”的后缀仅为了有利于本公开的说明，其本身没有特有的意义。因此，“模块”、“部件”或“单元”可以混合地使用。
为了达到QoS目标，在一些相关技术的方案中，控制器预先为待传输的流量计算它所经历的每个路由器的本地截止时间(Deadline)，是一个系统绝对时间值，并将这些本地截止时间形成一个堆栈然后随转发的数据报文携带，每个路由器根据自己的本地截止时间对报文进行优先级调度，以达到确定性的时延要求。但是在该方案中没有展开讨论转发面的具体实 现技术，只是提到转发面不能采用先进先出(FIFO，First In First Out)队列去实现这个功能，然而队列中的报文排序若不按照先进先出，则需要采用一种特定的数据结构以存放具有截止时间的报文，这个数据结构中的报文将按照截止时间从近到远自动排序。对于创建这样的数据结构，软件上实现不难，但转发面的硬件实现却很难。另外，该方案需要在报文中携带本地截止时间堆栈，也增加了实现的复杂度。
在一些相关技术中，提出了一种基于截止时间的报文调度方案，基本思想是只需要为报文指定使用单个截止时间去控制路径沿途所有节点的报文调度，所述的单个截止时间是一个偏移时间，表示允许报文在节点内的计划驻留时间。此外，还可以在报文中携带累计的计划驻留时间、累计的实际驻留时间、累计的驻留时间偏差。根据这些信息去动态地调整报文在节点内的允许驻留时间，以获得较低的端到端时延抖动。报文将根据其允许驻留时间选择进入具有相应剩余生存时间(TTL，Time To Live)的队列中。然而，该方案在某些情况下容易出现报文乱序。例如，在一次突发(burst)中，同一时刻收到的多个报文，由于发送节点与接收节点计时步长不同步等原因，可能排进不同的队列中，却不能保证按照各个报文接收时的先后顺序将后收到的报文加入到后发送的队列中，因此可能导致报文乱序。
本公开提出了一种基于截止时间对报文进行调度的思路，将排队时间长短作为队列的划分依据，不同队列的排队时间的上限覆盖的范围、下限覆盖的范围不同。收到的报文，根据报文中携带的计划驻留时间和驻留时间偏差，加入到相应的队列中。排队时间范围的上限和下限均会随时间的经过而进行倒计时，逐步递减，从而保证各队列能根据排队时间的长短进行发送。
第一方面，本公开实施例提供一种报文调度方法，如图1所示，包括如下步骤S100和S200。
在步骤S100中，根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中。
在步骤S200中，根据多个所述倒计时队列对应的排队时间范围所确定的时间顺序发送报文。
所述倒计时队列的排队时间范围为[CT1,CT2-I]，CT1为所述倒计时队列的第一剩余时间，CT2-I为所述倒计时队列的第二剩余时间，且CT1和CT2满足以下关系：CT2＝CT1+AT，AT为队列授权时间，所述队列授权时间为所述倒计时队列被允许发送报文的持续时长，所述倒计时队列的第一 剩余时间与第二剩余时间随着时间的经过而递减，I为倒计时的递减步长。
节点在收到转发的报文或产生待转发的报文时，首先获取报文的允许排队时延，然后选择相应的倒计时队列存放报文，所选择的倒计时队列的当前的排队时间范围需能涵盖报文的允许排队时延。倒计时队列包括如下特征1)至4)。
1)在网络中的节点内，针对特定出端口维护的多个队列中，新定义一些具有授权时间(AT，Authorization Time)与倒计时(CT，Countdown Time)的队列，将这些基于本地截止时间的队列称为倒计时队列。倒计时队列的授权时间是该队列在得到调度时可一直发送报文的持续时间。
每个倒计时队列的倒计时信息包括两部分：第一倒计时定时器的剩余时间，记为CT1、第二倒计时定时器的剩余时间，记为CT2，且CT1和CT2之间的关系满足CT2＝CT1+AT。每个倒计时队列中在第一剩余时间与第二剩余时间之间的范围[CT1,CT2-I]即排队时间范围。CT1与CT2会同时随着时间推移而递减，当CT1递减到0时，该倒计时队列的调度优先级为最高，在该倒计时队列中存放的报文被立即向出端口上发送，可持续发送的时间为授权时间。之后，CT1将恢复成预设的最大初始值，CT2将重新赋值为(CT1+AT)，此时该倒计时队列的优先级非最高，并继续进入下一轮的CT1与CT2随着时间推移而递减的操作。从上述说明可知，CT1为发送开始时刻的倒计时，CT2为发送关闭时刻的倒计时。
节点上可以设置一个循环定时器对所有倒计时队列的倒计时进行递减操作，即，每当定时器超时，所有倒计时队列的CT1和CT2的值将被减去定时器的时间间隔I，即这个定时器的时间间隔I就是倒计时队列的倒计时的递减步长。时间间隔I可以设定为小于倒计时队列的授权时间AT，且应满足时间间隔I能被授权时间AT整除的条件，即满足AT＝N*I，N是大于1的整数。另外，定时器的时间间隔I应该足够精细，以感知报文间的时延需求差异，比如报文间的时延需求差异仅为几微秒，则定时器的时间间隔可以设置为1微秒。
在一些实施方式中，所述多个倒计时队列的排队时间范围相邻且不重叠。
初始时，所有倒计时队列中，每个倒计时队列初始的第一剩余时间CT1的值相互错开，使得在任何时候只会有一个倒计时队列的第一剩余时间CT1递减到0。
2)当某个倒计时队列的第一剩余时间CT1递减到0时，该倒计时队列的调度优先级为最高，它将禁止缓存新的报文，而该倒计时队列中已缓存的报文被立即向出端口上发送，该倒计时队列发送报文所允许的最长持 续时间为预设的授权时间AT。原则上在此授权时间内需将倒计时队列中缓存的所有报文发送完毕。如果倒计时队列发送所有报文完毕后且授权时间还有空闲，调度引擎可继续调度其它次高优先级的倒计时队列。
进一步地，由于该倒计时队列的授权时间被定时器的时间间隔I分成了N等份，则相当于倒计时队列在物理上被分成了N等份的小窗格，第一份时间间隔I内将发送队首的第1个小窗格内的报文，第N份时间间隔I内将发送处于队尾的第N个小窗格内的报文。因此，倒计时队列的第一剩余时间CT1实际上是第1个小窗格的发送倒计时，而第二剩余时间CT2-I则是第N个小窗格的发送倒计时，记为[CT1,CT2-I]。
3)对于CT1已经减到0的倒计时队列，在经过授权时间AT后，CT2也递减到0，其CT1将恢复成预设的初始值，同时也被更新成(CT1+AT)，重新允许缓存新的报文，继续进入下一轮的CT1和CT2随着时间推移而递减的操作。
4)对于CT1未减到0的倒计时队列，允许缓存报文。节点在收到转发的报文或产生待从特定出端口转发的报文时，首先获取报文的允许排队时延Q，然后选择相应的倒计时队列存放报文，所选择的特定倒计时队列的当前的排队时间范围[CT1,CT2-I]需能涵盖报文的允许排队时延Q，即满足条件：CT1<＝Q<＝CT2-I。
关于如何获取报文在该节点内的允许排队时延Q，可参考现有技术draft-peng-detnet-deadline-based-forwarding-01中的描述，报文在该节点内的允许排队时延Q可以根据报文在该节点内的计划驻留时间，加上累计的时延偏差，再扣减掉报文在节点内的转发时延后得到。比如，如果一个报文在当前节点上的排队时延比允许排队时延Q多，则该报文在下游节点上会有更小的允许排队时延，而如果一个报文在当前节点上的排队时延比允许排队时延Q少，则该报文在下游节点上会有更大的允许排队时延。
节点收到的报文，都会根据报文中携带的计划驻留时间和累积的时延偏差，通过预定的计算方法确定出该报文的允许排队时延，根据计算出的允许排队时延将报文加入当前的排队时间范围[CT1,CT2-I]能涵盖到的特定倒计时队列中，从而保证了即使因一次突发收到多个报文，也会由于处于同一倒计时队列内的报文有先后顺序，并且即使不在同一倒计时队列中，后收到的报文也只会加入倒计时更长的队列中，从而避免了报文乱序的发生。
在一些特殊的突发场景下，例如，发报文的节点和收报文的节点在每个计时步长的起始时刻可能不一致、或计时步长长度不一致，可能会出现发报文时在报文中携带的时延偏差不同。收报文的节点在同一时刻收到 的大量报文中，根据不同的时延偏差算出了不同的允许排队时延，并且后收到的报文还可能因为时延偏差的原因算出更小的允许排队时延，导致后收到的报文加入到倒计时时长更短的队列中，导致报文乱序的出现。因此，可以增加一个变量以补偿因特殊场景下一次突发中的报文携带时延偏差不同的问题。
在一些实施方式中，如图2所示，所述根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中(即步骤S100)包括步骤S110和S120。
在步骤S110中，确定所述报文所对应的补偿变量V。
在步骤S120中，在所述报文的目标和大于或等于多个倒计时队列中的一个倒计时队列的第一剩余时间、且小于该倒计时队列的第二剩余时间的情况下，将所述报文加入该倒计时队列，所述报文的目标和为该报文的允许排队时延与该报文所对应的补偿变量V之和。
在允许排队时延Q的基础上，加入补偿变量V，采用目标和(Q+V)的数值在各个倒计时队列的当前的排队时间范围[CT1,CT2-I)的覆盖范围内进行匹配，在匹配到某个倒计时队列的情况下，将报文加入该倒计时队列。
在一些实施方式中，所述根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中(即步骤S100)还包括：在所述报文的目标和与多个倒计时队列中的一个倒计时队列的第二剩余时间相同的情况下，将该报文加入第二剩余时间与该报文的允许排队时延相同的倒计时队列之后的倒计时队列。
在目标和Q+V的数值与某个倒计时队列的第二剩余时间CT2-I相等的情况下，并不加入该倒计时队列，而是加入倒计时时长比该倒计时队列的第二剩余时间CT2-I所对应的时长更长的倒计时队列中，即该倒计时队列之后的倒计时队列中。
进一步地，如图3所示，所述确定所述报文所对应的补偿变量V(即步骤S110)包括步骤S111至S114。
在步骤S111中，获取所述报文所对应的当前的补偿变量V。
在步骤S112中，将所述报文的允许排队时延与所述报文所对应的当前的补偿变量V相加，得到所述报文当前的目标和。
在步骤S113中，在所述报文的当前的目标和与多个倒计时队列中的任一倒计时队列的第二剩余时间不同的情况下，将所述当前的补偿变量V确定为所述报文所对应的补偿变量V。
在步骤S114中，在所述报文的当前的目标和与多个倒计时队列中的一个倒计时队列的第二剩余时间相同的情况下，将所述当前的补偿变量V自增递减步长I，得到更新后的补偿变量V，将所述更新后的补偿变量V确定为所述报文所对应的补偿变量V。
为了保证突发情况下后收到报文的目标和Q+V不会小于先收到报文的目标和Q+V，可以将补偿变量V设置成递增变化。例如，每当目标和Q+V与某个倒计时队列的第二剩余时间CT2-I相等时，将补偿变量V自增一个倒计时的递减步长I，即V＝V+I，再用目标和Q+V与各个倒计时队列的当前的排队时间范围[CT1,CT2-I)进行匹配，将报文加入到排队时间范围[CT1,CT2-I)能够覆盖的倒计时队列中。
针对前文所述的一些特殊时序场景，例如一个突发中发送了大量报文，在上游节点中这些报文可能分别在不同的步长中发出，后发送的报文中携带的时延偏差可能比先发送的报文中携带的时延偏差更小，而由于不同节点上的步长很可能并不同步，这两个报文在当前节点却是在同一个步长中收到的，于是后收到报文的允许排队时间Q就有可能比先收到报文的允许排队时间Q小一个递减步长I，进入倒计时时长更短的倒计时队列中。因此，本公开提供的报文调度方法针对特殊时序引起的类似问题，设置了补偿变量V，采用目标和Q+V与各个倒计时队列的覆盖范围进行匹配，以确定报文可进入的倒计时队列。下文举例说明其原理。
如前文所述，每个倒计时队列中CT2＝CT1+AT，前一倒计时队列的排队时间范围是[CT1,CT2-I]，那么相邻后一倒计时队列的排队时间范围就是[CT2,(CT2+AT)-I]。最初时不需要进行补偿，可以设置补偿变量V的初始值为0，即Q+V＝Q。假设两报文中前一报文的允许排队时间Q为CT2，后一报文由于上游节点步长的原因，时延偏差更小，算出后一报文的允许排队时间Q为第二剩余时间CT2-I，会命中到前一倒计时队列所覆盖的范围。为了避免出现后一报文进入前一倒计时队列的乱序问题，通过补偿变量V自增来实现对目标和Q+V的调整。当目标和Q+V恰好等于某一倒计时队列的上限，即第二剩余时间CT2-I时，触发补偿变量V自增递减步长I后进行补偿。此时由于补偿变量V自增了递减步长I，目标和Q+V就不再是第二剩余时间CT2-I，而是CT2，也同样进入了后一倒计时队列中，前后两个报文进入同一倒计时队列时前后顺序不会改变，因此避免了报文乱序的出现。
在当前节点上，补偿变量V每次发生自增之后，同一突发中的后续报文均会按照此补偿变量V的值进行补偿，采用目标和Q+V与各个倒计时队列的覆盖范围进行匹配，以确定报文可进入的倒计时队列。如果再次发 生目标和Q+V恰好与某一倒计时队列的第二剩余时间CT2-I相等，则补偿变量V再次自增递减步长I，后续的报文也均按此自增后的补偿变量V的值进行补偿。依此类推，直至这一突发发送完毕，对补偿变量V进行重置。
需要注意的是，具体实现时，上述倒计时队列的倒计时信息可以是倒计时队列的显式设置的属性，并在硬件实现时对外呈现该属性；但上述倒计时队列的倒计时信息也可以通过倒计时队列的其它信息(如编号、名称等)结合必要的时间滴答数(比如在单个授权时间内所经历的定时器时间间隔的个数)去隐含地推导，不一定要在硬件实现时对外呈现该属性。不管是显式的或隐含的属性，对本公开所述的基于该属性的处理而言没有本质差异。
比如，图8中描述了一个倒计时队列示例。队列queue-1至queue-7是倒计时队列，其它队列是传统的非倒计时队列。每个倒计时队列的授权时间AT为10μs，且均有倒计时信息，并采用1μs的定时器时间间隔(I)对倒计时的值进行递减。预设的最大倒计时初始值(MAX_CT)为60μs。初始时刻(T0时刻)，所有倒计时队列的倒计时的值相互错开，比如，倒计时队列queue-1的倒计时信息(即，排队时间范围)为[CT1,CT2-I]＝[60,69]μs，倒计时队列queue-2的倒计时信息为[CT1,CT2-I]＝[50,59]μs，倒计时队列queue-3的倒计时信息为[CT1,CT2-I]＝[40,49]μs，等等。此时仅倒计时队列queue-7的第一剩余时间CT1为0，它具有最高的调度优先级，将不再接收新的报文，并立即发送倒计时队列queue-7中已存储的报文。
而在T0+1μs时刻，倒计时队列queue-1的倒计时信息变为[CT1,CT2-I]＝[59,68]μs，倒计时队列queue-2的倒计时信息变为[CT1,CT2-I]＝[49,58]μs，倒计时队列queue-3的倒计时信息变为[CT1,CT2-I]＝[39,48]μs，等等。此时倒计时队列queue-7的第一剩余时间CT1为-1(或者，一种实现可以是当倒计时队列的第一剩余时间CT1变为0时，在此后的一段授权时间内都将第一剩余时间CT1冻结为0)，它仍然具有最高的调度优先级。
而在T0+10μs时刻，也就是经过授权时间AT后，倒计时队列queue-1的倒计时信息变为[CT1,CT2-I]＝[50,59]μs，倒计时队列queue-2的倒计时信息变为[CT1,CT2-I]＝[40,49]μs，倒计时队列queue-3的倒计时信息变为[CT1,CT2-I]＝[30,39]μs，等等。此时倒计时队列queue-7的第一剩余时间CT1将恢复成最大倒计时初始值(MAX_CT)即60μs，它不再具有最高的调度优先级，将重新允许接收新的报文。此时，倒计时队列queue-6的第一剩余时间CT1为0，它具有最高的调度优先级，将不再接 收新的报文，并立即发送倒计时队列queue-6中已存储的报文。
假设在T0时刻，该节点收到了一个需要基于本地截止时间机制转发的报文P1，该报文的允许排队时延Q为15μs，则该报文将进入倒计时队列queue-6，这是因为根据条件：CT1<＝Q<＝CT2-I，即10<＝15<＝19；类似的，假设在T0时刻，该节点收到了一个需要基于本地截止时间机制转发的报文P2，该报文的允许排队时延Q为49μs，则该报文将进入倒计时队列queue-3，这是因为根据条件：CT1<＝Q<＝CT2-I，即40<＝49<＝49。注意，此示例仅是初步示例本公开的报文入队动作，实际上，如前所述，根据条件“CT1<＝Q<＝CT2-I”将报文插入倒计时队列在某些情况下存在报文乱序问题，进一步的优化措施如下。
在节点上，针对每条确定性流，可以以数据流为粒度维护单独的补偿变量V。补偿变量V的设置满足如下规则a)和b)，以实现避免报文乱序的进一步优化措施。
a)补偿变量V初始值为0，且每当节点在收到特定确定性流的新一次突发的报文时，该确定性流对应的补偿变量V就重新设置为0。
需要说明的是，按照相关技术，在网络中区分不同的确定性流有多种方式，比如在报文头部的相关字段中携带不同的流标识信息。另外，产生确定性流的源端在发送报文时一般是有规律的，比如每隔特定长度的时间间隔产生一次突发，一次突发中包含一些有序的报文。虽然相关技术中一般支持在报文中携带报文序列号，但本公开还假定报文中包含有突发序列号，即，节点可根据报文中的突发序列号来判断报文是否属于新的突发。
b)节点依次处理当前突发中包含的每一个报文并将其插入合适的倒计时队列。具体见如下伪代码：
获取报文的允许排队时延Q与报文对应的当前的补偿变量V；
如果目标和Q+V能被某个倒计时队列X涵盖，即满足：X的CT1<＝Q+V<X的CT2-I，则该报文插入倒计时队列X；
如果目标和Q+V不能被任一倒计时队列X涵盖，则如果目标和Q+V刚好等于某个倒计时队列X的第二剩余时间CT2-I，则先执行V＝V+I得到新的目标和Q+V，再根据新的目标和Q+V将该报文插入合适的其它倒计时队列Y(该倒计时队列Y是与倒计时队列X相邻且具有更大第一剩余时间CT1的值的倒计时队列)，即满足：倒计时队列Y的第一剩余时间CT1<＝Q+V<倒计时队列Y的第二剩余时间CT2-I；
一次突发中可能有多个报文都会导致执行V＝V+I，但补偿变量V并不会无限制的累计，因为在面对下一次突发的报文时，补偿变量V会先清零，然后再次执行上述报文入队操作。
在一些实施方式中，所述报文调度方法还包括：根据所述报文中携带的计划驻留时间和时延偏差计算该报文的允许排队时延。
最基本的一种算法是直接将计划驻留时间与时延偏差直接相加，然后减去报文在节点内的转发时延，得到允许排队时间Q。节点接收到报文，将报文加入到对应的倒计时队列中，再经过排队后发送出去，报文在节点上的实际排队时间可能并不是正好等于允许排队时间，因此报文经过每一节点进行转发时都会有时延偏差，并且会把累积的时延偏差携带到下一节点。例如，计划驻留时间是20μs，第一个节点还不存在时延偏差，在不考虑报文在节点内的转发时延的情况下，允许排队时间Q就是20μs，假设实际排队时间是16μs，小于允许排队时间，则会在报文中携带时延偏差20-16＝4(μs)发送到下一节点，可以理解为在此节点上节省了4μs，那么到下一节点时，允许排队时间Q就等于计划驻留时间20μs与时延偏差4μs的和，即24μs；假设在此节点上的实际排队时间长达30μs，大于允许排队时间24μs，则会在报文中携带时延偏差24-30＝-6(μs)发送到再下一节点，可以理解为在此节点上多花了6μs，那么到再下一节点时允许排队时延则等于计划驻留时间20μs与时延偏差(-6)μs的和，即14μs，依此类推。
当然，网络中影响时延的有多种因素，此处只是举出一个最基本的算法，还可以根据具体的影响因素确定计算方法，以得到更精确的允许排队时延。
如前文所述，为避免在的一些特殊时序中可能存在的报文乱序问题，本公开实施例设置了一个补偿变量V。
在一些实施方式中，所述补偿变量V的创建粒度包括以下粒度中的至少一种：以数据流为粒度，针对所述报文所属的数据流创建补偿变量V，作为所述报文所对应的补偿变量V；以入端口为粒度，针对接收到所述报文的入端口创建补偿变量V，作为所述报文所对应的补偿变量V；以入端口和数据流的组合为粒度，针对接收到所述报文的入端口下所述报文所属数据流创建补偿变量V，作为所述报文所对应的补偿变量V；以计划驻留时间为粒度，针对与所述报文具有相同计划驻留时间的数据流创建所述补偿变量V，作为所述报文所对应的补偿变量V；以入端口、计划驻留时间和数据流的组合为粒度，针对接收到所述报文的入端口下与所述报文具有相同计划驻留时间的数据流创建所述补偿变量V，作为所述报文所对应的补偿变量V。需要说明的是，补偿变量V的创建粒度，可以基于单个数据流，也可以基于节点入端口，还可以基于相同计划驻留时间等因素，甚至还可以是基于几种因素的组合，在此不一一列举。
在一些实施方式中，所述报文调度方法还包括：当所述报文所对应的补偿变量V不存在时，创建所述报文所对应的补偿变量V，为所述补偿变量V设置初始值。
例如，在以数据流为粒度的情况下，针对节点收到的各个数据流分别创建对应的补偿变量V。收到报文时，就直接使用报文所属数据流的补偿变量V对允许排队时延Q进行补偿。一般可以将补偿变量V的初始值设置为0，也可以根据需要，对补偿变量V设置其他初始值。以其他因素作为补偿变量V的创建粒度时，与上述操作类似。
在一些实施方式中，如图4所示，所述报文调度方法还包括步骤S131和S132。
在步骤S131中，检查所述报文的到达时刻与所述报文所对应的补偿变量V的最近一次更新的时刻的差值。
在步骤S132中，在所述差值超过第一阈值的情况下，将所述报文所对应的补偿变量V重置为初始值，且将所述报文所对应的补偿变量V的最近一次更新的时刻修改为当前系统时间。
在补偿变量初始创建时，可以将当前系统时间作为所述补偿变量V的最近一次更新的时刻，之后每次变化时，将变化当时的系统时间作为所述补偿变量V的最近一次更新的时刻。
补偿变量V还需要有一个回收机制，若不对补偿变量V进行回收，会导致补偿变量V的数量越来越多，对系统造成不必要的负担，还可能导致补偿变量V自增I执行多次后数值过大，无法匹配到倒计时队列。
在一些实施方式中，如图5所示，所述报文调度方法还包括：定时执行所述补偿变量V的回收流程。
所述回收流程包括：步骤S141和S142。
在步骤S141中，检查当前系统时间与所述补偿变量V的最近一次更新的时刻的差值。
在步骤S142中，在所述差值超过第二阈值的情况下，删除所述补偿变量V。
需要说明的是，此处只是给出了本公开实施例提供的一种回收流程示例，也可以有其他的回收方式，例如通过定时器对补偿变量V设定回收周期、或者为收到的报文设定一个数量区间、或者为补偿变量V的数值设定一个数量区间，等等，在此不一一列举。凡是定时执行补偿变量V的回收流程的均在本申请保护范围之内。
在一些实施方式中，如图6所示，各个倒计时队列中的第一剩余时间与所述倒计时队列的调度优先级成反比，所述根据多个所述倒计时队列 对应的排队时间范围所确定的时间顺序发送报文(即步骤S200)包括：步骤S210和S220。
在步骤S210中，根据各个倒计时队列的第一剩余时间确定多个所述倒计时队列中调度优先级最高的倒计时队列。
在步骤S220中，发送调度优先级最高的所述倒计时队列中的报文。
进一步地，如图7所示，所述发送调度优先级最高的所述倒计时队列中的报文(即步骤S220)包括步骤S221和S222。
在步骤S221中，在所述倒计时队列的第一剩余时间递减为0的情况下，发送所述倒计时队列中的报文。
在步骤S222中，在多个倒计时队列中不存在第一剩余时间为0的倒计时队列的情况下，发送第一剩余时间最小的且已具备发送条件的倒计时队列的报文。
本公开实施例中的每个倒计时队列在完成队列内报文的发布后，可以循环复用。
在一些实施方式中，所述报文调度方法还包括：在所述倒计时队列的第一剩余时间递减为0的情况下，再经过长度为队列授权时间AT的时间片之后，将所述倒计时队列的第一剩余时间和第二剩余时间进行重置，所述倒计时队列的第一剩余时间被重置为预设的初始最大值，所述倒计时队列的第二剩余时间被重置为预设的初始最大值与队列授权时间AT之和减去递减步长I。
类似地，也可以通过删除已完成发送的旧倒计时队列，创建第一剩余时间为预设的初始最大值的新倒计时队列，其实质与上述实施方式相同。
本公开提出的报文调度方法，根据时间范围划分队列，单独计算每个报文的允许排队时延，将报文加入到对应时间范围的队列中，使同一个流的相邻报文，即使存在后收到的报文的允许排队时延更小的情况，也能加入同一队列或之后的队列，而不会进入剩余时间更早的队列中，避免了报文乱序的发生。
下面结合3个示例对本公开第一个方面所述的报文调度方法在实际业务转发过程中的具体应用进行介绍。
示例1
如图9所示，源节点(src)发送的一次突发中包含有序的10个报文，基于本地截止时间机制转发，但希望在网络中转发时，不能因为本地截止时间的时延调整机制而导致报文乱序。有如下假设a)至d)。
a)每个报文在每个节点内的计划驻留时间为20μs，为便于说明本示例，本示例中不考虑节点内的其它时延类型，即驻留时间仅由排队时延 贡献。实际上，在考虑其它时延类型后应用场景中，实施方式也是类似的。
b)每个报文向出端口发送时所需的传输时间(transmission time)为1μs，该时间与出端口的带宽有关，对于同样大小的报文，出端口的带宽越大，则所需的传输时间越少。
c)不考虑报文在链路上的传播时延(propagation delay)。实际上，考虑该时延的应用场景中，实施方式也是类似的。
d)每个节点维护的倒计时队列的授权时间为10μs，并采用1μs的定时器时间间隔对各队列的倒计时信息进行递减。
接下来以一个具体的示例来说明报文在各节点上的入队操作，并说明本公开的报文调度方法是如何避免报文乱序的。
节点R1：
假设在T0时刻，节点R1上维护的倒计时队列具有如下的倒计时信息：
Queue-A：[CT1,CT2-I]＝[15,24]
Queue-B：[CT1,CT2-I]＝[25,34]
Queue-C：[CT1,CT2-I]＝[35,44]
随着时间的流逝，上述倒计时将逐步递减。
补偿变量V初始为0。
在T0时刻，节点R1收到第一个报文P1，该报文的允许排队时延为20μs(见括号中的数字，其它报文也类似)，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[15,24]能涵盖20μs，即满足15<＝20<24。
在T0+1μs时刻，节点R1收到第二个报文P2，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[14,23]能涵盖20μs，即满足14<＝20<23。
在T0+2μs时刻，节点R1收到第三个报文P3，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[13,22]能涵盖20μs，即满足13<＝20<22。
在T0+3μs时刻，节点R1收到第四个报文P4，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[12,21]能涵盖20μs，即满足12<＝20<21。
在T0+4μs时刻，节点R1收到第五个报文P5，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，这是因为该报文的允许排队时延恰好等于倒计时队列Queue-A的CT2-I，即20，所以补偿变量V自增为1，报文进入相邻的具有更大第一剩余时间CT1的值的倒计时队列 Queue-B(此时倒计时队列Queue-B的倒计时[CT1,CT2-I]为[21,30])，即满足21<＝20+1<30。
在T0+5μs时刻，节点R1收到第六个报文P6，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[20,29]能涵盖20μs，即满足20<＝20+1<29。
在T0+6μs时刻，节点R1收到第七个报文P7，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[19,28]能涵盖20μs，即满足19<＝20+1<28。
在T0+7μs时刻，节点R1收到第八个报文P8，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[18,27]能涵盖20μs，即满足18<＝20+1<27。
在T0+8μs时刻，节点R1收到第九个报文P9，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[17,26]能涵盖20μs，即满足17<＝20+1<26。
在T0+9μs时刻，节点R1收到第十个报文P10，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[16,25]能涵盖20μs，即满足16<＝20+1<25。
则：
节点R1将在T0+15μs时发送报文P1，考虑报文P1的传输时间为1μs，则报文P1在节点R1的实际驻留时间(对比报文P1的接收时刻T0)为16μs，与计划的驻留时间20μs相比，其时延偏差为4μs。
节点R1将在T0+16μs时发送报文P2，考虑报文P2的传输时间为1μs，则报文P2在节点R1的实际驻留时间(对比报文P2的接收时刻T0+1μs)为16μs，与计划的驻留时间20μs相比，其时延偏差为4μs。
节点R1将在T0+17μs时发送报文P3，考虑报文P3的传输时间为1μs，则报文P3在节点R1的实际驻留时间(对比报文P3的接收时刻T0+2μs)为16μs，与计划的驻留时间20μs相比，其时延偏差为4μs。
节点R1将在T0+18μs时发送报文P4，考虑报文P4的传输时间为1μs，则报文P4在节点R1的实际驻留时间(对比报文P4的接收时刻T0+3μs)为16μs，与计划的驻留时间20μs相比，其时延偏差为4μs。
节点R1将在T0+25μs时发送报文P5，考虑报文P5的传输时间为1μs，则报文P5在节点R1的实际驻留时间(对比报文P5的接收时刻T0+4μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
节点R1将在T0+26μs时发送报文P6，考虑报文P6的传输时间为1μs，则报文P6在节点R1的实际驻留时间(对比报文P6的接收时刻 T0+5μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
节点R1将在T0+27μs时发送报文P7，考虑报文P7的传输时间为1μs，则报文P7在节点R1的实际驻留时间(对比报文P7的接收时刻T0+6μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
节点R1将在T0+28μs时发送报文P8，考虑报文P8的传输时间为1μs，则报文P8在节点R1的实际驻留时间(对比报文P8的接收时刻T0+7μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
节点R1将在T0+29μs时发送报文P9，考虑报文P9的传输时间为1μs，则报文P9在节点R1的实际驻留时间(对比报文P9的接收时刻T0+8μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
节点R1将在T0+30μs时发送报文P10，考虑报文P10的传输时间为1μs，则报文P10在节点R1的实际驻留时间(对比报文P10的接收时刻T0+9μs)为22μs，与计划的驻留时间20μs相比，其时延偏差为-2μs。
从上可见，报文发送的顺序得到了保证。
节点R2：
假设在T0+16μs时刻，节点R2上维护的倒计时队列具有如下的倒计时信息：
Queue-X：[CT1,CT2-I]＝[24,33]
Queue-Y：[CT1,CT2-I]＝[34,43]
Queue-Z：[CT1,CT2-I]＝[44,53]
随着时间的流逝，上述倒计时将逐步递减。
补偿变量V初始为0。
在T0+16μs时刻，节点R2收到第一个报文P1，该报文的允许排队时延为24μs(计划驻留时间+时延偏差＝20+4)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[24,33]能涵盖24μs，即满足24<＝24<33。
在T0+17μs时刻，节点R2收到第二个报文P2，该报文的允许排队时延为24μs(计划驻留时间+时延偏差＝20+4)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[23,32]能涵盖24μs，即满足23<＝24<32。
在T0+18μs时刻，节点R2收到第三个报文P3，该报文的允许排队时延为24μs(计划驻留时间+时延偏差＝20+4)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[22,31]能涵盖24μs，即满足22<＝24<31。
在T0+19μs时刻，节点R2收到第四个报文P4，该报文的允许排队 时延为24μs(计划驻留时间+时延偏差＝20+4)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[21,30]能涵盖24μs，即满足21<＝24<30。
在T0+26μs时刻，节点R2收到第五个报文P5，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[14,23]能涵盖18μs，即满足14<＝18<23。
在T0+27μs时刻，节点R2收到第六个报文P6，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[13,22]能涵盖18μs，即满足13<＝18<22。
在T0+28μs时刻，节点R2收到第七个报文P7，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[12,21]能涵盖18μs，即满足12<＝18<21。
在T0+29μs时刻，节点R2收到第八个报文P8，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[11,20]能涵盖18μs，即满足11<＝18<20。
在T0+30μs时刻，节点R2收到第九个报文P9，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-X，根据倒计时队列的倒计时[10,19]能涵盖18μs，即满足10<＝18<19。
在T0+31μs时刻，节点R2收到第十个报文P10，该报文的允许排队时延为18μs(计划驻留时间+时延偏差＝20-2)，则报文进入倒计时队列Queue-Y，这是因为该报文的允许排队时延恰好等于倒计时队列Queue-X的第二剩余时间CT2-I，即18，所以V自增为1，报文进入相邻的具有更大第一剩余时间CT1的值的倒计时队列Queue-Y(此时倒计时队列Queue-Y的倒计时[CT1,CT2-I]为[19,28])，即满足19<＝18+1<28。
可见，上述报文P1至P9依序进入倒计时队列Queue-X，以及报文P10进入更低优先级的倒计时队列Queue-Y，则节点R2仍将有序地发送这些报文。
更下游的节点的处理过程也是与上述过程类似。
示例2
如图10所示，多个源节点向网络边界节点同时发送相同优先级的流 量，src1的一次突发中包含有序的10个报文，基于本地截止时间机制转发，但希望在网络中转发时，不能因为本地截止时间的时延调整机制而导致报文乱序。有如下假设a)至e)。
a)每个报文在每个节点内的计划驻留时间为20μs，为简单起见，本例中不考虑节点内的其它时延类型，即驻留时间仅由排队时延贡献。实际上，在考虑其它时延类型后的应用场景中，实施方式也是类似的。
b)每个报文向出端口发送时所需的传输时间为0.01μs，该时间与出端口的带宽有关，对于同样大小的报文，出端口的带宽越大，则所需的传输时间越少。
c)不考虑报文在链路上的传播时延。实际上，考虑该时延的应用场景中，实施方式也是类似的。
d)每个节点维护的倒计时队列的授权时间为10μs，并采用1μs的定时器时间间隔对各队列的倒计时信息进行递减。
e)网络边界节点R1虽然在0.1μs内从src1收到了10个报文，但这些报文被从其它源头收到的报文均匀干扰，导致在节点内部这10个报文按照每1μs一个报文的速率从入端口到达出端口，并进入相应的倒计时队列。因此本示例相比上一示例而言，关键差异是这些报文的允许排队时延不同。
接下来对报文在各节点上的入队操作进行说明，并说明本公开的报文调度方法是如何避免报文乱序的。
节点R1：
假设在T0时刻，节点R1上维护的倒计时队列具有如下的倒计时信息：
Queue-A：[CT1,CT2-I]＝[15,24]
Queue-B：[CT1,CT2-I]＝[25,34]
Queue-C：[CT1,CT2-I]＝[35,44]
随着时间的流逝，上述倒计时将逐步递减。
补偿变量V初始为0。
至T0至T+0.1μs的极短时间内，节点R1从src1收到了报文P1至P10，但这些报文却是按照每隔1μs到达出端口并进入倒计时队列，如下：
在T0时刻，第一个报文P1到达出端口，该报文的允许排队时延为20μs(见括号中的数字，其它报文也类似)，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[15,24]能涵盖20μs，即满足15<＝20<24。
在T0+1μs时刻，第二个报文P2到达出端口，该报文的允许排队时 延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[14,23]能涵盖20μs，即满足14<＝20<23。
在T0+2μs时刻，第三个报文P3到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[13,22]能涵盖20μs，即满足13<＝20<22。
在T0+3μs时刻，第四个报文P4到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-A，根据倒计时队列的倒计时[12,21]能涵盖20μs，即满足12<＝20<21。
在T0+4μs时刻，第五个报文P5到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，这是因为该报文的允许排队时延恰好等于倒计时队列Queue-A的第二剩余时间CT2-I，即20μs，所以补偿变量V自增为1，报文进入相邻的具有更大第一剩余时间CT1的值的倒计时队列Queue-B(此时倒计时队列Queue-B的倒计时[CT1,CT2-I]为[21,30])，即满足21<＝(20+1)<30。
在T0+5μs时刻，第六个报文P6到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[20,29]能涵盖20μs，即满足20<＝(20+1)<29。
在T0+6μs时刻，第七个报文P7到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[19,28]能涵盖20μs，即满足19<＝(20+1)<28。
在T0+7μs时刻，第八个报文P8到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[18,27]能涵盖20μs，即满足18<＝(20+1)<27。
在T0+8μs时刻，第九个报文P9到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[17,26]能涵盖20μs，即满足17<＝(20+1)<26。
在T0+9μs时刻，第十个报文P10到达出端口，该报文的允许排队时延为20μs，则报文进入倒计时队列Queue-B，根据倒计时队列的倒计时[16,25]能涵盖20μs，即满足16<＝(20+1)<25。
假设上述相邻两个报文的1μs的空隙内，塞满了从其它源端收到的报文。
则：
节点R1将在T0+15μs时发送报文P1，考虑报文P1的传输时间仅为0.01μs，则报文P1在节点R1的实际驻留时间(对比报文P1的接收时刻T0)为15μs，与计划的驻留时间20μs相比，报文P1的时延偏差为5μs。
节点R1将在T0+16μs时发送报文P2，考虑报文P2的传输时间仅为0.01μs，则报文P2在节点R1的实际驻留时间(对比报文P2的接收时刻T0。注意接收时刻实际值为T0+0.01μs，但由于非常接近接收时刻T0，则取近似值，其它报文也类似)为16μs，与计划的驻留时间20μs相比，报文P2的时延偏差为4μs。
节点R1将在T0+17μs时发送报文P3，考虑报文P3的传输时间仅为0.01μs，则报文P3在节点R1的实际驻留时间(对比报文P3的接收时刻T0)为17μs，与计划的驻留时间20μs相比，报文P3的时延偏差为3μs。
节点R1将在T0+18μs时发送报文P4，考虑报文P4的传输时间仅为0.01μs，则报文P4在节点R1的实际驻留时间(对比报文P4的接收时刻T0)为18μs，与计划的驻留时间20μs相比，报文P4的时延偏差为2μs。
节点R1将在T0+19μs时发送报文P5，考虑报文P5的传输时间仅为0.01μs，则报文P5在节点R1的实际驻留时间(对比报文P5的接收时刻T0)为19μs，与计划的驻留时间20μs相比，报文P5的时延偏差为1μs。
节点R1将在T0+25μs时发送报文P6，考虑报文P6的传输时间仅为0.01μs，则报文P6在节点R1的实际驻留时间(对比报文P6的接收时刻T0)为25μs，与计划的驻留时间20μs相比，报文P6的时延偏差为-5μs。
节点R1将在T0+26μs时发送报文P7，考虑报文P7的传输时间仅为0.01μs，则报文P7在节点R1的实际驻留时间(对比报文P7的接收时刻T0)为26μs，与计划的驻留时间20μs相比，报文P7的时延偏差为-6μs。
节点R1将在T0+27μs时发送报文P8，考虑报文P8的传输时间仅为0.01μs，则报文P8在节点R1的实际驻留时间(对比报文P8的接收时刻T0)为27μs，与计划的驻留时间20μs相比，报文P8的时延偏差为-7μs。
节点R1将在T0+28μs时发送报文P9，考虑报文P9的传输时间仅为0.01μs，则报文P9在节点R1的实际驻留时间(对比报文P9的接收时刻T0)为28μs，与计划的驻留时间20μs相比，P9的时延偏差为-8μs。
节点R1将在T0+29μs时发送报文P10，考虑报文P10的传输时间仅为0.01μs，则报文P10在节点R1的实际驻留时间(对比报文P10的接收时刻T0)为29μs，与计划的驻留时间20μs相比，报文P10的时延偏差为-9μs。
从上可见，报文发送的顺序得到了保证。
节点R2：
假设在T0+15μs时刻，节点R2上维护的倒计时队列具有如下的倒计时信息：
Queue-X：[CT1,CT2-I]＝[15,24]
Queue-Y：[CT1,CT2-I]＝[25,34]
Queue-Z：[CT1,CT2-I]＝[35,44]
随着时间的流逝，上述倒计时将逐步递减。
补偿变量V初始为0。
在T0+15μs时刻，节点R2收到第一个报文P1，该报文的允许排队时延为25μs(计划驻留时间+时延偏差＝20+5)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[25,34]能涵盖25μs，即满足25<＝25<34。
在T0+16μs时刻，节点R2收到第二个报文P2，该报文的允许排队时延为24μs(计划驻留时间+时延偏差＝20+4)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[24,33]能涵盖24μs，即满足24<＝24<33。
在T0+17μs时刻，节点R2收到第三个报文P3，该报文的允许排队时延为23μs(计划驻留时间+时延偏差＝20+3)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[23,32]能涵盖23μs，即满足23<＝23<32。
在T0+18μs时刻，节点R2收到第四个报文P4，该报文的允许排队时延为22μs(计划驻留时间+时延偏差＝20+2)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[22,31]能涵盖22μs，即满足22<＝22<31。
在T0+19μs时刻，节点R2收到第五个报文P5，该报文的允许排队时延为21μs(计划驻留时间+时延偏差＝20+1)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[21,30]能涵盖21μs，即满足21<＝21<30。
在T0+25μs时刻，节点R2收到第六个报文P6，该报文的允许排队时延为15μs(计划驻留时间+时延偏差＝20-5)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[15,24]能涵盖15μs，即满足15<＝15<24。
在T0+26μs时刻，节点R2收到第七个报文P7，该报文的允许排队时延为14μs(计划驻留时间+时延偏差＝20-6)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[14,23]能涵盖14μs，即满足14<＝14<23。
在T0+27μs时刻，节点R2收到第八个报文P8，该报文的允许排队时延为13μs(计划驻留时间+时延偏差＝20-7)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[13,22]能涵盖13μs，即满足 13<＝13<22。
在T0+28μs时刻，节点R2收到第九个报文P9，该报文的允许排队时延为12μs(计划驻留时间+时延偏差＝20-8)，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[12,21]能涵盖12μs，即满足12<＝12<21。
在T0+29μs时刻，节点R2收到第十个报文P10，该报文的允许排队时延为11μs，则报文进入倒计时队列Queue-Y，则报文进入倒计时队列Queue-Y，根据倒计时队列的倒计时[11,20]能涵盖11μs，即满足11<＝11<20。
可见，上述报文P1至P10依序进入倒计时队列Queue-Y，则节点R2仍将有序地发送这些报文。
更下游的节点的处理过程也是与上述过程类似。
示例3
本示例基于示例2，进一步讨论一种易发生报文乱序的场景，即倒计时队列的倒计时跳变时刻与报文的允许排队时延跳变时刻未对齐的情况。
如图11描述了节点R2在收到报文P1至P5等5个报文并执行入队操作时，倒计时队列的倒计时跳变信息。
如图11，在T0至T0+1μs的间隔内，各倒计时队列的倒计时信息如下：
Queue-A：[CT1,CT2-I]＝[25,34]
Queue-B：[CT1,CT2-I]＝[15,24]
Queue-C：[CT1,CT2-I]＝[5,14]
然而，在该时间间隔内，有可能同时收到报文P1和P2，如果简单的按照CT1<＝Q<＝CT2-I将报文插入倒计时队列，则报文P1(其允许排队时延Q等于25)会进入倒计时队列A，而报文P2(其允许排队时延Q等于24)会进入倒计时队列B，则，报文乱序产生，这是因为倒计时队列B比倒计时队列A更紧急，会先发送报文，而报文P2本应是排在报文P1之后的报文。
而根据避免乱序的优化机制实现如下：
报文P1(其允许排队时延Q等于25)会进入倒计时队列A，因为满足25<＝25<＝34；
报文P2(其允许排队时延Q等于24)也会进入倒计时队列A，因为24恰好为倒计时队列B的第二剩余时间CT2-I，则补偿变量V自增为1，再根据目标和Q+V＝25将报文插入倒计时队列A，即满足25<＝25<＝34；
需要说明的是，此种报文乱序场景是由于上下游节点的步长变化不 同引起的，收到的报文P1和P2在上游节点中是在相邻两个步长中发出的，而当前节点在同一步长内收到。因此，上游节点上的报文P1和P2之间最多只会相差一个递减步长I。假如报文P1与P2相差的步长超过递减步长I，说明并不是在上游节点的相邻步长中被发出的，因此在当前节点上收到报文P1与P2也不可能在相同步长中，从而也不会引起上述的报文乱序问题。即使当前节点上算出报文P1的Q＝25、报文P2的Q＝23，也会由于分别在当前节点的不同步长内收到而不会导致上述的报文乱序问题。
类似的，在T0+1μs至T0+2μs的时间间隔内收到的报文P3(其允许排队时延Q等于23)，会根据目标和Q+V＝24将报文插入倒计时队列A(注意此时倒计时队列A的倒计时已跳变)，即满足24<＝24<＝33。
类似的，报文P4，P5也都将依序进入倒计时队列A。
可见，节点R2仍将有序地发送这些报文。
第二方面，本公开实施例提供一种电子设备，如图12所示，包括：至少一个处理器501；以及存储器502，其上存储有至少一个计算机程序，当至少一个计算机程序被至少一个处理器501执行，使得至少一个处理器501实现如上述第一方面所述的报文调度方法。
在一些实施方式中，该电子设备还包括至少一个I/O接口503，连接在处理器501与存储器502之间，配置为实现处理器501与存储器502的信息交互。
处理器501为具有数据处理能力的器件，包括但不限于中央处理器(CPU)等；存储器502为具有数据存储能力的器件，包括但不限于随机存取存储器(RAM，更具体如SDRAM、DDR等)、只读存储器(ROM)、带电可擦可编程只读存储器(EEPROM)、闪存(FLASH)；I/O接口(读写接口)503连接在处理器501与存储器502间，能实现处理器501与存储器502的信息交互，包括但不限于数据总线(Bus)等。
在一些实施方式中，处理器501、存储器502和I/O接口503通过总线504相互连接，进而与计算设备的其它组件连接。
第三方面，本公开实施例提供一种计算机可读存储介质，如图13所示，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现上述第一方面所述的报文调度方法。
本领域普通技术人员可以理解，上文中所公开方法中的全部或某些步骤、系统、设备中的功能模块/单元可以被实施为软件、固件、硬件及其适当的组合。
在硬件实施方式中，在以上描述中提及的功能模块/单元之间的划分不一定对应于物理组件的划分；例如，一个物理组件可以具有多个功能， 或者一个功能或步骤可以由若干物理组件合作执行。某些物理组件或所有物理组件可以被实施为由处理器(如中央处理器、数字信号处理器或微处理器)执行的软件，或者被实施为硬件，或者被实施为集成电路，如专用集成电路。这样的软件可以分布在计算机可读介质上，计算机可读介质可以包括计算机存储介质(或非暂时性介质)和通信介质(或暂时性介质)。如本领域普通技术人员公知的，术语计算机存储介质包括在用于存储信息(诸如计算机可读指令、数据结构、程序模块或其他数据)的任何方法或技术中实施的易失性和非易失性、可移除和不可移除介质。计算机存储介质包括但不限于RAM、ROM、EEPROM、闪存或其他存储器技术、CD-ROM、数字多功能盘(DVD)或其他光盘存储、磁盒、磁带、磁盘存储或其他磁存储装置、或者可以用于存储期望的信息并且可以被计算机访问的任何其他的介质。此外，本领域普通技术人员公知的是，通信介质通常包含计算机可读指令、数据结构、程序模块或者诸如载波或其他传输机制之类的调制数据信号中的其他数据，并且可包括任何信息递送介质。
以上参照附图说明了本公开的示例性实施例，并非因此局限本公开的权利范围。本领域技术人员不脱离本公开的范围和实质内所作的任何修改、等同替换和改进，均应在本公开的权利范围之内。

Claims (15)

  1. 一种报文调度方法，包括：
    根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中；以及
    根据多个所述倒计时队列对应的排队时间范围所确定的时间顺序发送报文；
    其中，所述倒计时队列的排队时间范围为[CT1,CT2-I]，CT1为所述倒计时队列的第一剩余时间，CT2-I为所述倒计时队列的第二剩余时间，且CT1和CT2满足以下关系：
    CT2＝CT1+AT，
    AT为队列授权时间，所述队列授权时间为所述倒计时队列被允许发送报文的持续时长，所述倒计时队列的第一剩余时间与第二剩余时间随着时间的经过而递减，I为倒计时的递减步长。
  2. 根据权利要求1所述的报文调度方法，其中，根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中包括：
    确定所述报文所对应的补偿变量V；以及
    在所述报文的目标和大于或等于多个倒计时队列中的一个倒计时队列的第一剩余时间、且小于该倒计时队列的第二剩余时间的情况下，将所述报文加入该倒计时队列，其中，所述报文的目标和为该报文的允许排队时延与该报文所对应的补偿变量V之和。
  3. 根据权利要求2所述的报文调度方法，其中，所述根据报文的允许排队时延，将所述报文加入多个倒计时队列中的当前的排队时间范围能够覆盖所述报文的允许排队时延的倒计时队列中还包括：
    在所述报文的目标和与多个倒计时队列中的一个倒计时队列的第二剩余时间相同的情况下，将该报文加入第二剩余时间与该报文的允许排队时延相同的倒计时队列之后的倒计时队列。
  4. 根据权利要求3所述的报文调度方法，其中，所述确定所述报文所对应的补偿变量V包括：
    获取所述报文所对应的当前的补偿变量V；
    将所述报文的允许排队时延与所述报文所对应的当前的补偿变量V相加，得到所述报文当前的目标和；
    在所述报文的当前的目标和与多个倒计时队列中的任一倒计时队列的第二剩余时间不同的情况下，将所述当前的补偿变量V确定为所述报文所对应的补偿变量V；以及
    在所述报文的当前的目标和与多个倒计时队列中的一个倒计时队列的第二剩余时间相同的情况下，将所述当前的补偿变量V自增递减步长I，得到更新后的补偿变量V，将所述更新后的补偿变量V确定为所述报文所对应的补偿变量V。
  5. 根据权利要求1所述的报文调度方法，还包括：
    根据所述报文中携带的计划驻留时间和时延偏差计算该报文的允许排队时延。
  6. 根据权利要求2所述的报文调度方法，其中，补偿变量V的创建粒度包括以下粒度中的至少一种：
    以数据流为粒度，针对所述报文所属的数据流创建补偿变量V，作为所述报文所对应的补偿变量V；
    以入端口为粒度，针对接收到所述报文的入端口创建补偿变量V，作为所述报文所对应的补偿变量V；
    以入端口和数据流的组合为粒度，针对接收到所述报文的入端口下所述报文所属数据流创建补偿变量V，作为所述报文所对应的补偿变量V；
    以计划驻留时间为粒度，针对与所述报文具有相同计划驻留时间的数据流创建所述补偿变量V，作为所述报文所对应的补偿变量V；
    以入端口、计划驻留时间和数据流的组合为粒度，针对接收到所述报文的入端口下与所述报文具有相同计划驻留时间的数据流创建所述补偿变量V，作为所述报文所对应的补偿变量V。
  7. 根据权利要求2所述的报文调度方法，还包括：
    当所述报文所对应的补偿变量V不存在时，创建所述报文所对应的补偿变量V，为所述补偿变量V设置初始值。
  8. 根据权利要求7所述的报文调度方法，还包括：
    检查所述报文的到达时刻与所述报文所对应的补偿变量V的最近一次更新的时刻的差值；以及
    在所述差值超过第一阈值的情况下，将所述报文所对应的补偿变量V重置为初始值，且将所述报文所对应的补偿变量V的最近一次更新的时刻修改为当前系统时间。
  9. 根据权利要求7所述的报文调度方法，还包括：定时执行所述补偿变量V的回收流程；
    所述回收流程包括：
    检查当前系统时间与所述补偿变量V的最近一次更新的时刻的差值；
    在所述差值超过第二阈值的情况下，删除所述补偿变量V。
  10. 根据权利要求1所述的报文调度方法，其中，各个倒计时队列中的第一剩余时间与所述倒计时队列的调度优先级成反比，所述根据多个所述倒计时队列对应的排队时间范围所确定的时间顺序发送报文包括：
    根据各个倒计时队列的第一剩余时间确定多个所述倒计时队列中调度优先级最高的倒计时队列；以及
    发送调度优先级最高的所述倒计时队列中的报文。
  11. 根据权利要求10所述的报文调度方法，其中，所述发送调度优先级最高的所述倒计时队列中的报文包括：
    在所述倒计时队列的第一剩余时间递减为0的情况下，发送所述倒计时队列中的报文；以及
    在多个倒计时队列中不存在第一剩余时间为0的倒计时队列的情况下，发送第一剩余时间最小的且已具备发送条件的倒计时队列的报文。
  12. 根据权利要求1至11中任意一项所述的报文调度方法，还包括：
    在所述倒计时队列的第一剩余时间递减为0的情况下，再经过长度为队列授权时间AT的时间片之后，将所述倒计时队列的第一剩余时间和第二剩余时间进行重置，所述倒计时队列的第一剩余时间被重置为预设的初始最大值，所述倒计时队列的第二剩余时间被重置为预设的初始最大值与队列授权时间AT之和减去递减步长I。
  13. 根据权利要求1至11中任意一项所述的报文调度方法，其中，所述多个倒计时队列的排队时间范围相邻且不重叠。
  14. 一种电子设备，包括：
    至少一个处理器；
    存储器，其上存储有至少一个计算机程序，当所述至少一个计算机程序被所述至少一个处理器执行时，使得所述至少一个处理器实现根据权利要求1至13中任意一项所述的报文调度方法。
  15. 一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时实现根据权利要求1至13中任意一项所述的报文调度方法。
PCT/CN2023/119005 2022-09-19 2023-09-15 报文调度方法、电子设备和计算机可读存储介质 Ceased WO2024061114A1 (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
EP23867403.0A EP4576726A4 (en) 2022-09-19 2023-09-15 MESSAGE SCHEDULING METHOD, ELECTRONIC DEVICE, AND COMPUTER-READABLE RECORDING MEDIUM

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202211136390.6A CN117768410A (zh) 2022-09-19 2022-09-19 报文调度方法、电子设备和计算机可读存储介质
CN202211136390.6 2022-09-19

Publications (1)

Publication Number Publication Date
WO2024061114A1 true WO2024061114A1 (zh) 2024-03-28

Family

ID=90322485

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2023/119005 Ceased WO2024061114A1 (zh) 2022-09-19 2023-09-15 报文调度方法、电子设备和计算机可读存储介质

Country Status (3)

Country Link
EP (1) EP4576726A4 (zh)
CN (1) CN117768410A (zh)
WO (1) WO2024061114A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2025227703A1 (zh) * 2024-04-29 2025-11-06 中兴通讯股份有限公司 一种报文处理方法、存储介质及电子装置

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20180115493A1 (en) * 2015-03-23 2018-04-26 Alcatel Lucent Methods, queueing system, network element and network system for queueing and processing of packets
CN108540402A (zh) * 2017-03-02 2018-09-14 华为技术有限公司 一种优化队列时延的方法和设备
CN108628668A (zh) * 2017-03-21 2018-10-09 北京京东尚科信息技术有限公司 一种多倒计时任务调度系统、方法、电子设备和储存介质
US20190044857A1 (en) * 2018-07-27 2019-02-07 Intel Corporation Deadline driven packet prioritization for ip networks
US10277518B1 (en) * 2017-01-16 2019-04-30 Innovium, Inc. Intelligent packet queues with delay-based actions
CN114095453A (zh) * 2020-07-31 2022-02-25 华为技术有限公司 调度数据包的方法和相关装置

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114095454A (zh) * 2020-07-31 2022-02-25 华为技术有限公司 发送数据包的方法及网络设备

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20180115493A1 (en) * 2015-03-23 2018-04-26 Alcatel Lucent Methods, queueing system, network element and network system for queueing and processing of packets
US10277518B1 (en) * 2017-01-16 2019-04-30 Innovium, Inc. Intelligent packet queues with delay-based actions
CN108540402A (zh) * 2017-03-02 2018-09-14 华为技术有限公司 一种优化队列时延的方法和设备
CN108628668A (zh) * 2017-03-21 2018-10-09 北京京东尚科信息技术有限公司 一种多倒计时任务调度系统、方法、电子设备和储存介质
US20190044857A1 (en) * 2018-07-27 2019-02-07 Intel Corporation Deadline driven packet prioritization for ip networks
CN114095453A (zh) * 2020-07-31 2022-02-25 华为技术有限公司 调度数据包的方法和相关装置

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP4576726A4 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2025227703A1 (zh) * 2024-04-29 2025-11-06 中兴通讯股份有限公司 一种报文处理方法、存储介质及电子装置

Also Published As

Publication number Publication date
CN117768410A (zh) 2024-03-26
EP4576726A4 (en) 2025-11-19
EP4576726A1 (en) 2025-06-25

Similar Documents

Publication Publication Date Title
US10812397B2 (en) Method for managing traffic in a network based upon ethernet switches, vehicle, communication interface, and corresponding computer program product
US9882823B2 (en) Systems and methods for blocking transmission of a frame in a network device
KR101977523B1 (ko) 네트워크에 있어서의 데이터 프레임의 트래픽 쉐이핑의 방법 및 그 디바이스 및 컴퓨터 프로그램
EP4020900B1 (en) Methods, systems, and apparatuses for priority-based time partitioning in time-triggered ethernet networks
US7499402B2 (en) Network delay control
US9960872B2 (en) Systems and methods for performing a soft-block of a queue based on a size of a remaining period of a guard band
CN110419204B (zh) 传输通信信号帧的方法、实体和程序
CN112202685A (zh) 报文转发方法、转发设备和网络设备
WO2022199007A1 (zh) 一种时间敏感网络时隙调度方法、终端及存储介质
US11057400B2 (en) Device and method for detecting attack in network
EP4020901B1 (en) Methods, systems, and apparatuses for enhanced parallelism of time-triggered ethernet traffic using interference-cognizant network scheduling
EP4447405A1 (en) Message scheduling method, network device, storage medium, and computer program product
WO2024061114A1 (zh) 报文调度方法、电子设备和计算机可读存储介质
CN108353036A (zh) 用于通信网络的分组处理技术
EP3166255B1 (en) Switching of scheduled frames in an ethernet-based in-vehicle network
CN115865810A (zh) 一种时间敏感网络中信用值流量调度系统及方法
US20240323094A1 (en) Component-based method for worst-case analysis for stream-based scheduling, class-based scheduling and frame preemption in time-sensitive networks
EP3166257A1 (en) Start-up triggering in an ethernet-based in-vehicle network
WO2023109188A1 (zh) 报文调度方法、网络设备及计算机可读存储介质
Ababneh et al. Derivation of three queue nodes discrete-time analytical model based on DRED algorithm
EP4542934A2 (en) A method and apparatus for transmitting a message
WO2024082727A1 (zh) 报文调度方法、网络设备、存储介质及计算机程序产品
EP4576725A1 (en) Message scheduling method, network device, storage medium, and computer program product
CN117240801A (zh) 数据调度处理方法、设备、装置及存储介质
WO2025050611A1 (zh) 报文转发方法、存储介质和电子装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 23867403

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2023867403

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2023867403

Country of ref document: EP

Effective date: 20250320

NENP Non-entry into the national phase

Ref country code: DE

WWP Wipo information: published in national office

Ref document number: 2023867403

Country of ref document: EP