**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# On Time Synchronization Issues in Time-Sensitive Networks with Regulators and Nonideal Clocks

Jean-Yves Le Boudec, Ludovic Bernard Gérard Thomas

*Association for Computing Machinery, *2020

Article de conférence

Article de conférence

Résumé

Flow reshaping is used in time-sensitive networks (as in the context of IEEE TSN and IETF Detnet) in order to reduce burstiness inside the network and to support the computation of guaranteed latency bounds. This is performed using per-flow regulators (such as the Token Bucket Filter) or interleaved regulators (as with IEEE TSN Asynchronous Traffic Shaping, ATS). The former use one FIFO queue per flow, whereas the latter use one FIFO queue per input port. Both types of regulators are beneficial as they cancel the increase of burstiness due to multiplexing inside the network. It was demonstrated, by using network calculus, that they do not increase the worst-case latency. However, the properties of regulators were established assuming that time is perfect in all network nodes. In reality, nodes use local, imperfect clocks. Time-sensitive networks exist in two flavours: (1) in non-synchronized networks, local clocks run independently at every node and their deviations are not controlled and (2) in synchronized networks, the deviations of local clocks are kept within very small bounds using for example a synchronization protocol (such as PTP) or a satellite based geo-positioning system (such as GPS). We revisit the properties of regulators in both cases. In non-synchronized networks, we show that ignoring the timing inaccuracies can lead to network instability due to unbounded delay in per-flow or interleaved regulators. We propose and analyze two methods (rate and burst cascade, and asynchronous dual arrival-curve method) for avoiding this problem. In synchronized networks, we show that there is no instability with per-flow regulators but, surprisingly, interleaved regulators can lead to instability. To establish these results, we develop a new framework that captures industrial requirements on clocks in both non-synchronized and synchronized networks, and we develop a toolbox that extends network calculus to account for clock imperfections.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (22)

Chargement

Chargement

Chargement

Concepts associés (15)

Réseau informatique

thumb|upright|Connecteurs RJ-45 servant à la connexion des réseaux informatiques via Ethernet.
thumb|upright
Un réseau informatique ( ou DCN) est un ensemble d'équipements reliés entre eux pour échan

Time-Sensitive Networking

Time-Sensitive Networking (TSN) est un ensemble de normes pour la mise en réseau sensible au temps. Elles sont définies par le groupe de travail IEEE 802.1.
Ce groupe de travail TSN a été formé en

Temps

thumb|Chronos, dieu du temps de la mythologie grecque, par Ignaz Günther, Bayerisches Nationalmuseum à Munich.
vignette|Montre à gousset ancienne
Le temps est une notion qui rend compte du changement

We study networks of FIFO nodes, where flows are constrained by arrival curves. A crucial question with these networks is: Can we derive a bound to the maximum delay that a packet can experience when traversing the network, and to the maximum queue size at each node? For a generic FIFO network these are still open issues: Some examples show that, contrary to common sense, no matter how low the maximum node utilization is in the network, it is possible to build an example of an unstable FIFO network. The importance of this issue lies in the necessity of hard bounds on packet delay and queue size, in order to enable QoS guarantees in these networks. For this reason we choose to tackle this problem through a deterministic approach, based on worst-case behavior. Our first result is the determination of a general method to derive sufficient conditions for the stability of a network: We show how, with a proper choice of the observed variables in the network and with the use of network calculus results, it is possible to derive the expression of an operator whose properties are associated to the stability of the network. Exploiting this method on a simple example, we first derive a generalization of the RIN result to heterogeneous settings and to leaky bucket constrained flows. Through some realistic examples, we show how this method allows networks to achieve a level of utilization which is more than three times larger than the best existing result. By applying the general method to three different variable classes, we derive some new sufficient conditions for stability, that perform largely better than all the main existing results, and we show how they can all be derived from the new sufficient conditions. Finally, we present a new formula for the computation of end-to-end delay bounds in a network of GR nodes.

Christina Fragouli, Emina Soljanin

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.

2004,

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.