臺灣博碩士論文加值系統

多播在很多應用上都是不可或缺的。本論文的主旨是探討在以超立方體為
基本架構的情況之下，如何減少多播所需得通訊流量。Switching的技術
有很多種，例如：store-and-forward，circuit switching， virtual
cut-through 和 wormhole routing。依據不同的switching技術與需求目
的，多播可分類為the Steiner tree problem，the multicast tree
problem，the multicast path problem和the multicast cycle problem
。在這篇論文中，我們提出三個啟發性的演算法來解決這四個問題中的前
三個。我們解決the Steiner tree problem的演算法是集中式的，解決
the multicast tree problem的演算法是混合式的，而解決the
multicast path problem的演算法是分散式的。依據摸擬的方法與先前的
結果比較，我們的演算法通常只需較少的通訊流量。

Multicast is highly demanded in many applications. Our efforts
in this thesis are to reduce the communication traffic of
multicast in hypercube multiprocessors. There are various
switching technologies, such as store-and-forward, circuit
switching, virtual cut-through and wormhole routing. Depending
on different switching technologies and evaluation criteria,
the multicast communication problem has been formulated as four
different graph theoretical problems, namely the Steiner tree
problem, the multicast tree problem, the multicast path problem
and the multicast cycle problem. In this thesis, we propose
three heuristic algorithms for the first three of the four
problems. Our multicast path algorithm is distributed, our
Steiner tree algorithm is centralized and our multicast tree
algorithm is hybrid. Compared with the previous results by
simulation, each of our heuristic algorithm improves the
communication traffic in the corresponding problem model.