Virtual Topologies for Multiparty Communication

点击翻译按钮获取中文摘要

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.