Chakraborty, Gries. Supporting a low delay best-effort class in the presence of real-time traffic

Embedded Scribd iPaper - Requires Javascript and Flash Player
Supporting a Low Delay Best-Effort Class in the Presence of Real-Time Traffic
Samarjit Chakraborty∗ ETH Z¨ rich u Matthias Gries† UC Berkeley Lothar Thiele∗ ETH Z¨ rich u
Abstract
In this paper we propose a packet scheduler to provide a low delay service to best-effort packets without jeopardizing the delay bounds associated with real-time flows. We show that some of the well known service mechanisms for integrating soft real-time tasks into a hard real-time environment, such as the Total Bandwidth Server of Spuri and Buttazzo, turn out to be special cases of our scheme. Our experiments with realistic traffic, consisting of a mix of realtime flows such as voice and video and several best-effort flows show an average improvement of up to 45% in the delay experienced by the best-effort flows, without any realtime flows missing their deadlines.
in general, the need for such a low delay best-effort service class arises in the context of serving special packets carrying, for instance, network control information such as routing table updates. Another example of this class is sporadic http requests. Since the number packets belonging to such classes are usually very small, the overhead involved in designating a distinct flow for these packets and explicitly reserving a network bandwidth to serve them is very high. As a result, such packets are treated as best-effort packets but at the same time they have a short time-to-live. Our proposed scheduler although continues to treat such packets as best-effort packets, would guarantee that they are delivered as early as possible without jeopardizing the deadlines associated with real-time packets. The problem and its relation to previous work. The problem of integrating soft real-time or best-effort tasks into a hard real-time environment has very different manifestations and concerns in the context of processor scheduling and packet scheduling. Most of the real-time systems literature in the context of processor scheduling assume the hard real-time tasks to be periodic, with a specified period and a worst case execution requirement within each period. In several approaches based on executing the periodic tasks using a Rate Monotonic scheduling algorithm, the best-effort tasks are served using server mechanisms such as the Priority Exchange Server [11], the Sporadic Server [17], and the Deferrable Server [21]. Alternatively, slack stealing techniques under Rate Monotonic scheduling have been used in [7, 10, 22]. Algorithms for serving soft aperiodic tasks under EDF were proposed in [18, 19], and were extended in [20] and [4]. All of these above schemes are based on computing the remaining processor bandwidth after serving the periodic hard real-time tasks, and using this remaining bandwidth to schedule best-effort tasks. This remaining bandwidth (or utilization factor in the case of server mechanisms) is invariant over time and can therefore be specified as a single number. This is even the case when real-time tasks are not strictly periodic but their jobs are constrained by a minimum interarrival separation, or by other mechanisms different from the minimum interarrival time, such as those in Rate-Based Execution task models [9]. 1
1 Introduction
The problem of integrating jobs with soft deadlines into a hard real-time environment has been well studied in the real-time systems area (see [1] and [4] and the references therein). All the work on this problem, however, pertains to the processor scheduling domain, and the equivalent problem in the packet scheduling domain has remained largely ignored. In the packet scheduling area, there has been an extensive amount of work on advanced buffer management and scheduling algorithms to provide QoS guarantees to real-time continuous media traffic. But relatively little has been done to exploit these algorithms to better support besteffort traffic. In the presence of a mix of real-time and besteffort traffic, the most widely followed scheme blindly gives higher priority to the real-time packets and serves the besteffort packets only if no real-time packets are present at the scheduler. Motivated by the work done in the real-time systems area, in this paper we attempt to address this shortcoming by proposing a packet scheduling algorithm to provide a low delay service to best-effort packets without violating any of the delays associated with the real-time flows. Apart from improving the delays experienced by best-effort flows
∗ Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology (ETH) Z¨ rich, Gloriastrasse 35, CH-8092 Z¨ rich, u u Switzerland. E-mail: {samarjit, thiele}@tik.ee.ethz.ch † Department of Electrical Engineering and Computer Sciences, 231 Cory Hall, University of California, Berkeley, CA 94720-1770, USA. Email: gries@eecs.berkeley.edu
The setup in the case of packet scheduling is very different. Here packet arrivals from any real-time flow are constrained by arrival curves, which are described by general subadditive functions, each specifying the maximum amount of traffic that can arrive within any given time interval [6, 14]. For example, the (σ, ρ)-model [6] describes the worst case traffic from a flow j by a burst parameter σj and a long-term rate parameter ρj . This can be policed by a leaky bucket mechanism [23] and guarantees that within any time interval of length t, the maximum amount of traffic from flow j is bounded by σj + ρj t. If with each such real-time flow j, a deadline dj is associated with the interpretation that any packet from this flow has to be transmitted within dj time units after its arrival, then it is possible to calculate the link capacity used for serving all such real-time flows. However, the remaining link capacity which can be used for serving best-effort flows is not invariant over time (as in the case of the remaining processor bandwidth) and can not be specified as a single number. It turns out to be a function (over time interval lengths) dependent on the arrival curves and deadlines of the real-time flows. None of the known algorithms from the processor scheduling domain extend to this case in a straightforward manner. Our results. Our algorithm is based on EDF scheduling. The real-time flows are specified using their arrival curves and a deadline is associated with each such flow. We assume that there is a single best-effort flow. This might be an aggregated flow combining multiple flows (see Section 5 for further clarifications on this). The proposed algorithm assigns a deadline to each best-effort packet (on a packet by packet basis), and schedules this packet along with the other real-time packets using EDF. Central to our algorithm is this deadline assignment, and we prove that the overall system always remains schedulable and the deadline assignment is optimal (in the sense that with a shorter deadline, some packet might miss its deadline). The first algorithm we present, although optimal, is not feasible in practice since for any best-effort packet it requires the history of all the previous best-effort packets that arrived at the scheduler. However, based on this algorithm we propose several approximations which represent tradeoffs between the amount of computation that is required for each best-effort packet and the delay assigned to it. We show that the well known Total Bandwidth Server due to Spuri and Buttazzo [19] turn out to be one of these approximations. Our results with realistic traffic mixes consisting of audio, video, real-time transactions and best-effort flows like ftp, http and mail show between 25–45% improvements on the average in the delays experienced by the best-effort flows, without any of the real-time packets missing their deadlines. 2
Organization of the paper. In the next section we formally describe the model for characterizing real-time traffic in terms of arrival curves and deadlines; this forms the basis for all our algorithms. Section 3 motivates the design issues behind our algorithm and then describes our optimal algorithm, following which we present our different approximation schemes in Section 4. Our experimental results are presented in Section 5. Because of space restrictions all proofs have been omitted here; they can be found in [5].
2 Traffic Characterization
We denote by RT the set of real-time flows with traffic arrivals to the packet scheduler, and we have one besteffort flow which might be an aggregate of several besteffort flows. Packet arrivals from the real-time flows are constrained by arrival curves [6, 14] which specify an upper bound on the amount of traffic that can arrive from a flow within any specified time interval. Packet arrivals from the best-effort flow are not constrained in anyway, and are queued up, waiting to be served. If aj (t) denotes the traffic that arrives at the scheduler from a real-time flow j at time t, then Aj [t, t + τ ] = t+τ aj (t)dt denotes the traffic arrivals from the flow j in t the time interval [t, t+τ ]. The maximum traffic arrival from any flow j ∈ RT to the packet scheduler is bounded by a right-continuous subadditive traffic constraint function or arrival curve A∗ such that for all times t > 0 and for all j τ ≥ 0 we have: Aj [t, t + τ ] ≤ A∗ (τ ) j where A∗ (t) = 0 for all t < 0 and A∗ (t) ≥ 0 for t ≥ 0. j j There are usually two mechanisms to ensure that the traffic from a flow j entering the scheduler conforms to the traffic constraint function A∗ . The first is a traffic policer j placed at the entrance of a network node, which rejects any traffic from a flow j that does not comply to A∗ . The second j mechanism is a rate controller which temporarily buffers packets to ensure that the traffic from the flow j conforms to A∗ . Example constraint functions such as that given by j the (σ, ρ)-model [6] can be policed by a leaky bucket mechanism [23]. Each real-time flow j has an associated deadline dj , and any packet from this flow must be completely transmitted within dj time units after its arrival. We denote the deadlines assigned to (by our scheduling algorithm) the besteffort packets by δk , where δk is the (relative) deadline assigned to the k-th best-effort packet. If rk is the arrival time of this packet then its absolute deadline is equal to rk + δk . Throughout this paper, we refer to both absolute deadlines and relative deadlines, by the word deadline. It should be clear from the context which one we are referring to. Lastly, we denote the maximum packet size (from packets belonging to any flow) by smax , and the transmission rate of the scheduler is equal to one.
3 Optimal Deadline Assignment for BestEffort Packets
In this section we present our main algorithm. As mentioned before, it is similar to the Total Bandwidth Server of Spuri and Buttazzo [19] in the sense that best-effort packets are assigned a deadline on a packet-by-packet basis and are scheduled with the real-time packets using an EDF scheduler. However, the remaining link capacity available for serving best-effort packets is no longer a single number, but a function of the traffic constraint functions A∗ (described j in Section 2) and deadlines associated with the real-time flows. Therefore, the simple deadline calculation as done in the case of the Total Bandwidth Server does not extend to this case. A competing alternative to our proposed scheduler would be one based on the idea of proportional share resource allocation (such as the generalized processor sharing or any of its packetized versions) [14]. Given the arrival curves A∗ and the deadlines dj for each real-time flow, it j is possible to deduce the minimum link bandwidth required to serve each such flow such that its deadline is satisfied, and assign the remaining bandwidth to the best-effort flow. However, schedulers based on proportional share are primarily motivated by the need for fair sharing of surplus link bandwidth between different flows. On the other hand, our primary goal is to greedily allocate the maximum possible link bandwidth to the best-effort flow to improve its response time, subject to the constraint that the real-time packets do not miss their deadlines. In a deterministic setup, this is the only concern since real-time packets getting served much ahead of their designated deadlines do not improve the system performance. Our choice of EDF as a scheduling discipline is also motivated by the fact that it is known to have a larger schedulability region compared to generalized processor scheduling [8]. It has also been shown in [8] that the RSVP parameters in an IntServ framework [3] can be mapped to EDF reservations. This guarantees the conformance of our algorithm with IntServ, which happens to be one of the widely accepted service disciplines for guaranteeing real-time constraints in the Internet. Further, it was also shown in [2] that for supporting hybrid real-time multimedia applications, deadline based schemes are more appropriate compared to proportional sharing. In this section we make use of the traffic characterization defined in Section 2. Before describing our algorithm we need to define a few additional terms. For this, consider a mix of real-time and best-effort packets being served by the simple scheme in which real-time packets are served nonpreemptively using EDF, and a best-effort packet is served only when no real-time packets are present at the scheduler. Then it can be shown using the results from [12] that the set of all real-time flows RT is schedulable if and only if for all 3
t ≥ min{dj | j ∈ RT }: t ≥ k∈RT A∗ (t − dk ) + smax . k Based on this result, we define the residual link capacity over any time interval of length t, available to serve the besteffort flow, by a function RRT (t) where RRT (t) = t − ( A∗ (t − dk ) + smax ) k
k∈RT
Recall from Section 2 that A∗ is the traffic constraint funck tion and dk is the delay associated with the real-time flow k. smax is the maximum packet length of packets belonging to any flow. We define ERT (t) to be the effective residual link capacity available within any time interval of length t to serve best-effort packets. This is given by ERT (t) = min RRT (t )
t ≥t
Based on these two functions and the specifications of the real-time flows, our scheme for assigning deadlines to the best-effort packets is given by Algorithm 1. Algorithm 1 Computing Deadlines for the Best-Effort Packets
Given a set RT of real-time flows and one aggregated best-effort flow. The residual link capacity RRT (t) to serve the best-effort flow, over any time interval of length t is RRT (t) = t − ( k∈RT A∗ (t − dk ) + smax ). k Effective residual link capacity ERT (t) = mint ≥t RRT (t ). Computing the deadline δn of the n-th best-effort packet: The n-th best-effort packet arrives at time rn and has a transmission time of wn n δn = min{t | ERT (t) ≥ wn } for i = 1 to n − 1 do n−i n δn = min{t | ERT (t) ≥ j=n−i wj } − (rn − rn−i ) end for
i δn = max{δn | i = 1, 2, . . . , n}
Theorem 1 states that with the deadline assignment given by Algorithm 1, the order in which an EDF scheduler serves them is the same as the order in which they arrive at the scheduler. Therefore, Algorithm 1 does not disrupt the order of the best-effort packets. Theorem 1 For any n ≥ 1, if δn and δn+1 are the deadlines assigned to the n-th and the (n + 1)-th best-effort packets by Algorithm 1 then rn+1 + δn+1 > rn + δn . To informally explain Algorithm 1, we introduce a family of functions αn (t), n = 1, 2, . . ., where αn (t) denotes the service demand within any time interval of length t due to a sequence of best-effort packets 1, 2, . . . , n, ending with the n-th packet. It means that within any time interval of length t, a sequence of best-effort packets from the set ordered {1, . . . , n} and ending with packet n would require a total transmission time equal to αn (t) if they have to meet their assigned deadlines. Algorithm 1 assigns to each besteffort packet n the shortest possible deadline, maintaining the constraint that the curve αn (t) always lies below the effective residual link capacity curve ERT (t). We formally
state this idea below in Theorems 2 and 3. Theorem 2 states that with the deadline assignment due to Algorithm 1, the overall system (consisting of real-time and best-effort packets) still remains schedulable, and Theorem 3 states the optimality of the deadline assignment. Based on the above idea of service demand functions αn (t), if the first best-effort packet arrives at time r1 and is assigned a (relative) deadline δ1 (i.e. it has an absolute deadline equal to r1 + δ1 ), then within an interval of length δ1 the service demand due to this best-effort packet is equal to w1 . Hence α1 (δ1 ) = w1 , and α1 (δ) = 0 for all δ < δ1 . Now if the second best-effort packet arrives at time r2 and is assigned a deadline δ2 , then within an interval of length δ2 , the service demand is w2 and within an interval of length δ2 + r2 − r1 the service demand is w1 + w2 . These two constraints are captured in α2 (t), and the deadline δ2 is chosen so that α2 (t) for all values of t ≥ 0 lies below ERT (t). This procedure is followed for any subsequent packets. Therefore, for the n-th packet, the service demands within an interval of length: δn is wn , δn + rn − rn−1 is wn−1 + wn , . . . , δn + rn − r1 is w1 + . . . + wn . As before, δn is chosen by Algorithm 1 such that within any of these intervals the service demand is below the effective residual link capacity available within an interval.
α n (t)
α n+1 (t) rn+1 − (rn + δn ) wn+1 t δ n+1
α n (t)
t
(a)
(b)
Figure 1. Constructing the service demand curve
αn+1 (t) from the curve αn (t). (a) The service demand curve αn (t). (b) The service demand curve αn+1 (t).
best-effort packets are transmitted by their assigned deadlines. Theorem 3 If any best-effort packet is assigned a deadline smaller than that assigned by Algorithm 1, then some packet (either from a real-time or from the best-effort flow) might miss its deadline. It follows from the schedulability guarantee given by Theorem 2, and also the discussion above, that the deadlines assigned to the best-effort packets are dependent on their arrival rate. If too many best-effort packets arrive back-to-back and the effective residual link capacity is not too large to serve them, then the deadlines assigned to them grow larger and larger, but the real-time packets are never jeopardized. An overload situation created by best-effort traffic only increases their average response time. Lastly, it is clear that our scheme is never worse compared to the simple scheme of serving best-effort packets only when no real-time packets are present at the scheduler. Note that the deadline assignment for any best-effort packet requires the entire history of all the previous packets that arrived at the scheduler. As an implementation hint (which is as well obvious to note), we point out that this history can be reset whenever the scheduler is idle, i.e. there are no real-time or best-effort packets with already assigned deadlines waiting to be served. The next packet arriving after such a rest can be treated as the first best-effort packet. For any realistic traffic flow, such resets of the scheduler will be fairly common.
3.1 An Alternative Interpretation
If we list all the above constraints for each packet, we get: α1 (δ1 ) = w1 ; α2 (δ2 ) = w2 , α2 (δ2 + r2 − r1 ) = α2 (δ1 + (r2 + δ2 ) − (r1 + δ1 )) = w1 + w2 ; α3 (δ3 ) = w3 , α3 (δ3 + r3 − r2 ) = α3 (δ2 + (r3 + δ3 ) − (r2 + δ2 )) = w2 + w3 , α3 (δ3 + r3 − r1 ) = α3 (δ1 + (r2 + δ2 ) − (r1 + δ1 ) +(r3 + δ3 ) − (r2 + δ2 )) = w1 + w2 + w3 ; . . . It follows from the above list of constraints that, given the curve αn (t), and rn+1 , δn+1 , wn+1 , it is possible to construct the curve αn+1 (t) by shifting αn (t) horizontally by (rn+1 +δn+1 )−(rn +δn ), vertically by wn+1 , and appending a step function to it as shown in Figure 1. Note that the segment (in the middle) of length rn+1 − (rn + δn ) might be positive or negative in length. In the later case, a part of the last segment of αn (t) gets deleted. With this observation, Algorithm 1 can be alternatively interpreted as follows. Given the service demand curve αn (t), δn+1 is the smallest possible value assigned by Algorithm 1 such that the resulting curve αn+1 (t) lies below the curve ERT (t). With this deadline assignment the overall system remains schedulable, and with a deadline smaller than δn+1 some packet (either real-time or besteffort) might miss its deadline. This is stated in the following two theorems. Theorem 2 Given a set RT of schedulable real-time flows, under the deadline assignment for best-effort packets given by Algorithm 1, the set RT still remains schedulable and all 4
4 Approximating the Effective Residual Link Capacity
Algorithm 1 in spite of being optimal in terms of the response time experienced by best-effort packets, is infeasible for all practical purposes. This is because it requires maintaining the history of all the best-effort packets that arrived at the scheduler, to assign a deadline to the next packet. The reason for this is that the effective residual link capacity ERT (t) can in general be arbitrarily shaped. Combined with the fact that packet sizes can also be arbitrary, to fit the service demand functions αn (t) as tightly as possible
E RT
approx
E RT
approx
E RT γ
approx
s r
γ
t
(a)
δ
t
(b)
p’ p
t
(c)
Figure 2. Approximating ERT (t) with (a) a single line
passing through the origin, (b) a single line cutting t = δ, (c) a combination of two line segments of slope r and s (r < s).
packets 1, 2, . . . , n and (x, y) be the point on αn (t) which approx is closest to ERT (t) = γt. Then it follows from our discussion in Section 3.1 that the new coordinates of this point in αn+1 (t) become: (x+rn+1 +δn+1 −(rn +δn ), y + wn+1 ) For the system to be still schedulable, we require that: (x + rn+1 + δn+1 − (rn + δn ))γ ≥ y + wn+1
approx Since (x, y) was closest to ERT (t) = γt, if (x, y) lies below this line then all other points on αn (t) are also guaranteed to lie below it. Assuming that the system was schedulable with the deadline assignment for the n-th packet, i.e. xγ ≥ y, we have: (rn+1 + δn+1 − (rn + δn ))γ ≥ wn+1
below ERT (t), the full structure of αn (t) is required. The complexity of the algorithm can be reduced either by approximating the effective residual link capacity ERT (t) by a simple function, or by approximating the packet size to allow only a fixed number of distinct sizes. In this section we consider the former approach. It should be possible to derive the approximations based on later approach from the ideas that we present in this section. For the deadline assignment for any best-effort packet, the algorithms that we present in Sections 4.1 and 4.2 require the arrival times and deadlines of the previous packet only (in contrast to all the previous packets). The algorithm presented in Section 4.3 is more involved and requires the history of a bounded number of packets, and not all. Each of these algorithms represent a tradeoff between the complexity involved in the deadline assignment and the length of the deadline assigned.
or, δn+1 ≥ wn+1 /γ + (rn + δn ) − rn+1 (2) From inequalities (1) and (2), we get the deadline assignment for the n + 1-th best-effort packet to be: δn+1 = wn+1 /γ + max{0, (rn + δn ) − rn+1 } Therefore, rn+1 + δn+1 = wn+1 /γ + max{rn+1 , rn + δn } which is exactly the same as the deadline assignment in the case of the Total Bandwidth Server. This follows from the fact, that our straight line with slope γ approximating the effective residual link capacity is equivalent to a server with an utilization factor of γ. The Total Bandwidth Server therefore reduces to a special case of our Algorithm 1.
4.1 With a Straight Line Through the Origin
In this section we approximate the effective residual link capacity ERT (t) after serving the set of real-time flows RT , by a single straight line of slope γ passing through the origin (see Figure 2(a)). To satisfy the schedulability condition given by Theorem 2, the slope γ is chosen to be the largest possible value such that this line lies below the exact ERT (t) calculated from the traffic constraint functions (or arrival curve) A∗ (t) of the real-time flows j j ∈ RT , and the maximum packet size smax . Therefore, γ = max{γ | γ t ≤ ERT (t) ∀t ≥ 0}. The deadlines of the approx best-effort packets are now computed with ERT (t) = γt as the effective residual link capacity available for transmitting the best-effort flow. We show that under this approximation, the deadline of any best-effort packet can now be optimally calculated by using parameters (such as arrival times and deadlines) belonging to the previous packet only. This is in contrast to our exact algorithm which required the arrival times of all the previous best-effort packets. Consider the (n + 1)-th best-effort packet which arrives at the time rn+1 and has a transmission time equal to wn+1 . It follows from Algorithm 1 that for the system to be schedulable the deadline assigned to this packet should satisfy: δn+1 ≥ wn+1 /γ (1) Let αn (t) be the service demand due to the best-effort 5
4.2 With a Straight Line Cutting t = δ
Here we approximate the effective residual link capacity ERT (t) again by a single straight line with slope γ, but crossing the t-axis at t = δ instead of passing through the origin as in our last approximation (see Figure 2(b)). Therefore, it reduces to our last case if δ = 0. The approximate effective residual link capacity is now given by:
approx ERT (t) =
0 (t − δ)γ
if t ≤ δ if t > δ
approx The values γ and δ are chosen such that ERT (t) ≤ ERT for all t ≥ 0. Now consider the (n + 1)-th best-effort packet that arrives at time rn+1 and has a transmission time of wn+1 . If δn+1 is the deadline assigned to this packet then we require that:
δn+1 ≥ δ + wn+1 /γ
(3)
Let, as before, αn (t) be the service demand due to the best-effort packets 1, 2, . . . , n and (x, y) be the point on approx αn (t) which is closest to ERT . For the new coordinate
approx of (x, y) in αn+1 (t) to lie below ERT , after the deadline assignment δn+1 to the (n + 1)-th packet, we require:
Algorithm 2 Computing the approximate deadline δn+1 of the
(n + 1)-th best-effort packet based on approximating ERT (t) by a combination of two line segments
n Given S≤p = set of all packets {i | i ≤ n and (δn + rn − ri ) ≤ p}. n Given k>p where, among the set of packets that DO NOT belong to S≤p , k>p n is the k-th packet (1 ≤ k ≤ n), such that the point (δn +rn −rk , j=k wj ) on αn (t) is closest to the approximate effective residual link capacity curve approx ERT (t). The (n + 1)-th best-effort packet arrives at time rn+1 and has a transmission time of wn+1 . approx /∗ Compute the minimum deadline to fit αn+1 (t) below ERT (t) ∗/ approx Let δmin = min{t | ERT (t) ≥ wn+1 } n for all i ∈ S≤p do approx i Let δ = min{t | ERT (t) ≥ j=n+1 wj } − (rn+1 − rj ) if δ > δmin then δmin = δ end if end for δn+1 = δmin approx /∗ Find if a new point beyond t = p becomes closer to ERT (t) ∗/ n for all i ∈ S≤p do if (rn+1 + δn+1 − ri ) > p then n n S≤p = S≤p \{i}
(x + rn+1 + δn+1 − (rn + δn ) − δ)γ ≥ y + wn+1 Assuming that the system was schedulable with the deadline assignment of the n-th packet, i.e. (x − δ)γ ≥ y, we have: (rn+1 + δn+1 − (rn + δn ))γ ≥ wn+1 or, δn+1 ≥ wn+1 /γ + (rn + δn ) − rn+1 From inequalities (3) and (4) we have, δn+1 = wn+1 /γ + max{δ, (rn + δn ) − rn+1 } (4)
4.3 With a Combination of Two Line Segments
To more accurately approximate the effective residual link capacity, in this section we approximate it using a combination of two line segments (instead of one as in the previous cases), one of slope r passing through the origin and the second of slope s (s > r). The line segments intersect at a point whose t-coordinate is equal to p (see Figure 2(c)). Hence, it is given by:
approx ERT (t) =
compared to (δn+1 + rn+1 − rk>p , if end if end for
if (δn+1 + rn+1 − ri ,
n+1 j=i
approx wj ) is closer to the ERT (t) curve n+1 j=k>p
wj ) then k>p = i end
rt (t − p )s
if t < p if t ≥ p
/∗ Update the set of points on αn+1 (t) which lies to the left of t = p ∗/ if δn+1 ≤ p then n+1 n S≤p = S≤p ∪ {n + 1} else n+1 n S≤p = S≤p end if
The t-intercept p of the line with slope s can be calculated approx to be equal to p − pr/s. ERT reduces to the case in Section 4.1 if r = s, and to the case in Section 4.2 if r = 0 and p = δ. As before, r, s and p are chosen such that approx ERT (t) ≤ ERT for all t ≥ 0. Algorithm 2 gives the deadline assignment under this approximation. In contrast to the previous two algorithms, it requires the history of all the packets which constitute the portion of the service demand curve αn (t) that lies to the left of t = p. This algorithm is based on the idea of maintaining the curve αn (t) for any n only till the point t = p. Beyond t = p only the point which is closest to approx the curve ERT (t) is maintained. With the (n + 1)-th packet, the deadline δn+1 is chosen such that the part of αn (t) that lies to the left of t = p still continues to be beapprox low ERT (t) in αn+1 (t), and the point on αn (t) which approx is closest to ERT (t) and lies to the right of t = p also approx continues to lie below ERT (t). Because of the horizontal shift of αn (t) due to the (n + 1)-th packet, some points on αn (t) which were to the left of t = p would now cross approx this point and become the new nearest point to ERT (t) beyond t = p. 4.3.1 Approximating the Deadline In the last section, the deadline assignment for any besteffort packet required the arrival and the transmission times 6
of multiple previous packets. More precisely, all the packets which constitute the portion of the service demand curve αn (t) which was to the left of t = p (i.e. αn (t) for t < p). This was in contrast to our previous two approximation schemes where the deadline calculation for any packet required the arrival time and deadline of only one previous packet. While in many cases the number of packets that constitute the portion of the service demand curve lying on the left of t = p can be small (and in any case it is bounded), there might be situations where the number of such packets are very large. In the later case, computing the deadline of an incoming best-effort packet will involve an amount of computation and storage requirement which might be infeasible in practice, as in the case of our exact algorithm in Section 3. In this section, apart from approximating the effective residual link capacity ERT (t) using a combination of two line segments, we also approximate the (optimal) deadline approx that can be assigned using ERT (t) as the effective residual link capacity. Since we want to guarantee schedulability, the deadline assigned to any best-effort packet will now be greater than or equal to the deadline assignment in Secapprox tion 4.3 using ERT (t) as the effective residual link capacity. Our approximation is based on the idea of assuming that the service demand curve αn (t) at all points of time co-
E RT
approx
s r wn δn t α n (t)
Figure 3. Approximating the service demand curve αn (t) approx for all n, by assuming that it coincides with ERT (t) incides exactly with the approximate effective residual link approx capacity ERT (t). This is shown in Figure 3. If δn+1 is the deadline assigned to the n+1-th best-effort packet, then any point (x, y) on the αn (t) will be shifted to the point (x , y ) on αn+1 (t) where (x , y ) is given by: (x + rn+1 + δn+1 − (rn + δn ), y + wn+1 ) For the point (δn+1 , wn+1 ) in αn+1 (t) to lie below approx ERT (t), the following must hold: δn+1 ≥ wn+1 /r (wn+1 − pr)/s + p if wn+1 < rp if wn+1 ≥ rp (5)
Algorithm 3 Approximating the deadline δn+1
The (n + 1)-th best-effort packet arrives at time rn+1 and has a transmission time of wn+1 . approx The effective residual link capacity is given by ERT (t). if (wn + wn+1 ) ≥ rp then if wn+1 < rp then
w wn +wn+1 δn+1 = max{ n+1 , + r s else /∗ i.e. if wn+1 ≥ rp ∗/ wn +wn+1 δn+1 = + (rn − rn+1 ) s
thirds of the link capacity. The single aggregated best-effort flow is obtained from three additional non real-time flows (NRT) which fairly share the residual link capacity by passing through a Weighted Fair Queuing (WFQ) based scheduler before our deadline assignment for best-effort traffic is applied. A detailed description of this mechanism along with the traffic flows, their corresponding link bandwidth requirements, and the approximations used for the deadline assignment of best-effort traffic can be found in Sections A and B of the appendix. The results for the maximum and the average delay experienced by packets of the different flows are given in the Tables 1 and 2. The results from our algorithms are compared with the standard scheduling discipline where besteffort packets are injected only when the EDF scheduler is idle (i.e. there is no backlog from real-time flows). We have simulated the network node through which the traffic flows are passing, for a period of six minutes, which corresponds to about 5 × 105 processed packets. The first column shows the results from the standard best-effort (BE) scheme. This column is used as a reference for a comparison with our two approximations. The second column states the results for a deadline assignment for best-effort traffic using our simple approximation of the effective residual link capacity by a shifted straight line (from Section 4.2). The third column shows the delay values corresponding to the more involved approximation using two line segments (from Section 4.3).
flow class RT transactions RT video RT voice NRT ftp NRT http NRT mail standard BE scheme 2.11 / 100% 3.48 / 100% 1.31 / 100% 21.95 / 100% 21.29 / 100% 28.82 / 100% shifted line approx. 3.36 / 159% 9.95 / 286% 1.31 / 100% 14.25 / 65% 16.14 / 76% 22.84 / 79% two line approx. 5.73 / 272% 13.97 / 401% 2.54 / 194% 7.56 / 34% 11.14 / 52% 16.69 / 58%
(rn − rn+1 ) + p −
pr s }
+ p − pr s end if else /∗ if (wn + wn+1 ) < rp ∗/ w δn+1 = n+1 + max{0, (rn + δn ) − rn+1 } r end if
Table 1. Maximum delay (in msec) experienced by packets from the different flows within a 360sec period.
flow class RT transactions RT video RT voice NRT ftp NRT http NRT mail standard BE scheme 0.77 / 100% 1.52 / 100% 0.53 / 100% 2.50 / 100% 2.61 / 100% 3.61 / 100% shifted line approx. 0.86 / 117% 1.83 / 120% 0.53 / 100% 1.87 / 75% 1.93 / 74% 2.28 / 63% two line approx. 1.00 / 130% 1.88 / 124% 0.62 / 117% 1.73 / 69% 1.78 / 68% 1.97 / 55%
Since all points on αn (t) get displaced by the same amount in αn+1 (t), the deadline δn+1 should be large enough to guarantee that the point (δn , wn ) on αn (t) when approx shifted to a point in αn+1 (t), lies below ERT (t). This, along with inequality(5) would guarantee that αn+1 (t) lies approx approx below ERT (t) (it follows from the fact that ERT (t) is convex, since s ≥ r). Such a deadline assignment is given by Algorithm 3. Following this approach, for the deadline assignment of the (n + 2)-th packet, αn+1 (t) is assumed to exactly coapprox and the same steps as before are folincide with ERT lowed.
Table 2. Average delay (in msec) experienced by packets
from the different flows within a 360sec period.
5 Experimental Results
In this section we describe our results from simulations modeling a 10MBit/sec access link with six different traffic classes. Three real-time (RT) flows require about two 7
From the simulations it is obvious that a noticeable benefit can be gained even from the application of the very simple linear approximation of the effective residual link capacity that was presented in Section 4.2 to improve the response time for best-effort traffic. If we are able to afford the more involved approximation using two segments, then further improvement in the delays experienced by the best-effort traffic can be achieved. From the results, it is also possible to recognize that the real-time traffic with the most loose deadline (RT video) experiences the largest slow
x 10
-2
a)
plain best effort + EDF scheme
end-to-end packet delay [sec]
NRT ftp flow RT video flow
-2
x 10
b)
approximation with a single segment
NRT ftp flow
c)
approximation with two segments
RT video flow
RT video flow
simulation time [sec]
x 10
2
simulation time [sec]
x 10
2
Figure 4. Comparison of the delay experienced by two (out of the six) selected flows using our different approximation schemes for best-effort service. The delays experienced by a RT and a NRT flow using (a) the standard scheduling discipline of injecting NRT packets only when no RT packets are present at the scheduler, (b) our approximation scheme in Section 4.2, (c) our approximation scheme in Section 4.3. Note the gradual improvement in the delay experienced by the NRT flow from (a) to (c). The deadline of the RT flow (equal to 30 msec) is always met. down. Of course, in spite of the injection of the best-effort traffic with deadlines into the EDF scheduler, none of the deadlines associated with the real-time traffic are missed. The representations of the simulation trace in Figures 4 and 5 underpins the positive effect of our algorithm on the responsiveness for the non real-time flows. For readability reasons, only two selected flows are displayed. Note that the maximum delay experienced by some of the best-effort traffic improves by almost 65%, whereas the average delay improves by almost 45% in some cases. In the case of best-effort flows like sporadic http requests such benefits can be immediately perceived, proving the effectiveness of our scheduler. best-effort traffic can also be applied to this case by calculating the effective residual link capacity based on the schedulability test of SCED (eq. (14) in [15]). In the same way it is possible to refine the definition of fair shares for best-effort flows by using the Fair Service Curve approach in [13].
References
[1] L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Proc. 19th IEEE RealTime Systems Symposium, pages 4–13. IEEE Computer Society Press, 1998. [2] L. Abeni, G. Lipari, and G. Buttazzo. Constant bandwidth vs proportional share resource allocation. In Proc. IEEE International Conference on Multimedia Computing and Systems, volume 2, pages 107–111, 1999. [3] B. Braden, D. Clark, and S. Shenker. Integrated Services in the Internet architecture: an overview. Request for Comments 1633, Internet Engineering Task Force (IETF), June 1994. [4] G. Buttazzo and F. Sensini. Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments. IEEE Transactions on Computers, 48(10):1035– 1052, October 1999. [5] S. Chakraborty, M. Gries, and L. Thiele. Supporting a low delay best-effort class in the presence of real-time traffic. Technical Report TIK 131, ETH Z¨ rich, 2002. u [6] R. Cruz. A calculus for network delay, Part I: Network elements in isolation. IEEE Transactions on Information Theory, 1991. [7] R. Davis, K. Tindell, and A. Burns. Scheduling slack time in fixed priority preemptive systems. In Proc. Real-Time Systems Symposium, pages 222–231, 1993.
6 Conclusions
All the algorithms presented here exploit the inherent mobility (in time) of real-time packets with deadlines relatively far in the future to inject best-effort packets into the scheduler without violating any real-time deadlines. Thus, we reduce the delay experienced by non real-time flows since we do not require the EDF scheduler to be idle before best-effort traffic is eligible for service. Our experiments used a combination of WFQ and EDF schedulers. WFQ was used to fairly distribute the remaining link bandwidth among the different best-effort flows, and EDF was used as an overall scheduling strategy to benefit from its larger schedulability region compared to WFQ. We are aware of improved EDF-based scheduling disciplines such as service curve-based EDF (SCED [15]) and would like to point here that our deadline assignment for 8
x 10
-2
a)
plain best effort + EDF scheme
NRT ftp flow
end-to-end packet delay [sec]
RT video flow
x 10
-2
b)
approximation with a single segment
NRT ftp flow
c)
approximation with two segments
NRT ftp flow
RT video flow
RT video flow
simulation time [sec]
simulation time [sec]
Figure 5. Comparison of the delay experienced by the two selected flows shown in Figure 4. Here a small excerpt from the
simulation trace given in Figure 4 has been shown. [8] L. Georgiadis, R. Gu´ rin, V. Peris, and K. N. Sivarajan. Efe ficient network QoS provisioning based on per node traffic shaping. IEEE/ACM Transactions on Networking, 4(4):482– 501, Aug. 1996. [9] K. Jeffay and S. Goddard. Rate-based resource allocation models for embedded systems. In Proc. 1st Workshop on Embedded Software (EMSOFT), LNCS 2211, pages 204– 222. Springer-Verlag, 2001. [10] J. Lehoczsky and S. Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems. In Proc. Real-Time Systems Symposium, pages 110–123, 1992. [11] J. Lehoczsky, L. Sha, and J. Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proc. Real-Time Systems Symposium, pages 261–270, 1987. [12] J. Liebeherr, D. Wrege, and D. Ferrari. Exact admission control for networks with a bounded delay service. IEEE/ACM Transactions on Networking, 4(6):885–901, 1996. [13] T. S. E. Ng, D. Stephens, I. Stoica, and H. Zhang. Supporting best-effort traffic with Fair Service Curve. In GLOBECOM’99, pages 1799–1807, Dec. 1999. [14] A. Parekh and R. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Transactions on Networking, 1(3):344–357, 1993. [15] H. Sariowan, R. Cruz, and G. Polyzos. SCED: A generalized scheduling policy for guaranteeing Quality-ofService. IEEE/ACM Transactions on Networking, 7(5):669– 684, Oct. 1999. [16] S. Shenker and J. Wroclawski. General characterization parameters for integrated service network elements. Request for Comments 1633, Internet Engineering Task Force (IETF), Sept. 1997. [17] B. Sprunt, L. Sha, and J. Lehoczsky. Aperiodic task scheduling for hard real-time systems. Real-Time Systems, 1:27–60, 1989. [18] M. Spuri and G. Buttazzo. Efficient aperiodic service under earliest deadline scheduling. In Proc. IEEE Real-Time Systems Symposium, 1994. [19] M. Spuri and G. Buttazzo. Scheduling aperiodic tasks in dynamic priority systems. Real-Time Systems, 10(2):179– 210, 1996. [20] M. Spuri, G. Buttazzo, and F. Sensini. Robust aperiodic scheduling under dynamic priority systems. In Proc. 16th IEEE Real-Time Systems Symposium, pages 210–221, 1995. [21] J. Strosnider, J. Lehoczsky, and L. Sha. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments. IEEE Transactions on Computers, 44(1):73–91, 1995. [22] T.-S. Tia, J.-S. Liu, and M. Shankar. Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems. Real-Time Systems, 10(1):23–43, 1996. [23] J. Turner. New directions in communications (or which way to the information age?). IEEE Communications Magazine, 25(8):8–15, 1986.
A Arrival Curves and Scheduling Parameters
The traffic generators used for our simulations greedily generate packets as soon as they comply to a given TSpecconstrained [16] arrival curve (as sketched in Figure 6). The parameters for our set of flows are given in Table 3. We use three real-time and three non real-time flows. The realtime transactions class resembles traffic with a low bandwidth but hard deadline requirement to communicate with bandwidth brokers, bank applications, etc. Contrary to that, the video class models a high-bandwidth video with frame sizes considerably larger than the maximum packet length of 1536 Byte. A particular burstiness is caused by varying frame lengths due to predictive inter- or intraframe coding. Finally, the real-time voice class aggregates a couple 9
of constant-bit-rate voice sources. The three non real-time classes can also be distinguished by varying burstiness and bandwidth requirements. For instance, the NRT mail class forms the counterpart of the RT transactions class in the set of non real-time flows since the mail class also generates moderately average rates.
α M + pt
flow class RT transactions RT video RT voice flow class NRT ftp NRT http NRT mail
b [byte], r [byte/sec] 45000, 50000 15000, 600000 300, 150000 b [byte], r [byte/sec] 30720, 150000 50000, 100000 12288, 46080
M [byte], p [byte/sec] 700, 150000 1536, 800000 100, 250000 M [byte], p [byte/sec] 1536, 250000 1536, 150000 1536, 100000
deadline [msec] 20 30 5 WFQ weight 0.5 0.2 0.1
Table 3. TSpec description of the traffic flows (see Figure 6 for a description of the parameters).
b + rt
service
[byte/sec]
1.8 2 x 10
5
b
M
Figure 6. Arrival curve α(t) of a TSpec-constrained flow.
1.2
Table 3 also specifies the deadlines associated with realtime flows. Our main EDF scheduler is hierarchically combined with a WFQ scheduler into which the different non real-time flows are first fed (see Figure 7). The WFQ scheduler as a result creates an ordering of the packets belonging to these flows and generates an aggregated best-effort flow. Our deadline assignment for best-effort traffic is applied to packets belonging to this aggregated flow, after the WFQ scheduler has determined the ordering. These packets are then injected into the EDF part of the scheduler where they are scheduled along with the other real-time packets. The effective residual link capacity is therefore shared in a fair manner by scheduling the non real-time flows with the WFQ-based scheduler. The corresponding weights used by the WFQ scheduler are also stated in Table 3. The minimum
real-time (RT) flows packets
non real-time (NRT) flows
Figure 7. Hierarchical configuration of RT and NRT
schedulers.
packet length is bounded by 40 bytes. The link capacity is set to 10 MBit/sec to model a next-generation access link from a home or an office to a service provider. Based on the parameters in Table 3 we can now derive the effective residual link capacity as shown in Figure 8. In addition, the two different approximations of the effective residual capacity used for our simulations are also sketched in this figure.
B
Traffic Generators
Since our sources generate traffic greedily according to TSpec descriptions, some more parameters are required so that we do not quickly end up in the steady section of the TSpec curve but see some burstiness at the output. We 10
¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢  ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢  ¢¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ ¢¡  ¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¡   ¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡                                     ¢¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡¢   ¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ ¢¡  ¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡ ¡                                        ¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢¢¡  ¢ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡  ¢ ¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¢¡¡   ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢  ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¢¡ ¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡  
TSpec
link service
1.6
sum of reservations by real-time flows
t
1.4
effective residual link capacity
1
0.8
0.6
0.4
two line approximation:
358530 byte/sec and 450000 byte/sec slopes, change at 0.463 sec
0.2
shifted line approximation:
0.015 sec shift, 370530 byte/sec slope
0.1 0.2 0.3 0.4 0.5
0 0.0
time interval length [sec]
Figure 8. Approximations for deadline assignment to best-effort packets. therefore consider periods when a generator is idle and not producing any packets and when the generator is enabled. We call the corresponding intervals burst length and burst spacing periods respectively. The parameters used for our simulations are given in Table 4. N (avg, dev) stands for a normal distribution with mean avg and standard deviation dev and U (l, r) denotes a uniform distribution in the interval [l, r). Packet lengths are rounded to the next integer. Packet lengths below 40 Byte are rounded up to 40 Byte and lengths above 1536 Byte are round off to 1536 Byte. The fact that we use sources with a mean packet length above the maximum packet length leads to sequences of packets with maximum length followed by just a single or a couple of packets of smaller length. This behavior imitates the transmission of files larger than the maximum packet length which are therefore distributed over several packets. Moreover, we allow all non real-time flows to excessively use the maximum packet length to increase the negative effect on real-time flows due to non-preemptive link scheduling.
flow class RT transactions RT video RT voice NRT ftp NRT http NRT mail packet length [byte] N (300, 50) N (1700, 200) 100 N (1700, 200) N (1700, 200) N (1700, 200) burst length [ms] U (5, 35) U (50, 100) U (2, 4) U (10, 700) U (50, 400) U (5, 50) burst spacing [ms] U (50, 800) U (10, 20) U (6, 10) U (100, 300) U (50, 200) U (100, 300)
{
...
WFQ
EDF
outgoing link
{
...
best-effort deadline assignment
Table 4. Parameters used for generating traffic.