以最佳資訊分散方法用於具安全性及容錯性之平行通訊

Abstract

隨著電腦網路和分散式系統之快速發展，具高速、可靠性及安全性之通訊 需求愈來愈增。資訊分散方法 ( Information Dispersal Scheme )可以 用來加速在低傳輸速率網路中之通訊以及容忍傳輸路徑之誤失 ( failure )。在一個 (m, n)資訊分散方法 ( IDS ) 中，傳送節點 ( sender node ) 將一個訊息 ( message ) 分成 n 個小塊 ( pieces )， 使得接收節點 ( receiver node ) 從不同路徑接收到任何 m 個小塊，就 足以重構此訊息。這些小塊在平行通訊網路中可以被平行傳輸。 (m, n) 資訊分散方法可以用來容忍 ( tolerate ) n-m 條傳輸路徑之誤失。在本 論文中，我們將研究使用 (m, n) 資訊分散方法來達成具安全性及容錯性 之平行通訊。使用 (m, n) 資訊分散方法來達成具容錯性平行通訊之可靠 度 ( reliability )主要決定於三個重要因素：資訊分散度 (n)，資訊擴 張度 (n/m)，以及每條傳輸路徑之成功機率。根據不同形態之通訊網路， 每條傳輸路徑之成功機率可能相同或者不同。根據此兩種不同的情況，我 們提出了兩個演算法來動態地決定最佳的 (m, n) 資訊分散方法使具有最 高的可靠度。為了提供具容錯性之平行通訊一個整體的環境，我們提出了 一個控制合法通訊之存取機制。此機制有只需儲存少量資訊之優點。我們 也提出了(m, n, r) 可靠性資訊分散方法 ( RIDS )。此方法可以用來容 忍 n-m 條傳輸路徑之誤失，並且對於每一傳輸中的小塊，可以更正 r 個 symbol-errors。可靠性資訊分散方法將錯誤控制 ( error control )及容錯能力 (fault tolerance ) 合而為一，以降低兩者之 overhead。 最後，我們設計了具安全性之 (m, n, r) 可靠性資訊分散方法( SRIDS )。此方法可以達成通訊安全 ( communication security ) 之目的，並 且可以容忍 n-m 條傳輸路徑之誤失，以及對於每一傳輸中的小塊，可以 更正 r 個 symbol-errors。具安全性可靠性資訊分散方法則是將通訊安 全、錯誤控制及容錯能力合而為一，以降低三者之 overhead 。以上這些 被提出的方法對於具安全性及容錯性之平行通訊，提供了一個強而有力的 基礎。 In an (m, n) Information Dispersal Scheme (IDS), the sender node transforms a message M into n pieces Si, such that any m pices collected by the receiver node over vertex-disjoint paths suffice for reconstructing M. The (m,n)IDS can be used to tolerate up to n-m paths failures. In this dissertation, we study the use of the (m, n)IDS to support secure and fault tolerant parallel communic- ation. The reliability of the (m, n) IDS supporting fault tolerant parallel communication is primarily determined by three important factors, that is, information dispersal degree (n), information expansion ratio (n/m), and the probability of successful transmi- ssion over each path. Depending on the types of communication networks, the success probability of each path may or may not be the same. We propose two algorithms that dynamically determines the optimal (m, n)IDS with highest reliability for the two cases that the path success probabilities are equal and unequal, respectively. To support an integrated environment for the fault tolerant parallel communication, we propose an access control mechanism for legal communication. The proposed mechanism has the advantage of storing less information. We also propose the (m, n, r) Reliable IDS which has the capability of tolerating n-m paths failing and correcting r symbol-errors for each piece encoded into symbols list. RIDS provides both error control and fault tolerance in one process to reduce the overhead of both. Finally, we design the Secure (m, n, r) Reliable IDS (SRIDS) which has the capability of providing communication security for the message M, tolerating n-m paths failing, and correcting r symbol errors for each piece encoded into symbols list. The scheme is able to provide communication security, fault tolerance , and error control in one process to reduce the overhead of these three. The proposed schemes provide a strong basis for secure, fault-tolerant parallel communication.