P2P(peer-to-peer,對等式網路)
end-system可互相連線,可以不用透過server也能運作
常見的P2P協定
eMule: 檔案傳輸
BitTorrent: 檔案傳輸
KanKan:P2P Streaming
Skype:用在VoIP
……………………………….
以下以Bittorrent為範例介紹其原作機制
Bittorrent參與的元件
Peer(對等點):參與p2p的電腦,
Neighbors peer(相鄰對等點): 與對等點成功建立連線的其他對等點
Torrent:所有參與檔案傳輸的對等點
Chunks: 傳輸檔案的最小基本單位,預設256KB
Tracker(追蹤者): Torrent內至少會有一個的基礎節點, 讓剛加入torrent的peer註冊,以追蹤對等點的狀況
Peer list: 記錄每個peer的IP, 會記錄剛加入的peer一開始要聯繫的IP清單
Peer行為
1.當peer剛加入Torrent時,
向tracker註冊自己,
此時peer沒有任何chunk
2.tracker將peer list給剛加入的peer
剛加入的peer會先和peer list中的IP建立連線
3.peer在取得檔案時,
peer會週期性的告知tracker目前狀況,
會從neighbors peer下載越來越多chunk,同時也會上傳chunk給neighbors peer
peer可能會隨時離開或加入Torrent
4.一但peer取得所需要的完整檔案,
可能會離開Torrent,
或是在Torrent中繼續分享chunk給neighbors peer
下載策略, rarest first(最稀有優先)
peer會有所有neighbors peer的chunks列表, 每個列表都會不同,
peer會根據自己缺少的chunk和這些列表,計算出最稀有的chunk,並向有此chunk的neighbors peer要求下載
此策略可以讓最稀有的chunk逐漸變普及,讓各peer有機會下載
上傳策略,tit-for-tat(以德報德策略)
peer只會將chunk上傳給unchoked和optimistically unchoked的neighbors peer
unchoked(無阻的):peer每10秒會計算前4名可最快下載的neighbors peer
optimistically unchoked(樂觀無阻的): peer每30秒會隨機選擇1名neighbors peer
choked(被阻斷的):除了這5個neighbors peer以外的neighbors peer都是被阻斷的
此策略可找出更好的trading partners
…
DHT(distributed hash table,分散式雜湊表)
Distributed P2P database, peer可用來查詢那個檔案在那個peer的資料庫
由key,value組成的table , ex: (linux, 對等點a) , (linux, 對等點b)
DHT散布在各peer, 每個peer僅持有整體key,value配對的一部份
DHT運作屬於overlay network,也就是在實體網路之上會有自己的邏輯網路
DHT角色
key負責peer: 擁有此keyValue配對的peer
immediate successor peer: 最接近此peer ID的下一個peer
immediate predecessor peer:最接近此peer ID的上一個peer
循環式DHT搜尋key負責對等點
peer搜尋key負責peer時, 只會問immediate successor peer
若immediate successor peer沒有,就會在問他的immediate successor peer,以此類推
若immediate successor peer有,就會回傳給原始peer, 自己是key負責peer
ps:
peer只會處理immediate predecessor peer的搜尋
ps:
此搜尋機制最遭的情況下, 會一個一個問peer問到最後才找到
在DHT儲存keyvalue配對
1.計算key的hash
2.根據以下步驟決定peer
找出和此hash一樣的peer ID
若無,則尋找最接近此hash的peer ID,而且必須是下一個
若無,則尋找最小的peer ID
3.根據此peer ID , 儲存此keyvalue到此peer
ex:
假設peer有4個,識別碼分別是1,2,4,8
若key的hash為5,就將此keyvalue配對插入下一個最接近的peer 8
若key的hash為9,就將此keyvalue配對插入最小的peer 1
peer churn:離開DHT
peer會偵測後2個immediate successor peer
若immediate successor peer離開 ,
則讓第二個immediate successor peer當第一個
搜尋DHT下個對等點
當peer加入DHT時, 若不知道immediate successor peer和immediate predecessor peer
就會尋問存在DHT的其中1個peer,此peer會一路轉送此問題,
當轉送到正確的immediate predecessor peer ,此peer做2件事
1.直接回覆給剛加入peer以下資訊
immediate predecessor peer:自己
immediate successor peer:自己的下一個peer
2.將原本immediate predecessor peer設成剛加入的peer