3. GRAPH REDUCTION
In this section we explore graph properties that
permit a reduction in the number of states and transitions
considered in the problem. We introduce the idea
of "free stashing," which allows a number
of transitions to be eliminated. Next, we assess
conditions for suboptimal premature stashing, which
also enables reduction of transitions. Finally,
we prove that these reductions do not affect the
optimal solution.
Free Stashing
"Free stashing" implies that if a client
can be stashed at no additional cost, he should
always be stashed. This main result is derived from
two following lemmas, but we first must present
additional notation and two important notions that
define relationships of one state with respect to
another.
Notation:
P[supU][subk] minimum cost path of length k starting
at state U,
P[supU][subk] cost of P[supU][subk],
D[subU]: set of clients for which stashed copies
reach their maximum age in state U; in any state
one transition away from U, these clients must be
restashed,
D(A): set of clients that are reached by stashing
tree A.
Definition. A tree stashing A is usable from state
U if D[subU] subset or is equal to D(A), that is,
a stashing tree is usable from a state if such a
tree covers clients that must be stashed in any
transition exiting that state.
Definition. U is superior to V, U sup V equivalence
u[subi] less than or equal to v[subi], universal
quantifieri is an element of D.
Lemma 2. If U sup V then all stashing trees usable
from V are also usable from U.
Proof. By definition tree A is usable from V if
D[subV] subset or is equal to D(A). If U sup V then
D[subU] subset or is equal to D[subV], and since
D[subV] subset or is equal to D(A), D[subU] subset
or is equal to D(A), which completes the proof.
Lemma 3. If U sup V, then C[supU][subk] less than
or equal to C[supV][subk].
Proof. From the previous lemma we have seen that
if a tree is usable from V, it is also usable from
U. Let U' and V' be the states reached after using
the same stashing tree from U and V, respectively.
It is clear that U' sup V'. If Lemma 2 is applied
repeatedly, then the trees used along P[supV][subk]
can be used to build a valid path from state U.
Therefore, the cost C[supV][subk] is an upper bound
for C[supU][subk].
Theorem 3. Let N[subP] and N[subQ] be two subsets
of clients so that
Multiple line equation(s) can not be represented
in ASCII text.
and
Multiple line equation(s) can not be represented
in ASCII text.
Let C(N[subP]) and C(N[subQ]) represent the cost
of the respective stashing trees for these subsets
and let C(union of sets N[subP] and N[subQ]) = C(N[subP]).
Then from any state U, there is a path P[supU][subk]
that does not contain any state where only client
subset N[subP] is stashed.
Proof. Let U be a state such that D[subU] subset
or is equal to N[subP]. From this state, two scenarios
are considered. In the first scenario, the stashing
tree that refreshes only clients belonging to subset
N[subP] is used. In the second scenario, the stashing
tree that refreshes clients belonging to subset
(union of sets N[subP] and N[subQ]) is used. In
the first scenario, state V is reached, whereas
in the second scenario, state W is reached. The
Cost of reaching either state V or state W is C(N[subP]).
Also, since a superset of clients are stashed for
the second scenario, W sup V. Then, by Lemma 3,
C[supW][subk] less than or equal to C[supV][subk].
This implies that the minimal cost path starting
at state U and going through state W will never
cost more than the one through V. Since this result
is valid for any state U where D[subu] subset or
is equal to N[subP], the theorem is proved.
This theorem completes the results related to "free
stashing." In fact, if two subset N[subP] and
N[subQ] can be identified that fulfill the conditions
of the previous theorem, then all transitions leading
to a state in which only clients belonging to subset
N[subp] are stashed can be eliminated. In other
words, all transitions leading to class k so that
J[subk] = N[subP] can be removed. Moreover, when
searching for a minimal finite path, states belonging
to OMEGA[subk] can also be removed except, possibly,
for the initial state of the path.
Suboptimal Premature Stashing
A client is said to be stashed prematurely when
a new copy is sent before the maximum lifetime of
the old copy is attained. Figure 5 presents a simple
example showing clearly that there is no point in
stashing client d[sub1] prematurely when client
d[sub2] is stashed, or vice-versa. This section
explores some conditions under which it is suboptimal
to stash a client prematurely. We first present
the following lemma, which links the cost of stashing
any subset of clients N[subP] and N[subQ].
Lemma 4. C(union of sets N[subP and N[subQ])) less
than or equal to C(N[subP]) + C(N[subQ]).
Proof. To stash the set union of sets N[subP] and
N[subQ], it is clear that the trees used to stash
sets N[subP] and N[subQ] independently could be
used at a cost of C(N[subP]) + C(N[subQ]); therefore,
this sum is an upper bound on the optimal cost of
stashing union of sets N[subP] and N[subQ].
We are now ready to establish the theorem that
states conditions for suboptimal premature stashing.
Theorem 4. Let N[subP] and N[subQ] be two subsets
of clients, N[subP] subset or is equal to D, N[subQ]
subset or is equal to D, such that
Multiple line equation(s) can not be represented
in ASCII text.
and C(union of sets N[subP and N[subQ]) = C(N[subP])
+ C(N[subQ]). Then, from any state U there is a
path P[supU][subk] that contains no transition in
which clients of N[subQ] are stashed prematurely
while clients of N[subp] are stashed.
Proof. In the last transition, it is clear that
clients in NO should not be stashed since the cost
C(N[subQ]) could not be recovered and it is not
justified in a premature setting.
We now prove that the theorem is valid for the
(k - 1) first transitions. For this, we study the
costs over two transitions. Let N[subP] and N[subQ]
be two sets of clients satisfying the conditions
of the theorem. Let U be a state such that, in the
following transition, a set of clients D[subU] must
be stashed, where D[subU] subset or is equal to
N[subP]. Since
Multiple line equation(s) can not be represented
in ASCII text.
then
Multiple line equation(s) can not be represented
in ASCII text.
In other words, N[subQ] does not contain any clients
that must be stashed in a transition following state
U. Thus, to stash subset No on a transition following
State U would be considered premature. Two scenarios
are considered following state U. In the first scenario,
(union of sets N[subP] and N[subQ]) are stashed
on the first transition, and a subset N[subR] is
stashed on the second; the state reached after two
transitions is state V. Thus the cost of reaching
state V is:
Multiple line equation(s) can not be represented
in ASCII text.
By the conditions of the theorem, (8) can be rewritten
as:
Multiple line equation(s) can not be represented
in ASCII text.
In the second scenario, only N[subP] is stashed
on the first transition and union of sets N[subP]
and N[subR] is stashed on the second. The cost of
reaching the resulting state W is given by:
Multiple line equation(s) can not be represented
in ASCII text.
From Lemma 4 we can state that:
Multiple line equation(s) can not be represented
in ASCII text.
State V is reached at a cost greater or equal to
the cost of reaching state W. Now, since the same
clients are stashed according to the two scenarios
and some are stashed later, according to the second
scenario, we have that W sup V. Thus, by Lemma 3,
the cost of the minimum path of any length k from
state W is less than any such path from state V.
Thus, a minimum path from U going through state
W has a lower cost than a minimum path from U through
state V. Since this result is valid for any state
U such that D[subU] subset or is equal to N[subP],
the proof is complete.
The conditions of Theorem 4 are difficult to apply
in practice. However, for some states, called "ageable"
states, these conditions are easily identified.
Definition. A state U = (u[subi]) is ageable if
u[subi] < t[subi] - 1, universal quantifieri
is an element of D.
Corollary 1. For any state U and any length k,
there is a minimum path P[supU][subk] such that
a zero cost transition follows any ageable state
in the path.
Proof. This corollary corresponds to a limiting
case of Theorem 4 in which
Multiple line equation(s) can not be represented
in ASCII text.
For such a set C(union of sets N[subP] and N[subQ])
= C(N[subP]) + C(N[subQ]) = C(N[subQ]). Therefore,
the conditions of the theorem are always satisfied.
According to the theorem, no premature stashing
is carried out on set N[subQ]. It follows that if
a state is ageable, the only possible transition
left to follow that state is one in which all clients
are left to age at no cost.
The previous corollary is interesting since ageable
states are easy to identify. Since for a state to
be ageable the age of each client copy has to be
between 0 and t[subi] - 2, universal quantifieri
is an element of D, the total number of ageable
states N[subAS] is given by:
Multiple line equation(s) can not be represented
in ASCII text.
As soon as one client presents a maximum lifetime
of 1, there can be no ageable states and reductions
are not possible. However, when ageable states are
possible, the total number of transitions that can
be eliminated from the state transition graph is
given by:
Multiple line equation(s) can not be represented
in ASCII text.
Expression (13) can be explained as follows. Any
stashing tree can be used from any of the ageable
states. Every stashing tree implies a different
transition. The number of stashing trees is given
by (2[sup|D|] - 1). Thus the number of transitions
to be eliminated is the product of the number of
stashing trees by the number of ageable states.
Preserving a Minimum Mean Cycle
The steady-state solution approach proposed in
this paper will be based on a search for a minimum
mean cycle. In this section we show that at least
one minimum mean cycle is preserved after reductions.
The first result is contained in the following lemma.
Lemma 5. Let U be a state belonging to a minimum
mean cycle l[sub1] of length l[sub1] and cost c[sub1].
Then there is at least one integer value w[sup*]
such that P[supU][subw*], the minimum path of length
w[sup*] starting at state U,contains a minimum mean
cycle.
Proof. We base the proof of this lemma on the construction
of two paths of equal length w[sup*] both starting
at state U. The first path, denoted by p[subA],
will not include the minimum mean cycle, whereas
the second path, p[subB], will include it. Our aim
is to prove that the cost of p[subB] is inferior
to the cost of p[subA].
We start the construction of p[subA] at state U
and we increase, little by little, the path length.
Since the graph is finite, there is a finite number
of elementary cycles. Thus, if in the construction
of p[subA] the length is long enough, a suboptimal
elementary cycle must be repeated.
Let w[sup*] be the path length of p[subA] so that
a cycle of length l[sub2] has been repeated l[sub1]
times. We call this cycle l[sub2] and we assume
that its mean cost is c[sub2]. Note that the repetitions
of l[sub2] are not necessarily consecutive.
Let l[sub1] denote the minimum mean cycle; its
cost is denoted by c[sub1]. We now attempt to construct
a path p[subB] of length w[sup*] rising l[sub1]
as follows. First, l[sub1] is repeated l[sub2] times,
at which point we are back at state U. Next, we
add the subpath that results from subtracting from
p[subA] the l[sub1] repetitions of cycle l[sub2].
Note that now p[subA] and p[subB] are both of length
w[sup*].
The cost of the second path is:
Multiple line equation(s) can not be represented
in ASCII text.
By definition of the minimum mean cycle, c[sub1]
< c[sub2], it follows that l(P[subB]) < l(P[subA]).
Theorem 5. The reduced state transition graph contains
at least one of the minimum mean cycles of the original
state transition graph.
Proof. The reductions proposed preserve at least
a minimum path P[supU][subk], for all k and U. Then
the reductions will preserve at least one path P[supU][subk]
for k and U as defined in Lemma 5. By this lemma,
this path must contain a minimum mean cycle, which
completes the proof.
