6. CONCLUSIONS AND EXTENSIONS OF THE WORK

In the information age, the management of redundant information is becoming a major issue. The "stashing" technique can be seen as a useful tool for managing redundant information. However, the mathematical problem implicit in such a technique is the Steiner tree problem, which is very hard to solve.

In this paper we have explored a solution approach to the problem based on a state transition graph model. Part of the success of the implementation was based on the exploitation of some theoretical properties that permit considerable reduction in the number of transitions of the state transition graph. Also, we adapted the Hakimi algorithm for finding Steiner trees to our problem in such a way that the procedure to find all stashing trees involves the same complexity as the original Steiner tree algorithm. The problem, however, is still very hard to tackle.

With respect to modeling extensions of the problem, we underline that in this work we have assumed that the copies are sent integrally. In some applications (for example, large databases), it would be more worthwhile to send that part of the file that has been modified. In that case, transmission costs would increase with time, since the difference between the file and the stashed copies would also augment with time. Another example of costs that would vary over time are those related to the residual capacity in the network. Future studies should then include transmission costs that vary over time.

A particular application mentioned in the introduction was multicast broadband services. A large number of unsolved problems relate to such services. If infinite capacity is considered, then the DPSCP is directly transformed into a multicast problem. However, in the most general case the bandwith available for the connection will be restricted by resource sharing among different connections. In such a case, there will be a clear linking between commodities and the complexity of the model and resolution approach increases enormously. A first extension of our work aimed at solving such problems consists of adding capacity constraints and capacity requirements to the connection.

We believe that given the enormous flexibility provided to information-seeking users in future computer networks, Steiner tree problems that vary over time will become increasingly common. The approach presented in this paper opens the door to a new way of treating these difficult problems.