Design and Analysis of Algorithms for Multicast Networks

多播网络是近几年提出的一种新的信息路由和共享技术。这项新技术在不同领域的应用越来越多，从金融数据分发到视频会议、软件自动更新和群件，在多播网络中，目标是通过单一的发送操作将信息从一个源发送到多个用户。这种方法可以节省带宽，因为数据可以跨网络链路共享。组播网络应用常常需要求解复杂的组合优化问题。这些问题中的大多数都是NP难的，这使得它们不太可能在多项式时间内精确地得到解决。因此，必须开发专门的算法，为实践中发现的实例提供合理的良好解决方案。这些问题的内在复杂性一直是组播服务广泛应用的技术障碍，我们建议为组播网络领域中一些最重要的组合问题设计和研究算法。该领域中的问题之一要求确定多播组中的包要遵循的最佳路由。这就是所谓的组播路由问题(MRP)。近年来，人们提出了大量的启发式算法来求解网络工程师感兴趣的MRP问题，但这些启发式算法大多不能保证最优性，而且往往不能找到问题的全局最优解。第二个具有重要实际意义的问题是，当考虑网络链路中的容量时，寻找发送多播数据所需的最小高速缓存节点数。这也被称为流缓存放置问题(SCPP)。流缓存放置问题(SCPP)是最近才被研究的问题，它为开发新的组播系统提供了许多经济机会。本项目的目的是研究这些问题以及组播路由中出现的相关问题。我们的目标是找到实用的方法来有效地实现与组播应用相关的技术。解决这些问题的快速算法的发展是实现多播系统全面实现的重要一步。从理论上看，组播问题是网络领域中最难解决的问题之一。之所以会出现这种情况，是因为这些问题涉及大量节点，以一种非常复杂的方式相互作用，从而构建解决方案。例如，这一领域出现的新概念是各种源节点和目的节点的相互作用，以实现网络结构中的共同目标。我们在组播网络方面的知识将应用于网络算法研究的其他领域。为解决上述问题而提出的技术将涉及数学规划、近似算法、组合优化的亚启发式算法、大规模计算以及并行和分布式计算。这些技术是PI和他的研究小组的专长之一。在本项目的背景下开发的技术将对组播网络系统的工业实践产生广泛的影响。对与这类应用相关的算法问题的深入理解将促进更好的协议、新的路由实现和改进的终端用户软件的开发。除此之外，这一领域的理论进步将在其他网络问题上得到自然的应用，例如路线和运输系统。

AbtractMulticast networks have been proposed in the last years as a new technique for information routingand sharing. This new technology has an increasing number of applications in diverse fields, rangingfrom 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 asingle send operation. This approach allows one to save bandwidth, since data can be shared acrossnetwork links. Multicast network applications often require the solution of diffcult combinatorialoptimization problems. Most of these problems are NP-hard, which makes them very unlikely tobe solved exactly in polynomial time. Therefore, specialized algorithms must be developed thatgive reasonable good solutions for the instances found in practice. The intrinsic complexity of theseproblems 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 combinatorialproblems occurring in the area of multicast networks. One of the problems in this area asks forthe determination of an optimum route to be followed by packages in a multicast group. Thisis known as the multicast routing problem (MRP). A large number of heuristic algorithms havebeing 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 ableto find the global optimum for the problem. A second problem of great practical importance is thatof finding the minimum number of cache nodes required to send multicast data when capacities areconsidered 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 thedevelopment 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 technologiesinvolved with multicast applications. The development of fast algorithms for solving these problemsrepresents an important step in allowing full scale implementations of multicast systems.Intellectual Merit of the Proposed Activities. Multicast problems are among the mostdifficult in the area of networks from the theoretical point of view. This happens since such problemsencompass the construction of solutions involving a large number of nodes, interacting in a verycomplicated way. New concepts appearing in this area are, for example, the interplay of diversesource and destination nodes to achieve a common objective in a network structure. Our knowledgein 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 scalecomputing, and parallel and distributed computing. These techniques are among the specialities ofthe PI and his research group.Broader Impact. The techniques developed in the context of this project will have broad impactin industrial practices for multicast network systems. A deep understanding of the algorithmicissues 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 willhave natural applications in other network problems, such as routing and transportation systems.1