【計算機網路筆記】2.5 Peer-to-Peer File Distribution

Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。

P2P 架構與自我擴充性（Scalability）

複習：什麼是 P2P？

在傳統的主從式架構（Client-Server Architecture）中，伺服器必須承擔所有的上傳工作。

如果要發送一個檔案給 NN 個使用者，伺服器就必須把這個檔案傳送 NN 次，會導致伺服器的頻寬成為巨大的瓶頸。

在 P2P 架構（Peer-to-Peer Architecture）中，每一台參與的電腦被稱為 Peer（對等點）。

Peer 不僅僅是下載檔案，還會將已下載的檔案片段重新上傳給其他的 Peer。

為什麼 P2P 很重要？

這個架構最關鍵的特性叫做自我擴充性（Self-scalability）。

  • 傳統架構的問題：使用者越多，伺服器負擔越重，下載速度越慢。
  • P2P 的優勢：當新的 Peer 加入網路時，雖然帶來了新的下載需求，但它同時也帶來了新的上傳頻寬，因此，系統的總容量隨著使用者增加而自動擴充。

數學模型：為什麼 P2P 更快？

情境設定：要將一個大小為 FF 的檔案，分發給 NN 個 Peer。

  • usu_s ：伺服器的上傳頻寬。
  • uiu_i ：第 ii 個 Peer 的上傳頻寬。
  • did_i ：第 ii 個 Peer 的下載頻寬。
  • dmind_\text{min} ：所有 Peer 中最慢的下載速度。

image

Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 167, Figure 2.22)

主從式架構的傳布時間（ DcsD_\text{cs} ）

註：傳布時間等於 NN 個對等點全部收到一份檔案副本所花費的時間。

在 Client-Server 模式下，傳布時間（Distribution Time）取決於兩個瓶頸：

  1. 伺服器的上傳極限：有 NN 個對等點，則伺服器必須送出 NN 份檔案，總量為 N⋅FN \cdot F 位元，所需時間至少是： $$\frac{N \cdot F}{u_s}$$
  2. 客戶端的下載極限：最慢的客戶端下載完檔案至少需要： $$\frac{F}{d_\text{min}}$$

因此，傳布時間（Distribution Time）公式為： $$D_\text{cs} \ge max{\frac{N \cdot F}{u_s} , \frac{F}{d_\text{min}}}$$

當 NN（使用者數量）變得非常大時，主要瓶頸會卡在 N⋅Fus\frac{N \cdot F}{u_s} ，表示時間隨著人數線性增長，這是非常沒有效率的。

P2P 架構的傳布時間（ DP2PD_\text{P2P} ）

在 P2P 模式下，瓶頸比較複雜，但來看三個限制因素：

  1. 伺服器的起始上傳：伺服器至少要將檔案完整上傳一次到網路中，時間至少是 $$\frac{F}{u_s}$$
  2. 客戶端的下載極限：同上，最慢的 Peer 仍需 $$\frac{F}{d_\text{min}}$$
  3. 系統總上傳能力：系統的總上傳頻寬等於「伺服器頻寬」加上「所有 Peer 的頻寬總和」： $$u_\text{total} = u_s + \sum u_i$$ 系統必須傳布 N⋅FN \cdot F 的資料量，而這些資料是由大家一起分擔傳送，因此最終得到： $$\frac{N \cdot F}{u_s + u_1 + \cdots + u_N}$$

因此，傳布時間公式為：$$D_\text{P2P} \ge max{\frac{F}{u_s},\frac{F}{d_\text{min}},\frac{N \cdot F}{u_s + \sum^{N}_{i=1}u_i}}$$

注意 min{}min\{\} 當中第三項的分母。

當 NN 增加時，分子的需求（ N⋅FN \cdot F ）增加，但分母的供給（ ∑ui\sum u_i ）也跟著增加。

這使得 P2P 的傳布時間理論上不會隨著人數暴增，而是趨於平緩。

主從式架構 vs P2P 架構的傳布時間圖

如下圖 Figure 2.23，可見主從式架構（Client-Server）是呈現線性成長，而 P2P 則是像對數函數一般趨於平緩。

image

Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 170, Figure 2.23)

BitTorrent（位元奔流）

理論結束後，來看網際網路上最著名的 P2P 實作：BitTorrent，一種熱門的檔案傳布 P2P 協定。

術語解析

  1. Torrent（奔流 / 種子）：所有參與傳布特定檔案的對等點（Peer）。
  2. Tracker（追蹤伺服器）：一個負責追蹤當前哪些對等點（Peer）在奔流中的基礎設施節點。
  3. Chunks（檔案片段 / 區塊）：檔案被切分成許多固定大小的小塊（通常是 256 KB）。

運作流程

  1. 加入奔流（Torrent）：
    • 當一個新的對等點（稱其為 Alice）加入時，他會聯繫 Tracker（追蹤伺服器）。
    • Tracker 會隨機選取一組正在參與的對等點（例如 50 個）的 IP 地址給 Alice。
    • 接下來 Alice 會嘗試與這些對等點建立 TCP 連線，這些人就成為他的相鄰對等點（Neighboring Peers）。
  2. 接下來要決定下載什麼？Alice 手上什麼檔案片段都沒有，他該先請求哪一塊？
    • 策略：Alice 會詢問鄰居（相鄰對等點）們擁有哪些檔案片段，然後找出最稀有（在鄰居中副本最少）的檔案片段優先下載。
    • 原因：這樣做可以讓稀有的檔案片段迅速在網路中擴散，避免如果擁有稀有檔案片段的對等點離開，該檔案片段就絕種了。
    • 這種策略稱之為最稀有者優先（rarest first）
  3. 然後決定上傳給誰？Alice 的頻寬有限，他這一個對等點不能服務給所有人，他該把資料傳給誰？BitTorrent 設計了一套鼓勵性機制：
    1. 無阻的（Unchoked）：
      • Alice 會持續測量鄰居傳資料給他的速度。
      • 他會選出 4 個傳給他最快的人，作為回報，他也將資料上傳給這 4 人。
      • 該名單每 10 秒更新一次。
      • 該機制稱之為以德報德（tit-for-tat），你對我好，我就對你好。
    2. 樂觀無阻的（Optimistically Unchoked）：
      • 每 30 秒，Alice 會隨機選擇 1 個 鄰居（不管對方之前有沒有傳資料給他）傳送資料。
      • 目的：為了尋找潛在更好的交易夥伴，如果這個新夥伴發現 Alice 傳得很快，他也會回傳資料給 Alice，雙方可能就會建立長期的互惠關係。

此外，除了 BitTorrent 這種依賴 Tracker 的模式，還有一種更去中心化的技術叫做 DHT（Distributed Hash Table，分散式雜湊表），這是一種簡單的資料庫，資料庫紀錄分佈在 P2P 系統中的對等點上。簡單來說，它不需要中央伺服器也能找到 Peer。

總整理

P2P 架構：自我擴充性（Self-Scalability）

在傳統主從式架構（Client-Server Architecture）中，所有檔案都由伺服器負責上傳。

若要將大小為 FF 的檔案傳給 NN 個使用者，伺服器必須傳送 NN 份資料，總流量為 N⋅FN \cdot F 。

當使用者增加時：

  • 伺服器上傳頻寬成為瓶頸。
  • 下載時間隨人數線性增加。
  • 系統擴充成本極高。

在P2P 架構（Peer-to-Peer Architecture）中，每個 Peer（對等點）不只下載，也會上傳已取得的檔案片段。

兩者差異在於：P2P 架構下，新的使用者加入時，不只是增加需求，也同時增加供給。

因此，系統總上傳能力會隨著人數成長而提高，這種特性稱為自我擴充性。

數學模型比較：為什麼 P2P 傳得更快？

  1. 主從式架構的傳布時間 DcsD_\text{cs}
    • 兩個主要瓶頸：
      1. 伺服器上傳限制 $$\frac{N \cdot F}{u_s}$$
      2. 最慢客戶端下載限制 $$\frac{F}{d_\text{min}}$$
    • 因此傳布時間： $$D_\text{cs} \ge max{\frac{N \cdot F}{u_s} , \frac{F}{d_\text{min}}}$$
    • 當 NN 很大時，時間幾乎與 NN 成正比（線性成長），擴充性極差。
  2. P2P 架構的傳布時間 DP2PD_\text{P2P}
    • 三個限制條件：
      1. 伺服器至少要上傳一份完整檔案： $$\frac{F}{u_s}$$
      2. 最慢下載者限制： $$\frac{F}{d_\text{min}}$$
      3. 系統總上傳能力限制： $$\frac{N \cdot F}{u_s + u_1 + \cdots + u_N}$$
    • 因此傳布時間： $$D_\text{P2P} \ge max{\frac{F}{u_s},\frac{F}{d_\text{min}},\frac{N \cdot F}{u_s + \sum^{N}_{i=1}u_i}}$$
    • 關鍵在於第三項的分母：∑ui\sum u_i ，當 NN 增加時，分子增加同時分母也增加，因此傳布時間不再呈現線性成長，而是趨於平緩。

實際應用：BitTorrent

最著名的 P2P 檔案分發協定。

核心概念：

  • Torrent（奔流）：參與某個檔案分發的所有 Peers。
  • Tracker（追蹤伺服器）：協助 Peer 找到其他 Peer。
  • Chunks（檔案片段）：通常切成 256KB 小區塊。

BitTorrent 的三大關鍵設計

  1. Rarest First（最稀有者優先）
    • 下載策略：
      • 詢問鄰居有哪些片段。
      • 優先下載副本最少的片段。
    • 目的：
      • 防止稀有片段消失。
      • 提高整體檔案存活率。
      • 加速稀有資料在網路中擴散。
  2. Tit-for-Tat（以德報德）
    • 上傳策略：
      • 每 10 秒選出 4 個對自己上傳最快的鄰居。
      • 回報給這 4 個人資料（Unchoked）。
    • 形成互惠機制：你給我頻寬，我也給你頻寬。
    • 避免了搭便車（Free Rider）問題。
  3. Optimistic Unchoking（樂觀無阻）
    • 每 30 秒隨機選 1 人給予頻寬
    • 尋找潛在更好的合作對象
    • 這樣的設計有以下優點：
      • 保持網路彈性。
      • 讓新加入者有機會建立連結。
      • 避免固定關係僵化。

DHT（Distributed Hash Table，分散式雜湊表）

除了依賴 Tracker 的模式外，還可以使用 DHT（Distributed Hash Table）。

這是一種去中心化資料庫：

  • 不需要中央伺服器。
  • Peer 自己維護節點資訊。
  • 能直接查詢其他 Peer。

使 P2P 系統更加去中心化與可擴充。

主從式架構 vs P2P 架構

比較項目主從式P2P
上傳來源只有伺服器所有 Peer
擴充性差（線性成長）高（自我擴充）
瓶頸伺服器頻寬最慢下載者或總上傳能力
大規模分發效率低效率高