Per-Flow Performance Guarantees in Networked Systems with Complex Feedback Structures

We first consider a basic system with a feedback structure as in Figure 3 on the left. We assume that the server $S$ has a finite buffer that holds incoming packets of the arrivals $A$. After processing, some departures $D$ leave the server. To ensure that there are no more arrivals to the node than the buffer can hold at a time, the node signals to the sender (or previous node) whether space is still left in the buffer. This feedback is modeled by some function $\mathrm{\Phi }$ that depends on the departures. If there is no more space in the buffer, the sender throttles its sending rate accordingly and buffers the data itself until it is allowed to send again, essentially performing a blocking write. This mechanism is represented by the gray backwards loop in Figure 3. The effect of the throttling adjusts $A$ to $A^{\prime }$, which we call the effective arrivals to the server.

The analysis of the system is then done in several steps. We call the model in Figure 3 on the left a closed-loop system, i.e., the system has (feedback) edges that form a closed loop. The closed-loop system is min-plus non-linear [6, p. xix], and consequently cannot be directly analyzed using NC, as the framework is tailored to min-plus linear systems. It is hence the first step to resolve this feedback loop by transforming the closed-loop into a min-plus linear open-loop system. The general idea here is that we “encode” the flow control into the node at which the control signal is fed back into the data flow. The feedback is then effectively exerted by the server itself by adjusting the service it can offer to incoming arrivals. The resulting open-loop system is min-plus linear, and can be analyzed using NC. Since the transformation is a safe operation, any performance bounds we obtain for the open-loop system are also valid bounds for the closed-loop system. There is, however, generally no equivalence between the two systems, i.e., the open-loop system is an upper bound on the closed-loop system.

For us to be able to transform the closed-loop system for a NC analysis, we perform the transformation of the example system in Figure 3 from the left to the right. To this end, we introduce some preliminaries. We let $F=(i,j,\mathrm{\Phi })$ be a feedback constraint or loop, where $i$ is the server in front of which the feedback is entering the data path, $j$ is the server behind which the feedback loop starts. $\mathrm{\Phi }(D(t))$ represents the cumulative feedback at time $t$, and represents the type of feedback that is employed, as discussed previously. We call $\phi \in {ℱ}^{\uparrow }$ with $\phi (0)>0$ a feedback curve when $\mathrm{\Phi }\circ D\ge D\otimes \phi$. By abuse of notation, we also write $F=(i,j,\phi )$ interchangeably with $F=(i,j,\mathrm{\Phi })$. In most existing NC work on flow control, a fixed window size $u$ is assumed that cannot be exceeded by incoming traffic, i.e., $\mathrm{\Phi }(D(t))=D(t)+u$, $u>0$. The feedback curve for this fixed window size is part of the general model presented in [7, Chapter 6.2.2] and is defined as

since $D\otimes I_u(t)=D(t)+u$ (see also [12, p. 79]). Further, we specify the effective arrivals as

Through the usage of the minimum ($\wedge$) as a throttle, we ensure that the arrivals can never exceed the allowed maximum size $D\otimes \phi$ to not violate the feedback control.

Besides causality in the system, i.e., $D\le A^{\prime }$, it is further assumed that the server $S$ offers a min-plus service curve $\beta \in {ℱ}^{\uparrow }$ to $A^{\prime }$

where we also used Equation (5). Based on Equation (6), the next step is to transform the closed-loop into an open-loop system (see also Figure 4). We restate the central result from [12, Theorem 2.1.6]:

Using this result, we effectively encode the feedback constraint into $\beta$ by calculating a transformed service curve $\stackrel{\curvearrowleft }{𝛽}$ (also called equivalent service curve in [40]). Here, the transformed service curve of $\beta$ is $\stackrel{\curvearrowleft }{𝛽}=\beta \otimes {(\beta \otimes \phi )}^{\ast }$. The transformation of the example closed-loop into open-loop system is illustrated in Figure 4. Here, the feedback loop is replaced by the transformed service curve. Recalling the definition of the sub-additive closure in Definition 13, we illustrate its effects in the transformed service curve. Assuming that $\beta$ is a rate-latency service curve and $\phi =I_u$, the transformed service curve is depicted as the red curve in Figure 5. The grey curves illustrate the sub-additive closure operation ${({\beta }_{R,T}\otimes I_u)}^{\ast }$. Here, each curve represents the result of another self-convolution of ${\beta }_{R,T}\otimes I_u$. The illustrated two different scenarios depend on the relation between the service curve parameters $R$ and $T$ and the size of the feedback constraint $u$. If we have for the so-called bandwidth-delay product [1] that $R\cdot T\le u$, the feedback constraint has no effect on the system, and $\stackrel{\curvearrowleft }{𝛽}=\beta$ (see Figure 5(b)). This stems from the fact that ${\beta }_{R,T}$ is always smaller than ${({\beta }_{R,T}\otimes I_u)}^{\ast }$. If $R\cdot T>u$, calculating the sub-additive closure leads to a reduction of the transformed service curve, and consequently . This can be observed in Figure 5(a). This reduction stems from the fact that ${\beta }_{R,T}$ quickly becomes larger than ${({\beta }_{R,T}\otimes I_u)}^{\ast }$. Hence, $\stackrel{\curvearrowleft }{𝛽}$ follows the sub-additive closure ${({\beta }_{R,T}\otimes I_u)}^{\ast }$.

To recapitulate, we are given a closed-loop system, similar to the system we have examined in the introductory example. We use Theorem 15 to encode the feedback constraint existing in the closed-loop system into the service curve directly, resulting in an open-loop system that has no feedback any more, but a transformed service curve $\stackrel{\curvearrowleft }{𝛽}$. This new system constitutes a min-plus linear upper bound to the original system and can be analyzed with respect to performance bounds using NC.

We introduce another aspect of feedback constraints that will be subject to analysis in the paper. Assuming a static window flow control using $\phi =I_u$ for some $u>0$, we can obtain the optimal size of $u$ such that $\beta =\stackrel{\curvearrowleft }{𝛽}$ holds by

This is studied in detail in [1, 12, 7]. Looking again at Figure 5, the optimal $u$ would be attained if $u=R\cdot T$, since all the grey curves would then lie on the red curve, or, more formally, ${\beta }_{R,T}={({\beta }_{R,T}\otimes I_u)}^{\ast }$. We will expand on this result in Section 5.2.

We note that Theorem 15 makes no assumption about the type of service curve that is required to perform the transformation to an open-loop system, i.e., it only requires a min-plus service curve. In fact, we can show that this is the only relevant type of service curve we have to consider. We will discuss this in more detail in the next section.

Here, we show that, assuming strict service curves, feedback constraints would have no effect on closed-loop systems. We prove this observation for the special case of fixed window flow control, i.e. $\phi =I_u$. To this end, we first show that a backlogged period of a system without feedback is contained in the backlogged period of a closed-loop system.

So far, we only treated the basic case of a single feedback constraint. However, what we try to achieve is to be able to transform a closed-loop system with arbitrary many flow control mechanisms into an open-loop system. This has not been done in literature, previously. We have results for a feedback constraint spanning up to two nodes [12, 5, 8, 7, 19], but there are no existing results for feedback constraints spanning an arbitrary number of nodes. This is desirable, however, as we can have systems that employ different kinds of feedback mechanisms, such as an end-to-end window flow control or more complex signaling mechanisms for finite buffers that span over more than two nodes. This inevitably leads to feedback constraints that have interdependencies with other feedback constraints, where the transformed service curve of one feedback constraint is part of another feedback constraint. In Section 4, we identify all of these interdependence types, and how to transform them into corresponding open-loop systems. This, in return, enables the NC analysis for any kind of feedback structure in a tandem network, regardless of the existing interdependencies between feedback constraints in the network.

We assume a network as in Figure 6, where we have $n$ nodes as well as one feedback constraint $F=(i,j,\phi )$ in the system. To that end, we first generalize some of the equations introduced in the previous section. We define the effective arrivals $A_i^{\prime }$ at server $i$ as

The departures $D_i$ at server $i$ are characterized by

Theorem 15 can then be generalized as follows:

Figure 7 illustrates the general feedback tandem network that we aim to be able to analyze. Here, we consider $n$ nodes in a network, as well as an arbitrary number of feedback constraints $l$. In Figure 7, all possible interdependence types between feedback constraints that may occur are shown. In addition, a general flow aggregate consisting of multiple flows that may interfere with the flow of interest in any possible way across the nodes is illustrated (in colors). We point out again that the transformation of a closed-loop into an open-loop system is done before we consider any existing flows in the system.

In the following, we assume an ordered set of feedback constraints $F_l=(i_l,j_l,{\phi }_l),l=1,\mathrm{\dots },k$. The feedback loops are lexicographically ordered by the data path entering node $i_l$ as first criterion in ascending order, and the starting node of the control signal $j_l$ as second criterion in descending order. Let $F_l$ and $F_m$ be two feedback constraints with $l\le m$. If , then the two feedback loops are not interdependent with each other and can be evaluated independently from each other using Proposition 18. If, however, $j_l\ge i_m$, then they are interdependent and their respective evaluation needs to take that into account.

There are different types of interdependence. First, let us assume that , i.e., the second feedback enters the data path at a strictly later point in the tandem than the first one. If also $j_l\ge j_m$, we have a so-called contained interdependency between the constraints $F_l$ and $F_m$ (see also Figure 8 for an example). If, on the other hand, , then we call it an overlapping interdependency between $F_l$ and $F_m$ (see also Figure 9 for an example). Now let us assume $i_l=i_m$, i.e., both feedback loops enter the data path at the same point in the tandem (see also Figure 10(a) for an example). Due to the lexicographical ordering of the feedback constraints we have that $j_l\ge j_m$. While this configuration is similar to the contained interdependence type, the treatment of this special case justifies a separate type called compounded interdependency.

Figures 8-10 illustrate canonical versions of these three interdependence types, i.e., minimal tandem networks that exhibit each of the previously classified interdependence types. We note that we can adjust these structures to a larger size by making use of Proposition 18. In the following, we derive transformed service curves as well as an end-to-end service curve for each canonical interdependence type.

It is left to discuss in which order the closed-loop systems have to be transformed into open-loop systems to deal with the complex feedback structure of a general tandem as in Figure 7. In fact, the lexicographic order defined in Section 4.2 is instrumental for that purpose. As we have observed for all interdependence types, $F_2$ had to be evaluated before $F_1$, i.e., we need to proceed in reverse lexicographic order to transform the canonical cases into open-loop systems.

This directly generalizes for the feedback tandem. Given a network with $k$ feedback constraints in lexicographic order, the last feedback constraint $F_k$ does not depend on any other constraint $F_l$, . More specifically, since $i_k\ge i_l$, $F_l$ cannot overlap $F_k$; also, in case that $i_k=i_l$, then $j_k\le j_l$ and thus $F_l$ is not contained in $F_k$. At most we could have the special case of a compounded interdependency where $i_k=i_l$ and $j_k=j_l$. Yet, as discussed at the end of the previous subsection, we can combine them into a single feedback constraint. Hence, we first open the loop for $F_k$, then apply the same reasoning for the remaining feedback constraints until we have reached a completely open-loop tandem network.

We point out that even more general feedback networks than a tandem could be analyzed, based on the evaluation precedence rules as we obtain them from the different interdependence types. We can build a (directed) precedence graph with the feedback constraints as vertices; determining the interdependence type between two constraints $F_i$ and $F_j$ would then govern whether an edge between vertex $i$ and $j$ exists and its direction. If this precedence graph had no cycles, i.e. it is a directed acyclic graph, then we could perform a topological sort to find a feasible evaluation order of the feedback loops. The cyclic case we leave for future work as it is out of scope for this paper.

In principle, after we have dealt with all feedback loops and have arrived at an open-loop system, we seem to face a classical NC problem: We consider $f_1$ to be the flow of interest (foi), and $f_2,\mathrm{\dots },f_m$ to be cross flows interfering with the flow of interest at different sub-paths of the tandem (see again Figure 7, especially the lower part); each flow $f_j$ is constrained by a maximal arrival curve ${\overline{\alpha }}_j$. Yet, for the servers $S_i$, classically we would need to assume strict service curves ${\beta }_i$ in order to make use of existing network analyses like, e.g. PMOO [33, 32] (the only exception being FIFO scheduling). However, the transformed service curves in the open-loop tandem are not strict but just min-plus service curves (see Section 3.2 on why strict service curves are generally not useful in the modelling of feedback systems).

Instead, we make use of recent results in [19] where a residual service curve ${\beta }_i^{\mathrm{res}}$ is calculated from a min-plus service curve ${\beta }_i$ as

where ${\overline{\alpha }}_i^c$ is the aggregate maximal arrival curve of all cross flows at node $i$. This is still a min-plus service curve (see also [7, Theorem 7.3]) and can be used to calculate a valid residual service curve for any scheduling policy. Yet, in general, it is partially negative and decreasing and thus not in ${ℱ}_0^{\uparrow }$. Therefore, we cannot apply Theorem 10 to compute performance bounds anymore. However, in [19] we find a replacement for Theorem 10 when a service curve can be partially negative, enabled by the assumption of a minimal arrival curve $\underset{¯}{\alpha }$ for the foi:

Here, the $z$-distance is defined as $z(\underset{¯}{\alpha },\xi )≔inf\{\tau \ge 0|\underset{¯}{\alpha }\otimes \xi (\tau )\ge 0\}$. Consequently, we can make use of network analysis algorithms like PMOO again, despite not having a strict service curve, also when scheduling is not just FIFO. This makes feedback systems in general an interesting application for the new results. In fact, in [19] feedback systems are an application example, yet only a very simple instance with just a single server and two competing flows is treated. The following numerical experiments use our new insights in much more complex feedback systems.

In the following, we have five flows $f_1,\mathrm{\dots },f_5$, where $f_1$ is the flow of interest. We also assume that $f_1$ consists of four sub-flows $f_1^1,\mathrm{\dots },f_1^4$ with different priorities, where $f_1^4$ has the highest priority and $f_1^1$ the lowest. Application-wise, we interpret the highest priority as absolutely time-critical, for instance, sensor data, while $f_1^1$ represents Best-Effort (BE) traffic.

In a first step, we derive transformed service curves $\stackrel{\curvearrowleft \phantom{1}}{{\beta }_1},\stackrel{\curvearrowleft \phantom{2}}{{\beta }_2},\stackrel{\curvearrowleft \phantom{3}}{{\beta }_3},\stackrel{\curvearrowleft \phantom{4}}{{\beta }_4}$ that turn the closed-loop system from Figure 11 into an open-loop system. To this end, the feedback constraints are evaluated in the reverse lexicographic order $F_6>F_5>F_4>F_3>F_2>F_1$. Thus,

with ${\phi }_6^{\prime }={({\beta }_4\otimes {\beta }_5\otimes {\phi }_6)}^{\ast }$,

with ${\phi }_5^{\prime }={({\beta }_3\otimes {\beta }_4\otimes {\phi }_5)}^{\ast }$,

with ${\phi }_3^{\prime }={({\beta }_2\otimes {\beta }_3\otimes {\beta }_4\otimes {\beta }_5\otimes {\phi }_3)}^{\ast }$ and ${\phi }_4^{\prime }={({\beta }_2\otimes {\beta }_3\otimes {\phi }_4)}^{\ast }$,

with ${\phi }_1^{\prime }={\left({⨂}_{j=1}^6{\beta }_j\otimes {\phi }_1\right)}^{\ast }$ and ${\phi }_2^{\prime }={({\beta }_1\otimes {\beta }_2\otimes {\beta }_3\otimes {\beta }_4\otimes {\phi }_2)}^{\ast }$.

This takes us to the open-loop network in Figure 12, where ${\beta }_1,\mathrm{\dots },{\beta }_4$ are replaced by their transformed service curves $\stackrel{\curvearrowleft \phantom{1}}{{\beta }_1},\mathrm{\dots },\stackrel{\curvearrowleft \phantom{4}}{{\beta }_4}$. We observe that there are no feedback constraints left in the open-loop system, but the respective feedback properties are effectively contained within the transformed service curves.

Next, we calculate the FIFO residual end-to-end service curve for our flow of interest in the open-loop system. This is done using the PMOO analysis following the principle to always concatenate as many nodes as possible before computing residual service curves [33, 32]. For instance, in our case we first compute the concatenation of node $4$ and $5$ by convoluting the respective service curves $\stackrel{\curvearrowleft \phantom{4}}{{\beta }_4}$ and ${\beta }_5$, and then calculate the residual service curve with respect to cross flow $f_4$. For the calculation of the residual service curves we apply the well-known FIFO result [7, Theorem 7.5]

where we choose $\theta =\frac{\sum b_2^i}{R}$. This choice for $\theta$ minimizes the length of the interval $I=[0,s]$ over which ${\beta }_{\mathrm{FIFO}}^{\theta }(t)=0$, $\forall t\in I$.

This choice for $\theta$ minimizes the latency (period for which it is 0) of the residual service curve under token-bucket arrival and rate-latency service curves [6].

For the FIFO analysis of $f_1$, we can now directly calculate performance bounds based on Theorem 10. For the SP analysis of the sub-flows of $f_1$, we use Equation (14) to calculate their respective residual service curves, taking into account sub-flows with higher priorities as crossflows. We note that, since we assume ${\beta }_i$ to be min-plus service curves, we cannot make use of the residual service curve calculation in [7, Theorem 7.6], as this requires ${\beta }_i$ to be a strict service curve. Rather, we use Theorem 19 to calculate the sub-flow specific delay bounds.

We point out that the residual service curves calculated using Equation (15) are always positive and non-decreasing, while the residual curves calculated with Equation (14) are partially negative and decreasing. This is also shown in Figure 13.

The parameters used in our experiments are given in Table 1. Here, ${\phi }_l=I_2$ means that each feedback constraint has a fixed size $u=2\mathrm{Mbit}$. Also note that the burst of the maximal arrival curve of the foi ${\overline{b}}_1$ is the sum of the bursts of its sub-flows $b_1^4,b_1^3,b_1^2$ and $b_1^1$, as it holds that the sum of token-bucket arrival curves is again a token-bucket arrival curve for the aggregate. All experiments are conducted using the network calculus library Nancy [39]. We examine two different factors: bottleneck utilization and burstiness of BE traffic $f_1^1$. First, we compare the delay bounds for the FIFO and SP analyses against the utilization of the bottleneck node $S_2$. The results are illustrated in Figure 14. We see that the delay bounds for the FIFO analysis lie between the SP bounds of $f_1^2$ and $f_1^3$. This exhibits the inherent issue of FIFO scheduling, not being able to protect time-critical traffic from BE. We remark that, except for $f_1^4$, all SP delay bounds were calculated using the $z$-value of Theorem 19, explaining the constant behavior of the delay bounds for some periods as the $z$-distance does not react directly to a decreasing bottleneck capacity. On a similar note, due to the residual service curve shapes as shown in Figure 13, we see several utilizations where the bounds are increasing sharply. This stems from the fact that changing the utilization also affects the creation and periods of these functions, resulting in fluctuations of the bounds.

Next, we explore the effects of increasing the burst size of the BE traffic $f_1^1$. We use the default parameter set from Table 1, but let $b_1^1$ run from $3\mathrm{Mbit}$ to $20\mathrm{Mbit}$, instead. The results are illustrated in Figure 15. This scenario reinforces what we discussed in the previous paragraph. As the FIFO analysis is an aggregate analysis, increasing the burst size of a lower priority class also increases the delay bounds for more time-critical traffic. For the SP analysis, we do not observe this behavior other than for flow $f_1^1$, as SP isolates the other flows from the “bad behavior” of $f_1^1$ and we can still calculate good per-flow delay bounds.

We have seen how to deal with existing feedback mechanisms in a complex feedback system. However, depending on the application, it may not be desirable to have adverse effects from feedback control on the performance bounds of the system, at all. From a system design perspective, we can try to achieve this by providing enough resources, such as buffer space, for instance. But how do we determine the required resources that are needed in the system? We briefly restate the previously presented result from Section 3.1. For a feedback curve $\phi =I_u$, and for a single feedback constraint, we obtain the optimal $u$ such that $\stackrel{\curvearrowleft }{𝛽}=\beta$ as

Indeed, even with more complex feedback structures, Equation (16) can still be applied. To that end, we make use of the same (lexicographic) order of feedback resolutions as discussed in Section 4.3 and proceed as follows: Assuming we have $k$ feedback loops in the network, we calculate the optimal window size $u_k^{\mathrm{opt}}$ for feedback loop $F_k=(i_k,j_k,{\phi }_k)$ and transform this closed loop into an open loop system with ${\stackrel{\curvearrowleft \phantom{i}}{{\beta }_i}}_k={\beta }_{i_k}$. Next, we can apply Equation (16) again to obtain $u_{k-1}^{\mathrm{opt}}$ and transform $F_{k-1}$. We proceed in this manner for all remaining feedback loops until we have obtained a transformed service curve for all existing closed-loop feedback constraints. Essentially, since we only consider a single feedback constraint at a time, we can iteratively apply Equation (16). This procedure results in a network that has no adverse effects on performance bounds from feedback constraints. Indeed, we can interpret this as the minimal cost of the system (in terms of resource requirements) at wich we have no adverse effects of the feedback, and thus view this as optimal feedback. We can further calculate performance bounds for the system and confirm whether the system still meets existing timing requirements.

Applying this procedure to the example network, we obtain the optimal $u_l^{\mathrm{opt}}$ as $u_1^{\mathrm{opt}}=6,u_2^{\mathrm{opt}}=u_3^{\mathrm{opt}}=4,u_4^{\mathrm{opt}}=u_5^{\mathrm{opt}}=u_6^{\mathrm{opt}}=2$. Comparing the optimal $u_l$ values to the ones we (arbitrarily) picked in Section 5.1, we realize that the feedback constraints spanning more nodes ($F_1,F_2,F_3$) are under-provisioned, while $F_4$ to $F_6$ were already given their optimal values.

While calculating the optimal feedback is possible, network design usually has inherent restrictions on the budget that is available to dimension buffers. As a consequence, a required resource budget ${\eta }_{\mathrm{opt}}=\sum u_l^{\mathrm{opt}}$ is usually higher than an available resource budget ${\eta }_a$. In the following, we study different strategies for resource allocations for the feedback constraints and compare them to each other and the optimal allocation from the previous subsection with respect to delay bounds.