**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# On Cyclic Dependencies and Regulators in Time-Sensitive Networks

Abstract

For time-sensitive networks, as in the context of IEEE TSN and IETF Detnet, cyclic dependencies are associated with certain fundamental properties such as improving availability and decreasing reconfiguration effort. Nevertheless, the existence of cyclic dependencies can cause very large latency bounds or even global instability, thus making the proof of the timing predictability of such networks a much more challenging issue. Cyclic dependencies can be removed by reshaping flows inside the network, by means of regulators. We consider FIFO-per-class networks with two types of regulators: per-flow regulators and interleaved regulators (the latter reshape entire flow aggregates). Such regulators come with a hardware cost that is less for an interleaved regulator than for a per-flow regulator; both can affect the latency bounds in different ways. We analyze the benefits of both types of regulators in partial and full deployments in terms of latency. First, we propose Low-Cost Acyclic Network (LCAN), a new algorithm for finding the optimum number of regulators for breaking all cyclic dependencies. Then, we provide another algorithm, Fixed-Point Total Flow Analysis (FP-TFA), for computing end-to-end delay bounds for general topologies, i.e., with and without cyclic dependencies. An extensive analysis of these proposed algorithms was conducted on generic grid topologies. For these test networks, we find that FP-TFA computes small latency bounds; but, at a medium to high utilization, the benefit of regulators becomes apparent. At high utilization or for high line transmission-rates, a small number of per-flow regulators has an effect on the latency bound larger than a small number of interleaved regulators. Moreover, interleaved regulators need to be placed everywhere in the network to provide noticeable improvements. We validate the applicability of our approaches on a realistic industrial time-sensitive network.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (12)

Loading

Loading

Loading

Related concepts (8)

Computer network

A computer network is a set of computers sharing resources located on or provided by network nodes. Computers use common communication protocols over digital interconnections to communicate with eac

Computer hardware

Computer hardware includes the physical parts of a computer, such as the case, central processing unit (CPU), random access memory (RAM), monitor, mouse, keyboard, computer data storage, graphics ca

FIFO (computing and electronics)

In computing and in systems theory, first in, first out (the first in is the first out), acronymized as FIFO, is a method for organizing the manipulation of a data structure (often, specifically a d

We consider a cross-layer design of wireless ad-hoc networks. Traditional networking approaches optimize separately each of the three layers: physical layer, medium access and routing. This may lead to largely suboptimal network designs. In this work, we propose a jointly optimal design of the three layers, and we show a significant performance improvement over the conventional approach. In the first part of this thesis, our goal is to select appropriate performance metrics for the joint optimization problem. To that respect, we analyze several existing rate-maximization performance metrics for wireless ad-hoc networks: maximizing the sum of rates, max-min fairness and proportional fairness. We first show with several examples that it is not clear if and how max-min fairness can be defined on each one of the examples. We give a formal proof that the max-min fair rate allocation exists on a large class of sets of feasible rates, among which are the feasible-rate sets of all known ad-hoc networking examples. We also give a centralized algorithm to compute the max-min fair allocation whenever it exists. Next, we compare the three metrics for ad-hoc scenarios in terms of efficiency and fairness. We prove that, similar to wired networking,maximizing the sum of rates leads to gross unfairness and starvation of all but the flows with the best channel conditions. We also prove that, contrary to wired networking, max-min fairness yields all flows having the same rate, thus causing large inefficiencies. These findings offer theoretical explanations to the inefficiency and unfairness phenomena previously observed in the contexts of 802.11 and UWB networks. Finally, we show that proportional fairness achieves a good trade-off between efficiency and fairness and is a good candidate for a rate-based performance metric in wireless ad-hoc settings. Having shown that the proportional fairness is an appropriate optimization objective for our problem, in the second part of the thesis we consider a joint optimization of rates, transmission powers, medium access (scheduling) and routing, where the goal of the optimization is to achieve proportional fairness. We first analyze networks built on physical layers that have a rate which is a linear function of SNR at the receiver (such as UWB or low-gain CDMA systems). We find that the optimal solution is characterized by the following principles: (1)Whenever a node transmits, it has to transmit with the maximum power; otherwise it has to remain silent (0 - PMAX power control). (2) Whenever data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. (3) When a source transmits, it adapts its transmission rate according to the level of interference at the destination due to sources transmitting in parallel. (4) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination. We also show that (5) relaying along a minimum energy and loss route is better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally (6), the design of the optimal MAC protocol is independent of the choice of the routing protocol. We present a theoretical proof of optimality of 0 - PMAX power control, and the remaining findings we show numerically on a large number of random network topologies. Next, we consider narrow-band networks, where rate function is a strictly concave function of SNR. There, previous findings do not always hold. We show that in some cases, the size of the exclusion region and the optimal routing depend on transmission powers, and that the optimal MAC design depends on the choice of routing. Nevertheless, as we show with the example of 802.11 networks, a significant improvement over the existing 802.11 MAC can be achieved even with simpler, suboptimal strategies. Although this result is shown by simulations on a simplified model, it still gives further directions on how to improve the performance of RTS/CTS based protocols.

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

For time-sensitive networks, as in the context of IEEE TSN and IETF Detnet, cyclic dependencies are associated with certain fundamental properties such as improving availability and decreasing reconfiguration effort. Nevertheless, the existence of cyclic dependencies can cause very large latency bounds or even global instability, thus making the proof of the timing predictability of such networks a much more challenging issue. Cyclic dependencies can be removed by reshaping flows inside the network, by means of regulators. We consider FIFO-per-class networks with two types of regulators: per-flow regulators and interleaved regulators (the latter reshape entire flow aggregates). Such regulators come with a hardware cost that is less for an interleaved regulator than for a per-flow regulator; both can affect the latency bounds in different ways. We analyze the benefits of both types of regulators in partial and full deployments in terms of latency. First, we propose Low-Cost Acyclic Network (LCAN), a new algorithm for finding the optimum number of regulators for breaking all cyclic dependencies. Then, we provide another algorithm, Fixed-Point Total Flow Analysis (FP-TFA), for computing end-to-end delay bounds for general topologies, i.e., with and without cyclic dependencies. An extensive analysis of these proposed algorithms was conducted on generic grid topologies. For these test networks, we find that FP-TFA computes small latency bounds; but, at a medium to high utilization, the benefit of regulators becomes apparent. At high utilization or for high line transmission-rates, a small number of per-flow regulators has an effect on the latency bound larger than a small number of interleaved regulators. Moreover, interleaved regulators need to be placed everywhere in the network to provide noticeable improvements. We validate the applicability of our approaches on a realistic industrial time-sensitive network.

Razvan Cristescu, Martin Vetterli

We consider the problem of correlated data gathering by a network with a sink node and a tree based communication structure, where the goal is to minimize the total trans- mission cost of transporting the information collected by the nodes, to the sink node. For source coding of correlated data, we consider a joint entropy based coding model with explicit communication where coding is simple and the transmission structure optimiza- tion is difficult. We first formulate the optimization problem definition in the general case and then we study further a network setting where the entropy conditioning at nodes does not depend on the amount of side information, but only on its availability. We prove that even in this simple case, the optimization problem is NP-hard. We propose some efficient, scalable, and distributed heuristic approximation algorithms for solving this problem and show by numerical simulations that the total transmission cost can be significantly improved over direct transmission or the shortest path tree. We also present an approximation algorithm that provides a tree transmission structure with total cost within a constant factor from the optimal.

2006