5. COMPUTATIONAL RESULTS
To test the solution approach, a random problem
generator was created. The generator builds a stashing
network based on the following parameters:
number of intermediate nodes,
number of destination nodes,
vector of maximum lifetime, T,
number of links, |E|,
maximum connectivity degree, d[submax],
bounds on link transmission costs.
Two groups of tests were designed. The aim of the
first group was to determine, with relatively small
examples, the effect of changing different parameters
in the solution. For the second group of tests the
goal was to assess the maximum size of problem that
could be solved by the method. Given the different
requirements for the two groups of procedures, two
different computational platforms were used. For
group I, results were obtained on a sparc 10, whereas
for group II we favored a more powerful machine
(ultrasparc 140).
Group I
For the first group, five series of tests were
designed. In each series, five test problems were
generated. The series characteristics are shown
in Table I, and the test results are given in Table
II. Note that for series 1, 2, 3, and 5 the number
of states in the state transition graph is 180 and
the maximum number of transitions is 2,025. For
series 3 the number of states is 360 while the number
of transitions is 6,075.
The first column in Table II contains the series
number. The second column indicates the test problem
generated. The third, fourth, and fifth columns
provide results on the state graph generation: t[sub1](s)
corresponds to the number of seconds required to
generate the stashing trees for group I; t[sub2](S)
is the time necessary to generate the transitions;
the fifth column corresponds to the number of transitions
actually generated. The sixth column presents the
percentage of transition reduction made possible
by the transition generation procedure.
The stashing problem was solved for the steady
state by finding the minimum mean cycle (MMC) for
each network tested. The Karp algorithm (Karp 1978)
for the minimum mean cycle in a graph was used on
the state transition graphs. The seventh column
of Table II provides the solution time for the minimum
mean cycle; columns eight and nine give the length
of this cycle and its mean cost. Note that these
values are interesting for the system manager as
they provide the number of states and the value
of the optimal solution. In a system with a large
number of states in the optimal solution there is
a higher probability that interruptions and failures
affect the optimal management.
From the results in Table II, it is clear that
solution time is consumed by the search for the
stashing trees. In this table, times are reported
to a precision of one second. These times, which
are listed in the third column, are heavily influenced
by the addition of intermediate computer nodes,
as witnessed by the huge increase (by a factor of
2[sup3]) in solution time between series 1 and series
2. The increase in the number of destination nodes
does not affect stashing tree search time as directly
as does the increase in intermediate nodes. In fact.
only new destination nodes having maximum lifetimes
of more than 1 would substantially affect search
time. Test graphs generated in series 3 have three
more destination nodes than those in series 1. Only
one new destination node, however, has a life span
greater than 1. It can be seen that the stashing
tree search time has roughly tripled.
Note that graphs in series 4 contain twice the
number of links as those of series 1. Consequently,
stashing tree search time has doubled. As expected,
the number of links is not as important a factor
as the number of intermediate or destination nodes.
With respect to the reduction in the number of
transitions, some of the tests present impressive
results. For instance, test 3a shows that it is
possible to reduce the total number of transitions
by up to 63%.
Note that the solution time for the Karp algorithm
to find the minimum mean cycle is extremely fast.
The worst solution time, for a 360-states, 5,106-transitions
network, was four seconds.
Let us now examine the costs of the obtained MMCs.
Results for series 2 show that adding intermediate
nodes increases the cost of the MMC. This can be
explained by the fact that when intermediate nodes
are added, destination nodes become farther away
from the server, thus increasing transmission costs.
Results for series 3 show that costs have increased
with the increase m the number of destination nodes.
Series 4 shows that increasing the number of links
produces a decrease in the cost of the MCC. This
result was expected since more links implies more
possible stashing trees, thus increasing the possibility
of finding lower cost trees. Finally, series 5 shows
that variability in link costs does not have a major
impact on the MCC costs.
Group II
For this group, the size of the networks was progressively
increased, and several random cases were generated.
The values of the components of T were chosen at
random from 1 to 5, the maximum connectivity degree
was 4, and the link costs were again chosen at random
from [8,12].
An example is defined by the triplet (intermediate
nodes, destination nodes, number of arcs). From
the results of group I, it is clear that the most
challenging examples are produced when the number
of intermediate nodes is significant. Thus, to avoid
drowning the reader with too much data, only examples
with more than nine intermediate nodes are portrayed.
Within each example, we have selected the two random
instances that provide the best and the worst resolution
time. Results are compiled in Table III.
From the table, it is evident that there can be
a wide gap in terms of resolution time, even for
the same triplet examples. This is due to the difference
in the number of transitions and states as well
as cost structure that can be generated. As a rule
of thumb, within the same example, the larger the
number of states and transitions, the larger the
resolution time. However, it is clear that, in the
end, given the 2[sup|J|+|D|] complexity of the algorithm,
it is the total number of nodes that really influences
the growth rate, as can be seen by comparing problems
(13,8,30c) and (20,10,35c). The former has many
more states and transitions, yet takes just 35 minutes
compared with 45 hours for the latter.
