image accueil du logo de la rubrique

Tetrys : A novel on-the-fly coding scheme for time constrained applications

You are here : Tetrys » Tetrys » Tetrys


A novel on-the-fly coding scheme for time constrained applications

D 17 May 2018    

TETRYS enables a new reliability algorithm specifically useful when retransmission is either problematic or not possible. TETRYS is based on a new on-the-fly erasure coding concept specifically designed to operate efficient reliable transfer over bi-directional links.

Thanks to its "on-the-fly encoding" approach, Tetrys enables a fully or partially reliable delivery of contents, potentially with real-time constraints, better and faster than the TCP protocol or than traditional block FEC solutions would enable.

How to deal with packet losses?

Reliable transmissions over lossy channels are often either a must (e.g. in case of a file transfer) or a highly desired feature, even if a limited amount of losses may be tolerated (e.g. in case of video streaming). The origin of losses does not matter: it may be caused by bad reception conditions in case of wireless networks, or by IP datagram erasures in congested link. The result is the same and a certain number of data packets are missing.

Retransmitting lost packets is a solution. TCP, the dominant protocol over the Internet, heavily relies on TCP, even for video streaming (e.g. with the various “adaptive streaming over HTTP” techniques heavily used in video over the Internet services). However retransmitting requires both that a feedback channel exists (to know what is lost) and that data arrive in due time (it’s not necessarily the case with real-time video transmissions).

Adding redundancy to the flow of data sent, thanks to an FEC code, is another solution. This FEC code is a smart component that can calculate redundant packets from a set of data packets at a sender, and reciprocally that uses redundant packets to recover the missing data packets in case of losses. However the usual approach consists in calculating redundant packets from a predetermined set of packets. The number of redundant packets can be either fixed or can depend on reception feedbacks. That’s efficient and can be used even if the feedback channel is limited and in case of real-time content.

Tetrys is a solution that goes beyond these two techniques, taking the best of them, thanks to a unified encoding approach.

What about Tetrys and "On-the-Fly coding"?

TETRYS enables a new reliability algorithm that we call “on-the-fly encoding”. In the figure below, the sender periodically adds a redundant packet (noted R(..), in red) after two data packets (noted P.., in black). We assume that a feedback channel exists, also prone to losses.
The key innovation of Tetrys is the way encoding is performed: only non-acknowledged but useful packets are considered during encoding, using a sliding window over the data packets. This sliding window contains a number of packets that varies over the time, depending on what packets have been received or decoded so far at the receiver, and on the arrival of acknowledgements at the sender (they may be lost too).

In this example, R(1,2) is a redundant packet calculated with the two packets of the encoding window, P1 and P2. Since the acknowledgment of P1 has been lost, the encoding window grows and encompasses packets P1 to P4 the next time a redundant packet is calculated, R(1,4). In the absence of acknowledgment, the encoding window keeps on growing… until an acknowledgment of packets P1 to P8 arrives at the sender. Then the encoding window is updated to contain only P9 and P10,and the R(9,10) redundant packet is then calculated.

"On the fly encoding" is the key technology of Tetrys: only non-acknowledged and useful data packets are protected.

Full or partial reliability?

Usually, full reliability is only feasible if data is acknowledged by the receiver (or all the receivers with multicast transmissions), even lately. Applied to Tetrys, it means that a data packet stays in the encoding window until it is acknowledged.

But full reliability is not necessarily what an application is looking for. Indeed, a data packet may be useful only for a given time span. Think about a video frame. If this frame arrives after the moment it should have been displayed, it’s of no use. In that case it’s wiser to drop it anyway. Applied to Tetrys, it means that a data packet should stay in the “sliding encoding window” at most for a certain predefined time that depends on its real-time validity period. A data packet is either removed from the encoding window once acknowledged or upon reaching its maximum validity period.

Why is Tetrys a "must have"?

Tetrys is both an FEC coding scheme (e.g. it heavily relies on random linear FEC codes) and a transport protocol (it defines packets formats and protocol rules). As such it can be applied in several different places in a protocol stack:

  • below an application generating RTP packets for real-time video content, because of Tetrys exceptional benefits in terms of timely delivery of contents;
  • below TCP where it can help recovering from losses in wireless channels. Here poor reception conditions heavily hinder TCP connections since TCP assumes losses are caused by congestions and backs off, which is of no benefit in case of bad signal/noise issues;
  • in Delay Tolerant Network (DTN) systems, where feedbacks are not necessarily timely, nor necessarily feasible. In that case Tetrys offers a robust delivery even in presence of poor packet and feedback transmissions.

Tetrys provides a unified content delivery service that ensures a faster data availability to the receiving application compared to traditional techniques.

Contacts: Emmanuel Lochin and Jérôme Lacan