Balanced sequences and optimal routing.
The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over n letters where each letter is distributed as evenly as possible and appears with a given rate? The second objective of the paper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.
Introduction
It is a rather general problem to consider a system with multiple resources and tasks. Tasks
can be performed by any resource and arrive in the system sequentially. The problem is to
construct a routing of the tasks to the resources to minimize a given cost function. Such
models are common in multiprocessor systems and communication networks, where the
cost function may be the combined load in the resources.
Here, we show that under rather general assumptions, the optimal routing sequence in
terms of expected average workload in each resource is given by a balanced sequence, that
is a sequence in which the option to route towards a given resource, is taken in an evenly
distributed fashion.
INRIA, BP 93, 2004 Route des Lucioles, 06902 Sophia Antipolis Cedex, France. E-mail: alt-
man@sophia.inria.fr. URL:http://www.inria.fr:80/mistral/personnel/Eitan.Altman/me.html
y INRIA/CNRS/INRIA, BP 93, 2004 Route des Lucioles, 06902 Sophia Antipolis Cedex, France. E-mail:
gaujal@sophia.inria.fr.
z Dept. of Mathematics and Computer Science, Leiden University, P.O.Box 9512, 2300RA Leiden, The
Netherlands. E-mail: hordijk@wi.leidenuniv.nl. The research of Arie Hordijk was done while he was on
sabbatical leave at INRIA, Sophia-Antipolis; it has been partially supported by the Minist#re Fran#ais de
l'#ducation Nationale et de l'Enseignement Sup#rieur et de la Recherche.
This motivates the -rst part of the paper which is essentially based on word combinatorics
and uses its speci-c vocabulary. This part relies heavily on results in [9, 17].
The problem of balanced sequences and exactly covering sequences has been studied using
combinatorial as well as arithmetic techniques [20, 23, 18, 7, 16].
However, in these studies, the analysis of balanced sequences was done per se and did
not present any motivations or applications. In particular, the use of these constructions
in discrete event dynamic systems may not have been discovered before the seminal work
of Hajek, [10] in 1985. This work solves the one dimensional case problem, further generalized
in [1]. The goal of the present paper is to extend the same type of results to a
multidimensional case, which is surprisingly more diOEcult and of dioeerent nature as the
one dimensional case.
This is done in the second part of this paper, where we will show an application of balanced
sequences for routing problems. This part uses results from convex analysis, mainly
from [10, 2, 1]. The main results that are used here are of two dioeerent kinds. First, we
use the fact that the workload as well as the waiting time of customers entering a (max,+)
linear system are multimodular functions, under fairly general assumption ( stationarity of
the arrival process and of the service times)([1]). Then, we use general theorems from [2]
that prove that multimodular functions are minimized by regular sequences. The superposition
of several such sequences being a balanced sequence, this is the basis of the main
result of this paper.
It is interesting to exhibit this link between balanced sequences and scheduling prob-
lems, such as routing among several systems.
More precisely, the paper is structured as follows. In the second section, we introduce
a formal de-nition of balanced sequence and we present an overview on their properties.
The section 3 makes the link between the notion of balanced sequences and the optimal
scheduling in networks and is also devoted to prove the optimality of balanced sequences
for routing customers is a multiple queue system. Section 4 presents special cases for which
the optimal rates can be computed.
Balanced sequences
In this section, we will present the notion of balanced sequences, which is closely related
to the notion of Sturmian sequences [14] as well as exactly covering sequences. This
presentation is not exhaustive and many other related articles can be consulted for further
investigation on this topic [22, 11, 3, 5, 20, 7]. Although the section is self-contained and
presents several result which are of interest by their own, we mostly focus the rate problem
(see Problem 2), which will be used in the application section (# 3).
2.1 Preliminaries
Let A be a -nite alphabet and A Z the set of sequences de-ned on A.
If u 2 A Z , then a word W of u is a -nite subsequence of consecutive letters in u:
. The integer k is the length of W and will be denoted jW j.
If a 2 A, jW j a is the number of a's in the word W .
De-nition 2.1. The sequence u 2 A Z is balanced if for any two words W and W 0 in u of
same length, and any a 2 A,
If a 2 A, we also de-ne the indicator in u of the letter a as the function ffi a
otherwise. The support in u of the letter a is the
set S a
For any real number x, bxc will denote the largest integer smaller or equal to x and
dxe will denote that smallest integer larger or equal to x.
Lemma 2.2. If a sequence u 2 A Z is balanced, then for any a 2 A, there exists a real
number
lim
p a is called the rate of ffi a (u).
Proof. Let us de-ne s
The rest of the proof is classical by sub-additivity arguments. The proof for fffi a (u) n g n60
is similar. The fact that both limits coincide is obvious.
Note that the sum of the rates for all letters in a sequence u is one.
a2A
Now, we can present the main result which founds the theory of balanced sequences.
Theorem 2.3 (Morse and Hedlund). Suppose a sequence d 2 f0; 1g Z is balanced with
asymptotic rate letter 1. The support S 1 of d satis-es one of the following
cases.
(a) (irrational case) p is irrational and that exists OE 2 R such that
(b) (periodic case) p 2 Q and there exists OE 2 Q such that
(c) (skew case) Z such that
or
Sequences for which the support is of the form S are called bracket
sequences. This theorem shows the relation that exists between balanced sequences and
bracket sequences. The irrational case is the easiest case and can be characterized (see
Theorem 2.17). The two rational cases are more diOEcult to study. Our main objective for
studying balanced sequences is their application in routing control (see sections 3 and 4).
In our analysis, only the right tail of a sequence, that is fu i g i?i 0
for some i 0 in N maters.
Also, a sequence u and a shifted version, u 0 will have the same asymptotic performance
(see equation (7)). Hence, we consider such two sequences as being equivalent. Note that
this allows us to consider that the skew case and the rational case are equivalent.
De-nition 2.4. A sequence d 2 f0; 1g Z is (ultimately) regular if there exists two real
numbers ' and p (and an integer k) such that for all (n ?
Note that d is equivalent to S
Theorem 2.5. Let u 2 A Z .
(i)- If ffi a (u) is regular for all a 2 A, then u is balanced.
(ii)- If u is balanced, then ffi a (u) is ultimately regular for all a 2 A.
Proof. (i) is straightforward.
(ii) is a direct consequence of Theorem 2.3, since in all three cases, the sequence ffi a (u) is
ultimately regular. An elementary proof of (ii) which does not use Theorem 2.3 can be
found in [21].
In [13], the sequence u is said to have the reduction property if ffi u (a) is regular for all
a 2 A. Corollary 2.5 shows that u has the reduction property (ultimately) if and only if it
is balanced.
2.2 Constant gap sequences
Constant gap sequences are strongly balanced sequences, in the following sense.
De-nition 2.6. A sequence G is constant gap if for any letter a, ffi a (G) is periodic, with
a period of the form 0
Note that this explains the fact that G is said to have constant gaps for the letter a,
since each a is separated from the next a in G by a constant number of letters.
Proposition 2.7. Constant gap sequences are balanced.
Proof. For each letter a, ffi a (G) is of the form (0 Therefore, ffi a (G) is regular with
Using the characterization of balanced sequences
given in Theorem 2.5, this shows that G is balanced.
Proposition 2.8. Constant gap sequences are periodic.
Proof. For each letter a, ffi a (G) is periodic with period p a . The period of G is lcm(p a ; a 2
A).
In the next lemma, we give a characterization of constant gap sequences that stresses
the fact that constant gap is some kind of strong balance.
Proposition 2.9. G is constant gap if and only if, for any two -nite words, W and W 0
included in G with jjW for each letter a, jjW j a \Gamma jW 0 j a j 6 1.
Proof. Let a be a letter in the alphabet.
First, assume that G is constant gap. If jW j a \Gamma jW 0 j a ? 2, then, necessarily, jW 2.
Conversely, let a be any two words in G with no a in the subwords
U and U 0 . If jU j ? jU 2. This is
a contradiction. Therefore jU G is constant gap.
Since a constant gap sequence is balanced, each letter appears with a given rate in the
sequence. note however that since a constant gap sequence is necessarily periodic, the rate
of each letter is rational.
As we will do in section 2.4 for the case of balanced sequences, we now address the
following question:
Problem 1: Given a set (p possible to
construct a constant gap sequence on N letters with rates (p
We will not solve this problem for a general N . We will only give some properties of
the set (p which will be useful in the following. A non-eoeective characterization
of such (p in [23], under the name exact covering sequences.
De-nition 2.10. The set of couples f(' called an exact covering sequence
if for every nonnegative integer n, there exists one and only one 1 6 i 6 N such
that
As a general remark, note that (p are rational numbers of the form p
with d the smallest period of G. Therefore, we have,
for each i, k i divides
d. By de-nition of the rates, we also have p a = 1=q a for all letters.
We have the following result.
Proposition 2.11. The rates (p are constant gap if there exists N numbers
called such that the couples f(' an exact covering
sequence.
Proof. This property is a simple rewriting of the fact that each letter a i in a constant gap
sequence appears every f' i Ng.
Now, suppose that f(' is an exact covering sequence. Then in the
series
the coeOEcient of x n in this series is equal to Therefore, we have
Using this characterization we have the following interesting property.
Lemma 2.12 ([18]). Assume f(' is an exact covering sequence and that
appears at least twice in the set q
Proof. The proof given here is similar to the discussion in [23] on exact covering sequences.
e 2i-=r for some integer r ? 1. By de-nition, w is a primitive r-th root of one. We
. The set is exactly the set g. Equation (1)
speci-ed for can be written
This implies that the set cannot be reduced to a single point since w is not
zero.
To give some concrete examples, we consider the cases where N is small. First, note
that in the case where the k i are not all equal, (assume k 1 is the largest of all), we have
where l 1 is the gap between two letters a 1 . This implies,
2: (2)
Proposition 2.13. There exists a constant gap sequence G with rates only
Proof. Let a be a letter in G with gap l. Since the alphabet contains only two letters,
1. This means
Proposition 2.14. There exists a constant gap sequence G with rates (p
only if the following holds: (p or (1=2; 1=4; 1=4) (up to a permu-
tation).
Proof. Assume that (p 1
Using Equation (2), l Therefore, the sequence obtained from G when
removing all the letters a 1 is constant gap. Applying Lemma 2.13 shows that . The
only solution is 1=4. The associated constant gap sequence is
(a 1 a 2 a 1 a 3
Proposition 2.15. There exists a constant gap sequence G with rates (p
only if fp belongs to the set (up to a permutation),
Proof. We give a sketch of an elementary proof of this fact. If the rates are all equal, then
note that Equation 2 implies that if the rates
are not all equal 2. We consider any letter a assume that the number of
a 1 's in between two a i 's is not constant and takes values m and then we have
on the other hand. This is impossible
since l 1 6 2. Therefore, the number of a 1 's in between two a i 's is constant. This is true
for all i. The sequence formed by removing all a 1 's is still constant gap. It has rates of
the form (1=3; 1=3; 1=3) or (1=2; 1=4; 1=4). From this point a case analysis shows that the
original sequence has rates (1=2; 1=4; 1=8; 1=8); (1=2; 1=6; 1=6; 1=6)or(1=3; 1=3; 1=6; 1=6)g by
inserting the letter a 1 in a constant gap sequence over the letters a 2 ; a 3 ; a 4 .
These few examples of constant gap sequences illustrate the fact that the rates in these
sequences have very strong constraints.
2.3 Characterization of balanced sequences
Several studies have been recently done on balanced (or bracket) sequences [13, 20, 21, 16,
15]. In [9], a characterization involving constant gap sequences is given.
Proposition 2.16 (Graham). Let U be a balanced sequence on the alphabet f0; 1g. Construct
a new sequence S by replacing in U , the subsequence of zeros by a constant gap
sequence G on an alphabet A 1 , and the subsequence of ones by a constant gap sequence H
on a disjoint alphabet A 2 . Then S is balanced on the alphabet A 1 [ A 2 .
Proof. We give a proof similar to Hubert's proof ([11]). Let a be a letter in A 1 (the proof
is similar for a letter in A 2 . Let W and W 0 be two words of S of the same length. Then,
the corresponding words X and X 0 in U verify jjW since U is balanced. If
we keep only the 0's in X and X 0 , then the corresponding Z and Z 0 words in G satisfy
G is constant gap, and using Lemma 2.9, jjZj a \Gamma jZ 0 j a j 6 1.
We end the proof noting that the construction of Z and Z 0 implies jZj a = jW j a and
Conversely, we have the following theorem.
Theorem 2.17 (Graham). Let u 2 A Z be balanced and non periodic. Then there exists
a partition of A into two sets A 1 and A 2 such that the sequence v de-ned by:
is regular. Furthermore, the sequences z 1 and z 2 constructed from u by keeping only the
letters from A 1 and A 2 respectively have constant gaps.
The proof of this theorem was given by Graham [9] for bracket sequences. An independent
later proof can be found in [11] for balanced sequences. The relation between balanced
and bracket sequences given in Theorem 2.5 makes both proofs more or less equivalent.
2.4 Rates in balanced sequences
also note that a balanced sequence has several asymptotic properties, such as the
following lemma.
Let us formulate precisely the problem which we will study in this section.
Problem 2: Given a set (p possible to construct a balanced
sequence on N letters with rates (p
We will see in the following that this construction is not possible for all the values of
the rates (p makes the construction possible, such a
tuple is said to be balanceable. A similar problem has been addressed in [9, 15, 7], Where
relations between the rates in balanced sequences are studied.
2.5 The case
This case is well known and balanced sequences with two letters have been extensively
studied (see for example [6, 14]). The following result is known even if it is often given
under dioeerent forms.
Theorem 2.18. For all 1, the set of rates
Proof. The proof is similar to the proof of the -rst part of Theorem 2.5. We construct
a sequence S as the support of the function is a balanced
sequence because the interval ]k; k +m] contains exactly
S. This shows the value of e can dioeer
by at most one when k varies so S is a balanced sequence. If S 0 is the complementary set
of S, then it should be clear that S 0 has asymptotic rate
contains
Note that the proof of Theorem 2.18 also gives a construction of a balanced sequence
with the given rates.
2.6 The case
The case essentially dioeerent from the case 2. In the case
possible rates are balanceable while when there is essentially only one set of rates
which is balanceable. This result, when formulated under this form, was partly proved
and conjectured in [13] and proved in [20]. In earlier papers by Morikawa, [16], a similar
result is proved for bracket sequences. If Theorem 2.5 is used, then the result of Morikawa
can be used directly to prove the following theorem. Therefore, we attribute this result to
Morikawa, even if the result was stated dioeerently.
Theorem 2.19 (Morikawa). A set of rates (p only if,
or two rates are equal.
Proof. The proof of Morikawa is very technical since it does not use the balanced property
for bracket sequences. If the balanced property is used, then the proof becomes very easy.
We give a proof slightly simpler than the proof in [20]. First, assume that
let S be a balanced sequence with two letters fa; bg constructed with the rates (p 1
In S, replace alternatively the iais by the letters a 1 ; a 2 , we get a sequence S 0 on alphabet
us show that S 0 is balanced. Since S is balanced, the
number of iajs in an interval of length m is k or k +1, for some k. Now, for S 0 , the number
of ia 1 js (resp. ia 2 js) in such an interval is either is odd and k=2
or is even. This proves that S 0 is balanced.
Now, assume that (p 1 are three dioeerent numbers. We assume that
We will try to construct a sequence W with these respective rates on the alphabet fa; b; cg.
step 1: the sequence iacaj must appear in W .
There exists a pair of consecutive iaj with no ibj in between since This means that
the sequences iaaj or iacaj appear. If iaaj appears, then a icj is necessarily surrounded
by two iajs.
step 2: the sequence ibaabj must appear in W .
There exist a pair of consecutive ibj with no icj in between. This sequence is of the form
"ba n bj. Now, n 6 1 is not possible because of the presence of iacaj and b-regularity.
implies the existence of ia by a-regularity which is incompatible with
iba n bj because of b-regularity. Therefore 2. Note that this also implies the existence
of iaaj and of iabaabaj.
step 3: the sequence iabacabaj appears in W .
the sequence W must contain a icj. This icj is necessarily surrounded by two iajs since
iaaj exists by a-regularity. This group is necessarily surrounded by two ibjs since ibaabj
exists, and consequently, necessarily surrounded by two iajs, since iabaabaj exists. We get
the sequence iabacabaj.
Last step:
letter around this word can be a icj because ibaabj exists. None can be a ibj since
iacaj exists. Therefore, they have to be two iajs. Then note that the following two letters
cannot be a icj (because of the existence of iabaabaj), nor an iaj (because of the existence
of ibacj) so it is a ibj, then followed necessarily by an iaj (because iaaj exists). At this
point, we have the sequence i?abaabacabaaba?j. Both ?s are necessarily icjs.
To end the proof, note that a icj necessarily has the word iabaabaj on its right and
the same word on its left. Finally note that the word iabaabaj is necessarily surrounded
by two icjs. Therefore the sequence W is periodic of the form (abacaba) ! .
2.7 The case
The case very similar to the case rates. However when two
rates are equal, this case is more complicated.
Theorem 2.20. A rate tuple (p distinct rates is balanceable if and
only if (p
Proof. Again, it seems Morikawa has proved a similar result for bracket sequences. How-
ever, using the balanced property, the proof becomes much simpler. We suppose that
we show that there is only one balanced sequence with frequencies
those frequencies are (8=15; 4=15; 2=15; 1=15).
As a preliminary remark, note that if there exists at least one word
that does not contain any a j . This fact will be used several times in the following
arguments.
The proof involves dioeerent steps.
Step 1: W contains the words iacaj or iadaj or iacdaj or iadcaj.
There exists two consecutive iajs with no ibj in between because Therefore,
either iaaj or iacaj or iadaj or iacdaj or iadcaj exist. If iaaj exists, then, a icj is
surrounded by two iajs.
Step 2: W contains the word ibaabj
First, we show that if a word iba n bj exists, then 2. Indeed, the fact that iadaj
or iacaj or iacdaj or iadcaj exist makes ibbj and ibabj impossible. On the other hand, if
the existence of ia necessary by a-regularity and is incompatible with
the existence of iba n bj because of b-regularity.
Now, if no word of the form iba n bj exists, then there exist two consecutive ibjs with
one idj and no icj in between. This word (s 1 ) is of the form: ia i ba j da k ba l j. Note that the
numbers l may be equal to zero but b-regularity.
There also exist two consecutive icjs with no idj in between. This word (s 2 ), is of
the cj. Note that are integers that can dioeer by at most one,
the length of s 1 , js j. This is impossible by
c-regularity.
step 3: the word iabacabaabacabaj exists in W . There exists two consecutive icjs
with no idj in between. From step 3 in the proof of Lemma 2.19, we know that a icj is
necessarily surrounded by the word iabaj. Moreover, from step 4 in the proof of Lemma
2.19, we have: iabacabaabaUcabaj, where U is a word that contains no idj and no icj. U
cannot start with an iaj (because of ibacabj) cannot start with a ibj (because of iacaj)
cannot start with a icj and cannot start with a idj by construction. Therefore U has to
be empty.
Step 4: W is uniquely de-ned and is periodic of period iabacabadabacabaj.
Somewhere, W contains a idj. From this point on, we can extend the word uniquely as:
iabacabadabacabaj around this idj, and the word iabacabaabacabaj has to be surrounded
by two idjs. This ends the proof.
To complete the picture, it is not diOEcult to see that,
Proposition 2.21. if the tuple (p is made of less than two distinct numbers,
then it is balanceable.
Proof. First, if the rates are all equal, they are obviously balanceable. If three of them are
we can construct a balanced sequence with rates (3p 1
and we construct a balanced sequence with rates (p using Proposition 2.16
(where we take G the constant gap sequence (a 1 a 2 a 3
two pairs of
rates are equal, say then we construct a balanced sequence with rates
apply Proposition 2.16.
If the tuple (p is made of exactly three distinct numbers, then this is a more
complex case which is not studied here.
2.8 The general case
In this section, we are interested in the case of arbitrary N . First, note that Proposition
2.21 easily generalizes to any dimension.
Proposition 2.22. If the tuple (p is made of less than two distinct num-
bers, then it is balanceable.
Proof. The proof is similar to the proof of Proposition 2.21.
Proposition 2.23. If (p
balanceable.
Proof. The proof is very similar to that of Proposition 2.16. If W is a balanced sequence
with letters consider the sequence W 0 constructed starting from W and
replacing each ia 1 j by an element of (b 1 j, ib in a cyclic way. Note that W 0 has
the following set of rates, (p 1 =k;
Next, we show that W 0 is balanced. Since W is balanced, for an arbitrary integer m, the
number of ia 1 js in an interval of length m is n or n + 1, for some n. Now, for W 0 , the
number of ib i js in such an interval is either b(n \Gamma 1)=kc or b(n + 1)=kc. This proves that
W 0 is balanced.
For the general case and distinct rates , it is natural to give the following conjecture
(due to Fraenkel for bracket sequences):
Conjecture 2.24. A set of distinct rates fp is balanceable if and only if
We have not been able to prove this fact. Morikawa has also given some insight in this
problem. It is not clear whether it has been completely proven. Here, we only have partial
results given in the following lemmas.
Lemma 2.25. The rates are balance-
able, for all N 2 N .
This lemma is the iifj direction of the conjecture.
Proof. We construct a balanced sequence WN in the following inductive way.
First note that WN has rates
we show that WN is balanced by induc-
tion. In the sequence WN , any letter (say letter appears 2 N \Gammaj times in one period and
is of the form of 2 N \Gammaj \Gamma 1 intervals of the same length (2 j ) and one of length
By construction of WN+1 , this properties still hold and therefore, WN+1 is balanced.
Lemma 2.26. Let W be balanced with rates In
particular, this means that
Proof. If W is not periodic, Theorem 2.17 says that W is composed of two constant gap
sequences. At least one of these sequences has at least two letters, and therefore two letters
have rates which are equal by Lemma 2.12. Therefore, the rates in W of these two letters
are also equal.
Lemma 2.27. Let W be balanced with rates with the following property:
for any 1 6 i 6 N , there exists two consecutive letters ia i j with no a j in between, with
This lemma is a partial ionly ifj result for the conjecture.
Proof. The proof holds by induction. Let V k denote the period of the balanced sequence
with rates (2 2.25. We
recall that according to the construction in the proof of lemma 2.25, We
will prove by induction that W is periodic with period VN .
We -rst prove by induction on k that W contains the word V
that each letter in W , ia j
Now, for the -rst step of the induction note that according to the property on
W , W contains the word ia 1 a 1 j which is the same as iV 1 V 1 j. Therefore any other letter
is surrounded by two ia 1 js. This also implies the existence of ia 1 a 2 a 1 a 1 a 2 a 1 j by using a
similar argument as step 2 in the proof of Theorem 2.20, which ends the case
For the general case, by the induction assumption, a k is surrounded by V k\Gamma2 , and we
have the word iV k\Gamma2 a k V k\Gamma2 j. The existence of iV k\Gamma2 a proves that this
word is surrounded with two ia js. Therefore, two consecutive a k form the word
where U does not contain any letter ia j j, j ? k. If U contains ia then U is
iV k\Gamma2 a j. This is impossible because of the existence of ia
U contains any other letter ia i j, then U is reduced to this letter, and by construction of
the presence of ia contradicts the existence of ia Therefore, U is
empty and we have the second part of the proof.
Now, we -nish the proof by noticing that the letter aN is surrounded by VN \Gamma1 and by
noting that VN \Gamma1 is necessarily surrounded by ia N j.
Lemma 2.28. Assume that W is balanced. Assume that p a ? 0:5. Then the projection
W 0 of W over the alphabet A \Gamma fag is also balanced.
Proof. Choose two words
2 of length n in W 0 . Let V 1 and V 2 be any two words in
W whose projections over the alphabet A \Gamma fag are V 0
furthermore, that the -rst and last letters in V 1 and V 2 are not a. Let
denote the number of appearances of the letter a in V 1 and V 2 , resp.
then the dioeerence in the number of occurrences of any letter b in V 0and in V 0
2 is at most 1, since W is most regular, and since the number of b's in V 1 (resp.
is the same as its number in V 0
Step 2: Assume that l ? k + 1.
2 be the word obtained from V 2 by truncating the -rst and last letter. Then
and the number of a's in -
1 be the word obtained from V 1 by adding to it the next letters that
appears after V 1 in the sequence W . Then j -
and the number of a's
in -
1 is not larger than 2. This is a contradiction with the fact that W is
balanced.
Step 3: It remains to check l 1. Add to V 1 the next letter that occurs in W to its
right, to form the new word V 1 . If it is not a then we have two successive letters that are
not a, which contradicts the fact that a has an asymptotic frequency of at least 1/2. If it
is a, then V 1 and V 2 have the same number of a's. We can now apply the same argument
as in step 1 and conclude that the number number of occurrences of any letter b in V 0
1 and
in V 0
2 is at most 1.
Combining the above steps, we conclude that W 0 is balanced.
2.9 Extensions of the original problem
So far we have only analyzed the case where all the rates add up to one. The dioeerent
results tend to prove that very few rates are balanced.
Now let us look at a generalization when all the rates do not add up to one. Assume
that S is a sequence on the alphabet \Lambdag. We only require that S is balanced
for the letters a but not for the special letter  .
On a more practical point of view, the question can be viewed as whether this allows
more possibilities for rates to be balanced when ilossesj are allowed (represented by the
letter  ). Then again, in general, the rates are not balanced, even if the total sum is very
small as illustrated by the following lemma.
Lemma 2.29. For an arbitrary " ? 0, there exists two real numbers p 1 and p 2 such that
no sequence S on the alphabet fa; b; \Lambdag with asymptotic rate p 1 for letter a
and p 2 for letter b which is balanced for a and b.
Proof. Choose two irrational numbers p 1 and p 2 with
are not linearly dependent on Z. Now assume that there exists a sequence S on fa; b; \Lambdag
with asymptotic rate p 1 for letter a and p 2 for letter b which is balanced for a and b. By
Theorem 2.5, then there exists two real numbers x; y such that ffi a
otherwise. In the cube [0; , the set of points (x; dense (see for
example, Weyl's ergodic theorem [19]) and therefore hits the rectangle [(1\Gammap
This is not possible.
More on this kind of problems can be found in [21].
To end this short overview on balanced sequences, we must mention on the positive
side that iusualj rates, such as (1=k; 1=k; are often balanceable. In Appendix 4.3,
some examples of balanced sequences and their rates are given.
3 Routing of customers in multiple queues
The notion of balanced sequences gives birth to an large set of elegant properties in word
combinatorics. However, they are rarely used in other domains. The balanced sequences
in dimension used for discrete line drawing [14] and also for scheduling
optimization in [10, 8].
However, the case dioeerently than for higher dimension (as illustrated
by theorem 2.18) and does not really grasp all the complexity of the model.
Here, we present an application of balanced sequences in arbitrary dimensions to
scheduling optimization.
We consider a system where a sequence of tasks have to be executed by several processing
units. The tasks arrive sequentially and each task can be processed by any server. The
routing control consists in assigning to each task a server on which it will be processed.
The routing is optimal it it minimizes some cost function that measures the performance
of the system.
These kinds of models have used to study load balancing within several processors in
parallel processing problems as well as for eOEcient network utilization in telecommunication
systems.
3.1 Presentation of the model
In this section we consider a more precise queueing model of the system that we described.
Customers enter a multiple queue system composed of K nodes. Each node is made of
several queues which form an event graph. Event graphs are a subset of Petri nets with no
more than one input transition and one output transition per place. More details on the
dynamics of event graphs can be found in [4]. In particular, their dynamical behavior is
linear in the so-called (max,+) algebra ([4]). Many queueing networks can be represented
as event graphs, as long as there is no inside choice for the route followed by the customers.
(see [1] for a more complete discussion on this issue).
The routing of customers to the dioeerent nodes is controled by a sequence of vectors
g, with a n is in f0; 1g K and a i
means that the n-th customer is routed to queue i.
Note that a is a feasible admission sequence as long as for all n,
The link between a feasible routing policy and an in-nite sequence on a -nite alphabet
comes from choosing the alphabet A composed by the letters
Using this alphabet on K letters, a feasible routing policy can be viewed as an in-nite
sequence on A.

Figure

1 shows an illustration of the system we are considering.
We denote by T n the epoch when the n-th customer enters the system. We assume that
The inter-arrival time sequence is fffi
g. Finally, oe i;j
will denote the
service time of the n-th customer entering the j-th queue in node i.
The sequences fffi k g and foe i;j
will be considered as random processes. We also make
stochastic assumption on these sequences. The inter-arrival time of the customers and the
service times form stationary processes, and we assume that the inter-arrival times are
independent of the service times.
3.2 Optimal admission sequence
In each node i we pick an arbitrary server s i (which may be the last server in the node
for example). The performance criteria for node i will be the traveling time to server s i
node 2
node 1
node K

Figure

1: Illustration of the routing of customers in a K node system
of a virtual customer that would enter node i at time T n . Under the routing policy a,
this quantity only depends on the values of the n -rst routing choices. From the routing
sequence a, we can isolate the routing decision for node i: if a i
then the customer is
admitted in node i and if a i
then the customer is rejected (for node i). We denote
the traveling time at time T n by W i
We will be more particularly interested
in the expected value of the traveling time with respect to the service times in all the
servers contained in node i and with respect to the inter-arrival times: W i
convex increasing function.
If we focus on a single node i, the function W i
n ) has been studied in [1]. Its
most remarkable property is the fact that this function is multimodular. See [10, 2] for a
precise de-nition and several properties of multimodular functions. Here, we merely point
out that multimodularity is closely to convexity (see [2]).
Proposition 3.1 ([1]). Under the foregoing assumptions, the function W i
satis-es the following properties.
increasing in a i
Proof. These properties are shown in [1].
Using these properties, one can derive as in [2], a lower bound B i (ff; p) (which is increasing
in ff and p and continuous) for any routing a i , for the following discounted cost.X
k .
Also, for a given p, we de-ne the regular sequence with rate p and arbitrary phase ',
a
(see the de-nition 2.4). One can show as in [2] that a p (') satis-es
lim
m!1m
Here, however, we are interested in the performance of all nodes together. Therefore,
we choose as a cost function, the undiscounted average on n of some linear combination of
the expected traveling time in all nodes.
Let h be any increasing linear We consider the undiscounted
average cost of a feasible routing sequence a,
From this point on, we mimic the general method developed in [2] for our case.
We use the following notation.
Our objective is to minimize g(a).
Theorem 3.2. The following lower bound holds for all policies:
Proof. Due to Littlewood's and Jensen's inequalities as well as Equation 5, we have
lim
ff
ff
ff
where
a
ff
We note that
1. Hence, one may choose a sequence ff such that the
following limits exist:
lim
a
and
1. From the continuity of B i (ff; and ff we get from (8)
Note that there exists some p   that achieves the in-mum
since h(B 1 (p 1 ); :::; BK (p K )) is continuous in
Consider the routing policy a p
(') given for each i by
a i;p
There are some p   's for which the condition of feasibility of the policy a p
(') is satis-ed,
that is, there exists some that the regular policy a p
(') is feasible.
Using the correspondence between a routing policy and a sequence on the alphabet A,
these p   's correspond precisely to balanceable rates.
Theorem 3.3. Assume that p   is balanceable. Then a p
(') is optimal for the average cost,
i.e. it minimizes g(a) over all feasible policies.
Proof. The proof follows directly from Theorem 3.2 and Equation (6).
4 Study of some special cases
The problem which remains to be addressed is to -nd in which cases, the rate vector p   is
balanceable. We will present several simple examples for which we can make sure that the
optimal rate p   is balanceable.
4.1 The case
If the optimal rate vector is of the form p
Theorem 2.18
says that p   is always balanceable and therefore, the optimal routing sequence is given by
an associated balanced sequence. Note that this approach does not give any direct way to
compute the value of p   , however, it gives the structure of the optimal policy.

Figure

2: Routing in homogeneous queues.
4.2 The homogeneous case
Now let K be arbitrary and each node is made of a single server, all servers being identical.
This model is displayed in Figure 2.
Also assume that the function h is symmetrical in all coordinates (for example, just
the sum of all waiting times) By symmetry and convexity in (p of the function
K (p K )), which is balanceable. The associated
balanced sequence is the round robin routing scheme. Applying Theorem 3.3 yields the
following result which is new (to the best of the author's knowledge).
Theorem 4.1. The round robin routing to K identical ./G/1 queues, minimizes the total
average expected workload of all the queues over all admission sequences with no information
on the state of the system.
In [12], the round robin routing is proved to be optimal in separable-convex increasing
order for K identical ./GI/1 queues. Their method uses an intricate coupling argument,
whereas our proof is a simple corollary of the general theory on multimodular functions.
To illustrate the advantage of our approach, we further generalize the result to a system
composed of K identical (max,+) linear systems with a single entry. In this case, the
symmetry argument used in the case of simple queues still holds. Then again, the round
robin routing policy minimizes the traveling time in each system. This case includes models
such as routing among several identical systems composed of queues in tandem, for example
(see

Figure

3).
4.3 Two sets of identical servers
As a consequence of the two previous cases, we can consider a system composed of K 1
identical queues of type 1 and K 2 queues of type 2. Again, assume that h is symmetrical in
the K 1 nodes of type 1 and symmetrical in the K \Gamma 2 nodes of type 2. Then, by symmetry
arguments, the optimal rate vector p   is of the form

Figure

3: Routing in queues in tandem
This rate vector is balanceable indeed. This implies that for the weighted total average
expected workload, the optimal routing is of balanced type, if nodes of the same type have
the same weight.
Many other examples of this kind can be derived from these examples through similar
constructions.


Appendix


Here is a collection of balanceable rates. We also give a corresponding balanced sequence.
ffl (1=7; 2=7; 4=7) is balanceable and
ffl (1=11; 2=11; 4=11; 4=11) is balanceable and
ffl (1=11; 2=11; 2=11; 6=11) is balanceable and
ffl (1=11; 1=11; 3=11; 6=11) is balanceable and
ffl (1=14; 1=14; 4=14; 8=14) is balanceable and
ffl For all real number are balanceable, with
a corresponding balanced sequence constructed from a regular sequence with rate p
where all 1 are replaced in turn by the sequence (abac) ! and each 0 by the letter d.
ffl for all N , balanceable. The
associated balanced sequence is constructed recursively as in Lemma 2.25.
balanced sequence is:
balanced sequence with those rates is constructed
in the following way: Choose a balanced sequence S on letters, (A; B) with
rate (
fi). In S replace all the A (resp. B) by a 1 ; a
in a round robin fashion to get a balanced sequence with the required
rates.

Acknowledgment

The authors would like to thank Alain Jean-Marie who pointed out the reference [23] and
gave them a -rst proof of Lemma 2.12.



--R

Admission control in stochastic event graphs.
Multimodularity, convexity and optimization properties.
Complexity of sequences de-ned by billiards in the cube

Complexity of trajectories in rectangular billiards.

Journal of Combinatorial Theory
Optimal allocation sequences of two processes sharing a resource.
Covering the positive integers by disjoint sets of the form f
Extremal splittings of point processes.

Optimal load balancing on distrinuted homogeneous unreliable processors.
Markov Desicion Chains With Partial Information.
Mots, chapter Trac
Disjoint sequences generated by the bracket function i-vi
On eventually covering families generated by the bracket function i-v
Symbolic dynamics II- Sturmian trajectories
Roots of unity and covering sets.
Introduction to Ergodic Theory.
On complementary triples of sturmian sequences.
On disjoint pairs of sturmian bisequences.
Combinatoire des motifs d'une suite sturmienne bidimensionnelle.
Academic Press
--TR
Generating functionology
Optimization of static traffic allocation policies
Combinatorial properties of sequences defined by the billiard in paved triangles
On the pathwise optimal Bernoulli routing policy for homogeneous parallel servers
Combinatorics of patterns of a bidimensional Sturmian sequence.
Minimizing service and operation costs of periodic scheduling
Optimal Allocation Sequences of Two Processes Sharing a Resource
Optimal Load Balancing on Distributed Homogeneous Unreliable Processors

--CTR
N. Brauner , Y. Crama, The maximum deviation just-in-time scheduling problem, Discrete Applied Mathematics, v.134 n.1-3, p.25-50, 05 January 2004
Berth , Robert Tijdeman, Balance properties of multi-dimensional words, Theoretical Computer Science, v.273 n.1-2, p.197-224, February 2002
Berth , Robert Tijdeman, Lattices and multi-dimensional words, Theoretical Computer Science, v.319 n.1-3, p.177-202, June 10, 2004
Bruno Gaujal , Emmanuel Hyon , Alain Jean-Marie, Optimal Routing in Two Parallel Queues with Exponential Service Times, Discrete Event Dynamic Systems, v.16 n.1, p.71-107, January   2006
Shinya Sano , Naoto Miyoshi , Ryohei Kataoka, m-Balanced words: a generalization of balanced words, Theoretical Computer Science, v.314 n.1, p.97-120, 25 February 2004
Arie Hordijk , Dinard Van Der Laan, NOTE ON THE CONVEXITY OF THE STATIONARY WAITING TIME AS A FUNCTION OF THE DENSITY, Probability in the Engineering and Informational Sciences, v.17 n.4, p.503-508, October
Arie Hordijk, COMPARISON OF QUEUES WITH DIFFERENT DISCRETE-TIME ARRIVAL PROCESSES, Probability in the Engineering and Informational Sciences, v.15 n.1, p.1-14, January 2001
Eitan Altman , Bruno Gaujal , Arie Hordijk, Optimal Open-Loop Control of Vacations, Polling and Service Assignment, Queueing Systems: Theory and Applications, v.36 n.4, p.303-325, December 2000
Boris Adamczewski, Balances for fixed points of primitive substitutions, Theoretical Computer Science, v.307 n.1, p.47-75, 26 September
Raphael Rom , Moshe Sidi , Hwee Pink Tan, Design and analysis of a class-aware recursive loop scheduler for class-based scheduling, Performance Evaluation, v.63 n.9, p.839-863, October 2006
optimal control;stochastic event graphs;multimodularity;balanced sequences