Virtual Topologies for Multiparty Communication

该建议寻求通过应用图论以及并行和分布式计算领域的模型和方法来改善互联网上的多方通信。多方通信是指一组参与者之间的任何类型的信息交换，包括会议、广告、电子投票、远程监控和元计算。多播，或一对多通信，受到网络协议设计者的最大关注，并已在因特网的一个子集上实现，称为mbone。组播的普遍部署仍然存在一些障碍，如高成本和缺乏健壮性。此外，一些多方应用不能运行，或者运行效率较低，因为仿真组播与它们的通信方式不匹配。例如，大规模的电子投票可以使用多对一网络服务，投票结果在发送到中央报告服务的过程中部分制表。图论以及并行和分布式计算领域的研究已经解决了许多这样的问题，尽管环境与互联网有很大的不同。将这些结果应用于互联网协议的关键是使用将理论上的子结构映射到物理网络上的虚拟拓扑。与MBONE一样，虚拟拓扑中的链路可以由一些物理链路和一些通过封装隧道实现的虚拟链路组成，该研究首先解决了现有组播路由协议的局限性。研究人员建议研究将扳手作为密集多播组的虚拟拓扑的使用，从而提高该领域中使用的周期性编码的效率。对于人口稀少的组，我们提出将并行计算中的超立方体消息传递算法应用于设计一个更高效、更容错的组播协议。然后，研究人员计划将用于多播虚拟拓扑的技术应用于其他多方通信范例。研究人员已经确定了减少(多对一)、子播(一对多)和多源多播(少对多)的有前途的研究方向。该项目将分三个主要阶段进行：分析、方案设计和评估。分析阶段旨在识别适合多方通信协议的虚拟拓扑。该分析将包括所使用的虚拟拓扑的形式模型的定义、适当度量的定义和拓扑的随机样本的统计评估，以及相关精确和近似优化问题的复杂性状况的讨论。协议设计阶段将建立在我们的分析的基础上，将虚拟拓扑作为通信协议的基础。我们的重点将放在可行和实用的协议实现上，并将基于对所提出的图结构的静态特性的仿真研究。对新协议的评估将利用动态模拟来查看流量容量、延迟和容错恢复。最终，开发的协议将在先前支持NSF的网络试验台上实现和评估。这项工作的主要贡献将是一种将虚拟拓扑应用于Internet协议设计的方法，这些拓扑的形式化模型，以及用于组播路由、简化和其他通信范例的新协议。我们工作的进一步成果将包括用于模拟的拓扑库、动态群组成员关系和群组分布的建模方法、以及评估虚拟拓扑和协议的容错性能的技术。对教育的贡献将包括对研究生和本科生进行网络理论和工程方面的培训，以及开发和传播多方通信协议设计和评估的课程材料。

This proposal seeks to improve multiparty communication on the Internet by applying modelsand methodology from the fields of graph theory and parallel and distributed computing. Multipartycommunication refers to any type of information exchange among a group of participants, includingconferences, advertising, electronic voting, remote monitoring, and meta-computing.Multicast, or one-to-many communication, has received the most attention from network proto-col designers and has been implemented on a subset of the Internet known as the MBone. Severalobstacles to the universal deployment of multicast remain, such as high cost and lack of robustness.Moreover, some multiparty applications are not able to operate, or operate less efficiently, becausemulticast is a poor match for their style of communication. Large-scale electronic voting, for exam-ple, could use a many-to-one network service, with balloting results partially tabulated on the wayto a central reporting service. Research from the fields of graph theory and parallel and distributed computing has solved manyof these problems, albeit for environments that differ greatly from that of the Internet. The key toapplying these results to Internet protocols is the use of a virtual topology that maps a theoreticalsubstructure onto the physical network. As with the MBone, the links in the virtual topology couldconsist of some physical links and some virtual links implemented by encapsulation tunnels.The proposed research first addresses limitations in current multicast routing protocols. The researcherspropose to investigate the use of spanners as a virtual topology for densely-populated multicastgroups, thus improving the efficiency of the periodic ooding used in this domain. For sparsely-populated groups, we propose to apply hypercube message passing algorithms used in parallelcomputation to the design of a more efficient and fault-tolerant multicast protocol. The researchers then planto apply the techniques used for multicast virtual topologies to other multiparty communicationparadigms. The researchers have identified promising research directions for reduction (many-to-one), subcast (one-to-some), and multi-source multicast (few-to-many). The project will progress in three main stages: analysis, protocol design and evaluation. Theanalysis stage is intended to identify virtual topologies that are good candidates for multiparty com-munication protocols. The analysis will include definition of formal models of the virtual topologiesused, definition of appropriate metrics and statistical evaluation of random samples of the topologies,and discussion of complexity status of the relevant exact and approximate optimization problems.The protocol design stage will build on our analysis by using virtual topologies as the basis forcommunication protocols. Our emphasis will be on protocols that are feasible and practical toimplement and will be based on simulation studies of the static properties of proposed graph struc-tures. Evaluation of the new protocols will utilize dynamic simulation to look at traffic capacities,delay, and fault tolerance recovery. Eventually, the developed protocols will be implemented andevaluated on a network testbed built with prior NSF support. The major contributions of this work will be a methodology for applying virtual topologies toInternet protocol design, formal models for these topologies, and new protocols for multicast rout-ing, reduction, and other communication paradigms. Further outcomes of our work will includea database of topologies used in our simulations, methods for modeling dynamic group member-ship and group distribution, and techniques for evaluation of fault tolerance properties of virtualtopologies and protocols. The contributions to education will consist of training of graduate andundergraduate students in network theory and engineering, and development and dissemination ofcurriculum materials for the design and evaluation of multiparty communication protocols.