混合式網路下協議問題之研究

Abstract

近年來由於無線通訊以及行動計算的蓬勃發展使得現今的網路型態走向了混合式的網路（包含了有線網路及無線網路）。因此混合式網路的可靠度以及容錯問題成為非常重要的課題。 為了提供可靠的計算環境，我們需要一個機制讓參與運作的處理器即使在發生錯誤或攻擊時仍能夠達成協議。 因此拜占庭協議問題以及合議問題成為許多學者們關注的焦點。 然而，過往的拜占庭協議問題以及合議問題的研究大都是針對在有線的網路之上。由於有線網路的實體拓樸為靜態的，使得過往針對這些固定式網路所提出的協定無法運作在混合式網路之中，其主要原因在於混合式網路之實體拓樸為動態的。 在本論文中，我們將探討拜占庭協議問題以及合議問題於混合式網路。為了因應混合式網路的特性（行動式處理器的運算能力通常較固定式處理器要來的弱）以及減少為了達成協議所需要的訊息交換次數，因此在我們所設計的協定之中導入了階層式的概念，將大部分的通訊工作以及運算工作交由伺服器來處理，如此一來將可以大幅降低行動式處理器的負擔。以效能的觀點來看，本論文中所提出的協定使用了最少的訊息交換次數並且可以容忍最大數量的損毀處理器。此外，由於純粹的有線網路以及純粹的無線網路都是混合式網路的特例，因此我們也將討論協議問題於這兩種網路之上。 為了提供更高可靠度的計算環境，我們還必須偵測/定位出網路中的損毀處理器。 因此，我們也將提出一個新的錯誤診斷協定來偵測/定位出損毀的處理器於混合式網路之中。a 在應用方面，近年來檔案分享已經成為點對點網路上最受歡迎的一項服務，而許多的點對點網路都是架構在有線及無線的混合式網路之上。這也使得檔案一致性的問題成為一項非常重要的課題。 因為惡質性損毀的攻擊者可能會隨意變更檔案的內容，並且將這些更改過的檔案傳送給其他的處理器。如此一來將使網路上充斥著不一致的檔案，造成浪費許多的資源，例如：頻寬、儲存空間以及傳輸時間。 因此確認所擁有的檔案是否為正確是相當重要的。 在本研究當中我們將使用所提出的協定來解決檔案一致性的問題於點對點網路之中。

Since wireless communication and mobile computing are becoming more and more ubiquitous, most network environments today are combined wired and wireless. The reliability and fault tolerance of the combined wired/wireless network has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of processors to reach a common agreement, even in the presence of faulty processors, is needed. Therefore, the Byzantine Agreement (BA) problem and Consensus problem have drawn attention of more researchers. Traditionally, most of the BA problem and Consensus problem were focused on wired networks. We know that the physical topology of a wired network is static, but the physical topology of a combined wired/wireless network is dynamic. Thus, previous BA and Consensus protocols for static network are not applicable in a combined wired/wireless network. In this dissertation, we visited the BA problem and Consensus problem in combined wired/wireless network. In order to meet the characteristics of combine wired/wireless networks (the limited resources have made the computation ability of mobile processors often weaker than that of stationary processors) and reduce the number of rounds of message exchange required, most of the communications and computation overhead must be fulfilled within by the servers. Therefore, we introduce a hierarchical concept in our system model. Only servers need to exchange messages and compute the common value. From the performance perspective, the proposed protocols use the minimum number of message exchanges and can tolerate the maximum number of faulty processors allowed in the networks. AS a matter of fact, pure wired networks and pure wireless networks are all special case of the combined wired/wireless networks. We also discuss the BA and Consensus problems in pure wired network and pure wireless network. In a highly reliable fault-tolerant environment, to reach a common agreement is not enough. It is also necessary to detect/locate the faulty components in the network. Therefore, we also propose a new protocol to solve the Fault Diagnosis Agreement (FDA) problem in combined wired/wireless networks. In the usage, the file-sharing application has been the most popular application in Peer-to-Peer (P2P) systems. Many P2P networks are overlay networks because they run on top of the combined wired/wireless network. Hence, the Consensus problem of file-sharing has become an important topic. As malicious attackers may modify files arbitrarily and spread inconsistent files to other processors in the P2P network, inconsistent files will not only spread in P2P networks but also waste resources, such as bandwidth, space of storage and transmission time. Hence, how to make fault-free processors ensure that the files they hold are correct is an import topic. In this thesis, we give an application of Consensus protocol to ensure the file consistency of file-sharing in P2P systems.