Schedulability analysis of Ethernet Audio Video Bridging networks with scheduled traffic support

In all real-time application domains, timeliness guarantees are required. In fact, it is essential to provide an analytical method to achieve the worst-case latency of the messages in the network. Several timing analysis approaches for messages in AVB networks were presented, e.g., Diemer et al. (2012) and Bordoloi et al. (2014), however, none of them can support response time computation of messages in the presence of ST messages. In this paper, we identify the elements which influence the delay of messages when ST messages cross through the network. Then, we present a response time analysis for the different classes of traffic in the AVB ST. We follow the same response time analysis method as presented in Bordoloi et al. (2014). However, our analysis has the following dissimilarities compared to the analyses presented in Diemer et al. (2012) and Bordoloi et al. (2014): (i) we consider the effect of ST messages on the analysis, and (ii) we discuss the effect of queuing jitter from higher priority messages by showing potential optimism when jitter is neglected in the analysis, using a counterexample.

Finally, we conduct experiments in two types of application domains, automotive and automation networks. The architecture and traffic of the networks are inspired by close-to-industry case studies. In particular, for the automotive case study we referred to an architecture designed by BMW group (Lim et al. 2011), while for the automation case study we adopted the maximum number of switches that the standard guarantees. Then, we compute the response time of messages using the timing analysis presented in this paper, considering the bandwidth over-reservation. Also, we simulate the networks using OMNeT++ to compare the message response times with the computed ones, in order to show the effectiveness of the presented response time analysis.

The rest of the paper is organized as follows. The next section discusses related works on Ethernet AVB. Then, Sect. 3 presents the Ethernet AVB and AVB ST. Section 4 provides the system model. Section 5 recalls the previous response time analysis, while Sect. 6 presents the response time analysis for the AVB ST networks. Section 7 discusses the limitation of the analysis when allocating the bandwidth based on the AVB standard, and presents a solution to overcome it. The experiments on automation and automotive case studies are conducted in Sect. 8. Finally, Sect. 9 concludes the paper.

Recently, the real-time performance of IEEE AVB has been investigated extensively in multiple application domains, namely automotive, aeronautics, and industrial automation. For automotive networks, the work in Lo Bello (2011) and Tuohy et al. (2015) indicate AVB as one of the possible candidates for real-time communication domain. Moreover, the AVB suitability for supporting traffic flows of both Advanced Driver Assistance Systems (ADAS) and multimedia/infotainment systems was proven in Steinbach et al. (2012), Alderisi et al. (2012, 2012). In Lim and Volker (2011) the capability of AVB to be used as an in-car backbone network for inter domain communication is discussed. As far as the industrial automation communication is concerned, the Ethernet AVB ability to deal with real-time traffic requirements typically found in industrial automation is addressed in Imtiaz et al. (2011) and Jasperneite et al. (2009). In Jasperneite et al. (2009) the latency of forwarding the traffic is pointed out as one of the main challenges. In fact, due to the shaper in IEEE 802.1Q, a real-time message might be delayed in every bridge resulting in a poor performance. Therefore, further improvements are foreseen, including (i) shortening the non-real-time messages that interfere with real-time messages, (ii) allowing only real-time messages or (iii) providing mechanisms to avoid the mentioned interference. Focusing on the avionics application, AVB performance is discussed in Land and Elliott (2011) and Heidinger et al. (2012). In Heidinger et al. (2012) the reliability of AVB was evaluated and results showed that AVB solutions may be applicable to applications belonging to lower safety classes that have less demanding requirements on reliability. This is mainly due to the complexity of dynamic bandwidth reservation in AVB and failure probability of devices evaluated in Heidinger et al. (2012). In Schneele and Geyer (2012), the AVB is compared to the AFDX standard and the outcome is that further work is needed for making AVB suitable for the aeronautic industry requirements. In order to tackle the aforementioned improvements several kinds of traffic shapers were analyzed in Thangamuthu et al. (2015) and the Time-Aware Shaper (TAS) proved to be the one that can offer the lowest latency along with good jitter performance, albeit with an increased configuration cost for the switches. TAS prevents interference on the scheduled traffic, thus the traffic can be delivered faster. The only delay that the scheduled traffic suffers from is the forwarding latency crossing the switches.

Approaches to reduce latency for high priority traffic in the AVB networks, such as packet preemption and fragmentation, are discussed in Imtiaz et al. (2012). Moreover, TAS or time windows were proposed in Pannel (2012) and Cummings (2012) for isolating class A streams from the interference due to other traffic types. However, these approaches map all time-sensitive flows on the same class (class A) irrespective of their heterogeneous sizes and time constraints. Such a choice is not beneficial to low latency small-size traffic, which should not be handled in the same queue as large messages in AVB. For this reason, the work in Alderisi et al. (2013) proposed to add a separate class on top of the AVB Stream Reservation Classes A and B to introduce support for ST traffic, while maintaining the other traffic classes provided by the AVB standard. The work adopted TAS to enforce temporal isolation between ST and other classes of traffic. It also proved that ST traffic achieves both low and predictable latency, without significantly affecting the SR traffic. In this paper, we focus on the proposal in Alderisi et al. (2013), named AVB ST network, as it introduces relatively high performance in transmission of time-sensitive traffic. The details of the AVB ST are discussed in Sect. 3.2.

A number of timing analysis techniques were proposed for the Ethernet AVB networks, such as Imtiaz et al. (2009), Lee et al. (2006) and De Azua and Boyer (2014), each one using different approaches. For instance, the analysis presented in De Azua and Boyer (2014) applies the Network Calculus framework (Leboudec and Thiran 2001), while the one presented in Imtiaz et al. (2009) adopts delay computation. However, these analysis techniques are restricted to the computation of worst-case response time per-class, without distinguishing the individual messages’ response times. It should be noted that in many industrial systems a large number of messages are transmitted. For instance, in a modern truck 6000 messages are exchanged across several networks (Keynote 2013). Therefore, the delays of each individual message should be bounded, but this is not possible using the mentioned analysis approaches. Another analysis framework for the Ethernet AVB is presented in Reimann et al. (2013) and is based on Modular Performance Analysis (MPA) (Wandeler et al. 2006). In the presented analysis the interference from higher priority messages is not formally considered, i.e., multiple activations of higher priority messages are not taken into account.

A formal timing analysis is given in Diemer et al. (2012), where the response time of each individual message is computed in an Ethernet AVB architecture consisting of multiple switches. The recent work presented in Bordoloi et al. (2014) showed that the analysis in Diemer et al. (2012) considers only one blocking factor that results from lower priority messages, which is not the case in the Ethernet AVB, due to the traffic shaper. Thus, a new response time analysis is developed in Bordoloi et al. (2014). However, the proposed analysis is still limited to the constrained deadline traffic model, and a single-switch architecture. In this paper, we extend the response time analysis presented in Bordoloi et al. (2014) in two directions: (i) computing the response time of messages in Ethernet AVB when ST traffic is transmitted through the network, and (ii) considering the effect of queuing jitter from higher priority messages in multi-hop architectures.

The IEEE AVB standard consists of a set of technical standards. For our purposes here we mention the IEEE 802.1AS (2011) and the IEEE 802.1Q (2014). The IEEE 802.1AS Time Synchronization protocol is a variation of the IEEE 1588 (2008) standard, which provides precise time synchronization of the network nodes to a reference time with an accuracy better than 1 \(\upmu \)s. The IEEE 802.1Q provides Stream Reservation Protocol (SRP) that allows for reservation of resources (i.e., buffers and queues) within the switches (called bridges in the AVB terminology) along the path between the talker (i.e., the stream source node) and the listener (i.e., the stream final destination node). Moreover, the IEEE 802.1Q provides Queuing and Forwarding mechanism for AV Bridges to split time-critical and non-time-critical traffic into different traffic classes and applies the CBS algorithm that prevents traffic bursts by exploiting traffic shaping at the output ports of bridges and end nodes. The AVB standard guarantees a fixed maximum latency for up to seven hops within the network for two different Stream Reservation (SR) classes, i.e., 2 ms for class A and 50 ms for Class B. According to the CBS algorithm, each SR traffic class has an associate credit parameter, whose value changes within two limits, called loCredit and hiCredit, respectively. Pending messages in the queues may be transmitted only when their associated credit is zero or higher. During the message transmission the credit decreases at the sendSlope rate defined for the class. The credit is replenished at the constant rate idleSlope defined for the class when (i) the messages of that class are waiting for the transmission or (ii) when no more messages of the class are waiting, but credit is negative. If the credit is greater than zero and no more messages of the corresponding traffic class are waiting, the credit is immediately reset to zero. Figure 1 illustrates the operation of the CBS algorithm for classes A and B. At the beginning \(m_2\) is being transmitted, hence its credit (class B) decreases. At time \(t_1\) message \(m_1\) is ready in the queue of class A, thus its credit starts to increase. When at time \(t_3\) the transmission of \(m_2\) finishes, the transmission of \(m_1\) is initiated, as the credit for class A is positive. Moreover, credit of class B starts to increase as there is \(m_3\) pending for transmission. At time \(t_4\) transmission of \(m_1\) finishes and finally \(m_3\) is started for transmission. At time \(t_5\) since there is no pending traffic for class A, the credit immediately becomes zero.

The AVB ST approach presented in Alderisi et al. (2013) is summarised in Sect. 3.2 that shows a promising solution towards the support of ST traffic over AVB networks. The analysis and results in this paper are based on the AVB ST design presented in Alderisi et al. (2013).

The AVB ST approach introduces a separate traffic class for scheduled traffic, called the Scheduled Traffic Class (ST Class), on top of the AVB SR Classes A and B. ST frames get the highest priority TAG according to the IEEE 802.1Q standard, as scheduled traffic includes time-sensitive high-priority flows (e.g., control traffic) that deserve the best service. For this reason, the ST class not only has a separate queue, but also does not undergo credit-based shaping, this way avoiding the latency increase that traffic shaping introduces. Conversely, SR class A and B take the second and the third highest priority, respectively, and undergo CBS shaper. Finally, best-effort traffic is handled by strict priority (as in the IEEE 802.1Q standard).

As ST flows are periodic, with fixed and a priori known period and frame size, they can be scheduled offline. Suitable scheduling techniques, e.g., offset scheduling (Palencia and González Harbour 1998), can be adopted at the network configuration time to ensure, by design, the absence of collisions between ST frames in the whole network (i.e., either in the end stations or in the bridges). The AVB ST approach requires that every node and every switch has to be aware of the right time for transmitting its ST traffic, therefore, synchronization is provided by the IEEE 802.1AS standard.

The AVB ST approach is based on two fundamental concepts, i.e., TAS and ST_Window. TAS is a mechanism that, in order to prevent any interference on ST frames from other traffic classes, inhibits the transmission of non-ST traffic that would delay the upcoming ST one. In other words, in AVB ST, the TAS temporally isolates the transmission of ST frames from non-ST frames, thus enabling time-sensitive frames to be transmitted from a bridge port without any interference from other traffic types. In the AVB ST approach the messages belonging to the SR Classes undergo both TAS and credit shaping, while best-effort messages go through TAS only, in compliance with the AVB standard. The traffic shaping in the AVB ST design presented in Alderisi et al. (2013) is shown in Fig. 2.

According to the AVB ST design in Alderisi et al. (2013), the CBS and TAS operate as follows. When there is no ST transmission, the CBS operates as in Sect. 3.1.When there are ST messages to transmit, the TAS prevents the other classes far in advance to be certain that the ST transmission is fully protected. This protection window is the maximum transmission time of the registered SR classes in the worst-case, which is called a guard band. During the guard band and ST message transmission, the credit for SR classes that have pending messages increases at the rate of the relevant idleSlope. If there are no pending messages, the credit becomes immediately zero. Fig. 3 depicts an example of AVB ST transmission. An ST message (\(m_{\textit{ST}}\)) is scheduled for transmission at time \(t_3\). Although \(m_2\) from class A can be transmitted at time \(t_1\) as the credit is zero, the TAS prevents it as it would interfere with \(m_{\textit{ST}}\) transmission. Finally, \(m_2\) is sent after \(m_{\textit{ST}}\).

It should be noted that there is an intelligent way to assign a guard band. In fact, if the implementation determines which messages are waiting in the queue, for the guard band it is sufficient to use the maximum size of those messages instead of the maximum of all messages in that class.

The synchronization offered by the IEEE 802.1AS (2011) makes AVB bridges time-aware nodes (i.e., nodes provided with network timing information). Consequently, to implement TASs, only a suitable mechanism to allow/inhibit transmissions in a given time window and a way to configure the TAS based on the information provided by a Management Information Base (MIB) are needed.

The second fundamental concept for AVB ST is the ST_Window of each ST message. Such a window is defined as the time window, at the receiver side, within which the ST frame has to be received. In fact, as in the AVB ST approach ST frames are transmitted at known time instants and do not experience interference from the same class or from other traffic classes, the reception instant for any ST message can be calculated. The calculation has to consider the synchronization error between the nodes. The synchronization error is calculated using the drift of each node.

The results of comparative simulations of AVB ST and AVB in Alderisi et al. (2013) show a positive outcome for AVB ST, as ST traffic obtained low and predictable latency values, without significantly affecting SR traffic. The reason for this result is the combination of three features that are very beneficial for the ST class, namely, the offset-based scheduling, the temporal isolation provided by TAS and the absence of CBS shaping for the ST class.

The standardization process of the IEEE TSN is in progress and several projects are ongoing. Recently, an amendment of the IEEE 802.1Q, called IEEE 802.1Qbv-2015  (2015), was released. The IEEE 802.1Qbv introduces the support for scheduled traffic. To achieve this goal, a transmission gate is associated with each queue and the state of the transmission gate determines whether or not queued frames can be selected for transmission. For a given queue the gate can be in one of two states, i.e., open or closed. According to the transmission selection algorithm, a frame waiting in a traffic class queue cannot be transmitted if the transmission gate relevant to the queue is in the closed state or if there is not enough time for transmitting the entire frame before the next gate-close event. The gate operations are contained in a list and are cyclically repeated with a period called OperCycleTime. Two consecutive gate operations (i.e., opening/closing of one or multiple gates) are spaced by an interval called TimeInterval. Such an interval is equal for all the operations contained in the list. The list of operations is configured to create the protected window (PW) for the queues in which the scheduled traffic is transmitted with no interference. This operational approach foresees a unique PW cyclically repeated for each scheduled traffic queue large enough to accommodate the transmission of all the ST messages within a cycle. This results in a non-optimized scheduling in the case of multiple ST messages with different lengths and periods leading to the consequent waste of bandwidth. In fact, the PW should be sized so as to accommodate the transmission of all the ST frames handled by a node within a cycle, regardless of whether some ST messages have a larger period and they are not transmitted in each cycle. Note that the IEEE 802.1Qbv standard does not exclude multiple PWs for one queue. However, scheduling multiple protected windows for each message may result in a very complex and difficult implementation. The main differences between the IEEE 802.1Qbv standard and AVB ST are summarized as follows.

The AVB switches are considered to be full-duplex, i.e., the input and output of a switch port are isolated. Thus, the receiving message does not delay the transmission of a message. In this paper, we define a link as a connection between a node and a switch, as well as a connection between two switches. The link is denoted by l. Also, the switch has a fabric latency due to the hardware configuration for relaying messages, which is denoted by \(\epsilon \). This delay varies in different switches and usually is accounted for the time that the switch takes to process a received message and to insert it into the output port queue. The link delay due to wire and its physical characteristics is assumed to be very small and negligible.

Ethernet AVB uses a credit-based shaping algorithm to regulate the traffic transmission for two traffic classes, A and B, where class A has higher priority than class B. Assuming traffic class X, the replenishment rate (idleSlope) of the credit on link l is denoted by \(\alpha ^+_{X,l}\). Moreover, the credit is consumed when there is a transmission on a link, and the consumption rate (sendSlope) is specified by \(\alpha ^-_{X,l}\). The non-real-time traffic, known as best effort (BE) class, does not undergo the traffic shaper. Moreover, the total network bandwidth is denoted by R. It should also be noted that in the response time analysis the latency due to unprecise clock synchronization among the nodes is neglected.

For the traffic model, we use the real-time periodic model. A set of messages \(\Gamma \), composed by N messages, is characterized as follows:In this model, \(C_i\) represents the transmission time of \(m_i\), that is obtained from the message size based on the total network bandwidth (R). In our model, a message is not larger than the maximum possible Ethernet size, hence message fragmentation is not required. Also, \(T_i\) and \(D_i\) denote the period and relative deadline of the message, respectively. In this paper, we consider the constrained deadline model, i.e., \(D_i \le T_i\). A message belongs to a traffic class based on its priority. Several messages in the set may share a priority level and be assigned to the same traffic class. In this case, the FIFO policy applies to them in the queues of the switch. Therefore, \(P_i\) represents the class of \(m_i\), e.g., \(P_i = \textit{class}\;A\). In the analysis, \(\textit{lp}(m_i)\), \(sp(m_i)\) and \(hp(m_i)\) are the sets of the messages with lower, the same and higher priority than that of \(m_i\), respectively. Moreover, \(F_i\) represents the message length, which can be derived as \(F_i = C_i \cdot R\). A message traversing several switches may get variation in delay, which is called queuing jitter and denoted by \(J_i\).

A message may traverse multiple switches to arrive to its destination node. A set of links that \(m_i\) passes through is defined by \(\mathcal {L}_i\), where the number of links in the set is defined by \(n_i = |\mathcal {L}_i|\). Each member of the set is a tuple \(l = \langle x, y \rangle \), that represents a link l between the nodes/switches x and y. Note that the sequence in the tuple shows the direction of the message transmission from x to y. In this analysis, we restricted the model to unicast streams, i.e., only one destination per message is assumed. The multicast and broadcast streams can be handled by transforming them into multiple unicast streams, however we leave that case as out of the scope of this paper for the sake of clarity. The response time of \(m_i\) is the temporal interval between the time at which the message is inserted in the queue of its source node (i.e., the time instant when it becomes ready for transmission), and the time at which the message is delivered to its destination node. The response time is specified by \(\textit{RT}_i\). Moreover, the response time of \(m_i\) when it is transmitted from a node/switch to another node/switch through link l in a multi-hop architecture is denoted by \(\textit{RT}^l_i\). Table 1 summarizes the notations that are used in this paper.

In Ethernet AVB, class A messages have the highest priority, hence there is no interference from higher priority messages for this class. On the other hand, there might be blocking by lower priority messages, e.g., a blocking by class B or BE traffic. As there are only two traffic classes, several messages may be assigned to the same class, therefore a message may be delayed by the messages with the same priority in the FIFO queue. Finally, as the message transmission is controlled by the traffic shaper, even if the message is ready for transmission it may be blocked due to a negative credit. To sum up, three different elements have to be considered in the worst-case response time of a message: (i) blocking by lower priority messages, (ii) interference from the same priority messages in the FIFO queue, and (iii) traffic shaping.

A message from class B is not only blocked by lower priority messages (i.e., by the BE traffic), but it can also suffer from the interference of the higher priority messages (i.e., by the traffic in class A). Therefore, besides the three elements mentioned in the class A analysis, the interference from higher priority messages should be also considered. Although we adopt the constrained deadline model, considering one instance of the message under analysis is not sufficient. Instead, the response time of several instances of the message during a busy period (Lehoczky 1990) must be calculated and the maximum among them is the worst-case response time. The busy period is the maximum time interval during which the resource is busy. Note that in Ethernet AVB the resource is busy either when there is an ongoing transmission on the link or when the queue is not empty, but the transmission is prevented due to a negative credit. The reason behind the need for considering multiple instances is the non-preemptive nature of the transmission, which is thoroughly discussed in the Controller Area Network (CAN) response time analysis (Davis et al. 2007). Under high network utilization, a message may delay subsequent transmission of the higher priority messages. Thus, the higher priority interference may be pushed through into the next period of the messages, causing larger response time in the next instance. Let us consider an example in Fig. 6, where we are interested in computing the response time for \(m_3\). In this example, \(m_1\) and \(m_2\) are higher priority messages than \(m_3\). Moreover, \(m_1\) has period of 4 time units, while the period of the other messages is 6 time units. The transmission time of \(m_1\) and \(m_3\) is 2 time units and for \(m_2\) is 1 time unit. The first instance of \(m_3\) is completely sent at time 5, hence its worst-case response time is 5 time units if we consider the first instance only. However, \(m_1\) is ready at time 4, but it cannot preempt \(m_3\) due to the non-preemptive nature of the transmission. Thus, its transmission starts at time 5 and its third transmission starts at time 8, thus pushing the transmission of \(m_3\). Then, transmission of the second instance of \(m_3\) starts at time 10 and completes at time 12, thus making the worst-case response time for the first instance equal to 6 time units instead of 5. Therefore, in the calculation of the worst-case response time, several instances should be examined.

Given the \(q^{th}\) instance of message \(m_i\) in the busy period, we compute the queuing delay \(w_i(q)\), which is the longest time from the start of the busy period until the beginning of the transmission of the \(q^{th}\) instance, as shown in Eq. (7). The equation is a recursive function that starts with an initial value for \(w_i(q)\) and terminates when the previous value of \(w_i(q)\) equals the new value derived by the equation.The first term in Eq. (7) is the blocking by the lower priority messages. The second term is the transmission time of the message itself in the previous \(q-1\) instances. The third term is the interference from the same priority messages in the FIFO queue, excluding the message under analysis. The last term in the calculation is the interference from higher priority messages. Note that the inflation factor, as discussed before, is applied on the same priority messages including the message itself. Finally, the response time of \(m_i\), which is the maximum response time among the examined instances, is computed in Eq. (8). The first term of Eq. (8) is the queuing delay computed iteratively in Eq. (7), the second term is the number of periods for message \(m_i\) that has passed during the busy period, and the last term is the transmission time of the message itself.The range of q for which the response time must be calculated is \([1, q_{\textit{max}}]\), where \(q_{\textit{max}}\) is the smallest positive integer q derived in Eq. (9). The left side of Eq. (9) is the length of the busy period. Therefore, by dividing the busy period length to the period of the message \(T_i\) (in the right side of Eq. 9), the maximum number of instances during the busy period is derived. The length of busy period is calculated by adding the blocking from lower priority messages, the interference from same and higher priority messages (i.e., the interference that makes the resource busy during the busy period).

In the approach presented in Alderisi et al. (2013) the messages in the queues associated to the SR classes undergo both TAS and CBS, while the BE messages go through TAS only. According to the TAS mechanism, any non-ST message that is queued and is ready for transmission has to wait not only for the duration of an ST message transmission, but also for an additional time, called a guard band. The guard band is enforced by TAS to avoid the transmission of non-ST traffic that would delay the next ST message. Therefore, when calculating the response time for messages in class A, not only the interference from ST messages should be taken into account, but also the guard band should be considered. For the response time analysis of messages in class A four elements are required. These elements include: (i) interference from higher priority messages (i.e., from ST messages and their guard band), (ii) blocking by lower priority messages, (iii) interference from the same priority messages in the FIFO queue, and (iv) traffic shaper effect.

Similarly to the analysis for class A traffic, blocking times due to lower priority messages and interference from the same and higher priority messages should be considered in the worst-case response time calculation for class B traffic. Following the same proof made in the previous analysis, considering one blocking by the lower priority messages is sufficient if the same priority messages are inflated by \((1 + \frac{\alpha ^-_B}{\alpha ^+_B})\). Moreover, the interference from higher priority messages does not only stem from ST messages, but also from messages in class A. In this analysis, we must consider multiple instances of the message under analysis. Therefore, the queuing delay \(w_i^l(q)\) in link l is calculated in Eq. (15). The first term in Eq. (15) is the blocking by lower priority messages, while the second term is the transmission of \(m_i\) in previous \(q-1\) instances. Again, the transmission time of \(m_i\) is inflated only when there is no same priority messages in the set. The third term is the interference from the same priority messages. Also, the fourth term is the interference from higher priority messages, consisting of classes A and ST messages. Finally, the last term is the interference of virtual messages to consider the guard band in the analysis. Note that the queuing jitter of traffic class A (not by ST) on link l is denoted by \(J_j^l\) and described in the next subsection (Sect. 6.5).The maximum response time among \(q_{\textit{max}}\) instances of the message is the worst-case response time, as calculated in Eq. (16). Note that the switch fabric latency (\(\epsilon \)) is also included in the analysis. Moreover, the same scenario as in class A occurs for the transmission time of the message under analysis to account for the negative credit.The response time must be examined for instances within a range \([1, q_{\textit{max}}]\), where \(q_{\textit{max}}\) is derived as the smallest positive integer value from Eq. (17). Similar to Eq. (9), the left side of Eq. (17) is the length of the busy period, hence dividing that by \(T_i\) gives the maximum number of instances that have passed during the busy period. To compute the busy period length the interference and blocking should be added to the transmission time of the message.

The ST messages are scheduled offline and TAS prevents any interference from lower priority messages. Therefore, the transmission delay of ST messages is equal to their transmission time and the switch fabric latency, which is shown in Eq. (18). Note that the switch fabric latency in the last link should be omitted as the last link is connected to the destination node, not a switch.

In a multi-switch AVB architecture, messages are buffered in the queues of each switch through their route. Thus, the worst-case response time of a message traversing multiple switches is the sum of the per-hop response times, as shown in Eq. (19). Note that the wire latency is neglected in this calculation, whereas the switch fabric latency for each hop is already considered in each link. This means that as \(\epsilon \) was considered in each link, it is not needed in Eq. (19). Eq. (19) is used for classes A, B and ST.

The response time analysis given in Bordoloi et al. (2014) is presented for a single-switch network without considering the traffic shaper of the nodes. Therefore, messages arrive to the switch at every period without variation in their delays. Thus, the queuing jitter due to crossing switches does not appear. The response time analysis presented in Diemer et al. (2012) covers multi-hop architecture, however the queuing jitter is not considered. Here we show using a counterexample that if we do not consider the queuing jitter of a message due to passing through switches, the analysis can give an optimistic result. In AVB ST the queuing jitter of class A can affect the response time of message in class B. However, the ST traffic is scheduled offline without interference from other traffic classes. Therefore, they do not have queuing jitter. In this section, we discuss the effect of queuing jitter from class A on the class B analysis.

Assume a network with 3 messages, from classes A, B and BE, for the same destination. The parameters of the messages are given in Table 2 (values refer to time units). The idleSlope (\(\alpha ^+_A\)) and sendSlope (\(\alpha ^-_A\)) for class A are 0.4 and 0.6, respectively, while the idleSlope (\(\alpha ^+_B\)) and sendSlope (\(\alpha ^-_B\)) for class B are both equal to 0.5. In this example we assumed \(\epsilon = 0\).

A possible scheduling trace with jitter is shown in Fig. 9. In this scenario, we assume that \(m_A\) is arrived with a jitter of 4 time units, and \(m_{BE}\) started its transmission slightly before that, as the credit for \(m_B\) was negative. According to the figure the response time of \(m_B\) is 10 time units. However, when the response time of \(m_B\) is calculated using the analysis presented in this paper, without considering jitter, the response time becomes 8 time units as shown in Eq. (21), that is less than 10 time units shown in the figure. This is in contrast with the scheduling scenario shown in Fig. 9. In Eq. (21), \(w_B\) and \(\textit{RT}_B\) are calculated using Eqs. (15) and (16), respectively. Note that the maximum number of instances calculated in Eq. (17) is 1 in this example, i.e., \(w_B\) and \(\textit{RT}_B\) are only calculated for \(q = 1\). Moreover, the inflation factor for the message under analysis \(m_B\) is not considered as there is no interference from the same priority as \(m_B\).

Now, when we consider the jitter of \(m_A\) in the calculation (according to Eq. 15) the response time of message \(m_B\) becomes 10 (see Eq. 21), that is just equal to the depicted one in the figure. Again, in this calculation \(q = 1\) from Eq. (17).In this work, we apply jitter similarly to the other response time analysis for switched Ethernet networks, e.g., Martin and Minet (2006), by adding it to the calculation of busy period. In order to compute the queuing jitter of a message in class A, we need to find the difference between the worst-case and the best-case response times of the message from its source node to the link that we are calculating the response time of \(m_i\) in class B. This means that the response time for class A in all hops should be computed before the response time for class B. Equation (22) derives the queuing jitter of \(m_j\) from class A in link l.Note that the switch fabric latency (\(\epsilon \)) is considered for both best- and worst-case response times, however it is subtracted in Eq. (22).

Here, we demonstrate the limitation in two different cases. First, we focus on the effect of lower priority blocking on the bandwidth reservation. Second, we show that even in a network without lower priority messages, the analysis may provide schedulable results only when the periods of all messages are equal. Otherwise, when the bandwidth is reserved according to the standard, the system is not schedulable in any setting.

Through the previous section, we demonstrated that the system is not schedulable in most of the cases. Although, we show the limitation for class A traffic, the problem is inherited in other classes, as well as in AVB ST networks. In order to be able to use the response time analysis an over-reservation of the reserved bandwidth is essential. On the other hand, over-reservation may cause bandwidth waste due to reservation of the bandwidth being made unnecessarily high. Therefore, we propose a solution to find the minimum required over-reservation for classes A and B. We propose the solution in the context of the AVB ST networks, as a general form of the analysis for AVB. For the solution we define a new idleSlope for the traffic shaper of class X on link l of the network as \(\beta ^+_{X, l}\). Moreover, we define \(\beta ^+_{X,l,i}\) as the idleSlope for \(m_i\) of class X on link l. Intuitively, by increasing \(\beta ^+_{X, l}\) the response time becomes smaller, as the reserved bandwidth is larger. The intention of the solution is to find the minimum \(\beta ^+_{X,l,i}\) such that \(m_i\) meets its deadline. Then, \(\beta ^+_{X,l}\) is derived in Eq. (42) such that the whole set of messages in class X meet their deadlines, hence the system becomes schedulable.In addition, according to the standard (IEEE 2014), a maximum reservable bandwidth is defined for each class of traffic, for which a reservation cannot be made larger. Therefore, the over-reservation is limited to the maximum reservable bandwidth. Assuming f as the maximum reservable portion of the bandwidth, the maximum idleSlope for traffic class X (\(\beta ^X_{max, l}\)) is calculated in Eq. (43).Therefore, the calculated \(\beta ^+_{X, l}\) is valid if it is smaller or equal to \(\beta ^X_{max, l}\), otherwise the system cannot be schedulable with any over-reservation with the analysis presented in this paper. It should be noted that the over-reservation is derived based on the response time analysis presented in this paper. Therefore, the over-reservation is directly affected by the level of pessimism in the analysis. Moreover, when there is only one message in a class crossing a link, there is no need for over-reservation of bandwidth for that class in that link. The reason is that the idleSlope does not appear in the analysis when the same priority set is zero, i.e., \(sp(m_i) = \emptyset \). This can be seen in Eq. (14) for class A and in Eq. (16) for class B. Therefore, it is important to mention that the solution presented in this section applies only to the links crossed by traffic classes that have more than one message, i.e., \(sp(m_i) \ne 0\).

To make the system schedulable, the response time in its worst-case should be less or equal to the deadline of the message. However, as the response time is computed for one link, it should meet the deadline defined for that link, i.e., \(\textit{RT}_i^l \le D_i^l\). The sum of the deadlines for the links in the route of the message is \(D_i\), i.e., \(\sum _{l = 1\ldots n_i} D_i^l = D_i\). Defining the deadline of a message for each link can be done in several ways. The simple solution is to divide \(D_i\) equally among the number of links \(n_i\). However, a smarter solution is to divide the deadline proportional to the load on the links. Decomposition of the deadline has been studied in the real-time community, e.g., Chatterjee and Strosnider (1995) and Kao and Garcia-Molina (1993). In this paper, we do not focus on optimizing the results based on deadlines decomposition and we keep it as a future work. For the experiments in this paper, the end-to-end deadlines are divided proportionaly to the load on the links. The formulation is discussed in Sect. 8.

Algorithm 1 can be also used to find the over-reservation of idleSlope in the AVB networks. The only change is to assume the set of ST messages is zero in all calculations, i.e., \(\{ST class\} = \emptyset \), as the presented analysis is the general form for AVB analysis.

In this experiment we show the effect of accumulating delay over multiple hops on the bandwidth over-reservation. For this evaluation we consider a network with six switches, as illustrated in Fig. 11.

The total bandwidth capacity of the network is 100 Mbps, where 40 Mbps is set for each class of the SR traffic as the maximum reservable bandwidth. We assumed four messages, two from class A and two from class B. All messages have 500bytes payload with 2000 \(\upmu \)s period. The source of all four messages is N1, and we change their destination from N2 to N7, i.e., the number of hops that the messages are crossing is changing from one to six switches. We computed the idleSlope of class A and B based on the standard (i.e., \(\alpha ^+_A\) and \(\alpha ^+_B\)) in the destination link. For example, in case of crossing the switch 1, we computed the idleSlopes for link L2 which is the messages’ destination to node N2 (see Fig. 11). In addition, we calculated the new idleSlopes (i.e., \(\beta ^+_A\) and \(\beta ^+_B\)) based on the presented solution in this paper. The idleSlopes are illustrated in Fig. 12. As it can be seen in the Figure, the idleSlopes based on the standard are constant and equal (2.56 Mbps) by increasing the number of hops. This is because the standard for reserving bandwidth does not consider the queuing jitter from crossing previous switches. In contrast, the new idleSlopes increase with the number of hops. This means that the messages will get larger delay after crossing several switches, hence the reserved bandwidth should be higher to make the system schedulable. In this experiment higher bandwidth for class B is required, as it has higher priority interference, unlike class A.

In order to show the effect of the message parameters on the over-reservation, we run two experiments. In the first experiment, we fixed the value of payload for messages to 300 bytes and we changed the period of messages from 1600 to 3000 \(\upmu \)s. The new idleSlopes in every hop to the destination link for both classes A and B are presented in Fig. 13. In the second experiment, we fixed the value of periods to 2500 \(\upmu \)s and we increased the payload for all messages from 100 to 500 bytes. The idleSlopes for the second experiment are illustrated in Fig. 14. In general, increasing the period of messages or decreasing the payload of messages, the idleSlope decreases due to the decrease in the messages’ utilization. However, the trend in Figs. 13 and 14 shows that the messages in class B are affected more than messages in class A. This is indeed due to the interference from higher priority messages on class B.

In this case study, we assumed an architecture consisting of six switches connected in a line topology. The architecture is depicted in Fig. 15. In this example, there are eight nodes, seven of which are talkers and one is a listener. This results in a high load for the listener node.

We defined eight messages in different traffic classes. The parameters of the messages are shown in Table 3. The overhead of SR messages is assumed to be 42bytes, while for the ST messages is assumed to be 30Bytes due to removing 12Bytes of interpacket gap. Note that the listener for the messages is N8 in this example. In this experiment we do not have any BE traffic and the switch fabric latency \(\epsilon \) is assumed to be 5.2 \(\upmu \)s.

In the depicted architecture, we computed the idleSlope for classes A and B (\(\alpha ^+_A\) and \(\alpha ^+_B\)) based on the standard for each output link. Also, we calculated the over-reserved idleSlope (\(\beta ^+_A\) and \(\beta ^+_B\)) according to the presented solution in this paper. The results of idleSlopes are shown in Table 4, in Mbps. As it is mentioned in the system model, each link has two directions (full-duplex ports). Therefore, for each direction of a link, idleSlopes in class A and B are computed. In Table 4, for instance, L1<N1-SW1> shows link L1 with direction from N1 to SW1, hence it presents the idleSlope for output port of N1.

In Table 4, the zero values show that there is no traffic in that class that goes through that particular link and direction. For example, only a message belonging to class A crosses the link L1<N1-SW1>. Therefore, the idleSlope for class B is zero. Another observation is that the over-reservation for the links with higher load is larger. For instance, the idleSlope for class A on link L13<SW6-N8> is 8.26 Mbps since N8 is the listener for all defined messages. However, the over-reserved idleSlope is computed as 45.54 Mbps using the presented solution in this paper. This means that in order to have a schedulable system the idleSlope should be increased approximately 6 times for class A on link L13<SW6-N8>. This increase on the links with less load is lower. The reason is that by increasing the number of messages, the pessimism in the analysis becomes higher. Therefore, the bandwidth should be increased more to make the system schedulable. Furthermore, in some links no over-reservation is required. For instance, on link L1<N1-SW1> there is only one message crossing the link, hence, according to the analysis and solution, no over-reservation is required.

Using the over-reserved idleSlopes, we computed the response time of the messages. Moreover, we measured the response times in a simulation to be compared with the computed results. The simulation has been done with the original idleSlope (\(\alpha ^+\)) and the over-reserved idleSlope (\(\beta ^+\)) to show the effect of over-reservation in the simulation. We used offsets for ST messages. In the industrial case study there are two ST messages with 4 ms periods. The offsets are set to 0 s and 2 ms, respectively. Therefore, the interval between two consecutive ST messages is always 2 ms. The results are illustrated in Fig. 16. In the figure, the computed response times are indicated by RTA, while the simulation measurements are identified by Sim Max \(\alpha \) and Sim Max \(\beta \) for the maximum measured values for the original and over-reserved idleSlope, respectively. As it can be seen, all measured response times with the over-reserved idleSlope are always less than or equal to the computed ones. Moreover, the biggest difference between the maximum measured and calculated is for message 2, which shows around 86% pessimism. However, this level of pessimism is only for this example. Showing the level of pessimism for the analysis is rather difficult and it requires to provide a worst-case example ensuring that the simulation reaches the worst-case results. Note that the measured and computed response times for ST messages (messages 3 and 4) are equal as there is no interference or blocking on them. Also, their response times are much smaller than the other classes, thus showing the effectiveness of the AVB ST proposal. Another observation is that the measured response time for a message with the original idleSlope can be larger than the deadline of the message. In this case study, the measured response time of message 5 with the original idleSlope is 2033 \(\upmu \)s, which is larger than its deadline 1875 \(\upmu \)s, hence the system is not schedulable. We can conclude that there are case studies in which the system is not schedulable (with both response time analysis and simulation) if the idleSlope is assigned according to the standard. The over-reservation algorithm presented in this paper is very useful to achieve the minimum over-reservation and the system schedulability for such scenarios.

In this case study we consider an example automotive network consisting of two switches in a double star topology, illustrated in Fig. 17. The network supports an ADAS system consisting of three cameras (CAM1–CAM3), which send video frames to a specialized processing unit, named the DACAM. The DACAM processes the video frames and produces both warnings, which are sent to a Control Unit (CU) and to a Head Unit, and aggregated flows, which are displayed by the Head Unit. The network also supports the bidirectional exchange of control messages between the CU, the DACAM, and the Head Unit. In addition to these safety-critical flows, the network also supports some multimedia/infotainment and telematics systems, which are real-time, but not safety-critical.

For this case study we define 30 messages whose properties are inspired by realistic automotive messages. Audio and video frames are assigned to class A and B. The various type of control messages are all set as ST class. The properties of the messages are presented in Table 5. The switch fabric latency is assumed equal to 5.2 \(\upmu \)s.

Similarly to the previous case study, we computed the idleSlope for classes A and B based on the standard, and according to the over-reservation approach in this paper. The results for each link are shown in Table 6.

Considering the over-reserved bandwidth for each link, we calculated the response time of messages according to the analysis presented in this paper. Also, we measured the response times during the simulation. The results are depicted in Fig. 18. Similarly to the previous experiment, RTA, Sim Max \(\alpha \) and Sim Max \(\beta \) indicate the computed, maximum measured response times of the messages with the original and over-reserved idleSlope, respectively. As it can be seen, the computed response times of messages belonging to classes A and B are always larger than the measured ones with the over-reserved idleSlope. Also, the measured and computed response times of ST messages are always equal, and small compared to the response times of the other classes of messages. The highest pessimism in this example is for message 4 with around 86%. In the figure, the measured response times for messages 1, 2 and 3 are not the same, while their parameters are the same. In the simulation, all messages arrive to the switch at the same time in an order that is maintained in the simulation. This is why the first message has shorter response time compared with the others. However, in the analysis we consider the worst-case for each individual message. This case study validates the practicality of the ST approach as the ST messages have very short latency compared to the SR classes. Moreover, the over-reservation algorithm helps reduce the messages’ response time, e.g., for message 27.