Multicast networks have been proposed in the last years as a new technique for information routing and sharing. This new technology has an increasing number of applications in diverse fields, ranging from financial data distribution to video-conferencing, automatic software updates and groupware. In multicast networks, the objective is to send information from a source to multiple users with a single send operation. This approach allows one to save bandwidth, since data can be shared across network links. Multicast network applications often require the solution of diffcult combinatorial optimization problems. Most of these problems are NP-hard, which makes them very unlikely to be solved exactly in polynomial time. Therefore, specialized algorithms must be developed that give reasonable good solutions for the instances found in practice. The intrinsic complexity of these problems has been a technological barrier for the wide deployment of multicast services. We propose to design and study algorithms for some of the most important combinatorial problems occurring in the area of multicast networks. One of the problems in this area asks for the determination of an optimum route to be followed by packages in a multicast group. This is known as the multicast routing problem (MRP). A large number of heuristic algorithms have being proposed in the last years to solve the MRP, which is of great interest for network engineers. However, most of these heuristics do not give any guarantee of optimality and frequently are not able to find the global optimum for the problem. A second problem of great practical importance is that of finding the minimum number of cache nodes required to send multicast data when capacities are considered in the network links. This is also called the streaming cache placement problem (SCPP). The SCPP has been only recently studied, and it presents many opportunities for economy in the development of new multicast systems. The objective of this project is to study these and related problems occurring in multicast routing. Our goal is to find practical methods that can be used to implement efficiently the technologies involved with multicast applications. The development of fast algorithms for solving these problems represents an important step in allowing full scale implementations of multicast systems. Intellectual Merit of the Proposed Activities. Multicast problems are among the most difficult in the area of networks from the theoretical point of view. This happens since such problems encompass the construction of solutions involving a large number of nodes, interacting in a very complicated way. New concepts appearing in this area are, for example, the interplay of diverse source and destination nodes to achieve a common objective in a network structure. Our knowledge in multicast networks will have applications in other areas of network algorithmic research. The techniques proposed to solve the problems discussed above will involve mathematical programming, approximation algorithms, metaheuristics for combinatorial optimization, large scale computing, and parallel and distributed computing. These techniques are among the specialities of the PI and his research group. Broader Impact. The techniques developed in the context of this project will have broad impact in industrial practices for multicast network systems. A deep understanding of the algorithmic issues related to such applications will foster the development of better protocols, new routing implementations and improved end-user software. Beyond this, theoretical advances in this area will have natural applications in other network problems, such as routing and transportation systems. 1
