# Computer Networking — 2.5 Peer-to-Peer File Distribution

contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)>

###### tags: `Computer Networking`

目前為止在本章當中所提到的那些服務 —— 包含 Web、email，還有 DNS —— 都是採用主從式架構的服務，並且都大量仰賴那些持續在線提供服務 (always-on) 的伺服器作為基礎建設。我們先前在 2.1.1 節當中有提到，如果採用的是對等式 (P2P) 架構，那麼我們就幾乎不需要仰賴任何 always-on 的伺服器了。取而代之的是一對又一對維持著斷斷續續的連線的主機，又稱做 peer，直接與彼此互相通訊。Peers 並不是為服務提供商所擁有的，而是由一般使用者所控制的桌上型電腦或是筆記型電腦。

在本節當中我們要介紹的是一個對等式網路底下自然而然就會產生的一個應用服務，也就是讓一台單一的伺服器在大量的主機（也就是 peers）之間分享大型檔案。這些檔案有可能是最新版本的 Linux 作業系統，一個既存的作業系統或是應用程式的補丁，一個 MP3 音樂檔案，或是一個 MPEG 影片檔案。如果我們採用主從式架構來分享檔案，那麼那台提供檔案的主機就必須親自把這些檔案的副本送到每一台 peer 手中 —— 這會造成該伺服器大量的負擔，而且會消耗掉大量的伺服器頻寬。在 P2P 的檔案分享系統當中，每一個 peer 都可以把他手上從別的 peer 那裡拿來的檔案再次分送給其他人，因此就可以在這個分送的過程中協助伺服器一起分享檔案。截至 2016 年，最受歡迎的 P2P 檔案分享協定就是 BitTorrent。BitTorrent 協定由 Bram Cohen 創始，現在已經有了許多不同的、獨立的 BitTorrent 客戶端能夠支援該協定，就像有許多不同的瀏覽器遵守 HTTP 協定一樣。在接下來的小節當中，我們首先會在檔案分享這個應用的脈絡下，觀察 P2P 架構自我擴展的性質 (self-scalability)。接著我們會再介紹 BitTorrent 的一些細節，我們會著重在它最重要的特徵和功能上。

### Scalability of P2P Architectures

> Figure 2.22 檔案傳遞問題的圖例

為了比較主從式架構和對等式架構的異同，並展示對等式架構與生俱來的自我擴展性質，現在我們來假想一個簡單的量化模型，這個模型模擬了在一個固定的 peer 集合當中傳遞檔案的行為，該集合中同時具有上述兩種架構的電腦。如同 Figure 2.22 所示，伺服器跟 peer 都是透過接取線路連接到網際網路上的。我們將伺服器的接取線路的上傳速率記為 `u_s`、第 $i$ 個 peer 的接取線路的上傳速率記為 `u_i`、第 $i$ 個 peer 的接取線路的下載速率記為 `d_i`，另外，這個要分享的檔案的大小（以 bit 為單位）計為 $F$，而想要取得這份檔案的副本的電腦數量則記為 $N$。令**傳遞時長**為所有 $N$ 個 peer 都得到該檔案的副本所需耗費的總時長。在底下我們計算主從式架構和對等式架構分別所需的傳遞時長時，我們都會做一個讓模型簡單化的（但不失精確的 [Akella 2003]）假設，那就是網際網路的核心具有充足的頻寬，因此所有的傳輸瓶頸都是發生在接取線路上。我們同時也假設伺服器和客戶端都沒有在傳遞檔案的同時還同時在使用其他的網路服務，所以他們的上傳與下載頻寬是全部都用在檔案傳遞上的。

我們首先來計算主從式架構的傳遞時長，我們將其計為 $D_{cs}$。在主從式架構當中，沒有任何的 peer 會協助檔案的傳遞。我們可以觀察到以下兩個事實；

* 伺服器本人必須親自把一份檔案副本傳送給這 $N$ 台 peer，因此伺服器總共需要傳送 $NF$ bits。由於伺服器的上傳速率是 $u_s$，因此傳遞檔案所需的總時長為 $NF / u_s$。
* 令 $d_{\text{min}}$ 為所有 peer 中下載速率最慢的那台的下載速率，也就是 $d_{\text{min}} = \text{min}\{d_1, d_p, \ldots, d_N\}$。這台下載速率最慢的 peer 要取得這個有 $F$ bits 那麼大的檔案，至少得花上 $F/d_{\text{min}}$ 秒才夠。因此最小的傳遞時長至少也會有 $F/d_{\text{min}}$。

同時考慮這兩點事實，我們會得到

$$
D_{cs} \geq \text{max}\Bigg\{\frac{NF}{u_s}, \frac{F}{d_{\text{min}}}\Bigg\}
$$

這條式子告訴了我們主從式架構的傳遞時長的下限。在 homework problem 裏面，你會需要試著證明透過合理的檔案傳輸排程，這個下限是真的可以達到的。所以在這裡我們就直接令下限為真正的傳遞時長，也就是

$$
D_{cs} = \text{max}\Bigg\{\frac{NF}{u_s}, \frac{F}{d_{\text{min}}}\Bigg\} \tag{2.1}
$$

從 Equation 2.1 當中我們可以發現，當 $N$ 足夠大時，主從式架構所花費的傳遞時長就會是 $NF/u_s$。因此，傳遞時長是隨著 peer 的數量 $N$ 呈線性增長的。所以，舉例來說，如果網路上的 peer 數量在一個星期之內從一千台增長了一千倍，變成一百多萬台，那麼在所有 peer 之間傳遞檔案所需花費的時長就會跟著增加 1000 倍。

現在讓我們用類似的方法來分析對等式架構所需的傳遞時長，在對等式架構中，所有的 peer 都能協助伺服器一起傳遞檔案。更精確來說，每當一個 peer 收到一個檔案資料時，他都可以使用自己的上傳頻寬來將這個檔案再次傳遞出去給其他的 peer。分析對等式架構所需的傳遞時長某種程度上比分析主從式架構還要更困難，因為在這個情境中，傳遞時長的多寡會取決於每一個 peer 是怎麼把自己手中的一部份檔案分享給其他 peer 的。儘管如此，我們還是有辦法求出一個簡單的算式來代表最小傳遞時長 [Kumar 2006]。為了做到這件事，我們必須先考慮以下三點事實：

* 在傳遞檔案過程的最一開始，只有伺服器擁有那一份檔案。為了要把這個檔案完整的傳輸到整個 peer 的社群當中，這個伺服器必須要把該檔案的每一個 bit 都傳到他的接取線路中至少一次才行。因此最小傳遞時長至少會有 $F/u_s$。（不像主從式架構，曾經被伺服器傳過一次的 bit 不一定需要再被伺服器傳送第二次，因為 peer 和 peer 之間會自己再把這個 bit 分享出去。）
* 就跟主從式架構的情境一樣，下載速率最慢的 peer 要取得這個有 $F$ bits 大的檔案至少要花上 $F/d_{\text{min}}$ 秒。因此最小的傳遞時長至少也會有 $F/d_{\text{min}}$。
* 最後，我們可以觀察到如果把整個系統視為一體，則此系統的上傳頻寬就會等同於伺服器的上傳速率加上個別的 peer 的上傳速率，也就是 $u_{\text{total}} = u_s + u_1 + \ldots + u_N$。這個系統必須要將該檔案的 $F$ 個 bits 完整傳送（上傳）到共 $N$ 台的 peer 去，也就是總共要傳輸 $NF$ 個 bits。上傳的速率不可能比 $u_{\text{total}}$ 還要更快，因此最小傳遞時長也就至少要 $NF / (u_s + u_1 + \ldots + u_N)$。

同時考慮這三點事實，我們就可以得到對等式架構中的最小傳遞時長，記為 $D_{\text{P2P}}$。

$$
D_{\text{P2P}} \geq \text{max}\Bigg\{\frac{F}{u_s}, \frac{F}{d_{\text{min}}}, \frac{NF}{u_s + \sum\limits_{i=1}^{N}{u_i}}\Bigg\} \tag{2.2}
$$

Equation 2.2 告訴了我們對等式架構的最小傳遞時長的下限。結果我們會發現，如果每一個 peer 在取得了一個 bit 的當下就馬上再把他分享給下一個 peer，那麼就真的會有一個再次傳遞檔案的策略是可以達到這個下限的 [Kumar 2006]（我們會在作業當中證明這個結論的 special case）。不過在現實中，檔案並不是以 bit 為單位，而是一塊一塊的被再次傳遞的，在這個情況下，Equation 2.2 還是可以算出一個很不錯的近似值，來近似實際的最小傳遞時長。所以在這裡我們還是直接令下限為真正的傳遞時長，也就是

$$
D_{\text{P2P}} = \text{max}\Bigg\{\frac{F}{u_s}, \frac{F}{d_{\text{min}}}, \frac{NF}{u_s + \sum\limits_{i=1}^{N}{u_i}}\Bigg\} \tag{2.3}
$$

> Figure 2.23 對等式架構和主從式架構分別的傳遞時長

Figure 2.23 比較了這兩種架構的最小傳遞時間，並假設在這兩種架構中，所有 peer 的上傳速率都是 $u$。在 Figure 2.23 中，我們令 $F/u = 1$ 小時、$u_s = 10u$，並且 $d_{\text{min}} \geq u_s$。因此，如果一個 peer 可以在一個小時內上傳完整個檔案，那麼伺服器的傳輸速率就是 peer 上傳速率的 10 倍，並且（為了簡化模型）peer 的下載速率被設定成一個足夠大的速率，因此不會對傳遞時長有所影響。我們可以從 Figure 2.23 中觀察到：在主從式架構中，傳遞時長是隨著 peer 的數量毫無上限地呈線性增長的；但如果是使用對等式架構，最小傳遞時長不僅永遠都小於主從式架構的最小傳遞時長，不管 peer 的總數 $N$ 到底有多大，最小傳遞時長也永遠都小於一個小時。因此我們會說，對等式架構可以自我擴展。這個可擴展的性質是「peer 同時作為資料的消費者和再分享者」自然所導致的現象。

### BitTorrent

BitTorrent 是一個很有名的檔案傳輸用的 P2P 協定 [Chao 2011]。在 BitTorrent 的術語中，他們稱呼「所有共同參與傳遞某一個檔案的 peer 的集合」叫作一個 *torrent*。在某一個 torrent 裡面的 peer 們會從其他的 peer 那邊下載該檔案的等大的 *chunks*，這些 chunks 的大小一般來說是 256 kbytes。當一個 peer 剛被加進一個 torrent 裡時，他手上一個 chunk 也沒有，但隨著時間經過他就會蒐集到愈來愈多的 chunks。在它下載 chunk 的同時，他也會上傳這些 chunk 到別的 peer 那邊去。一旦一個 peer 獲得了完整的檔案，他可以選擇（自私地）離開這個 torrent，或是（無私地）留在 torrent 中繼續協助上傳 chunk 給其他 peer。另外，peer 也可以在下載檔案到一半的任何時候離開這個 torrent，然後等等再重新加進來。

現在讓我們來更進一步看看 BitTorrent 是怎麼運作的。由於 BitTorrent 是一個相對複雜的協定和系統，因此我們只會描述它最重要的一些機制而已，太細節的東西我們就先略過不看，如此一來我們才能一覽全局。每一個 torrent 都有一個作為基礎設施的節點，稱為 *tracker*。每當一個 peer 加入一個 torrent，他會跟 tracker 註冊自己，並且定期跟 tracker 通知說自己還待在 torrent 裡面。藉由這個動作，tracker 就可以持續追蹤還有哪一些 peer 還在參與這一個 torrent。在任何時候，一個 torrent 可能有小於十個，或是多於千個 peer 同時參與檔案傳遞的動作。

> Figure 2.24 透過 BitTorrent 進行檔案傳輸

就如同 Figure 2.24 所示，當一個新的 peer，Alice，新加入這個 torrent 時，tracker 會從正在參與這個 torrent 的所有 peer 中隨便挑一個子集合（為了更具體一點，假設該子集合內有 50 個 peer 好了），並且把這 50 個 peer 的 IP 位址傳送給 Alice。一旦獲得了這個 IP 位址的列表，Alice 就會嘗試跟這個列表上的所有 peer 建立並行的 (concurrent) TCP 連線。我們把有成功跟 Alice 建立起 TCP 連線的這些 peer 稱呼為「鄰接 peer (neighboring peers)」（在 Figure 2.24 當中，Alice 看起來只有三個鄰接 peers，但正常來說應該要有更多個）。隨著時間經過，有一些 peer 可能會離開，而（在這 50 個 peer 以外的）其他 peer 可能會嘗試跟 Alice 建立起 TCP 連線。所以一個 peer 的鄰接 peer 是有可能會浮動的。

在任意的時間點，每一個 peer 都會擁有該檔案的 chunks 的子集合，而不同的 peer 可能會擁有不同的 chunks 子集合。Alice 會（透過 TCP 連線）定期跟他鄰接的 peer 們要求他們所擁有的 chunk 列表。如果 Alice 有 $L$ 個不同的鄰居，她就會得到 $L$ 個 chunks 的列表。有了這些列表，Alice 就可以發出請求去要他目前還沒有擁有的 chunks（也是透過 TCP 連線）。

因此在任意的時間點，Alice 都擁有檔案的 chunks 的子集合，也知道她的鄰居們擁有哪些 chunks。有這些資訊，Alice 就需要做兩個很重要的決定。第一，她應該要先要求哪一個 chunk 好呢？第二，她應該要跟哪一個鄰居要呢？在決定要先要哪一個 chunk 時，Alice 會使用**稀有的先拿 (rarest first)** 這個策略。也就是她會從她還沒擁有的 chunks 當中，找出在她的鄰居中最少出現的那一個（也就是擁有該 chunk 的鄰居人數最少的那一個），然後最優先請求這一個 chunk。如此一來，愈稀少的 chunk 就可以愈快被重新傳遞出去，這樣就能（大致上）讓存在於 torrent 中的每一個 chunk 的副本數量變得一樣多。

（而當有請求傳過來時，）為了決定優先回覆哪一個請求，BitTorrent 使用了一個很聰明的交易演算法。這個演算法的基本概念就是：Alice 會優先選擇*提供她資料的速率最快的*鄰居來進行回應。具體來說，對於每一個鄰居，Alice 都會持續測量這些鄰居傳送資料給她的傳輸速率，然後從中挑選出傳得最快的四個鄰居。作為回報，Alice 也會傳送 chunks 給這四個鄰居。每隔 10 秒鐘，她都會重新測量一次傳輸速率，並且有可能改變這四個鄰居的人選。在 BitTorrent 的術語當中，這四個鄰居被稱為 **unchoked**（沒有窒息的人）。重要的是，每隔 30 秒鐘，Alice 也會隨機挑選一個她的鄰居，並且送出一個 chunk 給他。假設這個被隨便挑中的鄰居叫作 Bob 好了。在 BitTorrent 的術語當中，Bob 被稱為 **optimistically unchoked**（樂觀的 unchoked） 。由於 Alice 開始傳送資料給 Bob，她有可能會變成 Bob 的鄰居當中傳輸速率前四快的人，在這個情況下，Bob 也會開始傳資料給 Alice。如果 Bob 傳資料給 Alice 的速度夠快的話，就會換 Bob 也變成 Alice 的前四快的資料提供者。換句話說，每隔 30 秒，Alice 都會隨機挑選一個新的交易伙伴，並且跟那個伙伴進行交易。如果兩個人都滿意交易的結果，那麼他們就會把彼此都放進前四名的資料傳輸對象內並且跟彼此交換資料，直到某一方找到了更好的交易伙伴為止。這個演算法的影響就是，能夠以合適的上傳速率進行資料傳輸的 peer 更容易可以找到彼此，而隨機鄰居挑選的作法也更容易讓新的 peer 可以取得 chunk，由此一來他們才能有東西跟別人做交易。除了這五個人（前四快的人和被隨機挑中的那個人）以外的其他 peer 都被稱為 "choked"（窒息的人），意思就是說他們不會從 Alice 這邊收到任何的 chunk。BitTorrent 還有幾個很有趣的機制，我們在這邊沒有聊到，包含 pieces (mini-chunks)、管線化、隨機優先選擇、終局模式，還有反冷落 (anti-snubbing) 機制等等 [Cohen 2003]。

上述的交易演算法的獎勵機制，常常被稱為是「[投桃報李 (tit-for-tat)](https://zh.wikipedia.org/zh-tw/%E4%BB%A5%E7%89%99%E9%82%84%E7%89%99)」的策略 [Cohen 2003]。已經有研究證明這個獎勵機制是可以被巧妙地規避掉的 [Liogkas 2006; Locher 2006; Piatek 2007]。儘管如此，整個 BitTorrent 的生態圈還是很廣泛地成功了，有上百萬個同時在線的 peer 形成數十萬個 torrents 進行檔案分享。如果 BitTorrent 沒有這種「投桃報李」的（或是類似的）設計，就算剩下的功能通通都沒變，BitTorrent 可能連存在都不會存在，因為那樣一來，絕大部分的使用者都會變成[搭便車](https://zh.wikipedia.org/zh-tw/%E6%90%AD%E4%BE%BF%E8%BD%A6%E9%97%AE%E9%A2%98)的人 (freerider) [Saroiu 2002]。

作為討論 P2P 的收尾，我們在此再稍微介紹另一個 P2P 的應用程式，那就是分散式雜湊表 (Distributed Hash Table, DHT)。分散式雜湊表是一種簡單的資料庫，但這個資料庫當中的資料是被分散地儲存在 P2P 系統當中的各個 peers 上的。DHT 已經被廣泛地實作（例如：在 BitTorrent 中）並且也被作為一個研究主題廣泛地研究。我們在合作網站上的影片筆記中提供了一個 DHT 的簡介。（註：這個影片已經被下架了 Q）

----

[<< 2.4 DNS — The Internet’s Directory Service](https://hackmd.io/@kaeteyaruyo/computer-networking-2-4) | [目錄](https://hackmd.io/@kaeteyaruyo/computer-networking-index) | [2.6 Video Streaming and Content Distribution Networks >>](https://hackmd.io/@kaeteyaruyo/computer-networking-2-6)