Periodic routing to parallel queues with bounds on the average waiting time

A. Hordijk and D.A. van der Laan Mathematical Institute, University Leiden

Abstract

In this paper we introduce the combinatorial notion of unbalance for a zero-one splitting sequence and for a routing pattern. Using this unbalance we derive an upper bound for the average expected waiting time of jobs which are routed to parallel queues according to a periodic routing rule. A billiard sequence is obtained with unbalance smaller than or equal to \frac{N}{2} − 1, where N is the number of different symbols in the sequence which corresponds to the number of parallel queues in the routing problem.

KEY WORDS: periodic routing, parallel queues, bounds on waiting time, unbalance, billiard sequences

1 Introduction

Load balancing in distributed multiprocessors and in communication networks is an important tool to improve their performance in mean delay of the jobs (for overviews of the literature see [11] and [22]). In many systems the load balancing protocol is an open-loop control, in which case it does not depend on the information in the system, as queue-sizes etc., but only depends on the system parameters. In this paper we focus on the performance under this type of control, which usually is called static routing control. In the publications ([26],[37], [20] and [25] ) the static routing problem in a network is reduced to finding the best utilization of each service centre. Given this utilization of a particular service centre the problem then becomes to find the static routing to parallel queues with minimal average expected waiting time. For this routing problem probabilistic (also called Bernoulli) and deterministic routing policies have been analyzed. In case of probabilistic routing to homogeneous servers, the optimality of equal routing probabilities is proved in [14] and [27]. In general deterministic (generalized) round robin policies are superior to probabilistic routing for homogeneous (heterogeneous) servers. For homogeneous servers, the optimality of the round robin routing is proved in [29]. The problem of constructing the optimal generalized round robin policy for heterogeneous servers is an unsolved problem. In the papers [23] and [2] the optimal routing problem for exponential service times is transformed to a Markov decision process (see [1] for an overview of the applications of these processes in telecommunication).

In a recent approach the optimization procedure is splitted into two problems. First the fractions of jobs routed to the servers are computed via a best probabilistic routing. For networks these fractions are computed via the optimal rates (see [26],[37], [20] and [25]) , and for the single server with parallel queues also different approximation methods have been used (see [15]). Given the fractions of jobs that have to be routed to the queues, the problem then becomes to construct the best routing pattern. In the seminal paper of Hajek ([21]) it is shown for one queue with exponential service times that the regular splitting sequence with the density d is optimal for any initial phase ϕ, if a fraction d of the arriving customers have to be routed to that queue. A regular zero-one valued splitting sequence with rational density d and initial phase ϕ ∈ ℝ is:

{b_{k}^{d} (ϕ)} = ⌊(k + 1)d + ϕ⌋ − ⌊kd + ϕ⌋,

k = 1, 2, . . .. The corresponding routing rule assigns the k-th arrival to the queue if b_{k}^{d} (ϕ) = 1. Since the zeros of a regular splitting sequence with density d form a regular splitting sequence with density (1 − d), it follows that the regular splitting sequence with density d gives an optimal routing sequence to two queues with exponential service times for given fractions d and (1 − d). It is proved in [3] and [5] that a regular splitting policy is optimal in the class of all static routing policies (without fixing the routing fractions beforehand) for two queues with general stationary interarrival and service times. An algorithm for computing the optimal routing policy for two queues with deterministic interarrival and service times has been derived in [18].

The problem of finding the best optimal routing pattern with given splitting fractions is a complex optimization problem for N ≥ 3 queues (see [9]). There are only few sets of fractions for which the regular splitting sequences generate an exact covering of the positive integers (see [4] and [36]), and only in these cases the optimal routing pattern is known. Regular sequences, which are also called Beatty, Sturmian, or bracket sequences have applications in many branches of sciences (see [35]).

For routing to N ≥ 3 parallel queues many algorithms for finding good allocation patterns have been derived. In [32] the golden ratio policy is used for the optimal routing of jobs, in [24] for the dual problem of the static control of a multiple-access channel, and in [16] for optimal robot scheduling of web search engines. In these papers the asymptotic optimality of the golden ratio policy as the number of queues tends to infinity is studied. Other algorithms for generalized round robin routing sequences have been given in [7] and [9]. Methods to obtain good allocation patterns can be found in [15] and [12]. Although simulations make it evident that the proposed algorithms behave well, bounds on their performance were only derived for exponential queues with no buffer space.

In this paper we concentrate on obtaining bounds for the average expected waiting time of the jobs for a routing pattern to parallel queues with unlimited buffer capacity and general sequences of interarrival and service times. Our analysis is mainly combinatorial. For a given pattern allocation we introduce its unbalance. All regular sequences have unbalance equal to zero, and for a splitting sequence to one queue the unbalance is roughly speaking its ’distance’ to the regular sequence with the same density. For the routing pattern it is the sum of the unbalances of the splitting sequences to the queues. In [3] and [5] it is shown for routing policy ψ which routes a fraction d_{i} to queue i for i = 1, 2, …, N that the average expected waiting time \overline{W} (ψ) is bounded from below by R̃, where R̃ = ∑_{i=1}^{N} d_{i} ·\overline{W}^{i}(ω(d_{i})), with \overline{W}^{i}(ω(d_{i})) the average expected waiting time for jobs routed to queue i when the routing to queue i is according to a regular sequence with density d_{i}. The upper bound for \overline{W} (ψ) which we derive in this paper is R̃ + δ · \overline{O}(U), where δ is the mean interarrival time, U is the routing sequence corresponding to policy ψ and \overline{O}(U) is the unbalance of U. Hence,

R̃ ≤ \overline{W} (ψ) ≤ R̃ + δ · \overline{O}(U).

The unbalance \overline{O}(U) is a combinatorial notion and it does not depend on the service or the interarrival distribution. Hence the bounds are insensitive, i.e. they are valid for any stationary sequence of interarrival and service times. However, the lower bound R̃ does depend on the distribution of the interarrival and service times. The upper bound is tight for the heavy traffic situation in which the interarrival and service times are deterministic and the traffic intensity is 1 for each of the queues. So the upper bound is accurate for high traffic, whereas \overline{W} (ψ) will be close to the lower bound for low traffic.

Finding for given densities d_{i}, i = 1, 2, …, N the routing sequence U such that the unbalance \overline{O}(U) is minimal can be transformed to a combinatorial optimization problem (see [28]). Greedy algorithms for obtaining good routing policies have been given in [7], [9], [33] and [28]. In this paper we consider greedy algorithms which in a special case generate billiard sequences. Suppose a billiard consisting of the N-dimensional cube [0, 1]^{N} (see [8], [10]), with sides numbered 1, 2, …, N such that opposite sides have the same number. Give a billiard ball initial position (x_{1}, x_{2}, …, x_{N}) and initial velocity vector (−d_{1}, −d_{2}, …, −d_{N}), and take the sequence U_{b} = (n_{1}, n_{2}, …) indicating the order in which the sides are hit by the ball, breaking ties in an unique way and let ψ_{b} be the corresponding routing policy. Then ψ_{b}, which routes the k -th arrival to queue i if n_{k} = i, is a routing policy with densities d_{i}, i = 1, 2, …, N. We show that by taking a special initial position the unbalance \overline{O}(U_{b}) of this routing sequence is bounded by \frac{N}{2} − 1. Hence,

R̃ ≤ \overline{W} (ψ_{b}) ≤ R̃ + δ(\frac{N}{2} − 1).

For N = 2 an optimal routing is constructed, and for N ≥ 3 this billiard sequence is easily computed and has the above upper bound on its performance. In this paper we consider only rational densities d_{i} = \frac{p_{i}}{q_{i}} with p_{i}, q_{i} ∈ ℕ, gcd(p_{i}, q_{i}) = 1. In this case the billiard sequence is periodic with period T = lcm(q_{1}, q_{2}, …, q_{N}), and in fact it gives a routing pattern with period T.

The paper is organized as follows. In section 2 we start with an introduction of regular sequences together with properties which we need for our analysis. We define a partial order in the set P(T, k) of all sequences of zeros and ones of length T containing exactly k ones. The conjugacy class of the regular sequences in P(T, k) is shown to be the minimal element in an induced order. We define the notion unbalance for periodic words of zeros and ones by using the period cycle of the word, which is an element of P(T, k) if there are k ones in the cycle length T. In fact we will define a primal unbalance and a dual unbalance, the dual unbalance can be used for the dual model of optimal routing of the server in polling models. The unbalance is a measure for the irregularity of the word. The unbalance has a graphical representation (see figure 1), it is the area between the graph of its representation as element of P(T, k) and that of the regular one. This leads to another partial order which we called the graph order. The conjugacy class of the regular sequences in P(T, k) is shown to be the minimal element in this graph order. The results of section 2 are purely combinatorial and have possibly other applications than in this routing problem.

In section 3 we consider the routing to one queue and we consider all static deterministic policies which route a fraction p of all jobs to the queue. We restrict our analysis to periodic routing policies and thus to routing sequences with rational fraction p. We use the unbalance to bound the difference in average waiting times. We do this by a sample path comparison for fixed sequences of interarrival and service times. By using results on renovation and ergodicity we then obtain the above mentioned bounds for one queue. In section 4 we extend the bounds to N parallel queues.

In section 5 we extend the combinatorial analysis of the unbalance and derive its relation with the discrepancy function defined in section 2. We introduce greedy algorithms and the billiard sequence which is obtained by a special greedy algorithm. It is shown that there is a billiard sequence with minimal unbalance for given densities. For rational routing densities d_{i} = \frac{p_{i}}{q_{i}} with p_{i}, q_{i} ∈ ℕ, gcd(p_{i}, q_{i}) = 1 we show that the unbalance of the billiard routing pattern is bounded by \frac{N}{2} − 1 if an initial position (x_{1}, …, x_{N}) is chosen with x_{k} = 0 for k such that q_{k} = max_{i∈\{1,2,...,N\}} q_{i} and x_{j} = 1 − \frac{1}{q_{j}} for j ≠ k. Many examples illustrate the notions and results in the sections.

Notations. For t ∈ ℝ we denote by ℝ_{>t} (ℝ_{≥t}) the set of real numbers that are greater (or equal) than t. For the integers ℤ and the rational numbers ℚ we denote such subsets in a similar way. For x ∈ ℝ we denote by ⌊x⌋ and ⌈x⌉ the maximal integer not larger than x respectively the minimum integer not smaller than x. If a ∈ ℤ and b ∈ ℕ then a (mod b) denotes the integer c ∈ {0, 1, …, b − 1} for which there exists some d ∈ ℤ such that c + d · b = a. Further gcd denotes the greatest common divisor and lcm denotes the least common multiple. For any random variable X we denote by 𝔼X the expectation of X.

2 Comparing routing sequences

In this section we will compare routing sequences in a queueing system. For a particular queue the routing sequence will be a sequence of ones and zeros, where an one means that the corresponding arriving customer is routed to that queue and a zero means that the customer is not routed to that queue. Instead of sequences we also speak of words. We first give some definitions.

If u and v are finite sequences, u = (a_{1}, a_{2}, …, a_{n}) and v = (b_{1}, b_{2}, …, b_{m}) , then uv = (a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m}) denotes the concatenation of the two sequences. For k ∈ ℕ we denote by u^{k} the sequence uu … u in which the number of u’s is k and we say that u^{k} is a power of u. A finite sequence is primitive if it is not a power of some other sequence. The following lemma is part of Proposition 1.3.1 of [30].

Lemma 2.1 For every non-empty finite sequence u there exists an unique primitive sequence w such that u = w^{n} for some n ∈ ℕ.

Two finite sequences u, u′ are said to be conjugate if there exist sequences v and w (v or w may be empty) such that u = vw and u′ = wv. This is an equivalence relation since u is conjugate to u′ if and only if u′ is a cyclic permutation of u. If u and u′ are conjugate then we write u ∼ u′ and the conjugacy class of all the cyclic permutations of a finite sequence u is denoted by ũ.

Lemma 2.2 Let u be a finite sequence, u = w^{n} with w primitive. Then |ũ|, the number of distinct conjugates of u, equals the length of sequence w.

Proof. By Proposition 1.3.3 in [30] the number of distinct conjugates of u equals the number of distinct conjugates of w and by Proposition 1.3.2 in [30] the number of distinct conjugates of w equals the length of w. □

If A is a finite set (a so-called alphabet) and I ⊆ ℤ is an interval in ℤ then a mapping Λ : I → A is called an I - word or just word. Thus a word is a sequence of letters from the alphabet A. A word is (in)finite if I is in(finite). A subword of Λ is the restriction of Λ to some interval J ⊆ I. For a finite (sub)word Λ we denote the length of Λ by |Λ|. Further for a letter a ∈ A the number of a’s in Λ is denoted by |Λ|_{a}. For an I -word Λ the support of letter a is the set S_{a} = {t ∈ I : Λ(t) = a}. For an I -word Λ we have that letter a has density d if for every non-decreasing sequence of finite subintervals I_{i} with union I we have that \frac{|S_{a}∩I_{i}|}{|I_{i}|} tends to d. An (infinite) I - word Λ is periodic if for some q ∈ ℕ it holds that Λ(t) = Λ(t + q) for every t for which t, t + q ∈ I. Then q is said to be a period of the word and any subword of length q is said to be a period cycle of the word. The period of Λ is defined as the minimum of all the periods of Λ. If q is the period of word Λ then a subword of length q is said to be a primitive period cycle of the word. It is obvious that the following holds.

Lemma 2.3 If k is a period of some word Λ then for every m ∈ ℕ we have that k · m is a period of Λ.

Note that a sequence of zeros and ones corresponds to a word on the alphabet {0, 1}. Vice versa, to every letter in a word corresponds a sequence of ones and zeros via the support of the letter. In the sequel we identify a sequence (of integers) with a word and sometimes it is useful to choose an appropriate domain I for the word the sequence is identified with. So, we consider sequences of integers and words as the same thing and therefore we have the same notions and operations for words as for sequences. A sequence of zeros and ones is said to have density d if the letter 1 has density d in the corresponding word.

Definition 2.4 Let u be an infinite sequence of zeros and ones and Λ be the corresponding word defined on an appropriate infinite interval I. We say that u is regular with density d if for every n ∈ ℕ we have for every subword Λ′ of Λ of length n that |Λ′|_{1} equals ⌊nd⌋ or ⌈nd⌉. In that case we also say that the corresponding set S_{1} is a regular set.

The following theorem follows for I = ℕ from the classification of balanced sequences in [31] and the fact that regular sequences are particular balanced sequences (see [36]).

Theorem 2.5 Let u and Λ be as in Definition 2.4. If u is regular with density d then the support set S_{1} satisfies one of the following cases.

• (irrational case) d is irrational and there exists some φ ∈ ℝ such that

S_{1} = I ∩ \{⌊k · \frac{1}{d} + φ⌋\}_{k∈ℤ} or S_{1} = I ∩ \{⌈k · \frac{1}{d} + φ⌉\}_{k∈ℤ}.

• (rational case) d is rational and there exists some φ ∈ ℚ such that

S_{1} = I ∩ \{⌊k · \frac{1}{d} + φ⌋\}_{k∈ℤ}.

Theorem 2.5 has the following corollaries.

Corollary 2.6 Let u and Λ be as above. If u is regular with irrational density d then there exists a θ ∈ ℝ such that Λ(t) = ⌊(t + 1)d + θ⌋ − ⌊td + θ⌋ or Λ(t) = ⌈(t + 1)d + θ⌉ − ⌈td + θ⌉ for every t ∈ I. If u is regular with rational density d then there exists a θ ∈ ℚ such that Λ(t) = ⌊(t + 1)d + θ⌋ − ⌊td + θ⌋ for every t ∈ I.

Corollary 2.7 If u is regular with rational density d = \frac{p}{q} with p, q ∈ ℕ, gcd(p, q) = 1 then u is periodic with period q.

We define a finite sequence of zeros and ones to be regular if it is a period cycle of some infinite regular periodic sequence.

In [3] and [5] it is shown that a regular sequence is optimal when one has to route to a single queue and a certain fraction of all the arriving customers has to be routed to that queue. They also show that routing according to some regular sequence is optimal when one has to route to two parallel queues. For N ≥ 3 queues one often wants to route to the queues according to some (optimized) fractions, where the sum of these fractions is 1. However, for such prescribed fractions it is not always possible to route in such a way that the routing sequence for every queue is regular. Therefore we want to compare irregular sequences and for finite and periodic sequences (words) we introduce the notion of unbalance. In fact we will define a primal unbalance and a dual unbalance. The unbalance measures the irregularity of the sequence and has some useful properties. One of the obvious properties will be that a sequence has unbalance 0 if and only if it is a periodic regular sequence or it is a period cycle of a periodic regular sequence. We first define the unbalance for finite sequences.

Notation. Let P(T, k) be all sequences of zeros and ones of length T containing exactly k ones and let R(T, k) ⊆ P(T, k) be the subset of the regular sequences in P(T, k). Let u ∈ P(T, k) and Λ the corresponding word on the alphabet {0, 1}. We assume without loss of generality that I = {1, 2, …, T } and we denote u as well as Λ by (u_{1}, u_{2}, …, u_{T}), where u_{t} = Λ(t) for t = 1, 2, …, T. Further we say for l = 0, 1, …, T − 1 that (u_{1+l}, u_{2+l}, …, u_{T} , u_{1}, u_{2}, …, u_{l}) is the l -th cyclic permutation of u.

From the rational case of Theorem 2.5 follows the following lemma.

Lemma 2.8 Let u ∈ R(T, k). Then S_{1} = \{⌊i · \frac{T}{k} + φ⌋\}_{i=1}^{k} for some φ ∈ \{1 − \frac{T}{k} , 1 − \frac{T −gcd(T,k)}{k}, …, 1 − \frac{gcd(T,k)}{k}\}.

It is clear that if u ∈ R(T, k) and u′ ∼ u then u′ ∈ R(T, k). In fact the following lemma states that R(T, k) forms a conjugacy class of P(T, k) and thus the regular sequences in P(T, k) are all cyclic permutations of each other.

Lemma 2.9 Let u ∈ R(T, k). Then u′ ∈ R(T, k) if and only if u ∼ u′.

Proof. We still have to prove the ”only if”-part. For u ∈ R(T, k) we have that ũ ⊆ R(T, k) . By Lemma 2.1 we have that u = w^{n} for some primitive w and by Lemma 2.8 it follows that n = gcd(T, k). Hence the length of sequence w is \frac{T}{gcd(T,k)} and by Lemma 2.2 we have that |ũ| = \frac{T}{gcd(T,k)}. However, by Lemma 2.8 we have that |R(T, k)| ≤ \frac{T}{gcd(T,k)}. Thus ũ = R(T, k). □

Notation. For sequence u ∈ P(T, k) we define the counting function κ_{u} : {0, 1, …, T } → ℤ with κ_{u}(n) = ∑_{t=1}^{n} u_{t}. Thus κ(n) counts the number of ones in the first n letters of the corresponding word Λ. We also define the discrepancy function χ_{u} : \{0, 1, …, T \} → ℚ by χ_{u}(n) = n · \frac{k}{T} − κ_{u}(n) for n = 0, 1, …, T.

Now we define a partial order ⪯ on P(T, k). For u, v ∈ P(T, k) we say that u ⪯ v if κ_{u}(n) ≤ κ_{v}(n) for n = 1, 2, …, T.

Lemma 2.10 This partial order ⪯ on P(T, k) induces a total order on R(T, k).

Proof. Let u, u′ ∈ R(T, k). Then by Lemma 2.8 there exist φ, φ′ ∈ \{1 − \frac{T}{k} , 1 − \frac{T −gcd(T,k)}{k}, …, 1 − \frac{gcd(T,k)}{k}\} such that the support set S_{1} of u is \{⌊i · \frac{T}{k} + φ⌋\}_{i=1}^{k}, while the support set S1^{′} of u′ is \{⌊i · \frac{T}{k} + φ′⌋\}_{i=1}^{k}. Hence, u ⪯ u′ if φ ≥ φ′ and u′ ⪯ u if φ′ ≥ φ. Thus u and u′ are ordered. □

Since R(T, k) is finite it follows from Lemma 2.10 that R(T, k) contains a greatest element for this order. This greatest element is the sequence in which ” the ones are as much to the left as possible ” (under the constraint that the sequence is regular of course). This greatest element of R(T, k) is important for our definition of the (primal) unbalance of a sequence u ∈ P(T, k). We denote this greatest element with \overline{ω}(T, k) or just \overline{ω} if no confusion is possible. By Lemma 2.8 and the proof of Lemma 2.10 we have the following lemma which can be used to determine \overline{ω}(T, k) quickly.

Lemma 2.11 For the support set S_{1} of \overline{ω}(T, k) we have that

S_{1} = \{⌊i · \frac{T}{k} + 1 − \frac{T}{k} ⌋\}_{i=1}^{k}.

Corollary 2.12 For \overline{ω}(T, k) we have that

κ_{\overline{ω}(T,k)}(n) = ⌈n · \frac{k}{T} ⌉ for n = 0, 1, …, T.

We have seen in Lemma 2.9 that the regular sequences R(T, k) are a conjugacy class in P(T, k). We have the following theorem in which the partial order is used to give a characterising property (see Lemma 2.25) of the conjugacy class R(T, k) of regular sequences in the set of all the conjugacy classes of P(T, k).

Theorem 2.13 Every conjugacy class ũ of P(T, k) contains an upper bound of R(T, k), i.e for every u ∈ P(T, k) there exists a v ∈ P(T, k) such that v ∼ u and v ⪰ w for every w ∈ R(T, k).

Proof. Let u ∈ P(T, k) and let l = argmax_{n=0,1,... ,T −1} χ_{u}(n). We claim that u′ := (u_{1+l}, u_{2+l}, …, u_{T} , u_{1}, u_{2}, …, u_{l}), the l-th cyclic permutation of u, is an upper bound of R(T, k). Since u′ ∼ u this proves the theorem.

To prove the claim it suffices to show that u′ ⪰ \overline{ω}. By definition it follows that χ_{u}(l) ≥ χ_{u}((l + n) (mod T)) = χ_{u}(l) + χ_{u′}(n) for n = 0, 1, …, T − 1 and thus χ_{u′}(n) ≤ 0 for n = 0, 1, …, T − 1. Since χ_{u′}(0) = χ_{u′}(T) = 0 it follows that

max_{n=1,2,... ,T} χ_{u′}(n) = max_{n=0,1,... ,T −1} χ_{u′}(n) = 0.

Hence κ_{u′}(n) ≥ n · \frac{k}{T} and thus κ_{u′}(n) ≥ ⌈n · \frac{k}{T} ⌉ for n = 1, 2, …, T. So, by Corollary 2.12 we have indeed that u′ ⪰ \overline{ω}. □

Remark. If gcd(k, T) = 1 then it is easily seen for every u ∈ P(T, k) that χ_{u} is injective on the domain {0, 1, …, T − 1} and thus argmax_{n=0,1,... ,T −1} χ_{u}(n) is unique. A consequence is that for every u ∈ P(T, k) the upper bound of R(T, k) in the conjugacy class ũ is unique if gcd(k, T) = 1. If gcd(k, T) > 1 then the upper bound is in general not unique. For example, if u = (1, 0, 0, 0, 1, 0, 0, 1, 0) ∈ P(9, 3) then \overline{ω} = (1, 0, 0, 1, 0, 0, 1, 0, 0) and the conjugacy class ũ contains two upper bounds of R(9, 3). Namely, (1, 0, 1, 0, 0, 0, 1, 0, 0) and (1, 0, 0, 1, 0, 1, 0, 0, 0). Note that for u ∈ P(T, k) the proof of Theorem 2.13 yields an algorithm to determine the upper bound(s) of R(T, k) in the conjugacy class ũ.

Theorem 2.13 has the following ” dual ” theorem which is obtained in a completely analogous way. This dual theorem is needed for the definition of the dual unbalance.

Theorem 2.14 Every conjugacy class ũ of P(T, k) contains a lower bound of R(T, k).

We are now ready to define the (primal) unbalance.

Definition 2.15 Let u ∈ P(T, k), \overline{ω} = \overline{ω}(T, k) and let u′ be an upper bound with respect to the partial order ⪯ of R(T, k) in the conjugacy class ũ. Then the primal unbalance \overline{I} of u is defined by

\overline{I}(u) = \frac{1}{T} ∑_{n=1}^{T}(κ_{u′}(n) − κ\overline{ω}(n)).  (1)

Theorem 2.16 The primal unbalance \overline{I} is well defined.

Proof. The primal unbalance \overline{I} is well defined if and only if for every pair u′, u′′ of upper bounds of R(T, k) , u′ ∼ u′′ we have that ∑_{n=1}^{T} κ_{u′}(n) = ∑_{n=1}^{T} κ_{u′′}(n). We can assume that u′ ≠ u′′. Since u′ ∼ u′′ there exists an m ∈ {1, 2, …, T − 1} such that u′ = vw, u′′ = wv where v = (v_{1}, v_{2}, …, v_{m}) and w = (w_{1}, w_{2}, …, w_{T −m}). Since u′ ⪰ \overline{ω} and u′′ ⪰ \overline{ω} we have that χ_{u′}(n) ≤ 0 and χ_{u′′}(n) ≤ 0 for n = 0, 1, …, T. Moreover we have that χ_{u′}(0) = χ_{u′}(T) = 0 and χ_{u′′}(0) = χ_{u′′}(T) = 0. So,

χ_{u′}(m) = m · \frac{k}{T} − κ_{u′}(m) = (T − (T − m)) · \frac{k}{T} − ∑_{i=1}^{m} v_{i} = (T · \frac{k}{T} − κ_{u′′}(T))

−((T − m) · \frac{k}{T} − κ_{u′′}(T − m)) = χ_{u′′}(T) − χ_{u′′}(T − m) = −χ_{u′′}(T − m)

and thus χ_{u′}(m) = χ_{u′′}(T − m) = 0. Hence χ_{u′}(0) = χ_{u′′}(T − m) and by induction it follows that χ_{u′}(n′) = χ_{u′′}(T − m + n′) for n′ = 0, 1, …, m. Further χ_{u′}(m) = χ_{u′′}(0) and by induction it follows that χ_{u′}(n′) = χ_{u′′}(n′ − m) for n′ = m, m + 1, …, T. Hence

∑_{n=1}^{T} χ_{u′}(n) = ∑_{n′=1}^{m} χ_{u′}(n′) + ∑_{n′=m+1}^{T} χ_{u′}(n′) = ∑_{n′=1}^{m} χ_{u′′}(T − m + n′) + ∑_{n′=m+1}^{T} χ_{u′′}(n′ − m)

= ∑_{n=1}^{T} χ_{u′′}(n) and thus ∑_{n=1}^{T} κ_{u′}(n) = ∑_{n=1}^{T} κ_{u′′}(n).

□

Now that we have defined the primal unbalance we also define the dual unbalance. Therefore we use the dual order ⪯′ of the partial order ⪯, i.e u ⪯′ v if and only if v ⪯ u. With this dual order ⪯′ we have in a completely analogous way the same results as for the order ⪯. Thus also for this order ⪯′ we have that R(T, k) has a greatest element, which we denote by \underline{ω}(T, k), or just \underline{ω} if no confusion is possible. Note that \underline{ω} is the smallest element of R(T, k) with respect to the primal order ⪯. With this dual order we can restate Theorem 2.14 as ” Every conjugacy class ũ of P(T, k) contains an upper bound (with respect to the order ⪯′) of R(T, k).” Hence, Theorem 2.14 says the same as Theorem 2.13 except that the primal order ⪯ is replaced with the dual order ⪯′. Now we also define the dual unbalance.

Definition 2.17 Let u ∈ P(T, k), \underline{ω} = \underline{ω}(T, k) and let u′ be an upper bound with respect to the (dual) partial order ⪯′ of R(T, k) in the conjugacy class ũ. Then the dual unbalance \underline{I} of u is defined by

\underline{I}(u) = \frac{1}{T} ∑_{n=1}^{T}(κ\underline{ω}(n) − κ_{u′}(n)).  (2)

The dual unbalance is just as the primal unbalance well defined and we can illustrate the primal unbalance \overline{I}(u) and the dual unbalance \underline{I}(u) of some sequence u ∈ P(T, k) graphically in the following way. We draw in the 2-dimensional plane a line segment l with slope \frac{k}{T −k} from lattice point (0, 0) to lattice point (T − k, k). Further a sequence v ∈ P(T, k) corresponds to a connected graph from (0, 0) to (k, T − k) in the following way. The graph starts at (0, 0) and goes one length unit to the right or above if the next element of the sequence is a zero respectively an one. To determine \overline{I}(u) and \underline{I}(u) for some u ∈ P(T, k) we have to find u′ ∈ P(T, k) respectively u′′ ∈ P(T, k) such that u′ and u′′ are in the same conjugacy class as u, \overline{ω} ⪯ u′ and u′′ ⪯ \underline{ω}. Then if we draw the graphs of u′, u′′, \overline{ω} and \underline{ω} as described above we have the following. We have that the graph of \overline{ω} never is below the line segment l, but remains as close as possible to l under this condition. Namely, the graph of \overline{ω} goes through the lattice points that are on l and the lattice points that are immediately above l. Similarly the graph of \underline{ω} is never above l and goes through the lattice points on l and the lattice points immediately below l. Further the graph of u′ is never below \overline{ω} and thus never below l. It is easily seen that T ·\overline{I}(u) = T ·\overline{I}(u′) is the area below the graph of u′ minus the area below the graph of \overline{ω}. Similarly the graph of u′′ is never above \underline{ω} and thus never above l. Moreover T · \underline{I}(u) = T · \underline{I}(u′′) is the area below the graph of \underline{ω} minus the area below the graph of u′′. For example we do this for the sequence u = (1, 0, 0, 0, 1, 0, 0, 1, 0) ∈ P(9, 3) of the previous example. We take u′ = (1, 0, 1, 0, 0, 0, 1, 0, 0) as upper bound of R(9, 3) in the conjugacy class of u and we take u′′ = (0, 0, 0, 1, 0, 0, 1, 0, 1) as lower bound of R(9, 3) in the conjugacy class of u. In Figure 1 are the graphs of \overline{ω}, \underline{ω}, u′, u′′ and the line segment l. Note that we have drawn the lines of the graphs above l and below l thicker if the graphs of u′ and \overline{ω} respectively the graphs of u′′ and \underline{ω} coincide. It follows that \overline{I}(u) = \frac{1}{9} and \underline{I}(u) = \frac{2}{9}.

[figure]

Figure 1

A direct consequence of the definitions of the primal and dual unbalance is the following lemma which states that conjugates have the same primal unbalance and the same dual unbalance.

Lemma 2.18 If u ∼ u′ then \overline{I}(u) = \overline{I}(u′) and \underline{I}(u) = \underline{I}(u′).

For a finite word (sequence) u = (u_{1}, u_{2}, …, u_{T}) we denote by \overleftarrow{u} := (u_{T} , u_{T −1}, …, u_{1}) the reversed word. Further if for some sequences u, v ∈ P(T, k) we have that \overleftarrow{u} ∼ v then we say that u and v are mirrors of each other. Note that if u ∈ P(T, k) is regular then u is a mirror of itself.

Proposition 2.19 If u, v ∈ P(T, k) are mirrors of each other then \overline{I}(u) = \underline{I}(v) and \underline{I}(u) = \overline{I}(v).

Proof. Let u′ ∼ u be an upper bound with respect to the partial order ⪯ of R(T, k) and put v′ = \overleftarrow{u′}. Then

\overline{I}(u) = \frac{1}{T} ∑_{n=1}^{T}(κ_{u′}(n) − κ\overline{ω}(n)) = \frac{1}{T} ∑_{n=0}^{T}(κ_{u′}(n) − ⌈n · \frac{k}{T} ⌉)

and v′ ∼ v. Moreover for n′ = 0, 1, …, T we have that

κ_{v′}(T − n′) = k − κ_{u′}(n′) ≤ k − ⌈n′ · \frac{k}{T} ⌉ = ⌊(T − n′) · \frac{k}{T} ⌋

and thus κ_{v′}(n) ≤ ⌊n · \frac{k}{T} ⌋ for n = 0, 1, 2, …, T. Hence v′ ∼ v is an upper bound with respect to the partial order ⪯′ of R(T, k). Thus

\underline{I}(v) = \frac{1}{T} ∑_{n′=1}^{T}(κ\underline{ω}(n′) − κ_{v′}(n′)) = \frac{1}{T} ∑_{n′=0}^{T}(⌊n′ · \frac{k}{T} ⌋ − (k − κ_{u′}(T − n′)) =

\frac{1}{T} · ∑_{n′=0}^{T}(κ_{u′}(T − n′) − ⌈(T − n′) · \frac{k}{T} ⌉) = \frac{1}{T} · ∑_{n=0}^{T}(κ_{u′}(n) − ⌈n\frac{k}{T} ⌉) = \overline{I}(u).

Analogously it follows that \underline{I}(u) = \overline{I}(v). □

For example if u = (1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0) ∈ P(11, 7) then v = (1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1) ∈ P(11, 7) is a mirror of u. The reader can check that \overline{I}(u) = \underline{I}(v) = \frac{1}{11} and \underline{I}(u) = \overline{I}(v) = \frac{2}{11}.

We also define the primal unbalance \overline{I} and the dual unbalance \underline{I} on the set of conjugacy classes by \overline{I}(ũ) = \overline{I}(u) and \underline{I}(ũ) = \underline{I}(u) , where u is an arbitrary representative of ũ. By Lemma 2.18 this is well defined.

Lemma 2.20 If u = v^{m} where v is a primitive sequence and m ∈ ℕ then \overline{I}(u) = \overline{I}(v) and \underline{I}(u) = \underline{I}(v).

Proof. We can assume that v ∈ P(T, k). Then we have that u ∈ P(mT, mk) and by Lemma 2.11 we have that \overline{ω}(mT, mk) = \overline{ω}(T, k)^{m}. Further if w ∼ v and w is an upper bound of R(T, k) then w^{m} ∼ u and w^{m} is an upper bound of R(mT, mk). Thus we have for every l ∈ {1, 2, …, T } and b ∈ {0, 1, …, m − 1} that

κ_{w}(l) − κ_{\overline{ω}(T,k)}(l) = κ_{w^{m}}(l + bT) − κ_{\overline{ω}(mT,mk)}(l + bT).

Hence

\overline{I}(u) = \frac{1}{mT} ∑_{n=1}^{mT}\{κ_{w^{m}}(n) − κ_{\overline{ω}(mT,mk)}(n)\} = \frac{1}{mT} · m · ∑_{n=1}^{T}\{κ_{w}(n) − κ_{\overline{ω}(T,k)}(n)\}

= \frac{1}{T} ∑_{n=1}^{T}\{κ_{w}(n) − κ_{\overline{ω}(T,k)}(n)\} = \overline{I}(v).

It follows completely analogously that \underline{I}(u) = \underline{I}(v). □

Lemma 2.21 For every u ∈ P(T, k) we have that T · \overline{I}(u) ∈ ℤ_{≥0} and \overline{I}(u) = 0 if and only if u ∈ R(T, k). The same is true for the dual unbalance \underline{I}(u).

Proof. Let u′ as in the definition of the the primal unbalance. Then u′ ⪰ \overline{ω} and thus κ_{u′}(n) − κ\overline{ω}(n) ∈ ℤ_{≥0} for n = 1, 2, …, T. Thus T · \overline{I}(u) = ∑_{n=1}^{T}(κ_{u′}(n) − κ\overline{ω}(n)) ∈ ℤ_{≥0}. If u ∈ R(T, k) then by Lemma 2.9 we have that u′ = \overline{ω} and thus \overline{I}(u) = 0 . Conversely, if \overline{I}(u) = 0 then it follows that κ_{u′}(n) − κ\overline{ω}(n) = 0 for n = 1, 2, …, T and thus u′ = \overline{ω} ∈ R(T, k). So, by Lemma 2.9 we have that u ∈ R(T, k). For the dual unbalance \underline{I}(u) the proof is completely analogous. □

Lemma 2.22 Let u, u′, v, v′ ∈ P(T, k). Then u ∼ u′ , v ∼ v′, u ⪰ v ⪰ \overline{ω} and v′ ⪰ u′ ⪰ \overline{ω} implies u = v and u′ = v′.

Proof. By Lemma 2.18, the given orders and the definition of \overline{I}(u) we have that \overline{I}(u) = \overline{I}(u′), \overline{I}(v) = \overline{I}(v′), \overline{I}(u) ≥ \overline{I}(v) and \overline{I}(v′) ≥ \overline{I}(u′). Hence \overline{I}(u) = \overline{I}(u′) = \overline{I}(v′) =\overline{I}(v) and thus u = v and u′ = v′. □

In the sequel we denote the set of conjugacy classes of P(T, k) by P̃(T, k) and we denote the conjugacy class of regular sequences in P(T, k) by ω̃(T, k) or just ω̃. We now define a partial order ⊴\overline{g} and a partial order ⊴\underline{g} on P̃(T, k).

Definition 2.23 Let ũ, ṽ ∈ P̃(T, k). Then ũ ⊴\overline{g} ṽ if there exist u′, v′ ∈ P(T, k) such that u′ ∈ ũ, v′ ∈ ṽ and \overline{ω} ⪯ u′ ⪯ v′. Further ũ ⊴\underline{g} ṽ if there exist u′′, v′′ ∈ P(T, k) such that u′′ ∈ ũ, v′′ ∈ ṽ and \underline{ω} ⪯′ u′′ ⪯′ v′′.

Suppose that ũ ⊴\overline{g} ṽ for some u, v ∈ P(T, k) and let u′, v′ be as in Definition 2.23. Then the graph of u′ is never above the graph of v′ and they are both never below the graph of \overline{ω}. Therefore we call ⊴\overline{g} the upper graph order and similarly we call ⊴\underline{g} the lower graph order.

Lemma 2.24 ⊴\overline{g} and ⊴\underline{g} are indeed partial orders on P̃(T, k) .

Proof. From Theorem 2.13 the reflexivity of ⊴\overline{g} follows and from Lemma 2.22 the antisymmetry. Further the transitivity of ⊴\overline{g} follows directly from the definition and thus ⊴\overline{g} is a partial order on P̃(T, k). The proof that ⊴\underline{g} is a partial order on P̃(T, k) is completely analogous. □

As a direct consequence of Theorem 2.13 and the ” dual ” Theorem 2.14 we have the following result.

Lemma 2.25 The conjugacy class ω̃ is the smallest element of P̃(T, k) with respect to the order ⊴\overline{g} and also with respect to the order ⊴\underline{g}.

We say that ũ ◁\overline{g} ṽ if ũ ⊴\overline{g} ṽ and ũ ≠ ṽ and similar for the other partial orders. The following theorem follows directly from the definitions.

Theorem 2.26 Let u, v ∈ P(T, k). Then ũ ⊴\overline{g} ṽ implies \overline{I}(u) ≤ \overline{I}(v) and ũ ⊴\underline{g} ṽ implies \underline{I}(u) ≤ \underline{I}(v). Moreover, ũ ◁\overline{g} ṽ implies \overline{I}(u) < \overline{I}(v) and ũ ◁\underline{g} ṽ implies \underline{I}(u) < \underline{I}(v).

The orders ⊴\overline{g} and ⊴\underline{g} are in general not the same on P̃(T, k). For example if u = (1, 0, 1, 0, 0, 0, 1, 0, 0) ∈ P(9, 3) and v = (1, 0, 1, 0, 0, 1, 0, 0, 0) ∈ P(9, 3) then ũ ◁\overline{g} ṽ and ṽ ◁\underline{g} ũ. Therefore it is useful to define the partial order ⊴_{g} on P̃(T, k) as ”intersection” of the orders ⊴\overline{g} and ⊴\underline{g}. We call ⊴_{g} the (strong) graph order.

Definition 2.27 Let ũ, ṽ ∈ P̃(T, k). Then ũ ⊴_{g} ṽ if ũ ⊴\overline{g} ṽ and ũ ⊴\underline{g} ṽ.

Remark. The partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on P̃(T, k) induce in a natural way corresponding preorders on P(T, k). For example for u, v ∈ P(T, k) we say that u ⊴_{g} v if ũ ⊴_{g} ṽ and similar for the other orders. However, if the orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} are used on P(T, k) in this way then they are not antisymmetric, since cyclic permutations of u are different words and therefore they are not partial orders on P(T, k).

Now that we have defined the unbalance and several orders for finite sequences we will extend these notions to infinite periodic sequences (words). First of all we extend in a natural way the partial order ⪯ and its dual order ⪯′ to the infinite sequences u = (u_{1}, u_{2}, …) of zeros and ones corresponding to ℕ-words on the alphabet {0, 1}. We define just as for finite sequences (words) the counting function κ_{u} : ℤ_{≥0} → ℤ by κ_{u}(n) = ∑_{t=1}^{n} u_{t} and we say that u ⪯ v if κ_{u}(n) ≤ κ_{v}(n) for n = 1, 2, . . .. For a sequence u = (u_{1}, u_{2}, …) of zeros and ones of density d corresponding to an ℕ - word we also define the discrepancy function χ_{u} : ℤ_{≥0} → ℝ by χ_{u}(n) = n · d − κ_{u}(n) for n ∈ ℤ_{≥0}. Further we have the following equivalence relation ∼ for infinite periodic sequences. In fact ∼ is an equivalence relation for all infinite periodic integer sequences and the corresponding words on a finite alphabet A and not only for the sequences of zeros and ones.

Definition 2.28 Let u and v be infinite periodic integer sequences. Then we say that u is equivalent to v, u ∼ v if there exists a finite sequence w such that w is a period cycle of both u and v.

In our application of routing sequences in a queueing system we have in general that equivalent infinite periodic sequences have the same performance. Therefore in most cases we consider infinite periodic sequences modulo this equivalence relation, i.e if u ∼ v then we consider them as the same sequence. This is also necessary for the several partial orders that we define on infinite periodic sequences of zeros and ones to be antisymmetric. Further an infinite periodic sequence is now completely determined by a period cycle of the sequence. If u ∈ P(T, k) then u^{∞} = (u_{1}, u_{2}, …, u_{T})^{∞} is the infinite periodic sequence with period cycle u.

Let P be the set of infinite periodic sequences of zeros and ones (modulo the equivalence relation), R ⊆ P the subset of regular periodic sequences. Further for d ∈ ℚ, 0 ≤ d ≤ 1 let P(d) ⊆ P be the subset of sequences with density d and R(d) := R ∩ P(d). Then we have the following lemma.

Lemma 2.29 We have that

P = ∪_{d∈ℚ,0≤d≤1}P(d),

R = ∪_{d∈ℚ,0≤d≤1}R(d)

and |R(d)| = 1 for every d ∈ ℚ, 0 ≤ d ≤ 1 .

Proof. If u ∈ P then there exist k ∈ ℤ_{≥0} , T ∈ ℕ , k ≤ T such that u = v^{∞} for some v ∈ P(T, k) and thus u ∈ P(\frac{k}{T}) = P(d) for some d ∈ Q , 0 ≤ d ≤ 1. Hence

P = ∪_{d∈ℚ,0≤d≤1}P(d)

and thus

R = R ∩ P = R ∩ {∪_{d∈ℚ,0≤d≤1}P(d)} = ∪_{d∈ℚ,0≤d≤1}R(d).

By Lemma 2.9 we have that |R(d)| = 1 for every d ∈ ℚ, 0 ≤ d ≤ 1. □

We denote the unique element of R(d) by ω(d) for every d ∈ ℚ, 0 ≤ d ≤ 1. We now define the primal and dual unbalance for infinite periodic sequences.

Definition 2.30 Let u ∈ P and let u′ ∈ P(T, k) be a period cycle of u. Then we define the primal unbalance of u as \overline{I}(u) := \overline{I}(u′) and we define the dual unbalance of u as \underline{I}(u) := \underline{I}(u′).

Lemma 2.31 The primal unbalance \overline{I} and dual unbalance \underline{I} are well defined on P.

Proof. Suppose u′ and u′′ are both period cycles of u. Then we have to show that \overline{I}(u′) = \overline{I}(u′′). There exists a primitive period cycle w of u such that u′ ∼ w^{m} and u′′ ∼ w^{n} for some m, n ∈ ℕ. Then by Lemma 2.18 and Lemma 2.20 we have that \overline{I}(u′) = \overline{I}(w) = \overline{I}(u′′). Hence \overline{I} is well defined on P and completely analogously it follows that \underline{I} is well defined on P. □

Remark. When the unbalance of an infinite periodic sequence has to be computed it is of course most practical to compute the unbalance of a primitive period cycle of the sequence and not an arbitrary period cycle.

Suppose that u, v ∈ P(d) for some d ∈ ℚ, 0 ≤ d ≤ 1. Then we say that u, v are mirrors of each other if there exist u′, v′ such that u′ and v′ are period cycles of u respectively v and u′ and v′ are mirrors of each other. By proposition 2.19 and the definitions of the primal and dual unbalance for infinite period sequences of zeros and ones we have the following corollary.

Corollary 2.32 Suppose that u, v ∈ P(d) for some d ∈ ℚ, 0 ≤ d ≤ 1 and u and v are mirrors of each other. Then \overline{I}(u) = \underline{I}(v) and \underline{I}(u) = \overline{I}(v).

Now that we have defined the primal and dual unbalance on P we also define for every d ∈ ℚ, 0 ≤ d ≤ 1 the partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on P(d). Let u, v ∈ P(d) and let f_{1} be the period of u and f_{2} the the period of v. Then by Lemma 2.3 we have that u and v have both period T := lcm(f_{1}, f_{2}). Moreover, if u′ is a period cycle of length T of u and v′ is a period cycle of length T of v then we have that u′ ∈ P(T, d · T) and v′ ∈ P(T, d · T).

Definition 2.33 Let u, v ∈ P(d) for some d ∈ Q, 0 ≤ d ≤ 1 and let u′, v′ ∈ P(T, d·T) be corresponding period cycles as above. Then we define the partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on P(d) by

u ⊴\overline{g} v if ũ′ ⊴\overline{g} ṽ′ in P̃(T, d · T),
u ⊴\underline{g} v if ũ′ ⊴\underline{g} ṽ′ in P̃(T, d · T) and
u ⊴_{g} v if ũ′ ⊴_{g} ṽ′ in P̃(T, d · T).

All the results we had for the partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on P̃(T, k) we also have for the partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on P(d). They are indeed partial orders and we have the following results.

Lemma 2.34 For every d ∈ ℚ , 0 ≤ d ≤ 1, we have that the regular sequence ω(d) is the smallest element of P(d) with respect to the order ⊴\overline{g} , the order ⊴\underline{g} and with respect to the order ⊴_{g}.

Theorem 2.35 Let u, v ∈ P(d). Then u ⊴\overline{g} v implies \overline{I}(u) ≤ \overline{I}(v) and u ⊴\underline{g} v implies \underline{I}(u) ≤ \underline{I}(v). Moreover, u ◁\overline{g} v implies \overline{I}(u) < \overline{I}(v) and u ◁\underline{g} v implies \underline{I}(u) < \underline{I}(v).

We give an example to illustrate this . Let u = (1, 1, 0, 1, 0, 0)^{∞} ∈ P(\frac{1}{2}) and v = (1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0)^{∞} ∈ P(\frac{1}{2}). Then we have that u ◁\overline{g} v, v ◁\underline{g} u and (thus) u and v are not ⊴_{g} ordered. Further \overline{I}(u) = \frac{1}{3}, \overline{I}(v) = \frac{5}{12}, \underline{I}(u) = \frac{1}{6} and \underline{I}(v) = \frac{1}{12}.

3 Bounding the difference between sequences in expected average waiting time

Let {T_{i}}_{i=1,2,...} be a sequence of arrival times of customers, with the convention that T_{1} = 0. Put δ_{i} := T_{i+1}−T_{i} for i = 1, 2, . . .. Then {δ_{i}} is the sequence of interarrival times. Further a fraction of these arriving customers is routed to a server according to some routing sequence u = (u_{1}, u_{2}, …) of zeros and ones. For such a routing sequence we have the counting function κ_{u}(n) = ∑_{t=1}^{n} u_{t} that we used to define a partial order ⪯ for such routing sequences. Further we define the the following related function ν_{u}(i) : ℤ_{≥0} → ℤ with ν_{u}(j) = min{n ∈ ℤ_{≥0} : κ_{u}(n) = j} and we put τ_{u}(j) = ∑_{i=max(ν_{u}(j−1),1)}^{ν_{u}(j)−1} δ_{i} for j = 1, 2, …. Then τ_{u}(j) is the time elapsed between the routing of the j − 1-th and j-th customer to the server according to routing sequence u. If we put λ_{u}(j) = ∑_{k=1}^{j} τ_{u}(k) for j = 1, 2, … then λ_{u}(j) is the time at which the j − th customer is routed to the server according to routing sequence u. Further we have a sequence of service times {σ_{j}}_{j=1,2,...}, where σ_{j} is the service time of the j-th customer that is routed to the server according to any routing sequence. For now we assume that the interarrival times {δ_{i}}_{i=1,2,...} and service times {σ_{j}}_{j=1,2,...} are fixed sequences of non-negative real numbers. Later we will also consider the case that these are random variables. Further we define W_{u}(j, w) to be the workload for the server at the moment the j-th customer is routed to the server according to routing sequence u, given that the initial workload at time T_{1} = 0 is equal to w. In other words W_{u}(j, w) is the waiting time for the j -th customer that is routed to the server. If the initial workload w is fixed (thus the system starts for all routing sequences u with the same initial workload w) then we write for short W_{u}(j) in stead of W_{u}(j, w). For example this is the case if it is assumed that the server is empty at T_{1} = 0. Note that W_{u}(j) + λ_{u}(j) is the moment that the server starts serving the j-th customer that is routed to the server. We have the following lemma.

Lemma 3.1 Let u = (u_{1}, u_{2}, …) and v = (v_{1}, v_{2}, …) be routing sequences as above. If u ⪯ v and W_{v}(j, w) + λ_{v}(j) ≤ W_{u}(j, w′) + λ_{u}(j) for some j ∈ ℕ then for every k ≥ j we have that W_{v}(k, w) + λ_{v}(k) ≤ W_{u}(k, w′) + λ_{u}(k).

Proof. It suffices to show the assertion for k = j + 1, because it then follows with induction. We have that W_{v}(j+1, w) = max(W_{v}(j, w)+σ_{j}−τ_{v}(j+1), 0) and W_{u}(j+1, w′) = max(W_{u}(j, w′)+σ_{j}−τ_{u}(j+1), 0). Further λ_{u}(j + 1) − λ_{v}(j + 1) ≥ 0 since u ⪯ v. Hence

W_{v}(j + 1, w) ≤ max(W_{u}(j, w′) + λ_{u}(j) − λ_{v}(j) + σ_{j} − τ_{v}(j + 1), 0) ≤
max(W_{u}(j, w′) + σ_{j} − τ_{u}(j + 1), 0) + max(λ_{u}(j + 1) − λ_{v}(j + 1), 0) =
W_{u}(j + 1, w′) + λ_{u}(j + 1) − λ_{v}(j + 1).
□

If w = w′ then the inequality holds for j = 1 and thus we have the following corollary.

Corollary 3.2 Let u and v as above, u ⪯ v. Then W_{v}(j) + λ_{v}(j) ≤ W_{u}(j) + λ_{u}(j) for every j ∈ ℕ.

Note that for every j ∈ ℕ we have that λ_{u}(j) − λ_{v}(j) = ∑_{i=ν_{v}(j)}^{ν_{u}(j)−1} δ_{i}. This is a sum of interarrival times δ_{i}, where the number of terms in the sum is ν_{u}(j) − ν_{v}(j). Therefore, if we put N_{uv}(m) = ∑_{j=1}^{m}(ν_{u}(j) − ν_{v}(j)) for m = 1, 2, … then we have by the following lemma by Corollary 3.2.

Lemma 3.3 Let u and v be routing sequences with u ⪯ v. For every m ∈ ℕ we have that

∑_{j=1}^{m} W_{v}(j) ≤ ∑_{j=1}^{m} W_{u}(j) + ∑_{j=1}^{m} ∑_{i=ν_{v}(j)}^{ν_{u}(j)−1} δ_{i}.  (3)

In the double sum the number of terms is N_{uv}(m).

Since for every sequence u = (u_{1}, u_{2}, …) the functions κ_{u} and ν_{u} are strongly related , we can also use the counting function κ instead of ν to find an expression for N_{uv}(m). Namely, we have the following lemma.

Lemma 3.4 Let u = (u_{1}, u_{2}, …) and v = (v_{1}, v_{2}, …) be sequences of zeros and ones. Then we have for every m ∈ ℕ that

∑_{j=1}^{m}(ν_{u}(j) − ν_{v}(j)) = ∑_{n=1}^{max(ν_{u}(m),ν_{v}(m))}{min(m, κ_{v}(n)) − min(m, κ_{u}(n))}.

Proof. We prove it by induction to m. For m = 1 we may assume that ν_{u}(1) ≥ ν_{v}(1). Then we have that

ν_{u}(1) − ν_{v}(1) = ∑_{n=ν_{v}(1)}^{ν_{u}(1)−1} 1 = ∑_{n=1}^{ν_{u}(1)−1} min(1, κ_{v}(n)) =

∑_{n=1}^{max(ν_{u}(1),ν_{v}(1))}{min(1, κ_{v}(n)) − min(1, κ_{u}(n))}.

Similarly we have for m = 2, 3, … that

ν_{u}(m) − ν_{v}(m) = ∑_{n=min(ν_{u}(m),ν_{v}(m))}^{max(ν_{u}(m),ν_{v}(m))−1}{min(κ_{v}(n), κ_{u}(n) + 1) − min(κ_{u}(n), κ_{v}(n) + 1)}.

So, by induction we have for m = 2, 3, … that

∑_{j=1}^{m}(ν_{u}(j) − ν_{v}(j)) = ∑_{j=1}^{m−1}(ν_{u}(j) − ν_{v}(j)) + (ν_{u}(m) − ν_{v}(m)) =

∑_{n=1}^{max(ν_{u}(m−1),ν_{v}(m−1))}{min(m − 1, κ_{v}(n)) − min(m − 1, κ_{u}(n))} +

∑_{n=min(ν_{u}(m),ν_{v}(m))}^{max(ν_{u}(m),ν_{v}(m))−1}{min(κ_{v}(n), κ_{u}(n) + 1) − min(κ_{u}(n), κ_{v}(n) + 1)} =

∑_{n=1}^{max(ν_{u}(m),ν_{v}(m))}{min(m, κ_{v}(n)) − min(m, κ_{u}(n))}.

□

Corollary 3.5 Let u and v be sequences as above and suppose that for some l, m ∈ N we have that κ_{u}(l) = κ_{v}(l) = m. Then N_{uv}(m) = ∑_{n=1}^{l}(κ_{v}(n) − κ_{u}(n)).

For periodic sequences of the same density we have the following lemma.

Lemma 3.6 Suppose that u = (u′)^{∞} and v = (v′)^{∞} for some u′, v′ ∈ P(T, k) and \overline{ω}(T, k) ⪯ u′ ⪯ v′. Then if m = sk for some s ∈ ℕ we have that N_{uv}(m) = s · T · (\overline{I}(v) − \overline{I}(u)).

Proof. Let m = sk with s/in/N. Then κ_{u}(sT) = κ_{v}(sT) = sk. So, by Corollary 3.5 we have that N_{uv}(m) = ∑_{n=1}^{sT}(κ_{v}(n) − κ_{u}(n)). So, since {κ_{v}(n) − κ_{u}(n)} is periodic with period T we have that

N_{uv}(m) = ∑_{n=1}^{sT}(κ_{v}(n) − κ_{u}(n)) = s · ∑_{n=1}^{T}(κ_{v}(n) − κ_{u}(n)) =

s · ∑_{n=1}^{T}\{(κ_{v}(n) − κ\overline{ω}(n)) − (κ_{u}(n) − κ\overline{ω}(n))\} = s · T · (\overline{I}(v) − \overline{I}(u)).

□

Corollary 3.7 Suppose that u = (u′)^{∞} and v = (v′)^{∞} for some u′, v′ ∈ P(T, k) and \overline{ω}(T, k) ⪯ u′ ⪯ v′. Then for every m ∈ ℕ we have that

⌊\frac{m}{k}⌋ · T · (\overline{I}(v) − \overline{I}(u)) ≤ N_{uv}(m) ≤ ⌈\frac{m}{k}⌉ · T · (\overline{I}(v) − \overline{I}(u))

and lim_{m→∞} \frac{N_{uv}(m)}{m} = \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)).

Proof. Because u′ ⪯ v′ we have that u ⪯ v and it follows that N_{uv}(m) is monotonically non-decreasing in m. Therefore the first statement follows from Lemma 3.6 and the second statement follows from the first. □.

By Lemma 3.3 and Corollary 3.7 we have the following theorem.

Theorem 3.8 Let u and v be as in Corollary 3.7. Suppose that for {δ_{i}}_{i=1,2,...}, the sequence of interarrival times, we have for l = 1, 2, …, T that lim sup_{t→∞} \frac{1}{t} · ∑_{i=0}^{t−1} δ_{i·T +l} := γ_{l} ≤ δ. Then

lim sup_{m→∞} \frac{1}{m} · (∑_{j=1}^{m} W_{v}(j) − ∑_{j=1}^{m} W_{u}(j)) ≤ δ · \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)).

Proof. By Lemma 3.3 together with some straightforward derivations,

lim sup_{m→∞} \frac{1}{m} · (∑_{j=1}^{m} W_{v}(j) − ∑_{j=1}^{m} W_{u}(j)) ≤ lim sup_{m→∞} \frac{N_{uv}(m)}{m} · max_{l=1,... ,T} γ_{l} ≤ δ · lim sup_{m→∞} \frac{N_{uv}(m)}{m}.

Hence by Corollary 3.7

lim sup_{m→∞} \frac{1}{m} · (∑_{j=1}^{m} W_{v}(j) − ∑_{j=1}^{m} W_{u}(j)) ≤ δ · \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)).

□

Let u be a routing sequences of zeros and ones. If the interarrival times {δ_{i}} and service times {σ_{j}} are fixed sequences then we say that \overline{W} (u) is the long-run average waiting time of customers routed to the server according to routing sequence u if lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}(j) = \overline{W} (u). So, if lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}(j) exists then we say that \overline{W} (u) exists. If \overline{W} (u) exists, but the value depends on the initial workload w then \overline{W} (u) denotes the value for initial workload w = 0 (thus the server is assumed to be empty at T_{1} = 0 in that case). If the interarrival times \{δ_{i}\} and service times \{σ_{j}\} are random variables then we say that \overline{W} (u) is the almost sure long-run average waiting time of customers routed to the server according to routing sequence u if lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}(j) = \overline{W} (u) with probability one. So, if in case of random variables lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}(j) almost surely (a.s.) exists then we say that \overline{W} (u) exists and again if the value of \overline{W} (u) would depend on the initial workload w then \overline{W} (u) denotes the value for w = 0.

Theorem 3.8 has the following corollary.

Corollary 3.9 Let \{δ_{i}\}, u and v be as in Theorem 3.8. If \overline{W} (u) and \overline{W} (v) exist then

\overline{W} (v) − \overline{W} (u) ≤ δ · \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)).

From ergodic theory we have the following theorem for stochastic interarrival and service times. In fact a more general result will be proved in the appendix (see Theorem 6.1).

Theorem 3.10 Suppose that the interarrival times {δ_{i}} of customers arriving at the system are independent and identically distributed (i.i.d.) random variables with mean δ and the service times {σ_{j}} of the considered server are i.i.d. random variables with mean σ which are independent of the interarrival times. Further let u′ and u′′ be routing sequences of zeros and ones that are both representatives of some u ∈ P(d) with d ∈ ℚ and \frac{σ}{δ} · d < 1. Then \overline{W} (u′) and \overline{W} (u′′) exist and are finite. Moreover \overline{W} (u′) = \overline{W} (u′′) and the long-run average waiting time does not depend on the initial workload w.

Notation. Let δ , σ and d be as in Theorem 3.10. Then we say that ρ := \frac{σ}{δ} · d is the traffic intensity for the server.

By Theorem 3.10 all the routing sequences which are representatives of some given u ∈ P(d) have the same long-run average waiting time if the stability condition ρ < 1 is fulfilled. Therefore we denote this long-run average waiting time simply by \overline{W} (u) for u ∈ P(d).

Theorem 3.11 Let the interarrival times {δ_{i}} and the service times {σ_{j}} be as in Theorem 3.10. Further let u, v ∈ P(d) for some d ∈ ℚ such that the traffic intensity ρ < 1 and u ⊴\overline{g} v. Then

\overline{W} (v) − \overline{W} (u) ≤ \frac{δ}{d}(\overline{I}(v) − \overline{I}(u)).

Proof. Since u, v ∈ P(d) with d ∈ ℚ and u ⊴\overline{g} v there exist T, k ∈ ℕ , u′, v′ ∈ P(T, k) and routing sequences u′′, v′′ such that d = \frac{k}{T}, \overline{ω}(T, k) ⪯ u′ ⪯ v′ , u′′ = (u′)^{∞} is representative of u and v′′ = (v′)^{∞} is representative of v. By Theorem 3.10 we have that both \overline{W} (u) = \overline{W} (u′′) and \overline{W} (v) = \overline{W} (v′′) exist. Let the sequence {δ_{i}(u′′)}_{i=1,2,...} be a realisation of the sequence of interarrival times when routing sequence u′′ is used and let the sequence {δ_{i}(v′′)}_{i=1,2,...} be a realisation of the interarrival times when routing sequence v′′ is used. Because they are sequences of i.i.d. random variables we make the coupling that δ_{i}(u′′) = δ_{i}(v′′) = δ_{i} for i = 1, 2, … where the sequence {δ_{i}} is a realisation of the sequence of interarrival times. Let the sequence {σ_{j}(u′′)}_{j=1,2,...} be a realisation of the sequence of service times when routing sequence u′′ is used and let the sequence {σ_{j}(v′′)}_{j=1,2,...} be a realisation of the service times when routing sequence v′′ is used. Because they are sequences of i.i.d random variables we make the coupling that σ_{j}(u′′) = σ_{j}(v′′) = σ_{j} for j = 1, 2, … where the sequence {σ_{j}} is a realistation of the sequence of service times. Let W_{u′′}^{c}(j), W_{v′′}^{c}(j) be the workload for the server at the moment the j-th customer is routed to the server according to routing sequence u′′ respectively v′′ with this coupling of the interarrival times and service times. Then by Theorem 3.10 lim_{m→∞} \frac{1}{m} ·∑_{j=1}^{m} W_{u′′}^{c}(j) = \overline{W} (u′′) = \overline{W} (u) with probability one and lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{v′′}^{c}(j) = \overline{W} (v′′) = \overline{W} (v) with probability one. Further for every T ∈ ℕ and l ∈ ℕ we have that lim_{t→∞} \frac{1}{t} · ∑_{i=0}^{t−1} δ_{i·T +l} = δ with probability one and thus we have analogously to Theorem 3.8 that

lim sup_{m→∞} \frac{1}{m} · \{∑_{j=1}^{m} W_{v′′}^{c}(j) − ∑_{j=1}^{m} W_{u′′}^{c}(j)\} ≤ δ · \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)) = \frac{δ}{d}(\overline{I}(v) − \overline{I}(u))

with probability one. Hence \overline{W} (v) − \overline{W} (u) ≤ \frac{δ}{d}(\overline{I}(v) − \overline{I}(u)). □

By Theorem 3.11 and the results in the previous section we have the following corollary.

Corollary 3.12 Let the interarrival times {δ_{i}} and the service times {σ_{j}} be as in Theorem 3.10. Further let u ∈ P(d) for some d ∈ ℚ such that ρ < 1 and let ω = ω(d) be the regular sequence of density d. Then

\overline{W} (u) ≤ \overline{W} (ω) + \frac{δ}{d} · \overline{I}(u).

We also have the dual results of Theorem 3.11 and Corollary 3.12. In these dual results the dual unbalance \underline{I} is used instead of the primal unbalance \overline{I}. These can be proved completely analogously using the dual order instead of the primal order. The dual results of Theorem 3.11 and Corollary 3.12 are the following.

Theorem 3.13 Let the interarrival times {δ_{i}} and the service times {σ_{j}} be as in Theorem 3.10. Further let u, v ∈ P(d) for some d ∈ ℚ such that ρ < 1 and u ⊴\underline{g} v. Then

\overline{W} (v) − \overline{W} (u) ≥ \frac{δ}{d}(\underline{I}(u) − \underline{I}(v)).

Corollary 3.14 Let the interarrival times {δ_{i}} and the service times {σ_{j}} be as in Theorem 3.10. Further let u ∈ P(d) for some d ∈ ℚ such that ρ < 1 and let ω = ω(d) be the regular sequence of density d. Then

\overline{W} (u) ≥ \overline{W} (ω) − \frac{δ}{d} · \underline{I}(u).

Remark. Contrary to Corollary 3.12 this dual result Corollary 3.14 is not useful for this type of routing system, because if u and ω are as in these corollaries then it is known that \overline{W} (u) ≥ \overline{W} (ω) (See [3] and [5]).

In Theorem 3.10 we assume that the interarrival times {δ_{i}} are i.i.d. random variables with mean δ and the service times {σ_{j}} are i.i.d. random variables with mean σ. So, the results hold in particular if the interarrival and service times are deterministic, i.e the interarrival times are all equal to δ and the service times are all equal to σ. Further in this case the assumption that the traffic intensity ρ < 1 can be relaxed to ρ ≤ 1. Since the long-run average waiting time depends on the initial workload w if ρ = 1 we assume that the queue is empty at T_{1} = 0, i.e the initial workload w = 0 in this case. In [28] it is shown that Theorem 3.10 (except the statement that the long-run average waiting does not depend on the initial workload) in this deterministic case also holds for ρ = 1. Since ρ < 1 was only needed to prove Theorem 3.10 it follows that results following after Theorem 3.10 also hold for ρ = 1 in this deterministic case. In fact for routing to a deterministic queue and deterministic interarrival times with traffic intensity ρ = 1 we have instead of Theorem 3.11 and Corollary 3.12 the following stronger result.

Theorem 3.15 Suppose that the interarrival times and service times are deterministic and equal to δ respectively σ. Further suppose that the queue is initially empty. Let u ∈ P(d) for some d ∈ ℚ such that δ = dσ, hence ρ = 1, and let ω = ω(d) be the regular sequence of density d. Then

\overline{W} (u) = \overline{W} (ω) + \frac{δ}{d} · \overline{I}(u).

Proof. Let d = \frac{k}{T} with gcd(k, T) = 1. Let \overline{ω} = (\overline{ω}(T, k))^{∞}, which is a representative of ω. Let u′ ∈ P(T, k) such that \overline{ω}(T, k) ⪯ u′ and u′′ := (u′)^{∞} is a representative of u. From [28] we have that \overline{W} (ω) = \overline{W} (\overline{ω}) = lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W\overline{ω}(j) and \overline{W} (u) = \overline{W} (u′′) = lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u′′}(j). For both routing sequence \overline{ω} and u′′ the server is always busy serving customers from T_{1} = 0. Namely, let t_{0} ∈ ℝ_{≥0} be arbitrarily. Since customers arrive at times 0, δ, 2δ, … the number of customers routed to the server before time t_{0} according to routing sequence \overline{ω} is κ\overline{ω}(⌈\frac{t_{0}}{δ} ⌉) ≥ ⌈\frac{t_{0}}{δ} d⌉ = ⌈\frac{t_{0}}{σ} ⌉. Since the server could not start earlier with the serving of these customers than at time T_{1} = 0 and each of them has a serving time of σ, the server is not finished with serving these customers before time σ · ⌈\frac{t_{0}}{σ} ⌉ ≥ t_{0}. So, for routing sequence \overline{ω} the server is always busy from T_{1} = 0 and this follows analogously for routing sequence u′′. From this and the fact that the server is assumed to be empty at T_{1} = 0 it follows that W_{u′′}(j) + λ_{u′′}(j) = W\overline{ω}(j) + λ\overline{ω}(j) = (j − 1)σ for every j ∈ ℕ. Therefore we have for every m ∈ ℕ that (3) holds with equality for u′′ and \overline{ω} with δ_{i} = δ for i = 1, 2, . . .. Thus

∑_{j=1}^{m} W_{u′′}(j) − ∑_{j=1}^{m} W\overline{ω}(j) = ∑_{j=1}^{m} ∑_{i=ν_{u′′}(j)}^{ν\overline{ω}(j)−1} δ = δ · N_{\overline{ω}u′′}(m)

for every m ∈ ℕ. Hence by Corollary 3.7 we have that

\overline{W} (u) − \overline{W} (ω) = δ · lim_{m→∞} \frac{N_{\overline{ω}u′′}(m)}{m} = δ · \frac{T}{k} · \overline{I}(u′′) = \frac{δ}{d} · \overline{I}(u).

□

According to Theorem 3.15 the inequalities of Theorem 3.11 and Corollary 3.12 hold with equality for routing to a deterministic queue with traffic intensity ρ = 1 if the interarrival times are deterministic. For non-deterministic interarrival and service times the inequalities of Theorem 3.11 and Corollary 3.12 are rather tight if ρ is close to 1, or in other words if the traffic is heavy.

4 Routing to parallel queues

In this section we derive upper bounds on the average waiting time for routing customers to parallel queues according to some (periodic) routing policy. We assume that we have N ≥ 2 parallel servers. Then a routing policy ψ corresponds to an ℕ - word (integer sequence) U = (U_{1}, U_{2}, …) on the alphabet {1, 2, …, N}, where U_{i} is the server to which the i-th arriving customer is routed according to policy ψ. If the applied policy and thus also the corresponding word are both periodic we have for some T ∈ ℕ that U_{1}, U_{2}, …, U_{T} is a primitive period cycle of the word. Then we say that T is the period of the applied policy ψ and we denote ψ and the corresponding word U as (U_{1}, U_{2}, …, U_{T})^{∞}.

Definition 4.1 Let ψ and U be as above. Then for t ∈ ℕ we define W (t) = W_{ψ}(t) as the waiting time of the t -th arriving customer if policy ψ is applied, which is the remaining workload for server U_{t} at the moment that the t-th customer arrives. If the interarrival times and service times of all servers are fixed sequences then we say that \overline{W} (ψ) = \overline{W} (U) is the long-run average waiting time of the arriving customers routed according to policy ψ if lim_{τ→∞} \frac{1}{τ} · ∑_{t=1}^{τ} W_{ψ}(t) = \overline{W} (ψ) and the system is empty at T_{1} = 0. If the interarrival times and service times of the several servers are random variables then we say that \overline{W} (ψ) = \overline{W} (U) is the almost sure long-run average waiting time of the arriving customers routed according to policy ψ if lim_{τ→∞} \frac{1}{τ} · ∑_{t=1}^{τ} W_{ψ}(t) = \overline{W} (ψ) with probability one and the system is empty at T_{1} = 0.

Notation. If U is an ℕ -word (not necessarily periodic) on the alphabet {1, 2, …, N} (corresponding to some routing policy) then for i = 1, 2, …, N we denote by u^{i} = (u_{1}^{i}, u_{2}^{i}, …) the corresponding routing sequence of zeros and ones for server i, i.e u_{t}^{i} = \{ \begin{matrix}1 & if U_{t} = i \\ 0 & if U_{t} ≠ i \end{matrix} . For i = 1, 2, …, N and t ∈ ℕ

we put A^{t}(i) := {t′ ∈ ℕ : u_{t′}^{i} = 1} ∩ {1, 2, …, t}. Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. We denote by S(d_{1}, d_{2}, …, d_{N}) all the infinite ℕ -words U = (U_{1}, U_{2}, …) on the alphabet {1, 2, …, N} such that u^{i} has density d_{i} for i = 1, 2, …, N. If U is periodic then we have for every i ∈ {1, 2, …, N} that u^{i} ∈ P(d) for some d ∈ ℚ. Let d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} such that ∑_{i=1}^{N} d_{i} = 1. Then we denote by Q(d_{1}, d_{2}, …, d_{N}) all the infinite periodic ℕ - words U on the alphabet {1, 2, …, N} for which u^{i} ∈ P(d_{i}) for i = 1, 2, …, N. Further for T, k_{1}, k_{2}, …, k_{N} ∈ ℕ with ∑_{i=1}^{N} k_{i} = T we denote by Q({T }, k_{1}, k_{2}, …, k_{N}) all the infinite ℕ-words on the alphabet {1, 2, …, N} for which every subword of length T contains exactly k_{i} letters i for i = 1, 2, …, N.

Note that Q(\{T \}, k_{1}, k_{2}, …, k_{N}) ⊆ Q(\frac{k_{1}}{T} , \frac{k_{2}}{T} , …, \frac{k_{N}}{T}) and Q(d_{1}, d_{2}, …, d_{N}) ⊆ S(d_{1}, d_{2}, …, d_{N}). Let ψ be a periodic routing policy with period T and U the corresponding word on the alphabet {1, 2, …, N}. Then there exist non-negative integers k_{1}, k_{2}, …, k_{N} with ∑_{i=1}^{N} k_{i} = T such that from T consecutively arriving customers policy ψ routes exactly k_{i} of them to server i for i = 1, 2, …, N. Hence U ∈ Q(\{T \}, k_{1}, k_{2}, …, k_{N}) ⊆ Q(\frac{k_{1}}{T} , \frac{k_{2}}{T} , …, \frac{k_{N}}{T}) ⊆ S(\frac{k_{1}}{T} , \frac{k_{2}}{T} , …, \frac{k_{N}}{T}). Vice versa if U ∈ Q(d_{1}, d_{2}, …, d_{N}) with d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N and ∑_{i=1}^{N} d_{i} = 1 then there exist T, k_{1}, k_{2}, …, k_{N} ∈ ℕ with ∑_{i=1}^{N} k_{i} = T such that U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}). Further for every server i ∈ {1, 2, …, N} we have a corresponding routing sequence u^{i} = (u_{1}^{i}, u_{2}^{i}, …, u_{T}^{i})^{∞} ∈ P(d_{i}) where d_{i} = \frac{k_{i}}{T}. For example if U = (1, 2, 1, 2, 1, 3, 1, 2, 1, 1, 2, 3)^{∞} then U ∈ Q(\{12\}, 6, 4, 2) ⊆ Q(\frac{1}{2}, \frac{1}{3}, \frac{1}{6}). Further u^{1} = (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0)^{∞} ∈ P(\frac{1}{2}), u^{2} = (0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0)^{∞} ∈ P(\frac{1}{3}) and u^{3} = (0, 0, 0, 0, 0, 1)^{∞} ∈ P(\frac{1}{6}).

Let {δ_{i}} be the sequence of interarrival times and let {σ_{j}^{i}} be the sequence of service times of server i for i = 1, 2, …, N, i.e σ_{j}^{i} is the service time of the j - th customer that is routed to server i. We define \overline{W}^{i}(ψ) = \overline{W}^{i}(u^{i}) as the long-run average waiting time of customers routed to server i if policy ψ is applied in the same way as in the previous section. The only differences are that routing sequence u is replaced by routing sequence u^{i} and the sequence of service times {σ_{j}} is replaced with the sequence of service times {σ_{j}^{i}}. We have the following theorem.

Theorem 4.2 Suppose that the interarrival times {δ_{i}} of customers arriving at the system are i.i.d. random variables with mean δ and for every i ∈ {1, 2, …, N} the service times {σ_{j}^{i}} are i.i.d. random variables with mean σ_{i} which are independent of the interarrival times. Let ψ be a routing policy that corresponds to some word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that \frac{σ_{i}}{δ} · d_{i} < 1 for i = 1, 2, …, N. Then \overline{W} (ψ) exists and is finite. Moreover \overline{W} (ψ) = ∑_{i=1}^{n} d_{i} · \overline{W}^{i}(ψ).

Proof. We have that u^{i} ∈ P(d_{i}) and \frac{σ_{i}}{δ} · d_{i} < 1 for i = 1, 2, …, N. Hence by Theorem 3.10 we have for every i ∈ \{1, 2, …, N\} that \overline{W}^{i}(ψ) = \overline{W}^{i}(u^{i}) exists and is finite. Hence

lim_{τ→∞} \frac{1}{τ} · ∑_{t=1}^{τ} W_{ψ}(t) = lim_{τ→∞} \frac{1}{τ} ∑_{i=1}^{N} ∑_{t∈A^{τ} (i)} W_{ψ}(t) =

lim_{τ→∞} ∑_{i=1}^{N} d_{i} ∑_{t∈A^{τ} (i)} \frac{W_{ψ}(t)}{|A^{τ} (i)|} = ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(ψ).

□

Notation. Let ψ, δ, σ_{i}, d_{i} be as in Theorem 4.2 for i = 1, 2, …, N. Then we say that ρ_{i} := \frac{σ_{i}}{δ} · d_{i} is the traffic intensity for server i if policy ψ is applied.

Remark. If the interarrival times and the service times are deterministic then for Theorem 4.2 it suffices that ρ_{i} ≤ 1 for i = 1, 2, …, N, since in that case \overline{W}^{i}(ψ) exists and is finite.

Definition 4.3 Let U ∈ Q(d_{1}, d_{2}, …, d_{N}) for some d_{i} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then we define the total primal unbalance \overline{O} of U as

\overline{O}(U) := ∑_{i=1}^{N} \overline{I}(u^{i}).  (4)

Further we define the total dual unbalance \underline{O} of U as

\underline{O}(U) := ∑_{i=1}^{N} \underline{I}(u^{i}).  (5)

Further we define the partial orders ⊴\overline{g}, ⊴\underline{g} and ⊴_{g} on Q(d_{1}, d_{2}, …, d_{N}) in the following way. If U, V ∈ Q(d_{1}, d_{2}, …, d_{N}) then U ⊴\overline{g} V if u^{i} ⊴\overline{g} v^{i} for every i ∈ \{1, 2, …, N\}, U ⊴\underline{g} V if u^{i} ⊴\underline{g} v^{i} for every i ∈ {1, 2, …, N} and U ⊴_{g} V if u^{i} ⊴_{g} v^{i} for every i ∈ {1, 2, …, N}.

If it is clear what is meant we just say unbalance and not total unbalance. Suppose that U, V ∈ Q(d_{1}, d_{2}, …, d_{N}) for d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then we say that U, V are mirrors of each other if there exist U′, V′ such that U′ and V′ are period cycles of U respectively V and V′ = \overleftarrow{U′}.

Theorem 4.4 Suppose that U, V ∈ Q(d_{1}, d_{2}, …, d_{N}) are mirrors of each other. Then \overline{O}(U) = \underline{O}(V) and \underline{O}(U) = \overline{O}(V).

Proof. Since U and V are mirrors of each other it follows for every i ∈ {1, 2, …, N} that u^{i}, v^{i} ∈ P(d_{i}) are mirrors of each other. Thus by Corollary 2.32 we have for i = 1, 2, …, N that \overline{I}(u^{i}) = \underline{I}(v^{i}) and thus

\overline{O}(U) = ∑_{i=1}^{N} \overline{I}(u^{i}) = ∑_{i=1}^{N} \underline{I}(v^{i}) = \underline{O}(V).

Analogously it follows that \underline{O}(U) = \overline{O}(V). □

Example. Let U = (1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 4, 3)^{∞} ∈ Q(\{12\}, 4, 3, 3, 2) ⊆ Q(\frac{1}{3}, \frac{1}{4}, \frac{1}{4}, \frac{1}{6}). Then we have that \overline{I}(u^{1}) = \frac{1}{12}, \overline{I}(u^{2}) = 0, \overline{I}(u^{3}) = \frac{1}{12}, \overline{I}(u^{4}) = 0 and thus \overline{O}(U) = \frac{1}{6}. Further \underline{I}(u^{1}) = \frac{1}{4}, \underline{I}(u^{2}) = 0, \underline{I}(u^{3}) = \frac{1}{6}, \underline{I}(u^{4}) = 0 and thus \underline{O}(U) = \frac{5}{12}. Further for V = (1, 2, 4, 1, 3, 2, 1, 3, 4, 2, 1, 3)^{∞} ∈ Q(\{12\}, 4, 3, 3, 2) ⊆ Q(\frac{1}{3}, \frac{1}{4}, \frac{1}{4}, \frac{1}{6}) which is a mirror of U the reader can verify that \overline{O}(V) = \frac{5}{12} and \underline{O}(V) = \frac{1}{6}.

By Theorem 3.11 and Theorem 4.2 we have the following theorem.

Theorem 4.5 Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 4.2. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Suppose that ψ, ψ′ are routing policies with corresponding words U, V ∈ Q(d_{1}, d_{2}, …, d_{N}) respectively. Suppose that ρ_{i} < 1 for i = 1, 2, …, N and U ⊴\overline{g} V. Then

\overline{W} (ψ′) − \overline{W} (ψ) ≤ δ · (\overline{O}(V) − \overline{O}(U)).

Proof. We have that

\overline{W} (ψ′) − \overline{W} (ψ) = ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(v_{i}) − ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(u_{i}) = ∑_{i=1}^{N} d_{i} · (\overline{W}^{i}(v_{i}) − \overline{W}^{i}(v_{i})) ≤

∑_{i=1}^{N} d_{i} · (\frac{δ}{d_{i}}) · (\overline{I}(v^{i}) − \overline{I}(u^{i})) = δ · (\overline{O}(V) − \overline{O}(U)).

□

Analogously we have by Theorem 3.13 and Theorem 4.2 the following theorem.

Theorem 4.6 Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 4.2. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Suppose that ψ, ψ′ are routing policies with corresponding words U, V ∈ Q(d_{1}, d_{2}, …, d_{N}) respectively. Suppose that ρ_{i} < 1 for i = 1, 2, …, N and U ⊴\underline{g} V. Then

\overline{W} (ψ′) − \overline{W} (ψ) ≥ δ · (\underline{O}(U) − \underline{O}(V)).

Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 4.2. Further let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Then, if \overline{W}^{i}(ω(d_{i})) exists and is finite for i = 1, 2, …, N then we put

R̃ = R̃(d_{1}, d_{2}, …, d_{N}) := ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(ω(d_{i})).  (6)

Remark. It is easily seen that if the interarrival times and service times are random variables then for the existence of R̃ it suffices that ρ_{i} < 1 for i = 1, 2, …, N, while if the interarrival times and service times are deterministic then it suffices that ρ_{i} ≤ 1 for i = 1, 2, …, N. Further the definition of R̃ and these results for the existence of R̃ can be extended to the case of irrational d_{i}. Namely, let d_{i} ∈ ℝ_{>0} such that ρ_{i} < 1. Then in [3] and [5] it is shown that W^{i}(ω) exists and is the same for every regular sequence ω of zeros and ones of density d_{i}. In [28] this is also shown for the case of ρ_{i} = 1 and deterministic interarrival and service times. Moreover in Lemma 4.8 W^{i}(ω) is given explicitly for that case. So, if d_{i} ∈ ℝ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1 and ρ_{i} < 1, or ρ_{i} = 1 in case of deterministic interarrival and service times, then R̃ is well defined as follows:

R̃ = R̃(d_{1}, d_{2}, …, d_{N}) := ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(ω^{i}),  (7)

where ω^{i} is any regular sequence of zeros and ones of density d_{i} for i = 1, 2, …, N.

In general R̃ depends on the distribution of the interarrival times and service times and in some cases it is possible to compute R̃ explicitly. We will do this in some examples.

By Corollary 3.12 and Theorem 4.2 we have the following theorem.

Theorem 4.7 Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 4.2. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Suppose that a routing policy ψ is applied with corresponding word U ∈ Q(d_{1}, d_{2}, …, d_{N}) and ρ_{i} < 1 for i = 1, 2, …, N. Then

\overline{W} (ψ) − R̃ ≤ δ · \overline{O}(U).

From Theorem 7.12 in [28] we have an explicit formula for \overline{W}^{i}(ω^{i}) in case of ρ_{i} = 1, deterministic interarrival times and the server i has deterministic service times. In [28] the formula is given for interarrival times δ equal to 1 , but that is no restriction since the time-unit can always be chosen such that δ = 1. So, for general δ we can just multiply by δ and we get the following lemma.

Lemma 4.8 Suppose that the service times {σ_{j}^{i}} of some server i are deterministic equal to σ_{i} and the the interarrival times {δ_{i}} are deterministic and equal to δ. Let ω^{i} be a regular sequence of zeros and ones with density d_{i} ∈ ℝ_{>0} and suppose that the traffic intensity ρ_{i} = d_{i} · \frac{σ_{i}}{δ} for server i is equal to 1. If d_{i} is rational, d = \frac{p_{i}}{q_{i}} with p_{i}, q_{i} ∈ ℕ and gcd(p_{i}, q_{i}) = 1 then

\overline{W} (ω^{i}) = δ · (\frac{1}{2} − \frac{1}{2p_{i}}).  (8)

If d_{i} is irrational then \overline{W} (ω^{i}) = \frac{δ}{2}.

For the same case of deterministic interarrival and service times but with ρ_{i} < 1 an algorithm to calculate \overline{W} (ω^{i}) for a regular sequence ω^{i} is given in [18]. Thus in case of deterministic interarrival and service times R̃(d_{1}, d_{2}, …, d_{N}) can be determined exactly for any d_{1}, d_{2}, …, d_{N} ∈ R_{>0} with ∑_{i=1}^{N} d_{i} = 1 if ρ_{i} ≤ 1 for i = 1, 2, …, N. In the example at the end of this section R̃ is determined in a special case with Poisson arrivals and exponentially distributed service times. For general bounds on R̃ see [34].

We have the following theorem which emphasizes the sharpness of the bound of Theorem 4.7.

Theorem 4.9 Let the interarrival times {δ_{i}} be deterministic equal to δ and the service times {σ_{j}^{i}} be deterministic equal to σ_{i} for i = 1, 2, …, N. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Let p_{i}, q_{i} ∈ ℕ be such that d_{i} = \frac{p_{i}}{q_{i}} with gcd(p_{i}, q_{i}) = 1 for i = 1, 2, …, N. Suppose that a routing policy ψ is applied with corresponding word U ∈ Q(d_{1}, d_{2}, …, d_{N}) and ρ_{i} = 1 for i = 1, 2, …, N. Then

\overline{W} (ψ) = R̃ + δ · \overline{O}(U) = δ · (\frac{1}{2} − ∑_{i=1}^{N} \frac{1}{2q_{i}} + \overline{O}(U)) .

Proof. According to the remark following Theorem 4.2 we can apply Theorem 4.2 and by Theorem 3.15 it follows that

\overline{W} (ψ) = R̃ + δ · \overline{O}(U).

By (8) we have that

R̃ = ∑_{i=1}^{N} d_{i} · \overline{W} (ω(d_{i})) = ∑_{i=1}^{N} \frac{p_{i}}{q_{i}} · δ · (\frac{1}{2} − \frac{1}{2p_{i}}) = δ · (\frac{1}{2} − ∑_{i=1}^{N} \frac{1}{2q_{i}}).  (9)

Example. We consider a queueing system with 3 parallel servers where the interarrival times are deterministic and equal to δ = 3. The arriving jobs are routed to the servers according to the policy ψ that corresponds to the word

U = (1, 2, 1, 2, 1, 3, 1, 2, 1, 3)^{∞} ∈ Q(\{10\}, 5, 3, 2) ⊆ Q(\frac{1}{2}, \frac{3}{10}, \frac{1}{5}).

All the service times are deterministic and for server 1 they are equal to σ_{1} = 6, for server 2 equal to σ_{2} = 10 and for server 3 equal to σ_{3} = 15. Hence ρ_{i} = 1 for i = 1, 2, 3. Further \overline{I}(u^{1}) = 0, \overline{I}(u^{2}) = \frac{1}{10}, \overline{I}(u^{3}) = \frac{1}{10} and thus \overline{O}(U) = \frac{1}{5}. So, according to Theorem 4.9 we have that

\overline{W} (ψ) = 3 · (\frac{1}{2} − (\frac{1}{4} + \frac{1}{20} + \frac{1}{10}) + \frac{1}{5}) = \frac{9}{10}

which can be checked by direct calculation.

Theorem 4.10 Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 4.2. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Suppose that a routing policy ψ is applied with corresponding word U ∈ Q(d_{1}, d_{2}, …, d_{N}) and ρ_{i} < 1 for i = 1, 2, …, N. Then

R̃ ≤ \overline{W} (ψ) ≤ R̃ + δ · \overline{O}(U).

Proof. From [3] and [5] we have that R̃ ≤ \overline{W} (ψ) and according to Theorem 4.7 we have that \overline{W} (ψ) ≤ R̃ + δ · \overline{O}(U) . □

Note. Suppose that we have a queueing system where the arrivals are according to a Poisson process with parameter λ. Suppose that the service times of server i are exponentially distributed with parameter μ_{i}. If d_{i}, the fraction of jobs that is routed to server i, equals \frac{1}{q_{i}} for some q_{i} ∈ ℕ, then \overline{W}^{i}(ω(d_{i})) can be calculated in the following way. For the routing sequence ω(d_{i}) we have that among every q_{i} arriving jobs exactly one job is routed to server i. So, the interarrival times at server i consist of q_{i} Poisson arrivals with parameter λ. Hence the interarrival times for the queue of server i are Erlang distributed, namely according to an E_{λ}^{q_{i}} distribution. Thus \overline{W}^{i}(ω(d_{i})) is the same as the average waiting time for a E_{λ}^{q_{i}}/M/1 queue, where the parameter of the service times is μ_{i}. So (see [19]) if x_{i} ∈ (0, 1) is a solution of the equation

x = (\frac{λ}{λ + μ_{i} − μ_{i} · x})^{q_{i}},  (10)

then \overline{W}^{i}(ω(d_{i})) = \frac{x_{i}}{μ_{i}·(1−x_{i})}.

In the following example we have calculated \overline{W}^{i}(ω(d_{i})) for i = 1, 2, 3, 4 in this way. Further we have explicitly calculated the lower bound R̃ and upper bound R̃ + δ · \overline{O}(U) of Theorem 4.10 for \overline{W} (ψ), where U is the word corresponding to the applied routing policy ψ.

Example. We consider a queueing system with 4 parallel servers where the arrivals are according to a Poisson process with parameter λ = 11. Hence for the mean interarrival time δ we have that δ = \frac{1}{11}. The arriving jobs are routed to the servers according to the policy ψ that corresponds to the word

U = (1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 4, 3)^{∞} ∈ Q(\{12\}, 4, 3, 3, 2) ⊆ Q(\frac{1}{3}, \frac{1}{4}, \frac{1}{4}, \frac{1}{6})

which we considered in a previous example. For every i ∈ {1, 2, 3, 4} the service times are exponentially distributed with parameter μ_{i} and μ_{1} = 4, μ_{2} = μ_{3} = 3 and μ_{4} = 2. Then we find that \overline{W}^{1}(ω(\frac{1}{3})) = 1.7792 (rounded to 4 decimals) and thus by Corollary 3.12 we have that \overline{W}^{1}(u^{1}) ≤ 1.7792 + 3 · \frac{1}{11} · \frac{1}{12} = 1.8019. Similarly we have that \overline{W}^{2}(ω(\frac{1}{4})) = \overline{W}^{2}(u^{2}) = 2.2105, \overline{W}^{3}(ω(\frac{1}{4})) = 2.2105, \overline{W}^{3}(u^{3}) ≤ 2.2408 and \overline{W}^{4}(ω(\frac{1}{6})) = \overline{W}^{4}(u^{4}) = 3.0732. Hence

R̃ = \frac{1}{3} · \overline{W}^{1}(ω(\frac{1}{3})) + \frac{1}{4} · \overline{W}^{2}(ω(\frac{1}{4})) + \frac{1}{4} · \overline{W}^{3}(ω(\frac{1}{4})) + \frac{1}{6} · \overline{W}^{4}(ω(\frac{1}{6})) = 2.2105.

and R̃+δ·\overline{O}(U) = 2.2105+ \frac{1}{11} · \frac{1}{6} = 2.2257. So, by Theorem 4.10 we have that 2.2105 ≤ \overline{W} (ψ) ≤ 2.2257.

5 Billiard sequences and routing sequences

In this section we give some properties of sequences (words) and their implications for the corresponding routing policies. In particular we have some properties for so-called billiard sequences (see [8]and [10]). For every set of rational densities we obtain a billiard sequence with unbalance smaller or equal than \frac{N}{2} −1, where N is the number of parallel queues. We derive a relation between the discrepancy function and the unbalance and several properties can be obtained from that. We show that for given rational densities there exists a periodic billiard sequence which has minimal unbalance among all sequences with those densities.

Theorem 5.1 Let d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1 for some N ∈ ℤ_{≥2}. Then there exists a word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that \overline{O}(U) ≤ \frac{N}{2} − 1.

Theorem 5.1 follows from Theorem 5.5 which we formulate and prove later. The dual of Theorem 5.1, which is a consequence of Theorem 5.1 and Theorem 4.4, is the following theorem.

Theorem 5.2 Let d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1 for some N ∈ ℤ_{≥2}. Then there exists a word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that \underline{O}(U) ≤ \frac{N}{2} − 1.

Theorem 5.1 and Theorem 4.7 have the following corollary.

Corollary 5.3 Let the interarrival times {δ_{i}} , the service times {σ_{j}^{i}} and d_{i} for i = 1, 2, …, N be as in Theorem 4.7. Suppose that ρ_{i} < 1 for i = 1, 2, …, N. Then there exists a routing policy ψ corresponding to a word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that

\overline{W} (ψ) ≤ R̃(d_{1}, d_{2}, …, d_{N}) + δ · (\frac{N}{2} − 1).

Theorem 5.5 shows how to construct a word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that \overline{O}(U) ≤ \frac{N}{2} − 1. For the construction we use the following algorithm which we call the SG (Special Greedy) algorithm.

SG algorithm. Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1 and x_{1}, x_{2}, …, x_{N} ∈ ℝ_{≥0} be given. Then U = (U_{1}, U_{2}, …) is determined inductively in the following way. Suppose that U_{1}, U_{2}, …, U_{n−1} have been determined and thus κ_{u^{i}}(n − 1) is known for i = 1, 2, …, N. Choose U_{n} such that U_{n} = i ∈ \{1, 2, …, N\} for which \frac{x_{i}+κ_{u^{i}}(n−1)}{d_{i}} is minimal.

If 0 ≤ x_{i} ≤ 1 for i = 1, 2, …, N then a word U constructed by the SG algorithm is known in the literature as a billiard word or sequence (see for example [8]). Namely, if a billiard ball travels in an N -dimensional cube with elastic reflecton on the sides the cube and a sequence of integers from {1, 2, …, N} (the integers correspond to the sides of the cube and opposite sides correspond to the same integer) is constructed by writing down an integer if the ball reflects against a side of the cube corresponding to that integer then such a sequence is called a billiard sequence. It is easily seen that the word constructed by the SG algorithm is a billiard sequence obtained by starting in position (x_{1}, x_{2}, …, x_{N}) and having initial velocity vector (−d_{1}, −d_{2}, …, −d_{N}) in the unit cube [0, 1]^{N}. In the SG algorithm the choice of U_{n} is not totally determined if \frac{x_{i}+κ_{u^{i}}(n−1)}{d_{i}} is minimal for several i ∈ {1, 2, …, N}. We assume that in such cases a consistent choice is made. For example always the smallest i is chosen for which \frac{x_{i}+κ_{u^{i}}(n−1)}{d_{i}} is minimal. If this modified SG algorithm is used then the word obtained by the algorithm is determined by x_{1}, x_{2}, …, x_{N} ∈ ℝ_{≥0}. For billiard sequences this consistent choice means that if the billiard ball hits multiple sides at the same time then the order in which the letters corresponding to those sides appear in the billiard sequence is also prescribed. We will call such a billiard sequence a consistent billiard sequence. More precisely, we define a consistent billiard sequence on the alphabet {0, 1, …, N} to be a sequence (ℕ - word) that can be otained by applying the SG algorithm in a consistent way to some 0 ≤ x_{i} < 1 for i = 1, 2, …, N. Note that x_{i} < 1 instead of x_{i} ≤ 1 for i = 1, 2, …, N. The reason for this becomes clear in the proof of Lemma 5.4. A billiard sequence that is not consistent can be aperiodic even if the densities d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0}. However, for consistent billiard sequences we have the following lemma.

Lemma 5.4 Let d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Let p_{i}, q_{i}, k_{i} ∈ ℕ for i = 1, 2, …, N and T ∈ ℕ be such that d_{i} = \frac{p_{i}}{q_{i}} = \frac{k_{i}}{T} with gcd(p_{i}, q_{i}) = 1 for i = 1, 2, …, N and gcd(k_{1}, k_{2}, …, k_{N}) = 1. Let U be a consistent billiard sequence with these densities. Then U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}).

Proof. The consistent billiard sequence U can be constructed by starting in (x_{1}, x_{2}, …, x_{N}) with 0 ≤ x_{i} < 1 for i = 1, 2, …, N and initial velocity vector (−d_{1}, −d_{2}, …, −d_{N}). We assume that the velocity of the billard ball is such that for every i ∈ {1, 2, …, N} it takes 1/d_{i} time units to travel between the opposite sides of the cube corresponding to i. Then for every t ≥ 0 the billiard ball has reflected ⌈t · d_{i} − x_{i}⌉ times on sides corresponding to letter i in the time interval [0, t]. Hence in the time interval [0, T] the billiard ball has reflected ⌈T · d_{i} − x_{i}⌉ = k_{i} times on sides corresponding to i for i = 1, 2, …, N. Since ∑_{i=1}^{N} k_{i} = T it follows that κ_{u^{i}}(T) = k_{i} for every i ∈ {1, 2, …, N} and \frac{x_{i}+κ_{u^{i}}(T)}{d_{i}} = \frac{x_{i}}{d_{i}} + T for every i ∈ \{1, 2, …, N\}. Since U is obtained by applying the SG algorithm in a consistent way on x_{1}, x_{2}, …, x_{N} it follows that U_{T +t} = U_{t} for every t ∈ {1, 2, …, T } and by induction we have that U is periodic with period T. Hence U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}). □

Theorem 5.5 Let d_{i}, p_{i}, q_{i}, k_{i} and T be as in Lemma 5.4, N ≥ 2 and let k ∈ {1, 2, …, N} be such that q_{k} = max_{i∈\{1,2,... ,N\}} q_{i}. Put x_{k}^{∗} = 0 and x_{j}^{∗} = 1 − \frac{1}{q_{j}} for every j ∈ \{1, 2, …, N\} for which j ≠ k. Construct a consistent billiard sequence U starting in (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) with initial velocity vector (−d_{1}, −d_{2}, …, −d_{N}) in the unit cube [0, 1]^{N}. Then U ∈ Q(\{T \}, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}). Moreover \overline{O}(U) = 0 if N = 2 and \overline{O}(U) < \frac{N}{2} − 1 if N ≥ 3.

We prove this theorem later. In the theorem we have chosen a particular starting point for the billiard sequence, but we think that this is not necessary. We have the following conjecture.

Conjecture 5.6 For every consistent periodic billiard sequence U on N letters it holds that \overline{O}(U) ≤ \frac{N}{2} − 1 and \underline{O}(U) ≤ \frac{N}{2} − 1 if N ≥ 2.

Billiard sequences have more nice properties. For example, in [33] there is a notion for (routing) sequences to be called m - balanced. Regular sequences are 1 - balanced for that notion. From the results in that paper it follows that billiard sequences on an alphabet of N letters are N − 1 - balanced.

We need a number of lemmas and theorems in order to prove Theorem 5.5. These results are also of independent interest. A relation between the discrepancy function and the unbalance is derived.

Lemma 5.7 Let p, q ∈ ℕ. Then

∑_{n=1}^{q}⌈n · \frac{p}{q}⌉ = \frac{1}{2}(pq + p + q − gcd(p, q)).

Proof. Put p′ = \frac{p}{gcd(p,q)} and q′ = \frac{q}{gcd(p,q)}. Recall that for a ∈ ℤ and b ∈ ℕ we denote by a (mod b) the integer a′ ∈ {0, 1, …, b − 1} such that a = a′ + kb for some k ∈ ℤ. Then we have that

∑_{n=1}^{q}(⌈n · \frac{p}{q}⌉ − n · \frac{p}{q}) = \frac{1}{q} · ∑_{n=1}^{q}(−np) (mod q) =

\frac{gcd(p, q)}{q} · ∑_{n=1}^{q′} gcd(p, q) · (−np′) (mod q′) = \frac{(gcd(p, q))^{2}}{q} ∑_{i=0}^{q′−1} i =

\frac{(gcd(p, q))^{2}}{q} · \frac{q′}{2} · (q′ − 1).

Hence

∑_{n=1}^{q}⌈n · \frac{p}{q}⌉ = ∑_{n=1}^{q} n · \frac{p}{q} + ∑_{n=1}^{q}(⌈n · \frac{p}{q}⌉ − n · \frac{p}{q}) =

\frac{p}{2} · (q + 1) + \frac{1}{2} gcd(p, q) · (\frac{q}{gcd(p, q)} − 1) = \frac{1}{2}(pq + p + q − gcd(p, q)).

□

Recall the notation introduced in the previous section and the definition of the discrepancy function χ from section 2.

Definition 5.8 Let U ∈ S(d_{1}, d_{2}, …, d_{N}) for some d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then we define

c_{i} = c_{i}(U) = sup_{n∈ℤ_{≥0}}χ_{u^{i}}(n)

for i = 1, 2, …, N.

Lemma 5.9 If U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) for some T, k_{1}, k_{2}, …, k_{N} ∈ ℕ then

c_{i} = max_{n∈{0,1,... ,T −1}} χ_{u^{i}}(n) for i = 1, 2, …, N.

Proof. For i ∈ \{1, 2, …, N\} we have that d_{i} = \frac{k_{i}}{T} is the density of sequence u^{i}. So, for every n ∈ ℤ_{≥0} we have that

χ_{u^{i}}(n + T) = χ_{u^{i}}(n) + d_{i} · T − (κ_{u^{i}}(n + T) − κ_{u^{i}}(n)) = χ_{u^{i}}(n).
□

Theorem 5.10 Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N such that ∑_{i=1}^{N} d_{i} = 1. Let p_{i}, q_{i} ∈ ℕ such that d_{i} = \frac{p_{i}}{q_{i}} with gcd(p_{i}, q_{i}) = 1 for i = 1, 2, …, N and let U ∈ Q(d_{1}, d_{2}, …, d_{N}). Then

\overline{O}(U) = ∑_{i=1}^{N} c_{i}(U) − \frac{N}{2} + ∑_{i=1}^{N} \frac{1}{2q_{i}} .

Proof. There exist T, k_{1}, k_{2}, …, k_{N} ∈ ℕ such that U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}). For i ∈ {1, 2, …, N} put v_{i} = (u^{i}(1), u^{i}(2), …, u^{i}(T)). Then v_{i} ∈ P(T, k_{i}) is a period cycle of u^{i}. Let v′_{i} ∼ v_{i} be an upper bound with respect to the partial order ⪯ of R(T, k_{i}). We have that v′_{i} is the l-th cyclic permutation of v_{i} for some l ∈ {0, 1, …, T − 1}. It follows that (see the proof of Theorem 2.13) χ_{v_{i}}(l) = c_{i} = c_{i} + χ_{v′_{i}}(0) and thus χ_{v_{i}}((l + n) (mod T)) = χ_{v′_{i}}(n) + c_{i} for n = 0, 1, …, T. Hence by Definition of the primal unbalance

c_{i} = \frac{1}{T} ∑_{n=1}^{T}(χ_{v_{i}}(n) − χ_{v′_{i}}(n)) = \frac{1}{T} ∑_{n=1}^{T}(κ_{v′_{i}}(n) − κ_{v_{i}}(n)) =  (11)

\overline{I}(u^{i}) + \frac{1}{T} ∑_{n=1}^{T} κ_{\overline{ω}(T,k_{i})}(n) − \frac{1}{T} ∑_{n=1}^{T} κ_{u^{i}}(n).

By Corollary 2.12 and Lemma 5.7 we have that

∑_{i=1}^{N} \frac{1}{T} ∑_{n=1}^{T} κ_{\overline{ω}(T,k_{i})}(n) = ∑_{i=1}^{N}(\frac{1}{T} · ∑_{n=1}^{T}⌈n · \frac{k_{i}}{T} ⌉) =

\frac{1}{2} · ∑_{i=1}^{N}(k_{i} + \frac{k_{i}}{T} + 1 − \frac{gcd(k_{i}, T)}{T}) = \frac{1}{2} · (T + 1 + N − ∑_{i=1}^{N} \frac{1}{q_{i}}).

So, by (11) we have that

∑_{i=1}^{N} c_{i} = \overline{O}(U) − \frac{1}{T} ∑_{n=1}^{T} n + \frac{1}{2} · (T + 1 + N − ∑_{i=1}^{N} \frac{1}{q_{i}}) = \overline{O}(U) + \frac{N}{2} − ∑_{i=1}^{N} \frac{1}{2q_{i}} .

□

We need the following definitions. Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Put

S̃ = S̃(d_{1}, d_{2}, …, d_{N}) := inf_{U∈S(d_{1},d_{2},... ,d_{N})} ∑_{i=1}^{N} c_{i}(U).

Moreover, define

D = D(d_{1}, d_{2}, …, d_{N}) =

{(x_{1}, x_{2}, …, x_{N}) ∈ ℝ^{N} : n ≥ ∑_{i=1}^{N} max(⌈n · d_{i} − x_{i}⌉, 0) for every n ∈ ℤ_{≥0}}

and

D̃ = D̃(d_{1}, d_{2}, …, d_{N}) := inf_{(x_{1},x_{2},... ,x_{N})∈D} ∑_{i=1}^{N} x_{i}.

It is easily seen that for every U ∈ S(d_{1}, d_{2}, …, d_{N}) it holds that

(c_{1}(U), c_{2}(U), …, c_{N}(U)) ∈ D(d_{1}, d_{2}, …, d_{N}).  (12)

Consider the following algorithm to construct a sequence U with given densities. It is similar to the SG algorithm, but the choice of U_{n} is slightly less restricted. Therefore it is called the GG (General Greedy) algorithm.

GG algorithm. Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1 and x_{1}, x_{2}, …, x_{N} ∈ ℝ_{≥0} be given. Then U = (U_{1}, U_{2}, …) ∈ S(d_{1}, d_{2}, …, d_{N}) is determined inductively in the following way. Suppose that U_{1}, U_{2}, …, U_{n−1} have been determined and thus κ_{u^{i}}(n − 1) is known for i = 1, 2, …, N. Choose U_{n} such that U_{n} = i ∈ \{1, 2, …, N\} for which ⌊\frac{x_{i}+κ_{u^{i}}(n−1)}{d_{i}}⌋ is minimal.

It is easily seen that for a word U constructed by the GG algorithm it holds that U ∈ S(d_{1}, d_{2}, …, d_{N}) and note that the SG algorithm is a special GG algorithm. The following results (until Theorem 5.19) are from [28] in which a slightly different notation is used. We restate the results using the notation of this paper. Note that some of the results are for arbitrary real densities and not only for rational densities.

Lemma 5.11 Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Let U ∈ S(d_{1}, d_{2}, …, d_{N}) be constructed by applying the GG algorithm with x_{1}, x_{2}, …, x_{N} ∈ ℝ_{≥0} such that (x_{1}, x_{2}, …, x_{N}) ∈ D(d_{1}, d_{2}, …, d_{N}). Then c_{i}(U) ≤ x_{i} for i = 1, 2, …, N.

A direct consequence of (12) and Lemma 5.11 is that

S̃ = D̃  (13)

Theorem 5.12 For every set of fractions d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1 there exist U^{∗} ∈ S(d_{1}, d_{2}, …, d_{N}) and corresponding (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) = (c_{1}(U^{∗}), c_{2}(U^{∗}), …, c_{N}(U^{∗})) ∈ D such that

∑_{i=1}^{N} c_{i}(U^{∗}) = S̃ and ∑_{i=1}^{N} x_{i}^{∗} = D̃.

Thus according to Theorem 5.12 there are U and x_{i} which attain the respective infima.

Lemma 5.13 Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1 and suppose that

∑_{i=1}^{N} x_{i} = N − 1 and 0 ≤ x_{i} ≤ 1 + d_{i} for i = 1, 2, …, N.  (14)

Then (x_{1}, x_{2}, …, x_{n}) ∈ D.

Particular x_{1}, x_{2}, …, x_{N} that fulfill (14) are for example x_{i} = 0 for some i ∈ {1, 2, …, N} and x_{j} = 1 for all j ≠ i. Another example is x_{i} = 1 − d_{i} for i = 1, 2, …, N. Combining (13), Theorem 5.12 and Lemma 5.13 gives the following corollary.

Corollary 5.14 For every set of fractions d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1 we have that

S̃ = min_{U∈S(d_{1},d_{2},... ,d_{N})} ∑_{i=1}^{N} c_{i} ≤ N − 1.

We think that for any billiard sequence U it holds that ∑_{i=1}^{N} c_{i}(U) ≤ N − 1. The following theorem asserts that it is possible that S̃ = N − 1 and thus Corollary 5.14 is sharp. Theorem 5.15 Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. If d_{1}, d_{2}, …, d_{N} are linearly independent over ℤ then S̃(d_{1}, d_{2}, …, d_{N}) = N − 1. Put

S_{0}(d_{1}, d_{2}, …, d_{N}) = {U ∈ S(d_{1}, d_{2}, …, d_{N}) for which ∑_{i=1}^{N} c_{i} = S̃}

and

D_{0} = D_{0}(d_{1}, d_{2}, …, d_{N}) = {(x_{1}, x_{2}, …, x_{N}) ∈ D(d_{1}, d_{2}, …, d_{N}) for which ∑_{i=1}^{N} x_{i} = D̃}.

By Theorem 5.12 we have that S_{0}(d_{1}, d_{2}, …, d_{N}) ≠ ∅ and D_{0}(d_{1}, d_{2}, …, d_{N}) ≠ ∅. Moreover, if U ∈ S_{0}(d_{1}, d_{2}, …, d_{N}) then (c_{1}(U), c_{2}(U), …, c_{N}(U)) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) and vice versa if (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) then we have for any word U constructed by applying the GG algorithm with these x_{1}, x_{2}, …, x_{N} that U ∈ S_{0}(d_{1}, d_{2}, …, d_{N}). Theorem 5.16 Let d_{1}, d_{2}, …, d_{N} ∈ ℝ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then for every ε > 0 and i ∈ {1, 2, …, N} there exist (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) with x_{i} < ε and x_{j} < 1 for all j ≠ i. In the foregoing results it was not required for the densities d_{i} to be rational. In the remaining of this section the densities d_{i} are rational with ∑_{i=1}^{N} d_{i} = 1. Further p_{i}, q_{i}, k_{i} ∈ ℕ for i = 1, 2, …, N and T ∈ ℕ are such that d_{i} = \frac{p_{i}}{q_{i}} = \frac{k_{i}}{T} with gcd(p_{i}, q_{i}) = 1 and gcd(k_{1}, k_{2}, …, k_{N}) = 1 for i = 1, 2, …, N. Lemma 5.17 Let U ∈ S(d_{1}, d_{2}, …, d_{N}) be such that c_{i}(U) < ∞ for i ∈ {1, 2, …, N}. Then q_{i}·c_{i}(U) ∈ ℤ_{≥0}. Proof. For every n ∈ ℤ_{≥0} we have that q_{i} · χ_{u^{i}}(n) = p_{i} · n − q_{i} · κ_{u^{i}}(n) ∈ ℤ. □ Corollary 5.18 Suppose that (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(x_{1}, x_{2}, …, x_{N}). Then q_{i} · x_{i} ∈ ℤ_{≥0} for i = 1, 2, …, N. From this corollary we have that x_{j} < 1 implies x_{j} ≤ 1 − \frac{1}{q_{j}} for every j. Combining this with Theorem 5.16, we obtain the following result. Theorem 5.19 For every i ∈ {1, 2, …, N} there exists some (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) with x_{i} = 0 and x_{j} ≤ 1 − \frac{1}{q_{j}} for every j ≠ i. Moreover

S̃ ≤ N − 1 − ∑_{i=1}^{N} \frac{1}{q_{i}} + min_{i∈\{1,2,... ,N\}} \frac{1}{q_{i}} .

Proof of Theorem 5.5. By Lemma 5.4 we have that U ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}). According to Theorem 5.19 there exist (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) ⊆ D(d_{1}, d_{2}, …, d_{N}) with x_{i} ≤ x_{i}^{∗} for i = 1, 2, …, N. It follows directly from the definition of D(d_{1}, d_{2}, …, d_{N}) that if (x_{1}, x_{2}, …, x_{N}) ∈ D(d_{1}, d_{2}, …, d_{N}) and x_{i} ≤ x′_{i} for i = 1, 2, …, N then (x′_{1}, x′_{2}, …, x′_{N}) ∈ D(d_{1}, d_{2}, …, d_{N}). Hence (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) ∈ D(d_{1}, d_{2}, …, d_{N}). Since constructing a consistent billiard sequence is a special form of applying a GG algorithm we have by Lemma 5.11 that c_{i}(U) ≤ x_{i}^{∗} for i = 1, 2, …, N. Thus

∑_{i=1}^{N} c_{i}(U) ≤ ∑_{i=1}^{N} x_{i}^{∗} = N − 1 − ∑_{i=1}^{N} \frac{1}{q_{i}} + min_{i∈\{1,2,... ,N\}} \frac{1}{q_{i}} .

So, by Theorem 5.10 we have that

\overline{O}(U) = ∑_{i=1}^{N} c_{i}(U) − \frac{N}{2} + ∑_{i=1}^{N} \frac{1}{2q_{i}} ≤ \frac{N}{2} − 1 + min_{i∈\{1,2,... ,N\}} \frac{1}{q_{i}} − ∑_{i=1}^{N} \frac{1}{2q_{i}} .  (15)

If N = 2 then q_{1} = q_{2} and thus ∑_{i=1}^{N} \frac{1}{2q_{i}} = min_{i∈\{1,2,... ,N\}} \frac{1}{q_{i}} . Combining this with (15) gives \overline{O}(U) ≤ 0 and thus \overline{O}(U) = 0 if N = 2. If N > 2 then

∑_{i=1}^{N} \frac{1}{2q_{i}} ≥ ∑_{i=1}^{N} min_{i∈\{1,2,... ,N\}} \frac{1}{2q_{i}} > min_{i∈\{1,2,... ,N\}} \frac{1}{q_{i}}

and thus we have by (15) that \overline{O}(U) < \frac{N}{2} − 1 if N > 2. □

We now show that for every set of rational densities there exist a consistent and thus periodic billiard sequence which has minimal unbalance among all (periodic) sequences with those densities.

Theorem 5.20 For every set of rational densities d_{i} there exists some consistent billiard sequence U^{∗} ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}) such that

∑_{i=1}^{N} c_{i}(U^{∗}) = S̃ and \overline{O}(U^{∗}) = min_{U∈Q(d_{1},d_{2},... ,d_{N})} \overline{O}(U).

Proof. By Theorem 5.16 there exist (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) with 0 ≤ x_{i} < 1 for i = 1, 2, …, N. Let U^{∗} be obtained by applying the SG algorithm in a consistent way on such x_{1}, x_{2}, …, x_{N}. Then U^{∗} is a consistent billiard sequence and by Lemma 5.4 we have that U^{∗} ∈ Q({T }, k_{1}, k_{2}, …, k_{N}) ⊆ Q(d_{1}, d_{2}, …, d_{N}). Moreover, since (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) we have that U^{∗} ∈ S_{0}(d_{1}, d_{2}, …, d_{N}) and thus ∑_{i=1}^{N} c_{i}(U^{∗}) = S̃. By Theorem 5.10 it then follows that \overline{O}(U^{∗}) = min_{U∈Q(d_{1},d_{2},... ,d_{N})} \overline{O}(U). □

Such a billiard sequence with minimal unbalance can be found in an algorithmic way. Indeed, in case of rational densities d_{i} it is shown in [28] that an (x_{1}, x_{2}, …, x_{N}) ∈ D_{0}(d_{1}, d_{2}, …, d_{N}) with 0 ≤ x_{i} < 1 for i = 1, 2, …, N can be found by solving an integer linear programming problem (ILP). Thus for given rational densities it is possible to obtain a consistent billiard sequence U with minimal unbalance \overline{O} by first solving an ILP and then applying the SG algorithm in a consistent way. Then the routing policy ψ corresponding to U is periodic and the upper bound from Theorem 4.7 for \overline{W} (ψ) is minimized by ψ for those densities. Note that from Theorem 4.4 it follows that if V is a mirror of such a routing sequence U that then V has minimal dual unbalance \underline{O}. The following example illustrates some of the results of this section.

Example. Let N = 5, d_{1} = \frac{3}{8} , d_{2} = \frac{7}{24}, d_{3} = \frac{1}{6}, d_{4} = \frac{1}{8} and d_{5} = \frac{1}{24}. We apply the SG algorithm in a consistent way (in case of a tie the letter of smallest index is chosen) with x_{1} = \frac{7}{8}, x_{2} = 0, x_{3} = \frac{5}{6}, x_{4} = \frac{7}{8} and x_{5} = \frac{23}{24}. Then we obtain the word U = (2, 1, 2, 1, 3, 2, 4, 1, 2, 1, 3, 1, 2, 4, 1, 3, 2, 1, 2, 1, 3, 4, 5, 1)^{∞} and thus U ∈ Q(\{24\}, 9, 7, 4, 3, 1) ⊆ Q(\frac{3}{8}, \frac{7}{24}, \frac{1}{6}, \frac{1}{8}, \frac{1}{24}). Using Lemma 5.9 it can be checked that c_{1}(U) = \frac{5}{8}, c_{2}(U) = 0, c_{3}(U) = \frac{2}{3}, c_{4}(U) = \frac{3}{4}, c_{5}(U) = \frac{11}{12} and thus ∑_{i=1}^{N} c_{i}(U) = \frac{71}{24}. Note that c_{i}(U) ≤ x_{i} for every i ∈ {1, 2, 3, 4, 5} as expected by Lemma 5.11. By Theorem 5.10 or direct computation it follows that \overline{O}(U) = \frac{17}{24} and thus \overline{O}(U) < \frac{N}{2} − 1 as expected by Theorem 5.5. For the word V = (1, 5, 4, 3, 1, 2, 1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 1, 4, 2, 3, 1, 2, 1, 2)^{∞} which is a mirror of U we have by Theorem 4.4 that \underline{O}(V) = \overline{O}(U) = \frac{17}{24} < \frac{N}{2} − 1. By Lemma 5.11 we have that if the SG algorithm is applied with x_{i} = c_{i}(U) for i = 1, 2, …, 5 then a word U′ ∈ Q(\frac{3}{8}, \frac{7}{24}, \frac{1}{6}, \frac{1}{8}, \frac{1}{24}) is obtained with c_{i}(U′) ≤ c_{i}(U) for i = 1, 2, …, 5 and thus \overline{O}(U′) ≤ \overline{O}(U). Hence by using the SG algorithm iteratively in this way a sequence of periodic words with the given densities is found with non-increasing total primal unbalance. We do this for this example starting with U and we get the following sequence of words. First we obtain U′ = (2, 1, 2, 3, 1, 4, 2, 1, 1, 3, 2, 1, 2, 4, 1, 3, 2, 1, 1, 2, 3, 4, 5, 1)^{∞} with c_{1}(U′) = \frac{5}{8}, c_{2}(U′) = 0, c_{3}(U′) = \frac{1}{2}, c_{4}(U′) = \frac{5}{8}, c_{5}(U′) = \frac{11}{12} and \overline{O}(U′) = \frac{5}{12}. By applying the SG algorithm to x_{i} = c_{i}(U′) we obtain the word U′′ = (2, 1, 3, 2, 1, 4, 2, 1, 3, 1, 2, 1, 4, 2, 1, 3, 2, 1, 1, 2, 3, 4, 5, 1)^{∞} with c_{1}(U′′) = \frac{5}{8}, c_{2}(U′′) = 0, c_{3}(U′′) = \frac{1}{2}, c_{4}(U′′) = \frac{5}{8}, c_{5}(U′′) = \frac{11}{12} and \overline{O}(U′′) = \frac{5}{12}. Since c_{i}(U′′) = c_{i}(U′) for i = 1, 2, …, 5 applying the SG algorithm to x_{i} = c_{i}(U′′) gives the word U′′ again. Thus the iterative process stops with U′′, (see [28] for more on this iterative process) but the word U′′ does not have minimal unbalance for these densities. Namely, we have found that (0, \frac{7}{24}, \frac{1}{2}, \frac{3}{4}, \frac{23}{24}) ∈ D_{0}(\frac{3}{8}, \frac{7}{24}, \frac{1}{6}, \frac{1}{8}, \frac{1}{24}), and thus the word W = (1, 2, 1, 3, 2, 1, 4, 2, 1, 3, 1, 2, 1, 4, 2, 3, 1, 2, 1, 3, 1, 2, 4, 5)^{∞} obtained by applying the SG algorithm to this solution with \overline{O}(W) = \frac{1}{4} has minimal primal unbalance for these densities.

Conclusion

We investigated in this paper the static routing to parallel queues with different service times. We introduced a combinatorial notion which we called unbalance. For a periodic routing pattern we derived an upper bound on the average waiting time as function of its unbalance. From a combinatorial point of view it would be of interest to extend the notion of unbalance to non-periodic routing sequences which have irrational routing fractions. For applications it would be important to extend the bounds derived in this paper to the following models:

1. optimal routing of the server in polling systems;

2. parallel queues with two or more servers for each queue;

3. sojourn times in queueing networks.

Acknowledgement

The authors would like to thank Bruno Gaujal for his hospitality during their visits to LORIA, Nancy. During one of the stimulating discussions with him the graph order was found. The authors thank Robert Tijdeman for his helpful comments.

6 Appendix

In Theorem 3.10 and subsequent results we assumed that {δ_{i}} ({σ_{j}}) were i.i.d. random variables. Below we show that instead of i.i.d. random variables we may assume that they are stationary ergodic sequences. This greater generality is very useful for applications to traffic processes in telecommunication networks. To the authors’ knowledge there does not exist a proof for the i.i.d. case in the literature. But, it is a special case of the more general result of Theorem 6.1 (see also the remark following the theorem). Recall that W_{u}(j, w) denotes the workload for the server at the moment that the j-th customer is routed to the server (according to routing sequence u), given that the initial workload at time T_{1} = 0 is equal to w.

Theorem 6.1 Let u′ and u′′ be routing sequences of zeros and ones that are both representatives of some u ∈ P(d) where d = \frac{k}{T} ∈ ℚ and the period cycle of u is an element of P(T, k). Suppose that the interarrival times {δ_{i}} of customers arriving at the system are a stationary ergodic sequence with δ = 𝔼δ_{1}. Moreover, assume that the sequence {δ_{nT +l}}_{n=0}^{∞} is ergodic for each l ∈ {1, 2, …, T }. Suppose that the service times σ_{j} of the customers routed to the server form a stationary ergodic sequence with σ = 𝔼σ_{1}, and are stochastically independent of the interarrival times. Moreover, assume that the sequences \{σ_{nk+l}\}_{n=0}^{∞} is ergodic for each l ∈ \{1, 2, …, k\}. Suppose that \frac{σ}{δ} · d < 1. Then lim_{m→∞} \frac{1}{m} · ∑_{n=0}^{m−1} δ_{nT +l} = δ almost surely (a.s.) for l = 1, 2, …, T and there exists a deterministic value \overline{W} (u) such that

lim_{m→∞} \frac{1}{m} · ∑_{j=0}^{m−1} \overline{W}_{u′}(j, w′) = lim_{m→∞} \frac{1}{m} · ∑_{j=0}^{m−1} W_{u′′}(j, w′′) = \overline{W} (u), a.s.

for any initial workloads w′ and w′′.

Proof. Since {δ_{nT +l}}_{n=0}^{∞} is a stationary ergodic sequence it follows directly from Birkhoff’s theorem that ([13] Theorem 6.28) lim_{m→∞} \frac{1}{m} · ∑_{n=0}^{m−1} δ_{nT +l} = 𝔼δ_{l} a.s. Since δ_{i} is a stationary sequence we have that 𝔼δ_{l} = δ for l = 1, 2, …, T. It is shown in [6] that there exist k sequences {W_{u}^{∗}(nk + j)}_{n=0}^{∞}, j = 1, 2, …, k, which are all stationary ergodic, such that these sequences couple in finite time with the workload sequences. Indeed, for any w there exists a finite random variable M such that almost surely,

W_{u}(nk + j, w) = W_{u}^{∗}(nk + j) for all n ≥ M.  (16)

Define,

\overline{W} (u) = \frac{1}{k} · ∑_{j=1}^{k} 𝔼W_{u}^{∗}(j).

From Birkhoff’s ergodic theorem it follows that almost surely

lim_{m→∞} \frac{1}{m} · ∑_{n=0}^{m−1} W_{u}^{∗}(nk + j) = 𝔼W_{u}^{∗}(j) for j = 1, 2, …, k.

Hence,

lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}^{∗}(j) = \frac{1}{k} · ∑_{j=1}^{k} 𝔼W_{u}^{∗}(j) = \overline{W} (u) a.s.

With the coupling result (16) it then follows that

lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} \overline{W}_{u}(j, w) = \overline{W} (u) a.s.

For u′ a representative of u there is a l ∈ {1, 2, …, T } such that u_{n} = u′_{l+n}, n = 1, 2, . . .. If we couple the service times in the routing sequences u and u′ such that σ_{j} = σ′_{l+j} then W_{u}(n, w) = W_{u′}(l + n, w′) a.s. for n = 1, 2, …, where w := W_{u′}(l, w′). Hence

lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{M} W_{u′}(j, w′) = \overline{W} (u) a.s.

□

Remark. If {δ_{i}} and {σ_{j}} are independent sequences of i.i.d. random variables with mean δ respectively σ, then all the assumptions of Theorem 6.1 are satisfied. Indeed, every subsequence of i.i.d. random variables is stationary ergodic (see [13] Corollary 6.33). In modern telecommunication systems the arrival process is composed of heterogeneous traffic streams and in general more complex than a renewal process. Often a Markov Modulated Poisson process is considered as the appropriate process (see [17]). This process also satisfies the assumptions of Theorem 6.1.

References

[1] E. Altman, Applications of Markov decision processes in telecommunication: a survey, In Markov Decision Processes, Eds. A. Shwartz and E. Feinberg, 2000.

[2] E. Altman, S. Bhulai, B. Gaujal and A. Hordijk, Open-loop routing to M parallel servers with no buffers, J. Appl. Probab., 37, 668-684 (2000).

[3] E. Altman, B. Gaujal and A. Hordijk, Admission control in stochastic event graphs, IEEE Trans. Automat. Control, 45, 854-867 (2000).

[4] E. Altman, B. Gaujal and A. Hordijk, Balanced sequences and optimal routing, J. Assoc. Comput. Mach., 47, 752-775 (2000).

[5] E.Altman, B. Gaujal and A. Hordijk, Multimodularity, convexity and optimization properties, Math. Oper. Res., 25, 324-347 (2000).

[6] E. Altman and A. Hordijk, Applications of Borovkov’s renovation theory to non-stationary stochastic recursive sequences and their control, Adv. in Appl. Probab., 29, 388-413 (1997).

[7] Y. Arian and Y. Levy, Algorithms for generalized round robin routing, Oper. Res. Lett., 12, 313-319 (1992).

[8] P. Arnoux, C. Mauduit, I. Shiokawa and J. Tamura, Complexity of sequences defined by billiards in the cube, Bull. Soc. Math. France, 122, 1-12 (1994).

[9] A. Bar-Noy, R. Bhatia, J. Naor and B. Schieber, Minimizing service and operation costs of periodic scheduling, In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 11-20, ACM, New York, 1998.

[10] Y. Baryshnikov, Complexity of trajectories in rectangular billiards, Comm. Math. Phys., 175 , 43-56 (1995).

[11] R. K. Boel and J. H. van Schuppen, Distributed routing for load balancing, Proceedings of the IEEE, 77, 210-221 (1989).

[12] S. Borst and K. G. Kamakrishnan, Optimization of template-driven scheduling mechanisms, J. Sched., 2, 19-33 (1999).

[13] J. Breiman, Probability, Addison-Wesley, 1968.

[14] C. S. Chang, X. Chao and M. Pinedo, A note on queues with Bernoulli routing, In 29th Conference on Decision and Control, 1990.

[15] M. B. Combé and O. J. Boxma (1994), Optimization of static traffic allocation policies, Theoret. Comput. Sci., 125, 17-43 (1994).

[16] E. G. Coffman, Jr., Z. Liu and R. R. Weber, Optimal robot scheduling for web search engines, J. Sched., 1, 15-29 (1998).

[17] W. Fischer and K. S. Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cook book, Performance Evaluation, 18, 149-171 (1992).

[18] B. Gaujal and E. Hyon, Optimal routing policy in two deterministic queues, To appear in Calculateurs Parallèles. Also available as Technical Report INRIA RR-3997, 2000.

[19] D. Gross and C. M. Harris, Fundamentals of queueing theory, Wiley Series in Probability and Mathematical Statistics, 1974.

[20] B. Hajek, The proof of a folk theorem on queueing delay with applications to routing in networks, J. Assoc. Comput. Mach., 30, 834-851 (1983).

[21] B. Hajek, Extremal splittings of point processes, Math. Oper. Res., 10, 543-556 (1985).

[22] R. Hariharan, V. G. Kulkarni and S. Stidham, A survey of research relevant to virtual circuit routing in telecommunication networks, Technical Report WC/OC/TR 90-13, University of North Carolina at Chapel Hill, 1990.

[23] A. Hordijk, G. M. Koole and J. A. Loeve, Analysis of a customer assignment model with no state information, Probab. Engrg. Inform. Sci., 8, 419-429 (1994).

[24] A. Itai and Z. Rosberg, A golden ratio control policy for a multiple-access channel, IEEE Trans. Automat. Control, 29, 712-718 (1984).

[25] H. Kameda and Y. Zhang, Uniqueness of the solution for optimal static routing in open BCMP queueing networks, Math. Comput. Modelling, 22, 119-130 (1995).

[26] L. Kleinrock, Queueing systems. Volume II: Computer applications, Wiley, New York, 1976.

[27] G. M. Koole, On the static assignment to parallel servers, IEEE Trans. Automat. Control, 44, 1588-1592 (1999).

[28] D. A. van der Laan, Routing jobs to servers with deterministic service times, MI Report no. 2000-20, Leiden University, 2000.

[29] Z. Liu and R. Righter, Optimal load balancing on distributed homogeneous unreliable processors, Oper. Res., 46, 563-573 (1998).

[30] M. Lothaire, Combinatorics on Words, Cambridge University Press, Cambridge, Reissued in 1997, 1983.

[31] M. Morse and G.A. Hedlund, Symbolic dynamics II, Amer. J. Math., 62, 1-42 (1940).

[32] Z. Rosberg and D. Towsley, Customer routing to parallel servers with different rates, IEEE Trans. Automat. Control, 30, 1140-1143 (1985).

[33] S. Sano and N. Miyoshi, m-Balanced sequences and their applications to some network scheduling problems, submitted (2000).

[34] H. Shirakawa, M. Mori, and M. Kijima, Evaluation of Regular Splitting Queues, Comm. Statist. Stochastic Models, 5, 219-234 (1989).

[35] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, Algebraic number theory and diophantine analysis, Eds.F. Halter-Koch and R.F. Tichy, Walter de Gruyter, 467-483 (2000).

[36] R. Tijdeman, Fraenkel’s conjecture for six sequences, Discrete Math., 222, 223-234 (2000).

[37] T. P. Yum, The design and analysis of a semidynamic deterministic routing rule, IEEE Trans. Comm., 29, 498-504 (1981).

A. Hordijk: Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands; email: hordijk@math.leidenuniv.nl

D.A van der Laan: Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands; email: dvdlaan@math.leidenuniv.nl