Regular Ordering and Applications in Control Policies.
In this paper we introduce the notion of regular ordering for periodic sequences based on the gaps between the entries. We define the notion of regular preserving functions using Schur convexity. This is used to extend some optimization results in queuing control problems. In particular, we show that the maximal traveling time in a stochastic event graph as well as the transmission times in a channel with redundancy, decrease (in the stochastic sense) when the input sequence becomes more regular.
Introduction
A classical problem in the control of queues is to compute the optimal routing policy of a stream
of incoming customers into several queues in parallel. Often, the goal is to minimize the average
waiting time of the customers or the average load of the system.
When the number of queues is not larger than two, then the problem has been solved in several
cases. In the Markovian case, the optimal policy is a threshold policy and can be computed using
dynamic programming (see [20]). When the system is not Markovian, the optimal policy is a
Sturmian sequence as shown in [2] and te exact computation of the optimal policy has been done
in the deterministic case in [17].
However, when the number of queues in parallel is larger than two, then the problem becomes
more dicult. One of the reasons for this \three queue hiatus" is that Sturmian sequences in
dimension three or more do not exist in most cases (see [2]). The only case where this problem
has been solved so far is when the system is fully loaded and deterministic (see [22]).
Here, we will deal with the problem of routing customers in several queues in parallel using a softer
approach. We will not try to compute the optimal policy, which seems to be a very hard task.
Instead, we will introduce a partial order on the routing sequences called the regular ordering.
The main result of the paper is the following:
If the routing sequence s is more regular than the routing sequence s 0 , then the maximal waiting
times under s are smaller than the maximal waiting times under s 0 , for the stochastic order.
The work of this author was partially supported by the special year on networking at Dimacs, Piscataway, NJ.
This statement deserves several comments.
First, the notion of regularity is close the the notion of balance in the sense that a balanced sequence
is the most regular sequence possible (see Section 2.2). An integer sequence is balanced
if its partial sums over two arbitrary windows of the same length diers by at most one. They
have been extensively investigated in the past [24, 19] and lead to fruitful results in several elds
such as theoretical physics [25], combinatorics [10, 9] as well as control theory [21, 16]. In a recent
paper, [3], it is shown under rather general assumptions that balanced sequences minimize several
cost functions in discrete event systems. This result relies on the following theorem.
are multimodular functions, then the Cezaro limit lim N!1N
is minimized by a balanced sequence.
Second, majorization and Schur convex functions seem to be the right notions to use when comparing
the dispersion of nite sequences [23]. However, majorization does not take into account
the initial positions in the sequences to be compared since it is left invariant by the group of all
permutations.
It is often desirable to take the initial positions into account. For many systems, the input sequence
certainly induces a dierent behavior than the input sequence (1; 0; which
looks more balanced. However, these two sequences cannot be compared by using the classical
majorization technique because the former is a permutation of the latter. To overcome this dif-
culty, we introduce the notion of gap sequences (similar to partial sums, already used in [13])
that takes into account the initial positions in the sequence. This will narrow the gap between the
notion of Schur convexity and multimodularity as shown in Appendix B.
Finally, the usual performance measure in queuing networks is the average waiting time. However,
in communication models where real time constraints are important (such as voice and video traf-
c) the maximal waiting time (or sojourn time) are more important than the average. In Section
3, we show that for FIFO stochastic event graphs, the maximal waiting time (or sojourn time)
is regular preserving. As for computational issues, nding good allocation patterns (i.e. very
regular sequences), is possible via a mathematical programming problem with convex objective
functions as in corollary B.3. A similar procedure for minimizing the average waiting time has
been used by Combe and Boxma [15] and in [14] for dierent performance measures.
The rest of the paper is organized as follows. In section 2, we introduce the notion of gap sequences
and balanced sequences and the regular ordering.
In section 3, we introduce a model of a controlled queue with periodic inter-arrival sequences and
stationary service times. We show that the maximum waiting time is regular preserving w.r.t. the
inter-arrival time as well as w.r.t the service times. Section 3.6 extends the result to a routing
problem between several queues. Finally we show in Section 4, that the transmission rate on a
link with redundancy is also regular preserving.
Preliminaries
This section is devoted to the denition of gap sequences, balanced sequences and to the introduction
of the notion of regularity.
2.1 Gap Sequences
We use the notation for the set of all non-negative integers and we consider the
set P(T ; n) of all non-negative integer sequences size T which sum exactly
to n. Let s 2 P(T ; n). We call (p s the positions in s of all its partial sums.
We dene the vector d i (s) of the gaps of order i > 1 in the sequence s, by:
When the sequence s is in f0; 1g T , then the gaps are never null and measure the size of the number
of elements in the sequence s between the ones. This is illustrated in Figure 1.

Figure

1: Gaps of order one and two for a sequence s in P(9; 3).
2.2 Balanced Sequences
Denition 2.1. A sequence s is balanced if for all j, k and n,
6 1:
Theorem 2.2 ([24]). If a sequence s in P(T ; n) is balanced, then there exists  2 [0; 1] such that
for all j > 0,
Proof. The proof comes from [24] adapted to the nite case.
If s is a balanced sequence then the associated gap sequences have the following property.
Lemma 2.3. If s is a balanced sequence in P(T ; n), then for all j; i, d i
eg.
Proof. By denition, d i
By denition of p j , we have:
jg. Therefore,
This implies that
Similarly, we have:
As for d i
j , we get by subtracting the two previous equations
The following lemma in the converse of Lemma 2.3.
Lemma 2.4. Let s be a sequence such that for all i, all the gaps of order i, d i
dier by at most
one. Then, s is balanced.
Proof. Assume that s is not balanced. There exist two intervals of the same length, l. w 1 and
w 2 such that the sum in w 1 , denoted n 1 is larger than the sum in w 2 , denoted n 2 , plus two:
2. This means that there exists j 1 and j 2 such that d n1
j1 6 l and d n1
2.
Lemma 2.5. A sequence s 2 P(T ; n) is balanced if and only if d 1 (s) is balanced.
Proof. The \only if" assertion: we consider the sequence d 1 (s). Let w
kg be two windows of length k. Then the sums over w 1 of the sequence d 1 are
of the form d 1
and the sums over w 2 are d 1
By lemma 2.3, then these two quantities dier by at most one.
The \if" assertion: d 1 (s) is balanced means that there exists  such that for all j, d 1
This means that
Therefore, for any order i, the gaps of order i dier by at most one. By applying Lemma 2.4, s is
balanced.
Remark 2.6. Note however, that the gaps of order higher than one in a balanced sequence may
not be balanced. For example, if d 1 (which is balanced), then d 2
(5; 6; 5; 5; 6; 6; 5) which is not balanced because it contains two consecutive 5 (which sum up to 10)
and also two consecutive 6 (which sum up to 12).
2.3 Regularity and Schur Convexity
If x 2 R n , then we denote by the components of x arranged in decreasing
order. For x; y 2 R n , we say that x (resp. strictly) majorizes y (denoted x  y) (resp. x  y) if
y [i] and
(resp. with strict inequality for at least one m).
A function f : R n ! R is (resp. strictly) Schur convex if x  y
f(x) > f(y)). For more details on the theory of majorization, see [23].
Denition 2.7. If s; s 0 2 P(T ; n), then s 0 is more regular than s (denoted s
Lemma 2.8. The balanced sequences are the minimal sequences in P(T ; n) for the regularity
order. Moreover, if s is balanced, then for all s
Proof. This result is a consequence of Lemma 2.4. Indeed, if n divides iT , then for a balanced
sequence , d i
n , which is minimal. If n does not divide iT , then for the balanced sequence,
c; d iT
eg and is also minimal.
Balanced sequences in P(T ; n) will also be called the \most regular" sequences in P(T ; n) in the
following.
Example 2.9. Let us compare three sequences in P(6; 3): s
and s using the regular ordering. The respective gap sequences are:
Using majorization, it is not dicult to check that
According to the denition of the regular ordering, this means that s 3 Actually, s 3 is
balanced and is the most regular sequence in P(6; 3).
Denition 2.10 (regular-preserving functions). A function f : N T ! R is regular-preserving
(r.p.) if x
Lemma 2.11. A function f : N T ! R is regular-preserving if and only if it can be written under
the form:
is increasing in all coordinates and H are Schur convex.
Proof. The only if assertion is a direct consequence of Lemma 2.8. As for the if assertion, then f
is necessarily Schur convex in all d i . Now, the combination of all these arguments for all i shows
that f is of the form given in the lemma.
Note that if f is regular preserving on the set P(T ; n) then it reaches its minimal value for the
balanced sequences.
Remark 2.12. (Regularity without using the gap sequences)
The denition of regularity, as well as regular preserving functions, can be done in a similar fashion
by using the partial sum sequences of the original sequence s instead of the partial sums of its
order one gap sequence.
All the results given in this paper are still true in this new framework.
The passage from one framework to the other is simply done through Equations (1) and (A.4).
Application 1: Maximal Waiting Times in Networks
In this part, we show that the maximum waiting time in a queuing system with general stationary
inter-arrival and service times is a regular preserving function.
3.1 The D/D/1 Model
First, we consider a slotted D/D/1 queue where the arrival sequence s is periodic with n customers
arriving every T time slots (each of unit length). Therefore, s 2 P(T ; n) ! . By denition, the
number of customers arrivibg at time i is s i . The i-th customer arrives at time p i (s) and brings
a workload of  in the system.
We will also denote by C load brought by n consecutive customers.
We nally require that the queue is initially empty and that the customers are served in a FIFO
order (this last assumption can be relaxed to a non-idling server assumption in some cases).
let us consider the waiting time W i of the ith customer that enters the system. We have
f
We dene M(s;
Theorem 3.1. The function M(s) is regular preserving.
Proof. First, let us remark that if C > T , then W
In the rest of the proof, we will only consider the case where C 6 T . In that case, note that after a
transient period of length n, the waiting times are periodic: W Also note that
since the system is initially empty, the maximum waiting time is not reached during the initial
transient period. So we have
f
Equation (2) follows from the fact that C 6 T . Equation (3) comes from Equation (18). Changing
the order of the two max operators yields Equation (4).
Now, the function d j 7! max n
i Tg is Schur convex for each j and the function
M is increasing in d j for all j, and thus satises the conditions of Lemma 2.11. This means that
M is regular preserving.
Corollary 3.2. Among all inter-arrival sequences in P(T ; n), the balanced sequence minimizes
the maximum waiting time in the system. Moreover, for two sequences s; s
Remark 3.3. The function M(s) is multimodular (see Appendix B). This is a direct consequence
of Corollary B.3.
3.2 Characterization using regular preserving functions
The function M when plays an important role. Indeed, we have the following result giving
yet another characterization of balanced sequences.
Theorem 3.4. If
balanced.
Proof. When
Note that jT=n is the average value of d j
(s). Using Lemmas 2.3 and 2.4, s is balanced is equivalent
to the fact that M(s) < 1
3.3 The average waiting time is not regular preserving
In this section, we will show that unlike for the maximal waiting time, the average waiting time
in a stable D/D/1 queue is not regular preserving through an example.
Consider in P(16; 5) the sequences s and s 0 with the respective one-order gaps,
It is immediate to check that s D s 0 . However, if one computes the average waiting time in both
cases, when the load brought by each customer is equal to 3, one gets:
Remark 3.5. The function W is multimodular (see [1]). Therefore, it is minimized by a balanced
sequence in P(16; 5): W if u is a sequence such that d 1
3.4 The G/G/1 Model
Here, we generalize the previous model. The deterministic arrival process is replaced by a stochastic
process with stationary interarrival times: f i g i2N . The load carried by the k-th customer is
denoted by  k . The sequence f k g k2N , is stationary and independent of the arrival times. We
denote by  i (s) the time elapsed between the arrival of customer i and customer i +1 for sequence
s,
ps (i+1)
j=ps (i)+1
Using Lindley's equation, the waiting time of the i-th customer satises
f
If we consider the maximal waiting time within on period, starting with customer m+ 1, we dene
In a similar fashion as with the D/D/1 case, we dene
f
Intuitively,  n
r;m is constructed by going back in time for r customers only, while  n
goes back to
time
Note that if the queue has emptied during the last r arrivals, then both quantities coincide.
We assume that the queuing system is stable, that is TE( 1 generalizes the
previous assumption, C 6 T to the stochastic case). Under this stability condition, the queue
empties almost surely in nite time. Therefore, taking r large enough will ensure that  n
r;m and
will coincide. More precisely,
n
an;an
an
Now, we have,
an;an
k=i an
k=i an
Lemma 3.6. Let us assume that s and s 0 are two sequences in P(T ; n) such that s E s 0 . Then,
an;an st  n
an;an
Proof. For a given pair (i; ng  f1;    ang, we know by denition of the regular
ordering that there exits ng such that d j
Now, we dene a coupling of the service sequence as well as of the arrival sequence such that
N. Note that the coupled sequences have
the same probability distributions as the original ones because of stationarity and independence
between them and because the sequences  and  are independent of s and s 0 .
Using this coupling, and considering Equation (8), we have directly
i+an X
Since during a periods, the total number of arrivals under s and s 0 is the same and using the
coupling, we have
i+an 1
ps (i+an) X
p=ps (i)+1
ps (i)+Ta X
p=ps (i)+1
Finally, using the fact that d j
ps (i+j)
p=ps (i)+1
ps (i)+d j
p=ps (i)+1
Using these three relations,
an
i+an X
i+an 1
This is true for all i, and therefore also for the maximum over all possible i from 1 to an. Using
the fact that under the coupling, the sequences  0 and  0 are in a \typical" situation, we get
an;an st  n
an;an
Now, the stationary version of the queue is considered. Using a backward coupling argument and
Lemma 3.6, we obtain the following theorem.
Theorem 3.7. Let W i be the stationary waiting time in a stable G/G/1 queue. Then for two
sequences s; s
3.5 The Event Graph Model
We further generalize the previous model in several ways.
Networks assumptions. We replace the single queue by a network made of Q servers (tran-
sitions) and P buers (places) forming a FIFO stochastic event graph with a single entry.
(see [7] for more details on this class of networks. In particular, this class includes all queues
in tandem with general blocking.
Stochastic assumptions. The service time at node j for the k-th customer is denoted by  j
k .
The sequence f j
k g k2N;j2Q is stationary and independent of the arrival sequence. However
no independence assumption among the service times is required.
Initial state assumptions. We assume that initially, the event graph is empty, in the sense
that there is not any customer in any buer. (this is a generalization of the empty queue
assumption). Without loss of generality, we can further assume that each buer contains at
most one customer initially.
To any stochastic event graph, we can associate a family of matrices, A('), of size QQ. The entry
(i; in matrix A(') is the maximum over all the sums of the service times of the '-th customer,
' , in all the nodes k on any path from node j to node i with no initial tokens, except at node j,
and is 1 otherwise.
In the following, we will be using the (max; +) notation, where  stands for max
and
for +.
Matrix operations are dened accordingly. For more details on (max,+) notations and its use in
event graphs, see for example [7].
The matrices A(') exist and are nite whenever the network cannot reach a deadlock state (see
[7]). In that case, let X q (n) be the epoch when the n-th customer completes its service in server
q. Then the vector the following recurrence equation:
Let Wn be a vector , with its q-th component equal can be
seen as the traveling time for customer n between its entrance in the system and its passage in
server q.
Lemma 3.8 ([1]). Wn satises the following equation:
where D(h) is the diagonal matrix with h on the diagonal and 1 everywhere else, and B(n) is
a vector which describes the input connection.
Equation 9 can be seen as a vectorial form of the Lindley's equation. Its solution is similar to the
solution of the scalar case.
O
If we dene as previously,  n
O
We get by a similar technique as in the G/G/1 case (with a vectorial notation),
n
an;an
an
provided the event graph is stable (see [6]).
The quantity  n
an;an can be transformed using the fact that diagonal matrices commute with
everything.
an;an
O
O
O
an
O
B(an j
i+an 1
O
an
O
B(an j
i+an 1
O
O
Lemma 3.9. Let us assume that s and s 0 are two sequences in P(T ; n) ! such that s E s 0 . Then,
an;an st  n
an;an
Proof. The proof is similar to the single queue case, using a coupling argument and the denition
of the regular ordering.
For a given pair (i; ng  f1;    ang, we know by denition of the regular ordering
that there exits ng such that d j
Now, we dene a coupling of the service sequence such that for each queue q,  0 q
k+i . As
for the interarrival sequence, we set  0
Note that the coupled sequences have the same probability distributions as the original ones
because of stationarity and independence between them and because the sequences  and  are
independent of s and s 0 .
Using this coupling, we have by denition of A(k),
i+an 1
O
B(an
O
B(an
During a consecutive periods, the total number of arrivals with s and s 0 is the same. Therefore,
we have using the fact that D(  k (s)) are diagonal matrices,
i+an 1
O
ps (i+an) O
p=ps (i)+1
ps (i)+Ta O
p=ps (i)+1
O
O
As for the last term,
O
ps (i+j)
O
p=ps (i)+1
ps (i)+d j
O
p=ps (i)+1
O
O
These three relations are true for all i and j, therefore, considering Equation (14),  n
an;an st
an;an
Finally, we obtain the following extension of Theorem 3.7.
Theorem 3.10. In a stochastic event graph, the maximum traveling time M(s) over one period
of the admission sequence is a regular preserving function (in the stochastic sense).
3.6 Routing Problem
Now, we consider a network of K identical queues in parallel. Customers enter a system composed
by K queues in parallel. The routing of the customers is controlled by a sequence of vectors fS i g,
with
means that the i-th customer is routed to queue j. Note
that S is a feasible admission sequence as long as
Customers arrive in the system at each time unit and each customer brings a constant load of .

Figure

2 displays the model we are considering.
3.6.1 The Constrained Case
We consider periodic routing policies S satisfying the following constraint:
are xed with
In other words, S We denote this ste of policies
by

Figure

2: Routing of customers in a multiple queue system
Now, we dene I(S) to be the maximum waiting of any customer in the system, for S 2
is the maximum waiting time in queue j.
We say that the vector (n 1 ;    ; nK ) is balanceable if there exists S 2 A(n 1 ;    ; nK ) such that for
all j, S j is balanced. See [2] for a more detailed discussion on balanceable vectors. From Lemma
2.8 and 3.1, we get,
Lemma 3.11. If (n 1 ;    ; nK ) is balanceable then I(S) is minimized by a routing policy S such
that each S j is balanced.
Proof. This result is a direct consequence of Lemmas 2.8 and 3.1.
This result is similar to some extend to the results proved in [2] where multimodularity of the
waiting times in each queue is used. However, we get a new result here which follows directly from
the previous lemma and which holds for all (n necessarily balanceable).
Theorem 3.12. If such that for all j, S j D U j , then I(S) > I(U).
3.6.2 The Unconstrained Case
Now, we do not x the number of customers sent to each queue.
We want to consider all admission sequences S in the set
Lemma 3.13. The function I(S) is minimized on A for some balanced S
Proof. First, note that if n
(see [2] for a proof). Let b be a vector with such a property. Second, note that if not all n j 2
dT=Keg, then at least one of then is larger than dT=Ke. Finally, note that if s is a
balanced sequence in P(T
Now, the proof goes like this. By Theorem 3.12, I is minimized on A(b) by a balanced sequence
S(b). Moreover, there is some j such that dT=Ke. For any U
which is not in A(b), then there exists k such that n k > dT=Ke.
This nishes the proof
3.7 Computational Problems
For the constrained problem, we can compute the best sequence using a procedure similar to the
one used in [13] with quadratic programming techniques.
As for the unconstrained case, from Lemma 3.13, it is easy to see that when T=K 2 N, then the
best routing policy (which minimizes the function I) is the round robin policy. Similar results can
be found in [2].
However, when T=K 62 N, then little was know before. Here, we can come up with the optimal
routing sequence using the following procedure.
First, we compute the optimal sequence using Lemma 3.13. This sequence is
unique up to a permutation. Note that by symmetry of the cost function, all those permutation
will perform the same. Moreover, since all balanced sequences with the same number of appearance
in the routing sequence are shifts of each other, then for all j such that n dT=Ke, all the waiting
times are equal.
The construction of S j (b) for any j can be done by any known method to construct balanced
sequence, as for example, by using the Beaty construction (see [11]) or the iterative formula given
in Theorem 2.2.
3.8 Development of an example
Let us assume that we want to route customers into three parallel event graphs
dierent service times. For some reason, the proportions of customers sent to must be
1=2; 1=3 and 1=6 respectively. This is a case where the routing policy is constrained to stay in the
set A(3; 2; 1) with a period equal to
The proportions 1=2; 1=3; 1=6 are not balanceable. Therefore, it is not possible to nd a routing
sequence which is balanced for each event graph. However, we can use the regular ordering to
compare several policies.
If we consider the sequence of customers sent in E 1 we get S
In example 2.9, we showed that S 0
If we consider the sequence of customers sent in E 2 we get S
(0; 0; 2; 0; 0; 2). The sequence S 0
2 is balanced. Therefore, S 0
Finally, if we consider the sequence of customers sent in E 2 we get S
which are equal.
Since the sequence S 0 is more regular than S for all the event graphs, then the maximal waiting
time under S 0 is smaller than the maximal waiting time under S (in the stochastic sense). This is
true for all the distributions of the service times in the three event graphs.
However, if we consider S
1 but S 0
. The routing sequences
are not comparable for the regularity ordering. For some distributions of the service
times in the three event graphs then S 0 will be better than S 00 and for some other distributions,
S 00 will be better than S 0 .
Application 2: Assignment to one-buer queues with re-
dundancy
In this section, we present an example of optimal control of admission into a single buer queue
with redundancy.
{ Transmission opportunities occur at time T At each transmission opportunity, a
controller can decide to actually transmit a packet, or not. If transmission occurs, we assume that
it is instantaneous. Dene
{ At a down link node in the network a packet that has been transmitted is buered in a single
buer till its service there is completed. The duration of the service is exponentially distributed
and it has expectation  1 . We assume that the delay between the transmitter and the down link
node is zero (the results of this paper do not change if we take this time to be any other constant
period).
{ If a packet is transmitted before the previous packet has completed its service time then it is
lost.
A model that can be used to solve this problem was introduced and studied in [5]. Here, we further
focus on the following problem arising from higher layer network considerations. We consider the
problem of redundancy of packet transmission: each packet is retransmitted at K consecutive
transmission opportunities, which we call a frame, so as to decrease the probability of losses.
Thus, only if all the K packets in a frame are lost then the frame, or equivalently the original
information packet, is considered to be lost.
Our goal, roughly speaking, is to obtain a control with two objectives: on one hand it maximizes
the average throughput, and on the other it minimizes the loss probabilities of frames. Since the
throughput is the acceptance rate minus the losses, the problem can be formulated as maximization
of the average number of accepted packets, on one hand, and minimizing the loss probabilities of
frames, on the other.
We now formulate more precisely our problem. We dene a control policy as a sequence fs i g,
a transmission is scheduled at the ith transmission opportunity, and it is 0
otherwise. We consider here the case where the controller has no information on the state of the
buer (nor on which packet is the beginning of a frame).
. The actual kth transmission occurs at times p s (k) (see Denition 1). We
dene the process X k to be the number of packets in the buer just prior to time p s (k). Dene
as
where  is a negative constant. We consider the problem of minimizing G over all sequences s.
Note that D(N)=N is the acceptance rate, whereas the second term is the average number of
frames lost among the rst N ones. The cost thus contains a term responsible for maximizing
the throughput and a term for minimizing the loss rates. The parameter  can be viewed as a
Lagrange multiplier related to a constrained problem; indeed, in [5] a similar problem (for the case
studied where the loss rate is to be minimized subject to a constraint on the rate of
acceptance of packets.
Next, we focus on the cost G(s). We shall restrict to policies s that are periodic. (Recent techniques
in [12] can be used to show that restricting  to periodic policies is without loss of optimality.)
Our main result, stated below, is that G(s) is regular-preserving. (This allows us to conclude, in
particular, that there exists an optimal sequence which is balanced.)
Theorem 4.1. Assume that  k are stationary and that the service times are i.i.d. exponentially
distributed, and independent of the sequence  k . Let s 2 P(T ; n) ! . Then
(i) G can be rewritten as
where d k
i is dened in (1).
(ii) G(s) is regular-preserving for n > K .
Proof. (i) Let n denote the length of the time interval that started when the (n K+1)th packet
was transmitted, and ended when the nth packet is transmitted. fn
only if there has been no service completion during n , and is otherwise 1. Thus, the
expectation of fn (s) equals the probability that an exponential random variable with parameter
is greater than or equal to n . Using the periodicity of s, this yields (i).
(ii) This follows directly from Theorem B.2. Note that since g 0 is convex in x,
A Appendix: properties of the gap sequences
This appendix gives several properties of the gap sequences which have some interest by their own.
The two following lemmas are straightforward consequences of the denition of the gaps.
Lemma A.1. The gap sequences satisfy the following properties:
Proof. The proof is a straightforward consequence of the denition of the gaps.
Lemma A.2. Let s and s 0 be two sequences in P(T ; n). If s 0 is a shift of s or a mirror of s (i.e.
j+k or s
Proof. The proof also follows directly from the denition of the gaps.
Remark A.3. The converse of Lemma A.2 is false in general, as shown by the following counter
example choose s and s 0 such that d 1
s 0 is not a mirror nor a shift of s. However, for all order i, we have fd i )g. We will
prove in the following (see Remark A.6) that the converse of Lemma A.2 is true in the special case
of balanced sequences.
Lemma A.4. If s 2 P(T ; n), then d 1 is a shift of s.
Proof. By using Equation (17), then d 1 be a shift of s such that
and such that d 1 We will show that d 1 (d 1
ig. Now we compute
We can construct the dierent gaps by computing in the set Z[X ]=(X n 1). Indeed, from the set
(s), we can dene the polynomial
Note that by denition, we have P i
Lemma A.5. Let i > 1. The original sequence s can be retrieved from d i (s) if and only if i and
are relatively prime.
Proof. There is a one to one correspondence between s and d 1 (s). Therefore, we rather show
that the knowledge of d i enables one to compute d 1 (s) if and only if i and n are relatively
prime. If i and n are relatively prime, then the polynomials X n 1 and X are
relatively prime. Using the Bezout equality, there are two polynomials u(X) and v(X) in Z[X]
and a non-zero integer k such that 1). Therefore,
This counter example was provided to the authors by Jer^ome Galtier
by multiplying by P 1
s (X), we get kP 1
s (X)u(X) mod (X n 1). The knowledge of P 1
induces the knowledge of d 1 (s), which in turn gives all gaps by using Equation (16).
On the other hand, if i and n are not relatively prime, then gcd((X
and if we denote by q(X) 4
1). Therefore, two dierent gap sequences of
order one are compatible with the gap sequence of order i.
Remark A.6. Note that if for a sequence s, all the gaps of all order i dier by at most one and
are balanced by lemma 2.4. On the other hand, all
balanced sequences are shift of each other (see Theorem 2.2) (It is interesting to see that in this
case, all mirror transformations are also shifts). This is an answer to the question asked in Remark
A.3 in the case where the gap sequences are all formed by two consecutive numbers.
relations between regularity and multimodu-
larity
Multimodularity is a notion of discrete convexity which has been introduced in [21]. It has been
used extensively in the context of the admission control of queues [3, 1, 2, 4, 18]. Therefore, it is
interesting to see if regular preserving functions have some kind of discrete convexity properties.
In this appendix we will show that all regular preserving functions are multimodular in some sense
whereas the reverse is not true.
denote the vector with all components equal to 0 except the i-th component which is
equal to 1. Dene b g.
Since we deal with sequences which sums are xed to n, we use an adapted version of the denition
of multimodularity.
Denition B.1. A function f on P(T ; n) is multimodular with respect to F if for all
This is not the classical denition given by Hajek in [21], which considers arbitrary sequences
in N T . However, both denitions are closely related. One can show that the projection of a
multimodular function (in the sense of Hajek) on P(T ; n) is multimodular according to Denition
B.1. (see [3] as well as [8] for a deeper insight on the denition given here.)
Theorem B.2. Let f(s) be a function that only depends on d i (s), which is also denoted by
can be put under the from
is a convex function,
then it is is multimodular on P(T ; n).
Proof. According to the denition of multimodularity, we need to check the inequality (19) for all
First note that for all 1 6 k 6 T , there exists j k such that:
Now, for any 1 6 k; l 6 pn+i such that j k 6= j l  i, then b l and b k modify dierent gaps. Therefore,
For
This is positive since g is convex.
The following corollary covers the case when several gap orders are used.
Corollary B.3. If for all
are convex functions, then
dene the function
where c i are non negative constants. Then f is multimodular.
Proof. For all i, the function f i positive linear combination of
multimodular functions is multimodular.
Remark B.4. Note that the functions f i a \characteristic set" of regular preserving
in the same way sums of convex functions play an important role among Schur convex functions
([23]).
Remark B.5. Functions of the form (21) have been used in [13] as a criterion to test regularity of
a sequence. In that paper, the minimization problem of functions of this form is written as under
quadratic assignment formulation. This makes computations possible for small n and T and can
be used for optimization purposes.
In order to prove that a balanced sequence minimizes a function f as in (21) ( f(s) is regular
preserving and multimodular), one can choose two dierent methods. First, one can try to use the
fact that f(s) is multimodular in N T . By referring to a general (complicated) theorem proved in
[21, 3], f(s) will be minimized by a balanced sequence and then use the fact that if s is balanced,
then s is a balanced sequence in P(T ; n).
Another way to prove the same result, it by using the fact that f(s) is regular preserving directly.
This second proof is easier and has a clear advantage on the previous approach since it provides
a more precise result. It says that if s D s 0 , then f(s) > f(s 0 ).
This fact will be illustrated in the following section, where we show that a given cost function is
ri. The minimization will then derive directly from Lemma 2.8 as well as the comparison between
several policies.
Remark B.6. Finally, one may remark that regular preserving functions constitute an essential
class among multimodular functions. Indeed, as shown in Section 3.2, if a given sequence in
possible regular preserving functions, then this sequence in balanced.



--R

Admission control in stochastic event graphs.
Balanced sequences and optimal routing.
Multimodularity, convexity and optimization proper- ties
Optimal open-loop control of vacations
Optimal admission


Towards a uni
Complexity of trajectories in rectangular billiards.
The book of L
Mots, chapter Trac
Optimal routing problems and multimodularity.
Optimization of template-driven scheduling mechanisms
Optimization of template-driven scheduling mechanisms

Optimal allocation sequences of two processes sharing a resource.
Optimal routing policy in two deterministic queues.
Monotone optimal control of permutable gsmps.
Covering the positive integers by disjoint sets of the form f
Optimal control of two interacting service stations.
Extremal splitting of point processes.
Dinard Van Der Laan.
Theory of Majorization and Its Applications
Symbolic dynamics II- Sturmian trajectories
Quasicrystals and geometry.
--TR
admission control;regular ordering balanced sequences;schur convexity;plus algebra