Online Algorithms for Selective Multicast, Maximal Dense Trees, and Related Problems

这项研究的本质是一个系统的分类的变种的组播问题，目前自己在各种网络和分布式系统的应用程序，以及算法解决这些问题的精神“竞争分析”。尽管在这个项目中进行的研究是理论性的，但开发的算法可能具有实用价值。 网络界也在非常积极地研究所处理的问题。 这种算法的努力实际上可能是理论和网络社区之间的桥梁，因为网络社区的研究人员正在寻求解决方案，以解决互联网及其应用规模不断增长所带来的可怕问题。从算法的角度来看，这是在这个建议中采取的观点，多播问题可以定义如下。 各种网络用户发出联机请求，以连接到某些多播源。 网络要么连接该请求，要么拒绝它（接纳控制决策）。 如果连接了请求，则建立具有足够剩余带宽的路径，该路径从请求用户开始，并在源或先前连接到同一源的用户之一处结束（路由选择决策）。 这些准入控制和路由选择决策的目标是在网络容量约束下最大化连接的用户总数。 也就是说，通过任何边到不同源的连接的数量不应超过该边的容量。在这项研究中的创新是在开发一个统一的框架，同时捕获接纳控制和路由选择的决定，在其充分的一般性。这个框架可以概括为包括诸如定价政策、网络设计综合等问题。

The essence of this research is a systematic classification of the variants of the multicast problems that present themselves in various networking and distributed systems applications, as well as algorithmic solutions to these problems in the spirit of "competitive analysis". Even though the research pursued in this project is theoretical in nature, the algorithms developed may be of practical value. The issues addressed are also being very actively studied by the networking community. This algorithmic effort may in fact bridge between the Theory and Networking communities, since the researchers in the Networking community are seeking solutions to dire problems created by the growing scale of the Internet and its applications. From the algorithmic point of view, which is the point of view taken in this proposal, the Multicast Problem can be defined as follows. Various network users issue online requests for a connection to certain multicast sources. The network either connects this request or rejects it (admission control decision). If a request is connected, a path with sufficient residual bandwidth is established starting at the requesting user and ending either at the source or at one of the users previously connected to the same source (route selection decision). The goal of these admission control and route selection decisions is to maximize the total number of users connected subject to the network capacity constraints. Namely, the number of connections to different sources passing through any edge should not exceed the capacity of that edge. The innovation in this research is in developing a unifying framework that simultaneously captures admission control and route selection decisions in their full generality. This framework can be generalized to include issues such as pricing policies, network design & synthesis, etc.