Design and Analysis of Algorithms for Multicast Networks

组播网络算法设计与分析

• 批准号: 0430709
• 负责人: Panos Pardalos
• 金额: --
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430709&HistoricalAwards=false
• 关键词: Design; Analysis; Algorithms; Multicast; Networks

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

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