Virtual Topologies for Multiparty Communication

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

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.