計算機網絡自學筆記:P2P

1:P2P 文件分發的可擴展性

P2P 體系結構中,其中每個 peer 節點都能夠幫助服務器來分發文件。也就是說,當一 個 peer 節點接收到文件數據時,它可以利用自己的上載能力重新將數據分發給其他 peer 節 點。

計算機網絡自學筆記:P2P

在以上例子中,在分發的開始,只有服務器擁有文件。為了使這些 peer 節點得到該文 件,服務器必須經其接入鏈路至少發送一次該文件。因此,最小分發時間至少是

計算機網絡自學筆記:P2P

顯然,對幹 P2P 體系結構,文件分發是可以自我擴展的,因為 peer 節點除了是下載消

費外還能進行上傳提供服務。隨著 N 的增大,∑ui 也會增大,所以 dP2P 會保持穩定。

2:BitTorrent

BitTorrent 是一種用於文件分發的 P2P 協議。

在一個 Torrent 中,peer 節點彼此下載等長度的文件塊,塊長度通常為 256KB。當一個 peer 節點開始加入一個 Torrent 時,它沒有文件塊。隨著時間的推移,它將累積越來越多的 文件塊。當它下載文件塊時,也為其他 peer 節點上載了多個文件塊。peer 節點一但獲得了 整個文件,它可以(自私地)離開 Torrent,或(大公無私地)留在 Torrent 中並繼續向其他 peer 節點上載文件塊。

當一個 peer 節點 Alice 加入 Torrent 時,追蹤服務器隨機選擇一些 peer 節點,並將這些 peer 節點的 IP 地址發送給 Alice。

Alice 持有這些 peer 節點的列表,試著與該列表上的多個 peer 節點創建並行的 TCP 連接。 這裡稱所有與 Alice 成功地創建 TCP 連接的 peer 節點為“鄰近 peer 節點”。

隨著時間的推移,其中的一些 peer 節點可能離開,而其他 peer 節點可能試著與 Alice 創建 TCP 連接。因此,鄰近 peer 節點將隨著時間而改變。

在任何時刻,每個 peer 節點都擁有來自某文件塊的子集,且不同的 peer 節點具有不同 的文件塊子集。Alice 週期性地(經 TCP 連接)詢問每個鄰近 peer 節點它們所具有的塊列表。 如果 Alice 有 L 個鄰居,那麼她將獲得 L 個塊列表。因此,Alice 將對她當前還沒有的塊發出 請求(仍通過 TCP 連接)。

Alice 使用一種稱為最稀罕優先的策略,其思路是根據她沒有的塊從她的鄰居中確定最 稀罕的塊(最稀罕的塊就是在她的鄰居中拷貝數量最少的那些塊),並優先請求那些最稀罕的 塊。按照此方式,最稀罕的塊更迅速地重新分發,其目標(大致)是均衡每個塊在洪流中的拷 貝數量。

如果多個用戶向她請求文件塊,為了決定她響應哪個請求,BitTorrent 使用了一種對換 算法。其基本思想那些當前能夠以最高的速率供給她數據的鄰居具有較高的優先權。Alice 對於她的每個鄰居都持續地測量她們之間連接的速率,確定以最高速率流入的 4 個鄰居。然 後,她將數據塊發給這 4 個鄰居。每過 10 秒,她重新計算該速率並可能修改這 4 個 peer 節點。更重要的是,每過 30 秒,她要隨機地選擇一個另外的鄰居並向它發送塊。

在 PZP 文件共享中,搭免費車(free-riding)是一個常見的問題,這是指 peer 節點從文件 共享系統中下載文件而不上載文件。BitTorrent 的對換算法有效地消除了這種搭免費車問題。

3:分佈式散列表

分佈式散列表在 P2P 網絡中實現了一個簡單的數據庫。

數據庫只包含 key-value 對例如:鍵可以是社會保險號,值可以是相應的人名;在這種情況

下,鍵一值對的例子如(156-45- 7081 , John ),或者鍵可以是目錄名(例如,電影、唱片和軟 件的名字),值可以是存儲內容的 IP 地址。當用鍵來查詢數據庫,如果存在鍵值對,數據庫 就返回相應的值。

可以為每個 peer 節點分配一個標識符 ID,其中每個標識符是一個(0, 2n-1)範圍內的整數, n取某些固定的值。使用散列函數把每個鍵(如社會保險號)映射為(0, 2n-1)範圍內的一個整數。 散列函數是一種多對一的函數,使兩個不同的輸入可能具有相同的輸出(相同的整數),但是 具有相同輸出的似然性極低。

由於每個 peer 節點具有了一個整數標識符,這時就可以將 key-value 對分配給具有最近 ID 的 peer 節點.,一般最近的 peer 節點是指 key 是最鄰近的 peer 節點的後繼,例如

假設有 8 個 peers: 1,12,13,25,32,40,48,60

如果 key = 53,那麼這個 key-value 對將分配到 60 號 peer 節點

如果 key = 60,那麼這個 key-value 對將分配到 60 號 peer 節點

如果 key = 61,那麼這個 key-value 對將分配到 1 號 peer 節點

環形 DHT

計算機網絡自學筆記:P2P

為了處理規模的問題,將這些 peer 節點組織成環狀,每個 peer 節點僅知道它的直接 successor 和 predecessor。查找某個鍵值對時,在這個環狀網絡中進行時鐘順序查找。

為了加速查找,又建立了 peer 節點之間的 shortcut 連接。

計算機網絡自學筆記:P2P

此時每個 peer 節點保留 predecessor, successor, short cuts 的 IP 地址。例如 peer12 進行 鍵值 53 的查找從原來的 12-13-25-32-40-48-60 需要 7 個消息減少 12-48-60 的 3 個消息。

在 DHT 數據庫中,peers 節點可能加入和離開(churn),但是由於每個 peer 知道兩個後 繼的地址。只要每個 peer 週期性的 ping 兩個後繼以檢測活性,如果直接後繼離開, 那麼選 擇下一後繼為當前直接後繼。


分享到:


相關文章: