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.