四個分散式資源分配演法的設計與評估

Abstract

考慮在一分散式網路上，有大量的同等資源(identical resource)散布其上。我們 欲將這些資源配置給從外界進入的請求(request) 。在1986年，Lynch 等人提出一 個解決此一問題的分散式演算法，他們的理論結果引起我們的興趣。但是，他們假 設網路為一樹狀形態，所有樹葉到樹根的距離相等，並且資源和請求也只有在樹葉 的位置出現。本論文中，我們考慮一般性網路，放寬這些限制，直接引用他們的演 算法，並命名為TREE。 在某些系統中，被配置的資源需被送回請求發生的地方，而在某些系統，這些資源 立即被消耗。不幸的是，TREE演算法只適用於前者，因此，我們參考TREE演算法的 特質，提出NEWTREE 演算法，用於後者。此外，我們提出 NBF，SR，HP等三個分散 式演算法，來和TREE及NEWTREE 作比較。 模擬結果顯示，在評估最差反應時間時，HP表現出它的穩定性。除了在資源非常集 中的情況下，SR表現得比TREE和NEWTREE 好以外，TREE和NEWTREE 的表現均最好。 NBF 的表現雖然較差，但它具有簡單、容易實行、對網路變化的適應力強等優點。 此外，兩種不同的擴張樹，最小加權擴張樹和最小半徑擴張樹，被用來評估不同的 樹形架構對TREE和NEWTREE 影響。結果顯示，以最小半徑擴張樹為基礎，效率較高 。