Multicast Communication in Multicomputer Networks
Multicast Communication in Multicomputer Networks
复制标题
DOI：
10.1109/71.246072
复制
发表时间：
1993-10
期刊：
影响因子：
--
通讯作者：
X. Lin;L. Ni
中科院分区：
文献类型：
--
作者：
X. Lin;L. Ni
有效的消息路由是多计算机性能的关键。多播通信是指将同一消息从一个源节点传递到任意数量的目标节点。虽然多播通信在许多应用中都有很高的需求，但大多数现有的多机并不直接支持该服务；相反，它是由多个一对一或广播通信间接支持的，这会导致更多的网络流量和系统资源的浪费。研究了不同交换技术下组播通信的路由评价准则。多机组播通信是一个图论问题。根据评估标准和交换技术，他们研究了三个最优组播通信问题，相当于寻找以下三个子图：最优组播路径，最优组播周期和最小Steiner树，其中多计算机互连定义了一个主机图。他们证明了所有这些优化问题对于流行的二维网格和超立方体主图都是np完全的。针对这些路由问题，提出了启发式组播算法。>
Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed. >