[Title of Invention]

METHOD, ENTITY AND PROGRAM FOR TRANSMITTING

COMMUNICATION SIGNAL FRAMES

[Technical Field]

[0001]

The invention relates to packet-switched networks management.

[Background Art]

[0002]

Packet-switched networks are increasingly used for industrial control application thanks to the introduction of Layer-2 features that allow the transport of control data that cannot suffer latency and transfer delay variation.

[0003]

For instance, low-latency sampling data, (closed loop) control and image streaming (e.g. image processing) have very stringent latency requirements. Image streaming and associated processing as a part of a control loop has greater requirements than best effort transport could provide in a converged network. In parallel, best effort stream is not time-critical, but provides a constant source for interference stream.

[0004]

Solutions have been progressively developed, in particular for the adaptation of switched Ethernet to the requirements of industrial field busses: EtherCAT, Ethernet Powerlink, TCnet, PROFINET, etc.

[0005]

All these solutions rely on specific additions to the standard Ethernet protocol that provide support for scheduled streams.

[0006]

The common scheme used by these adaptations is based on an l organization of the transmission multiplex in time windows, each window being reserved for a specific stream. The number and repetition frequencies of the time windows are determined according to the requirements of the applications.

[0007]

Considering that the (industrial control) applications generating scheduled stream have a periodic activity, the transmission multiplex is organized in periodic cycles. Referring to figure 1, each cycle contains a series of time windows STW reserved for scheduled (low-latency) frames SF transmission, the rest of the transmission opportunities being devoted to non scheduled streams. [Summary of Invention]

[Technical Problem]

[0008]

However, some other control applications have less stringent latency or jitter requirements: embedded automotive control networks for example are among these applications. In these environments, the extra network engineering required by the computation of the schedules and the synchronization of traffic sources with the network can be avoided provided the chosen traffic management method guarantees limited jitter, bounded latency and zero-packet- loss to the critical control streams.

[0009]

Traffic shaping according to a predefined data rate reserved throughout the network and negotiated by the source with the network is a technique that is well adapted to achieve these performance goals. It provides means to guaranty transmission delay bounds and fairness between the shaped streams.

[0010]

To further reduce potential sources of latency due to the interference between shaped and non-shaped streams, pre-emption mechanisms can also be introduced. Preemption intervenes at the transition between a non-shaped stream transmission opportunity and a shaped stream transmission opportunity, as shown in figure 2. In particular, upon such a transition, the beginning of a shaped stream transmission opportunity SFTO can overlap the end of the transmission opportunity of an unshaped stream. In such a case, the frame of the shaped stream SF cannot be transmitted until the current transmission of a frame UF of a non-shaped stream ends.

[0011]

As still shown on figure 2, by pre-empting the transmission opportunity of the residual part of the unshaped frame UF, it is possible to avoid additional delay to be suffered by the shaped stream SF. To facilitate the pre-emption operation, frames of the unshaped stream can be therefore fragmented (as shown in the lower part of figure 2, with the transmission of frag#l) causing the transmission of the remaining fragment(s) (frag#2 in the example of figure 2) to be delayed until the transmission opportunities of the shaped streams are complete.

[0012]

So far, in order to provide efficient interworking between scheduled and non-scheduled streams, it has been proposed:

[0013]

A first type of standard as IEEE802.1Qbv, defining a scheduling scheme relying on the reservation of time windows for different types of streams (scheduled and non-scheduled);

[0014]

A second type of standard as IEEE802.3br and IEEE802.1Qbu defining a pre-emption scheme that specifies the fragmentation mechanisms applied to so- called "normal" frames upon the concurrent transmission of so-called "express" frames; typically belonging to scheduled streams.

[0015]

IEEE802.1Qbv is based on a periodic calendar table, of which each entry defines a time window reserved for the transmission of a particular class of stream (e.g. scheduled or non-scheduled).

[0016]

These standards provide then a complete framework for the transport of periodic scheduled streams with minimal latency, a similar service to those provided by the industrial standards cited above.

[0017]

The mechanism specified in IEEE802.3br allows a MAC Client that has an "Express" traffic (here shaped streams) to preempt "Normal" frames' transmission (belonging to unshaped streams), before the transmission opportunities of shaped traffic starts. When a frame belonging to a shaped stream is scheduled for transmission, it can be transmitted immediately.

[0018]

In addition, the IEEE802.3br standard defines a per-hop fragmentation and reassembly scheme of Normal frames that allows stopping the transmission of a Normal frame to give a transmission opportunity to an Express frame. Normal-frame fragments and Express-frames are distinguished by their preamble length and a "Start of Frame Delimiter" field. This allows non-express frames (Normal-frames) not to wait for a too long timeslot before being transmitted. This results in a limited added latency for Normal flows and a better use of the link capacity.

[0019]

It is to be noted that only a single Normal-frame can be fragmented at any time (on the same link or in the same transmit port).

[0020]

The minimum preempted fragment size is 64 bytes. Therefore, a packet with a length less than 128 bytes cannot be preempted, nor fragmented finally (without letting finally a fragment of less than 64 bytes). Moreover, non-final fragments have a length multiple of 8 bytes.

[0021] So far, the addition of residual latency due to interfering frames or fragments belonging to non scheduled stream can be avoided thanks to the availability of the exact times of beginning and end of transmission windows dedicated to normal (non-express) streams. Indeed, knowing when the next express traffic transmission window starts makes it possible to select the normal frame or fragment to be transmitted without any overlap with the express traffic transmission window.

[0022]

However, when critical data transfers are supported by shaped or at least rate-controlled streams (even if such transfers do not require ultra-low latency), no mechanism is defined to guaranty that these streams do not suffer from additional latency due to interfering with non-critical frames or fragments transmission.

[0023]

Using the state-of-the-art solution based on the current fragmentation standard (IEEE 802.3br and 802.1Qbu), multiplexing of shaped and unshaped streams can take benefit of the pre-emption but will still suffer from residual latency due to the transmission of frame fragments belonging to unshaped streams.

[Solution to Problem]

[0024]

The invention aims to improve the situation.

[0025]

To that end, the invention proposes 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, 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.

[0026]

More particularly, the communicating entity stores a plurality of first queues of frames of the first type, said first queues being associated respectively to said plurality of streams, and at least one second queue for frames of the second type. The communicating entity can therefore schedule 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. Moreover, to that end, for deciding to transmit a fragment only of a second type frame, the communicating entity can further determine whether the size of the fragment to be transmitted is greater than a threshold, and also whether the size of a remaining fragment of said second type frame is greater than that threshold. Otherwise, if these two conditions are not met, the communicating entity prevents from fragment transmission.

[0027]

Therefore, thanks to the implementation of the invention, it is possible to organize the transmission of frames belonging to shaped streams (the aforesaid "first type" frames) so that the beginning and end time of transmission opportunities reserved for shaped traffic are dynamically determined along the transmission of the shaped streams and provide the time boundaries for the transmission opportunities of unshaped fragments or frames (the aforesaid "second type" frames).

[0028]

In a possible embodiment, each of said first and second queues is stored in a first-in-first-out type buffer and a queue to which a first type frame is assigned is determined according to the stream to which that first type frame belongs, depending on features of said first type frame. Typically, information given in a header of the frame can be used to determine the type of that frame (belonging to shaped traffic or to unshaped traffic). Furthermore, features of said first type frame can include its length and a current rate of the stream to which said first type frame belongs. Therefore, the time taken for the transmission of each first type frame in its queue can be calculated (classically by dividing the length of frame by the stream rate), and respective transmission times can be scheduled accordingly for the first type frames.

[0029]

Consequently, in this embodiment, the frame belonging to a shaped stream can be selected for transmission by comparing scheduled transmission times (noted TTTi hereafter) of frames placed at the head of each first queue, the frame associated to the smallest scheduled transmission time (noted miniTTTi) being selected as a next candidate for transmission.

[0030]

In an embodiment where the communicating entity can perform a time counting for determining a current time, the communicating entity can therefore implement transmission of said next candidate if:

- the scheduled transmission time associated to said next candidate is smaller or equal to the current time, and if

- no other first type frame is currently being transmitted , and if

- no second type frame or fragment is currently being transmitted.

[0031]

The communicating entity can determine furthermore whether a second type frame or frame fragment is currently being transmitted, and if yes whether that 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 the aforesaid next candidate.

[0032] In this embodiment, the communicating entity can implement a fragmentation of that 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 the aforesaid threshold, and

- if the size of a frame fragment to remain in said second queue after the interruption is greater than that threshold.

[0033]

In an embodiment, for the purpose of the second type frames' transmission, the communicating entity can perform a time counting for determining a current time and implementing 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 smaller or equal to the current time.

[0034]

Moreover, a provision can be made so as to limit latency of the first type frames' transmission and to that end, the communicating entity can insert a probe frame at the head of at least one of the first queues, preferably the one comprising the next candidate for transmission, so as to avoid any latency of transmission of that next candidate.

[0035]

The present invention aims also at 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 as defined above. An example of embodiment of such a communicating entity is shown in figure 4 commented below.

[0036]

The present invention aims also at a computer program product, comprising instructions for performing the method as defined above, when run by a processor. A general algorithm of such a computer program can be illustrated by way of an example by the flowcharts corresponding to figures 5, 6, 9, 10 commented below.

[0037]

More generally, the present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings, in which like reference numerals refer to similar elements.

[Brief Description of the Drawings]

[0038]

[Fig. l]

Figure 1 shows a cyclic organization of a transmission multiplex according to prior art.

[Fig.2]

Figure 2 shows unshaped frame fragmentation guarantying shaped frame transmission.

[Fig.3]

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

[Fig.4]

Figure 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.

[Fig.5]

Figure 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.

[Fig.6A]

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

[Fig.6B]

Figure 6B shows operations performed by the communicating entity for transmitting a shaped frame from its transmission port.

[Fig.7A]

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

[Fig.7B]

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

[Fig.8]

Figure 8 shows transmission and fragmentation conditions for an unshaped frame.

[Fig.9]

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

[Fig.10]

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

[Description of Embodiments]

[0039] 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.

[0040]

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

[0041]

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).

[0042]

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

[0043]

The multiplexing scheme and involved parameters are described below with reference to figure 3.

[0044]

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.

I I [0045]

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 p. 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 figure 10 commented below).

[0046]

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

[0047]

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

[0048]

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.

[0049]

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

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) ;

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

[0050]

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.

[0051]

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

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

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

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

[0052]

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.

[0053]

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).

[0054]

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

[0055]

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.

[0056] 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 figure 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.

[0057]

Figure 5 shows an example of operation of the input ports 10 of such a communicating entity 100.

[0058]

In a first step SO, 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 SI) 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:

The destination output port (step S2), and

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

[0059]

The operation in the transmit ports 14 is now disclosed with reference to figures 6 A and 6B.

[0060]

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).

[0061]

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.

[0062]

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

[0063]

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 Sl l 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.

[0064]

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

[0065]

If an unshaped frame (or fragment) is currently being transmitted as shown in figure 7 A, 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. [0066]

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 figure 7B.

[0067]

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

[0068]

Therefore, a shaped frame is effectively transmitted mainly when:

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

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

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

[0069]

Referring again to figures 6A and 6B, the following operations are performed upon each increment of time variable T by 1 time unit in step SI 4. The shaped frame to be transmitted (having the lowest TTTi) as determined in step SI 1, has the index k and thus TTTk = minTTTi. In step SI 5, the result of the test should be normally TTTk≠ null since a frame is received at step SI 1. Furthermore, if T > TTTk at step SI 6, 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 SI 7), it is assessed further whether the transmission of a shaped frame is in progress or not in test SI 9. If not (ShapedTxBusy= 0), then in step S20, the shaped frame to transmit is placed at the head of Qk.

[0070] Then, updates are performed for the next time T. In step S21, the parameter ShapedTxBusy is updated to "1" for size(frame)*8/ p. 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.

[0071]

For the purpose of transmission and fragmentation of a frame belonging to an unshaped stream, details are now given hereafter while referring to figure 9.

As a general rules, the transmission of a frame belonging to an unshaped stream starts if the following conditions are met:

No frame belonging to a shaped stream is currently being transmitted, 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).

[0072]

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.

[0073]

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.

If not, no transmission occurs from the unshaped queue.

[0074]

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:

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

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

[0075]

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

[0076]

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

[0077]

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).

[0078]

Time T is incremented by Ί ' (step S 14) for a next run.

[0079]

Otherwise, referring now to figure 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 minj TTTi≠ null (test S34),

- if both the following conditions are met :

[(minTTTi -T) > MinFragSize* 8/p] and [size(frame) - (minTTTi -T)*p/8 > MinFragSize] (test S35),

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

and the parameter UnshapedTxBusy is set to 1 at step S37 during the minimum value between :

- (minTTTi-T) and - size(frame)*8/p (to that end, a corresponding temporisation can be provided).

[0080]

However, in test S34 (arrow N), if min^ 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/ p.

[0081]

Then, the next run is implemented when time T is incremented in step

S14.

[0082]

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 figure 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 figure 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 figure 3) and the next candidate for transmission in queue Qk will not suffer from any latency.

[0083]

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