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