METHOD FOR TRAFFIC SHAPING OF DATA FRAMES IN NETWORK AND DEVICE AND COMPUTER PROGRAM PRODUCT THEREFOR

Abstract

The present invention relates to packet-switched networks, such as Ethernet, and more particularly to a method for traffic shaping of data frames to transmit in such a telecommunication network, the frames to transmit being distinguished between: express frames, needing to be sent within predetermined time windows, and normal frames, intended to be sent at times outside said time windows. More particularly, for a current normal frame, the method comprises the steps of: determining whether said normal frame can be fragmented, and if yes: determining whether a remaining time to a next time window opening is enough to transmit one or several fragments of said normal frame, and if yes: transmitting said one or several fragments.

Claims

1-13. (canceled)

14. A method for traffic shaping of data frames to transmit in a telecommunication network, the frames to transmit being distinguished between: express frames, needing to be sent within predetermined time windows, and normal frames, intended to be sent at times outside said time windows, wherein, for a current normal frame, the method comprises the steps of: determining whether said normal frame can be fragmented, and if yes: determining whether a remaining time to a next time window opening is enough to transmit one or several fragments of said normal frame, and if yes: transmitting said one or several fragments, and wherein: several flows are being processed and each flow comprises successive normal frames and, if any, one or several fragments remaining from a previous normal frame processing, said normal frames and/or fragments of each flow are queued in a memory and are assigned with respective processing instants, a current time is compared with a least processing instant among all the queues of the respective flows so as to implement said steps if the current time is greater than said least processing instant, said processing instants are updated at each scheduled transmission of a frame or a fragment, by the duration of said scheduled transmission estimated on the basis of a transmission flow bitrate, by dividing the length of the frame or fragment of a flow, to transmit, by the current bitrate of that flow.

15. The method according to claim 14, wherein said normal frames and, if any, one or several fragments remaining from a previous normal frame processing, are queued in a memory and are assigned with respective processing instants and wherein a current time is compared with a least processing instant so as to implement said steps if the current time is greater than the least processing instant.

16. The method according to claim 14, wherein, if said current normal frame cannot be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit the whole current normal frame, and: if yes, said whole current normal frame is transmitted, otherwise, a temporization step is applied until a next current time.

17. The method according to claim 15, wherein, if said current normal frame cannot be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit the whole current normal frame, and: if yes, said whole current normal frame is transmitted, otherwise, a temporization step is applied until a next current time.

18. The method according to claim 14, wherein, if said current normal frame can be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit at least one fragment, and: if yes, at least one fragment is transmitted, otherwise, a temporization step is applied until a next current time.

19. The method according to claim 15, wherein, if said current normal frame can be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit at least one fragment, and: if yes, at least one fragment is transmitted, otherwise, a temporization step is applied until a next current time.

20. The method according to claim 16, wherein, if said current normal frame can be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit at least one fragment, and: if yes, at least one fragment is transmitted, otherwise, a temporization step is applied until a next current time.

21. The method according to claim 17, wherein, if said current normal frame can be fragmented, it is determined whether a remaining time to a next time window opening is enough to transmit at least one fragment, and: if yes, at least one fragment is transmitted, otherwise, a temporization step is applied until a next current time.

22. The method according to claim 18, wherein, if the current normal frame can be fragmented, it is determined further whether the remaining time until the next window opening is enough to send a remaining part of a normal complete frame, and: if yes, corresponding fragments of a remaining part of said normal complete frame are transmitted, otherwise, one or several fragments, corresponding to a total duration less than the remaining time until the next window opening, are transmitted.

23. The method according to claim 14, wherein said remaining time until the next window opening is compared to a time taken for transmitting a fragment or a normal frame estimated on the basis of a capacity of a link on which said fragment or frame is transmitted.

24. The method according to claim 14, wherein a normal frame is considered as able to be fragmented if its total length is at least twice as a length of a minimum fragment size.

25. The method according to claim 24, wherein said total length of a normal frame is updated with its remaining fragments which have not been transmitted.

26. The method according to claim 14, wherein said time windows are successively defined in a cyclic timetable.

27. A device, having traffic shaping means for performing the method according to claim 14.

28. A computer program product, comprising instructions for performing the method as claimed in claim 14, when run by a processor.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0053] FIG. 1 shows two examples of an AFDX traffic shaping according to the BAG,

[0054] FIG. 2 shows a TTEthernet flow scheduling,

[0055] FIG. 3 shows the principle of a transmission selection according to IEEE 802.1Qbv,

[0056] FIG. 4 shows Express and Normal traffics data paths,

[0057] FIG. 5 shows non-fragmented Express and Normal Frames, and successive fragments of a Normal Frame (lower part),

[0058] FIG. 6 shows a system comprising elements which can include a device according to the invention,

[0059] FIG. 7 shows an example of a structure of a device according to the invention, and comprising traffic shaping means so as to perform the method according to the invention,

[0060] FIG. 8 shows an example of a cyclic timetable defining the aforesaid time windows,

[0061] FIG. 9 shows steps of a method according to an example of embodiment of the invention.

DESCRIPTION OF EMBODIMENTS

[0062] In the present following specification, “Express traffic” (or “express frame”) denotes low latency, scheduled or TT (“Time-triggered”) traffic (or frame), while “Normal traffic” (or “normal frame”) denotes Rate-constrained (RC) traffic, or Best-effort (BE) traffic, or any other non-Express traffic (or frame).

[0063] The present invention proposes a combined frame scheduling and fragmentation mechanism which makes it possible to guarantee the conditions listed above.

[0064] Referring to FIG. 6, the scheduling function can be located in a device D provided for each output port of a switch SW of a network NET, or also in a device D having a frame transmission function in a terminal station (T1, T2) for transmitting data or voice data from a terminal T1, T2. As shown on FIG. 7, the incoming frames of each flow (F1, . . . , Fi, Fm) which are received through an input interface IN of the device D are stored in FIFO order (“First In First Out”) in an independent queue (Q.sub.i for flow i), in a working memory MEMA. The device D further comprises a processor PROC for performing the method of the invention with synchronization clock data CLK (obtained from the network or from a synchronized internal clock). Furthermore, the device D comprises a memory MEMB (which can be in a same or in a different memory unit from the working memory MEMA) storing the time table TST detailed on FIG. 8 for allocating timeslots to frames or fragments (FR) to be transmitted. Finally, the frames or fragments (referenced FR in FIG. 7) to transmit are received in an output interface OUT of the device in a convenient order, thanks to the implementation of the invention as detailed below with reference to FIG. 9. Of course, the device D can have further a third memory MEMC (in a same or a different memory unit from MEMA and MEMB) for storing computer program code instructions (INST) to be run by the processor PROC so as to implement the method of the invention.

[0065] The device D can be implemented as an autonomous device, such as an independent chip of a terminal T1, T2 or of a switch SW, or alternatively can use hardware resources (such as the processor and/or a memory unit) of such a terminal or switch (or more widely, any element of a network).

[0066] Referring to FIG. 8, the time table TST is used as follows.

[0067] Time is expressed in a unit corresponding to the duration of 1 bit on the transmission link attached to the output port. All nodes in the network are preferably synchronised on the same clock and have the same image of the current time CLK. The current value of the time is denoted hereafter as T.

[0068] It is associated a bit-rate, denoted r.sub.i, with each flow i, whether it is Normal or Express:

[0069] The volume of data transmitted in the recurring transmission windows of an Express flow allows defining the bit-rate of that flow,

[0070] Normal flows can be allocated with a bit-rate (maximum, enforced or not).

[0071] The sum of all bitrates r.sub.i must not be greater than the total capacity of the link For the sake of simplification, all links have preferably (but optionally) the same capacity, denoted ρ hereafter.

[0072] The transmissions of frames of each Express flow follow a periodic pattern. The table TST (of finite length) can contain the succession of all successive transmission window opening and closing times (respectively t.sup.o.sub.k and t.sup.c.sub.k) of all the scheduled Express flows. This means that an Express frame or fragment is transmitted within a time interval [t.sup.o.sub.k, t.sup.c.sub.k] while a Normal frame or fragment is rather transmitted in a left time interval [t.sup.c.sub.k, t.sup.o.sub.k+1] (with k modulo n). The assumption is also made that the duration of each widow is pre-computed so that, when opened, the window can permit the transmission of the Express-frames for which it has been provided. All Express window opening and closing times are stored in the circular table TST (with k[n] shown by the circular arrow CIRC on FIG. 8). In practice, each entry of the table is a couple (t.sup.o.sub.k, t.sup.c.sub.k) which respectively represents the opening time and the closing time of a window k. An offset corresponding to the depth of the table is added to the entry at each time when a read pointer of the table rewinds back to the first element of the table. The read pointer takes into account the current value of time T.

[0073] As for Normal flows, each normal frame stored at the head of each flow queue is associated with a theoretical transmission time (TT.sub.i), which corresponds to the theoretical time the first bit of the frame is supposed to be transmitted at. TT.sub.i are sorted in increasing order and the Normal frame or fragment with the least TT.sub.i (referenced min(TTi) in FIG. 9) is the next Normal frame or fragment candidate for insertion on the multiplex.

[0074] With reference now to FIG. 9:

[0075] S is the size of the current Normal-frame or fragment to be transmitted,

[0076] minfs is the minimum fragment size as defined by IEEE 802.3br (“minFrag” according to the notation of that value in that specification),

[0077] r.sub.i is the bitrate of flow i,

[0078] ρ is a mean capacity (in the example described here) of a link,

[0079] Δt is a time increment during a temporisation step S2 (for example the duration of a one bit transmission),

[0080] TT.sub.i are the theoretical time the first bit of a frame or fragment FR in a queue Q.sub.i is supposed to be transmitted at, before the computation according to the method of the invention.

[0081] A Normal-frame or fragment is inserted on the multiplex (actually transmitted) at least if the following conditions are met:

[0082] a) T≧min(TT.sub.i) (arrow “OK” from test a) on FIG. 9) and

[0083] b) T is not comprised in the current (t.sup.o.sub.k, t.sup.c.sub.k) window (arrow “KO” from test b) on FIG. 9) and

[0084] c) S≧2*minfs (arrow “OK” from test c) on FIG. 9).

[0085] Condition a) means that the current time T has come to start considering normal frames.

[0086] If condition a) is systematically verified, the system guarantees that each Normal flow is not transmitted at a rate greater than r.sub.i. It should be noted that condition a) can be made optional if fairness only between RC flows is to be achieved relatively to a weight represented by their respective bit-rate r.sub.i.

[0087] Condition b) means that it is checked whether the current time T is within a time window k (e.g. between its opening time t.sup.o.sub.k, and its closing time t.sup.c.sub.k) so as to give priority to the transmission of an Express frame in that case.

[0088] Condition c) means that it is checked whether (if the conditions a) and b) above are achieved) that a Normal frame can be fragmented of not. If it cannot be fragmented (arrow KO at the output of test c)), then a temporisation step S2 is performed until the time duration [t.sup.c.sub.k, t.sup.o.sub.k+1] (with k [n], meaning “k modulo n”) is long enough to send this non fragmentable Normal frame. If the Normal frame can be fragmented (arrow OK at the output of test c)), then further tests and steps are implemented as detailed below so as to perform the fragmentation in good and fair conditions.

[0089] The process starts with a first step S1, of:

[0090] Considering Normal frames or fragments to transmit (the algorithm points to a routine dedicated to Normal frames and fragments to process for transmission—for sending a whole frame or a fragment, common steps of the routine are used for algorithmic optimization),

[0091] Then, calculating the TT.sub.i in each queue,

[0092] Referring to the table TST so as to determine the current time window having the current index k,

[0093] Referring to the clock so as to determine the current time value T.

[0094] Then, step a) is performed: if current T has come for sending a Normal frame or fragment, then it is verified whether, considering the current window index k, the current time falls after the closing of that time window k (arrow OK from test T3), meaning then that the window index k needs to be updated (increment of step S4, with k [n]). Then, step b) is performed so as to determine whether priority is to be given to Express frames. Otherwise (arrow KO from test b)), it is determined whether the Normal frame can be fragmented. If not (arrow KO from test c)), then test T6 can be performed with the information that the frame cannot be fragmented (dashed arrow line KO from test c)). In test T6, it is determined whether a whole and complete frame can be transmitted, while taking into account the remaining time T to the next window opening t.sup.o.sub.k, and the link capacity ρ. If yes (arrow OK from test T6), then the frame FR is sent at step S7. The next time scheduled TT.sub.i for sending the next frame (or fragment as it will be seen later) is updated at step S8, while taking into account the flow bit-rate r.sub.i for sending a new frame having a size S. A test T9 is further performed so as to read the latest fragment—typically its heading—to be transmitted at step S7, to determine whether that fragment was the end of a frame. In the present branch of following the algorithm, since a complete frame is sent at step S7, the output of test T9 should be “OK” and a next candidate frame is considered (step S10) to be processed referring back to step S1.

[0095] If a whole and complete frame cannot be transmitted according to the test T6 (dashed arrow line KO from test T6, with the information that the frame cannot be fragmented), then a temporisation step is performed in step S2, so as to wait for a new time interval [t.sup.c.sub.k, t.sup.o.sub.k+1] long enough to send the whole frame.

[0096] If the frame can be fragmented (arrow OK from step c)), then fragmentation is contemplated and in test T5 it is checked whether the time left until the next window opening is long enough to send a fragment having a duration minfs. If yes (arrow OK from test T5), it is checked further whether a whole frame can be sent (at test T6, explained above). If fragments only can be sent (arrow KO from test T6 with the information that the frame can be fragmented), it is checked, at test T12, whether the remaining time until the next window opening is sufficient to send a remaining part of a complete frame (arrow “KO” of test T12 which condition can be written also: (t.sup.o.sub.k−T) ρ≧S−minfs: meaning then that at least one fragment (complementary for building the complete frame) having a length S−minfs can be created and sent at step S13 without disturbing the next transmission frame or fragment). Then, the scheduled times TT.sub.i are updated accordingly at step S14, and so as the next frame length to consider at step S15. Then, it can be checked whether that fragment is an end of frame (test T9). Normally, it should. It is nevertheless preferred to check it in the shown example because a last step (not shown on FIG. 9) can consist on calculating the FCS (Frame Check Sequence) to add at the end of the frame to transmit.

[0097] If (t.sup.o.sub.k−T)ρ≦S−minfs (arrow OK from test T12 while (t.sup.o.sub.k−T)* ρ≧minfs in test T5), this means that at least one fragment can be created and sent at step S16 (but not a last fragment terminating a frame). The length of the fragment is given by (t.sup.o.sub.k−T)* ρ in step S16. Then, the scheduled times TT.sub.i are updated accordingly at step S17, and so as the next frame length to consider at step S18. Then, it can be checked whether that fragment is an end of frame (test T9). Here, it can or cannot. If not (arrow KO from test T9), then a next fragment is considered in step S11 to implement with it step S1 again.

[0098] It should be noted that when step S1 is implemented again, the respective times TTi in the queues Q1, . . . , Qm (of the different flows F1, . . . , Fm) have been updated in one of the steps S8, S14 and S17, and the current time T has also advanced during the transmission of the fragment or the frame in one of steps S7, S13, S16. Therefore, these parameters TTi and T are naturally updated and ready to be used at step S1 (with a current window index k which can be updated also at step S4).

[0099] The main steps of the algorithm shown on FIG. 9 are listed below:

TABLE-US-00001 a) If T ≧ min(TT.sub.i) and b) If T is not comprised in the current (t.sup.o.sub.k, t.sup.c.sub.k) window and c) If S ≧ 2* minfs, If (t.sup.o.sub.k− T)* ρ ≧ minfs If (t.sup.o.sub.k− T)* ρ ≧ S Send frame or final fragment TT.sub.i = TT.sub.i + (S/r.sub.i) Select next frame of fragment candidate for transmission Else If (T+ S/ρ) − t.sup.o.sub.k >= minfs/ ρ Create and send fragment of length (t.sup.o.sub.k − T)* ρ TT.sub.i = TT.sub.i + ((t.sup.o.sub.k − T)* ρ/r.sub.i) S = S − (t.sup.o.sub.k − T)* ρ Select next fragment or frame candidate for transmission Else Create and send fragment of length (S − minfs) TT.sub.i = TT.sub.i + ((S − minfs)/r.sub.i) S = minfs Select next fragment or frame candidate for transmission Endif Endif Endif Else If (T+ S/ρ) < t.sup.o.sub.k Send frame or final fragment TT.sub.i = TT.sub.i + (S/r.sub.i) Select next frame or fragment candidate for transmission Endif Endif

[0100] The invention can be applied to any domain where a workload (computing time, process scheduling, etc.) has to be shared in time. In those cases, no particular change is to be made.

[0101] The invention can apply in networks supporting mix of applications with various time constraints (ranging from strong real-time (e.g. critical control loops) to more relaxed latency and synchronisation (audio-video transport) and best-effort).

[0102] The present invention can be implemented for example in time sensitive control networks (or any network such as in factory automation, or automotive or utilities or trains).

[0103] This invention solves a standard implementation problem but can be used as support for the standardisation any other “transmission selection” mechanism within IEEE 802.1 TSN, providing then a network traffic shaping with ultra-low latency and a network load sharing optimisation.

[0104] It has been described above in details the processing of several flows in parallel queues (Q1, . . . , Qm) like shown on FIG. 7. However, the invention can be performed also with a single queue of one single flow. Then, each frame or fragment of the queue has a processing time TTi which can be updated and rearranged at each implementation of the steps shown on FIG. 9 so as to determine which fragment or frame is to process at a next implementation of those steps.

[0105] The present invention can be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which, when loaded in an information processing system (for example a user equipment or a network element), causes the information processing system to carry out the invention. Computer program means or computer program in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after the conversion to another language. Such a computer program can be stored on a computer or machine readable medium allowing data, instructions, messages or message packets, and other machine readable information to be read from the medium. The computer or machine readable medium may include non-volatile memory, such as ROM, Flash memory, Disk drive memory, CD-ROM, and other permanent storage. Additionally, a computer or machine readable medium may include, for example, volatile storage such as RAM, buffers, cache memory, and network circuits. Furthermore, the computer or machine readable medium may comprise computer or machine readable information in a transitory state medium such as a network link and/or a network interface, including a wired network or a wireless network, that allow a device to read such computer or machine readable information.

[0106] While there has been illustrated and described what are presently considered to be the preferred embodiments of the present invention, it will be understood by those skilled in the art that various other modifications may be made, and equivalents may be substituted, without departing from the true scope of the present invention. Additionally, many modifications may be made to adapt a particular situation to the teachings of the present invention without departing from the central inventive concept described herein. Furthermore, an embodiment of the present invention may not include all of the features described above. Therefore, it is intended that the present invention not be limited to the particular embodiments disclosed, but that the invention include all embodiments falling within the scope of the invention as broadly defined above.

[0107] A person skilled in the art will readily appreciate that various parameters disclosed in the description may be modified and that various embodiments disclosed and/or claimed may be combined without departing from the scope of the invention.

INDUSTRIAL APPLICABILITY

[0108] This invention is applicable to networks in many kinds of fields.