Deterministic and probabilistic QoS guarantees for real-time traffics in a DiffServ/MPLS architecture Leila Azouz Saidane Pascale Minet Steven Martin Ines Korbi ENSI, CRISTAL INRIA Rocquencourt Univ. Paris Sud, LRI, ENSI, CRISTAL Campus Manouba 78153 Le Chesnay, France 91405 Orsay, France Campus Manouba 2010, Tunis, Tunisie
[email protected] [email protected] 2010, Tunis, Tunisie
[email protected] [email protected]
Abstract In this paper, we focus on the quantitative Quality of Service (QoS) guarantee in a Differenciated Services (DiffServ) domain that can be granted to an Expedited Forwarding (EF) flow in terms of end-to-end delay. This study shows that delays much smaller than the deterministic bound can be guaranteed with probabilities close to one. An admission control derived from these results is then proposed, providing a probabilistic QoS guarantee to EF flows.
1. Introduction The DiffServ architecture is based on traffic aggregation in a limited number of classes. The highest priority class, denoted the EF class, has been proposed for applications requiring low end-to-end packet delay, low delay jitter and low packet loss (e.g. voice and video applications that are delay and jitter sensitive). In addition, MultiProtocol Label Switching (MPLS) has been introduced to improve routing performance and then to obtain shorter packet response time. As MPLS allows to fix the path followed by all packets of a flow, it makes easier the QoS guarantee. Moreover, a MPLS label can easily represent a DiffServ class of service.
bound which is infrequently reached. The probabilistic approach, based on the probability density function of the response time, is introduced to evaluate the probability of missing a given deadline. This study shows that delays much smaller than the deterministic bound can be guaranteed with probabilities close to one. An admission control derived from these results is then proposed, providing a probabilistic QoS guarantee to EF flows. For this analysis, we adopt the following assumptions. Assumption 1 On each node, the EF class scheduling is FIFO and packet scheduling is non-preemptive. Assumption 2 All routers are DiffServ-compliant and Label Switching Routers (LSR). Assumption 3 Links interconnecting routers are supposed to be FIFO. Assumption 4 The network delay between two nodes has known lower and upper bounds: P min and P max. Assumption 5 Network is reliable: neither network failures nor packet losses. Assumption 6 We focus on a set τ = {τ1 , ..., τn } of n EF flows. According to MPLS , each flow τi follows a fixed sequence of nodes, called path, denoted Pi and comprising |Pi | nodes.
2. Deterministic approach In this paper, we show how to provide a quantitative QoS guarantee to all the EF flows in a DiffServ/MPLS domain. More precisely, we focus on the end-to-end response time of such flows. Indeed, beyond the qualitative definition of the offered QoS, no end-to-end quantitative guarantees have been proved for the EF class [1]. Two approaches are presented. The deterministic one is based on a worst case analysis and leads to a deterministic
The assumptions used in this section are those given in Section 1 plus additional ones specific to the deterministic approach. In this worst case analysis, we compute the worst case end-to-end response time of sporadic flows, using the trajectory approach. The trajectory approach considers the worst case scenario that can happen to a packet along its trajectory (its path) and not on each node visited (as done by the holistic approach [2]).
Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS’05) 1526-7539/05 $20.00 © 2005 IEEE
Assumption 7 The EF flows are assumed to be sporadic. A sporadic flow τi is defined by:
j=1 f irstj,i =h
slowj,i
(Cj
/Tj ))
≤
1,
Lemma 2 Assuming Condition 1 is met, the delay incurred by the packet of the EF flow τi generated at time t due to other EF packets is bounded by: h n Smaxh slowj,i i +Jj j=1 1 + · C j h∈Pi Tj f irstj,i =h
+
h∈Pi h=slowi,i
maxj∈τ {Cjh } − Cilasti ,
where S maxhj is the maximum time taken by a packet of the EF flow τj to arrive on node h, Jjh is the worst case jitter of flow τj when entering node h and lasti is the last node visited by flow τi .
Moreover, we assume that time is discrete. It has been shown in [3] that results obtained with a discrete scheduling are as general as those obtained with a continuous scheduling when all flow parameters are multiples of the node clock tick.
The worst case end-to-end response time of any flow τi is given by Property 1.
For the sake of simplicity, we first assume that all flows meet the following assumption. We will see in Subsection 2.2 how to remove this assumption.
EF
Property 1 Assuming Condition 1 is met, the worst case end-to-end response time of any packet of EF flow τi is bounded by: n Smaxh +Jjh slow j,i i 1+ · Cj Rmaxi ≤ Tj
Assumption 8 Forany EF flow τj following path Pj with Pj = Pi and Pj Pi = ∅ , if there exists a node h ∈ Pj Pi such that τj visits h = h + 1 immediately after h, then τj never visits a node h ∈ Pi after.
h∈Pi
2.1. Worst case end-to-end response time EF
h∈Pi (
where f irstj,i (respectively slowj,i ) is the first (respectively the slowest) node visited by the EF flow τj on path Pi .
• Ti , the minimum interarrival time (abusively called period) between two successive packets of τi ; • Cih , the maximum processing time on node h of a packet of τi ; • Ji , the maximum jitter of packets of τi arriving in the DiffServ domain; • Di , the end-to-end delivery deadline: any packet of flow τi generated at time t must be delivered at the latest at time t + Di .
The end-to-end response time of any generated at time t depends on:
n
Condition 1
+
packet m of τi
h∈Pi h=slowi,i
j=1 f irstj,i =h
max{Cjh } + j∈τ
h∈Pi
(B h − 1) + (|Pi | − 1) · P max.
Proof: From Lemmas 1 and 2.
• δi (t), the delay due to the non-preemptive effect; • XEF (t), the delay due to other EF packets; • network delays, bounded by (|Pi | − 1) · P max.
We can notice that this bound on the worst case endto-end response time is more accurate than the sum of the maximum sojourn times on the visited nodes, plus the sum of the maximum network delays. This shows the interest of the trajectory approach comparatively to the holistic one.
The two following lemmas establish bounds on δi (t) and XEF (t). Proofs are given in [4].
2.2. Generalization
Lemma 1 The maximum delay due to packets not belonging to the EF class incurred by any packet of the EF flow τi generated at time t meets: δi (t) ≤ h∈Pi (B h − 1), where B h denotes the maximum processing time at node h of any packet of flow not belonging to the EF class. By convention, B h − 1 = 0 if there is no such packets.
Property 1 can be extended to the general case by decomposing an EF flow in as many independent flows as needed to meet Assumption 8. To achieve that, the idea is to consider an EF flow crossing path Pi after it left Pi as a new EF flow. We proceed by iteration until meeting Assumption 8. We then apply Property 1 considering all these flows.
Notice that this bound can be optimized if we have additional information concerning flows not belonging to the EF class.
2.3. Determinism cost Let us consider the following example with six EF flows whose characteristics are given in Table 1. These flows visit
From the worst case analysis in [4], a sufficient condition to bound XEF (t) is given by: 2
Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS’05) 1526-7539/05 $20.00 © 2005 IEEE
four nodes. Flows not belonging to the EF class, denoted EF, represent a workload of 20% on each node. In this example, the worst case end-to-end response time of any EF flow is equal to 66 time units. Class Flow Ci Ti
EF
τ1 3 20
τ2 4 50
τ3 8 30
τ4 7 100
Assumption 10 We suppose that packet arrivals of a flow τi to a link ab also follow a Poisson process with parai i λi , where δab is given by eq.(1). meter λiab = δab Assumption 11 We also suppose at each link ab that EF flow packets arrive according to a Poisson process with parameter λEF ab .
EF
τ5 10 90
τ6 2 40
3 15
The service times for both EF and ally distributed and characterized by:
Table 1. Traffic parameters
• µEF ab : the average service rate of flow EF packets at the link ab. Each link ab can therefore be modelled by an M/G/1/./Head Of Line station. Packets of flow τi , i ∈ [1, n], are served with the highest priority over EF packets. Referred to [4], the Laplace transform the node so of i ∗ (s) is then journ time distribution for flow τi at ab, Sab given by:
∗ EF EF
i ∗
i ∗ (1−ρab ) s +λab 1− Bab (s) Sab (s) = Bab (s) n n
i ∗ s− λiab + λiab Bab (s)
3. Probabilistic approach In this section, we consider a study based on queuing theory to derive the end-to-end response time distribution for the set of real-time flows described in Section 1 by {τ1 , τ2 , ..., τn } aggregated over the EF class in the DiffServ/MPLS network. The assumptions used for this study are those given in Section 1 plus additional ones specific to the probabilistic approach.
i=1
Let si the end-to-end response time for a packet of flow τi and Si∗ (s) the Laplace transform of its probability density function. The end-to-end response time corresponds to the sum of the nodes response times crossed by the packet and the sum of the propagation delays between the different nodes. The random variables corresponding to these different durations being independent, we obtain:
Assumption 9 At network entries, the real-time flows arrive according to a Poisson process. Each flow τi is a Poisson process with parameter λi . In fact, the arrival process of the Internet traffic, at a packet scale, does not correspond to a Poisson process (On-off sources for example). However, it can be modeled by a Poisson process [5].
Q P Q P
Si∗ (s)
∗
i δab
= (L (s))a=1b=1
i S ab
∗
(s)
(3)
a,b∈[1..Q]
The network is composed of a set Q of edge and core routers interconnected by links [4]. According to Assumption 6, all the packets of a same flow τi go through the same path Pi . Hence, we define for each flow τi : =
i=1
(2)
EF ∗
i ∗ where Bab (s) and Bab (s) are respectively the Laplace transforms of flow τi packet service time at ab and the Laplace transform of flow EF packet service time at that link.
All the packets not belonging to the EF class will be referred by EF packets. EF is a virtual class defined in the probabilistic model to evaluate the non-preemptive effect of the node scheduler.
packets are gener-
• µiab : the average service rate of flow τi packets at the link ab.
The deterministic approach may lead to a bound that can be reached infrequently. A network dimensioning based on this bound can be expensive in terms of resources. Moreover, many applications do not require such guarantees. That is why we are interested in probabilistic QoS guarantees concerning the end-to-end response time. That is QoS is met with a given probability. An admission control, based on these results, can be derived.
i δab
EF
correspondwhere L∗ (s) is the Laplace transform of L, ing to the propagation delays between two nodes, and ∗ i S (s) is deduced from eq.(2). ab
1 if the link ab (node a to node b) belongs to Pi . 0 otherwise (1)
The end-to-end response time distribution si (t) is obtained by inspecting its Laplace transform given by eq.(3). 3
Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS’05) 1526-7539/05 $20.00 © 2005 IEEE
4. Admission control
5. Conclusion
The end-to-end response time distribution enables to determine, for a given configuration, the probability that a flow packet won’t stay in the network more than a given duration. Indeed, a packet belonging to the flow τi and arriving with a relative deadline Di won’t miss its deadline with the probability Psuccess (Di ) and will miss its deadline with the probability Pmiss (Di ) = 1 − Psuccess (Di ), where D Psuccess (Di ) = P [si < Di ] = 0 k si (t)dt and si (t) is the end-to-end response time distribution obtained by inspecting its Laplace transform.
In this paper, we have proposed a solution to provide quantitative end-to-end real-time guarantees for flows in the EF class of the DiffServ model, assuming that this class has the highest priority and packets are scheduled FIFO within the EF class. The EF class is well adapted for flows with real-time constraints such as voice or video flows. We have computed deterministic bounds on the end-to-end response time of any EF flow. This bound, obtained in the worst case scenarios, can be reached infrequently and leads to network overdimensioning. That is why we have developed mathematical models to evaluate the probability of meeting a specified end-to-end delay for any EF flow in the DiffServ/MPLS domain. The MPLS technology reduces forwarding delays because of simpler processing and allows to indicate in a label the service class of the packet.
If we consider the configuration described in Section 3, Table 2 gives the missing deadline probabilities for flow τ5 , which has the maximum service time, for different loads in class EF (10%, 20%, 30%) and the same load for class EF equal to 20%. We recall that delay bound obtained with the deterministic approach is equal to 66 time units. With the probabilistic approach, this bound is guaranteed with a probability of 6 · 10−4 for a load of 10%.
This study has shown that we can guarantee delays much smaller than the deterministic bound with a probability close to one. Moreover, this probabilistic approach yields to define an admission control based on a probabilistic guarantee of the required deadline. As a further work, we will study an Earliest Deadline First (EDF), scheduling policy within the EF class instead of FIFO to favor flows having small deadlines.
In fact, as a Poisson arrival process has been considered, the response time distribution cannot in any case equal zero. However, the network can guarantee a delay of 60 time units with a probability of 7.7 · 10−3 , a delay of 55 time units with a probability of 7.3 · 10−2 . These probabilities can be satisfying for some applications. UEF 10% 20% 30%
45 0.84 0.91 0.94
50 0.39 0.52 0.62
Di (ms) 55 60 0.073 7.7 · 10−3 0.17 3.3 · 10−2 0.26 8.8 · 10−1
References 66 6.1 · 10−4 5.3 · 10−3 1.8 · 10−2
[1] J. Bennett, K. Benson, A. Charny, W. Courtney, J. Le Boudec, Delay jitter bounds and packet scale rate guarantee for Expedited Forwarding, INFOCOM’2001, Anchorage, USA, April 2001.
Table 2. Deadline miss probability.
[2] K. Tindell, J. Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessors and Microprogramming, Euromicro Journal, Vol. 40, 1994.
A probabilistic admission control can be defined, it provides a probabilistic QoS guarantee to each accepted flow. A new EF flow τi is accepted if and only if:
[3] S. Baruah, R. Howell, L. Rosier, Algorithms and complexity concerning the preemptive scheduling of periodic real-time tasks on one processor, Real-Time Systems, 2, p 301-324, 1990.
• The QoS requested by flow τi can be met with a probability p computed from the flow characteristics (i.e. its arrival rate and deadline) according to the method presented previously in this Section.
[4] L. Azouz Saidane, P. Minet, S. Martin, I. Korbi, Deterministic and probabilistic QoS guarantees for the EF class in a DiffServ/MPLS domain, INRIA Research Report N 5622, July 2005.
• The probabilistic QoS of already accepted EF flows is not compromised by the acceptance of flow τi . A negotiation can take place between the admission control and the user submitting the new flow. For instance, if the user is not pleased with the probability computed, the admission control can propose other deadline values with the probabilities associated. The user selects the most appropriate deadline.
[5] T. Bonald, A. Prouti`ere, J. Roberts, Statistical performance guarantees for streaming flows using expedited forwarding, in Proc. of IEEE INFOCOM’2001, March 2001.
4
Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS’05) 1526-7539/05 $20.00 © 2005 IEEE
