Method, entity and program for transmitting communication signal frames

Abstract

The invention relates to a method implemented by a communicating entity in a packet-switched network, comprising at least one port for transmitting communication signal frames comprising a first type of frames, intended to be transmitted in a plurality of streams for which a traffic shaping is defined, and a second type of frames, for which no traffic shaping is defined, each frame being able to be fragmented so as to transmit a fragment only of a frame of said second type. The communicating entity stores a plurality of first queues of frames of the first type, the first queues being associated respectively to said plurality of streams, and at least one second queue for frames of the second type. The entity further schedules transmissions of first type frames, and between at least two first type frames, transmission of at least a fragment of at least one second type frame.

Claims

1. A method implemented by computer means of a communicating entity in a packet-switched network, said communicating entity comprising at least one port for transmitting communication signal frames, said frames comprising: a first type of frames (SF), intended to be transmitted in a plurality of streams for which a traffic shaping is defined, and a second type of frames (UF), for which no traffic shaping is defined, each frame being able to be fragmented so as to transmit a fragment only of a frame of said second type, wherein the communicating entity: stores: a plurality of first queues of frames of the first type, said first queues (Qi) being associated respectively to said plurality of streams, and at least one second queue (Qu) for frames of the second type, and schedules: transmissions of the first type frames, and between at least two first type frames, transmission of at least a fragment of at least one second type frame, and wherein, for deciding to transmit a fragment only of a second type frame, the communicating entity determines: whether the size of the fragment to be transmitted is greater than a threshold (MinFragSize), and whether the size of a remaining fragment of said second type frame is greater than said threshold, and otherwise prevents from fragment transmission, wherein each of said first and second queues is stored in a first-in-first-out type buffer (BUFF), and wherein a queue to which a first type frame is assigned is determined according to the stream to which said first type frame belongs, depending on features of said first type frame, and wherein a frame belonging to a shaped stream is selected for transmission by comparing scheduled transmission times (TTTi) of frames placed at the head of each first queue, the frame associated to the smallest scheduled transmission time (miniTTTi) being selected as a next candidate for transmission.

2. The method of claim 1, wherein said features of said first type frame include a frame length and a current rate of the stream to which said first type frame belongs, and wherein a time taken for the transmission of each first type frame in its queue is calculated and respective transmission times are scheduled for said first type frames according to said respective times taken for the transmissions of the first type frames.

3. The method of claim 1, wherein the communicating entity performs a time counting for determining a current time (T) and implements transmission of said next candidate if: the scheduled transmission time (TTTk.) associated to said next candidate is smaller or equal to the current time (T), and if no other first type frame is currently being transmitted, and if no second type frame or fragment is currently being transmitted.

4. The method according to claim 1, wherein the communicating entity determines whether a second type frame or frame fragment is being transmitted, and if yes whether said second type frame or frame fragment can be further fragmented for interrupting a transmission of said second type frame or frame fragment, and allowing thereby a transmission of said next candidate.

5. The method of claim 4, wherein the communicating entity implements a fragmentation of said second type frame or frame fragment: if the size of said second type frame or frame fragment which transmission is to be interrupted is greater than said threshold (MinFragSize), and if the size of a frame fragment to remain in said second queue after the interruption is greater than said threshold.

6. A communicating entity, comprising at least one port for transmitting communication signal frames in a packet-switched network, and further comprising a computer circuit for performing the method according to claim 1.

7. A non-transitory computer readable medium having stored there on a program comprising instructions for performing the method as claimed in claim 1, when run by a processor.

8. A method implemented by computer means of a communicating entity in a packet-switched network, said communicating entity comprising at least one port for transmitting communication signal frames, said frames comprising: a first type of frames (SF), intended to be transmitted in a plurality of streams for which a traffic shaping is defined, and a second type of frames (UF), for which no traffic shaping is defined, each frame being able to be fragmented so as to transmit a fragment only of a frame of said second type, wherein the communicating entity: stores: a plurality of first queues of frames of the first type, said first queues (Qi) being associated respectively to said plurality of streams, and at least one second queue (Qu) for frames of the second type, and schedules: transmissions of the first type frames, and between at least two first type frames, transmission of at least a fragment of at least one second type frame, and wherein, for deciding to transmit a fragment only of a second type frame, the communicating entity determines: whether the size of the fragment to be transmitted is greater than a threshold (MinFragSize), and whether the size of a remaining fragment of said second type frame is greater than said threshold, and otherwise prevents from fragment transmission, wherein the communicating entity performs a time counting for determining a current time and implements a second type frame fragmentation in view of fragment transmission: if no first type frame is currently being transmitted, and if no first type frame placed at a first queue head has a scheduled transmission time (TTTi) smaller or equal to the current time (T).

9. The method according to claim 1, wherein said communicating entity inserts a probe frame (PF) at the head of at least one of the first queues comprising said next candidate for transmission, so as to avoid any latency of transmission of said next candidate.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a cyclic organization of a transmission multiplex according to prior art.

(2) FIG. 2 shows unshaped frame fragmentation guarantying shaped frame transmission.

(3) FIG. 3 shows shaped and unshaped queues in a transmission port (or “output port” hereafter) of a communicating entity according to the present invention.

(4) FIG. 4 shows schematically a computer circuit (FPGA, integrated chip, or any other computer circuit) of a communicating entity according to an embodiment of the present invention.

(5) FIG. 5 shows operations performed by an input port and/or any other part of the communicating entity generating frames to be transmitted by the transmission port of the communicating entity.

(6) FIG. 6A shows operations performed by the communicating entity for transmitting a shaped frame from its transmission port.

(7) FIG. 6B shows operations performed by the communicating entity for transmitting a shaped frame from its transmission port.

(8) FIG. 7A shows transmission conditions for a shaped frame, in consistence with the embodiment of FIGS. 6A and 6B, in case of fragment transmission of unshaped frame, the scheduled transmissions time being here from right ([miniTTTi]1) to left ([miniTTTi]2).

(9) FIG. 7B shows transmission conditions for a shaped frame, in consistence with the embodiment of FIGS. 6A and 6B, in case of impossibility to transmit a fragment of unshaped frame, the scheduled transmissions time being here from right ([miniTTTi] 1) to left ([miniTTTi]2).

(10) FIG. 8 shows transmission and fragmentation conditions for an unshaped frame.

(11) FIG. 9 shows operations performed by the communicating entity for transmitting an unshaped frame from its transmission port, in consistency with FIG. 8, in the case where the transmission of an unshaped frame or fragment is already in progress (arrow Y from test S26).

(12) FIG. 10 shows operations performed by the communicating entity for transmitting an unshaped frame from its transmission port, in consistency with FIG. 8, in the case where no transmission of an unshaped frame or fragment is currently in progress (arrow N from test S26 starting FIG. 10).

DESCRIPTION OF EMBODIMENTS

(13) The implementation of the invention makes it possible to limit the latency experienced by the shaped streams in the successive multiplexing stages encountered in the network. For that purpose, it takes advantage of a time-based scheduling mechanism used to dynamically define the transmission opportunities dedicated to the shaped streams in conjunction with pre-emption applied to the unshaped streams. The timing information provided by the time-based scheduling mechanism enables determining the size of frames or fragments candidate for transmission between shaped stream transmission opportunities.

(14) Hereafter, express frames as defined in standard IEEE802.3br are frames belonging to shaped streams.

(15) Normal frames as defined in standard IEEE 802.3br are frames belonging to unshaped streams (that typically support a so-called “Best Effort” transport service).

(16) Normal frames can be segmented in fragments as per the standard IEEE802.3br.

(17) The multiplexing scheme and involved parameters are described below with reference to FIG. 3.

(18) Each shaped stream i is associated with a transmission rate Ri, and a queue Qi in an egress port of each communicating entity of the packet-switched network. In an embodiment, a communicating entity can be a multiplexing node through which the stream passes. In an alternative embodiment, a communicating entity can be a terminal transmitting received frames in a peer-to-peer communication configuration, and/or simply emitting its own frames.

(19) The aforesaid transmission rate Ri is expressed in bit per second. For all shaped streams i, the sum of Ri is less than the total link (or port) transmission rate ρ. Furthermore, a packet to transmit is supposed to be made of octets, each octet corresponding to 8 bits, and this explains the value “8” which appears later in the drawings (for example test S35 of FIG. 10 commented below).

(20) Ri is reserved in the successive nodes traversed by stream i by means of signalling or network administration.

(21) Packets of stream i are stored in memory buffers organized as FIFO (First In First Out), defining an order in queue Qi.

(22) Time is represented by a variable T that is incremented every bit transmission time (at the link rate) and is usually the same for all links and ports of a node.

(23) Each shaped stream i is associated with a stream context SCi that contains the variables required for the shaping mechanism, e.g.:

(24) The status of the associated shaped transmit queue in the output port, Stat(Qi), which can take the values empty (0) or not empty (1);

(25) A Theoretical Transmission Time of the frame stored at the head of the associated shaped transmit queue, noted hereafter TTTi

(26) For the sake of simplification here, all unshaped streams are allocated with a single dedicated queue: the unshaped transmit queue Qu that stores the frames in FIFO order.

(27) A queue context is associated with the unshaped transmit queue, UC, containing three variables:

(28) The status of the unshaped queue, Stat(Qu), which can take the values empty (0) or not empty (1);

(29) The size of the frame or remaining fragment stored at the head of the unshaped queue: sizeofQuHead;

(30) The number of bytes transmitted since the beginning of the current unshaped frame or fragment transmission: sizeofCurrFrag, updated upon the transmission of each byte.

(31) Considering the transmission of frames belonging to unshaped streams, a fragment cannot be shorter than a defined minimum fragment size MinFragSize. Typically, a frame fragment shall include at least: a header, an indication of a position of the fragment (at least first fragment, or intermediate fragment, or last fragment of a frame), a CRC code at the end of the fragment, and hopefully data in between.

(32) In fact, the minimum size MinFragSize cannot be less than a size corresponding to these requirements, but more generally cannot be less than the minimum size of an Ethernet frame (e.g. 64 bytes as previously indicated).

(33) The transmission of a shaped frame is indicated by the ShapedTxBusy flag, set to 1 during the transmission, and reset to 0 otherwise.

(34) The transmission of an unshaped frame or fragment is indicated by the UnshapedTxBusy flag, set to 1 during the transmission, and reset to 0 otherwise. The StopUnshapedTx flag is used to trigger the interruption of the transmission of an unshaped frame when a shaped frame transmission time is due.

(35) These operations can be implemented by a communicating entity 100 (node of a network, or terminal device in a peer-to-peer network, etc.), schematically shown in FIG. 4 and comprising: one or several input ports 10 receiving the frames to process, one or several output ports 14 to transmit the received frames (and/or any other frames to be sent by the communicating entity 100 for its direct needs), one or several buffer memories 13 storing at least queues of frames before their transmission as detailed below, and a computer circuit comprising for example a processor 11 cooperating with a memory 12 storing at least instructions of a computer program for performing the method according to an embodiment of the invention.

(36) FIG. 5 shows an example of operation of the input ports 10 of such a communicating entity 100.

(37) In a first step S0, the stream to which received frames belong is identified in the input port in order to determine whether the received frames are shaped frames or rather unshaped frames (step S1) and further in which transmit queue(s) the received frames have to be forwarded to. This identification uses information contained in the frame header and/or payload to determine:

(38) The destination output port (step S2), and

(39) The destination transmit queue Q within the selected output port (step S3).

(40) The operation in the transmit ports 14 is now disclosed with reference to FIGS. 6A and 6B.

(41) In case of receiving a shaped frame (arrow Y at output of test S4) and upon storing that frame in the shaped transmit queue Qi the following operations are performed: At test S5, if Stat(Qi)=0, then test S6 is performed and if T>TTTi, then TTTi=T at step S7; then TTTi value is injected in a sorting function at step S8 (as explained in details below); then the value Stat(Qi) is set to Stat(Qi)=1 (step S9).

(42) It is added here that regarding the unshaped stream, upon storing a frame in the unshaped transmit queue Qu (arrow N from test S4) Stat(Qu) is set to not empty (=1), in step S10.

(43) Now is disclosed the transmission of a frame belonging to a shaped stream.

(44) The frame belonging to a shaped stream to be transmitted is selected by comparing all TTTi (using thus the aforesaid sorting function). The frame associated to the smallest TTTi value (as determined in step S10) is determined in step S11 as the next candidate for transmission. For this purpose, the sorting function maintains the smallest TTTi, with i such that Stat(Qi)=1 (i.e. for which the queue is not empty). That smallest TTTi being noted hereafter minTTTi.

(45) If Stat(Qi) equals 0 for all streams i (i.e. all the shaped queues are empty, as determined in step S12) then minTTTi takes the null value in step S13.

(46) If an unshaped frame (or fragment) is currently being transmitted as shown in FIG. 7A, it is checked whether it can be (re)fragmented. To that end: the size of the frame (or fragment), which transmission is to be interrupted, must be greater than MinFragSize, and the size of the fragment remaining in the unshaped queue after transmission interruption must be also greater than MinFragSize.

(47) If both these two conditions are not met together, the normal transmission of unshaped frame (or fragment) continues as usual without further fragmentation, as shown in FIG. 7B.

(48) Otherwise, as shown in FIG. 7A, when fragmentation of the unshaped frame is possible, fragments of the unshaped frame can be transmitted between transmissions of shaped frames.

(49) Therefore, a shaped frame is effectively transmitted mainly when:

(50) TTTi is due, i.e. the current time T is greater or equal TTTi,

(51) There is no frame belonging to another shaped stream currently being transmitted,

(52) There is no frame or fragment belonging to an unshaped stream currently being transmitted.

(53) Referring again to FIGS. 6A and 6B, the following operations are performed upon each increment of time variable T by 1 time unit in step S14. The shaped frame to be transmitted (having the lowest TTTi) as determined in step S11, has the index k and thus TTTk=minTTTi. In step S15, the result of the test should be normally TTTk≠null since a frame is received at step S11. Furthermore, if T≥TTTk at step S16, then test S17 is performed so as to determine whether the transmission of an unshaped frame is currently in progress or not. If yes (UnshapedTxBusy=1), then a request for stopping that current transmission is set at step S18 (StopUnshapedTx=1). Otherwise (arrow N from test S17), it is assessed further whether the transmission of a shaped frame is in progress or not in test S19. If not (ShapedTxBusy=0), then in step S20, the shaped frame to transmit is placed at the head of Qk.

(54) Then, updates are performed for the next time T. In step S21, the parameter ShapedTxBusy is updated to “1” for size(frame)*8/ρ. In step S22, the TTTk value is also updated to TTTk=TTTk+size(frame)*8/Rk, as well as Stat(Qk) in step S23. Moreover, at test S24, if Stat(Qk) is not null, than TTTk is injected in the sorting function again at step S25.

(55) For the purpose of transmission and fragmentation of a frame belonging to an unshaped stream, details are now given hereafter while referring to FIG. 9. As a general rules, the transmission of a frame belonging to an unshaped stream starts if the following conditions are met:

(56) No frame belonging to a shaped stream is currently being transmitted,

(57) If no frame stored in one of the shaped queues has a transmission time which is due already (current time T greater or equal to its TTTi).

(58) The theoretical transmission time of the next-to-be-transmitted frame belonging to a shaped stream is therefore used to check if the unshaped frame can be transmitted, or fragmented.

(59) Finally, a first fragment of the unshaped frame is transmitted only if both its length and the length of the fragment remaining in Qu are greater or equal to MinFragSize.

(60) If not, no transmission occurs from the unshaped queue.

(61) Indeed, as seen before, in case where a new shaped frame must be transmitted while an unshaped frame transmission is pending, the transmission of the unshaped frame can be interrupted only if:

(62) the length of the fragment transmitted up to the interruption is greater or equal MinFragSize,

(63) and the length of the fragment to remain in the unshaped queue after the interruption is greater or equal MinFragSize.

(64) If anyone of the above conditions is not met, the transmission of the unshaped frame cannot be interrupted, as shown in FIG. 8.

(65) Referring to FIG. 9, the following operations are performed upon each increment of time variable T by 1 time unit.

(66) If UnshapedTxBusy=1 (test S26), and if StopTxUnshaped=1 (test S27), and if (sizeofQuHead≥MinFragSize and sizeofCurrFrag≥MinFragSize) in test S28, then the current frame transmission is stopped at step S29. Then, updates are performed and UnshapedTxBusy is set to null (step S30) and StopUnshapedTx is set to null (step S31).

(67) Time T is incremented by ‘1’ (step S14) for a next run.

(68) Otherwise, referring now to FIG. 10, if UnshapedTxBusy≠1 (arrow N from test S26), it is processed further to the following tests: if Stat(Qu)≠0 (test S32), and if ShapedTxBusy=0 (test S33), and if min.sub.i TTTi≠null (test S34), if both the following conditions are met:
[(minTTTi−T)≥MinFragSize*8/ρ] and [size(frame)−(minTTTi−T)*ρ/8≥MinFragSize](test S35),

(69) then the current frame or fragment is transmitted at the head of queue Qu in step S36,

(70) and the parameter UnshapedTxBusy is set to 1 at step S37 during the minimum value between: (minTTTi−T) and size(frame)*8/ρ (to that end, a corresponding temporisation can be provided).

(71) However, in test S34 (arrow N), if min.sub.i TTTi=null, then in step S38, it is time to transmit the frame or fragment at the head of Qu and in step S39 to set UnshapedTxBusy to 1 during a time corresponding to size(frame)*8/ρ.

(72) Then, the next run is implemented when time T is incremented in step S14.

(73) It should be noted that residual latency can be eliminated by the provision of a “probe” frame PF inserted in the shaped stream as explained hereafter. Such a probe frame PF can be inserted at the head of each shaped stream queue. In fact, when typically a frame of a shaped stream is transmitted after a period of silence for example, it may happen the case where the transmission of an unfragmentable unshaped frame or fragment cannot be aborted (due to the size of the produced fragments for example), and it cannot be given a way to the immediate transmission of a shaped frame instead, as shown in FIG. 7B. In order to avoid the resulting residual latency, a “probe” frame can be inserted in the shaped stream so that the first shaped frame following this probe does not experience any latency under such circumstances. In an alternative embodiment which is shown in FIG. 3, one probe frame PF only can be inserted at the head of the shaped frames queue Qk (with k=2 in the example of FIG. 3) and the next candidate for transmission in queue Qk will not suffer from any latency.

(74) More generally, the invention is targeted at packet-switched networks capable of forwarding preemption, and can provide low latency data transfer to time-critical applications that are transported on non-cyclic rate-controlled streams. Typically, it can be applied in embedded control networks such as industrial or automotive networks.