Open access

Token Passing Techniques for Hard Real-Time Communication

Written By

Gianluca Franchino, Giorgio C. Buttazzo and Tullio Facchinetti

Published: March 1st, 2010

DOI: 10.5772/9529

Chapter metrics overview

2,849 Chapter Downloads

View Full Metrics

1. Introduction

Distributed computing platforms are increasingly used to develop critical embedded systems, like control applications, sensors networks, telecommunication, and robotics systems. In such distributed applications, the correct behaviour depends on the timely execution of the tasks running on different nodes, which may frequently exchange shared data. In particular, since the nodes are typically connected through a common channel without the need of multi-hop communication, it turns out that a timely communication mainly depends on how the nodes access the channel. Even when a multi-hop communication is needed, a timely message delivery is not feasible without the support of a predictable channel access mechanism, which is implemented in the Medium Access Control (MAC) sub-layer of the communication stack.

There exist several MAC protocols designed for providing a timely communication among distributed nodes, mainly in the factory communication domain. One of the most effective solutions is given by token passing protocols, which have some nice characteristics that make them suitable for real applications. For instance, because of the token passing mechanism, the nodes do not need to be synchronized and they have an implicit bandwidth reclaiming mechanism that allows other nodes to exploit the unused bandwidth. Moreover, such protocols can serve both real-time and best-effort (non real-time) traffic.

Among token passing protocols, the timed token policy is a channel scheduling approach first proposed by Grow in (Grow, 1982). Since then, it has received a substantial attention and several relevant results have been derived (Zhang et al., 2004), which make timed token

protocols suitable for the real-time communication in industrial applications. Timed token policies are used as channel access mechanism in several standard protocols such as, for instance, PROFIBUS (Profibus, 1996) and FDDI (FDDI, 1987). However, the application domain of the timed token policy is not restricted to the cited communication standards, and some examples on their use can be found in (Lenzini et al., 2004) and (Cicconelli et al., 2007}.

To improve the ability of timed token protocols of managing real-time traffic, Shin and Zheng (Shin & Zheng, 1995) proposed a modification of the timed token protocol, which can guarantee a greater bandwidth for the real-time traffic with respect to the classic timed token protocol; however, under certain conditions, it cannot manage the best-effort traffic (Franchino et al., 2008). The Budget Sharing Token (BuST) protocol has been proposed as an improvement with respect to existing timed token protocols (Franchino et al., 2008). In particular, BuSTimproves the bandwidth guaranteed for the real-time traffic with respect to the timed token protocol, and it can manage best-effort traffic in those situations where the modified timed token protocol fails on serving this kind of traffic.

This chapter introduces a few timed token protocols, presenting their characteristics and illustrating the main results available in the literature. The BuSTprotocol is discussed in detail, illustrating its main advantages by means of analytic and simulation comparisons. New and well known properties of the protocols for managing both hard real-time and best-effort traffic will be analyzed, describing drawbacks and strengths of each protocol. The analysis is carried out considering the main budget allocation schemes available in the literature, thus contributing to the comparative characterization of the several schemes nowadays available.

Advertisement

2. Network Model

The communication network is composed by nnodes sharing a common medium, e.g. a bus, where each node can transmit both real-time and best-effort traffic. The former kind of traffic is modelled by assigning each node ia synchronous message stream Si, which is described by three parameters (Ci, Di, Ti), where:

  • Ciis maximum amount of time necessary to transmit a message generated in the stream Si. This includes the time to transmit both the message payload and the message headers/footers;

  • Di is the relative deadline of a message generated by stream Si, that is, the maximum amount of time that a message can wait in transmission queue before its transmission is completed. Hence, the transmission of the j-thmessage, which is queued at time ti,j, must be completed no later than its absolute deadline di= ti,j+Di.

  • Ti is the generation period of messages in stream Si. If the j-thmessage in the stream Siis put in the transmission queue at time ti,j, then the (j+1)-thwill arrive in the transmission queue at time ti,j+1=ti,j+ Ti.

Without loss of generality, only a stream per node it is considered, since the case of a network with more streams per node can be represented with a logical equivalent one with a stream per logical node, as showed in (Agrawal et al., 1994). We consider that each node iis assigned a bandwidth Hi, also called time budget, used to bound the transmission of the node.

The channel utilization of each message in stream Siis:

U=iSCimin(Ti,Di)E1

The total channel utilization of a periodic stream set is then:

US=i=1nUiSE2

which measures the channel bandwidth utilized by the real-time (periodic) traffic.

Before describing the protocols, the following definitions are needed:

Definition 1. τ is the time needed to transmit the token between nodes, including the overhead introduced by the protocol.

Definition 2. The Target Token Rotation Time (TTRT) represents the expected time needed by the token to complete an entire round-trip of the network.

Any assignment of the time budgets Himust satisfy the following two constraints:

Definition 3. (Protocol Constraint) The total bandwidth allocated to the nodes, during one complete token rotation, must be less than the available network bandwidth, that is,

i=1nHiTTRT1τTTRTE3

The Protocol Constraint is necessary to ensure a stable operation of the protocols.

Definition 4. (Deadline Constraint) If si,jdenotes the time at which the transmission of the j-th message in stream Siis completed, the deadline constraint requires that for i=1, …, n, and j=1, 2, …,

si,jti,j+DiE4

where ti,jis the message arrival time and Diis its relative deadline.

Meeting the Deadline Constraint ensures that every periodic message is transmitted before its absolute deadline. Note that in Inequality (4), while ti,jand Diare defined by the application, si,jdepends on the bandwidth (budget) allocation and on the TTRTvalue.

Definition 5. A stream set Γ={S1, S2, …, Sn} is said to be feasible or schedulable when both the Deadline Constraint and the Protocol Constraint are met.

To test the Protocol Constraint it is sufficient to check whether the sum of the budgets are not greater than the TTRTminus the overhead τ. However, testing the Deadline Constraint may be much more complicated. The following method is often used for testing whether the Deadline Constraint is met:

Let Xi be the minimum amount of time available for node ito transmit its j-thmessage during the time interval (ti,j, ti,j+ Di], then for a message stream set with message deadlines not greater than periods, the Deadline Constraint can be satisfied if and only if for all i, i=1,2,...,n, Xi≥ Ci.

Advertisement

3. Timed Token Protocols

The timed token protocol (TTP) is a basic channel access technique, namely a MAC protocol, which can be used to manage real-time traffic while guaranteeing a fair sharing of the unused bandwidth to the best-effort traffic. In timed token approaches, a token travels between nodes in a circular fashion and each node can transmit only when it possesses the token. An important parameter is the Target Token Rotation Time (TTRT), which represents the expected time needed by the token to complete an entire round-trip of the network. Each node ihas an associated time budget Hi; whenever a node receives the token, it can transmit its real-time messages for a time no greater than Hi. It can then transmit its best-effort messages if the time elapsed since the previous token arrival to the same node is less than the value of TTRT, that is, only if the token arrives earlier than expected. Figure 1, shows a typical timed token based network where 4 nodes sharing a common channel are arranged in a logical ring, as far as the token passing mechanism is concerned.

Figure 1.

Timed token network.

3.1. TTPoperation rules

To better understand the TTPoperation, the protocol channel access rules are detailed below:

  • During the network start up, each nodeideclares a TTRTvalue equal to one half of the deadline Direlated to its message stream Si. The minimum declared value is chosen as TTRT, and each node iis then assigned a time budget Hithat depends on TTRT.

  • Each node uses two timers, the token holding timer (THT) and the token-rotation-timer (TRT). The TRTcounter always increases, whereas the THTonly increases when the node is delivering best-effort traffic. When TRTreaches TTRT, it is reset to 0 and the token is signed as "late" by incrementing the node's late counter Lcby one. To initialize the timers and Lc, no messages are sent during the first token rotation after the ring initialization.

  • Only the node holding the token can transmit messages. Transmission is controlled by the timers, but an in-progress transmission of a single packet is not interrupted until its completion. When node igets the token, it performs the following operations:

    oIf Lc> 0, it sets Lc= Lc-1 and THT= TTRT. Otherwise, THT=TRTand TRT= 0.

    oIf node ihas synchronous packets, it transmits them for a time no greater than Hi.

  • If node ihas best-effort packets, it transmits them until THTcounts up to TTRT, or until all the asynchronous traffic is sent, which ever comes first.

  • Node ipasses the token to station (i+1) mod (n+1).

The main drawback of TTPis the inability of guaranteeing the total available bandwidth for the real-time traffic. As Johnson and Sevciks (Johnson & Sevciks, 1987) showed, the average interval between two consecutive visits of the token at the same node, namely the average token rotation time, does not exceed TTRTand the maximum rotation time does not exceed 2TTRT. Thus, if Dis the minimum deadline among stream deadlines, i.e. D= min(Di), it turns out that TTRT = D/2. From the Protocol Constraint it follows that:

i=1nHiTTRTτ=D2τE5

In the time interval defined by D, the bandwidth available for the real-time traffic can be obtained dividing the above equation by D:

i=1nHiD12τDE6

Since the total available bandwidth is 1 – τ/TTRT, the TTPcan guarantee at most half of the total available bandwidth for the real-time traffic.

3.2. Modified TTPoperation rules

To improve the bandwidth guaranteed for the real-time traffic, Shin (Shin & Zheng, 1995) proposed to modify the timed token rules, limiting the maximum time available for best-effort traffic to TBMAX, where:

TBMAX=TTRTi=1nHiτE7

Notice that, under TTP, the maximum bandwidth allocated for best-effort messages is TBMAX=TTRT – τ.

In(Chan et al., 1997), the authors showed that the maximum token rotation time for the Modified Timed Token Protocol (MTTP) is bounded by TTRT. This means that, under MTTP it is possible to select a value for TTRTno greater than the minimum deadline D. Hence, being TTRT≤ D, from the Protocol Constraint it follows that:

i=1nHiDτE8

and dividing by D, it gives:

i=1nHiD1τDE9

That is, MTTP can guarantee all the available bandwidth for the real-time traffic.

By definingTS=Hi, to guarantee that TBMAX= TTRT –TS– τ, MTTP can be defined as follows:

1. A new token rotation time is defined as TTRTn= TTRT - TS, and used instead of TTRT;

2. The counting of a node’s token rotation timer (TRT) is stopped when a real-time message is being delivered by the node.

The full details of the protocol rules are given below:

  • During the network start up, each nodeideclares a TTRTvalue equal to one half of the deadline Direlated to its message stream Si. The minimum declared value is chosen as TTRT. Each node iis assigned a time budget Hithat depends on TTRT, and it sets TTRTn= TTRT - TS.

  • Each node uses two timers, the token holding timer (THT) and the token-rotation-timer (TRT). The TRTcounter increases only when the node is not transmitting real-time traffic, whereas the THTonly increases when the node is delivering best-effort traffic.

  • Only the node holding the token can transmit messages. Transmission is controlled by the timers, but an in-progress transmission of a single packet is not interrupted until its completion. When node igets the token, it performs the following operations:

    oIf Lc> 0, it sets Lc= Lc-1 and THT= TTRT. Otherwise, THT=TRTand TRT= 0.

    oIf node ihas synchronous packets, it transmits them for a time no greater than Hi.

  • If node ihas best-effort packets, it transmits them until THTcounts up to TTRT, or until all the asynchronous traffic is sent, which ever comes first.

  • Node ipasses the token to station (i+1) mod (n+1).

Advertisement

4. The BuST protocol

The BuSTprotocol has been devised to improve the ability of TTPin managing real-time traffic, and to overcome the problems MTTPcan have in managing best-effort traffic (see Section 7).

Like timed token protocols, the BuSTprotocol assigns each node a time budget Hifor transmitting its real-time traffic. When a node receives the token, it can transmit the associated real-time traffic for a time no greater than the corresponding budget. The main difference with respect to TTPand MTTPconcerns the best-effort traffic service. Under TTP, when the token arrives early, the node can transmit best-effort traffic for a time no greater than TA= TTRT – τ – TLRT, where TLRTis the time spent in the last round-trip of the token. Using MTTP,a node does the same, but withTA=TTRTτHi. With BuST, a node can deliver non real-time traffic each time it gets the token, early or not, using the spare budget left by real-time messages. If Hicons is the budget consumed by node ito deliver periodic traffic, then it can send best-effort traffic for a time no greater than TAi= Hi– Hicons, even if the token is not early. Observe that, TTPand MTTPcan deliver best-effort traffic only when the token is early, that is, when TLRT<TTRT – τ.

The following rules specifies the BuST protocol in detail:

  • During the network initialization phase, each node ideclares a TTRTvalue equal to the deadline Diof its periodic message stream. The minimum declared value is selected as TTRT. Each node iis assigned a time budget Hithat depends on TTRT.

  • Each node has one timer, the token holding-rotation timer THRT. The THRTcounter always increases. To initialize the timers, no messages are sent during the first token rotation.

  • Only the node having the token can transmit messages. The transmission is controlled by THRT, but an in-progress transmission of a single packet is not interrupted until its completion. When node igets the token, it performs the following operations:

    • It sets THRT= 0.

    • If node ihas real-time packets, it transmits them until THRTcounts up to Hi, or until all the real-time traffic is sent, whichever comes first.

    • If node ihas best-effort packets, it transmits them until THRTcounts up to Hi, or until all the best-effort traffic is sent, which ever comes first.

    • If a real-time message becomes ready during the transmission of best-effort packets, and THRT<Hi, the transmission is stopped and the node starts delivering the real-time traffic until THRTcounts up to Hi, or until all the periodic traffic is sent, whichever comes first.

    • If node icompletes the transmission of the periodic traffic without entirely consuming its budget, i.e. THRT<Hi, it starts transmitting its non real-time traffic, if any, until THRTcounts up to Hi, or until all the best-effort traffic is sent, which ever comes first. Note that, in this case, the transmission is not stopped even if a real-time message becomes ready.

    • Node ipasses the token to station (i+1) mod (n+1).

The overhead generated when a best-effort transmission is interrupted can be easily accounted for. The same observation can be done for the overhead generated when an in-progress packet transmission is not interrupted until its completion. This also holds for TTPand MTTP.

As we can note from the protocol rules, under BuST, any node iexploits its time budget Hito deliver both real-time and non real-time messages. When compared to TTP, BuSTimproves (as MTTP) the bandwidth available for real-time messages and halves the bandwidth lost due to the protocol overhead. In addition, BuSTis able to deliver best-effort traffic also in those cases in which MTTPfails, as it will be shown in Section 7.

As a final remark, the implementation of BuSTonly requires one timer, instead of the two timers needed by TTPand MTTP. This can be useful when BuSTis adopted in small embedded systems, where resources (i.e., hardware timers) are scarce.

Advertisement

5.Time properties

In this section, we introduce the main time properties of the protocols under analysis. These properties are the basis to understand the protocols timing behaviour, to verify if a given periodic stream setM={S1, S2, …, Sn}is feasible, i.e. both the Protocol and the Deadline Constraints are met. Moreover, the results showed in the following can be used to analyses the protocols performance under the budget allocation schemes introduced in the next sections.

Lemmas 5.1, 5.2 and 5.3 provide an upper bound on the maximum transmission time for a real-time message under the BuST, MTTPand MTTPprotocols.

Lemma 5.1Under the BuST protocol, for all budget allocation schemes, if Ti≥ TTRT, i=1,…,n, it

holds:

i,j:si,jti,j+CiHi(k=1nHk+τ)E10

Proof.See (Franchino et al., 2007).

Lemma 5.2Under the TTP protocol, for all budget allocation schemes, if Ti≥ 2TTRT, i=1,…,n, it

holds:

i,j:si,jti,j+(CiHi+1)TTRT+CiCiHiHiE11

Proof. See (Franchino et al., 2007).

Lemma 5.3Under the MTTP protocol, for all budget allocation schemes, if Ti≥ TTRT, i=1,…,n, it

holds:

i,j:si,jti,j+CiHiTTRT+CiCiHiHiE12

Proof. See (Franchino et al., 2007).

The results and proofs in (Chen & Zhao, 1992) and (Chan et al., 1997) have been used as basis to derive the properties of BuST shown in the following. For comparison, the same type of results for TPP and MTTP, available in literature, are reported as well.

Theorem 5.1 gives the upper bound between any two consecutive visits of the token at the same node.

Theorem 5.1Under the BuST protocol, for any, i=1,…,n, and for any integer l > 0 it turns out that:

ti(l+1)ti(l)j=1nHj+τE13

where ti(l) is the time the token makes the l-thvisit at node i.

Proof. We provide the proof for the BuSTprotocol. For the MTTP protocol, the proof is very similar and it can be found in (Chan et al., 1997).

Since a node i can use only its time budget Hito transmit both real-time and best-effort traffic, the length of interval [ti(l), ti(l+1)] is equal to the sum of:

  1. time for real-time traffic transmission:trtj=1nHj;

  2. time for non real-time traffic transmission:tnrtj=1nHjtrt;

  3. time due to protocol overhead and token passing: τ.

    Thus,

    ti(l+1)ti(l)=trt+tnrt+τtrt+j=1nHjtrt+τ=j=1nHj+τ

The following corollary, generalizes the last theorem providing the upper bound on the time elapsed between v consecutive token arrival at the same node.

Corollary 5.1Under the BuST protocol, for any, i=1,…,n, and for any integer l > 0 and v > 0 it turns out that:

ti(l+v)ti(l)v(j=1nHj+τ)E14

where ti(l) is the time the token makes the l-th visit at node i.

Proof.By Theorem 5.1, it follows that:

ti(l+v)ti(l)=[ti(l+1)ti(l)]+[ti(l+2)ti(l+1)]+...+[ti(l+v)ti(l+v1)]j=1nHj+τ+j=1nHj+τ+...+j=1nHj+τ=v(j=1nHj+τ).

The following result, gives the upper bound between two consecutive token visits at the same node with the timed token protocol.

Theorem 5.2Under the TTP protocol, for any, i=1,…,n, and for any integer l > 0 it turns out that:

ti(l+1)ti(l)TTRT+j=1nHj+τ2TTRTE15

Proof.See (Sevcik & Johnson, 1987).

The next corollary, provides the upper bound on the time elapsed between v consecutive token visits at same node.

Corollary 5.2Under the TTP protocol, for any, i=1,…,n, and for any integer l > 0 and v > 0 it turns out that:

ti(l+v)ti(l)vTTRT+j=1,jinHj+τE16

where ti(l) is the time the token makes the l-th visit at node i.

Proof.See (Chen & Zhao, 1992).

The bound between two consecutive token arrivals at the same node, under the modified timed token protocol, is provided by the following theorem.

Theorem 5.3Under the MTTP protocol, for any, i=1,…,n, and for any integer l > 0 it turns out that:

ti(l+1)ti(l)TTRTE17

Proof. See (Chan et al., 1997).

The corollary below, generalizes the last theorem giving the upper bound between v consecutive token vistis at the same node.

Corollary 5.3Under the MTTP protocol, for any, i=1,…,n, and for any integer l > 0 and v > 0 it turns out that:

ti(l+v)ti(l)vTTRTE18

where ti(l) is the time the token makes the l-thvisit at node i.

Proof. See (Chan et al., 1997).

The following lemmas, give the minimum amount of time available for node i to transmit its real-time traffic before the deadline of each message. Notice that, for simplicity’s sake we consider a deadline Di= Ti. When the deadline Diis less than the period Ti, it is sufficient to replace Tiwith Diin the following results.

Lemma 5.3Under the BuST protocol, for any i=1,...,n, if at time t a periodic message with period Ti

arrives at node i, then in time interval (t,t+Ti] the minimum amount of time Xiavailable for node i to transmit the message is:

XiTij=1nHj+τHi+max(0,Hiδi)E19

whereδi=Tij=1nHj+τ(j=1nHj+τ)Ti.

Proof. Suppose t the time at which a new message is ready at node i. In the worst case, the token has just left node i when the new message is ready. As a consequence of Theorem 5.1, in time interval Ii=[t, t + Σnj=1Hj+ τ] node i receives the token at least once. Let t + t1be the time at which node i receives the token since t, it turns out that 0<t1≤ Σn j=1HjHi. Hence, Hi≤ Σn j=1Hj+ τt1, that is, the time available for node i to transmit its real-time traffic in Iiis Hi. Thus, by Corollary 5.1, it turns out that in a time interval Ii=[t, m·(t+Σn j=1Hj+τ)] node i has a minimum amount of time, to deliver its real-time traffic, equal to m·Hi.

If Δi=Ti/(Σn j=1Hj) and m=Δi, two cases are possible:

1. Δiis an integer, such that δi=0andIm=[t,t+m(j=1nHj+τ)]=[t,t+Ti], then it follows thatXi=Tij=1nHj+τHi.

2. Δiis not an integer, such that δi>0. In the worst case, the (m+1)-th token’s arrival at node i may be as late as

t+m(j=1nHj+τ)+j=1nHj+τ+Hi,

then, this token arrival will be not more than t+Tiif:

j=1nHj+τHiTi+m(j=1nHj+τ)=j=1nHj+τδi.

In this case, the residual transmission time available for the real-time traffic is the left time until t+Ti, which is equal to Hiδi, that is:

XiTij=1nHj+τHi+max(0,Hiδi)

Lemma 5.4Under the TTP protocol, for any i=1,...,n, if at time t a periodic message with period Ti

arrives at node i, then in time interval (t,t+Ti] the minimum amount of time Xiavailable for node i to transmit the message is:

XiTiTTRT1Hi+max(0,min(δiτj=1,jiHj,Hi))E20

whereδi=TiTiTTRTTTRT.

Proof. See (Chen & Zhao, 1992).

Lemma 5.5Under the MTTP protocol, for any i=1,...,n, if at time t a periodic message with period Ti

arrives at node i, then in time interval (t,t+Ti] the minimum amount of time Xiavailable for node i to transmit the message is:

XiTiTTRTHi+max(0,Hiδi)E21

whereδi=TiTTRTTTRTTi.

Proof. See (Chan et al., 1997).

Advertisement

6.Performance analysis

The real-time guarantee of the stream set highly depends on the budget allocation scheme (BAS) adopted for budgets assignment given the stream set parameters.

In literature exist several budget allocation schemes provided for timed-token protocols. They are traditionally classified into global or local schemes, depending on whether they need global or local information to assign the budgets. Local information is, for instance, the node stream parameters. Global information is, for instance, the number of nodes and the total channel utilization USrequired by the streams.

In this work, the budget allocation schemes are classified as proposed in (Daoxu et al. 1998). They can be divided into two categories, depending on the way they assign the budgets. The first category is the set of the TTRT-partitioningschemes, where a scheme belonging to this set assigns node budgets partitioning the time expected for the token to make a rotation of the network, i.e. TTRT −τ. The TTRT-partitioningschemes analyzed in the following are shown in Table 1.

The second category of budget allocation schemes, is the set of Ci-partitioningschemes, where a scheme belonging to this class assigns each budget Hipartitioning the maximum time length, Ci, to send a message from the stream Siamong a certain number of token rotation cycles. The Ci-partitioningschemes analyzed in the following are shown in Table 2.

TTRT-partitioning schemesAssignment rule
Proportional Allocation (PA)

Normalized Proportional Allocation (NPA)

Equal Partition Allocation (EPA)

Table 1.

TTRT-partitioningbudget allocation schemes.

TTRT-partitioning schemesAssignment rule
Local Allocation (LA)


Modified Local Allocation (NPA)

Table 2.

Ci-partitioningbudget allocation schemes.

The budget allocation schemes showed in the tables above have been extensively analyzed in literature. For a complete survey, an interested reader can see (Zhang et al., 2004) for TTP; (Chan et al., 1997) and (Daoxu et al., 1998) for MTTP; (Franchino et al., 2007), (Franchino et al., 2008) and (Franchino et al., 2008a) for BuST.

In the following, we compare the schemes performance under the token passing protocols considered in this chapter.

6.1. Performance metric

For evaluating and comparing the performance of different budget allocation schemes several metrics have been proposed. One of the most widely adopted metric is the Worst Case Achievable Utilization (WCAU). The WCAU of a budget allocation scheme represents the largest utilization (U*) of the network such that, for any real-time message set whose total network utilization is USU*, the budget allocation scheme can guarantee the timeliness of each single real-time message.

The WCAU test is useful to guarantee the feasibility of a periodic stream set when only an estimation of the amount of real-time traffic is known (i.e., the maximum time required to send a message) without requiring a detailed characterization of each single real-time message.

6.2. Budget allocation schemes analysis

In the following, we assume Di= Tifor all the streams, however, the same results can be derived for the case where Di< Tiby simply substituting Dito Ti. To make the treatment clearer, when not differently specified, let βi=Ti/TTRT, βmin= min(Ti)/TTRTand α=τ/TTRT. Parameter α represents the bandwidth loss due to the overhead.

Table 3 summarizes the WCAUs of the budget allocation schemes considered in this work.

With the PAscheme, the BuSTprotocol is the only one having a WCAUgreater than 0, whereas with TTPand MTTPno stream set can be guaranteed.

With the NPAscheme, BuSTand MTTPpresent the same WCAU which depends on βmin, hence the smaller TTRTthe greater is the bandwidth that the protocols can guarantee for the real-time traffic. Since βmin≤ 1 the minimum WCAUfor the NPA, under both BuSTand MTTP, is (1-α)/2. Instead, the TTPprotocols with the NPAscheme presents a WCAUwhich does not depends on βminand it is lower than that presented by the other protocols. It is worth observing that, under the NPAscheme, the MTTPprotocol cannot serve best-effort traffic (Franchino et al., 2008). Conversely, the BuSTprotocol presents the same WCAUof MTTPand can serve also best-effort traffic.

Under the EPAscheme, BuSTand MTTPhave a greater WCAUwith respect to TTP. However, the WCAUof all the tree protocols is very poor and it depends on the number of nodes. As for the NPAscheme, also under the EPAscheme the MTTPprotocol cannot serve non real-time traffic.

BuST, MTTPand TTPpresent the same WCAUunder the LAscheme. As for the NPAscheme, the WCAUunder the LAscheme depends on βmin, i.e. on the choice of TTRT. With the LAscheme βmin≥ 2, thus the minimum WCAUof this scheme is (1-α)/3.

With the MLAscheme, TTPpresents a null WCAU. Instead, both BuSTand MTTPpresent a WCAUwhich depends on βminand equivalent to that presented with the NPAscheme. As shown in (Franchino et al., 2008a), with the MLAscheme MTTPcan not serve best-effort traffic when Σni=1HiTTRT+ τ.

Allocation schemesTTPMTTPBuST
PA



NPA


ELA


LA (βmin≥2)


MLA (βmin≥1)
0







0
0





Table 3.

WCAU of the considered schemes.

Advertisement

7. Best-effort traffic service

So far, real-time streams service have been analyzed. This section briefly describes the best-effort service of the BuSTprotocol and its improvements with respect to MTTP.

As shown in Section 4, under MTTPthe maximum time a node can use to deliver non real-time traffic isHi=Ui(TTRTτ). It can be observed that:

  • For the PA schemeHi=UiU(TTRTτ);

  • For the NPAschemeHi=TTRTτn;

  • For the EPAschemeHi=CiTiTTRT1;

This means that MTTPis not able to deliver best-effort traffic under both the NPAand the EPAschemes, while TAdepends on Ususing the PAscheme. Moreover, it can be observed that MTTPcan not serve non real-time traffic whenHi=CiTiTTRT.To verify this last statement, it is sufficient to note that, as stated in Section 3.1, each time a node receives the token it can transmit non real-time traffic for a time no greater than TA, and since1α3, it follows that TA= 0. This means that, when this last condition holds, MTTP can starve best effort traffic also with both the LAand the MLAschemes.

To analyze a worst-case scenario for non real-time service, we assume that each node receiving the token has always best-effort traffic to deliver. In this case, the total channel utilization of the network, including real-time and best-effort traffic, is equal to 1-α, i.e. the channel is fully utilized.

The following theorem provides the minimum bandwidth that a node i can exploit to deliver non real-time traffic under the BuSTprotocol.

Theorem 7.2Under the BuST protocol, a node i can guarantee for the non real-time traffic a minimum bandwidth Uinrt, which depends on the budget allocation scheme adopted. In particular:

  • with PA,1α3n(1α);

  • with NPA,βmin1βmin+1(1α);

  • with EPA,βminβmin+1(1α);

Proof. See (Franchino et al., 2007), (Franchino et al., 2008) and (Franchino et al., 2008a).

We have shown that, under the BuSTprotocol, non real-time traffic at each node has a minimum bandwidth guaranteed. In addition, it is worth observing that, when not all nodes of the network have to send best-effort traffic, during the round trip of the token, the value of Uinrtcan increase.

Advertisement

8. Simulation results

In this section the performance of BuST, TTPand MTTPis compared by simulation. The simulations have been performed through a discrete-event simulator written for this purpose in C language. The simulation scenario considers a network consisting of 10 nodes. Each node has a periodic stream with a relative deadline ranging from 10 msecto 100 msec. An infinite amount of non real-time traffic is assumed: this means that, every time a node receives the token, it has some non real-time traffic to deliver. As already stated in Section 7, in this case the total channel utilization UTOT= UNRT+ USis equal to the total available bandwidth 1-α. Node budgets are assigned using the PA, NPA, LA, and MLAbudget allocation schemes.

Performance is evaluated through the Maximum Deadline Miss Ratio (MDMR), defined as the ratio between the number of messages that miss their deadline and the total number of generated messages. The MDMRis measured as a function of the real-time channel utilization US, ranging from 0.1 to 1.0 (step of 0.1). For each value of US, up to 1000 simulation runs are performed, and the MDMRis considered among the runs. A different stream set is generated each run. In particular, for each stream set the utilizations UShave been generated randomly with a uniform distribution using the method proposed in (Bini & Buttazzo, 2004). For each value of UiS, a relative deadline Diis generated randomly with a uniform distribution in the interval [10, 100] msec. Periods are assumed equal to deadlines, i.e for all i Ti= Di. The message lengths Cihave been computed as Ci= UiSDi. The overhead τ is assumed equal to 20 μsec.

In the simulations, the token is considered as never lost and no ring recovery process is implemented. In this way, a violation of the Protocol Constraint will not compromise the stability of the protocols.

For each scheme, three different scenarios have been considered in the simulations. One where TTRT= min(Di), one where TTRT= min(Di)/2, and the last with TTRT= min(Di)and only real-time traffic in the network.

Note that, when there is only real-traffic in the network BuST, TTPand MTTPoperate in the same way, that is, they are in practice the same protocol. Therefore, as it will be shown in the following, in case of only real-time traffic all the three protocols present the same performance in terms of MDMR.

8.1. Results with the PA scheme

In this subsection the results for the PAscheme are analyzed. Figure 2 shows the MDMRwhen the PAscheme is used to assign the node budgets, and TTRT= min(Di).

As expected from the results showed in Section 6, as long as US≤ 0.5, with BuSTall the messages meet their deadlines (MDMR= 0), while TTPand MTTPpresent a non-null deadline miss ratio. For US= 0.6, BuSTpresents a very small MDMR(equal to 0.5%) that cannot be appreciated in the figure. For US≥ 0.7, BuSTpresents a significant MDMRwhich is about 76% when US= 1, that is, when the channel is over-utilized (remember that the available bandwidth is 1-α).

While TTPpresents a significant MDMRfor all values of US, MTTPpresents a MDMRlower than that shown by BuSTfor US≤ 0.9.

Figure 3 shows the MDMRwith TTRT= min(Di)/2. Notice that, the performance of both BuSTand MTTPimprove as expected. Instead TTPstill presents a very poor performance.

Figure 4 shows the MDMRwhen nodes have only real-time traffic to deliver and TTRT= min(Di). In this case, as said before, the three protocols operate in the same way, producing the same performance. As long as USis not greater than 0.5, there are not deadline misses. With US= 0.6 we have a very small MDMR, which is equal to 0.69%. For US≥ 0.7 the MDMRstarts increasing significantly.

8.2. Results with the NPA scheme

Figure 5 reports the MDMRwhen the NPAscheme is used to assign node budgets and TTRT= min(Di).

As long as US≤ 0.5, BuSTand MTTPhave no deadline miss; for US≥ 0.6, they start experiencing deadline misses. It is worth noticing that, for US= 0.6, BuSTpresents a MDMRclose to 0%, which is not appreciable in the figure.

TTPhas deadline misses for all values of US; this is due to the fact thatTTPrequires that TTRT ≤ min(Di)/2to work properly.

For US≥ 0.9, MTTPperforms better than BuST. However, it is worth remembering that, under the NPAscheme, MTTPis not delivering non real-time traffic. This is the reason why it can provide a better service for real-time traffic.

Figure 6 shows the MDMRwith TTRT = min(Di)/2. Notice that, with a lowerTTRT, the performance of all the three protocols improves, as expected by the theoretical analysis showed in the previous sections. In particular, TTPhas no deadline miss as long as US≤ 0.3. For US= 0.4 and US= 0.5, TTPpresents an MDMRclose to 0%. For US≥ 0.6, TTPpresents an MDMRsignificantly greater than 0%. Notice that, BuSTand MTTPprovide more or less the same performance, with the difference that BuSTserves also non real-time traffic.

Figure 7 shows the MDMRwhen nodes have only real-time traffic to deliver and TTRT = min(Di).

8.3. Results with the LA scheme

Figure 8 shows the MDMRwhen the LAscheme is used to assign node budgets and TTRT = min(Di)/2.

As long as US≤ 0.8, MTTPand BuSTpresent a null MDMR. For US= 0.9, they present a MDMRnot appreciable in the figure, which is less than 0.05% for both protocols. TTPpresents a null MDMRas long as US≤ 0.4, and a MDMRless than 0.3% for 0.5 ≤ US≤ 0.7, which is not appreciable in the figure. For US> 0.7, TTPpresents a MDMRsignificantly greater than BuSTand MTTP.

Figure 9 shows the MDMRwhen the nodes have only real-time traffic to deliver. As it can be noted, the absence of non real-time traffic improves the protocols performance considerably. In particular, as long as US≤ 0.8, the MDMRis null; for US= 0.9, the MDMRis still close to 0%, and when US= 1 the MDMRis about 7%.

Finally, it is important to notice that a message deadline miss is due to the Protocol Constraint violation. As seen in Section 6, under the LAscheme, as long as the Protocol Constraint is met, the Deadline Constraint is met as well. Furthermore, as highlighted in Section 7, when the Protocol Constraint is not met, or even if the sum of the budgets is equal to TTRT - τ, MTTPcannot serve non real-time traffic.

8.4. Results with the MLA scheme

Figure 10 shows the MDMRwhen the MLAscheme is used to assign the node budgets, and TTRT = min(Di).

As long as US≤ 0.7, MTTPand BuSTpresent a null MDMR; for US= 0.8 and for U S= 0.9, the MDMR is less than 1% for both protocols. Under TTP, the MDMRis non-null for all values of US. This is due to the fact that, as stated in Section 6, the Deadline Constraint cannot be satisfied when the MLAscheme is used under TTP.

Figure 11 shows the MDMR under the MLAscheme when TTRT= min(Di)/2. For BuSTand MTTP, as long as US≤ 0.8, the MDMRis null. When US= 0.9, the MDMRis not greater than 0.3%, hence is not appreciable in the figure, while when the channel is overloaded, i.e. US= 1, the MDMRis approximately equal to 15%.

Figure 12 depicts the MDMRwhen nodes have only real-time traffic to deliver and TTRT= min(Di). As said before, in this case, all the three protocols present the same performance, and the absence of non real-time traffic improves the protocols performance considerably. In particular, as long as US≤ 0.8, the MDMRis null or very small. For US= 0.9, the MDMRis less than 2%, and when US= 1 the MDMRis close to 5%.

As highlighted in Section 6 for the LAscheme, when the MDMRis not null it means that the Protocol Constraint is not met also for the MLAscheme and, because of this, MTTPis not able to deliver non real-time traffic.

Figure 2.

Maximum Deadline Miss Ratio with the PA scheme.

Figure 3.

Maximum Deadline Miss Ratio with the PA scheme whenTTRT=min(Di)/2.

Figure 4.

Maximum Deadline Miss Ratio with thePAscheme with only best-effort traffic.

Figure 5.

Maximum Deadline Miss Ratio with theNPAscheme.

Figure 6.

Maximum Deadline Miss Ratio with theNPAscheme whenTTRT=min(Di)/2.

Figure 7.

Maximum Deadline Miss Ratio with theNPAscheme with only best-effort traffic.

Figure 8.

Maximum Deadline Miss Ratio with theLAscheme.

Figure 9.

Maximum Deadline Miss Ratio with theLAscheme with only best-effort traffic.

Figure 10.

Maximum Deadline Miss Ratio with theMLAscheme.

Figure 11.

Maximum Deadline Miss Ratio with theMLAscheme whenTTRT=min(Di)/2.

Figure 12.

Maximum Deadline Miss Ratio with theMLAscheme with only best-effort traffic.

Advertisement

9. Conclusions

In this work, we introduce and analyzed the BuSTprotocol in comparison with timed token and modified timed token protocols. All the three protocols are discussed in detail, showing their strengths and their drawbacks under different budget allocation schemes. New and well known time properties of the protocols are presented, together with their capability on managing both hard real-time and best-effort traffic. In particular, we have seen that both BuSTand MTTPare superior on serving real-time traffic with respect to the traditional timed token protocol. However, it has been shown that when both NPAand EPAschemes are used to assign the node budgets, MTTPcan starve best-effort traffic. Conversely, the BuSTprotocol can serve also best-effort traffic under all the analyzed budget allocation schemes.

Future work is focused on extending the performance analysis of BuSTwith other allocation schemes available in literature.

References

  1. 1. AgrawalG.ChenB.ZhaoW.DavariS.1994Guaranteeing Synchronous Message Deadlines with the Timed Token Medium Access Protocol,IEEE Transaction on Computers,433(March 1994),327339,0018-9340.
  2. 2. BiniE.ButtazzoG. C.2005Measuring Performance of Schedulability Tests, Real-Time Systems,301-2, ( May 2005),129154,0922-6443.
  3. 3. ChanE.DaoxuC.CaoJ.LeeC.1997Timing Properties of the FDDI-M Medium Access Protocol. The Computer Journal,401(1997),4349,0010-4620.
  4. 4. ChenD.ZhaoW.1997Properties of the Timed Token Protocol. Technical Report92038, Computer Science Dept., Texas A&M University, October 1992.
  5. 5. DaoxuC.ChanE.LeeV. C. S.1998Timing Properties of the FDDI-M Medium Access Protocol for a Class of Synchronous Budget Allocation Schemes. Proceedings of 7-th Int. Conferance on Computer Communications and Networks, (ICCCN98),825832, Lafayette, Lousiana, USA, Oct. 1998.
  6. 6. CicconettiC.LenziniL.MingozziE.SteaG.2007An Efficient Cross Layer Scheduler for Multimedia Traffic in Wireless Local Area Networks with IEEE 802.11e HCCA. ACM Mobile Computing and Communication Review,113(July 2007),3146,1559-1662.
  7. 7. Fiber Distributed Data Interface (FDDI)1987Token Ring Medium Access Control (MAC), May 1987. ANSI Standard X3.139.
  8. 8. FranchinoG.ButtazzoG. C.FacchinettiT.2007BuST: Budget Sharing Token Protocol for Hard Real-Time Communication, Proceedings of 12th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA07),12781285, Patras (Greece), September 2007, IEEE.
  9. 9. FranchinoG.ButtazzoG. C.FacchinettiT.2008Time Properties of the BuST Protocol under the NPA Budget Allocation Scheme, Proceedings of the Conference on Design, Automation and Test in Europe (DATE 2008),10511056, Munich (Germany), March 2008, ACM.
  10. 10. FranchinoG.ButtazzoG. C.FacchinettiT.2008aProperties of BuST and Timed Token Protocols in Managing Hard Real-Time Traffic, Proceedings of 13th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA08),12051212, Hamburg (Germany), September 2008, IEEE.
  11. 11. GrowR. M.1982A Timed Token Protocol for Local Area Networks. Proceedings of Electro’82, Paper 17/3, May 1982.
  12. 12. LenziniL.MingozziE.SteaG.2004Design and Performance Analysis of the Generalized Timed Token Service Discipline. IEEE Transaction on Computers,537(July 2004),879891,0018-9340.
  13. 13. Profibus1996General Purpose Field Communication System. European Standard EN50170, CENELEC,23, Profibus, July 1996.
  14. 14. SevcikK. C.JohnsonM. J.1987Cycle time properties of the FDDI token ring protocol. IEEE Transaction Software Engineering,SE-13,3(1987),376385.
  15. 15. ShinK. G.ZhengQ.1995FDDI-M: A Scheme to Double FDDI’s Ability of Supporting Synchronous Traffic. IEEE Transaction on Parallel and Distributed Systems,611(November 1995),11251131,1045-9219.
  16. 16. ZhangS.BurnsA.ChenJ.LeeE.2004Hard Real-Time communication with the Timed Token Protocol : Current State and challenging Problems.Real-time Systems,273( September 2004),271295,0922-6443.

Written By

Gianluca Franchino, Giorgio C. Buttazzo and Tullio Facchinetti

Published: March 1st, 2010