No CrossRef data available.
A TWO-NODE JACKSON NETWORK WITH INFINITE SUPPLY OF WORK
Published online by Cambridge University Press: 23 March 2005
Abstract
We consider a Jackson network with two nodes, with no exogenous input, but instead an infinite supply of work at each of the nodes: Whenever a node is empty, it processes a job from this infinite supply. We obtain an explicit expression for the steady state distribution of this system, as an infinite sum of product forms.
Information
- Type
- Research Article
- Information
- Probability in the Engineering and Informational Sciences , Volume 19 , Issue 2 , April 2005 , pp. 191 - 212
- Copyright
- © 2005 Cambridge University Press
1. INTRODUCTION
We consider a Jackson network with two nodes (Fig. 1), numbered i = 1,2. Processing times at the nodes are independent, and those at node i are exponentially distributed with rates μi, and jobs completing processing at node i move to node 3 − i with probability pi and leave the system otherwise. There is no exogenous input to the system. However, whenever one of the nodes is empty, it will process a job from an infinite supply of jobs. This system can be described by a two-dimensional Markov jump process, X(t) = (X1(t),X2(t)), the state space of which consists of the pairs of nonnegative integers (n1,n2), where n1 indicates the number of jobs at node 1 and n2 indicates the number of jobs at node 2. Whenever ni > 0, node i will process one of the jobs at the node. This introduces the transitions
Whenever node i is empty, it will process a job from its infinite supply, at the same rate μi, and upon completion, this job will move to the other node with probability pi and leave the system with probability 1 − pi. This introduces the additional transitions:
Note that jobs from the infinite supply of each buffer are indistinguishable from jobs queued at the nodes, but queued jobs have preemptive priority over jobs in the infinite supply. The transitions (1.2) constitute arrivals into the system.
A two-node Jackson network with infinite supply of work.
The two nodes in this system are processing jobs all the time. Hence, there are four independent Poisson streams in this system: Jobs depart the system in two Poisson streams with rates μ1(1 − p1) and μ2(1 − p2), and jobs arrive at the two nodes in two Poisson streams, with rates μ1 p1 and μ2 p2. The queue at node i therefore behaves as an M/M/1 queue, with arrival rate μ3−i p3−i and service rate μi. The system is stable if
with marginal steady state distributions
However, the queue lengths at the two nodes in steady state are not independent; the joint steady state distribution is not a product form:
In this note, we derive explicit expressions for the joint steady state distribution of the two-node system. We use the compensation approach, developed by Adan, Wessels, and Zijm [2] to obtain an expression that is an infinite sum of product forms.
This two-node Jackson network with an infinite supply of work describes quite a useful model of cooperative service by two servers. Consider jobs that require a sequence of tasks; the first task is performed by one of the servers and the remaining tasks are performed by alternating servers. Server i performs tasks at rate μi, and the job then requires an additional task with probability pi, or else it is complete and leaves the system. We assume that each of these servers has an infinite supply of jobs to start. However, each server gives preemptive priority to tasks that it received from the other server. Each server then has a queue of jobs that are “in process” and the analysis of these queues tells us how much storage for WIP (work in process) is needed and what is the cycle time of a job from first task to completion.
The concept of infinite supply of work, in contrast to the usual queuing assumption that jobs arrive randomly, is in fact very common in many systems: Whenever a server is expensive and it is desired not to keep it idle, one tries to monitor the server and control the inputs, so that the server never runs out of work. This is the case for an expensive machine, a highly trained server, or a high-performance communication link. In each case, work is shunted to such servers to prevent them from idling.
As we will see in Section 3, infinite-supply Jackson nodes provide much better performance than standard Jackson nodes.
Multiclass queuing networks with infinite supplies of jobs in some of the classes, also called infinite virtual queues, were introduced by Adan and Weiss [1], Kopzon and Weiss [8,9], and Weiss [12,13,14]; see also Levy and Yechiali [10]. They represent monitored control over job arrivals, as it often exists in manufacturing and communication systems. Jackson networks are described by Jackson [6] and Kelly [7]. Weiss [14] has discussed Jackson networks with virtual infinite buffers: He has derived flow rates, stability conditions, and partial steady state distributions. This work is also closely related to the results of Goodman and Massey [5]. The analysis in the current article provides one example of such networks, which is highly tractable.
2. MAIN THEOREM
The two-node Jackson network with an infinite supply of work is described by a Markov jump process moving on the two-dimensional nonnegative integer grid. The Markov process performs a two-dimensional simple random walk on the positive-integer grid, with transitions only to neighboring states, and with reflecting barriers on the horizontal and vertical axes. Furthermore, in the interior of the positive quadrant, the random walk has no transitions to the north, the northeast, and the east directions. The transition rates for this random walk are described in Figure 2.
Transition rates for the two-node system.
For such Markov jump processes, it is possible to obtain a closed-form expression of the steady state distribution, by the compensation method developed in the work of Adan et al. [2]. The random walk in Figure 2 has the property that the transition rates at the vertical boundary n1 = 0,n2 > 0 and the horizontal boundary n1 > 0,n2 = 0 are projections of the ones in the interior n1,n2 > 0. Boxma and van Houtum [3] showed that this property considerably simplifies the expression of the steady state distribution. See also [11].
The main steps in the derivation of the steady state probabilities are as follows: The balance equations for the interior are satisfied by product form expressions αn1βn2, where α and β are solutions of a quadratic equation Q(α,β) = 0. Solutions of this form do not as a rule satisfy the equations for the horizontal or vertical boundaries. However, it is possible to find compensating product forms such that the linear combination
satisfies the balance equations for the interior and the vertical boundary of the quadrant. Similarly, it is possible to find compensating product forms such that
satisfies the balance equations for the interior and the horizontal boundary of the quadrant. Then, starting with a product form αn1βn2 with α and β satisfying Q(α,β) = 0, one can construct an infinite linear combination by adding product forms to alternately compensate for the horizontal and vertical boundary. The resulting solution formally satisfies all of the balance equations. One then needs to choose the parameters of the product forms and their coefficients such that the solution is absolutely convergent. This method does indeed work for our system.
In Section 4, we will present the detailed derivation of the steady state distribution, without invoking the results in [2,3]. In the derivation, we make use of the steady state marginal distributions (1.3). This yields a particularly elegant and simple expression:
Theorem 2.1: The steady state distribution of the two-node Jackson network with infinite supply of work, when ρ1,ρ2 < 1, is given, for all (n1,n2) ≠ (0,0), by
where, for k ≥ 1,
with initially α0 = β0 = 1,α1 = ρ1, and β1 = ρ2. The steady state probability P(0,0) is
The closed-form expression in Theorem 2.1 immediately leads to similar expressions for the distribution of the total number in the system and for the (factorial) moments of the queue lengths at node 1 and 2. Let Xi denote the queue length of node i in steady state. Then we have the following:
Corollary 2.2:
(i) For all n > 0,
(ii) For all m,n ≥ 0 and m + n > 0,
Note that exact formulas for αk and βk can be obtained from the difference equation (2.2) but are not particularly illuminating. The asymptotic behavior of αk and βk is derived in Proposition 4.14.
3. COMPARISON WITH STANDARD JACKSON NETWORK
We compare our two-node system with an infinite supply of work and a standard Jackson network, with exogenous random inputs. Throughout this section we label our system as “∞-supply” and the Jackson network with random exogenous input as “standard.” For the comparison, we consider two nodes in a standard Jackson network as shown in Figure 3. Here, we have two nodes with the same processing rates μi, and with the same probabilities 1 − pi to complete a job, which then departs the system. The total inputs into the nodes are at rates λi, and they consist of both exogenous arrivals and feedback from other nodes. Recall that the input streams are not Poisson. The outflow in steady state is also at rate λi and includes a Poisson output stream of departures from the system at rate λi(1 − pi). As is well known, the steady state joint distribution of the jobs in the two nodes is the product form
This is only stable if λi < μi; therefore, the output rate of the standard nodes is always less than the rate (1 − pi)μi achieved by the ∞-supply system, and if one tries to approach this rate, the queue length explodes.
Standard Jackson network nodes.
It is interesting to compare the two systems in the case that both have the same traffic intensities. For the remainder of this section, we take ρi = λi /μi = μ3−i p3−i /μi. We compare the total number in the two nodes for the two systems. The marginal steady state distributions in the nodes of the two systems are the same, namely Geometric, with P(Xi ≥ n) = ρin. In particular, it follows that the mean number in the system is the same for both networks. However, the steady state distribution of the total number in the system is different.
In Figure 4, we show the distribution of the total number in the system for μ1 = 2, μ2 = 3, p1 = 0.8, p2 = 0.5 (top) and μ1 = μ2 = 1, p1 = p2 = 0.8 (bottom). We also plot the standard product form probabilities for comparison.
Probabilities of total number in the system.
The correlation between X1 and X2, calculated from formula (2.5), equals −0.2976 for the first example of an asymmetric system and −0.3873 for the second example of a symmetric system. In fact, it can be shown that the correlation is always negative; see Section 4.8. Negative correlation reduces the variance of the total number in the system compared to independent nodes. In Figure 5, we show the correlation between X1 and X2 for the symmetric system μ1 = μ2 and p1 = p2 = p. Clearly, the negative correlation gets stronger as p tends to 1; the limiting value for p = 1 is equal to 2/3π2 − 7 (see Section 4.8).
Correlation between X1 and X2 for the symmetric system μ1 = μ2 and p1 = p2 = p.
We can also get the asymptotic tail probabilities of X1 + X2, from (2.4). We will show that the sum is absolutely convergent and that the parameters αk and βk monotonously decrease. The values for large n therefore behave like the largest geometric term,
The corresponding asymptotics for the product form standard Jackson network are
Hence, the asymptotic ratio of the two is
In Table 1, we summarize various quantities for the two examples and the comparison of the total number in the system for the ∞-supply and standard systems.
Comparison of Infinite-Supply and Standard Jackson Networks
The most interesting part here is the strong form of variance reduction and tail probability (i.e., overflow probabilities in practice) obtained in the infinite-supply network, when the two nodes are symmetric.
4. DERIVATION OF STEADY STATE DISTRIBUTION
In this section, we prove Theorem 2.1. We first derive the expression as a formal solution to the balance equations and then prove that this solution is absolutely convergent.
4.1. Balance Equations
The balance equations for the steady state probabilities in this system are obtained by equating the flow out and into each state, yielding the following:
In the next section, we will characterize the product forms αn1βn2 satisfying the balance equations in the interior of the quadrant.
4.2. Product Form Trial Solutions in the Interior of the Quadrant
Consider first (4.1) in the interior of the quadrant and a product form trial solution αn1βn2. Substituting this trial solution in (4.1) and canceling αn1−1βn2−1, we see immediately the following:
Proposition 4.1: The product form αn1βn2 solves (4.1) for every n1,n2 = 0,±1,±2,…, if and only if α and β are on the curve:
Curve (4.5) is shown in Figure 6. The pairs of values (α,β) = (0,0) and (α,β) = (1,1) are on this curve. We also illustrate on the curve how the special roots that appear in the solution (2.1,2.2), αk,βk, are calculated, for k = 0,1,2,3.
Curve (4.5) for μ1 = 2,μ2 = 3 and p1 = 0.8,p2 = 0.5.
For every fixed value of 0 < α ≤ 1, (4.5) yields a quadratic equation for β:
Proposition 4.2: The quadratic equation (4.6) has two real roots for all 0 < α ≤ 1. For α = 1, the roots are β = 1 and β = ρ2. For 0 < α < 1, the larger root is β > α and the smaller root is 0 < β < α.
Proof: For the fixed value α = α0 = 1, the quadratic equation (4.6) for β is
with the two roots β = 1 and β = β1 = μ1 p1 /μ2 = ρ2. For 0 < α < 1, if we substitute β = α in the right-hand side of the quadratic equation (4.6), we get
Hence, the quadratic equation (4.6) has two roots, one of them larger and the other smaller than α. The product of the two roots is μ1 p1 /μ2; hence, both are positive. █
Similarly, for every fixed value 0 < β ≤ 1, (4.5) yields a quadratic equation for α:
Proposition 4.3: The quadratic equation (4.7) has two real roots for all 0 < β ≤ 1. For β = 1, the roots are α = 1 and α = ρ1. For 0 < β < 1, the larger root is α > β and the smaller root is 0 < α < β.
It is convenient to divide the quadratic equations (4.6) and (4.7) by α2β2 and to consider quadratic equations for α−1, β−1:
4.3. Compensating for the Vertical and Horizontal Boundaries
Let α and β satisfy (4.5), so that αn1βn2 solves the balance equations (4.1) for all n1,n2 = 0,±1,±2,…. We want to find a compensating term such that
will, in addition, solve the horizontal boundary equations (4.2).
We first subtract (4.2) from (4.1) to obtain
Since our trial solution
solves (4.1), it will solve (4.2) if and only if it solves (4.10). We substitute the trial solution in (4.10), yielding
To satisfy (4.11) for all n1 > 0, we are forced to take
; thus, to solve (4.1), we need to take
as the second root of the quadratic equation (4.6). Using the quadratic equation (4.8), we get the second root
in terms of α and the first root β−1:
We also get the product of the roots of (4.8):
By canceling αn1+1 in (4.11), we obtain an equation for c:
We now use (4.12) to cancel
on both sides and obtain
Multiplying the linear combination by the constant (1 − α)(1 − β), we may conclude that
solves the balance equations (4.1) and (4.2). The procedure to compensate for the vertical boundary equations is symmetric.
Proposition 4.4: Let α and β satisfy (4.5). Then
solves the balance equations (4.1) and (4.2) in the interior and the horizontal boundary if we take
Similarly,
solves the balance equations (4.1) and (4.3) in the interior and the vertical boundary if we take
4.4. Infinite Sequences of Compensations
Motivated by the marginal distribution (1.3), we start from a product form solution with α1 = ρ1. The roots of (4.6) are β0 = 1 and β2 < ρ1. Since we need convergence, we start from the trial solution α1n1 β2n2. To conform with our desired final form, we multiply this trial solution by a constant.
Proposition 4.5: The trial solution (1 − α1)α1n1(1 − β2)β2n2 with α1 = ρ1 and β2−1 = [(μ1 + μ2)/μ1 p1]ρ1−1 − 1 − [(1 − p1)/p1] solves (4.1) and (4.2) for all n1 > 0 and n2 ≥ 0.
Proof: In this case, the compensating term would have
, but then 1 −
, so the compensating term disappears. █
We next add a compensating term to solve (4.1) and (4.3). According to (4.15), we choose
to obtain a two-term trial solution
In this solution, the first term alone solves (4.1) and (4.2), and the two terms together solve (4.1) and (4.3).
From now on, we continue to add compensating terms to satisfy (4.2) and to satisfy (4.3) alternately. In the next step, we need to compensate the second term of (4.16) to solve (4.2) again, and we choose β4 according to (4.14). We continue these compensating steps indefinitely.
Proposition 4.6: For all k ≥ 1, let
with initially β0 = 1 and α1 = ρ1. Then trial solution
solves the balance equations for all (n1,n2) ≠ (0,1),(1,0),(0,0).
Proof: We show in Section 4.7 that the infinite sum (4.18) is absolutely convergent for every (n1,n2) ≠ (0,0). We will also show that the summation of (4.18) over all the values of (n1,n2) ≠ (0,0) converges absolutely. In the rest of the proof, we take this statement as proved.
The pair (α1,β0) is on the curve (4.5). Hence, using (4.14) and (4.15) and induction, so are all the pairs (α2k−1,β2k) and (α2k+1,β2k). Hence, all the terms in (4.18) solve (4.1), and by absolute convergence, so does the infinite sum for n1 > 0 and n2 > 0.
In the sum (4.18), each negative term compensates the preceding positive term so that their sum solves (4.3); see Proposition 4.4. Hence, for all K,
solves (4.3). By absolute convergence, (4.18) solves (4.3), whenever the equations do not involve (n1,n2) = (0,0). Hence, (4.18) solves (4.3) for all (0,n2),n2 > 1.
We saw that (1 − α1)α1n1(1 − β2)β2n2 solves (4.2). Each positive term (1 − α2k+1)α2k+1n1(1 − β2k+2)β2k+2n2 compensates the preceding negative term −(1 − α2k+1)α2k+1n1(1 − β2k)β2kn2 in the sum, so that their sum solves (4.2). Hence, for all K,
solves (4.2). By absolute convergence, (4.18) solves (4.2), whenever the equations do not involve (n1,n2) = (0,0). Hence, (4.18) solves (4.2) for all (n1,0),n1 > 1. █
Analogously, we can start from the (1,ρ2) on the curve (4.5) and get another solution:
Proposition 4.7: For all k ≥ 1, let
with initially α0 = 1 and β1 = ρ2. Then trial solution
solves the balance equations for all (n1,n2) ≠ (0,1),(1,0),(0,0).
4.5. The Complete Solution
The two solutions in Propositions 4.6 and 4.7 were not defined for (n1,n2) = (0,0). The reason is that, for n1 = n2 = 0, the sums are not (absolutely) convergent, and so they are meaningless. As a result, we could not check for (n1,n2) = (1,0) or (n1,n2) = (0,1).
To obtain a solution for all (n1,n2), we do the following: For all (n1,n2) ≠ (0,0), we take the sum of the two solutions (4.18) and (4.20). This yields
For (n1,n2) = (0,0), we take
Proposition 4.8: The expressions for P(n1,n2) in (4.21) and (4.22) solve all of the balance equations.
Proof: We will show in Section 4.7 that the sum in P(0,0) is also absolutely convergent. We shall take that as well as absolute convergence of all the other P(n1,n2) and their sum over all n1 and n2 as proved.
We already know by the previous two propositions that P(n1,n2) defined by (4.21) satisfy the balance equations (4.1), (4.2), and (4.3) for n1 + n2 > 1. It remains to consider the balance equations for (1,0),(0,1), and (0,0). For all K, we have seen in the proof of Proposition 4.6 that the sum
solves (4.2). Also, for all K, we have seen in the proof of Proposition 4.7 that the sum
solves (4.2). Hence, the sum of (4.23) and (4.24) also solves (4.2). Consider, in particular, the balance equation for (n1,n2) = (1,0):
It is satisfied by the sum of (4.23) and (4.24). We now look at the sum of (4.23) and (4.24) for n1 = n2 = 0:
As we will see, αk,βk → 0 as k → ∞. This property and absolute convergence of the sum
shows that (4.25) is satisfied by P(1,0), P(0,1), P(1,1), and P(2,0) as defined in (4.21) and P(0,0) as defined by (4.22). The proof for the balance equation of (0,1) is symmetric.
Finally, by the absolute convergence of the sum over all n1 and n2 of (4.21), we get that (4.4) is redundant and is satisfied automatically by the expressions for P(n1,n2) in (4.21) and (4.22). █
4.6. Normalizing the Sum of Probabilities
We again take absolute convergence as proved. Based on that, we can calculate various quantities. We first obtain marginal probabilities, which are consistent with (1.3).
Proposition 4.9: For ni > 0,
Proof: We make heavy use of the absolute convergence to change the order of summations and group sums of positive and negative terms. For n1 > 0, the sum is
The case of i = 2 is symmetric. █
We next calculate P(n1 = 0,n2 > 0) and P(n1 > 0,n2 = 0).
Proposition 4.10:
Proof: We again make heavy use of the absolute convergence:
The other case is symmetric. █
Finally, we have the following proposition.
Proposition 4.11: The probabilities P(n1,n2) in (4.21) and (4.22) sum up to 1.
Proof: By the previous two propositions and (4.22),
4.7. Absolute Convergence
In the previous sections, we made heavy use of the absolute convergence of the sums in (4.21) and (4.22). This will be proved next.
Proposition 4.12:
Proof:
In the next proposition, we show that the sequences αk and βk decrease geometrically, and, hence, the last sum converges. █
Proposition 4.13: For all k ≥ 0,
Proof: For k = 0, we have α0 = β0 = 1,α1 = ρ1, and β1 = ρ2 and this is the only case of equality. For k ≥ 1, by (4.15),
where the first inequality follows from βk−1 > αk−1−1 and the second from βk−1 > 1. The proof for βk+1 is symmetric. █
We can also get the asymptotic rate of decay of αk and βk:
Proposition 4.14: As k → ∞,
Proof: The parameters αk+1 and αk−1 are the roots of (4.5) with β = βk. Dividing (4.5) by βk2, we get that αk+1 /βk and αk−1 /βk are the roots of
with β = βk. As k → ∞, then βk → 0 by Proposition 4.13 and, thus,
where 0 < γ1 < 1 < γ2 are the roots of (4.26) with β = 0. Hence,
The proof for βk+1 /βk is similar. █
From the geometric decay of the sequences αk and βk, we can further conclude the following:
Corollary 4.15:
(i) The sum that defines P(0,0) in (4.22) is absolutely convergent.
(ii) For all m,n ≥ 0,m + n > 0, the sum defining
in (2.5) is absolutely convergent.
4.8. Nonnegativity and Ergodicity
From Propositions 4.8, 4.11, and 4.12 it follows that P(n1,n2) given by (4.21) and (4.22) are a nonnull, absolutely convergent solution of the balance equations, which sums up to 1. From Theorem 1 in Foster [4], we can immediately conclude the following:
Corollary 4.16: The Markov jump process X(t) = (X1(t),X2(t)) is ergodic when ρ1,ρ2 < 1, and its equilibrium probabilities are given by the solution P(n1,n2) defined by (4.21) and (4.22).
4.9. Queue Length Correlation
In this subsection, we show that the correlation between X1 and X2 is always negative, which is equivalent to
The terms in the infinite sum (4.27) are alternating and decreasing in magnitude, since α1 > β2 > α3 > ··· and β1 > α2 > β3 > ···. Hence, it suffices to show that
which can be verified by straightforward calculations. This proves the following proposition:
Proposition 4.17: If ρ1,ρ2 < 1, then Corr(X1,X2) < 0.
Figure 5 displays the correlation for the symmetric system μ1 = μ2 = μ and p1 = p2 = p. To find the limiting value of the correlation as p ↑ 1, note that in the symmetric case,
which can be derived from the recursive relations for the sequences αk and βk. Hence, from (4.27) and using that
we obtain
Note that exactly the same asymptotic correlation value appears in the calculations of Boxma and van Houtum [3, p.488], which is curious, since the two models are quite different.
Acknowledgments
This research was supported in part by Network of Excellence Euro-NGI (I. A. and G. W.) and Israel Science Foundation (Grant 249/02) (G. W.)
References
REFERENCES
Adan, I.J.B.F. &
Weiss, G.
(2003).
Analysis of a simple Markovian re-entrant line with infinite supply
of work under the LBFS policy.
Preprint.
Adan, I.J.B.F.,
Wessels, J., &
Zijm, W.H.M.
(1993).
A compensation approach for two-dimensional Markov processes.
Advances in Applied Probability
25:
783–817.Google Scholar
Boxma, O.J. &
van Houtum, G.J.
(1993).
The compensation approach applied to a 2 × 2 switch.
Probability in the Engineering and Informational Sciences
7:
471–493.Google Scholar
Foster, F.G.
(1953).
On the stochastic matrices associated with certain queueing
processes.
Annals of Mathematical Statistics
24:
355–360.Google Scholar
Goodman, J.B. &
Massey, W.A.
(1984).
The non-ergodic Jackson network.
Journal of Applied Probability
21:
860–869.Google Scholar
Kelly, F.P.
(1979).
Reversibility and stochastic networks.
New York:
Wiley.
Kopzon, A. &
Weiss, G.
(2002).
A push pull queueing system.
Operations Research Letters
30:
351–359.Google Scholar
Kopzon, A. &
Weiss, G.
(2003).
A preemptive push pull queueing system.
Preprint.
Levy, Y. &
Yechiali, U.
(1975).
Utilization of idle time in an M/G/1
queueing system.
Management Science
22:
202–211.Google Scholar
van Houtum, G.J.
(1994).
New approaches for multi-dimensional queueing systems.
Ph.D. thesis,
Eindhoven University of Technology, The Netherlands.
Weiss, G.
(1999).
Scheduling and control of manufacturing systems—A fluid
approach. In
Proceedings of the 37 Allerton Conference, pp.
577–586.
Weiss, G.
(2004).
Stability of a simple re-entrant line with infinite supply of
work—The case of exponential processing times.
Journal of Operations Research Society of Japan
47(4):
304–313.Google Scholar
Weiss, G.
(2003).
Jackson networks with unlimited supply of work and full
utilization.
Preprint.
A two-node Jackson network with infinite supply of work.
Transition rates for the two-node system.
Standard Jackson network nodes.
Probabilities of total number in the system.
Correlation between X1 and X2 for the symmetric system μ1 = μ2 and p1 = p2 = p.
Comparison of Infinite-Supply and Standard Jackson Networks
Curve (4.5) for μ1 = 2,μ2 = 3 and p1 = 0.8,p2 = 0.5.
You have
Access
- 11
- Cited by