1. THE PROBLEM
Let G(N, E) represent the computer network. N corresponds
to the set of vertices, that is, the network computers;
E, the set of edges, represents the communication
links between computers. Each edge has an associated
transmission cost. The computers of the system are
partitioned into three groups: servers that maintain
perfectly updated information, clients that maintain
information on local devices, and intermediate computers
to transmit information from servers to clients.
Intermediate computers simply relay information
but do not necessarily stash it.
As was mentioned in the introduction, information
on clients stashed locally must be updated so that
consistency between the original file and client
copy is assured. To this end, a "predicate,"
that we will call "maximum lifetime,"
is assigned to each stashed client copy. Let D be
the set of clients, and let n be the cardinality
of set D, then T = (t[sub1], t[sub2], ..., t[subn])
is the vector of the maximum lifetime for copies
stashed on every client. This maximum lifetime can
be expressed in terms of elapsed time or in terms
of number of versions of the original file. Figure
1 provides an example of a network with three servers
(s[sub1], s[sub2], and s[sub3]), three clients (d[sub1],
d[sub2], and d[sub3]), and four intermediate nodes.
The maximum lifetime vector is T = (4,6,10), which
means that the first client must be restashed before
four updates have been made to the original file,
the second client before six updates, and the third
client before 10 updates.
The objective of the problem is to find the optimal
stashing policy consistent with the T vector. In
other words, it is to find when, and over which
paths, the copies of the file must be transmitted
from servers to clients so that consistency requirements
are met for all copies. As the problem can be reduced
to an instance of the Steiner tree problem, it was
classified as NP-hard (Sanso and Soumis 1993).
Preprocessing
Before providing details of the mathematical formulation,
we remark that the discrete time space of the problem
is given by PI = {0, tau, 2tau,...}, where TAU is
the greatest common divisor of all the maximum lifetimes.
For instance, in the example shown in Figure 1,
TAU = 2 so that PI = {0, 2, 4, ...}. One preliminary
simplification is to normalize the time space so
that the discrete time unit equals 1. To achieve
this, all time-related information is divided by
TAU, so that the normalized lifetime vector becomes
T' = {t[sub1]/tau, t[sub2]/tau,...,t[subn]/tau}
and the normalized time space is PI' = {0, 1, 2,...}.
The second normalization is related to the number
of servers. In this paper, we treat the problem
of a single commodity, that is, a particular file
that must be stashed and kept consistent with the
information maintained by the server. Therefore,
when several servers are present in the network,
it is assumed that all servers keep the same file.
The case when several commodities can be transmitted
through the network and stashed on clients according
to different predicate requirements is not considered
in this paper. Note, however, that unless there
are specific linking constraints among commodities,
the multicommodity variant is decomposable by commodity.
Our computer model assumes that there is only one
server in the network. Therefore, if more than one
server is present in the system they can be either
"contracted" into a single server or transformed
into intermediate computers linked at zero cost
to a "supra server." When the contraction
causes parallel links to connect the server to other
computers, only the least costly edge will be obtained.
These preprocessing concepts are illustrated in
Figure 2, which presents the network of Figure 1
after normalization. In the figure the new intermediate
nodes resulting from the contraction and transformation
are presented in dashed circles. The balance of
this article assumes that all networks under study
are normalized.
