一种新型的可重排多播网络  

A New Rearrangeable Multi-stage Interconnection Network for Multicast

作　　者：顾乃杰[1] 潘伟[1] 李栋[1] 刘刚[1] 陈静[1] 

机构地区：[1]中国科学技术大学计算机科学技术系,安徽合肥230027

出　　处：《小型微型计算机系统》2003年第2期179-183,共5页Journal of Chinese Computer Systems

摘　　要：在并行分布式系统中 ,多播操作 (包括一对多播送和多源点多播 )是一种常见的操作 .关于多播操作 (尤其是多源点多播 )的研究是一个有一定难度 ,但又具有重要应用价值的问题 ,也是目前多级互连网络研究领域中的一个热门课题 .已有的关于多播的成果大多只针对现有的多级网络〔1〕 ,并且一般只能实现单个多播〔2〕 .Yang在〔3〕中针对多源点多播的并发 ,提出了一种新的多播网络 ,硬件复杂度为 O( N log2 N ) .本文提出了一种基于 Omega网的多播网络 ( 5 - Omega网 ) ,通过重排各级开关的状态 ,可以并发的实现任意的多源点多播 ,所需开关元件总数为 52 N log N .与 Yang提出的多播网络相比 ,硬件代价小得多 .同时 ,5 - Om ega网上的多播路由时间复杂度能达到 O( N log N) ,在相关的成果中 〔1〕也算是最优的 .并且由于 Omega网的结构较为简单 ,这种网的硬件集成也非常容易 ,因此更具有实用价值 .在这种网络的构造基础上 ,还提出了一种新的多播网络模型 。Multicast is an important operation in parallel and distributed systems. Researches on the multicast, especially multiple multicast, for the multistage interconnection networks (MINs) is a very difficult problem with great significance. But most of current relative studies merely focus on the previous MINs 〔1〕 and usually involve the single multicast operation only 〔2〕. For multiple multicast, Yang 〔3〕 first proposed a new multicast network using O(Nlog 2N) switches. In this paper, we propose another new multicast network (5-Omega network) based on Omega network. It uses 5/2·Nlog 2N switches. This network cost is much smaller than Yang's network. And 5-Omega network is very easy to be integrated because of the simpleness of Omega network. The routing time complexity for multiple multicast on this network is O(Nlog 2N). Finally based on the structure of 5-Omega network, we propose a new method to constitute multicast network in the future.

关 键 词：可重排多播网络 Omega网 5-Omega网 计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]